Dual-Free Stochastic Decentralized Optimization with Variance Reduction

Introduction

We consider the regularized empirical risk minimization problem distributed on a network of $n$ nodes. Each node has a local dataset of size $m$, and the problem thus writes:

where $f_{ij}$ typically corresponds to the loss function for training example $j$ of machine $i$, and $\sigma_{i}$ is the local regularization parameter for node $i$. We assume that each function $f_{ij}$ is convex and $L_{ij}$-smooth (see, e.g., Nesterov (2013)), and that each function $f_{i}$ is $M_{i}$-smooth. Following Xiao et al. (2019), we denote $\kappa_{i}=(1+\sum_{i=1}^{m}L_{ij})/\sigma_{i}$ the stochastic condition number of $f_{i}$, and $\kappa_{s}=\max_{i}\kappa_{i}$. Similarly, the batch condition number is $\kappa_{b}=\max_{i}M_{i}/\sigma_{i}$. It always holds that $\kappa_{b}\leq\kappa_{s}\leq m\kappa_{b}$, but generally $\kappa_{s}\ll m\kappa_{b}$, which explains the success of stochastic methods. Indeed, $\kappa_{s}\approx m\kappa_{b}$ when all Hessians are orthogonal to one another which is rarely the case in practice, especially for a large dataset.

Single-machine stochastic methods. Problem (1) is generally solved using first-order methods. When $m$ is large, computing $\nabla F$ becomes very expensive, and batch methods require $O(\kappa_{b}\log(\varepsilon^{-1}))$ iterations, which takes time $O(m\kappa_{b}\log(\varepsilon^{-1}))$, to minimize $F$ up to precision $\varepsilon$. In this case, updates using the stochastic gradients $\nabla f_{ij}$, where $(i,j)$ is selected randomly, can be much more effective (Bottou, 2010). Yet, these updates are noisy and plain stochastic gradient descent (SGD) does not converge to the exact solution unless the step-size goes to zero, which slows down the algorithm. One way to fix this problem is to use variance-reduced methods such as SAG (Schmidt et al., 2017), SDCA (Shalev-Shwartz and Zhang, 2013), SVRG (Johnson and Zhang, 2013) or SAGA (Defazio et al., 2014). These methods require $O((nm+\kappa_{s})\log(\varepsilon^{-1}))$ stochastic gradient evaluations, which can be much smaller than $O(m\kappa_{b}\log(\varepsilon^{-1}))$.

Decentralized methods. Decentralized adaptations of gradient descent in the smooth and strongly convex setting include EXTRA (Shi et al., 2015), DIGing (Nedic et al., 2017) or NIDS (Li et al., 2019). These algorithms have sparked a lot of interest, and the latest convergence results (Jakovetić, 2018; Xu et al., 2020; Li and Lin, 2020) show that EXTRA and NIDS require time $O((\kappa_{b}+\gamma^{-1})(m+\tau))\log(\varepsilon^{-1}))$ to reach precision $\varepsilon$. A generic acceleration of EXTRA using Catalyst (Li and Lin, 2020) obtains the (batch) optimal $O(\sqrt{\kappa_{b}}(1+\tau/\sqrt{\gamma})\log(\varepsilon^{-1}))$ rate up to log factors. Another line of work on decentralized algorithms is based on the penalty method (Li et al., 2018; Dvinskikh and Gasnikov, 2019). This consists in performing traditional optimization algorithms to problems augmented with a Laplacian penalty, and in particular enables the use of accelerated methods. Yet, these algorithms are sensitive to the value of the penalty parameter (when it is fixed), since it directly influences the solution they converge to. Another natural way to construct decentralized optimization algorithms is through dual approaches (Scaman et al., 2017; Uribe et al., 2020). Although the dual approach leads to algorithms that are optimal both in terms of number of communications and computations (Scaman et al., 2019; Hendrikx et al., 2020), they generally assume access to the proximal operator or the gradient of the Fenchel conjugate of the local functions, which is not very practical in general since it requires solving a subproblem at each step.

