arXiv:1706.04680v2 [math.OC] 10 Feb 2018

Accelerated Extra-Gradient Descent:
A Novel Accelerated First-Order Method∗
Jelena Diakonikolas and Lorenzo Orecchia
Computer Science Department, Boston University
email: {jelenad, orecchia}@bu.edu

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 [18] and Extra-Gradient
Descent [14] 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 [15]
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.

1

Introduction

First-order methods for convex optimization have come to play an important role in the design of
algorithms and in Theoretical Computer Science in general, with applications including numerical
methods [13, 30], graph algorithms [12, 29], submodular optimization [8] and complexity theory [11].
A classical setting for convex optimization is that of smooth optimization, i.e., minimizing a convex
differentiable function f over a convex set X ⊆ Rn , with the smoothness assumption that the gradient of
f be L-Lipschitz continuous1 for some positive real L, i.e.:
∀ x, y ∈ X, k∇f (x) − ∇f (y)k∗ ≤ L · kx − yk.
In this setting, it is also assumed that the algorithm can access the input function f only via queries to a
first-order oracle, i.e., a blackbox that on input x ∈ X, returns the vector ∇f (x) in constant time.2
∗
Part of this work was done while the authors were visiting the Simons Institute for the Theory of Computing. It was
partially supported by NSF grant #CCF-1718342 and by the DIMACS/Simons Collaboration on Bridging Continuous and
Discrete Optimization through NSF grant #CCF-1740425.
1
Lipschitz continuity is defined w.r.t to a pair of dual norms k · k, k · k∗ . At a first reading, these can be taken as k · k2 .
2
In general, we may assume that the blackbox also returns the function value f (x). However, for the general class of
problems we consider this information is not necessary and the gradient suffices [28]. For intuition about this, see the
expression for the change in duality gap in Equation 2.4.

1

Smooth optimization is of particular interest because it is the simplest setting in which the phenomenon
of acceleration arises, i.e., the optimal algorithms in the blackbox model achieve an error that scales
as O(1/t2 ), where t is the number of queries [22]. This should be compared to the convergence of
steepest-descent methods, which attempt to locally minimize the first-order approximation to the function
and only yield O(1/t)-convergence [3, 28]. Acceleration has proved an active topic of algorithmic research,
both for the promise of obtaining generic speed-ups for problems having some smoothness condition
and for the unintuitive nature of the fact that faster algorithms can be obtained by not moving in the
direction of steepest-descent.
Recently, a number of papers have helped demystify the concept behind accelerated algorithms by
providing interpretations based on continuous dynamics and their discretization [15, 31, 33], geometric
ideas [5], and on trading off the performances of two slower first-order methods [1]. Despite these efforts,
to this day, Nesterov’s Accelerated Gradient Descent (agd) methods remain the only paradigm [22, 23]
through which to obtain accelerated algorithms in the blackbox model and in related settings, where all
existing accelerated algorithms are variations of Nesterov’s general method [32].
Our Main Contributions We present a novel accelerated first-order method that achieves the optimal
convergence rate for smooth functions and is significantly different from Nesterov’s method, as it relies
on a predictor-corrector approach, similar to that of Mirror-Prox [18] and Extra-Gradient Descent [14].
For this reason, we name our method Accelerated Extra-Gradient Descent (axgd). Our derivation of
the axgd algorithm is based on the discretization of a recently proposed continuous-time accelerated
algorithm [15,33]. The continuous-time view is particularly helpful in clarifying the relation between agd,
axgd, and Mirror-Prox. Following [15], given a gradient field ∇f and a prox function ψ, it is possible to
define two continuous-time evolutions: the mirror-descent dynamics and the accelerated-mirror-descent
dynamics (see Section 2.2). With this setup, Nesterov’s agd can be seen as a variant of the classical
forward-Euler discretization applied to the accelerated-mirror-descent dynamics. In contrast, MirrorProx and extra-gradient methods arise from an approximate backward-Euler discretization [9] on the
mirror-descent dynamics. Finally, our algorithm axgd is the result of an approximate backward-Euler
discretization of the accelerated mirror-descent dynamics.
Another conceptual contribution of our paper is the application of a primal-dual viewpoint on the
convergence of first-order methods, both in continuous and discrete time. At every time instant t, our
algorithm explicitly maintains a current primal solution x(t) and a current dual solution z(t) , the latter in
the form of a convex combination of gradients of the convex objective, i.e., a lower-bounding hyperplane.
This primal-dual pair of solutions yields, for every t, both an upper bound Ut and a lower bound Lt on
the optimum: Ut ≥ f (x∗ ) ≥ Lt . In all cases, we obtain convergence bounds by explicitly quantifying the
rate at which the duality gap Gt = Ut − Lt goes to zero. We believe that this primal-dual viewpoint
makes the analysis and design of first-order methods easier to carry out. We provide its application
to proving other classical results in first-order methods, including Mirror Descent, Mirror-Prox, and
Frank-Wolfe algorithms in the upcoming manuscript [7].
Other Technical Contributions In Section 2.6, we provide a unified convergence proof for standard
smooth functions (as defined above) and for functions with Hölder-continuous gradients, a more general
notion of smoothness [20]. While this paper focuses on the standard smooth setup, the same techniques
easily yield results matching those of agd methods for the strongly-convex-and-smooth case. Indeed,
it is possible to prove that our method is universal, in the sense of Nesterov [21], meaning that it can
be composed with a line-search algorithm to yield near-optimal algorithms even when the smoothness
parameters of the functions are unknown. We illustrate this phenomenon by showing that (axgd) also
achieves the optimal rate for the optimization of Lipschitz-continuous convex functions, a non-smooth
problem.

2

Finally, we present a suite of experiments comparing agd, axgd, and standard gradient methods,
showing that the performance of axgd closely matches that of agd methods. We also explore the
empirical performance of axgd in the practically and theoretically relevant case in which the queried
gradients are corrupted by noise. We show that axgd exhibits better stability properties than agd in
some cases, leading to a number of interesting theoretical questions on the convergence of axgd.

1.1

Related Work

In his seminal work [22, 23], Nesterov gave a method for the minimization of convex functions that are
smooth with respect to the Euclidean norm, where the function is accessed through a first-order oracle.
Nesterov’s method converges quadratically faster than gradient descent, at a rate of O( t12 ), which has
been shown to be asymptotically optimal [23] for smooth functions in this standard blackbox model [28].
More recently, Nesterov generalized this method to allow non-Euclidean norms in the definition of
smoothness [25]. We refer to this generalization of Nesterov’s method and to instantiations thereof as agd
methods. Accelerated gradient methods have been widely extended and modified for different settings,
including composite optimization [16, 27], cubic regularization [26], and universal methods [21]. They
have also found a number of fundamental applications in many algorithmic areas, including machine
learning (see [4]) and discrete optimization [17].
An important application of agd methods concerns the solution of various convex-concave saddle
point problems. While these are examples of non-smooth problems, for which the optimal rate is known
to be Ω( √1k ) [20], Nesterov showed that the saddle-point structure can be exploited by smoothing the
original problem and applying agd methods on the resulting smooth function [25]. This approach [24, 25]
yields an O( k1 )-convergence for convex-concave saddle point problems with smooth gradients. Surprisingly,
at around the same time, Nemirovski [18] gave a very different algorithm, known as Mirror-Prox, which
achieves the same complexity for the saddle point problem. Mirror-Prox does not rely on the algorithm
or analysis underlying agd, but is based instead on the idea of an extra-gradient step, i.e., a correction
step that is performed at every iteration to speed up convergence. Mirror-Prox can be viewed as an
approximate solution to the implicit Euler discretization of the standard mirror descent dynamics of
Nemirovski and Yudin [20]. In this fashion, our axgd algorithm resembles Mirror-Prox as it also makes
use of an approximate implicit Euler step to discretize a different, accelerated dynamic.
A number of interpretations have been proposed to explain the phenomenon of acceleration in
first-order methods. Tseng gives a formal framework that unifies all the different instantiations of
agd methods [32]. More recently, Allen-Zhu and Orecchia [1] cast agd methods as the result of coupling
mirror descent and gradient descent steps. Bubeck et al. give an elegant geometric interpretation of the
Euclidean instantiation of Nesterov’s method [5]. At the same time, Su et al. [31], Krichene et al. [15], and
Wibisono et al. [33] have provided characterizations of accelerated methods as discretizations of certain
families of ODEs related to the gradient flow of the objective f. Our algorithm is strongly influenced
by these works: in particular, the starting point for the derivation of axgd is the continuous-time
accelerated-mirror-descent (amd) dynamics [15].

