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 minimize the variance of a mean estimator, which comprises data randomness and additive privacy noise centered at zero. 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. Suppose there are k groups (strata) of people Di with size Ni, i = 1,..., k, that make up the entire population. In each group i, Yij represents the feature of the j−th individual, j = 1,..., Ni, which has mean µi and variance σi2 with bounded support. In a local DP setting, instead of Yij, Zij = Yij + Wij is the privatized response one can access, where Wij is the i.i.d. additive noise with mean 0 and finite variance γ 2 depending on ni, Ni and ϵ. Since we can only draw ni samples from group Di with a total sample size of η, the constrained minimization problem of interest becomes arg min Pk i=1 αi 2 ni σi 2 + γ 2 (ni, Ni, ϵ), subject to P ni = η, where ni is searched over N, αi is weight, and η is a pre-determined total sample size. This problem is classified as nonlinear integer programming, where both the objective and the constraint are convex; specifically, the variance objective is strongly convex (Theorem 8). As it will be addressed later using the Lagrangian, which introduces a continuous multiplier for the equality constraint, it can be generally treated as a mixed-integer programming problem [Lee and Leyffer, 2011]. We assume αi, Ni, σi, (i = 1,.., k) and η are given or determined prior to subsampling. The following examples show how the αi can be chosen to optimize for various variance objectives. Example 2 (Population Mean Estimation). One of the most important parameters to estimate in survey sampling is the population mean. For group i, the group mean µi can be estimated by µ̂i = n1i Pni j=1 Zij, which is an unbiased estimator of µi. The population mean µ can thus be unbiasedly estimated by µ̂ = Pki=1 Ni µ̂i Pki=1 Ni. Then, Var(µ̂) = (P 1 Ni)2 Pk i=1 Ni 2 ni σi 2 + γ 2 (ni, Ni, ϵ). Thus, the constrained minimization problem is: arg min Pk i=1 Ni 2 ni σi 2 + γ 2 (ni, Ni, ϵ) s.t. P ni = η, n ∈ Nk. This aligns with (1) as αi = Ni for all i. Example 3 (A-Optimal Experimental Design). Another important case is the A-optimal experimental design, where we minimize the trace of the covariance matrix subject to the constraint. Denote the covariance matrix of (µ̂1,..., µ̂k)⊤ as Eµ, then the A-optimal experimental design is arg min tr(Eµ) = Pk i=1 1 ni σi 2 + γ 2 (ni, Ni, ϵ) s.t. P ni = η, n ∈ Nk. This algins with (1) as αi = 1 for all i. Remark 6. There are other interesting settings that fit into this framework. For instance, one may be interested in a unit-free optimal design by setting αi = 1/σi. Now, we look into the variance component from the privacy mechanism, that is, γ 2 (ni, Ni, ϵ) for all i, where the subsampling comes into play. Rather than using qmax for all k groups as in Lemma 5, we consider qi = nNii such that Mi ◦ Sni satisfies ϵ−DP, where Mi is the privacy mechanism for group i and Sni is the subsampling operator which chooses a subset of size ni from the group i. This ensures every person gets the same level of central DP privacy protection, regardless of their group size. Proposition 7. If the nominal privacy budget of Mi is log exp (ϵ/∆f)−1+qi qi, then Mi ◦ Sni satisfies ϵ−DP. Proposition 7 establishes the dual privacy guarantees for our mechanisms, ensuring uniform privacy protection for all individuals from public disclosure. Example 4. Applying Proposition 7 to the three mechanisms, we have the following, where si = 1/log 1 + exp (ϵ/∆f)−1 Ni ni: • The Laplace mechanism for local ϵ−DP is Zij = Yij + si · Lap(0, 1).Then, the variance objective becomes Pk i=1 αi 2 ni σi 2 + 2 log−2 1 + exp (ϵ/∆f)−1 Ni ni. (4) • The Discrete Laplace mechanism for local ϵ−DP is Zij = Yij + Kij, where Kij ∼ DLap (pi = exp(1/si)). Then, the variance objective becomes Pk i=1 αi 2 ni σi 2 + 2 ni Ni (exp (ϵ/∆f) − 1 + Ni) (exp (ϵ/∆f) − 1)2. (5) • The Truncated-Uniform-Laplace mechanism for local ϵ−DP is Zij = Yij + Kij + Uij where Kij ∼ DLap (pi = exp(1/si)). and Uij ∼ Uniform(− 12, 21). Then, the variance objective becomes Pk i=1 αi 2 ni σi 2 + 1 12 + 2 ni Ni (exp (ϵ/∆f) − 1 + Ni) (exp (ϵ/∆f) − 1)2. (6) By using an exhaustive search, the complexity of solving (1) is η−1 k−1 [Ross, 1974], motivating the need for a customized optimization method.

