論文の概要: Non-Euclidean Differentially Private Stochastic Convex Optimization
- arxiv url: http://arxiv.org/abs/2103.01278v1
- Date: Mon, 1 Mar 2021 19:48:44 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-05 09:27:21.104062
- Title: Non-Euclidean Differentially Private Stochastic Convex Optimization
- Title（参考訳）: 非ユークリッド微分私的確率凸最適化
- Authors: Raef Bassily, Crist\'obal Guzm\'an, Anupama Nandi
- Abstract要約: 雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。
私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
- 参考スコア（独自算出の注目度）: 15.302167005107135
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Differentially private (DP) stochastic convex optimization (SCO) is a
fundamental problem, where the goal is to approximately minimize the population
risk with respect to a convex loss function, given a dataset of i.i.d. samples
from a distribution, while satisfying differential privacy with respect to the
dataset. Most of the existing works in the literature of private convex
optimization focus on the Euclidean (i.e., $\ell_2$) setting, where the loss is
assumed to be Lipschitz (and possibly smooth) w.r.t. the $\ell_2$ norm over a
constraint set with bounded $\ell_2$ diameter. Algorithms based on noisy
stochastic gradient descent (SGD) are known to attain the optimal excess risk
in this setting.
In this work, we conduct a systematic study of DP-SCO for $\ell_p$-setups.
For $p=1$, under a standard smoothness assumption, we give a new algorithm with
nearly optimal excess risk. This result also extends to general polyhedral
norms and feasible sets. For $p\in(1, 2)$, we give two new algorithms, whose
central building block is a novel privacy mechanism, which generalizes the
Gaussian mechanism. Moreover, we establish a lower bound on the excess risk for
this range of $p$, showing a necessary dependence on $\sqrt{d}$, where $d$ is
the dimension of the space. Our lower bound implies a sudden transition of the
excess risk at $p=1$, where the dependence on $d$ changes from logarithmic to
polynomial, resolving an open question in prior work [TTZ15] . For $p\in (2,
\infty)$, noisy SGD attains optimal excess risk in the low-dimensional regime;
in particular, this proves the optimality of noisy SGD for $p=\infty$. Our work
draws upon concepts from the geometry of normed spaces, such as the notions of
regularity, uniform convexity, and uniform smoothness.
- Abstract（参考訳）: Differentially private (DP) stochastic convex Optimization (SCO) は基本的な問題であり、i.d.のデータセットが与えられた場合の凸損失関数に関して、人口リスクをほぼ最小化することを目的としている。
データセットに関して差分プライバシーを満たしながら、分布からのサンプル。
プライベート凸最適化の文献における既存の研究の多くは、損失がリプシッツ(おそらく滑らか) w.r.t であると仮定されるユークリッド(すなわち$\ell_2$)の設定に焦点を当てている。
有界な $\ell_2$ diameter を持つ制約集合上の $\ell_2$ norm 。
雑音性確率勾配勾配(SGD)に基づくアルゴリズムは、この設定において最適余剰リスクに達することが知られている。
本研究では,$\ell_p$-setups に対するdp-sco の系統的研究を行う。
p=1$の場合、標準的な平滑性仮定の下で、我々はほぼ最適な過剰リスクを持つ新しいアルゴリズムを与える。
この結果は一般多面体ノルムや実現可能集合にも拡張される。
p\in(1, 2)$の場合、2つの新しいアルゴリズムを与え、その中心となるビルディングブロックは、ガウス機構を一般化する新しいプライバシメカニズムである。
さらに、$d$ が空間の次元である $\sqrt{d}$ に対する必要な依存を示す、$p$ のこの範囲の過剰リスクに対するより低い境界を確立する。
我々の下限は、余剰リスクが$p=1$で突然遷移し、$d$への依存は対数から多項式に変化し、事前の作業 [TTZ15] で開問題を解決することを意味する。
p\in (2, \infty)$ の場合、雑音 SGD は低次元状態において最適余剰リスクを得るが、これは特に$p=\infty$ に対して雑音 SGD の最適性を証明する。
私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
関連論文リスト
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions [19.008521454738425]
重み付き勾配を持つ差分プライベート凸最適化(DP-SCO)の問題を考察し、一様境界ではなく、サンプル関数のリプシッツ定数上の$ktextth$-momentを仮定する。
Gcdot frac 1 sqrt n + G_k cdot (fracsqrt dnepsilon) 1 の誤差を達成し、重み付け設定における第1次最適率(対数係数まで)を得るための新しい還元ベースのアプローチを提案する。
論文 参考訳（メタデータ） (2024-06-04T21:26:29Z) - PrivSGP-VR: Differentially Private Variance-Reduced Stochastic Gradient Push with Tight Utility Bounds [9.47030623916154]
そこで本研究では,分散化による勾配プッシュを応用し,各ノードのプライバシを保証する,差分プライベートな分散学習手法(PrivSGPVR)を提案する。
この理論解析により, DP雑音下では, PrivGPS-VR は$mathcalO (1/sqrtnK)$のサブ線形収束速度を達成できることがわかった。
論文 参考訳（メタデータ） (2024-05-04T11:22:53Z) - Near-Optimal differentially private low-rank trace regression with guaranteed private initialization [0.0]
RRd_1times d$におけるランク-r$行列$Mの差分プライベート(DP)推定をトレース回帰モデルの下で検討する。
我々はまた、リーマン最適化(DP-RGrad)に基づいて$M$を推定する微分プライベートアルゴリズムを提案する。
DP-RGradで与えられる推定器は、微分プライバシーというより弱い概念において最適収束率に達することが示されている。
論文 参考訳（メタデータ） (2024-03-24T03:57:21Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Differentially Private Stochastic Convex Optimization in (Non)-Euclidean
Space Revisited [6.339471679859413]
ユークリッド空間における微分プライベート凸(DP-SCO)の問題を再考する。
強い有界と強い有界な損失関数の両方に対して、過剰な集団にのみ依存する()出力を達成することができる。
また、凸関数の幅が対数係数まで最適であることを示す。
論文 参考訳（メタデータ） (2023-03-31T13:29:27Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Private Convex Optimization in General Norms [23.166642097170545]
任意のノルム$normxcdot$におけるリプシッツである凸関数の微分プライベート最適化のための新しいフレームワークを提案する。
本稿では,このメカニズムが差分プライバシーを満足し,DP-ERM(経験的リスク最小化)とDP-SCO(確率的凸最適化)の両方を解決することを示す。
我々のフレームワークは、一般ノルム空間におけるプライベート凸最適化に初めて適用され、ミラー降下によって達成された非プライベートSCOレートを直接回復する。
論文 参考訳（メタデータ） (2022-07-18T02:02:22Z) - 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) - 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) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。