Better Mini-Batch Algorithms via Accelerated Gradient Methods

Introduction

We consider a stochastic convex optimization problem of the form

A parallel development has been the popularization of accelerated gradient descent methods . In a deterministic optimization setting and for general smooth convex functions, these methods enjoy a rate of $O(1/n^{2})$ (where $n$ is the number of iterations) as opposed to $O(1/n)$ using standard methods. However, in a stochastic setting (which is the relevant one for learning problems), the rate of both approaches have an $O(1/\sqrt{n})$ dominant term in general, so the benefit of using accelerated methods for learning problems is not obvious.

In this paper, we study the application of accelerated methods for mini-batch algorithms, and provide theoretical results, a novel algorithm, and empirical experiments. The main resulting message is that by using an appropriate accelerated method, we obtain significantly better stochastic optimization algorithms in terms of convergence speed. Moreover, in certain regimes acceleration is actually necessary in order to allow a significant speedups. The potential benefit of acceleration to mini-batching has been briefly noted in , but here we study this issue in much more depth. In particular, we make the following contributions:

We develop novel convergence bounds for the standard gradient method, which refines the result of by being dependent on $L(\mathbf{w}^{\star})=\inf_{\mathbf{w}\in\mathcal{W}}L(\mathbf{w})$, the expected loss of the best predictor in our class. For example, we show that in the regime where the desired suboptimality is comparable or larger than $L(\mathbf{w}^{\star})$, including in the separable case $L(\mathbf{w}^{\star})=0$, mini-batching does not lead to significant speed-ups with standard gradient methods.

We develop a novel variant of the stochastic accelerated gradient method , which is optimized for a mini-batch framework and implicitly adaptive to $L(\mathbf{w}^{\star})$.

We provide an analysis of our accelerated algorithm, refining the analysis of by being dependent on $L(\mathbf{w}^{\star})$, and show how it always allows for significant speed-ups via mini-batching, in contrast to standard gradient methods. Moreover, its performance is uniformly superior, at least in terms of theoretical upper bounds.

We provide an empirical study, validating our theoretical observations and the efficacy of our new method.

Preliminaries

We consider stochastic convex optimization problems over some convex domain $\mathcal{W}$. Here, we take $\mathcal{W}$ to be a convex subset of a Euclidean space, and use $\left\lVert{\mathbf{w}}\right\rVert$ to denote the standard Euclidean norm. In the Appendix, we state and prove the result in a more general setting, where $\mathcal{W}$ is a convex subset of a Banach space, and $\left\lVert{\mathbf{w}}\right\rVert$ can be an arbitrary norm.(subset of Euclidean case, see Appendix for the more general Banach space case), using an i.i.d. sample $z_{1},\ldots,z_{m}\in\mathcal{Z}$ drawn from some fixed distribution.

(for more general Banach space case, the norm on the left hand side is the dual norm). Let us denote

We wish to minimize $L(\mathbf{w})$ over convex domain $\mathcal{W}$. We will provide guarantees on $L(\mathbf{w})$ relative to $L(\mathbf{w}^{\star})$ at some $\mathbf{w}^{\star}\in\mathcal{W}$, where the guarantees also depend on $\left\lVert{\mathbf{w}^{\star}}\right\rVert$. We could choose $\mathbf{w}^{\star}:=\arg\min_{\mathbf{w}\in\mathcal{W}}L(\mathbf{w})$, though our results hold for any $\mathbf{w}^{\star}\in\mathcal{W}$, and in some cases we might choose to compete with a low-norm $\mathbf{w}^{\star}$ that is not optimal in $\mathcal{W}$.

The behavior of the accelerated gradient method also depends on the radius of $\mathcal{W}$, defined as:

We discuss two stochastic optimization approaches to deal with this problem: stochastic gradient descent (SGD), and accelerated gradient methods (AG). In a mini-batch setting, both approaches iteratively average sub-gradients with respect to several instances, and use this average to update the predictor. However, the update is done in different ways. In the Appendix, we also provide the form of the update in the more general mirror descent setting, where $\left\lVert{\mathbf{w}}\right\rVert$ is an arbitrary norm.

The stochastic gradient descent algorithm is summarized as Algorithm 1. In the pseudocode, $P_{\mathcal{W}}$ refers to the projection on to the ball $\mathcal{W}$ (under the Euclidean distance). The accelerated gradient method (e.g., ) is summarized as Algorithm 2.

