論文の概要: A Smooth Binary Mechanism for Efficient Private Continual Observation
- arxiv url: http://arxiv.org/abs/2306.09666v2
- Date: Mon, 15 Jan 2024 12:54:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-18 02:35:28.684239
- Title: A Smooth Binary Mechanism for Efficient Private Continual Observation
- Title（参考訳）: 能動的連続観察のための平滑なバイナリ機構
- Authors: Joel Daniel Andersson, Rasmus Pagh
- Abstract要約: 時間とともに進化するデータセットに基づいて、異なるプライベートな見積もりをリリースする方法を示す。
このアプローチのPython実装は、Hnzingerらのアプローチの実行時間よりも優れています。
- 参考スコア（独自算出の注目度）: 13.846839500730873
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In privacy under continual observation we study how to release differentially
private estimates based on a dataset that evolves over time. The problem of
releasing private prefix sums of $x_1,x_2,x_3,\dots \in\{0,1\}$ (where the
value of each $x_i$ is to be private) is particularly well-studied, and a
generalized form is used in state-of-the-art methods for private stochastic
gradient descent (SGD). The seminal binary mechanism privately releases the
first $t$ prefix sums with noise of variance polylogarithmic in $t$. Recently,
Henzinger et al. and Denisov et al. showed that it is possible to improve on
the binary mechanism in two ways: The variance of the noise can be reduced by a
(large) constant factor, and also made more even across time steps. However,
their algorithms for generating the noise distribution are not as efficient as
one would like in terms of computation time and (in particular) space. We
address the efficiency problem by presenting a simple alternative to the binary
mechanism in which 1) generating the noise takes constant average time per
value, 2) the variance is reduced by a factor about 4 compared to the binary
mechanism, and 3) the noise distribution at each step is identical.
Empirically, a simple Python implementation of our approach outperforms the
running time of the approach of Henzinger et al., as well as an attempt to
improve their algorithm using high-performance algorithms for multiplication
with Toeplitz matrices.
- Abstract（参考訳）: 連続観察下でのプライバシでは、時間とともに進化するデータセットに基づいて、差分プライベートな見積をリリースする方法を研究する。
プライベートプレフィックスの和を$x_1,x_2,x_3,\dots \in\{0,1\}$(各$x_i$の値がプライベートとなる場合)で解放する問題は特によく研究されており、一般化形式はプライベート確率勾配降下(SGD)の最先端手法で用いられる。
セミナーバイナリメカニズムは、最初の$t$プレフィックスの和と分散多対数ノイズを$t$でプライベートにリリースする。
最近、Henzinger et al. と Denisov et al. は2つの方法で二乗機構を改善することができることを示した。
しかしながら、ノイズ分布を生成するアルゴリズムは、計算時間や(特に)空間の観点からは、望まないほど効率的ではない。
我々は,二元機構の簡易な代替案を提示することにより,効率問題に対処する。
1)ノイズの発生には、値当たりの平均時間が必要となる。
2) 分散は, 2次機構と比較して約4因子で減少し,
3) 各ステップにおける雑音分布は同一である。
経験的に、我々のアプローチのPython実装は、Henzingerらのアプローチの実行時間よりも優れており、Toeplitz行列との乗算に高性能なアルゴリズムを用いてアルゴリズムを改良しようとする試みである。
関連論文リスト
- SGD with memory: fundamental properties and stochastic acceleration [15.25021403154845]
非確率設定では、損失収束$L_tsim C_Lt-xiの最適指数$xi$は、平滑なGDの倍である。
メモリ1のアルゴリズムでは、安定性を維持しながら、任意に$C_L$を小さくすることができる。
論文 参考訳（メタデータ） (2024-10-05T16:57:40Z) - Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy [24.138484222651346]
個人的連続数え上げに対する2つのアプローチを提案する。
最初のアプローチは、Toeplitz行列のクラスに対する空間効率のよいストリーミング行列乗算アルゴリズムに基づいている。
任意に多くのステップに対して目的関数の効率的な閉形式を導出し、直接数値最適化がこの問題に対して極めて実用的な解をもたらすことを示す。
論文 参考訳（メタデータ） (2024-04-25T16:11:46Z) - Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。
この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
論文 参考訳（メタデータ） (2024-04-02T16:35:52Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳（メタデータ） (2023-11-05T03:33:44Z) - 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) - 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) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。