Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation

arXiv:2404.02378v1 Announce Type: cross
Abstract: We prove new convergence rates for a generalized version of stochastic Nesterov acceleration under interpolation conditions. Unlike previous analyses, our approach accelerates any stochastic gradient method which makes sufficient progress in expectation. The proof, which proceeds using the estimating sequences framework, applies to both convex and strongly convex functions and is easily specialized to accelerated SGD under the strong growth condition. In this special case, our analysis reduces the dependence on the strong growth constant …

abstract arxiv convergence cs.lg faster framework generalized gradient math.oc progress prove stochastic type