論文の概要: Learning in an Echo Chamber: Online Learning with Replay Adversary

• arxiv url: http://arxiv.org/abs/2509.25135v1
• Date: Mon, 29 Sep 2025 17:50:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-30 22:32:20.183244
• Title: Learning in an Echo Chamber: Online Learning with Replay Adversary
• Title（参考訳）: Echo Chamberでの学習: Replay Adversaryによるオンライン学習
• Authors: Daniil Dmitriev, Harald Eskelund Franck, Carolin Heinzler, Amartya Sanyal,
• Abstract要約: 本稿では,リプレイ設定におけるオンライン学習という学習理論の枠組みを紹介する。 クロージャベースの学習者は、少なくとも$mathrmExThD(mathcalH)$の誤りを任意の適応的敵に対して行う。 敵に対しては、すべての交叉閉クラスに対して同様の有界性を証明する。
• 参考スコア（独自算出の注目度）: 13.758101623622105
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As machine learning systems increasingly train on self-annotated data, they risk reinforcing errors and becoming echo chambers of their own beliefs. We model this phenomenon by introducing a learning-theoretic framework: Online Learning in the Replay Setting. In round $t$, the learner outputs a hypothesis $\hat{h}_t$; the adversary then reveals either the true label $f^\ast(x_t)$ or a replayed label $\hat{h}_i(x_t)$ from an earlier round $i < t$. A mistake is counted only when the true label is shown, yet classical algorithms such as the SOA or the halving algorithm are easily misled by the replayed errors. We introduce the Extended Threshold dimension, $\mathrm{ExThD}(\mathcal{H})$, and prove matching upper and lower bounds that make $\mathrm{ExThD}(\mathcal{H})$ the exact measure of learnability in this model. A closure-based learner makes at most $\mathrm{ExThD}(\mathcal{H})$ mistakes against any adaptive adversary, and no algorithm can perform better. For stochastic adversaries, we prove a similar bound for every intersection-closed class. The replay setting is provably harder than the classical mistake bound setting: some classes have constant Littlestone dimension but arbitrarily large $\mathrm{ExThD}(\mathcal{H})$. Proper learning exhibits an even sharper separation: a class is properly learnable under replay if and only if it is (almost) intersection-closed. Otherwise, every proper learner suffers $\Omega(T)$ errors, whereas our improper algorithm still achieves the $\mathrm{ExThD}(\mathcal{H})$ bound. These results give the first tight analysis of learning against replay adversaries, based on new results for closure-type algorithms.
• Abstract（参考訳）: 機械学習システムは、自己アノテートされたデータをますます訓練するので、エラーを補強し、自分たちの信念の反響室になるリスクがある。 我々はこの現象を,リプレイ設定におけるオンライン学習という学習理論の枠組みを導入することによってモデル化する。 ラウンド $t$ では、学習者は仮説 $\hat{h}_t$ を出力し、真ラベル $f^\ast(x_t)$ または再生ラベル $\hat{h}_i(x_t)$ を以前のラウンド $i < t$ から出力する。 しかし、SOAや半減期アルゴリズムのような古典的なアルゴリズムは、リプレイされたエラーによって容易に誤解される。 拡張Threshold次元、$\mathrm{ExThD}(\mathcal{H})$を導入し、$\mathrm{ExThD}(\mathcal{H})$をこのモデルにおける学習可能性の正確な測度で表す上限と下限の整合性を証明する。 クロージャベースの学習者は、任意の適応的敵に対して少なくとも$\mathrm{ExThD}(\mathcal{H})$ミスを犯す。 確率的逆数に対しては、すべての交叉閉クラスに対して同様の境界が証明される。 リプレイ設定は古典的なミスバウンド設定よりも明らかに難しい: あるクラスは定数のリトルストーン次元を持つが、任意に大きな$\mathrm{ExThD}(\mathcal{H})$を持つ。 適切な学習はよりシャープな分離を示し、クラスが(ほぼ)交叉閉ざされた場合にのみ、リプレイの下で適切に学習可能である。 そうでなければ、すべての固有学習者は$\Omega(T)$エラーを被るが、我々の不適切なアルゴリズムは$\mathrm{ExThD}(\mathcal{H})$バウンドを達成する。 これらの結果から, 閉鎖型アルゴリズムの新しい結果に基づいて, 対戦相手に対する学習の厳密な分析を行うことができた。

関連論文リスト

• Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games [1.9161424760743742]
  平均報酬RL設定のためのオンラインモデル選択アルゴリズムを提案する。 モデル選択の追加コストは、モデルクラスの数である$M$でのみ線形にスケールすることを示す。 また,学習者の後悔度を低く抑えることで,$m*$への指数的依存が避けられないことを示す。
  論文  参考訳（メタデータ） (2024-11-09T05:03:10Z)
• Online Learning of Halfspaces with Massart Noise [47.71073318490341]
  我々はMassartノイズの存在下でのオンライン学習の課題について検討する。 計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。 我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-05-21T17:31:10Z)
• Simple online learning with consistent oracle [55.43220407902113]
  オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
  論文  参考訳（メタデータ） (2023-08-15T21:50:40Z)
• On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
  本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。 注目すべきは,上界が決定論的学習者によって達成できることである。
  論文  参考訳（メタデータ） (2022-10-06T06:49:48Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games [36.969021834291745]
  本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。 この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。 実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
  論文  参考訳（メタデータ） (2021-11-17T05:24:21Z)
• Littlestone Classes are Privately Online Learnable [28.04975353867202]
  プライバシー制約下でのオンライン分類の問題点を考察する。 この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。 学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
  論文  参考訳（メタデータ） (2021-06-25T09:08:33Z)

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

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