論文の概要: Online Learning in the Random Order Model

• arxiv url: http://arxiv.org/abs/2510.02820v1
• Date: Fri, 03 Oct 2025 08:53:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-06 16:35:52.321778
• Title: Online Learning in the Random Order Model
• Title（参考訳）: ランダム秩序モデルにおけるオンライン学習
• Authors: Martino Bernasconi, Andrea Celli, Riccardo Colini-Baldeschi, Federico Fusco, Stefano Leonardi, Matteo Russo,
• Abstract要約: ランダム順序入力は非定常性を示すことができ、学習アルゴリズムの性能を損なう可能性がある。 本稿では,学習アルゴリズムをランダム順序モデルに適応させるテンプレートを提案する。 また、オンライン分類を調査し、ランダムな順序で学習性はリトルストーン次元ではなくVC次元によって特徴づけられることを証明した。
• 参考スコア（独自算出の注目度）: 23.441342985145297
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the random-order model for online learning, the sequence of losses is chosen upfront by an adversary and presented to the learner after a random permutation. Any random-order input is \emph{asymptotically} equivalent to a stochastic i.i.d. one, but, for finite times, it may exhibit significant {\em non-stationarity}, which can hinder the performance of stochastic learning algorithms. While algorithms for adversarial inputs naturally maintain their regret guarantees in random order, simple no-regret algorithms exist for the stochastic model that fail against random-order instances. In this paper, we propose a general template to adapt stochastic learning algorithms to the random-order model without substantially affecting their regret guarantees. This allows us to recover improved regret bounds for prediction with delays, online learning with constraints, and bandits with switching costs. Finally, we investigate online classification and prove that, in random order, learnability is characterized by the VC dimension rather than the Littlestone dimension, thus providing a further separation from the general adversarial model.
• Abstract（参考訳）: オンライン学習におけるランダム順序モデルでは、損失の列は相手によって前もって選択され、ランダムな置換後に学習者に提示される。 任意のランダム順序入力は、確率的 i.d. と同値であるが、有限時間の間は、確率的学習アルゴリズムのパフォーマンスを妨げる重要な {\em non-stationarity} を示すことがある。 逆数入力のアルゴリズムは自然に不運な保証をランダムな順序で維持するが、ランダムな順序インスタンスに対して失敗する確率的モデルには単純な非回帰アルゴリズムが存在する。 本稿では,確率論的学習アルゴリズムをランダム順序モデルに適用するための一般的なテンプレートを提案する。 これにより、遅延による予測、制約によるオンライン学習、スイッチングコストによる帯域幅に関する改善された後悔境界を回復することが可能になります。 最後に、オンライン分類を調査し、ランダムな順序で学習可能性がリトルストーン次元よりもVC次元によって特徴づけられることを証明した。

関連論文リスト

• Semi-Bandit Learning for Monotone Stochastic Optimization [16.921694787482213]
  一般的なオンライン学習アルゴリズムは「モノトーン」問題のクラスのために開発されている。 当社のフレームワークは,預言不平等やPandoraのボックス,単一リソースの収益管理,ポスト価格など,いくつかの基本的な問題に適用しています。
  論文  参考訳（メタデータ） (2023-12-24T07:46:37Z)
• Arbitrarily Large Labelled Random Satisfiability Formulas for Machine Learning Training [5.414308305392762]
  決定問題を解くことなく、任意の大きさのランダムな式を正しくラベル付けする方法を示す。 我々は1万変数の式で満足度を予測するタスクのために、既存の最先端モデルを訓練する。 同じデータセットで99%をランダムに推測するのに勝るものは見当たらない。
  論文  参考訳（メタデータ） (2022-11-21T17:52:13Z)
• A Non-monotonic Self-terminating Language Model [62.93465126911921]
  本稿では,不完全復号アルゴリズムによる非終端列の問題に焦点をあてる。 まず、グリーディ探索、トップ$kのサンプリング、核サンプリングを含む不完全確率復号アルゴリズムを定義する。 次に,単調な終端確率の制約を緩和する非単調な自己終端言語モデルを提案する。
  論文  参考訳（メタデータ） (2022-10-03T00:28:44Z)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。 そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。 後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
  論文  参考訳（メタデータ） (2022-03-19T13:39:49Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。 ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。 本稿では,FTRLに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-28T08:25:26Z)
• Discovering Non-monotonic Autoregressive Orderings with Variational Inference [67.27561153666211]
  我々は、訓練データから高品質な生成順序を純粋に検出する、教師なし並列化可能な学習装置を開発した。 エンコーダを非因果的注意を持つトランスフォーマーとして実装し、1つのフォワードパスで置換を出力する。 言語モデリングタスクにおける経験的結果から,我々の手法は文脈認識であり,一定の順序と競合する,あるいはより優れた順序を見つけることができる。
  論文  参考訳（メタデータ） (2021-10-27T16:08:09Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。 1次保証は統計的およびオンライン学習において比較的よく理解されている。 三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
  論文  参考訳（メタデータ） (2021-07-05T19:20:34Z)
• Towards Costless Model Selection in Contextual Bandits: A Bias-Variance Perspective [7.318831153179727]
  文脈的包帯設定における累積的後悔最小化のための同様の保証の実現可能性について検討した。 提案アルゴリズムは, 新たな不特定性テストに基づいており, モデル選択による報酬推定の利点を実証する。
  論文  参考訳（メタデータ） (2021-06-11T16:08:03Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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