A distributed block coordinate descent method for training $l_1$ regularized linear classifiers

By Dhruv Kumar Mahajan, S. Sathiya Keerthi, S. Sundararajan. 2014

36 citations recorded by the source corpus.

Distributed training of $l_1$ regularized classifiers has received great attention recently. Most existing methods approach this problem by taking steps obtained from approximating the objective by a quadratic approximation that is decoupled at the individual variable level. These methods are designed for multicore and MPI platforms where communication costs are low. They are inefficient on systems such as Hadoop running on a cluster of commodity machines where communication costs are substantial. In this paper we design a distributed algorithm for $l_1$ regularization that is much better suited for such systems than existing algorithms. A careful cost analysis is used to support these points and motivate our method. The main idea of our algorithm is to do block optimization of many variables on the actual objective function within each computing node; this increases the computational cost per step that is matched with the communication cost, and decreases the number of outer iterations, thus yielding a faster overall method. Distributed Gauss-Seidel and Gauss-Southwell greedy schemes are used for choosing variables to update in each step. We establish global convergence theory for our algorithm, including Q-linear rate of convergence. Experiments on two benchmark problems show our method to be much faster than existing methods.

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

CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, background): “If hypothetically each of our quadratic subproblems Gσ k (∆α[k]) as defined in (10) were to be minimized exactly, the resulting steps could be interpreted as block-wise Newton-type steps on each coordinate block k, where the Newton-subproblem is modified to also contain the L1-regularizer (Mahajan e”
A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization (2016, methodology): “(Mahajan et al., 2017) considered each machine to handle a block of coordinates and proposed distributed block coordinate descent methods for solving `1 regularized loss minimization problems.”
FedBCD: A Communication-Efficient Collaborative Learning Framework for Distributed Features (2022, methodology): “Compared with the existing distributed (stochastic) coordinate descent methods [12], [13], [14], [15], we show for the first time that when the number of local updates, mini-batch size and learning rates are selected appropriately, the FedBCD converges to a O(1/√T ) accuracy with O(√T ) rounds of co”
Stochastic Dual Coordinate Ascent with Adaptive Probabilities (2015, unknown): “, 2014) and (Mahajan et al., 2014).”
L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework (2015, methodology): “Inspired by GLMNET and [34], the work of [3, 18] introduced the idea of a block-diagonal Hessian upper approximation in the distributed L1 context.”