Distributed Mini-Batch SDCA

Introduction

Stochastic optimization approaches have significant theoretical and empirical advantages in training linear Support Vector Machines (SVMs) and other regularized loss minimization problems, and are often the methods of choice in practice. Such methods use a single, randomly chosen, training example at each iteration. In the context of SVMs, many variations of stochastic gradient descent (SGD) have been suggested, based on primal stochastic gradients (e.g. Pegasos , NORMA , SAG , MISO , S2GD , mS2GD and Prox-SVRG ). In this paper we focus on SDCA—stochastic dual coordinate ascent—which is based on improvements to the dual problem, again considering only a single randomly chosen training example, and thus only a single randomly chosen dual variable, at each iteration . Especially when accurate solutions are desired, SDCA has better complexity guarantee, and often performs better in practice than SGD .

The inherent sequential nature of such approaches becomes a problematic limitation in parallel and distributed settings as the predictor must be updated after each training point is processed, providing very little opportunity for parallelization. A popular remedy is to use mini-batches: the use several training points at each iteration, calculating the update based on each point separately and aggregating the updates. The question is then whether basing each iteration on several points can indeed reduce the number of required iterations, and thus yield parallelization speedups.

For SGD with a non-smooth loss, mini-batching does not reduce the number of worst-case required iterations and thus does not allow parallel speedups in the worst case. However, when the loss function is smooth, mini-batching can be beneficial and linear speedups can be obtained, even when the mini-batch sizes scales polynomially with the total training set size . Alternatively, even for non-smooth loss, linear speedups can also be ensured if the data is reasonably well-spread, as measured by the spectral norm of the data, as long as the mini-batch size is not larger then the inverse of this spectral norm .

For SDCA, using a mini-batch corresponds to updating multiple coordinates concurrently and independently. If appropriate care is taken with the updates (see Section 6), then using a mini-batch size as large as the inverse spectral norm leads to a reduction in the number of iterations, and allows linear parallelization speedups, even when the loss is non-smooth . This parallels the SGD mini-batch analysis for non-smooth loss. But can mini-batching also be beneficial for SDCA with smooth losses and without a data-spread (spectral norm) assumptions, as with SGD? What mini-batch sizes allow for parallel speedups? In this paper we answer these questions and show that as with SGD, when the loss function is smooth, using mini-batches with SDCA yields a linear reduction in the number of iterations and thus allows for linear parallelization speedups, up to similar polynomial limits on the mini-batch size. Furthermore, we provide an analysis that combines the benefits of smoothness with the data-dependent benefits of a low spectral norm, and thus allows for even large mini-batch sizes when the loss is smooth and the data is well-spread.

Another issue that we address is the way mini-batches are sampled. Straight-forward mini-batch analysis, including previous analysis of mini-batch SDCA , assume that at each iteration we pick a mini-batch of size $b$ uniformly at random from among all subsets of $b$ training examples. In practice, though, data is often partitioned between $C\leq b$ machines, and at each iteration $b/C$ points are samples from each machine, yielding a mini-batch that is not uniformly distributed among all possible subsets (e.g. we have zero probability of using $b$ points from the same machine as a mini-batch). Other architectural restrictions might lead to different sampling schemes. The analysis we present can be easily applied to different sampling schemes, and in particular we consider distributed sampling as described above and show that essentially the same guarantees (with minor modification) hold also for this more realistic sampling scheme.

Finally, we compare our optimization guarantees to those recently established for CoCoA+ . CoCoA+ is an alternative dual-based distributed optimization approach, which can be viewed as including mini-batch SDCA as a special case, and going beyond SDCA to potentially more powerful optimization. At each iteration of CoCoA+, several groups of dual variables are updated. We focus on CoCoA+SDCA, where each group is updated using some number of SDCA iterations. When each group consists of a single variable, this reduces exactly to mini-batch SDCA. Allowing for multiple SDCA iterations on larger groups of variables yields a method that is more computationally demanding that mini-batch SDCA, and intuitively should be better than SDCA (and does appear better in practice). However, we show that our mini-batch SDCA analysis strictly dominates the CoCoA+ analysis: that is, with the same number of total dual variables updated per iteration, and thus less computation, our mini-batch SDCA guarantees are strictly better than those obtained for CoCoA+. Mini-batch SDCA is thus a simpler, computationally cheaper method, with better guarantees than those established for CoCoA+.

