Quasi-Newton Methods for Saddle Point Problems and Beyond

2021/11/04 by Liu, Chengchang, Luo, Luo
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2111.02708

Abstract

This paper studies quasi-Newton methods for solving strongly-convex-strongly-concave saddle point problems (SPP). We propose greedy and random Broyden family updates for SPP, which have explicit local superlinear convergence rate of \mathcal O((1-(1)/(nκ²))^k(k-1)/2), where n is dimensions of the problem, κ is the condition number and k is the number of iterations. The design and analysis of proposed algorithm are based on estimating the square of indefinite Hessian matrix, which is different from classical quasi-Newton methods in convex optimization. We also present two specific Broyden family algorithms with BFGS-type and SR1-type updates, which enjoy the faster local convergence rate of \mathcal O((1-(1)/(n))^k(k-1)/2). Additionally, we extend our algorithms to solve general nonlinear equations and prove it enjoys the similar convergence rate.

Cited by

• Physics-informed neural networks for solving saddle-point equations in strong-field physics with tailored fields

Related

• Multiple Greedy Quasi-Newton Methods for Saddle Point Problems
• Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates
• Explicit Convergence Rates of Greedy and Random Quasi-Newton Methods
• Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees