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.

提供了 Eigencurve，第一个可以在在底层 Hessian 矩阵的特征值分布呈倾斜分布时，为 SGD 优化二次目标达到了 minimax 最优收敛速率（最多提升一个常数），实现其近似的两个简单的学习速度计划，对于某些问题，其形状类似于余弦衰减的优化程序，对于其他情况，所提出的计划优于余弦衰减。

Eigencurve：具有偏斜黑塞谱的二次目标的 SGD 的最优学习速率表

Eigencurve: Optimal Learning Rate Schedule for SGD on Quadratic  Objectives with Skewed Hessian Spectrums

We study without-replacement SGD for solving finite-sum optimization
problems. Specifically, depending on how the indices of the finite-sum are
shuffled, we consider the RandomShuffle (shuffle at the beginning of each
epoch) and SingleShuffle (shuffle only once) algorithms. First, we establish
minimax optimal convergence rates of these algorithms up to poly-log factors.
Notably, our analysis is general enough to cover gradient dominated nonconvex
costs, and does not rely on the convexity of individual component functions
unlike existing optimal convergence results. Secondly, assuming convexity of
the individual components, we further sharpen the tight convergence results for
RandomShuffle by removing the drawbacks common to all prior arts: large number
of epochs required for the results to hold, and extra poly-log factor gaps to
the lower bound.

本文研究了无替换 SGD 算法在有限和优化问题上的应用及其两种不同的指标洗牌方式（RandomShuffle 和 SingleShuffle）。作者们建立了这些算法的最小二次理论下的优化收敛率。此外，作者们进一步应用了各自分量的凸性来缩小 RandomShuffle 的宽松收敛结果，并减少了所有先前艺术品中共有的缺点。