mlsanityData to 7 Oct 2026

Quasi-Newton Methods for Saddle Point Problems and Beyond

arXiv 2111.02708 ↗First posted 4 Nov 2021math.OC cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

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 Obig(big(1-frac1nkappa2big)k(k-1)/2big), where n is dimensions of the problem, kappa 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 Obig(big(1-frac1nbig)k(k-1)/2big). Additionally, we extend our algorithms to solve general nonlinear equations and prove it enjoys the similar convergence rate.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 20 of its 63 references that are in the map. First posted on arXiv 4 Nov 2021.

Builds on

20 of 63 references.

References · 20

  1. 2018Mitigating Unwanted Biases with Adversarial Learningcited by 663
  2. 2017Training GANs with Optimismcited by 217
  3. 2016Distributionally Robust Stochastic Optimization with Wasserstein Distancecited by 182
  4. 2021A survey on datasets for fairness-aware machine learningcited by 157
  5. 2016Variance-based regularization with convex objectivescited by 153
  6. 2015Distributionally Robust Logistic Regressioncited by 124
  7. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  8. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  9. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  10. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
  11. 2014Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimizationcited by 30
  12. 2019Last-iterate convergence rates for min-max optimizationcited by 25
8 more
  1. 2020Greedy Quasi-Newton Methods with Explicit Superlinear Convergencecited by 21
  2. 2020Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methodscited by 16
  3. 2020New Results on Superlinear Convergence of Classical Quasi-Newton Methodscited by 15
  4. 2020Rates of superlinear convergence for classical quasi-Newton methodscited by 13
  5. 2021Explicit Convergence Rates of Greedy and Random Quasi-Newton Methodscited by 5
  6. 2021Explicit Superlinear Convergence Rates of The SR1 Algorithmcited by 3
  7. 2021Explicit Superlinear Convergence Rates of Broyden's Methods in Nonlinear Equationscited by 3
  8. 2021Greedy and Random Broyden's Methods with Explicit Superlinear Convergence Rates in Nonlinear Equationscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 1; 2024: 7; 2025: 0; 2026: 1.

10 papers.

  1. 2023On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysiscited by 39
  2. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  3. 2024Exact Gauss-Newton Optimization for Training Deep Neural Networkscited by 10
  4. 2024QN-Mixer: A Quasi-Newton MLP-Mixer Model for Sparse-View CT Reconstructioncited by 6
  5. 2024Second-Order Min-Max Optimization with Lazy Hessianscited by 4
  6. 2024Multiple Greedy Quasi-Newton Methods for Saddle Point Problemscited by 3
  7. 2024Diffusion Stochastic Optimization for Min-Max Problemscited by 2
  8. 2024Electroencephalogram Emotion Recognition via AUC Maximizationcited by 2
  9. 2024Incremental Gauss--Newton Methods with Superlinear Convergence Ratescited by 0
  10. 2026Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimizationcited by 0