PaperlayerView exact revision on arXiv

Source-linked AI summary

Local LMO is Secretly a Projection Method!

Peter Richtárik, Ammar Mahran

arXiv:2609.33383v1math.OCcs.LG

TL;DR

Constrained convex optimization methods often access the feasible set through projections, while Local LMO instead uses a linear minimization over a local ball. The paper shows this step is itself a projection onto a separating half-space under a radius condition, and establishes universal Hölder-rate guarantees for deep cuts and Local LMO.

  • Problem

    Constrained convex optimization needs methods that handle feasible-set constraints, while projection operations may be avoided by using linear-oracle access.

    Source: §1 · pp. 1–2

  • Method

    The paper interprets Local LMO as projection onto the feasible set intersected with a gradient-normal separating half-space when its ball radius is at most the Polyak radius, and studies a family indexed by cut depth.

    Source: §1 · p. 2, §5 · p. 9

  • Results

    Deep cuts attain O(K^-(1+ϑ)/2); at the Polyak radius, Local LMO attains that rate when constrained optima are unconstrained optima and O(K^-1/(2-ϑ)) otherwise.

    Source: §5 · pp. 9–10

  • Takeaways & Limitations

    Local LMO implements a projection using a linear oracle, and its stated rates do not require the feasible set to be bounded.

    Source: §1 · p. 2, §5 · p. 10

    The analysis assumes a nonempty closed convex feasible set, a convex differentiable objective with a nonempty solution set, and, for the rates, a ϑ-Hölder continuous gradient.

    Source: §1 · p. 2, §3.2 · p. 6

Abstract

from arXiv · show

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 $\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.

1 Introduction

Local LMO avoids an explicit projection oracle by minimizing a linear model over the feasible set intersected with a ball. The paper shows that, up to the Polyak radius, this step is a projection onto a separating half-space and places Local LMO within a broader family of projection methods with universal Hölder-rate guarantees.

1 Introduction

  • Local LMO minimizes a linear model over the feasible set intersected with a ball around the current iterate, avoiding explicit recourse to a projection oracle.The paper frames oracle access as a way to organize constrained optimization methods.Source: §1 · pp. 1–2
  • When the ball radius is at most the Polyak radius, Local LMO returns the Euclidean projection onto the feasible set intersected with a gradient-normal half-space separating the iterate from the solution set.The resulting projection is computed by one linear minimization, and the method is Fejér monotone with respect to the solution set.Source: §1 · p. 2

1.1 A family of projection methods

  • The broader family projects onto the feasible set intersected with a gradient-normal half-space, and indexes methods by the cut’s depth.An admissible cut excludes the current iterate while retaining every minimizer; the Polyak radius is an admissible depth and defines the Polyak cut.Source: §1.1 · pp. 2–3

1.2 Contributions

  • Every method using a deep cut attains a best-iterate rate of O(K^-(1+ϑ)/2) for convex objectives with ϑ-Hölder continuous gradients.The deep-cut band consists of depths at least the Polyak radius and no greater than the deepest localizing cut.Source: §1.2 · p. 3, §1.1 · p. 3
  • At the Polyak radius, Local LMO attains O(K^-(1+ϑ)/2) when constrained minimizers are unconstrained optima, and O(K^-1/(2-ϑ)) otherwise.Both exponents are at least the Frank–Wolfe exponent ϑ on [0, 1], and neither guarantee requires a bounded feasible set.Source: §1.2 · p. 3

2 Related Literature

The related literature distinguishes methods by how they access the feasible set and by the geometry of their updates. This paper connects Local LMO to projection onto separating cuts while highlighting its linear-oracle implementation and Hölder-rate guarantees.

Frank–Wolfe and projection-free methods

  • Frank–Wolfe methods use a global linear minimization oracle and attain O(K^-ϑ) under ϑ-Hölder smoothness, requiring a bounded feasible set.The cited discussion contrasts this with projection-free variants and other methods that add structural assumptions or geometric constants.Source: §2 · p. 4

