Parametrized Accelerated Methods Free of Condition Number
This addresses a critical bottleneck for practitioners in machine learning, such as in kernel methods or deep neural networks, where condition numbers are often unbounded or mis-estimated, making it an incremental improvement over existing accelerated methods.
The paper tackles the problem of accelerated gradient descent methods failing when the condition number is unbounded or unknown, by proposing parametrized accelerated methods that treat the condition number as a free parameter, resulting in improved worst-case convergence rates and exponential convergence even with unknown condition numbers.
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.