A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input
Authors: Bar Mahpud
Or Sheffet
Venue: NeurIPS 2025 poster ()
Keywords: Differential Privacy
Second Moment Estimation
High-Dimensional Statistics
Subsampling
Private Learning
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We propose a differentially private algorithm that approximates the second moment matrix of any subsamplable dataset, and show its applicability to heavy-tailed distributions and input with outliers.

Abstract: We study the problem of differentially private second moment estimation and present a new algorithm that achieve strong privacy-utility trade-offs even for worst-case inputs under subsamplability assumptions on the data. 
We call an input $(m,\alpha,\beta)$-subsamplable if a random subsample of size $m$ (or larger) preserves w.p $\geq 1-\beta$ the spectral structure of the original second moment matrix up to a multiplicative factor of $1\pm \alpha$.
Building upon subsamplability, we give a recursive algorithmic framework  similar to Kamath et al (2019) that abides zero-Concentrated Differential Privacy (zCDP) while preserving w.h.p the accuracy of the second moment estimation upto an arbitrary factor of $(1\pm\gamma)$. 
We then show how to apply our algorithm to approximate the second moment matrix of a distribution $\mathcal{D}$, even when a noticeable fraction of the input are outliers.

A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input
Bar Mahpud Faculty of Engineering
Or Sheffet Faculty of Engineering Bar-Ilan University Israel or or..heffet@biu.ac il
Bar-Ilan University
Israel mahpudb@biu.ac..)
Abstract
We study the problem of differentially private second moment estimation and present new algorithm that achieve strong privacy-utility trade-offs even for worst-case inputs under subsamplability assumptions on the data. We call an input (m, a. (.s.s,3)suubbmmplabl if a random subsample of size m (or larger) preserves w.p 2 2 the spectral structure of the original second moment matrix up to a multi- plicative factor of 1 a. Building upon subsamplability, we give recursive algo- rithmic framework similar Kamath all (2019) that abides zero- Concentrated Differential Privacy (ZCDP) while preserving w.h.p the accuracy of the second moment estimation upto an arbitrary factor of (1 + 7). We then show how to ap- ply our algorithm to approximate the second moment matrix of distribution D, even when a noticeable fraction of the input are outliers.
Introduction
Estimating the second moment matrix (or equivalently, the covariance matrix) of dataset a funda- mental task in machine learning, statistics, and data analysis. In typical setting, given a dataset of points Rd, one aims to compute an empirical second moment (or covariance) matrix that close, in spectral norm, to the true second moment matrix. However, modern datasets increasingly con- tain sensitive information, maintaining strong privacy guarantees has become a key consideration.
A natural way to protect sensitive data is through differential privacy (DP). In this paper, we focus on the crro-CCnnettrtedd Differential Privacy (zCDP) framework (Bum & Steinke, 2016), which offers elegant composition properties and somewhat tighter privacy-utility trade-off' compared to tradi- tional (e, dD- While there have been works regarding the estimation of the second moment matrix (and PCA), they mostly focused on Gaussian input or vell-conditioned input (see Related Work below). In contrast, our work focuses on general setting, where the input's range significantly greater than Amin. the least eigenvalue of the 2nd-moment matrix.
Suppose indeed are in situation where the first and least eigenvalues of the input's 2nd moment matrix are very different. By and large, this could emanate from one of two options: either it is the result of few outliers, well with DP; or it is the case that the underlying distribution of the input does indeed have very different variances along different axes, and here DP approximation of the input plausible. Our work is focuses therefore the latter setting, which we define using the notion of subsamplability: Namely that from a sufficiently large random subsample, one can recover a spectral approximation to the original second moment matrix with high probability. This property resonates with classical conteniccnnctttttionn results (namely, matrix Bernstein bounds), yet as our analysis shows our subsamplability assumption offers less nuanced path to controlling the tail behavior of the data. In this work we formalize this notion of subsamplability which immediately gives a non son-private
which case it is unlikely to approximate the 2nd moment matrix
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

approximation the data's 's second moment matrix, and show how it can be integrated into a privacy- preserving algorithm with some overhead.
Subsamplability Assumption. Throughout this paper, we assume that our n-size input dataset is subsamplable, which we formally define as follows.
Definition 1.1. ((m, a, ()- >-subsampllbiiltty Let X C Rdd be dataset of points. Fix m S n, 0,3 E (0, (). Let X1...., Xmm be a random subsample of m' 2 m points ii.d from X. Denote Σ XxX?" and Σ = 1 Σ X,X," then the dataset X is (m, a, 3)-susaamllable if:
==
1 n sEIn]
Vm' 2 m Pr((1 Pr(11-aJE =) (1 a}Σ) 2 1- B
By assuming subsamplability, we ensure that the critical spectral properties of the data are retained, enabling efficient and accurate private estimation. This assumption provides a tractable way to manage the inherent complexity of the problem while maintaining robustness to variations in the data. On the contrapositive when the data isn't subsamplable, estimating the second moment matrix becomes significantly more challenging. Furthermore, in the case where the n input points drawn i.i.d. from some distribution (the case we study in Section ! subsamplability follows directly from the convergence of large enough sample to the true (distributional) second moment matrix: alternatively, sans subsamplability we cannot estimate the distribution's second moment matrix.
It is important note that subsamplability assumption is weaker than standard concentration bounds, which state that for any o. 3 there exists m(a, (3) such that a random subsample of m (or more) points preserve w.p.> 1 - B the spectral structure of Σ upto (1 + a)) -fccto. Here we only require that for some 3 there exists such a m(a 3), a distinction that allows us to cope even with situation of well-behaved distribution with outliers, as we discuss in Section EL In our analysis we require that a = O(1) (we set it as a < 1/2 purely for the ease of analysis); however, our analysis does require a bound on the / parameter, namely having 3 O(a/ log(R)). with R denoting the bound on the Le norm of all points. It is an interesting open problem to replace this requirement on with bbo-boonnd as well. is also important note that our result is stronger than the baseline we establish: subsamplability implies that using (roughly) m// samples, one can succesfully apply framework (Nissim all, 20K77) and obtain a = aaproxxmmiooiioo of the spectrum of the second moment matrix. In contrast, our algorithm can achieve a (1 = 7)- approximation of the second moment matrix of the "nice" portion of the input even for y < a (provided we have enough input points). Details below.
the sasaammpl--nndaggreeee
Contributions. First, we establish baseline for this problem. Under our subsamplability assump- tion, we use an off-the-shelff algorithm of Ashtian & Liaw (2022) that follows the "subsamplc-and- aggregate paradigm (Nisssi all 2007) to privately return a matrix Σ satisfying (1 10--24 2a> = Σ Σ +22)EE. We then turn our attention to our algorithm, which is motivated by the same recursive approach given in Kamath et all (2019): In each iteration we deal with input X whose 2nd moment matrix satisfy < Σ A RT, add noise (proportional to */m) to its 2nd-moment matrix and find the subspace of large eigenvalue (those that are greater than v/s for th R 1/m), and then apply a linear transfor- mation 1I reducing the projection onto the subspace of large eigenvalues by 1/2, thereby reducing the second moment matrix of IIX so that it is ~ 3x I. So we shrink R, the range of the input, to
/3/7R and continue by recursion. Yet unlike Kamath et all (201)) who work with the underlying assumption that the input is Gaussian, we only know that our input is subsamplable, and in our setting there could be input points whose norm is greater than /3/TRt after applying II and whose norm we must shrink to fit in the ball. So the bulk of our analysis focuses on these points that undergo shrinking, and show that they all must belong to a particular set we refer to as Pun (see Definition B We argue that there aren't 't too many of them (just roughly a 9/m-fraction of the input) and that even with shrinking these points, the second moment matrix of the input remains t I. This allows us to recurse all the way down to a setting where λ x m, where all we have to do simply add noise the 2nd moment matrix to obtain (1 + apprroxxinonoo w.h.p.
We then apply our algorithm to an ensemble of points drawn from general distribution (even a heavy-tailed one). So next we consider any distribution D with finite second moment Ep where

---

the vector y 1/p1220 for ~ D exhibits particular bounds (See Claim + for further details), and give concrete sample complexity bounds for our algorithm to approximate Ep up to a factor of 1 y w.p. 1 c. We then consider mixture of such well- D with an 77-fraction of outliers. We show that our algorithm allows to cope with the largest fraction of outliers (roughly ((1/d)) provided that the second moment matrix of the outliers Yout satisfies Dou 3 O(. In contrast, the subsample and aggregate baseline (and other baselines too) not only requires smaller bound on 7 but also has a significantly large sample complexity bound. Details appear in Section !!
Organization. After surveying related work in the remainder of Section M. we introduce necessary definitions and background in Section Q In Section [. we survey the baseline of Ashhiam & Liaw (2022), and in Section [3.2 discuss using existing algorithms to estimate the initial parameters of the input we require, namely its range R and its least eigenvalue Amin- Multiplying R² by 1 1/Amin we obtain input that indeed satisfies I = Σ I x7 (with R²/ /Xmin). Then, in Section BK present our algorithm and state its utility theorem, which we prove in Section B.4 Finally, Section illustrates how to apply our framework a general (potentially heavy tailed) distribution, including the case of a noticeable fraction of outliers.
Related Work. Differential privacy has been extensively studied in the context of mean and co- variance estimation, particularly in high-dimensional regimes. Early work by Dwork et all (2012) proposed private PCA for worst-case bounded inputs via direct perturbation of the second moment matrix, laying foundational tools for differentially private matrix estimation. Subsequently, Nissim aaal (200Z) introduced the subsample- -nd--andddg---aa framework, which has since become a stan- dard paradigm for constructing private estimators under structural assumptions.
A significant body of research has focused on learning high-dimensional Gaussian distributions under differential privacy. Kamath et all (2019) introduced a recursive private preconditioning tech- nique for Gaussian and product distributions, achieving nearly optimal bounds while relying on the assumption of a well-behaved (Gaussian) input. Their approach underlies several subsequent ad- vances in private estimation. Building on these ideas, Kamath et all (2022) proposed polynomial- time algorithm for privately estimating the mean and covariance of unbounded Gaussians. Their algorithm, which incorporated a novel private preconditioning step, improved both accuracy and computational efficiency.
Ashtiani & Liaw (2022) proposed a general framework that reduces private estimation its non- private analogue. This yielded efficient, approximate-DD estimators for unrestricted Gaussians with optimal (up to logarithmic factors) sample complexity. Their method also demonstrated the power of reduction-
techniques in bridging private and non- non-private statistics. Atten-Alretal (2021) gave near-optimal bounds for agnostically learning multivariate Gaussians under approximate DP, while Amin et all (2019) and Dong et all (2022) revisited the task of private covariance estimation under e-DP and >CDP respectively. These works introduced trace- and tail-sensitive algorithms for better handling of data heterogeneity.
Recent work has emphasized robustness and practical applicability. For example, [Biswas Et all (2020) introduced a robust and accurate mean/covariance estimator for sub-Gaussian data, and Kothari et all (2022) developed robust, polynomial-time estimator resilient to adversarial out- liers. Further, Alabi et all (2(25) presented near-optimal, computationally efficient algorithms for privately estimating multivariate Gaussian parameters in both pure and approximate DP models.
particularly notable contribution by Brown et all (2023), who studied the problem of differen- tially private covariance- mean estimation under sub-Gaussian assumptions. They introduced a polynomial-tin algorithm that achieves strong Mahalanobis distance guarantces with nearly op- timal sample complexity. Their techniques also extend to distribution learning tasks with provable guarantees on total variation distance.
Our algorithm outperforms prior methods that rely on per-point bounded leverage and residual conditions most notably the private covariance estimation algorithm of Brown al. Brown et all (2023) in settings where the dataset may contain a small fraction of outliers or where individual points may exhibit high leverage scores, but the global spectral structure is preserved in random subsamples. Unlike their algorithm, which requires strong uniform constraints on every data point (i.e., no large leverage scores), our method only assumes a subsamplability condition that holds with high probability over random subsamples. This allows us to tolerate the presence of many multiple
3

---

outliers, provided they do not dominate the overall spectrum. Moreover, our algorithm is tailored for second moment estimation, and achieves strong utility guarantees even when the second moment matrix has large condition number- a regime where the estimator of Brown al (2023) may incur significant error with the presence of outlier correlated with the directions of small eigenvalues. more elaborated discussion demonstrating this setting appears in Section 1
2 Preliminaries
Throughout the paper, we assume that our instance of dataset is subsamplable, as given Defini- tion I
Notations. Let Sd-1 denote The unit sphere in R4 which is defined the set of all points in d-dimensional Euclidean space that have unit norm, i.e., Sd-1 {ær E Rd || = 1]. Here, the superscript - indicates that the unit sphere is object of intrinsic dimension d embedded in IRd.
Let GUE((²) ( denote the distribution over d d symmetric matrices N where for all S j. we have Niy ~ (N o²) ii.d.. From basic random matrix theory, we have the following guarantee.
Fact 2.1 (see e.g. Iao (2012) Corollary 2.3.6). For d sufficiently large, there exist absolute constants [|2 Aovd I Ce-eAd for all 2
C.e such that:
Pr
N-GUE((2))
Definition 2.2 (Differential Privacy (Dwork aL 2006)). A randomized algorithm A satisfies (e, 6)- differential privacy if, for all datasets D and D' differing in at most one element, and for all measur- able subsets S of the output space of A, holds that:
Pr[A(D) E S] S Pr[A(D') E 5
Definition 2.3
Differential Privacy (zCDP) (Bun & Steinke. 20TG). A random- ized algorithm A satisfies p-zeeo-cooncentrated differential privacy (p-zCDP) if, for all datasets D and D' differing at most one element, and for a > 1, the Rényi divergence order a be- tween the output distributions of A on D and D' is bounded by pa,, i.e., D (A(()) S po.. Here, p 2 0 is the privacy parameter that controls the trade-off between privacy and utility, and D, denotes the Rényi divergence of order
Theorem 2.4 (Bun Stemke (2016)). If a randomized algorithm A satisfies p-zero- aeeoocooncentrated differential privacy (p-zCDP), then A also satisfies (c, diifferennt privacy for any ó 0, where:
p v 22ph (t).
Theorem 2.5 (Composition Theorem for p-zCDP), Let M1 and M2 be two independent mecha- nisms that satisfy PI-cCDP and P2-zCDP, respectively. Then their composition Mi M2 satisfies (p1 + P2)-
Technical Analysis
3.1 Baseline
In this section, we provide a baseline for the problem of 2nd mnd-moment estimation using subsample and aggregate framework (Nissim all 2007).. For the lack of space move the entire discussion of the baseline to Appendix Al and only cite here the conclusion.
Theorem 3.1. Let &, 8 be parameters, and let X C Rdd be (m, a, f)-subbsamplalle set of points. Then, there exists an algorithm for which the following properties hold:
1. The algorithu is 4e 4)) Private.
2. The algorithu returns? & satisfying 1E-1/2 1/2 I|| S 20, where XXX..
These guarantees hold under the following conditions:
1. The dataset size satisfies: n 2 800m- max 20(d41/0P) ind/1())))) 8ln(3/e) 12 [in(2/a)
In 11 26
80c
where (sC(vä++/m(te) for sufficiently large constant C C>0 0.

---

2. The subsamplability parameters satisfy m 2 28m/5.
In particular, Item
suggests sample complexity bound of n 92(
d-m(a.0)
3.2 Finding Initial Parameters
Our recursive algorithm requires as input two parameters that characterize the "aspect ratio" of the imput. namely Rmax the maximum distance of any point from the origin, and Xmins the minimum eigenvalue of input. These two parameters give us the initial bounds, as they imply that Amin/ 3 Σ 3 R2 to apply off-the-shelf algorithms, or modify such algorithms, to obtain these initial parameters to Appendix B
maxx J. Due to space constraints, we move the entire discussion, regarding how
3.3 Main Algorithm and Theorem
Next, detail our algorithm that approximates the second moment of the input. Its starting point is the assumption that the ipput has known bound on the L2-norm of each point R, and that the second moment matrix of the input, Σ, satisfies I I R
Algorithm 1 DP Second Moment Estimation
Input: a (m, a, subbsamplel set points X C IRd, parameters: error parameter 5 E (0, 1), privacy parameter p. covering radius R.
(T=))
Set: r) + 2/2, T logr/3
610m
16 10m
C
80m
C c- (660m, Kt R²
2: Σ
ReCDESMM
( X,,,,, C. (1a )m, ( R,T,EE
3: return (1 E
Algorithm 2 Recursive DP Second Moment Estimation (RecDPSME)
Input: a set of n points X
S Rdd parameters: linear shrinking " < 1,
eigenvalue threshold + bound K, radius R, iterations
stopping value C. noise eigenvalue upper bound T. error parameter &. privacy loss
Set 4R
nv2p
2: Sample N GUE(O?)
3: Σ 3 LXX" +N
4: I C' then
5: return E
6: end if
V < Span( (c; eigenvector of Σ with eigenvalue
2 vn])
8: II + nlll + IIy=
(My denotes the projection matrix onto U.)
9: Y - IIX.
where S(Y) = { min 1, T
10: Xnewt + S(Y)
BEY
X Xnext, n, C, 2, 3 T.,,,E.P)
11: Enee RecDPSME
return
7 2
In our analysis, the following definition plays key role. Definition 3.2. Let X be (m, a. subsamaaleel set. We denote Ptail as the set of points whose projection onto some direction u in Rd is m times greater than expected, namely
Pmi : 3u CEEE Rd: (I, w)2 ml1 + Σ (x, ux)
5

---

Theorem 3.3. Fix parameters & E 1). P > 0,y > 0 and 2 1. Let X C R be a (m, a, 5)- subsamplable set of n points bounded L2 norm by R2, with a S 1/2 and 5 4(1+a) logí (I prumm
(1-a )R²
s.r. 1=13 R2I where Σ have that Algorithu D satisfies p-2CDP,", and if
n Xxx". Then, denoting logr/s
O (2/m)), we
640m
d (VTlog(T/e) + log(1/s)
n 2 Ω
m "V7
Then (1) Piuut holds at most a (843") )-fraction of |X], and (2) w.p. 2 2 it outputs Σ such that:
m
(1 11-7 (1 (1+
where Daf
Σ
xx
Pa
3.4 Algorithm's Analysis
Next prove Theorem
Momentarily shall argue that Algorithm 2 repeats for at most iterations. Based on Fact 2 and on the bound on the number of iterations,
3.
T = logo/a 640m
is simple argue that the following event holds w.p. 2 1 E:
: in each iteration of Algorithm / we have |[ S cR² = =c ck
which follows from the fact that in each iteration the upper bound on the largest eigenvalue of Σ is most R2. We continue analysis conditioning & holding.
The analysis begins with the following lemma, that shows that under we have that in each iteration the cigenvalues of E decrease. Its proof is very similar to the proof in Kamath et all (MIT) and so deferred to Appendix C.
1, and s.t. I 3 Σ 3 k/ where Σ = _xx Let + Span( (u. : A 2 xx}} of the largest eigenvalues of the
Lemma 3.4. Given X {X1, ..., Xn3 Rd, C > 0, 0,0 < 17 < 1,0
noisy E and let Il rilly + 11... Given that: Ω m
In (T/))
Then:
(1
1 ) < IIII 3 (1² + き + 2c)
In particular, if C for some then: I
IESI
C(n +. kT.
Corollary 3.5. Given X = (X1, Xn) C Rd and x 2 s.t. 1 1 Σ 3 kl where Σ 1xx². Let V, 11 be as in Algorithm E and set 17 1/2, vi = 1/10m, 1/80m and C 640m in Lemma k2! Then w.p. 2 E: &:
(1 80m 1 HEI < (1
1 xl
8m
In particular, if C then: I 1 IIII v End.
Based Corollary 5% we can bound the number of iterations of the algorithm.
(GZ_))R) 6.0m
Corollary 3.6. Algorithm D has T logr/s
iterations.
Proof.
The algorithm halts when (2)T
(
1 1-a
k
S
C
640m so: T > loga/1
( )x
640m
( )R2
logr/a
640m
Note that the privacy of Algorithm @| holds for any input X with bounded L2- regardless of X being subsamplable or not.

---

With II reducing the largest eigenvalues of Σ from x to 8n/7. we now proceed and bound the radius of all datapoints by from to /3/TR. This is where our analysis diverges from the analysis in Kamath all (2019). Whereas Kamath et rely on the underlying Gaussian distribution to argue they have no outliers, we have to deal with outliers. For purpose, datapoint is outlier if the shrinking function S (Step 10 in Algorithm 2 reduces the norm of Hl since ||[|=]|| v2/RR. In the following claims we argue that all outliers lie Pai (Definition 6,2),, and moreover, that by shrinking the outliers do not alter the second moment matrix all too much. We begin by arguing that there aren't 't too many outliers.
Claim 3.7. Analogously Definition ST fix any m' 2 m and define Pan(mm)) = fx E X Fu
Rd (x u)² m' + a) E,(r) (a) )) Then holds that
[x E Pum((m)) B + ,82 m'
Pr #ERX
Proof sketch. The proof applies the (m, a, Jysuubaamlllbility property: if a point violates the bound, it would contradict subsamplability with non-negligible probability. A simple union bound and tail approximation then yield the claimed bound. Full details are deferred to Appendix CF
Lemma 3.8. Let X be a (m, a, 3) s)ssussamplable with 3 4(1+a) log(
Let P = X Preit-
Then:
Vu E Rdd Da, 2 a))
Σ xEX
(x, u)²
ZEP
Proof sketch. We partition the tail points according to the magnitude of their contribution and apply Claim B.7 to bound the measure of each bucket. Summing across buckets shows that the overall loss from removing the tail points is small. Full proof deferred to Appendix ME
Lemma 3.9. At each iteration t of Algorithm only points belonging to Pun are subjected to shrinking, given that < 1/2, 1/- T0m and 80m
Proof sketch. The proof uses induction over iterations. Shrinking happens only if a point's mass in low-eigenvalue subspace is too large. By carefully tracking how shrinking operates and applying Weyls theorem and Lemma BR we show that only initially bad points (i.e., those in Pmi)) can cause such violations. Full proof appears in Appendix C.4.
Corollary 3.10. In all iterations of the algorithm it holds that Σ T, namely, that the least eigen- value of the second moment matrix of the input is 2 1.
Proof sketch. We argue by induction that removing or shrinking tail points preserves a spectral lower bound. Using Lemma H.N and the shrinkage structure from Lemma B.Y the transformation at each step maintains the least eigenvalue above Full proof provided in Appendix 6%)
Proof of Theorem 3.5 First we argue that Algorithm D is p-zCDP. Given two neighboring data sets X, X' of size n which differ in that one contains X; and the other contains X the covariance matrix of these two data can change in Spectral norm by most:
(X,X n
< 1 [[(, - Xx)(x, n
< } |((x Xx)xal(XX S
(2R)² n
7
Since Algorithm invokes T calls to Algorithm Ø each preserving P/T-2CDD thus the privacy guar- antee of Algorithm [I follows from sequential composition of zCDP.
We now turn to proving the algorithm's utility. From Claim B.7 we conclude that |Pual indeed at most
B+0² ffraction of X We prove by recursion that: (1 E E - (1 7)
Stopping Rule:
Let T be the input at the final iteration T and let P = X Pun. Denote Σ(-) as the second moment matrix operator. We know that throughout the algorithm, the points from P were not shrunk. Moreover, Corollary BTll assures that the least eigen value of Σ(X) is 2 1. Additionally, our bound on yields that when x S then the noise matrix N we add satisfy that required.
|||] < 7 w.p. 1- - c. It thus follows that (1-7)Σ(X²). E+N 3 (1+7)E(X²)
7

---

Recursive Step: Let X be the input at iteration t < T. Then, by Lemma B4. we have: 3 E
& IKI. Lemma B. ensures that SIIX)* shrinks only points from Pai and so Corollary B.10 assures that the eigenvalue is 2 throughout the recursive iterations. Hence, by the inductive hypothesis, our recursive call returns Erec such that:
(1 Eier (VG
3 Exe 3 (1+ +) (vā
which implies:
(1 (1- 5 -1 3 (1 + ,))i(())
Proving the required for any intermediate iteration of Algorithm
4 Applications: Coping with Outliers
4.1 Input Drawn from 'Nice' Distributions
First, we show our algorithm returns an approximation of the 2nd-moment matrix when the input is drawn from a distribution D. Throughout this section, we apply the
Inequality. Σ, Zi whose mean and have norm
Fact 4.1. Let Z be the sum of i.i.d. matrices bounded by || Z S almost surely. Then, denoting o² ||[ZZ]]|- it holds that
12 /2
Pr[l t) 2d exp
0² Rt/3
We can apply Fact I above to measure how well the sample covariance estimator approximates the true covariance matrix of a general distribution using the following claim (proof deferred to Appendix C.).)
Claim 4.2. Let D be distribution Rd with finite second moment Σ. Consider random vector y chosen by drawing x D and then multiplying y = 1/1 Suppose that ||y|| < M1 a.s. that we
also have a bound [.("" "")""" < M2. Fix a, 3 0. we draw max 2M4
2(1+
a²
3a
In (4d/3) examples from D and compute the empirical second moment matrix Σ, then w.p. 2 B holds that
-Σー I12 Sa
Recall that + (1++)--pproxxima the 2nd-moment matrix the input w.p.2 - Thus, need the input itself to be (1 7)-approximation of the 2nd-moment matrix of the distribution. (We can then apply Fact A argue we get 1 + O(7) approximation the distribution's second moment matrix.) This means our algorithm requires
m(a,8 9)
d
m(7,5) +
log(
log(log( (i,e(((mm))) 1/E)
Amia
for a = 1/2 and 8 = O log Tog ) in order to return (1 ((t))))approiimatiio of the 2nd mo- ment of the distribution w.p. 2 O In Appendix D we give concrete examples of distributions for which this bound is applicable, including (bounded) heavy-tail distributions.
4.2 Distributional Input with Outliers
Next, we consider an application to our setting, in which we take some well-behaved distribution D and add outliers. Consider to be distribution that for any 7, [ > 0 m m subsamllaaeee for m = ( dl((%))) ). We consider here inputs that are composed of (1 - -))-faction of good points and p-fraction of outliers. We thus denote the second moment matrix of the input as
Σ (1 7) + T)Enut
We assume throughout that the least eigenvalue of Exp is Amin- Our goal is to return, w.h.p. (2 1-9 an approximation of Ep using DP algorithm.

---

Inapplicability of Brown et al (20233). The work of Brown et all (2002) shows that if the input has X-bounded leverage scores, namely, if Vx, x" x²(" (²xx""= S X, then they recover the second
moment of the input with 0 v overhead to the sampling complexity. However, in this case one Amin (provided the input has L2-norm bound of R). We argue that the algorithm of (Brown et all (2025) is unsuited for such case. Indeed, the algorithm of Broww et all (2023) has an intrinsic "counter" of outliers (referred to as score), which when reached (11/c) causes the algorithm to return 'Failure'. So either it holds that 1) is so small that the overall number of outliers constant (namely, ym = O()/)), or we set the bound on the leverage scores to be n2² Amin and suffer the cost in sample complexity.
can set outliers so that their leverage scores is Am/Amin
A Private Learner. Suppose lj is very small. In this case we can simply take some off-the-shelf (e, 6DP algorithm with sample complexity m(7, e, 6) that approximates the second moment ma- trix, and run in over a subsample of m points out of that input. In order for this to work we require ). so that a subset of size m would be clean of any outliers. that By would be smaller than O m,,)...,,))
Subsample and Aggregate. The framework of Subsample and Aggregate (Nissim et all. 2007)) in a way 'perfect fit' for the problem: we subsample 1 datasets of size m(1, E) each, and then wisely aggregate the (majority of the) t. results into one. However, in order for this to succeed, it required that most of the subsamples are clean of outliers. In other words, we require that the
probability of dataset to be clean ought be 1/2, namely - (1 (1-n))(x.4) > 1/2 or alternatively that 7 = ( minr,)) ) which in our case means 17 O Togta/e) ). We analyze this paradigm as part of the subsample-ane hatp-nple-and-ggggee aggregate baseline we establish (Appendix A)), and the subsample caaampll-and-aaae aad--and--gggg -aggeaaate baseline requires
ò (a (M-m(rrs)) =ō (0(0
(m- (dLlog(d/3) log(d/3)
d
e73
in order to return (1+) approximation of the 2nd moment of the distribution w.p. 2 1-0
Our Work.
Our work poses an alternative to the above mentioned techniques. Rather than having m():g) we have a slightly more delicate requirement. We require that there exists a = 1/2 and
1
B such that 17 0( m(a, +) )- (In particular, for the given 'D it implies that we require B - 12 logg Aani
that 17 = dloggd) log( R/ RR/Amin.) )) which is considerably higher value than in the case of subsample and aggregate discussed above.) This way, we can argue that w.p. 2 - 8 it holds that a subsample 2
of size m(a, ) contains only points from D and that w.p. 2 1 _ that sample is 'good' in the sense that its empirical second moment satisfy & m Ep.
However, we also require that the subsample of size m(a, 9) would satisfy that its empirical second moment matrix satisfies that (1 - 1 = & = (1 + ف since we set = 1 As E ~ Dp it follows that suffices to require that
(1 - 1( ED + S 3 Ex 3 (1 (1+ + D) + F)utt
1
Some arithmetic shows that the upper bound is easily satisfied when 1 / (which clearly holds for our value of 17), yet the lower bound requires that we have
1 + +1EE 0(11))D Tq
Eout
Under these two conditions, our work returns w.p.
- O(E) a matrix & that satisfies that
Σ > (1 - ((T))ED, with sample complexity of
0 + G) /dloot////mii log( log log(
(R/mmin))
=0 d dlor(d/E)
/ log(d) log (2 (B/ Amna) log log (R/mmin)
TVP
2 "oorcover, in their algorithm, this 'score' intrinsically cannot be greater than k O(1/e) as they use a particular bound of the form k/e.

---

Acknowledgments and Disclosure of Funding
O.S. is supported by the BIU Center for Research Applied Cryptography and Cyber Security in conjunction with the Israel National Cyber Bureau in the Prime Ministers Office, and by ISF grant no. 2559/20, Both authors thank the anonymous reviewers for their suggestions and advice on improving this paper.
References
Aden-Ali, I., Ashtiani, H., and Kamath, G. On the sample complexity of privately learning un- bounded digh-dimensional gaussians. In Feldman, V., Ligett, K., and Sabato, S. (eds.), Pro- Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pp. 185-216. PMLR, 16-19 Mar 2021. URL httpp://pprocsedings mlr wwtppppwwsepepppppppppppppp/eeea aden attp:///dennaaaaaliae ali2la. html.
ceedings of the 32nd International Conference
Alabi, D., Kothari, K., Tankala, P., Venkat, P., and Zhang, F. Privately estimating a gaussian: Efficient, robust, and optimal. In Proceedings of the 55th Annual ACM Symposium Theory of Computing, STOC 2023, pp. 483496, New York, NY, USA, 2023. Association for Computing doi: 10.1 10.1145/3564446.355557
Machinery. ISBN 978 1450399135.
URL https://dot org/
10. 20.1145/3354240 95555555422443355194444
Amin, K., Dick, T., Kulesza, A.. Munoz. A., and Vassilvitskii, S. Differentially private covari- ance estimation. In Wallach, H., Larochelle, H.. Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL https::/procceedigggg htwp:eeeeednnnnn.nnnrr.r....eeee weeurrps.ccppappee. http/ppprr.ilees/pppe///////// pdf.
Ashtiani, H. and Liaw, C. Private and polynomial time algorithms for learning gaussians and beyond. In Loh, P.-L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 1075-1076. PMLR, 02-05 Jul 2022. URL
mlr wwwppppwwwee/aeeeeetppppppppee /tt/////t/t/tan222.aamm html,
Biswas, S., Dong, Y., Kamath, G., and Ullman, J. Coinpress: Practical private mean and covari- ance estimation. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 14475 14485. Curran As- sociates, Inc., 2020. URL htll://5eeeee//5522222///2266660
files/ patpse//appppp/2....//
pdf..
Brown, G., Hopkins, S., and Smith, A. Fast, sample-efficient, affine-invariant private mean and co- variance estimation for subgaussian distributions. In Neu, G. and Rosasco, L. (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 1578-5579 PMLR, 12-15 Jul 2023. URL https://proceedingg mlr.press.
7195/bromn23a html
Bun, M. and Steinke, T. Concentrated differential privacy: Simplifications, extensions, and lower bounds. Cryptology ePrint Archive, Paper 2016/816, 2016. URL https://pprint iacr. org/ 2016/816.
Dong, W., Liang, Y., and Yi, K. Differentially private covariance revisited. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 850-861. Curran Associates, www.r//rooooddioe...........o..p neurips cc/ cc/paper files/ pappr/2022/filee
Inc., 2022. URL 05/405Id/3aa htt.a//w......aaaaaaaaaoooooornn Ponttro pdf.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In Halevi, S. and Rabin, T. (eds.), Theory of Cryptography, pp. 265-284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. ISBN 978-3-540--3732-55.
Dwork, C., Talwar, K., Thakurta, A., and Zhang, L. Analyze gauss: optimal bounds for privacy- preserving principal component analysis. In Shmoys, D. B. (ed.), Symposium on Theory of Com- puting, STOC 2014, New York, NY. USA, May 31 June 03, 2014, pp. 11-20. ACM, 2014.
10

---

Kamath, G., Li, J.. Singhal, V., and Ullman, J. Privately learning high-dimensional distributions. In Beygelzimer, A. and Hsu, D. (eds.), Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp- 1853-1902. PMLR, 25-28 Jun 2019. URL https://proceediiii
mlr wwwppppwssseeeepeeppp http//kamtttttee htmll
Kamath, G., Mouzakis, A., Singhal, V., Steinke, T., and Ullman, J. A private and computationally efficient estimator for unbounded gausstans. In Loh, P.-L. and Raginsky, M. (eds.). Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 Proceedings of Machine Learning Research, pp. 544-572, PMLR, 02-05 Jul 2022. URL sttps://proceediii
mlr pres/
v178/kamath22a.11 html.
Kothari, P., Manurangsi, P., and Velingker, A. Private robust estimation by stabilizing convex relax- ations. In Loh, P.-L.. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 723-777. PMLR, 02-05 mlr
Jul 2022. URL sttps::/proceeeeee http://oooeeoaaaaa....peeeeeeeaa httpppeee//11///ochrrr2222
html.
Mahpud, and Sheffet,
differentially private linear-time fptas for the minimum enclosing ball problem. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 31640-31652. Curran As- sociates, Inc., 2022. URL https:: neurips cc/paper www.s/paper//a// pdf.
file/cad800fff2008aaaae Eigeedaebbfc000aaeeeeeeeee000222
Nissim, K. and Stemmer, U. Clustering algorithms for the centralized and local models. In Janoos, F., Mohri, M., and Sridharan, K. (eds.), Proceedings of Algorithmic Learning Theory, volume 83 of Proceedings of Machine Learning Research, pp. 619-653. PMLR, 07-09 Apr 2018. URL https://prooceeding. mlr. prwss/ v83/ ni missimi8a. html.
Nissim, K., Raskhodníkova, S., and Smith, A. D. Smooth sensitivity and sampling in private data analysis. In Johnson, D. S. and Feige, U. (eds.), Proceedings of the 39th Annual ACM Symposium on Theory of Computing. San Diego, California, USA, June 11-13, 2007, pp. 75-84. ACM, 2007.
Nissim, K., Stemmer, U., and Vadhan, S. Locating a small cluster privately. Proceedings of Symposium Principles of Database Systems, SIG-
the 35th ACM MOD/PODS16, pp. 41 413427. ACM, June 2016. doi: 10.1145/2902211.2900 22902299.....
URL kttp:
//dx. doi. org/10....... 1145/290225/ 2902296.
Tao, T. Topics in Random Matrix Theory. Graduate studies in mathematics. American Mathematical Soc., 2012. ISBN 0780821885077
URL attps://books google..ooo..oooooooooooooo..... co co..
UHLNPTOC

---

A Baseline
In this section, we provide a bascline for the problem of 2nd-moment estimation using subsample and aggregate framework (Nissim et (20077)).
In this baseline, we work with the following notion of a convex semimetric space. The key property to keep in mind is that for semimetric spaces, we only have approximate triangle inequality, as long as the points are significantly close to one another.
Definition A.1. Let y be convex set and let dist y x - Ryo. We say ()), dist) is a convex semimetric space if there exist absolute constants t 1, 2 0, and such that for every k E N and every Y, Y1, ..,.., Yx E y, the following conditions hold:
1. dist(Y, Y) and , 122 2 0.
2. Symmetry. dis V2) dist((Y2, Y1).
3. t-approximate r-restricted triangle inequality. both dist(Yí, Y2), dist(Y Ya) s r,
then
Yis S t. (dist(Y,, Y2) + dist(Y2, Ys)).
4. Convexity. For all a E Ak.
dist (aavii) s Σ ar,is((Y, Y).
5. d-Localiyy, For all a, E As.
dist Eart s
<Elo, a'l (2((0
(0+ max dist(Y,, Y,) in
where A₁ denotes the k-dimensional probability simplex. When is unspecified, we take it to mean r oc and refer to it as a t-approximate triangle inequality.
The following technical lemma (whose proof appears in Appendix C in Ashtiani & Liaw (2022)) is helpful for learning second moment matrices.
Lemma A.2. Let Sa be the set of all d positive definite matrices. For A, B E Sa, let
dist (A, B)
-
I[]}.
Then (Sa, dist) is convex semimetric which satisfies approxxmpt 1-restricted triangle in- equality and 1-locality.
Based on Lemma A. the following distance function forms a semimetric space for positive definite matrices:
max([|E2 1/200011/,,000./////// 1/25,, " //2/2 Iall |E] Σ2 1/>
Iall)
rank = rank otherwise
dist(En, (E, Ex)
x
Fact A.3. Let A, B be d x d matrices and suppose that ||A- - I|| S 5 1/2. Then |BB-1/ABB-1 1/2 < 4y
12

---

Algorithm 3 Baseline DP Second Moment Estimation
Input: a set of n points X C RR, subsamplability parameters m, a, 3, error parameter E (0, 1),
privacy parameters 6.
Randomly split X into T [*/m] subgroups XI...., XT of size m.
2: for Wrtte E [T' do
3: Σi _ XxX?"
4: end for
5: fort E [T] do
6:
+ 7lit' E [T] dist(E, Ev) s
2a I-a!
7: end for
8: Q - + q:
9: Z ~ (Lap(3/T,e,
10: Q- 7
11: iQ < 0.8 Tr.
In(1 + c--1) then
12: fail and return 1
13: end if
14: for [T) do
15: Wi = =min(1, (0 0.6))
16: end for
17: Σ + EIE(T) / EiE(T] Wt
18: N ~ NOO0, 1)x
19: 1 asc(va+ (n(())) {C some large constant]
20: return Σ = (1 + nI + nV
Lemma A.4. (Utility Analysis) Let E = X X and set 4SC va+ vm((/e)) for sufficiently
large constant C > 0. Then w.p. 2 1 - Algorithm B returns Σ such that dist(E, Σ) S 2a given that:
10m
e and 2 g
23n
In(1
28
Proof. Indeed, we have that
-/ーV/ 7 = N)(++ ( IlI
3 2 + 1NNNN
$ 2n + vin(4() + + vin()))))
where we used the fact that || S C(vd + (n(e/)) w.p. 2 1- 6/2. Applying n as defined in the lemma gives that:
E カー 1 < 2/12
Following from Fact A we have that:
/Éー1/ 1| < 4/3
So we have that dist( $0, 52) S a/3.
Now we show that dist(E, 9) S w.p. 2 1-2
Based on the subsamplability assumption, we know that w.p. 2 (1 (1- ()T
Vt E [T] dist(E,, <a
It means that w.p. 2 (1 3) all l + t' E [7] satisfy:
dist E, Σ) < a
2a
dist(E, Ex)
dist(Eir, )) < a
1-a
Hence w.p. 2 (1-BY 2 > 8/2 all [T] satisfy:
1 { E [T] dist(E Ex) 5 1 -
2a
q: T
=1
13

---

Finally, Q = 1>11>>0 > 0.8 + w.p. 2
2.
In + e'11 w.p. 2 f/2 and therefore the algorithm does not fail 28
Te
Now obviously dist(E, )) - since Σ is weighted average of E..
So have that dist(E,, Σ 0/3 and dist(E, Σ.) w.p. triangle inequality for the dist function, we get:
Applying the 9/2-approximate
Σ 1 I||
3
a
+
a
=
2a
2
3
Lemma A.5. (Privacy Analysis) Suppose that:
2d(d 1/67)
8d 8d
8ln(2/6)
12 12
(2/())()/))
800m
max
67)
Then Algorithm is (2e, 46 DD-.
Proof. By basic composition of Truncated Laplace Mechanism and Lemma 3.6 of Ashtiant & Liaw (2022).
Both Lemma A4 and Lemma A.5 together imply the following theorem:
Theorem A.6. Let E, e, 8 be parameters, and let X C R&d be a (m, a, -ssussappllll set of points. Then, for Algorithm B the following properties hold:
1. Algorithm satisfies Ae (2e,4e -Diffeerentti Privacy.
2. The algorithm returns E such that dist(E, 2a, where E LXXT.
These guarantees hold under the following conditions:
1. The dataset size satisfies:
2d(d 1/72) 8d 8d//n(2//) 81n(2/)) 12 12/d1n(2/)) In (1+ - )))
800m-
max
en
80c
where 17
4SC(va+ /in(te) for sufficiently large constant C 0.
2. The subsamplability parameters satisfy 2 23n g
B Finding Initial Parameters
Our recursive algorithm requires input two parameters that characterize the "aspect ratio" of the input, namely - Rmmax the maximum distance of any point from the origin, and Amin. the minimum eigenvalue of the input. These that Amin' = Σ < R. We detail here the algorithms that allow us to retrieve these parameters. Finding Rmax is fairly simple, as it requires us only to apply off tie-hhe-sheff algorithms that find an enclosing ball of the input points (Nissim et all (2016); Nissum & Stemmen (2018); Mahpud & Sheffel (2022)). Finding the minimal eigenvalue is fairly simple well, and we use subsample- and-aggregate framework. Details follow.
parameters give the initial bounds, as they imply
Finding a Covering Radius of The Data
Definition B.I. A I-cluster problem (Xd xx,,,, 1) consists of a d-dimensional domain Xd and param-
eters n 2 t. We say that algorithm M solves (xd, d n, t) with parameters (A, w. B) if for every input database E (Xd)² outputs, with probability at least 1 - 3, center and radius such that: (i) the ball of radius around contains at least - A points from S: and (ii) S Tops, where Topt is the radius of the smallest ball in x containing least points from S.
14

---

Theorem B.2 (Nissim & Stemmer (2018)) Let n., t, 1,,,,,,,, e.8.8 be s.t.
t20 0.11 vd
nd
glog (2)x
log
log
log
B
36
33
There exists an (c. difffereent private algorithm that solves the L-cluster problem X n, with parameters (A, w) and error probability 3, where w = =0(1) and
0.1
A
log
log
glog (2]x]va)
38
In words, there exists an efficient (e, 5) -differrntiall private algorithm that (ignoring logarithmic factors) is capable of identifying ball of radius O(rape) containing t t- ((" points, provided that 2 O( va/c).
Finding Minimal Eigenvalue The algorithm described in Kamath et all (2022) (Section 3) pri- vately estimates all eigenvalues of the second moment matrix of the data. However, for the purpose of this study, we focus solely on identifying the minimum eigenvalue while maintaining the privacy guarantees provided by the algorithm. To adapt the algorithm, we modify its structure priori- tize the computation the minimum eigenvalue directly, rather than estimating the full spectrum only reduces computational overhead but also aligns with
of eigenvalues. This simplification the specific objectives of our work. Below, we detail the adjusted methodology and highlight the changes made the original theorem.
Algorithm 4 DP Minimum Eigenvalue Estimator
Input: a set of n points X C Rd, subsamplability parameters m, a, B, error parameter & E (0, 1), privacy parameters e, 6.
1: Randomly split X into T [n/m]] subgroups XI,..., Xy of size m.
2: for E [7) do
3: Let X Xmnn be the minimum eigenvalue of 1 XXxT
4: end for
5: Ω 1- 2 (..., [(1 a)², a), 1), a (-app)... (. [[000]]}
6: Divide [0, oc) into Ω
7: Run (e, DDP histogram on all Xmmin over S2
8: if no bucket is returned then
9: return
10: end if
Let [e, u| be non-empty bucket returned and set Xmin + l. return Xmin
Theorem B.3. ((Differentially Private Eigenvalue from Kamath all (2022)) For every
8, > 0, the following properties hold for Algorithmm B
1. The algorithmm is (e, -)diifferentially private.
2. The algorithu runs in time In(f/4mmm111(/4)))))
3. if:
m mln(())))))
2,8n
n n O
and m 2 In ( (-//2)
then outputs Smin such that with probability least &, Amin [(1 ax) Amins (1 Amin) where Amin is the minimum eigenvalue of XXX.
Proof. Privacy and running time is proven by the theorem of stability- based private histograms (See Lemma 2.6 in Kamath et all (2022)). Now, we move on to the accuracy guarantees. By subsamplability, with probability at least - 6/2, the non-private estimates of Aman must be within a factor of (1 + ar) due to our subsample complexity. Therefore, most two consecutive buckets would be filled with X S. Due to our sample complexity and private histograms utility, those buckets are released with probability at least (1 6/2). which proves our theorem.
D
15

---

C Missing Proofs
Lemma C.I. (Lemma restated.) Given X [X Xn3 C R C 0, 0,0 1
1,0 < v < 1, and K 2 s.t. I 3 3 kl where Σ _Xx*. Let V + Span( ( : A 2 {x) and
Il ylly + 1.l. Given that: 2 0 m dI (T(7/s) Then:
(1
17 - ) = IEI = (1²² + + + 2c)
In particular, if > C for some constant C' then:
17 + 1b KI
I I
IEN 3
(1 C
Proof. First we prove the upper bound. Note that ||ЛI 2 || - -N < || + ||
So we bound the two terms separately. Using Fact 2. with A O in(3/e) for sufficiently large
we get ||2 I ck w.p. 1 - 6/2. Additionally |IEII||| s
+ I[ll Ellv= s
cc) D (172 + sh + c)r. So overall,
| S (n) + 2c)n
Next we prove the lower bound. Let u E S Our lower bound requires we show that nz" TTETe 2 We consider two cases:
7 p
Case 1: || < -
Since y : + ||TTvu|2 =1 we have [ u1l > (1
1/-00 1))
hence, using the
fact that > we have that
1 71 c K
I'IE' 2 |ul 2 ||] (1
Case 2:
|| 2 -
Note that u" "IEll = u 11 N) = THiSi - x² I1NII. So we bound each
term separately. We know that
" TET u Tl Eu 2 r>>b<<][Tll
Additionally, based on the bound on the spectral norm N we have that an IINII S os [u|| v ex]|[Tyul|? So overall:
u MEE 2 (1/ [u 2
Claim C.2. (Claim 3 restated.) Analogously Definition 532 fix any m' 2 m and define Paa(m') = {a E X: Eu E Rdd (xFuy² > m²(1 + a) (x) 2). Then it holds that
Pr Ix Pai(mmm) < + g2 xERX
m'
Proof. Let E X be datapoint and X = (xi,..., Xme) } be subsample of m points i.i.d from X. From subsamplability we know that: Pr[(1-a)E= E (1+a) 2 1-3 where Σ ==1 " xEX
Σ xxT
and Σ /. Σ X.XT. In other words:
iE(m']
Pr|Vu Rdd (1-auu-x S Th (1 aju 1-
Clearly, even a single To E (mn(mn) belongs X then we'd have that for some direction u we have
1 Σ (xF
1 1
T Su
(oo (1+ aju' Eu
m
m
16

---

contradicting subsamplability. It follows that w.p. 2 1- 3 no point in X belongs to Pun(mm)) Thus, if we denote p Pr I E (ma))m) then we get that 1 (1 (1-p) Using known inequalities =ERx
wC get pm 2 (1 - p) 2 1 e B- therefore p S S+92
m
Lemma C.3. (Lemma 6 restated.)
Let X be a (m, -usbummmplll with S
Let P X
Prait- Then:
4(1++) log( (I (amm)
Vu Rd: E
u) u1)
a)
Σ
(2, u)²
n x
xEP
Proof. Fix direction u, and denote XP = 1 Σ (r, u)² and A
Σ
(c,, u)? Our goal is to prove
PEP
wEX
that À - X S ad.
Assume that Punl holds p-fraction of X, and denote also Atall
E (e, u)? Hence:
PPall
ZEPu
À = Pd pm + X X X2= pa
which implies that our goal prove that pAiil S ad.
Now split the interval [(1 + m R²), the interval Pmn, into buckets Bo, B1, B2,... Bg where
B [2' + a)mA, 2 (1 + a)mA)
and = log
Ra [1+ammX
S log( (1+a))
R² ), and clearly we have Pr [x, u) > m(1+a) Pr E 2EX
=EX
B, Recall that Claim implies that for any i we can set m' 2' and get:
k=0
8 B
Pr x E Bi] 5 aE
2'm
Now can bound pA Pu using B;:
pd tiil
[ E Bi] 22t a1a zeX
Pr
i=0
+ 8²2
2 (1 a)md s 28 23--2k( 2k(1 aa)
2'm
i=0
which is upper bounded by À for 3 S a[Ita]"
Lemma C.4. (Lemma 6_ restated.) At each iteration é of Algorithm A only points belonging to and Pun are subjected to shrinking, given that < 1/2, s 10m
80m
Proof. The proof works by induction the iterations of the algorithm. Clearly, at = 0, before the algorithm begins, no points were subjected to shrinking so argument is vacuously correct.
Let t < T' and let æ E X denote a point that undergoes shrinking for the first time at iteration t, with X denoting the input the t-th time we apply Algorithm EL Our goal is to show that stems from a point in Punl Since x hasn't been shrunk prior to iteration t, then there exists some z; in the original input such that x A'x; for the linear transformation A' IT' -I to show that x; E Punl-
II. Our goal is
We assume is shrunk at iteration t. This shrinking happens since xI I'Iyi > R With S we have $ > 1ta then follows that x satisfies:
4
1 } +a)l = ) aak,
x Illly >
For the given parameters and c, observe that:
" "I > 1 (1 a)x 2m(1 + a)( + c)N + ck.
17

---

Recall that V denotes the subspace spanned by all eigenvectors of E Σ + N corresponding to eigenvalues the and that ||-V|| S ck. Now denote U the subspace spanned by all eigenvectors of E corresponding to eigenvalues I (+b + c)K. By Weyl's theorem it holds that
x' U 2 x= HyII oR 2 2m(1 + a: + c)
Thus we infer the existence of u E U (unit length vector in the direction 2y such that:
(x" 2m(1 + (1 + ccl..
But as U+ spanned by all cigenvalues 2 (v + c)イs of then it holds that #/2 (xT = (16 + c)x, so
(oTu)² 2m + a)
Σ uxT TEX
(2)
Now recall that x undergoes shrinking for the first time at iteration That means that there exists some 2; in the original input such that A'x; for the linear transformation A' = -I II' Moreover, by the induction hypothesis all points that were shrunk upto iteration are from Pmn- So for any point z E X Puml it holds that z My for the corresponding in the original input X. We get that Σ uo 2
Y
(x"n)²= Σ (n).
rex:
MEXTAU
We now apply Lemma
C to infer that
Σ
2 a) Σ ATTATu)2
1 Σ AT)
n
7
2n
yEX
seeing as a S 1/2. Plugging this into Equation (2) we
(o A uu)² (I u) m(1 n
1
Σ (T, VEX
which by definition proves that v; belongs to Puil-
Corollary C.5. (Corollary BM0 restated.) In all iterations of the algorithm it holds that E > namely, that the least eigenvalue of the second moment matrix of the input is 2 1.
Proof. Again, we prove this by induction of the iteration of Algorithm D. In fact, denoting X as the input of of Algorithm D at iteration f, then we argue that the least eigenvalue of the matrix Σ xxd is at least 1.
PM
Consider 0, prior to the execution of Algorithm e even once. Apply Lemma 3.S with u being
the direction of the least eigenvalue of Σ, and we get that Σ rx
(1 a.) 1. Observe
ZeX
that Algorithm D invokes Algorithm A on the input multiplied I-a factor, and so it holds that Σ
Tx T 2 1 for X", the very first input on which Algorithm D run.
Consider now any intermediate t, where assume that input satisfies
Σ zr 2 P.
1.
We can apply Lemma B.4 and Corollary 3.5 solely to the points in X \ Pusl and have that
Σ $allx"
Since Lemma B% asserts no point X Pran shrunk then we get
*EX")
that the required also holds at the invocation of the next iteration.
Claim C.6. (Claim 47 restated.) Let D be a distribution on gd with a finite second moment Σ. Consider random vector chosen by drawing x D and then multiplying y 121/2 Suppose that ||y|| < M1 a.s. that we also have a bound || [B( y) < M2. Fix a, 3 > 0. we draw
m max 2Mg 2(1+M)) } In( examples from D and compute the empirical second moment
Sa
matrix Σ, then w.p. 2 1 - 3 it holds that
ΣΣ 1/
1/2 T S
18

---

Proof. Denote our sample of drawn points as 22, Dm. Define vi Vi = Σ- 1/2,, so that
Elyay?] I. This transforms the problem to bounding: | /|/2 S where Sby 1 Σ yo
m
Now 11 I|2 ll 22 $ MP.
Next, define the random deviation Z of the estimator Ey from the true covariance matrix I:
m Zz z= - 1 Σ
where Z. = -waNT -
m
1=1
The random matrices Z; are independent, identically distributed, and centered. To apply Fact A.l we need to find a uniform bound R. for the summands, and we need to control the matrix variance statistic o². First, let us develop a uniform bound on the spectral norm of each summand. We can calculate that:
loca - I| _ (llvvv v II + 1111))
M +
|2:11
S
m
m
m
Second, we need bound the matrix variance statistic x² defined in A.
with x² = |[|ZZ]]
E
Z
||l- We need to determine the variance of each summand. By direct calculation:
1
1
1 m² Ely.v y.u! ylu.
E
[4,41
El(uvd - TNvv 1)²)= m2 (Eluev v.v.' T)
2
Then we have:
7
m Σ m² Eluyy yerl 111 S m
1 || El(/ wuee
M2 m
E E|Z,Z, S
We now invoke the matrix Bernstein incquality. Fact
ma²/2 1/
Pr[l 7112 > a) I 2d exp
M2 a(1 + MF)/3
which is upper bounded by B given that m 2 m(a, 3) = max { 22M, 2(1+M)
}
In (d/4/)))
30
D More Applications
D.1 Application: The Uniform Distribution Over Some Convex Ellipsoid
Fix a PSD matrix 0 < A < I. Consider the uniform distribution D over the surface of some convex
ellipsoid K. fa E Rdd x² A-'A-12
1}. Our goal in this section to argue that our algorithm able to approximate the 2nd moment matrix Ep. To that end, we want to determine the size of
subsample drawn from D, such that with probability at least 3: 1 S 1ll S a where En 1 A is the second moment of D.
To utilize Claim 2. it is necessary to compute the bounds M₁ and My. First, note that if x is drawn from the surface of IC then |/>:-1/221 2|| Vd|jy| for unit-length vector y, implying M1 v d.
Second, consider y = E.p 1/2 x and observe that:
ElysT T uy | EE 1/2 xx DDp
rx
2
1/2 de -EAA
1/2 x..
T A
A-' LITTTTTT T A/
(+) d E/A-
1/2 -
A 1/2 = d² A 1/2 2
(1=) dl
where inequality (+) follows from the fact that TJ 1 r = 1 for all and equality (**) follows since E[x,2?"1 1 A.
Hence we have || E|yn yarl S M2, and we conclude that D (O (-4. -n((4//))) a, B)- subsamplable.
19

---

Recall that we (1 -arr>)aappxximttte the 2nd- mod-moment matrix of the imput w.p. 1- Ç. Thus, we need the imput itself (1 approximation of the 2nd-moment matrix of the distribution. This means our algorithm requires
m(a, 9) (1(1))+
d
log(
Amin log log(log( ( 3/E)
?
for 1/2 and 3 0 log(l/Amss in order to return (1 ((r)) of the 2nd moment of the distribution w.p. 2 (
Plugging the m(a, () of we conclude that in order to return a (1 + -aproxxipiooniaationn of the 2nd moment of D w.p. 2 OEE) our sample complexity ought be
ml 21 log(1/Dmin)
d log(L///nn log(
log(1 (1 Ammin) = =0 -0
( 7VD
d3/2
m(),5) +0
While, for comparison, our baseline algorithm requires
(4 (lmm(,)5) = eY
d
-
ex
in order to return a (1=)(1)) aaprrxxiattoooooooooonn of the 2nd moment of the distribution w.p. 2 1-)
D.2 Examples of Heavy-Tailed Distributions
The above discussion holds for general distribution. Next we demonstrate our algorithms perfor- mance few heavy-tailed distributions. However, we also emphasize that many more applications are possible, since the subsamplability assumption is broad and encompasses a wide range of in- put distributions. For example, we further analyze datasets drawn from uniform distributions over ellipsoids and from Gaussian mixtures with stochastic outliers in Appendix D. and ?? respectively.
The Truncated Pareto Distribution. Throughout
the following distribution truncated Pareto distribution, denoted Ps. that is supported on the interval [1, B) for some B > (say B = 10), and whose PDF is x = Formally, its PDF is
5 B
x.
ff B
fxx
if
< 1 or B
so that f integrates to 1. Simple calculations show that def
E A~Po
[ =
B(B B that og
def
E |x A~Po
B² (m² and that E
[ = AmPP
(²(B-1)
B--1
15-1
We consider here two distributions composed of À ~ Pe and u En S The first is Au, namely a vector with direction distributed uniformly the unit sphere and magnitude distributed according to the Ps distribution; and the second is À o v, namely a (d + 1)-dimensional vector with first coordinate drawn from Ps. concatenated with uniformly chosen vector from the unit sphere on the remaining d coordinates.
The Au Distribution. Define the random variable x Xe, where v is uniformly distributed from unit sphere, and ~ Pa. Let 'D the distribution of x. Our goal is to argue that our algorithm is able to approximate the 2nd moment matrix Ed and outperforms the baseline(s). To that end, we want to determine the size m(a, 3) of a subsample drawn from so that with probability at least
1 3:
D| 1/2 "
Ep' 2 S
To utilize Claim
1 we compute Eo B[Au(Ac) = E(vo" o since B[wo-] = LT
It follows that D
1/2 x Vdd λa, we can bound ||v|| = M1 def Byd Lastly, it is necessary to compute M2. To this end, we evaluate the expectation:
B 1
E|2% 1/2 x ! 2i 2. E((
)2
2 xe(AD) (u(Au)
B²(B3-1)
20

---

9d2
BS
12 [E[A"] E(vo²* vv (+) 9d
BS
B2 - 1) )2 "P((4)) Elwe"))
25
Ba (B3 - -1)
25
(*))
9d
B5-1
5B - 1)
(3 - B5 - d S 2d1
25
where (x) follows from u²v = and (*x) holds since R[X*] 3B 3B' and E[ue"] J. Hence B6-1
we have Elyav weyl'll 2d M2. We now plug-in our values of B, Amin and M and infer this distribution is m(a, -)smmlalab for m (mmax _/ dB² } In(4/))). Plugging this into (I) we conclude that order to return a
a
of the 2nd moment of D w.p. (
our sample complexity ought to be
ml (Bd)
d
log( log( log( log log( (
Ô max d
dB²
dB²
d
m)+
7
7/2 ?
7
While, for comparison, our baseline algorithm requires
( d (d.m(7:5) = =0 δ
(0
-maxx (=
d Bed
72
in order return
of the 2nd moment of the distribution w.p. 2 1 1- (g).
The À o v Distribution. Consider the (d + dimeennsia distribution D where the first coordi- nate is drawn from the truncated Pareto distribution Ps and the remaining coordinates are drawn uniformly
[
D. Our goal in this section is to ar- gue that our algorithm is able to approximate the 2nd moment matrix Ep. To that end, we want determine the size m of subsample drawn from D, such that with probability least 1 B:
the unit sphere s#-1; Lee. x
[> " "'D'''
1ll2 S a.
First it is easy to see that the L2- norm of any x ~ D is at most B + 1. Next, we compute Ep:
X2
Au
2
0" 1
ED E
El
Au
un?
0 X ddu
It follows that the vector y
EnD 1/2
0
its norm is upper
bounded by Mi = V yd+ od++0"" og B2, So now we can evaluate the expectation:
og 222
LVVxx duu'
Elyy? Tyy El[ly|| "yy"
Bl
-2 22 + d)
-1
Vadu
[o6
[oo "EA*
+ do [[2
og
+
0
(o 2 E[A?] + djLa
0
(d+ 1)1s
dla+1 +
0
[[1]]
Ta
seeing og E[A"]
O(1) we can infer that M2 E[y"" yy = O(d).
We now plug-in our values of B, Amin and M and infer this distribution is m(a, 33-mmlallbe for m = O(mxx _ d+ In(//)). Plugging this into (II we conclude that in order to return a O(E) our sample complexity ought + (())) approxiaiioiii of the 2nd moment of D w.p. to be
m1) log Baj
d log (od( log(
log( log(Bd) = max
d B2
+
B
d
m(
72
21

---

The analysis suggests we can even set B O(Vd) and get a sample complexity of Ô g %%)
While, for comparison, our baseline algorithm requires
ò ((:mir())) Ō ( max
d B²+ 1)) uBg va Ô ক
73' 72
in order to return (1#0(7)) aaproxxmaaiiiiioooioon of the 2nd moment of the distribution w.p. 2 1-0(g)
22

---

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 abstract and introduction clearly state the main contributions of the paper, including the subsamplability assumption, the design of recursive zCDP algorithm for private second moment estimation, and its robustness to outliers.
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 motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper explicitly discusses key limitations, including the reliance on the subsamplability assumption and the requirement that the failure probability / be small relative a/ log(R).
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 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 (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might be used reliably provide closed captions for online lectures because fails to 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 ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play 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
23

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
The paper provides precise and complete statements for all theoretical results, with clearly stated assumptions such subsamplability parameters (m, a, ()) and bounds on input norms and eigenvalues. Full proofs are included either in the main text or the appendix, and all necessary external results (e.g.. matrix concentration inequalities) appropriately cited and referenced to support correctness. Guidelines:
Justification:
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 theo- rems.
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 short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This is theoretical paper that does not include empirical experiments. All claims are supported by formal definitions, theorems, and complete proofs, making experi- mental reproducibility not applicable.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, 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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions 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 new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a 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 re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
24

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case au- thors are 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., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This paper is entirely theoretical and does include empirical experiments or datasets. As such, no code or data is necessary to reproduce the main results, and this question is not applicable.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nlps.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.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 NeurIPS code and data submission guidelines (https:
//nips.com //nips.cc/publcce. hetpaliic/guide//ddeeeeeeee
oot.ssubbbisiooooooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is a theoretical work that does not involve empirical experiments, train- ing, or testing. Therefore, specifications such as data splits, hyperparameters, optimizers are not applicable.
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 appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
25

---

The paper does not include empirical experiments or statistical tests. All results are theoretical and supported by formal analysis. so reporting statistical significance or enror bars is not applicable.
Justification:
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, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars 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.)
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.
It is OK to report 1-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of eтrоrs is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots. The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper contains empirical experiments statistical evaluations; all results are theoretical and supported by formal analysis and proofs. Hence, reporting error bars statistical significance not applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics /ttt
Answer: [Yes]
Justification: The paper is theoretical in nature and does not involve human subjects, per- sonal data, deployment of systems. The research adheres to the NeurIPS Code of Ethics in full, including principles of transparency, rigor, and integrity.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
26

---

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: [NA]
This work is foundational and theoretical in nature, focusing on differential privacy and second moment estimation without reference to specific applications or de- ployments. As such, it does not have direct societal impact, either positive or negative, and broader impact considerations are not applicable in this context.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or 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 spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and 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 is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
This paper does not release any models, datasets, or tools that pose a risk of misuse. It presents purely theoretical results in differential privacy and statistical estimation, and therefore no safeguards are necessary or applicable.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
allow for controlled use of the model, for example by re-
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
27

---

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: The paper does not use any external assets such as datasets, codebases, or pretrained models. All results are derived from original theoretical work, and all prior research properly cited accordance with academic standards.
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 used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the pack- age should be provided. For popular datasets, paperswi thcode com datassts has curated licenses for some datasets. Their licensing guide can help determine the li-
cense 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.
If this information is not available online, the authors are encouraged to reach out to asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: The paper does not introduce or release any new datasets, code, models. It presents only theoretical contributions, so no asset documentation required.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/moodll 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 is 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. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve any crowdsourcing, user studies, or research with human subjects. It is purely theoretical and does require participant interaction or data collection from individuals.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
28

---

According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage 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:
The paper does not involve any research with human subjects participant data. It is purely theoretical, so IRB approval or equivalent review is not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. 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 NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
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 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 the research, declaration is not required.
Question:
Answer: [NA]
The paper does not involve the use of large language models (LLMs) in the development of core methods or theoretical results. Any use of L.MMs, any, was limited to writing assistance and does not impact the scientific rigor originality of the research.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
attep://heeurpppcc/c//ooeerrrrrs for what should or should not be described.
Please refer to our LLM
29


Reviews:
[{"review_id": "tYRo5h7Obs", "reviewer": "Reviewer_AvYQ", "summary": "This paper presents a novel differentially private algorithm for approximating the second-moment matrix of subsampleable datasets, even in the presence of outliers. By leveraging a recursive framework under zero-concentrated Differential Privacy, the authors achieve strong privacy-utility trade-offs and demonstrate robustness for heavy-tailed distributions and outlier-contaminated data. The theoretical contributions include formalizing subsamplability assumptions and providing concrete bounds for sample complexity and accuracy.", "questions": "1. In Theorem 3.1, what is the trade-off between privacy and estimation accuracy? Looks like the accuracy bound is only determined by $\\alpha$.\n2. Are there any empirical comparisons with existing methods to demonstrate the claimed advantages?", "limitations": "See 'Weakness' part.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The paper provides a comprehensive theoretical analysis, including formal proofs and clear assumptions, ensuring the robustness of the proposed algorithm.\n2. The method achieves strong utility guarantees under a weaker subsamplability assumption compared to traditional concentration bounds, making it applicable to a broader range of datasets, including those with heavy-tailed distributions or outliers.\n\nWeakness:\n1. The paper lacks experimental results to validate the theoretical claims, making it difficult to assess practical performance.\n2. The algorithm relies on multiple input parameters. How to tune these parameters and what is their impact on the estimation?", "was_revised": true, "final_justification": "I will keep my positive score for potential acceptance.", "rebuttal": "We thank the reviewers for their thoughtful feedback. We are pleased that our work is recognized as technically rigorous and novel, and we appreciate the opportunity to clarify and address the concerns raised.\n\n1. On the subsamplability parameter:\nThe parameter m is unknown in general, as it encapsulates a property of the input distribution. However, if the data is known to come from a specific distribution (e.g., heavy tailed distributions), the value of m can often be computed analytically — see Section 4.1 and Appendix D for such examples. In the general case, while there is no universally optimal way to estimate m under privacy, one can still privately run the algorithm for multiple candidate values of m, since our method is differentially private for any choice of m. This pragmatic approach allows post-hoc validation of outputs and circumvents the need for stringent concentration bounds.Note that even \"classical\" results, such as estimating $\\Sigma$ under the promise of data sampled from a Gaussian, make assumptions on the nature of the input and do not concern themselves with verifying whether such an assumption holds or not. The only difference is that we use a slightly less common assumption. But, as it turns out, our subsamplability assumption makes it possible to deal with both cases at the same time: (1) data drawn from a distribution and (2) data with a small fraction (roughly \\beta/m) of outliers. Lastly, we ourselves tried to address the \"minimality\" of subsamplability in lines 25-29 in the introduction.\n\n2. On the lack of experiments:\nOur work is entirely theoretical, and all claims are rigorously proven. Empirical experiments in such settings merely illustrate that the mathematical analysis holds — a fact already established through our theorems. In this light, we believe that including synthetic experiments would not significantly enhance the contribution, although we agree that future applied extensions could and should incorporate them.\n\n\nSpecific comments for Reviewer #1:\nOn baselines:\nOur comparison baseline provides only an \\alpha-approximation of the second-moment matrix. This sets an initial threshold, whereas our algorithm achieves a \\gamma-approximation for arbitrarily small \\gamma, subject to sample complexity. Thus, the comparison is illustrative of a qualitative improvement in precision."}, {"review_id": "uwg3zmNqys", "reviewer": "Reviewer_dJaK", "summary": "This paper presents a differentially private algorithm for estimating the 2nd-moment matrix (covariance matrix) under the assumption of $(m,\\alpha, \\beta)$-subsamplability. The authors propose a recursive mechanism that iteratively reduces the range of the data while preserving spectral structure and satisfying zCDP. The proposed approach is robust to outliers and overcomes limitations in prior DP methods.", "questions": "Please see the weaknesses.", "limitations": "Please see the weaknesses.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe proposed algorithm and its analysis are both technically rigorous and innovative.\n\nWeaknesses:\n\n1. The subsamplability assumption, although less stringent than standard matrix concentration bounds, remains somewhat probabilistic and non-constructive. It is unclear how one might verify or estimate whether a dataset satisfies this condition, especially under privacy constraints.\n2. The paper lacks experimental results, which limits its practical validation. Simulations on synthetic or real-world datasets (e.g., robustness to outliers, improved sample complexity) and comparisons with author-mentioned methods such as Nissim et al.(2007), Kamath et al.  (2019), Brown et al. (2023) would strengthen the empirical relevance.\n3. The recursive algorithm involves multiple spectral decompositions and tail-point truncation, which could be expensive in high dimensions.\n4. It seems that the error bound analysis critically relies on the parameters $R$ and $\\lambda_{\\rm min}$, but the procedure for estimating these quantities in a privacy-preserving manner is only briefly mentioned. I am curious about how the $R$ and $\\lambda_{\\rm min}$ affect the main utility error bound.\n5. In Section 4, how sensitive is the robustness guarantee to slight violations of the $\\Sigma_{\\rm out} \\preceq O(1/\\eta)\\Sigma_{\\rm D}$ condition in line 337?\n6. In Algorithm 1, the iteration bound is defined as $T = \\log_{7/3}\\left(\\frac{\\frac{1}{1-\\alpha}R^2}{640m}\\right)$, which takes an unusual logarithmic base value $7/3$. Could the authors clarify the rationale behind choosing this specific base?\n7. How should the covering radius $R$ be determined in practical scenarios where the dataset may contain outliers? Since the input may not be bounded.\n8. The title of ``....\\emph{Any} Subsamplable Input\" may be overly broad, as the efficiency of the proposed method relies on the subsamplability assumption. Additionally, the algorithm uses uniform random subsampling. It would be useful to discuss whether the results extend to other subsampling schemes, such as Poisson or leverage-score based sampling.\n9. The manuscript is not well-structured, and the content lacks logic. For example, the introduction presents subsamplability assumption in a way that is difficult to follow without prior knowledge. Further, Sections 3.3 - 3.4 would benefit from additional remarks or intuition around the theoretical results and the recursive analysis.", "was_revised": true, "final_justification": "Nice theoretical work on the private estimation problem, although there are no numerical results.", "rebuttal": "We thank the reviewers for their thoughtful feedback. We are pleased that our work is recognized as technically rigorous and novel, and we appreciate the opportunity to clarify and address the concerns raised.\n\n1. On the subsamplability parameter:\nThe parameter m is unknown in general, as it encapsulates a property of the input distribution. However, if the data is known to come from a specific distribution (e.g., heavy tailed distributions), the value of m can often be computed analytically — see Section 4.1 and Appendix D for such examples. In the general case, while there is no universally optimal way to estimate m under privacy, one can still privately run the algorithm for multiple candidate values of m, since our method is differentially private for any choice of m. This pragmatic approach allows post-hoc validation of outputs and circumvents the need for stringent concentration bounds.Note that even \"classical\" results, such as estimating $\\Sigma$ under the promise of data sampled from a Gaussian, make assumptions on the nature of the input and do not concern themselves with verifying whether such an assumption holds or not. The only difference is that we use a slightly less common assumption. But, as it turns out, our subsamplability assumption makes it possible to deal with both cases at the same time: (1) data drawn from a distribution and (2) data with a small fraction (roughly \\beta/m) of outliers. Lastly, we ourselves tried to address the \"minimality\" of subsamplability in lines 25-29 in the introduction.\n\n2. On the lack of experiments:\nOur work is entirely theoretical, and all claims are rigorously proven. Empirical experiments in such settings merely illustrate that the mathematical analysis holds — a fact already established through our theorems. In this light, we believe that including synthetic experiments would not significantly enhance the contribution, although we agree that future applied extensions could and should incorporate them.\n\n\nSpecific comments for Reviewer #2:\n\n1. On computational complexity:\nWe agree that the algorithm might involve expensive spectral computations. However, similar limitations appear in prior work such as Kamath et al. (2019), which also refrain from approximating these steps. Replacing the decompositions with approximations is an interesting future direction, but outside the scope of our study, as it unclear how sensitive these approximation algorithms to the presence/omittion of one datapoint.\n\n2. On sensitivity to R and \\lambda_min:\nThe bounds depend only logarithmically on these parameters (and thus polynomially in their natural representation). Thus, while important, they have limited effect on the overall accuracy guarantees.\n\n3. On “slight violations” of the subsamplability condition:\nWe would appreciate clarification on what is meant here. Obviously, if a requirement for our algorithm doesn't hold, then its guarantee is vacuous.  \n\n4. On the iteration bound and log base:\nThe bound T=O(log(R/m)) is chosen for analytical tractability (as part of our preference to set parameters without using asymptotic notation). The base does not affect the asymptotic behavior; the important point is that the number of iterations depends logarithmically on the ratio R/m.\n\n5. On estimating R:\nIn practice, R can be chosen to include most of the data, using private range estimation techniques such as those in Nissim, Stemmer, and Vadhan (2016) or Nissim and Stemmer (2018).\n\n6. On alternative sampling schemes:\nSampling strategies like leverage-score sampling depend intricately on the data and are difficult to make private in a general-purpose way. Our result assumes uniform sampling. The term “any” in the title refers to input datasets satisfying the subsamplability assumption, not arbitrary sampling schemes - and as said earlier - these can be either inputs drawn from a distribution or some well-behaved input with a faction of outliers.\n\n7. On manuscript structure:\nWe thank the reviewer and welcome specific constructive suggestions to improve the clarity of Sections 3.3–3.4 and the introduction. We will incorporate more intuitive explanations and structural improvements in the revision. We just ask that the presentation suggestions will be agreed upon by all reviewers."}, {"review_id": "4PiJI6VtOP", "reviewer": "Reviewer_GJ5K", "summary": "Privately estimating statistics suchs as means and covariance matrices of a set of vectors has been a subject of intense study in the last 5-10 years. Good approximation is only possible under conditions on data, and various such conditions have been explored, often assuming that data is sampled from some \"nice\" distribution. This paper considers a new such condition that allows approximating the second moment of a distribution, namely subsamplability, which roughly means that a sample of the data has approximately the same spectral structure as the whole dataset with high probability. For datasets satisfying this condition, it is shown that a good approximation to the second moment matrix can be calculated with zero-concentrated differential privacy. This includes datasets with outliers, something not sufficiently captured by previous conditions.", "questions": "* Maybe a newbie question, but why don't you also consider covariance estimation? Is it because the results are weaker in that setting? Surely SOME result about covariance estimation must follow from your work\n\n* Is there a private way to tell if the subsampling condition holds for given m, alpha and beta?\n\n* In algorithm 2 the recursive call uses the same privacy parameter rho, which is counterintuitive since one would usually need to invoke composition. Can you comment on this?\n\n* In Theorem 3.3 it sounds like large n is needed for privacy (property 1). If that is the case, how may one ensure that n is large enough for privacy?", "limitations": "The theoretical limitations are well discussed. I feel that the paper could have also discussed any limitations that may arise when trying to use this kind of method in practice.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is a novel contribution to a well-studied area that is relevant to machine learning. Its relation to other results in the literature is well explained. Even though it is not in my area of expertise, I was able to understand the key ideas.\n\nThe work is theoretical with no empirical work, which can be seen as a weakness. The algorithm also needs to know the parameters for which the subsampling condition holds, and it is not obvious how to find such parameters in a private way.", "was_revised": true, "final_justification": "The rebuttal confirms my assessment of the paper as a good theoretical contribution to the area.", "rebuttal": "We thank the reviewers for their thoughtful feedback. We are pleased that our work is recognized as technically rigorous and novel, and we appreciate the opportunity to clarify and address the concerns raised.\n\n1. On the subsamplability parameter: The parameter m is unknown in general, as it encapsulates a property of the input distribution. However, if the data is known to come from a specific distribution (e.g., heavy tailed distributions), the value of m can often be computed analytically — see Section 4.1 and Appendix D for such examples. In the general case, while there is no universally optimal way to estimate m under privacy, one can still privately run the algorithm for multiple candidate values of m, since our method is differentially private for any choice of m. This pragmatic approach allows post-hoc validation of outputs and circumvents the need for stringent concentration bounds.\nNote that even \"classical\" results, such as estimating under the promise of data sampled from a Gaussian, make assumptions on the nature of the input and do not concern themselves with verifying whether such an assumption holds or not. The only difference is that we use a slightly less common assumption. But, as it turns out, our subsamplability assumption makes it possible to deal with both cases at the same time: (1) data drawn from a distribution and (2) data with a small fraction (roughly \\beta/m) of outliers. Lastly, we ourselves tried to address the \"minimality\" of subsamplability in lines 25-29 in the introduction.\n\n2. On the lack of experiments: Our work is entirely theoretical, and all claims are rigorously proven. Empirical experiments in such settings merely illustrate that the mathematical analysis holds — a fact already established through our theorems. In this light, we believe that including synthetic experiments would not significantly enhance the contribution, although we agree that future applied extensions could and should incorporate them.\n\n\nSpecific comments for Reviewer #3:\n1. On covariance estimation:\nTo estimate the covariance matrix, one typically subtracts the outer product of the mean vector. While this can be done privately using standard DP mean estimation algorithms, it incurs additional noise, hence degrading utility. For this rather technical reason, we focus on the second moment.\n\n2. On privacy composition in recursion:\nIndeed, each recursive call uses the same target privacy parameter \\rho, but we ensure that each call only consumes \\rho/T-zCDP. By composition, the total privacy cost sums to \\rho, preserving the global privacy budget.\n\n3. On privacy and sample size:\nWe appreciate this clarification. Privacy is preserved regardless of sample size. We agree the current wording in Theorem 3.3 may be misinterpreted, and we will revise it to: \"Algorithm 1 preserves \\rho-zCDP, and if n \\geq ...\""}]

Author rebuttal:

Meta-review: The paper provides a differentially private algorithm for approximating a dataset's second moment matrix. When the data takes a certain ("subsamplable") form, they provide formal utility guarantees.

The reviewers generally appreciated the submission's algorithmic novelty and the basic conceptual idea of subsamplability, and all three recommended acceptance. However, all three reviewers also asked for clarifications regarding the "subsamplability" parameter and its effect on privacy (if I understand correctly, the assumption is only necessary for utility, not privacy), as well as the role of other input parameters; the authors should add discussion of those points to the final version.
Decision: Accept (poster)