Distribution Learning with Valid Outputs Beyond the Worst-Case

Authors: nick  rittler
kamalika  chaudhuri
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 21:27:22

Abstract: Generative models at times produce "invalid" outputs, such as images with generation artifacts and unnatural sounds. Validity-constrained distribution learning attempts to address this problem by requiring that the learned distribution have a provably small fraction of its mass in invalid parts of space -- something which standard loss minimization does not always ensure. To this end, a learner in this model can guide the learning via "validity queries", which allow it to ascertain the validity of individual examples. Prior work on this problem takes a worst-case stance, showing that proper learning requires an exponential number of validity queries, and demonstrating an improper algorithm which -- while generating guarantees in a wide-range of settings -- makes a relatively large polynomial number of validity queries. In this work, we take a first step towards characterizing regimes where guaranteeing validity is easier than in the worst-case. We show that when the data distribution lies in the model class and the log-loss is minimized, the number samples required to ensure validity has a weak dependence on the validity requirement. Additionally, we show that when the validity region belongs to a VC-class, a limited number of validity queries are often sufficient.

Main paper: 
 introduction: 
 When sampling from a generative model, it is highly desirable that its outputs meet some basic criteria of quality. In the case of text, this may mean that generated sentences respect grammar rules, or avoid the use of biased or offensive language [1, 2] . When generating code, a criterion may be that the generated code successfully compiles [3] . In image generation, we might wish to avoid blurry outputs, or those possessing generation artifacts which clearly distinguish them from natural images [4, 5] .In this paper, we examine the statistical cost of ensuring that learned distributions produce such "valid" outputs. To do so, we consider an elegant formulation of the problem of learning such valid models due to [3] . In their work, training data are generated according to a probability distribution P , and the binary "validity" of examples is determined by some unknown "validity function" v. Given sample access to P and query access to v, a learner attempts to identify a probability distribution which outputs invalid examples with probability at most 2 . At the same time, the distribution should have a loss which is at most 1 worse than that of the minimum loss model in a class Q which outputs valid examples with probability 1. Here, query access to v captures the idea that collecting samples is often cheap, but verifying validity is often less so, possibly requiring a human-in-the-loop.The initial work of [3] suggests that choosing such a low-loss, high-validity distribution q may require a large number of validity queries. Under the assumption that P is "fully-valid", i.e. outputs a valid example with probability 1, they show that in the worst case, 2 Ω(1/ 1) validity queries are required to choose such a model q from the class Q. They follow this result with an improper learning algorithm for choosing q which, while achieving polynomial bounds on the number of validity queries, uses a relatively large number of validity queries Õ log(|Q|)/ 2 1 2 . The somewhat pessimistic picture painted by these fascinating complexity-theoretic results can be tracked to their generality. Firstly, it's possible that Q and P are significantly "mismatched", i.e. the support of each model q ∈ Q has only a small overlap with the support of the distribution P , in which case the validity information contained in valid training samples is unhelpful to a proper learner. Secondly, their improper learning algorithm is largely loss-agnostic, in that it generates guarantees for a wide class of bounded loss functions. Finally, nothing is assumed about the form of the validity function v, precluding provable estimation.In this work, we offer a counterbalance to this picture, beginning an investigation into learning settings where guaranteeing validity is cheaper than such results might indicate. We first consider learning under complete elimination of model class mismatch, where Q is rich enough to contain the fullyvalid data distribution P , and the loss is the log-loss l(f (x)) = log(1/f (x)). It is intuitive that in this setting, loss minimization alone should guarantee validity. Somewhat less intuitively, we demonstrate an algorithm closely related to empirical risk minimization which uses just Õ log(|Q|)/ min( 21 , 2 ) samples to guarantee its output meets loss and validity requirements -in other words, validity comes quickly under random sampling from P in this setting.Secondly, we consider learning under a different realizability assumption, namely that the validity region is a member of a VC-class of dimension D. In this setting, we provide an analysis of the natural scheme of restricting the empirical risk minimizer to an estimate of the valid part of space. We show that when small-loss models q ∈ Q have at least constant validity, this scheme uses Õ (D/ 2 ) validity queries, implying a query cost reduction over the general-purpose algorithm of [3] . We also show that learning under the capped log-loss can be used to relax the assumption of constant validity at the cost of an extra factor of 1/ 1 .Our results suggest the existence of a rich web of settings in which validity may be cheaper than in the general case. They also suggest that the choice of the loss plays an important roll in guaranteeing valid outputs, compelling further investigation of the log-loss in particular.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: We think so.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 The framing of learning distributiuons in terms of PAC guarantees similar to [6] dates back to [7] , who consider the learnability of specific classes of discrete distributions under a realizability assumption. A significant body of work on distribution learning has been developed overtime, often focusing on algorithms for learning over parametric families or under specific "structural" assumptions [8, 9, 10, 11] . The only theoretical contribution to validity-constrained distribution learning under the formulation posed by [3] that we are aware of is that work itself.The study of loss functions for the evaluation of probabilistic models has often been studied the lens of "scoring rules" in the forecasting literature [12, 13, 14] . There are some notable recent contributions towards expanding the understanding of when loss functions for distribution learning display desirable properties, e.g. "properness", which designates that the loss is minimized by the true data distribution [8, 15] .The first half of this paper draws on intuition from hypothesis testing to evaluate the performance of empirical risk minimization. Hypothesis testing is a major focus of the classical statistics literature [16] . The bounds in the first half of the paper are due to analysis inspired by the Neyman-Pearson lemma [17, 18] , and rely on the approximation of total variational distance between product measures [19] .The applied literature on generative modeling has consistently noted the problem of learned models producing "invalid" examples [20, 21, 22, 4] . Various techniques have been proposed for mitigating invalidity generally, and in domain specific settings [23, 20, 24] . While working under the assumption that the validity function lies in a VC-class, the strategy we introduce has some rough semblance to a "post-editing" procedure proposed by [24] .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: Yes, the assumptions in theorem statements are made clear.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
problem setup: 
 Let X be a subset of Euclidean space R d with finite Lebesgue measure λ. Let P denote the set of all probability distributions on the measurable space (X , F X ), where F X arises from Lebesgue measurable sets intersected with X . Let P ∈ P be the data-generating distribution.In the eyes of the learner, the function v : X → {0, 1} is a fixed and unknown "validity function", measurable with respect to the relevant distributions. The validity function denotes whether or not an example x ∈ X is considered a valid output for a learned approximation of P . The learner is given a model class of Q ⊂ P of probability distributions on X , each with density f q with respect to λ, and afforded with the knowledge that at least one q ∈ Q is "fully-valid", i.e. that there is some q ∈ Q with invalidity V (q) := Pr X∼q (v(X) = 1) = 1. We at times use the notion of "invalidity" of a model, by which we mean I(q) = 1 -V (q). Following the main exposition of [3] , we assume Q is of finite cardinality.The goodness-of-fit of a model q ∈ P is governed by a decreasing "local" loss function l : R ≥0 → R ∪ {∞}. Such a loss function gives rise to loss of model via L P (q; l) := E X∼P [l (f q (X))]. Given an i.i.d sample S from P , we let the empirical estimate of the loss of a model be L S (q; l) = xi∈S l(f q (x i ))/|S|. We use the shorthand L P (q) and L S (q) to denote the true and empirical losses of q under the log-loss l(q) = log(1/f q (x)), where log denotes the natural logarithm. We take the log-loss to be infinite at points where f q (x) = 0.The goal of the learner is to choose some q ∈ P which has a loss L P (q; l) similar to that of the lowest-loss fully-valid model in Q, while simultaneously maintaining near full-validity. Explicitly, consider the model q * := arg min q∈Q:V (q)=1 L P (q; l).To describe the quality of an outputted model, we consider two learning parameters 1 and 2 , where 1 is used to control the loss sub-optimality, and 2 to control the invalidity. Formally then, the goal of the learner is to output q ∈ P satisfying L(q) ≤ L(q * ) + 1 and I(q) ≤ 2 . To accomplish this goal, the learner has sample access to P , and query access to v, i.e. a learner can draw any finite number of i.i.d. samples from P , and any request the value of the validity function v at any finite number of inputs in X .At a minimum, we are interested in algorithms which require a number of samples from P and number validity queries that is polynomial in log(|Q|), 1/ 1 and 1/ 2 . Ideally, we would like to minimize the number of validity queries given some polynomial number of samples from P . The motivation for this goal is similar to the minimization of label queries in active learning for classification [25] , where samples from the marginal over instances are often cheap, but labeling such examples is assumed expensive.We assume that all samples from the data-generating distribution P are valid, i.e. that V (P ) = 1.Under such an assumption, the query demand of a learning algorithm can be conceptualized as the overhead number of queries sufficient for choosing a good model under the standard procedure of removing invalid examples from the training set.If the data distribution is not fully-valid, and valid samples are required by an algorithm, the question of minimizing the overall number of queries is dependent on the sample complexity of learningif one assumes that P has been constructed by "accepting" valid samples from some underlying distribution which outputs a valid sample with constant probability, then the overall query cost incurred by an algorithm is on the order of the larger of the number of samples and the number of "overhead" validity queries it uses.In this paper, we are primarily interested in the "overhead" number of queries, which we refer to as the "number of validity queries" of a given scheme. In most cases, algorithm sample requirements are similar to O(log(|Q|)/ 2 1 ), which allows for accurate loss estimation in many settings.The learning problem above is due to [3] , who considered the possibility of specifying learning algorithms meeting the above bi-criteria objective for any choice of bounded, decreasing, local loss function.This work gives some interesting insight into the difficulty of selecting such a low-loss, high-validity model. They begin by giving a negative result, namely that any proper learning algorithm outputting q ∈ Q, must make 2 Ω(1/ 1) validity queries in the worst case, regardless of the number of samples available from P . This result arises from a specific problem instance wherein every q ∈ Q has a significant amount of mass outside of the support of P , in which case samples from a fully-valid P do not give information about v in parts of space relevant to the choice of q ∈ Q.On the other hand, they demonstrate an improper learning algorithm which achieves polynomial bounds on samples and validity queries for any choice of loss meeting the above criteria. Their algorithm harnesses a constrained ERM oracle, iteratively querying the validity of samples from the model q ∈ Q which is the empirical loss minimizer putting no mass on points known to be invalid. In particular, their scheme uses Õ(log(|Q|)/2 1 ) samples and Õ(log(|Q|)/ 2 1 2 ) validity queries.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
