DMM: Distributed Matrix Mechanism for Differentially-Private Federated Learning Based on Constant-Overhead Linear Secret Resharing

1. Why discrete Gaussians?:

Since our novel techniques are independent of the noise distribution used, we just chose one distribution that we believe to be the most well-studied/understood: the discrete Gaussian distribution. Indeed, we just need CX + Z to be differentially-private, where Z can be sampled from any (discrete) noise distribution; whichever distribution yields the best results can be used and these results will be at least as good as those stated in our paper. We are not currently aware of any other (discrete) noise distribution that is always better than the discrete Gaussian. Ultimately, the main message of our paper is the same: using the matrix mechanism for local (distributed) DP is better than using uncorrelated noise for local (distributed) DP.

1. How baseline is run:

We use the exact experiment details specified in the respective papers: (Section 5; Kairouz et al., 2021) for Local DP DDG and (Section 6 and Appendix I; Choquette-Choo et al., 2023a) for the Central DP mechanisms. For local DP DDG, the FEMNIST norm clip is set to 0.03 and the SO-NWP norm clip is set to 0.3. Additionally, Generic RDP amplification via sampling (Zhu And Wang, 2019) is used. For central DP, the SO-NWP clip is set to 1. Amplification is calculated using the technique presented in their paper along with the dp_accounting python library (reference [18] in their paper). We will include these in our paper.

2. Effect of number of rounds on complexity:

Let T* be the total number of rounds and d the model dimension. In a given round T <= T*, the complexity of our algorithm for a general matrix factorization (including the Optimal Matrix Factorization) scales as O(d * T), while for the Honaker Online mechanism, the complexity scales as O(d log T). We will make this more explicit in the paper.

3. Scaling in terms of k:

We use k = 2 * \mu * n for 0 < \mu < 1/2, as stated in Section 3, “Communication Complexity”. In round T, the concrete overhead is a 1/(4 \mu^2) factor (times d * T in the case of general, including optimal, Matrix Factorization, and d log T in the case of Honaker Online mechanism). We will make this clearer in the paper.

4. Noise methods and centralized MM papers:

Since our techniques are independent of the noise distribution, we just chose one that we believe to be the most well-studied/understood: the discrete Gaussian. Indeed, we just need CX + Z to be differentially-private, where Z can be sampled from any (discrete) noise distribution; whichever distribution yields the best results can be used and these results will be at least as good as those in our paper. Ultimately, the message of our paper is the same: using the matrix mechanism for local (distributed) DP is better than using uncorrelated noise for local (distributed) DP.

Also, we believe that the Skellam Distribution is incomparable to the discrete Gaussian in terms of privacy-utility tradeoff: Theoretically, quoting from (Agarwal et al., 2021) the bound on \eps DP they “provide is at most 1 + O(1/\mu) worse than the bound for the Gaussian” (this also holds with respect to the discrete Gaussian). Experimentally, it can be seen from Figure 5 of (Agarwal et al., 2021) that performance from the discrete Gaussian and Skellam are quite similar; depending on \eps, sometimes the discrete Gaussian is better.

For the Poisson binomial mechanism of (Chen et al. 2022), Table 1 of that paper indicates that the error from that mechanism and the discrete Gaussian is asymptotically the same. They do not experimentally compare to the discrete Gaussian or run FL experiments, so it is hard to tell which has better accuracy in practice. We will be sure to cite this paper.

We are happy to include the performance of the Skellam and Poisson binomial distributions in our paper (in the current version we do acknowledge and reference the Skellam Distribution in Footnote 6).

Also, note that we do reference and indeed compare to “Choquette-Choo: (Amplified) Banded Matrix Factorization: A unified approach…” as the SOTA, which is indeed a NeurIPS 2023 paper and thus cited as (Choquette-Choo et al., 2023) in e.g., caption of Figure 2, and elsewhere.

5. Pseudo-gradients:

Our system only requires clients to compute vectors that will be used to update the model parameters at the server (by somehow aggregating all of the vectors of the clients, i.e., averaging). So pseudo-gradients can be used in our system.

6. Lines 269-270:

Yes, thank you for pointing it out.

7. Lines 252-254:

Yes, each party i = 1,...,n in round T sends n shares, for a total of n^2 communication per round across all i=1,...,n.

8. Client-to-client communication:

