Fugu-MT 論文翻訳(概要): Efficient Competitions and Online Learning with Strategic Forecasters

論文の概要: Efficient Competitions and Online Learning with Strategic Forecasters

arxiv url: http://arxiv.org/abs/2102.08358v1
Date: Tue, 16 Feb 2021 18:48:37 GMT
ステータス: 処理完了
システム内更新日: 2021-02-17 14:49:08.742672
Title: Efficient Competitions and Online Learning with Strategic Forecasters
Title（参考訳）: 戦略的予知による効率的な競争とオンライン学習
Authors: Rafael Frongillo, Robert Gomez, Anish Thilagar, Bo Waggoner
Abstract要約: Witkowskiet al。この問題を特定し、勝者を選ぶための真正なメカニズムであるELFを提案した。 ELFは、確率の高い準最適予測器を選択するために、$Theta(nlog n)$イベントやテストデータポイントを必要とする。標準オンライン学習アルゴリズムは、$O(log(n) / epsilon2)$イベントのみを使用して$epsilon$-optimal予測子を選択します。
参考スコア（独自算出の注目度）: 10.772308279491202
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Winner-take-all competitions in forecasting and machine-learning suffer from distorted incentives. Witkowskiet al. identified this problem and proposed ELF, a truthful mechanism to select a winner. We show that, from a pool of $n$ forecasters, ELF requires $\Theta(n\log n)$ events or test data points to select a near-optimal forecaster with high probability. We then show that standard online learning algorithms select an $\epsilon$-optimal forecaster using only $O(\log(n) / \epsilon^2)$ events, by way of a strong approximate-truthfulness guarantee. This bound matches the best possible even in the nonstrategic setting. We then apply these mechanisms to obtain the first no-regret guarantee for non-myopic strategic experts.
Abstract（参考訳）: 予測と機械学習における勝者獲得競争は、ゆがんだインセンティブに苦しむ。 Witkowskiet al。この問題を特定し、勝者を選ぶための真正なメカニズムであるELFを提案した。 n$の予測者のプールからelfには$\theta(n\log n)$イベントまたはテストデータポイントが必要であり、高い確率で最適に近い予測者を選択する。次に、標準的なオンライン学習アルゴリズムが$O(\log(n) / \epsilon^2)$イベントのみを使用して$\epsilon$-optimal forecasterを選択することを示した。このバインドは、非戦略設定でも可能な限りベストにマッチします。次に,このようなメカニズムを応用して,非名指し戦略専門家に対する最初のno-regret保証を得る。

関連論文リスト

Fair Secretaries with Unfair Predictions [12.756552522270198]
予測値が少なくとも$maxOmega (1), 1 - O(epsilon)$倍の候補を受け入れることを約束しているにもかかわらず、アルゴリズムが最良の候補を受け入れる確率がゼロであることを示し、ここでは$epsilon$が予測誤差である。私たちのアルゴリズムと分析は、既存の作業から分岐し、結果のいくつかを単純化/統一する、新たな"ペギング(pegging)"アイデアに基づいている。
論文参考訳（メタデータ） (2024-11-15T00:23:59Z)
Competitive strategies to use "warm start" algorithms with predictions [12.970501425097645]
本稿では,温暖化開始アルゴリズムの学習と予測利用の問題点について考察する。この設定では、アルゴリズムは問題のインスタンスと解の予測を与える。我々は、$k$の予測を考慮に入れたより強力なベンチマークに対して、競争力のある保証を与えます。
論文参考訳（メタデータ） (2024-05-06T17:38:20Z)
No-Regret Online Prediction with Strategic Experts [16.54912614895861]
オンラインバイナリ予測の一般化をエキスパートアドバイスフレームワークを用いて研究し、各ラウンドで、学習者は、Kドルの専門家のプールからmgeq 1ドルの専門家を選ぶことができる。我々は、専門家が戦略的に行動し、彼らの信念を誤報することでアルゴリズムの予測への影響を最大化することを目的とした設定に焦点を当てる。目標は,次の2つの要件を満たすアルゴリズムを設計することです。 1) $textitIncentive-compatible$: 専門家に信念を真実に報告させるインセンティブ,2) $textitNo-regret$: Achieve。
論文参考訳（メタデータ） (2023-05-24T16:43:21Z)
Forecasting Competitions with Correlated Events [7.57024681220677]
フォロー・ザ・レギュラライズド・リーダー(FTRL)に基づく競合機構を提案する。それらのメカニズムは、$O(log(n)/epsilon2)$イベントのみを使用して、高い確率で$epsilon$-optimal forecasterを選択する。この相関による分布下では、FTRL機構は$O(b2 log(n)/epsilon2)$イベントを使用して、$epsilon$-Optimalの保証を保持する。
論文参考訳（メタデータ） (2023-03-24T04:15:03Z)
Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。目標は最小限のコストで予測を行うことだ。最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文参考訳（メタデータ） (2023-03-03T04:39:53Z)
Neural Greedy Pursuit for Feature Selection [72.4121881681861]
我々は,非線形予測問題に対する$P$入力機能のうち,$N$重要な特徴を選択するための欲求アルゴリズムを提案する。ニューラルネットワークをアルゴリズムの予測子として使用し、損失を計算します。
論文参考訳（メタデータ） (2022-07-19T16:39:16Z)
No-Regret Learning with Unbounded Losses: The Case of Logarithmic Pooling [12.933990572597583]
対数プール法(対数プール)として知られる基本的および実用的アグリゲーション法に焦点をあてる。オンラインの対戦環境において,最適なパラメータ集合を学習する問題を考察する。本稿では,O(sqrtT log T)$experied regretに達する方法で,専門家の重みを学習するアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-02-22T22:27:25Z)
Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文参考訳（メタデータ） (2021-06-15T02:23:07Z)
Online Adversarial Attacks [57.448101834579624]
我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。まず、オンライン脅威モデルの決定論的変種を厳格に分析する。このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
論文参考訳（メタデータ） (2021-03-02T20:36:04Z)
Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations [78.23408201652984]
トップk予測は、マシンラーニング・アズ・ア・サービス、レコメンダ・システム、Web検索など、多くの現実世界のアプリケーションで使用されている。我々の研究はランダム化平滑化に基づいており、入力をランダム化することで、証明可能なロバストな分類器を構築する。例えば、攻撃者がテスト画像の5ピクセルを任意に摂動できる場合に、ImageNet上で69.2%の認定トップ3精度を達成する分類器を構築することができる。
論文参考訳（メタデータ） (2020-11-15T21:34:44Z)
A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
論文参考訳（メタデータ） (2020-10-04T15:27:39Z)

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