Communication Efficient Distributed Optimization using an Approximate Newton-type Method

Introduction

We are particularly interested in a stochastic optimization (learning) setting, where the ultimate goal is to minimize some stochastic (population) objective (e.g. expected loss or generalization error)

and each of the $m$ machines has access to $n$ i.i.d. samples $z_{i}^{1},\ldots,z_{i}^{n}$ from the source distribution $\mathcal{D}$, for a total of $N=nm$ independent samples evenly and randomly distributed among the machines. Each machine $i$ can construct a local empirical (sample) estimate of $F(w)$:

and the overall empirical objective is then:

We can then use the empirical risk minimizer (ERM)

as an approximate minimizer of $F(w)$. Since our interest lies mostly with this stochastic optimization setting, we will denote $\hat{w}=\arg\min\phi(w)$ even when the optimization objective $\phi(w)$ is not an empirical approximation to a stochastic objective.

A straight-forward single-iteration approach is for each machine to optimize its own local objective, obtaining

This approach, which we refer to as “one-shot parameter averaging”, was recently considered in Zinkevich et al. (2010) and further analyzed by Zhang et al. (2013). The latter also proposed a bias-corrected improvement which perturbs each $\hat{w}_{i}$ using the optimum on a bootstrap sample. This approach gives only an approximate minimizer of $\phi(w)$ with some finite suboptimality, rather then allowing us converge to $\hat{w}$ (i.e. to obtain solutions with any desired suboptimality $\epsilon$). Although approximate solutions are often sufficient for stochastic optimization, we prove in Section 2 that the one-shot solution $\bar{w}$ can be much worse in terms of minimizing the population objective $F(w)$, compared to the actual empirical minimizer $\hat{w}$. It does not seem possible to address this suboptimality by more clever averaging, and instead additional rounds of communications appear necessary.

Gradient Descent

One possible multi-round approach to distributed optimization is a distributed implementation of gradient descent: at each iteration each machine calculates $\nabla\phi_{i}(w^{(t)})$ at the current iterate $w^{(t)}$, and then these are averaged to obtain the overall gradient $\nabla\phi(w^{(t)})$, and a gradient step is taken. As the iterates are then standard gradient descent iterates, the number of iterations, and so also number of communication rounds, is linear in the conditioning of the problem – or, if accelerated gradient descent is used, proportional to the square root of the condition number: If $\phi(w)$ is $L$-smooth and $\lambda$-strongly convex, then

iterations are needed to attain an $\epsilon$-suboptimal solution. The polynomial dependence on the condition number may be disappointing, as in many problems the parameter of strong convexity $\lambda$ might be very small. E.g., when strong convexity arises from regularization, as in many stochastic optimization problems, $\lambda$ decreases with the overall sample size $N=nm$, and is typically at most $1/\sqrt{nm}$ (Sridharan et al. 2008; Shalev-Shwartz et al. 2009; and see also Section 4.3 below). The number of iterations / communication rounds needed for distributed accelerated gradient descent then scales as $\sqrt{nm}$, i.e. increases polynomially with the sample size.

Instead of gradient descent, one may also consider more sophisticated methods which utilize gradient information, such as quasi-Newton methods. For example, a distributed implementation using L-BFGS has been proposed in Agarwal et al. (2011). However, no guarantee better then (8) can be ensured for gradient-based methods Nemirovsky and Yudin (1983), and we thus may still get a polynomial dependence on the sample size.

ADMM and other approaches

Another popular approach is distributed alternating direction method of multipliers (ADMM, e.g. Boyd et al. 2011), where the machines alternate between computing shared dual variables in a distributed manner, and solving augmented Lagrangian problems with respect to their local data. However, the convergence of ADMM can be slow. Although recent works proved a linear convergence rate under favorable assumptions Deng and Yin (2012); Hong and Luo (2012), we are not aware of any analysis where the number of iterations / communication rounds doesn’t scale strongly with the condition number, and hence the sample size, for learning applications. A similar dependence occurs with other recently-proposed algorithms for distributed optimization (e.g. Yang, 2013; Mahajan et al., 2013; Dekel et al., 2012; Cotter et al., 2011; Duchi et al., 2012). We also mention that our framework is orthogonal to much recent work on distributed coordinate descent methods (e.g. Recht et al., 2011; Richtárik and Takác, 2013), which assume the data is split feature-wise rather than instance-wise.

