論文の概要: Malicious Experts versus the multiplicative weights algorithm in online prediction

• arxiv url: http://arxiv.org/abs/2003.08457v1
• Date: Wed, 18 Mar 2020 20:12:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-22 13:26:45.167114
• Title: Malicious Experts versus the multiplicative weights algorithm in online prediction
• Title（参考訳）: オンライン予測における悪質専門家と乗法重みアルゴリズム
• Authors: Erhan Bayraktar, H. Vincent Poor, Xin Zhang
• Abstract要約: 2人の専門家と1人の予測者による予測問題を考える。 専門家の一人が正直で、各ラウンドで確率$mu$で正しい予測をしていると仮定する。 もう一つは悪意のあるもので、各ラウンドで真の結果を知り、予測者の損失を最大化するために予測を行う。
• 参考スコア（独自算出の注目度）: 85.62472761361107
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a prediction problem with two experts and a forecaster. We assume that one of the experts is honest and makes correct prediction with probability $\mu$ at each round. The other one is malicious, who knows true outcomes at each round and makes predictions in order to maximize the loss of the forecaster. Assuming the forecaster adopts the classical multiplicative weights algorithm, we find upper and lower bounds for the value function of the malicious expert. Our results imply that the multiplicative weights algorithm cannot resist the corruption of malicious experts. We also show that an adaptive multiplicative weights algorithm is asymptotically optimal for the forecaster, and hence more resistant to the corruption of malicious experts.
• Abstract（参考訳）: 2人の専門家と予測者による予測問題を考える。 専門家の一人が正直で、各ラウンドで確率$\mu$で正しい予測をしていると仮定する。 もう一方は悪意があり、各ラウンドの真の結果を知り、予測者の損失を最大化するために予測を行う。 予測者が古典的な乗法重みアルゴリズムを採用すると仮定すると、悪意のある専門家の値関数の上限と下限が見つかる。 その結果,乗算重みアルゴリズムは悪意のある専門家の腐敗に抵抗できないことが示唆された。 また,適応乗法重み付けアルゴリズムは予測者にとって漸近的に最適であり,従って悪質な専門家の腐敗に抵抗することを示した。

関連論文リスト

• Towards Human-AI Complementarity with Predictions Sets [14.071862670474832]
  予測セットに基づく意思決定支援システムは、人間の専門家が分類タスクを解くのに役立つことが証明されている。 共形予測を用いて構築された予測集合は、一般に平均精度の点で準最適であることを示す。 我々は,多種多様な専門家モデルと非最適スコアに対して,同等あるいはより優れた性能を提供する予測セットを見つけることが保証される,欲求的アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2024-05-27T18:00:00Z)
• Sorting and Hypergraph Orientation under Uncertainty with Predictions [0.45880283710344055]
  本研究では,不確実性下でのソートとハイパーグラフ配向のための学習強化アルゴリズムについて検討する。 我々のアルゴリズムは、予測なしで最良となる最悪の保証を維持しつつ、精度の高い予測性能を保証する。
  論文  参考訳（メタデータ） (2023-05-16T07:52:08Z)
• Mixing predictions for online metric algorithms [34.849039387367455]
  我々は予測を組み合わせるアルゴリズムを設計し、このような動的組み合わせと競合する。 我々のアルゴリズムは、バンディットのような方法で予測者にアクセスするように適応することができ、一度に1つの予測者しかクエリできない。 我々の下界の1つが予想外の意味を持つのは、$k$-server問題に対する定式化のカバーに関する新しい構造的洞察である。
  論文  参考訳（メタデータ） (2023-04-04T13:18:00Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Memory Bounds for the Experts Problem [53.67419690563877]
  専門家のアドバイスによるオンライン学習は、逐次予測の根本的な問題である。 目標は、予測を処理し、最小コストで予測を行うことです。 アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。
  論文  参考訳（メタデータ） (2022-04-21T01:22:18Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Toward Optimal Adversarial Policies in the Multiplicative Learning System with a Malicious Expert [87.12201611818698]
  専門家のアドバイスを組み合わせて真の結果を予測する学習システムについて考察する。 専門家の一人が悪意があり、システムに最大損失を課すことを目指していると推測されている。 誤予測を常に報告する単純な欲求ポリシーは、近似比が1+O(sqrtfracln NN)$で最適であることを示す。 悪意のある専門家がその判断を適応的に行うことができるオンライン環境では、最適のオンラインポリシーを$O(N3)$で動的プログラムを解くことで効率的に計算できることが示される。
  論文  参考訳（メタデータ） (2020-01-02T18:04:46Z)

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

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