remarkRemark hypothesisHypothesis claimClaim Augmented Newton MethodMd Sarowar
Morshed AND ex_supplement

# Augmented Newton Method for Optimization: Global Linear Rate and Momentum
Interpretation

Md Sarowar Morshed Independent Researcher (, https://morshed.netlify.app/).
<EMAIL_ADDRESS>
###### Abstract

We propose two variants of Newton method for solving unconstrained
minimization problem. Our method leverages optimization techniques such as
penalty and augmented Lagrangian method to generate novel variants of the
Newton method namely the Penalty Newton method and the Augmented Newton
method. In doing so, we recover several well-known existing Newton method
variants such as Damped Newton, Levenberg, and Levenberg-Marquardt methods as
special cases. Moreover, the proposed Augmented Newton method can be
interpreted as Newton method with adaptive heavy ball momentum. We provide
global convergence results for the proposed methods under mild assumptions
that hold for a wide variety of problems. The proposed methods can be sought
as the penalty and augmented extensions of the results obtained by Karimireddy
et. al [24].

###### keywords:

Newton Method, Generalized Linear Model, Augmented Newton Method, Penalty
Newton Method, Penalty Method, Augmented Lagrangian, Method of Multipliers,
Nonlinear Optimization.

49M15, 49M37, 58C15, 65K05, 65K10, 65Y20, 68Q25, 90C06, 90C30, 90C51.

##  1 Introduction

In this work, we consider solving the following unconstrained minimization
problem:

(1) $\min_{x\in\mathbb{R}^{n}}f(x),$

where $f:\mathbb{R}^{n}\to\mathbb{R}$ is a well behaved function. Newton’s
method is one of the most important method for solving the above optimization
problem. Although, Newton’s method is originally proposed in the context of
finding roots of polynomial equations, from the last century it has been
recognised as one of the fundamental second order methods for solving
optimization problems. In the following, we discuss the historical
developments of the Newton method as well as the modern developments of Newton
method variants.

#### Historical developments

The first occurrence of Newton type method can be traced back to the work of
Persian astronomer and mathematician Al-Kashi (1380–1429). In his seminal work
’The Key to Arithmetic’ published in 1427, he discussed a variant of Newton
method that was based on the earlier works by the famous polymath Al-Biruni
(973–1048) and mathematician Al-Tusi (1135-1213). The work of Al-Kashi
remained hidden to the western scientific community until the work of Francois
Vieta (1540-1603). In 1600, Vieta rediscovered a similar technique like Al-
Kashi’s in the context of solving scalar polynomial equations of degree six
[45]. Vieta’s method gained considerable attention by the work of Sir Isaac
Newton (1643–1727) who improved Vieta’s method immensely and developed a
closely related method [26] in his seminal works titled ’De analysi per
aequationes numero terminorum infinitas’ (1669, published in 1711) and ’De
metodis fluxionum et serierum infinitarum’ (1671, published in 1736). Based on
the work of Newton, Joseph Raphson (1648-1715) in 1690 proposed a closely
related method for finding roots of polynomial equations. However, the
connection between Newton method and function derivative was unknown until the
later work of Thomas Simpson (1710-1761). In 1740, Simpson proposed a closely
related variant of Newton method which was the earliest method that resembles
the modern Newton method most [8].

During early 1900s, the works of Bennet [5] and Kantarovich [22] are the
driving force for the popularization of the Newton method as an optimization
algorithm. In his seminal work [23] Kantarovich was the first one to prove
local linear convergence of the Newton method for solving operator equation.
This prompted several convergence proofs of variants of Newton method under
various assumptions (for a detailed discussion on this issue we refer
interested reader to the work of Ortega et. al [33]). In the 1980s, Newton’s
scheme has found applications in various nonlinear optimization algorithm
settings such as Augmented Lagrangian [6], and Interior Point Methods (IPMs)
[1]. In that time, Nesterov and Nemirovski [1] proved that under the condition
of ’self-concordance’ Newton method achieves quadratic convergence rate
locally.

#### Modern developments

In the last decade, there has been a surge of work developing convergence
results of variants of Newton method (for a detailed discussion please see
[32] and the references therein). At that time, most of the global convergence
results either used strong assumptions on the function $f(x)$ or had
incomparable convergence rates 111One can obtain similar type of global
convergence rates for the inexact type Newton method [40, 28]. with respect to
the Gradient Descent (GD) algorithm. Moreover, some variants have slower rates
compared to the vanilla GD algorithm proposed in [18]. The first breakthrough
result in terms of convergence result has been obtained by Nesterov and
Polyak. In their seminal work [32], they obtained $O(1/k^{2})$ convergence
rate. Subsequently after that Nesterov achieved $O(1/k^{3})$ rate using the
so-called cubic regularization technique [31]. The main ingenuity of these
works is that, these rates do not require either the strong convexity or the
Lipschitz smoothness conditions which were the state-of-the-art assumptions
[35, 28] of that time. The main disadvantage of these cubic variants is that
the cubic subproblem that is the building block of these methods is hard to
solve and often times impractical for huge dimensional problems. In their
recent work, Karireddy et. al provided the convergence results of the Newton
method and its trust region variants under the $c$–stability condition [24].
They showed that the $c$–stability condition is weaker than the standard
Lipschitz smoothness, and strong convexity conditions and furthermore
$c$–stability is much more weaker than the ’self-concordance’ assumption of
Nesterov and Nemirovski [1]. Recently it has been shown that convergence of
some variants of Newton’s method can be achieved without smoothness or
convexity [38].

Most modern variants of the Newton method can be categorized into three
special types such as _Subsampled Newton_ , _Cubic Newton_ , and _Subspace
Newton_ methods. Subsampled Newton methods are stochastic second order
algorithms designed mostly to tackle the finite sum minimization problem. Over
the years, several variants such as _Subsampled Newton_ methods[7, 14, 44, 39]
and _Subsampled Cubic Newton_ methods [25, 43, 42] and _Stochastic Cubic
Newton_ methods [41, 11, 27] have been proposed. These methods make use of the
Hessian sketching technique [34]. Cubic Newton method make use of the cubic
regularization of the Taylor approximation of the function $f(x)$. In their
work [32], Nesterov et. al established the first global complexity results of
the Cubic Newton method. After their work surprising result, research boomed
in developing variants of cubic Newton method such as accelerated [31, 29],
adaptive [9, 10], block [13], and universal [16, 17, 12] cubic Newton methods.
Subspace Newton methods are the type of stochastic algorithms that use random
projections of the Hessian matrix. These types of methods are of the form
$x_{k+1}=x_{k}+Sh_{k}$, where $S$ is a random sketch matrix and $h_{k}$ is the
sketched Newton direction. Several available variants of these types are
Stochastic Dual Newton Ascent [37], Randomized Subspace Newton [15],
Stochastic Subspace Cubic Newton [19], and Sketched Newton-Raphson [46].

###  1.1 Newton Method

The full Newton method for solving problem (1) can be expressed as the
following update formula:

(2) $\displaystyle
x_{k+1}=x_{k}-\left(\nabla^{2}f(x_{k})\right)^{\dagger}\nabla f(x_{k}).$

A more general form of the update is the so-called Damped Newton (DN) method
that can expressed as follows:

(3) $\displaystyle
x_{k+1}=x_{k}-t\left(\nabla^{2}f(x_{k})\right)^{\dagger}\nabla f(x_{k}).$

An standard way of choosing step size $t$ is by backtracking line search which
goes as follows: start with $t=1$ and $0<\alpha\leq 1/2$, $0<\beta<1$ and
check the following:

$\displaystyle f(x_{k+1})>f(x_{k})-\alpha t\nabla
f(x_{k})^{\top}\left(\nabla^{2}f(x_{k})\right)^{\dagger}\nabla f(x_{k}).$

The quantity $\left(\nabla
f(x_{k})^{\top}\left(\nabla^{2}f(x_{k})\right)^{\dagger}\nabla
f(x_{k})\right)^{1/2}$ is known as the Newton Decrement. It is well-known that
the above method with backtracking line search achieve quadratic convergence
rate under some nice assumptions on function $f(x)$.

###  1.2 Contributions

In this paper, we make the following fundamental contributions:

  * •

New variants of Newton method. We propose two variants of Newton method namely
the Penalty Newton Method (PNM) and Augmented Newton Method (ANM) by
incorporating the Lagrangian penalty function based techniques on the Newton
system (16).

  * •

Special cases. From our proposed algorithms we recover well-known algorithms
such as Levenberg and Levenberg-Marquardt algorithms as special cases.

  * •

Momentum interpretation. Moreover, the proposed ANM algorithm can be
interpreted as Newton method with adaptive heavy ball momentum.

  * •

Global linear rate. We analyze and obtain linear convergence results for the
proposed methods under weaker assumptions on the function $f(x)$. For
instance, we proved convergence results without imposing the strong convexity
and Lipschitz continuity conditions on the function $f(x)$.

Furthermore, we analyze and compare the efficiency of the proposed methods to
the Newton method for solving Generalized Linear Models. The proposed PNM and
ANM algorithms bear resemblance to the recently proposed penalty and augmented
Kaczmarz methods for solving linear systems and linear feasibility problems
[30].

##  2 Notations, Assumptions and Preliminary Results

In this section, we introduce some standard notations and definitions that
will be used throughout the paper. We also provide necessary assumptions that
are crucial to the convergence analysis of the proposed methods. At the end of
this section, we mention some technical results most of those are borrowed
from the literature.

###  2.1 Notations & Definitions

For any matrix $A$, by $A^{\dagger}$, $\textbf{Range}(A)$, $\textbf{Null}(A)$,
$\lambda_{\min}^{+}(A)$, $\lambda_{\max}(A)$, $\sigma_{\min}^{+}(A)$,
$\sigma_{\max}(A)$ we denote the Moore-Penrose pseudo-inverse, range, null,
the smallest nonzero eigenvalue, the largest eigenvalue of matrix $A$, the
smallest nonzero singular value, the largest singular value of matrix $A$,
respectively. For any positive definite matrix $B\in\mathbb{R}^{n\times n}$,
we denote $\langle x,Bx\rangle=x^{\top}Bx=\|x\|_{B}^{2}$. We denote the
optimal value of (1) as $f^{*}=f(x^{*})$, where, $x^{*}$ is the optimal
solution. We denote $\nabla f(x)$ and $\nabla^{2}f(x)=\mathbf{H}(x)$ as the
gradient and Hessian of $f$ at $x$, respectively. Let,
$G\in\mathbb{R}^{n\times n}$ be a positive definite matrix, then for any
$x\in\mathbb{R}^{n}$ let us define the following matrices:

(4)
$\displaystyle\mathbf{K}(x)=\left(\frac{1}{\rho}G+\mathbf{H}(x)\right)^{-1},\
\
\mathbf{L}(x)=\mathbf{H}^{\frac{1}{2}}(x)\left(\frac{1}{\rho}I+\mathbf{H}^{\frac{1}{2}}(x)G^{-1}\mathbf{H}^{\frac{1}{2}}(x)\right)^{-1}\mathbf{H}^{\frac{1}{2}}(x).$

We denote the set $\mathcal{Q}_{\rho}$ as the level set of function
$f(x)+\frac{L}{2\rho}\|x-y\|^{2}_{G}$ associated with initial iterates $x_{0}$
and $y_{0}$ as follows:

(5) $\displaystyle\mathcal{Q}_{\rho}:=\\{x,y\in\mathbb{R}^{n}\ :\
f(x)+\frac{L}{2\rho}\|x-y\|^{2}_{G}\leq
f(x_{0})+\frac{L}{2\rho}\|x_{0}-y_{0}\|^{2}_{G}\\}.$

###  2.2 Assumptions

Throughout the paper, we assume $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is
convex, twice differentiable and bounded from below. Also, we assume the set
of minimizers of problem (1) is nonempty. Furthermore, we assume the following
two assumptions hold.

######  Assumption 1.

There exists constant $0<\mu\leq L$ such that the following relations hold:

(6) $\displaystyle f(x)\leq f(y)+\langle\nabla
f(y),x-y\rangle+\frac{L}{2}\|x-y\|^{2}_{\mathbf{H}(y)},$ (7) $\displaystyle
f(x)\geq f(y)+\langle\nabla
f(y),x-y\rangle+\frac{\mu}{2}\|x-y\|^{2}_{\mathbf{H}(y)},$

for all $x,y\in\mathcal{Q}_{\rho}$.

In the literature, these constants have been referred to as the relative
smoothness constant, $L$ and the relative convexity constant, $\mu$ [24, 15].
One can show that the conditions of assumption 1 are direct consequences of
the smoothness and strong convexity conditions. Indeed, from Lemma 2 of [24],
we have the following relations

$\displaystyle\mbox{$L$--smooth + $\mu$--strongly
convex}\quad\Rightarrow\quad\mbox{$c$--stability},$
$\displaystyle\mbox{$c$--stability}\quad\Rightarrow\quad\mbox{$L$--relative
smoothness \& $\mu$--relative convexity}.$

where, the condition $c$–stability was introduced in [24]. Specially in [24],
the authors proved that assuming the $c$–stability of the Hessian matrix is
sufficient for proving global linear convergence of the Newton method. This
specific assumption of stable Hessian was also used to analyze the statistical
characteristics of the logistic regression [2], and the convergence of
Stochastic Gradient descent (SGD) for logistic regression [4, 3]. We will also
assume the following:

######  Assumption 2.

For all $x\in\mathbb{R}^{n}$, we have $\nabla
f(x)\in\textbf{Range}(\mathbf{H}(x))$.

If the Hessian is positive definite, assumption 2 holds trivially. Moreover,
the above assumption holds generally for the Generalized Linear Model.

###  2.3 Preliminary Results

In the following, we will introduce some preliminary technical results that
will be used frequently throughout our convergence analysis.

######  Lemma 2.1.

(Lemma 9 in [15]) Let $y\in\mathbb{R}^{n}$, $\kappa>0$ and
$\mathbf{H}\in\mathbb{R}^{n\times n}$ be a symmetric positive semi-definite
matrix. Let $w\in\textbf{Range}(\mathbf{H})$. Then, we have

(8) $\min_{x\in\mathbb{R}^{n}}\langle
w,x-y\rangle+\frac{\kappa}{2}\|x-y\|_{\mathbf{H}}^{2}=-\frac{1}{2\kappa}\|w\|_{\mathbf{H}^{\dagger}}^{2}.$

######  Lemma 2.2.

Let Assumptions 1 and 2 holds, then we have the following

(9) $\displaystyle f(x_{k})-f^{*}$ $\displaystyle\leq\frac{1}{2\mu}\|\nabla
f(x_{k})\|_{\mathbf{H}^{\dagger}(x_{k})}^{2}.$

######  Proof 2.3.

Substituting $y=x_{k}$ in (7), we get

$\displaystyle f(x)\overset{\eqref{als:an:8}}{\geq}f(x_{k})+\langle\nabla
f(x_{k}),x-x_{k}\rangle+\frac{\mu}{2}\|x-x_{k}\|^{2}_{\mathbf{H}(x_{k})}.$

Minimizing over all $x\in\mathcal{Q}_{\rho}$ and using Lemma 2.1 we get

$\displaystyle f^{*}-f(x_{k})$
$\displaystyle\geq\min_{x\in\mathcal{Q}_{\rho}}\left[\langle\nabla
f(x_{k}),x-x_{k}\rangle+\frac{\mu}{2}\|x-x_{k}\|^{2}_{\mathbf{H}(x_{k})}\right]$
$\displaystyle\geq\min_{x\in\mathbb{R}^{n}}\left[\langle\nabla
f(x_{k}),x-x_{k}\rangle+\frac{\mu}{2}\|x-x_{k}\|^{2}_{\mathbf{H}(x_{k})}\right]\overset{\eqref{als:an:9}}{=}-\frac{1}{2\mu}\|\nabla
f(x_{k})\|_{\mathbf{H}^{\dagger}(x_{k})}^{2}.$

This proves the Lemma.

Next, we provide the definition of Generalized Linear Model that satisfy
assumptions 1 and 2. Let $\phi_{i}:\mathbb{R}\to\mathbb{R}_{+}$ be twice
differentiable functions such that $u\leq\phi_{i}^{\prime\prime}(t)\leq\ell,\
0\leq u\leq\ell$ hold for all $i=1,2,...,m$. Take,
$A=[a_{1},a_{2},...,a_{m}]\in\mathbb{R}^{n\times m}$ where
$a_{i}\in\mathbb{R}^{n}$ for $i=1,\ldots,m$. Now, let us function
$f:\mathbb{R}^{n}\to\mathbb{R}$ is defined as follows:

(10) $\displaystyle
f(x)=\frac{1}{m}\sum\limits_{i=1}^{m}\phi_{i}(a_{i}^{\top}x)+\frac{\alpha}{2}\|x\|^{2},$

for some $\alpha>0$. The problem $\min_{x\in\mathbb{R}^{n}}f(x)$ is called a
Generalized Linear Model with $L_{2}$ regularization. The Hessian of the above
function is given by

(11)
$\displaystyle\nabla^{2}f(x)=\mathbf{H}(x)=\textstyle\frac{1}{m}\sum\limits_{i=1}^{m}a_{i}a_{i}^{\top}\phi_{i}^{\prime\prime}(a_{i}^{\top}x)+\alpha
I=\frac{1}{m}A\Phi^{\prime\prime}(A^{\top}x)A^{\top}+\alpha I.$

Since, $\mathbf{H}(x)\succ 0$ for all $x$ assumption 2 is satisfied trivially.
The following Lemma was proven in [15].

######  Lemma 2.4.

(Proposition 1, [15]) Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a Generalized
Linear Model with $0\leq u\leq\ell$. Then, assumption 2 is satisfied with

(12) $\displaystyle L=\frac{\ell\ \sigma_{\max}^{2}(A)+m\alpha}{u\
\sigma_{\max}^{2}(A)+m\alpha}\qquad\mbox{and}\qquad\mu=\frac{u\
\sigma_{\max}^{2}(A)+m\alpha}{\ell\ \sigma_{\max}^{2}(A)+m\alpha}.$

######  Lemma 2.5.

(Woodbury Matrix Identity, [20]) Assume matrices $A\in\mathbb{R}^{q\times q}$,
and $C\in\mathbb{R}^{r\times r}$ are invertible. Then the following identity
holds:

(13)
$\displaystyle\left(A+UCV\right)^{-1}=A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1},$