Our Method

The method we propose can be viewed as an approximate Newton-like method, where at each iteration, instead of a gradient step, we take a step appropriate for the geometry of the problem, as estimated on each machine separately. In particular, for quadratic objectives, the method can be seen as taking approximate Newton steps, where each machine $i$ implicitly uses its local Hessian $\nabla^{2}\phi_{i}(w)$ (although no Hessians are explicitly computed!). Unlike ADMM, our method can take advantage of the fact that for machine learning applications, the sub-problems are usually similar: $\phi_{i}\approx\phi$. We refer to our method as DANE—Distributed Approximate NEwton.

Notation and Definitions

For vectors, $\|v\|$ is always the Euclidean norm, and for matrices $\|A\|_{2}$ is the spectral norm. We use $\lambda\preccurlyeq A\preccurlyeq L$ to indicate that the eigenvalues of $A$ are bounded between $\lambda$ and $L$. We say that a twice differentiableAll our results hold also for weaker definitions of smoothness and strong convexity which do not require twice differentiability. function $f(w)$ is $\lambda$-strongly convex or $L$-smooth, iff for all $w$, its Hessian is bounded from below by $\lambda$ (i.e. $\lambda\preccurlyeq\nabla^{2}f(w)$), or above by $L$ (i.e. $\nabla^{2}f(w)\preccurlyeq L$) respectively.

Stochastic Optimization and One-shot Parameter Averaging

In a stochastic optimization setting, where the true objective is the population objective $F(w)$, there is a limit to the accuracy with which we can minimize $F(w)$ given only $N=nm$ samples, even using the exact empirical minimizer $\hat{w}$. It is thus reasonable to compare the suboptimality of $F(w)$ when using the exact $\hat{w}$ to what can be attained using distributed optimization with limited communication.

where $w^{*}=\arg\min F(w)$ is the population minimizer and the expectation is with respect to the random sample of size $N=nm$. One might then ask whether a suboptimality of $\epsilon=\mathcal{O}\left(\frac{G^{2}}{\lambda nm}\right)$ can be also be achieved using a few, perhaps only one, round of communication. This is different from seeking a distributed optimization method that achieves any arbitrarily small empirical suboptimality, and thus converges to $\hat{w}$, but might be sufficient in terms of stochastic optimization.

For one-shot parameter averaging, Zhang et al. (2013, Corollary 2) recently showed that for $\lambda$-strongly convex objectives, and when moments of the first, second and third derivatives of $f(w,z)$ are bounded by $G$, $L$, and $M$ respectivelyThe exact conditions in Zhang et al. (2013) refer to various high order moments, but are in any case satisfied when $\|\nabla_{w}f(w,z)\|\leq G$, $\|\nabla^{2}_{w}f(w,z)\|_{2}\leq L$ and $\nabla^{2}f(w,z)$ is $M$-Lipschitz in the spectral norm. For learning problems, all derivatives of the objective can be bounded in terms of a bound on the data and bounds on the derivative of a scalar loss function, and are less of a concern to us., then

Zhang et al. (2013) argued that the dependence on the sample size $mn$ above is essentially optimal: the dominant term (as $n\rightarrow\infty$, and in particular when $n\gg m$) scales as $1/(nm)$, which is the same as for the empirical minimizer $\hat{w}$ (as in eq. 10), and so one-shot parameter averaging achieves the same population suboptimality rate, using only a single round of communication, as the best rate we can hope for using unlimited communication, or if all $N=nm$ samples were on the same machine. Moreover, the $\mathcal{O}(n^{-2})$ terms can be replaced by a $\mathcal{O}(n^{-3})$ term using an appropriate bias-correction procedure.

However, this view ignores the dependence on the other parameters, and in particular the strong convexity parameter $\lambda$, which is much worse in (12) relative to (10). The strong convexity parameter often arises from an explicit regularization, and decays as the sample size increases. E.g., in regularized loss minimization and SVM-type problems (Sridharan et al., 2008), as well as more generally for stochastic convex optimization (Shalev-Shwartz et al., 2009), the regularization parameter, and hence the strong convexity parameter, decreases as $\frac{1}{\sqrt{N}}=\frac{1}{\sqrt{nm}}$. In practice, $\lambda$ is often chosen even smaller, possibly as small as $\frac{1}{N}$. Unfortunately, substituting $\lambda=\mathcal{O}(1/\sqrt{nm})$ in (12) results in a useless bound, where even the first term does not decrease with the sample size.

