Research map / Optimization / Nonconvex and smooth optimization
Tight Risk Bounds for Gradient Descent on Separable Data
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 a smooth loss with tail exp(-x) and run gradient descent | Linear classification on γ-separable data · γ-separable data; exponential tail exp(-x) | population risk bound: \Theta\left( \frac{\log^2(T)}{\gamma^2T}+\frac{ \log^2(T)}{\gamma^2n}\right) | Helped |
| Use a polynomially decaying loss tail x^{-α} | Gradient descent on γ-separable data · γ-separable data; polynomial tail x^{-α} | population risk bound: \Theta\brk2{\brk!{\frac{1}{\gamma}}^{\frac{2\alpha}{2+\alpha}}\brk2{\frac{1}{T^{\frac{\alpha}{2+\alpha}}}+\frac{T^{\frac | Mixed |
| Use a loss with tail exp(-x^{α}) | Gradient descent on γ-separable data · γ-separable data; tail exp(-x^{α}) | population risk bound: \Theta\left(\frac{ \log^{\frac{2}{\alpha}}(T)}{\gamma^2 T}+\frac{\log^{\frac{2}{\alpha}}(T)}{\gamma^2 n}\right) | Helped |
| Increase the number of gradient steps | Unregularized gradient descent · Separable classification; surrogate loss risk | population risk | Mixed |
| Impose an additional Lipschitz condition on the loss | Gradient descent risk upper bound · Separable classification | population risk bound | No clear effect |
| Add matching risk lower bounds to the upper-bound analysis | Gradient descent across tail-decay rates and parameter regimes · Separable classification | population risk bound tightness | Helped |
Closest papers by meaning
- Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification (NeurIPS 2025 · similarity 0.93)
- Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence (ICML 2025 · similarity 0.89)
- Stability and Sharper Risk Bounds with Convergence Rate $\tilde{O}(1/n^2)$ (NeurIPS 2025 · similarity 0.88)
- A Universal Growth Rate for Learning with Smooth Surrogate Losses (NeurIPS 2024 · similarity 0.88)
- Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods (ICLR 2025 · similarity 0.88)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · 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.