Distribution Learning with Valid Outputs Beyond the Worst-Case

We thank the reviewer for taking the time to read our work with such attentiveness, and write such a detailed review. We will work to clarify the writing in the next version, and agree that some proof intuition can be added.

Answers to the reviewer's questions can be found below:

1. This is correct: in the realizable case $q^* = P$. Theorem 1 was phrased in terms of $q^*$ mostly for notational consistency, but we should note the confluence here.

2. While we do not have a formal result, our impression is that the driving issue here is not the coverage loss, but the sort of extreme case of non-realizability they construct. When the supports of the distributions in the model class $\mathcal{Q}$ have so little overlap with the data generating distribution $P$, there is no way to ascertain which models are valid and which aren't without something close to exhaustively searching through them. The choice of loss does not feel helpful in resolving this -- for example, there is nothing about the maximum likelihood model $q$ that guarantees any sort of validity in the worst case.

3. Our writing in this paragraph is imprecise, and will be cleaned in the next version. By "realizable complexity" we were referring to the fact that $P \in \mathcal{Q}$ in the setting of Theorem 1. Given that the lower bound only applies to proper learners, the reviewer is correct in saying that it's possible there is an improper algorithm that surpasses the $\Omega(1/\epsilon_2)$ lower bound. That said, this feels to us somewhat unlikely given that the improperness of Algorithm 1 arises so that we can control the loss -- it is done so that we don't output a hypothesis that is small in total variation to $P$ but large in KL-divergence. From the perspective of invalidity, small total variation to $P$ is sufficient.

4. The reviewer is correct: the samples from $P$ do not need to be queried for validity, and updating the algorithm to reflect this saves a constant factor. We left this detail out originally, but will add it to Algorithms 2 and 3 in the next version.

5. The reviewer is correct that likelihood maximization is really what's doing most of the legwork in Theorem 1 (via Lemma 6). There is one other feature of the log-loss (see Lemma 8) which we use in Theorem 1 and Theorem 4: for mixture distributions $f_M(x) = (1-\epsilon) f_q(x) + \epsilon f_{r}(x)$, the form of the log-loss admits the inequality $\log(1/f_M(x)) \leq 2\epsilon + \log(1/f_q(x))$. In the case of Theorem 1, this allows us to argue that mixing with the uniform distribution does not degrade the loss too much. There are definitely some nice generalizations that can be made.

6. This is a good catch. The $f^n_P$ outside of the minimum in line 470 is a typo. The proof is correct when it is removed.

7. We use samples from both $P$ and the ERM in Algorithm 2 is so that we get a single estimate of the validity function $\hat{v}$ which has a high probability of agreement with the true validity function $v$ under samples from both distributions. Basically, we use the accuracy of the estimate $\hat{v}$ under $P$ to ensure that the loss of the returned distribution is small, and the accuracy of the estimate $\hat{v}$ under the ERM is to bound the invalidity. If we could return a distribution constructed by "accepting/rejecting" samples from the ERM using the true validity function $v$, we'd have perfect validity, but under an estimate of $v$, we need to make sure this estimate doesn't disagree too much with $v$ precisely under the proposal distribution $\hat{q}_{ERM}$, or too many invalid samples may be leaked.

We appreciate the review, and will try to address the weaknesses they point out.

We would argue that most practical situations are likely closer to the regime of realizability explored in the first half of this paper than the case where no model in the model class is a reasonable approximation for the data generating distribution, the setting which motivates algorithms in previous work [1].

It also seems that valid regions of space are "learnable" in practice, motivating the second half of the paper where the validity function is known to lie in a bounded complexity class. For example, [3] found empirical success on the problem of post-editing GANs by coaxing GANs towards their restriction to "valid" parts of space.

[1] Hanneke, S., Kalai, A., Kamath, G., & Tzamos, C. (2018). Actively Avoiding Nonsense in Generative Models. https://arxiv.org/abs/1810.06988
[3] Kong, Z., & Chaudhuri, K. (2022). Data Redaction from Pre-Trained GANs. https://arxiv.org/abs/2206.14389

We thank the reviewer for looking closely at our work, and apologize for sometimes being less clear than we should.