Of course, this strong dependence on $\lambda$ might be an artifact of the analysis of Zhang et al.. However, in Theorem 1 below, we show that even in a simple one-dimensional example, when $\lambda\leq\mathcal{O}(1/\sqrt{n})$, the population sub-optimality of the one-shot estimator (using $m$ machines and a total of $nm$ samples), can be no better then the population sub-optimality using just $n$ samples, and much worse than what can be attained using $nm$ samples. In other words, one-shot averaging does not give any benefit over using only the data on a single machine, and ignoring all other $(m-1)n$ data points.

For any number of machines $m$, if we run one-shot parameter averaging to compute $\bar{w}$, it holds for some universal constants $C_{1},C_{2},C_{3},C_{4}$ that

The intuition behind the construction of Theorem 1 is that when $\lambda$ is small, the deviation of each machine output $\hat{w}_{i}$ from $w^{*}$ is large, and its expectation is biased away from $w^{*}$. The exact bias amount is highly problem-dependent, and cannot be eliminated by any fixed averaging scheme. Since bias is not reduced by averaging, the optimization error does not scale down with the number of machines $m$. The full construction and proof appear in appendix A. In the appendix we also show that the bias correction proposed by Zhang et al. to reduce the lower-order terms in equation (11) does not remedy this problem.

Distributed Approximate Newton-type Method

We now describe a new iterative method for distributed optimization. The method performs two distributed averaging computations per iteration, and outputs a predictor $w^{(t)}$ which, under suitable parameter choices, converges to the optimum $\hat{w}$. The method, which we refer to as DANE (Distributed Approximate NEwton-type Method) is described in Figure 1.

DANE maintains an agreed-upon iterate $w^{(t)}$, which is synchronized among all machines at the end of each iteration. In each iteration, we first compute the gradient $\nabla\phi(w^{(t-1)})$ at the current iterate, by averaging the local gradients $\nabla\phi_{i}(w^{(t-1)})$. Each machine then performs a separate local optimization, based on its own local objective $\phi_{i}(w)$ and the computed global gradient $\nabla\phi(w^{(t)})$, to obtain a local iterate $w_{i}^{(t)}$. These local iterates are averaged to obtain the centralized iterate $w^{(t)}$.

The crux of the method is the local optimization performed on each machine at each iteration:

To understand this local optimization, recall the definition of the Bregman divergence corresponding to a strongly convex function $\psi$:

Now, for each local objective $\phi_{i}$, consider the regularized local objective, defined as

and its corresponding Bregman divergence:

It is not difficult to check that the local optimization problem (13) can be written as

where we also added the terms $\phi(w^{(t-1)})+\langle\nabla\phi(w^{(t-1)}),w^{(t-1)}\rangle$ which do not depend on $w$ and do not affect the optimization. The first two terms in (14) are thus a linear approximation of the overall objective $\phi(w)$ about the current iterate $w^{(t-1)}$, and do not depend on the machine $i$. What varies from machine to machine is the potential function used to localize the linear approximation. The update (14) is in-fact a mirror descent update (Nemirovski and Yudin, 1978; Beck and Teboulle, 2003) using the potential function $h_{i}$, and step size $\eta$.

At the other extreme, consider the case where $\mu=0$ and all local objectives are equal, i.e. $h_{i}(w)=\phi_{i}(w)=\phi(w)$. Substituting the definition of the Bregman divergence into (14), or simply investigating (13), we can see that $w_{i}^{(t)}=\arg\min\phi_{i}(w)=\arg\min\phi(w)=\hat{w}$. That is, DANE converges in a single iteration to the overall empirical optimum. This is an ideal Newton-type iteration, where the potential function is perfectly aligned with the objective.

Of course, if $\phi_{i}(w)=\phi(w)$ for all machines $i$, we would not need to perform distributed optimization in the first place. Nevertheless, as $n\rightarrow\infty$, we can hope that $\phi_{i}(w)$ are similar enough to each other, such that (14) approximates such an ideal Newton-type iteration, gets us very close to the optimum, and very few such iterations are sufficient.

