FedDANE: A Federated Newton-Type Method

By Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, Virginia Smith. 2019

175 citations recorded by the source corpus.

Federated learning aims to jointly learn statistical models over massively distributed remote devices. In this work, we propose FedDANE, an optimization method that we adapt from DANE [8], [9], a method for classical distributed optimization, to handle the practical constraints of federated learning. We provide convergence guarantees for this method when learning over both convex and non-convex functions. Despite encouraging theoretical results, we find that the method has underwhelming performance empirically. In particular, through empirical simulations on both synthetic and real-world datasets, FedDANE consistently underperforms baselines of FedAvg [7] and FedProx [4] in realistic federated settings. We identify low device participation and statistical device heterogeneity as two underlying causes of this underwhelming performance, and conclude by suggesting several directions of future work.

Subfields: Artificial Intelligence, Computer Science Applications, 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 Computer Science Applications

In Optimization & Training

In Federated & Distributed Learning

Citations in the corpus

Federated Optimization in Heterogeneous Networks (2018, background): “We refer interested readers to Li et al. (2020) for more detailed discussions.”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, methodology): “It works with any local solver and server optimizer and is therefore complementary to existing approaches such as [38, 39, 20, 40].”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “A second common assumption is to assume that the (stochastic) gradients are uniformly bounded (e.g. Koloskova et al., 2019; Li et al., 2020b), that is for a constant G .”
Adaptive Personalized Federated Learning (2020, background): “Due to inherent diversity among local data shards and highly non-IID distribution of the data across clients, FedAvg is hugely sensitive to its hyperparameters, and as a result, does not beneﬁt from a favorable convergence guarantee (Haddadpour and Mahdavi, 2019; Li et al., 2020).”
Federated Learning With Quantized Global Model Updates (2020, background): “…convergence guarantees for FL under various scenarios, considering iid data across the devices [11, 24–27], non-iid data [27, 14, 28, 29], participation of all the devices [30–33], or only a subset of devices at each iteration [34–36, 29, 37], and FL under limited communication constraints [37–40].”
Exploiting Shared Representations for Personalized Federated Learning (2021, methodology): “For FEMNIST, we restrict the dataset to 10 handwritten letters and assign samples to clients according to a log-normal distribution as in (Li et al., 2019).”
FedBE: Making Bayesian Model Ensemble Applicable to Federated Learning (2020, background): “F ED P ROX (Li et al., 2020a; Sahu et al., 2018), F ED DANE (Li et al., 2019), Yao et al. (2019), and SCAFFOLD (Karimireddy et al., 2020) designed better local training strategies to prevent clients’ model drifts.”
FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data (2020, methodology): “FedDANE [22] also proposes a way of designing the subproblem by using the global gradient, but this violates the CTA protocol.”
Decentralized Federated Averaging (2021, background): “In the paper [12], the authors propose a Newton-type scheme for federated learning.”
Multi-center federated learning: clients clustering for better personalization (2020, methodology): “[14].”
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning (2019, methodology): “DANE by (Shamir et al., 2014) obtain a closely related primal only algorithm, which was later accelerated by Reddi et al. (2016b) and recently extended to federated learning (Li et al., 2020).”
Federated Learning Based on Dynamic Regularization (2021, background): “However, FedDANE performs worse than FedAvg empirically with partial participation (Li et al., 2019).”