PaperlayerView exact revision on arXiv

Source-linked AI summary

SPADE-DFL: Communication-Efficient Decentralized Federated Learning via Derivative-Free Linearized ADMM

Mengli Wei, Mengkai Zhu, Jiawen Chen, Wenwu Yu, Duxin Che

arXiv:2609.29446v1cs.LGcs.NI

TL;DR

Derivative-free decentralized learning must balance fewer neighbor exchanges against disagreement accumulated during local updates. SPADE-DFL uses a primal–dual local-training method and protects one accumulated data-dependent update per client and round. Its prescribed nonprivate schedule preserves an O(T^-1/3) stationarity and consensus order with Θ(T^2/3) communication rounds.

  • Problem

    The paper asks how local function-value evaluations can replace neighbor communication while preserving convergence order despite the drift of local models between exchanges.

    Source: §I · p. 1

  • Method

    SPADE-DFL combines a memory-based single-point estimator with local-training ADMM, separating the accumulated data-dependent update from the graph correction for a once-per-round privacy release.

    Source: §I · pp. 1–2

  • Results

    τ = Θ(T^1/3) local updates per exchange yield an O(T^-1/3) stationarity and consensus order using Θ(T^2/3) communication rounds under the prescribed nonprivate schedule.

    Source: §VI · p. 11

  • Takeaways & Limitations

    The schedule lets local training grow with the computation budget while preserving the nonprivate stationarity and consensus convergence order.

    Source: §VI · p. 11

Abstract

from arXiv · show

Reducing communication in derivative-free decentralized learning requires controlling the disagreement accumulated over multiple local updates. This paper develops SPADE-DFL, a primal--dual method that allows the number of local function-value updates between neighbor exchanges to grow with the computation budget while preserving the nonprivate convergence order. For smooth nonconvex objectives under uniform query-moment bounds, the prescribed nonprivate schedule achieves a time-averaged stationarity and consensus bound of $\mathcal{O}(T^{-1/3})$ using only $\Theta(T^{2/3})$ communication rounds, where $T$ is the number of local updates per client. For private training, the accumulated data-dependent increment is isolated from the graph correction, allowing one protected state per client and round to generate all outgoing messages. We prove client-level differential privacy for the full interactive transcript and quantify the resulting optimization error over a finite horizon. Experiments on four classification tasks show that SPADE-DFL achieves higher mean test accuracy than existing decentralized learning methods.

I. INTRODUCTION

SPADE-DFL addresses how local function-value computation can replace neighbor exchanges while controlling model drift and preserving convergence order. It combines a memory-based single-point direction with a local-training ADMM scheme and a privacy mechanism that protects the accumulated update while retaining the graph correction.

I. INTRODUCTION

  • The introduction asks how much communication local loss evaluations can replace while preserving collective-learning convergence order despite local-model drift.It notes that training length, stepsize, smoothing radius, and network gain must be selected jointly.Source: §I · p. 1
  • τ = Θ(T^1/3) local updates per exchange retain an O(T^-1/3) stationarity and consensus order under the prescribed nonprivate schedule.The schedule is stated for smooth nonconvex objectives under uniform query-moment bounds.Source: §I · p. 2

A. Communication in Decentralized Learning

  • Prior communication work spans local training, synchronization and mixing protocols, topology correction, compression, and error-feedback methods.The discussion contrasts reducing exchange frequency with reducing the information sent in each exchange.Source: A. Communication in Decentralized… · p. 2

B. Learning from Function Values

  • Function-value methods supply directional information without gradients, while prior work applies them to distributed estimation, local training, and ADMM-based solvers.The paper positions estimator choice alongside the work performed by the local solver.Source: B. Learning from Function Values · p. 2

C. Privacy across Distributed Interactions

  • SPADE-DFL isolates the accumulated data-dependent update from the graph correction, clips and perturbs that update once per round, and establishes client-level privacy for the full interactive transcript.The stated privacy setting replaces an entire fixed-size local dataset.Source: §I · p. 2, C. Privacy across Distributed… · p. 3

A. Problem Formulation

  • The problem formulation distributes empirical risks across clients and uses neighbor-edge constraints to recover a common model when the graph is connected.Clients have component-loss values but no access to component or local gradients; the stated graph is fixed, undirected, unweighted, connected, and synchronously communicating.Source: A. Problem Formulation · p. 3

B. Single-Point Estimation and Memory Properties

The section develops a one-point function-value estimator and a component-memory correction for local training. Under query-moment assumptions, the correction preserves the conditional mean of fresh estimates while keeping its second moment controlled.

B. Single-Point Estimation and Memory Properties

  • Each query returns one noisy component-loss value at a perturbed model point, from which the method forms a derivative-free direction.The perturbation uses smoothing radius µ, direction u, and query noise ζ.Source: B. Single-Point Estimation and Memory… · p. 4
  • Under Assumption 3, the query has conditional mean µ∇f_i,h(x) plus a remainder bounded by c_rµ^2, and its second moment is controlled.The assumption bounds query-direction moments and centers the query noise; bounded smooth losses with bounded conditional noise variance are given as a sufficient example.Source: B. Single-Point Estimation and Memory… · p. 4
  • The component-memory correction preserves the conditional mean of fresh single-point estimates and admits a controlled second moment.At the start of a round, the memory is initialized with one function query per component, then sampled entries are replaced during local updates.Source: B. Single-Point Estimation and Memory… · p. 4

