Fugu-MT 論文翻訳(概要): A Smooth Computational Transition in Tensor PCA

論文の概要: A Smooth Computational Transition in Tensor PCA

arxiv url: http://arxiv.org/abs/2509.09904v1
Date: Fri, 12 Sep 2025 00:21:20 GMT
ステータス: 翻訳完了
システム内更新日: 2025-09-15 16:03:07.948405
Title: A Smooth Computational Transition in Tensor PCA
Title（参考訳）: テンソルPCAの滑らかな計算遷移
Authors: Zhangsong Li,
Abstract要約: 重み付きハイパーグラフの特定の族をカウントしたテンソルPCAの効率的なアルゴリズムを提案する。この結果から,信号対雑音比と計算コストとの間には円滑なトレードオフが認められた。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We propose an efficient algorithm for tensor PCA based on counting a specific family of weighted hypergraphs. For the order-$p$ tensor PCA problem where $p \geq 3$ is a fixed integer, we show that when the signal-to-noise ratio is $\lambda n^{-\frac{p}{4}}$ where $\lambda=\Omega(1)$, our algorithm succeeds and runs in time $n^{C+o(1)}$ where $C=C(\lambda)$ is a constant depending on $\lambda$. This algorithm improves a poly-logarithmic factor compared to previous algorithms based on the Sum-of-Squares hierarchy \cite{HSS15} or based on the Kikuchi hierarchy in statistical physics \cite{WEM19}. Furthermore, our result shows a smooth tradeoff between the signal-to-noise ratio and the computational cost in this problem, thereby confirming a conjecture posed in \cite{KWB22}.
Abstract（参考訳）: 重み付きハイパーグラフの特定の族をカウントしたテンソルPCAの効率的なアルゴリズムを提案する。順序-$p$のテンソルPCA問題では、$p \geq 3$が固定整数である場合、信号-雑音比が$\lambda n^{-\frac{p}{4}}$であるとき、$\lambda=\Omega(1)$で、我々のアルゴリズムが成功し、時間で$n^{C+o(1)}$で走る場合、$C=C(\lambda)$は$\lambda$に依存する定数であることを示す。このアルゴリズムは、統計物理学における Sum-of-Squares 階層 \cite{HSS15} や菊池階層をベースとした従来のアルゴリズムと比較して、多対数係数を改善する。さらに,この結果から,信号対雑音比と計算コストとの円滑なトレードオフが示され,従って \cite{KWB22} の予想が確定される。

関連論文リスト

The Algorithmic Phase Transition in Symmetric Correlated Spiked Wigner Model [0.0]
本研究では,一対のスパイクされたウィグナー行列における相関信号の検出と推定の計算タスクについて検討する。アルゴリズムはスパイク間の相関を利用して、$X$から$x$を効率よく回収するか、$Y$から$y$を効率よく回収するかのどちらかが計算不可能な状態であっても信号を検出して推定することができる。
論文参考訳（メタデータ） (2025-11-08T15:23:44Z)
Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文参考訳（メタデータ） (2025-10-12T15:42:44Z)
Robust random graph matching in Gaussian models via vector approximate message passing [0.0]
我々は,n1-o(1)$の任意の逆摂動の下で頑健な効率的なランダムグラフマッチング型アルゴリズムを提案する。我々のアルゴリズムは,n1-o(1)$の任意の逆摂動の下で頑健な,最初の効率的なランダムグラフマッチング型アルゴリズムである。
論文参考訳（メタデータ） (2024-12-21T03:15:38Z)
Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
我々は,暗黙のモーメントテンソル複雑性を表わす汎用的アルゴリズムを開発した。暗黙のモーメント推定アルゴリズムを利用して、以下のモデルに対して最初の$mathrmpoly(d, k, 1/epsilon)$-time学習アルゴリズムを得る。
論文参考訳（メタデータ） (2024-11-23T23:13:24Z)
A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文参考訳（メタデータ） (2024-03-07T18:23:51Z)
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)
Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
論文参考訳（メタデータ） (2023-02-20T18:45:24Z)
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)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文参考訳（メタデータ） (2022-06-17T17:55:43Z)
Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文参考訳（メタデータ） (2022-05-27T00:34:03Z)
The Complexity of Sparse Tensor PCA [1.90365714903665]
1leq leq k$の場合、我々のアルゴリズムは信号対雑音比$lambda geq tildemathcalO (sqrtt cdot (k/t)p/2)$のスパースベクトルを時間内に回収する。 PCAの制限されたケースでさえ、既知のアルゴリズムは、$lambda geq tildemathcalO(k cdot r)のスパースベクトルのみを復元する一方、我々のアルゴリズムは$lambda geを必要とする。
論文参考訳（メタデータ） (2021-06-11T10:57:00Z)
The Kikuchi Hierarchy and Tensor PCA [50.840260149979265]
テンソルPCA(主成分分析)問題に対して,ランタイムの増大を伴うアルゴリズムの階層化を提案する。我々の階層は、SOS(sum-of-squares)階層に似ているが、代わりに統計物理学や関連するアルゴリズムにインスパイアされている。
論文参考訳（メタデータ） (2019-04-08T06:26:35Z)

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