論文の概要: Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD

• arxiv url: http://arxiv.org/abs/2302.06570v1
• Date: Mon, 13 Feb 2023 18:13:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-14 14:25:20.053110
• Title: Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD
• Title（参考訳）: 均一な平滑性を超えて:適応型SGDの停止解析
• Authors: Matthew Faw, Litu Rout, Constantine Caramanis, Sanjay Shakkottai
• Abstract要約: この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。 我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
• 参考スコア（独自算出の注目度）: 38.221784575853796
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work considers the problem of finding a first-order stationary point of a non-convex function with potentially unbounded smoothness constant using a stochastic gradient oracle. We focus on the class of $(L_0,L_1)$-smooth functions proposed by Zhang et al. (ICLR'20). Empirical evidence suggests that these functions more closely captures practical machine learning problems as compared to the pervasive $L_0$-smoothness. This class is rich enough to include highly non-smooth functions, such as $\exp(L_1 x)$ which is $(0,\mathcal{O}(L_1))$-smooth. Despite the richness, an emerging line of works achieves the $\widetilde{\mathcal{O}}(\frac{1}{\sqrt{T}})$ rate of convergence when the noise of the stochastic gradients is deterministically and uniformly bounded. This noise restriction is not required in the $L_0$-smooth setting, and in many practical settings is either not satisfied, or results in weaker convergence rates with respect to the noise scaling of the convergence rate. We develop a technique that allows us to prove $\mathcal{O}(\frac{\mathrm{poly}\log(T)}{\sqrt{T}})$ convergence rates for $(L_0,L_1)$-smooth functions without assuming uniform bounds on the noise support. The key innovation behind our results is a carefully constructed stopping time $\tau$ which is simultaneously "large" on average, yet also allows us to treat the adaptive step sizes before $\tau$ as (roughly) independent of the gradients. For general $(L_0,L_1)$-smooth functions, our analysis requires the mild restriction that the multiplicative noise parameter $\sigma_1 < 1$. For a broad subclass of $(L_0,L_1)$-smooth functions, our convergence rate continues to hold when $\sigma_1 \geq 1$. By contrast, we prove that many algorithms analyzed by prior works on $(L_0,L_1)$-smooth optimization diverge with constant probability even for smooth and strongly-convex functions when $\sigma_1 > 1$.
• Abstract（参考訳）: 本研究は、確率的勾配オラクルを用いて、非凸関数の非有界な滑らか性定数の1次定常点を求める問題を考察する。 Zhangらによって提案された$(L_0,L_1)$-smooth関数のクラス(ICLR'20)に焦点を当てる。 経験的な証拠から、これらの関数は、広く普及している$l_0$-smoothnessに比べて、実用的な機械学習問題をより密接に捉えていることが示唆される。 このクラスは、$(0,\mathcal{O}(L_1))$-smoothである$\exp(L_1 x)$のような非常に非滑らかな関数を含むのに十分リッチである。 リッチさにもかかわらず、新しい作品のラインは、確率勾配のノイズが決定論的に一様有界であるとき、収束率の$\widetilde{\mathcal{o}}(\frac{1}{\sqrt{t}})が得られる。 このノイズ制限は$l_0$-smooth設定では不要であり、多くの実用的な設定では満足できないか、あるいは収束率のノイズスケーリングに関してより弱い収束率となる。 我々は、ノイズサポートに一様境界を仮定することなく、$(L_0,L_1)$-smooth関数に対して$\mathcal{O}(\frac{\mathrm{poly}\log(T)}{\sqrt{T}})$収束率を証明できる技術を開発した。 結果の背後にある重要なイノベーションは、注意深く構築された停止時間$\tau$であり、これは平均で同時に「大きい」が、勾配から独立して$\tau$よりも適応的なステップサイズを処理できる。 一般的な$(L_0,L_1)$-smooth関数の場合、我々は乗法ノイズパラメータ $\sigma_1 < 1$ という穏やかな制限を必要とする。 l_0,l_1)$-smooth関数の幅広いサブクラスに対して、$\sigma_1 \geq 1$ の時点で収束率は継続する。 対照的に、$(L_0,L_1)$-smooth最適化に関する先行研究によって解析された多くのアルゴリズムは、$\sigma_1 > 1$ のとき、滑らかで強凸な関数であっても、一定の確率で分岐する。

関連論文リスト

• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• High Probability Convergence of Stochastic Gradient Methods [15.829413808059124]
  最適解への初期距離に依存する有界収束を示す。 AdaGrad-Normのハイバウンドが得られることを示す。
  論文  参考訳（メタデータ） (2023-02-28T18:42:11Z)
• Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise [28.780192812703948]
  重み付き雑音状態において、滑らかだが必ずしも凸な目標を持つ最適化問題を考察する。 簡単な構造しか持たない低境界の$Omega(Tfrac1-p3p-2)$よりも高速な速度が得られることを示す。 また、軽度条件下では、高い確率収束率が$O(log(T/delta)Tfrac1-p3p-2)$であることを保証する。
  論文  参考訳（メタデータ） (2023-02-14T00:23:42Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [8.0153031008486]
  大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。 我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
  論文  参考訳（メタデータ） (2023-01-08T21:46:27Z)
• 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)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Accelerating Optimization and Reinforcement Learning with Quasi-Stochastic Approximation [2.294014185517203]
  本稿では、収束理論を準確率近似に拡張することを目的とする。 強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
  論文  参考訳（メタデータ） (2020-09-30T04:44:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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