Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle

• URL: http://arxiv.org/abs/2605.08850v1
• Date: Sat, 09 May 2026 10:03:24 GMT
• Title: Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle
• Abstract summary: Local L is a new projection-free type for constrained optimization.<n>Local LMO is perhaps best viewed as an oracle of Gradient Descent (GD)
• Score: 51.714334316332476
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We design Local LMO - a new projection-free gradient-type method for constrained optimization. The key algorithmic idea is to replace the global linear minimization oracle over the constraint set used by Frank-Wolfe (FW) with a local linear minimization oracle over the intersection of the constraint set and a "small" ball centered at the current iterate. In particular, when minimizing $f:\mathbb{R}^d\to \mathbb{R}$ over a constraint $\emptyset\neq\mathcal{X}\subseteq\mathbb{R}^d$, Local LMO performs the iteration \[x_{k+1}\in \arg\min_{z\in\mathcal{X}\cap\mathcal{B}(x_{k},t_k)}\langle\nabla f(x_{k}), z \rangle,\] where $x_0\in\mathcal{X}$, and $t_k>0$ is a suitably chosen radius which can be interpreted as an effective stepsize. While designed as an alternative to FW, Local LMO is perhaps best viewed as a generalization of Gradient Descent (GD) rather than a modification of FW. Indeed, it is easy to see that Local LMO reduces to GD in the unconstrained setting and, more generally, to GD restricted to an affine subspace if the constraint $\mathcal{X}$ is affine. We prove that this simple algorithmic scheme transfers the known (unaccelerated) convergence rates of Projected Gradient Descent (PGD) to the projection-free world in several important regimes, some of which are beyond the reach of FW. In contrast to FW theory, i) our guarantees hold without requiring the feasible set $\mathcal{X}$ to be bounded, ii) our theory does not require the "curvature" assumption, which allows us to establish a standard sublinear rate for convex functions with bounded gradients, iii) we obtain a linear rate in the smooth strongly convex regime. Furthermore, we obtain sharp sublinear rates in the smooth convex and non-convex regimes, in the $(L_0,L_1)$-smooth convex regime, and in stochastic and non-differentiable settings.

Related papers

• Towards Scalable Persistence-Based Topological Optimization [44.16669776030478]
  Persistence-based topological optimization deforms a point cloud $X subset mathbbRd$ by minimizing objectives of the form $L(X) = ell(mathrmDgm(X))$, where $mathrmDgm(X)$ is a persistence diagram.<n>In practice, optimization is limited by two coupled issues: persistent homology is typically computed on subsamples, and the resulting topological gradients are highly sparse, with only a few anchor points receiving nonzero updates.
  arXiv  Detail & Related papers  (2026-05-09T15:47:20Z)
• Group Orthogonalized Policy Optimization:Group Policy Optimization as Orthogonal Projection in Hilbert Space [0.0]
  We present a new alignment algorithm for large language models derived from the geometry of Hilbert function spaces.<n>GOPO lifts alignment into the Hilbert space L2(pi_k) of square-integrable functions.<n>Because group-normalized advantages sum to zero, the Lagrange multiplier enforcing probability conservation vanishes exactly.
  arXiv  Detail & Related papers  (2026-02-24T12:59:32Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  We provide a unified analysis of two-timescale gradient ascent (TTGDA) for solving structured non minimax optimization problems.<n>Our contribution is to design TTGDA algorithms are effective beyond the setting.
  arXiv  Detail & Related papers  (2024-08-21T20:14:54Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
  This paper presents a subgradient-based algorithm for constrained nonsmooth convex computation. Our proposed algorithm can handle nonsmooth problems with general convex functional inequality constraints. Similar performance is observed when deterministic subgradients are replaced with subgradients.
  arXiv  Detail & Related papers  (2023-11-18T23:06:33Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
  Subgradient method is one of the most fundamental algorithmic schemes for nonsmooth optimization. In this work, we first extend the typical iteration complexity results for the subgradient method to cover non-Lipschitz convex and weakly convex minimization.
  arXiv  Detail & Related papers  (2023-05-23T15:26:36Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Provably Efficient Model-Free Constrained RL with Linear Function Approximation [4.060731229044571]
  We develop the first model-free, simulator-free algorithm that achieves a sublinear regret and a sublinear constraint violation even in large-scale systems. Our results are achieved via novel adaptations of the standard LSVI-UCB algorithms.
  arXiv  Detail & Related papers  (2022-06-23T17:54:31Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  We consider the problem of finding a saddle point for the convex-concave objective $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, where $f$ is a convex function with locally Lipschitz gradient and $g$ is convex and possibly non-smooth. We propose an adaptive version of the Condat-Vu algorithm, which alternates between primal gradient steps and dual steps.
  arXiv  Detail & Related papers  (2021-10-28T14:19:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.