Optimal Survey Design for Private Mean Estimation
Authors: Yu-Wei Chen
Raghu Pasupathy
Jordan Awan
Venue: ICML 2025 poster (2025)
Keywords: Differential Privacy
Experimental Design
Stratified sampling
Subsampling
Privacy Amplification
Primary area: social_aspects->security
TL;DR: We propose a privacy-aware subsampling scheme that minimizes the variance for private mean estimation.

Abstract: 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.

Optimal Survey Design for Private Mean Estimation
Yu-Wei Chen'
Raghu Pasupathy Jordan Awan
Abstract
ysis (Gaboardi et al., 2016; Gaboardi & Rogers, 2017; Wang et al., 2018), simulation-base inference (Awan & 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.
This work identifies the first privacy-aware strat- ified sampling scheme that minimizes the vari- ance 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 guarantce for each group, different nominal privacy budgets need to be used depending on the subsampling rate. Ignor- ing the effect of DP, traditional stratified sampling strategies risk significant variance inflation. We phrase our optimal survey design as optimiza- tion problem, where we determine the optimal subsampling sizes for each group with the goal of minimizing the variance of the resulting estima- tor. We establish strong convexity of the variance objective, propose an efficient algorithm to iden- tify the optimal design, and offer insights on the structure of this design in different settings.
Survey sampling traditionally encompasses three compo- nents: sample selection, data collection, and estimation (Brick, 2011). Over time, survey sampling has been evolv- ing to incorporate new technologies (Frankel & Frankel, 1987). such as registration-baset sampling (Green & Ger- ber, 2006), telephone sampling (Force et al., 2010), and computerization (Baker, 1998). Differential privacy rep- resents 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 a robust scheme that leverages auxiliary informa- tion 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 character- isties (Lohr, 2021). Neyman (1934) was the first to formal- ize stratified sampling, introducing an optimal allocation of samples to minimize variance across groups goal aligned with the principles of experimental design (Wu & Hamada, 201 I).
1. Introduction
Differential Privacy (DP), introduced by Dwork et al. (2006), is a popular probabilistic framework designed to protect indi- vidual privacy while preserving the utility of data. By intro- ducing calibrated random noise into the data processing, DP ensures that outputs remain informative while redueing 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 incor- rect conclusions (Santos-Lozada et al., 2020; Kenny et al., 2021). To address these challenges, researchers commonly employ various inference strategies, such as Bayesian in- ference (Bernstein & Sheldon, 2018 & 2019; Schein al., 2019; Kulkarni al., 2021; Ju al., 2022), asymptotic anal-
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 technique to reduce response bias-also known answer bias-which often arises when individuals avoid answering sensitive or controversial ques- tions truthfully, leading to skewed or inaccurate conclusions. Randomized response, introduced by Warner (1965), pro- vides 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.
Department Statisties, Purdue University, West Lafayette IN, USA. Correspondence to: Jordan Awan <jawan @ purduc.cdus
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 the formu- lation of our problem: When a privacy mechanism applied to randomly sampled subset of population (while the
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Optimal Survey Design for Private Mean Estimation
sampled individuals themselves remain secret), a stronger privacy guarantee can be achieved (Kasiviswanathan al., 2011). This effect is referred to as the "secrecy of the sam- ple" or privacy amplification by subsampling, Thus, in stratified sampling, where the population is divided into sub- populations, 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.
for variance from sampling as well as from the DP noise amplified by subsampling during the design phase, allocat- ing 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 dif- ferential privacy, fundamentally altering optimal stratified sampling schemes to accommodate DP considerations. Our contributions include the following:
This paper is the first to consider optimizing survey design when incorporating a differential privacy guarantee. Specif- ically, we develop an optimal stratified sampling scheme to minimize the estimator variance in private mean estima- tion 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.
We identify and formulate the problem as constrained pngger-rogramming problem, identifying its align- ment within the framework of DOE.
We establish strong convexity for a general variance ob- jective, covering important cases such as A-optimality (minimizing the trace of the covariance matrix) and population mean estimation, under three common ad- ditive 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- Saaieedd-nifoo-m--- Laplace mechanisms; additionally, we derive the optimal continuous design when using purely Laplace noise, which reveals the DP-aware de- sign lies between the original, no-noise design and the pure Laplace noise design.
Ignoring DP- -idindueed variance during the design phase can lead to significant inflation in estimator variance, as demon- strated in Section 5 and highlighted in the table below. Es- sentially, the Neyman allocation (Neyman, 1934), referred to as naive stratified sampling in our setting, only minimizes the variance from the data but can perform poorly when incorporating the variance induced by DP. Since the DP variance objectives in our problem contain both a compo- nent from the data and one from the DP mechanism, the op-optimal design differs from the Neyman allocation.
By leveraging the strong convexity of the variance ob- jectives, we develop a computationally efficient algo- rithm to locate the integer-optimal design, overcoming the intractability of exhaustive search methods.
Table 1 compares the non-private (Neyman) solution and the DP-optimal design, both evaluated under the DP variance objective, using Laplace and Truncaed-Uniffomm- Unifonn--apllaatt (TuLap) mechanisms (Awan & Slavković, 2018). The table reports the ratio of the DP variance Neyyyan over
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- convex-constrained minimization problem with a general variance objective. Section 4 establishes the strong con- vexity of the problem, a key property enabling the efficient search for the integer-optimal design. In Section 5, we illus- trate variance inflation resulting from naive stratified sam- pling 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.
Organization:
the potential inefficiency caused by ignoring the effect of DP during the design.
6
0.1
10-1/2
101/2
10
Laplace 1.828
2.095
2.269
2.311
1.973
TuLap
2.405
3.324
3.877
4.060
4.076
Table 1. Ratio of the DP variance objective when using the non- private solution versus the DP-optimal design for population mean estimation (1 is optimal, higher worse).
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 and can increase privacy risks.
Contributions:
We propose novel framework for design- ing stratified sampling schemes under a hybrid local/central differential privacy regime, leveraging a design of experi- ment (DOE) perspective. We provide an efficient algorithm for locating the optimal integer design, which practitioners can easily implement in practice. Our approach accounts
2

---

Optimal Survey Design for Private Mean Estimation
Sampling has also been employed technique to ad- dress DP-related problems. Ebadi al. (2016) examine the impact of various sampling schemes on differential pri- vacy, demonstrating that only Bernoulli sampling amplifies privacy protection. Joy & 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.
als 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.
Duchi et al., 2013). Let X' be the set of possible contributions of an individual. A privacy mechanism M provides local e- differential privacy, if for any two data points x, xr,² E X and for any measurable set S C (M))
Definition 2.1 (Local Differential Privacy:
The concept of "secrecy of the sample." proposed and for- malized 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- a-anonymity safely after a random sampling step ensures (c, 6)-DP. Cheu et al. (2019) employ "secrecy of the sample" to establish the privacy guarantee of the shuffled model, intermedi- ate 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. Ar- colezi et al. (2021) incorporate random sampling into their solution for multivariate frequency estimation in locally differentially private (LDP) settings.
(r]M(x) E S] S e PH(M(x') E S].
To safeguard individual privacy through added noise, the amount of noise must be carefully quantified, with sensi- tivity playing pivotal role in this process. Greater data dispersion increases sensitivity, which in turn requires scal- ing up the noise in the privacy mechanism.
Definition 2.2 (Sensitivity). Let f X - R be statistic. The sensitivity of f is Af = xaax,,''xxlful - f(z')).
In Example 2.3, we introduce three DP mechanisms to which we apply our findings throughout the paper.
Variance minimization and estimation, well as utility- maximization mechanisms, have been widely investigated under DP. Treating multi-agent systems as probabilistic mod- els of environmental states parameterized by agent profiles, Wang et al. (2017) establish lower bound on the 4 -indduced norm of the covariance matrix for vvrrinnce un- biased estimators when the agents' profiles are e-DP. Li et al. (2023b) expose how output poisoning attacks can manipulate and deteriorate mean and variance estimation under local DP. Amin et al. (2019) identify viri-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 mecha- nism minimizes the expected loss for virtually all possible users while satisfying the DP constraint. Similarly, for single val-valued query function, Geng & Viswanath (2015) demonstrate that the staircase mechanism can minimize & and E2 costs under specific parameter settings.
Example 2.3. The following are three common DP mech- anisms. For local c-DP, given a real-valued statistic fxx),
the Laplace mechanism is Z = f(x) + L, where L ~ Lap(0, 8) with As/e.
the Discrete Laplace mechanism (DLap) (Inusah & Kozubowski, 2006; Ghosh et al., 2009) for integer- valued data is Z = f(z) + K, where K ~ P(K- = k) 1-p pl with p = exp (-+/As).
I+p
the Truncated- Bruncated-Uniform--ar Uniform-Laplace mechanism (TuLap) (Awan & Slavković, 2018) is Z f(x) + K + U, where K is the same as in DLap and U Uniform(11/2 1/2). TuLap is canonical noise dis- tribution (Awan & Vadhan, 2023) and it is related to the Staircase distribution (Geng & Viswanath, 2015).
While local DP offers strong protection against both exter- nal adversaries as well as the data collectors themselves, it requires a large amount of noise for privatization. For ex- ample, Duchi et al. (2013) show that local DP mechanisms have inferior asymptotic variance compared to non- non-private estimators. On the other hand, central DP has a trusted cura- tor, but gives the same DP guarantee external adversaries and allows for asymptotically negligible noise to be added (Smith, 2011; 1; Barber & Duchi, 2014).
2. Background
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 per- turb sensitive data or statistics and produce their privatized outputs. Local DP offers stronger privacy protection by pri- vatizing individual data, ensuring that sensitive information remains unknown to anyone, thereby shielding individu-
Definition 2.4 (Central Differential Privacy: Dwork et al., 2006). Let X be the set of possible datasets with sam- ple size n and d be the Hamming distance on X" x X"", a privacy mechanism M provides (central) e- differential privacy, if for any two datasets X, X' E xm
3

---

Optimal Survey Design for Private Mean Estimation
such that dx(XX, (X,X') < 1, and for any measurable set S C MM)g
where Way is the i.i.d. additive noise with mean and fi- nite variance y2 depending on ni, N; and Assume that n; samples are drawn from group D; with total sample size of lf E [b; Σ No). The constrained minimization problem of interest becomes
Pr(M(() E 8] S Pr(M(X') E S).
Note that all local DP mechanisms are also central DP. Therefore, the following lemmas on central DP can be ap- plied to local DP mechanisms.
arg min
[o; + (m,, c)]
(1)
1=1
Lemma 2.5 (Parallel Composition: McSherry, 2009). Let M1, My...., MR be a set of k mechanisms, where each M; satisfiex e- Suppose these mechanisms are applied to dis- joint subsets of the dataset X", denoted as D1, D2..... DE. such that X = - Di, and where the sizes of D are public. Then, the combined mechanism M (M
subject C, = (n E N Enn n4 oI and 0 < mi S
Nr, Vi]. where a; are pre-determined weights.
This problem is classified as a nonlinear integer program. As it will be addressed later using the Lagrangian, which in- troduces a continuous multiplier for the equality constraint, it can be generally treated as a mixed-integer programming problem (Lee & Leyffer. 2011).
satisfies max; DP-
Lemma 2.5 states that the ultimate privacy guarantee of a set of privacy mechanisms applied to disjoint datasets only hinges on the worst among all guarantees. In stratified sampling, a set D, represents a stratum (group).
Note that og, N1, di, (i = 1,.., k) and 1j are assumed to be given or determined prior to subsampling. The following examples show how the a; can be chosen to optimize for various variance objectives.
Lemma 2.6 (Subsampling: Corollary 3, Dong et al., 2022; Ullman, 2017). If M is a privacy mechanism that satisfies c-DP for a dataset of size n, and S., is the subsampling operator that chooses subset of size in from the dataset of size n uniformly at random, then the subsampled mechansim M o Sm satisfies log(1 -q+ -xxpeex()))-DD where m//n
Example 3.1 (Population Mean Estimation). One of the most important parameters to estimate in survey sampling is the population mean. For group i, the group mean b4 can be estimated by jú = n.
1 Σド= Zej, which is an
unbiased estimator of M4s The population mean μ can thus be unbiasedly estimated by j = Σt_ Nyps Then, 2i=; N.
Lemma 2.6 shows how subsampling creates its randomness, thereby bringing about privacy amplification. It follows from Lemma 2.5 that if N is decomposed into k disjoint groups of size N₂ for i = 1.... K and we want to sample subsets of size n; from each group, uniformly at random, then the privacy guarantee for a nominal e-DP mechanism M applied to the subsamples is log(1 --l--p0 Qmax Imax exp(c)), where fmax max, N
Var(() E the constrained minimization problem is
No E x N., e)] Thus,
k N
arg min
n2: [o + 72 (n c.]
s.t. > n4 7) n, S N., n4 EN,, Vi.
Finally, we recall the post-processing property of DP: If M : X + y is an e-DP mechanism and g : y + 2 is another mechanism, then g o M : X + Z satisfies c-DP (Dwork et al., 2014). This property allows us to con- struct customized estimators from the DP outputs, without compromising the privacy guarantee.
This aligns with (1) as a, = N, for all i. Example 3.2 (A- (A-Optimal Experimental Design). Another important case is the A-optimal experimental design, where the goal is to estimate each group mean with the A-optimal weighting. Denote the covariance matrix of (/..)..,fs)) as E,.. then the A-optimal experimental design is
k
3. Problem Setup
arg argmin min tr(Ep)
Σ
1
[o + 72 (I...N..)) (3)
1=1 nhi
In this paper, we minimize the variance of a mean estimator, which comprises data randomness and additive privacy noise centered at zero, with the following problem setup:
s.l. Σ n4 =1= n. S N., n. EN,
Vi.
This algins with (1) as a; = 11 for all i.
Suppose there are k groups (strata) of people D, (i 1....,k k) with size N, that make up the entire population. In each group i, Yij represents the survey response of the j-th individual (j = 1,..., N₂) which has mean μ4 and variance of with bounded support. In a local DP setting, instead of Vig. Ziz Yú₁ + W.y is the privatized survey response,
Remark 3.3. There are other interesting settings that into this framework. For instance, one may be interested in a unit-free optimal design by setting a; 1/0
Now, we look into the variance component from the pri- vacy mechanism, that is, (2;, Nr, e) for all i, where the
4

---

Optimal Survey Design for Private Mean Estimation
subsampling comes into play. Rather than using mmax for all & groups in Lemma 2.6, we consider q: = 8; such that M, Sn, satisfies e-DP, where M, is the privacy mecha- nism for group and S,, is the subsampling operator which chooses a subset of size n, from the group i. This ensures every person gets the same level of central DP privacy pro- tection, regardless of their group size.
The Laplace mechanism for local e-DP is Z,g Yug + Lap(O,, 1). The variance objective is
8;
a
of + 2 2lg -2 (1+ exp (xp(c/AAt-/n.)) n
74
The Discrete Laplace mechanism for local DP is Zg = Yis + Kıj. where Kg DLap (p: exp(1/si))- The variance objective is
Population
k
au (exp (e/Af) - # (exp (c/Af) - 1)2
No 0 +
(5)
1st group
2nd group
1-th group
7
M2
Mechanisms
Me
The Trancacd-Unnffrm--Lallaee mechanism for lo- cal c-DP is Zij = Yi + K2 + U2 where K;z (:
Y11
Vins
Y21.
Y2na
Yur. Yens
Smy
DLap (p; exp(1/s:)). and Uti Uniform( 2 3)
Sua
S.x
The variance objective is
Subsampling Operations
k
2
+ +2
1
Th (exp (c/Af) 1+ N: (exp (e/Af) 1)2
N:
(6)
n
12
Figure 1. Diagram of the DP stratified sampling
By using an exhaustive search, the complexity of solving
Illustrated in Figure 1, the key challenge lies as follows:
(I) is O ((E)) (Ross, 1974), motivating the need for customized optimization method.
To avoid wasting the final privacy budget e across groups, the parallel composition between groups must account for the subsampling operations when determin- ing central nominal budget for each group. This bud- get is then distributed as local nominal budget to each individual in the group in order to protect individual survey response, ensuring- within group-that that the group as a whole satisfies the central nominal privacy guarantee.
4. Theoretical Results and Algorithm
In this section, we develop the optimal integer design which solves (I). In Section 4.1, we discover and prove the strong convexity of the variance objectives under Laplace, DLap, and Tul app mechanisms, which enables us to precisely locate the optimal design in Section 4.3. In Section 4.2 we also derive some closed-fore form solutions over continuous space for some special cases.
parallel composition
Since the total sample size 77 is fixed, allocating fewer samples to one group may allow for less local noise in that group, while simultaneously increasing the local noise required for other groups and amplifying the 1/n, factor in the overall variance objective.
4.1. Strong Convexity
We begin by establishing the strong convexity of our vari- ance objectives. Strong convexity ensures unique optimum over the reals and provides a quadratic lower bound for the objective function. These properties are leveraged in Sec- tion 4.3 to develop an efficient optimization algorithm.
Therefore, our method has dual privacy guarantees: a local DP guarantee from the nominal privacy loss budget against the data collector, and a central DP guarantee, boosted by subsampling, against external adversaries.
Theorem 4.1 (Strong Convexity). Let a, N., os and 1 be given for all i = I....,k. kt. Then, the continuous relaxations of the variance objectives (4), (5) and (6), with (n1...., n4k) replaced by continuous vector I C. = {x E gg* Σ 2, = 11 0 < 2, S N,, Vi), are strongly convex.
Proposition 3.4. If the nominal privacy budget of M; is log (e/Afi -DP, then M, o Sn, satisfies e-DP.
Proposition 3.4 establishes the dual privacy guarantees for our mechanisms, ensuring uniform privacy protection for all individuals from public disclosure.
Proof Sketch. We first prove that the variance objectives are strongly convex over (0, 1)* and then show that this property continues to hold under the constraints. For the DLap and TuLap mechanisms, strong convexity follows by inspection; for Laplace, strong convexity is established by change of variables and repeated differentiation.
Example 3.5. Applying Proposition 3.4 the three mecha- nisms with = 1/log + exp (c/AS)- N:). we have the following:
5

---

Optimal Survey Design for Private Mean Estimation
Strong convexity in Theorem 4.1 guarantees a unique so- lution over the reals. This solution can be found via New- ton's method with established R packages such as opt im, nlopt r or a aabama. However, solving the mixed-integer programming problem is more complex, as existing pack- ages do not provide direct solutions. Strong convexity is
Proposition 4.4 (Closed-Form Solution of Purely Laplace Variance for Population Mean). Under the constraint of Ca. the purely DP variance from the Laplace mechanism (8) is minimized at x; = (N./ Σ for all i.
Proof Sketch. In addition to the similar Lagrangian proof argument in Proposition 4.2, we use the result that yoy)) 2 log 2 (1+ c/y) is strongly convex, as proved in Theo- y rem 4.1, to identify the solution form.
key in identifying the integer-optimal design in Section 4.3. Note that neither CVX's free solvers in MatLab nor any R package support mixed-integer programming.
4.2. Closed-Form Solution for Population Mean
Proposition 4.4 indicates that the sample size allocated to each group is merely proportional the size of the group. This corresponds to the concept of the proportional allo- cation (Kempf-Leonard, 2004). It is surprising that the solution is independent of c as (8) can be blown up when e drops. Although e does not play a role in either the solution of the original variance or that of the pure DP variance, it plays a critical role in the solution of the total variance. We illustrate this phenomenon in Section 5.
closed-fore continuous solution desirable for its ease of implementation and the insights it provides into the behavior of the design. While such a solution does not exist for all og, intriguing results emerge when a; N,, the case of population mean estimation.
Proposition 4.2 (Closed-Form Solutions for Population Mean). If Mj is DLap or TuLap with a; N; and as- sume that [Ta/ 33//Z(,N)lp T;N:)ln I 1 for all i, the continuous solution of (5) and (6) under the constraint of C2 have a closed form x (T;:Na)(( N;,)),, where n? = of for
4.3. Algorithm to Find the Optimal Integer Design
DLap and oे of + T2 for TuLap.
Since Theorem 4. only ensures the existence and unique- ness of the continuous-optimal design, in this section we use the strong convexity property derive a small region that is guaranteed to contain the integer-optimal design. This result is leveraged in Algorithm 1 to efficiently find the integer-optimal design.
Proof Sketch. We first formulate the Lagrangian of the con- strained optimization problem. The KKT conditions give a proportional relation x; x T,N, for all i. Then, the con- straint provides unique solution for the x; 's.
Remark 4.3. The solution of (5) is identical to the naive strat- ified sampling design, also known as the Neyman allocation (Neyman, 1934) or the optimal allocation (Kempf-Leonate 2004), where the sample size allocated each group is proportional to both the variability and the size of the group. In contrast, (6) has regularization effect on its sample sizes that results in a different allocation.
The search over integer points satisfying the convex con- straint finite, as the set of feasible integer-valued solutions, D = (n N² Σ n; = 77 0 < n, N,, Vi), is inherently limited. Moreover, the strong convexity of the variance objective provides quadratic lower bound, ensuring that certain level set of this bound must contain the integer- optimal point. This level set can be characterized in terms of Euclidean distance, with the radius determined by the smallest eigenvalue of the objective function.
As for the Laplace noise, although were unable derive general closed-form solution for (4), we have interest- ing finding in the case of population mean estimates, which offers insight in the interplay between the no-DP and purely DP solutions. First, we define the non-private variance as
Lemma 4.5 (Range Search for Integer-Optimal Design). Let 91, 92, 92.93 !a be the objective function from (4), (5), (6) respectively, and C2 such that xt" = arg ming 9j (z), then
A
N
n" = arg min gj (n).
(9)
(7)
D
N.
F
is located within B (r) fz || - < r} with
Under the constraint of Cz, the non- -oi-private variance (7) is minimized at x; = (a,N./ Σ N.)) for all i, On the other hand, we can define the pure DP variance as
r = /2(g (Pini.) - (x (x*)))/ for any given E (1, 2, 3), where is the smallest eigenvalue of the Hessian of g, (x)) and Aiiiit = arg ming gj (n) with F. = (n E N* Σ n
77, [x;] S n4 S [x;]].
k
N
(1 (1+
exp exp(c/ANT (c/AA)) -11--11 -
2 log
2
Applying the result of Lemma 4.5, we propose Algorithm I which starts with the continuous solution, identifies a small (8) set of candidate integer solutions, and then identifies the integer-optimal design within this smaller set.
N,
Zi
No/N:
6

---

Optimal Survey Design for Private Mean Estimation
Algorithm 1 Integer- Design
marks the final exhaustive search region, which includes all feasible candidates for the integer-optimal design.
Input: x² (the optimal continuous solution) and Hessian
matrix of g: Hz(2*)
Remark 4.8. Strong convexity of the variance objective plays key role in identifying the optimal design. While an exhaustive grid search has ((=)) different combina- tions, scaling 017²-1) when & is fixed, Algorithm reduces 1J to 2r, giving a much lower complexity of O ((2r)*-1). We show in Section 5 that r relatively small.
for ,....,
do
Define T; {nz E N [x,] n4 S [
end for
Define T = Mo......,,.111. n4) : TA = 1
Σ ni where (M.,...., mk-1) Ti ... Tk-1}
Select Dinit. = arg mill (n))
Calculate the smallest eigenvalue À of Hg (2*)
Calculate radius
(2(mm 9(x'''0))))''' 1)/2
5. Simulation
for i 1,...,k k do
We numerically illustrate our method through simulation studies. Section 5.1 compares compares variances between naive and DP-aware stratified sampling. Section 5.2 ex- plores the interplay between the non-private and purely DP designs. Section 5.4 showcases the computational ef- ficiency of our algorithm. The input of Algorithm x=, is obtained by package nloptr r and a abama in R. All computations, including runtime measurements, were con- ducted on the Purdue Bell clusters using multiple cores. The source codes are available at https: / /gittub..../.. com/ ga garyOcchen/DP___ SttpeeeennDppptttuuuureeeee htt__ppttiiiie..e..mmm
Define S. = {m+ E N max( - r, 1) S n2 S
min(x, + Ni,, k+ 1)}
end for
Define =
mk- nz) : n 7
Σis Wi, where (m),.... Tkk E S x... x S
Select n² = arg minnee (1z by an exhaustive search.
Output: n"
Theorem 4.6 (Integer-Optimal Design). Algorithm I out- puts the integer-optimal design (9).
Remark 4.7. Before entering the second for-loop in Algo- rithm the practitioner may decide to check the optimality gap Lo( aii.)) ) g(=*))/9(=") If the optimality gap is suffi- ciently small, it may be acceptable to adopt the suboptimal design Tini.. This is demonstrated in Section 5.4.
5.1. Suboptimality of Naive Stratified Subsampling
As shown in Table 1, stratified sampling under our DP frame- work requires a tailored design to minimize the variance objective. Both private mean estimation and private A- optimal estimation face variance inflation under specific privacy mechanisms.
In this simulation, there are 4 groups with population sizes N = (7000, 8000, 9000, 10000) and variance o² = (0.08, 0.08², 0.083, 0.08*) and total sample size rj = 200. We plot the variance ratio from naive subsampling scheme to that of the integer-optimal design while varying from 0.01 to 100.
Minit
For the population mean case, Figure 3 illustrates that, under the Laplace mechanism, the naive subsampling variance can be up to 2.5 times larger than the optimal design variance within 1 < E < 10. Under TuLap, the variance ratio can reach as high as 4. Note that DLap gives the same design for population mean.
Figure 2. Illustration of Algorithm 1: level set (dotted blue), B. (r) and its enclosing sphere and cube (dashed black), fea- sible region induced from r (thick green), integer points (black)
Figure 2 illustrates the main idea behind Lemma 4.5 and Algorithm I. Note that the dotted blue ellipse repre- sents the level set of the variance objective g evaluated at Tinni,. the nearest integer design from the continuous op-
Laplace
TuLap
Variance Ratio
2.0
Mechaniem
timum x². Starting by locating 7mmit. our method then constructs ball Bx-(r) centered at x: with radius r = /2(g) (fini..) 9, ()/A This ball corresponds to the level set of quadratic lower bound of g, and thus still
Laplaca
1.5
Tul
0.1
0.1
100
0.01
0.1
100
contains the integer-optimal design. We then enclose the ball in cube to simplify the search. The solid green cube
Figure 3. Variance Ratio on population mean

---

Optimal Survey Design for Private Mean Estimation
For A-optimal cases, illustrated in Figure 4, the naive sub- sampling variance under the Laplace mechanism can be up to 1.8 times larger than the optimal design variance within the range 1 < é < 10. For the TuLap mechanism, a notice- able jump in the variance ratio occurs around = 10, driven by the variance of the On, 1) component. Similarly, the DLap mechanism follows a trend comparable to TuL but demonstrates the smallest variance ratio gap between the
protection the optimal design more closely aligns with the Neyman allocation.
Group 1
Group 2
Group 3
100
Subsampling Sizes
80
Idager Soluton
No Noise
naive subsampling scheme and the optimal integer design.
-- Pure Noise
This behavior aligns with the population mean scenario, where the ratio remains constant at 1.
Optimal
0.01
100
3.1
9.1
100
0.t
0.1
10
DLap
Laplace
TuLap
1.005
3.0
Figure 5. Optimal, no-noise, and pure-noise designs as varies
1.75
Variance Ratio
1.004
Mechaniom
5.3. Sensitivity Analysis
1,000
1.50
DLap
Laptaae
1,002
Tul.sp
The setting is the same as in Section 5.2, with additional consideration of misspecifying the sample variance 6² rela- tive to the true variance o². We examine four cases where 6² 30 1.2x², 0.9a², 0.3o². As shown in Figure 6, the DP-omtimal design is largely robust misspecification within +00% The convergence of curves near = 100 occurs because, under weak privacy constraints, the DP- optimal design approaches Neyman allocation, which is proportional to a, and thus to in this setting.
1.25
1.001
1.5
1.000
1.30
0.01
0.1
100
0.01
0.1
100
0.81
01
Figure 4. Variance Ratio for A-Optimal Design
The trend of the Laplace mechanism differs from those of DLap and TuLap because, in the latter two, strong convex- ity arises only from the data variance, while the variance induced from the Discrete Laplace mechanism is actually linear. In contrast, both the data and Laplace variance com- ponents are strongly convex in the Laplace mechanism. In- tuitively, when both sources of randomness are strongly convex, each favors its own optimal design (for example, Neyman allocation for data variance and proportional allo- cation for purely Laplace variance in the population mean case). The interplay between these competing effects shapes the overall optimal design, as shown more clearly in Sec- tion 5.2.
Group
Group
Group
100
Subsampiing Sizes
80
Soluton
300%
120%
60
80%
3016
0.0
10
100
Figure 6. Sensitivity Analysis
5.2. Interplay between No-noise and Purely Laplace Noise Optimal Designs
5.4. Computational Efficiency of Algorithm 1
While a closed-form solution for private mean estimation under the Laplace mechanism is unavailable, the optimal design tends to fall between the no-noise and pare-Laplace noise designs.
Our problem is formulated as mixed-integer programming task, which lacks an off-the-shelf solution method, partic- ularly in R. While exhaustive search becomes infeasible as either the total sample size 1) or the number of groups k increases, our algorithm proves to be relatively efficient for practical implementation. Although it struggles with scenarios involving large k. it remains highly efficient for substantial v) values- up to 100, 000 and more-when & is kept at a reasonable scale.
In our simulation, there are 3 groups with population sizes N (1000, 2000, 3000), a² (0.08, 0.08 0.08?), 1 and total sample size 17 200. We use the set- ting of the population mean with Laplace noise. Figure 5 demonstrates that the integer-optimal design largely inter- polates between the no-noise and pore-noise designs. As privacy protection strengthens, the design shifts closer to the pure-noise configuration; conversely, with weaker privacy
In this simulation, there are 10 groups with N = (N1, Ng....,,NNu N10) = (20000, 19000,.... 110000 and r² = (of.0z...., = (0.081.1 0.081.2 ........08)
8

---

Optimal Survey Design for Private Mean Estimation
and e 1. We measure the computation time for an ex- haustive search and for our proposed algorithm the total sample size 1) increases from 30 to 48, using the population mean case with Laplace noise. Figure 7 demonstrates that the exhaustive search exhibits exponential growth in compu- tation time, whereas Algorithm effectively mitigates this growth. In fact, we see that Algorithm can effectively find the optimal solution with sample sizes up to 10 in less time than exhaustive search takes for 1) = 30.
6. Discussion
We proposed new framework for integrating differential privacy (DP) into stratified sampling, aiming to achieve two main goals: minimizing the total variance and protecting individual privacy. A significant contribution of our work is the inclusion of privacy considerations in the data collection design. While traditional stratified sampling focuses on min- imizing variance assuming non-private data, our approach takes into account the noise introduced by privacy mecha- nisms as well as the privacy amplification by subsampling, ensuring more reliable results under privacy constraints.
Computation Time (sec.)
10,000
1,000
Our framework is fairly flexible, as it works with three common DP mechanisms: Laplace, Discrete Laplace, and Truncated- TruncatedUnniforn-Laapa Uniform-Laplace. Furthermore, the strong con- vexity of the variance objective ensures that the optimization problem is well-defined, which leads to solid theoretical re- sults. We also addressed the computational challenges of exhaustive search methods by developing an efficient algo- rithm for finding the optimal integer design.
100
Method Algerithm
10
Exhaustive
.0
22
46
100
1000
10000
100200
Sampe Size r)
Figure? 7. Computation time comparison
However, there are some limitations to our framework. We assume prior knowledge of population variances across groups. In practice, a pilot study is commonly conducted, where a small portion of pilot samples are drawn from each group to estimate group sample variances. The fixed sam- ple size constraint, while reasonable, may be too strict or may not account for more complex scenarios (e.g. chance constraints). Additionally, our algorithm may be inefficient when the search radius is large. Exploring alternative meth- ods for finding the integer-optimal design could improve efficiency; for example Gurobi, MOSEK, and Julia's Pa jarito all have generic mixed-integer programming packages. Lastly, our analysis is limited to e-DP with the Laplace, DLap, and TuLap mechanisms and uses subsam- pling without replacement. Future work could extend our results to other privacy and subsampling frameworks, such as the Staircase mechanism Geng & Viswanath (2015), Gaussian mechanism, or general canonical noise distribu- tions Awan & Vadhan (2023) as well as the p-7CDP (Bun & Steinke, 2016), μ-GDP, f-D frameworks (Dong et al., 2022) subsampling with replacement (Balle et al., 2018).
Now, we consider k groups with N (N1, N2, -,.... No) (10000 + 1000- k 10000 + 900 k ...... 11000) and の² 0.08 +k/10 and e ==1 1. We implement our full algorithm from h = 2 to 12, locating the optimal design n=, and that of the first part of our algorithm from A: = 14 to 26, locating the nearest integer design Téjnit.-
(aî, ,?....,,,.? = (0.08--1, 0.08
if >1> then as i increases the computation time exhibits exponential growth, which becomes large especially when k 2 14. In practice, if r > 1.5 and k is large. we rec- ommend identifying the nearest integer design Tinit corre- sponding to the first half of the algorithm. In this simulation, maintains an optimality gap (the relative increase in the DP variance objective at Almmti compared to the continuous optimal x²) of less than 10-1 from the continuous-opting optimaal design x². Notably, locating the continuous-optin optimal de- sign is independent of Algorithm and requires less than second for any k in the simulation.
Some directions for future work are as follows: Incorpo- rating the double privacy amplification effect of subsam- pling and shuffling (Li et al., 2023a) could strengthen pri- vacy guarantees but also introduces additional optimization challenges. Applying our framework in a fully central DP context, assuming a trusted curator, is another option and would yield different variance objective. Finally, extend- ing the framework to more complex sampling designs, such as multi-stage or adaptive sampling, would broaden its ap- plicability. These directions would further solidify the role of Da-aware stratified sampling in collection.
Radius (r)
Runtime (sBc.)
Optimality Gap
Valuue (log scaled y-axis)
16:06
1.0
100
16-06
Sample
0.5
10
16-07
10000
0.3
1e-08
1c+05
16-09
2
Number of Groups (k)
data
Figure& 8. Curse of dimensionality in number of groups

---

Optimal Survey Design for Private Mean Estimation
Impact Statement
Bernstein, G. and Sheldon, D. R. Differentially private Bayesian inference for exponential families. In Ben- gio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa- Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018.
This work enables accurate and privacy-aware data collec- tion for private mean estimation by optimally designing stratified sampling schemes under differential privacy. It allows practitioners to conduct surveys in sensitive domains such as health, education, and public policy while obtaining reliable results backed by formal privacy guarantees.
Bernstein, G. and Sheldon, D. R. Differentially private Bayesian linear regression. Advances in Neural Informa- tion Processing Systems, 32, 2019.
Acknowledgments
This work was supported in part by NSF grant no. SES 2150615 to Purdue University. The authors are grateful to the anonymous reviewers, whose valuable feedback helped to improve the presentation of this paper.
Bichsel, B., Gehr, T., Trachsler-Cohen. D., Tsankov, P., and Vechev, M. Dp-finder: Finding differential privacy viola- tions by sampling and optimization. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Com- munications Security, CCS '1, pp. pp. pp.5085515 508-524, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450356930.
References
Amin, K., Kulesza, A., Munoz, A., and Vassilvtiskii, S. Bounding user contributions: A bias-variance trade-off in differential privacy. In International Conference on Machine Learning, pp. 26LR, 2019.
Brick, J. M. The future of survey sampling. The Public Opinion Quarterly, 75:872-8883 888, 2011.
Bun, M. and Steinke, T. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In The- ory of Cryptography Conference, pp. 635-658. Springer, 2016.
Arcolezi, H. H., Couchot, J.-F., Al Bouna, B., and Xiao, X. Random sampling plus fake data: Multidimensional frequency estimates with local differential privacy. In Proceedings of the 30th ACM International Conference on Information Knowledge Management, CIKM '21, pp. 47-57, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978 9781450384469.
Bun, M., Drechsler, J., Gaboardi, M., McMillan, A., and Sarathy, J. Controlling privacy loss in sampling schemes: An analysis of stratified and cluster sampling. arXiv preprint arXiv:2007. 12674, 2020.
Awan, J. and Slavkovié, A. Differentially private uniformly most powerful tests for binomial data. In Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018
Cheu, A., Smith, A., Ullman, J., Zeber, D., and Zhilyaev, M. Distributed differential privacy via shuffling. In Ad- vances in Eyypology-EUROCRRY
2019: 38th Annual International Conference on the Theory and Applica- tions of Cryptographic Techniques, Darmstadl, Germany, May 19-23, 2019, Proceedings, Part 38, pp. 375 403. Springer, 2019.
Awan, J. and Vadhan, S. Canonical noise distributions and private hypothesis tests. The Annals of Statistics, 51(2): 547-572, 2023.
Dong. J., Roth, A., and Su, W. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3-37, 2022.
Awan, J. and Wang. Z. Simulation- based, sampl inference for privatized data. Journal of the American Statistical Association, pp. 1-27, 2024.
Duchi, J. C., Jordan, M. I., and Wainwright, M. J. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 429-438. IEEE, 2013.
Baker, R. P. Computer Assisted Survey Information Collec- tion, volume 66. John Wiley & Sons, 1998.
Balle, B., Barthe, G., and Gaboardi, M. Privacy amplifica- tion by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems, 31, 2018.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cali- brating noise to sensitivity in private data analysis. Theory of Cryptography, Vol. 3876:265-284, 01 2006.
Barber, R. F. and Duchi, J. C. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint 1rXiv:1412.4451, 2014.
Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theo- retical Computer Science, 9(3-4)221 1-777 2014.
10

---

Optimal Survey Design for Private Mean Estimation
Ebadi, H., Antignac, T., and Sands, D. Sampling and par- titioning for differential privacy. In 2016 14th Annual Conference Privacy, Security and Trust (PST), pp. 664-673,220 2016.
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhod- nikova, S., and Smith, A. What learn privately?
SIAM Journal Computing, 40(3)7993-826 2011.
Kempf-Leonard, K. Encyclopedia of Social Measurement. Elsevier Science, 2004.
Ferrando, C.. Wang, S., and Sheldon, D. Parametric boot- strap for differentially private confidence intervals. In International Conference on Artificial Intelligence and Statistics, pp. 1598-1618. PMLR, 2022.
Kenny, T., Kuriwaki, S., McCartan, C., Rosenman, E.
T. R., Simko, T., and Imai, K. The use of differential privacy for census data and its impact on redistricting: The case of the 2020 U.S. Census. Science Advances, 7 (41):eab33283, 2021.
Force, A. C. T. et al. New considerations for survey researchers when planning and conducting rdd telephone surveys in the US with respondents reached via cell phone numbers. Deerfield, IL: American Association for Public Opinion Research, 2010.
Kulkarni, T., Jälkö, J., Koskela, A., Kaski, S., and Honkela, A. Differentially private Bayesian inference for gener- alized linear models. In International Conference on Machine Learning, pp. 5838-5849 PMLR, 2021.
Frankel, M. R. and Frankel, R. Fifty years of survey sam- pling in the United States, The Public Opinion Quarterly, 51:8127-S138, 1987.
Lee, J. and Leyffer, S. Mixed Integer Nonlinear Program- ming, volume 154. Springer Science & Business Media, 2011.
Gaboardi, M. and Rogers, R. Local private hypothesis test- ing: Chi-square tests. arXiv preprint arXiv:1709.0711 2017.
Li, N., Qardaji, W., and Su, D. On sampling, anonymization, and differential privacy or, k-anonymization meets differ- ential privacy. In Proceedings of the 7th ACM Symposium Information, Computer and Communications Security, pp. 32-33, 2012.
Gaboardi, M., Lim, H., Rogers, R., and Vadhan, S. Differen- tially private chi-squared hypothesis testing: Goodness of fit and independence testing. In International Conference on Machine Learning, pp. 2111-2120 PMLR, 2016.
Li, X., Cao, Y., and Yoshikawa, M. Locally private stream- ing data release with shuffling and subsampling. In 2023 IEEE 39th International Conference on Data Engineering Workshops (ICDEW), pp. 125-131, April 2023a.
Geng, Q. and Viswanath, P. The optimal noise-adding mech- anism in differential privacy. IEEE Transactions on In- formation Theory, 62(2):25-951,, 2015.
Li, X., Li, N., Sun, W., Gong. N. Z., and Li, H. Fine-grainee poisoning attack to local differential privacy protocols for mean and variance estimation. In 32nd USENIX Secu- rity Symposium (USENIX Security 23), pp- 1739-1756, 2023b.
Ghosh, A., Roughgarden, T., and Sundararajan, M. Uni- versally utility- maximmiing privacy mechanisms. In Pro- ceedings of the Forty-Firs Annual ACM Symposium on Theory of Computing, STOC '09. pp. 351 351-360, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 978 1605585062.
Lin, S., Bun, M., Gaboardi, M., Kolaczyk, E. D., and Smith, A. Differentially private confidence intervals for pro- portions under stratified random sampling. Electronic Journal of Statistics, 14(5):4555-149 2024.
Green, D. P. and Gerber, A. S. Can eggistration-basel sam- pling improve the accuracy of midterm election forecasts? Public Opinion Quarterly, 70(2):197-223, 2006.
Lohr, S. L. Sampling: Design and Analysis. Chapman and Hall/CRC, 2021.
Inusah, S. and Kozubowski, T. J. A discrete analogue of the Laplace distribution. Journal of Statistical Planning and Inference, 13603):1000-1102, March 2006. ISSN 03783758.
McSherry, F. D. Privacy integrated queries: an extensible data analysis. In Proceed-
platform for ings the 2009 ACM SIGMOD International Conference on Management of data, pp. 19-30, 2009.
the
Joy. J. and Gerla, M. Differential privacy by sampling. arXiv preprint / 2017.
Neyman, J. On the two different aspects of the representative method. Journal of the Royal Statistical Society Series A, 97:558-608 1934.
Ju, N., Awan, J., Gong, R., and Rao, V. Data augmenta- tion MCMC for Bayesian inference from privatized data. Advances in Neural Information Processing Systems, 35: 12732-12743, 2022.
Ross, S. A First Course in Probability. Pearson Prentice Hall, 1974. ISBN 978-0- 13--0-333-33333

---

Optimal Survey Design for Private Mean Estimation
Santos-Lozada, A. R., Howard, J. T., and Verdery, A. M. How differential privacy will affect understanding of health disparities in the United States. Proceedings of the National Academy of Sciences, 137244) 2020.
Schein, A., Wu, Z. S., Schofield, A., Zhou, M., and Wallach, H. Locally private Bayesian inference for count models. In International Conference on Machine Learning, pp. 5638-5648. PMLR, 2019.
Smith, A. Privacy-preserving statistical estimation with opti- mal convergence rates. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing. STOC '11, pp. 813-822, New York, NY, USA, 201 I. Associa- tion for Computing Machinery. ISBN 978 1.
Ullman, Cs7880:
Rigorous approaches to URL https://wwi
data privacy, 2017.
khoury. htwprrthheaateeeeeeeeeeeeeeeeeee
http:/hhmem/ummmeeee juulljullann. cs 2s7880s17/EWlsol.ppct Lecture notes.
Wang, Y., Mitra, S., and Dullerud, G. E. Differential pri- vacy and minimun-variance unbiased estimation in multi- agent control systems. PAAC-PapesOOnLiee 50(1); 9526, 2017.
Wang, Y., Kifer, D., Lee, J., and Karwa, V. Statistical ap- proximating distributions under differential privacy. Jour- nal of Privacy and Confidentiality. 8(1), 2018.
Wang, Z., Cheng, G., and Awan, J. Differentially private bootstrap: New privacy analysis and inference strategies. arXiv preprint arXiv:2210.06144 2022.
Warner, S. Randomized response: survey technique for eliminating evasive answer bias. Journal of the Amer- ican Statistical Association, 60(309):63-69, 1965. ISSN
01621459, 1537274X.
Wu, and Hamada, M. Experiments: Planning, Analysis, and Optimization. John Wiley & Sons, 2011.
12

---

Optimal Survey Design for Private Mean Estimation
A. Proofs and Technical Details
Lemma A.I. For all y >
(1- log(1 + 4) - - -1+ log(1 + y) 0.
(10)
Proof. First, since we focus on the positive real line (y > 0), we can do change of variable by letting e - 1 with
domain x > 0, then (10) becomes
xe
6
We can multiply through by (e* - 1)2 to give us the equivalent of problem of establishing that h(x) > where
h(x)= = (xe" 2e + 2)² + (x 1)(e² - 1)
To analyze h(r), we compute its derivatives to the third order:
dh(xr) =e 2x (2x² 4r + 3) + 2c (x - 2) + 1,
dx
d
=2E (e" (2x² -2x
2x + 1) + - 1).
dx²
dh(())) -2xe (Axe" + 1).
dr
We begin by noting that <>)( dx
>
0 for all x > 0, which implies that dh(x)
dizt is increasing. Since
d = 0, it follows du
that dhh(zr) dzd > 0 for all x >> 0. By the same argument, knowing that Finally, since h(0)- 0, we establish that h(x) > for all æ > 0.
dh(ar)
O, we conclude that dh
de 0 for all > 0.
dx
Theorem 4.1 (Strong Convexity). Let ae N,, and 1) be given for all i = I,...,k. Then, the continuous relaxations of the variance objectives (4), (5) and (6), with (ni,..., nz) replaced by a continuous vector x E C2 == {x E R$ n. v; < N₁, Vi), are strongly convex.
k.
Σ x2
Proof. Since we intend to prove that the variance objective is strongly convex on the reals, we substitute æ E R4 for n in the proof for distinction. We will first prove that the variance objective strongly convex as function of æ (without the constraint Σ x4 = 17) and then verify that they remain strongly convex under the constraint of Σ H; = 77
Let (n()) (4). The Hessian matrix H is diagonal matrix with diagonal entry (Hg, )ss as follows:
02 g1 dx,² (11, mR) 2a,
of
(x, + log (1+ + 9t) cs (4r; + 3c,) log(1 + (:) + +c3
(1I)
x
1,{(x, c2)2 log (1
5 25
which is positive for x; E (0.n) n) for all = 1...., k. where c, = (exp (c/Af) 1). This is because the first term and the denominator of the second term of (11) are clearly positive for all m; (0, 7) and hence it remains to check the numerator of the second term; by letting y
&u and completing the squares, we have
(x: 2 log 2 (1 + S c:(Ax; + 3c:) log(1 1 4 + 3 3;
C
+ c;)) log 2 (1 + vi) - c144 C/
+ +c;) log(1 (1 + + + 3c
y/i
1 2 log 2 (1 w:) (3+ +
4
(1
log y1) +
y/1
y/
(1+ log([ vi) -2 1 + log(1 + yi)
=
yi
>0 (Lemma A.1).
13

---

Optimal Survey Design for Private Mean Estimation
Similarly, let (2()) (5) and (2(n) (6). The Hessian matrix Hga is diagonal matrix with diagonal entry (Hg2)a
which are both 2 and the Hessian matrix ga a diagonal matrix with diagonal entry (Hgs)st 20 positive for 2, (0) for all i ,,....
Since 9j is strongly convex with respect to (#1..... ( 11,1, for j = 1,2,3, it remains to show that they are strongly convex under the constraint 7) Ei= Ty. Let
Σ 2 and a, b P. For E (0, 1). gj(ta (1 1)6) ig,(0 (a) (1 t)g;(() (b) because a, b dom(g)); meanwhile, ta + (1 t)b P due to the convexity of the constrained subspace. Therefore, the strong convexity holds for additional box constraint, i.e. p (1II....................... Ikk.
[ 2x)
Ex 17, 0, 24 < N.).
Proposition 4.2 (Closed-Form Solutions for Population Mean). If M, is DLap or TuLap with as = No and assume that 1T/(2 Nln & 1 for all i, the continuous solution of (5) and (6) under the constraint of C2 have a closed form 2; (T, (a, N,N,,)nn where T? = of for DLap and T. = of + 12 for TuLap.
1
Proof. Consider
N
Hs + (exp (c/Af) 1)N;
min N:)'
2
+
(exp (e/Af) 1)2
s.t. Σ 84 = 17.
We can write its Lagrangian as
h
N
Ti + 2 2. + (exp (e/Af) 1)
L(x,V) N.
+ v( Σ xs - m))
(exp (E/Af) - 1)
The KKT condition implies that for all 1 < i S k
aL
- +
=v=0
N.
2,
(OND (e/A-///
aL
Σ 33 17 17
0v
Then, v vEEN + (oxp (xp(r/Af)-1)/
2
2, 2,² T implies o Nr as the LHS of the equation is constant for all i, Therefore,
N.N N 7
where 7,2 of for Diserete Laplace and 7? of + for TuL.p.
12
Proposition 4.4 (Closed-Form Solution of Purely Laplace Variance for Population Mean). Under the constraint of Cu, the purely DP variance from the Laplace mechanism (8) is minimized at x = (N:/ E Niyn for all i.
Proof. We can express the problem as an squality-constraine minimization problem
ENp(
( N,)2
s.t. Σ 53 7
where, with (e/Aff 1,)(() 2 log 2 (1+ 5)
strongly convex w.r.t y. Its Lagrangian is
I(x.v) Σ Nip( N.
11) ( N2
+ vl
14

---

Optimal Survey Design for Private Mean Estimation
The KKT condition implies that for all sisk k
ar.
1 N.) + +V= 0
B1.
Σ i3 - 11
OV
Thus, - ( =... 4'( N2 ). Note that ip is strongly convex if and only if y is strictly increasing, which #) 02 implies Ni N2
No is sufficient and necessary condition for the system of equations to hold. Now, since E and 2; N, (i.e. bN, for some b E IR, I. bΣ N₂ and hence b I which gives
" N₂ for all i, # NN:
1³ -²= = PE (
Lemma 4.5 (Range to Search for Integer-Optimal Design). Let 91, 92, be the objective function from (4), (5), (6) respectively, and Cg such that x² = arg ming gj (2), then
n" = arg min Oj (n),
(9)
1
is located within (r) = {x: | x=112 S Sr with r = (2g ) ()(x)) for any given j E {1, where À
the smallest eigenvalue of the Hessian of gj (x*) and Vinit. = arg ming (n) with = (n E N Σ nd = n, |x,]] -
n, $ [x]
Proof. Let Ly(c)= = fx f(x)= & cf be the level set of f at c. For any fixed j E {1,2,3), let
1x(x) = M1 (x²) + Vg,(=*) x²) + 2 || - xx 112
We see that, for any c E I. Lg, (c) S L1, (c). Thus, we plug 93 (Mimit) in and get
n. E Tugs (gy (nim..) S Ta, (gg (Timm))).
Now, to calculate the radius of Lt, (gg (Nini.))), )), we look at the boundary of it, where {x (z(x)) = =g, ()(iii)))) ). Then, the set of boundary points satisfy
A 11 x²1
9y (Tiii.)) = 9)((")) + (zz(x") [x -x") =g)(x*) || 1=
The conclusion follows we set the radius r = 2(1 (Nimit.) - 99 (x*) ))/A such that n² E B (r).
15


Reviews:
[{"review_id": "EWuUufKds9", "reviewer": "Reviewer_TMRh", "summary": "This paper develops a stratified sampling scheme that minimizes variance while ensuring differential privacy (DP) under the Laplace, Discrete Laplace, and Truncated-Uniform-Laplace mechanisms. The key insight is that stratified sampling can amplify privacy guarantees, but optimal allocation of samples across strata must account for the effect of privacy noise. The authors formulate the problem as an optimization task, determining the optimal subsampling sizes to minimize variance while maintaining a fixed total sample size. They prove the strong convexity of the variance objective, derive closed-form continuous solutions for specific DP mechanisms, and propose an efficient algorithm for finding the optimal integer solution. The results demonstrate that ignoring DP effects can lead to significant variance inflation, and their method offers a principled way to balance privacy and accuracy in survey design.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your questions. We are happy to address them below:\n\n- 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.\n\n- 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.\n\n- 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%.\n\nPlease let us know if our responses have addressed your questions or if you have any remaining concerns about the paper.\n\nWe 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.", "claims_and_evidence": "See questions", "methods_and_evaluation_criteria": "See questions", "theoretical_claims": "See questions", "experimental_designs_or_analyses": "See questions", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "- Since the analysis is limited to three specific DP mechanisms, could the author discuss the extension to consider alternative frameworks such as Gaussian DP or Rényi DP? Would it benefit the utility or computation results?\n\n- For equation (1),  do we need the constraint $n_ i\\leq N_ i$? That is, do we allow sub-sampling with replacement?\n\n- This framework seems to assume that $\\sigma_i$, the population variances, are known. Though in the discussion, the authors claimed that a pilot study is commonly conducted in practice, would the small portion of pilot samples further introduce a large variance in the objective function? How is it going to affect the accuracy of the solution?", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "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": "HT5iuBqUnH", "reviewer": "Reviewer_kmJ8", "summary": "This submission is about designing stratified sampling schemes for surveys conducted with differential privacy. In stratified sampling, groups may be surveyed at different rates and these per-group estimates then combined. This is a ubiquitous survey method.\n\nThe survey setting is an important one for statistical privacy, but there is not much work on it. The starting point of this paper is that is may be better to design the survey with privacy in mind, rather than independently combining \"the best nonprivate survey\" with \"the best privacy mechanism.\" Notably, the choice of stratification interacts with the privacy guarantees from subsampling.\n\nFor a class of surveys and privacy mechanisms, this paper shows how the task of finding the lowest-variance private survey design can be solved optimally and efficiently.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not check proofs carefully; the claims seem to make sense.", "experimental_designs_or_analyses": "The simulations seem appropriate.", "relation_to_broader_scientific_literature": "The submission grounds itself well in the existing literature and clearly identifies the gap it fills.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "The submission is well-written and well-constructed. I found it very easy to follow.\n\nThe analysis here is limited: we only consider a few noise distributions and a certain family of variance objectives. The approach assumes exact access to quantities which will not usually be known (e.g., the true per-stratum variances). This is not a fully-formed solution, but I regard it as a large step toward it.", "other_comments_or_suggestions": "none.", "questions_for_authors": "none.", "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": "HtIaELVZqm", "reviewer": "Reviewer_RCeZ", "summary": "The authors propose a DP stratified sampling scheme that can be optimized for various objectives such as population mean estimation or an A-optimal design. The main contributions are a general algorithm to solve the mixed-integer programming problem this creates, as well as closed-form solutions for important settings.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n- **(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.  \n\n  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.\n\n- We will update the text size in the figures to match the font size in the main content to improve readability.\n\n- 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.", "claims_and_evidence": "All theoretical results are accompanied by proofs in the appendix.", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense for the problem.", "theoretical_claims": "I looked through the proofs in Appendix A, but did not examine them in great detail. I did not notice any issues.", "experimental_designs_or_analyses": "I examined each of the experiments the authors present and did not notice any major issues. However, there are a few features of the figures that the authors might further analyze. For example, we see a strong effect for the Laplace Mechanism in Figure 2 where the variance ratio increases monotonically for epsilon < 1 and then decreases monotonically for epsilon > 1. A similar effect is observed in Figure 6. What is happening here?", "relation_to_broader_scientific_literature": "The key contribution of the paper is optimal survey design for private estimation, which (as far as I am aware) has not been previously explored in the DP literature.", "essential_references_not_discussed": "I am not aware of any essential references not discussed.", "other_strengths_and_weaknesses": "The authors identified a gap in the DP literature, successfully derived a solution, and provided a thoughtful experimental evaluation.", "other_comments_or_suggestions": "1. The figures are difficult to read in their current form; I ask the authors to please update the text size in the figures to match the remainder of the document. \n2. I had trouble understanding Table 1 in Section 1 given what had been introduced so far at that point in the work. It wasn't until after reading to Section 5 that I was able to go back and understand the point the authors were making. I would suggest the authors either add more context initially or move Table 1 to later in the document.", "questions_for_authors": "I have no additional questions for the 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": "lkFx3jOBMC", "reviewer": "Reviewer_o79u", "summary": "This paper studies how to estimate a population mean from surveys collected from different groups of people. Differential privacy is required at the level of each group At a high level, the mechanism randomly samples users from each group, who then send in their responses plus noise. The population mean is then a weighted average of the received responses. There are free parameters of the algorithm, namely the number of users to sample in each group, and depending on the variance estimate, these parameters can be optimized. Specifically, for three common types of noise distributions, the number of users for each group is a convex optimization problem, and can be selected using convex optimization. For special parameter choices, the paper derives closed-form solutions for this optimization problem, and in general, they show that the optimal solution can be found using exhaustive search in k dimensions (k is the number of groups). They demonstrate experimentally, the optimization procedure can reduce variance by a factor of 2-4, and the searching algorithm runs efficiently for up to moderate (<30) values of k.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing that our work contributes to the growing trend of incorporating differential privacy into fundamental statistical methodologies, particularly in stratified sampling.\n\n- 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%.\n\n- **In Proposition 3.4**, the nominal privacy budget $M_i$ is given by  \n  $$\\log \\left( \\frac{\\exp(\\epsilon/\\Delta f) - 1 + q_i}{q_i} \\right)-DP$$\n  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.  \n\n  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.  \n\n  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.\n\n- 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.", "claims_and_evidence": "Most of the claims in the paper are adequately supported by theorems and experimental evidence. There is one claim I feel needs more evidence, which is the local differential privacy guarantee.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are adequate.", "theoretical_claims": "I did not closely check the theoretical claims, but they seem reasonable.", "experimental_designs_or_analyses": "I did not check the experimental designs, but they seem reasonable.", "relation_to_broader_scientific_literature": "This paper fits in both the differential privacy and statistics literature. It continues a trend towards adding differential privacy to fundamental statistical methods, including stratified sampling, the setting considered here.", "essential_references_not_discussed": "I cannot think of essential references not already discussed.", "other_strengths_and_weaknesses": "The algorithms in the paper are simple and easy to implement. This applies to both the estimation scheme, which is based off of simple local DP methods, and to the optimization algorithm, where the authors are very clear about how the various convex optimization solvers are being used.\n\nA negative about the work is that it requires lots of prior knowledge to be known about the sample, namely their variances. It is somewhat common to make such assumptions in statistics, but it seems a bit more complicated in the privacy setting since it requires knowing something a priori about the private data.", "other_comments_or_suggestions": "None", "questions_for_authors": "There is currently no quantitative explanation of the local differential privacy guarantee of the algorithm. I believe it should be a factor of $$N_i / n_i$$ higher than the central DP guarantee. This seems like it could be quite high; are there examples where the sampling probability is not too low (like >0.3 for example)? Do we gain anything statistically by taking a large fraction of samples?\n\nWhen can we expect to have accurate estimates of variances in each group in a private setting? Can we use existing work to privately measure the population variance under DP?", "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:

Meta-review: This paper introduces a principled framework for designing optimal stratified sampling schemes under differential privacy (DP) to estimate population means. The authors identify and address a key challenge: while stratified sampling is a classical technique to reduce variance, naïvely applying it under DP, without accounting for privacy amplification effects, can significantly degrade statistical efficiency. The paper proposes a variance-minimizing design tailored to the Laplace, Discrete Laplace, and Truncated-Uniform-Laplace mechanisms, and provides both theoretical analysis (including convexity guarantees) and efficient integer optimization algorithms for implementation.

This paper addresses a timely and foundational problem in the intersection of statistics and differential privacy, and does so with rigor, clarity, and practicality. It should be of interest to researchers in both theoretical DP and statistics.
Decision: Accept (poster)