# Local convergence analysis of inexact Gauss-Newton like
methods under majorant condition

O. P. Ferreira IME/UFG, Campus II- Caixa Postal 131, 74001-970 - Goiânia, GO,
Brazil (E-mail:orizon@mat.ufg.br). The author was partly supported by CNPq
Grant 473756/2009-9, CNPq Grant 302024/2008-5, PRONEX-
Optimization(FAPERJ/CNPq) and FUNAPE/UFG. M. L. N. Gonçalves COPPE-Sistemas,
Universidade Federal do Rio de Janeiro, 21945-970 Rio de Janeiro, RJ, BR
(E-mail:maxlng@cos.ufrj.br). The author was partly supported by CNPq Grant
473756/2009-9. P. R. Oliveira COPPE-Sistemas, Universidade Federal do Rio de
Janeiro, 21945-970 Rio de Janeiro, RJ, BR (Email: poliveir@cos.ufrj.br). This
author was partly supported by CNPq.

###### Abstract

In this paper, we present a local convergence analysis of inexact Gauss-Newton
like methods for solving nonlinear least squares problems. Under the
hypothesis that the derivative of the function associated with the least
square problem satisfies a majorant condition, we obtain that the method is
well-defined and converges. Our analysis provides a clear relationship between
the majorant function and the function associated with the least square
problem. It also allows us to obtain an estimate of convergence ball for
inexact Gauss-Newton like methods and some important, special cases.

Keywords: Nonlinear least squares problems; inexact Gauss-Newton like methods;
Majorant condition; Local convergence.

##  1 Introduction

Let $\mathbb{X}$ and $\mathbb{Y}$ be real or complex Hilbert spaces. Let
$\Omega\subseteq\mathbb{X}$ be an open set, and $F:\Omega\to\mathbb{Y}$ a
continuously differentiable nonlinear function. Consider the following
nonlinear least squares problems

$\min_{x\in\Omega}\;\|F(x)\|^{2}.$ (1)

The interest in this problem arises in data fitting, when
$\mathbb{X}=\mathbb{R}^{n}$ and $\mathbb{Y}=\mathbb{R}^{m}$ and $m$ is the
number of observations and $n$ is the number of parameters, see for example
[13]. A solution $x_{*}\in\Omega$ of (1) is also called a least-squares
solution of nonlinear equation $F(x)=0.$

When $F^{\prime}(x)$ is injective and has closed image for all $x\in\Omega$,
the Gauss-Newton’s method finds stationary points of the above problem.
Formally, the Gauss-Newton’s method is described as follows: Given an initial
point $x_{0}\in\Omega$, define

$x_{k+1}={x_{k}}+S_{k},\qquad
F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})S_{k}=-F^{\prime}(x_{k})^{*}F(x_{k}),\qquad
k=0,1,\ldots,$

where $A^{*}$ denotes the adjoint of the operator $A$. It is worth pointing
out that if $x_{*}$ is solution of (1), $F(x_{*})=0$ and $F^{\prime}(x_{*})$
is invertible, then the theories of the Gauss-Newton’s method merge into the
theories of Newton’s method. Early works dealing with the convergence of
Newton’s and Gauss-Newton’s methods include [1, 2, 3, 6, 8, 9, 10, 11, 14, 16,
17, 19, 20, 21, 24, 25, 28].

The inexact Gauss-Newton process is described as follows: Given an initial
point $x_{0}\in\Omega$, define

$x_{k+1}=x_{k}+S_{k},\qquad{k=0,1,...,}$

where $B_{k}:\mathbb{X}\to\mathbb{Y}$ is a linear operator and $S_{k}$ is any
approximated solution of the linear system

${B_{k}S_{k}=-F^{\prime}(x_{k})^{*}F(x_{k})+r_{k},}$

for a suitable residual $r_{k}\in\mathbb{Y}$. In particular, the above process
is inexact Gauss-Newton method if
$B_{k}=F^{\prime}(x_{k})^{T}F^{\prime}(x_{k}),$ the process is inexact
modified Gauss-Newton method if
$B_{k}=F^{\prime}(x_{0})^{T}F^{\prime}(x_{0}),$ and it represents a inexact
Gauss-Newton like method if $B_{k}$ is an approximation of
$F^{\prime}(x_{k})^{T}F^{\prime}(x_{k}).$

For inexact Newton methods, as shown in [12], if
$\|r_{k}\|\leq\theta_{k}\|F(x_{k})\|$ for $k=0,1,\ldots$ and
$\\{\theta_{k}\\}$ is a sequence of forcing terms such that
$0\leq\theta_{k}<1$ then there exists $\epsilon>0$ such that the sequence
$\\{x_{k}\\}$, for any initial point $x_{0}\in
B(x_{*},\epsilon)=\\{x\in\mathbb{R}^{n}:\;\|x_{*}-x\|<\epsilon\\}$, is well
defined and converges linearly to $x_{*}$ in the norm
$\|y\|_{*}=\|F^{\prime}(x_{*})y\|$, where $\|\;\|$ is any norm in
$\mathbb{R}^{n}$. As pointed out by [22] (see also [23]) the result of [12] is
difficult to apply due to a dependence of the norm $\|\;\|_{*}$, which is not
computable.

Formally, the inexact Gauss-Newton like methods for solving (1), which we will
consider, are described as follows: Given an initial point $x_{0}\in{\Omega}$,
define

$x_{k+1}={x_{k}}+S_{k},\qquad
B(x_{k})S_{k}=-F^{\prime}(x_{k})^{*}F(x_{k})+r_{k},\qquad k=0,1,\ldots,$

where $B(x_{k})$ is a suitable invertible approximation of the derivative
$F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})$ and the residual tolerance $r_{k}$
and the preconditioning invertible matrix $P_{k}$ (considered for the first
time in [23]) for the linear system defining the step $S_{k}$ satisfy

$\|P_{k}r_{k}\|\leq\theta_{k}\|P_{k}F^{\prime}(x_{k})^{*}F(x_{k})\|,$

for suitable forcing number $\theta_{k}$. Note that, if the forcing sequence
vanishes, i.e., $\theta_{k}=0$ for all $k,$ the inexact Gauss-Newton methods
include the class of Gauss-Newton iterative methods. Hence, the theories of
inexact Gauss-Newton methods merge into the theories of Gauss-Newton methods.

The classical local convergence analysis for the inexact Newton’s methods (see
[12, 23]) requires, among other hypotheses, that $F^{\prime}$ satisfies the
Lipschitz condition. In the last years, there have been papers dealing with
the issue of convergence of the Newton method and inexact Newton’s method,
including the Gauss-Newton’s method and inexact Gauss-Newton’s method, by
relaxing the assumption of Lipschitz continuity of the derivative (see for
example: [5, 6, 7, 9, 14, 15, 16, 17, 21, 28]). One of the main conditions
that relaxes the condition of the Lipschitz continuity of the derivative is
the majorant condition, which we will use, and Wang’s condition, introduced in
[28] and used in [5, 6, 7, 8, 20, 21] to study the Gauss-Newton’s and Newton’s
methods. In fact, it can be shown that these conditions are equivalent. But
the formulation as a majorant condition is in some sense better than Wang’s
condition, as it provides a clear relationship between the majorant function
and the nonlinear function under consideration. Besides, the majorant
condition provides a simpler proof of convergence.

In the present paper, we are interested in the local convergence analysis,
i.e., based on the information in a neighbourhood of a stationary point of (1)
we determine the convergence ball of the method. Following the ideas of [14,
15, 16, 17], we will present a new local convergence analysis for inexact
Gauss-Newton like methods under majorant condition. The convergence analysis
presented provides a clear relationship between the majorant function, which
relaxes the Lipschitz continuity of the derivate, and the function associated
with the nonlinear least square problem (see for example: Lemmas 12, 13 and
14). Besides, the results presented here have the conditions and the proof of
convergence in quite a simple manner. Moreover, two unrelated previous results
pertaining to inexact Gauss-Newton like methods are unified, namely, the
result for analytical functions and the classical one for functions with
Lipschitz derivative.

The organization of the paper is as follows. In Section 1.1, we list some
notations and basic results used in our presentation. In Section 2 the main
result is stated, and in Section 2.1 some properties involving the majorant
function are established. In Section 2.2 we present the relationships between
the majorant function and the non-linear function $F$. In Section 2.3 the main
result is proven and some applications of this result are given in Section 3.
Some final remarks are offered in Section 4.

###  1.1 Notation and auxiliary results

The following notations and results are used throughout our presentation. Let
$\mathbb{X}$ and $\mathbb{Y}$ be Hilbert spaces. The open and closed ball at
$a\in\mathbb{X}$ and radius $\delta>0$ are denoted, respectively by

$B(a,\delta):=\\{x\in\mathbb{X};\;\|x-a\|<\delta\\},\qquad
B[a,\delta]:=\\{x\in\mathbb{X};\;\|x-a\|\leqslant\delta\\}.$

The set $\Omega\subseteq\mathbb{X}$ is an open set and the function
$F:\Omega\to\mathbb{Y}$ is continuously differentiable, and $F^{\prime}(x)$
has closed image in $\Omega$.

Let $A:\mathbb{X}\to\mathbb{Y}$ be a continuous and injective linear operator
with closed image. The Moore-Penrose inverse
$A^{\dagger}:\mathbb{Y}\to\mathbb{X}$ of $A$ is defined by

$A^{\dagger}:=(A^{*}A)^{-1}A^{*},$

where $A^{*}$ denotes the adjoint of the linear operator $A$.

######  Lemma 1.

(Banach’s Lemma) Let $B:\mathbb{X}\to\mathbb{X}$ be a continuous linear
operator, and $\mbox{I}:\mathbb{X}\to\mathbb{X}$ the identity operator. If
$\|B-I\|<1$, then $B$ is invertible and $\|B^{-1}\|\leq
1/\left(1-\|B-I\|\right).$

###### Proof.

See the proof of Lemma 1, p. 189 of Smale [26] with $A=I$ and $c=\|B-I\|$. ∎

######  Lemma 2.

Let $A,B:\mathbb{X}\to\mathbb{Y}$ be a continuous linear operator with closed
image. If $A$ is injective, $E=B-A$ and $\|EA^{\dagger}\|<1$, then $B$ is
injective.

###### Proof.

In fact, $B=A+E=(I+EA^{\dagger})A,$ from the condition $\|EA^{\dagger}\|<1,$
we have of Lemma 1 that $I+EA^{\dagger}$ is invertible. So, $B$ is injective.
∎

The next lemma is proven in Stewart [27] ( see also, Wedin [29] ) for $m\times
n$ matrix with $m\geq n$ and $rank(A)=rank(B)=n$, that proof holds in more
general context as we will state below.

######  Lemma 3.

Let $A,B:\mathbb{X}\to\mathbb{Y}$ be continuous and injective linear operators
with closed images. Assume that $E=B-A$ and $\|A^{\dagger}\|\|E\|<1$, then

$\|B^{\dagger}\|\leq\frac{\|A^{\dagger}\|}{1-\|A^{\dagger}\|\|E\|},\qquad\|B^{\dagger}-A^{\dagger}\|\leq\frac{\sqrt{2}\|A^{\dagger}\|^{2}\|E\|}{1-\|A^{\dagger}\|\|E\|}.$

######  Proposition 4.

If $0\leq t<1$, then $\sum_{i=0}^{\infty}(i+2)(i+1)t^{i}=2/(1-t)^{3}.$

###### Proof.

Take $k=2$ in Lemma 3, pp. 161 of Blum, et al. [4]. ∎

Also, the following auxiliary results of elementary convex analysis will be
needed:

######  Proposition 5.

Let $R>0$. If $\varphi:[0,R)\to\mathbb{R}$ is convex, then

$D^{+}\varphi(0)={\lim}_{u\to
0+}\;\frac{\varphi(u)-\varphi(0)}{u}={\inf}_{0<u}\;\frac{\varphi(u)-\varphi(0)}{u}.\\\
$

###### Proof.

See Theorem 4.1.1 on pp. 21 of Hiriart-Urruty and Lemaréchal [18]. ∎

######  Proposition 6.

Let $\epsilon>0$ and $\tau\in[0,1]$. If
$\varphi:[0,\epsilon)\rightarrow\mathbb{R}$ is convex, then
$l:(0,\epsilon)\to\mathbb{R}$ defined by

$l(t)=\frac{\varphi(t)-\varphi(\tau t)}{t},$

is increasing.

###### Proof.

See Theorem 4.1.1 and Remark 4.1.2 on pp. 21 of Hiriart-Urruty and Lemaréchal
[18]. ∎

##  2 Local analysis for inexact Gauss-Newton like methods

In this section, we will state and prove a local theorem for inexact Gauss-
Newton like methods. Assuming that the function

$\Omega\ni x\mapsto F(x)^{*}F(x),$

has a point stationary $x_{*}$, we will, under mild conditions, prove that the
inexact Gauss-Newton like methods is well defined and that the generated
sequence converges linearly to this point stationary. The statement of the
theorem is as follows:

