論文の概要: Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
- arxiv url: http://arxiv.org/abs/2404.16706v2
- Date: Fri, 26 Apr 2024 21:23:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-30 20:10:08.399068
- Title: Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
- Title（参考訳）: ディファレンシャルプライバシのストリーミングのための高効率・準最適ノイズ生成
- Authors: Krishnamurthy Dvijotham, H. Brendan McMahan, Krishna Pillutla, Thomas Steinke, Abhradeep Thakurta,
- Abstract要約: 個人的連続数え上げに対する2つのアプローチを提案する。
最初のアプローチは、Toeplitz行列のクラスに対する空間効率のよいストリーミング行列乗算アルゴリズムに基づいている。
任意に多くのステップに対して目的関数の効率的な閉形式を導出し、直接数値最適化がこの問題に対して極めて実用的な解をもたらすことを示す。
- 参考スコア（独自算出の注目度）: 24.138484222651346
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the task of differentially private (DP) continual counting, we receive a stream of increments and our goal is to output an approximate running total of these increments, without revealing too much about any specific increment. Despite its simplicity, differentially private continual counting has attracted significant attention both in theory and in practice. Existing algorithms for differentially private continual counting are either inefficient in terms of their space usage or add an excessive amount of noise, inducing suboptimal utility. The most practical DP continual counting algorithms add carefully correlated Gaussian noise to the values. The task of choosing the covariance for this noise can be expressed in terms of factoring the lower-triangular matrix of ones (which computes prefix sums). We present two approaches from this class (for different parameter regimes) that achieve near-optimal utility for DP continual counting and only require logarithmic or polylogarithmic space (and time). Our first approach is based on a space-efficient streaming matrix multiplication algorithm for a class of Toeplitz matrices. We show that to instantiate this algorithm for DP continual counting, it is sufficient to find a low-degree rational function that approximates the square root on a circle in the complex plane. We then apply and extend tools from approximation theory to achieve this. We also derive efficient closed-forms for the objective function for arbitrarily many steps, and show direct numerical optimization yields a highly practical solution to the problem. Our second approach combines our first approach with a recursive construction similar to the binary tree mechanism.
- Abstract（参考訳）: 差分的プライベート(DP)連続カウントのタスクでは、インクリメントのストリームを受け取り、特定のインクリメントについて多くを明らかにすることなく、これらのインクリメントの総実行量を近似的に出力することを目的としています。
その単純さにもかかわらず、差分的に個人的連続的数え上げは理論と実際の両方において大きな注目を集めている。
微分プライベートな連続的数え上げのための既存のアルゴリズムは、その空間的使用法において非効率であるか、あるいは過度のノイズを付加し、準最適効用を誘導する。
最も実用的なDP連続計数アルゴリズムは、ガウス雑音を注意深く値に付加する。
このノイズの共分散を選択するタスクは、(プレフィックス和を計算する)下の三角形行列を分解する言葉で表すことができる。
本稿では,DP の連続数え上げに近似的有用性を実現し,対数的あるいは多対数的空間(および時間)のみを必要とする,このクラスからの2つのアプローチを提案する。
最初のアプローチは、Toeplitz行列のクラスに対する空間効率のよいストリーミング行列乗算アルゴリズムに基づいている。
DP連続数え上げのためにこのアルゴリズムをインスタンス化するには、複素平面上の円上の平方根を近似する低次有理関数を見つけるのに十分であることを示す。
次に、ツールを近似理論から拡張してこれを実現する。
また、任意に多くのステップに対して目的関数の効率的な閉形式を導出し、直接数値最適化がこの問題に対して非常に実用的な解をもたらすことを示す。
第2のアプローチは、最初のアプローチとバイナリツリー機構に似た再帰的な構造を組み合わせるものです。
関連論文リスト
- Optimal Rates for DP-SCO with a Single Epoch and Large Batches [12.184984662899868]
我々は,この独立性を破り,勾配差でのみプライバシを支払うことができる新しいDPアルゴリズムを提案する。
我々のアルゴリズムは、バッチサイズが少なくとも$sqrtn$のバッチグラデーションステップで実行できます。
論文 参考訳（メタデータ） (2024-06-04T18:59:42Z) - Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。
我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-05-28T19:02:30Z) - Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
2つの凸関数の和を最小化する自己協和スムージングの概念を導入し、そのうちの1つは滑らかであり、もう1つは非滑らかである。
本稿では, 近位ニュートンアルゴリズムであるProx-N-SCOREと近位一般化したガウスニュートンアルゴリズムであるProx-GGN-SCOREの2つのアルゴリズムの収束性を証明する。
論文 参考訳（メタデータ） (2023-09-04T19:47:04Z) - A Smooth Binary Mechanism for Efficient Private Continual Observation [13.846839500730873]
時間とともに進化するデータセットに基づいて、異なるプライベートな見積もりをリリースする方法を示す。
このアプローチのPython実装は、Hnzingerらのアプローチの実行時間よりも優れています。
論文 参考訳（メタデータ） (2023-06-16T07:45:32Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - 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) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。