Parametrized Accelerated Methods Free of Condition Number

Abstract

Analyses of accelerated (momentum-based) gradient descent usually assume bounded condition number to obtain exponential convergence rates. However, in many real problems, e.g., kernel methods or deep neural networks, the condition number, even locally, can be unbounded, unknown or mis-estimated. This poses problems in both implementing and analyzing accelerated algorithms. In this paper, we address this issue by proposing parametrized accelerated methods by considering the condition number as a free parameter. We provide spectral-level analysis for several important accelerated algorithms, obtain explicit expressions and improve worst case convergence rates. Moreover, we show that those algorithm converge exponentially even when the condition number is unknown or mis-estimated.

arXiv comment23 pages, 3 figures

References in corpus (4)

• DRAW: A Recurrent Neural Network For Image Generation
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A geometric alternative to Nesterov's accelerated gradient descent
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems

Cited by in corpus (4)

• Anderson Acceleration as a Krylov Method with Application to Asymptotic Convergence Analysis
• Rejuvenating AMLI-Cycle: From Chebyshev Polynomials to Momentum Acceleration
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network