A Functional Approximation Based Distributed Learning Algorithm

By Dhruv Kumar Mahajan, Nikunj Agrawal, S. Sathiya Keerthi, S. Sundararajan, L. Eon Bottou. 2013

18 citations recorded by the source corpus.

Scalable machine learning over big data stored on a cluster of commodity machines with significant communication costs has become important in recent years. In this paper we give a novel approach to the distributed training of linear classifiers (involving smooth losses and L2 regularization) that is designed to reduce communication costs. At each iteration, the nodes minimize approximate objective functions; then the resulting minimizers are combined to form a descent direction to move. Our approach gives a lot of freedom in the formation of the approximate objective function as well as in the choice of methods to solve them. The method is shown to have O(log(1/ǫ)) time convergence. The method can be viewed as an iterative parameter mixing method. A special instantiation yields a parallel stochastic gradient descent method with strong convergence. When communication times between nodes are large, our method is much faster than the SQM method [7], which computes function and gradient values in a distributed fashion.

Subfields: Artificial Intelligence, Computational Mechanics

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

Citations in the corpus

SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, background): “Mahajan et al. (2018a) propose an approach to distributed learning of linear classifiers (i.e., convex problems) where, in parallel, workers minimize locally formed approximate loss functions, and then the resulting minimizers are averaged to determine a descent direction.”
On the Convergence of FedAvg on Non-IID Data (2019, methodology): “If the data are iid, distributed optimization can be efficiently solved by the second-order algorithms (Mahajan et al., 2018; Reddi et al., 2016; Shamir et al., 2014; Shusen Wang et al., 2018; Zhang and Lin, 2015) and the one-shot methods (Lee et al.”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “GIANT also bears a resemblance to FADL [16], but we show better convergence bounds.”
Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss (2015, background): “Next we discuss the theoretical implications for logistic regression and the smoothed hinge loss constructed in Section 2.”
Communication-Efficient Local Decentralized SGD Methods (2019, methodology): “3 [23] Dhruv Mahajan, Nikunj Agrawal, S Sathiya Keerthi, Sundararajan Sellamanickam, and Léon Bottou.”
Think Locally, Act Globally: Federated Learning with Local and Global Representations (2020, background): “Recent work has improved the communication efﬁciency of distributed learning by sparsifying the data and model [76], developing efﬁcient gradient-based methods [77, 21], and compressing the updates [75, 83, 49, 52, 46].”
Gaia: Geo-Distributed Machine Learning Approaching LAN Speeds (2017, background): “They show that a geodistributed ML system can perform significantly better by leveraging a communication-efficient algorithm [49] for logistic regression models.”
An efficient distributed learning algorithm based on effective local functional approximations (2013, methodology): “This contribution is covered in detail in Mahajan et al. (2013b); we give a summarized view in Subsection 3.5.”
A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization (2016, methodology): “…2012; Li et al., 2014); the other is to adapt traditional single-machine optimization methods to handle data parallelism (Boyd et al., 2011; Yang, 2013; Mahajan et al., 2013; Shamir et al., 2014; Jaggi et al., 2014; Mahajan et al., 2014; Ma et al., 2015a; Takáč et al., 2015; Zhang and Lin, 2015).”