for any matrices $U\in\mathbb{R}^{q\times r}$ and $V\in\mathbb{R}^{r\times q}$
such that $A+UCV$ and $C^{-1}+VA^{-1}U$ are non-singular.

######  Lemma 2.6.

The following relations hold:

(14) $\displaystyle\mathbf{H}(x)\mathbf{K}(x)=I-\frac{1}{\rho}G\mathbf{K}(x),$
(15) $\displaystyle G\mathbf{K}(x)G=\rho G-\rho\mathbf{L}(x).$

######  Proof 2.7.

Since, $\mathbf{K}(x)$ is invertible, we have the following simplification:

$\displaystyle\mathbf{H}(x)\mathbf{K}(x)=\left[\frac{1}{\rho}G+\mathbf{H}(x)-\frac{1}{\rho}G\right]\mathbf{K}(x)=\left[\mathbf{K}^{-1}(x)-\frac{1}{\rho}G\right]\mathbf{K}(x)=I-\frac{1}{\rho}G\mathbf{K}(x).$

This resolves the first part of Lemma 2.6. This proves the first part of the
Lemma. As $G^{-1}\succ 0$ follows from our construction, using the Woodburry
matrix identity and the definition of $\mathbf{L}(x)$, we have the following:

$\displaystyle\mathbf{L}(x)$
$\displaystyle=\mathbf{H}^{\frac{1}{2}}(x)\left(\frac{1}{\rho}+\mathbf{H}^{\frac{1}{2}}(x)G^{-1}\mathbf{H}^{\frac{1}{2}}(x)\right)^{-1}\mathbf{H}^{\frac{1}{2}}(x)$
$\displaystyle\overset{\eqref{als:an:14}}{=}\mathbf{H}^{\frac{1}{2}}(x)\left[\rho-\rho^{2}\mathbf{H}^{\frac{1}{2}}(x)\left(G+\rho\mathbf{H}^{\frac{1}{2}}(x)\mathbf{H}^{\frac{1}{2}}(x)\right)^{-1}\mathbf{H}^{\frac{1}{2}}(x)\right]\mathbf{H}^{\frac{1}{2}}(x)$
$\displaystyle=\mathbf{H}^{\frac{1}{2}}(x)\left[\rho-\rho\mathbf{H}^{\frac{1}{2}}(x)\left(\frac{1}{\rho}G+\mathbf{H}^{\frac{1}{2}}(x)\mathbf{H}^{\frac{1}{2}}(x)\right)^{-1}\mathbf{H}^{\frac{1}{2}}(x)\right]\mathbf{H}^{\frac{1}{2}}(x)$
$\displaystyle=\mathbf{H}^{\frac{1}{2}}(x)\left[\rho-\rho\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)\right]\mathbf{H}^{\frac{1}{2}}(x)$
$\displaystyle=\rho\mathbf{H}(x)-\rho\mathbf{H}(x)\mathbf{K}(x)\mathbf{H}(x)$
$\displaystyle\overset{\eqref{als:an:15}}{=}\rho\mathbf{H}(x)-\rho\mathbf{H}(x)\mathbf{K}(x)\left[\mathbf{K}^{-1}(x)-\frac{1}{\rho}G\right]=\mathbf{H}(x)\mathbf{K}(x)G=G-\frac{1}{\rho}G\mathbf{K}(x)G.$