Projection onto a separating cut

  • Projection onto gradient-normal separating cuts has precedents in subgradient projectors, level methods, and variational-inequality methods.The paper identifies as its distinction that a single trust-region linear minimization can produce such a projection for arbitrary closed convex feasible sets.Source: §2 · p. 4

Universal and Hölder-smooth methods

  • Universal gradient methods attain O(K^-(1+ϑ)/2) unaccelerated and O(K^-(1+3ϑ)/2) accelerated across the Hölder scale without knowing (ϑ, Lϑ).The cited account attributes these rates to Nesterov (2015) and notes the unaccelerated method uses backtracking line search.Source: §2 · p. 4

Local LMO and the Polyak stepsize

  • Prior Local LMO work establishes well-posedness, structured-set closed forms, and convergence under smoothness, strong convexity, and bounded gradients.The passage also relates the Polyak radius to the Polyak stepsize and notes that it presumes knowledge of f⋆, which may be estimated online.Source: §2 · p. 4

3 Theory

The theory recasts Local LMO as a projection onto a minimizer-localizing half-space, then analyzes convergence through the depth of such cuts. Deep cuts have a universal Hölder rate; Local LMO has a separate rate guarantee that accounts for shallower cuts.

3.1 Local LMO is a projection method

  • For admissible radii, the Local LMO step is the projection onto a half-space that localizes minimizers, has length t, and reduces squared distance to each minimizer by at least t^2.Its cut depth is positive and at most the radius, and the cut separates the current iterate from the solution set.Source: §3.1 · p. 5

3.2 A universal rate for deep cuts

  • K^-(1+ϑ)/2 is the universal best-iterate rate for projection methods whose cut depths lie between the Polyak radius and the largest depth retaining every minimizer.The method does not need prior knowledge of the Hölder exponent or constant; the rate matches the universal primal gradient method of Nesterov (2015).Source: §3.2 · pp. 6–7

3.3 A universal rate for Local LMO

  • The rate analysis handles shallow Local LMO cuts by charging their gradient-weighted depth shortfall as overshoot, which quantifies the failure of the deep-cut descent bound.The function gap equals the one-step Bregman divergence plus overshoot; the refined Fejér contraction compensates for steps that make little function-value progress.Source: §3.3 · pp. 7–8
  • When G*=0, Local LMO recovers the deep-cut exponent; otherwise its Polyak-radius guarantee has exponent 1/(2−ϑ).For G*=0 the second term in the Local LMO bound disappears; at ϑ=0 the two exponents coincide at 1/2.Source: §3.3 · p. 8

4 Experiments

The experiment compares Local LMO at the Polyak radius with a projection method at the Polyak cut on a two-dimensional objective. As G increases, Local LMO develops a longer initial plateau, while the projection method is unaffected by G.

4 Experiments

  • The Local LMO plateau grows linearly with G, whereas the projection method converges linearly and is unaffected by G.At G=0 the two methods coincide.Source: Figure 1 · p. 9, §4 · p. 9
  • The comparison uses ϑ=1/2 and varies G while keeping the Hölder constant fixed; both methods remain on the feasible face y=0.For G>0 the constrained minimizer is unique and lies on the boundary; the objective's affine term vanishes along the face where the iterates move.Source: §4 · p. 8, Figure 1 · p. 9
  • At each position, the suboptimality is independent of G but the gradient norm grows with G, throttling the Polyak radius and limiting each step to at most a0/G.The initial distance R therefore takes at least GR/a0 iterations to cover, explaining the observed plateau.Source: §4 · p. 9

5 Conclusion

The conclusion identifies Local LMO as a projection method whenever its radius is at most the Polyak radius, despite requiring only a linear oracle. It places the method in a depth-indexed family and summarizes universal rate guarantees for deep cuts and Local LMO.

