Accelerating the Fast Gradient Method

Ross Drummond, Stephen Duncan

Published 2018-05-23Version 1

A set of accelerated first order optimisation algorithms for minimising strictly convex functions are proposed. Using only gradient information, these algorithms can achieve a worst-case convergence rate proportional to $ 1-\left(\frac{\mu}{L}\right)^{1/N}$ for $N = 1, 2, 3, \dots$ and can exceed that of the fast gradient method. However, the improvement in the rate of convergence comes at the expense of a loss of robustness. Robustness is recovered by using an adaptive restarting controller that guarantees iterate convergences and recovers the faster convergence rates.