論文の概要: Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA

• arxiv url: http://arxiv.org/abs/2303.06198v2
• Date: Sun, 13 Oct 2024 02:58:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-15 15:03:29.222868
• Title: Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA
• Title（参考訳）: Deflated HeteroPCA:ヘテロスケダスティックPCAにおける不調の呪いの克服
• Authors: Yuchen Zhou, Yuxin Chen,
• Abstract要約: 本稿では,汚染されたデータからmathbbRn_1times n$の低ランク行列$boldsymbolXstarの列部分空間を推定することに関心がある。 信号-雑音比 (SNR) の広帯域化を図りながら, 最適な統計的精度を得る方法は困難である。
• 参考スコア（独自算出の注目度）: 17.75853665586128
• License:
• Abstract: This paper is concerned with estimating the column subspace of a low-rank matrix $\boldsymbol{X}^\star \in \mathbb{R}^{n_1\times n_2}$ from contaminated data. How to obtain optimal statistical accuracy while accommodating the widest range of signal-to-noise ratios (SNRs) becomes particularly challenging in the presence of heteroskedastic noise and unbalanced dimensionality (i.e., $n_2\gg n_1$). While the state-of-the-art algorithm $\textsf{HeteroPCA}$ emerges as a powerful solution for solving this problem, it suffers from "the curse of ill-conditioning," namely, its performance degrades as the condition number of $\boldsymbol{X}^\star$ grows. In order to overcome this critical issue without compromising the range of allowable SNRs, we propose a novel algorithm, called $\textsf{Deflated-HeteroPCA}$, that achieves near-optimal and condition-number-free theoretical guarantees in terms of both $\ell_2$ and $\ell_{2,\infty}$ statistical accuracy. The proposed algorithm divides the spectrum of $\boldsymbol{X}^\star$ into well-conditioned and mutually well-separated subblocks, and applies $\textsf{HeteroPCA}$ to conquer each subblock successively. Further, an application of our algorithm and theory to two canonical examples -- the factor model and tensor PCA -- leads to remarkable improvement for each application.
• Abstract（参考訳）: 本稿では、汚染データから低ランク行列 $\boldsymbol{X}^\star \in \mathbb{R}^{n_1\times n_2}$ の列部分空間を推定することに関心がある。 最も広い信号-雑音比(SNR)を調節しながら最適な統計的精度を得るには、ヘテロスケダティックノイズと非バランス次元(すなわち$n_2\gg n_1$)の存在が特に難しい。 最先端のアルゴリズムである $\textsf{HeteroPCA}$ は、この問題を解決するための強力なソリューションとして現れるが、その性能は $\boldsymbol{X}^\star$ の条件数として低下する「悪条件の呪い」に悩まされている。 許容 SNR の範囲を妥協することなくこの問題を克服するために,$\ell_2$ と $\ell_{2,\infty}$ の両面から,ほぼ最適かつ条件数のない理論的保証を実現する,$\textsf{Deflated-HeteroPCA}$ という新しいアルゴリズムを提案する。 提案アルゴリズムは、$\boldsymbol{X}^\star$のスペクトルを、よく条件付きおよび相互に分離されたサブブロックに分割し、各サブブロックを順次征服するために$\textsf{HeteroPCA}$を適用する。 さらに、因子モデルとテンソルPCAという2つの標準例に対するアルゴリズムと理論の適用により、各アプリケーションに顕著な改善がもたらされる。

関連論文リスト

• Fair Submodular Cover [18.37610521373708]
  フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。 まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。 次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-07-05T18:37:09Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• A Combinatorial Approach to Robust PCA [18.740048806623037]
  敵の汚職下でのガウスデータの回復問題について検討する。 ガウスノイズは未知の$k$-次元部分空間$U subseteq mathbbRd$と、各データポイントのランダムに選択された座標が敵の制御に該当すると仮定する。 我々の主な結果は、$ks2 = O(d)$のとき、期待して$tilde O(ks/d)$のほぼ最適エラーまですべてのデータポイントを復元する効率的なアルゴリズムです。
  論文  参考訳（メタデータ） (2023-11-28T01:49:51Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• DP-PCA: Statistically Optimal and Differentially Private PCA [44.22319983246645]
  DP-PCAは、両方の制限を克服するシングルパスアルゴリズムである。 準ガウスデータに対しては、$n=tilde O(d)$ であっても、ほぼ最適な統計的誤差率を提供する。
  論文  参考訳（メタデータ） (2022-05-27T02:02:17Z)
• Sharper Utility Bounds for Differentially Private Models [20.246768861331276]
  最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。 新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
  論文  参考訳（メタデータ） (2022-04-22T07:03:13Z)
• 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)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。 結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
  論文  参考訳（メタデータ） (2020-06-29T21:06:52Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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