論文の概要: 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)$であることが示される。
理論的な主張を検証するために、我々の発見を裏付ける数値結果を提供し、我々の主張を支持する。
関連論文リスト
- Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decomposition [27.29463801531576]
TTに基づくToT回帰モデルの理論的およびアルゴリズム的側面について検討する。
制約付き誤差境界に対する解を効率的に見つけるための2つのアルゴリズムを提案する。
我々はIHTとRGDの両方の線形収束速度を確立する。
論文 参考訳（メタデータ） (2024-06-10T03:51:38Z) - Online Tensor Inference [0.0]
従来のオフライン学習は、各計算繰り返しにおける全てのデータの保存と利用を伴い、高次元テンソルデータには実用的ではない。
既存の低ランクテンソル法は、オンラインの方法での統計的推論能力に欠ける。
本手法では,広範囲なメモリ要求を伴わずに効率的なリアルタイムデータ処理を実現するため,グラディエント・Descent (SGD) を用いる。
論文 参考訳（メタデータ） (2023-12-28T16:37:48Z) - Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - Tensor-on-Tensor Regression: Riemannian Optimization,
Over-parameterization, Statistical-computational Gap, and Their Interplay [9.427635404752936]
テンソル・オン・テンソル回帰(tensor-on-tensor regression)について検討し、テンソル応答とテンソル共変量とをタッカー階数パラメータ/行列で結合する。
我々は、未知の階級の課題に対処する2つの方法を提案する。
一般テンソル・オン・テンソル回帰に対する最初の収束保証を提供する。
論文 参考訳（メタデータ） (2022-06-17T13:15:27Z) - Truncated tensor Schatten p-norm based approach for spatiotemporal
traffic data imputation with complicated missing patterns [77.34726150561087]
本研究は, モード駆動繊維による3症例の欠失を含む, 4症例の欠失パターンについて紹介する。
本モデルでは, 目的関数の非性にもかかわらず, 乗算器の交互データ演算法を統合することにより, 最適解を導出する。
論文 参考訳（メタデータ） (2022-05-19T08:37:56Z) - Near-optimal inference in adaptive linear regression [60.08422051718195]
最小二乗法のような単純な方法でさえ、データが適応的に収集されるときの非正規な振る舞いを示すことができる。
我々は,これらの分布異常を少なくとも2乗推定で補正するオンラインデバイアス推定器のファミリーを提案する。
我々は,マルチアームバンディット,自己回帰時系列推定,探索による能動的学習などの応用を通して,我々の理論の有用性を実証する。
論文 参考訳（メタデータ） (2021-07-05T21:05:11Z) - Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation
from Incomplete Measurements [30.395874385570007]
基本的な課題は、高度に不完全な測定からテンソルを忠実に回収することである。
タッカー分解におけるテンソル因子を直接回復するアルゴリズムを開発した。
2つの正準問題に対する基底真理テンソルの線形独立率で確実に収束することを示す。
論文 参考訳（メタデータ） (2021-04-29T17:44:49Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z) - Extrapolation for Large-batch Training in Deep Learning [72.61259487233214]
我々は、バリエーションのホストが、我々が提案する統一されたフレームワークでカバー可能であることを示す。
本稿では,この手法の収束性を証明し,ResNet,LSTM,Transformer上での経験的性能を厳格に評価する。
論文 参考訳（メタデータ） (2020-06-10T08:22:41Z) - Path Sample-Analytic Gradient Estimators for Stochastic Binary Networks [78.76880041670904]
二進的アクティベーションや二進的重みを持つニューラルネットワークでは、勾配降下によるトレーニングは複雑である。
そこで本研究では,サンプリングと解析近似を併用した新しい推定法を提案する。
勾配推定において高い精度を示し、深部畳み込みモデルにおいてより安定かつ優れた訓練を行うことを示す。
論文 参考訳（メタデータ） (2020-06-04T21:51:21Z) - Tensor denoising and completion based on ordinal observations [11.193504036335503]
我々は,不完全と思われる順序値の観測から,低ランクテンソル推定の問題を考える。
本稿では,マルチ線形累積リンクモデルを提案し,ランク制約付きM推定器を開発し,理論的精度の保証を得る。
提案した推定器は低ランクモデルのクラスにおいて最小限最適であることを示す。
論文 参考訳（メタデータ） (2020-02-16T07:09:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。