learning without model class mismatch under the log-loss: 
 We first consider the problem of selecting a low-loss, high-validity model under a relaxation of two of the main sources of difficulty in original problem formulation: the misalignment of the model class Q with the data distribution P , and the lack of assumptions on the loss.In particular, we consider the problem under a realizability assumption, namely that P ∈ Q, further investigating the power of the log-loss. Such a setting is arguably more closely aligned with contemporary learning settings with rich model classes that appropriately capture features of the underlying data distribution, where the validity information contained in samples from P can be exploited by convergence to the best information-theoretic representation of P in Q.The log-loss is by far the most widely-used loss in practice [8] . It is a classic result of the proper scoring rule literature that the log-loss is the unique strictly-proper local loss, i.e. the only local loss under which for all distributions q = P , it holds that L P (P ; l) < L P (q; l). This highly desirable property -implying that convergence to the optimum over P coincides with convergence to Pmakes the choice of an alternative outside of capped variants preferable only under specialized circumstances.Given that samples are assumed to be valid, and the log-loss permits convergence to the data generating distribution, one would hope that simply selecting a model q ∈ Q which is a sufficiently good representation of P under the log-loss would yield validity guarantees in this setting. Simply utilizing empirical risk minimization (ERM) is the canonical approach to this end, and one which, given sufficient data from P , uses exactly zero validity queries.Note that any model q with invalidity I(q) > 2 necessary has d T V (q, P ) > 2 . In this case, q must have at least 2 mass in the invalid part of space, where P has none. Thus, if one can guarantee that q has d T V (q, P ) ≤ 2 , the validity requirement is met. Recalling the Pinsker inequality d T V (q, q ) ≤ O( d KL (q, q )) relating total variational distance and KL-divergence, it follows that obtaining a model q which is at most 2 2 sub-optimal in log-loss yields a model meeting the validity requirement.While this illustrates useful intuition for the setting, it glosses over two main issues. Firstly, empirical estimates of the log-loss do not admit concentration guarantees -one can construct simple examples where E X∼P [log(1/f q (X))] is unbounded above, but with high probability, the empirical estimate L S (q) = x∈S log(1/f q (x))/|S| is approximately that of P [8] . Thus, selecting low-empirical loss models can never yield loss guarantees. Secondly, this application of Pinsker's inequality demands q ERM ← arg min q∈Q xi∈S log (1/f q (x i ))3:return q = (1 -∧ /8) • q ERM + ∧ /8 • uMix ERM, uniform distribution 4: end procedureWe would hope that in the case that zero-query learning is possible, that guaranteeing validity arises somewhat coincidently with convergence to P , meaning that the sample complexity is not much worse given a validity requirement than without one. Thus, the path towards satisfaction of the learning objectives requires subtle handling, and compels particular attention to the sample complexity dependence on the validity parameter 2 .As indicated above, it is not possible to guarantee that empirical risk minimization (ERM) outputs a model with small log-loss. It is, however possible to guarantee that it outputs a model which closely resembles P and inherits validity guarantees with a small number of samples.In particular, it's possible to show that given sufficient samples, ERM yields a model with small total variation to P when P ∈ Q. This is due to the following folklore theorem [8] , which we prove under assumption of density existence in the Appendix. Lemma 4. Fix 0 < , δ < 1 arbitrarily, and let P, q ∈ P be distributions with densities with respect to λ. Then if d T V (q, P ) ≥ , and S ∼ P n for n ≥ Ω(log(1/δ)/ 2 ), it holds with probability ≥ 1 -δ that L S (P ) < L S (q). Thus, at the statistical cost of estimating a coin bias, any distribution q with total variation ≥ from the data distribution will reveal itself to be empirically inferior when the log-loss is used. This can be easily leveraged to generate guarantees for ERM over Q in terms of total variation.It is tempting to think that this is the entire story when it comes to guaranteeing validity. After all, we argued above that small total variation from P is sufficient for 2 invalidity. That said, simply looking at total variation ignores a particular structural feature of distributions q with I(q) > 2 -in particular, such distributions have mass in parts of space in which P does not.This observation can be used to construct tight lower bounds on the total variational distance between product measures arising from P and q with I(q) > 2 . This leads to the following result, which states that ERM yields a faithful representation of the data generating distribution that is at most 2 invalid given a number of samples with a modest dependence on the validity parameter 2 .Lemma 5. Fix 0 < δ, 1 , 2 < 1 arbitrarily, and suppose P ∈ Q. If P is fully-valid under v, andS ∼ P n for n ≥ Ω log(|Q|)+log(1/δ) min( 2 1 , 2), then with probability ≥ 1 -δ over S ∼ P n , the ERM solution q = arg minq∈Q xi∈S log(1/q(x i )),satisfies both d T V (q, P ) ≤ 1 and I(q) ≤ 2 .Note that this guarantee is not redundant -having d T V (q, P ) ≤ 1 does not imply I(q) ≤ 2 when 2 < 1 .This result can be interpreted as a vote of confidence for the naive training of generative models under the log-loss. Nevertheless, from a learning-theoretic perspective, there is a question whether or not it is possible to guarantee low log-loss while maintaining validity with zero validity queries.While ERM cannot possibly furnish log-loss guarantees, it turns out that it is possible to modify the output of ERM to generate log-loss guarantees at the cost of an extra polylogarithmic factor in the sample complexity, at least when the densities f q are bounded above and below in their support. 1 The idea, formalized in Algorithm 1, is simply to mix the output of ERM with the uniform distribution.Giving the uniform distribution a mixture component on the order of min( 1 , 2 ) can be shown to ensure that the validity guarantees of the ERM output are preserved, while also giving the outputted distribution support across the entire space. This leads to the following theorem.Theorem 1. Fix 0 < δ, 1 , 2 < 1 arbitrarily, and suppose P ∈ Q and that P is fully-valid under v.If it holds that for each q ∈ Q that α ≤ f q (x) ≤ β for all x ∈ supp(q), then there is anN ≤ Õ log 2 (1/ min( 1 , 2 , α)) • log(|Q|) + log(1/δ) min( 2 1 , 2 ), such that for all n ≥ N , with probability ≥ 1 -δ, the output q of Algorithm 1 satisfies L P (q) ≤ L P (q * ) + 1 and I(q) ≤ 2 .Here the Õ notation hides a polylogarithmic dependence on 1/β, which is insignificant in most regimes, and treats the density of the uniform distribution over X as a constant, which would otherwise also enter polylogarithmically.Theorem 1 shows that guarantees with respect to the unbounded log-loss are attainable improperly, i.e. when the learner can choose q / ∈ Q. It's an interesting question whether the logarithmic dependence on min( 1 , 2 ) can be removed with a more subtle strategy.One might suspect that achieving a smaller dependence than 1/ 2 on the validity parameter should be impossible. We confirm this is true at least for proper learners, showing that the analysis of ERM in Lemma 5 is tight in its dependence on 2 . This lemma is used to generate the validity guarantee in Theorem 1.Theorem 2. For all 2 < 1/4 and for all proper learners L : S → P, if the sample S ∼ P n is of size n ≤ 1/8 2 , then there exists a triple (P, Q, v) with P ∈ Q and P fully-valid, on which L(S) has invalidity I(L(S)) > 2 with probability ≥ 1/4.The intuition here is that while any invalid q ∈ Q has at least 2 total variation from P , in the worst case, the total variation between q and P is upper bounded by O( 2 ) as well. This makes distinguishing between P and some 2 invalid distribution hard enough to generate such a lower bound.The sample requirement of 1/ 2 1 , both in our guarantees and in previous work, is a standard offshoot of loss estimation, irrespective of the search of a valid model. In general, one cannot expect improvements to this end -this is the standard dependence one finds for estimating the means bounded random variables. This suggests that the "realizable complexity" for this setting is 1/ min( 21 , 2 )while non-zero losses should not be generally estimable using "realizable" techniques, guaranteeing small invalidity can when P ∈ Q. 