######  Theorem 7.

Let $\Omega\subseteq\mathbb{X}$ be an open set, $F:{\Omega}\to\mathbb{Y}$ a
continuously differentiable function. Let $x_{*}\in\Omega,$ $R>0$ and

$c:=\|F(x_{*})\|,\qquad\beta:=\left\|F^{\prime}(x_{*})^{\dagger}\right\|,\qquad\kappa:=\sup\left\\{t\in[0,R):B(x_{*},t)\subset\Omega\right\\}.$

Suppose that $F^{\prime}(x_{*})^{*}F(x_{*})=0$, $F^{\prime}(x_{*})$ is
injective and there exists a $f:[0,\;R)\to\mathbb{R}$ continuously
differentiable such that

$\left\|F^{\prime}(x)-F^{\prime}(x_{*}+\tau(x-x_{*}))\right\|\leq
f^{\prime}\left(\|x-x_{*}\|\right)-f^{\prime}\left(\tau\|x-x_{*}\|\right),$
(2)

for all $\tau\in[0,1]$, $x\in B(x_{*},\kappa)$ and

  * h1)

$f(0)=0$ and $f^{\prime}(0)=-1$;

  * h2)

$f^{\prime}$ is convex and strictly increasing;

  * h3)

$\alpha:=\sqrt{2}\,c\,\beta^{2}D^{+}f^{\prime}(0)<1$.

Take $0\leq\vartheta<1$, $0\leq\omega_{2}<\omega_{1}$ such that
$\omega_{1}(\alpha+\alpha\vartheta+\vartheta)+\omega_{2}<1$. Let the positive
constants

$\nu:=\sup\left\\{t\in[0,R):\beta[f^{\prime}(t)+1]<1\right\\},$
$\rho:=\sup\bigg{\\{}t\in(0,\nu):(1+\vartheta)\omega_{1}\beta\frac{tf^{\prime}(t)-f(t)+\sqrt{2}c\beta[f^{\prime}(t)+1]}{t[1-\beta(f^{\prime}(t)+1)]}+\omega_{1}\vartheta+\omega_{2}<1\bigg{\\}},\;r:=\min\left\\{\kappa,\,\rho\right\\}.$

Then, the inexact Gauss-Newton like methods for solving (1), with initial
point $x_{0}\in B(x_{*},r)\backslash\\{x_{*}\\}$

$x_{k+1}={x_{k}}+S_{k},\qquad
B(x_{k})S_{k}=-F^{\prime}(x_{k})^{*}F(x_{k})+r_{k},\qquad\;k=0,1,\ldots,$ (3)

for the forcing term $\theta_{k}$ and the following conditions for the
residual $r_{k}$ and the invertible matrix $P_{k}$ preconditioning the linear
system in (3)

$\|P_{k}r_{k}\|\leq\theta_{k}\|P_{k}F^{\prime}(x_{k})^{*}F(x_{k})\|,\qquad
0\leq\theta_{k}\mbox{cond}(P_{k}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k}))\leq\vartheta,\qquad\;k=0,1,\ldots,$

where $B(x_{k})$ is an invertible approximation of
$F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})$ satisfying the following conditions

$\|B(x_{k})^{-1}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})\|\leq\omega_{1},\qquad\|B(x_{k})^{-1}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})-I\|\leq\omega_{2},\qquad\;k=0,1,\ldots,$

is well defined, contained in $B(x_{*},r)$, converges to $x_{*}$ and there
holds

$\|x_{k+1}-x_{*}\|\leq(1+\vartheta)\omega_{1}\beta\frac{[f^{\prime}(\|x_{0}-x_{*}\|)\|x_{0}-x_{*}\|-f(\|x_{0}-x_{*}\|)]}{\|x_{0}-x_{*}\|^{2}[1-\beta(f^{\prime}(\|x_{0}-x_{*}\|)+1)]}{\|x_{k}-x_{*}\|}^{2}\\\
+\left(\frac{(1+\vartheta)\omega_{1}\sqrt{2}c\beta^{2}[f^{\prime}(\|x_{0}-x_{*}\|)+1]}{\|x_{0}-x_{*}\|[1-\beta(f^{\prime}(\|x_{0}-x_{*}\|)+1)]}+\omega_{1}\vartheta+\omega_{2}\right)\|x_{k}-x_{*}\|,\qquad
k=0,1,\ldots.$ (4)

######  Remark 1.

In particular, if taking $\vartheta=0$ (in this case $\theta_{k}\equiv 0$ and
$r_{k}\equiv 0$) in Theorem 7, we obtain the convergence of Gauss-Newton’s
like method under majorant condition which, for $\omega_{1}=1$ and
$\omega_{2}=0$, i.e., $B(x_{k})=F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})$, has
been obtained by Ferreira et al. [16] in Theorem 7. Now, if taking $c=0$ (the
so-called zero-residual case) and $F^{\prime}(x_{*})$ is invertible, we obtain
the convergence of inexact Newton-Like methods under majorant condition, which
has been obtained by Ferreira, Gonçalves [15] in Theorem 4. Finally, if
$c=\vartheta=\omega_{2}=0$, $\omega_{1}=1$ and $F^{\prime}(x_{*})$ is
invertible in Theorem 7, we obtain the convergence of Newton’s method under
majorant condition, which has been obtained by Ferreira [14] in Theorem 2.1.

For the important case $\vartheta=0$, namely, Gauss-Newton’s like method under
majorant condition, the Theorem 7 becomes:

######  Corollary 8.

Let $\Omega\subseteq\mathbb{X}$ be an open set, $F:{\Omega}\to\mathbb{Y}$ a
continuously differentiable function. Let $x_{*}\in\Omega,$ $R>0$ and

$c:=\|F(x_{*})\|,\qquad\beta:=\left\|F^{\prime}(x_{*})^{\dagger}\right\|,\qquad\kappa:=\sup\left\\{t\in[0,R):B(x_{*},t)\subset\Omega\right\\}.$

Suppose that $F^{\prime}(x_{*})^{*}F(x_{*})=0$, $F^{\prime}(x_{*})$ is
injective and there exists a $f:[0,\;R)\to\mathbb{R}$ continuously
differentiable such that

$\left\|F^{\prime}(x)-F^{\prime}(x_{*}+\tau(x-x_{*}))\right\|\leq
f^{\prime}\left(\|x-x_{*}\|\right)-f^{\prime}\left(\tau\|x-x_{*}\|\right),$

for all $\tau\in[0,1]$, $x\in B(x_{*},\kappa)$ and

  * h1)

$f(0)=0$ and $f^{\prime}(0)=-1$;

  * h2)

$f^{\prime}$ is convex and strictly increasing;

  * h3)

$\alpha:=\sqrt{2}\,c\,\beta^{2}D^{+}f^{\prime}(0)<1$.

Take $0\leq\omega_{2}<\omega_{1}$ such that $\omega_{1}\alpha+\omega_{2}<1$.
Let $\nu:=\sup\left\\{t\in[0,R):\beta[f^{\prime}(t)+1]<1\right\\},$

$\rho:=\sup\bigg{\\{}t\in(0,\nu):\omega_{1}\beta\frac{tf^{\prime}(t)-f(t)+\sqrt{2}c\beta[f^{\prime}(t)+1]}{t[1-\beta(f^{\prime}(t)+1)]}+\omega_{2}<1\bigg{\\}},\quad
r:=\min\left\\{\kappa,\,\rho\right\\}.$

Then, the Gauss-Newton’s like method for solving (1), with initial point
$x_{0}\in B(x_{*},r)\backslash\\{x_{*}\\}$

$x_{k+1}={x_{k}}+S_{k},\qquad
B(x_{k})S_{k}=-F^{\prime}(x_{k})^{*}F(x_{k}),\qquad\;k=0,1,\ldots,$

where $B(x_{k})$ is an invertible approximation of
$F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})$ satisfying

$\|B(x_{k})^{-1}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})\|\leq\omega_{1},\qquad\|B(x_{k})^{-1}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})-I\|\leq\omega_{2},\qquad\;k=0,1,\ldots,$

is well defined, contained in $B(x_{*},r)$, converges to $x_{*}$ and there
holds

$\|x_{k+1}-x_{*}\|\leq\omega_{1}\beta\frac{[f^{\prime}(\|x_{0}-x_{*}\|)\|x_{0}-x_{*}\|-f(\|x_{0}-x_{*}\|)]}{\|x_{0}-x_{*}\|^{2}[1-\beta(f^{\prime}(\|x_{0}-x_{*}\|)+1)]}{\|x_{k}-x_{*}\|}^{2}\\\
+\left(\frac{\omega_{1}\sqrt{2}c\beta^{2}[f^{\prime}(\|x_{0}-x_{*}\|)+1]}{\|x_{0}-x_{*}\|[1-\beta(f^{\prime}(\|x_{0}-x_{*}\|)+1)]}+\omega_{2}\right)\|x_{k}-x_{*}\|,\qquad
k=0,1,\ldots.$ (5)

######  Remark 2.

Despite the fact that the above corollary is a special case of Theorem 7, the
results contained therein extend the results of Chen and Li in [8], as the
results obtained [8] are only for the case $c=0.$

######  Remark 3.

Assumption (2) is crucial for our analysis. It should be pointed that, under
appropriate regularity conditions in the nonlinear function $F$, assumption
(2) always holds on a suitable neighbourhood of $x_{*}$. For instance, if $F$
is two times continuously differentiable, then the majorant function
$f:[0,\kappa)\to\mathbb{R}$, as defined by $f(t)=Kt^{2}/2-t,$ where
$K=\sup\\{\|F^{\prime\prime}(x)\|:x\in B[x_{*},\kappa]\\}$ satisfies
assumption (2). Estimating the constant $K$ is a very difficult problem.
Therefore, the goal is to identify classes of nonlinear functions for which it
is possible to obtain a majorant function. We will give some examples of such
classes in Section 3.

To prove Theorem 7 we need some results. From here on, we assume that all
assumptions of Theorem 7 hold.

###  2.1 The majorant function

In this section, we will prove that the constant $\kappa$ associated with
$\Omega$ and the constants $\nu$, $\rho$ and $r$ associated with the majorant
function $f$ are positive. We will also prove some results related to the
function $f$.

We begin by noting that $\kappa>0$, because $\Omega$ is an open set and
$x_{*}\in\Omega$.

######  Proposition 9.

The constant $\nu$ is positive and there holds

$\beta[f^{\prime}(t)+1]<1,\qquad t\in(0,\nu).$

###### Proof.

As $f^{\prime}$ is continuous in $(0,R)$ and $f^{\prime}(0)=-1,$ it is easy to
conclude that

$\lim_{t\to 0}\beta[f^{\prime}(t)+1]=0.$

Thus, there exists a $\delta>0$ such that $\beta(f^{\prime}(t)+1)<1$ for all
$t\in(0,\delta)$. Hence, $\nu>0.$

Using h2 and definition of $\nu$ the last part of the proposition follows.

∎

######  Proposition 10.

The following functions are increasing:

  * i)

$[0,\,R)\ni t\mapsto 1/[1-\beta(f^{\prime}(t)+1)];$

  * ii)

$(0,\,R)\ni t\mapsto[tf^{\prime}(t)-f(t)]/t^{2};$

  * iii)

$(0,\,R)\ni t\mapsto[f^{\prime}(t)+1]/t;$

As a consequence, there is an increase of the following functions

$(0,\,R)\ni
t\mapsto\frac{tf^{\prime}(t)-f(t)}{t^{2}[1-\beta(f^{\prime}(t)+1)]},\qquad\qquad(0,\,R)\ni
t\mapsto\frac{f^{\prime}(t)+1}{t[1-\beta(f^{\prime}(t)+1)]}.$

###### Proof.

The item i is immediate, because $f^{\prime}$ is strictly increasing in
$[0,R)$.

For proving item ii, note that after some simple algebraic manipulations we
have

$\frac{tf^{\prime}(t)-f(t)}{t^{2}}=\int_{0}^{1}\frac{f^{\prime}(t)-f^{\prime}(\tau
t)}{t}\;d\tau.$

So, applying Proposition 6 with $f^{\prime}=\varphi$ and $\epsilon=R$ the
statement follows.

For establishing item iii use $\bf h2$, $f^{\prime}(0)=-1$ and Proposition 6
with $f^{\prime}=\varphi,$ $\epsilon=R$ and $\tau=0.$

To prove that the functions in the last part are increasing, combine item i
with ii for the first function, and i with iii for the second function. ∎

######  Proposition 11.

The constant $\rho$ is positive and there holds

$(1+\vartheta)\omega_{1}\beta\frac{tf^{\prime}(t)-f(t)+\sqrt{2}c\beta[f^{\prime}(t)+1]}{t[1-\beta(f^{\prime}(t)+1)]}+\omega_{1}\vartheta+\omega_{2}<1,\qquad\forall\;t\in(0,\,\rho).$

###### Proof.

First of all, note that the assumption $\bf h1$ implies, after simple
calculation, that

