acceptodds
Under review as a conference paper at ICLR 2027

Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descen

20 views

Abstract

We propose Broximal Gradient Descent (BroxGD), a projection-free sister method to projected gradient descent for constrained optimization. Its forward–backward construction replaces the proximal backward operation by the broximal operation of Gruntkowska et al (2025). Instead of projecting, each step minimizes a linear function over the intersection of the constraint set and a ball centered at the current iterate , of suitable radius : We develop a comprehensive convergence theory spanning a wide range of optimization regimes and radius rules. We expect BroxGD to find many applications and inspire numerous extensions, much like projected gradient descent. Our contribution is theoretical; potential applications and toy experiments illustrate the method and suggest directions for future work.

Primary area:
optimization
Keywords:
Constrained Optimization, linear minimization oracle

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_6hpJOpenReview ↗
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 tkt_k 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 tkt_k, BroxGD either requires an upper bound RR on ∣x0−x⋆∣\\|x_0 - x_\star\\| 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 L,μL, \mu and also ∣xk−x⋆∣\\|x_k - x_\star\\|, while optimal tuning of ProjGD does not need the last information.

Questions for authors
  • At least for the LL-smooth convex case, it seems like the requirement of knowing LL (which is common for PGD) is replaced with the requirement of knowing RR in BroxGD. There is an interesting correspondence of "Projection ↔\leftrightarrow LMO", "Step-size ↔\leftrightarrow Radius", and "LL-requirement ↔\leftrightarrow RR-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 t=∣ak∣/Lt = \\|a_k\\| / L? I think this selection is against the intuition that the LL-requirement of PGD is replaced with RR-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 x⋆x_\star." in Theorem 3.4 mean? Is this necessary?

2 comments
AuthorsOpenReview ↗

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−210^{-2}, BroxGD beats both projected baselines on all 30 instances, with median speedups of 6.06.0–7.0×7.0\times over the faster baseline for accurate projections and 1.91.9–2.2×2.2\times 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 ff on a nonempty closed convex feasible set with an attained minimum, take a nonoptimal xx and

0<t≤f(x)−f⋆∣∣∇f(x)∣∣.0<t\le\frac{f(x)-f^\star}{||\nabla f(x)||}.

If yy is the BroxGD update, define H={z:⟨∇f(x),z−y⟩≤0}H=\lbrace z:\langle\nabla f(x),z-y\rangle\le0\rbrace. 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
AuthorsOpenReview ↗

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 G=∇f(X)G=\nabla f(X) and H=G−Diag⁡(diag⁡(G))H=G-\operatorname{Diag}(\operatorname{diag}(G)). When H≠0H\ne0, the linear minimizer over the unit-diagonal affine space intersected with the local ball is X+=(187)X−tH∣∣H∣∣F.X^+\overset{\text{(187)}}{=}X-t\frac{H}{||H||_F}. If X+⪰0X^+\succeq0, 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 yy be a local-oracle solution and let λ>0\lambda>0 be a multiplier for (∣∣y−x∣∣2−t2)/2≤0(||y-x||^2-t^2)/2\le0. 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.
Reviewer_1DEgOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes a family of descent methods, named Broximal Gradient Descent, that have roots in both the recerntly proposed Broximal Point method framework and in trust-region methods.

In fact, as aknowledged by the authors themselves in Section 1.4, their method is a trust-region method with a zero approximation of the Hessian.

The interesting part is the convergence guarantee, and the sligthly different acceptance criteria for a new iterate in the backtracking variants.

I am not very worried about the limited experiments, since this is mainly a theoretical paper to build a future upon, and not a claim of a new SOTA optimizer. It's an initial analysis that may lead to such, but is not in itself a practical SOTA optimizer method.

Critical strengths
  1. Very clear writing, no excees use of a huge number of symbols, concepts, letters, or indices. Bravo - something rare to see at ICLR!
  2. Novel analysis of trust-region-like methos with a new backtracking rule (Algorithm 2).
  3. Clear positioning providing insights about the method as an "in-between" alternative between Frank Wolfe and Projected Gradient Descent.
Critical weaknesses
  1. Limited experiments. This is not a major weakness, since the contribution is mainly theoretical
  2. Missing derivation of closed-form iterates for interesting constraint sets (something that Frank-Wolfe is known for - efficient LMOs, when projections are expensive). The practical usefulness of the method stems from ability to cheaply compute the oracle.
Questions for authors

NA

1 comment
AuthorsOpenReview ↗

Response to Reviewer 1DEg

Thank you for your positive assessment, especially your comments on the exposition, the backtracking analysis, and the positioning between projected gradient descent and Frank-Wolfe. We agree that the cost of the local oracle is central to practical usefulness. The submitted paper already contains explicit oracle formulas and application-specific constructions that address this concern.

1. Closed-form oracle examples are already given in Appendix C.2.

Appendix C.2, entitled “Examples of feasible sets admitting a closed-form broximal gradient step,” provides explicit solutions for the whole space, singletons, affine subspaces and hyperplanes, affine lines, rays, line segments, Euclidean balls, and slabs between parallel hyperplanes.

