論文の概要: Sample-Optimal Private Regression in Polynomial Time
- arxiv url: http://arxiv.org/abs/2503.24321v1
- Date: Mon, 31 Mar 2025 17:08:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-01 14:37:23.944679
- Title: Sample-Optimal Private Regression in Polynomial Time
- Title（参考訳）: ポリノミアル時間におけるサンプル最適プライベート回帰
- Authors: Prashanti Anderson, Ainesh Bakshi, Mahbod Majid, Stefan Tiegel,
- Abstract要約: アルゴリズムのサンプル複雑性の改善は,統計的クエリや情報理論的下位境界に反することを示した。
アルゴリズムは任意の外れ値の小さな部分に対して頑健であり、外れ値の小さな部分の関数として最適誤差率を達成する。
- 参考スコア（独自算出の注目度）: 3.3748750222488657
- License:
- Abstract: We consider the task of privately obtaining prediction error guarantees in ordinary least-squares regression problems with Gaussian covariates (with unknown covariance structure). We provide the first sample-optimal polynomial time algorithm for this task under both pure and approximate differential privacy. We show that any improvement to the sample complexity of our algorithm would violate either statistical-query or information-theoretic lower bounds. Additionally, our algorithm is robust to a small fraction of arbitrary outliers and achieves optimal error rates as a function of the fraction of outliers. In contrast, all prior efficient algorithms either incurred sample complexities with sub-optimal dimension dependence, scaling with the condition number of the covariates, or obtained a polynomially worse dependence on the privacy parameters. Our technical contributions are two-fold: first, we leverage resilience guarantees of Gaussians within the sum-of-squares framework. As a consequence, we obtain efficient sum-of-squares algorithms for regression with optimal robustness rates and sample complexity. Second, we generalize the recent robustness-to-privacy framework [HKMN23, (arXiv:2212.05015)] to account for the geometry induced by the covariance of the input samples. This framework crucially relies on the robust estimators to be sum-of-squares algorithms, and combining the two steps yields a sample-optimal private regression algorithm. We believe our techniques are of independent interest, and we demonstrate this by obtaining an efficient algorithm for covariance-aware mean estimation, with an optimal dependence on the privacy parameters.
- Abstract（参考訳）: 正規の最小二乗回帰問題における予測誤差保証をガウス共変量(共分散構造不明)でプライベートに取得する作業について考察する。
本稿では,この課題に対して,純粋および近似微分プライバシーの両面において,最初のサンプル最適多項式時間アルゴリズムを提案する。
アルゴリズムのサンプル複雑性の改善は,統計的クエリや情報理論的下位境界に反することを示した。
さらに,アルゴリズムは任意の外れ値のごく一部に対して頑健であり,外れ値の比率の関数として最適誤差率を達成する。
対照的に、全ての事前の効率的なアルゴリズムは、準最適次元依存性を持つサンプル複素数、共変量の条件数によるスケーリング、またはプライバシーパラメータに対する多項式的に悪い依存を得るかのいずれかである。
まず、二乗フレームワーク内のガウスのレジリエンス保証を活用します。
その結果、最適なロバスト性率とサンプル複雑性を有する回帰のための効率的な2乗和アルゴリズムが得られた。
第2に、最近のロバストネス・アンド・プライバシ・フレームワーク(HKMN23, (arXiv:2212.05015))を一般化し、入力サンプルの共分散によって引き起こされる幾何を考慮した。
このフレームワークは、頑健な推定器を2乗のアルゴリズムに頼り、この2つのステップを組み合わせることで、サンプル最適化プライベート回帰アルゴリズムが得られる。
我々は,この手法が独立した関心事であると信じており,プライバシーパラメータに最適に依存する共分散を考慮した平均推定のための効率的なアルゴリズムを得ることによってこれを実証している。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Robustness Implies Privacy in Statistical Estimation [16.061651295129302]
本研究では,高次元統計学における敵のプライバシーと差分プライバシーの関係について検討する。
プライバシーから堅牢性への最初のブラックボックスの削減は、最適なトレードオフを伴うプライベートな推定器を生み出すことができる。
また, アルゴリズムは, ほぼ最適に崩壊したサンプルに対して頑健である。
論文 参考訳（メタデータ） (2022-12-09T18:07:30Z) - Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean
Estimation [8.9598796481325]
本稿では, アルゴリズムと計算複雑性の両面において, 異なる統計問題に対する観測結果について検討する。
プライベートスパース平均推定のための情報計算ギャップを確立する。
また、プライバシーによって引き起こされる情報計算のギャップを、いくつかの統計や学習問題に対して証明する。
論文 参考訳（メタデータ） (2022-11-01T20:03:41Z) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳（メタデータ） (2022-05-05T06:43:46Z) - Private Robust Estimation by Stabilizing Convex Relaxations [22.513117502159922]
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
論文 参考訳（メタデータ） (2021-12-07T07:47:37Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Sparse PCA: Algorithms, Adversarial Perturbations and Certificates [9.348107805982604]
標準統計モデルにおけるスパースPCAの効率的なアルゴリズムについて検討する。
私たちのゴールは、小さな摂動に耐性を持ちながら、最適な回復保証を達成することです。
論文 参考訳（メタデータ） (2020-11-12T18:58:51Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳（メタデータ） (2020-05-22T22:30:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。