  In machine learning applications, it is well known that carefully designed
learning rate (step size) schedules can significantly improve the convergence
of commonly used first-order optimization algorithms. Therefore how to set step
size adaptively becomes an important research question. A popular and effective
method is the Polyak step size, which sets step size adaptively for gradient
descent or stochastic gradient descent without the need to estimate the
smoothness parameter of the objective function. However, there has not been a
principled way to generalize the Polyak step size for algorithms with momentum
accelerations. This paper presents a general framework to set the learning rate
adaptively for first-order optimization methods with momentum, motivated by the
derivation of Polyak step size. It is shown that the resulting techniques are
much less sensitive to the choice of momentum parameter and may avoid the
oscillation of the heavy-ball method on ill-conditioned problems. These
adaptive step sizes are further extended to the stochastic settings, which are
attractive choices for stochastic gradient descent with momentum. Our methods
are demonstrated to be more effective for stochastic gradient methods than
prior adaptive step size algorithms in large-scale machine learning tasks.
