論文の概要: Curse of Dimensionality in Unconstrained Private Convex ERM
- arxiv url: http://arxiv.org/abs/2105.13637v1
- Date: Fri, 28 May 2021 07:28:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-31 13:23:19.645739
- Title: Curse of Dimensionality in Unconstrained Private Convex ERM
- Title(参考訳): 拘束のないプライベートコンベックスERMの寸法曲線
- Authors: Daogao Liu, Zhou Lu
- Abstract要約: 一般凸関数に対する微分プライベートな経験的リスク最小化の低い境界を考える。
凸一般化線型モデル (GLMs) に対して、制約された場合におけるDP-ERMのよく知られたタイトバウンドは $tildeTheta(fracsqrtpepsilon n)$ であるが、近年では citesstt21 は非制約の場合において DP-ERM のタイトバウンドは $tildeTheta(fracsqrttextrankepsilon n)$ である。
- 参考スコア(独自算出の注目度): 2.512827436728378
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the lower bounds of differentially private empirical risk
minimization for general convex functions in this paper. For convex generalized
linear models (GLMs), the well-known tight bound of DP-ERM in the constrained
case is $\tilde{\Theta}(\frac{\sqrt{p}}{\epsilon n})$, while recently,
\cite{sstt21} find the tight bound of DP-ERM in the unconstrained case is
$\tilde{\Theta}(\frac{\sqrt{\text{rank}}}{\epsilon n})$ where $p$ is the
dimension, $n$ is the sample size and $\text{rank}$ is the rank of the feature
matrix of the GLM objective function. As $\text{rank}\leq \min\{n,p\}$, a
natural and important question arises that whether we can evade the curse of
dimensionality for over-parameterized models where $n\ll p$, for more general
convex functions beyond GLM. We answer this question negatively by giving the
first and tight lower bound of unconstrained private ERM for the general convex
function, matching the current upper bound
$\tilde{O}(\frac{\sqrt{p}}{n\epsilon})$ for unconstrained private ERM. We also
give an $\Omega(\frac{p}{n\epsilon})$ lower bound for unconstrained pure-DP ERM
which recovers the result in the constrained case.
- Abstract(参考訳): 本稿では,一般凸関数に対する差分プライベートなリスク最小化の下位限について考察する。
凸一般化線型モデル (GLMs) に対して、制約された場合における DP-ERM のよく知られたタイトバウンドは $\tilde{\Theta}(\frac{\sqrt{p}}{\epsilon n})$ であるが、近年では \cite{sstt21} が非制約の場合における DP-ERM のタイトバウンドは $\tilde{\Theta}(\frac{\sqrt{\text{rank}}}{\epsilon n})$ である。
{rank}\leq \min\{n,p\}$ として、自然で重要な疑問は、n\ll p$ の超パラメータモデルに対する次元の呪いを避けることができるか、あるいは glm を超えたより一般的な凸関数を回避できるかである。
一般凸関数に対する非拘束プライベート ERM の第一下界と強下界を与え、非拘束プライベート ERM に対して現在の上界 $\tilde{O}(\frac{\sqrt{p}}{n\epsilon})$ に一致する。
また、制約付きケースで結果を回復するunconstrained pure-dp ermに対して$\omega(\frac{p}{n\epsilon})$ lowerboundを与えます。
関連論文リスト
- Nearly Optimal Regret for Decentralized Online Convex Optimization [58.372148767703955]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳(メタデータ) (2024-02-14T13:44:16Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its
Momentum Extension Measured by $\ell_1$ Norm: Better Dependence on the
Dimension [70.4788692766068]
本稿では古典的RMSPropPropとその運動量拡張について考察する。
これにより$frac1Tsum_k=1Teleft[|nabla f(xk)|_1right]leq O(fracsqrtdT1/4)$が$ell_$ノルムで測定される。
論文 参考訳(メタデータ) (2024-02-01T07:21:32Z) - The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。
さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
論文 参考訳(メタデータ) (2023-11-09T14:29:25Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳(メタデータ) (2023-09-25T17:54:19Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳(メタデータ) (2022-10-27T05:08:07Z) - 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) - Sharper Utility Bounds for Differentially Private Models [20.246768861331276]
最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。
新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
論文 参考訳(メタデータ) (2022-04-22T07:03:13Z) - Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。
私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
論文 参考訳(メタデータ) (2021-03-01T19:48:44Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳(メタデータ) (2020-06-29T17:10:10Z) - Evading Curse of Dimensionality in Unconstrained Private GLMs via
Private Gradient Descent [27.729293699332793]
我々は、よく研究された微分プライベートな経験的リスク(ERM)問題を再考する。
制約のない一般化線形モデル(GLM)の場合、過剰な経験的リスクが得られることを示す。
論文 参考訳(メタデータ) (2020-06-11T20:07:09Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳(メタデータ) (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。