---
abstract: |
    In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Davidon–Fletcher–Powell(DFP) method and the Broyden–Fletcher–Goldfarb–Shanno(BFGS) method which are two well-known quasi-Newton methods. The asymptotic superlinear convergence rate of these quasi-Newton methods has been extensively studied, but their explicit finite time local convergence rate has not been established yet. In this paper, we provide a finite time (non-asymptotic) convergence analysis for BFGS and DFP methods under the assumptions that the objective function is strongly convex, its gradient is Lipschitz continuous, and its Hessian is Lipschitz continuous only in the direction of the optimal solution. We show that in a local neighborhood of the optimal solution, the iterates generated by both DFP and BFGS converge to the optimal solution at a superlinear rate of $(\frac{1}{k})^\frac{k}{2}$, where $k$ is the number of iterations. Numerical experiments on different objective functions confirm our explicit convergence rates. Our theoretical guarantee is one of the first results that provide a non-asymptotic superlinear convergence rate for DFP and BFGS quasi-Newton methods.

    **Keywords:** Quasi-Newton method, superlinear convergence rate, non-asymptotic analysis, DFP algorithm, BFGS algorithm
author:
- 'Qiujiang Jin[^1]Aryan Mokhtari[^2]'
bibliography:
- 'bmc\_article.bib'
title: '**Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods**'
---

Introduction
============

In this paper, we study the problem of minimizing a strongly convex and smooth function $f:\mathbb{R}^d\to \mathbb{R}$, i.e., $$\min_{x \in \mathbb{R}^d} f(x).$$ Denote $x_*$ as the optimal solution of this problem and $\|\cdot\|$ as the Euclidean norm in $\mathbb{R}^{d}$ and $l_{2}$ norm for a matrix. The inner product of vectors $u, v \in \mathbb{R}^{d}$ is indicated by $u^\top v$. Since the objective function $f$ is strongly convex, it has a unique optimal solution $x_*$.

There is an extensive literature on the use of first-order methods for solving this class of problems. Under the smoothness and strong convexity assumptions, it is well-known that the best possible convergence rate for first-order methods is a linear rate. Specifically, we say a sequence $\{x_k\}$ converges linearly if $\|x_k - x_*\|\leq C\rho^k\|x_0 - x_*\|$, where $\rho\in (0, 1)$ is the constant of linear convergence, and $C$ is a constant possibly depending on problem parameters. Among first-order methods, the accelerated gradient method proposed by @nesterov1983method achieves a fast linear convergence rate of $\left(1-\sqrt{\frac{\mu}{L}}\right)^{k/2}$, where $\mu$ is the strong convexity parameter and $L$ is the smoothness parameter (the Lipschitz constant of the gradient) [@nesterov2013introductory]. <span>It is also known that the convergence rate of the accelerated gradient method is optimal for first-order methods in the setting when the dimension of the space $d$ is sufficiently larger than the number of iterations [@nemirovsky1983problem]. </span>

Classical alternatives to improve convergence rate of first-order methods are second-order methods [@bennett1916newton; @ortega1970iterative; @conn2000trust; @nesterov2006cubic] and in particular Newton's method. It has been shown that if in addition to smoothness and strong convexity assumptions, the objective function $f$ is self-concordant or has Lipschitz continuous Hessian, the iterates generated by Newton's method converge to the optimal solution at a quadratic rate in a local neighborhood of the optimal solution; see [@boyd04 Chapter 9]. Despite the fact that the quadratic convergence rate of Newton's method holds only in a local neighborhood of the optimal solution, it could reduce the overall number of iterations significantly as it is substantially faster than the linear rate of first-order methods. The fast quadratic convergence rate of Newton's method, however, does not come for free. Implementation of Newton's method requires solving a linear system at each iteration with the matrix defined by the objective function Hessian $\nabla^2 f(x)$. As a result, the computational cost of implementing Newton's method in high-dimensional problems is prohibitive, as it could be $\mathcal{O}(d^3)$, unlike first-order methods that have a cost of $\mathcal{O}(d)$ per iteration.

Quasi-Newton methods are quite popular since they serve as a middle ground between first-order methods and Newton-type algorithms. They improve the linear convergence rate of first-order methods and achieve a local superlinear rate, and their computational cost per iteration is $\mathcal{O}(d^2)$. The main idea of quasi-Newton methods is to approximate the step of Newton's method without computing the objective function Hessian $\nabla^2 f(x)$ or its inverse $\nabla^2 f(x)^{-1}$ at every iteration [@nocedal2006numerical Chapter 6]. To be more specific, quasi-Newton methods aim at approximating the curvature of the objective function by using only first-order information of the function, i.e., its gradients $\nabla f(x)$; see Section \[sec:QN\_methods\] for more details.

There exists several different approaches for approximating the objective function Hessian and its inverse using first-order information which lead to different quasi-Newton updates, but perhaps the most popular quasi-Newton algorithms are the Symmetric Rank-One (SR1) method [@conn1991convergence], Broyden's method [@broyden1965class; @Broyden; @gay1979some], the Davidon-Fletcher-Powell (DFP) method [@davidon1959variable; @fletcher1963rapidly], the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method [@broyden1970convergence; @fletcher1970new; @goldfarb1970family; @shanno1970conditioning], and the limited-memory BFGS (L-BFGS) method [@nocedal1980updating; @liu1989limited].

As mentioned earlier, in a local neighborhood of the optimal solution, some quasi-Newton methods asymptotically converge to the optimal solution at a superlinear rate. Specifically, the ratio between the distance to the optimal solution at time $k+1$ and $k$ approaches zero as $k$ approaches infinity, i.e., $$\lim_{k\to\infty } \frac{\|x_{k+1} - x_*\|}{\|x_k - x_*\|} =0.$$ For various settings, this superlinear convergence result has been established for a large class of quasi-Newton methods including Broyden's method [@broyden1970convergence; @Broyden; @more1976global], the DFP method [@powell1971convergence; @Broyden; @dennis1974characterization], the BFGS method [@Broyden; @dennis1974characterization; @byrd1987global; @gao2019quasi], and several other variants of these algorithms [@griewank1982local; @dennis1989convergence; @yuan1991modified; @al1998global; @li1999globally; @yabe2007local; @mokhtari2017iqn]. Although this result is promising and lies between the linear rate of first-order methods and the quadratic rate of Newton's method, it only holds asymptotically and does not characterize an explicit upper bound on the error of quasi-Newton methods after a finite number of iterations. As a result, the overall complexity of quasi-Newton methods for achieving an $\epsilon$-accurate solution, i.e., $\|x_k - x_*\|\leq \epsilon$, is unknown. Hence, it is essential to establish a non-asymptotic convergence rate for quasi-Newton methods, which is the main goal of this paper.

In this paper, we show that if the initial iterate is sufficiently close to the optimal solution and the initial Hessian approximation error is sufficiently small, then the iterates of both DFP and BFGS methods converge to the optimal solution at a superlinear rate of $(\frac{1}{k})^\frac{k}{2}$. We further show that our theoretical result suggests a trade-off between the size of the superlinear convergence neighborhood and the rate of superlinear convergence. In other words, one can improve the rate of superlinear convergence at the cost of reducing the radius of the neighborhood in which DFP and BFGS converge superlinearly. We believe that our theoretical guarantee provides one of the first non-asymptotic results for the superlinear convergence rate of BFGS and DFP.

Related Work
------------

In a recent work, @rodomanov2020greedy study the non-asymptotic analysis of a class of *greedy* quasi-Newton methods that are based on the updating formulas of the Broyden family and use greedily selected basis vectors for updating Hessian approximations. In particular, @rodomanov2020greedy show a superlinear convergence rate of $(1-\frac{\mu}{dL})^{k^2/2}(\frac{dL}{\mu})^k$ for this class of algorithms. Note that greedy quasi-Newton methods are more computationally costly than standard quasi-Newton methods because they require computing greedily selected basis vector. Such computation requires additional information beyond the gradient of the objective function, e.g., the diagonal components of the Hessian at each iteration.

Also, in two very recent concurrent papers, @rodomanov2020rates [@rodomanov2020ratesnew] study the non-asymptotic superlinear convergence rate of DFP and BFGS methods. In [@rodomanov2020rates], the authors show that when the objective function is smooth, strongly convex, and strongly self-concordant, the iterates of BFGS and DFP, in a local neighborhood of the optimal solution, achieve a superlinear convergence rate of $(\frac{dL}{\mu k})^{k/2}$ and $(\frac{dL^2}{\mu^2 k})^{k/2}$ respectively. In the follow-up paper [@rodomanov2020ratesnew], they improve the superlinear convergence results to be $[\frac{L}{\mu}(e^{\frac{d}{k}\ln{\frac{L}{\mu}}} - 1)]^{k/2}$ and $[e^{\frac{d}{k}\ln{\frac{L}{\mu}}} - 1]^{k/2}$, respectively. The proof techniques, assumptions, and final theoretical results of [@rodomanov2020rates; @rodomanov2020ratesnew] and our paper are different and derived independently. The major difference is that they use the potential function related with the trace and the logarithm of the determinant of the Hessian approximation matrix ,while we use the Frobenius norm potential function. In addition, we would like to mention that our convergence rates for both DFP and BFGS are independent of the problem dimension $d$. Nevertheless the neighborhood of superlinear convergence depends on $d$. Moreover, to derive our results we require the objective function Hessian to be Lipschitz only with respect to the optimal solution, which is more general than the strongly self-concordant assumption in [@rodomanov2020rates; @rodomanov2020ratesnew].

Outline
-------

In Section \[sec:QN\_methods\], we discuss the steps of different quasi-Newton methods including DFP and BFGS. In Section \[sec:preliminaries\], we mention our main assumptions and notations used as well as some general technical lemmas. Then, in Section \[sec:main\_results\], we present the main theoretical results of our paper on non-asymptotic superlinear convergence of DFP and BFGS. In Section \[sec:discussions\] we provide a detailed discussion on the advantages and drawbacks of our theoretical results. In Section \[sec:experiments\], we present some numerical experiments to compare the convergence rate of BFGS in practice with our theoretical guarantee to confirm our results. Finally, in Section \[sec:conclusion\], we close the paper by stating some concluding remarks.

Quasi-Newton Methods {#sec:QN_methods}
====================

In this section, we formally review the update of quasi-Newton methods, and, in particular, we discuss the update rules for DFP and BFGS methods. Consider a time index $k$, a step size $\eta_k$, and a positive definite matrix $B_k$ to define a generic descent algorithm through the iteration $$\label{QN_update}
    x_{k+1} = x_k - \eta_k B_k^{-1}\nabla f(x_k).$$ Note that if we simply replace $B_k$ by the identity matrix $I$ we recover the update of gradient descent, and if we replace it by the objective function Hessian $\nabla^2 f(x_k)$ we obtain the update of Newton's method. The main goal of quasi-Newton methods is to find a positive definite matrix $B_k$ using only first-order information such that $B_k$ is close to the true Hessian $\nabla^2 f(x_k)$. Note that the step size $\eta_k$ is often computed according to a line search routine for the global convergence of quasi-Newton methods. Our focus in this paper, however, is on the local convergence of quasi-Newton methods, which requires the unit step size $\eta_k=1$. Hence, in the rest of the paper, we assume that the iterate $x_k$ is sufficiently close to the optimal solution $x_*$ and the step size is $\eta_k = 1$.

In several quasi-Newton methods, the function's curvature is approximated in a way that it satisfies the *secant condition*. To better explain this property, let us first define the variable variation $s_k$ and gradient variation $y_k$ as $$\label{ch1_ball}
      s_k := x_{k+1} - x_k,  \quad \text{and} \quad  
      y_k := \nabla f(x_{k+1}) - \nabla f(x_k).$$ The goal is to find a matrix $B_{k+1}$ that satisfies the secant condition $ B_{k+1} s_k = y_k$. The rationale for satisfying the secant condition is that the Hessian $\nabla^2 f(x_k)$ approximately satisfies this condition when $x_{k+1}$ and $x_k$ are close to each other. Notice, however, that the secant condition $ B_{k+1} s_k = y_k$ alone is not enough to completely specify $B_{k+1}$. To resolve this indeterminacy, different quasi-Newton algorithms consider different extra conditions. One common additional constraint is to enforce the Hessian approximation (or its inverse) at time $k+1$ be close to the one computed at time $k$. This is indeed a valid extra condition as we except the Hessian (or its inverse) evaluated at $x_{k+1}$ to be close to the one computed at $x_k$.

In the DFP method, we enforce the proximity condition on Hessian approximations $B_k$ and $B_{k+1}$. Basically, we aim to find the closest positive definite matrix to $B_k$ (in some weighted matrix norm) that satisfies the secant condition; see Chapter 6 of [@nocedal2006numerical] for more details. The Hessian approximation of DFP is given by $$\label{DFP_Hessian_update}
    B_{k+1}= \left(I-\frac{y_k s_k^\top}{y_k^\top s_k}\right) B_k \left(I-\frac{ s_ky_k^\top}{s_k^\top y_k}\right) +\frac{y_k y_k^\top}{y_k^\top s_k}.$$ Since the implementation of the update of quasi-Newton methods in requires access to the inverse of the Hessian approximation, it is essential to derive an explicit update for the Hessian inverse approximation to avoid the cost of inverting a matrix at each iteration. If we define $H_k$ as the inverse of $B_k$, i.e., $H_k=B_k^{-1}$, using the Sherman-Morrison-Woodbury formula, one can write the update of DFP for the Hessian inverse approximation matrices as $$\label{DFP_Hessian_inverse_update}
  H_{k+1} = H_k - \frac{H_k y_k y_k^\top H_k}{y_k^\top H_k y_k} + \frac{s_k s_k^\top}{s_k^\top y_k}.$$ The steps of DFP are summarized in Algorithm \[algo\_DFP\].

\[t\]

\[1\] <span>Initial iterate $x_0$ and initial Hessian inverse approximation $H_0$. Update the variable: $x_{k+1} = x_k - H_k \nabla f(x_k)$; Compute the variable variation $s_k = x_{k+1} - x_k$; Terminate the algorithm Compute the gradient variation $y_k = \nabla f(x_{k+1}) - \nabla f(x_k) $; Update the Hessian inverse approximation $H_{k+1} = H_k - \frac{H_k y_k y_k^\top H_k}{y_k^\top H_k y_k} + \frac{s_k s_k^\top}{s_k^\top y_k}$; </span>

The BFGS method can be considered as the dual of DFP. In BFGS, we also seek a positive definite matrix that satisfies the secant condition, but instead of forcing the proximity condition on the Hessian approximation $B$ we enforce it on the Hessian inverse approximation $H$. To be more precise, we aim to find a psotive definite matrix $H_{k+1}$ that satisfies the secant condition $  s_k = H_{k+1} y_k$ and is the closest matrix (in some weighted norm) to the previous Hessian inverse approximation $H_k$. The update of BFGS method for the Hessian inverse approximation matrix $H_{k+1}$ is given by, $$\label{BFGS_Hessian_inverse_update}
    H_{k+1}= \left(I-\frac{s_k y_k^\top}{y_k^\top s_k}\right) H_k \left(I-\frac{ y_k s_k^\top}{s_k^\top y_k}\right) +\frac{s_k s_k^\top}{y_k^\top s_k}.$$ The steps of BFGS are summarized in Algorithm \[algo\_BFGS\].

It is worth noting that the computation cost of the descent direction $B_k^{-1}\nabla f(x_k)=H_k \nabla f(x_k)$ for the DFP method in and for the BFGS method in is of $\mathcal{O}(d^2)$, which improves $\mathcal{O}(d^3)$ per iteration cost of Newton's method. Also in Algorithm \[algo\_DFP\] and Algorithm \[algo\_BFGS\] the algorithms will be terminated when $s_k = 0$. So in the following analysis we always assume that $s_k \neq 0$. It can also be shown that when the function is strongly convex, we can also ensure that $y_k \neq 0$ and $s_k^\top y_k \neq 0$. Hence, the updates in and are always well-defined.

\[t\]

\[1\] <span>Initial iterate $x_0$ and initial Hessian inverse approximation $H_0$. Update the variable: $x_{k+1} = x_k- H_k \nabla f(x_k)$; Compute the variable variation $s_k = x_{k+1}-x_k$; Terminate the algorithm Compute the gradient variation $y_k = \nabla f(x_{k+1})-\nabla f(x_{k}) $; Update the Hessian inverse approximation $H_{k+1}= \left(I-\frac{s_k y_k^\top}{y_k^\top s_k}\right) H_k \left(I-\frac{ y_k s_k^\top}{s_k^\top y_k}\right) +\frac{s_k s_k^\top}{y_k^\top s_k}$; </span>

Preliminaries {#sec:preliminaries}
=============

In this section, we specify the required assumptions for our theoretical results, introduce some notations to simplify our expressions, and mention some intermediate lemmas that we will use later in Section \[sec:main\_results\] to prove our main theoretical results.

Assumptions
-----------

We next formally state the required assumptions for establishing our theoretical results.

\[ass\_str\_cvx\_smooth\] The objective function $f(x)$ is twice differentiable. Moreover, it is strongly convex with parameter $\mu > 0$ and its gradient $\nabla f$ is Lipschitz continuous with parameter $L > 0$. Hence, $$\mu\| x - y \| \leq \|\nabla{f(x)} - \nabla{f(y)}\| \leq L\| x - y\| \quad \forall x, y \in \mathbb{R}^{d},$$ $$\mu I \preceq \nabla^{2}{f(x)} \preceq LI \quad \forall x \in \mathbb{R}^{d}.$$

As the function $f$ is twice differentiable, the conditions in Assumption \[ass\_str\_cvx\_smooth\] ensure that the eigenvalues of the objective function Hessian are strictly larger than zero and are bounded above by a constant.

\[ass\_Hess\_lip\] The objective function Hessian $\nabla^2 f(x)$ satisfies the following condition for some constant $M > 0$, $$\|\nabla^{2}{f(x)} - \nabla^{2}{f(x_*)}\| \leq M\| x - x_{*}\| \quad \forall x \in \mathbb{R}^{d}.$$

The condition in Assumption \[ass\_Hess\_lip\] is common in the analysis of second-order methods as we need some sort of regularity condition for the objective Hessian. In fact, the condition in Assumption \[ass\_Hess\_lip\] is one of the least strict conditions required for the analysis of second-order type methods as it requires Lipschitz continuity of the Hessian only in the direction of the optimal solution. This condition is, indeed, weaker than assuming that the Hessian is Lipschitz continuous (for any two points). It is also weaker than the strict self-concordance assumption required in [@rodomanov2020rates; @rodomanov2020ratesnew] for smooth functions. Note that when the functions is smooth (has Lipschitz continuous gradient), strict self-concordance assumption implies that that the Hessian is Lipschitz continuous everywhere, which is stronger than the required condition in Assumption \[ass\_Hess\_lip\].

The condition in Assumption \[ass\_Hess\_lip\] also leads to the following result.

\[corollary\] If the condition in Assumption \[ass\_Hess\_lip\] holds, then for all $ x, y \in \mathbb{R}^{d}$ we have $$\|\nabla{f(x)} - \nabla{f(y)} - \nabla^{2}{f(x_*)}(x - y)\| \leq M\|x - y\|\max\{\|x - x_{*}\|, \|y - x_{*}\|\}$$

See Lemma 3.1 in [@Broyden].

We would like to emphasize that our analysis can be easily extended to the case that the conditions in Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\] only hold in a neighborhood of the optimal solution $x_{*}$. Here we assume that they hold in $\mathbb{R}^{d}$ just to simplify our proof and avoid the excessive process.

Notations
---------

In this section, we briefly mention some of the major definitions and notations that will be used in all following theorems and proofs.

For a symmetric positive definite matrix $Q \in \mathbb{R}^{d \times d}$, we define its matrix norm for any matrix $A \in \mathbb{R}^{d \times d}$ as $\|A\|_{Q} = \|QAQ\|_{F}$, where $\|\cdot\|_{F}$ is the Frobenius norm. Moreover, for a symmetric matrix $A$, its induced $2$-norm is denoted by $\|A\|$, i.e., $\|A\|=\max_{\|v\|=1}\|Av\|$.

Throughout the paper, we also analyze and study weighted versions of the Hessian approximation $\hat{B}_k $ and its inverse $\hat{H}_k$, which are formally defined as $$\begin{aligned}
\label{main_def_1}
\hat{B}_k = \nabla^{2}f(x_*)^{-\frac{1}{2}}B_k\nabla^{2}f(x_*)^{-\frac{1}{2}}, \qquad \hat{H}_k = \nabla^{2}f(x_*)^{\frac{1}{2}}H_k\nabla^{2}f(x_*)^{\frac{1}{2}}.\end{aligned}$$ Notice that both $\nabla^{2}f(x_*)^{\frac{1}{2}}$ and $\nabla^{2}f(x_*)^{-\frac{1}{2}}$ are symmetric positive definite matrices. It can be easily verified that $\hat{H}_k $ is the inverse of $\hat{B}_k$ as $
\hat{B}_k^{-1} = \nabla^{2}f(x_*)^{\frac{1}{2}}B_k^{-1}\nabla^{2}f(x_*)^{\frac{1}{2}} = \hat{H}_k.
$ We also use $\|\hat{B}_k - I\|_F$ as the measure of closeness between $B_k$ and $\nabla^{2}f(x_*)$ and $\|\hat{H}_k - I\|_F$ as the measure of closeness between $H_k$ and $\nabla^{2}f(x_*)^{-1}$, which can also be written as $$\label{Hess_def_eq}
   \|\hat{B}_k - I\|_F=  \|B_k - \nabla^{2}f(x_*)\|_{\nabla^{2}f(x_*)^{-\frac{1}{2}}}, \qquad
   \|\hat{H}_k - I\|_F=  \|H_k - \nabla^{2}f(x_*)^{-1}\|_{\nabla^{2}f(x_*)^{\frac{1}{2}}}.$$ We further define the weighted gradient variation $\hat{y}_k$, variable variation $\hat{s}_k$, and gradient $\nabla{\hat{f}(x_k)} $ as $$\begin{aligned}
\label{main_def_2}
\hat{y}_k = \nabla^{2}f(x_*)^{-\frac{1}{2}}y_k, \qquad \hat{s}_k = \nabla^{2}f(x_*)^{\frac{1}{2}}s_k, \qquad \nabla{\hat{f}(x_k)} = \nabla^{2}f(x_*)^{-\frac{1}{2}}\nabla{f(x_k)}.\end{aligned}$$ To measure closeness to the optimal solution for iterate $x_k$, we use $r_k\in \mathbb{R}^n$, $\sigma_k$, and $\tau_k$ which are formally defined as $$\begin{aligned}
\label{main_def_3}
    r_k = \nabla^{2}f(x_*)^{\frac{1}{2}}(x_k - x_*), \qquad 
    \sigma_k = \frac{M}{\mu^{\frac{3}{2}}}\|r_k\|, \qquad
    \tau_k = \max\{\sigma_k, \sigma_{k+1}\},\end{aligned}$$ where $\mu$ is the strong convexity parameter defined in Assumption \[ass\_str\_cvx\_smooth\] and $M$ is the Lipschitz continuity parameter for the Hessian at the optimal solution defined in Assumption \[ass\_Hess\_lip\].

Intermediate Lemmas
-------------------

In this section, we present some general lemmas that we will later use to establish the non-asymptotic superlinear convergence of DFP and BFGS. The proofs of these lemmas are relegated to the appendix.

\[lemma:lemma\_1\] For any symmetric matrix $A \in \mathbb{R}^{d \times d}$ and vector $u \in \mathbb{R}^{d}$ with $\|u\| = 1$ we have $$\label{eq:claim_lemma_11}
    \|A\|^2_F - \|(I - uu^\top)A(I - uu^\top)\|^2_F \geq \|Au\|^2.$$

Check Appendix \[sec:proof\_of\_lemma\_1\].

\[lemma:lemma\_2\] For any symmetric positive definite matrix $A \in \mathbb{R}^{d \times d}$ and arbitrary matrix $B \in \mathbb{R}^{d \times d}$ we have $$\label{lemma_2_1}
    \|AB\|_F \leq \|A\|\|B\|_F,\qquad 
    \|B^\top AB\|_F \leq \|A\|\|B\|^2_F.$$

Check Appendix \[sec:proof\_of\_lemma\_2\].

\[lemma:lemma\_6\] Consider matrices $A,E \in \mathbb{R}^{d \times d}$ such that $A^{-1}$ exists and $\|A^{-1}\|\|E\| < 1$. Then, $(A + E)^{-1}$ exists and its induced $2$-norm is bounded above by $$\|(A + E)^{-1}\| \leq \frac{\|A^{-1}\|}{1 - \|A^{-1}\|\|E\|}$$

Check Theorem 3.1.4 of [@dennisschnabel]

The results in Lemmas \[lemma:lemma\_1\]-\[lemma:lemma\_6\] hold for arbitrary matrices and are not specific to the ones considered in this paper. The next lemma focuses on some properties of the weighted gradient variation $\hat{y}_k$ and weighted variable variation $\hat{s}_k$, when the conditions in Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\] are satisfied.

