論文の概要: Better Rates for Random Task Orderings in Continual Linear Models

• arxiv url: http://arxiv.org/abs/2504.04579v1
• Date: Sun, 06 Apr 2025 18:39:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-08 14:14:50.494868
• Title: Better Rates for Random Task Orderings in Continual Linear Models
• Title（参考訳）: 連続線形モデルにおけるランダムタスク順序付けの高速化
• Authors: Itay Evron, Ran Levinstein, Matan Schliserman, Uri Sherman, Tomer Koren, Daniel Soudry, Nathan Srebro,
• Abstract要約: 以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。 実現可能な最小二乗の設定において、新しい最期境界を開発し、それらを連続学習に応用する。 タスクを繰り返しないランダム化だけで、十分に長いタスクで破滅的な忘れを防げることが、初めて証明された。
• 参考スコア（独自算出の注目度）: 50.11453013647086
• License:
• Abstract: We study the common continual learning setup where an overparameterized model is sequentially fitted to a set of jointly realizable tasks. We analyze the forgetting, i.e., loss on previously seen tasks, after $k$ iterations. For linear models, we prove that fitting a task is equivalent to a single stochastic gradient descent (SGD) step on a modified objective. We develop novel last-iterate SGD upper bounds in the realizable least squares setup, and apply them to derive new results for continual learning. Focusing on random orderings over $T$ tasks, we establish universal forgetting rates, whereas existing rates depend on the problem dimensionality or complexity. Specifically, in continual regression with replacement, we improve the best existing rate from $O((d-r)/k)$ to $O(\min(k^{-1/4}, \sqrt{d-r}/k, \sqrt{Tr}/k))$, where $d$ is the dimensionality and $r$ the average task rank. Furthermore, we establish the first rates for random task orderings without replacement. The obtained rate of $O(\min(T^{-1/4}, (d-r)/T))$ proves for the first time that randomization alone, with no task repetition, can prevent catastrophic forgetting in sufficiently long task sequences. Finally, we prove a similar $O(k^{-1/4})$ universal rate for the forgetting in continual linear classification on separable data. Our universal rates apply for broader projection methods, such as block Kaczmarz and POCS, illuminating their loss convergence under i.i.d and one-pass orderings.
• Abstract（参考訳）: 本研究では,過パラメータ化モデルが協調実現可能な一連のタスクに順次適合する共通連続学習装置について検討する。 以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。 線形モデルの場合、タスクのフィッティングは修正対象上の1つの確率勾配勾配(SGD)ステップと等価であることを示す。 実現可能な最小二乗構成において, 新たな最上級SGD上限を開発し, 連続学習に新たな結果を導出する。 T$のタスクに対するランダムな順序付けに焦点をあてて、我々は普遍的な忘れる率を確立する一方、既存のレートは問題次元や複雑性に依存する。 具体的には、置換を伴う連続回帰において、$O((d-r)/k)$から$O(\min(k^{-1/4}, \sqrt{d-r}/k, \sqrt{Tr}/k))$に改善する。 さらに,代わることなくランダムなタスク順序付けを行うための第1のレートを確立する。 得られた$O(\min(T^{-1/4}, (d-r)/T)$は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスにおける破滅的な忘れを防ぐことができることを初めて証明する。 最後に、分離可能なデータに対する連続線形分類における忘れ物に対する類似の$O(k^{-1/4})$ユニバーサルレートを証明した。 我々の普遍レートは、Kaczmarz ブロックや POCS のようなより広い射影法に適用され、i.d および 1-パス順序の下でそれらの損失収束を照らす。

関連論文リスト

• Entangled Mean Estimation in High-Dimensions [36.97113089188035]
  信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。 最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
  論文  参考訳（メタデータ） (2025-01-09T18:31:35Z)
• Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way [12.331596909999764]
  マルコフ過程のレンズを通した等質化スキームについて検討する。 我々は、定段化によって導入された分散とバイアスと同様に、明示的な幾何学的および非漸近収束率を導出する。
  論文  参考訳（メタデータ） (2024-10-16T21:49:27Z)
• MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
  多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。 最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。 一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
  論文  参考訳（メタデータ） (2024-05-29T18:36:59Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。 我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-07T15:03:50Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• A No-Free-Lunch Theorem for MultiTask Learning [19.645741778058227]
  すべてのタスク$P_t$が共通の最適分類器$h*,$を共有する、一見好都合な分類シナリオを考える。 このようなレジームは、$n$と$N$の両方のミニマックスレートを許容するが、適応アルゴリズムは存在しない。
  論文  参考訳（メタデータ） (2020-06-29T03:03:29Z)

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

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