Private Statistical Estimation via Truncation
Authors: Manolis Zampetakis
Felix Zhou
Venue: NeurIPS 2025 poster ()
Keywords: Theory
Differential Privacy
Truncated Statistics
Computationally Efficient Estimation
Primary area: theory
TL;DR: We introduce a novel framework for differentially private statistical estimation via data truncation.

Abstract: We introduce a novel framework for differentially private (DP) statistical estimation via data truncation, addressing a key challenge in DP estimation when the data support is unbounded. Traditional approaches rely on problem-specific sensitivity analysis, limiting their applicability. By leveraging techniques from truncated statistics, we develop computationally efficient DP estimators for exponential family distributions, including Gaussian mean and covariance estimation, achieving near-optimal sample complexity. Previous works on exponential families only consider bounded or one-dimensional families. Our approach mitigates sensitivity through truncation while carefully correcting for the introduced bias using maximum likelihood estimation and DP stochastic gradient descent. Along the way, we establish improved uniform convergence guarantees for the log-likelihood function of exponential families, which may be of independent interest. Our results provide a general blueprint for DP algorithm design via truncated statistics.

Private Statistical Estimation via Truncation
Manolis Zampetakis
Felix Zhou Yale University felix. wwww@yale. edu
Yale University manolis wwwoliiszampttakkisselaaa..
Abstract
We introduce a novel framework for differentially private (DP) statistical estimation via data truncation, addressing key challenge in DP estimation when the data support is unbounded. Traditional approaches rely on problem-specife sensitivity analysis, limiting their applicability. By leveraging techniques from truncated statistics, we develop computationally efficient DP estimators for exponential fam- ily distributions, including Gaussian mean and covariance estimation, achieving near-optimal sample complexity. Previous works on exponential families only consider bounded or one-dimensional families. Our approach mitigates sensitivity through truncation while carefully correcting for the introduced bias using maxi- mum likelihood estimation and DP stochastic gradient descent. Along the way, we establish improved uniform convergence guarantees for the log-likelihood function exponential families, which may be of independent interest. Our results provide general blueprint for DP algorithm design via truncated statistics.
Introduction
In of data-driven decision-making, differential privacy (DP) has become the gold standard for statistical analysis, ensuring that the inclusion or exclusion of any individual's data does not significantly alter outcomes [20]. DP has widespread adoption, including in the U.S. Census Bureau's data releases [2] and industry applications [21], due to its rigorous guarantees balancing privacy and utility.
Over the past two decades, research has produced private estimation methods for mean estima- tion [45], regression [44], and hypothesis testing [24]. Techniques like the Laplace and Gaussian mechanisms [20]. differentially private empirical risk minimization [13], and DP-SGD [1] have enabled privacy- preserving machine learning.
Despite this long line of work, key limitation remains: there is no seneral-purposs computationally efficient framework for differentially private statistical estimation, when the support of the data is unbounded, e.g., IR.. In such cases, bounding the sensitivity of the statistical estimators a very challenging task and existing methods require case-specific sensitivity analyses, making their broad application challenging. Without a good bound on the sensitivity of an estimator, is impossible to obtain good DP mechanisms with utility-privace tradeoffs.
Data Truncation. One natural approach to reducing sensitivity-and thereby improving privacy- utility trade-offs-is to artificially truncate the data, ensuring that extreme values do not unduly influence the estimation process. Truncation directly controls sensitivity, which crucial in DP settings where privacy guarantees depend on bounding the worst-case impact of single data point. While this technique provides a compelling solution to the challenge of sensitivity control, introduces new issue: bias. Truncation distorts the underlying distribution, leading to inaccurate estimates if not properly corrected. This raises an important question:
Can we leverage techniques from truncated statistics to develop principled framework
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

for reducing sensitivity in differentially private statistical estimation?
The study of truncated statistics has a long history, with recent results providing efficient methods for estimating distributions and regression models under truncation. Notably, works such as Daskalakis al. [17] have developed polynomial-ting algorithms for estimating Gaussian parameters from truncated samples, overcoming computational barriers. However, despite the rich theory of truncated statistics, its potential for designing differentially private estimators remains largely unexplored. In this work, we take a step in this direction by introducing a principled approach that integrates differential privacy with statistical methods designed for truncated data. A novel consequence of our work is the first efficient DP algorithm for estimating the parameters of unbounded high-dimensional exponential families.
1.1 Contributions
Our main conceptual contribution a method for private statistical estimation using truncation. Using this paradigm, we design the first algorithm for privately estimating the parameter of unbounded high-dimensional exponential family distributions. As special cases, we recover algorithms for Gaussian mean and covariance estimation with near-optimal sample complexities.
We write m to denote the dimension of the parameters/suffcciett statisties of an exponential family distribution qe parameterized by 0, and d to denote the dimension of the distribution. Let e, E (0, 1) denote the approximate-DD parameters and a E (0, 1) denote the accuracy parameter. We design the following efficient (s, 8DP algorithms that outputs:
(See Theorem 3.1) an estimate @ for the parameter of an exponential family distribution go such that ||0 15--% || S a with sample complexity that is linear in m and proportional to 1/2, 1/a2, and 3/ae.
(See Theorem 4.1) an estimate á for the mean of a Gaussian N(u,, .)) such that 11 - μ²1 S with sample complexity that linear in d and proportional to l/e, 1/a", and 1/ae.
(See Theorem 4.2) an estimate Σ for the covariance of a Gaussian (0, E²) such that || | --- & || S a with sample complexity that scales as d2 and is proportional 1/e, Ya², and 1/ae.
In particular, Theorem 1 is the first efficient algorithm for privately estimating unbounded high- dimensional exponential families, All prior works consider only bounded or one-dimensional/one parameter cases (see related works in Section 1.2). Theorems 4.1 and 4.2 demonstrate the sample efficiency of our method by recovering the optimal sample complexities for the specific case of Gaussian estimation.
Technical Contributions. The key idea in obtaining our private estimator for exponential familics is to only access data after truncating to appropriate bounded survival set. Then, folklore techniques suffice to estimate the parameters of the truncated distribution. This raises two issues: 1) there may be bias introduced by the truncation and 2) how can choose the survival set?
In Sections 3.2 to 3.5, we first assume we are given a bound R = O(1) on the radius of the norm of the true parameter so that one straightforward choice for the survival set is the ball of radius O(ym) about the origin. Then we address 1) by using stochastic gradient descent (SGD) on the truncated negative log-like likelihood function L over carefully chosen projection set K to ensure strong convexity. The true parameter is a minimizer of L. However, to satisfy privacy, we must use DP-SGD, which requires making multiple passes over the data. This raises further issues since each truncated sample only provides a single unbiased gradient estimate. We overcome this by instead optimizing the empirical likelihodoo İ. which necessitates a uniform convergence result to ensure that the empirical minimizer remains close to the population minimizer.
Shah, Shah, and Wornell [43] also derived a uniform convergence result for exponential families but their proof does not immediately handle truncation. Furthermore, they require O(1/a4) samples, which would lead to sub-optimal sample complexity for Gaussian mean and covariance estimation. Our proof overcomes this limitation by first showing that Ō- E K lies in the projection set of Ż after O(1) samples. Hence f. actually satisfies a uniform convergence at O(7a²) samples.
(PI.) condition, which leads to
2

---

To address 2), we observe that simply estimating the parameter of the truncated distribution yields constant-distance warm start. Appendices B.6 and B.7, we remove the need for a prior by adapting a standard bounding box algorithm for the parameter of the truncated distribution that attains Oppoly (m) ((poly(m)))diitaaie distaacce warm start. This is adapted from folklore algorithm for Gaussian estimation that we generalize to truncated exponential families. Next, to avoid unnecessary poly(m) ----epeddennce in the sample complexity, we further refine this to an (())ddistance warm start by adapting Gaussian estimation algorithm of Biswas et al. [7] that we generalize to truncated exponential families.
Finally, in Section 4, we show that we can derive algorithms for Gaussian mean and covariance estimation from our general algorithm for exponential families. However, to avoid linear dependence on the condition number, we adapt a recursive Gaussian preconditioning algorithm by Biswas et al. [7] which we again generalize to the setting of truncated Gaussians.
1.2 Related Works
DP Exponential Family Estimation. Prior works on privately estimating the parameter expo- nential families focus either on asymptotic guarantees [23], bounded exponential families [6], or mee-dimeensionallon--aaaaa exponential families [6, 37J. In contrast, our algorithms can handle unbounded high-dimensional multi-parameter exponential families.
The first sample-optimal DP Gaussian mean/covariance estimation algo- rithms were due Aden-Ali, Ashtiani, and Kamath [3], who attains rates of Ō +
DP Gaussian Estimation.
log(1/4)
and Ō dP
log(/s)) respectively. However, their algorithms require exponential running time. Recent transformations from robust algorithms to private algorithms obtained the same optimal sample complexities for mean estimation [26] and covariance estimation [27] in polynomial time. See Hopkins et al. [27, Table 1, Table 2] for a detailed summary of prior algorithmic results. The sample complexities are tight up to logarithmic factors [29, 30, 39, 42].
The private Gaussian estimation algorithms of Biswas al. [7] and Karwa and Vadhan [30] are also relevant as we adapt them for truncated exponential families. Note that due to the bias introduced by the truncation step, directly running the adaptations on truncated samples yields biased estimates.
However, we show that these biased estimates suffice as warm starts/preconditionesss.
DP Empirical Risk Minimization. A related line of work develops methods to solve empirical risk minimization problems (see e.g. Bassily, Smith, and Thakurta [5] and references therein). This line of work only handles the sensitivity problem that we describe above when the support of the input distribution is bounded. In the problem of learning exponential families that explore in this paper, these assumptions are often violated and this is one illustration of the importance of the methods that we propose.
Truncated Statistics. The recent seminal work of Daskalakis al. [17] developed the first polynomial-tine tereo algorithms for estimating Gaussian parameters from truncated samples within given survival set. This has led to flurry of developments, including generalizations to truncated exponential families [34, 35], truncated Gaussian estimation with unknown survival sets [32, 35), truncated regression [15, 16, 18], and truncated linear dynamics [41].
Preliminaries
We include the standard preliminaries for differential privacy in Appendix A.
2.1 Notation
We write d for the dimension of the ambient space, m for the dimension of the sufficient statistic for an exponential family distribution qo parameterized by 0, e, 5 for the privacy parameters, and a, B for the accuracy, failure probability parameters. We typically probability when truncating a distribution to survival set S C Rdd For R > 0, we use (r(()) to denote the closed Fuclidean ball of radius R about x. or Bx(X)) to denote the union of closed Euclidean balls of radius R about E X. (=R(X) = {I E X BR(x) X)) denotes R-interior of
p E (0, 1) to indicate the survival
3

---

