Summary
This paper follows up on the line of study initiated in the work "Actively Avoiding Nonsense in Generative Models" by Hanneke et al. 2018. The model studied in that paper is as follows: we are given data generated by a distribution $P$ over a domain $X$. A certain fraction of the domain $X$ is labeled "valid" and the rest is "invalid"; $P$ is only supported over valid samples. We are given access to an oracle that tells us whether any point $x \in X$ is valid or not. Our goal is to obtain a distribution $\hat{q}$, which minimizes a certain loss, subject to not having too much mass on the invalid fraction of the domain. More precisely, our benchmark is against a specified family of distributions $Q$. Let $q^\star$ be the distribution that minimizes a loss function among all the distributions $q \in Q$ that are fully supported on valid data. The distribution $\hat{q}$ we return should suffer an excess loss of at most $\epsilon_1$ compared to $q^\star$. Furthermore, the mass that $\hat{q}$ assigns to invalid samples should be at most $\epsilon_2$. To obtain such a $\hat{q}$, we can do 2 actions: 1) obtain iid samples from the data distribution $P$ 2) issue queries to the validity oracle. To obtain the required $\hat{q}$, we ideally want both our sample complexity as well as query complexity to be polynomial in $1/\epsilon_1$, $1/\epsilon_2$ and possibly also in the range of the loss function (i.e., if it is bounded in $[0,M]$ for $M < \infty$).
Among other results, the paper by Hanneke et al. 2018 shows that 1) If the learning algorithm is proper (constrained to return a distribution in $Q$), then even with infinite running time and infinite samples from $P$, it must issue at least $2^{\Omega(1/\epsilon_1)}$ queries to the validity oracle. 2) If the learning algorithm is improper, it can return $\hat{q}$ satisfying the required criteria with $O(M^2 \log |Q|/\epsilon_1^2)$ samples from $P$ and $O(M^2\log|Q|/\epsilon_1^2\epsilon_2)$ queries to the validity oracle. These results are stated for a very general class of loss functions (just bounded, monotonic decreasing).
The main contribution of this work is to study under what specialized settings the guarantees of Hanneke et al. 2018 can be improved, especially in the number of validity queries that learning algorithms require. The authors study two different scenarios, and obtain improved query complexities for each.
First, the authors consider a setting where 1) the true data distribution $P$ also belongs to the benchmark class $Q$ 2) the loss function is simply the log-loss function i.e. $l(x)=\log(1/\hat{q}(x))$ (where we are abusing notation so that $\hat{q}(x)$ is the density that $\hat{q}$ assigns to $x$). The former is a "realizability" condition, and the latter is natural since in practice, a default training choice is to maximize the likelihood of the observed data, which is equivalent to minimizing the log-loss. For this setting, the authors present an algorithm that obtains the desired $\hat{q}$ with **no queries to the validity oracle at all**---but now, the algorithm requires $\tilde{O}(\log|Q|/\min(\epsilon_1^2, \epsilon_2))$ samples, as compared to the $O(M^2\log|Q|/\epsilon_1^2)$ samples required by the more general improper algorithm of Hanneke et al. 2018. (Note that the log-loss is not bounded at all, and it helps to think of the comparison when $M$ is a constant). The learning algorithm simply returns the distribution in $Q$ that minimizes the emipirical loss, but suitably mixed with the uniform distribution over the domain $X$. Thus, under the assumptions of realizability, and with a specific loss function, the punchline is that validity comes easily from random examples themselves. The analysis uses classic tools from hypothesis testing like the Neyman-Pearson lemma (this is where the realizability assumption as well as the log-loss shows up). The authors also argue that the sample complexity dependence on $\epsilon_2$ is more-or-less optimal---any proper learner must necessarily use $1/\epsilon_2$ samples (although it still might be possible that improper learners, like the one the authors produce, can do better).
Second, the authors return to the more general setting considered by Hanneke et al. 2018, i.e., $P$ need not belong to $Q$, and the loss function is a monotone decreasing function bounded in $[0,M]$. However, now the crucial assumption is that validity oracle, which is a function that maps $X$ to {0,1}, belongs to a function class $V$ of bounded VC dimension $d$. Here again, the authors obtain a natural algorithm that uses fewer validity queries than the one by Hanneke et al. 2018. First, the algorithm obtains a distribution from $Q$ that minimizes empirical loss. Then, the algorithm obtains extra samples from $P$ (in fact, from $P$ mixed with $\hat{q}$), and invokes the validity oracle on this sample, to obtain valid/invalid labels for all the examples so obtained. Then, the algorithm finds a function $\hat{v}$ in $V$ that agrees with this labeling as much as possible. Finally, $\hat{q}$ obtained in the previous step is re-normalized to only have mass on points that are rendered valid by $\hat{v}$. The authors show that this algorithm works (when all the distributions in $Q$ have at least a constant mass on valid examples) with a sample complexity of $O(M^2\log|Q|/\epsilon_1^2)$ and query complexity of $\tilde{O}(d/\min(\epsilon_1,\epsilon_2))$. Note that the latter is still an improvement (in the dependence on $\epsilon_1, \epsilon_2$). The authors are also able to prove a result without the assumption of constant valid mass, albeit with a slightly worse query complexity (that is still better than that of Hanneke et al. 2018) and which only works for the capped-log-loss.
Finally, the authors comment on ways to improve the query complexities of their results in this setting.
Strengths
The authors present an interesting, suitably exhaustive and strong set of results for natural "special" cases of the problem of validity-constrained distribution learning. Both the settings that the authors study (realizability with log-loss, as well as validity oracle in a bounded VC class) in the paper are natural beyond-worst case instances of the problem, and may well form a reasonable model of practical scenarios. The gains in the realizable setting are particularly impressive---it is nice to see that one can in principle do away with the validity oracle, while also maintaining near-optimal sample complexity. Even in the second setting, which just adds the additional assumption of a bounded VC validity region over those of Hanneke et al. 2018, the authors obtain improved query complexities. Overall, the suite of results feels satisfying and paints a meaningful beyond-worst case picture of the problem.
Weaknesses
While I do find the study compelling, if I am to nitpick and search for weaknesses, I will say that there are no proof sketches whatsoever for the main theorems in the body. Notably, the content is still well under the page limit, and hence I suggest that the authors at least attempt to summarize the main steps used in the proofs of their results in the main body. Also, certain points and sentences could have used more elaboration and verbosity, to make the reading slightly less heavy. For example, lines 251-252 were not coherent to me and seemed like a mouthful, and similarly, at a few other places, I felt like more exposition could have been useful for the reader.
Questions
Here are a few questions that came to my mind as I was reading (some may not be well-formed/basic misunderstandings):
1) In the guarantee of Theorem 1, isn't $q^\star= P$? maybe it would help to write a remark saying this.
2) From a skim, the exponential lower bound for proper learners in Hanneke et al. 2018 uses the coverage loss function. Do you think that such a bound for proper learners might also hold under non-realizability with the log-loss? Basically, I am trying to see if the reason for the exponentially many samples can be isolated to non-realizability alone, or if it also requires the unnatural loss function
3) In lines 250-252, what do you mean by the "realizable complexity"? Shouldn't this be "proper sample complexity" instead? Isn't it possible that there exists an improper learner in the realizable setting that gets something smaller than $1/\epsilon_2$?
4) Just to clarify, in Algorithm 2, in line 4, is it true that all the samples obtained in the previous line from $P$ will be labeled as valid by the validity oracle? I this only really saves a constant factor, but still, these samples need not be queried to the oracle.
5) From a skim of the proofs in the Appendix, it seems that the log-loss is only used to the degree that it is equivalent to likelihood maximization (e.g. in the proof of Lemma 6). If that is the case, can you say something more generic, that your results also hold for any loss functions that get minimized when the likelihood of the observed data gets maximized? If this is not the case, could you point out where exactly the exact form of the log-loss (i.e. $l(x)=\log(1/q(x))$ is crucial in your arguments?
6) I may be wrong and misunderstanding the measure notation, but it seems to me that in the equation block at line 470, in the second line, the $f^n_P(x)$ shouldn't be there. This is because, at least in the discrete case with pmfs, $\sum_x \min(p(x), q(x)) = 1-TV(p,q)$ (note that there is no $p(x)$ multiplying the $\min$ in the summation).
7) Could you explain a little more as to why in Algorithm 2, one needs to obtain samples from the mixture of $P$ with $\hat{q}$? Why do the samples from $\hat{q}$ end up being necessary?
---
Minor typos:
Line 112: typo any \
Line 136 any choice of \
Line 142 samples \
Line 249 means of \
Line 250-252 is not coherent and can use some elaboration \
Line 286 $d$ should be $D$