Local Quadratic Convergence of Stochastic Gradient Descent with Adaptive Step Size

2021/12/30 by Adityanarayanan Radhakrishnan, Mikhail Belkin, Radhakrishnan, Adityanarayanan +3
Computer Science · Engineering · Mathematics · #Machine Learning and ELM #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.LG #math.OC

paper · pdf · doi:10.48550/arxiv.2112.14872

ICML 2021 Workshop on Beyond first-order methods in ML systems

arxiv created 2021/12/30 · arxiv updated 2022/01/03

Abstract

Establishing a fast rate of convergence for optimization methods is crucial to their applicability in practice. With the increasing popularity of deep learning over the past decade, stochastic gradient descent and its adaptive variants (e.g. Adagrad, Adam, etc.) have become prominent methods of choice for machine learning practitioners. While a large number of works have demonstrated that these first order optimization methods can achieve sub-linear or linear convergence, we establish local quadratic convergence for stochastic gradient descent with adaptive step size for problems such as matrix inversion.

Related

• Adaptive Learning Rates for Faster Stochastic Gradient Methods
• Stochastic Adaptive Gradient Descent Without Descent
• Adaptive Step Sizes for Preconditioned Stochastic Gradient Descent
• On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes
• Optimal Adaptive and Accelerated Stochastic Gradient Descent