Decentralized and Parallel Primal and Dual Accelerated Methods for Stochastic Convex Programming Problems

Introduction

We consider the stochastic convex optimization problem

number of calculations of unbiased stochastic subgradients $\nabla f(x,\xi)$ by using batch parallelization [Devolder, 2013, Dvurechensky and Gasnikov, 2016, Gasnikov and Nesterov, 2018, Ghadimi and Lan, 2013]. In this case we can parallelize subgradients calculations on no more than

processors (depending on where the minimum in (3) is reached). Notice that this is much better than in previous case. Since this result cannot be improved [Woodworth et al., 2018], it is the best possible way (in general) to solve (1) by using parallel architecture in online context [Shalev-Shwartz et al., 2009].

For many reasons, in some situations in practice, it can be impossible to organize model-based requestFor desired $x$ and independently generated $\xi$, a request returns $\nabla f(x,\xi)$. This allows not to keep the set of functions $\{f(x,\xi^{k})\}_{k}$ for different $k$ in the memory. for calculating stochastic gradient $\nabla f(x^{k},\xi^{k})$ in online regime. Typically, in machine learning applications [Hastie et al., 2001, Shalev-Shwartz and Ben-David, 2014], instead of online access to $\left\{\nabla f(x^{k},\xi^{k})\right\}_{k=1}^{m}$ we have offline access. This means that the set of functions $\left\{f(x,\xi^{k})\right\}_{k=1}^{m}$ are stored in the memory and to use them in algorithms, we need to request corresponding function and then calculate its gradient. This may significantly change the complexity of the problem. Indeed, it is known from [Guigues et al., 2017, Shalev-Shwartz et al., 2009, Shapiro et al., 2009] that with high probability the exact solution of problem

is an $\varepsilon$-solution (in the function value) of problem (1) if

where $f_{k}(x,\eta^{k})=f(x,\xi^{kl+\eta^{k}})$ and $\eta^{k}=i$ with probability $1/l$, $i=1,...,l$. Representation (5) allows to use bound (3) in the stochastic case in a parallel manner at each node. The number of oracle calls per node also corresponds (in general) to (3) and the number of communication steps is also $d$ times more than (3) with $\sigma^{2}=0$.

Unfortunately, centralized architecture has a synchronization drawback and a high requirement for the master node [Scaman et al., 2017]. To address these disadvantages to some extent, a decentralized distributed architecture should be used [Bertsekas and Tsitsiklis, 1989, Kibardin, 1979]. This architecture relies on two basic principles [Nedic, 2020]: every node communicates only with its neighbors, and all communications are performed simultaneously. The main difference here is a simple strategy of communications: each node communicates only with all available direct neighbors. This architecture is more robust. In particular, it can be applied to time-varying (wireless) communication networks [Rogozin et al., 2018].

As problems (4) and (5) have a definite structure of the sum type, they can be solved much faster on one machine. For instance, using some incremental algorithms [Allen-Zhu, 2017, Lan and Zhou, 2017, Lin et al., 2015, Woodworth and Srebro, 2016], one can solve (4) $\sqrt{m}$ times cheaper in terms of the number of oracle calls, but not in terms of the number of iterations ( =communication steps). Unfortunately, this result prohibits parallelization. Note, that for this problem in asynchronized mode ( at each step only two randomly chosen nodes can communicate ), one can obtain such ($\sim\sqrt{m}$) an acceleration for the star-type communication network [Lan and Zhou, 2018]. Moreover, a ‘dual’ analogue of this acceleration has recently been proposed for (4) [Hendrikx et al., 2018] and (5) [Hendrikx et al., 2019a, Hendrikx et al., 2019b] with arbitrary communication networks.

