The Sample Complexity of Uniform Approximation for Multi-dimensional CDFs and Fixed-Price Mechanisms

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 1/ϵ3log(1/ϵ)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.