Local LMO is Secretly a Projection Method!
Abstract
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 ϑ-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 𝒪(K−(1+ϑ)/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 (|∇ f(x⋆)| = 0), and the rate 𝒪(K−1/(2−ϑ)) otherwise.
Related
- A potential projection method for the nonlinear Schrödinger equation with low regularity potential
- Existence and Uniqueness Proof for the Transport Equation and the Orthogonal Dynamics Equation for Zwanzig's Projection on Gaussian Spaces: A Vanishing Viscosity Method
- Quantum non-local games: Quantum relations, projection lattices and rule operators
- A Local Discontinuous Galerkin method for the modified Camassa--Holm equation
- On Landau's "local method" for obtaining zero-free regions
BibTeX
@misc{richtarik2026local,
title = {{Local LMO is Secretly a Projection Method!}},
author = {Peter Richtárik and Ammar Mahran},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33383},
eprint = {2609.33383},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33383},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Local LMO is Secretly a Projection Method!
AU - Peter Richtárik
AU - Ammar Mahran
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33383
UR - https://arxiv.org/abs/2609.33383
AB - 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 ϑ-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 𝒪(K^−(1+ϑ)/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 (|∇ f(x_⋆)| = 0), and the rate 𝒪(K^−1/(2−ϑ)) otherwise.
ER -