  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.
