🔢 mathematics

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

This paper introduces Local LMO, a projection-free optimization method that replaces the global linear minimization oracle of Frank-Wolfe with a local one to achieve convergence rates comparable to Projected Gradient Descent—including linear rates for strongly convex functions and guarantees for unbounded sets—without relying on traditional curvature assumptions.

Original authors: Peter Richtárik, Kaja Gruntkowska, Hanmin Li

Published 2026-05-12

📖 6 min read🧠 Deep dive

CC0 1.0

Original authors: Peter Richtárik, Kaja Gruntkowska, Hanmin Li

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Navigating a Maze

Imagine you are trying to find the lowest point in a vast, foggy landscape (this is your objective function, or the thing you want to minimize, like a cost or error). However, you are not free to walk anywhere; you are confined to a specific path or room (this is your constraint set).

In the world of optimization, there are two main ways people usually try to find that lowest point:

The "Bouncer" Method (Projected Gradient Descent): You take a step downhill. If you accidentally step outside the allowed room, a bouncer immediately grabs you and throws you back to the nearest point on the wall. This works great if the room has simple walls (like a box), but if the room is a complex, twisted shape, the bouncer has to do a lot of heavy lifting to calculate exactly where to throw you. This "throwing" (projection) can be very slow and expensive.
The "Compass" Method (Frank-Wolfe): You don't have a bouncer. Instead, you have a compass that points to the best direction within the room. You look at the whole room, find the point that looks best in that direction, and walk toward it. This is fast because it's easy to find the "best point" in a room. However, because you are always walking toward the edge of the room, you tend to zig-zag and move very slowly, especially if the room is huge.

The New Idea: "Local LMO"

The authors of this paper propose a third way, called Local LMO. They call it a "Local Linear Minimization Oracle."

Think of it like this: Instead of looking at the entire room to find the best direction (which is slow and zig-zaggy), or getting thrown back by a bouncer every time you step out (which is expensive), you only look at a small circle around your current feet.

The Local View: You draw a small circle around where you are standing.
The Local Search: You ask, "Within this small circle, and staying inside the room, which direction goes downhill the fastest?"
The Step: You take a step in that direction, exactly the size of the circle's radius.

Why is this a big deal?

The paper claims that this simple change fixes the biggest problems of the other two methods:

It's faster than the "Compass" method: Because you only look at a small neighborhood, you don't get stuck zig-zagging along the edges of the room. You can move straight toward the bottom. In fact, the paper proves that if the landscape is "strongly convex" (like a perfect bowl), this method finds the bottom just as fast as the "Bouncer" method, but without needing the expensive "throwing" step.
It works in bigger rooms: The "Compass" method gets slower if the room is huge (its speed depends on the size of the room). The "Local LMO" method doesn't care how big the room is; it only cares about how far you are from the goal.
It handles tricky shapes: It works even if the room has no "curvature" (it's flat or weirdly shaped), a situation where the "Compass" method often fails to converge at all.

The "Magic" Radius

The secret sauce of this method is the size of the circle (the radius).

If the circle is too small, you take tiny, slow steps.
If the circle is too big, you might step outside the room or miss the best direction.

The authors provide mathematical formulas to calculate the perfect size for this circle at every step. Interestingly, they show that if you choose the radius correctly, this method is actually just a fancy version of Gradient Descent (the standard way to walk downhill) that happens to respect the walls of the room without needing a bouncer.

A Simple Analogy: The Hiker in a Forest

Imagine you are a hiker trying to find the bottom of a valley, but you are surrounded by a dense forest (the constraint).

Projected Gradient Descent: You walk downhill. If you hit a tree, you have to stop, calculate the exact angle to walk around it, and then continue. This calculation takes time.
Frank-Wolfe: You stand still, look at the entire forest, find the tree that is furthest downhill, and walk toward it. You might walk a long way, but you often end up walking in circles around the edge of the forest.
Local LMO: You only look at the trees within 5 feet of you. You find the best path among those trees, take a step, and repeat. Because you are only looking locally, you don't get confused by the whole forest, and you don't have to do complex calculations to avoid every single tree in the distance. You just keep moving efficiently toward the valley floor.

What the Paper Proves

The authors didn't just guess this would work; they did the math to prove:

It converges: It is guaranteed to reach the bottom.
It's fast: It reaches the bottom at the same speed as the best existing methods for smooth, bowl-shaped problems.
It's flexible: It works for problems where the "Compass" method fails (like when the room is infinite or the shape is weird).
It's robust: Even if the landscape isn't perfectly smooth or if you only have noisy information (stochastic settings), it still works.

The Catch

The paper admits that calculating the "perfect" circle size requires knowing some things you usually don't know in real life (like exactly how far you are from the bottom). However, they show that even if you use a smart guess (a geometric schedule) instead of the perfect formula, the method still works incredibly well in practice.

In summary: Local LMO is a new way to solve constrained optimization problems that combines the speed of "looking locally" with the efficiency of "walking downhill," avoiding the heavy lifting of projections and the slowness of global searches.

Technical Summary: Local LMO – Constrained Gradient Optimization via a Local Linear Minimization Oracle

1. Problem Formulation

The paper addresses the constrained optimization problem:
$\min_{x \in X} f(x)$
where $X \subseteq \mathbb{R}^d$ is a nonempty, closed, and convex constraint set, and $f: \mathbb{R}^d \to \mathbb{R}$ is a differentiable objective function. The goal is to minimize $f$ subject to $X$ , a formulation central to machine learning, statistics, and signal processing where constraints encode prior structure, regularization, or physical feasibility.

The authors position their work within the landscape of constrained optimization methods, which are typically categorized by the oracle used to access $X$ :

Projection Oracles: Used by Projected Gradient Descent (PGD), requiring computation of $\text{Proj}_X(x)$ . While PGD offers optimal convergence rates independent of the geometry of $X$ (e.g., its diameter), projections can be computationally expensive or intractable for complex sets.
Linear Minimization Oracles (LMO): Used by Frank–Wolfe (FW) and variants, solving $\text{LMO}_X(g) = \arg\min_{z \in X} \langle g, z \rangle$ . These avoid projections but often suffer from slower convergence rates that depend on the diameter of $X$ and require curvature assumptions. They may also fail to converge for non-smooth functions or in regimes where gradients are bounded but the FW curvature constant is infinite.
Separation Oracles: Used by ellipsoid and cutting-plane methods.

2. Methodology: Local LMO

The paper proposes Local LMO, a new projection-free gradient-type method. The core algorithmic idea is to replace the global linear minimization oracle used in FW with a local linear minimization oracle restricted to the intersection of the constraint set $X$ and a "small" ball centered at the current iterate $x_k$ .

The iteration is defined as:
$x_{k+1} \in \arg\min_{z \in X \cap B(x_k, t_k)} \langle \nabla f(x_k), z \rangle$
where $B(x_k, t_k) = \{y \in \mathbb{R}^d : \|y - x_k\| \le t_k\}$ and $t_k > 0$ is a suitably chosen radius (effective stepsize).

Key Conceptual Shift

The authors argue that Local LMO should be viewed not merely as a modification of FW, but as a generalization of Gradient Descent (GD) to the constrained setting.

Unconstrained Case: If $X = \mathbb{R}^d$ , the method reduces to GD with a normalized step direction: $x_{k+1} = x_k - \gamma_k \nabla f(x_k)$ , where $\gamma_k = t_k / \|\nabla f(x_k)\|$ .
Affine Subspace Case: If $X$ is an affine subspace, it reduces to GD restricted to that subspace.
Geometric Interpretation: The method is interpreted as a "forward–backward" scheme where the standard proximal backward step (quadratic penalty) is replaced by a "broximal" backward step (hard trust-region constraint).

3. Key Contributions

A. A New Projection-Free Framework

The authors introduce the Local LMO framework, which fundamentally alters the theoretical behavior of LMO-based methods. By restricting the search to a local trust region $X \cap B(x_k, t_k)$ , the method bridges the gap between projection-free optimization and GD. Unlike previous "local linear optimization oracle" (LLOO) literature which frames such methods as improved FW variants, this work derives from a geometric perspective rooted in trust-region linearization.

B. GD-Type Guarantees Without Global Geometric Dependence

The primary theoretical contribution is proving that Local LMO transfers the known convergence rates of PGD to the projection-free world in several regimes, without requiring the constraint set $X$ to be bounded or depending on global geometric quantities like the diameter of $X$ ( $\text{diam } X$ ) or FW-style curvature constants.

Specifically, the paper establishes:

Smooth Convex Regime: An $O(1/K)$ rate for the gradient difference $\min_{0 \le k < K} \|\nabla f(x_k) - \nabla f(x^\star)\|^2$ , matching PGD.
Strongly Convex Regime: A linear convergence rate for the distance to the solution $\|x_k - x^\star\|^2 \le \rho^{2k} \|x_0 - x^\star\|^2$ , where the contraction factor matches the optimal PGD rate. This contrasts with FW, which generally does not admit linear convergence without special assumptions on the solution's location or the set's geometry.
Bounded Gradient Regime: An $O(1/\sqrt{K})$ rate for convex functions with bounded gradients. The authors note that FW is not known to converge in this regime (as the FW curvature constant may be infinite even with bounded gradients), whereas Local LMO provides a standard sublinear rate.
Extensions: The theory extends to $(L_0, L_1)$ -smooth convex functions, smooth non-convex functions (convergence to stationary points), and stochastic settings.

C. Theoretical Analysis of the Oracle

The paper analyzes the computational implications of the local oracle. While solving the local subproblem over $X \cap B(x_k, t_k)$ can be more complex than the global LMO, the authors demonstrate that for many structured sets (e.g., affine subspaces, balls, polytopes), the local minimization admits closed-form solutions or efficient implementations.

4. Results and Experiments

Theoretical Results

The paper provides rigorous convergence guarantees across multiple regimes (summarized in Table 1 of the paper):

Smooth Strongly Convex: Linear convergence with a rate dependent on the condition number of the problem restricted to the constraint set, not the ambient space.
Smooth Convex: Sublinear convergence of the gradient difference.
Non-Convex: Convergence to first-order stationary points measured by the projected gradient mapping.
Stochastic: Convergence rates for finite-sum objectives with bounded gradients.

Experimental Validation

The authors conduct experiments on a 2D strongly convex quadratic problem with box constraints to isolate algorithmic behavior:

Comparison with PGD and FW: Local LMO exhibits linear convergence, significantly outperforming FW (which shows zig-zagging behavior) and approaching the performance of PGD (which is fastest due to cheap projections).
Radius Schedules: The experiments compare the theoretically prescribed adaptive radius (dependent on the unknown distance to the optimum) with geometric decay schedules ( $t_k = c q^k$ ). Results show that a well-tuned geometric schedule can nearly match the adaptive rule, suggesting practical viability even without knowledge of the optimal solution distance.

5. Significance and Claims

The paper positions Local LMO as a foundational step for a new class of projection-free gradient-type methods. Its significance lies in:

Overcoming FW Limitations: It resolves the dependency on the diameter of $X$ and the need for curvature assumptions that plague FW theory, allowing for linear convergence in regimes where FW fails or is slow.
Unifying Perspective: It reframes projection-free optimization not as a distinct alternative to GD, but as a natural generalization of GD using local linearization and hard constraints.
Practical Relevance: The method offers a "middle ground" between the high cost of projections (PGD) and the slow convergence of global linear oracles (FW), particularly in settings where projections are intractable but local linear minimization is feasible.

The authors acknowledge that the theoretical radius rules often depend on unknown quantities (like $x^\star$ or $f(x^\star)$ ), and while heuristic schedules (like geometric decay) show promise in experiments, further work is needed to develop fully implementable, parameter-free variants. They also suggest potential connections to modern LMO-based deep learning optimizers (e.g., Muon, Scion), though this remains a preliminary observation for future investigation.