論文の概要: Tensor cumulants for statistical inference on invariant distributions
- arxiv url: http://arxiv.org/abs/2404.18735v1
- Date: Mon, 29 Apr 2024 14:33:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-30 13:28:15.840321
- Title: Tensor cumulants for statistical inference on invariant distributions
- Title（参考訳）: 不変分布に関する統計的推測のためのテンソル累積
- Authors: Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein,
- Abstract要約: 我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。
我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。
また、異なるアンサンブルを区別する新しい問題も分析できます。
- 参考スコア（独自算出の注目度）: 49.80012009682584
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many problems in high-dimensional statistics appear to have a statistical-computational gap: a range of values of the signal-to-noise ratio where inference is information-theoretically possible, but (conjecturally) computationally intractable. A canonical such problem is Tensor PCA, where we observe a tensor $Y$ consisting of a rank-one signal plus Gaussian noise. Multiple lines of work suggest that Tensor PCA becomes computationally hard at a critical value of the signal's magnitude. In particular, below this transition, no low-degree polynomial algorithm can detect the signal with high probability; conversely, various spectral algorithms are known to succeed above this transition. We unify and extend this work by considering tensor networks, orthogonally invariant polynomials where multiple copies of $Y$ are "contracted" to produce scalars, vectors, matrices, or other tensors. We define a new set of objects, tensor cumulants, which provide an explicit, near-orthogonal basis for invariant polynomials of a given degree. This basis lets us unify and strengthen previous results on low-degree hardness, giving a combinatorial explanation of the hardness transition and of a continuum of subexponential-time algorithms that work below it, and proving tight lower bounds against low-degree polynomials for recovering rather than just detecting the signal. It also lets us analyze a new problem of distinguishing between different tensor ensembles, such as Wigner and Wishart tensors, establishing a sharp computational threshold and giving evidence of a new statistical-computational gap in the Central Limit Theorem for random tensors. Finally, we believe these cumulants are valuable mathematical objects in their own right: they generalize the free cumulants of free probability theory from matrices to tensors, and share many of their properties, including additivity under additive free convolution.
- Abstract（参考訳）: 高次元統計学における多くの問題は統計計算のギャップがあり、推論が情報理論上可能であるが(概念的には)計算的に難解な信号対雑音比の値の範囲である。
そのような問題はテンソルPCAであり、階数1の信号とガウス雑音からなるテンソル$Y$を観測する。
複数の作業行は、テンソルPCAが信号の大きさの臨界値で計算的に困難になることを示唆している。
特に、この遷移より下において、低次多項式アルゴリズムは高い確率で信号を検出できない。
我々は、スカラー、ベクトル、行列、その他のテンソルを生成するために、$Y$の複数のコピーが「収縮」された直交不変多項式であるテンソルネットワークを考慮し、この作業を統一し拡張する。
対象の新たな集合、テンソル累積を定義し、与えられた次数の不変多項式に対して明示的でほぼ直交的な基底を与える。
この基礎は、低次硬さに関する以前の結果を統一・強化し、信号を検出するのではなく、低次多項式に対する厳密な下限を証明し、その下で働く半指数時間アルゴリズムの硬さ遷移と連続性の組合せ的な説明を与える。
また、ウィグナーやウィッシャートテンソルのような異なるテンソルアンサンブルを区別する新たな問題を分析し、鋭い計算しきい値を確立し、ランダムテンソルに対する中央極限定理における新しい統計計算的ギャップの証拠を与える。
行列からテンソルへの自由確率理論の自由累積を一般化し、加法的自由畳み込みの下で加法性を含む多くの性質を共有する。
関連論文リスト
- Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
我々は、ある微分方程式のオイラー・マルヤマ離散化のように見える、より一般で幅広いマルコフ連鎖、伊藤鎖を考える。
伊藤鎖の法則と微分方程式の間の$W_2$-距離の有界性を証明する。
論文 参考訳（メタデータ） (2023-10-09T18:38:56Z) - 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) - Lower Bounds for the Convergence of Tensor Power Iteration on Random
Overcomplete Models [3.7565501074323224]
テンソルパワー反復を任意の真の成分に収束させるためには、テンソルの多くのステップが必要であることを示す。
我々は、テンソル分解の一般的な目的関数が、電力反復経路に沿って厳密に増大していることを証明する。
論文 参考訳（メタデータ） (2022-11-07T19:23:51Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Smooth tensor estimation with unknown permutations [14.391648046717073]
任意の指数置換を含む滑らかなテンソルモデルの族を開発する。
ブロックワイズ群における制約付き最小二乗推定器がミニマックス誤差境界を達成することを示す。
また,効率の良いボルダカウントアルゴリズムも提案する。
論文 参考訳（メタデータ） (2021-11-08T17:53:48Z) - Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation
from Incomplete Measurements [30.395874385570007]
基本的な課題は、高度に不完全な測定からテンソルを忠実に回収することである。
タッカー分解におけるテンソル因子を直接回復するアルゴリズムを開発した。
2つの正準問題に対する基底真理テンソルの線形独立率で確実に収束することを示す。
論文 参考訳（メタデータ） (2021-04-29T17:44:49Z) - Inference for Low-rank Tensors -- No Need to Debias [22.163281794187544]
本稿では,低ランクテンソルモデルの統計的推論について考察する。
階数 1 の PCA モデルに対して、個々の特異テンソル上での推論の理論を確立する。
最後に、理論的な発見を裏付けるシミュレーションが提示される。
論文 参考訳（メタデータ） (2020-12-29T16:48:02Z) - Conformal Properties of Hyperinvariant Tensor Networks [0.0]
半周期臨界スピン鎖に対するハイメラにおけるテンソルの最適化に関する課題を解析する。
元の構成と異なる性質を示すテンソル分解の2つの新しい集合を示す。
hyMERAにおける局所下降超作用素のスペクトルに課される制約は、いくつかのミニミアルモデルCFTの演算子スペクトルと互換性があることが分かる。
論文 参考訳（メタデータ） (2020-12-17T14:06:15Z) - Spectral Learning on Matrices and Tensors [74.88243719463053]
テンソル分解は行列法で欠落する潜伏効果を拾うことができることを示す。
また,効率的なテンソル分解法を設計するための計算手法についても概説する。
論文 参考訳（メタデータ） (2020-04-16T22:53:00Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。