C. SPADE-DFL

SPADE-DFL reduces neighbor-exchange frequency by performing multiple derivative-free local updates while holding the ADMM correction fixed. Each completed local stage yields a released state used to construct neighbor messages and auxiliary updates.

C. SPADE-DFL

  • After the local stage, the accumulated data-dependent update is clipped and perturbed once, and outgoing messages and auxiliary-variable updates use the released state.Initialization, graph, and parameter schedules are public and data-independent; fresh local randomization is independent across clients.Source: Figure 1 · p. 5, C. SPADE-DFL · p. 5
  • Clients perform τ_i local updates between neighbor exchanges, amortizing communication over multiple function-value updates.Each directed edge carries one d-dimensional ADMM message per round.Source: C. SPADE-DFL · p. 5, Figure 1 · p. 5
  • During a local stage, SPADE-DFL freezes the ADMM correction while clients perform multiple single-query updates.The round uses a stepsize η_k and smoothing radius µ_k; ρ and β determine the ADMM correction.Source: C. SPADE-DFL · p. 5, Figure 1 · p. 5

1) Local Derivative-Free Training:

SPADE-DFL holds the neighbor-dependent ADMM correction fixed during local updates, then releases a sanitized accumulated increment for neighbor exchange. The section establishes client-level privacy for the full interactive transcript.

1) Local Derivative-Free Training:

  • The neighbor-dependent ADMM correction stays fixed across τ_i local updates; α_k is the effective descent stepsize and α_kβ its correction coefficient.For synchronized settings, a = ταβ is the aggregate network gain over one communication round.Source: 1) Local Derivative-Free Training · p. 5

2) Private Release and Decentralized Communication:

  • Before exchange, SPADE-DFL clips and adds Gaussian noise to the accumulated data-dependent increment once, leaving the explicit ADMM correction unchanged.Outgoing messages are constructed from the resulting released state.Source: 2) Private Release and Decentralized… · p. 5
  • Each client completes τ_i local updates before exchange, and each directed edge carries one d-dimensional ADMM message per round from the released state.Source: 2) Private Release and Decentralized… · p. 5

A. Exact Message Recursion and Transcript Privacy

  • Oriented-edge message differences define ω_e,k, while λ_k = −Bω_k−1 expresses neighbor exchanges as a graph-correction recursion.Source: A. Exact Message Recursion and… · p. 6
  • Given released-state history, directed messages and auxiliary states are deterministic, and the full interactive transcript is client-level (ε_i, δ_i)-DP.The transcript includes released states and exchanged messages through round K − 1, as well as public initialization and schedules.Source: A. Exact Message Recursion and… · p. 6

B. Network Stability and Disagreement

The analysis studies synchronized network dynamics, characterizes stability of homogeneous disagreement modes, and relates released-state disagreement to local iterates between exchanges.

B. Network Stability and Disagreement

C. Finite-Horizon Stationarity and Consensus

Under the stated assumptions, the analysis bounds time-averaged stationarity and consensus. A prescribed nonprivate schedule preserves the convergence order while reducing communication rounds.

C. Finite-Horizon Stationarity and Consensus

D. Communication and Query Complexity

SPADE-DFL combines longer local training stages with single-point updates to reduce communication while preserving the nonprivate stationarity–consensus rate. Experiments report higher mean test accuracy across the evaluated dataset–partition combinations and examine sensitivity to client count and privacy budget.

D. Communication and Query Complexity

  • Under the non-private schedule of Corollary 1, choosing τ = Θ(T 1/3) preserves the O(T −1/3) stationarity–consensus rate.Source: D. Communication and Query Complexity · p. 7
  • Each directed edge carries one d-dimensional vector per round, while the memory table uses O(m_i d) storage beyond model and edge states.Each client uses m_i + τb_i function queries per round, including memory initialization.Source: D. Communication and Query Complexity · p. 7
  • At fixed T, increasing τ reduces the number of releases K = T/τ and the noise variance required per release under a fixed total zCDP budget.The analysis relates these communication savings to local-drift and release-error terms in the stationarity–consensus bound.Source: D. Communication and Query Complexity · p. 7
  • Privacy composes over each client’s K releases under replacement of that client’s dataset, and adaptive composition covers the full interactive transcript.The communication count includes all 2|E|K directed messages.Source: D. Communication and Query Complexity · p. 8

A. Datasets and Models

  • Evaluation spans MNIST, Fashion-MNIST, Alzheimer’s disease, and Brain Tumor MRI across IID, two Dirichlet, and pathological client-data partitions.The comparison uses the same partition and random seed across methods within each comparison.Source: A. Datasets and Models · p. 8

