論文の概要: Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regret

• arxiv url: http://arxiv.org/abs/2306.03372v3
• Date: Tue, 22 Oct 2024 14:24:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-23 14:26:19.869487
• Title: Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regret
• Title（参考訳）: オンラインテンソル学習:計算と統計のトレードオフ、適応性と最適回帰
• Authors: Jingyang Li, Jian-Feng Cai, Yang Chen, Dong Xia,
• Abstract要約: oRGradはテンソル学習のためのオンラインアルゴリズムで、計算効率が高く、メモリ消費がはるかに少なく、シーケンシャルに到着したデータを処理できる。 我々は、oRGradが太陽F10.7指数の予測においてオフラインよりも著しく優れていることを示した。
• 参考スコア（独自算出の注目度）: 19.480538520915175
• License:
• Abstract: Large tensor learning algorithms are typically computationally expensive and require storing a vast amount of data. In this paper, we propose a unified online Riemannian gradient descent (oRGrad) algorithm for tensor learning, which is computationally efficient, consumes much less memory, and can handle sequentially arriving data while making timely predictions. The algorithm is applicable to both linear and generalized linear models. If the time horizon T is known, oRGrad achieves statistical optimality by choosing an appropriate fixed step size. We find that noisy tensor completion particularly benefits from online algorithms by avoiding the trimming procedure and ensuring sharp entry-wise statistical error, which is often technically challenging for offline methods. The regret of oRGrad is analyzed, revealing a fascinating trilemma concerning the computational convergence rate, statistical error, and regret bound. By selecting an appropriate constant step size, oRGrad achieves an $O(T^{1/2})$ regret. We then introduce the adaptive-oRGrad algorithm, which can achieve the optimal $O(\log T)$ regret by adaptively selecting step sizes, regardless of whether the time horizon is known. The adaptive-oRGrad algorithm can attain a statistically optimal error rate without knowing the horizon. Comprehensive numerical simulations corroborate our theoretical findings. We show that oRGrad significantly outperforms its offline counterpart in predicting the solar F10.7 index with tensor predictors that monitor space weather impacts.
• Abstract（参考訳）: 大規模なテンソル学習アルゴリズムは通常計算コストが高く、大量のデータを格納する必要がある。 本稿では,テンソル学習のためのオンラインリーマン勾配降下アルゴリズム(oRGrad)を提案する。 このアルゴリズムは線形モデルと一般化線形モデルの両方に適用できる。 時間地平線Tが知られている場合、oRGradは適切な固定ステップサイズを選択して統計的最適性を達成する。 ノイズの多いテンソル補完は、トリミング手順を回避し、鋭い進入度統計誤差を確実にすることで、特にオンラインアルゴリズムの恩恵を受ける。 oRGradの後悔は解析され、計算収束率、統計誤差、後悔境界に関する興味深いトリレンマが明らかになった。 適切な定数ステップサイズを選択することで、oRGrad は $O(T^{1/2})$ regret を達成する。 次に、時間的地平線が知られているかどうかに関わらず、ステップサイズを適応的に選択することで、最適な$O(\log T)$ regretを実現できるアダプティブ-oRGradアルゴリズムを導入する。 適応-oRGradアルゴリズムは水平線を知らずに統計的に最適な誤差率が得られる。 総合的な数値シミュレーションは我々の理論的な結果を裏付ける。 我々は、oRGradが、太陽のF10.7指数を宇宙気象の影響を観測するテンソル予測器で予測する際、オフラインよりも著しく優れていることを示した。

関連論文リスト

• Approximating Metric Magnitude of Point Sets [4.522729058300309]
  計量等級は、多くの望ましい幾何学的性質を持つ点雲の「大きさ」の尺度である。 様々な数学的文脈に適応しており、最近の研究は機械学習と最適化アルゴリズムを強化することを示唆している。 本稿では, 等級問題について検討し, 効率よく近似する方法を示し, 凸最適化問題として扱うことができるが, 部分モジュラ最適化としては適用できないことを示す。 本稿では,高速に収束し精度の高い反復近似アルゴリズムと,計算をより高速に行うサブセット選択法という,2つの新しいアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2024-09-06T17:15:28Z)
• Low-rank extended Kalman filtering for online learning of neural networks from streaming data [71.97861600347959]
  非定常データストリームから非線形関数のパラメータを推定するための効率的なオンライン近似ベイズ推定アルゴリズムを提案する。 この方法は拡張カルマンフィルタ (EKF) に基づいているが、新しい低ランク+斜角行列分解法を用いている。 変分推論に基づく手法とは対照的に,本手法は完全に決定論的であり,ステップサイズチューニングを必要としない。
  論文  参考訳（メタデータ） (2023-05-31T03:48:49Z)
• One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares [8.443742714362521]
  我々は,従来のデータポイントの予測にほとんど変化しない方向にパラメータを変更しながら,すべての新しいデータポイントに完全に適合するワンパス学習アルゴリズムを開発した。 我々のアルゴリズムは、インクリメンタル・プリンシパル・コンポーネント分析(IPCA)を用いてストリーミングデータの構造を利用して、メモリを効率的に利用する。 本実験では,提案手法の有効性をベースラインと比較した。
  論文  参考訳（メタデータ） (2022-07-28T02:01:31Z)
• Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization [44.54772242784423]
  低ランク学習行列に対する効率的な非正規化アルゴリズムを開発した。 提案アルゴリズムは、高価な折り畳み/折り畳み問題を回避することができる。 実験の結果,提案アルゴリズムは既存の状態よりも効率的で空間が広いことがわかった。
  論文  参考訳（メタデータ） (2022-05-06T07:47:10Z)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。 そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。 後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
  論文  参考訳（メタデータ） (2022-03-19T13:39:49Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More [7.484063729015126]
  最適輸送のためのコスト行列の2つの効率的な対数線形時間近似を提案する。 これらの近似は、複雑な高次元空間に対してもよく機能するエントロピー規則化OTに対する一般的な対数線形時間アルゴリズムを可能にする。 グラフ距離回帰のために,グラフニューラルネットワーク(GNN)と拡張シンクホーンを組み合わせたグラフトランスポートネットワーク(GTN)を提案する。
  論文  参考訳（メタデータ） (2021-07-14T17:40:08Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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