Eigencurve: Optimal Learning Rate Schedule for SGD on Quadratic
  Objectives with Skewed Hessian Spectrums
  Learning rate schedulers have been widely adopted in training deep neural
networks. Despite their practical importance, there is a discrepancy between
its practice and its theoretical analysis. For instance, it is not known what
schedules of SGD achieve best convergence, even for simple problems such as
optimizing quadratic objectives. In this paper, we propose Eigencurve, the
first family of learning rate schedules that can achieve minimax optimal
convergence rates (up to a constant) for SGD on quadratic objectives when the
eigenvalue distribution of the underlying Hessian matrix is skewed. The
condition is quite common in practice. Experimental results show that
Eigencurve can significantly outperform step decay in image classification
tasks on CIFAR-10, especially when the number of epochs is small. Moreover, the
theory inspires two simple learning rate schedulers for practical applications
that can approximate eigencurve. For some problems, the optimal shape of the
proposed schedulers resembles that of cosine decay, which sheds light to the
success of cosine decay for such situations. For other situations, the proposed
schedulers are superior to cosine decay.
