acceptodds
Under review as a conference paper at ICLR 2027

Local LMO is Secretly a Projection Method!

Abstract

The local linear minimization oracle, 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—a projection that 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 -Hölder continuous gradient, every method from this family whose half-space lies sufficiently deep drives the best of its first iterates to optimality at the universal rate , matching the non-accelerated universal gradient method of Nesterov. Run at the Polyak radius, Local LMO attains the same rate when the constrained optima are also unconstrained (), and the rate otherwise.

Primary area:
optimization
Keywords:
LMO, local linear minimization oracle, frank-wolfe, projection methods

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_EtyKOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies Local LMO, which minimizes a linear approximation of the objective over the feasible set intersected with a ball around the current iterate. It shows that, in this restricted setting, Local LMO is equivalent to a projection method: the update projects onto the feasible set intersected with a half-space containing all minimizers. The authors use this connection to derive convergence rates under Hölder smoothness for both a broader family of projection methods and Local LMO itself.

Critical strengths
  • Connection to projection methods:
    The paper gives a clear geometric interpretation of Local LMO and connects it to established tools for analyzing projection methods. I find this nice since it connects LMO (that we usually motivate/think of as projection-free) with a projection method. Hence, runtime analysis from projection methods can/are be borrowed to obtain better convergence times.

  • Improved convergence analysis:
    Under Hölder smoothness, the basic Fejér analysis of the Polyak-radius iteration retains a K−1/2K^{-1/2} term when the solution gradient is nonzero. Theorem 4 uses a refined distance-decrease argument to obtain O(K−1/(2−ϑ))O(K^{-1/(2-\vartheta)}) for the same iteration, yielding K−2/3K^{-2/3} for ϑ=1/2\vartheta=1/2 and K−1K^{-1} in the smooth case. Earlier smooth Local LMO results use a different radius and control gradient differences, so they do not directly establish this function-gap guarantee. This is a nontrivial improvement in the analysis of the existing method.

Critical weaknesses
  • Limited novelty of the projection characterization:
    The projection identity follows fairly directly from local optimality and the known boundary property of Local LMO. The main technical advance is therefore the refined convergence analysis of an existing algorithm.

  • Unresolved rate tightness:
    The paper does not establish whether the rate O(K−1/(2−ϑ))O(K^{-1/(2-\vartheta)}) is tight when the solution gradient is nonzero. The two-dimensional example illustrates the geometric mechanism, but does not resolve whether the slower guarantee reflects an intrinsic limitation of Local LMO or a limitation of the analysis.

Questions for authors
  • Rate tightness: For 0<ϑ<10<\vartheta<1, is the rate O(K−1/(2−ϑ))O(K^{-1/(2-\vartheta)}) tight when the solution gradient is nonzero? Does the slower exponent reflect an intrinsic limitation of Local LMO, or could the analysis potentially recover O(K−(1+ϑ)/2)O(K^{-(1+\vartheta)/2})?

  • Practical scope:
    Could you identify concrete problem classes where f⋆f^\star is known and the local oracle over X∩B(xk,tk)X \cap B(x_k,t_k) is computationally attractive compared with projection onto XX? This would help clarify where the theoretical guarantees could be useful in practice.

1 comment

We thank the reviewer for the positive and precise review, and address all points raised below.

The projection identity follows fairly directly from local optimality and the known boundary property of Local LMO. The main technical advance is therefore the refined convergence analysis of an existing algorithm.

Agreed: the proof of Thm 2 is short. What is new is the set it identifies, a half-space that contains X⋆\mathcal X_\star and whose depth drives the sharpened Fejér bound (Thm 26) and hence Thm 4. Sec. 3.1 now also relates Thm 2 to the projected-gradient reading of Ferris & Zavriev (1996, Thm 2.10).

For 0<ϑ<10<\vartheta<1, is the rate O(K−1/(2−ϑ))O(K^{-1/(2-\vartheta)}) tight when the solution gradient is nonzero? Does the slower exponent reflect an intrinsic limitation of Local LMO, or could the analysis potentially recover O(K−(1+ϑ)/2)O(K^{-(1+\vartheta)/2})?

