論文の概要: Spectral gap-based deterministic tensor completion

• arxiv url: http://arxiv.org/abs/2306.06262v1
• Date: Fri, 9 Jun 2023 21:18:44 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-13 20:01:18.184638
• Title: Spectral gap-based deterministic tensor completion
• Title（参考訳）: スペクトルギャップに基づく決定論的テンソル補完
• Authors: Kameron Decker Harris and Oscar L\'opez and Angus Read and Yizhe Zhu
• Abstract要約: 本稿では,2つのテンソル完備化法,ポアソン損失と原子ノルム最小化の解の一般化誤差について検討する。 我々は原子テンソルノルムのいくつかの新しい性質を証明し、arXiv:1711.04965の階数依存をランダムサンプリングスキームで$r3t-3$から$r3t-5$に減らした。 数値実験は, 実効最大準位, リッジペナルティ, ポアソン損失最小化アルゴリズムのスペクトルギャップに対する再構成誤差の依存性を示す。
• 参考スコア（独自算出の注目度）: 10.569670359770514
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tensor completion is a core machine learning algorithm used in recommender systems and other domains with missing data. While the matrix case is well-understood, theoretical results for tensor problems are limited, particularly when the sampling patterns are deterministic. Here we bound the generalization error of the solutions of two tensor completion methods, Poisson loss and atomic norm minimization, providing tighter bounds in terms of the target tensor rank. If the ground-truth tensor is order $t$ with CP-rank $r$, the dependence on $r$ is improved from $r^{2(t-1)(t^2-t-1)}$ in arXiv:1910.10692 to $r^{2(t-1)(3t-5)}$. The error in our bounds is deterministically controlled by the spectral gap of the sampling sparsity pattern. We also prove several new properties for the atomic tensor norm, reducing the rank dependence from $r^{3t-3}$ in arXiv:1711.04965 to $r^{3t-5}$ under random sampling schemes. A limitation is that atomic norm minimization, while theoretically interesting, leads to inefficient algorithms. However, numerical experiments illustrate the dependence of the reconstruction error on the spectral gap for the practical max-quasinorm, ridge penalty, and Poisson loss minimization algorithms. This view through the spectral gap is a promising window for further study of tensor algorithms.
• Abstract（参考訳）: テンソル補完(Tensor completion)は、レコメンデータシステムや他のドメインで使用されるコア機械学習アルゴリズムである。 行列ケースはよく理解されているが、特にサンプリングパターンが決定論的である場合、テンソル問題の理論的結果は限られている。 ここでは、2つのテンソル完備化法、ポアソン損失と原子ノルム最小化の解の一般化誤差を有界とし、ターゲットテンソル階数の観点からより厳密な境界を与える。 基底トラステンソルが CP-ランク$r$ で$t$ であるなら、$r$ への依存は $r^{2(t-1)(t^2-t-1)}$ arXiv:1910.10692 から $r^{2(t-1)(3t-5)}$ に改善される。 我々の境界における誤差はサンプリング間隔パターンのスペクトルギャップによって決定的に制御される。 また、原子テンソルノルムに対するいくつかの新しい性質を証明し、arXiv:1711.04965 において $r^{3t-3} から $r^{3t-5} へのランク依存をランダムサンプリングスキームで減らした。 制限は、原子ノルムの最小化は理論上は興味深いが、非効率なアルゴリズムにつながることである。 しかし、数値実験により、実用的なmax-quasinorm、リッジペナルティ、ポアソン損失最小化アルゴリズムのスペクトルギャップに対する再構成誤差の依存性が示されている。 スペクトルギャップを通したこの見解は、テンソルアルゴリズムのさらなる研究のための有望な窓である。

関連論文リスト

• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [63.01248796170617]
  最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。 次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
  論文  参考訳（メタデータ） (2024-11-21T17:41:09Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• 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)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  テンソルの低階近似について検討し,テンソルトレインとタッカー分解に着目した。 テンソル列車の分解には、小さなビクリテリアランクを持つビクリテリア$(1 + eps)$-approximationアルゴリズムと、O(q cdot nnz(A))$ランニングタイムを与える。 さらに、任意のグラフを持つテンソルネットワークにアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2022-07-15T11:55:09Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Fast Tensor Disentangling Algorithm [0.0]
  本稿では, 互いに絡み合うユニタリテンソルを最適化する近似的, 高速, 簡易なアルゴリズムを提案する。 我々のアルゴリズムは以前の反復アルゴリズムよりも高速であり、しばしば最小の10から40%以内の残絡エントロピーをもたらす。
  論文  参考訳（メタデータ） (2021-04-16T18:00:01Z)
• Beyond Lazy Training for Over-parameterized Tensor Decomposition [69.4699995828506]
  過度なパラメータ化対象の勾配勾配は遅延学習体制を超え、データ中の特定の低ランク構造を利用する可能性があることを示す。 以上の結果から,過パラメータ化対象の勾配勾配は遅延学習体制を超え,データ中の特定の低ランク構造を利用する可能性が示唆された。
  論文  参考訳（メタデータ） (2020-10-22T00:32:12Z)
• A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iteration [23.308822706415867]
  高次直交反復(HOOI)に対するブロックワイドテンソル摂動境界を確立する。 モード-$k$特異部分空間推定の上限は、摂動と信号強度のブロックワイズ誤差を特徴とする量に一側収束することを示す。 一つの反復しか持たない一段階 HOOI がテンソル再構成の点でも最適であり,計算コストの低減に有効であることを示す。
  論文  参考訳（メタデータ） (2020-08-06T03:01:28Z)

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

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