The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms
This provides tight bounds for learning fixed-price mechanisms in small markets, such as bilateral trade, but is incremental as it extends existing inequalities to a bandit feedback setting.
The paper tackles the problem of learning a uniform approximation of multi-dimensional cumulative distribution functions with minimal one-bit feedback, showing a sample complexity of (1/ε^3) * (log(1/ε))^{O(n)} where dimensionality n only affects logarithmic terms.
We study the sample complexity of learning a uniform approximation of an $n$-dimensional cumulative distribution function (CDF) within an error $ε> 0$, when observations are restricted to a minimal one-bit feedback. This serves as a counterpart to the multivariate DKW inequality under ''full feedback'', extending it to the setting of ''bandit feedback''. Our main result shows a near-dimensional-invariance in the sample complexity: we get a uniform $ε$-approximation with a sample complexity $\frac{1}{ε^3}{\log\left(\frac 1 ε\right)^{\mathcal{O}(n)}}$ over a arbitrary fine grid, where the dimensionality $n$ only affects logarithmic terms. As direct corollaries, we provide tight sample complexity bounds and novel regret guarantees for learning fixed-price mechanisms in small markets, such as bilateral trade settings.