在仅限一比特反馈下，实现高维分布函数均匀逼近的样本复杂度近似与维度无关。
The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms
- 基于一比特反馈设计高维累积分布函数的均匀逼近方法。
- 样本复杂度为 $\frac{1}{\varepsilon^3} \log(\frac{1}{\varepsilon})^{\mathcal{O}(n)}$，维度仅影响对数项。
- 适用于小市场固定价格机制学习，可给出紧致样本复杂度与新后悔界。
研究在仅允许一比特反馈条件下，以误差 $\varepsilon > 0$ 学习 $n$ 维累积分布函数（CDF）的均匀逼近所需的样本复杂度。该问题可视为全反馈下多变量DKW不等式的带通反馈版本。主要结果表明：样本复杂度在维度上近乎不变——在任意精细网格上实现 $\varepsilon$-均匀逼近的样本量为 $\frac{1}{\varepsilon^3} \log\left(\frac{1}{\varepsilon}\right)^{\mathcal{O}(n)}$，其中维度 $n$ 仅通过对数项影响复杂度。作为直接推论，本文为小市场中的固定价格机制学习（如双边交易场景）提供了紧致的样本复杂度界与新的后悔保证。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。