  Recently, Loizou et al. (2021), proposed and analyzed stochastic gradient
descent (SGD) with stochastic Polyak stepsize (SPS). The proposed SPS comes
with strong convergence guarantees and competitive performance; however, it has
two main drawbacks when it is used in non-over-parameterized regimes: (i) It
requires a priori knowledge of the optimal mini-batch losses, which are not
available when the interpolation condition is not satisfied (e.g., regularized
objectives), and (ii) it guarantees convergence only to a neighborhood of the
solution. In this work, we study the dynamics and the convergence properties of
SGD equipped with new variants of the stochastic Polyak stepsize and provide
solutions to both drawbacks of the original SPS. We first show that a simple
modification of the original SPS that uses lower bounds instead of the optimal
function values can directly solve issue (i). On the other hand, solving issue
(ii) turns out to be more challenging and leads us to valuable insights into
the method's behavior. We show that if interpolation is not satisfied, the
correlation between SPS and stochastic gradients introduces a bias, which
effectively distorts the expectation of the gradient signal near minimizers,
leading to non-convergence - even if the stepsize is scaled down during
training. To fix this issue, we propose DecSPS, a novel modification of SPS,
which guarantees convergence to the exact minimizer - without a priori
knowledge of the problem parameters. For strongly-convex optimization problems,
DecSPS is the first stochastic adaptive optimization method that converges to
the exact solution without restrictive assumptions like bounded
iterates/gradients.
