PaperlayerView exact revision on arXiv

Source-linked AI summary

FedDANE: A Federated Newton-Type Method

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

arXiv:2001.01920v1cs.LGstat.ML

TL;DR

Federated learning must optimize models across devices with heterogeneous data and limited participation. This paper adapts inexact DANE into FedDANE, providing convex and non-convex convergence guarantees, but finds that FedDANE underperforms FedAvg and FedProx empirically. The study attributes this result to inexact gradient estimation and statistical heterogeneity, while identifying practical limitations and future research directions.

  • Problem

    FedDANE addresses federated optimization under low device participation and statistically heterogeneous data, settings in which DANE had not been analyzed.

  • Method

    FedDANE adapts inexact DANE by collecting gradient updates from subsets of devices and approximately solving Newton-type local subproblems.

  • Results

    FedDANE provides convergence guarantees for convex and non-convex functions but consistently underperforms FedAvg and FedProx in empirical federated settings.

  • Takeaways & Limitations

    The study highlights drawbacks of FedDANE's gradient correction term and reports that FedProx achieves improved federated optimization performance using only a proximal term.

  • Takeaways & Limitations

    FedDANE requires two communication rounds per update, making it less efficient than FedAvg and FedProx.

Abstract

from arXiv · show

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, 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 and FedProx 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.

I. INTRODUCTION

Federated learning trains models across heterogeneous remote devices while keeping data localized, but low participation and statistical heterogeneity challenge existing methods. FedDANE adapts inexact DANE to this setting, with theoretical guarantees but weaker empirical performance than FedAvg and FedProx.

  • Federated learning trains statistical models across heterogeneous remote devices while keeping data localized, providing computational and privacy benefits.
  • FedAvg uses low device participation and local updates, but can diverge when device data is statistically heterogeneous.FedAvg may involve only 1% of devices per communication round.
  • FedDANE adapts inexact DANE by approximating the global gradient from a subset of devices and solving approximate Newton-type local subproblems.The method is designed for low participation and heterogeneous data settings.
  • FedDANE provides convergence guarantees for convex and non-convex functions under low participation and differing device data distributions.
  • FedDANE consistently underperforms FedAvg and FedProx empirically, with low participation and statistical heterogeneity identified as underlying causes.The method also requires two communication rounds for one update.
  • The paper positions FedDANE within communication-efficient distributed methods that use inexact local updates to trade communication for computation.DANE and inexact DANE are examples of such methods, alongside primal-dual approaches such as COCOA.

B. Preliminaries: FedAvg and DANE

FedAvg uses partial device participation and local SGD, whereas DANE relies on distributed subproblem solving and full-gradient computation. FedDANE adapts DANE to federated settings by approximating full gradients from sampled devices, but requires two communication rounds per outer iteration.

  • FedAvg: FedAvg randomly selects a subset of devices, which perform E epochs of local SGD before synchronously sending updates for aggregation.Each selected device updates the received model on its local function using step-size η.
  • DANE: DANE has workers solve local subproblems, after which the server aggregates their updates to obtain the next model.The update requires workers to collectively compute the overall gradient before aggregation.
  • Federated constraint: Computing DANE’s full gradient is infeasible in massive federated networks because it requires communication with and gradient averaging from all devices.This full-participation requirement is the critical obstacle to directly applying inexact DANE to federated learning.
  • FedDANE: FedDANE approximates the full gradient using gradients from randomly sampled devices, then has another selected device subset solve the subproblem inexactly.The method aggregates sampled gradients before selecting devices for the subsequent subproblem update.
  • FedDANE limitation: Two communication rounds per FedDANE outer iteration make it less efficient than FedAvg and FedProx, motivating a pipelined one-round variant.The proposed pipeline is intended to perform one update in a single communication round.

IV. ANALYSIS

FedDANE's analysis quantifies local-solver inexactness and device dissimilarity, then uses these quantities to study convergence under heterogeneous federated data.

  • Analysis: FedDANE allows selected devices to solve local subproblems inexactly at each updating round to reduce communication.The analysis introduces γ to quantify this inexactness.
  • Analysis: A smaller γ corresponds to higher local-solution accuracy.γ lies in [0, 1).
  • Analysis: B-local dissimilarity quantifies how device gradients differ from the global gradient at a model point.The paper uses the bound B to characterize device heterogeneity in its convergence results.

A. Convex Case

The paper derives expected-decrease and convergence results for FedDANE on convex and non-convex objectives under bounded device dissimilarity and inexact local solutions.

  • Convex Case: For convex local functions with Lipschitz gradients, Theorem 3 gives an expected decrease in the global objective under bounded B-dissimilarity and the γ-inexact criterion.The proof takes expectations over randomly selected devices and applies the bounded dissimilarity assumption.
  • Convex Case: When local problems are solved exactly and B is large, Corollary 4 chooses µ ≈ 5LB^2 and obtains ρ ≈ 3/(25LB^2).This is the stated convex convergence characterization for the high-dissimilarity regime.
  • Non-convex Case: Theorem 6 characterizes FedDANE's convergence rate to approximate stationary solutions in the non-convex case.The theorem assumes the conditions of Theorem 5 hold at each iteration.
  • Non-convex Case: FedDANE's derived convergence rates recover FedProx's results and are asymptotically the same as SGD's.This comparison is stated for the convergence rates derived in the paper.

