論文の概要: 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)$-differenti al 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)$-differenti al 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を保証するのに十分であることを示している。
- 全文 参考訳へのリンク
関連論文リスト
- Sharper Utility Bounds for Differentially Private Models [20.246768861331276]
最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。
新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
論文 参考訳（メタデータ） (2022-04-22T07:03:13Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [51.47633778534544]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳（メタデータ） (2022-04-11T17:26:19Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for
Online Convex Optimization [93.14387921542709]
非定常環境におけるオンライン凸最適化について検討する。
エンファンダイナミックな後悔をパフォーマンス指標として選びます。
本研究では,スムーズさを生かし,動的後悔の中で$T$に依存する新しいオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Differentially Private Stochastic Optimization: New Results in Convex
and Non-Convex Settings [15.122617358656539]
凸および非滑らかな一般損失(GLL)に対する微分プライベートアルゴリズムを提案する。
凸の場合、非滑らかな一般化損失(GLL)の族に焦点をあてる。
論文 参考訳（メタデータ） (2021-07-12T17:06:08Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - Regret and Cumulative Constraint Violation Analysis for Online Convex
Optimization with Long Term Constraints [24.97580261894342]
本稿では,長期的制約を伴うオンライン凸最適化について考察する。
新たなアルゴリズムが最初に提案され、静的後悔のために$mathcalO(Tmaxc,1-c)$bound、累積制約違反のために$mathcalO(T(1-c)/2)$boundを達成する。
論文 参考訳（メタデータ） (2021-06-09T15:18:06Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-different ly 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) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。