• $\gdef\xbar{\bar{x}}F(\xbar) = 0$
• $F:\bbRn \to \bbRn$ is Newton differentiable at $\xbar$ with $\mathcal{H}F$
• $\sup_{x \in U \in \mathcal{V}(\xbar)} \sup_{H \in \mathcal{H}F(x)}\|H^{-1}\| \le \Omega$

Then any Newton-type method converges superlinearly for any $x^0$ close enough to $\xbar$

$F:\bbRn \to \bbRn$ is $\mathcal{C}^1$ on a convex set $\Rightarrow$ $F$ Newton differentiable with $\mathcal{H}F = \nabla F$

1. $\forall {\{t_k\}}_{k \in \bbN} > 0$, ${\{d^k\}}_{k \in \bbN}$ convergent
2. ${\{H^k\}}_{k \in \bbN} \in \partial^c F(\xbar + t_k d^k)$, $\lim_{k \to \infty} H^k(\lim_{n \to \infty}d_n)$ exists
3. \[\lim_{x \to \xbar}\frac{\|F'(x; x - \xbar) - F'(\xbar; x - \xbar)\|}{\|x - \xbar\|} = 0\]

\(\gdef\graph{\operatorname{Graph}}\)$\graph F \in \mathcal{O}^{2n}$,

1. $\forall n$, $\mathcal{O}^n \subseteq \bbRn$ is a boolean algebra
2. $S \in \mathcal{O}^n$ implies \(\gdef\bbR{\mathbb{R}}\)$S \times \bbR \in \mathcal{O}^{n+1}$ and $\{(x_1, \dots, x_{n-1}~|~\exists y,~(x_1, \dots, x_{n-1}, y) \in S)\} \in \mathcal{O}^{n-1}$
3. $\mathcal{O}^1$ is the set of semi-algebraic sets and $\{(x_1, x_2)~|~x_1, \le x_2\} \in \mathcal{O}^2$

• $F(\xbar) = 0$
• $F:\bbRn \to \bbRn$ is weakly Newton differentiable at $\xbar$ with $\mathcal{H}F$
• $\sup_{x \in U \in \mathcal{V}(\xbar)} \sup_{H \in \mathcal{H}F(x)}\|H^{-1}\| \le \Omega$
• $\Omega\lim_{x \to \xbar}\sup_{H \in \mathcal{H}F(x)}\|F(x) - F(\xbar) - H(x - \xbar)\| \le \|x - \xbar\|$

Then Newton-type method converges linearly for any $x^0$ close enough to $\xbar$

Holds if

• $F$ is $L$-Lipschitz
• $F$ is hypo-monotone \[ \exists \alpha > 0, \forall x, y \in U, \quad \langle F(x) - F(y), x - y \rangle \ge -\alpha \|x - y\|^2 \]
• $F$ is metric subregular \[\exists \kappa > 0, \forall x \in U,\quad \|x - \xbar\| \le \kappa\inf \{\|H^{-1}F(x)\|~|~H \in \mathcal{H}(x)\}\]
• $\lambda^2 + 2M\lambda + \lambda^{-2}L^2 - \kappa\lambda(1-\lambda) < \lambda$

Holds if

