論文の概要: Robust Learning of Optimal Auctions

• arxiv url: http://arxiv.org/abs/2107.06259v1
• Date: Tue, 13 Jul 2021 17:37:21 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-14 14:32:02.353374
• Title: Robust Learning of Optimal Auctions
• Title（参考訳）: 最適オークションのロバスト学習
• Authors: Wenshuo Guo, Michael I. Jordan, Manolis Zampetakis
• Abstract要約: 本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。 我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 84.13356290199603
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning revenue-optimal multi-bidder auctions from samples when the samples of bidders' valuations can be adversarially corrupted or drawn from distributions that are adversarially perturbed. First, we prove tight upper bounds on the revenue we can obtain with a corrupted distribution under a population model, for both regular valuation distributions and distributions with monotone hazard rate (MHR). We then propose new algorithms that, given only an ``approximate distribution'' for the bidder's valuation, can learn a mechanism whose revenue is nearly optimal simultaneously for all ``true distributions'' that are $\alpha$-close to the original distribution in Kolmogorov-Smirnov distance. The proposed algorithms operate beyond the setting of bounded distributions that have been studied in prior works, and are guaranteed to obtain a fraction $1-O(\alpha)$ of the optimal revenue under the true distribution when the distributions are MHR. Moreover, they are guaranteed to yield at least a fraction $1-O(\sqrt{\alpha})$ of the optimal revenue when the distributions are regular. We prove that these upper bounds cannot be further improved, by providing matching lower bounds. Lastly, we derive sample complexity upper bounds for learning a near-optimal auction for both MHR and regular distributions.
• Abstract（参考訳）: 入札者の評価値のサンプルが反対に破損したり、反対に混乱した分布から引き出されたりする場合に、サンプルから収益最適のマルチバイダーオークションを学習する問題について検討する。 第一に, 人口モデルの下で, 定評定分布と単調ハザード率(mhr)の分布の両方において, 腐敗した分布で得られる収益の上限を厳密に証明する。 次に、入札者の評価に「近似分布」のみを与えられた新しいアルゴリズムを提案し、コルモゴロフ-スミルノフ距離における元の分布に対して$\alpha$-closeの全ての「真の分布」に対して、収益がほぼ同時に最適であるメカニズムを学習する。 提案アルゴリズムは,従来研究されてきた有界分布の設定を超えて動作し,分布が MHR である場合の真の分布の下での最適収益の1-O(\alpha)$1-O(\alpha)が保証される。 さらに、分布が正規である場合には、最適収益の少なくとも1-o(\sqrt{\alpha})$が与えられることが保証される。 一致した下界を提供することで、これらの上界をさらに改善することは不可能である。 最後に, MHRと正規分布の双方に対して, ほぼ最適のオークションを学習するために, サンプル複雑性上限を導出する。

関連論文リスト

• Efficiently learning and sampling multimodal distributions with data-based initialization [20.575122468674536]
  静止測度から少数のサンプルを与えられたマルコフ連鎖を用いて多重モーダル分布をサンプリングする問題を考察する。 マルコフ連鎖が$k$dのスペクトルギャップを持つ場合、静止分布からのサンプルは、静止測度からテレビ距離において$varepsilon$-closeの条件法則を持つサンプルを効率よく生成する。
  論文  参考訳（メタデータ） (2024-11-14T01:37:02Z)
• Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization [0.4732176352681218]
  本稿では、多様体制約データ分布のクラスにおける段階的領域適応の課題に対処する。 本稿では,適応的なワッサースタイン半径を持つ分布ロバスト最適化(DRO)を基礎とした手法を提案する。 我々のバウンダリは、新たに導入されたそれとの互換性尺度に依存しており、シーケンスに沿ったエラー伝搬のダイナミクスを完全に特徴付けています。
  論文  参考訳（メタデータ） (2024-10-17T22:07:25Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  本報告では,明示的な次元の一般スコアミスマッチ拡散サンプリング器を用いた最初の性能保証について述べる。 その結果, スコアミスマッチは, 目標分布とサンプリング分布の分布バイアスとなり, 目標分布とトレーニング分布の累積ミスマッチに比例することがわかった。 この結果は、測定ノイズに関係なく、任意の条件モデルに対するゼロショット条件付きサンプリングに直接適用することができる。
  論文  参考訳（メタデータ） (2024-10-17T16:42:12Z)
• New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem [34.51168440208439]
  スパースパラメータの内積を通じて腕の特徴が報酬に影響を及ぼすスパースコンテキストバンドイット問題を考える。 近年の研究では、グリーディアーム選択ポリシーに基づくスパーシリティ非依存アルゴリズムが開発されている。
  論文  参考訳（メタデータ） (2023-12-19T18:35: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 Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits [0.0]
  我々は、腕上の分布の一般、おそらくはパラメトリックでないモデルDを考える。 情報理論量に基づいて最適なアームを誤識別する平均対数確率の上限を提案する。
  論文  参考訳（メタデータ） (2022-09-30T10:55:40Z)
• Cooperative Distribution Alignment via JSD Upper Bound [7.071749623370137]
  教師なし分布アライメントは、2つ以上のソース分布を共有整列分布にマッピングする変換を推定する。 このタスクには、生成モデリング、教師なしドメイン適応、社会的に認識された学習など、多くの応用がある。 我々は,従来のフローベースアプローチを,単一の非逆数フレームワークで統一し,一般化することを提案する。
  論文  参考訳（メタデータ） (2022-07-05T20:09:03Z)
• Partial and Asymmetric Contrastive Learning for Out-of-Distribution Detection in Long-Tailed Recognition [80.07843757970923]
  既存のOOD検出手法は,トレーニングセットが長距離分布している場合,大幅な性能劣化に悩まされていることを示す。 本稿では,部分的および非対称的な教師付きコントラスト学習(PASCL)を提案する。 我々の手法は従来の最先端の手法を1.29%$, $1.45%$, $0.69%$異常検出偽陽性率(FPR)と$3.24%$, 4,.06%$, 7,89%$in-distributionで上回ります。
  論文  参考訳（メタデータ） (2022-07-04T01:53:07Z)
• Distributional Reinforcement Learning via Moment Matching [54.16108052278444]
  ニューラルネットワークを用いて各戻り分布から統計量の有限集合を学習する手法を定式化する。 我々の手法は、戻り分布とベルマン目標の間のモーメントの全ての順序を暗黙的に一致させるものとして解釈できる。 Atariゲームスイートの実験により,本手法は標準分布RLベースラインよりも優れていることが示された。
  論文  参考訳（メタデータ） (2020-07-24T05:18:17Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  確率分布が未知な分布の不確実性の下でBQOについて検討する。 標準的なBQOアプローチは、固定されたサンプル集合が与えられたときの真の期待目標のモンテカルロ推定を最大化する。 この目的のために,新しい後方サンプリングに基づくアルゴリズム,すなわち分布的に堅牢なBQO(DRBQO)を提案する。
  論文  参考訳（メタデータ） (2020-01-19T12:00:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。