Unified Privacy Guarantees for Decentralized Learning via Matrix Factorization
Authors: Aurélien Bellet
Edwige Cyffers
Davide Frey
Romaric Gaudel
Dimitri Lerévérend
Francois Taiani
Venue: ICLR 2026 Poster (2026)
Keywords: Differential Privacy
Decentralized Learning
Matrix Mechanism
Gossip
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We cast Decentralized SGD as a Matrix Factorization Mechanism, improving existing accounting methods and leading to a new algorithm Mafalda-SGD with better privacy-utility trade-offs.

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.

Published as a conference paper at ICLR 2026
UNIFIED PRIVACY GUARANTEES FOR DECENTRAL- IZED LEARNING VIA MATRIX FACTORIZATION
Aurélien Bellet
Inria, Université de Montpellier, INSERM Montpellier, France
Edwige Cyffers
Institute of Science & Technology Austria (ISTA) Klosterneuburg, Austria
Davide Frey, Romaric Gaudel, Dimitri Lerévérend; François Taïani University of Rennes, Inria, CNRS, IRISA Rennes, France
ABSTRACT
Decentralized Learning (DL) enables users to collaboratively train models with- out sharing raw data by iteratively averaging local updates with neighbors in net- work 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 cen- tralized training. which may be due limitations current DP accounting meth- ods for DI.. In this paper, we show that recent advances in centralized DP account- ing 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 formu- lation. 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 lated noise that outperforms existing methods on synthetic and real-world graphs.
gossip- based DL algorithm with user-level corre-
INTRODUCTION
In Decentralized Learning (DL), participants collaboratively train shared model by exchanging model parameters on a peer-to-peer communication graph (Lian et al., 2017 2018 Koloskova al.,
2020 Beltrán al. 2022 Tian al. 2023 Yuan al. 2024). By removing the central server, DL offers faster deployment, higher scalability, and improved robustness. Since data remains local only subset of communications, DL is also motivated by privacy cerns (Cyffers & Bellet 2022, Cyffers et al. 2202 Kairouz et al. 2021c). However, decentralization still leak sensitive information that enables inference or reconstruction of local data (El Mrini et al. (2024) Pasquini et al. 2023). Data protection thus requires additional mechanisms beyond decentralization.
and each participant
alone is insufficient ensure privacy, as exchanged messages
Differential Privacy (DP) (Dwork et al. 2006) is the gold standard for privacy in machine learning. DP protects participation by ensuring that outputs do not depend too strongly on any single data point, typically through noise injection. Extending DP to Decentralized Learning is challenging: unlike centralized settings, where trusted curator releases only the final output, DL exposes in- termediate peer-to-peer messages to participants. A natural option is to analyze DP-DL algorithms under Local DP (Kasiviswanathan et al. 2008 Bellet et al. 2018 Wang et al. 2015), which assumes
"Corresponding author, dimi mimmiiiiicm weweverendeinnnee nria..f

---

