論文の概要: Efficient Private SCO for Heavy-Tailed Data via Clipping
- arxiv url: http://arxiv.org/abs/2206.13011v1
- Date: Mon, 27 Jun 2022 01:39:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-28 16:36:21.261433
- Title: Efficient Private SCO for Heavy-Tailed Data via Clipping
- Title(参考訳): クリッピングによる重機データのための効率的なプライベートSCO
- Authors: Chenhan Jin, Kaiwen Zhou, Bo Han, James Cheng, Ming-Chang Yang
- Abstract要約: 差分プライベート(DP)の勾配を保証した重み付きデータの凸最適化について検討する。
一般的な凸問題では、過剰な集団リスクを$TildeOleft(fracd1/7sqrtlnfrac(n epsilon)2beta d(nepsilon)2/7right)$と$TildeOleft(fracd1/7lnfrac(nepsilon)2beta d(nepsilon)2
- 参考スコア(独自算出の注目度): 31.37972684061572
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider stochastic convex optimization for heavy-tailed data with the
guarantee of being differentially private (DP). Prior work on this problem is
restricted to the gradient descent (GD) method, which is inefficient for
large-scale problems. In this paper, we resolve this issue and derive the first
high-probability bounds for private stochastic method with clipping. For
general convex problems, we derive excess population risks
$\Tilde{O}\left(\frac{d^{1/7}\sqrt{\ln\frac{(n \epsilon)^2}{\beta
d}}}{(n\epsilon)^{2/7}}\right)$ and
$\Tilde{O}\left(\frac{d^{1/7}\ln\frac{(n\epsilon)^2}{\beta
d}}{(n\epsilon)^{2/7}}\right)$ under bounded or unbounded domain assumption,
respectively (here $n$ is the sample size, $d$ is the dimension of the data,
$\beta$ is the confidence level and $\epsilon$ is the private level). Then, we
extend our analysis to the strongly convex case and non-smooth case (which
works for generalized smooth objectives with H$\ddot{\text{o}}$lder-continuous
gradients). We establish new excess risk bounds without bounded domain
assumption. The results above achieve lower excess risks and gradient
complexities than existing methods in their corresponding cases. Numerical
experiments are conducted to justify the theoretical improvement.
- Abstract(参考訳): 重み付きデータに対する確率的凸最適化は、差分プライベート(DP)を保証する。
この問題の先行研究は、大規模問題に対して非効率な勾配降下法(GD)に限られている。
本稿では, この問題を解き, クリッピングを用いたプライベート確率法の最初の高確率境界を導出する。
一般的な凸問題では、過剰な人口のリスク$\tilde{o}\left(\frac{d^{1/7}\sqrt{\ln\frac{(n \epsilon)^2}{\beta d}}}{(n\epsilon)^{2/7}}\right)$と$\tilde{o}\left(\frac{d^{1/7}\ln\frac{(n\epsilon)^2}{\beta d}}{(n\epsilon)^{2/7}}\right)$が有界または非有界な仮定の下で導かれる(ここで$n$はサンプルサイズ、$d$はデータの次元、$\beta$は信頼レベル、$\epsilon$はプライベートレベル)。
すると、我々は解析を強凸ケースと非滑らかケース(H$\ddot{\text{o}}$lder-continuous gradients で一般化された滑らかな目的に対して機能する)にまで拡張する。
境界領域の仮定なしで新たな過剰リスク境界を確立する。
以上の結果から, 既存の手法に比べて, 余剰リスクや勾配複雑度は低い。
理論的改善を正当化するために数値実験が行われる。
関連論文リスト
- 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) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-01-01T18:51:29Z) - 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) - High Dimensional Differentially Private Stochastic Optimization with
Heavy-tailed Data [8.55881355051688]
本研究では,高次元空間における重み付きデータを用いたDP-SCOの問題に関する最初の研究を行う。
損失関数が滑らかで、その勾配が第二次モーメントに有界ならば、$epsilon$-DPモデルで$tildeO(fraclog d(nepsilon)frac13)$の(高い確率)誤差境界(過剰な集団リスク)を得ることが可能である。
論文の第2部では,重み付きデータを用いたスパース学習について検討した。
論文 参考訳(メタデータ) (2021-07-23T11:03:21Z) - 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) - On Differentially Private Stochastic Convex Optimization with
Heavy-tailed Data [18.351352536791453]
本稿では,重み付きデータを用いた凸最適化(SCO)のためのDPアルゴリズムの設計について考察する。
このようなデータの不規則性は、ほとんど全ての既存のDP-SCOおよびDP-ERM法で使われるいくつかの重要な仮定に反する。
我々は,データの不規則性に起因する課題に対して,アルゴリズムが効果的に対処可能であることを示す。
論文 参考訳(メタデータ) (2020-10-21T15:45:27Z) - Fast Dimension Independent Private AdaGrad on Publicly Estimated
Subspaces [24.52697154861819]
AdaGradは、従来のAdaGradに匹敵する後悔と、ノイズによるよく制御された用語を達成していることを示す。
我々は制約付きおよび制約なしの最小化において一般凸関数で操作する。
論文 参考訳(メタデータ) (2020-08-14T20:46:38Z) - Safe Learning under Uncertain Objectives and Constraints [66.05180398174286]
我々は、テキスト不明で安全クリティカルな制約の下で、非テクスト無知かつ安全クリティカルな最適化問題を考察する。
このような問題は、ロボティクス、製造、医療などの様々な領域で自然に発生する。
我々の分析の重要な要素は、安全な最適化の文脈で収縮と呼ばれる手法を導入し、適用することである。
論文 参考訳(メタデータ) (2020-06-23T20:51:00Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳(メタデータ) (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。