# Description Complexity of Regular Distributions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 May 2023.

## Built on by (most cited first, 3 of 3)

- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Learning Thresholds with Latent Values and Censored Feedback](https://mlsanity.com/paper/2312.04653/) (2023)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)

## Abstract (arXiv)

Myerson's regularity condition of a distribution is a standard assumption in economics. In this paper, we study the complexity of describing a regular distribution within a small statistical distance. Our main result is that tildeTheta(ε-0.5) bits are necessary and sufficient to describe a regular distribution with support [0,1] within ε Levy distance. We prove this by showing that we can learn the regular distribution approximately with tildeO(ε-0.5) queries to the cumulative density function. As a corollary, we show that the pricing query complexity to learn the class of regular distribution with support [0,1] within ε Levy distance is tildeTheta(ε-2.5). To learn the mixture of two regular distributions, tildeTheta(ε-3) pricing queries are required.