論文の概要: Private Robust Estimation by Stabilizing Convex Relaxations
- arxiv url: http://arxiv.org/abs/2112.03548v1
- Date: Tue, 7 Dec 2021 07:47:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-08 14:27:15.143955
- Title: Private Robust Estimation by Stabilizing Convex Relaxations
- Title（参考訳）: 安定化凸緩和によるプライベートロバスト推定
- Authors: Pravesh K. Kothari, Pasin Manurangsi, Ameya Velingker
- Abstract要約: $(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
- 参考スコア（独自算出の注目度）: 22.513117502159922
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give the first polynomial time and sample $(\epsilon,
\delta)$-differentially private (DP) algorithm to estimate the mean, covariance
and higher moments in the presence of a constant fraction of adversarial
outliers. Our algorithm succeeds for families of distributions that satisfy two
well-studied properties in prior works on robust estimation: certifiable
subgaussianity of directional moments and certifiable hypercontractivity of
degree 2 polynomials. Our recovery guarantees hold in the "right
affine-invariant norms": Mahalanobis distance for mean, multiplicative spectral
and relative Frobenius distance guarantees for covariance and injective norms
for higher moments. Prior works obtained private robust algorithms for mean
estimation of subgaussian distributions with bounded covariance. For covariance
estimation, ours is the first efficient algorithm (even in the absence of
outliers) that succeeds without any condition-number assumptions.
Our algorithms arise from a new framework that provides a general blueprint
for modifying convex relaxations for robust estimation to satisfy strong
worst-case stability guarantees in the appropriate parameter norms whenever the
algorithms produce witnesses of correctness in their run. We verify such
guarantees for a modification of standard sum-of-squares (SoS) semidefinite
programming relaxations for robust estimation. Our privacy guarantees are
obtained by combining stability guarantees with a new "estimate dependent"
noise injection mechanism in which noise scales with the eigenvalues of the
estimated covariance. We believe this framework will be useful more generally
in obtaining DP counterparts of robust estimators.
Independently of our work, Ashtiani and Liaw [AL21] also obtained a
polynomial time and sample private robust estimation algorithm for Gaussian
distributions.
- Abstract（参考訳）: 最初の多項式時間とサンプル$(\epsilon, \delta)$-differentially private (DP) アルゴリズムを与え、正反対の外れ値の一定割合の存在下での平均、共分散および高次モーメントを推定する。
本アルゴリズムは, 配向モーメントの証明可能な部分ガウス性, 次数2多項式の証明可能な超収縮率という, 先行研究でよく研究された2つの特性を満たす分布の族に成功している。
平均、乗法スペクトルおよび相対フロベニウス距離に対するマハラノビス距離は、共分散および高モーメントの単射ノルムに対して保証される。
先行研究は、有界共分散を持つ部分ガウス分布の平均推定のためのプライベートロバストアルゴリズムを得た。
共分散推定では、条件数仮定なしで成功する最初の効率的なアルゴリズム(外乱のない場合でも)である。
我々のアルゴリズムは、アルゴリズムが実行中に正当性の証人を生成するたびに、適切なパラメータノルムにおいて、強い最悪の安定性を保証するために、堅牢な推定のために凸緩和を修正するための一般的な青写真を提供する新しいフレームワークから生じる。
このような保証は、ロバストな推定のための半定値プログラミング緩和の標準和和(SoS)の修正に対して検証される。
我々のプライバシー保証は、安定性保証と、推定共分散の固有値にノイズがスケールする新しい「見積依存」ノイズ注入機構を組み合わせることで得られる。
我々は、このフレームワークが、より一般的に、堅牢な推定器のDP版を得るのに役立つと信じている。
我々の研究とは独立に、Ashtiani と Liaw [AL21] も多項式時間とガウス分布のサンプル頑健性推定アルゴリズムを得た。
関連論文リスト
- An Inexact Halpern Iteration with Application to Distributionally Robust
Optimization [9.529117276663431]
決定論的および決定論的収束設定におけるスキームの不正確な変種について検討する。
不正確なスキームを適切に選択することにより、(予想される)剰余ノルムの点において$O(k-1)収束率を許容することを示す。
論文 参考訳（メタデータ） (2024-02-08T20:12:47Z) - Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。
本手法は, 精度の高い問題に特に適している。
提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
論文 参考訳（メタデータ） (2023-11-08T00:10:21Z) - Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。
純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。
平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文 参考訳（メタデータ） (2022-12-15T18:27:39Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳（メタデータ） (2022-11-29T05:52:17Z) - Boosting the Confidence of Generalization for $L_2$-Stable Randomized
Learning Algorithms [41.082982732100696]
適切に設計されたサブバッグプロセスは、データとアルゴリズムの両方にほぼ28の指数関数的一般化バウンダリをもたらすことを示す。
さらに、自然減衰学習率を持つ凸問題や非重み付き問題に対する高確率一般化境界を改善するために、総合的な結果を導出する。
論文 参考訳（メタデータ） (2022-06-08T12:14:01Z) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳（メタデータ） (2022-05-05T06:43:46Z) - Robust Estimation for Nonparametric Families via Generative Adversarial
Networks [92.64483100338724]
我々は,高次元ロバストな統計問題を解くためにGAN(Generative Adversarial Networks)を設計するためのフレームワークを提供する。
我々の研究は、これらをロバスト平均推定、第二モーメント推定、ロバスト線形回帰に拡張する。
技術面では、提案したGAN損失は、スムーズで一般化されたコルモゴロフ-スミルノフ距離と見なすことができる。
論文 参考訳（メタデータ） (2022-02-02T20:11:33Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Differentially private inference via noisy optimization [3.015622397986615]
本研究では, 雑音勾配降下法や雑音の強いニュートン法と併用して, 最適な個人推定値が得られることを示す。
シミュレーションにおける小サンプル実験性能の向上につながるバイアス補正の有効性を実証する。
論文 参考訳（メタデータ） (2021-03-19T19:55:55Z) - Outlier Robust Mean Estimation with Subgaussian Rates via Stability [46.03021473600576]
本研究では,ロバストなアウトリール高次元平均推定問題について検討する。
外乱平均推定のために, ガウス平均を用いた第1次計算効率を得る。
論文 参考訳（メタデータ） (2020-07-30T17:33:03Z) - Distributional Robustness and Regularization in Reinforcement Learning [62.23012916708608]
経験値関数の新しい正規化器を導入し、ワッサーシュタイン分布のロバストな値関数を下限とすることを示す。
強化学習における$textitexternalな不確実性に対処するための実用的なツールとして正規化を使用することを提案する。
論文 参考訳（メタデータ） (2020-03-05T19:56:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。