Research map / Learning theory and algorithms / Sample complexity
Distribution Learning with Valid Outputs Beyond the Worst-Case
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that under full validity of the data and realizable log-loss, ERM (with uniform mixing) achieves validity with samples scaling weakly in epsilon_2, and that restricting ERM to a VC-class estimate of the valid region needs only O(D/eps2) validity queries.
Problem
Validity-constrained distribution learning: learn a distribution with low loss relative to the best fully-valid model while keeping invalid mass below epsilon_2, using samples from P and costly validity queries.
Approach
When P is in the model class and fully valid, log-loss minimization (ERM mixed with uniform) guarantees validity with sample complexity depending on 1/min(eps1^2, eps2) rather than exponential query cost; when the validity function lies in a VC class, restricting ERM to an estimated valid region reduces validity queries from the prior polynomial bound.
Key results
- With P in Q and fully valid, ERM mixed with uniform achieves loss and invalidity guarantees with samples scaling as log(|Q|)/min(eps1^2, eps2) up to polylog factors.
- Valid-restriction algorithm uses O((D log(1/gamma eps2) + log(1/delta))/(gamma eps2)) validity queries when VC dimension of validity class is D and model validity is at least gamma.
- Any proper learner with n <= 1/(8 eps2) samples can have invalidity above eps2 with probability at least 1/4 in the worst case, showing the 1/eps2 dependence is tight for proper learners.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use log-loss ERM when P belongs to Q, rather than a general-purpose validity-query algorithm | Validity-constrained distribution learning · Realizable setting (P ∈ Q) | validity queries: \tilde{O}(\log(|\mathcal{Q}|)/\epsilon_1^2 \epsilon_2) -> zero | Helped |
| Use log-loss ERM under the realizability assumption | Validity-constrained distribution learning · Realizable setting (P ∈ Q) | samples: n \geq \Omega\left( \frac{\log(|\mathcal{Q}|) + \log(1/\delta)}{\min(\epsilon_1^2, \epsilon_2)}\right) | Helped |
| Mix the ERM output with the uniform distribution | Log-loss ERM in the realizable setting · Realizable setting with bounded densities | log-loss: L_P(\hat{q}) \leq L_P(q^*) + \epsilon_1 | Helped |
| Restrict the ERM model to an estimated validity region when validity belongs to a VC-class | Post-hoc validity restriction · Validity region in a VC-class of dimension D | validity queries: O\left( \frac{D \log(1 / \gamma \epsilon_2) + \log(1/\delta) }{\gamma \epsilon_2} \right) vs. \tilde{O}(\log(|\mathcal{Q | Helped |
| Assume only low-loss models have validity bounded below by a constant | Post-hoc validity restriction · Validity region in a VC-class | validity queries: O\left(\frac{ D \log(1 / \epsilon_2) + \log(1/\delta) }{\epsilon_2} \right) | Helped |
| Use capped log-loss and mix the ERM model with a known distribution of constant validity | Validity restriction with a VC-class validity function · Validity region in a VC-class; capped log-loss | validity queries: O\left( \frac{D \log(1 / \epsilon_1 \epsilon_2) + \log(1/\delta) }{\epsilon_1 \epsilon_2} \right) | Mixed |
| Reduce the sample size below the stated threshold for a proper learner | Proper learner in the realizable setting · Realizable setting (P ∈ Q) | invalidity: n \leq 1/8\epsilon_2; I(L(S)) > \epsilon_2 with probability \geq 1/4 | Hurt |
Surprising findings
- ERM alone cannot guarantee log-loss sub-optimality, though it does guarantee total variation and validity; mixing with uniform fixes the loss.
- Validity guarantees can come with sample complexity only weakly dependent on eps2 when P is in the model class, so validity arrives quickly under random sampling.
Limitations
- Analysis assumes P is in the model class (realizability) and fully valid.
- Log-loss guarantees require densities bounded above and below in their support and an extra polylog factor.
- Results for agnostic case P not in Q are left open.
Experimental setup
Baselines: constrained ERM improper algorithm of prior work
Builds on: Validity-constrained distribution learning (Goodfellow-style formulation of prio Neyman-Pearson lemma Le Cam / Yu-style product measure TV bounds
Closest papers by meaning
- Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.85)
- Improved Diffusion-based Generative Model with Better Adversarial Robustness (ICLR 2025 · similarity 0.84)
- A Likelihood Based Approach to Distribution Regression Using Conditional Deep Generative Models (ICML 2025 · similarity 0.84)
- Towards Theoretical Understandings of Self-Consuming Generative Models (ICML 2024 · similarity 0.83)
- Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization (NeurIPS 2024 · similarity 0.83)
- Generative Conditional Distributions by Neural (Entropic) Optimal Transport (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.