論文の概要: Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods

• arxiv url: http://arxiv.org/abs/2305.12475v1
• Date: Sun, 21 May 2023 14:40:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-23 20:14:24.473968
• Title: Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods
• Title（参考訳）: 1つのコインの2つの側面:未修正SGDの限界と適応手法のパワー
• Authors: Junchi Yang, Xiang Li, Ilyas Fatkhullin and Niao He
• Abstract要約: 本研究では,未調整のSGDに対する適応的手法により,スムーズさと情報優位性で問題を緩和することを示す。 この結果から, 指数関数依存性が欠如している場合, 未修正SGDに対する適応手法の理論的正当性について検討した。
• 参考スコア（独自算出の注目度）: 22.052459124774504
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical analysis of Stochastic Gradient Descent (SGD) with polynomially decaying stepsize $\eta_t = \eta/\sqrt{t}$ relies on well-tuned $\eta$ depending on problem parameters such as Lipschitz smoothness constant, which is often unknown in practice. In this work, we prove that SGD with arbitrary $\eta > 0$, referred to as untuned SGD, still attains an order-optimal convergence rate $\widetilde{O}(T^{-1/4})$ in terms of gradient norm for minimizing smooth objectives. Unfortunately, it comes at the expense of a catastrophic exponential dependence on the smoothness constant, which we show is unavoidable for this scheme even in the noiseless setting. We then examine three families of adaptive methods $\unicode{x2013}$ Normalized SGD (NSGD), AMSGrad, and AdaGrad $\unicode{x2013}$ unveiling their power in preventing such exponential dependency in the absence of information about the smoothness parameter and boundedness of stochastic gradients. Our results provide theoretical justification for the advantage of adaptive methods over untuned SGD in alleviating the issue with large gradients.
• Abstract（参考訳）: 多項式減衰ステップを持つ確率的勾配降下(sgd)の古典的解析は、リプシッツ滑らか性定数のような問題パラメータに依存するよく調整された$\eta$に依存するが、実際にはよく知られていない。 本研究では、任意の$\eta > 0$ の SGD が、滑らかな目的を最小化するための勾配ノルムにおいて、順序-最適収束率 $\widetilde{O}(T^{-1/4})$ が得られることを証明する。 残念なことに、これは滑らか性定数に対する破滅的な指数的依存を犠牲にしており、ノイズのない環境でもこのスキームは避けられない。 次に、適応的手法の3つのファミリである $\unicode{x2013}$ Normalized SGD (NSGD), AMSGrad, and AdaGrad $\unicode{x2013}$ を、滑らか性パラメータと確率勾配の有界性に関する情報がない場合に、そのような指数的依存を防ぎ、それらのパワーを明らかにする。 この結果から,未調整SGDに対する適応手法の利点を理論的に正当化し,大きな勾配で問題を緩和する。

関連論文リスト

• Convergence Analysis of Adaptive Gradient Methods under Refined Smoothness and Noise Assumptions [18.47705532817026]
  AdaGradは特定の条件下では$d$でSGDより優れていることを示す。 これを動機として、目的物の滑らかさ構造と勾配のばらつきを仮定する。
  論文  参考訳（メタデータ） (2024-06-07T02:55:57Z)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。 そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
  論文  参考訳（メタデータ） (2022-11-03T14:41:46Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。 DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-27T03:45:02Z)
• 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)
• Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise [11.768495184175052]
  本稿では,勾配雑音が重みを示す場合の非線形勾配降下シナリオに関する一般的な枠組みを紹介する。 有界出力を持つ非線形性や1より大きい順序の有限モーメントを持たない勾配雑音に対して、非線形SGDは速度$O(/tzeta)$, $zeta in (0, 1)$でゼロに収束することを示す。 実験により、我々のフレームワークは、ヘビーテールノイズ下でのSGDの既存研究よりも汎用的であるが、我々のフレームワークから実装が容易ないくつかの非線形性は、実際のデータセット上のアート代替品の状況と競合することを示した。
  論文  参考訳（メタデータ） (2022-04-06T06:05:52Z)
• A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm [3.2958527541557525]
  このような問題は、堅牢な経験的リスク最小化という文脈で機械学習で頻繁に発生する。 高速化された原始双対 (SAPD) アルゴリズムは勾配雑音に対する頑健な手法であると考えている。 提案手法は,SAPDの実践と理論の両方において改善されていることを示す。
  論文  参考訳（メタデータ） (2022-02-19T22:12:30Z)
• The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance [46.15915820243487]
  AdaGrad-Normは$mathcalOleftのオーダー最適収束を示す。 AdaGrad-Normは$mathcalOleftのオーダー最適収束を示す。
  論文  参考訳（メタデータ） (2022-02-11T17:37:54Z)
• Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
  雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。 我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。 他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
  論文  参考訳（メタデータ） (2021-10-21T19:22:14Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。 我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
  論文  参考訳（メタデータ） (2020-06-12T02:45:21Z)

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

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