In this section, we develop the optimal integer design which solves (1), introduced in Secion 3. In Section 4.1, we discover and prove the strong convexity of the variance objectives under Laplace, DLap, and TuLap mechanisms, which enables us to precisely locate the optimal design in Section 4.3. In Section 4.2 we also derive some closed-form solutions over continuous space for some special cases. We begin by establishing the strong convexity of our variance objectives. Strong convexity ensures a unique optimum over the reals and provides a quadratic lower bound for the objective function. These properties are leveraged in Section 4.3 to develop an efficient optimization algorithm. Theorem 8 (Strong Convexity). Let αi, Ni, σi, and η be given for all i = 1,..., k. Then, the continuous relaxations of the variance objectives (4), (5) and (6), with (n1,..., nk) replaced with (x1,..., xk) ∈ Rk+ such that P xi = η, are strongly convex. Proof Sketch. We first prove that the variance objectives are strongly convex over (0, η)k and then show that this property continues to hold under the convex constraint. For the DLap and TuLap mechanisms, strong convexity follows by inspection; for Laplace, strong convexity is established by change of variables and successive differentiation. Strong convexity in Theorem 8 guarantees a unique solution over the reals. A straightforward approach to solving it is using Newton’s method with established R packages such as optim, nloptr or alabama. However, solving the mixed-integer programming problem is more complex, as existing packages do not provide direct solutions. Strong convexity is 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. A closed-form continuous solution is 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 αi, intriguing results emerge when αi = Ni, the case of population mean estimation. Proposition 9 (Closed-Form Solutions for Population Mean). If Mi is Discrete Laplace or TuLap and αi = Ni for all i, the continuous solution of (5) and (6) under the constraint (x1,..., xk) ∈ Rk+: η = P xi have a closed form x∗i = [(τi Ni)/(P τi Ni)]η, where τi2 = σi2 for Discrete Laplace and τi2 = σi2 + 1 12 for TuLap (x∗i plays the role of n∗i). Proof Sketch. We first formulate the Lagrangian of the constrained optimization problem. The KKT conditions give a proportional relation xi ∝ τi Ni for all i. Then, the constraint provides a unique solution for the xi ’s. Remark 10. The solution of (5) is identical to the naive stratified sampling design, also known as the Neyman allocation [Neyman, 1934] or the optimal allocation [Kempf-Leonard, 2004], where the sample size allocated to each group is proportional to both the variability and the size of the group. In contrast, (6) has a regularization effect on its sample sizes that results in a different allocation. As for the Laplace noise, although we were unable to derive a general closed-form solution for (4), we have an interesting 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 (Pk i=1 Ni 2 xi σi 2) (P Ni)2. (7) Under the constraint of C = x ∈ Rk: P xi = η, the non-private variance (7) is minimized at x∗i = (σi Ni / P σi Ni)η, for all i. On the other hand, we define the pure DP variance as (Pk i=1 Ni 2 xi 2 log−2 1 + exp (ϵ/∆f)−1 xi /Ni) (P Ni)2. (8) Proposition 11 (Closed-Form Solution of Purely Laplace Variance). Under the constraint of C = x ∈ Rk: P xi = η, the pure DP variance from the Laplace mechanism (8) is minimized at x∗i = (Ni / P Ni)η, for all i. Proof Sketch. In addition to the similar Lagrangian proof argument in Proposition 9, we use the result that φ(y) = y2 log−2 1 + yc is strongly convex, as proved in Theorem 8, to identify the solution form. Proposition 11 indicates that the sample size allocated to each group is merely proportional to the size of the group. This corresponds to the concept of the proportional allocation [Kempf-Leonard, 2004]. It is surprising that the solution is independent of ϵ as (8) can be blown up when ϵ drops. Although ϵ 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. Since Theorem 8 only ensures the existence and uniqueness of the continuous-optimal design, in this section we use the strong convexity property to 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. The search over integer points satisfying the convex constraint is finite, as the set of feasible integer-valued solutions, D = n ∈ Nk: P ni = η, is inherently limited. Moreover, the strong convexity of the variance objective provides a quadratic lower bound, ensuring that a 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. Lemma 12 (Range to Search for Integer-Optimal Design). Let g1, g2, g3 be the objective function from (4), (5), (6) respectively, and C = x ∈ Rk: Pk i=1 xi = η, x > 0 such that x∗ = arg minC gj (x), then n∗ = arg min gj (n), (9) D is located within Bx∗ (r) = x: ∥x − x∗ ∥2 ≤ r with r = q 2(gj (ninit.) − gj (x∗))/λ for any given j ∈ 1, 2, 3, where λ is the smallest eigenvalue of the Hessian of gj (x∗) and ninit. = arg minE gj (n) with E = n ∈ Nk: P ni = η, ⌊x∗i ⌋ ≤ ni ≤ ⌈x∗i ⌉. Applying the result of Lemma 12, we propose Algorithm 1 which starts with the continuous solution, identifies a small set of candidate integer solutions, and then identifies the integer-optimal design within this smaller set. Algorithm 1 Integer-Optimal Design Input: x∗ (the optimal continuous solution) and Hessian matrix of g: Hg (x∗) for i = 1,..., k − 1 do Define Ti = ni ∈ N: ⌊x∗i ⌋ ≤ ni ≤ ⌈x∗i ⌉ end for Define T = (n1,..., nk−1, nk): nk = η − Pk−1 i=1 ni, where (n1,..., nk−1) ∈ T1 ×... × Tk−1 Select the nearest integer design ninit. = arg minn∈T g(n) Calculate the smallest eigenvalue λ of Hg (x∗) Calculate radius r = q 2(g(ninit.)−g(x∗)) λ for i = 1,..., k − 1 do Define Si = ni ∈ N: x∗i ≤ ni ≤ max(x∗i + r, η) end for Define S = (n1,..., nk−1, nk): nk = η − Pk−1 i=1 ni, where (n1,..., nk−1) ∈ S1 ×... × Sk−1 Select the integer-optimal design n∗ = arg minn∈S g(n) by an exhaustive search. Output: n∗ Theorem 13 (Integer-Optimal Design). Algorithm 1 outputs the integer-optimal design (9). Remark 14. Before entering the second for-loop in Algorithm 1, the practitioner may decide to check the optimality gap [g(ninit.) − g(x∗)]/g(x∗). If the optimality gap is sufficiently small, it may be acceptable to adopt the suboptimal design ninit.. This is demonstrated in Section 5.3. Figure 1 illustrates the big picture of Lemma 12 and Algorithm 1. The dotted blue ellipse represent a level set of the variance objective g. Our method starts from selecting the nearest integer design ninit. and uses it to establish a ball Bx∗ (r) that contains the integer-optimal design with radius r = q 2(gj (ninit.) − gj (x∗))/λ. Then, the solid green cube represents the valid and possible designs for the integer-optimal design, which can potentially be farther from the initial nearest integer design and might not be unique. Remark 15. Strong convexity of the variance objective plays a key role in identifying the optimal design. While an exhaustive grid search has η−1 k−1 different combinations, scaling O(η k−1) when k is fixed, Algorithm 1 reduces η to 2r, resulting in a much lower complexity of O (2r)k−1. We show in Section 5 that r is relatively small.