In particular, consider the case where $\phi_{i}(w)$, and hence also $\phi(w)$ are quadratic. In this case, the Bregman divergence $D_{i}(w;w^{(t-1)})$ takes the form:

and the update (14) can be solved in closed form:

Contrast this with the true Newton update:

The difference here is that in (16) we approximate the inverse of the average of the local Hessians with the average of the inverse of the Hessians (plus a possible regularizer). Again we see that the DANE update (16) approximates the true Newton update (17), which can be performed in a distributed fashion without communicating the Hessians.

For a quadratic objective, a single Newton update is enough to find the exact optimum. In Section 4 we rigorously analyze the effects of the distributed approximation, and quantify the number of DANE iterations (and thus rounds of communication) required.

For a general convex, but non-quadratic, objective, the standard Newton approach is to use a quadratic approximation to the ideal Bregman divergence $D_{\phi}$. This leads to the familiar quadratic Newton update in terms of the Hessian. DANE uses a different sort of approximation to $D_{\phi}$: we use a non-quadratic approximation, based on the entire objective and not just a local quadratic approximation, but approximate the potential on each node separately. In the stochastic setting, this approximation becomes better and better, and thus the required number of iterations decrease, as $n\rightarrow\infty$.

Since it is notoriously difficult to provide good global analysis for Newton-type methods, we will investigate the global convergence behavior of DANE carefully in the next Section but only for quadratic objective functions. This analysis can also be viewed as indicative for non-quadratic objectives, as locally they can be approximated by quadratics and so should enjoy the same behavior, at least asymptotically. For non-quadratics, we provide a rigorous convergence guarantee when the stepsize $\eta$ is sufficiently small or the regularization parameter $\mu$ is sufficiently large (in Section 5). However, this analysis does not show a benefit over distributed gradient descent for non-quadratics. We partially bridge this gap by showing that even in the non-quadratic case, the convergence rate improves as the local problems $\phi_{i}$ become more similar.

DANE for Quadratic Objectives

In this Section, we analyze the performance of DANE on quadratic objectives. We begin in Section 4.1 with an analysis of DANE for arbitrary quadratic objectives $\phi_{i}(w)$, without stochastic assumptions, deriving a guarantee in terms of the approximation error of the true Hessian. Then in Section 4.2 we consider the stochastic setting where the instantaneous objective $f(w,z)$ is quadratic in $w$, utilizing a bound on the approximation error of the Hessian to obtain a performance guarantee for DANE in terms of the smoothness and strong convexity of $f(w,z)$ . In Section 4.3 we also consider the behavior for stochastic optimization problems, where $\lambda$ is set as a function of the sample size $N=nm$.

We begin by considering the case where each local objective $\phi_{i}(w)$ is quadratic, i.e. has a fixed Hessian. The overall objective $\phi(w)$ is then of course also quadratic.

After $t$ iterations of DANE on quadratic objectives with Hessians $H_{i}=\nabla^{2}\phi_{i}(w)$, we have:

If $0<\lambda\preccurlyeq H\preccurlyeq L$ and for all $i$, $\|H_{i}-H\|_{2}\leq\beta$, then setting $\eta=1$ and $\mu=\max\{0,\frac{8\beta^{2}}{\lambda}-\lambda\}$, we have:

In the next Section, we consider the stochastic setting, where we can obtain bounds for $\|H_{i}-H\|_{2}$ that improve with the sample size, and plug these into Lemma 1 and Theorem 2 to obtain a performance guarantee for DANE.

2 Stochastic Quadratic Problems

We now turn to a stochastic quadratic setting, where $\phi_{i}(w)=\hat{F}_{i}(w)$ as in (3), and the instantaneous losses are smooth and strongly convex quadratics. That is, for all $z$, $f(w,z)$ is quadratic in $w$ and $\lambda\preccurlyeq\nabla^{2}_{w}f(w,z)\preccurlyeq L$.

We first use a matrix concentration bound to establish that all Hessians $H_{i}=\nabla^{2}\hat{F}_{i}(w)$ are close to each other, and hence also to their average:

