Distribution Learning with Valid Outputs Beyond the Worst-Case
Authors: Nicholas Rittler
Kamalika Chaudhuri
Venue: NeurIPS 2024 poster (2024)
Keywords: distribution learning
trustworthy machine learning
learning theory
Primary area: learning_theory

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.

Distribution Learning with Valid Outputs Beyond the Worst-Case
Nick Rittler
Kamalika Chaudhuri University of California San Diego kamalikee aaanck ucsd. edu
University of California San Diego nrittlerQucsd. edu
Abstract
Generative models at times produce "invalid" outputs, such images with gen- eration 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 stan- dard 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 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 an atypical polynomial number of validity queries. In this work, 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 of samples required to ensure validity has a weak dependence on the validity require- ment. Additionally, we show that when the validity region belongs to VC-class, a limited number of validity queries are often sufficient.
take first step towards characterizing regimes where
1 Introduction
When sampling from 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, avoid the use of biased offensive language 212 When generating code, criterion may be that the generated code successfully compiles 3. image generation, we might wish to avoid blurry outputs, or those possessing generation artifacts which clearly distinguish them from natural images 5.
In this paper, we examine the statistical cost of ensuring that learned distributions produce such "validd" 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 a probability distribution P. and the binary "validity" of examples determined by some unknown "validity function" v. Given sample access to P and query access v. learner attempts identify probability distribution which outputs invalid examples with probability at most <2. At the same time, the distribution should than that of the minimum loss model in class which outputs
have loss which is most é valid examples with probability 1. Here, query access to e captures the idea that collecting samples is often cheap, but verifying validity is often less so, possibly requiring human-in-the- in-the-looo..
The initial work of 3 suggests that choosing such a low-loss, vigh-validity distribution q may require large number of validity queries. Under the assumption that P is "fully-valid", i.e. outputs valid example with probability 1, they show that in the worst case, 20(1/e)) validity queries are required to choose such model I from the class Q. They follow this result with an improper learning algorithm
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

for choosing 9 which, while achieving polynomial bounds on the number of validity queries, uses relatively large number of validity queries Ô
The somewhat pessimistic picture painted by these fascinating tthpleeity--hhoretii results can be tracked to their generality. Firstly, it's possible that Q and P are significantly "mismatched", f.e. the support of each model q E 2 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 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 2, 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 fully- valid data distribution P, and the loss is the log-loss (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( 21) min(e?, (f),)) <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 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 E Q have at least constant validity, this scheme uses Ô (D/e2) validity queries, implying a query cost reduction over the general- caneral-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.
2 Related Work
The framing of learning distributiuons in terms of PAC guarantees similar to (6] dates back to 77. 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 [ 9 10 (T). The only theoretical contribution to validity-constrainct distribution learning under the formulation posed by 3 that we are aware of is that work itself.
The study of loss funetions for the evaluation of probabilistic models has often been studied the lens of "scoring rules" in the forecasting literature [12] [3] 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 major focus of the classical statistics literature [6]. The bounds in the first half of the paper are due to analysis inspired by the Neyman- Deyraan-n lemma [8). and rely on the approximation of total variational distance between product measures 19.
The applied literature generative modeling has consistently noted the problem of learned models producing "invalid" examples 200 21 22 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 VC-class, the strategy we introduce has some rough semblance to a "post-editing" procedure proposed by (24).

---

3 Preliminaries
3.1 Problem Setup
Let X' be a subset of Euclidean space R with finite Lebesgue measure X. Let P denote the set of all probability distributions on the measurable space Fx). where Fx arises from Lebesgue measurable sets intersected with X. Let P E P be the data-generating distribution.
In the eyes of the learner, the function v. X' + {0, 1 is fixed and unknown "validity function", measurable with respect to the relevant distributions. The validity function denotes whether or not an example E X' is considered valid output for learned approximation of P. The learner is given a model class Q C P of probability distributions on X, each with density fy with respect to A. and afforded with the knowledge that at least one E Q is "fully-valid", i.e. that there is some E Q with invalidity (g) := Prx~ (x(X) = 1) = 1. We at times use the notion of "invalidity" of model, by which mean (q)) of finite cardinality.
(g). Following the main exposition of [ we assume Q is
The goodness-of-fit of a model E P is governed by a decreasing "local" loss function 1: R220 - U {oo). Such loss function gives rise to loss of model via Lp(g; 1) Ex-r [1 (X))) Given an i.i.d sample S from P. we let the empirical estimate of the loss of a model be Ls(g;) = S).
Ex (z) We use the shorthand Lp(g) and Ls(4) to denote the true and empirical losses of q under the log-loss I(4) = (z))), where log denotes the natural logarithm. We take the log-loss to be infinite at points where fa(r) O.
3.2 Goal of Learning
The goal of the learner is choose some P which has loss Lp I) similar that of the lowest-loss fully-valid model in Q, while simultaneously maintaining near full-validity. Explicitly, consider the model
arg min Lp(g!). q vEQ:V(g)=1
To describe the quality an outputted model, we consider two learning parameters 61 and 62, where E is used to control the loss sub-optimality. and 62 to control the invalidity. Formally then, the goal of the learner is to output q E P satisfying L(ğ) I L(q") + E1 and [[q) S 62. To accomplish this goal, the learner has sample access to P. and query access to v. L.c. 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( Ql). 1/e, and 1/e2. 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 [255, where samples from the marginal over instances are often cheap, but labeling such examples is assumed expensive.
3.3 Full-Validity of P
We assume that all samples from the data-gent eetta-gnerratng 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 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 algorithm, the question of minimizing the overall number of queries is dependent on the sample complexity of learning - if 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 algorithm is 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 given scheme. In most cases, algorithm sample requirements similar to (log( (log()@))/e)) which allows for accurate loss estimation many settings.
3

---

3.4 Summary of Previous Results
The learning problem above is due to B 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 low-loss, high-validity model. They begin by giving a negative result, namely that any proper learning algorithm outputting & E Q, must make 20(1/n)) validity queries in the worst case, regardless of the number of samples available from P. This result arises from specific problem instance wherein every q E Q has significant amount of mass outside of the support of P. in which case samples from a fully-valid P do not give information about in parts of space relevant to the choice of E Q.
On the other hand, they demonstrate an improper learning algorithm which achieves polynomial bounds 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 E Q which is the empirical loss minimizer putting no mass on points known to be invalid. In particular, their scheme uses ((log()Q))/e) samples and ((log())))/Efe) validity queries.
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 partieular, we consider the problem under a realizability assumption, namely that P E O 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-theorree 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-propes local loss, i.e. the only local loss under which for all distributions q * P, it holds that (P:)) < Lp(g: 1). This highly desirable property implying that convergence the optimum over coincides with convergence P makes the choice of an alternative outside of capped variants preferable only under specialized cireumstances.
4.1 Towards Validity without Validity Queries
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 E Q which is sufficiently good representation 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 with invalidity T(g) > necessary has drv P}> 62. In this case, must have at least 62 mass in the invalid part of space, where P has none. Thus, one can guarantee that has drv (q. P) S 62, the validity requirement is met. Recalling the Pinsker inequality drv (4,44) s 1loddlllg obtaining model which is at most ej sub-optimal in log-loss yields model meeting the validity requirement.
relating total variational distance and KL-divergence, it follows that
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 Ex (log (X)) is unbounded above, but with high probability, the empirical estimate Ls(g) = Exes log(1/f,(()) (+))/ 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 & loss sub-optimality, suggesting that ensuring validity via the selection of a good model under the log-loss is even harder than guaranteeing small loss.

