# Local LMO is Secretly a Projection Method!

arXiv: https://arxiv.org/abs/2609.33383 · HTML: https://mlsanity.com/paper/2609.33383/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 62 references that are in the map.
- First posted on arXiv 27 Sep 2026.

## Builds on (most cited first, 23 of 23)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Safe RLHF: Safe Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2310.12773/) (2023)
- [Empirical Risk Minimization under Fairness Constraints](https://mlsanity.com/paper/1802.08626/) (2018)
- [Training Deep Learning Models with Norm-Constrained LMOs](https://mlsanity.com/paper/2502.07529/) (2025)
- [Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals](https://mlsanity.com/paper/1809.04198/) (2018)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Revisiting the Polyak step size](https://mlsanity.com/paper/1905.00313/) (2019)
- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)
- [Deep Neural Network Training with Frank-Wolfe](https://mlsanity.com/paper/2010.07243/) (2020)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Constrained Optimization to Train Neural Networks on Critical and Under-Represented Classes](https://mlsanity.com/paper/2102.12894/) (2021)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization](https://mlsanity.com/paper/1309.5547/) (2013)
- [New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results](https://mlsanity.com/paper/2505.20219/) (2025)
- [A Parameter-Free Conditional Gradient Method for Composite Minimization under H"older Condition](https://mlsanity.com/paper/2305.18181/) (2023)
- [The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications](https://mlsanity.com/paper/2502.02002/) (2025)
- [Uniformly Optimal and Parameter-free First-order Methods for Convex and Function-constrained Optimization](https://mlsanity.com/paper/2412.06319/) (2024)
- [Beyond Short Steps in Frank-Wolfe Algorithms](https://mlsanity.com/paper/2501.18773/) (2025)
- [Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization](https://mlsanity.com/paper/2510.00823/) (2025)
- [New Results on the Polyak Stepsize: Tight Convergence Analysis and Universal Function Classes](https://mlsanity.com/paper/2512.06231/) (2025)
- [Polyak Stepsize: Estimating Optimal Functional Values Without Parameters or Prior Knowledge](https://mlsanity.com/paper/2508.17288/) (2025)
- [Polyak Minorant Method for Convex Optimization](https://mlsanity.com/paper/2310.07922/) (2023)
- [A Linearly Convergent Projection-Free Algorithm for Smooth Convex Sets](https://mlsanity.com/paper/2608.04321/) (2026)

## Abstract (arXiv)

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"older 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 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 O(K-1/(2-vartheta)) otherwise.