論文の概要: Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems
- arxiv url: http://arxiv.org/abs/2411.15769v1
- Date: Sun, 24 Nov 2024 09:46:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-26 14:22:48.680606
- Title: Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems
- Title（参考訳）: 非凸-強凸極小問題の解法における勾配ノルム正規化2次アルゴリズム
- Authors: Jun-Lin Wang, Zi Xu,
- Abstract要約: 提案手法は,非強弱畳み込みミニマックス問題の解法である。
本稿では,提案アルゴリズムが$mathcalを達成することを示す。
スティロン
2階ノルムは上向きであることが証明されている。
tk
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
400ドルだ
$k
- 参考スコア（独自算出の注目度）: 2.3721580767877257
- License:
- 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 $\mathcal{O}(\epsilon,\sqrt{\epsilon})$-second-order stationary point is proved to be upper bounded by $\tilde{\mathcal{O}}(\rho^{0.5}\kappa^{1.5}\epsilon^{-3/2})$, where $\rho$ and $\kappa$ are the Lipschitz constant of the Jacobian matrix and the condition number of the objective function 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 $\mathcal{O}(\epsilon,\sqrt{\epsilon})$-second-order stationary point within $\tilde{\mathcal{O}}(\rho^{0.5}\kappa^{1.5}\epsilon^{-3/2})$ number of iterations. Numerical results show the efficiency of both proposed algorithms.
- Abstract（参考訳）: 本稿では,近年多くの分野,特に機械学習において注目されている非凸凸凹最小値問題の2次解法について検討する。
本稿では,非凸凸凹最小値問題の解法として,信頼領域サブプロブレムの目的関数をヘッセン行列の正規化版を用い,ボール制約の正規化係数と半径を勾配ノルムの平方根に比例する勾配ノルム正規化信頼領域(GRTR)アルゴリズムを提案する。
提案したGRTRアルゴリズムの反復複雑性は、$\tilde{\mathcal{O}}(\rho^{0.5}\kappa^{1.5}\epsilon^{-3/2})$で、$\rho$と$\kappa$はヤコビ行列のリプシッツ定数であり、目的関数の条件数は、非凸強凸極小問題を解くための二階法の最もよく知られた反復複雑性と一致する。
さらに、勾配ノルム正規化係数を持つレバンス・マルカルトアルゴリズムを提案し、負曲率方向を用いて反復方向(LMNegCur)を補正する。
また、LMNegCurアルゴリズムは、$\tilde{\mathcal{O}}(\rho^{0.5}\kappa^{1.5}\epsilon^{-3/2})$の反復数において、$\mathcal{O}(\epsilon,\sqrt{\epsilon})$2次定常点を得ることを示す。
数値計算の結果,両アルゴリズムの効率性を示した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。