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 [11] and Extra-Gradient Descent [7] in the solution of convex-concave saddle point problems. For this reason, we dub our algorithm Accelerated Extra-Gradient Descent (axgd).
Abstract
Its construction is motivated by the discretization of an accelerated continuous-time dynamics [8] using the classical method of implicit Euler discretization. Our analysis explicitly shows the effects of discretization through a conceptually novel primal-dual viewpoint. Finally, we present experiments showing that our algorithm matches the performance of Nesterov's method, while appearing more robust to noise in some cases.
Introduction
In his seminal work [13, 14] , 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( 1 /k 2 ), which has been shown to be asymptotically optimal [14] for smooth functions in this standard blackbox model [19] . More recently, Nesterov generalized this method to allow non-Euclidean norms in the definition of smoothness [16] . We refer to this generalization of Nesterov's method and to instantiations thereof as Accelerated Gradient Descent (agd) methods. Accelerated gradient methods have been widely extended and modified for different settings, including composite optimization [9, 18] , cubic regularization [17] and universal methods [20] . They have also found a number of fundamental applications in many algorithmic areas, including machine learning (see [2] ) and discrete optimization [10] . However, to this day, Nesterov's agd methods remain the only paradigm 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 [22] . In this paper, 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 [11] and Extra-Gradient Descent [7] . For this reason, we name our method Accelerated Extra-Gradient Descent (axgd).
Introduction
Our derivation of the axgd algorithm is based on the discretization of a recently proposed continuoustime accelerated algorithm [8, 23] . The continuous-time view is particularly helpful in clarifying the relation between agd, axgd and Mirror-Prox. Following Krichene's presentation [8] , 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.1). With this setup, Nesterov's agd can be seen as a variant of the classical forward-Euler discretization applied to the acceleratedmirror-descent dynamics. In contrast, Mirror-Prox and similar extra-gradient methods arise from the application of an approximate backward-Euler discretization [6] to the mirror-descent dynamics. Finally, our algorithm axgd is the result of an approximate backward-Euler discretization of the accelerated mirror-descent dynamics.
Introduction
While this paper focuses on the smooth case, the same techniques easily yield results matching those of agd methods both for the strongly-convex-and-smooth case and the case of Hölder-continuous gradients. A more thorough description of the techniques together with their applications to a range of convex optimization problems will be included in the upcoming full version of this paper.
Introduction
Another conceptual contribution of this 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 algorithms explicitly maintain 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 U t and a lower bound L t on the optimum: U t ≥ f (x * ) ≥ L t . In all cases, we obtain convergence bounds by explicitly quantifying the rate at which the duality gap G t = U t − L t 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 [5] .
Introduction
Finally, we present an analysis of axgd for the case of a noisy first-order oracle and a number of experiments showing that the performance of axgd closely matches that of agd methods while exhibiting better stability properties in some cases.
Related Work
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 Ω( 1 / √ k) [12] , Nesterov showed that the saddle-point structure can be exploited by smoothing the original problem and applying agd methods on the resulting smooth function [16] . This approach [15, 16] yields an O( 1 /k)-convergence for convex-concave saddle point problems with smooth gradients. Surprisingly, at around the same time, Nemirovski [11] 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 [12] . 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.
Related Work
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 [22] . 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 [3] . At the same time, Krichene et al. [8] and Wibisono et al. [23] 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 [8] .
Preliminaries
We will focus on continuous and differentiable functions defined on a convex set X ⊆ R n . The following definitions will be useful in our analysis, and thus we state them here for completeness.
Preliminaries
. A function f : X → R is strongly convex on X with strong convexity parameter σ and with respect to a norm . , if for all
Preliminaries
In the rest of the paper, we will assume that ψ(x) is continuously differentiable, so that Fenchel-Moreau Theorem implies that ψ * * = ψ. 1 We are interested in minimizing a convex function f over X ⊆ R n . We let x * = arg min x∈X f (x).
Preliminaries
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
Preliminaries
We will assume that there is a strongly-convex differentiable function ψ : X → R such that max x∈X { z, x − ψ(x)} is easily solvable, possibly in a closed form. Notice that this problem defines the convex conjugate of ψ(.), i.e., ψ * (z) = max x∈X { z, x − ψ(x)}. The following standard fact will be extremely useful in carrying out the analysis of the algorithms in this paper. Properties of the Bregman Divergence. The following properties of Bregman divergence will be useful in our analysis.
Preliminaries
Proof. From the definition of ψ * and Fact 1.6,
Preliminaries
Similarly, as in the light of Fenchel-Moreau Theorem ψ * * = ψ,
Preliminaries
Using the definition of D ψ (∇ψ * (z), x) and Fact 1.6:
Preliminaries
Similarly, using the definition of D ψ * (∇ψ(x), z) combined with (1.1):
Preliminaries
Comparing (1.3) and (1.4), the proof follows.
Preliminaries
Using the definition D ψ * (z,ẑ) and (1.1), we can write D ψ * (z,ẑ) as:
Preliminaries
Since ψ(.) is σ-strongly convex, it follows that:
Preliminaries
As, from Fact 1.6, ∇ψ * (z) = arg max x∈X { x, z − ψ(x)}, by the first-order optimality condition
Preliminaries
completing the proof.
Preliminaries
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:
Preliminaries
The Bregman divergence D ψ * (x, y) is a convex function of x. Its Bregman divergence is itself. 
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. Steps in each iteration of agd come from explicit (forward) Euler discretization, followed by the gradient step that is used to correct the discretization error. The points x (k) are used in the construction of the lower bound, while the pointŝ x (k) = Grad(x (k) ) are used in the upper bound.
Accelerated Extra-Gradient Descent
Accelerated Gradient Descent (agd )
Accelerated Extra-Gradient Descent
x (k+1) = Grad(x (k+1) ).
(2.1)
Accelerated Extra-Gradient Descent (axgd )
(2.1)
The iterations of axgd come from an approximate implementation of implicit (backward) Euler discretization. The idea is similar to Nemirovski's mirror prox algorithm [11] , with the main difference coming from the discretization of the accelerated dynamics in Equation (2.4) (as opposed to the standard mirror descent dynamics used in [11] ). As we will show, an exact implicit Euler step would have x (k+1) equal ∇ψ * (z (k+1) ) in the third line of axgd. However, obtaining such an x (k+1) 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 ∇ψ * (ẑ (k) ) that adds the gradient at an intermediate pointx (k) constructed using x (k) and z (k) from the previous iteration. Thanks to this extra-gradient (or, more accurately, extra-prox) step, axgd can correct the discretization error without using a gradient step as agd, and both the upper bound and the lower bound are constructed from the points x (k) .
(2.1)
Convergence proofs for the two algorithms together with the sufficient conditions for obtaining optimal convergence bounds are provided in Section 2.3 and Appendix B. Theorems 2.6 and B.1 show that when the objective function is smooth, agd and axgd converge at the optimal rate of 1/k 2 .
Accelerated Mirror Descent in Continuous Time
We now discuss the continuous-time analogues of first-order methods, upon which our new algorithm is based. While the analogy between discrete optimization algorithms and continuous-time dynamics was known from the outstart [12] , recent works by Krichene et al. [8] and Wibisono et al. [23] have shed more light on this connection, reaffirming the importance of the choice of discretization, which was also studied by Scieur et al. [21] .
Accelerated Mirror Descent in Continuous Time
Our description of the dynamics closely follows that of Krichene et al. [8] . We use "dot" notation to denote the time derivative. That is,ẋ = dx /dt. We allow for a slightly more general scaling of time, by introducing a continuously-differentiable monotonically increasing function α (t) be of time t with α (1) = 1.
Accelerated Mirror Descent in Continuous Time
Mirror Descent then has following continuous-time analogue [12] :
Accelerated Mirror Descent in Continuous Time
.
Accelerated Mirror Descent in Continuous Time
(2.3)
Accelerated Mirror Descent in Continuous Time
Recently, Krichene et al. [8] introduced a different dynamics, the accelerated-mirror-descent (AMD) dynamics, as a continuous-time analogue of accelerated first-order methods. The continuous-time AMD dynamics can be described as:
Accelerated Mirror Descent in Continuous Time
),
Accelerated Mirror Descent in Continuous Time
.
Accelerated Mirror Descent in Continuous Time
(2.4)
Accelerated Mirror Descent in Continuous Time
The following proposition gives an integral expression for z (t) and x (t) in the AMD dynamics. Its simple proof appears in the appendix. To avoid singularities at the initial point, we will start the evolution of (2.4) at t 0 = 1 from an arbitrary point x (1) ∈ X and z (1) = ∇ψ(x (1) ). In this proposition and for the rest of the paper, we will make use of the Lesbegue-Stieljes notation for the integral with respect to the densityα (t) .
Accelerated Mirror Descent in Continuous Time
Proposition 2.1. Let x (t) and z (t) evolve according to (2.4) , starting at t 0 = 1 from an arbitrary point x (1) ∈ X and z (1) = ∇ψ(x (1) ). Then, ∀t ≥ 1:
Accelerated Mirror Descent in Continuous Time
At this point, we briefly remark on the difference between the mirror descent dynamic and its accelerated counterpart, which lies in the form ofż (t) . In the basic mirror-descent dynamic, this derivative equals the negative gradient of the function at the point ∇ψ * (z (t) ), which can be thought of as the primal image of the current dual solution z (t) under the mirror map ∇ψ * . In contrast, for the accelerated dynamics, the gradient is actually taken at x (t) , which, by the previous preposition, is the average of the mirror maps of the dual solutions observed so far. Ultimately it is this additional averaging that enables acceleration.
Accelerated Mirror Descent in Continuous Time
We now describe an analysis of the convergence of f (x (t) ) to f (x * ) in the AMD dynamics. Our argument differs from that of Krichene et al. [8] by taking a primal-dual viewpoint. This analysis will provide a blueprint for the convergence arguments of all accelerated algorithms in this paper.
Accelerated Mirror Descent in Continuous Time
Constructing Upper and Lower Bounds to the Optimum. We interpret the primal-dual pair (x (t) , z (t) ) maintained by the evolution of (2.4) as constructing both an upper and a lower bound to the optimal value f (x * ). The upper bound U t is naturally given by the function value at time t, i.e., U t def = f (x (t) ). In continuous time, this has derivativė
Accelerated Mirror Descent in Continuous Time
(2.5)
Accelerated Mirror Descent in Continuous Time
The construction of the lower bound is more interesting. At each time t, the convexity of the objective f (.) yields the lower-bounding hyperplane:
Accelerated Mirror Descent in Continuous Time
A natural choice of lower bound to the optimum at time t ≥ 1, is given by averaging such hyperplanes over [1, t] according to the measure α and by minimizing over
Accelerated Mirror Descent in Continuous Time
While we could use 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, it is not defined for our initial time t 0 = 1, meaning that we do not have a natural concept of initial lower bound and initial duality gap. We overcome the first obstacle by applying Moreau-Yosida regularization, i.e., by adding to the minimization a regularizer term that is strongly-convex in x. Without loss of generality, this term can be taken to be the Bregman divergence of a σ-strongly convex function ψ taken from an input point x (1) . This yields:
Accelerated Mirror Descent in Continuous Time
To address the second problem, we mix into the α-combination of hyperplanes the optimal 2 lower bound f (x * ) with weight 1. Rescaling the normalization factor, we obtain our notion of regularized lower bound:
Accelerated Mirror Descent in Continuous Time
With this definition, a simple computation yields the derivative of the lower bound L t .
Accelerated Mirror Descent in Continuous Time
Proof. First, we notice that:
Accelerated Mirror Descent in Continuous Time
We then have:
Accelerated Mirror Descent in Continuous Time
Convergence of Accelerated Mirror Descent. We are now ready to prove the convergence of the AMD dynamics from Equation (2.4).
Accelerated Mirror Descent in Continuous Time
Theorem 2.3. The continuous-time dynamics described by Eq. (2.4) and the initial condition z (1) = ∇ψ(x (1) ) converges as follows: for any t > 1,
Accelerated Mirror Descent in Continuous Time
Proof. Consider the evolution of the duality gap G t = U t − L t . By Equation (2.5) and Proposition 2.2, we have:Ġ
Accelerated Mirror Descent in Continuous Time
By the definition of the dynamics, this yieldsĠ t = −α (t) Gt α (t) . Because this is equivalent to d /dt α (t) G t = 0, we obtain that G t = G 1/α (t) for t ≥ 1.
Discretization
We now show how to discretize the continuous time algorithms from the previous subsection, while using similar arguments in the convergence analysis. We will consider unit-length steps (i.e., the algorithm will be making updates at times t 0 , t 0 + 1, t 0 + 2, ...) and replace integrals from the convergence analysis with Riemann sums. The measure α will be replaced in the Riemann sums by non-negative coefficients a i , with A k = k i=1 a i . As in the continuous-time case, the growth of A k as a function of k will determine the convergence rate. From this point on, to distinguish between the continuous-time and discrete-time cases, we will use t, τ ∈ R + to denote time in the continuous-time domain, and k, i ∈ Z + to denote discrete time points in the discrete-time domain. In particular, we will construct a sequence of primal-dual pairs (x (k) , z (k) ) that act as a discretization of the continuous curves (x (t) , z (t) ). Following the argument in the previous section, we can define a notion of upper bound U k and lower bound L k in the discrete case. We have U k def = f (x (k) ) and:
Discretization
The following theorem provides an expression for the discretization error accrued by the duality gap G k def = U k − L k . Its proof uses the same arguments as in the continuous case and is presented in the appendix for completeness.
Discretization
A k+1 G k be the discretization error in Equation (2.6). Then:
Discretization
In particular, we have
Discretization
We will now describe how axgd cancels out the discretization error by (approximately) implementing implicit Euler discretization ofẋ (t) . In Appendix B, we use our understanding of the discretization error from Theorem 2.3 to interpret agd as performing explicit (forward) Euler discretization ofẋ (t) and correcting the discretization error by performing an additional gradient step.
Discretization
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
Discretization
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 continuoustime amd, as shown in the next theorem. Ultimately, we will use this extra slack to trade-off the error arising from an approximate implicit discretization.
Discretization
Theorem 2.5. For the evolution of Equation (2.7), we have
Discretization
Proof. We bound the discretization error E k+1 in Theorem 2.4 for all k ≥ 1. By convexity, f (x (k+1) ) − f (x (k) ) ≤ ∇f (x (k+1) ), x (k+1) − x (k) , and therefore:
Discretization
The result follows by Theorem 2.4.
Convergence of axgd
A standard way to implement implicit Euler discretization in the solution of ODEs [6] is to replace the exact solution of the implicit equation with a small number of fixed point iterations of the same equation.
Convergence of axgd
In our case, the implicit equation can be written as:
Convergence of axgd
Two steps of the fixed-point iteration yield the following updates, which are exactly those performed by axgd:
Convergence of axgd
We can now analyze axgd as producing an approximate solution to the implicit Euler discretization problem. The following theorem 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" pointx (0) . This change is only important for bounding the initial gap G 1 ; everything else remains the same.
Convergence of axgd
Theorem 2.6. Consider the axgd algorithm as described in Equation (2.2), starting from an arbitrary pointx (0) with z (0) = ∇ψ(x (0) ) and A 0 = 0. Then the error from Theorem 2.4 is bounded by:
Convergence of axgd
Proof. As in the proof of Theorem 2.5, we use convexity to bound the error given by Theorem 2.4, followed by the definition of axgd :
Convergence of axgd
We now use the fact that a k+1 f (x (k) ) = z (k) −ẑ (k) together with the standard triangle-inequality for Bregman divergences (see Proposition 1.9) to show that:
Convergence of axgd
Combining the results of the two previous equations, we have the final bound on the error:
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 Theorem 2.6. The crux of the proof is that we can take sufficiently large steps while maintaining the error from Theorem 2.6 non-positive. In other words, we are able to move quickly through the continuous evolution of amd by taking large discrete steps. Theorem 2.7. Let f : X → R be an L-smooth convex function and let x (k) , z (k) ,x (k) ,ẑ (k) be updated according to the axgd algorithm in Equation (2.2), starting from an arbitrary initial pointx (0) with the following initial conditions: z (0) = ∇ψ(x (0) ) and A 0 = 0. Let ψ : X → R be σ-strongly convex. If the steps a k satisfy the inequality a k 2 A k ≤ σ L , then for all k ≥ 1,
Smooth Minimization with axgd
In particular, if a k = k+1 2 · σ L and ψ(x) = σ 2 x 2 , then:
Smooth Minimization with axgd
Proof. The proof follows directly by applying Theorem 2.6 and using L-smoothness of f and σ-strong convexity of ψ. In particular, by Cauchy-Schwartz inequality and smoothness:
Smooth Minimization with axgd
and, by Proposition 1.8
Smooth Minimization with axgd
From the definition of the steps,
Smooth Minimization with axgd
A k+1 (∇ψ * (ẑ (k) ) − ∇ψ * (z (k) )), and, therefore:
Smooth Minimization with axgd
where p = ∇ψ * (ẑ (k) ) − ∇ψ * (z (k+1) ) and q = ∇ψ * (z (k) ) − ∇ψ * (ẑ (k) ) . Since, for any non-negative p, q,
Smooth Minimization with axgd
which is true by the theorem assumptions. In particular, for a k = k+1
Smooth Minimization with axgd
It remains to bound G 1 . This a simple computation, shown in the appendix, which yields:
Acceleration with Noise-Corrupted Gradients
We now assume that we do not have the exact information about the gradients at queried points. Instead, we will assume that the gradients are corrupted by additive noise. This model is fundamentally different than the model considered in e.g., [4] . In [4] , it is assumed that a function f (.) is associated with a (δ, L) oracle, such that
Acceleration with Noise-Corrupted Gradients
x − x 2 that we normally get from f 's smoothness). Such a model seems more suitable for incorrectly specified functions (e.g., non-smooth functions treated as being smooth) rather than for inexact gradients, which is our focus.
Constructing a Lower Bound from Noise-Corrupted Gradients
Suppose that the sequence of queried points is x (1) , x (2) , ..., x (k) , ..., where each point x (k) is associated with an inexact gradient ∇f (x (k) ) = ∇f (x (k) ) + η k , where ∇f (x (k) ) is the true gradient and η k is the additive noise. Using convexity of f (.), ∀x ∈ X and any positive a 1 , ..., a k , where A k = k i=1 a i :
Constructing a Lower Bound from Noise-Corrupted Gradients
Therefore, using the same construction of the lower bound as in the case of exact gradients, we have:
Constructing a Lower Bound from Noise-Corrupted Gradients
We can observe that Λ k is equivalent to L k with the only difference of the exact gradients being replaced by the noisy gradients. In particular, if for some suitably chosen upper-bound U k , U k − Λ k ≤ , then the duality gap is bounded by
Constructing a Lower Bound from Noise-Corrupted Gradients
. This is good, because when we use noisy gradients, the lower bound is only corrupted by the average of the noise-distance to the optimum innerproduct. Moreover, since ∀i, x (i) is independent of the gradient at time i (and, therefore, independent of η i ), when η's elements have mean zero, 1 A k k i=1 a i η i , x * − x (i) also has mean equal to zero.
Upper Bound and the AGD Gap
Suppose that AGD is run using noisy gradient (the algorithm may be unaware of the noise). Observe that in this case z (k+1) = z (k) − a k+1 ∇f (x (k+1) ). As before, let the upper bound be U k = f (x (k) ), wherê
Upper Bound and the AGD Gap
Using that, by convexity of
Upper Bound and the AGD Gap
and repeating the same arguments as for the exact gradients (Appendix B, with the same assumptions as in Theorem B.1), it follows that: x (k+1) ) . From the definition ofx (k+1) :
Upper Bound and the AGD Gap
where the inequality comes from ∇f (x (k+1) ) = ∇f (x (k+1) ) + η k+1 and the assumption that ∀x,x:
Upper Bound and the AGD Gap
The bound (3.3) we get for the decrease in the duality gap is not encouraging for our techniques: each step contributes to additional noise, which even if it had a low mean, could still have a very high variance.
Upper Bound and the AGD Gap
Moreover,x (k+1) is not independent of η k+1 , sincex (k+1) depends on the noisy gradient ∇f (x (k+1) ).
Upper Bound and the AGD Gap
Note that the noise-accumulating component does not seem avoidable, since it comes from the inexact gradient within the minimization problem in M k+1 when we take a gradient step from x (k+1) . The only inequalities we have used in deriving the gap come from the convexity and second-order approximation of f (.), which are deterministic properties. Thus, it seems unlikely that the noise component from (3.3) can be removed without any changes to the algorithm (or techniques).
Upper Bound and the AXGD Gap
Consider now AXGD (Eq. (2.2)) with noisy gradients. Let U k = f (x (k) ) be the upper bound, same as in the case of exact gradients. Using the same arguments as in Section 2.3:
Upper Bound and the AXGD Gap
By convexity of f (.) and the definition of ∇f (x (k+1) ):
Upper Bound and the AXGD Gap
Observing that a k+1 ∇f (x (k) ) = z (k) −ẑ (k) , and using Prop. 1.9, we obtain a similar bound as in the case of exact gradients:
Upper Bound and the AXGD Gap
In particular, if we assume that the discretization error
Upper Bound and the AXGD Gap
is non-positive (see Theorems 2.6 and 2.7), we have:
Upper Bound and the AXGD Gap
Therefore, we have the following bound on the duality gap:
4)
Suppose that D = max x,x∈X x −x is bounded. If the elements of η k 's are chosen adversarially from the interval [− , ], then the error due to noise on the right-hand side of (3.4) is a random variable with mean at most 2 D and standard deviation at most 2 D. Now suppose that η k 's are vectors whose elements are independent Gaussians with zero mean and standard deviation . Unfortunately, because ∇ψ * (z (i) ) depends on both ∇f (x (i) ) and ∇f (x (i) ), it is correlated with both η i andη i , and thus we cannot obtain zero mean and O( D) standard deviation on the right-hand side. However, using Cauchy-Schwartz Inequality, we can bound the mean and the standard deviation of the error on the right-hand side of (3.4) with 2 √ nD, which means that in the case of AXGD when the diameter of the region is bounded, the noise cannot accumulate (i.e., it remains bounded as a function of , n, and D).
Experiments
We now illustrate the performance of agd and axgd for (i) an unconstrained problem over R n with the objective function f (x) = 1 2 Ax, x − b, x , and (ii) for the problem with the same objective and unit simplex as the feasible region, where A is the Laplacian of a cycle graph 3 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., [19] ). We also include Gradient Descent (gd) in the exact gap graphs for comparison.
Experiments
In the experiments, we take n = 100 and σ = L (= 4). We use the 2 norm in the gradient steps.
Experiments
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 G k = U k − L k 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.
Experiments
Acceleration and Noise. We now 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. When the region is unconstrained (top row in Fig. 2) , the algorithms may be taking large steps, which leads to a high error (see Section 3 for more details). gd overall exhibits higher tolerance to noise, since it takes steps based only on the last point, and thus it cannot accumulate noise from previous steps.
Experiments
In the case of the unit simplex region (bottom row in Fig. 2) , the diameter is one and thus the norm of the step size taken by any of the algorithms is bounded by one, which makes all the algorithms more tolerant to noise than in the unconstrained case. Since the points come from the unit simplex, the steps correspond to the vector rotation. In this case, averaging over steps helps, since it, intuitively, reduces the chance of high vector rotation due to noise. This explains the more stable behavior of axgd compared to agd and gd, which both take greedy gradient steps in each iteration.
Conclusion
We have presented a novel accelerated methodaxgd -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) non-smooth objectives with Hölder-continuous gradients, (iii) and non-smooth Lipschitz-continuous objectives [5] . In the experiments from Section 4, the method demonstrates favorable performance compared to agd when subjected to zero-mean Gaussian noise.
Conclusion
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 is 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/nonaccelerated algorithms in practice depending on the application. Finally, it is interesting 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 accelerated methods in practice.
Conclusion
A Proofs for Section 2 (Accelerated Extra-Gradient Descent) Proposition 2.1. Let x (t) and z (t) evolve according to (2.4) , starting at t 0 = 1 from an arbitrary point x (1) ∈ X and z (1) = ∇ψ(x (1) ). Then, ∀t ≥ 1:
Conclusion
Proof. The first part follows by integrating both sides of the first equation in (2.4) from 1 to t. For the second part, we can write the second equation in (2.4) equivalently as
Conclusion
Observing that
Conclusion
dt and integrating both sides from 1 to t, we get the required statement:
Conclusion
Finally, from Fact 1.6, it must be that ∇ψ(z (τ ) ) ∈ X for all τ ∈ [1, t] . As x (t) is a convex combination of x (1) ∈ X and 1
Conclusion
A k+1 G k be the discretization error in Equation (2.6). Then:
Conclusion
In particular, we have
Conclusion
Proof. Using the same arguments as in the construction of the lower bound in the continuous-time domain (beginning of the proof of Theorem 2.3), the lower bound in the discrete-time domain can be written as:
Conclusion
Letting z (k+1) = ∇ψ(x (1) ) − k+1 i=1 ∇f (x (i) ), we can further write:
Conclusion
Recalling that z (k) = ∇ψ(z (1) ) − k i=1 a i ∇f (x (i) ), we can bound (.) 2 as:
Conclusion
(.) 2 = ψ(∇ψ * (z (k+1) )) − ψ(∇ψ * (z (k) )) − z (k) , ∇ψ * (z (k+1) ) − ∇ψ * (z (k) ) = D ψ * (z (k) , z (k+1) ), and thus we arrive at:
Conclusion
which, adding and subtracting U k = f (x (k) ), gives
Conclusion
Remaining Proof of Theorem 2.7 (The Bound on G 1 ). To bound G 1 , we recall the definition of L 1 :
Conclusion
As a 1 = A 1 , x (1) = ∇ψ * (ẑ (0) ), and a 1 ∇f (x (0) ) = z (0) −ẑ (0) , using Proposition 1.9, we have that:
Conclusion
On the other hand, by smoothness of f (.) and the initial condition:
Conclusion
∇f (x (1) ) − ∇f (x (0) ), ∇ψ * (z (1) ) − x (1) ≥ −L ∇ψ * (ẑ (0) ) −x (0) ∇ψ * (z (1) ) − x (1) .
Conclusion
Finally, by Proposition 1.7 and the initial condition z (0) = ∇ψ(x (0) ), we have that D ψ * (z (0) , z (1) ) = D ψ (∇ψ * (z (1) ),x (0) ). Combining with (A.1), (A.2), and G 1 = U 1 − L 1 = f (x (1) ) − L 1 :
Conclusion
where we have used Proposition 1.7, x (1) = ∇ψ * (ẑ (0) ), and a 1 2
B Discretization for Nesterov's Algorithm
We now consider a different discretization method: namely, the explicit Euler discretization which leads to agd. This method allows us to perform one step per iteration (compared to axgd that performs two steps per iteration), at the cost of performing an additional gradient step to improve the upper bound. Observe that, by the definition of Bregman divergence:
B Discretization for Nesterov's Algorithm
We will further assume that we can use (B.1) to perform a gradient step, defined as:
B Discretization for Nesterov's Algorithm
With these assumptions on hand, we can show the following result:
B Discretization for Nesterov's Algorithm
Theorem B.1. Let x (1) ∈ X be an arbitrary initial point and let z (1) = ∇ψ(x (1) ) − f (x (1) ), and x (1) = Grad(x (1) ). For k ≥ 1, let x (k) , z (k) ,x (k) evolve according to (2.1). If, ∀x ∈ X :, 1 (1) ) and ∀k ≥ 1 :
B Discretization for Nesterov's Algorithm
Proof. The sequence of pointsx (1) ,x (2) , ... is used in the construction of the upper bounds. In particular, ∀k ≥ 1:
B Discretization for Nesterov's Algorithm
). The construction of the lower bound is as before, based on the points x (1) , x (2) , ... In particular:
B Discretization for Nesterov's Algorithm
where E k+1 = A k f (x (k+1) ) − f (x (k) ) − a k+1 ∇f (x (k+1) ), ∇ψ * (z (k+1) ) − x (k+1) − D ψ * (z (k) , z (k+1) ).
B Discretization for Nesterov's Algorithm
Therefore, to obtain the claimed result, we need to show that f (x (k+1) ) − E k+1/A k+1 ≥ f (x (k+1) ) = U k+1 .
B Discretization for Nesterov's Algorithm
By convexity, f (x (k) ) − f (x (k+1) ) ≤ ∇f (x (k+1) ),x (k) − x (k+1) . Additionally, as a k+1 ∇f (x (k+1) ) = z (k) − z (k+1) , we have that: D ψ * (z (k) , z (k+1) ) = ψ * (z (k) ) − ψ * (z (k+1) ) − a k+1 ∇f (x (k+1) ), ∇ψ * (z (k+1) ) . Therefore: E k+1 ≤ ∇f (x (k+1) ), A k+1 x (k+1) − A kx (k) + A k ψ * (z (k) ) − ψ * (z (k+1) ) .
(B.4)
We now focus on ψ * (z (k) ) − ψ * (z (k+1) ), which, using Fact 1.6 and the definition of a convex conjugate, we can write as: ψ * (z (k) ) − ψ * (z (k+1) ) = min x∈X − z (k+1) , x + ψ(x) − ψ(∇ψ * (z (k) )) + z (k) , ∇ψ * (z (k) ) . ψ(x) − z (k) , x =ψ(∇ψ * (z (k) )) − z (k) , ∇ψ * (z (k) ) + ∇ψ(∇ψ * (z (k) )) − z (k) , x − ∇ψ * (z (k) ) + D ψ (x, ∇ψ * (z (k) )) ≥ψ(∇ψ * (z (k) )) − z (k) , ∇ψ * (z (k) ) + D ψ (x, ∇ψ * (z (k) )), where the inequality follows by the first-order optimality condition implied by Fact 1.6. It follows that: ψ * (z (k) ) − ψ * (z (k+1) ) ≥ min x∈X z (k) − z (k+1) , x + D ψ (x, ∇ψ * (z (k) )) = min x∈X a k+1 ∇f (x (k+1) ), x + D ψ (x, ∇ψ * (z (k) )) .
(B.5)
Combining (B.5) and (B.4), we have:
(B.5)
∇f (x (k+1) ), a k+1 x + A kx (k) − A k+1 x (k+1) + D ψ (x, ∇ψ * (z (k) )) .
(B.5)
By the theorem's assumption, 1
(B.5)
(k) , x (k+1) )). Setting y = a k+1
(B.5)
A k+1 x + A k A k+1x
(B.5)
(k) ∈ X:
(B.5)
∇f (x (k+1) ), y − x (k+1) + ∆ f (y, x (k+1) ) = −f (x (k+1) ) + f (x (k+1) ), asx (k+1) = Grad(x (k+1) ) and by (B.1). Therefore:
(B.5)
, and, it follows that: U k+1 − L k+1 ≤ A k A k+1 (U k − L k ). To complete the proof, it remains to bound the initial gap U 1 − L 1 . To do so, it suffices to show that (1) ). From the definition of the lower bound and the initial conditions:
(B.5)
where the second inequality follows by the theorem assumptions.
(B.5)
Theorem B.2. Let f : X → R be an L-smooth convex function and let x (k) , z (k) ,x (k) evolve as in Theorem B.1. Let ψ : X → R be σ-strongly convex. If the steps a k satisfy a k 2 A k ≤ σ L , then, ∀k ≥ 1, f (x (k) ) − f (x * ) ≤ D ψ (x * ,x (1) ) A k . In particular, if a k = k+1 2 · σ L and ψ(x) = σ 2 x 2 , then:
(B.5)
f (x (k) ) − f (x * ) ≤ L (k + 1) 2 x * − x (1) 2 .
(B.5)
Proof. The proof follows by applying Theorem B.1 and by using the smoothness of f (.) and the strong convexity of ψ(.). In particular, the smoothness of f (.) gives D f (x,x) ≤ L 2 x −x 2 , ∀x,x ∈ X, while the strong convexity of ψ(.) gives D ψ (x,x) ≥ σ 2 x −x 2 ≥ σ L D f (x,x), ∀x,x ∈ X. Therefore,
(B.5)
where the last inequality follows by ∇ψ * (z (k) ) = A k+1
(B.5)
a k+1 x (k+1) − A k A k+1x
(B.5)
(k) and from the choice of a k 's.
(B.5)
Finally, choosing a k = k+1 2 · σ L and ψ(x) = σ 2 x 2 gives f (x (k) ) − f (x * ) ≤ L (k+1) 2 x * − x (1) 2 .

{'paper_id': '4678628', 'title': 'Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method', 's2_url': 'https://api.semanticscholar.org/CorpusID:4678628', 'source': 'S2ORC'}