Online Learning to Precondition II. Quasi-Newton methods

This blog continues the previous discussion on “online learning to precondition”, and I’ll show that the renowned quasi-Newton (QN) family carries the same “online learning” insight, albeit with a more intricate analysis. In particular, the secant equation used in quasi-Newton methods can be interpreted as a loss function that learns the (inverse) Hessian at the optimum.

AI-disclosure. All my blogs marked by emphasize insights behind technical results, and I write the whole blog draft by myself. Generative AI tools are only used for result verification/proofreading.

Introduction and background

Again, to simplify the discussion, I’ll resort to the quadratic function convention

\[ \min_{x \in \mathbb{R}^n} \quad \tfrac{1}{2} \langle x, A x \rangle - \langle b, x \rangle =: f (x) \]

where \(\mu I \preceq A \preceq L I\). For unconstrained optimization of medium sizes, arguably the most widely used algorithm is quasi-Newton method (Nocedal and Wright 2006; Fletcher 2000). The first quasi-Newton method, now known as DFP update, was invented by William C. Davidon in 1959 (Davidon 1991). After years of development, many QN variants have been proposed, and the most effective variants, such as BFGS and SR1, stand the test of time and are deployed in modern numerical optimization packages.

As most textbooks teach it, locally QN mimics the behavior of Newton’s method by learning the (inverse) Hessian \(\nabla^2 f (x^{\star})\). There is a central equation behind most QN methods, known as secant equation: given two points \(x\) and \(x^+\), for quadratic \(f\), the following two equations hold

\[ \nabla^2 f (x^{\star}) (x^+ - x) = \nabla f (x^+) - \nabla f (x) \quad \text{and} \qquad [\nabla^2 f (x^{\star})]^{- 1} (\nabla f (x^+) - \nabla f (x)) = x^+ - x \]

Define the step vector \(s = x^+ - x\) and the corresponding yield vector \(y = \nabla f (x^+) - \nabla f (x)\), the equations can be equivalently written as

\[ P^{\star} y - s = B^{\star} s - y = 0, \]

where \(P^{\star} = [\nabla^2 f (x^{\star})]^{- 1}\) and \(B^{\star} = \nabla^2 f (x^{\star})\). Given an existing \(P\) (or \(B\)) and the secant equation \(P^{\star}\) (or \(B^{\star}\)) should satisfy, QN looks for \(P_+ \in \mathcal{P}\) following the “least change” principle (Fletcher 1991)

\[ \begin{array}{rcl} P_+ & = & \min_{Q \in \mathcal{P}} V_d (Q, P)\\ \text{subject to} & & \hspace{3em} Q y = s, \end{array} \]

where \(V_d (Q, P)\) is a matrix Bregman divergence induced by a strictly convex kernel \(d\). Different choices of \(d\), learning object \(P^{\star}, B^{\star}\), and the set give different variants of QN.

Table 1: Instantiations of different quasi-Newton variants.

Learning object & secant equation	Kernel \(d\)	Matrix space	Quasi-Newton variant
\(P^{\star} = [\nabla^2 f(x^{\star})]^{-1},\quad Py=s\)	\(\tfrac12\|\cdot\|_F^2\)	\(\mathbb{S}^n\)	Powell-symmetric-Broyden
		\(\mathbb{R}^{n\times n}\)	Broyden’s bad update
	\(-\log\det\)	\(\mathbb{S}^n_{++}\)	DFP
\(B^{\star}=\nabla^2 f(x^{\star}),\quad Bs=y\)	\(\tfrac12\|\cdot\|_F^2\)	\(\mathbb{S}^n\)	Powell-symmetric-Broyden
		\(\mathbb{R}^{n\times n}\)	Broyden’s good update
	\(-\log\det\)	\(\mathbb{S}^n_{++}\)	BFGS

Quasi-Newton and OL2P

To see how QN fits into the OL2P idea. I’ll use Broyden’s update

\[ B_+ = B - \tfrac{(B s - y) s^{\top}}{\| s \|^2} \]

as a demo and introduce a useful tool from the literature.

Proximal point and Moreau envelope descent.

The QN subproblem can be written more compactly as proximal minimization with an indicator \(\mathbb{I} \{ Q s = y \}\):

\[ B_+ = \arg \min_Q \left\{ \mathbb{I} \{ Q s = y \} + \tfrac{\rho}{2} \| Q - B \|_F^2 \right\}, \tag{1}\]

where \(\rho > 0\) is the proximal parameter. Furthermore, a proximal point update as in Equation 1 can be further written as gradient descent on the Moreau envelope function (Parikh and Boyd 2014)