Decentralized stochastic optimization. Although both stochastic and decentralized methods have a rich litterature, there exist few decentralized stochastic methods with linear convergence rate. Although DSA (Mokhtari and Ribeiro, 2016), or GT-SAGA (Xin et al., 2020) propose such algorithms, they respectively take time $O((m\kappa_{s}+\kappa_{s}^{4}\gamma^{-1}(1+\tau)\log(\varepsilon^{-1}))$ and $O((m+\kappa_{s}^{2}\gamma^{-2})(1+\tau)\log(\varepsilon^{-1}))$ to reach precision $\varepsilon$. Therefore, they have significantly worse rates than decentralized batch methods when $m=1$, and than single-machine stochastic methods when $n=1$. Other methods have better rates of convergence (Shen et al., 2018; Hendrikx et al., 2019b) but they require evaluation of proximal operators, which may be expensive.

Our contributions. This work develops a dual approach similar to that of Hendrikx et al. (2019b), which leads to a decentralized stochastic algorithm with rate $O(m+\kappa_{s}+\tau\kappa_{b}/\sqrt{\gamma})$, where the $\sqrt{\gamma}$ factor comes from Chebyshev acceleration, such as used in Scaman et al. (2017). Yet, our algorithm, called DVR, can be formulated in the primal only, thus avoiding the need for computing expensive dual gradients or proximal operators. Besides, DVR is derived by applying Bregman coordinate descent to the dual of a specific augmented problem. Thus, its convergence follows from the convergence of block coordinate descent with Bregman gradients, which we prove as a side contribution. When executed on a single-machine, DVR is similar to dual-free SDCA (Shalev-Shwartz, 2016), and obtains similar rates. We believe that the same methodology could be applied to tackle non-convex problems, but we leave these extensions for future work.

We present in Section 2 the derivations leading to DVR, namely the dual approach and the dual-free trick. Then, Section 3 presents the actual algorithm along with a convergence theorem based on block Bregman coordinate descent (presented in Appendix A). Section 4 shows how to accelerate DVR, both in terms of network dependence (Chebyshev acceleration) and global iteration complexity (Catalyst acceleration (Lin et al., 2017)). Finally, experiments on real-world data are presented in Section 5, that demonstrate the effectiveness of DVR.

Algorithm Design

This section presents the key steps leading to DVR. We start by introducing a relevant dual formulation from Hendrikx et al. (2019b), then introduce the dual-free trick based on Lan and Zhou (2017), and finally show how this leads to DVR, an actual implementable decentralized stochastic algorithm, as a special case of the previous derivations.

Following the approach of Hendrikx et al. (2019b, 2020), we further split the $f_{i}(\theta^{(i)})$ term into $\sigma_{i}\|\theta^{(i)}\|^{2}/2+\sum_{j=1}^{n}f_{ij}(\theta^{(ij)})$, with the constraint that $\theta^{(i)}=\theta^{(ij)}$ for all $j$. This is equivalent to the previous approach performed on an augmented graph (Hendrikx et al., 2019b, 2020) in which each node is split into a star network with the regularization in the center and a local summand at each tip of the star. Thus, the equivalent augmented constrained problem that we consider writes:

2 Dual-free trick

Dual methods are based on variants of Problem (4), and apply different algorithms to it. In particular, Scaman et al. (2017); Uribe et al. (2020) use accelerated gradient descent (Nesterov, 2013), and Hendrikx et al. (2019a, b) use accelerated (proximal) coordinate descent (Lin et al., 2015b). Let $p_{\rm comm}$ denote the probability of performing a communication step and $p_{ij}$ be the probability that node $i$ samples a gradient of $f_{ij}$, which are such that for all $i$, $\sum_{j=1}^{m}p_{ij}=1-p_{\rm comm}$. Applying a coordinate update with step-size $\eta/p_{\rm comm}$ to Problem (4) in the direction $x$ (associated with communication edges) writes:

where we denote $\nabla_{x}$ the gradient in coordinates that correspond to $x$ (communication edges), and $\nabla_{y,ij}$ the gradient for coordinate $(ij)$ (computation edge). Similarly, the standard coordinate update of a local computation edge $(i,j)$ can be written as:

where the minimization problem actually has a closed form solution. Yet, as mentioned before, solving Equation (6) requires computing the derivative of $f_{ij}^{*}$. In order to avoid this, a trick introduced by Lan and Zhou (2017) and later used in Wang and Xiao (2017) is to replace the Euclidean distance term by a well-chosen Bregman divergence. More specifically, the Bregman divergence of a convex function $\phi$ is defined as:

Bregman gradient algorithms typically enjoy the same kind of guarantees as standard gradient algorithms, but with slightly different notions of relative smoothness and strong convexity (Bauschke et al., 2017; Lu et al., 2018). Note that the Bregman divergence of the squared Euclidean norm is the squared Euclidean distance, and the standard gradient descent algorithm is recovered in that case. We now replace the Euclidean distance by the Bregman divergence induced by function $\phi:y\mapsto(L_{ij}/\mu_{ij}^{2})f_{ij}^{*}(\mu_{ij}y^{(ij)})$, which is normalized to be $1$-strongly convex since $f_{ij}^{*}$ is $L_{ij}^{-1}$-strongly convex. We introduce the constant $\alpha>0$ such that $\mu_{ij}^{2}=\alpha L_{ij}$ for all computation edges $(i,j)$. Using the definition of the Bregman divergence with respect to $\phi$, we write:

In particular, if we know $\nabla f_{ij}^{*}(\mu_{ij}y_{t}^{(ij)})$ then it is possible to compute $y_{t+1}^{(ij)}$. Besides,

so we can also compute $\nabla f_{ij}^{*}(\mu_{ij}y_{t+1}^{(ij)})$, and we can use it for the next step. Therefore, instead of computing a dual gradient at each step, we can simply choose $y_{0}^{(i)}=\mu_{ij}^{-1}\nabla f_{ij}(z_{0}^{(ij)})$ for any $z_{0}^{(ij)}$, and iterate from this. Therefore, the Bregman coordinate update applied to Problem (4) in the block of direction $(i,j)$ with $y_{0}^{(ij)}=\mu_{ij}^{-1}\nabla f_{i}(z_{0}^{(ij)})$ yields:

The iterations of (9) are called a dual-free algorithm because they are a transformation of the iterations from (6) that do not require computing $\nabla f_{ij}^{*}$ anymore. This is obtained by replacing the Euclidean distance in (6) by the Bregman divergence of a function proportional to $f_{ij}^{*}$.

3 Distributed implementation

To show that $\left[A(x_{t},y_{t})\right]_{\rm comm}$ is locally accessible to each node, we write:

Plugging Equation (11) into the updates of (9), we obtain the following updates:

for communication edges, and for the local update of the $j$-th component of node $i$:

Convergence Rate

We choose p_{\rm comm}=\big{(}1+\gamma\frac{m+\kappa_{s}}{\kappa_{\rm comm}}\big{)}^{-1}, $p_{ij}\propto(1-p_{\rm comm})(1+L_{ij}/\sigma_{i})$ and $\alpha$ and $\eta$ as in Algorithm 1. Then, there exists $C_{0}>0$ that only depends on $\theta_{0}$ (initial conditions) such that for all $t>0$, the error and the expected time $T_{\varepsilon}$ required to reach precision $\varepsilon$ are such that:

We have seen in Section 2 that DVR is obtained by applying Bregman coordinate descent on a well-chosen dual problem. Therefore, one of our key results consists in proving convergence rates for Bregman coordinate descent. In order to ease the reading of the paper, we present these results for a general setting in Appendix A, which is self-contained and which we believe to be of independent interest (beyond its application to decentralized optimization).

Then, Appendix B focuses on the application to decentralized optimization. In particular, we recall the Equivalence between DVR and Bregman coordinate descent applied to the dual problem of Equation (4), and show that its structure is suited to the application of coordinate descent. Indeed, no two virtual edges adjacent to the same node are updated at the same time with our sampling. Then, we evaluate the relative smoothness and strong convexity constants of the augmented problem, which allows to derive adequate values for parameters $\alpha$ and $\eta$. Finally, we choose $p_{\rm comm}$ in order to minimize the execution time of DVR. ∎

We would like to highlight the fact that the convergence theory of DVR decomposes nicely into several building blocks, and thus simple rates are obtained. This is not so usual for decentralized algorithms, for instance many follow-up papers were needed to obtain a tight convergence theory for EXTRA (Shi et al., 2015; Jakovetić, 2018; Xu et al., 2020; Li and Lin, 2020). We now discuss the convergence rate of DVR more in details.

Computation complexity. The computation complexity of DVR is the same computation complexity as locally running a stochastic algorithm with variance reduction at each node. This is not surprising since, as we argue later, DVR can be understood as a decentralized version of an algorithm that is closely related to dual-free SDCA (Shalev-Shwartz, 2016). Therefore, this improves the computation complexity of EXTRA from $O(m(\kappa_{b}+\gamma^{-1}))$ individual gradients to $O(m+\kappa_{s})$, which is the expected improvement for stochastic variance-reduced algorithm. In comparison, GT-SAGA (Xin et al., 2020), a recent decentralized stochastic algorithm, has a computation complexity of order $O(m+\kappa_{s}^{2}/\gamma^{2})$, which is significantly worse than that of DVR, and generally worse than that of EXTRA as well.

Communication complexity. The communication complexity of DVR (i.e., the number of communications, so the communication time is retrieved by multiplying by $\tau$) is of order $O(\kappa_{\rm comm}/\gamma)$, and can be improved to $O(\kappa_{\rm comm}/\sqrt{\gamma})$ using Chebyshev acceleration (see Section 4). Yet, this is in general worse than the $O(\kappa_{b}+\gamma^{-1})$ communication complexity of EXTRA or NIDS, which can be interpreted as a partly accelerated communication complexity since the optimal dependence is $O(\sqrt{\kappa_{b}/\gamma})$ (Scaman et al., 2019), and $2\sqrt{\kappa_{b}/\gamma}=\kappa_{b}+\gamma^{-1}$ in the worst case ($\kappa_{b}=\gamma^{-1}$). Yet, stochastic updates are mainly intended to deal with cases in which the computation time dominates, and we show in the experimental section that DVR outperforms EXTRA and NIDS for a wide range of communication times $\tau$ (the computation complexity dominates roughly as long as $\tau<\sqrt{\gamma}(m+\kappa_{s})/\kappa_{\rm comm})$. Finally, the communication complexity of DVR is significantly lower than that of DSA and GT-SAGA, the primal decentralized stochastic alternatives presented in Section 1.

Homogeneous parameter choice. In the homogeneous case ($\sigma_{i}=\sigma_{j}$ for all $i,j$), choosing the optimal $p_{\rm comp}$ and $p_{\rm comm}$ described above leads to $\eta\lambda_{\max}(W)=\sigma p_{\rm comm}$. Therefore, the communication update becomes $\theta_{t+1}=\left(I-W/\lambda_{\max}(W)\right)\theta_{t}$, which is a gossip update with a standard step-size (independent of the optimization parameters). Similarly, $\alpha\eta(m+\kappa_{s})=p_{\rm comp}$, and so the step-size for the computation updates is independent of the network.

Links with SDCA. The single-machine version of Algorithm 1 ($n=1$, $p_{\rm comm}=0$) is closely related to dual-free SDCA (Shalev-Shwartz, 2016). The difference is in the stochastic gradient used: DVR uses $\nabla f_{ij}(z_{t}^{(ij)})$, where $z_{t}^{(ij)}$ is a convex combination of $\theta_{k}^{(i)}$ for $k<t$, whereas dual-free SDCA uses $g_{t}^{(ij)}$, which is a convex combination of $\nabla f_{ij}(\theta_{k}^{(i)})$ for $k<t$. Both algorithms obtain the same rates.

Local synchrony. Instead of using the synchronous communications of Algorithm 1, it is possible to update edges one at a time, as in Hendrikx et al. (2019b). This can be very efficient in heterogeneous settings (both in terms of computation and communication times) and similar convergence results can be obtained using the same framework, and we leave the details for future work.

Acceleration

We show in this section how to modify DVR to improve the convergence rate of Theorem 1.

Network acceleration. Algorithm 1 depends on $\gamma^{-1}$, also called the mixing time of the graph, which can be as high as $O(n^{2})$ for a chain of length $n$ (Mohar, 1997). However, it is possible to improve this dependency to $\gamma^{-1/2}$ by using Chebyshev acceleration, as in Scaman et al. (2017). To do so, the first step is to choose a polynomial $P$ of degree $k$ and communicate with $P(W)$ instead of $W$. In terms of implementation, this comes down to performing $k$ communication rounds instead of one, but this makes the algorithm depend on the spectral gap of $P(W)$. Then, the important fact is that there is a polynomial $P_{\gamma}$ of degree $\lceil\gamma^{-1/2}\rceil$ such that the spectral gap of $P_{\gamma}(W)$ is of order $1$. Each communication step with $P_{\gamma}(W)$ only takes time $\tau{\rm deg}(P_{\gamma})=\tau\lceil\gamma^{-1/2}\rceil$, and so the communication term in Theorem 1 can be replaced by $\tau\kappa_{\rm comm}\gamma^{-1/2}$, thus leading to network acceleration. The polynomial $P_{\gamma}$ can for example be chosen as a Chebyshev polynomial, and we refer the interested reader to Scaman et al. (2017) for more details. Finally, other polynomials yield even faster convergence when the graph topology is known (Berthier et al., 2020).

Catalyst acceleration. Catalyst (Lin et al., 2015a) is a generic framework that achieves acceleration by solving a sequence of subproblems. Because of space limitations, we only present the accelerated convergence rate without specifying the algorithm in the main text. Yet, only mild modifications to Algorithm 1 are required to obtain these rates, and the detailed derivations and proofs are presented in Appendix C.

Experiments

Figure 1 compares the performance of DVR with that of state-of-the-art primal algorithms such as EXTRA (Shi et al., 2015), NIDS (Li et al., 2019), GT-SAGA (Xin et al., 2020), and Catalyst accelerated versions of EXTRA (Li and Lin, 2020) and DVR. Suboptimality refers to $F(\theta_{t}^{(0)})-F(\theta^{\star})$, where node is chosen arbitrarily and $F(\theta^{\star})$ is approximated by the minimal error over all iterations. Each subplot of Figure 1(a) shows the same run with different x axes. The left plot measures the complexity in terms of individual gradients ($\nabla f_{ij}$) computed by each node whereas the center plot measures it in terms of communications (multiplications by $W$). All other plots are taken with respect to (simulated) time (i.e., computing $\nabla f_{ij}$ takes time $1$ and multiplying by $W$ takes time $\tau$) with $\tau=250$ in order to report results that are independent of the computing cluster hardware and status. All parameters are chosen according to theory, except for the smoothness of the $f_{i}$, which requires finding the smallest eigenvalue of a $d\times d$ matrix. For this, we start with $L_{b}=\sigma_{i}+\sum_{j=1}^{m}L_{ij}$ (which is a known upper bound), and decrease it while convergence is ensured, leading to $\kappa_{b}=0.01\kappa_{s}$. The parameters for accelerated EXTRA are chosen as in Li and Lin (2020) since tuning the number of inner iterations does not significantly improve the results (at the cost of a high tuning effort). For accelerated DVR, we set the number of inner iterations to $N/p_{\rm comp}$ (one pass over the local dataset). We use Chebyshev acceleration for (accelerated) DVR but not for (accelerated) EXTRA since it is actually slower, as predicted by the theory.

As expected from their theoretical iteration complexities, NIDS and EXTRA perform very similarly Li and Lin (2020), and GT-SAGA is the slowest method. Therefore, we only plot NIDS and GT-SAGA in Figure 1(a). We then see that though it requires more communications, DVR has a much lower computation complexity than EXTRA, which illustrates the benefits of stochastic methods. We see that DVR is faster overall if we choose $\tau=250$, and both methods perform similarly for $\tau\approx 1000$, at which point communicating takes roughly as much time as computing a full local gradient. We then see that accelerated EXTRA has quite a lot of overhead and, despite our tuning efforts, is slower than EXTRA when the regularization is rather high. On the other hand, accelerated DVR consistently outperforms DVR by a relatively large margin. The communication complexity is in particular greatly improved, allowing accelerated DVR to be the fastest method regardless of the setting. Further experimental results are given in Appendix D, and the code is available in supplementary material.

Conclusion

This paper introduces DVR, a Decentralized stochastic algorithm with Variance Reduction obtained using Bregman block coordinate descent on a well-chosen dual formulation. Thanks to this approach, DVR inherits from the fast rates and simple theory of dual approaches without the computational burden of relying on dual oracles. Therefore, DVR has a drastically lower computational cost than standard primal decentralized algorithms, although sometimes at the cost of a slight increase in communication complexity. The framework used to derive DVR is rather general and could in particular be extended to analyze asynchronous algorithms. Finally, although deriving a direct acceleration of DVR is a challenging open problem, Catalyst and Chebyshev accelerations allow to significantly reduce DVR’s communication overhead both in theory and in practice.

Acknowledgements

This work was funded in part by the French government under management of Agence Nationale de la Recherche as part of the “Investissements d’avenir” program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). We also acknowledge support from the European Research Council (grant SEQUOIA 724063) and from the MSR-INRIA joint centre.

