Research map / Learning theory and algorithms / Kernels and regression theory
Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization
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.
Adds stochastic random projection plus quantization to CMI generalization bounds, yielding bounds that stay O(1/sqrt(n)) on the Attias et al. and Livni SCO counterexamples and showing memorization can be avoided by an auxiliary algorithm.
Problem
Classic MI and CMI generalization bounds become vacuous or fail to decay with n on certain stochastic convex optimization counterexamples (Attias et al. 2024, Livni 2023), and the memorization necessity result for SCO raises questions about the role of memorization in generalization.
Approach
Combine a random Johnson-Lindenstrauss-style projection of the hypothesis onto a low-dimensional subspace with lossy quantization of the projected model, then bound the generalization error of the projected-back auxiliary model via disintegrated CMI plus a distortion term, so the CMI is computed in low dimension while distortion is controlled by concentration.
Key results
- On the Attias et al. CLB counterexample, the new bound gives generalization error at most 8LR/sqrt(n), versus Theta(LR) for the standard CMI bound.
- For the CSL counterexample, the new bound gives O(1/sqrt(n)), yielding O(sqrt(epsilon)) at the ERM sample complexity.
- For generalized linear stochastic optimization, the bound gives O(1/n^{1/4}) rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add stochastic projection and lossy compression to the CMI bound | Generalization analysis of the CLB counterexample · CLB counterexample (P_cvx) | generalization error bound: \Theta(LR) -> 8LR/\sqrt{n} | Helped |
| Add stochastic projection and lossy compression to the CMI bound | Generalization analysis of the CSL counterexample · CSL counterexample (P_scvx) | generalization error bound: \Omega\left(\frac{1}{\varepsilon}\right) -> \frac{8L_c R}{\sqrt{n}} | Helped |
| Apply stochastic projection and lossy compression in the CMI bound | Livni squared-distance counterexample · Livni squared-distance counterexample | generalization error bound: vacuous -> \mathcal{O}(1/\sqrt{n}) | Helped |
| Apply stochastic projection and lossy compression in the CMI bound | Generalized linear stochastic optimization · Generalized linear stochastic optimization | generalization error bound: \mathcal{O}\left(\frac{LRB}{\sqrt[4]{n}}\right) vs. \mathcal{O}(1/\sqrt{n}) | Mixed |
| Project and quantize the model using a stochastic projection | Any learning algorithm in the CLB memorization problem · CLB memorization problem (P_cvx) | absolute generalization-error distortion: \mathcal{O}\left(n^{-r}\right) | Helped |
| Project and quantize the model using a stochastic projection | Any learning algorithm in the CLB memorization problem · CLB memorization problem (P_cvx) | traced training samples: m=o(n) or \xi \geq q | Helped |
| Use a one-dimensional stochastic projection (d=1) | Stochastic projection + lossy compression CMI · CLB counterexample (P_cvx) | generalization error bound: \mathcal{O}(LR/\sqrt{n}) | Helped |
Surprising findings
- The projected-quantized auxiliary model has squared norm growing as Omega(n^3), which breaks the boundedness assumption used in Attias et al.'s impossibility proofs.
- Memorization is not necessary for good generalization: an auxiliary algorithm with comparable generalization error does not trace the training data.
Limitations
- Generalized linear extension only achieves O(1/n^{1/4}) rate, which is not optimal.
- Results are stated for stochastic convex optimization and do not extend directly to general learning settings, per the authors' conclusion.
- The auxiliary algorithm for memorization is data-distribution dependent in the deterministic-projection variant.
Experimental setup
Metrics: generalization error bound order in n CMI order
Baselines: CMI bound (Steinke and Zakynthinou) individual-sample CMI bound MI bound (Livni 2023 single-datum)
Builds on: conditional mutual information bounds (Steinke and Zakynthinou) Attias et al. 2024 counterexample lossy compression MI bounds (Hellström and Durisi) Johnson-Lindenstrauss lemma
Closest papers by meaning
- Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence (ICML 2025 · similarity 0.90)
- Slicing Mutual Information Generalization Bounds for Neural Networks (ICML 2024 · similarity 0.89)
- Fantastic Generalization Measures are Nowhere to be Found (ICLR 2024 · similarity 0.89)
- Information Complexity of Stochastic Convex Optimization: Applications to Generalization, Memorization, and Tracing (ICML 2024 · similarity 0.89)
- Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective (ICML 2024 · similarity 0.88)
- Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.