Parameter-free projected gradient descent

Understand

We consider the problem of minimizing a convex function over a closed convex set, with Projected Gradient Descent (PGD).

• We propose a fully parameter-free version of AdaGrad, which is adaptive to the distance between the initialization and the optimum, and to the sum of the square norm of the subgradients.
• Our algorithm is able to handle projection steps, does not involve restarts, reweighing along the trajectory or additional gradient evaluations compared to the classical PGD.
• It also fulfills optimal rates of convergence for cumulative regret up to logarithmic factors.