1.2

Preliminaries

We focus on continuous and differentiable functions defined on a closed convex set X ⊆ Rn . We assume
that there is an arbitrary (but fixed) norm k · k associated with the space, and all the statements about
function properties are stated with respect to that norm. We also define the dual norm k · k∗ in the
standard way: kzk∗ = sup{hz, xi : kxk = 1}. The following definitions will be useful in our analysis, and
thus we state them here for completeness.
Definition 1.1. A function f : X → R is convex on X, if for all x, x̂ ∈ X: f (x̂) ≥ f (x) + h∇f (x), x̂ − xi.

3

Definition 1.2. A function f : X → R is smooth on X with smoothness parameter L and with respect
to a norm k · k, if for all x, x̂ ∈ X: f (x̂) ≤ f (x) + h∇f (x), x̂ − xi + L2 kx̂ − xk2 .
Definition 1.2 can equivalently be stated as: k∇f (x) − ∇f (x̂)k∗ ≤ Lkx − x̂k.
Definition 1.3. A function f : X → R is strongly convex on X with strong convexity parameter σ and
with respect to a norm k · k, if for all x, x̂ ∈ X: f (x̂) ≥ f (x) + h∇f (x), x̂ − xi + σ2 kx̂ − xk2 .
def

Definition 1.4. (Bregman Divergence) Dψ (x, x̂) = ψ(x) − ψ(x̂) − h∇ψ(x̂), x − x̂i.
Definition 1.5. (Convex Conjugate) Function ψ ∗ is the convex conjugate of ψ : X → R, if ψ ∗ (z) =
maxx∈X {hz, xi − ψ(x)}, ∀z ∈ R.
In the rest of the paper, we will assume that ψ(x) is continuously differentiable, so that FenchelMoreau Theorem implies that ψ ∗∗ = ψ.3 We are interested in minimizing a convex function f over
X ⊆ Rn . We let x∗ = arg minx∈X f (x).
We will refer to any step that decreases the value of f as a gradient descent step. In the special
case of a smooth function f the gradient descent step from a point x ∈ X will be given as Grad(x) =
arg minx̂∈X {f (x) + h∇f (x), x̂ − xi + L2 kx̂ − xk2 }.
We will assume that there is a strongly-convex differentiable function ψ : X → R such that
maxx∈X {hz, xi − ψ(x)} is easily solvable, possibly in a closed form. Notice that this problem defines the convex conjugate of ψ(·), i.e., ψ ∗ (z) = maxx∈X {hz, xi − ψ(x)}. The following standard fact will
be extremely useful in carrying out the analysis of the algorithms in this paper.
Fact 1.6. Let ψ : X → R be a differentiable strongly-convex function. Then:
∇ψ ∗ (z) = arg max {hz, xi − ψ(x)} .
x∈X

Additional useful properties of Bregman divergence are provided in Appendix A.

2

Accelerated Extra-Gradient Descent

In this section, we describe the axgd method and analyze its convergence. For comparison, steps of
agd and axgd are shown next to each other in the box below. In continuous time, both algorithms
follow the same dynamics. However, due to the different discretization methods used in constructing
agd and axgd, they follow different discrete-time updates. In particular, we show in [7] that agd can
be interpreted as performing explicit (forward) Euler discretization plus a gradient step to correct the
discretization error. In contrast, axgd uses an approximate implementation of implicit (backward) Euler
discretization to directly control the discretization error.
Accelerated Gradient Descent (agd)

(k+1)

x

Accelerated Extra-Gradient Descent (axgd)
x̂(k) =

Ak (k)
ak+1
=
x̂ +
∇ψ ∗ (z(k) ),
Ak+1
Ak+1

z(k+1) = z(k) − ak+1 ∇f (x(k+1) ),

Ak (k)
ak+1
x +
∇ψ ∗ (z(k) ),
Ak+1
Ak+1

ẑ(k) = z(k) − ak+1 ∇f (x̂(k) ),
Ak (k)
ak+1
x(k+1) =
x +
∇ψ ∗ (ẑ(k) ),
Ak+1
Ak+1

(2.1)

x̂(k+1) = Grad(x(k+1) ).

(2.2)

z(k+1) = z(k) − ak+1 ∇f (x(k+1) ).

The idea behind axgd is similar to the dual-averaging version of Nemirovski’s mirror prox algorithm
[7, 18], with the main difference coming from the discretization of the accelerated dynamics in Equation
Note that Fenchel-Moreau Theorem requires ψ to only be lower-semicontinuous for ψ ∗∗ = ψ to hold, which is a weaker
property than continuity or continuous differentiability.
3

4

(2.5) (as opposed to the standard mirror descent dynamics used in [18]). As we will show, an exact
implicit Euler step would have ∇ψ ∗ (z(k+1) ) instead of ∇ψ ∗ (ẑ(k) ) in the third line of axgd. However,
obtaining x(k+1) in a such a manner could be computationally prohibitive since z(k+1) implicitly depends
on x(k+1) through its gradient. Instead, we opt for an extra prox-step ∇ψ ∗ (ẑ(k) ) that adds the gradient
at an intermediate point x̂(k) constructed using x(k) and z(k) from the previous iteration. Thanks to this
extra-gradient step, axgd can correct the discretization error without using a gradient step.
Convergence proof for axgd together with the sufficient conditions for obtaining optimal convergence
bounds are provided in Section 2.4. For example, Theorem 2.5 shows that when the objective function is
smooth, axgd converges at the optimal rate of 1/k 2 . The analysis of agd is provided in [7].

2.1

Approximate Optimality Gap

The analysis relies on the construction of an approximate optimality gap Gt , which is defined as the
difference of an upper bound Ut and a lower bound Lt to the optimal function value f (x∗ ). In particular,
for an increasing function of time t, α(t) , the convergence analysis will work on establishing the following:
Invariance condition: α(t) Gt is non-increasing with time t.
(t )