We justify the transition from the optimal centralized distributed complexity bounds for problems (4) and (5) in the smooth case to decentralized ones In the deterministic case this was partially done in [Li et al., 2018]. by replacing $d$ with $\sqrt{\chi}$, the average $L$ with the worse one and variance of $f$ with the variance of $f_{k}$, that can be $m$ times more.For instance, this takes place in the case when we have independent noise at each $f_{k}$. Note also that in this case in decentralized distributed optimization one can improve the variance dependence and eliminate factor $m$ (see [Olshevsky et al., 2019a, Olshevsky et al., 2019b]). But, this is possible due to the worse estimate for the number of communication steps. Here and everywhere below we keep $\mu$ at the average level (without loss of generality, we can assume that each $f_{k}$ has the same $\mu$) by using a trick from [Scaman et al., 2017]. The announced results are also not improvable in terms of communication steps (rounds) [Arjevani and Shamir, 2015, Scaman et al., 2017].

By using different smoothing techniques [Allen-Zhu and Hazan, 2016, Nesterov, 2005, Scaman et al., 2018], we may lead the non-smooth case to the smooth one with $L\sim 1/\varepsilon$. This allows to reduce the complexity estimate (2) by using (3). However, in general, this reduction makes the cost of oracle calls more expensive. Thus, we can only improve the communication steps (rounds) bound that corresponds to (3) (up to a $\sqrt{\chi}$ factor) with $L\sim 1/\varepsilon$ and $\sigma^{2}=0$.Note that such tricks sometimes allow to obtain the optimal (in terms of dependence on $\varepsilon$) communication round estimates [Arjevani and Shamir, 2015, Scaman et al., 2018]. Can we preserve the bound (2) for standard conception of oracle calls (primal oracle that gives $\nabla f_{k}$) per node in decentralized approach by improving the number of communication steps? The answer is positive up to the replacement of the average $M$ to the worst one [Lan et al., 2017, Scaman et al., 2018]. In our paper, we simplify the approaches proposed in these articles to prove this result.

As a motivation for the second main result, we consider the problem of type

We develop optimal decentralized distributed algorithms with dual (stochastic) oracle for strongly convex objective in (6). The approach is based on dual reformulation of (6) [Scaman et al., 2017]. An optimal algorithm for non-strongly convex dual function with stochastic oracle was recently proposed in [Dvinskikh et al., 2019]. To propose an optimal method with stochastic dual oracle for strongly convex primal objective, we use recent work [Foster et al., 2019]. We notice a rather unexpected result: we cannot improve (up to a logarithmic factor) the bound for the number of dual stochastic gradient calculations in comparison with non-strongly convex dual objective.

We also notice that initially we were motivated by the study of the dual oracle not only as an application from [Dvinskikh et al., 2019, Dvurechenskii et al., 2018, Uribe et al., 2018]. We also tried to find a simple explanation for the optimal communication step bounds [Arjevani and Shamir, 2015, Scaman et al., 2018] in non-smooth case. One of the ways to do it is Nesterov’s dual smoothing technique [Nesterov, 2005] that builds a bridge to the notion of dual oracle. This plan was partially (in the deterministic case) implemented in [Scaman et al., 2017, Uribe et al., 2020, Uribe et al., 2020]. Here we generalize the results of these works for the stochastic dual oracle.

2 Paper organization

The paper is organized as follows. In Section 2, we propose optimal stochastic (parallelized) accelerated gradient methods for stochastic convex optimization problems. In Sections 3 and 4, we apply the results of Section 2 to stochastic convex optimization problems with affine type of constraints (of type $Ax=0$). We describe the modern stochastic (parallelized) accelerated gradient methods which are optimal both in terms of (stochastic) oracle calls and matrix-vector multiplications $Ax$. In Sections 3, we are focusing on primal methods, in Section 4, we present dual ones. Section 5, describes the distributed primal and dual formulation of the finite-sum minimization problem, and presents distributed algorithms. In Section 6, we incorporate the proposed distributed decentralized method to get the optimal bounds for the finite-sum minimization problem using primal or dual oracle. Finally, we discuss future work and possible extensions. We notice that all proposed methods are optimal in terms of communication steps and in many cases in terms of (parallel stochastic) primal/dual oracle calls.

