# Distribution Learning with Valid Outputs Beyond the Worst-Case

arXiv: https://arxiv.org/abs/2410.16253 · HTML: https://mlsanity.com/paper/2410.16253/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 31 references that are in the map.
- First posted on arXiv 21 Oct 2024.

## Builds on (most cited first, 12 of 12)

- [Image-to-Image Translation with Conditional Adversarial Networks](https://mlsanity.com/paper/1611.07004/) (2016)
- [Red Teaming Language Models with Language Models](https://mlsanity.com/paper/2202.03286/) (2022)
- [Persistent Anti-Muslim Bias in Large Language Models](https://mlsanity.com/paper/2101.05783/) (2021)
- [Grammar Variational Autoencoder](https://mlsanity.com/paper/1703.01925/) (2017)
- [Checkerboard artifact free sub-pixel convolution: A note on sub-pixel convolution, resize convolution and convolution resize](https://mlsanity.com/paper/1707.02937/) (2017)
- [Analysis of KNN Density Estimation](https://mlsanity.com/paper/2010.00438/) (2020)
- [Data Redaction from Pre-trained GANs](https://mlsanity.com/paper/2206.14389/) (2022)
- [Actively Avoiding Nonsense in Generative Models](https://mlsanity.com/paper/1802.07229/) (2018)
- [Blur, Noise, and Compression Robust Generative Adversarial Networks](https://mlsanity.com/paper/2003.07849/) (2020)
- [Proper losses for discrete generative models](https://mlsanity.com/paper/2211.03761/) (2022)
- [Toward a Characterization of Loss Functions for Distribution Learning](https://mlsanity.com/paper/1906.02652/) (2019)
- [Learning a Generative Model for Validity in Complex Discrete Structures](https://mlsanity.com/paper/1712.01664/) (2017)

## Abstract (arXiv)

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 an atypical 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 of 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.