\[lemma:lemma\_3\] Recall the definitions in - . Suppose that for any $k \geq 0$ we have $\tau_k < 1$, where $\tau_k$ is defined in . If Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\] hold, then the following inequalities hold for $k \geq 0$: $$\label{lemma_3_1}
    \|\hat{y}_k - \hat{s}_k\| \leq \tau_k\|\hat{s}_k\|,$$ $$\label{lemma_3_2}
    (1 - \tau_k)\|\hat{s}_k\|^2 \leq \hat{s}_k^\top\hat{y}_k \leq (1 + \tau_k)\|\hat{s}_k\|^2,$$ $$\label{lemma_3_3}
    (1 - \tau_k)\|\hat{s}_k\| \leq \|\hat{y}_k\| \leq (1 + \tau_k)\|\hat{s}_k\|,$$ $$\label{lemma_3_4}
    \|\nabla{\hat{f}(x_k)} - r_k\| \leq \sigma_k\|r_k\|.$$

Check Appendix \[sec:proof\_of\_lemma\_3\].

Main Theoretical Results {#sec:main_results}
========================

In this section, we characterize the non-asymptotic superlinear convergence of DFP and BFGS quasi-Newton methods. To do so, we first establish a crucial proposition which characterizes the error of Hessian approximation for these quasi-Newton methods in Section \[sec:main\_result\_hess\_appr\]. Then, in Section \[sec:main\_result\_linear\_convergence\], we leverage this result to show that the iterates of DFP and BFGS converge at least linearly to the optimal solution, if the initial distance to the optimal solution and the initial Hessian approximation error are sufficiently small. Finally, we use these intermediate results to prove that the iterates of both DFP and BFGS methods converge to the optimal solution at a superlinear rate of $(1/k)^{k/2}$. This result is shown in Section \[sec:main\_result\_superlinear\_convergence\].

Hessian approximation error: Frobenius norm potential function {#sec:main_result_hess_appr}
--------------------------------------------------------------

In this section, we use Frobenius norm to quantify the error of Hessian and Hessian inverse approximation in DFP and BFGS methods. To do so, we will use the results of Lemma \[lemma:lemma\_1\], Lemma \[lemma:lemma\_2\], and Lemma \[lemma:lemma\_3\] to derive the Frobenius norm potential functions of Hessian approximation matrix for both DFP and BFGS updates. These potential functions play fundamental roles in our proof of superlinear convergence of quasi-Newton methods. Next, we show how the error of Hessian approximation $\|\hat{B}_{k+1} - I\|_F$ in DFP evolves as time progresses.

\[lemma:lemma\_4\] Consider the update of DFP in and recall the definition of $\tau_k$ in . Suppose that there exists $\delta > 0$ such that for $k \geq 0$ we have that $\tau_k < 1$ and $\|\hat{B}_k - I\|_{F} \leq \delta$. Then, the matrix $B_{k+1}$ generated by the DFP update satisfies the following inequality $$\|\hat{B}_{k+1} - I\|_F \leq \|\hat{B}_k - I\|_{F} - \frac{\|(\hat{B}_k - I)\hat{s}_k\|^2}{2\delta\|\hat{s}_k\|^2} + W_k\tau_k,$$ where $W_k = \|\hat{B}_k\|\frac{4}{1 - \tau_k} + \|\hat{B}_k\|\frac{4\tau_k}{(1 - \tau_k)^2} + \frac{3 + \tau_k}{1 - \tau_k}$.

Recall the DFP update in and multiply both of sides of that expression with the matrix $\nabla^{2}f(x_*)^{-\frac{1}{2}}$ to obtain $$\hat{B}_{k+1} = \left(I - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{y}_k^\top\hat{s}_k}\right)\hat{B}_{k}\left(I - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right) +\frac{\hat{y}_k\hat{y}_k^\top}{\hat{y}_k^\top\hat{s}_k},$$ where we used the fact that $s_k^\top y_k = s_k^\top \nabla^{2}f(x_*)^{\frac{1}{2}}\nabla^{2}f(x_*)^{-\frac{1}{2}}y_k = \hat{s}_k^\top \hat{y}_k$. Using this expression we can show that $\hat{B}_{k+1} - I $ can be written as $$\begin{split}
    &\hat{B}_{k+1} - I \\
    & = \left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} + \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} -  \frac{\hat{y}_k\hat{s}_k^\top}{\hat{y}_k^\top\hat{s}_k}\right)\hat{B}_k\left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} + \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} -  \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right) - I  + \frac{\hat{y}_k\hat{y}_k^\top}{\hat{y}_k^\top\hat{s}_k}\\
    & = \left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right)\hat{B}_k\left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right) +  \left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right)\hat{B}_k\left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_{k}\|^2} - \frac{\hat{s}_{k}\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\\
    & \quad + \left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_{k}\|^2} - \frac{\hat{y}_{k}\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\hat{B}_k\left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right) + \left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\hat{B}_k\left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right) - I + \frac{\hat{y}_k\hat{y}_k^\top}{\hat{y}_k^\top\hat{s}_k}
    \end{split}$$ which can be simplified as $$\begin{split}
    \hat{B}_{k+1} - I 
    & = \left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right)(\hat{B}_k - I)\left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right) + \left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right)\left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right)  - I + \frac{\hat{y}_k\hat{y}_k^\top}{\hat{y}_k^\top\hat{s}_k}\\
    & \quad + \left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right)\hat{B}_k\left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_{k}\|^2} - \frac{\hat{s}_{k}\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right) + \left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_{k}\|^2} - \frac{\hat{y}_{k}\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\hat{B}_k\left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right)\\
    & \quad + \left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\hat{B}_k\left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)
\end{split}$$ If we replace $\left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right)\left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right) $ by its simplified version which is $I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}$, we obtain that $\hat{B}_{k+1} - I$ can be written as the sum of five matrices $$\hat{B}_{k+1} - I = D_k + E_k + F_k + F^\top_k + G_k,$$ where $$\begin{split}
        & D_{k} = \left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right)(\hat{B}_k - I)\left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right), 
        \quad E_{k} = \frac{\hat{y}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k} - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2},\\
        & F_{k} = \left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right)\hat{B}_k\left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_{k}\|^2} - \frac{\hat{s}_{k}\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right),  \quad G_{k} = \left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\hat{B}_k\left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right).
    \end{split}$$ Now we derive upper bounds for the norms of $D_{k}$, $E_{k}$, $F_{k}$ and $G_{k}$. By Lemma \[lemma:lemma\_1\] we have $$\label{proof:eq_1_1_1}
    \|\hat{B}_k - I\|^2_F - \|D_k\|^2_F \geq \frac{\|(\hat{B}_k - I)\hat{s}_k\|^2}{\|\hat{s}_k\|^2}.$$ Use the fact that $a^2 - b^2 \leq 2a(a - b)$ for any real numbers $a$ and $b$ to show $$\label{proof:eq_1_1_2}
    \|\hat{B}_k - I\|^2_F - \|D_k\|^2_F \leq 2\|\hat{B}_k - I\|_F(\|\hat{B}_k - I\|_F - \|D_k\|_F) \leq 2\delta(\|\hat{B}_k - I\|_F - \|D_k\|_F)$$ Combine the results in and to write $$\label{proof:eq_1_1_3}
    \|D_k\|_F \leq \|\hat{B}_k - I\|_F - \frac{\|(\hat{B}_k - I)\hat{s}_k\|^2}{2\delta\|\hat{s}_k\|^2},$$ which provides an upper bound for $\|D_k\|_F$.

Next, we derive an upper bound for $\|E_k\|_F$. Use the fact that $\|ab^\top\|_F = \|a\|\|b\|$ for any $a, b \in \mathbb{R}^d$ and the results in , and from Lemma \[lemma:lemma\_3\] to write $$\begin{split}
    \|E_k\|_F & \leq \|\frac{\hat{y}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k} - \frac{\hat{s}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\|_F + \|\frac{\hat{s}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k} - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\|_F\\
    & \leq \frac{\|\hat{y}_k\hat{y}_k^\top - \hat{y}_k\hat{s}_k^\top\|_F + \|\hat{y}_k\hat{s}_k^\top - \hat{s}_k\hat{s}_k^\top\|_F}{\hat{s}_k^\top\hat{y}_k} +  \frac{|\hat{s}_k^\top(\hat{s}_k - \hat{y}_k)|\|\hat{s}_k\hat{s}_k^\top\|_F}{\|\hat{s}_k\|^2\hat{s}_k^\top\hat{y}_k}\\
    & \leq \frac{(\|\hat{y}_k\| + \|\hat{s}_k\|)\|\hat{y}_k - \hat{s}_k\|}{\hat{s}_k^\top\hat{y}_k} + \frac{\|\hat{s}_k\|\|\hat{s}_k - \hat{y}_k\|}{\hat{s}_k^\top\hat{y}_k}\\
    & \leq \frac{(2 + \tau_k)\tau_k\|\hat{s}_k\|^2}{(1 - \tau_k)\|\hat{s}_k\|^2} + \frac{\tau_k\|\hat{s}_k\|^2}{(1 - \tau_k)\|\hat{s}_k\|^2}\\
    & = \frac{3 + \tau_k}{1 - \tau_k}\tau_k
\end{split}$$

We proceed to derive an upper bound for $\|F_k\|_F$. Notice that $I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}$ is a symmetric matrix and we have that $\left(I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right)^2 = I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}$. This means that $I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}$ is an orthogonal projection matrix and its $l_2$ norm should be $1$. Using this observation and the result in of Lemma \[lemma:lemma\_2\] we can show that $\|F_k\|_F$ is bounded above by $$\begin{aligned}
    \|F_k\|_F & \leq \left\| I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right\|
    \left\|\hat{B}_k\left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\right\|_F\\
    & = \left\|\hat{B}_k\left(\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\right\|_F\\
    & \leq\left  \|\hat{B}_k\right\| \left\|\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|_F\\
      & \leq\left  \|\hat{B}_k\right\| \left\|\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}-\frac{\hat{s}_k\hat{y}_k^\top}{\|\hat{s}_k\|^2}+\frac{\hat{s}_k\hat{y}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|_F,
    \end{aligned}$$ where the first equality follows from the fact that $\left\| I - \frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2}\right\|=1$, the inequalities hold due to the results in Lemma \[lemma:lemma\_2\], and the last equalit is obtained by adding and subtracting $\frac{\hat{s}_k\hat{y}_k^\top}{\|\hat{s}_k\|^2}$. Next, by using the triangle inequality and exploiting the results in , and of Lemma \[lemma:lemma\_3\] we can simplify the upper bound and show $$\begin{aligned}
    \|F_k\|_F  
    & \leq \|\hat{B}_k\|\left(\left\|\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\|\hat{s}_k\|^2}\right\|_F + \left\|\frac{\hat{s}_k\hat{y}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|_F\right)\\
    & = \|\hat{B}_k\|\left(\frac{\|\hat{s}_k(\hat{s}_k - \hat{y}_k)^\top\|_F}{\|\hat{s}_k\|^2} + \frac{|\hat{s}_k^T(\hat{s}_k - \hat{y}_k)|\|\hat{s}_k\hat{y}_k^\top\|_F}{\|\hat{s}_k\|^2\hat{s}_k^\top\hat{y}_k}\right)\\
    & \leq \|\hat{B}_k\|\left(\frac{\|\hat{y}_k - \hat{s}_k\|}{\|\hat{s}_k\|} + \frac{\|\hat{y}_k - \hat{s}_k\|\|\hat{y}_k\|}{\hat{s}_k^\top\hat{y}_k}\right)\\
    & \leq \|\hat{B}_k\|\left(\tau_k + \frac{\tau_k(1 + \tau_k)}{1 - \tau_k}\right)\\
    & = \|\hat{B}_k\|\frac{2}{1 - \tau_k}\tau_k \end{aligned}$$

