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

Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, Patrick Thiran
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3007-3015, 2026.

Abstract

We study the local oracle complexity of stochastic first-order methods under a local $\alpha$–Polyak–{Ł}ojasiewicz ($\alpha$–P{Ł}) condition in a neighborhood of a target connected component $\mathcal M’$ of the local minimizer set. The parameter $\alpha\in[1,2]$ is the exponent of the gradient norm in the $\alpha$–P{Ł} inequality: $\alpha=2$ recovers the classical P{Ł} case, $\alpha=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 $\hat x$ with $F(\hat x)-l\le\varepsilon$, where $l:=F(y)$ for any $y\in\mathcal M’$. We work in a local regime where the algorithm is initialized near $\mathcal M’$ and, with high probability, its iterates remain in that neighborhood. We establish a lower bound $\Omega(\varepsilon^{-2/\alpha})$ for all stochastic first-order methods in this regime, and we obtain a matching upper bound $\mathcal O(\varepsilon^{-2/\alpha})$ for $1\le \alpha<2$ via a SARAH-type variance-reduced method with time-varying batch sizes and step sizes. Thus, for $1\le\alpha<2$, the optimal dependence on $\varepsilon$ is $\Theta(\varepsilon^{-2/\alpha})$. In the convex setting, assuming a local $\alpha$–P{Ł} condition on the $\varepsilon$-sublevel set, we further show a complexity lower bound $\widetilde{\Omega}(\varepsilon^{-2/\alpha})$ for reaching an $\varepsilon$-global optimum, matching the $\varepsilon$-dependence of known accelerated stochastic subgradient methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-masiha26a, title = { Optimal Local Convergence Rates of Stochastic First-Order Methods under Local Alpha-PL }, author = {Masiha, Saeed and Salehkaleybar, Saber and He, Niao and Kiyavash, Negar and Thiran, Patrick}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3007--3015}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/masiha26a/masiha26a.pdf}, url = {https://proceedings.mlr.press/v300/masiha26a.html}, abstract = { We study the local oracle complexity of stochastic first-order methods under a local $\alpha$–Polyak–{Ł}ojasiewicz ($\alpha$–P{Ł}) condition in a neighborhood of a target connected component $\mathcal M’$ of the local minimizer set. The parameter $\alpha\in[1,2]$ is the exponent of the gradient norm in the $\alpha$–P{Ł} inequality: $\alpha=2$ recovers the classical P{Ł} case, $\alpha=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 $\hat x$ with $F(\hat x)-l\le\varepsilon$, where $l:=F(y)$ for any $y\in\mathcal M’$. We work in a local regime where the algorithm is initialized near $\mathcal M’$ and, with high probability, its iterates remain in that neighborhood. We establish a lower bound $\Omega(\varepsilon^{-2/\alpha})$ for all stochastic first-order methods in this regime, and we obtain a matching upper bound $\mathcal O(\varepsilon^{-2/\alpha})$ for $1\le \alpha<2$ via a SARAH-type variance-reduced method with time-varying batch sizes and step sizes. Thus, for $1\le\alpha<2$, the optimal dependence on $\varepsilon$ is $\Theta(\varepsilon^{-2/\alpha})$. In the convex setting, assuming a local $\alpha$–P{Ł} condition on the $\varepsilon$-sublevel set, we further show a complexity lower bound $\widetilde{\Omega}(\varepsilon^{-2/\alpha})$ for reaching an $\varepsilon$-global optimum, matching the $\varepsilon$-dependence of known accelerated stochastic subgradient methods. } }
Endnote
%0 Conference Paper %T Optimal Local Convergence Rates of Stochastic First-Order Methods under Local Alpha-PL %A Saeed Masiha %A Saber Salehkaleybar %A Niao He %A Negar Kiyavash %A Patrick Thiran %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-masiha26a %I PMLR %P 3007--3015 %U https://proceedings.mlr.press/v300/masiha26a.html %V 300 %X We study the local oracle complexity of stochastic first-order methods under a local $\alpha$–Polyak–{Ł}ojasiewicz ($\alpha$–P{Ł}) condition in a neighborhood of a target connected component $\mathcal M’$ of the local minimizer set. The parameter $\alpha\in[1,2]$ is the exponent of the gradient norm in the $\alpha$–P{Ł} inequality: $\alpha=2$ recovers the classical P{Ł} case, $\alpha=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 $\hat x$ with $F(\hat x)-l\le\varepsilon$, where $l:=F(y)$ for any $y\in\mathcal M’$. We work in a local regime where the algorithm is initialized near $\mathcal M’$ and, with high probability, its iterates remain in that neighborhood. We establish a lower bound $\Omega(\varepsilon^{-2/\alpha})$ for all stochastic first-order methods in this regime, and we obtain a matching upper bound $\mathcal O(\varepsilon^{-2/\alpha})$ for $1\le \alpha<2$ via a SARAH-type variance-reduced method with time-varying batch sizes and step sizes. Thus, for $1\le\alpha<2$, the optimal dependence on $\varepsilon$ is $\Theta(\varepsilon^{-2/\alpha})$. In the convex setting, assuming a local $\alpha$–P{Ł} condition on the $\varepsilon$-sublevel set, we further show a complexity lower bound $\widetilde{\Omega}(\varepsilon^{-2/\alpha})$ for reaching an $\varepsilon$-global optimum, matching the $\varepsilon$-dependence of known accelerated stochastic subgradient methods.
APA
Masiha, S., Salehkaleybar, S., He, N., Kiyavash, N. & Thiran, P.. (2026). Optimal Local Convergence Rates of Stochastic First-Order Methods under Local Alpha-PL . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3007-3015 Available from https://proceedings.mlr.press/v300/masiha26a.html.

Related Material