論文の概要: Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares
- arxiv url: http://arxiv.org/abs/2404.15409v1
- Date: Tue, 23 Apr 2024 18:00:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-25 15:23:04.548791
- Title: Insufficient Statistics Perturbation: Stable Estimators for Private Least Squares
- Title(参考訳): 不十分な統計摂動:プライベートリーストスクエアの安定推定器
- Authors: Gavin Brown, Jonathan Hayase, Samuel Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C. Perdomo, Adam Smith,
- Abstract要約: 通常の最小二乗に対するサンプルと時間効率の微分プライベートアルゴリズムを提案する。
私たちのほぼ最適精度は、条件番号または指数時間を持つデータセットに対して保持します。
- 参考スコア(独自算出の注目度): 38.478776450327125
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a sample- and time-efficient differentially private algorithm for ordinary least squares, with error that depends linearly on the dimension and is independent of the condition number of $X^\top X$, where $X$ is the design matrix. All prior private algorithms for this task require either $d^{3/2}$ examples, error growing polynomially with the condition number, or exponential time. Our near-optimal accuracy guarantee holds for any dataset with bounded statistical leverage and bounded residuals. Technically, we build on the approach of Brown et al. (2023) for private mean estimation, adding scaled noise to a carefully designed stable nonprivate estimator of the empirical regression vector.
- Abstract(参考訳): 通常の最小二乗に対するサンプルおよび時間効率の微分プライベートアルゴリズムを提案し、誤差は次元に線形に依存し、X^\top X$の条件数とは独立であり、ここでは設計行列が$X$である。
このタスクの全ての以前のプライベートアルゴリズムは、$d^{3/2}$例、条件数と多項式的に誤差が増加すること、指数時間を必要とする。
我々の準最適精度保証は、統計レバレッジと有界残差を持つ任意のデータセットに対して成り立つ。
技術的には、プライベート平均推定のためのBrown et al (2023) のアプローチに基づいて、慎重に設計された経験的回帰ベクトルの安定な非プライベート推定器にスケールドノイズを付加する。
関連論文リスト
- On Differentially Private U Statistics [25.683071759227293]
局所的なH'ajekプロジェクションを用いて、データの異なる部分集合を再重み付けする新しいしきい値に基づくアプローチを提案する。
これは、非退化U統計に対してほぼ最適なプライベート誤差をもたらし、退化U統計に対してほぼ最適であることを示す強い指標となる。
論文 参考訳(メタデータ) (2024-07-06T03:27:14Z) - Private Gradient Descent for Linear Regression: Tighter Error Bounds and
Instance-Specific Uncertainty Estimation [17.84129947587373]
正方形誤差損失下での線形回帰に対する標準偏差偏差勾配勾配の解析を改良した。
我々の分析はアルゴリズムの精度に新たな結果をもたらす。
論文 参考訳(メタデータ) (2024-02-21T04:58:41Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳(メタデータ) (2023-01-31T18:47:42Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳(メタデータ) (2023-01-11T09:12:28Z) - 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) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳(メタデータ) (2022-05-05T06:43:46Z) - Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected
Error [0.3997680012976965]
目標は、最悪の予測エラーを最小限に抑える推定器を設計することである。
Chen, Valiant および Valiant は、データ値が $ell_infty$-normalized の場合、平均の推定値を計算する時間アルゴリズムが存在することを示した。
本稿では,オンライン凸最適化に基づく最適半線形推定器の近似アルゴリズムを設計する。
論文 参考訳(メタデータ) (2021-12-27T18:47:25Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳(メタデータ) (2021-02-23T18:25:13Z) - Strongly universally consistent nonparametric regression and
classification with privatised data [2.879036956042183]
非パラメトリック回帰の古典的問題を再考するが、局所的な差分プライバシー制約を課す。
我々は回帰関数の新しい推定器を設計し、よく研究された分割回帰推定器の民営版とみなすことができる。
論文 参考訳(メタデータ) (2020-10-31T09:00:43Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳(メタデータ) (2020-05-22T22:30:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。