Although SDCA is a dual-method, improving the dual at each iteration, following the analysis methodology of , all our guarantees are on the duality gap, and thus on the primal sub-optimality, that is on the actual regularized error we care about.

Setup and Preliminaries

We consider the problem of minimizing the regularized empirical loss

SDCA is a coordinate ascent algorithm optimizing the dual (D). At $t$-th iteration of SCDA a coordinate $i\in\langle n\rangle:=\{1,2,\dots,n\}$ is chosen at random and then a new iteration is obtained by updating only the $i$-th coordinate and keeping all other coordinates of $\alpha$ unchanged i.e. $\alpha^{(t+1)}=\alpha^{(t)}+\Delta\alpha^{(t)}_{i}e_{i}$, where

Assumptions on Loss Function

Mini-Batched SDCA

At each iteration of mini-batched SDCA, a subset $S\subseteq\langle n\rangle$ of the coordinates is chosen at random (see below for a discussion of the sampling distribution) and a new dual iterate is obtained by independently updating only the chosen coordinates. Since each coordinate is updated independently, mini-batch SDCA is amenable to parallelization.

The naïve approach is to use the same update rule for each coordinate as in serial case: the update is then given by $\alpha^{(t+1)}=\alpha^{(t)}+\sum_{i\in S}\Delta\alpha^{(t)}_{i}$ where $\Delta\alpha^{(t)}_{i}$ is given by (1). Such a naïve approach could be fine if the mini-batch size is very small and the data is “spread-out” enough . However, more generally, not only might such a mini-batch iteration not be better than an iteration based on only a single point, but such a naïve mini-batch update might actually be much worse. In particular, it is easy to construct an example with just two examples where a naïve mini-batch approach will never reach the optimum solution, and diverging behavior frequently occurs in practice on real data sets . The problem here is that the independent updates on multiple similar points might combine together to “overshoot” the optimum and hurt the objective.

An alternative that avoids this problem is to average the updates instead of adding them up, $\alpha^{(t+1)}=\alpha^{(t)}+\frac{1}{|S|}\sum_{i\in S}\Delta\alpha^{(t)}_{i}$ , but such an update is overly conservative: it is not any better than just updating a single dual variable, and cannot lead to parallelization speedups. Following , the approach we consider here is to use a summed update $\alpha^{(t+1)}=\alpha^{(t)}+\sum_{i\in S}\Delta\alpha^{(t)}_{i}$, where the independent updates $\Delta\alpha^{(t)}_{i}$ are derived from a relaxation of the dual:

When $v_{i}=\left\lVert{x_{i}}\right\rVert^{2}$, the update exactly agrees with the dual-optimizing update (1). But as we shall see, when larger mini-batches are used, larger values of $v_{i}$ are required, resulting in smaller steps. The update (2) generalizes where a single parameter $v_{i}=v$ was used—here we allow $v_{i}$ to vary between dual variables, accommodating differences in $\left\lVert{x_{i}}\right\rVert$.

To summarize, the mini-batch SDCA algorithm we consider takes as input data $X$, loss functions $\phi_{i}$, a distribution over subsets $S\subseteq\langle n\rangle$, which we will refer to as the random sampling $\hat{S}$, and a weight vector $v$, and proceeds as shown on Algorithm 1.

