Non-Asymptotic Analysis Of Data Augmentation For Precision Matrix Estimation
Authors: Lucas Morisset
Adrien Hardy
Alain Oliviero Durmus
Venue: NeurIPS 2025 spotlight ()
Keywords: Data Augmentation
Precision Matrix
High Dimensional Statistics
Random Matrix Theory
Primary area: theory
TL;DR: We introduce a data-centric estimator of the squared error of usual precision matrix estimates, both in the non-augmented case and the augmented case. Furthermore, we give non-asymptotic guarantees on our estimate.

Abstract: This paper addresses the problem of inverse covariance (also known as precision matrix) estimation in high-dimensional settings. Specifically, we focus on two classes of estimators: linear shrinkage estimators with a target proportional to the identity matrix, and estimators derived from data augmentation (DA). Here, DA refers to the common practice of enriching a dataset with artificial samples—typically generated via a generative model or through random transformations of the original data—prior to model fitting.
For both classes of estimators, we derive estimators and provide concentration bounds for their quadratic error. This allows for both method comparison and hyperparameter tuning, such as selecting the optimal proportion of artificial samples.
On the technical side, our analysis relies on tools from random matrix theory. We introduce a novel deterministic equivalent for generalized resolvent matrices, accommodating dependent samples with specific structure. We support our theoretical results with numerical experiments.

Non-Asymptotic Analysis Of Data Augmentation For Precision Matrix Estimation
Lucas Morisset Qube Research and Technologies & École Polytechnique
Adrien Hardy Qube Research and Technologies
Alain Durmus
École Polytechnique
Abstract
This paper addresses the problem of inverse covariance (also known as precision ma- trix) estimation high-dimensional settings. Specifically, we focus on two classes of estimators: linear shrinkage estimators with a target proportional to the identity matrix, and estimators derived from data augmentation (DA). Here, DA refers to the common practice of enriching dataset with artificial samples- typicallly generated via a generative model or through random transformations of the original data-prior to model fitting. For both classes of estimators, we derive estimators and provide concentration bounds for their quadratic error. This allows for both method comparison and hyperparameter tuning, such selecting the optimal proportion of artificial samples. On the technical side, our analysis relies on tools from random matrix theory. We introduce novel deterministic equivalent for generalized resolvent matrices, accommodating dependent samples with specific structure. We support our theoretical results with numerical experiments.
Introduction
In this work, we consider the problem of estimating the inverse covariance matrix, also known as the precision matrix, of a random vector from i.i.d. zero-mean samples [* [X]] E IRdx" with true covariance Σx = []] Here, n denotes the number of samples, and is the dimensionality of the data. This problem has important applications in statistics and signal processing (see, e.g..
[FLL16, Car88J).
We are particularly interested in the high-dimensional regimes, where the data dimension d and the number of samples are of the same order. In this setting, the sample covariance matrix Cx n -xx may be non-invertible poorly-conditionned. As result, using its inverse as an estimator can lead to numerical instability and high estimation error. To address this issue, shrinkage estimators for the covariance matrix have been proposed as regularization method [BGP16, LW04, SSO5, LSW03], which involve adding a target matrix to Cx. The simplest and most common choice for the target is multiple of the identity matrix, which effectively shifts the eigenvalues above a threshold À > improving stability. In addition to linear shrinkage and even importantly, this paper also explores the use of data augmentation (DA) as alternative strategy.
Data augmentation (DA) involves increasing the size of a dataset by incorporating additional artificial samples. The underlying intuition that, in many cases, possible artificially replicate the
"Correspondence to: lucas. tensmmorisseetpllyecciiige
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

data distribution, thereby reducing the variance of the model while maintaining relatively low bias. Due to its effectiveness in low-data regimes and its ability mitigate overfitting, DA has become increasingly popular and is now widely used in machine learning and data science [SK GSK 18, CKNH20, 20)+ finds applications across a variety of fields, including computer vision [SK19], natural language processing [FGW+21] and neuroscience [LLM20]..
Two main types of data augmentation (DA) can be distinguished. The first Transformative Data Augmentation (TDA), where original samples are transformed through a random mapping-foo example, by adding Gaussian noise or applying random mask. The second is Generative Data Augmentation (GDA), in which artificial samples are generated using a generative model and added the training dataset. In the case of GDA, we assume that the generative model has been pre-trained on the original samples X.
In both cases, the artificial samples are dependent on the original data. Although TDA and GDA differ conceptually, our framework and results encompass both approaches. More precisely, we consider the inverse of the empirical covariance matrix associated with the augmented dataset
X iX,,..., Xny GI..... Gm] as estimator of Σx² where each G, Rd is artificial sample. That is, we study the estimator which consists of the inverse of (n + regularization parameter À > 0.
X + + for some m) m))
Although there is extensive empirical evidence that DA improves the performance of machine learning models, the theoretical literature on the subject remains relatively limited. In this work, our goal to establish performance guarantees that enable meaningful comparisons between different DA strategies and, as a by-product, allow for the optimization of certain associated hyperparameters. To this end, we leverage tools from random matrix theory construct estimators of the quadratic error for DA-based estimators, which, under mild assumptions, satisfy exponential concentration inequalities. Our analysis can also adapted-and fact simplifies to cover linear shrinkage estimators with target proportional to the identity matrix. To summarize, our main contributions are as follows:
In Section 2, we focus on the estimator of Ex given by the inverse of linear shrinkage estimator, where the shrinkage target is a scalar multiple the identity matrix. Specifically, we derive estimators for the quadratic error and show that they satisfy non-asymptotic exponential concentration bounds. Our results hold under standard assumptions from random matrix concentration property for X.
the Lipschitz
In Section 3, extend our analysis data-augmented estimators under appropriate conditions on the DA procedure, which we show hold true for common DA.
Finally, for both scenarios, we show how our estimators for the quadratic error can be used to compare and tune their corresponding methods with respect to key hyper-parameters such as the nomber of additional samples m for DA. These conclusions are illustrated numerically on real data in Section 4.
Notation and convention. Motivated by high-dimensional statistics, we will consider that n, d and m are variables, yet for notation simplicity, we will most often not reflect dependancies in n. m or in our notations. Additionally, we write, x S y (resp x 2 y) whenever x I Cy (resp x 2 Cy) for a universal constant C' that neither depends on the model's parameters, nor on the parameters n, m, d. For any matrix E Rd we denoted by CH = -H the corresponding covariance matrix. For any symmetric matrix Σ E Rdddd, we denote by >a(E)) .... < X (Σ) its eigenvalues. The Frobenius and operator norms are denoted II- and Il-llop respectively. Random variables will be referred to by capital letters X, G. Z, and we will denote by Ber(p), N(m, Σ) and (E) the Bernoulli distribution of parameter p E [0, 1). the Gaussian distribution mean m E Rd and covariance Σ dxd, and the uniform distribution over a discrete set E. Furthermore, we introduce the p- Wasserstein metric, (P(11, 12)= = inf inf [| vll dy(x, v) for any distributions v and Me dx and where y E 12) if and only if for any E Rd (R E) 2) and (E, pdxn)= 12 (E).

---