Yes, for ϑ∈(0,1)\vartheta\in(0,1): the exponent 12−ϑ\frac1{2-\vartheta} is attained, so the slowdown is intrinsic to Local LMO at the Polyak radius (new Sec. 3.4, App. D). Thm B gives, for every G⋆>0G_\star>0 and every large enough KK, an instance in R3\mathbb R^3 with min⁡k≤Kak≥1100(LϑR2G⋆1−ϑ)1/(2−ϑ)K−1/(2−ϑ)\min_{k\le K}a_k\ge\frac1{100}(L_\vartheta R^2G_\star^{1-\vartheta})^{1/(2-\vartheta)}K^{-1/(2-\vartheta)}, so no analysis can recover K−(1+ϑ)/2K^{-(1+\vartheta)/2} over the class. On these instances the gradient pushes into the constraint while the step zig-zags across a thin valley, so almost all of each step is wasted. As in classical lower bounds (Nesterov 2004, Sec. 2.1.2, Thm 2.1.7; Drori & Teboulle 2014, Thm 2), the instance depends on KK, but any fixed instance may converge faster. The dependence on G⋆G_\star cannot be removed, and no constant of Thm 4 can be reduced by more than a ϑ\vartheta-dependent factor (Prop. A, Cor. 36, Rem. 38). Fig. 1 (right) illustrates Thm B.

Could you identify concrete problem classes where f⋆f_\star is known and the local oracle over X∩B(xk,tk)\mathcal X\cap\mathcal B(x_k,t_k) is computationally attractive compared with projection onto X\mathcal X?

f⋆=0f_\star=0 is known in consistent feasibility problems written as minimization, e.g. finding x∈Xx\in\mathcal X with Ax=bAx=b (f=12∥Ax−b∥2f=\frac12\lVert Ax-b\rVert^2) or x∈X∩Cx\in\mathcal X\cap C (f=12dist2(x,C)f=\frac12\mathrm{dist}^2(x,C)), and in interpolating models; otherwise f⋆f_\star can be estimated online as for Polyak steps (though this is not covered by our analysis). In these examples G⋆=0G_\star=0, where Thm 4 gives K−(1+ϑ)/2K^{-(1+\vartheta)/2}.

On cost, we do not claim the local oracle is cheaper than projection. By Ferris & Zavriev (Thm 2.10, Lemma 2.5), it is a projected-gradient step whose stepsize is found by a 1-D search (e.g. bisection), each trial costing one projection onto X\mathcal X (Sec. 3.1). The closed-form cases of Richtárik et al. (affine sets, Euclidean balls, one-dimensional sets) also have cheap projections. Our contribution is to the theory of this oracle rather than a cost advantage.


We thank the reviewer again, and hope the new lower bounds settle the question of tightness.

Reviewer_UZTHOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This work establishes the interesting geometric equivalence between implementing LMO over intersection with a ball of smaller than Polyak radius and implementing projection over intersection with a certain half-space, and provided unviersal holder rates for a family of projection methods in light of this observation.

Critical strengths
  1. Clear presentation and a potentially important geometric insight.

The authors do a very good job of establishing the background and motivation for the problem. In particular, the Introduction clearly distinguishes between separation oracles, projection oracles, and linear minimization oracles (LMOs), with appropriate citations and representative algorithms for each category. This provides a helpful foundation for understanding the paper's contributions.

More importantly, Theorem 2 establishes an interesting geometric connection between Local LMO and projection methods. Showing that Local LMO can implicitly perform a projection onto the intersection of the feasible set and a separating half-space is a potentially valuable conceptual insight. I believe this connection could have broader theoretical implications for the projection-free optimization community.

  1. New convergence guarantees arising from the geometric interpretation.

Theorems 3 and 4 further develop the implications of this geometric connection by establishing universal convergence guarantees under Hölder continuity. In particular, Theorem 4 provides an improved convergence analysis for Local LMO, while Theorem 3 establishes a common convergence guarantee for a broader family of deep-cut projection methods.

These results suggest that the geometric characterization is not merely an alternative interpretation of an existing algorithm, but can also lead to meaningful theoretical developments.

Critical weaknesses
  1. Insufficient motivation for Local LMO and unclear practical significance of the results.

While I am familiar with the extensive literature on standard LMOs (also called linear optimization oracles, LOOs), I have encountered relatively little work involving Local LMO, defined as linear minimization over the intersection of the feasible set and a ball. The authors cite Ferris & Zavriev (1996) and Richtárik et al. (2026), but I would appreciate more concrete motivation for investigating this particular oracle.

