Source-linked AI summary
A Unified Framework for Fair and Personalized Decentralized Learning under Communication Constraints
Krishnendu S. Tharakan, Carlo Fischione
TL;DR
The paper asks how fairly decentralized learning can operate under limited communication, where client heterogeneity, performance disparities, and bandwidth constraints must be handled together. It proposes DMFL-SQ, combining graph-based personalization, agnostic fairness, and compressed event-triggered communication. DMFL-SQ retains an O(T^-1/2) expected squared Moreau-envelope stationarity rate, provides PAC-Bayes guarantees, and achieves a favorable accuracy-fairness-communication trade-off while reducing communication.
Problem
Existing decentralized learning approaches do not provide a unified framework combining graph-based personalization, agnostic fairness, and compressed communication under general nonconvex objectives.
Method
DMFL-SQ combines personalized graph-coupled model training, an agnostic mixture fairness objective, and sparsified, quantized, event-triggered decentralized communication.
Results
DMFL-SQ achieves an O(T^-1/2) rate in expected squared Moreau-envelope stationarity and a favorable accuracy-fairness-communication trade-off while reducing communication cost.
Takeaways & Limitations
Personalization, fairness, and communication efficiency can be jointly achieved in decentralized learning under the considered heterogeneous settings.
Abstract
from arXiv · showhide
Decentralized learning systems aim to collaboratively train models across multiple clients without relying on a central coordinator. While decentralization improves scalability, privacy, and robustness, it also exacerbates three fundamental challenges: statistical heterogeneity across clients, fairness in client-level performance, and stringent communication constraints. This raises a natural question: \emph{how fair can decentralized learning be under limited communication?} We address this question by presenting a unified framework for decentralized learning under communication constraints, bringing together graph-based personalization, agnostic fairness, and compressed event-triggered communication. Specifically, we propose a new algorithm DMFL-SQ, a decentralized multi-task learning algorithm that couples personalized model training over a communication graph with an agnostic mixture fairness objective, while reducing communication through sparsification, quantization, and event-triggered synchronization. We establish convergence guarantees for general non-convex objectives and show that DMFL-SQ achieves an $\mathcal{O}(T^{-1/2})$ rate in expected squared Moreau-envelope stationarity despite sparse, quantized, and event-triggered communication. We further derive PAC-Bayes generalization guarantees for the fairness-aware mixture objective. Experiments on CIFAR-10 and the real heterogeneous MUSMET EEG dataset demonstrate that DMFL-SQ substantially reduces communication while maintaining predictive performance and improving fairness across clients. Together, our theoretical and empirical results show that personalization, fairness, and communication efficiency can be jointly achieved in decentralized learning while preserving the dominant convergence rate.
I. INTRODUCTION
The paper addresses the lack of a unified framework combining personalization, client-level fairness, and communication efficiency in decentralized learning. DMFL-SQ integrates these components and provides convergence and generalization guarantees under compressed, event-triggered communication.
- Motivation: Decentralized learning must address heterogeneous client data, unequal client-level performance, and high communication overhead over bandwidth-limited networks.These challenges motivate personalized learning, fairness-aware objectives, and communication compression.
- Research gap: Existing approaches typically study personalization, fairness, and communication efficiency in isolation rather than within one decentralized non-convex framework.Compressed decentralized methods generally target consensus or shared global models, while agnostic fairness methods are usually centralized or server-assisted.
- Proposed framework: DMFL-SQ combines graph-based personalization, agnostic fairness, sparsification, quantization, and event-triggered synchronization for decentralized multi-task learning.Personalized models are softly coupled over a communication graph while communication is reduced through compressed event-triggered updates.
- Theory: O(T^-1/2) expected squared Moreau-envelope stationarity is established for general nonconvex objectives while accounting for optimization, communication, compression, and triggering errors.The analysis explicitly separates neighbor-copy residual, compression residual, and event-triggering error.
- Theory: PAC-Bayes generalization bounds are derived for the fairness-aware mixture objective, covering the statistical cost of controlling worst-client and general client-mixture risks.The framework therefore analyzes both optimization and statistical aspects of fairness-aware decentralized learning.
- Empirical and overall findings: DMFL-SQ achieves a favorable accuracy-fairness-communication trade-off while reducing communication cost and preserving standard stochastic nonconvex convergence behavior.Experiments on heterogeneous settings support the reported trade-off, while the conclusion compares communication cost with existing baselines.
A. Assumptions
DMFL-SQ assumes smooth non-convex local learning, a connected weighted graph, unbiased stochastic directions, and controlled compressed communication. Its implementation uses fairness selection, reconstructed neighbor copies, and event-triggered sparse-quantized updates, while retaining empirical-to-population fairness discrepancies in the analysis.
- Model and stochastic assumptions: The analysis assumes smooth local objectives, conditionally independent loss-selection and gradient mini-batches, and unbiased stochastic gradients with controlled variance.
- Graph assumptions: The communication graph is undirected and connected, with symmetric nonnegative edge weights defining a bounded graph-coupling regularizer.
- Communication assumptions: The compressor satisfies a contraction property that bounds expected reconstruction error relative to the uncompressed vector.
- Fairness implementation: DMFL-SQ selects fairness components from empirical loss estimates using scalar max-consensus, while separately tracking the population fairness-selection gap.
- Fairness limitation: Exact max-consensus aligns clients on the empirical maximizer but does not ensure that it maximizes the population fairness envelope, so the discrepancy remains in the convergence analysis.
- Algorithmic operation: Each client updates its personalized model every iteration, evaluates graph coupling using reconstructed neighbor copies, and communicates sparse-quantized innovations only when a trigger threshold is met.
IV. PAC-BAYES GENERALIZATION FOR DMFL-SQ
The paper studies PAC-Bayes generalization for fairness-aware agnostic mixture risks with client-specific, potentially non-convex losses. The guarantee is formulated for independently sampled heterogeneous client datasets and mixture weights in a probability-simplex subset.
- The paper establishes an algorithm-agnostic PAC-Bayes generalization guarantee for the fairness-aware agnostic mixture objective under possibly non-convex client losses.
- Client datasets are mutually independent, with samples drawn iid from client-specific distributions that may differ across clients.
- The fairness-aware objective uses agnostic mixture risks over mixture weights Λ contained in the probability simplex.
A. PAC-Bayes Generalization Bound
The paper derives PAC-Bayes generalization guarantees for the agnostic fairness mixture objective and analyzes the one-step perturbation caused by stale and compressed neighbor exchange.
- PAC-Bayes bound: Theorem 1 provides PAC-Bayes bounds for population and empirical agnostic mixture risks over client models.The result holds with high probability simultaneously over posteriors Q under bounded client losses.
- Mixture classes: For the full simplex Λ = ∆n, the uniformity cost is ln n, while general compact mixture classes incur a covering-number cost.The general-class term is ln |Nε(Λ, ∥·∥1)|.
- Mixture classes: The full-simplex case corresponds to the agnostic mixture used in the main fairness objective.The supremum over ∆n is attained at a vertex.
- Communication perturbation: Stale, sparse, quantized, and event-triggered neighbor exchange induces a one-step empirical mixture-risk perturbation that decays as O((1 + log T)^{1/2}).The perturbation is linked to the graph-coupling approximation error and average weighted communication residual.
V. CONVERGENCE ANALYSIS
The convergence analysis establishes regularity of the fairness-aware personalized objective, controls fairness-selection error under explicit conditions, and supports a finite-horizon stationarity guarantee.
- Regularity: The fairness envelope Ψ is L-weakly convex, and the full objective is κ-weakly convex with κ = (1 + ρ)L.The result follows because local objectives are L-smooth and the graph regularizer RG is convex.
- Fairness selection: The Moreau-envelope analysis accommodates changes in the active fairness component and explicitly includes the empirical fairness-selection gap εΨ,t.The empirical maximizer selected by clients need not equal a population maximizer.
- Fairness selection: Under sub-Gaussian selection losses, the expected fairness-selection gap is bounded by a term depending on σsel and the selection minibatch size.For losses with range width R, one may take σsel ≤ R/2.
- Schedules: Assumption 7 uses a finite-horizon stepsize γt = γ/T and a trigger schedule ϑt = ϑ0/√(t + 1).The schedules are part of the conditions used for the final stationarity bound.
A. Weak Convexity and Moreau-Envelope Regularity
The fairness envelope and personalized objective retain weak convexity despite the supremum-based fairness formulation, enabling analysis through the Moreau envelope.
- Weak convexity: Each mixture objective Φλ is L-weakly convex when every local objective Fi is L-smooth.This property is inherited by the pointwise supremum defining the fairness envelope.
- Weak convexity: The fairness envelope Ψ is L-weakly convex because it is the pointwise supremum of mixture objectives sharing that constant.The supremum may be nonsmooth while preserving weak convexity.
- Full objective: The full objective L(w) is κ-weakly convex with κ = (1 + ρ)L after adding the convex graph regularizer and fairness penalty.The objective combines local losses, RG, and ρΨ.
- Moreau envelope: For κ-weakly convex objectives and µ ∈ (0, 1/κ), the proximal mapping is single-valued and the Moreau envelope is continuously differentiable.These properties provide the regularized stationarity framework used in the analysis.
B. Technical Lemmas for the Convergence Analysis
The convergence proof decomposes optimization, stochastic-gradient, fairness-selection, and communication effects, then bounds the residual from stale and compressed neighbor models.
- Technical lemmas: Lemmas 4–6 respectively establish Moreau-envelope descent, communication-residual recursion, and an average communication-residual bound.Together they separate optimization, fairness-selection, stochastic-gradient, and communication effects.
- Error decomposition: The local direction used by Algorithm 1 decomposes as ht = Vt + qt + dt.Here the decomposition separates the exact direction, stochastic-gradient noise, and graph-coupling approximation error.
- Communication residual: The graph-coupling approximation error is controlled through stale and compressed neighbor-model copies and depends on graph weights and coupling parameter α.Lemma 5 bounds the error using the average weighted communication residual.
- Communication residual: The residual recursion requires a sufficiently small stepsize satisfying 2χ1KGγ^2 ≤ χ0ω^2.Under the finite-horizon schedule, Lemma 6 supplies the resulting cumulative bound.
C. Convergence Rate
DMFL-SQ achieves an O(T^-1/2) expected squared Moreau-envelope stationarity rate for its nonsmooth, nonconvex personalized objective, while communication effects remain lower order. Experiments evaluate its accuracy, fairness, communication, threshold, topology, and loss behavior on heterogeneous CIFAR-10 and MUSMET settings.
- Convergence guarantee: O(T^-1/2) expected squared Moreau-envelope stationarity is established for the nonsmooth and nonconvex objective.The convergence bound explicitly accounts for stochastic gradients, empirical fairness selection, compression, and event-triggered neighbor-model communication.
- Convergence guarantee: O((1 + log T)/T) communication terms are lower order than the dominant stationarity rate.The theorem’s constants are independent of T.
- Empirical evaluation: DMFL-SQ reaches higher CIFAR-10 accuracy with substantially fewer communicated bits than D-PSGD and DSGT, and better final accuracy than CHOCO-SGD.The comparison uses strongly non-iid CIFAR-10 with 20 clients and α_Dir = 0.1.
- Empirical evaluation: Smaller event-trigger thresholds communicate more frequently and accelerate early convergence, whereas larger thresholds reduce communication and slow initial learning.DMFL-SQ remains stable across threshold choices, with larger thresholds eventually catching up when more rounds are allowed.
- Empirical evaluation: DMFL-SQ achieves faster loss decrease and lower final loss than D-PSGD on non-iid CIFAR-10 while remaining stable under sparse-quantized event-triggered communication.Fairness regularization also keeps CVaR@0.1 slightly below the ρ = 0 variant for most rounds after an initial transient.
- Empirical evaluation: On heterogeneous MUSMET, DMFL-SQ has the highest average, worst-client, bottom-10% accuracy, and Jain’s index, with the lowest client-accuracy standard deviation and reduced communication.The result demonstrates an accuracy-fairness-communication trade-off against dense decentralized and compressed baselines.
VII. CONCLUSION
The paper presents DMFL-SQ as a decentralized multi-task fair learning framework combining personalization, fairness, and compressed event-triggered communication. Theory and experiments support an O(T^-1/2) stationarity rate and a favorable accuracy-fairness-communication trade-off in heterogeneous settings.
- Contributions: DMFL-SQ unifies personalization, fairness, and sparsified, quantized, event-triggered communication for decentralized non-convex optimization.The framework is designed as a single decentralized optimization paradigm.
- Contributions: O(T^-1/2) expected squared Moreau-envelope stationarity is established while accounting for compression, network topology, and triggering effects.The convergence analysis explicitly includes these communication and network factors.
- Empirical conclusion: Experiments report a favorable accuracy-fairness-communication trade-off while reducing communication cost compared with existing baselines.The evaluation covers heterogeneous settings.
APPENDIX A PROOF OF THEOREM 1 & COROLLARY 1
The appendix proves PAC-Bayes guarantees for the agnostic mixture objective by treating worst-client or mixture selection through augmented posterior-prior constructions. It then bounds the perturbation caused by stale, sparse, quantized, and event-triggered neighbor exchanges.
- PAC-Bayes proof: For Λ = ∆n, the agnostic mixture-risk supremum is attained at a simplex vertex corresponding to a measurable worst-case client selection.The augmented posterior and prior add ln n to the KL divergence.
- PAC-Bayes proof: For compact Λ, an independently constructed ℓ1 ε-net approximates the population maximizer using the 1-Lipschitz property of population and empirical mixture maps.The augmented KL divergence becomes KL(Q∥Π) + ln |N_ε(Λ, ∥·∥1)|.
- PAC-Bayes proof: Hoeffding’s lemma, PAC-Bayes change of measure, and Markov’s inequality yield simultaneous high-probability bounds for the augmented posteriors.The argument assumes losses in [0,1] and mutually independent client samples.
- Communication perturbation: The PAC-Bayes bound is algorithm-agnostic, while the subsequent analysis quantifies one-step empirical fairness-risk perturbation from stale and compressed neighbor copies.The perturbation analysis isolates the communication approximation introduced by the graph regularizer.
- Communication perturbation: The stale, sparse, quantized, and event-triggered neighbor-exchange perturbation vanishes asymptotically as T → ∞.This establishes the stated corollary after bounding the one-step empirical agnostic mixture-risk perturbation.
APPENDIX B PROOF OF THEOREM 2 (CONVERGENCE ANALYSIS)
The convergence proof decomposes the implemented update into fairness, stochastic, compression, and graph-coupling components, then controls their effects through proximal Moreau-envelope analysis. Communication-copy errors are bounded separately for triggered and non-triggered exchanges.
- Update decomposition: The vector update is wt+1 = wt − γt ht with ht = Vt + qt + dt, separating the implemented direction into principal, compression, and graph-approximation terms.The decomposition supports separate control of communication and stochastic effects.
- Descent argument: Conditional zero mean of the compression error removes its inner-product contribution in expectation during the descent argument.The proof conditions on the history and fairness-selection mini-batches before taking expectations.
- Event-trigger analysis: Triggered communication applies compressor-based error control, while non-triggered rounds preserve the existing copy because no message is sent.The proof combines both cases to bound communication-copy errors.
- Graph-coupling control: The graph-direction approximation error is bounded by the communication residual, yielding ∥dt∥2 ≤ nα2 d̄G Et.This relation supplies the graph-coupling constant used in the convergence proof.
C. Proof of Lemma 6
The proof sums the one-step inequality over all iterations, applies the stated lower bound and auxiliary assumptions, and derives the convergence bound. The resulting terms scale as O(T^-1/2), while communication contributes the lower-order O((1 + log T)/T) term.
- Summing the one-step inequality over t = 0, . . . , T −1 and using Lµ(wT ) ≥ L⋆ produces the aggregate bound.
- O(T −1/2) describes the first four terms, whereas the communication term is O((1 + log T)/T) because problem-dependent constants are independent of T.
- The proof concludes that communication effects are lower order relative to the dominant convergence terms.