Stochastic convex optimization

First-order methods for the optimization problem of minimizing a convex function $f$ on a simple convex set $Q$, e.g.,

play a fundamental role in modern problems arising in machine learning and statistics. The complexity of these methods is measured by the number of iterations or (and) the number of oracle calls. For a deterministic oracle, this concept can be identified. By the first-order oracle, we mean a black-box model that for a given input $x\in Q$, returns the vector $\nabla f(x)$.

We say that a function $f$ is $M$-Lipschitz continuous if Here and below in such type of assumptions (especially in the case when $Q$ is unbounded) instead of $\forall x\in Q$ we may write $\forall x\in Q:\|x-x^{*}\|_{2}\leq 2R$ [Gasnikov, 2017] (analogously for $y$).

We say that function $f$ is $L$-smooth or has $L$-Lipschitz continuous gradient if

We also say that function $f$ is $\mu$-strongly convex if

Accelerated gradient methods (e.g., Algorithm 1 (STM) [Gasnikov and Nesterov, 2018, Nesterov, 2018b, Lan, 2019]) allow to obtain the optimal number of iterations and number of gradient oracle calls for problem (7) as described in Table 1, where $R=\|x^{0}-x^{*}\|_{2}$ is the Euclidean distance from the starting point $x^{0}$ to the solution $x^{*}$ of (7) that corresponds to the minimum of this norm, and $\varepsilon$ is the desired precision in function value.

For a composite optimization problem with composite term $h(x)$, step 4 of Algorithm 1 is replaced by the more general operator [Gasnikov and Nesterov, 2018, Nesterov, 2018b]

where $\varepsilon$ is desired accuracy (in function value) for initial problem (7). If $\mu=0$ we can also generalize this step for the non-Euclidean case and using restarts [Gasnikov and Nesterov, 2018] generalize such a method on $\mu>0$. Note, that by using restarts with STM($L$,0,$x^{0}$) one can eliminate the gap from $\ln(LR^{2}/\varepsilon)$ to $\ln(\mu R^{2}/\varepsilon)$ between lower bounds and the bounds for STM($L$,$\mu$,$x^{0}$) without restarts [Gasnikov and Nesterov, 2018]. The same remains true for the stochastic oracle.

then with probability at least $1-\beta$, we have $f(x^{N})-f(x^{*})\leq\varepsilon$ after

where $\xi_{1}^{k+1},\dots,\xi_{r_{k+1}}^{k+1}$ are i.i.d from the same distribution as $\xi$ and the batch size is

Moreover, the total number of oracle calls Oracle calls can be easily and fully parallelized (on $r_{k}$ processors) at each iteration. Note, that for $\nabla^{r_{k}}f(x,\{\xi_{i}\}_{i=1}^{r_{k}})$ we can reduce the variance $\sigma^{2}:=O(\sigma^{2}/r_{k})$. is (this bound is optimal up to logarithmic factors)

We refer to such a variant of STM as BSTM($L$,$\mu$,$\sigma^{2}$,$x^{0}$) (batched STM($L$,$\mu$,$x^{0}$)).

Thus, using minibatches for constructing an approximation of the true gradient allows us to keep the optimal number of iterations for stochastic methods, as presented in Table 1, where we skip high probability logarithmic multipliers. The number of stochastic oracle calls for this case is shown in Table 2.

STM outputsNote, that according to [Poljak, 1981] even for the last point of gradient descent on a simple quadratic optimization problem we cannot guarantee convergence without proper stopping rule. With proper stopping rule in (8) it is required (see [Polyak, 1987, Theorem 7, item 6.1.3]) $\delta\sim\varepsilon^{2}$ that is worse than what we have $\delta\sim\varepsilon$. But we can guarantee standard convergence of noisy gradient descent under (8) in (Cesaro) average [Gasnikov, 2017] (not for the last point). The results below generalize [Gasnikov, 2017] on a proper accelerated method (STM). $x^{N}$ such that [Devolder et al., 2014, Dvinskikh et al., 2020]

