Optimal Survey Design for Private Mean Estimation

This work identifies the first privacy-aware stratified sampling scheme that minimizes the variance for general private mean estimation under the Laplace, Discrete Laplace (DLap) and Truncated-Uniform-Laplace (TuLap) mechanisms within the framework of differential privacy (DP). We view stratified sampling as a subsampling operation, which amplifies the privacy guarantee; however, to have the same final privacy guarantee for each group, different nominal privacy budgets need to be used depending on the subsampling rate. Ignoring the effect of DP, traditional stratified sampling strategies risk significant variance inflation. We phrase our optimal survey design as an optimization problem, where we determine the optimal subsampling sizes for each group with the goal of minimizing the variance of the resulting estimator. We establish strong convexity of the variance objective, propose an efficient algorithm to identify the integer-optimal design, and offer insights on the structure of the optimal design.

Differential Privacy (DP), introduced by Dwork et al. [2006], is a popular probabilistic framework designed to protect individual privacy while preserving the utility of data. By introducing calibrated random noise into the data processing, DP ensures that outputs remain informative while reducing the risk of identifying individuals. However, this added noise introduces unique challenges for data analysis. Neglecting the effects of DP mechanisms can lead to biased and incorrect conclusions (Santos-Lozada et al., 2020; Kenny et al., 2021). To address these challenges, researchers commonly employ various inference strategies, such as Bayesian inference (Bernstein and Sheldon, 2018 & 2019; Schein et al., 2019; Kulkarni et al., 2021; Ju et al., 2022), asymptotic analysis (Gaboardi et al., 2016; Gaboardi and Rogers, 2017; Wang et al., 2018), simulation-based inference [Awan and Wang, 2024], and bootstrapping methods (Ferrando et al., 2022; Wang et al., 2022). However, there is also a growing need to integrate DP into the design of data collection schemes.

Survey sampling traditionally encompasses three components: sample selection, data collection, and estimation [Brick, 2011]. Over time, survey sampling has been evolving to incorporate new technologies [Frankel and Frankel, 1987], such as registration-based sampling [Green and Gerber, 2006], telephone sampling [Force et al., 2010], and computerization [Baker, 1998]. Differential privacy represents one of the latest advances, fostering the need to optimize data collection to balance privacy and utility.

Among survey sampling methods, stratified sampling stands out as a robust scheme that leverages auxiliary information to collect valuable samples that can minimize variance. Unlike simple random sampling (SRS), stratified sampling minimizes the risk of having bad samples by dividing the population into groups (strata) based on common characteristics [Lohr, 2021]. Neyman [1934] was the first to formalize stratified sampling, introducing an optimal allocation of samples to minimize variance across groups—a goal aligned with the principles of experimental design [Wu and Hamada, 2011]. Developing DP techniques for surveys is very important to protect individual respondents, especially when sensitive questions are asked. Furthermore, another key motivation for incorporating DP is as a technique to reduce response bias—also known as answer bias—which often arises when individuals avoid answering sensitive or controversial questions truthfully, leading to skewed or inaccurate conclusions. Randomized response, introduced by Warner [1965], provides a mechanism for respondents to address such questions while satisfying differential privacy [Dwork et al., 2014]. Incorporating appropriate noise through DP techniques, our framework effectively balances data utility with individual privacy and can also reduce response biases.

When considering differential privacy for survey sampling, it is first important to recognize a crucial result of differential privacy under sampling which plays a key role in the formulation of our problem: When a privacy mechanism is applied to a randomly sampled subset of a population (while the sampled individuals themselves remain secret), a stronger privacy guarantee can be achieved [Kasiviswanathan et al., 2011]. This effect is referred to as the “secrecy of the sample” or privacy amplification by subsampling. Thus, in stratified sampling, where the population is divided into subpopulations, subsampling within groups can amplify privacy protection. This effect adds complexity to the optimization problem of determining the optimal survey design when integrating differential privacy into stratified sampling.

