PaperlayerView exact revision on arXiv

Source-linked AI summary

Randomized Quasi-Gauss--Newton Methods for Solving General Nonlinear Equations

Chengchang Liu, Luo Luo

arXiv:2608.27084v1math.OCmath.NA

TL;DR

The paper addresses gaps in quasi-Newton methods for general nonlinear systems, including unclear superlinear guarantees beyond square systems and costly or restrictive Jacobian approximations. It develops randomized quasi-Gauss–Newton methods that approximate Gram matrices and establishes local superlinear convergence for underdetermined systems and condition-number-free linear convergence for overdetermined systems.

  • Problem

    Existing quasi-Newton guarantees are largely limited to square systems, while general systems require an accurate initial Jacobian estimator or exact Gram-matrix access.

  • Method

    The paper develops randomized quasi-Gauss–Newton methods that approximate the Gram matrix using randomized-direction Broyden family updates.

  • Results

    The methods achieve local superlinear convergence for underdetermined systems and condition-number-free linear convergence to stationary points of the nonlinear least-square formulation for overdetermined systems.

  • Takeaways & Limitations

    RQGN extends local convergence guarantees to both underdetermined and overdetermined nonlinear equations without requiring a sufficiently accurate initial Jacobian estimator.

  • Takeaways & Limitations

    Existing non-asymptotic superlinear guarantees remain limited to square systems, and general-system methods may require accurate Jacobian initialization or exact Gram-matrix access.

Abstract

from arXiv · show

This paper considers the local convergence for solving general nonlinear equations. We establish randomized quasi-Gauss--Newton methods based on the approximation of the Gram matrix, addressing both the underdetermined and the overdetermined settings. For the underdetermined case, we show that our methods achieve local superlinear convergence to the optimal solution. For the overdetermined case, we show that our methods achieve local condition-number-free convergence to the stationary point of the nonlinear least-square formulation of the problem. In contrast, existing quasi-Newton methods mostly focus on square systems and additionally require the initial Jacobian estimate to be sufficiently close to the exact one.

1 Introduction

The paper targets limitations in quasi-Newton methods for general nonlinear equations and introduces randomized quasi-Gauss–Newton methods with guarantees for both underdetermined and overdetermined systems.

  • Existing non-asymptotic superlinear convergence guarantees are limited to square systems, leaving the general case unclear.
  • Existing methods require either an accurate initial Jacobian estimator or the exact Gram matrix, increasing computational cost.
  • RQGN methods approximate the Gauss–Newton Gram matrix using randomized-direction Broyden family updates.
  • RQGN applies to both underdetermined and overdetermined systems without requiring the exact Gram matrix or an accurate initial Jacobian approximation.
  • Underdetermined systems receive explicit local superlinear convergence rates without assuming solution uniqueness.
  • Overdetermined systems receive explicit local condition-number-free linear convergence rates toward stationary points of the nonlinear least-square formulation, even when no solution exists.

2 Notation and Preliminaries

This section defines the mapping, Jacobian, Gram matrix, regularity assumptions, and randomized quasi-Newton updates used to analyze RQGN.

  • The framework uses a differentiable mapping F: R^d → R^n with Jacobian J and sets m ≜ min{n, d} for Gram-matrix notation.
  • The assumptions impose bounded Lipschitz continuity on the Jacobian and a lower singular-value bound σ_m(J(x)) ≥ µ on a nonempty set Ω.
  • Under these assumptions, the Gram matrix is Lipschitz continuous and bounded above and below by spectral constants.
  • BFGS, fast BFGS, and SR1 updates approximate a positive-definite target matrix from a current estimator and update direction.
  • For Gaussian update directions, fast BFGS and SR1 contract their respective error quantities in expectation by a factor involving 1 − 1/m.
  • The updates preserve the matrix bounds H ⪯ G ⪯ ηH when initialized within those bounds.

3 Randomized Quasi-Gauss–Newton Methods

RQGN replaces the exact Gauss–Newton Gram matrix with a randomized quasi-Newton estimator and uses scaled updates to maintain the relations needed for convergence analysis.

  • RQGN constructs a square estimator G for J(x)J(x)^⊤ or J(x)^⊤J(x), depending on whether the system is underdetermined or overdetermined.
  • The iteration uses J(x)^⊤G^-1F(x) for n < d and G^-1J(x)^⊤F(x) for n ≥ d.
  • At the next point, G is rescaled and updated with BFGS, fast BFGS, or SR1 using a Gaussian direction.
  • A scaled identity matrix can initialize the Gram estimator, with G0 = cI_m for c ≥ L2, and each quasi-Newton update costs O(m^2) flops.
  • Appropriate scaling maintains a partial Gram-matrix relation that unscaled quasi-Newton updates cannot guarantee for general nonlinear equations.

4 The Convergence Analysis

The analysis establishes how randomized Gram-matrix approximations behave and derives local convergence guarantees for both underdetermined and overdetermined nonlinear equations. The results include underdetermined local superlinear convergence and overdetermined condition-number-free linear convergence, with superlinear convergence under stronger conditions.

  • General convergence framework: Lemma 10 bounds the Gram estimator by H_t ⪯ G_t ⪯ (1 + δ_t)H_t and controls the expected evolution of δ_t.The bound applies along iterates remaining in the local region and is established for the randomized quasi-Gauss–Newton analysis.
  • Underdetermined case: For underdetermined systems, the analysis maintains iterates in a local region and establishes explicit local convergence guarantees under a local lower bound on the Jacobian singular values.The lower singular-value assumption is required only on the local region because the analysis is local.
  • Underdetermined case: The underdetermined method achieves local superlinear convergence, while its Gram estimator can be initialized with G_0 = L^2I_n rather than a sufficiently accurate Jacobian estimate.The initialization yields η_0 ≤ L^2/μ^2, and the convergence statement includes a finite-time high-probability bound.
  • Overdetermined case: For overdetermined systems, the analysis targets stationary points of the nonlinear least-square objective and uses a weighted norm to handle the discrepancy between G and the exact Gram matrix.The weighted metric is well-defined when the modified Hessian is positive definite in the local region.
  • Overdetermined case: The overdetermined analysis keeps all iterates in the local region and establishes a two-stage local linear convergence rate with finite-time bounds on Gram approximation error.The result is derived under assumptions guaranteeing a stationary point and local regularity around it.
  • Overdetermined case: Under the stronger condition θ = 0, the overdetermined method also achieves local superlinear convergence, including settings such as square nonlinear equations and strongly-convex-strongly-concave minimax optimization.Without this strengthened condition, the overdetermined rate can retain an additional cθ term and need not be superlinear.

5 Numerical Experiments

The experiments evaluate RQGN methods on underdetermined, overdetermined, and square nonlinear problems, comparing iterations and CPU time with baseline methods. Across these settings, the reported results show faster convergence and lower running time for RQGN in the highlighted comparisons.

  • Experimental settings: RQGN methods are evaluated on scientific-computing eigenvalue problems, generalized linear models, and fairness-aware machine-learning problems.The experiments use underdetermined eigenvalue equations, overdetermined nonlinear least squares, and square nonlinear equations from a minimax formulation.
  • Underdetermined case: For the eigenvalue problem, RQGN methods are compared with gradient descent and generalized Broyden methods for n ∈ {300, 400, 500}.The comparison reports iteration counts and CPU time in Figure 1.
  • Underdetermined case: RQGN methods outperform the baseline algorithm in most cases on the underdetermined eigenvalue experiments.The reported metrics are iterations and CPU time.
  • Overdetermined case: RQGN methods are compared with gradient descent on the “a1a,” “w1a,” and “splice” real-world data sets.The experiments report iterations and CPU time for all three data sets in Figure 2.
  • Overdetermined case: RQGN methods show faster local convergence behavior and less running time than the baseline on the generalized linear-model experiments.These results are reported for the three LIBSVM data sets.
  • Square case: For fairness-aware machine learning, RQGN methods are compared with extragradient on the “heart,” “adult,” and “law school” data sets.The paper reports empirical results on iterations and CPU time in Figure 3 and observes that RQGN converges much faster than EG.

6 Conclusion and Future Work

The paper proposes RQGN methods for both overdetermined and underdetermined nonlinear equations and establishes local convergence guarantees for each setting. It also identifies global convergence of quasi-Newton methods for general nonlinear equations as future work.

  • Conclusion: RQGN methods address both overdetermined and underdetermined nonlinear equations.The methods are based on randomized quasi-Gauss–Newton updates.
  • Conclusion: The methods have condition-number-free linear rates for the overdetermined case and superlinear rates for the underdetermined equation.These are local convergence guarantees.
  • Conclusion: The convergence results do not depend on the sufficiently accurate initial Jacobian estimator required by Broyden’s methods.This distinguishes the stated convergence guarantees from that requirement.
  • Future work: Future work is to study global convergence of quasi-Newton methods for general nonlinear equations.The paper frames this as extending existing global results for convex optimization and monotone variational inequalities.

A Proofs for Sections 2 and 3

This appendix provides detailed proofs for propositions in Sections 2 and 3.

  • Proofs: Detailed proofs are provided for the propositions in Sections 2 and 3.

A.1 Proof of Proposition 3