If $0\preccurlyeq\nabla^{2}_{w}f(w,z)\preccurlyeq L$ for all $z$, then with probability at least $1-\delta$ over the samples, $\max_{i}\|H_{i}-H\|_{2}\leq\sqrt{\frac{32L^{2}\log(dm/\delta)}{n}}$, where $H_{i}=\nabla^{2}\hat{F}_{i}(w)$ and $H=\nabla^{2}\hat{F}(w)$.

The proof appears in appendix D. Combining Lemma 2, Lemma 1 and Theorem 2, we can conclude:

In the stochastic setting, and when the instantaneous losses are quadratic with $\lambda\preccurlyeq\nabla f(w,z)\preccurlyeq L$, then after

iterations of DANE, we have, with probability at least $1-\delta$, that $\hat{F}(w^{(t)})\leq\hat{F}(\hat{w})+\epsilon$.

The proof appears in Appendix E. From the theorem, we see that if the condition number $L/\lambda$ is fixed, then as $n\rightarrow\infty$ the number of required iterations decreases. In fact, for any target sub-optimality $\epsilon$, as long as the sample size is at least logarithmically large, namely $n=\Omega\left((L/\lambda)^{2}\log(dm)\log(\frac{1}{\epsilon})\right)$, we can obtain the desired accuracy after a constant or even a single DANE iteration! This is a mild requirement on the sample size, since $N$ generally increases at least linearly with $1/\epsilon$.

We next turn to discuss the more challenging case where the condition number decays with the sample size.

3 Analysis for Regularized Objectives

Confronted with such non-strongly-convex objectives, a standard approach is to perform empirical minimization on a regularized objective (Shalev-Shwartz et al., 2009). That is, to define the regularized instantaneous objective

and minimize the corresponding empirical objective $\hat{F}_{\lambda}$. The instantaneous objective $f_{\lambda}(w,z)$ of the modified stochastic optimization problem is now $\lambda$-strongly convex. If $f(w,z)$ are $G$-Lipschitz in $w$, then we have (Shalev-Shwartz et al., 2009):

where $\hat{w}_{\lambda}=\arg\min\hat{F}_{\lambda}(w)$ and $w_{\lambda}^{*}=\arg\min F_{\lambda}(w)$. The optimal choice of $\lambda$ in the above is $\lambda=\sqrt{\frac{G^{2}}{B^{2}N}}$, where $B$ is a bound on the predictors we would like to compete with, and with this $\lambda$ we get the optimal rate:

It is thus instructive to consider the behavior of DANE when $\lambda=\Theta\left(\sqrt{\frac{G^{2}}{B^{2}N}}\right)=\Theta\left(\sqrt{\frac{G^{2}}{B^{2}nm}}\right)$. Plugging this choice of $\lambda$ into Theorem 3, we get that the number of DANE iterations behaves as:

That is, unlike distributed gradient descent, or any other relevant method we are aware of, the number of required iterations / communication rounds does not increase with the sample size, and only scales linearly with the number of machines.

Convergence Analysis for Non-Quadratic Objectives

As discussed above, it is notoriously difficult to obtain generic global analysis of Newton-type methods. Our main theoretical result in this paper is the analysis for quadratic objectives, which we believe is also instructive for non-quadratics. Nevertheless, we complement this with a convergence analysis for generic objectives.

We therefore return to considering generic convex objectives $\phi_{i}(w)$. We also do not make any stochastic assumptions. We only assume that each $\phi_{i}(w)$ is $L_{i}$-smooth and $\lambda_{i}$ strongly convex, and that the combined objective $\phi(w)$ is $L$-smooth and $\lambda$-strongly convex.

Assume that for all $i,w,z$, $\lambda_{i}\preccurlyeq\nabla^{2}\phi_{i}(w)\preccurlyeq L_{i}$ and $\lambda\preccurlyeq\nabla^{2}\phi(w)\preccurlyeq L$. Let

If $\rho>0$, then the DANE iterates satisfy $\phi(w^{(t)})-\phi(\hat{w})\leq(1-\rho)^{t}[\phi(w^{(0)})-\phi(\hat{w})].$