This paper is the first to consider optimizing a survey design when incorporating a differential privacy guarantee. Specifically, we develop an optimal stratified sampling scheme to minimize the estimator variance in private mean estimation under differential privacy. Holding the total sample size fixed, we search for the optimal subgroup sizes. A key challenge is that different subsampling rates for each group require different “nominal privacy budgets” in order to give the same privacy guarantee to all members of the population, which results in a complex objective function. Ignoring DP-induced variance during the design phase can cause significant inflation in estimator variance, as demonstrated in Section 5 and highlighted in the table below. Table 1 illustrates this issue by comparing the variance ratio of the naive design to the optimal design, using both Laplace and Truncated-Uniform-Laplace (TuLap) mechanisms [Awan and Slavković, 2018].

ϵ 0.1 10−1/2 1 101/2 10

Laplace 1.828 2.095 2.269 2.311 1.973

TuLap 2.405 3.324 3.877 4.06 4.076

Table 1: Variance ratio on population mean

Contributions: We propose a novel framework for designing stratified sampling schemes under a hybrid local/central differential privacy regime, leveraging a design of experiment (DOE) perspective. We provide an efficient algorithm for locating the optimal integer design, which enables practitioners to conveniently implement in practice. Our approach accounts for variance from sampling as well as from the DP noise amplified by subsampling during the design phase, allocating the best subsampling sizes to minimize the variance of our final estimator. This work is, to the best of our knowledge, the first to apply experimental design principles to data collection under differential privacy, fundamentally altering optimal stratified sampling schemes to accommodate DP considerations. Our contributions include the following:

• We identify and formulate the problem as a constrained integer-programming problem, identifying its alignment within the framework of DOE.

• We establish strong convexity for a general variance objective, covering important cases such as A-optimality (minimizing the trace of the covariance matrix) and population mean estimation, under three common additive DP mechanisms: Laplace, Discrete Laplace, and Truncated-Uniform-Laplace.

• For the population mean estimate, we derive closed-form continuous solutions under Discrete Laplace and Truncated-Uniform-Laplace mechanisms; additionally, we derive the optimal continuous design when using purely Laplace noise, which reveals the DP-aware design lies between the original, no-noise design and the pure Laplace noise design.

• By leveraging the strong convexity of the variance objectives, we develop a computationally efficient algorithm to locate the integer-optimal design, overcoming the intractability of exhaustive search methods.

Organization: The rest of the paper is structured as follows: Section 2 provides the necessary background on local and central differential privacy as well as privacy amplification by subsampling. Section 3 formulates the main problem, a convex-constrained minimization problem with a general variance objective. Section 4 establishes the strong convexity of the problem, a key property enabling the efficient search for the integer-optimal design. In Section 5, we illustrate variance inflation resulting from naive stratified sampling without considering DP effects and demonstrate the efficiency of our algorithm in locating the integer-optimal design, even as the number of groups increases. Finally, Section 6 discusses the implications of our findings and potential avenues for future work.

Related Work: Although optimal survey design for private estimation remains unexplored, differentially private survey sampling has recently been studied in other contexts. Lin et al. [2024] construct confidence intervals for proportions using data collected through stratified sampling. Bun et al. [2020] examine stratified and cluster sampling, highlighting that certain sampling schemes can degrade privacy rather than enhance it and can increase privacy risks. Sampling has also been employed as a technique to address DP-related problems. Ebadi et al. [2016] examine the impact of various sampling schemes on differential privacy, demonstrating that only Bernoulli sampling amplifies privacy protection. Joy and Gerla [2017] propose a sampling-based privacy mechanism satisfying differential privacy, while Bichsel et al. [2018] develop a correlated sampling method to detect privacy violation. The concept of “secrecy of the sample,” proposed and formalized by Kasiviswanathan et al. [2011], highlights the role of random sampling from population in enhancing privacy guarantees while keeping the members of the dataset secret. Li et al. [2012] demonstrate that implementing k−anonymity safely after a random sampling step ensures (ϵ, δ)−DP. Cheu et al. [2019] employ “secrecy of the sample” to establish the privacy guarantee of the shuffled model, an intermediate variant between central and local models that enhances privacy by relying on a trusted curator to shuffle the locally privatized data before releasing a final private statistic. Arcolezi et al. [2021] incorporate random sampling into their solution for multivariate frequency estimation in locally differentially private (LDP) settings. Variance minimization and estimation, as well as utility-maximization mechanisms, have been widely investigated under DP. Treating multi-agent systems as probabilistic models of environmental states parameterized by agent profiles, Wang et al. [2017] establish a lower bound on the l1-induced norm of the covariance matrix for minimum-variance unbiased estimators when the agents’ profiles are ϵ-DP. Li et al. [2023a] expose how output poisoning attacks can manipulate and deteriorate mean and variance estimation under local DP. Amin et al. [2019] identify a bias-variance trade-off caused by clamping in DP learning and provide careful tuning on the clamping bound. For a fixed count query, Ghosh et al. [2009] show that the geometric mechanism minimizes the expected loss for virtually all possible users while satisfying the DP constraint. Similarly, for a single real-valued query function, Geng and Viswanath [2015] demonstrate that the staircase mechanism can minimize l1 and l2 costs under specific parameter settings.

