論文の概要: Estimating Principal Components under Adversarial Perturbations
- arxiv url: http://arxiv.org/abs/2006.00602v2
- Date: Tue, 2 Jun 2020 03:31:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 12:43:37.025558
- Title: Estimating Principal Components under Adversarial Perturbations
- Title（参考訳）: 対向摂動下における主成分の推定
- Authors: Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan
- Abstract要約: 本研究では,高次元統計的推定問題に対するロバストネスの自然なモデルについて検討する。
我々のモデルは、低精度機械学習や対人訓練といった新しいパラダイムによって動機付けられている。
- 参考スコア（独自算出の注目度）: 25.778123431786653
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Robustness is a key requirement for widespread deployment of machine learning
algorithms, and has received much attention in both statistics and computer
science. We study a natural model of robustness for high-dimensional
statistical estimation problems that we call the adversarial perturbation
model. An adversary can perturb every sample arbitrarily up to a specified
magnitude $\delta$ measured in some $\ell_q$ norm, say $\ell_\infty$. Our model
is motivated by emerging paradigms such as low precision machine learning and
adversarial training.
We study the classical problem of estimating the top-$r$ principal subspace
of the Gaussian covariance matrix in high dimensions, under the adversarial
perturbation model. We design a computationally efficient algorithm that given
corrupted data, recovers an estimate of the top-$r$ principal subspace with
error that depends on a robustness parameter $\kappa$ that we identify. This
parameter corresponds to the $q \to 2$ operator norm of the projector onto the
principal subspace, and generalizes well-studied analytic notions of sparsity.
Additionally, in the absence of corruptions, our algorithmic guarantees recover
existing bounds for problems such as sparse PCA and its higher rank analogs. We
also prove that the above dependence on the parameter $\kappa$ is almost
optimal asymptotically, not just in a minimax sense, but remarkably for every
instance of the problem. This instance-optimal guarantee shows that the $q \to
2$ operator norm of the subspace essentially characterizes the estimation error
under adversarial perturbations.
- Abstract（参考訳）: ロバストネスは機械学習アルゴリズムを広く展開するための重要な要件であり、統計学とコンピュータ科学の両方で多くの注目を集めている。
逆摂動モデルと呼ばれる高次元統計的推定問題に対するロバストネスの自然なモデルについて検討する。
例えば$\ell_\infty$というような$\ell_q$ノルムで測定された$\delta$まで任意にすべてのサンプルを乱すことができる。
我々のモデルは、低精度機械学習や逆行訓練のような新しいパラダイムに動機づけられている。
逆摂動モデルの下でガウス共分散行列のトップ$r$主部分空間を高次元で推定する古典的な問題について検討する。
劣化したデータを与えられた計算効率の高いアルゴリズムを設計し、我々が同定したロバスト性パラメータ$\kappa$に依存するエラーによりトップ$r$主部分空間の推定を復元する。
このパラメータは、主部分空間上のプロジェクタの$q \to 2$演算子ノルムに対応し、よく研究されたスパーシティの解析的概念を一般化する。
さらに, 汚職の欠如により, スパースPCAや上位アナログなどの問題に対して, 既存の境界の回復が保証される。
また、上記のパラメータ $\kappa$ への依存性は、minimax の意味でだけでなく、問題のすべての例において、ほとんど最適漸近的であることも証明する。
このインスタンス最適化保証は、サブスペースの$q \to 2$演算ノルムが本質的に逆の摂動による推定誤差を特徴づけていることを示している。
関連論文リスト
- Differentially Private Learning Beyond the Classical Dimensionality Regime [19.030954416586596]
比例次元の体系における差分私的学習について研究する。
いくつかのよく研究された微分プライベートアルゴリズムの誤差を鋭く理論的に推定する。
論文 参考訳（メタデータ） (2024-11-20T19:56:12Z) - Wasserstein Distributionally Robust Multiclass Support Vector Machine [1.8570591025615457]
データの特徴が $mathbfx$ であり,そのラベルが $mathbfy$ であるような設定におけるマルチクラス分類の問題について検討する。
我々は、分散ロバストな最適化を用いて、クラマー・シンガー(CS)損失を特徴とするマルチクラスサポートベクターマシン(SVM)のロバストバージョンを開発する。
我々の数値実験は、トレーニングデータが高度に不均衡な環境で、我々のモデルが最先端のOVAモデルより優れていることを示す。
論文 参考訳（メタデータ） (2024-09-12T21:40:04Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Sparse PCA with Oracle Property [115.72363972222622]
新規な正規化を伴うスパースPCAの半定緩和に基づく推定器群を提案する。
我々は、家族内の別の推定器が、スパースPCAの標準半定緩和よりも、より急激な収束率を達成することを証明した。
論文 参考訳（メタデータ） (2023-12-28T02:52:54Z) - On the Identifiability and Estimation of Causal Location-Scale Noise
Models [122.65417012597754]
位置スケール・異方性雑音モデル(LSNM)のクラスについて検討する。
症例によっては, 因果方向が同定可能であることが示唆された。
我々は,LSNMの2つの推定器を提案し,その1つは(非線形)特徴写像に基づく推定器と,1つはニューラルネットワークに基づく推定器を提案する。
論文 参考訳（メタデータ） (2022-10-13T17:18:59Z) - Consistent Estimation for PCA and Sparse Regression with Oblivious
Outliers [13.244654316770815]
我々は効率よく計算可能で一貫した推定器を設計する機械を開発する。
スパース回帰では、最適なサンプルサイズ$ngsim (klog d)/alpha2$の整合性を達成する。
PCAの文脈では、パラメータ行列上の広いスパイキネス仮定の下で最適な誤差を保証する。
論文 参考訳（メタデータ） (2021-11-04T15:59:44Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Sharp Statistical Guarantees for Adversarially Robust Gaussian
Classification [54.22421582955454]
逆向きに頑健な分類の過剰リスクに対する最適ミニマックス保証の最初の結果を提供する。
結果はAdvSNR(Adversarial Signal-to-Noise Ratio)の項で述べられており、これは標準的な線形分類と逆数設定との類似の考え方を一般化している。
論文 参考訳（メタデータ） (2020-06-29T21:06:52Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - A Precise High-Dimensional Asymptotic Theory for Boosting and
Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。
統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。
また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
論文 参考訳（メタデータ） (2020-02-05T00:24:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。