論文の概要: Online Tensor Learning: Computational and Statistical Trade-offs,
Adaptivity and Optimal Regret
- arxiv url: http://arxiv.org/abs/2306.03372v2
- Date: Mon, 10 Jul 2023 05:51:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-13 19:09:15.681176
- Title: Online Tensor Learning: Computational and Statistical Trade-offs,
Adaptivity and Optimal Regret
- Title（参考訳）: オンラインテンソル学習:計算と統計のトレードオフ、適応性と最適後悔
- Authors: Jian-Feng Cai, Jingyang Li and Dong Xia
- Abstract要約: 本稿では,線形モデルと一般化線形モデルの両方を包含したオンライン環境下での潜在低ランクテンソル推定フレームワークについて検討する。
また、オンラインテンソル補完とオンラインバイナリテンソル学習という2つの特定の応用についても検討する。
特に、我々の研究は、オンライン低ランクテンソルリカバリタスクにノイズを組み込む最初の試みである。
- 参考スコア（独自算出の注目度）: 17.29570708667132
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate a generalized framework for estimating latent low-rank tensors
in an online setting, encompassing both linear and generalized linear models.
This framework offers a flexible approach for handling continuous or
categorical variables. Additionally, we investigate two specific applications:
online tensor completion and online binary tensor learning. To address these
challenges, we propose the online Riemannian gradient descent algorithm, which
demonstrates linear convergence and the ability to recover the low-rank
component under appropriate conditions in all applications. Furthermore, we
establish a precise entry-wise error bound for online tensor completion.
Notably, our work represents the first attempt to incorporate noise in the
online low-rank tensor recovery task. Intriguingly, we observe a surprising
trade-off between computational and statistical aspects in the presence of
noise. Increasing the step size accelerates convergence but leads to higher
statistical error, whereas a smaller step size yields a statistically optimal
estimator at the expense of slower convergence. Moreover, we conduct regret
analysis for online tensor regression. Under the fixed step size regime, a
fascinating trilemma concerning the convergence rate, statistical error rate,
and regret is observed. With an optimal choice of step size we achieve an
optimal regret of $O(\sqrt{T})$. Furthermore, we extend our analysis to the
adaptive setting where the horizon T is unknown. In this case, we demonstrate
that by employing different step sizes, we can attain a statistically optimal
error rate along with a regret of $O(\log T)$. To validate our theoretical
claims, we provide numerical results that corroborate our findings and support
our assertions.
- Abstract（参考訳）: オンライン環境での潜在低ランクテンソル推定のための一般化フレームワークについて検討し,線形モデルと一般化線形モデルの両方を包含する。
このフレームワークは、連続変数や分類変数を扱うための柔軟なアプローチを提供する。
さらに、オンラインテンソル補完とオンラインバイナリテンソル学習の2つの応用について検討する。
これらの課題に対処するために、線形収束と低ランク成分を全てのアプリケーションで適切な条件下で回復する能力を示すオンラインリーマン勾配降下アルゴリズムを提案する。
さらに,オンラインテンソル完備化のための正確なエントリワイド誤差を確立する。
特に、我々の研究は、オンライン低ランクテンソルリカバリタスクにノイズを組み込む最初の試みである。
興味深いことに、ノイズの存在における計算的側面と統計的側面の間の驚くべきトレードオフを観察する。
ステップサイズの増加は収束を加速するが、より小さなステップサイズでは収束が遅くなり、統計的に最適な推定器となる。
さらに,オンラインテンソル回帰に対する後悔分析を行った。
固定ステップサイズでは,収束率,統計誤差率,後悔に関する興味深いトリレンマが観察された。
ステップサイズを最適に選択することで、$O(\sqrt{T})$を最適に後悔する。
さらに、この解析を水平線Tが未知な適応的な設定にまで拡張する。
この場合、異なるステップサイズを使用することで、統計的に最適のエラー率を達成でき、後悔は$o(\log t)$であることが示される。
理論的な主張を検証するために、我々の発見を裏付ける数値結果を提供し、我々の主張を支持する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。