- 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 term when the solution gradient is nonzero. Theorem 4 uses a refined distance-decrease argument to obtain for the same iteration, yielding for and 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 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 , is the rate tight when the solution gradient is nonzero? Does the slower exponent reflect an intrinsic limitation of Local LMO, or could the analysis potentially recover ?
-
Practical scope:
Could you identify concrete problem classes where is known and the local oracle over is computationally attractive compared with projection onto ? This would help clarify where the theoretical guarantees could be useful in practice.
We thank the reviewer for the positive and precise review, and address all points raised below.
Agreed: the proof of Thm 2 is short. What is new is the set it identifies, a half-space that contains X⋆ 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).
Yes, for ϑ∈(0,1): the exponent 2−ϑ1 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⋆>0 and every large enough K, an instance in R3 with mink≤Kak≥1001(LϑR2G⋆1−ϑ)1/(2−ϑ)K−1/(2−ϑ), so no analysis can recover K−(1+ϑ)/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 K, but any fixed instance may converge faster. The dependence on G⋆ cannot be removed, and no constant of Thm 4 can be reduced by more than a ϑ-dependent factor (Prop. A, Cor. 36, Rem. 38). Fig. 1 (right) illustrates Thm B.
f⋆=0 is known in consistent feasibility problems written as minimization, e.g. finding x∈X with Ax=b (f=21∥Ax−b∥2) or x∈X∩C (f=21dist2(x,C)), and in interpolating models; otherwise f⋆ can be estimated online as for Polyak steps (though this is not covered by our analysis). In these examples G⋆=0, where Thm 4 gives K−(1+ϑ)/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 (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.