In line 37 ("while achieving polynomial bounds on the number of validity queries, uses relative large number of validity queries''), what we were referring to is that the improper algorithm of Hanneke et al. makes $\tilde{O}(1/\epsilon_1^2 \epsilon_2)$ validity queries, which looks large relative to the quadratic dependence one is used to seeing. It's an open question what the right query complexity is for the general case discussed by Hanneke et al. [1]., so this sentence should probably be reworked.

In line 232-233 ("guarantees for the log-loss are attainable, at least improperly"), the reviewer is correct in assuming that by invoking “improper” learning here, we are referring to the fact that we output a mixture of the ERM and the uniform distribution in Algorithm 1. Satisfying the loss requirement with a proper learner will in general require many more samples than $\tilde{O}(1/\min(\epsilon_1^2, \epsilon_2)$, as there may be some $\tilde{P} \in \mathcal{Q}$ which is very close in total variation to $P$, but has infinite KL-divergence from $P$.

With regard to computational considerations, the algorithms are in general inefficient. For efficiency, one needs access to an efficient ERM routine over the distribution class $\mathcal{Q}$ -- in this sense, our work follows in the line of original work of Hanneke et al. [1]., who assume access to an efficient (constrained) ERM oracle for computational efficiency. In the cases of Algorithms 2 and 3, one also needs access to an efficient ERM routine over the VC class. It's true that many important VC classes do not admit efficient ERM.

[1] Hanneke, S., Kalai, A., Kamath, G., & Tzamos, C. (2018). Actively Avoiding Nonsense in Generative Models, https://arxiv.org/abs/1810.06988

We appreciate the review, and agree that the next version of the paper should furnish more practical insight.

We mainly see these results as a first attempt at studying the problem of learning a valid generative model from the opposite perspective of [1], which paints learning in this setting as a complex endeavor. In practice, generative models do often suffer from invalidity issues, leading to a variety of techniques for mitigating this issue, many of which are quite intuitive and feasible [2, 4, 5, 6]. We hope this work can spark further investigation into uncovering natural settings where practical algorithms can be effective.

Lemma 2 -- which shows that validity naturally arises when the data distribution $P$ is in the model class $\mathcal{Q}$ -- is intended to shed light on what learning a valid generative model is like when the model class $\mathcal{Q}$ contains good approximations of the "validity-filtered" data distribution. While the rates in Lemma 2/Theorem 1 hold only for the realizable case, we would argue that this setting likely a more faithful representation of generative modeling in practice than the more general setting of [1], where much of the complexity seems to come from the possibility that all models in $\mathcal{Q}$ bare little to no resemblance to the data generating distribution $P$. Basically, our claim here is that learning the distribution well is really what needs to be done – if you’ve learned well in this setting, you’re unlikely to generate invalid outputs.

In the second half of the paper, we consider the possibility of learning the validity function and restricting the ERM model to the learned "valid" part of space. One recent applied work [3] similarly considers post-editing GANs by "learning the data distribution restricted to the complement of the [valid part of space]". Explaining the success of such schemes that operate on the estimation of the validity function requires relaxations of the original learning model of [1], where the validity function cannot be estimated well with a polynomial number of queries.

[1] Hanneke, S., Kalai, A., Kamath, G., & Tzamos, C. (2018). Actively Avoiding Nonsense in Generative Models. https://arxiv.org/abs/1810.06988
[2] Kaneko, T., & Harada, T. (2021). Blur, Noise, and Compression Robust Generative Adversarial Networks. https://arxiv.org/abs/2003.07849
[3] Kong, Z., & Chaudhuri, K. (2022). Data Redaction from Pre-Trained GANs. https://arxiv.org/abs/2206.14389
[4] Schramowski, P., Brack, M., Deiseroth, B., & Kersting, K. (2023). Safe Latent Diffusion: Mitigating Inappropriate Degeneration in Diffusion Models. https://arxiv.org/abs/2211.05105
[5] Malnick, S., Avidan, S., & Fried, O. (2023). Taming Normalizing Flows. https://arxiv.org/abs/2211.16488
[6] Liu, J., Xu, J., & Wang, Y. (2022). Efficient Retrieval-Augmented Generation: An Empirical Study of Practical Techniques. https://arxiv.org/abs/2210.04610