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 frac1ε3logleft(frac 1 ε right)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.