論文の概要: Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
- arxiv url: http://arxiv.org/abs/2011.06585v1
- Date: Thu, 12 Nov 2020 18:58:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-26 07:55:36.841666
- Title: Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
- Title（参考訳）: スパースPCA:アルゴリズム、逆摂動、証明書
- Authors: Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer
- Abstract要約: 標準統計モデルにおけるスパースPCAの効率的なアルゴリズムについて検討する。
私たちのゴールは、小さな摂動に耐性を持ちながら、最適な回復保証を達成することです。
- 参考スコア（独自算出の注目度）: 9.348107805982604
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study efficient algorithms for Sparse PCA in standard statistical models
(spiked covariance in its Wishart form). Our goal is to achieve optimal
recovery guarantees while being resilient to small perturbations. Despite a
long history of prior works, including explicit studies of perturbation
resilience, the best known algorithmic guarantees for Sparse PCA are fragile
and break down under small adversarial perturbations.
We observe a basic connection between perturbation resilience and
\emph{certifying algorithms} that are based on certificates of upper bounds on
sparse eigenvalues of random matrices. In contrast to other techniques, such
certifying algorithms, including the brute-force maximum likelihood estimator,
are automatically robust against small adversarial perturbation.
We use this connection to obtain the first polynomial-time algorithms for
this problem that are resilient against additive adversarial perturbations by
obtaining new efficient certificates for upper bounds on sparse eigenvalues of
random matrices. Our algorithms are based either on basic semidefinite
programming or on its low-degree sum-of-squares strengthening depending on the
parameter regimes. Their guarantees either match or approach the best known
guarantees of \emph{fragile} algorithms in terms of sparsity of the unknown
vector, number of samples and the ambient dimension.
To complement our algorithmic results, we prove rigorous lower bounds
matching the gap between fragile and robust polynomial-time algorithms in a
natural computational model based on low-degree polynomials (closely related to
the pseudo-calibration technique for sum-of-squares lower bounds) that is known
to capture the best known guarantees for related statistical estimation
problems. The combination of these results provides formal evidence of an
inherent price to pay to achieve robustness.
- Abstract（参考訳）: 標準統計モデル(spiked covariance in its wishart form)におけるスパースpcaの効率的なアルゴリズムについて検討した。
我々の目標は、小さな摂動に耐えつつ、最適な回復保証を達成することである。
摂動レジリエンスの明示的な研究を含む先行研究の長い歴史にもかかわらず、スパースPCAのアルゴリズム的保証は脆弱であり、小さな対向摂動の下で破壊される。
乱行列のスパース固有値上の上限値の証明に基づく摂動レジリエンスと \emph{certification algorithm} の基本的な関係を観測する。
他の手法とは対照的に、ブルート力最大確率推定器を含む証明アルゴリズムは、小さな逆摂動に対して自動的に頑健である。
この接続を用いて,乱数行列のスパース固有値上の上界に対する新しい効率的な証明を得ることにより,加法的摂動に対して弾力性のある問題に対する最初の多項式時間アルゴリズムを得る。
我々のアルゴリズムは、基本半定値プログラミングか、パラメータ規則によって強化される低次2乗和に基づいている。
それらの保証は、未知ベクトルのスパース性、サンプル数、および周囲の次元の観点から、最もよく知られた \emph{fragile} アルゴリズムの保証と一致または接近する。
アルゴリズム計算の結果を補完するため,低次多項式に基づく自然計算モデルにおいて,弱多項式時間アルゴリズムとロバスト多項式時間アルゴリズムのギャップを満たした厳密な下限を証明し,関連する統計的推定問題の最もよく知られた保証を捉えた。
これらの結果の組み合わせは、堅牢性を達成するために支払う固有の価格の正式な証拠を提供する。
関連論文リスト
- Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。
UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。
我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文 参考訳（メタデータ） (2024-05-24T04:11:58Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability [17.771354881467435]
一般化された, インスタンスに依存しないステップサイズを持つ単純なアルゴリズムは, ほぼ最適分散とバイアス項を得るのに十分であることを示す。
本手法は, 線形近似のための洗練された誤差境界と, ランダム行列の積に対する新しい安定性結果に基づく。
論文 参考訳（メタデータ） (2023-10-22T12:37:25Z) - Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement
Learning [53.445068584013896]
低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。
低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。
簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
論文 参考訳（メタデータ） (2023-10-10T17:06:41Z) - Geometry-Aware Approaches for Balancing Performance and Theoretical
Guarantees in Linear Bandits [6.907555940790131]
トンプソンサンプリングとグリーディは有望な経験的性能を示したが、これは悲観的な理論的後悔の境界とは対照的である。
本研究では不確実楕円体の幾何学的特性を追跡する新しいデータ駆動手法を提案する。
ベースアルゴリズムが不十分な問題インスタンスを特定し,コース修正する。
論文 参考訳（メタデータ） (2023-06-26T17:38:45Z) - Adversarially robust clustering with optimality guarantees [7.0830450321883935]
我々はガウス以下の混合系から得られるデータポイントをクラスタリングする問題を考察する。
ロイドアルゴリズムのような最適ラベル誤りを確実に達成する既存の手法は、通常、外れ値に対して脆弱である。
本稿では, 対数外乱が存在する場合でも, 座標中央値に基づく単純なロバストアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-16T17:17:07Z) - Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean
Estimation [8.9598796481325]
本稿では, アルゴリズムと計算複雑性の両面において, 異なる統計問題に対する観測結果について検討する。
プライベートスパース平均推定のための情報計算ギャップを確立する。
また、プライバシーによって引き起こされる情報計算のギャップを、いくつかの統計や学習問題に対して証明する。
論文 参考訳（メタデータ） (2022-11-01T20:03:41Z) - Uniform-PAC Bounds for Reinforcement Learning with Linear Function
Approximation [92.3161051419884]
線形関数近似を用いた強化学習について検討する。
既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たない。
我々はFLUTEと呼ばれる新しいアルゴリズムを提案し、高い確率で最適ポリシーへの均一PAC収束を享受する。
論文 参考訳（メタデータ） (2021-06-22T08:48:56Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。