Research map / Optimization / Nonconvex and smooth optimization
Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster
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 gradient descent with Armijo line-search converges faster than fixed 1/L step-size GD under a non-uniform smoothness condition, yielding linear rates for logistic regression, softmax policy gradient, and GLMs, plus a convergence result for SGD with stochastic line-search under interpolation.
Problem
Armijo line-search for gradient descent is known to give only constant-factor gains over 1/L step-size GD under standard smoothness; the question is whether it can provably give faster (e.g., linear) rates on common ML objectives, and whether this carries over to stochastic line-search.
Approach
Introduces an (L0, L1) non-uniform smoothness condition where local smoothness scales with function value, plus a gradient-norm bound; shows the Armijo step-size is lower-bounded by 1/(lambda0 + lambda1 f(theta)), so step-sizes grow as the loss shrinks, yielding faster rates without knowing problem constants.
Key results
- For convex (L0=0) objectives such as logistic regression, GD-LS with eta_max=infinity satisfies a bound with T = O((f*/eps + 1) ln(1/eps)), giving faster than sublinear GD(1/L) rates when f* is small.
- On linearly separable logistic regression, GD-LS converges linearly with T = O(ln^2(1/eps)/gamma^2) iterations, versus Omega(1/eps) for GD(1/L).
- For softmax bandit policy gradient, GD-LS gives T = O(K^2 ln(1/eps)) iterations, matching natural policy gradient-type linear rates.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Armijo line-search instead of a constant 1/L step-size | Gradient descent on convex non-uniform smooth logistic-regression objectives · Logistic regression | iterations to ε-suboptimality: O\left(\nicefrac{1}{\epsilon}\right) -> O\left(\left(\nicefrac{f^*}{\epsilon}\right) \, \ln\left(\nicefrac{1}{\epsilon}\ | Helped |
| Use Armijo line-search instead of a constant step-size | Gradient descent on separable logistic regression · Logistic regression on linearly separable data | iterations to ε-suboptimality: \Omega(1/\epsilon) -> O \left( \frac{c }{(1-c) \, (2c-1) \, \gamma^2} \, \left[\ln\left(\frac{1}{\epsilon}\right)\right] | Helped |
| Use Armijo line-search instead of a constant 1/L step-size | Softmax policy gradient · Multi-armed bandit | iterations to ε-suboptimality: \Omega\left(\frac{1}{\epsilon}\right) -> O\left(K^2 \ln\left(\nicefrac{1}{\epsilon}\right) \right) | Helped |
| Ensure the sampled function has loss at least ε/2 | SGD-SLS for separable logistic regression · Logistic regression on linearly separable data | iterations to ε-suboptimality: O\left(\frac{n}{\gamma^2}\, \left[\ln(\frac{n}{\epsilon^2})\right]^2\right) -> O\left(\frac{1}{\gamma^2} \, \left[\ln\le | Helped |
Surprising findings
- GD-LS step-size increases non-monotonically as the loss decreases on separable logistic regression, and the stochastic line-search SGD-SLS analysis yields a rate with an unavoidable linear dependence on n in the worst case.
Limitations
- Stochastic line-search analysis gives O(n ...) rate depending on n in worst case; faster rate requires sampling assumption not implemented.
- Results for non-convex case restricted to gradient domination settings (softmax policy gradient, GLMs with PL condition).
- Analysis assumes exact backtracking (beta approximately 1) and eta_max = infinity.
Experimental setup
Datasets: ijcnn
Benchmarks: ijcnn
Metrics: suboptimality f(theta_t)-f* step-size trajectory
Baselines: GD(1/L) normalized GD GD with Polyak step-size natural policy gradient SARAH
Builds on: Armijo line-search (L0,L1)-smoothness normalized gradient descent Polyak step-size stochastic line-search
Closest papers by meaning
- Toward a Unified Theory of Gradient Descent under Generalized Smoothness (ICML 2025 · similarity 0.89)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.88)
- Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search (NeurIPS 2024 · similarity 0.88)
- MGDA Converges under Generalized Smoothness, Provably (ICLR 2025 · similarity 0.88)
- The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations (ICML 2025 · similarity 0.87)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 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.