---

Algorithm Modifying ERM to Yield Log-Loss Guarantees
Losssssisssisssiiittotoooo Class Q, S. min(e1, 2: (ERM < arg min Ea,es log ( (1/)g(rr))
procedure
3: return / = ex/8) (ERM + ex/8 88/1
D Mix ERM, uniform distribution
4: end procedure
We would hope that in the case that zero-query learning is possible, that guaranteeing validity arises somewhat coincidently with convergence 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 E2.
4.2 Analysis of Empirical Risk Minimization
As indicated above, is not possible to guarantee that empirical risk minimization (ERM) outputs a model with small log-loss. however possible to guarantee that it outputs model which closely resembles P and inherits validity guarantees with a small number of samples.
In particular, it's possible show that given sufficient samples, ERM yields model with small total variation to P when P E Q. This is due to the following folklore theorem 8 which we prove under assumption of density existence in the Appendix.
8 < 1 arbitrarily, and let P.g E P be distributions with densities with respect to A. Then if drv (g. P) 2 e, and S ~ Pm for n 2 (1log(110)) ())) holds with probability 2 - that
Lemma 4. Fix
Ls(P) < Ls(g).
Thus, at the statistical cost of estimating coin bias, any distribution g with total variation 2 from the data distribution will reveal itself to empirically inferior when the log-loss used. This can be casily leveraged to generate guarantees for ERM over Q in terms of total variation.
is tempting to think that this is the entire story when it comes guarantceing validity. After all, we argued above that small total variation from P is sufficient for 62 invalidity. That said, simply looking at total variation ignores particular structural feature of distributions q with [(q) > c2 in particular, such distributions have mass in parts of space in which P does not.
This observation be used to construct tight lower bounds on the total variational distance between product measures arising from P and with (()) > <2. This leads to the following result, which states that ERM yields faithful representation of the data generating distribution that most e2 invalid given number of samples with modest dependence on the validity parameter E2.
Lemma 5. Fix 0 < 8,61,62 < arbitrarily, and suppose P E Q. If P is fully-valid under v, and Pa for n 2 2 ( [ogg(())++og(()) then with probability 2 over S ~ P the ERM min(e),e2)
solution
i arg min
Σ log(1/g(x:)),
q
3,ES
satisfies both
drv (q. P) S and 1(4) S Ez.
Note that this guarantee is redundant having drv P) < ı does not imply I(g) 62 when
62 < é1.
4.3 Attaining Log-Loss Guarantees
This result can be interpreted as vote of confidence for the naive training of generative models under the log-loss. Nevertheless, from learning-theoresn perspective, there a question whether or not is possible to guarantee low log-loss while maintaining validity with zero validity queries.
5

---

While ERM cannot possibly furnish log-loss guarantees, it turns out that it is possible to modify the oulput of ERM to generate log-loss guarantees the cost of an extra polylogarithmic factor in the sample complexity, at least when the densities fa are bounded above and below in their support |
The idea, formalized in Algorithm[] is simply mix the output of ERM with the uniform distribution. Giving the uniform distribution a mixture component on the order of min(e1, eq) 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.
1 arbitrarily, and suppose P E Q and that P is fully-valid under If it holds that for each E 2 that S fg(x) S 3 foror all x E supp(g), then there is an
Theorem 1. Fix e 62 61
N δ log (1/ min((e,, (Iog(12) + log(1/6)) min(t,,
such that for all 2 N, with probability 2 21-6. 8. the output of Algorithu Datissice
Lr(g) S Lr(g") t1 and [()) S 62.
Here the Ô notation hides a polylogarithmic dependence on 1/3. which is insignificant in most regimes, and treats the density of the uniform distribution over X' as a constant, which would otherwise also enter polylogarihhiccaly.
Theorem shows that guarantees with respect to the unbounded log-loss are attainable improperly, i.e. when the learner can choose q & Q. It's interesting question whether the logarithmic dependence on min(é1, E2) can be removed with more subtle strategy.
4.4 Discussion of Optimality
One might suspect that achieving smaller dependence than 1/e2 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 is tight in its dependence c2. This lemma is used to generate the validity guarantee in Theorem
Theorem 2. For all c 1/4 and for all proper learners L S P, if the sample S ~ PD is of size n < 1/8cg. then there exists a triple (P. Q, v) with E Q and P vally-valid, on which L(S) has invalidity I(L(S)) 62 with probability > 1/4.
The intuition here is that while any invalid q E Q has at least e2 total variation from P. in the worst case, the total variation between and P is upper bounded by (Ee)) as well. This makes distinguishing between and some 62 invalid distribution hard enough generate such lower bound.
The sample requirement of 1/c,, both in our guarantees and in previous work, is standard offshoot of loss estimation, irrespective of the search of a valid model. In general, one cannot expect improvements this end ehis is the standard dependence random variables. This suggests that the "realizable complexity" for this setting is 1/ min(e? (2) while non-zero losses should not be generally estimable using "realizable" techniques, guarantceing small invalidity can when P E Q.
finds for estimating the means bounded
5 Utilizing Estimates of the Validity Function in Training
In the general formulation of the problem, the learner is given an arbitrary bounded, decreasing loss, model class Q which is mismatched with P, and has 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 setting where it is known to the learner that can be found in hypothesis class V bounded complexity. Under such an assumption, we would hope to be able to lower the number of validity queries beyond the bounds of (3].

---

Algorithm 2 Post-Hoc Restriction of ERM to an Estimate of Valid Outputs 1: procedure VALID_ D.w.DD_EESST..cr.oooDDStrhrtbu Class 2, Validity Class V. c1 c 0,
Af ( 2: S S Ω
ii.d. samples P
of
3: @FRM arg min Exes (g(x))
4: Sp + Q MiD MMD (+ogg(188)
ii.d. samples ~ P.
D (log(1/hes)+oog(/) i.i.d. samples FRM
Squar + Ω
5: +- arg minkev EXESPUSPERA ERM
1[h(x) + v(x)]
>> Label Sques via queries to o
6: return Sa Squusl (1) ((((z)
if @RM ((((x)) = 13) > else Sa -quuu
7: end procedure
5.1 Algorithm
A 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 0. This is the precisely the idea formalized in Algorithm 2
To generate guarantees for such strategy, the estimate should be accurate. In our case, we generate accuracy guarantees over both P and the ERM model Ū FRM by selecting an estimate that has O empirical source of the query complexity of the algorithm comes from the fact that samples arising from ςERM must be labeled by oracle calls v. Noting that samples from P 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.
must determine the distribution with respect to which
both distributions. The
Accuracy under samples from P allows one control the loss of g by invoking the boundedness of the loss in the disagreement region of i and and guarantees with respect to q ERM allow us to bound the invalidity of the restriction. Because region of and ό correspond to parts of space where ú(x) 1 as the loss is non-increasing, placing more mass such parts of space can never increase the loss contribution attributable to integrating over this region.
fully-valid, loss contributions from the agreement
Algorithm alsoo requires parameter 7 > 0. This parameter should be validity lower bound the models g E Q. providing a safeguard on the possibility of an "invalidity blowup" when restricting the ERM output 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 priori lower bound the validity allows for precise enough estimation of é 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 E Q this is 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.
5.2 Guarantees
The restricted output á of Algorithm admits the following guarantee over loss sub-optimality and invalidity.
This does yield uniform convergence Q given that the support of E Q need not align with P
7

---

Theorem 3. Suppose u E V with VC-dimension VC(V) S D. and for each E Q. the validity V(g) y > 0. For all 0 61,6,, I and for all choices of non-increasing loss finctions
1:R20 [0, MI Algorithm requires number of samples
oo M (log(1 + 1og(1/6)) i
M (D (Dlog(M/ea) log )
and number of validity queries
D Dlog(1/ye2) + log()
0
7/2
ensure that with probability 2 6, its output enjoys
Lp(g:1) S Lp(9";
and [()] - e2.
Thus, in regimes where e.g. 7 2 ((E)), ). D = (log(( 2)),, ) this guarantee represents a reduced number of queries under the ((M² log( ())/c(e2 bound of [ It also implies a "'dcoupling" of the query complexity from 61-
We note that the sample requirement from P is increased in certain regimes over the Ölog (Q) 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 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 '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 Ô (MD/E1) extra samples is asymptotically inconsequential relative to (M log( ()) and the Ô (D/rez) query budget required to execute the algorithm given access fully-valid P.
5.3 Better Query Complexity Bounds
5.3.1
Exploiting the Power of Active Learning
Theorem presennss somewhat pessimistic view of the potential of such a "post-filtering" scheme,.
Firstly, it ignores the potential of active learners 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 0. In the realizable setting, query complexities of active learning look like Ō (og)) (27). Definitionally, it can be shown that 0 S 1/e. Thus, proving the gains of active learning algorithms usually relies on bounding the disagreement coefficient non-trivially, i.e. showing 0 < o (1/cc), or ideally, < (11)
While this is challenging, as f is both class and couribution-deennenn quantity, there is a literature that addresses this potential in various settings
the references in (25]. In principle, could use such an analysis to show that the query complexity an active learning modification of Algorithm 2 is lower order than the guarantee of Theorem 3 when conditions it may be useful to note that a modification of Algorithm wherein is selected as the ERM on a dataset generated by mixture of and Ụ FRRM admits guarantees as well.
favorable. To this end,
5.3.2 Only Low-Loss Models Need Appreciable Validity
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 E Q. This is unnecessary with high probability, in the first step of the algorithm, one selects model E Q with O(e)) true loss. Thus, what really matters for such a strategy is that models that have relatively small loss do not have invalidity nearing 1.

---

This is a realistic scenario in the case that the loss function despite possibly not being proper prioritizes models which in some sense resemble the data generating distribution P. Indeed, it's somewhat difficult to envision situation where 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 if in addition it holds that all models q E Q with loss sub-optimality e1 have validity greater than some constant, then the query complexity of Algorithm can be improved to
0O Dlog(1/ez) + log
62
5.3.3 Removing the Positive Validity Requirement
Using an idea found in the algorithm of [. one can show that a learner has access to single distribution D with density and at least some non-zero constant validity, and the densities Sq are bounded above, that Algorithm can be modified so as to drop the requirement of positive validity over models when learning under the capped log-loss.
By mixing the ERM with D, giving mixture component ((4) to D, one can generate similar guarantees as those of Theorem 3] The modification can be found in the Appendix as Algorithm and enjoys the following guarantee.
Theorem 4. Suppose E V where VC(V) S. D. and that for each q Q. we have fa(a) S B. Suppose further that there is some known E P with density fo which has V(D) 2 c> 0 for some constant Then for all choices of 0 C2, 8 1/2 and M 0, Algorithm requires number of samples
Sō 10M2
M (log() Q1) log(1/o))
M (D looloog//// (M/e) log(1/61)
E1
and a number of validity queries
D Dlog(L/erez) Dlog(//rrs)+
Log(1//)))))))
00
6162
to ensure that with probability 2 1 - 8, its output enjoys
E Ex~P min (M, log(1/f((X))) Ex~P min (M, log(1/ (X))) te and 1(9) S ez.
Here, the Ô notation again hides factors polylogarithmic in 1/3.
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/3) when working with densities bounded above by 1. In the case that densities can be bounded above by as in the discrete setting of 33 this dependence disappears.
Conclusion
This work is intended as first-look into settings closer the common-case, where ensuring validity may be relatively cheap.
A more thorough investigation of the log-loss, well capped variants, seems very relevant line of further inquiry, given the widespread use of this family in practice and its useful information-theww properties. A natural extension to the first part of this work would be to consider learning in the agnostic case & 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 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.

---

References
[1] Ethan Perez, Saffron Huang, Francis Song, Trevor Cai, Roman Ring, John Aslanides, Amelia Glaese, Nat McAleese, and Geoffrey Irving. Red teaming language models with language models. arXiv preprint arXiv:2202.032885 2022.
[2] Abubakar Abid, Maheen Farooqi. and James Zou. Persistent ant--muslim bias in large language models. In Proceedings of the 2021 AAAI/ACM Conference AI, Ethics, and Society, pages 298-306, 2021.
[3] Steve Hanneke, Adam Kalai, Gautam Kamath, and Christos Tzamos. Actively avoiding nonsense in generative models. CoRR, abs/1802.0722) 2018.
[4] Takuhiro Kaneko and Tatsuya Harada. Blur, noise, and compression robust generative adversar- ial networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13579-13589, 2021.
[5] Augustus Odena, Vincent Dumoulin, and Chris Olah. Deconvolution and checkerboard artifacts. Distill, 1(10):e3, 2016.
[6] L. G. Valiant. A theory of the learnable. Communications of the ACM, pages 1134-1142, 1984.
[7] Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, and Linda Sellie. On the learnability of discrete distributions. In Proceedings of the Twenty-Sixth Annual ACM Symposium Theory of Computing, STOC '94, page 273-282 New York, NY, USA, 1994. Association for Computing Machinery.
[8] Nika Haghtalab, Cameron Musco, and Bo Waggoner. Toward a characterization of loss functions for distribution learning. CoRR, Nee119066022655 2019.
[9] Constantinos Daskalakis, Ilias Diakonikolas, Ryan ODonnell, Rocco A Servedio, and Li- Yang Tan. Learning sums of independent integer random variables. In 2013 IEEE 54th Annual Symposium Foundations of Computer Science, pages 217-226. IEEE, 2013.
[10] Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. Efficiently learning mixtures of two gaussians. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 553-562, 2010.
[11] Constantinos Daskalakis, Ilaas Diakonikolas, and Rocco A Servedio. Learning poisson binomial distributions. In Proceedings of the forty- forty-fourth annual ACM symposium on Theory of computing. pages 709-728, 2012.
[12] Glenn W. Brier. Verification of Forecasts Expressed in Terms of Probability. Monthly Weather Review, 78(1), January 1950.
[13] Irving John Good, Rational decisions. Journal of the Royal Statistical Society: Series B (Methodological), 14(1):107-114, 1952.
[14] Tilmann Gneiting and Adrian Raftery, Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102:359-378, 03 2007.
[15] Rafael Frongillo, Dhamma Kimpara, and Bo Waggoner. Proper losses for discrete generative models, 2022.
[16] Erich Leo Lehmann, Joseph Romano, and George Casella. Testing statistical hypotheses, volume 3. Springer, 1986.
[17] Jerzy Neyman and Egon Sharpe Pearson. On the Problem of the Most Efficient Tests of Statistical Hypotheses. Phil. Trans. Roy. Soc. Lond. A, 231669947706)222--337 1933.
[18] Patrick Rebeschini. Minimax lower bounds and hypothesis testing, December 2021.
[19] R.D. Reiss. Approximation of product measures with an application to order statistics. The Annals of Probability, 9(2):335 341, 1981.
[20] Matt Kusner, Brooks Paige, and José Miguel Hernández-Lobato. Grammar variational autoencoder. In International conference muchine learning, pages 1945-1954. PMLR, 2017.
[21] David Janz, Jos van der Westhuizen, Brooks Paige, Matt Kusner, and José Miguel Hernández- Lobato. Learning generative model for validity complex discrete structures. arXiv preprint 1711v.171..01644, 2017.
10

---

[22] Y IsolaP, T Zhou, et al. Image to imagetranslation with conditional adversarial networks. Proceedingsofthe Seteecneeeeeeenccmmmmeeeeooettee 1 1125: 134, 2017.
Hawaii, USA,
[23] Andrew Aitken, Christian Ledig, Lucas Theis, Jose Caballero, Zehan Wang, and Wenzhe Shi. Checkerboard artifact free sub-pixel convolution: A note sub-pixel convolution, resize convolution and convolution resize. arXiv preprint arXiv:1707.029377 2017.
[24] Zhifeng Kong and Kamalika Chaudhuri. Data redaction from pre-trained gans. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 538-677. IEEE, 2023.
[25] Steve Hanneke. Theory of disagreement-based active learning. Foundations and Trends in Machine Learning, 7:131-309, 01 2014.
[26] Steve Hanneke. A bound on the label complexity of agnostic active learning. In Proceedings of the 24th International Conference Machine Learning, page 353-360, 2007.
[27] Sanjoy Dasgupta. Two faces of active learning. Theoretical Computer Science, 412(19):1767- 1781, 2011.
[28]
Bruce Driver. Probability tools with examples, June 2010.
[29] Ton Steerneman. On the total variation and hellinger distance between signed measures; an application to product measures. Proceedings of the American Mathematical Society, 88(4):684- 688. 1983.
[30] Puning Zhao and Lifeng Lai. Analysis of knn density estimation. IEEE Transactions Information Theory, 2022.

---

7 Appendix
7.1 Probability Distributions and Measure Theoretic Formalism
We work over Euclidean space R and let be a Lebesgue measurable set with Lebesgue measure X(²) < co. By À and Lebesgue measurable set, we refer to the measure and o-algebra F arising from the usual construction of Lebesgue measure on Rd By "distribution", we mean a probability measure on the measurable space (x,xx), where Fx (ENX: E E F). Let u the uniform distribution be the measure given by u () = X(E ((X)) for E E Fx. Let P denote the set of all probability measures on (x,
We assume that P E P and q E Q C P have densities fr and fg with respect to the reference measure X. 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 5 > a > 0, we mean that for all E supp(g) == cl(z fx( 0}. we have a S fz) B, where the closure is defined through open balls in the Euclidean metric. Note that in this setting, we have ((supp(1) = 1, as (supp)(g))
[ [r E (u
f'dd O.
@ q the product measure over the measurable space (x Fx²), ). Such measure corresponds to the process of taking n i.i.d. samples ~ q. Denote the density of q" with respect to X via fm
Denote via q"h = q
We define log(1/0) g(x) < xo for x E and g(x) = oo for some x E F.. This allows us integrate over the finite part of functions and get finite result.
co. Following the conventions in (28), we say that 1 E E] g(z) 0 if
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 and functions in the validity class V V-are are (X, Fx.-Fx))maat measurabbe..
7.2 Estimates of Validity, Invalidity
We fix the validity function v as an arbitrary function X' - 10. measurable with respect to each
distribution q arising the Appendix, As discussed above, for a given model q E P. the "validity" of q is the quantity (gg)= Prx-q (u(X)= = 1), and the "invalidity" T(2) = 1 - Vg)). We will at times be interested estimating the validity of a model g using samples from q along with validity queries. Given an i.i.d. sample { from g, we let ((g)= = Σi v(X))/n be the natural estimate the validity of
At times. we will be interested in the validity of model under an estimate of the underlying validity function. To this end, given a model E P and a function g X - 1), we let (g) = Prx~ (9(X) 1). Given sample {X,) let Vg(g) Ei ((,))/n Note that in the language of this notation, we have (gg) = Vg)g) and (q)) V.(g). We extend this notation in the natural way to invalidity quantities.
7.3 Analysis of Empirical Risk Minimization, Improper Algorithm in Realizable Setting
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 < c < 1 arbitrarily, For any validity function v, if E P has I(4) > c, and PEP has I ((P) 0, then
(r >
Proof. Fix the validity function arbitrarily. Consider the event E-g = (a ( X v(x) = 0}. Then we have dry (P.9) supecx IP(E) q(E)) 2 g(Ew)) - P(E-v) e, where have used that I(P) 0 implics P(E-w) = 0.
12

---

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 lower bound the total variation between product measures by the difference in probabilities on the event that at least one example from sample of size n is invalid. Of course, for each sample, this happens with probability 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 O < c
<<> 1 and n E NN {0} arbitrarily. For any validity function v, if q E P has I(g) > and P P has I(P) = 0, then
drv ..
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 the event
E21 - ( In) E X li s.t. v(x,) = =
Because P has perfect validity, any given draw from P has probability of being invalid. Thus, ("(E>1) 0. On the other hand, the invalidity of q states that for any S I n, we have (( E X' v(x) = 0}) > c. Let E, fx E X' v(x) 1}, and note that g( Ev) < Then we
have
9" (E1) = 1 - -E,)) > 1 (1 c)n
2
where the final inequality follows from the fact that (1 + x/n)" R S e² for x S 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 bound on the probability that after samples, model with appreciable invalidity has smaller loss than P.
Pearson
Lemma 3. Fix 0 < < and E NN \ {0} arbitrarily. For any validity function if E P has T(g) > e, P E P has T(P) = O, and y and have densities with respect the reference measure then
Prs-Pn (((S))2*(SS) ne
2
Proof. The proof follows that of the Neyman-Pearson lemma's claim that the Likelihood Ratio Test achieves the lower bound the sum of Type I and Type II errors (18), combined with Lemmal 2 We give the full argument for completeness.
Fix the validity function arbitrarily, and note the following string of relations:
Prg-pn (f((5) PP / 11f7()) ((())
min (z) (x)
drv ,4")
< nc
where the switch to total variation in the second to last line is the result of a classic characterization of total variation given by "Scheffe's Theorem", and the final line comes from Lemmal 2
D
13

---

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 y have appreciable invalidity with weaker one that the total variation between a model g and the data distribution can no longer rely on the structure of the supports of 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.
appreciable. When does not have appreciable invalidity, we
Lemma 4. Fix 8 < 1 arbitrarily, and let P.q E P be distributions with densities with respect to A. Then if drv (g. P) 2 6, and S PD for n 2 (1log(16))/(), holds with probability 2 that
Ls(P) Ls(g)-
Proof. When q and both possess densities, we can related the the probability that the likelihood of q is at least that of P to their total variation, in the Seayaan-Pearson Lemma.
Prg-p" (S) 50))) (*())
([f sf (N
min (fF(z), (x)
S e (drv
S m
Here, the second to last inequality is the consequence of powerful result of [1] (and later (29). namely that for any two collections of probability measures {4: Vi=1 and {p: over measurable spaces FF)) the product measures over the respective collections g" and p" satisfy
1 - exp
Σ dr (r.(p. 1=1
drv(d"
The final inequality follows from assumed gap in total variation between P and
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 large total variation distance from P.
Lemma 5. Fix 0 < 8, 61, C2 < arbitrarily, and suppose P E Q. If P is fully-valdd under v, and S ~ pa for Ω [og[ (2) (o))((()))( ), then with probability 2 â over S ~ Pn, the ERM
min(e?.r2)
solution
arg min
Σ
log(1/g(zi)),
REQ
3,ES
satisfies both
drv(q, P) S and I(ÿ) S e2.
Proof. Let QdTvze {g E :: (g. P) > G). By Lemma and a union bound, it holds that
Prs- (dT((GPP) 21
< PT (3q E Qdrv sit. LL(g) s Ls(())
<12drv>al
max gEReypon
Prewen (L(1)) s Ls(P))
< 1Qle-me?1
14

---

In the same manner, let u be an arbitrary validity function, and let Qi>e, {q E Q I(())) e2)
Then we have
Pm
T(1) > 62
s Pm (7
E s.l. Ls(g) S Tis(P))
Qizes
- 1r max Prs- (L(1)) S Ls(P))
< [ 162
where the final inequality holds by Lemma Then finally,
Prs- pm ( P) V [( > 22
S 1
$1Q/e-nri7 nr//
+|[|e 1Q "ca
and so choosing n 2 2(log( Q)) + (l)))))))///))) min(ei, E2) ensures that the sum of these final terms S 6.
Before prove Theorem we need one final intermediate result, which 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 wepl-appro by a linear function near 1. We will use this result to argue that the loss of the output of Algorithm [ is not significantly different than that of the ERM in the support of the ERM.
Lemma 4. Fix 0 <
1. For any q E P having a density with respect the mixture M = - e/2)q + eu/2 has density JM (M() = - -e/2) +f(())/2 and this density satisfies
log (1/fa((e)) s sc+ log 11fg((1)
for all x E X.
Proof. The existence claim on the densities is immediate given the definition of the uniform distribution with respect to the reference measure A. To see the inequality, fix x E X arbitrarily, and note that far(z) (z) (1 c/2)f Thus, we may write
log (1/Sar(e)) < log
1
+ +log
1/fg(t))
11
1
c/2 -1)
+ log
1/fg(z)
</2
+log
(L/f((z)
1 e/2
< log (1/fg(1))
where second equality comes from the fact that log(2) < = 1, the final follows from the fact that z/(1 - 2) < 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 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 support with P.
To deal with this possibility, we mix the ERM model with the uniform distribution in accordance with Algorithm Because the weight given to the uniform distribution is O(min(e?: (2)), the invalidity 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(ÿ FRM) and it's complement. We first observe that the ERM always has an empirical risk which a faithful estimator of the integral Ex-P [L[X supp(ğ ERM)] log (1/ fa (x))), allowing us to bound this
15

---

integral above in terms of the loss of P. The integral of the loss over supp(4 (RM) can be shown to be small using the lower bound on the density the output model q afforded by mixing with the uniform distribution, and the fact that supp((ERM) must have small measure under P when the ERM close to total variation.
Theorem 1. Fix 0 < ö, 62,62 < arbitrarily, and suppose P E Q and that P is fully-valid under If it holds that for each E Q that S fx(x) S 3 for all x E supp(g), then there is an
log² (1/ (1/min((1,,.0/ 02) (log(1 log(1/6))
N O
min(ct.e2) 62)
such that for all n 2 N, with probability 2 11 6, the output q of Algorithm satisfies Lp( & Lp(g") +1 and I S 62.
Proof. Fix v arbitrarily, and let εΛ. min(E1, 62). To see the claim the validity, note that by the guarantee of Lemma the assymptotic complexity of Lemma y the guarantee ((Â)))) I 62/2 with probability 2 1 5/3, in which case
Prx-g (x(X) = 0) Prx uuw (u(X) =0)
en
+ Prx (v(X) = 0) en
22
fA
+1.
2
8
8
E2
The loss of the outputted model i can be decomposed into the contributions from the loss in supp(i ERM) and it's complement:
Lr(g) = Ex-r 1[x (upp("erm)) - log((1/f(())) + Ex-p 1[x e supp((erm))) (ooo///mam)(1oo(((((()))))
To bound the first term, for each Q, consider the function
B²(x) = {0 log (1/f((=)) if E supp(g),
else.
These functions bounded above by log(1/a) and below by log(1/8) (if 3 1, simply loosen the density upper bound), and thus for a sample X ~ P, define bounded random vari- ables (X). By Hoeffding's 's inequality and a union bound, it holds that sample S of size 2 (1log2(1 (1/a))log(())))) + log(1 (1(1))))/e from P large enough such that with probability 2 8/3, for each q Q, it holds that
E Ex~P (B,() - Σ B
Note that for each E Q with ls((4) < oc, it holds that Lg(g) coincides with the empirical estimates of Ex~P(B,(X]] namely
B,(z)) 1 Σ log (1/fg(zx)).
n
2,ES
Furthermore, this coincidence takes place for 9ERM with probability 1, as E Q implies that Ls(ğ ERM) S (P( < with probability 1 note that Ls(P) is good estimator for Lp(P) in the sense arising from an application of Hoeffding, as log(1/fp(X)) is bounded almost surely for X P given that P has density that bounded in it's support member of Q). Thus, may write
Ex-P 1[X supp(s ERM) log(1/f((X)) Ex~p 1 supp(ĀERM)) log(1) fqum (X)) (x)) + E1
4
Ex-p [B (X)]
61
361
< Ls(gERM) +
< Lr(g") + 61
2
16

---

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 2 (log2 (log[[Q) + log(1/6)) /cf), holds with probability 2 Because q has density at least ex/8 everywhere in x we
6/3 that
(iv(N P) S e have
Exar 1[x supp("ERM)) log(1/f6(X))
s log(8/ex) Exar 1[x supp(бERM))]
I <log(8/<A) drv (P,
<1//2,
where in the second line we use the fact that E (supp( (RM)) = 1 to argue that drv (P, FRMM > ((sup((EERM) Combining the bounds on the two summands and union bounding the confidence yields the full guarantee.
We note that this argument implies slight more precise sample complexity bound given by
log(( @) + (1/0) log² (1/ min((1, e2, a)) [lg(((]) log
δ max
cf
which affords a minor improvement in certain regimes where 62 < éj.
7.4 A Zero-Query Lower Bound
Theorem 2. For all 62 < 1/4 and for all proper learners L S - P, if the sample S ~ Phh is of size n < 1/802, then there exists a triple (P, Q, v) with P Q and P fully-valid, on which L(S) has invalidity I(L(S)) > 62 with probability 2 1/4.
Proof. We give an argument inspired by the proof of a lower bound Theorem 2 of 30
Let X = j0, 1] C IR. Fix the proper learner L and 62 < 1/4 arbitrarily. Consider a model class
defined by Q (P, PJ. where P and have densities with respect to the Lebesgue measure
1
fr(x) [[ E [0, 2e2]] 1 2ea fa(x) 1[x [2e2, 11] 1 2
This Q gives rise to two realizable problem instances of interest. Under the first, P is the data generating distribution and v(x) = everywhere except for in 11-2ey 262, 1], where v(x) = 0. Under the second, 1 is the data generating distribution and u(x) = everywhere except for in [0, 2e2). where v(x:) 0. Assume by contradiction that for both problem instances, given sample of size < 1/882, we have that ((L(S)) < with probability > 3/4. In both cases, we have that [g] 2 2E2) > Eg for the model g which is not the data generating distribution. Thus, L(S) is a model with / (L)) < é2 with probability > 3/4 over both problem instances if and only it identifies the data generating distribution with probability 3/4 over both problem instances.
Consider the simple hypothesis tester defined by T2(S) = L(S), which by the above, outputs the correct data generating distribution given a choice of or and given n S 1/862 samples from either P or P with
wiiht probability > 3/4. Note that the distributions P, P have drv (P, P) 212/(1 26²) < 4c2, where we use 62 < 1/4 and 2/(1 - 2) I 2z for small enough in the inequality. By classic upper bound on the total variation between product measures [19], we have
that dPv pa) < 4nez. Then, by Le Cam's method and this upper bound on drv Pn), we have
1 SP pm) 2
1 - 2ne2-
inf T:S (P.P)
max Presun (Tz(S) # 4)
drv (Pn
2 2
2
Thus, n < 1 1/8e2, the there is a choice of data generating distribution such that Tr. incurs enror probability 1/4, which is contradiction.
WWhen the uniform distribution has a density smaller than 1, there is an extra log factor account for here.
We can WLOG this away by adding the condition that X(X() e.g. arising from normalized data.
17

---

7.5 Strategies Arising from Estimation of the Validity Function
When the validity function is known to lie 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 that unlike in most learning settings, the learner can actually choose which distributions it would like estimate with respect to, i.e. decide under which marginal distributions over X' the estimate should small disagreement with v.
We begin with a lemma arguing that whenever the ERM has positive probability of outputting an example with ((x) I, and the disagreement of ê and under proposal distribution is small enough, the restriction will indeed yield a low-validity model.
Lemma 5. F < and a distributtin g P absolutely continuous with respect À arbitrarily, Further, fix V4)) such that 0 < (g) S V (q), and suppose that for some i X + {0, } have
Prx- (6(X)= # x(X)) (g)e
Then whenever there is distribution i corresponding to
fa(x) x (z( 1},
it has invalidity (()) S.
Proof. Let Vo(g)= = Prx-g (o(X) = 1) denote the normalizing constant for the restriction to esti- mated valid region. Note that the restriction corresponds to a probability distribution if and only if Vg(g) > 0, and that in this case
(z))) = Vi(e)
fa(x)
holds further that @ is absolutely continuous with respect to X, and that we can write the following chain of relations:
I( = / 1(v(x) = 01]((x) dx(x))
1
1((ax) + (())s,(()) dA(x)
Vo(a)
(g))
Vo(g)²
V(a)
Vg(g) 2'
where the first inequality follows after inputting the definition of fg. and the final two inequalities come by assumption. It's further possible show that validity of q can be approximated from above by a constant multiple of (g), which can be conceptualized as the validity of if è were the true validity function. In particular,
v(4) = (Volo) - Vo(o)) + V(1)
Vol4)+ + / (1lo(o) = 1] 11-1(0(6) =1)) (x) d2(x)
S Vo(1)) / /1(0(a) & ((x))f((x) dX(x)
$ Vel4)) + V(gee
2
S Volg) + V(q)e
2
This implies that V(g) S V1(g)/(1 - e/2), which yields V(g) S 2V²(g) as e < Utilizing this inequality in the last line of the first string of inequalities gives the guarantee.
D
18

---

The need for a lower estimate on the validity in the precision of the estimate for é 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 é may create huge (or infinite) increases in mass over the proposal distribution - in the language of Lemma 5 (g(g) may be very small for a proposal distribution q. this is the case, the estimate i 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 g constructed by accepting samples from some "proposal distribution" q that fall in the valid part of space under ú, the contribution to the loss from the part of space where i agrees with e can never exceed the total loss of the proposal distribution g. Essentially, we are exploiting the full-validity of P here in the subregion
of the agreement region {v(z) = }(z)} on which the loss is computed, we have that 6(x) = 1 by the fact that X P valid. This means that the density of q can only larger than the density of q in this region, which under non-increasing loss cannot increase the loss over that incurred by
Lemma 6. Fix 0 < 6,8 < 1, validity fanction estimate è : X + {0,1}, and q E 2 aarbitarrll.. Supposel I: R20 + [0, M) is non-increasing loss function. Then whenever
f4(x) x [,())[(((1)) =
corresponds to a probability distribution, it enjoys
Ex-r (fg(X)) [((X) = -(X)]] s Lr(g
Proof. Let Ve(g) Prx~9 (6(x) 1) be the normalizing constant for q. where we note that Vo(g) > O when [z) = 1] corresponds to probability distribution.
Given that P is fully-valid, we have Prx-r (v(X) 1) 1. By the fact that integration is defined up to null sets, it holds that
Ex~P ((f((X)) (((())))(((())----))) -[((x)=((x)) x(x)) Exap (f((()) 16(()) = o(X) 11
Further, we may write
Ex-P 1 (lg(x)) ((0() = o(X) A xxx)= =1]
[((X) (113))000200110 41) -[((x) 11|
< Ex-P
Vi(1)
fg(X)
< EXxx
Vo(a)
< EX-P
(ff(())
L)(g:t).
Here, the second to last inequality comes from the non-negativity of the loss along with the fact that whenever 6(X) = 0, the integrand is zero when 8(X) = 1, the loss is just evaluated at the normalized density, and so the integrand introduced in this line an upper bound for the previous integrand. The final inequality comes from the non-increasingnes of the loss function along with the observation that (²) < 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 samples in Sp is sufficient to make the disagreement of u and i small enough under P such that the contribution the loss in that part of space can be controlled by trivially applying the loss upper bound M.
19

---

Theorem 3. Suppose u E V with VC-dimension VC(V) S D. and for each E Q. the validity V(g) y > 0. For all 0 61, I and for all choices of non-increasing loss functions requires number of samples
1:R20 [0, MI Algorithm 2
SO M (log(1 + log(1/6)) (D log (M/(M//1))))) + log(1/6))
of
and number of validity queries
D log Dlog(1/762) + log (1/0)
0
762
ensure that with probability 2 6, its output enjoys
Lp(;: - (p( + and (Ø) S E2.
Proof. Given that the loss is bounded, Hoeffding's inequality applied the random variables 1 (X)( for X ~ P. and a union bound, imply that is large enough that with probability 2 1 - 8/3, have that for all q Q, the empirical loss estimates [ss 1) are most 61/4 away from true losses Lr(g;() l). For any choice of [RM because we have v E V, it must hold that any minimizer ê is consistent with the labeling under of both Sp and Sq The standard rates of convergence when choosing an arbitrary consistent hypothesis thus imply that the sizes of Sp and S/x are large enough to guarantee that, with probability
28/3, we have
PEX~P (6(X) + ((x) S
61 2M
(6(x) (xx)) S
7
A Prx-quaO zuo
2
By a union bound, with probability 2 1 8, 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 ỘERM (f6(x) 1}} 0. as for any ERM, we have
ERM (f6(z) = 11) = Ex Ex~ama ma [1/p(x) = 1]] - / (1(v(x) 1] 1[((z) = 1]) di (R)
E X Ex [1(((x) = 1]] - 1[b(x)) # ((x))dqEEM<(()
762
2
0.
Thus, the restriction of the ERM the estimated validity region is a viable probability distribution, and is outputted by the algorithm as q. For any estimate of the validity function 0, we can decompose the loss of g as
Lp(ğ:l) Ex-p (f((())
1 = v(x)] + +XX~ (f((X) - 1(( * u(X)]
First using Lemma 6 and then using the uniform convergence of the loss estimates, we can bound the first term as
Ex-p ((((()) - 1[(())
$ [p(âERR;
61 $ Lp(gft +
2
$ L +
61
2
where of = arg ming, Lp(g 1) is the lowest-loss model in the class Q. To upper bound the second
term the loss decomposition, we can use the fact that Prx-p (f(X) + v(X)) S <1/2M and the upper bound on the loss to write
Exap (f((X)) 1[((x) # v(x)] < M Ex~p
[[(X)) # v(X))
s E1
2/
20

---

Algorithm 3 Restriction to ERM under Log-Loss without Validity Assumption
1: procedure VALID VALID_ www.RRRSSTRIIIOIO SitaSTRRrCctIOLLLLO(DSSttrbooooo Class Q, Validity Class V, D, 8, c1, (2)
(log +lg((1)))))) i.i.d samples ~ P
2: S + Ω
sf
3: @ERM arg min E EEss min (M, (z)(f(())))
4: i FRRM (1 c18) 9 ERM + c -
Mix with constant validity D
5: Sp + Q MiD MiD (log(11))
i..d. samples ~ P.
SqURM Ω
D log (oog(//ac))) i.i.d. samples ~ JERM
11
6: +- arg min En E BRM 1[((x) + vx))
Label x E Si via v
7: return fa Sā . ((((z) = 1] if FRM ((((z) = 1}) > 0 else ʃa =SâERM
8: end procedure
yielding the loss guarantee.
The validity guarantee follows directly from the fact that Prx~qumu (6(X) + v(X)) S yc2/2 and Lemma 5 where y furnishes the lower estimate for the validity of the model & ERM-
The corollary to Theorem 3 stating that only low-loss models need appreciable validity is straightfor- wards. 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 of the optimal loss across models in Q, meaning that has validity greater than some constant Thus, one can run Algorithm 2 with an Si large enough to achieve (ee2) disagreement rate between and under samples from ERM. lowering the label complexity.
The proof of Theorem Iis very similar to that of Theorem 3
The main difference is that when the exploit stability property under mixture similar to that introduced in Lemma 4 This allows us to mix 9 ERM with a distribution of constant validity to get a validity lower bound the final proposal distribution ERM without increasing the loss more than (()). The validity lower bound can then be used as in Theorem 3
loss is the capped log-loss,
Theorem 4, Suppose v E V where VC(V) < D, and that for each q E Q. we have fa(x) S B. Suppose further that there is some known D E P with density fo which has ( 2 <> f some constant c. Then for all choices of c1, E2. < 1/2 and M > 0, Algorithm requires a number of samples
(1og() M (log() Q1) + log(1/8)) Sō CAMML
M (M)eg(M/e)) log(1/))))
of
61
and number of validity queries
D Dlog(1/cre)) + log(11/))
0
E1
to ensure that with probubility 2 8. its output enjoys
Ex-P min (M, (M, Ex-p min (M, log(// (X)))
and I(î) S E2.
Proof. WLOG assume B 2 and consider learning over I(2) min(M, log(1/2)) - (L/B)
translation of the capped log-loss bounded below by 0 for all inputs to fa E Q and bounded above by M = M log(1/3).
Similar to the proof of Theorem 3. with probability 2 1 - 8/2 over the sample S ~ p it holds that for all E Q that Ls(g:)) Lp(g:T) < <// in this case, we use the fact that fa S B to ensure that the random variables (X)) for X P are bounded, allowing for an application of
21

---

Hoeffding's inequality over empirical estimates of loss unbounded below. As above, for any choice of FRM. the sizes of Sp and Siguss are such that with probability N 1 1--66/3. 25/3.
Prx~P 6(X) + =x() S
61
A
Prx-qqEm ERM
xx S
C2
2M
16
As before, by union bound, these bounds both hold simultaneously with probability 2 1 6. We condition on this intersection of favorable events going forwards.
Note that when this intersection of events takes place, have @RR (f0(x) 1}) > 0. In this case, we have that V (RTM)) 2 61 (D) 2 610/8 as V(D) 2 c, and so identically to our work in Theorem we may write
$ ERM (f6(z) =}) 2 Ex~4 IMM [1(e(X) 11] f 1(0(z) + u(z))
C61
06162
8 16
0.
Thus, the restriction of 9 ERM 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 q. consider the loss decomposition used in the proof of Theorem 3
(g: = Ex-P ((((x)) ((( = v(x)
+ Ex-p T(4 1[((x) m(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 Vo( > be the normalizing constant for We can write
fawes (x)1(6(X)=11 1[((X) 11]
E Ex~P [xx =(()]
Ex-P
VolTERM)
fā (X)
Ex~p
Vo(ĀTRM))
Ex~P
[(aazu(
Here, the non-increasingness of the loss still holds, leading the final step. Now, fix some x X
arbitrarily, and note the following, in the style of Lemma 4
I(J (1)) + 1l0(113) = log (1/Si (x)
A M
+ log (1/Sieuu(o)) M
log
c1/8
(1/fiband (10) )) AM
El 1/4+ + log
/1/S (20) A
MM AM++ 61
< log
Thus, it holds that ff (x)) <
+ /4/4, and so we may write
S SExp T( (x)) + E1 Exap [((((1))
4
= -L((EERM: 1) 61
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 Lr(g") + c12..
121 Given Prx~ (6(X) + u x(X) S 02162/ 16, and the lower bound on the validity of qerM derived in the third paragraph above, we can again apply Lemma 5 to get the validity guarantee.
22

---

NeurIPS Paper Checklist
1. Claims
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, the assumptions 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 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
Yes, the assumptions are outlined in the Preliminaries and theorems. The Appendix has some further measure theory details for interested readers. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ http:p/bbl...giiiiee/d//deeeeaaa CoodeSubeeiieeeeeeeeee ssi asionnolle onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:[NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
25

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:::////uis//eeeeeeeee wttphherrrs.ccppppiepeeeep httpp//ccc...c/..cccccceeeeaaaa.
Answer: [Yes]
Justification:
We read the code of ethics and are in compliance.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The societal impacts limited for theory work like ours.
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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
26

---

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 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.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 best faith effort.
12. Licenses for existing assets
Are the creators 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?
Question:
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 dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, wwppppawpptheeee throdee.etecee...... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
27

---

Answer: [NA]
JNstification:[NA]]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:(NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere 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.
28


Reviews:
[{"review_id": "h4q2jLLERK", "reviewer": "Reviewer_yKWM", "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})$.", "questions": "Do all algorithms run in exponential time, i.e. computationally inefficient?", "limitations": "I have no concerns on the potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper considers a nontrivial problem, learning a generative distribution with validity verification. It contributes to the literature of both generative networks and distribution learning. On the other hand, it improves the query efficiency of the learning algorithm by specifying or restricting the class of distribution, loss function, class of validity functions. The progress on improving the query efficiency, see summary, looks a bit incremental; however, requires delicate handling in the algorithmic design and analysis. The theoretical analysis looks sound to me.", "weaknesses": "There are some typos. Line 136: choice of. Line 237: \"is true for .. for ..\" To name a few.\n\nSome 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.\n\nLine 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?\n\nIn addition, the format for the references is not unified. Some references are missing the information for venues.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for looking closely at our work, and apologize for sometimes being less clear than we should.\n\nIn 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. \n\nIn 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$.\n\nWith 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.\n\n[1]  Hanneke, S., Kalai, A., Kamath, G., & Tzamos, C. (2018). Actively Avoiding Nonsense in Generative Models, https://arxiv.org/abs/1810.06988", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DIqauWQwsR", "reviewer": "Reviewer_HLjo", "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.\n\nPrevious 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.\n\nFor 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.", "questions": "Could the authors elaborate on any practical insights that can be derived from the algorithms and bounds presented in this work?", "limitations": "See the weaknesses section. It would be great to include a discussion of insights for practice.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper makes concrete improvements to the bounds established in previous works (under certain assumptions).", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the review, and agree that the next version of the paper should furnish more practical insight.\n\nWe 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.\n\nLemma 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. \n\nIn 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.\n\n[1] Hanneke, S., Kalai, A., Kamath, G., & Tzamos, C. (2018). Actively Avoiding Nonsense in Generative Models. https://arxiv.org/abs/1810.06988 \\\n[2] Kaneko, T., & Harada, T. (2021). Blur, Noise, and Compression Robust Generative Adversarial Networks. https://arxiv.org/abs/2003.07849 \\\n[3] Kong, Z., & Chaudhuri, K. (2022). Data Redaction from Pre-Trained GANs. https://arxiv.org/abs/2206.14389 \\\n[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 \\\n[5] Malnick, S., Avidan, S., & Fried, O. (2023). Taming Normalizing Flows. https://arxiv.org/abs/2211.16488 \\\n[6] Liu, J., Xu, J., & Wang, Y. (2022). Efficient Retrieval-Augmented Generation: An Empirical Study of Practical Techniques. https://arxiv.org/abs/2210.04610", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "30GE5NEAMm", "reviewer": "Reviewer_CS1K", "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.", "questions": "-", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper makes good high level arguments for why regarding common case instead of worst case settings can be appropriate in some situations.\n\nThe proposed algorithm makes sense and are supported by mathematical derivations of its low error and high validity guarantees given assumptions on the space of learnable distributions.\n\nThe theorems look valid, though I didn't check the proofs.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the review, and will try to address the weaknesses they point out. \n\nWe would argue that most practical situations are likely closer to the regime of realizability \nexplored 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]. \n\nIt 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. \n\n[1] Hanneke, S., Kalai, A., Kamath, G., & Tzamos, C. (2018). Actively Avoiding Nonsense in Generative Models. https://arxiv.org/abs/1810.06988 \\\n[3] Kong, Z., & Chaudhuri, K. (2022). Data Redaction from Pre-Trained GANs. https://arxiv.org/abs/2206.14389", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "El1sujtOdQ", "reviewer": "Reviewer_KhXL", "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$). \n\n\nAmong 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).\n\n\nThe 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.\n\n\nFirst, 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).\n\nSecond, 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.\nFinally, the authors comment on ways to improve the query complexities of their results in this setting.", "questions": "Here are a few questions that came to my mind as I was reading (some may not be well-formed/basic misunderstandings):\n\n1) In the guarantee of Theorem 1, isn't $q^\\star= P$? maybe it would help to write a remark saying this.\n2) 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\n3) 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$?\n4) 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.\n5) 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?\n6) 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).\n7) 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? \n---\nMinor typos:\n\nLine 112: typo any \\\nLine 136 any choice of \\\nLine 142 samples \\\nLine 249 means of \\\nLine 250-252 is not coherent and can use some elaboration \\\nLine 286 $d$ should be $D$", "limitations": "The authors have adequately addressed limitations as far as I can see.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The authors present an interesting, suitably exhaustive and strong set of results for natural \"special\" cases of the problem of validity-constrained distribution learning. Both the settings that the authors study (realizability with log-loss, as well as validity oracle in a bounded VC class) in the paper are natural beyond-worst case instances of the problem, and may well form a reasonable model of practical scenarios. The gains in the realizable setting are particularly impressive---it is nice to see that one can in principle do away with the validity oracle, while also maintaining near-optimal sample complexity. Even in the second setting, which just adds the additional assumption of a bounded VC validity region over those of Hanneke et al. 2018, the authors obtain improved query complexities. Overall, the suite of results feels satisfying and paints a meaningful beyond-worst case picture of the problem.", "weaknesses": "While I do find the study compelling, if I am to nitpick and search for weaknesses, I will say that there are no proof sketches whatsoever for the main theorems in the body. Notably, the content is still well under the page limit, and hence I suggest that the authors at least attempt to summarize the main steps used in the proofs of their results in the main body. Also, certain points and sentences could have used more elaboration and verbosity, to make the reading slightly less heavy. For example, lines 251-252 were not coherent to me and seemed like a mouthful, and similarly, at a few other places, I felt like more exposition could have been useful for the reader.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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. \n\nAnswers to the reviewer's questions can be found below:\n\n1) 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. \n\n2) 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.\n\n3) 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. \n\n4) 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. \n\n5) 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. \n\n6) 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. \n\n7) 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)