論文の概要: Enhancing Trade-offs in Privacy, Utility, and Computational Efficiency
through MUltistage Sampling Technique (MUST)
- arxiv url: http://arxiv.org/abs/2312.13389v1
- Date: Wed, 20 Dec 2023 19:38:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-22 16:50:03.788106
- Title: Enhancing Trade-offs in Privacy, Utility, and Computational Efficiency
through MUltistage Sampling Technique (MUST)
- Title(参考訳): MUST(Multistage Smpling Technique)によるプライバシ、ユーティリティ、計算効率のトレードオフの強化
- Authors: Xingyuan Zhao, Fang Liu
- Abstract要約: プライバシ・アンプリフィケーション(PA)のためのMUST(MUST)と呼ばれるサブサンプリング手法のクラスを提案する。
本稿では,2段階のMUST手順,すなわちMUST.WO,MUST.OW,MUST.WWに対して,PA効果と実用性を包括的に分析する。
以上の結果から,MUST.OWとMUST.WWは1段サンプリング法よりも,エプシロン$が強いことが示唆された。
- 参考スコア(独自算出の注目度): 4.107946593741216
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Applying a randomized algorithm to a subset of a dataset rather than the
entire dataset is a common approach to amplify its privacy guarantees in the
released information. We propose a class of subsampling methods named
MUltistage Sampling Technique (MUST) for privacy amplification (PA) in the
context of differential privacy (DP). We conduct comprehensive analyses of the
PA effects and utility for several 2-stage MUST procedures, namely, MUST.WO,
MUST.OW, and MUST.WW that respectively represent sampling with (W), without
(O), with (W) replacement from the original dataset in stage I and then
sampling without (O), with (W), with (W) replacement in stage II from the
subset drawn in stage I. We also provide the privacy composition analysis over
repeated applications of MUST via the Fourier accountant algorithm. Our
theoretical and empirical results suggest that MUST.OW and MUST.WW have
stronger PA in $\epsilon$ than the common one-stage sampling procedures
including Poisson sampling, sampling without replacement, and sampling with
replacement, while the results on $\delta$ vary case by case. We also prove
that MUST.WO is equivalent to sampling with replacement in PA. Furthermore, the
final subset generated by a MUST procedure is a multiset that may contain
multiple copies of the same data points due to sampling with replacement
involved, which enhances the computational efficiency of algorithms that
require complex function calculations on distinct data points (e.g., gradient
descent). Our utility experiments show that MUST delivers similar or improved
utility and stability in the privacy-preserving outputs compared to one-stage
subsampling methods at similar privacy loss. MUST can be seamlessly integrated
into stochastic optimization algorithms or procedures that involve parallel or
simultaneous subsampling (e.g., bagging and subsampling bootstrap) when DP
guarantees are necessary.
- Abstract(参考訳): データセット全体ではなくデータセットのサブセットにランダム化アルゴリズムを適用することは、リリース情報におけるプライバシの保証を強化する一般的なアプローチである。
差分プライバシー(DP)の文脈において,プライバシ増幅(PA)のためのMUST(MUltistage Smpling Technique)というサブサンプリング手法のクラスを提案する。
2段階の必須手続きである must.wo, must.ow, must.ww を,それぞれ (w), without (o), with (w) でサンプリングし, (o), without (w) でサンプリングし, stage i で描画された部分集合から stage ii で (w) を置換して,pa 効果と有用性を包括的に解析する。
また、フーリエ会計アルゴリズムを用いてMUSTの繰り返し適用に関するプライバシー構成分析を行う。
理論的および実証的な結果から,MUST.OWとMUST.WWのPA値が,ポアソンサンプリング,交換なしサンプリング,置換によるサンプリングを含む一般的な1段階サンプリング法よりも強いことが示唆された。
また、MUST.WOはPAで置換したサンプリングと等価であることを示す。
さらに、MUSTプロシージャによって生成される最後のサブセットはマルチセットであり、同一のデータポイントの複数のコピーを含むことができるため、異なるデータポイント(例えば勾配降下)で複雑な関数計算を必要とするアルゴリズムの計算効率が向上する。
我々のユーティリティ実験は、MUSTが同様の、または改善されたユーティリティと安定性をプライバシー保護出力で提供することを示す。
MUSTは、DP保証が必要な場合、並列または同時サブサンプリング(例えば、バッグとサブサンプリングブートストラップ)を含む確率最適化アルゴリズムや手順にシームレスに統合することができる。
関連論文リスト
- Weighted Sparse Partial Least Squares for Joint Sample and Feature
Selection [7.219077740523681]
本稿では, 共同サンプルと特徴選択のために, $ell_infty/ell_0$-norm制約付きスパースPSS(ell_infty/ell_$-wsPLS)法を提案する。
我々は,各マルチビューwsPLSモデルに対して効率的な反復アルゴリズムを開発し,その収束性を示す。
論文 参考訳(メタデータ) (2023-08-13T10:09:25Z) - One-Dimensional Deep Image Prior for Curve Fitting of S-Parameters from
Electromagnetic Solvers [57.441926088870325]
Deep Image Prior(ディープ・イメージ・プライオリ、ディープ・イメージ・プライオリ、DIP)は、ランダムなd畳み込みニューラルネットワークの重みを最適化し、ノイズや過度な測定値からの信号に適合させる技術である。
本稿では,Vector Fitting (VF) の実装に対して,ほぼすべてのテスト例において優れた性能を示す。
論文 参考訳(メタデータ) (2023-06-06T20:28:37Z) - Conformal Frequency Estimation using Discrete Sketched Data with
Coverage for Distinct Queries [35.67445122503686]
本稿では、非常に大きな離散データセットにおいて、問合せ対象の周波数に対する信頼区間を構築するための共形推論手法を開発する。
提案手法は,シミュレーションにおける既存の頻繁主義者やベイズ的な代替手法と比較して,経験的性能が向上したことを示す。
論文 参考訳(メタデータ) (2022-11-09T00:05:29Z) - Towards Automated Imbalanced Learning with Deep Hierarchical
Reinforcement Learning [57.163525407022966]
不均衡学習はデータマイニングにおいて基本的な課題であり、各クラスにトレーニングサンプルの不均等な比率が存在する。
オーバーサンプリングは、少数民族のための合成サンプルを生成することによって、不均衡な学習に取り組む効果的な手法である。
我々は,異なるレベルの意思決定を共同で最適化できる自動オーバーサンプリングアルゴリズムであるAutoSMOTEを提案する。
論文 参考訳(メタデータ) (2022-08-26T04:28:01Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳(メタデータ) (2021-06-29T12:49:54Z) - Improved, Deterministic Smoothing for L1 Certified Robustness [119.86676998327864]
分割雑音を伴う非加法的決定論的平滑化法(dssn)を提案する。
一様加法平滑化とは対照的に、ssn認証は無作為なノイズコンポーネントを独立に必要としない。
これは、規範ベースの敵対的脅威モデルに対して決定論的「ランダム化平滑化」を提供する最初の仕事である。
論文 参考訳(メタデータ) (2021-03-17T21:49:53Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - On sampling from data with duplicate records [6.552205517927228]
複製の有無でデータベースに存在するエンティティの集合から一様にサンプリングする手順を開発する。
最初のステップでは、データベース内の全てのエンティティの周波数を推定します。
第2のステップでは、リジェクションサンプリングを使用して、エンティティの集合から一様サンプルを得る。
論文 参考訳(メタデータ) (2020-08-24T16:41:47Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳(メタデータ) (2020-04-23T05:00:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。