Published as a conference paper at ICLR 2026
all messages released publicly, but this overly conservative trust model often leads to poor pri- vacy- utty-utility tradc-offs (Chan et al. 2012). More realistic models, such as Pairwise Network DP (PNDP) (Cyfters et al., 2022; Cyffers & Bellet 2022) and Secret-based LDP (SecLDP) (Allouah) et al. 2024), have recently been proposed to account for adversaries with only partial knowledge of the system, showing that decentralization can amplify privacy guarantees relative to Local DP.
Unfortunately, despite these recent advances, designing DP-DL algorithms and analyzing their pri- vacy guarantees remains a difficult and technical endeavor, and existing results rely on ad hoc proofs tailored to specific algorithms and trust models (Cyffers et al., 2024; Biswas et al. [025] Allouah al. 2024), rather than on a general, principled approach. There is also room obtain tighter pr- vacy guarantees by more carefully accounting for correlated noise arising from redundant exchanges between nodes, both in parallel and across timesteps an aspect largely overlooked in existing anal- yses, which can lead to overly pessimistic bounds.
In this work, we address these limitations by introducing unified formulation for analyzing pri- vacy guarantees in DP-DL, building recent advances in centralized privacy accounting via the Matrix Factorization (MF) mechanism (Kairouz et al., 202 Pillutla et al. (025). MF uses a well- chosen factorization of a workload matrix representing the algorithm to exploit noise correlations and achieve stronger privacy-utility trade-offs, but has been so far applied only in centralized con- texts. We propose framework that make MF applicable to ensuring DP in decentralized learning. Achieving this requires addressing several fundamental challenges. First, decentralized learning algorithms must be encoded been achieved in prior work. Second, the diversity of trust models requires disentangling the matrix governing privacy guarantees from the one driving optimization schemes-twa quantities that col- lapse into a single object in the centralized setting. Finally, incorporating these elements requires generalizing MF to richer classes of workload matrices and constraints. Our framework overcomes these challenges. providing a principled foundation to analyze existing DP-DL algorithms across different trust models and to design new ones. Specifically, our contributions are as follows:
single tractable matrix multiplication, formulation that has not
(i) We generalize existing privacy guarantees for MF to broader settings; We show how existing DP-DL algorithms and trust models can be analyzed as specific instances of our generalized MF framework;
(iii) We use our framework to design a new algorithm, MAFALDA-SGD; and
(iv) We evaluate our approach on synthetic and real-world graphs and datasets, demonstrating tighter privacy guarantees for existing algorithms and superior performance of MAFALDA- SGD compared to prior methods.
2 RELATED WORK
Matrix factorization mechanism. The Matrix Factorization (MF) mechanism for SGD first ap- peared as a generalization of correlated noise in the online setting (Kairouz et al., 202 based on tree mechanisms (Dwork et al. 2010: Jain et al., 2012), and was later formalized by Demisov ctt al. (2022). More recent work improves the factorization either by designing more efficient de- compositions CChoquette-Choo
al., 2023), or by allowing additional constraints the strategy matrix, i.e., the matrix encoding locally applied noise correlations on the gradient. Existing con- straints typically enforce a limited window for temporal correlations via banded matrices, which reduces computation (Choquette-Chie -Choo et al., (2023] Kalinin & Lampert (2024), whereas in this work our constraint in MAFALDA-SGD enforces that correlations occur only within nodes. Other works extend the mechanism to more complex participation schemes (Choquette-Chie et al. 2023). For a more comprehensive survey, we refer the reader to Pilllula al. (2025).
Differentially private decentralized learning. Private decentralized learning was first studied un- der the trust model of Local DP (Bellet et al.] 22088 Cheng et al.] 2019 Huang et al. 2015). which suffers from poor utility due to overly pessimistic assumptions: participants are only protected by their own noise injection, since all messages are assumed to be known to the attacker. Relaxed trust models have since gained traction, such as Pairwise Network Differential Privacy (PNDP) (Cyffers) et al. 2022). ) initially introduced for gossip averaging and later extended to several algorithms (Cyf- fers al. 2024 Li al. 2025 Biswas et al.) 2025). PNDP assumes that the attacker is node participating in the algorithm, and that it is thus sufficient to protect what a node observes during the ceccution-typicalle only the messages it sends receives. Similarly, SecL.D (Allouah al.
2

---

Published as a conference paper at ICLR 2026
2024) enforces DP conditional set of secrets that remain hidden from the attacker. The idea of correlating noise has a long history in DL. first as an obfuscation method against neighbors with- out formal guarantees (Mo & Murray 2017 Gupta al., 2020). More recent works provide DP guarantees for algorithms with correlated noise (Sabater et al. 2022 Allouah et al. 2024 Biswas et al., 2025), but correlations are not optimized and instead dictated by what can be proven, which explains why our method MAFALDA-SGD significantly outperforms them. Finally, the concept of representing attacker knowledge in DL via a matrix that can be constructed algorithmically was in- troduced by EEI Mrini et al. (2024) and more recently studied by Koskela & Kulkarni (2025), but only for specific cases of algorithms and trust models, and without establishing connection the matrix factorization mechanism.
3 BACKGROUND: MATRIX FACTORIZATION MECHANISM
In this section, we review the centralized version of Differentially Private Stochastic Gradient De- scent (DP-SGD) and correlated noise variant based on matrix factorization (MF-SGD) (Denisov et al. 2022), which we will later adapt to the decentralized case.
Differential Privacy (DP) (Dwork et al. 2006) ensures that the output of mechanism does not reveal too much information about any individual data record in its input. A mechanism satisfies DP its output distribution remains close on any two neighboring datasets and D' that differ one record (denoted D = D'), Although DP is classically defined in terms of (e, 6D- in this paper we adopt Gaussian DP (GDP), which is particularly well suited to mechanisms with Gaussian noise. GDP offers tighter privacy accounting, simpler analysis, and can be converted back into Rényi DP or (c, 6)-D (Dong et al. 2022).
- Dong et al. 2022 Pillutla et al. 22025. A ran- domized mechanism M satisfies p-Gaussian Differential Privacy (J-GDP) if. for any neighboring datasets D D', there exists a (possibly randomized) functioo h such that
Definition (Gaussian Differential Privacy (GDP)-Dovvl
M(Z) d M(D), Z ~~010,11, M(Z') - M(D'), Z'~N((,1)
where- denotes equality in distribution.
In practice, Gaussian DP is obtained by adding appropriately calibrated Gaussian noise, which is the central building block of the centralized DP-SGD algorithm. Given a training dataset D, a learning rate 1/ > O, and starting from an initial model 0o E R.d, the DP-SGD update can be written as:
0++1=0, 0, 0.
(ge + 2 9t = clip (VS(O,,))) E),,), 2 ~ ('0,
(1)
with & sample from D and A suppe [V) V2(2) the sensitivity of V enforced by the clipping operation. Even for this simple version of DP-SGD without correlated noise, we can define a so-called workload matrix Arre IR TxT with 4 1,25 such that:
0= 0. (A G Z), GERTX.
(2)
where 0 is the matrix of stacked 01,..., Gr, G is the matrix of stacked gradients and 7 ~ (O, o² a'd) Here G corresponds to the data-dependent part of the algorithm, and & corresponds to the outputs of DP-SGD. We thus aim to protect G as much as possible by adding a large variance vector Z, while still achieving the best possible final 0r, typically by keeping 2 as small as possible.
To reach these contradictory goals, the matrix factorization mechanism exploits the postprocessing property of which ensures that if mechanism M GDGDP, then for every function f. foM also H-GDP-to allow noise correlation across iterations and improve the privacy-utilin trade-off. For any factorization A BC, one can rewrite G + BZ as A ( +- C 2), where the multi- plication by ArR is seen as a post-processing of the term (G+CCZ) Z) and Cf is the pseudo-inverse of C. This factorization leads to a slight modification of DP-SGD, resulting the MF-SGD updates:
O++1 = 02 - ( + Σt=o Ct,x².)
To derive DP guarantees for MF-SGD, it suffices to analyze the privacy guarantees of (G + CtZ). For neighboring datasets D ~ D' differing only in one record æ, differences in occur whenever x is used, which may happen multiple timesteps if the dataset cycled through several times. The
3

---

Published as a conference paper at ICLR 2026
Algorithm ME-D-SGD: Matrix Factorization Decentralized Stochastic Gradient Descent
Require: W R C, Ay. o, 0o Raxx, Z ~ (0, (3, wTxd
1: for all node u in parallel do
2: for /
9: [u) 1 to 7 do
3:
+ clip V (f) (1()))) Agl with c(x) ~ D'
> Clipped gradient
T(g (w) + (CCt))nni (netmi)
4:
b Local update
Send (lw) all neighbors e F.
5:
Receive g(v) from all neighbors T.. 0.41
6:
2+2
7:
Ever, Wlu.v
Local average
8: return 0/4/1 Vu E [1,n]
participation scheme is the set of all participation patterns т, encoding whether ø participates in given row of G (see Chapter 3 in Pillutla et al.) 2025). This extends the neighboring relation from datasets to gradients: G =m G'. The sensitivity is then the worst case over all participation patterns:
sens C) se + CG) max G=nG'
||C (C-G-GG -G
11
For fixed sensitivity vensn(C), generating Z ~N(00, sensn(C)3)) ensures that (G Ctz) GDD... Optimizing the noise correlation is typically done by minimizing sens(C)² |B] under the constraint _A = BC, where ||B|] represents the utility of the factorization. While the privacy analysis is straightforward if G and G' are fixed advance, the guarantee remains valid when G is computed adaptively through time, with II depending on 91...... - -t....-9t-11 This has been proven only for workload matrices that are square, lower triangular, and full rank (Denisov et al. 2022] Pillutla al. (025). We show in Section 5 that the privacy guarantees also hold in a more general case, thereby enabling adaptivity DL as well.
DECENTRALIZED LEARNING AS A MATRIX FACTORIZATION MECHANISM
In this section, we show that many DL algorithms can be cast as instances the matrix factorization mechanism. To do so, we must address several challenges: encoding the updates of the algorithms, representing the sensitive information, and capturing what is known to a given attacker suitable for analyzing DP guarantees. For concreteness, for a specific yet already fairly general algorithm, which we call MF-D-SGD, under Local DP, and then further generalize large class of DL algorithms and trust models in Section 4.2
form first show in Section 4. how to proceed
4.1 WARM-UP: MF-D-SGD UNDER LOCAL DP
We introduce the decentralized setting studied in our work and build step-by-step the encoding of Decentralized SGD (D-SGD) algorithm where DP is introduced in similar way as in MF-SGD.
We refer to this algorithm as ME-D-SGD and present its pseudocode from the users' perspective in Algorithm D and from the matrix perspective in Figure D
We consider that n users, represented as nodes of graph G (V,E), collaboratively minimizing loss function by alternating gradient steps computed on their local datasets (D,) (Lines and 4h and gossiping steps, i.e., averaging their local models with their neighbors (Line 5 In DI., two datasets D = (Dw) (eu) and D' = (D') are neighboring if they differ in exactly one record at a single node u, i.c., D. D' for all
and D', = D. \ {x} U (2'). We write this as D ~ D'.
Model updates. We stack the local parameters the nodes as a vector O, E Raad where o(w) is the local parameter of node at time E [0,T T 1].. The gradient step then be written as 0.+ = 0, 7 (G, + Z) where each row u of G, is the vector G(1)) V (0(") " and C E Rm is the block of Ct from the (tn + 1)-th row to the (t 1)n-th one. C. Z captures arbitrary noise correlation, and setting C Tar recovers the local updates of DP-D-SGD, the simple
4

---

Published as a conference paper at ICLR 2026
Ne Woddral 2
Lock soorgttt
hee if
with seal
Draen frr Aiil eleawic
Bee 2
(TT W
80 ?
C
heer T{
Goords mantie
W
Oytvrieérusee eoreniin
Dutt Indepecdaes
Figure 1: Overview of the MF-D-SGD algorithm written single equation.
decentralized SGD with uncorrelated noise. After the local updates, nodes perform a gossiping step, exchanging their models with neighbors and averaging the intermediate models 0 using the gossip matrix W.
r+3
Definition 2 (Gossip matrix). A gossip matrix W E R2 on the graph G = (V,E) is stochastic matrix, Le.. Ex=1 Wav 1, and if Wav 0 then is neighhor of denoted T..
With this definition, the gossiping step can be written as 0,41 = W0 Thus, one full iteration of MF-D-SGD corresponds to 0.+1 = W W(, 7 (G, + C)
We now stack all steps of MF-D-SGD over T iterations. This requires defining a matrix M with stacked powers of W (starting with power 0) and a larger matrix Wr E R xnT with blocks of size in lower triangular Toeplitz form, where the main diagonal is filled with I, and the i-th diagonal with W i-1 Wi-1 The whole algorithm can then be summarized as:
0 (Tr W) (Mo, n Wr(G+
where O and G denote the collections of local models and gradients, respectively, after T' iterations.
Remark 3. Up to this point, we have assumed that the gossip matrix W is fixed across iterations for simplicity's sake (notably when explaining Figure [7.. the remainder of the paper we move to the more general case of time-varying gossip matrices W.. This change only requires replacing powers of single matrix gossip W by products of matrices the expression of WT. See Appendix A.7 for details of this more general expression.
Attacker knowledge. subtlety arises from the fact that under decentralized trust models, an attacker typically does not observe the sequence of local models 0 directly. Hence, we should not apply the MF mechanism to Equation (5), but rather the peer-to-peet messages. Under the Local DP trust model, where all messages exchanged by the nodes throughout the algorithm are assumed to be public, the view O of the attacker can be seen as a MF mechanism:
O (G+
(6)
4.2 GENERAL FORMULATION
The factorization obtained in previous section for MF-D-SGD requires assumptions: (i) each iteration, every node sends the same message to all of its neighbors, and (ii) the attacker observes all messages shared on the network. To encompass broader range of algorithms and trust models, this section proposes more general definitions for both. To the best of our knowledge, these definitions cover all existing DP-DL algorithms and trust models.
Definition 4 (Linear DL algorithm). A decentralized learning algorithm is linear if all observable quantities can be expressed as a linear combination of the concatenated grudients G and the con- catenated noise Z.
This definition covers the Zip-DL algorithm, in which user u applies distinct yet correlated noises to its communications within the same gossiping step (Biswas et al., 2025). We complete our frame- work by defining trust models on linear DL algorithms as follows.
Definition 5 (Attacker knowledge). Given a Linear DL algorithm. the attacker knowledge of trust model, i.e., the information the attacker A derives from its observations, can be expressed as O AG + BZ.
5

---

Published as a conference paper at ICLR 2026
This definition encompasses not only scenarios in which knowledge is obtained by observing mes- sages or models, but also situations where the attacker sees only a subset of them, as PNDP. further allows encoding: (i) gradients already known to the attacker, e.g., when user knows its own gradients or those of colluding users (in which case the corresponding columns of A are 0); (ii) information available about the noise, e-g-, when user knows the noise it added, in SecLDP when some neighbors' noise values are known (in which case the corresponding columns of B are 0), as shown by the following theorem.
Remarkably, these general definitions not only capture all widely used trust models and algorithms. but the existence by the following theorem.
corresponding factorization for these cases also guaranteed, as established
For each of the three trust models-LDDD PNDP, and SecLDP- for all existing DL algorithms, there exist matrices A, B. and C such that the attacker knowledge can be expressed as Oa= AG + BZ with A = BC.
Theorem 6.
We refer the reader Appendix for the proof, where we construct the matrices A, B and for each trust model based on the algorithms that introduced them. These matrices are constructed in two steps: (i) forming three distinct blocks corresponding to observed messages, known gradients, and known noise; (ii) removing from the overall matrix A the contribution of the known gradients. The first step ensures that all known information properly accounted for, while the second step guarantees the existence of factorization A BC, which is crucial to obtain GDP guarantees, as established in the next section by Theorem g
5 MORE GENERAL PRIVACY GUARANTEES FOR MATRIX FACTORIZATION
In Section 4 we showed how to cast the attacker knowledge in DL as a MF mechanism AG + BZ with A BC. However, the resulting matrices do not satisfy the assumptions used in existing MF results, which require to be a square, full rank and lower-triane triangular matrix. In this section, extend the MF mechanism's differential privacy guarantees workloads A that may violate these assumptions. To do so, we first introduce a more precise definition of sensitivity, which is fundamental for evaluating the quality of factorization (Pillutla al. 2025).
Definition 7 (Sensitivity under participation, generalized). Let B and C' be two matrices. The sensitivity of C with respect to B and a participation scheme 11 is
sens( (C; B)
||C
Gl)
G-nG'
with |AI| == tr tetttr(ATTT (ATBA).
With this definition, we state our main privacy theorem, whose proof is provided in Appendix B
Theorem 8. Let OA = AG + BZ be the attacker knowledge of a trust model on linear DL algorithm, and denote M(G) the corresponding mechanism. Let II be a participation scheme for
mond G. For Z ~ N (0 when A is column-echelon matrix and there exists some matrix C such that A BC with
V = == sens(( B) with
sens
(en & max sEll
Σ S,EET
(CT
(8)
II
then M LGD,, even when G is chosen adaptively.
Theorem 8 shows that the privacy guarantees of a matrix factorization mechanism remain valid for a broader class of matrices A, even when the gradient vector is chosen adaptively, i.e., when it may depend arbitrarily on all past information (Denisov al. 2022).. The column-echelon form property of the matrix ensures it cannot depend on on future information. This generalization of the usual lower- triangular property is necessary when considering attackers who have only partial information the network. Most sets of observations that follow the natural causal ordering in DL can be rewritten column-echelon matrix.
Our result generalizes existing results by allowing to be rectangular and possibly rank-deficient, a relaxation crucial for applying it DI. algorithms. The price of this extension is dependency B:

---

Published as a conference paper at ICLR 2026
since B may not be invertible, C' is not unique, and the sensitivity now depends both the encoder matrix C' and the decoder matrix B. The correction B B can interpreted as a projection of the columns of C' onto the space of B, discarding unobserved gradient combinations. When B is square and full rank, as in prior work, we recover the known formula sensn(C; B) sensn (C; 7) (C)
In DL, the participation scheme II is also slightly modified. A participation pattern x is associated to a local dataset D. and can be non-negative only for the rows in {u, n u..... (T
Remark 9.
1)n + w). which corresponds to gradients computed from 'D.-
Remark 10. Following Corollary I of Dong et al. (2022), μ-GDP directly and rightly translates into (c, 6D- with appropriate e and ó values. Moreover, it is also possible to derive (a, c)-éénii
DP guarantees Gil et al. 2013).
A NOVEL ALGORITHM WITH OPTIMIZED NOISE CORRELATION
In this section, we showcase how the formalization developed in the previous sections enables op- timizing noise correlation in DL algorithms. Specifically, we introduce MAFALDA-SGD (MAtrix FActorization for Local Differentially privAte SGD), new algorithm for DL. with LDP, which can be seen as a special instance of MF-D-SGD.
We first define an objective function Cupa capturing the optimization enror of MF-D-SGI
Definition 11. Consider Equation (5) with encoder matrix C, such that WT BC. The optimal correlation can be found by minimizing the following objective function:
Cupii (W r, (,,,BCC) = sens (C; (C; & W) W) TI
In DL, the optimization loss is defined with respect to the averaged model, as explicilly written in Equation (5) for MF-D-SGD. However, sensitivity must also account for the attacker knowledge (Theorem 8) which in this case corresponds to Oa (defined in Equation (6)) The difference be-
tween the two terms explains why. despite having workload matrix equal Wr, the second term involves (Ir & W) Wr instead.
While one could attempt minimize Equation (9) directly, doing so is impractical without additional constraints. The encoder matrix C' has size nz' x nnl, which becomes intractable for large graphs or long time horizons. Furthermore, the resulting correlated noises could necessitate correlations across nodes, which in turn would require trust between them. These challenges motivate the introduction of structural constraints on C.
Here, we focus on Local DP guarantees, where nodes cannot share noise. Accordingly, we consider only local correlations, constraining C' = Crocal 3 Jn so that the block structure enforces locality and all nodes follow the same pattern, reducing the cost of computing C. For simplicity, we also assume that all nodes adhere to the same local participation pattern. Correlation schemes proposed for the centralized setting naturally fit this form; for example, AntiPGD (Koloskova al. (023)) subtracts the noise added at a given step in the next step. However, we find that this correlation pattern performs poorly when used in DL (see Section (7). motivating approach of optimizing correlations specifically for decentralized algorithms.
Under LDP and local noise correlation, sensitivity depends only on Cweat- We simplify the general objective in Definition I with the following lemma, with its proof deferred to Appendix [
Lemma 12. Consider the LDP trust model (Á = Wr. B = B) and local noise correlation Ciocal & Ind Define:
A= := [Ir
& (m))
H : Σ A,A. A
(10)
where (T,))) is a commutation matrix that commutes space and time in representation Loan 2000 Then, the objective function of Equation (9) is equivalent to:
Copa (Wr, ; B, Crocat) Loppi (W T. Cioca) sens (Crcai) I.Clucal (loca F²
(11)
Hass
where I. is lower triangular and obtained by Cholesky decomposition of H = T. L.

---

Published as a conference paper at ICLR 2026
Algorithm 2 MAFALDA-SGD: MAtrix FActorization for Local Differentially privAte SGD
Require: We RR*x, T, Ag. o, 0g E B
1: Build workload matrix Wr T
Figure
2: H + Σi=1 A,A, A; where A; == [IT @ W) W..) (xTs((41)7-1
> Lemma 12
3: L Cholesky decomposition of H
> H = L L
4: Cmafalda +- minC Coptl (L, Chocal)
Using L-BFGS Choquette- Choo et al. (2023
5: return MF-D-SGD(W, mmtaadda T, Ag 0, Bu)
> Algoritmm
This yields standard factorization problem for L. which can be solved using existing frameworks for the MF mechanism Choquette- Chho al. (2023); (Pillulaa et al. (2025). practice, these frame- works operate on the Gram matrix H L. 7., avoiding the need for Cholesky decomposition.
Algorithm summarizes our novel MAFALDA-SGD algorithm. first computes the optimal correlation by optimizing for the privacy-utility trade-off in DL based on the objective function Lemma 12 before running MF-D-SGD with the resulting Gmafalda- Note that Caaaalda can be computed offline by any party that knows the gossip matrix and the participation pattern.
Remark 13. The complexity of Algorithm 2 is driven by (i) the computation of the matrix L, which costs On n² time, and ( ( in space, and (ii) the minimization of Lopu which is O(T9) per step L-BFGS. Correlation restarts (Pillutla et al. 2025) be used keep T within reasonable bounds.
7 EXPERIMENTS
In this section, we highlight the advantages of our approach by first showing that we can achieve significantly tighter privacy accounting for an existing algorithm under PNDP (Section 7.1) and then demonstrating that MAFALDA-SGD outperforms existing DL algorithms under LDP. We use both synthetic and real-world graphs. Additional experiments are reported in Appendix
7.1 TIGHTER ACCOUNTING FOR PNDP
Privacy loss [Röugi Divergence)
102
Graph
10
Accomnting
10-1
Floeatine
Fooebook Ego
Peentulee
Ouss
Cyfiee (1020)
Shortest Path Length from Attacler
Figure 2: PNDP loss accounting for DP-D-SGD. comparison between the original accounting of Cyfters et al. (2022) (dashed lines) and our accounting (solid lines) under the PNDP trust model. We report the Rényi divergence (fixing 2 w.l.o.g., since the results are proportional to a) for the minimum, maximum, and average in error bars over nodes at a given distance.
In this experiment, consider DP-D-SGD-whind corresponds to the Muffliato-SGI algorithm from Cyffers et af. (2022) when the number of gossip steps is set to = l-and compute its PNDP guarantee with different privacy accounting methods: the one proposed by byfCyfeer et al. (2022) and our own, obtained by casting the guarantees of Theorem g to the case of DP-D-SGD with
PNDP attacker follows. For C, InT and B. P. WT. using Theorem g the bound on sensitivity of DP-D-SGD under PNDP is
sens CCi Ba) < max Σ (B)B.)
Σ (P.WW))
max
(12)
KEII
xEll SHETT
KTETT
8

---

Published as a conference paper at ICLR 2026
This sensitivity allows us compute GDGDP bound, which we then convert into RDP. Since the initial accounting in Cyffers et al. (2022) was performed at the user level rather than at the finer- grained record level, run accounting under the worst-case assumption that the attacked node always exposes the same single record (this corresponds to (T. }-participation for all nodes). This ensures that our guarantees are computed the same user level, leading to a fair comparison.
Note that the accounting does not depend on the choice of learning model or dataset. Rather, it is determined by the participation scheme, the number of epochs, the clipping parameter, and the noise scale, but also on the communication graph through the gossip matrix, as PNDP provides privacy guarantees that are specific each pair of nodes. We thus consider several graphs that correspond to plausible real-world scenarios:
ErdössRénny graphs: generated randomly with 100 nodes and parameter p = 0.2, ensuring that each generated graph is strongly connected. These graphs have expander properties and can be generated in a distributed fashion.
Facebook Ego graph (Leskovec & Mcauley 2012): corresponds to the graph of fixed Facebook user (omitted from the graph). where nodes are the user's friends and edges represent friendships between them. This graph has 148 nodes.
PeerTube graph (Damie & Cyffers 2026]; an example of decentralized social platform. PeerTube is an open-source decentralized alternative to YouTube. Each node represents a PeerTTbee server and edges encode follow relationships between servers, allowing videos across instances. The graph, restricted to its largest connected component, has 271 nodes.
to watch recommended
Florentine Families (Breiger & Pattison 1986): a historical graph with 15 nodes describing mar- ital relations between families in 15th-century Florence.
Results are shown in Figure 2 For all graphs, our accounting is significantly tighter for all possible distances between nodes. In particular, while the PNDP accounting Cyffers al. (2022) provides no improvement over LDP guarantees for nodes at distances less than or equal to 2, our method already achieves significant uains-up an order of magnitude. The improvement is even larger, with reductions of at least two orders of magnitude at distances greater than or equal to 3. The gains are consistent across all the considered graphs, demonstrating the versatility of our method, which leverages both the topology and the correlations induced between nodes.
7.2 MAFALDA-SGD
We now illustrate the performance of MAFALDA-SGD under LDP and compare it with three base- lines: non-private D-SGD, AntiPGD defined in Appendix A and standard DP-D-SGD without noise correlation between nodes. Results on the Facebook Ego graph are shown in Figure 3 with We
additional results for other privacy levels and graphs reported in Appendix for all the algorithms to provide fair comparison and because it is the tightest accounting available.
accounting
We study regression task on the Housing dataset | which has 8 features and 20,640 data points, with the goal of predicting house prices based on demographic and housing features. In all experi- ments, we use simple multilayer perceptron (MLP) with one hidden layer of width 64 and ReLU activation, followed by linear output layer for regression, trained with the mean-square eтror loss. This dataset has been used in several related works (Cyffers et al. 2022 Li al., 2025). In all experiments, we cycle over the data points such that each of them participates 20 times in total, with participation every 19 steps. These numbers were chosen for memory constraints and not optimized. This cyclic participation corresponds to (kc, ba-participation scheme with h 20 and b = 19 in the matrix factorization literature (Choquette-Chnee Chho et al. 2023).
Our algorithm MAFALDA-SGD outperforms all private baselines across all privacy regimes by large margin. For a fixed privacy budget e, MAFALDA-SGD achieves a 31% average improvement in test loss in the last 50 training steps, while for fixed test-loss value of 0. 75, it achieves a 2-fold reduction in e. These results illustrate the importance of correlated noise for the performance of differentially private decentralized algorithms. Additional experiments confirm that this superiority holds regardless of the graph topology. In particular, under small privacy budgets, there exist regimes where MAFALDA-SGD converges while competitors diverge (e.g., AntiPGD in Figure 3..
https:: www. http://wwwwpppmm/.///////// wtt.:/ppemmmoor///////00/00

---

Published as a conference paper at ICLR 2026
4.0
Univised hanlize DF-D-SCD
ANTIEGD
Unzoderd
SAAALDAASG (Oun)
33
ANTIPO
3.0
Finol Test Loss
MAPALDA SGD (Qun))
2.5
1.0
0.5
1.0
0.0
Stop
Figure 3: Comparison of MAFALDA-SGD with the non-private baseline, AntiPGD, and standard DP-SGD under local differential privacy on the Housing dataset with the Facebook Ego graph. Left: test loss over time (AntiPGD does not appear because the test loss always greater than 6), averaged over 20 runs. Right: final test loss as function of the LDP privacy budget, averaged over 20 runs. In both cases, data points are distributed uniformly at random across nodes.
Finel Tet. Acsuray
MAPALLAASD
ANMPPN
MAPMENW SCB (Ows)
Figure 4: FEMNIST classification results on the Facebook Ego graph. Left: test accuracy evolution for fixed privacy budget. Right: privacy-utility tradeoff between the final test accuracy as function of the LDP privacy budget. Error bands show 95% confidence intervals.
We also evaluate MAFALDA-SGD on the federated EMNIST (FEMNIST) image classification task from the LEAF benchmark (Caldas et al. 2018), predicting handwritten characters across users. This setting is highly non-iid and realistic for decentralized learning. To ensure enough data is present, each node is given 10 unique handwriting styles training data. We use small convolutional network comprising two convolutional layers (16 and 32 filters, x kernels) with ReLU and x max-pooling, followed by group normalization and fully-connected layer for softmax output trained with cross-entropy. Training uses cyclic participation scheme ((k, b) = (20, 16)).
We compare MAFALDA-SGI) runs) are reported in Figure 4 Across all privacy budgets, MAFALDA-SGD consistently achieves higher test accuracy than the private baselines, with the largest relative gains at high privacy levels where correlated noise preserves utility while satisfying LDP.
baselines under local DP accounting. Results (averaged
20
CONCLUSION
In this work, we establish new connection between two separate research directions by extend- ing the matrix factorization mechanism from the well-studied centralized DP-SGD differentially private decentralized learning. This required generalizing known results in matrix factorization to broader classes of matrices, which may also prove useful in other contexts. Our framework is flexi- ble enough to capture both algorithms and trust models, while providing tighter privacy guarantees than prior analyses. also enables the design of new algorithms, as illustrated by MAFALDA-SGD. which outperforms existing approaches. Overall, framework lays the foundation for more prin- cipled design private decentralized algorithms and enhances the practicality of grivacy-presenvee machine learning in decentralized settings.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported by grant ANR-20-CE211 0002 IPOP (Interdisciplinary Project on Privacy) project of the Cybersecurity PEPR and by the Aus- trian Science Fund (FWF) [10.55776/COE2). This research was supported part by the Groupe La Poste, sponsor of the Inria Foundation, in the framework of the FedMalin Inria Challenge. This project was provided with computing AI and storage resources by GENCI at IDRIS thanks to the grant 2025-AD01 1015352RI on the supercomputer Jean Zay's s V100 partition. Experiments pre- sented in this paper were also carried out using the Grid 5000 testhed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities well as other organizations (see tttps:: / www. gr grid5000.fry The authors thank Quino for his comic strip Mafalda which inspired our new algorithm name.
(Project PRIDE) and the ANR 22-
REPRODUCIBILITY
We provide an open-source implementation of the code used in this work, publicly available uthttps://githe com http://coooommmmmmm......m aimiarbre//FDD
REFERENCES
Youssef Allouah, Anastasia Koloskova, Aymane El Firdoussi, Martin Jaggi, and Rachid Guerraoui. The privacy power of correlated noise in decentralized learning. In International Conference Machine Learning (ICML), volume 235 of ICML'24 '4, Vienna, Austria, July 2024. JMLR.org.
Aurélien Bellet, Rachid Guerraoui, Mahsa Taziki, and Mare Tommasi. Personalized and Private Peer-to-Peer Machine Learning. In Conference Uncertainty in Artificial Intelligence (AIS- TATS). PMIR, March 2018
Enrique Tomás Martínez Beltrán, Mario Quiles Pérez, Pedro Miguel Sánchez Sánchez, Sergio López Bernal, Gérôme Bovet, Manuel Gil Pérez, Gregorio Martínez Pérez, and Alherto Huertas Celdrán. Decentralized federated learning: Fundamentals, state-of-the-art, frameworks, trends, and chal- lenges, 2022.
Sayan Biswas, Davide Frey, Romaric Gaudel, Anne-Marie Kermarrec, Dimitri Lerévérend, Rafael Pires, Rishi Sharma, and François Taiani. Low-Cost Srivacy-Preservinn Decentralized Learning. Proceedings on Privacy Enhancing Technologies, 2025(3), 2025. ISSN 2299-0984.
Ronald L. Breiger and Philippa Pattison. Cumulated social roles: The duality of persons and their algebras. Social Networks, 8(3), September 1986. ISSN 0378-8733.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint 1111::1112.01097, 2018.
T-H. Hubert Chan, Elaine Shi, and Dawn Song. Optimal Lower Bound for Differentially Private Multi-party Aggregation. In Algorithms ESA 2012, Berlin, Heidelberg, 2012. Springer. ISBN 978-3-642-33000-2.
Hsin-Pai Cheng, Patrick Yu, Haojing Hu, Syed Zawad, Feng Yan, Shiyu Li, Hai Li. and Yiran Chen. Towards decentralized deep learning with differential privacy. In Cloud Computing CLOUD 2019, Cham, 2019. Springer International Publishing. ISBN 978-3-030-23502-4
Christopher A. Choquette-Choo, Krishnamurthy Dvijotham, Krishna Pillutla, Arun Ganesh, Thomas Steinke, and Abhradeep Thakurta. Correlated Noise Provably Beats Independent Noise for Dif- ferentially Private Learning, October 2023.
Christopher A. Choquette- Choou, Arun Ganesh, Ryan McKenna, H. Brendan McMahan, John Rush, Abhradeep Guha Thakurta, and Zheng Xu. (amplified) banded matrix factorization: A unified approach to private training. In Conference on Neural Information Processing Systems (NeurIPS), volume 36. Curran Associates, Inc., 2023.

---

Published as a conference paper at ICLR 2026
Christopher A. Choquette- Choquette-Choo. Hugh Brendan Memahan, J. Keith Rush, and Abhradeep Guha Thakurta. Multi- Epoch Matrix Factorization Mechanisms for Private Machine Learning. In In- ternational Conference on Machine Learning (ICML). PMLR, July 2023.
Edwige Cyffers and Aurélien Bellet. Privacy Amplification by Decentralization. In Conference on Uncertainty in Artificial Intelligence (AISTATS), Virtual, Spain, 2022.
Edwige Cyffers, Mathieu Even, Aurélien Bellet, and Laurent Massoulié. Muffliato: Peer-to-Pece Privacy Amplification for Decentralized Optimization and Averaging. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
Edwige Cyffers, Aurélien Bellet, and Jalaj Upadhyay. Differentially private decentralized learning with random walks. In International Conference on Machine Learning, pp. 9762-9783. PMLR, 2024.
Mare Damie and Edwige Cyffers. Fedivertex: a Graph Dataset based on Decentralized Social Media. In wwW '26 ACM Web Conference 2026, Dubai, United Arab Emirates, April 2026. doi: 10.1145/3774900337788888
Sergey Denisov, H. Brendan McMahan, John Rush, Adam Smith, and Abhradeep Guha Thakurta. Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams. Advances Neural Information Processing Systems, 35, December 2022.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series (Statistical Methodology), 84(1), 2022.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Berlin, Germany, 2006. Springer Berlin Heidelberg. ISBN 978-3-540-32732-55
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proceedings of the Forty-Second ACM Symposium on Theory of Com- puting, STOC '00 New York, NY, USA, 2010. Association for Computing Machinery. ISBN 9781450300506.
Abdellah Mrini, Edwige Cyffers, and Aurélien Bellet. Privacy attacks in decentralized learning. In International Conference on Machine Learning (ICML), ICML'24. JMLR .org 2024.
M. Gil, F. Alajaji, and T. Linder. Rényi divergence measures for commonly used univariate contin- uous distributions. Information Sciences, 249, November 2013. ISSN 00200255.
Nirupam Gupta, Jonathan Katz, and Nikhil Chopra. Information- privacy in distributed
average consensus, 2020.
Harold Henderson and S. R. Searle, The vec-permutation matrix, the vec operator and Kronecker products: A review. Linear and Multilinear Algebra, 9(),, January 1981. ISSN 0308-1087.
Zhenqi Huang, Sayan Mitra, and Nitin Vaidya. Differentially private distributed optimization. In Proceedings of the 16th International Conference Distributed Computing and Network- ing, ICDCN '1, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450329286..
Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Workshop Computational Learning Theory (COLT), volume 23 of Proceedings of Machine Learning Research, Edinburgh, Scotland, 25-27 Jun 2012. PMLR
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) leariing without sampling or shuffling, 2021a.
Peter Kairouz, Brendan Memahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and Private (Deep) Learning Without Sampling or Shuffling. In International Conference Machine Learning (ICML). PMLR, July 2021b.
12

---

Published as a conference paper at ICLR 2026
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D' D'Oliveira, Hubert Eichner, Salim El Rouayheb. David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, 7aid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateck Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends& Machine Leurning, 14 (1-2), 2021c. ISSN 1935-8237.
Joshi,
Nikita Kalinin and Christoph H Lampert. Banded square root matrix factorization for differentially private model training. Advances in Neural Information Processing Systems, 37, 2024.
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
Anastasia Koloskova, Nicolas Loizou, Sadra Boreini, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. In International Confer- ence on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research. PMLR, 13-18 Jul 2020.
Anastasia Koloskova, Ryan McKenna, Zachary Charles, J. Keith Rush, and Hugh Brendan McMa- han. Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy. In Conference on Neural Information Processing Systems (NeurIPS), November 2023,
Antti Koskela and Tejas Kulkarni. Differential Privacy Analysis of Decentralized Gossip Averaging under Varying Threat Models, May 2025.
Jure Leskovec and Julian Mcauley. Learning to discover social circles in Ego networks. In F. Pereira, C.J. Burges, Bottou, and K.Q. Weinberger (eds.). Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
Xiang Li, Chendi Wang, Buxin Su, Qi Long, and Weijie Su. Mitigating the privacy-utility trade-off in decentralized federated learning via f-differential privacy. In Conference on Neural Informa- tion Processing Systems (NeurIPS), 2025. Poster 117431, NeurIPS.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In Conference on Neural Information Processing Systems (NeurIPS), 2017.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochas- tic gradient descent. In International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research. PMLR, 10-15 Jul 2018.
Charles Van Loan. The ubiquitous Kronecker product. Journal of Computational and Applied Mathematics, 123(1), November 2000. ISSN 0377-0427.
Yilin Mo and Richard M. Murray. Privacy preserving average consensus. IEEE Transactions on Automatic Control, 62(2), February 2017. ISSN 1558-2523.
Dario Pasquini, Mathilde Raynal, and Carmela Troncoso. On the (In)security of Peer-to-Peer De- centralized Machine Learning. In 2023 IEEE Symposium on Security and Privacy (SP). IEEE Computer Society, May 2023. ISBN 978-1-66549-336-3
Krishna Pillutla, Jalaj Upadhyay, Christopher A. Choquette-Churn Krishnamurthy Dvijotham, Arun Ganesh, Monika Henzinger, Jonathan Katz, Ryan McKenna, H. Brendan McMahan, Keith Rush, Thomas Steinke, and Abhradcep Thakurta. Correlated noise mechanisms for differentially private learning, 2025.
13

---

Published as a conference paper at ICLR 2026
César Sabater, Aurélien Bellet, and Jan Ramon. An accurate, scalable and verifiable protocol for federated differentially private averaging. Machine Learning, 111(11), November 2022. ISSN 1573-0565.
Youliang Tian, Shuai Wang, Jinbo Xiong, Renwan Bi, Zhou Zhou, and Md Zakirul Alam Bhuiyan. decentralized deep federated learning training: Focusing digital
Robust and healthcare applications. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2023.
Lloyd N. Trefethen. Numerical Linear Algebra. Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6. Philadelphia, PA 19104), Philadelphia, Pa, 1997. ISBN 778-0-89871-361- 978-0-89871-957-42
Shaowei Wang, Liusheng Huang, Miaomiao Tian, Wei Yang, Hongli Xu, and Hansong Guo. Per- Data Aggregation for Histogram Estimation. In 2015 IEEE Global Communications Conference (GLOBECOM), December 2015.
sonalized
Liangqi Yuan, Ziran Wang, Lichao Sun, Philip S. Yu, and Christopher G. Brinton. Decentralized Federated Learning: A Survey and Perspective. IEEE Internet of Things Journal, 11(21)33417- 34638, November 2024. ISSN 2327-4662. doi: 10. 10.1109// 109/0100..02444444011
Symbol
Usage
Source
V
Set of nodes participating in the training
Number of nodes in the training
d
Model size
Learning rate
T
time i ranges from to
Number of observations made by the attacker
0
A model during the training
W
Gossip matrix
W
Decentralized learning workload
Figure
CT
Transpose of matrix C.
C
Moore-Penrose pseudo-invers inverse of matrix
Kronecker product
II
Participation scheme
D.
Dalaset some node u
Table List of symbols used this work
A SOTA DP-DL APPROACHES AS MATRIX FACTORIZATION MECHANISMS
In this section, we prove Theorem by looking at algorithms one by one. But first, we explain the strategy used to get the factorization, and we present useful Lemma.
A.1 PATH TO MATRIX FACTORIZATION MECHANISMS
For each setting, the proof of Theorem follows two-step strategy:
1. list observed messages, known gradients, and known noise, and derive the corresponding matrices A and B;
2. (if necessary) remove the impact of the known gradients from matrix A (apply Lemmal 14
Apart from LDP, the second step is mandatory to recover a proper factorization. Indeed, if one considers a Linear DL algorithm and an attacker knowledge O = AG + BZ such that A
K
B
and B = Then, no matrix C such that A = BC', as would imply that KG OC.
14

---

Published as a conference paper at ICLR 2026
However, by following the cleaning strategy given by Lemma 14 obtain second reduced view, O^ = AG + BZ, such that À = BC can exist.
Lemma 14 (Attacker-knowl knowledge reduction). Let O = AG + BZ be the attacker knowledge of a trust model on a Linear DL algorithm, such that the attacker aware of some linear combina- tions of gradients (without noise). Without loss of generality, let assume A [A] KG and B = [BT 0] where none of B's rows are null. If we define = A(I - KG), then the GDP guarantees of the allacker knowledge O are the same as the one of the attacker-knolledg reduction O AG BZ.
Proof.
AG + BZ BZ 1 (O G+ A xG)
G+
(13)
Á Á(I A[I-KGtKO
= AAKo -AKKI(KCG) +
G+
(14)
KG (1 KGl KGlKK.
A(1 kol kG'K())
= =AK G) +
G+ BZ
(15)
0
= Ak G)* +
M
(1 (1- (1-kotp Kg
)0)
G+ G+BZ BZ
(16)
00]
= AK (K + ÄG + BZ
(17)
(18)
Then, as the attacker knows KGG, the GDP properties of AG + BZ are the same as those of ÅG BZ, which concludes the proof.
A.2 PROOF OF THEOREM 6 FOR DP-D-SGD
In this section, we make explicit the factorization of Theorem for the DP-SGD algorithm, where all noises are independent, under the different trust models.
LDP
With LDP, the attacker has only access to messages, therefore, no reduction is needed, and analyze the factorization the messages directly. We have CDR-SGD = IaT, yielding ADP-D-SD = BpP S.D WT.
PNDP PNDP considers a A of attacker nodes. Each attacker observes
the messages receives,
its own gradients,
its own noise,
the messages it emits (which is a linear combination of previous information, will omit it).
To ease the proof, without loss of generality, reorder G and Z. such that their first lines correspond to the attackers' gradients and noise.
Define KS as:
K S
IT &8 K,A
(19)
PNDP
where KAli,, [ = for [L, Al. where I'A = UnE I' represents the (ordered) list of
neighbors of A. KPNDe thus projects the set of all messages onto the set messages received by A. Denote the number of attackers, and b the total number of their neighbors.
15

---

Published as a conference paper at ICLR 2026
Then, the attacker knowledge is
(K& PNDP Wr)
PNDP W
OT
0
G+
0
0
7,
0
LOT
where Rn7xx After reduction, it becomes
(K S
WT) PNDP
(KPs S
W
0
0
G+
0 LaT
Z.
Inn-ay
OaTxaT
OaTx(a-a)I
Hence A
which concludes the proof for PNDP setting.
A.3 PROOF OF THEOREM 6 ANTI-PGD
In this section, we make explicit the factorization of Theorem 0 for the AntiPGD algorithm, which was studied Koloskova al. (2023).
LDP Following the factorization found in centralized setting Koloskova et al.
2023 we have
CAN 1,z6 I, PANTLPGD Wr and:
J
W W In
T
0
BANT-PGD
WT (W 1.)
W In)
Ind
This notation shows how noise cancellation propagated and lagging one step behind terms of communication.
PNDP PNDP considers a set A attacker nodes. ease the proof, without loss generality, we reorder G and Z such that their first lines correspond to the attackers gradients and noise.
Define SND as the projection of messages onto the set messages received by A. Denote the number of attackers, and the total number of their neighbors.
An alternative expression of messages in ANTI-PGD WT (G DZ), where D is the invertible
0
lower-triangular matrix
-1
1
0
Then, the attacker knowledge is
K PNDP
WT)
(KS
Wr
L&T
G
0
0
Z,
lOT
where Z Rndxx After reduction, it becomes
(KS
Wr)
(KS ANDD
WrD)
0
0
G+
O
0
Z.
0
[(n-a)T]
Lar
OaTxaT
(aTx(a-a)T ((n-a)r
Hence A = BD-1
which concludes the proof for PNDP setting.
0 Onn-o)TxaT
A.4 PROOF OF THEOREM 6 FOR MUFFLIATO-SGD
In this section, we make explicit the factorization of Theorem 6 for the Muffliato algorithm, which was studied in Cyffers et al. (2022).
16

---

Published as a conference paper at ICLR 2026
LDP Muffliato-SGi Cyfferr et al. 2022 requires a different communication workload than Wi- That is because they consider multiple communication rounds before computing new gradient. For- mally, they define K the number of communication steps between two gradients, and they perform iterations. This means that the set of messages shared is:
In [Kaxn]]
1)
)(G++ (G+ 2).
O MuDD W KT
1
We see here that MuffliatoSSGD adds uncorrelated local noises (Ct InT). and thus we have SMfflino-SGD = INT, as well as AMuffian-SGD SMff = WT IT @
In
0 O(K-1)xn
PNDP For MufllattoSGDD(K) we assume T KT", where T is the number of gradient descent, and has communication rounds between each gradient descent.
PNDP considers a set A of attacker nodes. To case the proof, without loss of generality, we reorder and Z such that their first lines correspond to the attackers gradients and noise.
Define KENDP as the projection of all messages onto the set of messages received by A. Denote the number of attackers, and the total number of their neighbors.
Then, the attacker knowledge is
K
PNDP- AMufliato-SGD
S PNDP
K
S PNDP Mufflinto-SD)
La.
0
G+
Z,
0
LTT
0
where RRl''dd After reduction, it becomes
(KS (Ky AMuttiaco-SGD
G+
0
7.
[(n-ajr
0
LaT
0
OaTxaT
OaTx(n-ar7) [nn-aTT
Hence A = (n-a)Txx
which concludes the proof for PNDP setting.
Note that while the formulation is similar the proof for DP-D-SGD, the workload matrix here has K times more rows.
A.5 PROOF OF THEOREM 6 FOR DECOR
In this section, make explicit the factorization of Theorem for the DECOR algorithm, which was studied in Allouah et al. (2024).
First, let provide the correlation matrix used in DECOR CDECOR Correlation is performed edge- wise in the graph, as each neighbor adds a noise correlated with their neighbors to their local noise. Consider arbitrary orientation E of edges & of the symmetric graph G. The correlation matrix has the following structure:
CDECOR = IT @ [In Citndee'' 1
1 if Elel (i.j)
Ve [F [1,n] Cioodesi,,
- 1 Efe (j.i)
otherwise
where the first part of [ww Ct| corresponds to the local private noise, and the second part to the "secrets". Interestingly. multiple correlation matrices (and thus equivalent factorizations) exist for DECOR, as there are multiple ways to generate possible orientations of the edges of the graph G.
LDP The messages exchanged by DECOR take the form Wr (G CbECOR
7). Hence =
W,, B WT [hr Ct]. and = B [rr
which concludes the proof for LDP setting.
17

---

Published as a conference paper at ICLR 2026
PNDP With DECOR, each node knows of the noises of its neighbors. Therefore, Sec-LDP is more appropriate to describe the knowledge gathered by some attackers.
Sec-LDP Let consider set A of attacker nodes. To case the proof, without loss of generality, we reorder G such that its first lines correspond to the attackers gradients. For Z, we first gather the local noise of the attackers, then other local noises, and finally the "secrets" noise.
Define PNDD as the projection of all messages onto the set messages received by A. Denote the number of attackers.
Then, the attacker knowledge is
K PNDP WT
K
PNDP WT
T
LTT
DI]
LT
G+
0
Z,
LaT 0
0
0
E
where Z RnTxd and D the correlation matrix of secrets and subpart E. After reduction, it becomes
KPNDP WT 0
K$
PNDP
WT
LAT
DI]
0
O
G+
0
0
[(n-a)T]
lar
0
0
0
E
OaT
(n-x(T=
Hence A = B
xyT
((n-a) (nx(n-a)T
where b is the number of columns of Dt, which
ObxaT
concludes the proof for PNDP setting.
Note that while the formulation is similar to the proof for DP-D-SGD, the workload matrix here has K times more rows.
A.6 PROOF OF THEBREM 6 ZIP-DL
In this section, we make explicit the factorization of Theorem was introduced in Biswas et al. (2025).
6 for the Zip-DL algorithm, which
Zip-DL. considers message-wise noises, with one noise per message sent between nodes. For each node i, let , be its set of neighbors. Define 8; T the number of messages sent by i and Σn -i=1= 5; the total number of messages.
Zip-DL is already expressed under matrix form (Biswas et al. 2025); by introducing n² virtual nodes, and translating to express the gossip matrix W under this virtual equivalent W e 1." xxx encode messages. Formally, we have W [ni+j++, mj++++] W[i.z]. Furthermore, considering
an averaging matrix M, and a correlation matrix Ct Dip-Dr. (coined Ö in Biswas et al. (2025)) ). Zip-DL. can be expressed as:
B.+1 MW (In G.) CL
(20)
We can now define the messages shared on the network, and viewed by an LDP attacker A:
O^ = -W ((NT 8 G (Ir @ Chi..1) 2),
(21)
In2
0
0
MW
1
Wr = (Tr & Ins)
(22)
T-1
T
MW
MW
I,a
where I,2 is a diagonal matrix filled with zeros except for I, [ri + 1, + Tr. Intuitively, MW corresponds to round of averaging. This is typically very sparse matrix, even more so because many lines will be zero when considering communication graphs that are not the complete graph.
18

---

Published as a conference paper at ICLR 2026
WT (Knr @ 1n). B Wr @ 1n) (Ir @ C Capor): and C' (Ir @ CZIp-DL) concludes the proof for Zip-DL algorithm.
LDP A =
PNDP For the ease of notation, we assume here that for any node i, = The generalization straightforward. To ease the proof, without loss of generality, we reorder and Z such that their first lines correspond the attackers gradients and noise.
We denote A the set of attacker nodes, and assume for simplicity there only one such attacker node (extension to more simply requires doing this decomposition multiple times, extending the projection matrices). Denote KNDD E ReTxxnTT the matrix selecting the messages received by A.
The PNDP attacker knowledge is therefore
( (K WT) (Ir 0 01xe-1)) 1))
K WT)
K$ 0
0
(La & 1.)++
0
Z,
LeT 0
where Rnnexx After reduction, it becomes
KeNDP Wr)
( W
KS
(1 ( 2 1.)
a+
0
0
Z.
LeT 0
Hence A B OxTxeT
(n- 1(n-177 &
which concludes the proof for Zip-DI. algorithm.
( (ee-
A.7 EXTENDING NOTATIONS TO VARYING GOSSIP
We extend the notations introduced in Section 4.1 to time-varying graphs encoded as sequence of gossip matrices Wi, for & [1, 7]. In this more general context, the workload matrix W becomes:
In
0
0
Wi
In
0
W
W₂
I
W W
W.
TT3
- W
This new definition of WT encodes how messages spread through time using the sequence of gossip matrices (Wi).. The formalization of the MF-D-SGD algorithm (initially presented in Equation (5) similarly needs adapting by replacing Ir @ by block diagonal matrix of all W,:
Wi
0
0
0
W2
0
0
=
(MBu (M
(23)
0
Wr
B PROOF OF THBOREM g
Proof. (of Theorem
We denote M M'' two mechanisms that have the same 4-GDP properties. In this proof, this will either be because they are distributionally equivalent, or because they are an invertible operation away from each other (meaning they have the same μ-GDP properties by post-processing)
19

---

Published as a conference paper at ICLR 2026
We start by proving the following equivalences:
M:G. + B(CG Z)
= =M (CG + 2)
> with B' E (Brnk(())m and B'C an echelon matrix
= :M2:C. G + [LO] (QCG 2)
> with B' = [L Q the LQ decomposition of B'
= M3 G (ÔCG + 2)
with Q (resp. Z) the first rank (B') rows of Q (resp. 2)
Then, since M3 can operate in the continual release model, those privacy guarantees will transfer back to M.
Algorithm Rows Selection for Matrix
Require: Matrix B E leaxb
1:
Selected rows (empty matrix)
2: P
3: for = 1 to a do
4: if' Bpg is not linear combination of rows in R then
R
5:
R
B 01
6:
P
Ey E I2 selects line of BC
7: return P
Proof that M = MM1 Let P be a projection matrix selecting rank(B) rows of B, in the original order, and such that rank(PB) rank B). P can be obtained through Algorithm 3 Denote B' the matrix PB. By design, B' is full-rank, B' E xran raakk (Bk) = rank B) m, and B'C is echelon matrix.
Denote S the rows of B not B'. By design, they are linear combinations rows of B', meaning there exists matrix D such that S = DB'.
As S is the complement of B', there exists a permutation matrix æ such that
B S
B'
Irank B
B
B'. D
DB
and finally M = Trank B D
Mi.
As also M₁ = PM, by applying post-proccen processin in both directions, we have M MM.
Proof of M1 = M2 Consider an LQ decooooopoiiionn of B' since rank B') = rank( (B) S m can find decomposition B' = LL 0] Q such that L E grank(B (B' )xrank(B')) is lower triangular and Q mm is an orthonormal matrix Trefethen (997). Then, (G) = 5L 0) (QCG+ QZ) for any G. Since Q is orthonormal matrix, this is distributionally equivalent to M2-
Proof of M2 Ms: in M2 has been constructed be square and lower triangular matrix of full rank (as B' is of full rank). Thus, L is invertible. This means, by post-processing using an invertible operator that the privacy guarantees of M2 are the one of [frank(B') 0] (QCG + Z). It suffices to name Q = [/rank(B')
0] Q and Ž = [rrnn((B)) 0] Z to see this corresponds to M3-
Proof of 1-GDP of Ms: M3 is an instance of the Gaussian mechanism on QCG. Since N' (0 (aakk)) "aak(B")xx xd this mechanism is L-GDP i (QC)) Additionally, we have PA BCC = LÂC. Then, QC = L- PAA, which implies that QC' is lower echelon (by design of P and T.). Therefore, for the same value of v, M3 remains !-GDP when considering adaptive gradients.
20

---

Published as a conference paper at ICLR 2026
Note that
scns(QCC=
max G=nG'
(G-
(24)
11
(IC(G- ((C(G-G)) (C
max GenC'
(25)
( - G')) BtBC (G G²)
max G=nG'
(26)
max ||C (G- Bt
(27)
GznG'
senss(C; B);
(28)
where Equation 26 stands as the rows of Q and B span the same space.
Then, applying Lemma 3.15 of Pillutla al. 2025) allows to derive the following bound:
sens(C; B) sens (C)
max TEll
((Oc)
QC
(29)
11
E (TTQTOC)
< max
(30)
xell
max Rell
(CT B" S.
(31)
max REll B
Σ
(CT (CTBBCC)
8.1
(32)
where Equation 22 corresponds to Part (a) of Lemma 3.15 in Pillutla et al. (2025) (generalization
to batch releases). We also have equality when the ((oc) II).
T QC)
[t. r] > 0 for all t, T E m, for all
C ADDITIONAL EXPERIMENTS
In this section, we provide missing experimental details and results from Section
7
C.I HOUSING PRIVACY-UTILITY TRADEOFF
We simulate all baselines on the Housing dataset for various values a. We display their utility privacy tradeoff, by considering the utility as function of for (e, 1e -)-DP privacy guarantec. Figure 5 reports the resulting privacy budget. For all graphs, the privacy-utility tradeoff offered by MAFALDA-SGD improves upon that of the existing literature.
Smaller graphs only yield better privacy/utility tradeoffs because data is partitioned into bigger batches smaller graphs, there is more data for each node, netting better privacy properties.
C.2 FEMNIST PRIVACY-UTILITY TRADEOFF
We also include F present the privacy-utility tradeoff's for the FEMNIST dataset on the Flo- rentine families graph and the Facebook Ego graph. In both cases, better test accuracy is consistently reached by MAFALDA-SGD for different values of
D PROOF OF LEMMA 12
In this section we present the proof of Lemma 12 which is used in Section to justify Algorithm ?
21

---

Published as a conference paper at ICLR 2026
Untared DINDASG
Untaaeed
3,
DRAD-SCD
ANTIECI
ANTIECI
Finni Test. Loss
3.0
MAPALDA-SGU (Uuss
Finel Test Loss
8.0
MAPALDA SGB (Uhss)
2.0
2.0
1.6
1.0
0.5
10
0.
Florentine Families
Facebook Ego graph
Unuraed loaeline
Unnoaedd looeline
3.5
DPDDSGD
35
DPAD
SGR (Dues)
ANTIFGI
Finsl Tost. Loss
3.0
Find Test Loss
5.0
MAPALDA D-DG (Uis)
2.0
2.0
1.5
1.0
0.5
10
05
107
Peertube
Misskey
Figure 5: Privacy-utility tradeoff on the housing dataset for various graphs.
1.7
0.
Final Test Accureyy
Final Test Accursey
0.5
0.0
Unndted
Unaooed beseliee
ANTIPGO
ANTIPGI
0.3
0.3
MAPALDA-SGD (Oies)
11
0.1
Florentine Families
Facebook Ego graph
Figure 6: Privacy-utility tradeoff on the FEMNIST dataset for various graphs.
22

---

Published as a conference paper at ICLR 2026
Proof. (Lemma
Consider local correlation and PA = LnT. Then, the optimization loss of Equation becomes:
(Ir @ W) WT (Clomaa In l
Copti (W1: Clocat) sons(Crocall Thaa
(33)
This follows from the property of the Phoor-Peenrose pseudoinverse: (Clocal @ I,) = Clanal @ In.
well as the fact that sensn (Ciocal InT; B) sen (Crocal) under localized participation scheme II that is identical for all nodes.
As highlighted in Loan (2000). the commutation matrix K(TT)) (also called the vec-permutationn matrix Henderson & Searle (1981)) is way to change the representation from stacking through time the observations of the global system stacking the observations locally of each node through time. In other words, for any matrix X Ruxn Y E I xI' we have:
K in. T) (X (Y X K (T.)
It suffices to focus on the norm, since the sensitivity term remains unchanged. Let A (Ir @ W) W(n,(, First, note that ((T,n) is permutation matrix, so we have:
( W) WT (Clocas @ 1n)
|| @ W) WT (Clorat @ In) K (())))
|| & W) WrK((T)
(In 8 Clocal)
||A (4n clooma) l|
tr (IA (In @ Clocai)) A (In @ Ciooat)
If we consider A; = Ap.raT(+1--1) then A A 8 Ciocal) = [AeCt when considering the trace, the product will only focus on the blocks for given node and there are no cross-terms:
An Atorat: Thus,
1n) tr [ & W) Wr (Clocat 2 1n))
(A,Clocat) T AcCiocal
tr Toornt A, A,Crocal
tr Cooat
Σ E.TA,
Crocat
Taking L such that LTL= = Ei= AT A, using the Cholesky decomposition yields the desired result.
23


Reviews:
[{"review_id": "8Csa8nYmk9", "reviewer": "Reviewer_dv87", "summary": "This is an interesting paper that addresses differentially private (DP) decentralized learning (DL) by generalizing recent advances in centralized DP. In particular, it achieves privacy be means of correlated noise through the matrix factorization mechanism which is shown to apply also in decentralized settings. The proposed framework is applicable for different trust models, e.g., Local DP, Pairwise Network DP, and Secret-based LDP, providing tighter privacy guarantees and covering all known DP-DL algorithms under a single formulation.", "questions": "1) How restrictive is Definition 3? For example, it seems to roll out adaptive optimization like ADAM, quantization techniques, personalization (often achieved via regularization) etc. \n\n2) In section 6, when defining MAFALDA-SGD, the authors assume that all nodes follow the same local participation pattern. This assumption seem to rule out dynamic topologies that are, in fact, prevalent in DL settings. For example within potential space applications or where nodes may exhibit dropout.\na) Is this assumption necessary for MAFALDA?\nb) How does this assumption limit the applicability of MAFALDA?\nc) Is the framework applicable to dynamic graphs?\n\n3) Can the authors provide an analysis of the complexity of the approach? Is the framework applicable in realistic scenarios?\n\n4) Algorithm 1 and 2 requires that each node has access to $W$, $\\Delta_g$, and $\\sigma$.\na) Why is it reasonable for each node to have access to the entire topology?\nb) How would $\\Delta_g$ be decided in practice? If all nodes must use the same value, it requires coordination that will add to the complexity. How does data heterogeneity among nodes play a role?\n\n5) It would be interesting to see more holistic experiments including i) more realistic settings with larger models, ii) the effect of graph topology, and larger graphs.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Extends the centralized matrix factorization mechanism to decentralized learning, unifying several existing trust models (LDP, PNDP, SecLDP) and encompassing all known DP-DL algorithms within one framework.\n\n- Generalizes DP analysis to adaptive and non-square workload matrices through Theorem 7, enabling rigorous privacy guarantees for realistic decentralized and potentially other distributed systems.\n\n- Introduces a novel algorithm (MAFALDA-SGD) that optimizes local noise correlation, achieving tighter privacy accounting and better privacy–utility trade-offs than previous methods.\n\n- Empirically validated on multiple graph topologies and datasets, showing consistent performance gains and more accurate privacy bounds compared with prior accounting techniques.", "weaknesses": "- The experimental section only include small graphs (the largest including only 271 nodes). Moreover, the models considered in section 7.2 is very small, an MLP with a single hidden layer. \n\n- There are no ablations on the effect of graph topology, participation patterns, or colluding attackers. \n\n- There is no complexity analysis of the new algorithm. \n\n- It is not clear how restrictive definition 3 is.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VTR4Z2qDpY", "reviewer": "Reviewer_6ixT", "summary": "The paper builds a unified privacy-accounting framework for decentralized learning (DL) by recasting DL updates as a Matrix Factorization (MF) mechanism. The paper extends centralized MF-style DP accounting to decentralized settings and multiple trust models. This achives tighter guarantees (especially under PNDP) and motivates a new algorithm, Mafalda-SGD, with optimized, node-wise correlated noise that outperforms prior DP-DL baselines on synthetic and real graphs.", "questions": "1. The theory assumes linear DL where \"all observable quantities can be expressed as a linear combination of the concatenated gradients G and the concatenated noise Z.\" This is often not true in practice. For example, in practice, quantization or compression is often used when exchanging information, which would render them non-linear. Also, if cryptographic techniques are further used to encrypt the weights or to perform secure aggregation, the weights/gradients will usually be converted into a discrete space.\n2. In practice, how do we verify/enforce the column-echelon condition on real DL workloads?\n3. A client needs to know the gossip matrix and the participation pattern to optimize for correlation. Is this a standard assumption? I guess a client may just know its local patterns. Also the topology may be time-varying.\n3. What’s the computational/communication overhead of computing and refreshing the optimal correlation on large graphs and long horizons? How sensitive is the performance to approximate solutions if optimization is hard.\n4. While experiments are conducted on a wide range of graphs (both synthetic and real-world), they are limited to small tabular datasets with small models. How would the proposed method for vision or NLP tasks?\n5. The paper seems to use GDP and Renyi terms mostly, I recommend the authors to also include (epsilon,delta)-DP guarantees that will be of the interest to many practitioners.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper derives neat theory with clean abstraction and provides a unified lens and extends to adaptive and rectangular cases.\n2. The paper presents substantially tighter bounds on PNDP.\n3. The paper presents a concrete algorithm Mafalda-SGD that is adoptable and easy to run after an offline correlation evaluation step.\n4. Empirically results show strong performance across a lot of graphs.", "weaknesses": "1. Seemingly strong assumptions (e.g., linear DL (definition 3), column-echelon, and the knowledge of gossip matrix for MAFALDA-SGD)\n2. Limited experimental scale\n3. Computational overhead is not discussed\n\nPlease see the questions section below for more details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SbYrxVa2mI", "reviewer": "Reviewer_fuoh", "summary": "The paper proposes a unified privacy framework for decentralized learning based on the Matrix Factorization (MF) mechanism, bridging recent advances in centralized DP accounting to decentralized, peer-to-peer training. This paper presents a new algorithm, MAFALDA-SGD, which achieves tighter privacy guarantees.", "questions": "1. Why is a direct multiplicative objective preferable in Eq. 9? Could the authors provide empirical evidence or theoretical justification that this formulation does not suffer from scale imbalance in larger graphs or longer training horizons?\n2. Why does the method not explore cross-node correlation or richer participation structures, which the theory explicitly allows?\n3. Does the method remain computationally practical when gradients are extremely high-dimensional, as in Transformers?\n4. Can your generalized privacy theorem (Theorem 7) apply to asynchronous or time-varying gossip matrices W_t?\n5. Did you explore non-Gaussian noise distributions (e.g., Laplace or sub-Gaussian) within the MF framework?\n6. Could MAFALDA-SGD be extended to heterogeneous privacy budgets across nodes?\n7. Is the matrix-factorization optimization offline-only, or could it adapt online to changing participation patterns?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The background information and technical introduction are very detailed and the writing is well-organized.\n2. The issue of distributed privacy protection is of great practical significance, and the utility-privacy trade-off faced by existing methods is more severe compared to that in the centralized approach.\n3. Sufficient theoretical evidence shows that each step has detailed proofs.", "weaknesses": "1. The gap between theory and method implementation: The theoretical framework in Sections 4–5 establishes a very general condition for the MF mechanism. This suggests wide applicability to diverse decentralized algorithms and trust models. However, the proposed algorithm MAFALDA-SGD in Section 6 only instantiates this framework under a restricted setting: Local Differential Privacy (LDP) combined with node-local temporal correlation.\n2. Additional computational overhead: MAFALDA-SGD algorithm requires an offline optimization of the noise correlation matrix. This process involves computing the Gram matrix and its Cholesky factorization, which may introduce non-negligible computational overhead.\n3.\tLimited empirical diversity: Experiments focus on small to mid-scale graphs (≤ 300 nodes). Realistic, large-scale federated networks (e.g., > 10⁴ users) would better demonstrate practicality.\n4.\tMinor clarity issues: Heavy notation could be simplified, and intuitive explanations (especially for Eq. 9 and Lemma 10) would help non-specialists.\n5.\tEvaluation scope: Only MLP on Housing dataset — a deeper model (e.g., CNN or Transformer under DL setting) would show robustness of MAFALDA-SGD.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mfYHAswQ8M", "reviewer": "Reviewer_KGVY", "summary": "The paper studies Differentially Private Decentralized Learning and proposes a matrix-factorization view that unifies attacker observations and common trust models (LDP, PNDP, SecLDP). It generalizes prior MF privacy results to a broader class of workloads while preserving adaptivity, enabling tighter privacy accounting for existing DP-DL methods. The framework also disentangles the matrix governing privacy from the one driving optimization, clarifying how to design useful noise correlations in decentralized settings. Building on this, the authors introduce MAFALDA-SGD, which optimizes node-local noise correlations under LDP, and they report tighter PNDP accounting and improved utility on synthetic and real graphs and a regression task.", "questions": "- Could the authors clarify whether attackers who can read some local models $\\theta$ (for example, compromised nodes) can be incorporated by augmenting $O_A = A G + B Z$, and whether the column-echelon and adaptivity arguments still apply in that setting?\n\n- Can you bound the limits of generality by stating which settings fall outside the framework, for example, non-linear message transforms, asynchronous or stale models, quantization or compression, or additional side information that might violate linearity or the column-echelon assumption?\n\n- Do you plan to add further experiments, such as a classification task, ablations over participation schemes $(k,b)$ and training epochs, and sensitivity to graph topology, to substantiate the generality and robustness of the reported improvements?\n\n- Do the authors plan to include an LDP baseline, such as DECOR (or provide a rationale if not), to clarify the relative benefits of optimized local correlations under LDP?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The work offers a unifying template to express the attacker across multiple decentralized trust models, which generalizes beyond prior algorithm-specific analyses.\n\n- The theoretical contribution extends matrix-factorization privacy guarantees to column-echelon workloads, preserves adaptivity, and formalizes sensitivity, providing principled guarantees that support the framework.\n\n- The empirical results indicate tighter PNDP accounting and improved utility for MAFALDA-SGD under LDP on the reported setups, suggesting practical benefits.", "weaknesses": "- The paper’s accessibility is limited for readers without prior exposure to matrix-factorization in DP; the notation is dense, the definition and role of “column-echelon” are introduced with minimal intuition in the main text, and the transition from the general theorem to MAFALDA is abrupt. A short primer with a toy $T=3$ derivation (showing how $A = B C$ and $C^\\dagger$ shape correlations), a step-by-step “apply-the-framework” recipe (choose trust model and participation, form the attacker view and objective, impose constraints, solve for correlations), a brief glossary of symbols, and one worked example mapping a familiar DP-D-SGD variant into the proposed matrices would substantially improve readability.\n\n- The empirical scope is narrow, focusing on one regression task and a few graphs; adding a classification task and ablations over participation schemes and correlation patterns would better demonstrate robustness.\n\n- The presentation would benefit from precise definitions and cleanup, including defining the weighted/semi-norm $|\\cdot|_{B^\\dagger B}$ when first introduced and making the Cholesky orientation consistent throughout (for example, state clearly whether $H = L L^\\top$ or $H = L^\\top L$ and keep that convention)\n\n- The set of LDP baselines could be expanded or justified; in particular, including DECOR as a comparison (or explaining why it is out of scope) would help situate MAFALDA-SGD among methods that also exploit correlations under LDP.\n\n- Typo: “Independent” in Figure 1", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)