We will refer to several sampling distributions $\hat{S}$, yielding different variants of mini-batch SDCA: Serial SDCA. $\hat{S}$ is a uniform distribution over singletons. That is, $S_{t}$ contains a single coordinate chosen uniformly at randomly. Setting $v_{i}=\left\lVert{x_{i}}\right\rVert$ yields standard SDCA. Standard Mini-batch SDCA. $\hat{S}$ is a uniform distribution over subsets of size $b$. Distributed SDCA. Consider a setting with $C$ machines, $n$ total data points and a mini-batch size $b$, where for simplicity $n$ and $b$ are both integer multiples of $C$. For a partition of the $n$ coordinates into $C$ equal sized subsets $\{P_{c}\}_{c=1}^{C}$, consider the following sampling distribution $\hat{S}$: for each $c=1..C$, choose a subset $S^{c}\subset P_{c}$ uniformly and independently at random among all such subsets of size $b/C$, and then take their union. We refer to such a sample as a $(C,b)$-distributed sampling. Such a sampling is suitable in a distributed environment when $n$ samples are equally partitioned over $C$ computational nodes in a cluster . When $C=1$ we obtain the Standard Mini-batch sampling.

The main question we now need to address is what weights $v_{i}$ are suitable for use with each of the above sampling schemes, and what optimization guarantee to they yield. To answer this question, in the next Section we will introduce the notion of Expected Separable Overapproximations.

Expected Separable Overapproximation

In this Section we will make use of the Expected Separable Overapproximation (ESO) theory introduced in and further extended e.g. in .

Consider the $t$-th iteration of mini-batch SDCA. Our current iterate is $\alpha^{(t)}$ and we have chosen a set $S_{t}$ of coordinates which we will update in current iteration. We need to compute the updates to those coordinates, i.e. $\forall i\in S_{t}$ we need to compute $\Delta\alpha_{i}^{(t)}$. Maybe the natural way how to define the updates would be to define them such that $D(\alpha^{(t+1)})$ is as large as possible, i.e. that we maximize $D(\alpha^{(t)}+\sum_{i\in S_{t}}\Delta\alpha_{i}^{(t)}e_{i})$. However, this e.g. for hinge loss would lead to a QP, hence the computation cost would be substantial. The main disadvantage of this approach is the fact that the updates for different coordinates are dependent on each other, i.e. the value of $\Delta\alpha_{i}^{(t)}$ depends on all coordinates in $S_{t}$. This make it hard to parallelize. Considering the fact that $S_{t}$ is a random set, maybe one would like to define the updates so that the updates doesn’t depend on current choice of $S_{t}$ and that they maximize the expected value of $D$ at next iteration. In this case we are facing following maximization problem

2 Lower-bound

Let us first state the definition of ESO.

Now we can derive the expected lowerbound of $\mathcal{D}$ as follows

where in the first inequality for the first part we have used the fact that the function is separable (see Theorem 4 in ). If we define

3 Computing ESO Parameter

Serial SDCA. In this simplest case we can define $v_{i}=\|x_{i}\|^{2}$. Standard Mini-batch SDCA. In standard mini-batch we can choose $v_{i}=(1+\frac{(b-1)(n\sigma^{2}-1)}{\max\{1,n-1\}})\|x_{i}\|^{2}$. If the data matrix $X$ is sparse, we can define $v_{i}=\sum_{j=1}^{d}(x_{i}^{T}e_{j})^{2}(1+\tfrac{(b-1)(\|x_{i}\|_{0}-1)}{n-1})$. Distributed SDCA. In distributed case we can choose $v_{i}=\frac{b}{b-C}(1+\tfrac{(b-C)(n\sigma^{2}-1)}{\max\{C,n-C\}})\|x_{i}\|^{2}$, provided that $b\geq 2C$ and $v_{i}=(1+b\sigma^{2})\|x_{i}\|^{2}$ if $b=C$. A simple upper-bound valid for any $b$ can be derived as follows $v_{i}=2(1+b\sigma^{2})\|x_{i}\|^{2}$.

Convergence Guarantees

We are now ready to present optimization guarantees for Algorithm 1 based on the ESO parameters studied in the previous Section. These theorems extends the serial case of to mini-batch setting. The Theorems are based on weights $v$ are chosen such that $f(\alpha)=\|\frac{1}{\lambda n}X^{T}\alpha\|^{2}$ admits $v$-ESO for a sampling $\hat{S}$ used in the Algorithm 1. Proofs are provided in the supplemental material.