In terms of existing results, for the SGD algorithm we have [4, Section 5.1]

whereas for an accelerated gradient algorithm, we have

where in both cases the dependence on $D,H$ and $\left\lVert{\mathbf{w}^{\star}}\right\rVert$ is suppressed. The above bounds suggest that, as long as $b=o(\sqrt{m})$, both methods allow us to use a large mini-batch size $b$ without significantly degrading the performance of either method. This allows the number of iterations $n=m/b$ to be smaller, potentially resulting in faster convergence speed. However, these bounds do not show that accelerated methods have a significant advantage over the SGD algorithm, at least when $b=o(\sqrt{m})$, since both have the same first-order term $1/\sqrt{m}$. To understand the differences between these two methods better, we will need a more refined analysis, to which we now turn.

Convergence Guarantees

The following theorems provide a refined convergence guarantee for the SGD algorithm and the AG algorithm, which improves on the analysis of by being explicitly dependent on $L(\mathbf{w}^{\star})$, the expected loss of the best predictor $\mathbf{w}^{\star}$ in $\mathcal{W}$.

For any $\mathbf{w}^{\star}\in\mathcal{W}$, using Stochastic Gradient Descent with a step size of $\eta=\min\left\{\frac{1}{2H},\tfrac{\sqrt{\frac{b\left\lVert{\mathbf{w}^{*}}\right\rVert^{2}}{L(\mathbf{w}^{\star})Hn}}}{1+\sqrt{\frac{H\left\lVert{\mathbf{w}^{*}}\right\rVert^{2}}{L(\mathbf{w}^{\star})bn}}}\right\}$, we have:

Note that the radius $D$ does not appear in the above bound, which depends only on $\left\lVert{\mathbf{w}^{\star}}\right\rVert$. This means that $\mathcal{W}$ could be unbounded, perhaps even the entire space, and a projection step for SGD is not really crucial. The step size, of course, still depends on $\left\lVert{\mathbf{w}^{\star}}\right\rVert$.

For any $\mathbf{w}^{\star}\in\mathcal{W}$, using Accelerated Gradient with step size parameters $\beta_{i}=\frac{i+1}{2}$, $\gamma_{i}=\gamma i^{p}$ where

Unlike for SGD, notice that the bound for the AG method above does depend on $D$, and a projection step is necessary for our analysis. However it is worth noting that $D$ only appears in terms of order at least $1/n$, and appears only mildly in the $1/(\sqrt{b}n)$ term, suggesting some robustness to the radius $D$.

We emphasize that Theorem 2 gives more than a theoretical bound: it actually specifies a novel accelerated gradient strategy, where the step size $\gamma_{i}$ scales polynomially in $i$, in a way dependent on the minibatch size $b$ and $L(\mathbf{w}^{\star})$. While $L(\mathbf{w}^{\star})$ may not be known in advance, it does have the practical implication that choosing $\gamma_{i}\propto i^{p}$ for some $p<1$, as opposed to just choosing $\gamma_{i}\propto i$ as in ), might yield superior results.

We now provide a proof sketch of Theorems 1 and 2. A more general statement of the Theorems as well as a complete proof can be found in the Appendix.

The proof for the stochastic gradient descent bound is mainly based on the proof techniques in and its extension to the mini-batch case in . Following the line of analysis in , one can show that

rearranging and setting $\eta$ appropriately gives the final bound. ∎

The proof of the accelerated method starts in a similar way as in . For the $\gamma_{i}$’a and $\beta_{i}$’s mentioned in the theorem, following similar lines of analysis as in we get the preliminary bound

Using smoothness, the self bounding property some manipulations, we can further get the bound

Using the $p$ as given in the theorem statement, and few simple manipulations, gives the final bound. ∎

Optimizing with Mini-Batches

To compare our two theorems and understand their implications, it will be convenient to treat $H$ and $D$ as constants, and focus on the more interesting parameters of sample size $m$, minibatch size $b$, and optimal expected loss $L(\mathbf{w}^{\star})$. Also, we will ignore the logarithmic factor in Theorem 2, since we will mostly be interested in significant (i.e. polynomial) differences between the two algorithms, and it is quite possible that this logarithmic factor is merely an artifact of our analysis. Using $m=nb$, we get that the bound for the SGD algorithm is

