Learning multivariate Gaussians with imperfect advice

The problem of approximating an underlying distribution from its observed samples is a fundamental scientific problem. 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 in modern applications is on highdimensional distributions, with the goal being to understand when one can escape the curse of dimensionality. The survey by [Dia16] gives an excellent overview of classical and modern techniques for distribution learning, especially when there is some underlying structure to be exploited. In this work, we investigate how to go beyond worst case sample complexities for learning distributions. We consider the situation where the algorithm is also given the aid of possibly imperfect advice regarding the input distribution. We position our study in the context of algorithms with predictions, where the usual problem input is supplemented by "predictions" or "advice" (potentially drawn from modern machine learning models) and the algorithm's goal is to incorporate the advice in a 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 setting. Most previous work in this setting are in the context of online algorithms, e.g. for the ski-rental problem [GP19, WLW20, ADJ