論文の概要: Differentially Private Stochastic Optimization: New Results in Convex
and Non-Convex Settings
- arxiv url: http://arxiv.org/abs/2107.05585v2
- Date: Tue, 13 Jul 2021 18:24:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-15 11:34:25.467642
- Title: Differentially Private Stochastic Optimization: New Results in Convex
and Non-Convex Settings
- Title（参考訳）: 微分プライベート確率最適化:凸設定と非凸設定の新しい結果
- Authors: Raef Bassily, Crist\'obal Guzm\'an, Michael Menart
- Abstract要約: 凸および非滑らかな一般損失(GLL)に対する微分プライベートアルゴリズムを提案する。
凸の場合、非滑らかな一般化損失(GLL)の族に焦点をあてる。
- 参考スコア（独自算出の注目度）: 15.122617358656539
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study differentially private stochastic optimization in convex and
non-convex settings. For the convex case, we focus on the family of non-smooth
generalized linear losses (GLLs). Our algorithm for the $\ell_2$ setting
achieves optimal excess population risk in near-linear time, while the best
known differentially private algorithms for general convex losses run in
super-linear time. Our algorithm for the $\ell_1$ setting has nearly-optimal
excess population risk $\tilde{O}\big(\sqrt{\frac{\log{d}}{n}}\big)$, and
circumvents the dimension dependent lower bound of [AFKT21] for general
non-smooth convex losses. In the differentially private non-convex setting, we
provide several new algorithms for approximating stationary points of the
population risk. For the $\ell_1$-case with smooth losses and polyhedral
constraint, we provide the first nearly dimension independent rate, $\tilde
O\big(\frac{\log^{2/3}{d}}{{n^{1/3}}}\big)$ in linear time. For the constrained
$\ell_2$-case, with smooth losses, we obtain a linear-time algorithm with rate
$\tilde O\big(\frac{1}{n^{3/10}d^{1/10}}+\big(\frac{d}{n^2}\big)^{1/5}\big)$.
Finally, for the $\ell_2$-case we provide the first method for {\em non-smooth
weakly convex} stochastic optimization with rate $\tilde
O\big(\frac{1}{n^{1/4}}+\big(\frac{d}{n^2}\big)^{1/6}\big)$ which matches the
best existing non-private algorithm when $d= O(\sqrt{n})$. We also extend all
our results above for the non-convex $\ell_2$ setting to the $\ell_p$ setting,
where $1 < p \leq 2$, with only polylogarithmic (in the dimension) overhead in
the rates.
- Abstract（参考訳）: 凸および非凸設定における離散確率最適化について検討する。
凸の場合、非滑らかな一般化線形損失(GLL)の族に焦点を当てる。
提案手法は,超線形時間での一般凸損失に対する最もよく知られた微分プライベートなアルゴリズムである一方,超線形時間での最適超過集団リスクを実現する。
この$\ell_1$設定のアルゴリズムは、ほぼ最適な過剰人口リスク$\tilde{O}\big(\sqrt {\frac {\log{d}}{n}}\big)$であり、一般の非滑らか凸損失に対して[AFKT21]の次元依存下界を回避する。
差動的にプライベートな非凸設定では、人口リスクの定常点を近似するいくつかの新しいアルゴリズムを提供する。
滑らかな損失と多面体制約を持つ $\ell_1$-case に対して、線形時間で最初のほぼ次元の独立なレート $\tilde o\big(\frac{\log^{2/3}{d}}{{n^{1/3}}}\big)$ を提供する。
制約付き$\ell_2$-case に対し、滑らかな損失を持つ線形時間アルゴリズム $\tilde o\big(\frac{1}{n^{3/10}d^{1/10}}+\big(\frac{d}{n^2}\big)^{1/5}\big)$ を得る。
最後に、$\ell_2$-case に対して、$d= O(\sqrt{n})$ のとき、最も優れた非私的アルゴリズムと一致する速度 $\tilde O\big(\frac{1}{n^{1/4}}+\big(\frac{d}{n^2}\big)^{1/6}\big)$ の確率最適化のための最初の方法を提供する。
また、上記のすべての結果を、非凸の$\ell_2$設定に対して$\ell_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) - Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates [33.46648653842542]
我々は,KL(Kurdyka-Lojasiewicz)条件を満たす損失に対する個人的経験的リスク問題について検討した。
近似点法のプライベート実装で$tildeObig(big(fracsqrtdnsqrtrhobig)kappabig)を実現できることを示す。
論文 参考訳（メタデータ） (2023-11-22T15:12:42Z) - Near-Optimal Algorithms for Private Online Optimization in the
Realizable Regime [74.52487417350221]
オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。
そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-27T21:19:24Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Faster Rates of Convergence to Stationary Points in Differentially
Private Optimization [31.46358820048179]
リプシッツの定常点と滑らかな関数を$(varepsilon,delta)$-differential privacy(DP)で近似する問題について検討する。
点 $widehatw$ は関数 $mathbbRdrightarrowmathbbR$ if $|nabla F(widehatw)|leq alpha$ の $alpha$-stationary point と呼ばれる。
我々は$tildeObig(big[)を見つける新しい効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-06-02T02:43:44Z) - Sharper Utility Bounds for Differentially Private Models [20.246768861331276]
最初の$mathcalObig (fracsqrtpnepsilonbig)$ 高確率過剰集団リスクは、差分プライベートアルゴリズムに縛られる。
新しいアルゴリズムm-NGPは、実データセット上での差分プライベートモデルの性能を改善する。
論文 参考訳（メタデータ） (2022-04-22T07:03:13Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。