スパースPCA:アルゴリズム,敵対摂動および証明書【JST・京大機械翻訳】

d'Orsi Tommaso; Kothari Pravesh K.; Novikov Gleb; Steurer David

プレプリント

J-GLOBAL ID：202202202592167596 整理番号：22P0209245

スパースPCA:アルゴリズム,敵対摂動および証明書【JST・京大機械翻訳】

Sparse PCA: Algorithms, Adversarial Perturbations and Certificates

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (4件)： , , ,
資料名：
発行年： 2020年11月12日プレプリントサーバーでの情報更新日： 2020年11月12日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

標準統計モデル(そのWishart形式におけるスパイク共分散)におけるスパースPCAのための効率的なアルゴリズムを研究した。著者らの目標は,小さな摂動に対して弾力性がある間,最適回復保証を達成することである。摂動レジリエンスの明示的研究を含む以前の研究の長い歴史にもかかわらず,Sparse PCAのための最良の既知のアルゴリズム保証は,小さな敵対摂動の下で脆弱で壊れる。ランダム行列のスパース固有値に関する上限の証明書に基づく摂動レジリエンスと認証アルゴリズムの間の基本的結合を観察した。他の技術とは対照的に, br力最大尤度推定器を含むそのような証明アルゴリズムは,小さな敵対摂動に対して自動的にロバストである。この接続を用いて,ランダム行列のスパース固有値上の上限に対する新しい効率的な証明書を得ることにより,付加的敵対摂動に対して弾力性があるこの問題に対する最初の多項式時間アルゴリズムを得た。著者らのアルゴリズムは,基本半定値プログラミングまたはパラメータ領域に依存するその低度和二乗強化に基づいている。それらの保証は,未知ベクトルのスパース性,サンプル数,および周囲次元に関して,最良に知られている保証を,最良に保証する。著者らのアルゴリズム結果を補完するために,関連する統計的推定問題に対する最良の既知保証を捉えることが知られている,低度多項式に基づく自然計算モデルにおける脆弱性とロバスト多項式時間アルゴリズムの間のギャップをマッチングする厳密な下限を証明した。これらの結果の組合せは,ロバスト性を達成するために固有の価格の正式な証拠を与える。【JST・京大機械翻訳】

, , , , , , , , , , , ,
, , , 【Automatic Indexing@JST】

信号理論 , 人工知能 , 計算理論

, , , ,

前のページに戻る