pipette
ENEnglish

An Adaptive Short-Step Variant of BroxGD with Linear Convergence under Quadratic Growth

Jan Niklas Kolzenburg, Peter Richt\'arik

Preprint

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.

Resultado principalLimitación que admiten los autores

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 37 pages, 1 figure, 2 tables