論文の概要: Private Convex Optimization via Exponential Mechanism
- arxiv url: http://arxiv.org/abs/2203.00263v1
- Date: Tue, 1 Mar 2022 06:51:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-02 15:54:33.371777
- Title: Private Convex Optimization via Exponential Mechanism
- Title（参考訳）: 指数メカニズムによるプライベート凸最適化
- Authors: Sivakanth Gopi, Yin Tat Lee, Daogao Liu
- Abstract要約: 我々は、$ellcave2$ regularizerを$F(x)$に追加することで指数的なメカニズムを変更することで、既知の最適経験的リスクと人口損失の両方を$(epsilon,delta)$-DPで回復することを示した。
また、DP-SCOに対して$widetildeO(n min(d, n))クエリを使って$f_i(x)にこのメカニズムを実装する方法を示す。
- 参考スコア（独自算出の注目度）: 16.867534746193833
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study private optimization problems for non-smooth convex
functions $F(x)=\mathbb{E}_i f_i(x)$ on $\mathbb{R}^d$. We show that modifying
the exponential mechanism by adding an $\ell_2^2$ regularizer to $F(x)$ and
sampling from $\pi(x)\propto \exp(-k(F(x)+\mu\|x\|_2^2/2))$ recovers both the
known optimal empirical risk and population loss under $(\epsilon,\delta)$-DP.
Furthermore, we show how to implement this mechanism using $\widetilde{O}(n
\min(d, n))$ queries to $f_i(x)$ for the DP-SCO where $n$ is the number of
samples/users and $d$ is the ambient dimension. We also give a (nearly)
matching lower bound $\widetilde{\Omega}(n \min(d, n))$ on the number of
evaluation queries.
Our results utilize the following tools that are of independent interest: (1)
We prove Gaussian Differential Privacy (GDP) of the exponential mechanism if
the loss function is strongly convex and the perturbation is Lipschitz. Our
privacy bound is \emph{optimal} as it includes the privacy of Gaussian
mechanism as a special case and is proved using the isoperimetric inequality
for strongly log-concave measures. (2) We show how to sample from
$\exp(-F(x)-\mu \|x\|^2_2/2)$ for $G$-Lipschitz $F$ with $\eta$ error in total
variation (TV) distance using $\widetilde{O}((G^2/\mu) \log^2(d/\eta))$
unbiased queries to $F(x)$. This is the first sampler whose query complexity
has \emph{polylogarithmic dependence} on both dimension $d$ and accuracy
$\eta$.
- Abstract（参考訳）: 本稿では,非滑らか凸関数のプライベート最適化問題を$F(x)=\mathbb{E}_i f_i(x)$ on $\mathbb{R}^d$で検討する。
F(x)$ と $\pi(x)\propto \exp(-k(F(x)+\mu\|x\|_2^2/2))$ と $(\epsilon,\delta)$-DP に $\ell_2^2$ の正規化子を加えて指数的メカニズムを変更することで、既知の最適経験的リスクと人口損失の両方を復元することを示した。
さらに、このメカニズムを$\widetilde{o}(n \min(d, n))$ query to $f_i(x)$ for the dp-sco ここで$n$はサンプル/ユーザ数、$d$はアンビエント次元である。
また、評価クエリの数に対して、(ほぼ)一致した下限の$\widetilde{\Omega}(n \min(d, n))$も与えます。
1)損失関数が強凸で摂動がリプシッツであれば指数的なメカニズムのガウス微分プライバシー(GDP)を証明する。
私たちのプライバシバウンドは \emph{optimal} であり、特別な場合としてガウス機構のプライバシを含み、強い対数凸測度の等長不等式を用いて証明される。
2) $\exp(-F(x)-\mu \|x\|^2_2/2)$ for $G$-Lipschitz $F$ with $\eta$ error in total variation (TV) distance using $\widetilde{O}((G^2/\mu) \log^2(d/\eta))$ unbiased query to $F(x)$。
これは、クエリの複雑さが$d$と$\eta$の両方で \emph{polylogarithmic dependency} を持つ最初のサンプルである。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。
以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
論文 参考訳（メタデータ） (2023-09-29T14:14:53Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Unique Games hardness of Quantum Max-Cut, and a conjectured
vector-valued Borell's inequality [6.621324975749854]
関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。
我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
論文 参考訳（メタデータ） (2021-11-01T20:45:42Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。
第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
論文 参考訳（メタデータ） (2021-07-31T22:23:39Z) - From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical
Approximation and Statistical Applications [18.618590805279187]
我々は$mathsfW_p(sigma)$が$pth次スムーズな双対ソボレフ$mathsfd_p(sigma)$で制御されていることを示す。
我々は、すべての次元において$sqrtnmathsfd_p(sigma)(hatmu_n,mu)$の極限分布を導出する。
論文 参考訳（メタデータ） (2021-01-11T17:23:24Z) - Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。
疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文 参考訳（メタデータ） (2020-06-17T09:21:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。