Metraipolis › archive › dc_bb70eace28eb

Multi-Step Performance Estimation for Gradient Descent under the Polyak Lojasiewicz Condition — arXiv:2611.06713

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.06713
License (as archived): CC0-1.0
Archived: 2026-11-05T18:27:29.813Z
SHA-256 of the archived text: 351836a45cc5abc94f92a168276bda8b4ea050c00f3c92b08193592e33166eac
Stable URL of this page: https://metraipolis.com/documento/dc_bb70eace28eb

How to cite

Multi-Step Performance Estimation for Gradient Descent under the Polyak Lojasiewicz Condition — arXiv:2611.06713 — arXiv (en), https://arxiv.org/abs/2611.06713 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bb70eace28eb (Metraipolis archive dc_bb70eace28eb, sha256 351836a45cc5abc94f92a168276bda8b4ea050c00f3c92b08193592e33166eac)

BibTeX

@misc{dcbb70eace28eb,
  title = {Multi-Step Performance Estimation for Gradient Descent under the Polyak Lojasiewicz Condition — arXiv:2611.06713},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.06713},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bb70eace28eb; sha256 351836a45cc5abc94f92a168276bda8b4ea050c00f3c92b08193592e33166eac},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06713. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\mu$-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\in(0,2/L)$. The solution exhibits three stepsize regimes. For $0<t\leq 1/L$ and $1/L<t\leq \sqrt{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 $\sqrt{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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2611.06713 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:17:34.247Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).