Research map / Learning theory and algorithms / Kernels and regression theory
Generalization Bounds for Uniformly Stable Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the previous second-moment analysis with the new stability-based bound | Uniformly stable data-dependent functions · Uniformly stable data-dependent functions | second moment of estimation error: O(\gamma + 1/n) -> O(\gamma^2 +1/n) | Helped |
| Use the new high-probability analysis instead of the previous uniform-stability bound | Uniformly stable data-dependent functions · Uniformly stable data-dependent functions | high-probability estimation-error bound: O((\gamma +1/n) \sqrt{n \log(1/\delta)}) -> O(\sqrt{(\gamma + 1/n) \log(1/\delta)}) | Helped |
| Apply the new second-moment bound to strongly convex ERM | Strongly convex ERM · Strongly convex ERM | excess loss bound: \frac{4}{\delta \lambda n} -> c_1 \left( \frac{1}{\sqrt{\delta} \lambda n} + \frac{1}{\sqrt{n}} \right) | Helped |
| Choose regularization using the new second-moment bound | Regularized convex ERM · Regularized convex ERM | excess loss bound: \frac{4}{\sqrt{\delta n}}\cdot \left(1 + \frac{8}{\delta n}\right) -> \frac{c_1}{\delta^{1/4}\sqrt{n}} | Helped |
| Choose regularization using the new high-probability bound | Regularized convex ERM · Regularized convex ERM | excess loss bound: O(1/\sqrt{\delta n}) -> \frac{c_2 \sqrt{\ln (1/\delta)}}{n^{1/3}} | Helped |
| Apply the new second-moment bound to projected gradient descent | Projected gradient descent on smooth convex functions · Projected gradient descent on smooth convex functions | excess loss bound: \frac{c_1}{\delta^{1/4}\sqrt{n}} | Helped |
| Apply the new high-probability bound to projected gradient descent | Projected gradient descent on smooth convex functions · Projected gradient descent on smooth convex functions | excess loss bound: \frac{c_2 \sqrt{\ln (1/\delta)}}{n^{1/3}} | Helped |
| Apply the new stability bounds to the expected loss of a differentially private predictor | Differentially private prediction · Differentially private prediction | estimation-error bounds: 16(e^\eps-1)^2 + \frac{2}{n}; 8 \sqrt{\left(2(e^\eps-1) + \frac{1}{n}\right) \cdot \ln (8/\delta)} | Helped |
Closest papers by meaning
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.93)
- Fantastic Generalization Measures are Nowhere to be Found (ICLR 2024 · similarity 0.90)
- Certification-Enhanced Generalization Bounds (NeurIPS 2026 · similarity 0.90)
- Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters (NeurIPS 2026 · similarity 0.89)
- Stability and Sharper Risk Bounds with Convergence Rate $\tilde{O}(1/n^2)$ (NeurIPS 2025 · similarity 0.89)
- Which Algorithms Have Tight Generalization Bounds? (NeurIPS 2025 · similarity 0.89)
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.