- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies the Broximal Gradient Descent (BroxGD) algorithm, whose updated is defined via linear minimization oracle (LMO) over an intersection of the constraint set and a ball centered around the current iterate. It provides convergence results of BroxGD over a broad range of problem settings, including the convex functions with bounded or Lipschitz continuous gradients, or smooth strongly convex functions.
Critical strengths
I think the strength of this paper is clear: it proposes a new axis for future developments. The paper calls broximal gradient method a "projection-free sister" of projected gradient descent (PGD) and dubbing it so is justified by demonstrating the potential that research on BroxGD could be extended to the degree comparable to that on PGD.
The paper is well-written, with consideration. It builds a nice parallelism between PGD and BroxGD, cleanly derives the LMO formulation of BroxGD, connects and compares BroxGD to gradient descent and Frank-Wolfe methods, and explains the geometric intuition behind the descent property BroxGD has. It is therefore easy and enjoyable to read.
Critical weaknesses
I think the main weakness of this paper is a limited justification on the how and why BroxGD is useful and relevant. I understand that conceptually, BroxGD replaces the projection oracle with an LMO oracle and still enjoys quantitatively similar convergence results to PGD, and this symmetry is what the paper tries to highlight. In fact, that is the part I like about the paper. However, the ball-constrained LMO operation does not seem to be particularly useful or conceptually simpler than projection in general. There is also an additional complication that an admissible radius has to be supplied at each iteration. While the paper seems to honestly acknowledge these points, it is still an intrinsic weakness of the topic.
Regarding the selection of , BroxGD either requires an upper bound on or a backtracking scheme, unlike its popular sister PGD. Achieving the sharp linear convergence rate for smooth and strongly convex problem requires the knowledge of and also , while optimal tuning of ProjGD does not need the last information.
Questions for authors
-
At least for the -smooth convex case, it seems like the requirement of knowing (which is common for PGD) is replaced with the requirement of knowing in BroxGD. There is an interesting correspondence of "Projection LMO", "Step-size Radius", and "-requirement -requirement" between PGD and BroxGD. The order of convergence rate are essentially the same. Do the authors have any clue on whether these can be understood as consequences of a deeper dual relationship?
-
Related to the first point, why does Algorithm 2 initialize the backtracking with ? I think this selection is against the intuition that the -requirement of PGD is replaced with -requirement of BroxGD and makes the backtracking version of BroxGD seem strictly worse than PGD in terms of requirements on the knowledge on the problem.
-
What does the sentence "Freeze the sequence at ." in Theorem 3.4 mean? Is this necessary?
2 comments
Additional response to Reviewer 6hpJ
We would like to add four concrete points about the usefulness and broader implications of the local-oracle viewpoint.
1. Why the local solve can be cheaper: the mechanism behind Section 4.
For correlation matrices, write and . When , the linear minimizer over the unit-diagonal affine space intersected with the local ball is If , this point also solves the full BroxGD subproblem exactly: it minimizes over a larger set and belongs to the smaller feasible set. Crucially, only this candidate must be feasible; the entire local ball need not lie inside the PSD cone. A successful Cholesky factorization provides the numerical feasibility check.
When a projected-gradient candidate is indefinite, the tested projector instead invokes Dykstra iterations involving repeated eigendecompositions. Both methods receive the same affine shortcut when their candidate is feasible. Appendix G.3 measures the cost difference at the same initial point: the median first projection costs approximately 49–54 times the first local solve with accurate projections, and 13-15 times with loose projections. These are per-oracle measurements, separate from the overall speedups reported previously.
Thus radius selection can keep the local candidate in a regime where an exact solve needs only an explicit formula and a feasibility check. The feasibility-GD control also exploits this mechanism; the computational saving is not exclusive to BroxGD. Our convergence theory gives guarantees for specified radius policies, while the experiments identify where the associated local solves are inexpensive.
2. Your proposed stepsize-radius correspondence does have a precise interpretation.
Appendix A.5 compares quadratic regularization of the linear model with a ball constraint. More specifically, let be a local-oracle solution and let be a multiplier for . The optimality condition in Appendix A.6 gives
\operatorname{Proj}_{\mathcal X}\left(x-\frac{\nabla f(x)}{\lambda}\right).$$ Hence $1/\lambda$ is an implicit projected-gradient stepsize associated with the chosen radius. The positivity condition matters: this formula cannot divide by a zero multiplier. Appendix B.7 credits Ferris–Zavriev's earlier projection connection. This penalty-constraint relationship complements the projection onto a separating cut discussed in our first response. It makes the stepsize-radius correspondence mathematically precise, although it does not imply a universal interchangeability of $L$ and $R$. **3. Localization also changes which problems admit a linear oracle.** For any nonempty closed convex $\mathcal X$, feasible center $x$, and finite radius, $\mathcal X\cap\mathbb B(x,t)$ is nonempty and compact. Its linear subproblem therefore attains a solution even when the global LMO is unbounded below (Theorem C.1). Appendix H.3 gives an example on the unbounded PSD cone. If the cost matrix $G$ has a negative eigenvalue, minimizing $\langle G,M\rangle$ over $M\succeq0$ is unbounded below. The local oracle remains well defined. Adding a trace bound to enable a global FW oracle changes the feasible problem. This is a structural benefit of localization, independently of whether its implementation is faster than projection. **4. The framework already yields a new explanation of Frank–Wolfe.** The follow-up [1] derives FW by approximating the BroxGD search region. For compact convex $\mathcal X$ of diameter $D$ and $0\le\gamma\le1$, $$x+\gamma(\mathcal X-x)\subseteq\mathcal X\cap\mathbb B(x,\gamma D).$$ Minimizing the linear model over this contracted set gives exactly the FW update. Section 3 then gives a common convergence proof: FW with $\gamma_k=2/(k+2)$ and exact BroxGD with $t_k=\gamma_kD$ both satisfy $$f(x_K)-f_\star\overset{\text{[1], (27)}}{\le}\frac{2LD^2}{K+2},\qquad K\ge1,$$ under the stated smooth convex assumptions. The same analysis distinguishes the linear-model guarantee preserved by FW from the distance-decrease geometry it can lose. This illustrates how BroxGD provides a framework for deriving and understanding existing algorithms, in addition to suggesting new ones. We would appreciate knowing whether these mechanisms address your concern about usefulness and relevance, and which substantive concern, if any, remains. [1] P. Richtarik and Z. Tovmasyan. *Frank–Wolfe is Approximate Broximal Gradient Descent*, arXiv:2611.02942, 2026.
Response to Reviewer 6hpJ
Thank you for your positive assessment and thoughtful questions.
1. When can the local oracle be useful?
Appendix H develops five application families: fair ranking, matching and transport (H.2); PSD-constrained metric, covariance, precision and kernel learning (H.3); occupancy-measure optimization for reinforcement learning (H.4); robust low-rank learning (H.6); and structured prediction (H.7). It provides exact local formulas under feasibility conditions and master-and-pricing constructions for boundary-active problems. Appendix C.2 gives further closed-form examples.
Section 4 tests correlation matrices: at relative error 10−2, BroxGD beats both projected baselines on all 30 instances, with median speedups of 6.0–7.0× over the faster baseline for accurate projections and 1.9–2.2× for looser ones. Baselines share the affine shortcut; timings include inner work. The feasibility-only GD control is faster on 29 instances but stalls on one. High-accuracy performance is not uniformly favorable. These are problem-dependent benefits, not a universal cost advantage.
2. The connection with projected GD has an exact geometric interpretation.
The paper Local LMO is Secretly a Projection Method! [1] which aleady builds upon our work addresses this question. For convex differentiable f on a nonempty closed convex feasible set with an attained minimum, take a nonoptimal x and
0<t≤∣∣∇f(x)∣∣f(x)−f⋆.
If y is the BroxGD update, define H={z:⟨∇f(x),z−y⟩≤0}. Theorem 2 of [1] establishes
\operatorname{Proj}_{\mathcal X\cap H}(x).$$ The half-space excludes $x$ and contains every minimizer. Thus **BroxGD is itself a gradient-based projection method, with this projection computed through a local LMO**. The projection is onto a localized feasible set, rather than the usual projected-GD operation on a gradient-shifted point. This explains the distance-decrease geometry under the stated radius condition, rather than positing a general duality. Here “projection-free” concerns the oracle used to compute the step, not the absence of a projection interpretation. **3. Why initialize Algorithm 2 with $t=||a_k||/L$?** The $L$-versus-$R$ correspondence concerns Theorem 3.2(ii): its fixed-horizon rule uses $R$ and $K$, but no knowledge of $L$. Algorithm 2 deliberately offers a different tradeoff: it uses $L$, but **needs neither $R$, $f^\star$, nor $\mu$**, and its radius policy does not depend on the final horizon. Table 1 distinguishes these requirements. Without constraints, the local solve at this radius gives $y=x_k-a_k/L$: exactly the usual GD step. It satisfies the acceptance test $-\langle a_k,y-x_k\rangle\ge L||y-x_k||^2$ with equality. With constraints, shrinking the radius until that test holds certifies objective decrease. This scale also yields the multiplier bound in Theorem D.4. Compared with known-$L$ projected GD, this variant requires no additional solution-distance information to run. Its convex rate assumes bounded distance to the solution set along the accepted trajectory, but that bound is not an input. Accepted steps may require multiple oracle calls, as stated in Theorem 3.3. **4. The sharp linear rate is a benchmark, not the only linear guarantee.** Theorem 3.4 is explicitly a solution-dependent benchmark (Section 3.4). The implementable alternative, Theorem 3.3, gives $$\Delta_K\overset{\text{(18)}}{\le} (1+\xi^2\mu/L)^{-K}\Delta_0.$$ For fixed $\xi$, this has the same order of condition-number dependence as projected GD, without knowing $\mu$ or any solution distance to select radii. Here $K$ counts accepted steps. Theorem D.3 also provides predetermined geometric radii from certified initial bounds. The benchmarks complement practical guarantees and can guide future rules. **5. What does “Freeze the sequence at $x^\star$” mean? Is it necessary?** Once an iterate reaches $x^\star$, subsequent iterates remain there, so the bound applies for every $K$. In Theorem 3.4, this convention is redundant: the prescribed radius is proportional to $||x_k-x^\star||$, so it becomes zero at the solution. The local feasible set then contains only $x^\star$, and the update stays there automatically. No extra stopping test or knowledge is needed beyond the theorem's already solution-dependent radius. [1] Richtarik and Mahran. *Local LMO is Secretly a Projection Method!* arXiv:2609.33383, 2026. https://arxiv.org/abs/2609.33383