utilizing estimates of the validity function in training: 
 In the general formulation of the problem, the learner is given an arbitrary bounded, decreasing loss, a model class Q which is mismatched with P , and has no a priori information about the validity function v. In such a setting, it is clear that validity queries are necessary.In this section, we consider a setting where it is known to the learner that v can be found in a hypothesis class V of bounded complexity. Under such an assumption, we would hope to be able to lower the number of validity queries beyond the bounds of [3] .1: procedure valid_restriction(Distribution Class Q, Validity Class V, 1 , 2 , δ, γ) 2: S ← Ω M 2 (log(|Q|)+log(1/δ)) 2 1 i.i.d. samples ∼ P 3:q ERM ← arg min q∈Q x∈S l(q(x))4:S P ← Ω M (D log(M/ 1 )+log(1/δ)) 1 i.i.d. samples ∼ P , S q ERM ← Ω D log(1/γ 2)+log(1/δ) γ 2 i.i.d. samples ∼ q ERM 5: v ← arg min h∈V x∈S P ∪S q ERM 1[h(x) = v(x)]Label S q ERM via queries to v 6:return f q ∝ f q ERM (x) • 1[v(x) = 1] if q ERM ({v(x) = 1}) > 0 else f q = f q ERM 7: end procedureA natural algorithm in this setting is to "correct" the invalidity of the empirical risk minimizer -to restrict the empirical risk minimizer to parts of space which are valid with respect to an estimate of the validity v. This is the precisely the idea formalized in Algorithm 2.To generate guarantees for such a strategy, one must determine the distribution with respect to which the estimate v should be accurate. In our case, we generate accuracy guarantees over both P and the ERM model q ERM by selecting an estimate v that has 0 empirical error over both distributions. The source of the query complexity of the algorithm comes from the fact that samples arising from q ERM must be labeled by oracle calls to v. Noting that samples from P can be automatically labeled as valid by the full-validity of P saves a constant factor over naively labeling all examples acquired in the second half of the algorithm.Accuracy under samples from P allows one to control the loss of q by invoking the boundedness of the loss in the disagreement region of v and v, and guarantees with respect to q ERM allow us to bound the invalidity of the restriction. Because P is fully-valid, loss contributions from the agreement region of v and v correspond to parts of space where v(x) = 1 -as the loss is non-increasing, placing more mass in such parts of space can never increase the loss contribution attributable to integrating over this region.Algorithm 2 also requires a parameter γ > 0. This parameter should be a validity lower bound on the models q ∈ Q, providing a safeguard on the possibility of an "invalidity blowup" when restricting the ERM output to a certain region of space -one must normalize the restriction to output a probability distribution, which in this case means increasing mass in parts of space that are estimated to be valid. An a priori lower bound on the validity allows for precise enough estimation of v that increasing the mass in such regions is unlikely to lead to appreciable invalidity in the final model.It's possible that the restriction of the ERM estimated valid region is undefined -this happens if and only if the estimated valid region has zero mass under the ERM. Given validity lower bounds for models q ∈ Q , this is a low probability event which can occur only when estimation of the validity function is very poor relative to the query complexity. As one might imagine, the handling of this case is immaterial for PAC-guarantees. We choose to arbitrarily define behavior in this case by outputting the ERM model.The restricted output q of Algorithm 2 admits the following guarantee over loss sub-optimality and invalidity.Theorem 3. Suppose v ∈ V with VC-dimension V C(V) ≤ D, and that for each q ∈ Q, the validity V (q) ≥ γ > 0. For all 0 < 1 , 2 , δ ≤ 1 and for all choices of non-increasing loss functions l : R ≥0 → [0, M ], Algorithm 2 requires a number of samples≤ O M 2 (log(|Q|) + log(1/δ)) 2 1 + M (D log(M/ 1 ) + log(1/δ)) 1 ,and a number of validity queries≤ O D log(1/γ 2 ) + log(1/δ) γ 2 ,to ensure that with probability ≥ 1 -δ, its output enjoysL P (q; l) ≤ L P (q * ; l) + 1 and I(q) ≤ 2 .Thus, in regimes where e.g. γ ≥ Ω( 1), D = Θ(log(|Q|)), this guarantee represents a reduced number of queries under the Õ(M 2 log(|Q|)/ 2 1 2 ) bound of [3] . It also implies a "decoupling" of the query complexity from 1 .We note that the sample requirement from P is increased in certain regimes over the Õ(log(|Q|)/ 2 1 ) requirement of [3] . This is, however, not a concern in most settings where validity queries are expensive. If samples from a fully-valid P are readily obtainable, the setting is analogous to that of active learning, where focus is directed to the number of labels requested in training.Even if P must be constructed by "accepting" valid samples from some unfiltered P , a comparison between the query complexity of Theorem 3 and the query bound of [3] is often still representative of the relative data costs of the schemes. Supposing P produces valid samples with constant probability, the total number of validity queries made by each scheme is proportional to the scheme's sample requirements from P , plus the number of validity queries used in its execution. Essentially, to yield validity query speedups, our scheme requires a VC bound on V which does not dwarf log(|Q|). Thus, in most cases of interest, the querying the validity of Õ (M D/ 1 ) extra samples is asymptotically inconsequential relative to O(M 2 log(|Q|)/ 2 1 ), and the Õ (D/γ 2 ) query budget required to execute the algorithm given access to a fully-valid P .Theorem 3 presents a somewhat pessimistic view of the potential of such a "post-filtering" scheme.Firstly, it ignores the potential of active learners to improve query complexities over passive sampling. Query complexities in active learning of classifiers are often expressed in terms of the "disagreement coefficient" [26] , often denoted via θ. In the realizable setting, query complexities of active learning look like Õ(Dθ log(1/ )) [27] . Definitionally, it can be shown that θ ≤ 1/ . Thus, proving the gains of active learning algorithms usually relies on bounding the disagreement coefficient non-trivially, i.e. showing θ < o(1/ ), or ideally, θ ≤ O(1).While this is challenging, as θ is both a class and distribution-dependent quantity, there is a literature that addresses this potential in various settings -see the references in [25] . In principle, one could use such an analysis to show that the query complexity of an active learning modification of Algorithm 2 is on a lower order than the guarantee of Theorem 3 when conditions are favorable. To this end, it may be useful to note that a modification of Algorithm 2 wherein v is selected as the ERM on a dataset generated by a mixture of P and q ERM admits guarantees as well.Another source of potential looseness in the statement of Theorem 3 is that it phrases the query complexity in terms of the worst-case validity over models q ∈ Q. This is unnecessary -with high probability, in the first step of the algorithm, one selects a model q ∈ Q with O( 1 ) true loss. Thus, what really matters for such a strategy is that models that have relatively small loss l do not have invalidity nearing 1. This is a realistic scenario in the case that the loss function l -despite possibly not being proper -prioritizes models which in some sense resemble the data generating distribution P . Indeed, it's somewhat difficult to envision a situation where a loss would be chosen that prioritizes models with no relation to the data generating distribution. To this end, we give the following corollary to Theorem 3. Corollary 1. Under the conditions of Theorem 3, if in addition it holds that all models q ∈ Q with loss sub-optimality 1 have validity greater than some constant, then the query complexity of Algorithm 2 can be improved to≤ O D log(1/ 2 ) + log(1/δ) 2 .Using an idea found in the algorithm of [3] , one can show that if a learner has access to single distribution D with a density and at least some non-zero constant validity, and the densities f q are bounded above, that Algorithm 2 can be modified so as to drop the requirement of positive validity over models when learning under the capped log-loss.By mixing the q ERM with D, giving mixture component O( 1) to D, one can generate similar guarantees as those of Theorem 3. The modification can be found in the Appendix as Algorithm 3, and enjoys the following guarantee. Theorem 4. Suppose v ∈ V where V C(V) ≤ D, and that for each q ∈ Q, we have f q (x) ≤ β.Suppose further that there is some known D ∈ P with density f D which has V (D) ≥ c > 0 for some constant c. Then for all choices of 0 < 1 , 2 , δ < 1/2 and M > 0, Algorithm 3 requires a number of samples≤ Õ M 2 (log(|Q|) + log(1/δ)) 2 1 + M (D log(M/ 1 ) + log(1/δ)) 1 ,and a number of validity queriesEQUATION, to ensure that with probability ≥ 1 -δ, its output enjoysE X∼P min (M, log(1/f q (X))) ≤ E X∼P min (M, log(1/f q * (X))) + 1 and I(q) ≤ 2 .Here, the Õ notation again hides factors polylogarithmic in 1/β.Note that the Õ now appears in the sample complexity. This simply reflects the fact that the M -capped log-loss can range between gap M and log(1/β) when working with densities bounded above by β ≥ 1. In the case that densities can be bounded above by 1, as in the discrete setting of [3] , this dependence disappears. 