and the bound for the accelerated gradient method we propose is

To understand the implication these bounds, we follow the approach described in to analyze large-scale learning algorithms. First, we fix a desired suboptimality parameter $\epsilon$, which measures how close to $L(\mathbf{w}^{\star})$ we want to get. Then, we assume that both algorithms are ran till the suboptimality of their outputs is at most $\epsilon$. Our goal would be to understand the runtime each algorithm needs, till attaining suboptimality $\epsilon$, as a function of $L(\mathbf{w}^{\star}),\epsilon,b$.

To measure this runtime, we need to discern two settings here: a parallel setting, where we assume that the mini-batch gradient computations are performed in parallel, and a serial setting, where the gradient computations are performed one after the other. In a parallel setting, we can take the number of iterations $n$ as a rough measure of the runtime (note that in both algorithms, the runtime of a single iteration is comparable). In a serial setting, the relevant parameter is $m$, the number of data accesses.

To analyze the dependence on $m$ and $n$, we upper bound (5) and (6) by $\epsilon$, and invert them to get the bounds on $m$ and $n$. Ignoring logarithmic factors, for the SGD algorithm we get

First, let us compare the performance of these two algorithms in the parallel setting, where the relevant parameter to measure runtime is $n$. Analyzing which of the terms in each bound dominates, we get that for the SGD algorithm, there are 2 regimes, while for the AG algorithm, there are 2-3 regimes depending on the relationship between $L(\mathbf{w}^{\star})$ and $\epsilon$. The following two tables summarize the situation (again, ignoring constants):

SGD Algorithm Regime n $b\leq\sqrt{L(\mathbf{w}^{\star})m}$ $\frac{L(\mathbf{w}^{\star})}{\epsilon^{2}b}$ $b\geq\sqrt{L(\mathbf{w}^{\star})m}$ $\frac{1}{\epsilon}$

AG Algorithm Regime n $\epsilon\leq L(\mathbf{w}^{\star})^{2}$ $b\leq L(\mathbf{w}^{\star})^{1/4}m^{3/4}$ $\frac{L(\mathbf{w}^{\star})}{\epsilon^{2}b}$ $b\geq L(\mathbf{w}^{\star})^{1/4}m^{3/4}$ $\frac{1}{\sqrt{\epsilon}}$ $\epsilon\geq L(\mathbf{w}^{\star})^{2}$ $b\leq L(\mathbf{w}^{\star})m$ $\frac{L(\mathbf{w}^{\star})}{\epsilon^{2}b}$ $L(\mathbf{w}^{\star})m\leq b\leq m^{2/3}$ $\frac{1}{\epsilon\sqrt{b}}$ $b\geq m^{2/3}$ $\frac{1}{\sqrt{\epsilon}}$

From the tables, we see that for both methods, there is an initial linear speedup as a function of the minibatch size $b$. However, in the AG algorithm, this linear speedup regime holds for much larger minibatch sizesSince it is easily verified that $\sqrt{L(\mathbf{w}^{\star})m}$ is generally smaller than both $L(\mathbf{w}^{\star})^{1/4}m^{3/4}$ and $L(\mathbf{w}^{\star})m$. Even beyond the linear speedup regime, the AG algorithm still maintains a $\sqrt{b}$ speedup, for the reasonable case where $\epsilon\geq L(\mathbf{w}^{\star})^{2}$. Finally, in all regimes, the runtime bound of the AG algorithm is equal or significantly smaller than that of the SGD algorithm.

We now turn to discuss the serial setting, where the runtime is measured in terms of $m$. Inspecting (7) and (8), we see that a larger size of $b$ actually requires $m$ to increase for both algorithms. This is to be expected, since mini-batching does not lead to large gains in a serial setting. However, using mini-batching in a serial setting might still be beneficial for implementation reasons, resulting in constant-factor improvements in runtime (e.g. saving overhead and loop control, and via pipelining, concurrent memory accesses etc.). In that case, we can at least ask what is the largest mini-batch size that won’t degrade the runtime guarantee by more than a constant. Using our bounds, the mini-batch size $b$ for the SGD algorithm can scale as much as $L/\epsilon$, vs. a larger value of $L/\epsilon^{3/2}$ for the AG algorithm.

Finally, an interesting point is that the AG algorithm is sometimes actually necessary to obtain significant speed-ups via a mini-batch framework (according to our bounds). Based on the table above, this happens when the desired suboptimality $\epsilon$ is not much bigger then $L(\mathbf{w}^{\star})$, i.e. $\epsilon=\Omega(L(\mathbf{w}^{\star}))$. This includes the “separable” case, $L(\mathbf{w}^{\star})=0$, and in general a regime where the “estimation error” $\epsilon$ and “approximation error” $L(\mathbf{w}^{\star})$ are roughly the same—an arguably very relevant one in machine learning. For the SGD algorithm, the critical mini-batch value $\sqrt{L(\mathbf{w}^{\star})m}$ can be shown to equal $L(\mathbf{w}^{\star})/\epsilon$, which is $O(1)$ in our case. So with SGD we get no non-constant parallel speedup. However, with AG, we still enjoy a speedup of at least $\Theta(\sqrt{b})$, all the way up to mini-batch size $b=m^{2/3}$.

Experiments

While both datasets are relatively easy to classify, we also wished to understand the algorithms’ performance in the “separable” case $L(\mathbf{w}^{\star})=0$, to see if the theory in Section 4 holds in practice. To this end, we created an additional version of each dataset, where $L(\mathbf{w}^{\star})=0$, by training a classifier on the entire dataset and removing margin violations.

In all of our experiments, we used up to half of the data for training, and one-quarter each for validation and testing. The validation set was used to determine the step sizes $\eta$ and $\gamma_{i}$. We justify this by noting that our goal is to compare the performance of the SGD and AG algorithms, independently of the difficulties in choosing their stepsizes. In the implementation, we neglected the projection step, as we found it does not significantly affect performance when the stepsizes are properly selected.

In our first set of experiments, we attempted to determine the relationship between the performance of the AG algorithm and the $p$ parameter, which determines the rate of increase of the step sizes $\gamma_{i}$. Our experiments are summarized in Figure 1. Perhaps the most important conclusion to draw from these plots is that neither the “traditional” choice $p=1$, nor the constant-step-size choice $p=0$, give the best performance in all circumstances. Instead, there is a complicated data-dependent relationship between $p$, and the final classifier’s performance. Furthermore, there appears to be a weak trend towards higher $p$ performing better for larger minibatch sizes $b$, which corresponds neatly with our theoretical predictions.

In our next experiment, we directly compared the performance of the SGD and AG methods. To do so, we varied the minibatch size $b$ while holding the total amount of data used for training, $m=nb$, fixed. When $L(\mathbf{w}^{\star})>0$ (top row of Figure 2), the total sample size $m$ is high and the suboptimality $\epsilon$ is low (red and black plots), we see that for small minibatch size, both methods do not degrade as we increase $b$, corresponding to a linear parallel speedup. In fact, SGD is actually overall better, but as $b$ increases, its performance degrades more quickly, eventually performing worse than AG. That is, even in the least favorable scenario for AG (high $L(\mathbf{w}^{\star})$ and small $\epsilon$, see the tables in Section 4), it does give benefits with large enough minibatch sizes. Also, we see that even here, once the suboptimality $\epsilon$ is roughly equal to $L(\mathbf{w}^{\star})$, AG significantly outperforms SGD, even with small minibatches, agreeing with our the theory.

Turning to the case $L(\mathbf{w}^{\star})=0$ (bottom two rows of Figure 2), which is theoretically more favorable to AG, we see it is indeed mostly better, in terms of retaining linear parallel speedups for larger minibatch sizes, even for large data set sizes corresponding to small suboptimality values, and might even be advantageous with small minibatch sizes.

Summary

In this paper, we presented novel contributions to the theory of first order stochastic convex optimization (Theorems 1 and 2, generalizing results of and to be sensitive to $L\left(\mathbf{w}^{\star}\right)$), developed a novel step size strategy for the accelerated method that we used in order to obtain our results and we saw works well in practice, and provided a more refined analysis of the effects of minibatching which paints a different picture then previous analyses and highlights the benefit of accelerated methods.

A remaining open practical and theoretical question is whether the bound of Theorem 2 is tight. Following , the bound is tight for $b=1$ and $b\rightarrow\infty$, i.e. the first and third terms are tight, but it is not clear whether the $1/(\sqrt{b}n)$ dependence is indeed necessary. It would be interesting to understand whether with a more refined analysis, or perhaps different step-sizes, we can avoid this term, whether an altogether different algorithm is needed, or whether this term does represent the optimal behavior for any method based on $b$-aggregated stochastic gradient estimates.

References

Appendix A Generalizing to Different Norms

We now turn to general norms and discuss the generic Mirror Descent and Accelerated Mirror Descent algorithms. In this more general case we let domain $\mathcal{W}$ be some closed convex set of a Banach space equipped with norm $\left\lVert{\cdot}\right\rVert$. We will use $\left\lVert{\cdot}\right\rVert_{*}$ to represent the dual norm of $\left\lVert{\cdot}\right\rVert$. Further the $H$-smoothness of the loss function in this general case is takes the form that for any $z\in\mathcal{Z}$ and any $\mathbf{w},\mathbf{w}^{\prime}\in\mathcal{W}$,

The generalizations of the SGD and AG methods are summarized in Algorithms 3 and 4 respectively. The key difference between these and the Euclidean case is that the gradient descent step is replaced by a descent step involving gradient mappings of $R$ and its conjugate $R^{*}$ and the projection step is replaced by Bregman projection (projection to set minimizing the Bregman divergence to the point).

as long as $n\geq\max\{783K^{2},\frac{87K^{2}L(\mathbf{w}^{\star})}{HD^{2}}\}$, we have that :

Appendix B Complete Proofs

We provide complete proofs of Theorems 3 and 4, noting how Theorems 1 and 2 are specializations to the Euclidean case.

Due to $H$-smoothness of convex function $L$ we have that,

We now note that the update step can be written equivalently as

It can be shown that (see for instance Lemma 1 of )

Adding $\frac{1}{n-1}L(\mathbf{w}_{1})$ on both sides and removing $L(\mathbf{w}_{n})$ on the left we conclude that

Writing $\alpha=\frac{1}{1-\frac{16\eta HK^{2}}{b}}-1$, so that $\eta=\frac{b}{16HK^{2}}\left(1-\frac{1}{\alpha+1}\right)$ we get,

Now we shall always pick $\eta\leq\frac{b}{32HK^{2}}$ so that $\alpha\leq 1$ and so

or equivalently $\alpha=\min\left\{1,\sqrt{\frac{32HK^{2}R(\mathbf{w}^{\star})}{L(\mathbf{w}^{\star})bn}}\right\}$ we get,

Using Jensen’s inequality concludes the proof. ∎

For Euclidean case $R(\mathbf{w})=\frac{1}{2}\left\lVert{\mathbf{w}}\right\rVert_{2}^{2}$ and $K=\sqrt{\sup_{\mathbf{w}:\left\lVert{\mathbf{w}}\right\rVert_{2}\leq 1}\left\lVert{\mathbf{w}}\right\rVert^{2}}=1$. Plugging these in the previous theorem concludes the proof. ∎

B.2 Accelerated Mirror Descent

For the accelerated update rule, if the step sizes $\beta_{i}\in[1,\infty)$ and $\gamma_{i}\in(0,\infty)$ are chosen such that $\beta_{1}=1$ and for all $i\in[n]$

We now note that the update step 2 of accelerated gradient can be written equivalently as

It can be shown that (see for instance Lemma 1 of )

Multiplying throughout by $\beta_{i}\gamma_{i}$ we get

Owing to the condition that $\gamma_{i+1}(\beta_{i+1}-1)\leq\gamma_{i}\beta_{i}$ we have that

Using the above inequality repeatedly we conclude that

Plugging these back in Equation 10 we get :

Dividing throughout by $\gamma_{n}(\beta_{n}-1)$ concludes the proof.

Thus we have verified that the step sizes satisfy the conditions required by previous lemma. From the previous lemma we have that

Note that for any $i$ by smoothness, $a_{i}\leq L_{0}:=\frac{3}{2}HD^{2}+L(\mathbf{w}^{\star})$ Also notice that

$\sum_{i=n-M-1}^{n}A(i)\leq 1$. We shall ensure that the $\gamma$ we choose will satisfy the above condition. Now applying lemma B.3 we get that for any $M$,

Plugging this back in Equation 12 we conclude that

