論文の概要: Generalization Bounds for Dependent Data using Online-to-Batch Conversion
- arxiv url: http://arxiv.org/abs/2405.13666v2
- Date: Wed, 19 Feb 2025 13:27:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-20 13:56:02.730950
- Title: Generalization Bounds for Dependent Data using Online-to-Batch Conversion
- Title(参考訳): オンライン・バッチ変換を用いた依存データに対する一般化境界
- Authors: Sagnik Chatterjee, Manuj Mukherjee, Alhad Sethi,
- Abstract要約: 混合プロセスから抽出したサンプルに基づいて学習したバッチ学習アルゴリズムの一般化誤差を上限とする。
私たちの仕事は、バッチ学習者に対する安定性の仮定を一切必要としません。
我々は、オンライン学習アルゴリズムの教科書ファミリーであるEWAアルゴリズムが、我々の新しい安定性の概念を満たすことを証明した。
- 参考スコア(独自算出の注目度): 0.6144680854063935
- License:
- Abstract: In this work, we upper bound the generalization error of batch learning algorithms trained on samples drawn from a mixing stochastic process (i.e., a dependent data source) both in expectation and with high probability. Unlike previous results by Mohri et al. (2010) and Fu et al. (2023), our work does not require any stability assumptions on the batch learner, which allows us to derive upper bounds for any batch learning algorithm trained on dependent data. This is made possible due to our use of the Online-to-Batch ( OTB ) conversion framework, which allows us to shift the burden of stability from the batch learner to an artificially constructed online learner. We show that our bounds are equal to the bounds in the i.i.d. setting up to a term that depends on the decay rate of the underlying mixing stochastic process. Central to our analysis is a new notion of algorithmic stability for online learning algorithms based on Wasserstein distances of order one. Furthermore, we prove that the EWA algorithm, a textbook family of online learning algorithms, satisfies our new notion of stability. Following this, we instantiate our bounds using the EWA algorithm.
- Abstract(参考訳): 本研究では,混合確率過程(すなわち,依存データ源)から抽出したサンプルに基づいて学習したバッチ学習アルゴリズムの一般化誤差を期待値と高い確率で上限とする。
Mohri et al (2010) と Fu et al (2023) の以前の結果とは異なり、我々の研究はバッチ学習者に対する安定性の仮定を一切必要とせず、従属データに基づいて訓練されたバッチ学習アルゴリズムの上限を導出することができる。
バッチ学習者から人工的に構築されたオンライン学習者へ安定性の重荷を移すことができる。
我々は、我々の境界が、基礎となる混合確率過程の崩壊率に依存する項に設定する i.d. の境界と等しいことを示す。
我々の分析の中心は、注文1のワッサーシュタイン距離に基づくオンライン学習アルゴリズムのアルゴリズム安定性の新しい概念である。
さらに、オンライン学習アルゴリズムの教科書ファミリーであるEWAアルゴリズムが、我々の新しい安定性の概念を満たすことを証明した。
次に、EWAアルゴリズムを用いて境界をインスタンス化する。
関連論文リスト
- Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective [9.867914513513453]
そこで本研究では,従来の研究よりも高い一般化率で低損失境界を達成できるオラクル効率のアルゴリズムを提案する。
また,この分離条件下では,最適な学習率が得られる差分プライベート学習の変種も提示する。
論文 参考訳(メタデータ) (2025-02-14T16:52:50Z) - Data-dependent and Oracle Bounds on Forgetting in Continual Learning [7.903539618132858]
継続的な学習では、知識はタスク間で保存され、再利用されなければならない。
モデルとアルゴリズムの選択に関係なく適用可能な,データ依存およびオラクル上界の両方を提供する。
提案手法は,いくつかの連続的な学習問題に対して,学習を忘れることに厳密な制約を課すことを実証的に証明する。
論文 参考訳(メタデータ) (2024-06-13T17:50:51Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳(メタデータ) (2022-02-09T19:22:34Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳(メタデータ) (2021-11-23T18:10:48Z) - A Boosting Approach to Reinforcement Learning [59.46285581748018]
複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。
このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
論文 参考訳(メタデータ) (2021-08-22T16:00:45Z) - Learning Expected Emphatic Traces for Deep RL [32.984880782688535]
オフポリシーサンプリングと経験リプレイは、サンプル効率を改善し、モデルフリーの時間差学習手法をスケールするための鍵となる。
リプレイと組み合わせることができるマルチステップ強調重み付けと、必要な強調重み付けを学習するための時間反転TD学習アルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-07-12T13:14:03Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳(メタデータ) (2021-03-02T11:04:33Z) - Batch Value-function Approximation with Only Realizability [17.692408242465763]
バッチ強化学習(RL):探索データセットからQstar$を学習する。
我々のアルゴリズムであるBVFTは、トーナメントの手順を通じて硬さ予想(探索データというより強い概念の下では)を破る。
また、BVFTが他の拡張と開問題の間のモデル選択にどのように適用できるかについても論じる。
論文 参考訳(メタデータ) (2020-08-11T20:09:37Z) - A Constraint-Based Algorithm for the Structural Learning of
Continuous-Time Bayesian Networks [70.88503833248159]
連続時間ベイズネットワークの構造を学習するための制約に基づく最初のアルゴリズムを提案する。
我々は,条件付き独立性を確立するために提案した,異なる統計的テストと基礎となる仮説について論じる。
論文 参考訳(メタデータ) (2020-07-07T07:34:09Z) - Tracking Performance of Online Stochastic Learners [57.14673504239551]
オンラインアルゴリズムは、大規模なバッチにデータを保存したり処理したりすることなく、リアルタイムで更新を計算できるため、大規模な学習環境で人気がある。
一定のステップサイズを使用すると、これらのアルゴリズムはデータやモデル特性などの問題パラメータのドリフトに適応し、適切な精度で最適解を追跡する能力を持つ。
定常仮定に基づく定常状態性能とランダムウォークモデルによるオンライン学習者の追跡性能の関連性を確立する。
論文 参考訳(メタデータ) (2020-04-04T14:16:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。