AdaBatch: Efficient Gradient Aggregation Rules for Sequential and Parallel Stochastic Gradient Methods

Introduction

We consider large-scale supervised learning with sparse features, such as logistic regression, least-mean-square or support vector machines, with a very large dimension as well as a very large number of training samples with many zero elements, or even an infinite stream. A typical example of such use of machine learning is given by Ads click prediction where many sparse features can be used to improve prediction on a problem with a massive online usage. For such problems, stochastic gradient (SG) methods have been used successfully .

Sparse optimization requires the usage of CPUs and unlike other domains in machine learning, it did not benefit much from the ever increasing parallelism accessible in GPUs or dedicated hardware. The frequency of CPUs has been stagnating and we can no longer rely on the increase of CPU sequential computational power for SG methods to scale with the increase of data . New CPUs now rely on multi-core and sometimes multi-socket design to offer more power to its users. As a consequence, many attemps have been made at parallelizing and distributing SG methods . Those approaches can be classified in two types: (a) synchronous methods, that seek a speed-up while staying logically equivalent to a sequential algorithm, (b) asynchronous methods, which allow some differences and approximations from the sequential algorithms, such as allowing delays in gradient updates, dropping overlapping updates from different workers or allowing inconsistent reads from the model parameters. The latter such as Hogwild! have been more successful as the synchronization overhead between workers from synchronous methods made them impractical.

Such methods however do not lead to a complete provability of convergence for step-sizes used in practice, as most proof methods require some approximation . Proving convergence for such methods is not as straightforward as there is not anymore a clear sequence of iterates that actually exist in memory and conflicting writes to memory or inconsistent reads can occur. When increasing the number of workers it is also likely to increase how stale a gradient update is when being processed.

Synchronous approaches rely mostly on the usage of mini-batches in order to parallelize the workload . Increasing the size of the mini-batches will lead to a reduction of the variance of the gradients and the overall estimator. However for the same number of samples we will be doing $B$ times less iterations where $B$ is the size of the mini-batch. In practice one has to increase the learning rate (i.e., the step size) in order to compensate and achieve the same final accuracy as without mini-batches; however increasing the step size can lead to divergence and is sometimes impossible . The decrease in sample efficiency (i.e., a worse performance for a given number of processed training samples) is especially visible early during optimization and will lower over time as the algorithm reaches an asymptotic regime where using mini-batches of size $B$ will have the same sample efficiency as without mini-batches.

In this paper, we make the following contributions:

We propose in Section 2 a new merging operator for gradients computed over a mini-batch, to replace taking the average. Instead, for each mini-batch we count for each coordinate how many samples had a non zero gradient in that direction. Rather than taking the sum of all gradients and dividing by $B$ we instead divide each coordinate independently by the number of times it was non zero in the batch. This happens to be equivalent to reconditioning the initial problem in order to exploit its sparsity. Because each coordinate is still an average (albeit a stochastic one), the norm of the gradient will stay under control. In order to notice this effect, one has to look at the problem in a different geometry that accounts for the sparsity of the data. We also draw a parallel with Adagrad-type methods as our operator is equivalent to an implicit rescaling of the gradients per coordinate.

We show in Section 3 that this new merging rule outperforms regular mini-batch on sparse data and that it can have the same if not an improved sample efficiency compared to regular SGD without mini-batch.

We explain in Section 4 how this can be used to make synchronous parallel or distributed methods able to compete with asynchronous ones while being easier to study as they are logically equivalent to the sequential version.

We extend our results to variance-reduced SG methods such as SVRG in Section 5 and show similar gains are obtained when using AdaBatch.

We present in Section 6 experimental results to support our theoretical claims as well as a proof of concept that our new merging operator can make synchronous parallel SG methods competitive with asynchronous ones. We also extend our experiments to variance reduction methods like SVRG and show that AdaBatch yields similar improvement as in the case of SG methods.

This setup covers many practical cases, such as finite sum optimization where $f$ would have the uniform distribution over the sum elements or stochastic online learning where $f$ would be an infinite stream of training samples.

In the case of logistic regression, one would have for instance $\phi(X^{T}w)=\log(1+\exp{-YX^{T}w})$ for $Y\in\{-1,1\}$ the random label associated with the feature vector $X$.

We notice here that we have a specific structure to the geometry of $F$ which depends on $p$ and which need to be taken into account. The proof of (1.4) is given in the supplementary material (Section C.4).

