Online Adaptive Methods, Universality and Acceleration

Introduction

The accelerated gradient method of Nesterov 1983 is one of the cornerstones of modern optimization. Due to its appeal as a computationally efficient and fast method, it has found use in numerous applications including: imaging (Chambolle and Pock 2011), compressed sensing (Foucart and Rauhut 2013), and deep learning (Sutskever et al. 2013), amongst other.

Despite these merits, accelerated methods are less prevalent in Machine Learning due to two major issues: (i) acceleration is inappropriate for handling noisy feedback, and (ii) acceleration requires the knowledge of the objective’s smoothness. While each of these issues was separately resolved in (Lan 2012; Hu et al. 2009; Xiao 2010), and respectively in (Nesterov 2015); it was unknown whether there exists an accelerated method that addresses both issues. In this work we propose such a method.

Concretely, Nesterov 2015 devises a method that obtains an accelerated convergence rate of $\mathcal{O}(1/T^{2})$ for smooth convex objectives, and a standard rate of $\mathcal{O}(1/\sqrt{T})$ for non-smooth convex objectives, over $T$ iterations. This is done without any prior knowledge of the smoothness parameter, and is therefore referred to as a universal Following Nesterov’s paper (Nesterov 2015), we say that an algorithm is universal if it does not require to know in advance whether the objective is smooth or not. Note that universality does not mean a parameter free algorithm. Specifically, Nesterov’s universal methods (Nesterov 2015) as well as ours are not parameter free. method. Nonetheless, this method uses a line search technique in every round, and is therefore inappropriate for handling noisy feedback. On the other hand, Lan 2012, Hu et al. 2009, and Xiao 2010, devise accelerated methods that are able to handle noisy feedback and obtain a convergence rate of $\mathcal{O}({1}/{T^{2}}+{\sigma}/{\sqrt{T}})$, where $\sigma$ is the variance of the gradients. However, these methods are not universal since they require the knowledge of both $\sigma$ and of the smoothness.

Conversely, adaptive first order methods are very popular in Machine Learning, withAdaGrad, (Duchi et al. 2011), being the most prominent method among this class. AdaGrad is an online learning algorithm which adapts its learning rate using the feedback (gradients) received through the optimization process, and is known to successfully handle noisy feedback. This renders AdaGrad as the method of choice in various learning applications. Note however, that AdaGrad (probably) can not ensure acceleration. Moreover, it was so far unknown whether AdaGrad is able to exploit smoothness in order to converge faster.

In this work we investigate unconstrained convex optimization. We suggest AcceleGrad (Alg. 2), a novel universal method which employs an accelerated-gradient-like update rule together with an adaptive learning rate à la AdaGrad. Our contributions,

We also present a new result regarding the AdaGrad algorithm. We show that in the case of stochastic optimization with a smooth expected loss, AdaGrad ensures an $\mathcal{O}(1/T+\sigma/\sqrt{T})$ convergence rate, where $\sigma$ is the variance of the gradients. AdaGrad does not require a knowledge of the smoothness, hence this result establishes the universality of AdaGrad (though without acceleration).

On the technical side our algorithm emoploys three simultaneous mechanisms: learning rate adaptation in conjunction with importance weighting, in the spirit of adaptive online learning algorithms (Duchi et al. 2011; Levy 2017), combined with an update rule that linearly couples two sequences, in the spirit of (Allen-Zhu and Orecchia 2017).

This paper is organized as follows. In Section 2 we present our setup and review relevant background. Our results and analysis for the offline setting are presented in Section 3, and Section 4 presents our results for the stochastic setting. In Section 5 we present our empirical study, and Section 6 concludes.

In his pioneering work, Nesterov 1983, establishes an accelerated rate for smooth convex optimization. This was later generalized in, (Nesterov 2003; Beck and Teboulle 2009), to allow for general metrics and line search.

In recent years there has been a renewed interest in accelerated methods, with efforts being made to understand acceleration as well as to extend it beyond the standard offline optimization setting.

An extension of acceleration to handle stochastic feedback was developed in, (Lan 2012; Hu et al. 2009; Xiao 2010; Cohen et al. 2018). Acceleration for modern variance reduction optimization methods is explored in, (Shalev-Shwartz and Zhang 2014; Allen-Zhu 2017), and generic templates to accelerating variance reduction algorithms are developed in, (Lin et al. 2015; Frostig et al. 2015). Scieur et al. 2016, derives a scheme that enables hindsight acceleration of non-accelerated methods. In (Yurtsever et al. 2015), the authors devise a universal accelerated method for primal dual problems. And the connection between acceleration and ODEs is investigated in, (Su et al. 2014; Wibisono et al. 2016; Flammarion and Bach 2015; Lessard et al. 2016; Aujol and Dossal 2017; Attouch and Chbani 2015). Universal accelerated schemes are explored in Nesterov 2015; Lan 2015; Neumaier 2016, yet these works do not apply to the stochastic setting. Alternative accelerated methods and interpretations are explored in, (Arjevani et al. 2016; Bubeck et al. 2015; Diakonikolas and Orecchia 2017).