Such a condition immediately implies: Gt ≤ αα(t)0 Gt0 , leading to the α1(t) convergence rate. We sketch the
main ideas that relate to the accelerated methods and axgd in particular here for completeness, while
the more general arguments that recover a number of known first-order methods are provided in [7].
We now describe the upper bound and the lower bound choices, which will take the same form in both
continuous time and discrete time domains. To do so, we will rely on the Lebesgue-Stieltjes integration,
which allows us to treat continuous and discrete choice of α(t) in a unified manner. Observe
that Rwhen α(t)
Rt
t
(t)
(t)
(τ
is a discrete measure, α̇ is a train of (scaled) Dirac Delta functions. Denote A = t0 dα ) = t0 α̇(τ ) dτ .
Upper Bound As x∗ ∈ X is the minimizer of f (·), f (x) for any x ∈ X constitutes a valid upper
bound. In particular, our choice of the upper bound will be Ut = f (x(t) ), where x(t) is the solution
maintained by the algorithm at time t.
Lower Bound More interesting than the upper bound is the construction of a lower bound to
f (x∗ ). From convexity of f , we have the standard lower-bounding hyperplanes ∀x, x̂ ∈ X: f (x) ≥
f (x̂) + h∇f (x̂), x − x̂i. A natural choice of a lower bound to the optimum at time t ≥ t0 , is obtained by
averaging such hyperplanes over [t0 , t] according to the measure α:
Rt
f (u) ≥

t0

f (x(τ ) )dα(τ )
A(t)

Rt
+

t0

∇f (x(τ ) ), u − x(τ ) dα(τ )
A(t)

, ∀u ∈ X.

While we could take the minimum over u ∈ X on the right-hand side of this equation as our notion of
lower bound, this choice has two serious drawbacks. First, it is non-smooth, and in general not even
differentiable, as a function of t. Second, in continuous-time, it is not defined for our initial time t0 ,
meaning that we do not have a natural concept of initial lower bound and initial duality gap. (In the
discrete time, we can ensure that α contains a Dirac Delta function at t0 , which overcomes this issue.)
We address the first problem by applying regularization, i.e., by adding to both sides of the inequality
a regularizer term that is strongly-convex in x and then minimizing the right-hand side with respect
to u ∈ X.4 Without loss of generality, the regularizer can be taken to be the Bregman divergence of a
4

This is similar to the well-known Moreau-Yosida regularization.

5

σ-strongly convex function ψ taken from an input point x(t0 ). This yields:
f (x∗ ) +

