Fugu-MT 論文翻訳(概要): Private Zeroth-Order Nonsmooth Nonconvex Optimization

論文の概要: Private Zeroth-Order Nonsmooth Nonconvex Optimization

arxiv url: http://arxiv.org/abs/2406.19579v1
Date: Thu, 27 Jun 2024 23:57:01 GMT
ステータス: 処理完了
システム内更新日: 2024-07-01 18:10:10.149941
Title: Private Zeroth-Order Nonsmooth Nonconvex Optimization
Title（参考訳）: プライベートゼロ階非平滑非凸最適化
Authors: Qinzi Zhang, Hoang Tran, Ashok Cutkosky,
Abstract要約: 非平滑な目的と非平滑な目的に対するプライベート最適化のための新しいゼロ階アルゴリズムを提案する。データセットサイズが$M$であれば、アルゴリズムはプライバシの差分を見つける。目的はスムーズではないが、プライバシーがある。無料の$tdepsilon$
参考スコア（独自算出の注目度）: 41.05664717242051
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We introduce a new zeroth-order algorithm for private stochastic optimization on nonconvex and nonsmooth objectives. Given a dataset of size $M$, our algorithm ensures $(\alpha,\alpha\rho^2/2)$-R\'enyi differential privacy and finds a $(\delta,\epsilon)$-stationary point so long as $M=\tilde\Omega\left(\frac{d}{\delta\epsilon^3} + \frac{d^{3/2}}{\rho\delta\epsilon^2}\right)$. This matches the optimal complexity of its non-private zeroth-order analog. Notably, although the objective is not smooth, we have privacy ``for free'' whenever $\rho \ge \sqrt{d}\epsilon$.
Abstract（参考訳）: 非凸および非滑らかな目的に対するプライベート確率最適化のための新しいゼロ階アルゴリズムを提案する。 M$のデータセットが与えられた場合、我々のアルゴリズムは$(\alpha,\alpha\rho^2/2)$-R\enyi差分プライバシーを保証し、$(\delta,\epsilon)$-stationary pointを$M=\tilde\Omega\left(\frac{d}{\delta\epsilon^3} + \frac{d^{3/2}}{\rho\delta\epsilon^2}\right)$とすると$(\delta,\epsilon)$-stationary pointを見つける。これは、その非プライベートなゼロ階アナログの最適複雑性と一致する。特に、目的はスムーズではありませんが、$\rho \ge \sqrt{d}\epsilon$.sqrt{d}\epsilon$.sqrt{d}" のとき、プライバシーは ``for free'' になります。

関連論文リスト

Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
論文参考訳（メタデータ） (2024-05-25T08:34:49Z)
Differentially Private Stochastic Linear Bandits: (Almost) for Free [17.711701190680742]
中心的なモデルでは、最適な非プライベートなアルゴリズムとほとんど同じ後悔を実現しています。シャッフルモデルでは、中央の場合のように$tildeO(sqrtT+frac1epsilon)$ % for small $epsilon$を後悔する一方、最もよく知られたアルゴリズムは$tildeO(frac1epsilonT3/5)$を後悔する。
論文参考訳（メタデータ） (2022-07-07T17:20:57Z)
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文参考訳（メタデータ） (2022-02-10T16:10:41Z)
Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings [15.122617358656539]
凸および非滑らかな一般損失(GLL)に対する微分プライベートアルゴリズムを提案する。凸の場合、非滑らかな一般化損失(GLL)の族に焦点をあてる。
論文参考訳（メタデータ） (2021-07-12T17:06:08Z)
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)
Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
本研究では,バンディットとフルインフォメーションの両方のフィードバックの下で,オンライン学習環境における個人差分問題について検討する。差分的な私的盗賊に対しては、UTBとトンプソンサンプリングに基づくアルゴリズムを同時に提案し、最適な$O左(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right)$ minimax lower boundとする。同じ差分プライベートなフル情報設定に対しては、$epsilon$-differentially も提示する。
論文参考訳（メタデータ） (2021-02-16T02:48:16Z)
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)
A closed form scale bound for the $(\epsilon, \delta)$-differentially private Gaussian Mechanism valid for all privacy regimes [0.0]
同様の閉じた形式 $sigma geq delta (epsilonsqrt2)-1 left (sqrtaz+epsilon + ssqrtazright)$ for $epsilon in (0,1)$ を示す。
論文参考訳（メタデータ） (2020-12-18T21:35:26Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。