Curiously, Allen-Zhu and Orecchia 2017, interpret acceleration as a linear coupling between gradient descent and mirror descent, our work builds on their ideas. Our method also relies on ideas from (Levy 2017), where universal (non-accelerated) procedures are derived through a conversion scheme of online learning algorithms.

Setting and Preliminaries

We focus on first order methods, i.e., methods that only require gradient information, and consider both smooth and non-smooth objectives. The former is defined below,

It is well known that with the knowledge of the smoothness parameter, $\beta$, one may obtain fast convergence rates by an appropriate adaptation of the update rule. In this work we do not assume any such knowledge; instead we assume to be given a bound on the distance between some initial point, $x_{0}$, and a global minimizer of the objective.

An access to the exact gradients of the objective is not always possible. And in many scenarios we may only access an oracle which provides noisy and unbiased gradient estimates. This Stochatic Optimization setting is prevalent in Machine Learning, and we discuss it more formally in Section 4.

The adaptive method presented in this paper is inspired by AdaGrad (Alg. 1), a well known online optimization method which employs an adaptive learning rate. The following theorem states AdaGrad’s guarantees Actually AdaGrad is well known to ensure regret guarantees in the online setting. For concreteness, Thm. 2.1 provides error guarantees in the offline setting. , (Duchi et al. 2011),

Let $\mathcal{K}$ be a convex set with diameter $D$. Let $f$ be a convex function. Then Algorithm 1 guarantees the following error;

Offline Setting

This section discusses the offline optimization setting where we have an access to the exact gradients of the objective. We present our method in Algorithm 2, and substantiate its universality by providing $O(1/T^{2})$ rate in the smooth case (Thm. 3.1), and a rate of $O(\sqrt{\log T/T})$ in the general convex case (Thm. 3.2). The analysis for the smooth case appears in Section 3.1 and we defer the proof of the non-smooth case to the Appendix.

AcceleGrad is summarized in Algorithm 2. Inspired by, (Allen-Zhu and Orecchia 2017), our method linearly couples between two sequences $\{z_{t}\}_{t},\{y_{t}\}_{t}$ into a sequence $\{x_{t+1}\}_{t}$. Using the gradient , $g_{t}=\nabla f(x_{t+1})$, these sequences are then updated with the same learning rate, $\eta_{t}$, yet with different reference points and gradient magnitudes. Concretely, $y_{t+1}$ takes a gradient step starting at $x_{t+1}$. Conversely, for $z_{t+1}$ we scale the gradient by a factor of $\alpha_{t}$ and then take a projected gradient step starting at $z_{t}$. Our method finally outputs a weighted average of the $\{y_{t+1}\}_{t}$ sequence.

Our algorithm coincides with the method of (Allen-Zhu and Orecchia 2017) upon taking $\eta_{t}=1/\beta$ and outputting the last iterate, ${y}_{T}$, rather then a weighted average; yet this method is not universal. Below we present our $\beta$-independent choice of learning rate and weights,

The learning rate that we suggest adapts similarly to AdaGrad. Differently from AdaGrad we consider the importance weights, $\alpha_{t}$, inside the learning rate rule; an idea that we borrow from (Levy 2017). The weights that we employ are increasing with $t$, which in turn emphasizes recent queries.

Next we state the guarantees of AcceleGrad for the smooth and non-smooth cases,

Assume that $f$ is convex and $\beta$-smooth. Let $\mathcal{K}$ be a convex set with bounded diameter $D$, and assume there exists a global minimizer for $f$ in $\mathcal{K}$. Then Algorithm 2 with weights and learning rate as in Equation (1) ensures,

Remark: Actually, in the smooth case we do not need a bound on the Lipschitz continuity, i.e., $G$ is only required in case that the objective is non-smooth. Concretely, if we know that $f$ is smooth then we may use $\eta_{t}={2D}{\left(\sum_{\tau=0}^{t}\alpha_{\tau}^{2}\|g_{\tau}\|^{2}\right)^{-1/2}}$, which yields a rate of $\mathcal{O}\left(\frac{\beta D^{2}\log(\beta D/\|g_{0}\|)}{T^{2}}\right)$.

Next we show that the exactly same algorithm provides guarantees in the general convex case (see proof in Appendix B),

Assume that $f$ is convex and $G$-Lipschitz. Let $\mathcal{K}$ be a convex set with bounded diameter $D$, and assume there exists a global minimizer for $f$ in $\mathcal{K}$. Then Algorithm 2 with weights and learning rate as in Equation (1) ensures,

