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