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

arXiv:2602.10868v2 Announce Type: replace Abstract: We study the sample complexity of learning a uniform approximation of an n-dimensional cumulative distribution function (CDF) within an error epsilon > 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 epsilon-approximation with a sample complexity frac{1}{epsilon^3}{logleft(frac 1 epsilon 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.

Source: arXiv cs.LG | 2026-05-12