Remark: For non-smooth objectives, we can modify AcceleGrad and provide guarantees for the constrained setting. Concretely, using Alg. 2 with a projection step for the $y_{t}$’s, i.e., $y_{t+1}=\Pi_{\mathcal{K}}(x_{t+1}-\eta_{t}g_{t})$, then we can bound its error by $f(\bar{y}_{T})-\min_{x\in\mathcal{K}}f(x)\leq\mathcal{O}\left({GD}\sqrt{\log T}/{\sqrt{T}}\right)$. This holds even in the case where minimizer over $\mathcal{K}$ is not a global one.

Here we provide a proof sketch for Theorem 3.1 (the full proof is deferred to Appendix A) . For brevity, we will use $z\in\mathcal{K}$ to denote a global mimimizer of $f$ which belongs to $\mathcal{K}$.

Recall that Algorithm 2 outputs a weighted average of the queries. Consequently, we may employ Jensen’s inequality to bound its error as follow,

Combining this with $\sum_{t=0}^{T-1}\alpha_{t}\geq\Omega(T^{2})$, implies that in order to substantiate the proof it is sufficient to show that, $\sum_{t=0}^{T-1}{\alpha_{t}}\left(f(y_{t+1})-f(z)\right)$, is bounded by a constant. This is the bulk of the analysis.

We start with the following lemma which provides us with a bound on $\alpha_{t}\left(f(y_{t+1})-f(z)\right)$,

Assume that $f$ is convex and $\beta$-smooth. Then for any sequence of non-negative weights $\{\alpha_{t}\}_{t\geq 0}$, and learning rates $\{\eta_{t}\}_{t\geq 0}$, Algorithm 2 ensures the following to hold,

Interestingly, choosing $\eta_{t}\leq 1/\beta$, implies that the above term, $\frac{\alpha_{t}^{2}}{2}\left(\beta-\frac{1}{\eta_{t}}\right)\|y_{t+1}-x_{t+1}\|^{2}$, does not contribute to the sum. We can show that this choice facilitates a concise analysis establishing an error of $\mathcal{O}(\beta D^{2}/T^{2})$ for $\bar{y}_{T}$ While we do not spell out this analysis, it is a simplified version of our proof for Thm. 3.1..

Note however that our learning rate does not depend on $\beta$, and therefore the mentioned term is not necessarily negative. This issue is one of the main challenges in our analysis. Next we provide a proof sketch of Theorem 3.1. The full proof is deferred to Appendix A.

Lemma 3.1 enables to decompose $\sum_{t=0}^{T-1}\alpha_{t}(f(y_{t+1})-f(z))$,

Next we separately bound each of the above terms.

Using the fact that $\{1/\eta_{t}\}_{t\in[T]}$ is monotonically increasing allows to show,

We will require the following property of the weights that we choose (Eq. (1)),

Where the last inequality uses Equation (5) (see full proof for the complete derivation).

Let us denote $\tau_{\star}:=\max\left\{t\in\{0,\ldots,T-1\}:2\beta\geq 1/\eta_{t}\right\}~.$ We may now split the term $\rm{(C)}$ according to $\tau_{\star}$,

where in the second line we use $2\beta\leq\frac{1}{\eta_{t}}$ which holds for $t>\tau_{\star}$, implying that $\beta-\frac{1}{\eta_{t}}\leq-\frac{1}{2\eta_{t}}$; in the last line we use $\|y_{t+1}-x_{t+1}\|=\eta_{t}\|g_{t}\|$.

Combining the bounds in Equations (4),(3.1),(3.1) into Eq. (3.1), and re-arranging gives,

We are now in the intricate part of the proof where we need to show that the above is bounded by a constant. As we show next this crucially depends on our choice of the learning rate. To simplify the proof sketch we assume to be using , $\eta_{t}=2D\left(\sum_{\tau=0}^{t}\alpha_{\tau}^{2}\|g_{\tau}\|^{2}\right)^{-1/2}$, i.e. taking $G=0$ in the learning rate. We will require the following lemma before we go on,

For any non-negative numbers $a_{1},\ldots,a_{n}$ the following holds:

Equipped with the above lemma and using $\eta_{t}$ explicitly enables to bound $(*)$,

where in the last inequality we have used the definition of $\tau_{\star}$ which implies that $1/\eta_{\tau_{\star}}\leq 2\beta$.

Using similar argumentation allows to bound the term $(**)$ by $\mathcal{O}(\beta D^{2}\log\left(\beta D/\|g_{0}\|\right))$. Plugging these bounds back into Eq. (8) we get,

Combining this with Eq. (2) and noting that $\sum_{t=0}^{T-1}\alpha_{t}\geq T^{2}/32$, concludes the proof. ∎

Stochastic Setting