$\lim_{t\to
0}\frac{tf^{\prime}(t)-f(t)}{t[1-\beta(f^{\prime}(t)+1)]}=\lim_{t\to
0}\frac{f^{\prime}(t)-(f(t)-f(0))/t}{1-\beta(f^{\prime}(t)+1)}=0.$

Again, using $\bf h1$, some algebraic manipulation and that $f^{\prime}$ is
convex, we have by Proposition 5

$\lim_{t\to 0}\frac{f^{\prime}(t)+1}{t[1-\beta(f^{\prime}(t)+1)]}=\lim_{t\to
0}\frac{(f^{\prime}(t)-f^{\prime}(0))/t}{1-\beta(f^{\prime}(t)+1)}=D^{+}f^{\prime}(0).$

Hence, by combining the two above equalities it is easy to conclude that

$\lim_{t\to
0}(1+\vartheta)\omega_{1}\beta\frac{tf^{\prime}(t)-f(t)+\sqrt{2}c\beta[f^{\prime}(t)+1]}{t[1-\beta(f^{\prime}(t)+1)]}+\omega_{1}\vartheta+\omega_{2}=(1+\vartheta)\omega_{1}\sqrt{2}c\beta^{2}D^{+}f^{\prime}(0)+\omega_{1}\vartheta+\omega_{2}.$

As, $\alpha=\sqrt{2}c\beta^{2}D^{+}f^{\prime}(0)$ and
$\omega_{1}(\alpha+\alpha\vartheta+\vartheta)+\omega_{2}<1$, we obtain that
there exists a $\delta>0$ such that

$(1+\vartheta)\omega_{1}\beta\frac{tf^{\prime}(t)-f(t)+\sqrt{2}c\beta[f^{\prime}(t)+1]}{t[1-\beta(f^{\prime}(t)+1)]}+\omega_{1}\vartheta+\omega_{2}<1,\qquad
t\in(0,\delta),$

Hence, $\delta\leq\rho$, which proves the first statement. To conclude the
proof, we use the definition of $\rho$, the above inequality, and the last
part of Proposition 10. ∎

###  2.2 Relationship of the majorant function with the non-linear function

In this section we will present the main relationships between the majorant
function $f$ and the function $F$ associated with the nonlinear least square
problem.

######  Lemma 12.

Let $x\in\Omega$. If $\|x-x_{*}\|<\min\\{\nu,\kappa\\}$, then
$F^{\prime}(x)^{*}F^{\prime}(x)$ is invertible and the following inequalities
hold

$\left\|F^{\prime}(x)^{\dagger}\right\|\leq\frac{\beta}{1-\beta[f^{\prime}(\|x-x_{*}\|)+1]},\qquad\left\|F^{\prime}(x)^{\dagger}-F^{\prime}(x_{*})^{\dagger}\right\|<\frac{\sqrt{2}\beta^{2}[f^{\prime}(\|x-x_{*}\|)+1]}{1-\beta[f^{\prime}(\|x-x_{*}\|)+1]}.$

In particular, $F^{\prime}(x)^{*}F^{\prime}(x)$ is invertible in $B(x_{*},r)$.

###### Proof.

Let $x\in\Omega$ such that $\|x-x_{*}\|<\min\\{\nu,\kappa\\}$. Since
$\|x-x_{*}\|<\nu$, using the definition of $\beta$, the inequality (2) and
last part of Proposition 9 we have

$\|F^{\prime}(x)-F^{\prime}(x_{*})\|\|F^{\prime}(x_{*})^{\dagger}\|\leq\beta[f^{\prime}(\|x-x_{*}\|)-f^{\prime}(0)]<1.$

For the sake of simplicity, the notations define the following matrices

$A=F^{\prime}(x_{*}),\qquad B=F^{\prime}(x),\qquad
E=F^{\prime}(x)-F^{\prime}(x_{*}).$ (6)

The last definitions, together with the latter inequality, imply that

$\|EA^{\dagger}\|\leq\|E\|\|A^{\dagger}\|<1,$

which, using that $F^{\prime}(x_{*})$ is injective, implies in view of Lemma 2
that $F^{\prime}(x)$ is injective. So, $F^{\prime}(x)^{*}F^{\prime}(x)$ is
invertible and by definition of $r$ we obtain that
$F^{\prime}(x)^{*}F^{\prime}(x)$ is invertible for all $x\in B(x_{*},r)$.

We already know that $F^{\prime}(x_{*})$ and $F^{\prime}(x)$ are injective.
Hence, to conclude the lemma use definitions in (6) and then combine the above
inequality and Lemma 3. ∎

Now, it is convenient to study the linearization error of $F$ at point in
$\Omega$, for which we define

$E_{F}(x,y):=F(y)-\left[F(x)+F^{\prime}(x)(y-x)\right],\qquad y,\,x\in\Omega.$
(7)

We will bound this error by the error in the linearization on the majorant
function $f$

$e_{f}(t,u):=f(u)-\left[f(t)+f^{\prime}(t)(u-t)\right],\qquad t,\,u\in[0,R).$
(8)

######  Lemma 13.

If $\|x-x_{*}\|<\kappa$, then there holds $\|E_{F}(x,x_{*})\|\leq
e_{f}(\|x-x_{*}\|,0).$

###### Proof.

Since $B(x_{*},\kappa)$ is convex, we obtain that $x_{*}+\tau(x-x_{*})\in
B(x_{*},\kappa)$, for $0\leq\tau\leq 1$. Thus, as $F$ is continuously
differentiable in $\Omega$, definition of $E_{F}$ and some simple
manipulations yield

$\|E_{F}(x,x_{*})\|\leq\int_{0}^{1}\left\|[F^{\prime}(x)-F^{\prime}(x_{*}+\tau(x-x_{*}))]\right\|\,\left\|x_{*}-x\right\|\;d\tau.$

¿From the last inequality and the assumption (2), we obtain

$\|E_{F}(x,x_{*})\|\leq\int_{0}^{1}\left[f^{\prime}\left(\left\|x-x_{*}\right\|\right)-f^{\prime}\left(\tau\|x-x_{*}\|\right)\right]\|x-x_{*}\|\;d\tau.$

Evaluating the above integral and using definition of $e_{f}$, the statement
follows. ∎

Define the Gauss-Newton step to the functions $F$ by the following equality:

$S_{F}(x):=-F^{\prime}(x)^{\dagger}F(x).$ (9)

######  Lemma 14.

If $\|x-x_{*}\|<\min\\{\nu,\kappa\\}$, then

$\|S_{F}(x)\|\leq\frac{\beta
e_{f}(\|x-x_{*}\|,0)+\sqrt{2}c\beta^{2}[f^{\prime}(\|x-x_{*}\|)+1]}{1-\beta[f^{\prime}(\|x-x_{*}\|)+1]}+\|x-x_{*}\|.$

###### Proof.

Using (9), $F^{\prime}(x_{*})^{*}F(x_{*})=0$ and some algebraic manipulation,
it follows from (7) that

$\displaystyle\|S_{F}(x)\|$
$\displaystyle=\|F^{\prime}(x)^{\dagger}\left(F(x_{*})-[F(x)+F^{\prime}(x)(x_{*}-x)]\right)-(F^{\prime}(x)^{\dagger}-F^{\prime}(x_{*})^{\dagger})F(x_{*})+(x_{*}-x)\|$
$\displaystyle\leq\|F^{\prime}(x)^{\dagger}\|\|E_{F}(x,x_{*})\|+\|F^{\prime}(x)^{\dagger}-F^{\prime}(x_{*})^{\dagger}\|\|F(x_{*})\|+\|x-x_{*}\|.$

So, the last inequality together with the Lemma 12, Lemma 13 and definition of
$c,$ imply that

$\|S_{F}(x)\|\leq\frac{\beta
e_{f}(\|x-x_{*}\|,0)}{1-\beta[f^{\prime}(\|x-x_{*}\|)+1]}+\frac{\sqrt{2}c\beta^{2}[f^{\prime}(\|x-x_{*}\|)+1]}{1-\beta[f^{\prime}(\|x-x_{*}\|)+1]}+\|x-x_{*}\|,$

which is equivalent to the desired inequality. ∎

######  Lemma 15.

Let $\Omega\subseteq\mathbb{X}$ be an open set and $F:{\Omega}\to\mathbb{Y}$ a
continuously differentiable function. Let $x_{*}\in\Omega,$ $R>0$ and $c,$
$\beta,$ $\kappa$ as a definition in Theorem 7. Suppose that
$F^{\prime}(x_{*})^{*}F(x_{*})=0$, $F^{\prime}(x_{*})$ is injective and there
exists a $f:[0,\;R)\to\mathbb{R}$ continuously differentiable satisfying (2),
h1, h2 and h3. Let $\alpha$, $\vartheta$, $\omega_{1}$, $\omega_{2}$, $\nu$,
$\rho$ and $r$ as in Theorem 7. Assume that $x\in
B(x_{*},r)\backslash\\{x_{*}\\}$, i.e., $0<\|x-x_{*}\|<r$. Define

$x_{+}={x}+S,\qquad B(x)S=-F^{\prime}(x)^{*}F(x)+r,$ (10)

where $B(x)$ is an invertible approximation of
$F^{\prime}(x)^{*}F^{\prime}(x)$ satisfying

$\|B(x)^{-1}F^{\prime}(x)^{*}F^{\prime}(x)\|\leq\omega_{1},\qquad\|B(x)^{-1}F^{\prime}(x)^{*}F^{\prime}(x)-I\|\leq\omega_{2},$
(11)

and the forcing term $\theta$ and the residual $r$ satisfy

$\theta\mbox{cond}(PF^{\prime}(x)^{*}F^{\prime}(x))\leq\vartheta,\qquad\|Pr\|\leq\theta\|PF^{\prime}(x)^{*}F(x)\|,$
(12)

with $P$ an invertible matrix(preconditioner for the linear system in (10)).
Then $x_{+}$ is well defined and there holds

$\|x_{+}-x_{*}\|\leq(1+\vartheta)\omega_{1}\beta\frac{[f^{\prime}(\|x-x_{*}\|)\|x-x_{*}\|-f(\|x-x_{*}\|)]}{\|x-x_{*}\|^{2}[1-\beta(f^{\prime}(\|x-x_{*}\|)+1)]}{\|x-x_{*}\|}^{2}\\\
+\left(\frac{(1+\vartheta)\omega_{1}\sqrt{2}c\beta^{2}[f^{\prime}(\|x-x_{*}\|)+1]}{\|x-x_{*}\|[1-\beta(f^{\prime}(\|x-x_{*}\|)+1)]}+\omega_{1}\vartheta+\omega_{2}\right)\|x-x_{*}\|,\qquad
k=0,1,\ldots.$ (13)

In particular,

$\|x_{+}-x_{*}\|<\|x-x_{*}\|.$

###### Proof.

First note that, as $\|x-x_{*}\|<r$, it follows from Lemma 12 that
$F^{\prime}(x)^{*}F^{\prime}(x)$ is invertible. Now, let $B(x)$ an invertible
approximation of it satisfying (11). Thus, $x_{+}$ is well defined. Now, as
$F^{\prime}(x_{*})^{*}F(x_{*})=0,$ some simple algebraic manipulation and (10)
yield

$x_{+}-x_{*}=x-x_{*}-B(x)^{-1}F^{\prime}(x)^{*}\big{(}F(x)-F(x_{*})\big{)}+B(x)^{-1}{r}\\\
+B(x)^{-1}F^{\prime}(x)^{*}F^{\prime}(x)\left[F^{\prime}(x_{*})^{\dagger}F(x_{*})-F^{\prime}(x)^{\dagger}F(x_{*})\right].$

Again, some algebraic manipulation in the above equation gives

$x_{+}-x_{*}=B(x)^{-1}F^{\prime}(x)^{*}F^{\prime}(x)F^{\prime}(x)^{\dagger}\big{(}F(x_{*})-[F(x)+F^{\prime}(x)(x_{*}-x)]\big{)}+B(x)^{-1}{r}\\\
+B(x)^{-1}\left(F^{\prime}(x)^{*}F^{\prime}(x)-B(x)\right)(x-x_{*})+B(x)^{-1}F^{\prime}(x)^{*}F^{\prime}(x)[F^{\prime}(x_{*})^{\dagger}F(x_{*})-F^{\prime}(x)^{\dagger}F(x_{*})].$

The last equation, together with (7) and (11), imply that

$\|x_{+}-x_{*}\|\leq\omega_{1}\|F^{\prime}(x)^{\dagger}\|\|E_{F}(x,x_{*})\|+\|B(x)^{-1}{r}\|+\omega_{2}\|x-x_{*}\|+\omega_{1}\|F^{\prime}(x)^{\dagger}-F^{\prime}(x_{*})^{\dagger}\|\|F(x_{*})\|.$

On the other hand, using (9), (11) and (12) we have, by simple calculus,