C. Device-specific Constants

The convergence analysis extends to device-specific smoothness, proximal, and inexactness constants while retaining an expected-decrease guarantee under bounded dissimilarity.

  • Device-specific Constants: The analysis allows L, µ, and γ to vary across devices instead of assuming common constants.This extension covers device-specific smoothness, proximal-penalty, and inexactness parameters.
  • Device-specific Constants: Theorem 7 assumes convex local objectives with device-specific L_k-Lipschitz gradients and bounded B-dissimilarity.The theorem also uses device-specific µ_k and γ_k values.
  • Device-specific Constants: Under the stated parameter conditions, iteration t has an expected decrease in the global objective.The expectation is taken over the distribution of randomly selected devices S_t.
  • Device-specific Constants: The analysis is agnostic to the local solver and covers device sampling with or without replacement.The paper gives the full proof in Appendix V-F.

V. EXPERIMENTS

Experiments evaluate FedDANE on synthetic and real-world federated datasets and find consistently disappointing convergence relative to FedAvg and FedProx. The discussion attributes this gap to practical federated conditions and outlines possible variants for future work.

  • Experimental Setup: The evaluation uses synthetic datasets with varying heterogeneity and three real-world LEAF datasets: FEMNIST, Shakespeare, and Sent140.FEMNIST uses a convex model, while Shakespeare and Sent140 use non-convex deep neural networks.
  • Evaluation Results: With 10 devices selected per round and E = 20 local epochs, FedDANE consistently performs worse than FedAvg and FedProx.The plotted training loss treats two FedDANE communication rounds as one.
  • Discussion: The authors identify statistical heterogeneity and low device participation, which makes full-gradient approximation inaccurate, as factors that may hurt FedDANE convergence.The experiments use only 10 participating devices per updating round.
  • Evaluation Results: Except on Synthetic IID, FedDANE underperforms both baselines as heterogeneity increases, either converging more slowly or diverging.The synthetic datasets are ordered from less to more heterogeneous.
  • Discussion: The empirical underperformance may reflect violations of assumptions about Hessian curvature, local strong convexity, and sufficient decrease.The paper presents these as possible explanations for the discrepancy between theory and practice.
  • Discussion: Possible future variants include decaying the gradient-correction term and pipelining communication, although pipelining would require stale gradients.A decayed variant would eventually reduce to FedProx, while the proposed method currently requires two communication rounds per update.

D. Proof for Theorem 3

The proof derives the theorem by combining gradient regularity, optimality conditions, strong convexity of the local subproblem, and expectations over randomly selected devices.

  • Proof: The proof begins from Lipschitz continuity of the gradients.
  • Proof: Optimality conditions characterize the iterate w_t used in the argument.
  • Proof: The local subproblem P_t(w) is identified as μ-strongly convex.
  • Proof: The derivation combines intermediate inequalities and then takes expectation over the randomly chosen device set S_t.

E. Proof for Theorem 5

This proof follows the same convergence-analysis pattern, using gradient continuity, optimality conditions, strong convexity of the local subproblem, and substituted intermediate bounds.

  • Proof: The proof invokes Lipschitz continuity of the gradients.
  • Proof: Optimality conditions characterize the iterate w_t.
  • Proof: The local subproblem P_t(w) is treated as (μ − λ)-strongly convex.
  • Proof: The argument substitutes bounds from earlier equations and applies the inequality from equation (10) before reaching the final bound.

F. Proof for Theorem 7

The proof applies gradient continuity and optimality conditions to a local subproblem whose strong convexity depends on μ_k − λ, then substitutes bounds involving the selected-device set.

  • Proof: The proof starts with Lipschitz continuity of the gradients and optimality conditions for w_t.
  • Proof: The local subproblem P_t(w) is assumed to be (μ_k − λ)-strongly convex.
  • Proof: The derivation substitutes intermediate inequalities and uses |S_t| = K_t when bounding the selected-device contribution.

G. Additional Experiments

Additional experiments show that FedDANE remains weak under nearly full participation and small local epochs, while low participation further harms it under statistical heterogeneity.

  • Low device participation hurts FedDANE in statistically heterogeneous settings.The experiment varies participation across 1, 5, 10, and 30 of 30 devices per round, with E = 20.
  • FedDANE performs worse than FedAvg and FedProx even in unrealistic settings with nearly full participation and E = 1.These settings favor FedDANE by allowing broad participation and minimal local computation.
  • On highly heterogeneous datasets, FedDANE performs especially poorly compared with FedAvg and FedProx.Even full device participation does not improve FedDANE on the Synthetic (0.5,0.5) dataset.
Loading 2001.01920v1…