conclusion: 
 This work is intended as a first-look into settings closer to the common-case, where ensuring validity may be relatively cheap.A more thorough investigation of the log-loss, as well as capped variants, seems a very relevant line of further inquiry, given the widespread use of this family in practice and its useful information-theoretic properties. A natural extension to the first part of this work would be to consider learning in the agnostic case P / ∈ Q under the log-loss, where one would hope to be able to exploit these properties and the validity of training samples to keep the number of validity queries low.In general, characterizing the sample and query demands of validity-constrained distribution learning is challenging, given that proving lower bounds in general requires arguing against learners with two tools at their disposal -sampling and actively querying validity. Work in this direction will likely require some creative constructions. 
probability distributions and measure theoretic formalism: 
 We work over Euclidean space R d and let X be a Lebesgue measurable set with Lebesgue measure λ(X ) < ∞. By λ and Lebesgue measurable set, we refer to the measure and σ-algebra F arising from the usual construction of Lebesgue measure on R d . By "distribution", we mean a probability measure on the measurable space (X , F X ), where F X = {E ∩ X : E ∈ F}. Let u the uniform distribution be the measure given by u(E) = λ(E)/λ(X ) for E ∈ F X . Let P denote the set of all probability measures on (X , F X ).We assume that P ∈ P and q ∈ Q ⊂ P have densities f P and f q with respect to the reference measure λ. At times, it will be useful to assume that densities are bounded away from zero in certain parts of space. By saying densities are bounded in their support by β > α > 0, we mean that for all x ∈ supp(q) := cl{x : f q (x) > 0}, we have α ≤ f q (x) ≤ β, where the closure is defined through open balls in the Euclidean metric. Note that in this setting, we have q(supp(q)) = 1, asq(supp(q) c ) = 1[x ∈ supp(q) c ]f q (x)dλ(x) = 0dλ = 0.Denote via q n = q ⊗ • • • ⊗ q the product measure over the measurable space (X ⊗n , F ⊗n X ). Such a measure corresponds to the process of taking n i.i.d. samples ∼ q. Denote the density of q n with respect to λ n via f n q .We define log(1/0) = ∞. Following the conventions in [28] , we say that 1[x ∈ E] • g(x) = 0 if g(x) < ∞ for x ∈ E and g(x) = ∞ for some x ∈ E c. This allows us to integrate over the finite part of functions and get a finite result.To facilitate digestibility, we refrain from measure theoretic notation as much as possible. It is at times useful, particularly in dealing with total variation. We assume throughout that all functions we encounter in the Appendix -including the fixed validity function v and functions in the validity class V -are (X , F X )-measurable.We fix the validity function v as an arbitrary function v : X → {0, 1} measurable with respect to each distribution q arising in the Appendix. As discussed above, for a given model q ∈ P, the "validity" of q is the quantity V (q) = Pr X∼q (v(X) = 1), and the "invalidity" I(q) = 1 -V (q). We will at times be interested in estimating the validity of a model q using samples from q along with validity queries. Given an i.i.d. sample {X i } n i=1 from q, we let V (q) = n i=1 v(X i )/n be the natural estimate of the validity of q.At times, we will be interested in the validity of a model under an estimate of the underlying validity function. To this end, given a model q ∈ P and a function g : X → {0, 1}, we let V g (q) = Pr X∼q (g(X) = 1). Given a sample {X i } n i=1 , let Vg (q) = n i=1 g(X i )/n. Note that in the language of this notation, we have V (q) = V v (q) and V (q) = Vv (q). We extend this notation in the natural way to invalidity quantities.To begin our analysis of the realizable setting, we first observe that models with appreciable invalidity look very different from a fully-valid data generating distribution -because they must have mass in parts of space where P does not, they are separated in total variation from P by a margin. We formalize this idea via the following.Lemma 1. Fix 0 < < 1 arbitrarily. For any validity function v, if q ∈ P has I(q) > , and P ∈ P has I(P ) = 0, then d T V (P, q) > .Proof. Fix the validity function arbitrarily. Consider the event E ¬v = {x ∈ X : v(x) = 0}. Then we have d T V (P, q) = sup E⊆X |P (E) -q(E)| ≥ q(E ¬v ) -P (E ¬v ) > , where we have used that I(P ) = 0 implies P (E ¬v ) = 0.We next extend this observation to the associated product measures, which are the main target of analysis under i.i.d. sampling from P . The idea is to lower bound the total variation between product measures by the difference in probabilities on the event that at least one example from a sample of size n is invalid. Of course, for each sample, this happens with probability 0 under P and with probability at least under any model q with at least invalidity. Thus, identically to how one shows realizable rates for classification tasks, we attain a large total variation gap between P and any q with appreciable invalidity -mistakes in classification are thus analogous to the generation of an "invalid" samples in our setting.Lemma 2. Fix 0 < < 1 and n ∈ N \ {0} arbitrarily. For any validity function v, if q ∈ P has I(q) > , and P ∈ P has I(P ) = 0, thend T V (P n , q n ) > 1 -e -n .Proof. Fix the validity function arbitrarily. Consider lower bounding the total variation between the product measures via the magnitude of the difference of their measures on the eventE ≥1 = (x 1 , . . . , x n ) ∈ X n : ∃i s.t. v(x i ) = 0 .Because P has perfect validity, any given draw from P has probability 0 of being invalid. Thus, P n (E ≥1 ) = 0. On the other hand, the invalidity of q states that for any1 ≤ i ≤ n, we have q({x ∈ X : v(x) = 0}) > . Let E v = {x ∈ X : v(x) = 1}, and note that q(E v ) < 1 -. Then we haveq n (E ≥1 ) = 1 -q(E v ) n > 1 -(1 -) n ≥ 1 -e -n ,where the final inequality follows from the fact that (1 + x/n) n ≤ e x for x ≤ n.We can then borrow from classical analysis of hypothesis testing given by the Neyman-Pearson lemma to leverage this gap in total variation between product measures into a bound on the probability that after n samples, a model with appreciable invalidity has a smaller loss than P .Lemma 3. Fix 0 < < 1 and n ∈ N \ {0} arbitrarily. For any validity function v, if q ∈ P has I(q) > , P ∈ P has I(P ) = 0, and q and P have densities with respect to the reference measure λ, thenPr S∼P n q n (S) ≥ P n (S) ≤ e -n .Proof. The proof follows that of the Neyman-Pearson lemma's claim that the Likelihood Ratio Test achieves the lower bound on the sum of Type I and Type II errors [18] , combined with Lemma 2. We give the full argument for completeness.Fix the validity function arbitrarily, and note the following string of relations:Pr S∼P n q n (S) ≥ P n (S) = 1[f n q (x) ≥ f n P (x)]f n P (x)dλ n (x) ≤ min f n q (x), f n P (x) dλ n (x) = 1 -d T V (P n , q n ) ≤ e -n ,where the switch to total variation in the second to last line is the result of a classic characterization of total variation given by "Scheffé's Theorem", and the final line comes from Lemma 2.To generate loss guarantees, we need to be able to reason about models which do not have appreciable invalidity. The next lemma is an analogue of the previous one -it is identical up to the replacement of the condition that q have appreciable invalidity with a weaker one that the total variation between a model q and the data distribution P is appreciable. When q does not have appreciable invalidity, we can no longer rely on the structure of the supports of q and P to generate large margins for the total variation separation of product measures, and have to fall back on more general estimates for total variation between product measures.Lemma 4. Fix 0 < , δ < 1 arbitrarily, and let P, q ∈ P be distributions with densities with respect to λ. Then if d T V (q, P ) ≥ , and S ∼ P n for n ≥ Ω(log(1/δ)/ 2 ), it holds with probability ≥ 1 -δ that L S (P ) < L S (q).Proof. When q and P both possess densities, we can related the the probability that the likelihood of q is at least that of P to their total variation, as in the Neyman-Pearson Lemma.PrS∼P n P n (S) ≤ q n (S) = 1[f n P (x) ≤ f n q (x)]f n P (x)dλ n (x) ≤ min f n P (x), f n q (x) dλ n (x) = 1 -d T V (P n , q n ) ≤ e -nd T V (p,q) 2 /2 ≤ e -n 2 /2 .Here, the second to last inequality is the consequence of powerful result of [19] (and later [29] ), namely that for any two collections of probability measures {q i } n i=1 and {p i } n i=1 over measurable spaces {(X i , F i )} n i=1 , the product measures over the respective collections q n and p n satisfy1 -exp - 1 2 n i=1 d T V (q i , p i ) 2 ≤ d T V (q n , p n ).The final inequality follows from assumed gap in total variation between P and q.The previous two results concern the testing of individual models against P . In the standard way, we now leverage the finite cardinality to argue via a union bound that given enough samples from P , it's unlikely that the ERM model has a large total variation distance from P .Lemma 5. Fix 0 < δ, 1 , 2 < 1 arbitrarily, and suppose P ∈ Q. If P is fully-valid under v, andS ∼ P n for n ≥ Ω log(|Q|)+log(1/δ) min( 2 1 , 2), then with probability ≥ 1 -δ over S ∼ P n , the ERM solution q = arg minq∈Q xi∈S log(1/q(x i )),satisfies both d T V (q, P ) ≤ 1 and I(q) ≤ 2 .Proof.Let Q d T V > 1 = {q ∈ Q : d T V (q, P ) > 1 }. By Lemma 4 and a union bound, it holds thatPr S∼P n d T V (q, P ) > 1 ≤ Pr S∼P n ∃q ∈ Q d T V > 1 s.t. L S (q) ≤ L S (P ) ≤ |Q d T V > 1 | • max q∈Q d T V > 1Pr S∼P n L S (q) ≤ L S (P )≤ |Q|e -n 2 1 /2 .In the same manner, let v be an arbitrary validity function, and let Q I> 2 = {q ∈ Q : I(q) > 2 }.Then we havePr S∼P n I(q) > 2 ≤ Pr S∼P n ∃q ∈ Q I> 2 s.t. L S (q) ≤ L S (P ) ≤ |Q I> 2 | • max q∈Q I> 2Pr S∼P n L S (q) ≤ L S (P )≤ |Q| e -n 2 ,where the final inequality holds by Lemma 3. Then finally,Pr S∼P n d T V (q, P ) > 1 ∨ I(q) > 2 ≤ |Q|e -n 2 1 /2 + |Q|e -n 2 ,and so choosing n ≥ 2(log(|Q|) + log(1/δ))/ min( 2 1 , 2 ) ensures that the sum of these final terms is ≤ δ.Before we can prove Theorem 1, we need one final intermediate result, which we now give. It states that the value of the log-loss at any given x for a mixture distribution constructed by heavily weighting one of two distributions is not much different than the value of the loss for the heavily weighted component. This follows from the fact that the natural log is well-approximated by a linear function near 1. We will use this result to argue that the loss of the output of Algorithm 1 is not significantly different than that of the ERM in the support of the ERM. Lemma 4. Fix 0 < < 1. For any q ∈ P having a density with respect to λ, the mixture M = (1 -/2)q + u/2 has density f M (x) = (1 -/2)f q (x) + f u (x)/2 and this density satisfieslog 1/f M (x) ≤ + log 1/f q (x) , for all x ∈ X .Proof. The existence claim on the densities is immediate given the definition of u as the uniform distribution with respect to the reference measure λ. To see the inequality, fix x ∈ X arbitrarily, and note that f M (x) ≥ (1 -/2)f q (x). Thus, we may writelog 1/f M (x) ≤ log 1 1 -/2 + log 1/f q (x) ≤ 1 1 -/2 -1 + log 1/f q (x) ≤ /2 1 -/2 + log 1/f q (x) ≤ + log 1/f q (x) ,where second equality comes from the fact that log(z) ≤ z -1, the final follows from the fact that z/(1 -z) ≤ 2z for z ≤ 1/2.To get guarantees for the log-loss, we make heavy use of the previous lemma. Being able to guarantee a small total variational distance from the ERM to P and small invalidity means that the ERM output is already likely to be a faithful representation of P with small invalidity. All that is then needed is to eliminate the possibility that the ERM has a large log-loss because of small mismatches in support with P .To deal with this possibility, we mix the ERM model with the uniform distribution in accordance with Algorithm 1. Because the weight given to the uniform distribution is O(min( 2 1 , 2 )), the invalidity is close to that of the ERM. To show that such a move does not increase the loss significantly, we split the contribution to the loss of the outputted model into two that arising from supp(q ERM ) and it's complement. We first observe that the ERM always has an empirical risk which is a faithful estimator of the integral E X∼P [1[X ∈ supp(q ERM )] • log(1/f q ERM (x))], allowing us to bound this integral above in terms of the loss of P . The integral of the loss over supp(q ERM ) c can be shown to be small using the lower bound on the density of the output model q afforded by mixing with the uniform distribution, and the fact that supp(q ERM ) c must have a small measure under P when the ERM is close to P in total variation. Theorem 1. Fix 0 < δ, 1 , 2 < 1 arbitrarily, and suppose P ∈ Q and that P is fully-valid under v. If it holds that for each q ∈ Q that α ≤ f q (x) ≤ β for all x ∈ supp(q), then there is anN ≤ Õ log 2 (1/ min( 1 , 2 , α)) • log(|Q|) + log(1/δ) min( 2 1 , 2 ), such that for all n ≥ N , with probability ≥ 1 -δ, the output q of Algorithm 1 satisfies L P (q) ≤ L P (q * ) + 1 and I(q) ≤ 2 .Proof. Fix v arbitrarily, and let ∧ = min( 1 , 2 ). To see the claim on the validity, note that by guarantee of Lemma 5, the assymptotic complexity of Lemma 5 yields the guarantee I(q ERM ) ≤ 2 /2 with probability ≥ 1 -δ/3, in which casePr X∼q v(X) = 0 = Pr X∼q ERM v(X) = 0 • 1 - ∧ 8 + Pr X∼U v(X) = 0 • ∧ 8 ≤ 2 2 • 1 - ∧ 8 + 1 • ∧ 8 < 2 .The loss of the outputted model q can be decomposed into the contributions from the loss in supp(q ERM ) and it's complement:L P (q) = E X∼P 1[X ∈ supp(q ERM )] • log(1/f q (X)) + E X∼P 1[X ∈ supp(q ERM ) c ] • log(1/f q (X)) .To bound the first term, for each q ∈ Q, consider the functionB q (x) = log (1/f q (x)) if x ∈ supp(q), 0 else.These functions are bounded above by log(1/α) and below by log(1/β) (if β < 1, simply loosen the density upper bound), and thus for a sample X ∼ P , define bounded random variables B q (X). By Hoeffding's inequality and a union bound, it holds that a sample S of size n ≥ Ω(log 2 (1/α)(log(|Q|) + log(1/δ))/ 2 1 ) from P is large enough such that with probability ≥ 1 -δ/3, for each q ∈ Q, it holds thatE X∼P [B q (X)] - 1 n xi∈S B q (x i ) ≤ 1 8.Note that for each q ∈ Q with L S (q) < ∞, it holds that L S (q) coincides with the empirical estimates ofE X∼P [B q (X)], namely 1 n xi∈S B q (x i ) = 1 n xi∈S log (1/f q (x i )) .Furthermore, this coincidence takes place for q ERM with probability 1, as P ∈ Q implies that L S (q ERM ) ≤ L S (P ) < ∞ with probability 1 -note that L S (P ) is a good estimator for L P (P ) in the sense arising from an application of Hoeffding, as log(1/f P (X)) is bounded almost surely for X ∼ P given that P has a density that is bounded in it's support (as a member of Q). Thus, we may writeEQUATION≤ L P (q * ) + 1 2 ,where we invoke Lemma 4 in the first step, and in the last step use that q * = P by the strict properness of the log-loss.To bound the second term, note that by the argument in given in Lemma 5, when n ≥ Ω log2 (1/ ∧ ) • (log(|Q| + log(1/δ)) / 2 1 , it holds with probability ≥ 1 -δ/3 that d T V (q ERM , P ) ≤ 1 /8 log(8/ ∧ ). Because q has density at least ∧ /8 everywhere in X , 2 we haveE X∼P 1[X ∈ supp(q ERM ) c ] • log(1/f q (X)) ≤ log(8/ ∧ ) • E X∼P 1[X ∈ supp(q ERM ) c ] ≤ log(8/ ∧ ) • d T V (P, q ERM ) < 1 /2,where in the second line we use the fact that q ERM (supp(q ERM )) = 1 to argue that d T V (P, q ERM ) ≥ P (supp(q ERM ) c ). Combining the bounds on the two summands and union bounding the confidence yields the full guarantee.We note that this argument implies a slight more precise sample complexity bound given byEQUATION, which affords a minor improvement in certain regimes where 2 < 2 1 .Theorem 2. For all 2 < 1/4 and for all proper learners L : S → P, if the sample S ∼ P n is of size n ≤ 1/8 2 , then there exists a triple (P, Q, v) with P ∈ Q and P fully-valid, on which L(S) has invalidity I(L(S)) > 2 with probability ≥ 1/4.Proof. We give an argument inspired by the proof of a lower bound in Theorem 2 of [30] .Let X = [0, 1] ⊂ R. Fix the proper learner L and 2 < 1/4 arbitrarily. Consider a model class defined by Q = {P, P }, where P and P have densities with respect to the Lebesgue measuref P (x) = 1[x ∈ [0, 1 -2 2 ]] 1 1 -2 2 , f P (x) = 1[x ∈ [2 2 , 1]] 1 1 -2 2 .This Q gives rise to two realizable problem instances of interest. Under the first, P is the data generating distribution and v(x) = 1 everywhere except for in (1 -2 2 , 1], where v(x) = 0. Under the second, P is the data generating distribution and v(x) = 1 everywhere except for in [0, 2 2 ), where v(x) = 0. Assume by contradiction that for both problem instances, given a sample of size n ≤ 1/8 2 , we have that I(L(S)) ≤ 2 with probability > 3/4. In both cases, we have that I(q) = 2 2 /(1 -2 2 ) > 2 for the model q which is not the data generating distribution. Thus, L(S) is a model with I(L(S)) ≤ 2 with probability > 3/4 over both problem instances if and only if it identifies the data generating distribution with probability > 3/4 over both problem instances.Consider the simple hypothesis tester defined by T L (S) = L(S), which by the above, outputs the correct data generating distribution given a choice of P or P -and given n ≤ 1/8 2 samples from either P or P -with probability > 3/4. Note that the distributions P , P have d T V (P, P ) = 2 2 /(1 -2 2 ) ≤ 4 2 , where we use 2 < 1/4 and z/(1 -z) ≤ 2z for small enough z in the inequality. By a classic upper bound on the total variation between product measures [19] , we have that d T V (P n , P n ) ≤ 4n 2 . Then, by Le Cam's method and this upper bound on d T V (P n , P n ), we have infT :S→{P, P } max q∈{P, P } Pr S∼q n (T L (S) = q) ≥ 1 2 - 1 2 • d T V (P n , P n ) ≥ 1 2 -2n 2 .Thus, if n ≤ 1/8 2 , the there is a choice of data generating distribution such that T L (S) incurs error probability ≥ 1/4, which is a contradiction.When the validity function v is known to lie in a class of bounded complexity, it is learnable, and learned estimates may be utilized in the selection of a low-loss, high-validity model. An interesting feature of the problem setup here is that unlike in most learning settings, the learner can actually choose which distributions it would like estimate v with respect to, i.e. decide under which marginal distributions over X the estimate v should small disagreement with v.We begin with a lemma arguing that whenever the ERM has positive probability of outputting an example with v(x) = 1, and the disagreement of v and v under a proposal distribution is small enough, the restriction will indeed yield a low-validity model.Lemma 5. Fix 0 < < 1 and a distribution q ∈ P absolutely continuous with respect to λ arbitrarily. Further, fix V (q) such that 0 < V (q) ≤ V (q), and suppose that for some v : X → {0, 1} we havePr X∼q (v(X) = v(X)) ≤ V (q) 2 .Then whenever there is a distribution q corresponding tof q (x) ∝ f q (x)1[v(x) = 1],it has invalidity I(q) ≤ .Proof. Let V v (q) = Pr X∼q (v(X) = 1) denote the normalizing constant for the restriction to estimated valid region. Note that the restriction corresponds to a probability distribution if and only if V v (q) > 0, and that in this casef q (x) = f q (x)1[v(x) = 1] V v (q) .It holds further that q is absolutely continuous with respect to λ, and that we can write the following chain of relations:I(q) = 1[v(x) = 0]f q (x) dλ(x) ≤ 1 V v (q) 1[v(x) = v(x)]f q (x) dλ(x) ≤ V (q) V v (q) 2 ≤ V (q) V v (q) 2 ,where the first inequality follows after inputting the definition of f q , and the final two inequalities come by assumption. It's further possible to show that validity of q can be approximated from above by a constant multiple of V v (q), which can be conceptualized as the validity of q if v were the true validity function. In particular,V (q) = V v (q) -V v (q) + V (q) = V v (q) + 1[v(x) = 1] -1[v(x) = 1] f q (x) dλ(x) ≤ V v (q) + 1[v(x) = v(x)]f q (x) dλ(x) ≤ V v (q) + V (q) 2 ≤ V v (q) + V (q) 2 .This implies that V (q) ≤ V v (q)/(1 -/2), which yields V (q) ≤ 2V v (q) as < 1. Utilizing this inequality in the last line of the first string of inequalities gives the guarantee.The need for a lower estimate on the validity in the precision of the estimate for v can be understood as follows: when the proposal distribution has very small validity, the restriction to the estimation of the valid parts of space under v may create huge (or infinite) increases in mass over the proposal distribution -in the language of Lemma 5, V v (q) may be very small for a proposal distribution q. If this is the case, the estimate v must be more precise, as small errors in the estimation of the validity function may lead to invalid parts of space having large mass under q.We introduce another lemma before proving Theorem 3. It argues that for a model q constructed by accepting samples from some "proposal distribution" q that fall in the valid part of space under v, the contribution to the loss from the part of space where v agrees with v can never exceed the total loss of the proposal distribution q. Essentially, we are exploiting the full-validity of P here -in the subregion of the agreement region {v(x) = v(x)} on which the loss is computed, we have that v(x) = 1 by the fact that X ∼ P is valid. This means that the density of q can only be larger than the density of q in this region, which under a non-increasing loss cannot increase the loss over that incurred by q.Lemma 6. Fix 0 < , δ < 1, a validity function estimate v : X → {0, 1}, and q ∈ Q arbitrarily. Suppose l : R ≥0 → [0, M ] is a non-increasing loss function. Then wheneverf q (x) ∝ f q (x)1[v(x) = 1]corresponds to a probability distribution, it enjoysE X∼P l (f q (X)) • 1[v(X) = v(X)] ≤ L P (q; l).Proof. Let V v (q) = Pr X∼q (v(x) = 1) be the normalizing constant for q, where we note that V v (q) > 0 when f q (x)1[v(x) = 1] corresponds to a probability distribution.Given that P is fully-valid, we have Pr X∼P (v(X) = 1) = 1. By the fact that integration is defined up to null sets, it holds thatE X∼P l (f q (X)) • 1[v(X) = v(X)] = E X∼P l (f q (X)) • 1[v(X) = v(X) ∧ v(X) = 1] .Further, we may writeE X∼P l (f q (X)) • 1[v(X) = v(X) ∧ v(X) = 1] ≤ E X∼P l f q (X)1[v(X) = 1] V v (q) • 1[v(X) = 1] ≤ E X∼P l f q (X) V v (q) ≤ E X∼P l (f q (X)) = L P (q; l).Here, the second to last inequality comes from the non-negativity of the loss along with the fact that whenever v(X) = 0, the integrand is zero -when v(X) = 1, the loss is just evaluated at the normalized density, and so the integrand introduced in this line is an upper bound for the previous integrand. The final inequality comes from the non-increasingness of the loss function along with the observation that V v (q) ≤ 1 -in removing the normalizing constant, we can only make the value at which the loss is evaluated at smaller, which cannot decrease the value of the loss.We are now ready to prove the main result of the second half of the paper -the guarantee for Algorithm 2. It combines the previous lemmas, noting further that the number of samples in S P is sufficient to make the disagreement of v and v small enough under P such that the contribution to the loss in that part of space can be controlled by trivially applying the loss upper bound M .Theorem 3. Suppose v ∈ V with VC-dimension V C(V) ≤ D, and that for each q ∈ Q, the validity V (q) ≥ γ > 0. For all 0 < 1 , 2 , δ ≤ 1 and for all choices of non-increasing loss functions l : R ≥0 → [0, M ], Algorithm 2 requires a number of samples≤ O M 2 (log(|Q|) + log(1/δ)) 2 1 + M (D log(M/ 1 ) + log(1/δ)) 1 ,and a number of validity queries≤ O D log(1/γ 2 ) + log(1/δ) γ 2 ,to ensure that with probability ≥ 1 -δ, its output enjoys L P (q; l) ≤ L P (q * ; l) + 1 and I(q) ≤ 2 .Proof. Given that the loss is bounded, Hoeffding's inequality applied to the random variables l (f q (X)) for X ∼ P , and a union bound, imply that S is large enough that with probability ≥ 1 -δ/3, we have that for all q ∈ Q, the empirical loss estimates L S (q; l) are at most 1 /4 away from true losses L P (q; l). For any choice of q ERM , because we have v ∈ V, it must hold that any minimizer v is consistent with the labeling under v of both S P and S q ERM . The standard rates of convergence when choosing an arbitrary consistent hypothesis thus imply that the sizes of S P and S q ERM are large enough to guarantee that, with probability ≥ 1 -2δ/3, we havePr X∼P v(X) = v(X) ≤ 1 2M ∧ Pr X∼q ERM v(X) = v(X) ≤ γ 2 2 .By a union bound, with probability ≥ 1 -δ, all of these estimation accuracy events take place. We condition on these favorable events taking place going forwards.Note that conditioned on these favorable events, the normalizing constant q ERM ({v(x) = 1}) > 0, as for any ERM, we haveq ERM ({v(x) = 1}) = E X∼q ERM [1[v(x) = 1]] -(1[v(x) = 1] -1[v(x) = 1]) dq ERM (x) ≥ E X∼q ERM [1[v(x) = 1]] -1[v(x) = v(x)]dq ERM (x) ≥ γ - γ 2 2 > 0.Thus, the restriction of the ERM to the estimated validity region is a viable probability distribution, and is outputted by the algorithm as q. For any estimate of the validity function v, we can decompose the loss of q asL P (q; l) = E X∼P l (f q (X)) • 1[v(X) = v(X)] + E X∼P l (f q (X)) • 1[v(X) = v(X)] .First using Lemma 6, and then using the uniform convergence of the loss estimates, we can bound the first term asE X∼P l (f q (X)) • 1[v(X) = v(X)] ≤ L P (q ERM ; l) ≤ L P (q * l ; l) + 1 2 ≤ L P (q * ; l) + 1 2 ,where q * l = arg min q∈Q L P (q; l) is the lowest-loss model in the class Q. To upper bound the second term in the loss decomposition, we can use the fact that Pr X∼P (v(X) = v(X)) ≤ 1 /2M and the upper bound on the loss to write E X∼P l (f q (X)) • 1[v(X) = v(X)] ≤ M • E X∼P 1[v(X) = v(X)] ≤ 1S ← Ω M 2 (log(|Q|)+log(1/δ))2 1 i.i.d samples ∼ P 3:q ERM ← arg min q∈Q x∈S min(M, -log(f q (x)))4:q ERM ← (1 -1 /8) • q ERM + 1 /8 • DMix with constant validity D 5:S P ← Ω M (D log(M/ 1 )+log(1/δ)) 1 i.i.d. samples ∼ P , S q ERM ← Ω D log(1/ 1 2)+log(1/δ) 1 2 i.i.d. samples ∼ q ERM 6: v ← arg min h∈V x∈S P ∪Sq ERM 1[h(x) = v(x)] Label x ∈ S q ERM via v 7: return f q ∝ f q ERM (x) • 1[v(x) = 1] if q ERM ({v(x) = 1}) > 0 else f q = f q ERM 8: end procedureyielding the loss guarantee.The validity guarantee follows directly from the fact that Pr X∼q ERM (v(X) = v(X)) ≤ γ 2 /2 and Lemma 5, where γ furnishes the lower estimate for the validity of the model q ERM .The corollary to Theorem 3 stating that only low-loss models need appreciable validity is straightforwards. One can simply add an extra line to the proof of Theorem 3, arguing that when the intersection of good estimation events takes place, the loss of the ERM distribution is within O( 1 ) of the optimal loss across models in Q, meaning that it has validity greater than some constant c. Thus, one can run Algorithm 2 with an S q ERM large enough to achieve O( 2) disagreement rate between v and v under samples from q ERM , lowering the label complexity.The proof of Theorem 4 is very similar to that of Theorem 3. The main difference is that when the loss is the capped log-loss, we can exploit a stability property under mixture similar to that introduced in Lemma 4. This allows us to mix q ERM with a distribution of constant validity to get a validity lower bound on the final proposal distribution q ERM without increasing the loss more than O( 1 ).The validity lower bound can then be used as in Theorem 3. Theorem 4. Suppose v ∈ V where V C(V) ≤ D, and that for each q ∈ Q, we have f q (x) ≤ β.Suppose further that there is some known D ∈ P with density f D which has V (D) ≥ c > 0 for some constant c. Then for all choices of 0 < 1 , 2 , δ < 1/2 and M > 0, Algorithm 3 requires a number of samples≤ Õ M 2 (log(|Q|) + log(1/δ)) 2 1 + M (D log(M/ 1 ) + log(1/δ)) 1 ,and a number of validity queriesEQUATION, to ensure that with probability ≥ 1 -δ, its output enjoys E X∼P min (M, log(1/f q (X))) ≤ E X∼P min (M, log(1/f q * (X))) + 1 and I(q) ≤ 2 .Proof. WLOG assume β ≥ 1, and consider learning over l(z) = min(M, log(1/z)) -log(1/β), a translation of the capped log-loss bounded below by 0 for all inputs to f q ∈ Q, and bounded above by M = M -log(1/β).Similar to the proof of Theorem 3, with probability ≥ 1 -δ/2 over the sample S ∼ P n , it holds that for all q ∈ Q that L S (q; l) -L P (q; l) ≤ 1 /8; in this case, we use the fact that f q ≤ β to ensure that the random variables l (f q (X)) for X ∼ P are bounded, allowing for an application of Hoeffding's inequality over empirical estimates of a loss unbounded below. As above, for any choice of q ERM , the sizes of S P and S q ERM are such that with probability ≥ 1 -2δ/3,Pr X∼P v(X) = v(X) ≤ 1 2M ∧ Pr X∼q ERM v(X) = v(X) ≤ c 1 2 16 .As before, by a union bound, these bounds both hold simultaneously with probability ≥ 1 -δ. We condition on this intersection of favorable events going forwards.Note that when this intersection of events takes place, we have q ERM ({v(x) = 1}) > 0. In this case, we have that V (q ERM ) ≥ 1 V (D)/8 ≥ 1 c/8 as V (D) ≥ c, and so identically to our work in Theorem 3, we may writeq ERM ({v(x) = 1}) ≥ E X∼q ERM [1[v(X) = 1]] -1[v(x) = v(x)]dq ERM (x) ≥ c 1 8 - c 1 2 16 > 0.Thus, the restriction of q ERM to the estimate of the valid region is defined and outputted by the algorithm as q. To see that the loss guarantee then holds for such a q, consider the loss decomposition used in the proof of Theorem 3:L P (q; l) = E X∼P l (f q (X)) 1[v(X) = v(X)] + E X∼P l (f q (X)) 1[v(X) = v(X)] .We upper bound the second term exactly as in Theorem 3. To upper bound the first term, consider an argument similar to that of the proof of Lemma 6. Let V v (q ERM ) > 0 be the normalizing constant for q. We can writeE X∼P l (f q (X)) 1[v(X) = v(X)] ≤ E X∼P l f q ERM (X)1[v(X) = 1] V v (q ERM ) • 1[v(X) = 1] ≤ E X∼P l f q ERM (X) V v (q ERM ) ≤ E X∼P l (f q ERM (X)) .Here, the non-increasingness of the loss still holds, leading to the final step. Now, fix some x ∈ X arbitrarily, and note the following, in the style of Lemma 4:l(f q ERM (x)) + log(1/β) = log 1/f q ERM (x) ∧ M ≤ log 1 1 -1 /8 + log 1/f q ERM (x) ∧ M ≤ 1 /4 + log 1/f q ERM (x) ∧ M ≤ log 1/f q ERM (x) ∧ M + 1 4 .Thus, it holds that l(f q ERM (x)) ≤ l(f q ERM (x)) + 1 /4, and so we may writeE X∼P l(f q (X)) ≤ E X∼P l (f q ERM (X)) + 1 4 = L P (q ERM ; l) + 1 4 .Thus, we have written the loss in terms of the ERM, and so we have, as in Theorem 3, that the first term of the loss decomposition can be bounded by L P (q * ) + 1 /2.Given Pr X∼q ERM (v(X) = v(X)) ≤ c 1 2 /16, and the lower bound on the validity of q ERM derived in the third paragraph above, we can again apply Lemma 5 to get the validity guarantee.NeurIPS Paper Checklist 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: [NA] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: [NA] Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification:[NA] Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: 38th Conference on Neural Information Processing Systems (NeurIPS 2024).2 loss sub-optimality, suggesting that ensuring validity via the selection of a good model under the log-loss is even harder than guaranteeing a small loss.This does not yield uniform convergence over Q given that the support of q ∈ Q need not align with PWhen the uniform distribution has a density smaller than 1, there is an extra log factor to account for here. We can WLOG this away by adding the condition that λ(X ) = 1, e.g. arising from normalized data. 