\[ \ell^{\rho}_{y, s} (B) = \min_Q \left\{ \mathbb{I} \{ Q s = y \} + \tfrac{\rho}{2} \| Q - B \|_F^2 \right\}, \]

where \(\ell^{\rho}_{y, s} (B)\) satisfies the following properties

Proposition 1 The function \(\ell^{\rho}_{y, s} (B) = \tfrac{\rho}{2 \| s \|^2} \| B s - y \|^2\) with \(s \neq 0\) has the following properties:

1. it is \(\rho\)-smooth and convex;

2. its gradient is \(\nabla \ell^{\rho}_{y, s} (B) = \rho (B - B_+) = \rho \tfrac{(B s - y) s^{\top}}{\| s \|^2}\);

3. it satisfies \(\ell^{\rho}_{y, s} (B^{\star}) = 0\).

Therefore, we can write

\[ B_+ = B - \tfrac{1}{\rho} \rho (B - B_+) = B - \tfrac{1}{\rho} \nabla \ell^{\rho} (B) . \]

In other words, QN can be viewed as online gradient descent on the smoothed loss \(\ell^{\rho}_{y, s}\).

Now we can formally write Broyden’s update in this format. Note that we do not consider any globalization procedure for brevity. Also we will resort to the shorthand notation \(\ell^{\rho}_k = \ell^{\rho}_{y^k, s^k}\).