At last we provide an upper bound for $\|G_k\|_F$. According to the result of Lemma \[lemma:lemma\_2\], $\|G_k\|_F$ is bounded above by the Cauchy-Schwarz inequality $$\|G_k\|_F \leq \|\hat{B}_k\| \left\|\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|^2_F$$ Notice that by , and in Lemma \[lemma:lemma\_3\] we can write $$\begin{split}
   \left \|\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|_F 
   & \leq \left\|\frac{\hat{s}_k\hat{s}_k^\top}{\|\hat{s}_k\|^2} - \frac{\hat{s}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|_F + \left\|\frac{\hat{s}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|_F\\
    & \leq \frac{|\hat{s}_k^\top(\hat{s}_k - \hat{y}_k)|\|\hat{s}_k\hat{s}_k^\top\|_F}{\|\hat{s}_k\|^2\hat{s}_k^\top\hat{y}_k} + \frac{\|\hat{s}_k(\hat{s}_k - \hat{y}_k)^\top\|_F}{\hat{s}_k^\top\hat{y}_k}\\
    & \leq \frac{\tau_k}{1 - \tau_k} + \frac{\tau_k}{1 - \tau_k}\\
    & = \frac{2\tau_k}{1 - \tau_k},
\end{split}$$ and therefore we obtain $$\|G_k\|_F \leq \|\hat{B}_k\|\frac{4\tau_k}{(1 - \tau_k)^2}\tau_k.$$

If we replace $\|D_k\|_F$, $\|E_k\|_F$, $\|F_k\|_F$, and $\|G_k\|_F$ with their upper bounds we obtain that $$\begin{split}
    \|\hat{B}_{k+1} - I\|_F & \leq \|D_k\|_F + \|E_k\|_F + 2\|F_k\|_F + \|G_k\|_F\\
    & \leq \|\hat{B}_k - I\|_F - \frac{\|(\hat{B}_k - I)\hat{s}_k\|^2}{2\delta\|\hat{s}_k\|^2} + W_k\tau_{k},
\end{split}$$ where $W_k = \|\hat{B}_k\|\frac{4}{1 - \tau_k} + \|\hat{B}_k\|\frac{4\tau_k}{(1 - \tau_k)^2} + \frac{3 + \tau_k}{1 - \tau_k}$, and the proof is complete.

The result in Lemma \[lemma:lemma\_4\] shows how the error of Hessian approximation in DFP evolves as we run more updates. Next, we establish a similar result for the BFGS algorithm with a minor difference. For the BFGS method, we characterize the error of Hessian inverse approximation instead of Hessian approximation. In other words, we study the potential function $\|\hat{H}_{k} - I\|_F$ and derive an upper bound for that in terms of the error at previous step.

\[lemma:lemma\_5\] Consider the update of BFGS in and recall the definition of $\tau_k$ in . Suppose that there exists $\delta > 0$ such that for $k \geq 0$ we have that $\tau_k < 1$ and $\|\hat{H}_k - I\|_{F} \leq \delta$. Then, the matrix $H_{k+1}$ generated by the BFGS update satisfies the following inequality $$\|\hat{H}_{k+1} - I\|_F \leq \|\hat{H}_k - I\|_{F} - \frac{\|(\hat{H}_k - I)\hat{y}_k\|^2}{2\delta\|\hat{y}_k\|^2} + V_k\tau_k,$$ where $V_k = \|\hat{H}_k\|\frac{4}{1 - \tau_k} + \|\hat{H}_k\|\frac{4(1 + \tau_k)^2\tau_k}{(1 - \tau_k)^2} + \frac{3 + 2\tau_k}{1 - \tau_k}$.

Multiply both sides of the BFGS update in with $\nabla^{2}f(x_*)^{\frac{1}{2}}$ from left and right to obtain $$\hat{H}_{k+1} = \left(I - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{y}_k^\top\hat{s}_k}\right)\hat{H}_{k}\left(I - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right) +\frac{\hat{s}_k\hat{s}_k^\top}{\hat{y}_k^\top\hat{s}_k}$$ Using this expression we can show that $\hat{H}_{k+1} - I$ can be written as $$\begin{split}
    \hat{H}_{k+1} - I & = \left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} + \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} -  \frac{\hat{s}_k\hat{y}_k^\top}{\hat{y}_k^\top\hat{s}_k}\right)\hat{H}_k\left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} + \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} -  \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right) - I  + \frac{\hat{s}_k\hat{s}_k^\top}{\hat{y}_k^\top\hat{s}_k}\\
    & = \left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right)\hat{H}_k\left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right) +  \left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right)\hat{H}_k\left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_{k}\|^2} - \frac{\hat{y}_{k}\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\\
    & \quad + \left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_{k}\|^2} - \frac{\hat{s}_{k}\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\hat{H}_k\left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right) + \left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\hat{H}_k\left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\\
    & \quad - I + \frac{\hat{s}_k\hat{s}_k^\top}{\hat{y}_k^\top\hat{s}_k}\\
    & = \left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right)(\hat{H}_k - I)\left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right) + \left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right)\left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right)  - I + \frac{\hat{s}_k\hat{s}_k^\top}{\hat{y}_k^\top\hat{s}_k}\\
    & \quad + \left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right)\hat{H}_k\left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_{k}\|^2} - \frac{\hat{y}_{k}\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right) + \left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_{k}\|^2} - \frac{\hat{s}_{k}\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\hat{H}_k\left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right)\\
    & \quad + \left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\hat{H}_k\left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)
\end{split}$$ Replace $\left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right)\left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right)$ with its simplification $\left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right)$ to obtain that $$\hat{H}_{k+1} - I = D_k + E_k + F_k + F^\top_k + G_k,$$ where $$\begin{split}
        & D_{k} = \left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right)(\hat{H}_k - I)\left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right),\quad E_{k} = \frac{\hat{s}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k} - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2},\\
        & F_{k} = \left(I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right)\hat{H}_k\left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_{k}\|^2} - \frac{\hat{y}_{k}\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right),\quad\! G_{k} = \left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{s}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\hat{H}_k\left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right).
    \end{split}$$ Now we proceed to bound the norm of $D_{k}$, $E_{k}$, $F_{k}$ and $G_{k}$. By Lemma \[lemma:lemma\_1\] we have $$\|\hat{H}_k - I\|^2_F - \|D_k\|^2_F \geq \frac{\|(\hat{H}_k - I)\hat{y}_k\|^2}{\|\hat{y}_k\|^2}$$ Use the fact that $a^2 - b^2 \leq 2a(a - b)$ for any real number $a$ and $b$ we have $$\|\hat{H}_k - I\|^2_F - \|D_k\|^2_F \leq 2\|\hat{H}_k - I\|_F(\|\hat{H}_k - I\|_F - \|D_k\|_F) \leq 2\delta(\|\hat{H}_k - I\|_F - \|D_k\|_F)$$ Combine the above two inequalities to show that $\|D_k\|_F$ is bounded above by $$\|D_k\|_F \leq \|\hat{H}_k - I\|_F - \frac{\|(\hat{H}_k - I)\hat{y}_k\|^2}{2\delta\|\hat{y}_k\|^2}.$$

Next we derive an upper bound for $\|E_k\|_F$. Use the fact that $\|ab^\top\|_F = \|a\|\|b\|$ for any $a, b \in \mathbb{R}^d$ as well as the results in Lemma \[lemma:lemma\_3\] to write $$\begin{split}
    \|E_k\|_F & \leq \|\frac{\hat{s}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k} - \frac{\hat{y}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\|_F + \|\frac{\hat{y}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k} - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\|_F\\
    & \leq \frac{\|\hat{s}_k\hat{s}_k^\top - \hat{y}_k\hat{s}_k^\top\|_F + \|\hat{y}_k\hat{s}_k^\top - \hat{y}_k\hat{y}_k^\top\|_F}{\hat{s}_k^\top\hat{y}_k} +  \frac{|\hat{y}_k^\top(\hat{y}_k - \hat{s}_k)|\|\hat{y}_k\hat{y}_k^\top\|_F}{\|\hat{y}_k\|^2\hat{s}_k^\top\hat{y}_k}\\
    & \leq \frac{(\|\hat{y}_k\| + \|\hat{s}_k\|)\|\hat{y}_k - \hat{s}_k\|}{\hat{s}_k^\top\hat{y}_k} + \frac{\|\hat{y}_k\|\|\hat{s}_k - \hat{y}_k\|}{\hat{s}_k^\top\hat{y}_k}\\
    & \leq \frac{(2 + \tau_k)\tau_k\|\hat{s}_k\|^2}{(1 - \tau_k)\|\hat{s}_k\|^2} + \frac{(1 + \tau_k)\tau_k\|\hat{s}_k\|^2}{(1 - \tau_k)\|\hat{s}_k\|^2}\\
    & = \frac{3 + 2\tau_k}{1 - \tau_k}\tau_k
\end{split}$$

Next, we provide an upper bound for $\|F_k\|_F$. Note that $\|I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\|=1$. Therefore, $$\begin{split}
    \|F_k\|_F & \leq \left\|I - \frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2}\right\|
   \left \|\hat{H}_k\left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\right\|_F\\
    & = \left\|\hat{H}_k\left(\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right)\right\|_F\\
    & \leq \|\hat{H}_k\| \left\|\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|_F
    \end{split}$$ Next, using the triangle inequality and the results in Lemma \[lemma:lemma\_2\] and Lemma \[lemma:lemma\_3\] we have $$\begin{split}
    \|F_k\|_F 
    & \leq \|\hat{H}_k\|\left(\left\|\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\|\hat{y}_k\|^2}\right\|_F + \left\|\frac{\hat{y}_k\hat{s}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|_F\right)\\
    & = \|\hat{H}_k\|\left(\frac{\|\hat{y}_k(\hat{y}_k - \hat{s}_k)^\top\|_F}{\|\hat{y}_k\|^2} + \frac{|\hat{y}_k^T(\hat{s}_k - \hat{y}_k)|\|\hat{y}_k\hat{s}_k^\top\|_F}{\|\hat{y}_k\|^2\hat{s}_k^\top\hat{y}_k}\right)\\
    & \leq \|\hat{H}_k\|\left(\frac{\|\hat{y}_k - \hat{s}_k\|}{\|\hat{y}_k\|} + \frac{\|\hat{s}_k - \hat{y}_k\|\|\hat{s}_k\|}{\hat{s}_k^\top\hat{y}_k}\right)\\
    & \leq \|\hat{H}_k\|\left(\frac{\tau_k}{1 - \tau_k} + \frac{\tau_k}{1 - \tau_k}\right)\\
    & = \|\hat{H}_k\|\frac{2}{1 - \tau_k}\tau_k 
    \end{split}$$

Finally, we upper bound the norm $\|G_k\|_F$. Using the result of Lemma \[lemma:lemma\_2\] we have $$\|G_k\|_F \leq \|\hat{H}_k\| \left\|\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|^2_F$$ Moreover, based on the inequalities in , and we have $$\begin{split}
   \left \|\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|_F & \leq \left\|\frac{\hat{y}_k\hat{y}_k^\top}{\|\hat{y}_k\|^2} - \frac{\hat{y}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|_F + \left\|\frac{\hat{y}_k\hat{y}_k^\top}{\hat{s}_k^\top\hat{y}_k} - \frac{\hat{y}_k\hat{s}_k^\top}{\hat{s}_k^\top\hat{y}_k}\right\|_F\\
    & \leq \frac{|\hat{y}_k^\top(\hat{s}_k - \hat{y}_k)|\|\hat{y}_k\hat{y}_k^\top\|_F}{\|\hat{y}_k\|^2\hat{s}_k^\top\hat{y}_k} + \frac{\|\hat{y}_k(\hat{y}_k - \hat{s}_k)^\top\|_F}{\hat{s}_k^\top\hat{y}_k}\\
    & \leq \frac{(1 + \tau_k)\tau_k}{1 - \tau_k} + \frac{(1 + \tau_k)\tau_k}{1 - \tau_k}\\
    & = \frac{2(1 + \tau_k)\tau_k}{1 - \tau_k},
\end{split}$$ and therefore we have $$\|G_k\|_F \leq \|\hat{H}_k\|\frac{4(1 + \tau_k)^2\tau_k}{(1 - \tau_k)^2}\tau_k.$$

If we replace $\|D_k\|_F$, $\|E_k\|_F$, $\|F_k\|_F$, and $\|G_k\|_F$ with their upper bounds we obtain that $$\begin{split}
    \|\hat{H}_{k+1} - I\|_F & \leq \|D_k\|_F + \|E_k\|_F + 2\|F_k\|_F + \|G_k\|_F\\
    & \leq \|\hat{H}_k - I\|_F - \frac{\|(\hat{H}_k - I)\hat{y}_k\|^2}{2\delta\|\hat{y}_k\|^2} + V_k\tau_{k},
\end{split}$$ where $V_k = \||\hat{H}_k\|\frac{4}{1 - \tau_k} + \|\hat{H}_k\|\frac{4(1 + \tau_k)^2\tau_k}{(1 - \tau_k)^2} + \frac{3 + 2\tau_k}{1 - \tau_k}$. Hence, the claim holds and the proof is complete.

Linear convergence {#sec:main_result_linear_convergence}
------------------

In this section, we leverage the results from the previous section on the error of Hessian and Hessian inverse approximation for DFP and BFGS methods, respectively, to show that if the initial point is sufficiently close to the optimal solution and the initial Hessian approximation matrix is close enough to the Hessian at the optimal solution, then the iterates converge at least linearly to the optimal solution. Moreover, the Hessian approximation matrices always stay close to the Hessian at the optimal solution and the norms of Hessian approximation matrix and its inverse are always bounded above. These results are essential in proving non-asymptotic superlinear convergence rate of the considered quasi-Newton methods.

We first state our result for the DFP method.

\[lemma:lemma\_7\] Consider the DFP method described in Algorithm \[algo\_DFP\], and recall the definitions in -. Suppose the objective function $f$ satisfies the conditions in Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\]. Moreover, suppose the initial point $x_0$ and initial Hessian approximation matrix $B_0$ satisfy $$\label{lemma_7_neighbor}
    \sigma_0 \leq \epsilon, \qquad \|\hat{B}_0 - I\|_F \leq \delta,$$ where $\epsilon$ and $\delta$ are positive constants such that for some $r \in (0, 1)$ they satisfy $$\label{lemma_7_condition}
\left[(2\delta + 1)\frac{4}{(1 - \epsilon)^2} + \frac{3 + \epsilon}{1 - \epsilon}\right]\frac{\epsilon}{1 - r} \leq \delta, \qquad \epsilon + 2\delta \leq \frac{r}{1 + r} \ .$$ Then, the sequence of iterates $\{x_k\}_{k=0}^{+\infty}$ converges to the optimal solution $x_*$ with $$\label{lemma_7_conclusion_1}
\sigma_{k+1} \leq r\sigma_k \qquad \forall k \geq 0.$$ Furthermore, the matrices $\{B_k\}_{k=1}^{+\infty}$ stay in a neighborhood of $\nabla^{2}{f(x_*)}$ defined as $$\label{lemma_7_conclusion_2}
\|\hat{B}_{k+1} - I\|_F \leq 2\delta \qquad \forall k \geq 0.$$ Moreover, the norms $\{\|\hat{B}_k\|\}_{k=0}^{+\infty}$ and $\{\|\hat{B}_k^{-1}\|\}_{k=0}^{+\infty}$ are all uniformly bounded above by $$\label{lemma_7_conclusion_3}
\|\hat{B}_k\| \leq 2\delta + 1, \qquad \|\hat{B}_k^{-1}\| \leq 1 + r \qquad \forall k \geq 0.$$

We will use induction to prove the results , and . First consider the case of $k = 0$. By condition we have that $$\label{lemma_7_inter_1}
    \|\hat{B}_0\| \leq \|\hat{B}_0 - I\| + \|I\| \leq  \|\hat{B}_0 - I\|_F + 1 \leq \delta + 1 \leq 2\delta + 1$$ Based on and , we can also show that $$\|\hat{B}_0 - I\| \leq \|\hat{B}_0 - I\|_F \leq \delta \leq 2\delta \leq \frac{r}{1 + r} < 1$$ Using this result and the result of Lemma \[lemma:lemma\_6\] we know that $\hat{B}_0^{-1}$ exists and $$\label{lemma_7_inter_2}
    \|\hat{B}_0^{-1}\| = \|(I + \hat{B}_0 - I)^{-1}\| \leq \frac{1}{1 - \|\hat{B}_0 - I\|} \leq \frac{1}{1 - \frac{r}{1 + r}} = 1 + r$$ The results in and show that the conditions in hold for $k=0$.

Next we use the conditions in Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\] as well as the definitions in - to write $$\begin{split}
    \sigma_1 & = \frac{M}{\mu^{\frac{3}{2}}}\|\nabla^{2}{f(x_*)}^{\frac{1}{2}}(x_1 - x_*)\|\\
    & = \frac{M}{\mu^{\frac{3}{2}}}\|\nabla^{2}{f(x_*)}^{\frac{1}{2}}(x_0 - B_0^{-1}\nabla{f(x_0)} - x_*)\|\\
    & = \frac{M}{\mu^{\frac{3}{2}}}\|-\nabla^{2}{f(x_*)}^{\frac{1}{2}}B_0^{-1}[\nabla{f(x_0)} - \nabla^2{f(x_*)}(x_0 - x_*) - (B_0 - \nabla^2{f(x_*)})(x_0 - x_*)]\|\\
    & = \frac{M}{\mu^{\frac{3}{2}}}\|-\hat{B}_0^{-1}[\nabla{\hat{f}(x_0)} - r_0 - (\hat{B}_0 - I)r_0]\|\\
    & \leq \frac{M}{\mu^{\frac{3}{2}}}\|\hat{B}_0^{-1}\|\left(\|\nabla{\hat{f}(x_0)} - r_0\| + \|\hat{B}_0 - I\|\|r_0\|\right)\\
\end{split}$$ Using in Lemma \[lemma:lemma\_3\] and the conditions in , and we have $$\sigma_1 \leq \frac{M}{\mu^{\frac{3}{2}}}\|\hat{B}_0^{-1}\|(\sigma_0\|r_0\| + \|\hat{B}_0 - I\|\|r_0\|) = \|\hat{B}_0^{-1}\|(\sigma_0 + \|\hat{B}_0 - I\|)\sigma_0 \leq  (1 + r)(\epsilon + 2\delta)\sigma_0 \leq r\sigma_0$$ This indicates that the condition in is valid for $k = 0$.

Moreover, since $\tau_0 = \max\{\sigma_0, \sigma_1\} = \sigma_0 \leq \epsilon < 1$ and $\|\hat{B}_0 - I\|_F \leq \delta$, by using Lemma \[lemma:lemma\_4\] we can show that $$\|\hat{B}_1 - I\|_F \leq \|\hat{B}_0 - I\|_{F} - \frac{\|(\hat{B}_0 - I)\hat{s}_0\|^2}{2\delta\|\hat{s}_0\|^2} + W_0\sigma_0 \leq  \|\hat{B}_0 - I\|_{F} + W_0\sigma_0,$$ where $W_0 = \|\hat{B}_0\|\frac{4}{1 - \sigma_0} + \|\hat{B}_0\|\frac{4\sigma_0}{(1 - \sigma_0)^2} + \frac{3 + \sigma_0}{1 - \sigma_0}$. Next, using , and we obtain that $$W_0\sigma_0 \leq \left[(2\delta + 1)\frac{4}{(1 - \epsilon)^2} + \frac{3 + \epsilon}{1 - \epsilon}\right]\epsilon \leq (1 - r)\delta \leq \delta,$$ and, therefore, $$\|\hat{B}_1 - I\|_F \leq \|\hat{B}_0 - I\|_{F} + W_0\sigma_0 \leq \delta + \delta = 2\delta.$$ Hence, the result in is also correct for $k = 0$. As a result, all conditions in , and hold for $k = 0$, and the base of induction is complete.