Finally, we want not only to solve problems (1.2) or (1.3), but to be able to do so while using $W$ workers. Those workers can either be running on the same machine with shared memory or in a distributed fashion.

2 Related work

There have been several approaches for parallelizing or distributing SG methods.

Parallelized stochastic gradient descent. This approach described by consists in splitting a dataset in $W$ different parts and averaging the model obtained by $W$ independent workers. Model averaging always reduces the variance of the final estimator but the impact on the bias is not as clear. For sparse optimization this approach does not in practice outperform a purely sequential algorithm .

Delayed stochastic gradient descent. The effect of delay for constant step-size stochastic gradient descent has been studied by . Allowing for delay will remove the need for synchronization and thus limit the overhead when parallelizing. The main result of concludes that there is two different regimes. During the first phase, delay will not help convergence, although once the asymptotic terms are dominating, a theoretical linear speedup with the number of worker is recovered.

Using mini-batches is a popular alternative for parallelizing or distributing SGD. In , the reduction of the variance of the gradient estimate is used to prove improvement in convergence. Our theoretical and practical results show that in the case of sparse learning, mini-batch do not offer an improvement during the first stage of optimization. We believe our merging rule is a simple modification of mini-batch SGD that can considerably improve convergence speed compared to regular mini-batch.

The case of averaged stochastic gradient descent with constant step size for least-squares regression has been studied in much detail and in that case it is possible to get an explicit expression for the convergence of the algorithm . During the first phase of optimization, in order to achieve the same accuracy after a given number of samples, the step size must be increased proportionally to the batch size which is possible up to a point after which the algorithm will diverge. We draw the same conclusions in a more generic case in Section 3.

In , a specific subproblem is solved instead of just averaging the gradients in a mini-batch. However, solving a subproblem is much more complex to put in place and requires the tuning of extra parameters. Our method is very simple as it only requires a per-coordinate rescaling of the gradients and does not require any parameter tuning.

Hogwild! is a very simple parallel SG method. Each worker processes training examples completely in parallel, with no synchronization and accessing the same model in memory . The overhead is minimal, however the theoretical analysis is complex. New proof techniques have been introduced to tackle those issues . Our contribution here is to make synchronous methods almost as fast as Hogwild!. This has an interest for cases where Hogwild! cannot perform optimally, for instance with a mixture of dense and sparse features, or in the distributed setting where memory cannot be shared. Hogwild! has inspired parallel versions for SDCA, SVRG and SAGA . AdaBatch can similarly be extended to those algorithms and we provide proof for SVRG. Cyclades builds on Hogwild!, assigning training samples to specific workers using graph theory results to remove conflicts.

Adagrad. Adagrad performs a per coordinate rescaling dependent on the size of past gradients that has proven to be highly efficient for sparse problem, besides it can be combined with Hogwild! for parallel optimization . Adagrad rescaling is similar in nature to the one performed by AdaBatch. Adagrad has a step size going to 0 with the number of iterations which gives good convergence properties for various problems. On the other hand, AdaBatch works with a wider range of methods such as SVRG. Constant step size has proven useful for least-mean-square problems or in the field of deep learning .

AdaBatch for SGD

Plugging (2.2) into (2.1) yields the regular SGD mini-batch algorithm with constant step size $\gamma$ and batch size $B$.

Instead of taking the average of all gradients, for each coordinate we make an average but taking only the non zero gradients into account. Let us take a coordinate $k\in[d]$; if $p^{(k)}$ is close to 1, then the AdaBatch update for this coordinate will be the same as with regular mini-batch with high probability. On the other hand, if $p^{(k)}$ is close to zero, the update of AdaBatch will be close to summing the gradients instead of averaging them. Adding updates instead of averaging has been shown to be beneficial in previous work such as in CoCoa+ , a distributed SDCA-inspired optimization algorithm. We observed experimentally that in order to achieve the same performance with mini-batch compared to AdaBatch, one has to take a step size that is proportional to $B$. This will boost convergence for less frequent features but can lead to divergence when $B$ increases because the gradient for frequent features will get too large. Our method allows to automatically and smoothly move from summing to averaging depending on how frequent a feature is.

Interestingly, we now have a gradient that is equivalent to a reconditioning of $F^{\prime}$. We can draw here a parallel with Adagrad which similarly uses per-coordinate step sizes. When using Adagrad, the update rule becomes

The goal is to have an adaptative step size that will have a larger step size for coordinate for which the gradients have a smaller magnitude. One should note a few differences though:

Adagrad relies on past informations and updates the reconditioning at every iteration. It works without any particular requirement on the problem. Adagrad also forces a decaying step size. Although this give Adagrad good convergence properties, it is not always suitable, for instance when using variance reduction methods such as SVRG where the step size is constant.

On the other side, the AdaBatch scaling stays the same (in expectation) through time and only tries to exploit the structure coming from the sparsity of the problem. It does not require storing extra information and can be adapted to other algorithms such as SVRG or SAGA.

When used together with mini-batch, Adagrad will act similarly to AdaBatch and maintain the same sample efficiency automatically even when increasing the batch size.

Convergence results

We make the following assumptions which generalize our observation from Section 1.1 for sparse linear prediction.

The Hessians $F^{\prime\prime}$ (resp. $f^{\prime\prime}$) of $F$ (resp. $f$) are such that:

Let $w_{*}:=\operatorname*{arg\,min}_{w\in\mathcal{D}}F(w)$,

Detailed proofs of the following results are given in the supplementary material (Section C). Our proof technique is based on a variation from the one introduced by . It requires an extra projection step on $\mathcal{D}$. In practice however, we did not require it for any reasonable step size that does not make the algorithm diverge and our bounds do not depend on $\mathcal{D}$ because of (3.2). The results are summarized in Table 1. We use a constant step size as a convenience for comparing the different algorithms. It is different but equivalent to using a decreasing step size (see just before Corollary 1). For instance, if we know the total number of iterations is $n\gg 1$, taking $\gamma=\frac{6\log(n)}{n}$, the bias term is approximately $\frac{\mu}{4\log(n)n^{2}}$. The variance term which is proportional to $\gamma$ is a $O(\log(n)/n)$ which is the usual rate for strongly convex SGD.

We notice that the final error is made of two terms, one that decreases exponentially fast and measures how quickly we move away from the starting point and one that is constant, proportional to $\gamma$ and that depends on the stochastic noise around the optimal value. We will call the former the bias term and the latter the variance term, following the terminology introduced by . The bias term decreases exponentially fast and will be especially important during the early stage of optimization and when $\mu$ is very small. The variance term is the asymptotically dominant term and will prevail when close to the optimum. In practical applications, the bias term can be the most important one to optimize for . This has also been observed for deep learning, where most of the optimization is spent far from the optimum .

Wild AdaBatch

We now have a SG method trick that allows us to increase the size of mini-batches while retaining the same sample efficiency. Intuitively one can think of sample efficiency as how much information we extract from each training example we process i.e. how much the loss will decrease after a given number of samples have been processed. Although it is easy to increase the number of samples processed per seconds when doing parallel optimization, this will only lead to a true speedup if we can retain the same sample efficiency as sequential SGD. If the sample efficiency get worse, for instance when using regular mini-batch, then we will have to perform more iterations to reach the same accuracy, potentially canceling out the gain obtained from parallelization.

When using synchronous parallel SG methods such as , using large mini-batches allows to reduce the overhead and thus increase the number of samples processed per second. SGD with mini-batches typically suffers from a lower sample efficiency when $B$ increases. It has been shown to be asymptotically optimal , however our results summarized in Section 3 show that in cases where the step size cannot be taken too large, it will not be able to achieve the same sample efficiency as SGD without mini-batch.

We have shown in Section 3 that for sparse linear prediction, AdaBatch can achieve the same sample efficiency as for $B=1$. Therefore, we believe it is a better candidate than regular mini-batch for parallel SGD. In Section 6, we will present our experimental results for Wild AdaBatch, a Hogwild! inspired, synchronous SGD algorithm. Given a batch size $B$ and $W$ workers, they will first compute in parallel $B$ gradients, wait for everyone to be done and then apply the updates in parallel to update $w_{n}$. The key advantage here is that thanks to the synchronization, analysis of this algorithm is easier. We have a clear sequence of iterates $w_{n}$ in memory and there is no delay or inconsistent read. It is still possible that during the update phase, some updates will be dropped because of overlapping writes to memory, but that can be seen simply as a slight decrease of the step size for those coordinate. In practice, we did not notice any difference with the sequential version of AdaBatch.

AdaBatch for SVRG

SVRG is a variance-reduced SG method that has a linear rate of convergence on the training error when $F$ is given by a finite mean of functions $F:=\frac{1}{N}\sum_{i\in[N]}f_{i}$. This is equivalent to $f$ following the uniform law over the set $\{f_{1},\ldots,f_{N}\}$. SVRG is able to converge with a constant step size. To do so, it replaces the gradient $f^{\prime}(w)$ by $f^{\prime}(w)-f^{\prime}(y)+F^{\prime}(y)$ where $y$ is updated every epoch (an epoch being $m$ iterations where $m$ is a parameter to the algorithm, typically of the order of the number of training samples). Next, we show the difference between regular mini-batch SVRG and AdaBatch SVRG and give theoretical results showing improved convergence for the latter.

We now only assume that $F$ verifies the following inequalities for $\mu>0$, almost surely,

with $g_{s,n}$ the SVRG update based on $(f_{s,n,b})_{b\in[B]}$ i.i.d. samples of $f$. Let us introduce

For any dimension $k$ such that $D^{(k)}_{s,n}\neq\varnothing$ we have

and for $D^{(k)}_{s,n}=\varnothing$ we take $g_{s,n}^{(k)}:=0$. Regular mini-batch SVRG is recovered for $C_{s,n}^{(k)}:=B$. On the other hand, AdaBatch SVRG is obtained for $C_{s,n}^{(k)}:=\left|D^{(k)}_{s,n}\right|$. One can note that we used a similar trick to the one in in order to preserve the sparsity of the updates.

For both updates, there exists a choice of $\gamma$ and $m$ such that

Experimental results

We have implemented both Hogwild! and Wild AdaBatch and compared them on three datasets, spamhttp://plg.uwaterloo.ca/~gvcormac/trecspamtrack05/trecspam05paper.pdf, news20https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html, and url . Spam has 92,189 samples of dimension 823,470 and an average of 155 active features per sample. News20 has 19,996 samples of dimension 1,355,191 and an average of 455 active features per example. Finally, url has 2,396,130 samples of dimension 3,231,961 and an average of 115 active features per example.

We implemented both in C++ and tried our best to optimize both methods. We ran them on an Intel(R) Xeon(R) CPU E5-2680 v3 @ 2.50GHz with 24 CPUs divided in two sockets. Each socket contains 12 physical CPUs for 24 virtual ones. In our experiments though, it is better to keep the number of threads under the number of actual physical CPUs on a single socket. We restricted each experiment to run on a single socket in order to prevent NUMA (non uniform memory access) issues. For all the experiments we ran (and all methods), we perform a grid search to optimize the step size (or the main parameter of Adagrad). We then report the test error on a separate test set.

Wild AdaBatch. We trained each algorithm for logistic regression with 5 passes over the dataset, 1 pass only in the case of url. We normalized the features so that each sample has norm 1. For each dataset, we evaluate 3 methods: Wild AdaBatch (AB) and Wild mini-batch SGD (MB, the same as AB but with the regular average of the gradients) as well as Hogwild! (HW) for various numbers of workers $W$. For AdaBatch and mini-batch SGD, the batch size is set to $B=10W$ for news20 and $B=50$ for url and spam which was giving a better speedup for those datasets. We take $W$ going from $1$ to $12$, which is the maximum number of physical CPUs on a single socket on our machine. We also evaluate purely sequential SGD without mini-batch (SEQ).

We only present here the result for news20. The figures for the other datasets can be found in the supplementary material Section E. In Figure 1 we show the convergence as a function of the wall-clock time. In Figure 3, we give the wall-clock time to reach a given test error (where our method is achieving close to a linear speed-up) and the number of processed samples per seconds. On news20, the gain in sample efficiency actually allows Wild AdaBatch to reach the goal the fastest, even though Wild AdaBatch can process less samples per seconds than Hogwild!, thanks to its improved sampled efficiency.

Comparison with Adagrad. We compare AdaBatch with Adagrad for various batch-size on Figure 4 when trained with a fixed number of samples, so that when $B$ increases, we perform less iterations. On the url dataset, Adagrad performs significantly better than AdaBatch, however we notice that as the batch-size increases, the gap between AdaBatch and Adagrad reduces. On the spam dataset with the least-mean-square loss, constant step size SGD performs better than Adagrad. We believe this is because Adagrad is especially well suited for non strictly convex problems. For strictly convex problem though, constant step size SGD is known to be very efficient . We also plotted the performance of constant step size regular mini-batch SGD. In all cases, regular mini-batch scales very badly as the batch size increases. We fine tune the step size for each batch size and observed the regular mini-batch will take a larger step size for small batch sizes, that allows to keep roughly the same final test error. However, when the batch size increases too much, this is no longer possible as it makes optimization particularly unstable, thus leading to a clear decrease in sample efficiency. Finally, AdaBatch can even improve the sample complexity when increasing $B$. We believe this comes from the variance reduction of the gradient for features that occurs more than once in a mini-batch, which in turn allows for a larger step size.

Conclusion

We have introduced a new way of merging gradients when using SG methods with mini-batches. We have shown both theoretically and experimentally that this approach allows to keep the same sample efficiency as when not using any mini-batch and sometimes even improve it. Thanks to this feature, AdaBatch allowed us to make synchronous parallel SG methods competitive with Hogwild!. Our approach can extend to any SG methods including variance-reduced methods. Although not explored yet, we also believe that AdaBatch is promising for distributed optimization. In such a case, memory is no longer shared so that Hogwild! cannot be used. Distributed mini-batch or SGD with delay have been used in such case ; AdaBatch is a few line change for distributed mini-batch which could vastly improve the convergence of those methods.

We thank Nicolas Flammarion, Timothée Lacroix, Nicolas Usunier and Léon Bottou for interesting discussions related to this work. We acknowledge support from the European Research Council (SEQUOIA project 724063).

Supplementary material

We present in Section A the pseudocode for AdaBatch and Wild AdaBatch. In Section B, we give two lemma from which we can derive the expectation and variance of the AdaBatch gradient update. In Section C we study the convergence of regular mini-batch and AdaBatch for SGD as well as the convergence of reconditionned SGD. In Section D we compare the convergence of regular mini-batch and AdaBatch for SVRG. Finally in Section E we give convergence plots for Wild AdaBatch and SVRG on the remaining datasets that were not included in the main paper.

A Algorithms

We present two possible uses of AdaBatch. Algorithm 1 counts for each mini-batch the number of time each feature is non zero and use that to recondition the gradient. This is the algorithm that we study in Section 2 of the main paper.

B Expectation and variance of the AdaBatch update

so that we have the recurrence rule for SGD

Taking $Q\sim\mathcal{B}(p)$ a Bernoulli of parameter $p$ independent from $Z^{+}$, one can readily notice that $Z\sim QZ^{+}$. We thus take $N$ i.i.d. such copies $(Q_{i},Z_{i}^{+})_{i\in[N]}$. Let us take any $q\in\{0,1\}^{N}$ so that $\left|q\right|:=\sum_{i\in[N]}q_{i}>0$,

as $\sum_{k\in[N]}\binom{N}{k}p^{k}(1-p)^{N-k}\frac{1}{k}\leq 1-(1-p)^{N}$ which gives us (7.5) and conclude this proof. ∎

We now present an improved bound for the second order moment of $Z$ that can be better if than the previous one in the case where $Np$ is large enough. Although we will not provide a full proof of convergence using this result for simplicity, we will comment on how this impact convergence in the proof of theorem 2.

With the same notation as in lemma 1, if $Np\geq 5$ we have

We reuse the notation from the proof of Lemma 1. Let us define $M:=\left|Q\right|$ which follows a binomial law of parameter $N$ and $p$. Using Chernoff’s inequality, we have for any $k\leq Np$,

We have as $p\geq 5/N$ and using standard analysis techniques,

Plugging this result into (7.5), we immediately have

C Proof of convergence of AdaBatch and mini-batch SGD

We will first give a convergence result for the regular mini-batch SGD, which is adapted from .

The hessian $F^{\prime\prime}$ of $F$ is bounded from above and below as:

with $\mu>0$ so that $f$ is $\mu$ strongly convex and $L$ smooth over $\mathcal{D}$.

We assume $f^{\prime\prime}$ is almost surely bounded,

Let $w_{*}:=\operatorname*{arg\,min}_{w\in\mathcal{D}}F(w)$,

