Research map / Optimization / Nonconvex and smooth optimization
Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions
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 |
|---|---|---|---|
| Use EBC-adaptive ERM for Lipschitz continuous losses | ERM · Risk minimization under EBC | excess risk: \widetilde O\left(\left(\frac{d}{n}\right)^{\frac{1}{2-\theta}}\right); from the classical \widetilde O(\sqrt{d/n}) rate | Helped |
| Use non-negative smooth convex losses with EBC in ERM | ERM · Risk minimization under EBC | excess risk: \widetilde O\left(\frac{d}{n} + \left(\frac{d P_*}{n}\right)^{\frac{1}{2-\theta}}\right) | Helped |
| Use the large-sample ERM bound for non-negative smooth convex losses | ERM · Risk minimization under EBC; sufficiently large n | excess risk: \widetilde O\left(\left[\frac{d}{n}\right]^{\frac{2}{2-\theta}}+\left[\frac{dP_*}{n}\right]^{\frac{1}{2-\theta}}\right) | Helped |
| Use parameter-free, EBC-adaptive ASA | Stochastic approximation · Risk minimization under EBC | excess risk: \widetilde O\left(\left(\frac{1}{n}\right)^{\frac{1}{2-\theta}}\right); compared with O(1/\sqrt{n}) | Helped |
| Use ASA instead of PSG | ASA and PSG · E2006-tfidf test | square loss | Helped |
| Use ASA instead of SMD | ASA and SMD · E2006-log1p test | square loss | Helped |
| Use ASA instead of SAG | ASA and SAG · Two relatively low-dimensional datasets | square loss | No clear effect |
| Use ASA instead of SAG | ASA and SAG · E2006-tfidf and E2006-log1p test | square loss | Helped |
Closest papers by meaning
- Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back (NeurIPS 2016 · similarity 0.90)
- First-Order Adaptive Sample Size Methods to Reduce Complexity of Empirical Risk Minimization (NeurIPS 2017 · similarity 0.89)
- Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach (NeurIPS 2021 · similarity 0.89)
- Information Theoretic Guarantees for Empirical Risk Minimization with Applications to Model Selection and Large-Scale Optimization (ICML 2018 · similarity 0.89)
- Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails (ICML 2025 · similarity 0.88)
- A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging (NeurIPS 2025 · 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.