With further simplification, we get the second part of Lemma 2.6.

######  Lemma 2.8.

(Lemma 10, [15]) Assume, $N$ is a positive semidefinite matrix and matrix $M$
such that $\textbf{Null}(N)\subset\textbf{Null}(M^{\top})$ holds. Then, we
have the following:

$\textbf{Null}(M)=\textbf{Null}(M^{\top}NM)\quad\text{and}\quad\textbf{Range}(M^{\top})=\textbf{Range}(M^{\top}NM).$

##  3 Lagrangian Penalty Approaches

In this section we introduce the proposed schemes that are constructed based
on Lagrangian penalty methods. To achieve this, let us rewrite the Newton
update provided in (3) as the solution of the following optimization problem:

(16)
$x_{k+1}\in\operatorname*{arg\,min}_{x}\frac{1}{2}\|x-x_{k}\|^{2}_{\mathbf{H}(x_{k})}\quad\textbf{s.t}\quad\mathbf{H}(x_{k})(x-x_{k})=-\frac{1}{L}\nabla
f(x_{k}),$

here, we use $t=1/L$. We interpret the above problem as the projected Newton
system. In the following, we will discuss the proposed variants of the Newton
method that are achieved by incorporating various modern optimization
techniques to the above Newton system.

###  3.1 Penalty Newton Method (PNM)

Our first approach builds on the idea of penalty method that is used
frequently for solving constrained optimization problems. The basic premise of
the PNM algorithm is as follows: we modify the objective function of problem
(16) by adding a penalty term 222For simplicity of exposition, in this work we
consider only quadratic penalty function. to mitigate the constraint
violation, then we solve the resulting unconstrained optimization problem to
find the next update. Our end goal is that by following the above
construction, we can make the algorithm satisfy the equality constraint by
increasing the penalty of not doing that. With the above setup, we get the
following optimization problem:

(17) $\displaystyle
x_{k+1}\in\operatorname*{arg\,min}_{x}\mathcal{L}(x,\rho)\coloneqq\frac{1}{2}\|x-x_{k}\|^{2}_{\mathbf{H}(x_{k})}+\frac{\rho}{2}\big{\|}\mathbf{H}(x_{k})(x-x_{k})+\frac{1}{L}\nabla
f(x_{k})\big{\|}^{2}_{G^{-1}},$

here, $G\succ 0$ is a positive definite matrix. We derive a closed form
solution in the next Lemma.

######  Lemma 3.1.

The following update formula solves the optimization problem of (17):

(18) $\displaystyle
x_{k+1}=x_{k}-\frac{1}{L}\left(\frac{1}{\rho}G+\mathbf{H}(x_{k})\right)^{-1}\nabla
f(x_{k})=x_{k}-\frac{1}{L}\mathbf{K}(x_{k})\nabla f(x_{k}).$

######  Proof 3.2.

Setting $\frac{\partial\mathcal{L}(x,\rho)}{\partial x}=0$, we get

(19) $\displaystyle 0=\frac{\partial\mathcal{L}(x,\rho)}{\partial x}$
$\displaystyle=\left[\mathbf{H}(x_{k})+\rho\
\mathbf{H}(x_{k})G^{-1}\mathbf{H}(x_{k})\right](x-x_{k})+\frac{\rho}{L}\mathbf{H}(x_{k})G^{-1}\nabla
f(x_{k}).$

This is the first order optimality condition of problem (17). Next, we show
that the update formula of (18) satisfies the above optimatliy condition.
Using the update formula, we have the following:

$\displaystyle\left[\mathbf{H}(x_{k})+\rho\mathbf{H}(x_{k})G^{-1}\mathbf{H}(x_{k})\right]$
$\displaystyle(x_{k+1}-x_{k})\overset{\eqref{als:an:19}}{=}-\frac{1}{L}\left[\mathbf{H}(x_{k})+\rho\mathbf{H}(x_{k})G^{-1}\mathbf{H}(x_{k})\right]\mathbf{K}(x_{k})\nabla
f(x_{k})$ $\displaystyle=-$
$\displaystyle\frac{1}{L}\mathbf{H}(x_{k})\mathbf{K}(x_{k})\nabla
f(x_{k})-\frac{\rho}{L}\mathbf{H}(x_{k})G^{-1}\mathbf{H}(x_{k})\mathbf{K}(x_{k})\nabla
f(x_{k})$ $\displaystyle\overset{\eqref{als:an:15}}{=}-$
$\displaystyle\frac{1}{L}\mathbf{H}(x_{k})\mathbf{K}(x_{k})\nabla
f(x_{k})-\frac{\rho}{L}\mathbf{H}(x_{k})G^{-1}\left(I-\frac{1}{\rho}G\mathbf{K}(x_{k})\right)\nabla
f(x_{k})$ (20) $\displaystyle=-$
$\displaystyle\frac{\rho}{L}\mathbf{H}(x_{k})G^{-1}\nabla f(x_{k}).$

Here, we used the identity,
$\mathbf{H}(x_{k})\mathbf{K}(x_{k})=I-\frac{1}{\rho}G\mathbf{K}(x_{k})$ from
Lemma 2.6. Substituting the identity of (3.2) into (19), we deduce that
$x_{k+1}$ satisfies the first order optimality condition. Therefore, we can
say that $x_{k+1}$ provided in (18) is a solution of the optimization problem
(17).

Algorithm 1 $x_{K+1}=\textbf{PNM}(G,c,f(x),K)$

Choose initial points $x_{0}\in\mathbb{R}^{n},\ \rho_{0}\in\mathbb{R}$

while $k\leq K$ do

$x_{k+1}=x_{k}-\frac{1}{L}\left(\frac{1}{\rho_{k}}G+\mathbf{H}(x_{k})\right)^{-1}\nabla
f(x_{k}),\quad\quad\rho_{k+1}=c\rho_{k};$ $k\leftarrow k+1$;

end while

###  3.2 Augmented Newton Method (ANM)

Our second approach uses the idea of the augmented Lagrangian method for
optimization. The method was proposed by Hestenes in 1969 [21] and was
originally called as the method of multipliers (see the works of Powell [36]
and Bertsekas [6] for a detailed discussion). The basic premise of the ANM
algorithm is as follows: we solve problem (16) by the augmented Lagrangian
method, unlike the penalty method here we update the dual solution $z$ as an
estimator of Lagrange multiplier. The major advantage of this approach is that
it is not required to make $\rho\rightarrow\infty$ like we did in the penalty
method. Instead, we update the corresponding dual solution at each iteration
that compensates the smaller penalty. Considering the above framework, we
reformulate problem (16) using augmented Lagrangian penalty function as
follows:

$\displaystyle x_{k+1}\in$
$\displaystyle\operatorname*{arg\,min}_{x}\frac{1}{2}\|x-x_{k}\|^{2}_{\mathbf{H}(x_{k})}+\frac{\rho}{2}\Big{\|}\mathbf{H}(x_{k})(x-x_{k})+\frac{1}{L}\nabla
f(x_{k})\Big{\|}^{2}_{G^{-1}}$ (21)
$\displaystyle\quad\qquad\qquad\textbf{subject
to}\qquad\mathbf{H}(x_{k})(x-x_{k})+\frac{1}{L}\nabla f(x_{k})=0.$

The Lagrangian of the above problem is given by

$\displaystyle\mathcal{L}(x,z,\rho)=\frac{1}{2}\|x-x_{k}\|^{2}_{\mathbf{H}(x_{k})}$
$\displaystyle+z^{\top}\left[\mathbf{H}(x_{k})(x-x_{k})+\frac{1}{L}\nabla
f(x_{k})\right]$ (22)
$\displaystyle+\frac{\rho}{2}\Big{\|}\mathbf{H}(x_{k})(x-x_{k})+\frac{1}{L}\nabla
f(x_{k})\Big{\|}^{2}_{G^{-1}}.$

Then, we set the ANM update formulas as follows:

(23) $\displaystyle
x_{k+1}\in\operatorname*{arg\,min}_{x}\mathcal{L}(x,z_{k},\rho),\quad
z_{k+1}=z_{k}+\rho\
G^{-1}\left[\mathbf{H}(x_{k})(x_{k+1}-x_{k})+\frac{1}{L}\nabla
f(x_{k})\right].$

Algorithm 2 $x_{K+1}=\textbf{ANM}(G,c,f(x),K)$

Choose initial points $x_{0},x_{1}\in\mathbb{R}^{n},\ \rho_{0}\in\mathbb{R}$

while $k\leq K$ do

$x_{k+1}=x_{k}-\left(\frac{1}{\rho_{k}}G+\mathbf{H}(x_{k})\right)^{-1}\left[\frac{1}{L}\nabla
f(x_{k})-\frac{1}{\rho_{k}}G(x_{k}-x_{k-1})\right],\quad\rho_{k+1}=c\rho_{k};$
$k\leftarrow k+1$;

end while

######  Lemma 3.3.

Denote, $u(x_{k},z_{k})=\frac{\rho}{L}\nabla f(x_{k})+Gz_{k}$. Then, the
following update formulas solve the Lagrangian system of (23):

(24) $x_{k+1}=x_{k}-\frac{1}{\rho}\mathbf{K}(x_{k})\
u(x_{k},z_{k})=x_{k}-z_{k+1},\quad z_{k+1}=\frac{1}{\rho}\mathbf{K}(x_{k})\
u(x_{k},z_{k}).$

Moreover, the following update solves the Lagrangian system of (23):

(25) $\displaystyle x_{k+1}$
$\displaystyle=x_{k}-\left(\frac{1}{\rho}G+\mathbf{H}(x_{k})\right)^{-1}\left[\frac{1}{L}\nabla
f(x_{k})-\frac{1}{\rho}G(x_{k}-x_{k-1})\right].$

######  Proof 3.4.

Setting $\frac{\partial\mathcal{L}(x,z_{k},\rho)}{\partial x}=0$, we get

(26) $\displaystyle 0=\frac{\partial\mathcal{L}(x,z_{k},\rho)}{\partial x}$
$\displaystyle=\left[\mathbf{H}(x_{k})+\rho\mathbf{H}(x_{k})G^{-1}\mathbf{H}(x_{k})\right](x-x_{k})+\mathbf{H}(x_{k})\left(\frac{\rho}{L}G^{-1}\nabla
f(x_{k})+z_{k}\right).$