Now assume that the conditions in , and hold for all $k$ that $0 \leq k \leq t - 1$, where $t \geq 1$. Our goal is to show that these conditions are also satisfied for the case of $k = t$. To prove this claim, note that since the condition in holds for $k=t-1$ we have $$\label{lemma_7_inter_3}
    \|\hat{B}_t\| \leq \|\hat{B}_t - I\| + \|I\| \leq  \|\hat{B}_t - I\|_F + 1 \leq 2\delta + 1$$ Again by using for $k=t-1$ and the condition in we can write $$\|\hat{B}_t - I\| \leq \|\hat{B}_t - I\|_F \leq 2\delta \leq \frac{r}{1 + r} < 1$$ Also by using Lemma \[lemma:lemma\_6\], we know that $\hat{B}_t^{-1}$ exists and $$\label{lemma_7_inter_4}
    \|\hat{B}_t^{-1}\| = \|(I + \hat{B}_t - I)^{-1}\| \leq \frac{1}{1 - \|\hat{B}_t - I\|} \leq \frac{1}{1 - \frac{r}{1 + r}} = 1 + r$$ The results in and indicate that the condition in also holds for $k = t$.

Now notice that based on Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\] as well as the definitions in - we have $$\begin{split}
    \sigma_{t+1} & = \frac{M}{\mu^{\frac{3}{2}}}\|\nabla^{2}{f(x_*)}^{\frac{1}{2}}(x_{t+1} - x_*)\|\\
    & = \frac{M}{\mu^{\frac{3}{2}}}\|\nabla^{2}{f(x_*)}^{\frac{1}{2}}(x_t - B_t^{-1}\nabla{f(x_t)} - x_*)\|\\
    & = \frac{M}{\mu^{\frac{3}{2}}}\|-\nabla^{2}{f(x_*)}^{\frac{1}{2}}B_t^{-1}[\nabla{f(x_t)} - \nabla^2{f(x_*)}(x_t - x_*) - (B_t - \nabla^2{f(x_*)})(x_t - x_*)]\|\\
    & = \frac{M}{\mu^{\frac{3}{2}}}\|-\hat{B}_t^{-1}[\nabla{\hat{f}(x_t)} - r_t - (\hat{B}_t - I)r_t]\|\\
    & \leq \frac{M}{\mu^{\frac{3}{2}}}\|\hat{B}_t^{-1}\|\left(\|\nabla{\hat{f}(x_t)} - r_t\| + \|\hat{B}_t - I\|\|r_t\|\right)\\
\end{split}$$ By leveraging the conditions in and we obtain that $\sigma_t \leq \sigma_0 \leq \epsilon$ and $\|\hat{B}_t - I\| \leq 2\delta$. Moreover, considering the results in , and we can write $$\sigma_{t+1} \leq \frac{M}{\mu^{\frac{3}{2}}}\|\hat{B}_t^{-1}\|(\sigma_t\|r_t\| + \|\hat{B}_t - I\|\|r_t\|) = \|\hat{B}_t^{-1}\|(\sigma_t + \|\hat{B}_t - I\|)\sigma_t \leq  (1 + r)(\epsilon + 2\delta)\sigma_t \leq r\sigma_t$$ This indicates that result in is correct for $k = t$.

Now note that since holds for all $0\leq k \leq t$, we obtain that $\tau_k = \max\{\sigma_k, \sigma_{k + 1}\} = \sigma_k \leq \epsilon < 1$ for $0 \leq k \leq t$. Moreover, since the condition in holds for $0\leq k\leq t-1$ we know that $\|\hat{B}_k-I\|_F \leq 2\delta$ for $0 \leq k \leq t$. Hence, by using these results and the result of Lemma \[lemma:lemma\_4\] we can show that $$\label{lemma_7_inter_5}
    \|\hat{B}_{k+1} - I\|_F \leq \|\hat{B}_k - I\|_{F} - \frac{\|(\hat{B}_k - I)\hat{s}_k\|^2}{4\delta\|\hat{s}_k\|^2} + W_k\sigma_k \leq \|\hat{B}_k - I\|_{F} + W_k\sigma_k \qquad 0 \leq k \leq t,$$ where $W_k = \|\hat{B}_k\|\frac{4}{1 - \sigma_k} + \|\hat{B}_k\|\frac{4\sigma_k}{(1 - \sigma_k)^2} + \frac{3 + \sigma_k}{1 - \sigma_k}$. Since holds for $0 \leq k \leq t$, we know that $\sigma_k \leq \sigma_0 \leq \epsilon$. Using this result and the inequalities in and we obtain that $$W_k \leq (2\delta + 1)\frac{4}{(1 - \epsilon)^2} + \frac{3 + \epsilon}{1 - \epsilon} \qquad 0 \leq k \leq t.$$ Compute the sum from $k = 0$ to $t$ and use the conditions in and to obtain $$\sum_{k = 0}^{t}\sigma_k \leq \frac{\sigma_0}{1 - r} \leq \frac{\epsilon}{1 - r}$$ Hence, we have $$\sum_{k = 0}^{t}W_k\sigma_k \leq \left[(2\delta + 1)\frac{4}{(1 - \epsilon)^2} + \frac{3 + \epsilon}{1 - \epsilon}\right]\sum_{k = 0}^{t}\sigma_k \leq \left[(2\delta + 1)\frac{4}{(1 - \epsilon)^2} + \frac{3 + \epsilon}{1 - \epsilon}\right]\frac{\epsilon}{1 - r} \leq \delta,$$ where the last inequality holds due to the first inequality in . By leveraging this result, we can show that if we compute the sum of the terms in the left and right hand side of (\[lemma\_7\_inter\_5\]) from $k = 0$ to $t$ we obtain $$\|\hat{B}_{t + 1} - I\|_F  \leq  \sum_{k = 0}^{t}W_k\sigma_k + \|\hat{B}_0 - I\|_{F} \leq \delta + \delta = 2\delta,$$ which implies that (\[lemma\_7\_conclusion\_2\]) holds for $k = t$. Hence, the claims in , and all hold for $k = t$, and our induction step is complete.

In Lemma \[lemma:lemma\_7\] we showed that the iterates of DFP converge at least linearly to the optimal solution, the Hessian approximation error $\|\hat{B}_{k} - I\|_F $ stays bounded, and the norm of Hessian $\hat{B}_{k}$ and Hessian inverse $\hat{B}_{k}^{-1}$ approximations are both bounded above for all iterates $k\geq 0$. Next we state a similar result for the BFGS update.

\[lemma:lemma\_8\] Consider the BFGS method described in Algorithm \[algo\_BFGS\], and recall the definitions in -. Suppose the objective function $f$ satisfies the conditions in Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\]. Moreover, suppose the initial point $x_0$ and initial Hessian inverse approximation matrix $H_0$ satisfy $$\label{lemma_8_neighbor}
    \sigma_0 \leq \epsilon, \qquad \|\hat{H}_0 - I\|_F \leq \delta,$$ where $\epsilon$ and $\delta$ are positive constants such that for some $r \in (0, 1)$ they satisfy $$\label{lemma_8_condition}
\left[(2\delta + 1)\frac{4(1 + 2\epsilon^2 + \epsilon^3)}{(1 - \epsilon)^2} + \frac{3 + 2\epsilon}{1 - \epsilon}\right]\frac{\epsilon}{1 - r} \leq \delta, \qquad (2\delta + 1)\epsilon + 2\delta \leq r.$$ Then, the sequence of iterates $\{x_k\}_{k=0}^{+\infty}$ converges to the optimal solution $x_*$ with $$\label{lemma_8_conclusion_1}
\sigma_{k+1} \leq r\sigma_k \qquad \forall k \geq 0.$$ Furthermore, the matrices $\{H_k\}_{k=1}^{+\infty}$ stay in a neighborhood of $\nabla^{2}{f(x_*)}^{-1}$ defined as $$\label{lemma_8_conclusion_2}
\|\hat{H}_{k+1} - I\|_F \leq 2\delta \qquad \forall k \geq 0.$$ Moreover, the norms $\{\|\hat{H}_k\|\}_{k=0}^{+\infty}$ and $\{\|\hat{H}_k^{-1}\|\}_{k=0}^{+\infty}$ are all uniformly bounded above by $$\label{lemma_8_conclusion_3}
\|\hat{H}_k\| \leq 2\delta + 1, \qquad \|\hat{H}_k^{-1}\| \leq \frac{1}{1 - r} \qquad \forall k \geq 0.$$

We will use induction to prove the results (\[lemma\_8\_conclusion\_1\]), (\[lemma\_8\_conclusion\_2\]) and (\[lemma\_8\_conclusion\_3\]). First consider the case of $k = 0$. By condition (\[lemma\_8\_neighbor\]) we have that $$\label{lemma_8_inter_1}
    \|\hat{H}_0\| \leq \|\hat{H}_0 - I\| + \|I\| \leq  \|\hat{H}_0 - I\|_F + 1 \leq \delta + 1 \leq 2\delta + 1$$ Based on (\[lemma\_8\_condition\]) and (\[lemma\_8\_neighbor\]), we can also show that $$\|\hat{H}_0 - I\| \leq \|\hat{H}_0 - I\|_F \leq \delta \leq 2\delta \leq r < 1$$ Using this result and the result of lemma \[lemma:lemma\_6\] we know that $\hat{H}_0^{-1}$ exists and $$\label{lemma_8_inter_2}
    \|\hat{H}_0^{-1}\| = \|(I + \hat{H}_0 - I)^{-1}\| \leq \frac{1}{1 - \|\hat{H}_0 - I\|} \leq \frac{1}{1 - r}$$ The results in and show that the conditions in hold for $k=0$.

Next we use the conditions in Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\] as well as the definitions in - to write $$\begin{split}
    \sigma_1 & = \frac{M}{\mu^{\frac{3}{2}}}\|\nabla^{2}{f(x_*)}^{\frac{1}{2}}(x_1 - x_*)\|\\
    & = \frac{M}{\mu^{\frac{3}{2}}}\|\nabla^{2}{f(x_*)}^{\frac{1}{2}}(x_0 - H_0\nabla{f(x_0)} - x_*)\|\\
    & = \frac{M}{\mu^{\frac{3}{2}}}\|-\nabla^{2}{f(x_*)}^{\frac{1}{2}}H_0[\nabla{f(x_0)} - \nabla^2{f(x_*)}(x_0 - x_*)] + \nabla^{2}{f(x_*)}^{\frac{1}{2}}(I - H_0\nabla^2{f(x_*)})(x_0 - x_*)]\|\\
    & = \frac{M}{\mu^{\frac{3}{2}}}\|-\hat{H}_0(\nabla{\hat{f}(x_0)} - r_0) + (I - \hat{H}_0)r_0\|\\
    & \leq \frac{M}{\mu^{\frac{3}{2}}}\left(\|\hat{H}_0\|\|\nabla{\hat{f}(x_0)} - r_0\| + \|I - \hat{H}_0\|\|r_0\|\right)\\
\end{split}$$ Using in Lemma \[lemma:lemma\_3\] and the conditions in , and we have $$\sigma_1 \leq \frac{M}{\mu^{\frac{3}{2}}}[(2\delta + 1)\sigma_0\|r_0\| + \delta\|r_0\|] \leq [(2\delta + 1)\epsilon + 2\delta]\sigma_0 \leq r\sigma_0$$ This indicates that the condition in is valid for $k = 0$.

Moreover, since $\tau_0 = \max\{\sigma_0, \sigma_1\} = \sigma_0 \leq \epsilon < 1$ and $\|\hat{H}_0 - I\|_F \leq \delta$, by using Lemma \[lemma:lemma\_5\] we can show that $$\|\hat{H}_1 - I\|_F \leq \|\hat{H}_0 - I\|_{F} - \frac{\|(\hat{H}_0 - I)\hat{y}_0\|^2}{2\delta\|\hat{y}_0\|^2} + V_0\sigma_0 \leq  \|\hat{H}_0 - I\|_{F} + V_0\sigma_0$$ Where $V_0 = \||\hat{H}_0\|\frac{4}{1 - \sigma_0} + \|\hat{H}_0\|\frac{4(1 + \sigma_0)^2\sigma_0}{(1 - \sigma_0)^2} + \frac{3 + 2\sigma_0}{1 - \sigma_0}$. Next using (\[lemma\_8\_condition\]), (\[lemma\_8\_neighbor\]) and (\[lemma\_8\_inter\_1\]) we obtain that $$V_0\sigma_0 \leq \left[(2\delta + 1)\frac{4(1 + 2\epsilon^2 + \epsilon^3)}{(1 - \epsilon)^2} + \frac{3 + 2\epsilon}{1 - \epsilon}\right]\epsilon \leq (1 - r)\delta \leq \delta$$ and, therefor, $$\|\hat{H}_1 - I\|_F \leq \|\hat{H}_0 - I\|_{F} + V_0\sigma_0 \leq \delta + \delta = 2\delta$$ Hence, the result in is also correct for $k = 0$. As a result, all conditions in , and hold for $k = 0$, and the base of induction is complete.

Now assume that the conditions in , and hold for all $k$ that $0 \leq k \leq t - 1$, where $t \geq 1$. Our goal is to show that these conditions are also satisfied for the case of $k = t$. To prove this claim, note that since the condition in holds for $k=t-1$ we have $$\label{lemma_8_inter_3}
    \|\hat{H}_t\| \leq \|\hat{H}_t - I\| + \|I\| \leq  \|\hat{H}_t - I\|_F + 1 \leq 2\delta + 1$$ Again by using for $k=t-1$ and the condition in we can write $$\|\hat{H}_t - I\| \leq \|\hat{H}_t - I\|_F \leq 2\delta \leq r < 1$$ Also by using Lemma \[lemma:lemma\_6\], we know that $\hat{H}_t^{-1}$ exists and $$\label{lemma_8_inter_4}
    \|\hat{H}_t^{-1}\| = \|(I + \hat{H}_t - I)^{-1}\| \leq \frac{1}{1 - \|\hat{H}_t - I\|} \leq \frac{1}{1 - r}$$ The results in and indicate that the condition in also holds for $k = t$.

Now notice that based on Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\] as well as the definitions in - we have $$\begin{split}
    \sigma_{t+1} & = \frac{M}{\mu^{\frac{3}{2}}}\|\nabla^{2}{f(x_*)}^{\frac{1}{2}}(x_t - x_*)\|\\
    & = \frac{M}{\mu^{\frac{3}{2}}}\|\nabla^{2}{f(x_*)}^{\frac{1}{2}}(x_t - H_t\nabla{f(x_t)} - x_*)\|\\
    & = \frac{M}{\mu^{\frac{3}{2}}}\|-\nabla^{2}{f(x_*)}^{\frac{1}{2}}H_t[\nabla{f(x_t)} - \nabla^2{f(x_*)}(x_t - x_*)] + \nabla^{2}{f(x_*)}^{\frac{1}{2}}(I - H_t\nabla^2{f(x_*)})(x_t - x_*)]\|\\
    & = \frac{M}{\mu^{\frac{3}{2}}}\|-\hat{H}_t(\nabla{\hat{f}(x_t)} - r_t) + (I - \hat{H}_t)r_t\|\\
    & \leq \frac{M}{\mu^{\frac{3}{2}}}\left(\|\hat{H}_t\|\|\nabla{\hat{f}(x_t)} - r_t\| + \|I - \hat{H}_t\|\|r_t\|\right)\\
\end{split}$$ By leveraging the conditions in and we obtain that $\sigma_t \leq \sigma_0 \leq \epsilon$ and $\|\hat{H}_t - I\| \leq 2\delta$. Moreover, considering the results in and we can write $$\sigma_{t+1} \leq \frac{M}{\mu^{\frac{3}{2}}}[(2\delta + 1)\sigma_t\|r_t\| + 2\delta\|r_t\|] \leq [(2\delta + 1)\epsilon + 2\delta]\sigma_t \leq r\sigma_t,$$ where the last inequality holds due to the second condition in . This result indicates that result in (\[lemma\_8\_conclusion\_1\]) is correct for $k = t$.

Now note that since holds for all $0\leq k \leq t$, we obtain that $\tau_k = \max\{\sigma_k, \sigma_{k + 1}\} = \sigma_k \leq \epsilon < 1$ for $0 \leq k \leq t$. Moreover, since the condition in holds for $0\leq k\leq t-1$ we know that $\|\hat{H}_k-I\|_F \leq 2\delta$ for $0 \leq k \leq t$. Hence, by using these results and the result of Lemma \[lemma:lemma\_5\] we can show that $$\label{lemma_8_inter_5}
    \|\hat{H}_{k+1} - I\|_F \leq \|\hat{H}_k - I\|_{F} - \frac{\|(\hat{H}_k - I)\hat{y}_k\|^2}{4\delta\|\hat{y}_k\|^2} + V_k\sigma_k \leq \|\hat{H}_k - I\|_{F} + V_k\sigma_k \qquad 0 \leq k \leq t$$ Where $V_k = \||\hat{H}_k\|\frac{4}{1 - \sigma_k} + \|\hat{H}_k\|\frac{4(1 + \sigma_k)^2\sigma_k}{(1 - \sigma_k)^2} + \frac{3 + 2\sigma_k}{1 - \sigma_k}$. Since holds for $0 \leq k \leq t$, we know that $\sigma_k \leq \sigma_0 \leq \epsilon$. Using this result and the inequalities in and we obtain that $$V_k \leq (2\delta + 1)\frac{4(1 + 2\epsilon^2 + \epsilon^3)}{(1 - \epsilon)^2} + \frac{3 + 2\epsilon}{1 - \epsilon} \qquad 0 \leq k \leq t$$ Compute the sum from $k = 0$ to $t$ and use the conditions in and to obtain $$\sum_{k = 0}^{t}\sigma_k \leq \frac{\sigma_0}{1 - r} \leq \frac{\epsilon}{1 - r}$$ Hence, we have $$\begin{aligned}
\sum_{k = 0}^{t}V_k\sigma_k 
&\leq \left[(2\delta + 1)\frac{4(1 + 2\epsilon^2 + \epsilon^3)}{(1 - \epsilon)^2} + \frac{3 + 2\epsilon}{1 - \epsilon}\right]\sum_{k = 0}^{t}\sigma_k \\
&\leq \left[(2\delta + 1)\frac{4(1 + 2\epsilon^2 + \epsilon^3)}{(1 - \epsilon)^2} + \frac{3 + 2\epsilon}{1 - \epsilon}\right]\frac{\epsilon}{1 - r} \\
&\leq \delta\end{aligned}$$ where the last inequality holds due to the first inequality in . By leveraging this result, we can show that if we compute the sum of the terms in the left and right hand side of (\[lemma\_8\_inter\_5\]) from $k = 0$ to $t$ we obtain $$\|\hat{H}_{t + 1} - I\|_F \leq  \sum_{k = 0}^{t}V_k\sigma_k + \|\hat{H}_0 - I\|_{F} \leq \delta + \delta = 2\delta$$ which implies that (\[lemma\_8\_conclusion\_2\]) holds for $k = t$. Hence, the claims in , and all hold for $k = t$, and our induction step is complete.

