論文の概要: Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches

• arxiv url: http://arxiv.org/abs/2406.02716v2
• Date: Wed, 02 Oct 2024 18:14:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-04 23:29:56.987532
• Title: Optimal Rates for $O(1)$-Smooth DP-SCO with a Single Epoch and Large Batches
• Title（参考訳）: O(1)$-Smooth DP-SCOの単一エポックと大バッチの最適レート
• Authors: Christopher A. Choquette-Choo, Arun Ganesh, Abhradeep Thakurta,
• Abstract要約: 相関凸最適化(SCO)問題を再考する。 DP-SCO(ポリログ因子まで)の最適速度を1つのエポックで達成するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 12.184984662899868
• License:
• Abstract: In this paper we revisit the DP stochastic convex optimization (SCO) problem. For convex smooth losses, it is well-known that the canonical DP-SGD (stochastic gradient descent) achieves the optimal rate of $O\left(\frac{LR}{\sqrt{n}} + \frac{LR \sqrt{p \log(1/\delta)}}{\epsilon n}\right)$ under $(\epsilon, \delta)$-DP, and also well-known that variants of DP-SGD can achieve the optimal rate in a single epoch. However, the batch gradient complexity (i.e., number of adaptive optimization steps), which is important in applications like federated learning, is less well-understood. In particular, all prior work on DP-SCO requires $\Omega(n)$ batch gradient steps, multiple epochs, or convexity for privacy. We propose an algorithm, Accelerated-DP-SRGD (stochastic recursive gradient descent), which bypasses the limitations of past work: it achieves the optimal rate for DP-SCO (up to polylog factors), in a single epoch using $\sqrt{n}$ batch gradient steps with batch size $\sqrt{n}$, and can be made private for arbitrary (non-convex) losses via clipping. If the global minimizer is in the constraint set, we can further improve this to $n^{1/4}$ batch gradient steps with batch size $n^{3/4}$. 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.
• Abstract（参考訳）: 本稿では,DP確率凸最適化(SCO)問題を再考する。 凸滑らかな損失に対しては、標準 DP-SGD (stochastic gradient descent) が$O\left(\frac{LR}{\sqrt{n}} + \frac{LR \sqrt{p \log(1/\delta)}}{\epsilon n}\right)$(\epsilon, \delta)$-DP という最適な速度を達成することが知られている。 しかし、フェデレート学習のようなアプリケーションにおいて重要なバッチ勾配の複雑さ(すなわち適応最適化ステップの数)はよく理解されていない。 特に、DP-SCOの以前の作業は、バッチ勾配ステップ、複数のエポック、あるいはプライバシーの凸性など、$\Omega(n)$のバッチ勾配ステップを必要とする。 DP-SCO(ポリログ因子まで)の最適速度を1エポックで達成し,バッチサイズ$\sqrt{n}$のバッチ勾配ステップをバッチサイズ$\sqrt{n}$で提案し,クリッピングによる任意の(非凸)損失に対してプライベートにすることができる。 グローバルな最小値が制約セットにある場合、さらに$n^{1/4}$のバッチ勾配ステップを$n^{3/4}$に改善できる。 これを実現するために,提案アルゴリズムは,確率的再帰勾配(SRG)の変種,勾配勾配の加速,DP連続計数からの相関雑音生成の3つの重要な要素を組み合わせた。

関連論文リスト

• 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)

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

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