We now optimize over the choice of $M$ above by using

Ofcourse for the choice of $M$ to be valid we need that $n-M-2\leq n$ which gives our second condition on $\gamma$ which is

We shall try to now optimize the above bound w.r.t. $\gamma$, To this end set

We first need to verify that this choice of $\gamma$ satisfies the conditions in Equation 11 and 13. To this end, note that as for the condition in Equation 11,

and hence it can be easily verified that for $n\geq 3$, $\gamma\leq\frac{b}{64HK^{2}n^{p}}$. On the other hand to verify the condition in Equation 13, we need to show that

It can be verified that this condition is satisfied as long as,

So in effect as long as $n\geq 3$ and sample size $nb\geq\max\{783K^{2},\frac{87K^{2}L(\mathbf{w}^{\star})}{HD^{2}}\}$ the conditions are satisfied. Now plugging in this choice of $\gamma$ into the bound in Equation 14, we get

Recall that $L_{0}=\frac{3}{2}HD^{2}+L(\mathbf{w}^{\star})$. Now note that if $L(\mathbf{w}^{\star})\leq HK^{2}D^{2}/2$ then $L_{0}\leq 2HK^{2}D^{2}$, on the other hand if $L(\mathbf{w}^{\star})>HK^{2}D^{2}/2$ then $(HK^{2}R(\mathbf{w}^{\star}))^{2/3}L_{0}^{\frac{1}{3}}\leq\sqrt{4HK^{2}R(\mathbf{w}^{\star})L(\mathbf{w}^{\star})}$. Hence we can conclude that,

Since $n>783K^{2}$ and $R(\mathbf{w}^{\star})\leq D^{2}/2$ we can conclude that

For Euclidean case $R(\mathbf{w})=\frac{1}{2}\left\lVert{\mathbf{w}}\right\rVert_{2}^{2}$ and $K=\sqrt{\sup_{\mathbf{w}:\left\lVert{\mathbf{w}}\right\rVert_{2}\leq 1}\left\lVert{\mathbf{w}}\right\rVert^{2}}=1$. Plugging these in the previous theorem (along with appropriate step size) we get

The second inequality is a direct consequence of the fact that $\left\lVert{\mathbf{w}^{\star}}\right\rVert\leq D$. ∎

B.3 Some Technical Lemmas

Denote $K:=\sqrt{2\sup_{\mathbf{w}:\left\lVert{\mathbf{w}}\right\rVert\leq 1}R(\mathbf{w})}$, then for any $\mathbf{x}_{1},\ldots,\mathbf{x}_{b}$ mean zero vectors drawn iid from any fixed distribution,

where the step before last was due to Fenchel-Young inequality and $R^{*}$ is simply the convex conjugate of $R$. Now For any $i\in[b]$ define $S_{i}=R^{*}\left(\frac{\alpha}{b}\sum_{t=1}^{i}\mathbf{x}_{t}\right)$. We claim that

To see this note that since $R$ is $1$-strongly convex w.r.t. $\left\lVert{\cdot}\right\rVert$, by duality $R^{*}$ is $1$-strongly smooth w.r.t. $\left\lVert{\cdot}\right\rVert_{*}$ and so for any $i\in[b]$,

Taking expectation we get as claimed that :

Now using this above recursively (and noting that $S_{0}=0$ ) we conclude that

Consider a sequence of non-negative number $a_{1},\ldots,a_{n}\in[0,a_{0}]$ that satisfy

where $A$ is decreasing in $n$. For such a sequence, for any $m\in[n]$, as long as $A(i)\leq 1/2$ for any $i\geq n-m-1$ and $\sum_{i=n-m-1}^{n}A(i)\leq 1$ then

We shall unroll this recursion. Note that

We would now like to bound in general the term $\prod_{i=1}^{m-1}(1+A(n-i))$. To this extant note that,

Now assume $A(i)\leq 1/2$ for all $i\geq n-m-1$ so that $\log(1+A(n-i))\leq A(n-i)$. We get

Now if $\sum_{i=n-m-1}^{n}A(i)\leq 1$ then we can conclude that

Now if for each $i\leq n$, $a_{i}\leq a_{0}$ then we see that

Hence we conclude that as long as $\sum_{i=n-m-1}^{n}A(i)\leq 1$