mlsanityData to 7 Oct 2026

Directional Smoothness and Gradient Methods: Convergence and Adaptivity

arXiv 2403.04081 ↗First posted 6 Mar 2024cs.LG math.OCcited by 15

Not on the map. Why?

Abstract (arXiv)

We develop new sub-optimality bounds for gradient descent (GD) that depend on the conditioning of the objective along the path of optimization rather than on global, worst-case constants. Key to our proofs is directional smoothness, a measure of gradient variation that we use to develop upper-bounds on the objective. Minimizing these upper-bounds requires solving implicit equations to obtain a sequence of strongly adapted step-sizes; we show that these equations are straightforward to solve for convex quadratics and lead to new guarantees for two classical step-sizes. For general functions, we prove that the Polyak step-size and normalized GD obtain fast, path-dependent rates despite using no knowledge of the directional smoothness. Experiments on logistic regression show our convergence guarantees are tighter than the classical theory based on L-smoothness.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 28 of its 47 references that are in the map. First posted on arXiv 6 Mar 2024.

Builds on

28 of 47 references.

References · 28

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
  3. 2014Convex Optimization: Algorithms and Complexitycited by 569
  4. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  5. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 413
  6. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 335
  7. 2020Improved Analysis of Clipping Algorithms for Non-convex Optimizationcited by 88
  8. 2022Adaptive Gradient Methods at the Edge of Stabilitycited by 88
  9. 2022Understanding the unstable convergence of gradient descentcited by 84
  10. 2019Adaptive Gradient Descent without Descentcited by 79
  11. 2020Reconciling Modern Deep Learning with Traditional Optimization Analyses: The Intrinsic Learning Ratecited by 59
  12. 2019Revisiting the Polyak step sizecited by 55
16 more
  1. 2022Making SGD Parameter-Freecited by 50
  2. 2023Toward Understanding Why Adam Converges Faster Than SGD for Transformerscited by 50
  3. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  4. 2023Convex and Non-convex Optimization Under Generalized Smoothnesscited by 44
  5. 2017Online to Offline Conversions, Universality and Adaptive Minibatch Sizescited by 39
  6. 2023Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedulecited by 19
  7. 2017Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuitycited by 18
  8. 2023Normalized Gradients for Allcited by 18
  9. 2021Eigencurve: Optimal Learning Rate Schedule for SGD on Quadratic Objectives with Skewed Hessian Spectrumscited by 15
  10. 2020Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysiscited by 14
  11. 2022Gradient Descent in the Absence of Global Lipschitz Continuity of the Gradientscited by 11
  12. 2021A first-order primal-dual method with adaptivity to local smoothnesscited by 7
  13. 2020First-Order Algorithms Without Lipschitz Gradient: A Sequential Local Optimization Approachcited by 5
  14. 2022Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradientcited by 5
  15. 2023Non-Uniform Smoothness for Gradient Descentcited by 5
  16. 2020Preconditioned accelerated gradient descent methods for locally Lipschitz smooth objectives with applications to the solution of nonlinear PDEscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 6; 2026: 6.

15 papers.

Sort:

  1. 2024Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizescited by 9
  2. 2026Non-Euclidean Gradient Descent Operates at the Edge of Stabilitycited by 7
  3. 2025New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Resultscited by 6
  4. 2024Adaptive Gradient Normalization and Independent Sampling for (Stochastic) Generalized-Smooth Optimizationcited by 4
  5. 2024SPAM: Stochastic Proximal Point Method with Momentum Variance Reduction for Non-convex Cross-Device Federated Learningcited by 3
  6. 2025Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Fastercited by 3
  7. 2025Nested Stochastic Algorithm for Generalized Sinkhorn distance-Regularized Distributionally Robust Optimizationcited by 3
  8. 2025Glocal Smoothness: Line search and adaptive step sizes can help in theory too!cited by 2
  9. 2025Sparse Polyak: an adaptive step size rule for high-dimensional M-estimationcited by 2
  10. 2026The Road Taken: The Role of Optimizers at the Edge of Stabilitycited by 1
  11. 2025First-ish Order Methods: Hessian-aware Scalings of Gradient Descentcited by 0
  12. 2026Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuningcited by 0
3 more
  1. 2026Convergence Guarantees of Gradient Descent for Neural Networks via Generalized Lipschitz Smoothnesscited by 0
  2. 2026A Journey to the Edge of Stabilitycited by 0
  3. 2026Muon Sublates the Edge of Stability in LLM Pretrainingcited by 0