Using the value of $x_{k+1}$ from (24) in place of $x$, we get the following:

$\displaystyle\left[\mathbf{H}(x_{k})+\rho\mathbf{H}(x_{k})G^{-1}\mathbf{H}(x_{k})\right]$
$\displaystyle(x_{k+1}-x_{k})\overset{\eqref{als:an:25}}{=}-\frac{1}{\rho}\left[\mathbf{H}(x_{k})+\rho\mathbf{H}(x_{k})G^{-1}\mathbf{H}(x_{k})\right]\mathbf{K}(x_{k})u(x_{k},z_{k})$
$\displaystyle\overset{\eqref{als:an:15}}{=}-\frac{1}{\rho}\mathbf{H}(x_{k})\mathbf{K}(x_{k})u(x_{k})-\mathbf{H}(x_{k})G^{-1}\left(I-\frac{1}{\rho}G\mathbf{K}(x_{k})\right)u(x_{k},z_{k})$
(27) $\displaystyle=-\mathbf{H}(x_{k})\left(\frac{\rho}{L}G^{-1}\nabla
f(x_{k})+z_{k}\right).$

Substituting the expression in (26), we get that $x_{k+1}$ satisfies the
equation (26). Now, from the definition of $z_{k+1}$, we have

$\displaystyle z_{k+1}$ $\displaystyle\overset{\eqref{als:an:24}}{=}z_{k}+\rho
G^{-1}\left[\mathbf{H}(x_{k})(x_{k+1}-x_{k})+\frac{1}{L}\nabla
f(x_{k})\right]$ $\displaystyle\overset{\eqref{als:an:25}}{=}z_{k}+\rho
G^{-1}\left[-\frac{1}{\rho}\mathbf{H}(x_{k})\mathbf{K}(x_{k})u(x_{k},z_{k})+\frac{1}{L}\nabla
f(x_{k})\right]$
$\displaystyle\overset{\eqref{als:an:15}}{=}z_{k}+\frac{\rho}{L}G^{-1}\nabla
f(x_{k})-G^{-1}\left(I-\frac{1}{\rho}G\mathbf{K}(x_{k})\right)u(x_{k},z_{k})=\frac{1}{\rho}\mathbf{K}(x_{k})\
u(x_{k},z_{k}).$

That is precisely the expression provided in (24). This proves the first part
of the Lemma. To prove the second part, we will simplify the update formula
further by cancelling the $z$ variables from the update formulas. Since,
$z_{k+1}=x_{k}-x_{k+1}$ and $z_{k}=x_{k-1}-x_{k}$, we can combine the update
formulas as follows:

$\displaystyle x_{k+1}\overset{\eqref{als:an:24}}{=}$ $\displaystyle
x_{k}-\left(\frac{1}{\rho}G+\mathbf{H}(x_{k})\right)^{-1}\left[\frac{1}{L}\nabla
f(x_{k})+\frac{1}{\rho}Gz_{k}\right]$ (28) $\displaystyle=\ $ $\displaystyle\
x_{k}-\left(\frac{1}{\rho}G+\mathbf{H}(x_{k})\right)^{-1}\left[\frac{1}{L}\nabla
f(x_{k})-\frac{1}{\rho}G(x_{k}-x_{k-1})\right].$

This proves the second part.

###  3.3 Special Cases

In this subsection, we discuss some special cases that can be obtained from
the proposed PNM and ANM algorithms by varying parameters $G$ and $\rho$.

#### Newton Method

By taking $\rho\rightarrow\infty$ in both the PNM and ANM algorithms, we get
the Newton method. In the following Lemma, we provide a detailed discussion
about the transformation.

######  Lemma 3.5.

In the limiting case, both PNM and ANM resolves into the Newton method, i.e.,
$\lim_{\rho\rightarrow\infty}\text{PNM}\equiv\lim_{\rho\rightarrow\infty}\text{ANM}\equiv\text{NM}$.

######  Proof 3.6.

From the update formula of the PNM method, we have

$\displaystyle\lim_{\rho\rightarrow\infty}x_{k+1}$
$\displaystyle\overset{\eqref{als:an:19}}{=}x_{k}-\frac{1}{L}\lim_{\rho\rightarrow\infty}\mathbf{K}(x_{k})\nabla
f(x_{k})$ (29) $\displaystyle\overset{\text{Assumption}\
\ref{als:an:a:2}}{=}x_{k}-\frac{1}{L}\lim_{\rho\rightarrow\infty}\mathbf{K}(x_{k})\mathbf{H}^{\frac{1}{2}}(x_{k})\mathbf{H}^{\dagger/2}(x_{k})\nabla
f(x_{k}).$

In the last line, we used Assumption 2. Denote,
$Y_{k}=\mathbf{H}^{\frac{1}{2}}(x_{k})G^{-\frac{1}{2}}$, then we have

$\displaystyle\lim_{\rho\rightarrow\infty}x_{k+1}$
$\displaystyle\overset{\eqref{als:an:30}}{=}x_{k}-\frac{1}{L}G^{-\frac{1}{2}}\lim_{\rho\rightarrow\infty}\left(\frac{1}{\rho}I+Y_{k}^{\top}Y_{k}\right)^{-1}Y^{\top}_{k}\mathbf{H}^{\dagger/2}(x_{k})\nabla
f(x_{k})$
$\displaystyle\overset{\eqref{als:an:310}}{=}x_{k}-\frac{1}{L}G^{-\frac{1}{2}}Y^{\dagger}_{k}\mathbf{H}^{\dagger/2}(x_{k})\nabla
f(x_{k})\overset{\eqref{als:an:310}}{=}x_{k}-\frac{1}{L}G^{-\frac{1}{2}}(Y^{\top}_{k}Y_{k})^{\dagger}Y^{\top}_{k}\mathbf{H}^{\dagger/2}(x_{k})\nabla
f(x_{k})$
$\displaystyle=x_{k}-\frac{1}{L}G^{\frac{1}{2}}\left(G^{\frac{1}{2}}\mathbf{H}(x_{k})G^{\frac{1}{2}}\right)^{\dagger}G^{\frac{1}{2}}\mathbf{H}^{\frac{1}{2}}(x_{k})\mathbf{H}^{\dagger/2}(x_{k})\nabla
f(x_{k})$ (30) $\displaystyle\overset{\text{Assumption}\
\ref{als:an:a:2}}{=}x_{k}-\frac{1}{L}\mathbf{H}^{\dagger}(x_{k})\nabla
f(x_{k}).$

Here, we used Assumption 2 along with the following identities of matrix
pseudo-inverse:

(31)
$Y^{\dagger}_{k}=(Y_{k}^{\top}Y_{k})^{\dagger}Y_{k}^{\top}=\lim_{\rho\rightarrow\infty}\left(\frac{1}{\rho}I+Y^{\top}_{k}Y_{k}\right)^{-1}Y_{k}^{\top}.$

The update formula of (3.6) is precisely the update formula of the Newton
method. Moreover, from the update formula of the ANM method, we get,

(32) $\displaystyle\lim_{\rho\rightarrow\infty}x_{k+1}$
$\displaystyle\overset{\eqref{als:an:29}}{=}x_{k}-\lim_{\rho\rightarrow\infty}\mathbf{K}(x_{k})\left[\frac{1}{L}\nabla
f(x_{k})-\frac{1}{\rho}G(x_{k}-x_{k-1})\right]=x_{k}-\frac{1}{L}\lim_{\rho\rightarrow\infty}\mathbf{K}(x_{k})\nabla
f(x_{k}).$

Here we used the limit $\lim_{\rho\rightarrow\infty}\left[\frac{1}{L}\nabla
f(x_{k})-\frac{1}{\rho}G(x_{k}-x_{k-1})\right]=\frac{1}{L}\nabla f(x_{k})$.
This means the $x$ update sequences of the two methods are same in the
limiting case. This proves the Lemma.

#### Levenberg $\&$ Augmented Levenberg Algorithms

With the choice $G=I$, the PNM algorithm resolves into the original Levenberg
algorithm, i.e.,

(33) $\displaystyle x_{k+1}$
$\displaystyle\overset{\eqref{als:an:19}}{=}x_{k}-\frac{1}{L}\left(\frac{1}{\rho}I+\mathbf{H}(x_{k})\right)^{-1}\nabla
f(x_{k}).$

Similarly, substituting $G=I$ in the ANM algorithm, we get the following
update:

(34) $\displaystyle x_{k+1}$
$\displaystyle\overset{\eqref{als:an:29}}{=}x_{k}-\frac{1}{L}\left(\frac{1}{\rho}I+\mathbf{H}(x_{k})\right)^{-1}\nabla
f(x_{k})+\frac{1}{\rho}\left(\frac{1}{\rho}I+\mathbf{H}(x_{k})\right)^{-1}(x_{k}-x_{k-1}).$

We refer to the above method as the Augmented Levenberg algorithm.

#### Levenberg-Marquardt $\&$ Augmented Levenberg-Marquardt Algorithms

With the choice $G=\textbf{diag}(\mathbf{H}(x_{k}))$ in the PNM algorithm we
get the following update:

(35) $\displaystyle x_{k+1}$
$\displaystyle\overset{\eqref{als:an:19}}{=}x_{k}-\frac{1}{L}\left(\frac{1}{\rho}\textbf{diag}(\mathbf{H}(x_{k}))+\mathbf{H}(x_{k})\right)^{-1}\nabla
f(x_{k}).$

This is precisely the Levenberg-Marquardt variant of the Newton method.
Similarly, substituting $G=\textbf{diag}(\mathbf{H}(x_{k}))$ in the ANM
algorithm, we get the following update:

(36) $\displaystyle x_{k+1}$
$\displaystyle\overset{\eqref{als:an:29}}{=}x_{k}-\frac{1}{L}\left(\frac{1}{\rho}\mathbf{D}_{k}+\mathbf{H}(x_{k})\right)^{-1}\nabla
f(x_{k})+\frac{1}{\rho}\left(\frac{1}{\rho}\mathbf{D}_{k}+\mathbf{H}(x_{k})\right)^{-1}\mathbf{D}_{k}(x_{k}-x_{k-1}).$

here, we denote $\mathbf{D}_{k}=\textbf{diag}(\mathbf{H}(x_{k}))$. We refer to
the above method as the Augmented Levenberg-Marquardt algorithm. Using the
above parameter values in Theorems 4.9 and 4.11, we get the respective
convergence results of the above-mentioned methods.