This does not limit us to the case of globally strongly convex functions $F$ as we only require it to be strongly convex on a compact subset that contains the global optimum $w_{*}$. In practice, this is often going to be the case, even when using a non strictly convex loss such as the logistic loss as soon as the problem is not perfectly separable, i.e., there is no hyperplane that perfectly separates the classes we are trying to predict.

where $\Pi_{\mathcal{D}}[w]:=\operatorname*{arg\,min}_{x\in\mathcal{D}}\left\|w-x\right\|^{2}$ is the orthogonal projection on the set $\mathcal{D}$. This extra step of projection is required for this proof technique but experience shows that it is not needed.

Introducing $\bar{w}_{N}$ allows for an easier comparison directly on the objective function. This is made for qualitative analysis and we do not in practice perform this averaging.

We can see that the error given by (7.16) can be composed in two terms, one that measure how quickly we move away from the starting point and the second that depends on the stochastic noise around the optimum. We will call the former the bias term and the latter the variance term, following the terminology introduced by .

We introduce $\forall n\in[N],\mathcal{F}_{n-1}$ the $\sigma$-field generated by $(f_{i,b})_{i\in[n-1],b\in[B]}$. Let us take $n\in[N]$ and introduce $\eta_{n}:=w_{n}-w_{*}$ and $g_{n}:=\frac{1}{B}\sum_{b\in[B]}f^{\prime}_{n,b}(w_{n-1})$. We then proceed to bound $\left\|\eta_{n}\right\|^{2}$,

Taking the expectation while conditioning on $\mathcal{F}_{n-1}$ we obtain

As $F^{\prime\prime}\preceq L\operatorname{Id}$ and using the co-coercivity of $F^{\prime}$ we have

We want $A$ to be large enough, we will take

summing for $n$ from $1$ to $N$ we obtain

dividing by $\sum_{n\in[N]}\alpha^{-n}$ on each side and using the convexity of $F$ we get

which gives us (7.16) and concludes this proof. ∎

C.2 Convergence of reconditioned SGD

Let us now assume that we have for some matrices $T$ and $C$ definite positive so that

We now study $w_{n}$ defined by the following recurence

First let us introduce $v_{0}:=\sqrt{C}^{-1}w_{0}$, $v_{*}:=\sqrt{C}^{-1}w_{*}$ and $h(w):=f(\sqrt{C}w)$ as well as $\forall n\in[N],b\in[B],h_{n,b}(w):=f_{n,b}(\sqrt{C}w)$, then we define

Multiplying by $\sqrt{C}$ we recover the same recurrence rule as (7.21) for $w_{n}=\sqrt{C}v_{n}$. Therefore, the convergence of $v_{n}$ will give us the convergence of $w_{n}$.

where $\mathcal{D}_{C}=\sqrt{C}^{-1}\mathcal{D}$, $L_{C}$ is the largest eigen value of $C$. If we take $\mu_{C,T}$ (resp $L_{C,T}$) the smallest (resp largest) eigenvalue of $\sqrt{C}T\sqrt{C}$, then using Theorem 1, we have for

C.3 Convergence of AdaBatch

The Hessian $F^{\prime\prime}$ (resp $f^{\prime\prime}$) of $F$ (resp $f$) are bounded from above and below as:

Let $w_{*}:=\operatorname*{arg\,min}_{w\in\mathcal{D}}F(w)$,

where $\Pi_{\mathcal{D},C}[w]:=\operatorname*{arg\,min}_{x\in\mathcal{D}}\left\|w-x\right\|_{C^{-1}}^{2}$ is the projection on the set $\mathcal{D}$ with respect to $\left\|\cdot\right\|_{C^{-1}}$. This extra step of projection is required for this proof technique but experience shows that it is not needed. We introduce $\forall p\in,p^{+B}:=1-(1-p)^{B}$.

We introduce $\forall n\in[N],\mathcal{F}_{n-1}$ the $\sigma$-field generated by $(f_{i,b})_{i\in[n-1],b\in[B]}$. Let us take $n\in[N]$ and introduce $\eta_{n}:=w_{n}-w_{*}$. We then proceed to bound $\left\|\eta_{n}\right\|^{2}_{C^{-1}}$,

Taking the expectation while conditioning on $\mathcal{F}_{n-1}$ we obtain

Although we will not do it in the following, it is also possible to use Lemma 2. Indeed, for any $k\in[d]$ such that $Bp^{(k)}\geq 5$, we have