1.1
Related work
Data Augmentation. Numerous empirical studies have demonstrated the benefits of using DA when training machine learning models [MM22b, MMN22, vDM01J. Among popular DA schemes, mention Autmnntment [CZM* 19, LKK 19, ZWZZ20), which aims to learn an optimal augmentation policy from data by combining a set of sub-policies. In addition, significant works have also explored the incorporation of knowledge about the distribution invariances directly into the training procedures [CDL20].
However, DA does not always lead to systematic improvement in test error [KIB HGK20, CL25], and very little theoretical understanding backs-up the improvement observed empirically. An early analysis by [Bis95] showed that adding Gaussian noise to data points is equivalent to applying Tikhonov regularization. Building on this seminal work-an given the practical importance of DA for machine learning practitioners few studies have sought to develop theoretical understanding of its effects.
In the context of kernel methods, [DGR + 19] showed that DA can be approximated by a combination of first-order feature averaging and second-order variance regularization. Similarly, in the context of linear and logistic regressions, [LKDM22] revealed that DA induces implicit spectral regularization in two ways: first, by adjusting the relative proportions of the eigenvalues of the data covariance matrix in training-dependent way; and second, by uniformly shifting the entire spectrum via ridge regression.
Taking a different perspective, [WZVR20] consider a family of linear transformations and study their effects on the ridge estimator in an over-parametrized linear regression setting. First, they show that transformations that preserve the labels of the data can improve estimation by increasing the span of the training data. Second, they show that transformations that mix data can improve estimation by playing regularization effect. They proposed an augmentation scheme that searches over the linear span of set of transformations, aiming to maximize model uncertainty on the transformed data.
Recently, studies have shown that even small amounts of artificial data can lead to model collapse [SSZ*24, 24, DFK24, DFSK25), phenomenon where the performance of generative models deteriorates when recursively trained on synthetic data.
Precision Matrix Estimation. In high- nigh-diiensional settings where the number of covariates is comparable to or exceeds the number of
covariance estimation methods often suffer from poor conditioning, making the estimation of the precision matrix particularly challenging. To address this, [LW04] introduced linear shrinkage methods, which involve forming convex combination xCx + (1 )T of the sample covariance matrix Cx with shrinkage target T, where w E [0. 1]. [LW03, LW04] derived the optimal value of w that minimizes the mean squared error between the shrinkage estimator and the true covariance matrix Σx.
Extending this work, [LW12, LW22, BGBP23] proposed and analyzed non-linear shrinkage estima- tors of the form U UDDDUT where Cx = UDU is the eigenvalue decomposition of Cx and f is suitably chosen function applied to the eigenvalues.
Fewer works have addressed shrinkage methods specifically designed for precision matrix estimation.
Among them, [BGP16] studied estimators of the form (1 - x)Cx + III, where II is a deterministic shrinkage target, and derived the optimal shrinkage intensity w. In addition, [WPTZ15] considered estimators of the form Ωx ()) = ((1 W)Cx + w Ia) and derived the optimal w to minimize the objective function ||[x ( Ex Tall in the high-dimensional regime where d/n + 7 > 0.
An independent line of research, motivated by Gaussian graphical models [YL07], has focused on estimating sparse precision matrices. In particular, [MH12, CLL11] introduced the Graphical Lasso method, which has become widely used for this purpose.
Random Matrix Theory. Since the pioneering work of [Wis28], numerous studies have investigated the behavior of the eigenvalues and eigenvectors of the sample covariance matrix Cx in the high- dimensional regime where d/ n + 7 > 0: see, for example, [MP67, Si189]. More recently, [AEK* 14] first demonstrated that, in the isotropic setting, the resolvent (Cx + A Aaa converges weakly to a scalar multiple of the identity matrix as d/'n - 7 > 0. This was later extended to the anisotropic case by [KY17], who established so-called deterministic equivalent results for (Cx + AI)) These results have been further generalized to settings with more complex dependency structures. In
3

---

particular, [Cho22, LC23] showed that deterministic equivalents continue to hold under weaker assumptions.
Building on these foundational results, several studies have established connections between classical random matrix phetry-particularly the results of [MP67, -in89] the behavior of modern machine learning models. In particular, random matrix theory has proven in- strumental in explaining the double-descent phenomenon, initially observed in linear models [HMRT22, DLM20, MVSS20, BLLT20, DKT2IJ, and later extended to certain classes of shallow models, such as random feature models [MM22a, LCM21, GLK+21, DRBK20J. Complementing these works, [SDCL24, SCDL24] provided a sharp asymptotic characterization of the test error in deep random feature models-repreese represeniin significant step toward understanding generaliza- tion in deeper architectures. Finally, [ITL 24] leveraged random matrix theory to develop precise performance estimates for multi-task learning across a variety of statistical models.
2 Inverse covariance estimation using shrinkage method
We consider here the following estimator Rx (A) of the precision matrix, and its squared error:
Rx(A) (Cx + + Ex(A) (1A))=2(1x(0) (1xx
Here, À > O is a hyperparameter that controls the strength of the regularization. Note that this estimator is not per shrinkage estimator, but it is the inverse of a shrinkage estimator of the covariance matrix. In addition, Rx (A( is also referred to as the diagonal loading estimator in the signal processing community; see e.g., [LSW03]. Furthermore, note that our result can be readily applied to an estimators of the form ((1 - a) ao La) = (1-a) (1-a)- + oz la / a)) a))-
for any RR+, and a E (0, 1).
This estimator does not rely on any data augmentation procedure. However, as we will see, applying data augmentation leads to results that are closely related this regularization approach. This is not surprising, as it is relatively well known that data augmentation induces an implicit regularization effect [Bis95, LKDM22J. For this reason, present this simple case in detail as preliminary step, which will allow us to transition more smoothly to the data-augmented case in Section 3. As already emphasized in the introduction, main goal is to derive a data-centric estimate for the error Ex Ex(A). To this end, we introduce two assumptions.
HI (Concentration of X). The random matrix X E Rdd writes 1 where Z E Bddx has independant sub-Gaussian entries with parameter x-
HI is standard in the random matrix theory literature, yet one can employ a more general framework, as in [Cho22, 2T, LC18] by introducing the notion of Lipschitz concentration (H6), we detail this generalization throughout the appendix and stick to this simpler framework in the main body for the sake of simplicity. In addition, assumption on the entries of X, albeit with weaker- ttpically done in [LP11]. We leave a detailed investigation of this extension for future work.
expect results to remain valid under fiite-moment
cnmomial-cooccntrattono bounds, as
We next suppose that with high probability the leave one-out covariance matrix Ox is well- conditionned. This matrix is defined for any X E Rdd= as the covariance matrix
Ox = Cx-
x = X,, Xo..., x
More formally, for any 17 define
Ag = [X gdxn Aa(C()) 2
n n)
(2)
H2 (Model conditionning). There exist 1) > 0 and cx > 0 such that P (X & Ag) S exe.
We highlight Appendix that H2 holds provided HI holds and 2 Kx + 1j 7 1) for some constant Kx depending only ox.

---

We are now ready to present our estimator for Ex( and to state its concentration properties. The estimator is given by:
Ex(A) = 1 ir (Rx(())) 2(1 - dd/n) tr (Rx (0)) A., (X) + 2tr (A)(
Ab(A) + txxx²x (3)
A
b(A) == I- d/n + (A/n) tr (Rx(A))
Note that for fixed vj > Ex(2) is computable from the data X only, up an additive constant. Theorem 1. Assume HI and H2. Then, holds for all 2 0 and À > 0,
P -(Ex(A)-E(X))
- ex(2) 2 2 &
for universal constant and where
Ax(A) C103 VdIxxil + Cze A3nd
1
Here C1 C2 are explicit polynomial functions of [E 7a(Ex), (n X) and ex see (B).
From practical standpoint, the previous result can be used to optimize the hyperparameter À by minimizing the function À + (A), using εx proxy. Moreover, it is worth noting that the derivative of X - &x depends only the data matrix X, and not the true covariance Σx. As result, εx can be minimized using a gradient descent scheme, provided that the parameter rj satisfies H2. We illustrate these applications on real data in Section 4.
Although the full proof of Theorem is deferred Appendix B, provide here sketch of its derivation. We highlight the main ideas and technical challenges, and note that the proof of our result on estimation using data augmentation, Theorem 2, shares several of these steps.
First, expanding the Frobenius norm in (1), we have,
(A( (1/d) tr (Rx (A)3) (2/d) ir (EX (x())) (2)))+++ (1/d) (1/x))((X)))))
The first term in the previous expansion directly computable from the data matrix X, while the last term is constant with respect to À and can be ignored when the goal is to optimize X. Therefore, suffices to establish a deterministic equivalent for Rx(A) and thus of tr (Vxx² Rx())). To this end, we rely the following result, whose proof is postponed appendix B.
Proposition 1. Assume Hl and H2. Let B e gdxd be deterministic matrix, then have for all O,
P (1 (B (X) [Rx (A) (x)]3) 21) - exp (-c(n++++ o
Furthermore, defining fa(b) 1 tr (Ex(Ex/X + -1) and = 6* (A) as the unique fixed point of fx on [1, 20), we have
Ciox v Ex 3
| [[x(())- - R5 (2) 1a, (x))
+ C2e -x
nd (Ex (17 2)8
Rx(2)= = Ex -2xx + +Ala
where C1, C2 are defined as in Theorem I.
Proposition shows that (x( concentrates around R (A), which we refer to as a deterministic equivalent of Rx (A). Our result extends that of [Cho22] by covering the case of vanishing regular- ization (A - 0). This extension constitutes the main technical innovation required for the proof of Theorem 1.
5

---

We can now leverage the deterministic equivalent of Proposition 1 to rewrite (1/d) tr (Ex' Rx(2)). Informally, holds with high probability that
7) LA, (X)
1 7 tr (2xx Rx())) d tr
Σx
xx
+Ala
(*()))
[Rx ( (01) AA, (X)
( (A) tr [Rx (2)) (a)) 1A, (X)
tr
Adb (0)
where the last equality follows from the identity A -B- A BB A AJB Finally, using Proposition again, and that 60( (1 d/n) 11 is the fixed point of So : + bd/n, we get
1 (xx Rx (A)
d/n (Rx(0) (X)
Adb (Rx()))
(4)
Ad
Finally, by the definition of b* (A) and through straightforward algebraic manipulations, we obtain ur n
6a (a tr ( =1 { - ( (1)
n
Therefore, applying Proposition
again yields
6*()) = 1 (d/n) + (A/n) tr Rx (A) 1- (d/n) (Vm b(A),
Plugging this estimate in (4), we identify Ex (A) (3) and it completes the proof of Theorem 1. The formal proof is postponed to Appendix in the supplement.
3 Precision matrix estimation using generic data augmentation
In this section, we investigate a data augmentation strategy to improve the estimation of the inverse covariance matrix of X. Specifically, we consider an additional set of artificial samples G [G,,... Gm], which may depend on X and are typically generated using either TDA or GDA techniques; see Table I. More precisely, given X, we assume that G is drawn from known regular conditional distribution (X, A) + (x(A), meaning that for any measurable set E C IRd we have (G, E X) = ux (E). Then, we consider the following new estimator and define its quadratic егrоr as:
Raug (A) = ((n + m) (XxT + GG +
(Aug(A) (1/d)Il -
In the following, in addition to HI and H2, which pertain to X, we introduce further assumptions on G. These are organized into three categories: a concentration assumption on G, smoothness assumption on Ux, and a stability assumption on VX-
HB (Concentration of G). The random matrix G E Raxm has i.idd centered columns conditionally on X, i.e., X for any {1....,m,) m). In addition,
(i) The columns of G are sub-Gaussian, with parameter OG
(ii) There exist < 3 < 1, and Ag Rdxx - gd such that almost surely
E[GG X] BCC Aa(X).
and (X) is positive definite matrix satisfying for some 0, K- S Aa(AG(X)) s (AGG S k almost surely on A, defined in (2).
Part (1) of H3 concentration assumption on G conditional on X, similar HI.
Regarding the second part (ii), can be interpreted as a structural assumption. In most cases, the parameters 3 and Ag can be directly derived from the definition of the augmentation process. Table I provides values 3 and AG for a range of common DA schemes. As an example, consider the case where G is drawn from a TDA procedure of the form Gj- = g(Xr,, Zj). where 1m are i.i.d. and 1 L-Lipschitz concentrated (Definition 1), and (1 are i.i.d, with 4 Unif( [1.'.- r2)), also

---

Augmentation Name
Description
Ag
8
GDA
Fixed Gaussian GDA
Gj N(O,A)
0
Gaussian mixture GDA
G3 E w;N(Hu,A.)
Σ wiAAi + mmu!
0
Fixed Gaussian TDA
A p(1 p) diag(Cx) X1, 7, (1 7,) N(O, p( p) diag(Cx) p) 2
X1, + 43 4 N(O,
1
Random mask TDA
X1, 2n 2, Ber(p)
0
Salt & Pepper TDA
p
Table I: Various augmentation procedures and corresponding B and Ag. We used the notation
1 ~ ,n,i(( For more details, we refer to Appendix A.
assume that for any I E IRd, Ez [z(21, = g for some 3(4) 2 O. Then, is straightforward to verify that H3-(ii) is satisfied with | +- -/(e) and A(X) + (X) where
( (x) 1 Σ [1, (OXx, (0(Z), X,) 3 x;)
x.
(5)
Table I below, shows the value of 8 and Ac(X) for variety of common data-augmentation scheme.
Our second assumption on G suppose that X ++ vx and X + AG(X) are Lipschitz. More precisely:
H4 (Smoothness of the artificial distribution). There exist Lg and LA such that for any
X, Y E Rdxa, and m. E N,
Wi (u " S VmLa - Y|FFF ||Aa(X) - Ac(Y) S Y
Note that the DA examples Table I all satisfy this assumption provided X has compact support. Otherwise, we believe that results are robust enough to hold only when Ag and X + vx are locally Lipschitz, albeit with slightly weaker convergence guarantees.
H5 (Stability of the artificial distribution). (i) The map + vx is invariant under permutation of the columns of X, i.e., for any permutation {1..... n} + (1...., nJ. vx ix, where X = (X, X,(0l
(ii) Furthermore, we assume that there exists K 2 0, such that for any m E N.
(1 8m
1/
60m
S /mK,
a.s.
Typically, should remain bounded with respect both n and d. H5 can be interpreted as a condition ensuring that the data augmentation procedure used to generate the {G specific individual sample. met by various data augmentation procedures found in the literature. We provide in our next result condition on vx and ux- only, which implies H5-(ii). It proof is postponed to Appendix A.
pm does not depend on any
Proposition Suppose that W2(vx,Vxx S Then, H5-(ii) holds.
Remark 1. a non-trivial example of DA scheme that satisfies H4 and H5, let consider the Random mask TDA, described in Table 1. We further illustrate our assumptions on other DA strategies in Appendix A. Let X. Y pd and consider the coupling of vx and ny. defined as for Ber(p)
j E (1,...,,,, m, G; Z, @ X1,, G² Z 3 YI, where I ~ Unif((1,... Zz ((1,...,,,) ,n]), and O the elementvise multiplication. Then we have by the Cauchy-Schie Schhaar inequality,
Wi(v 8cm (0m))) VmW2lvx. vX) Vm B E II -Y,) Z12 VmpliX Y
Furthermore, from Table 1, we know that (X) 1-e diag((xx therefore is locally-Lipschte
only. However, assuming that X bounded, we can always find another function ÅG satisfying H 3-(ii) and which is Lipschitz.
We show through similar computations and using Proposition 2 that H5 is satisfied
W2xux, Ux- ) V - xx,)
O 2 S PV
1 i/n-1(r(Ex)
7

---

We are now ready to introduce our estimate of EAug( (A). To this end, for any a 2 1,
E Ca
R (A) = (1-
Cx) (11-
+ Ala
(6)
where a = m/(n + m). In addition, we also consider the quantities
a- (x(X) 11 1 (1 1-///g (x)) x (Rx-uc(A)) X] X1,
n
a ir " (X) +
(E [Ca X] (X) X))
m
and the two functions
(X) = (1-d/i) d/n) tr Rx(())
(AA(())
+ AIa 7) IA, (X),
d
ax(x)
(8)
(x( - - ///ag()))))
R (2)
R2alx)
(ado(x)
+ lld
da
az(X)
Finally, we set
1 EAng (A) = d (( -xxx)x))) + (xx²)xx)
and emphasize that Euug (A) is computable from X alone, provided sample from the distribution G conditionally on X. Our main result below states conditions under which &xug (A) concentrates around EAug( (A), for À arbitrarily small.
Theorem 2. Assume H1 to H5. Let Exug (A) be defined in (9). Denoting s = (n. A}. for two scalars Ti and T2, (also independant of n, d and m, and depending polynomially E) defined in (78), it holds
P ((EAu((A) EAug(A) 1 AAUS) S enexp (-x((=k(n + m) /
where
A Aug- = E1 (03 + (1 + +x 11pp + ||x ||Exx*+IXxlllll (lophe) E (A [r]
-
+ +
(1- a--a)mil amaa (E?
33Vd
|ExI
Vd [ExE[Ac(X)] E [X)
and the constants Õ₁ and C2 depend polynomially on Ax(Ex), | lop x- n/m, K, LG and e.
In the statement above, the three contributions to DAug are small under natural conditions. The first term decays like n1 provided the covariance matrices Σx and Ac(X) remain well-conditioned and the fraction of artificial samples stays bounded away from one. The second term vanishes if the fluctuations of Ag (X) adequately controlled. Finally, the third term is negligible only when IE [Aa(X)) approximately commutes with Σx. for instance, when the eigenvectors of Σx are known, when the augmentation is isotropic on average (so that E [Ag(X)] is scalar matrix), or more generally when E [XG(X)] splits into a low-rank component plus a multiple of the identity (as in Gaussian mixture augmentations with few components relative d, c.f. table 1).
4 Numerical experiments
In this section, we illustrate Theorem and Theorem 2 on real datasets. We use MNIST and CIFAR10, consisting of 70,000 labeled 28 x 28 images and 60,000 labeled 32 x 32 images, respectively, with the following preprocessing:
MNIST. We discard the labels, normalize pixel values to [0, 1]. and add pixel-level Gaussian noise with standard deviation 0.1 ensure that the covariance matrix Σx is well-conditioned.

---

CIFAR1O. We discard the labels and convert images to grayscale.
For both datasets, we denote by X = [X Xn] Rdx= the matrix formed by the first samples, for varying > 0. To approximate Ex (A) and Eaug(A) computed from all available samples (70,000 for MNIST, 60,000 for CIFAR 10), and consider the proxies
the sample covariance matrix Σx
(((A) = - ( -
and := |Rug (A)
(10)
Ft
which are expected to closely approximate Ex(A) and (A)g(A) since the sample size greatly exceeds the data dimension.
Figure summarizes our results for MNIST. In particular, figure la reports À Ex (A) for various = 784/n n over À E [10 3, 1]. and compares it with the proxy above. Figure 1b and Figure lc present (Aug(0) as function of a m/ + m) under two lata-augmentttion schemes. The first is a k-centroid Gaussian-mixture GDA,
G mi, (X) + (O,
where the centroids {m: are estimated via EM on X and Ij Uni,([,.... k}). The second is a Gaussian-noise TDA,
=, oN(
with 1 Unif (fl....,)) n²)). In both cases, the minimizers of X EA( and + EAng (A) are consistently close those the proxies (A) and &ug (A). which should very closely approximate the true errors.
Symmetrically, for CIFARIO (after grayscale conversion, d 1024), figure 2a reports À - Ex (A) for various = 1024/n n over X E [10-3, 3 1] and compares it with the proxy in (10). Figures 2b and 2c present EAug(0) as a function of a m/ + m) under the same k-centroid Gaussian-mixtun GDA and Gaussian-noie noise TDA schemes above. In all cases, the minimizers of À + Ex (A) and EAug(A (A) closely match those of the proxies Ex (A) and Aug (A).
declt vs 62,10 vosi vieae orc
2ught di, Phwocca
2037
13107
2437
(a) Non-augmented, Ridge-like esti-bb 10-centroid Gaussian mixture mator.
(c) Gaussian noise TDA.
GDA.
Figure 1: Numerical results MNIST for Ex and Exng (A), compared with (10).
Fox 1ii Raurdda Matuon
fu 20,20 tie undia reieo Tix
241271
1844
7456
(a) con-augmented, Ridge-like like esti-(b) 10-centroid Gaussian mixture mator.
(c) Gaussian noise TDA.
GDA.
Figure 2: Numerical results on CIFAR-10 for Ex(N) and Exug (A), compared with (10).

---

Conclusion
In this paper, we established new results based on random matrix theory that allow one quantify from data only the impact of the regularization effect induced by data augmentation on common class of precision matrix estimates. In the meantime, we presented formula that allows one to compute from data only the error of a non non-augmented "Ridgelike" precision matrix estimator. From a practical point of view, our results might allow one to optimally tune hyperparameters of data augmentation scheme for estimating the bottom eigenvalues and eigenvectors of the covariance matrix of the data, provided the data augmentation scheme satisfies a strict commutativity condition. Furthermore, it is well understood that the precision matrix is a fundamental object in many statistical models; hence, a natural extension this work would be to study the generalization error of various machine learning models, such lincar regression, kernel regression, some class of shallow networks.
10

---

References
[AEK*14] Bloemendal Alex, László Erdós, Antti Knowles, Horn-TTzer Yau, and Jun Yin. Isotropic local laws for sample covariance and generalized wigner matrices. Electron. J. Probab., 19:no. 33, 1-53, 2014.
[BGBP23] Florent Benaych-Georgen Jean- Shan-Phllippe Bouchaud, and Marc Potters. Optimal cleaning for singular values of cross-covariance matrices. The Annals of Applied Probability, 33(2):1295-1326, April 2023.
[BGP16] Taras Bodnar, Arjun Gupta, and Nestor Parolya. Direct shrinkage estimation of large dimensional precision matrix. Journal of Multivariate Analysis, 146:223-236, 2016.
[Bis95] Chris M. Bishop. Training with noise is equivalent to tikhonov regularization. Neural Computation, 7(1):108-11 116, 1995.
[BLLT20] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):3003330007
2020.
[BM13] V. V. Buldygin and K. K. Moskvichov. The sub-gaussian norm of binary random variable. Theory of Probability and Mathematical Statistics, 86:33 49, 2013, Article electronically published on August 20, 2013.
[Car88] Blair D Carlson. Covariance matrix estimation errors and diagonal loading in adaptive arrays. IEEE Transactions on Aerospace and Electronic systems, 24(4):397-401, 1988.
[CDL.20] Shuxiao Chen, Edgar Dobriban, and Jane H. Lee. A group-theoretic framework for data augmentation. Journal of Machine Learning Research, 21(245):1-71, 2020.
[Cho22] Clément Chouard. Quantitative deterministic equivalent of sample covariance matrices with a general dependence structure, 2022.
[CKNH20] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597-1607. PmLR, 2020.
[CL25] Adil Rengim Cetingoz and Charles-Albert Lehalle. Synthetic data for portfolios: A throw of the dice will never abolish chance, 2025.
[CLLI1] Tony Cai, Weidong Liu, and Xi Luo. A constrained & minimization approach to sparse precision matrix estimation. Journal of the American Statistical Association, 106(494):594-607, 2011.
ICZM+19) 19] Ekin D. Cubuk, Barret Zoph, Dandelion Mané, Vijay Vasudevan, and Quoc V. Le. Au- toaugment: Learning augmentation strategies from data. In 2019 IEEE/CVE Conference Computer Vision and Pattern Recognition (CVPR), pages 113 113-123, 2019.
[DFK24] Elvis Dohmatob, Yunzhen Feng, and Julia Kempe. Model collapse demystified: The case of regression. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[DFSK25] Elvis Dohmatob, Yunzhen Feng, Arjun Subramonian, and Julia Kempe. Strong model collapse. In The Thirteenth International Conference on Learning Representations, 2025.
[DGR+19] Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Chris De Sa, and Christopher Re. kernel theory modern data augmentation. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1528-1537. PMLR, 09-15 Jun 2019.
[DKT21] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high-dimensional binary linear classification. Information and Inference: Journal of the IMA. 11(2):435-495, 04 2021.

---

[DLM20] Michal Derezinski. Feynman T Liang, and Michael W Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Infor- mation Processing Systems, volume 33, pages 5152-5164. Curran Associates, Inc., 2020.
[DRBK20]
Stephane Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double trouble in double descent:
Bias and variance(s) in the lazy regime. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2280-2290 PMLR, 13-18 Jul 2020.
[FG Steven Y. Feng, Varun Gangal, Jason Wei, Sarath Chandar, Soroush Vosoughi, Teruko Mitamura, and Eduard Hovy. A survey of data augmentation approaches for NLP. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 968-988, Online, 2021. Association for Computational Linguistics.
[FLL16] Jianqing Fan, Yuan Liao, and Han Liu. An overview of the estimation of large covariance and precision matrices. The Econometrics Journal, 19(1):C1-C33 C32, 2016.
[GLK+21] Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, and Lenka Zdeborova. Generalisation error in learning with random features and the hidden manifold model. Journal of Statistical Mechanics: Theory and Experiment, 2021 2021(12)1224013, 2021.
[GSA+20] Jean-Bastien Grill, Florian Strub, Florent Altche, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, al. Bootstrap your own latent-a new approach self-supervised learning. Advances in neural information processing systems, 33:21271-21284, 2020.
[GSKI8] Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. arXiv preprint arXiv:1803.0722 2018.
[HGK20] Alex Herrandez-Garria and Peter Konig. Data augmentation instead of explicit regular- ization, 2020.
[HMRT22] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949986,, 2022.
[TTL+24] Romain Ilbert, Malik Tiomoko, Cosme Louart, Ambroise Odonnat, Vasilii Feofanov, Themis Palpanas, and levgen Redko. Analysing multi-task regression via random matrix theory with application to time series forecasting. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[KBB Polina Kirichenko, Mark Ibrahim, Randall Balestriero, Diane Bouchacourt, Shan- mukha Ramakrishna Vedantam, Hamed Firooz, and Andrew Gordon Wilson. Un- derstanding the detrimental class-level effects of data augmentation. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[Kir34] M. Kirszbraun. Über die zusammenziehende und lipschitzsche transformationen. Fun- damenta Mathematicae, 22(1):77-108, 1934.
[KY17] Antti Knowles and Jun Yin. Anisotropic local laws for random matrices. Probability Theory and Related Fields, 169(1):25--352,2 2017.
[LC18] Cosme Louart and Romain Couillet. Concentration of measure and large random matrices with an application to sample covariance matrices. arXiv preprint arXiv: 1=Xiv:8005.0829) 2018.
[LC23] Cosme Louart and Romain Couillet. Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns, 2023.
12

---

[LCM21] Zhenyu Liao, Romain Couillet, and Michael W Mahoney. A random matrix analysis of random fourier features: beyond the gaussian kernel, a precise phase transition, and the corresponding double descent. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):12006, 2021.
[LKDM22] Chi-Heng Lin, Chiraag Kaushik, Eva L. Dyer, and Vidya Muthukumar. The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspective. J. Mach. Learn. Res., 25:91:1-91:85,, 2022.
[LKK+19] Sungbin Lim, Ildoo Kim, Taesup Kim, Chiheon Kim, and Sungwoong Kim. Fast autoaugment, 2019.
[LLM20] Elnaz Lashgari, Dehua Liang, and Uri Maoz. Data augmentation for deep-learning-bars based electreencephaaoggappyy Journal of Neuroscience Methods, 346: 108885, 2020.
[LP11] Olivier Ledoit and Sandrine Peche. Eigenvectors of some large sample covariance matrix ensembles. Probability Theory and Related Fields, 151(1):233-264, 2011.
[LSW03] Jian Li, P. Stoica, and Zhisong Wang. On robust capon beamforming and diagonal loading. IEEE Transactions on Signal Processing, 51(7):1002-1715, 2003.
[LW03] Olivier Ledoit and Michael Wolf. Improved estimation of the covariance matrix of stock returns with an application to portfolio selection. Journal of Empirical Finance, 10(5):603-621, 2003.
[LW04] Olivier Ledoit and Michael Wolf. well-conditioned estimator for large-dimensione covariance matrices. Journal of multivariate analysis, 88(2):365-411, 2004.
[LW12] Olivier Ledoit and Michael Wolf. Nonlinear shrinkage estimation of large-dimensional covariance matrices. The Annals of Statistics, 40224::02110 2012.
[LW22] Olivier Ledoit and Michael Wolf. The power of (non-) linear shrinking: A review and guide to covariance matrix estimation. Journal of Financial Econometrics, 20(1):187 218, 2022.
[MH12] Rahul Mazumder and Trevor Hastic. The graphical lasso: New insights and alternatives. Electronic journal of statistics, 6:2125, 2012.
[MM22a] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022. First published online: June 6, 2021.
[MM22b] Alhassan Mumuni and Fuseini Mumuni. Data augmentation: A comprehensive survey of modern approaches. Array, 16: 100258, 2022.
[MMN22] Kiran Maharana, Surajit Mondal, and Bhushankumar Nemade. A review: Data pre- processing and data augmentation techniques. Global Transitions Proceedings, 3(1):91- 99, 2022. International Conference on Intelligent Engineering Approach(ICIEA-2000
[MP67] V. A. Marchenko and L. A. Pastur. Distribution of eigenvalues for some sets of random matrices. Math. USSR-Sb. 1(4):457-483, 1967.
[MVSS20] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harm- less interpolation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 1(1):67-83, 2020.
[SCDL224) Dominik Schroder, Hugo Cui, Daniil Dmitriev, and Bruno Loureiro. Deterministic equivalent and error universality of deep random features learning*. Journal of Statistical Mechanics: Theory and Experiment, 1024(10):000117, oct 2024.
[SDCL24] Dominik Schroder, Daniil Dmitriev, Hugo Cui, and Bruno Loureiro. Asymptotics of learning with deep structured (random) features. In Proceedings of the 41st International Conference on Machine Learning (ICML., pages 43862-43894, PMLR, 2024, Published: 21 July 2024.
13

---

[Si189] Jack W. Silverstein. On the eigenvectors of large dimensional sample covariance matrices. Journal of Multivariate Analysis, 10(1):1-16, 1989.
[SK19] Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of big data, 6(1): 2019.
[SM50] Jack Sherman and Winifred J Morrison. Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. The Annals of Mathematical Statisties, 21(1):124-127, 1950.
[SS05] Juliane Schafer and Korbinian Strimmer. A shrinkage approach large-scale covariance matrix estimation and implications for functional genomics. Statistical applications in genetics and molecular biology, 4(1), 2005.
[S Ilia Shumailov, Zakhar Shumaylov, Yiren Zhao, Nicolas Papernot, Ross Anderson, and Yarin Gal. Ai models collapse when trained on recursively generated data. Nature, (81())2)):55577555 2024.
[vDM01] David A. van Dyk and Xiao-Li Meng. The art of data augmentation. Journal of Computational and Graphical Statistics, 10(1):1-50, 2001.
[Ver09] Roman Vershynin. High-dimensional probability, 2009.
[Verl1] Roman Vershynin. Introduction the non-asymptotic analysis of random matrices, 2011.
[Ver18] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[Wis28] John Wishart. The generalised product moment distribution samples from normal multivariate population. Biometrika, 20A((/2):32-52, 1928.
[WPTZ15] Cheng Wang, Guangming Pan, Tiejun Tong, and Lixing Zhu. Shrinkage estimation of large dimensional precision matrix using random matrix theory. Statistica Sinica, pages 993-1008, 2015.
[WZVR20] Sen Wu, Hongyang Zhang, Gregory Valiant, and Christopher Re. On the generalization effects of linear transformations in data augmentation. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10410-10420. PMLR, 13-18 Jul 2020.
[YL07] Ming Yuan and Yi Lin. Model selection and estimation in the gaussian graphical model. Biometrika, 94(1):19-3 03 2007.
[ZWZZ20] Xinyu Zhang, Qiang Wang, Jian Zhang, and Zhao Zhong. Adversarial autoaugment. In International Conference on Learning Representations, 2020.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Our abstract clearly states main resutls of our paper. The claims are then stated fully and diseussed in the main body. We have tried to briefly discussed the limitations of our study in the abstract, but these limitations are only discussed in detail Section 3.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions 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 fine to include aspirational goals motivation long it is clear that these goals not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We introduced strong and restrictive assumptions the data augmentation scheme used, these limitations were discussed and several examples of scheme satisfying all the assumptions were presented. Section 3, we further discuss the range of applicability of Theorem 2, by presenting few DA example on which our bounds are tight.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to vi- olations of these assumptions (e-g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it 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 address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by review- ers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important 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
15

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Assumptions to each theorem of the paper are clearly stated in HI, H2, H3, H4 and H5. Although the proof' of our results do not appear in the main body of the paper (apart from a brief sketch for Theorem 1), they are provided in the various sections of the appendix, whose headings designed help the reader locate each proof easily.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by
formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [No]
We aknowledge that our results Theorem and Theorem are not fully explicit due to the unspecified constant 7). Indeed, there is no obvious choice for 7). although we discuss how to select this parameter in Appendix A.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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.
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 a novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access hosted model (e.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend the nature of the contribution. For example
(a) If the contribution is primarily a 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) If the contribution is be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how construct the dataset).
model (e.g., large language model), then there should either
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of dlosed-soure models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
16

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions
faithfully reproduce the main experimental results, as described supplemental material?
Answer: [Yes]
Justification: Our numerical experiments have been performed on the well known, open-access, dataset MNIST, the data pre-processing that was aplied was thoroughly described in Section 4. Although we do not provide the code for our numerical experiments, the definition of EAug (A) in Section is self sufficient to replicate our results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: http//itps.ccppblliee/ guides/CodeSutee ssoonolicyy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips.cc/publll htcp/pblic//guieeeeeeeoopecceeee Seriideee/ooeSSumiiii ssi onooiicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only subset of experiments are reproducible, they should state which ones 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 the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparame- ters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: These consideration were discussed in Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core of the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We emphasis that in Figure and Figure 2, the quantitics that plotted realization of random variables, because users shall only be interested by one realization, we do provide further statistical significance tests. The error of our estimates given in Theorem and Theorem are clearly visible Figure and Figure 2.
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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to 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 or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not 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 in the text how they were calculated and reference the corresponding figures or tables the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [No]
Justification: Although the aspect of computer ressources were not discussed in the paper, we believe that our estimator doesn't 't require any particular computing or memory ressources to be efficiently implemented. For this reason, we deemed this discussion as unnecessary.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethies https://neurl:: http://wwwuriiss.ppppbc...cc cc/pubblcc/tthheauu.daaa
Answer: [Yes]
Justification:
We reviewed and conformed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure preserve anonymity (c.g., if there is special consideration due to laws or regulations in 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]
Justification:
We do not inditify any relevant socictal impact of our work.
Guidelines:
The answer NA means that there is socictal impact of the work performed.
18

---

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.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly eredited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Our work and experiments only rely the MNIST dataset, which is publicly available and was appropriately referenced in Section 4. The proofs of our results sometime rely existing works, which were systematically cited.
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 or 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 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.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode. thcode. com/ datasets has curated
licenses for some datasets. Their licensing guide can help determine the license of dataset.
19

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should provided. this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification:
We do not release any new assets in paper.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/moodll as part of their sub- missions 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. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We do not use crowdsourcing nor human subjects in our paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human sub- jects
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 an equivalent approval/review based the requirements your country or institution) were obtained?
Answer: [NA]
Justification:
We do not use crowdsourcing nor human subjects in our paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
20

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non- standard component of the core methods in this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration not required.
Answer: [NA]
Justification: We did not use any LLMs for this work, appart from simple writting and editing task, such as grammar correction, which is accepted by the NeurlPS LLM policy.
Guidelines:
The answer NA means that the core method development in this research does not involve
LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https penetps://neee //tt:://nnu...eeeee wwaerripssccccoooeeeee http///ripss.cc/affffeeeeeeeeeee /c///onferencce//22//////11 for what should or should be described.
21

---

A In-depth justification of the hypothesis
This appendix provides detailed justifications for the technical assumptions introduced in the main text. In Appendix A.I, we analyze the concentration of the smallest eigenvalues of empirical covariance matrices under mild conditions, thereby establishing H2 for standard random matrix models commonly studied in the literature. Subsequently, in Appendix A.2, we focus on data augmentation schemes and identify natural conditions for TDA and GDA under which Assumptions H H5 are satisfied.
A.1 Discussions on H2
In this subsection, establish explicit conditions under which H2 holds and provide closed-form expressions for the parameters and cx These expressions are not directly estimable from data, they depend structural properties of the population covariance Ex, in particular its smallest eigenvalue Ad(Ex) Nonetheless, they yield useful theoretical insight into the regimes where our results applicable. Formally,
obtain the following result:
Proposition 3. Assume that X satisfies HI, and that Aa(Ex) > 0. There exists a universal constant such that whenever n d > H2 guarenteed hold for any choice of and ex satisfying:
7 7 >d(xx (V
vo) and cx =
Aa(Ix)
To support the previous claim, introduce standard non-asymptotic result from random matrix theory. For a rectangular matrix A E Rd we denote by smin(() (A) its smallest singular value. The following theorem, due to Rudelson and Vershynin [Verll, Theorem 5.39), provides sharp lower bound on 8min for random sub-Gaun Sab-Gaussian matrices.
Theorem (Rudelson- (Rudelson-Vershynin [Verl1, Theorem 5.39]). Let Z be d random matrix with 2 d, whose columns are independent, identically distributed, mean-zero, isotropic sub-Gaussian random vectors in Rdd Then there exist absolute constants e such that, for all I 0,
smin (2) 2 Vn- - vd-tt 2 1-2c dd
Observing that X 11/22 - where Z has isotropic and independant columns (under HI) and applying Theorem 3 to Z. we obtain the following bound the probability of encountering small cigenvalues the leave-one-on covariance matrix Cx- Corollary 1. Assume that X satisfies HI. Then, for every O.
(-
2
P(MI(C>) I exp -c
Exx
where e > O is the same absolute constants as in Theorem In particular, Proposition follows directly.
Proof. Let 7 == E Then Z is random matrix with i.i.d. isotropic uab-Gaussian columns, since satisfies Hi and,
E 1 Ez n
Using the inequality Smin (AB) > Smin (A) (B), we obtain
>a(Cx) - smin (x-)² {xa(Ex) smin )2 where -- -Z,,..... Znl
Hence, for any 0 5 Vn- - 1 Vd. have
I Ad(C)) (xxx (Vn - dd t)²
2 IP smiu (minn(Z Vn
vd vd-
n
Applying Theorem 3, we deduce that for all 2 O, we have,
( (V Va
2
2 1 - 20-
(11)
vn
22

---

Now fix any 0<イs Aa(Ex) (n 1)/n vd/n) and define
bn
n=1 xx)
Vn
By construction, bn 2 And substituting / by into (11) yields
P(Nx(Cx) 2 2 2e 4t
which is the desired bound.
A.2 Discussions on H3, H4, H5
In this section, we demonstrate that several common data augmentation (DA) schemes satisfy Assumptions H3-H5. We also discuss the limitations of these assumptions and identify scenarios in which they hold exactly, thereby clarifying the regimes where results apply. We begin by introducing a generalization
which will help us achieve more general statements, as well as simplify the proofs. To this end, introduce the following definition of Lipschitz concentrated random vectors:
Definition (Lispehitz concentration). We say that,
(i)
The random vector Xı Rdd is Lispchitz concentrated with parameter if and only for any 1 L-Lipschitz, function J, and any & 2 0, we have,
E exxp (sff(Xi) - E[f(X)II)) exp (o²s²)
(ii) The probability distribution μ E P(Rd) has the Lispchitz concentration property of paramet if and only if for X1 ~ μ2, X2 is Lipschitz concentrated with parameter a.
and we replace HI by the following assumption:
H6 (Lipschitz concentration of the data). The columns X1,..., E Rd of the data matrix X Rdxn are independent random vectors, each of which is Lipschitz concentrated with parameter
ax 0 in the sense of Desinition 1. Equivalently, for every --iisccilt.funntiion . I and every 8 2 0,
E(esp(s(f(X))- - -EI((XI))) S 2 2exp
for all i E (l,...,
One can easily check HI implies H6, furthermore the class of matrix satifying H6 being stable by Lispchitz transformations (up to rescaling of concentration parameter), will turn very convenient for the proofs of our main results.
We now provide set of simple sufficient conditions under which H3 is satisfied, we believe that the vast majority common data augmentation scheme satify this condition. First, in the case GDA schemes, show that under almost sure smoothness property of the sample generation process Item (i) is satisficd:
Proposition Let X RRdx be random matrix. Assume that for each j E (1....,m), G₁ f(Z,, X), where Zúj are i..dd. random vectors with the az apssiit concentration property, and where f(, X): Rd - Rd is almost surely L -ipisscchitz Then G = [GI...., Gm, satisfies Item (i) of H3, with parameter
DG Lyoz.
Proof. Let μ denote the distribution of Z, so that for any measurable set E c Rd ((E) = P(Z E E). Since G,- f(,, the conditional law of G, given X the pushforward measure of μ under f(;X);
vx f(,X)*
where for measurable map y A measure j on A, we recall the notation **1(E) (E).
23

---

To show that G satisfies Item (i), we set h : R + R to be any 1-Lipschitz function such that [h( Consider, for 2
E lexp (sh(Gi)) X] E lexp (sh(f(2), [
The mapping
11
(11,
is centered with respect to n by the assumption on h. and it is Ly-Lipschitz almost surely, since it is the composition of 1-Lipschitz map and an Ly-Lipschitz map. Because Z f has the oz-Lipschitz concentration property we thus obtain
E exp (sh(G1)) X] 1 exp (sL
This establishes that ux has the www.:e.lpcccitcccoceececco conceetratiinnnn property with ag Ly and completes the proof.
Similarly, the case of TDA schemes, we have highlight the following sufficient condition for Item (i) of HB:
Proposition 5. Let X E Rdxx be a random matrix. Assume that G₁ = I(2,, where:
f is ass functioo w.r. its first argument.
-Uni((()....,.)) and Zg has the az-Lipschitz concentration property.
The augmented samples lie in a compact, for all i, [[][(Z, X ll S K.
Then G [G1, ,Gin satisfies Item (i) of HH33fo for
og + 13 ck2 + cL2002
where e is a universal constant.
Proof. Note that under the assumptions of Proposition 5, we have,
1
vx f(, ((,
where μ is the distribution of Z, such that P PZ E ((E). for any E Rd. and used the notation * y for the pushforward measure, * ((E)) (E)- for any E C Rd.
We show that vx has the Lipschitz concentration property, to this end, let Rdd + R be a Lipschitz function (X -measureable) such that h(0) (note that this can be assumed without loss of generality). For notation simplicity, we further define = any 0,
h E [b(G)) X), then we have for
exp (s(h(G1) - (h(,))
XT) | = E exp (sh(G:1) |x]
(exp (sh X,))) X]
Denote by m, E [b(((2,.x)) [X] BB X²)) X - [h(1i) X]. we further write,
(eep ( xT)
Σ exp (sm+) E [exp (s (T; X,)) mm))]
$ cxxp (s²1.))
Σ exp (sm:)
where have used the Lipschitz concentration of μ. and the Lipschitz property of h in the last bound. We now denote π as the following measure,
8m.
24

---

where 5m, is the Dirac measure at m, Remarking that n support (because the X; 's are boudned and the maps f and h are Lipschitz). We further write,
E O. and that π has bounded
E (exp (s(M(G)) - E [b(Gr) XJ)) X] S exp (s²L3) B [exp(s (M E [M]}] to conclude the proof, note that M ~ x has bounded support in R, as so necessarly Gaussian, with uub-Gaussian norm,
(12)
|M 1l 2 In(2) :
sup |mmal
which follows from [Ver09], Example 2.5.8. Thus, we have for a universal constant c > 0,
Eg (exp (s {M- - E [M]]]] S
exp
cs sup
sup /m;l?)
(13)
Finally, we bound |mj independantly of i, leveraging the boundedness of X. We have,
m [B(M X:)) X]]
[h)f(o,x,)) + E [h, x,)) (f)((o,)))) XI]
[|]
S sup ([](00,)))) 2
isn
sup |m,1 = sup E [M] (Z, X,)) x)- X]I
< 22uup E [h ( X.)) X]]
s 22 + sup E [ X;)) ((O) X]
$ 2|(1(0 + sup E [|| (2 x,) X
< 2 [h() sup EE [f (Z, X,, X1ll2 + sup /B [l.f((,,)) - BIf(Z,,
X] X]
< suu E [f(Z. X,) X 2 + 2z
Where in the last line, we have used the Lipschitz concentration property of Z, (as well as X,) being Ly Lispchitz), and the fact that (()) = O. We conclude the proof by using the boundedness assumption E [Z( X,) X], which yields,
sup |m < (2K + 2L, < 4K2 + 41302
plugging this back into (12) and (13), we obtain,
E [exp (s (h(Gr) - E (f(Gt) xT)) | exp (s² {L} + cK² + +
As consequences of Propositions and 5, broad class of commonly used data-augmentation (DA)
schemes satisfy Item (i) from H3. In particular:
(1) Deep generative models. Consider generative mapping
f(2,X) 0% 01( .......00 (002))))
where L 2 1. Let de denote the width of layer (so dy = dz and dp = d). For each ( 1...., L.
assume o; Rede + Rd is a non-linear, 1-Lipschitz activation and Q E Rdexde1 is (possibly X-dependent) weight matrix. Suppose further that the operator norms are a.s. bounded by constant K, i.c., |10 op < K for all e. Then, by Proposition 4, the matrix
G = GI...., Gm]:
Gj [(Zj, X), Zz N(O, Taz):
satisfies Item (i). Indeed, the network X(; is I |100 -ipschic, hence K LL-Lipschitz a.s., from Proposition 4 it results that G satisfies Item (i) of HB with concentration parameter KL.
25

---

(2) Transformative data augmentation. Likewise, Proposition 5 provides mild conditions under which Item (i) holds for transformative DA schemes. Consider
G = [G
G₃ = f(x,, 2z), 1 Unif((L...... Zz p.
i.e. we randomly select the sample to be deformed, and the deformation smooth w.r.. some parameter Z. Numerous standard transformative DA mechanisms smooth, small-amplitude perturbations; later in this section we detail the cases of Gaussian noise and random masking.
The second part Item (ii) of H3 is not always theoretically guaranteed, yet in the case of an unbiased TDA it is immediate consequence of the law of total variance. Indeed, assuming G3 = f(XX, Zj) as in Proposition 5, and that vx, [ Z) = one can write
n
E|Ce x]
x] xX [x] (X, 2)
n
Σ E (f - (I, xI)(f(X, BIf(X,, 2) x1) x [
= Cx + 1 -x - xx]
where 15 Unif([],..... m)) and Zz ~ μ are independent.
In the of GDA, the decomposition in Item (ii) of HB holds trivially, yet simple expression of (X) exists.
We now spell out conditions under which H5 holds. To this end, we introduce the following upper bound:
Lemma 1. Let yn and u2 be two probahility measures Rd. Then, for any m 1,
Wi(m 6m (1))) S Vm
Proof.
Recall that
cT( m?") / |
Wi(u 6m (
inf Ym
x' ||e drim (x,
where r(...) denotes the set of all couplings and || ||r is the Fuclidean/Froheeiuss norm on (Rd)m.
Let 7 (121, be optimal coupling for W2, that
f 11-- du,)),u,,))
W2(u1,
Consider 7/m : 7 E I'(m1 @m ). Then, by the definition of W and Cauchy-Schwar,,
Wi(uI" @m 11z (m) $ ||x - x' dy (1,""(xxx' (0) S (/ ||Ix dy - (z, (x, 1/2
/ | - d (1s,)
1/2
vmn V2Wiinn,
The previous result is particularly convenient for demonstrating that H4 and H5 hold, which will be done in full detail for all DA scheme presented in Table 1. Towards full justification of Table 1, we show that (5) holds. In particular, we establish that the following true:
Lemma 2. Assume that
G; S(x Z,); j= m,
where I, ~ Unif(I,.... n) and Zi.... Zm are i.i.d. random variables. Further suppose that for each i n,
E [[f(X, Z1) Xx] VBX,,
BE [0, 1).
26

---

Then
1 Σ B -V-x -V3x.) x].
BB[G X] BCx
+
and Item (ii) H3
H3 holds.
Proof. We use the notation
B|G x [B2]/(X1, x], ..... Bz[ 2) X] Rdx=.
By the law of total variance,
E|Cg X = E
x] = Σ
()xx, |x]
1m1
xI) [x] BIF(X,, 2) xx]) CEGIIX| + Σ Σ (1(X,
n
x
3C 1 Σ E [1((x, (1X-VXx.)((Xxx. -VBx.)" |
which concludes the proof.
Relying on the above results Lemma and Lemma 2, we now justify the results presented in Table 1.
Fixed Gaussian GDA: Consider the Gaussian GDA schemn where, for all j {I...., m), we have Gý ~ N(0, A), for some fixed positive semi-definite matrix A.
We recall from [LC18, Theorem 2.19] that the standard Gaussian distribution N(0,Ia) in Rd satisfies the 1-Lipschitz concentration property. Moreover, the mapping + 11/2Z is ||A/// |lpp/hllo-Lippsciizz (with respect to the Frobenius norm), which, by the same result, implies that is ||A 1/2 //lpo--ppshhitz concentrated.
Furthermore, we have
E|Cg X E =A,
which shows that the Gaussian GDA scheme satisfies H3, with 3 Ag A, and og ||A4/2||| Ilop
Finally, note that //x N)O,A) is constant (i.e., independent of X), and therefore trivially satisfies both H4 and H5.
In the more general and realistic case where the covariance matrix of the artificial distribution depends on X, we assume that G, N(0, A(X)) for all j S m, such that A is LA- Lipschitz (with respect the Frobenius norm), and that K Aa(A(X)) < ... [IX()ll almost surely. These assumptions directly ensure that both parts of H3 are satisfied: indeed G is guaranteed to be K-Liiscchiz concentrated conditionally on X for the same reason in the fixed Gaussian case, and Item (ii) holds with (x + A(X) by definition. Similarly, the second part of H4 is satisfied by the hypothesis on A(X).
Gaussian GDA:
K
To show the first part of H4, we use an equivalent "Procrustes" form of 2-Wassertein for zero-mean Gaussians with covariances:
W7 vx)
min UEO(d) ||(x))/22 | 1000:/2-AXX1111 -
tr (A(X) A - -1X
which follows expanding |/2 B1/2U || and maximizing (3/ over orthogonal U via von Neumann's 's trace inequality. This yields
vx) I ||A(X) (AAX)) 1/2)
(14)
To further bound the above W₂ metric, we need to prove that spectral transformations of large symmetric matrices Lipschitz. To this end, we introduce the following lemma:
27

---

Lemma 3. Let A and B be two symmetric matrices in IRdx with respective eigenvalues (1
Aa(A) and A (B) 2 2 (B). Let f + R be Lipiscchtt on an interval containing
(A) (B) Then
(If(A) f(B)llF Ly || -BIFF.
where for any symmetric matrix M = P dliag(d1........ da) PT, we define f(M) PT.
Proof. Define the path W(1) B - ((A - B) for L E [0, 1]. Note that each (()) is symmetric, and
S(A) - J(B) = - {" d
dt (W(()) de.
By the triangle incquality,
IIf(A) f (BB)l I (W((t) dt = ([(((((())))) (A - B)ll dt,
d dt
where (((((t) denotes the (matrix) derivative coming from the spectral calculus. Since f is Ly- Lipschitz on interval containing the spectrum of each W(I,, we have (I)(((() llop S Ly for a.e. t, hence
IIf(A) - f(B)le & / Ly 1 ||A-BBBp df = L, IIA BllB. 1-BBE-
This proves the claim.
To conclude on the Lispehitz bound, apply Lemma 3 f(t) Vt on the spectral interval of A(X)
and AYY). Recall that we have Aa(A(-)) 2 K-1, then || = suP12x-1
vK
2v7
2
VR 2
VK
1A( |r S
|A(X) - A(Y)lI I
LA x Y
2
Combining the previous with (14) yields
K 2
LA X Y
Mixture GDA (concise). We consider a DA scheme that, conditionally on X, samples from N N-component mixture with
G3 A1, (X) 1/2 + my, (X), Zj ~ ,1 17
where each Ag (X) > O, the mixture is centered Σ my (X) = and μ is bounded and isotropic with E = x² La. Assume is oz Lipschhct concentrated and, for every k, Ax(.) and m, (-) bounded Lipschitz functions (with constants LAz, Lmz). Let u be the uniform measure (1....,N] N} and define
fx(2,k) (x) m4 (X).
PX (fx) (n u).
Concentration and conditional covariance. Since @ u is Lipschitz concentrated and fx is Lipschitz on Sμрр(u) f1....,N' NN. the pushforward vx is Lipschitz concentrated, so Item (i) holds. Moreover,
1 N
B|Ca X E G
x
Σ
(x) 1/2 2 [Ax(()) + my (X)m=(X)T) (X).),
and since A (-), me(+) are Lipschitz and bounded, so Ac(:); hence the second part of H4 and Item (ii) of HB follow.
28

---

First part of H4. By Cantorovich-Rubinseenn and i.dd. structure,
(fx (,) Fx(2), I vm (11 1/2
Wi(UX
28 mm
S E
N
1/2
= =m
-(()))))))RAM)))))))+ Ax(Y) (mm(() - me (Y3))1
N
1/2
m
(M( (
(x) m. (Y)
N
If the spectra of (+) are uniformly bounded below by K- > O, then by Lemma with f(t) Vt.
VK ||Ax(X) -x(() S
LA, K
[|Ax(X) (22
1x Y|
2
and [X) - m& mx (Y)l22 S Line
| - Y|IF.. Thus
1/2
03
W1 pm
L
m
| Y
4N
which proves the first part of H4. Stability follows similarly.
Fixed Gaussian TDA. Consider the TDA scheme
Gj = X1, + A Z,, Zj ~N(O,Ta), In ~ Unif(1,...,nI} By Lemma 2 with B (unbiasedness), we obtain
B[Cg X] = Cx + A.
Moreover, the augmentation noise law is fixed:
Vx A)., hence it does not depend on X and therefore H3, H4, and H5 are satisfied trivially in this setting. (Equivalently, since the standard Gaussian is 1-Lipschitz concentrated and the map +> A1/22 is -iipschiz, G is ||A - concentrated conditionally on X.)
Random masking TDA. Consider the augmentation
Gj bj @ X1,, I ~ Unif(1,.... n). by ~ Bernoulll(1 - p) p) (i.i.d), where & denotes elementwise product. Assume X bounded, i.e., ||x;|| S K a.s.
Concentration and conditional covariance. Writing
VX = (fx) (Bernoulllli - p) Sd Unif(I.....,
with fx(b, bo X₁, the map fx is Lipschitz on the compact domain (with constant independent of X by boundedness of X). Hence, by Proposition 5, G is Lipschitz. concentrated conditionally on X, i.e. Item (i) holds. Moreover, Lemma 2 with 8 =1 P yields
E[CG X] = (1 pxCx + (x()), Ax(X) = p(1 - p)
so Item (ii) also holds.
Smoothness. Since Ag (X) a composition of Lipschitz maps on the bounded set [- K]dx,, is Lipschitz; this proves the second part of H4. For the first part, couple (u (m)) by using the same (T,, by) on both sides. Then
W1( Wi 2pm
s E
(b, C X1, - by 2 (2,1),
F
1/2
S vm
Ellbi + (X1, k)))
1/2
-m p) (- Σ [X Y, 12
1/2
= vm
E b 2 OX, - -Y)11)
< / (1
p)
X ||
since E[b 1 Ebb = 1 - p for each coordinate k. This proves the first part of H4. Stability
follows by the same argument.
29

---

B Proof of theorem 1
This appendix provides the proof of Theorem 1. Along the way, we introduce several auxiliary lemmas on concentration for transformations of X under H 6. appendix B.1 establishes concentration bounds for random variables of the form f(X) [X) when f is Lipschitz only on a subset E C Fd*= (not necessarily on all of Id We show that the Lipschitz concentration of still yields sharp control of f(X) LE(X). appendix B.2 then analyzes quadratic forms X (XX) )1,, where M :Rdx - dRd and X satisfies H 6. The derivations rely on the Hanson Hanson-Wright inequality (see [LC18, Remark 2.3 Building these results, appendix B.3 derives deterministic equivalent, in the spirit of [Cho22, Thm. 6.16], under H 2, which allows regularizations arbitrarily close to O. Finally, appendix B.4 combines the above ingredients complete the proof of theorem I.
For simplicity, throughout this section we set ox 1.
B.1 Some sub Gaussian concentration bounds
In this section we study random variables of the form f(X) LE(X), where is Lipschitz only on subset E C R (and not necessarily on all of Rdx"). We show that fXX 1g(X) still admits Gub-Gaussian tails and we derive tight upper bound on its sub-Gaussian norm in proposition 6.
We begin with a standard Lipschitz extension lemma (see [Kir34]); for completeness, we include a short proof.
Lemma 4. Let f E IR be L, Lipschitz on E C Rdxn
Define
f(X) infYEE { {f(X) Ly |X 1
X 1d
Then f is Ly Lipischhtt Rdxn and f(X) f(X) for all X E.
Proof. Fix X. X' E Idx and any E By the triangle inequality,
((Y) + 1, YIIe S f(Y) 1 - Y|II 1 X
Taking the infimum over Y E yields f(x) - f(X') + Ly X - X' Swapping X and X' gives the reverse inequality, hence Ly-iisiis
For X E. the Lipschitz property of on Eimplies f(X) < +Ly) Y|IF i for every Y Taking the infimum over gives f(X)= 2 f(X), while choosing Y X gives f(X) S f(X). Thus
f(x) = f(X) on E.
Leveraging lemma 4, we now prove the announced concentration bound for f(X) 1x(X) when f is only Lipschitz on E.
Proposition 6. Ler E C Bdxx and f E + R be Lipsschhi Assume || < oo and that X satisfies H6. Then fX) LE(X) Bxf Lx(X] is sub- Gaussian with variance proxy
oî. S P(X e L) + 1151 of.
where for E 1),
1- 2p
o(p) 1 12 -p)/p)*
oPP(X E))
Proof.
By lemma 4, extend f to f IRdx - R with Lip(}) = L, and Á = f. Define the clipped
map
g(X) max ((x)) II -1
Then g is Lippsshiz,, I| = Il, and = f on E, hence f(X) 1E(X) = g(X) 1E(X) a.s. Write
g(X) 9(X) - E[)( IE(X) = 1E(X) - P(X E),
P:=P(X E E).
30

---

A direct decomposition gives
g(X) LE(X) - (ig(()gg LE()) = g(X) LE(X) - Cov( +pg(X) + (x(X).
=:W
(15)
Applying Hölder with exponents (3,3,3) to the MGF of the sum in (15) yields
E [(eep B[gLE|)] - E[exp[3ssW)] /3 E[exp[3s p g3) Blexp Blgl [E)]//3
(16)
Two easy sub-Gausiian factors. Since X is Lipschitz a universal c > 0 such that
Lipschitz.comnenraaeed concentrated and g is Ly-Lisschit,, there exists
3lexp(3sps(X))) S explc explcs"p²1))) L3}.
(17)
Moreover, Ix(X) is a centered Bernoulli random variable with sub- Gaussian proxy de = a(p) (see [BM13, Thm. 2.1]), and [X][[ < [o
hence
E/exp[ 3s Eíg] 1E(X))) S explcs |fll o²).
(18)
The product term W is Sab-Gaussian (detailed the bound). We prove that W = 9 lg Cov 1E) sub-Gat Gaussian by exhibiting a scale S >> 0 with E Eexp( ( ( S 2, i.e. | u/ S.
First, using (u - u)² s 2u² + 20 and [g] I lgl + [gg s 2ll
2 s 2 12 + 2 Cov(g, LE)² S 8 Il i 2 Cov(g, 1g)
(19)
Next, by Cauchy-Schward,
Cov(g, LE)l & Var(g) v Var((e))
Since g is sub- Gaussian with proxy $ Ly, there exists universal constant Co such that Var(g) s Co L3: also Var(1E) = p(1 p). Hence Cov(g, LE)² s P(1-p(1-p)) p(1 p). p).
(20)
Fix a E (0, 1] and set
8 11 of
8 11
S2 =
(21)
S
OF
2
Using (19)-(21),
W2
811.1133
2 Cov(g, 1E)²
E Exxp
< Eexp {
12) exp
52
S
S
12
a Cov(g,
= Ecxp{a
of
exp
111f of S.
(22)
By the definition of the norm of ig. E Eexp (2202) 22 For 0 a 1, Lyapunov's inequality gives
inequalll
1 EXxp a
< (Bexp(L2/o21) 22.
-
oF
Using (20) in the second factor of (22),
exp{
Cov(g. 12)2
s expfoct
13 - p) [ oe
(23)
411/11 of
for some absolute C1 >> 0. Combining (22)-(33) gives
W2
s 2a exp aA).
L p(1 p) | of
Eexp
A C₁
52
31

---

Choose
A -1 a' = (1+
lm2 E (0, 1|,
so that 2a exp(a* A} S
With S in (21) at we obtain
1/2 52 2, hence
E Exxp
| 1/2 I 5 I (IIFII oF L3 p)).
for a universal constant C (use 1/a* = 1+ A/ In and the definition of A). By the standard sub-Gaussian MGF bound, there exists universal 0 with
Elexp[3>W S exples [ z explce (1 oF + +1 - p))}-
(24)
Conclusion. Combining (16), (17), (18), and (24),
E (ff(X))(f(X) (x (x [E(X)))]] S cs c + I1f1la de
for a universal constant e 0. This is the desired sub-Gaussian MGF bound and proves the claimed variance proxy.
B.2
Concentration bounds for random quadratic forms
We now study the concentration random quadratic forms of the type X ({-))x where M Rdxx Raxdd Such quantities naturally appear in the proof of Proposition We prove the following lemma.
Lemma 5, Let X E IRdxn satisfy H6. Then there exists a universal constant e > such that for any M. Raxa Rdxd
2 - E | )1
2
Var (x M(X )x1
II + Var(t(Ex
Proof. By the law of total variance applied to (X1, X"),
Var(X] M(X ),, E Var(X; ( )X X Var(B[X] M(X-)x) ((xx)xx/x--)
B{[av X M(X )x x
where we used E (X X ([X
It remains control the first term. Conditionally X- the Hanson-Wrije inequality (see [LC18, Remark 2.31J) yields, almost surely,
(e-min
(IIM "I | >)pppp )
12
P(XX] M(--)x (M(MX-)EX 2 X < 2 2exp
Writing the conditional variance in integral form,
Var (XXM(XX) )X1 x
/ P M(X (XXxM(XX 2 vt vt(x-) dt
2 exp csp(- ||MX- )
cxp cxp(
Vi |M(X-) (llop dt
dt + 2
J0
2X
4| 11
where we used the change of variables u = cvt//|M(X [lloo in the second integral. Taking
expectations X gives
B[Var (X | |M +
2 -|
which, combined with the total-variance decomposition above, completes the proof.
32

---

In the special case where the map M : Rdxa - Bdxd is Lipschitz on An (with A, defined in H2), Lemma 5 yields:
Proposition 7. Let X Rdxa satisfy H6 and H2. For any functions Mi An Raxd and
M2 An - Raxd that respectively L1- and Lz- Lippciiii and bounded, and any B E Raxdd with
|B|l = 1, we have
JA, (X)) & 11 { + | & (1 (1+cx)))
LA, (X)) & 1E + [1+
Var (X] M )&, AA, (X)) & 1Ex { (11 M| + | I (1 [1+cx)) ((xx)))
where MM = ||
Proof. We treat the three cases in the same way. By Lemma 5 and since (x, is o- measurable,
Var (ar
Mi(X ]x,
)x, LA, (X))
2
E
|1 >| In, (X) + |MM )10pp Ia, (x)
2
Var(m((xxM(
C
2
M + 2
+ )
( ddl (V
Similarly,
Var (X, Mi B 1A, (X))
2
E [
B (X)
2 ( I )1 IA, (x) (Xr(tr(ExM (x)))
c
2 MMMil + ( Var(tr(ExMM )B BA (x,)) 11MM + )B IA, (X)))
Finally,
Var X Mi M BB (X
2 R
J B (X ) IA, (X)
IA, (x)
Var (X (A (B-))XX
2 21
11
< M 1 M2 + Var Mi (B2X) (MM(X))AA,X)))) (X))).
It remains to bound the vrace-variance terms. By
for all X, Y E An
v Y|
(EX ]B) < [xxlo -
and
(B tr (Ex BB-YY)))
$ ||Ei flop (I| L2 + | || - Y|IF
Therefore, by Proposition 6 and standard sub-Gaussian variance bounds,
(ax S d d Li d 11 + dl || 18p M oĀ
33

---

(ar(tr(ExMixx ]B) S Ex Li MI 12o + +d M1 o,
and
(BM(((()MM)X)MMXXx)))))) 12x 1 (1I 42 +11 + P I M2
|x 1xppp 1 oh
Finally, by H2.
2P(X E An)
0
2 2oo
1- P(XEA,)
nE nx
since 1 1- PAA,) X exp(-cxn). We also note that H2 forces d n (otherwise Cx would be rank-deficient a.s., yielding P(X E A,) for all 0). Plugging the bound on o2, above into the previous displays gives the stated upper bounds.
Ll
B.3 A deterministic equivalent for Rx (A), with arbitrarly small regularization parameter
We first show that the resolvent map is locally Lipschitz, and in particular Lipschitz An. Lemma 6. Let X1, X2 E RRdxa and let D z Assume that for E {1,2), Aa(Cx, + +D) Then
2
||(Cx, + +D= - (Cx, + D) S
X1 X211F
Vn
Proof. Using -
B-1 = (B B 11 and |AB||E & ||A||op1 Blle,
[Cxx, + +D- (Cx, + +D) D)- |[xx + D)-1((xx)) Cx.) +D)-111
||xx,, + +D) (X,( - X2) + +(X, - xx2)x)) + +D)-"
Using |UV || S |0 and the triangle inequality,
$ 1 (I(Cx, + +D) DX, olp [Cx, + D) llop + 11(Cx, + lop |1(xx, + +D)-=1lop) |X -XelFF
Since Ax,xx +D) c, we have || D)- Sc_ Moreover,
Vn |(xx, DD= Xillop nd / (Cx; +D- X,X, x (Cx, +D)-1 "
1
VallCC, +D) Cx, (Cx, + D)- Vaal(Cx, + +D) s -1/2
where we used Cx, 3 Cx, DD. Plugging these bounds into the previous display yields
[[x, +D -Cx, +D) S Vn
2 11/2
1/2 6 | X211F
2
Xi X2115
Vne
as claimed.
In particular. On A, (X Aa(Ox) 2 n) (take D 0), the map X H (Cx + ATa) is Lipschitz with constant 2/ n(n) 233, for all 2
Define, for any [1, and any matrix D [dddd
(D)
Σx +DD D)
We provide two choices the parameter for which R (D) is deterministic equivalent of R (D). Precisely:
34

---

Proposition 8. Assume X satisfies H6 and for some > 0. Ler B E Radd and let D = 0 be positive semidefinite. Define
a'
++ n
and the unique fixed point of
SD b bb: x
Then, for an absolute constant lo > 0 and all t > 0.
P( P(# - (r(((RX(D) LA, E - (D) 1A,, (x)])) 2t) 2 exp
cx (n Aa( nt?
-
B (1 Na(D) + cx cx/d)
Furthermore, define the polynomial Q 1R R by
Q(X,Y, = (1+UX VX) X + YX + vx and set = Q - >a(DD,, (xxx,, Ex Ex xx nー Then
ạ avd || Pip
B (Rx Rx (D) (D) Ia, (x)
n xx(xx) (1) (D))6
and
Rx (D)) LA, (A, 2 (1+ (1+dd|Exlley n Adxxxx))
9 /d |Ex ll
| Rx (D)
-
x (17 + (D))6)
d |Exllop +
d2 | llsp
e exe
(n Aa (D)) n²
Remark. This result generalizes those of [Cho22]. Firstly, under H2 one may take an arbitrarily small regularization D > 0 and still retain favorable concentration properties for the resolvent (even D 0), secondly we provide fully explicit bounds which allow to understand deeper the dependancies to all the parameters. Our proof follows [Cho22] closely.
Proof. The proof procees two parts, first we derive the claimed concentration bound for terms of the form d tr (B Rxx (D)). which follows from concentration of Lipschitz transformations of X (H 6), as well as Proposition Then we will derive the claimed bias bound, using the Bvermann-Morison formula.
Concentration of dr (B Rx (D)) Ix,(X) map
We mainly rely on Proposition 6, first note that the
An
+ R 1
LB.D
X
d tr (B
is 2 (1) (D)) (D) 1/2d 1/2 Lipsscitt from Lemma 6. Moreover ||/,,||>> S |B 1 (n+ X₂ (D)) we have from Proposition 6 that LB (X))A, (X) is sub Gaussian, with parameter,
| lpp
| O A,)))
of ( S P(X E A2
(n+Aa 3d
(r))a
and, remarking that by definition of given in Proposition 6, since v satisfies H 2, we have,
(P e E))² S
nCX
which implies that
B
B
B B
op
op
CX + (1 + (
nd(n
(D)3
cxn(1+ + >a
cxn(1 (D))3
35

---

hence, using the variance bound for sub Gaussian random variable, we have for universal constant
k.
f'xx (1 + Aa
P ([ (X) E tr (BRx (D)) LA, (X)]] 2 - exp
(-M
B Pp (1) ( cx /d)
First equivalent for E [Rx(D)LA, (X) Recall the notation R (D)
Rx (D) where x
[0, X1, Xn], we have from the Ceeemann-MMorsone formula [SM50],
1 (D) X R Rx()) (D) (X) Rx (D)
] (X,,
(25)
m1++-1xX X Ry (D)x,
hence, multiplying both sides by X1, obtain,
(D)x) 1 (x)
Rx(D)X (X)
LA, (X).
Denoting ax 1 1 n x Rx (D)X11A, (X), simplify the above expression to,
(x) = R (X).
(26)
B We now focus on bounding the bias of Rx (D) (X). First, using the identity A-1 (B A)B-1 we have,
{ [xx(D) (D) Rx (D)) LA, (X)
Σx
Cx ) Rx (D)AA,(X))
=
Rx (D)
a²
Ex
-x,xi Rx (D)
= Rx (D)
ar
Rx(D)ExR (D) 1 Rx())xxx (D) LA, (x))
a-
where, in the last equality, we have used (26). Further rearranging the terms, we get,
[xx(D) (D) Rx (D)} IA,, (x)]
100++(1- -x- R (D)
=E a (R) (
ax
Hence, by applying the triangle inequality to bound the bias, we obtain,
E [xx(D) Rxx (D)) 1A, (x)) ||
s E (D) R (X) Ex (D)
(1
1 1
Rx(D)xxX] (D)
E a- ax
(27)
Controlling each term individualy, first use
||A||
||||| B||F get,
Rx)
Ex D
E [Rx -R)
[ (D) (R)
ar
a*
(BB
From (26),
- (R())())
E
R (x)
n
ax
In order to easily bound the riht-hand side of the previous inequality, we introduce the Lowner order on symetrix matrices. We say that A B if and only if B A is PSD matrix, then have
36

---

ax Ry ( (D) R2 (D) (X)) almost surely. It is clear that this ordering preserved when averaging the matrices, we get
E
R
(D)x, ( 3
ax
and, using the fact that the Frobenius norm is non-decreasing w.r.t. the Lowner order PSD matrices, we deduce,
BB [[xx(D) (D) - R5 (A) (X)]
1
R
( ax
1
E [Ry
(D) (x)]
n
1
$ || [R (D)xx R (D)TA, (x)]
n
VdlEExlan 1lp
(1 + (D))
Plugging the previous computations in (27), we get (D)
E Rx
- Rx (D)) JA, (x) 1|
(28)
( -=- ax
Vd Ex lop
Rx (D (D)LA, (x)
a-
T² + Aa()))²
It remains only to bound the second term in the right hand side of (27), recalling the dual representation of the Frobenius norm,
| sup (r(B A) (A),
| PS PSI
we define for any B of unit Frobenius norm, the random variable CB. R (D)BR ( (X), have
E [11
1
(x Rx (D)I,,
ax
1
1
R (D) (X))
sup
E
Lr
B
|
ax
1
1
sup
E
tr
B
R
(D()xxix (D) (D) (X)
B||==1
ax
sup
BB
a-
To conclude the proof, we use proposition 7 to bound the variances ax as well as {B.x, to bound the above term uniformly over all the possible choices of B. Using the triangle inequality, we have,
ax B < (
E [B.x
+ E
BB
(29)
a-
E [ax]]
[x]]
ax
We further rewrite the first term by remarking that 2 1 almost surely, and similarly a", we get:
( [ax]
E [B.x
E [B..]] Ja" 1 -E [ax]
a*
Now, observe that [E [B.x] may be explicitly controlled by,
Σx
R (D) (D)1A, (X) (x)
|E [C x/a"x=/aa|l
a"
Vd
(30)
11 Aa(D)
37

---

Where we have used the fact that Ex (A)/a" 3 Ta- Secondly, the bias of ax can be bounded using (25) as,
1 (Ex
- ax
(T(xx)xx RF(D))
|a" -F [[x
tr
( - Rx (D)))
= n7 tr
Σxx
Rx
n
1
tr (Ex X Ry
B
tr ((Ex Ry (D)
n²
n²
Ex lop (1 + Aa (D))2n2
Which implies the following bound the first term in (29),
(
1 1 (11 + Aa (D)))
E [G
(31)
az
E
[ax]]
Now dealing with the second term in (29), using the Cauchy-Schwand inequality, as well as E[ax] 2 we have,
1
BB
E
E
[[xx]
ax
CB
=
E [ax - TE (ax])
ax [ax
S V Var (ax) Var (GB,x/ax)
We write (B,x/ax- (SB,X -E [GB.x))//xx EE [GB.]] / /xx and using Var(a + b) S 2 Var(a) 2 Var(b), we have,
Var (CB,x/ax) /xx) S Var ((B,, E [[B. 1)/ /ax) + 2 Var (E (BBB)))aa /ax)
s 2R ((B..x - E [GB, x [x )²]
+ 21E [CB. Var (ax²)
< 2E (GB.x - E [<B.x]] 1)²
+ 2E [<B,]] Var (ax")
< 2 Var(SB,x) + 2F [B. Var(ax))
Furthermore, Var(ax') inf E [(xx' m)?] s E (ax' - E [ax] [ax] yp] I Var(ax), which
follows from ax 2 1 again, we get,
Var (GB.x/ax) s Var Var (SB.x) + 2E [B, Var(ax),
which results in,
[[ E [[ax]
1 ax
CB
< 2 Var (ax) Var (GB,x) + 2E [[ Var (ax)²
(32)
We conclude by bounding Var(ax) and Var(SB.x). using Proposition 7 and the Lipschitz property of X + Rx on A, (which results from Lemma 6), we have,
d dxxxx 1
1
1 c
Var Var(ax)= = no
Var (x, R (A)X (X))
S
n²
(n+ (a)))
(n+ DD())
E|xxx 11ep
1
(1
1
(n + Aa())(())
n²(n + A (D)33
n
Cx
similarly,
Var (GD.x) S R (D) (X)
|x |x R (D) 2
1
(1
1
(n+ + (
(1 A (D) 3
cx
38

---

it results from the two previous upper bounds, as well as (30) and (32), that
1
1
Ex lep [R (D)
lop
1
E
[B
x
1
(n + Aa(DD) (33)
E
[xx]
ax
n11 (D)
n
cx
_| 18p [
-
(n+ (n+ {((D)))>
+
1+
(² + (a))) )
cx
vd Ex 1po ||x
lop
1
|+ )x)) (1) (1+
n(1 (D))3
n
a//8/2 Ex lop
1
(n + b((D))]
+ (n + da
+
|+ cx
Finally, we bound
| (D) and a" by writing
d d|jxillop
a' = 1 + - tr (ExE (D),A,
n(1 + >a()))
and
d
x (Dll 1
+ +A(())
a
1
n
[x ( (D))
+
(34)
a"
x1
A1(2x))
We conclude from (33),
1
1
2
vdl 1d 11
1
1+ 1 (n+ (n+ (n+)aD))) (35)
E
[B
<
+
E
[ax]
ax
nda(Ex (17 + (D))3 3
n
cx
/0/2 llop
1+ 1
(1 (m+))
+
n² (Exx + da (D)
cx
E
(1
(1) ( (m+)a(D)))
+
n² + AD(
cx
d Σx 18
1 (1) (
1
n + DD))
cx
We slighly simplify the previous upper bound by remarking that H2 implies that d < n, hence:
1/2 n3
3/2 n2
Vd n
Using this in (35), we obtain,
1 ax
2 2
vd l
(1+ + 2a)))) n/Ex|lop
1)
(1 + Aa))))
E
+ 1
[[xx
nd (Ex) ) (17 + (D))5
Cx
|Ellop
vdllEx 18
1 Aa(A
1 ox
(n+ (aa))
nda (E (n + (a)()))))
n
vd|lEx 11
(x) + (n()
(1+1)
(1+
-
Ax(Ex)(1 + +a((D))
+
+ (a(())
12 n1|Exxllop
-x/
CX
|E lop
vdleEx11
Aa(D)) + (1+ 1
Ad (
ada +n Aa(5)
n
Cx
Defining the polynomial P1 as:
Pi Z) = x² + x2 + +XX, , p1 Pi( (xxx)
we can rewrite the previous upper bound as,
1
1
E
[B,
(36)
E [xx
ax
11s nda
vØliE
+1+ 1
(Ex (17 + Aa D3 P1
In(n+ + (n(n+A((D)) Aa()
CX
39

---

Plugging (31) and (36) in (29), we get,
1
(D)x (D) (x) (x)]
E
Rx
ax
d3/2
|x 18
Vd lop
+ +1+ -22
Na (D) 32
mAa(Ix)(1 (1) + (D))
(a(n)) Na(D)) (nnn +
cx
vd Σx I8
1
+ +1+ 1
(2x (n + (a())
P1
n + Aa()))
cx
+
12xllop
Where, once again, we have used the fact that d < n from H2.
Finally, from (28), we have,
Rx (D) Rx (D)} 1A, (x)) 11e
Pi (a()+ +1+ ox ) (1) (D)) (xx(Exx)11 + (D))
Vil Ex lapp
VdlIxx 1lp
Aa(Ex) + )((())(+><(())))) |Exxlop
v VdllExll llap
(17 + >a(aaDD))p n
(1 (1 Cx
1
mAx + Aa(
( (
xxx lop
Defining Q as.
(37)
We have shown that:
vdl Σx 1l
E (Rx(D)) Rx (D)} 1A, (x)
ndd(Exx (1 + (D))6 Q(1
: xx,n_=
(38)
This concludes the proof for the first deterministic equivalent.
Second equivalent for E [Rx (D)]
Now, we show that:
B [Rx(D) - Rx (D)) IA,
(x) (x)] ||
d|Ex|lop)
[d|Ex 1lop llop
d2 1 1 (1+ Aa AD()))
$ 1+ nda(Ex))
+
e -xx
Aa +
n
where b* is defined as the only positive solution to equation b 1 + n tr (2xRI (D)) Recall the definition of fD. for any b E [1, oo),
(b( 1 1 tr (IxR'x (D)
For notation simplicity, we introduce g IR defined
q= Q (D). ||Ex 1lpp . ---))
where Q defined in (37).
First, using (38), we have.
E Rx (D) - Rxx (D) AA, (x)]
(39)
E [x) - Rs (D) I (x) + [I R (D) IA (x)]
nda(Ex)(1 + (D))6 + +|13 R [RX
(D) - R (D) (x)]lI
40

---

Then, using the identity A-1 - B = A
(B A)B - we deduce
(D) (D) LA,
P(X e An)
| (D)Ex (D) (40)
a²
3 |a b" || (D)llr/a*
Jaa b"l dd
[xx
Furthermore, we remark that a" is almost a fixed point of fD from the first deterministic equivalent, indeed,
ja" (D(a")l=n" =- ir [x E
Rx (
Rx (DI
Vdl Σx llop
Rx (Rx (X)] - Rx (D)
π2
vd Σx llop
d|IEx llop || (D)
E Rx (D)
(x) |1 +
(1 PPX An))
n
n
Recalling (34), and using H 2, we have,
d Σx lop Rx
(D) [l) - P(X An))
dd|Ex
d² d2 1lop (n (D(
n
Now, using equation (38), we have,
qV 2i 11p
[d|xi|lop 1 11ap
aa - /D(aa)) nda(Ex)(11 (D)) +
exn
Ar D )n?
Furthermore, we show that fo is a contraction mapping around 6*, indeed we have for any b E (c),
ir [Eix [ - R² (Di)) = = n
tr (xxR (D)ER>> (D) b/ 6"
(bD(b) (D(')) n
(La- -DR's (D)
Σx Rx (D)) |6 6-1
n
1
[Xx (D) 16 - b"1
<
ir
n6"
< [D((") -1 [D(6")
6* - b b*1
6 b*1
where in the last line, we have used the fact that 6 the only fixed point of fD. We conclude that fD is contractive around 6*. We conclude on the distance between a' and b* by writing,
ba - 1 n b"1.
la -b((a= (\D((a)) (b((")] Ja" SDD("')
which implies,
aa" bo| S 6"'a" fD(a"))
To conclude the proof, we need to bound b* To this end, write
[ExRx 6" (D) s1+ 1 n
= t (Xx)B(()) s 11+
d d nAx(Ex))
6* = 1 n
which followed from Rx (D) = R (D), we obtain from (40).
E [ (D) - R (D) } LE(X)) ||:
1- d|2ixllop (
qV 1
[ [d[xxllo llop
d x Plop
+
nda(EEx de (D))6
n
(n + (a(D))n?
41

---

Finally, from (39), we have,
B - (D) - Rx (D)} 4E(x))]
I+ 4|Ex|lop mdd(Ex))
gvd
[d|Exxlop
d2 1 lop (1 (D)))) e exn
nda(Ex) (D))6
This concludes the proof.
B.4 Conclusion on the proof of theorem
We leverage proposition 1, to prove that (A) approximates Ex (A). In all this proof, we set X E IRdxn and vj > 0, such that H and H 2 are satisfied. We first recall,
(x =
[x 1
Exli; for X= 0,
and
Ex(A) = to (Rx(A)))) 2(1 2(1)
tr (Rx(0)) LA, (X)+ Ab(A)d tr (Rx(A)) 1 (x
Ad
where
1
b(A) 1 d/n + A/n tr (Rx(A))
We will write A = Ex
Ex (A), and we remark that,
E 2(1 d/n)
2
1 (Ix² Rx(A))
ir (Rxx (x,) + Ab(A)d (Rx()))
Ad
We derive the claimed concentration bound by applying proposition first noting that A is close to the following quantity with high probability,
2(1 d/n) AAx
1 tr (Rx(0)) 1A, (X) + Ab(A)d tr (Rx(A)) = tr (Ex Rx Bx(2)) LA, (X)
Ad
indeed, have for all > O.
P -(X((A)))EE((A)) 2
Furthermore, we show that each term in AE (A) concentrates around its expectation. We have,
2(1 (11)//n) Xd
(Ax - [A)
Ir (Rx(0) lA, (X) - E tr (Rx(0)) lA, (X)]
tr
(Rx (A))
1
1
+ Ad
-E
6(A)
((A)
2
+ E
(ir (Ax(A))Ia,())) - [ur (Rx(A) (A, (x)]
Ab(A)d
+
tr (ΣX²
(A)(
tr (ΣX Rx 1 (x)
42

---

Remarking that 77 > O implies that d < hence, 0 111 d/n S 1, as well as (x 3 X-1 Ia and ((A) 2 I, we bound the various multiplicative term in the previous inequation as,
2 Ad
(A - E x
-
tr (Rx (0)) LA,, (X) - E tr (Rx (0)) LA,, (X)]
tr (Rx 1 ftr (Rx())))) + 2
2A-
|tr (Rx( E|t (R)(I
n
Ad
tr {xX Rx - E द tr (Σx Rx(
2 Ad
tr (Rx (0)) LA, (X) EE tr (Rx (R)( LA,, (x)]l
A + スJ / trr (Rx (A)IA, (X) - [tr (Rx LA,, (x)])
1
ā tr (2Xx) Rx Rx( (X) - EE tr (2x Rx (A)) LA,, (X)]
Hence, from a union bound argument, we have,
(X) - P ((AEx(A) - E[ 21) SP tr - (xx((0)a, At T (41
+ Ir
(x)]) 6(1+~11)
(Rx( - {Xxx(AJA,(x)))) 2
We now control each of these term, by using the concentration statement of proposition every time.
We denote,
n
(t)
max | lopp 1) + cx/d)
Then, Proposition 1 and (41) implies that,
P A (A)
E AE (A)) 2 S KE(A(/6) +e - -E(tt//(6(A+t b)) -EE(13))
for a universal constant 1: > Now remarking that {(At/6) 2 =(t/(6(A+xx1))) we have,
P (|AEx()) E [Ex())]] 2 21 S d(((tmi((1/AAAA").)))
for universal constant k', And, conclude,
P (A) E [x) > exp -K' x (omin(1,1 11 13222
max{[] (op 1)(1 + cx/d]] +exp (-cxn)
(42)
43

---

We now bound E [Ex (A)] to this end, write.
E [Ax = 2(1 - d/n)
2
tr (E [Rx(O)AA, + E
tr (Rxx LA, (Rx((A))
d tr (RX(A
Xd
Ab(AAd
2(1 - -d/n)
2
(r (E [xx [Rx(O) (X)]) + E
(r((Rx(A)Ia, (X))) d ir (rEx'E (Rx)),
Xd
Ab(A)d
Cov 1
+ X 6((A) d tr (Rx LA, (A), (x))
2(1 - d/n) lr (Rx()(0) (0)) + "bb(Aadd ir (RX (N) - -ē ir
2
Xd
Cov ( 1
+ A
6(()) d tr (Rx (1)) LA, (X)
+ (1+ d d|Ex lop
q <v Top ndi (2xx )ra
[d|Exllo llop
d d 12
+
cx
ndi(2xx)
7/22
where the last line followed from applying the second deterministic equivalent presented in Proposi- tion
Recalling the definition of b(A), we have,
2 Cov (
(orA) tr (Rx(2))) 2Xd/n Cov ((x(A))))) - (Rx(2))) b(A)'
1 1
A
Var (21((R((1))
which is controlled using H 1, from the fact that X + d= tr (Rx(A)) 2A (from lemma 6), hence H ensures that d- tr (Rx (A)) is sub Gaussian, and has variance bounded as,
Var ( ( (2
2 A3nd .
which implies,
2(1 -d/n)
(Rx + Ab (A)d
2
(R (2)
[Σx 5 (x)) (((EEN))
EEx(A)] 2
Ad
+ (1+ d|[xx llop nd1 (Ex)
qVd| Σx 1ap nd1 (m))m)
[d]Exxlop
|1 12s
+
c exx
+ A3nd
n
n/2
Now, we remark that by definition 6* 60( is the unique fixed point of fo(b) = 1 + bd/ n, which gives, 60) = (1 - d/n)- hence,
(Ex(A)) S { Xd tr (Ex+) + (b)d ir
(R
(RE
(2))
(xx!RX
(2))
P(XEAA)
ā ir
x
(1+ dI Ex 1lpp
(Vvd] Ex 18p +
d||Ex llop
d d' 11ap
+
e cxx
+ X3nd
ndn (Ex)
nn2
Finally, using the identity
A 1 B-1 A A A)B-1, we get,
Rx (A) Eィ' = =AR (A)Σ*T)
(2)
6 (2)
6*())
we thus conclude on the bias of Ex (A) as,
E AEx [A]] 2 1 d [1pp)l)
( ( Ex 1l.p
[d|
E1|Exxllop
d' sm1
+ 1
nxx(Ex))
c -xn
nd1 (x) 6
2nd
B(m)
44

---

and, merging the previous equation with (42). we get universal constant k, and the function (n) defined above,
( P P((AEx(A) > t+ B())) S (14Ex ++ E (A) S ((AEx(2) E [xx 21)
(-k (-k cxT min ( A + 1
S exp
[ () + cx/dj] + +exp(-cxn)
which terminates the proof of theorem 1.
45

---

C A deterministic equivalent for resolvent matrices of augmented sample covariances
In this section we generalize Proposition to the setting where non-negligible proportion of the dataset is produced by a data-augmentation scheme. We consider the augmented dataset ; G,,,,. Gi.... Gm., where the two blocks [X ..,,,, and [G,,..., G.m]] satisfy H2-H 6. The proof follows the non-augmented case presented in Appendix B.
We begin with the following technical lemma, which will be used to derive concentration for the augmented resolvent matrix Raug (D).
Lemma 7. Assume X and vx satisfy H6 and H4, let f Rddx Raxm IR be Ly-Iispchitz function An Rdxm Then for any X. Y Ay
/ (X, u)x (dg) / 1(Y,))uu x (dg) SL (1 vmLa) |X - Y|1F
ie, X + f g(X
( 8m (dg) is L + LG) Lispchitz on An
Proof. Using HI and H4, we have
/ʃ f(X, 9)x (m (dg) / f(Y (dg)
Rom (dg)
1 ((X,g)/ g)v (dg) - f(Y.)))))) Sm (dg) f(Y, g)u 9))x"" / 9(X,g)uz="dd)
< Ly |X LyWi (uSm TT)
< Ly |X Yllp + LLV Y/1F
Ly (1+ VmLG) |X - -X-Yl
Where the last upper bound followed from H 4.
We further recall the following notation for any positive semi-definite matrix E [gdxd and two dilation factors a₂ and ag.
(D) (CAuR + - (11-a)Cr- + aCo +D)
and,
(a) Rug
R
(D)
1 (1
3/ag )a
-1 Σx Ao D)
a₂
where AG E [A](
We prove the following result, Theorem 4, Assume that H to H6 hold. Let B E Rdxd, and let D be a positive semi-definite matrix. We define (a ag) as,
a- 1+ 1- (1- tr EE [Aug ())AA(())) a-= = =1=1+0 m
tr (E 1BCxx + +Ao(X)) Raug (D)AA, (x)))
Then, we have for universal constant k,
d Ir (B [RAug (D)IA, - [RAng (D)1a, (x)]1) 21)
P
n(u + Aa
< 2 2exp
(-h (1 (1
46

---

And.
RAug (D) -R ( (D)} IA,, (x)
(N11 + +22) 10 Σx 1öp + x²)) + + Ex n -111/-
24
n a)n + Ad (D)
aB(1 a1)--a1-++11 o3 / lop
vd
+n+m m (1 + u(n)) + vn + VaLG (1 (1+6)
xx cx -1/2 / (x
(1-a)m + Aa(D) (17 (D)))3/mm
a0(1 a3(1-a)) avd
1 / Ad I [[ - dGlle] v Aa()) Vala+
(1 (1- 1-n AD( (17 + Ad (D))33/m
|
n
E (X) - AGlIF
@3v Eev
((1 a0) (D)) a- ndd(Ex) + (DD(1( (1)() a¹))
where a' = ax/ ag q1, 92 and q3 are polynomials in rj + (z( Ad(xx), [Exlla ,xt and
n
Proof. Following the proof of proposition 1, we consider only the simpler case of ox (the general case readily follows by considering X/ and G/ax.) we prove the two statements of the theorem independantly. First focusing on the concentration of d' tr (B RAng (D)).
Proof of the concentration inequality.
Let B Rdxd be any squared matrix, for notation simplicity we will denote hB X,G + d' tr (B RX)G(D)) lA, (X) as well as X = X UG (for Li being the column-wiss wise concatenation operator), so that simply need bound the cumulative probality function of hx(()) Ebhn (X). To do so, we first bound its moment generating function, for any scalar s E I,
exp 8 (BB(X) -E (x)())))]
= E exp (s (bB(()) E (x)())) xx})) cxp (s { (xB(() x] - E [bs())))))
= E B exp (8 (x())(() -E /BB( (8) x }}] x]] exp (s (xB(X) xx] (x) [x}{
Note that the random function G ln (X L G) is almost surely 2 Aa(D))-3/2 3/22 Lisphiitt A, from Lemma 6, hence, relying on the -i-Lipschitz concentration property G conditionally to X, and applying Proposition 6, we get
2|| [Bop + 1
exp (s (nB(1)) [he xx}) x] S exp (-csto8 {
<exp
m)d(n++ (D))3 + |IABBlBco
Finally, remarking that under H2, have R, S n1, well using we have,
|1/B|1/0 S (n +1
E exp (s (x)( (E (X) xx]}]] < exp
-cssoo
(n 1n+m)d(( + (D) n(n + (a
exp
-cs²
od 11-a
+ +n
n( (a))))))))
d
Now, we will leverage Proposition to bound the remaining term, writting E (xb((X) x] = ØB mB)),,,,(X) (X), where for any X E Any.
/ 2 tr (BRxug (D)) du du (m
(X)
We know from Lemma 7 that JB is Lgn Lispchitz on Ay, with Lgn = 2(1 + /mLa) (n 1) + -3/2) Hence, using Proposition 6, prove the existence of a numerical
47

---

constant e, such the following bound holds,
IE [exp (s (9B(X)LA,, E (X S exp (-o2s² (1+ + )
d(n +
(1 u {a)))²
Putting the previous bounds all together, we have shown that the moment generating function of (X) is bounded for universal constant c by.
E exp (s (bB(X)
(X)
E [bB(x)}}) (1 )
I exp
-cs² d(n + (1) + Aa(D))3
o n(n - (D))
1-a + (
= exp
(-os² ml + (D)33
a
d (1 + vmla)) + (1
a)oz
+ + +
Aa(()+)a(D)))) M(D)))
d
Relying on the Chernoff's bound, and usual computations, the claimed concentration bound follows. A first equivalent for E [RAn (D) (X)]-
We now focus on the bias of RAng ( (X). We will show that (a Aug
(D) is close to
[RAng (,, (X)]-
As a first step, let us notice that conditionally to X, G satisfies all the assumptions of Proposition 8, hence for any a (X)-measuaable matrix Dx. RG(Dx) admist deterministic equivalent conditionally
to X. We will through a slight abuse of notation denote (x) (Dx) the equivalent of (Dxxx)
conditionally to X. It is given by Proposition 8, i.e.
E Caa X]
1x) = ( 30x Ao(X)
(x) G (Dx) =
+ Dx
+ Dx 1n, (x),
ag(X))
(x(X) xx(X)
(x) = ++ m
tr (E [Co ([ x])
=1 m
tr (13Cx Ac( (Dx) XX]
Writting for simplicity, a' = (1 - 3/az)a, a, and a (x) = (1 3Xay(X))a, we will rely on the following upper bound which follows from the triangle inequality,
E RAug (D) - R (a)
(D)} LA, (x)
Aug
E
RAug (D) - - G|X
1
(2)(X)
(1-00x
(a Cx +
I IA (x))
a
+
E
a
R
(X)
(1=aCx+ Cx+ ())
1 1-a
a
a
l-a
1
Rx (a1 año
(1-00aa3
+ 1 111 D
1
1 (x)
1
ado + I- 1
(D) LA (x)
+
[
Rx
a'-aa)
D
Aug
F
and, remark that we can rewrite,
1
(1--) Cx + -
RAug (D) = ((1- xx + aCo + +D)
Rg
a
a
1 Ra,()) Cx + ID) I (X) =
1 (1-a
E
E
X]
+ 1 1-a
Cx =x+++D) 1x)
a Gix
a
a
a (x(X)
a
(1 (1-
B
ado(x)
-1
(x(X) a Cx
+D)
In (X)
ag(X)
(1 a' (X)) + ado(X)
+D) 1,,
ag (x)
48

---

1 a- Rx
aña
1 D
D I,, = (1'x''
aña D
Inn
a')ag
og
and.
R ( (D) (X) R ( aT-
año
1 "1- +I-aD) Lnn (X).
1
Aug
Using these equalities, we rewrite the previous bound as,
E
RAug (D) - -RAuu Aug
(D)} LA (x)]]
(43)
(1 [xx + DD)
1 (2,
1-a Cx -x= _ 1n, (x)(
<
E
Rc
Roi
a
a
(Xx) aAa(X) +D)
-(1-- año +D)
+
E
(1
1An (X)
(X)
ag
1 a Rx
Toda
+ +1-a
I- - R ( ado
1
(1-00) + '1-a' (aa))
1n, [x, (X)
+
The first and third terms in (43) are bounded by Proposition 8, whereas the second term is controlled from the fact that ag( (X) and Ax(X) have small deviations. We deal with each of the terms in the right hand side of the previous upper bound one by one, first using the Jensen's 's inequality,
(1
cx a
+ -'D)
1 Bax(x)
+ (1=00x 1x Cx+
2D))
||=
E
RG
Ia, (x)
a
a
a
RG
(1 (x=
+ a
+2D
-RG
RG (2x(x)
(1-20x Ox + D
x
LA, (x))
a
a
Remarking that for all E An, we have (a((1-a//CCs +D/a) 2 a - '(1 a) Aa We set (1 a)n/aa + (D)//a we have from the previous remark and using proposition 8,
-
(1 Cx
+'D)
1 D
1
Raa(x)
1 (1-ncx
Cx + a 1.D)} 1 (x)
RG
Gix
a
a
a
a
a
1
(1 (1-
+ .DD)
("-00x, Ox + 1 _ ) x
RG
1 AA, (X)
a
a
VallE [Ca X] |
24
X X111op, 0,
lop
IA, (X)
nAa(E [Co
X])c6
where Q is the polynomial function defined in Proposition 8. In order to integrate the above error over the distribution of X, one needs to ensure that this random quantity doesn't blow up. We deal with this, first by using the fact that Q is non-decreasing with respect to it's third entry, and we recall the notation Ks such that,
Sp)Aa(X)) C [ [k] a.s. X] llop 2 infx (X)))X))loo 2 K, we write,
and using |E [Cg
Q(e,Aa(B | XJ), ||I [Ca
X] I|ا 0, 11 < Q( Aa X]), (infx [AAo(X)))))) 0, < < (B x]), K,0,,
and, remarking that there exists two polwnomials 41 and da (polynomials in e, K, k, such that, (c,, (TE [Co X]), K. 0, = 9 + (F X])92. which is trivial from the definition of Q in Proposition 1. We write,
VallE [Ca |X]
E
Q(e,
Xl), |E |Co
X] Il O,
LA, (x)
nAa(E [Ca X]]e
E CG X]
3
dE [|| [Ca | X] 1 LA,, (X)]
E
lop
1A, (X)
92
nAda [E [C X])
6
49

---

and, we control the remaining (E Ce XI) term by remarking that Aa [CG X() = Aa + (x))) 2 infx (X)) 2 K hence,
VdliE CC nda ( [C
X] 13
Q(e,A X)), | [Ca X] 1lop 0,n
(x)
x))
v dE
[| Ca
X]
llop (X)
((q] + (2)
ne
remains only to control the term E ||E Ca X]
llop lA, (X)]. Recall from H3 that [Co |X] =
3Cx + (x)),, which thanks to b)s S a² + implies.
E
| [Co X] lop An (x)] $ LE [||x -xx + 11 + Ao (X)
B [||Cx Σx + |0 ll + n².
hence,
(1 (1-aa(x
-D
1 (X,(X)
1 1 a Cx + ] dA (x) (x0
Fla Rg
a
a
+
a
a
RG
G|X
a
(44)
Vdoe (B3T
[1|xx
Σx op +
Σx 1 +
2 (nqq + 92)
nae
remains only to handle the deviation of Cx in operator norm. To this end, we rely on [Ver18] result 9.2.5, which states that for a universal constant K,
(v****
P 1I Exllop 2 Ko
r + 24
|2ix|lop
S 2e
tr (Ex)
Σx lop
Note that [Ver18] states this result in the case of X having sub-Gaussian columns, which in our setting is direct consequence of Definition 1. In particular, write,
(V*t"
r r
1
1 +- n
(u( = Ko
[Exllop-
thus ('(u) =Ko's
KoKs m//(r+ +
12x llop
and, by the change of variable p(u), we have,
E |IIxx 1xpp
P(I|Cx Exllop 2 1) dt /- P([|Cx Exllop 2 1113) de
P(|CX - Exllop 2 p(u)) ((((u) (()) du
$ 2 e " (3)((u) (((u) du I 66'(0) / E p(u) du
K20t 1o --- 12 (0) K208 f e- u)²
S 60)(0)
n²
1 2Vr
(x++t) +²)
(r+1 +
2(r 2r + 2)
I 6
n
n²
recalling that r- -t (xxrrxxx//l)) E1 lup. and noticing dAd (xx llop S S d, it results that
[Exlop + (nx)
1
dd+1
d2 + d
E [[|Cx - Ex(1pp] S 10
n
2
1Exllop + (nx))(Ex)
1
012
n
50

---

where we have used d < n, garenteed by H2. We plug this into (44), and we get,
Rs
(1-a)Cx
- +
1
Ray())
(1-0xx
Ox+ + -22/))
Ox
[x,
(45)
a
a
a
Vdog | [x
+ x2)
Vila
1Exxlop
111
S (nqq + (2)
nac
naE
(iidAs(2xx)
11
(k9) + (2) v2 (og (3
Σx 18 + n²)) + x |
Eo 11/2
nac
21 (nq + +2 (o)
Σx 1ip + R²) o |I loppllopaaaAAA
nl(1 - a)7 + (D)
This concludes our analysis of the first term in (43). We now focus on the second term in Equation (43),
which is controlled, provided IE [X] AGlle] is small. First, we check that,
ax(X) = + tr (180x + Ac(X)) Ra ((1 - ([1a)xxx++D/oa x))
m
-1 + (180x + Ao(x)) ((1 a) + aC + +D x)
m
([3Cx + Aa(X)) Rang (D) X])
m
From this, one can hope that ag (X) concentrates around az E [a, hence, we write,
(1 (1-'( ado(X) +D) +D)²
- - (111 (11-a')xx a') + adG
E
+ +D)
Jn 11,
Xx(X)
a
F
E
(1 (1- ado(X)
+ +D) -(1- + ado(X)
-1
+D)
IA (x)
(x(
(x
[1-oo00x++
aAo(X) (x(
+D) -1
- -11
+ ado
+ +D) -01 1n, (x)) og
+
E
+
furthermore, relying on the identity A 1- B B-1, we write,
E
(1-o((X)) ado(X)
+ +D)
-D)² (n-a))xx aAc(X)
+ +D)
(x,
(x(X)
az(X)
E
(a'(x) - d') { (1- ado(X)
-a')
+D)
Cx (1--o) + ado(x)
+D)
1a (x) (x)
ax(X)
ax(X)
[x((x all (1-o(x)) + ano(X)
-1
Cx (1 (1-a')xx + ado(X)
-1
+ D))
+ +D
(x)
ax(x)
ax(X)
Now, remarking that
|0x (1- (u-d)ox + aAo(X)
-1
+D
1a, (X) < 1- a
ax(x)
op
and,
(1- (1= Ao(X)
-1
1
(x( +D)
1A, (X) 1
(1 a((X))n Aa(D)
(1 (1-a) Aa(D)
op
51

---

Similarly,
(1 - d')xx + ado(x)
+D) - (1- + ada
+D) -1
} AA, (x)
E
(X)
ag
|F
1
( (1 (1- + ado(x) +D) Ao(x) (1- - ado 0g
<
alE
a')
+ D
lA,
xx(X)
ag(X)
(1_a')0x + aAo(x) +D) (Ao(x) -do (1- + ado(X)
+ E
+ D
0g
(x
(x(
E (X)
aill
E [X] - AGlLF]
a)n + X1 (D)
((1-a)) Ao (D))2*
which results in
{(0-- (10-0(X)) + aAo(X)
+ -D) -)² - (1- + ado(X)
-1
-1
E
Xx(X) +D)
1 A. ((X6)
(x(
E [lla'(X) - a'll a')-1
(1 a)n + A1 + E [IAa(() AGlIF]
E (X) -011
+
- (1- 7d
((1-a)n + >a()))²
aBE (X) - ai (1 - a')-
E (X) -i [ - Aclle
+ (1 aan+ + (D) ((1 2)n + 2D))
a1-a)n++ (D)
(05(1-a')-1 E (X) [ +
E (X) - AGllF]
$ (1- +a
- ((1-a)n Ao
From the previous, one can see that controlling E [X - Aalle) and E [Xa,(X) agll is sufficient in order control the second term in decomposition (43). While the first needs to be assumed small, we can show that E [Xa - -ayll is small under quite general conditions, to this end, we write,
,,
03
tr [ Cx RAug (D)1A, (X) X| - E |Cx Raug (D) lA, (x)])
tr E [X)(X) Rang D) LA, (X) x] - E [Ao(X) R Ang (D) (),,,
a
tr (H [x.XT RAug (D) A, (X) x] E [ Rang (D) A, (x)])
mn
a tr (E [Aa(X) Rang (D) (X) x] - E [Aa(X) Rang (D) (x)])
Now remark that the distribution of tr (B X Raug (A) x] E X RAug (A)]) doesn't 't depend on i by exchangcability of the columns of X and H5, we thus focus only on the term = 1, by writting,
a,3 E E
E (X) - a;ll s
X Rang (D) (X) | x EE [X] Raug (D) (X)]
m
a
[t (E [Aa (X) Rang 1D) A. (X) X] - E [Xa(X) Ra (D) (X)])
m
0.3
E || [X] Rang (D) (X) x | Raug (D) (X)]
171
E [| |r ((Ac(X) - Ar [RAug (D)
x 1A, (X) - E [[AG - Act Raug (D)LA,
m
[[t (Ao (RAng (D)
X 1 A
X)) E [ (D) (x)]))
where the last inequality followed from using the triangle inequality. To bound the above quantity. we first focus on the second and third terms, which are notably less technical, it holds from Cauchy-
52

---

Schwarz inequality and remarking that RAug (D))AA, (X)Ile S vd(n + AdD) -1 that
E trr ((Ac(X) AG JE [Raug (D) X] AA, (X) - [[AG(X) Ac) RAug (X)])((X)))
m
avd 22 m(n m(n + (D))
E [[IAa(X) - AGllr]
(m) Furthermore, the function X tr (Ao Rxin (D)) du (g) is Acdloolllopl + vmLa)
(((D))3/2()) + m) - Lipsshhhhh from lemma and lemma 7. Hence, we have that EAgE Raug (D) X]) 1A, is uub-Gaussian (which follows from HIl and proposition 6), and
we have,
E [|t (Ao (E RAug (D) X] 1A, (X) E (D)LA, [X)]
m
V Var(tr [RAuE (D)
x]) LA, (X))
m
VdIAAcllopL + vmLa)
dlAAcllop oAn
24 m
Aa m)
1 7 +o(a)
Recalling that AT S n- from H2, and using that (which also follows from H2), we simplify the previous bound
a E tr (Aa(E [Raug (D) X] LA., (X) ( (D) (x)]1)
m
avd Acllo
(1+ VmLG
1 n (aD)
Avdoo
|Valo + 1 / Aa(
Vn+mm +
(1) + (D)
(11 + (D)))3/2m
/n
Plugging the previous calculation back into (C), we find,
E [X) - a7ll s ag E [ [XT RA (D)XIIA, (X) X] - -B [x] Raug (Magg()XX 1I) (X)](7)
Adllo
E [IIA(( - [a]lp] V Aa(D)
VoLe + 1+ -n Aa(D)
(n + (D))33mm
|
n
It remains only to bound the expected deviation of E [X] Raug (D)1A, (X) x). Using the coammann-morisoon 's formula, we first write,
1 Rx (D)x,Xi ( Rx (()x
X RAug 1A) (X)
X Rx-uo
n m 1 (n+ Rx (D-u,(D)x, ] 1x,(X)
X1 Rx uG (D)X;
I+ (n m 1)-mm)1p Xx Rx (D)x (X)
(n + m)
= (n + m)
1x,
1 (n + m Rx-uo (D)X,
hence, writting / (n + m)/(1111111 (n -x) (note that is I-Lipschitz), we have,
E [X] (AnRRADDD)) (D)XI x] (n (n+m)) mm+ A.,) E [[( Rx (D)
(X) X
53

---

which allows to rewrite.
[X] Rang ( x] = (I+ m) -) S(XT (x- (du un, (x)
=] (X) - (X
Rx B (D) - 1 (()
+ +/IXTT [(x)
= (x0+ - RX-1n (D)X Idu X (0m
-(f Rx Rx-uy -( (I) - (fxT R (x ))
+ +ʃ F(XT Rx un (x)d11 x {g),
which ensures,
E IE [X] RAIR (A)XI (X) X] E EXT RA LA)X
(48)
Xi Rx (D) X1 (o) IA, (x)- =x(r (xxī Rx (D)
$
E
f
R X1 de de (0)
1An (X)
/ f(XT Rx ug (I) (X) du TTm (g) r/ Xi Bx Rx uy (D) (D) 6. (و) LA, (x0
E
/// [(X) Rx ug (D) (X, - x Hol
E
and we once again bound each term in the previous upper bound (48), starting with the last term,
we notice that the function G / [(X (X) (X)X)) is 2X7 X1 (x()) (n2 m)-1//2 from Lemma 6 (almsot surely). Hence, using H5, we have,
E /// s(T Rx- (D) (1) IA,
E XT]
1A, (X) (X) d K0m - -x HD)
+ Na (D) )3/2 + m)112 u(n)
tr (Ex)
(D)) (n + m 1/2 1/2 u())
Furthermore, using the Jensen's 's inequality, we have.
/ʃ [(X] (xx du x (g) s1/ X, x1] Rx-111 du d (0)) IA, (x0]
E
| Rx Lo (i) - 11/ X Rx uy (D) X1 du dv @m (m)) du d (g)
< E
E [lx(xiiT (Rx-u,(D) / R (D) (D) dm)))))))))) du (o)
Relying on the -ipLschht concentration property of &mm, we can bound the previous term using the fact that G + ir XX RX-LG (D)) is Lipschitz (from Lemma 6). We get,
1 s(X] (x) du Sm (g) 1// Xi (D) du [x,
E [ X1]
(rxxx
nn (D))3//2 (n m)/1/2 (n (D))3(D)) + 1/1
54

---

Now, focusing on the first term in (48), we write using the Jensen's 's inequality as well as leveraging the Lipschitz property of
r (1 Xi Rx ug (D) X1 du 1m (0) LA, (A) - E -x {[ (/ Xi Rx ug (D) di 1A,
E
s (ʃ
c0 x- (0) (X) - ((()
E [ Xi Rx Rx (D) X1 du mmm (0l) IY (x)))
E
X Rx
( X1
|
X1 E f Xi Rx (D) X1 du 0m (01) LA, (X) E (fxx Rx Rx- (D) X1 du dxxxx (0) dA, (x))
+ E
/./
Rxx Un (D) dn (X) - / X Rx Un (D) du
- 18
x
d (g) (X)
X Rx-1 (D) X) du (2) - - Xi Rx-1x (D) X1 du xm (g)
+
E
E
V Var [xT]
/ (Rdd (X)x1
Now, we remark that I Rx-1n (D) (X) is o(X-) measureable, our Proposition applies, and get,
Var (xT RX-LRL (D)- s {
{
(1 + vmLc)²
1 1 cx
+ (11 (m)))
(17 da (D))2
Which implies,
| (fxT [XTRX--IN (D) Bx-igg X1 du (0) 1A, (X) (X) -E(r (ʃ Rx- ( 1 (x)
x Ex|lox {
(1 + /mLG)
1 cx 1/2 (1 aa
+
(a()) / +
Putting all these bounds together, and plugging them back in (48), we find that,
E XT Ra
(D)Xi (X) X| - IE XI RAug I (X)]
(1 /mLG)
1 1/2
S Vdl lop
(n + (D) 3/2 3/2333/2+/// +
( Na(1)
tr (Ex)
(1 u(n))
(1 Aa(D))3322 + +m)
V llop (1 (n+>a
Vd
<
(1 + u(n)
Vn + m VOLG + (1 (1+0x)) ( Na()
Vv + mm
We conclude on the second term in (43) by plugging the above bound into (47),
a:3/d Ex llop
Vd
E [[ay(X) a;
Vn v + (1 + u(n))
+ VALG (1 (1+ Ax
(17 + >2 (3))3/mm
Vn + m
av d Acllop
(X) - AGllE] Ad(D + VaLa + 1 +
nn (3)333mm
||AGllop
Vn.
55

---

Hence, using (46), we have,
E
(1 (1- + ado(x)
+ +D)
-1
(1-
ado(X)
ax(x) +D)
IA, (A9)
xx(x)
FF
2 a:(11 - a0)--+))+++ aBVd|
Vd
Vn m (1 + u())) Vn+ + VaLa + (1 +xx 1113) v n Ad(D)
(1-a) + +a (D) (17
Ap (D) 33/2m
a3(1-a)) - +1 avd|AAGla
E [[IAa(X) - AGlle] Ad(D)
+ VOLG + 1+
+ (1-a)n AD( (17 + Aa (D))3/2m
A
vn
E ( - AGILE
(11 a)n ²D))²
Which conclude our analysis of the second term in (43).
Finally, we turn to the third and final term in (43), which is controlled using Proposition 8. First note that (a(a:///aj + D/(1 - a')) (D() a'), hence Proposition 8 ensures that there exists constant that depends polynomially on .... such that,
a Rx
aaaa ag
1)
a¹ D)
Ro: ( αλo + +1-2D) In,
(x) (10)
1 a' (1 a')a
43 [5x 1
a' ndd((x) + >a (D))((1
Now putting our computations all together, in particular plugging (45), (49) and (50), in (43) we have shown,
{ RAug (D) R Aug
(D) IA, (x)]
(Kq) + Vd (33) (338
Σx 13 + +33 + o 1 1 Xxxxxxx(((((
21
n((1 (() + (D))6
a -3(1- a. a.vdllEx lop + (1-a)m + AD(D) (17 + (D))332m
Vn+ (1 + u(n) + Vn+m + VOLa + +1+ cx 11/2 / V Ao(A
Vd.
1
-8(1-a0)-+1 avd olp
E2 [II - AAllr] /n+Aaa
VaLa + 1+ +
(1- (D) (17 + Aa 3D))33mmm
|Aellop
Vn
E (X) - AGIle]
g3 d Σx
(11
1- a' nda(2'x + A, (D) a
56

---

To simplify the above upper bound, we use the fact that 1 - a' 2 1- a S 1 as well as d < n, which yields,
RAug (D) R Aug (1 (D)} I.,, (x)]]|
2/ (mq) + 92) Vi (B8 Σx lipp + n²) +
nl(1 a)1 + Ad (D)
+ a,((1 - a) +1 a5 / lop
(1 + u())) + VOLa + (1 (1+18/2)) ) + (DD)
(1-a)n + AD( (17 + Ad (D))
+1 avd| Acllop
E [|) Acllel Aa(D VaLa + 1 +
+ (1-a)n (D) (17 + (D)))33/2m
A
vn
E (|I AGILF] (1-a)n+ + Ax + ndd(Ex)(( - a)n + (D))6
(1-a) 93
1x 11op
ndd(Ex)( a0) + Ao (D) 6 (NiqI + 92) (M((EX) + d(B3lsxx 18p + +x3)
(80 1lip + n²))
0 Σx llop
a
aBvd( Ex 1x 1lop + 93 AG Acloop)
{1++ u(n) + Vala+ + (1 (1 x23 vn+
+1
I a
a1-a)m + An D 5m/2m
a
+1)
1 (11 + A2 (D)2 (1-a)y (1-aay=>(())77? xz(D))5/2m
aBvd
E [IAa6(X) -clll)
a
57

---

D Proof of theorem 2
This section this Appendix details the proof of theorem 2. First recall the definition of Exug (A), for all À > 0:
( (1 (1-d/1) d/n)
[aAc(X)
-1 tAla
tr [x(
Ia, (X),
d
(x(X)
(51)
+ ATd )1)
1 - (1 - 3/ ag (X))a
((a,(x)) (2,
2 (X)
tr
da.((X
az(X)
Where we have used the three notations,
ag (X) 1+ - (1 1--11///ag/ B\a, Xi Rx- du 8m (1) 11)
n
(52)
(x) = 1 a tr m
(18x++Adk)) +o(2x)) / Rxu (0)
and, for any 1,
R G (1, (1 (1- a + Als) )
Finally, we set,
1 EAug(A) (A) = j (RAug(A)3) - + j tr (xx²)
1
Firstly, appendix D.1 we detail the concentration of (X) and (X) defined in (52). Secondly, in appendix D.2, we show that 4 (X) and (x(X) (defined in (51)) essencially have sub-Exponential tail, we provide an upper bound on their sub-Exponential norm. We then conclude on the proof of theorem in the last part of the Appendix.
D.1 Concentration of ag (X) and ag (X)
Proposition 9. Assume that X and G satisfy assumptions HI to H2, Let ag and a (X) defined as in (52), we set,
2²2
X²4
At
(t) = min
Xt,
LoVVLo 1//n m)² So
a)
B (lop
X212 M +
Vx31
23 + m))22
In(n)
(t) min
82 p u(n))2² BloG + u(n))' a² (LA/VA+ VoxLo k// 1//n++
m
as well as
8g = a3
4(Ga + u(n))tt(Ex))
(1+
m
m
(23(+
|Ex(llop Vn
(2(nn)
tr tr(Ex)
8, 8y +
+
X3/2
A(n + m)
then the following holds for a universal constant c >
P ((a,(X) - ag 2 + 5z) S exp (-c(n + m))
and,
PP (X) a 1 2xt (x + m)
58

---

Proof. We first recall that À > 0 and from (52),
033 ag (x) ++ and from Theorem 4,
tr (Cx (RAug (A) X]) + m
tr (Ac(X)E [Raug (2) x1)
m
a 0 - tr [Ex Raug (A]]) tr (E (A)g(A)))
we can thus write.
(X)
(53)
a/3
tr (E RAug (A) X| - E RAug (A)I) + tr (E)) Raug (2) x - E (X) Raug (A)Di
m
a
(E [XXX]] RAng(A) 1 X] - E [X Rang (A)][
mn
tr (E (X) RAug (A) X] (X) Ra (AJ))
Now remark that the distribution of [tr (E XxxX RAug(A) (A) | X - E I RAug (A))) doesn't
depend on by exchangeability of the columns of X, we thus focus only on the term = 1. Using the Shermann- morisson's Shermann-morisson'ss formula, we have,
1 XI Lx X Rx- uo- (A) X, Raug (A) XT Rx uG (A)x1 n n+ m
1+ (n + m)- Rx-uG X1
X1 XiRx-uc X1
1+ (n + m)
-Xx (x-ix
(n + m)
mm+m)
1+ (n + m) - Rx (A)
hence, writting ʃ : x + (n + m)/(1 (1 + (n + (1++m)=-p) -))-)) (note that f is I-Lipschitz), we have,
E [ (A) x] = (n m) E [f(X] (x- X
In order to derive the concentration of E [X] (A) X]. we mostly rely on the use of the Hanson- Hanson-Wright inequality, which applies to quadratic forms of the shape x, M(X))x, with M(X- being a (X-) measureable random matrix. To this end, we show that
E [ RAug (A)x2 X] is close to being of this form. We have,
E [X] Raug (A)Xi x] = (n + m) - f s(XT (X)
1 5(XT (N) (t
(n + m)
+ / f(xT (xx tcm 1 (()
= (n =m) -f (xx]Rxx Rx Ru- (A) 60m (g)
- ([F Rx un (A))))) - (ʃ
X Rx up (A)
+ / (A) 1x 200 (9))
Similarly, we write.
m) E [ Rx (A)xi] = (n m) - S (R. (R I Xi Rx (A) [/TTA-L((AAXIddd000000 )
S(X) Rx (d) (m)) -s E
X__ Rx ug (AX
E
+ B [ [XXT Rx 1x ~x ((a)
59

---

which ensures,
TE [X] RAug(A) | x] -B [X] RAug (1)x1]
= f xi Rx un (d)) (0) - -11 E / X1 Rx up (X)
+ /s 5(XT Rx- ddu T (g) f f (s
Xi ( (0)
+ E // F(X) Bxx uR (d)x)) @m (g) f
E Xi Rx ug ( 6TH (g) 1)
X
+ / 5(X) Rx Rx (A) xX xm (o)
[ 5(X) Rx (A) - -
+
Now, using the Jensen's 's inequality, as well the 1-Lispchtiz property of f. the previous equation implies,
E
[ T RAug (A)x, x] B [ RAug (A)x3]
Rx- Rx-uu(A)dd XT (g)Xx - ir (xx Ex / Rx (2)d @m
xT
+ / tr X (RX-ug(A) - / R (X)d 3mm (0) }) du dup"(o) (g)
+ E / ar (xixi ( -B /RxxLo(()dde7700)
9Th
|}) de dm
+ // S(X) RX-L Sm xx ((0 m
E [ 5(x) Rx- (A)xi)d(u Sm - (e)
To bound the above, first remark that the map g: : XUG (X Rx uG) is 2 1
m) 1/2 conditionally on X1 (as a consequence of lemma 6), we have from HB, that x Rx (1) is sub-Gaussian conditionally to X, for S and from the moment bounds for sub-Gaussian random variables,
{ (RX-LO(A)- - / Rx Rx-un Sem (0)
tr XixX
de du (g)
$ / tr (XxxI { (RX uo( - / Rx ug (A)d (0) })) 2
du (g)
2xxXTX1
V (x +m)
Similarly, and using a triangle inequality, we have,
X,XX { Rx- -E tr
[ (d-- s0m
E
de x. (o)
/ tr [xix]]
[ B
aaS (ox-uo())oo Sm (0) 1}) du @m (0)
E
20 [X
(n + m)
and, using Lemma 7, we have that and the variance bound for sub-Gaussian random variables, we have,
E S tr (xixT { (A)- - E [s Rx Ex-uu(()dde X (0)
1)) de (0)
2(1 + VmLc) + 20 [X] xi]
2(1 VmLG) + 20 (Ex)
VA8(n + m)
v 1²3(n + m)
60

---

Furthermore, using H4, and recalling that G + f (X is 12 3/2 + m) 1/2. 11/2 Lispchitz, the two final terms are bounded as,
IX (ox)))))))) (O))
2 1/ 33-3/2(n m)) 1/22 (uxTT --²)
2 | 3/ (n + mm
-1/2 m
and,
E [ (xx] Rx
Bax-ught ug (A)x)) - - [10
s 2tr xEx)
Merging all these together, we have shown,
E [ Raug (1)x2 x] [ R Rang (A)X1]
/ xi Rx- (A) (g) E I Xx] Xx Rx-Lg ( du Xm (g)
2x, Xi
2 21r
2(1 + La)
+ (oa + an((n))
+ (oa + uu(n)
(n n + m))
v (n +
V + m)
XI / [ (A)de R0 1 -tr (xxx (x) (0)
+ 2(0G u(n))
4(0G + u(n))) to (Ex)
2(1 + LG)
x1 X1 - ir (Ex)
V23(n + m)
VAa(n +m) m)
VAa(n m)
Finally, putting back the previous upper bound in (53), we have,
a
(x) - a5و5
tr (E
X (x)
X] E [ Rx(A)))
Tum
20 + ((n))
4aB(aa + u(n)) tr (Ex) + 2a + Lc)
Σ XxxX - ir (Ex))
V (n m)mm
A + mmmm
at tr (E RAug
(Aug()) x]
(Ang())
Applying a union bound, we have,
P (x)(X) - agg22+ as AloG + tr
(1+ + La) (1+
(54)
V
/A + m))
(xx [x]] / Rx (x-ug (g) - tr Σx
(x (8)
mt
< nP
2
3a,
[xxx] - tr (Ex) A + mJmt
+ nP
6ag(oG + u(n))
(AGG(EX)
X]) [tr (Aa(X) Raug (A))
mt
3o
We now bound each term that appears in the left side of the previous equation. beginning with the third term, remark that the function X + ir (Ac(X) ʃ Rx in (A)ddxx.m (g)) is Lipschitz, and,
P [r (AG(X) RAng (A) |X] E (X) RAng (A))) 2 mt
=P =P(1(X)-EBtt -b(x)) mt
3a
3x
61

---

indeed, writting for X, Y E Rx
1 9(Y) < Ir (Ao(x)-Ao(X))) Ao(Y)) / Rx (2) dexom(())
tr ( (AoDo) ()) / (Y durssm (0) (01))]
Lava + 2|)Aa(Y) + vmLa)va
| 1L-YIe
13/2 / (n +))
Lavd +
2x(1 vmLa)vd (n + m)
XX- Y|IF.
1
where the last bounds were derived by using H4, Lemma 7, and the fact that [YAo(Y)lo) (as well as the fact that X LUG + RXuG (A) is 22 3n2 + mm)-1/2-issphitzz) Furthermore, note,
3a LAVd
2x(1 + VMLG)Vd 13/2 (n m)
LA 2x(1 + VmLG)
m
A (m + n)
vn + m
LA
VanLo
(m + n)
vn + m
Hence, the third term in (54) is bounded by applying HI, we get for a universal constant k;
P tr ([IEAAO(X)) (A) x] -E - RAng(())
mt
X + m)
S 2exp
-K (
3x
(LN/VA+ vanLa + K/ /n + +
2
We now focus on the first term (54), by using the Hanson- Wright inequality, we have for universal constant k.
xi Rx (x-= tr Ex / Rx du ( (mm
mt
3aB
(-kmin
(n + m))
A(n - m)tt )) < < 2xxp
{
A2222 At
(-k(nn + m) min
< 2 exp
d32
g2 B
where we have used the fact that m/a = (n + m). as well as Rxua (A) the second term in (54),
- Similarly for
( + mJmt
( m)
( + +m)3t
P Xx tr tr (Ex)
< 2xx
-emin
6ag(aG u(n))
Blaa + u(n))
Bl0G + u(n))
+ ( 3laa + u(n)) B(ac + u(n)) }
(2 + m)t
< 2xxp
-c(n + m) min
We conclude, by merging the three previous bounds in Equation (54), it holds for a universal constant
k
a3
4(0G + ur tr (Ex)
(1+ (a+La) LG) / 13 + m)
P [a,(X) - arr 2 ++
m
(A +m)
12222 X1 #1 {3
A3 mm)2 (n mjjt
< e2mxxp
[k(n + m) min
+ 2n exp
-k(n + m) min
8e u(n))² 3(0c + w(n)) f)
2 + m2
+ 2exp
-k(n + m)
a² (L/VV+ VanLo + x\/ w//n/t/// m
62

---

Thus, only keeping the dominant term, define
22 At
(n m)
V
( + m)2
In In(n)
(1) = min
+
g2 B
plac + u(n))²' Bloa + u(n)) a² (LN/VĀ+ vanlo + ////////1
2
n + m
In(n)
7t + m
we have shown, for a universal constant c,
4(0a + u(n)) tr (Ex) P (x,(X) - ازوه z ++ a.3
(A + m) )) S 6P (-(n+m)()(() (()
(1+ (L)
m
V + m)
(55)
We now turn to the concentration of ag (X), we have from (7) and the triangle inequality,
(1 (/)a(X)) tr (XxxT- - -xx] / Rx--u( (A)de
[g (X) - a I
n
(1 - (X),
Σx { tr
(g) - -E (RAAac(A]]))
+
1
1
+ 30
lr (ExE [RAug
(X)
03 n
(XiX]- - -xx /RX
Rx up A) (0)
tr
/ Rx- in (2) S (o) }
Σx
som (g) E
-
Ex [R.
/2/ [[X Rx ug (A)d (0)
E [R (2))
Ex lop (x)
nd
where we have used the fact that ag (X) 2 ag and a 1, as well as the Cauchy- Schwarz inequality. Similarly as previously, we bound the deviation probability of each term independantly then use a union bound argument conclude. First,
(1
a tr
(XIx]- - Σx} / Rx us (A)dd (0) )
IP
2t)
(xix] - -xx} / RX-- ( (A)c com (0)
)
2 1 ne
}
E
P
tr
X
X
(-kmin { (1 a)2d' (1-a)) a)) X212 Xt
X22222 Ant
}
2exp
2exp
(-k(n + m) min
a
which followed from the Hanson Wright inequality. The second term is controlled by remarking that,
(1 1 -1-9 ir Σx {/ Rx- (A)du com (g) -
som (0) 11) |))2)) 21)
(A) x
x
n
= =P([g(X - [g(x }]| 2 m)t)
where 9 X + tr (Ex f R (d) (g)) is 2v (lop(1 + VmLG)) 332 (n m) 1121 Lispchitz, and so does X + g(X by composition of Lispehitz maps. It resutls from HI,
1 1--a ir Ex { /
R { (A)du (0)
1)) 21) (n 3) 11p (VOLa 1/ m/)
P
(gx-u (m E
(n + 2332
(-A -
(-h
< 2exp
(-k Ex|px(lbp! + /
< 2exp
63

---

The third term is bounded by using the Caucy- Soucy-Schwarz inequality,
1 a Ir
{ Rx (A)de @m (0) - EE' [RAn (R (nlI)]
Σx
E
(1 - a) Ex Vd
/ (Rx-Lo()dee"" wo) E ([RAaR
<
E
n
and, using the shermann-Morisson' 's formula, it results,
Rx (A)dd 30m (0) - E [RAug (A)]
E
[ [Rx-uy(A) (A) (x) de (a)
E
Rx- (X)= @m 1x H()
+
E
B f (xx-ug (A) - (0)
Rx uy (A)x X (A)
du d (g)
Rom
F
12 + m
1 (n 1xx Rx us (A)xx
remarking that, for the Lowner order I. we have,
Rx ug (A)X Rx (N) + (n I u
(x Rx-
further using the facts that the Lowner order is preserved when integrating over the distribution of the random matrices, and that the Forbenius norm is increasing for the Lowner order on PSd matrices, we have,
Rx-1N 19 (A)x,X] Rx- 11 (A) du (0)
[
E
<
E
Rx ug (A)X1X) Rx- -ug (A) 8o (g)
1 + (n + m) Rx- (1)x1
< EE
(A)x (0)
EE
tr (Ex)
Thus.
< E / Rx (A)d - nx Ho)
+ tr (Ex) A(n + m)
E
fcm (o) E Auug (A) Rx Lig (A) x
F
Finally, using the dual representation of the Frobeniusn norm, H5, and the Lispchitz property of g Rx Rxx-ug()) we have,
/ /Rx-uu -8('((0)
/ B (2 d(u 1x " (())
E
sup E
[Bll==
2E [ (uXT.
@m -
S sup
13/2 m)
Bl[e
2 2/mul()))
2 2
X3/2 (n + 1/1
23/2
we conclude on the third term by,
a
tr
Σx E
(X)dd 8om (0) x (m)
(Ruu (al1}))
n
(1 ai) [u][Exxlo lopp vd
[RX (A)du (o)
E.
E (RAug (A))
n
(1 a)l Σx Vl
(2u(n)
X3/2 + tr trx)
M(n + m)
|Xx llop
(2van(n)
(r (Ex)
<
+
nn
X3/2
X(n + m)
64

---

finally, the deviation probability of (X) that appears in (55) was already controlled in the first part of the proof, we thus conclude throuh union bound argument that,
|xxx llpp
(2/ea(n)
Ir tr(Ex)
P [x)
- a 2
++
+ +6g
Vn
A3/2
X(++
S
a
tr
(x1x] - -Ex] /
Rx-11n
c0m (0)
2 3
71
a tr
Σx {f Rxx (g) - EE { (
(X) 1}) 23)
+ P
n
30 |al|Ex Exx llope
+ P
[xy(X) -ağl
2 3
t
nd
{ X212
Nt :06)
(n + m)
$ 2xpp
ccnn + m) min
+ 2exp
- oolVaLo 1/ 1/vn mm3
(1 a)"
(-dnn m)a maaa
nttt
+ 6exp
Bal|E llopd
(1 a) 1 )e))
X262
(n + m))3(²
< 2exp
ccln + m)) min
c(n
2exp
(- oglVaaa + 1/ //v m)3
(-on+ + m/aa
At
6exp
3 ExExlen llpp
defining,
X222 :
2²2²
(
At
(1- At,
Se
oolVaLo 1//n + m)
the claim follows.
D.2 Proof of Theorem 2
This section is dedicated to the proof of Theorem 2. To this end, we define AEAug(A) EAug(A)- (Aug(A), and we notice that
A (A) = 2 { 1 tr (Exx RAug + (XI (((())(Db..) xxxx))
(56)
d
where i and Φ are defined in (8). The proof of Theorem 2 goes in several step that we hereby describe. the first step (Appendix 1.2.1), we provide tight concentration bounds for o and $ In second step (Appendix D.2.2), we shall bound E [AE (A)]. Finally, in the third and last step (Appendix D.2.3), we deduce the concentration property of AE
D.2.1 Concentration of Φ and 42
First recall the definitions of Φ (X) and (x) from (8),
(X) (1 d/n)
(AA((X)
d tr Rx(
+Ald
LA (X),
(X)
xx - (1 3/a (X))a
(x,(())) R (A, ()
(x (X)
+ Ala -1)
(X) ir
We begin by introducing the auxilary functions V,, V/ defined as follows,
(aAc(X)) + ATa "1 In, (X),
(X() = 1- 1-dd/n)
d tr Rx((0)
aj
VX Rdxx
(57)
(X( 1- (1 3/ag)a
tr p(a)) (2) ( (aAc(X)
+ Ald )
da;
ag
65

---

where (a., a2)) were defined in Theorem 4.
This first part of the proof consists in showing that (x and (2(X) are respectively close to V (X) and (X), and then showing that the functions 1 and V2 are Lipschitz, which will results in Lub-Gaussian concentration bounds from HI.
Concentration bounds for Φ (x)) - 1 (X) and ( (2(X)
We show that & (X) v (X) has sub-exponential tail, to do so, write the following almost sure decomposition,
1 (X) (x()
1 - (d/n)
tr (Rx (0)) tr [xx(0) {
(
(ada(X)
- Ald ")) L (X)
+ +dla)
d
(x(X)
%
a(1 - (d/n)) ir Rx(0) (oAo(X)
Aa(x) ( (adcox) + X1l ))) I (X) 1x)(X)
(x)(x))
+ +ATs)
(x)
%
d
(x(
aj
a(1 (d/n))
(Ad(X)
[ado(X)
<
[x)(X) -55l
+ Ala
ax(X)m) )md
aj
0g
<
[X)
aاا n
This implies,
IP P (X) - (X) 2 P (xx(x)) - -agl > 7
Leveraging Proposition the previous implies in straightwordard way that,
(x((X) 22(x)12t+
adgy
SP (ax(x)) - -ayl 2 a
ntt
+ 6g z exp
(-onn + m)sa qAt
))
n
(58)
where So was defined in (9).
Similarly, we write for (X) (X),
xx(()) v2(X)] 5
1
Ba
R (1,
(x,(()))
(Ao(X)
+ +Ala -) ax(X)
-1
a
(X))
da (X)
1
1- a'
tr
R (2,
((la(2))
(2,X)
(ano(X)
+ +AIa
ax (X)
ag(x)
+AIa ) (x)
1 a'
(())
((5)
(xdo(X)
tr
[ (2,
da
(at) Roi (x,)) x) {
/ado(X) Ala "}]
1 - a'
( xx(X)
tr
+ Ald
dag
ay
66

---

(0.2 Recalling that R / (A, X) was defined in (6), we further get, from A that,
B-1 1
A AB A)B-1
22 (X) - vx2(
0g
1
og(X)
da (X)
Ba
tr
GIX
((a,(X))
(
(X,
(x(x)
+ +Xls) )
1
1 - a²
tr
R
R(aa(X))
(),
ado(X)
+als
a
az
(X)
(x(X)
1
1 - a'
[((((()) G (2, + aAc(X)) B (1,)) (
(ado(X) +Ala
+
tr
0g
(X)
da
(x(X)
+
0g
(X)
1
1 - a'
da
Ir
(a)) G
(
(
xx(X)
ATaa)
ada(X)
(ado(x) + Ala
})
and, applying Cauchy-Schwarz inequality, as well as using that all dilation factors are greater than 1, we get.
3a X²
(X) Mx((X) $ |az -xg(X)
a'
+ +la; an ax))
12
a'
1B3Cx + (X)
p(o)) GIX (A,
+ (X) - -a/l
A2
ag
opp
a'
xAa(() (aAa(X)
-1
+ (X) - a/y
+ Ald
A2
0g
Ba + 2(1 a²)
1 - a'
(X) a
+
[xx(X) arl
X2
X2
x 9g (X) - ag + x2 a (X) -a
results, from a unoin bound argument, that,
82 + 6g
( v2 1+
< (X) - aلا 2 X 5g) PP (Ia agl X553L 6z)
X²
S (exp(=c(n + m) min C, (t) (x
where the last line (as well as the definitions of 85, 6g. Sx and (g) followed from Proposition 9.
Concentration bounds for V 1 (X) and (x2(X)
As previously discussed, the concentration of 1 (X) and (X) follows from the Lipschitz proper- ties of , and 2 as well as HI. Starting by the concentration of 4 (X), recall that d < from H2 and we write for any X, Y E An,
(ado(X)
+ +AIa) -Aaa) )
|V -
(Y()
d un (Rx(0)-Rr(O)) -
ay
1
ur Ry (0){ (ada(X)
(0)(aa)())) + +Ald)
-1 (ada())
+ +Ala) }
+
d
9
un [xx(0) Rx(()) + -lTx (and((X) -11
aj
+ a tr Rx (0) (ala(X)
- -ooX)) (adoly))
+ xIa) "
+ +Xla)
ag d
ag
67

---

Using the Cauchy-Schwarr inequality, as well as H4, we get
1 1 -0-,),y))) V.(Y) V (X)
Rx (0) Ry(0))lr
nd ||Ao(x) Ac(Y))F
2 dn +
|x -X-Yi -YllF.
n2avd
Lo,
Where, we used Lemma 6 and H4 in the last bound. We have proved that V is Læ, -Lipphitz on Ay
and || W 11IA, 1o.0 5n 1--11-1 <n
we have from Proposition 6 that v (X) is -j--ub-Gaussian, with
aLa
L + IA,, RR S Amps/2 dn
n
Hence, there exists constant k: > 0 such that,
12
(X), 1 2 1) S exx
-k 3/21//-/2///0 ///////n/// Lan 1 x-2/Vaje) (60)
Similarly for (2)))), we write for any X, E Rdxn
1
R (a
( (A, X)- RiO (. (A.Y) 87
(x
V2((Y)
+ +ATa
ard
1
(05)) Raix (A. (2.1)
{ (CAO(x) +2la
(ascc(X) + XIa
7}]
+
ad
ag
ag
1
{ [ (A, X)- - -RGIx (2, {)
(0g)
(2)o(x)
+ -l4e
and
+ a
ir [RG (1, Y)
(oso(X)) +Ala)
(lc(X)-a(7)
(ado(X) aj
+ Ala
aj
and, using the Cauchy- Scharz inequality, get.
1
(ap) G
(A, X) R(o) (A, Y)IFF
(2(X)=
V2(1) a;\v d
R
Aa(X) - AG
a3a;231vV
2
ALa
X - Y
a:/1///2 v d(n + m)
a3y;X2n
=h4g
(1g)
where used the Lipschitz property of X + G X), which follows from Lemma 6. Remark further that,
1
LA
Lg, S Lw S
+
2/23/2 /d(3/2/d(n + m)
nd2vd
thus, we get from HI, the existence of a constant & such that,
- -k 3/2/ / /d(n + m) + Lan 1x 1222/Vd22
t²
P 2 [ s 2exp
(2
(61)
68

---

D.2.2 An upper bound on the asymptotic bias of EAug(A (A)
Let us denote for sake of notational simplicity,
V llop + n²) ndI (Ex) an 2)6 (kqq + +22 (1(( d(B3)|Exx18 + xT
1|1
0Aug
ag
+1)
0. a.3vd( Ex llop + +3 1333|AAallpp)
(1 (1+ + + 1/3
/n+
a
((1 a)) 2
1 -1-a +1)
a
aB3dd
+
((1 a:)7 + 222 + ((1 a)n + 2)5/2m
E [[1AG(X)-Aam) -
/ op (11 [|Exx 11s x22)
\1 (xx)
1
(KGq) + 02)
+
nd1 [xx )
|xx lop
K3
2x 1lop + 93 AallAAllop lop (1+ + VaLa + (1 (x 133 Vn+1
(1 - -a)))//m
+ 11/2 vd E (X) Acl FF
(62)
a
m
such that it holds from Theorem 4,
E
S 8Amg (A) - Aug (2)
(2)
(63)
Let us first recall from (56),
{ - tr (Ix RAug (A)) (X) +2(x))
1
AE (A)
We have shown in Appendix 1.2.1 that $b (X) and (x) respectively concentrate around EE (X))
and E [X)]] In this section, we derive an upper bound for the aboslute value of
1 ur (Ex [RAUE (A))) + E BV BV
E A Xun (A)] = 2
First relying on (63), we write,
1 E | Aug (A)] $ - tr ( Aug (2) E (X)) E (x)
8 (Ex)
(64)
and, we remark that in the case where Σx and AG commute, then the first term in the right-hand side can 'lincarize', in the general case, we use the notation [A, B] two matrices, and we write,
AB -BA for the commutator of
d tr (Ex R
1 (5-15(1 (3). (1)))))11)) AAug
1 [Rug (1) (A)
+Als) (2)(a
(aλo
(ada
+ +AIa)
"xx()
az
aada + AAla Ex¹
(ada
tr
R (2)
+ >ld
aj
aj
tr
(aajaa)())) R R
(2)
aaão + 2)
[
-1 + Ala
, {ل
a
az
(65)
We now bound the second term and provide new expression for the first one.
69

---

Using the identity
A- the Cauchy-Schward inequality, and Ill we can bound the term involving the commutator
A
IH I VVd
[
1
R (2)
+ +ATa)
tr
Raug
+AIa
d
tr
R
Aug
(
(2)Ex
aaA + +AIs, Σx
Ex
Σx
(ada Ald
ag
og
tr
Auu
(2(0 (2)23 (2)2x
|Ao. 2x 2x
aAc
+ Ald
dag
9g
9
Σx 1
aλG %
+ Alaa
R
(A)xX
|Ex 1
S a
op ||AG. Σx 2
||AG. Ex|lp
Vdag
vdd²
(66)
Furthermore, using -1 11------ A- A)B we get,
(12)03) Aug
(aAc
ag + Ala Σx = 1 (A)
aAcc + +Ala) (1- (1-(1-8/a5ja)
2x
-1 1 (1 8/a 2/15)a )a
R
(A)
3/a5)a)
ag
a
(1 (1- (1 3/ag)a)
R [0] (A)
(67)
Aug
a
Plugging (66)-(67) in (65), we get,
1 d ir Σx
Rang
())
x tr
Σx
Ao
+ Ald )7)
1 - (1 3//a% )
tr
Raug
(A)
(Ac
Ac
+ Ald )
d
az
ag
Σx 12
||AA Ex|1lF
vdx²
Plugging the previous equation in (64), we get,
+ AI -1 E. [E (X)]
Ag
E A Aug
(A)]
d tr
(68)
(1 3/ 8/ar)ax
((aana)))))
(2) (
Ao
+ AId ")
E [x)(
R
a
ag
| lla
dAug.
||A
Ex]ll+ +
vdx²
We thus simply need to bound the biases of (X) and (x),, for notation simplicity again, we introduce the notations,
1
Ag
V
tr
Σ
+
+AId
(69)
d
ag
1 (1
B/a
AG
V2
R
(2)
+ Ald
ax
az
Then, we have by definition of v (X) in (57)
E ((V = 1- (d/n)
E in [x((0) {
(ado(X)
+ (laa
(ade + Ala) "1)) IA, (x))
(,g
d
aj
1 (d/n) ufT (Rx(O)
Exx
[1 (x)
(ada
+ Ala) )
1 (d/n)
ax
+ ((
70

---

Thus, thanks to the triangle inequality.
tn Rx(0) ((ado(x)
-1
(adea + +d1a) -11) I 1n (x)
[X)] V11 S
E
+ ATTa
d
aj
I- Σx
} La,
[x,(
(adaa og
+ ALa) )
d
Rx (0)
(d/n)
v (1 P(A,))
furthermore, using the Cauchy- Sacchy-Schwarztee inequality and the Jensen's inequality, we get
[ w1 5
(
+ +Al1)
+ +Ala)
- La, (x) (70)
1/V
%
1
E
Rx
1- 2x
(d/ri) / 1A (x)
Av d
(1 11
Using A -1 ------1-- A-1 ( A}B- 11 we can bound the first term in (70),
(X) a
-1
+ +aaa) -aadc g
+ +Ala)
1 (X)
S E [IAAaX)- - AG]lF]
x2
(71)
the second term in (70) is controlled by applying Proposition 8, remark that (1- - (d/n))-1 is the
fixed point of + 1 + b(d/n) (which implies that (1 (d/n)) = Rxx (0)), the second term is bounded as
=Rx
Ex
1A, (x)
E Rx( - 1- (d/n)
(72)
|Ex 1lpp) 1+
(Vd Ex 11
|Exllop + |Ex 1lap 1
I
+
c cxn
A1(Ex)
nn1 (7
for q being a polynomial function in 17 + A₁ (D), (Ex), Ex ex and n-1 Finally, the last term in (70) is controlled thanks to H2, prcesicely, holds,
E lap e exx
1 -xn (Ex)a
- ((
(73)
Putting (71), (72) and (73) together in (70), we get,
1 (1 1+
|E llop
[oValEE 11a
(MI1ZaIA + +1|Exlop +
|EE 112
E [ (X) Jo -
cxn
Xva
(Ex)))
"
va E [IIA((X) ACIIF]
(74)
(xx)
d||Ex
[E llop
nd, (Ex) Am
An (2xx)
1
(xxx mintA, n3
+ 21 (Exx))
1 11 exxn AA, (2x)² n)Va
+
Ex llop
|5x 12
|| |Ex||op
E [IIAa(X) - Aclle]
Vd
71

---

We now turn to the bias of (x)X), recalling (57), and (69), we have,
V2(X)- - 1/2- - 1-a' a'
(o))) (
{
( + +Ala)
aacc aj
+ Als) "})
tr
R
and
dj
+ 1 1- a' ir (1RO21 (1, x) -
( /ado
+ ATa -
a²d
thus, using the triangle inequality yields.
{
1 1 a² E [x)] W/2l
(ado aj
E
tr
(2
+ Ald
ag d
4g
a'
Ir ((z)
(a)) [
(xx)
Raug
((0i (1)) (
(adc 4g
+ Ald
add
and, further using the Scharz inequality, as well as - a S 1, we get,
E [
S
1
E
xxA((X)
+ALa)
(aAa + +Ala
Avd
d
ag
ng
1
[ (A, x0] - 15) (A) (
((( GiX
E
Ava
1
E (X) Aolle]
1
E R
(a (2, x)]
R (2)
13 d
Avd
Now, using that R (A, X)= (1-a') -Rx (aAa(X) +1/(1 -a) La), we write.
E 2 (X)] - 2/22
I 1
[[]A6(X)- - Aclle]
23 \v
-()-a')0+ [1--d)(x+ + aAo(X)
- (11- + ado(x)
+
E
+ +Ala)
+ +Ald
Xva
a
oj
I
+
(1
a'jaa
E Rx (1 a')az
Rx
+ a- Ia
1a) ]]
R(a:)
xx
( αïo
(1 (1-a')a;
+ 1 - a' Id
E [XI - Aallo] + (1-o')Ava
1
[ (D) R((3) (D)
v3
Where, we have used the notation,
aλo
A
D
1- a La
(1 11-ci a''aaaa
Finally, using Proposition 8, get,
E 2X)] - 2
(75)
qVd Σx 1lsp (1 a') nd (Ex (1 + (D)) Xvdd E [[AA(XX) - Aclle]
+
And, remarking that (D 2 2/(1 - a'), we finally get,
q x|
E [X)) 12 S nxx(E a')n + A)6 + v E [lAa(X) - Aollr]
(76)
72

---

D.2.3 Conclusion on the proof of Theorem 2
To conclude on the proof of Theorem 2, we plug (68), we first show that Φ1 (X) concentrates around V (resp. (2(X) around 22 with bias of order òaug (resp. ÒAug). Introduce the following notations,
(2xx
+
|xx llop
ndI (Exx \2
A1 (Ex)
1
(xx min(f,
+ (Ex))
|| [xx l8p exx
+
|Exlon
|xx lop
Exllop
AA1 (Ex) min ( 77 Vd
a
E (aacaxx)-Aalll
-
1/22
x1<xx nd Ex) + + X3vd [[AG(X) - Ralle]
50z =
and, make the preliminary remark that, for some C1 C2 and C3 independant of n, d, m, and that depend polynomially on A₁ (Ex), [x llop and min (), 77, we have,
E1 ndi (Ex) 1 min (A, 1)
E2 e exn
[Il -AllFF]
5v
5w2 2
+
(77)
A (Ex) min A, vVv
min mi,( A33Va
C3 + | lipp
E [ Acllr]
M 2 min \, 1
min min3n,Ap3Vl
From there, we bound E
A Ang (A)] as,
X ()]]
2 1 -
E
1 (X)]
+ 1 E [x)1(()]]
|| |x 1lpp
8A
||AG, ΣxIlFp
Vdx2
(Ex)vV
|Σx 12a
6 jang
82, +o2z +
[[A,EExlll +
vdx²
A (Ex)vo
Ca(1 + + E
E [I) - Aclle
|E
8A
[[ Ex]][r
(Ex) min 17
min X/aVa
Vdx²
Where the first inequality followed from (68), the second from (74) and (76), and the last one followed from (77). Now, recalling (62), we have,
8 8
a Σx (app(( ( Ex 1 + x3))
(11
22
{
{ (1(x)))
1
Ad
nd1 ).6
|E
A3
Σ llop + 9al vallAcllop
a)di (Ex )15/2m ( (11+u(n)) u(n)) + VOLo + (1+ 1122
Vn+
1/22 + vd -
(1 (Ex))
It results that for constants C4, C3 independant of d, and that depend polynomially on À₁ (Ex). Ex Ilops K, m/n, u(n), La and min(A, (7,). we have,
T Aug (A)]I C (1 o6) + cx (1 16p + |E (loppttt (1 (1-a) am (Ex)² min(), (A, n77
E [IIAG(X) AcllF]]
|E 11g
+ Cs
||AG Ex]le
min(n, \33va
vdx²
73

---

Writting &total = ōv, +ōg + +1 Ilop d 1/2 2 | Ex]llE + &Aug. we write from a union bound,
P AlAAug (A) 2 + KrTotal) S
A E Aug (A) E | (A)] 2 1)
1
P
1 (X)) -B [ 2 2 + [02(X) -E - - 2 2)
1 4) +P
W ( - E 2 ' 1)
S P
( (X) vi(X) 2
(22(X) - v2(x)) = 1 1) + P [22(X) E E[ 2 1
+ P
2 exp
-k(n + m) min (,(A9t)66(199))) (2(11), So
6
+ exp
- -1-111133/2 /(nn + m) Lan 1
1111
$ exp
k(n + m) min (x(29t) So
(kk (-k (LA + 1/v
17 d22
+ exp
Where the last inequality followed from (58), (59), (60) and (61). The previous holds for large enough K and small enough that are both universal constants.
To conclude the proof, it remains only to simplify the quantities & and &z. Sg. in order to match the statement of Theorem 2. We start by simplifying the exponent in the concentration statement. First, defining ε = min (A, 1}. we remark that,
n )})
exp (-K(n + m) min
Ca (A2t)), (((2))) So
- exp (-k(n m) min (C((E))),,G(()))
We recall the definition
C2 (t) and (t) from Proposition 9,
X212
2312
}
(t) = min
Xt,
0 (VaaL + 1/ Vn m) So
(1 (1-o8 (1-a)²
B 31 1lop
X212 M
3 + m)
Vx4t
13 + 2)
In In(n)
(t) = min
g B
3 u(n))² Blaa + u(n))
a² (LA VaVAnLo + RV/\ vn
2
m
Note that in the worst case scenariom we have (n + m) = 1, hence we write.
212 et en + m)12
e21 Plac + u(n)) Bloo + u(n)) a² (LA + Vav/nLo + /KVA//n
5 + m)2
In(n)
(t) 2 min
12 3
m
t
t²
t
2 3 min
Beee B
BE(oC + u(n))) a² (LA + varinilo + KVA 32 + u(n))²²
8
and
12
1
el {
(t) 2 3 min
mmm
[e(1 a)' 56 odl + 1 Co
74

---

We From there, we define,
11,2 =
2, max(e(1 ol. + 1)2}
and,
= = max u(n)) a² (LA vavanLo kVX)
Eigg m u(n)))
This ensures that,
12
1
(g(e2t) 2 e² min
0 min
E2. Ez.
E2
and,
Ect E122
et
602
Se(e2t) 2 2 min
fig E2,9
31Ex1lopE1,
/3||Ex (ipp
1
12
min EtEi E2
B
Ex E1.9 B² 52.52.9
Defining P1 and P2 such that, Pi max [1 x e S e [1
P2 =max . 531|Ex lop =² {2
(78)
we have shown,
ndAt )))
exp (kx(n + m) min (=(A2t).
I exp (-k(n m) min
x ne k(n+m))) ppa + kkx+m)ttpp
75


Reviews:
[{"review_id": "dpECRnJSWD", "reviewer": "Reviewer_1hLH", "summary": "This paper presents a theoretical and empirical study of inverse covariance (precision matrix) estimation in high-dimensional settings. It compares two classes of estimators: (1) standard linear shrinkage estimators and (2) estimators based on data augmentation (DA), including both transformative and generative DA schemes. The authors develop non-asymptotic concentration bounds for the quadratic error of these estimators, leveraging advanced tools from random matrix theory, including novel deterministic equivalents. They also provide practical estimation formulas and validate them using experiments on synthetic and real datasets (e.g., MNIST).", "questions": "Any results on more complex datasets, besides the simple MNIST?", "limitations": "No, the authors showed that the proposed method works on high-dimension settings, but the experiments were conducted on a very simple dataset (MNIST).", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths：\n1.\tThe paper makes a substantial contribution by offering a non-asymptotic framework for analyzing precision matrix estimation with DA, an area where prior work is sparse.\n\n2.\tIn this paper, the author gives a comprehensive and detailed prove to support the proposed claim.\n\n3.\tNumerical results support the claims, demonstrating the tightness of the theoretical bounds.\n\nWeaknesses：\n\n1.\tThe theorical contribution is substantial, but the definitions, lemma, theorem are too many resulting certain sections are notation-heavy. Is it possible to simplify some statement and make it more reader-friendly.\n2.\tThis paper is more about theory analysis and lack of practical demonstration. The experiment part need to consolidate. MNIST dataset is too simple to verify the theory is  consistent with real world scenario. This paper focus on high dimension data but MNIST data (28*28) is low dimension in reality. And also the experiment part lack comparison with prior key method.\n3.\tWhile the theory is well-documented, the experimental section lacks of code and implementation details. Hard to reproduce and understand the connection between theory and practice if lack of code.", "was_revised": true, "final_justification": "The authors' rebuttal responses clarified some questions. I updated my rating accordingly.", "rebuttal": "We thank the reviewer for their thoughtful feedback and for recognizing the importance of the contribution of our work, we address the reviewer's feedbacks and question below:\n\n**_The theoretical contribution is substantial, but the definitions, lemma, theorem are too many resulting certain sections are notation-heavy. Is it possible to simplify some statement and make it more reader-friendly._**\n\nWe agree that some parts of the paper may appear notation-heavy. However, we would like to emphasize that this level of formalism is essential to ensure the rigor and generality of our theoretical results. That said, we acknowledge that the complexity may hinder readability for some audiences and may not always be necessary to convey the core narrative of the paper.\n\nIf the reviewer believes it would improve accessibility, we are open to implementing the following modifications:\n\n* In the main text, we could restrict our presentation to the case of Gaussian (or sub-Gaussian) data and replace assumption H2 with the simpler condition that the eigenvalues of $\\Sigma_X$ are bounded away from zero. As already mentioned in the submitted version, this setting suffices to apply our results (see Appendix A.1 for details). Making this change would allow us to remove some of the heavier notational machinery—such as Definition 1 and H1—from the main document.\n* We could then postpone the more general framework to the appendix and explicitly show how the simplified setting discussed in the main text is a special case of the broader results.\n\nUnfortunately, the statements of Theorems 1 and 2 cannot be easily simplified without weakening our bounds on the estimation error. In this regard, we would like to clarify our motivation for introducing the quantities $C_1$ and $C_2$: they are designed to simplify our expressions by encapsulating repetitive and technical terms such as $\\|\\Sigma_X\\|_{\\mathrm{op}}^{-1}$, $c_X^{-1}$, and $\\eta + \\lambda$. \nIn all relevant random matrix models, these quantities are upper bounded.\nMoreover, the constants $C_1$ and $C_2$ are non-increasing functions of these quantities, making our upper bounds conservative in a meaningful way.\nIn summary, Theorems 1 and 2 provide worst-case bounds where $C_1$ and $C_2$ remain bounded for all relevant models. We recognize that this point may not have been sufficiently clear in the original submission, and we will include a discussion clarifying this in the revised version of the paper.\n\n**_This paper is more about theory analysis and lack of practical demonstration. \nThe experiment part need to consolidate. MNIST dataset is too simple to verify the theory is consistent with real world scenario. \nThis paper focus on high dimension data but MNIST data (28*28) is low dimension in reality. And also the experiment part lack comparison with prior key method._**\n\n**_Any results on more complex datasets, besides the simple MNIST?_**\n\nWe acknowledge that the MNIST dataset is relatively simple, as the reviewer pointed out. However, we would like to emphasize that it is still widely used as a conventional benchmark in many recent studies, \nsee for instance [1] or [2].\n\nIn response to your feedback, we have also conducted additional experiments on CIFAR-10 and CIFAR-100. These results exhibit similar behavior and, in particular, further validate our theoretical findings in a larger-scale setting. For reference, we include the sample tables below\n, as linking to external figures is not allowed this year.\nTable 1 gives $(\\hat{\\lambda} - \\lambda^\\*) / \\lambda^\\*$, where $\\lambda^\\* = \\arg\\min \\mathcal{E}_X(\\lambda)$, $\\hat{\\lambda} = \\arg\\min \\hat{\\mathcal{E}}_X(\\lambda)$, for various $\\gamma = d/n$, on CIFAR-10 and CIFAR-100 (both in grayscale):\n\n| $\\gamma = d/n$ | CIFAR-10 | CIFAR-100 |\n|----------------|----------|------------|\n| 0.15 |  7.13   % |  0.82  %|\n| 0.30 |  0.16   % |  0.13  %|\n| 0.45 |  0.10   % |  0.09  %|\n| 0.60 |  0.08   % |  0.07  %|\n| 0.75 |  0.07   % |  0.06  %|\n| 0.90 |  0.06   % |  0.06  %|\n\nSimilarly, we provide a table for the relative error of estimating the optimal proportion of artificial data, in the case of the fixed Gaussian TDA with $\\Lambda = \\sigma I$ (presented in table 1 of the paper), we display $(\\hat{\\alpha} - \\alpha^\\*)/ \\alpha^\\*$, where $\\hat{\\alpha}$ has been estimated by minimizing $\\hat{\\mathcal{E}}_{Aug}(0)$, for various values of $\\sigma$, and for fixed $\\gamma = 0.85$.\n\n| $\\sigma$ | CIFAR-10 | CIFAR-100 |\n|----------|-----------|------------|\n| 1   | 0.64   % | -0.06  %|\n| 0.9 | 0.59   % | -3.06  %|\n| 0.8 | 0.65   % | 0.85  %|\n| 0.7 | 1.24   % | -1.26  %|\n| 0.6 | -0.78  % | -1.72  %|\n| 0.5 | -0.25  % | 0.71  %|\n\nIn addition, we would like to clarify the reasoning behind our dataset choices and highlight certain limitations. Our primary objective was to evaluate the accuracy of our estimators $\\hat{\\mathcal{E}}\\_X(\\lambda)$ and $\\hat{\\mathcal{E}}\\_{\\text{Aug}}(\\lambda)$. \nTo do this meaningfully, we either needed access to the true covariance matrix of the data distribution (which is not possible) or a highly accurate empirical approximation. This required a high-dimensional dataset (dimension > 100) where the ratio of dimension to sample size was sufficiently small (less than 1/100), ensuring the sample covariance matrix is a reliable proxy for the true $\\Sigma_X$. This requirement is motivated by the Marchenko-Pastur theorem, which explains why such a ratio is crucial. To the best of our knowledge, very few publicly available datasets satisfy these conditions, and we were unable to identify higher-dimensional alternatives to MNIST or CIFAR that fit these stringent criteria.\n\nThat being said, we believe that our expanded numerical experiments offer a compelling proof of concept and empirically validate the estimators presented in Theorems 1 and 2. This level of empirical support aligns with what is typically expected in theoretical contributions such as ours, a point the reviewer also acknowledged as a strength of the paper. To the best of our knowledge, we are the first to provide computable non-asymptotic bounds for precision matrix estimation using data augmentation, while also shedding light on the key limitations of this widely used technique. We view this work as an important step toward better understanding and tuning of data augmentation in modern machine learning. Moreover, the technical difficulty of the proof methods developed in the paper is, in our view, nontrivial. This is  reflected in the length and complexity of the supplemental material, which spans 56 pages of detailed appendices.\n\n**_While the theory is well-documented, the experimental section lacks of code and implementation details. Hard to reproduce and understand the connection between theory and practice if lack of code._**\n\nSince our experiments were relatively small-scale, as the reviewer noted, we did not initially deem it necessary to include the code. However, in response to the reviewer’s request, we will make the code available in the revised version of our paper.\n\nWe thank the reviewer again for their valuable comments and constructive suggestions. If the reviewer finds our clarifications and proposed revisions satisfactory, we would kindly ask them to consider updating their evaluation to reflect these improvements.\n\n**References**\n\n[1] \"Efficient Data-Dependent Random Projection for Least Square Regressions\" by J. Sturges et al.  \n[2] \"Maximizing the Potential of Synthetic Data: Insights From Random Matrix Theory\" by A. El Firdoussi et al."}, {"review_id": "z6rI9hPINk", "reviewer": "Reviewer_y2zf", "summary": "The paper analyses common methods for estimating the inverse covariance of a matrix in high-dimensional settings. In particular it develops data-dependent estimates for the squared error of linear shrinkage and data augmentation estimators, and provides guarantees for these data-dependent estimates. It uses these empirical estimates to help tune certain hyper parameters used in covariance matrix estimation.", "questions": "1. Can you discuss the weaker convergences guarantees guarantees you promise when one relaxes H4?\n2. Can you perform an asymptotic analysis of your guarantees under some simplifying assumptions as a sanity check for your readers?\n3. Could you discuss the growth of your error in estimating the squared-error with respect to d and n?", "limitations": "Many have been discussed by the authors, I have discussed some other limitations that inform my decision to lean towards rejecting the paper above.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper addresses the important problem of estimating inverse covariance matrices from a theoretical perspective.\n2. The paper focuses on the important subproblem of estimating the squared error of both kinds of inverse covariance estimators\n3. The paper establishes theoretical guarantees for these squared error estimators\n4. The paper’s brief empirical experiments help strengthen their claim about the reliability of their empirical estimators\n\nWeaknesses:\n1. Part ii of H3 severely limits the applicability of their result, and the work does not discuss how their results would change if parts of the statement were relaxed (such as the conditioning of Lambda_G(X))\n2. The Wasserstein distance part of H4 seems quite strong, it would be nice if the paper elaborated on the “weaker convergence guarantees” they mention below it.\n3. Most important: This is my biggest qualm. The theoretical results are not well thought out. Their expression uses both the operator norm of Sigma_X and lambda_1(Sigma_X), which are literally the same thing unless I am gravely mistaken. Further, the dependence of the error in squared-error estimation on d and n is not clear since the operator norm of a matrix can grow with d and n. This is further exacerbated by the missing expressions for C_1 and C_2 and no discussion about their growth with d and n. I am leaning reject primarily because the theory is not properly addressed, which is supposed to be the main strength of the paper in my eyes.\n4. While the paper is about non-asymptotic guarantees, it is important to have a sanity check where they recover some familiar or believable asymptotic guarantees under perhaps additional distributional assumptions on X.\n5. While experiments were perhaps not the main focus of this paper when it was being written, I think a paper addressing an estimation problem and submitted to an ML conference with claims about its utility in choosing hyperparameters should have more extensive experiments across multiple datasets. Unlike some theory papers, this paper’s theory is less about conceptual insight and more about estimating bounds. I think such papers need to have extensive experiments.", "was_revised": true, "final_justification": "The rebuttal has addressed my qualms but my new score is heavily conditional on a significant improvement in the paper’s presentation and writing.", "rebuttal": "We sincerely thank the reviewer for taking the time to engage critically and constructively with our submission. We appreciate the recognition of the strengths of the paper, particularly about the quality of the theoretical contributions, and we value the concerns raised. We address each of the reviewer’s points in detail below. \n\n**_Part ii of H3 severely limits the applicability of their result, and the work does not discuss how their results would change if parts of the statement were relaxed (such as the conditioning of $\\Lambda_G(X)$)._**\n\nWe respectfully disagree with the reviewer’s comment. The decomposition of $\\mathbb{E}[C_X \\mid X]$ assumed in H2-(ii) is always satisfied (at least for $\\beta = 0$), and the conditions on the conditioning, as well as smoothness of $\\Lambda_G(X)$ holds for a wide range of common data augmentations, as illustrated in Table 1 and discussed in detail in Appendix A.2. In fact, our formulation of H2-(ii) was specifically motivated by these data augmentation techniques, and we expect that any reasonable augmentation scheme amenable to theoretical analysis will satisfy this assumption. That said, we remain open to revisiting this point should the reviewer be aware of a common data augmentation method that does not satisfy point (ii) of H3.\n\n **_The Wasserstein distance part of H4 seems quite strong; it would be nice if the paper elaborated on the “weaker convergence guarantees” they mention below it._**  \n**_Can you discuss the weaker convergence guarantees you promise when one relaxes H4?_**\n\nWe acknowledge that Assumption H4 is relatively restrictive. However, it is satisfied under additional assumptions on the distribution of $X$ (e.g., boundedness of the data), as discussed in detail in Appendix A.2, to which we refer the reviewer for further clarification.\n\nWhile it is indeed possible to relax this assumption by adapting our proof strategies, e.g., by requiring only local Lipschitz continuity along with stronger assumptions on the data distribution, this would introduce considerable technical complexity and result in looser bounds. We chose not to pursue this direction for two main reasons. First, incorporating such generalizations would significantly increase the length of the paper, which already includes 56 pages of supplementary material. Second, it would further complicate the presentation of our results, which some reviewers already found difficult to digest. In fact, one reviewer even suggested that we simplify the assumptions in the main text and relegate the general framework to the appendix.\n\nFor these reasons, we fear that including such an extension would be lost in the supplementary material and would not substantially benefit the clarity or accessibility of the paper. We therefore leave this extension for future work.\n\n **_[...] uses both the operator norm of $\\Sigma_X$ and $\\uplambda_1(\\Sigma_X)$, which are literally the same thing [...]_**\n\nAs noted in the notation section on page 2, we follow the convention $\\uplambda_1(\\Sigma_X) \\leq \\ldots \\leq \\uplambda_d(\\Sigma_X)$; therefore, the two quantities mentioned are indeed distinct. While the reverse ordering is perhaps more common in the machine learning literature, our choice is standard in parts of the probability literature and is not a typographical error, \nsee for instance [1] or [2].\nThat being said, if the reviewer finds this convention to be detrimental to the clarity of the paper, we are of course open to changing it to align with the standards of the machine learning community.\n\n**_[...] the dependence of the error in squared-error estimation on d and n is not clear since the operator norm of a matrix can grow with d and n. This is further exacerbated by the missing expressions for $C_1$ and $C_2$ and no discussion about their growth with d and n._**\n\nWhile it is true that all quantities involved in these terms depend on $d$ and $n$, it is common in asymptotic random matrix theory to assume that they are bounded. If one is interested in the detailed expressions of these terms, they can be found in Appendix C, page 58, for $C_1$ and $C_2$, and Appendix D, page 74, for $\\tilde{C}_1$ and $\\tilde{C}_2$.\nOtherwise, assuming the previous greatly simplifies the asymptotic analysis of our bounds and results in $\\Delta_X(\\lambda) = O(\\sqrt{d}/n + 1/(\\lambda^3 nd))$.\n\nMore precisely, the constants $C_1$ and $C_2$ are designed to simplify our expressions by encapsulating repetitive and technical terms such as $\\|\\Sigma_X\\|_{\\mathrm{op}}^{-1}$, $c_X^{-1}$, and $\\eta + \\lambda$. As previously discussed it is standard to treat these latter quantities as upper bounded. Moreover, the constants $C_1$ and $C_2$ are non-increasing functions of these quantities, making our upper bounds conservative in a meaningful way.\nIn summary, Theorems 1 and 2 provide worst-case bounds where $C_1$ and $C_2$ remain bounded for all relevant models. We recognize that this point may not have been sufficiently clear in the original submission, and we will include a discussion clarifying this in the revised version of the paper.\n\n**_While the paper is about non-asymptotic guarantees, it is important to have a sanity check where they recover some familiar or believable asymptotic guarantees under perhaps additional distributional assumptions on $X$._**\n\nTo our knowledge, no existing results directly compare to Theorems 1 and 2. However, we did compare the non-asymptotic guarantees derived for our deterministic equivalents, particularly Proposition 1, with results from the asymptotic literature. In particular, our bounds are consistent with those established in [3].\n\n**_[...] I think a paper addressing an estimation problem and submitted to an ML conference with claims about its utility in choosing hyperparameters should have more extensive experiments across multiple datasets. [...]_**\n\nIn response to your feedback, we have also conducted additional experiments on CIFAR-10 and CIFAR-100. These results exhibit similar behavior and, in particular, further validate our theoretical findings. For reference, we include the sample tables below, as linking to external figures is not allowed this year. Tables 1 and 2 further validate our methodology for hyperparameter selection. Table 1 gives $(\\hat{\\lambda} - \\lambda^\\*)/ \\lambda^\\*$, where $\\lambda^\\* = \\arg\\min \\mathcal{E}_X(\\lambda)$ and $\\hat{\\lambda} = \\arg\\min \\hat{\\mathcal{E}}_X(\\lambda)$, for various values of $\\gamma = d/n$, on CIFAR-10 and CIFAR-100 (both in grayscale):\n\n| $\\gamma = d/n$ | CIFAR-10 | CIFAR-100 |\n|----------------|----------|------------|\n| 0.15 |  7.13 % |  0.82 % |\n| 0.30 |  0.16 % |  0.13 % |\n| 0.45 |  0.10 % |  0.09 % |\n| 0.60 |  0.08 % |  0.07 % |\n| 0.75 |  0.07 % |  0.06 % |\n| 0.90 |  0.06 % |  0.06 % |\n\nSimilarly, Table 2 gives $(\\hat{\\alpha} - \\alpha^\\*)/ \\alpha^\\*$, in the case of the fixed Gaussian TDA with $\\Lambda = \\sigma I$ (presented in table 1 of the paper), where $\\hat{\\alpha}$ has been estimated by minimizing $\\hat{\\mathcal{E}}\\_{Aug}(0)$, for various values of $\\sigma$, and for fixed $\\gamma = 0.85$.\n\n| $\\sigma$ | CIFAR-10 | CIFAR-100 |\n|----------|----------|-------------|\n| 1.0      | 0.64 %   | -0.06 %     |\n| 0.9      | 0.59 %   | -3.06 %     |\n| 0.8      | 0.65 %   | 0.85 %      |\n| 0.7      | 1.24 %   | -1.26 %     |\n| 0.6      | -0.78 %  | -1.72 %     |\n| 0.5      | -0.25 %  | 0.71 %      |\n\nIn addition, we would like to clarify the reasoning behind our dataset choices and highlight certain limitations. Our primary objective was to evaluate the accuracy of our estimators $\\hat{\\mathcal{E}}\\_X(\\lambda)$ and $\\hat{\\mathcal{E}}\\_{\\text{Aug}}(\\lambda)$. To do this meaningfully, we either needed access to the true covariance matrix of the data distribution (which is not possible) or a highly accurate empirical approximation. This required a high-dimensional dataset (dimension $>$ 100) where the ratio of dimension to sample size was sufficiently small (less than 1/100), ensuring the sample covariance matrix is a reliable proxy for the true $\\Sigma_X$. This requirement is motivated by the Marchenko-Pastur. To the best of our knowledge, very few publicly available datasets satisfy these conditions, and we were unable to identify higher-dimensional alternatives to MNIST or CIFAR that fit these stringent criteria.\n\nThat being said, we believe that our expanded numerical experiments offer a compelling proof of concept for the estimators presented in Theorems 1 and 2. This level of empirical support aligns with what is typically expected in theoretical contributions such as ours, a point the reviewer also acknowledged as a strength of the paper. To the best of our knowledge, we are the first to provide computable non-asymptotic bounds for precision matrix estimation using data augmentation, while also shedding light on the key limitations of this widely used technique. We view this work as an important step toward better understanding and tuning of data augmentation in modern machine learning. Moreover, the technical difficulty of the proof methods developed in the paper is, in our view, nontrivial. This is  reflected in the length and complexity of the supplemental material, which spans 56 pages of detailed appendices.\n\nOnce again, we are grateful to the reviewer for their insightful comments. If the reviewer finds our clarifications and the new experimental results satisfactory, we would respectfully ask them to consider improving their score, as we believe the revisions and explanations provided significantly strengthen the clarity, completeness, and overall contribution of the paper.\n\n**References**\n\n[1] \"Large Complex Correlated Wishart Matrices: Fluctuations and Asymptotic Independence at the Edges\" by W. Hachem et al.  \n[2] \"On the Distribution of Eigenvalues of GUE and its Minors at Fixed Index\" by T. Tao.  \n[3] \"Quantitative Deterministic Equivalent of Sample Covariance Matrices with a General Dependence Structure\" by C. Chouard.\n\\end{itemize}"}, {"review_id": "gVjDGYD4Pu", "reviewer": "Reviewer_HgXn", "summary": "The objective of this paper is to derive non-asymptotic guarantees for estimating the precision matrix (i.e., the inverse of the covariance matrix). The quality of the estimation is assessed using the Frobenius norm between the estimator and the true precision matrix.\n\nIn the first part of the paper, the precision matrix is estimated using a ridge-like estimator of the form $(C_X + \\lambda I)^{-1}$, and the associated risk, which depends on the regularization parameter $\\lambda$, is estimated. It is shown that this risk estimator increasingly approximates the true risk. Consequently, the parameter $\\lambda$ can be optimized—provided the estimated risk has a computable gradient—in order to improve the precision matrix estimation.\n\nThe second part of the paper investigates the effect of augmenting the data matrix $X$ with additional samples (e.g., Gaussian isotropic noise or dropout-based augmentations), and then applying the same estimation and optimization procedure to this enriched dataset.", "questions": "You can responds on the weakness(soudness) bullet points to improve your rating.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n* The paper provides a solid theoretical foundation, offering non-asymptotic results for the inverse of a random matrix—a notably challenging problem.\n* The use of deterministic equivalents and the companion Stieltjes transform reflects a modern approach in non-asymptotic random matrix theory.\n* Table 1 presents a broad set of data augmentation (DA) examples, and the stated assumptions are satisfied.\n* The proposed method includes a practical component, enabling gradient-based optimization of the estimated risk, which is fully computable.\n\n**Weaknesses**\n\n* The choice of the Frobenius norm as the error metric is not sufficiently justified. For instance, in some applications it might be more relevant to focus on estimation accuracy along the leading eigen-directions of $\\Sigma$.\n* The assumption $\\gamma = d/n < 1$ (required for Assumption H2) appears inconsistent with the introduction’s emphasis on the high-dimensional regime and the double descent phenomenon.\n* The assumptions in Section 2 are overly complex. Assumption H1, in particular, includes conditions both on the entire matrix $X$ and on its columns. These could be simplified by focusing only on column-level assumptions (e.g., i.i.d. Gaussian or bounded entries). Definition 1 seems unnecessary for the main narrative and could be moved to the appendix.\n* The term $\\Delta_\\lambda$, intended to represent a bound on the bias, is not clearly defined. Its formulation includes the same quantity in both the constant and the expression, making it difficult for the reader to identify the key parameters. Moreover, the homogeneity of the expression is not respected.\n* Section 3 is promising, but somewhat disappointing. While it hints at the potential to replace the regularization term $+\\lambda I$ with a data augmentation strategy that serves a similar role, this idea is not fully proved in the upper bound and the number of augmented samples is not optimized. Although the paper alludes to the implicit regularization of DA, it does not concretely leverage this concept.\n\n**Writing advices**\n\n* The manuscript may include an excess of theoretical detail (e.g., Proposition 1 and the subsequent discussion) without sufficient commentary or illustrative examples to aid understanding.\n* The choice $\\lambda_1 < \\cdots < \\lambda_d$ is unconventional (and somewhat inexacte due to multiplicity). \n\n**Typos (no response needed)**\n\n* $\\mathrm{tr}$ instead of $tr$ in Equation (3).\n*  $:=$ is not consistently used for definitions.\n* $\\bar\\Lambda$ not defined.\n\n**Summary**\n\nIn conclusion, while the paper is built on a solid mathematical foundation and uses modern tools, its overall narrative lacks clarity, which makes it difficult to follow. Nonetheless, the approach and results are compelling. I encourage the authors to clarify their exposition and would be open to revising my evaluation.\n\nAfter rebuttal period: borderline reject -> accept", "was_revised": true, "final_justification": "The author has provided clear and convincing responses to my questions and has made significant improvements to the manuscript (such as simplifying assumptions and adding a paragraph on the case $\\gamma > 1$). Given the author’s thorough approach and the strong theoretical contribution of the paper, I am pleased to revise my recommendation to acceptance.", "rebuttal": "We sincerely thank the reviewer for the thoughtful and constructive feedback. We are especially grateful for the recognition of the theoretical foundations of our work. Below, we provide detailed responses to the concerns and suggestions raised.    \n\n**_The choice of the Frobenius norm as the error metric is not sufficiently justified. For instance, in some applications it might be more relevant to focus on estimation accuracy along the leading eigen-directions of $\\Sigma$._**\n\nThe reviewer raises a valid point. First, we would like to emphasize that our results, being stated in the Frobenius norm, do imply bounds on quantities of the form\n$|u^\\top (\\Sigma_X^{-1} - (C_{\\text{Aug}} + \\lambda I)^{-1}) u|$\nfor any fixed vector $u$. In particular, this includes cases where $u$ is an eigenvector of $\\Sigma_X$ associated with a large eigenvalue. However, we agree that such bounds would be looser than those obtained by directly analyzing the quantity of interest without relying on norm-based inequalities.\n\nAlthough this application is indeed feasible, it falls outside the scope of our paper, which focuses on estimation errors that are direction-agnostic. This choice is motivated by the fact that Frobenius-norm-based errors are widely used in applications involving global precision matrix estimation, such as regularization, control of model complexity, risk management (see [1]).\n\nWe believe that including an in-depth analysis of directional errors would significantly complicate an already technically dense paper. Therefore, we prefer to leave this direction for future work or a separate study dedicated to directional error analysis.\n\n**_The assumption $\\gamma = d/n < 1$ (required for Assumption H2) appears inconsistent with the introduction’s emphasis on the high-dimensional regime and the double descent phenomenon._**\n\nIt is a common misconception to think that the condition $\\gamma < 1$ is inconsistent with our emphasis on high-dimensional settings. In fact, many practical datasets satisfy $\\dim > 100$ while still having $0 \\ll \\gamma < 1$. Even under this regime, estimating $\\Sigma_X^{-1}$ remains a difficult problem—this is well documented in the literature on the Marchenko–Pastur theorem   (see e.g. [2]).\n\nMoreover, our method can be adapted to the case $\\gamma > 1$ modifying  the considered estimator. As discussed in the proof sketch of Theorem 1, the assumption $\\gamma < 1$ is specifically used to approximate $d^{-1} \\operatorname{tr}(\\Sigma_X^{-1})$ by $(1 - \\gamma)\\, d^{-1} \\operatorname{tr}(C_X^{-1})$. For $\\gamma > 1$, a similar approximation holds via the dual formulation:\n$$\nd^{-1} \\operatorname{tr}(\\Sigma_X^{-1}) \\approx \\left(1 - \\frac{1}{\\gamma}\\right) n^{-1} \\operatorname{tr}\\left((d^{-1} X^\\top X)^{-1}\\right),\n$$\ni.e., using the Gram matrix rather than the sample covariance matrix. This duality between the $\\gamma < 1$ and $\\gamma > 1$ regimes is well-established in random matrix theory, as it is known that the eigenvalue distribution of the covariance and the Gram matrix differ only by a Dirac mass in $0$ (see, e.g., [3])\nThe case $\\gamma = 1$, however, remains more delicate and is not directly addressed by current tools.\n\nWhile it would certainly be interesting to include the full analysis corresponding to the $\\gamma > 1$ regime, doing so would significantly increase the length and complexity of an already notation-heavy paper. Since clarity and focus are among our priorities, and as this was also a concern raised by the reviewers, we suggest to only add a single paragraph describing how our results generalize in the case $\\gamma > 1$.\n\n**_The assumptions in Section 2 are overly complex. Assumption H1, in particular, includes conditions both on the entire matrix $X$ and on its columns. These could be simplified by focusing only on column-level assumptions (e.g., i.i.d. Gaussian or bounded entries). Definition 1 seems unnecessary for the main narrative and could be moved to the appendix._**\n\nBased on your feedback and suggestions, we propose the following modifications to improve the clarity of our paper:\n\n* In the main text, we will restrict our presentation to the case of Gaussian (or sub-Gaussian) data and replace Assumption H2 with the simpler requirement that the eigenvalues of $\\Sigma_X$ are bounded away from zero. As noted in the submitted version, this assumption is sufficient to apply our results. This simplification will allow us to eliminate some of the more technical notation—such as Definition 1 and Assumption H1—from the main body of the paper.\n\n* The more general framework, along with the full set of assumptions and technical details, will be moved to the appendix. We will also make explicit how the simplified setting presented in the main text is a special case of our broader results.\n\nIf the reviewer agrees that this modification would enhance the clarity and readability of the manuscript, we will implement it in the final version of our paper.\n\n**_The term $\\Delta_X(\\lambda)$, intended to represent a bound on the bias, is not clearly defined. Its formulation includes the same quantity in both the constant and the expression, making it difficult for the reader to identify the key parameters. Moreover, the homogeneity of the expression is not respected._**\n\nFirst, note that all our bounds are explicit, and a fully detailed expression for $\\Delta_X(\\lambda)$ is provided in App. C. We would also like to clarify our motivation for the form given in the main text, and in particular, explain why we introduced the constants $C_1$ and $C_2$:\nthey are designed to simplify our expressions by encapsulating repetitive and technical terms such as $\\|\\Sigma_X\\|_{\\mathrm{op}}^{-1}$, $c_X^{-1}$, and $\\eta + \\lambda$. \nIn all relevant random matrix models, these quantities are upper bounded.\nMoreover, the constants $C_1$ and $C_2$ are non-increasing functions of these quantities, making our upper bounds conservative in a meaningful way.\nIn summary, Theorems 1 and 2 provide worst-case bounds where $C_1$ and $C_2$ remain bounded for all relevant models. We recognize that this point may not have been sufficiently clear in the original submission, and we will include a discussion clarifying this in the revised version of the paper.\n\n**_[...] While it hints at the potential to replace the regularization term $+ \\lambda I$ with a data augmentation strategy that serves a similar role, this idea is not fully proved [...]_**\n\n**_[...] this idea is not fully proved in the upper bound and the number of augmented samples is not optimized. [...]_**\n    \nWe would like to highlight that implicit regularization is already a well-known impact of data augmentation (see e.g. [4] or [5].). \nThe aim of our paper was only to revisit this effect from a quantitative perspective, allowing the users to 1. compare two data augmentation schemes and 2. tune the data augmentation hyperparameters, which can be done by minimizing $\\hat{\\mathcal{E}}_{Aug}(\\lambda)$ with respect to the scheme's hyperparameters. \n\nIn this regard, Our Figures 1.a, 1.b, 1.c show that $\\|\\Sigma_X^{-1} - (C_{\\text{Aug}} + \\lambda I)^{-1}\\|_{\\mathrm{Frob}}$ can be reliably estimated using our results.  \nOptimizing the proportion of artificial data is a natural application that we explicitly mention in the paper.  \nFrom a practical perspective, this can be done using a simple binary search or a gradient descent procedure.\n\n**_The choice $\\uplambda_1(\\Sigma) < \\ldots < \\uplambda_d(\\Sigma)$ is unconventional_**\n\nAs noted in the notation section on page 2, we follow the convention $\\uplambda_1(\\Sigma_X) \\leq \\ldots \\leq \\uplambda_d(\\Sigma_X)$; therefore, the two quantities mentioned are indeed distinct. While the reverse ordering is perhaps more common in the machine learning literature, our choice is standard in parts of the probability literature and is not a typographical error, see for instance [6] or [7].\nThat being said, if the reviewer finds this convention to be detrimental to the clarity of the paper, we are of course open to changing it to align with the standards of the machine learning community.\n\nOnce again, we thank the reviewer for their time and valuable insights. We hope that the clarifications and proposed revisions demonstrate our commitment to improving both the technical quality and the accessibility of the paper. If the reviewer finds our responses satisfactory, we would be grateful if they would consider increasing their rating of the submission accordingly.\n\n**References**\n\n[1] \"An Overview on the Estimation of Large Covariance and Precision Matrices\" by J. Fan et al.  \n[2] \"Spectral analysis of large dimensional random matrices\" by Z. Bai & J. Silverstein  \n[3] \"Anisotropic local laws for random matrices\" by A. Knowles et al.  \n[4] \"Training with noise is equivalent to Tikhonov regularization\" by C.M. Bishop  \n[5] \"The good, the bad and the ugly sides of data augmentation: An implicit spectral regularization perspective\" by C. Lin et al.  \n[6] \"Large Complex Correlated Wishart Matrices: Fluctuations and Asymptotic Independence at the Edges\" by W. Hachem et al.  \n[7] \"On the Distribution of Eigenvalues of GUE and its Minors at Fixed Index\" by T. Tao."}, {"review_id": "Oh5PBrhr1S", "reviewer": "Reviewer_awgT", "summary": "The paper considers the problem of estimating the inverse covariance matrix in a high-dimensional setting. Suppose that $X_1,\\dots,X_n$ are i.i.d. copies of some random vector $X\\in \\mathbb{R}^d$, where $n$ and $d$ are of the same order. The true covariance matrix is $\\Sigma = \\mathbb{E}XX^\\top$ and the goal is to estimate $\\Sigma^{-1}$ from the samples. Since the empirical estimator $\\hat{\\Sigma} = (1/n) \\sum_i X_i X_i^\\top$ could be close to being singular, the paper considers the resolvent $R(\\lambda) = (\\hat{\\Sigma} + \\lambda I)^{-1}$ and studies the error $E(\\lambda) = (1/d)\\Vert R(\\lambda) - \\Sigma\\Vert_F^2$. \n\nIt proposes an estimator for $E(\\lambda)$ and, under certain assumptions (such as Lipschitz concentration) on the distribution, derives a concentration inequality result for the estimator. This enables the use of the estimator as a surrogate objective for tuning $\\lambda$.\n\nIt also considers an estimator based on data augmentation. Let $g_1, \\dots, g_m$ be artificial samples generated from an auxiliary distribution depending on $X$. The augmented resolvent is $R_{aug}(\\lambda) = ((n+m)^{-1}(\\sum X_i X_i^\\top + \\sum g_i g_i^\\top)^{-1} + \\lambda I)^{-1}$ with the associated error $E_{aug}(\\lambda) = (1/d)\\Vert R_{aug}(\\lambda) - \\Sigma\\Vert_F^2$. Under assumptions on the auxiliary distribution, the paper develops an estimator $E_{aug}(\\lambda)$ and proves a concentration bound.", "questions": "1. Proposition 1: What is B? Why is the right-hand side of the inequality independent of B? If I rescale B up by a large factor, the tail probability should be much smaller (depending on the factor)?\n2. Can authors comment on the dependence on eta in their results? Delta_X(lambda) has a dependence of 1/eta^6 and the tail has a dependence of eta^3, which do not look good for small eta.\n3. Can eta depend on n or d? For instance, can eta be at the order of 1/sqrt(n)?\n\nMinor points:\n- Line 16: reads better by changing it to “of a random mean-zero vector from i.i.d. Samples”\n- Line 79: isn’t E a measurable subset of E^{d x k}?\n- Equation (3): “tr” in “tr(R_X(lambda))” should be in upright font\n- Line 228: what is A?\n- Line 247: add a space before “we also”\n- Line 291: what is Equation (66)? It is bad for the main text to point to something in the appendix in a theorem statement.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: These are interesting results to find a surrogate to optimal lambda in the resolvent. \n\nWeaknesses: It does not seem that authors have placed a lot of effort to optimize the bounds; the bounds are not trivial but they seem largely based on the recent progress in random matrix theory. (The dependence on some parameters look bad; see below)", "was_revised": true, "final_justification": "I think the paper makes meaningful progress and is technically strong; however, there is considerable room for improvement in the presentation, so I cannot recommend a firm “accept\".", "rebuttal": "We thank the reviewer for their valuable feedback and insightful questions. We appreciate the recognition of the novelty of our results and the opportunity to clarify and improve the presentation and technical depth of our paper. We respond to each point below.    \n    \n**_It does not seem that authors have placed a lot of effort to optimize the bounds_**\n\nRegarding the optimality of the bounds, we would like to emphasize that considerable attention was paid to ensuring that our bounds remain fully explicit and tight\n—particularly with respect to the exponents involving key parameters such as $\\lambda$, $\\eta$, $\\|\\Sigma_X\\|_{\\mathrm{op}}$, and $\\uplambda_1(\\Sigma_X)$.\nWhile minor refinements may be possible in regards of the complexity and length of the proof, \nwe believe that our bounds already reflect the inherent difficulty of the problem and do not leave any straightforward improvements unaddressed.\n    \nSince we introduced the quantities $C_1$ and $C_2$ in the statements of theorems 1 and 2, we only highlight the worst-case contributions of each parameter involved.\nIn that regard, we recognize that they might appear as suboptimal bounds. This point may not have been sufficiently clear in the original submission, and we will include a discussion clarifying this in the revised version of the paper. \n    \n**_Proposition 1: What is B? Why is the right-hand side of the inequality independent of B? If I rescale B up by a large factor, the tail probability should be much smaller (depending on the factor)?_** \n    \nIn our setting, $B$ is a deterministic matrix of appropriate dimensions. As the reviewer correctly notes, rescaling $B$ should influence the tail probability. The corrected inequality reads:\n\n$$\n\\mathbb{P}\\left( \\left| d^{-1} \\operatorname{tr}\\left( B \\left\\\\{ R_X(\\lambda) \\mathbf\\{1\\}\\_\\{A\\_\\eta\\}(X) - \\mathbb{E}\\left[R_X(\\lambda) \\mathbf\\{1\\}\\_\\{A\\_\\eta\\}(X)\\right] \\right\\\\} \\right) \\right|  \\ge t \\right) \\lesssim \\exp\\left(-c \\\\|B\\\\|_{\\mathrm{op}}^2 (\\eta + \\lambda)^3 \\sigma_X^2 n d t^2 \\right)\n$$\n\nWe thank the reviewer for bringing this typographical error to our attention and will correct the statement in the revised manuscript.\n    \n**_Can authors comment on the dependence on eta in their results? $\\Delta_X(\\lambda)$ has a dependence of $1/\\eta^6$ and the tail has a dependence of $\\eta^3$, which do not look good for small eta._**\n\nRegarding the dependence on $\\eta$, we acknowledge that terms such as $1/\\eta^6$ and $\\eta^3$ may appear unfavorable for small $\\eta$.\nHowever, this behavior is consistent with the role $\\eta$ plays in our framework: \nit serves as a threshold parameter that can be interpreted as a form of forced regularization in the unfavorable event where $C_X$ is not well conditioned.\n\nProvided the covariance matrix $\\Sigma_X$ is well-conditioned (i.e., $\\uplambda_1(\\Sigma_X)$ is bounded below independantly of $n$ and $d$), \n$\\eta$ can be chosen proportionally to $\\uplambda_1(\\Sigma_X)$ and thus stays safely bounded away from zero. \nThis scenario is addressed in Appendix A.1. \nMoreover, our bounds align with known results in random matrix theory, such as those in \"Quantitative Deterministic Equivalents of Sample Covariance Matrices with a General Dependence Structure\" by C. Chouard, \nwhich also feature cubic dependence on regularization parameters in tail bounds, as well as comparable asymptotic guarentees for the bias bound.\n\n**_Can eta depend on n or d? For instance, can eta be at the order of $1/\\sqrt{n}$?_**\n\nThe answer is yes. \nMost parameters in our bounds depend (explicitly or implicitly) on the underlying distribution of $X$, which may itself depend on $n$ or $d$. \nIn standard settings, assuming $\\uplambda_1(\\Sigma_X) \\ge \\epsilon > 0$, $\\eta$ can remain independent of $n$, or bounded w.r.t. $n$. \nIf instead $\\uplambda_1(\\Sigma_X)$ scales as $1/\\sqrt{n}$, then $\\eta$ would also scale accordingly. \nIn this setting our bounds would necessarily degrade, and the control over estimation error would deteriorate, and our method would not be applicable for hyperparameter tuning. \nHowever, a user can easily avoid this scenario by either removing multicolinearity in his features, or by applying a PCA step before using our method (say by projecting the data on a subspace of dimension $\\lfloor 0.9 \\times d \\rfloor$, \nthus removing the directions of very low variance and ensuring that $\\uplambda_1(\\Sigma_X)$ stays bounded away from $0$).\n\n**_Line 79: isn’t E a measurable subset of $E^{d \\times k}$?_**\n\nIt is a measurable subset of $\\mathbb{R}^{d \\times k}$.\n    \n**_Line 228: what is A?_**\n\nA measurable subset of $\\mathbb{R}^{d \\times k}$. In fact, it should be replaced by 'E' to homogenize our notations throughout the paper, as 'A' is used only once to refer to a subset of $\\mathbb{R}^{d \\times k}$, this will be changed in the revised version of the paper and we thank the reviewer for pointing this out.\n\n**_Line 291: what is Equation (66)? It is bad for the main text to point to something in the appendix in a theorem statement._**\n\nEquation (66) is located in the appendix and provides the detailed expressions of $C_1$ and $C_2$. \nWhile referencing an appendix from a theorem is not ideal, it seems to us that in machine learning conferences this is relatively commonly accepted due to page limit. In addition, we tried to avoid writing the full upper bounds on $\\Delta_X(\\lambda)$ and $\\Delta_{Aug}(\\lambda)$ as they are quite long, and would have made the statement unnecessarily complex. \nHowever, if space allow and the reviewer thinks that it is preferable, we will add their expression in the final version of our paper.\n    \n\nOnce again, we thank the reviewer for their helpful comments and careful reading of our manuscript. We believe that these clarifications will improve the presentation and highlight the rigor of our results. We hope the reviewer will find these revisions satisfactory and would kindly consider updating their evaluation to reflect these improvements."}]

Author rebuttal:

Meta-review: This paper presents a theoretical (as well as a bit empirical) study of inverse covariance (precision matrix) estimation in high-dimensional settings. 
The authors compare standard linear shrinkage estimators and estimators based on data augmentation.
The major technical contribution is the derivation of non-asymptotic concentration bounds on the quadratic estimation error, achieved using advanced random matrix theory techniques, as well as novel deterministic equivalents.

The paper is well-organized and clearly written. During the rebuttal period, the authors responded thoroughly to the reviewers' concerns, added further experimental results to support their theoretical findings, and clarified several technical aspects of the manuscript. 
As a result, all reviewers are now satisfied and recognize the strength and relevance of the contribution.

Overall, this is a strong paper that makes meaningful theoretical and empirical advances in high-dimensional precision matrix estimation.
I thus recommend acceptance.
Decision: Accept (spotlight)