In particular, it is unclear to me under what circumstances Local LMO offers advantages over a conventional LMO, or how their computational costs compare. Since Local LMO solves a more restricted optimization subproblem, its computational cost should not automatically be assumed equivalent to that of a standard LMO.

This uncertainty makes it difficult to assess the practical significance of the proposed theoretical results. Although the geometric connection is interesting, I am not yet convinced that it will materially influence the design or analysis of optimization algorithms in practice.

  1. The framing may suggest broader implications than the results establish.

When I first read the title and Introduction, I expected the paper to establish a broad connection between linear minimization and projection oracles. However, the main equivalence in Theorem 2 applies specifically to Local LMO with a radius bounded by the Polyak radius, and the corresponding projection is onto the intersection of the feasible set and a particular separating half-space, rather than onto the original feasible set alone.

I fully understand and appreciate this mathematical distinction. Nevertheless, I found that the initial framing gave me a somewhat different impression of the scope of the contribution.

In particular, I was initially left with the impression that the authors intended to challenge the conventional characterization of Local LMO as a projection-free method. After reading the paper more carefully, I instead understood the contribution as showing that a computationally projection-free procedure can be interpreted geometrically as a particular projection method.

These are rather different messages, with different implications for the optimization community. I believe the authors could better articulate this distinction and more clearly explain the significance of the result beyond the mathematical equivalence itself.

Questions for authors
  1. What motivates the use of Local LMO instead of conventional LMO? (Clarification — significance and applicability)

Could the authors provide concrete examples or applications in which Local LMO is preferable to a conventional LMO, particularly in terms of computational efficiency or algorithmic performance?

I recognize that my unfamiliarity with Local LMO may partly reflect my own research background, which is more closely related to separation oracles. Nevertheless, understanding where Local LMO is useful would substantially help me assess the significance of the paper's contribution.

More specifically, are there important classes of feasible sets where Local LMO is computationally efficient, and how does its oracle cost compare with that of a standard LMO or an explicit projection? It is ok if these are considered to be different access model instead of computational improvements.

  1. What exactly does the projection interpretation imply for the concept of projection-free optimization? (Clarification — scope of the contribution)

It has been my observation that much of the projection-free optimization literature uses the term "projection-free" to describe algorithms relying on linear minimization rather than explicit projections.

My understanding of Theorem 2 is that Local LMO remains computationally projection-free, but its output coincides with a projection onto the feasible set intersected with a particular half-space, provided the radius satisfies the theorem's assumptions.

Is this interpretation correct?

If so, should the result be understood primarily as a new geometric interpretation that facilitates convergence analysis, rather than as a challenge to the conventional notion of projection-free algorithms?

Furthermore, since the identified projection is onto an intersection with a half-space rather than onto the feasible set itself, should the two operations be considered computationally distinct?

I would appreciate clarification of the intended conceptual message and how the authors believe the broader community should interpret this result.

  1. What are the concrete algorithmic implications of Theorems 3 and 4? (Clarification — impact of the theoretical results)

I appreciate the universal Hölder convergence guarantees established in Theorems 3 and 4. However, these guarantees concern a particular family of projection methods and Local LMO under a specific radius rule.

Could the authors clarify what these results imply for algorithm design or for the broader projection-free optimization literature?

For example, do the results suggest that practitioners should favor Local LMO over conventional LMO when both are available? Or is the main contribution an improved theoretical understanding and convergence analysis of an existing algorithm?

A clearer discussion of the improvements over previously established Local LMO convergence guarantees, together with their practical or algorithmic implications, would significantly strengthen my assessment of the paper.

  1. What are the precise improvements over previous convergence guarantees, and to what extent do they rely on the geometric equivalence? (Clarification — novelty and significance)

I would appreciate a more explicit comparison between Theorems 3 and 4 and the existing convergence guarantees in the literature.

My understanding is that Theorem 3 establishes a universal convergence guarantee for a particular family of deep-cut projection methods, matching the rate of Nesterov (2015), rather than improving the best-known rate. In contrast, Theorem 4 appears to strengthen the convergence guarantees for the existing Local LMO algorithm by exploiting the geometric equivalence established in Theorem 2.