Decision: This work studies the problem of approximating a target distribution under the constraint that the estimated distribution should not assign too high weight on invalid regions. Though prior work gave worst-case analysis that implies exponential sample complexity, this paper considers a few special models under which polynomial sample complexity can be obtained.

Though there is certain concern on the practical implication, the theoretical results were found interesting and sound, and the special cases  appear reasonable path to attack the problem.

Reviews: review: paper_summary: paper_summary: This paper studies distribution learning with invalidity constraints. It assumes that the algorithm has access to an oracle that provides validity queries, and targets to reduce the total amount of queries to the oracle while achieving comparable learning guarantees to previous counterparts. By specifying the loss function and restricting the hypothesis class, the paper achieved improved sample/query complexity of $\tilde{O}(\log{\lvert Q\rvert}/\min(\epsilon_1^2,\epsilon_2))$ (from previous $\tilde{O}(\log\lvert Q\rvert/\epsilon_1^2\epsilon_2)$ of Hanneke et al. 2018). Additionally, by assuming that the validity function is from a VC-class with VC-dim $D$, then the query complexity can be further reduced to $\tilde{O}(D/\min{\epsilon_1,\epsilon_2})$.
strength_weakness: strength_weakness: There are some typos. Line 136: choice of. Line 237: "is true for .. for .." To name a few.