Explicit non-asymptotic superlinear rate of DFP {#sec:main_result_superlinear_convergence}
-----------------------------------------------

In the previous section, we established local linear convergence of iterates generated by DFP and BFGS. Indeed, these local linear results are not our ultimate goal, as first-order methods are also linearly convergent under the same assumptions. However, the linear convergence of these two algorithms are required to establish their local non-asymptotic superlinear convergence rate.

Next, we state the main results of this paper on the non-asymptotic superlinear convergence rate of the DFP method. To prove this claim we use the result in Lemma \[lemma:lemma\_7\].

\[thm\_DFP\] Consider the DFP method described in Algorithm \[algo\_DFP\]. Suppose the objective function $f$ satisfies the conditions in Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\]. Moreover, suppose the initial point $x_0$ and initial Hessian approximation matrix $B_0$ satisfy $$\label{thm_DFP_neighbor}
    \|x_0 - x_*\| \leq \frac{\mu^{\frac{3}{2}}}{M\sqrt{L}}\epsilon, \qquad \|{\nabla^{2}f(x_*)^{-\frac{1}{2}}}\ \! B_0\ \!{\nabla^{2}f(x_*)^{-\frac{1}{2}}} - I\|_F \leq \delta,$$ where $\epsilon$ and $\delta$ are positive constants such that for some $r \in (0, 1)$ they satisfy $$\label{thm_DFP_condition}
\left[\frac{4(2\delta + 1)}{(1 - \epsilon)^2} + \frac{3 + \epsilon}{1 - \epsilon}\right]\frac{\epsilon}{1 - r} \leq \delta, \qquad \epsilon + 2\delta \leq \frac{r}{1 + r} \ .$$ Then, the iterates $\{x_{k}\}_{k=0}^{+\infty}$ generated by DFP converge to $x_*$ at a superlinear rate of $$\label{thm_DFP_rate}
\|x_k - x_0\| \leq \sqrt{\frac{L}{\mu}}\left(\frac{2\sqrt{2}\delta\frac{1 + r}{1 - \epsilon}\sqrt{k} + \frac{(1 + r)\epsilon}{(1 - r)(1 - \epsilon)}}{k}\right)^k\|x_0 - x_*\|, \qquad \forall k \geq 1.$$

When conditions and are both satisfied, by assumption \[ass\_str\_cvx\_smooth\] we have that $$\sigma_0 = \frac{M}{\mu^{\frac{3}{2}}}\|\nabla^{2}f(x_*)^{\frac{1}{2}}(x_0 - x_*)\| \leq \frac{M}{\mu^{\frac{3}{2}}}\|\nabla^{2}f(x_*)^{\frac{1}{2}}\|\|x_0 - x_*\| \leq \frac{M\sqrt{L}}{\mu^{\frac{3}{2}}}\|x_0 - x_*\| \leq \epsilon,$$ $$\|\hat{B}_0 - I\|_F = \|{\nabla^{2}f(x_*)^{-\frac{1}{2}}}B_0{\nabla^{2}f(x_*)^{-\frac{1}{2}}} - I\|_F \leq \delta.$$ Using Lemma \[lemma:lemma\_7\], the results in , and hold. This indicates for any $t \geq 0$ we have $$\tau_t = \max\{\sigma_t, \sigma_{t+1}\} = \sigma_t \leq \sigma_0 \leq \epsilon < 1,\qquad
\|\hat{B}_t - I\|_F \leq 2\delta.$$ Hence, using Lemma \[lemma:lemma\_4\] we can obtain that $$\label{proof_thm_DFP_inter_1}
    \|\hat{B}_{t+1} - I\|_F \leq \|\hat{B}_t - I\|_{F} - \frac{\|(\hat{B}_t - I)\hat{s}_t\|^2}{4\delta\|\hat{s}_t\|^2} + W_t\sigma_t \qquad \forall t \geq 0,$$ where $W_t = \|\hat{B}_t\|\frac{4}{1 - \sigma_t} + \|\hat{B}_t\|\frac{4\sigma_t}{(1 - \sigma_t)^2} + \frac{3 + \sigma_t}{1 - \sigma_t}$. Using the inequality in and the fact that $\sigma_t \leq \epsilon$, we have $$\begin{aligned}
\label{eq:bound_on_w_k}
W_t \leq \frac{4(2\delta + 1)}{(1 - \epsilon)^2} + \frac{3 + \epsilon}{1 - \epsilon} \qquad \forall t \geq 0.\end{aligned}$$ Therefore, using this result and the fact that $\sigma_t \leq r\sigma_{t-1}$ we can show that for any $k \geq 1$ $$\begin{aligned}
\label{eq:bound_on_sum_w_k_sigma_k}
\sum_{t = 0}^{k - 1}W_t\sigma_t 
&\leq \left[\frac{4(2\delta + 1)}{(1 - \epsilon)^2} + \frac{3 + \epsilon}{1 - \epsilon}\right]\sum_{t = 0}^{k - 1}\sigma_t \nonumber\\
&\leq  \left[\frac{4(2\delta + 1)}{(1 - \epsilon)^2} + \frac{3 + \epsilon}{1 - \epsilon}\right]  \frac{\epsilon}{1-r}   \nonumber\\
&\leq \delta,\end{aligned}$$ where the first inequality holds due to , the second inequality holds since $
    \sum_{t = 0}^{k - 1}\sigma_t \leq \frac{\sigma_0}{1 - r} \leq \frac{\epsilon}{1 - r}
$, and the last inequality follows from the first condition in .

Now compute the sum of both sides of from $t = 0$ to $k - 1$ to obtain $$\|\hat{B}_k - I\|_F \leq \|\hat{B}_0 - I\|_F - \sum_{t = 0}^{k - 1}\frac{\|(\hat{B}_t - I)\hat{s}_t\|^2}{4\delta\|\hat{s}_t\|^2} + \sum_{t = 0}^{k - 1}W_t\sigma_t.$$ Regroup the terms and use the result in to show that $$\begin{aligned}
\sum_{t = 0}^{k - 1}\frac{\|(\hat{B}_t - I)\hat{s}_t\|^2}{4\delta\|\hat{s}_t\|^2} 
&\leq \|\hat{B}_0 - I\|_F - \|\hat{B}_k - I\|_F + \sum_{t = 0}^{k - 1}W_t\sigma_t \nonumber\\
&\leq \|\hat{B}_0 - I\|_F + \sum_{t = 0}^{k - 1}W_t\sigma_t\nonumber\\
& \leq \delta + \delta = 2\delta,\end{aligned}$$ which leads to $$\sum_{t = 0}^{k - 1}\frac{\|(\hat{B}_t - I)\hat{s}_t\|^2}{\|\hat{s}_t\|^2} \leq 8\delta^2.$$ By Cauchy-Schwarz inequality we have that $$\label{proof_thm_DFP_inter_2}
    \sum_{t = 0}^{k - 1}\frac{\|(\hat{B}_t - I)\hat{s}_t\|}{\|\hat{s}_t\|} \leq 2\sqrt{2}\delta\sqrt{k}.$$ This result provides an upper bound for the sum $\sum_{t = 0}^{k - 1}\frac{\|(\hat{B}_t - I)\hat{s}_t\|}{\|\hat{s}_t\|} $ which is a crucial element in the remaining of the proof. Next we proceed to characterize the relationship between the convergence rate of DFP and the expression $\sum_{t = 0}^{k - 1}\frac{\|(\hat{B}_t - I)\hat{s}_t\|}{\|\hat{s}_t\|} $.

To do so, note that $x_{t + 1} = x_t - B_t^{-1}\nabla{f(x_t)}$ and this is equivalent to $\nabla{f(x_t)} = -B_t s_t$. So $\nabla{f(x_{t+1})}$ can be written as $$\nabla{f(x_{t+1})} = y_t + \nabla{f(x_t)} = y_t - B_ts_t = y_t - \nabla^2{f(x_*)}s_t - (B_t - \nabla^2{f(x_*)})s_t.$$ Premultiply both sides by $\nabla{f(x_*)}^{-\frac{1}{2}}$ to obtain $
\nabla{\hat{f}(x_{t+1})} = \hat{y}_t - \hat{s}_t - (\hat{B}_t - I)\hat{s}_t
$. Next, by using triangle inequality we have $$\|\nabla{\hat{f}(x_{t+1})}\| \leq \|\hat{y}_t - \hat{s}_t\| + \|(\hat{B}_t - I)\hat{s}_t\|.$$ Using this result and the one in we can show that $$\label{eq:bound_on_grad_over_s}
\frac{\|\nabla{\hat{f}(x_{t+1})}\|}{\|\hat{s}_t\|} \leq \frac{\|\hat{y}_t - \hat{s}_t\|}{\|\hat{s}_t\|} + \frac{\|(\hat{B}_t - I)\hat{s}_t\|}{\|\hat{s}_t\|} \leq \sigma_t + \frac{\|(\hat{B}_t - I)\hat{s}_t\|}{\|\hat{s}_t\|}.$$ On the other hand, by triangle inequality, the inequality in , and $\sigma_{t+1}\leq \epsilon$ we can write $$\|\nabla{\hat{f}(x_{t+1})}\| \geq  \|r_{t+1}\| - \|\nabla{\hat{f}(x_{t+1})} - r_{t+1}\| \geq  (1 - \sigma_{t+1})\|r_{t+1}\| \geq  (1 - \epsilon)\|r_{t+1}\|,$$ which implies that $$\label{eq:bound_on_r_k+1_norm}
\|r_{t+1}\| \leq \frac{\|\nabla{\hat{f}(x_{t+1})}\| }{1 - \epsilon}.$$ Also, since $\sigma_{t+1} \leq r\sigma_t$ and $\sigma_t = \frac{M}{\mu^{\frac{3}{2}}}\|r_t\|$ we obtain that $\|r_{t+1}\| \leq r\|r_t\|$. Hence, we can write $$\|\hat{s}_t\| = \|\nabla{f(x_*)}^{\frac{1}{2}}(x_{t+1} - x_* + x_* - x_t)\| \leq \|r_{t+1}\| + \|r_t\| \leq (1 + r)\|r_t\|,$$ which implies that $$\label{eq:bound_on_r_k_norm}
\|r_{t}\| \geq \frac{\|\hat{s}_t\| }{(1 + r)}.$$ Using the expressions in and , we can show that the rate of convergence $\frac{\|r_{t+1}\|}{\|r_t\|}$ is bounded above by $$\label{eq:bound_on_rate_of_convg}
\frac{\|r_{t+1}\|}{\|r_t\|} \leq \frac{\frac{1}{1 - \epsilon}\|\nabla{\hat{f}(x_{t+1})}\|}{\frac{1}{1 + r}\|\hat{s}_t\|} \leq \frac{1 + r}{1 - \epsilon}\left(\sigma_t + \frac{\|(\hat{B}_t - I)\hat{s}_t\|}{\|\hat{s}_t\|}\right),$$ where the second inequality is valid due to the result in . Compute the sum of both sides of from $t = 0$ to $k - 1$ and use the result in to obtain $$\sum_{t=0}^{k-1}\frac{\|r_{t+1}\|}{\|r_t\|} \leq \frac{1 + r}{1 - \epsilon}\left(\sum_{t=0}^{k-1}\sigma_t + \sum_{t=0}^{k-1}\frac{\|(\hat{B}_t - I)\hat{s}_t\|}{\|\hat{s}_t\|}\right) \leq \frac{1 + r}{1 - \epsilon}(\frac{\epsilon}{1 - r} + 2\sqrt{2}\delta\sqrt{k}).$$ By leveraging the Arithmetic Geometric inequality we get that $$\label{DFP_temp_result}
    \frac{\|r_k\|}{\|r_0\|} = \prod_{t=0}^{k-1}\frac{\|r_{t+1}\|}{\|r_t\|} \leq \left(\frac{\sum_{t=0}^{k-1}\frac{\|r_{t+1}\|}{\|r_t\|}}{k}\right)^k \leq \left(\frac{2\sqrt{2}\delta\frac{1 + r}{1 - \epsilon}\sqrt{k} + \frac{(1 + r)\epsilon}{(1 - r)(1 - \epsilon)}}{k}\right)^k,$$ by assumption \[ass\_str\_cvx\_smooth\] we have $$\begin{aligned}
\label{relationship}
    & \|x_k - x_*\| = \|\nabla^{2}f(x_*)^{-\frac{1}{2}}\nabla^{2}f(x_*)^\frac{1}{2}(x_k - x_*)\| \leq \|\nabla^{2}f(x_*)^{-\frac{1}{2}}\|\|\nabla^{2}f(x_*)^\frac{1}{2}(x_k - x_*)\| \leq  \frac{1}{\sqrt{\mu}}\|r_k\|,\nonumber\\
    & \|r_0\| = \|\nabla^{2}f(x_*)^\frac{1}{2}(x_0 - x_*)\| \leq \|\nabla^{2}f(x_*)^\frac{1}{2}\|\|x_0 - x_*\| \leq \sqrt{L}\|x_0 - x_*\|,\nonumber\\
    & \frac{1}{\|x_0 - x_*\|} \leq \sqrt{L}\frac{1}{\|r_0\|}.\end{aligned}$$ Using this and (\[DFP\_temp\_result\]) we obtain that $$\frac{\|x_k - x_*\|}{\|x_0 - x_*\|} \leq \sqrt{\frac{L}{\mu}}\frac{\|r_k\|}{\|r_0\|} \leq \sqrt{\frac{L}{\mu}}\left(\frac{2\sqrt{2}\delta\frac{1 + r}{1 - \epsilon}\sqrt{k} + \frac{(1 + r)\epsilon}{(1 - r)(1 - \epsilon)}}{k}\right)^k, \qquad \forall k \geq 1,$$ and the proof is complete.

The result in Theorem \[thm\_DFP\] indicates that in a local neighborhood of the optimal solution the sequence of iterates generated by DFP converges to the optimal solution at a superlinear rate of $(\frac{C_1\sqrt{k}+C_2}{k})^k$, where the constants $C_1$ and $C_2$ are determined by $r, \epsilon, \delta \in (0, 1)$. Indeed, as time progresses then the rate behaves as $(\frac{\mathcal{O}(1)}{{k}})^{\frac{k}{2}}$. Note that the tuple $(r, \epsilon, \delta)$ is independent of the problem parameters $(\mu, L, M, d)$, and the only required condition for the tuple $(r, \epsilon, \delta)$ is that they should satisfy the conditions in . Note that the superlinear rate in is significantly faster than the linear rate of first-order methods as the contraction coefficient also approaches zero at a sublinear rate of $\mathcal{O}(\frac{1}{k})$.

Another important outcome of the result in Theorem \[thm\_DFP\] is the existence of a trade-off between the *rate of convergence* and the *neighborhood of superlinear convergence*. We highlight this point in the following remark.

There exists a trade-off between the size of the local neighborhood in which DFP converges superlinearly and the rate of convergence. To be more precise, by choosing larger values for $\epsilon$ and $\delta$ (as long as they satisfy the conditions in ) we can increase the size of the region in which DFP has a fast superlinear convergence rate, but on the other hand it will lead to a slower superlinear convergence rate according to the result in . Conversely, by choosing small values for $\epsilon$ and $\delta$, the rate of convergence becomes faster, but the local neighborhood defined in becomes smaller. In Corollary \[cor\_DFP\], we report the result for a specific choices of $r$, $\epsilon$ and $\delta$, but indeed one can adjust these parameters to control the neighborhood and rate of superlinear convergence.

The final result of Theorem \[thm\_DFP\] in depends on the choice of parameters $(r, \epsilon, \delta)$, and it may not be easy to quantify the exact convergence rate at first glance. To better quantify the superlinear convergence rate of DFP, in the following corollary we state the result of Theorem \[thm\_DFP\] for specific choices of $r$, $\epsilon$, and $\delta$.

\[cor\_DFP\] Consider the DFP method described in Algorithm \[algo\_DFP\]. Suppose the objective function $f$ satisfies the conditions in Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\]. Moreover, suppose the initial point $x_0$ and initial Hessian approximation matrix $B_0$ satisfy $$\label{cor_DFP_neighbor_1}
\|x_0 - x_*\| \leq \frac{\mu^{\frac{3}{2}}}{200M\sqrt{L}}, \qquad 
\|\nabla^{2}f(x_*)^{-\frac{1}{2}}B_0\nabla^{2}f(x_*)^{-\frac{1}{2}} - I\|_F \leq \frac{1}{12}.$$ Then, for $k\geq 1$, the iterates $\{x_k\}_{k=0}^{+\infty}$ generated by DFP satisfy $$\label{cor_DFP_rate}
\|x_k - x_*\| \leq \sqrt{\frac{L}{\mu}}\left(\frac{1}{k}\right)^{\frac{k}{2}}\|x_0 - x_*\| .$$

This results can be shown by setting $r = \frac{1}{2}$, $\epsilon = \frac{1}{200}$ and $\delta = \frac{1}{12}$ in Theorem \[thm\_DFP\]. Notice that for these choices of $(r, \epsilon, \delta)$ the conditions in are all satisfied since $$\left[\frac{4(2\delta + 1)}{(1 - \epsilon)^2} + \frac{3 + \epsilon}{1 - \epsilon}\right]\frac{\epsilon}{1 - r} < \frac{1}{12} = \delta, \qquad 
\epsilon + 2\delta = \frac{1}{200} + \frac{1}{6} < \frac{1}{3} = \frac{r}{1 + r}.$$ Moreover, the expression in can be simplified as $$\begin{aligned}
\frac{2\sqrt{2}\delta\frac{1 + r}{1 - \epsilon}\sqrt{k} + \frac{(1 + r)\epsilon}{(1 - r)(1 - \epsilon)}}{k}
&=\frac{\frac{2\sqrt{2}(1 + \frac{1}{2})}{12(1 - \frac{1}{200})} \sqrt{k} + \frac{(1 + \frac{1}{2})\frac{1}{200}}{(1 - \frac{1}{2})(1 - \frac{1}{200})} }{k}
< \frac{\frac{1}{2} \sqrt{k} + \frac{1}{2} }{k}
\leq \frac{1 }{\sqrt{k}}\ ,\end{aligned}$$ and the claim in follows.

The result in Corollary \[cor\_DFP\] shows that for some specific choices of $\epsilon$, $\delta$ and $r$, the convergence rate of DFP is $\left(1/k\right)^{k/2}$, which is significantly faster than any linear convergence rate for first-order methods. However one major shortcoming of the results in Theorem \[thm\_DFP\] and Corollary \[cor\_DFP\] is that in both results in addition to assuming that the initial iterate $x_0$ is sufficiently close to the optimal solution, we also require the initial Hessian approximation error to be sufficiently small. In the following theorem, we resolve this issue by suggesting a practical choice for $B_0$ such that the second condition in can be satisfied under some conditions. To be more precise, we show that if $\|x_0 - x_*\|$ is sufficiently small (we formally describe this condition), then by setting $B_0 = \nabla^{2}{f(x_0)}$ the second condition in for Hessian approximation is always satisfied. So we can achieve the convergence rate of .