In particular, for the case of non-smooth objective, the stochastic oracle does not yield gains compared to its deterministic counterpart.

Both in Table 1 and in Table 2, the last two columns can be obtained from the corresponding first columns by choosing $L=M^{2}/(2\delta)$, where $\delta=\varepsilon/N$ (see [Gasnikov and Nesterov, 2018]). This is the idea of universal accelerated methods [Nesterov, 2015], but with predefined $L$. Here and in all further tables we skip numerical constants.

Primal methods for stochastic convex optimization with affine constraints

To build the complete theory of distributed primal and dual method we need to generalize the result of Tables 1 and 2 for the convex optimization problemIn decentralized optimization $A$ is taken to be $\sqrt{W}$ (square root of the Laplacian matrix of the communication network).

where $A{\succeq}0$ and $\text{Ker}A\neq\varnothing$. The purpose of this section is to develop such algorithms for (12) that are optimal in terms of the number of $\nabla f(x)$ calculations and the number of $A^{T}Ax$ calculations. In this section we use Euclidean proximal setup [Ben-Tal and Nemirovski, 2001]. This is the only section where we significantly rely on Euclidean prox-structure.

Using the penalty method we rewrite (12) as follows

Next we use [Gasnikov, 2017, Remark 4.2] and get if the following holds

This factor arises because of the complexity of the auxiliary problem. We refer to these approaches as PSTM and PBSTM (Penalty STM and BSTM). Here and below we skip arguments of the algorithms if they are obvious from the context.

In non-smooth case ($f$ is $M$-Lipschitz), we use the Sliding algorithm [Lan, 2016], [Lan, 2019] . If $\mu=0$ according to [Lan, 2016] this algorithm requires (see Tables 1, 2 for comparison)

$O\left(\sqrt{\frac{\lambda_{\max}(A^{T}A)R_{y}^{2}R_{x}^{2}}{\varepsilon^{2}}}\right)$

$O\left(\frac{M^{2}R_{x}^{2}}{\varepsilon^{2}}\right)$

calculations of $\nabla f(x)$, where $R_{x}=\|x^{0}-x^{*}\|_{2}$.

If we have unbiased $\nabla f(x,\xi)$ with $\sigma^{2}$-sub-Gaussian variance [Jin et al., 2019] instead of $\nabla f(x)$, i.e.,

with $\sigma^{2}=O(M^{2})$ (for compact notationIn general $M^{2}$ is replaced by $M^{2}+\sigma^{2}$ in the stochastic case.), then the bound for calculations of $A^{T}A$ does not change and the bound for calculations of $\nabla f(x,\xi)$ is the same as it was for the number of calculations of $\nabla f(x)$ in deterministic case (up to a logarithmic high-probability deviations factor).

By using a restart technique [Uribe et al., 2020] we can generalize this method for $\mu$-strongly convex $f$:

calculations of $\nabla f(x)$ ($\nabla f(x,\xi)$).

We call this approach by R-Sliding (Restart Sliding).

Dual methods for stochastic convex optimization with affine constraints

Now we assume that we can build a dual problem for

We notice that turning to a dual problem does not oblige us using dual oracle. Instead, we can use a primal oracle and the Moreau theorem [Rockafellar, 2015] with Fenchel-Legendre representation. This maximization problem can be solved using the first-order oracle for the function $f$. But such an approach does not allow to obtain the optimal bounds on the number of primal first-order oracle calls. Note that typically in decentralized optimization $A$ in (15) is taken as the square root of the Laplacian matrix $W$ of the communication network [Scaman et al., 2017]. But in the asynchronized case the square root $\sqrt{W}$ replaced by incidence matrix $M$ [Hendrikx et al., 2018] ($W=M^{T}M$). Then in asynchronized case instead of accelerated methods for (4) one should use an accelerated (block) coordinate descent method [Dvurechensky et al., 2017, Gasnikov, 2017, Hendrikx et al., 2018, Shalev-Shwartz and Zhang, 2014].

