Research map / Optimization / Nonconvex and smooth optimization
Information Complexity of Stochastic Convex Optimization: Applications to Generalization, Memorization, and Tracing
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.
Shows every dimension-independent epsilon-learner for convex-Lipschitz-bounded and strongly convex SCO must have CMI Omega(1/eps^2) and Omega(1/eps), tight, and derives memorization, compression, and ISCMI implications.
Problem
How much information (CMI) must an epsilon-accurate learner reveal about its training data in stochastic convex optimization, and what does this imply for memorization, generalization bounds and sample compression?
Approach
Uses fingerprinting-style lower bound constructions over the hypercube with a supersample/CMI framework to show that any SCO learner with optimal sample complexity must have CMI scaling with its sample size (Omega(1/eps^2) for CLB, Omega(1/eps) for strongly convex), and that a membership adversary can identify that many training points.
Key results
- For CLB (1-Lipschitz, bounded domain) every epsilon-learner has CMI Omega(1/eps^2) for some distribution in dimension d >= Omega(n^2 log n), matched by an upper bound of O(log(2/delta)/eps^2).
- For 1-Lipschitz 1-strongly convex SCO, every epsilon-learner has CMI Omega(1/eps), which is tight.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require ε-accurate learning on CLB SCO | Every ε-learner · CLB SCO | CMI: Ω(1/ε^2) | Helped |
| Add strong convexity to the SCO losses | Every ε-learner · Strongly convex SCO | CMI: Ω(1/ε^2) -> Ω(1/ε) | Mixed |
| Use an ε-learner with a subsample of O(log(1/δ)/ε^2) examples | CLB SCO learning · CLB SCO | CMI: O(1/ε^2) | Helped |
| Add strong convexity to the SCO losses | Membership inference adversary · Strongly convex SCO | memorized samples recalled: Ω(1/ε^2) -> Ω(1/ε) | Mixed |
| Use a CMI-based generalization bound for an optimal-sample-complexity learner | CLB SCO learning · CLB SCO | generalization bound: Θ(LR) | Hurt |
| Measure individual-sample CMI instead of standard CMI | Every ε-learner · CLB SCO | ISCMI: Ω(1/ε^2) | No clear effect |
Surprising findings
- CMI-based generalization bounds are vacuous (order Omega(1)) for every optimal-sample-complexity learner in SCO, not just gradient descent.
- Dimension-independent sample compression schemes of constant size cannot exist for SCO, with compression size at least Omega(n).
Limitations
- Lower bounds hold for some distribution in sufficiently high dimension (d >= Omega(n^2 log n)), not for all problems.
- Results are purely theoretical with no experiments.
- Individual-sample CMI lower bounds are stated for proper learners in one corollary.
Experimental setup
Metrics: conditional mutual information excess population risk soundness recall
Baselines: gradient descent regularized ERM input-output mutual information bound
Builds on: conditional mutual information (Steinke and Zakynthinou 2020) fingerprinting codes input-output mutual information bounds (Xu and Raginsky) individual sample CMI
Closest papers by meaning
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.89)
- On Traceability in $\ell_p$ Stochastic Convex Optimization (NeurIPS 2025 · similarity 0.89)
- Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization (NeurIPS 2025 · similarity 0.89)
- Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence (ICML 2025 · similarity 0.87)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.87)
- Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.87)
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.