論文の概要: Online Differentially Private Synthetic Data Generation
- arxiv url: http://arxiv.org/abs/2402.08012v1
- Date: Mon, 12 Feb 2024 19:21:14 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 17:40:15.748034
- Title: Online Differentially Private Synthetic Data Generation
- Title(参考訳): オンライン微分プライベート合成データ生成
- Authors: Yiyun He, Roman Vershynin, Yizhe Zhu
- Abstract要約: 差分プライベートな合成データセットを毎回$t$で生成するオンラインアルゴリズムを開発した。
このアルゴリズムは、$O(t-1/dlog(t))$ for $dgeq 2$と$O(t-1log4.5(t))$ for $d=1$の近似精度を1-ワッサーシュタイン距離で達成する。
- 参考スコア(独自算出の注目度): 11.438537476739633
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a polynomial-time algorithm for online differentially private
synthetic data generation. For a data stream within the hypercube $[0,1]^d$ and
an infinite time horizon, we develop an online algorithm that generates a
differentially private synthetic dataset at each time $t$. This algorithm
achieves a near-optimal accuracy bound of $O(t^{-1/d}\log(t))$ for $d\geq 2$
and $O(t^{-1}\log^{4.5}(t))$ for $d=1$ in the 1-Wasserstein distance. This
result generalizes the previous work on the continual release model for
counting queries to include Lipschitz queries. Compared to the offline case,
where the entire dataset is available at once, our approach requires only an
extra polylog factor in the accuracy bound.
- Abstract(参考訳): オンライン微分プライベート合成データ生成のための多項式時間アルゴリズムを提案する。
ハイパーキューブの$[0,1]^d$と無限の時間軸内のデータストリームに対して、各時刻に差動的にプライベートな合成データセットを生成するオンラインアルゴリズムを開発した。
このアルゴリズムは、$O(t^{-1/d}\log(t))$ for $d\geq 2$ and $O(t^{-1}\log^{4.5}(t))$ for $d=1$ in the 1-Wasserstein distanceである。
この結果は、Lipschitzクエリを含むクエリをカウントする継続リリースモデルに関する以前の作業を一般化する。
データセット全体が一度に利用可能となるオフラインの場合と比較して、我々のアプローチは精度境界に追加のポリログ係数しか必要としない。
関連論文リスト
- Online Algorithms with Limited Data Retention [4.101276693704335]
データ保持に関する厳密な制約を受けるオンラインアルゴリズムのモデルを導入する。
我々は,全てのデータをできるだけ長く保持するベースラインアルゴリズムよりも指数関数的に改善できることを示す。
我々の結果の1つの意味は、データ保持法は忘れられる権利を保証するのに不十分であるということだ。
論文 参考訳(メタデータ) (2024-04-17T02:17:23Z) - Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳(メタデータ) (2023-07-14T16:11:22Z) - 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) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Efficient Mean Estimation with Pure Differential Privacy via a
Sum-of-Squares Exponential Mechanism [16.996435043565594]
純微分プライバシーを受ける独立サンプルの共分散で$d$正確率分布の平均を推定するアルゴリズムを初めて与える。
我々の主な手法は、強力なSum of Squares法(SoS)を用いて微分プライベートアルゴリズムを設計する新しいアプローチである。
論文 参考訳(メタデータ) (2021-11-25T09:31:15Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳(メタデータ) (2021-03-02T06:53:44Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳(メタデータ) (2020-11-19T17:21:37Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳(メタデータ) (2020-11-11T17:48:00Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z) - A Deterministic Streaming Sketch for Ridge Regression [15.256452294422294]
リッジ回帰を推定するための決定論的空間効率アルゴリズムを提案する。
これは、ソリューションエラーが保証された最初の$o(d2)$空間決定論的ストリーミングアルゴリズムである。
合成データセットと実世界のデータセットのランダムなスケッチアルゴリズムと比較して、我々のアルゴリズムは空間と類似時間が少なくて経験的誤差が少ない。
論文 参考訳(メタデータ) (2020-02-05T22:08:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。