Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Second-order methodsMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Gradient Regularized Natural Gradients
Gradient regularization (GR) has been shown to improve the generalizability of trained models. While Natural Gradient Descent has been shown to accelerate optimization in the initial phase of training, little attention h…
Gradient-Normalized Smoothness for Optimization with Approximate Hessians
In this work, we develop new optimization algorithms that use approximate second-order information combined with the gradient regularization technique to achieve fast global convergence rates for both convex and non-conv…
The Ordered Weighted $\ell_1$ Norm: Atomic Formulation, Projections, and Algorithms
The ordered weighted $\ell_1$ norm (OWL) was recently proposed, with two different motivations: its good statistical properties as a sparsity promoting regularizer; the fact that it generalizes the so-called {\it octagon…
ClusteringregressionStochastic quasi-Newton with line-search regularization
In this paper we present a novel quasi-Newton algorithm for use in stochastic optimisation. Quasi-Newton methods have had an enormous impact on deterministic optimisation problems because they afford rapid convergence an…
State Space ModelsHybrid Conditional Gradient - Smoothing Algorithms with Applications to Sparse and Low Rank Regularization
We study a hybrid conditional gradient - smoothing algorithm (HCGS) for solving composite convex optimization problems which contain several terms over a bounded set. Examples of these include regularization problems wit…