For example, for X=a+V\mathcal X=a+V, the exact update is

xk+1=xk−tkPV∇f(xk)∣∣PV∇f(xk)∣∣,x_{k+1}=x_k-t_k\frac{P_V\nabla f(x_k)}{||P_V\nabla f(x_k)||},

when the denominator is nonzero, where PVP_V is the orthogonal projector onto the linear subspace VV. Otherwise, one may retain xkx_k. Appendix C.8 formalizes this oracle and its connection to gradient descent on the affine space.

The examples also cover active constraints: the Euclidean-ball case treats the intersection of the two balls, including when both boundaries are active; the slab case gives the optimizer on the appropriate ball–hyperplane cross-section when the unconstrained ball minimizer violates the slab. Thus the examples are not confined to cases where the additional constraints can be ignored.

2. Appendix H develops applications and the corresponding oracle implementations.

It covers five families:

  • H.2: fair ranking, differentiable matching, and nonlinear transport;
  • H.3: PSD-constrained metric, covariance, precision, and kernel learning;
  • H.4: occupancy measures for safe, fair, exploratory, or imitation reinforcement learning;
  • H.6: robust low-rank learning over a nuclear-norm ball;
  • H.7: structured prediction over large products of simplices.

These sections provide concrete mathematical models, implementation formulas or constructions, and their limitations. Proposition H.1 gives an exact normalized tangent-gradient update when explicit local feasibility conditions hold. For ordinary doubly stochastic matrices, H.2 computes this direction by double-centering the gradient, at O(n2)O(n^2) cost beyond gradient evaluation, under the stated nonnegativity-slack condition. The PSD and occupancy-measure examples give analogous feasibility certificates and discuss their computational cost.

For boundary-active problems, H.5–H.7 develop a different approach: a restricted master problem plus atomic pricing, with Proposition H.2 certifying when the result solves the full local oracle exactly. These are implementation routes, not claims of closed-form solutions or uniformly cheap inner solves. In particular, clipping a prescribed radius to an interior-feasibility bound does not automatically preserve its convergence guarantee.

3. The experiments illustrate a useful regime while retaining the theoretical scope.

Section 4 studies correlation matrices, where an affine-ball solution is an exact local-oracle output whenever its PSD feasibility is certified. At relative objective error 10−210^{-2}, BroxGD beats both tested projected baselines on all 30 instances. Median speedups over the faster baseline are 6.06.0–7.0×7.0\times with accurate projections and 1.91.9–2.2×2.2\times with looser projections. The projected baselines receive the same affine shortcut, and timings include inner work.

The paper also reports the limitations: a feasibility-only GD control is faster on 29 instances but stalls on one, and higher-accuracy performance is not uniformly favorable. Appendix G contains broader synthetic studies, including unfavorable regimes; the potential downstream applications in Appendix H are not presented as established application-level successes.

4. The framework also sheds new light on Frank–Wolfe.

Recent work already building upon our paper [1] derives FW as an approximation of BroxGD. For a compact convex set of diameter DD, replace the local region X∩B(x,γD)\mathcal X\cap\mathbb B(x,\gamma D) by its subset x+γ(X−x)x+\gamma(\mathcal X-x). Minimizing the linear model over this contracted set gives exactly the FW update. The paper derives the classical O(1/K)O(1/K) last-iterate rate for both methods through a common proof, and shows how FW can lose the distance-decrease geometry of the exact BroxGD step. This is a new interpretation of a classical method, illustrating the explanatory value of our BroxGD framework beyond designing another optimizer.

[1] P. Richtarik and Z. Tovmasyan. Frank–Wolfe is Approximate Broximal Gradient Descent. arXiv:2611.02942, 2026. https://arxiv.org/abs/2611.02942

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

This paper proposes broximal gradient descent method for constrained optimization. In each step, the update solves a linear minimization problem function over the intersection of the constraint set and a ball centered at the current iterate, where can be understood as adding a ball constraint in the Frank–Wolfe method. A comprehensive convergence theory is developed under a wide range of optimization regimes and radius rules.

Critical strengths

Thorough comparison between the proposed method and two classes of classic methods: projected gradient descent and Frank–Wolfe are discussed. These discussions make the design of the algorithm and the convergence results convincing and easy to follow. For the construction of the algorithm, the broximal gradient descent method takes the projection-free advantage of Frank–Wolfe from considering a linear minimization problem similar to Frank–Wolfe. Without constraint, the broximal gradient descent method reduces to a special case of gradient descent. In this point of view, the broximal gradient descent method achieves comparable convergence rates as projected gradient descent in several cases.

Critical weaknesses

Most extended convergence results compared with Frank-Wolfe lack practical radius rules.

Questions for authors