This section discusses the stochastic optimization setup which is prevalent in Machine Learning scenarios. We formally describe this setup and prove that Algorithm 2, without any modification, is ensured to converge in this setting (Thm. 4.1). Conversely, the universal gradient methods presented in (Nesterov 2015) rely on a line search procedure, which requires exact gradients and function values, and are therefore inappropriate for stochastic optimization.

As a related result we show that the AdaGrad algorithm (Alg. 1) is universal and is able to exploit small variance in order to ensure fast rates in the case of stochastic optimization with smooth expected loss (Thm. 4.2). We emphasize that AdaGrad does not require the smoothness nor a bound on the variance. Conversely, previous works with this type of guarantees, Xiao 2010; Lan 2012, require the knowledge of both of these parameters.

We also assume that the internal coin tosses (randomizations) of the oracle are independent. It is well known that variants of Stochastic Gradient Descent (SGD) are ensured to output an estimate $\bar{x}_{T}$ such that the excess loss is bounded by $O(1/\sqrt{T})$ for the setups of stochastic convex optimization, Nemirovskii et al. 1983. Similarly to the offline setting we assume to be given a set $\mathcal{K}$ with bounded diameter $D$, such that there exists a global optimum of $f$ in $\mathcal{K}$.

The next theorem substantiates the guarantees of Algorithm 2 in the stochastic case,

Assume that $f$ is convex and $G$-Lipschitz. Let $\mathcal{K}$ be a convex set with bounded diameter $D$, and assume there exists a global minimizer for $f$ in $\mathcal{K}$. Assume that we invoke Algorithm 2 but provide it with noisy gradient estimates (see Eq. (9)) rather then the exact ones. Then Algorithm 2 with weights and learning rate as in Equation (1) ensures,

The analysis of Theorem 4.1 goes along similar lines to the proof of its offline counterpart (i.e., Thm. 3.2). The full proof is deferred to Appendix C.

It is well known that AdaGrad (Alg. 1) enjoys the standard rate of $\mathcal{O}(GD/\sqrt{T})$ in the stochastic setting. The next lemma demonstrates that: (i) AdaGrad is universal, and (ii) AdaGrad implicitly make use of smoothness and small variance in the stochastic setting.

Assume that $f$ is convex and $\beta$-smooth. Let $\mathcal{K}$ be a convex set with bounded diameter $D$, and assume there exists a global minimizer for $f$ in $\mathcal{K}$. Assume that we invoke AdaGrad (Alg. 1) but provide it with noisy gradient estimates (see Eq. (9)) rather then the exact ones. Then,

Next we provide a proof of the above theorem,

the last line uses the lemma below, which holds since we assume $\mathcal{K}$ contains a global minimum.

Eq. (10) enables to show, $\sum_{t=1}^{T}\mbox{\bf E}\left(f(x_{t})-\min_{x\in\mathcal{K}}f(x)\right)\leq 4\beta D^{2}+2\sigma D\sqrt{T}$. Combining this together with the definition of $\bar{x}_{T}$ and Jensen’s inequality concludes the proof. ∎

Experiments

In this section we compare AcceleGrad against AdaGrad (Alg. 1) and universal gradient methods (Nesterov 2015), focusing on the effect of tuning parameters and the level of adaptivity.

We consider smooth ($p=2$) and non-smooth ($p=1$) regression problems of the form

Universal gradient methods are based on an inexact line-search technique that requires an input parameter $\epsilon$. Moreover, these methods have convergence guarantees only up to $\frac{\epsilon}{2}$-suboptimality. For smooth problems, these methods perform better with smaller $\epsilon$. In stark contrast, for the non-smooth problems, small $\epsilon$ causes late adaptation, and large $\epsilon$ ends up with early saturation. Tuning is a major problem for these methods, since it requires rough knowledge of the optimal value.

Universal gradient method (also the fast version) provably requires two line-search iterations on average at each outer iteration. Consequently, it performs two data pass at each iteration (four for the fast version), while AdaGrad and AcceleGrad require only a single data pass.

The parameter $\rho$ denotes the ratio between $D/2$ and the distance between initial point and the solution. Parameter $D$ plays a major role on the step-size of AdaGrad and AcceleGrad. Overestimating $D$ causes an overshoot in the first iterations. AcceleGrad consistently overperforms AdaGrad in the deterministic setting. As a final note, it needs to be mentioned that the iterates $y_{t}$ of AcceleGrad empirically converge faster than the averaged sequence $\bar{y}_{T}$. Note that for AcceleGrad we always take $G=0$, i.e., use $\eta_{t}=2D\left(\sum_{\tau=0}^{t}\alpha_{\tau}^{2}\|g_{\tau}\|^{2}\right)^{-1/2}$.

We also study the stochastic setup (Appendix E), where we provide noisy gradients of $F$ based on minibatches. As expected, universal line search methods fail in this case, while AcceleGrad converges and performs similarly to AdaGrad.

