論文の概要: Faster Privacy Accounting via Evolving Discretization
- arxiv url: http://arxiv.org/abs/2207.04381v1
- Date: Sun, 10 Jul 2022 04:25:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-12 16:22:26.523319
- Title: Faster Privacy Accounting via Evolving Discretization
- Title（参考訳）: 離散化の進化による高速なプライバシ会計
- Authors: Badih Ghazi and Pritish Kamath and Ravi Kumar and Pasin Manurangsi
- Abstract要約: プライバシランダム変数の数値合成のための新しいアルゴリズムを提案する。
本アルゴリズムは,メカニズムを自己コンパイルするタスクに対して,$mathrmpolylog(k)$の実行時間とメモリ使用量を達成する。
- 参考スコア（独自算出の注目度）: 54.32252900997422
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce a new algorithm for numerical composition of privacy random
variables, useful for computing the accurate differential privacy parameters
for composition of mechanisms. Our algorithm achieves a running time and memory
usage of $\mathrm{polylog}(k)$ for the task of self-composing a mechanism, from
a broad class of mechanisms, $k$ times; this class, e.g., includes the
sub-sampled Gaussian mechanism, that appears in the analysis of differentially
private stochastic gradient descent. By comparison, recent work by Gopi et al.
(NeurIPS 2021) has obtained a running time of $\widetilde{O}(\sqrt{k})$ for the
same task. Our approach extends to the case of composing $k$ different
mechanisms in the same class, improving upon their running time and memory
usage from $\widetilde{O}(k^{1.5})$ to $\widetilde{O}(k)$.
- Abstract（参考訳）: そこで本稿では,プライバシ・ランダム変数の数値構成のための新しいアルゴリズムを提案する。
このアルゴリズムは、メカニズムを自己合成するタスクに対して、実行時間およびメモリ使用量として$\mathrm{polylog}(k)$ を、幅広いメカニズムクラスから$k$ times で達成する。
これに対して、Gopiらによる最近の研究(NeurIPS 2021)は、同じタスクに対して$\widetilde{O}(\sqrt{k})$のランニングタイムを得た。
我々のアプローチは、同じクラスで$k$の異なるメカニズムを構成する場合に拡張され、実行時間とメモリ使用量を$\widetilde{O}(k^{1.5})$から$\widetilde{O}(k)$に改善します。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning [2.2083091880368855]
差分的にプライベートな$k$選択問題について検討し、$d$アイテムから最も高いスコアを持つ$k$アイテムの列を特定することを目的とした。
Gillenwaterらによる最近の研究(ICML '22)は、$d,Theta(k)$ possible length-$k$ sequencesの膨大なコレクションから直接サンプリングアプローチを採用している。
時間と空間の複雑さを持つアルゴリズムを改良し、$O(d + k2 / epsilon cdot ln d)$で、$epsilon$はプライバシーを表す。
論文 参考訳（メタデータ） (2024-11-14T16:06:13Z) - Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More [5.893651469750359]
マルチウェイカットと最小$k$cutのためのエッジ微分プライベートアルゴリズムを導入する。
最小$k$-cut問題に対して、指数的メカニズムと近似$k$-cutの数の有界性を組み合わせた別のアプローチを用いる。
論文 参考訳（メタデータ） (2024-07-09T14:46:33Z) - User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。
近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。
ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
論文 参考訳（メタデータ） (2023-09-21T21:51:55Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - A Smooth Binary Mechanism for Efficient Private Continual Observation [13.846839500730873]
時間とともに進化するデータセットに基づいて、異なるプライベートな見積もりをリリースする方法を示す。
このアプローチのPython実装は、Hnzingerらのアプローチの実行時間よりも優れています。
論文 参考訳（メタデータ） (2023-06-16T07:45:32Z) - 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) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - On Scheduling Mechanisms Beyond the Worst Case [17.281501828240877]
機構Kは各入力における機構Pよりも社会的コストが小さいことが分かる。
また、メカニズムPの平均ケース近似比は、同じ定数に収束する。
論文 参考訳（メタデータ） (2022-04-14T20:57:50Z) - Private Frequency Estimation via Projective Geometry [47.112770141205864]
そこで本研究では,局所微分型(LDP)周波数推定のための新しいアルゴリズムであるProjectiveGeometryResponse (PGR)を提案する。
私たちの$varepsilon$-LDPアルゴリズムは、プライベートコイン設定で$lceillogkrceilビット、パブリックコイン設定で$varepsilonlog e + O(1)$の通信コストを持っています。
実際に使用される多くのパラメータ設定では、これは最近のPIによって達成されるO(n+k2)$Optimalコストよりも大幅に改善されている。
論文 参考訳（メタデータ） (2022-03-01T02:49:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。