A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
An Element-wise RSAV Algorithm for Unconstrained Optimization Problems
We present a novel optimization algorithm, element-wise relaxed scalar auxiliary variable (E-RSAV), that satisfies an unconditional energy dissipation law and exhibits improved alignment between the modified and the orig…
On the convergence rate of the three operator splitting scheme
The three operator splitting scheme was recently proposed by [Davis and Yin, 2015] as a method to optimize composite objective functions with one convex smooth term and two convex (possibly non-smooth) terms for which we…
Predictive Local Smoothness for Stochastic Gradient Methods
Stochastic gradient methods are dominant in nonconvex optimization especially for deep models but have low asymptotical convergence due to the fixed smoothness. To address this problem, we propose a simple yet effective …
A Short Information-Theoretic Analysis of Linear Auto-Regressive Learning
In this note, we give a short information-theoretic proof of the consistency of the Gaussian maximum likelihood estimator in linear auto-regressive models. Our proof yields nearly optimal non-asymptotic rates for paramet…
A Unified Algorithmic Framework for Distributed Adaptive Signal and Feature Fusion Problems -- Part II: Convergence Properties
This paper studies the convergence conditions and properties of the distributed adaptive signal fusion (DASF) algorithm, the framework itself having been introduced in a `Part I' companion paper. The DASF algorithm can b…