We introduce the necessary background of local and central differential privacy and relevant subsampling results. Differential privacy can be ensured from two perspectives: local DP and central DP. Both approaches achieve privacy guarantees by employing randomized mechanisms that perturb sensitive data or statistics and produce their privatized outputs. Local DP offers stronger privacy protection by privatizing individual data, ensuring that sensitive information remains unknown to anyone, thereby shielding individuals from both internal and external threats. However, this comes at the cost of reduced data utility. In contrast, central DP relies on trusted data curators to collect sensitive data and subsequently release a privatized summary, protecting individual only from external adversaries. Definition 1 (Local Differential Privacy: Duchi et al. [2013]). Let X be the set of possible contributions of an individual. A randomized privacy mechanism M provides local ϵ−differential privacy, if for any two data points x, x′ ∈ X and for any measurable set S ⊆ Range(M). Pr[M (x) ∈ S] ≤ eϵ Pr[M (x′) ∈ S]. To safeguard individual privacy through added noise, the amount of noise must be carefully quantified, with sensitivity playing a pivotal role in this process. Greater data dispersion increases sensitivity, which in turn requires scaling up the noise in the privacy mechanism. Definition 2 (Sensitivity). Let f: X → R be a statistic. The sensitivity of f is ∆f = maxx,x′ ∈X f (x) − f (x′). In Example 1, we introduce three differentially private mechanisms to which we apply our findings throughout the paper. Example 1. The following are three common DP mechanisms. For local ϵ−DP, given a real-valued statistic f (x), • the Laplace mechanism is Z = f (x) + L, where L ∼ Lap(0, s) with s = ∆f /ϵ. • the Discrete Laplace mechanism (DLap) [Inusah and Kozubowski, 2006, Ghosh et al., 2009] for integer-valued data is Z = f (x) + K, where K ∼ P (K = k) = 1−p 1+p p k with p = exp − ∆f ϵ. • the Truncated-Uniform-Laplace mechanism (TuLap) [Awan and Slavković, 2018] is Z = f (x) + K + U, where K is the same as in DLap and U ∼ Uniform(− 12, 12). TuLap is a canonical noise distribution [Awan and Vadhan, 2023] and it is related to the Staircase distribution [Geng and Viswanath, 2015]. While local DP offers strong protection against both external adversaries as well as the data collectors themselves, it requires a large amount of noise for privatization. For example, Duchi et al. [2013] show that local DP mechanisms have inferior asymptotic variance compared to non-private estimators. On the other hand, central DP has a trusted curator, but gives the same DP guarantee to external adversaries and allows for asymptotically negligible noise to be added [Smith, 2011, Barber and Duchi, 2014]. Definition 3 (Central Differential Privacy: Dwork et al. [2006]). Let X n be the set of possible datasets with sample size n and dH (·, ·) be the Hamming distance on X n × X n, a randomized privacy mechanism M provides (central) ϵ−differential privacy, if for any two datasets X, X ′ ∈ X n such that dH (X, X ′) ≤ 1, and for any measurable set S ⊆ Range(M), Pr[M (X) ∈ S] ≤ eϵ Pr[M (X ′) ∈ S]. Note that all local DP mechanisms are also central DP. Therefore, the following lemmas on central DP can be applied to local DP mechanisms. Lemma 4 (Parallel Composition: McSherry [2009]). Let M1, M2,..., Mk be a set of k mechanisms, where each Mi satisfies ϵi −DP. Suppose these mechanisms are applied to disjoint subsets of the dataset X n, denoted as D1, D2,..., Dk, such that X n = ∪ki=1 Di. Assume that the sizes of Di ’s are public. Then, the combined mechanism M = (Mi)ki=1 satisfies maxi ϵi −DP. Lemma 4 states that the ultimate privacy guarantee of a set of privacy mechanisms applying to disjoint datasets only hinges on the worst among all guarantees. In stratified sampling, a set Di represents a stratum (group). Lemma 5 (Subsampling: Corollary 3, Dong et al., 2022; Ullman, 2017). If M is a privacy mechanism that satisfies ϵ-DP for a dataset of size n, and Sm is the subsampling operator that chooses a subset of size m from the dataset of size n uniformly at random, then M ◦ Sm satisfies log(1 − q + q exp(ϵ))−DP, where q = m/n. Lemma 5 shows how subsampling creates its randomness, thereby bringing about privacy amplification. It immediately follows from Lemma 4 that if N is decomposed into k disjoint groups of size Ni for i = 1,..., k, and we want to sample subsets of size ni from each group, uniformly at random, then the privacy guarantee for a nominal ϵ-DP mechanism M applied to the subsamples is log(1 − qmax + qmax exp(ϵ)), where qmax = maxi nNii. Finally, we recall the post-processing property of DP: If M: X n → Y is an ϵ−DP mechanism and g: Y → Z is another mechanism, then g ◦ M: X n → Z satisfies ϵ−DP [Dwork et al., 2014]. This property allows us to construct customized estimators from the DP outputs, without compromising the privacy guarantee.

