Polynomial Preconditioning for Gradient Methods
This work addresses optimization bottlenecks for researchers and practitioners in machine learning, offering an incremental improvement over existing preconditioning methods.
The paper tackles the problem of improving the condition number for first-order optimization methods in structured nonlinear convex optimization by introducing a new family of preconditioners based on symmetric polynomials, which provably cuts gaps between highest eigenvalues without explicit spectral knowledge, and numerical experiments confirm efficiency in machine learning problems.
We study first-order methods with preconditioning for solving structured nonlinear convex optimization problems. We propose a new family of preconditioners generated by symmetric polynomials. They provide first-order optimization methods with a provable improvement of the condition number, cutting the gaps between highest eigenvalues, without explicit knowledge of the actual spectrum. We give a stochastic interpretation of this preconditioning in terms of coordinate volume sampling and compare it with other classical approaches, including the Chebyshev polynomials. We show how to incorporate a polynomial preconditioning into the Gradient and Fast Gradient Methods and establish the corresponding global complexity bounds. Finally, we propose a simple adaptive search procedure that automatically chooses the best possible polynomial preconditioning for the Gradient Method, minimizing the objective along a low-dimensional Krylov subspace. Numerical experiments confirm the efficiency of our preconditioning strategies for solving various machine learning problems.