  We propose a new stochastic gradient method called MOTAPS (Moving Targetted
Polyak Stepsize) that uses recorded past loss values to compute adaptive
stepsizes. MOTAPS can be seen as a variant of the Stochastic Polyak (SP) which
is also a method that also uses loss values to adjust the stepsize. The
downside to the SP method is that it only converges when the interpolation
condition holds. MOTAPS is an extension of SP that does not rely on the
interpolation condition. The MOTAPS method uses $n$ auxiliary variables, one
for each data point, that track the loss value for each data point. We provide
a global convergence theory for SP, an intermediary method TAPS, and MOTAPS by
showing that they all can be interpreted as a special variant of online SGD. We
also perform several numerical experiments on convex learning problems, and
deep learning models for image classification and language translation. In all
of our tasks we show that MOTAPS is competitive with the relevant baseline
method.