In this paper, we mi…

Based on the paper, here are specific improvements that can be made to AI systems, particularly those involved in survey design, data collection, and privacy-preserving analytics:

1. Privacy-Aware Adaptive Sampling Module for Data Collection Agents

• Improvement: Replace the standard Neyman allocation (which ignores DP noise) in stratified sampling agents with the paper's DP-aware allocation algorithm. The system will take as input: group sizes (Ni), estimated group variances (σi2), total sample budget (η), and the target privacy budget (ε). It will then output the optimal integer sample sizes (n1,..., nk) per stratum.

• What the improved system can do: Automatically adjust sample allocation in real-time based on the privacy budget. For example, with ε=1, Laplace noise, and heterogeneous strata, the system will allocate more samples to larger strata (closer to proportional allocation) rather than purely variance-proportional allocation, reducing estimator variance by up to 2.3x compared to naive designs (as shown in Table 1). This prevents the common failure mode where a privacy mechanism is bolted on after sampling, causing severe variance inflation.

2. Strongly Convex Optimizer for Mixed-Integer DP Problems

• Improvement: Integrate the paper's strong convexity proof (Theorem 8) and the radius-bounding lemma (Lemma 12) into the optimization engine. Instead of using generic mixed-integer solvers (which are intractable for large η), the system will: (a) solve the continuous relaxation via Newton's method, (b) identify the nearest integer point, (c) compute a guaranteed search radius r = sqrt(2(g(n init) - g(x*))/λ), and (d) perform an exhaustive search only within that small ball.

• What the improved system can do: Find the exact integer-optimal design in O((2r)(k-1)) time instead of O(η(k-1)). For a survey with 10 strata and η=100,000, the system can find the optimum in under 1 second (as demonstrated in Figure 4), whereas exhaustive search would take exponential time. This makes DP-aware design feasible for large-scale national surveys (e.g., census-like studies) that were previously computationally prohibitive.

3. Mechanism-Specific Variance Predictor for Design-Time Decisions

• Improvement: Embed the closed-form variance formulas for Laplace (Eq. 4), DLap (Eq. 5), and TuLap (Eq. 6) into the system's cost model. The system will automatically select the best mechanism for a given scenario by comparing predicted variances, rather than defaulting to Laplace.