the argument. We let Sd denote the set of d x d real-symmetric matrices. For A. B E S we write A < B, A A B denote the positive definite and positive semi-definite relations. S indicates the subset of positive semi-definite matrices.
2.2 Neighboring Truncated Datasets
Our guiding principle for designing private algorithms is to discard outlier samples that fall outside some survival set' S to obtain bounded sensitivity. However, given an algorithm A that differentially private on truncated samples, it is not clear how to reason about the privacy guarantees when first truncate dataset and feed it to A, since the truncated datasets may no longer be neighboring. Specifically, let D' be obtained from the dataset D by modifying an entry. Then, depending on whether the modified entry falls in S, the truncated datasets Ds, D's fall into one of three categories: Either 1) D's Dg. 2) D's be obtained from Ds by modifying entry, obtained from Ds by adding/deleting an element.
D'g can be
Below, we formally state the guarantees of preprocessing procedure we employ in addition to truncation and defer its proof to Appendix A.3.
Lemma 2.1. Fix 2 1 and let N E N. Let D) E TRdx be an N-sample dataset, D' E TR be obtained from D by modifying a single entry, and S C Rd. Write Ds, D's to denote the datasets obtained from D, D' by discarding entries that fall outside of S. There is preprocessing algorithm A such that
(i) A(D's) E S" can be obtained from A(Ds) E S" by modifying a single element,
(ii) for any (e, DDP algorithm with respect to neighboring truncated datasets, the compo- sition ((A(Ds) is (E.8 with respect neighboring (untruncated) datasets D, D', and
(iii) if D sampled i..dd. from some distribution p such that p(S) =: p. then A(D) contains i.d. samples from the truncated distribution yd with probability 3, provided N 2( 2("log log()))).
Throughout this work. we only work with truncated distributions with constant survival mass 2 ((1). Thus in light of Lemma 2.1, suffices to analyze the privacy and sample complexity of datasets from the truncated distribution and then incur a sample complexity blowup of O(log(//))))) 1/a) for the untruncated distribution while maintaining the privacy guarantees. From hereonforth, we do not distinguish between the sample complexity of truncated and untruncated samples, but it is understood that we perform this preprocessing to obtain truncated samples. See e.g. Algorithm B. for an explicit example.
2.3 Exponential Families
Exponential families form fundamental class of probability distributions that unify and generalize many statistical models, including the Gaussian, Bernoulli, and Poisson distributions [9]. Their structured mathematical form provides a natural framework for efficient statistical inference, enabling widespread applications in machine learning, information theory, and Bayesian statistics [49].
In this paper, we consider absolutely continuous exponential family distributions over Id
go(z) (x) h(x)) exp TTT)))) r(0))
where h : Rd + R4 is the base measure, T Rd + R" is a sufficient statistic, T(0) log J2 h(x) Txx)) dr is the log partition function that ensures go integrates to 1, and 0 H = (0: A(0) < 6o)
} is the natural parameter of the distribution.
is hard to see that H is convex. We write O C H to be closed, convex subset of the natural parameter space. As we illustrate in Section 4 for Gaussians, it may be necessary to restrict ourselves θ in order to obtain useful properties such strong convexity of the NLL function.
Daskalakis al. [17] also referred this the truncation "Our algorithms are able to handle more general distributions for which the empirical log likelihood function is almost surely differentiable, but we present the case of absolutely continuous distributions with respect to the Lebesgue measure for simplicity.

---

Statistical Assumptions. We now state some common statistical assumptions for estimating (truncated) exponential families. Remark that these are necessary assumptions that appear even in the non-private literature for exponential families 34, 35, 43J. Moreover, these assumptions hold for a variety common distributions such as exponential distributions, Weibull distributions, continuous Bernoulli distributions, and continuous Poisson distributions [34, Appendix BJ.
Assumption 2.2 (Statistical Assumptions).
(SI) (Bounded Condition Number) Al I CoV (T (x), 1 for every 0 E θ. (c.g. isotropic Gaussian satisfies this with 1)
(S2) (Interiority) 0* is in the n-interior (+) of θ for some 1j E (0, i.e (,) C
(S3)
Log-Concaviity Each ga, is log-concave distribution (e.g. isotropic Gaussian)
(S4) (Polynomial Sufficient Statistics) (xx) is a polynomial of given constant degree k = 0()
(e.g. for isotropic Gaussian).
Some remarks about the statistical assumptions are in order.
We relax Assumption (S1) to XI < (T)(T A/ by rescaling the sufficient statistics (x) + T(a)/VA if necessary. Then the condition number becomes A/x. In order to obtain computationally efficient algorithms, some assumptions on the spectrum of Cov [Tv(T(x)) (z)) are made even for non-prie con-privately learning exponential families [43]. Typically, as in the case of Gaussians (Appendix C.4), possible to precondition the distribution so that X = 22(1). Hence we think of as being constant bounded away from O.
Assumption (S2) is usually easy to satisfy just by "blowing up" θ by (e.g. Appendices C.I and C.3 for Gaussians). Thus throughout this work, we think of as a small constant bounded away from O. Assumptions (SI) and (S2) together imply subexponential concentration inequality on the sufficient statistic T T(x) for x ~ qe- (Proposition A.8).
Assumptions (S3) and (S4) together imply an anti-concentration result of polynomials under log- concave measures [12]. This is a crucial ingredient in deriving computationally efficient algorithms for truncated statistics which appears even in the most basic case of learning truncated Gaussians [17]. Alternatively, we may assume that the sufficient statistics belong to a class of functions that satisfy anti-concentration. For simplicity of exposition, we focus the case where T(x) is polynomial.
Computational Subroutines. In order to efficiently implement algorithms, will need access to a few problem-specific subroutines. We emphasize that these are standard computational tasks and specify how they be achieved in the of Gaussian mean and covariance estimation in Appendices C.1 and C.3.
Assumption 2.3 (Computational Subroutines).
(C1) (Projection Acess to Convex Parameter Space) There is poly(m)- projection oracle to θ e 0*
(C2) (Sample Access to Log-Concavy Distribution) For every 0 E θ, we can (approximately) sample from do in poly(d)-time
(C3) (Moment-Matching Oracle) There is an oracle MomentMatch such that given some 7 E I the oracle returns some 0 such that Ezwag [T))) т (approximately) holds in poly (time
We also comment on the problem-specific computational subroutines required by our algorithm.
For simple convex sets like R. half-spaces, Euclidean balls, or hypercubes, there are simple subroutines compute the convex projection onto them. For general convex bodies, suffices to assume access to separation oracle in order to call on the ellipsoid method [25] and implement projection oracle. Thus Assumption (C1) is typically not strong condition. Moreover, our algorithm may require taking projections onto the intersections of closed convex sets which occur when we iteratively reduce the domain of the feasible region. This can be efficiently implemented via Djikstra's algorithm [8, 50].
5

---

There are efficient algorithms to sample from log- concave distributions under additional regularity conditions on qo [14] or when the support is a convex body [36]. Thus Assumption (C2) is not stringent concern.
Finally, there are closed-form solutions for Assumption (C3) in many scenarios such the standard parameterization of Gaussian distributions as an exponential family. In general, a moment matching oracle can be implemented by solving maximum-likelihon estimation (MLE) problem, which is convex optimization problem with efficient solutions (see e.g. Lee, Wibisono, and Zampetakis [34]).
2.4 The Negative Log-Liken Log-Likelihood Function (NLL)
Here we recall some facts about the negative log-likelihood function (NLL) for an exponential family. Let denote the density of an exponential family distribution parameterized by 0 and E(0; z) == - log (0()) be its single sample NLL. can be shown (see e-g. Busa-Fekett et [11]) that the derivative and Hessian (also known as Fisher information) of the NLL for a single sample 9o- are given by
Vol x) = Ey -
v)((0xx) yov [T(),, = 0.
Thus the gradient and Hessian of the population NLL L(0) Ex [((0
follows:
o ( = Eyraga [T(y)] Ex-go- [T())]
(OL( = Cov gm (T)). T()) = 0.
As example, let qe denote the density function of member of some exponential family and oे denote the density truncated to the set S. For any S SCC Rd, we see that the gradient and Hessian of the empirical NI.L [0) x(1) (())) = Σ log (x)(0) for n truncated samples have the following form
n ΣΣ TT
V e (() E By [())
V (0:: Cov y-uq (T(y), ž 0.
Note that under Assumption (S1), both the (untruncated) population and empirical NLL are convex, 1-smooth, and X-strongly convex over θ
3 Privately Estimating Exponential Families via Truncation
Our main result is an efficient conncation-based algorithm for privately learning an exponential family from samples.
Theorem 3.1. Let a, E 10 and suppose the statistical assumptions hold (As- sumption 2.2) and computational subroutines exist (Assumption 2.3). There is an SGD- based (e, D)D algorithm such that given samples from qa-, outputs an estimate Ô satisfy- ing 110 1' < a with probability 1 - B. Moreover, the algorithm has sample complexity _01/22) (0l/2)) log((+/00)) and time complexity poly (n, m, d).
Ō m log(t//2))) X
m (o) a
+
Xane
The exponential dependence on is an artifact of existing truncated statisties methods [35], which uses general anti- cotinnnncentittoon property of polynomials under log-concave measures in order to control the decay in the strong convexity of the truncated log likeelioooo function compared the untruncated counterpart. Moreover, some dependence on 1/A is necessary even when using vanilla SGD to estimate Gaussian parameters. However, for many important exponential families such as Gaussians, this can be mitigated by preconditioning the samples so that X = (1). We demonstrate how to do this for Gaussians in Section 4.2 (Theorem 4.2).
Remark 3.2 (Robustness against Existing Truncation). All of our algorithms only access samples after a preprocessing truncation step. Thus the guarantees of our algorithms all hold if. instead of having sample access to an exponential family, we are only given access to samples which have already undergone truncation to an arbitrary but known survival set.
Pseudocode. Our main DP-SGD subroutine can be found in Algorithm B. which we defer to Appendix B.4 due to space constraints. We present simplified version below for convenience:

---

1) Truncate samples based on survival set.
2) Preprocess inputs and initialize parameters via warm-stardprreoondttonnnng
3) Minimize truncated empirical NLL using DP-SGD (Theorem 3.4)
4) Return (approximate) minimizer as parameter estimate.
3.1 Technical Overview
Algorithmically, we first truncate the input dataset carefully chosen survival set, which bounds sensitivity but introduces bias for naive estimators such as the sample mean. Then, we use DP-SGD (Algorithm B.1) to minimize the truncated NILL function. This allows us to correct for the bias introduced by the truncation.
For the sake of modularity, first present algorithm under the simplifying condition where are given a R = 0(1) warm-start and later adapt standard DP estimation tools to obtain R 0 log Yol in Appendices B.6 and B.7.
Condition 3.3. We are given ((0) E and -(0) E [[))] E Rm such that 0 (B(
for some given < R = 0(1..
We emphasize that Condition 3.3 is only stated to simplify exposition. It is completely removed in Appendices B.6 and B.7 by adapting standard DP Gaussian estimation tools to the truncated exponential family setting.
We use the following analysis of DP-SGD due to Bassily, Smith, and Thakurta [5].
Theorem 3.4 (Theorem II.1 and Theorem II.4 in [5]). Let e, (0,1). Suppose F(w)
I =i= S((w) is a sum of X-strongly convex functions over closed convex set K C Ikm.. Sup- pose further that i [n). Then there is an (e, D)DP algorithm that outputs some vo E K satisfying
given stochastic gradient oracles 9i for V satisfying || G for all
min F(w) S0 mG2 log² (*/6))og(1/))
[
WER
x²=x=2
The algorithm runs DP-PSGD for T = (n²²) iterations with step-size Xt at iteration i and calls the gradient oracle T times in total.
We remark that the logarithmic factors in the convergence rate of Theorem 3.4 can be removed under additional assumptions about the condition number of the objective function F [22]. In general, the exponential family distributions we study may be ill-conditioned and we must employ Theorem 3.4
instead.
In the rest of this section, we provide the details for the estimation algorithm of Theorem 3.1 and its proof of correctness. As mentioned, our main workhorse is Theorem 3.4. Sections 3.2 to 3.6 addresses how we satisfy the assumptions of Theorem 3.4 and preprocess the input to attain the desired sample complexity. This is summarized in further detail below.
Section 3.2 constructs the survival set SsGD of samples and feasible projection set K of the parameters (Lemma 3.5), Our goal is to ensure that K contains the true parameter and that the truncated NLL function remains strongly convex over K.
For technical reasons, we cannot achieve optimal rates when optimizing the population NLL and must instead optimize the empirical NLL. Section 3.3 details this reasoning and proves a uniform convergence property which ensures that the minimizer of the empirical NLL remains good estimate of the true parameter (Lemma 3.6).
Section 3.4 addresses how to obtain unbiased estimates of the gradient of the empirical NLL well as analyzes the norm of the estimates (Lemma 3.7). The latter is necessary quantity that appears in the DP-SGD analysis (Theorem 3.4).
Section 3.5 applies Theorem 3.4 derive the guarantees of our DP-SGD subroutine (Algo- rithm B) and shows how to recover 0* (Lemma 3.8).
'The original theorem statement is for deterministic gradient oracle under Lipschitz condition. It is not hard see that the same statement holds for an unbiased stochastic gradient oracle with bounded norm.
7

---

Finally, Section 3.6 brings together all the ingredients along with suitable adaptations of standard DP preprocessing tools prove our main Theorem 3.1.
3.2 Strong Convexity (Survival & Projection Sets)
As mentioned in Section 3.1, one sufficient condition for recovering parameters with SGD via Theorem 3.4 is strong convexity. In this section, we specify the truncation operation we impose and show that the truncated NLL is strongly convex over carefully chosen projection as long as the survival set has mass p 2 (2(1).
Let 010), 7( be as in the simplifying Condition 3.3 and define
K = (2 ne,
SSGD = x E R. (T(x)
{
S
m
+ 2R
1-p
Lemma 3.5. Suppose the statistical assumptions (Assumption 2.2 and the simplifying Condition 3.3 hold. Let L denote the empirical NLL over truncated samples with survival set SSGD- Then for any 0 E K, v²i(0) de - O(1²) (I(A)I.
The proof of Lemma 3.5 is deferred to Appendix B.1. Crucially, we rely on anti-concentration inequality due to Carbery and Wright [12] restated by Lee, Wibisono, and Zampetakis [34] (Proposi- tion B.3).
3.3 Uniform Convergence of Empirical Likelihood
Having confirmed the strong convexity property necessary to apply Theorem 3.4, we move on to the algorithmic details. Specifically, Theorem 3.4 requires making multiple passes of the data. However, this is problematic as each data point only provides single unbiased estimate of the gradient of the population NLL. We avoid this complication by instead optimizing the empirical NL.L, for which each data point provides an unlimited number of unbiased gradient estimates. This requires uniform convergence type result to ensure that the empirical minimizer is close to the population minimizer.
Lemma 3.6. Suppose the statistical assumptions (Assumption 2.2) and simplifying Condition 3.3 hold. Let be the minimizer of the n-sample empirical NLL for qø- over K. Then we have ||0 2 S with probability 3 given that 2 -2 (m+ (2++R) R*) (o)(/))(/))
X217t
Lemma 3.6 strengthens prior uniform convergence results [43]. which require 121/a*) samples, and may be of independent interest. Its proof is deferred Appendix B.2.
3.4 Computing Stochastic Gradients
The previous subsection ensures that Theorem 3.4. We now address how to compute gradients within each iteration. Similar to previous works on truncated statistics [17], We are able obtain unbiased stochastic gradients via a simple rejection sampling procedure.
DP-SGD for the required number of iterations per
Lemma 3.7. Assume the statistical assumptions (Assumption 2.2) and simplifying Condition 3.3 hold. Fix a sample x ~u Sya and assume we have access to a sampling oracle for ~ qe (Assumption (C2)). The following holds:
(i) There is unbiased stochastic gradient estimate g(0) for v((0;x).
(ii) With probability 3, the estimator calls the sampling oracle (log(1/s)// times.
(iii) The gradient estimate satisfies (1) G O(-m+ R) with probability 1.
The proof of Lemma 3.7 is deferred to Appendix B.3.
'We only use Assumptions (S1), (S3) and (S4) but state all the statistical assumptions for simplicity of presentation.

---

3.5 DP Empirical Risk Minimization
Now that we are equipped with strong convexity (Lemma 3.5) and bounded gradients (Lemma 3.7) for the necessary number of iterations (Lemma 3.6), we can apply the DP-SGD analysis (Theorem 3.4) show the following result, whose formal proof is deferred to Appendix B.4.
Lemma 3.8. E, 6, ae, (0, 1). Suppose the statistical assumptions hold (Assumption 2.2), the computational subroutines exist (Assumption 2.3), the simplifying Condition 3.3 hold, and that we have sample access to qa- Let 0r denote the minimizer of the n-sample empirical NLL qg Stm Algorithm B.I is an (E, 6)P algorithm that oulputs eslimate 0 E θ such that B[I]0 01 S a². Moreover, Algorithm B.1 has sample complexity n. Ō O(R2) (m R. (m) log(1/6) and poly (m, n, d) running time.
Aae
Remark 3.9 Hligh-Probability Guarantees; See Corollary B.4). By using a clustering trick by Daskalakis al. [17] and taking sufficient samples for uniform convergence to hold (Lemma 3.6), obtain a high- probbbbiiyii guarantee for estimating the true underlying parameter 6*.
We defer the exact statement of Corollary B.4 and its proof Appendix B.5.
3.6 Proof of Theorem 3.1
In Sections 3.2 3.5, we require a constant distance warm start to 8* (Condition 3.3) in order to obtain optimal sample complexity using DP-SGD on the truncated empirical NLL function. This can be removed by adapting standard DP Gaussian warm-start algorithms to truncated exponential families, which we present in Appendices B.6 and B.7 (Lemmas B.5 and B.8). While running the adaptations on truncated data yields biased estimates, such estimates still suffice as warm start.
Our end-to-end algorithm first obtains a O log(//)) -diittacc warm-start via Lemmas B.5 and B.8. Then, use DP-SGD to address the bias introduced by the truncation involved in the rough estimations (Corollary B.4). This yields a proof of Theorem 3.1 with the desired sample and time log(1/))
complexity Ō
m (-/88)))8)
+
+
/01/A m log(2/86)
X
Xaae
4 Private Gaussian Estimation
In order to contextualize our results, we instantiate our general algorithm from Theorem 3.1 for the well-studied case of Gaussian estimation and demonstrate that we can recover the known optimal sample complexities up to logarithmic factors. We emphasize that the first polynomial-time algorithms with optimal sample complexity were achieved by Hopkins, Kamath, and Majid [26] and Hopkins al. [27], and this section demonstrates that we can recover the optimal sample complexities with our more general algorithmic framework.
4.1 Private Gaussian Mean Estimation
We first study Gaussian mean estimation. That there an underlying d-dimensional data- getilaaggneaanggggg distribution ,I) to which we have sample access. We would like to privately estimate μ²"
In Appendix C.1, verify that the statistical and computational assumptions (Assumptions 2.2 and 2.3) hold for Gaussian mean estimation, leading to the following corollary of Theorem 3.1.
Theorem 4.1. Let 8, a, 3 E (0,1). There an (s, 6)DD algorithm such that given samples from
Gaussian distribution N(p,, T), outputs an estimate j satisfying [| - 1='ll E a with probability
1 -B. B. Moreover, the algorithm has sample complexity Ö [/ma) and running time poly(n, d).
dlogg(1)))
d/og()/a6)
4.2 Private Gaussian Covariance Estimation
We next specialize algorithm to the case of Gaussian covariance estimation. That is, there is an underlying d-dimensional data- aataa-gnerating distribution (0, Σn) to which we have sample access. We would like to estimate E E s under differential privacy constraints, where So denotes the space of d x d dositive-definite matrices.

---

Theorem 4.2. Let E, a, E (0, and suppose that = 3 AI. There is an (E. DP algorithm such that given samples from a Gaussian distribution NO,, outputs an estimate || S a with probability - B. Moreover, the algorithm has sample complexity n Ō dh log(A/saz) de log(t/as) de (og(t/)) d log(Hos) and running time poly(n, d).
E satisfying || - (Σ')-&E(E")
as
We present the proof of Theorem 4.2 in Appendix C.2. In addition verifying the statistical and computational assumptions, polynomial dependence on the condition number A/x, We present a preconditioner adapted from the work of Biswas et al. [7] in Appendix C.4. The adapted algorithm essentially estimates the covariance of the truncated Gaussian distribution, which will be a biased estimate of original covariance but suffices to precondition the samples.
also need a private preconditioning algorithm in order to avoid
5 Impact& & Future Work
We introduce a novel paradigm of private algorithm design through truncation and demonstrate its versatility by designing the first efficient algorithm for estimating unbounded high-dimensional exponential families. We further demonstrate its sample efficiency by recovering the optimal sample complexities for standard private statistical tasks such as Gaussian mean and covariance estimation. Our methods may enable more practical and scalable deployment of tools in settings where extreme data values are common but privacy critical.
data analysis
would be interesting to see further applications of truncated statistic techniques in private algorithm design, such regression [15, 16, 18] and linear dynamics [41].
Acknowledgements
We thank Alkis Kalavasis for the insightful discussions. Felix Zhou acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC).
References
[1] Martin Abadi et al. "Deep Learning with Differential Privacy" In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2016, pp. 308- 318. DOI: 10. 1145/2976749. 2978318 (cit. on p. 1).
[2] John M. Abowd. "The US Census Bureau Adopts Differential Privacy".. In: Proceedings of
the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2018, p. 2867. DOI: 10. 1145/3219819 3226070 (cit. on p. 1).
[3] Ishaq Aden-All Ali, Hassan Ashtiani, and Gautam Kamath. "On the Sample Complexity of Pri- vately Learning Unbounded Tigh-DDimesioonl Gaussians". In: Algorithmic Learning Theory, 16-19 March 2021, I, Virtual Conference, Worldwide. Ed. by Vitaly Feldman, Katrina Ligett, and
Sivan Sabato. Vol. 132. Proceedings of Machine Learning Research. PMLR, 2021, pp. 185-
216. URL: http: / httt:://procceetii http///poeeeenn.eeeee/e/e mlr pwwps/reesee vvtess/vvv/// ali2ia. html (cit. on p. 3).
[4] Hassan Ashtiani and Christopher Liaw. "Private and polynomial time algorithms for learning Gaussians and beyond". In: Conference on Learning Theory, 2-5 July 2022, London, UK. Ed. by Po-Ling Loh and Maxim Raginsky. Vol. 178. Proceedings of Machine Learning Research. PMLR, 2022, pp. 1075-1076. URL.: https: httpps::/proceeeingggg. mlr press/v178/ ashtiani 12a. html (cit. p. 34).
[5] Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. "Private Empirical Risk Minimiza- tion: Efficient Algorithms and Tight Error Bounds". In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014. IEEE Computer Society, 2014, pp. 464-473. DOI: 10. 1109/FOCS. 2014. 56. URL: https: / //doi. oroooo///// 10. 1119 2014. 56 (cit. on pp. 3, 7, 27).
10

---

[6] Garrett Bernstein and Daniel Sheldon. "Differentially Private Bayesian Inference for Exponen- tial Families". In: Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Mon- tréal, Canada. Ed. by Samy Bengio et 2018, pp. 2924 /tt::httss///proceedaaa neurips. cc paper 2018 hassh/aahhaaaaae 40044000700900
Abstract
html (cit. on p. 3).
[7] Sourav Biswas et al. "CoinPress: Practical Private Mean and Covariance Estimation". In: Advances in Neural Information Processing Systems 33: Annual Conference Neural In- formation Processing Systems 2020, NewrlPS 2020, December 6-12, 2020, virtual. Ed. by Hugo Larochelle al. 2020. URL: https: / proceedings neurips cc /tpppaap//////// /2000/ hash/ hash/a/8eeheeeeeeeeeeeaaa 4004440cee7761522777788688888880 -aw.raeeeebbbe4---baraatttt -ttll (cit. on pp. 3, 10, 27, 28, 32-34).
[8] James Boyle and Richard Dykstra. "A method for finding projections onto the intersection of convex sets in Hilbert spaces". In: Advances in Order Restricted Statistical Inference: Proceedings of the Symposium on Order Restricted Statistical Inference held in lowa City, Iowa, September 11-13, 1985. Springer. 1986, pp. 28-47 (cit. on p. 5).
[9] Lawrence D. Brown. Fundamentals of Statistical Exponential Families: With Applications in Statitical Decision Theory. Institute of Mathematical Statistics, 1986 (cit. on 4).
[10] Mark Bun, Kobbi Nissim, and Uri Stemmer. "Simultaneous Private Learning of Multiple Concepts". In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016. Ed. by Madhu Sudan. ACM, 2016, pp. 369-380, DOE: 10. 1145/2840728 2840747. URL: https: pottps::/dosss /ttii//o...///. org./0..11111. 1145/ 2840728. 2840747 (cit. on pp. 29, 30).
[11] Róbert Busa-Fekete et al. "Optimal Learning of Mallows Block Model". In: Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA. Ed. by Alina Beygelzimer and Daniel Hsu. Vol. 99. Proceedings of Machine Learning Research. PMLR, 2019, pp. 529- mlr http:/edddnn........esss///////e htass/v99/busee fekete html (cit. on pp. 5,
532. URL:
6).
[12] Anthony Carbery and James Wright. "Distributional and 1,9 norm inequalities for polynomials over convex bodies in Te In: Mathematical research letters 8.3 (2001), pp. 233-248 (cit. on pp. 5, 8).
[13] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. "Differentially Private Empirical Risk Minimization". In: Journal of Machine Learning Research 12 (2011), pp. 1069- 1109 (cit. on p. 1).
[14] Sinho Chewi. Llg-CConcvee Sampling. unpublished draft, 2024. URL: https::/chhwiiiiin gi github. io/main.......... påf (cit. on p. 6).
[15] Constantinos Daskalakis, Dhruv Rohatgi, and Emmanouil Zampetakis. "Truncated Linear Regression in High Dimensions". In: Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual. Ed. by Hugo Larochelle et al. 2020. uRl: https: / proceedings. neurips- cc paper / 2020 hhat://31166000rrsa000000eooobea html (cit. on pp. 10).
Abstract
[16] Constantinos Daskalakis et al. "Computationally and Statistically Efficient Truncated Re- gression". In: Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA. Ed. by Alina Beygelzimer and Daniel Hsu. Vol. 99. Proceedings of Machine Learning Research. PMLR, 2019. pp. 955 5600 URL: http: : proceedings mlr. press /v9
daskalakis html (cit. on pp. 3, 10).
[17] Constantinos Daskalakis et al. "Efficient Statistics, in High Dimensions, from Truncated Samples" In: 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, Ed. by Mikkel Thorup. IEEE Computer Society,2015 pp. 639 649. DOI: 10. 1109 11199/FOCC FOCS. 2018. ..0067. URL: https: org 10. 1109/FOCS. 2018. 00060006670000 (cit. on pp. 2-5, 8, 9, 27, 34).
[18] Constantinos Daskalakis et al. "Efficient Truncated Linear Regression with Unknown Noise Variance". In: Advances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual. URL: https: / propeeeeeedns...
Ed. by Mare Aurelio Ranzato et 2021, pp. 1952-1962

---

neurips cc //0/////.../000.0..c0o0000000030 - Abstract
html (cit. on pp. 3, 10).
[19] Cynthia Dwork and Aaron Roth. "The Algorithmic Foundations of Diffeerential Privacy". In:
Found. Trends Theor. Comput. Sci. 9.3-4 (2014), pp. 21 217-407. DOI: . 1561//4000000044
URL: https: / /oi. org/ 10/ 151/0400000440 (cit. on 22).
[20] Cynthia Dwork et al. "Calibrating Noise to Sensitivity in Private Data Analysis". In: Theory of Cryptography. Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings. Ed. by Shai Halevi and Tal Rabin. Vol. 3876. Lecture Notes in Computer Science. Springer. 2006, pp. 265-284. DOI: 10. 1007 / 11681878 __1 URl.: https://doi. wtt. 10. 0t11/116811778/8 14 (cit. on pp. 1, 22, 30).
[21] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. "RAPPOR: Randomized Aggre- gatable Privacy-Preserve Ordinal Response". : In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, ACM, 2014, pp. 1054-1067. DOI:
10. 1145/2660267 2660348 (cit. on p. 1).
[22] Vitaly Feldman, Tomer Koren, and Kunal Talwar. "Private stochastic convex optimization: optimal rates in linear time". In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. Ed. by Konstantin Makarychev et al. ACM, 2020, pp. 439-449. DOI: 10 1145 / 3357713 3384335. URL: https://doi. org/ 0144/3357713 3384335 (cit. on p. 7).
[23] Cecilia Ferrando, Shufan Wang, and Daniel Sheldon. (GGeneral-purpss differentially-priiaa confidence intervals". In: arXiv preprint 2rXiv:2006.07744 (2020) (cit. on p. 3).
[24] Marco Gaboardi al. "Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing". In: Proceedings of the 33rd International Conference on Machine Learning (ICML). PMLR, 2016, pp. 2111-11121 2111-2120 (cit. on p. 1).
[25] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combi- natorial Optimization. Vol. 2. Algorithms and Combinatorics. Springer, 1988. ISBN: 978-9-647 97883-8. DOr: 1007 1000/978-3 9978------ 10--3-6222 642 97881-4
URL: https: org/10. 1007/970
3 3-642- 978-2-97881-4 (cit. on p. 5).
[26] Samuel B. Hopkins, Gautam Kamath, and Mahbod Majid. "Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism". In: STOC '22: 54th Annual ACM SIGACT' Symposium
Theory of Computing, Rome, Italy, June 20 24, 2022. Ed. by Stefano Leonardi and Anupam Gupta. ACM, 2022, pp. 1406-146 1417. DOI: 10. 1145/ 3519947 (cit. on pp.
3519935 351 9947. 9).
URL: https: //doia //oii org/ 10.
[27] Samuel B. Hopkins et al. "Robustness Implies Privacy in Statistical Estimation". In: Proceed- ings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023. Ed. by Barna Saha and Rocco A. Servedio. ACM, 2023, pp. 497-
506. DOI: 10. / 05545456444.... 3585115. URL: https: : //doiii...//. org/ 10. 1145/356428 3585115 (cit. on pp. 3).
(28) Svante Janson. "Tail bounds for sums of geometric and exponential variables". In: Statistics & Probability Letters 135 (2018), pp. 1-6 (cit. on p. 24).
[29] Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. "New Lower Bounds for Private Estimation and Generalized Fingerprinting Lemma". In: Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022. Ed. by Sanmi Koyejo et al. 2022. URL: http: / papers nips cc paper files/ paper / /002/ Abstract Conference html (cit. on
hash 0a862288118664491199995656688889 p. 3).
[30]
Vishesh Karwa and Salil P. Vadhan. "Finite Sample Differentially Private Confidence Intervals". In: 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA. Fd. by Anna R. Karlin. Vol. 94. LIPles. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2018, 44:1-44:9, Dor: 10. 4230/LIPICS, URL: https: ///::://doo. iidiii.o///iieeee
.rcs.2018. 2018.44.. 44. org/ 10. 4230/LIPICS. ITCS. 2018. 44 (cit. on pp. 3, 29, 30).
[31] Jonas Moritz Kohler and Aurélien Lucchi. "Sub-sampled Cubic Regularization for Non-convex Optimization". In: Proceedings of the 34th International Conference Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017 Ed. by Doina Precup and Yee Whye
12

---

Teh. Vol. 70. Proceedings of Machine Learning Research. PMLR, 2017, pp. 1895-19999 URL: http://proceediin mll: mlr. ppwss//70/kohl erw.. (cit. on p. 23).
[32] Vasilis Kontonis, Christos Tzamos, and Manolis Zampetakis. "Efficient Truncated Statistics with Unknown Truncation". In: 60th IEEE Annual Symposium Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019. Ed. by David Zuck-
erman. IEEE Computer Society, 2019, pp. 1578- 1578-1595. DOI: 10. 1109/FDCS 2019900093. URL: ttttps://don http://oooooo/////////// 10. 1011//0C9C.... 2019. .00093 (cit. on p. 3).
[33]
Beatrice Laurent and Pascal Massart. "Adaptive estimation of a quadratic functional by model selection". In: Annals of statistics (2000), pp. 1302-1338 (cit. on p. 22).
[34] Jane Lee, Andre Wibisono, and Emmanouil Zampetakis. "Learning Exponential Families from Truncated Samples". In: Advances in Neural Information Processing Systems 36: Anmual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023. Ed. by Alice Oh al. 2023. URL: http: / httpp/aappeeeee/ea//eeeeeeeeeeea caipp..s.ppp...................s cc / /apppe 7, files / paper / 2023 / hash html (cit. on pp- 3, 5, 6, 8, 23, 25, 28).
Obstract-Confferree
[35] Jane H. Lee, Anay Mehrotra, and Manolis Zampetakis. "Efficient Statisties With Unknown Truncation, Polynomial Time Algorithms. Beyond Gaussians". In: 65th IEEE Annual Sympo- sium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024. JEEE, 2024, pp. 988-1006. DOI: 10. 1109/119FFFF /FCS61226666 2024. 00066. URL: https: //doi.org// 10. 1109 L099FFCS612666 2024. 00066 (cit. on pp. 3, 5, 6, 33).
[36] László Lovász and Santosh S. Vempala. "The geometry of logconcave functions and sampling algorithmss. In: Random Struct. Algorithms 30.3 (2007), pp. 307-358, DOI: 10. 1002/RSA.
20135. URL. https:://///.. /ttp:://ddooooooooo org/ 10. 1002/rsa....... 20135 (cit. on p. 6).
[37] Audra McMillan, Adam Smith, and Jon Ullman. "Instance-optimal differentially private estimation". In: arXiv preprint arXiv:2210. 15819 (2022) (cit. on p. 3).
[38] Frank McSherry. "Privacy integrated queries: an extensible platform for privacy-preserving data analysis". In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2009, Providence, Rhode Island, USA, June 29- July 2. 2009, Ed. by Ugur Çetintemel et al. ACM, 2009, pp. 19-30. DOI: 10. 0A44//559445. 1559850. URL: https: / //doi.org/ 10. 1ee.111111111111 1559845.9.. 1559850 (cit. on p. 22).
[39] Shyam Narayanan. "Better and simpler lower bounds for differentially private statistical estimation". In: IEEE Transactions on Information Theory (2024) (cit. on p. 3).
[40] Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. "Locating a Small Cluster Privately". In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIEE Systems, PODS 2016, San Francisco, CA, USA, June 26 July 01, 2016. Ed. by Tova Milo and Wang-Chiew Tan. ACM, 2016, pp. 413-427 DO1: 10. 1145/2902221111111 7790225122902996..... https: org/ 10. 1e111/1122222// 29022512222111 2902296 (cit. on p. 30).
Symposium on Principles of Dutabase
2902296. URL:
[41] Orestis Plevrakis. "Learning from Censored and Dependent Data: The case of Linear Dynam- ies". In: Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA. Fd. by Mikhail Belkin and Samory Kpotufe. Vol. 134. Proceedings of Machine Learning Research. PMLR, 2021, pp. 3771-3787. URL: http: / http://prrceeen...////////o mlr press/v13// plevrakis21a, html (cit. on pp. 3, 10).
hmml
[42] Victor S. Portella and Nick Harvey. "Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes". In: CoRR abs/2404.17714 (2024). DOT: 10. 48550/ ARXIV. 2404. 17714. arXiv: 2404. 17714. URL: https: /doi.
org/10. 10/10...2 480004855//000 arxiv. 2404. 17714 (cit. on p. 3).
[43] Abhin Shah, Devavrat Shah, and Gregory W. Wornell. "A Computationally Efficient Method for Learning Exponential Family Distributions". In: Advances in Neural Information Pro- cessing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual. Ed. by Marc' Aurelio Ranzato et al. 2021, pp. 15841-15854. URL: https : / pro.eedecedeggs.. neurips. , cc / /paper/ / 2021/ / hash/ / Abstract. html (cit. on pp. 2, [44] Or Sheffet. "Differentially Private Ordinary Least Squares". In: Proceedings of the 34th International Conference on Machine Learning (ICML). PMLR, 2017, pp. 3105-3114 (cit. on
p. 1).
13

---

[45] Adam Smith.
Statistical Estimation with Optimal Convergence Rates". In: Proceedings of the 43rd Anmual ACM Symposium on Theory of Computing (STOC). ACM,
2011, pp. 813-822. DOT: 10. 1 1145/1993636. 1993743 (cit. p. 1).
[46] Terence Tao. Topics in random matrix theory. Vol. 132. American Mathematical Soc., 2012
(cit. on p. 23).
[47] Salil P. Vadhan. "The Complexity of Differential Privacy". In: Tutorials on the Foundations of Cryptography. Ed. by Yehuda Lindell. Springer International Publishing, 2017, pp. 347-450. DOI: 10. 1007 9978 3- 00119-70088-8888 _ URL: https: : //wii/ii.../ org/ 10. 1007 9978-3 3- $19-57048-8%55_1 (cit. on pp. 29, 30).
[48] Martin J Wainwright. High-dimensionas statistics: A non-asymptotic viewpoint. Vol. 48. Cam
bridge university press. 2019 (cit. p. 22).
[49] Martin Wainwright and Michael I. Jordan. Graphical Models, Exponential Families, and Variational Inference. Vol. Foundations and Trends in Machine Learning 1-2. Now Publish- ers Inc., 2008, pp. 1-305 (cit. on p. 4).
[50] Xiaozhou Wang and Ting Kei Pong- "Convergence Rate Analysis of a Dykstra- Sype Projection Algorithm". In: SIAM J. Optim. 34.1 (2024), pp. 563-589. DOr: 10. 10111 10.117723M114578.1 URL: https://doi.co org/oog.//// 1137/23m1545781 (cit. on p. 5).
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Our contribution is purely theoretical and the theoretical model and assump- tions are clearly stated.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiittinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification:
All assumptions and proofs provided.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: Our contributions are purely theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
Our contributions are purely theoretical.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: cissss.ccppublc//gue guidee/ /CodeSubmia sgionoiccyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
Our contributions are purely theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our contributions are purely theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our contributions are purely theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https http::://///uuiit http///enerii..eeeeeeeee cttp:////c/ccceccccccccceeelelld
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The impacts are stated in the "Impact Statement" section.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
Our contributions are purely theoretical.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Our contributions are purely theoretical and we cite all prior works upon which contributions rely.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
Our contributions are purely theoretical.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our contributions are purely theoretical and no crowdsourcing/human experi- mentation was conducted.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our contributions are purely theoretical.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
20

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //tprr//nnu.../eeeeee teeeurip..cc/oofeeeeeee /LLM) for what should or should be described.
21

---

A Deferred Preliminaries
A.1 Differential Privacy
We first recall the following preliminaries from differential privacy.
Definition A.1 (Differential Privacy; Dwork al. [20]). Given 0 and E (0, 1), randomized algorithm A Xm + (e, 6)-DP if, for every pair of neighboring datasets D, D' E x that differ by single entry (i.e. neighboring datasets) and for all subsets U of the output space.
Pr[A(D) E UJ S éf Prr(A(D") E U] +6
fundamental tool in designing DP algorithms is the Gaussian mechanism. We write D D' to denote two neighboring datasets.
Proposition A.2 (Gaussian Mechanism; Dwork and Roth [19)). Let f X Rd be arbitrary function d-dimensional with lz-sensitivity A2(f) = maxp -io-Dyllfff [D) - f(D')l. For any e, 6 E
(0, 1), the mechanism that outputs f(D) + where & ~~ o (E for
242 In(.122/)/))
An important property of differential privacy is that performing computation on a privatized output cannot lose additional privacy:
Theorem A.3 (Post-Processing: Dwork and Roth (19]). Let M be an ()D) mechanism and be any arbitrary random mapping. Then g(M()) is (e, didifferrenl private.
Moreover, multiple computations on a dataset incur privacy cost in a natural manner.
Theorem A.4 (Simple Composition; Dwork and Roth [19]). Let Mi and M2 be (E1, and (#2, 82) DDP mechanisms, respectively. Then the (adaptive) composition M2(-.M(--) is (51 + E2, 81 + -D)
On the other hand, executing private mechanism on disjoint partitions of the same dataset does not incur any additional privacy cost.
Theorem A.5 (Parallel composition of differential privacy; McSherry [38]). Let M be an (s, 6)-DP mechanism and Di...., Dy be k disjoint subsets of the dataset D. Then the mechanism that outputs ((.D),))...,((M)) is (c, 6)-DP.
A.2
Concentration Inequalities
Theorem A.6 (Lemma in Laurent and Massart [33]). Let Z ~ N(O, Then with probability
1 8,
| < + v 2d (1/8) + (og(1/s)
Recall a centered random variable is said to be (v², ( su/expsubxpoontii if
x²
E AX < exp
2
for all [X| E (0, If is (v? 1/::) subexponnntt for i E [n], then it is well-known [48, Section 2.1.3] that its sum E, X; is (v" 1/1) subexponential for
Σ 2
==
max
7
Subexponential variables enjoy the following concentration properties. Proposition A.7 (Proposition 2.9 in [48]). For
( subexxxonoon variable X,
2
203
tE (0, v2))
Pr X 2 $
<
e
2,
t t2 v2n
and
tE (0, 12)))))
Pr|X < -
t2 121.
22

---

A specific example is the subexponeniiality of the sufficient statistics of exponential families. Proposition A.8 (Claim in [34]). Suppose Assumptions (S1) and (S2) hold. Then for any unit vector E T and qo*, (By-gg- [T()]] T(x)) is (1, (1,,)))-subees syn-spbbexpoo (cf. Appendix A.2).
useful concentration result for bounded vectors is the following.
Theorem A.9 (Vector Bernstein Inequality; Lemma 18 in [31]. Let X .....,,(m)) X(m) be independent random vectors with common dimension d satisfying the following for all i [m]:
(i) E[ 1 0
(ii) [X $ R
(iii) [|] G²
Let x = E Then for any (0, G//n).
a=n 1 SG2 4
P||l| a] S exp
For covariance estimation, we also require the following spectral concentration bound for symmetric Gaussian matrices.
Theorem A.10 (Corollary 2.3.6 in Tao [46]). Let Y be random d x d symmetric matrix Y with Y
o0) For sufficiently large, there are absolute constants C, c > O such that for all C,
Pr[lyil2 > tovd I &Cexp(-ctd))
A.3
Omitted Proofs from Section 2.2
We now restate and prove the guarantees of our preprocessing algorithm.
Lemma 2.1. Fix n 2 1 and let N E N. Let D E IR be an N-sample dataset, D' E IR N be obtained from D by modifying single entry, and S Rd. Write Ds, D's to denote the datasets obtained from D, D' by discarding entries that fall outside of S. There is preprocessing algorithm A such that
(i) A(D's) E S"h can be obtained from A(Ds) E S" by modifying a single element,
(ii) for any (s, 8)- algorithm B with respect to neighboring truncated datasets, the compo- sition ((A(Ds)) (e, 8) with respect to neighboring (untruncated) datasets D, D', and
(iii) if D is sampled i.i.d. from some distribution such that p(S) = then A(D) contains i...d. samples from the truncated distribution p with probability 3, provided N D( p log(L/o)
Pseudocode.
See Line to Line 4 of Algorithm B.I.
Proof. We wish to produce two neighboring datasets of size by discarding points that lie outside of the survival set.
Proof of (i): We first analyze the relationship between neighboring datasets after the initial truncation.
Suppose D' is obtained from D by modifying D to E D', then Ds. D's fall into one of three cases:
1) If & S, then Dş = D's
II) If x. S, then D's can be obtained from Ds by modifying v to y, i.c. they are again neighboring datasets.
m I w 1, then D's can be obtained from Ds by adding deleting an element.
23

---

We focus on the more challenging Case IIII, Without loss of generality, suppose that z & S and y so that D's is obtained from Ds by adding y. If Dsl D I n, A picks any data- independent duumaay E S and add copies of 7dummy to the truncated dataset until there are elements. Then A(D), A(D)) are neighboring n-sample datasets with elements from S. Otherwise, if n S [2| < D'sl. A keeps the first n datapoints of the truncated dataset so that there are again elements. Then A(D)) are once again neighboring nt-aamle datasets with elements from S, regardless of which entry of the dataset differs between D, D'. Note that in either scenarios, we need to enforce the dataset size by adding or deleting elements, but never both.
Cases D), II) are more clear as they are already neighboring datasets and the additional processing does not change this fact.
Proof of (ii): Next, we analyze the privacy guarantees of the composition (()(Ds)) This essentially follows from (i), as A(Ds),.(DD) can be obtained from each other as sets by modifying one element. The only subtle difference is that in case III) above, prior to the shuffling step, the order of entries is possibly not "aligned", iee there could be more than one index E [n] where A(Ds); A A(D's): a. The extra shuffling step in Line 4 of Algorithm B.1 ensures that under suitable coupling of A(Ds), A(D's) they are always neighboring datasets, i.e. there is only a single index i* such that A(Ds):
A(D's) We can take this coupling to be the one where every element in A(Ds) n ADDs) is always shuffled to the same index. Then the privacy of (((( follows by the privacy guarantees of B.
Proof of (ii)): We finish by analyzing the utility guarantees. By a concentration incquality for sums of geometric random variables [28, Corollary 2.4), for N = S2 n log(1/)), ) it holds with probability 1 1- 3 that there are at least n samples that remain after the preprocessing step. Conditioned on this, the preprocessing simply deletes some possibly additional samples from y but does not add dummy points and the output as desired.
B Omitted Proofs from Section 3
B.1 Proof of Lemma 3.5
We now restate and prove Lemma 3.5.
Lemma 3.5. Suppose the statistical assumptions (Assumption 2.2 and the simplifying Condition 3.3 hold. Let L denote the empirical NLL over truncated samples with survival set SSGD- Thenfor any 0 E K, v2i ž - = I
The proof relies on the following facts from the truncated statistics literature.
Proposition B.1. Suppose that Assumption (SI) and Condition 3.3 hold. Then for any K, (SSSo) 2 = Q(()
Proof of Proposition B.I. From elementary probability,
Exngo [1] - IE Egy [T())]]]]] tr (Cov znggo [T<), S m.
Then do puts mass on the set
So I [T(x) Ey [T [T)]]]
Let f denote the population NLL function with respect to ((0) so that f(((()) = 0. By Assump- tion (S1), 2 3 I over K. Thus for any 0 E B (0))))) n O,
BByaga [T())] Raz [[x)]] = V (0)]
V (0) V {((()))]
< ||0 |
(By 1-smoothness of f)
< R.
This ensures that S4 C SSGD so that qe ge(Ssan (SsGD) 2 2(1).
'We only use Assumptions (S1), (S3) and (S4) but state all the statistical assumptions for simplicity of presentation.
24

---

Proposition B.2 (Lemma 3.4 in [34]). Suppose Assumption (S1) holds. Then for any 0, H' E θ and
S C Rdd qo (S) 2 go (5) exp 1100 8'11))
Proposition B.3 (Lemma 3.2 in [34]) Fix 0 G. Suppose Assumptions (S1), (S3) and (S4) holds
2k
and S S IRd satisfies qo(S) > 0. Then Cov y~o Cov some absolute constant.
(T()). T(u)) =
2=(S)
XI, where C > 0
4Ck
We are now ready prove Lemma 3.5.
Proof of Lemma 3.5. By Condition 3.3, K certainly contains 0*. In particular, Proposition B. ensures that we have qe- (SSGD) 2 p= Q(1). An application Proposition B.2 allows us to deduce
that qo puts (2 (SSGD) )) = 2(px) mass on SsGD for every K. But then by Proposition B.3,
pa PR--GR2
2k
Cov
BAGD [Ty). [(y) =
AI, concluding the proof.
4CW
B.2 Proof of Lemma 3.6
We now prove Lemma 3.6, whose statement is copied below for convenience.
Lemma 3.6. Suppose the statistical assumptions (Assumption 2.2) and simplifying Condition 3.3 hold. Let 9r be the minimizer of the n-sample empirical NLL for S000 over K. Then have -10 0*112 S with probability B given that 2 Q (m+ R²) log(V/)
X
The sufficient statistics of SeOD has radius r = O( R) by construction. We can thus apply a vector Bernstein inequality (Theorem A.9) see that for any a E (0,
Proof.
1 Σ (()
a 8r
1
Pr
E gy
T())
S exp
Let 0 be the constant guaranteed by Lemma 3.5 such that Ż. is ci-strongly convex over K. We have V [( -an"/4r with probability 1 8/2 given that
(m + R2a) lox(1/a)
n 2 Ω
X21d
But then by strong convexity,
c\ 10 0-112 < - -0+) 2
cAn²
2r.
4r
Thus |1Ø- 1- S 17. By application of the triangle inequality, this ensures that ||Ø - -0(0) < R 1 S 2R so that 0* E K.
Conditioned on 0+ E K and using the fact that L is strongly convex over K, we see that Ż in fact satisfies a cA-PL inequality:
Vi I(0") - L(O-) 2 110 0.1
2cA
We have |Vi()')]| S cλa with probability 1 - -3/2 provided that
n 120 Ω (m + RP2) (bg(
X²
In particular, 110*~0011 < This concludes the proof.
25

---

B.3 Proof of Lemma 3.7
We now restate and prove Lemma 3.7.
Lemma 3.7. Assume the statistical assumptions (Assumption 2.2) and simplifying Condition 3.3 hold. Fix sample Secp and assume we have access sampling oracle for y qo (Assumption (C2)).
Qg-
The following holds:
(i) There is an an unbiased stochastic gradient estimate g Vl(0;2).
(ii) With probability 1-3, 3, the estimator calls the sampling oracle (log((/))/)) times.
(iii) The gradient estimate satisfies (1g(0) G Olym R) with probability 1.
Given a sampling oracle to qe, we can perform rejection sampling to obtain y 9g Sano Then we have stochastic access to VeL given by g = T Tz)) Moreover, (T(x) T(y - [[(x)) 7 700) + [T(x) 7(0| s O( + R) by the choice of SSGD. Hence we have deterministic bound [l I G = O m + Rt on the norm of the stochastic gradient.
Proof. Fix a sample I ~ 4g- SunD
B.4 Proof of Lemma 3.8
we now restate and prove Lemma 3.8.
Lemma 3.8. Let ,, az, (0, 1). Suppose the statistical assumptions hold (Assumption 2.2), the computational subroutines exist (Assumption 2.3), the simplifying Condition 3.3 hold, and that we have sample access to qa- Let 6r denote the minimizer of the n-sample empirical NLL for 9 Swm Algorithm B.I is an (e, 8)D algorithm that outputs estimate Ô E θ such that B[[]0 11 a²
Moreover, Algorithm B.1 has sample complexity n Ō( OUR²) (m+Ry/m log(t/a) rumning time.
and poly n, d)
Aae
See Algorithm B.I for the pseudocode. We note that the main difference from standard applications of DP-SGD is the initial truncation step which discards samples that fall outside of the survival set S. This provides an easy bound on the sensitivity of the gradient, but requires optimizing the truncated NLL opposed to the regular NLL in order address the bias introduced by the initial truncation step.
Pseudocode.
Analysis.
Applying Theorem 3.4 yields proof of Lemma 3.8.
Proof of Lemma 3.8. We know that L. K - IR is Ae - - -strongly convex by Lemma 3.5. Moreover, Lemma 3.7 guarantees that have stochastic gradients with bounded norm G O(ym+ RR. Let 0 be the output of Theorem 3.4. We see that satisfies
(OuLE) (m² mRt log2 (m/6) log(4/))
Ell 111 so
X²n2g2
Thus in order to reduce the expected squared distance to (*/16)2, suffices to take
((A8) + Rym) log(*/8) log()/5)
2 Ω
Xag
This concludes the proof.
B.5 Proof of High-Probability Estimation
Here, we state and prove the high-probabilityy version of Lemma 3.8.
Corollary B.4. Let e, 8, a, 8 E (0.1). Suppose Assumption 2.2, Assumption 2.3, and Condition 3.3 hold and that we have sample access to 48-
Swa. There is an (e, 6)-DP algorithm that outputs
26

---

Algorithm B.1: DP-SGD with Truncation
Input: N-sample dataset D. desired truncated samples n. privacy parameters E, (0, 1), survival set S, truncated sensitivity A > O, warm-start g(0) E IR accuracy (0. 1),
step-size function ((t) 2+ - +.,, projection set K
Output: estimator i for 0
Ds {x E E S}
Ds D5
dummmg 12 [n- [n]n-
Fill with dummy elements if there are less than
elements
3 Ds 6- Ds[1:n]
> Only keep first n elements if there are more than n
Shuffle Ds uniformly at random
x² f 32A log("/s) (og(
D Taken from Bassily, Smith, and Thakurta [5] (Theorem 3.4)
for iteration 1, 1,...,77 n² do
Dg sampled with replacement
y 9)
> Rejection sampling using sampling oracle (Assumption (C2))
(0) - T(x) -T()
P Gradient computation (Lemma 3.7)
10
E~ o2)
11
(10) - 011-1) -(t)[g
+
000) - ((())
12
13 return ((n²)
estimate such that 1/0- (m++ 11") (sg(
s a² with probability 1-3. Moreover, the algorithm has sample and poly (m, d, n) running time.
complexity Ö
_on2)) (m+ m)) log log(1/s)
Ane
Proof. Similar to Daskalakis et al. [17], we perform a boosting trick. Consider the output of a single execution of Algorithm B. 1. By Lemma 3.8 and Markov's 's inequality, ||0 8+ 2 a/a with probability most 1/a. By multiplicative Chernoff bound, repeating
(log(L/s) independent executions of Algorithm B. ensures that at least 2/3 of the outputs ((1), ..... Øle) are a/1-close to 0* Now, any of the 2/3 outputs are within a/2 distance to each other, Hence by outputting any of the points, say 0, that is within a/2 distance with at least v/2 of the other points ensures that is within B.
distance of from 8 with probability
Furthermore, by Lemma 3.6, we have that -|0- - 0* < a given that
n 2 Ω (m + R²2) log(4/a)
Boosting increases the sample complexity by a factor of (llog!/s)). Note that there is no additional privacy loss since (Theorem A.5). Thus we require
think of the algorithm as running e disjoint chunks of the dataset
n δ (m + R2)) log(1/o)
co(R) + Rym) log( /lgl:)//)ooo(C/ log(1/s)
X
Aae
This concludes the proof.
B.6 Recursive Warm-Start
ddistance warm start with logarithmic dependence on the prior radius R. The algorithm is adapted from the work of Biswas al. [7] for Gaussians. Similar the rest of our work, our algorithm only requires truncated sample access to exponential family and thus generalizes the work of Biswas et al. [7] from Gaussians
now present a simple recursive method that obtains a O log((/e)
27

---

to truncated exponential families. In Appendix B.7, we will see how to obtain -oly(m)-distance warm-start without any prior. thus completely removing the dependence R.
Lemma B.S. Suppose that the exponential family has bounded covariances (Assumption (S1)) and that we have access to moment matching oracle (Assumption (C3)). Algorithm B.2 is an (s, DDD algorithm such that given samples from and a prior parameter ((0) such that ||0(0) 0* S R,
outputs some 0 and Ezzpy (T()) such that |10 0* S 0 (oo()/)) with probability 1
Moreover, the algorithm has sample complexity n Ô log R/8) Ing (1/66) voly(m, n. n.
and running time
AE
The proof of the result above is deferred to Appendix B.6. We emphasize Lemma B.5 requires only truncated sample access for an exponential family. While there are private warm-start algorithms for Gaussians, it is not clear if their guarantees hold for truncated exponential families.
Pseudocode. See Algorithm B.2 for pseudocode of the warm-start algorithm. We remark that is a straightforward adaptation of the Gaussian estimation algorithm from Biswas et al. [7] to the case of truncated exponential families. However, the adaptation only provides a constant-distane warm start since the initial truncation step introduces bias.
Algorithm B.2: Recursive Warm-Start
Input: dataset D, number of desired samples n, privacy parameters E, 8 E (0, 1), initial prior
((o) E gR, initial expected sufficient statistic 7()) Ex-agco) [T)),, initial distance
R> 0, survival probability p E (0, 1)
Output: estimator Ô for 0" and o [T())
+ log(R///m))) m/)
2 8' + (og(R//m)H
3 a +- O (R+v/m log(1/8")
ne*
for i O,...., log R2/ vm) do Swarm, + {u E Rd -z) < I-p
+ 2- R3
Produce n truncated samples r11), ...,, x: (n) from Ds D= 2mmm, 2
b (Lemma 2.1)
T C),(T(r()) E~ N(0,002) 7(+1 +
b sensitivity A = 0 R-
b Gaussian mechanism (Proposition A.2)
10 ((++1) + MomentMatch( return ((++1), ((+1))
D (Assumption (C3))
Analysis. Once again, the idea is impose a truncation about the samples that can work with bounded random variable. However, we need to ensure that the survival set is chosen to have constant mass. Similar Section 3.2, we consider the survival set
{ x: E RdR: [ - (0 < 1-p +2 2-22R R).
/m
S Swarm,2-iR
where we iteratively shrink the prior distance with each iteration i.
Once we have an estimate of the bounded mean of some truncated distribution, we use the following fact to translate that back into an estimate of the true underlying expected sufficient statistic.
Proposition B.6 (Corollary 3.8 in [34]). Let E O. Suppose Assumption (SI) holds and that (o()) > Then
E y [(y) - Exwag [[()]] S0 log go(SS) ))
28

---

Proposition B.6 ensures that an good estimate of the truncated expected sufficient statistic is already constant distance warm-start. However, in order avoid -dedeednneee on the prior radius. we iteratively refine our estimate. The following lemma analyzes the guarantees of one iteration of Algorithm B.2.
Lemma B.7. Suppose Assumptions (SI) and (C3) holds. There is an (E algorithm such that Stom. and prior parameter (19) of distance at most R 2 M m), estimates O* up distance a/x o/xfor a (S(llg((o)) ()),)) R) with probability 3. Moreover, the algorithm has sample complexity
given truncated samples from Qo-
R log(1/s) Rym log( log log(1/) (
a
Proof. By vector Bernstein inequality (Theorem A.9), taking
2 Ω R2 log(
a
samples ensure that the sample sufficient statistic is at most o/1-distance from the expectation of the truncated sufficient statistic with probability 8/2. By standard Gaussian concentration inequalities (Theorem A.6), taking
n 2 Rog( 1/5) log(1/)
a0
ensures the gaussian mechanism (Proposition A.2) adds noise of magnitude O S %/1 with probability 5/2. By Proposition B.6, this then at most O(log(//)) = dii)-istaance from the true expected sufficient statistic. Thus our estimate is distance at most from the true expected sufficient statistic given the constant lower bound on a sufficiently large. By the A-strong convexity of the (untruncated) NLL function, the updated prior output by the moment matching oracle is a/x-distance from 0*
We are now ready prove Lemma B.5.
Proof of Lemma B.5. Repeating the one-step algorithm from Lemma B.7 log R// /m) times ensures with iteratively halved accuracy parameters a = X2 yields an estimate of the prior parameter of distance O O(ym). This incurs a sample complexity blowup of Ó(log(R) for a total sample complexity of
δ log(R/a) X2
vm log(1/)) (og())))
We can then apply the one-step algorithm one last time but with - (log(%/o)) This incurs an additional sample complexity of
o m log(t/o) + m log(1/8) log(1/s)
We can re-use samples for each repetition. By simple composition (Theorem A.4), suffices to incur another Olog(R)) blow-up in sample complexity to preserve privacy.
B.7 Coarse Bounding Box
As the final ingredient, we derive private bounding box algorithm for 0* that translates to ((v7/2) (///))-distanne warm start. Combined with Appendix B.6, this completely removes the need for the simplifying Condition 3.3 from Sections 3.2 to 3.5.
The basis is folklore result for Gaussians whose guarantees are stated by Karwa and Vadhan [30] but
follows from prior works [10, 20, 47]. In particular, the idea is to learn an e. ball about Ez [T(x)) by executing private histogram algorithm on each of the coordinates. Translating the Eox ball to a (m/m)-disttam
Fuclidean ball about 0* yields
warm-start. Lemma B.8 formalizes this idea. We in fact present more general bounding box algorithm for truncated exponential families. For now, we can take the survival set to be all of dgd with survival mass 1.
29

---

Lemma B.8. Suppose the exponential family has bounded covariances (Assumption (S1)). interiority
(Assumption (S2)), and we have access moment-mant matching oracle (Assumption (C3)). Further suppose we are given trancated samples from qg- with survival mass p. There is an (e. DDD
algorithm that outptt some 8 and f == = [T)) such that ||0 10--0 0- S
ym log p06E m log(1/86) and
with probubility B. Moreover, the algorithm has sample complexity n. running time poly(m, n, d).
The proof of Lemma B.8 is deferred Appendix B.7. As with all other algorithms we present, Lemma B.8 requires only truncated sample access for an exponential family,
We note that past works considered the multi-dimensional Gaussian case [40], but Lemma B.8 is the first to handle truncated exponential families.
Pseudocode. See Algorithm B.3 for pseudocode. As mentioned, it a straightforward adaption of the Gaussian bounding interval algorithm stated by Karwa and Vadhan [30] to the multi dalli-dimeensionl truncated exponential family case.
Algorithm B.3: Bounding Box
Input: truncated dataset D (x(11,,
,..., ,...,,,.11 ,n()), privacy parameters e, E (0, 1), bin length Output: estimator 9 for l and Eymol (xx)]
for coordinate =l..... m do
[a, + s) t bin with largest estimated mass from the output of Privatelfistogram(ia ... x (n) 5/m, 5/m)
> (Proposition B.9)
a 9/2
< MomentMatch(?
return 0,F
Analysis. The bounding box algorithm erucially relies on private histogram algorithm whose guarantees stated by Karwa and Vadhan [30] but follows from the works of Bun, Nissim, and Stemmer [10], Dwork et al. [20], and Vadhan [47].
Proposition B.9 (Histogram Learning; Lemma 2.3 [30]). Consider any countable distribution,
say Z > R4, privacy parameters E, 5 (0, 1/n), error a > O, and confidence B E (0, 1). There an (E, DDD algorithm PrivateRfstogran that outputs estimates p. such that given
8 8lo((//6)
log(4/)
60
2a
samples from p. then
(i) | pllco with probability at least B and
(ii) Prfargmax, Pt S np--
We are now equipped to derive our rough estimation algorithm.
Theorem B.10. Let X be a random vector such that the i-th centered coordinate X, - E[X,]] is (1, 1/)) subexponential for some 17 E (0, 1) and assume we have access truncated samples from some survival set S with mass p > 0. Discretize the real line using bins of length s defined below.
8 log(4/26) log(4/s)
12g(2n/p2)
2
21
Ran the (e, hiisttgrrmm learner (Proposition B.9) on bins length s using the i-th coordinate of n. i..dd truncated samples and output the bin with the largest empirical mass along with its two adjucent bins. Then with probability least - 3, this interval of length 38 contains the untruncated mean [[X.] of the i-th coordinate.
30

---

Proof. Without loss of generality, consider the first coordinate X1. By Proposition A.7,
(-
6
[11 - R[xi]| 2 1 S exxp Pr x>x
21y
But for any event E, we have Pr Pra~xs(]] [E] [E). Hence
2
Pr 2~X8
(101 Ex [x1]] 2 t S
exp
P
21)
Thus with probability 1 1-
log(2/08)
xm Ex [x1]]
2n
We claim that with probability 1 1 Indeed, Let J _ Z the indices of bins which lie beyond distance s of E[X]. Then ΣjeJ Pj I P/n by the choice of s. Thus by Proposition B.9, the probability of outputting any such bin as the central bin is at most (3.
3, the central bin must contain point within distance of [E
Since the central bin must contain a point within distance of [[[]], then by the definition of the bin length, the union of the central bin along with its adjacent bins must contain [[ as desired.
We now ready prove Lemma B.8.
Proof of Lemma B.8. Privacy follows from the privacy of PrivateHisstogram (Theorem 10) and simple composition (Theorem A.4).
Consider a single coordinate from the sufficient statistic of a single sample x qe say T(x) without loss of generality. Proposition A.8 assures us that T(r) [ is (1, 1/))-ssubexpoonntial under the true measure qa- Thus the assumptions of Theorem B. 10 hold and PrivateHi stograa outputs an interval containing [x))). Repeating this procedure with different coordinates from the same dataset yields an estimate & of E[](x)) with O(s) for error or (ss/m) er-erro.. By the X-strong convexity of the (untruncated) population NLL for qa,, MomentMatch (Assumption (C3)) returns some such that ||0 0* (ss X) as desired.
C Omitted Details from Section 4
C.1 Verifying Assumptions from Section 4.1
The isotropic Gaussian density function is given by
(- m1(?)
[-11)a1 exp (uT=-11u01
p) = (2x) exp
2//2 exp
Thus the parameter is given by the mean μ and the sufficient statistic is taken to the identity T(x) We take θ = Rd
Statistical Assumptions.
We first check that Assumption 2.2 holds.
(S1) (Bounded Condition Number) For any μ E Rdd, the covariance of ((,, 7) the identity matrix. Hence À = 1.
(S2) (Interiority) There is a ball of radius 1 about every E IRd.
(S3) (Log Log-Concaviity) Each Ni, I) Idd is a log-concave distribution.
(S4) (Polynomial Sufficient Statisties) T(x) is polynomial of degree l 1.
31

---

Computational Subroutines. Next we describe how to implement the subroutines specified in Assumption 2.3.
(CI) (Projection Acess to Convex Parameter Space) We take = I2 so that the convex projection is the identity function.
(C2) (Sample Access to Log-Concave Distribution) We can sample 2 ~ (N and μ + is sample from (1, I).
(C3) (Moment- MaathnntMatching Oracle) If [[](]] = T, then the corresponding parameter simply 1
C.2 Proof of Theorem 4.2
We now restate and prove Theorem 4.2.
Theorem 4.2. Let E, ax 3 E (0, 1) and suppose that XI 31 2, Al. There is an (E, algorithm such that given samples from Gaussian distribution NO,, ), outputs estimate E satisfying I|I - ---) -(E+) || with probability B. Moreover, the algoritim has sample complexity Ō a1. log(s/aae) de log(3/as) poly(n, d).
(og()s) de log(V/o)) and running time
By scaling if necessary, we can work under the simplifying condition that AI 3 E = 3 for some X (0, 1/8). In Lemma C.2, will see how precondition the distribution that À 2(1).
We begin by verifying that Assumptions 2.2 and 2.3 hold in Appendix C.3, leading to the following corollary of Theorem 3.1.
Lemma C.I. Let e, 8, 3 10, and suppose AI Ex 3 L.. There is an (e, 8)D algorithm such that given samples from a Gaussian distribution NO0,E*) outputs an estimate M satisfying II (E+)-1|r S with probability 1 1.3. Moreover, the algorithm has sample complexity and time complexity poly(n, d).
Ō d log(4/o)) d log(yo) +
d00/>2) log(Yoo)
X
As mentioned, we require private preconditioning algorithm to avoid polynomial dependence 1/x. We extend one such algorithm for Gaussians due to Biswas et al. [7] to the case of truncated Gaussians.
The idea to truncate the data to a centered ball of radius I-p to preserve p survival mass and then apply the following lemma.
Lemma C.2. Let E, 6, a, E (0, 1) and assume AI 3 Ex 1 L. Algorithu C.I is an (e, 6)D algorithm such that given samples from a truncated Gaussian distribution (0, Σ* S) with survival probability p > O, outputs an estimate E satisfying 1 (-*) - 3 OOlog (e))
with probability - 3. Moreover, the algorithm has sample complexity n Ô d log (/2p8)) and runnning time poly(n,
We present the proof of Lemma C.2 Appendix C.4. By combining Lemmas C.I and C.2, we obtain a proof of Theorem 4.2.
Proof of Theorem 4.2. By Lemma C.2, after truncating to B (0), Algorithm C.1 yields constant I-p
enror estimate of the covariance matrix. By Lemma C. preconditioning further samples and
executing the general algorithm for Gaussian covariances as an exponential family (Theorem 3. 3) yields the desired result.
L
C.3 Verifying Assumptions from Appendix C.2
As reminder, we work under the simplifying condition that XI N E 3 I. Let |M] denote the determinant of square matrix M. Let M E-1 denote the precision matrix of (0, E). The zero-mean Gaussian density function parameterized by M is given by
p(x: M)
exp
-x Mx
2
32

---

The exponential family parameter is given by the precision matrix 0 = M and the suffi- cient statistic is taken to be T(x) 2 We take the closed convex parameter space = (M E 84 71 M 1
Statistical Assumptions. Once again, must verify that the Assumption 2.2 is satisfied in order to apply Theorem 3.1. We require the following result by Lee, Mehrotra, and Zampetakis [35].
Proposition C.3 (Lemmaa 9.1 in [35]). Let denote the smallest and largest eigenvalues of the covariance matrix Σ = M > 0. Then
min (X2 v I Cov [T()), 3 mmax(A,3)))
We ready perform the verification.
(S1) (Bounded Condition Number) By Proposition C.3, for any M E O, the Fisher information is spectrally lower bounded by 22(2²) and upper bounded by 1.
(S2) (Interiority) For M - E O, any M' E (M) satisfies
7/ 3 M 3 11/++1TT x
Hence M' and we can take 77 = 1. (S3) Cog-Connayitt) Each (00, M 1), M E θ is a log-concave distribution.
(S4) (Polynomial Sufficient Statistics) T(x)
rr a polynomial of degree k
Computational Subroutines. We also describe how to implement the computational subroutines from Assumption 2.3.
(C1) (Projection Acess to Convex Parameter Space) For any symmetric matrix M E gd its projection onto can computed by solving semi-definite program.
(C2) (Sample Access to Log- Concave Distribution) We can sample 2 ~ _N(0, I) and Σ p is sample from N (0, E).
Σ, then the corresponding parameter is simply (C3) (Moment-Matching Oracle) E[ 2x "]
C.4 Proof of Lemma C.2
Below, we restate and prove Lemma C.2.
Lemma C.2. Let e, 5, a E (0,1) 1) and assume AI -2 3 L. Algorithm C. is an (e, DDP algorithm such that given samples from truncated Gaussian distribution N Σ S) with survival probability p > O, oulputs an estimate E. satisfying Stpp2) 3 - -E(E") (l)o(()o))
with probability 3. Moreover, the algorithm has sample complexity Ō 83.5 log()) and rumnning time doly(n,d).
We emphasize that all algorithms we present require only truncated sample access for an exponential family. While there private preconditioning algorithms without any dependence A/x, it is not clear if their guarantees hold for truncated samples.
Pseudocode. See Algorithm C.1 for pseudocode of the preconditioning algorithm. As mentioned, is a straightforward adaptation of the Gaussian covariance estimation algorithm Biswas et al. [7], with the main difference being the initial truncation step. Due to the bias introduced by truncation, this adapation is only able to achieve a constant-error approximation.
We given truncated sample access zero-mean Gaussian distribution and would like to privately learn its second moment up to constant relative spectral error.
Analysis.
Our proof requires the following facts about truncated statistics.
33

---

Proposition C.4 (Lemma in Daskalakis et al. [17]). Let Es denote the covariance of the truncated Gaussian (0, Σ, S) with survival mass p > The following hold.
(i) max ||--||/a)) 20 of truncated samples x! is O (vālog PB
Es of 1 (1-a)Es = Es (1+a) with probability 1 - 3 whenever n
with probability 1-
(ii) The empirical
covariance
truncated
samples satisfies
S2
d dlog (Lo))
The following result allows us relate the covariance matrix a truncated Gaussian with its original covariance.
Proposition C.5 (Lemma 6 in [17). Let E'g denote the covariance matrix of the truncated Gaussian distribution (o0, E" , SS) with survival mass p 0. Then
2
Ollg((/o)).
We are now equipped to prove Lemma C.2.
Proof of Lemma C.2. Privacy follows by the guarantees of the Gaussian mechanism (Proposition A.2) and simple composition (Theorem A.4).
Following the presentation of Biswas et al. [7]. we can assume without loss of generality we know that 3 E I KI. This can achieve by scaling the data by 1/vā and taking x 1/x. Then by Proposition C.5, ((p²) 3 E's I O log(H/)))T. We begin with the preconditioner Ao == Ve
Assume inductively that have A;-1 such that
Es 3 (A 1) E' (Ath-))) (2- -2-2-
+ x2 x2-
We would like to output some A (3) that satisfies the above induction hypothesis.
By Proposition C.4, the relative spectral error of the sample covariance is at most 1/8 with probability (x) when
1
> (dd
Similarly, by Theorem A.10, the error due to the noise Y added for privacy is at most 1/8 with probability 1 (((og(())
B when
oso (
n 22 (1.5log(//00)) haae///nn////)) In(1/6)
(Vllg(M)))
The rest of the inductive step are simple calculations that can be found Biswas et al. [7, Appendix B.3, arXiv version]. The only difference is that we replace the two spectral norm concentration bounds that Biswas et al. [7] used with the two listed above. After = O(lo((:)) iterations and conditioning on the concentration bounds, the inductive hypothesis implies that
A (v-
ST.
Finally, we pay a multiplicative spectral error of poly(p) when translating the guarantees of the estimate of the truncated covariance to the true covariance.
We remark that Ashtiani and Liaw [4, Theorem 5.4, arXiv version] give polynomial-time (s, 0)- DP algorithm to estimate the covariance up to constant error and with sample complexity that is independent of the condition number. However, it is not clear that their algorithm works without change for truncated Gaussians, unlike the rest of our results (see Remark 3.2).
34

---

Algorithm C.I: Recursive Preconditioning
Input:
n-sample truncated dataset D, privacy parameters E, (0, 1), initial spectral lowerbound bound X, survival probability E (0, 1)
Output: estimator for covariance matrix Σ*
1o)(V))
n'
+ log(n")
3 + log(K')
dv lo'( log(n4/o0) nes
o +
8 R + (Vlolg(d///o))
A(0) - 7/1
for = =0....,v==0N Ollog(ll)))) do
mllh) (1)))( for j E [n]
b || s w.h.p.
mi) po
for E [x]
Z E, wb(((())
sensitivity A = (d/)
11
Y T Gaussian matrix with symmetric entries YiJ ~ ~0,00²
12
((++)) + S Y
Gaussian mechanism (Proposition A.2)
U+ 70+1) + 1
A + (1(
14
return ((
35


Reviews:
[{"review_id": "Hm11qNc1Se", "reviewer": "Reviewer_RRzL", "summary": "This paper introduces a novel framework for differentially private (DP) statistical estimation via data truncation, addressing the fundamental challenge of sensitivity control when the data support is unbounded. The authors propose a truncation-enhanced DP-SGD algorithm that enables efficient parameter estimation for exponential-family distributions while achieving near-optimal sample complexity. The theoretical contributions are significant.", "questions": "1. In practice, how should the survival set, i.e. the ball radius, be chosen?\n2. Could you elaborate on warm-start and preconditioning?\n3. What failure probability beta is reasonable for real-world data sets?", "limitations": "The same as above.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths\n1) Novel and interesting approach. Using truncated data to bound sensitivity in DP estimation is both theoretically sound and practically valuable.\n2) Technical innovations. Compared with [3], the complexity of estimating Gaussian statistics is reduced.\n3) Theoretical proofs. The authors make a substantial effort to establish rigorous theoretical results.\n\nWeaknesses\n1) Although the paper provides strong theoretical results for Gaussian data, it is unclear how to apply the method to real-world datasets. For example, how to choose the survival set in practice is not well explained; how to warm-start and preconditioning; and what failure probability beta is reasonable.\n2) The algorithm is more complex than classical DP methods, so it would be helpful to include visualizations to better illustrate the practical benefits over classical DP. It remains unclear whether the increased computational complexity is acceptable for large-scale datasets.\n3) Many key results rely on a set of strong and potentially difficult-to-verify assumptions. It remains unclear whether these assumptions are realistically satisfiable in practical scenarios. If these assumptions are violated, how the performance or guarantees of the proposed algorithm would degrade?\n4) Although many theoretical results are provided, no numerical experiments or empirical validation are included to demonstrate practical performance, convergence behavior, and related aspects.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback and for appreciating our results. \n\nOur work is primarily a theoretical study, and our main goal is to formalize and rigorously analyze the connection between truncation and differential privacy. While truncation should intuitively synergize with privacy, our work is first to establish a systematic framework with precise utility guarantees and sample complexity bounds. We view this conceptual link as the main message of our paper, and we believe it can open the door to more practical algorithmic developments in future work.\n\nTo the best of our knowledge, our techniques lead to the first algorithm for privately estimating unbounded high-dimensional truncated families, whereas prior works focus on bounded or 1-parameter families.\n\nWe emphasize that we adopt standard exponential family regularity assumptions and the assumptions customary in truncated statistics analyses. We state the assumptions explicitly and quantify how constants depend on them.\n\nPlease find below the responses to specific questions:\n1. In practice, we would ideally choose the survival set to contain a large constant fraction of the distribution, e.g., 90%. This can be a hyperparameter which is tuned. We would like to point out that one benefit of the truncated statistics framework is that the estimator is consistent regardless of the survival mass. This is a feature that is not shared by standard clipping operations to guarantee privacy.\n2. We provide a generic warm-start algorithm in the appendix. Intuitively, it suffices to privately estimate the parameter of the *truncated* distribution, which will be a biased estimate of the true parameter but suffices as a warm start. This is an easier task since the truncated distribution is a bounded distribution. \n\n    We also provide a pre-conditioning algorithm in the appendix. Again, the idea is to privately estimate the parameters of the *truncated* distribution.\n3. In practice, a reasonable rule of thumb is to choose the failure probability beta to be a small constant, e.g., 5%. It may be helpful to think of beta as the significance level of a statistical study which should be set according to the field of study."}, {"review_id": "L7XRCguXj3", "reviewer": "Reviewer_REUx", "summary": "The paper presents a new framework for differentially private (DP) statistical estimation using truncated statistics, focusing on unbounded exponential family distributions. It proposes an efficient DP algorithm for estimating parameters, like Gaussian mean and covariance, with optimal sample complexity. The method truncates data to control sensitivity, corrects bias using DP-SGD and maximum likelihood estimation, and adapts existing algorithms for truncated exponential families.", "questions": "- At line 173, the article supposes that the distributions are absolutely continuous. Is this with respect to Lebesgue measure? If so, what is the technical step that is blocking with more general measures? Conceptually, shouldn’t it work as long as the empirical log-likelihood is almost surely differentiable (in order for first-order methods to make sense) and that the other assumptions are satisfied?\n- I did not see (but I may have missed it) an assumption on the boundedness of the set in which we are searching the parameter. However, without such an assumption, how do you guarantee that the loss is Lipschitz, which is necessary for the privacy of DP-SGD? Indeed, as the losses are supposed strongly convex, the gradients are coercive, and ensuring their boundedness typically requires a priori information on the location of the optimal parameter.\n- Linked to the last question, can the authors detail how the sample complexity depends on the size of the a-priori set in which we expect to find the optimal parameter?\n- In terms of pure technical contributions, is the main technical advancement Lemma 2.1?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- The paper’s is well written and clear, making it easy to follow. \n- The framework for combining truncation with DP is innovative, and recovers optimal sample complexities for Gaussian estimation. \n- The generality of the article make it applicable to many real-world scenarios\n\nWeaknesses\n- It can be hard to tell what’s new versus what’s built on existing results. \n- Moving basic exponential family facts to the appendix and diving deeper into technical contributions would help clarify the paper’s novelty. \n- Also, the paper doesn’t present a single numerical experiment, which weakens its practical validation and leaves questions about real-world performance.", "was_revised": true, "final_justification": "After reading the author’s response, I’ve decided to retain my positive rating of the article, as I believe it’s a valuable contribution.", "rebuttal": "We thank the reviewer for their careful reading, suggestions on the presentation, and for appreciating our results. We will incorporate these suggestions into the camera-ready version of our paper.\n\nOur main conceptual contribution is the connection between truncation and differential privacy. While this seems intuitive, we are the first to formalize this connection and design algorithms with rigorous utility guarantees and sample complexity. We believe this can open the door to more practical algorithmic developments in future work.\n\nWe emphasize that our techniques lead to the first algorithm for privately estimating unbounded high-dimensional truncated families, whereas prior works focus on bounded or 1-parameter families.\n\nPlease find the responses to specific questions below:\n1. We thank the reviewer for pointing out the additional generality of our technique. We indeed assumed absolute continuity with respect to the Lebesgue measure for simplicity to ensure the log-likelihood is differentiable. Our algorithm goes through as long as the latter holds. We will be sure to mention this in the camera-ready version.\n1. We demonstrate how to privately obtain a rough estimate of the parameter (warm start) in Appendix B without any prior bounds. Previous works demonstrated how to achieve this for Gaussian distributions, and we extended the techniques to truncated exponential families. Once we have a rough estimate of the parameter, our algorithm chooses the survival set to be a bounded set of appropriate radius (depending on the warm start), which automatically yields a bound on the gradient norm of the *truncated* log-likelihood function. This is a key benefit of the truncation framework and optimizing the truncated log-likelihood. \n1. Our general algorithm for exponential families does not have any dependence on prior bounds of the parameter (please see previous response).\n1. Technically, Lemma 2.1 shows that it suffices to design DP algorithms for truncated distributions by designing a ``stable’’ reduction from (untruncated) distributions to truncated ones. We hope that this reduction can lead to other DP algorithms obtained via truncation. As noted in Section 1.1, another technical contribution that may be of independent interest beyond our work is the improved uniform convergence result for exponential families (Lemma 3.6), which improves upon prior works by a quadratic factor in the error parameter."}, {"review_id": "vBW1imrSPt", "reviewer": "Reviewer_dfJz", "summary": "The paper considers DP statistical estimation, i.e. estimating the parameter of a distribution given samples from that distribution with differential privacy. Normally, differential privacy requires a bound on the sensitivity of some function (e.g. the sample mean) of the samples, which is at odds with sampling from unbounded distributions. The authors consider methods from the non-private statistics literature for working with samples restricted to a \"truncation set\". They give an algorithm which obtains the optimal sample complexity dependence on the dimension $m$, privacy parameter $\\epsilon$, and error $\\alpha$ of $O(m(\\frac{1}{\\epsilon} + \\frac{1}{\\alpha^2} + \\frac{1}{\\alpha \\epsilon})$ in polynomial time.\n\nTheir algorithm has a number of components and associated proofs. First, they give a procedure for padding/truncating a dataset so all samples appear in the truncation set and the dataset has fixed size, and with high probability the final dataset matches n samples from the distribution restricted to the truncation set, which allows them to work with the replace adjacency. Next, they assume a warm-start which they show can be obtained by a recursive mean estimation algorithm. Given the warm-start they run DP-SGD using the negative log likelihood ratio of the samples as a loss. They show this is strongly convex under an assumption about the condition number of the covariance of the sufficient statistics, hence DP-SGD has a known bounded error for this loss. They also show how to obtain an unbiased estimator of gradients of this loss with bounded gradient norms.", "questions": "* Theorem 3.4 is somewhat outdated. For example, the authors could maybe use results from Section 5 of https://arxiv.org/pdf/2005.04763, which removes an unnecessary $\\log^2 (n/\\delta)$ factor from BST14, and also only requires a single pass which would alleviate the problem discussed in Section 3.3 \"Uniform Convergence of Empirical Likelihood\". Have the authors considered this / is it straightforward to integrate these to simplify the analysis and slightly improve the bounds?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n* First paper to get the right dependence on the privacy parameter $\\epsilon$ and error parameter $\\alpha$ for general exponential families without requiring boundedness or dimension 1. \n* The paper retrieves the best rates for Gaussian mean and covariance estimation using a more generally applicable algorithm.\n* The technical aspects of the paper are reasonably novel; e.g. optimization of the negative LLR is pretty different from the private selection-based approaches used for the optimal results on Gaussians.\n* Presentation in the paper is good; the key steps are frequently outlined throughout the paper, the assumptions are clearly stated, the technical barriers and how they are dealt with are summarized nicely.\n\nWeaknesses:\n* Some of the results from the DP optimization literature which are used as a black box are outdated and the paper might be improved \"for free\" by using more recent results; see Questions for more detail.", "was_revised": true, "final_justification": "I remain happy with the paper, and the authors also nicely addressed my only stated weakness, which was minor to begin with.", "rebuttal": "We thank the reviewer for recognizing the novelty and technical contributions of our work, as well as sharing the reference to more recent work on DP stochastic convex optimization.\n\nThe ``iterative localization’’ technique from [FKT20] does indeed directly optimize the population likelihood in one pass, under the additional assumptions that the likelihood is smooth and the condition number is not too large. For exponential families where we have a private preconditioning algorithm (e.g., Gaussians), this is indeed applicable to our setting and can simplify the proof as well as yield a logarithmic improvement in the bounds.\nHowever, in general, for badly conditioned exponential families, this additional requirement on the condition number bound is more nuanced.\nWe will be sure to include this discussion in the camera-ready version.\n\n---\n\n[FKT20] Feldman, V., Koren, T., & Talwar, K. (2020). Private stochastic convex optimization: Optimal rates in linear time"}, {"review_id": "lUYKnc5pJz", "reviewer": "Reviewer_LDZ7", "summary": "This paper proposed a differentially private statistical estimation framework by using techniques from truncated statistics. They then apply their framework to exponential family distributions. A distribution $q_\\theta$ (on $R^d$) from the exponential families takes the form $q_\\theta(x) \\propto h(x) \\exp(\\theta^\\top T(x))$ where $\\theta \\in R^m$ is the unknown parameter, $h : R^d \\to R_+$ is the base measure, $T : R^d \\to R^m$ is a sufficient statistic. \nThis paper obtains an algorithm with sample complexity that depends linearly on $m$ (dimension of sufficient statistics), polynomially on $1/\\alpha\\varepsilon$, $1/\\varepsilon$, $1/\\alpha^2$, exponentially on the condition number. Their algorithm runs in time poly(n, m, d) (n is the number of samples and d is the dimension of each sample). They instantiate their algorithms for Gaussian mean estimation (with known covariance matrices) and Gaussian covariance estimation. For both problems, their algorithm gets the right sample complexity dependence on the dimension.\nTheir algorithmic framework first chooses a \"survival set\" and truncates data to that set, and then minimizes the empirical truncated NLL function using DP-SGD.", "questions": "- How does the sample complexity in Theorem 3.1 compare with the non-private one (i.e. what can be achieved without privacy)?\n- The framework shares some similarity with the clip-and-noise method. Can you elaborate on their differences?\n- Can the 1-d algorithm from [MSU20] be extended to high-dimensional settings?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:** \n- This paper made a nice observation that results/techniques from truncated statistics could be made use of for DP estimation. I think this connection is very natural and might have great potential. \n- This paper is generally well written.\n\n**Weakness:**\n- The results for Gaussian estimation are actually suboptimal and the claim of (near-)optimality for Gaussian estimation in the paper is overstated. For Gaussian mean estimation (Theorem 4.1), e.g., let's consider the regime when beta is a sufficiently small constant. Then the optimal sample complexity is $d/\\alpha^2 + d/\\alpha\\varepsilon + \\log(1/\\delta)/\\varepsilon$, while the sample complexity in Theorem 4.1 is $d/\\alpha^2 + d\\log(1/\\delta)/\\alpha\\varepsilon$. For Gaussian covariance estimation (Theorem 4.2), their sample complexity depends on the condition number. Although the dependence is only logarithmic, the optimal sample complexity should not depend on the condition number at all.\n- It's not very clear how good the sample complexity stated in Theorem 3.1 is, without enough context about what can be achieved non-privately. I think there should be more detailed discussion. E.g. where does the exponential dependence on the condition number arise?", "was_revised": true, "final_justification": "I think the connection between DP statistics and truncated statistics is nice and natural, but the exponential dependence on the condition number as well as its application to gaussian estimation makes the significance of the contribution questionable. The authors claim one can use private preconditioner to reduce the condition number, but this is usually highly non-trivial and problem specific. Given this, I decide to keep my rating.", "rebuttal": "We thank the reviewer for recognizing the important conceptual connection between truncation and differential privacy. While this seems intuitive, we are the first to formalize this connection and design algorithms with rigorous utility guarantees and sample complexity bounds. We are hopeful that this can open the door to more DP algorithmic developments in future works, obtained via truncation.\n\nOur main result is a private learner for exponential families that only accesses the sensitive data after a truncation pre-processing step. As a bonus, our algorithms go through even if the provided data has already undergone truncation!\nWhen specialized to Gaussian mean estimation, our techniques indeed yields the correct sample complexity up to logarithmic factors in the lower-order terms. We will certainly clarify this in the camera-ready version.\nFor Gaussian covariance estimation, if we are ok with dropping the bonus mentioned above, we can use any private pre-conditioning algorithm to avoid all dependence on the condition number. This logarithmic dependence comes up only under the restricted sample access since it is not clear if previous private Gaussian preconditioning algorithms can extend to the truncated setting.\n\nPlease find below the responses to specific questions:\n1. Using (non-private) SGD to minimize the log-likelihood of exponential families in our setting yields a sample complexity of $O(\\frac{m}{\\alpha^2} \\cdot \\text{poly}(\\kappa))$ where $m$ is the dimension of the parameter space, $\\alpha$ is the $\\ell_2$-error parameter, and $\\kappa$ is the condition number (see e.g. Theorem 4.3 in [42] from references section).\n    \n    We note that the main difference is the dependence on $\\kappa$, which is necessary as it arises from using techniques from the truncated statistics literature to lower bound the strong convexity parameter of the *truncated* log-likelihood function (see e.g. [34] in references section). Indeed, this exponential dependence appears even for (non-privately) estimating truncated exponential families.\n2. One difference between truncation and clipping is that minimizing the truncated log-likelihood function yields a consistent estimator as long as the survival set has positive mass, e.g., 50%. This truncation of half of the data introduces biases that we then remove using our algorithms. In contrast, the clipping radius must depend on the concentration of the underlying distribution, as we must ensure no point is clipped with high probability so that no truncation bias is introduced. We commit to adding a discussion about this in the final version.\n3. If we understand correctly, the framework from [36] in the references section is not generally suitable for estimating multivariate statistics, as it relies on a simple-hypothesis-testing formulation that does not fully capture private estimation for multivariate statistics. Specifically, (private) hypothesis testing and parameter estimation depend on the dimension in different ways.\n\nWe commit to clarifying the discussions above in the camera-ready version."}]

Author rebuttal:

Meta-review: This work proposes algorithms for differentially private (DP) statistical estimation by leveraging recent algorithmic techniques from the area of truncated statistics. The main application is new DP algorithms for certain exponential families. The reviewers appreciated the contribution. While the idea of using some kind of truncation is fairly standard in the context of DP estimation, the connection to the truncated statistics literature is a useful observation. Some concerns were raised on certain extraneous dependencies (e.g., on condition number) in the sample complexity of the resulting algorithms, even for the Gaussian case. While the concrete new implications themselves may not be as strong as desired, the conceptual contribution of the work is interesting and I am inclined to recommend borderline acceptance.
Decision: Accept (poster)