論文の概要: Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the
Tensor Nuclear Norm Under Strict Complementarity
- arxiv url: http://arxiv.org/abs/2308.01677v1
- Date: Thu, 3 Aug 2023 10:31:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-04 14:30:05.126415
- Title: Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the
Tensor Nuclear Norm Under Strict Complementarity
- Title（参考訳）: 厳密な相補性下におけるテンソル核規範を用いた低ランクテンソル回復の一階法の有効性
- Authors: Dan Garber, Atara Kaplan
- Abstract要約: テンソル核ノルムによって誘導される球上での制約反復に基づく低ランクテンソルの回収のための凸緩和について考察する。
厳密な相補性条件の下では、標準勾配法の収束率と点当たりのランタイムの両方が劇的に改善される。
- 参考スコア（独自算出の注目度）: 19.930021245647705
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider convex relaxations for recovering low-rank tensors based on
constrained minimization over a ball induced by the tensor nuclear norm,
recently introduced in \cite{tensor_tSVD}. We build on a recent line of results
that considered convex relaxations for the recovery of low-rank matrices and
established that under a strict complementarity condition (SC), both the
convergence rate and per-iteration runtime of standard gradient methods may
improve dramatically. We develop the appropriate strict complementarity
condition for the tensor nuclear norm ball and obtain the following main
results under this condition: 1. When the objective to minimize is of the form
$f(\mX)=g(\mA\mX)+\langle{\mC,\mX}\rangle$ , where $g$ is strongly convex and
$\mA$ is a linear map (e.g., least squares), a quadratic growth bound holds,
which implies linear convergence rates for standard projected gradient methods,
despite the fact that $f$ need not be strongly convex. 2. For a smooth
objective function, when initialized in certain proximity of an optimal
solution which satisfies SC, standard projected gradient methods only require
SVD computations (for projecting onto the tensor nuclear norm ball) of rank
that matches the tubal rank of the optimal solution. In particular, when the
tubal rank is constant, this implies nearly linear (in the size of the tensor)
runtime per iteration, as opposed to super linear without further assumptions.
3. For a nonsmooth objective function which admits a popular smooth
saddle-point formulation, we derive similar results to the latter for the well
known extragradient method. An additional contribution which may be of
independent interest, is the rigorous extension of many basic results regarding
tensors of arbitrary order, which were previously obtained only for third-order
tensors.
- Abstract（参考訳）: テンソル核ノルムによって誘導されるボール上の制約最小化に基づく低ランクテンソルの回収のための凸緩和について考察する。
我々は,低ランク行列の回復に対する凸緩和を考慮した最近の結果を基に構築し,厳密な相補性条件 (SC) の下では,標準勾配法の収束率と点当たり実行時間の両方が劇的に向上することを示した。
テンソル核ノルムボールの適切な厳密相補性条件を開発し、この条件下で次の主な結果を得る。
1. 最小化の目的が $f(\mX)=g(\mA\mX)+\langle{\mC,\mX}\rangle$,, where $g$ is strongly convex and $\mA$ is a linear map (例: least squares) であるとき、f$は強凸ではないという事実にもかかわらず、標準射影勾配法に対する線型収束率を意味する二次成長境界が成立する。
2 滑らかな目的関数に対して、scを満たす最適解の特定の近傍で初期化されるとき、標準射影勾配法は、最適解の管級に一致するランクのsvd計算(テンソル核ノルム球への射影)のみを必要とする。
特に、管のランクが一定である場合、これは(テンソルの大きさの)ほぼ線形のランタイムを、それ以上の仮定なしで超線形とは対照的に意味する。
3. 一般的な滑らかな鞍点定式化を許容する非滑らかな目的関数に対しては、よく知られた超勾配法で後者と同様の結果を導出する。
独立な興味を持つかもしれない追加の貢献は、以前は三階テンソルに対してのみ得られていた任意の順序のテンソルに関する多くの基本的な結果の厳密な拡張である。
関連論文リスト
- Low-Rank Tensor Learning by Generalized Nonconvex Regularization [25.115066273660478]
低ランクテンソル学習の問題点について検討し, 基礎となるテンソルを観測するサンプルはごくわずかである。
非テンソル学習関数の族は、基礎となるテンソルの低ランク性を特徴づけるために用いられる。
結果の大量化最小化を解決するために設計されたアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-10-24T03:33:20Z) - Large Deviations and Improved Mean-squared Error Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetry [47.653744900375855]
本研究では,オンライン環境における非線形凸勾配法の一般的な枠組みを,大偏差と平均二乗誤差(MSE)で保証する。
重騒音対称密度関数の存在下での広帯域ステップサイズに対する強い結果を与える。
論文 参考訳（メタデータ） (2024-10-21T04:50:57Z) - Low-Rank Tensor Completion via Novel Sparsity-Inducing Regularizers [30.920908325825668]
低ランクテンソル完備化問題において、l1-ノルムを緩和するため、非ランクサロゲート/正則化器が提案されている。
これらの正則化器は核ランク復元に適用され,乗算器法に基づく効率的なアルゴリズムが提案されている。
論文 参考訳（メタデータ） (2023-10-10T01:00:13Z) - 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) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる
新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
論文 参考訳（メタデータ） (2021-05-13T04:23:07Z) - A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration [23.308822706415867]
高次直交反復(HOOI)に対するブロックワイドテンソル摂動境界を確立する。
モード-$k$特異部分空間推定の上限は、摂動と信号強度のブロックワイズ誤差を特徴とする量に一側収束することを示す。
一つの反復しか持たない一段階 HOOI がテンソル再構成の点でも最適であり,計算コストの低減に有効であることを示す。
論文 参考訳（メタデータ） (2020-08-06T03:01:28Z) - Tensor completion via nonconvex tensor ring rank minimization with
guaranteed convergence [16.11872681638052]
近年の研究では、テンソル環(TR)のランクはテンソル完備化において高い効果を示している。
最近提案されたTRランクは、特異値が等しくペナル化される重み付き和の中で構造を捉えることに基づいている。
本稿では,ロゼット型関数を非スムーズな緩和法として利用することを提案する。
論文 参考訳（メタデータ） (2020-05-14T03:13:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。