$\displaystyle\|B(x)^{-1}{r}\|$ $\displaystyle\leq\|B(x)^{-1}P^{-1}\|\|P{r}\|$
$\displaystyle\leq\theta\|B(x)^{-1}F^{\prime}(x)^{*}F^{\prime}(x)\|\|(PF^{\prime}(x)^{*}F^{\prime}(x))^{-1}\|\|PF^{\prime}(x)^{*}F^{\prime}(x)\|\|F^{\prime}(x)^{\dagger}F(x)\|$
$\displaystyle\leq\omega_{1}\vartheta\|S_{F}(x)\|.$

Hence, it follows from the two last equations that

$\|x_{+}-x_{*}\|\leq\omega_{1}\|F^{\prime}(x)^{\dagger}\|\|E_{F}(x,x_{*})\|+\omega_{1}\vartheta\|S_{F}(x)\|+\omega_{2}\|x-x_{*}\|+\omega_{1}\|F^{\prime}(x)^{\dagger}-F^{\prime}(x_{*})^{\dagger}\|\|F(x_{*})\|.$

Combining the last equation with the Lemmas 12, 13 and 14, we obtain that

$\|x_{+}-x_{*}\|\leq(1+\vartheta)\beta\omega_{1}\frac{e_{f}(\|x-x_{*}\|,0)+\sqrt{2}c\beta(f^{\prime}(\|x-x_{*}\|)+1)}{1-\beta(f^{\prime}(\|x-x_{*}\|)+1)}+\omega_{1}\vartheta\|x-x_{*}\|+\omega_{2}\|x-x_{*}\|.$

Now, using (8) and some algebraic manipulation, we conclude from the last
inequality that

$\|x_{+}-x_{*}\|\leq(1+\vartheta)\beta\omega_{1}\frac{f^{\prime}(\|x-x_{*}\|)\|x-x_{*}\|-f(\|x-x_{*}\|)+\sqrt{2}c\beta(f^{\prime}(\|x-x_{*}\|)+1)}{1-\beta(f^{\prime}(\|x-x_{*}\|)+1)}\\\
+\omega_{1}\vartheta\|x-x_{*}\|+\omega_{2}\|x-x_{*}\|,$

which is equivalent to (13). To end the proof, note that the right hand side
of (13) is equivalent to

$\Bigg{[}(1+\vartheta)\omega_{1}\beta\frac{f^{\prime}(\|x-x_{*}\|)\|x-x_{*}\|-f(\|x-x_{*}\|)+\sqrt{2}c\beta(f^{\prime}(\|x-x_{*}\|)+1)}{\|x-x_{*}\|[1-\beta(f^{\prime}(\|x-x_{*}\|)+1)]}+\omega_{1}\vartheta+\omega_{2}\Bigg{]}\|x-x_{*}\|.$

On the other hand, as $x\in B(x_{*},r)/\\{x_{*}\\}$, i.e.,
$0<\|x-x_{*}\|<r\leq\rho$ we apply the Proposition 11 with $t=\|x-x_{*}\|$ to
conclude that the quantity in the bracket above is less than one. So, the last
inequality of the lemma follows. ∎

###  2.3 Proof of Theorem 7

Now, we will produce the proof of Theorem 7.

###### Proof.

Since $x_{0}\in B(x_{*},r)/\\{x_{*}\\},$ i.e., $0<\|x_{0}-x_{*}\|<r,$ by
combination of Lemma 12, last inequality in Lemma 15 and induction argument,
it is easy to see that $\\{x_{k}\\}$ is well defined and remains in
$B(x_{*},r)$.

We are going to prove that $\\{x_{k}\\}$ converges towards $x_{*}$. As,
$\\{x_{k}\\}$ is well defined and contained in $B(x_{*},r)$, applying Lemma 15
with $x_{+}=x_{k+1},$ $x=x_{k},$ $r=r_{k},$ $B(x)=B(x_{k}),$ $P=P_{k},$ and
$\theta=\theta_{k}$ we obtain

$\|x_{k+1}-x_{*}\|\leq(1+\vartheta)\omega_{1}\beta\frac{[f^{\prime}(\|x_{k}-x_{*}\|)\|x_{k}-x_{*}\|-f(\|x_{k}-x_{*}\|)]}{\|x_{k}-x_{*}\|^{2}[1-\beta(f^{\prime}(\|x_{k}-x_{*}\|)+1)]}{\|x_{k}-x_{*}\|}^{2}\\\
+\left(\frac{(1+\vartheta)\omega_{1}\sqrt{2}c\beta^{2}[f^{\prime}(\|x_{k}-x_{*}\|)+1]}{\|x_{k}-x_{*}\|[1-\beta(f^{\prime}(\|x_{k}-x_{*}\|)+1)]}+\omega_{1}\vartheta+\omega_{2}\right)\|x_{k}-x_{*}\|,\qquad
k=0,1,\ldots.$

Now, using the last inequality of Lemma 15, it is easy to conclude that

$\|x_{k}-x_{*}\|<\|x_{0}-x_{*}\|,\qquad\;k=1,2\ldots.$ (14)

Hence, combining the last two inequalities with the last part of Proposition
10 we obtain that

$\|x_{k+1}-x_{*}\|\leq(1+\vartheta)\omega_{1}\beta\frac{[f^{\prime}(\|x_{0}-x_{*}\|)\|x_{0}-x_{*}\|-f(\|x_{0}-x_{*}\|)]}{\|x_{0}-x_{*}\|^{2}[1-\beta(f^{\prime}(\|x_{0}-x_{*}\|)+1)]}{\|x_{k}-x_{*}\|}^{2}\\\
+\left(\frac{(1+\vartheta)\omega_{1}\sqrt{2}c\beta^{2}[f^{\prime}(\|x_{0}-x_{*}\|)+1]}{\|x_{0}-x_{*}\|[1-\beta(f^{\prime}(\|x_{0}-x_{*}\|)+1)]}+\omega_{1}\vartheta+\omega_{2}\right)\|x_{k}-x_{*}\|,\qquad
k=0,1,\ldots,$

which is the inequality (5). Now, using (14) and the last inequality we have

$\|x_{k+1}-x_{*}\|\leq\\\
\Bigg{[}(1+\vartheta)\omega_{1}\beta\frac{f^{\prime}(\|x_{0}-x_{*}\|)\|x_{0}-x_{*}\|-f(\|x_{0}-x_{*}\|)+\sqrt{2}c\beta(f^{\prime}(\|x_{0}-x_{*}\|)+1)}{\|x_{0}-x_{*}\|[1-\beta(f^{\prime}(\|x_{0}-x_{*}\|)+1)]}+\omega_{1}\vartheta+\omega_{2}\Bigg{]}\|x_{k}-x_{*}\|,$

for all $k=0,1,\ldots$. Applying Proposition 11 with $t=\|x_{0}-x_{*}\|$ it is
straightforward to conclude from the latter inequality that
$\\{\|x_{k}-x_{*}\|\\}$ converges to zero. So, $\\{x_{k}\\}$ converges to
$x_{*}$. ∎

##  3 Special cases

In this section, we present two special cases of Theorem 7. They include the
classical convergence theorem on Gauss-Newton’s method under the Lipschitz
condition and Smale’s theorem on Gauss-Newton for analytical functions.

###  3.1 Convergence result for Lipschitz condition

In this section we show a correspondent theorem for Theorem 7 under the
Lipschitz condition, instead of the general assumption (2).

######  Theorem 16.

Let $\Omega\subseteq\mathbb{X}$ be an open set, $F:{\Omega}\to\mathbb{Y}$ a
continuously differentiable function. Let $x_{*}\in\Omega,$ $R>0$ and

$c:=\|F(x_{*})\|,\qquad\beta:=\left\|F^{\prime}(x_{*})^{\dagger}\right\|,\qquad\kappa:=\sup\left\\{t\in[0,R):B(x_{*},t)\subset\Omega\right\\}.$

Suppose that $F^{\prime}(x_{*})^{*}F(x_{*})=0$, $F^{\prime}(x_{*})$ is
injective and there exists a $K>0$ such that

$\alpha:=\sqrt{2}c\beta^{2}K<1,\qquad\qquad\left\|F^{\prime}(x)-F^{\prime}(y)\right\|\leq
K\|x-y\|,\qquad\forall\;x,y\in B(x_{*},\kappa).$

Take $0\leq\vartheta<1$, $0\leq\omega_{2}<\omega_{1}$ such that
$\omega_{1}(\alpha+\alpha\vartheta+\vartheta)+\omega_{2}<1$. Let

$r:=\min\left\\{\kappa,\frac{2(1-\omega_{1}\vartheta-\omega_{2})-2\sqrt{2}cK\beta^{2}\omega_{1}(1+\vartheta)}{\beta
K\left(2+\omega_{1}-\vartheta\omega_{1}-2\omega_{2}\right)}\right\\}.$

Then, the inexact Gauss-Newton like methods for solving (1), with initial
point $x_{0}\in B(x_{*},r)\backslash\\{x_{*}\\}$

$x_{k+1}={x_{k}}+S_{k},\qquad
B(x_{k})S_{k}=-F^{\prime}(x_{k})^{*}F(x_{k})+r_{k},\qquad\;k=0,1,\ldots,$ (15)

with the following conditions for the residual $r_{k},$ and the forcing term
$\theta_{k}$

$\|P_{k}r_{k}\|\leq\theta_{k}\|P_{k}F^{\prime}(x_{k})^{*}F(x_{k})\|,\qquad
0\leq\theta_{k}\mbox{cond}(P_{k}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k}))\leq\vartheta,\qquad\;k=0,1,\ldots,$

where $\\{P_{k}\\}$ is an invertible matrix sequence (preconditoners for the
linear system in (15)) and $B(x_{k})$ is an invertible approximation of
$F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})$ satisfying

$\|B(x_{k})^{-1}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})\|\leq\omega_{1},\qquad\|B(x_{k})^{-1}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})-I\|\leq\omega_{2},\qquad\;k=0,1,\ldots,$

is well defined, contained in $B(x_{*},r)$, converges to $x_{*}$ and there
holds

$\|x_{k+1}-x_{*}\|\leq\frac{(1+\vartheta)\beta\omega_{1}K}{2(1-\beta
K\|x_{0}-x_{*}\|)}\|x_{k}-x_{*}\|^{2}+\left(\frac{(1+\vartheta)\omega_{1}\sqrt{2}c\beta^{2}K}{1-\beta
K\|x_{0}-x_{*}\|}+\omega_{1}\vartheta+\omega_{2}\right)\|x_{k}-x_{*}\|,$

for all $k=0,1,\ldots.$

###### Proof.

It is immediate to prove that $F$, $x_{*}$ and $f:[0,\kappa)\to\mathbb{R}$ as
defined by $f(t)=Kt^{2}/2-t,$ satisfy the inequality (2), conditions h1 and
h2. Since $\sqrt{2}c\beta^{2}K<1$ the condition h3 also holds. In this case,
it is easy to see that constants $\nu$ and $\rho$ as defined in Theorem 7,
satisfy

$0<\rho=\frac{2(1-\omega_{1}\vartheta-\omega_{2})-2\sqrt{2}cK\beta^{2}\omega_{1}(1+\vartheta)}{\beta
K\left(2+\omega_{1}-\vartheta\omega_{1}-2\omega_{2}\right)}\leq\nu=1/\beta K,$

as a consequence, $0<r=\min\\{\kappa,\,\rho\\}.$ Therefore, as $F$, $r$, $f$
and $x_{*}$ satisfy all of the hypotheses of Theorem 7, taking $x_{0}\in
B(x_{*},r)\backslash\\{x_{*}\\}$ the statements of the theorem follow from
Theorem 7. ∎

For the case $\vartheta=0$, the Theorem 16 becomes:

######  Corollary 17.

Let $\Omega\subseteq\mathbb{X}$ be an open set, $F:{\Omega}\to\mathbb{Y}$ a
continuously differentiable function. Let $x_{*}\in\Omega,$ $R>0$ and

$c:=\|F(x_{*})\|,\qquad\beta:=\left\|F^{\prime}(x_{*})^{\dagger}\right\|,\qquad\kappa:=\sup\left\\{t\in[0,R):B(x_{*},t)\subset\Omega\right\\}.$

Suppose that $F^{\prime}(x_{*})^{*}F(x_{*})=0$, $F^{\prime}(x_{*})$ is
injective and there exists a $K>0$ such that

$\alpha:=\sqrt{2}c\beta^{2}K<1,\qquad\qquad\left\|F^{\prime}(x)-F^{\prime}(y)\right\|\leq
K\|x-y\|,\qquad\forall\;x,y\in B(x_{*},\kappa).$

Take $0\leq\omega_{2}<\omega_{1}$ such that $\omega_{1}\alpha+\omega_{2}<1$.
Let

$r:=\min\left\\{\kappa,\frac{2(1-\omega_{2})-2\sqrt{2}cK\beta^{2}\omega_{1}}{\beta
K\left(2+\omega_{1}-2\omega_{2}\right)}\right\\}.$

Then, the Gauss-Newton’s like method for solving (1), with initial point
$x_{0}\in B(x_{*},r)\backslash\\{x_{*}\\}$