\begin{algorithm}
\caption{Broyden's (bad) update with null step}
\begin{algorithmic}
\Require $x^1, P_1, \eta = \tfrac{1}{\rho} > 0$
\For{$k = 1, \ldots, K$}
  \State $x^{k + 1/2} = x^k - B_k^{-1}\nabla f(x^k)$
  \State \textbf{choose} $x^{k+1} \in \arg\min_{x \in \{x^k,x^{k+1/2}\}} \|\nabla f(x)\|^2$
  \State \textbf{compute} $s^k=x^{k+1/2}-x^k$ and $y^k=\nabla f(x^{k+1/2})-\nabla f(x^k)$
  \State $B_{k+1}=B_k-\eta\nabla\ell_k^\rho(B_k)=\arg\min_Q\left\{\mathbb{I}\{Qs^k=y^k\}+\tfrac\rho2\|Q-B_k\|_F^2\right\}$
\EndFor
\end{algorithmic}
\end{algorithm}

Note that the parameter choice \(\eta = \rho\) recovers the proximal point update, yet theoretically the analysis would hold for fixed value of \(\eta \leq \rho^{- 1}\). To establish the convergence behavior, let’s recall the “either-or” discussion from Blog #3: at each iteration,

• we either achieve good progress in convergence (e.g., good contraction \(r^k = \tfrac{f (x^{k + 1}) - f (x^{\star})}{f (x^k) - f (x^{\star})}\))

• or we reduce the distance between \(B\) and \(B^{\star}\) (e.g., \(\| B - B^{\star} \|_F^2\)).

The “or” relation is easy for QN. Since \(B^{\star}\) minimizes \(\{ \ell_k^{\rho} \}_{k = 1}^K\), we have reduction in the Euclidean distance:

\[ \begin{array}{rcl} \| B_{k + 1} - B^{\star} \|_F^2 & = & \| B_{k + 1} - B^{\star} \|_F^2 - 2 \eta \left[ \ell_k^{\rho} (B_k) - \ell_k^{\rho} (B^{\star}) + \tfrac{1}{2 \rho} \| \nabla \ell_k^{\rho} (B_k) \|_F^2 \right] + \eta^2 \| \nabla \ell_k^{\rho} (B_k) \|_F^2\\ & \leq & \| B_{k + 1} - B^{\star} \|_F^2 - 2 \eta [\ell_k^{\rho} (B_k) - \ell_k^{\rho} (B^{\star})] + 2 \rho \eta^2 [\ell_k^{\rho} (B_k) - \ell_k^{\rho} (B^{\star})] - \tfrac{\eta}{\rho} \| \nabla \ell_k^{\rho} (B_k) \|_F^2\\ & = & \| B_{k + 1} - B^{\star} \|_F^2 - 2 \eta (1 - \rho \eta) [\ell_k^{\rho} (B_k) - \ell_k^{\rho} (B^{\star})] - \tfrac{\eta}{\rho} \| \nabla \ell_k^{\rho} (B_k) \|_F^2\\ & = & \| B_{k + 1} - B^{\star} \|_F^2 - 2 \eta (1 - \rho \eta) \ell_k^{\rho} (B_k) - 2 \eta \ell_k^{\rho} (B_k)\\ (\eta = \rho^{- 1}) & = & \| B_{k + 1} - B^{\star} \|_F^2 - 2 \rho^{- 1} \ell_k^{\rho} (B_k), \end{array} \]

where the first inequality uses cocoercivity of convex functions (Gao et al. 2026) and the last one uses \(\| \nabla \ell_k^{\rho} (B_k) \|_F^2 = 2 \rho \ell_k^{\rho} (B_k)\). Therefore, \(\| B - B^{\star} \|_F^2\) is reduced by an amount that is proportional to \(\ell_k^{\rho} (B_k)\).

However, there is one issue left: the quantity \(\ell_k^{\rho} (B_k) = \tfrac{\rho}{2 \| s^k \|^2} \| B s^k - y^k \|^2\) is simply a weighted residual of secant equation and seems irrelevant to any convergence metric. How can we connect it to a desired quantity such as contraction? This is a nontrivial question. But fortunately, we can stand on the shoulders of the giants. The famous (variant of) the Dennis-Moré condition provides what we need.

Lemma 1 (Dennis–Moré variant) Suppose \(x^+ = x - B^{- 1} \nabla f (x)\). Then with \(s = x^+ - x, y = \nabla f (x^+) - \nabla f (x)\),

\[ \tfrac{\| B s - y \|^2}{\| s \|^2} \geq \tfrac{\mu^2}{2} \tfrac{\beta}{\beta + 1}, \]

where \(\beta := \tfrac{\| \nabla f (x^+) \|^2}{\| \nabla f (x) \|^2}\). Hence \(\ell_{y, s} (B) = \tfrac{\rho}{2 \| s \|^2} \| B s - y \|^2 \geq \tfrac{\rho \mu^2}{4} \frac{\beta}{\beta + 1}\).

With Lemma 1, we have the desired “either-or” relation: at each iteration, we have

• either \(\tfrac{\| \nabla f (x^{k + 1 / 2}) \|^2}{\| \nabla f (x^k) \|^2} = \beta_k\) is good

• or \(\| B_{k + 1} - B^{\star} \|_F^2 \leq \| B_{k + 1} - B^{\star} \|_F^2 - 2 \rho^{- 1} \ell_k^{\rho} (B_k) \leq \| B_{k + 1} - B^{\star} \|_F^2 - \tfrac{\mu^2}{2} \frac{\beta_k}{\beta_k + 1}\).

Note that it is possible that \(\beta_k \rightarrow \infty\) while \(\ell_k^{\rho} (B_k)\) remains bounded, and null step guarantees that

\[ r_k = \tfrac{\| \nabla f (x^{k + 1}) \|^2}{\| \nabla f (x^k) \|^2} = \min \{ \beta_k, 1 \} \]

so that the convergence metric will not blow up.

Potential reduction.

As we did in Blog #3, define the learning potential:

\[ \phi (x, B) := \log \| \nabla f (x) \|^2 + \tfrac{2}{\mu^2} \| B - B^{\star} \|_F^2 . \]

and it is easy to show that this potential reduces by at least a constant in each iteration:

Proposition 2 We have \(\phi (x^{k + 1}, B_{k + 1}) \leq \phi (x^k, B_k) - \tfrac{1}{2}\) for all \(k \geq 1\).

And the total iteration complexity follows immediately.

Theorem 1 The total complexity for finding an \(\varepsilon\)-stationary point of \(f\) is

\[ \mathcal{O} \left( \tfrac{2}{\mu^2} \| B_1 - B^{\star} \|_F^2 + \log \left( \tfrac{\| \nabla f (x^1) \|^2}{\varepsilon} \right) \right) . \]

Superlinear convergence.

We can also obtain superlinear convergence result.

Theorem 2 Algorithm 1 also satisfies the following superlinear convergence rate

\[ \tfrac{\| \nabla f (x^{K + 1}) \|^2}{\| \nabla f (x^1) \|^2} \leq \left( \tfrac{4 \| B_1 - B^{\star} \|_F^2}{\mu^2 K} \right)^K . \]

Final remarks

The perspective of viewing quasi-Newton methods through the lens of online learning is not new. For example, in (Jiang and Mokhtari 2026; Jiang et al. 2023), the authors consider the Dennis-Moré condition as an online loss function and designs an elegant online learning procedure to learn the Hessian. My own work (OSGM) also falls into this category, and I’ll cover them in the next posts.

References

Davidon, William C. 1991. “Variable Metric Method for Minimization.” SIAM Journal on Optimization 1 (1): 1–17.

Fletcher, Roger. 1991. “A New Variational Result for Quasi-Newton Formulae.” SIAM Journal on Optimization 1 (1): 18–21.

Fletcher, Roger. 2000. Practical Methods of Optimization. John Wiley & Sons.

Gao, Wenzhi, Chang He, and Madeleine Udell. 2026. “Small Gradient Norm Regret for Online Convex Optimization.” arXiv Preprint arXiv:2601.13519.

Jiang, Ruichen, Qiujiang Jin, and Aryan Mokhtari. 2023. “Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence.” The Thirty Sixth Annual Conference on Learning Theory, 1962–92.

Jiang, Ruichen, and Aryan Mokhtari. 2026. “Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence: R. Jiang and a. Mokhtari.” Mathematical Programming, 1–64.

Nocedal, J, and S Wright. 2006. Numerical Optimization. Springer.

Parikh, Neal, and Stephen Boyd. 2014. “Proximal Algorithms.” Foundations and Trends in Optimization 1 (3): 127–239.

Appendix

Proof of Lemma 1

For quadratic \(f\), we have \(x^+ = x - B^{- 1} \nabla f (x)\) and \(B (x^+ - x) = - \nabla f (x)\), giving

\[ B s - y = - \nabla f (x) - (\nabla f (x^+) - \nabla f (x)) = - \nabla f (x^+) \]

and

\[ \begin{array}{rcl} \frac{\| B s - y \|^2}{\| s \|^2} & = & \frac{\| \nabla f (x^+) \|^2}{\| x^+ - x^{\star} - (x - x^{\star}) \|^2}\\ & \geq & \frac{1}{2} \frac{\| \nabla f (x^+) \|^2}{\| x^+ - x^{\star} \|^2 + \| x - x^{\star} \|^2}\\ & \geq & \frac{\mu^2}{2} \frac{\| \nabla f (x^+) \|^2}{\| \nabla f (x^+) \|^2 + \| \nabla f (x) \|^2} = \frac{\mu^2}{2} \frac{\tfrac{\| \nabla f (x^+) \|^2}{\| \nabla f (x) \|^2}}{\tfrac{\| \nabla f (x^+) \|^2}{\| \nabla f (x) \|^2} + 1} . \end{array} \]

This completes the proof.

Proof of Proposition 2

By definition, we have

\[ \log \| \nabla f (x^{k + 1}) \|^2 - \log \| \nabla f (x^k) \|^2 = \log \tfrac{\| \nabla f (x^{k + 1}) \|^2}{\| \nabla f (x^k) \|^2} = \log \min \{ \beta_k, 1 \} \]

and \(\| B_{k + 1} - B^{\star} \|_F^2 \leq \| B_k - B^{\star} \|_F^2 - \tfrac{\mu^2}{2} \frac{\beta_k}{\beta_k + 1}\). Hence the potential function is reduced by

\[ \begin{array}{rcl} \phi (x^{k + 1}, B_{k + 1}) & \leq & \phi (x^k, B_k) + \log \min \{ \beta_k, 1 \} - \frac{\beta_k}{\beta_k + 1}\\ & \leq & \phi (x^k, B_k) + \max_{\beta} \left\{ \log \min \{ \beta, 1 \} - \frac{\beta}{\beta + 1} \right\}\\ & = & \phi (x^k, B_k) - \tfrac{1}{2} \end{array} \]

and this completes the proof.

Proof of Theorem 2

If \(\beta \leq 1\), we have \(r = \beta\) and \(\tfrac{\beta}{\beta + 1} \geq \tfrac{\beta}{2} = \tfrac{r}{2}\). Otherwise \(\beta \geq 1\), and we have \(r = 1\) and \(\tfrac{\beta}{\beta + 1} \geq \tfrac{1}{2} = \tfrac{r}{2}\). Hence

\[ \| B_{k + 1} - B^{\star} \|_F^2 \leq \| B_k - B^{\star} \|_F^2 - \tfrac{\mu^2}{2} \tfrac{\beta_k}{\beta_k + 1} \leq \| B_k - B^{\star} \|_F^2 - \tfrac{\mu^2 r_k}{4} \]

and \(\sum_{k = 1}^K r_k \leq \frac{4 \| B_1 - B^{\star} \|_F^2}{\mu^2}\), giving

\[ \frac{\|\nabla f(x^{K+1})\|^2}{\|\nabla f(x^1)\|^2} = \prod_{k=1}^K r_k \leq \left(\frac{1}{K}\sum_{k=1}^K r_k\right)^K \leq \left(\frac{4\|B_1-B^{\star}\|_F^2}{\mu^2 K}\right)^K. \]

and completes the proof.