論文の概要: Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery
- arxiv url: http://arxiv.org/abs/2401.02592v2
- Date: Sat, 21 Dec 2024 07:55:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-24 15:53:10.027000
- Title: Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery
- Title(参考訳): テンソルトレイン回復のための非凸因子化法
- Authors: Zhen Qin, Michael B. Wakin, Zhihui Zhu,
- Abstract要約: 因子化アプローチに対する最初の収束保証を提供する。
いわゆる左直交TTフォーマットを最適化する。
我々はRGDが線形速度で基底真理を確実に回復できることを証明した。
- 参考スコア(独自算出の注目度): 30.876260188209105
- License:
- Abstract: In this paper, we provide the first convergence guarantee for the factorization approach. Specifically, to avoid the scaling ambiguity and to facilitate theoretical analysis, we optimize over the so-called left-orthogonal TT format which enforces orthonormality among most of the factors. To ensure the orthonormal structure, we utilize the Riemannian gradient descent (RGD) for optimizing those factors over the Stiefel manifold. We first delve into the TT factorization problem and establish the local linear convergence of RGD. Notably, the rate of convergence only experiences a linear decline as the tensor order increases. We then study the sensing problem that aims to recover a TT format tensor from linear measurements. Assuming the sensing operator satisfies the restricted isometry property (RIP), we show that with a proper initialization, which could be obtained through spectral initialization, RGD also converges to the ground-truth tensor at a linear rate. Furthermore, we expand our analysis to encompass scenarios involving Gaussian noise in the measurements. We prove that RGD can reliably recover the ground truth at a linear rate, with the recovery error exhibiting only polynomial growth in relation to the tensor order. We conduct various experiments to validate our theoretical findings.
- Abstract(参考訳): 本稿では、因子化アプローチに対する最初の収束保証を提供する。
具体的には、スケーリングの曖昧さを回避し、理論的解析を容易にするため、ほとんどの要因の正則性を強制するいわゆる左直交TTフォーマットを最適化する。
正則構造を保証するために、リーマン勾配降下(RGD)を用いてスティーフェル多様体上のこれらの因子を最適化する。
まず、TT分解問題を掘り下げ、RGDの局所線型収束を確立する。
特に、収束速度はテンソル次数が増加するにつれて線形減少しか生じない。
次に,線形測定からTTフォーマットテンソルを復元することを目的としたセンサ問題について検討する。
検出作用素が制限等尺性(RIP)を満たすと仮定すると、スペクトル初期化によって得られる適切な初期化により、RGDは線形速度で接地トラステンソルに収束する。
さらに、計測におけるガウス雑音を含むシナリオを包含するように分析を拡張した。
RGD が線形速度で基底真理を確実に回復できることを証明し、その回復誤差はテンソル次数に関して多項式成長のみを示す。
我々は理論的な結果を検証するために様々な実験を行った。
関連論文リスト
- 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) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳(メタデータ) (2023-06-29T01:20:44Z) - The Inductive Bias of Flatness Regularization for Deep Matrix
Factorization [58.851514333119255]
この研究は、ディープ線形ネットワークにおけるヘッセン解の最小トレースの帰納バイアスを理解するための第一歩となる。
測定値の標準等尺性(RIP)が1より大きいすべての深さについて、ヘッセンのトレースを最小化することは、対応する終端行列パラメータのシャッテン 1-ノルムを最小化するのとほぼ同値であることを示す。
論文 参考訳(メタデータ) (2023-06-22T23:14:57Z) - 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) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation
from Incomplete Measurements [30.395874385570007]
基本的な課題は、高度に不完全な測定からテンソルを忠実に回収することである。
タッカー分解におけるテンソル因子を直接回復するアルゴリズムを開発した。
2つの正準問題に対する基底真理テンソルの線形独立率で確実に収束することを示す。
論文 参考訳(メタデータ) (2021-04-29T17:44:49Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳(メタデータ) (2021-03-23T17:15:53Z) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。
暗黙正則化現象の理論的保証を提供する。
論文 参考訳(メタデータ) (2020-07-16T13:27:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。