論文の概要: Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements

• arxiv url: http://arxiv.org/abs/2104.14526v1
• Date: Thu, 29 Apr 2021 17:44:49 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-30 12:40:32.321103
• Title: Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• Title（参考訳）: スケーリングとスケーラビリティ:不完全測定による非凸低ランクテンソル推定
• Authors: Tian Tong, Cong Ma, Ashley Prater-Bennette, Erin Tripp, Yuejie Chi
• Abstract要約: 基本的な課題は、高度に不完全な測定からテンソルを忠実に回収することである。 タッカー分解におけるテンソル因子を直接回復するアルゴリズムを開発した。 2つの正準問題に対する基底真理テンソルの線形独立率で確実に収束することを示す。
• 参考スコア（独自算出の注目度）: 30.395874385570007
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tensors, which provide a powerful and flexible model for representing multi-attribute data and multi-way interactions, play an indispensable role in modern data science across various fields in science and engineering. A fundamental task is to faithfully recover the tensor from highly incomplete measurements in a statistically and computationally efficient manner. Harnessing the low-rank structure of tensors in the Tucker decomposition, this paper develops a scaled gradient descent (ScaledGD) algorithm to directly recover the tensor factors with tailored spectral initializations, and shows that it provably converges at a linear rate independent of the condition number of the ground truth tensor for two canonical problems -- tensor completion and tensor regression -- as soon as the sample size is above the order of $n^{3/2}$ ignoring other dependencies, where $n$ is the dimension of the tensor. This leads to an extremely scalable approach to low-rank tensor estimation compared with prior art, which suffers from at least one of the following drawbacks: extreme sensitivity to ill-conditioning, high per-iteration costs in terms of memory and computation, or poor sample complexity guarantees. To the best of our knowledge, ScaledGD is the first algorithm that achieves near-optimal statistical and computational complexities simultaneously for low-rank tensor completion with the Tucker decomposition. Our algorithm highlights the power of appropriate preconditioning in accelerating nonconvex statistical estimation, where the iteration-varying preconditioners promote desirable invariance properties of the trajectory with respect to the underlying symmetry in low-rank tensor factorization.
• Abstract（参考訳）: マルチ属性データとマルチウェイインタラクションを表現するための強力で柔軟なモデルを提供するテンソルは、科学と工学のさまざまな分野にわたる現代のデータ科学において不可欠の役割を担っている。 基本的な課題は、テンソルを統計的かつ計算的に効率的に高度に不完全な測定から忠実に回収することである。 Harnessing the low-rank structure of tensors in the Tucker decomposition, this paper develops a scaled gradient descent (ScaledGD) algorithm to directly recover the tensor factors with tailored spectral initializations, and shows that it provably converges at a linear rate independent of the condition number of the ground truth tensor for two canonical problems -- tensor completion and tensor regression -- as soon as the sample size is above the order of $n^{3/2}$ ignoring other dependencies, where $n$ is the dimension of the tensor. これは、空調に対する過度な感度、メモリと計算における高精細化コスト、サンプルの複雑性保証の低さといった欠点の少なくとも1つに悩まされている先行技術と比較して、低ランクテンソル推定に対する非常にスケーラブルなアプローチにつながります。 我々の知る限り、ScaledGDはタッカー分解による低ランクテンソル完備化のために、ほぼ最適な統計および計算の複雑さを同時に達成する最初のアルゴリズムである。 本アルゴリズムは,非凸統計量推定を加速する上での適切な事前条件付けのパワーを強調し,低ランクテンソル因子分解の基底対称性に関して,反復変動前条件が軌道の望ましい不変性特性を促進する。

関連論文リスト

• 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)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent [22.801592340422157]
  本稿では,Burer-Monteiro法に類似した因子分解法に基づく効率的かつ効果的な低ツバルテンソル回収法を提案する。 我々は,FGDのノイズフリーおよび雑音条件下での収束を確保するために,厳密な理論的解析を行う。 提案手法は,より高速な計算速度とより小さい収束誤差の観点から,複数のシナリオにおいて優れた性能を示す。
  論文  参考訳（メタデータ） (2024-01-22T13:30:11Z)
• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization [48.65416821017865]
  この章では、スケールドグラデーション(ScaledGD)と呼ばれる新しいアルゴリズムアプローチを紹介します。 低ランク物体の条件数に依存しない定数速度で直線的に収束する。 様々なタスクに対して、勾配降下の低い摂動コストを維持できる。
  論文  参考訳（メタデータ） (2023-10-09T21:16:57Z)
• A Novel Tensor Factorization-Based Method with Robustness to Inaccurate Rank Estimation [9.058215418134209]
  本稿では,2つの低ランク制約を持つテンソルノルムを提案する。 結果のテンソル完成モデルが不正確なランク推定による性能劣化を効果的に回避できることが理論的に証明されている。 これに基づいて、最適化アルゴリズムの各イテレーションの総コストは$mathcalO(n3log n + kn3)$から$mathcalO(n4)$に削減される。
  論文  参考訳（メタデータ） (2023-05-19T06:26:18Z)
• Error Analysis of Tensor-Train Cross Approximation [88.83467216606778]
  我々は, テンソル全体の精度保証を行う。 結果は数値実験により検証され、高次テンソルに対するクロス近似の有用性に重要な意味を持つ可能性がある。
  論文  参考訳（メタデータ） (2022-07-09T19:33:59Z)
• Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descent [30.299284742925852]
  本稿では、テンソルロバスト主成分分析(RPCA)に取り組む。 希少な腐敗によって汚染された観測から低ランクのテンソルを回収することを目的としている。 提案アルゴリズムは, 最先端行列やテンソルRPCAアルゴリズムよりも, より優れた, よりスケーラブルな性能を実現する。
  論文  参考訳（メタデータ） (2022-06-18T04:01:32Z)
• 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)
• MTC: Multiresolution Tensor Completion from Partial and Coarse Observations [49.931849672492305]
  既存の完備化の定式化は、主に1つのテンソルからの部分的な観測に依存する。 この問題を解決するために,効率的なマルチレゾリューション・コンプリート・モデル(MTC)を提案する。
  論文  参考訳（メタデータ） (2021-06-14T02:20:03Z)
• Low-Rank and Sparse Enhanced Tucker Decomposition for Tensor Completion [3.498620439731324]
  テンソル完備化のために,低ランクかつスパースに拡張されたタッカー分解モデルを導入する。 我々のモデルはスパースコアテンソルを促進するためにスパース正規化項を持ち、テンソルデータ圧縮に有用である。 テンソルに出現する潜在的な周期性と固有相関特性を利用するので,本モデルでは様々な種類の実世界のデータセットを扱うことが可能である。
  論文  参考訳（メタデータ） (2020-10-01T12:45:39Z)
• Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimality [92.35257908210316]
  本研究では,不完全かつ破損した観測によって与えられる低ランクテンソルを推定する問題について検討する。 改善不可能なレートをell-2$の精度で達成できることが分かりました。
  論文  参考訳（メタデータ） (2020-06-15T17:47:13Z)

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

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