  Performance of optimization on quadratic problems sensitively depends on the
low-lying part of the spectrum. For large (effectively infinite-dimensional)
problems, this part of the spectrum can often be naturally represented or
approximated by power law distributions, resulting in power law convergence
rates for iterative solutions of these problems by gradient-based algorithms.
In this paper, we propose a new spectral condition providing tighter upper
bounds for problems with power law optimization trajectories. We use this
condition to build a complete picture of upper and lower bounds for a wide
range of optimization algorithms -- Gradient Descent, Steepest Descent, Heavy
Ball, and Conjugate Gradients -- with an emphasis on the underlying schedules
of learning rate and momentum. In particular, we demonstrate how an optimally
accelerated method, its schedule, and convergence upper bound can be obtained
in a unified manner for a given shape of the spectrum. Also, we provide first
proofs of tight lower bounds for convergence rates of Steepest Descent and
Conjugate Gradients under spectral power laws with general exponents. Our
experiments show that the obtained convergence bounds and acceleration
strategies are not only relevant for exactly quadratic optimization problems,
but also fairly accurate when applied to the training of neural networks.

Optimization and Control;Machine Learning;Neural and Evolutionary Computing