論文の概要: Sharper Utility Bounds for Differentially Private Models
- arxiv url: http://arxiv.org/abs/2204.10536v1
- Date: Fri, 22 Apr 2022 07:03:13 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-25 14:27:02.319895
- Title: Sharper Utility Bounds for Differentially Private Models
- Title（参考訳）: 異なるプライベートモデルのためのシャーパーユーティリティ境界
- Authors: Yilin Kang, Yong Liu, Jian Li, Weiping Wang
- Abstract要約: 最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。
新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
- 参考スコア（独自算出の注目度）: 20.246768861331276
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, by introducing Generalized Bernstein condition, we propose the
first $\mathcal{O}\big(\frac{\sqrt{p}}{n\epsilon}\big)$ high probability excess
population risk bound for differentially private algorithms under the
assumptions $G$-Lipschitz, $L$-smooth, and Polyak-{\L}ojasiewicz condition,
based on gradient perturbation method. If we replace the properties
$G$-Lipschitz and $L$-smooth by $\alpha$-H{\"o}lder smoothness (which can be
used in non-smooth setting), the high probability bound comes to
$\mathcal{O}\big(n^{-\frac{\alpha}{1+2\alpha}}\big)$ w.r.t $n$, which cannot
achieve $\mathcal{O}\left(1/n\right)$ when $\alpha\in(0,1]$. To solve this
problem, we propose a variant of gradient perturbation method,
\textbf{max$\{1,g\}$-Normalized Gradient Perturbation} (m-NGP). We further show
that by normalization, the high probability excess population risk bound under
assumptions $\alpha$-H{\"o}lder smooth and Polyak-{\L}ojasiewicz condition can
achieve $\mathcal{O}\big(\frac{\sqrt{p}}{n\epsilon}\big)$, which is the first
$\mathcal{O}\left(1/n\right)$ high probability excess population risk bound
w.r.t $n$ for differentially private algorithms under non-smooth conditions.
Moreover, we evaluate the performance of the new proposed algorithm m-NGP, the
experimental results show that m-NGP improves the performance of the
differentially private model over real datasets. It demonstrates that m-NGP
improves the utility bound and the accuracy of the DP model on real datasets
simultaneously.
- Abstract（参考訳）: 本稿では、一般化バーンスタイン条件を導入することにより、勾配摂動法に基づいて、G$-Lipschitz,$L$-smooth,およびPolyak-{\L}ojasiewicz条件を仮定して、微分プライベートアルゴリズムに対して有界な高確率過剰集団リスクを、最初の$\mathcal{O}\big(\frac{\sqrt{p}}{n\epsilon}\big)として提案する。
プロパティ $G$-Lipschitz と $L$-smooth を $\alpha$-H{\"o}lder smoothness (これは非滑らかな設定で使用することができる) に置き換えると、高い確率境界は $\mathcal{O}\big(n^{-\frac {\alpha}{1+2\alpha}}\big)$ w.r.t $n$ となり、$\mathcal{O}\left(1/n\right)$ は$\alpha\in(0,1)$ となる。
この問題を解決するために、勾配摂動法の変種である \textbf{max$\{1,g\}$-Normalized Gradient Perturbation} (m-NGP)を提案する。
さらに、正規化により、高確率過剰集団リスクは、仮定により$\alpha$-H{\"o}lder smooth と Polyak-{\L}ojasiewicz 条件が$\mathcal{O}\big(\frac{\sqrt{p}}{n\epsilon}\big)$ が得られることが示され、これは最初の$\mathcal{O}\left(1/n\right)$ 高確率過剰集団リスクは非滑らかな条件下での微分プライベートアルゴリズムに対して w.r.t $n$ となる。
さらに,提案アルゴリズムm-NGPの性能評価を行い,実験結果から,m-NGPは実データセットよりも微分プライベートモデルの性能を向上させることが示された。
m-NGPは実データセット上のDPモデルのユーティリティ境界と精度を同時に改善することを示した。
関連論文リスト
- 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) - A Fast Algorithm for Adaptive Private Mean Estimation [5.090363690988394]
我々は、$Sigma$に適応する$(varepsilon, delta)$-differentially privateアルゴリズムを設計する。
推定子は、誘導されたマハラノビスノルム $|cdot||_Sigma$ に対して最適な収束率を達成する。
論文 参考訳（メタデータ） (2023-01-17T18:44:41Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - 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) - Differentially Private Stochastic Optimization: New Results in Convex
and Non-Convex Settings [15.122617358656539]
凸および非滑らかな一般損失(GLL)に対する微分プライベートアルゴリズムを提案する。
凸の場合、非滑らかな一般化損失(GLL)の族に焦点をあてる。
論文 参考訳（メタデータ） (2021-07-12T17:06:08Z) - 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) - Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。
私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
論文 参考訳（メタデータ） (2021-03-01T19:48:44Z) - 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) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。