References

Appendix A Block Coordinate descent

We focus in this section on the general problem minimizing $f+g$ using coordinate Bregman gradient, where $g$ is separable, i.e., $g(x)=\sum_{i=1}^{d}g_{i}(x^{(i)})$. This is a self-contained section, and notations may differ from the rest of the paper. In particular, function $f$ is for now arbitrary and not related to $F$ or $f_{i}$ from Problem (1), and the dimension $d$ is arbitrary as well.

We first precise the blocks sampling rule. More specifically, we define a block $b\subset\{1,\dots,d\}$ as a collection of coordinates, and $\mathcal{B}$ is the set of all blocks that can be chosen for the updates. Then, the algorithm updates each block $b\in\mathcal{B}$ with probability $p(b)$, so that the probability of updating a given coordinate is given by $p_{i}=\sum_{i\in b}p(b)$. Similarly to individual coordinates, we write $x^{(b)}$ the restriction of $x$ to coordinates in $b$. The Bregman coordinate gradient update for a block of coordinates $b$ writes:

where $\nabla_{i}f$ denotes the gradient of $f$ in direction $i$. Note that this update is more general than the one used to derive DVR, for which $g=0$. In order to derive strong guarantees for this block coordinate descent algorithm, we need to ensure that there is some separability in functions $f$ and $\phi$, and that the block structure is suited to this separability. All the assumptions about the separability structure of $f$, $g$ and $\phi$ are contained in the following assumption.

