Online learning guided quasi-Newton methods with global non-asymptotic convergence

Abstract

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.