論文の概要: Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems

• arxiv url: http://arxiv.org/abs/2411.15769v2
• Date: Sun, 15 Jun 2025 03:49:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 15:15:29.004057
• Title: Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems
• Title（参考訳）: 非凸-強凸極小問題の解法における勾配ノルム正規化2次アルゴリズム
• Authors: Jun-Lin Wang, Zi Xu,
• Abstract要約: 提案手法は,非強弱畳み込みミニマックス問題の解法である。 提案アルゴリズムは$tell内の上位定常点であることが証明された。 エル $. $. $. $. $. $. $. $. $. $. $. $. $. $. $. $. $
• 参考スコア（独自算出の注目度）: 2.3721580767877257
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study second-order algorithms for solving nonconvex-strongly concave minimax problems, which have attracted much attention in recent years in many fields, especially in machine learning.We propose a gradient norm regularized trust-region (GRTR) algorithm to solve nonconvex-strongly concave minimax problems, where the objective function of the trust-region subproblem in each iteration uses a regularized version of the Hessian matrix, and the regularization coefficient and the radius of the ball constraint are proportional to the square root of the gradient norm. The iteration complexity of the proposed GRTR algorithm to obtain an $O(\epsilon,\sqrt{\epsilon})$-second-order stationary point is proved to be upper bounded by $\tilde{O}(\ell^{1.5}\rho^{0.5}\mu^{-1.5}\epsilon^{-1.5})$, where $\mu$ is the strong concave coefficient, $\ell$ and $\rho$ are the Lipschitz constant of the gradient and Jacobian matrix respectively, which matches the best known iteration complexity of second-order methods for solving nonconvex-strongly concave minimax problems. We further propose a Levenberg-Marquardt algorithm with a gradient norm regularization coefficient and use the negative curvature direction to correct the iteration direction (LMNegCur), which does not need to solve the trust-region subproblem at each iteration. We also prove that the LMNegCur algorithm achieves an $O(\epsilon,\sqrt{\epsilon})$-second-order stationary point within $\tilde{O}(\ell^{1.5}\rho^{0.5}\mu^{-1.5}\epsilon^{-1.5})$ number of iterations.The inexact variants of both algorithms can still obtain $O(\epsilon,\sqrt{\epsilon})$-second-order stationary points with high probability, but only require $\tilde{O}(\ell^{2.25}\rho^{0.25}\mu^{-1.75}\epsilon^{-1.75})$ Hessian-vector products and $\tilde{O}(\ell^{2}\rho^{0.5}\mu^{-2}\epsilon^{-1.5})$ gradient ascent steps.
• Abstract（参考訳）: 本稿では,近年多くの分野,特に機械学習において注目されている非凸領域最小値問題の2次解法について検討し,非凸領域最小値問題の解法として勾配ノルム正規化信頼領域 (GRTR) アルゴリズムを提案し,各反復における信頼領域準値の目的関数がヘッセン行列の正規化バージョンを用い,球制約の正則化係数と半径は勾配ノルムの平方根に比例する。 提案したGRTRアルゴリズムの反復複雑性は、$O(\epsilon,\sqrt{\epsilon})$2次定常点は、$\tilde{O}(\ell^{1.5}\rho^{0.5}\mu^{-1.5}\epsilon^{-1.5})$で上界であることが証明された。 さらに、勾配ノルム正規化係数を持つレバンス・マルカルトアルゴリズムを提案し、負曲率方向を用いて反復方向(LMNegCur)を補正する。 また、LMNegCurアルゴリズムは、$O(\epsilon,\sqrt{\epsilon})$-second-order stationary point in $\tilde{O}(\ell^{1.5}\rho^{0.5}\mu^{-1.5}\epsilon^{-1.5})$ number of iterations()$-exact variants of both algorithm could have $O(\epsilon,\sqrt{\epsilon})$-second-order stationary points with high probability but only only required $\tilde{O}(\ell^{2.25}\rho^{0.25}\mu^{-1.75}\epsilon^{-1.75})$ Hesianctor product and $\tilde{O}(\ell^{1.5}\rho^{0.5}\mu^{-2}\epsilon^{-1.1.5})$-second-order stationary points as higher steps.

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems with Optimal Iteration Complexity [2.815239177328595]
  凸凹極小最適化問題の解法として,Lipschitz-free Cubal regularization (LF-CR)アルゴリズムを提案する。 また,この問題のパラメータを必要としない完全パラメータフリー立方正則化(FF-CR)アルゴリズムを提案する。 我々の知る限り、FF-CRアルゴリズムは凸凹極小最適化問題の解法として初めて完全にパラメータフリーな2次アルゴリズムである。
  論文  参考訳（メタデータ） (2024-07-04T01:46:07Z)
• Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for Nonconvex Minimax Problems with Coupled linear Constraints [3.898056433020865]
  線形制約付きミニマックス問題に対する2つのゼロ階正則複雑性アルゴリズムを提案する。 我々の知る限りでは、彼らは最初の2つのゼロオーダーのアルゴリズムであり、非局所的な複雑さに最適である。
  論文  参考訳（メタデータ） (2024-01-26T11:22:13Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。 また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
  論文  参考訳（メタデータ） (2023-06-30T20:36:44Z)
• Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problems [9.792800635198935]
  NC-PLミニマックス問題の解法として,ゼロ階交互勾配降下法(ZO-AGDA)アルゴリズムを提案する。 我々の知る限りでは、NC-PLミニマックス問題を解くための複雑さを保証した最初の2つのゼロ階アルゴリズムである。
  論文  参考訳（メタデータ） (2022-11-24T15:34:33Z)
• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
  本稿では,スムーズで強靭なミニマックス最適化問題を再考する。 既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。 我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
  論文  参考訳（メタデータ） (2022-05-11T17:33:07Z)
• Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems [9.173866646584031]
  本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。 また,非コンケーブミニマックス問題に対処できることを示す。
  論文  参考訳（メタデータ） (2021-08-01T15:23:49Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)

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

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