In particular, Richtárik et al. (2026, Theorem 3.6) established an (O(K^{-1/2})) objective-gap guarantee for Local LMO under bounded gradients using the Polyak radius, whereas Theorem 4 appears to improve this to (O(K^{-1})) in the smooth convex setting. However, the prior work also established other convergence guarantees under different radius choices and convergence measures.

Could the authors clarify precisely which convergence guarantees are genuinely improved compared with prior Local LMO results, under comparable assumptions, radius choices, and performance measures? Furthermore, to what extent are these improvements enabled by the new projection interpretation in Theorem 2, rather than by an independent refinement of the convergence analysis?

A more explicit comparison with prior results, potentially in tabular form, would help me assess the novelty and significance of these contributions.

Overall, I find the mathematical connection interesting and potentially important, and I appreciate the clarity of the theoretical presentation. My main reservation concerns the significance and scope of the contribution rather than the presentation of the mathematics itself. I would be open to revising my assessment if the authors could clarify these questions and better establish the implications of their results.

2 comments

We thank the reviewer for the careful and constructive review---the questions shaped our revision.

[...] it is unclear to me under what circumstances Local LMO offers advantages over a conventional LMO, or how their computational costs compare. [...] how does its oracle cost compare with that of a standard LMO or an explicit projection? It is ok if these are considered to be different access model [...]

We view it as a different access model, as the reviewer suggests. Unlike those for Frank–Wolfe, its guarantees need neither a bounded X\mathcal X nor a curvature constant, and its exponents exceed the Frank–Wolfe exponent ϑ\vartheta on [0,1)[0,1); but it needs f⋆f_\star. On cost: by Ferris & Zavriev (1996, Thm 2.10, Lemma 2.5), the step is a projected-gradient step whose stepsize is found by a 1-D search (e.g. bisection), each trial costing one projection onto X\mathcal X (Sec. 3.1). Over a polytope, the LMO is an LP while Local LMO adds a Euclidean ball (an SOCP). Closed forms exist for affine sets, Euclidean balls and 1-D sets (Richtárik et al.), and f⋆=0f_\star=0 is known in consistent feasibility problems. We do not claim it should replace the LMO.

My understanding of Theorem 2 is that Local LMO remains computationally projection-free, but its output coincides with a projection onto the feasible set intersected with a particular half-space [...]. Is this interpretation correct? [...] should the two operations be considered computationally distinct?

Yes on both counts. Local LMO stays computationally projection-free; for t≤t(x)t\le t(x) its output equals a projection onto X∩H\mathcal X\cap\mathcal H, not onto X\mathcal X. The half-space H\mathcal H is selected by the oracle itself; a projection onto X\mathcal X intersected with a prescribed half-space (e.g. the Polyak cut) is in general not available from a linear oracle. The result is a geometric interpretation, not a challenge to the notion of projection-free methods: it places Local LMO in the same family of cut projections as the method of Nesterov (2024) and drives the analysis. The abstract, introduction and conclusion now say this, close to the reviewer's words.

[...] do the results suggest that practitioners should favor Local LMO over conventional LMO when both are available? Or is the main contribution an improved theoretical understanding and convergence analysis of an existing algorithm?

The latter. The results say when Local LMO at the Polyak radius is as good as the projection benchmark (Thm 3) and when it is not:

  1. If ∇f(x⋆)=0\nabla f(x_\star)=0, it attains the same exponent 1+ϑ2\frac{1+\vartheta}{2}, universally over ϑ\vartheta and without a bounded X\mathcal X.
  2. If G⋆>0G_\star>0, its gap can plateau for G⋆R/(2a0)G_\star R/(2a_0) steps (Prop. A), and for ϑ∈(0,1)\vartheta\in(0,1) its worst-case exponent drops to 12−ϑ\frac1{2-\vartheta}, which is intrinsic to the method, not to the analysis (Thm B, Sec. 3.4).
  3. The identification lets tools from the analysis of projection methods, such as Fejér bounds and the depth of the cut, be applied to an LMO-type method. Thm 4 is obtained this way: its proof rests on the sharpened Fejér bound (Thm 26), which is the projection inequality onto X∩H\mathcal X\cap\mathcal H.

Could the authors clarify precisely which convergence guarantees are genuinely improved [...]? Furthermore, to what extent are these improvements enabled by the new projection interpretation in Theorem 2 [...]? [...] potentially in tabular form [...]

