Fugu-MT 論文翻訳(概要): Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces

論文の概要: Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces

arxiv url: http://arxiv.org/abs/2008.06570v2
Date: Sat, 30 Jan 2021 23:34:27 GMT
ステータス: 処理完了
システム内更新日: 2022-10-30 16:52:23.537262
Title: Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces
Title（参考訳）: 公共推定部分空間上での高速次元独立プライベートAdaGrad
Authors: Peter Kairouz, M\'onica Ribero, Keith Rush, Abhradeep Thakurta
Abstract要約: AdaGradは、従来のAdaGradに匹敵する後悔と、ノイズによるよく制御された用語を達成していることを示す。我々は制約付きおよび制約なしの最小化において一般凸関数で操作する。
参考スコア（独自算出の注目度）: 24.52697154861819
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We revisit the problem of empirical risk minimziation (ERM) with differential privacy. We show that noisy AdaGrad, given appropriate knowledge and conditions on the subspace from which gradients can be drawn, achieves a regret comparable to traditional AdaGrad plus a well-controlled term due to noise. We show a convergence rate of $O(\text{Tr}(G_T)/T)$, where $G_T$ captures the geometry of the gradient subspace. Since $\text{Tr}(G_T)=O(\sqrt{T})$ we can obtain faster rates for convex and Lipschitz functions, compared to the $O(1/\sqrt{T})$ rate achieved by known versions of noisy (stochastic) gradient descent with comparable noise variance. In particular, we show that if the gradients lie in a known constant rank subspace, and assuming algorithmic access to an envelope which bounds decaying sensitivity, one can achieve faster convergence to an excess empirical risk of $\tilde O(1/\epsilon n)$, where $\epsilon$ is the privacy budget and $n$ the number of samples. Letting $p$ be the problem dimension, this result implies that, by running noisy Adagrad, we can bypass the DP-SGD bound $\tilde O(\sqrt{p}/\epsilon n)$ in $T=(\epsilon n)^{2/(1+2\alpha)}$ iterations, where $\alpha \geq 0$ is a parameter controlling gradient norm decay, instead of the rate achieved by SGD of $T=\epsilon^2n^2$. Our results operate with general convex functions in both constrained and unconstrained minimization. Along the way, we do a perturbation analysis of noisy AdaGrad of independent interest. Our utility guarantee for the private ERM problem follows as a corollary to the regret guarantee of noisy AdaGrad.
Abstract（参考訳）: 我々は、異なるプライバシーを持つ経験的リスク最小化(ERM)の問題を再考する。 AdaGradは、勾配を描画できる部分空間について適切な知識と条件を与えられた場合、従来のAdaGradに匹敵する後悔とノイズによる制御のよい項を達成できることを示す。収束率は$O(\text{Tr}(G_T)/T)$で、ここでは$G_T$は勾配部分空間の幾何学を捉える。 $\text{Tr}(G_T)=O(\sqrt{T})$ は凸関数とリプシッツ関数のより高速な速度を得ることができ、$O(1/\sqrt{T})$ は雑音分散に匹敵する雑音勾配の既知のバージョンによって達成される。特に、勾配が既知の定数階数部分空間に存在し、感度が低下するエンベロープへのアルゴリズムによるアクセスを仮定すると、$\tilde o(1/\epsilon n)$という過剰な経験的リスクに対してより高速に収束できることを示す。 p$を問題次元とすると、この結果は、ノイズの多いadagradを実行することによって、$t=(\epsilon n)^{2/(1+2\alpha)}$のdp-sgdバウンド$\tilde o(\sqrt{p}/\epsilon n)$ in $t=(\epsilon n)^{2/(1+2\alpha)}$ をバイパスできることを意味する。この結果は制約付きおよび制約なしの最小化において一般凸関数で動作する。その過程で, 独立利害関係の無声アダグラードの摂動解析を行う。プライベートEMM問題に対する当社のユーティリティ保証は、ノイズの多いAdaGradの残念な保証の要旨である。

関連論文リスト

Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions [18.47705532817026]
適応勾配法は間違いなくニューラルネットワークの最も成功した最適化アルゴリズムである。適応的勾配法は、アダッド・エル・エル・アンド・ジオメトリ(Adad-ell/ell$ geometry)を形作る可能性があることを示す。
論文参考訳（メタデータ） (2024-06-07T02:55:57Z)
ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文参考訳（メタデータ） (2023-01-01T18:51:29Z)
Efficient Private SCO for Heavy-Tailed Data via Clipping [31.37972684061572]
差分プライベート(DP)の勾配を保証した重み付きデータの凸最適化について検討する。一般的な凸問題では、過剰な集団リスクを$TildeOleft(fracd1/7sqrtlnfrac(n epsilon)2beta d(nepsilon)2/7right)$と$TildeOleft(fracd1/7lnfrac(nepsilon)2beta d(nepsilon)2
論文参考訳（メタデータ） (2022-06-27T01:39:15Z)
Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文参考訳（メタデータ） (2022-06-16T17:10:57Z)
Generalization Bounds for Gradient Methods via Discrete and Continuous Prior [8.76346911214414]
次数$O(frac1n + fracL2nsum_t=1T(gamma_t/varepsilon_t)2)$の新たな高確率一般化境界を示す。また、あるSGDの変種に対する新しい境界を得ることもできる。
論文参考訳（メタデータ） (2022-05-27T07:23:01Z)
High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文参考訳（メタデータ） (2022-04-06T13:50:33Z)
Cascading Bandit under Differential Privacy [21.936577816668944]
本研究では,カスケードバンドにおける自己差分プライバシー(DP)と局所差分プライバシー(LDP)について検討する。 DPでは,$epsilon$-indistinguishability を保証し,$mathcalO(fraclog3 Tepsilon)$を任意の小さな$xi$に対して後悔するアルゴリズムを提案する。 Epsilon$,$delta$)-LDPの下では、プライバシの予算とエラー確率のトレードオフを通じて、K2$依存を緩和します。
論文参考訳（メタデータ） (2021-05-24T07:19:01Z)
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)
Differentially Private SGD with Non-Smooth Loss [26.212935426509908]
ロス関数は、$alpha$-H"older連続勾配を持つように緩和される。 α$-h" のノイズの多い sgd は勾配摂動による滑らかな損失が $(epsilon,delta)$-differential privacy を保証できることを証明します。
論文参考訳（メタデータ） (2021-01-22T03:19:06Z)
Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文参考訳（メタデータ） (2020-05-29T07:20:35Z)
Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。我々はCIFARに関する実験結果を示し,その理論を検証した。
論文参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。