We propose a stochastic variant of the classical Polyak step-size (Polyak,
1987) commonly used in the subgradient method. Although computing the Polyak
step-size requires knowledge of the optimal function values, this information
is readily available for typical modern machine learning applications.
Consequently, the proposed stochastic Polyak step-size (SPS) is an attractive
choice for setting the learning rate for stochastic gradient descent (SGD). We
provide theoretical convergence guarantees for SGD equipped with SPS in
different settings, including strongly convex, convex and non-convex functions.
Furthermore, our analysis results in novel convergence guarantees for SGD with
a constant step-size. We show that SPS is particularly effective when training
over-parameterized models capable of interpolating the training data. In this
setting, we prove that SPS enables SGD to converge to the true solution at a
fast rate without requiring the knowledge of any problem-dependent constants or
additional computational overhead. We experimentally validate our theoretical
results via extensive experiments on synthetic and real datasets. We
demonstrate the strong performance of SGD with SPS compared to state-of-the-art
optimization methods when training over-parameterized models.

本文介绍了一种新颖的随机 Polyak 步长方法，称为 SPS，它可以有效地用于随机梯度下降，特别是在训练超参数化模型时表现良好，并且在不需要任何与问题相关的常数或额外计算开销的情况下收敛速度快，并且与其他优化方法相比表现出色。