The function $g$ is separable and the function $\phi$ is block-separable for $b$, meaning that for all $b\in\mathcal{B}$, there exist two convex functions $\phi_{b}$ and $\phi_{b}^{\perp}$ such that for all $x$,

Besides, for all $b\in\mathcal{B}$, either of the following two hold:

$\phi$ and $f$ are separable for $b$, i.e., $\phi_{b}(x^{(b)})=\sum_{i\in b}\phi_{i}(x^{(i)})$, and

If $\phi$ is not block-separable, the support of the Bregman update in direction $b$ may not restricted to $b$. This causes some of the derivations below to fail, which is why we prevent it by assuming that Equation (16) holds.

Then, the first option ensures that within a block, the updates do not affect each other. The function $f$ is not separable, but some directions can be updated independently from others. To have these independent updates, we also need to assume further separability of $\phi$ within the blocks. The second option states that if only block-separability of $\phi$ is assumed then within each block for which $\phi$ and $f$ are not separable, coordinates must be picked with the same probability.

Assumption 1 is a bit technical but we actually require all statements in order to derive DVR. In particular, the first option is verified when updating within the same block virtual edges that are adjacent to different nodes in the dual problem. The second option is verified when picking all communication edges at once within the same block.

Now that we have made assumptions on the structure of $f$, $g$ and $\phi$, we will make assumptions on their regularity. We start by a directional relative smoothness assumption between $f$ and $\phi$, i.e., we assume that for all $i$, there exists $L_{\rm rel}^{i}$ such that for all $\delta>0$ and $e_{i}$ the unit vector of direction $i$,

Similarly, for $\sigma_{\rm rel}>0$, $f$ is said to be $\sigma_{\rm rel}$-strongly convex relatively to $\phi$ if for all $x,y$:

We finally assume that $f$ and $\phi$ are convex (but not necessarily smooth). We can now state the central theorem of this section:

Let $f$ and $\phi$ be such that $f$ is $L_{\rm rel}^{i}$-smooth in direction $i$ and $\sigma_{\rm rel}$-strongly convex relatively to $\phi$. Denote $p_{\min}=\min_{i}p_{i}$, and

Then, if the blocks $\mathcal{B}$ respect Assumption 1 (separability) and $\eta_{t}L_{\rm rel}^{i}<p_{i}$ for all $i$, the Bregman coordinate descent algorithm guarantees for all $x$:

The same result holds with $L^{\prime}_{t}=D_{\phi}(x,x_{t})+\frac{1}{L_{\rm rel}^{\max}}\left(F(x_{t})-F(x)\right)$, where $L_{\rm rel}^{\max}=\max_{i}L_{\rm rel}^{i}$.

To prove this theorem, we start by proving the monotonicity of such iterations.

We note $\delta_{i}=e_{i}^{\top}(x_{t+1}-x_{t})e_{i}$. If $x_{t+1}=\arg\min_{x}V_{t}^{b}(x)$ then:

If $\phi$ and $f$ are separable for $b$ then for all $i\in b$, if $\eta_{t}L_{\rm rel}^{i}\leq p_{i}$ then $F(x_{t})\geq F(x_{t}+\delta_{i})$.

If $p_{i}=p_{j}$ for all $i,j\in b$ and $\eta_{t}L_{\rm rel}^{b}\leq p_{b}$ then $F(x_{t})\geq F(x_{t+1})$.

We start by the first point. If $\phi$ is separable for $b$ then this means that each coordinate is updated independently. By definition of $x_{t+1}^{(i)}$, we have $V_{t}^{b}(x_{t+1}^{(b)})\leq V_{t}^{b}(x_{t})$. This writes, splitting over each $i$ and using the fact that $D_{\phi_{i}}(x_{t},x_{t})=0$:

The result follows from summing over all $i\in b$, and using Assumption 1. For the second point, it is not possible to split the update per coordinate since $\phi$ is not separable. Yet, we can still write (using separability of $g$):

Since $g$ is separable and $p_{i}=p_{b}$ for all $i\in b$, Equation (19) writes:

Note that this crucially relies on $x_{t+1}-x_{t}$ having support on $b$, which is enforced by the block-separability of $\phi$. Then, the proof is similar to that of the first point, using that $\eta_{t}L_{\rm rel}^{b}\leq p_{b}$. ∎

Using this monotonicity result allows us to prove Theorem 3.

First note that by convexity of all $g_{i}$,

Then, $\nabla V_{t}^{b}(x_{t+1})=0$ by definition of $x_{t+1}$, so Equation (21) writes:

We first consider that the first option of Assumption 1 holds, i.e., that $f$ and $\phi$ are separable in $b$. We note $\delta_{i}=e_{i}^{\top}(x_{t+1}-x_{t})e_{i}$, so that:

Therefore, if $\eta_{t}L_{\rm rel}^{i}\leq p_{i}$ for all $i\in b$,

The $g_{i}(x_{t+1}^{(i)})-g_{i}(x^{(i)})$ term can be replaced by $g(x_{t}+\delta_{i})-g(x_{t})+g_{i}(x_{t}^{(i)})-g_{i}(x^{(i)})$ since $g_{j}(x_{t+1})=g_{j}(x_{t})$ for $j\neq i$. Therefore, we obtain:

The separability of $F$ in $b$ and its monotonicity lead to, using the fact that $x_{t+1}=x_{t}+\sum_{i\in b}\delta_{i}$:

Therefore, if the first option of Assumption 1 holds, we obtain:

If the second option holds, i.e., $p_{i}=p$ for all $i\in b$, then

and Equation (LABEL:eq:after_monoton) can be obtained through similar derivations (at the block-level). Using the separability of $g$, we obtain that

Therefore, taking the expectation of Equation (LABEL:eq:before_monoton) yields:

Finally, $\sigma_{\rm rel}\leq L_{\rm rel}^{i}$ so $\eta_{t}\sigma_{\rm rel}\leq\eta_{t}L_{\rm rel}^{i}\leq p_{i}$ for all $i$, and in particular $1-p_{\min}\leq 1-\eta_{t}\sigma_{\rm rel}$, which yields the desired result.

The result on $L_{t}^{\prime}$ is be obtained by bounding $\eta/p_{\min}$ by $L_{\rm rel}^{\max}=\max_{i}L_{\rm rel}^{i}$ and remarking that $1-\eta_{t}L_{\rm rel}^{\max}\leq 1-\eta_{t}\sigma_{\rm rel}$ since $L_{\rm rel}^{\max}\geq\sigma_{\rm rel}$. ∎

Appendix B Convergence results for DVR

We now give a series of small results, that justify our approach. We start by showing the applicability of Theorem 3 to Problem (4), and the associated constants. Finally, we show how to obtain rates for the primal iterates $\theta_{t}$.

In this section, we note $f_{\rm sum}^{*}=\sum_{i=1}^{n}\sum_{j=1}^{m}f_{ij}^{*}$, so that Problem 4 writes:

The iterations of Algorithm 1 are equivalent to the iteration of Equations (15) applied to Problem (4) with $g=0$ and $\phi(x,y)=\phi_{\rm comm}(x)+\sum_{i=1}^{n}\sum_{j=1}^{m}\phi_{ij}(y^{(ij)})$, with $\phi_{\rm comm}(x)=\frac{1}{2}\|x\|^{2}_{A^{\dagger}A}$ for coordinates associated with communication edges, and $\phi_{ij}(y^{(ij)})=\frac{L_{ij}}{\mu_{ij}^{2}}f_{ij}^{*}(\mu_{ij}y_{ij})$ for coordinates associated with computation edges.

This result follows from the dual-free and implementation-friendly derivations presented in the previous section. ∎

Let $\alpha=2\lambda_{\min}(A^{\top}_{\rm comm}D_{M}^{-1}A_{\rm comm})$, and $\phi$ as in Lemma 2, then:

$q_{A}+f_{\rm sum}^{*}$ is ($\alpha/2$)-strongly convex relatively to $\phi$.

$q_{A}+f_{\rm sum}^{*}$ is ($L_{\rm rel}^{\rm comm}$)-smooth relatively to $\phi$ in the direction of communication edges, with

$q_{A}+f_{\rm sum}^{*}$ is ($L_{\rm rel}^{ij}$)-smooth relatively to $\phi$ in the direction of virtual edge $(i,j)$, with

First note that $\nabla^{2}f_{\rm sum}^{*}$ is a block-diagonal matrix, and its $ij$-th block is equal to

Finally, using that Equation (25) along with the fact that $\sigma_{F}\leq\alpha$ implies that $q_{A}+f_{\rm sum}^{*}$ is $\sigma_{F}$-relatively strongly convex with respect to $\phi$.

Finally, $\nabla^{2}f_{ij}^{*}(\mu_{ij}y^{(ij)})\succcurlyeq P_{ij}/L_{ij}$, and $\alpha\leq L_{\rm rel}^{i}$, which ends the proof of the directional relative smoothness result. ∎

Assumption 1 holds with $f=q_{A}+f^{*}_{\rm sum}$, $g=0$, and $\phi$ as in Lemma 2, and when the sampling is such that either:

All communication edges are sampled at once, or

Each node samples exactly one virtual edge.

First of all, $g=0$ is separable, and $\phi$ is separable with respect to the communication and computation blocks by construction.

We note $b_{\rm comm}$ the block of all communication edges, which is sampled with probability $p_{\rm comm}$. All communication edges are sampled at the same time, so $p_{i}=p_{\rm comm}$ for all $i\in b_{\rm comm}$ and so $\phi$ respects option $2$ for the communication block.

Finally, $f_{\rm sum}^{*}$ is separable, and so $q_{A}+f_{\rm sum}^{*}$ respects option 2. ∎

We can now prove the main theorem on the convergence rate of DVR.

with $p_{\min}=\min(p_{\rm comm},\min_{ij}p_{ij})$, $\lambda_{t}=(x_{t},y_{t})$ and $D=-(q_{A}+f_{\rm sum}^{*})$. Therefore, the expected time $T_{\varepsilon}$ required to reach precision $\varepsilon$ is equal to:

