PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors

We thank the reviewer for their positive review, and will update the paper to address their valuable feedback. Below we address some of their questions.

Missing definitions: We apologize for the oversight, and will add definitions of any cryptographic terms that we use.

Additional complexity: The reviewer is correct that much like Prio itself, the use of complex cryptographic components will introduce additional engineering complexity. We hope that PREAMBLE will be implemented in the standard libraries that implement various prio protocols, such as libprio and daphne, reducing the overhead. Overall, we believe that PREAMBLE enables larger dimensional mean estimation than was feasible with prior techniques, and the incremental engineering complexity over prio can be justified in scenarios when such aggregates are needed.

Violations of Block-sparsity assumption: In PREAMBLE, block sparsity is not an assumption on the input, but rather ensured by our sub-sampling process. The cryptographic part of the algorithm requires inputs to be block-sparse. However, given an arbitrary input, PREAMBLE first subsamples the right number of blocks to ensure that block-sparsity holds. Indeed this subsampling can be viewed as a pre-processing technique to induce the block-sparse structure.

We thank the reviewer for their positive evaluation of our work and will address their feedback in the updated version. Below we address their specific questions.

Performance on larger models: We believe that our DP-SGD results demonstrate that the shape of the noise in PREAMBLE does not impact the convergence of DP-SGD, and one can focus on the scale of the noise. In Figure 13 in the appendix, we evaluate gradient estimation error for $\varepsilon=1$ and $2$ per batch, and this should allow us to evaluate the impact on DP-SGD convergence for any model. In particular, DP-SGD in the low privacy regime typically uses per-batch sigma in the range [0.6,2]. If the per-batch privacy sigma is 1.0, and batch size is 10k, Theorem 3.1 implies that sending 100k coordinates per user will ensure an overall sigma of ~1.05. By taking a slightly larger batch of 11k, the effective sigma can be brought back down to 1.0, so that the utility is equivalent to non-compressed DP-SGD. The privacy analysis can then be done with this slightly larger batch and using PREAMBLE. This privacy analysis of the scheme will now need to account for two levels of sampling (sampling a batch of users, and sampling of blocks), and we can use [FS25] to handle this and compute the final (\eps,\delta) parameters. This privacy analysis will incur a small overhead compared to the Moments accountant (and a slightly larger overhead compared to PRV accountants), and for typical parameters, we expect this increase to be small. We will add examples of this overhead for some parameter settings from recent works in the final version of the paper.

We remark that mean estimation is a really wide-spread primitive in private learning and statistics well beyond DP-SGD, with applications ranging from learning histograms over dictionaries both big and small, using such histograms in adaptive algorithms for learning heavy hitters over very large dictionaries, training small and large ML models, running k-means and similar clustering algorithms, running Bayesian inference algorithms, etc. Indeed learning histograms is the most widely-used practical application of Federated learning by far, and Fig. 4(c) captures the benefits of our approach for this application.

Runtime and Resource usage for client and server: The decreased communication in PREAMBLE does come at a computation cost for clients and servers; however, we introduce improvements to existing DPF constructions to keep this computation very modest. The main computational overhead for clients and servers is the evaluation of PRGs from a small seed - we describe the construction at a high level at the start of Section 4 and in more detail in Appendix H. The total computation, dominated by length-doubling PRG evaluations, is done in a tree-like structure, where the client must evaluate k paths in this tree and the server must evaluate the entire tree.

To give some intuition of the runtime of the PRG operations, we quickly benchmarked the PRG instantiated with AES-128 on an Apple M2 laptop with 16GB of memory. Using the command line tool openssl speed, we measured a time of approximately 2ms for server computation and 0.5ms for client computation. To obtain these numbers, we consider a group of size $2^64$ in the final layer and set $\lambda = 128$, $D=10^6$, $B=2^{10}$, and $k=2^8$.

The asymptotic computation cost is stated in the table below. The improvement in server computation stems from constraining the sparsity structure to have k non-zero blocks instead of $kB$ non-zero coordinates overall, resulting in $k\log(D/B)$ calls to a length-doubling PRG and $k$ calls to a PRG whose output is $B\times$ the size of the input. This change could also be applied to existing approaches for multi-point DPFs in the other rows of the table, but this is not a focus of those previous works. The asymptotic notation for server computation in the probabilistic batch codes approach hides a multiplicative constant of approximately 3, while our approach requires approximately D PRG evaluations (1.03D in practice), avoiding the constant overhead.

Comparison with [CSOK23]: [CSOK23] operates in the multi-message shuffle model and thus relies on different trust assumptions than PREAMBLE. Similarly to their work, PREAMBLE exploits the fact that the sparsity pattern of vectors can be hidden. However, our work crucially relies on blocking to reduce the sparsity, and is necessary to make the DPF construction significantly more efficient. Blocking helps significantly with the truncation error, as we show in Section 5. Sparsity constraints also make regular Poisson subsampling, which is used by [CSOK23], less suitable for our application and necessitate the use of sampling schemes that require a more involved privacy analysis.

