Distributed Block Coordinate Descent for Minimizing Partially Separable Functions

By Jakub Marecek, Peter Richtárik, Martin Takác. 2014

64 citations recorded by the source corpus.

A distributed randomized block coordinate descent method for minimizing a convex function of a huge number of variables is proposed. The complexity of the method is analyzed under the assumption that the smooth part of the objective function is partially block separable. The number of iterations required is bounded by a function of the error and the degree of separability, which extends the results in Richtarik and Takac (Parallel Coordinate Descent Methods for Big Data Optimization, Mathematical Programming, DOI:10.1007/s10107-015-0901-6) to a distributed environment. Several approaches to the distribution and synchronization of the computation across a cluster of multi-core computer are described and promising computational results are provided.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, background): “As the size of the mini-batch grows, this can slow them down in terms of overall runtime, and can even lead to divergence in practice (Takáč et al., 2013; Takáč et al., 2015; Richtárik and Takáč, 2016; Marecek et al., 2015).”
Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization (2015, methodology): “The asynchronous parallel optimization recently received many successes and broad attention in machine learning and optimization [Niu et al., 2011, Li et al., 2013, 2014b, Yun et al., 2013, Fercoq and Richtárik, 2013, Zhang and Kwok, 2014, Marecek et al., 2014, Tappenden et al., 2015, Hong, 2014].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “An extended version with description of implementation details is presented in [61].”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, methodology): “…proof is based on techniques developed in recent coordinate descent papers, including (Richt´arik & Tak´aˇc, 2014; 2013b; 2012; Tappenden et al., 2015; Mareˇcek et al., 2014; Fercoq & Richt´arik, 2013; Lu & Xiao, 2013; Fercoq et al., 2014; Qu & Richt´arik, 2014; Qu et al., 2014) (Efﬁcient…”
Communication-Efficient Distributed Dual Coordinate Ascent (2014, background): “As we discuss below (Section 5), our approach is distinguished from recent work on parallel and distributed optimization [2, 3, 4, 5, 6, 7, 8, 9] in that we provide a general framework for improving the communication efficiency of any dual optimization method.”
Distributed optimization with arbitrary local solvers (2015, background): “In general, one would intuitively expect that the optimal choice would be to have Θ such that T A (Θ) = O (1) × c . values In practice, however, the best strategy for any given local solver is to try several for the number of local iterations to estimate the optimal choice.”
Coordinate descent algorithms (2015, methodology): “In the scheme of Marecek, Richtarik, and Takac [32], the variable vector x is partitioned into subvectors, and each processor is assigned the responsibility for updating one of these subvectors.”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “Two classes of methods address this issue – randomized coordinate descent methods [4], [5], [6] , [7], [8], [9], [10], [11], [12], [13] and stochastic gradien t methods [14], [15], [16], [17], [18].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “However, mini-batch versions of both SGD and coordinate descent (CD) [151, 149, 164, 111, 188, 176, 150, 140, 141, 143, 38, 40] suffer from their convergence rate degrading towards the rate of batch gradient descent as the size of the mini-batch is increased.”
A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order (2016, background): “One of core theoretical questions is how much speedup (or benefit) the asynchronous parallelization can bring us.”
Stochastic Dual Coordinate Ascent with Adaptive Probabilities (2015, unknown): “O C ] 27 F”
Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go? (2018, unknown): “…coordinate descent (Liu et al., 2014; Avron et al., 2015; Liu & Wright, 2015; Tappenden et al., 2017; Fercoq & Richtárik, 2015), dual coordinate descent (Tran et al., 2015), block coordinate descent (Wang et al., 2016; Marecek et al., 2015; Wright, 2015), ADMM (Zhang & Kwok, 2014; Hong, 2017), etc.”
A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization with Nonsmooth Regularization (2018, background): “[13], Richtárik and Takáč [18] consider solving (1) in a distributed environment where X is partitioned feature-wise (i.”
Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization? (2015, background): “Existing mehods often require a large amount of communication between computing nodes [17, 7, 9, 18], which is typically several magnitudes slower than reading data from their own memory [10].”
A Stochastic Large-scale Machine Learning Algorithm for Distributed Features and Observations (2018, methodology): “Distributed Block Coordinate Descent [12] is one of the methods working for datasets with distributed features.”
Distributed Mini-Batch SDCA (2015, background): “(4) Let us now just assume that we can find such a vectorv such that (4) holds (we show how to findv in Section 4.3) and we now show how to derive the lowerbound ofE[D(α(t) + t[St])].”
Communication Lower Bounds for Distributed Convex Optimization: Partition Data on Features (2016, background): “Actually, almost all existing partition-on-feature algorithms satisfy this restriction [14, 11, 9, 12, 7].”