論文の概要: Faster Rates of Differentially Private Stochastic Convex Optimization
- arxiv url: http://arxiv.org/abs/2108.00331v1
- Date: Sat, 31 Jul 2021 22:23:39 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-04 12:20:29.682892
- Title: Faster Rates of Differentially Private Stochastic Convex Optimization
- Title（参考訳）: 微分プライベート確率凸最適化の高速化
- Authors: Jinyan Su and Di Wang
- Abstract要約: 人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。
第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
- 参考スコア（独自算出の注目度）: 7.93728520583825
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we revisit the problem of Differentially Private Stochastic
Convex Optimization (DP-SCO) and provide excess population risks for some
special classes of functions that are faster than the previous results of
general convex and strongly convex functions. In the first part of the paper,
we study the case where the population risk function satisfies the Tysbakov
Noise Condition (TNC) with some parameter $\theta>1$. Specifically, we first
show that under some mild assumptions on the loss functions, there is an
algorithm whose output could achieve an upper bound of
$\tilde{O}((\frac{1}{\sqrt{n}}+\frac{\sqrt{d\log
\frac{1}{\delta}}}{n\epsilon})^\frac{\theta}{\theta-1})$ for $(\epsilon,
\delta)$-DP when $\theta\geq 2$, here $n$ is the sample size and $d$ is the
dimension of the space. Then we address the inefficiency issue, improve the
upper bounds by $\text{Poly}(\log n)$ factors and extend to the case where
$\theta\geq \bar{\theta}>1$ for some known $\bar{\theta}$. Next we show that
the excess population risk of population functions satisfying TNC with
parameter $\theta>1$ is always lower bounded by
$\Omega((\frac{d}{n\epsilon})^\frac{\theta}{\theta-1}) $ and
$\Omega((\frac{\sqrt{d\log
\frac{1}{\delta}}}{n\epsilon})^\frac{\theta}{\theta-1})$ for $\epsilon$-DP and
$(\epsilon, \delta)$-DP, respectively. In the second part, we focus on a
special case where the population risk function is strongly convex. Unlike the
previous studies, here we assume the loss function is {\em non-negative} and
{\em the optimal value of population risk is sufficiently small}. With these
additional assumptions, we propose a new method whose output could achieve an
upper bound of
$O(\frac{d\log\frac{1}{\delta}}{n^2\epsilon^2}+\frac{1}{n^{\tau}})$ for any
$\tau\geq 1$ in $(\epsilon,\delta)$-DP model if the sample size $n$ is
sufficiently large.
- Abstract（参考訳）: 本稿では,微分的にプライベートな確率凸最適化(dp-sco)の問題を再検討し,一般凸関数と強凸関数のこれまでの結果よりも高速な特殊種類の関数に対して過剰な集団リスクを与える。
本論文の第1部では,人口リスク関数がtysbakovノイズ条件 (tnc) を満たす場合について,パラメータ$\theta>1$ で検討する。
具体的には、損失関数に関するいくつかの穏やかな仮定の下で、出力が$\tilde{O}((\frac{1}{\sqrt{n}}+\frac{\sqrt{d\log \frac{1}{\delta}}}{n\epsilon})^\frac{\theta}{\theta-1})$ for $(\epsilon, \delta)$-DP if $\theta\geq 2$ ここで$n$はサンプルサイズであり、$d$は空間の次元である。
次に、非効率な問題に対処し、$\text{Poly}(\log n)$ factor で上限を改善し、既知の $\bar{\theta}$ に対して $\theta\geq \bar{\theta}>1$ の場合に拡張する。
次に、パラメータ$\theta>1$のtncを満たす人口関数の過剰な人口リスクは、$\omega((\frac{d}{n\epsilon})^\frac{\theta}{\theta-1}) $と$\omega((\frac{\sqrt{d\log \frac{1}{\delta}}}{n\epsilon})^\frac{\theta}{\theta-1})$で、$\epsilon$-dpと$(\epsilon, \delta)$-dpで常に低いことを示す。
第2部では,人口リスク関数が強い凸である特別な場合に焦点を当てる。
以前の研究とは異なり、損失関数は「非負」であり、人口リスクの最適値は「十分小さい」と仮定する。
これらの仮定により、サンプルサイズ$n$が十分大きい場合、任意の$\tau\geq 1$ in $(\epsilon,\delta)$-DPモデルに対して、出力が$O(\frac{d\log\frac{1}{\delta}}{n^2\epsilon^2}+\frac{1}{n^{\tau}})の上限を達成できる新しい方法を提案する。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - 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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - 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) - Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
論文 参考訳（メタデータ） (2022-02-01T16:06:20Z) - Differentially Private $\ell_1$-norm Linear Regression with Heavy-tailed
Data [22.233705161499273]
我々は$epsilon$-DPモデルにおける$ell_1$-norm線形回帰に注目した。
我々は高い確率で$tildeO(sqrtfracdnepsilon)$の上限を達成することができることを示す。
我々のアルゴリズムは、データの各座標が有界なモーメントを持つような、よりリラックスしたケースにも拡張できる。
論文 参考訳（メタデータ） (2022-01-10T08:17:05Z) - 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) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - $\lambda$-Regularized A-Optimal Design and its Approximation by
$\lambda$-Regularized Proportional Volume Sampling [1.256413718364189]
本稿では,$lambda$-regularized $A$-optimal design problemについて検討し,$lambda$-regularized proportional volume sample algorithmを紹介する。
この問題は、リッジ回帰モデルにおける真の係数からリッジ回帰予測器の2乗誤差を最小化しようとする、リッジ回帰の最適設計から動機づけられている。
論文 参考訳（メタデータ） (2020-06-19T15:17:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。