We numerically illustrate our method through simulation studies. Section 5.1 compares compares variances between naive and DP-aware stratified sampling. Section 5.2 explores the interplay between the non-private and purely DP designs. Section 5.3 showcases the computational efficiency of our algorithm. The input of Algorithm 1, x∗, is obtained by package nloptr and alabama in R. All computations, including runtime, were conducted on a single-core cluster. As shown in Table 1, stratified sampling under our DP framework 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 σ 2 = (0.08, 0.082, 0.083, 0.084) and a total sample size η = 200. We plot the variance ratio from a naive subsampling scheme to that of the integer-optimal design while varying ϵ from 0.01 to 100. For the population mean case, Figure 2 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 < ϵ < 10. Under TuLap, the variance ratio can reach as high as 4. Note that DLap gives the same design for population mean. For the A-optimal case, it reveals a similar trend for the Laplace and TuLap mechanisms as observed in the population mean case (See appendix). In Section 4.2, 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 pure-Laplace noise designs. In our simulation, there are 3 groups with population sizes N = (1000, 2000, 3000), σ 2 = (0.08, 0.081.5, 0.082), ϵ = 1 and a total sample size η = 200. We use the setting of the population mean with Laplace noise. Figure 3 demonstrates that the integer-optimal design largely interpolates between the no-noise and pure-noise designs. As privacy protection strengthens, the design shifts closer to the pure-noise configuration; conversely, with weaker privacy protection the optimal design more closely aligns with the Neyman allocation. Our problem is formulated as a mixed-integer programming task, which lacks an off-the-shelf solution method, particularly in R. While exhaustive search becomes infeasible as either the total sample size η 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 η values—up to 100, 000 and more—when k is kept at a reasonable scale. In this simulation, there are 10 groups with N = (N1, N2,..., N10) = (20000, 19000,..., 11000) and σ 2 = (σ12, σ22,..., σ10 2) = (0.081.1, 0.081.2,..., 0.082) and ϵ = 1. We measure the computation time for an exhaustive search and for our proposed algorithm as the total sample size η increases from 30 to 48, using the population mean case with Laplace noise. Figure 4 demonstrates that the exhaustive search exhibits exponential growth in computation time, whereas Algorithm 1 effectively mitigates this growth. In fact, we see that Algorithm 1 can effectively find the optimal solution with sample sizes up to 105 in less time than an exhaustive search takes for η = 30. We consider k groups with N = (N1, N2,..., Nk) = (10000 + 1000 · k, 10000 + 900 · k,..., 11000) and σ 2 = (σ12, σ22,..., σk2) = (0.081.1, 0.081.2,..., 0.081+k/10) and ϵ = 1. We implement our full algorithm from k = 2 to 12, locating the optimal design n∗, and that of the first part of our algorithm from k = 14 to 26, locating the nearest integer design ninit.. If r > 1, then as k increases the computation time exhibits exponential growth, which becomes large especially when k ≥ 14. In practice, if r > 1.5 and k is large, we recommend identifying the nearest integer design ninit., corresponding to the first half of the algorithm. In this simulation, it maintains an optimality gap of less than 10−4 from the continuous-optimal design x∗. Notably, locating the continuous-optimal design is independent of Algorithm 1 and requires less than 1 second for any k in the simulation.