Large batches: In Appendix E.3 we show results on a real dataset which demonstrate the appeal of AcceleGrad in the large-minibatch regime. We show that with the increase of batch size the performance of AcceleGrad verses the number of gradient calculations does not degrade and might even improve. This is beneficial when we like to parallelize a stochastic optimization problem. Conversely, for AdaGrad we see a clear degradation of the performance as we increase the batch size.

Conclusion and Future Work

We have presented a novel universal method that may exploit smoothness in order to accelerate while still being able to successfully handle noisy feedback. Our current analysis only applies to unconstrained optimization problems. Extending our work to the constrained setting is a natural future direction. Another direction is to implicitly adapt the parameter $D$, this might be possible using ideas in the spirit of scale-free online algorithms, Orabona and Pál 2015; Cutkosky and Orabona 2018.

Acknowledgement

The authors would like to thank Zalán Borsos for his insightful comments on the manuscript.

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no $725594$ - time-data). K.Y.L. is supported by the ETH Zurich Postdoctoral Fellowship and Marie Curie Actions for People COFUND program.

References

Appendix A Proofs for the Smooth Case (Thm. 3.1)

Here we provide the complete proof of Theorem 3.1, and of the related lemmas. For brevity, we will use $z\in\mathcal{K}$ to denote a global mimimizer of $f$ which belongs to $\mathcal{K}$.

Recall that Algorithm 2 outputs a weighted average of the queries. Consequently, we may employ Jensen’s inequality to bound its error as follow,

Combining this with $\sum_{t=0}^{T-1}\alpha_{t}\geq\Omega(T^{2})$, implies that in order to substantiate the proof it is sufficient to show that, $\sum_{t=0}^{T-1}{\alpha_{t}}\left(f(y_{t+1})-f(z)\right)$, is bounded by a constant. This is the bulk of the analysis.

We start by recalling Lemma 3.1 which provides us with abound on $\alpha_{t}\left(f(y_{t+1})-f(z)\right)$,

Assume that $f$ is convex and $\beta$-smooth. Then for any sequence of non-negative weights $\{\alpha_{t}\}_{t\geq 0}$, and learning rates $\{\eta_{t}\}_{t\geq 0}$, Algorithm 2 ensures the following to hold,

The proof Lemma 3.1 appears in Appendix A.1. Next we prove Theorem 3.1.

It is natural to separately bound each of the sums above.

Using the fact that $\{1/\eta_{t}\}_{t\in[T]}$ is monotonically increasing we may bound $\rm{(A)}$ as follows,

We will require the next lemma regarding the specific choice of the weights,

The following holds for the $\alpha_{t}$’s which are described in Eq. (1),

where in the fourth line we use Lemma A.1, we also use $\alpha_{0}^{2}-\alpha_{0}=0$ and $\alpha_{T-1}^{2}-\alpha_{T-1}\geq 0$.

Let us denote $\tau_{\star}$ as follows: $\tau_{\star}=\max\left\{t\in\{0,\ldots,T-1\}:2\beta\geq 1/\eta_{t}\right\}~.$ We may now split the last term as follows,

where in the third line we use $2\beta\leq\frac{1}{\eta_{t}}$ which holds for $t>\tau_{\star}$, implying that $\beta-\frac{1}{\eta_{t}}\leq-\frac{1}{2\eta_{t}}$; in the fourth line we use $\|y_{t+1}-x_{t+1}\|=\eta_{t}\|g_{t}\|$.

Combining the bounds in Eq. (A)-(A) into Eq. (A), we obtain,

This is the intricate part of the proof where we show that the above is bounded by a constant. This crucially depends on our choice of the learning rate, i.e., $\eta_{t}=2D\left(G^{2}+\sum_{\tau=0}^{t}\alpha_{\tau}^{2}\|g_{\tau}\|^{2}\right)^{-1/2}$. We require the following lemma (proof is found in Appendix A.4) before we go on,

For any non-negative numbers $a_{1},\ldots,a_{n}$ the following holds:

Equipped with the above lemma and using $\eta_{t}$ explicitly enables to bound $(*)$,

where in the second line we use the left hand nequality of Lemma A.2; in the fourth line we use the right hand inequality of Lemma A.2 ; and in the last line we have used the definition of $\tau_{\star}$ which implies that $1/\eta_{\tau_{\star}}\leq 2\beta$.

We will also require the following lemma (proof is found in Appendix A.5),

For any non-negative real numbers $a_{1},\ldots,a_{n}$,

Equipped with the above lemma and using $\eta_{t}$ explicitly enables to bound $(**)$,

where in the third line we used Lemma A.3, and in the last line we have used the definition of $\tau_{\star}$ which implies that $1/\eta_{\tau_{\star}}\leq 2\beta$. Combining Equations (A), (A) back into Eq. (17) and using Jensen’s inequality we are now ready to establish the final bound,

