Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method

The extragradient method for finding saddle points and other problems

G. M. Korpelevich · 1977

Earlier work this paper cites.

Problem complexity and method efficiency in optimization

Arkadii Nemirovskii and David Borisovich Yudin · 1983

Earlier work this paper cites.

A method of solving a convex programming problem with convergence rate O ⁡ ( 1 / k 2 ) O(1/k^{2})

Yurii Nesterov · 1983

Earlier work this paper cites.

Optimal methods of smooth convex minimization

Arkadi S Nemirovski and Yurii Evgen’evich Nesterov · 1985

Earlier work this paper cites.

Solving Ordinary Differential Equations I (2nd Revised. Ed.): Nonstiff Problems

E Hairer, SP Nørsett, and G Wanner · 1993

Earlier work this paper cites.

Lectures on modern convex optimization: Analysis, algorithms, and engineering applications

Aharon Ben-Tal and Arkadi Nemirovski · 2001

Earlier work this paper cites.

Prox-method with rate of convergence O ⁡ ( 1 / t ) O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems

Arkadi Nemirovski · 2004

Earlier work this paper cites.

Introductory Lectures on Convex Programming Volume: A Basic course

Yurii Nesterov · 2004

Earlier work this paper cites.

Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

Daniel A. Spielman and Shang-Hua Teng · 2004

Earlier work this paper cites.

Excessive gap technique in nonsmooth convex minimization

Yurii Nesterov · 2005

Earlier work this paper cites.

Smooth minimization of non-smooth functions

Yurii Nesterov · 2005

Earlier work this paper cites.

Accelerating the cubic regularization of Newton’s method on convex problems

Yurii Nesterov · 2008

Cited alongside, same era.

On accelerated proximal gradient methods for convex-concave optimization, 2008

Paul Tseng · 2008

Cited alongside, same era.

QIP = PSPACE

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous · 2011

Cited alongside, same era.

An optimal method for stochastic composite optimization

Guanghui Lan · 2011

Cited alongside, same era.

A simple, combinatorial algorithm for solving SDD systems in nearly-Linear time

Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu · 2013

Cited alongside, same era.

A new approach to computing maximum flows using electrical flows

Yin Tat Lee, Satish Rao, and Nikhil Srivastava · 2013

Cited alongside, same era.

First-order methods of smooth convex optimization with inexact oracle

Olivier Devolder, François Glineur, and Yurii Nesterov · 2014

Later among the works it cites.

Robustness vs acceleration, 2014

Moritz Hardt · 2014

Later among the works it cites.

An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations

Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford · 2014

Later among the works it cites.

A differential equation for modeling nesterov’s accelerated gradient method: Theory and insights

Weijie Su, Stephen Boyd, and Emmanuel Candes · 2014

Later among the works it cites.

A geometric alternative to Nesterov’s accelerated gradient descent

Original

Sébastien Bubeck, Yin Tat Lee, and Mohit Singh · 2015

Later among the works it cites.