• What the improved system can do: For a population mean estimation task with ε=0.1, the system will predict that TuLap has 2.405x higher variance ratio than the optimal design, while DLap has 1.828x. It can then recommend switching to DLap or adjusting the design accordingly. This prevents the common mistake of assuming all DP mechanisms behave identically under subsampling, which can lead to 2-4x variance inflation (as shown in Figure 2).

4. Continuous-Design Interpolation Engine for Privacy Tuning

• Improvement: Use Proposition 11 and the observed interpolation behavior (Figure 3) to build a privacy slider that smoothly transitions between Neyman allocation (no privacy) and proportional allocation (pure DP). The system will compute the optimal design for any ε by solving the KKT conditions, even when no closed-form exists (Laplace case).

• What the improved system can do: Given a target ε, the system can instantly provide the optimal continuous allocation. For ε=1, it will allocate samples between the variance-proportional and size-proportional extremes. This allows survey designers to quickly explore the trade-off between privacy and statistical efficiency without re-running expensive optimizations, enabling interactive what-if analysis for policy decisions.

5. Robustness Checker for Unknown Variances

• Improvement: Incorporate the paper's strong convexity to build a sensitivity analysis module. Since the objective is strongly convex, the system can compute a quadratic lower bound and quantify the maximum suboptimality if the assumed σi2 are misspecified.

• What the improved system can do: Before committing to a design, the system can report: If the true variance of stratum 2 is 20% higher than assumed, the design's variance will increase by at most X%. This is critical for real-world surveys where pilot estimates of variance are noisy. The system can also suggest a minimax design that is robust to variance misspecification, leveraging the convexity to find the worst-case optimal allocation.

6. Automated Pilot-Study-to-Full-Survey Pipeline

• Improvement: Create an end-to-end pipeline that: (1) uses a small pilot sample (e.g., 5% of budget) to estimate σi2, (2) applies Algorithm 1 to find the optimal design for the remaining 95% budget, (3) executes the survey, and (4) computes the final DP estimate with the correct nominal privacy budget per stratum (using Proposition 7).

• What the improved system can do: Eliminate the manual, error-prone process of separately designing sampling and privacy mechanisms. The system will automatically ensure that each individual gets the same ε-DP guarantee (via the subsampling amplification formula) while minimizing variance. This is particularly valuable for longitudinal studies where strata characteristics change over time, requiring re-optimization at each wave.

7. Benchmarking Tool for DP Survey Designs

• Improvement: Implement the variance ratio metric (naive vs. optimal) as a standard diagnostic. The system will automatically flag designs where the naive allocation leads to >1.5x variance inflation and suggest the optimal alternative.

• What the improved system can do: For any proposed survey design (even non-optimal), the system will output: Your current design has a variance ratio of 2.1 compared to the optimal DP-aware design. You can achieve the same accuracy with 52% fewer samples by reallocating as follows: [specific n i values]. This provides immediate, actionable feedback to practitioners who may not be optimization experts.

These improvements transform the paper's theoretical contributions into practical, deployable capabilities for AI-driven survey platforms, ensuring that privacy protection and statistical efficiency are jointly optimized rather than treated as sequential afterthoughts.

This work identifies the first privacy-aware stratified sampling scheme that minimizes the variance for general private mean estimation under the Laplace, Discrete Laplace (DLap) and Truncated-Uniform-Laplace (TuLap) mechanisms within the framework of differential privacy (DP). We view stratified sampling as a subsampling operation, which amplifies the privacy guarantee; however, to have the same final privacy guarantee for each group, different nominal privacy budgets need to be used depending on the subsampling rate. Ignoring the effect of DP, traditional stratified sampling strategies risk significant variance inflation. We phrase our optimal survey design as an optimization problem, where we determine the optimal subsampling sizes for each group with the goal of minimizing the variance of the resulting estimator. We establish strong convexity of the variance objective, propose an efficient algorithm to identify the integer-optimal design, and offer insights on the structure of the optimal design.