A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity

• URL: http://arxiv.org/abs/2604.13393v1
• Date: Wed, 15 Apr 2026 01:43:24 GMT
• Title: A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity
• Abstract summary: We show that descent with an adaptive stepsize converges locally at a nearly-linear rate for smooth functions.<n>We obtain a more adaptive variant than the original algorithm with encouraging numerical performance.
• Score: 7.5757345574662205
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Davis, Drusvyatskiy, and Jiang showed that gradient descent with an adaptive stepsize converges locally at a nearly-linear rate for smooth functions that grow at least quartically away from their minimizers. The argument is intricate, relying on monitoring the performance of the algorithm relative to a certain manifold of slow growth -- called the ravine. In this work, we provide a direct Lyapunov-based argument that bypasses these difficulties when the objective is in addition convex and a has a unique minimizer. As a byproduct of the argument, we obtain a more adaptive variant than the original algorithm with encouraging numerical performance.

Related papers

• Local linear convergence of gradient methods for overparameterized Gaussian mixtures [14.415705090244252]
  We show that a standard divergence measure minimized by statistical learning procedures possesses a manifold of slow growth on which the well-known Polyak stepsize reduces the loss geometrically.<n>We also show that our method converges to nearly optimal solutions -- up to a natural misspecification threshold -- for mixtures with arbitrary weights.
  arXiv  Detail & Related papers  (2026-05-29T07:25:36Z)
• Preconditioned subgradient method for composite optimization: overparameterization and fast convergence [16.437253140200788]
  Composite optimization problems involve minimizing the composition of a smooth map with a convex function.<n>The subgradient method achieves local linear convergence when the composite loss is well-conditioned.<n>We introduce a Levenberg-Morrison-Marquardt subgradient method that converges linearly under mild regularity conditions.
  arXiv  Detail & Related papers  (2025-09-15T00:26:47Z)
• Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth [20.47417191285737]
  We show that gradient descent with an adaptive stepsize converges at a local (nearly) linear rate on any smooth function.<n>The adaptive stepsize we propose arises from an intriguing decomposition theorem.
  arXiv  Detail & Related papers  (2024-09-29T21:27:00Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization [55.115992622028685]
  Previous work suggests that first-order methods would need to trade-off convergence rate (gradient convergence rate) for better. We demonstrate that both optimal complexity and near-optimal convergence guarantees can be achieved for smooth convex minimization and smooth convex-concave minimax problems.
  arXiv  Detail & Related papers  (2023-10-26T19:56:52Z)
• The Novel Adaptive Fractional Order Gradient Decent Algorithms Design via Robust Control [5.5491171448159715]
  The vanilla fractional order descent may oscillatively converge to a region around the global minimum instead of converging to the exact minimum point, or even diverge, in the case where the objective function is strongly convex. To address this problem, a novel adaptive fractional order descent (AFDOG) and a novel fractional descent (AFOAGD) method are proposed in this paper.
  arXiv  Detail & Related papers  (2023-03-08T02:03:30Z)
• Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration [30.369542816161378]
  We show that standard extragradient methods (i.e. mirror prox and dual extrapolation) recover optimal accelerated rates for first-order minimization of smooth convex functions. We generalize this framework to handle local and randomized notions of relative Lipschitzness.
  arXiv  Detail & Related papers  (2020-11-12T18:43:40Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  We study the problem of zero-order optimization of a strongly convex function. We consider a randomized approximation of the projected gradient descent algorithm. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
  arXiv  Detail & Related papers  (2020-06-14T10:42:23Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  Adaptive algorithms perform gradient updates using the history of gradients and are ubiquitous in training deep neural networks. In this paper we analyze a variant of OptimisticOA algorithm for nonconcave minmax problems. Our experiments show that adaptive GAN non-adaptive gradient algorithms can be observed empirically.
  arXiv  Detail & Related papers  (2019-12-26T22:10:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.