growth condition – Optimization Online

A Parameter-Free Restart Scheme with Only a Parallelizable $\log\log(1/\epsilon)$ Overhead

Published: 2026/05/30

Convex Optimization, Nonsmooth Optimization convergence rates, first-order methods, growth condition, restart

It is well-known that first-order methods can offer accelerated convergence rates in the presence of growth structures. Restarting schemes provide a general tool for such speed-ups. These schemes typically either require unrealistic problem knowledge, incur logarithmic overhead factors in oracle complexity, and/or have a nontrivial initial burn-in phase. We present a parameter-free approach for restarting … Read more

Affine invariant convergence rates of the conditional gradient method

Published: 2021/12/29

Javier F. Peña

Convex Optimization affine invariance, conditional gradient, convergence rates, growth condition

We show that the conditional gradient method for the convex composite problem \[\min_x\{f(x) + \Psi(x)\}\] generates primal and dual iterates with a duality gap converging to zero provided a suitable growth property holds and the algorithm makes a judicious choice of stepsizes. The rate of convergence of the duality gap to zero ranges from sublinear … Read more