論文の概要: Differentially Private Generalized Linear Models Revisited
- arxiv url: http://arxiv.org/abs/2205.03014v1
- Date: Fri, 6 May 2022 05:01:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-09 20:01:22.921301
- Title: Differentially Private Generalized Linear Models Revisited
- Title（参考訳）: 微分一般線形モデルの再検討
- Authors: Raman Arora, Raef Bassily, Crist\'obal Guzm\'an, Michael Menart,
Enayat Ullah
- Abstract要約: 本研究では,凸損失のある線形予測器の差分学習における$(epsilon,delta)$-differentially private Learningの問題について検討する。
特に, $tildeOleft(fracVert w*Vertsqrtn + minleftfracVert w*Vert4/3(nepsilon)2/3, fracsqrtdVert w*Vertnepsilon の過剰集団リスクの低い境界を示す。
- 参考スコア（独自算出の注目度）: 33.755583302780614
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of $(\epsilon,\delta)$-differentially private learning
of linear predictors with convex losses. We provide results for two subclasses
of loss functions. The first case is when the loss is smooth and non-negative
but not necessarily Lipschitz (such as the squared loss). For this case, we
establish an upper bound on the excess population risk of
$\tilde{O}\left(\frac{\Vert w^*\Vert}{\sqrt{n}} + \min\left\{\frac{\Vert w^*
\Vert^2}{(n\epsilon)^{2/3}},\frac{\sqrt{d}\Vert
w^*\Vert^2}{n\epsilon}\right\}\right)$, where $n$ is the number of samples, $d$
is the dimension of the problem, and $w^*$ is the minimizer of the population
risk. Apart from the dependence on $\Vert w^\ast\Vert$, our bound is
essentially tight in all parameters. In particular, we show a lower bound of
$\tilde{\Omega}\left(\frac{1}{\sqrt{n}} + {\min\left\{\frac{\Vert
w^*\Vert^{4/3}}{(n\epsilon)^{2/3}}, \frac{\sqrt{d}\Vert
w^*\Vert}{n\epsilon}\right\}}\right)$. We also revisit the previously studied
case of Lipschitz losses [SSTT20]. For this case, we close the gap in the
existing work and show that the optimal rate is (up to log factors)
$\Theta\left(\frac{\Vert w^*\Vert}{\sqrt{n}} + \min\left\{\frac{\Vert
w^*\Vert}{\sqrt{n\epsilon}},\frac{\sqrt{\text{rank}}\Vert
w^*\Vert}{n\epsilon}\right\}\right)$, where $\text{rank}$ is the rank of the
design matrix. This improves over existing work in the high privacy regime.
Finally, our algorithms involve a private model selection approach that we
develop to enable attaining the stated rates without a-priori knowledge of
$\Vert w^*\Vert$.
- Abstract（参考訳）: 本研究では,凸損失を持つ線形予測器における$(\epsilon,\delta)$-differentially private learningの問題について検討する。
損失関数の2つのサブクラスに対して結果を提供する。
第一のケースは、損失が滑らかで非負であるが必ずしもリプシッツ(正方形損失など)ではないときである。
この場合、過剰な集団リスクの上限は$\tilde{O}\left(\frac{\Vert w^*\Vert}{\sqrt{n}} + \min\left\{\frac{\Vert w^* \Vert^2}{(n\epsilon)^{2/3}},\frac{\sqrt{d}\Vert w^*\Vert^2}{n\epsilon}\right\right)$である。
$\Vert w^\ast\Vert$への依存とは別に、我々の境界は本質的にすべてのパラメータできつい。
特に、$\tilde{\Omega}\left(\frac{1}{\sqrt{n}} + {\min\left\{\frac{\Vert w^*\Vert^{4/3}}{(n\epsilon)^{2/3}}, \frac{\sqrt{d}\Vert w^*\Vert}{n\epsilon}\right\right)$ の下界を示す。
また,以前検討したリプシッツ損失例(SSTT20)を再検討した。
この場合、既存の作業のギャップを埋めて、最適なレートが(ログファクタまで)$\Theta\left(\frac{\Vert w^*\Vert}{\sqrt{n}} + \min\left\{\frac{\Vert w^*\Vert}{\sqrt{n\epsilon}},\frac{\sqrt{\text{rank}}\Vert w^*\Vert}{n\epsilon}\right\right)$であることを示す。
これは、高いプライバシー体制における既存の作業よりも改善される。
最後に、我々のアルゴリズムは、$\Vert w^*\Vert$の知識を必要とせずに、記述されたレートを達成するためのプライベートモデル選択アプローチを含む。
関連論文リスト
- Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。
観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-26T21:54:31Z) - Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。
スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。
また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
論文 参考訳（メタデータ） (2023-04-05T07:24:19Z) - Improved Regret Bounds for Online Kernel Selection under Bandit Feedback [13.510889339096117]
過去の限界を改善する2種類の後悔境界を証明します。
2つのアルゴリズムを時間とともにオンラインカーネル選択に適用し、以前の$O(sqrtTlnK +Vert fVert2_mathcalH_imaxsqrtT,fracTsqrtmathcalR)$ expected bound ここで$mathcalR$は時間予算であることを示す。
論文 参考訳（メタデータ） (2023-03-09T03:40:34Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed
Data [22.233705161499273]
我々は$epsilon$-DPモデルにおける$ell_1$-norm線形回帰に注目した。
我々は高い確率で$tildeO(sqrtfracdnepsilon)$の上限を達成することができることを示す。
我々のアルゴリズムは、データの各座標が有界なモーメントを持つような、よりリラックスしたケースにも拡張できる。
論文 参考訳（メタデータ） (2022-01-10T08:17:05Z) - Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。
第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
論文 参考訳（メタデータ） (2021-07-31T22:23:39Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。
低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文 参考訳（メタデータ） (2021-03-17T18:18:57Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。