Research map / Optimization / Nonconvex and smooth optimization
Directional Smoothness and Gradient Methods: Convergence and Adaptivity
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.
Derives path-dependent sub-optimality bounds for gradient descent using directional smoothness functions, shows closed-form adapted step-sizes for quadratics, and proves Polyak and normalized GD adapt to any directional smoothness without knowing it.
Problem
Gradient descent analyses rely on global L-smoothness and worst-case constants, which are pessimistic and do not reflect the local conditioning along the optimization path, especially when f is not globally smooth.
Approach
Replace global smoothness with directional smoothness functions M(x,y) that depend only on f along the chord between x and y; derive GD bounds in terms of these, show strongly adapted step-sizes (eta = 1/M) are computable (closed form for quadratics, Newton/exponential search in general), and show the Polyak step-size automatically adapts to any directional smoothness.
Key results
- Polyak step-size with gamma=1.5 gives a bound 3*Delta_0 / sum_i M(x_i,x_{i+1})^{-1}, which recovers the classic O(1/k) rate up to constants when f is L-smooth and adapts to the average directional smoothness otherwise.
- For convex quadratics, the strongly adapted point-wise step-size eta_i = ||grad f(x_i)|| / (2||B grad f(x_i)||) recovers the Cauchy-type step-size and approaches the edge of stability at 2/L.
- On UCI logistic regression, the Polyak step-size performs best on every dataset except ozone, where GD with eta=1/D_k solves the problem to high accuracy in a few iterations; theoretical rates are an order of magnitude tighter than L-smoothness rates on ionosphere.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use directional smoothness instead of global L-smoothness for the convergence bound | GD on Ionosphere logistic regression · Ionosphere | theoretical convergence bound | Helped |
| use directional smoothness instead of global L-smoothness for the convergence bound | Polyak GD on Mammographic logistic regression · Mammographic | theoretical convergence bound | Helped |
| use strongly adapted step-sizes instead of the fixed step-size η=1/L | GD on synthetic quadratic problems with Hessian skew · Synthetic quadratic with Hessian skew | convergence | Helped |
| use adaptive step-sizes instead of the fixed step-size η=1/L | GD on three UCI logistic regression problems · Three additional UCI logistic regression problems | convergence | Helped |
| use Polyak step-size instead of the compared GD step-size rules | GD on the additional UCI logistic regression problems · Additional UCI logistic regression problems except Ozone | convergence | Helped |
| use strongly adapted step-sizes η=1/D_k instead of Polyak step-size | GD on Ozone logistic regression · Ozone | convergence | Helped |
| use adaptive step-sizes instead of η=1/L | GD on Horse-colic logistic regression · Horse-colic | convergence rate | Helped |
Surprising findings
- Adapted GD with step-sizes above 2/L is observed, operating at the edge of stability, with directional smoothness much smaller than L along the path.
- The point-wise directional smoothness can be at most a factor of two weaker than L-smoothness, and this factor of two is shown to be unavoidable.
Limitations
- Bounds are sub-optimality bounds; convergence requires a sequence of adapted step-sizes, which are impractical to compute exactly for general functions.
- Accelerated rates with mu=0 require prior knowledge of the minimum step-size.
- Experiments limited to logistic regression on three or four UCI datasets and synthetic quadratics.
Experimental setup
Datasets: UCI logistic regression datasets (ionosphere, mammographic, horse-colic, ozone) synthetic quadratic problems with Hessian skew
Benchmarks: UCI logistic regression problems synthetic quadratics
Metrics: optimality gap f(x_k)-f(x*) theoretical vs actual convergence rate step-size behaviour
Baselines: GD with L-smoothness step-size 1/L Polyak step-size normalized GD AdGD
Builds on: Polyak step-size Nesterov accelerated gradient descent non-uniform smoothness (L0,L1)-smoothness AdGD
Closest papers by meaning
- Toward a Unified Theory of Gradient Descent under Generalized Smoothness (ICML 2025 · similarity 0.93)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.91)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.91)
- Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness (ICLR 2025 · similarity 0.89)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.89)
- Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes (ICML 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.