Optimal Local Convergence Rates of Stochastic First-Order Methods under Local Alpha-PL

摘要

We study the local oracle complexity of stochastic first-order methods under a local α–Polyak–Łojasiewicz (α–PŁ) condition in a neighborhood of a target connected component ℳ’ of the local minimizer set. The parameter α∈[1,2] is the exponent of the gradient norm in the α–PŁ inequality: α=2 recovers the classical PŁ case, α=1 corresponds to Hölder-type error bounds, and intermediate values interpolate between these regimes. Our performance criterion is the number of oracle queries required to output x̂ with F(x̂)-l≤ε, where l:=F(y) for any y∈ℳ’. We work in a local regime where the algorithm is initialized near ℳ’ and, with high probability, its iterates remain in that neighborhood. We establish a lower bound Ω(ε^-2/α) for all stochastic first-order methods in this regime, and we obtain a matching upper bound 𝒪(ε^-2/α) for 1≤α<2 via a SARAH-type variance-reduced method with time-varying batch sizes and step sizes. Thus, for 1≤α<2, the optimal dependence on ε is Θ(ε^-2/α). In the convex setting, assuming a local α–PŁ condition on the ε-sublevel set, we further show a complexity lower bound Ω(ε^-2/α) for reaching an ε-global optimum, matching the ε-dependence of known accelerated stochastic subgradient methods.