Excess-Risk of Distributed Stochastic Learners

By Zaid J. Towfic, Jianshu Chen, Ali H. Sayed. 2013

26 citations recorded by the source corpus.

This paper studies the learning ability of consensus and diffusion distributed learners from continuous streams of data arising from different but related statistical distributions. Four distinctive features for diffusion learners are revealed in relation to other decentralized schemes even under left-stochastic combination policies. First, closed-form expressions for the evolution of their excess-risk are derived for strongly convex risk functions under a diminishing step-size rule. Second, using these results, it is shown that the diffusion strategy improves the asymptotic convergence rate of the excess-risk relative to non-cooperative schemes. Third, it is shown that when the in-network cooperation rules are designed optimally, the performance of the diffusion implementation can outperform that of naive centralized processing. Finally, the arguments further show that diffusion outperforms consensus strategies asymptotically and that the asymptotic excess-risk expression is invariant to the particular network topology. The framework adopted in this paper studies convergence in the stronger mean-square-error sense, rather than in distribution, and develops tools that enable a close examination of the differences between distributed strategies in terms of asymptotic behavior, as well as in terms of convergence rates.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “In the context of decentralized optimization, previous works have studied the error convergence in terms of iterations or communication rounds for decentralized gradient descent [1], [2], [3], [4], [5], [6], [7], [8] mostly for (strongly) convex loss functions.”
Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic Rates. (2018, background): “y(a:s:) E[v i(k;x i(k)) 2 jF k;z i;k] c vkx i(k)k 2 + ˙2 v; a:s:; (22) where c v and ˙2 are nonnegative constants. Assumption A4 is standard in the analysis of stochastic optimization methods, e.g., [10]. It is stated in terms of noise v i(k;x i(k)) in (17) rather then directly in terms of the SZOno”
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent (2019, background): “ditions. In addition to [8,9,10] discussed before, [25,26] proved that distributed stochastic approximation performs asymptotically as well as centralized schemes by means of a central limit theorem. [48] rst showed that a distributed stochastic gradient algorithm asymptotically achieves comparable ”
Efficient Distributed Online Prediction and Stochastic Optimization With Approximate Distributed Averaging (2014, methodology): “An alternative diffusion-based approach is studied in [33], [34] uses a constant step-size.”
Convergence Rates for Distributed Stochastic Optimization Over Random Networks (2018, background): “Regarding the underlying network, references [13], [14] consider static networks, while the works [15]–[17] consider deterministic time-varying networks.”