Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent
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 𝔹(xk,tk) centered at the current iterate xk, of suitable radius tk>0: xk+1∈argminz∈𝒳∩𝔹(xk,tk)⟨∇ f(xk),z⟩. 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.
Related
- Frank-Wolfe is Approximate Broximal Gradient Descent
- Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size
- A projected descent method for minimization of weakly semismooth functions over polyhedral sets
- A Safeguarded Projected-Gradient Framework for Complementarity Constrained Least Squares Problems
- An Adaptive Projected-Gradient Algorithm for Sample-Average Approximations of Stochastic Multi-Objective Optimization
BibTeX
@misc{richtarik2026broximal,
title = {{Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent}},
author = {Peter Richtárik and Kaja Gruntkowska and Hanmin Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.08850},
eprint = {2605.08850},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.08850},
note = {CC0},
}
RIS
TY - UNPB
TI - Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent
AU - Peter Richtárik
AU - Kaja Gruntkowska
AU - Hanmin Li
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2605.08850
UR - https://arxiv.org/abs/2605.08850
AB - 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 𝔹(x_k,t_k) centered at the current iterate x_k, of suitable radius t_k>0: x_k+1∈argmin_z∈𝒳∩𝔹(x_k,t_k)⟨∇ f(x_k),z⟩. 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.
ER -