論文の概要: Faster Rates of Convergence to Stationary Points in Differentially
Private Optimization
- arxiv url: http://arxiv.org/abs/2206.00846v2
- Date: Tue, 30 May 2023 20:45:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 04:41:52.423094
- Title: Faster Rates of Convergence to Stationary Points in Differentially
Private Optimization
- Title（参考訳）: 微分プライベート最適化における定点収束の高速化
- Authors: Raman Arora, Raef Bassily, Tom\'as Gonz\'alez, Crist\'obal Guzm\'an,
Michael Menart, Enayat Ullah
- Abstract要約: リプシッツの定常点と滑らかな関数を$(varepsilon,delta)$-differential privacy(DP)で近似する問題について検討する。
点 $widehatw$ は関数 $mathbbRdrightarrowmathbbR$ if $|nabla F(widehatw)|leq alpha$ の $alpha$-stationary point と呼ばれる。
我々は$tildeObig(big[)を見つける新しい効率的なアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 31.46358820048179
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of approximating stationary points of Lipschitz and
smooth functions under $(\varepsilon,\delta)$-differential privacy (DP) in both
the finite-sum and stochastic settings. A point $\widehat{w}$ is called an
$\alpha$-stationary point of a function $F:\mathbb{R}^d\rightarrow\mathbb{R}$
if $\|\nabla F(\widehat{w})\|\leq \alpha$. We provide a new efficient algorithm
that finds an
$\tilde{O}\big(\big[\frac{\sqrt{d}}{n\varepsilon}\big]^{2/3}\big)$-stationary
point in the finite-sum setting, where $n$ is the number of samples. This
improves on the previous best rate of
$\tilde{O}\big(\big[\frac{\sqrt{d}}{n\varepsilon}\big]^{1/2}\big)$. We also
give a new construction that improves over the existing rates in the stochastic
optimization setting, where the goal is to find approximate stationary points
of the population risk. Our construction finds a
$\tilde{O}\big(\frac{1}{n^{1/3}} +
\big[\frac{\sqrt{d}}{n\varepsilon}\big]^{1/2}\big)$-stationary point of the
population risk in time linear in $n$. Furthermore, under the additional
assumption of convexity, we completely characterize the sample complexity of
finding stationary points of the population risk (up to polylog factors) and
show that the optimal rate on population stationarity is $\tilde
\Theta\big(\frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{n\varepsilon}\big)$. Finally, we
show that our methods can be used to provide dimension-independent rates of
$O\big(\frac{1}{\sqrt{n}}+\min\big(\big[\frac{\sqrt{rank}}{n\varepsilon}\big]^{2/3},\frac{1}{(n\varepsilon)^{2/5}}\big)\big)$
on population stationarity for Generalized Linear Models (GLM), where $rank$ is
the rank of the design matrix, which improves upon the previous best known
rate.
- Abstract（参考訳）: リプシッツの定常点と滑らかな関数を$(\varepsilon,\delta)$-differential privacy (DP)の下で有限サムと確率の両方で近似する問題について検討する。
点 $\widehat{w}$ は関数 $f:\mathbb{r}^d\rightarrow\mathbb{r}$ if $\|\nabla f(\widehat{w})\|\leq \alpha$ の$\alpha$-stationary point と呼ばれる。
有限サム設定において、$n$ がサンプル数である有限サム設定において、$\tilde{o}\big(\big[\frac{\sqrt{d}}{n\varepsilon}\big]^{2/3}\big)$-定常点を求める新しい効率的なアルゴリズムを提供する。
これは、以前の最高レート$\tilde{o}\big(\big[\frac{\sqrt{d}}{n\varepsilon}\big]^{1/2}\big)$で改善される。
また, 人口リスクの近似定常点を求めることを目的として, 確率的最適化設定における既存レートを改良する新しい構成法を提案する。
我々の構成は、$\tilde{O}\big(\frac{1}{n^{1/3}} + \big[\frac{\sqrt{d}}{n\varepsilon}\big]^{1/2}\big)$-stationary point of the population risk in time linear in $n$である。
さらに、凸性のさらなる仮定の下で、人口リスクの定常点(ポリログ因子まで)を見つけるためのサンプルの複雑さを完全に特徴づけ、人口定常性の最適率は$\tilde \Theta\big(\frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{n\varepsilon}\big)$であることを示す。
最後に, 一般線形モデル (GLM) の集団定常性について, $rank$ が設計行列のランクである場合, $O\big(\frac{1}{\sqrt{n}}+\min\big(\big[\frac{\sqrt{rank}}{n\varepsilon}\big]^{2/3},\frac{1}{(n\varepsilon)^{2/5}}\big)\big)$ であることを示す。
関連論文リスト
- Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - 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) - Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function
Approximation: Minimax Optimal and Instance-Dependent Regret Bounds [26.277745106128197]
本研究では,線形関数近似を用いた強化学習におけるそのような報奨の課題に対処する。
我々はまず,重み付き線形包帯に対するtextscHeavy-OFUL というアルゴリズムを設計し,インセンス依存の$T$-round regret of $tildeObig を実現した。
我々の結果は、オンライン回帰問題全般において、重くノイズを扱うことに独立した関心を持つような、新しい自己正規化集中不等式によって達成される。
論文 参考訳（メタデータ） (2023-06-12T02:56:09Z) - 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) - Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。
第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
論文 参考訳（メタデータ） (2021-07-31T22:23:39Z) - Differentially Private Stochastic Optimization: New Results in Convex
and Non-Convex Settings [15.122617358656539]
凸および非滑らかな一般損失(GLL)に対する微分プライベートアルゴリズムを提案する。
凸の場合、非滑らかな一般化損失(GLL)の族に焦点をあてる。
論文 参考訳（メタデータ） (2021-07-12T17:06:08Z) - Optimal Approximation Rate of ReLU Networks in terms of Width and Depth [5.37133760455631]
本稿では,深部フィードフォワードニューラルネットワークの幅と深さの近似力に着目した。
幅$mathcalObig(maxdlfloor N1/drfloor,, N+2big)$と深さ$mathcalO(L)$のReLUネットワークは、近似レート$mathcalObig(lambdasqrtd (N2L2ln)で$[0,1]d$のH"古い連続関数を近似できる。
論文 参考訳（メタデータ） (2021-02-28T13:15:55Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。