論文の概要: Improved Rates for Differentially Private Stochastic Convex Optimization
with Heavy-Tailed Data
- arxiv url: http://arxiv.org/abs/2106.01336v1
- Date: Wed, 2 Jun 2021 17:45:47 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-03 14:37:59.251860
- Title: Improved Rates for Differentially Private Stochastic Convex Optimization
with Heavy-Tailed Data
- Title(参考訳): 重み付きデータを用いた微分プライベート確率凸最適化の精度向上
- Authors: Gautam Kamath, Xingtu Liu, Huanyu Zhang
- Abstract要約: 差分プライバシーの制約の下で,重み付きデータを用いた凸最適化について検討した。
我々は、純粋な差分プライバシーの制約の下で、ほぼ一致する低い境界を証明し、我々の境界が厳密であることを示す強力な証拠を与える。
- 参考スコア(独自算出の注目度): 13.465471169118974
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study stochastic convex optimization with heavy-tailed data under the
constraint of differential privacy. Most prior work on this problem is
restricted to the case where the loss function is Lipschitz. Instead, as
introduced by Wang, Xiao, Devadas, and Xu, we study general convex loss
functions with the assumption that the distribution of gradients has bounded
$k$-th moments. We provide improved upper bounds on the excess population risk
under approximate differential privacy of
$\tilde{O}\left(\sqrt{\frac{d}{n}}+\left(\frac{d}{\epsilon
n}\right)^{\frac{k-1}{k}}\right)$ and
$\tilde{O}\left(\frac{d}{n}+\left(\frac{d}{\epsilon
n}\right)^{\frac{2k-2}{k}}\right)$ for convex and strongly convex loss
functions, respectively. We also prove nearly-matching lower bounds under the
constraint of pure differential privacy, giving strong evidence that our bounds
are tight.
- Abstract(参考訳): 差分プライバシーの制約の下で,重み付きデータを用いた確率凸最適化について検討した。
この問題に関するほとんどの先行研究は、損失関数がリプシッツである場合に限られる。
代わりに、Wang, Xiao, Devadas, Xu によって導入されたように、勾配の分布が k$-次モーメントに有界であるという仮定で一般凸損失函数を研究する。
我々は、それぞれ凸と強い凸損失関数に対して、近似微分プライバシーの下で、過剰な集団リスクを$\tilde{O}\left(\sqrt {\frac{d}{n}}+\left(\frac{d}{\epsilon n}\right)^{\frac{k-1}{k}}\right)$と$\tilde{O}\left(\frac{d}{n}+\left(\frac{d}{\epsilon n}\right)^{\frac{2k-2}{k}}\right)$で改善した上限を提供する。
また、純粋な微分プライバシーの制約の下で下限とほぼ一致することを証明し、我々の境界が厳密であることの強い証拠を与えます。
関連論文リスト
- Better and Simpler Lower Bounds for Differentially Private Statistical
Estimation [7.693388437377614]
任意の$alpha le O(1)$に対して、ガウスの共分散をスペクトル誤差まで推定するには$tildeOmegaleft(fracd3/2alpha varepsilon + fracdalpha2right)$サンプルが必要である。
次に、有界な$k$thモーメントで重み付き分布の平均を推定するには$tildeOmegaleft(fracdalphak/(k-1) varepsilon +
論文 参考訳(メタデータ) (2023-10-10T04:02:43Z) - DIFF2: Differential Private Optimization via Gradient Differences for
Nonconvex Distributed Learning [58.79085525115987]
以前の研究でよく知られたユーティリティ境界は$widetilde O(d2/3/(nvarepsilon_mathrmDP)4/3)$である。
本稿では,差分プライベートフレームワークを構築した mphDIFF2 (DIFFerential private via DIFFs) という新しい差分プライベートフレームワークを提案する。
大域的な降下を持つ$mphDIFF2は$widetilde O(d2/3/(nvarepsilon_mathrmDP)4/3の効用を達成する
論文 参考訳(メタデータ) (2023-02-08T05:19:01Z) - Private Stochastic Optimization With Large Worst-Case Lipschitz
Parameter: Optimal Rates for (Non-Smooth) Convex Losses and Extension to
Non-Convex Losses [16.587199291939346]
多くの実践的な問題において、すべてのデータポイントにおける損失の最悪の(一様)リプシッツパラメータは非常に大きいかもしれない。
この研究は、損失の均一なリプシッツパラメータに依存しない準最適超過リスク境界を提供する。
論文 参考訳(メタデータ) (2022-09-15T16:03:23Z) - Efficient Private SCO for Heavy-Tailed Data via Clipping [31.37972684061572]
差分プライベート(DP)の勾配を保証した重み付きデータの凸最適化について検討する。
一般的な凸問題では、過剰な集団リスクを$TildeOleft(fracd1/7sqrtlnfrac(n epsilon)2beta d(nepsilon)2/7right)$と$TildeOleft(fracd1/7lnfrac(nepsilon)2beta d(nepsilon)2
論文 参考訳(メタデータ) (2022-06-27T01:39:15Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad
Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。
我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。
我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文 参考訳(メタデータ) (2022-04-06T13:50:33Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳(メタデータ) (2021-06-28T00:17:01Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳(メタデータ) (2021-03-02T06:53:44Z) - Differentially Private SGD with Non-Smooth Loss [26.212935426509908]
ロス関数は、$alpha$-H"older連続勾配を持つように緩和される。
α$-h" のノイズの多い sgd は勾配摂動による滑らかな損失が $(epsilon,delta)$-differential privacy を保証できることを証明します。
論文 参考訳(メタデータ) (2021-01-22T03:19:06Z) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳(メタデータ) (2020-12-23T17:07:26Z) - On Differentially Private Stochastic Convex Optimization with
Heavy-tailed Data [18.351352536791453]
本稿では,重み付きデータを用いた凸最適化(SCO)のためのDPアルゴリズムの設計について考察する。
このようなデータの不規則性は、ほとんど全ての既存のDP-SCOおよびDP-ERM法で使われるいくつかの重要な仮定に反する。
我々は,データの不規則性に起因する課題に対して,アルゴリズムが効果的に対処可能であることを示す。
論文 参考訳(メタデータ) (2020-10-21T15:45:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。