mlsanityData to 14 Oct 2026

Local LMO is Secretly a Projection Method!

arXiv 2609.33383 ↗First posted 27 Sep 2026math.OC cs.LGcited by 0

Not on the map. Why?

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.

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

23 of 62 references.

References · 23

  1. 2021Convex optimizationcited by 2,515
  2. 2023Safe RLHF: Safe Reinforcement Learning from Human Feedbackcited by 656
  3. 2018Empirical Risk Minimization under Fairness Constraintscited by 226
  4. 2025Training Deep Learning Models with Norm-Constrained LMOscited by 192
  5. 2018Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goalscited by 103
  6. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 77
  7. 2019Revisiting the Polyak step sizecited by 55
  8. 2013The Complexity of Large-scale Convex Programming under a Linear Optimization Oraclecited by 29
  9. 2020Deep Neural Network Training with Frank-Wolfecited by 23
  10. 2021Complexity of Linear Minimization and Projection on Some Setscited by 20
  11. 2021Constrained Optimization to Train Neural Networks on Critical and Under-Represented Classescited by 19
  12. 2023A simple uniformly optimal method without line search for convex optimizationcited by 18
11 more
  1. 2013Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimizationcited by 14
  2. 2025New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Resultscited by 6
  3. 2023A Parameter-Free Conditional Gradient Method for Composite Minimization under H"older Conditioncited by 5
  4. 2025The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applicationscited by 5
  5. 2024Uniformly Optimal and Parameter-free First-order Methods for Convex and Function-constrained Optimizationcited by 4
  6. 2025Beyond Short Steps in Frank-Wolfe Algorithmscited by 4
  7. 2025Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimizationcited by 4
  8. 2025New Results on the Polyak Stepsize: Tight Convergence Analysis and Universal Function Classescited by 4
  9. 2025Polyak Stepsize: Estimating Optimal Functional Values Without Parameters or Prior Knowledgecited by 3
  10. 2023Polyak Minorant Method for Convex Optimizationcited by 2
  11. 2026A Linearly Convergent Projection-Free Algorithm for Smooth Convex Setscited by 2

Built on by

Not cited yet.