Unified Privacy Guarantees for Decentralized Learning via Matrix Factorization

AI summary

Overview

• Research area: Privacy-preserving machine learning, specifically Differentially Private Decentralized Learning (DP-DL) and privacy accounting via the Matrix Factorization (MF) mechanism.
• Technical level: Advanced. The paper assumes familiarity with Differential Privacy, Gaussian DP, gossip/consensus averaging on graphs, and the matrix factorization mechanism for correlated noise in DP-SGD.
• Scope: The paper generalizes matrix-factorization privacy accounting to decentralized learning, casts existing DP-DL algorithms and trust models into a single linear formulation, and uses that formulation to design a new algorithm, MAFALDA-SGD.

What This Paper Is About

Decentralized learning lets users train a shared model by averaging updates with neighbors on a peer-to-peer graph instead of sending data to a central server. Differential Privacy can be added with noise, and in principle decentralization can amplify privacy because noise spreads across many communications. In practice, though, the observed privacy-utility trade-off is often worse than in centralized training, which the authors attribute to limitations in current DP accounting methods for decentralized learning. This paper shows that recent centralized accounting advances based on Matrix Factorization can be generalized to decentralized learning, yielding tighter privacy guarantees for existing algorithms and a principled way to build new ones.

Key Contributions

1. Generalized MF privacy guarantees. The authors extend existing privacy results for the Matrix Factorization mechanism to a broader class of workload matrices—rectangular and possibly rank-deficient, column-echelon rather than strictly square, full-rank and lower-triangular—with a sensitivity definition that depends on both the encoder matrix C and the decoder matrix B.
2. A unified formulation of decentralized learning. They show that standard DL algorithms and common trust models (Local DP, Pairwise Network DP, and Secret-based LDP) can all be written as attacker knowledge of the form A·G + B·Z with A = BC, where G stacks gradients and Z stacks noise.
3. A new algorithm, MAFALDA-SGD. Using this framework under Local DP, they introduce MAFALDA-SGD, a gossip-based DL algorithm whose noise correlation is optimized offline for the decentralized workload, restricted to local correlation so that nodes never need to share noise.
4. Empirical evaluation. They show tighter accounting for an existing PNDP algorithm on synthetic and real-world graphs, and show that MAFALDA-SGD outperforms private baselines on a regression task.

Main Findings

• Tighter PNDP accounting than prior work: For DP-D-SGD (equivalent to Muffliato-SGD of Cyffers et al. (2022) when the number of gossip steps is K = 1, as stated in the paper), the new accounting is significantly tighter than the original for all node distances and all tested graphs. The original accounting gave no improvement over Local DP for nodes at distance less than or equal to 2, whereas the new one already achieves gains of up to an order of magnitude at those distances.
• Large gains at longer distances: For nodes at distance greater than or equal to 3, the improvement is at least two orders of magnitude. The gains are consistent across the Erdős–Rényi, Facebook Ego, PeerTube, and Florentine Families graphs. Accounting is reported as Rényi divergence with α = 2 (results are proportional to α) with minimum, maximum, and average error bars over nodes at a given distance.
• MAFALDA-SGD beats private baselines: On the Housing dataset under Local DP, MAFALDA-SGD outperformed all private baselines across all privacy regimes by a large margin. For a fixed privacy budget ε it achieved a 31% average improvement in test loss in the last 50 training steps; for a fixed test-loss value of 0.75 it achieved a 2-fold reduction in ε.
• Existing correlation schemes transfer poorly: The paper reports that AntiPGD, a correlation scheme from the centralized setting (subtracting the noise added at a step in the next step), performs poorly when used in decentralized learning, motivating optimizing correlations specifically for the decentralized workload.
• Privacy holds under adaptivity: Theorem 8 states that the mechanism remains 1/σ-GDP even when the gradient matrix G is chosen adaptively, provided A is column-echelon (which prevents dependence on future information).

Methodology in Plain English

The authors build a common language for decentralized learning algorithms. Every algorithm is written as a sequence of clipped local gradient steps followed by gossip averaging, and the whole run over T iterations is compressed into one matrix equation using a large lower-triangular block matrix built from powers of the gossip matrix W. They then separate two things that are merged in the centralized setting: the matrix that describes the optimization (how models are updated and averaged) and the matrix that describes what an attacker actually sees. Under a given trust model, the attacker's observations become A·G + B·Z—a linear function of the gradients and the injected noise—which is exactly the shape the matrix factorization mechanism analyzes.

They then prove a generalized privacy theorem for this form. The key quantity is a sensitivity measure that projects the encoder matrix onto the row space of the decoder matrix, so that unobserved gradient combinations are discarded. When the decoder is square and full rank, this reduces to the known centralized formula.

