Metraipolis › archive › dc_4332fc30037d

Local LMO is Secretly a Projection Method! — arXiv:2609.33383

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.33383
License (as archived)
CC0-1.0
Archived
2026-10-07T22:39:59.865Z
SHA-256 of the archived text
d879647d9f85c5ee9c88c6a6e543fe7298d0529928bf9a4e8a9d32843d81c90c
Stable URL of this page
https://metraipolis.com/documento/dc_4332fc30037d

How to cite

Local LMO is Secretly a Projection Method! — arXiv:2609.33383 — arXiv (en), https://arxiv.org/abs/2609.33383 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4332fc30037d (Metraipolis archive dc_4332fc30037d, sha256 d879647d9f85c5ee9c88c6a6e543fe7298d0529928bf9a4e8a9d32843d81c90c)
BibTeX
@misc{dc4332fc30037d,
  title = {Local LMO is Secretly a Projection Method! — arXiv:2609.33383},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.33383},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4332fc30037d; sha256 d879647d9f85c5ee9c88c6a6e543fe7298d0529928bf9a4e8a9d32843d81c90c},
  year = {2026}
}

Archived text

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

The local linear minimization oracle (Ferris and Zavriev, 1996; arXiv:2605.08850 ), or Local LMO, solves constrained convex problems without having to compute a projection: it minimizes a linear model over the intersection of the feasible set with a ball around the current iterate. We show that, whenever the ball radius does not exceed the Polyak radius, the Local LMO step is the Euclidean projection of the current iterate onto the intersection of the feasible set with a half-space that separates the iterate from the solution set; this projection is nonetheless computable by a linear oracle alone. We demonstrate that Local LMO belongs to a broader family of projection methods which may be indexed by the depth of the localizing half-space. For objectives with $\vartheta$-Hölder continuous gradient, every method from this family whose half-space lies sufficiently deep drives the best of its first $K$ iterates to optimality at the universal rate $\mathcal{O}(K^{-(1+\vartheta)/2})$, matching the non-accelerated universal gradient method of Nesterov (2015). Run at the Polyak radius, Local LMO attains the same rate when the constrained optima are also unconstrained ($\|\nabla f(x_\star)\| = 0$), and the rate $\mathcal{O}(K^{-1/(2-\vartheta)})$ otherwise.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-29 in cs.LG).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.33383 — 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-10-07T22:14:28.713Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).