Some parts are a bit unclear, for example, Line 37: "while achieving polynomial bounds on the number of validity queries, uses relative large number of validity queries". It is unclear what the "relative large number" is comparing to.

Line 232-233: "attainable, at least improperly". Does this mean that the algorithm can output an improper hypothesis? Is this due to the mixture of the ERM with the uniform distribution? Then, is proper learning achievable?

In addition, the format for the references is not unified. Some references are missing the information for venues.
questions: questions: Do all algorithms run in exponential time, i.e. computationally inefficient?
limitations: limitations: I have no concerns on the potential negative societal impact.
paper_summary: paper_summary: The paper considers the problem of learning generative models under validity constraints. Specifically, given data from a distribution and an oracle that tells whether a particular datapoint is valid, the goal is to output a generative model from a hypothesis class Q whose output has a small loss epsilon_1 (compared to the best model in Q) while ensuring the output is valid with high probability (1 - epsilon_2).  The objective is to achieve this with minimal training samples and validity queries to the oracle.

Previous work on this problem showed a negative result:  exp(1/epsilon_1) validity queries are needed to properly learn the generative model. For improper learning, they show that O(log(Q)/(epsilon_1^2 epsilon_2)) validity queries suffice. This work aims to improve these results by making further assumptions.

For example, it is shown that if the true data-generating distribution P is assumed part of class Q, then a minor modification of empirical risk minimization can achieve the loss and validity requirements with O(log(Q)/min(epsilon_1^2, epsilon_2))  samples and no validity queries. Additional results are provided, assuming a bound on the VC dimension of the class to which the validity oracle belongs.
strength_weakness: strength_weakness: While the problem of generative modeling under validity constraints has been introduced citing practical concerns, it is unclear if the results or algorithms in this paper add much to generative modeling in practice. Therefore, the significance and relevance of these results are unclear.
questions: questions: Could the authors elaborate on any practical insights that can be derived from the algorithms and bounds presented in this work?
limitations: limitations: See the weaknesses section. It would be great to include a discussion of insights for practice.
paper_summary: paper_summary: The paper proposes a method for vastly improved validation query efficiency in validity-constrained distribution learning by relaxing the requirement for worst case settings of distributions, loss function and true validity function.
strength_weakness: strength_weakness: A more in depth discussion of situations where one could clearly afford the proposed relaxation versus those where it might not be prudent enough would be helpful for justifying it.
questions: questions: -
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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$
limitations: limitations: The authors have adequately addressed limitations as far as I can see.

Comments: title: Official Comment by Reviewer yKWM
Response to rebuttal
comment: Thank you for your response. It will be helpful to include the discussion in the revision.
Thanks for the response!

The point I mentioned in the review is that in different practical situations, the assumption might or might not be valid. Even if it is valid in most situation, some guidelines or measurable prerequisites that make the assumption more likely to safely hold would be helpful. This is however a minor point for the overall paper, and I'm maintaining my score.
I appreciate the authors' response. While I agree that this work adds nuance to the prior work by Hanneke et al., the high-level takeaways and the algorithms do not seem to contribute significantly beyond what is already established in the practice of generative modeling. Therefore, I will maintain my original score.
Thank you for the response. Please do revise the submission to reflect the discussion above. I maintain my score of 8, and believe this work should be accepted. Great job!