論文の概要: Replicable Online Learning

• arxiv url: http://arxiv.org/abs/2411.13730v1
• Date: Wed, 20 Nov 2024 22:10:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-22 15:18:37.997188
• Title: Replicable Online Learning
• Title（参考訳）: Replicable Online Learning
• Authors: Saba Ahmadi, Siddharth Bhandari, Avrim Blum,
• Abstract要約: 本稿では,Impagliazzo と Ghazi が導入したアルゴリズム的複製性の概念について考察する。 本モデルでは,オンライン学習者が受信した入力シーケンスを,相手が選択した時間変化分布から生成する。 我々の目的は、2つの独立したサンプル入力シーケンス上で実行される場合、高い確率で全く同じ動作列を生成する、低レベルのオンラインアルゴリズムを設計することである。
• 参考スコア（独自算出の注目度）: 12.14234796585091
• License:
• Abstract: We investigate the concept of algorithmic replicability introduced by Impagliazzo et al. 2022, Ghazi et al. 2021, Ahn et al. 2024 in an online setting. In our model, the input sequence received by the online learner is generated from time-varying distributions chosen by an adversary (obliviously). Our objective is to design low-regret online algorithms that, with high probability, produce the exact same sequence of actions when run on two independently sampled input sequences generated as described above. We refer to such algorithms as adversarially replicable. Previous works (such as Esfandiari et al. 2022) explored replicability in the online setting under inputs generated independently from a fixed distribution; we term this notion as iid-replicability. Our model generalizes to capture both adversarial and iid input sequences, as well as their mixtures, which can be modeled by setting certain distributions as point-masses. We demonstrate adversarially replicable online learning algorithms for online linear optimization and the experts problem that achieve sub-linear regret. Additionally, we propose a general framework for converting an online learner into an adversarially replicable one within our setting, bounding the new regret in terms of the original algorithm's regret. We also present a nearly optimal (in terms of regret) iid-replicable online algorithm for the experts problem, highlighting the distinction between the iid and adversarial notions of replicability. Finally, we establish lower bounds on the regret (in terms of the replicability parameter and time) that any replicable online algorithm must incur.
• Abstract（参考訳）: 我々は,Impagliazzo et al 2022,Ghazi et al 2021,Ahn et al 2024によって導入されたアルゴリズム的複製性の概念をオンライン環境で検証する。 本モデルでは,オンライン学習者が受信した入力シーケンスを,相手が選択した時間変化分布から生成する。 我々の目的は、高確率で、前述した2つの独立したサンプル入力シーケンス上で実行された場合、全く同じ動作列を生成する、低レベルのオンラインアルゴリズムを設計することである。 逆複製可能なようなアルゴリズムを参照する。 以前の研究(Esfandiari et al 2022)では、固定分布から独立して生成された入力の下でのオンライン設定の複製性について検討した。 本モデルでは, 逆数列, iid 入力列, およびそれらの混合物を解析し, 特定の分布を点質量としてモデル化する。 我々は、オンライン線形最適化のための逆複製可能なオンライン学習アルゴリズムと、サブ線形後悔を実現する専門家の問題を実証する。 さらに,オンライン学習者から逆複製的な学習者へ変換する汎用フレームワークを提案する。 また, 専門家問題に対して, iid-replicableオンラインアルゴリズムをほぼ最適に提案し, iid と逆の再現性の概念の区別を強調した。 最後に、あらゆるレプリカブルオンラインアルゴリズムが生み出すべき後悔(複製性パラメータと時間の観点から)の限界を低くする。

関連論文リスト

• On the Computational Landscape of Replicable Learning [40.274579987732416]
  本稿では,Impagliazzo,Lei,Pitassi,Sorrellによって導入された安定性の概念である,アルゴリズム的複製性の計算的側面について考察する。 複製可能性と他の学習可能性の概念との強い統計的つながりを築き上げた最近の研究に動機づけられた我々は、複製可能性とこれらの学習パラダイムの間の計算的つながりをよりよく理解することを目指している。
  論文  参考訳（メタデータ） (2024-05-24T14:30:40Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• A Batch-to-Online Transformation under Random-Order Model [23.817140289575377]
  本稿では,オンラインアルゴリズムの開発に利用可能な変換フレームワークについて紹介する。 オンライン$(k,z)$-clustering,オンライン行列近似,オンライン回帰など,さまざまな問題に適用する。 われわれのアルゴリズムは、一部のオンラインアプリケーションで望まれる低整合性も享受している。
  論文  参考訳（メタデータ） (2023-06-12T14:50:21Z)
• Replicable Reinforcement Learning [15.857503103543308]
  本稿では、並列値反復のための証明可能なレプリカブルアルゴリズムと、エピソード設定における証明可能なR-maxのレプリカブルバージョンを提供する。 これらは制御問題に対する最初の公式なレプリカ化結果であり、バッチ学習設定とは異なるレプリケーションの課題を提示している。
  論文  参考訳（メタデータ） (2023-05-24T16:05:15Z)
• Online Regenerative Learning [0.0]
  入力による目的関数を最大化するオンライン線形プログラミング(OLP)問題について検討する。 このタイプの OLP を解析する様々なアルゴリズムの性能は、入力が i.i.d 分布に従うとよく研究される。
  論文  参考訳（メタデータ） (2022-09-18T21:04:56Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Discovering Non-monotonic Autoregressive Orderings with Variational Inference [67.27561153666211]
  我々は、訓練データから高品質な生成順序を純粋に検出する、教師なし並列化可能な学習装置を開発した。 エンコーダを非因果的注意を持つトランスフォーマーとして実装し、1つのフォワードパスで置換を出力する。 言語モデリングタスクにおける経験的結果から,我々の手法は文脈認識であり,一定の順序と競合する,あるいはより優れた順序を見つけることができる。
  論文  参考訳（メタデータ） (2021-10-27T16:08:09Z)
• Online Adversarial Attacks [57.448101834579624]
  我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。 まず、オンライン脅威モデルの決定論的変種を厳格に分析する。 このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
  論文  参考訳（メタデータ） (2021-03-02T20:36:04Z)
• Active Online Learning with Hidden Shifting Domains [64.75186088512034]
  本稿では,その後悔度とラベルクエリ数とを適応的にバランスさせる,驚くほど単純なアルゴリズムを提案する。 我々のアルゴリズムは、異なる領域からの入力のインターリービングスパンを適応的に処理できる。
  論文  参考訳（メタデータ） (2020-06-25T15:23:59Z)
• Competitive Mirror Descent [67.31015611281225]
  制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。 本稿では, 競合ミラー降下法(CMD)を提案する。 特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
  論文  参考訳（メタデータ） (2020-06-17T22:11:35Z)
• A Modern Introduction to Online Learning [15.974402990630402]
  オンライン学習(オンライン学習)とは、最悪の場合における後悔の最小化の枠組みを指す。 凸損失を伴うオンライン学習のための一階と二階のアルゴリズムを提示する。
  論文  参考訳（メタデータ） (2019-12-31T08:16:31Z)

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

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