Cubic Regularized Newton Method for the Saddle Point Models: A Global and Local Convergence Analysis

Kevin Huang, Junyu Zhang, Shuzhong Zhang

Research output: Contribution to journalReview articlepeer-review

Abstract

In this paper, we propose a cubic regularized Newton method for solving the convex-concave minimax saddle point problems. At each iteration, a cubic regularized saddle point subproblem is constructed and solved, which provides a search direction for the iterate. With properly chosen stepsizes, the method is shown to converge to the saddle point with global linear and local superlinear convergence rates, if the saddle point function is gradient Lipschitz and strongly-convex-strongly-concave. In the case that the function is merely convex-concave, we propose a homotopy continuation (or path-following) method. Under a Lipschitz-type error bound condition, we present an iteration complexity bound of O(ln (1 / ϵ)) to reach an ϵ-solution through a homotopy continuation approach, and the iteration complexity bound becomes O((1/ϵ)1-θθ2) under a Hölderian-type error bound condition involving a parameter θ (0 < θ< 1).

Original languageEnglish (US)
Article number60
JournalJournal of Scientific Computing
Volume91
Issue number2
DOIs
StatePublished - May 2022

Bibliographical note

Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

Keywords

  • Cubic regularized Newton method
  • Homotopy continuation
  • Merit function
  • Minimax saddle point problem

Fingerprint

Dive into the research topics of 'Cubic Regularized Newton Method for the Saddle Point Models: A Global and Local Convergence Analysis'. Together they form a unique fingerprint.

Cite this