The appendix establishes auxiliary matrix and recurrence relations used to analyze the randomized quasi-Gauss–Newton methods. It then derives bounds and high-probability statements for the underdetermined and overdetermined cases.

  • Auxiliary results: The proof develops a spectral-equivalence lemma relating a1A ⪯ B ⪯ a2A to a1I_m ⪯ A^-1/2BA^-1/2 ⪯ a2I_m.The equivalence is shown in both directions using quadratic-form arguments.
  • Matrix bounds: The analysis proves that the Gram-matrix approximation remains bounded between H_t and (1 + δ_t)H_t through induction.The induction uses Proposition 5 and Lemma 9 to preserve the partial matrix relation.
  • Randomized options: For Options I–III, the proof derives distinct bounds on the expected approximation error, with γ = μ^2/(mL^2) for Option I and γ = 1/m for Options II and III.Option III additionally introduces the factor L^2/μ^2 in the resulting constant.
  • Underdetermined case: The underdetermined analysis uses induction to maintain x_t ∈ Ω_under and the matrix relation H_t ⪯ G_t ⪯ η_tH_t.The initialization follows from Algorithm 1 and η_0, while the induction step applies Lemma 14 and Proposition 5.
  • Underdetermined case: With probability at least 1 − p, the underdetermined error ratio satisfies the bound obtained by applying Lemma 31 with X_t = λ_under,t+1/λ_under,t.The argument uses the recursion and γ ∈ (0, 1).
  • Overdetermined case: The overdetermined analysis verifies the assumptions needed for local bounds using Lipschitz continuity of H(·) and conditions on the Hessians ∇^2F_i(·).One case uses F(x*) = 0, which makes x* a stationary point of ϕ(·).

B.8 Proof of Lemma 24

The proof establishes local bounds for the overdetermined update by separately controlling the quantities u, v, and w. These bounds are combined to obtain the stated inequalities and support the induction argument.

  • B.8 Proof of Lemma 24: The proof decomposes the update analysis into upper bounds for the quantities u, v, and w.These bounds are subsequently substituted into equation (95).
  • Upper bounds: The bound for u follows from the matrix condition on G, inverse inequalities, and the spectral-equivalence lemma.The lemma is applied with A = (∇̃^2ϕ(x))^-1 and B = G^-1.
  • Upper bounds: The proof combines the bounds on u, v, and w to establish equation (31), then derives equation (30) using the condition on λ_over(x).The final inequalities use the definitions of C1 and K.
  • Induction: The induction argument maintains equations (112) and (35) for all iterations by applying Lemma 24 and Proposition 5 to consecutive iterates.The base case follows from η_0 and the initial condition.

B.10 Proof of Theorem 26

Theorem 26 is proved by combining recursive bounds for the overdetermined error quantities with expectation and high-probability arguments. The induction preserves the required matrix relation and convergence-region conditions.

  • B.10 Proof of Theorem 26: The proof starts from the initial condition of Theorem 25 and combines it with the recursive overdetermined bounds.The notation λ_over,t = λ_over(x_t) is used throughout the argument.
  • Matrix control: The matrix relation H_t ⪯ G_t ⪯ (1 + δ_t)H_t and the bound on E_t[δ_t+1] provide the conditions needed for Lemma 24.The resulting step is applied with η = 1 + δ_t.
  • Recursive bounds: Expectation bounds are iterated using ν = min{γ, (1 − cθ)/(2η_0)} to control the overdetermined sequence across iterations.The proof uses exponential bounds and the condition ν ≤ γ.
  • High-probability result: With probability at least 1 − p, the high-probability result follows by defining events E_j and applying a union bound and Markov’s inequality.The argument then derives an upper bound valid for all t ≥ 1.

B.11 Proof of Corollary 28

The corollary proof specializes the overdetermined recursion by setting θ = 0. It then applies the probabilistic recurrence lemma to obtain a high-probability bound for the resulting error quantity.

  • B.11 Proof of Corollary 28: Setting θ = 0 in the recursive relations yields bounds involving ξ_t = δ_t + C2λ_over,t.The proof uses 1 + x ≤ e^x to control the recurrence.
  • B.11 Proof of Corollary 28: The expectation bound is combined with Lemma 31 using X_t = ξ_t, a = q_over, and τ = 1/γ.This produces the stated probabilistic inequality.
  • B.11 Proof of Corollary 28: With probability at least 1 − p, the resulting upper bound holds for all t ≥ 1.This is the final high-probability conclusion of the corollary proof.

C Implementation of RQGN with F-BFGS

This section presents Algorithm 2, an implementation of RQGN using a fast BFGS update, with a closed-form iteration costing O(m^2) flops per iteration.

  • Algorithm 2 implements RQGN with the fast BFGS update, also called Option II.It is described as an instance of Algorithm 1 with a specified choice of G_t.
  • The update for G_{t+1} can be implemented through a closed-form iteration.The construction follows cited prior propositions and equations.
  • O(m^2) flops are required per iteration.
  • The algorithm takes x_0 ∈ Ω, L_0 ∈ R^{m×m}, a matrix inequality condition on (L_0^⊤L_0)^−1, and M ≥ 0 as inputs.
  • The method proceeds over iterations indexed by t = 0, 1, … until the algorithm terminates.
Loading 2608.27084v1…