5 Conclusion

  • Whenever its radius does not exceed the Polyak radius, Local LMO returns the Euclidean projection onto the feasible set intersected with a gradient-normal half-space separating the iterate from every minimizer.The projection is computed by a single linear minimization over the feasible set intersected with a ball.Source: §5 · p. 9
  • The family of projection methods can be indexed by the depth of the half-spaces onto which its members project.Local LMO selects its own half-space while remaining implementable by a linear oracle.Source: §5 · p. 9
  • K^-(1+ϑ)/2 is guaranteed for the deep-cut family and for Polyak-radius Local LMO when the constrained optima are also unconstrained; otherwise Local LMO has rate K^-1/(2−ϑ).Neither guarantee requires the feasible set to be bounded.Source: §5 · pp. 9–10

A Proof of Theorem 2: Local LMO is a projection method

The proof establishes the projection identity through geometric properties of Local LMO and relationships among cut levels and depths. It then shows how localization of minimizers supports Fejér monotonicity and how the relevant thresholds are ordered.

A Proof of Theorem 2: Local LMO is a projection method

  • The Local LMO step has length t and satisfies the projection characterization for the feasible set intersected with its gradient-normal localizing half-space.The proof outline derives these properties from the local linear minimization subproblem and the geometry of the ball.Source: A Proof of Theorem 2: Local LMO is a… · p. 15

A.3 Localization and Fejér monotonicity

  • When a cut retains every minimizer, projection onto the localized feasible set yields Fejér monotonicity with respect to the solution set.The proof uses inclusion of the minimizers in the projected set and the standard projection optimality condition.Source: A Proof of Theorem 2: Local LMO is a… · p. 15, §A.3 · p. 18

A.1 Levels and depths

  • Cut levels and depths are order-reversing descriptions, with the admissible thresholds corresponding to the ordered depths s_lmo(x,t) ≤ t ≤ t(x) ≤ s*(x).Here t(x) is the Polyak radius; a cut localizes the solution set when its depth does not exceed s*(x).Source: §A.1 · p. 15

A.2 Preliminary lemmas

  • The gradient is constant across the solution set, so its norm at a constrained minimizer does not depend on which minimizer is chosen.The preliminary lemmas also establish that a feasible point with zero gradient is a minimizer.Source: §A.2 · p. 15

A.4 Three thresholds

  • For t ≤ t(x), the thresholds satisfy αcvx(x) ≤ αproj(x,t) ≤ αlmo(x,t), with αproj(x,t)=αcvx(x) when t=t(x).The resulting half-space inclusions establish the ordering needed for the projection identity.Source: §A.4 · p. 19

A.5 Identification, step length, and the proof of Theorem 2

Theorem 2 characterizes an admissible Local LMO step as a Euclidean projection onto the feasible set intersected with a separating half-space. It also establishes the step length and distance properties that support this characterization.

A.5 Identification, step length, and the proof of Theorem 2

  • The Local LMO minimizer lies on the boundary of the radius-t ball, so the step length is t.The argument uses convexity of the feasible set and first-order optimality for the local linear minimization problem.Source: §A.5 · pp. 20, 21, 23
  • For 0 < t ≤ t(x), the Local LMO step is the Euclidean projection onto the feasible set intersected with a gradient-normal half-space.The half-space separates the current iterate from the minimizers.Source: §A.5 · pp. 20, 23
  • The Local LMO depth is admissible and no greater than the radius, and its half-space separates the iterate from the minimizers.The proof establishes positive depth and uses the Polyak-radius condition to localize the solution set.Source: §A.5 · p. 23
  • The theorem’s squared-distance bound guarantees a reduction of at least t^2 in distance to every minimizer.The resulting Fejér monotonicity makes the distance to each minimizer nonincreasing.Source: §A.5 · pp. 23–24
  • The projection characterization makes the Local LMO minimizer unique.The minimizers of the local linear problem lie on the ball boundary, and their set is convex, so it is a singleton.Source: §A.5 · pp. 20, 23

B Proof of Theorem 3: a universal rate on the deep-cut band