$x_{k+1}={x_{k}}+S_{k},\qquad
B(x_{k})S_{k}=-F^{\prime}(x_{k})^{*}F(x_{k}),\qquad\;k=0,1,\ldots,$ (16)

where $B(x_{k})$ is an invertible approximation of
$F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})$ satisfying

$\|B(x_{k})^{-1}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})\|\leq\omega_{1},\qquad\|B(x_{k})^{-1}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})-I\|\leq\omega_{2},\qquad\;k=0,1,\ldots,$

is well defined, contained in $B(x_{*},r)$, converges to $x_{*}$ and there
holds

$\|x_{k+1}-x_{*}\|\leq\frac{\beta\omega_{1}K}{2(1-\beta
K\|x_{0}-x_{*}\|)}\|x_{k}-x_{*}\|^{2}+\left(\frac{\omega_{1}\sqrt{2}c\beta^{2}K}{1-\beta
K\|x_{0}-x_{*}\|}+\omega_{2}\right)\|x_{k}-x_{*}\|,$

for all $k=0,1,\ldots.$

Note that letting $c=0$ in the above corollary, we obtain the Corollary 6.1 of
[8].

###  3.2 Convergence result under Smale’s condition

In this section we present a correspondent theorem to Theorem 7 under Smale’s
condition. For more details see Smale [26] and Dedieu and Shub [11].

######  Theorem 18.

Let $\Omega\subseteq\mathbb{X}$ be an open set, $F:{\Omega}\to\mathbb{Y}$ a
continuously differentiable function. Let $x_{*}\in\Omega,$ $R>0$ and

$c:=\|F(x_{*})\|,\qquad\beta:=\left\|F^{\prime}(x_{*})^{\dagger}\right\|,\qquad\kappa:=\sup\left\\{t\in[0,R):B(x_{*},t)\subset\Omega\right\\}.$

Suppose that $F^{\prime}(x_{*})^{*}F(x_{*})=0$, $F^{\prime}(x_{*})$ is
injective and

$\qquad\gamma:=\sup_{n>1}\left\|\frac{F^{(n)}(x_{*})}{n!}\right\|^{1/(n-1)}<+\infty,\qquad\qquad\alpha:=2\sqrt{2}c\beta^{2}\gamma<1.$
(17)

Take $0\leq\vartheta<1$, $0\leq\omega_{2}<\omega_{1}$ such that
$\omega_{1}(\alpha+\alpha\vartheta+\vartheta)+\omega_{2}<1$. Let
$a:=(1-\vartheta\omega_{1}-\omega_{2})$, $b:=(1+\vartheta)\omega_{1}\beta,$
$\bar{a}:=b+2a(1+\beta)-\sqrt{2}\gamma\beta bc$ and

$r:=\min\left\\{\kappa,\frac{\bar{a}-\sqrt{\bar{a}^{2}-4a(1+\beta)(a-2\sqrt{2}c\beta
b\gamma)}}{2a\gamma(1+\beta)}\right\\}.$

Then, the inexact Gauss-Newton like methods for solving (1), with initial
point $x_{0}\in B(x_{*},r)\backslash\\{x_{*}\\}$

$x_{k+1}={x_{k}}+S_{k},\qquad
B(x_{k})S_{k}=-F^{\prime}(x_{k})^{*}F(x_{k})+r_{k},\qquad\;k=0,1,\ldots,$ (18)

with the following conditions for the residual $r_{k},$ and the forcing term
$\theta_{k}$

$\|P_{k}r_{k}\|\leq\theta_{k}\|P_{k}F^{\prime}(x_{k})^{*}F(x_{k})\|,\qquad
0\leq\theta_{k}\mbox{cond}(P_{k}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k}))\leq\vartheta,\qquad\;k=0,1,\ldots,$

where $\\{P_{k}\\}$ is an invertible matrix sequence (preconditoners for the
linear system in (18)) and $B(x_{k})$ is an invertible approximation of
$F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})$ satisfying

$\|B(x_{k})^{-1}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})\|\leq\omega_{1},\qquad\|B(x_{k})^{-1}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})-I\|\leq\omega_{2},\qquad\;k=0,1,\ldots,$

is well defined, contained in $B(x_{*},r)$, converges to $x_{*}$ and there
holds

$\displaystyle\|x_{k+1}-x_{*}\|\leq$
$\displaystyle\frac{(1+\vartheta)\omega_{1}\beta\gamma}{(1-\gamma\|x_{0}-x_{*}\|)^{2}-\beta\gamma(2\|x_{0}-x_{*}\|-\gamma\|x_{0}-x_{*}\|^{2})}\|x_{k}-x_{*}\|^{2}$
$\displaystyle+$
$\displaystyle\left(\frac{(1+\vartheta)\omega_{1}\sqrt{2}c\beta^{2}\gamma(2-\gamma\|x_{0}-x_{*}\|)}{(1-\gamma\|x_{0}-x_{*}\|)^{2}-\beta\gamma(2\|x_{0}-x_{*}\|-\gamma\|x_{0}-x_{*}\|^{2})}+\omega_{1}\vartheta+\omega_{2}\right)\|x_{k}-x_{*}\|,$

for all $k=0,1,\ldots.$

We need the following result to prove the above theorem.

######  Lemma 19.

Let $\Omega\subseteq\mathbb{X}$ be an open set, $F:{\Omega}\to\mathbb{Y}$ an
analytic function. Suppose that $x_{*}\in\Omega$ and
$B(x_{*},1/\gamma)\subset\Omega$, where $\gamma$ is defined in (17). Then, for
all $x\in B(x_{*},1/\gamma)$ there holds

$\|F^{\prime\prime}(x)\|\leqslant 2\gamma/(1-\gamma\|x-x_{*}\|)^{3}.$

###### Proof.

See the proof of the Lemma 21 of [16]. ∎

The next result gives a condition that is easier to check than condition (2),
whenever the functions under consideration are twice continuously
differentiable.

######  Lemma 20.

Let $\Omega\subseteq\mathbb{X}$ be an open set, $x_{*}\in\Omega$ and
$F:{\Omega}\to\mathbb{Y}$ be twice continuously on $\Omega$. If there exists a
$f:[0,R)\to\mathbb{R}$ twice continuously differentiable such that

$\|F^{\prime\prime}(x)\|\leqslant f^{\prime\prime}(\|x-x_{*}\|),$ (19)

for all $x\in\Omega$ such that $\|x-x_{*}\|<R$. Then $F$ and $f$ satisfy (2).

###### Proof.

See the proof of the Lemma 22 of [16]. ∎

[Proof of Theorem 18]. Consider the real function
$f:[0,1/\gamma)\to\mathbb{R}$ defined by

$f(t)=\frac{t}{1-\gamma t}-2t.$

It is straightforward to show that $f$ is analytic and that

$f(0)=0,\quad f^{\prime}(t)=1/(1-\gamma t)^{2}-2,\quad f^{\prime}(0)=-1,\quad
f^{\prime\prime}(t)=(2\gamma)/(1-\gamma t)^{3},\quad
f^{n}(0)=n!\,\gamma^{n-1},$

for $n\geq 2$. It follows from the last equalities that $f$ satisfies h1 and
h2. Since $2\sqrt{2}c\beta^{2}\gamma<1$ the condition h3 also holds. Now, as
$f^{\prime\prime}(t)=(2\gamma)/(1-\gamma t)^{3}$ combining Lemmas 20, 19 we
conclude that $F$ and $f$ satisfy (2) with $R=1/\gamma$. In this case, it is
easy to see that constants $\nu$ and $\rho$ as defined in Theorem 7, satisfy

$0<\rho=\frac{\bar{a}-\sqrt{\bar{a}^{2}-4a(1+\beta)(a-2\sqrt{2}c\beta
b\gamma)}}{2a\gamma(1+\beta)}<\nu=((1+\beta)-\sqrt{\beta(1+\beta)})/(\gamma(1+\beta))<1/\gamma,$

and as a consequence, $0<r=\min\\{\kappa,\rho\\}.$ Therefore, as $F$,
$\sigma$, $f$ and $x_{*}$ satisfy all hypotheses of Theorem 7, taking
$x_{0}\in B(x_{*},r)\backslash\\{x_{*}\\}$, the statements of the theorem
follow from Theorem 7.∎

For the case $\vartheta=0$, the Theorem 18 becomes:

######  Corollary 21.

Let $\Omega\subseteq\mathbb{X}$ be an open set, $F:{\Omega}\to\mathbb{Y}$ a
continuously differentiable function. Let $x_{*}\in\Omega,$ $R>0$ and

$c:=\|F(x_{*})\|,\qquad\beta:=\left\|F^{\prime}(x_{*})^{\dagger}\right\|,\qquad\kappa:=\sup\left\\{t\in[0,R):B(x_{*},t)\subset\Omega\right\\}.$

Suppose that $F^{\prime}(x_{*})^{*}F(x_{*})=0$, $F^{\prime}(x_{*})$ is
injective and

$\qquad\gamma:=\sup_{n>1}\left\|\frac{F^{(n)}(x_{*})}{n!}\right\|^{1/(n-1)}<+\infty,\qquad\qquad\alpha:=2\sqrt{2}c\beta^{2}\gamma<1.$

Take $0\leq\omega_{2}<\omega_{1}$ such that $\omega_{1}\alpha+\omega_{2}<1$.
Let
$\bar{a}:=\omega_{1}\beta+2(1-\omega_{2})(1+\beta)-\sqrt{2}\gamma\beta^{2}\omega_{1}c$
and

$r:=\min\left\\{\kappa,\frac{\bar{a}-\sqrt{\bar{a}^{2}-4(1-\omega_{2})(1+\beta)(1-\omega_{2}-2\sqrt{2}c\beta^{2}\omega_{1}\gamma)}}{2(1-\omega_{2})\gamma(1+\beta)}\right\\}.$

Then, the Gauss-Newton’s like method for solving (1), with initial point
$x_{0}\in B(x_{*},r)\backslash\\{x_{*}\\}$

$x_{k+1}={x_{k}}+S_{k},\qquad
B(x_{k})S_{k}=-F^{\prime}(x_{k})^{*}F(x_{k}),\qquad\;k=0,1,\ldots,$

where $B(x_{k})$ is an invertible approximation of
$F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})$ satisfying

$\|B(x_{k})^{-1}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})\|\leq\omega_{1},\qquad\|B(x_{k})^{-1}F^{\prime}(x_{k})^{*}F^{\prime}(x_{k})-I\|\leq\omega_{2},\qquad\;k=0,1,\ldots,$

is well defined, contained in $B(x_{*},r)$, converges to $x_{*}$ and there
holds

$\displaystyle\|x_{k+1}-x_{*}\|\leq$
$\displaystyle\frac{\omega_{1}\beta\gamma}{(1-\gamma\|x_{0}-x_{*}\|)^{2}-\beta\gamma(2\|x_{0}-x_{*}\|-\gamma\|x_{0}-x_{*}\|^{2})}\|x_{k}-x_{*}\|^{2}$
$\displaystyle+$
$\displaystyle\left(\frac{\omega_{1}\sqrt{2}c\beta^{2}\gamma(2-\gamma\|x_{0}-x_{*}\|)}{(1-\gamma\|x_{0}-x_{*}\|)^{2}-\beta\gamma(2\|x_{0}-x_{*}\|-\gamma\|x_{0}-x_{*}\|^{2})}+\omega_{2}\right)\|x_{k}-x_{*}\|,$

for all $k=0,1,\ldots.$

Note that letting $c=0$ in the above corollary, we obtain the Example 1 of
[8].

##  4 Final remark

The Theorem 7 gives an estimate of the convergence radius for inexact Gauss-
Newton like methods. In particular, for $\vartheta=\omega_{1}=0$ and
$\omega_{2}=1$ is shown in Ferreira et al. [16], that $r$ is the best possible
convergence radius.

Another detail is that, as pointed out by Morini in [23] if preconditioning
$P_{k}$, satisfying

$\|P_{k}r_{k}\|\leq\theta_{k}\|P_{k}F^{\prime}(x_{k})^{*}F(x_{k})\|,$ (20)

for some forcing sequence $\\{\theta_{k}\\}$, is applied to finding the
inexact Gauss-Newton steep, then the inverse proportionality between each
forcing term $\theta_{k}$ and
$\mbox{cond}(P_{k}F^{\prime}(x_{k})^{*}F(x_{k}))$ stated in the following
assumption:

$0<\theta_{k}\mbox{cond}(P_{k}F^{\prime}(x_{k})^{*}F(x_{k}))\leq\vartheta,\qquad\;k=0,1,\ldots,$
(21)

is sufficient to guarantee convergence, and may be overly restrictive to bound
the sequence $\\{\theta_{k}\\}$, always such that the matrices
$P_{k}F^{\prime}(x_{k})^{*}F(x_{k})$, for $k=0,1,\ldots,$ are badly
conditioned. Moreover, $\theta_{k}$ does not depend on
$\mbox{cond}(F^{\prime}(x_{k})^{*}F(x_{k}))$ but only on the
$\mbox{cond}(P_{k}F^{\prime}(x_{k})^{*}F(x_{k}))$ and a suitable choice of
scaling matrix $P_{k}$ leads to a relaxation of the forcing terms.