If the losses are $(1/\gamma)$-smooth and $f(\alpha)=\|\frac{1}{\lambda n}X^{T}\alpha\|^{2}$ admits $v$-ESO for the sampling $\hat{S}$, then for a desired duality gap $\epsilon_{\mathcal{G}}>0$, using Algorithm 1, if we choose

If the losses are $L$-Lipschitz and $f(\alpha)=\|\frac{1}{\lambda n}X^{T}\alpha\|^{2}$ admits $v$-ESO for the sampling $\hat{S}$, then for a desired duality gap $\epsilon_{\mathcal{G}}>0$, using Algorithm 1, denoting $G=4L^{2}\frac{\sum_{i=1}^{n}v_{i}}{n}$, if we choose

Guarantees and Speedups for Specific Sampling Distributions

Theorems 3 and 2 are stated in terms of ESO parameter $v$. Let us now consider the specific sampling distribution of interest. Assume for simplicity $\left\lVert{x_{i}}\right\rVert\leq 1$, and define

for the serial, standard and distributed sampling schemes respectively, with overall mini-batch size $b$ and distribution over $C$ machines. Using the weights $v_{i}=\beta$, we then have the following obtain the following iteration complexities:

$L$-Lipschitz Continuous Loss. Combining equations (10) and (11), and again ignoring logarithmic factors, we get an iteration complexity of:

Plugging in $\beta_{std}$ into (13) recovers the previous analysis of Lipschitz loss with standard sampling.

Both the Lipschitz and smooth cases involve two terms: the first term, $\tfrac{n}{b}$, always displays a linear improvement as we increase the mini-batch size. However, in the second term, we also have a dependence on the data-dependent $1\leq\beta\leq b$, which depends on the mini-batch size $b$. We will have a linear improvement in the second term, i.e. potential for linear speedup, as long as $\beta=O(1)$. For standard sampling we have that $\beta\approx 1+b\sigma^{2}$, and so we obtain linear speedups as long as $b=O(1/\sigma^{2})$, as discussed in (13). We can now also quantify the effect of distributed sampling and see that it is quite negligible and yields almost the same speedups and the same maximum allows mini-batch size as with standard sampling. Note that typically we will have $C\ll b$, as we would like to process multiple example on each machine—otherwise communication costs would overwhelm computational costs . The analysis supports this choice as well as the extreme choice $C=b$.

Focusing on the smooth loss, it is possible to obtain a linear reduction in the iteration complexity (corresponding to linear speedups) for SGD with mini-batch size of up to $\mathcal{O}(\sqrt{n})$ without any data-dependent assumption, that is regardless of the value of $\beta$ . Is this possible also with SDCA? Indeed, even if we don’t account for the data dependent quantity $\beta$, since we always have $\beta\leq b$, then the iteration complexity of SDCA for mini-batch SDCA with smooth loss is: $\mathcal{O}(1/(\lambda\gamma)+n/b)\log(1/\epsilon))$ a larger mini-batch scales the second term (unconditional on any data dependence), and as long as it is the dominant term, we get linear speedups. Now, to get the min-max learning guarantee, we need to set $\lambda=\Theta(1/\sqrt{n})$(see ). Plugging this in, we see that we get linear speedups up to a mini-batch of size $\mathcal{O}(\gamma\sqrt{n})$. Unsurprising, this is the same as the mini-batch SGD guarantee. Now, if we do take data-dependence into account, we have $\beta=\mathcal{O}(1+b\sigma^{2})$ (where $\sigma^{2}$ is as defined above). As long as $b<1/\sigma^{2}$, we get linear speedps even if the $1/\lambda$ term is dominant, i.e. regardless of the scaling of lambda relative to $n$. This is good, because in practice, and especially when the expected error is low, the best lambda is often closer to $1/n$ and not $1/\sqrt{n}$. Returning to the worst-case rate and $\lambda=1/\sqrt{m}$ : we now have an allowed mini-batch size of up to $b=\mathcal{O}(\gamma\sqrt{n}/\sigma^{2})$ while still getting linear scaling. That is, we can combined the benefits of both smoothness, where we can scale the mini-batch size by $\sqrt{n}$, and the data dependence, to get an additional scaling by $1/\sigma^{2}$.

