AccSPS Learning Rate: Accelerated Convergence Through Decision-Adjusted Levels for Stochastic Polyak Stepsize

Recently, the application of stochastic gradient descent (SGD) with Polyak stepsizes has gained attention and exhibited promising performance for machine learning problems. However, when the interpolation condition (where each loss attains a minimum at a globally optimal solution) is not satisfied, SGD with Polyak stepsizes encounters a primary limitation that impedes its overall effectiveness: a lack of knowledge of the optimal loss. In this study, we introduce a non-diminishing accelerated stochastic Polyak stepsize (AccSPS) with level adjustment coupled with approximate variance-reduced gradient (AVRG) descent to overcome this limitation. Our approach incorporates a decision-based level adjustment method to obtain an accurate estimation of the optimal loss. To significantly reduce memory requirements, we adopt a variance-reduced method that keeps a snapshot of average gradients after specific iterations. Theoretical analyses establish the convergence rate to the exact minimum in the non-interpolated setting. Numerical studies demonstrate the superior performance of AccSPS, showcasing a significantly lower loss when compared to state-of-the-art algorithms like DecSPS, AdaGrad, Adam, and AMSGrad, up to several orders of magnitude.