Dψ (x∗ , x(t0 ) )
A(t)
nR
o
Rt
t
(τ ) )dα(τ )
minu∈X t0 ∇f (x(τ ) ), u − x(τ ) dα(τ ) + Dψ (u, x(t0 ) )
f
(x
+
.
≥ t0
A(t)
A(t)

To address the second problem, we mix into the α-combination of hyperplanes the optimal lower bound
f (x∗ ) with weight α(t) −A(t) (which is just zero in the discrete time, as in that case A(t) = α(t) ). Rescaling
the normalization factor, we obtain our notion of regularized lower bound:
nR
o
Rt
t
(τ ) ), u − x(τ ) dα(τ ) + D (u, x(t0 ) )
(τ
)
(τ
)
min
∇f
(x
u∈X
ψ
f (x )dα
t0
def
Lt = t0
+
(t)
(t)
α
α
(2.3)
(α(t) − A(t) )f (x∗ ) − Dψ (x∗ , x(t0 ) )
+
.
α(t)

2.2

Accelerated Mirror Descent in Continuous Time

We now show that the accelerated dynamics can be obtained by enforcing the invariance condition from
d
previous subsection with α(t) Gt being constant; i.e., we enforce that dt
(α(t) Gt ) = 0. Towards that goal,
assume that α(t) is continuously differentiable, and observe that α(t) − A(t) = α(t0 ) is constant. To
simplify the notation when taking the time derivative of α(t) G(t) , we first show the following:
Rt
Proposition 2.1. Let z(t) = ∇ψ(x(t0 ) ) − t0 ∇f (x(τ ) )dα(τ ) . Then:
∗

(t)

∇ψ (z ) = arg min
u∈X

Z t D

∇f (x

(τ )

), u − x

(τ )

E

dα

(τ )

+ Dψ (u, x

(t0 )


) .

t0

I.e., ∇ψ ∗ (z(t) ) is the argument of the minimum appearing in the definition of lower bound Lt . The
proof is simple and is provided in the appendix.
Recalling that Ut = f (x(t) ) and using (2.3) and Danskin’s theorem (which allows us to differentiate
inside the min):
D
E
d (t)
d
(α Gt ) = (α(t) f (x(t) )) − α̇(t) f (x(t) ) − α̇(t) ∇f (x(t) ), ∇ψ ∗ (z(t) ) − x(t)
dt
dt
E

D
= ∇f (x(t) ), α(t) x(t) − α̇(t) ∇ψ ∗ (z(t) ) − x(t) .
(2.4)
d
Hence, to obtain dt
(α(t) Gt ) = 0, it suffices to set α(t) x(t) = α̇(t) (∇ψ ∗ (z(t) ) − x(t) ), resulting in the
accelerated dynamics from [15]:

ż(t) = −α̇(t) ∇f (x(t) ),
∇ψ ∗ (z(t) ) − x(t)
,
α(t)
∈ X is an arbitrary initial point.

ẋ(t) = α̇(t)
z(t0 ) = ∇ψ(x(t0 ) ), x(t0 )

(2.5)

It is not hard to see that (2.5) constructs a sequence of points x(t) that are feasible, that is, x(t) ∈ X.
d
This is because x(t) can equivalently be written as dt
(α(t) x(t) ) = α̇(t) ∇ψ ∗ (z(t) ), which, after integrating
R
(t
)
t
0
over τ ∈ [t0 , t], gives x(t) = αα(t) x(t0 ) + α1(t) t0 ∇ψ ∗ (z(τ ) )dα(τ ) – a convex combination of x(t0 ) and
∇ψ ∗ (z(τ ) ) for τ ∈ [t0 , t]. By (2.5), x(t0 ) ∈ X, while ∇ψ ∗ (z(τ ) ) ∈ X by Proposition 2.1.
We immediately obtain the following continuous-time convergence guarantee:
6

Lemma 2.2. Let x(t) evolve according to (2.5). Then, ∀t ≥ t0 :
f (x(t) ) − f (x∗ ) ≤

α(t0 ) (f (x(t0 ) ) − f (x∗ )) + Dψ (x∗ , x(t0 ) )
.
α(t)

d
Proof. We have already established that dt
(α(t) G(t) ) = 0, and, therefore, f (x(t) ) − f (x∗ ) ≤ Gt =
Observing that Gt0 = f (x(t0 ) ) − f (x∗ ) + Dψ (x∗ , x(t0 ) )/α(t0 ) , the proof follows.

2.3

α(t0 )
Gt0 .
α(t)

Discretization

As discussed in Section 2.1, our construction of the approximate optimality gap is valid both in the
continuous time and in the discrete time domain. To understand where the discretization error occurs,
we make the following observations. First, the upper bound does not involve any integration, and thus
cannot incur a discretization error. In the lower bound (2.3), the role of the first integral is only to
perform weighted averaging, which is the same in the continuous time and in the discrete time, and,
therefore, does not incur a discretization error. The terms that are not integrated over look the same
whether or not α(t) is discrete. Therefore,
the only term that can incur the discretization error is the
Rt
integral under the min: I (t0 ,t) = t0 ∇f (x(τ ) ), ∇ψ ∗ (z(t) ) − x(τ ) dα(τ ) .
P
As mentioned before, when α is a discrete measure, we can express it as α(t) = ∞
+i−1)),
i=1 ai δ(t−(t
R
P 0
t
(τ
)
(t)
where δ(·) denotes the Dirac Delta function and ai ’s are positive. Then A = t0 dα = i:t0 +i−1≤t ai .
To simplify the notation, we will use i ∈ Z+ to denote the discrete time points corresponding to t0 + i − 1
on the continuous line. Therefore, the discretization error incurred in A(t) Lt between the discrete time
(i,i+1)
(i,i+1)
points i and i + 1 (understood as integrating from i+ to (i + 1)+ ) is I (i,i+1) − Ic
, where Ic
is
(i,i+1)
(i,i+1)
the continuous approximation of I
(i.e., we allow continuous integration rules in Ic
). We can
now establish the following bound on the discretization error.
Lemma 2.3. Let Ai+1 Gi+1 − Ai Gi ≡ Ei+1 be the discretization error. Then
Pk
Ei
A1
Gk =
G1 + i=1
Ak
Ak
and

D
E
Ei+1 ≤ ∇f (x(i+1) ), A(i+1) x(i+1) − A(i) x(i) − ai+1 ∇ψ ∗ (z(i+1) ) − Dψ∗ (z(i) , z(i+1) ).

Proof. The first part of the lemma follows by summing over 1 ≤ i ≤ k. For the second part, we have
(i,i+1)
already argued that Ei+1 = Ic
− I (i,i+1) . For the discrete integral I (i,i+1) , as α̇(t) just samples the
function under the integral at point i + 1, we have:
D
E
I (i,i+1) = ai+1 ∇f (x(i+1) ), ∇ψ ∗ (z(i+1) ) − x(i+1) .
(2.6)
For the continuous integral, using (2.5) and integration by parts:
Z i+1
Z i+1 D
D
E
E
(i,i+1)
(τ )
(τ )
(τ )
Ic
=
α
∇f (x ), ẋ
dτ +
∇f (x(τ ) ), ∇ψ ∗ (z(i+1) ) − ∇ψ ∗ (z(τ ) ) dα(τ )
i
i
Z i+1 D
E
= A(i) (f (x(i+1) ) − f (x(i) )) −
ż(τ ) , ∇ψ ∗ (z(i+1) ) − ∇ψ ∗ (z(τ ) ) dτ
i

= A(i) (f (x(i+1) ) − f (x(i) )) − Dψ∗ (z(i) , z(i+1) ),

(2.7)

where we have used ż(τ ) = −α̇(τ ) ∇f (x(τ ) ), ∇z(τ ) Dψ∗ (z(τ ) , z(i+1) ) = ∇ψ ∗ (z(τ ) ) − ∇ψ ∗ (z(i+1) ), and
Dψ∗ (z(i) , z(i) ) = 0.
7

By convexity of f , f (x(i+1) ) − f (x(i) ) ≤ ∇f (x(i+1) ), x(i+1) − x(i) . Combining with (2.6) and (2.7):
D
E
Ei+1 ≤ ∇f (x(i+1) ), A(i+1) x(i+1) − A(i) x(i) − ai+1 ∇ψ ∗ (z(i+1) ) − Dψ∗ (z(i) , z(i+1) ),
as claimed.
We remark that the same result for the discretization error can be obtained by directly computing
Ai+1 Gi+1 − Ai Gi under a discrete measure α (where all the integrals in the definition of the duality gap
are replaced by summations). We have chosen to work with the integration error described above to
demonstrate the cause of the discretization error.
We now describe how axgd cancels out the discretization error by (approximately) implementing
implicit Euler discretization of ẋ(t) .
Implicit Euler Discretization Implicit Euler discretization is an abstract discretization method
which defines the next iterate x(k+1) implicitly as a function of the gradient at x(k+1) . In the case of the
amd dynamics, implicit Euler discretization yields the following algorithm: let x(1) ∈ X be an arbitrary
initial point that satisfies x(1) = ∇ψ ∗ (z(1) ), where z(1) = ∇ψ(x(1) ) − ∇f (x(1) ); for all k ≥ 1
(
z(k+1) = z(k) − ak+1 ∇f (x(k+1) ),
(2.8)
a
k
x(k+1) = AAk+1
x(k) + Ak+1
∇ψ ∗ (z(k+1) )
k+1
Observe that x(k+1) in (2.8) exactly sets the inner product in Ei+1 (Lemma 2.3) to zero, leaving only the
negative term −Dψ∗ (z(i) , z(i+1) ). While this discretization is not computationally feasible in practice, as
it requires solving for the implicitly defined x(k+1) , it also boasts a negative discretization error, i.e., it
converges faster than the continuous-time amd. Ultimately, we will use this extra slack to trade-off the
error arising from an approximate implicit discretization.

2.4

Convergence of AXGD

A standard way to implement implicit Euler discretization in the solution of ODEs [9] is to replace the
exact solution of the implicit equation with a small number of fixed point iterations of the same equation.
In our case, the implicit equation can be written as:
x(k+1) =

Ak (k) ak+1
x +
∇ψ ∗ (z(k) − ak+1 ∇f (x(k+1) )).
Ak+1
Ak+1

Two steps of the fixed-point iteration yield the following updates, which are exactly those performed by
axgd:
(
a
k
x̂(k) = AAk+1
x(k) + Ak+1
∇ψ ∗ (z(k) ).
k+1
x(k+1) =

Ak
(k)
Ak+1 x

+

ak+1
∗ (k)
Ak+1 ∇ψ (z

− ak+1 ∇f (x̂(k) ))

We can now analyze axgd as producing an approximate solution to the implicit Euler discretization
problem. The following lemma gives a general bound on the convergence of axgd for a convex and
differentiable f (·) without additional assumptions. The only (mild) difference is replacing Dψ (x, x(1) )
and Dψ (x∗ , x(1) ) by Dψ (x, x̂(0) ) and Dψ (x∗ , x̂(0) ), since we start from the “intermediate” point x̂(0) . This
change is only important for bounding the initial gap G1 ; everything else is the same as before.
Lemma 2.4. Consider the axgd algorithm as described in Equation (2.2), starting from an arbitrary
point x̂(0) with z(0) = ∇ψ(x̂(0) ) and A0 = 0. Then the error from Lemma 2.3 is bounded by:
D
E
Ei+1 ≤ai+1 ∇f (x(i+1) ) − ∇f (x̂(i) ), ∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) )
− Dψ∗ (ẑ(i) , z(i+1) ) − Dψ∗ (z(i) , ẑ(i) ).
8

Proof. From Lemma 2.3:
D
E
Ei+1 ≤ai+1 ∇f (x(i+1) ), ∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) ) − Dψ∗ (z(i) , z(i+1) )
D
E
=ai+1 ∇f (x(i+1) ) − ∇f (x̂(i) ) + ∇f (x̂(i) ), ∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) )
− Dψ∗ (z(i) , z(i+1) ).
We now use the fact that ai+1 f (x̂(i) ) = z(i) − ẑ(i) together with the standard triangle-inequality for
Bregman divergences (see Proposition A.3) to show that:
D
E D
E
ai+1 ∇f (x̂(i) ), ∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) ) = z(i) − ẑ(i) , ∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) )
= Dψ∗ (z(i) , z(i+1) ) − Dψ∗ (ẑ(i) , z(i+1) ) − Dψ∗ (z(i) , ẑ(i) ),
Combining the results of the last two equations, we get the claimed bound on the error.