The dual problem (up to a sign) is following

If we have only a stochastic (randomized) unbiased model $\nabla\varphi(\lambda,\xi)|_{\lambda=A^{T}y}=x(A^{T}y,\xi)$ with $\sigma^{2}_{\varphi}$-sub-Gaussian variance, i.e.

then for BSTM($L_{\psi}$,0,$\sigma^{2}_{\psi}$,0) where $\sigma^{2}_{\psi}=\lambda_{\max}(A^{T}A)\sigma^{2}_{\varphi}$ with probability $\geq 1-\beta$ (4) holds true [Dvinskikh et al., 2019]. We refer to this algorithm as SPDSTM (Stochastic PDSTM).

it is sufficient to find such $y^{N}$ ($\|y^{N}\|_{2}\leq 2R_{y}$) that

Recently, there appear accelerated methods with the proper rate of convergence in terms of the norm of the gradient OGM-G [Gasnikov, 2017, Kim and Fessler, 2018]:

After $\bar{N}=O\left(\sqrt{\frac{L_{\psi}}{\mu_{\psi}}}\right)$ iterations of OGM-G we have

So after $l=\log_{2}\left({\|}\nabla\psi(y^{0})\|_{2}\frac{R_{y}}{\varepsilon}\right)$ restarts ($y^{0}:=y^{\bar{N}}$) we have (19). We denote such an approach by ROGM-G (Restart OGM-G). This approach requires

of $\nabla\psi(y)$ (that is $Ax(A^{T}y)$) calculations. The key inequality to prove this fact is

can be obtained by using STM($L_{\psi}$,$\mu_{\psi}$,0) with bound ${\sqrt{\frac{L_{\psi}}{\mu_{\psi}}}}\ln\left(\frac{L_{\psi}R_{y}^{2}}{\varepsilon^{\prime}}\right)$ (see [Nesterov, 2010]) and desired accuracy $\varepsilon^{\prime}=\frac{\varepsilon^{2}}{2L_{\psi}R^{2}_{y}}$. This follows from

Now we consider RRMA+AC-SA2 [Foster et al., 2019] (see also [Allen-Zhu, 2018] in the non-accelerate, but composite case). This algorithm converges as follows (for simplicity we skip polylogarithmic factors and high probability terminology)

then $\|\nabla\psi(\bar{y}^{l})\|_{2}\leq\varepsilon/R_{y}$ after $l=O\left(\log_{2}\left(\|\nabla\psi(y^{0})\|_{2}R_{y}/\varepsilon\right)\right)$ restarts. Therefore, the total number of oracle calls is

Decentralized distributed optimization

Now we show how to present (6) in a decentralized distributed manner

where ${\rm deg}(i)$ is the degree of vertex $i$ (i.e., the number of neighboring nodes).

To present problem (P1) in a distributed fashion we rewrite it with introducing the artificial consensus equality constraints and then change these constraints to one affine constraint with the communication matrix $W$ as follows

where all $f_{k}$ are $M$-Lipschitz, $L$-smooth and $\mu$-strongly convex (it is possible that, $L=\infty$ or (and) $\mu=0$).

Problem (P2) can be considered to be a particular case of problem (12) with the following replacements

$A^{T}Ax=Wx$ (calculated in a decentralized distributed manner)

Problem (D2) can be considered as a particular case of problem (4) with

The main observation in the dual approach (see Section 4) is as follows [Scaman et al., 2017]: since $x(A^{T}y)=\mathbf{x}(\sqrt{W}\mathbf{y})$ we should change the variables as follows

It is obvious that input, output and steps 3–5 of Algorithm 2 are changed such that they can be performed in a decentralized distributed manner. For that we just multiply the corresponding steps by $\sqrt{W}$.

Main Results