\[thm\_DFP\_Hessian\] Consider the DFP method described in Algorithm \[algo\_DFP\]. Suppose the objective function $f$ satisfies the conditions in Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\]. If the initial point $x_0$ and initial Hessian approximation matrix $B_0$ satisfy $$\label{thm_DFP_Hessian_neighbor}
    \|x_0 - x_*\| \leq \min\left\{\frac{\mu^\frac{3}{2}\epsilon}{M\sqrt{L}}, \frac{\mu\delta}{M\sqrt{d}}\right\}, \qquad B_0 = \nabla^{2}{f(x_0)},$$ where $\epsilon$ and $\delta$ are positive constants such that for some $r \in (0, 1)$ they satisfy $$\label{thm_DFP_condition_22}
\left[\frac{4(2\delta + 1)}{(1 - \epsilon)^2} + \frac{3 + \epsilon}{1 - \epsilon}\right]\frac{\epsilon}{1 - r} \leq \delta, \qquad \epsilon + 2\delta \leq \frac{r}{1 + r} \ .$$ then iterates $\{x_{k}\}_{k=0}^{+\infty}$ generated by DFP converge to the optimal solution $x_*$ at the rate of $$\|x_k - x_*\| \leq \sqrt{\frac{L}{\mu}}\left(\frac{2\sqrt{2}\delta\frac{1 + r}{1 - \epsilon}\sqrt{k} + \frac{(1 + r)\epsilon}{(1 - r)(1 - \epsilon)}}{k}\right)^k\|x_0 - x_*\|, \qquad \forall k \geq 1.$$

Notice that by (\[thm\_DFP\_Hessian\_neighbor\]) we obtain $$\|x_0 - x_*\| \leq \frac{\mu^{\frac{3}{2}}}{M\sqrt{L}}\epsilon.$$ So first part of conditions (\[thm\_DFP\_neighbor\]) is satisfied. Using assumption \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\] we have $$\begin{split}
    \|\nabla^{2}f(x_*)^{-\frac{1}{2}}B_0\nabla^{2}f(x_*)^{-\frac{1}{2}} - I\|_F & = \|\nabla^{2}f(x_*)^{-\frac{1}{2}}(\nabla^{2}f(x_0) - \nabla^{2}f(x_*))\nabla^{2}f(x_*)^{-\frac{1}{2}}\|_F\\
    & \leq \sqrt{d}\|\nabla^{2}f(x_*)^{-\frac{1}{2}}(\nabla^{2}f(x_0) - \nabla^{2}f(x_*))\nabla^{2}f(x_*)^{-\frac{1}{2}}\|\\
    & \leq \sqrt{d}\|\nabla^{2}f(x_*)^{-\frac{1}{2}}\|^2\|\nabla^{2}f(x_0) - \nabla^{2}f(x_*)\|\\
    & \leq \sqrt{d}\frac{1}{\mu}\|\nabla^{2}f(x_0) - \nabla^{2}f(x_*)\|\\
    & \leq \sqrt{d}\frac{M}{\mu}\|x_0 - x_*\|\\
    & \leq \delta.
\end{split}$$ The first inequality is because of the fact that $\|A\|_F \leq \sqrt{d}\|A\|$ for any matrix $A \in \mathbb{R}^{d \times d}$. The last inequality is due to condition (\[thm\_DFP\_Hessian\_neighbor\]). Hence second part of conditions (\[thm\_DFP\_neighbor\]) is also satisfied. By theorem \[thm\_DFP\] we prove the conclusion.

Based on Theorem \[thm\_DFP\_Hessian\], when the initial error $\|x_0 - x_*\| = \mathcal{O}(\min\{\frac{\mu^\frac{3}{2}}{M\sqrt{L}}, \frac{\mu}{M\sqrt{d}}\})$ and the initial Hessian approximation $B_0=\nabla^2 f(x_0)$ we obtain a convergence rate of $\frac{\|x_k - x_*\|}{\|x_0 - x_*\|} \leq \sqrt{\frac{L}{\mu}}(\frac{\mathcal{O}(1)}{k})^\frac{k}{2}$ for the DFP method.

In practice, we can use the fact that $\|x_0 - x_*\| \leq \frac{1}{\mu}\|\nabla{f(x_0)}\|$ to check if $\|x_0 - x_*\|$ is sufficiently small. We can use any optimization method to find $x_0$ satisfying the condition $\|\nabla{f(x_0)}\| = \mathcal{O}(\min\{\frac{\mu^\frac{5}{2}}{M\sqrt{L}}, \frac{\mu^2}{M\sqrt{d}}\})$. Then we can ensure that the condition $\|x_0 - x_*\| = \mathcal{O}(\min\{\frac{\mu^\frac{3}{2}}{M\sqrt{L}}, \frac{\mu}{M\sqrt{d}}\})$ holds. When this condition is satisfied, then by choosing $B_0=\nabla^2 f(x_0)$, we obtain the guaranteed superlinear convergence result. We should also mention that the suggested procedure requires evaluation of the inverse Hessian only for the initial iterate and in the rest of the algorithm the Hessian approximations (and their inverses) are updated according to the DFP update in .

Explicit non-asymptotic superlinear rate of BFGS
------------------------------------------------

We proceed to state the non-asymptotic superlinear convergence rate of the BFGS method. The results in this section are very similar to the ones in the previous section for the DFP method, but there are some minor differences on the required initial conditions. Also, the proof techniques for the BFGS method are almost identical to the ones for the DFP method, but for completeness we state all the proofs.

\[thm\_BFGS\] Consider the BFGS method described in Algorithm \[algo\_BFGS\]. Suppose the objective function $f$ satisfies the conditions in Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\]. Moreover, suppose the initial point $x_0$ and initial Hessian inverse approximation matrix $H_0$ satisfy $$\label{thm_BFGS_neighbor}
    \|x_0 - x_*\| \leq \frac{\mu^{\frac{3}{2}}}{M\sqrt{L}}\epsilon, \qquad \|\nabla^{2}f(x_*)^\frac{1}{2}H_0\nabla^{2}f(x_*)^\frac{1}{2} - I\|_F \leq \delta,$$ where $\epsilon$ and $\delta$ are positive constants such that for some $r \in (0, 1)$ they satisfy $$\label{thm_BFGS_condition}
\left[(2\delta + 1)\frac{4(1 + 2\epsilon^2 + \epsilon^3)}{(1 - \epsilon)^2} + \frac{3 + 2\epsilon}{1 - \epsilon}\right]\frac{\epsilon}{1 - r} \leq \delta, \qquad (2\delta + 1)\epsilon + 2\delta \leq r.$$ Then, the iterates $\{x_k\}_{k=0}^{+\infty}$ generated by BFGS converges to $x_*$ at a superlinear rate of $$\label{thm_BFGS_rate}
\|x_k - x_*\| \leq \sqrt{\frac{L}{\mu}}\left(\frac{2\sqrt{2}\delta\frac{(1 + \epsilon)(1 + r)}{(1 - \epsilon)(1 - r)}\sqrt{k} + \frac{(1 + \epsilon)\epsilon(1 + r)}{(1 - \epsilon)^2(1 - r)^2}}{k}\right)^k\|x_0 - x_*\|, \qquad \forall k \geq 1.$$

When conditions (\[thm\_BFGS\_neighbor\]) and (\[thm\_BFGS\_condition\]) are both satisfied, by assumption \[ass\_str\_cvx\_smooth\] we have that $$\sigma_0 = \frac{M}{\mu^{\frac{3}{2}}}\|\nabla^{2}f(x_*)^{\frac{1}{2}}(x_0 - x_*)\| \leq \frac{M}{\mu^{\frac{3}{2}}}\|\nabla^{2}f(x_*)^{\frac{1}{2}}\|\|x_0 - x_*\| \leq \frac{M\sqrt{L}}{\mu^{\frac{3}{2}}}\|x_0 - x_*\| \leq \epsilon,$$ $$\|\hat{H}_0 - I\|_F = \|{\nabla^{2}f(x_*)^\frac{1}{2}}H_0{\nabla^{2}f(x_*)^\frac{1}{2}} - I\|_F \leq \delta.$$ Using Lemma \[lemma:lemma\_8\], the results in , and hold. This indicates for any $t \geq 0$ we have $$\tau_t = \max\{\sigma_t, \sigma_{t+1}\} = \sigma_t \leq \sigma_0 \leq \epsilon < 1, \qquad
\|\hat{H}_t - I\|_F \leq 2\delta.$$ Hence, using Lemma \[lemma:lemma\_5\] we can obtain that $$\label{proof_thm_BFGS_inter_1}
    \|\hat{H}_{t+1} - I\|_F \leq \|\hat{H}_t - I\|_{F} - \frac{\|(\hat{H}_t - I)\hat{y}_t\|^2}{4\delta\|\hat{y}_t\|^2} + V_t\sigma_t, \qquad \forall t \geq 0,$$ where $V_t = \||\hat{H}_t\|\frac{4}{1 - \sigma_t} + \|\hat{H}_t\|\frac{4(1 + \sigma_t)^2\sigma_t}{(1 - \sigma_t)^2} + \frac{3 + 2\sigma_t}{1 - \sigma_t}$. Using inequality in (\[lemma\_8\_conclusion\_3\]) and the fact that $\sigma_t \leq \epsilon$, we have $$\begin{aligned}
\label{eq:bound_on_v_k}
V_t \leq (2\delta + 1)\frac{4(1 + 2\epsilon^2 + \epsilon^3)}{(1 - \epsilon)^2} + \frac{3 + 2\epsilon}{1 - \epsilon}, \qquad \forall t \geq 0.\end{aligned}$$ Therefore, using this result and the fact that $\sigma_t \leq r\sigma_{t-1}$ we can show that for any $k \geq 1$ $$\begin{aligned}
\label{eq:bound_on_sum_v_k_sigma_k}
\sum_{t = 0}^{k - 1}V_t\sigma_t 
&\leq \left[(2\delta + 1)\frac{4(1 + 2\epsilon^2 + \epsilon^3)}{(1 - \epsilon)^2} + \frac{3 + 2\epsilon}{1 - \epsilon}\right]\sum_{t = 0}^{k - 1}\sigma_t \nonumber\\
&\leq  \left[(2\delta + 1)\frac{4(1 + 2\epsilon^2 + \epsilon^3)}{(1 - \epsilon)^2} + \frac{3 + 2\epsilon}{1 - \epsilon}\right]  \frac{\epsilon}{1-r}   \nonumber\\
&\leq \delta,\end{aligned}$$ where the first inequality holds due to , the second inequality holds since $
    \sum_{t = 0}^{k - 1}\sigma_t \leq \frac{\sigma_0}{1 - r} \leq \frac{\epsilon}{1 - r}
$, and the last inequality follows from the first condition in .

Now compute the sum of both sides of from $t = 0$ to $k - 1$ to obtain $$\|\hat{H}_k - I\|_F \leq \|\hat{H}_0 - I\|_F - \sum_{t = 0}^{k - 1}\frac{\|(\hat{H}_t - I)\hat{y}_t\|^2}{4\delta\|\hat{y}_t\|^2} + \sum_{t = 0}^{k - 1}V_t\sigma_t.$$ Regroup the terms and use the result in to show that $$\begin{aligned}
    \sum_{t = 0}^{k - 1}\frac{\|(\hat{H}_t - I)\hat{y}_t\|^2}{4\delta\|\hat{y}_t\|^2} & \leq \|\hat{H}_0 - I\|_F - \|\hat{H}_k - I\|_F + \sum_{t = 0}^{k - 1}V_t\sigma_t\nonumber\\
    & \leq \|\hat{H}_0 - I\|_F + \sum_{t = 0}^{k - 1}V_t\sigma_t\nonumber\\
    & \leq \delta + \delta = 2\delta,\end{aligned}$$ which leads to $$\sum_{t = 0}^{k - 1}\frac{\|(\hat{H}_t - I)\hat{y}_t\|^2}{\|\hat{y}_t\|^2} \leq 8\delta^2.$$ By Cauchy-Schwarz inequality we have that $$\label{proof_thm_BFGS_inter_2}
    \sum_{t = 0}^{k - 1}\frac{\|(\hat{H}_t - I)\hat{y}_t\|}{\|\hat{y}_t\|} \leq 2\sqrt{2}\delta\sqrt{k}.$$ This result provides an upper bound for the sum $\sum_{t = 0}^{k - 1}\frac{\|(\hat{H}_t - I)\hat{y}_t\|}{\|\hat{y}_t\|} $ which is a crucial element in the remaining of the proof. Next we proceed to characterize the relationship between the convergence rate of BFGS and the expression $\sum_{t = 0}^{k - 1}\frac{\|(\hat{H}_t - I)\hat{y}_t\|}{\|\hat{y}_t\|} $.

To do so, note that $x_{t + 1} = x_t - H_t\nabla{f(x_t)}$ and this is equivalent to $H_t\nabla{f(x_t)} = - s_t$. So $\nabla{f(x_{t+1})}$ satisfies $$H_t\nabla{f(x_{t+1})} = H_t(y_t + \nabla{f(x_t)}) = H_t y_t - s_t = (H_t - \nabla^2{f(x_*)}^{-1})y_t + (\nabla^2{f(x_*)}^{-1}y_t - s_t)$$ Premultiply both sides by $\nabla{f(x_*)}^{\frac{1}{2}}$ to obtain $$\hat{H}_t\nabla{\hat{f}(x_{t+1})} = (\hat{H}_t - I)\hat{y}_t + (\hat{y}_t - \hat{s}_t).$$ By using triangle inequality we have $$\|\nabla{\hat{f}(x_{t+1})}\| \leq \|\hat{H}^{-1}_t\|\left[\|\hat{y}_t - \hat{s}_t\| + \|(\hat{H}_t - I)\hat{y}_t\|\right].$$ Using this result and the one in , and (\[lemma\_8\_conclusion\_3\]) we can show that $$\frac{\|\nabla{\hat{f}(x_{t+1})}\|}{\|\hat{y}_t\|} \leq \|\hat{H}^{-1}_t\|\left(\frac{\|\hat{y}_t - \hat{s}_t\|}{\|\hat{y}_t\|} + \frac{\|(\hat{H}_t - I)\hat{y}_t\|}{\|\hat{y}_t\|}\right) \leq \frac{1}{1 - r}\left(\frac{\sigma_t}{1 - \sigma_t} + \frac{\|(\hat{H}_t - I)\hat{y}_t\|}{\|\hat{y}_t\|}\right).$$ By the fact that $\sigma_t \leq \epsilon$ we obtain $$\label{eq:bound_on_grad_over_s_BFGS}
    \frac{\|\nabla{\hat{f}(x_{t+1})}\|}{\|\hat{y}_t\|} \leq \frac{1}{1 - r}\left(\frac{\sigma_t}{1 - \epsilon} + \frac{\|(\hat{H}_t - I)\hat{y}_t\|}{\|\hat{y}_t\|}\right).$$ By (\[lemma\_3\_3\]) we have $$\|\hat{y_t}\| \leq (1 + \sigma_t)\|\hat{s}_t\| \leq (1 + \epsilon)\|\hat{s}_t\|.$$ $$\|\hat{s}_t\| \geq \frac{1}{1 + \epsilon}\|\hat{y_t}\|$$ Using this and the expressions in and , we can show that the rate of convergence $\frac{\|r_{t+1}\|}{\|r_t\|}$ is bounded above by $$\label{eq:bound_on_rate_of_convg_BFGS}
    \frac{\|r_{t+1}\|}{\|r_t\|} \leq \frac{\frac{1}{1 - \epsilon}\|\nabla{\hat{f}(x_{t+1})}\|}{\frac{\|\hat{s}_t\|}{1 + r}} \leq \frac{\frac{1}{1 - \epsilon}\|\nabla{\hat{f}(x_{t+1})}\|}{\frac{\|\hat{y}_t\|}{(1 + \epsilon)(1 + r)}} \leq \frac{(1 + \epsilon)(1 + r)}{(1 - \epsilon)(1 - r)}\left(\frac{\sigma_t}{1 - \epsilon} + \frac{\|(\hat{H}_t - I)\hat{y}_t\|}{\|\hat{y}_t\|}\right),$$ where the last inequality is valid due to the result in . Compute the sum of both sides of from $t = 0$ to $k - 1$ and use the result in to obtain $$\begin{aligned}
    \sum_{t=0}^{k-1}\frac{\|r_{t+1}\|}{\|r_t\|} & \leq \frac{(1 + \epsilon)(1 + r)}{(1 - \epsilon)(1 - r)}\left(\frac{1}{1 - \epsilon}\sum_{t=0}^{k-1}\sigma_t + \sum_{t=0}^{k-1}\frac{\|(\hat{H}_t - I)\hat{y}_t\|}{\|\hat{y}_t\|}\right)\\
    & \leq \frac{(1 + \epsilon)(1 + r)}{(1 - \epsilon)(1 - r)}\left(\frac{\epsilon}{(1 - r)(1 - \epsilon)} + 2\sqrt{2}\delta\sqrt{k}\right).\end{aligned}$$ By leveraging the Arithmetic Geometric inequality we get that $$\label{eq:BFGS_numerical}
    \frac{\|r_k\|}{\|r_0\|} = \prod_{t=0}^{k-1}\frac{\|r_{t+1}\|}{\|r_t\|} \leq \left(\frac{\sum_{t=0}^{k-1}\frac{\|r_{t+1}\|}{\|r_t\|}}{k}\right)^{k} \leq \left(\frac{2\sqrt{2}\delta\frac{(1 + \epsilon)(1 + r)}{(1 - \epsilon)(1 - r)}\sqrt{k} + \frac{(1 + \epsilon)\epsilon(1 + r)}{(1 - \epsilon)^2(1 - r)^2}}{k}\right)^k.$$ Using this and (\[relationship\]) we obtain that $$\frac{\|x_k - x_*\|}{\|x_0 - x_*\|} \leq \sqrt{\frac{L}{\mu}}\frac{\|r_k\|}{\|r_0\|} \leq \sqrt{\frac{L}{\mu}}\left(\frac{2\sqrt{2}\delta\frac{(1 + \epsilon)(1 + r)}{(1 - \epsilon)(1 - r)}\sqrt{k} + \frac{(1 + \epsilon)\epsilon(1 + r)}{(1 - \epsilon)^2(1 - r)^2}}{k}\right)^k,$$ and the proof is complete.

