Product Distribution Learning with Imperfect Advice

The paper falls in the line of research of algorithms with predictions where algorithms are equipped with advice or predictions. Given recent developments in machine learning it is often too pessimistic to run a worst-case algorithm and not leverage predictable structures of the input. The line of research seeks to bridge algorithms and ML by obtaining provably improved algorithms with accurate predictions while also maintaining worst case guarantees.

The paper studies the problem of learning a product distribution $\bf{p}$ (parametrized by Bernoulli parameters $(p_1,\dots,p_d)$) over the hypercube $\{0,1\}^d$. It is well-known that $\Theta(d/\varepsilon^2)$ is necessary and sufficient in the classic setting of the problem where we want to return a distribution of total variation distance at most $\varepsilon$ to $**p**$. The paper shows that if each $p_i\in [\tau,1-\tau]$ (they call this assumption balancedness), say for some $\tau=\Omega(1)$, if we are given access to an advice distribution $\bf{q}$ such that $\|**p**-**q**\|_1$ is small, one can reduce the sample complexity. Specifically, one can obtain sublinear sample complexity $\tilde O (d^{1-\eta}/\varepsilon^2)$ as long as $\|**p**-**q**\|_1\leq \varepsilon d^{0.5-\Omega(\eta)}$. The paper additionally shows lower bounds demonstrating that without the balancedness assumption, even with very accurate advice, say $\|**p**-**q**\|_1=O(1)$, we must use $\Omega(d/\varepsilon)$ samples. Additionally, they show that when $\|**p**-**q**\|_1\geq \varepsilon\sqrt{d}$, we again require $\Omega(\sqrt{d})$ samples.

I found the problem well motivated and the techniques quite interesting. The main challenge is to estimate $\|**p**-**q**\|_1$ using a small number of samples from $**p**$. If this quantity is large, say $\geq \lambda$, the algorithm just resorts to its classic counterpart which returns the empirical mean of a bunch of samples. Otherwise, they can return the solution to a constrained (by $\|\hat **p**-**q**\|\leq \lambda$) least squares problem. With this constraint, the sample complexity is correspondingly smaller.

The authors considered the problem setting of learning product distribution under imperfect advice, With some assumption on the mean for each coordinate that is balanced (not too close to 0 or 1). The problem setting is as follows. Given an unknown product distribution of {0,1}^d (with p be the mean vector of it), and advice vector q. The algorithm needs to learn a $\hat{p}$ as an estimation of p, such that the product distribution specified by $\hat{p}$ It is close to the true input product distribution in total variance distance. (With the balanced assumption here, this is equivalent to small l_2 norm between $\hat{p}$ and $p$.) If the given advice is good ($\|q-p\|_1$ is small), the algorithm needs to use fewer samples than the trivial $d/\epsilon^2$ sample complexity. And if the given advice is bad, the algorithm needs to perform as well as the trivial $d/\epsilon^2$ sample complexity. This need to be done without the previous knowledge of $\|q-p\|_1$.

For their result, the authors give a polynomial time algorithm with $d^{1-\eta}/\epsilon^2$ sample complexity algorithm when $\|p-q\|_1<\epsilon d^{0.5-\Omega(\eta)}$. The high-level idea they used is the following: The first step is to get an estimation of $\|q-p\|_1$. Directly approximating it would result in linear sample complexity and defeat the purpose. So the author partitions it into d/k blocks, each with k coordinates. Then, estimate the L2 norm difference on each block and add them up. This gives an estimation of the l1 norm by a multiplicative error factor of at most $\sqrt{k}$. After that, the problem can then be reformulated as the convex optimization below line 84.

I feel like the result is far from optimal, and a lot more should be done in this setting. In particular, there isn't much justification from the lower bound side, or some argument such as this result is the best achievable under some particular type of methods. Furthermore, it seems both the assumption and the guarantee are very artificial. (mostly to incorporate the methodology using L2 norm from my understanding) The author didn't explain about this L2 norm approach, like whether they are typical in this setting, or if this is the best we can do. This is based on my limited knowledge of this topic, and I would encourage the authors to point out any mistakes I may have made.

