2021/10/10 by Luo Luo, Luo, Luo, Li, Yujun +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2110.04814
openalex publication_date 2021/10/10 · openalex created_date 2021/10/25 · openalex updated_date 2026/07/28
We study the smooth minimax optimization problem min\bf xmax\bf y f(\bf x,\bf y), where f is ℓ-smooth, strongly-concave in \bf y but possibly nonconvex in \bf x. Most of existing works focus on finding the first-order stationary points of the function f(\bf x,\bf y) or its primal function P(\bf x)\triangleq max\bf y f(\bf x,\bf y), but few of them focus on achieving second-order stationary points. In this paper, we propose a novel approach for minimax optimization, called Minimax Cubic Newton (MCN), which could find an (ε,κ1.5√(ρε) )-second-order stationary point of P(\bf x) with calling \mathcal O(κ1.5√ρε-1.5) times of second-order oracles and \mathcal O(κ2√ρε-1.5) times of first-order oracles, where κ is the condition number and ρ is the Lipschitz continuous constant for the Hessian of f(\bf x,\bf y). In addition, we propose an inexact variant of MCN for high-dimensional problems to avoid calling expensive second-order oracles. Instead, our method solves the cubic sub-problem inexactly via gradient descent and matrix Chebyshev expansion. This strategy still obtains the desired approximate second-order stationary point with high probability but only requires \mathcal O(κ1.5ℓε-2) Hessian-vector oracle calls and \mathcal O(κ2√ρε-1.5) first-order oracle calls. To the best of our knowledge, this is the first work that considers the non-asymptotic convergence behavior of finding second-order stationary points for minimax problems without the convex-concave assumptions.