GIANT: Globally Improved Approximate Newton Method for Distributed Optimization

By Shusen Wang, Farbod Roosta-Khorasani, Peng Xu, Michael W. Mahoney. 2017

148 citations recorded by the source corpus.

For distributed computing environment, we consider the empirical risk minimization problem and propose a distributed and communication-efficient Newton-type optimization method. At every iteration, each worker locally finds an Approximate NewTon (ANT) direction, which is sent to the main driver. The main driver, then, averages all the ANT directions received from workers to form a {\it Globally Improved ANT} (GIANT) direction. GIANT is highly communication efficient and naturally exploits the trade-offs between local computations and global communications in that more local computations result in fewer overall rounds of communications. Theoretically, we show that GIANT enjoys an improved convergence rate as compared with first-order methods and existing distributed Newton-type methods. Further, and in sharp contrast with many existing distributed Newton-type methods, as well as popular first-order methods, a highly advantageous practical feature of GIANT is that it only involves one tuning parameter. We conduct large-scale experiments on a computer cluster and, empirically, demonstrate the superior performance of GIANT.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training, Federated & Distributed Learning

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

In Optimization & Training

In Federated & Distributed Learning

Citations in the corpus

Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “An orthogonal one is to pay more local computation for less communication, e.g., one-shot aggregation [53, 54, 16, 21, 46], primal-dual algorithms [37, 38, 7] and distributed Newton methods [33, 52, 29, 35, 25].”
On the Convergence of FedAvg on Non-IID Data (2019, methodology): “2 [25] Shusen Wang, Farbod Roosta Khorasani, Peng Xu, and Michael W.”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, methodology): “…have been proposed in order to achieve better accuracy than the one-round approach while maintaining lower communication costs; examples include DANE (Shamir et al., 2014), Disco (Zhang and Lin, 2015), distributed SVRG (Lee et al., 2015) and their variants (Reddi et al., 2016, Wang et al., 2017).”
Federated Learning: Challenges, Methods, and Future Directions (2019, methodology): “work, methods such as FedAvg have been shown to diverge in practice [65, 75]. Parallel SGD and related variants, which make local updates similar to FedAvg, have been 9 analyzed in the I.I.D. setting [68, 93, 104, 108, 120, 121, 122, 125, 136, 140]. However, the results rely on the premise that each”
Communication-Efficient Edge AI: Algorithms and Systems (2020, methodology): “ned conjugate gradient method. It reduces the communication rounds compared with “DANE”, while the computation cost at the master machine grows roughly cubically with the model dimension. Wang et al. [53] proposed an improved approximate Newton method “GIANT” to further reduce the communication roun”
A Distributed Second-Order Algorithm You Can Trust (2018, methodology): “This includes L1-regularized objectives such as Lasso and sparse logistic regression as very important application cases, which were not covered by earlier methods such as (Shamir et al., 2014; Zhang & Lin, 2015; Wang et al., 2017; Lee & Chang, 2017).”
ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning (2020, background): “There have also been multiple theoretical studies showing better convergence rate of second order based meth-ods [2, 3, 5, 10, 12, 13, 42, 52–54, 56, 60].”
An Efficient Framework for Clustered Federated Learning (2020, methodology): “With the cluster identity estimations, the center machine runs any federated learning algorithm separately within each cluster, such as gradientbased methods [1], the Federated Averaging (FedAvg) algorithm [3], or second-order methods [42], [43].”
Federated Learning via Over-the-Air Computation (2018, background): “2) Large communication loads across mobile devices limit the scalability for federated learning to efficiently exchange locally computed updates at each device [12], [18].”
Communication-Efficient Local Decentralized SGD Methods (2019, methodology): “3 [30] Shusen Wang, Farbod Roosta Khorasani, Peng Xu, and Michael W.”
DINGO: Distributed Newton-Type Method for Gradient-Norm Optimization (2019, background): “However, the theoretical analysis of both GIANT and DiSCO is limited to the case where each f i is strongly convex, and for GIANT they are also of the special form where in (2) we have (cid:96) j ( w ; x j ) = ψ j ( (cid:104) w , x j (cid:105) ) + γ (cid:107) w (cid:107) 2 , γ > 0 is a regularizatio”
A Sharper Generalization Bound for Divide-and-Conquer Ridge Regression (2019, methodology): “In recent years, many communication-efﬁcient methods, e.g., (Mahajan et al. 2013; Zhang, Duchi, and Wainwright 2013; Shamir, Srebro, and Zhang 2014; Smith et al. 2016; Wang et al. 2018), have been proposed to make distributed computing more efﬁcient.”
Do Subsampled Newton Methods Work for High-Dimensional Data? (2019, methodology): “We analyze GIANT and improve the convergence analysis of (Wang et al. 2018).”