I really like the model of "learning with imperfect advice", which I think is both conceptually interesting and practically well motivated. In my own words, and at a high level, this model is the following: A learner interacts with some untrusted third party which gives them "advice". If the advice is "good" then the query complexity of the learner should improve over the baseline learning algorithm. However, the learner should never require more queries than the baseline algorithm, even if the advice is "bad" -- i.e. the learning algorithm should be robust against "bad" advice. The learner has no promise on whether the advice is good or bad. Given this setup, there is a clear high-level algorithm for this problem, which is roughly the following: Test if the advice is good or bad. If the advice is good, accept the advice - you're done. If the advice was bad, revert to learning, possibly using extra information gained during testing. From the above its clear that this model mixes learning and testing in an interesting way, and that learning with sublinear query complexity should be possible when the advice is good and a sublinear test for this is possible. As before, I think this really is an interesting model, and that there are many many natural and interesting open questions. With this in mind, the submitted manuscript studies the problem of learning product distributions in this model, where the advice is a full description of a candidate product distribution. This is a natural analogue of previous work in this area on learning multivariate Gaussians with imperfect advice (BCGJ24), and indeed the high-level structure of the algorithm given in the manuscript is analogous to the one given in BCGJ24. However, to instantiate this algorithm the authors of the submitted manuscript need to develop a novel tolerant mean tester and l1 approximation algorithm. Interestingly, it also turns out that unlike the multivariate gaussian case, one provably needs a "balancedness" assumption in this setting (even though this assumption is not necessary for identity testing of product distributions!). With this in mind, I think the manuscript has the following strengths and weaknesses:

This paper studies distribution learning with advice, within the line of research on learning-augmented algorithms or algorithms with predictions. In the standard version of the problem, the algorithm is given samples from a product distribution $P$ over $\{0,1\}^d$ and the goal is to output an estimate of $P$ which is $\epsilon$ close in TV distance. In this work, the algorithm is also given access to the parameters of another distribution $Q$, also a product distribution over $\{0,1\}^d$. The goal is to design an algorithm which is more sample efficient if $Q$ is close to $P$ and which is not much more sample inefficient ($O(d/\epsilon^2)$ samples is the benchmark in the standard setting) for worst-case $Q$.

The main result of this paper is an algortihm which improves over $O(d/\epsilon^2)$ samples as long as $\|Q-P\|_1 \ll \epsilon \sqrt{d}$. This result is restricted to the case where every coordinate of $P$ has probability bounded away from $0$ and $1$. The authors show that both this condition and the dependence on the $\ell_1$ distance between $P$ and $Q$ are required: there exist distributions which do not satisfy these conditions for which sublinear in $d$ samples are insufficient for learning.

If the $\ell_1$ distance between $P$ and $Q$ was known, then the authors show that a reduction to hypothesis selection by covering the $\ell_1$ ball around $Q$ with $\ell_2$ balls of radius $\epsilon$. To estimate the distance, the authors develop a tolerant tester for product distributions based on tolerant testers for discrete distributions over $[d]$.

This paper studies the classic and fundamental problem of learning a discrete product distribution $p$ over $\{0,1\}^d$ from i.i.d. samples, with the twist that the algorithm is now given some additional (imperfect) advice $q$ on what the true distribution is. While the classic problem is well-understood, requiring $\Theta(d/\epsilon^2)$ samples to learn to total variation distance $\epsilon$, this paper shows how to beat the bound polynomially under a balancedness assumption---which the authors show are necessary---and improve the sample complexity to $O(d^{1-\eta}/\epsilon^2)$ where $\eta$ is a parameter derived from how close $p$ and $q$ are.

Reviewers and I all agree that this paper has an interesting model and an interesting result, and is a solid contribution to NeurIPS.