The proof appears in Appendix F. The theorem establishes that with any $\mu>0$ and small enough step-size $\eta$, DANE converges to $\hat{w}$. If each $\phi_{i}(w)$ is strongly convex, we can also take $\mu=0$ and sufficiently small $\eta$ and ensure convergence to $\hat{w}$. However, the optimal setting of $\eta$ and $\mu$ above is to take $\mu\rightarrow\infty$ and set $\eta=\mu/L$, in which case $\rho\rightarrow\lambda/L$, and we recover distributed gradient descent, with the familiar gradient descent guarantee.

We again emphasize that the analysis above is weak and does not take into account the relationship between the local objectives $\phi_{i}(w)$. We believe that the quadratic analysis of Section 4 better captures the true behavior of DANE. Moreover, we can partially bridge this gap by the following result, which shows that a variant of DANE enjoys a linear convergence rate which improves as the local objectives $\phi_{i}$ become more similar to $\phi$ (the proof is in Appendix G):

Assume that in the DANE procedure, we replace step $(*)$ by $w^{(t)}=w_{1}^{(t)}$, and define $h(\cdot)=h_{1}(\cdot)$. If there exists $\gamma>0$ such that $\forall w,w^{\prime}$, we have $\gamma D_{h}(w;w^{\prime})\leq D_{\phi}(w;w^{\prime})\leq\eta^{-1}D_{h}(w;w^{\prime})$, then

If $\mu$ is small and $\phi_{i}\approx\phi$, then we expect $\gamma\approx 1$ and $\eta\approx 1$. In this case, $\eta\gamma\approx 1$, leading to fast convergence.

Experiments

In this section, we present preliminary experimental results on our proposed method. In terms of tuning $\eta,\mu$, we discovered that simply picking $\eta=1,\mu=0$ (which makes DANE closest to a Newton-type iteration, as discussed in Section 3) often results in the fastest convergence. However, in unfavorable situations (such as when the data size per machine is very small), this can also lead to non-convergence. In those cases, convergence can be recovered by slightly increasing $\mu$ to a small positive number. In the experiments, we considered $\mu=0,3\lambda$. These are considerably smaller than what our theory indicates, and we leave the question of the best parameter choice to future research.

Finally, we examine the convergence on these datasets in terms of the average loss on the test set. In figure 4, we present the results for $m=64$ machines on the three datasets, using DANE (with $\mu=3\lambda$) and ADMM. We also present for comparison the objective value obtained using one-shot parameter averaging (OSA), using bias correction as proposed in Zhang et al. (2013). The figure highlights the practical importance of multi-round communication algorithms: while DANE and ADMM converge to the value achieved by the regularized loss minimizer, the single-round OSA algorithm may return a significantly suboptimal result.

Ohad Shamir and Nathan Srebro are supported by the Intel ICRI-CI Institute. Ohad Shamir is further supported by an Israel Science Foundation grant 425/13 and an FP7 Marie Curie CIG grant.

References

Appendix A Lower Bounds for One-shot Parameter Averaging

Before providing the proof details, let us first describe the high-level intuition of our construction. Roughly speaking, one-shot averaging works well when the bias of the predictor returned by each machine (as a random vector in Euclidean space, based on the sampled training data) is much smaller than the variance. Since each such predictor is based on independent data, averaging $m$ such predictors reduces the variance by a factor of $m$, leading to good guarantees. However, averaging has no effect on the bias, so this method is ineffectual when the bias dominates the variance. The construction below shows that when the strong convexity parameter is small, this can indeed happen.

More specifically, when the strong convexity parameter is smaller than $\mathcal{O}(1/\sqrt{n})$, the magnitude of the deviations of the (random) predictor returned by each machine does not decay with the sample size $n$. Moreover, its distribution is highly dependent on the data distribution and the shape of $f$, and is biased in general. Below we use one such construction, which we found to be convenient for precise analytic calculations, but the intuition applies much more broadly.

Specifically, let $\mathcal{W}=[-2/\lambda,\log(1/\lambda)]$, and define the loss function $f(w;z)$ as

Taking the derivative, equating to zero and slightly manipulating the result, we get that

We now turn to analyze $w(x)+w(-x)$. First, we have by definition