#### Newton Method With Momentum

Next, we discuss the ANM algorithm from a heavy ball/Polyak momentum
perspective. Note that, from the simplified update formula of the ANM
algorithm provided in (3.4), we get

$\displaystyle x_{k+1}$
$\displaystyle\overset{\eqref{als:an:29}}{=}x_{k}-\frac{1}{L}\left(\frac{1}{\rho}G+\mathbf{H}(x_{k})\right)^{-1}\nabla
f(x_{k})+\frac{1}{\rho}\left(\frac{1}{\rho}G+\mathbf{H}(x_{k})\right)^{-1}G(x_{k}-x_{k-1})$
(37)
$\displaystyle=x_{k}-\frac{1}{L}\left(\frac{1}{\rho}G+\mathbf{H}(x_{k})\right)^{-1}\nabla
f(x_{k})+\Theta(x_{k})(x_{k}-x_{k-1}).$

The above update can be interpreted as Newton method with adaptive heavy
ball/Polyak momentum with
$\Theta(x_{k})=\frac{1}{\rho}\left(\frac{1}{\rho}G+\mathbf{H}(x_{k})\right)^{-1}G$.
To the best of our knowledge this is the first variant of Newton method that
incorporates the heavy ball/Polyak momentum update to the Newton method.

#### Penalty & Augmented Newton Method for Root Finding

Let’s take the equation $f(x)=0,\ f:\mathbb{R}\rightarrow\mathbb{R}$. Denote
$f^{{}^{\prime}}(x)$ as the function derivative of $f$, then the proposed
methods take the following form:

$\displaystyle\textbf{Penalty Newton: }\quad x_{k+1}=x_{k}-\frac{\rho\
f(x_{k})}{1+\rho\ f^{{}^{\prime}}(x_{k})}$ $\displaystyle\textbf{Augmented
Newton: }\quad x_{k+1}=x_{k}-\frac{\rho\ f(x_{k})}{1+\rho\
f^{{}^{\prime}}(x_{k})}+\frac{x_{k}-x_{k-1}}{1+\rho\ f^{{}^{\prime}}(x_{k})}$

######  Remark 3.7.

Note that in Algorithms 1 and 2, we provided adaptive versions of the above
methods. In that regard, we gradually increase the penalty parameter $\rho$ in
a way such that $\rho_{k}$ grows larger as the iteration progresses. We used
the simplest update possible to achieve this, i.e., $\rho_{k+1}=c\rho_{k}$ and
replace $\rho$ with $\rho_{k}$ is the PNM and ANM methods.

##  4 Main Results

We now present the convergence results for the proposed variants of Newton
method. In brief, for the PNM algorithm we show that $f(x_{k})\rightarrow
f^{*}$ holds and for the ANM method we show that both $f(x_{k})\rightarrow
f^{*}$ and $\|x_{k}-x_{k-1}\|^{2}_{G}\rightarrow 0$ hold. To achieve this we
define the following sequence:

(38)
$\displaystyle\mathcal{V}_{k}(\rho)=f(x_{k})-f(x^{*})+\frac{L}{2\rho}\|x_{k}-x_{k-1}\|^{2}_{G},$

for any $k\geq 1$, and $\rho>0$. We will show that for the ANM algorithm,
$\mathcal{V}_{k}(\rho)$ is a Lyapunov function. Before we delved into the
convergence results, let us provide some technical Lemmas that are crucial to
the convergence analysis. First, define the following constant:

(39)
$\displaystyle\xi(x)=\min_{v\in\textbf{Range}(\mathbf{H}(x))}\frac{\langle\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)v,v\rangle}{\|v\|^{2}},\quad\
\xi=\min_{x\in\mathcal{Q}_{\rho}}\xi(x).$

Constant $\xi(x)$ can be interpreted as the condition number of matrix
$\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)$.

######  Lemma 4.1.

For any $x\in\mathbb{R}^{n}$, matrices
$\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)$ and
$G^{-\frac{1}{2}}\mathbf{L}(x)G^{-\frac{1}{2}}$ have the same nonzero
eigenvalues, i.e.,
$\lambda_{i}^{+}\left(\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)\right)=\lambda_{i}^{+}\left(G^{-\frac{1}{2}}\mathbf{L}(x)G^{-\frac{1}{2}}\right)$.

######  Proof 4.2.

Let, $Y=\mathbf{H}^{\frac{1}{2}}(x)G^{-\frac{1}{2}}$. Assume $Y$ has the
following singular value decomposition, i.e., $Y=U\Sigma V^{\top}$. Then we
have the following simplifications:

(40)
$\displaystyle\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)$
$\displaystyle\overset{\eqref{als:an:4}}{=}Y\left(\frac{1}{\rho}I+Y^{\top}Y\right)^{-1}Y^{\top}=U\Sigma\left(\frac{1}{\rho}I+\Sigma^{\top}\Sigma\right)^{-1}\Sigma^{\top}U^{\top},$
(41) $\displaystyle G^{-\frac{1}{2}}\mathbf{L}(x)G^{-\frac{1}{2}}$
$\displaystyle\overset{\eqref{als:an:4}}{=}Y^{\top}\left(\frac{1}{\rho}I+YY^{\top}\right)^{-1}Y=V\Sigma^{\top}\left(\frac{1}{\rho}I+\Sigma\Sigma^{\top}\right)^{-1}\Sigma
V^{\top}.$

Since, $U$ and $V$ are orthogonal matrices from the above expressions we get
the following:

(42)
$\displaystyle\lambda_{i}^{+}\left(\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)\right)\overset{\eqref{als:an:40}}{=}\frac{\rho\lambda^{+}_{i}\left(G^{-\frac{1}{2}}\mathbf{H}(x)G^{-\frac{1}{2}}\right)}{1+\rho\lambda^{+}_{i}\left(G^{-\frac{1}{2}}\mathbf{H}(x)G^{-\frac{1}{2}}\right)}\overset{\eqref{als:an:41}}{=}\lambda_{i}^{+}\left(G^{-\frac{1}{2}}\mathbf{L}(x)G^{-\frac{1}{2}}\right).$

These resolve from the fact that both $U$ and $V$ are orthogonal matrices.
Also, both $\Sigma(1/\rho\ I+\Sigma^{\top}\Sigma)^{-1}\Sigma^{\top}$ and
$\Sigma^{\top}(1/\rho\ I+\Sigma\Sigma^{\top})^{-1}\Sigma$ are diagonal
matrices with
$\frac{\rho\lambda^{+}_{i}\left(Y^{\top}Y\right)}{1+\rho\lambda^{+}_{i}\left(Y^{\top}Y\right)}$
be the nonzero diagonal entries in $i^{th}$ position. This proves the Lemma.

######  Lemma 4.3.

For any $x\in\mathbb{R}^{n}$, the following relation holds:

$\displaystyle\textbf{Range}(\mathbf{H}(x))=\textbf{Range}(\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)),$

that implies the following:

(43)
$\displaystyle\xi(x)=\lambda_{\min}^{+}\left(\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)\right)=\min_{i:\sigma_{i}(x)>0}\frac{\rho\sigma^{2}_{i}(x)}{1+\rho\sigma^{2}_{i}(x)}=\frac{\rho\lambda^{+}_{\min}\left(G^{-\frac{1}{2}}\mathbf{H}(x)G^{-\frac{1}{2}}\right)}{1+\rho\lambda^{+}_{\min}\left(G^{-\frac{1}{2}}\mathbf{H}(x)G^{-\frac{1}{2}}\right)},$

where,
$\sigma_{i}(x)=\sqrt{\lambda_{i}\left(\mathbf{H}^{\frac{1}{2}}(x)G^{-1}\mathbf{H}^{\frac{1}{2}}(x)\right)}=\sqrt{\lambda_{i}\left(G^{-\frac{1}{2}}\mathbf{H}(x)G^{-\frac{1}{2}}\right)}$.

######  Proof 4.4.

Since, $\mathbf{K}(x)\succ 0$, we have the following relation:

(44)
$\displaystyle\textbf{Null}(\mathbf{K}(x))\subset\textbf{Null}(\mathbf{H}(x))=\textbf{Null}(\mathbf{H}^{\frac{1}{2}}(x)).$

Now, applying Lemma 2.8 with $N(x)=\mathbf{K}(x)$ and
$M(x)=\mathbf{H}^{\frac{1}{2}}(x)$, we get the following:

(45)
$\displaystyle\textbf{Range}(\mathbf{H}^{\frac{1}{2}}(x))=\textbf{Range}(\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x))=\textbf{Range}(\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)).$

Then, from the definition of $\xi(x)$, we have

$\displaystyle\xi(x)=$
$\displaystyle\min_{v\in\textbf{Range}(\mathbf{H}(x))}\frac{\langle\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)v,v\rangle}{\|v\|^{2}}$
(46)
$\displaystyle\overset{\eqref{als:an:45}}{=}\min_{v\in\textbf{Range}(\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x))}\frac{\langle\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)v,v\rangle}{\|v\|^{2}}=\lambda_{\min}^{+}\left(\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)\right).$

Considering the singular value decomposition provided in the previous Lemma,
we get the complete result.

######  Lemma 4.5.

Assume, assumption 2 holds. Then for any $x\in\mathbb{R}^{n}$, the following
relation holds:

(47) $\displaystyle\|\nabla f(x)\|^{2}_{\mathbf{K}(x)}\geq\ \xi(x)\ \|\nabla
f(x)\|^{2}_{\mathbf{H}^{\dagger}(x)}\geq\ \xi\ \|\nabla
f(x)\|^{2}_{\mathbf{H}^{\dagger}(x)}.$

######  Proof 4.6.

Since,
$\textbf{Range}(\mathbf{H}(x))=\textbf{Range}(\mathbf{H}^{\frac{1}{2}}(x))$
using the relation $\nabla f(x)\in\textbf{Range}(\mathbf{H}(x))$ (assumption
2), we have the following:

(48) $\displaystyle\mathbf{H}^{\frac{1}{2}}(x)\mathbf{H}^{\dagger/2}(x)\nabla
f(x)=\nabla f(x),$

here, we used the notation $\mathbf{H}^{\dagger/2}(x)$ to denote the quantity
$\left(\mathbf{H}^{\dagger}(x)\right)^{\frac{1}{2}}$. Then using the above
relation, we have

