論文の概要: 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を保証するのに十分であることを示している。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。 本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2023-05-30T17:47:27Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Sharper Utility Bounds for Differentially Private Models [20.246768861331276]
  最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。 新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
  論文  参考訳（メタデータ） (2022-04-22T07:03:13Z)
• 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)
• Gradient-Based Empirical Risk Minimization using Local Polynomial Regression [39.29885444997579]
  この論文の主な目標は、勾配降下(GD)や勾配降下(SGD)といった異なるアルゴリズムを比較することである。 損失関数がデータのスムーズな場合、各反復でオラクルを学習し、GDとSGDの両方のオラクル複雑度に打ち勝つことができることを示す。
  論文  参考訳（メタデータ） (2020-11-04T20:10:31Z)
• 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)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。 我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
  論文  参考訳（メタデータ） (2020-06-12T02:45:21Z)

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

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