A common question that an estate planning attorney gets asked is how to obtain a copy of a deceased person's last will and testament or other probate court filings. Since probate records are public court records that anyone can read, if a will has been filed for probate, then you should be able to obtain a copy of it. With modern technology comes the ability to locate information about a deceased person's estate online, and in most cases for absolutely free.
While you may not be able to view copies of the actual will and other documents that have been filed with the probate court for free, at the very least you will be able to see a list of the documents that have been filed, who has been named as the executor of the estate, which attorney the executor has hired, and the name of the judge presiding over the case.
Some courts even list the names of all of the beneficiaries of the estate. This will then give you the ability to request copies of the will and any other documents you are interested in viewing from the probate clerk's office, or you can try contacting the executor or the executor's attorney for additional information.
An estate is probated in the county where the deceased person lived at the time of his or her death, or, in some cases, the county where the deceased person owned real estate. Use the following website to locate the correct name of the county by plugging in the name of the city where the deceased person lived or owned real estate: City - County Search.
Once you have located the appropriate county, an online search can be done for that county's probate court or probate court dockets. This can be tricky because in some states the probate court is not actually called the probate court, it could be referred to as the "circuit court," "surrogate's court," "orphan's court," or any other number of courts. Be persistent - since probate occurs in each and every county across the country, chances are you will be able to locate the appropriate court's online information.
Appearing in person and asking for a copy of the will or other probate documents, or making a written request by fax or mail if applying in person is not feasible.
Paying a copying fee for the number of pages that the will or other probate document contains. These fees usually range from $1.00 to a few dollars per page.
Providing a self-addressed, stamped envelope for mailing the copies if the request is not made in person.
If the estate you are interested in is being probated in the Seminole County Circuit Court located in Sanford, Florida, then this county does not currently have its probate dockets available online. Instead, you will need to call the probate department of the Seminole County clerk's office at (407)665-4328 and ask them about their procedures for obtaining copies of probate court records and the costs involved. The clerk's website can be accessed by following this link: Seminole County Clerk of Courts.
If the decedent lived in one of these cities or owned real estate located in one of these cities, then contact the Seminole County clerk's office as indicated above.


Saturday was important for Texas State.
It was senior day, and the Bobcats made sure their three senior student-athletes, Ana Perez, Julia Navajo-Melendez and Joy Chia Ming Ming, knew how much they were appreciated by the team.
The seniors, in turn, helped lead the maroon and gold to its second Sun Belt victory of the season, sweeping Arkansas State, 4-0.
Texas State's first victory came from Perez, who defeated her opponent in straight sets, 6-3, 6-3. Sophomore Rishona Israel-Lewis came next. She dropped her first set, 6-2, but came back in the next, winning 6-4, and sealed the match by taking the third set 6-3.
Navajo-Melendez had the tightest match of the day. She cruised to a 6-4 win in the first set, but fell in the next, 6-4. It took an extra point, but the senior got the final victory in a 7-5 third set.
Chia Ming Ming sealed the sweep for the hosts, winning 6-3 and 7-5.
The win moves the Bobcats to ninth place in the conference, just half a game behind Georgia Southern and Georgia State, who are currently tied for the No. 7 seed.
Texas State (6-10, 2-5 Sun Belt) and its seniors will play in their final home series of the season on Tuesday when the team hosts UT Arlington (13-7, 4-2) inside the Bobcat Tennis Complex at 1 p.m.


We offered the get free members of memon news.
We offered the jobs and intership for the community.
We will provide marriage panel as soon as possible.
Life/ death are the part of the life. Be always ready for that.
All the latest offers are available for your kind consideration.
Building the future of the society with diversified efforts.


NPR Research, Archives & Data Strategy's (RAD) Olympus team is seeking a Music Metadata intern. You will work closely with the product owner of Orpheus, NPR's music and spoken word database. We are evaluating the product's content, features and more, so you will have a chance to influence the future of music storage and retrieval at NPR. Team Olympus uses Agile Methodology (Scrum) to plan and execute software development.
Propose, evaluate and test new features or bug repairs for database.
Create and edit music metadata.
Evaluate quality of music metadata from open source or commercial sources.
Participate in daily scrum to keep Olympus team members up to date with progress.
Participate in bi-weekly presentations for the rest of the RAD team and other Olympus stakeholders.
Regularly check in with product owner regarding tasks, ongoing progress and objectives.
A thriving, mission-driven multimedia organization, NPR produces award-winning news, information, and music programming in partnership with hundreds of independent public radio stations across the nation. NPR listeners value information, creativity, curiosity, and social responsibility – our employees do too. We are innovators and leaders in diverse fields, from journalism and digital media to software design and development. Every day our employees and member stations touch the lives of millions worldwide.
Our best internship candidates are passionate about metadata, music and information science. You should be good at managing your time and deadlines, communicating in all ways digital and non, and working accurately – both on your own and with others on our team.