Comparison with CoCoA+

CoCoA+ is a recently presented framework and analysis for distributed optimization of the dual (D): Data (and hence dual variables) are partitioned among $C$ machines (as in our distributed sampling), defining $C$ subproblems, one for each machine. At each iteration, the set of dual variables of each of the $C$ machines are updated independently, and then communicated and aggregated across machines. Different local updates can be used, and the CoCoA+ analysis depends on how well the update improves the local subproblem. Here we will consider using local SDCA updates in conjunction with CoCoA+: at each iteration, on each of the $C$ machines, $b/C$ dual variables are selected (as in our distributed sampling), and $H$ iterations of SDCA are performed sequentially on these $b/C$ points (in parallel on each of the $C$ machines, and while considering all other dual variables, including all variables on other machines, as fixed).

Setting $b>C$ and $H=b/C$, both minibatch SDCA and CoCoA+ perform the same number of SDCA updates (same amount of computation) at each iteration, but while minibatch SDCA’s updates are entirely independent, each group of $H$ CoCoA+ updates (the $H$ updates on the same machine) are performed sequentially. We would therefore expect CoCoA+’s updates to be better, and therefore require less iterations. Unfortunately, the CoCoA+ analysis does not show this.

And so, even though CoCoA+ with SDCA updates should be a more powerful algorithm, its analysis fails to show benefits over the simpler mini-batch SDCA, and out analysis here of mini-batch SDCA even dominates the CoCoA+ analysis. The reason for this is that CoCoA+ aims to be a more general framework capable of including arbitrary local solvers. Hence, necessarily, the analysis must be more conservative.

Numerical Experiments