## References

  * [1] R. L. Adler, J. P. Dedieu, J. Y. Margulies, M. Martens, and M. Shub.  Newton’s method on Riemannian manifolds and a geometric model for the human spine.  IMA J. Numer. Anal., 22(3):359–390, 2002.
  * [2] F. Alvarez, J. Bolte, and J. Munier.  A unifying local convergence result for Newton’s method in Riemannian manifolds.  Found. Comput. Math., 8(2):197–226, 2008.
  * [3] I. K. Argyros and S. Hilout.  Improved generalized differentiability conditions for Newton-like methods.  J. Complexity, In Press, Corrected Proof:–, 2010.
  * [4] L. Blum, F. Cucker, M. Shub, and S. Smale.  Complexity and real computation.  Springer-Verlag, New York, 1998.  With a foreword by Richard M. Karp.
  * [5] J. Chen.  The convergence analysis of inexact Gauss-Newton methods for nonlinear problems.  Comput. Optim. Appl., 40(1):97–118, 2008.
  * [6] J. Chen and W. Li.  Convergence of Gauss-Newton’s method and uniqueness of the solution.  Appl. Math. Comput., 170(1):686–705, 2005.
  * [7] J. Chen and W. Li.  Convergence behaviour of inexact Newton methods under weak Lipschitz condition.  J. Comput. Appl. Math., 191(1):143–164, 2006.
  * [8] J. Chen and W. Li.  Local convergence results of Gauss-Newton’s like method in weak conditions.  J. Math. Anal. Appl., 324(2):1381 – 1394, 2006.
  * [9] J. P. Dedieu and M. H. Kim.  Newton’s method for analytic systems of equations with constant rank derivatives.  J. Complexity, 18(1):187–209, 2002.
  * [10] J. P. Dedieu, P. Priouret, and G. Malajovich.  Newton’s method on Riemannian manifolds: covariant alpha theory.  IMA J. Numer. Anal., 23(3):395–419, 2003.
  * [11] J. P. Dedieu and M. Shub.  Newton’s method for overdetermined systems of equations.  Math. Comp., 69(231):1099–1115, 2000.
  * [12] R. S. Dembo, S. C. Eisenstat, and T. Steihaug.  Inexact Newton methods.  SIAM J. Numer. Anal., 19(2):400–408, 1982.
  * [13] J. E. Dennis, Jr. and R. B. Schnabel.  Numerical methods for unconstrained optimization and nonlinear equations, volume 16 of Classics in Applied Mathematics.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996.  Corrected reprint of the 1983 original.
  * [14] O. P. Ferreira.  Local convergence of Newton’s method in Banach space from the viewpoint of the majorant principle.  IMA J. Numer. Anal., 29(3):746–759, 2009.
  * [15] O. P. Ferreira and M. L. N. Goncalves.  Local convergence analysis of inexact Newton-like methods under majorant condition.  Comput. Optim. Appl., Article in Press:1–21, 2009.
  * [16] O. P. Ferreira, M. L. N. Goncalves, and P. R. Oliveira.  Local convergence analysis of gauss-newton’s method under majorant condition. To appear in  J. Complexity, 1–20, 2010.
  * [17] O. P. Ferreira and B. F. Svaiter.  Kantorovich’s majorants principle for Newton’s method.  Comput. Optim. Appl., 42(2):213–229, 2009.
  * [18] J.-B. Hiriart-Urruty and C. Lemaréchal.  Convex analysis and minimization algorithms. I, volume 305 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].  Springer-Verlag, Berlin, 1993.  Fundamentals.
  * [19] L. V. Kantorovich.  The principle of the majorant and Newton’s method.  Doklady Akad. Nauk SSSR (N.S.), 76:17–20, 1951.
  * [20] C. Li, N. Hu, and J. Wang.  Convergence behavior of Gauss-Newton’s method and extensions of the smale point estimate theory.  J. Complexity, In Press, Corrected Proof:–, 2010.
  * [21] C. Li, W. H. Zhang, and X. Q. Jin.  Convergence and uniqueness properties of Gauss-Newton’s method.  Comput. Math. Appl., 47(6-7):1057–1067, 2004.
  * [22] J. M. Martinez and L. Qi.  Inexact Newton methods for solving nonsmooth equations.  J. Comput. Appl. Math., 60:127–145, 1999.
  * [23] B. Morini.  Convergence behaviour of inexact Newton methods.  Math. Comp., 68:1605–1613, 1999.
  * [24] P. D. Proinov.  General local convergence theory for a class of iterative processes and its applications to Newton’s method.  J. Complexity, 25(1):38 – 62, 2009.
  * [25] P. D. Proinov.  New general convergence theory for iterative processes and its applications to Newton-Kantorovich type theorems.  J. Complexity, 26(1):3 – 42, 2010.
  * [26] S. Smale.  Newton’s method estimates from data at one point.  In The merging of disciplines: new directions in pure, applied, and computational mathematics (Laramie, Wyo., 1985), pages 185–196. Springer, New York, 1986.
  * [27] G. W. Stewart.  On the continuity of the generalized inverse.  SIAM J. Appl. Math., 17:33–45, 1969.
  * [28] X. Wang.  Convergence of Newton’s method and uniqueness of the solution of equations in Banach space.  IMA J. Numer. Anal., 20(1):123–134, 2000.
  * [29] P. A. Wedin.  Perturbation theory for pseudo-inverses.  Nordisk Tidskr. Informationsbehandling (BIT), 13:217–232, 1973\.


# AI and the Sense of Self

Srinath Srinivasa<EMAIL_ADDRESS>0000-0001-9588-6550 and  Jayati Deshmukh
<EMAIL_ADDRESS>International Institute of Information
Technology26/C, Electronics City Phase 1BangaloreKarnatakaIndia560100

###### Abstract.

After several winters, AI is center-stage once again, with current advances
enabling a vast array of AI applications. This renewed wave of AI has brought
back to the fore several questions from the past, about philosophical
foundations of intelligence and commonsense– predominantly motivated by
ethical concerns of AI decision-making. In this paper, we address some of the
arguments that led to research interest in intelligent agents, and argue for
their relevance even in today’s context. Specifically we focus on the
cognitive sense of “self” and its role in autonomous decision-making leading
to responsible behaviour. The authors hope to make a case for greater research
interest in building richer computational models of AI agents with a sense of
self.

machine ethics, autonomous agents, reinforcement learning, sense of self

††ccs: Computing methodologies Philosophical/theoretical foundations of
artificial intelligence

##  1\. Introduction

“Artificial Intelligence” or AI, a term coined by Minsky and McCarthy in
1956111History of Artificial Intelligence
https://en.wikipedia.org/wiki/History_of_artificial_intelligence, has evolved
into a veritable global vision and dream, evoking interest from not just
researchers, but also practitioners, artists, writers, policy makers, and the
general public. Like most fields of study, AI has gone through several waves
interspersed by periods of relative insignificance– the so called “AI
winters.”

Each wave of AI resurgence has been characterized by specific forms of
conceptual advancements– like formal logic, artificial neural networks,
intelligent agents, subsumption architecture, etc. The current resurgence in
interest in AI is perhaps unique in that regard, since arguably, the primary
catalyst for this new wave comes from advances in hardware, especially
Graphical Processing Units (GPUs), re-purposed for massive parallel processing
of Artificial Neural Networks. This wave is hence driven more by AI
applications and deployments, rather than by conceptual breakthroughs.
Although in the last decade, there have been several new advances in deep-
learning architectures, autonomous agents and robotic interaction models,
arguably, none of them constitute a paradigmatic departure from earlier
models.

This also implies that much of the open questions and challenges posed by AI
from earlier times, have remained unanswered. Of significance is the issue of
machine ethics, which was once primarily a philosophical debate, but which has
now become center-stage with large-scale deployment of AI in different
application contexts.

Machine ethics refers to a family of disparate concerns. With data-heavy
applications like recommendation and personalization systems, biases in the
data or in the algorithmic design assumptions, can pose several ethical
concerns (Kirkpatrick, 2016; Hajian et al., 2016; Vorvoreanu et al., 2019).
Similarly, AI agents acting autonomously in order to achieve some objective,
may create several kinds of collateral damage with serious ethical
implications (Goodall, 2014; Tolmeijer et al., 2020).

For a large part, ethical considerations for machines have been specified
using normative constructs, and modeled as either a constraint satisfaction
problem or a constrained optimization problem. Different paradigms are used to
model underlying ethical guidelines. These include (Tolmeijer et al., 2020):
deontics (specification of what one ought to do), consequentialism (reasoning
based on expected consequences), modeling of an innate sense virtues in
agents, and particularism (context-specific ethical reasoning). In addition,
emerging areas like Artificial Moral Agents (AMA), Reflective Equilibrium
(RE), and Value Sensitive Design (VSD) have addressed formal modeling of
ethical frameworks as a fundamental design principle of AI systems (Jobin et
al., 2019; Daniels, 1979; Floridi and Sanders, 2004; Friedman, 1996; Friedman
et al., 2002; Fossa, 2018; Wallach et al., 2008, 2010).

However, this paper argues that our understanding of machine ethics is far
from complete, and that there is a need to reopen some of the philosophical
debates from the 1980s and 1990s about the nature of intelligence, and address
them in today’s context. There are fundamental issues with the way
“intelligence” is defined and modeled in present day AI systems, that create a
barrier for AI to reason about ethics seamlessly. Ethics and intelligence are
often assumed to be orthogonal, if not conflicting dimensions.

Most questions pertaining to modeling ethics, require some form of generalized
understanding of ethical principles, necessitating an element of “commonsense”
reasoning (Powers, 2006)– leading to yet another long-standing open issue,
that is typically relegated to “strong” AI or Artificial General Intelligence
(AGI).

Many such considerations led to the emergence of the field of Intelligent
Agents (IA), addressing issues like agency, autonomy, self-interest, and so
on. Multi-Agent Systems (MAS) extended on this concept, to model interacting
autonomous agents and their emergent properties. The field of multi-agent
systems have had to contend with issues of ethics and responsibility, when
self-interest from disparate agents interfere with one another. This lead to
the development of several forms of multi-agent negotiation protocols and
fairness constructs (Kraus, 1997; Panait and Luke, 2005; Vidal and Durfee,
2003).

While IA and MAS elicited a lot of research interest in the early 2000s, the
interest soon waned. This paper tries to bring back some of the key
philosophical arguments that lead to research interest in computational
modeling of agency, with the hope that some of them may provide promising
paths of inquiry for some of the pressing concerns of AI deployments today.

In particular, the authors propose to extend on some of the arguments around
agency, and propose that an “elastic sense of self” is a key ingredient that
can address disparate issues concerning self-interest, ethics and responsible
behaviour.

##  2\. Machines and Societies

Scientific and engineering models today are predominantly grounded in
Newtonian hermeneutics, where reality is considered to be built from
impersonal, inanimate matter, and causal relationships between them. This form
of thinking replaced earlier models of human inquiry, that were overtly
anthropomorphic. Hence for instance, we no longer consider an earthquake today
as an expression of “anger” of some God, but as a causal chain of tectonic
events leading to the catastrophe.

Newtonian hermeneutics has enabled us to build rich causal models of physical
phenomena, paving the way for machines and robots that are as versatile as
natural beings, if not more, as regards their mechanical abilities. However,
when such machinery needs to inter-operate in an ecosystem of sentient beings
like humans and animals, they pose great challenges, since there is no place
for anthropomorphic constructs like free-will, conscience, trust, desire,
anger, etc. as part of Newtonian hermeneutics. This makes a lot of social
constructs and communication paradigms inaccessible and inapplicable to
machines. For instance, “shaming” or expressing disapproval, disgust and anger
against a reprehensible act can act as a deterrent to a human; but machines
hitherto don’t respond to such expressive rhetoric. While we can appeal to the
conscience of a human wrong-doer to make them correct their actions, no such
mechanisms exist for interacting with AI that is about to do something
irresponsible.

To some extent, present day AI can be made to respond to rhetoric, by modeling
them as reinforcement signals from the environment. Indeed, in a number of AI
deployments, ethical issues are enforced by means of constraints and/or
reinforcements over an underlying adaptive logic (Abel et al., 2016;
Noothigattu et al., 2019).

But this only opens up deeper questions about how to bring about ethical and
responsible behaviour in the absence of relevant reinforcements and
constraints. A sense of ethics in humans are not always responses to external
reinforcements. Appeal to conscience of a person, is not the same as
deterrence by inducing the fear of penalty. Indeed, the system of external
reinforcements in the form of laws and social norms, are themselves an
emergent characteristic of complex interactions around ethics, among humans.
There is evidence that a sense of ethics and responsible behaviour is an
innate element of human nature (Bregman, 2020; Hamlin, 2013).

