論文の概要: Combinatorial Sparse PCA Beyond the Spiked Identity Model

• arxiv url: http://arxiv.org/abs/2603.02607v1
• Date: Tue, 03 Mar 2026 05:19:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-04 21:38:10.644121
• Title: Combinatorial Sparse PCA Beyond the Spiked Identity Model
• Title（参考訳）: スパイクされたアイデンティティモデルを超えたコンビニアルスパースPCA
• Authors: Syamantak Kumar, Purnamrita Sarkar, Kevin Tian, Peiyuan Zhang,
• Abstract要約: 一般に$s2 cdot Mathrmpolylog(d)$サンプルと$d2 cdot Mathrmpoly(s)$タイムを用いて$$を証明可能なスパースPCAの手法を提案する。 また,本手法を合成および実世界のデータセット上で評価した。
• 参考スコア（独自算出の注目度）: 25.073817053937802
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sparse PCA is one of the most well-studied problems in high-dimensional statistics. In this problem, we are given samples from a distribution with covariance $Σ$, whose top eigenvector $v \in R^d$ is $s$-sparse. Existing sparse PCA algorithms can be broadly categorized into (1) combinatorial algorithms (e.g., diagonal or elementwise covariance thresholding) and (2) SDP-based algorithms. While combinatorial algorithms are much simpler, they are typically only analyzed under the spiked identity model (where $Σ= I_d + γvv^\top$ for some $γ> 0$), whereas SDP-based algorithms require no additional assumptions on $Σ$. We demonstrate explicit counterexample covariances $Σ$ against the success of standard combinatorial algorithms for sparse PCA, when moving beyond the spiked identity model. In light of this discrepancy, we give the first combinatorial method for sparse PCA that provably succeeds for general $Σ$ using $s^2 \cdot \mathrm{polylog}(d)$ samples and $d^2 \cdot \mathrm{poly}(s, \log(d))$ time, by providing a global convergence guarantee on a variant of the truncated power method of Yuan and Zhang (2013). We provide a natural generalization of our method to recovering a vector in a sparse leading eigenspace. Finally, we evaluate our method on synthetic and real-world sparse PCA datasets.
• Abstract（参考訳）: スパースPCAは高次元統計学において最もよく研究されている問題の1つである。 この問題では、共分散$$$の分布からサンプルが与えられ、その最上位固有ベクトル$v \in R^d$は$s$-sparseである。 既存のスパースPCAアルゴリズムは、(1)組合せアルゴリズム(例えば、対角的または要素的共分散しきい値)と(2)SDPベースのアルゴリズムに大別できる。 組合せアルゴリズムはより単純であるが、通常はスパイクされた恒等式($Σ= I_d + γvv^\top$ for some $γ> 0$)の下でのみ解析される。 我々はスパースPCAの標準組合せアルゴリズムの成功に対して、スパイクされた同一性モデルを超えて、明示的な反例共分散を$Σ$で示している。 この相違を考慮し、一般に$s^2 \cdot \mathrm{polylog}(d)$ sample と $d^2 \cdot \mathrm{poly}(s, \log(d))$ time を用いて証明的に成功するスパースPCAに対する最初の組合せ法を与える。 スパースリード固有空間内のベクトルを復元する手法を自然に一般化する。 最後に,本手法を合成および実世界のスパースPCAデータセット上で評価する。

関連論文リスト

• An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise [8.555773470114698]
  任意の$k leq d$に対してトップ$k$固有ベクトルを推定できるアルゴリズムを提案する。 我々のアルゴリズムは、$n = tilde!O(d)$ であっても、ほぼ最適統計誤差を達成する。
  論文  参考訳（メタデータ） (2025-08-14T17:48:45Z)
• SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
  我々は、最大$|M u|$で境界を証明できる新しいアップタイムアルゴリズムの族を与える。 我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。
  論文  参考訳（メタデータ） (2024-12-30T18:59:46Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Oja's Algorithm for Streaming Sparse PCA [7.059472280274011]
  Oja's Algorithm for Streaming principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time。 Ojaのアルゴリズムの出力をしきい値にする単純なシングルパス手順は、$O(d)$ space と $O(nd)$ time の正則性条件下での最小誤差を達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-11T16:36:48Z)
• 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)
• Replicable Clustering [57.19013971737493]
  我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。 理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
  論文  参考訳（メタデータ） (2023-02-20T23:29:43Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)

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

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