Using Lemmas 4 and 3, we apply Theorem 3 (convergence of Bregman coordinate gradient descent), and obtain that the convergence rate is $\eta_{t}\alpha/2$, with $\eta_{t}\leq\min_{ij}p_{ij}/L_{\rm rel}^{i}$ and $\eta_{t}\leq p_{\rm comm}/L_{\rm rel}^{\rm comm}$. Therefore, for communication edges, we have that

For computation edges, we know that $p_{ij}=p_{\rm comm}(1+L_{ij}/\sigma_{i})/(\sum_{j=1}^{m}(1+L_{ij}/\sigma_{i}))$, and so

with $\kappa_{s}\geq\sigma_{i}^{-1}\sum_{j=1}^{m}L_{ij}$ for all $i$.

In the end, we would like these two bounds to be equal, so we choose $p_{\rm comp}$ and $p_{\rm comm}$ such that

Yet, we also know that $p_{\rm comm}=1-p_{\rm comp}$, so

With this choice, one can verify that $\eta_{t}$ verifies both $\eta_{t}\alpha\leq 2p_{\rm comm}$ and $\eta_{t}\alpha\leq 2\min_{ij}p_{ij}$, so the rate is:

The expected execution time to reach precision $\varepsilon$, denoted $T_{\varepsilon}$, is equal to $T_{\varepsilon}=\rho^{-1}(p_{\rm comp}+\tau p_{\rm comm})K_{\varepsilon}$ with $K_{\varepsilon}$ such that $C(1-\eta_{t}\alpha/2)^{K_{\varepsilon}}<\varepsilon$ for some constant $C$, and so:

B.2 Primal guarantees

The goal of this section is to recover primal guarantees from dual guarantees. Although the initial setting is inspired from Lin et al. [2015b], the proof is different, and in particular does not require smoothness of the $f_{ij}^{*}$ or an extra proximal step. We define for $\beta\geq 0$ the Lagrangian function:

The dual problem $D(\lambda)$ is defined as

Given an approximate dual solution $\lambda_{k}$, we can get an approximate primal solution $\theta_{k}=\arg\min_{\theta}\mathcal{L}(\lambda_{k},\theta)$, which is obtained as:

Denote $C_{0}=\frac{(\beta+\sigma_{\max}+L_{\max})}{2(\sigma_{\min}+\beta)^{2}}\left(\frac{p_{\min}}{\eta_{t}}D_{\phi}(\lambda^{\star},\lambda_{0})+\left(D(\lambda^{\star})-D(\lambda_{0})\right)\right)$, then

Using the fact that $\theta_{t}^{(i)}=\frac{1}{\sigma_{i}+\beta}((A\lambda_{t})^{(i)}+\omega_{t}^{(i)}$) (and similarly for $\theta^{\star}$), where $\Sigma_{\beta}$ is the block diagonal matrix such that $(\Sigma_{\beta})_{ii}=(\sigma_{i}+\beta)^{-1}I_{d}$, we obtain:

Using the $\min((\sigma_{\max}+\beta)^{-1},L_{ij}^{-1})$-strong convexity of $\theta\mapsto\frac{1}{2}x^{\top}\Sigma_{\beta}x+\sum_{i,j}f_{ij}^{*}(x^{(ij)})$, we obtain:

Then, we add $p_{\min}\eta_{t}^{-1}D_{\phi}(\lambda^{\star},\lambda_{t})\geq 0$ and apply Theorem 4, which yields

Then, Theorem 1 is a direct consequence of Theorem 4 and Lemma 5.

Appendix C Catalyst acceleration

We show in this Section how to apply Catalyst acceleration to DVR, and prove the convergence speed in this case.

In the main text, we derived DVR to solve regularized finite sum problems. Although not so different, the subproblem obtained with Catalyst is not in the form of Problem (1), and some adjustments need to be made. More specifically, we would like to solve problems of the form:

An easy way to adapt the algorithm is to consider the extra $(\beta/2)\|\theta-\omega_{t}^{(i)}\|^{2}$ as just another component of the sum. Yet, the point of this extra term is to make the problem easier to solve by adding strong convexity. This would not be the case if this term were is treated as just another term in the sum. Therefore, we want to include it with the quadratic term. We define:

then $h^{*}(x)=\frac{1}{2(\beta+\sigma)}\|x+\beta\omega_{t}^{(i)}\|^{2}-\frac{\beta}{2}\|\omega_{t}^{(i)}\|^{2}$. Therefore, Problem (4) becomes:

with $(\Sigma_{\beta})_{ii}=(\sigma_{i}+\beta)^{-1}$ for $i\in\{1,\dots,n\}$. The linear term does not affect the Hessians, and thus the convergence rate is the same as before, with $\sigma$ replaced by $\sigma+\beta$. In terms of algorithms, we just need to modify the gradient term, and obtain Algorithm 2. The only term that changes is $\nabla q_{A}(x,y)$, to which an extra $\beta\Sigma_{\beta}\omega_{t}$ term is added. Therefore, the updates to $\theta_{t}$ and $z_{t}$ remain unchanged, and only the initial expression of $\theta_{t}$ requires some adjustments since we now have that (as written in Equation 30):

If we only consider 1 inner loop then the only thing that changes is the initial condition. If we consider several outer loops, then the we must choose the new parameter as $\theta_{0}^{t+1}=\theta_{T}^{t}+\Sigma_{\beta}(\omega_{t+1}-\omega_{t})$ in order to maintain the invariant, but a remarkable fact is that the inner iterations remain the same, with the only exception that $\Sigma$ is replaced by $\Sigma_{\beta}$. Note that it is possible to warm-start the $z_{t+1,0}$ as well, but this requires updating $\theta_{t,0}$ accordingly with $\nabla f_{ij}(z_{t,0}^{(ij)})$, which requires a full pass over the local dataset. We therefore choose not to do it.

where $\bar{\omega}_{t}=\frac{1}{n}\sum_{i=1}^{n}\omega_{t}^{(i)}$. This means that although $F_{t}$ is only defined with the local variables $\omega_{t}^{(i)}$, solving $F_{t}$ is equivalent to solving a problem involving $\bar{\omega}_{t}$ only. Besides, the Catalyst iterations are linear, meaning that performing the extrapolation step on $\bar{\theta}_{t}$ is equivalent to performing it on each $\theta_{t}^{(i)}$ individually. Therefore, although Catalyst is implemented in a fully decentralized manner (each node knowing only its own parameter), it is conceptually applied to a mean parameter $\bar{\theta}_{t}$ (that is never explicitly computed). In the following, we thus analyze the performances of the following algorithm:

where we recall that $q=\sigma_{\min}/(\sigma_{\min}+\beta)$. Recall that the inner problem is approximated using DVR and the means do not need to be computed explicitly. Let $\kappa_{s}^{\beta}=\max_{i}1+(\sum_{j=1}^{m}L_{ij})/(\beta+\sigma_{i})$, and $\kappa_{\rm comm}^{\beta}$ be obtained similarly to $\kappa_{\rm comm}$ but replacing $\Sigma$ by $\Sigma_{\beta}$. We consider in this section that $\sigma_{i}=\sigma$ for all $i\in\{1,\dots,n\}$ in order to simplify exposition, but the results hold more generally. Note that $\alpha$ and $\eta$ have slightly different expressions than in the main text since $\beta$ is now involved in their definitions. We define the sequence $\varepsilon_{t}$ which is such that:

Note that the error is on the mean parameter, and we also want $\theta_{t}^{(i)}$ to be close to $\bar{\theta}_{t}$ for all $i$. This is ensured by Lemma 5. Before we start the proof of Theorem 5, we show that Theorem 2 is a corollary of Theorem 5.

Using the same argument as in Theorem 1, we obtain that each inner loop takes time

in expectation, so the total number of inner iterations is of order:

Therefore, we see that if we choose $\beta+\sigma=L_{\rm comm}$ then, taking into account the fact that $\kappa_{s}\leq m\kappa_{\rm comm}$, the algorithm takes time:

Therefore, using Chebyshev acceleration allows to recover the rate of optimal batch algorithms (up to log factors). On the other hand, if we choose $\beta=L_{s}/m-\sigma$ then if $\beta\geq 0$ (i.e., $\kappa_{s}\geq m$), the time to convergence is equal to:

Therefore, we obtain the optimal $\sqrt{m\kappa_{s}}$ computation complexity in this case, with a slightly suboptimal communication complexity due to the $\sqrt{m\kappa_{\rm comm}/\kappa_{s}}$ term. When this term is equal to $1$ then $\sqrt{m\kappa_{s}}=m\sqrt{\kappa_{b}}$ and so nothing is gained from using a stochastic algorithm. Otherwise, this allows to trade-off communications for computations. ∎

The proof of Theorem 5 is obtained in several steps, that we emphasize below:

Equivalent decentralized implementation of Catalyst.

Bounding the primal suboptimality as $F_{t}(\bar{\theta}_{t})-\min_{\theta}F_{t}(\theta)\leq(1-(\eta\alpha)/2)^{k}D_{0}^{t}$, with $k$ the number of inner iterations and $D_{0}^{t}$ a dual error. This quantifies how precisely the inner problem is solved.

Evaluating the initial dual suboptimality $D_{0}^{t}$, which depends on $\theta_{t-1}$ (and its associated dual parameter $\lambda_{t-1}$). This quantifies how good $\bar{\theta}_{t-1}$ already is as a solution to $F_{t}$.

In the end, this allows us to use the catalyst general results with primal criterion, and with simple warm-start scheme (warm-start on the last iterate of the last outer iteration). The first point is presented at the beginnning of this section and the second one is adressed by Lemma 5. The following section deals the last point.

C.2 Proof of Theorem 5

We now show a bound on the initial error of an inner loop when warm-starting on the last iterate of the previous inner loop. Indeed, the convergence results for DVR depend on the initial dual error and so results from [Lin et al., 2017] cannot be used directly. Yet, it can be adapted, as we show in this section. We note $D_{t}(\lambda)$ the dual function at outer step $t$ (which should not be mistaken with the Bregman divergence $D_{\phi}$), and $\lambda_{\star}^{t}$ its minimizer. Similarly, we note $\theta_{\star}^{t}=\arg\min_{\theta}F_{t}(\theta)$, whereas $\theta^{\star}$ is the global minimizer of $F$. The following theorem ensures convergence of $\bar{\theta}_{t}$ to the true optimum, given that the subproblems are solved precisely enough.

[Lin et al., 2017, Proposition 5]. If $F_{k}(\bar{\theta}_{k})-F_{k}(\theta_{\star}^{k})\leq\varepsilon_{k}$ for all $k\leq t$ then

Therefore, our goal is to prove that $F_{t}(\bar{\theta}_{t+1})-F_{t}(\theta_{\star}^{t})\leq\varepsilon_{t}$ for all $t$. The smoothness of $F_{t}$ ensures that this is achieved if

Yet, using Lemma 5, we know that, since $\theta_{t+1}^{(i)}$ is obtained by applying $K$ steps of DVR to $F_{t}$ starting from $\lambda_{0}^{t}$.

Unfortunately, we have no control over the dual error at this point. In the remainder of this section, we prove by recursion that Equation (40) holds for all $t$. More specifically, we start by assuming that:

where $C_{1}$ and $C_{2}$ are such that the conditions are verified for $t=-1$, with $D_{-1}=D_{0}$, $\theta_{\star}^{-1}=\theta_{\star}^{0}$, and $\lambda_{\star}^{-1}=\lambda_{\star}^{0}$. Equation (41) may not hold for $t=-1$, but making it hold at time $t=0$ would only require a slightly longer first inner iteration, meaning at most an extra $\log$ factor. Therefore we assume without loss of generality that it is the case, since the final complexities are given up to logarithmic factors. The rest of this section is devoted to showing that if $K$ is chosen as in Theorem 5 then Equations (41), (42) and (43) hold regardless of $t$. The first part focuses on assessing the initial error of outer iteration $t+1$ when the conditions hold at the end of outer iteration $t$, and the second part on showing how these errors shrink during outer iteration $t+1$.

We know that DVR converges linearly, and so the error for each subproblem decreases exponentially fast. Yet, we need to know how big the error is when solving a new problem in order to make sure that the progress from solving previous subproblems is not lost. The point of this is to avoid an extra $\log(\varepsilon^{-1})$ factor in the rate, which would come from having to solve each subproblem from a $O(1)$ precision to an $\varepsilon$ precision using DVR. We show in this section that the initial error is actually much lower than $O(1)$ and decreases with the outer iterations. We first start by bounding the variations of $\omega_{t}$ across iterations, which we will need for the next proofs.

The form of the updates yields that (see Lin et al. [2017, Proposition 12] or Li and Lin [2020, Proof of Lemma 10])

Note that here, $\theta^{\star}$ is the actual solution of the primal problem without the catalyst perturbation. Then, the error can be decomposed as:

Finally, the strong convexity of $F$ leads to

where in the last inequality we use [Lin et al., 2017, Proposition 5], which holds because $F_{k}(\bar{\theta}_{k})-F_{k}(\theta^{k}_{\star})\leq\varepsilon_{k}$ for all $k<t$. Indeed, $K$ is such that for all $k\leq t$, $\frac{1}{2}\sum_{i=1}^{n}\|\theta_{k}^{(i)}-\theta^{k}_{\star}\|^{2}\leq\frac{n}{L}\varepsilon_{k}$, which yields:

