PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates
This work addresses the need for robust and efficient optimization methods in machine learning, offering a scalable solution with strong theoretical guarantees, though it is incremental as it builds on existing algorithms like SVRG, SAGA, and Katyusha.
The paper tackles the problem of ill-conditioning and hyperparameter tuning in large-scale convex optimization for machine learning by introducing PROMISE, a suite of preconditioned stochastic gradient algorithms, which outperform or match tuned optimizers on 51 benchmark problems.
This paper introduces PROMISE ($\textbf{Pr}$econditioned Stochastic $\textbf{O}$ptimization $\textbf{M}$ethods by $\textbf{I}$ncorporating $\textbf{S}$calable Curvature $\textbf{E}$stimates), a suite of sketching-based preconditioned stochastic gradient algorithms for solving large-scale convex optimization problems arising in machine learning. PROMISE includes preconditioned versions of SVRG, SAGA, and Katyusha; each algorithm comes with a strong theoretical analysis and effective default hyperparameter values. In contrast, traditional stochastic gradient methods require careful hyperparameter tuning to succeed, and degrade in the presence of ill-conditioning, a ubiquitous phenomenon in machine learning. Empirically, we verify the superiority of the proposed algorithms by showing that, using default hyperparameter values, they outperform or match popular tuned stochastic gradient optimizers on a test bed of $51$ ridge and logistic regression problems assembled from benchmark machine learning repositories. On the theoretical side, this paper introduces the notion of quadratic regularity in order to establish linear convergence of all proposed methods even when the preconditioner is updated infrequently. The speed of linear convergence is determined by the quadratic regularity ratio, which often provides a tighter bound on the convergence rate compared to the condition number, both in theory and in practice, and explains the fast global linear convergence of the proposed methods.