$\displaystyle\nabla f(x)^{\top}\mathbf{K}(x)\nabla f(x)$
$\displaystyle\overset{\eqref{als:an:48}}{=}\nabla
f(x)^{\top}\mathbf{H}^{\dagger/2}(x)\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)\mathbf{H}^{\dagger/2}(x)\nabla
f(x)$ $\displaystyle=\nabla
f(x)^{\top}\mathbf{H}^{\dagger/2}(x)\mathbf{H}^{\frac{1}{2}}(x)\mathbf{K}(x)\mathbf{H}^{\frac{1}{2}}(x)\mathbf{H}^{\dagger/2}(x)\nabla
f(x)$ $\displaystyle\overset{\eqref{als:an:43}}{\geq}\xi(x)\ \|\nabla
f(x)\|^{2}_{\mathbf{H}^{\dagger}(x)}\overset{\eqref{als:an:39}}{\geq}\xi\
\|\nabla f(x)\|^{2}_{\mathbf{H}^{\dagger}(x)},$

here, we used the definition of $\xi(x),\ \xi$ along with the relation
$\mathbf{H}^{\dagger/2}(x)\nabla f(x)\in\textbf{Range}(\mathbf{H}(x))$.

######  Assumption 3.

Let, $x_{k}$ be the random iterate generated by the ANM algorithm and for all
$k\geq 1$, assume one of the following holds:

(49) $\displaystyle\text{Either}\quad\mathbf{H}(x_{k})\succ
0\quad\text{or}\quad G(x_{k}-x_{k-1})\in\textbf{Range}(\mathbf{H}(x_{k})).$

######  Lemma 4.7.

Assume assumption 3 holds. Then we have the following:

(50)
$\displaystyle\|x_{k}-x_{k-1}\|^{2}_{\mathbf{L}(x_{k})}\geq\lambda_{\min}^{+}\left(G^{-\frac{1}{2}}\mathbf{L}(x_{k})G^{-\frac{1}{2}}\right)\|x_{k}-x_{k-1}\|^{2}_{G}=\xi(x_{k})\
\|x_{k}-x_{k-1}\|^{2}_{G}.$

######  Proof 4.8.

First, assume $\mathbf{H}(x_{k})\succ 0$. This implies
$G^{-\frac{1}{2}}\mathbf{L}(x_{k})G^{-\frac{1}{2}}\succ 0$. Since,
$G^{-\frac{1}{2}}\mathbf{L}(x_{k})G^{-\frac{1}{2}}\succ 0$ we have
$\lambda_{\min}\left(G^{-\frac{1}{2}}\mathbf{L}(x_{k})G^{-\frac{1}{2}}\right)=\lambda_{\min}^{+}\left(G^{-\frac{1}{2}}\mathbf{L}(x_{k})G^{-\frac{1}{2}}\right)=\xi(x_{k})$.
Then we have

$\displaystyle\|x_{k}-x_{k-1}\|^{2}_{\mathbf{L}(x_{k})}$
$\displaystyle=(x_{k}-x_{k-1})^{\top}G^{\frac{1}{2}}G^{-\frac{1}{2}}\mathbf{L}(x_{k})G^{-\frac{1}{2}}G^{\frac{1}{2}}(x_{k}-x_{k-1})$
(51)
$\displaystyle\geq\lambda_{\min}\left(G^{-\frac{1}{2}}\mathbf{L}(x_{k})G^{-\frac{1}{2}}\right)\|x_{k}-x_{k-1}\|^{2}_{G}=\xi(x_{k})\|x_{k}-x_{k-1}\|^{2}_{G}.$

Considering the second condition of assumption 3, we have

(52) $\displaystyle
G(x_{k}-x_{k-1})\in\textbf{Range}(\mathbf{H}(x_{k}))=\textbf{Range}(\mathbf{H}^{\frac{1}{2}}(x_{k})).$

As
$\textbf{Null}\left(\left(\frac{1}{\rho}+\mathbf{H}^{\frac{1}{2}}(x_{k})G^{-1}\mathbf{H}^{\frac{1}{2}}(x_{k})\right)^{-1}\right)\subset\textbf{Null}(G^{-\frac{1}{2}}\mathbf{H}^{\frac{1}{2}}(x_{k}))$,
applying Lemma 2.8 with
$N(x_{k})=\left(\frac{1}{\rho}+\mathbf{H}^{\frac{1}{2}}(x_{k})G^{-1}\mathbf{H}^{\frac{1}{2}}(x_{k})\right)^{-1}$
and $M(x_{k})=\mathbf{H}^{\frac{1}{2}}(x_{k})G^{-\frac{1}{2}}$, we get the
following:

(53)
$\displaystyle\textbf{Range}(G^{-\frac{1}{2}}\mathbf{H}^{\frac{1}{2}}(x_{k}))=\textbf{Range}(G^{-\frac{1}{2}}\mathbf{H}^{\frac{1}{2}}(x_{k})N(x_{k})\mathbf{H}^{\frac{1}{2}}(x_{k})G^{-\frac{1}{2}})=\textbf{Range}(G^{-\frac{1}{2}}\mathbf{L}(x_{k})G^{-\frac{1}{2}}).$

This implies

(54) $\displaystyle
G^{\frac{1}{2}}(x_{k}-x_{k-1})\overset{\eqref{als:an:52}}{\in}\textbf{Range}(G^{-\frac{1}{2}}\mathbf{H}^{\frac{1}{2}}(x_{k}))\overset{\eqref{als:an:53}}{=}\textbf{Range}(G^{-\frac{1}{2}}\mathbf{L}(x_{k})G^{-\frac{1}{2}}).$

Using the Courant-Fisher Theorem along with the above relation, we get the
following identity:

$\displaystyle\|x_{k}-x_{k-1}\|^{2}_{\mathbf{L}(x_{k})}$
$\displaystyle=(x_{k}-x_{k-1})^{\top}G^{\frac{1}{2}}G^{-\frac{1}{2}}\mathbf{L}(x_{k})G^{-\frac{1}{2}}G^{\frac{1}{2}}(x_{k}-x_{k-1})$
$\displaystyle\overset{\eqref{als:an:54}}{\geq}\lambda_{\min}^{+}\left(G^{-\frac{1}{2}}\mathbf{L}(x_{k})G^{-\frac{1}{2}}\right)\|x_{k}-x_{k-1}\|^{2}_{G}$
(55) $\displaystyle\overset{\text{Lemma}\
\ref{als:an:lem:10}+\eqref{als:an:39}}{=}\xi(x_{k})\
\|x_{k}-x_{k-1}\|^{2}_{G}.$

Combining (4.8) and (4.8), we get the required result.

######  Theorem 4.9.

Assume, $x_{k}$ are random iterates of the PNM algorithm. Then, the sequences
$x_{k}$ converges and the following identity holds:

(56) $\displaystyle f(x_{k+1})-f^{*}\leq(1-\eta)^{k+1}\ [f(x_{0})-f^{*}],$

here,
$\beta=\min_{x\in\mathcal{Q}_{\rho}}\lambda_{\min}\left(\mathbf{K}^{\frac{1}{2}}(x)G\mathbf{K}^{\frac{1}{2}}(x)\right)$
and $\eta=\frac{\mu\xi(\beta+\rho)}{\rho L}$.

######  Proof 4.10.

Using the update formula of the PNM method provided in (18) along with
assumption 1 we have,

$\displaystyle f(x_{k+1})-f^{*}$
$\displaystyle\overset{\eqref{als:an:7}}{\leq}f(x_{k})-f^{*}+\langle\nabla
f(x_{k}),x_{k+1}-x_{k}\rangle+\frac{L}{2}\|x_{k+1}-x_{k}\|^{2}_{\mathbf{H}(x_{k})}$
$\displaystyle\overset{\eqref{als:an:19}}{=}f(x_{k})-f^{*}-\frac{1}{L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}+\frac{L}{2}\big{\|}\frac{1}{L}\mathbf{K}(x_{k})\nabla
f(x_{k})\big{\|}^{2}_{\mathbf{H}(x_{k})}$
$\displaystyle=f(x_{k})-f^{*}-\frac{1}{L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}+\frac{1}{2L}\nabla
f(x_{k})^{\top}\mathbf{K}(x_{k})\mathbf{H}(x_{k})\mathbf{K}(x_{k})\nabla
f(x_{k})$
$\displaystyle\overset{\eqref{als:an:15}}{=}f(x_{k})-f^{*}-\frac{1}{L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}+\frac{1}{2L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}$
$\displaystyle\qquad\qquad\qquad-\frac{1}{2\rho L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})G\mathbf{K}(x_{k})}$
$\displaystyle=f(x_{k})-f^{*}-\frac{1}{2L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}-\frac{1}{2\rho L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})G\mathbf{K}(x_{k})}$ $\displaystyle\leq
f(x_{k})-f^{*}-\frac{1}{2L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}-\frac{\beta}{2\rho L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}$
$\displaystyle=f(x_{k})-f^{*}-\frac{\beta+\rho}{2\rho L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}$
$\displaystyle\overset{\eqref{als:an:47}}{\leq}f(x_{k})-f^{*}-\frac{\xi(\beta+\rho)}{2\rho
L}\|\nabla f(x_{k})\|^{2}_{\mathbf{H}^{\dagger}(x_{k})}$
$\displaystyle\overset{\eqref{als:an:10}}{\leq}f(x_{k})-f^{*}-\frac{\mu\xi(\beta+\rho)}{\rho
L}[f(x_{k})-f^{*}]$ $\displaystyle=(1-\eta)[f(x_{k})-f^{*}]$ (57)
$\displaystyle\leq(1-\eta)^{k+1}\ [f(x_{0})-f^{*}],$

here,
$\beta=\min_{x\in\mathcal{Q}_{\rho}}\lambda_{\min}\left(\mathbf{K}^{\frac{1}{2}}(x)G\mathbf{K}^{\frac{1}{2}}(x)\right)$
and $\eta=\frac{\mu\xi(\beta+\rho)}{\rho L}$. Unrolling the recurrence, we get
the required result.

######  Theorem 4.11.

Assume, $x_{k}$ is the random iterates of the ANM algorithm. Then, the
sequence $x_{k}$ converges and the following identity holds:

(58)
$\displaystyle\mathcal{V}_{k+1}(\rho)\leq\left(1-\xi\frac{\mu}{L}\right)^{k}\
\mathcal{V}_{1}(\rho).$

######  Proof 4.12.

Using the update formula of the ANM method, we have

From the first identity of assumption 1 we have,

(59) $\displaystyle f(x_{k+1})$
$\displaystyle\overset{\eqref{als:an:7}}{\leq}f(x_{k})+\langle\nabla
f(x_{k}),x_{k+1}-x_{k}\rangle+\frac{L}{2}\|x_{k+1}-x_{k}\|^{2}_{\mathbf{H}(x_{k})}.$

Now, we use the update formula of the ANM algorithm provided in (25) to
simplify the right hand side of (59).Using (25), the second term of (59) can
be simplified as follows:

$\displaystyle\langle\nabla f(x_{k}),x_{k+1}-x_{k}\rangle$
$\displaystyle\overset{\eqref{als:an:26}}{=}-\frac{1}{\rho}\nabla
f(x_{k})^{\top}\mathbf{K}(x_{k})\left[\frac{\rho}{L}\nabla
f(x_{k})-G(x_{k}-x_{k-1})\right]$ (60) $\displaystyle=-\frac{1}{L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}+\frac{1}{\rho}(x_{k}-x_{k-1})^{\top}G\mathbf{K}(x_{k})\nabla
f(x_{k}).$

The third term of (59) can be simplified as follows:

$\displaystyle\frac{L}{2}\|x_{k+1}-x_{k}\|^{2}_{\mathbf{H}(x_{k})}$
$\displaystyle\overset{\eqref{als:an:26}}{=}\frac{L}{2}\big{\|}\frac{1}{L}\mathbf{K}(x_{k})\nabla
f(x_{k})-\frac{1}{\rho}\mathbf{K}(x_{k})G(x_{k}-x_{k-1})\big{\|}^{2}_{\mathbf{H}(x_{k})}$
$\displaystyle=\frac{1}{2L}\|\mathbf{K}(x_{k})\nabla
f(x_{k})\|^{2}_{\mathbf{H}(x_{k})}+\frac{L}{2\rho^{2}}\|\mathbf{K}(x_{k})G(x_{k}-x_{k-1})\|^{2}_{\mathbf{H}(x_{k})}$
$\displaystyle\qquad\qquad-\frac{1}{\rho}\langle G(x_{k}-x_{k-1}),\nabla
f(x_{k})\rangle_{\mathbf{K}(x_{k})\mathbf{H}(x_{k})\mathbf{K}(x_{k})}$
$\displaystyle\overset{\eqref{als:an:15}}{=}\frac{1}{2L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}-\frac{1}{2\rho L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})G\mathbf{K}(x_{k})}$
$\displaystyle+\frac{L}{2\rho^{2}}\|G(x_{k}-x_{k-1})\|^{2}_{\mathbf{K}(x_{k})}-\frac{L}{2\rho^{3}}\|G(x_{k}-x_{k-1})\|^{2}_{\mathbf{K}(x_{k})G\mathbf{K}(x_{k})}$
$\displaystyle-\frac{1}{\rho}(x_{k}-x_{k-1})^{\top}G\mathbf{K}(x_{k})\nabla
f(x_{k})$ (61)
$\displaystyle+\frac{1}{\rho^{2}}(x_{k}-x_{k-1})^{\top}G\mathbf{K}(x_{k})G\mathbf{K}(x_{k})\nabla
f(x_{k}).$

Similarly, we have

$\displaystyle\frac{L}{2\rho}\|x_{k+1}-x_{k}\|^{2}_{G}$
$\displaystyle\overset{\eqref{als:an:26}}{=}\frac{L}{2\rho}\big{\|}\frac{1}{L}\mathbf{K}(x_{k})\nabla
f(x_{k})-\frac{1}{\rho}\mathbf{K}(x_{k})G(x_{k}-x_{k-1})\big{\|}^{2}_{G}$
$\displaystyle=\frac{1}{2\rho L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})G\mathbf{K}(x_{k})}+\frac{L}{2\rho^{3}}\|G(x_{k}-x_{k-1})\|^{2}_{\mathbf{K}(x_{k})G\mathbf{K}(x_{k})}$
(62)
$\displaystyle\qquad\qquad-\frac{1}{\rho^{2}}(x_{k}-x_{k-1})^{\top}G\mathbf{K}(x_{k})G\mathbf{K}(x_{k})\nabla
f(x_{k}).$

Substituting (4.12) and (4.12) back in (59) and using (4.12) we have

$\displaystyle\mathcal{V}_{k+1}(\rho)$
$\displaystyle=f(x_{k+1})-f^{*}+\frac{L}{2\rho}\|x_{k+1}-x_{k}\|^{2}_{G}$
$\displaystyle\leq f(x_{k})-f^{*}+\langle\nabla
f(x_{k}),x_{k+1}-x_{k}\rangle+\frac{L}{2}\|x_{k+1}-x_{k}\|^{2}_{\mathbf{H}(x_{k})}+\frac{L}{2\rho}\|x_{k+1}-x_{k}\|^{2}_{G}$
$\displaystyle\overset{\eqref{als:an:60}+\eqref{als:an:61}+\eqref{als:an:62}}{=}f(x_{k})-f^{*}-\frac{1}{L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}+\cancel{\frac{1}{\rho}(x_{k}-x_{k-1})^{\top}G\mathbf{K}(x_{k})\nabla
f(x_{k})}$ $\displaystyle+\frac{1}{2L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}-\cancel{\frac{1}{2\rho L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})G\mathbf{K}(x_{k})}}$
$\displaystyle-\cancel{\frac{L}{2\rho^{3}}\|G(x_{k}-x_{k-1})\|^{2}_{\mathbf{K}(x_{k})G\mathbf{K}(x_{k})}}+\frac{L}{2\rho^{2}}\|G(x_{k}-x_{k-1})\|^{2}_{\mathbf{K}(x_{k})}$
$\displaystyle-\cancel{\frac{1}{\rho}(x_{k}-x_{k-1})^{\top}G\mathbf{K}(x_{k})\nabla
f(x_{k})}+\cancel{\frac{1}{\rho^{2}}(x_{k}-x_{k-1})^{\top}G\mathbf{K}(x_{k})G\mathbf{K}(x_{k})\nabla
f(x_{k})}$ $\displaystyle+\cancel{\frac{1}{2\rho L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})G\mathbf{K}(x_{k})}}+\cancel{\frac{L}{2\rho^{3}}\|G(x_{k}-x_{k-1})\|^{2}_{\mathbf{K}(x_{k})G\mathbf{K}(x_{k})}}$
$\displaystyle-\cancel{\frac{1}{\rho^{2}}(x_{k}-x_{k-1})^{\top}G\mathbf{K}(x_{k})G\mathbf{K}(x_{k})\nabla
f(x_{k})}$ $\displaystyle\leq f(x_{k})-f^{*}-\frac{1}{2L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}+\frac{L}{2\rho^{2}}\|G(x_{k}-x_{k-1})\|^{2}_{\mathbf{K}(x_{k})}$
$\displaystyle\overset{\eqref{als:an:16}}{\leq}f(x_{k})-f^{*}-\frac{1}{2L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{K}(x_{k})}+\frac{L}{2\rho}\|x_{k}-x_{k-1}\|^{2}_{G}-\frac{L}{2\rho}\|x_{k}-x_{k-1}\|^{2}_{\mathbf{L}(x_{k})}$
$\displaystyle\overset{\eqref{als:an:47}+\eqref{als:an:50}}{\leq}\mathcal{V}_{k}(\rho)-\frac{\xi(x_{k})}{2L}\|\nabla
f(x_{k})\|^{2}_{\mathbf{H}^{\dagger}(x_{k})}-\frac{\xi(x_{k})L}{2\rho}\|x_{k}-x_{k-1}\|^{2}_{G}$
$\displaystyle\overset{\eqref{als:an:10}}{\leq}\mathcal{V}_{k}(\rho)-\frac{\mu\xi(x_{k})}{L}\left[f(x_{k})-f^{*}\right]-\frac{\xi(x_{k})L}{2\rho}\|x_{k}-x_{k-1}\|^{2}_{G}$
$\displaystyle\overset{\eqref{als:an:39}}{\leq}\mathcal{V}_{k}(\rho)-\frac{\mu\xi}{L}\left[f(x_{k})-f^{*}\right]-\frac{\xi
L}{2\rho}\|x_{k}-x_{k-1}\|^{2}_{G}$ $\displaystyle\leq(1-\theta)\
\mathcal{V}_{k}(\rho)$ $\displaystyle=\left(1-\xi\frac{\mu}{L}\right)\
\mathcal{V}_{k}(\rho)$ (63)
$\displaystyle\leq\left(1-\xi\frac{\mu}{L}\right)^{k}\ \mathcal{V}_{1}(\rho),$

where, $\theta=\xi\min\\{1,\frac{\mu}{L}\\}=\xi\frac{\mu}{L}$. This proves the
Theorem.

##  5 Conclusion

In this work, we proposed two variants of the Newton method for solving the
unconstrained minimization problem. Our proposed approach incorporates the
penalty method and augmented Lagrangian techniques to the Newton system. We
provided convergence results of the proposed method under mild conditions
imposed on the function $f(x)$. The proposed penalty Newton method generalizes
the so-called Levenberg and Levenberg-Marquardt algorithm into one framework.
The proposed algorithms outperform the existing Newton method on various test
instances. Building on our work one can design penalty and augmented variants
of the so-called Randomized Subspace Newton (RSN) method proposed in [15].

## Acknowledgements

The Author would like thank Rober M. Gower for his thoughtful comments on an
earlier version of the manuscript.