This leads us to ask whether there are some paradigmatic differences between
natural beings and artificial automation. Could it be that the idea of machine
ethics is itself an ill-posed problem? Could it be that machines today, lack
essential design elements that are present in natural beings, and that which
endow them with anthropomorphic abilities including their sense of ethics?

When we compare automation in nature, and that of human engineering, we can
immediately see a number of contrasts between an artificial machine (like a
car), and a natural being (like a tiger)– even in their mechanics.

Firstly, we can see that nature does not have wheels, and hardly if ever,
bases its mechanics on rotary motion. There are hardly any examples of motors,
pumps and turbines in nature that are based on rotary motion. In contrast, the
wheel is such a fundamental element of human engineering, that “don’t reinvent
the wheel” is an oft-repeated cliché. But, nature has not “invented” the wheel
at all!

Natural pumps, like the heart in animals, use contraction and expansion as a
means for pumping. Conventional mechanical engineering would call that an
inefficient design, since continuous contraction and expansion leads to
material fatigue and wear-and-tear. However, the heart beats continuously
throughout the lifetime of the natural being (60-100 years for average
humans), without ever taking a break– a feat that is very hard if not
impossible to achieve with more “efficient” motors built from conventional
engineering!

Clearly, paradigmatic differences between natural and artificial engineering
can lead to fundamental differences in engineering wisdom. What is clearly an
unwise design in one paradigm, is the design of choice in the other. Could
this paradigmatic difference hold the key for us to understand anthropomorphic
constructs that are an integral part of natural beings, but not of artificial
machines?

The paradigmatic difference between artificial and natural automation can be
summarized as the difference between a “machine” and a “society.”

Unlike machines, which are built from components custom-made for their
functionality, natural beings are modeled as a large “society” of autonomous
entities called cells. Cells are generic components, which in their nascent
stages (called stem cells), can be moulded into several different kinds of
functional agents, like muscles, nerves, cartilage, bone matter, tissue, etc.

The master-plan directing role distribution among the cells is encoded in an
organism’s genotype, or its genetic material. But unlike the “blueprint” of
machines, a genotype does not rigidly encode the phenotype (the resultant
organism). The structure and function of the phenotype is a combination of
both genetically encoded plan, and adjustments to its environment (nature and
nurture).

The logic that drives moulding of stem cells into specific forms of functional
roles is based on the economic demand from the “society” that makes up the
organism. Hence, a physically active organism creates a larger demand for
muscle cells to develop, much like growth in a particular sector (like say,
biotechnology) of a human society, creates a demand for more professionals to
be trained in this area.

Machine-oriented and society-oriented designs lead to some sharp differences
in engineering wisdom, as noted earlier. Society-oriented design needs to work
with building blocks that are autonomous, and act independently in their
individual interest. For the system of cells to work together as an organism,
the system needs to be such that acting in cooperation with other cells is far
more rationally lucrative than acting independently.

Cooperation does not mean that the collective will always overrides individual
autonomy. The autonomous nature of individual components makes organisms
immensely adaptive and self-sustaining. Organisms have intelligent responses
encoded throughout their being. This pervasive intelligence of societies
result in resilience and self-healing properties like responding to routine
issues like a scratch or a skin prick, in a subconscious manner– without
sometimes the brain (representing the collective society) even being aware of
it.

But by far, a characteristic feature of natural beings that has been largely
ignored by engineers, is the sense of “self” that pervades across all cells of
the organism. Cells have a sharp notion of “citizenship” to the being that
make them act with vigilance against “foreign” cells that infect the organism.
Even though each agent in the being is acting autonomously, there is also a
sense of “oneness” or “belongingness” to the being, that pervades across all
the agents.

When the organism strives to survive, it is the pervasive sense of self that
is sought to be maintained and preserved and not for instance, any particular
cell. It is also the pervasive sense of self, that is sought to be protected
against attacks in the form of infections, by the immune system.

The sense of self is also “elastic” in the sense that the being may sometimes
identify with other external entities or concepts, by attaching a part of its
sense of self, to that object. Identifying with an external entity means that,
the being contributes some part of its biological and cognitive processes
towards preserving and furthering the interests of the object of identity.

Hence, parents identifying with their children, or patriots identifying with
their country, or activists identifying with a cause, proactively invest their
efforts and mind towards the interests of their object of identity. This
elastic sense of self may also underlie the mirror neuron system (MNS) that is
thought to be the neurological basis for empathy (Rizzolatti and Craighero,
2005; Oberman et al., 2007).

We argue that modeling this elastic sense of self, holds the key for several
issues pertaining to responsible AI, and hope to elicit more research interest
in this area.

##  3\. Computational Modeling of Agency

Computational modeling of agency and autonomy began to elicit increasing
research interest starting from the late 1980s. A survey of different
computational models of agency may be found in (Srinivasa and Deshmukh, 2020).

Early models of agency focused on the proactive nature of autonomous agents,
implemented as software objects with an independent thread of execution. Later
on, logics based on intentionality and norms, tempered by an agent’s beliefs
and knowledge, were developed for modeling autonomy (Georgeff et al., 1998;
Rao and Georgeff, 1991). A third paradigm of agency were adaptive models
powered by reinforcement learning and extensive games (Lin, 1992; Shoham,
1993).

While the above approaches resulted in rich, proactive and adaptive behaviour,
questions still remained about what is meant by autonomy itself. Perhaps the
closest we have come to answering this question is to model autonomy using the
theory of rational choice (Panait and Luke, 2005; Boella and Lesmo, 2002).
Rational choice is represented by two elements, self-interest, and utility
maximization.

Foundations of rational choice and economic games come from the work of von
Neumann and Morgenstern (Morgenstern and Von Neumann, 1953), that is also now
called the “classical” model of rational choice. This theory is based on
representing self-interest in the form of preference functions between pairs
of choices. Ordinal preference relations between pairs of choices, are
converted to numerical payoffs based on equating expected payoffs of a
conflicting set of choices. For instance, suppose an agent prefers $A$ over
$B$ over $C$ (represented as $A>B>C$). Suppose now that the agent is presented
a choice, where Choice I returns $B$ with 100% certainty, and Choice II
returns either $A$ or $C$ with a probability of $p$ and $(1-p)$ respectively.
The value of $p$ at which the agent becomes indifferent between choices I and
II provides us a mechanism for assigning numerical payoff values to $A$, $B$
and $C$. The classical theory is also developed further, with a set of
axiomatic basis like methodological individualism, transitivity of
preferences, independence of choices, etc.

While classical rational choice theory is widely used in different application
areas, including modeling human behaviour and micro-economic models, it has
also received criticism from various quarters about how well it can model
human sense of agency. In his critique called “Rational Fools” (Sen, 1977),
Sen argues that our autonomy comes from our “sense of self” and it is too
simplistic to reduce our sense of self to a preference matrix between pairs of
choices. Specifically, Sen argues that humans display an innate sense of trust
and empathy towards others, and assume a basic level of trust to exist even
among self-interested strangers. If humans were to be strict rational
maximizers, then according to Sen, the following kinds of interactions would
be more commonplace (Sen, 1977):

> ”Where is the railway station?” he asks me. ”There,” I say, pointing at the
> post office, ”and would you please post this letter for me on the way?”
> ”Yes,” he says, determined to open the envelope and check whether it
> contains something valuable.

This critique of the classical model lead to the development of the theory of
rational empathy and welfare economics.

Similarly, Kahnemann and Tversky in their work called “prospect theory”
(Kahneman and Tversky, 2013), critique the classical model for its linear
model of utility from expected payoffs.

Figure 1. Contrasting derived utility between classical model and prospect
theory

Figure 1 contrasts the model of derived utility between the classical model
and prospect theory. Utility is also called “intrinsic payoff” and refers to
the value associated by the agent to an external payoff received.

Prospect theory identifies at least two characteristics of human valuation to
external payoffs– saturation, and risk aversion. Saturation refers to
diminishing valuation of returns with increasing returns. The first million
earned may be valued very highly, by a business, but by the time the business
earns 50 million, it is largely business as usual.

Similarly, humans value negative and positive payoffs differently. Humans are
known to be “risk averse” and value prospects of negative returns much more
negatively, than positive returns of the same worth. Hence an investment that
provides a guaranteed return of $x$ is valued higher than another investment
that returns either $0$ or $2x$ with equal probability.

Both saturation and risk-aversion can also be tagged back to our “sense of
self”. Risk aversion comes from our pursuit of homeostasis– preserving our
sense of self, making us more often to choose smaller but guaranteed returns,
over higher but riskier returns. Similarly, saturation can be explained by our
mind’s eternal quest for novelty or epistemic surprise (Clark, 2018), where
unexpected rewards are valued more than expected returns.

##  4\. An Elastic Sense of Identity

It is reasonably clear that the human sense of autonomy is much more than
rational choice, as described by the classical model. Critiques of the
classical model introduce several facets of our sense of self, including:
rational empathy, trust, homeostasis, foraging or epistemic novelty, risk
aversion, etc.

While we may be far from a comprehensive computational model of self, in this
work, we focus on a specific characteristic of our sense of self that may hold
the key for the innate sense of responsibility and ethics in humans. We call
this the elastic sense of self, extending over a set of external objects
called the identity set.

Our sense of self, is not limited to the boundaries of our physical being, and
often extends to include other objects and concepts from our environment. This
forms the basis for social identity (Jenkins, 2014) that builds a sense of
belongingness and loyalty towards something other than, or beyond one’s
physical being.

We model this formally as follows. Given an agent $a$, the sense of self of
$a$ is described as:

(1) $S(a)=(I,d_{a},\gamma_{a})$

Here $I$ is the set of identity objects, where $a\in I$. The agent itself
belongs to its set of identity objects. The set may contain any number of
other entities including other agents, collections of agents, or even abstract
concepts. The term $d_{a}:\\{a\\}\times I\rightarrow\Re^{+}$ represents the
“semantic distance” between $a$ and some object in its identity set, with
$d_{a}(a)=0$. The term $\gamma_{a}\in[0,1]$ represents an attenuation
parameter, indicating how fast does the sense of identity attenuate with
distance. The agent identifies with object at distance $d$ with an attenuation
of $\gamma_{a}^{d}$.

The “sense of self” of the agent describes how its internal valuation or
utility, is computed based on external rewards or payoffs that may be received
by elements of its identity set. For any element $o\in I$, let the term
$o_{i}$ refer to the payoff obtained by object $o$ in game (system) state $i$.

Given this, the utility derived by agent $a$ is computed as follows:

(2) $\displaystyle u_{i}(a)$ $\displaystyle=$
$\displaystyle\frac{1}{Z}\displaystyle\sum_{\forall o\in
I}\gamma_{a}^{d_{a}(o)}o_{i}$ (3) $\displaystyle Z$ $\displaystyle=$
$\displaystyle\displaystyle\sum_{\forall o\in I}\gamma_{a}^{d_{a}(o)}$

The above can be understood as a “unit” of self being attached in different
proportions to the objects in the identity set, based on their semantic
distance and attenuation rate. Since the distance from an agent to itself is
zero, this has the least attenuation.

|  | Player A
---|---|---
|  | C | D
Player B | C | 6, 6 | 0, 10
D | 10, 0 | 1, 1
Table 1. Prisoner’s Dilemma

To illustrate the impact of an elastic sense of identity, consider the game of
Prisoners’ Dilemma as shown in Table 1.

The Prisoners’ Dilemma (PD) represents a situation where players have to
choose to cooperate (C) or defect (D) on the other. When both players
cooperate, there are rewarded with a payoff (6 in the example). However, as
long as one of the players chooses to cooperate, the other player has a
temptation to defect, and end up with a much higher payoff (10 in the
example). Hence, a player choosing to cooperate, runs the risk of getting
exploited by the other player. And when both players choose to defect on the
other, they end up in a state of “anarchy” with a much lesser payoff (1 in the
example), than had they both chosen to cooperate.

When played as a one-shot transaction, there is no rational incentive for a
player to choose to cooperate. Regardless of whether a player is known to
choose cooperate or defect, it makes rational sense for the other player to
choose $D$ over $C$. The state $DD$ is also the Nash equilibrium, representing
the mutual best response by both players, given the choice of the other. The
choice $D$ strictly dominates over choice $C$, since regardless of what the
other player chooses, a player is better off choosing $D$ over $C$.

The only way players in a PD game find a rational incentive to cooperate, is
when the game is played in an iterated manner, with evolutionary adjustments
allowing players to change strategies over time (Axelrod and Hamilton, 1981).

However, with an elastic sense of identity, we can create a rational incentive
for the players to cooperate, even in a one-shot transaction. Instead of
working on strategies and payoffs, here we change the players’ sense of self,
to include the other player, to different extents.

Without loss of generality, consider player $A$, and let the payoff in game
state $i$ be denoted as $a_{i}$. With an elastic identity that includes the
other player in one’s identity set at a distance of 1, the derived utility of
player $A$ in game state $i$ is given by (from Eqn 2):

(4) $u_{i}(A)=\frac{1}{1+\gamma}[a_{i}+\gamma b_{i}]$

Figure 2. Change in expected utility with increased elasticity of sense of
self

