Faster SGD Using Sketched Conditioning
This work addresses the need for faster optimization in machine learning, particularly for deep neural networks, though it appears incremental as it builds on existing conditioning methods.
The authors tackled the problem of accelerating stochastic optimization by proposing a novel method that uses sketching to construct a cheap conditioner, achieving a significant speedup over Stochastic Gradient Descent (SGD).
We propose a novel method for speeding up stochastic optimization algorithms via sketching methods, which recently became a powerful tool for accelerating algorithms for numerical linear algebra. We revisit the method of conditioning for accelerating first-order methods and suggest the use of sketching methods for constructing a cheap conditioner that attains a significant speedup with respect to the Stochastic Gradient Descent (SGD) algorithm. While our theoretical guarantees assume convexity, we discuss the applicability of our method to deep neural networks, and experimentally demonstrate its merits.