We thank the reviewer for their positive evaluation of our work and will incorporate their valuable feedback in the updated version of the paper. Below we address their specific questions.

Collaborative computation: We acknowledge the complexity of the cryptographic parts of the protocol, and have attempted to give a high-level view of the roadblocks and their resolution in Sec. H in the appendix. We will rework the pseudocode of the collaborative decoding to make it clearer.

Hybrid Trust Model: That is a great question, and we will add more discussion of this. Prio guarantees that as long as one server is honest, the other server (even if they were malicious) learns nothing except for the published aggregate. So from the privacy point of view, we have the strong privacy guarantee: nothing except the differentially-private aggregate can be learnt by any of the parties as long as one of the servers is honest. A malicious server can corrupt the output of course, but cannot impact privacy.

Concrete numbers for the example: That is a great suggestion. We will add some numbers here, and make this example more consistent with the example on lines 78-81. Holding m=kB=50000 constant and choosing $B\approx1000$, our communication would be ~400KB in this example, if the field size is 64 bits.

The need for Zero knowledge proofs (ZKPs): That is a great question and we will add more discussion of this. The primary reason to have ZKPs here is to make the protocol robust to malicious clients. Absent proofs, a single client can change the whole aggregate arbitrarily. Proofs can ensure that a malicious client can only change the output by a bounded amount. Our protocol has 2 rounds, but as we discuss in section H.2, it can be made single round using Fiat-Shamir (and Fiat-Shamir is provably secure for our protocols in the random oracle model).

Would the gain extend to other uses of randomly-sparsified vectors: Yes and no. Privacy amplification analysis will help in case of random sparsification whenever we can make sure that the adversary cannot learn which coordinates a client contributes to. In single server settings (or in typical MPC-amongst-clients protocols), this is seldom the case, though one can imagine protocols can be designed to ensure this. This need to hide the sparsity pattern is the reason we use DPFs in our work.

We thank the reviewer for their positive evaluation and their valuable feedback that we will incorporate in an updated version of the paper. Below we address some of the reviewer’s questions.

Privacy parameters : We missed adding privacy parameters in the main paper, and will bring these forward from the supplementary material. The details for our DP-SGD experiments are presented in the Appendix (Section I.1). In particular, for figure 5, we use the privacy parameters $\varepsilon = 2.0, \delta = 10^−6$.

Constant $c$ : While the constant $c$ in Thm 3.2 can be explicitly calculated, the analytic formula is primarily valuable for giving intuition for the asymptotics. It is off by constant factors and hence is not used in practice. In practice (even for simple DP-SGD), one uses numerical accounting methods, and we do the same in our work.

Low-privacy Regime : We believe that our DP-SGD results demonstrate that the shape of the noise in PREAMBLE does not impact the convergence of DP-SGD, and one can focus on the scale of the noise. In Figure 13 in the appendix, we evaluate gradient estimation error for $\varepsilon=1$ and $2$ per batch, and this should allow us to evaluate the impact on DP-SGD convergence in the low privacy regime.

In particular, DP-SGD in the low privacy regime typically uses per-batch sigma in the range [0.6,2]. If the per-batch privacy sigma is 1.0, and batch size is 10k, Theorem 3.1 implies that sending 100k coordinates per user will ensure an overall sigma of about 1.05. By taking a slightly larger batch of 11k, the effective sigma can be brought back down to 1.0, so that the utility is equivalent to non-compressed DP-SGD. The privacy analysis can then be done with this slightly larger batch and using PREAMBLE. This privacy analysis of the scheme will now need to account for two levels of sampling (sampling a batch of users, and sampling of blocks), and we can use [FS25] to handle this and compute the final (\eps,\delta) parameters. This privacy analysis will incur a small overhead compared to the Moments accountant (and a slightly larger overhead compared to PRV accountants), and for typical parameters, we expect this increase to be small. This is the analysis in our current plots, and we will add examples of this overhead for some parameter settings from recent works in the final version of the paper.

We remark that mean estimation is a really wide-spread primitive in private learning and statistics well beyond DP-SGD, with applications ranging from learning histograms over dictionaries both big and small, using such histograms in adaptive algorithms for learning heavy hitters over very large dictionaries, training small and large ML models, running k-means and similar clustering algorithms, running Bayesian inference algorithms, etc. Indeed learning histograms is the most widely-used application of Federated learning by far and Fig. 4(c) captures the benefits of our approach for this application. The parameters of interest here: the batch size, the dimension, and the DP noise scale will vary considerably in these applications, and our approach will provide benefits in some of these cases when dimension is larger than the batch size. Our theorem 3.1 provides some guidance on what compression one can expect for a given setting of parameters. We will add more discussion of this in the updated paper.