where we have used $\alpha_{t}\geq\frac{1}{4}(t+1)$ and therefore $\sum_{t=0}^{T-1}\alpha_{t}\geq T^{2}/32$.

A.1 Proof of Lemma 3.1

Our starting point is bounding $\alpha_{t}(f(x_{t+1})-f(z))$ which can be decomposed as follows,

where we use $g_{t}=\nabla f(x_{t+1})$ in conjunction with the gradient inequality. Let us now bound the terms in the above equation.

The next lemma enables to bound this term,

The proof of Lemma A.4 is provided in Appendix A.2.

We can now relate the first term in the above lemma to $y_{t+1}$. Define $v=\tau_{t}z_{t+1}+(1-\tau_{t})y_{t}\in\mathcal{K}$, and notice that $x_{t+1}-v=\tau_{t}(z_{t}-z_{t+1})$. Using this we may write,

where we use $\tau_{t}=1/\alpha_{t}$; also in the inequality we use the following equivalent form for the update rule of $y_{t+1}$,

this equivalence can be directly validated by finding the global optimum of the above objective and showing that it is obtained by choosing $y_{t+1}=x_{t+1}-\eta_{t}g_{t}$.

Combining Eq. (A.1) with Lemma A.4 gives,

Notice that re-arranging the relation between $x_{t+1},y_{t},z_{t}$ (recall $x_{t+1}=\tau_{t}z_{t}+(1-\tau_{t})y_{t}$) gives,

where we denote $r_{t}={(1-\tau_{t})}/{\tau_{t}}$. Also note that the smoothness of $f$ implies,

where second line uses the gradient inequality. We have also used $r_{t}=(1-\tau_{t})/{\tau_{t}}=\alpha_{t}-1$ (see Alg. 2).

Combining Equations (A.1), (22) and (A.1) we get,

A.2 Proof of Lemma A.4

Writing the update of the $z_{t}$’s explicitly we have,

Simplifying the above implies the following equivalent form,

where $\mathcal{R}_{z_{t}}(x):=\|x-z_{t}\|^{2}/2$. Since $z_{t+1}$ is a solution of the above minimization problem it satisfies the first order optimality conditions, i.e. $\forall z\in\mathcal{K}$,

which follows by the first order optimality conditions for $z_{t+1}$. We are now ready to complete the proof,

where the second line follows due to Eq. (26), and the second line is due to following lemma (which may be easily extended to general Bergman divergences),

Below we provide the proof of this lemma.

Noticing that $-\nabla\mathcal{R}_{v}(u)=v-u$ the lemma may be validated by a direct calculation. Indeed, $-\nabla\mathcal{R}_{v}(u)\cdot(u-z)=-v\cdot z+u\cdot z+u\cdot v-\|u\|^{2}$. Also,

A.3 Proof of Lemma A.1

For $t\leq 3$ we have $\alpha_{t}^{2}-\alpha_{t}=0$ and the lemma immediately follows. For $t>3$ we have,

A.4 Proof of Lemma A.2

First direction: We will prove this part by induction. The base case, $n=1$, immediately holds. For the induction step assume that the lemma holds for $n-1$ and let us show it holds for $n$. By the induction assumption,

where we denote $x:=a_{n}$ and $Z=\sum_{i=1}^{n}a_{i}$ (note that $x\leq Z$). Thus, in order to prove the lemma it is sufficient to show that,

which we do next. Multiplying both sides by $\sqrt{Z}$ we get that the above is equivalent to,

Taking the square of the above an re-ordering we get that the above is equivalent to,

Which holds in our case since $x=a_{n}\leq\sum_{i=1}^{n}a_{i}=Z$. This concludes the first part of the proof.

Second direction: The second inequality in the lemma is due to Lemma $7$ in (McMahan and Streeter 2010). For completeness we include their proof.

This part is also proved by induction. The base case, $n=1$, immediately holds. For the induction step assume that the lemma holds for $n-1$ and let us show it holds for $n$. By the induction assumption,

where we denote $x:=a_{n}$ and $Z=\sum_{i=1}^{n}a_{i}$ (note that $x\leq Z$). The derivative of the right hand side with respect to $x$ is $-\frac{1}{\sqrt{Z-x}}+\frac{1}{\sqrt{Z}}$ , which is negative for $x\geq 0$. Thus, subject to the constraint $x\geq 0$, the right hand side is maximized at $x=0$, and is therefore at most $2\sqrt{Z}$. This concludes the second part of the proof. ∎

A.5 Proof of Lemma A.3

We will prove the statement by induction over $n$. The base case $n=1$ holds since,

For the induction step, let us assume that the guarantee holds for $n-1$, which implies that for any $a_{1},\ldots,a_{n}\geq 0$,

The above suggests that establishing following inequality concludes the proof,

