Enhancing Stochastic Gradient Descent: A Unified Framework and Novel Acceleration Methods for Faster Convergence
This work addresses a fundamental bottleneck in stochastic optimization for machine learning practitioners by providing a framework to enhance convergence analysis and acceleration methods, though it appears incremental as it builds on existing SGD-based algorithms.
The authors tackled the challenge of analyzing convergence for first-order stochastic optimization methods under non-convex conditions by proposing a unified framework that interprets update directions as stochastic subgradients plus acceleration terms. They discovered two plug-and-play acceleration methods, Reject Accelerating and Random Vector Accelerating, and theoretically demonstrated that these methods improve convergence rates.
Based on SGD, previous works have proposed many algorithms that have improved convergence speed and generalization in stochastic optimization, such as SGDm, AdaGrad, Adam, etc. However, their convergence analysis under non-convex conditions is challenging. In this work, we propose a unified framework to address this issue. For any first-order methods, we interpret the updated direction $g_t$ as the sum of the stochastic subgradient $\nabla f_t(x_t)$ and an additional acceleration term $\frac{2|\langle v_t, \nabla f_t(x_t) \rangle|}{\|v_t\|_2^2} v_t$, thus we can discuss the convergence by analyzing $\langle v_t, \nabla f_t(x_t) \rangle$. Through our framework, we have discovered two plug-and-play acceleration methods: \textbf{Reject Accelerating} and \textbf{Random Vector Accelerating}, we theoretically demonstrate that these two methods can directly lead to an improvement in convergence rate.