2.5

Smooth Minimization with AXGD

We show that axgd achieves the asymptotically optimal convergence rate of 1/k 2 for the minimization
of an L-smooth convex objective f (·) by applying Lemma 2.4. The crux of the proof is that we can take
sufficiently large steps while keeping the error from Lemma 2.4 non-positive. In other words, we are able
to move quickly through the continuous evolution of amd by taking large discrete steps.
Theorem 2.5. Let f : X → R be an L-smooth convex function and let x(k) , z(k) , x̂(k) , ẑ(k) be updated
according to the axgd algorithm in Equation (2.2), starting from an arbitrary initial point x̂(0) ∈ X with
the following initial conditions: z(0) = ∇ψ(x̂(0) ) and A0 = 0. Let ψ : X → R be σ-strongly convex. If
ak 2
σ
Ak ≤ L , then for all k ≥ 1,
Dψ (x∗ , x̂(0) )
.
f (x(k) ) − f (x∗ ) ≤
Ak
In particular, if ak =

k+1
2

·

σ
L

and ψ(x) = σ2 kxk2 , then:
f (x(k) ) − f (x∗ ) ≤

2L
kx∗ − x̂(0) k2 .
(k + 1)2

Proof. The proof follows directly by applying Lemma 2.4 and using L-smoothness of f and σ-strong
convexity of ψ. In particular, by Cauchy-Schwartz inequality and smoothness:
D
E
∇f (x(k+1) ) − ∇f (x̂(k) ), ∇ψ ∗ (ẑ(k) ) − ∇ψ ∗ (z(k+1) )
≤ Lkx(k+1) − x̂(k) k · k∇ψ ∗ (z(k+1) ) − ∇ψ ∗ (ẑ(k) )k,
and, by Proposition A.2
Dψ∗ (ẑ(k) , z(k+1) ) + Dψ∗ (z(k) , ẑ(k) )

σ
k∇ψ ∗ (ẑ(k) ) − ∇ψ ∗ (z(k+1) )k2 + k∇ψ ∗ (z(k) ) − ∇ψ ∗ (ẑ(k) )k2 .
≥
2
From the definition of the steps, x(k+1) − x(k) =
Ek+1 ≤

ak+1
∗ (k)
Ak+1 (∇ψ (ẑ )

− ∇ψ ∗ (z(k) )), and, therefore:

ak+1 2
σ
L · pq − (p2 + q 2 ),
Ak+1
2
9

(2.9)

where p = k∇ψ ∗ (ẑ(k) ) − ∇ψ ∗ (z(k+1) )k and q = k∇ψ ∗ (z(k) ) − ∇ψ ∗ (ẑ(k) )k. Since, for any p, q, p2 +
2
a
L
≤ 1, which is true by the
q 2 − 2αpq ≥ 0 whenever α ≤ 1, it follows that Ek+1 ≤ 0 whenever Ak+1
k+1 σ
2

σ
σ (k+1)(k+2)
theorem assumptions. In particular, for ak = k+1
) ≥ Lσ (k+1)
. This proves that
2 · L , Ak = L (
4
4
G1
(k)
∗
f (x ) − f (x ) ≤ Ak . It remains to bound G1 . This a simple computation, shown in the appendix, which
yields: G1 ≤ A11 Dψ (x∗ , x̂(0) ).

2.6

Generalized Smoothness: Hölder-Continuous Gradients

Suppose that f (·) has Hölder-continuous gradients, namely, f (·) then satisfies:
k∇f (x̂) − ∇f (x)k ≤ Lν kx̂ − xkν ,

(2.10)

which also implies:
∀x, x̂ ∈ X : f (x̂) ≤ f (x) + h∇f (x), x̂ − xi +

Lν
kx̂ − xk1+ν ,
1+ν

(2.11)

where ν ∈ (0, 1], Lν ∈ R++ . In particular, if ν = 1, then f (·) is Lν -smooth. Thus, the functions with
Hölder-continuous gradients represent a class of functions with generalized/relaxed smoothness properties.
The lower iteration complexity bound for (unconstrained) minimization
of convex
 functions with

2
1+ν − 1+3ν
Hölder-continuous gradients was established in [20] and equals O Lν D1 
, where D1 is the
distance from the initial point to the optimal solution. A matching upper bound was obtained in [19].
To recover the optimal convergence rate in the minimization of convex functions with Hölder-continuous
gradients, as before, we bound the discretization error from Lemma 2.4. Before doing so, we will need
the following technical proposition (which appears in a similar form as Lemma 3.1 a) in [18]).
Proposition 2.6.
D
E
ai+1 ∇f (x(i+1) ) − ∇f (x̂(i) ), ∇ψ ∗ (z(i+1) ) − ∇ψ ∗ (ẑ(i) ) ≤ σ −1 ai+1 2 k∇f (x(i+1) ) − ∇f (x̂(i) )k2 .
The proof is provided in the appendix.
Theorem 2.7. Let f (·) be a convex function that satisfies (2.10), and let ψ(·) be σ-strongly convex.
Let x(k) , z(k) , x̂(k) , ẑ(k) be updated according to the axgd algorithm in Equation (2.2), starting from an
arbitrary initial point x̂(0) ∈ X with the following initial conditions: z(0) = ∇ψ(x̂(0) ) and A0 = 0. Let
ak = c Lσν D1−ν k

−1+3ν
2

, where D = maxx,x̂∈X kx − x̂k and c = 2
f (x(k) ) − f (x∗ ) ≤ 2

1−3ν(ν+1)
2

3ν(ν+1)−1
2

. Then, ∀k ≥ 1 :

Lν Dν−1 Dψ (x∗ , x̂(0) )
.
1+3ν
σ
k 2

In particular, if ψ(x) = σ2 kxk2 , then:
f (x(k) ) − f (x∗ ) ≤ 2

1−3ν(ν+1)
2

Lν D1+ν k −

1+3ν
2

.

Proof. We prove the theorem by bounding the discretization error Ei+1 from Lemma 2.4. Applying

10

Propositions A.2 and 2.6:
D
E
Ei+1 =ai+1 ∇f (x(i+1) ) − ∇f (x̂(i) ), ∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) )
− Dψ∗ (ẑ(i) , z(i+1) ) − Dψ∗ (z(i) , ẑ(i) )
≤σ −1 ai+1 2 k∇f (x(i+1) ) − ∇f (x̂(i) )k2

σ
−
k∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) )k2 + k∇ψ ∗ (z(i) ) − ∇ψ ∗ (ẑ(i) )k2
2
σ
−1
≤σ ai+1 2 Lν 2 kx(i+1) − x̂(i) k2ν − k∇ψ ∗ (z(i) ) − ∇ψ ∗ (ẑ(i) )k2
2
2+2ν
σ
a
i+1
∗ (i)
∗ (i) 2ν
∗ (i)
∗ (i) 2
≤σ −1 Lν 2
2ν k∇ψ (z ) − ∇ψ (ẑ )k − 2 k∇ψ (z ) − ∇ψ (ẑ )k ,
Ai+1

(2.12)

where the second inequality is by (2.10) and the third inequality is by the step definition (2.2).
3ν(ν+1)−1
P
P
−1+3ν
2
Taking ak = c Lσν D1−ν k 2 , where c = 2
, it follows that Ak = ki=1 ai ≥ ki=dk/2e ai ≥
 1+3ν