The new Table 1 compares by assumptions, radius (and what it requires), measure, and rate. At the Polyak radius:

  • Richtárik et al. (v1, Thm 3.6) give GR/KGR/\sqrt K on the best gap under bounded gradients; their updated manuscript (v2 of 28 Sep 2026, Thm 3.5) gives (G⋆+LR)R/K(G_\star+LR)R/\sqrt K for LL-smooth ff, and 2LR2/K2LR^2/K if G⋆=0G_\star=0 (averaged iterate).
  • Our Thm 4 needs no gradient bound and gives K−1/(2−ϑ)K^{-1/(2-\vartheta)} on the best gap when G⋆>0G_\star>0, i.e. 1/K1/K for smooth ff, universally over ϑ\vartheta; for ϑ∈(0,1)\vartheta\in(0,1), Thm B shows that this exponent is attained.

Their other results use other radii, which need ∇f(x⋆)\nabla f(x_\star), x⋆x_\star, LL, or RR and KK (e.g. LR2/(2K)LR^2/(2K) at radius R/KR/\sqrt K, v2, Thm 3.2), or other measures (gradient residual, distance). Our Thm 3 matches Nesterov (2015) and coincides with Nesterov (2024) at the Polyak cut.

The improvement relies on Thm 2: the sharpened Fejér bound (Thm 26) is the projection inequality onto X∩H\mathcal X\cap\mathcal H, applied where [xk,x⋆][x_k,x_\star] meets the boundary of H\mathcal H. The plain Fejér decrease gives only K−1/2K^{-1/2} when G⋆>0G_\star>0.


We hope these clarifications address the reviewer's reservations about significance and scope, and that they will reconsider their assessment.

Thank you for the response, and all my previous questions were addressed. My previous review leans more on presentation and understanding of the results and its impact on the larger communitry, and less on technical details. However, since the other reviewer seems to be familiar with the matter, I look forward to hearing/looking into more details during the discussion phase before conveying any decisions.

Reviewer_vNA2OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the relationship between the Local Linear Minimization Oracle (Local LMO) and projection-based methods for constrained convex optimization. The main result shows that, when the local radius does not exceed the Polyak radius, a Local LMO step can be interpreted as a Euclidean projection onto the intersection of the feasible set and a separating half-space. Based on this characterization, the authors introduce a family of projection methods indexed by the depth of the half-space cut. They establish a universal O(K−(1+ϑ)/2)O(K^{-(1+\vartheta)/2}) best-iterate rate for sufficiently deep cuts under Hölder smoothness. For Local LMO at the Polyak radius, they derive an O(K−1/(2−ϑ))O(K^{-1/(2-\vartheta)}) rate when the optimal gradient is nonzero, recovering O(1/K)O(1/K) in the smooth case. The analysis further introduces an overshoot quantity and a refined Fejér decrease inequality to explain the convergence behavior. A two-dimensional synthetic example illustrates the difference between Local LMO and Polyak-cut projection.

Critical strengths
  • Theorem 26 sharpens Fejér monotonicity using Theorem 2, explaining why nearly tangential steps still reduce the distance to the solution set.
  • For smooth objectives, Theorem 4 gives an O(1/K)O(1/K) best-iterate rate at the Polyak radius, even with nonzero optimal gradient and without globally bounded gradients. This improves the O(1/K)O(1/\sqrt K) bound of Richtárik et al. (2026, Theorem 3.6).
  • The guarantees require neither boundedness of the feasible set nor a Frank–Wolfe curvature constant.
  • Lemma 24 provides a useful explanation of slow progress through the overshoot term.
Critical weaknesses
  • Nesterov (2024, Lemma 5 and Theorem 1) gives the same Polyak-cut update and Hölder rate as the endpoint of Theorem 3, including the constant under the intended distance normalization. This work is not cited and only the extension to deeper cuts goes beyond it.
  • However, choosing depths beyond the Polyak cut requires information about the unknown solution set, and no general implementable rule is provided.
  • Ferris & Zavriev (1996, Theorem 2.10) already relate the same local subproblem to projected-gradient steps. Although Theorem 2 establishes a different half-space projection identity, it mainly recharacterizes an existing update rather than introducing a new method. Beyond enabling the refined convergence analysis, its additional conceptual or computational significance is unclear.
  • The optimal-value f⋆f_\star requirement is acknowledged but not emphasized despite comparisons with methods that do not require it.
  • Theorem 4 has no matching lower bound. On the paper's own example with G>0G>0, the gap decays as Θ(k−(1+ϑ)/ϑ)\Theta(k^{-(1+\vartheta)/\vartheta}), substantially faster than the stated bound.
  • Experiments use only one synthetic 2D family, comparing against Polyak-cut projection without evaluating oracle costs. Nesterov (2024, Example 2) already illustrates a related contrast.