## References

  * [1] 2\. Self-Concordant Functions and Newton Method, pp. 11–55, https://doi.org/10.1137/1.9781611970791.ch2, https://epubs.siam.org/doi/abs/10.1137/1.9781611970791.ch2, https://arxiv.org/abs/https://epubs.siam.org/doi/pdf/10.1137/1.9781611970791.ch2.
  * [2] F. Bach, Self-concordant analysis for logistic regression, Electronic Journal of Statistics, 4 (2010), pp. 384 – 414, https://doi.org/10.1214/09-EJS521, https://doi.org/10.1214/09-EJS521.
  * [3] F. Bach, Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression, Journal of Machine Learning Research, 15 (2014), pp. 595–627, http://jmlr.org/papers/v15/bach14a.html.
  * [4] F. Bach and E. Moulines, Non-strongly-convex smooth stochastic approximation with convergence rate o(1/n), in Advances in Neural Information Processing Systems, C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, eds., vol. 26, Curran Associates, Inc., 2013, https://proceedings.neurips.cc/paper/2013/file/7fe1f8abaad094e0b5cb1b01d712f708-Paper.pdf.
  * [5] A. A. Bennett, Newton’s method in general analysis, Proceedings of the National Academy of Sciences, 2 (1916), pp. 592–598, https://doi.org/10.1073/pnas.2.10.592, https://www.pnas.org/content/2/10/592, https://arxiv.org/abs/https://www.pnas.org/content/2/10/592.full.pdf.
  * [6] D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods (Optimization and Neural Computation Series), Athena Scientific, 1 ed., 1996.
  * [7] R. H. Byrd, G. M. Chin, W. Neveitt, and J. Nocedal, On the use of stochastic hessian information in optimization methods for machine learning, SIAM Journal on Optimization, 21 (2011), pp. 977–995, https://doi.org/10.1137/10079923X, https://doi.org/10.1137/10079923X, https://arxiv.org/abs/https://doi.org/10.1137/10079923X.
  * [8] F. Cajori, Historical note on the newton-raphson method of approximation, The American Mathematical Monthly, 18 (1911), pp. 29–32, http://www.jstor.org/stable/2973939.
  * [9] C. Cartis, N. I. M. Gould, and P. L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. part i: motivation, convergence and numerical results, Mathematical Programming, 127 (2011), pp. 245–295, https://doi.org/10.1007/s10107-009-0286-5, https://doi.org/10.1007/s10107-009-0286-5.
  * [10] C. Cartis, N. I. M. Gould, and P. L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. part ii: worst-case function- and derivative-evaluation complexity, Mathematical Programming, 130 (2011), pp. 295–319, https://doi.org/10.1007/s10107-009-0337-y, https://doi.org/10.1007/s10107-009-0337-y.
  * [11] C. Cartis and K. Scheinberg, Global convergence rate analysis of unconstrained optimization methods based on probabilistic models, Mathematical Programming, 169 (2018), pp. 337–375, https://doi.org/10.1007/s10107-017-1137-4, https://doi.org/10.1007/s10107-017-1137-4.
  * [12] N. Doikov and Y. Nesterov, Minimizing uniformly convex functions by cubic regularization of newton method, 2019, https://arxiv.org/abs/1905.02671.
  * [13] N. Doikov and P. Richtárik, Randomized block cubic newton method, in Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, J. G. Dy and A. Krause, eds., vol. 80 of Proceedings of Machine Learning Research, PMLR, 2018, pp. 1289–1297, http://proceedings.mlr.press/v80/doikov18a.html.
  * [14] M. A. Erdogdu and A. Montanari, Convergence rates of sub-sampled newton methods, in Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2, NIPS’15, Cambridge, MA, USA, 2015, MIT Press, p. 3052–3060.
  * [15] R. Gower, D. Kovalev, F. Lieder, and P. Richtarik, Rsn: Randomized subspace newton, in Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché Buc, E. Fox, and R. Garnett, eds., vol. 32, Curran Associates, Inc., 2019, pp. 616–625, https://proceedings.neurips.cc/paper/2019/file/bc6dc48b743dc5d013b1abaebd2faed2-Paper.pdf.
  * [16] G. N. Grapiglia and Y. Nesterov, Regularized newton methods for minimizing functions with hölder continuous hessians, SIAM Journal on Optimization, 27 (2017), pp. 478–506, https://doi.org/10.1137/16M1087801, https://doi.org/10.1137/16M1087801, https://arxiv.org/abs/https://doi.org/10.1137/16M1087801.
  * [17] G. N. Grapiglia and Y. Nesterov, Accelerated regularized newton methods for minimizing composite convex functions, SIAM Journal on Optimization, 29 (2019), pp. 77–99, https://doi.org/10.1137/17M1142077, https://doi.org/10.1137/17M1142077, https://arxiv.org/abs/https://doi.org/10.1137/17M1142077.
  * [18] M. Gürbüzbalaban, A. Ozdaglar, and P. Parrilo, A globally convergent incremental newton method, Mathematical Programming, 151 (2015), pp. 283–313, https://doi.org/10.1007/s10107-015-0897-y, https://doi.org/10.1007/s10107-015-0897-y.
  * [19] F. Hanzely, N. Doikov, Y. Nesterov, and P. Richtarik, Stochastic subspace cubic Newton method, in Proceedings of the 37th International Conference on Machine Learning, H. D. III and A. Singh, eds., vol. 119 of Proceedings of Machine Learning Research, PMLR, 13–18 Jul 2020, pp. 4027–4038, http://proceedings.mlr.press/v119/hanzely20a.html.
  * [20] H. V. Henderson and S. R. Searle, On deriving the inverse of a sum of matrices, SIAM Review, 23 (1981), pp. 53–60, https://doi.org/10.1137/1023004, https://doi.org/10.1137/1023004, https://arxiv.org/abs/https://doi.org/10.1137/1023004.
  * [21] M. R. Hestenes, Multiplier and gradient methods, Journal of Optimization Theory and Applications, 4 (1969), pp. 303–320, https://doi.org/10.1007/BF00927673, https://doi.org/10.1007/BF00927673.
  * [22] L. V. Kantorovich, Functional analysis and applied mathematics, Usp. Mat. Nauk, 3 (1948), pp. 89–185.
  * [23] L. Kantorovitch, The method of successive approximation for functional equations, Acta Mathematica, 71 (1939), pp. 63 – 97, https://doi.org/10.1007/BF02547750, https://doi.org/10.1007/BF02547750.
  * [24] S. P. Karimireddy, S. U. Stich, and M. Jaggi, Global linear convergence of newton’s method without strong-convexity or lipschitz gradients, 2018, https://arxiv.org/abs/1806.00413.
  * [25] J. M. Kohler and A. Lucchi, Sub-sampled cubic regularization for non-convex optimization, in Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, JMLR.org, 2017, p. 1895–1904.
  * [26] N. Kollerstrom, Thomas simpson and ’newton’s method of approximation’: An enduring myth, The British Journal for the History of Science, 25 (1992), pp. 347–354, http://www.jstor.org/stable/4027257.
  * [27] D. Kovalev, K. Mishchenko, and P. Richtárik, Stochastic newton and cubic newton methods with simple local linear-quadratic rates, 2019, https://arxiv.org/abs/1912.01597.
  * [28] C.-p. Lee and S. J. Wright, Inexact successive quadratic approximation for regularized optimization, Computational Optimization and Applications, 72 (2019), pp. 641–674, https://doi.org/10.1007/s10589-019-00059-z, https://doi.org/10.1007/s10589-019-00059-z.
  * [29] R. D. C. Monteiro and B. F. Svaiter, An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods, SIAM Journal on Optimization, 23 (2013), pp. 1092–1125, https://doi.org/10.1137/110833786, https://doi.org/10.1137/110833786, https://arxiv.org/abs/https://doi.org/10.1137/110833786.
  * [30] M. S. Morshed, Penalty & augmented kaczmarz methods for linear systems & linear feasibility problems, 2022, https://doi.org/10.48550/ARXIV.2205.08085, https://arxiv.org/abs/2205.08085.
  * [31] Y. Nesterov, Accelerating the cubic regularization of newton’s method on convex problems, Mathematical Programming, 112 (2008), pp. 159–181, https://doi.org/10.1007/s10107-006-0089-x, https://doi.org/10.1007/s10107-006-0089-x.
  * [32] Y. Nesterov and B. T. Polyak, Cubic regularization of newton method and its global performance, Mathematical Programming, 108 (2006), pp. 177–205, https://doi.org/10.1007/s10107-006-0706-8, https://doi.org/10.1007/s10107-006-0706-8.
  * [33] J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Society for Industrial and Applied Mathematics, 2000, https://doi.org/10.1137/1.9780898719468, https://epubs.siam.org/doi/abs/10.1137/1.9780898719468, https://arxiv.org/abs/https://epubs.siam.org/doi/pdf/10.1137/1.9780898719468.
  * [34] M. Pilanci and M. J. Wainwright, Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence, SIAM Journal on Optimization, 27 (2017), pp. 205–245, https://doi.org/10.1137/15M1021106, https://doi.org/10.1137/15M1021106, https://arxiv.org/abs/https://doi.org/10.1137/15M1021106.
  * [35] B. T. Polyak, Newton-kantorovich method and its global convergence, Journal of Mathematical Sciences, 133 (2006), pp. 1513–1523, https://doi.org/10.1007/s10958-006-0066-1, https://doi.org/10.1007/s10958-006-0066-1.
  * [36] M. J. D. POWELL, A method for nonlinear constraints in minimization problems, Optimization, (1969), pp. 283–298, https://ci.nii.ac.jp/naid/20000922074/en/.
  * [37] Z. Qu, P. Richtarik, M. Takac, and O. Fercoq, SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization, in Proceedings of The 33rd International Conference on Machine Learning, vol. 48, New York, USA, 20–22 Jun 2016, PMLR, pp. 1823–1832, http://proceedings.mlr.press/v48/qub16.html.
  * [38] F. Roosta, Y. Liu, P. Xu, and M. W. Mahoney, Newton-mr: Newton’s method without smoothness or convexity, 2019, https://arxiv.org/abs/1810.00303.
  * [39] F. Roosta-Khorasani and M. W. Mahoney, Sub-sampled newton methods, Mathematical Programming, 174 (2019), pp. 293–326, https://doi.org/10.1007/s10107-018-1346-5, https://doi.org/10.1007/s10107-018-1346-5.
  * [40] K. Scheinberg and X. Tang, Practical inexact proximal quasi-newton method with global complexity analysis, Mathematical Programming, 160 (2016), pp. 495–529, https://doi.org/10.1007/s10107-016-0997-3, https://doi.org/10.1007/s10107-016-0997-3.
  * [41] N. Tripuraneni, M. Stern, C. Jin, J. Regier, and M. I. Jordan, Stochastic cubic regularization for fast nonconvex optimization, in Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, eds., vol. 31, Curran Associates, Inc., 2018, https://proceedings.neurips.cc/paper/2018/file/db1915052d15f7815c8b88e879465a1e-Paper.pdf.
  * [42] Z. Wang, Y. Zhou, Y. Liang, and G. Lan, Stochastic variance-reduced cubic regularization for nonconvex optimization, 2018, https://arxiv.org/abs/1802.07372.
  * [43] P. Xu, F. Roosta, and M. W. Mahoney, Newton-type methods for non-convex optimization under inexact hessian information, Mathematical Programming, 184 (2020), pp. 35–70, https://doi.org/10.1007/s10107-019-01405-z, https://doi.org/10.1007/s10107-019-01405-z.
  * [44] P. Xu, J. Yang, F. Roosta, C. Ré, and M. W. Mahoney, Sub-sampled newton methods with non-uniform sampling, in Advances in Neural Information Processing Systems, D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, eds., vol. 29, Curran Associates, Inc., 2016, https://proceedings.neurips.cc/paper/2016/file/55c567fd4395ecef6d936cf77b8d5b2b-Paper.pdf.
  * [45] T. J. Ypma, Historical development of the newton-raphson method, SIAM Review, 37 (1995), pp. 531–551, http://www.jstor.org/stable/2132904.
  * [46] R. Yuan, A. Lazaric, and R. M. Gower, Sketched newton-raphson, ICML 2020 workshop “Beyond first order methods in ML systems”, (2020), https://arxiv.org/abs/2006.12120.