Optimal Survey Design for Private Mean Estimation

Thank you for recognizing that our work contributes to the growing trend of incorporating differential privacy into fundamental statistical methodologies, particularly in stratified sampling.

• Regarding the need for prior knowledge of variances, we agree that this is a limitation. However, in practice, statisticians can often estimate variances using historical data or prior knowledge. Alternatively, a portion of the privacy budget could be allocated for variance estimation. We will conduct a sensitivity analysis through simulations to assess the impact of mild variance misspecifications, ranging from 10-20%.

• In Proposition 3.4, the nominal privacy budget $M_i$ is given by
  $\log \left( \frac{\exp(\epsilon/\Delta f) - 1 + q_i}{q_i} \right)-DP$ where $q_i = \frac{n_i}{N_i}$. We sincerely apologize for the omission of "-DP" in our submission, which may have led to confusion. We have corrected this in our revised version.

  Indeed, when the subsampling rate $\frac{n_i}{N_i}$ is relatively small, the nominal budget can be quite large. Nevertheless, our primary goal is to ensure central DP while providing some additional protection against the data curator through the (weaker) local-DP guarantee.

  There could certainly be settings where the sample size is a moderate proportion of the population size, and having a larger sample would improve the statistical estimation by reducing the variance.

• Accurate variance estimation within each group can be feasible given historical data or prior knowledge. Alternatively, a portion of the privacy budget could be allocated to estimate population variances during an initial phase.

We are thankful that you acknowledged that we identified a gap in the DP literature regarding survey sampling and provided a successful solution along with a thoughtful experimental evaluation. We hope that our responses below will address your comments.

• (Experimental Design Comment) Thank you for the question. Please recall that the DP variance objective consists of two components: data variance and DP randomness. When analyzing the variance objective under the Laplace mechanism, we found that both components are strongly convex, though proving the strong convexity of the DP-induced variance required significantly more effort. Initially, we assumed that the Discrete Laplace and TuLap mechanisms would exhibit similar behavior due to their comparable shapes. However, we later discovered that for these two mechanisms, strong convexity arises solely from the data variance, while the variance due to the Discrete Laplace mechanism itself is merely convex (specifically, linear). This key difference explains why the Laplace case differs from the others.

  Intuitively, when both sources of randomness exhibit strong convexity, they each lead to their own optimal designs (Neyman allocation for data variance and proportional allocation for purely Laplace variance). The competition between these two effects determines the optimal design. However, this dynamic does not hold for the Discrete Laplace and TuLap mechanisms, as their variance objectives are not strongly convex by themselves. We will add these insights to the simulation section.

• We will update the text size in the figures to match the font size in the main content to improve readability.

• To clarify, the table compares the non-private solution (optimal design) evaluated with the DP variance against the DP-optimal solution evaluated with the DP variance, and the values are the ratio of these variances (higher is worse). We will provide additional context for Table 1 to ensure it can be understood by the reader in the introduction section.

Thank you for your questions. We are happy to address them below:

• The key aspect of our setup that enables an efficient solution is the strong convexity property. When generalizing to other settings, it is important to verify that the resulting objective is still strongly convex, which may need to be done in a case-by-case manner; without strong convexity, our efficient algorithm is not applicable. Furthermore, we use the subsampling result of $\epsilon$-DP, which also exists in Rényi-DP and $f$-DP, but not in Gaussian-DP or zero-concentration DP. Regarding utility, the use of Gaussian noise could improve the utility of the final estimator as it has lighter tails than Laplace noise; however, the variances of both scale in the same manner as the privacy parameter is varied. Ultimately, these extensions are promising directions for future work, and we will include a paragraph in the discussion that includes these points.

• You are correct that we do impose the constraint $n_i \leq N_i$, and we only consider subsampling without replacement. A possible extension of this work could also consider subsampling with replacement: for results on privacy amplification through subsampling with replacement, we refer to "Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences" by B. Balle et al. As noted earlier, the key aspect to investigate in this extension is whether their variance objective is strongly convex, but this is left for future work. This extension will also be mentioned in the discussion section of the paper.

• Yes, we agree and recognize this limitation of known variances. In practice, and as is widely done in survey sampling, the variances will be replaced by estimated variances or known bounds on the unknown variances. This is not ideal, but as other reviewers have also noted, this work begins the treatment of what appears to be a fundamental problem, and so assuming that variances are known seems like a reasonable step. Future work should address the issue of estimating variances, and especially the effect of any heavy tails that may result. Regarding accuracy, even if the variances are misspecified, the mean estimation remains unbiased, though the design may no longer be optimal. We will conduct a sensitivity analysis through simulations to compare the design performance under mild variance misspecifications of approximately 10-20%.

Please let us know if our responses have addressed your questions or if you have any remaining concerns about the paper.

We would appreciate any further clarification regarding your reasoning for the inclination towards rejection. We are particularly keen to understand your perspective, as other reviewers have acknowledged the novelty and potential impact of our work.

Thank you for recognizing the contributions of our work. While we acknowledge that this research does not fully resolve all related problems, we are pleased that you see it as a significant step forward. Please let us know if you have any further questions.