and a similar bound can be used for $\theta_{t-1}^{(i)}$ and $\theta_{t-2}^{(i)}$. Then, we finish proof by plugging in the expression of $\varepsilon_{t-1}$. ∎

We then use Lemma 6 to bound the initial dual error. We denote $\theta_{k}^{t}$ (and $\lambda_{k}^{t}$) the parameters at inner iteration $k$ of outer iteration $t$.

Note that we simply warm-start the dual coordinates for an outer iteration using the last iterate from the previous one. Yet, this leads to $\theta_{0}^{t}=\theta_{K}^{t-1}+\beta\Sigma_{\beta}^{-1}(\omega_{t+1}-\omega_{t})$, as in Algorithm 2.

Equation (34) implies that $D_{t}(\lambda)$ can be written as:

with $R_{\rm comp}(\lambda)$ that only depends on $\lambda^{(ij)}$ and not on $\omega_{t}^{(i)}$ for $i\in\{1,\cdots,n\}$. Therefore,

Equation (30) writes $(A\lambda_{\star}^{t})^{(i)}=(\beta+\sigma_{i})\theta_{\star}^{t}-\beta\omega_{t}^{(i)}$, and so:

Then, we know from the equivalent reformulation of Equation (LABEL:eq:catalyst_average_formulation) that $\theta_{t}^{\star}=\arg\min F(\theta)+\frac{\beta}{2}\|\theta-\bar{\omega}_{t}\|^{2}$, so using the $1$-Lipschitzness of the proximal operator yields

Similarly, $\Sigma_{\beta}(A\lambda_{\star}^{t-1}-A\lambda_{K}^{t-1})=\theta_{\star}^{t-1}-(\theta_{K}^{t-1})^{(i)}$, and so:

Finally note that $D_{t-1}(\lambda^{t}_{\star})\leq D_{t-1}(\lambda^{t-1}_{\star})$ since $\lambda^{t-1}_{\star}$ is the maximizer of $D_{t-1}$, and $(\theta_{K}^{t-1})^{(i)}=\theta_{t}^{(i)}$ since it is the output of DVR after inner iteration $t$. The final expression is obtained using 6 and the recursion assumptions given by Equations (41) and (43). ∎

Finally, the warm-start error on the nodes parameters is given by the two following lemmas.

Denote $\|\theta_{1}-\theta_{2}\|^{2}_{\rm comp}=\sum_{i=1}^{n}\sum_{j=1}^{m}\|\theta_{1}^{(ij)}-\theta_{2}^{(ij)}\|^{2}$. Then,

We use the fact that $(\theta_{t})^{(ij)}=(\theta_{0}^{t})^{(ij)}=(\theta_{K}^{t-1})^{(ij)}$ to write:

Then, as before, the 1-Lipchitzness of the prox operator yields $\|\theta_{\star}^{t-1}-\theta_{\star}^{t}\|\leq\frac{1}{n}\|\omega_{t}-\omega_{t-1}\|$. ∎

Denote $\|\theta_{1}-\theta_{2}\|^{2}_{\rm comp}=\sum_{i=1}^{n}\sum_{j=1}^{m}\|\theta_{1}^{(ij)}-\theta_{2}^{(ij)}\|^{2}$. Then,

We use the fact that since $\lambda_{0}^{t}=\lambda_{K}^{t-1}$ then $(\theta_{0}^{t})^{(i)}=(\theta_{0}^{t})^{(i)}+\frac{\beta}{\beta+\sigma_{i}}(\omega_{t}^{(i)}-\omega_{t-1}^{(i)})$ to write:

We finish this part on warm starts by proving the following lemma, that links the initial dual parameters error (computed with the Bregman divergence of $\phi$), to the other parameters which we already know how to control.

with $C_{\phi}=\frac{6\left(C_{\omega}+n/L\right)+L_{\max}^{2}(2C_{\omega}+2mC_{1})}{\lambda_{\min}^{+}(A^{\top}\Sigma_{\beta}^{2}A)}+\frac{2L_{\max}(C_{\omega}+2mC_{1})}{\alpha}$.

We first decompose the Bregman divergence as:

Then, we bound the communication term as:

For the computation part, we use the duality property of the Bregman divergence, which yields

Substituting Equations (52) and (53) into Equation (51) finishes the proof. ∎

C.2.2 Inner iteration error decrease

Now that we have bounded the error at the beginning of each outer iteration, we bound error at the end of each outer iteration by using the convergence results for DVR. We first prove the following Lemma, which controls the distance between the virtual parameters and the actual one:

where in the last inequality we used the convexity of the squared norm. We use that $p_{ij}\rho_{ij}\geq\rho$ (equal for the smallest one), and write that:

Noting $\rho_{\rm sum}=\max_{i}\sum_{j=1}^{m}\rho_{ij}p_{ij}$ and $\|\theta_{k}^{t}-\theta_{\star}^{t}\|^{2}_{{\rm comp},i}=\sum_{j=1}^{m}\|(\theta_{k}^{t})^{(ij)}-\theta_{\star}^{t}\|^{2}$, we obtain

Using Lemma 5, we know that $\sum_{i=1}^{n}\|(\theta_{k}^{t})^{(i)}-\theta_{\star}^{t}\|^{2}\leq C_{0}(t)(1-\rho)^{k}$, with $C_{0}(t)$ a constant that depends on the initial conditions of outer iteration $t$. Therefore,

If Equations (41), (42) and (43) hold at time $t$, and $K$ is such that:

Using Corollary 1, we obtain that if $K$ is set such that

then the recursion condition is respected for the virtual parameters. This yields the first and second conditions on $K$. Now, we write $C_{L}=\left(\frac{p_{\min}}{\eta_{t}}C_{\phi}+C_{D}\right)$, then using Lemmas 10 and 7 (where $C_{\phi}$ and $C_{D}$ are defined), we obtain using Theorem 4 that

since $\lambda_{t+1}$ is obtained by performing $K$ iterations of DVR to minimize $F_{t}$ starting from $\lambda_{t}$. This yields the third condition on $K$. Finally, the last condition on $K$ is obtained by leveraging Lemma 5.

Appendix D Experiments

For the experiments, the following logistic regression problem is solved:

Figure 2 is the full version of Figure 1, in which we report the number of individual gradients and number of communications for each configuration. We see that accelerated EXTRA actually outperforms EXTRA when the regularization is small, as already mentioned in the main text. We also see that Accelerated EXTRA and Accelerated DVR have comparable communication complexity on the grid graph, when $\gamma$ is smaller. Yet, the computation complexity of (accelerated) DVR is much smaller, so accelerated DVR is much faster overall as long as $\tau$ is not too big.