Estimation, Optimization, and Parallelism when Data is Sparse

By John C. Duchi, Michael I. Jordan, H. Brendan McMahan. 2013

105 citations recorded by the source corpus.

Subfields: Optimization & Training, ML Systems & Hardware

How researchers see this paper

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

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Federated Learning: Challenges, Methods, and Future Directions (2019, background): “usceptible to stragglers in the face of device variability. Asynchronous schemes are an attractive approach to mitigate stragglers in heterogeneous environments, particularly in shared-memory systems [27, 30, 48, 92, 141]. However, they typically rely on bounded-delay assumptions to control the degr”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, background): “Several variants of SGD have been proposed for parallel computing, many of which build on the idea of asynchronous communication (Niu et al., 2011; Duchi et al., 2013).”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, background): “For an overview over this currently active research field, we refer the reader to (Balcan et al., 2012; Richtárik & Takáč, 2013; Duchi et al., 2013; Yang, 2013; Liu & Wright, 2014; Fercoq et al., 2014; Jaggi et al., 2014; Shamir & Srebro, 2014; Shamir et al., 2014; Zhang & Lin, 2015; Qu & Richtárik,”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, background): “A large body of recent work has demonstrated that near-linear speedups are achievable, in theory and practice, on many common machine learning tasks [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 13, 16].”
Distributed optimization with arbitrary local solvers (2015, background): “Several distributed variants of SGD have been proposed, many of which build on the idea of a parameter server [18, 43, 50].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Several distributed variants of SGD have been proposed, many of which build on the idea of a parameter server [133, 149, 53].”
Cyclades: Conflict-free Asynchronous Machine Learning (2016, background): “Additional work in first order optimization and beyond [8, 21, 5], has further demonstrated that linear speedups are generically possible in the asynchronous shared-memory setting.”
Revisiting Distributed Synchronous SGD (2016, background): “Understanding the theoretical impact of staleness is difﬁcult work and the topic of many recent papers, e.g. Recht et al. (2011); Duchi et al. (2013); Leblond et al. (2016); Reddi et al. (2015); k to parameter servers. end Algorithm 2: Async-SGD Parameter Server j Input: γ 0 , γ 1 , . . . learning…”
Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning (2014, background): “Since we will need non-increasing learning rates, it will be useful to define G̃bck1:t ≡ maxs≤tGbck1:s and G̃fwd1:t ≡ maxs≤tGfwd1:s .”
Neural Taylor Approximations: Convergence and Exploration in Rectifier Networks (2016, background): “RMS-Normalization encourages Exploration Adaptive optimizers based on root-mean-square normalization exhibit an up-to-exponential improvement over nonadaptive methods when gradients are sparse (Duchi et al., 2013) or low-rank (Krummenacher et al.”
Scaling Up Stochastic Dual Coordinate Ascent (2015, methodology): “In [7, 13, 12], the sparsity has been utilized to develop asynchronous parallel coordinate descent and stochastic gradient type algorithms.”
LOCO: Distributing Ridge Regression with Random Projections (2014, methodology): “For the random projection we used the DCT implemented in FFTW 4 .”
DUAL-LOCO: Distributing Statistical Estimation Using Random Projections (2015, background): “Recently, several asynchronous stochastic gradient descent (SGD) methods [3, 4] have been proposed for solving problems of the form (1) in a parallel fashion in a multi-core, shared-memory environment and have been extended to the distributed setting.”
Asynchronous Decentralized Online Learning (2021, background): “However, compared to the well-studied centralized online [9, 18] and decentralized stochastic [17, 12, 3, 23] settings, how to do asynchronous learning in the decentralized online setting remains largely unexplored.”
Proposal Scaling Distributed Machine Learning with System and Algorithm Co-design (2016, unknown): “There are some other interesting works studying specific scenarios, for example, [50], which focuses on the sparse data.”
Asynchronous stochastic convex optimization: the noise is in the noise and SGD don't care (2015, methodology): “For our first set of experiments, we study the effect that data sparsity has on the convergence behavior of asynchronous methods—sparsity has been an essential part of the analysis of many asynchronous and parallel optimization schemes [15, 4, 18], while our theoretical results suggest it should be ”