text:
\section{#1}\setcounter{equation}{0}}
\newcommand{\appnumsection}[1]{\section*{#1}\setcounter{equation}{0}
  \renewcommand{\theequation}{A.\arabic{equation}}
  \renewcommand{\thetheorem}{A.\arabic{theorem}}
  \renewcommand{\thetable}{A.\arabic{table}}
  \renewcommand{\thefigure}{A.\arabic{figure}}
  \renewcommand{\thesection}{A} }
\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\renewcommand{\thetable}{\arabic{section}.\arabic{table}}
\renewcommand{\thefigure}{\arabic{section}.\arabic{figure}}
\renewcommand{\thefootnote}{(\arabic{footnote})}
\newcommand{{\cal A}}{{\cal A}}
\newcommand{{\cal M}}{{\cal M}}
\newcommand{{\cal N}}{{\cal N}}
\newcommand{{\cal O}}{{\cal O}}
\newcommand{{\cal S}}{{\cal S}}
\newcommand{{\cal X}}{{\cal X}}
\newcommand{\beqn}[1]{\begin{equation}\label{#1}}
\newcommand{\end{equation}}{\end{equation}}
\newcommand{\ii}[1]{\{1, \ldots, #1 \}}
\newcommand{\iiz}[1]{\{0, \ldots, #1 \}}
\newcommand{\iibe}[2]{\{ #1, \ldots, #2 \}}
\newcommand{f_{\rm low}}{f_{\rm low}}
\newcommand{\overline{\phi}}{\overline{\phi}}
\newcommand{\widetilde{\overline{\phi}}}{\widetilde{\overline{\phi}}}
\newcommand{\Delta T}{\Delta T}
\newcommand{\overline{\Delta T}}{\overline{\Delta T}}
\newcommand{{\footnotesize {\sf SAR$qp$} }}{{\footnotesize {\sf SAR$qp$} }}
\newcommand{\mathbb{E}}{\mathbb{E}}
\newcommand{\mathbbm{1}_}{\mathbbm{1}_}
\newcommand{\no}[1]{#1^c}
\newcommand{\calM}{{\cal M}}
\newcommand{\indic{\AM_k}}{\mathbbm{1}_{\calM_k}}
\newcommand{\indic{\no{\AM_k}}}{\mathbbm{1}_{\no{\calM_k}}}
\newcommand{\indic{\calS_k}}{\mathbbm{1}_{{\cal S}_k}}
\newcommand{\indic{\no{\calS_k}}}{\mathbbm{1}_{\no{{\cal S}_k}}}
\newcommand{\mathbb{P}{\rm r}}{\mathbb{P}{\rm r}}
\newcommand{\calA_{k-1}^{M}}{{\cal A}_{k-1}^{M}}
\newcommand{\calX}{{\cal X}}
\newcommand{p_*}{p_*}
\newcommand{\sfrac}[2]{{\scriptstyle \frac{#1}{#2}}}
\newcommand{\sfrac{1}{2}}{\sfrac{1}{2}}
\newcommand{\sfrac{1}{4}}{\sfrac{1}{4}}
\newcommand{\tim}[1]{\;\; \mbox{#1} \;\;}
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\stackrel{\rm def}{=}}{\stackrel{\rm def}{=}}
\newcommand{\;\;\;\;}{\;\;\;\;}
\newcommand{\overline{d}}{\overline{d}}
\newcommand{\overline{f}}{\overline{f}}
\newcommand{\overline{D}}{\overline{D}}
\newcommand{\overline{S}}{\overline{S}}
\newcommand{\overline{T}}{\overline{T}}
\newcommand{\bigfrac}[2]{\frac{\displaystyle #1}{\displaystyle #2}}
\newcommand{\displaystyle \sum}{\displaystyle \sum}
\newcommand{\displaystyle \max}{\displaystyle \max}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{algorithm}{Algorithm}[section]
\newtheorem{definition}{Definition}
\newcommand{\llem}[2]{\vspace{\baselineskip}
\noindent\framebox[\textwidth]{\parbox{0.95\textwidth}{
\begin{lemma} \label{#1} \rm #2 \end{lemma} } } \vspace{\baselineskip} }
\newcommand{\lthm}[2]{\vspace{\baselineskip}
\noindent\framebox[\textwidth]{\parbox{0.95\textwidth}{
\begin{theorem} \label{#1} \rm #2 \end{theorem} } } \vspace{\baselineskip} }
\newcommand{{\bf Proof.} \hspace{1.5mm}}{{\bf Proof.} \hspace{1.5mm}}
\newcommand{\hfill $\Box$ \vspace*{1em}}{\hfill $\Box$ \vspace*{1em}}
\newcommand{\proof}[1]{
\begin{list}{}{
\setlength{\topsep}{0.0pt}
\setlength{\partopsep}{0.0pt}
\setlength{\leftmargin}{0.025\textwidth}
\setlength{\rightmargin}{0.5\leftmargin}
\setlength{\labelwidth}{0.5\leftmargin}
\setlength{\labelsep}{0.25\leftmargin}}
\item {\bf Proof.} \hspace{1.5mm} #1 \hfill $\Box$ \vspace*{1em} \noindent
\end{list}}
\newcounter{algo}[section]
\renewcommand{\thealgo}{\thesection.\arabic{algo}}
\newcommand{\algo}[3]{\refstepcounter{algo}
\begin{center}\begin{figure}[htbp]
\framebox[\textwidth]{
\parbox{0.95\textwidth} {\vspace{\topsep}
{\bf Algorithm \thealgo : #2}\label{#1}\\
\vspace*{-\topsep} \mbox{ }\\
{#3} \vspace{\topsep} }}
\end{figure}\end{center}}
\newcommand{\al}[1]{{\footnotesize{\sf #1}}}
\newcommand{{\tt accuracy}}{{\tt accuracy}}
\newcommand{{\tt accuracy}$_s$\,}{{\tt accuracy}$_s$\,}
\newcommand{{\tt accuracy}$_j$\,}{{\tt accuracy}$_j$\,}
\newcommand{{\tt insufficient}}{{\tt insufficient}}
\newcommand{{\tt terminal}}{{\tt terminal}}
\newcommand{{\tt absolute}}{{\tt absolute}}
\newcommand{{\tt relative}}{{\tt relative}}
\newcommand{{\tt status}}{{\tt status}}
\newcommand{{\tt order}}{{\tt order}}
\newcommand{{\tt delta}}{{\tt delta}}
\newcommand{{\tt radius}}{{\tt radius}}
\newcommand{{\tt in-noise-phi}}{{\tt in-noise-phi}}
\newcommand{{\tt in-noise-s}}{{\tt in-noise-s}}
\newcommand{{\tt in-noise-f}}{{\tt in-noise-f}}
\newcommand{{\tt approximate-minimizer}}{{\tt approximate-minimizer}}
\newcommand{\widehat{\phi}}{\widehat{\phi}}
\newcommand{\epsilon_{\min}}{\epsilon_{\min}}
\renewcommand{\Re}{\mathbb{R}}

\topmargin -10truept
\pagestyle{myheadings}
\markright{Bellavia, Gurioli, Morini, Toint: Noise and Complexity for
  Trust-Region methods}

\title{The Impact of Noise on Evaluation Complexity: \\ The Deterministic Trust-Region Case}

\author{
  S. Bellavia\thanks{Dipartimento di Ingegneria Industriale,
    Universit\`{a} degli Studi di Firenze, Italy. Member of the INdAM Research
    Group GNCS. Email: stefania.bellavia@unifi.it},
  G. Gurioli\thanks{Dipartimento di Matematica e Informatica ``Ulisse Dini'',
    Universit\`{a} degli Studi di Firenze, Italy.  {Member of the INdAM Research
    Group GNCS.} Email: gianmarco.gurioli@unifi.it},
  B. Morini\thanks{Dipartimento di Ingegneria Industriale,
    Universit\`{a} degli Studi di Firenze, Italy. Member of the INdAM Research
    Group GNCS. Email: benedetta.morini@unifi.it} \ and
  Ph. L. Toint\thanks{ Namur Center for Complex Systems (naXys),
    University of Namur, 61, rue de Bruxelles, B-5000 Namur, Belgium.
    Email: philippe.toint@unamur.be}
}

\date{6 IV 2021}

\begin{document}

\maketitle

\begin{abstract}
Intrinsic noise in objective function and derivatives evaluations may cause
premature termination of optimization algorithms. Evaluation complexity bounds
taking this situation into account are presented in the framework of a
deterministic trust-region method. The results show that the presence of
intrinsic noise may dominate these bounds, in contrast with what is known for
methods in which the inexactness in function and derivatives' evaluations is
fully controllable. Moreover, the new analysis provides estimates of the
optimality level achievable, should noise cause early termination. It finally
sheds some light on the impact of inexact computer arithmetic on evaluation
complexity.
\end{abstract}

{\bf Keywords:} noise, evaluation complexity, trust-region methods, inexact
functions and derivatives.

\numsection{Introduction}

This paper attempts to answer a simple question: how does noise in function
values and derivatives affect evaluation complexity of smooth optimization?
While analysis has been produced to indicate how high accuracy can be
reached by optimization algorithms even in the presence of inexact but
deterministic\footnote{Similar results are also known for the stochastic case
(see \cite{BandScheVice14,ChenMeniSche18,PaquSche20,BlanCartMeniSche19,BellGuriMoriToin20,BellGuri21}),
which is outside the scope of this paper.}
function and derivatives' values (see
\cite{Cart91,ConnGoulToin00,XuRoosMaho20,BellGuriMori21,YaoXuRoosMaho20,GratSimoToin20,CartGoulToin20c}),
these approaches crucially rely on the assumption
that the inexactness is controllable, in that it can be made arbitrarily small
if required so by the algorithm. But what happens in practical applications
where significant noise is intrinsic and can't be assumed away? How is the
evaluation complexity of the optimization algorithm altered?

To limit the scope of this analysis, we focus here on trust-region methods for
unconstrained problems, a well known class of algorithms (see
\cite{ConnGoulToin00} for an in-depth coverage and \cite{Yuan15} for a more
recent survey), whose complexity was first investigated in
\cite{GratSartToin08}. We choose to base our present developements on the existing
analysis of \cite{CartGoulToin20c}, where the evaluation complexity of
trust-region methods with explicit dynamic accuracy is presented. It is shown
in this paper that, under standard Lipschitz continuity assumptions, a variant
of the classical trust-region algorithm using derivatives of degree one to $q$
and allowing the control of inexactness in objective function and derivatives'
values will find a $q$-th order $\epsilon$- approximate minimizer of the objective function in
${\cal O}(\epsilon^{-(q+1)})$ evaluations of $f$ and its derivatives.

Our purpose in this paper is to extend these results to the case where such
favourable assumptions of the noise can no longer be made, in that evaluation
of $f$ or its derivatives may simply fail if the requested accuracy is too high.
In that case, the desired $\epsilon$ optimality may not be reachable, and
our minimization algorithm may be forced to terminate before approximate
convergence can be declared. The question then arises to establish not only an
upper bound on the number of evaluations for this event to occur, but also
bounds, if possible, on the level of optimality achieved at termination.
However, since noisy problems often occur in a context where even moderate
accuracy is expensive to obtain, we wish our algorithms to preserve the
ability of the methods described in \cite{CartGoulToin20c,BellGuriMoriToin20}
to dynamically adjust accuracy requests in the limits imposed by noise.

\vspace*{2mm}
\noindent
{\bf Contributions.}
We will present a trust-region method
  allowing dynamic accuracy control whenever possible given the level of
  noise, and show that termination of this algorithm will occur in at most
  ${\cal O}\Big(\min[\vartheta_f^{-1},\vartheta_d^{-1}\epsilon^{-(q+1)},\epsilon^{-(q+1)}]\Big)$
    evaluations, where $\vartheta_f$ and $\vartheta_d$ are the absolute noise levels in
    $f$ and its derivatives, respectively, $\epsilon$ is the (ideally)
    sought optimality threshold and
    $q\geq1$ is the sought optimality order. In addition, we will derive upper
    bounds on the value of optimality measures at termination that depend on
    $\vartheta_f$. To the best of our knowledge, these results are the first
    of their kind. Finally, a brief discussion will illustrate our results in
    the case where intrinsic noise is caused by computer arithmetic and
    round-off errors.

\noindent
Because our development heavily hinges on \cite{CartGoulToin20c},
repeating some material from this source is necessary to keep our argument
understandable. We have however done our best to limit this repetition as much
as possible, pushing some of it in an appendix when possible.

Even if the analysis presented below does not depend in any way on the choice
of the optimality order $q$, the authors are well aware that, while requests
for optimality of orders $q\in\{1,2\}$ lead to practical, implementable
algorithms, this may no longer be the case for $q>2$, at least for now. For high orders, the
methods discussed in the paper therefore constitute an ``idealized'' setting
(in which complicated subproblems can be approximately solved without affecting the
evaluation complexity) and thus indicate the limits of achievable results.

\vspace*{2mm}
\noindent
    {\bf Outline.} A first section briefly recalls the context and the notion
    of high-order approximate minimizers.  Section~\ref{section:trqdan} then
    presents a ``noise-aware'' inexact trust-region algorithm and its
    evaluation complexity. Brief conclusions and perspectives are finally
    presented in Section~\ref{section:conclusion}.

\vspace*{2mm}
\noindent
{\bf Basic notations.}
Unless otherwise specified, $\|\cdot\|$ denotes the standard
Euclidean norm for vectors and matrices.  For a general symmetric tensor $S$
of order $p$, we define
\[
\|S\| \stackrel{\rm def}{=} \max_{\|v\|=1}  | S [v]^p |
= \max_{\|v_1\|= \cdots= \|v_p\|=1} | S[v_1, \ldots, v_p] |
\]
the induced Euclidean norm. We also denote by $\nabla_x^j f(x)$ the $j$-th
order derivative tensor of $f$ evaluated at $x$ and note that such a tensor is
always symmetric for any $j\geq 2$. $\nabla_x^0 f(x)$ is a synonym for $f(x)$.
$\lfloor \alpha \rfloor$ denotes the largest integer not exceeding
$\alpha$. For symmetric matrices, $\lambda_{\min}[M]$ is the
leftmost eigenvalue of $M$.

\numsection{High-Order Taylor Decrements and High-Order Optimality}
\label{section:high-order}

Throughout this paper, we consider the unconstrained problem given by
\beqn{problem}
\min_{x \in \Re^n}  f(x),
\end{equation}
where we assume that
the \emph{values of the objective function $f$ and its derivatives are computed
  inexactly and are subject to noise}. Inexact quantities will be denoted by
an overbar, so that $\overline{f}(s)$ is an inexact value of $f(x)$ and
$\overline{\nabla_x^j f}(x)$ an inexact value of $\nabla_x^j f(x)$.
We will also assume that

\vspace*{1mm}
\noindent
{\bf AS.1:} the objective function $f$ is $q$ times continuously
differentiable in $\Re^n$, for some $q\geq 1$;

\vspace*{1mm}
\noindent
{\bf AS.2:} the first $q$ derivative tensors of $f$ are globally Lipschitz
    continuous, that is, for each $j\in\ii{q}$ there exist a constant
    $L_{f,j} \geq 0$ such that, for all $x,y$ in $\Re^n$,
    \[
    \| \nabla_x^j f(x) - \nabla_x^j f(y) \| \leq L_{f,j} \| x-y \|;
    \]

\vspace*{1mm}
\noindent
{\bf AS.3:} the objective function $f$ is bounded below by $f_{\rm low}$ on $\Re^n$.

\vspace*{1mm}
\noindent
In what follows, we consider algorithms that are able to exploit all available
derivatives of $f$.  As in many minimization methods, we would like to build a
model of the objective function $f$ using the truncated Taylor expansions
(now of degree $j$ for $j\in\ii{q}$) given by
\beqn{taylor}
T_{f,j}(x,s) \stackrel{\rm def}{=} f(x) + \sum_{\ell=1}^j \nabla_x^\ell f(x)[s]^\ell,
\end{equation}
where $\nabla_x^\ell f(x)$ is a $\ell$-th order symmetric tensor and
$\nabla_x^\ell f(x)[s]^\ell$ is this tensor applied to $\ell$ copies of the
vector $s$. More specifically, we will be interested, at a given iterate
$x_k$, in finding a step $s\in \Re^n$ which makes the \emph{Taylor decrements}
\[
\Delta T_{f,j}(x_k,s) \stackrel{\rm def}{=} f(x_k)- T_{f,j}(x_k,s) =
T_{f,j}(x_k,0)-T_{f,j}(x_k,s)
\]
large (note that $\Delta T_{f,j}(x,s)$ is independent of $f(x)$). When this is
possible, we anticipate from the approximating properties of the Taylor
expansion that some significant decrease is also possible in $f$.  Conversely,
if $\Delta T_{f,j}(x,s)$ cannot be made large in a neighbourhood of $x$, we
must be close to an approximate minimizer.  More formally, we define, for some
\emph{optimality radius} $\delta \in (0,1]$, the measure
\beqn{phi-def}
\phi_{f,j}^{\delta}(x) = \max_{\|d\|\leq \delta} \Delta T_{f,j}(x,d),
\end{equation}
that is the maximal decrease in $T_{f,j}(x,d)$ achievable in a ball of radius $\delta$
centered at $x$.  We then define $x$ to be a $q$-th order
$(\epsilon,\delta)$-approximate minimizer (for some accuracy requests
$\epsilon\in (0,1]^q$) if and only if
\beqn{approx-min}
\phi_{f,j}^\delta(x) \leq \epsilon_j \frac{\delta^j}{j!}
\tim{ for } j \in \ii{q},
\end{equation}
(a vector $d$ solving the optimization problem defining
$\phi_{f,j}^{\delta}(x)$ in \req{phi-def} is called an \emph{optimality
displacement}).  In other words, a $q$-th order
$(\epsilon,\delta)$-approximate minimizer is a point from which no significant
decrease of the Taylor expansions of degree one to $q$ can be obtained in a
ball of optimality radius $\delta$. This notion is coherent with standard
optimality measures for low orders\footnote{It is easy to verify that,
irrespective of $\delta$, \req{approx-min} holds for $j=1$ if and only if
$\|\nabla_x^1f(x)\|\leq\epsilon_1$ and that, if $\|\nabla_x^1f(x)\|=0$,
$\lambda_{\min}[\nabla_x^2 f(x)] \geq -\epsilon_2$ if and only if
$\phi_{f,2}^\delta(x) \leq \epsilon_2$.} and has the advantage of being
well-defined and continuous in $x$ for every order.

Unfortunately, the exact values of $f(x)$ and $\nabla_x^\ell f(x)$ may be
unavailable, and we then face several difficulties.
The first is that we can't consider the optimality measure \req{phi-def}
anymore, but could replace it by the inexact variant
\beqn{barphi-def}
\overline{\phi}_{f,j}^{\delta}(x) = \max_{\|d\|\leq \delta} \overline{\Delta T}_{f,j}(x,d).
\end{equation}
where
\[
\overline{\Delta T}_{f,j}(x,d) \stackrel{\rm def}{=} \overline{T}_{f,j}(x,0)-\overline{T}_{f,j}(x,d)
\tim{ with }
\overline{T}_{f,j}(x_k,s)
\stackrel{\rm def}{=} \overline{f}(x_k) + \sum_{\ell=1}^j \overline{\nabla_x^\ell f}(x_k)[s]^\ell.
\]
However, computing the exact global maximum in this definition may also be
too expensive, and we follow  \cite[Theorem~6.3.5]{ConnGoulToin00} and
\cite{CartGoulToin20c} in choosing to use the approximate version
given by $\overline{\Delta T}_{f,j}(x,d)$, where
\beqn{bbarphi-def}
\varsigma\,\overline{\phi}_{f,j}^{\delta}(x) \leq \overline{\Delta T}_{f,j}(x,d),
\end{equation}
for some displacement $d$ such that $\|d\|\leq \delta$ and some constant
$\varsigma \in (0,1]$.  Note that \req{bbarphi-def} does not assume the
knowledge of the global maximizer or $\overline{\phi}_{f,j}^{\delta}(x)$, but merely
that we can ensure \req{bbarphi-def} (see
\cite{deKlLaur19,deKlLaur20,SlotLaur20} for research in this direction). Note
also that, by definition,
\beqn{weak-opt}
\overline{\Delta T}_{f,j}(x,d) \leq \varsigma \alpha
\tim{ implies }
\overline{\phi}_{f,j}^{\delta}(x) \leq \alpha.
\end{equation}

The second difficulty occurs when computing a step $s_k$ which is supposed to
make the exact Taylor decrement $\Delta T_{f,j}(x_k,s_k)$ large,
since we now have to resort to making the inexact decrement
\[
\overline{\Delta T}_{f,j}(x,s_k) \stackrel{\rm def}{=} \overline{T}_{f,j}(x_k,0)-\overline{T}_{f,j}(x_k,s_k)
\]
large. It is therefore necessary to ensure, somehow, that the error on this
decrement does not dominate its value. The theory developed in this paper
depends on making the \emph{relative} error on $\overline{\Delta T}_{f,j}(x_k,s_k)$ (for a
chosen step $s_k$) smaller than one, which is to require that
\beqn{relerr-barDT}
|\overline{\Delta T}_{f,j}(x_k,s_k) - \Delta T_{f,j}(x_k,s_k)|
\leq \omega \overline{\Delta T}_{f,j}(x_k,s_k)
\end{equation}
for some constant $\omega\in (0,1)$ to be specified later.
It is clearly not obvious at this point how to enforce this relative error
bound. For now, we simply assume that it can be done in a finite
number of evaluations of $\{\overline{\nabla_x^{\ell}f}(x)\}_{\ell=1}^j$ which
are inexact approximations of $\{\nabla_x^{\ell}f(x)\}_{\ell=1}^j$.  The
third difficulty arises when assessing the performance of the computed step:
is the predicted decrease in objective function predicted by the (inexact)
decrement significant in view of the (absolute) noise level in computing
$\overline{f}(x_k)$ and $\overline{f}(x_k+s)$?  If not, the obtained decrease is dominated
by noise in $f$ and thus unreliable.  To avoid this, our algorithms
will attempt to require that
\beqn{abserr-f}
|\overline{f}(x_k)-f(x_k)| \leq \omega \overline{\Delta T}_{f,j}(x_k,s_k)
\tim{and}
|\overline{f}(x_k+s_k)-f(x_k+s_k)| \leq \omega \overline{\Delta T}_{f,j}(x_k,s_k),
\end{equation}
where $\omega$ is the parameter occuring in \req{relerr-barDT}.
The fourth, and for our present purpose, most significant difficulty is that
achieving \req{relerr-barDT} or \req{abserr-f} may require an accuracy
of $f$ and its derivatives which is not feasible for noisy problems, and we
will have to prematurely terminate the algorithm. In what follows, we make the
assumption that this situation may occur (and thus does occur in the worst
case) if, for some $x_k$ of interest and $j\in\ii{q}$,
\beqn{noise-termination}
|\overline{f}(x_k)-f(x_k)| \leq \vartheta_f
\tim{ ~~or~~}
\|\overline{\nabla_x^\ell f}(x_k)-\nabla_x^\ell f(x_k)\|\leq \vartheta_d
\tim{for some $\ell \in \ii{j}$.}
\end{equation}
for some non-negative \emph{absolute noise levels}  $\vartheta_f$ and $\vartheta_d$.
The rest of our analysis will therefore focus on analyzing trust-region
algorithms which ensure that
\req{relerr-barDT} and \req{abserr-f} hold  as long as \req{noise-termination}
fail.

Like many trust-region methods, our proposed algorithms will consist  of an
initialization followed by a loop, performed until termination, in which one
successively
\begin{enumerate}
\vspace*{-2mm}
\item \label{s-term} evaluates the function's derivatives and checks for termination,
\vspace*{-2mm}
\item \label{s-step} computes a step $s_k$ which approximately minimizes an (inexact) Taylor
  model $\overline{T}_{f,j}(x_k,s)$  while remaining the inequality $\|s_k\| \leq \Delta_k$,
  where $\Delta_k$ is the current trust-region radius,%
\vspace*{-2mm}
\item \label{s-compf} evaluates the objective function at the new potential iterate and
  accepts or refuses the step,
\vspace*{-2mm}
\item updates the trust-region radius $\Delta_k$.
\vspace*{-2mm}
\end{enumerate}
The discussion above suggests that, at the very least, specialized versions of
the first three steps will be necessary.

\numsection{A Trust-Region Algorithm with Explicit Dynamic Accuracy and Noise}
\label{section:trqdan}

Because our analysis is based on  \req{relerr-barDT}
and \req{abserr-f}, we have to discuss how these conditions can be achieved.
For this purpose, we will use
the ``Explicit Dynamic Accuracy'' (EDA) framework already used in
\cite{ConnGoulToin00,BellGuriMoriToin19,GratSimoToin20}, in which absolute
accuracies on the function and derivatives values may be specified by the
algorithm by imposing the bounds
\beqn{eda-f}
|\overline{f}(x)-f(x)| \leq \zeta_f
\end{equation}
and
\beqn{eda-d}
\|\overline{\nabla_x^\ell f}(x)- \nabla_x^\ell f(x)\| \leq \zeta_d
\tim{for} \ell\in\ii{j}
\end{equation}
before the actual computation of $\overline{f}(x)$ and $\overline{\nabla_x^\ell f}(x)$
takes place\footnote{We could obviously use values of $\zeta_d$ and
  $\vartheta_d$ depending on the degree $\ell$, but we prefer the above
  formulation to simplify notations.}.
Such a framework is applicable for instance to multiprecision
computations \cite{High17,GratToin20} or to problems where the desired values
are computed by an iterative process whose accuracy can be monitored. In our
trust-region algorithm, the thresholds $\zeta_f$ and $\zeta_d$ will be
adaptively updated in the course of the iterations, but it is already clear
that requesting $\zeta_d < \vartheta_d$  will be impossible when
 \req{noise-termination} holds.

\subsection{Checking the accuracy of the model decrease}

However, before this happens, the algorithm will need to verify that the model
decrease relative accuracy bound \req{relerr-barDT} holds when the
``derivative-by-derivative'' absolute errors $\zeta_d$ are
known. As it turns out, this request has to be relaxed somewhat whenever the
right-hand side $\omega \overline{\Delta T}_{f,j}(x_k,s_k)$ is small, as can be expected
near a minimizers, and we have to replace the relative accuracy bound
\req{relerr-barDT} by an absolute error bound in that case. The management of
these crucial details is the object of the \al{CHECK} algorithm
\vpageref{algorithm:check}. To describe this algorithm in a general context,
we suppose that we have a $r$-th degree Taylor series $T_r(x,v)$ of a given
function about $x$ in the direction $v$, along with an
approximation $\overline{T}_r(x,v)$ and its decrement $\overline{\Delta T}_r(x,v)$.
Additionally, we suppose that a bound $\delta \geq \|v\|$ is given, and that
\emph{required} relative and absolute accuracies $\omega$ and $\xi>0$
are on hand. Moreover, we assume that the \emph{current}
upper bound $\zeta_{d,i_\zeta}$ on absolute accuracies of the derivatives of
$\overline{T}_r(x,v)$ with respect to $v$ at $v=0$ are provided.
Because it will always be the case when we need it,
we will assume for simplicity that $\overline{\Delta T}_r(x,v) \geq 0$.  Finally, the
relative accuracy constant $\omega \in (0,1)$ will be fixed in our trust-region
algorithm, and we assume that it is given when needed in \al{CHECK}. The
constants $\gamma_\zeta$, $\vartheta_f$ and $\vartheta_d$ of \req{noise-termination} are also
assumed to be known.

\algo{algorithm:check}{The \al{CHECK} algorithm}{
\vspace*{-3mm}
\[
{\tt accuracy} = \mbox{\al{CHECK}}\Big(\delta,\overline{\Delta T}_r(x,v),\zeta_{d,i_\zeta},\xi\Big).
\]
\vspace*{-2mm}
\begin{description}
\item[\hspace*{6.5mm}]
  If
  \vspace*{-3mm}
  \beqn{verif-term-2}
  \overline{\Delta T}_r(x,v) > 0
  \tim{ and }
  \zeta_{d,i_\zeta}\sum_{\ell=1}^r \frac{\delta^\ell}{\ell!} \leq \omega \,\overline{\Delta T}_r(x,v),
  \vspace*{-3mm}
  \end{equation}
  set {\tt accuracy}\ to {\tt relative}.
\item[\hspace*{6.5mm}]
  Otherwise, if
  \vspace*{-3mm}
  \beqn{verif-term-3}
  \zeta_{d,i_\zeta} \sum_{\ell=1}^r \frac{\delta^\ell}{\ell!} \leq \omega \,\xi\, \frac{\delta^r}{r!},
  \vspace*{-3mm}
  \end{equation}
  set {\tt accuracy}\ to {\tt absolute}.
\item[\hspace*{6.5mm}]
  Otherwise, if
  \beqn{improve-possible}
  \gamma_\zeta \zeta_{d,i_\zeta} > \vartheta_d,
  \end{equation}
  set
  \beqn{improve-accuracy}
  \zeta_{d,i_\zeta+1}= \gamma_\zeta \zeta_{d,i_\zeta}
  \end{equation}
  and {\tt accuracy}\ to {\tt insufficient}.
\item[\hspace*{6.5mm}]
 Otherwise, set {\tt accuracy}\ to {\tt terminal}.
\end{description}
}

\noindent
Note that the integer $i_\zeta$ counts the number of times the accuracy
threshold has been reduced by a factor $\gamma_\zeta$.
The outcome of the \al{CHECK} algorithm can then characterized as follows.

\llem{lemma:check}{
Let $\omega \in (0,1)$ and $\delta$, $\xi$ and $\zeta_{d,i_\zeta}$ be positive.
Suppose that $\overline{\Delta T}_r(x,v) \geq 0$ and \req{eda-d} hold.  Then the call
${\tt accuracy} = \mbox{\al{CHECK}}\Big(\delta,\overline{\Delta T}_r(x,v),\zeta_{d,i_\zeta},\xi\Big)
$
ensures that

\noindent
{\em (i)} {\tt accuracy}\ is either {\tt absolute}\ or {\tt relative}\ whenever
\vspace*{-3mm}
\[
\zeta_{d,i_\zeta}\sum_{\ell=1}^r \frac{\delta^i}{i!} \leq \omega \xi \frac{\delta^r}{r!};
\]

\noindent
{\em (ii)} if {\tt accuracy}\ is {\tt absolute},
\[
\max\Big[\overline{\Delta T}_r(x,v),
    \left|\overline{\Delta T}_r(x,w)- \Delta T_r(x,w)\right|\Big]
  \leq \xi \frac{\delta^r}{r!}
\]
for all $w$ with $\|w\|\leq \delta$;

\noindent
{\em (iii)} if {\tt accuracy}\ is {\tt relative},
  $\overline{\Delta T}_r(x,v)>0$ and
\[
  \left|\overline{\Delta T}_r(x,w)- \Delta T_r(x,w)\right|
  \leq \omega \overline{\Delta T}_r(x,v),
  \tim{for all $w$ with $\|w\|\leq \delta$}.
\]

\noindent
Moreover, the outcome ${\tt accuracy} = {\tt insufficient}$ indicates that new values of
the required approximate derivatives should be computed with the updated accuracy
thresholds, while ${\tt accuracy} = {\tt terminal}$ indicates that the minimization
algorithm has reached the noise level and should be terminated.
}

\proof{We note that the \al{CHECK} algorithm is identical to the \al{VERIFY}
  algorithm of \cite{CartGoulToin20c} (itself inspired by
  \cite{BellGuriMoriToin19})  whenever {\tt accuracy}\ is either
  {\tt absolute}\ or {\tt relative}. Lemma~2.1 in that reference therefore ensures the
  conclusions (i) to (iii). If ${\tt accuracy} = {\tt insufficient}$, then
  \req{improve-possible} ensures that the accuracy threshold update
  \req{improve-accuracy} has been performed safely
  (\req{noise-termination} remains violated), while ${\tt accuracy} = {\tt terminal}$
  indicates that this was not the case, suggesting termination.
}

\noindent
Note that case (ii) is the case where relative accuracy would be excessively
requiring and absolute accuracy is preferred.

\subsection{Testing for termination}

We now start constructing  our new algorithm (which we call the
\al{TR$q$EDAN} algorithm because it uses the \al{EDA} framework and handles
\al{N}oise) step by step, following the outline given at the end of
Section~\ref{section:high-order}. Consider Step~1 first.
Since we have to rely on $\overline{\nabla_x^\ell f}(x_k)$ rather than
$\nabla_x^\ell f(x_k)$, it is clear that our optimality measure \req{phi-def} and test
\req{approx-min} should be modified to use the inexact values.
Ideally, we could mimic \cite{CartGoulToin20c} and terminate because of
\req{weak-opt} as soon as
\beqn{approx-min-inexact}
\overline{\Delta T}_{f,j}(x_k,d_{k,j}) \leq \left(\frac{\varsigma\epsilon_j}{1+\omega}\right) \frac{\delta_k^j}{j!}
\tim{ for } j \in \ii{q},
\end{equation}
and where $\omega\in(0,1)$ is the (still unspecified) relative accuracy
parameter of \req{relerr-barDT},
\[
\varsigma \overline{\phi}_{f,j}^{\delta_k}(x_k) \leq \overline{\Delta T}_{f,j}(x_k,d_{k,j})
\]
and $\delta_k$ is the optimality radius
at iteration $k$ (which we leave again unspecified at this stage).
However, we now have to take into account the
fact that noise in the values of the derivatives may prevent a meaningful
computation of $\overline{\Delta T}_{f,j}(x_k,d_{k,j})$. We therefore have to modify the
technique proposed in \cite[Algorithm~2.2]{CartGoulToin20c}.  Assuming that
the optimality radius $\delta_k$ is given, we thus consider
Algorithm~\ref{algorithm:phij} for computing the $j$-th approximate optimality measure
which is needed in \req{approx-min-inexact} to test for termination in the first step of the
\al{TR$q$EDAN} algorithm.

\algo{algorithm:phij}{Computing \boldmath$\overline{\Delta T}_{f,j}(x_k,d_{k,j})$}{
The iterate $x_k$, the index $j\in\ii{q}$ and the radius $\delta_k\in (0,1]$
are given, as well as constants $\gamma_\zeta \in (0,1)$ and
$\varsigma \in (0,1]$. The counter $i_\zeta$, the relative accuracy
$\omega\in (0,1)$ and the absolute accuracy bound $\zeta_{d,i_\zeta}$ are also given.
\\
\vspace*{-3mm}
\begin{description}
\item[Step 1.1: ] If they are not yet available, compute
  $\{\overline{\nabla_x^if}(x_k)\}_{i=1}^j$ satisfying \req{eda-d} for
  $\zeta_d=\zeta_{d,i_\zeta}$.
\item[Step 1.2: ]
     Find $d_{k,j}$ with $\|d_{k,j}\|\leq \delta_k$ such that

     \varsigma \overline{\phi}_{f,j}^{\delta_k}(x_k) \leq \overline{\Delta T}_{f,j}(x_k,d_{k,j})
     \vspace*{-1mm}
     $
     and compute
     \beqn{check-for-phi}
     \mbox{{\tt accuracy}$_j$\,} =
     \mbox{\al{CHECK}}\Big(\delta_k,\overline{\Delta T}_{f,j}(x_k,d_{k,j}),
             \zeta_{d,i_\zeta}, \sfrac{1}{2} \varsigma \epsilon_j\Big).
     \end{equation}
\item[Step 1.3: ] If {\tt accuracy}$_j$\, is {\tt absolute}\ or {\tt relative}, return
      $\overline{\Delta T}_{f,j}(x_k,d_{k,j})$.
\item[Step 1.4: ] If {\tt accuracy}$_j$\, is {\tt insufficient}, return to Step~1.1 (with the
     tightened accuracy threshold $\zeta_{d,i_\zeta+1}$).
     Else (i.e.\ if {\tt accuracy}$_j$\, is {\tt terminal}), terminate the \al{TR$q$EDAN}
     algorithm with $\tilde{x}=x_k$, {\tt status}\ = {\tt in-noise-phi}, {\tt order} = $j$
     and  {\tt delta} = {\tt radius}\ = $\delta_k$.
\end{description}
}

\noindent
Note that, when termination occurs, this algorithm (and other algorithms we
will meet later) sets the four flags {\tt status}, {\tt order}, {\tt delta}\ and {\tt radius}, which
will allow the user to determine the reason of termination once it occured
and, as we will see in Theorem~\ref{theorem:trqedan-complexity} below,
derive some useful properties of the point $\tilde{x}$ returned.

Because Algorithm~\ref{algorithm:phij} and
\cite[Algorithm~2.2]{CartGoulToin20c} only differ in Step~1.4, we may then
follow the reasoning of \cite[Lemma~2.2]{CartGoulToin20c} and obtain the
following result.

\llem{lemma:phi-res}{If Algorithm~\ref{algorithm:phij} terminates within Step~1.3 when
{\tt accuracy}$_j$\, is {\tt absolute}, then
\beqn{term-absolute}
\phi_{f,j}^{\delta_k}(x_k) \leq \epsilon_j \frac{\delta_k^j}{j!}.
\end{equation}
Otherwise, if it terminates with {\tt accuracy}$_j$\, being {\tt relative}, then
\beqn{term-relative}
(1-\omega) \overline{\Delta T}_{f,j}(x_k,d_{k,j})
\leq \phi_{f,j}^{\delta_k}(x_k)
\leq \left(\frac{1+\omega}{\varsigma}\right) \overline{\Delta T}_{f,j}(x_k,d_{k,j})
\end{equation}
Moreover, termination with one of these two outcomes must occur if
\beqn{term-bound-phi}
\zeta_{d,i_\zeta} \leq \frac{\omega}{4}\,\varsigma\,\epsilon_j\,\frac{\delta_k^{j-1}}{j!}.
\end{equation}
}

\noindent
Of course, termination may occur before \req{term-bound-phi} occurs (for
instance because of \req{noise-termination}
in the call to \al{CHECK} in Step~1.2), but the bound
\req{term-bound-phi} shows that, if this doesn't happen, the accuracy
threshold $\zeta_{d,i_\zeta}$ can not be reduced infinitely often by the
factor $\gamma_\zeta$ and thus the loop between Steps~1.4 and 1.1 is
finite. Note that the rightmost inequality in \req{term-relative} and
\req{approx-min-inexact} together also imply \req{term-absolute} for order
$j$, justifying our choice of the scaling by $(1+\omega)$ in the former.

Refering now to our outline on the trust-region method at the end of
Section~\ref{section:high-order}, we may now use
Algorithm~\ref{algorithm:phij} to implement a complete Step~1.  The idea is
first to identify a suitable optimality radius, which we choose to be
\beqn{deltak-def}
\delta_k = \min[\Delta_k, \theta]
\end{equation}
(for some constant $\theta \leq 1$),
estimate the needed (inexact) derivatives and $\overline{\phi}_{f,j}^{\delta_k}(x_k)$  for
$j\in\ii{q}$ and decide on termination. The result is the \al{STEP1} algorithm
\vpageref{algorithm:STEP1}.

\algo{algorithm:STEP1}{\al{STEP1} for the \al{TR$q$EDAN} algorithm}{
  Set $\delta_k$ according to \req{deltak-def}. \\
  For $j = 1, \ldots, q $,\\
  \hspace*{2mm}\parbox[t]{14.5cm}{\vspace*{-2mm}\begin{description}
  \item{1.}  Evaluate $\overline{\nabla_x^j f}(x_k)$ and compute
  $\overline{\Delta T}_{f,j}(x_k,d_{k,j})$ using Algorithm~\ref{algorithm:phij}.
  \item{2.} If termination of the \al{TR$q$EDAN} algorithm has not
  happened in Step~1.4 of Algorithm~\ref{algorithm:phij} and
  \beqn{cauchy}
  \overline{\Delta T}_{f,j}(x_k,d_{k,j})
  > \left(\frac{\varsigma\epsilon_j}{1+\omega}\right) \frac{\delta_k^j}{j!},
  \end{equation}
  exit \al{STEP1} with the current value of $j$ and the
  optimality displacement $d_{k,j}$ associated  with
  $\overline{\phi}_{f,j}^{\delta_k}(x_k)$. Otherwise consider the next $j$.
  \end{description}}\\*[1.5ex]
  Terminate the \al{TR$q$EDAN} algorithm with $\tilde{x} = x_k$,
  {\tt status}\ = {\tt approximate-minimizer}, {\tt order}\ = $q$ and {\tt delta}\ = {\tt radius}\ =  $\delta_k$.
}

\noindent
Before progressing any further, we state an easy but useful technical
inequality.

\llem{lemma:chi-ineq}{
Consider $\delta\geq 0$.  Then, for all $j\geq 1$,
\beqn{chi-ineqs}
\min[\delta,1] \leq \sum_{\ell=1}^j\frac{\delta^\ell}{\ell!} < 2
\max[\delta,\delta^j].
\end{equation}
}

\proof{
  The bounds \req{chi-ineqs} easily follow from
  $
  1 \leq \displaystyle \sum_{\ell=1}^j\frac{1}{\ell!} < e-1 < 2.
  $
}

\noindent
We now consider what can be said if the \al{TR$q$EDAN} algorithm
terminates within \al{STEP1}.

\llem{lemma:step1-termination}{\mbox{
\begin{itemize}
\item[(i)] Suppose that termination of the \al{TR$q$EDAN} algorithm occurs
  within \al{STEP1} with {\tt status}\ = {\tt in-noise-phi}, {\tt order}\ = $j$ and {\tt delta}\ = $\delta_k$.
  Then
  \beqn{step1-termination}
  \phi_{f,i}^{\delta_k}(\tilde{x}) \leq \epsilon_i\frac{\delta_k^i}{i!}
  \tim{for} i\in\ii{j-1}
  \tim{ ~and~ }
  \phi_{f,j}^{\delta_k}(\tilde{x}) < \frac{4\vartheta_d}{\gamma_\zeta \omega}\delta_k.
  \end{equation}
\item[(ii)] Suppose that termination of the \al{TR$q$EDAN} algorithm occurs
  with {\tt status}\ = {\tt approximate-minimizer}\ and {\tt delta}\ = $\delta_k$.
  Then \req{approx-min} holds and $\tilde{x}$ is a
  $q$-th order $(\epsilon,\delta_k)$-approximate minimizer.
\end{itemize}
}

\proof{
  We prove case (ii) first, which can only occur if Algorithm~\ref{algorithm:phij}
  terminates within Step~1.3 and \req{cauchy} fails for every $j\in\ii{q}$.
  We then have from Lemma~\ref{lemma:phi-res} that, for every $j\in\ii{q}$,
  \[
  \phi_{f,j}^{\delta_k}(x_k)
  = \phi_{f,j}^{\delta_k}(\tilde{x})
  \leq \max\left[ \epsilon_j \frac{\delta_k^j}{j!},\left(\frac{1+\omega}{\varsigma}\right)\,\overline{\Delta T}_{f,j}(x_k,d_{k,j})\right]
  \leq \epsilon_j \frac{\delta_k^j}{j!},
  \]
  the last inequality resulting from the failure of \req{cauchy}.  Thus \req{approx-min} holds.

  Consider now case (i), that is when the call \al{CHECK} in Step~1.2 of
  Algorithm~\ref{algorithm:phij} returns {\tt accuracy}$_j$\, $=$ {\tt terminal}\ for some $j\in\ii{q}$.
  Thus Algorithm~\ref{algorithm:phij} has terminated within Step~1.3 and
  \req{cauchy} has failed for every order of index smaller than
  ${j-1}$. Applying the same reasoning as for case (ii), we obtain that the
  first part of \req{step1-termination} holds. Now suppose that, instead of
  the call \req{check-for-phi} resulting in {\tt accuracy}$_j$\, being {\tt terminal}, we had
  made the hypothetical call
  \beqn{hypothetical-check}
  \mbox{{\tt accuracy}$_j$\,} =
     \mbox{\al{CHECK}}\Big(\delta_k,\overline{\Delta T}_{f,j}(x_k,d_{k,j}),\zeta_{i,i_\zeta},
     \frac{\zeta_{d,i_\zeta}j!}{\omega\delta_k^j}\sum_{\ell=1}^j\frac{\delta_k^\ell}{\ell!}\Big).
  \end{equation}
  Observe first that, since the call \req{check-for-phi} returned {\tt terminal}, \req{verif-term-2}
  failed on that call, and thus, since this is independent of the last
  argument of the call, it also fails for the call
  \req{hypothetical-check}. However, one easily checks that \req{verif-term-3}
  holds as an equality for this hypothetical call, and thus
  \req{hypothetical-check} would return {\tt accuracy}$_j$\,\ as {\tt absolute}.  We may then
  use case (ii) in Lemma~\ref{lemma:check} and deduce from the triangular
  inequality that, for some $\tilde{d}$ with $\|\tilde{d}\|\leq \delta_k$,
  \[
  \phi_{f,j}^{\delta_k}(\tilde{x})
  = \Delta T_j(\tilde{x},\tilde{d})
  \leq \overline{\Delta T}_j(\tilde{x},\tilde{d})
       + \left|\overline{\Delta T}_j(\tilde{x},\tilde{d})- \Delta T_j(\tilde{x},\tilde{d})\right|
  \leq 2\,\frac{\zeta_{d,i_\zeta}j!}{\omega\delta_k^j}
       \left(\sum_{\ell=1}^j\frac{\delta_k^\ell}{\ell!}\right)\frac{\delta_k^j}{j!}.
  \]
  Moreover, since the call \req{check-for-phi} returned {\tt terminal}, we have
  that $\gamma_\zeta \zeta_{d,i_\zeta} < \vartheta_d$, and we deduce that
  \beqn{phi-terminal-j}
  \phi_{f,j}^{\delta_k}(\tilde{x})
  < 2 \, \frac{\vartheta_d}{\gamma_\zeta\omega}
       \left(\sum_{\ell=1}^j\frac{\delta_k^\ell}{\ell!}\right).
  \end{equation}
  The second part of \req{step1-termination} then results from this inequality
  and \req{chi-ineqs} for $\delta=\delta_k\leq \theta\leq 1$.
}

\noindent
We also have the following useful result.

\llem{lemma:no-term-step1}{
Suppose that, at iteration $k$, termination of the \al{TR$q$EDAN} algorithm
does not happen during execution of \al{STEP1}. Then
\beqn{barDTd-lower}
\overline{\Delta T}_{f,j}(x_k,d_{k,j})
\geq \frac{\zeta_{d,i_\zeta}}{\omega} \sum_{\ell=1}^j \frac{\delta_k^\ell}{\ell!},
\end{equation}
where the threshold $\zeta_{d,i_\zeta}$ refers to its value at the end of
\al{STEP1}.
Moreover,
\beqn{phi-end-step1}
\phi_{f,i}^{\delta_k}(x_k) \leq \epsilon_i\frac{\delta_k^i}{i}
\tim{for} i\in \ii{j-1}
\tim{ and }
\phi_{f,j}^{\delta_k}(x_k) \leq \left(\frac{1+\omega}{\varsigma}\right)\overline{\phi}_{f,j}^{\delta_k}(x_k).
\end{equation}
}

\proof{
Suppose that the last value of {\tt accuracy}$_j$\,\ computed during the execution of
\al{STEP1} is {\tt absolute}.  Then Lemma~\ref{lemma:phi-res} implies that
\req{term-absolute} holds.  But, since $\omega \in (0,1)$, this  and
Lemma~\ref{lemma:check} (ii) contradict
\req{cauchy}. As a consequence, the last value of {\tt accuracy}$_j$\,\ must be
{\tt relative}, in which case \req{verif-term-2} ensures \req{barDTd-lower}.
The first part of \req{phi-end-step1} again follows from the reasoning of
Lemma~\ref{lemma:step1-termination}(ii) for $i\in\ii{j-1}$. Finally,
the fact that {\tt accuracy}$_j$\,\ is {\tt relative}\ implies that \req{term-relative} holds in
Lemma~\ref{lemma:phi-res}, which gives the second part of \req{phi-end-step1}.
}

\subsection{Computing a step}

Given Step~1, constructing Step~2 of our \al{TR$q$EDAN} algorithm is
relatively straightforward and we immediately provide the details in the
\al{STEP2} algorithm \vpageref{algorithm:STEP2}.

\algo{algorithm:STEP2}{\al{STEP2} for the \al{TR$q$EDAN} algorithm}{
The iterate $x_k$, the relative accuracy $\omega$, the requested accuracy
$\epsilon_j\in (0,1]^q$, the constant $\gamma_\zeta \in (0,1)$  the counter
$i_\zeta$ and the absolute accuracy threshold $\zeta_{d,i_\zeta}$ are given.
The index $j\in\ii{q}$, the optimality displacement $d_{k,j}$ resulting from
Step~1 and the constant $\theta \in (0,1]$, are also given such
that, by \req{cauchy},
\beqn{Cdecr}
\overline{\Delta T}_{f,j}(x_k,d_{k,j}) > \left(\frac{\varsigma\epsilon_j}{1+\omega}\right) \frac{\delta_k^j}{j!}.
\end{equation}
\begin{description}
\item[Step 2.1: ] If they are not yet available, compute
    $\{\overline{\nabla_x^\ell f}(x_k)\}_{i=1}^j$ satisfying \req{eda-d} for
  $\zeta_d=\zeta_{d,i_\zeta}$ and recompute $\overline{\Delta T}_{f,j}(x_k,d_{k,j})$ for
  this accuracy threshold.
\item[Step 2.2: Step computation.]
  If $\Delta_k \leq \theta$, set $s_k = d_{k,j}$ and exit the \al{STEP2}
  algorithm with $\overline{\Delta T}_{f,j}(x_k,s_k) = \overline{\Delta T}_{f,j}(x_k,d_{k,j})$.
  Otherwise, find $s_k$ such that $\|s_k\|\leq\Delta_k$ and
  \beqn{step-subproblem}
  \overline{\Delta T}_{f,j}(x_k,s_k) \geq \overline{\Delta T}_{f,j}(x_k,d_{k,j}),
  \end{equation}
  and compute
    \vspace*{-2mm}
    \beqn{check-sk}
    \mbox{{\tt accuracy}$_s$\,} =
    \mbox{\al{CHECK}}\Big( \|s_k\|,\overline{\Delta T}_{f,j}(x_k,s_k),\zeta_{d,i_\zeta},
    \bigfrac{\varsigma\epsilon_j}{4(1+\omega)}\,\Big(\bigfrac{\theta}{\max\big[\theta,\|s_k\|\big]}\Big)^j\Big).
    \end{equation}
  \item [Step 2.3:] If {\tt accuracy}$_s$\,\ is {\tt relative}, exit the \al{STEP2} algorithm
    with the step $s_k$ and the associated $\overline{\Delta T}_{f,j}(x_k,s_k)$.
\item[Step 2.4: ] If {\tt accuracy}$_s$\, is {\tt insufficient}, return to Step~2.1 (with the
  tightened accuracy thresholds).
  Otherwise, if {\tt accuracy}$_s$\, is {\tt terminal}, terminate the \al{TR$q$EDAN}
  algorithm  with $\tilde{x}=x_k$, {\tt status}\ = {\tt in-noise-s}, {\tt order}\ = $j$,
  {\tt delta}\ = $\delta_k$ and {\tt radius}\ = $\|s_k\|$.
\end{description}
}

  \noindent
Note that setting $s_k=d_{k,j}$ when $\Delta_k<\theta$
makes sense since $d_{k,j}$, computed in Step~1.2, is already a (\al{CHECK}ed)
approximate global maximizer of $\overline{\Delta T}_{f,j}(x_k,s)$ in the ball of radius
$\delta_k=\Delta_k$.
Two features of this algorithm remain nevertheless somewhat mysterious at this
stage.  The first is the complicated function of
$\|s_k\|$ and $\epsilon_j$ occuring in the last argument of the call to the
\al{CHECK} algorithm. As it turns out, it is possible to show
that the conjunction of \req{cauchy} and this particular
call to \al{CHECK}\footnote{\al{VERIFY} in \cite{CartGoulToin20c}.} ensures
that {\tt accuracy}$_s$\,\ cannot be {\tt absolute}.  This then also clarifies the second
mysterious feature, which is why this value of {\tt accuracy}$_s$\,\ is not considered in the rest
of the algorithm.  This is part of the following lemma, which was proved as
Lemma~3.2 in \cite{CartGoulToin20c} and which we can reuse since
the step computation
in that reference\footnote{In \cite{CartGoulToin20c}, the step computation is the combination
of Step~2 in Algorithm~3.1 and Algorithm~3.2 for the case where $\Delta_k\geq
\theta$. Note that, in this case, $\delta_k=\theta$ and thus $\delta_k$ may
be replaced by $\theta$ in the right-hand side of \req{Cdecr}, as
stated in Algorithm~3.2 of \cite{CartGoulToin20c}.}
and the \al{STEP2} algorithm only differ in the possibility that the \al{TR$q$EDAN}
algorithm can terminate in the call to \al{CHECK} in Step~2.2.

\llem{lemma:step2-res}{
  Suppose that the \al{TR$q$EDAN} algorithm does not terminate within the call
  to \al{CHECK} in Step~2.2 of the \al{STEP2} algorithm. Then the \al{STEP2}
  algorithm terminates with {\tt accuracy}$_s$\, being {\tt relative}\  and
  \req{relerr-barDT} holds. Moreover, this outcome must occur if
  \beqn{step2-bound}
  \zeta_{d,i_\zeta}
  \leq \frac{\varsigma \omega\delta_k^j}{8j!(1+\omega)} \,\frac{\epsilon_j}{\max[1,\Delta_{\max}^j]}.
  \end{equation}
}

\noindent
As for Lemma~\ref{lemma:phi-res}, the bound \req{step2-bound} ensures that the
loop between Steps~2.4 and 2.1 is finite.

We conclude this paragraph by examining the optimality guarantees which may be
obtained, should the \al{TR$q$EDAN} algorithm terminate in \al{STEP2}.

\llem{lemma:step2-termination}
{
  Suppose that, at iteration $k$, the \al{TR$q$EDAN} algorithm terminates
  within  \al{STEP2} with {\tt status}\ = {\tt in-noise-s}, {\tt order} = $j$  and {\tt radius}\ = $\|s_k\|$.

  Then
\beqn{step2-termination}
\phi_{f,j}^{\|s_k\|}(\tilde{x}) \leq \frac{4\vartheta_d}{\gamma_\zeta\omega}
\max\big[\|s_k\|,\|s_k\|^j\big].
\end{equation}
}

\proof{
The fact that {\tt status}\ = {\tt in-noise-s}\ implies that termination occurs in
Step~2.4, and it must be because the call \req{check-sk}
returns {\tt accuracy}$_s$\,\ equal to {\tt terminal}. As in the proof of
Lemma~\ref{lemma:step1-termination}, we consider replacing this call by the
hypothetical
\beqn{hypothetical-check-sk}
  \mbox{{\tt accuracy}$_s$\,} =
     \mbox{\al{CHECK}}\Big(\|s_k\|,\overline{\Delta T}_{f,j}(x_k,s_k),
 \zeta_{i,i_\zeta}, \frac{\zeta_{d,i_\zeta}j!}{\omega\|s_k\|^j}\sum_{\ell=1}^j\frac{\|s_k\|^\ell}{\ell!}\Big)
\end{equation}
and verify that this call must return {\tt accuracy}$_s$\,\ equal to {\tt absolute}.  We also
deduce from case (ii) in Lemma~\ref{lemma:check}, the triangular inequality
and the bound $\gamma_\zeta\zeta_{d,i_\zeta}<\vartheta_d$ that, for some $\tilde{d}$
with $\|\tilde{d}\|\leq\|s_k\|$,
\[
\phi_{f,j}^{\|s_k\|}(\tilde{x})
= \Delta T_j(\tilde{x},\tilde{d})
\leq \overline{\Delta T}_j(\tilde{x},\tilde{d})
      + \left|\overline{\Delta T}_j(\tilde{x},\tilde{d})- \Delta T_j(\tilde{x},\tilde{d})\right|
\leq 2 \, \frac{\vartheta_d}{\gamma_\zeta\omega}\left(\sum_{\ell=1}^j\frac{\|s_k\|^\ell}{\ell!}\right),
\]
and \req{step2-termination} follows from \req{chi-ineqs}.
}

\subsection{The complete \al{TR$q$EDAN} algorithm}

Having constructed the first two steps of the \al{TR$q$EDAN} algorithm, we are
now in position to specify the algorithm in its entirety
(see \vpageref{algorithm:trqedan}), making the necessary changes to handle
\req{noise-termination} in Step~3 along the way.

\algo{algorithm:trqedan}{The \al{TR$q$EDAN} algorithm}
{
\vspace*{-2mm}
\begin{description}
\item[Step~0: Initialisation.]
  A criticality order $q$, a starting point $x_0$ and an initial trust-region radius
  $\Delta_0$ are given, as well as accuracy levels $\epsilon \in (0,1)^q$ and
  an  initial bound on absolute derivative accuracies $\kappa_\zeta$.
  The constants $\omega$, $\varsigma$, $\theta$, $\eta_1$, $\eta_2$,
  $\gamma_1$, $\gamma_2$,  $\gamma_3$ and $\Delta_{\max}$ are also given and satisfy
  \[
  \theta \in [\min_{j\in\ii{q}} \epsilon_j, 1],\;\;\;
  \Delta_0\leq \Delta_{\max},\;\;\;
  0 < \eta_1 \leq \eta_2 < 1, \;\;\;
  0< \gamma_1 < 1 < \gamma_2 < \gamma_3,
  \]
  \[
  \varsigma \in (0,1], \;\;\;
  \omega \in \Big(0,\min\big[\sfrac{1}{2} \eta_1, \sfrac{1}{4}(1-\eta_2)\big]\Big),\;\;\;
  \kappa_\zeta > \min_{j\in\ii{q}} \epsilon_j^{q+1}
  \tim{and}
  \vartheta_d< \kappa_\zeta.
  \vspace*{-1mm}
  \]
  Choose $\zeta_{d,0}\leq \kappa_\zeta$ and
  set $k=0$ and $i_\zeta=0$.
\item[Step~1: Termination test.]
  Apply the \al{STEP1} algorithm (p.~\pageref{algorithm:STEP1}), resulting in either
  termination, or a model degree $j$ and the associated displacement $d_{k,j}$
  and decrease $\overline{\Delta T}_{f,j}(x_k,d_{k,j})$.
\item[Step~2: Step computation.]
  Apply the \al{STEP2} algorithm (p.~\pageref{algorithm:STEP2}) to compute a
  step $s_k$ such that $\overline{\Delta T}_{f,j}(x_k,s_k)\geq \overline{\Delta T}_{f,j}(x_k,d_{k,j})$.
\item[Step~3: Accept the new iterate.] If
  $\overline{\Delta T}_{f,j}(x_k,s_k)\leq\vartheta_f/\omega$, then terminate with
  $\tilde{x}=x_k$, {\tt status}\ = {\tt in-noise-f}, {\tt order}\ = $j$, {\tt delta}\ = $\delta_k$
  and {\tt radius} = $\max[\delta_k,\|s_k\|]$.\\
  Otherwise, compute $\overline{f}(x_k+s_k)$ ensuring that
  \beqn{Df+-DT}
  |\overline{f}(x_k+s_k)-f(x_k+s_k)| \leq \omega \overline{\Delta T}_{f,j}(x_k,s_k);
  \vspace*{-1mm}
  \end{equation}
  and ensure (by setting
  $\overline{f}(x_k)=\overline{f}(x_{k-1}+s_{k-1})$
  or by recomputing $\overline{f}(x_k)$) that
  \beqn{Df-DT}
  |\overline{f}(x_k)-f(x_k)| \leq \omega \overline{\Delta T}_{f,j}(x_k,s_k).
  \end{equation}
  Then compute
  \beqn{rhokdef2}
  \rho_k = \frac{\overline{f}(x_k) - \overline{f}(x_k+s_k)}
                {\overline{\Delta T}_{f,j}(x_k,s_k)}.
  \end{equation}
  If $\rho_k \geq \eta_1$, set $x_{k+1} = x_k + s_k$; otherwise set $x_{k+1} = x_k$.
\item[Step~4: Update the trust-region radius.]
  Set
 \[
  \Delta_{k+1} \in \left\{ \begin{array}{ll}
  {}[\gamma_1 \Delta_k, \gamma_2 \Delta_k] & \tim{if} \rho_k < \eta_1,\\
  {}[\gamma_2 \Delta_k, \Delta_k] & \tim{if} \rho_k \in  [\eta_1, \eta_2),\\
  {}[\Delta_k, \min(\Delta_{\max},\gamma_3 \Delta_k)] & \tim{if} \rho_k \geq  \eta_2,
  \end{array}\right.
  \]
  Increment $k$ by one and go to Step~1.
  \end{description}
}

\noindent
We immediately note the condition, at the beginning of Step~3, that
$\overline{\Delta T}_{f,j}(x_k,s_k)>\vartheta_f/\omega$.  This guarantees that the limit
in noise imposed by \req{noise-termination} will not come into play when
computing $\overline{f}(x_k+s_k)$ (and possibly recomputing $\overline{f}(x_k)$).

We also note that, except for
that feature, our specialized \al{STEP1} and \al{STEP2} using the \al{CHECK}
algorithm to handle intrinsic noise on the derivatives, and the relevant
initialization of $\omega$, the
\al{TR$q$EDAN} algorithm is identical to that analyzed in
\cite{CartGoulToin20c}\footnote{\cite{CartGoulToin20c} uses degree-specific
values for $\zeta_d$, but the can be assumed to be identical.}. Again, this
allows us to reuse results in this reference as needed, the first of which
relates the number of iterations of ``successful'' iterations (those where the
new iterate is accepted in Step~3) and ``unsuccessful'' ones.  If, as is
standard, we define
\[
{\cal S}_k = \{ i \in \iiz{k} \mid x_{i+1}= x_i+s_i\}
= \{ i \in \iiz{k} \mid \rho_i \geq \eta_1 \},
\]
the following useful result is applicable to the \al{TR$q$EDAN} algorithm.

\llem{lemma:SvsU}{\cite[Lemma~3.1]{CartGoulToin20c}
Suppose that the \al{TR$q$EDAN} algorithm is used and that $\Delta_k \geq
\Delta_{\min}$ for some $\Delta_{\min} \in (0,\Delta_0]$. Then, if $k$ is the index of an
iteration before termination,
\beqn{unsucc-neg}
k \leq |{\cal S}_k| \left(1+\frac{\log\gamma_3}{|\log\gamma_2|}\right)
+ \frac{1}{|\log\gamma_2|}
\left|\log\left(\frac{\Delta_{\min}}{\Delta_0}\right)\right|.
\end{equation}
}

\subsection{Evaluation complexity and optimality at termination}

Readers with some background in evaluation complexity analysis will not be
surprised by the fact that the complexity of the \al{TR$q$EDAN} algorithm
crucially depends on the decrease that can be achieved on the exact objective
function at successful iterations.  This will in turn depend on the achievable
decrease in inexact values of the objective, which is itself depending on the
decrease $\overline{\Delta T}_{f,j}(x_k,s_k)$ on the inexact model.  Fortunately, we can
again call on the analysis of \cite{CartGoulToin20c} for help, since such
decreases necessarily happen in the \al{TR$q$EDAN} algorithm, before early
termination due to \req{noise-termination} possibly occurs.

\llem{lemma:phihat}{\cite[Lemmas 3.4 and 3.6]{CartGoulToin20c}
Suppose AS.1 and AS.2 hold. At iteration $k$ before termination of the \al{TR$q$EDAN} algorithm
define
\beqn{phihat-def}
\widehat{\phi}_{f,k} \stackrel{\rm def}{=} \frac{j!\,\,\overline{\Delta T}_{f,j}(x_k,d_{k,j})}{\delta_k^{j}},
\end{equation}
where $j$ is the model's degree resulting from \al{STEP1} at iteration $k$. Then,
\beqn{phi-hat-eps}
\widehat{\phi}_{f,k}\geq \frac{\varsigma\epsilon_{\min}}{1+\omega},
\end{equation}
with $\epsilon_{\min}=\min_{j\in \{1,\ldots,q\}} \epsilon_j$.
Moreover,
\beqn{DT-phi}
\Delta T_{f,j}(x_k,s_k) \geq \widehat{\phi}_{f,k}\frac{\delta_k^{j}}{j!}
\tim{ and }
\Delta_k
\geq  \min\left\{\gamma_1\theta,\kappa_r \min_{i\in\iiz{k}}\widehat{\phi}_{f,i}\right\}
\end{equation}
where
\beqn{kappar-def}
\kappa_r
\stackrel{\rm def}{=} \frac{\gamma_1(1-\eta_2)}{4 \max[1,L_f]}
\min\left[\theta,\frac{\Delta_0 \min_{j=1,\ldots,q} \delta_{0,j}^j }
{2q(\max_{j=1,\ldots,q}\|\nabla _x^i f(x_0)\|+\kappa_{\zeta})}\right] \in (0,1).
\end{equation}
}

\noindent
Using these results, we may consider the all-important lower bound on the
model decrease at successful iterations.

\llem{lemma:noisy-decrease}{
Suppose that $\vartheta_d >0$ and let $k$ be the index of a successful
iteration of the \al{TR$q$EDAN} algorithm before termination. Then
\begin{equation}
\label{decr}
\overline{\Delta T}_{f,j}(x_k,s_k)
\ge
\frac{\vartheta_d}{\omega}\varsigma\kappa_{\delta}\epsilon_{\min},
\end{equation}
where
\beqn{kappddef}
\kappa_\delta \stackrel{\rm def}{=} \frac{\kappa_r}{1+\omega}.
\end{equation}
}

\proof{
Observe first that, since iteration $k$ is successful, the algorithm must have
reached the end of Step~3 at this iteration, and thus termination did not
occur in Steps 1 or 2. This means in particular, in view of
\req{improve-possible}, that
\beqn{good-zetas}
\zeta_{d, i_\zeta} > \vartheta_d
\end{equation}
for all values of the accuracy threshold $\zeta_{d, i_\zeta}$ encountered during
Steps 1 and 2 of iteration $k$. Moreover Lemma~\ref{lemma:no-term-step1}
applies and \req{barDTd-lower} and \req{good-zetas} imply that
\beqn{4-22}
\overline{\Delta T}_{f,j}(x_k,d_{k,j})
\geq \frac{\zeta_{d,i_\zeta}}{\omega} \sum_{\ell=1}^j\frac{\delta_k^\ell}{\ell!}
\geq \frac{\vartheta_d}{\omega}\delta_k,
\end{equation}
again irrespective of the accuracy threshold $\zeta_{d, i_\zeta}$ encountered during
Steps 1 and 2.

We now distinguish two cases, depending on the ratio between $\Delta_k$ and $\theta$.\\
\noindent
{\bf $\bullet$}  Suppose first that $\Delta_k\leq \theta$, (or, equivalently, that
$\delta_k=\Delta_k$).  Then, using \req{step-subproblem} and \req{4-22},  we obtain
that
\beqn{4-22-b}
\overline{\Delta T}_{f,j}(x_k,s_k)
= \overline{\Delta T}_{f,j}(x_k,d_{k,j})
\geq \frac{\vartheta_d}{\omega}\delta_k
\end{equation}
Now, since $\delta_k=\Delta_k \leq \theta$, \req{phi-hat-eps} and the second part
\req{DT-phi} in Lemma~\ref{lemma:phihat} ensure that
$\delta_k \geq \kappa_r \varsigma \epsilon_{\min} / (1+\omega)$. Substituting this latter bound
in \req{4-22-b} then yields
\[
\overline{\Delta T}_{f,j}(x_k,s_k)
\geq \frac{\vartheta_d\,\kappa_r\,\epsilon_{\min}}{\omega(1+\omega)}
\]
and \req{decr} follows.\\
\noindent
{\bf $\bullet$}  Suppose now that $\Delta_k> \theta$, (or, equivalently, that
$\delta_k<\Delta_k$).  Then $\delta_k = \theta$. Suppose first that $\|s_k\|\geq
\delta_k=\theta$.  Lemma~\ref{lemma:step2-res} ensures that  \al{STEP2}
terminates with {\tt accuracy}$_s$\, being {\tt relative}\ and  \req{verif-term-2} holds for
$x=x_k$ and $v=s_k$. As a consequence, using \req{kappar-def}, \req{kappddef} and the fact
that $\varsigma\epsilon_{\min}\leq 1$,
\[
\overline{\Delta T}_{f,j}(x_k,s_k)
\geq \frac{\zeta_{d,i_\zeta}}{\omega} \sum_{\ell=1}^r \frac{\delta_k^\ell}{\ell!}
> \frac{\vartheta_d}{\omega}\sum_{\ell=1}^r \frac{\delta_k^\ell}{\ell!}
\geq \frac{\vartheta_d}{\omega}\theta
\geq \frac{\vartheta_d}{\omega}\varsigma\kappa_\delta \epsilon_{\min},
\]
again implying \req{decr}.  Suppose finally that $\|s_k\|< \delta_k=\theta$.
Then we deduce from  \req{4-22} and \req{step-subproblem} that
\[
\overline{\Delta T}_{f,j}(x_k,s_k)
\geq \overline{\Delta T}_{f,j}(x_k,d_{k,j})
\geq \frac{\vartheta_d}{\omega}\delta_k
= \frac{\vartheta_d}{\omega}\theta
\geq \frac{\vartheta_d}{\omega}\varsigma\kappa_\delta \epsilon_{\min}
\]
and \req{decr} also holds in this last case.

\noindent
Of course, this lemma does not allow any useful conlusion if $\vartheta_d=0$,
that is in the noiseless case.  But we can call on the noiseless analysis of
\cite{CartGoulToin20c} to cover this case.

\llem{lemma:noiseless-decrease}
Suppose that $\vartheta_d=0$. Then, for every $k$ before termination,
\beqn{noiseless-decrease}
\Delta T_j(x_k,s_k) \geq \frac{1}{q!}(\varsigma\kappa_\delta)^{q+1} \epsilon_{\min}^{q+1},
\end{equation}
where $\kappa_\delta$ is defined in \req{kappddef}.
}

\proof{See \cite[Lemma~3.7]{CartGoulToin20c}.  The proof is based on using
  \req{DT-phi} and \req{phi-hat-eps} in Lemma~\ref{lemma:phihat}.
}

\noindent
We may finally combine Lemmas~\ref{lemma:step1-termination},
\ref{lemma:step2-termination}, \ref{lemma:noisy-decrease} and
\ref{lemma:noiseless-decrease} to derive a upper-bound on the number of
evaluations required by the \al{TR$q$EDAN} algorithm for termination.

\lthm{theorem:trqedan-complexity}{
Suppose that AS.1--AS.3 hold and define $\epsilon_{\min} =
\min_{j\in\ii{q}}\epsilon_j$. Then there exists positive constants
$\kappa^A_{{\sf TRqEDAN}}$, $\kappa^B_{{\sf TRqEDAN}}$,
$\kappa^C_{{\sf TRqEDAN}}$, $\kappa^D_{{\sf TRqEDAN}}$,
$\kappa^E_{{\sf TRqEDAN}}$ and $\kappa^S_{{\sf TRqEDAN}}$
such that the \al{TR$q$EDAN} algorithm needs at most
\beqn{number-derivs}
\begin{array}{l}
\kappa^{S}_{{\sf TRqDAN}}\,\bigfrac{f(x_0)-f_{\rm low}}
         {\max[\vartheta_f,\vartheta_d\epsilon_{\min},\epsilon_{\min}^{q+1}]}
         + \kappa^D_{{\sf TRqDAN}}
        \left|\log\left(\epsilon_{\min}\right)\right|
+ \kappa^E_{{\sf TRqEDAN}}
\\*[3ex]
\hspace*{6cm}
= {\cal O}\left(\min\left[\vartheta_f^{-1},(\vartheta_d\epsilon_{\min})^{-1},\epsilon_{\min}^{-(q+1)}\right]\right)
\end{array}
\end{equation}
evaluations of the (inexact) derivatives $\{\nabla_x^\ell f(x)\}_{\ell=1}^q$, and at most
\beqn{number-f}
\begin{array}{l}
  \kappa^A_{{\sf TRqEDAN}}\bigfrac{f(x_0)-f_{\rm low}}
        {\max\left[\vartheta_f,\vartheta_d\epsilon_{\min},\epsilon_{\min}^{q+1}\right]}
+ \kappa^B_{{\sf TRqEDAN}}\big|\log(\epsilon_{\min})\big|  + \kappa^C_{{\sf TRqEDAN}} \\*[3ex]
\hspace*{6cm}
= {\cal O}\left(\min\left[ \vartheta_f^{-1},(\vartheta_d\epsilon_{\min})^{-1},\epsilon_{\min}^{-(q+1)}\right]\right)
\end{array}
\end{equation}
evaluations of $f(x)$ itself to terminate with flags {\tt status}, {\tt order}, {\tt delta},
{\tt radius}\ and a point $\tilde{x}$ at which
\beqn{optimality0}
\phi_{f,i}^\delta(\tilde{x}) \leq \epsilon_i\frac{\delta^i}{i!}
\tim{for} i\in\ii{j-1}
\end{equation}
and
\begin{align}
{\bf \bullet} & \;\;\;\;
\phi_{f,i}^\delta(x) \leq \epsilon_i \frac{\delta^i}{i!} \tim{for} i \in \iibe{j}{q}\label{optimality1}\\
&\hspace*{7cm} \tim{if {\tt status}\ = {\tt approximate-minimizer};}\nonumber\\
{\bf \bullet} & \;\;\;\;
\phi_{f,j}^\delta(\tilde{x}) \leq \frac{4\vartheta_d}{\gamma_\zeta \omega}\delta\label{optimality2}\\
&\hspace*{7cm} \tim{if {\tt status}\ = {\tt in-noise-phi};}\nonumber\\
{\bf \bullet} & \;\;\;\;
\phi_{f,j}^\nu(\tilde{x}) \leq \frac{4\vartheta_d}{\gamma_\zeta\omega}
\max\big[\nu,\nu^j\big]\label{optimality3}\\
&\hspace*{7cm} \tim{if {\tt status}\ = {\tt in-noise-s},}\nonumber
\end{align}
where  $j$ = {\tt order}, $\delta$ = {\tt delta}\ and $\nu$ = {\tt radius}.
If, in addition,
\beqn{sk-globmin}
s_k =\arg\max_{\|s_k\|\leq \Delta_k} \overline{\Delta T}_{f,j}(x_k,s)
\end{equation}
at iteration $k$ at which termination occurs with {\tt status}\ = {\tt in-noise-f},
then
\beqn{optimality4}
\phi_{f,j}^\nu(\tilde{x}) \leq
\frac{\vartheta_f}{\varsigma}(1+\frac{1}{\omega}).
\end{equation}
}

\proof{
We note that the various flag-dependent optimality guarantees
\req{optimality0}--\req{optimality3} are a simple compilation of the results of
Lemmas~\ref{lemma:step1-termination} and \ref{lemma:step2-termination}. To
prove \req{optimality4}, observe that, if termination occurs in Step~3 (as
indicated by {\tt status}\ = {\tt in-noise-f}), it
must be because $\overline{\Delta T}_{f,j}(x_k,s_k)\leq \vartheta_f/\omega$.  But
\req{deltak-def} and \req{sk-globmin} imply that
\begin{align*}
\overline{\phi}_{f,j}^{\delta_k}(x_k)
&  =  \overline{\Delta T}_{f,j}(x_k,s_k)  \leq \bigfrac{\vartheta_f}{\omega}  \mbox{\hspace*{10mm}if } \|s_k\|\leq \delta_k,\\*[2ex]
\overline{\phi}_{f,j}^{\|s_k\|}(x_k)
&\leq \overline{\Delta T}_{f,j}(x_k,s_k)  \leq \bigfrac{\vartheta_f}{\omega}  \mbox{\hspace*{10mm}if } \|s_k\| > \delta_k.
\end{align*}
Moreover, the fact that Step~3 has been reached ensures that termination did
not occur in either Step~1 or Step~2. Thus \req{phi-end-step1} in
Lemma~\ref{lemma:no-term-step1} with the definition {\tt radius}\ = $\max[\delta_k,\|s_k\|]$ gives \req{optimality4}.

We now focus on proving \req{number-derivs} and \req{number-f}.  Let $k$ be the
index of a successful iteration before termination. Because \req{Df+-DT} and
\req{Df-DT} both hold at every successful iteration  before termination, we
have that, for each $i\in{\cal S}_k$
\[
f(x_i)-f(x_{i+1})
\geq [\overline{f}(x_i) - \overline{f}(x_{i+1})] - 2 \omega \overline{\Delta T}_{f,j}(x_i,s_i)
\geq (\eta_1 -2 \omega) \overline{\Delta T}_{f,j}(x_i,s_i).
\]
Combining now this inequality with Lemmas~\ref{lemma:noisy-decrease} and
\ref{lemma:noiseless-decrease} we obtain that
\beqn{decr1}
f(x_i)-f(x_{i+1})
\geq (\eta_1 -2 \omega) \max\left[\frac{\vartheta_d}{\omega}\varsigma\kappa_{\delta}\epsilon_{\min},
  \frac{1}{q!}(\varsigma\kappa_\delta)^{q+1} \epsilon_{\min}^{q+1}\right].
\end{equation}
Moreover, the mechanism of Step~3 of the \al{TR$q$EDAN} algorithm implies that
\beqn{decr2}
f(x_i)-f(x_{i+1}) > \frac{\eta_1-2\omega}{\omega}\,\vartheta_f.
\end{equation}
From \req{decr1} and \req{decr2}, we thus deduce that
\[
f(x_i)-f(x_{i+1})
\geq (\eta_1 -2 \omega)
  \max\left[\frac{\vartheta_d}{\omega}\varsigma\kappa_{\delta}\epsilon_{\min},
      \frac{1}{q!}(\varsigma\kappa_\delta)^{q+1}\epsilon_{\min}^{q+1},\frac{\vartheta_f}{\omega}\right]
\stackrel{\rm def}{=} \Delta_f.
\]
Using now the standard ``telescoping sum'' argument and AS.3, we obtain that
\[
f(x_0) - f_{\rm low}
\geq f(x_0)-f(x_{k+1})
= \sum_{i\in {\cal S}_k} [ f(x_i)- f(x_{i+1})]
\geq |{\cal S}_k| \Delta_f,
\]
so that the total number of successful iterations before termination is
\beqn{Sk-bound}
|{\cal S}_k|
\leq \frac{f(x_0)-f_{\rm low}}{\Delta_f}
= \kappa^S_{{\sf TRqEDAN}} \frac{f(x_0)-f_{\rm low}}
    {\max\left[\vartheta_f,\vartheta_d\epsilon_{\min},\epsilon_{\min}^{q+1}\right]}
\end{equation}
where
\[
\kappa^S_{{\sf TRqEDAN}}
\stackrel{\rm def}{=} \frac{1}{(\eta_1-2\omega)}
       \max\left[\frac{1}{\omega},\frac{(\varsigma\kappa_\delta)^{q+1}}{q!}\right]^{-1}.
\]
Now \req{phi-hat-eps}, the second part of \req{DT-phi} and \req{kappddef} imply that
\beqn{rkmin}
\Delta_k\geq \varsigma\kappa_\delta \epsilon_{\min},
\end{equation}
so that, invoking now Lemma~\ref{lemma:SvsU}, we deduce that the total number of
iterations before termination is bounded above by
\[
n_{\rm it}
\stackrel{\rm def}{=} \frac{f(x_0)-f_{\rm low}}{\Delta_f}\, \left(1+\frac{\log\gamma_3}{|\log\gamma_2|}\right)
+ \frac{1}{|\log\gamma_2|}
\left|\log\left(\frac{\varsigma\kappa_\delta \epsilon_{\min}}{\Delta_0}\right)\right|.
\]
Since each iteration of the \al{TR$q$EDAN} algorithm inexactly compute the
objective function's value at most twice (in Step~3),
we obtain that the total number of such evaluations before termination is
bounded above by $2n_{\rm it}$, yielding \req{number-f} with
\[
\kappa^A_{{\sf TRqEDAN}}
\stackrel{\rm def}{=} \frac{2}{\eta_1-2\omega} \min\left[\omega,\frac{q!}{(\varsigma\kappa_\delta)^{q+1}}\right]
       \left(1+\frac{\log\gamma_3}{|\log\gamma_2|}\right),
\]
\[
\kappa^B_{{\sf TRqEDAN}} \stackrel{\rm def}{=} \frac{2}{|\log\gamma_2|}
\tim{ and }
\kappa^C_{{\sf TRqEDAN}} \stackrel{\rm def}{=} \frac{2}{|\log\gamma_2|}
\left|\log\left(\frac{\varsigma\kappa_\delta}{\Delta_0}\right)\right|.
\]

To complete the proof, we need to elaborate on \req{Sk-bound} to derive an
upper bound on the number of derivatives evaluations. While the \al{TR$q$EDAN}
algorithm evaluates $\{\nabla_x^\ell f(x_k)\}_{\ell=1}^j$ at least once in
Step~1, it may need to evaluate the derivatives also when \al{CHECK} returns
{\tt insufficient}, and this can happen in the loops between Steps~1.4 and 1.1 in
Algorithm~\ref{algorithm:phij} and between Steps~2.4 and 2.1 in the \al{STEP2}
algorithm. Thus the total number of derivatives' evaluations is given by
$|{\cal S}_k|$ plus the total number of accuracy tightenings (counted by
$i_\zeta$).  The next step is therefore to establish an upper bound on this
latter number. This part of the proof is a variation on that of Theorem~3.8 in
\cite{CartGoulToin20c}, now involving the bounds \req{term-bound-phi} and
\req{step2-bound} but also the additional inequality $\zeta_{d,i_\zeta} \geq
\vartheta_d$ which must hold as long as termination has not
occured.  To summarize the argument, these three bounds ensure a global lower
bound $\zeta_{d,\min}$ on $\zeta_{d,i_\zeta}$, while an upper bound is given
by $\kappa_\zeta$.  Since each tightening proceeds by multiplying the accuracy
threshold by $\gamma_\zeta$, one then deduces that the maximum number of such
tightenings is ${\cal O}\big(|\log(\zeta_{d,\min}/\kappa_\zeta)|\big)$, which then leads to
\req{number-derivs}.  The details are given in appendix.
}

\noindent
Observe that condition \req{sk-globmin} needs only to be enforced if the bound
\req{optimality4} is desired and when termination occurs with {\tt status}\ =
{\tt in-noise-f}. Should \req{optimality4} be of interest, the step
may have to be recomputed in the course of the algorithm to
ensure \req{sk-globmin},  whenever $\overline{\Delta T}_{f,j}(x_k,s_k) <
\vartheta_f/\omega$. Termination is then declared if this inequality still
holds for the new step, or the algorithm is continued otherwise.

The results of Theorem~\ref{theorem:trqedan-complexity} merit some comments.
Firstly, and as expected, we see in the bounds \req{number-derivs} and
\req{number-f} that the total number of evaluations needed for the
\al{TR$q$EDAN} to terminate may be considerably smaller when intrinsic noise
is present ($\vartheta_d >0$ and $\vartheta_f>0$) than in the noiseless
situation ($\vartheta_d=\vartheta_f=0$), in which case we recover the bound in
${\cal O}(\epsilon_{\min}^{-(q+1)})+{\cal O}(|\log(\epsilon_{\min})|)$ of
\cite{CartGoulToin20c}. More interestingly, we note that, for the intrinsic
noise to be small enough to let the trust-region algoritm run its course
unimpeded, we need that $\vartheta_d = {\cal O}(\epsilon_{\min}^q)$ and $\vartheta_f =
{\cal O}(\epsilon_{\min}^{q+1})$.  Since $\vartheta_d$ and $\vartheta_f$ are intrinsic to
the problem, it means that we expect the algorithm to run unimpeded (in the
worst case) only if \beqn{order-observation} \epsilon_{\min} \gtrsim
\max\left[\vartheta_f^{\frac{1}{q+1}},\vartheta_d^{\frac{1}{q}}\right].  \end{equation}
To give an example, suppose that we are applying the \al{TR$q$EDAN} algorithm
to find second-order approximate minimizers on a machine whose machine
precision is $10^{-15}$. This suggest that (in the worst case again), the
algorithm could work as if noise where absent for $\epsilon_{\min}$ of order $10^{-5}$
and above. Of course, this ignores that some of the deterministic bounds we
have imposed could fail and yet the algorithm could proceed without trouble.

We also note that the second term in \req{number-derivs}, which accounts for
the additional evaluations due to inexact but still acceptable evaluations,
now involves a term in $|\log(\vartheta_d/\kappa_\zeta)|$ (the magnitude of the
accuracy range between it initial value and noise) along with the term in
$\log(\epsilon_{\min})=\log(\epsilon_{\min}^q)$ of \cite{CartGoulToin20c}. This is coherent
with our observation \req{order-observation}.

We finally note the difference between the impact of the absolute noise on
the objective function's values ($\vartheta_f$) and that on the derivatives
($\vartheta_d$), the former being significantly more limitative than the
latter. This is reminiscent of similar observations and assumptions
in the stochastic context \cite{BeraCaoSche19,BellGuri21,BlanCartMeniSche19}.

\numsection{Conclusions and Perspectives}
\label{section:conclusion}

We have discussed the evaluation complexity of trust-region algorithms in the
presence of intrinsic noise on function and derivatives values, possibly
causing early termination of the minimization method. We have produced an
evaluation complexity bound which stresses this dependence and relates it to
the complexity bound for the noiseless, albeit inexact, case. In our analysis,
we have priviledged focus and clarity over generality. We have already
mentioned that the noise levels and accuracy thresholds could be made
dependent on the degree of the derivative considered, but other extensions are
indeed possible.  The first is to consider constrained problems, where the
feasible set is convex (or even ``inexpensive'' or ``simple'', see
\cite{BellGuriMoriToin19,CartGoulToin20b,CartGoulToin20a}).  The second is to
replace the Lipschitz continuity required in AS.2 by the weaker H\"{o}lder
continuity (as in
\cite{CartGoulToin17d,CartGoulToin18a,CartGoulToin16,GrapNest17,Nest15}). The
minimization of composite function (using techniques of
\cite{CartGoulToin20b,GratSimoToin20,Nest13}) is another possibility.

Finally, considering ``noise-aware'' stochastic minimization algorithm is also
of interest, and will be reported on in a forthcoming report.

{\footnotesize

redpajama_set_name: RedPajamaArXiv


text:
A Rendőrakadémia 6. – Az ostromlott város (eredeti cím: Police Academy 6: City Under Siege) 1989-ben bemutatott amerikai bűnügyi filmvígjáték, amely a Rendőrakadémia-sorozat hatodik része, és főképp Los Angelesben játszódik. Az élőszereplős játékfilm rendezője Peter Bonerz, producerei Paul Maslansky és Donald L. West. A forgatókönyvet Stephen Curwick írta, a zenéjét Robert Folk szerezte. A mozifilm gyártója és forgalmazója a Warner Bros. Pictures.

Amerikában 1989. március 10-én, Magyarországon 1991. június 14-én mutatták be a mozikban.

Cselekmény

Szereplők

Televíziós megjelenések
HBO, TV3, RTL Klub, Film+, Cool, Prizma TV / RTL+, RTL II, Viasat 3, AXN, AXN Black, Viasat 6

Jegyzetek

Források

További információk

1989 filmjei
Rendőrakadémia
Amerikai bűnügyi filmek
Amerikai filmvígjátékok
Warner Bros. Pictures-filmek
InterCom-filmek

redpajama_set_name: RedPajamaWikipedia


Mary-Louise will be teaching a simple knicker making class. With a choice of pattern design, there will be options for a thong, mid-size brief or boy shorts. You may get a chance to start a second pair depending on how quickly you work.
There will be a bra making class on 3rd March.
A requirements pack will be available on booking this class in the shop. A basic sewing kit will be required.
Tea and coffee will be in plentiful supply.


Daniel Connell, the creator of the SolarFlower has released another very useful DIY tutorial. This one is for building a wind turbine from scratch for only about $30 in material costs. The solution he proposes is a vertical axis wind turbine based on the Lenz2 lift+drag design.
Most of the materials for building the wind turbine can be repurposed, while the three vane version of the turbine can be easily built by one person in about 6 hours. One of the key components of an energy harvesting wind turbine is an alternator to the rotor. Daniel's plans call for using a 50% efficient car alternator, as the most accessible and affordable option, which would be able to produce 158 watts of electricity in a 50 km/h winds, and 649 watts at 80 km/h winds.
Finding a method for storing the electricity produced is also important, though the energy harvested by the turbine could also be used solely for mechanical purposes like rotation of a water pump, or spinning a flywheel.
The construction of the wind turbine requires basic tools, such as a hand drill, a pop riveter and assorted hardware, like bolts, washers and nuts. A single DIY wind turbine like this is probably not going to be able to produce enough energy to power your house, though you might consider building a series of them and storing the energy produced in a battery bank. A solution like that would produce enough power for a small household.
Detailed written instructions can be found on the SolarFlower.org website. Below is also a video on the construction process filmed by Daniel.