Learning multivariate Gaussians with imperfect advice
Authors: Arnab Bhattacharyya
Davin Choo
Philips George John
Themis Gouleakis
Venue: ICML 2025 poster (2025)
Keywords: learning-augmented algorithms
multivariate gaussian learning
sample complexity
Primary area: theory->probabilistic_methods
TL;DR: You can learn gaussians using strictly fewer samples than needed in the worst case, if you start with a good enough guess for the parameters.

Abstract: We revisit the problem of distribution learning within the framework of learning-augmented algorithms.
In this setting, we explore the scenario where a probability distribution is provided as potentially inaccurate advice on the true, unknown distribution. Our objective is to develop learning algorithms whose sample complexity decreases as the quality of the advice improves, thereby surpassing standard learning lower bounds when the advice is sufficiently accurate. Specifically, we demonstrate that this outcome is achievable for the problem of learning a multivariate Gaussian distribution $N(\mu, \Sigma)$ in the PAC learning setting. Classically, in the advice-free setting, $\widetilde{\Theta}(d^2/\varepsilon^2)$ samples are sufficient and worst case necessary to learn $d$-dimensional Gaussians up to TV distance $\varepsilon$ with constant probability. When we are additionally given a parameter $\widetilde{\Sigma}$ as advice, we show that $\widetilde{\mathcal{O}}(d^{2-\beta}/\varepsilon^2)$ samples suffices whenever $|| \widetilde{\Sigma}^{-1/2} \Sigma \widetilde{\Sigma}^{-1/2} - I_d ||_1 \leq \varepsilon d^{1-\beta}$ (where $||\cdot||_1$ denotes the entrywise $\ell_1$ norm) for any $\beta > 0$, yielding a polynomial improvement over the advice-free setting.