Using the notation $x=a_{n}/(1+\sum_{i=1}^{n-1}a_{i})$, Equation (27) is equivalent to the following,

However, it is immediate to validate that the function $M(x)=\log(x+1)-\frac{x}{1+x}$, is non-negative for any $x\geq 0$, which establishes the lemma. ∎

Appendix B Proofs for the General Convex Case (Thm. 3.2)

Here we provide the complete proof of Theorem 3.2, and of the related lemmas. For brevity, we will use $z\in\mathcal{K}$ to denote a global mimimizer of $f$ which belongs to $\mathcal{K}$.

Recall that Algorithm 2 outputs a weighted average of the queries. Consequently, we may employ Jensen’s inequality to bound its error as follow,

We start with the following lemma which provides us with a bound on $\alpha_{t}\left(f(y_{t+1})-f(z)\right)$,

Assume that $f$ is convex and $G$-Lipschitz. Then for any sequence of non-negative weights $\{\alpha_{t}\}_{t\geq 0}$, and learning rates $\{\eta_{t}\}_{t\geq 0}$, Algorithm 2 ensures the following to hold,

The proof of Lemma B.1 is provided in Appendix B.1. We are now ready to prove Theorem 3.2.

It is natural to separately bound each of the sums above.

Similarly to part $\rm{(a)}$ in the proof of Theorem 3.1 we can show the following to hold,

Note that by the definition of $\eta_{t}$ we have

where the second inequality uses Lemma A.2.

Writing down $\eta_{t}$ explicitly we get,

where we used $\forall t\leq T;\;\alpha_{t}\leq T$. The last line uses the following lemma (see proof in Appendix B.2),

Consider the $\alpha_{t}$’s used by our algorithm, i.e.,

And assume a sequence of non-negative numbers, $b_{0},b_{1},\ldots,b_{T-1}\in$. Then the following holds,

Combining the bounds on the different terms, Eq. (30)-(B), together with Eq. (B), we have,

Re-arranging and using the explicit expression for $\eta_{T-1}$ we get,

where we have used $\|g_{t}\|\leq G$, and also, $\alpha_{t}\leq t+1$ implying that $\sum_{t=0}^{T-1}\alpha_{t}^{2}\leq T^{3}$.

Using Jensen’s inequality we are now ready to establish the final bound,

where we have used $\alpha_{t}\geq\frac{1}{4}(t+1)$ and therefore $\sum_{t=0}^{T-1}\alpha_{t}\geq T^{2}/32$.

B.1 Proof of Lemma B.1

Our starting point is bounding $\alpha_{t}(f(x_{t+1})-f(z))$ which can be decomposed as follows,

where we use $g_{t}=\nabla f(x_{t+1})$ in conjunction with the gradient inequality. Let us now bound the terms in the above equation.

Similarly to the proof of Lemma 3.1 we can show the following to hold (see Eq. (22) in Lemma 3.1),

Combining the above with $\|x_{t+1}-y_{t+1}\|=\eta_{t}\|g_{t}\|$ implies,

Notice that re-arranging the relation between $x_{t+1},y_{t},z_{t}$ (recall $x_{t+1}=\tau_{t}z_{t}+(1-\tau_{t})y_{t}$) gives,

where we denote $r_{t}={(1-\tau_{t})}/{\tau_{t}}$. Using the above we get,

where second line uses the gradient inequality, in the third line we used $r_{t}=(1-\tau_{t})/{\tau_{t}}=\alpha_{t}-1$ (see Alg. 2); and in the last line we used $|f(y_{t+1})-f(x_{t+1})|\leq G\|y_{t+1}-x_{t+1}\|\leq G\eta_{t}\|g_{t}\|$, which follows by the $G$-Lipschitzness of $f$.

Combining Equations (B.1), (35), (B.1) we get,

Re-arranging the above equation and we get,

B.2 Proof of Lemma B.2

Let us define the following time variables,

By the definition of $T_{0}$, the following applies,

For the other time variables we can similarly show the following bounds, i.e., $\forall k\geq 1$,

Using the definition of the time variables together with Equations (37),(38) we get,

where in the third line we use $\sum_{\tau=0}^{t}\alpha_{\tau}^{2}b_{\tau}^{2}>4^{k-1}$ which by definition holds for any $T_{k-1}<t\leq T_{k}$.

Thus, we are left to show that $\sum_{k\geq 1}\sqrt{T_{k}-T_{k-1}}\leq 2\sqrt{\log T}\sqrt{T}$. To do so, first notice that the maximal value of $k$ is bounded as follows,

Thus, assuming $T\geq 2$ we have $k_{\max}\leq 3\log_{2}T$, and therefore,

Appendix C Proof of Theorem 4.1

For brevity we will not rehearse all of the details which are similar to the proof of the offline setting, but rather only emphasize the differences compared to the analysis of Theorem 3.2. First note the following which is analogous to Lemma B.1,

