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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 21 references that are in the map.
- First posted on arXiv 11 Feb 2026.

## Builds on (most cited first, 11 of 11)

- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022)
- [Pricing Query Complexity of Revenue Maximization](https://mlsanity.com/paper/2111.03158/) (2021)
- [Better Regret Rates in Bilateral Trade via Sublinear Budget Violation](https://mlsanity.com/paper/2507.11419/) (2025)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Learning to Maximize Gains From Trade in Small Markets](https://mlsanity.com/paper/2401.11596/) (2024)
- [Selling Joint Ads: A Regret Minimization Perspective](https://mlsanity.com/paper/2409.07819/) (2024)
- [Online Two-Sided Markets: Many Buyers Enhance Learning](https://mlsanity.com/paper/2503.01529/) (2025)

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

- [Regret Minimization in Bilateral Trade With Perturbed Markets](https://mlsanity.com/paper/2605.10475/) (2026)
- [Breaking the T3/4 Barrier for Regret Minimization With Bi-Dimensional CDFs](https://mlsanity.com/paper/2607.20258/) (2026)

## Abstract (arXiv)

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.