論文の概要: Private Convex Optimization in General Norms
- arxiv url: http://arxiv.org/abs/2207.08347v1
- Date: Mon, 18 Jul 2022 02:02:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-19 16:19:14.930058
- Title: Private Convex Optimization in General Norms
- Title（参考訳）: 一般ノルムにおけるプライベート凸最適化
- Authors: Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, Kevin Tian
- Abstract要約: 任意のノルム$normxcdot$におけるリプシッツである凸関数の微分プライベート最適化のための新しいフレームワークを提案する。
本稿では,このメカニズムが差分プライバシーを満足し,DP-ERM(経験的リスク最小化)とDP-SCO(確率的凸最適化)の両方を解決することを示す。
我々のフレームワークは、一般ノルム空間におけるプライベート凸最適化に初めて適用され、ミラー降下によって達成された非プライベートSCOレートを直接回復する。
- 参考スコア（独自算出の注目度）: 23.166642097170545
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a new framework for differentially private optimization of convex
functions which are Lipschitz in an arbitrary norm $\normx{\cdot}$. Our
algorithms are based on a regularized exponential mechanism which samples from
the density $\propto \exp(-k(F+\mu r))$ where $F$ is the empirical loss and $r$
is a regularizer which is strongly convex with respect to $\normx{\cdot}$,
generalizing a recent work of \cite{GLL22} to non-Euclidean settings. We show
that this mechanism satisfies Gaussian differential privacy and solves both
DP-ERM (empirical risk minimization) and DP-SCO (stochastic convex
optimization), by using localization tools from convex geometry. Our framework
is the first to apply to private convex optimization in general normed spaces,
and directly recovers non-private SCO rates achieved by mirror descent, as the
privacy parameter $\eps \to \infty$. As applications, for Lipschitz
optimization in $\ell_p$ norms for all $p \in (1, 2)$, we obtain the first
optimal privacy-utility tradeoffs; for $p = 1$, we improve tradeoffs obtained
by the recent works \cite{AsiFKT21, BassilyGN21} by at least a logarithmic
factor. Our $\ell_p$ norm and Schatten-$p$ norm optimization frameworks are
complemented with polynomial-time samplers whose query complexity we explicitly
bound.
- Abstract（参考訳）: 任意のノルム$\normx{\cdot}$におけるリプシッツである凸関数の微分プライベート最適化のための新しいフレームワークを提案する。
我々のアルゴリズムは、密度$\propto \exp(-k(F+\mu r))$、$F$は経験的損失であり、$r$は、$\normx{\cdot}$に対して強く凸な正規化子であり、近年の \cite{GLL22} の非ユークリッド設定への一般化である。
この機構はガウス微分プライバシーを満足し、凸幾何からの局在化ツールを用いてdp-erm(empirical risk minimization)とdp-sco(stochastic convex optimization)の両方を解決する。
我々のフレームワークは、一般的なノルム空間におけるプライベート凸最適化に初めて適用され、プライバシーパラメータ $\eps \to \infty$ としてミラー降下によって達成された非プライベートSCOレートを直接回収する。
アプリケーションとして、すべての$p \in (1, 2)$に対する$\ell_p$ノルムのリプシッツ最適化のために、最初の最適なプライバシユーティリティトレードオフを得る;$p = 1$の場合、私たちは、少なくとも対数係数によって、最近の研究である‘cite{AsiFKT21, BassilyGN21} によって得られるトレードオフを改善する。
我々の$\ell_p$ と schatten-$p$ の最適化フレームワークは、クエリの複雑さが明示的に束縛された多項式時間スプライマーで補完されます。
関連論文リスト
- 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) - Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。
純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。
本稿では,総和,数,投票の単純な統計量について両問題を解く。
論文 参考訳（メタデータ） (2023-09-27T17:09:36Z) - 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) - Sharper Utility Bounds for Differentially Private Models [20.246768861331276]
最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。
新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
論文 参考訳（メタデータ） (2022-04-22T07:03:13Z) - Private Convex Optimization via Exponential Mechanism [16.867534746193833]
我々は、$ellcave2$ regularizerを$F(x)$に追加することで指数的なメカニズムを変更することで、既知の最適経験的リスクと人口損失の両方を$(epsilon,delta)$-DPで回復することを示した。
また、DP-SCOに対して$widetildeO(n min(d, n))クエリを使って$f_i(x)にこのメカニズムを実装する方法を示す。
論文 参考訳（メタデータ） (2022-03-01T06:51:03Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。