In this section, we present the rates of convergence for problems (P1) and (D2) (and their stochastic counterparts) in terms of the number of iterations (communication steps) and the number of (parallelized) oracle calls. For the primal problem, we present the results to achieve $\varepsilon$-precision in objective residuals, and for the dual problem we seek to achieve $\varepsilon$-precision in duality gap or primal objective residuals (in smooth strongly convex case). Feasibility constrains are smaller than $\varepsilon/R_{\mathbf{y}}$.

For brevity, we introduce the condition number of the Laplacian matrix $W$ as follows

where $\lambda_{\min}^{+}(W)$ is the minimal positive eigenvalue of $W$, and $\lambda_{\max}(W)$ is the maximal eigenvalue of $W$. Now we are ready to present our main results incorporated in multiple tables: Tables 3– 6. These results are obtained by direct substitution of constants from Section 5 to the problems from Sections 3 and 4.

Note that the bounds on communication steps (rounds) are optimal (up to a logarithmic factor) due to [Arjevani and Shamir, 2015, Scaman et al., 2017, Scaman et al., 2018]. Bounds for the oracle calls per node are probably optimal in the class of methods with optimal number of communication steps (up to a logarithmic factor) in the deterministic case [Allen-Zhu, 2018, Foster et al., 2019, Woodworth et al., 2018] and optimal for the non-smooth stochastic primal oracle and stochastic dual oracle for parallel architecture.In parallel architecture the bounds on stochastic oracle calls per node of type $\max\{B,D\}$ can be parallel up to $B/D$ processors. For stochastic oracle the bounds hold in terms of high probability deviations (we skip the corresponding logarithmic factor).

This bound is optimal but it uses an incremental oracle and does not imply full parallelization. The best known way to parallelize it is described in [Lan and Zhou, 2018]. For full parallelization one should use a standard accelerated scheme without variance reduction and incremental oracle [Woodworth et al., 2018]. In this case, another bound for the total number of oracle calls occurs, that is

But this bound assumes the natural way of parallelization or centralized distribution of calculations. In the last case for a graph of diameter $d$ with $m$ nodes we have the following number of oracle calls per node

and the following number of communication steps

For decentralized architecture (see Table 4) the number of oracle calls per node and the number of communication steps are

respectively. Unfortunately, the factor $m$ is no longer presented in $\sigma^{2}$ in the decentralized case. It is interesting to note, that it is possible to propose such a decentralized distributed algorithm that requires

oracle calls per node (stochastic gradients calculations) [Olshevsky et al., 2019a, Olshevsky et al., 2019b]. However, this algorithm is not optimal in terms of communication steps. Moreover, to the best of our knowledge, it is an open question whether is (21) optimal bound in terms of oracle calls (per node) in the class of methods with the optimal number of communication steps.

Note also that the blue bound in Table 6 seems to be rather unexpected at first sight for us. But we hypothesize that this bound is optimal not only in terms of the number of communication steps but also in terms of the number of oracle calls (per node) in the class of methods with the optimal number of communication steps.

The detailed proofs of the statements collected in this paper takes more than 90 pages. These can be found in the arXiv preprint [Gorbunov et al., 2019]:

Discussion

Below we outline various areas for further work.

We can expect that the results can be improved by replacing the first-order methods with primal and dual deterministic oracle by tensor methods ($p=2,3$) from [Nesterov, 2018a]. However, for the moment we do not know any such results. For the dual approach we also do not know how to use the trick $A=\sqrt{W}$ (see [Scaman et al., 2017]). Here we should take $A=W$, which (with additional increased complexity of auxiliary problem) makes the bounds on communication steps worse. The basic fact in the dual approach is the following. To solve auxiliary problems we have to calculate the values of the form $\nabla^{p}_{y}\varphi(Wy)$ on different vectors [Carmon and Duchi, 2016, Nesterov, 2018a, Nesterov, 2018b]. This can be done multiplying $W$ by vectors (communications) and multiplying corresponding (block) diagonal tensor ( $\nabla^{p}_{\lambda}\varphi(\lambda)|_{\lambda=Wy}$) by vectors (can be distributed among nodes)

