Research map / Learning theory and algorithms / Kernels and regression theory

Certification-Enhanced Generalization Bounds

NeurIPS 2026 · Learning theory and algorithms › Kernels and regression theory · approach: Information-theoretic generalization bounds · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Uses abstract gradient training (AGT) reachability analysis to certify sample-specific algorithmic stability and converts it, via a smooth-sensitivity concentration inequality, into sound high-probability bounds on the expected generalization gap.

Problem

Generalization bounds from algorithmic stability are either vacuous (worst-case analysis for neural networks) or non-sound when estimated numerically; existing sound bounds rely on restrictive analytical assumptions.

Approach

Recast dataset-specific algorithmic stability as a formal specification verified by AGT over parameter-space reachable sets, then connect sample-specific certificates to distributional expected gap via a smooth (beta-smooth) sensitivity concentration inequality, using only a constant number of AGT runs.

Key results

• Certified bounds are consistently tighter than analytical sound baselines (HRS uniform bounds) on halfmoons while remaining competitive with unsound numerical bounds.
• Bounds decrease roughly at O(1/sqrt(n)) rate in the sample-size ablation, matching the asymptotic analysis.
• Computing bounds from 100 k-values takes about 2-3.5 seconds per setting on the reported hardware.

Surprising findings

• The KL bound baseline consistently violates soundness, essentially modeling noise around the error.
• Uniform (worst-case) stability bounds are loose because the worst-case test instance with maximal stability lies far from observed data.

Limitations

• AGT over-approximation makes bounds conservative and potentially vacuous for deeper models or longer training.
• Bounds require the certified reachable parameter set to be bounded (effective boundedness), which is verified rather than assumed.
• Bounds bound only the expected generalization gap, not the realized gap; more expensive than closed-form analytical bounds.

Experimental setup

Datasets: halfmoons MNIST ImageNet Twitter hate speech dataset

Benchmarks: halfmoons MNIST ImageNet Twitter hate speech

Metrics: generalization bound tightness cross-entropy generalization gap wall-clock time

Baselines: HRS uniform stability bound KL bound uniform stability bounds data-dependent stability bounds

Builds on: Abstract Gradient Training algorithmic stability smooth sensitivity interval bound propagation McDiarmid's inequality

Closest papers by meaning

• Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite $L_p$ Moments (ICML 2026 · similarity 0.91)
• Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.90)
• Fantastic Generalization Measures are Nowhere to be Found (ICLR 2024 · similarity 0.89)
• Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power (ICLR 2025 · similarity 0.89)
• Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective (ICML 2024 · similarity 0.89)
• Which Algorithms Have Tight Generalization Bounds? (NeurIPS 2025 · similarity 0.88)