which would be equivalent for the dimension $k$ to having a regular batch size of $\frac{p^{(k)}B}{5}$. This shows that AdaBatch will benefit from a reduced variance for features that are frequent enough. For simplicity we will however stick with the simpler bound given by (7.30).

We want $A$ to be large enough, we will take

which gives us (7.27). We obtain (7.28) in the exact same way as in the proof of Theorem 1. ∎

C.4 Sparse linear prediction

We will now show that Assumption 3 is easy to meet in the case of linear predictions. For simplicity, let us assume $X$ is a random variable with values in $\{0,1\}^{d}$ with uncorrelated features, i.e.,

As $\sqrt{p}\sqrt{p}^{T}\preceq\left\|\sqrt{p}\right\|^{2}\operatorname{Id}=\sum_{k\in[d]}p^{(k)}\operatorname{Id}$, we obtain

D AdaBatch for SVRG

We now only assume that $F$ verifies the following inequalities for $\mu>0$,

with $g_{s,n}$ the SVRG update based on $(f_{s,n,b})_{b\in[B]}$ i.i.d samples of $f$. Let us introduce

If Assumptions 7.35 are verified and $\gamma$ verifies

and using that $F^{\prime}(w_{n-1})^{T}(w_{n-1}-w_{*})\geq F(w_{n-1})-F_{*}$ we have

Summing the above inequality for $n\in[m]$ and taking the expectation with respect to $\mathcal{F}_{0}$,

Using the strong convexity of $F$ we have $\left\|w_{0}-w_{*}\right\|^{2}\leq\frac{2}{\mu}\left(F(y)-F_{*}\right)$ and finally

One can derive a simplified convergence result when we assume $B$ large enough.

If we assume $B\gg 1$, then with $\gamma=\frac{1}{L}$ and $m=\frac{2BL}{\mu(0.9B-4)}\approx\frac{2.2L}{\mu}$, we have

D.2 AdaBatch SVRG

Let us now assume that $F$ verify the following inequalities for $\mu>0$,

We now define for any dimension $k$ such that $D^{(k)}_{s,n}\neq\emptyset$,

If Assumptions 7.38 are verified and $\gamma$ verifies

We reuse the same proof technique as previously and introduce the same operators $\Gamma$ and $\Gamma_{n,b}$, again dropping all $s$ indices for simplicity.

using similar arguments as for regular mini-batch. Therefore, we have

Summing the above inequality for $n\in[m]$ and taking the expectation with respect to $\mathcal{F}_{0}$,

Using the strong convexity of $F$ we have

D.3 Comparing the effect of regular mini-batch and AdaBatch for SVRG

If $F$ verifies our sparse convexity condition

This number is roughly constant with the batch size. However the cost of each single iteration is now $B$ times larger, thus meaning that we would need to process $B$ times more samples before reaching the same accuracy as when $B=1$.

On the other hand, using Corollary 2, in order to achieve the same rate of convergence, we would require the number of inner iterations to be

thus the number of inner iterations is inversely proportionnal to the batch size, which balances perfectly the increased cost of each iteration. We will reach the same accuracy as for $B=1$ without requiring to process more samples.

It should be noted that using Lemma 2, it is possible to show that AdaBatch also benefits from variance reduction for the coordinates where $p^{(k)}B$ is large enough. This will depend on the datasets but we have observed such an effect in practice, which allows us to take a larger step-size and further improve convergence.

As for regular SGD, we have noticed experimentally that mini-batch SVRG will become more efficient than AdaBatch when we are close to the optimum. For instance, on datasets that are much smaller than url such as news20 or spam, we observed that mini-batch SVRG will perform better than AdaBatch. Therefore, we would advice using AdaBatch for early optimization and regular mini-batch for fine tuning when close to the optimum.

E Experimental results

We present here the same graphs as in the main paper but for the spam and url dataset. We also provide the convergence with respect to the number of samples for news20. On both datasets, AdaBatch performs competitively with Hogwild! and significantly better than mini-batch SGD, especially when increasing the number of workers and batch-size.

E.2 Experimental results for SVRG

We give a comparison of regular mini-batch and AdaBatch on news20 and spam on figure 10. The difference is less marked than on the url dataset which we believe is due to the relative simplicity of the optimization problem on such datasets. The L2 regularization was chosen in order to achieve relatively good validation error while retaining the good convergence of SVRG in the strongly convex case.

References