論文の概要: A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input
- arxiv url: http://arxiv.org/abs/2505.14251v1
- Date: Tue, 20 May 2025 12:04:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-21 14:49:53.155504
- Title: A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input
- Title（参考訳）: サブサンプル入力の第2モーメント行列のプライベート近似
- Authors: Bar Mahpud, Or Sheffet,
- Abstract要約: 差分プライベートな第2モーメント推定の問題について検討し、強力なプライバシー利用トレードオフを実現する新しいアルゴリズムを提案する。
入力の顕著な割合が外れた場合でも、分布$mathcalD$の2モーメント行列を近似するためにアルゴリズムを適用する方法を示す。
- 参考スコア（独自算出の注目度）: 10.128808054306187
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of differentially private second moment estimation and present a new algorithm that achieve strong privacy-utility trade-offs even for worst-case inputs under subsamplability assumptions on the data. We call an input $(m,\alpha,\beta)$-subsamplable if a random subsample of size $m$ (or larger) preserves w.p $\geq 1-\beta$ the spectral structure of the original second moment matrix up to a multiplicative factor of $1\pm \alpha$. Building upon subsamplability, we give a recursive algorithmic framework similar to Kamath et al 2019, that abides zero-Concentrated Differential Privacy (zCDP) while preserving w.h.p. the accuracy of the second moment estimation upto an arbitrary factor of $(1\pm\gamma)$. We then show how to apply our algorithm to approximate the second moment matrix of a distribution $\mathcal{D}$, even when a noticeable fraction of the input are outliers.
- Abstract（参考訳）: 差分プライベートな第2モーメント推定の問題について検討し、データに対するサブサンプリング可能性仮定の下で最悪の入力であっても、強力なプライバシー利用トレードオフを実現する新しいアルゴリズムを提案する。
入力 $(m,\alpha,\beta)$-subsamplable (m$ (またはそれ以上) が w.p $\geq 1-\beta$ を保存するとき、入力 $(m,\alpha,\beta)$-subsamplable と呼ばれる。
サブサンプリング性に基づいて、我々は、ゼロ集中微分プライバシー(zCDP)を回避しつつ、第2モーメント推定の精度を1\pm\gamma(英語版)$まで保ちながら、Kamathらと似た再帰的なアルゴリズムフレームワークを提供する。
次に、入力の顕著な割合が外れた場合でも、分布 $\mathcal{D}$ の第二モーメント行列を近似するためにアルゴリズムを適用する方法を示す。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
複数のサンプルを持つ場合の個人レベルの個人別平均推定について検討した。
我々は、計算効率のよいアルゴリズムを、純粋DPで、計算効率の悪いアルゴリズムを、ほぼ一致する下界は、近似DPの最も寛容な場合を抑える。
論文 参考訳（メタデータ） (2024-05-30T18:20:35Z) - Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳（メタデータ） (2024-02-24T06:36:08Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Robust Sub-Gaussian Principal Component Analysis and Width-Independent
Schatten Packing [22.337756118270217]
基本統計量に対する2つの方法を開発した:$epsilon$-corrupted set of $n$ sample from a $d$-linear sub-Gaussian distribution。
最初のロバストなアルゴリズムは反復フィルタリングを時間内に実行し、近似固有ベクトルを返し、単純なフィルタリングアプローチに基づいている。
私たちの2つめは、わずかに悪い近似係数を達成し、軽度のスペクトルギャップ仮定の下でほぼ自明な時間とイテレーションで実行します。
論文 参考訳（メタデータ） (2020-06-12T07:45:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。