論文の概要: Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization

• arxiv url: http://arxiv.org/abs/2305.17323v4
• Date: Thu, 27 Jun 2024 02:53:30 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-28 20:35:54.686135
• Title: Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization
• Title（参考訳）: 強凸最適化のための下次手法の原始双対理論
• Authors: Benjamin Grimmer, Danlin Li,
• Abstract要約: 我々は、強く凸するが、潜在的に非滑らかな非Lipschitz最適化のための段階的手法を考える。 本稿では,古典的下位段階法,近位下位段階法,スイッチング下位段階法に対する等価な2値記述について述べる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider (stochastic) subgradient methods for strongly convex but potentially nonsmooth non-Lipschitz optimization. We provide new equivalent dual descriptions (in the style of dual averaging) for the classic subgradient method, the proximal subgradient method, and the switching subgradient method. These equivalences enable $O(1/T)$ convergence guarantees in terms of both their classic primal gap and a not previously analyzed dual gap for strongly convex optimization. Consequently, our theory provides these classic methods with simple, optimal stopping criteria and optimality certificates at no added computational cost. Our results apply to a wide range of stepsize selections and of non-Lipschitz ill-conditioned problems where the early iterations of the subgradient method may diverge exponentially quickly (a phenomenon which, to the best of our knowledge, no prior works address). Even in the presence of such undesirable behaviors, our theory still ensures and bounds eventual convergence.
• Abstract（参考訳）: 我々は、強く凸するが、非滑らかな非Lipschitz最適化のための(確率的に)段階的な方法を考える。 古典的下位段階法,近位下位段階法,スイッチング下位段階法に対して,新しい等価な2値記述(二値平均化のスタイル)を提供する。 これらの同値性により、$O(1/T)$収束保証は古典的原始的ギャップと、強い凸最適化のための以前に解析されなかった双対ギャップの両方の観点から可能である。 その結果、これらの古典的手法には、計算コストを伴わずに、単純で最適な停止基準と最適性証明が提供される。 この結果は、段階的な選択や、過次法の初期反復が指数関数的に高速に発散できるような非リプシッツ不条件問題(私たちの知る限りでは、事前の作業アドレスがない現象)に適用できる。 そのような望ましくない振る舞いが存在するとしても、我々の理論は依然として最終的な収束を保証し、束縛する。

関連論文リスト

• A Unified Analysis for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions [8.960341489080609]
  非Lipschitzおよび非滑らかな最適化問題の文脈における新しい収束解析を提案する。 論文で導入すべき下次上界条件のいずれかの下では、$O (1/stqrT)$がエンベロープ関数の平方勾配で成り立つことを示し、さらに1/2$指数を持つ一様KL条件が成り立つ場合、$O (1/T)$に改善される。
  論文  参考訳（メタデータ） (2023-08-30T23:34:11Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• DRSOM: A Dimension Reduced Second-Order Method [13.778619250890406]
  信頼的な枠組みの下では,2次法の収束を保ちながら,数方向の情報のみを用いる。 理論的には,この手法は局所収束率と大域収束率が$O(epsilon-3/2)$であり,第1次条件と第2次条件を満たすことを示す。
  論文  参考訳（メタデータ） (2022-07-30T13:05:01Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。 クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
  目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる 新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
  論文  参考訳（メタデータ） (2021-05-13T04:23:07Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Adaptive Gradient Methods Can Be Provably Faster than SGD after Finite Epochs [25.158203665218164]
  適応勾配法は有限時間後にランダムシャッフルSGDよりも高速であることを示す。 我々の知る限り、適応的勾配法は有限時間後にSGDよりも高速であることを示すのはこれが初めてである。
  論文  参考訳（メタデータ） (2020-06-12T09:39:47Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• A Unified Convergence Analysis for Shuffling-Type Gradient Methods [32.8097849940763]
  有限項問題を解くための一般化勾配シャッフル型法に対する統一収束解析を提案する。 以上の結果から,特定の神経シャッフル変種でのトレーニングに適する選択が示唆された。
  論文  参考訳（メタデータ） (2020-02-19T15:45:41Z)

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

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