Assume that $f$ is convex and $G$-Lipschitz. Assume that we invoke Algorithm 2 but provide it with noisy gradient estimates (see Eq. (9)) rather then the exact ones. Then for any sequence of non-negative weights $\{\alpha_{t}\}_{t\geq 0}$, and learning rates $\{\eta_{t}\}_{t\geq 0}$, the following holds,

Taking expectations and using the above in conjunction with the definition of $\bar{y}_{T}$ and Jensen’s inequality concludes the proof. ∎

The proof follows similar lines to the proof of Lemmas B.1 and 3.1. Here we will highlight the changes due to the stochastic setting.

Our starting point is bounding $\alpha_{t}(f(x_{t+1})-f(z))$ which can be decomposed as follows,

Similarly to the proof of Lemma 3.1 we can show the following to hold (see Eq. (22) in Lemma 3.1),

Similarly to the proof of Lemma B.1 we can show the following to hold (see Eq. (B.1) therein),

Combining Equations (40), (41) and (C.1) we get,

Re-arranging the above equation and we get,

Appendix D Proof of Lemma 4.1

Taking $u=-\frac{1}{\beta}\nabla F(x)$ we get,

where in the last inequality we used $F(x^{*})\leq F(x+u)$ which holds since $x^{*}$ is the global minimum. ∎

Appendix E Additional Numerical Experiments

Here, we present numerical experiments on the stochastic setting, and on a practical variant that neglects the projection steps.

We consider the same problem setup as in Section 5. Rather than using the exact gradients, we compute the unbiased estimates evaluated by a single data point (i.e. minibatch of size $1$) The results are shown in Figure 2.

AdaGrad and AcceleGrad perform similar empirically for most of the parameter choices. AdaGrad overperforms AcceleGrad only for the smooth problem with $\rho=1$. This bahavior is caused by the projection step, and slightly increasing $D$ cures the problem for AcceleGrad.

Universal gradient methods (Nesterov 2015) are based on a line-search technique that relies on the exact first order oracle information. Thus, it is not so surprising that in practice these methods fail upon receiving stochastic feedback, and we therefore do not present their performance.

E.2 Numerical Experiments Neglecting the Projections

We observed that the methods work well in practice even if we ignore the projection step in the unconstrained setting. In some cases, this simple tweak may even improve the performance. We used the same test setup as in Section 5, and the results are shown in Figures 3 and 4 for the deterministic and stochastic settings respectively. Note that the method works also when we underestimate $D$.

E.3 Experiments with Large Minibatch

In this section we apply AcceleGrad to a real world stochastic optimization problem and compare its performance with AdaGrad. We examine the effect of minibatch size verses performance. The large minibatch regime is important when one likes to apply SGD using several machines in parallel. This is done by dividing the minibatch computation between the machines. Unfortunately, it is well known that the performance of SGD degrades with the increase of minibatch size $b$. Here, we show that AcceleGrad might be more appropriate in this case.

Concretely we consider the RCV1 available in the UCI repository website (https://archive.ics.uci.edu/ml/) dataset which is a binary labeled set with $20424$ datapoints samples and $47366$ features. We train a classifier for this dataset using logistic loss (smooth case) as well as using the hinge loss (SVM). We compare the performance of AcceleGrad with AdaGrad. For each method we examine several minibatch sizes, and observe the performance of each method verses the number of epochs (total number of gradients that we have computed).

The results for logistic regression appear in Figure 6. For AdaGrad we see that the performance degrades as we increase the minibatch size beyond $b=1000$. This actually agrees with theory that predicts a degradation with the increase of $b$.

For AcceleGrad we observe an interesting phenomenon: if we aim for a very small error (in this case smaller than $10^{-2}$) then as we increase the minibatch size the performance actually improves. The intuition behind this is the following: upon using small $b$ the gradients are noisy and both AcceleGrad and AdaGrad will obtain the slow $\mathcal{O}(1/\sqrt{T})$ rate, where $T$ is the number of iterations. However, as $b$ increases the gradients are becoming more accurate and AcceleGrad with obtain a rate approaching $\mathcal{O}(1/T^{2})$ while AdaGrad will approach $\mathcal{O}(1/T)$ rate. Now note that the number of gradient calculations $S$, depends on $b$ and $T$ as follows, $T=S/b~.$ Thus, for small minibatch, both methods will ensure a rate of $\mathcal{O}(\sqrt{b}/\sqrt{S})$, which clearly degrades with $b$. As $b$ increases AcceleGrad will obtain a rate approaching $\mathcal{O}(b^{2}/S^{2})$ while AdaGrad will approach $\mathcal{O}(b/S)$ rate.

We have observed similar behaviour when train an SVM (i.e., using hinge loss). This can be seen in Figure 5.