B. Comparative Evaluation under Heterogeneous Client Data

  • SPADE-DFL achieved the highest mean test accuracy in all 16 dataset–partition combinations, with gains of 0.86–4.83 percentage points over the best competing method.The reported accuracies cover MNIST, Fashion-MNIST, Alzheimer’s disease, and Brain Tumor MRI.Source: B. Comparative Evaluation under… · p. 8

C. Sensitivity to Client Count and Privacy Budget

  • At ε = 32, accuracy ranged from 99.03–99.21% on MNIST and 65.00–70.96% on Brain Tumor MRI as client count varied from 30 to 100.Brain Tumor MRI showed the largest variation and reached its highest mean accuracy at N = 100.Source: C. Sensitivity to Client Count and… · p. 10
  • As ε increased from 4 to 32 at N = 100, mean validation accuracy rose from 43.29% to 70.96% on Brain Tumor MRI, the largest gain among the four datasets.MNIST accuracy changed little beyond ε = 16, while Fashion-MNIST varied by approximately one percentage point over the tested range.Source: C. Sensitivity to Client Count and… · p. 10

D. Client Heterogeneity and Roundwise Comparisons

Across the client partitions, mean accuracy curves remain closely aligned even as non-IID partitions show greater variation in client-level digit-7 proportions. The communication schedule sharply reduces transmitted scalars at the reported budget, with a larger stationarity–consensus residual than exchanging after every update.

D. Client Heterogeneity and Roundwise Comparisons

E. Communication–Optimization Trade-off

VI. CONCLUSION

  • The conclusion gives an O(T^-1/3) stationarity and consensus bound with Θ(T^2/3) communication rounds, and establishes client-level privacy for the full interactive transcript.Source: §VI · p. 11

APPENDIX A ORACLE AND MEMORY BOUNDS

The appendix analyzes the one-point estimator and its component-memory correction. It uses smoothness and query-moment assumptions to establish estimator properties and bounds on stored entries.

  • The Taylor expansion and query-moment conditions eliminate constant and noise terms in expectation, leaving the linear term µ∇fi,h(x) plus a remainder.Source: Appendix A · p. 11
  • Conditioning on Fk,t fixes the memory table, and uniform sampling makes the sampled-memory mean cancel the stored-average term in the expectation argument.Source: Appendix A · p. 11
  • Each initialized memory entry has second moment at most Q^2, and the bound is maintained as entries are refreshed.Source: Appendix A · p. 11

APPENDIX B MESSAGE RECURSION AND TRANSCRIPT PRIVACY

The appendix derives message identities and uses them to obtain a recursion for the decentralized updates. It also establishes client-level differential privacy for the complete interactive transcript through post-processing and adaptive composition.

  • Differences and sums of oriented-edge messages, substituted into the primal update, yield the message recursion and shifted dual identities.Source: Appendix B · pp. 11–12
  • All outgoing messages are deterministic post-processing of the released state and history, so adaptive composition establishes client-level privacy for the full transcript under whole-dataset adjacency.Source: Appendix B · p. 12

APPENDIX C SCHUR STABILITY AND DISAGREEMENT BOUNDS

The appendix characterizes when the homogeneous disagreement modes are Schur stable and develops bounds for the disagreement criterion. The proof also identifies a unique positive-definite solution to (16) and uses the common initialization to set V0 to zero.

  • 0 < aρλ < 8/3 is the Jury stability condition, required for every nonzero graph Laplacian eigenvalue.Source: Appendix C · p. 12
  • Equation (16) has a unique positive-definite solution in the stability analysis.Source: Appendix C · p. 12
  • The disagreement proof uses a nonexpansive projection and independent zero-mean release noise; common initialization gives V0 = 0.Source: Appendix C · p. 12

APPENDIX D DESCENT AND CONVERGENCE BOUNDS

The appendix derives descent and convergence bounds, then applies a prescribed schedule to obtain the stated local-update range and communication count. Its proof uses cancellation and fixed Lyapunov constants to establish the intermediate bounds.

APPENDIX D DESCENT AND CONVERGENCE BOUNDS

  • In the proof of Lemma 4, fη2Q2 cancels the last term in (53), and bounding the remaining gradient coefficients by −α/8 proves (21).Source: Appendix D · p. 13
  • Fixed a = τβ_α, ρ, and graph, the common initialization gives V_0 = 0 and Γ is bounded uniformly over τ, fixing the Lyapunov constants.These facts support the theorem's convergence-bound derivation.Source: Appendix D · p. 13
  • The inequality 1/(τα) ≤ 1 + 1/(τα^2) for α > 0 and τ ≥ 1 establishes (22) by substitution.Source: Appendix D · p. 13
  • The schedule (23) fixes a = τβ_T and τη_T μ_T = a_0, with T = Kτ.Source: Appendix D · p. 13
  • The schedule yields the stated local-update range and communication count from τ^2/T = O(T^-1/3) and K = T/τ.The release terms vanish in this step.Source: Appendix D · p. 13
Loading 2609.29446v1…