Research map / Learning theory and algorithms / Sample complexity
The Role of Randomness in Stability
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 that the randomness complexity of replicability and differential privacy is tightly controlled by deterministic global stability, and uses this to characterize randomness complexity of agnostic PAC learning (finite Littlestone dimension, O(log(1/alpha)) scaling).
Problem
How many random bits are needed for algorithmic stability (replicability and differential privacy) in statistical tasks, and in particular for agnostic PAC learning as a function of excess error?
Approach
A weak-to-strong boosting theorem: the number of random bits needed for replicability (certificate complexity) and DP is equivalent up to constants to the log inverse of the best deterministic global stability; combined with an agnostic-to-realizable reduction, this gives error-dependent global stability for agnostic PAC learning exactly when Littlestone dimension is finite.
Key results
- Global stability and certificate complexity satisfy C_Glob <= C_Rep <= C_Glob + 1 for any statistical task.
- A class has bounded error-dependent global stability / certificate complexity iff it has finite Littlestone dimension, with certificate complexity poly(d)+O(VC(H) log(1/alpha)).
- Stability-to-DP and DP-to-stability transforms hold up to log(1/eps)+log(1/delta) additive randomness terms, with user-level DP relating C_DP directly to C_Glob.
Surprising findings
- Without stability constraints, a class with infinite Littlestone dimension has C_Rep(alpha)=infinity for any alpha<1/2, so no globally stable, DP or replicable algorithm better than random guessing exists.
Limitations
- DP-to-stability transforms require parameter constraints such as eps <= c/sqrt(T log T) and delta <= c/T.
- Sample complexity of the replicable agnostic learner is exponential in d (exp(poly(d))), and poly-sample replicable learners with good certificate size remain open.
- Full equivalence between DP complexity and global stability is not established in the parametrized setting.
Experimental setup
Baselines: Dixon et al. 2024 DP complexity Cannone et al. 2024 Chase et al. 2023 list-replicability
Builds on: certificate complexity (Dixon et al.) global stability (Bun et al.) random thresholding replicability (Impagliazzo et al.) DP selection perfect generalization
Closest papers by meaning
- On the Computational Landscape of Replicable Learning (NeurIPS 2024 · similarity 0.88)
- Computationally Efficient Replicable Learning of Parities and Applications (NeurIPS 2026 · similarity 0.87)
- Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale (NeurIPS 2026 · similarity 0.85)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.84)
- The Stability of Online Algorithms in Performative Prediction (NeurIPS 2026 · similarity 0.83)
- Replicable Distribution Testing (NeurIPS 2025 · similarity 0.83)
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.