c 1−ν σ k
2
. Therefore, the expression in (2.12) is at least:
2D
Lν 2

1
− c2 23ν(ν+1) (k + 1)ν−1 +
σk∇ψ ∗ (z(k) ) − ∇ψ ∗ (ẑ(k) )k2 ≥ 0,
2
as (k + 1)ν−1 ≤ 1. Therefore, we have that Gk ≤
initial gap G1 , the proof follows.

2.7

A(1)
G ,
A(k) 1

and using similar arguments to bound the

Non-Smooth Minimization: Lipschitz-Continuous Objective

We now show that we can recover the well-known √1k convergence rate for the class of non-smooth
L-Lipschitz objectives by using axgd. This is summarized in the following theorem. We note that, as
in the analysis of classical mirror descent (see, e.g., [3]), the factor log(k) can be removed if we fix the
approximation error (and, consequently, the number of steps k) in advance.
Theorem 2.8. Let f (·) be a Lipschitz-continuous function with parameter L. Let x(k) , z(k) , x̂(k) , ẑ(k)
be updated according to the axgd algorithm in Equation (2.2), starting from an arbitraryq
initial point
x̂(0) ∈ X with the following initial conditions: z(0) = ∇ψ(x̂(0) ) and A0 = 0. If ak =
then, ∀k ≥ 1:
q
f (x

(k)

L·

∗

) − f (x ) ≤ 8(2 + log(k))

√
√σ
2 2L

Dψ (x∗ ,x̂(0) )
,
k

Dψ (x∗ , x̂(0) )
.
√ √
σ k

In particular, for ψ(x) = σ2 kxk2 :
√
L · kx∗ − x̂(0) k
√
f (x(k) ) − f (x∗ ) ≤ 4 2(2 + log(k))
.
k
Proof. As before, we bound the discretization error from Lemma 2.4. As f (·) is L-Lipschitz, using
Proposition A.2:
D
E
Ei+1 ≤ai+1 ∇f (x(i+1) ) − ∇f (x̂(i) ), ∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) )
− Dψ∗ (ẑ(i) , z(i+1) ) − Dψ∗ (z(i) , ẑ(i) )
≤2ai+1 Lk∇ψ ∗ (z(i+1) ) − ∇ψ ∗ (ẑ(i) )k −
≤

8(a(i+1) L)2
,
σ
11

σ
k∇ψ ∗ (z(i+1) ) − ∇ψ ∗ (ẑ(i) )k2
2

(a) unconstrained

(b) unconstrained

(c) simplex

(d) simplex

Figure 1: ((a)),((c)) Exact and ((b)),((d)) approximate duality gaps for agd and axgd with exact
gradients.
where we have used the inequality 2xy − x2 ≤ y 2 , ∀x, y. As σ ≥ L and
√
2 2L

k
k
X
X
1
1
1
√ ≥
√ ≥ ·
Ak · q
=
2
k i=dk/2e k
σDψ (x∗ , x̂(0) )
i=1

we have that
k
L·
X
Ei
≤8·
Ak
i=1

r

k
,
2

q
Dψ (x∗ , x̂(0) )
(log(k) + 1),
√ √
σ k

which, after bounding the initial gap by similar arguments, completes the proof.

3

Experiments