Therefore, we have $w(x)+w(-x)\leq 0$ for all $x$. More precisely, considering (23) and the fact that its left hand size is monotonic in $w(x)$, it’s easy to verify that for any $x\geq 0$, we have $w(x)\geq\log\left(\frac{x}{\lambda\sqrt{n}}-\log\left(\frac{x}{\lambda\sqrt{n}}\right)\right)$, and $w(-x)\leq-\frac{x}{\lambda\sqrt{n}}$, so using (24),

Since $\log(a)<a/2$ for all $a\geq 0$, this expression is at most $-\frac{x}{2\lambda\sqrt{n}}$. Plugging this back into (22), and using the assumption $n\geq 9$, we get that

Since $p(x)$ is the standard Gaussian distribution, it can be numerically checked that this is at most

Now, we show that this expected value of $\hat{w}_{1}$ is far away from $w^{*}$. $w^{*}$ is not hard to calculate: It satisfies

and it can be calculated numerically that $w^{*}=-0.5671..>-3/5$. Moreover, we assume $\lambda\leq 1/(9\sqrt{n})$, so $\lambda\sqrt{n}\leq 1/9$ and thus it can be verified that

Note that this is always a positive quantity. As a result, using Jensen’s inequality, we get

Moreover, by $\lambda$-strong convexity of $f$, we have that

(see Equation (10)). Combining the four inequalities above gives us the theorem statement.

A.2 Bias Correction Also Fails

In Zhang et al. (2013), which analyzes one-shot parameter averaging, the authors noticed that the analysis fails for small values of $\lambda$, and proposed a modification of the simple averaging scheme, designed to reduce bias issues. Specifically, given a parameter $r\in$, each machine subsamples $rn$ examples without replacement from its dataset, and computes the optimum $\hat{w}_{2,k}$ with respect to this subsample. Then, it computes the optimum $\hat{w}_{k,1}$ over the entire dataset, and returns the weighted combination $\hat{w}_{k}=(\hat{w}_{k,1}-r\hat{w}_{k,2})/(1-r)$. Unfortunately, the analysis still results in lower-order terms with bad dependence on $\lambda$, and it’s not difficult to extend our construction from Theorem 1 to show that this bias-corrected version of the algorithm still fails (at least, if $r$ is chosen in a fixed manner).

Appendix B Proof of Theorem 2

For any $w^{(t-1)}$, the optimal solution is always given by:

where for the last equality we rearranged (25) to calculate $\nabla\phi(w^{(t-1)})=H(w^{(t-1)}-\hat{w})$. Bounding $\|Av\|\leq\|A\|_{2}\|v\|$ and iterating (26) leads to the desired result.

Appendix C Proof of Lemma 1

where $\lambda$ is the smallest eigenvalue of $H$.

This equals one minus the smallest element on the diagonal of the diagonal matrix $(S+\mu I)^{-1}S$, which is $\lambda/(\lambda+\mu)$. ∎

Let $A$ be a positive definite matrix with minimal eigenvalue $\gamma$ which is larger than some $\mu>0$, and $\{\Delta_{i}\}_{i=1}^{m}$ matrices of the same size, such that $\max_{i}\|\Delta_{i}\|\leq\beta$ and $\beta<\gamma$. Then

Note that $\|A^{-1}\Delta_{i}\|\leq\|A^{-1}\|\|\Delta_{i}\|\leq\frac{1}{\gamma}\beta<1$. Therefore, we can use the identity

which holds for any $C$ such that $\|C\|<1$. Using this with $C=A^{-1}\Delta_{i}$ and plugging back, we get

Averaging over $i=1\ldots m$ and using the assumption $\sum_{i=1}^{m}\Delta_{i}=0$, we get

Multiplying both sides by $(A-\mu I)$, we get

By the triangle inequality and convexity of the norm, this implies

Now, we use Lemma 4 with $A=H+\mu I$ and $\Delta_{i}=H_{i}-H$ (noting that $\|\Delta_{i}\|\leq\beta$), and get the bound

Now, let us assume the even stronger condition that $\beta<\frac{1}{2}(\lambda+\mu)$ (which we shall justify at the end of the proof), then we can upper bound the right hand side in the equation above by

Differentiating with respect to $\mu$, we get an optimal point at

