arXiv preprint ·
Local LMO is Secretly a Projection Method!
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $\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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Plug-and-Play Methods Provably Converge Even with Improperly Trained Denoisers: Convergence by Architectural Design
Online Stochastic Allocation with Increasing Returns
ILP-BO: Integer Linear Programming-Based Black-Box Optimization
Efficient Reasoning via Constrained Optimization in Latent Space
Convergence of Practical Muon
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.