We proposed a 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 minimizing variance assuming non-private data, our approach takes into account the noise introduced by privacy mechanisms as well as the privacy amplification by subsampling, ensuring more reliable results under privacy constraints. Our framework is fairly flexible, as it works with three common DP mechanisms: Laplace, Discrete Laplace, and Truncated-Uniform-Laplace. Furthermore, the strong convexity of the variance objective ensures that the optimization problem is well-defined, which leads to solid theoretical results. We also addressed the computational challenges of exhaustive search methods by developing an efficient algorithm for finding the optimal integer design. 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 sample size constraint, while reasonable, may be too strict or not account for more complex scenarios (e.g. chance constraints). Additionally, our algorithm may be inefficient when the search radius r is large. Exploring alternative methods for finding the integer-optimal design could improve efficiency; for example Gurobi, MOSEK, and Julia’s Pajarito all have generic mixed-integer programming packages. Lastly, our analysis is limited to ϵ-DP and the Laplace, DLap, and TuLap mechanisms. Future work could extend our results to other mechanisms and privacy frameworks, such as the Staircase mechanism Geng and Viswanath [2015], Gaussian mechanism, or general canonical noise distributions Awan and Vadhan [2023] as well as the ρ-zCDP [Bun and Steinke, 2016], µ-GDP, and f-DP frameworks [Dong et al., 2022]. We also suggest several promising directions for future research. Incorporating the double privacy amplification effect of subsampling and shuffling [Li et al., 2023b] could enhance privacy guarantees, while resulting in a more complex optimization problem. Another option is to apply our framework to a fully central DP context, assuming the presence of a trusted data curator, which would also give a different variance objective. Finally, extending the framework to accommodate more complex sampling designs, such as multi-stage or adaptive sampling, would broaden its applicability to diverse survey scenarios. These potential advancements would further solidify the role of DP-aware stratified sampling in privacy-preserving data collection.

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.