論文の概要: Optimal Rates for DP-SCO with a Single Epoch and Large Batches
- arxiv url: http://arxiv.org/abs/2406.02716v1
- Date: Tue, 4 Jun 2024 18:59:42 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-06 23:08:11.232489
- Title: Optimal Rates for DP-SCO with a Single Epoch and Large Batches
- Title（参考訳）: 単一エポックと大バッチを用いたDP-SCOの最適レート
- Authors: Christopher A. Choquette-Choo, Arun Ganesh, Abhradeep Thakurta,
- Abstract要約: 我々は,この独立性を破り,勾配差でのみプライバシを支払うことができる新しいDPアルゴリズムを提案する。
我々のアルゴリズムは、バッチサイズが少なくとも$sqrtn$のバッチグラデーションステップで実行できます。
- 参考スコア（独自算出の注目度）: 12.184984662899868
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The most common algorithms for differentially private (DP) machine learning (ML) are all based on stochastic gradient descent, for example, DP-SGD. These algorithms achieve DP by treating each gradient as an independent private query. However, this independence can cause us to overpay in privacy loss because we don't analyze the entire gradient trajectory. In this work, we propose a new DP algorithm, which we call Accelerated-DP-SRGD (DP stochastic recursive gradient descent), that enables us to break this independence and only pay for privacy in the gradient difference, i.e., in the new information at the current step. Our algorithm achieves the optimal DP-stochastic convex optimization (DP-SCO) error (up to polylog factors) using only a single epoch over the dataset, and converges at the Nesterov's accelerated rate. Our algorithm can be run in at most $\sqrt{n}$ batch gradient steps with batch size at least $\sqrt{n}$, unlike prior work which required $O(n)$ queries with mostly constant batch sizes. To achieve this, our algorithm combines three key ingredients, a variant of stochastic recursive gradients (SRG), accelerated gradient descent, and correlated noise generation from DP continual counting. Finally, we also show that our algorithm improves over existing SoTA on multi-class logistic regression on MNIST and CIFAR-10.
- Abstract（参考訳）: 微分プライベート(DP)機械学習(ML)のための最も一般的なアルゴリズムは、例えばDP-SGDのような確率勾配勾配に基づくものである。
これらのアルゴリズムは、各勾配を独立したプライベートクエリとして扱うことでDPを実現する。
しかし、この独立性は、勾配の軌跡全体を分析しないため、プライバシーの損失を過払いする可能性がある。
本研究では,DP-SRGD (Accelerated-DP-SRGD) と呼ばれる新しいDPアルゴリズムを提案する。
提案アルゴリズムは,データセット上の1つのエポックのみを用いてDP-stochastic convex Optimization (DP-SCO) 誤差を最適化し,ネステロフ加速率に収束する。
我々のアルゴリズムは、バッチサイズが少なくとも$\sqrt{n}$のバッチ勾配ステップで実行することができる。
これを実現するために,提案アルゴリズムは,確率的再帰勾配(SRG)の変種,勾配勾配の加速,DP連続計数からの相関雑音生成の3つの重要な要素を組み合わせた。
また,本アルゴリズムはMNISTとCIFAR-10の多クラスロジスティック回帰において,既存のSoTAよりも改善されていることを示す。
関連論文リスト
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates [15.27596975662702]
重み付き勾配を用いたDP最適化の最適速度を達成するアルゴリズムについて検討する。
その結果,DP下での凸最適化の理論的限界が達成可能であることを示す。
論文 参考訳（メタデータ） (2024-08-19T11:07:05Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。
まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。
DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。
我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。
他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
論文 参考訳（メタデータ） (2021-10-21T19:22:14Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Differentially Private SGD with Non-Smooth Loss [26.212935426509908]
ロス関数は、$alpha$-H"older連続勾配を持つように緩和される。
α$-h" のノイズの多い sgd は勾配摂動による滑らかな損失が $(epsilon,delta)$-differential privacy を保証できることを証明します。
論文 参考訳（メタデータ） (2021-01-22T03:19:06Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。