論文の概要: The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms
- arxiv url: http://arxiv.org/abs/2602.10868v1
- Date: Wed, 11 Feb 2026 13:55:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-12 21:44:01.954426
- Title: The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms
- Title（参考訳）: 多次元CDFのための一様近似のサンプル複雑度と固定価格機構
- Authors: Matteo Castiglioni, Anna Lunghi, Alberto Marchesi,
- Abstract要約: 我々は,$n$次元累積分布関数の均一近似を学習する際のサンプル複雑性について検討した。
小型市場における固定価格メカニズムの学習において,厳密なサンプル複雑性境界と新たな後悔の保証を提供する。
- 参考スコア（独自算出の注目度）: 25.375074054942434
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
- Abstract（参考訳）: 最小の1ビットフィードバックに制限された場合, 誤差$ε>0$内における$n$次元累積分布関数 (CDF) の均一近似を学習する際のサンプル複雑性について検討した。
これは「完全なフィードバック」の下で多変量DKWの不等式に匹敵するものとして機能し、それを「バンドフィードバック」という設定にまで拡張する。
サンプル複雑性の均一な$ε$-approximationとサンプル複雑性の$\frac{1}{ε^3}{\log\left(\frac 1 ε\right)^{\mathcal{O}(n)}}$を任意の微細格子上で得られる。
直結系として、二国間貿易設定のような小市場における固定価格の仕組みを学習するための厳密なサンプル複雑性境界と、新たな後悔の保証を提供する。
関連論文リスト
- Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum [62.691095807959215]
我々は,シングルタイムスケールアクター・クリティック(AC)アルゴリズムを用いて,$O(-2)$の最適なグローバルポリシを得るための最適なサンプル複雑性を確立する。
これらのメカニズムは、既存のディープラーニングアーキテクチャと互換性があり、実用的な適用性を損なうことなく、小さな修正しか必要としない。
論文 参考訳（メタデータ） (2026-02-02T00:35:42Z) - Pair Correlation Factor and the Sample Complexity of Gaussian Mixtures [0.0]
本稿では,コンポーネント手段のクラスタリングを計測する幾何量であるemphPair correlation Factor (PCF)を紹介する。
最小のギャップとは異なり、PCFはパラメータ回復の難しさをより正確に判断する。
均一な球面の場合、通常の$epsilon-2$以上のサンプルが必要な場合に、サンプルの複雑さ境界を改良したアルゴリズムを与える。
論文 参考訳（メタデータ） (2025-08-05T16:50:33Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - On counterfactual inference with unobserved confounding [36.18241676876348]
独立だが不均一な単位を持つ観測的研究を前提として、各単位の反実分布を学習することが目的である。
我々は、すべての$n$サンプルをプールして、すべての$n$パラメータベクトルを共同で学習する凸目的を導入する。
対数的ソボレフ不等式を満たすためにコンパクトに支持された分布に対して十分な条件を導出する。
論文 参考訳（メタデータ） (2022-11-14T04:14:37Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - $k$-Variance: A Clustered Notion of Variance [23.57925128327]
我々は,ランダム二成分マッチングの機構に基づく分散の一般化である $k$-variance を導入する。
1次元測度、クラスター測度、低次元部分集合に集中した測度など、いくつかの重要な場合において、この量の詳細分析を行う。
論文 参考訳（メタデータ） (2020-12-13T04:25:32Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
差分的にプライベートな分布の平均推定におけるミニマックスサンプルの複雑さについて, 新たな上限値と下限値を与える。
$n = Thetaleft(frac1alpha2 + frac1alphafrack-1varepsilonright)$サンプルは必要で、$varepsilon$-differential privacyの下で$alpha$-accuracyと見積もるのに十分である。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。