Online learning guided quasi-Newton methods with global non-asymptotic convergence
Mathematical Programming · 19.08.2026
DOI: 10.1007/s10107-026-02396-4 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 19.08.2026. Verfasst von Ruichen Jiang und 1 weiteren Autor:innen. Die Arbeit nennt 79 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.
Abstract (Originalsprache)
In this paper, we propose a quasi-Newton method for solving smooth and monotone nonlinear equations, including unconstrained minimization and minimax optimization as special cases. For the strongly monotone setting, we establish two global convergence bounds: (i) a linear convergence rate that matches the rate of the celebrated extragradient method, and (ii) an explicit global superlinear convergence rate that provably surpasses the linear convergence rate after at most $$\mathcal {O}(d)$$ O ( d ) iterations, where d is the problem’s dimension. In addition, for the case where the operator is only monotone, we prove a global convergence rate of $$\mathcal {O}(\min \{\frac{1}{k},\frac{\sqrt{d}}{k^{1.25}}\})$$ O ( min { 1 k , d k 1.25 } ) in terms of the duality gap. This matches the rate of the extragradient method when $$k = \mathcal {O}(d^2)$$ k = O ( d 2 ) and is faster when $$k = \varOmega (d^2)$$ k = Ω ( d 2 ) . These results are the first global convergence results to demonstrate a provable advantage of a quasi-Newton method over the extragradient method, without querying the Jacobian of the operator. Unlike classical quasi-Newton methods, we achieve this by using the hybrid proximal extragradient framework and a novel online learning approach for updating the Jacobian approximation matrices. Specifically, guided by the convergence analysis, we formulate the Jacobian approximation update as an online convex optimization problem over non-symmetric matrices, relating the regret of the online problem to the convergence rate of our method. To facilitate efficient implementation, we further develop a tailored online learning algorithm based on an approximate separation oracle, which preserves structures such as symmetry and sparsity in the Jacobian matrices.
Förderung
- National Science Foundation
Zitieren
APA
Jiang, R., & Mokhtari, A. (2026). Online learning guided quasi-Newton methods with global non-asymptotic convergence. Mathematical Programming. https://doi.org/10.1007/s10107-026-02396-4
Vancouver
Jiang R, Mokhtari A. Online learning guided quasi-Newton methods with global non-asymptotic convergence. Mathematical Programming. 2026. doi:10.1007/s10107-026-02396-4
BibTeX
@article{Jiang2026,
author = {Jiang, Ruichen and Mokhtari, Aryan},
title = {Online learning guided quasi-Newton methods with global non-asymptotic convergence},
journal = {Mathematical Programming},
year = {2026},
doi = {10.1007/s10107-026-02396-4}
}
EUVIMED