Note: in practice the communication between clients will be (end-to-end encrypted and) routed through the server. Indeed, it is quite common for communication to be routed through the server, see, e.g., (Bonawitz et al, 2017) and most follow-ups. Moreover, such communication only occurs between clients of consecutive cohorts (i.e. rounds T and T+1), so we do not believe it's a heavy requirement.

9. Suitability of ICML:

We believe that any paper that improves the SOTA for any topics of interest in the Call for Papers should be seen as suitable. Our paper is for “Trustworthy Machine Learning” topic listed in the call. Indeed, we directly improve an IMCL 2021 paper (Kairouz et al. 2021a).

10. LDP -> DDP:

Thanks. We will fix it.

11. LRP description:

The input to Reshare is indeed a vector of k shares: z_[1,k]^i = (z_1^i, …, z_k^i). The output is a packed secret sharing where the shared secret vector is the above, z_[1,k]^i. This output sharing is denoted by [z_[1,k]^i] = ( (z_[1,k]^i)^1 ,... , (z_[1,k]^i)^n) (i.e., a vector of n shares, 1 for each party in the next cohort).

1. Construction of matrix A:

The matrix A (and its factorization A=BC) is a public value that can be constructed before training begins by the central server (which does still exist in our framework, though importantly privacy holds even with respect to this server; see, e.g., right of Figure 1).

2. Figure 6, performance of eps=5 and eps=2.7 at given round:

Note that it is common for the accuracy at different privacy levels to be similar in early training rounds before the accuracy for weaker privacy levels (i.e., smaller noise scale) becomes higher in the final training rounds. See, e.g., Figure 7 in (Kairouz et al., 2021a).

3. Practical Setting and Motivation:

Differentially Private Federated Learning has already been widely deployed in practice (see Section 1). In many cases, there could be regulations and/or other privacy concerns that prevent even a central server from obtaining sensitive client information, or that prevent clients from trusting that the central server will properly add noise. This is the setting in which our results fit—clients must add noise locally. We believe our experiments show the practicality of our solution.

Moreover, our setting is the same as many other works, including an ICML 2021 paper (Kairouz et al., 2021a), and a concurrent work (Ball et al., 2024). (See our comparison to the latter paper, which has weaker privacy guarantees, in Section 1, Related Work and Section E.)

4. “Theoretical analysis heavily depends on existing works”:

We believe that our proposed Constant-Overhead Linear Secret Resharing protocol and its correctness/security analyses are novel and significant contributions.

1. Dropout Resistance:

We thank the reviewer for pointing this out. We did not include the details for dropout resistance in the main body to make the (already complex) protocol easier to understand, but we should have included it in the appendix.

However, the reviewer is correct; there is a simple way to fix this: The clients in cohort T+1 must agree on a subset of clients from cohort T whose shares they use in the Recover algorithm. As the reviewer suggests, the server (through which all communication is routed) can simply send to cohort T+1 this subset directly, defined as those clients of cohort T who sent shares to all cohort T+1 clients. (For reference, it is quite common for communication to be routed through the server, see, e.g., (Bonawitz et al, 2017)).

Then, the Recover algorithm of protocol LRP in Section 3 will additionally take as input such a set of NONDROPOUTS (received from the server), and the existing summation in the Recover algorithm will now be for i \in NONDROPOUTS (and similarly for the Recons algorithm).

We will make this change for dropout resistance in the final version.

2. Description of Ball et al:

Note that in Ball et al, the server receives ciphertexts from the clients, then maintains and aggregates the ciphertexts which are to be eventually decrypted (also by the server). For example, in Section 4.1 of that paper, it is written that from an encryption of x1 received from Alice and x2 received from Bob, “the server can sum the result to get an encryption of x1+x2”. Then “imagine the server is holding a ciphertext” encrypting x, “Alice and Bob can simply compute and send” their (noisy) secret keys which “enables the server to recover x”.

Also, in Section 4.2, it is written that “writing to the secret state” means “the server then simply sums the resulting correlated ciphertext with all ciphertexts received from cohort Ci”.

Thus, the server maintains the ciphertexts itself and even performs the decryption itself, so it can certainly submit the wrong ciphertext for decryption. Furthermore, even if the server did not perform the decryption itself, the clients would still need to receive the maintained (aggregated) ciphertexts from the server.

3. Comparison to matrix mechanism in the clear (without discretization):

Note that we indeed compare to the matrix mechanism in the clear (without discretization) for the StackOverflow NWP task in FIgure 2. We achieve very similar accuracy for given privacy values \eps.