We now illustrate the performance of agd and axgd for (i) an unconstrained problem over Rn with
the objective function f (x) = 12 hAx, xi − hb, xi, and (ii) for the problem with the same objective and
unit simplex as the feasible region, where A is the Laplacian of a cycle graph5 and b is a vector whose
first element is one and the remaining elements are zero. This example is known as a “hard” instance for
smooth minimization – it is typically used in proving the lower iteration complexity bound for first-order
methods (see, e.g., [28]). We also include Gradient Descent (gd) in the exact gap graphs for comparison.
In the experiments, we take n = 100 and σ = L (= 4). We use the `2 norm in the gradient steps.
In the figures, f denotes the objective value at the upper-bound point and f ∗ denotes the optimal
objective value, so that f − f ∗ is the true distance to the optimum (the exact gap). Fig. 1 shows the
distance to the optimum and the approximate duality gap Gk = Uk − Lk obtained using our analysis.
We can observe that agd and axgd exhibit similar performance in these examples. The approximate
gap overestimates the actual duality gap, however, the difference between the two decreases with the
number of iterations.
Acceleration and Noise We now consider the setting in which the gradients output by our oracle
are corrupted by additive noise, which has significant applications in practice [10] and theory [2]. We
note that this model is fundamentally different from the inexact model considered by Devolder et al. [6],
for which tight lower bounds preventing acceleration exist.6
5

Namely, the sum of a tridiagonal matrix B with 2’s on its main diagonal and -1’s on its remaining two diagonals and a
matrix C whose all elements are zero except for the C1,n = Cn,1 = −1.
6
In [6], it is assumed that a function f (·) is associated with a (δ, L) oracle, such that f (x̂) ≤ f (x) + h∇f (x), x̂ − xi +
L
kx̂
− xk2 + 2δ , ∀x, x̂ ∈ X. Such a model seems more suitable for incorrectly specified functions (e.g., non-smooth functions
2
treated as being smooth) and adversarially perturbed functions.

12

(a) η = 10−1 , unconstrained

(b) η = 10−2 , unconstrained

(c) η = 10−3 , unconstrained

(d) η = 10−1 , simplex

(e) η = 10−2 , simplex

(f) η = 10−3 , simplex

Figure 2: Exact gap for additive Gaussian noise in the gradients with zero mean and covariance η I
((a))-((c)) in the unconstrained-region case and ((d))-((f)) in unit simplex.
Specifically, we experimentally evaluate the performance of agd and axgd under additive Gaussian
noise. Fig. 2 illustrates the performance of agd and axgd when the gradients are corrupted by zero-mean
additive Gaussian noise with covariance matrix η I, where I is the identity matrix. When the region
is unconstrained (top row in Fig. 2), both agd and axgd exhibit high sensitivity to noise. The gd
method overall exhibits higher tolerance to noise (at the expense of slower convergence). In the case of
the unit simplex region (bottom row in Fig. 2), all the algorithms appear more tolerant to noise than in
the unconstrained case. Interestingly, on this example axgd exhibits higher tolerance to noise than gd
and agd, both in terms of mean and in terms of variance. Explaining this phenomenon analytically is an
interesting question that merits further investigation.

4

Conclusion

We have presented a novel accelerated method – axgd– that combines ideas from the Nesterov’s agd and
Nemirovski’s mirror prox. axgd achieves optimal convergence rates for a range of convex optimization
problems, such as the problems with the (i) smooth objectives, (ii) objectives with Hölder-continuous
gradients, (iii) and non-smooth Lipschitz-continuous objectives. In the constrained-regime experiments
from Section 3, the method demonstrates favorable performance compared to agd when subjected to
zero-mean Gaussian noise.
There are several directions that merit further investigation. A more thorough analytical and
experimental study of acceleration when the gradients are corrupted by noise is of particular interest,
since the gradients can often come from noise-corrupted measurements. Further, our experiments from
Fig. 2 suggest that there are cases that incur a trade-off between noise tolerance and acceleration. A
systematic study of this trade-off is thus another important direction, since it would guide the choice of
accelerated/non-accelerated algorithms in practice depending on the application. Finally, it is interesting

13

to investigate whether restart schemes can improve the algorithms’ noise tolerance, since in the noiseless
setting several restart schemes are known to improve the convergence of agd in practice.

References
[1] Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and
mirror descent. In Proc. ITCS’17, 2017.
[2] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient
algorithms and tight error bounds. In Proc. IEEE FOCS’14, 2014.
[3] Aharon Ben-Tal and Arkadi Nemirovski. Lectures on modern convex optimization: Analysis,
algorithms, and engineering applications. MPS-SIAM Series on Optimization. SIAM, 2001.
[4] Sébastien Bubeck. Theory of Convex Optimization for Machine Learning. 2014. arXiv preprint,
arXiv:1405.4980v1.
[5] Sébastien Bubeck, Yin Tat Lee, and Mohit Singh. A geometric alternative to Nesterov’s accelerated
gradient descent. 2015. URL: http://arxiv.org/abs/1506.08187.
[6] Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex
optimization with inexact oracle. Math. Prog., 146(1-2):37–75, 2014.
[7] Jelena Diakonikolas and Lorenzo Orecchia. The approximate gap technique: A unified approach to
optimal first-order methods, 2017. Manuscript.
[8] A. Ene and H. L. Nguyen. Constrained submodular maximization: Beyond 1/e. In Proc. IEEE
FOCS’16, 2016.
[9] E Hairer, SP Nørsett, and G Wanner. Solving Ordinary Differential Equations I (2nd Revised. Ed.):
Nonstiff Problems. Springer Ser. Comput. Math. Springer-Verlag New York, Inc., 1993.
[10] Moritz
Hardt.
Robustness
vs
acceleration,
2014.
http://blog.mrtz.org/2014/08/18/robustness-versus-acceleration.html.

Accessible

at

[11] Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. QIP = PSPACE. Journal of the
ACM (JACM), 58(6):30, 2011.
[12] Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time
algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations.
In Proc. ACM-SIAM SODA’14, 2014.
[13] Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. A simple, combinatorial
algorithm for solving SDD systems in nearly-Linear time. In Proc. ACM STOC’13, 2013.
[14] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matekon
: translations of Russian & East European mathematical economics, 13(4):35–49, 1977.
[15] Walid Krichene, Alexandre Bayen, and Peter L Bartlett. Accelerated mirror descent in continuous
and discrete time. In Proc. NIPS’15, 2015.
[16] Guanghui Lan. An optimal method for stochastic composite optimization. Math. Prog., 133(1-2):365–
397, January 2011.

14

[17] Yin Tat Lee, Satish Rao, and Nikhil Srivastava. A new approach to computing maximum flows
using electrical flows. In Proc. ACM STOC ’13, 2013.
[18] Arkadi Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with
Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM
J. Optimiz., 15(1):229–251, 2004.
[19] Arkadi S Nemirovski and Yurii Evgen’evich Nesterov. Optimal methods of smooth convex minimization. Zh. Vychisl. Mat. i Mat. Fiz., 25(3):356–369, 1985.
[20] Arkadii Nemirovskii and David Borisovich Yudin. Problem complexity and method efficiency in
optimization. Wiley, 1983.
[21] Yu Nesterov. Universal gradient methods for convex optimization problems. Math. Prog., 152(12):381–404, 2015.
[22] Yurii Nesterov. A method of solving a convex programming problem with convergence rate O(1/k 2 ).
In Doklady AN SSSR (translated as Soviet Mathematics Doklady), volume 269, pages 543–547, 1983.
[23] Yurii Nesterov. Introductory Lectures on Convex Programming Volume: A Basic course, volume I.
Kluwer Academic Publishers, 2004.
[24] Yurii Nesterov. Excessive gap technique in nonsmooth convex minimization. SIAM J. Optimiz.,
16(1):235–249, January 2005.
[25] Yurii Nesterov. Smooth minimization of non-smooth functions. Math. Prog., 103(1):127–152,
December 2005.
[26] Yurii Nesterov. Accelerating the cubic regularization of Newton’s method on convex problems. Math.
Prog., 112(1):159–181, 2008.
[27] Yurii Nesterov. Gradient methods for minimizing composite functions. Math. Prog., 140(1):125–161,
2013.
[28] Yurii Nesterov. Introductory lectures on convex optimization: A basic course. Springer Science &
Business Media, 2013.
[29] Jonah Sherman. Nearly maximum flows in nearly linear time. In Proc. IEEE FOCS’13, 2013.
[30] Daniel A. Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning,
graph sparsification, and solving linear systems. In Proc. ACM STOC ’04, 2004.
[31] Weijie Su, Stephen Boyd, and Emmanuel Candes. A differential equation for modeling nesterov’s
accelerated gradient method: Theory and insights. In Proc. NIPS’14, 2014.
[32] Paul Tseng. On accelerated proximal gradient methods for convex-concave optimization, 2008.
[33] Andre Wibisono, Ashia C Wilson, and Michael I Jordan. A variational perspective on accelerated
methods in optimization. In Proc. Natl. Acad. Sci. U.S.A., 2016.

15

A

Properties of the Bregman Divergence

The following properties of Bregman divergence will be useful in our analysis.
Proposition A.1. Dψ (∇ψ ∗ (z), x) = Dψ∗ (∇ψ(x), z), ∀x, z.
Proof. From the definition of ψ ∗ and Fact 1.6,
ψ ∗ (z) = h∇ψ ∗ (z), zi − ψ(∇ψ ∗ ), ∀z.

(A.1)

Similarly, as in the light of Fenchel-Moreau Theorem ψ ∗∗ = ψ,
ψ(x) = h∇ψ(x), xi − ψ ∗ (∇ψ(x)), ∀x.

(A.2)

Using the definition of Dψ (∇ψ ∗ (z), x) and Fact 1.6:
Dψ (∇ψ ∗ (z), x) = ψ(∇ψ ∗ (z)) − ψ(x) − h∇ψ(x), ∇ψ ∗ (z) − xi
= ψ(∇ψ ∗ (z)) + ψ ∗ (∇ψ(x)) − h∇ψ(x), ∇ψ ∗ (z)i .

(A.3)

Similarly, using the definition of Dψ∗ (∇ψ(x), z) combined with (A.1):
Dψ∗ (∇ψ(x), z) = ψ ∗ (∇ψ(x)) − ψ ∗ (z) − h∇ψ ∗ (z), ∇ψ(x) − zi
= ψ ∗ (∇ψ(x)) + ψ(∇ψ ∗ (z)) − h∇ψ ∗ (z), ∇ψ(x)i .

(A.4)

Comparing (A.3) and (A.4), the proof follows.
Proposition A.2. If ψ(·) is σ-strongly convex, then Dψ∗ (z, ẑ) ≥ σ2 k∇ψ ∗ (z) − ∇ψ ∗ (ẑ)k2 .
Proof. Using the definition of Dψ∗ (z, ẑ) and (A.1), we can write Dψ∗ (z, ẑ) as:
Dψ∗ (z, ẑ) = ψ(∇ψ ∗ (ẑ)) − ψ(∇ψ ∗ (z)) − hz, ∇ψ ∗ (ẑ) − ∇ψ ∗ (z)i .
Since ψ(·) is σ-strongly convex, it follows that:
Dψ∗ (z, ẑ) ≥

σ
k∇ψ ∗ (ẑ) − ∇ψ ∗ (z)k2 + h∇ψ(∇ψ ∗ (z)) − z, ∇ψ ∗ (ẑ) − ∇ψ ∗ (z)i .
2

As, from Fact 1.6, ∇ψ ∗ (z) = arg maxx∈X {hx, zi − ψ(x)}, by the first-order optimality condition
h∇ψ(∇ψ ∗ (z)) − z, ∇ψ ∗ (ẑ) − ∇ψ ∗ (z)i ≥ 0,
completing the proof.
The Bregman divergence Dψ∗ (x, y) captures the difference between ψ ∗ (x) and its first order approximation at y. Notice that, for a differentiable ψ ∗ , we have:
∇x Dψ∗ (x, y) = ∇ψ ∗ (x) − ∇ψ ∗ (y).
The Bregman divergence Dψ∗ (x, y) is a convex function of x. Its Bregman divergence is itself.
Proposition A.3. For all x, y, z ∈ X
Dψ∗ (x, y) = Dψ∗ (z, y) + h∇ψ ∗ (z) − ∇ψ ∗ (y), x − zi + Dψ∗ (x, z).

16

B

Omitted Proofs from Section 2

Rt
Proposition 2.1. Let z(t) = ∇ψ(x(t0 ) ) − t0 ∇f (x(τ ) )dα(τ ) . Then:
Z t D

E
∗ (t)
(τ )
(τ )
(τ )
(t0 )
∇ψ (z ) = arg min
∇f (x ), u − x
dα + Dψ (u, x ) .
u∈X

t0

Proof. From the definition of Bregman divergence:

Z t D
E
(τ )
(τ )
(τ )
(t0 )
arg min
∇f (x ), u − x
dα + Dψ (u, x )
u∈X
t0
Z t D
E
D
E
(τ )
(τ )
(τ )
(t0 )
(t0 )
(t0 )
= arg min
∇f (x ), u − x
dα + ψ(u) − ψ(x ) − ∇ψ(x ), u − x
u∈X
t0
Z t


(τ )
(τ )
(t0 )
= arg min
∇f (x )dα − ∇ψ(x ), u + ψ(u) .
u∈X

t0

Using the definition of z(t) and Fact 1.6, the proof follows.
Remaining Proof of Theorem 2.5 (The Bound on G1 ). To bound G1 , we recall the definition of L1 :
D

E
1
1
(1)
(1)
(1)
(0)
+
L1 = f (x ) + min
∇f (x ), x − x
Dψ (x, x̂ ) −
Dψ (x∗ , x̂(0) )
x∈X
A1
A1
E
D
1
1
Dψ (∇ψ ∗ (z(1) ), x̂(0) ) −
Dψ (x∗ , x̂(0) ).
= f (x(1) ) + ∇f (x(1) ), ∇ψ ∗ (z(1) ) − x(1) +
A1
A1
As a1 = A1 , x(1) = ∇ψ ∗ (ẑ(0) ), and a1 ∇f (x̂(0) ) = z(0) − ẑ(0) , using Proposition A.3, we have that:
E
D
E
1 D (0)
∇f (x̂(0) ), ∇ψ ∗ (z(1) ) − x(1) =
z − ẑ(0) , ∇ψ ∗ (z(1) ) − ∇ψ ∗ (ẑ(0) )
A1

1 
Dψ∗ (z(0) , ẑ(0) ) − Dψ∗ (z(0) , z(1) ) + Dψ∗ (ẑ(0) , z(1) ) .
(B.1)
=
A1
On the other hand, by smoothness of f (·) and the initial condition:
E
D
∇f (x(1) ) − ∇f (x̂(0) ), ∇ψ ∗ (z(1) ) − x(1) ≥ −Lk∇ψ ∗ (ẑ(0) ) − x̂(0) kk∇ψ ∗ (z(1) ) − x(1) k.

(B.2)

Finally, by Proposition A.1 and the initial condition z(0) = ∇ψ(x̂(0) ), we have that Dψ∗ (z(0) , z(1) ) =
Dψ (∇ψ ∗ (z(1) ), x̂(0) ). Combining with (B.1), (B.2), and G1 = U1 − L1 = f (x(1) ) − L1 :
G1 ≤Lk∇ψ ∗ (ẑ(0) ) − x̂(0) k · k∇ψ ∗ (z(1) ) − x(1) k

1
1 
−
Dψ∗ (z(0) , ẑ(0) ) + Dψ∗ (ẑ(0) , z(1) ) +
Dψ (x∗ , x̂(0) )
A1
A1
=Lk∇ψ ∗ (ẑ(0) ) − x̂(0) k · k∇ψ ∗ (z(1) ) − x(1) k

1 
1
−
Dψ (∇ψ ∗ (ẑ(0) ), x̂(0) ) + Dψ∗ (ẑ(0) , z(1) ) +
Dψ (x∗ , x̂(0) )
A1
A1
≤Lk∇ψ ∗ (ẑ(0) ) − x̂(0) k · k∇ψ ∗ (z(1) ) − x(1) k

σ 
1
−
k∇ψ ∗ (ẑ(0) ) − x̂(0) k2 + k∇ψ ∗ (z(1) ) − x(1) k2 +
Dψ (x∗ , x̂(0) )
2A1
A1
1
≤ Dψ (x∗ , x̂(0) ),
A1
where we have used Proposition A.1, x(1) = ∇ψ ∗ (ẑ(0) ), and
17

a1 2
A1

= A1 ≤

σ
L.

Proposition 2.6.
D
E
ai+1 ∇f (x(i+1) ) − ∇f (x̂(i) ), ∇ψ ∗ (z(i+1) ) − ∇ψ ∗ (ẑ(i) ) ≤ σ −1 ai+1 2 k∇f (x(i+1) ) − ∇f (x̂(i) )k2 .
Proof. From the first order optimality condition in Fact 1.6, ∀x, y ∈ X:
D
E
∇ψ(∇ψ ∗ (z(i+1) )) − z(i+1) , x − ∇ψ ∗ (z(i+1) ) ≥ 0, and
D
E
∇ψ(∇ψ ∗ (ẑ(i) )) − ẑ(i) , y − ∇ψ ∗ (ẑ(i) ) ≥ 0.

(B.3)
(B.4)

Letting x = ∇ψ ∗ (ẑ(i) ), y = ∇ψ ∗ (z(i+1) ), and summing (B.3) and (B.4):
D
E
ẑ(i) − z(i+1) , ∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) )
D
E
≥ ∇ψ(∇ψ ∗ (ẑ(i) )) − ∇ψ(∇ψ ∗ (z(i+1) )), ∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) )
≥ σk∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) )k2 ,

(B.5)

where (B.5) follows by the σ-strong convexity of ψ(·). Using the Cauchy-Schwartz inequality and dividing
both sides by k∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) )k gives kẑ(i) − z(i+1) k ≥ σk∇ψ ∗ (ẑ(i) ) − ∇ψ ∗ (z(i+1) )k.
Since, by the step definition (2.2), ẑ(i) − z(i+1) = ai+1 (∇f (x(i+1) ) − ∇f (x̂(i) )), applying CauchySchwartz Inequality to ai+1 ∇f (x(i+1) ) − ∇f (x̂(i) ), ∇ψ ∗ (z(i+1) ) − ∇ψ ∗ (ẑ(i) ) completes the proof.

18

