論文の概要: ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization

• arxiv url: http://arxiv.org/abs/2312.02277v4
• Date: Tue, 18 Jun 2024 21:31:08 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-22 06:08:04.560078
• Title: ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization
• Title（参考訳）: ALEXR: Convex Finite-Sum Coupled compositional Stochastic Optimizationのための最適単ループアルゴリズム
• Authors: Bokun Wang, Tianbao Yang,
• Abstract要約: ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
• 参考スコア（独自算出の注目度）: 53.14532968909759
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper revisits a class of convex Finite-Sum Coupled Compositional Stochastic Optimization (cFCCO) problems with many applications, including group distributionally robust optimization (GDRO), learning with imbalanced data, reinforcement learning, and learning to rank. To better solve these problems, we introduce an efficient single-loop primal-dual block-coordinate proximal algorithm, dubbed ALEXR. This algorithm leverages block-coordinate stochastic mirror ascent updates for the dual variable and stochastic proximal gradient descent updates for the primal variable. We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions of involved functions, which not only improve the best rates in previous works on smooth cFCCO problems but also expand the realm of cFCCO for solving more challenging non-smooth problems such as the dual form of GDRO. Finally, we present lower complexity bounds to demonstrate that the convergence rates of ALEXR are optimal among first-order block-coordinate stochastic algorithms for the considered class of cFCCO problems.
• Abstract（参考訳）: 本稿では、群分散ロバスト最適化(GDRO)、不均衡データによる学習、強化学習、ランク付け学習など、多くのアプリケーションにおける凸型有限結合構成確率最適化(cFCCO)のクラスを再検討する。 これらの問題を解決するために、ALEXRと呼ばれる効率的な単ループプリマル・デュアルブロック座標近似アルゴリズムを導入する。 このアルゴリズムは、主変数の二重変数および確率的近位勾配降下更新に対するブロック座標確率鏡の上昇更新を利用する。 我々は, ALEXR の凸面および強凸面における収束速度を, 関連関数の滑らかさおよび非平滑性条件下で確立し, これまでの滑らかな CFCCO 問題における最良の速度を改善するだけでなく, GDRO の双対形式のようなより困難な非平滑性問題の解法として cFCCO の領域を拡大する。 最後に、ALEXRの収束速度が、検討されたcFCCO問題に対する1次ブロック座標確率アルゴリズムの中で最適であることを示すために、より低い複雑性境界を示す。

関連論文リスト

• An inexact LPA for DC composite optimization and application to matrix completions with outliers [5.746154410100363]
  本稿では,複合最適化問題のクラスについて述べる。 合成構造を利用することで、ポテンシャル関数が反復列において1/2$のKL特性を持つ条件を与える。
  論文  参考訳（メタデータ） (2023-03-29T16:15:34Z)
• Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization [20.11028799145883]
  複合凸最適化のための外挿法 (A-CODER) を用いた加速サイクル座標二元平均化法を提案する。 A-CODERは,前処理よりもブロック数に依存して最適な収束率が得られることを示す。 目的関数の滑らかな成分が有限和形式で表現できるような設定では、A-CODERの分散還元変種であるVR-A-CODERを導入し、最先端の複雑性を保証する。
  論文  参考訳（メタデータ） (2023-03-28T19:46:30Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
  本稿では,新しい一階最適化アルゴリズムであるAcceleratedGradient-OptimisticGradient (AG-OG) Ascentを提案する。 我々はAG-OGが様々な設定に対して最適収束率(定数まで)を達成することを示す。 アルゴリズムを拡張して設定を拡張し、bi-SC-SCとbi-C-SCの両方で最適な収束率を達成する。
  論文  参考訳（メタデータ） (2022-10-31T17:59:29Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems [12.010310883787911]
  我々は、弱凸(おそらく非滑らかな)最適化問題の重要なクラスを解くための、適応的な段階的な新しい手法の族を解析する。 実験結果から,提案アルゴリズムが0次勾配降下と設計変動を経験的に上回ることを示す。
  論文  参考訳（メタデータ） (2020-05-19T07:44:52Z)

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

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