If this is non-positive, it means that $\lambda^{2}>8\beta^{2}$, and moreover, that $\mu=0$, so (27) equals $4\beta^{2}/\lambda^{2}$. Otherwise, we pick $\mu=\frac{8\beta^{2}}{\lambda}-\lambda$, and (27) becomes

Combining the two cases, we get the result stated in the Lemma. Finally, it remains to justify why $\beta<\frac{1}{2}(\lambda+\mu)$. By the way we picked $\mu$, it’s enough to prove that

This is true since $\max\{x,8/x\}>2$ for all positive $x$.

Appendix D Proof of Lemma 2

$H$ is the average of the Hessians of $mn$ i.i.d. quadratic functions, all with eigenvalues at most $L$, and each $H_{i}$ is the average of the Hessians of $n$ i.i.d. quadratic functions, all with eigenvalues at most $L$. By a matrix Hoeffding’s inequality (Tropp, 2012), we have that for each $i$, with probability $1-\delta$ over the samples received by machine $i$,

By a union bound, we get that with probability $1-\delta$,

Combining these, we get that with probability $1-\delta$,

Appendix E Proof of Theorem 3

Plugging 2 into Lemma 1, and noting that the strong convexity of the instantaneous losses implies $\hat{F}(w)$ is $\lambda$ strongly convexIn fact, it is enough to require that $\hat{F}(w)$ is $\lambda$-strongly convex, and it is not necessary to require strong convexity of $f(w,z)$ for each individual $z$. However, requiring that the population objective $F(w)$ is $\lambda$-strongly convex might not be sufficient if $\lambda<L/\sqrt{n}$, e.g. when $\lambda\propto 1/\sqrt{nm}$., we obtain

By smoothness of $\hat{F}$, we have $\hat{F}(w^{(t)})-\hat{F}(\hat{w})\leq\frac{L}{2}\|w^{(t)}-\hat{w}\|^{2}$, and therefore Theorem 2 implies that

This means that to get optimization error $\leq\epsilon$, the number of iterations required is

Considering (28), if the first case holds, then the denominator in (29) is at least $2\log(2)$ and we get that the number of iterations required is $\mathcal{O}\left(\log\left(\frac{L\|w^{(0)}-\hat{w}\|}{\epsilon}\right)\right)$. If the second case in (28) holds, we have

which implies that the iteration bound (29) is at most

Appendix F Proof of Theorem 4

Under the conditions of Theorem 4, the following inequalities hold:

The smoothness of $h_{i}$ implies that its conjugate $h_{i}^{*}$ is $1/(L_{i}+\mu)$ strongly convex. Let $u^{\prime}=\nabla h_{i}(w^{\prime})$ and $u=\nabla h_{i}(w)$, then $w^{\prime}=\nabla h_{i}^{*}(u^{\prime})$ and $w=\nabla h_{i}^{*}(u)$. We have

Since $\nabla\phi(\hat{w})=0$, $\|\nabla\phi(w)\|_{2}^{2}=\|\nabla\phi(w)-\nabla\phi(\hat{w})\|_{2}^{2}$. From $\|\nabla\phi(w)-\nabla\phi(\hat{w})\|_{2}\geq\lambda\|w-\hat{w}\|_{2}$, we obtain

We are now ready to prove the Theorem. At iteration $t$, we have the following first order equation:

where $\rho_{i}=\left[\frac{1}{\mu+L_{i}}-\frac{\eta L}{2(\mu+\lambda_{i})^{2}}\right]\eta\lambda$. In the above derivations, the first inequality uses the smoothness of $\phi$; the second inequality uses the strong convexity of $h_{i}$; the third inequality uses (30); the second and the last equalities use (32).

where the first inequality is Jensen’s and the third inequality is due to (31). As a result, we get

The desired bound follows by recursively applying the above inequality.

Appendix G Proof of Theorem 5

where in the last inequality, we have used the assumption that $D_{\phi}(w^{(t)};w^{(t-1)})\leq\eta^{-1}D_{h}(w^{(t)};w^{(t-1)})$. This implies that

where the first inequality is due to (33), the second inequality comes from the inequality $\phi(\hat{w})\leq\phi(w^{(t)})$, and the third inequality uses the assumption that $D_{\phi}(\hat{w};w^{(t-1)})\geq\gamma D_{h}(\hat{w};w^{(t-1)})$. We thus obtain