Local LMO behaves like a projection method for convex problems
Local LMO is Secretly a Projection Method!
Machine Learning
Summary
Solving constrained optimization problems often requires complex computations like projections. The authors show that the Local Linear Minimization Oracle (Local LMO) method, which avoids explicit projections, actually acts like projecting the current guess onto a specific set defined by the problem constraints. This means Local LMO is part of a broader family of projection methods that can efficiently reach the optimal solution at known convergence rates. Their analysis provides guarantees on how fast these methods improve with more steps.
What this means in practice
- •For machine learning engineers: Optimize constrained models efficiently without explicit projection operations using Local LMO or related projection methods.
- •For operations research teams: Solve convex constrained optimization tasks faster by applying Local LMO as a projection step implemented with linear oracles.
Authors
Peter Richtárik, Ammar Mahran
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.