For the new algorithm, MAFALDA-SGD, they minimize the sensitivity-squared times the utility term, but the encoder matrix would be of size nT × nT, which is intractable. They therefore constrain the encoder to be Kronecker-structured (local correlations only, with all nodes following the same pattern), reduce the objective to a standard factorization problem via a Cholesky decomposition of a Gram matrix H built from a commutation matrix, and solve it with L-BFGS using existing matrix-factorization tooling. The resulting correlation matrix can be computed offline by any party that knows the gossip matrix and participation pattern.

Experiments use synthetic and real-world graphs: Erdős–Rényi graphs with 100 nodes and parameter p = 0.2; the Facebook Ego graph with 148 nodes; a PeerTube graph restricted to its largest connected component with 271 nodes; and the Florentine Families graph with 15 nodes. The learning task is regression on the Housing dataset (8 features, 20,640 data points) using an MLP with one hidden layer of width 64 and ReLU activation, followed by a linear output layer, trained with mean-square error loss. Each data point participates 20 times, with participation every 19 steps, corresponding to a (k, b)-participation scheme with k = 20 and b = 19.

Why This Matters

• Unifies a fragmented literature: Prior DP-DL results relied on ad hoc proofs tailored to specific algorithms and trust models. This work gives one formulation that covers all existing DP-DL algorithms and trust models, which makes comparisons and new designs more systematic.
• Closes an accounting gap: Because the tighter accounting composes with the graph topology and the correlations between nodes, decentralization's theoretical privacy amplification becomes visible in the numbers rather than being lost to overly pessimistic bounds.
• Real-world applications (as implicated by the paper's settings):
  • Federated and peer-to-peer learning deployments where no trusted central server exists, such as cross-device or on-premise model training.
  • Decentralized social platforms: the paper uses a PeerTube graph, where servers follow one another and recommend videos across instances.
  • Social-network-shaped deployments: the paper uses the Facebook Ego friendship graph.
  • Privacy-sensitive statistical modeling on tabular data: the paper's learning task is housing-price regression on the Housing dataset.
• Industry relevance: Any organization that trains models across parties without a trusted aggregator—healthcare consortia, edge and IoT fleets, and decentralized platforms—can use the framework to obtain principled privacy budgets, and the optimized noise correlation comes with an offline precomputation step rather than new infrastructure.

Future Directions

• Scaling the correlation computation: The paper reports complexity of O(n³T + n²T³) in time and O(n²T²) in space for building the matrix L, plus O(T³) per L-BFGS step, and notes that correlation restarts can be used to keep T within reasonable bounds. Reducing this cost for large graphs or long horizons is an open direction.
• Beyond local correlation: The MAFALDA-SGD constraint C = C_local ⊗ I_n assumes all nodes follow the same local pattern and forbids sharing noise across nodes. Determining what becomes possible—and what trust assumptions are needed—when cross-node correlation is allowed is left open.
• Optimizing under other trust models: The paper optimizes correlation explicitly only under Local DP; applying the same optimization machinery under PNDP or SecLDP is a natural extension.
• Broadening the algorithm class and empirical scope: The framework covers linear DL algorithms, and the experiments study one regression task, one privacy level set, and a specific participation scheme. Extending evaluation to other algorithms, datasets, non-linear observables, and the results deferred to the paper's appendix would test how far the unifying formulation reaches.

Target Audience

Researchers and graduate students working on differential privacy, decentralized and federated learning, or privacy accounting; practitioners designing peer-to-peer training systems who need defensible privacy budgets; and theoreticians interested in the matrix factorization mechanism who want to see it extended from the centralized setting to graph-structured, multi-party computation.

Authors’ abstract

Decentralized Learning (DL) enables users to collaboratively train models without sharing raw data by iteratively averaging local updates with neighbors in a network graph. This setting is increasingly popular for its scalability and its ability to keep data local under user control. Strong privacy guarantees in DL are typically achieved through Differential Privacy (DP), with results showing that DL can even amplify privacy by disseminating noise across peer-to-peer communications. Yet in practice, the observed privacy-utility trade-off often appears worse than in centralized training, which may be due to limitations in current DP accounting methods for DL. In this paper, we show that recent advances in centralized DP accounting based on Matrix Factorization (MF) for analyzing temporal noise correlations can also be leveraged in DL. By generalizing existing MF results, we show how to cast both standard DL algorithms and common trust models into a unified formulation. This yields tighter privacy accounting for existing DP-DL algorithms and provides a principled way to develop new ones. To demonstrate the approach, we introduce MAFALDA-SGD, a gossip-based DL algorithm with user-level correlated noise that outperforms existing methods on synthetic and real-world graphs.