The expected utility of a choice (either $C$ or $D$) is computed by the
utility accrued at all possible game states on making this choice, along with
the probability of this game state. Since we make no further assumptions, all
game states are considered equally probable. Hence, the expected utility for
choosing a given choice is computed as follows:

(5) $\displaystyle E_{A}(C)=0.5\cdot u_{CC}(A)+0.5\cdot u_{CD}(A)$ (6)
$\displaystyle E_{A}(D)=0.5\cdot u_{DC}(A)+0.5\cdot u_{DD}(A)$

Figure 2 plots the expected utility from choosing $C$ or $D$ over varying
values of $\gamma$ or the elasticity in one’s sense of self. When $\gamma=0$,
this becomes the usual PD game, where the expected utility from choosing $D$
is much higher than the expected utility from choosing $C$. However, as
$\gamma$ increases, with player $A$ identifying more and more with player $B$,
the expected utility of choosing $C$ overtakes that of choosing $D$, when
$\gamma=\frac{1}{3}$. At this value of $\gamma$ the sense of self is split
between one’s own interest and the other’s interest, in a ratio of
$\frac{3}{4}:\frac{1}{4}$.

When $\gamma=1$ the sense of self is evenly split between a player and the
other. In this state, the PD game effectively “flips over” with $C$ and $D$
swapping places with respect to expected utility. In this state, it makes as
much rational sense to choose to cooperate, as it made rational sense in the
conventional PD to choose to exploit the other. This seems to give credence to
the folk wisdom that a relationship between two persons is at its natural
ideal when each member feels as much for the other, as for themselves. In such
a state, cooperation is more appealing than selfish gains.

An elastic sense of self can be contrasted with other forms of pro-social
constructs that have inspired the design of fairness in artificial agents. We
look at a few of these constructs here.

### Pareto Optimality

One of the commonly used constructs for fairness is Pareto optimality
(Banerjee and Sen, 2007; De Jong et al., 2008). A game state is said to be
Pareto optimal, if it does not contain any “Pareto improvement” where an agent
can improve one’s payoffs by changing its choice, such that it does not result
in a reduced payoff for any other agent.

Figure 3. Pareto boundary and fairness

In the PD example, while game state $CC$ is not a Nash equilibrium, it is
Pareto optimal, since no player can switch to the other choice to get a better
payoff, without hurting the other. In this sense, “consideration for the
other” or “aversion to inequity in incremental payoffs” as an ethical
principle, can lead to cooperation.

However, Pareto optimality can also just as well result in grossly unfair
configurations. Figure 3 shows a two player game with several states. The set
of states in the “Pareto boundary” connected by the line, represent Pareto
optimal states. In these states, no player can change its choice to get a
better payoff for itself, without hurting the other. As we can see, the shaded
state, where Player $y$ has a negative payoff, is also on the Pareto boundary!

Pareto optimality, used by itself as a measure of responsible behaviour, can
also admit oppressive constructs as “fair” configurations.

### Altruism

Altruism or “selfless” behaviour where an agent “sacrifices” one’s own good
for the welfare of the other, or for the collective, is sometimes celebrated
as the epitome of pro-social responsibility.

However, as we can see from the PD game, while an altruist would be attracted
by the state $CC$, the game state $CD$ would also be attractive for an
altruist agent, since this gives the best possible payoff for the other
player.

Not being concerned about one’s own welfare, doesn’t necessarily lead to
responsible behaviour. Consider a surgeon or pilot sacrificing their sleep or
rest time to maximally serve their patients or passengers. They would be
putting them at risk rather than serving them.

An elastic sense of self on the other hand, does not put one’s own self in
conflict with the interests of others, nor does it invalidate one’s own
individuality for collective interests.

##  5\. Conclusions

The objective of this paper is to address the question of machine ethics in a
philosophical manner using foundations of human cognition, and propose a new
line of thinking for modeling responsibility in AI agents. An elastic sense of
self, as proposed in this paper, may be a foundational element for modeling
several forms of anthropomorphic constructs in AI, including machine ethics.

For future work, we plan to take up realistic agent-based applications
involving reinforcement learning, and introduce an elastic sense of self into
the learning agents. Preliminary work in this regard has yielded promising
results, with agents pursuing self-interest while being mindful of collateral
damage.

Elastic identity also opens up several new questions and opportunities for
research. Some of these questions include the following: underlying model for
deciding the elements of one’s identity set, semantic distance to each element
of one’s identity set, and the attenuation parameter. There are also questions
about how and when is the attenuation parameter set, and whether it changes
over time and with fruitful or adverse experiences.

At a systemic level, there are also open questions about the evolutionary
stability of a system of agents with elastic identity. Can a system of
empathetic agents be successfully “invaded” by a small group of non-empathetic
agents who don’t identify with others? Or does there exist a strategy for
deciding the optimal level of one’s empathy or extent of one’s identity set,
that makes it evolutionarily stable?

## References

  * (1)
  * Abel et al. (2016) David Abel, James MacGlashan, and Michael L Littman. 2016\.  Reinforcement Learning as a Framework for Ethical Decision Making.. In _AAAI Workshop: AI, Ethics, and Society_ , Vol. 16. Phoenix, AZ, 02.
  * Axelrod and Hamilton (1981) Robert Axelrod and William D Hamilton. 1981.  The evolution of cooperation.  _science_ 211, 4489 (1981), 1390–1396.
  * Banerjee and Sen (2007) Dipyaman Banerjee and Sandip Sen. 2007.  Reaching pareto-optimality in prisoner’s dilemma using conditional joint action learning.  _Autonomous Agents and Multi-Agent Systems_ 15, 1 (2007), 91–108.
  * Boella and Lesmo (2002) Guido Boella and Leonardo Lesmo. 2002.  A game theoretic approach to norms and agents.  (2002).
  * Bregman (2020) Rutger Bregman. 2020\.  _Humankind: A hopeful history_.  Bloomsbury Publishing.
  * Clark (2018) Andy Clark. 2018\.  A nice surprise? Predictive processing and the active pursuit of novelty.  _Phenomenology and the Cognitive Sciences_ 17, 3 (2018), 521–534.
  * Daniels (1979) Norman Daniels. 1979\.  Wide reflective equilibrium and theory acceptance in ethics.  _The journal of philosophy_ 76, 5 (1979), 256–282.
  * De Jong et al. (2008) Steven De Jong, Karl Tuyls, and Katja Verbeeck. 2008\.  Artificial agents learning human fairness. In _Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2_. 863–870.
  * Floridi and Sanders (2004) Luciano Floridi and Jeff W Sanders. 2004.  On the morality of artificial agents.  _Minds and machines_ 14, 3 (2004), 349–379.
  * Fossa (2018) Fabio Fossa. 2018\.  Artificial moral agents: moral mentors or sensible tools?  _Ethics and Information Technology_ 20, 2 (2018), 115–126.
  * Friedman (1996) Batya Friedman. 1996\.  Value-sensitive design.  _interactions_ 3, 6 (1996), 16–23.
  * Friedman et al. (2002) Batya Friedman, Peter Kahn, and Alan Borning. 2002\.  Value sensitive design: Theory and methods.  _University of Washington technical report_ 2-12 (2002).
  * Georgeff et al. (1998) Michael Georgeff, Barney Pell, Martha Pollack, Milind Tambe, and Michael Wooldridge. 1998.  The belief-desire-intention model of agency. In _International workshop on agent theories, architectures, and languages_. Springer, 1–10.
  * Goodall (2014) Noah J Goodall. 2014\.  Machine ethics and automated vehicles.  In _Road vehicle automation_. Springer, 93–102.
  * Hajian et al. (2016) Sara Hajian, Francesco Bonchi, and Carlos Castillo. 2016\.  Algorithmic bias: From discrimination discovery to fairness-aware data mining. In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_. 2125–2126.
  * Hamlin (2013) J Kiley Hamlin. 2013\.  Moral judgment and action in preverbal infants and toddlers: Evidence for an innate moral core.  _Current Directions in Psychological Science_ 22, 3 (2013), 186–193.
  * Jenkins (2014) Richard Jenkins. 2014\.  _Social identity_.  Routledge.
  * Jobin et al. (2019) Anna Jobin, Marcello Ienca, and Effy Vayena. 2019\.  The global landscape of AI ethics guidelines.  _Nature Machine Intelligence_ 1, 9 (2019), 389–399.
  * Kahneman and Tversky (2013) Daniel Kahneman and Amos Tversky. 2013.  Prospect theory: An analysis of decision under risk.  In _Handbook of the fundamentals of financial decision making: Part I_. World Scientific, 99–127.
  * Kirkpatrick (2016) Keith Kirkpatrick. 2016\.  Battling algorithmic bias: How do we ensure algorithms treat us fairly?  _Commun. ACM_ 59, 10 (2016), 16–17.
  * Kraus (1997) Sarit Kraus. 1997\.  Negotiation and cooperation in multi-agent environments.  _Artificial intelligence_ 94, 1-2 (1997), 79–97.
  * Lin (1992) Long-Ji Lin. 1992\.  Self-improving reactive agents based on reinforcement learning, planning and teaching.  _Machine learning_ 8, 3-4 (1992), 293–321.
  * Morgenstern and Von Neumann (1953) Oskar Morgenstern and John Von Neumann. 1953.  _Theory of games and economic behavior_.  Princeton university press.
  * Noothigattu et al. (2019) Ritesh Noothigattu, Djallel Bouneffouf, Nicholas Mattei, Rachita Chandra, Piyush Madan, Kush R Varshney, Murray Campbell, Moninder Singh, and Francesca Rossi. 2019\.  Teaching AI agents ethical values using reinforcement learning and policy orchestration.  _IBM Journal of Research and Development_ 63, 4/5 (2019), 2–1.
  * Oberman et al. (2007) Lindsay M Oberman, Jaime A Pineda, and Vilayanur S Ramachandran. 2007\.  The human mirror neuron system: a link between action observation and social skills.  _Social cognitive and affective neuroscience_ 2, 1 (2007), 62–66.
  * Panait and Luke (2005) Liviu Panait and Sean Luke. 2005.  Cooperative multi-agent learning: The state of the art.  _Autonomous agents and multi-agent systems_ 11, 3 (2005), 387–434.
  * Powers (2006) Thomas M Powers. 2006\.  Prospects for a Kantian machine.  _IEEE Intelligent Systems_ 21, 4 (2006), 46–51.
  * Rao and Georgeff (1991) Anand S Rao and Michael P Georgeff. 1991.  Modeling rational agents within a BDI-architecture.  _KR_ 91 (1991), 473–484.
  * Rizzolatti and Craighero (2005) Giacomo Rizzolatti and Laila Craighero. 2005.  Mirror neuron: a neurological approach to empathy.  In _Neurobiology of human values_. Springer, 107–123.
  * Sen (1977) Amartya K Sen. 1977\.  Rational fools: A critique of the behavioral foundations of economic theory.  _Philosophy & Public Affairs_ (1977), 317–344.
  * Shoham (1993) Yoav Shoham. 1993\.  Agent-oriented programming.  _Artificial intelligence_ 60, 1 (1993), 51–92.
  * Srinivasa and Deshmukh (2020) Srinath Srinivasa and Jayati Deshmukh. 2020.  The Evolution of Computational Agency.  In _Novel Approaches to Information Systems Design_. IGI Global, 1–19.
  * Tolmeijer et al. (2020) Suzanne Tolmeijer, Markus Kneer, Cristina Sarasua, Markus Christen, and Abraham Bernstein. 2020\.  Implementations in machine ethics: A survey.  _ACM Computing Surveys (CSUR)_ 53, 6 (2020), 1–38.
  * Vidal and Durfee (2003) José M Vidal and EH Durfee. 2003.  Multiagent systems.  _The Handbook of Brain Theory and Neural Networks_ (2003).
  * Vorvoreanu et al. (2019) Mihaela Vorvoreanu, Lingyi Zhang, Yun-Han Huang, Claudia Hilderbrand, Zoe Steine-Hanson, and Margaret Burnett. 2019.  From gender biases to gender-inclusive design: An empirical investigation. In _Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems_. 1–14.
  * Wallach et al. (2008) Wendell Wallach, Colin Allen, and Iva Smit. 2008.  Machine morality: bottom-up and top-down approaches for modelling human moral faculties.  _Ai & Society_ 22, 4 (2008), 565–582.
  * Wallach et al. (2010) Wendell Wallach, Stan Franklin, and Colin Allen. 2010\.  A conceptual and computational model of moral decision making in human and artificial agents.  _Topics in cognitive science_ 2, 3 (2010), 454–485.


* [58] C.R. Harris, K.J. Millman, S.J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau et al., _Array programming with NumPy_ , _Nature_ 585 (2020) 357–362.
  * [59] P. Virtanen, R. Gommers, T.E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau et al., _SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python_ , _Nature Methods_ 17 (2020) 261.
  * [60] J.D. Hunter, _Matplotlib: A 2d graphics environment_ , _Computing in Science Engineering_ 9 (2007) 90.