• $f$ has the KŁ property i.e. $\exists\phi:[0, \infty) \to [0, \infty)$ in $\mathcal{C}^{1}$ with $\phi(0) = 0$ and $\phi$ increasing \[\phi'(f(x) - f(\xbar))\|\nabla f(x)\| \ge 1 \]
  '
• ${\{x^k\}}_{k \in \bbN}$ has sufficient decrease i.e. \[\exists \rho > 0, \forall k \in \bbN,\quad \rho\|x^{k+1} - x^k\|^2 \le f(x^{k}) - f(x^{k+1}) \]
• ${\{x^k\}}_{k \in \bbN}$ has a gradient lower bound i.e. \[\exists \rho > 0, \forall k \in \bbN,\quad \|\nabla f(x^k)\| \ge \rho\|x^{k + 1} - x^k\| \]

• $F(\xbar) = 0$
• $F:\bbRn \to \bbRn$ is Newton differentiable at $\xbar$ with $\mathcal{H}F$
• $\sup_{x \in U \in \mathcal{V}(\xbar)} \sup_{H \in \mathcal{H}F(x)}\|H^{-1}\| \le \Omega$

Then any Newton-type method converges superlinearly for any $x^0$ close enough to $\xbar$

• If $F$ is Newton differentiable on a set, with $\gdef\tbar{\bar{t}}\mathcal{H}F$ Hölder continuous, \[\|\mathcal{H}F(x) - \mathcal{H}F(y)\| \le L\|x - y\|^{\gamma-1}\]
• $B := \|{\mathcal{H}F(x^0)}^{-1}\|$ and $\eta := \|{\mathcal{H}F(x^0)}^{-1}F(x^0)\|$,

  \[\begin{aligned} &\frac{LB}{2}{\left(\frac{f(t)}{f'(t)}\right)}^\gamma \le f\left(t - \frac{f(t)}{f'(t)}\right), & f(0) = \eta,\quad f(t) > 0,\quad f(\tbar) = 0, \\ &f'(t) < 0,\quad f'(t) \ge {(1 + L t)}^{-1}, &f''(t) > 0 \end{aligned} \]'

then $\exists \xbar$ such that $F(\xbar) = 0$

1. $\forall {\{t_k\}}_{k \in \bbN} > 0$, ${\{d^k\}}_{k \in \bbN}$ convergent
2. ${\{H^k\}}_{k \in \bbN} \in \partial^c F(\xbar + t_k d^k)$, $\lim_{k \to \infty} H^k(\lim_{n \to \infty}d_n)$ exists
3. \[\forall \epsilon, \exists \delta, \forall \xbar \in V,\quad\|\xbar - x\| \le \delta\Rightarrow \frac{\|F'(x; x - \xbar) - F'(\xbar; x - \xbar)\|}{\|x - \xbar\|} \le \epsilon \]

$\nabla F$ is uniformly Newton differentiable on $V$ with Newton differential $\mathcal{H}F$ $\Rightarrow$ $G$ is uniformly Newton differentiable on $V$ with Newton differential $\mathcal{H}G(x, \sigma) = \sigma^T\mathcal{H}F(x) \times \{\Id\}$

Using the assumptions $\Rightarrow$ sufficient decrease i.e. \[\exists \rho, \forall x, \forall x^{+} \in \{x - H^{-1}\partial_1 f(x)~|~H \in \mathcal{H}f(x)\},\quad f(x) - f(x^+) \ge \rho \|x^{+} - x\|^2\]

Using assumption, given $\varepsilon > 0$  and $\exists \delta$ \[\forall x\quad\mathbb{P}(\mathbb{H}(x)^{-1} \in \mathcal{H}f(x)) \ge 1 - \delta\]

$K$ is the random number of iterations until the algorithm terminates

$\Rightarrow$ $\exists \rho$, $\exists \tau$ \[\gdef\bbE{\mathbb{E}}\bbE(K) \le \frac{1}{1 - \delta}\left( \frac{f(x^0) - f(\xbar)}{\rho{(\tau\varepsilon)}^2} + \frac{\log \frac{\rho}{c^0}}{\log \alpha } \right) \]

$\forall \gamma \in (0, 1)$ \[\gdef\bbP{\mathbb{P}} \bbP\left(K \ge \frac{2 + \gamma(1 - \gamma^2)}{1 - \gamma} \bbE(K)\right) \le e^{-\gamma^2\bbE(K)} \]

Using assumption, given $\varepsilon > 0$  and $\exists \delta$ \[\forall x\quad\mathbb{P}(\mathbb{H}(x)^{-1} \in \mathcal{H}f(x)) \ge 1 - \delta\]

The algorithm run for $K$ steps

$\Rightarrow$ $\exists \rho$, $\exists \tau$ \[\bbP\left(\min_{n \le K} \|\partial_1 f(x^n)\| \ge \sqrt{\frac{f(x^0) - f(\xbar)}{\rho\tau^2 \left((1 - \gamma)K - \frac{\log \frac{\rho}{c_0}}{\log \alpha } \right)}} \right) \le e^{-K(1 - \delta)\frac{\gamma^2}{2}} \]

• $F:\bbRn \to \bbRn$ is Newton differentiable at $\xbar$ with $\mathcal{H}F$
• $\proj_{\ker A} F(\xbar) = 0$
• $\sup_{x \in U \in \mathcal{V}(\xbar)} \sup_{H \in \mathcal{H}F(x)}\|{\proj_{\ker A}H\proj_{\ker A}}^{-1}\| \le \Omega$

Then any Newton-type method converges superlinearly for any $x^0$ close enough to $\xbar$