Each step the Broximal gradient descent method solves a strengthened constrained problem (with an addtional ball constraint) compared with Frank–Wolfe. Therefore, my understanding is that the convergence rate of the Broximal gradient descent should be at least as good as Frank–Wolfe. For LL-smooth and convex objective with fixed horizon, why the Broximal gradient descent method only achieve (1/K)\mathcal(1/K) convergence on function gap for the best iterate, while Frank–Wolfe obtain the same rate for the last iterate?

1 comment
AuthorsOpenReview ↗

Response to Reviewer FoyD

Thank you for your positive assessment and thoughtful questions. We clarify the practical radius rules and the best-iterate versus last-iterate guarantees below.

1. Practical radius rules are already provided in Table 1.

Group A of Table 1 is entitled “Practical objective guarantees: fixed schedules, then backtracking.” Its “Practical radius” column and footnotes (i)–(j) specify the information required:

  • Theorem 3.2: practical fixed-horizon guarantees for bounded-gradient convex and smooth convex objectives. In the smooth case, tk=R/Kt_k=R/\sqrt K, where RR bounds the initial solution distance. Selecting the radius requires no knowledge of LL.
  • Algorithm 2 and Theorem 3.3: observable backtracking giving last-iterate O(1/K)O(1/K) convergence under the stated convex assumptions and linear convergence under strong convexity. The algorithm uses LL, but neither a solution-distance bound, the optimal objective value, nor the strong-convexity parameter.
  • Theorem D.3: predetermined geometric radii giving linear objective convergence from certified bounds on L,μL,\mu, and the initial objective gap, without knowing the current solution distance or optimality gap.

We deliberately also include solution-dependent rules. They reveal behavior attainable through localization, illuminate differences from other optimization methods, and provide benchmarks that may guide future practical rules. For example, Theorem 3.4 matches the sharp distance contraction of optimally tuned projected gradient descent, while Theorem 3.3 supplies an implementable linear-rate alternative. Section 3.4 explains this distinction.

2. The paper already proves last-iterate convergence.

The best-iterate result in your question concerns the particular constant-radius policy in Theorem 3.2(ii). Theorem 3.3, “Practical backtracking and last-iterate rates,” establishes, for globally convex, LL-smooth objectives,

\frac{\max\lbrace \Delta_0,4LR_{\mathrm{lev}}^2/\xi^2\rbrace}{K+1},$$ where $\Delta_0=f(x_0)-f^\star$, $\xi\in(0,1)$ is the contraction factor, and accepted iterates satisfy $\operatorname{dist}(x_k,\mathcal X^\star)\le R_{\mathrm{lev}}$. On compact feasible sets, as in the classical FW comparison, this condition holds automatically with $R_{\mathrm{lev}}=\operatorname{diam}\mathcal X$. The condition also allows unbounded sets. Here $K$ counts accepted steps; rejected trials cost additional oracle calls. Theorem 3.2(ii) offers a different tradeoff: a budget of $K$ local-oracle calls, no backtracking, no knowledge of $L$ to choose the radius, and no boundedness requirement on the feasible set, with $$\min_{0\le k\le K}(f(x_k)-f^\star) \overset{\text{(15)}}{\le}\frac{LR^2}{2K}.$$ **Why the best iterate?** Set $\varepsilon=Lt^2/2$. The proof in Appendix D.1.2 shows that whenever the next iterate has error greater than $\varepsilon$, its squared distance to a solution decreases by at least $t^2$. If every iterate missed the target, summing would exhaust the initial squared distance within the stated budget. Hence an accurate iterate must occur. However, the constant radius does not enforce objective descent: later steps may increase the objective. Returning the best observed iterate retains the guarantee without knowing $f^\star$. Algorithm 2 instead enforces sufficient decrease and supports a last-iterate proof. **3. The connection you suggest is already formalized by a recent follow-up to our paper.** Your intuition has a precise interpretation in [1], which derives **Frank–Wolfe as an approximation of BroxGD**. For compact convex $\mathcal X$ of diameter $D$, the contracted set $x+\gamma(\mathcal X-x)$ lies inside the BroxGD region $\mathcal X\cap\mathbb B(x,\gamma D)$. Minimizing the linear model over this smaller set gives exactly the FW update. Thus the connection is more specific than adding a constraint to the global oracle: FW replaces the BroxGD search region by an inner approximation. Section 3 of [1] establishes a common convergence proof. FW with $\gamma_k=2/(k+2)$ and exact BroxGD with $t_k=\gamma_kD$ both satisfy the **last-iterate** guarantee $$f(x_K)-f^\star\overset{\text{[1], Eq. (27)}}{\le} \frac{2LD^2}{K+2},\qquad K\ge1.$$ Hence BroxGD recovers the classical diameter-dependent last-iterate guarantee under matched schedules. Theorem 3.2 instead studies a different policy providing a diameter-free, fixed-budget guarantee. The distinction is between radius policies and their guarantees, not an inherent best-iterate limitation of BroxGD. [1] P. Richtarik and Z. Tovmasyan. *Frank–Wolfe is Approximate Broximal Gradient Descent*. arXiv:2611.02942, 2026. https://arxiv.org/abs/2611.02942

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.