The recently proposed stochastic Polyak stepsize (SPS) and stochastic linesearch (SLS) for SGD have shown remarkable effectiveness when training overparameterized models. However, two issues remain unsolved in this line of work. First, in non-interpolation settings, both algorithms only guarantee convergence to a neighborhood of a solution which may result in a worse output than the initial guess. While artificially decreasing the adaptive stepsize has been proposed to address this issue (Orv...
