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

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 X and a ball mathbbB(xk,tk) centered at the current iterate xk, of suitable radius tk>0: [ xk+1∈argmin_z∈XcapmathbbB(xk,tk)langlenabla f(xk),zrangle. ] 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.