論文の概要: Faster Differentially Private Samplers via R\'enyi Divergence Analysis
of Discretized Langevin MCMC
- arxiv url: http://arxiv.org/abs/2010.14658v2
- Date: Thu, 17 Dec 2020 07:21:58 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-02 13:25:45.597616
- Title: Faster Differentially Private Samplers via R\'enyi Divergence Analysis
of Discretized Langevin MCMC
- Title（参考訳）: 離散化ランジュバンmcmcのr\'enyi divergence解析による高速微分プライベートサンプラー
- Authors: Arun Ganesh, Kunal Talwar
- Abstract要約: ランゲヴィン力学に基づくアルゴリズムは、統計距離のようなある程度の距離測度の下で、はるかに高速な代替手段を提供する。
我々の手法は単純で汎用的で、アンダーダムドランゲヴィン力学に適用できる。
- 参考スコア（独自算出の注目度）: 35.050135428062795
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Various differentially private algorithms instantiate the exponential
mechanism, and require sampling from the distribution $\exp(-f)$ for a suitable
function $f$. When the domain of the distribution is high-dimensional, this
sampling can be computationally challenging. Using heuristic sampling schemes
such as Gibbs sampling does not necessarily lead to provable privacy. When $f$
is convex, techniques from log-concave sampling lead to polynomial-time
algorithms, albeit with large polynomials. Langevin dynamics-based algorithms
offer much faster alternatives under some distance measures such as statistical
distance. In this work, we establish rapid convergence for these algorithms
under distance measures more suitable for differential privacy. For smooth,
strongly-convex $f$, we give the first results proving convergence in R\'enyi
divergence. This gives us fast differentially private algorithms for such $f$.
Our techniques and simple and generic and apply also to underdamped Langevin
dynamics.
- Abstract（参考訳）: 様々な微分プライベートアルゴリズムは指数関数機構をインスタンス化し、適切な関数に対して$\exp(-f)$からサンプリングする必要がある。
分布領域が高次元である場合、このサンプリングは計算的に困難である。
ギブスサンプリングのようなヒューリスティックサンプリングスキームを使用すると、必ずしも証明可能なプライバシーにつながるとは限らない。
f$が凸であるとき、対数凹サンプリングの技術は多項式時間アルゴリズムに導かれる。
ランゲヴィン力学に基づくアルゴリズムは、統計距離などの距離測度の下ではるかに高速な代替手段を提供する。
本研究では,差分プライバシーに適合する距離尺度を用いて,これらのアルゴリズムの高速収束を実現する。
滑らかで強凸な$f$ に対して、r\'enyi divergence の収束を証明する最初の結果を与える。
これにより、そのような$f$の高速な微分プライベートアルゴリズムが得られます。
我々の技術と単純で汎用的で、アンダーダムドランゲヴィン力学にも応用できる。
関連論文リスト
- Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。
純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。
本稿では,総和,数,投票の単純な統計量について両問題を解く。
論文 参考訳（メタデータ） (2023-09-27T17:09:36Z) - Convergence Rates for Non-Log-Concave Sampling and Log-Partition
Estimation [0.0]
m$timesの微分可能関数が$d$の場合、$n$(m/d)のアルゴリズムの最適レートは$n(m/d)であることが知られている。
サンプリングと計算に類似したレートが可能であり、独立レートが$d$の時間で実現可能であることを示す。
論文 参考訳（メタデータ） (2023-03-06T15:53:44Z) - 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) - Resolving the Mixing Time of the Langevin Algorithm to its Stationary
Distribution for Log-Concave Sampling [34.66940399825547]
本稿では,Langevinアルゴリズムの定常分布に対する混合時間の特徴について述べる。
本稿では,差分プライバシー文献からサンプリング文献へのアプローチを紹介する。
論文 参考訳（メタデータ） (2022-10-16T05:11:16Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Normalized/Clipped SGD with Perturbation for Differentially Private
Non-Convex Optimization [94.06564567766475]
DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。
DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
論文 参考訳（メタデータ） (2022-06-27T03:45:02Z) - 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) - 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) - Projected Stochastic Gradient Langevin Algorithms for Constrained
Sampling and Non-Convex Learning [0.0]
ランジュバンアルゴリズムは付加ノイズを持つ手法である。
ランジュバンアルゴリズムは何十年もチェーンカルロ(ミロン)で使われてきた
学習にとって、それはそれがそれが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それがそれが事実であるということであり、それがそれがそれが事実であるということであるということであるということが、それが事実であるということであるということが、それが事実であるということであることを示している。
論文 参考訳（メタデータ） (2020-12-22T16:19:20Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。