According to Theorem \[thm\_BFGS\], in a local neighborhood of the optimal solution, the sequence of iterates generated by BFGS approaches the optimal solution at a superlinear rate of $(\frac{C_1\sqrt{k}+C_2}{k})^k$, where the constants $C_1$ and $C_2$ determined by $r, \epsilon, \delta \in (0, 1)$ which is similar to the result for DFP in Theorem \[thm\_DFP\]. This result also implies that for sufficiently large $k$ the convergence rate of BFGS is $(\frac{\mathcal{O}(1)}{k})^{k/2}$.

As we mentioned in the analysis of DFP, here we also observe a trade-off between the size of local neighborhood in which BFGS converges superlinearly and the rate of superlinear convergence. For instance, choosing large values for $\epsilon$ and $\delta$ increases the size of the region in which BFGS converges at a superlinear rate, but it will lower the speed of convergence. Hence, by choosing different values for $r$, $\epsilon$, and $\delta$, the region and speed of superlinear convergence change. In the following corollary, we report the result of Theorem \[thm\_BFGS\] for specific choices of $r$, $\epsilon$, and $\delta$ to simplify the expression for the convergence rate of BFGS.

\[cor\_BFGS\] Consider the BFGS method described in Algorithm \[algo\_BFGS\]. Suppose $f(x)$ satisfies the conditions in Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\]. If the initial iterate $x_0$ and the initial Hessian inverse approximation $H_0$ satisfy $$\label{cor_BFGS_neighbor_1}
\|x_0 - x_*\| \leq \frac{\mu^{\frac{3}{2}}}{400M\sqrt{L}},$$ $$\label{cor_BFGS_neighbor_2}
\|\nabla^{2}f(x_*)^{\frac{1}{2}}H_0\nabla^{2}f(x_*)^{\frac{1}{2}} - I\|_F \leq \frac{1}{24},$$ then, for $k \geq 1$, the iterates $\{x_k\}_{k=0}^{+\infty}$ generated by BEGS satisfy $$\label{cor_BFGS_rate}
\|x_k - x_*\| \leq \sqrt{\frac{L}{\mu}}\left(\frac{1}{k}\right)^{\frac{k}{2}}\|x_0 - x_*\|, \qquad \forall k \geq 1.$$

this results can be shown by setting $r = \frac{1}{2}$, $\epsilon = \frac{1}{400}$ and $\delta = \frac{1}{24}$ in theorem \[thm\_BFGS\]. Notice that for these choices of $(r, \epsilon, \delta)$ the conditions in are all satisfied since $$\left[(2\delta + 1)\frac{4(1 + 2\epsilon^2 + \epsilon^3)}{(1 - \epsilon)^2} + \frac{3 + 2\epsilon}{1 - \epsilon}\right]\frac{\epsilon}{1 - r} < \frac{1}{24} = \delta,$$ $$(2\delta + 1)\epsilon + 2\delta = (\frac{2}{24} + 1)\frac{1}{400} + \frac{2}{24} < \frac{1}{2} = r.$$ Moreover, the expression in can be simplified as $$\begin{aligned}
\frac{2\sqrt{2}\delta\frac{(1 + \epsilon)(1 + r)}{(1 - \epsilon)(1 - r)}\sqrt{k} + \frac{(1 + \epsilon)\epsilon(1 + r)}{(1 - \epsilon)^2(1 - r)^2}}{k}
&=\frac{\frac{2\sqrt{2}(1 + \frac{1}{400})(1 + \frac{1}{2})}{24(1 - \frac{1}{400})(1 - \frac{1}{2})} \sqrt{k} + \frac{(1 + \frac{1}{400})\frac{1}{400}(1 + \frac{1}{2})}{(1 - \frac{1}{400})^2(1 - \frac{1}{2})^2} }{k}
< \frac{\frac{1}{2} \sqrt{k} + \frac{1}{2} }{k}
\leq \frac{1 }{\sqrt{k}}\ ,\end{aligned}$$ and the claim in follows.

The result in Corollary \[cor\_BFGS\] shows for specific choices of $\epsilon$, $\delta$, and $r$, the rate of convergence for BFGS is $(1/k)^{k/2}$. Similarly we also need a more practical version of the convergence result for BFGS method. In the following theorem, we show that if we set $H_{0} = \nabla^{2}{f(x_0)}^{-1}$ and the initial distance to the optimal solution $\|x_0 - x_*\|$ is small enough, then the conditions in is satisfied.

\[thm\_BFGS\_Hessian\] Consider the BFGS method described in Algorithm \[algo\_BFGS\]. Suppose $f$ satisfies the conditions in Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\]. If the initial point $x_0$ and initial Hessian inverse approximation matrix $H_0$ satisfy $$\label{thm_BFGS_Hessian_neighbor}
    \|x_0 - x_*\| \leq \frac{\mu^\frac{3}{2}}{M\sqrt{L}}\min\{\epsilon, \frac{\delta}{\sqrt{d}}\}, \qquad H_0 = \nabla^{2}{f(x_0)}^{-1},$$ where $\epsilon$ and $\delta$ are positive constants such that for some $r \in (0, 1)$ they satisfy $$\label{thm_BFGS_condition_22}
\left[(2\delta + 1)\frac{4(1 + 2\epsilon^2 + \epsilon^3)}{(1 - \epsilon)^2} + \frac{3 + 2\epsilon}{1 - \epsilon}\right]\frac{\epsilon}{1 - r} \leq \delta, \qquad (2\delta + 1)\epsilon + 2\delta \leq r\ .$$ Then iterates $\{x_{k}\}_{k=0}^{+\infty}$ generated by BFGS converges to the optimal solution $x_*$ at the rate of $$\|x_k - x_*\| \leq \sqrt{\frac{L}{\mu}}\left(\frac{2\sqrt{2}\delta\frac{(1 + \epsilon)(1 + r)}{(1 - \epsilon)(1 - r)}\sqrt{k} + \frac{(1 + \epsilon)\epsilon(1 + r)}{(1 - \epsilon)^2(1 - r)^2}}{k}\right)^k\|x_0 - x_*\|, \qquad \forall k \geq 1.$$

Notice that by (\[thm\_BFGS\_Hessian\_neighbor\]) we get $$\|x_0 - x_*\| \leq \frac{\mu^{\frac{3}{2}}}{M\sqrt{L}}\epsilon$$ So first part of conditions (\[thm\_BFGS\_neighbor\]) is satisfied. Using assumption \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\] we have $$\begin{split}
   & \|\nabla^{2}f(x_*)^\frac{1}{2}H_0\nabla^{2}f(x_*)^\frac{1}{2} - I\|_F \nonumber\\
   &\qquad = \|\nabla^{2}f(x_*)^\frac{1}{2}(\nabla^{2}f(x_0)^{-1} - \nabla^{2}f(x_*)^{-1})\nabla^{2}f(x_*)^\frac{1}{2}\|_F\\
    &\qquad \leq \sqrt{d}\|\nabla^{2}f(x_*)^\frac{1}{2}(\nabla^{2}f(x_0)^{-1} - \nabla^{2}f(x_*)^{-1})\nabla^{2}f(x_*)^\frac{1}{2}\|\\
    &\qquad = \sqrt{d}\|\nabla^{2}f(x_*)^\frac{1}{2}\nabla^{2}f(x_*)^{-1}(\nabla^{2}f(x_0) - \nabla^{2}f(x_*))\nabla^{2}f(x_0)^{-1}\nabla^{2}f(x_*)^\frac{1}{2}\|\\
    &\qquad = \sqrt{d}\|\nabla^{2}f(x_*)^{-\frac{1}{2}}(\nabla^{2}f(x_0) - \nabla^{2}f(x_*))\nabla^{2}f(x_0)^{-1}\nabla^{2}f(x_*)^\frac{1}{2}\|\\
    &\qquad \leq \sqrt{d}\|\nabla^{2}f(x_*)^{-\frac{1}{2}}\|\|\nabla^{2}f(x_0) - \nabla^{2}f(x_*)\|\|\nabla^{2}f(x_0)^{-1}\|\|\nabla^{2}f(x_*)^\frac{1}{2}\|\\
    &\qquad \leq \sqrt{d}\frac{\sqrt{L}}{\mu^{\frac{3}{2}}}\|\nabla^{2}f(x_0) - \nabla^{2}f(x_*)\|\\
    &\qquad \leq \sqrt{d}\frac{M\sqrt{L}}{\mu^{\frac{3}{2}}}\|x_0 - x_*\|\\
    &\qquad = \delta
\end{split}$$ The first inequality is because of the fact that $\|A\|_F \leq \sqrt{d}\|A\|$ for any matrix $A \in \mathbb{R}^{d \times d}$. The last inequality is due to condition (\[thm\_BFGS\_Hessian\_neighbor\]). Hence second part of conditions (\[thm\_BFGS\_neighbor\]) is also satisfied. By theorem \[thm\_BFGS\] we prove the conclusion.

Based on Theorem \[thm\_BFGS\_Hessian\], when the initial error $\|x_0 - x_*\| = \mathcal{O}(\frac{\mu^{\frac{3}{2}}}{M\sqrt{dL}})$ and the initial Hessian inverse approximation $H_0=\nabla^2 f(x_0)^{-1}$ we get a convergence rate of $\frac{\|x_k - x_*\|}{\|x_0 - x_*\|} \leq \sqrt{\frac{L}{\mu}}(\frac{\mathcal{O}(1)}{k})^\frac{k}{2}$ for the BFGS method.

Discussion {#sec:discussions}
==========

In this section, we discuss the strengths and shortcomings of our main theoretical results and compare them with concurrent papers [@rodomanov2020rates; @rodomanov2020ratesnew] on the non-asymptotic superlinear convergence of DFP and BFGS.

Initial Hessian approximation condition
---------------------------------------

Note that in our main theoretical results, in addition to the fact that the initial iterate $x_0$ has to be close to the optimal solution $x_*$, which is a common condition for local convergence results, we also need the initial Hessian approximation $B_0$ (or its inverse $H_0$) to be close to the Hessian at the optimal solution $\nabla^2 f(x_*)$ (or its inverse $\nabla^2 f(x_*)^{-1}$). At first glance, this might seem restrictive, but as we have shown in Theorem \[thm\_DFP\_Hessian\] for DFP and in Theorem \[thm\_BFGS\_Hessian\] for BFGS, if we set the initial Hessian approximation or its inverse using the Hessian at the initial point $\nabla^2 f(x_0)$, this condition is automatically satisfied as long as the initial iterate error $\|x_0-x_*\|$ is sufficiently small. From a practical point of view this approach is also acceptable as quasi-Newton methods and Newton's method outperform first-order methods only in a local neighborhood of the optimal solution, and globally they could be slower than linearly convergent first-order methods. Hence, as suggested in [@nesterov2013introductory], to obtain the best performance in practice, one might use first-order methods such as Nesterov's accelerated gradient method to reach a local neighborhood of the optimal solution, and then switch to locally fast methods such as quasi-Newton methods. If this procedure is used, our theoretical results show that by setting $B_0=\nabla^2 f(x_0)$ for DFP and $H_0=\nabla^2 f(x_0)^{-1}$ for BFGS, where $x_0$ is the first iterate used for the quasi-Newton scheme, the fast superlinear convergence rate of $(1/k)^{k/2}$ can be obtained.

It is worth noting that the frameworks in [@rodomanov2020rates; @rodomanov2020ratesnew] require the initial Hessian approximation to be $B_0=LI$, where $I$ is the identity matrix and $L$ is the Lipschitz constant of the gradient. Indeed, satisfying this condition is computationally more affordable than our proposed scheme, as it does not require access to the Hessian or its inverse at the initial iterate $x_0$. However, it still requires a *switching scheme*. To be more precise, it requires to monitor the error of iterates and setting the Hessian approximation as $LI$, once the error $\|x-x_*\|$ is sufficiently small.

An ideal theoretical guarantee would be compatible with line-search schemes. To be more precise, in both mentioned analyses we need to monitor the error $\|x-x_*\|$ and reset the Hessian approximation once the error is small. A more comprehensive analysis should be applicable to the case that we follow a line-search approach from the very beginning, and it would automatically guarantee that once the iterates reach a local neighborhood of the optimal solution, the Hessian approximation for DFP or BFGS satisfies the required conditions for superlinear convergence without requiring to reset the Hessian approximation matrix. That said, the results in this work and [@rodomanov2020rates; @rodomanov2020ratesnew] are first attempts to study the non-asymptotic behavior of quasi-Newton methods and there is indeed room for improving these results.

Convergence rate-neighborhood trade-off
---------------------------------------

As mentioned earlier, we observe a trade-off between the radius of the neighborhood in which BFGS and DFP converge superlinearly to the optimal solution and the rate (speed) of superlinear convergence. One important observation here is that for specific choices of $\epsilon$, $\delta$ and $r$, the rate of convergence could be independent of the problem dimension $d$, while the neighborhood of the convergence would depend on $d$. Note that by selecting different parameters we could improve the dependency of the neighborhood on $d$, at the cost of achieving a contraction factor that depends on $d$. In this case, the contraction factor may not be always smaller than $1$, and we can only guarantee that after a few iterations it becomes smaller than $1$ and eventually behaves as $1/k$. The results in [@rodomanov2020rates; @rodomanov2020ratesnew] have a similar structure. For instance, in [@rodomanov2020rates], the authors show that when the initial Newton decrement is smaller than $\frac{\mu^{\frac{5}{2}}}{ML}$, which is independent of the problem dimension, the convergence rate would be of the form $(\frac{dL}{\mu k})^{k/2}$. Hence, to observe the superlinear convergence rate one need to run the BFGS method at least for $d L/\mu$ iterations to ensure the contraction factor is smaller than $1$. A similar conclusion could be made using our results, if we adjust the neighborhood. In our main result, we only report the case that the neighborhood depends on $d$ and the rate is independent of that, since in this case the contraction factor is always smaller than $1$ and the superlinear behavior starts from the very first iteration.

Numerical Experiments {#sec:experiments}
=====================

In this section, we present our numerical experiments and study the non-asymptotic performance of quasi-Newton method and compare them with Newton's method and gradient descent method on different problems. We further investigate if the convergence rate of quasi-Newton method is bounded above by our theoretical guarantees.

In particular, we solve the following optimization problems

$$\label{eq:function_1}
    \min_{x \in \mathbb{R}^d} f_1(x) = x_1^4 + x_1^2 + \sum_{i = 2}^{d}x_i^2,$$

$$\label{eq:function_2}
    \min_{x \in \mathbb{R}^d} f_2(x) = x_1^{40} + 100x_1^2 + \sum_{i = 2}^{d}x_i^2,$$

$$\label{eq:function_3}
    \min_{x \in \mathbb{R}^d} f_3(x) = x_1^{400} + 10000x_1^2 + \sum_{i = 2}^{d}x_i^2,$$

where $d$ is the dimension. We can see that all three functions are strongly convex. Notice that the gradients and Hessians of these functions are not Lipschitz continuous in the global domain $\mathbb{R}^d$. But, in our numerical experiments we restrict all $x \in \mathbb{R}^d$ in a bounded domain near the optimal solution, and the gradients and Hessians of all these objective functions are locally Lipschitz continuous with different parameters in those restricted domain. In summary the objective functions $f_1(x)$, $f_2(x)$ and $f_3(x)$ satisfy Assumptions \[ass\_str\_cvx\_smooth\] and \[ass\_Hess\_lip\] in the close neighborhood of the optimal solution.

In all numerical experiments we conduct the BFGS quasi-Newton method because it is more widely-used compared to the DFP algorithm. Suppose we minimize the function $f(x)$ with optimal solution $x_*$ and notice that for all three functions (\[eq:function\_1\]), (\[eq:function\_2\]) and (\[eq:function\_3\]) we have that solution $x_* = \vec{\mathbf{0}}$ where $\vec{\mathbf{0}} \in \mathbb{R}^d$ is the zero vector. We start the quasi-Newton BFGS method with initial point $x_0$ and the initial Hessian inverse approximation matrix $\nabla^2{f(x_0)}^{-1}$. We also compare the BFGS quasi-Newton method with Newton's method starting from the initial point $x_0$ with step size $1$ and the gradient descent method starting from the same point $x_0$. The step size of the gradient descent method is tuned in different numerical experiments to generate the linear convergence.

In all numerical experiments we set $x_0 = c*\vec{\mathbf{1}}$ where $c > 0$ is a tuned parameter and $\vec{\mathbf{1}} \in \mathbb{R}^d$ is the one vector. We do not set the initial point $x_0$ to satisfy the initial condition (\[cor\_BFGS\_neighbor\_1\]) or (\[thm\_BFGS\_Hessian\_neighbor\]) because those conditions are only sufficient for the superlinear convergence rate. As shown in our numerical experiments even the initial point $x_0$ is out of those neighborhoods we can still achieve the superlinear convergence rate bounded above by the theoretical results. This still confirms our theoretical theorems because when $x_0$ is in those neighbors it will converge to the $x_*$ much faster. Here we use $\|r_k\| = \|\nabla^{2}f(x_*)^{\frac{1}{2}}(x_k - x_*)\|$ to characterize the convergence rate as expressed in (\[eq:BFGS\_numerical\]) from Theorem \[thm\_BFGS\] because this gives a tighter result compared with $\|x_k - x_*\|$ in (\[thm\_BFGS\_rate\]). By Theorem \[thm\_BFGS\], Corollary \[cor\_BFGS\] and Theorem \[thm\_BFGS\_Hessian\] we expect the iterates $\{x_k\}_{k = 0}^{\infty}$ generated by the BFGS update satisfy the following superlinear convergence rate

\[b\]<span>0.45</span> ![Convergence rate of $f_1(x)$ with dimension $d = 30$ and $x_0 = 0.45*\vec{\mathbf{1}}$<span data-label="fig:f_1_30"></span>](Fig1.eps "fig:"){width="\linewidth"}

\[b\]<span>0.45</span> ![Convergence rate of $f_1(x)$ with dimension $d = 30$ and $x_0 = 0.45*\vec{\mathbf{1}}$<span data-label="fig:f_1_30"></span>](Fig2.eps "fig:"){width="\linewidth"}

\[b\]<span>0.45</span> ![Convergence rate of $f_1(x)$ with dimension $d = 3000$ and $x_0 = 0.45*\vec{\mathbf{1}}$<span data-label="fig:f_1_3000"></span>](Fig3.eps "fig:"){width="\linewidth"}

\[b\]<span>0.45</span> ![Convergence rate of $f_1(x)$ with dimension $d = 3000$ and $x_0 = 0.45*\vec{\mathbf{1}}$<span data-label="fig:f_1_3000"></span>](Fig4.eps "fig:"){width="\linewidth"}

$$\frac{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_k - x_*)\|}{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_0 - x_*)\|} \leq \left(\frac{1}{k}\right)^{\frac{k}{2}}, \qquad \forall k \geq 1.$$

Notice that this result is equivalent to the following result.

$$\left(\frac{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_k - x_*)\|}{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_0 - x_*)\|}\right)^\frac{1}{k} \leq \frac{1}{\sqrt{k}}, \qquad \forall k \geq 1.$$