Ferris, M. C., & Zavriev, S. K. (1996). The Linear Convergence of a Successive Linear Programming Algorithm. Technical Report 96-12, University of Wisconsin–Madison.

Lemaréchal, C., Nemirovskii, A., & Nesterov, Y. (1995). New Variants of Bundle Methods. Mathematical Programming, 69, 111–147.

Nesterov, Y. (2015). Universal Gradient Methods for Convex Optimization Problems. Mathematical Programming, 152, 381–404.

Nesterov, Y. (2024). Primal Subgradient Methods with Predefined Step Sizes. Journal of Optimization Theory and Applications, 203, 2083–2115.

Richtárik, P., Gruntkowska, K., & Li, H. (2026). Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle. arXiv:2605.08850.

Questions for authors
  • Lemma 5 and Theorem 1 of Nesterov (2024) appear to establish the Polyak-cut projection update and the same Hölder convergence rate as the endpoint case of Theorem 3. Could the authors clarify what is new in Theorem 3 beyond extending the admissible cuts to greater depths?

  • Ferris & Zavriev (1996, Theorem 2.10) already connect the local linear subproblem with projected-gradient steps. Beyond the different half-space projection characterization and its use in the convergence analysis, does Theorem 2 provide any additional algorithmic or computational advantage?

2 comments

We thank the reviewer for the detailed review and address each of their points below.

Nesterov (2024, Lemma 5 and Theorem 1) gives the same Polyak-cut update and Hölder rate as the endpoint of Theorem 3 [...]. Could the authors clarify what is new in Theorem 3 beyond extending the admissible cuts to greater depths?

The reviewer is right, and we regret missing this work. Thm 3 now credits Nesterov (2024, Thm 1) at the Polyak cut, Sec. 1.1 credits his Lemma 5 for the update, and Thm 3 is no longer a separate contribution; our addition is the extension to deeper cuts.

[...] choosing depths beyond the Polyak cut requires information about the unknown solution set [...]

Yes. The band is an analysis device: Local LMO's cut is never deeper than the Polyak cut, and Thm 3 is the benchmark Thm 4 is measured against. Sec. 1.1 now states that only the Polyak cut is implementable in general.

Ferris & Zavriev (1996, Theorem 2.10) already relate the same local subproblem to projected-gradient steps. [...] does Theorem 2 provide any additional algorithmic or computational advantage?

Their Thm 2.10 shows that the projected-gradient step PX(x−τ∇f(x))P_{\mathcal X}(x-\tau\nabla f(x)), with τ\tau chosen so that the step has length tt, solves the Local LMO subproblem; as that minimizer is unique (our Thm 2), the two coincide. Our Thm 2 describes the same point as the projection of xx onto X∩H\mathcal X\cap\mathcal H, where H\mathcal H is the half-space with normal ∇f(x)\nabla f(x) whose boundary passes through that point. Sec. 3.1 now discusses this and credits their result.

Thm 2 gives no computational advantage. Its value is analytical and conceptual: it places Local LMO in the same family of cut projections as the method of Nesterov (2024) and identifies what separates the two: a possibly shallower cut. H\mathcal H contains every minimizer, and its depth can be computed along the run; the projected-gradient form shows neither, only an unknown stepsize τ\tau. Thm 26 is the projection inequality onto X∩H\mathcal X\cap\mathcal H at the point where [xk,x⋆][x_k,x_\star] meets the boundary of H\mathcal H. Without it, the Fejér decrease of Richtárik et al. gives only K−1/2K^{-1/2} when G⋆>0G_\star>0 (cf. their v2, Thm 3.5); with it, Thm 4 obtains K−1/(2−ϑ)K^{-1/(2-\vartheta)}, i.e. 1/K1/K for smooth ff.

The optimal-value f⋆f_\star requirement is acknowledged but not emphasized [...]

f⋆f_\star is now stated as a requirement in the abstract, the contributions, and each comparison with Frank–Wolfe.

Theorem 4 has no matching lower bound. On the paper's own example with G>0G>0, the gap decays as Θ(k−(1+ϑ)/ϑ)\Theta(k^{-(1+\vartheta)/\vartheta}) [...]

Thm 4 bounds the worst case over all instances with given (ϑ,Lϑ,R,G⋆)(\vartheta,L_\vartheta,R,G_\star), and we now show that, for ϑ∈(0,1)\vartheta\in(0,1), its exponent is attained, its dependence on G⋆G_\star cannot be removed, and no constant can be reduced by more than a ϑ\vartheta-dependent factor (Sec. 3.4, App. D). As in classical lower bounds (Nesterov 2004, Sec. 2.1.2, Thm 2.1.7; Drori & Teboulle 2014, Thm 2), the instance may depend on the horizon KK, so faster convergence on a fixed instance is no contradiction. Prop A shows that on this example the gap stays above 2−(1+ϑ)a02^{-(1+\vartheta)}a_0 for G⋆R/(2a0)G_\star R/(2a_0) iterations, so the dependence on G⋆G_\star is necessary. Thm B gives, for ϑ∈(0,1)\vartheta\in(0,1) and every large enough KK, an instance in the same class with min⁡k≤Kak≥1100(LϑR2G⋆1−ϑ)1/(2−ϑ)K−1/(2−ϑ)\min_{k\le K}a_k\ge\frac1{100}(L_\vartheta R^2G_\star^{1-\vartheta})^{1/(2-\vartheta)}K^{-1/(2-\vartheta)}, so the exponent of Thm 4 is attained.

Experiments use only one synthetic 2D family [...] without evaluating oracle costs. Nesterov (2024, Example 2) already illustrates a related contrast.

Sec 4 shows the dependence on G⋆G_\star in the bound for Local LMO, to which the Polyak-cut projection is not subject; Fig 1 (right) now adds the instances of Thm B. Together they illustrate the two differences between Thm 4 (Local LMO) and Thm 3 (Polyak-cut projection). On oracle cost, Sec 3.1 now notes that, by Ferris & Zavriev (Lemma 2.5), Local LMO costs a 1-D search over projections when projecting onto X\mathcal X is cheap, and is otherwise a different access model. Sec 4 now cites Nesterov's Example 2; there, Local LMO gives ak=Θ(k−2)a_k=\Theta(k^{-2}), between the linear rate of the Polyak-cut projection and the Θ(k−1)\Theta(k^{-1}) of the classical projected Polyak step.


We hope this addresses the reviewer's concerns and that they will reconsider their assessment. Regarding the soundness score: if any step of our analysis is incorrect, we would be grateful to know; if not, we kindly ask that the score reflect this, as the points raised concern novelty and scope.

Thank you for the detailed response and revisions.

I appreciate the clarification of the relationship to Nesterov (2024) and Ferris & Zavriev (1996), as well as the additional lower-bound analysis for Theorem 4.

However, my main concerns regarding the novelty and significance of the contributions remain. The Polyak-cut endpoint of Theorem 3 is already established in prior work, while the extension to deeper cuts does not yield a generally implementable method. Theorem 2 provides a different geometric characterization of an existing update, but no additional computational advantage. The requirement for knowing the optimal objective value and the limited practical evaluation also remain important limitations.

Although the new tightness analysis strengthens the theoretical results, I do not find that it sufficiently changes the overall contribution or addresses my main concerns about its significance.

Therefore, I will maintain my original rating.

Comments on the paper

1 comment

We thank all reviewers for their time, their careful reading, and the discussion. Their comments improved the paper, and the revised version reflects them:

  • Reviewer vNA2 pointed us to Nesterov (2024), and we now place Local LMO next to Nesterov's method in the same family of cut projections. The discussion of Theorem 2 now also relates to the projected-gradient view of Ferris & Zavriev.
  • Reviewer UZTH's questions on framing and oracle cost led us to state clearly that Local LMO remains computationally projection-free while being geometrically a projection, and to clarify the framing of the method. The suggested comparison to existing guarantees (now in Table 1) makes the contribution and differentiation clearer.
  • Reviewer EtyK's question on tightness (also raised by Reviewer vNA2) led to the new lower bounds in Section 3.4 and Appendix D, which show that the exponent of Theorem 4 is attained.

We appreciate the constructive exchange and look forward to the final decision.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.