The primal approach in the smooth case can be generalized for the (stochastic inexact) gradient-free oracle. The number of communication steps remains the same. The number of oracle calls becomes $\sim n$ times larger [Gorbunov et al., 2018, Dvurechensky et al., 2017]. In the non-smooth case gradient-free (stochastic) decentralized distributed algorithm was developed in [Beznosikov et al., 2019]

In [Hendrikx et al., 2019a], [Hendrikx et al., 2019b] asynchronized distributed optimization was considered via dual accelerated (block) coordinate descent algorithms. The primal approach proposed above allows asynchronized generalizations in the smooth case. For that we should use the (block) coordinate version of STM [Dvurechensky et al., 2017] and additional randomization of sum type when $[Wx]_{i}$ is calculated. This will increase the number of communication steps $\sim\sqrt{n}\div n$ times

Most of the results of this paper can be generalized to composite problems [Nesterov, 2013]. Perhaps, it is possible to make the next step and try to generalize these results to more general types of models [Stonyakin et al., 2019b, Stonyakin et al., 2019a]

For smooth convex centralized distributed optimization problems there exists a universal way to accelerate non-accelerated (stochastic, asynchronized etc.) algorithm Catalyst [Lin et al., 2015]. The basic idea is using a non-accelerated centralized distributed algorithm for the inner problem arising at each step of the Catalyst procedure

Perhaps, it is possible to generalize the primal approach described above on time-varying graphs [Rogozin and Gasnikov, 2019]. Moreover, these generalizations can be done also for the smooth stochastic case

It seems the result of [Rogozin et al., 2018] can be improved by using mixed communication: many decentralized steps alternate with centralized ones. In this case, one can use non-accelerated distributed decentralized algorithms, which are robust on time-varying graphs [Rogozin et al., 2018], and then accelerate them by using the Catalyst technique [Lin et al., 2015] and centralization. Since the graph is changing we should recalculate spanning tree whenever we apply a centralized step. We expect that this mixed communication will be useful also for tensor schemes in decentralized optimization

The main scheme in the primal approach is based on the result formulated directly after (14). This result does not depend on convexity of the objective. So it would be interesting to apply this scheme for non-convex distributed optimization problems [Sun and Hong, 2018]

Since the first version of this paper was submitted on arXiv, there appeared alternative explanations (for smooth problems) of the results for the primal deterministic oracle [Fallah et al., 2019, Kovalev et al., 2020, Li and Lin, 2020, Xu et al., 2019, Hendrikx et al., 2020a] and the primal stochastic oracle (strongly convex case) [Fallah et al., 2019]. Moreover, in [Rogozin et al., 2020, Ye et al., 2020] (see also [Rogozin and Gasnikov, 2019] for the non-accelerated case and [Scaman et al., 2018] for lower bounds) for the primal deterministic oracle (strongly convex case) it was shown that $L:=\max_{k}L_{k}$ used in this paper can be improved to $L:=L_{f}$, where $L_{f}$ is the Lipschitz gradient constant of (6) (which can be much smaller [Tang et al., 2019]). The same holds true for $\mu$. More interestingly, we expect that combinations of [Rogozin and Gasnikov, 2019, Rogozin et al., 2020, Ye et al., 2020] allows to develop accelerated decentralized distributed primal algorithms on time-varying graphs (accelerated in $L$ and $\varepsilon$, but not in $\chi$). Moreover, based on [Rogozin and Gasnikov, 2019, Rogozin et al., 2020, Ye et al., 2020] we may expect that the answer to the open problem posed in the Section 6 is negative. The bound can be decreased by a factor $m$ for a stochastic primal oracle. The reasons for that are almost the same that we have for the $\max_{k}L_{k}\to L_{f}$ improvement.

