An Adaptive Short-Step Variant of BroxGD with Linear Convergence under Quadratic Growth
En palabras de los autores
Broximal Gradient Descent (BroxGD), recently analyzed by Richt\'arik et al. (arXiv:2605.08850v1), is a projection-free sister method to Projected Gradient Descent (ProjGD) for solving , where and is nonempty, closed and convex. The method performs local linear minimization over the feasible set intersected with a Euclidean ball and carefully prescribed radius. Like ProjGD, BroxGD enjoys linear convergence in the smooth strongly convex setting, with the same condition-number dependence. However, the known radius rule leading to linear convergence requires unavailable information and is therefore impractical. We develop an adaptive short-step variant of BroxGD which converges linearly for smooth convex functions under quadratic growth (generalizing strong convexity), without requiring unavailable information. We use where is the smoothness constant of , is the Euclidean ball centered at of radius , and is the line segment connecting and . The radius is updated by . Projection onto requires only scalar clipping. Assuming an exact local linear minimization oracle, each update uses one oracle call. For any positive initial radius, we bound all oracle calls to reach objective error at most and obtain for fixed initialization, where and is the quadratic-growth constant.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 37 pages, 1 figure, 2 tables