Learning multivariate Gaussians with imperfect advice

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.

For 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.

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$.

The 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.

The 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.

The 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$.

The 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.

Finally, some numerical experiments are provided to demonstrate the sample complexity improvements when advice is used.

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)$.

Authors study bounds on sample complexity of mean and covariance estimation of multivariate gaussians in learning-augmented setting. Here, the algorithm receives an untrusted advice in the form of estimates of the mean and the covariance matrix. The 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.

The authors are motivated by the fact that there is an algorithm by Diakonikolas et al. which, given precise estimate of the mean, can certify that this estimate is correct in time only $O(\sqrt{d}/epsilon^2)$ which suggests that an improvement might be possible also with an approximately correct estimate. Indeed, they propose an algorithm which, given an estimate $\tilde \mu$ of the mean $\mu$ requires only $\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.

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.