Title: Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method,
Abstract: We provide a novel accelerated first-order method that achieves the
asymptotically optimal convergence rate for smooth functions in the first-order
oracle model. To this day, Nesterov's Accelerated Gradient Descent (AGD) and
variations thereof were the only methods achieving acceleration in this
standard blackbox model. In contrast, our algorithm is significantly different
from AGD, as it relies on a predictor-corrector approach similar to that used
by Mirror-Prox [Nemirovski, 2004] and Extra-Gradient Descent [Korpelevich,
1977] in the solution of convex-concave saddle point problems. For this reason,
we dub our algorithm Accelerated Extra-Gradient Descent (AXGD). Its
construction is motivated by the discretization of an accelerated
continuous-time dynamics [Krichene et al., 2015] using the classical method of
implicit Euler discretization. Our analysis explicitly shows the effects of
discretization through a conceptually novel primal-dual viewpoint. Moreover, we
show that the method is quite general: it attains optimal convergence rates for
other classes of objectives (e.g., those with generalized smoothness properties
or that are non-smooth and Lipschitz-continuous) using the appropriate choices
of step lengths. Finally, we present experiments showing that our algorithm
matches the performance of Nesterov's method, while appearing more robust to
noise in some cases.