論文の概要: Statistical Query Lower Bounds for Tensor PCA

• arxiv url: http://arxiv.org/abs/2008.04101v2
• Date: Sat, 13 Feb 2021 19:00:15 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-31 23:32:00.548025
• Title: Statistical Query Lower Bounds for Tensor PCA
• Title（参考訳）: テンソルPCAにおける統計的問合せ下界
• Authors: Rishabh Dudeja and Daniel Hsu
• Abstract要約: Richard と Montanari が導入した PCA 問題では、$n$サンプル $mathbbEmathbfT_1:n$ of i.d. Perkins Gaussian tensors of order $k$ からなるデータセットが与えられ、$mathbbEmathbfT_1:n$ はランク 1 である。 目標は$mathbbE mathbfT_1$を見積もることである。 最適なサンプルの複雑さを鋭く分析する。
• 参考スコア（独自算出の注目度）: 10.701091387118023
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the Tensor PCA problem introduced by Richard and Montanari (2014), one is given a dataset consisting of $n$ samples $\mathbf{T}_{1:n}$ of i.i.d. Gaussian tensors of order $k$ with the promise that $\mathbb{E}\mathbf{T}_1$ is a rank-1 tensor and $\|\mathbb{E} \mathbf{T}_1\| = 1$. The goal is to estimate $\mathbb{E} \mathbf{T}_1$. This problem exhibits a large conjectured hard phase when $k>2$: When $d \lesssim n \ll d^{\frac{k}{2}}$ it is information theoretically possible to estimate $\mathbb{E} \mathbf{T}_1$, but no polynomial time estimator is known. We provide a sharp analysis of the optimal sample complexity in the Statistical Query (SQ) model and show that SQ algorithms with polynomial query complexity not only fail to solve Tensor PCA in the conjectured hard phase, but also have a strictly sub-optimal sample complexity compared to some polynomial time estimators such as the Richard-Montanari spectral estimator. Our analysis reveals that the optimal sample complexity in the SQ model depends on whether $\mathbb{E} \mathbf{T}_1$ is symmetric or not. For symmetric, even order tensors, we also isolate a sample size regime in which it is possible to test if $\mathbb{E} \mathbf{T}_1 = \mathbf{0}$ or $\mathbb{E}\mathbf{T}_1 \neq \mathbf{0}$ with polynomially many queries but not estimate $\mathbb{E}\mathbf{T}_1$. Our proofs rely on the Fourier analytic approach of Feldman, Perkins and Vempala (2018) to prove sharp SQ lower bounds.
• Abstract（参考訳）: Richard and Montanari (2014) が導入したTensor PCA問題では、$n$サンプル$\mathbf{T}_{1:n}$、すなわち$k$のガウステンソル$と、$\mathbb{E}\mathbf{T}_1$がランク1テンソルおよび$\|\mathbb{E} \mathbf{T}_1\| = 1$からなるデータセットが与えられる。 目標は$\mathbb{E} \mathbf{T}_1$を見積もることである。 この問題は、$k>2$:$d \lesssim n \ll d^{\frac{k}{2}}$が$\mathbb{E} \mathbf{T}_1$を推定することは理論上可能な情報であるが、多項式時間推定器は知られていない。 統計的クエリーモデル(SQ)モデルにおける最適なサンプル複雑性を鋭く分析し、多項式クエリ複雑性を持つSQアルゴリズムが予測されたハードフェーズでテンソルPCAを解くことに失敗するだけでなく、リチャード・モンタナリスペクトル推定器のような多項式時間推定器と比較して、厳密なサンプル複雑性を持つことを示す。 解析により、SQモデルの最適なサンプル複雑性は、$\mathbb{E} \mathbf{T}_1$ が対称であるか否かに依存することが明らかになった。 対称な順序テンソルに対しても、$\mathbb{E} \mathbf{T}_1 = \mathbf{0}$ または$\mathbb{E}\mathbf{T}_1 \neq \mathbf{0}$ が多項式的に多くのクエリを持つが$\mathbb{E}\mathbf{T}_1$ を推定しない場合、検定可能なサンプルサイズ規則も分離する。 我々の証明は、鋭いSQ下界を証明するために、Feldman, Perkins and Vempala (2018) のフーリエ解析的アプローチに依存している。

関連論文リスト

• Near-Optimal and Tractable Estimation under Shift-Invariance [0.21756081703275998]
  そのような信号のクラスは、非常にリッチである:$mathbbCn$ 上のすべての指数振動を含み、合計$s$ である。 このクラスの統計複雑性は、$(delta)$-confidence $ell$-ballの半径2乗最小マックス周波数によって測定されるが、$s$-sparse信号のクラス、すなわち$Oleft(slog(en) + log(delta-1)right) cdot log(en/s)とほぼ同じであることを示す。
  論文  参考訳（メタデータ） (2024-11-05T18:11:23Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Statistical Query Lower Bounds for Learning Truncated Gaussians [43.452452030671694]
  この問題のSQアルゴリズムの複雑さは、$dmathrmpoly (1/epsilon)$であり、クラス$mathcalC$が単純である場合でも、$mathrmpoly(d/epsilon)が情報理論的に十分であることを示す。
  論文  参考訳（メタデータ） (2024-03-04T18:30:33Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
  多次元分布に対する近接性(あるいは等価性)検定の統計的課題について検討する。 具体的には、$mathbf p, mathbf q$ on $mathbb Rd$ に対して、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ の2つの未知の分布へのサンプルアクセスが与えられると、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ を区別する。 本研究の主な成果は,任意の固定次元におけるサブラーニングサンプルの複雑性を考慮に入れた,この問題に対する最初のクローズネステスタである。
  論文  参考訳（メタデータ） (2023-11-22T04:34:09Z)
• 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)
• 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)
• Multimeasurement Generative Models [7.502947376736449]
  我々は、密度$p_X$ in $mathbbRd$を未知分布からサンプリングする問題を学習とサンプリングの問題を$p_mathbfY$ in $mathbbRMd$とする。
  論文  参考訳（メタデータ） (2021-12-18T02:11:36Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)

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

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