Non-Uniform Smoothness for Gradient Descent
Preprint
Abstract
The analysis of gradient descent-type methods typically relies on the Lipschitz continuity of the objective gradient. This generally requires an expensive hyperparameter tuning process to appropriately calibrate a stepsize for a given problem. In this work we introduce a local first-order smoothness oracle (LFSO) which generalizes the Lipschitz continuous gradients smoothness condition and is applicable to any twice-differentiable function. We show that this oracle can encode all relevant problem information for tuning stepsizes for a suitably modified gradient descent method and give global and local convergence results. We also show that LFSOs in this modified first-order method can yield global linear convergence rates for non-strongly convex problems with extremely flat minima, and thus improve over the lower bound on rates achievable by general (accelerated) first-order methods.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Trust Region Methods for Nonconvex Stochastic Optimization beyond Lipschitz SmoothnessProceedings of the AAAI Conference on Artificial Intelligence, 2024
- Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation and Perspectives2022
- First-order optimization algorithms via inertial systems with Hessian driven dampingMathematical Programming, 2020
- Optimization Methods for Large-Scale Machine LearningSIAM Review, 2018
- Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosityMathematical Programming, 2016
- Introductory Lectures on Convex Optimization2004
- Two-Point Step Size Gradient MethodsIMA Journal of Numerical Analysis, 1988