論文の概要: Differentially Private SGD with Non-Smooth Loss

• arxiv url: http://arxiv.org/abs/2101.08925v1
• Date: Fri, 22 Jan 2021 03:19:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-21 06:49:04.662600
• Title: Differentially Private SGD with Non-Smooth Loss
• Title（参考訳）: 非滑らかな損失を有する差分プライベートSGD
• Authors: Puyu Wang, Yunwen Lei, Yiming Ying, Hai Zhang
• Abstract要約: ロス関数は、$alpha$-H"older連続勾配を持つように緩和される。 α$-h" のノイズの多い sgd は勾配摂動による滑らかな損失が $(epsilon,delta)$-differential privacy を保証できることを証明します。
• 参考スコア（独自算出の注目度）: 26.212935426509908
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we are concerned with differentially private SGD algorithms in the setting of stochastic convex optimization (SCO). Most of existing work requires the loss to be Lipschitz continuous and strongly smooth, and the model parameter to be uniformly bounded. However, these assumptions are restrictive as many popular losses violate these conditions including the hinge loss for SVM, the absolute loss in robust regression, and even the least square loss in an unbounded domain. We significantly relax these restrictive assumptions and establish privacy and generalization (utility) guarantees for private SGD algorithms using output and gradient perturbations associated with non-smooth convex losses. Specifically, the loss function is relaxed to have $\alpha$-H\"{o}lder continuous gradient (referred to as $\alpha$-H\"{o}lder smoothness) which instantiates the Lipschitz continuity ($\alpha=0$) and strong smoothness ($\alpha=1$). We prove that noisy SGD with $\alpha$-H\"older smooth losses using gradient perturbation can guarantee $(\epsilon,\delta)$-differential privacy (DP) and attain optimal excess population risk $O\Big(\frac{\sqrt{d\log(1/\delta)}}{n\epsilon}+\frac{1}{\sqrt{n}}\Big)$, up to logarithmic terms, with gradient complexity (i.e. the total number of iterations) $T =O( n^{2-\alpha\over 1+\alpha}+ n).$ This shows an important trade-off between $\alpha$-H\"older smoothness of the loss and the computational complexity $T$ for private SGD with statistically optimal performance. In particular, our results indicate that $\alpha$-H\"older smoothness with $\alpha\ge {1/2}$ is sufficient to guarantee $(\epsilon,\delta)$-DP of noisy SGD algorithms while achieving optimal excess risk with linear gradient complexity $T = O(n).$
• Abstract（参考訳）: 本稿では,確率凸最適化(sco)の設定において,微分プライベートなsgdアルゴリズムに関心を持つ。 既存の作業の多くはリプシッツ連続かつ強滑らかな損失を必要とし、モデルパラメータは一様有界である。 しかしながら、これらの仮定は、多くの一般的な損失が、SVMのヒンジ損失、ロバスト回帰の絶対損失、そして非有界領域の最小二乗損失など、これらの条件に反するので制限的である。 我々はこれらの制約的仮定を著しく緩和し、非滑らか凸損失に伴う出力と勾配の摂動を用いたプライベートSGDアルゴリズムのプライバシーと一般化(ユーティリティ)の保証を確立する。 具体的には、損失関数は $\alpha$-H\"{o}lder 連続勾配 ($\alpha$-H\"{o}lder smoothness) として緩和され、リプシッツ連続性(英語版)(\alpha=0$)と強滑らか性(英語版)(\alpha=1$)をインスタンス化する。 α$-h\"older のノイズの多い sgd の勾配摂動による滑らかな損失は、$(\epsilon,\delta)$-differential privacy (dp) を保証し、最適な余剰人口リスク $o\big(\frac{\sqrt{d\log(1/\delta)}}{n\epsilon}+\frac{1}{\sqrt{n}}\big)$ を、対数項まで、勾配複雑性(例えば)を達成する。 繰り返しの総数)$T = O( n^{2-\alpha\over 1+\alpha}+ n)$ これは、損失のより古い滑らかさと統計的に最適な性能を持つプライベートSGDの計算複雑性$T$の間の重要なトレードオフを示す。 特に、我々の結果は、$\alpha$-H\'older smoothness with $\alpha\ge {1/2}$は、線形勾配複雑性$T = O(n)$で最適余剰リスクを達成しつつ、ノイズの多いSGDアルゴリズムの$(\epsilon,\delta)$-DPを保証するのに十分であることを示している。

関連論文リスト

• Private Isotonic Regression [54.32252900997422]
  部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。 約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。 上記の境界は本質的に最良であることを示す。
  論文  参考訳（メタデータ） (2022-10-27T05:08:07Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  微分プライベート降下勾配(SGD)アルゴリズムのプライバシーと実用性(一般化)性能について検討する。 点学習には、$mathcalOBigの過剰なリスク境界を確立する。 ペアで学習するために、勾配に基づく単純なプライベートSGDを提案し、これは$(epsilon,delta)$-differential privacyを満たす。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• 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 Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• 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)
• Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
  雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。 私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
  論文  参考訳（メタデータ） (2021-03-01T19:48:44Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces [24.52697154861819]
  AdaGradは、従来のAdaGradに匹敵する後悔と、ノイズによるよく制御された用語を達成していることを示す。 我々は制約付きおよび制約なしの最小化において一般凸関数で操作する。
  論文  参考訳（メタデータ） (2020-08-14T20:46:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。