The proof establishes a universal rate for projection methods with cuts in the deep-cut band. Its argument combines a function-gap bound at the Polyak cut with summable step lengths from Fejér monotonicity.

B Proof of Theorem 3: a universal rate on the deep-cut band

  • Cuts in the deep-cut band yield the universal rate K^(-(1+ϑ)/2) without requiring knowledge of ϑ or L_ϑ.The proof outline attributes the rate to a function-gap bound and summability of squared step lengths.Source: B Proof of Theorem 3: a universal rate… · p. 24

B.1 The Polyak cut turns a Bregman divergence into a function gap

B Proof of Theorem 3: a universal rate on the deep-cut band

  • Fejér monotonicity makes squared step lengths summable, bounding the shortest of K steps in terms of the initial distance to the solution set.The proof combines this step-length bound with Hölder continuity to obtain the rate.Source: B Proof of Theorem 3: a universal rate… · p. 24

B.2 A universal rate for any method that cuts at the Polyak level

The argument gives a rate bound for methods satisfying a Polyak-level function-gap condition and a Fejér-type distance decrease. Hölder continuity controls the function gap through the step length, while the distance decrease limits the shortest step.

B.2 A universal rate for any method that cuts at the Polyak level

  • Hölder continuity of the gradient bounds the Bregman divergence by L_ϑ/(1+ϑ) times distance raised to 1+ϑ.This links the function gap to the step length in the rate argument.Source: §B.2 · pp. 24–25
  • For a method satisfying the stated properties, the best of its first K iterates has gap bounded by L_ϑ/(1+ϑ) times the shortest step length raised to 1+ϑ.The bound follows by combining the function-gap property with the Hölder bound on the Bregman divergence.Source: §B.2 · pp. 24–25
  • A Fejér-type decrease subtracts each squared step length from the squared distance to every minimizer.Telescoping this decrease yields the bound on the shortest step used in the argument.Source: §B.2 · pp. 24–25

B.3 Proof of Theorem 3

Theorem 3 proves a universal rate for deep-cut projection methods by verifying function-gap and Fejér conditions. The Local LMO proof outline treats its cuts separately, while the Hölder analysis supplies gradient and radius bounds used in that argument.

B.3 Proof of Theorem 3

  • For a Hölder-continuous gradient with exponent ϑ ∈ [0,1], Theorem 3 establishes a universal Hölder rate when possibly adaptive depths remain in the deep-cut band, stopping upon reaching an optimum.The proof’s minimum is over x1, …, xK, sharper than one over x0, …, xK.Source: §B.3 · p. 25

C Proof of Theorem 4: a universal rate for Local LMO

  • The Local LMO proof handles cuts above the Polyak level separately because the deep-cut-band analysis does not apply.Its outline tracks suboptimality, the fraction of available first-order decrease captured by the oracle, and squared-distance decrease.Source: C Proof of Theorem 4: a universal rate… · pp. 25–26
  • The Local LMO analysis combines gradient bounds, gap and overshoot estimates, and the projection identity with Fejér monotonicity.Its proof outline also counts steps by whether they exceed a threshold, stall, or are productive.Source: C Proof of Theorem 4: a universal rate… · pp. 25–26

C.1 Two consequences of Hölder continuity

  • The Hölder analogue of a standard smooth inequality is developed alongside a separate Hölder-0 bound on the Bregman divergence.The latter is described as forcing the gradient map to have bounded range.Source: §C.1 · pp. 26–27
  • Hölder continuity bounds the gradient difference from a constrained minimizer in terms of the function gap.The resulting bounds support estimates on the gradient and on the Polyak radius along Local LMO runs.Source: §C.1 · pp. 26–27

C.2 The local Frank–Wolfe gap and the overshoot

The local Frank–Wolfe gap lower-bounds progress in proportion to the step radius, while an overshoot term limits how far a Local LMO step can reduce suboptimality. The overshoot vanishes only at the full Polyak radius when the unconstrained ball minimizer is feasible.

