論文の概要: Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions

• arxiv url: http://arxiv.org/abs/2405.18577v3
• Date: Mon, 28 Oct 2024 20:04:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-30 13:37:36.735921
• Title: Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions
• Title（参考訳）: 最大構造弱凸関数の差分に対する単ループ確率アルゴリズム
• Authors: Quanqi Hu, Qi Qi, Zhaosong Lu, Tianbao Yang,
• Abstract要約: 非滑らかな非漸近公正問題のクラスを$min_x[yin Yphi(x, y) - max_zin Zpsix(x, z)]$の形で示す。 本稿では,これらの問題を解く最初の方法であるエンベロープ近似勾配SMAGを提案する。
• 参考スコア（独自算出の注目度）: 41.43895948769255
• License:
• Abstract: In this paper, we study a class of non-smooth non-convex problems in the form of $\min_{x}[\max_{y\in Y}\phi(x, y) - \max_{z\in Z}\psi(x, z)]$, where both $\Phi(x) = \max_{y\in Y}\phi(x, y)$ and $\Psi(x)=\max_{z\in Z}\psi(x, z)$ are weakly convex functions, and $\phi(x, y), \psi(x, z)$ are strongly concave functions in terms of $y$ and $z$, respectively. It covers two families of problems that have been studied but are missing single-loop stochastic algorithms, i.e., difference of weakly convex functions and weakly convex strongly-concave min-max problems. We propose a stochastic Moreau envelope approximate gradient method dubbed SMAG, the first single-loop algorithm for solving these problems, and provide a state-of-the-art non-asymptotic convergence rate. The key idea of the design is to compute an approximate gradient of the Moreau envelopes of $\Phi, \Psi$ using only one step of stochastic gradient update of the primal and dual variables. Empirically, we conduct experiments on positive-unlabeled (PU) learning and partial area under ROC curve (pAUC) optimization with an adversarial fairness regularizer to validate the effectiveness of our proposed algorithms.
• Abstract（参考訳）: 本稿では,非滑らかな非凸問題のクラスを$\min_{x}[\max_{y\in Y}\phi(x,} の形で研究する。 y) - \max_{z\in Z}\psi(x, どちらも$\Phiです。 (x) = \max_{y\in Y}\phi(x, y)$と$\Psi (x)=\max_{z\in Z}\psi(x, z)$は弱凸関数であり、$\phi(x) である。 y), \psi(x, z)$ は、それぞれ$y$ と $z$ の点で強凹函数である。 研究されているが、シングルループ確率アルゴリズム、すなわち弱い凸関数と弱い凸 min-max 問題の違いが欠落している2つの問題群をカバーする。 本研究では,SMAGと呼ばれる確率論的モローエンベロープ近似勾配法を提案する。 この設計の鍵となる考え方は、原始変数と双対変数の確率勾配更新の1ステップだけを用いて、モローエンベロープの$\Phi, \Psi$の近似勾配を計算することである。 提案アルゴリズムの有効性を検証するために, 実証実験として, ROC曲線 (pAUC) 最適化の下で, 正未ラベル学習(PU) と部分領域について, 対向フェアネス正規化器を用いて実験を行った。

関連論文リスト

• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Black-Box Min--Max Continuous Optimization Using CMA-ES with Worst-case Ranking Approximation [22.576922942465142]
  一般的なアプローチでは、$x$と$y$を同時に、あるいは交互に更新する。 既存のアプローチは、$f$がリプシッツの滑らかで、最適解を囲む凸凸が強い場合失敗する。 本稿では、共分散行列適応進化戦略を用いて、最悪の対象関数 $F(x)=max_yf(x,y)$ を最小化することを提案する。
  論文  参考訳（メタデータ） (2022-04-06T08:03:39Z)
• Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
  線形凸凹サドル点問題 $min_xmax_y f(x) ytopmathbfA x - g(y) について検討する。
  論文  参考訳（メタデータ） (2021-12-30T20:31:46Z)
• 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)
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms [0.0]
  主な結果は、非滑らか関数に対する$epsilon$-approximate Local minimumの新たな特徴に基づいている。 標準的な仮定では、摂動近位点、摂動近位勾配、摂動近位線形アルゴリズムは非滑らかな凸関数に対して$epsilon$-approximate局所最小値を求める。
  論文  参考訳（メタデータ） (2021-02-04T19:17:13Z)
• The Complexity of Constrained Min-Max Optimization [29.57458485068705]
  十分大きな局所点 min-max が存在することが保証されていることを示す。 さらに重要なこととして、近似的な固定勾配 Descent/Ascent 近似が完成することを示す。 この結果は、2つの基本的な最適化問題の指数関数近似を初めて示したものである。
  論文  参考訳（メタデータ） (2020-09-21T05:54:12Z)
• A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
  提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。 提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
  論文  参考訳（メタデータ） (2020-06-03T04:00:52Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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