論文の概要: Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent

• arxiv url: http://arxiv.org/abs/2006.06783v2
• Date: Tue, 2 Mar 2021 21:04:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-22 13:13:04.648575
• Title: Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent
• Title（参考訳）: プライベートグラディエントDescenceによる非拘束プライベートGLMの寸法曲線の計算
• Authors: Shuang Song, Thomas Steinke, Om Thakkar, Abhradeep Thakurta
• Abstract要約: 我々は、よく研究された微分プライベートな経験的リスク(ERM)問題を再考する。 制約のない一般化線形モデル(GLM)の場合、過剰な経験的リスクが得られることを示す。
• 参考スコア（独自算出の注目度）: 27.729293699332793
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the well-studied problem of differentially private empirical risk minimization (ERM). We show that for unconstrained convex generalized linear models (GLMs), one can obtain an excess empirical risk of $\tilde O\left(\sqrt{{\texttt{rank}}}/\epsilon n\right)$, where ${\texttt{rank}}$ is the rank of the feature matrix in the GLM problem, $n$ is the number of data samples, and $\epsilon$ is the privacy parameter. This bound is attained via differentially private gradient descent (DP-GD). Furthermore, via the first lower bound for unconstrained private ERM, we show that our upper bound is tight. In sharp contrast to the constrained ERM setting, there is no dependence on the dimensionality of the ambient model space ($p$). (Notice that ${\texttt{rank}}\leq \min\{n, p\}$.) Besides, we obtain an analogous excess population risk bound which depends on ${\texttt{rank}}$ instead of $p$. For the smooth non-convex GLM setting (i.e., where the objective function is non-convex but preserves the GLM structure), we further show that DP-GD attains a dimension-independent convergence of $\tilde O\left(\sqrt{{\texttt{rank}}}/\epsilon n\right)$ to a first-order-stationary-point of the underlying objective. Finally, we show that for convex GLMs, a variant of DP-GD commonly used in practice (which involves clipping the individual gradients) also exhibits the same dimension-independent convergence to the minimum of a well-defined objective. To that end, we provide a structural lemma that characterizes the effect of clipping on the optimization profile of DP-GD.
• Abstract（参考訳）: 本稿では, 個人的リスク最小化(ERM)の課題を再考する。 制約のない凸一般化線形モデル (glms) に対して、$\tilde o\left(\sqrt{{\texttt{rank}}}/\epsilon n\right)$ という過剰な経験的リスクが得られ、ここで${\texttt{rank}}$ はglm問題における特徴行列のランクであり、$n$ はデータサンプルの数であり、$\epsilon$ はプライバシーパラメータである。 この境界は微分プライベート勾配降下(DP-GD)によって達成される。 さらに、制約のないプライベートermの第一下限を介して、我々の上限はタイトであることを示す。 制約されたERM設定とは対照的に、周囲のモデル空間(p$)の次元性には依存しない。 (注意:${\textt{rank}}\leq \min\{n, p\}$.) さらに、$p$の代わりに${\texttt{rank}}$に依存する類似の過剰人口リスク境界を得る。 滑らかな非凸 GLM 設定(すなわち、目的関数が非凸であるが GLM の構造を保存する)に対しては、DP-GD が $\tilde O\left(\sqrt{{\texttt{rank}}}/\epsilon n\right)$ の次元非依存収束を得ることを示す。 最後に, dp-gd の変種である convex glms についても, 十分に定義された目的の最小値に対して, 次元独立な収束を示すことが示されている。 そこで我々は,DP-GDの最適化プロファイルに対するクリッピングの効果を特徴付ける構造補題を提案する。

関連論文リスト

• 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)
• 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)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• 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)
• Differentially Private Exploration in Reinforcement Learning with Linear Representation [102.17246636801649]
  まず,線形混合MDP(Ayob et al., 2020)の設定(モデルベース設定)について検討し,共同・局所微分プライベート(DP)探索を統一的に分析するための枠組みを提供する。 我々はさらに、線形MDP(Jin et al., 2020)におけるプライバシー保護探索(つまりモデルフリー設定)について研究し、$widetildeO(sqrtK/epsilon)$ regret bound for $(epsilon,delta)を提供する。
  論文  参考訳（メタデータ） (2021-12-02T19:59:50Z)
• Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
  雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。 私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
  論文  参考訳（メタデータ） (2021-03-01T19:48:44Z)
• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces [24.52697154861819]
  AdaGradは、従来のAdaGradに匹敵する後悔と、ノイズによるよく制御された用語を達成していることを示す。 我々は制約付きおよび制約なしの最小化において一般凸関数で操作する。
  論文  参考訳（メタデータ） (2020-08-14T20:46:38Z)
• Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification [47.23063195722975]
  微分プライベートSGD(DP-SGD)は、微分プライベートな経験的リスク最小化(ERM)を解決する最も一般的な方法の1つである。 各勾配更新におけるノイズの多い摂動のため、DP-SGDの誤差率は、モデル内のパラメータ数である周囲次元$p$でスケールする。 雑音勾配を低次元部分空間に投影することでノイズ低減を行うDP-SGDを提案する。
  論文  参考訳（メタデータ） (2020-07-07T22:31:01Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)

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

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