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

Which Algorithms Have Tight Generalization Bounds?

NeurIPS 2025 · 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.

Characterizes which learning algorithms admit tight (estimable) generalization bounds relative to a distribution collection, showing inestimability for inductive biases toward VC subclasses and nearly-orthogonal functions, sufficiency of hypothesis/loss stability, and an exact conditional-variance characterization in ℓ2.

Problem

Which learning algorithms and distribution collections admit tight algorithm- and distribution-dependent generalization bounds in the overparameterized regime, i.e., when the sample size is insufficient for learning.

Approach

Frames tight generalization bounds as estimability of population loss from the sample; shows inductive biases toward (nearly-orthogonal or VC-subclass) hypothesis sets preclude estimability, stability (hypothesis or loss) suffices, and ℓ2-estimability is equivalent to a small expected conditional variance of the loss.

Key results

• Theorem: for VC class H with dimension d and m <= sqrt(d)/10, some subclass F and realizable distributions make any F-interpolating learner not (1/4-o(1), 1/6, m)-estimable on average.
• Theorem: (alpha,beta,m,k)-hypothesis or loss stable learners with k >= Omega(log(1/beta0)/alpha0^2) are (alpha0+alpha1, beta0+beta1, m)-uniformly estimable.
• Fact: l2-estimability holds iff the expected conditional variance of the population loss given S is at most epsilon.

Surprising findings

• Algorithms with no inductive bias that are random can be estimable yet not hypothesis stable, so stability is sufficient but not necessary.
• Estimability is delicate: changing sample size by a small constant (d vs d+10 for parity ERM) can change estimability drastically.

Limitations

• Stability conditions are not necessary for estimability and are hard to verify analytically; checking relies on estimation in practice.
• Constants in inestimability theorems are not optimized and results hold only in the overparameterized regime with small m relative to VC dimension.
• Preliminary experiments on neural network stability are limited to a simple architecture.

Experimental setup

Builds on: Gastpar et al. 2023 fantastic generalization measures and where to find them Kearns and Ron 1999 algorithmic stability Bousquet and Elisseeff 2002 stability

Closest papers by meaning

• Fantastic Generalization Measures are Nowhere to be Found (ICLR 2024 · similarity 0.93)
• Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.89)
• Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power (ICLR 2025 · similarity 0.88)
• Certification-Enhanced Generalization Bounds (NeurIPS 2026 · similarity 0.88)
• Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence (ICML 2025 · similarity 0.88)
• Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization (NeurIPS 2025 · similarity 0.88)