C.2 The local Frank–Wolfe gap and the overshoot

  • ℓ(x,t) is at least t/||x−x⋆|| times the suboptimality f(x)−f⋆ for every optimizer x⋆.The bound follows from convexity and holds for 0<t≤t(x).Source: §C.2 · pp. 27–28
  • At radius tk, the Local LMO point lies in the projection half-space exactly when the unconstrained ball minimizer is feasible in X.When the constraint is active, the step lies outside that half-space.Source: §C.2 · p. 28
  • Every Local LMO step has suboptimality equal to its Bregman divergence plus the nonnegative overshoot Γk.Thus f(xk+1)−f⋆=Df(xk+1,xk)+Γk.Source: §C.2 · p. 28
  • The overshoot is a floor on the next suboptimality and vanishes only at the full Polyak radius when the unconstrained ball minimizer is feasible.A shorter radius leaves a positive floor even when X is inactive.Source: §C.2 · p. 28
  • For a Hölder-continuous gradient, the suboptimality recursion combines the local gap with a smoothness error proportional to tk^(1+ϑ).The stated assumptions are 0<tk≤t(xk), with the iterate distance bounded by R.Source: §C.2 · p. 28

C.3 The sharpened Fejér budget

The sharpened Fejér analysis relates the Local LMO step to projection onto a half-space and tracks both distance progress and function-value progress. At the Polyak radius, the overshoot fraction ρk exposes a trade-off between these two forms of progress.

C.3 The sharpened Fejér budget

  • A point on the segment from xk to an optimizer is chosen on the half-space boundary, letting the projection inequality yield a sharpened distance bound.The construction sets s=ℓk/(ℓk+εk(x⋆)) and z=(1−s)xk+sx⋆.Source: §C.3 · p. 29
  • At the Polyak radius, ρk=ℓk/ak lies in (0,1], and smaller ρk worsens value progress while improving distance progress by the reciprocal factor.The overshoot is Γk=(1−ρk)ak.Source: §C.3 · p. 29
  • Corollary 28 gives a bound for Local LMO run at the Polyak radius, assuming iterates remain outside the solution set through step K−1.Its proof is described as telescoping the sharpened distance inequality.Source: §C.3 · p. 29

C.4 Proof of Theorem 4

Theorem 4 analyzes Local LMO at the Polyak radius for Hölder-continuous gradients, using Fejér and value-progress budgets. Its proof divides the run into regimes to bound the best suboptimality among the first K iterates.

C.4 Proof of Theorem 4

  • The proof balances small value progress against its reciprocal Fejér-budget cost, so the overshoot fraction ρk cannot be chosen without a corresponding distance cost.It separates steps into stalling and productive groups and bounds their counts.Source: §C.4 · pp. 30, 32, 33
  • The proof bounds constants Dϑ and Eϑ before applying its case analysis to the Hölder-rate estimate.The supplied bounds include Dϑ≤25/2 and E(1)ϑ≤25.Source: §C.4 · p. 30
  • Theorem 4 establishes a universal Hölder-rate bound for Local LMO at the Polyak radius when the gradient is Hölder continuous.The run starts outside the solution set and stops if it reaches that set.Source: §C.4 · p. 31
  • When ϑ=0, the proof gives min_{k≤K} a_k ≤ max{Λ1,Λ2}K^-1/2, with Λ1=25/2 L0R and Λ2≥25G⋆R, by (22).Source: §C.4 · p. 31
  • For G⋆=0, the proof sets Λ2=0; when G⋆>0, it splits the run at the threshold ā and further separates productive from stalling steps.The threshold and case split organize the proof's bounds on the first K iterates.Source: §C.4 · pp. 31–32
  • In the G⋆>0 case, one branch bounds A by a constant times K^-1/(2−ϑ), yielding the same exponent for the stated Λ2 bound.The displayed comparison gives A≤E(3)ϑG⋆R K^-1/(2−ϑ)≤Λ2K^-1/(2−ϑ).Source: §C.4 · p. 33
Loading 2609.33383v1…