Multi-Step Performance Estimation for Gradient Descent under the Polyak Lojasiewicz Condition
Abstract
Gradient descent is a fundamental algorithm in machine learning and statistical inference. Performance estimation provides a systematic framework for obtaining sharp convergence bounds through semidefinite programming. We study the worst-case performance of constant-stepsize gradient descent over the class of L-smooth functions satisfying the μ-Polyak--Łojasiewicz (PŁ) inequality. We formulate the N-step objective-gap analysis as a semidefinite programming (SDP) relaxation based on pairwise smoothness constraints and pointwise PŁ inequalities. Since an exact interpolation condition for smooth PŁ functions is not currently available, the resulting SDP provides a valid upper bound on the true worst-case performance. We solve a reduced SDP retaining only consecutive-pair smoothness constraints analytically for every horizon N and every stepsize t∈(0,2/L). The solution exhibits three stepsize regimes. For 0<t≤ 1/L and 1/L<t≤ √3/L, the reduced and full pairwise SDPs have the same optimal value, and the one-step SDP contraction factor tensorizes to a geometric N-step rate. For √3/L<t<2/L, the reduced-SDP value is nongeometric in the horizon: an initial transient phase is followed by eventual geometric decay. The resulting asymptotic contraction factor is tight for the full pairwise SDP and strictly improves the bound obtained by recursively applying the one-step estimate. Explicit primal and dual feasible solutions certify the results, with numerical SDP experiments guiding their construction. Our results show that analyzing several iterations together can give a better convergence bound than repeatedly applying the sharp one-step SDP bound in the Regime III.
Related
- Convergence rate of stochastic gradient descent under Łojasiewicz type condition and polynomially controlled noise
- Online Covariance Estimation for Averaged Stochastic Gradient Descent on Riemannian Manifolds
- Last-Iterate Performance of Gradient Descent and Relaxed Proximal Point via s-Composability
- Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design
- Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent
BibTeX
@misc{hong2026multistep,
title = {{Multi-Step Performance Estimation for Gradient Descent under the Polyak Lojasiewicz Condition}},
author = {Wanli Hong and Shuyang Ling},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06713},
eprint = {2611.06713},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06713},
}
RIS
TY - UNPB
TI - Multi-Step Performance Estimation for Gradient Descent under the Polyak Lojasiewicz Condition
AU - Wanli Hong
AU - Shuyang Ling
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06713
UR - https://arxiv.org/abs/2611.06713
AB - Gradient descent is a fundamental algorithm in machine learning and statistical inference. Performance estimation provides a systematic framework for obtaining sharp convergence bounds through semidefinite programming. We study the worst-case performance of constant-stepsize gradient descent over the class of L-smooth functions satisfying the μ-Polyak--Łojasiewicz (PŁ) inequality. We formulate the N-step objective-gap analysis as a semidefinite programming (SDP) relaxation based on pairwise smoothness constraints and pointwise PŁ inequalities. Since an exact interpolation condition for smooth PŁ functions is not currently available, the resulting SDP provides a valid upper bound on the true worst-case performance. We solve a reduced SDP retaining only consecutive-pair smoothness constraints analytically for every horizon N and every stepsize t∈(0,2/L). The solution exhibits three stepsize regimes. For 0<t≤ 1/L and 1/L<t≤ √3/L, the reduced and full pairwise SDPs have the same optimal value, and the one-step SDP contraction factor tensorizes to a geometric N-step rate. For √3/L<t<2/L, the reduced-SDP value is nongeometric in the horizon: an initial transient phase is followed by eventual geometric decay. The resulting asymptotic contraction factor is tight for the full pairwise SDP and strictly improves the bound obtained by recursively applying the one-step estimate. Explicit primal and dual feasible solutions certify the results, with numerical SDP experiments guiding their construction. Our results show that analyzing several iterations together can give a better convergence bound than repeatedly applying the sharp one-step SDP bound in the Regime III.
ER -