Parallel and distributed computation

By Dimitri P. Bertsekas, John N. Tsitsiklis. 1989

How researchers see this paper

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

In ML Systems & Hardware

Citations in the corpus

Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, methodology): “Finally, as is standard in the literature, we make an assumption on the maximum delay that asynchrony can cause – this is the partially asynchronous setting as defined in Bertsekas and Tsitsiklis (1989):”
Optimization Methods for Large-Scale Machine Learning (2016, background): “ However, convergence of the method can be proved, and improves when one can bound the degree of staleness of each update. For further information and insight into these ideas, we refer the reader to [16,98]. 8 Methods for Regularized Models Our discussion of structural risk minimization (see x2.3) ”
Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, background): “Recalling our population risk (3), basic distributed learning procedures (without privacy) iterate as follows [13, 24, 17]:”
Deep learning with Elastic Averaging SGD (2014, methodology): “We however emphasize that to the best of our knowledge the problem of stochastic optimization in the parallel deep learning setting under the communication constraints was never addressed in the literature before (and thus as well a more general problem when the data is distributed).”
Optimal Distributed Online Prediction Using Mini-Batches (2010, background): “In an asynchronous distributed computing environment (see, e.g., Tsitsiklis et al., 1986; Bertsekas and Tsitsiklis, 1989), this can be quite wasteful.”
Distributed delayed stochastic optimization (2011, methodology): “Certainly distributed optimization has been studied for several decades, tracing back at least to seminal work of Tsitsiklis and colleagues ([Tsi84, BT89]) on minimization of smooth functions where the parameter vector is distributed.”
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– 8].”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, neutral): “Note that convergence analysis of asynchronous algorithms tends to be more challenging since their dynamics are much richer [20], and asynchronous optimization algorithms often converge under more restrictive conditions than their synchronous counterparts.”
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants (2015, neutral): “, [3, 14]).”
Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication (2018, background): “While early work dates back to 1980’s (Tsitsiklis et al., 1986; Bertsekas & Tsitsiklis, 1989), consensus based gradient descent and dual averaging methods with sublinear convergence have made their debut (Nedic & Ozdaglar, 2009; Duchi et al., 2012), which consist of two steps: all nodes (i) gather…”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, background): “First, many of these algorithms are based on first-order subgradient methods [1], [12], [9], which for general convex problems have slow convergence rates (given by O(1/ √ k) where k is the iteration number),1 making them impractical in many large scale applications.”
Asynchronous distributed optimization using a randomized alternating direction method of multipliers (2013, methodology): “The first one is based on the simultaneous use of a local first-order optimization algorithm (subgradient algorithm [2], [3], [4], Nesterov-like method [5], [6]) and a gossip process which drives the”
Distributed subgradient methods and quantization effects (2008, methodology): “Our proposed method builds on the work in [24], [25] (see also, [3]).”
Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss (2015, methodology): “More specifically, we modify the definition of fi(w) as fi(w) def = 1 n n∑ j=1 φ(w, zi,j) + λ 2 ‖w‖22, i = 1, . . . ,m. (3) For example, when φ is the hinge loss, this formulation yields the support-vector machine [12].”
Distributed Ridge Regression with Feature Partitioning (2018, methodology): “Finally, the Lagrange multipliers in V are updated through gradient-ascent [27].”
Flexible Decomposition Algorithms for Weakly Coupled Markov Decision Problems (1998, background): “While some progress has been made on understanding some very special cases where MDPs may be decomposed into independent subproblems (Singh, 1992; Lin, 1997), much of the effort has focused on methods that decompose MDPs into “communicating” subproblems ( Bertsekas & Tsitsiklis, 1989; Dean & Lin, 1”