Hence, in our numerical experiments, we compare the convergence rate of $\frac{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_k - x_*)\|}{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_0 - x_*)\|}$ with $\left(\frac{1}{\sqrt{k}}\right)^{k}$ and the convergence rate of $\left(\frac{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_k - x_*)\|}{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_0 - x_*)\|}\right)^{1/k}$ with $\frac{1}{\sqrt{k}}$ to check the correctness of our theoretical guarantees. Our numerical experiments are shown in Figures \[fig:f\_1\_30\], \[fig:f\_1\_3000\], \[fig:f\_2\_30\], \[fig:f\_2\_3000\], \[fig:f\_3\_30\] and \[fig:f\_3\_3000\] for functions $f_1(x)$, $f_2(x)$ and $f_3(x)$ with different dimensions and initial point $x_0$.

\[b\]<span>0.45</span> ![Convergence rate of $f_2(x)$ with dimension $d = 30$ and $x_0 = 0.95*\vec{\mathbf{1}}$<span data-label="fig:f_2_30"></span>](Fig5.eps "fig:"){width="\linewidth"}

\[b\]<span>0.45</span> ![Convergence rate of $f_2(x)$ with dimension $d = 30$ and $x_0 = 0.95*\vec{\mathbf{1}}$<span data-label="fig:f_2_30"></span>](Fig6.eps "fig:"){width="\linewidth"}

\[b\]<span>0.45</span> ![Convergence rate of $f_2(x)$ with dimension $d = 3000$ and $x_0 = 0.99*\vec{\mathbf{1}}$<span data-label="fig:f_2_3000"></span>](Fig7.eps "fig:"){width="\linewidth"}

\[b\]<span>0.45</span> ![Convergence rate of $f_2(x)$ with dimension $d = 3000$ and $x_0 = 0.99*\vec{\mathbf{1}}$<span data-label="fig:f_2_3000"></span>](Fig8.eps "fig:"){width="\linewidth"}

\[b\]<span>0.45</span> ![Convergence rate of $f_3(x)$ with dimension $d = 30$ and $x_0 = \vec{\mathbf{1}}$<span data-label="fig:f_3_30"></span>](Fig9.eps "fig:"){width="\linewidth"}

\[b\]<span>0.45</span> ![Convergence rate of $f_3(x)$ with dimension $d = 30$ and $x_0 = \vec{\mathbf{1}}$<span data-label="fig:f_3_30"></span>](Fig10.eps "fig:"){width="\linewidth"}

\[b\]<span>0.40</span> ![Convergence rate of $f_3(x)$ with dimension $d = 3000$ and $x_0 = 0.99*\vec{\mathbf{1}}$<span data-label="fig:f_3_3000"></span>](Fig11.eps "fig:"){width="\linewidth"}

\[b\]<span>0.40</span> ![Convergence rate of $f_3(x)$ with dimension $d = 3000$ and $x_0 = 0.99*\vec{\mathbf{1}}$<span data-label="fig:f_3_3000"></span>](Fig12.eps "fig:"){width="\linewidth"}

In all figures, the $y-$axis is log scale and the $x-$axis is the number of iterations $k$. Note that for each problem, we present two plots. The first plot (plot (a)) showcases the convergence path of $\frac{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_k - x_*)\|}{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_0 - x_*)\|}$ for BFGS, gradient descent and Newton's method as well as our theoretical result which is $\left(\frac{1}{\sqrt{k}}\right)^{k}$. In the second plot (plot (b)), we compare the convergence path of $\left(\frac{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_k - x_*)\|}{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_0 - x_*)\|}\right)^{1/k}$ for BFGS, gradient descent and Newton's method with our theoretical upper bound which is $\frac{1}{\sqrt{k}}$.

We observe that the convergence path of $\frac{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_k - x_*)\|}{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_0 - x_*)\|}$ for BFGS is bounded above by $\left(\frac{1}{\sqrt{k}}\right)^{k}$ and the convergence path of $\left(\frac{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_k - x_*)\|}{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_0 - x_*)\|}\right)^{1/k}$ for BFGS is bounded above by $\frac{1}{\sqrt{k}}$. Therefore, these experiment results confirm our theoretical superlinear convergence rate of quasi-Newton methods. Also we can see that the convergence path of $\left(\frac{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_k - x_*)\|}{\|\nabla^2{f(x_*)}^{\frac{1}{2}}(x_0 - x_*)\|}\right)^{1/k}$ for quasi-Newton method decays rapidly and much faster than its corresponding theoretical upper bound $\frac{1}{\sqrt{k}}$. This indicates that for those specific problems there may exist faster superlinear convergence rate than $\left(\frac{1}{\sqrt{k}}\right)^{k}$ and this leaves some room for improvements of our theoretical results.

We also observe that Newton's method outperforms BFGS and BFGS outperforms the gradinet descent. This is indeed expected as gradient descent only achieves linear convergence rate while quasi-Newton methods are superlinear. And quasi-Newton methods are not as fast as Newton's method, because in each iteration of Newton's method we calculate the exact Hessian inverse matrix, while quasi-Newton methods only use the Hessian inverse approximation matrix as the second-order information. The advantage of quasi-Newton methods is that the expense of the update of Hessian inverse approximation matrix is usually much less than the cost of computing Newton's method descent direction.

Conclusion {#sec:conclusion}
==========

In this paper, we studied the local convergence rate of DFP and BFGS quasi-Newton methods and provided their non-asymptotic superlinear convergence rate. In particular, for the DFP method, we showed that if the initial distance to the optimal solution is $\|x_0 - x_*\| = \mathcal{O}(\frac{\mu^{\frac{3}{2}}}{M\sqrt{L}})$ and the initial Hessian approximation error is $\|{\nabla^{2}f(x_*)^{-\frac{1}{2}}}\ \! B_0\ \!{\nabla^{2}f(x_*)^{-\frac{1}{2}}} - I\|_F = \mathcal{O}(1)$, then the sequence of iterates converges to the optimal solution at a superlinear rate of $\frac{\|x_k - x_*\|}{\|x_0 - x_*\|} \leq \sqrt{\frac{L}{\mu}}\left(\frac{\mathcal{O}(1)}{k}\right)^{\frac{k}{2}}$. Specially, we can achieve the same superlinear convergence rate for DFP method if the initial error is $\|x_0 - x_*\| = \mathcal{O}(\min\{\frac{\mu^\frac{3}{2}}{M\sqrt{L}}, \frac{\mu}{M\sqrt{d}}\})$ and the initial Hessian approximation matrix is $\nabla^2{f(x_0)}$. For the BFGS method, we showed that if the initial distance to the optimal solution is $\|x_0 - x_*\| = \mathcal{O}(\frac{\mu^{\frac{3}{2}}}{M\sqrt{L}})$ and the initial Hessian inverse approximation error is $\|{\nabla^{2}f(x_*)^{\frac{1}{2}}}\ \! H_0\ \!{\nabla^{2}f(x_*)^{\frac{1}{2}}} - I\|_F = \mathcal{O}(1)$, then iterates converge to the optimal solution at a superlinear rate of $\frac{\|x_k - x_*\|}{\|x_0 - x_*\|} \leq \sqrt{\frac{L}{\mu}}\left(\frac{\mathcal{O}(1)}{k}\right)^{\frac{k}{2}}$. In particular, we can achieve the same superlinear convergence rate for BFGS method if the initial error is $\|x_0 - x_*\| = \mathcal{O}(\frac{\mu^\frac{3}{2}}{M\sqrt{Ld}})$ and the initial Hessian inverse approximation matrix is $\nabla^2{f(x_0)}^{-1}$.

Acknowledgment {#acknowledgment .unnumbered}
==============

Q. Jin acknowledges support from a National Initiative for Modeling and Simulation (NIMS) Graduate Research Fellowship. The research of A. Mokhtari is supported by NSF Award CCF-2007668.

Proof of Lemma \[lemma:lemma\_1\] {#sec:proof_of_lemma_1}
=================================

We first use the fact that $\mathrm{Tr}\left(ab^\top\right) = a^\top b$ for any $a, b \in \mathbb{R}^d$ to show that $$\label{eq:proof_1_1}
\begin{split}
    \| A(I - uu^\top)\|^2_F & = \mathrm{Tr}\left((I - uu^\top)^\top A^\top A(I - uu^\top)\right)\\
    & = \mathrm{Tr}\left(A^\top A - uu^\top A^\top A - A^\top Auu^\top + uu^\top A^\top Auu^\top\right)\\
    & = \mathrm{Tr}\left(A^\top A\right) - \mathrm{Tr}\left(uu^\top A^\top A\right) - \mathrm{Tr}\left(A^\top Auu^\top\right) + \mathrm{Tr}\left(uu^\top A^\top Auu^\top\right)\\
    & = \|A\|^2_F - 2u^\top A^\top Au + u^\top A^\top Au\mathrm{Tr}\left(uu^\top\right)\\
    & = \|A\|^2_F - 2\|Au\|^2 + \|Au\|^2(u^\top u)\\
    & = \|A\|^2_F - \|Au\|^2,
\end{split}$$ where in the last equality we used the fact that $u^\top u = \|u\|^2 = 1$. Replace $A$ by $(I - uu^\top)A$ in the above equation to obtain $$\label{eq:proof_1_2}
\|(I - uu^\top)A(I - uu^\top)\|^2_F = \|(I - uu^\top)A\|^2_F - \|(I - uu^\top)Au\|^2 \leq \|(I - uu^\top)A\|^2_F.$$ Use the inequality in and symmetry of $A$ to write $$\begin{split}
    \|(I - uu^\top)A(I - uu^\top)\|^2_F 
    & \leq\|(I - uu^\top)A\|^2_F\\
    & =
     \mathrm{Tr}\left(A^\top(I - uu^\top)^\top(I - uu^\top)A\right)\\
    & = \mathrm{Tr}\left((I - uu^\top)AA^\top(I - uu^\top)^\top\right)\\
    & = \mathrm{Tr}\left((I - uu^\top)^\top A^\top A(I - uu^\top)\right)\\
    & = \|A(I - uu^\top)\|^2_F\\
    & = \|A\|^2_F - \|Au\|^2,
\end{split}$$ where the last equality holds due to the result in . Hence, the claim in holds and the proof is complete.

Proof of Lemma \[lemma:lemma\_2\] {#sec:proof_of_lemma_2}
=================================

Since $A$ is a symmetric positive definite matrix we can have that $A = U^\top DU$ where $U \in \mathbb{R}^{d \times d}$ is an unitary matrix and $D \in \mathbb{R}^{d \times d}$ is a diagonal matrix with $D_{ii} > 0$ for all $1\leq i \leq d$. These conditions imply that $\|A\| = \max_{1 \leq i \leq d}{D_{ii}}$. Hence, we can write $$\|AB\|^2_F = \mathrm{Tr}\left(B^\top A^\top AB\right) = \mathrm{Tr}\left(B^\top U^\top D^2UB\right) = \mathrm{Tr}\left(D^2UBB^\top U^\top\right)$$ Since $U^\top U = I$ and $UBB^\top U^\top$ is a symmetric positive semi-definite matrix we have that $$\|AB\|^2_F \leq \max_{1 \leq i \leq d}{D^2_{ii}}\mathrm{Tr}\left(UBB^\top U^\top\right) = \|A\|^2\mathrm{Tr}\left(B^\top U^\top UB\right) = \|A\|^2\mathrm{Tr}\left(B^\top B\right) = \|A\|^2\|B\|^2_F$$ Hence, we have $$\|AB\|_F \leq \|A\|\|B\|_F$$ and the proof of the first result is complete. Next, to prove the second claim we use the fact that $$\label{sdadas}
\|B^\top AB\|^2_F  = \mathrm{Tr}\left(B^\top A^\top BB^\top AB\right) = \mathrm{Tr}\left(B^\top U^\top DUBB^\top U^\top DUB\right) = \mathrm{Tr}\left(DUBB^\top U^\top DUBB^\top U^\top\right)$$ Notice $UBB^\top U^\top DUBB^\top U^\top$ and $UBB^\top BB^\top U^\top$ are symmetric positive semi-definite, and, therefore, $$\label{sdadas2}
\begin{split}
    \mathrm{Tr}\left(DUBB^\top U^\top DUBB^\top U^\top\right) & \leq \max_{1 \leq i \leq d}{D_{ii}}\mathrm{Tr}\left(UBB^\top U^\top DUBB^\top U^\top\right)\\
    & = \max_{1 \leq i \leq d}{D_{ii}}\mathrm{Tr}\left(DUBB^\top U^\top UBB^\top U^\top \right)\\
    & = \max_{1 \leq i \leq d}{D_{ii}}\mathrm{Tr}\left(DUBB^\top BB^\top U^\top \right)\\
    & \leq \max_{1 \leq i \leq d}{D^2_{ii}}\mathrm{Tr}\left(UBB^\top BB^\top U^\top \right)\\
    & = \max_{1 \leq i \leq d}{D^2_{ii}}\mathrm{Tr}\left(B^\top BB^\top U^\top UB\right)\\
    & = \max_{1 \leq i \leq d}{D^2_{ii}}\mathrm{Tr}\left(B^\top BB^\top B\right)\\
    & = \|A\|^2\|B^\top B\|^2_F
\end{split}$$ By combining the results in and we obtain that $$\|B^\top AB\|_F \leq \|A\|\|B^\top B\|_F \leq \|A\|\|B^\top\|_F\|B\|_F = \|A\|\|B\|^2_F,$$ and the proof is complete.

Proof of Lemma \[lemma:lemma\_3\] {#sec:proof_of_lemma_3}
=================================

By Assumption \[ass\_str\_cvx\_smooth\] and Corollary \[corollary\] we have $$\label{sec_3_proof_10}
\begin{split}
\|\hat{y}_k - \hat{s}_k\| & = \|\nabla^{2}f(x_*)^{-\frac{1}{2}}y_k - \nabla^{2}f(x_*)^{\frac{1}{2}}s_k\|\\
& \leq \|\nabla^{2}f(x_*)^{-\frac{1}{2}}\|\|y_k - \nabla^{2}f(x_*)s_k\|\\
& = \|\nabla^{2}f(x_*)^{-\frac{1}{2}}\|\|\nabla{f(x_{k+1})} - \nabla{f(x_k)} - \nabla^{2}f(x_*)(x_{k+1} - x_k)\|\\
& \leq \frac{M}{\mu^{\frac{1}{2}}}\|s_k\|\max{\{\|x_{k+1} - x_*\|, \|x_k - x_*\|\}}
\end{split}$$ Notice that $$\label{sec_3_proof_20}
\|s_k\| = \|\nabla^{2}f(x_*)^{-\frac{1}{2}}\nabla^{2}f(x_*)^{\frac{1}{2}}s_k\| \leq \|\nabla^{2}f(x_*)^{-\frac{1}{2}}\|\|\hat{s}_k\| \leq \frac{1}{\mu^{\frac{1}{2}}}\|\hat{s}_k\|,$$ and based on the definition $  r_k = \nabla^{2}f(x_*)^{\frac{1}{2}}(x_k - x_*)$ we have $  x_k - x_* = \nabla^{2}f(x_*)^{-\frac{1}{2}}r_k$ and hence $$\label{sec_3_proof_30}
\max{\{\|x_{k+1} - x_*\|, \|x_k - x_*\|\}} \leq \|\nabla^{2}f(x_*)^{-\frac{1}{2}}\|\max{\{\|r_k\|, \|r_{k+1}\|\}} \leq \frac{1}{\mu^{\frac{1}{2}}}\max{\{\|r_k\|, \|r_{k+1}\|\}}.$$ Replace the upper bounds in and into to obtain $$\label{sec_3_proof_40}
\|\hat{y}_k - \hat{s}_k\| \leq \frac{M}{\mu^{\frac{3}{2}}}\max{\{\|r_k\|, \|r_{k+1}\|\}}\|\hat{s}_k\| = \tau_k\|\hat{s}_k\|,$$ where the last equality holds since $ \tau_k = \max\{\sigma_k, \sigma_{k+1}\}$ and $\sigma_k = \frac{M}{\mu^{\frac{3}{2}}}\|r_k\|$. Hence, the proof of the first claim in is complete.

By using Cauchy-Schwarz inequality and the result in we can write $$-\tau_k\|\hat{s}_k\|^2 \leq -\|\hat{y}_k - \hat{s}_k)\|\|\hat{s}_k\| \leq (\hat{y}_k - \hat{s}_k)^\top\hat{s}_k \leq \|\hat{y}_k - \hat{s}_k)\|\|\hat{s}_k\| \leq \tau_k\|\hat{s}_k\|^2.$$ Therefore, we obtain that $$(1 - \tau_k)\|\hat{s}_k\|^2 \leq \hat{s}_k^\top\hat{y}_k \leq (1 + \tau_k)\|\hat{s}_k\|^2,$$ and the second claim in holds.

Next, we prove the third claim in . Note that $(1 - \tau_k)\|\hat{s}_k\|^2 \leq \hat{s}_k^\top\hat{y}_k \leq \|\hat{s}_k\|\|\hat{y}_k\|$ which implies $(1 - \tau_k)\|\hat{s}_k\| \leq \|\hat{y}_k\|.$ Also, by triangle inequality we have $\|\hat{y}_k\| \leq \|\hat{y}_k - \hat{s}_k\| + \|\hat{s}_k\| \leq (1 + \tau_k)\|\hat{s}_k\|$. Hence, both sides of the inequality in hold.

Next, to prove the last claim in , we use Assumption \[ass\_str\_cvx\_smooth\] and Corollary \[corollary\] to show $$\begin{split}
\|\nabla{\hat{f}(x_k)} - r_k\| & = \|\nabla^{2}f(x_*)^{-\frac{1}{2}}\nabla{f(x_k)} - \nabla^{2}f(x_*)^{\frac{1}{2}}(x_k - x_*)\|\\
& \leq \|\nabla^{2}f(x_*)^{-\frac{1}{2}}\|\|\nabla{f(x_k)}  - \nabla{f(x_*)} - \nabla^{2}f(x_*)(x_k - x_*)\|\\
& \leq \frac{M}{\mu^{\frac{1}{2}}}\|x_k - x_*\|^2\\
& = \frac{M}{\mu^{\frac{1}{2}}}\|\nabla^{2}f(x_*)^{-\frac{1}{2}}\nabla^{2}f(x_*)^{\frac{1}{2}}(x_k - x_*)\|^2\\
& \leq \frac{M}{\mu^{\frac{3}{2}}}\|r_k\|^2\\
& = \sigma_k\|r_k\|.
\end{split}$$

[^1]: Oden Institute for Computational Engineering and Sciences, The University of Texas at Austin, Austin, TX, USA. {qmartinez@example.net}.

[^2]: Department of Electrical and Computer Engineering, The University of Texas at Austin, Austin, TX, USA. {qmartinez@example.net}.

{'source': 'arXiv_out/2003'}