Learning multivariate Gaussians with imperfect advice
Arnab Bhattacharyya" Davin Choo 22 Philips George John Themis Gouleakis
Abstract
in modern applications is on high-dimensional distributions, with the goal being to understand when one escape the curse of dimensionality. The survey by (Diakonikolas, 2016) gives an excellent overview of classical and modern techniques for distribution learning, especially when there is some underlying structure to be exploited.
We revisit the problem of distribution learning within the framework of learning -aggnnnte al- gorithms. In this setting, we explore the scenario where a probability distribution is provided as po- tentially inaccurate advice on the true, unknown distribution. Our objective is to develop learning algorithms whose sample complexity decreases the quality of the advice improves, thereby surpassing standard learning lower bounds when the advice is sufficiently accurate. Specifically, we demonstrate that this outcome is achievable for the problem of learning a multivariate Gaus- sian distribution N (M, Σ) in the PAC learning setting. Classically, in the advice-free setting. (e22 samples are sufficient and worst case necessary to learn d-dimensional Gaussians up TV distance with constant probability, When we are additionally given parameter E as advice. we show that O(d2- /e²) samples suffice when- ever ||5~1/25 1/2 Talli S ed--8 (where || [Ia denotes the entrywise & norm) for any 3 > 0. yielding a polynomial improvement over the advice-free setting.
In this work, we investigate how to go beyond worst case sample complexities for learning distributions by consider- ing situations where one is also given the aid of possibly imperfect advice regarding the input distribution. We posi- tion our study in the context of algoritims with predictions, where the usual problem input is supplemented by "predic- tions" or "advice" (potentially drawn from modern machine learning models). The algorithm's goal is to incorporate the advice in way that improves performance if the advice is of high quality, but if the advice is inaccurate, there should not be degradation below the performance in the no-advice set- ting. Most previous works in this setting are in the context of online algorithms, e.g. for the ski-rental problem (Gollapudi & Panigrahi, 2019; Wang et al., 2020; Angelopoulos et al., 2020), non-clairvoyant scheduling (Purohit et al., 2018), scheduling (Lattanzi al., 2020; Bamas al., 2020a; An- toniadis et al., 2022), augmenting classical data structures with predictions (e.g. indexing (Kraska et al., 2018) and Bloom filters (Mitzenmacher, 2018)), online selection and matching problems (Antoniadis et al., 2020; Dütting et al., 2021; Choo et al., 2024), online TSP (Bernardini et al., 2022; Gouleakis et al., 2023), and a more general frame- work of online primal-dual algorithms (Bamas et al., 2020b). However, there have been some recent applications to other areas, c.g. graph algorithms (Chen al., 2022; Dinitz et al., 2021), causal learning (Choo et al., 2023), and mechanism design (Gkatzelis et al., 2022; Agrawal er al., 2022).
1. Introduction
The problem of approximating underlying distribution from its observed samples is fundamental scientific prob- lem. The distribution learning problem has been studied for more than a century in statistics, and it is the underlying engine for much of applied machine learning. The emphasis
"Equal contribution. Part of work done while the au- thors were affiliated with the National University of Singa- pore, Singapore. 'University of Warwick, United King- dom 'Harvard University, United State of America 'CNRS- CREATE & National University of Singapore, Singapore "Nanyang Technological University. Singapore. Correspondence to: Arnab Bhattacharyya <arnab. saamaaabbattacchayyyeee warwick.ac.uk>> Davin Choo <davinchoo@ @ seas. harvadd.dd.. Philips George John <philips sehilipp..eorge.... @ edu. Themis Gouleakis <themis.gouleakie edt....u..g>>.
We apply the algorithms with predictions perspective to the classical problem of learning nigh-dimensional Gaussian distributions. For a d-dimensional Gaussian (H, E), is known (e.g. see Appendix C. of (Ashtiani al., 2020)) that (I) When Σ = Ia, ((d/=²) i.i.d. samples suffice to learn Ā E Rd such that drv (N (2,L,)) Ia), N (ñ, It)) S E.
(2) In general, @(d2 /E2) i.i.d. samples suffice to learn jú and Σ such that dN E), N(, Σ)) S..
Here, dry denotes the total variation distance, and the al- gorithm for both cases is the most natural one: compute the empirical mean and empirical covariance. Meanwhile, note
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning multivariate Gaussians with imperfect advice
that if one is given as advice the correct mean jí J4, then e
Theorem 1.2. For any given e, E (0,1), 11 E [0. and
using distribution testing, one can certify that using only @(vd/E²) samples, quadratically better than without advice: see (Diakonikolas et al., 2023) and Ap- pendix C of (Diakonikolas al., 2017). This observation motivates the object of our study.
Σ
E Rddd TESTANDOPIMZEECOVARAAAC
uses n E
0
d d + min { (1,
where
||voo (voc(E-111 1-111-11---- 1/2 Iall
(E,,,d.,.E))
d
i..d. samples from N(u, Σ) for some unknown mean I and unknown covariance E, and can produce je and Σ in poly(n, d, log(1/E)) time such that drv (Hs E), N (f,, E) Se E with success probubility at least - 6.
GAUSSIAN LEARNING WITH ADVICE: Given sam- ples from a Gaussian N (H,, Σ), as well as advice zú and Σ. how many samples are required to recover ğ and Σ such that ( (14, Σ), (f,, Σ) S & with proba- bility at least 1 - 8? The sample complexity should be a function of the dimension, e, 5, as well as a measure of how close/ jı and Σ are to 14 and E respectively.
In particular, TESTANDOPTIMIZEMEAN uses only 2 samples when || MAll < ed = =vd- d 52/2 for any TJ E [0. 41. Similarly, TESTANDOP-
TIMIZECVVARIANCE uses only Ō 0( samples when |/vcc E 1/2 1/2 L1)ll1 < =d =d' = Ed d d' for any ") E [0, 1]. Both algorithms have polynomial runtime.
Notation. We use lowercase letters for scalars, set elements, random variable instantiations, uppercase letters for ran- dom variables, bolded lowercase letters for vectors and sets, bolded uppercase letters for set of random variables and matrices, calligraphic letters for probability distributions and sets of sets, and small caps for algorithm names. Intu- itively, we use non-bolded versions for singletons, bolded versions for collections of items, and calligraphic for more complicated objects. The context should be clear enough to distinguish between various representations.
The choice of representing the quality of the advice in terms of the l f-norm is well-motivated. It is known, e.g. see Theorem 2.5 of (Foucart & Rauhut, 2013), that if vec- tor x satisfies ||0||] S т, then for any positive integer s, ag (w) < </(2/²). where o.(xx) is the f--error of the best s- sparse approximation to x. Thus, if - I (1d(1-n)/2 then aw- (e - μ1) S E. The latter may be very reasonable, as one may have good predictions for most of the coordi- nates of the mean with the error in the advice concentrated sublinear (d'-") number of coordinates. Algorithmi- cally, we employ sublinear property testing algorithms to evaluate the quality of the given advice before deciding how to produce a final estimate, similar in spirit to the TE- STA STANDMATCH approach in (Choo et al., 2024). The idea of incorporating property testing as a way to verify whether certain distributional assumptions are satisfied that enable ef- ficient subsequent learning has also been explored in recent works on testable learning (Rubinfeld & Vasilyan, 2023; Klivans et al., 2024; Vasilyan, 2024).
1.1. Our main results
We give the first known results in distribution learning' with imperfect advice. Our techniques are piecewise elementary and easy to follow. Furthermore, we provide polynomial time algorithms for producing the estimates ç and Σ based on LASSO and SDP formulations.
Given mean j Rd and covariance matrix Σ Raxd as advice, we present two algorithms TESTANDOPTIMIZE- that prov-
MEAN and TESTANNOFTIIIZZCOOAAARI ably improve on the sample complexities of (dd/=²) and @(P / for identity and general covariances respectively when given high quality advice.
We supplement the above with information-theorrtie lower bounds. Here, we say that an algorithm (e, 1 PPC learns a distribution P it can produce another distribution P such that (Pv P) S with success probability at least 1- Our lower bounds tell us that (id/e?) and ((d2/e2) samples are unavoidable for PAC-learning N (H, and N(,, Σ) respectively when given low quality advice.
Theorem 1.1. For any given e, 8 E (0, 1), n E 10, 21, and algorithm uses
j Rd,, the TESTANDOPTIMIZMEAN O (d-" + min (1, (1, d, e))) where
f(u, ūt d E) = - R
dn-ing²
Theorem 1.3. Suppose we are given já R2 as advice with only the guarantee that || Aill1 S A. Then, any algorithm that (E, 3 learns N La) requires
i..dd samples from Nu,, La)for some unknown mean and identity covariance La and can produce îe in poly(n, d) time such that dTv (H, Ia), N (īi La)) S s with success probability at least 8.
d mmin(d,22// (22)) samples in the worst case. elog(1/6)
Theorem 1.4. Suppose we are given a symmetric and positive-defmite E E Rddxd as advice with only the guarantee that ||vec (Σ-AΣŹI-1D - La) 11 S A. Then,
There recent concurrent work discrete distribution testing with imperfect advice (Aliakharpour et al., 2024).
2

---

Learning multivariate Gaussians with imperfect advice
any algorithm that (e, PPAC learns ( Σ) requires
1.2.1. APPROACH FOR TESTANDOPTIMZEMEAN
Ω mingd" A2 E" (oo((1/))
samples in the worst case.
Without loss of generality, we may assume henceforth that / 0 since one always pre-process samples by sub- tracting j and then add μ back to the estimated p.. Our overall approach is quite natural: (i) use the tolerant testing algorithm in Lemma 1.5 to get an upper bound on the "ad- vice quality", and (ii) enforce the constraint on the "advice quality" when learning Jr.
Both of our lower bounds are tight in the following sense. Our algorithm TESTANDOPIMIZEEEN gives a polynomially-smallee sample complexity compared to Odd/e) when the advice quality (measured in terms of the (n-nrrm) is polynomially smaller compared to eVd. Theo- rem 1.3 shows that this is the best we can do; there is a hard instance where the advice quality is S Evd and we need Mddss)) samples. A similar situation happens between TE- STAANOPTIMIIZCOVARAAA
The most immediate notion of advice quality one may posit is || O||2 = || Let us see what issues arise. Using an exponential search process, we can in- voke Lemma 1.5 directly to find some > O, such that r/2 < /I - fاll = || S r. To argue about the sample complexity for learning j., and ignoring computational ef- ficiency, one can invoke the Scheffé tournament approach for density estimation. Let N be an E-cover in & of the the fz-ball of radius r around O. Clearly, 1 is e-close in lg to one of the points in N. It is known (e.g. see Chapter 4 of (Devroye & Lugosi, 2001)) that the sample complexity of the Scheffé tournament algorithm scales as log WW How- ever, we have that log [M] = (d)) e.g. see Proposition 4.2.13 of (Vershynin, 2018). Indeed, one can get a formal lower bound showing that the sample complexity cannot be made sublinear in d for non-trivial values of To get around this barrier, will instead take the notion of advice quality to be ||]|/ instead of |/l|2. is known that d d lg balls of radius s suffice to cover an -balll of radius r, for some absolute constant c > 0; e.g. see Chapter 4, Example 2.8 of (Vershynin, 2012). Using this modified approach, the Scheffé tournament only requires O log d) samples which could be o(d/e?) for a wide range of values of r.
and Theorem 1.4, when the guarantee on the advice quality is S ed.
Note that the lower bounds in Theorems 1.3 and 1.4 apply even when the parameter A is known to the algorithm, while our algorithms are stronger since they do not need to know A beforehand. In case A is known, the sample complexity of the distribution learning component of our algorithms match the above lower bounds up to log factors.
1.2. Technical overview
To obtain our upper bounds, we first show that the existing test statistics for non-tolerant testing can actually be used for tolerant testing with the same asymptotic sample complexity bounds and then use these new tolerant testers to test the advice quality. The tolerance is with respect to the f2-norm for mean testing and with respect to the Frobenius norm for covariance testing. These results are folklore, but since they may be of independent interest, we present their proofs in Appendix B.1 for completeness.
Lemma 1.5 (Tolerant mean tester). Given 62 E1 O, 16s2 2
There are still two issues address: (i) how to obtain an é estimate r of μ., i.c., r/2 S || S r, and (ii) how to get a computationally efficient learning algorithm.
5 E (0, 1), and d 2
(z-r)) there is a tolerant tester that
Vd log (!)) i.i.d. samples (1, Ia) and uses O 69-87
To address (i), we can apply the standard inequality //4||2 S ||||| S Vd[|palla bound to transform our la estimate from Lemma 1.5 into an l one. However, since the number of samples has quadratic relation with r, we need a better approximation than vd to achieve sample complexity that is sublinear in d. To achieve this, we partition the ls vector into blocks of size at most k < d and approximate the & norm of each smaller dimension vector separately and then add them up to obtain an é estimate of the overall μ.. Doing so improves the resulting multiplicative error to RJ vd/k instead of Vd. In effect, we devise tolerant tester for mixed f12 norm instead of the & or E2 norms directly.
satisfies both conditions below:
1. If |/pp < E1, then the tester outputs Accept.
2. If |||l|| 2 Ez, then the tester outputs Reject,
each with success probubility at least 1 1-d d.
Lemma 1.6 (Tolerant covariance tester). Given E2 > E1 > 0, 3. E (0, 1), and d 2 E.. there is a tolerant tester that uses O dd max
1 :. 2 )²
- 2)
)
log (t) i.i.d.
(
samples from N(0, E) and satisfies both conditions below:
1f Σ - Ial|r F S Eι, then the tester outputs Accept, 2. - Iall= 2 E2, then the tester outputs Reject,
each with success probability at least 1 - 5.
To address (ii), observe that the Scheffé tournament ap- proach requires time at least linear in the size of the e-cover. In order to do better, we observe that we can formulate our task an optimization problem with an e -i-conttraint. Specifically, given samples y1,..., Yn. we solve the follow-
We will first explain how to obtain our result for TES- TANDOPTIMIZEMEAN before explaining how a similar approach works for TISTANNOPTTIEECOVAALAA
3

---

Learning multivariate Gaussians with imperfect advice
ing program: jú argmin || 1 Ei= Ily, - 31 The error l| -4--P fal22 can be analyzed by similar techniques as
Rdxd, we have [[AAA)
- 1/2 -all
- 1/2 - -Ill-
those used for analyzing E ---reullarization in the context of
LASSO or compressive sensing; e.g. see (Tibshirani, 1996; 1997; Hastie et al., 2015).
The matrix A in Lemma 1.7 is essentially constructed by combining the eigenspace corresponding to "large eigen- values" with suitably upscaled eigenspace corresponding to "small eigenvalues" in the empirical covariance matrix obtained by d i.i.d. samples.
1.2.2. APPROACH FOR TESTANDDOPIMIZECOOWAANNE
As before, we may assume without loss of generality that Σ = La by pre-processing the samples appropriately. Fur- thermore, we can invest ((d/=²) samples up-front to ensure that the empirical mean j will be an s-good estimate of μ.. Then, it will suffice to obtain an estimate Σ of E such that | - Lallr F S (E)) suffices. Furthermore, we may assume that we get i.i.d. samples from (0, Σ) and also that Σ is full rank. These are without loss of gener- ality for the following two reasons. Firstly, instead of single sample from N(u, E), we will draw two samples 22 N Σ) and consider x' 21-21 which is dis- tributed according to (O, S).eenonly it is known that the empirical covariance constructed from d i. samples of (0, )) will have the same rank as E itself, with proba- bility at least 1 - 6; see see Lemma 131 So, we can simply project and solve the problem on the full rank subspace of the empirical covariance matrix.
The second adjustment pertains to the partitioning idea used for multiplicatively approximating ||vec Iu)ll Ob- serve that the covariance matrix of marginal of a mul- tivariate Gaussian is precisely the principal submatrix of the original covariance Σ on the corresponding projected coordinates. For example, if one focuses on coordinates [i,j} S [d] of each sample, then the corresponding co-
E Σi,] for i < j. To this end, ΣS Σn
variance matrix is
we generalize the partitioning scheme described for TES- TANDOPTIMIZEEEAN to higher ordered objects.
v2
Definition 1.8 (Partitioning scheme). Fix q 2 1. 2 1,
and a q-ordered d-dimensional tensor T E Rd Let B S [d] be a subset of indices and define TB as the princi- pal subtensor of T indexed by B. A collection of subsets B ... S [d] is called an (g, d, k; a, parrtiition of the tensor T if the following three properties hold:
At a high level, the approach for TESTANDOPTIMIZECO- VARIANCE is the same as TISTAANDOPTIMIZEMEANN after three adjustments to adapt from vectors to matrices.
1. B S k...., |Bu| S k
2. For every cell of T appears in at least of the principal subtensors , .... TB...
The first adjustment is that perform a suitable precondi- tioning process using an additional (dd) samples so that we can subsequently argue that Σ 1 S 1. This will then al- low us argue that Σ - Ialle I Σ E ||2 Σ Σ Σ||r E O(e). Our preconditioning technique is inspired by (Ka- math et al., 2019); while they use (dd samples to construct a preconditioner to control the maximum eigenvalue, we use a similar approach to control the minimum eigenvalue.
3. For every cell of T appears in at most b of the w principal subtensors TB.,..., TB...
For example, when q = 2, T E Rdxd is just a d x d ma- trix. Observe one can always obtain a partitioning with h S dd by letting the index sets Bi,... B encode every possible index, but this results in large w ( which can be undesirable for downstream analysis. The partition- ing used in TESTANDOPTIMIZEMEAAN of Definition 1.8 with g = a = b = 1, k = [d/w]. For TISTANDDOPIMMZEECOWWIINNN
is a special case
In more detail, our technique is as follows: we will compute a preconditioning matrix A using d i.i.d. samples such that AEA has cigenvalues at least 1, i.e. Xunnn (AEA) 2 1. That is. [I(AEA) 12 = AAIAA & 1. Then, we solve the problem treating AEA as our new Σ. This adjust- ment succeeds with probability at least 1 - 5 for any given 5 E (0. 1) and is possible because, with probability 1, the empirical covariance Σ formed by using d i.i.d. samples would have the same eigenspace as E, and we would have a bound on the ratios between the minimum eigenval- ues between Σ and Σ; see Lemma 1.1
we are interested in the case where q = and a 1. Ideally, we want to mini- mize k and 6 as well. Figure illustrates an example of a (q = 2, 5, 3, 1, parrtitiion.
While an existence result suffices, we show that a probabilis- tic construction will in fact succeed with high probability.
Lemma 1.9. Fix dimension d 2 2 and group size k S d. Consider the q = 2 setting where T E Rddx is a matrix. Define w = 10d(d-1)logd Pick sets BI....,BA Bu each of size k uniformly at random (with replacement) from all the possible (2) sets. With high probability in d, this is a (g = 2, 2, = 1,b 30(d-1) -prtitiionig scheme.
k(k-1)
Lemma 1.7. For any 8 E 10, there is an explicit preconditioning process that uses i.i.d. samples from N NO. Σ) and succeeds with probability at least 1 8 in constructting a matrix A E Baxd such that Amiu (AEA) >
(k-1)
The key idea behind utilizing partitioning schemes is that the marginal over a subset of indices S [d] of a d-dimensional
Furthermore, for any full rank PSD matrix Σ E
4

---

Learning multivariate Gaussians with imperfect advice
Slack (1.2.11
Rook (1.4.5)
Hlock (2.4.9)
Mack [S.49]
tions f1y-... (a....-JAa Ja that satisfy the conditions of the lemma (pairwise KI. and pairwise TV 2c), while also sat- isfying a guarantee on the advice quality with respect to all fi..... faM (say, the quality of a is Q). Then, applying the lemma will show a sample complexity lower bound for learning a distribution given advice with quality Q, since an adversary can choose an Si in the cover set and give a (fixed) as the advice in each case while still satisfying the advice quality requirement. Note that the advice is immaterial here as the underlying ground truth is one of fI...., S'..
Figure I: Consider partitioning a d x d matrix (i.e., = 5
and q = 2) with w blocks (11,2,3), (1,4,5), (2, 5), (3, 4, 5)], each of size k 3. We see that every cell in the original 5 x 5 matrix appears in at least and at most b = 3 times across all the induced submatrices.
The lemma asserts that we still need Q log M
samples to learn a distribution close to the given fü (where the pair- wise TV separation of >> 2s is crucial in ensuring that the learning algorithm would need to identify the correct fa to succeed, since no distribution f will be s-close in TV to fi and f, for i i j due to the triangle inequality).
Gaussian with covariance matrix Σ has covariance ma- trix that is the principal submatrix ΣB of E. So, if we can obtain multiplicative a-approximation of a collection of principal submatrices -...... ΣB,, such that all cells of Σ are present, then we can obtain a multiplicative a- approximation of Σ just like in Section 2. Meanwhile, the b parameter allows us to upper bound the overestimation factor due to repeated occurrences of any cell of E.
In the context of learning a Gaussian with unknown mean, the advice quality that we consider is || - 1lll.. where jú is the advice and f is the ground truth. To show Theorem 1.3, we construct cover of M distributions N N(1,, La) such that || Milla is precisely the same for all fe, ss Then, we ensure that the pairwise TV and KL requirements are satisfied by controlling the & distance I| - F4yl2 for each pair * j. This enables us to use a construction where we set the first & coordinates of each μ4, based on the codewords of an error correcting code with distance 2 ()k)), and we can show the existence of such a code with 20((k) codewords using the Gilbert- Saabert-v bound.
Finally, the third and last adjustment is to the optimization program for learning E. Given samples y Yn from N (H,, Σ), we define:
Σ = argmin
- - 11
A gdxd is p...d 1=1 [| Sr Sr [A $1
Observe that Σ is a feasible solution to the above program. The optimization problem can be solved efficiently since it can be written as SDP with convex constraints; see Appendix D.3. We finally bound| Σ Σ|[r y using an anal- ysis that mirrors that for TESTANDOPTIMIZEL
In the context of learning Gaussians with unknown covari- ance, we consider the advice quality || ΣΣ -ーー - -Lall where Σ is the ground truth and Σ is the advice. To prove lower bound on the sample complexity of learning given good advice, we follow a similar strategy where again, we want to construct a cover of M distributions NO, E,) which all satisfy a bound on the advice quality and also sat- isfy the pairwise TV and KL requirements, (Ashtiani et al., 2020) also pursue the same goal but without the advice qual- ity constraint. We adapt their construction by defining family of block-diagonal orthogonal matrices such that the size of the submatrices can be used to control the entrywise e -oror distance to the identity. Quantifying the KL diver- gences and TV distances between the constructed gaussians then gives the desired lower bound.
but is in terms of matrix algebra. We provide the pseudocode and analysis of the gorithm in Appendix D.
al-
1.2.3. LOWER ROUND
To prove Theorem 1.3 and Theorem 1.4, we make use of a lemma in (Ashtiani et al., 2020) that informally says the following: If we can construct cover fi...., far of distri- butions such that the pairwise KL divergence is at most ı and the pairwise TV distance is > 2e, then, given sample access to an unknown fa. the sample complexity of learning a distribution which is E-close to f; in total variation with probability 2 over the samples (which referred to as Jun
Remainder of the paper. Due to space constraints, our main paper focuses on presenting results for the identity co- variance setting and defer details for the general covariance setting to the appendix; see also Appendix A for review on Gaussian distributions. THSTANDOPTTMIEEEAN is presented in Section 2 and the hardness result Lemma 3.2 is given in Section 3. Some experimental results illustrating the savings in sample complexity are shown in Section 4 before we conclude with some open directions in Section 5.
(e, () PAC learning in total variation) is 2 Ω Ing M This lemma gives an information-theoon
lower bound and is consequence of the generalized Fano's inequality.
To apply this lemma in the context of learning with ad- vice, we need to fix an advice a (mean or covariance, in the case of our problem) and find a large cover of distribu-
5

---

Learning multivariate Gaussians with imperfect advice
2. Identity covariance setting
By optimality of ja in Equation (1), we have
We begin by defining a parameterized sample count m(),e,)). Then, we will describe APpROXLI and show how to use it according to the strategy in Section 1.2.1.
1 7
yr
My:
1ul
(2)
Definition 2.1. For any d 2 1, è > 0, and å E (0, 1), we define m(d, e, 6) = e Ts = 16 (1 + [log ( (1)
By expanding and rearranging Equation (2), one can show (see Appendix C.2)
Given samples from d-dimensional isotropic Gaussian N (4, La) with unknown mean μ and identity covariance, the APPROXL1 algorithm partitions the d coordinates into w = [d/k] buckets each of length at most & E [d] and separately perform an exponential search to find the 2- approximation of the l2 norm of each bucket by repeatedly invoking the tolerant tester from Lemma 1.5. In the termi- nology of Definition 1.8, this is partitioning scheme with q 1, 1, and b- 1. Crucially, projecting the samples in R of N (p, Ia) into the subcoordinates of B S [d] yields samples in I B from ( [B) so we can obtain valid estimates using each of these marginals. After obtaining the l2 estimate of each bucket, we use Fact A. to obtain bounds on the L and then combine them by summing up these esti- mates: if we have an e-multiplicative approximation of each bucket's l, then their sum will be an ((f))-mutipllcatiive approximation of the entire la vector whenever the partition overlap parameters and of Definition 1.8 are constants.
2 n n
I1 11l2
gi i pe)
(3)
Meanwhile, it is known (see Lemma A.15) that
Pr(I Er gi 10000 2 v log (2 S 8. Therefore, using
Hölder's inequality and triangle inequality with the above, we see that, with probability at least 1 8.
1 11
S
gi p 11) S _
Σ gi
-1 pella
1=1
2
log (2d)
اللقا| + ||(0|11) S 4r.
gi
2+ log
zd
E O ( (5 log log g) we have |
When n2
In Appendix C.I, we give the pseudocode of the APPROXL1 algorithm and prove that it has the following guarantees.
1ll3 S 4r ity (see Theorem 10) and KL divergence of Gaussians (see Lemma A.8), we see that drv (N, Iz), (p. S
2log
4Ea. So, by Pinsker's inequal-
"
Lemma 2.2. Let k a, and Ç be the imput parameters to the APPROXLI algorithm (Algorithm 4). Given milk or, 8') i..dd samples from Nu, Ia). APPROXL1 succeeds with probability at least 1 - 8 and has the following properties:
V //d. (m, Ia), (N, La)) S v ddll m0l S E. Fi- nally, it is known that LASSO runs in poly (n, d) time.
1. If APPROXL1 ourputs Fail, then || > 5/2. If APPROXL1 outputs X E R, then |||||| S X S 2/h.
Using Lemma 2.3, we now ready to prove Theorem 1.1.
([d/k] a + 21]
Algorithm 1 The TESTANDOPTIMIZEEEN algorithm.
Now, suppose APPROXLI tells us that ||||| S r. We can then perform a constrained LASSO to search for candidate f Rd using O log 9 samples from N(u, Ia).
1: Input: Error rate O, failure rate 8 E (0, 1), parame- ter E [0, }), and sample access to N(p, Ia)
2: Output: çú Idd
3: Define k = [dtm], a =- -d (1-133))/2 C = 4 Vd.
Lemma 2.3. Fix d 2 L, r 2 O, and 8 > 0. Given OC log ) samples from NH, Ia) some unknown μ E Rd with ||||| S one can produce an estimate ja E Rdd in poly(n, d) time such that (Tv(N (u, La), (ū, (f,,a)) S with success probability at least 1 5.
5
and 8' = | [long c/al
> Note: Ç > 2a
4: Draw m(k: o., 8') i.i.d. samples from N(u, Ia) and store it into set S
>> See Definition 2.1
5: Let Out come be the output of the APPROXLI algo- rithm given k a, Ç. and S as inputs
E TR and X < evd then then Draw n E ( / i...d samples Vi....,y. E Rd 8: return çt argmin | x Σi lly: B
if Outcome
Proof. Suppose we get n samples y1, .1.....Y8. .n..... NN(,, La). For E [m]] we can re-express each y; as y; = a + g, for
9:
else
some gi ~ (0, La). Let us define ğú E Rd as follows:
10: Draw E (ddde² i.i.d. samples y1,... Yn E Rdd
11: return ğu - - Yi
> Empirical mean
1 ly: - -112
12: end if
p = argmin
(1)
6

---

Learning multivariate Gaussians with imperfect advice
Proof of Theorem 1.1. Without loss of generality, we may
sample complexity logarithmically, one may be tempted to use a larger value than Ç = 4e 4evd. However, observe that running APPROXLI with larger upper bound than Ç = 4 d would not be helpful since || > </4 whenever APpROXII currently returns Fail and we have ||||| S X whenever APPROXLI returns À E R. So, ev = </4 < || S ||||| S À and TESTANDOPTIMIZEMEANN would have resorted to using the empirical mean anyway.
assume that jı = 0. This is because can pre-process all samples by subtracting jı to yield i.i.d. samples from N II) where μí' = μ - fu. Suppose we solved this prob- lem to produce ji' where drv (N(,', Ia), N(T,, Ia)) & 10s, we can then output ÿ = 5 + já and see from data processing inequality that dTv(NN La), N(, Ia)) = drv(N Id). (Ni (+)) &
10e; see the coupling char-
acterization of TV in (Devroye et al., 2018).
Remark about early termination without the optimiza- tion step. If there is no Fail amongst {o1,-... 0n) and 4 TH 0² S E² after Line 10 of A then we could have just output ÿ = O₂ without running the optimization step. This ie because since 4 +y==1 of S E² would imply
Correctness of ji output. TESTAND gorithm 1) has two possible oulputs for ja: Case 1: P = argmin n > iimi - which can only happen when Outcome is À E I and < evd E.
(AI-
Case 2: j 1.2 7
1 l2 S via l = Σ}= | 1
S
1=1 of S g² and thus drv (N La), N Ia))
Conditioned on A I succeeding, with probability at least 1-6, we will show that drv Ia), N (ū, Ia)) S e and failure probability at most 8 in each of these cases, which implies the theorem statement.
dKL( Ia), ((P, Ia)
[ || 0
S via Pinsker's inequality (Theorem A.10).
Case I: Using r = Å as the upper bound, Lemma 2.3 tells us that dTv(N (I,, Ia), N (ūz, Ia)) S & with failure probability at most when (x) i.i.d. samples are used.
3. Hardness for the identity covariance setting
Theorem 1.3 is implied by Lemma 3.2, which depends on the following corollary of Fano's inequality.
Case 2: With (ddee)) samples, it is known that the empir- ical mean fi achieves drv (N (M, Ia), N (p, Ia)) S s with failure probability at most d; see Lemma A.1
Lemma 3.1 (Lemma 6.1 of (Ashtiani et al., 2020)). Let k : TE + T be function and let F be class of dis- tributions such that, for all s >> 0, there exist distribu- tions J,...,, as E F such that dxc,(fi;;j)) S n(e) and dTv (f. > 2E for all i j E [M]. Then any method that learns F to within total variation distance E with prob- log M (oe))og(1/e)
Sample complexity used. By Definition 2.1, APPROXL1 uses S m(k, a. 8') Ō(Vk/a²) samples to produce Out come. Then, APPROXL1 further uses ((X²/=t) sam- ples or O(d/s²) samples depending on whether X < evd. So, TESTANDOPTTMIZEEEEA
ability 2 2/3 has sample complexity Q
has a total sample complex-
ity of Ö vT a= + min { N $ ()). Meanwhile, Lemma 2.2 states that ||H||| S X S 2/k. . (Id/k] a 211m|11) when- ever Outcome is A E TR. Since (a + b) S 2a² 212 for any two real numbers b E R. we see that of E d o 0 (fe't [mlli) C o TTT
Lemma 3.2. Suppose we are given sample access to N Ia) for some unknown μe E Rd, and an advice j E Rd. Then, any algorithm that (e, 3 learns N (M, Ia) requires it (min I| illi d 11) 22 {}) samples.
X²
k Iell
Putting together the above observations, we see that the total sample complexity is
Proof. Without loss of generality, we can consider ju O since we can sample from N(u - pu, Ia) by sampling Nu,, Ia) and subtracting ÿú from each sample. Let fu denote the output of the learning algorithm.
k a²
d
min ( da²
+ k- ||llll
1, 52k
dea
Recall that dRI, (N I,), N( (I( = Ell
1'1.. For I| H'll2 I 1. it is known that dry (Devroye et al., 2018). Now, for any E show the existence of M ( d. A2 tions {fi). fi & N(u,, La). with |
Recalling that μ in the analysis above actually refers to the pre-processed μ jú, and that TISTANDOPTMIIEEEAANN sets k: = [d'n]] and a = (1-312)) with 0 < 7 S 4. the above expression simplifies to
Ia)) E I|m-''l 1 200
see
0. we
distribu-
(d - + min f(u, c d, m,)))) 2
d
X and ||,, - M2ll2 E <E' vi #j E [M] As long
as g' S 2. the above implies that dry f3) 2 200 and min minfdRL (f+lf), dkL(( S 2(())2
d'
||ايم where f(u, ur, d, n))) = 21- 2
Remark on setting upper bound Ç. As Ç only affects the
Taking & = 400 such a cover fi,..., fM will satisfy
7

---

Learning multivariate Gaussians with imperfect advice
7-
lest mo0oimiee Firghtio
Ferplion
6-
6
5-
3-
2-
50
150
250
250
300
100
150
250
302
50
150
200
250
300
Number of samples
Number of sompless
Mumber samples
Figure 2: Here, d 500, s {100, 200, 300), and 9 || f
50. Error bars show standard deviation over 10 runs.
Op Eir prrical
Emprriaal
4-
3-
2-
2-
50
250
250
samptea
Number
Figure 3: Here, d = 500, 100, and = || - 20/11 E {0.1, 20,30,, Error bars show standard deviation over 10 runs.
the conditions of Lemma 3.1 with r(E)) = 4002 E? This gives a sample complexity lower bound of n (min {d. | Plog]//e) for (e, PPCP learn- ing in TV distance given advice.
line of Algorithm 1 versus returning the empirical mean as in line 11. As such, we do not invoke APPROXI. but instead explore how to || #ALGll2 behaves function of 14 Íاll: and number of samples, where ALG is either our TESTANDOPTIMIZE approach or simply computing the empirical mean. For reproducibility, our code and scripts are provided in the supplementary materials.
Construct M1...., Mas as follows: Choose
min {d. J. By the Gilbert- Varshamov bound, for any
k> 4, there exists a code S 13 with pairwise Ham- ming distance E [k/4, k] such that |C| 2 EE2-1 2
We perform two experiments on multivariate Gaussians of dimension d = 500 while varying two parameters: sparsity [d] and advice quality q E R R-0- In both experiments, the difference vector μ j Rd is generated with ran- dom = /s values in the first s coordinates and zeros in the remaining d - coordinates. In the first experiment (see Figure 2). we fix 50 and vary E {100, 200, 300). In the second experiment (see Figure 3), we fix s = 100 and vary g E {0.1, 20, 30). In both experiments, we see that TESTANDOPTIMIZE beats the empirical mean estimate in with the diminishing benefits q or increases.
20(1) (via Stirling's approximation).
With M = 20(k), choose such a code C and get (UI....,UM S [=1] by applying (I1,..., xx) H ((-1)=i...., (-1)ak) (-1)*) to each æ E C. The first coor- dinates of each μ4 E Rd are set to å/ v; and the remain- ing d le coordinates are set to O. Then, by construction, [p, اlll ||m/|| k (2)
A for each μ. and [e: M1ll2 (2+) v w0 uy loo- Thus, we will have Lr.- -11l2 E
terms of incurred Eg error (which translate directly to drv).
2 2A for each # j E [M].
VK vk
For computational efficiency. we solve the LASSO optimization in its Lagrangian form Ñ argmingeR n E lly, - B1B + A| us- method
4. Experiments
Here, we explore the sample complexity gains in the identity covariance setting when one is given high quality advice, specifically the benefits of performing the optimization in
ing the LassoLa instead of the equivalent penalized form. The value of the hyperparameter À is chosen using 5-fold vross-validation.
8

---

Learning multivariate Gaussians with imperfect advice
5. Conclusion
Iith Innovations in Theoretical Computer Science Con- ference (ITCS 2020). Schloss Dagstuhl--LcinnnzzZZenmn für Informatik, 2020.
We propose a learning-augmentt algorithm for learning multivariate Gaussians that incorporates property testing as subroutine, where the advice quality is stated in terms of & error, and provide matching information-theoreti lower bounds. While running our experiments, we observe interesting phenomenon: the rate of improvement does not worsen as & increases if we fixed the lo sparsity; see Ap- pendix E. As such, it would be interesting to show theoreti- cal guarantees with advice error in the fo-norm.
Antoniadis, A., Gouleakis, T., Kleer, P., and Kolev, P. Secre- tary and online matching problems with machine learned advice. Advances in Neural Information Processing Sys- tems, 33:7933-7944, 2020.
Antoniadis, A., Jabbarzade, P., and Shahkarami, G. A Novel Prediction Setup for Online Speed-Scaling. In 18th Scan- dinavian Symposium and Workshops on Algorithm The- ory (SWAT 2022). Schloss Dagstuhl-Leibniz- Zentrum für Informatik, 2022.
Leibniz-Zentrum
Acknowledgements
AB: This research was supported by the National Re- search Foundation (NRF), Prime Minister's Office, Sin- gapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme, by the NRF-AI Fellowship R-252- 1100000----880 Amazon Faculty Research Award, and Google South & South- cast Asia Research Award.
Ashtiani, H., Ben-Davis S., Harvey, N. J. A., Liaw, C., Mehrabian, A., and Plan, Y. Near-optimal sample com- plexity bounds for robust learning of gaussian mixtures via compression schemes. J. ACM, 67(6), oct 2020. ISSN 0004-5411, doi: 10.1145/3417994, URL https: / // /doii. org/10 0. 1 1 444534417999
Bamas, É., Maggiori, A., Rohwedder, L., and Svensson, O. Learning Augmented Energy Minimization via Speed Scaling. Advances in Neural Information Processing Systems, 33:15350-15533 15359, 2020a.
DC: This research/project is supported by the National Research Foundation, Singapore under its AI Singa- pore Programme (AISG Award No: AID2-PDD/2021- 08-013).
Bamas, E., Maggiori, A., and Svensson, O. The Primal-Dual method for Learning Augmented Algorithms. Advances in Neural Information Processing Systems, 33:20083- 20094, 2020b.
TG: This research was partially supported by MoE AcRF Tier A-80009880000-00 while at NUS and by an NTU startup grant while at NTU.
Bernardini, G., Lindermayr, A., Marchetti-SSaaceee Spaccamela, A.,
Megow, N., Stougie, L.., and Sweering, M. A Universal Error Measure for Input Predictions Applied to Online Graph Problems. In Advances in Neural Information Processing Systems, 2022.
Impact Statement
This paper presents work whose goal is advance the field of Machine Learning. It addresses the abstract problem of PAC learning high-dimensional Gaussians, and hence does not have any direct societal impact. There are potential indi- rect societal consequences of our work (through algorithms that use Gaussian learning), none which we feel must be specifically highlighted here.
Boyd, S. and Vandenberghe, L. Convex optimization. Cam- bridge university press, 2004.
Cai, T. T. and Ma, Z. Optimal hypothesis testing for high di- mensional covariance matrices. Bernoulli, 19(5)32335- 2388, 2013.
References
Chen, J., Silwal, S., Vakilian, A., and Zhang, F. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pp. 3583-3600 PMLR, 2022.
Agrawal, P., Balkanski. E., Gkatzelis, V. Ou, T., and Tan, X. Learning-augmentee mechanism design: Leveraging predictions for facility location. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 497-528, 2022.
Choo, D., Gouleakis, T. and Bhattacharyya, A. Ac- tive causal structure learning with advice. In Interna- tional Conference on Machine Learning, pp. 5838-5861 PMLR, 2023.
Aliakbarpour, M., Indyk, P., Rubinfeld, R., and Silwal, S. Optimal algorithms for augmented testing of discrete distributions. arXiv preprint arXiv:2412.00977 2024.
Choo, D., Gouleakis, T., Ling, C. K., and Bhattacharyya, A. Online bipartite matching with imperfect advice. In International Conference on Machine Learning. PMLR, 2024.
Angelopoulos, S., Dürr C., Jin, S., Kamali, S., and Re- nault, M. Online Computation with Untrusted Advice. In

---

Learning multivariate Gaussians with imperfect advice
Devroye, L. and Lugosi, G. Combinatorial methods in density estimation. Springer Science & Business Media, 2001.
Gollapudi, S. and Panigrahi, D. Online Algorithms for Rent- or-Buy with Expert Advice. In International Conference on Machine Learning, pp. 2319-2327. PMLR, 2019.
Devroye, L., Mehrabian, A., and Reddad, T. The total variation distance between high dithenimensionl gaussians with the same mean. arXiv preprint arXiv:1810.08692, 2018.
Gouleakis, T., Lakis, K., and Shahkarami, G. Learning- Augmented Algorithms for Online TSP on the Line, In 37th AAAI Conference on Artificial Intelligence. AAAI, 2023.
Diakonikolas, I. Learning structured distributions. Hand- book of Big Data, 267:10-1200 2016.
Hastie, T., Tibshirani, R., and Wainwright, M. Statistical learning with sparsity. Monographs on statistics and applied probability, 143(143):8, 2015.
Diakonikolas, I., Kane, D. M., and Stewart, A. Sta- tistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 73 84, 2017. doi: 10.1 N0.1109/FCSS.217.11
Horn, R. A. and Johnson, C. R. Matrix Analysis. Cambridge University Press, 2012.
Huang, B., Jiang, S., Song, Z., Tao, R., and Zhang. R. Solving sdp faster: A robust ipm framework and efficient implementation. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 233- 244. IEEF, 2022.
Diakonikolas, I., Kane, D. M., and Pensia, A. Gaussian mean testing made simple. In Symposium Simplicity in Algorithms (SOSA), pp. 348 0-2...222222 SIAM, 2023.
Kamath, G., Li, J., Singhal, V., and Ullman, J. Privately learning high-dimensional distributions. In Conference on Learning Theory, pp. 1853-1902. PMLR, 2019.
Dinitz, M., Im, S., Lavastida, T., Moseley, B., and Vassilvit- skii, S. Faster matchings via learned duals. Advances in neural information processing systems, 34: 14:10393-00 2021.
Klivans, A., Stavropoulos, K., and Vasilyan, A. Testable Learning with Distribution Shift. Conference on Learn- ing Theory (COLT), pp. 2887-2943. Proceedings of Ma- chine Learning Research (PMLR), 2024.
Dütting, P., Lattanzi, S., Paes Leme, R., and Vassilvitskii, S. Secretaries with Advice. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp- 409-429, 2021.
Kraska, T., Beutel, A., Chi, E. H., Dean, J., and Polyzotis, N. The Case for Learned Index Structures. In Proceedings of the 2018 international conference on management of data pp. 489-504, 2018.
Foucart, S. and Rauhut, H. A Mathematical Introduction to Compressive Sensing. Birkhäuser Basel, 2013. ISBN 0817649476.
Lattanzi, S., Lavastida, T., Moseley, B., and Vassilvitskii, S. Online Scheduling via Learned Weights. In Proceed- ings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1859-1877. SIAM. 2020.
Freund, R. M. inite Programming
Introduction to Semidef- URL
https: https:://cw..rt (SDP), 2004.
15=0883=--onllaaarrrrproaamm---- 20 Mitzenmacher, M. A Model for Learned Bloom Filters, and Optimizing by Sandwiching. Advances in Neural Information Processing Systems, 31, 2018.
453255666222283355574333333338 @ec23_semidef_____
MIT OpenCourseWare.
Gärtner, B. and Matousek, J. Approximation Algorithms and Semidefinite Programming. Springer Science & Business Media, 2012.
Purohit, M., Svitkina, Z., and Kumar, R. Improving Online Algorithms via MI. Predictions. Advances in Neural Information Processing Systems, 31, 2018.
Ghosh, M. Exponential tail bounds for chisquared random variables. Journal of Statistical Theory and Practice, 15, 2021. doi: 10.10077:44511--200000 56-xx
Rubinfeld, R. and Vasilyan, A. Testing distributional as- sumptions of learning algorithms. In Proceedings the 55th Annual ACM Symposium on Theory of Computing, pp. 1643-1656, 2023.
Gkatzelis, V., Kollias, K., Sgouritsa, A., and Tan, X. Im- proved price of anarchy via predictions. In Proceedings of the 23rd ACM Conference on Economics and Compu- tation, pp. 529-557, 2022.
Tibshirani, R. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-22) 1996.
10

---

Learning multivariate Gaussians with imperfect advice
Tibshirani, R. The lasso method for variable selection in the cox model. Statistics in medicine, 16(4):385-395, 1997.
Vandenberghe, L. and Boyd, S. Semidefinite Programming. SIAM Review, 38(1) 3:49-99 1996.
Vasilyan, A. Enhancing Learning Algorithms via Sublinear- Time Methods. PhD thesis, Massachusetts Institute of Technology, 2024.
Vershynin, R. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 101 1.3027, 2010.
Vershynin, R. Lectures in geometric functional analysis, 2012.
Vershynin, R. High-dimensional probability: An introduc- tion with applications in data science, volume 47. Cam- bridge university press, 2018.
Wang, S., Li, J., and Wang, S. Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice. Advances in Neural Information Processing Systems, 33: 8150-8160, 2020.
Zhang, F. The Schur Complement and Its Applications. Springer, 2005.

---

Learning multivariate Gaussians with imperfect advice
A. Preliminaries
For any integer d 2 1, we write [d] to mean the set of integers [l....,dl, d]. We will write V ~ N(u, Σ) to mean drawing a multivariate Gaussian sample and MM (v....., ViMI to mean a collection of [M] independently drawn such vectors.
In the rest of this section, we will state some basic facts and lemmas that would be useful for work. Most of them folklore results and we supplement proofs for them when we could not nail down direct reference.
A.1. Matrix facts
Fact A.1 (e.g. see Exercise 5.4.P3 of (Hom & Johnson, 2012)). Letx Rdd be an arhitrary d-dimensional real vector. Then,
the & and l2 norms of x are defined as ||x||] Ei [x| and ||x||2 = E x? respectively, They satisfy the inequality:
|xx|2 $ |x||1 S Vd. ||x||2-
For real matrix M E Raxd define its vectorized form vec(M) Rdd by vec(M) (M Ma,a) and we see that | = [[vee(M)] We recover a matrix given its vectorized form via M = mat(vec(MM), For any matrix A, we use min (A) to denote its smallest eigenvalue. Note that for any full rank matrix A E Rdxd, we have
TAT - | -1 22. ||A I || I vd ||A||2 (e.g. see Exercise 5.6.P23 of (Horn & Johnson, 2012)), and || =
|vec A) < (A)c(A)]l: 1|1 & vd. ||vec(A)) 22. For any two matrices A and B of the same dimension, we also know that JAB |F S min | ||2 B IF, ||
Lemma A.2 (Chapter 5.6 of (Horn & Johnson, 2012)). Let A and B be two square real matrices where A is an invertible matrix Then, ||AB| = /A||
Proof. Exercise 5.6.P58(b) of (Horn & Johnson, 2012) tells us that || = |[BA]] when A normal and B is Hermitian. Since normal matrices are invertible and every real matrix is Hermitian, the claim follows.
Lemma A.3. Let A and B be two square d x d matrices where A is invertible matrix with a square root. Then, ||A 1122BA 1/2 /|| = A B
Tall
Proof. ||A -|/2B/B - 1/2
Lall = 1 - A1/2) A 111 = ||A 1/2 1/2B 1/2-A-----AA = |A A Lall.
Definition A.4 (Projected vector). Let (x1,...,, Xa) E Rd be a d-dimensional vector and B {61 (f1,..-,ful (m) C [d] be
subset of 1 < S d indices, where i < ... < iw. Then, we define XB = (X.,...., xi.) E R as the projection of the
vector x to the coordinates indicated by B.
Lemma A.5 (Trace inequality). For any three matrices A, B, E Rdxd, we have Tr(ABC) S ||vec(BA)]] ||C||2.
Proof. Let (M)) ..... (MMM) denote the eigenvalues of a matrix M E Raxd
TH(ACC) < Σ A((AB) A((C)
(by von Neumann trace inequality)
CA(AA)- (.(C)
(e.g. see Theorem 1.3.22 of (Horn & Johnson, 2012))
Σ ((BA) A(()
(BA) CC)
(Hölder's 's inequality)
(BA)
Σ (BA) max (C)
(Definitions of vector & and tor norms)
Σ M(BA)) |CIl2
(Definition of matrix spectral norm)
12

---

Learning multivariate Gaussians with imperfect advice
It remains argue that E, (BA) ||ve(BA)]]ı To this end, consider the singular value decomposition (SVD) of
BA UEV with unitary matrices U, V and diagonal matrix Σ diag(o1,-..., vd). Let denote the eigenvalues of BA by o1y..., oa and the columns of BA by 2i...... 2d R Then,
E (BA]I & Σ oi
(e.g. see Equation (7.3.17) in (Horn & Johnson, 2012))
-Tr=>)
(By definition of Σ)
=Tr(V VU UE)
(Since U and V are unitary matrices)
=T(VU U
(By eyelic property of trace)
=Tr(VU BA)
(By SVD of BA)
Σ (VU 2,),
(By definition of trace)
|VU 2:112
(Since (VUT 22)? is just term in summation of || z 12)
| l
(Since and V are unitary matrices)
d
(Since b2 S 61)
1=1
(BA)
(By definition of vector 4 norm)
| BA
(By definition of |ee (BA)
Putting together, we get (ABC < E, [A((A)) |Cl|2 & ||vec |a ||C||2 as desired.
Lemma A.6. For any two matrices A, B E IRd we have vec A B|] < |eo A ][| + [|veo(B)]] and ||vec[ AB) || S
||vec(A] A]] [|vec(B)]]1
Proof. To see ||vec(A A + B1I S ||vec(A)] + |lee (rec(B)ll..
observe that
d
d
|vec A + B)Il1
Au + Bul S
Byl |]vec()]] + [|vec(B)]]
==1=1
To see |/vco(AA)) < ||voc[ (A)lli ||vec[ B BB]l1 observe that
d ΣΣ Σ
|vec(AA)]]
A B
Auj
Σ
Bykl
=|]vec[A)]lz -
||vee(B)) (B)
Aml Am
Am
A.2. Distance measures between distributions
Definition A.7 (Kullback-Leibler (KL) divergence). For two continuous distributions P and Q over X.
/
P((x)
dKL (P, Q)
P(x) log
dx
XXX
Q(xx
Note that KI. divergence is not symmetric general.
13

---

Learning multivariate Gaussians with imperfect advice
Lemma A.8 (Known fact about KL divergence). Given two d-dimensional multivariate Gaussian distributions P Nup, Ep) and Nug, E where Ep and 2g are invertible, have
1 (P,
Ep) d (mo - up)) Σ (mo 1p) + In (1<(X//>))
det Ee det Ep
1
((P up) -0' (me up) + |
2
where X 12122p
Op 2
1/2
La with eigenvalues A da. In particular, dKL(P, (P,2) =b11me Hp when
Ep Σg Ia and dkt. (P, 2)
< \ X when ut P.
Proof. Let P ~ N(p Ep) and Q ~ N Σe) be two d-dimensional multivariate Gaussian distributions where Ep and Dg are full rank invertible covariance matrices.
By definition, the KL divergence between P andd is
1 (Tr(Eg'>)) Ep) d (ug ppp) Ex (ng 1p)) + In
( det Σe det Ep
deL. (P,, (P,
(4)
1/2 Ia with eigenvalues .1,..., Ap- Note that X is invertible because Ep and De are invertible, Λ1 A1:..., Ad 0. Then, Equation (4) can be upper bounded as
Let define the matrix X E
1/2 1/1 Ep E.
dRL (P,0) (Ir(2g -p) Ep) d (uo -ppppppp) 0Φ (me up) + In
det Ee det En
$ 2 ((HQ - Up) De (mo -pP) + +X|)) (5)
This is because Tr(Eo- Σp) = "/<=""/"pp""""" = Tr(X + Ia) = Tr(X) + and
del. Σg
-In
det Ep det EE))Ep) In (X Ia)
(1 X₂)
d In(1 + Ar) 2 Σ (A: - x2) Tr(X) - x² -Tr())xX-) - 1 D
d
d
2=1
where the inequality holds due to Aı,..., 0.
When Σp Eg = I,, Equation (4) reduces (P, =b1lme 1pl12. Meanwhile, when μpp 1M Equation (5) reduces dKL Q) < ().
Definition A.9 (Total variation (TV) distance). For two continuous distributions P and Q over domain X, with density functions f and g respectively, drv (P, Q) = fxex [x() g(x) dr.
Theorem A.10 (Pinsker's inequality). IfP and Q are two probability distributions on the same measurable space, then (P, Q) S (P,
A.3. Properties of Gaussians
The following are standard results about empirical statistics of Gaussian samples.
Lemma A.11 (Lemma C.4 in (Ashtiani al., 2020); Corollary 5.50 in (Vershynin, 2010)). Let ......, 8n N(0, Ia) and let c 1 t f. n 2 co e²
Pd for some absolute constant Co, then
Pr
gig.
I
< 2 2xxp(-Ed)
1=1
14

---

Learning multivariate Gaussians with imperfect advice
Lemma A.12 (Folklore; e.g. Appendix C of (Ashtiani al., 2020)). Fix e, (0, 1). Given 2n i.i.d. samples (1,, Σ) for some unknown mean it and unknown covariance E, define empirical mean and covariance
X2n X1y...9
1
2n
as
and Σ
a22 Σ
n
221-1)(022 121-1)
2n
2n
1=1
Then,
When n E O
& (
we have Pr (dTv(N M), N(ū E)) Se) 2 8
we have Pr ((ā -1) p1) M - (īt 1)) 14 5 2 1-8 d+ (log(11))
When n E O
g²
Lemma A.13 (Properties of empirical covariance). Let Σ E RRdxdd be the empirical covariance constructed from iid. samples from N (0, Σ) for some unknown covariance E. Then,
When n = d, with probability 1, we have that E and E share the same eigenspace.
Let d1 S ... S Xa and dn S...
S da be the eigenvalues of E and E respectively. With probability least 1 5, we
have 3i < 1+0
d++ 1/8
Proof. For item let S be the rank of E. We consider the case of the d-dimensional Gaussian with zero mean
I, 0
and covariance r, = 0 0] where I, denotes the r-dimensional identity matrix and the zero-padding is added when
r < d. Note that there is an invertible transformation between samples from NO,, (,) and N(0 Σ) with samples from (O, r,) having the r + +,.... d coordinates fixed to 0. Now, let us denote the i-th standard basis vector by e, and apply an induction argument on from 1 to d. The base case (r 1) is obviously true since a single sample æ will span {er } unless 11 O, which will happen with probability 0. When > by strong induction, samples T1..... .y will not span {ei,.... (ei,...,ery er) only if the r-th sample æ, lies in the subspace spanned by æ1,-.., - This is measure event under the r,) measure.
For item 2, see Fact 3.4 of (Kamath et al., 2019).
Lemma A.14. Fix n 2 and d 2 1. Suppose E Rd is hidden mean vector and we draw n samples Xi,..., Xn N(, Ia). Define z, = vn Ei= X; and yn ||z Then,
1. follows the non-central chi-squared distribution Xa (² (A) Var(yn) 2d + 4X.
X nll This also implies that Elynn] d + X and
2. For any t >>> 0.
t
Pr(y. > d+ tt S exp
log 1+
2 d 2X
d 2A
d12
exp
"4(d + 21)(d 22 +t)
3. For any t E (0. (0.d+1 A),
t
Pr(y, < <d+ À S
+ log
1
2
d + 2X
d d 21
dt2
- exp
4(d 2X)2
15

---

Learning multivariate Gaussians with imperfect advice
Proof. The first item follows from the definition of the non-central chi-squared distribution, noting that the random vector Zn distributed as N (Vvū- μr, Ta)- The second and third items follow from Theorems 3 and of (Ghosh, 2021) respectively.
Lemma A.15. Suppose 81. B1...... ..... (0, Ia). Then,
2d
Pr
Σ
gi
2
2n log
8
Proof. Since gl...., Bn (0, we see that y gi + + gn (0,,nda) nla). Furthermore, each coordinate i [d] of y; (y1..... yd) is distributed according N(0, n). By standard Gaussian tail bounds, we know that Pr(lud 2 1) S exx for any E [d] and 0. So.
2
2d 5
2d
Pr
g
log
Pr
loo 2
2n log
i=1
2d
Pr
max ||vall ic(d]
2
2n log
5
2d
2
Pr
|12all 2
2n log
(Union bound over all d coordinates)
1=1
2n log
- 2dexp
(Setting = 2n log (24)
2n
8
B. Additional results
B.1. Tolerant testing
In this section, present algorithm for testing whether unknown distribution is close standard normal distribution. More specifically, we first describe tolerant tester for the property that the mean of an isotropic Gaussian distribution equals zero. Subsequently, we present tolerant tester for the property that the covariance matrix equals the identity matrix.
B.I.I. TOLERANT TESTING FOR MEAN
The definition of tolerant tester for the mean of isotropic Gaussian distribution is given below.
Definition B.1 (Tolerant testing of isotropic Gaussian mean). Fix 1, d E, > E1 > 0, and d 0. Suppose E IR is a hidden mean vector and we draw m samples XI,... ....... Xm ~ ((,, An algorithm ALG is said to be (E1, 3)-tolrrant isotropic Gaussian mean tester if it satisfies the following two conditions:
1. If [4ll < f1, then ALG should Accept with probability least 1
2. If |||1|2 2 $2, then ALG should Reject with probability least 6.
ALG is allowed to decide arbitrarily when E1 < || < E2.
It is known that the test statistic yı || J Σ x can be used for non-toleraní isotropic Gaussian mean testing with an appropriate threshold; see Appendix C of (Diakonikolas et al., 2017). With the following lemma we show that yo can also be used for tolerant isotropic Gaussian mean testing.
Lemma B.2. Fix 2 d 62 81 0, and 8 > 0. Suppose μ Rdd is hidden vector and draw i.i.d. samples XI,...,Xop ~ N (1,, La). When d > (21, -)-tollrant isotropic Gaussian mean tester.
16c2 2
and m E O log (t)). TOLERANTIGMI (Algorithm 2)
16

---

Learning multivariate Gaussians with imperfect advice
Algorithm 2 The TOLERANTIGMT algorithm.
1: Input: 82 > 81 > 0, 5 & (0, 1), m i.i.d. samples of (1,, La), where la E Rd
2: Output: Fail (too little samples), Accept (1 S E1), or Reject (I|el22 2 E2).
3: Define sample batch size
16v4 c
4: Define number of rounds log( ) if log( ] is odd, otherwise define + [log( 1
5: Define testing threshold + te
6: if m < then
7: return Fail
8: else
9: for E r) do
10: Use unused batch of n i..d. samples xi ..... Xx (I)
11: Compute test statistic yn (+) = VT
1
E x for the 7th test
12: Define th outcome ((0) as Accept ym S r. and Reject otherwise
end for
return majority(R ,...,
15:
end if
Proof. The total number of samples m required is nr O samples in each of the (logg })) rounds.
Vd c
log (t) since TOLERANTIGMT uses
16v
i.i.d.
53 -
For correctness, will prove that each round i (1....,r) succeeds with probability least 2/3. Then, by Chernoff bound, the majority outcome out of log( 12) independent tests will be correct with probability at least 1 ò.
r). Now, fix an arbitrary round i E (l,...,ry. TOLERANTIGMT uses
16vd -
2 1 ii.d. samples to form statistic yn and
tests against the threshold r = d + nee +23) From Lemma A. 14 (first item), we know that ym Xa (A) a non-central
2
chi-square random variable with À = n nl1 Let us define = m(e3-sf) > 0. Observe that we can rewrite the testing
threshold 7 in two different ways: T = d +c2 = d + nst + = d + n t.
Case 1: 1 S E1
In this case, we have x = nl|uul13 S ne? and r + nE? + So.
Pr(y! > = Pr(y d + n t)
(since -= d nee
$ Pr(y (8)
> d + 1)
(since S nEt))
di2
< exp
(apply Lemma A.14 (second item) with / > 0)
4(d+ 2X) + 2X +1)
d12
S exp
(since À S ncf))
4(d+ 2n= 2n
dn² - 2
(since - n(es-si) < 2n(e ef))
< exp
16(d + 2n () (d 2n
162
16/d (since
exp
16(d + 2nc 2no (d 2n
2/ -
16
exp
(dividing both numerator and denominator by 16d
2nu? 1 + d
1+
2ns
16
16v7 (since
exp
32c?
(1
32:2
-
Vdle3 +
Vile -f
17

---

Learning multivariate Gaussians with imperfect advice
16
16c c
16c
exp
(since d 2
2
(1 + 2)(1 + 2)
16
exp
9 <
Thus, when ||al|2 S EL, we have Pr(yn (0) at least 2/3.
T) 2 2/3 and the 7th test outcome will be correctly an Accept with probability
Case 2: |el| 2 82
In this case, have x nl|mu12 2 ne3 > net and d + no3 t. We first observe the following inequalities:
Since n 2 1, d 2 1, nEz. and E2 >
E1 > 0, we see that
net
nE²
2
2
dd (1
2 +2)
2
2
2
and
1
+2
(6)
A
NE
Since
16yd -
2 1 and d
d>
16:3
2 1, we see that
c2--8
(1+
2n03
2
s 32
(7)
So,
Pr(v (
<T) = Pr(y (0 < d nEn - t)
(since r d + nEz t)
Pr(v
dd+ X (A + ns²))
(Rewriting)
d(A + t n2
exp
(apply Lemma A.14 (third item) with 0 < À + ne² < A)
4(d + 22)2
d(A - 5o 302)²
nlo3
exp
(since
4(d + 2사)2
2
(2 "s"
exp
(Pulling out the factor of from numerator)
16
4 2)
1 2
d
S exp
(by Equation (6)
+ 2) 2
16
d
2
(83 e))
S exp
(Pulling out factors of n, d, and E
2
16d
1 +
d
16
(since n 16v/
exp
(1 + no?
16
16
exp
exp
(by Equation (7))
32
9
Thus, when ||aa||2 2 E2, we have Pr(y (4)
r) 2 2/3 and the tt test outcome will be correctly a Reject with probability at
least 2/3.
18

---

Learning multivariate Gaussians with imperfect advice
We ready state the main theorem below.
1622
Lemma B.3 (Tolerant mean tester). Given 62 é1 0, (0, 1), and d d2
there is tolerant tester that
-
O Va log (t) i.i.d. samples from (u, Ia) and satisfies both conditions below:
1.
p4 E1, then the tester outputs Accept,
2. If |||l| 2 then the lester oulputs Reject, each with success probability at least 1 1-d. 6.
Proof. Use the guarantee of Lemma B.2 on TOLERANTIGMT (Algorithm 2) with parameters 81 and 82 2e.
B. 1.2. TOLERANT TESTING FOR COVARIANCE MATRIX
We now give the definition of a tolerant tester for the unknown covariance matrix being equal to identity.
Definition B.4 (Tolerant testing of zero-mean Gaussian covariance matrix). Fix m 2 1, d 2 62 > E1 0, and ő > 0. Suppose Σ E Rdxd is hidden full rank covariance matrix and we draw m samples X1..... ~ NO, Σ). An algorithm ALG is said to be a (21, 8 tolerant zero-mean Gaussian covariance tester it satisfies the following two conditions:
1. If | Ta|lr v & then AL. should Accept with probability least
2. If] E LallF 2 é2, then ALG should Reject with probability at least 1 - 6.
ALG allowed to decide arbitrarily when E < Σ Lall2 < 82.
Definition B.5 (Test statistic T,). Let .,...., En be iidd samples from ~ (N,,, Σ) for an unknown E E Rdxd For i * j. we define h(,,, 2z) = (z, 2z)² 2 (x) n. + 2 2z) + d. Then, we define Tn as
2
Σ
Tn n(n 1)
ISi<jšn
It is known that the test statistic T. (Definition B.5) can be used for non-tolerant zero-mean Gaussian covariance testing with an appropriate threshold; see (Cai & Ma, 2013). With the following lemma, we show that Tn can also be used for tolerant zero-mean Gaussian covariance testing.
Algorithm 3 'OLEEANTZMGGT
1: Input: 82 81 5, 5 (0, 1), i.i.d. samples of N(0, E), where E Rdxd
2: Output: Fail (too little samples), Accept (|Σ 1all d Reject (|
Lall > si)
3: Define sample batch size 3200 d max
37 /
4: Define number of rounds log( 42) if [log( 12)] is odd, otherwise define
+ [log( 2
5: Define testing threshold ci+e
6: if m < nr then
7: return Fail
8: else
9: for E (l....,r) do
10: Use unused batch of n i.i.d. samples x( ..... x NN E)
Compute test statistic T.(1) according to Definition B.5 for the 5th test
11:
12: Define ith outcome R(1) as Accept if T and Reject otherwise
13: end for
14:
return majority( ...., R((r)) ((.,).....
15:
end if
19

---

Learning multivariate Gaussians with imperfect advice
Lemma B.6. Fix m 1, d 1, E2 e1 O, and > Suppose E E Rdxd is hidden full rank covariance malrix and draw iid. samples X1,... Xm (O, Σ). When d 2 E2 and
m O d max
1
22
log
1 5) )
2
-
TOLERANTZMGCT (Algorithm 3) is 62,,
E2, 8 zero-mean Gaussian covariance tester.
To prove Lemma B.6, we first state the expectation and variance of Tn known from (Cai & Ma, 2013), and give an upper bound on the variance that will be useful for subsequent analysis.
Lemma B.7 ((Cai & Ma, 2013)), For the test statistic Tn defined Definition B.S, we have E [m) = || - Iall and
(Tx) = 4 nj (>*) + Tr(=*)] + T> ).
bdd then | d (1+ 3 vn )²
Lemma B.8. Fix n 2 1, E E Rdxd, and b > 0. 1 La 11
Proof. Since the matrices can be treated as vectors in Rdd and then the Frohenius norm corresponds to the &g norm, we see that
| F S | Ialle +
||allF
(Triangle inequality)
d b. V n
+ Vd
(Since |/ I 6'd and | = d)
= Vd 1+ vn
Therefore, E < d. (1 + b vn )² desired.
Lemma B.9. Fix 2 1, 2 2, E E Rdxd, and b 2 0. If E
Ial
bdd n.
then for the test statistic Tn defined in
Definition B.5, we have
64d
(1+ n m 1
82
6²
o (In) S n²
+ +
n
Proof. We begin by observing two simple upper bounds for Tr(E') and Tr Tr E - 1))
Tr(E') اー < E Σ
=
(8)
Since E(E - La) - ニ= --- 1,), i.. Σ and Σ
Ia commute, we have
1 E
L -ー | -L Tr(=3) Tr((E - Ia)3)
(9)
(T,)
4
TT> T+()')] + 8 - 1,)3)
(By Lemma B.7)
n(n- - 1)
n
8
[T2 + (n TrE I,)
(By Equation (8))
n(n
8
T ( + TT(E3) Tr((E I2)3)]
(By Equation (9)
n(n 1)
8
Th(=²) (T<=))) 1) Tr(E 1))3)]
n(n-1
20

---

Learning multivariate Gaussians with imperfect advice
8
Tr(=3)- [Tr(>3) +n- Tr((2- 1a)
(Since Tr((2 La) 2 0)
n(n -1 1)
8
vnl )
b
2
b 2
d
1+
d 1
+n n Tn-Tr(E2 L))²)
n(n - 1)
vn)
(Since Tr(>²) = |>1| and by Lemma B.8)
8
d.
1+
2
d
1+
2
+
6
(Since Tr((E - = ΣΣ Iall 5²d)
Ia)²)
n(n - 1)
Vn
vn
8df
b
2
2
1+
1+
+
62
n(nn- 1)
vnl
vn)
16df
b
2
(1+
b
2
+
+
(Since n 2 2)
112
vTi
vn
64d
b22
b²
+
1+
+
b²
(Since (a bb² S 2a.2 2b²)
n²
n
n
Proof of Lemma B.6. Let us define Asy max
1
2
.2
O and suppose ||
Ial bdd for
27'
2--c7
some b 120 0.
The total number of samples m required is nr e O (d Den,ez log (b)) since TOLERANTZMGCT uses n -3200-- 2-00-d i..dd samples in each of the E O(log())) rounds.
For correctness, we will prove that each round i E (I....,,r) succeeds with probability least 2/3. Then, by Chernoff bound, the majority outcome out of r 2 log( 12) independent tests will be correct with probability at least 1 1-6.
Now, fix an arbitrary round E (1....,r). r). TOLERANTZMGCT uses n = 3200 d Ae,,2 i..d. samples to form a statistic T (Definition B.5) and tests against the threshold T Std..
Case 1: Σ La 1/ S o?
We that
n 82 = d
1 I 1
(Since | I b2d
3200
| Iall?
(Since n 3200 d )2)
3200 A A ot
(Since - Ial 2 $
and
6²
Σ
Lall
1
+
(Since ||
La bi'
n1
d
2
<
+
(Since | 1-Iaa S $ì
< 2
(Since 2 E E?)
So.
64d
12
(1 (1+ 12
(²(TT)
<
1
12
(By Lemma B.9)
n2
64d
2
(2
3200----
+
(From above)
n2
64-2
1
(2+3200 3200
Der.ez =7)
(Since n = 3200 d A
3200
2
61,00
21

---

Learning multivariate Gaussians with imperfect advice
64.2
1
3202
(Since AEL.Z 2 1)
3200
64 2 3202
2
(E)
=72²
(Since
5 S (o
3200
Chebyshev's inequality then tells us that
3 -
62+c7 2 = o9 + 63-69
PT > r) = Pr
Tn > 87
(Since r
2
2
E2
E
< Pr
In > Σ - - +
(Since
| - Iall p S t
13-1al?
2
2/ Ei
Pr
Ta > B B[Tn] +
(By Lemma B.7)
2
e
< Pr
[Tm B[T,)
(Adding absolute sign)
2
2
2
S (In)
(Chebyshev's inequality)
22
2
-4 3202
(6)
81
2)
(From above)
32002
(6) - =7²²
Thus, when |Σ
Iall3 < ef. we have Pr (T, <)) 2/3 and the ith test outcome will be correctly an Accept with
probability least 2/3.
Case 2: Σ La |/ 2 =
We can lower bound 6² as follows:
b² n d 1 -
(Since |/ I 5td) (Since n = =3200 d Ac.
=3200- Der.ez
E E--ig -all??
3200 - Denee 2
(Since |Σ Ial 2 2 2
Meanwhile, we can lower bound n as follows:
T 3200 d Ae1.22
(Since n 3200 d -ee,e2)
3200 cg A
(Since 83)
3200 =2
Aenez
(Since Denee 2 2
C2 E5-
DELiE
62
Using these lower bounds on 6² and n (which we color for convenience), we can conclude that 1 1+ 6" S via the following two equivalences:
6² 3200
(5)-s)) 2
82
b²
c7
2
1
62
n
3200
2
3200
and
3200 A
11
n n>
3200 A
61
2
3200-63 -
3200
2
1
.gg
c
-1
A Ans
(
82
- 1
22

---

Learning multivariate Gaussians with imperfect advice
So.
64d
b²
8²
(T(Tn)
1 +
++
+
(By Lemma B.9)
n12
12
$ 64 2-
dc
b²
c/ $
2
b²
[2
2
+
6²
(Since 1 + S
5 of
2
n2a
3200
2
3200
22
2
3200
E
64 2-2
$ 1
d2
-2- 2
84
(Since 3200
S 1)
3200
2
n
64 2-2
1
2
Σ
Iall
(Since
Σ Id
b'd)
3200
2
Chebyshev's inequality then tells us that
In sg. (1-
22 o
S.te c 3-5 2
Pr (In r) = Pr
(Since 7
28
3/ o
Pr
Tn Σ --
11-
(Since |Σ Ial
28
8
Pr
T [
Ia
1.
(Rearranging)
28
82 -
E
= Pr
E[TT]
Tp > EΣ La
(By Lemma B.7)
28
82 of
S Pr
[B[Tn] - Tnl > Σ Ial
(Adding absolute sign)
252
2
2
<T)(TT))
(Chebyshev's inequality)
E In P
3 - 77
64 24-
( [2] E
1
2
2
E Iall
(From above)
3200
$2
|
Lal
=?
64-2-2.4
3200
Thus, when |Σ 1. 2 =2 we have Pr (T > T) 2 2/3 and the 5th test outcome will be correctly an Reject with probability at least 2/3.
Lemma B.10 (Tolerant covariance tester), Given 82 > 8 > 0, 5 E (0, 1), and d 2 EY, there is a tolerant tester that uses d max
7 - (3
1 -5-- (
2
log (1)
i.i.d. samples from N (0, Σ) and satisfies both conditions below:
If Σ La F S E1, then the tester outputs Accept,
2. 10 E Iallr 82, then the lester outputs Reject,
each with success probability at least 1-6 6.
Proof. Use the guarantee of Lemma B.6 on TOLERANTZMGCT (Algorithm 3) with parameters of ===" =² and =3 2s...
C. Identity covariance setting
C.1. Guarantees of APPROXL1
Here, we show that the guarantees of the APPROXLI algorithm (Algorithm 4).
Lemma C.1. Let k a, and Ç be the input parameters to the APPROXLI algorithm (Algorithm 4). Given m a.)" samples from N N(u, La), APPROXL1 succeeds with probability at least 8 and has the following properties:
8') i.ddd.
23

---

Learning multivariate Gaussians with imperfect advice
Algorithm 4 The APPROXL. algorithm.
Input: Block size & E [d]. lower bound a >> 0, upper bound Ç > 2a, failure rate E (0, 1), and i.id. samples S from
(J,, Ia)
2: Output: Fail or X E IR
3: Define [d/k] and 8' 1o-1log,5/7 5/al
4: Partition the index set [d] into w blocks:
B (I....,,)),
k), B2 = -k I,.... 2k),..... ............ B.. [k(w 1) + +1,,11.. I.....d}}
5: for j E {1.... w) } do
6:
Define S; = (BB, E IR. B,l
x EXES as the samples projected to B,
D See Definition A.4
7:
Initialize 0j Fail
8: for 1, ... [log2 C/a] do
9:
Define 4 = 2
10:
Let Outcome be the output of the tolerant tester of Lemma 1.5 using sample set Sj with parameters
8 = 44 82 = 24, and = TrOut come Accept then Set 0, and break
11:
Escape inner loop for block j
end if
14: end for
15: end for
16: if there exists Fail amongst {oi,.... )w) then
17: return Fail
18: else
19: return = 2 BB]
D is an estimate for ||
end if
If APPROXLI outputs Fail, then || > 5/2.
2. If APPROXL1 outputs R, then ||||]] À < 2Vk ([d/R] a 2/1
Proof. We begin by stating some properties of o1.... ow Fix an arbitrary index E {1...., w) and suppose o, is not Fail, i.c. the tolerant tester of Lemma 1.5 outputs Accept for some i" E {1, 21.2.... [log </a]}. Note that ApPROXLI sets Oj = l.- and the tester outputs Reject for all smaller indices i E {1,..., - 1}. Since the tester outputs Accept for i", we have that I|w ll2 S 26,- 20y. Meanwhile, if 1, then |l, f l. 1 = 0 since the tester outputs Reject for i 1. Thus, we see that
When of is not Fail, we have [| ||2 S 20j.
When |MB |2 I 2o, we have i" = 1 and = f1 = a.
When [MB, ll > 2o = 26,, we have 1" > 1 and so oj < 2111B,
Success probability. Fix an arbitrary index E (1, [log C/ai] with L, = 2 ax where l, S E for any i. We invoke the tolerant tester with E2 = 24, 2 so the tth invocation uses at most 74.. ii.d. samples to succeed with probability at least - 6; see Definition 2.1 and Algorithm 2. So, with m(k, a, 8') samples, any call to the tolerant tester succeeds with probability least 8'. where 8' ar inga C/al By construction, there will be most w [log, C/a] calls to the tolerant tester. Therefore, by union bound, all calls to the tolerant tester jointly succeed with probability at least 1 - 8.
Property When APPROXLI outputs Fail, there exists a Fail amongst {o,,..., ow }. For any fixed index j E fl..... w) this can only happen when all calls to the tolerant tester outputs Reject. This means that || | l|2 E1 = l, = 2 a for all i (1, (1,2...., [log2 {/a]]. }. In particular, this means that ||æB, Ç/2.
24

---

Learning multivariate Gaussians with imperfect advice
Property 2. When APPROXLI outputs À b== v BB) og E IR, we lower bound À as follows:
w A= =
[B] 0j
j=l
MB,
ll2
2 2
[,]
(since || ll2 S 20,))
2
3=1
|B
(since | |1 S (BB |AB (12)
|
(since Σド=1 LB, || | (11)
That is. A 2 |lll Meanwhile, we can also upper bound as follows:
w A
B 0j
j=1
$ 2v {: Σ9
(since [, S k)
j=1
= =2V
Σ
Oj +
Oj
(partitioning the blocks based on || ll versus 2a))
j=1
[lwn, Ia52a
M >
2Vk.
Σ
a +
Σ
(since ||BB ll2 S 2a implies 0j = o.)
j=1
j=1
[|4B, 1252a
I|aa, >2>2
$ 2vF..
Σ
a+
Σ
2 211 ll2
(since ||B ll2 2a implies of $2 (12)
I1BB, S2
I|B 12>2a
22V
Σ
a a+2
Σ
PB, llı
(since || lla - |BB Il1)
j=1
[14B, Iaa2a
|pnylla>2a 2n
< 22k.
[d/k] +
Σ
MMB l1
(since |i E [w] MB, S 22)) S w)
j=1
||B 2a
S 2vk- ([d/k] a 211
(since Σ W
LB, 1l1 S E |B, || = |B 11
j=1 I| >l
That is, A 22T. ([d/k] a 21)m The property follows by putting together both bounds.
C.2. Deferred derivation
Here, we show how to derive Equation (3) from Equation (2).
For any two vectors a, IRd, observe that ||a - blg = (a b, a b) (a-bbT(a b) =Taa 2a Thb + bTb. Tb, since
25

---

Learning multivariate Gaussians with imperfect advice
b bJa is just number. So,
y iz+ p (2)
1=1
lyy
Xu
Σ
(yTy: - 2y 4 1 11)
1=1
Therefore,
Í 1=12
j 1
( Ā 2p it + fi 14)
1=1
<
(2y: p - 2y, r + μ 4 4 2p + 1 14)
(Since Equation (3) tells us that Eimi lly. 11 - lly: 1al13)
(n + g:) ( 11) 1 p 11 11)
(Since y; = - gi)
n i=1
2
[g. (īi 11)
2
gi f p1)
im
Bi, 14 14)
(Linearity of inner product)
i=1
establishing Equation (3) as desired.
D. General covariance setting
In this section, give results for learning multivariate Gaussians with imperfect advice for the general covariance setting. We will later define analogs of m(d, a,, and APPROXLI from Section 2 to the unknown covariance setting: respectively. Then, after stating the guarantees of VECTORIZEDAPPROXLII we
m' (d, a. 6) and VECTORiZEDA show how to use them according to the strategy outlined in Section 1.2.2.
For the rest of this section, we assume that we get i.i.d. samples from N Σ) and also that Σ is full rank. These are without loss of generality for the following reasons:
Instead of single sample from NH, Σ), will draw two samples æ1, 22 N(u, Σ) and consider x' # One can check that x' distributed according to (00, Σ) and we only use a multiplicative factor additional samples, which subsumed the big-O.
v2
By Lemma A.13, the empirical covariance constructed from i.i.d. samples of N(O, Σ) will have the same rank as itself, with probability at least So, we can simply project and solve the problem on the full rank subspace of the empirical covariance matrix.
Outline of this appendix section. In Appendix D. we first elaborate on the adjustments mentioned in Section 1.2.2 to adapt the approach from the identity covariance setting to the unknown covariance setting, then show how to adapt the same approach as Section to handle the general covariance setting in Appendix D.2. Appendix D.3 shows that optimization problem in Appendix D.2 can reformulated as a semidefinite program (SDP) that is polynomial time solvable. Finally, Appendix D.4 presents the proof for Theorem 1.4.
26

---

Learning multivariate Gaussians with imperfect advice
D.I. The adjustments
To begin, we elaborate on the adjustments mentioned in Section 1.2.2 adapt the approach from the identity covariance setting to the unknown covariance setting.
The first adjustment relates to performing suitable preconditioning process using an additional d samples so that we can subsequently argue that Amin [ 2 1. The idea is as follows: we will compute preconditioning matrix A using i.idd samples such that A AE has eigenvalues at least 1, i.e. Amin (AEA) 2 1. That is, || (AAEA) - Ami((AAA) S Then, we solve the problem treating AEA as our new E. This adjustment succeeds with probability at least 1 - 8 for any given E (0, 1) and is possible because, with probability 1, the empirical covariance Σ formed by using d i.i.d. samples would have the same eigenspace E, and would have bound the ratios between the minimum eigenvalues between Σ and Σ; see Lemma A.13.
Lemma D.I. For any 8 E (0, 1). there is an explicit preconditioning process that uses d i.i.d. samples from NO, E) and succeeds with probability at least 1 - in constructing a matrix A Rddd such that X (AEA) 2 1. Furthermore, for any full rank PSD matrix Σ Rdxd, we have [|(AA)) 1/2 AEA(AAA))))))) 1122 - 1 1/2 Isll-
Proof. Suppose Σ E Rddd be the empirical covariance constructed from n = d i.idd samples from N(,, E). Let A & < da and \1 .... Aa be the eigenvalues of Σ and Σ respectively. By Lemma A.13, we know that:
With probability 1, we have that E and E share the same eigenspace.
With probability at least 8, we have
& A
+1+00 co
d+ 1/8
for some absolute constant co.
Let vi...., Va be the eigenvectors corresponding to the eigenvalues 22,..., dd. Define the following terms:
small Imaalll = Eiev srall V. and Iig Eieva, V.V.
V small
{i [d] Xu < and Vbig [d] V
A =
small + big, where k-
1 + Co-00-
d+lng 1/6
1
X
We first argue that the smallest eigenvalue of AEA is at least 1, i.. Amin (AEA) 2 1. To show this, it suffices to show that u² AEAu > 1 for any unit vector E IR. By definition,
u T AEAu ku II small
E u + big Elg Dig
since the cross terms are zero because u small EI big u u Hi EI u = 0.
Now, observe that u II small E[I
11 11
2 A
I 1 and u T Thin El 2 Therefore,
1 u ul
Meanwhile, by Pythagoras
theorem, we know that [ small
u
2 [oig u
u AEAu =ku Imall EII amal u + u 1bg E
Im
||
Lamal u/2 2 + [ u (2)
where the last inequality is because To complete the proof, note that for any full rank PSD matrix Σ E Rdddd we have
1
1 1 Co
do 1/8 n
2
X1
[[ ((AAA)) AAAAAA/AAAAAAAAAA Iall = ||AAA)) -'EAA
'AAA - L
=1A-- Lal
27

---

Learning multivariate Gaussians with imperfect advice
EE'EAA - -aal
1Ê Iall
= -18-1/2 -aa
-aal
The matrix A in Lemma 1.7 is essentially constructed by combining the eigenspace corresponding to "large eigenvalues" with suitably upscaled eigenspace corresponding to "small eigenvalues" in the empirical covariance matrix obtained by d i..d. samples and relying on Lemma A.13 for correctness arguments.
The second adjustment relates to showing that the partitioning idea also works for obtaining sample efficient & estimates of vec(E Ia). While an existence result suffices, we show that simple probabilistic construction will in fact succeed with high probability.
Lemma D.2. Fix dimension d 2 2 and group size ls S d. Consider the q 2 setting where T E IRdxd is a matrix. Define 10d(d-1)logd Pick sets Bi,..., Bi each of size k uniformly at random (with replacement) from all the possible (i) R(k-1)
sets. With high probability in d, this a (q 2, dl K a 1,b 30(d- 1ylogd >-partitioning scheme.
(k-1)
Proof. By definition, we have B Bwl = k. Let us define E1 as the event that the cell (i.j) of T never appears in any of the submatrices ....... T and E2,i,j as the event that the cell (i,j) of T appears strictly more than b submatrices. In the rest of this proof, our goal is to show that Pr[E,] and Pr[Eş] are small, where & = 14 and & (((,)) E2,33
Fix any two distinet i.j E [d]. For f E [w], let us define x as the indicator event that the cell (i.5) in T appears in the 8t principal submatrix TB, when i,j E B₁, By construction,
k(k-1) a(a-1)
if j
Pr[X = =]= =
5/4
ifi=j
To analyze ε,, we first consider i,j E [d] where * j. We see that
II Pr[x = 0] -(1 1
k:kk -k-11 < exp
wk(k - 11
1
Pr|E
=exp (-10 log d)
10
d(d 1dd
d(d (dd(d-
d00
t=1
Meanwhile, when i i= j.
II Pr|x 0] (1
-11-2)
2) "
exp
(- wk (-d
d
< exp (-10 log d)
d
1
Taking union bound over (i,5) E [d] x [d]. we get
d²
Pr(Ei] <
Σ
Pr(Einus]
<
d1o
d
To analyze &,, let us first define Z expectations tells us that
Ei X for any i E [d]. Since the X variables indicators, linearity of
k(k-1) wkrk ddd we d
if
E Z - =
E
d(d-1)
i
For * j. applying Chernoff bound yields
28

---

Learning multivariate Gaussians with imperfect advice
[B| .2²
Pr|z > (1+ B[Z41] exp
S exp (-B(Z+)]
2+2 2
(- _ukkk - 11
eexp
(=d(d= "(dd-1) 1) (
= =exp (-10 logd) d) = di
Meanwhile, when i = j.
wk S exp (-10 log d) (-a
1
Pr|Z > (1+2)-B|z*]] $ exp
exp ( (-B[Z"1)) exp
2+2
d
By defining
3wk 30(d logd
3 max E[Z
(k: 1
we see that Pr[E2.i.]] = Pr[z > bj < Pr|z > (1 + 2) B| < 7. and Pr[ = Pr|z > bj s Prizi>>
(1+ E1 $ zi0 Therefore, taking union bound over (t, E [d] x [d]. we get
d²
Pr(E2]
Pr[Eens] S x
Σ
d
In conclusion, this construction satisfy all conditions of Definition 1.8 with high probability in d.
We obtain (4= d,, ki 1,b 0( (olo)))) ) )-partitioning scheme by repeating the construction of Lemma 1.9 until in satisfies required conditions. Since it succeeds with high probability in d, we should not need many tries. The key idea behind utilizing partitioning schemes is that the marginal over subset of indices B S [d] of a d-dimensional Gaussian with covariance matrix Σ has covariance matrix that is the principal submatrix ΣB of Σ. So, if we can obtain a multiplicative a-approximation of a collection of principal submatrices EB, EB., such that all cells of Σ are present, then we can obtain a multiplicative a-approximation of Σ just like in Section 2. Meanwhile, the parameter allows us to upper bound the overestimation factor due to repeated occurrences of any cell of Σ.
D.2. Following the approach from the identity covariance setting
We begin by defining parameterized sample count m'dd, e, o),), similar to Definition 2.1.
Definition D.3. Fix any d 2 1, > 0, and 8 E (0, We define m' (d, 5, 6) = n2/,e TT. where
1 EZ .
H
12 1
n'yc- 3200d max
and
To = 1+
log
The VECTORIZEDAPPROXLI algorithm corresponds to APPROXLI 1 in Section it performs an exponential search to find the 2-approximation of the | 10 Iall? by repeatedly invoking the tolerant tester from Lemma 1.6 and then utilize a suitable partitioning scheme to bound ||vec(2 L2)ll;: see Lemma 1.9 and the discussions below
We now show that the VECTORIZEDAPPRONE
algorithm has the following guarantees.
Lemma D.4. Let E, 8, k a, and Ç be the input parameters to the VECTORIZEDAPPROX.. algorithm (Algorithm 5). Given m(k, a. 8') i.i.d. samples from N Nu, Ia), the VECTORIZEDDPPRRXXL algorithm succeeds with probability least 8 and has the following properties:
If VECTORIZEDAAPRRXLI outputs Fail, then | - Iali > C/2.
If VECTORIZEDAAPRRXLI outputs À E R, then
(10d(d - 1) log d
|/ee -oocE-1o - Ia)ll < A < 2vk.
a + 2//voc(EE [a)lh)
k(k 1)
29

---

Learning multivariate Gaussians with imperfect advice
Algorithm 5 The VECTORIZEDAPPROXXI algorithm.
Input: Error rate 0, failure
(0,1), block size & [d], lower bound a upper bound Ç > 2a, and i..d.
samples S from (0, Σ)
2: Output: Fail or À E IR
Define w 10d(d-1) log 8' u loga </al and let B,...., B S [d]² be a (q 2,d, 1,b O (dlogg ((dlord)
partitioning scheme as per Lemma
4: for j E (I..... w) do
5: Define SB, {E ER
RBB.1 S} as the projected samples
See Definition A.4
6: Initialize 0j Fail
7:
for 1,2,.... [log2 {/a]]
do
8:
Define 4 = 2
9:
Let Outcome be the output of the tolerant tester of Lemma 1.6 using sample set SB, with E = 44 E2 = 22,, and
8' 8
Outccome Accept then
Set 0, and break
Escape inner loop for block
12: end if
13: end for
14: end for
15: if there exists a Fail amongst {or,.... ow then
16: return Fail
else
return À 2 VBB
D À is an estimate for |[ee[( Ba)llı
end if
Proof. We begin by stating some properties of o1...., Ow Fix arbitrary index E { w and suppose o, is not Fail, i.e. the tolerant tester of Lemma 1.6 outputs Accept for some i* E (1, [log2 S/oi]] J. Note that VECTORIZEDAP- PROXL1 I sets o, = f.- and the tester outputs Reject for all smaller indices E {l...., 1}. Since the tester outputs Accept for , we have that || EB, Iallæ < 20a- 20j. Meanwhile, if > 1, then EB, - Ia -alF F > e = /2 = 03/2 since the tester outputs Reject for 1. Thus, we see that
When is not Fail, we have EB, IallF I 203.
When B IallF S 2a, we have i" = 1 and 0₁ = =1 a.
When EB,
LallF 2a 26,, we have i 1 and so o, <B|EB, Iall
Dogz [/a]} with l, 2i-La, where l, S = a for any i. We invoke the tolerant tester with 52 = 24 22,, so the ith invocation uses at most n',,- ra i..d. samples to succeed with probability at least 1 - 5; see Definition D.3 and Algorithm 3. So, with m(k, mnk,,,,") 5') samples, any call to the tolerant tester succeeds with probability at least 1 - 8', where 8' w- luga c/al By construction, there will be at most w [log2 C/a] calls the tolerant tester. Therefore, by union bound, all calls the tolerant tester jointly succeed with probability least 1 8.
Suecess probability. Fix an arbitrary index E (1,
8
outputs Fail, there exists Fail amongst {01,..., Ow.) For any fixed index j E (1, .,, w) this only happen when all calls to the tolerant tester outputs Reject. This means that [EB La]l E1 = l = 2 a for all i E 21.2...., [log, </a]]: In particular, this means that ΣB, Iall > C/2.
Property 1. When VECTORIZEDA
Property
When VECTORIZEDAAPROXLI outputs À 22 -, VBBl Og E we can lower bound À as follows:
w A = Σ
Byl-og of
/=1
10
EB, L
2
By
(since EB, IIllF S 20,)
2
1=1
30

---

Learning multivariate Gaussians with imperfect advice
w
B,1 |/ee 1
(since |EB Lall ||veC[EB, -a)ll
(2, - -aall1
(since ||vvec Ia)lli S [By] ||vee [a)ll²)
j=1
||vec Σ In)ll1
(Since each cell in Σ appears at least 1 times across all submatrices EB, ........ EB.)
That is, x 2 vee E Ia]ll 1- Meanwhile, we can also upper bound À as follows:
== 2 Σ V
B,] oj
j=1
$ 2/k. Oj
(since By S k)
j=1
2
Σ
Oj +
Oj
(partitioning based on ||E, Ialle versus 2a)
j=1
j=1
| -.ll
[2n, -1 p>2a
=2vk-
Σ
+
Σ
Oj
(since [EB - Lalle 2a implies oj a)
j=l
[nEn $2a
Enn -2lll>>2a
S 2VT.
Σ
at +2 2
Σ
EB, Ialle
j=1
==1
EB - 22n
[EB 52a
(since EB, - -LalE > 2a implies of s 2 - -allF)
2vk.
at + 2
|ieec EB, Ix)ll
Iall = ||vec( 11)13) (since [B,
1=1
1=1
EEB Tall $20
[Eg Talle
w
W Σ
< 2/h.
Σ
a a+2
Veoe I4)ll1
j=1
| T.ll 22n
[nn 220
(since |/ee EB, La)ll2 S ||vee(EB -1))l1)
< 2v/.
+2
Σ
(Be -tall1
(since Ki [w] EE Talle <2a)] s w)
[En Lalli 52a
< 22k (wa + 2||vee( Σ - 11)
(since
Σ
Vvee Ia)li S E |eeeen; Ia)ll ||vec Σ Ia)l
[Eg Tall $20
That is, À 2 (wa + 2llvee( I.)ll)), where w bounds.
10d(d-1) 1o logd k(k-1)
The property follows by putting together both
Now, suppose VECTORIZEDAPPROOXI tells us that |vee(E)) E Ia)ll1 S r. We can then construct SDP to search for
31

---

Learning multivariate Gaussians with imperfect advice
candidate Σ E Rdxd using O [ log !
samples from N(O,E)
Lemma D.5. Fix d 2 1, 2 O, and E > 0. Given O ( log d+ /Hvylog(1/b
samples from (0, 2) for some
unknown E E Rdxd with I|vec(E - 11)l1 I r, one can produce estimates çı E IR' and E E gaxd in poly(n, d, log(1/s)) time such that (Nv E), (ū, Σ) I with success probability at least 1 - 5.
Proof. Suppose get samples y1,.... Yn (0, Σ) For E [n], we can re-express each y as y; Σ//2 for some
g: (O, Ia). Let us define T = Σ Big, and S = Σ y.y. 1/ ( 1. Σ = Σ 1//TE'1
Let us define Σ did as follows:
$
argmin
A - y.y,
(10)
gexd psd. 1=1 ||vea[A Sr Amin (A)21
Observe that Σ is a feasible solution to Equation (10). We show in Appendix D.3 that Equation (10) is a semidefinite program (SDP) that is polynomial time solvable.
Since E and Σ are symmetric p.s.d. matrices, observe that
Σ y.y. 11 Σ - 1/2 g.g: //3
(Since y, /1//g/) gi)
Σ Tr ((5- 1/2
gig. 12/2
(É->'/1 11// gig, x21²2
i=1
(Since || Tr(A A) for any matrix A)
Tr
E 2g.g. 11/3 1/ + ggg Eg.g Σ
1=1
(Expanding and applying cyclic property of trace)
Similarly, by replacing E with E, we that
Σ Σ - y.y
Σ 1=1
Tr (x2 2g.g, Σ g.g. Egig, 2)
By standard SDP results (e.g. see (Vandenberghe & Boyd, 1996; Freund, 2004; Gärtner & Matousek, 2012)), Equation (10) can be solved optimally up to up to additive & in the objective function. We show explicitly in Appendix D.3 that our problem can be transformed into a SDP and be solved in poly(n, d, log(1/s)) time. Since we solve up to additive e in the objective function, we have
n
n
Σ i y.y.
1 Set +
Σ
Σ y.y 11
(11)
which implies that
x
Σ Tr S2
2g.g. 1/2 ggg Eg.g, x) < Σ Tr 2 2g.g.
"² g.g. Eg.g +gg.. Σ)
Cancelling the common g.g, Eg,g, Σ term and rearranging, we get
( x²
E 2 M Tr
ggg.
(31//X11/2 E²))
(12)
t=1
32

---

Learning multivariate Gaussians with imperfect advice
Therefore,
Σ - = Tr ( ( { (E- ((->))(-->)) )
= Tr
[ - 25 +2²)
8
2
2 n
Σ
Tr Big (3 - -x²) - EE 22)
n
i=1
(Add 2Σ - -ΣE both sides of Equation (12))
-+ + - Σ
E
2
Tr (B:8. T -l4) (I1/2SE1/ - Σ²)
(Since TrEE) Tr /r<""/3E1//)
E=1
- - Σ1/ix) E1/2. (1
ε + Tr
gig
Ia
(Rearranging with cyclic property of trace)
C vec ΣΣ Σ"
11
n
$
+
gig.
La
n
(By Lemma A.5 with A Σ
1
11/2 Σ, B = 11/ and C = (1 E.= gig, I.)
Recall that T = 1 Σ B.g, and Lemma A.11 tells us that Pr (IT
Tall2 > >) S 2exp(-11d) when the number of sam-
ples - log 3. for some absolute constant co. So, complete the proof, it suffices upper bound vec (Σ Σ²) l,:
Consider the following:
voc ΣΣΣ 1²11,1 = |/vcc (Ia (Ia- Σ)(E Σ)= E + E)|1
|[vec[Id - Σ)11 /vooE E 8)1 vec E Σ)}
(By Lemma A.6)
(I|vec(La - Σ)[l +1) |/recf + Ia Σ) 1)|1
(Rearranging and adding 0)
(I|vec (Id Σ)ll +1) (Ivec(E- Ia)ll + vie )}}11>
(By Lemma A.6)
S (r -2
(Since ||vec[[a Σ)Il $ r and /eo Ia) r)
When 2
& < n and n E
( log 1)
the following holds with probability at least - 6:
$ - Σ < ε +2 voc ΣΣ - >²),,, IT -Ill2 S & + 4r((r + - < E +
E²
2
dt d+v/llo(115)
Now, Lemma A.12 tells that the empirical mean j formed using O
samples satisfies (āi - (
4) < 5², with failure probability at most 8. So,
(N N(,, E))
det Σ det Σ
Tr(E 1 d + (μ ( E (p ( + In
2
$
1
(w- T - (1 (i) Σ 1/11/25--11 1/2
Lall
(By Lemma A.8)
2
1
(n- (
1--)TT> 3 4 - ) + EΣ -
(By Lemma A.2)
2
33

---

Learning multivariate Gaussians with imperfect advice
2 +
ΣΣΣ
La 1
(Since (Ø (1) - ( (4) S E, with probability at least 8)
1
(
1
Σ
(Submultiplicatiiity of Frobenius norm)
$ 2
(
-1---117
(Since | - [X] S 1)
$ 2
(5² +59)
(From above, with probability at least - 8)
By union bound, the above events jointly hold with probability at least 26. Thus, by symmetry of TV distance and Theorem A.10, see that
(Mv(N(H.L.,, = (Q S (N S VE =c
The claim holds by repeating the same argument after scaling d by appropriate constant.
Algorithm The TESTANDOPPTIIEEACOVVAAAA algorithm.
1: Input: Error rate > 0, failure rate 5 E (0, 1), parameter E (0, 1], and sample access to N(0,E)
2: Output: Σ Rdxd
3: Define & [d" = ed"-1,. 4ad, and 8 loga 5/a
Note: <> 2a
4: Draw m m'(k, or 8') i.i.d samples from N(0, Σ) and store into a set
D See Definition D.3
5: Let Outcome be the output of the VECTORIIZEDAPRROL.I algorithm given 8, k, a. Ç. and as inputs
6: if Outcome is À IR and À Ed then
7: Draw E (()² () i.idd samples y1....; Vn Rd from I.)
8: return Σ argmin
E gaxd is p.s.d.
Ei= ||A y
See Equation (10)
Ive A LI)S <A
Amin (A)21
9:
else
Draw 2n O(d /=²) ii.d. samples y1.... V2n Rd from (O,
11:
return Σ 2n Σi (Y2s 12 -22-1)
> Empirical covariance
end if
Theorem 1.2. For any given e, E (0.1). E [0.1] and E Rdxd, "ESTAANDOPTMM/ZZCOVVAINNGG uses n.
20 " min 1, f(E Σ, d, n.s)))) where
EE d. ||vec( 11122E5 I2)
d2-ng2
i.i.d. samples from N (1, Σ) for some unknown mean l and unknown covariance Σ, and can produce jú and E in poly(n, d, log(1/e)) time such that (Tv(N(,, E), N (ñ. E)) < s with success probability least 1-8.
Proof. Without loss of generality, we may assume that Σ = 1a. This is because we can pre-process all samples by 1/2) pre-multiplying 1/12 each them to yield i.i.d. samples from N N11,3 Σ 1/3 1122) and then post-process the estimated Σ by outputting $1/2 instead.
Correctness of output. Consider the TISTANDDOPTMIEECWWWAANNC algorithm given in Algorithm Using the empirical mean ç 1 - formed by d+ (1g(
C (d/e²) samples, Lemma A.12 tells us that
( 11) Σ -ー - 1) < with probability at least 1 - 8. There are two possible outputs for Σ:
1. E argmin
En || y.y. II2. which can only happen when Outcome is
E axx ispaa | -TilSS Amiin A1215I
34

---

Learning multivariate Gaussians with imperfect advice
2. Σ
2n Σ 2n
Li=1 (22) Y2-1)( Y2
Conditioned on VECTORIZEDAPPROXLI succeeding, with probability at least - 8, we will now show that ( Σ), (p, Σ) S and failure probability at most 26 each of these cases, which implies the theorem statement as we can repeat the argument by scaling e and by appropriate constants.
Case 1: Using À the upper bound, Lemma D.5 tells that (N E), (p, Σ)) with failure probability
most when O _ + ( i.i.d. samples are used.
Case 2: With (dd / samples, Lemma A.12 tells us that (Nv N(, Σ) S with failure probability at most 5.
Sample complexity used. By Definition D.3, VECTORIZEDAPPROOXI uses |S| mm(k,, a,,,,,8), E Ō(k/a²) samples to produce Outcome. Then, VECTORIIZEDAPROXXI. further uses O /ea) samples Odd / samples depending whether À ed. So, TESTANDOPPIMIZZCCWAWIIAIA
has total sample complexity of
k 2
min
{
A²
d
} e²
d'
cō
k a²
+
d
min
x d ह x
(13)
2
Meanwhile, Lemma D.4 states that
(10d(d 1) log
|eee - -a)ll1 SAS2VR
kik - 1) a + 2/|voo -Ia)ll
whenever Outcome is x E R. Since b)+ 2a² + 2b2 for any two real numbers a, b R, we see that
x² e
dd l|veo - c d ddaa 62
k. |/ee E -aaIl
E
A-r +
+
dee2 )
(14)
ct
Putting together Equation (13) and Equation (14), we see that the total sample complexity is
k a²
d
d²
da
k
|||voc[E- II)ll? })
+
+
min
52k +
E2
E²
dR=2
Recalling that TISTANDOPPIM/ZECOVAIIING sets k = [d" 10 = -d with 0 S S 1. So, the above expression
simplifies to
c
d² e
min { I.d
|/vec La)
1)
d2 (a-9
+0n+min+ min { |/ee E
d2- --
Ia)l
}))
22
c²
R2
To conclude, recall that Σ in the analysis above actually refers to the pre-processed Σ 11-1/2 1/2
Remark on setting upper bound Ç. As Ç only affects the sample complexity logarithmically. one may be tempted to larger value than 4ed. However, observe that running VECTORIZEDAAPPROXI. with larger upper bound than Ç d would not be helpful since | La > </2 whenever VECTORIZEDAPPROXLI currently returns Fail and we have ||vee{ Σ - Ia)l < X whenever VECTORIZEEAPPROXLI. returns À E R. So, ed = </4 < ΣΣ - Iall?
|]vee( E - 1 2 < [] 2- - Ia)lla < Á and TESTANDOPTIMIZEEEAN would have resorted to using the empirical mean anyway.
Remark about early termination without the optimization step. If there no Fail amongst {oi..... ow) and 4b ΣØ= 0f < x² after Line 9 of VECTORIZEDAPPROXLE then we could have just output Σ = La without running the optimization step. This ie because since 4b Σラ= of e² would imply | Iall < E² via
10
30
2 S L
EB, L <b b Σ (20,)2 S 1=1
j=1
35

---

Learning multivariate Gaussians with imperfect advice
Meanwhile, Lemma A.12 tells us that (it (4) 1----=110 14) s e². Therefore, see that
dxl (N (H,
det Σ det Σ
T1(--1)) - d + ( ( Σ -
(n (p- (1) + In
2
=
(w- [i) ">)> E - (m / + Σ 1/2 - 1/2 Ialli.)
(By Lemma A.8)
2
1
((p ( E E
(p 4 / - La 11:))
(Since Σ Id)
2
1
$
(6² + | lall²)
(Since (ī 11) E D- (4) S c, with probability at least 8)
2
$
1
(5² +
(Since || 15-Li Lall S a², with probability at least 1 - 6)
2
1 2
(e2 +
(since a d
ek < E as k S d)
Thus, by symmetry of TV distance and Theorem A.10, that
(N Σ), N(, E) drv E),
(u, (H,E)) S Vō (N Σ), E)) S vo=== =
D.3. Polynomial running time of Equation (10)
In this section, show that Equation (10) in Lemma D.5 be reformulated as semidefinite program (SDP) that is polynomial time solvable. Recall that we are given n samples y1,....Ya NO, Σ) under the assumption that |vee( Σ Ia)ll S for some r > 0, and Equation (10) was defined as follows:
$ = argmin E adxd pxal 1=1
ΣIA --y. 11
[|vec(A- Sr
AA)21
To convert our optimization problem to the standard SDP form, we "blow up" the problem dimension into some integer n' e poly(d). Let m be the number of constraints and n' be the problem dimension. For symmetric matrices C, DI,.... Dm E
Rn xnn and values bi....,de bm E R, the standard form of SDP is written as follows:
min X
(C,X)
subject to
(D1, X)
(15)
D X)
bm
X
J 0
where the inner product between two matrices A, B E R xn' is written as
(A,
A Biy
i=
For further expositions about SDPs, we refer readers to (Vandenberghe & Boyd, 1996; Boyd & Vandenberghe, 2004; Freund, 2004; Gärtner & Matousek, 2012). In this section, we simply rely on the following known result to argue that our optimization problem will be polynomial time (in terms of n, d, and r) after showing how to frame Equation (10) in the standard SDP form.
Theorem D.6 (Implied by (Huang et al., 2022)). Consider an SDP instance of the form Equation (15). Suppose it has an optimal solution X* TR xn' and any feasible solution X E R xn' satisfies |X 2 < for some R > Then, there is an algorithu that produces X in Oppoly (n, d, (og(1/E))) time such that (C, X) < (C, x*) + RR |||||
36

---

Learning multivariate Gaussians with imperfect advice
Remark D.7. Apart from notational changes, Theorem 8.1 of (Huang al., 2022) actually deals with the maximization problem but here transform it to minimization setting. They also guarantee additional bounds the constraints with respect to X, which we do not use.
In the following formulation, for any indices and j. we define dú, E {0, 1) as the indicator indicating whether = j. This will be useful for representation of the identity matrix.
D.3.1. RE-EXPRESSING THE OBJECTIVE FUNCTION
Observe that for any i [n], we have
TT-((A | = (A
-Tr(A 2Ir (y.y, + +' Tyry.Ty
Since y1.... .n I2 are constants with respect to the optimization problem, we can ignore the Tr (y.y, y.y!) term and instead minimize nTr (A (ATA) X Tr (y:y, A). As A A is quadratic expression, let us define an auxiliary matrix B E addd which we will later enforce (r(B) 2 Tr(A" (A). Defining a symmetric matrix = - y.y. E Rdxd the minimization objective becomes
TT (B) 2TH (Y) nB1,1 +... + nBd.d 2(Y, A)
(16)
D.3.2. DEFINING THE VARIABLE MATRIX X
Let n' 2d 3d and let us define the SDP variable matrix X BR'''n follows:
B A T
A
I
A La
4-L4
E IR "R'''x' xn'
X =
U
SU
B
where the empty parts of X are zero matrices of appropriate sizes, B E ddd is auxiliary matrix aiming capture A A. and U and S are diagonal matrices of size d2:
U diag 11 U1, U1,ds Ud,1s ud,a) E xd"
S diag $ $1,1 s1. .1.d...., Sd,1 sd.1..... sd.a) E lxd
xd
For convenience, we define
M =
B
A
E Rd2x2d
A
L
so we can write
M
A
L
X
U
E R Xn²
(17)
S
8B
In the following subsections, we explain how to ensure that submatrices in X model the desired notions and constraints on A, B, and so on. For instance, we will use to enforce vvc(A A I1)ll S an element- wise fashion and use and su for slack variables to transform inequality constraints to equality ones. The slack variable SB is used for upper bounding the norm of B later, so that we can argue that the feasible region bounded.
37

---

Learning multivariate Gaussians with imperfect advice
D.3.3. DEFINING THE COST MATRIX C
To capture the objective function Equation (16), let define a symmetric cost matrix C gg''xn' follows:
diag(n: nn....,.) Y
C Y
Oaxd
Ra''n'
(18)
0220
One can check that (C, X) 111 +... nBad A(Y,
D.3.4. ENFORCING ZEROES, ONES, AND LINKING A ENTRIES WITH A Ia
To enforce that the empty parts of X always solves to zeroes, we can define symmetric constraint matrix Digro E BR''xn such that
if = and j' =j
D D 2e
00
otherwise
and b = 0. Then, (Deero, X) = bi resolves to Xij = (Diero, X) = 1 0. We can similarly enforce that the appropriate part of X in M resolves to La.
Now, to ensure that the A submatrices within M are appropriately linked A La, we can define a symmetric constraint matrix D 12 xn' such that
Odxd
0 Oaxd
t
A
0 x
Rud 'xx
0g xd
and ) = 0, where contains 1/2 at the (i.j)-th and (j, z) entries and i contains d,,- - entries, with 0 everywhere else; if j. we double the value. So, (D X) big would enforce that the (i,j)-th and (j, i)-th entries between the A submatrices within M and those in Ia are appropriately linked.
at the (i,j)-th and (j 4)-th
D.3.5. MODELING THE L CONSTRAINT
To encode veov A Ia)lI S in SDP form, let us define auxiliary variables (1s.))i and define the linear constraints:
- Ui < - for all i,j e [d]
Ai.j Ui.j S 8..j for all ر E [d]
Ed Ej Ui.j r
The first two constraints effectively encode |Ar, o4,يl S Uij and the third constraint captures ||vec(A - Ia)li S desired. To convert the inequality constraint to equality one, we use the slack variables {si, J.SEja in S. For instance, we can define symmetric constraint matrices D E R xn' Dū, E I xn', and D E R xnn with b b and b" as follows:
Oaxd
Oaxd
Oaxd
Odxd
Oaxd
Oaxd
D
D
t
38

---

Learning multivariate Gaussians with imperfect advice
O2dx2d
Odxd
da x
D =
xd2
0
where contains --سr at the (i. and (j. i)-th entries, i contains - at the (i,j) and (j. i)-th entries, and contains
at the (i, j)th and (i, i)-th entries, with 0 everywhere else; if = j. we double the value. So, (D k.j. X) = b models
jij Aij Wi.j 8i,j O, DD X)
bij models Ar, ōū, wis sig 0, and (Di, X) b models
55 > iiml Ej=1 Wij
D.3.6. POSITIVE SEMIDEFINITE CONSTRAINTS
By known properties of the (generalized) Schur complement (see Section 1.4 and Section 1.6 of (Zhang, 2005)), it is known that = 0 if and only if the following properties hold simultaneously:
1. M m 0
2. A I 0
A = Amin (A) 1, which also implies that A is psd
3. 1 0 +
11 21,, u1.ds.... Ud
Ud 2
4. 820
+
$1,1, si,d.... sd....... Sd,d 2 0
5. 8u20
6. 22
B
A
= O if and only if 2 ATA. Observe that B = A A implies Tr(B)= 2 Tr(ATA), which aligns with our intention of modeling A by B. Note that the objective function nTT((B) (Tr(YA) and we have that Tr(B) 2 Tr(A A) for all feasible matrices B. Thus, for any pair (A*. B") that minimizes of the objective function, it has to be that Tr(B*) Tr((A") A*), since otherwise, the pair (A B (A+) A+) would have smaller value.
For the first property, since La > 0, Schur complement tells us that M
A
Ia
D.3.7. ENFORCING AN UPPER BOUND ON |B|||
To apply Theorem D.6, we need to argue that the feasible region of our SDP is bounded and non-empty, so that [[X]] is upper bounded. To do so, we need to enforce an upper bound on |B||2-
Since ||vco(A A Ia)l| I r, by triangle inequality and standard norm inequalities, we see that
|| < A La/1 | 2 I ||A LallF + ||ll| = |]vec A La)lla d < ||vec(A La)ll d S r d (19)
As B is supposed to model A A and is constrained only by B A T A, it feasible enforce Tr(B) < B S d-(r+d) because
| T A d
| d |||| < d (rdd--r-0 (r dd)
To this end, let us define a symmetric constraint matrix D. E jnn'xn' 'xn' such that t.j
L
D
E T
0 022F42244DX(22222444
and JB = d- (r + d) Then, (DB, X) = BB resolves to Tr(B) + sB = DD X) = BB = d. -d-rr (r + d) In other words,
since the slack variable sp is non-ncgative, i.c. sB 2 0, we have
|B|| - Tr(B) < | S d. (r d)a
(20)
39

---

Learning multivariate Gaussians with imperfect advice
D.3.8. BOUNDING |Cll AND
|
Recalling the definition of C in Equation (18), we see that
diag(n,..... (n)...)......)
-Y
|| <
I + |
0axd
Meanwhile, we know from Lemma A.13 that
d+ (vat log 1/6
| - | (1+
with probability at least 8.
Recall from Algorithm that when we solve the optimization problem of Equation (10), we have that ||vec E - -I]l $ So, by a similar chain of arguments as Equation (19), we see that
| < Σ
Lalla + ||all = | Lall Lalla ||vec E
(1 log 1/6 Ia)ll +d=r+d ||vec
Ia)ll2
Therefore,
1/5 (
)) S +n+
)) poly(n, d,r)
|||| n | (1+0)
n
n
Meanwhile, recalling definition of X from Equation (17), we see that for any feasible solution X.
X 2 S max {||M] 2. |A Lall,, U||2 su,
By Equation (20), we have that B 2 < vd- (r + d)). So.
2 - B ||2 + || + s d (r + d) +r d+1 poly(d,r)
Also, all the remaining terms are in poly(r, d) since |/vec(A - 1a)ll1 S r. Therefore, |X 12 E poly(d, with probability
1 - 8. So, |||| S R for some R E poly(d,
D.3.9. PUTTING TOGETHER
Suppose we aim for an additive error e' in Equation (11) when we solve Equation (10). From above, we have that |2, poly(n, d, r). Let us define s = मলं in Theorem D.6. Then, the algorithm of Theorem D.6 produces X E Ra'xn' xn' in poly(n, d, log(1/e)) S poly (n, d, log( R.ICI) (ell)))) C poly (n, d, log(1/E")) time such that (C, 8) S
(C, X*) + aR ||C||2 = X.) + g' as desired.
D.4. Hardness results
Theorem 1.4. Suppose we are given a symmetric and positive-defiiite Σ E Raxd as advice with only the guarantee that [|vec ( - Ia) || A. Then, any algorithm that (c, 3 PPC learns N(0, Σ) requires Q minld / samples in the worst case.
log(1/6)
Σ I since, can transform the input samples from N E) as + E 1 x to get samples from N 0 - )), so that the advice quality in the transformed space (with
Proof. Without loss of generality, we can assume
advice taken to be I,) would be ||vec I, E L 3 1 1) Ia) ll. which is equal to the original advice quality
|ivec プー Ia) I|1.
To use Lemma 3.1, we need construct a set of M distributions fi...., fM with fr & N(O, Σ,) such that
Advice quality vec (E, - Ia) || s A for each E [M],
40

---

Σ. Learning multivariate Gaussians with imperfect advice
(ii) the pairwise KL divergence dRL (Aillf) O(s2),
(iii) the the pairwise TV distance drv (f:(f. 2 (2(c), and
(iv) log M 2 2 min dd, (d(.2t)) )
we can construct such a family. Lemma 3.1 would give us a sample complexity lower bound of A² ) to (z. (E33/3)-PAC learn the true disitribution, even given advice with quality A.
Q min (og( at log(1/s)
d
The following lemma is Gilbert- Varshamov like bound on the existence of large sets of s-tuples of [NT with pairwise distance 2
20 )8.
Lemma D.8. For any N z 200 and > O, there exists A {Ai..... A Au3 S [N] with M 2 N such that for all puirs j E [M], A and Aj agree on S 8/40 coordinates.
And the following lemma follows from (Ashtiani et al., 2020), Lemma 6.4.
Lemma D.9. For 2 10, there exist N > 20 matrices UI...., UN E RPx(p/10) such that the columns of each U; the first x 10 columns of p orthogonal matrix, and for each pair i + j E [N]. | U,l S p/20.
Let d be positive integer such that d is a multiple of 10, and either di is multiple of 10
Aa dL < 10
Aa -
For
every and A c, there exist infinitely many choices of d that satisfy these criteria. Take p min d, 10
A き
Then, we will have p for some integer 2 and p will be a multiple of 10. Also take μ S (12//)/2///)
A V
10
2 s/VV (using
P
Let U,...., U.....,,,, U E (px(1110) be the N 2 20(r)) matrices as in Lemma D.9.
Also let A AM denote the M 2 20(2's) 20mn (f (3)))) tuples in [N] which agree pairwise only S s/40 coordinates guaranteed by Lemma D.8.
Then, we use the construction in Thcorem 6.3 of (Ashtiani et al., 2020) block-wise to construct each covariance matrix
Σ
0
E E [M]. We construct each Σ;
0
Rdddd where each Σ.j I, + (UA.)) UT U.O
0
0
RPxP_
By Lemma D.9, each Σij- - I, u1 A,) UT U has p/10 eigenvalues which are equal to i and the remaining p/10 eigenvalues equal to O. Thus, we have | - Lall = Σラ Ei. - 4pl1 (decomposing the sum the E norm definition) S s s.p. v (since Frobenius norm Schatten-2 norm) dlp/p/10 < (substituting sp and = (A/d) 110pp)
E P- Σi
l| (by
We have Σ = Ip
Ail) by construction of UI,..., Un. By similar calculation as in Theorem 6.3 of A UA.0) Uhi
I+e
(Ashtiani et al., 2020), we have dRr. (fi, = TT, Σ, La) Ei !TE -I,) S sh1 To (using μ a/v
S d < (sa2)
By using similar argument as in Lemma 6.6 of (Ashtiani et al., 2020), we can lower bound the pairwise TV dis- tance. By Theorem 1.1 in (Devroye et al., 2018), we have drv (fr, ff) 2 θ mmnn(1, | 1/2 ,/مماا Σ. 1/2 Ialle)) Since
mmin E 13) (1 + (1) 1/2 @(1) when & S Vd, we have drv (fe, fz) 2 ((E)) when E Σ,1ir 2 2(e). We then

---

Learning multivariate Gaussians with imperfect advice
have
[ Σソ 1
Di, Ejrll = Σ
U U UAiG) - U (r) UA,oll
r=1
Σ Tr ((UA(O)) Actr) Us( U2(01) (UA(()) -U (,, U Ub((o)
Σ n² (Tr(UAi(r)))in) Tr(U A,(()))))))) - A,
21
(using U Ai(r)
UAi(r) 1/100 cyelic property of trace, and || Tr(AT A))
2pdd
2/²²
Σ
A Ua L (using Tr(U,, 1o Vn [M] d= sp)
10
rml
2p²d
2p²
((A((r) = Ar(r) P + # # A,(r)) P
10
10
20
(using
U,71 U,
p/10 and | 1n S p/20 for +n by Lemma D.9)
242d d
2/²²
sp
sp
9p2d
((s²)
(using Lemma D.8).
10
40
20
40
This concludes the proof that all requirements of Leamma 3.1 are met and we get the desired result by applying it.
E. Additional experiments
42

---

Learning multivariate Gaussians with imperfect advice
Etrpricall
Erip rica
Emrge scal
5-
3-
2-
2-
2-
200
250
100
150
300
50
200
Number
Number
Numberr samples
7-
Tettenrypomiie Trpption
50
100
250
250
100
150
250
302
50
130
200
250
Number of Samples
Number of samplees
Murtber samples
100
150
200
300
tarpliee
(20, 30, 40, 50, 1000, 10000, 100000). Error bars show standard deviation over 10 runs. Observe that the slope of the green line looks the same for all 2 1000 instances.
Figure 4: Here, d = 500, 100, and g
114-71i /1]l1 1111
43


Reviews:
[{"review_id": "0a6VMPQjQK", "reviewer": "Reviewer_nuex", "summary": "Authors study bounds on sample complexity of mean and covariance estimation of multivariate gaussians\nin learning-augmented setting. Here, the algorithm receives an untrusted advice in the form\nof estimates of the mean and the covariance matrix.\nThe goal is to improve the sample complexity beyond the classical bounds of $O(d/\\epsilon^2)$ and $O(d^2/\\epsilon^2)$ respectively if the advice is close to correct.\n\nThe authors are motivated by the fact that there is an algorithm by Diakonikolas et al. which, given\nprecise estimate of the mean, can certify that this estimate is correct in time only $O(\\sqrt{d}/epsilon^2)$\nwhich suggests that an improvement might be possible also with an approximately correct estimate.\nIndeed, they propose an algorithm which, given an estimate $\\tilde \\mu$ of the mean $\\mu$ requires\nonly $\\tilde O(d^{1-\\eta}/\\epsilon^2)$ samples if $\\lVert \\mu -\\tilde \\mu\\rVert_1 < \\epsilon\\sqrt{d}\\cdot d^{-5\\eta/2}$. They provide a similar improvement in the case of covariance estimation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for thoughtful and constructive review!\n\nFor the mean setting, one can trivially obtain a sample complexity of $\\widetilde{O}(\\sqrt{d}/\\varepsilon^2)$ when the advice quality is \"good enough\" by first running the tolerant tester (see Lemam 1.5) with $k = d$ and $\\alpha = \\varepsilon$, and returning the advice mean directly if the tolerant tester accepts (since this would imply that using the advice mean only incurs a KL error of at most $\\varepsilon^2$). However, we agree that there is a discontinguity in the sample complexity between this \"good enough\" advice quality and our Theorem 1.1. This is in contrast to the covariance setting where our parameters in Theorem 1.2 allow us to recover $\\widetilde{O}(d^2 / \\varepsilon^2)$ directly. We are currently unsure if such brittleness/discontiguity is inherent for the mean problem setting but it would be interesting future work to pursue this inquiry.\n\nYou are also indeed correct that there is a fundamental difference between our upper and lower bounds in terms of whether the advice quality is known. Our upper bounds (and the problem formulation) assume that the advice quality ($\\\\| \\widetilde{\\mu} - \\mu \\\\|_1$ and $\\\\| \\widetilde{\\Sigma}^{-1/2} \\Sigma \\widetilde{\\Sigma}^{-1/2} - I_d \\\\|_1$ respectively) is not known to the learning-augmented algorithms, even as an upper bound. Whereas the lower bounds apply even for the \\emph{weaker} problem where (an upper bound of) the advice quality is known to the algorithms. \n\nAs a side note, there is a typo in the definition of $\\alpha$ in Algorithm 6 and on Line 1847. It should be $\\alpha = \\varepsilon d^{\\eta - 1}$ and our subsequent calculations, theorem statement, and conclusions about the covariance setting remains unchanged. There are also some missing tildes to capture the $\\log d$ factors in the proof. We will fix these errors in the revision.", "claims_and_evidence": "their claims are well supported with proofs and experiments", "methods_and_evaluation_criteria": "performance metrics studied are well established and the benchmark datasets are suitable for a theoretical study.", "theoretical_claims": "I did not check fully any proof. However, their approach seems viable.", "experimental_designs_or_analyses": "I did not try to replicate the experiments", "relation_to_broader_scientific_literature": "Authors study an important problem and their study fits well within the literature on learning-augmented algorithms.", "essential_references_not_discussed": "I am not aware of any.", "other_strengths_and_weaknesses": "Strengths:\n\n* nice and promising results on an important problem\n\n* performance of their algorithm with known prediction error is almost optimal, as supported by their lower bounds\n\nWeaknesses:\n\n* performance with perfect advice does not seem to match the certification algorithm by Diakonikolas et al. (2017).\n\n* not clear whether the performance of their algorithm with unknown prediction error is optimal: lower bounds provided only for the case of known prediction error.", "other_comments_or_suggestions": "none", "questions_for_authors": "can you please comment on the performance of your algorithm with $\\lVert \\eta - \\tilde \\eta\\rVert_1$ approaching 0 and how does it match Diakonikolas et al.?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lbvOjMYhOP", "reviewer": "Reviewer_qviZ", "summary": "This paper studied the problem of learning high dimensional Gaussians given imperfect advice. In particular, the authors show that given imperfect advice that is close to the true statistic quantity (in $l_1$ norm), both the following tasks have polynomial improvements with respect to the dependence of the dimension $d$ in sample complexity compared with the algorithms without using imperfect advice. The tasks are: given an imperfect advice of Gaussian mean, learn the true Gaussian mean of $N(\\mu, I)$; given imperfect advice of Gaussian mean and covariance, learn the true mean and covariance of $N(\\mu, \\Sigma)$.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for thoughtful and constructive review!\n\nYou are right that while the SDP formulation used in TestAndOptimizeCovariance can be solved in polynomial time from a theoretical perspective (as we show in Appendix C.3), it is definitely impractical in practice. The focus of this work is to establish theoretical achievable sample complexity bounds and we hope that our work inspires future work that develops practical solutions matching our sample complexity bound.", "claims_and_evidence": "Yes, they are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Checked the proof in the main body.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The paper contributes well to the vast thread research of gaussian testing/learning, providing interesting results and improving the sample complexity of gaussian distribution learning. For example, the prior result on gaussian mean learning requires O(d) sample, however, the authors showed that given some accurate knowledge of the mean $\\mu$, the sample complexity can be improved to $O(d^{1-\\eta})$.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n1. I think this paper is clearly written with very useful explanation of the algorithm and motivation.\n2. I think the results are interesting and strong. It is interesting to see that given imperfect advice one can break the sample complexity lower bounds.\n3. The paper is solid with highly technical contributions.\n\nQuestion/Weakness\nI seems the SDP algorithm blows up the dimension to n' which is a polynomial of $d$. I think it would be a nice improvement to have more efficient algorithm for this.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3ZJKsfMmje", "reviewer": "Reviewer_M9iy", "summary": "One of the fundamental tasks in statistics is learning a Gaussian in total variation (TV) distance $\\epsilon$. It is well known that the sample complexity for this task is on the order of $d/\\epsilon^2$ when the covariance is the identity and $d^2/\\epsilon^2$ for general Gaussians. This paper investigates whether the learning process can be made more efficient when given advice (or a warm start). For the first case (identity covariance), the advice consists of a vector $\\tilde \\mu$ that is somewhat close to $\\mu$, while for the second case (general Gaussians), it consists of a matrix $\\tilde \\Sigma$ that is somewhat close to $\\Sigma$.\n\nThe main results show that in the identity covariance case, if $\\|\\tilde \\mu - \\mu\\|_1 < \\epsilon d^{(1-\\gamma)/2}$, then $O(d^{1-\\Omega(\\gamma)}/\\epsilon^2)$ samples suffice. For general Gaussians, if $\\|\\text{vec}(\\tilde{\\Sigma}^{-1/2}\\Sigma \\tilde{\\Sigma} - I )\\|_1 < \\epsilon d^{1-\\gamma}$, then $O(d^{2-\\gamma}/\\epsilon^2)$ samples suffice. Here, $\\|\\cdot\\|_1$ denotes the $\\ell_1$-norm of vectors. Both algorithms run in polynomial time with respect to $d$ and the number of samples. These upper bounds are complemented by lower bounds showing that, up to constant factors in $\\gamma$, no algorithm can achieve the task with fewer samples. Notably, the algorithm does not require knowledge of the quality of advice (i.e., $\\|\\tilde \\mu - \\mu\\|_1$ and $\\|\\text{vec}(\\tilde{\\Sigma}^{-1/2}\\Sigma \\tilde{\\Sigma} - I )\\|_1$), and the lower bounds hold even when this quality is known.\n\n\nThe algorithmic approach consists of two main steps: (i) using a Gaussian tester combined with a search procedure to determine the quality of the given advice and (ii) designing an estimator that effectively utilizes the advice. The authors initially attempt to formulate the advice using the $\\ell_2$-norm, since existing Gaussian testing methods rely on it. Ignoring computational constraints for a moment, a natural approach is to use a standard tournament argument along with a discretization of the unit ball to search for a vector that is $\\epsilon$-close to $\\mu$ in $\\ell_2$-norm, which would imply a TV-distance guarantee. However, this approach requires at least $d$ samples, which is suboptimal. Instead, the argument is adapted to use the $\\ell_1$-norm, leading to improved sample complexity. The paper further modifies the testers from (i) to be $\\ell_1$-norm-based by partitioning the vector into chunks and using relationships between $\\ell_1$ and $\\ell_2$ norms for each chunk. While the tournament method has exponential computational complexity, the paper circumvents this by reformulating it as an appropriate optimization problem. This explains the use of the $\\ell_1$-norm and outlines the proof of the first result.\n\n  \n\nThe second result follows a similar high-level strategy, but the proof requires additional complexity to handle the matrix setting instead of the vector setting. Specifically, the partitioning of coordinates and the optimization program are more intricate. Additionally, an initial preconditioning step, inspired by differential privacy techniques, is introduced to ensure that $\\|\\Sigma^{-1}\\|_2 \\leq 1$.\n\nThe lower bound is derived using the Fano method, specifically a lemma from Ashtiani et al. (2020). This approach involves constructing a large family of Gaussians whose pairwise TV distance is at least $c_1 \\epsilon$ while maintaining a KL divergence of at most $c_2 \\epsilon$. The lemma is applied to Gaussians with means $\\mu_i$ such that all $\\mu_i$ satisfy the same upper bound on $\\|\\mu_i - \\tilde \\mu\\|_1$ (advice) and have pairwise distances bounded by $\\epsilon$. Such means can be constructed using codewords from an error-correcting code, as guaranteed by the Gilbert-Varshamov bound.\n\nFinally, some numerical experiments are provided to demonstrate the sample complexity improvements when advice is used.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for thoughtful and constructive review!\n\nThank you for the reference of \"Gaussian Mean Testing Made Simple\", we will add it in our revision.\n\nYou are also indeed correct that there is a fundamental difference between our upper and lower bounds in terms of whether the advice quality is known. Our upper bounds (and the problem formulation) assume that the advice quality ($\\\\| \\widetilde{\\mu} - \\mu \\\\|_1$ and $\\\\| \\widetilde{\\Sigma}^{-1/2} \\Sigma \\widetilde{\\Sigma}^{-1/2} - I_d \\\\|_1$ respectively) is not known to the learning-augmented algorithms, even as an upper bound. Whereas the lower bounds apply even for the *weaker* problem where (an upper bound of) the advice quality is known to the algorithms.", "claims_and_evidence": "The paper contains an extensive proof sketch in the main body which describes the main ideas.", "methods_and_evaluation_criteria": "See below for theoretical methods. I haven't looked into detail on the experiments, but they seem to be clear.", "theoretical_claims": "I read the proof sketch of the introduction and the proofs presented in the main body. I don't have any major issues with these technical parts.", "experimental_designs_or_analyses": "See above.", "relation_to_broader_scientific_literature": "The paper notes that advice has been studied in various problems within the context of online algorithms. While I have not seen this specific problem explicitly stated as an open question in prior work, I find it reasonable and believe it is a valuable addition to the literature.", "essential_references_not_discussed": "Regarding the reference at the end of the first page, there is a much simpler testing algorithm in Ilias Diakonikolas, Daniel M. Kane, and Ankit Pensia. “Gaussian Mean Testing Made Simple.” SOSA, 2023.", "other_strengths_and_weaknesses": "The paper is clearly written, and it provides lower bounds, which strengthen its theoretical contributions. However, there remains a gap between the upper and lower bounds. Specifically, when $\\Delta^2 = \\epsilon^2 d^{1-5\\eta}$, the upper bound (ignoring logarithmic factors) is $d^{1-\\eta}/\\epsilon^2$, while the lower bound is $d^{1-5\\eta}/\\epsilon^2$.\n\nOverall, I do not have any major concerns with the paper and would recommend its acceptance.", "other_comments_or_suggestions": "I suggest explicitly stating the polylogarithmic factors in the theorem statements, as $\\tilde{O}(\\cdot)$ typically hides factors involving the variables inside the parentheses. In the current notation, it is unclear whether the sample complexity depends on $\\delta$.\n\nAdditionally, does the lower bound hold for any $\\Delta$ or only for a specific value of $\\Delta$? It would be helpful to clarify this in the statement or in the text that follows.", "questions_for_authors": "Included above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1dsI3V7eEY", "reviewer": "Reviewer_Mqzt", "summary": "This paper studies distribution learning within the framework of learning-augmented algorithms. Specifically, the authors study how to leverage potentially inaccurate \"advice\" about the true distribution to achieve lower sample complexity for learning multivariate Gaussian distributions.\n\nFor Gaussians with identity covariance, when given mean advice μ̃, the authors develop an algorithm achieving better sample complexity when the advice is accurate. Similar bounds were given for general covariance Gaussian. The paper also gives lower bound showing that the algorithms are optimal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for thoughtful and constructive review!\n\nYou are right that while the SDP formulation used in TestAndOptimizeCovariance can be solved in polynomial time from a theoretical perspective (as we show in Appendix C.3), it is definitely impractical in practice. The focus of this work is to establish theoretical achievable sample complexity bounds and we hope that our work inspires future work that develops practical solutions matching our sample complexity bound.", "claims_and_evidence": "The main sample complexity claims are well-supported by the analysis.\n\nThe efficiency claims for their algorithms are supported by showing how to formulate the estimation problems as LASSO or SDP optimization problems.\n\nThe experimental section provides empirical validation of the theoretical claims, showing the performance advantages when advice quality is good. I find the evidence presented thorough.", "methods_and_evaluation_criteria": "The paper uses LASSO-based method for mean estimation and SDP for covariance estimation. The latter may be somewhat inefficient in practice. \n\nIn terms of evaluation, the paper provides synthetic experiments, it'd be stronger if the experiments consider real data.", "theoretical_claims": "I checked the main proofs in the main paper.", "experimental_designs_or_analyses": "The experimental section only explores the sample complexity gains in the identity\ncovariance setting when one is given high quality advice. It'd be great if the work also studies the covariance case and see if the algorithm proposed is practical", "relation_to_broader_scientific_literature": "The topic broadly lies in the literature on learning-augmented algorithm. This particular work also intersects with algorithmic high dimensional statistics. Both have a long line of works in the past ~10 years in the theory community.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "No", "other_comments_or_suggestions": "No.", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper analyzes the sample complexity of mean and covariance estimation for multivariate Gaussians in a learning-augmented setting, where the algorithm receives untrusted advice in the form of estimated parameters. The authors show how accurate advice can reduce the required sample complexity below the classical bounds for mean and covariance estimation. 

The main concern by multiple reviewers is the gap between the upper bounds achieved in this paper compared to the upper bounds achieved by Diakonikolas et. al. (2018), which should be discussed in more detail. Although the initial review scores were positive, these concerns were not resolved during the subsequent external or internal discussion phases, reflecting more borderline evaluations.
Decision: Accept (poster)