We assume that all $f_{k}(x,\xi)$ in (22) satisfy

Also we introduceNote that nowadays it’s quite popular to obtain estimates on rate of convergence that depend on the constants defined at the solution point $x^{*}$ [Stonyakin et al., 2020].

Assume now that at each iteration $t$ we may call one time an oracle (that returns an independent realization of $\nabla f_{k}(x^{t},\xi^{t,k})$) at each node and make no more than one communication step with (in general, random) communication matrix $\bar{W}_{k}$. Moreover, we assume that [Koloskova et al., 2020]In [Koloskova et al., 2020] it was also assumed that symmetric matrix $\bar{W}$ determined by doubly stochastic matrix $P$: $\bar{W}=P-I$, where $I$ – unit matrix. So do we. But below, when we generalize the results of [Koloskova et al., 2020] on a large class of algorithms that assumes more than one communication on one iteration, we may consider $\bar{W}$ to be the same as in section 5 and $\chi$ is determined in (20) style.

where $\beta\in$, $\alpha=1\text{ or }1/2,$ here $I$ is a function such that $I[\rm true]=1$, $I[\rm false]=0$, and when $f_{k}$ is $\mu$-strongly convex

If we remove the condition that at each iteration we can only call stochastic oracle one time and make no more than one communication, then the blue term can be eliminated with $\alpha=1/2$. More precisely, the first two terms correspond to the total number of oracle calls per node and the last term – to the number of communications steps. Up to a factor $m$ in the denominator we have developed these results in the paper, but with $\tau=1$ and fixed $W$.For time-varying communication graphs in the eneral case for the moment it seems that we should put the factor $\chi$ instead of $\sqrt{\chi}$ in the last term [Rogozin and Gasnikov,]. We also note that it is an open problem whether it is possible in the general (accelerated) situation ( which differs from the [Koloskova et al., 2020]) to determine $\bar{\zeta}^{2}$ and $\bar{\sigma}^{2}$ only at point $x^{*}$? It seems, that for the current moment of time we have a positive answer only with respect to $\bar{\zeta}^{2}$.

The following generalizations are related with the case

In this case with additional assumptions about proximal and dual friendly $f_{k}$ it is possible to reduce worth case constant $L$ to the ¡¡average¿¿ one [Hendrikx et al., 2020b]. In [Hendrikx et al., 2020b] this looks like a variance reduction acceleration, but the nature of the effect (also explained in [Hendrikx et al., 2020b]) based on coordinate descent acceleration [Nesterov and Stich, 2017] for the dual problem formulation. In [Hendrikx et al., 2020a] was proposed a dual-free generalization of [Hendrikx et al., 2020b] with a bit worse oracle complexity estimate. The main idea is to apply a non-accelerated coordinate descent for the dual problem with Bregman divergence determined by the dual function itself. In [Li et al., 2020] an optimal algorithm both for communications steps and oracle calls per node was developed.

Another way to obtain a better result for the required number of communication steps is possible if $\{f_{kj}\}$ have i.i.d. nature (that is typically for data science applications). In this case $f_{k}$ is statistically similar to $f$. Based on this fact in centralized architecture, we may use on a master node statistical preconditioned algorithms that can significantly reduce the required number of communications with slaves [Hendrikx et al., 2020c].

Acknowledgment

The work of D. Dvinskikh in Sections 1 and 5 was supported by RFBR 19-31-51001 and in Section 6 was funded by the Russian Science Foundation (project 18-71-10108). The work of A. Gasnikov was supported by the Ministry of Science and Higher Education of the Russian Federation (Goszadaniye) no. 075-00337-20-03, project No. 0714-2020-0005.

We would like to thank F. Bach, P. Dvurechensky, E. Gorbunov, A. Koloskova, A. Kulunchakov, J. Mairal, A. Nemirovski, A. Olshevsky, S. Parsegov, B. Polyak, N. Srebro A. Taylor and C. Uribe for useful discussions.

References