In this Section we show that the cost of distribution is negligible (in terms of # iterations) when compared to standard mSDCA. We also show that if $b\gg 1$, then CoCoA+ is faster than mSDCA in practice. We have run experiments on 4 datasets (see Table 1). Note that most of the datasets are sparse (e.g, news20: an average tsample depends on 385 features out of 1.3M).

Standard vs. Distributed SDCA. Figure 1 (top row) compares standard and distributed SDCA. Recall that distributed sampling with $C=1$ and standard mini-batch sampling coincide. On the $x$-axis is the parameter $b$ and on the $y$-axis we plot how much more data-accesses we have to as $b$ or $C$ grow, to get achieve the same accuracy. We see that the lines are almost identical for various choices of $C$, which implies that the cost of using distributed mSDCA does not affect the number of iterations significantly. This is also supported by the theory (notice that in (12) we have $\beta_{\mbox{dist}}/\beta_{\mbox{std}}\approx 1$). Also note that, for news20 for instance, increasing $b$ to $10^{4}$ implies that the number of data-accesses (epochs) will increase by a factor of 11, which implies that # iterations will decrease almost by 1,000 for $b=10^{4}$ when compared with $b=1$.

mSDCA vs. CoCoA+. In Figure 1 (bottom row) we compare the mSDCA with CoCoA+ with SDCA as a local solver. We plot the duality gap as a function of epochs (if communication is negligible then the main cost is in computation) or iterations (if the communication cost is significant than this is the correct measure of performance). As the results suggest, is the communication cost it negligible then the mSDCA with small $b$ is the best (as expected), however, if communications cost is significant, then CoCoA+ with large values of $H$ significantly outperforms mSDCA.

References

Appendix A Technical Results

Following Lemma is a minibatch extension of Lemma 1 in .

Assume that $\phi_{i}^{*}$ is $\gamma$-strongly convex ($\gamma$ can be also zero). Then, for any $t$ and any $s\in$ we have

$u_{t}=(u_{1}^{(t)},\dots,u_{n}^{(t)})^{T}$ and $-u_{i}^{(t)}\in\partial\phi_{i}(w_{\alpha^{(t)}}^{T}x_{i})$.

Following lemma is a small extension of Lemma 4 in to obtain more tide bounds in case each sample has different norm or when ESO bound is used. For example, in serial case we will have that $\forall t:G^{t}\leq 4L^{2}\frac{\sum_{i=1}^{n}\|x_{i}\|^{2}}{n}$.

Suppose that for all $i$, $\phi_{i}$ is $L$-Lipschitz continuous. Then

Appendix B Proofs

Let us define ${\bf T}_{\alpha}$ as an unique maximizer of a function $\mathcal{H}(t,\alpha)$ defined in (7), i.e.

$\mathcal{H}({\bf 0},\alpha)=\mathcal{D}(\alpha)$,

$\mathcal{H}(t,\alpha)\leq\mathcal{H}({\bf T}_{\alpha},\alpha)$.

Convex conjugate maximal property implies that

Let us estimate the expected change of dual objective.

Using $\gamma$-strong convexity of $\phi_{i}^{*}$ we have that

Substituting the definition of duality gap (G) we obtain

Multiplying both sides by $-\frac{b}{n}$ we obtain (15).

B.2 Proof of Theorem 3

At first let us estimate expected change of dual feasibility.

Choice of $s=1$ and $t=t_{0}:=\max\{0,\lceil\tfrac{n}{b}\log(2\lambda n\epsilon_{D}^{(0)}/(G))\rceil\}$ will lead to

Following the proof in we are now going to show that

Clearly, (24) implies that (25) holds for $t=t_{0}$. Now imagine that it holds for any $t\geq t_{0}$ then we show that it also has to hold for $t+1$. Indeed, using $s=\frac{2n}{2n+b(t-t_{0})}$ we obtain

In the last inequality we have used the fact that geometric mean is less or equal to arithmetic mean. If $\bar{\alpha}$ is defined as (9) then we obtain that

Now, if $T\geq\lceil\frac{n}{b}\rceil+T_{0}$ such that $T_{0}\geq t_{0}$ we obtain

Using $s=\frac{n}{b(T-T_{0})}$ we obtain that

To have this quantity $\leq\epsilon_{\mathcal{G}}$ we obtain that $T,t_{0},T_{0}$ has to satisfy (10). The fact that $T_{0}\geq t_{0}+\frac{1}{b}\left(\frac{4G}{\lambda\epsilon_{\mathcal{G}}}-2n\right)_{+}$ implies that right-hand site of (26) is $\leq\epsilon_{\mathcal{G}}$.

B.3 Proof of Theorem 2

Therefore if we denote by $\epsilon_{D}^{(t)}=\mathcal{D}(\alpha^{*})-\mathcal{D}(\alpha^{(t)})$ we have that

Right hand site will be smaller than some $\epsilon_{D}$ if

Moreover, to bound the duality gap we have

Therefore $\mathcal{G}(\alpha^{(t)})\leq\frac{\|v\|_{\infty}+\lambda n\gamma}{b\lambda\gamma}\epsilon_{D}^{(t)}$. Hence if $\epsilon_{D}\leq\frac{b\lambda\gamma}{\|v\|_{\infty}+\lambda n\gamma}\epsilon_{\mathcal{G}}$ then $\mathcal{G}(\alpha^{(t)})\leq\epsilon_{\mathcal{G}}$. Therefore after

iterations we have duality gap less than $\epsilon_{\mathcal{G}}$ and the first part of the proof is done. To show the second part of Theorem let us sum (30) over $t=T_{0},\dots,T-1$ to obtain

Now, if we choose $\bar{w},\bar{\alpha}$ to be either average vectors or a randomly chosen vector over $t\in\{T_{0}+1,\dots,T\}$, then we have

To get a high probability result we use Lemma 8 with $\xi^{(t)}=\mathcal{D}(\alpha^{*})-\mathcal{D}(\alpha^{(t)})$, $c_{2}=\frac{\|v\|_{\infty}+\lambda n\gamma}{b\lambda\gamma}$ (see (29)) and $\epsilon=\frac{b\lambda\gamma}{\|v\|_{\infty}+\lambda n\gamma}\epsilon_{\mathcal{G}}$ to obtain that after