affil0affil0affiliationtext: Department of Industrial and Systems Engineering,
Lehigh University, USA

# Worst-Case Complexity of an SQP Method for Nonlinear Equality Constrained
Stochastic Optimization

Frank E. Curtis E-mail<EMAIL_ADDRESS>supported by NSF Grant
CCF-2008484 and ONR Grant N00014-21-1-2532 Michael J. O’Neill E-mail:
<EMAIL_ADDRESS>supported by the CI Fellows Program Daniel P. Robinson
E-mail<EMAIL_ADDRESS>supported by supported by ONR Grant
N00014-21-1-2532

A worst-case complexity bound is proved for a sequential quadratic
optimization (commonly known as SQP) algorithm that has been designed for
solving optimization problems involving a stochastic objective function and
deterministic nonlinear equality constraints. Barring additional terms that
arise due to the adaptivity of the monotonically nonincreasing merit parameter
sequence, the proved complexity bound is comparable to that known for the
stochastic gradient algorithm for unconstrained nonconvex optimization. The
overall complexity bound, which accounts for the adaptivity of the merit
parameter sequence, shows that a result comparable to the unconstrained
setting (with additional logarithmic factors) holds with high probability.

##  1 Introduction

We present a worst-case complexity analysis of an algorithm for minimizing a
smooth objective function subject to nonlinear equality constraints. (Due to
the nature of the algorithm, this worst-case complexity analysis holds in
terms of iterations, function evaluations, and derivative evaluations.)
Problems of this type arise in various important applications throughout
science and engineering, including optimal control, PDE-constrained
optimization, and resource allocation [3, 4, 15, 22]. However, unlike the vast
majority of the literature on equality constrained optimization, the algorithm
that we consider has been designed to solve problems in which the objective
function is stochastic, in the sense that it is defined by the expectation of
a function that has a random variable argument. The algorithm that we consider
assumes that evaluations of the objective function and its gradient are
intractable to obtain, but that it has access to (unbiased) stochastic
gradient estimates.

A few algorithms have been proposed recently for solving problems of this
type. These approaches fall into two categories: penalty methods [7, 19, 23]
(which includes the class of augmented Lagrangian methods) and sequential
quadratic optimization (commonly known as SQP) methods [2, 18]. Penalty
methods aim to solve the constrained optimization problem by adding a term to
the objective function, weighted by a penalty parameter, that penalizes
constraint violation. Unconstrained optimization techniques are then applied
to minimize the resulting penalty function, after which the penalty parameter
may be modified and the minimization is performed again in an iterative manner
until a solution is obtained that (approximately) satisfies the original
constraints. Methods of this type perform well in some situations, but in
others they perform poorly, e.g., due to ill-conditioning and/or nonsmoothness
of the subproblems. Such methods also often suffer due to their sensitivity to
the particular scheme used for updating the penalty parameter.

In practice in both deterministic and stochastic optimization contexts,
penalty methods are frequently outperformed by SQP methods. Indeed, it is
commonly accepted in the deterministic optimization literature that a state-
of-the-art algorithm is an SQP method that chooses stepsizes based on a line
search applied to a merit function. In this deterministic setting, such an
algorithm is intimately connected with applying Newton’s method to the first-
order primal-dual necessary conditions for optimality of the problem [25].

In this paper, we present a worst-case complexity analysis of the SQP method
proposed in [2], which can be seen as an extension of an SQP method from the
deterministic to the stochastic setting. A consequence of our analysis is
that, in an idealized setting in which one knows a threshold for the merit
parameter beyond which the merit function is _exact_ [13], the number of
iterations required until the method generates a point at which first-order
necessary conditions for optimality hold in expectation with accuracy
$\varepsilon\in(0,\infty)$ is ${\cal O}(\varepsilon^{-4})$. This is arguably
the best result that one can expect given this is the same bound proved to
hold for a stochastic gradient method employed to solve an unconstrained
nonconvex problem [11]. However, _our analysis does not only consider this
idealized setting_ ; we go further and prove a worst-case complexity bound for
the algorithm when the merit parameter threshold is unknown and the algorithm
adaptively updates a monotonically nonincreasing merit parameter sequence. We
prove under reasonable assumptions that the aforementioned worst-case bound,
with additional logarithmic factors, holds with high probability. The high-
probability aspect of this result arises purely due to the uncertainty of the
behavior of the adaptive merit parameter sequence, and does not reflect any
uncertainty of the behavior of the method during situations in which the merit
parameter sequence remains constant.

To the best of our knowledge, ours is the first worst-case complexity result
for an SQP algorithm that operates in the _highly stochastic regime_ (where
one merely presumes that the stochastic gradient estimates have bounded
variance) for solving stochastic optimization problems involving deterministic
nonlinear equality constraints. Prior to this work, the only known complexity
results for stochastic constrained optimization were for algorithms for
solving problems with simple constraint sets that enable projection-based
methods [11, 12] and Frank-Wolfe type methods [14]. (One exception is a
complexity bound proved for the SQP algorithm proposed in [18], although that
result only holds for the idealized setting in which the algorithm has _a
priori_ knowledge of a threshold for the merit function parameter.) Our
analysis focuses a great deal on the complications that arise due to the
adaptivity of the merit parameter sequence, which essentially means that the
algorithm in our consideration is aiming to reduce a merit function that
_changes_ during the optimization process. Hence, many aspects of our analysis
are quite distinct from the analyses that have been presented for stochastic
gradient methods in the context of unconstrained optimization or optimization
over simple constraint sets, for which the tool for measuring the progress of
an algorithm—namely, the objective function itself—remains the same throughout
the optimization.

###  1.1 Problem formulation

The algorithm that we consider is designed to solve problems of the form

$\min_{x\in\mathbb{R}^{n}}f(x)\ \ \operatorname{s.\\!t.}\ \ c(x)=0,\ \
\text{with}\ \ f(x)=\mathbb{E}[F(x,\omega)],$ (1)

where $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$,
$c:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$, $\omega$ is a random variable
with associated probability space $(\Omega,\mathcal{F},P)$,
$F:\mathbb{R}^{n}\times\Omega\rightarrow\mathbb{R}$, and $\mathbb{E}$
represents expectation with respect to $P$. In particular, following [2], we
make the following assumption about problem (1) and the algorithm that we
analyze (stated as Algorithm 1 on page 1), which in any run generates a
sequence of iterates $\\{x_{k}\\}\subset\mathbb{R}^{n}$.

######  Assumption 1.

Let ${\cal X}\subseteq\mathbb{R}^{n}$ be an open convex set that contains
$\\{x_{k}\\}$ for all realizations of Algorithm 1. The objective function
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is continuously differentiable and
bounded below by $f_{\text{\rm low}}\in\mathbb{R}$ over ${\cal X}$ and the
corresponding gradient function $\nabla
f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is bounded and Lipschitz continuous
with constant $L\in(0,\infty)$ over ${\cal X}$. The constraint function
$c:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ $($where $m\leq n$$)$ and the
corresponding Jacobian function $J:=\nabla
c^{\top}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m\times n}$ are bounded over
${\cal X}$, each gradient function $\nabla
c_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is Lipschitz continuous with
constant $\gamma_{i}$ over ${\cal X}$ for all $i\in\\{1,\dots,m\\}$, and the
singular values of $J\equiv\nabla c^{\top}$ are bounded below and away from
zero over ${\cal X}$.

A consequence of Assumption 1 is that there exists
$\kappa_{g}\in\mathbb{R}_{>0}$ such that

$\|\nabla f(x_{k})\|\leq\kappa_{g}\ \ \text{for any $k\in\mathbb{N}$ in any
realization of Algorithm~{}\ref{alg:ssqp}}.$ (2)

Defining the Lagrangian
$\ell:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}$ corresponding
to (1) by $\ell(x,y):=f(x)+c(x)^{\top}y$, first-order primal-dual stationarity
conditions for (1), which are necessary for optimality under Assumption 1, are
given by

$0=\left[\begin{matrix}\nabla_{x}\ell(x,y)\\\
\nabla_{y}\ell(x,y)\end{matrix}\right]=\left[\begin{matrix}\nabla f(x)+\nabla
c(x)y\\\ c(x)\end{matrix}\right].$ (3)

###  1.2 Notation

We adopt the notation that $\|\cdot\|$ denotes the $\ell_{2}$-norm for vectors
and the vector-induced $\ell_{2}$-norm for matrices. We denote by
$\mathbb{S}^{n}$ the set of $n\times n$ dimensional real symmetric matrices.
The set of nonnegative integers is denoted as
$\mathbb{N}:=\\{0,1,2,\dots,\\}$. For any integer $k\in\mathbb{N}$, we use
$[k]$ to denote the subset of nonnegative integers up to $k$, namely,
$[k]:=\\{0,\dots,k\\}$. Correspondingly, to represent a set of vectors
$\\{v_{0},\dots,v_{k}\\}$, we define $v_{[k]}:=\\{v_{0},\dots,v_{k}\\}$.

Given $\phi:\mathbb{R}\to\mathbb{R}$ and $\varphi:\mathbb{R}\to[0,\infty)$, we
write $\phi(\cdot)={\cal O}(\varphi(\cdot))$ to indicate that
$|\phi(\cdot)|\leq c\varphi(\cdot)$ for some $c\in(0,\infty)$. Similarly, we
write $\phi(\cdot)=\widetilde{\cal O}(\varphi(\cdot))$ to indicate that
$|\phi(\cdot)|\leq c\varphi(\cdot)|\log^{\mkern
1.5mu\overline{\mkern-1.5muc}}(\cdot)|$ for some $c\in(0,\infty)$ and $\mkern
1.5mu\overline{\mkern-1.5muc}\in(0,\infty)$. In this manner, one finds that
${\cal O}(\varphi(\cdot)|\log^{\mkern
1.5mu\overline{\mkern-1.5muc}}(\cdot)|)\equiv\widetilde{\cal
O}(\varphi(\cdot))$ for any $\mkern
1.5mu\overline{\mkern-1.5muc}\in(0,\infty)$.

Algorithm 1 is iterative, generating in each realization a sequence
$\\{x_{k}\\}$. (See Section 4.1 for a complete description of the stochastic
process generated by the algorithm.) For our analysis, we also append the
iteration number to other quantities corresponding to each iteration, e.g.,
$f_{k}:=f(x_{k})$ for all $k\in\mathbb{N}$.

When discussing stochastic quantities, we use capital letters to denote random
variables and corresponding lower case letters to denote a realization of a
random variable. For example, a stochastic gradient in iteration
$k\in\mathbb{N}$ is denoted as $G_{k}$, a realization of which is written as
$g_{k}$.

###  1.3 Outline

Section 2 provides a worst-case complexity result for the algorithm from [2]
for the deterministic setting, and uses this result and further commentary to
provide an overview of our main result for the stochastic setting. Details of
the algorithm for the stochastic setting are presented in Section 3, followed
by our main result and analysis, which are provided in Section 4. Finally, we
provide concluding thoughts and mention future directions in Section 5.

##  2 Outline of Main Results

Our algorithm of consideration, namely, Algorithm 3.1 in [2], is derived from
Algorithm 2.1 in [2], which is proposed and analyzed for the deterministic
setting as a precursor for the stochastic setting (of Algorithm 3.1 in [2]).
In the deterministic algorithm, the $k$th search direction
$d_{k}\in\mathbb{R}^{n}$ is computed by solving an optimization subproblem
defined by a quadratic approximation of the objective function and an affine
approximation of the constraints using derivative information at the current
iterate $x_{k}\in\mathbb{R}^{n}$. This computation also results in a Lagrange
multiplier vector $y_{k}\in\mathbb{R}^{m}$. The subsequent iterate is set by
$x_{k+1}\leftarrow x_{k}+\alpha_{k}d_{k}$, where $\alpha_{k}\in(0,\infty)$ is
a stepsize determined by a procedure to reduce the merit function
$\phi:\mathbb{R}^{n}\times(0,\infty)\to\mathbb{R}$ defined by

$\phi(x,\tau)=\tau f(x)+\|c(x)\|_{1}.$ (4)

In particular, based on properties of the search direction $d_{k}$, a value of
the merit parameter $\tau_{k}\in(0,\tau_{k-1}]$ is set by the algorithm, after
which $\alpha_{k}\in(0,\infty)$ is computed to ensure that
$\phi(x_{k},\tau_{k})-\phi(x_{k+1},\tau_{k})$ is sufficiently positive.

###  2.1 Complexity of the Deterministic Algorithm

To motivate our main result for the stochastic setting, it is instructive to
state a worst-case complexity bound for the deterministic algorithm. Such a
result is the following; further details and a proof are provided in Appendix
6.

######  Theorem 1.

Consider Algorithm 2.1 in [2] and suppose that Assumption 1 holds along with
Assumption 2.4 from [2]. Let $\tau_{-1}\in\mathbb{R}_{>0}$ be the initial
value of the merit parameter sequence and let $\tau_{\min}\in(0,\tau_{-1}]$ be
a positive lower bound for the merit parameter sequence $($the existence of
which follows from Lemma 2.16 in [2]$)$. Then, for any $\varepsilon\in(0,1)$,
there exists $(\kappa_{1},\kappa_{2})\in\mathbb{R}_{>0}\times\mathbb{R}_{>0}$
such that the algorithm reaches an iterate
$(x_{k},y_{k})\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ satisfying

$\|g_{k}+J_{k}^{\top}y_{k}\|\leq\varepsilon\ \ \text{and}\ \
\sqrt{\|c_{k}\|_{1}}\leq\varepsilon$ (5)

in a number of iterations no more than

$\left(\frac{\tau_{-1}(f_{0}-f_{\text{\rm
low}})+\|c_{0}\|_{1}}{\min\\{\kappa_{1},\tau_{\min}\kappa_{2}\\}}\right)\varepsilon^{-2}.$
(6)

Theorem 1 is not surprising. After all, such a complexity bound of ${\cal
O}(\varepsilon^{-2})$ is well-known for gradient-based algorithms in
unconstrained nonconvex optimization. Since Algorithm 2.1 in [2] and its
corresponding analysis do not exploit the use of exact higher-order derivative
information, this complexity bound is on the order of what could be expected
for such a method.

###  2.2 Preview of the Complexity of the Stochastic Algorithm

Moving to the stochastic setting, there are a few major technical hurdles that
need to be addressed, all of which relate to the adaptivity of the merit
parameter sequence. In particular, the analysis for the deterministic setting
relies heavily on the facts that $(i)$ each step of the algorithm yields a
sufficient reduction in the merit function for the current value of the merit
parameter, $(ii)$ each such reduction in the merit function can be tied to a
first-order primal-dual stationarity measure for the current iterate, and
$(iii)$ under Assumption 1, one can be certain of the existence of a positive
lower bound for the merit parameter sequence. This lower bound for the merit
parameter is referenced directly in the proof of the worst-case bound for the
deterministic algorithm; in particular, it is shown (see Lemma 14 and the
beginning of the proof of Theorem 4) that the improvement in the merit
function from any iterate that is not $\varepsilon$-stationary is at least
proportional to $\min\\{1,\tau_{\min}\\}\varepsilon^{-2}$, even if the current
value of the merit parameter is greater than $\tau_{\min}$. Unfortunately,
these properties of the steps and merit parameter sequence are not certain in
the stochastic setting. For example, as discussed in [2], it is possible—even
under Assumption 1—for the merit parameter sequence to vanish or for it to
eventually remain constant at a value that is not sufficiently small, and for
there to be iterations in which the expected reduction in the merit function
cannot be tied to a first-order primal-dual stationarity measure. As a result,
we have had to devise new analytical approaches that confront the fact that
$\\{\tau_{k}\\}$ is a random process, the ultimate behavior of which is
uncertain.

To aid the reader, we provide here an overview and commentary about our
ultimate complexity bound; see Corollary 1 on page 1. Our result is proved
under Assumption 1 along with others that are introduced in the subsequent
sections. For one thing, as is common in SQP methods for deterministic
optimization, we assume that the subproblem defining the search direction in
each iteration is defined by a matrix that is positive definite in the null
space of the constraint Jacobian; see Assumption 2 on page 2. We also assume,
as is common for stochastic gradient methods, that the stochastic gradient
estimates are unbiased with variance bounded by $M\in(0,\infty)$, along with
some related assumptions; see Assumption 3 on page 3. Furthermore, our
analysis conditions on the occurrence of an event that we call $E$ (see (17));
this event captures situations in which, over a total of
$k_{\max}+1\in\mathbb{N}$ iterations, the merit parameter is reduced at most
$s_{\max}\in[k_{\max}]$ times and the merit parameter is bounded below by
$\tau_{\min}\in(0,\infty)$. Under these conditions, our main complexity result
shows that, within $k_{\max}+1$ iterations, it holds with probability
$1-\delta\in(0,1)$ that the algorithm generates $x_{k^{*}}\in\mathbb{R}^{n}$
corresponding to which there exists an associated Lagrange multiplier
$y_{k^{*}}^{\text{\rm true}}\in\mathbb{R}^{m}$ such that

$\displaystyle\ \mathbb{E}[\|\nabla
f_{k^{*}}+J_{k^{*}}^{\top}y_{k^{*}}^{\text{\rm
true}}\|^{2}+\|c_{k^{*}}\|_{1}|E]$ $\displaystyle=$ $\displaystyle\ {\cal
O}\Bigg{(}\frac{\tau_{-1}(f_{0}-f_{\text{\rm
low}})+\|c_{0}\|_{1}+M}{\sqrt{k_{\max}+1}}$ (7a)
$\displaystyle\qquad+\frac{(\tau_{-1}-\tau_{\min})(s_{\max}\log(k_{\max})+\log(1/\delta))}{\sqrt{k_{\max}+1}}\Bigg{)}.$
(7b)

This form of the result is commonly called a convergence rate since it bounds
the expected stationarity error from above by a function that decreases with
the number of iterations performed, namely, $k_{\max}+1$. This bound can be
used to form a worst-case complexity result. Specifically, the result above
and Jensen’s inequality imply that, within $k_{\max}+1$ iterations and as long
as $s_{\max}={\cal O}(\log(k_{\max}))$ (more on this below), it holds with
probability $1-\delta$ that the algorithm requires at most $\widetilde{\cal
O}(\varepsilon^{-4})$ iterations to generate $x_{k^{*}}$ with corresponding
$y_{k^{*}}^{\text{\rm true}}$ such that $\mathbb{E}[\|\nabla
f_{k^{*}}+J_{k^{*}}^{\top}y_{k^{*}}^{\text{\rm true}}\||E]\leq\varepsilon$ and
$\mathbb{E}[\sqrt{\|c_{k^{*}}\|_{1}}|E]\leq\varepsilon$.

The first three quantities on the right-hand side of the convergence rate,
namely, in (7a), representing the initial objective function gap, initial
constraint violation, and the variance of the stochastic gradient estimates,
mirror the presence of similar terms that appear for comparable results for
the stochastic gradient method in an unconstrained or simple-constraint-set
setting. The final term in (7b), on the other hand, as well as the fact that
the result is stated as a high-probability result, are unique to our setting
and arise due to the adaptivity of the merit parameter sequence. If one were
to have prior knowledge of $\tau_{\min}$, then one could set
$\tau_{-1}=\tau_{\min}$ (and disable the update mechanism for the merit
parameter in the algorithm), in which case our analysis would show that the
expected stationarity error is bounded above by (7a) (surely, not only with
high probability).

In the context of an adaptive merit parameter sequence, the particular form of
our complexity result depends on the magnitude of $s_{\max}$ relative to
$k_{\max}+1$, i.e., the bound on the number of times that the merit parameter
is decreased relative to the total number of iterations performed. One setting
in which our result is relatively straightforward is when, over all
realizations of the algorithm, the differences between the stochastic gradient
estimates and the true gradients are bounded deterministically, in which case
$s_{\max}$ is bounded by a value that is independent from $k_{\max}+1$; this
follows from a deterministic lower bound on $\tau_{\min}$ [2, Proposition
3.18] and the fact that whenever the merit parameter is decreased, it is done
so by a constant factor. Beyond this setting, for another concrete example of
a situation in which $s_{\max}$ is guaranteed to be sufficiently small
relative to $k_{\max}$, we prove in Section 4.5 that if the distributions of
the stochastic gradient estimates are sub-Gaussian, then with probability
$1-\delta$ one finds that $s_{\max}={\cal
O}(\log(\log(\tfrac{k_{\max}}{\delta})))$, meaning that our proved convergence
rate is not ruined by the term in (7b).

##  3 Algorithm

For ease of reference, in this section we present Algorithm 3.1 from [2],
which is designed to solve problems of the form (1) and is our focus for the
remainder of the paper. In the spirit of an SQP method, the algorithm computes
a search direction $d_{k}$ and Lagrange multiplier vector $y_{k}$ in iteration
$k\in\mathbb{N}$ by solving

$\min_{d\in\mathbb{R}^{n}}\ f_{k}+g_{k}^{\top}d+\tfrac{1}{2}d^{\top}H_{k}d\ \
\operatorname{s.\\!t.}\ \ c_{k}+J_{k}d=0,$ (8)

where $H_{k}\in\mathbb{S}^{n}$ is chosen independently from $g_{k}$, and we
remind the reader that $g_{k}$ is a realization of the stochastic gradient
$G_{k}$. Under Assumption 1 and the following Assumption 2 (that we make
throughout the remainder of the paper), the solution of (8) can be obtained
from the unique solution of

$\left[\begin{matrix}H_{k}&J_{k}^{\top}\\\
J_{k}&0\end{matrix}\right]\left[\begin{matrix}d_{k}\\\
y_{k}\end{matrix}\right]=-\left[\begin{matrix}g_{k}\\\
c_{k}\end{matrix}\right].$ (9)

######  Assumption 2.

The sequence $\\{\|H_{k}\|\\}$ is bounded by $\kappa_{H}\in\mathbb{R}_{>0}$.
In addition, there exists $\zeta\in\mathbb{R}_{>0}$ such that, for all
$k\in[k_{\max}]$, the matrix $H_{k}\in\mathbb{S}^{n}$ has the property that
$u^{\top}H_{k}u\geq\zeta\|u\|_{2}^{2}$ for all $u\in\mathbb{R}^{n}$ such that
$J_{k}u=0$.

After computation of $(d_{k},y_{k})$, the remainder of the $k$th iteration
involves $(i)$ updating the merit parameter, $(ii)$ updating an auxiliary
parameter needed for the stepsize computation, and $(iii)$ computing a
positive stepsize. These algorithmic components are designed with the aim of
yielding a sufficiently positive reduction in a model of the merit function,
which in turn is aimed at yielding a sufficiently positive reduction in the
merit function itself. The algorithm employs the model
$q:\mathbb{R}^{n}\times\mathbb{R}_{+}\times\mathbb{R}^{n}\times\mathbb{S}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$
defined by

$q(x,\tau,g,H,d)=\tau(f(x)+g^{\top}d+\tfrac{1}{2}\max\\{d^{\top}Hd,0\\})+\|c(x)+J(x)d\|_{1},$

and the reduction function $\Delta
q:\mathbb{R}^{n}\times\mathbb{R}_{+}\times\mathbb{R}^{n}\times\mathbb{S}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$,
for a given $d\in\mathbb{R}^{n}$ satisfying $c(x)+J(x)d=0$, defined by

$\displaystyle\Delta q(x,\tau,g,H,d):=$ $\displaystyle\
q(x,\tau,g,H,0)-q(x,\tau,g,H,d)$ (10) $\displaystyle=$ $\displaystyle\
-\tau(g^{\top}d+\tfrac{1}{2}\max\\{d^{\top}Hd,0\\})+\|c(x)\|_{1}.$

Specifically, in order to ensure in iteration $k$ that
$\tau_{k}\leq\tau_{k-1}$ and

$\Delta
q(x_{k},\tau,g_{k},H_{k},d_{k})\geq\tfrac{1}{2}\tau\max\\{d_{k}^{\top}H_{k}d_{k},0\\}+\sigma\|c_{k}\|_{1}\geq
0$ (11)

holds for all $\tau\leq\tau_{k}$, the algorithm sets, for user-defined
$\sigma\in(0,1)$, the value

$\tau_{k}^{\rm trial}\leftarrow\begin{cases}\infty&\mbox{if
$g_{k}^{\top}d_{k}+\max\\{d_{k}^{\top}H_{k}d_{k},0\\}\leq 0$}\\\
\frac{(1-\sigma)\|c_{k}\|_{1}}{g_{k}^{\top}d_{k}+\max\\{d_{k}^{\top}H_{k}d_{k},0\\}}&\mbox{otherwise,}\end{cases}$
(12)

and then sets, for some $\epsilon_{\tau}\in(0,1)$, the merit parameter value

$\tau_{k}\leftarrow\begin{cases}\tau_{k-1}&\mbox{if
$\tau_{k-1}\leq\tau_{k}^{\rm trial}$}\\\ (1-\epsilon_{\tau})\tau_{k}^{\rm
trial}&\mbox{otherwise.}\end{cases}$ (13)

Then, for use in the stepsize computation (as motivated in [2]) it sets

$\xi_{k}^{\rm trial}\leftarrow\frac{\Delta
q(x_{k},\tau_{k},g_{k},H_{k},d_{k})}{\tau_{k}\|d_{k}\|^{2}}\ \ \text{then}\ \
\xi_{k}\leftarrow\begin{cases}\xi_{k-1}&\mbox{if }\xi_{k-1}\leq\xi_{k}^{\rm
trial}\\\ (1-\epsilon_{\xi})\xi_{k}^{\rm trial}&\mbox{otherwise}\end{cases}$
(14)

for some $\epsilon_{\xi}\in(0,1)$, which, for one thing, ensures
$\xi_{k}\leq\xi_{k}^{\rm trial}$. The last component in the $k$th iteration is
to set the stepsize, the magnitude of which is controlled by prescribed
$\\{\beta_{k}\\}\subset(0,1]$, which is employed in the following projection
interval that is used in the stepsize computation:

$\mbox{Proj}_{k}(\cdot):=\mbox{Proj}\left(\cdot\;\Bigg{|}\left[\frac{\beta_{k}\xi_{k}\tau_{k}}{\tau_{k}L+\Gamma},\frac{\beta_{k}\xi_{k}\tau_{k}}{\tau_{k}L+\Gamma}+\theta\beta_{k}^{2}\right]\right),$

where $\mbox{Proj}(\cdot\;|\;\mathcal{I})$ represents the projection operator
onto the interval $\mathcal{I}\subset\mathbb{R}$. As in other stochastic-
gradient-based methods, the convergence properties of the method depend on
properties of $\\{\beta_{k}\\}$, which in many analyses is considered to be a
constant or diminishing sequence. In our analysis, we establish our result for
the case of $\beta_{k}={\cal O}(1/\sqrt{k_{\max}+1})$ for all
$k\in[k_{\max}]$.

Overall, the algorithm that we consider is stated as Algorithm 1. The only
changes from Algorithm 3.1 in [2] are the fixed iteration limit ($k_{\max}$),
a slightly stronger decrease requirement for the definition of $\tau_{k}$ in
(13) when $\tau_{k-1}>\tau_{k}^{\rm trial}$, and the concluding step for
producing the return value ($x_{k^{*}}$). This method of sampling $k^{*}$ to
produce the return value is consistent with other approaches in the literature
on complexity analyses for algorithms for solving nonconvex optimization
problems; see, e.g., [11]. It amounts to uniform sampling over the iterates
when constant $\\{\beta_{k}\\}$ is considered, as in our analysis. Finally, we
remark that Algorithm 1 presumes knowledge of Lipschitz constants for the
objective and constraint gradients, although in practice one might only
estimate these values using standard procedures [10].

Algorithm 1 Stochastic SQP Algorithm

1:$x_{0}\in\mathbb{R}^{n}$; $k_{\max}\in\mathbb{N}$;
$\tau_{-1}\in\mathbb{R}_{>0}$; $\epsilon_{\tau}\in(0,1)$;
$\epsilon_{\xi}\in(0,1)$; $\sigma\in(0,1)$; $\xi_{-1}\in\mathbb{R}_{>0}$;
$\\{\beta_{k}\\}\subset(0,1]$; $\theta\in\mathbb{R}_{\geq 0}$;
$L\in(0,\infty)$, a Lipschitz constant for $\nabla f$;
$\Gamma\in[\sum_{i=1}^{m}\gamma_{i},\infty)$, where $\gamma_{i}\in(0,\infty)$
is a Lipschitz constant for $\nabla c_{i}$ for all $i\in[m]$

2:for all $k\in[k_{\max}]$ do

3: Compute $(d_{k},y_{k})$ as the solution of (9)

4: if $d_{k}=0$ then

5: Set $\tau_{k}^{\rm trial}\leftarrow\infty$, $\tau_{k}\leftarrow\tau_{k-1}$,
$\xi_{k}^{\rm trial}\leftarrow\infty$, and $\xi_{k}\leftarrow\xi_{k-1}$

6: Set $\widehat{\alpha}_{k,\text{init}}\leftarrow 1$,
$\widetilde{\alpha}_{k,\text{init}}\leftarrow 1$, and $\alpha_{k}\leftarrow 1$

7: else (if $d_{k}\neq 0$)

8: Set $\tau_{k}^{\rm trial}$ by (12) and $\tau_{k}$ by (13)

9: Set $\xi_{k}^{\rm trial}$ and $\xi_{k}$ by (14)

10: Set  $\widehat{\alpha}_{k,\text{init}}\leftarrow\tfrac{\beta_{k}\Delta
q(x_{k},\tau_{k},g_{k},H_{k},d_{k})}{(\tau_{k}L+\Gamma)\|d_{k}\|_{2}^{2}}\ \
\text{and}\ \
\widetilde{\alpha}_{k,\text{init}}\leftarrow\widehat{\alpha}_{k,\text{init}}-\tfrac{4\|c_{k}\|_{1}}{(\tau_{k}L+\Gamma)\|d_{k}\|_{2}^{2}}$

11: Set
$\widehat{\alpha}_{k}\leftarrow\operatorname{Proj}_{k}(\widehat{\alpha}_{k,\text{init}})$
and
$\widetilde{\alpha}_{k}\leftarrow\operatorname{Proj}_{k}(\widetilde{\alpha}_{k,\text{init}})$,
then  $\alpha_{k}\leftarrow\begin{cases}\widehat{\alpha}_{k}&\text{if
$\widehat{\alpha}_{k}<1$}\\\ 1&\text{if $\widetilde{\alpha}_{k}\leq
1\leq\widehat{\alpha}_{k}$}\\\ \widetilde{\alpha}_{k}&\text{if
$\widetilde{\alpha}_{k}>1$}\end{cases}$

12: end if

13: Set $x_{k+1}\leftarrow x_{k}+\alpha_{k}d_{k}$

14:end for

15:Sample $k^{*}\in[k_{\max}]$, where
$\mathbb{P}[k^{*}=k]=\frac{\beta_{k}}{\sum_{k=0}^{k_{\max}}\beta_{k}}$ for all
$k\in[k_{\max}]$, then return $x_{k^{*}}$

##  4 Complexity Analysis

We begin our complexity analysis by describing the algorithm as a stochastic
process (Section 4.1), then formalizing the assumptions that we make about the
stochastic gradient estimates (Section 4.2). We then state, in some cases in a
slightly modified form, some key lemmas from [2] that are needed for our
analysis (Section 4.3). Our generic complexity result, which has been outlined
in Section 2, is then stated and proved (Section 4.4). Consequences and
extensions of our generic complexity result are then discussed for some
special cases of distributions for the stochastic gradient estimates for which
our required assumptions hold with high-probability (Section 4.5). Finally, we
conclude this section by outlining a form of our generic complexity result
that relaxes one of our minor simplifying assumptions (Section 4.6).

Similarly as for the convergence analysis in [2], our complexity analysis
makes use of orthogonal decompositions of the search directions computed by
the algorithm; in particular, for all $k\in\mathbb{N}$, we express
$d_{k}=u_{k}+v_{k}$, where $u_{k}\in\mbox{Null}(J_{k})$ and
$v_{k}\in\mbox{Range}(J_{k}^{\top})$. We note here that conditioned on the
algorithm having reached $x_{k}$ at iteration $k$, the normal component
$v_{k}$ is deterministic, depending only on the constraint value $c_{k}$ and
the Jacobian $J_{k}$.

In addition to the quantities that are computed explicitly in Algorithm 1, our
analysis also refers to the quantities that would have been computed in each
iteration $k\in\mathbb{N}$, conditioned on the event that the algorithm has
reached $x_{k}$ as the $k$th iterate, if the true gradient $\nabla f(x_{k})$
is used in place of the stochastic gradient $g_{k}$. These quantities are
denoted by a “true” superscript. For example, in iteration $k$, the true
search direction and corresponding true Lagrange multiplier estimate are the
solution of the linear system

$\left[\begin{matrix}H_{k}&J_{k}^{\top}\\\
J_{k}&0\end{matrix}\right]\left[\begin{matrix}d_{k}^{\text{\rm true}}\\\
y_{k}^{\text{\rm true}}\end{matrix}\right]=-\left[\begin{matrix}\nabla
f(x_{k})\\\ c_{k}\end{matrix}\right],$ (15)

which may be decomposed as $d_{k}^{\text{\rm true}}=u_{k}^{\text{\rm
true}}+v_{k}$, where $u_{k}^{\text{\rm true}}\in\mbox{Null}(J_{k})$ and
$v_{k}\in\mbox{Range}(J_{k}^{\top})$. Here, we write $v_{k}$ (without a
superscript) since the normal component of the search direction is defined in
a manner that makes it independent of the objective gradient (estimate).
Similarly, the true value of the merit parameter that would have been computed
is denoted

$\tau_{k}^{\rm\text{trial},\text{\rm true}}\leftarrow\begin{cases}\infty\ \ \
\text{if $\nabla f(x_{k})^{\top}d_{k}^{\text{\rm
true}}+\max\\{(d_{k}^{\text{\rm true}})^{\top}H_{k}d_{k}^{\text{\rm
true}},0\\}\leq 0$}&\\\ \frac{(1-\sigma)\|c_{k}\|_{1}}{\nabla
f(x_{k})^{\top}d_{k}^{\text{\rm true}}+\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}},0\\}}\ \ \
\text{otherwise}.&\end{cases}$

This definition of $\tau_{k}^{\rm\text{trial},\text{\rm true}}$ guarantees
that, for any $\tau\leq\tau_{k}^{\rm\text{trial},\text{\rm true}}$, one finds

$\Delta q(x_{k},\tau,\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm
true}})\geq\tfrac{1}{2}\tau\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}},0\\}+\sigma\|c_{k}\|_{1}.$ (16)

###  4.1 Stochastic Process

Henceforth, for the sake of formality, we shall refer in our analysis to the
stochastic process generated by Algorithm 1. Specifically, in terms of values
that are computed by the algorithm itself, we have the stochastic process

$\\{(X_{k},G_{k},D_{k},Y_{k},{\cal T}_{k},\Xi_{k},{\cal A}_{k})\\},$

where, for all $k\in\mathbb{N}$, the random variables are: the algorithm
iterate $X_{k}$, stochastic gradient estimate $G_{k}$, search direction
$D_{k}$, Lagrange multiplier estimate $Y_{k}$, merit parameter ${\cal T}_{k}$,
ratio parameter $\Xi_{k}$, and stepsize ${\cal A}_{k}$. For all
$k\in\mathbb{N}$, a realization of the corresponding element of this process
is denoted $(x_{k},g_{k},d_{k},y_{k},\tau_{k},\xi_{k},\alpha_{k})$. Similarly,
in terms of “true” values and step decomposition values that are not computed
by the algorithm, but are defined for the sake of our analysis, we have the
simultaneously generated process

$\\{(V_{k},U_{k},D_{k}^{\text{\rm true}},U_{k}^{\text{\rm
true}},Y_{k}^{\text{\rm true}},{\cal T}_{k}^{\rm\text{trial},\text{\rm
true}})\\},$

where, for all $k\in\mathbb{N}$, the random variables are: the normal search
direction component $V_{k}$, the tangential search direction component
$U_{k}$, the true search direction $D_{k}^{\text{\rm true}}$, the true
tangential search direction component $U_{k}^{\text{\rm true}}$, the true
Lagrange multiplier estimate $Y_{k}^{\text{\rm true}}$, and the true trial
merit parameter ${\cal T}_{k}^{\rm\text{trial},\text{\rm true}}$. For all
$k\in\mathbb{N}$, a realization of the corresponding element of this process
is denoted $(v_{k},u_{k},d_{k}^{\text{\rm true}},u_{k}^{\text{\rm
true}},y_{k}^{\text{\rm true}},\tau_{k}^{\rm\text{trial},\text{\rm true}})$.
Finally, for the sake of tracking the number of merit parameter updates that
occur during runs of the algorithm, we define the stochastic process
$\\{S_{k}\\}$, where for all $k\in\mathbb{N}$ the random variable $S_{k}$
represents the number of merit parameter decreases up to the end of the $k$th
iteration, i.e., the number of iterations in which ${\cal T}_{k}<{\cal
T}_{k-1}$. For all $k\in\mathbb{N}$, a realization of $S_{k}$ is denoted
$s_{k}$.

In any run, the behavior of Algorithm 1 is dictated entirely by the initial
conditions and the sequence of stochastic gradient estimates that are
generated. Let ${\cal F}_{k}$ denote the $\sigma$-algebra generated by the
random variables $\\{G_{0},\dots,G_{k-1}\\}$, a realization of which (along
with all initial conditions of the algorithm, including $X_{0}=x_{0}$)
determines the realizations of

$\\{X_{j}\\}_{j=1}^{k}\ \text{and}\ \\{(D_{j},Y_{j},{\cal T}_{j},\Xi_{j},{\cal
A}_{j},V_{j},U_{j},D_{j}^{\rm true},U_{j}^{\rm true},Y_{j}^{\rm true},{\cal
T}_{j}^{\rm trial,true},S_{j})\\}_{j=0}^{k-1}.$

For completeness, let ${\cal F}_{0}=\sigma(x_{0})$. As a result, $\\{{\cal
F}_{k}\\}_{k\geq 0}$ is a filtration. When conditioning on a specific
realization of Algorithm 1 up to the beginning of iteration $k\in\mathbb{N}$,
we condition on $G_{[k-1]}=g_{[k-1]}$, since these stochastic gradients
determine $x_{k}$. (Recall our notation that $g_{[k-1]}$ represents
$\\{g_{0},\dots,g_{k-1}\\}$.) Similarly, later in our analysis when we
condition on ${\cal F}_{k}$, we are conditioning on all realizations of
$G_{[k-1]}$ that are measurable with respect to the filtration ${\cal F}_{k}$.

###  4.2 Assumptions

Our analysis presumes certain good behavior of the sequences of merit and
ratio parameters that are set adaptively by the algorithm. Formally, given
$(k_{\max},s_{\max},\tau_{\min},\xi_{\min})\in\mathbb{N}\times\mathbb{N}\times\mathbb{R}_{>0}\times\mathbb{R}_{>0}$,
our main result characterizes the worst-case behavior of Algorithm 1
conditioned on the event denoted as

$E:=E(k_{\max},s_{\max},\tau_{\min},\xi_{\min}),$ (17)

which we define as the event such that, in every realization of the algorithm,
the merit parameters $\\{\tau_{k}\\}_{k=0}^{k_{\max}}$ and ratio parameters
$\\{\xi_{k}\\}_{k=0}^{k_{\max}}$ satisfy

  * •

$\tau_{k}\geq\tau_{\min}>0$ for all $k\in[k_{\max}]$,

  * •

$\tau_{k}^{\rm\text{trial},\text{\rm true}}\geq\tau_{\min}>0$ for all
$k\in[k_{\max}]$,

  * •

$\xi_{k}=\xi_{\min}>0$ for all $k\in[k_{\max}]$, and

  * •

$|\\{k\in[k_{\max}]:\tau_{k}<\tau_{k-1}\\}|\leq s_{\max}$.

Consideration of this event as a focus for proving a worst-case complexity
result for Algorithm 1 is justifiable for the following reasons.

  * •

The condition in $E$ that the ratio parameter sequence is constant over all
iterations is not actually essential for our analysis; rather, it is made for
the sake of simplicity. Indeed, in Section 4.6, we present an extension of our
main result to the setting in which this parameter sequence is not constant.
Observe that, as proved in [2, Lemma 3.5], the sequence $\\{\Xi_{k}\\}$ is
bounded below by a positive real number whose value is deterministic, i.e., it
is independent of the sequence of stochastic gradient estimates that are
generated by the algorithm. Hence, for the sake of simplicity, we assume for
now that $\\{\Xi_{k}\\}$ is constant and leave the statement of the more
complicated version of our main result to a subsection at the end of our
analysis.

  * •

The conditions in $E$ pertaining to the behavior of the merit parameter
sequence are not necessarily minor. That said, attention to this behavior of
the algorithm is justified by arguments made in [1, 2], which under the same
kinds of assumptions made in this paper argue that, in any run of the
algorithm, the probability is zero that the merit parameter vanishes.
Furthermore, in Section 4.5, we consider a particular setting in which the
distributions of the stochastic gradient estimates are sub-Gaussian over any
run of the algorithm, in which case we show that the merit parameter remains
bounded below with high probability, meaning that our main worst-case
complexity bound—which holds with high probability due to the adaptivity of
the merit parameter sequence—remains essentially unchanged in this setting
when we do not presume upfront that the merit parameter sequence remains
bounded above a positive real number.

  * •

The condition in $E$ pertaining to the existence of $s_{\max}$ is not actually
an additional requirement beyond the existence of $\tau_{\min}$ in the event.
After all, by the construction of Algorithm 1, it follows that when the merit
parameter is decreased, it is decreased by at least a constant factor, from
which it follows (under the existence of $\tau_{\min}$) that $s_{\max}$ exists
and satisfies

$s_{\max}\leq\min\left\\{k_{\max}+1,\left\lceil\frac{\log(\tau_{\min}/\tau_{-1})}{\log(1-\epsilon_{\tau})}\right\rceil\right\\}.$
(18)

That said, for simplicity and generality in our analysis, we define $s_{\max}$
as a quantity that is decoupled from the above (conservative) inequality.

Conditioned on $E$, we assume the following about the stochastic gradient
estimates. Such an assumption, namely, that conditioned on the event that a
given iterate has been reached the stochastic gradient is unbiased and has
bounded variance, is common in analyses of stochastic optimization methods.
Here and throughout the remainder of the paper, we let $\mathbb{P}_{k}[\cdot]$
(respectively, $\mathbb{E}_{k}[\cdot]$) denote probabilty (respectively,
expectation) conditioned on event $E$ and that $G_{[k-1]}=g_{[k-1]}$ for a
given $g_{[k-1]}$, i.e., we define

$\mathbb{P}_{k}[\cdot]:=\mathbb{P}[\cdot|E,G_{[k-1]}=g_{[k-1]}]\ \ \text{and}\
\ \mathbb{E}_{k}[\cdot]:=\mathbb{E}[\cdot|E,G_{[k-1]}=g_{[k-1]}].$

######  Assumption 3.

There exists $M\in\mathbb{R}_{>0}$ such that, for all $k\in[k_{\max}]$ and any
realization $g_{[k-1]}$ of $G_{[k-1]}$, one finds that

$\mathbb{E}_{k}[G_{k}]=\nabla f(x_{k})\ \ \text{and}\ \
\mathbb{E}_{k}[\|G_{k}-\nabla f(x_{k})\|_{2}^{2}]\leq M.$ (19)

In addition, there exists $M_{\tau}\in\mathbb{R}_{>0}$ such that, for all
$k\in[k_{\max}]$ and any realization $g_{[k-1]}$ of $G_{[k-1]}$, one finds
that

$\displaystyle\text{either}\ \ \mathbb{P}_{k}[\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})<0,{\cal T}_{k}<\tau_{k-1}]$
$\displaystyle=0$ (20) $\displaystyle\text{or}\ \
\mathbb{E}_{k}[\|G_{k}-\nabla f(x_{k})\|_{2}|\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})<0,{\cal T}_{k}<\tau_{k-1}]$
$\displaystyle\leq M_{\tau}.$

Observe that the inequality in (19) can imply (20), such as when there exists
$p\in(0,1]$ such that, for all $k\in[k_{\max}]$ and $g_{[k-1]}$, one finds
that

$\mathbb{P}_{k}[\nabla f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})<0,{\cal
T}_{k}<\tau_{k-1}]\geq p$

whenever this probability is nonzero. This occurs, for example, when the
objective of (1) is a finite sum of $N$ terms and each stochastic gradient
estimate is computed as a so-called mini-batch estimate through the uniform
(random) selection of $b$ indices, in which case the above holds with $p=b/N$.

We make one additional assumption for our analysis, namely, the following.

######  Assumption 4.

There exists $p_{\tau}\in(0,1]$ such that, for all $k\in[k_{\max}]$ and any
realization $g_{[k-1]}$ of $G_{[k-1]}$, one finds that

$\mathbb{P}_{k}[G_{k}^{\top}D_{k}+\max\\{D_{k}^{\top}H_{k}D_{k},0\\}\geq\nabla
f(x_{k})^{\top}d_{k}^{\text{\rm true}}+\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}},0\\}]\geq p_{\tau}.$

Similar to [2, Proposition 3.16], Assumption 4 allows us to prove that, with
high probability, the number of iterations in which
$\tau_{k}>\tau_{k}^{\rm\text{trial},\text{\rm true}}$ is not too large. In [2,
Example 3.17], it was shown that the inequality in this assumption holds with
$p_{\tau}=\frac{1}{2}$ when, conditioned on having reached $x_{k}$, the
stochastic gradient $G_{k}$ has a Gaussian distribution. We show in Section
4.5 that this result can be extended to other settings as well.

###  4.3 Properties of Algorithm 1

In this section, we state key results from [2] that are needed for our
analysis.

By [2, Lemma 2.10], there exists $\kappa_{uv}\in\mathbb{R}_{>0}$ such that,
for all $k\in[k_{\max}]$, if $\|u_{k}^{\text{\rm
true}}\|^{2}\geq\kappa_{uv}\|v_{k}\|^{2}$, then $\frac{1}{2}(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm
true}}\geq\frac{1}{4}\zeta\|u_{k}^{\text{\rm true}}\|^{2}$, where $\zeta$ is
defined in Assumption 2. Correspondingly, let us define

$\Psi_{k}:=\begin{cases}\|u_{k}^{\text{\rm true}}\|^{2}+\|c_{k}\|&\mbox{if
}\|u_{k}^{\text{\rm true}}\|^{2}\geq\kappa_{uv}\|v_{k}\|^{2}\\\
\|c_{k}\|&\mbox{otherwise.}\end{cases}$

The following lemma is stated using a different norm (for $c_{k}$) than in [2,
Lemma 2.11]. The result holds in the same manner due to the norm-equivalence
between $\|\cdot\|$ and $\|\cdot\|_{1}$ in $\mathbb{R}^{m}$. We state the
result in this manner for consistency in the measure of constraint violation
stated in our final complexity bound.

######  Lemma 1 ([2, Lemma 2.11]).

Let Assumptions 1 and 2 hold. Then, there exists
$\kappa_{\Psi}\in\mathbb{R}_{>0}$ such that, for all $k\in[k_{\max}]$, the
true search direction and constraint violation satisfy $\|d_{k}^{\text{\rm
true}}\|^{2}+\|c_{k}\|_{1}\leq(\kappa_{\Psi}+1)\Psi_{k}$.

######  Lemma 2 ([2, Lemma 2.12]).

Let Assumptions 1 and 2 hold. Then, there exists
$\kappa_{q}\in\mathbb{R}_{>0}$ such that, for all $k\in[k_{\max}]$ and any
$\tau\leq\tau_{k}^{\rm\text{trial},\text{\rm true}}$, the true reduction in
the merit model satisfies $\Delta q(x_{k},\tau,\nabla
f(x_{k}),H_{k},d_{k}^{\text{\rm true}})\geq\kappa_{q}\tau\Psi_{k}$.

######  Lemma 3 ([2, Lemma 3.7]).

Let Assumptions 1 and 2 hold and suppose that the sequence $\\{\beta_{k}\\}$
is chosen such that $\beta_{k}\xi_{k}\tau_{k}/(\tau_{k}L+\Gamma)\in(0,1]$ for
all $k\in[k_{\max}]$. Then, for all $k\in[k_{\max}]$, it follows that

$\displaystyle\phi(x_{k}+\alpha_{k}d_{k},\tau_{k})-\phi(x_{k},\tau_{k})$
$\displaystyle\leq-\alpha_{k}\Delta q(x_{k},\tau_{k},\nabla
f(x_{k}),H_{k},d_{k}^{\text{\rm true}})$ (21)
$\displaystyle\quad+\tfrac{1}{2}\alpha_{k}\beta_{k}\Delta
q(x_{k},\tau_{k},g_{k},H_{k},d_{k})$
$\displaystyle\quad+\alpha_{k}\tau_{k}\nabla
f(x_{k})^{\top}(d_{k}-d_{k}^{\text{\rm true}}).$

######  Lemma 4.

Let Assumptions 1, 2, and 3 hold. Then, for all $k\in[k_{\max}]$, it follows
that $\mathbb{E}_{k}[D_{k}]=d_{k}^{\text{\rm true}}$,
$\mathbb{E}_{k}[U_{k}]=u_{k}^{\text{\rm true}}$, and
$\mathbb{E}_{k}[Y_{k}]=y_{k}^{\text{\rm true}}$. Moreover, there exists
$\kappa_{d}\in\mathbb{R}_{>0}$ such that, for all $k\in[k_{\max}]$, one finds
that

$\displaystyle\|d_{k}^{\text{\rm true}}\|\leq\kappa_{d}\|\nabla f(x_{k})\|$
$\displaystyle\leq\kappa_{d}\kappa_{g},$
$\displaystyle\mathbb{E}_{k}[\|D_{k}-d_{k}^{\text{\rm
true}}\|]\leq\kappa_{d}\mathbb{E}_{k}[\|G_{k}-\nabla f(x_{k})\|]$
$\displaystyle\leq\kappa_{d}\sqrt{M},\ \ \text{and}$
$\displaystyle\mathbb{E}_{k}[\|D_{k}-d_{k}^{\text{\rm true}}\||\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})<0,{\cal T}_{k}<\tau_{k-1}]$
$\displaystyle\leq\kappa_{d}M_{\tau}.$

###### Proof.

Except for the final inequality, the result follows directly from [2, Lemma
3.8] (or the proof therein) and (2). As for the final inequality, observe by
the arguments in [2, Lemma 3.8] that for any realization of $G_{k}$ and
$D_{k}$ one finds $\|d_{k}-d_{k}^{\text{\rm
true}}\|\leq\kappa_{d}\|g_{k}-\nabla f(x_{k})\|$, which combined with (20)
gives

$\displaystyle\ \mathbb{E}_{k}[\|D_{k}-d_{k}^{\text{\rm true}}\||\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})<0,{\cal T}_{k}<\tau_{k-1}]$
$\displaystyle\leq$ $\displaystyle\ \kappa_{d}\mathbb{E}_{k}[\|G_{k}-\nabla
f(x_{k})\||\nabla f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})<0,{\cal
T}_{k}<\tau_{k-1}]\leq\kappa_{d}M_{\tau},$

as desired. ∎∎

######  Lemma 5 ([2, Lemma 3.9]).

Let Assumptions 1, 2, and 3 hold. Then, for all $k\in[k_{\max}]$, it follows
that

$\displaystyle\nabla f(x_{k})^{\top}d_{k}^{\text{\rm
true}}\geq\mathbb{E}_{k}[G_{k}^{\top}D_{k}]$ $\displaystyle\geq\nabla
f(x_{k})^{\top}d_{k}^{\text{\rm true}}-\zeta^{-1}M$ $\displaystyle\text{and}\
\ \mathbb{E}_{k}[D_{k}^{\top}H_{k}D_{k}]$ $\displaystyle\geq(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}}.$

###  4.4 Complexity Result

In this section, we present our main complexity results. We derive our results
in largely the same manner as the global convergence result in [2], but with
two major changes that stem from the need to characterize the behavior of the
algorithm in the context of an adaptive merit parameter sequence. At a high
level, the two modifications are as follows:

  1. 1.

We derive, in Lemma 6, an upper bound for the last term in (21), the
derivation of which is complicated by the fact that, conditioned on $x_{k}$
being the $k$th iterate in a run of the algorithm, this term is the product of
three correlated random variables: ${\cal A}_{k}$, ${\cal T}_{k}$, and $\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})$. A critical aspect of our
derived bound is that we isolate a term for the event when $\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})<0$ and ${\cal
T}_{k}<\tau_{k-1}$, since this happens to be an event that complicates
subsequent aspects of our analysis. In Lemma 9, we prove a high-probability
bound on the sum of the probabilities of the occurrences of this event over
the entire run of the algorithm.

  2. 2.

A critical aspect of the analysis in [2] for the deterministic setting is that
one can always tie the reduction in the model of the merit function to a
first-order stationarity error measure (with respect to the constrained
optimization problem) due to the fact that
$\tau_{k}^{\rm\text{trial},\text{\rm true}}\geq\tau_{k}$ for all
$k\in\mathbb{N}$. Unfortunately, however, this inequality is not guaranteed to
hold in the stochastic setting, which is problematic for our purposes in this
paper. To account for this issue, we define an auxiliary sequence
$\\{\hat{\cal T}_{k}\\}$ (not generated by the algorithm) such that
$\hat{{\cal T}}_{k}:=\min\\{{\cal T}_{k},{\cal
T}_{k}^{\rm\text{trial},\text{\rm true}}\\}$ for all $k\in[k_{\max}]$. In
Lemmas 7 and 8, we analyze behaviors of the algorithm with respect to this
auxiliary sequence, and in Lemma 10 we provide a high-probability bound on the
total number of iterations in which ${\cal T}_{k}^{\rm\text{trial},\text{\rm
true}}<{\cal T}_{k}$ may occur. (More precisely, Lemma 10 considers a superset
of the iterations in which this bound may occur, which serves our purposes
just as well.)

The first few results in this section consider properties of algorithmic
quantities conditioned on the algorithm having generated a certain sequence of
stochastic gradient estimates through a given iteration. In particular, given
$k\in[k_{\max}]$ and $g_{[k-1]}$, values generated by the algorithm have been
determined up to the beginning of iteration $k$, including $x_{k}$,
$d_{k}^{\text{\rm true}}$, and $\tau_{k-1}$. Given these quantities, let us
define three events:

  * •

$E_{k,1}$, the event that $\nabla f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm
true}})\geq 0$;

  * •

$E_{k,2}$, the event that $\nabla f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm
true}})<0$ and ${\cal T}_{k}=\tau_{k-1}$; and

  * •

$E_{k,3}$, the event that $\nabla f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm
true}})<0$ and ${\cal T}_{k}<\tau_{k-1}$.

We now derive an upper bound on the final term in (21). In the following
lemma, we make use, for given $k\in[k_{\max}]$ and $g_{[k-1]}$, of the
stepsize values

$\displaystyle\alpha_{\min,k}^{<}:=\frac{\beta_{k}\xi_{\min}\tau_{\min}}{\tau_{\min}L+\Gamma},\
\ \alpha_{\min,k}^{=}$
$\displaystyle:=\frac{\beta_{k}\xi_{\min}\tau_{k-1}}{\tau_{k-1}L+\Gamma},$
(22) $\displaystyle\text{and}\ \ \varsigma_{\max,k}$
$\displaystyle:=\alpha_{\min,k}^{=}+\theta\beta_{k}^{2}.$

The first value here represents a lower bound on the smallest stepsize that
may be computed in the event that ${\cal T}_{k}<\tau_{k-1}$, while the second
value is the smallest stepsize that may be computed in the event that ${\cal
T}_{k}=\tau_{k-1}$; it is easily verified that
$\alpha_{\min,k}^{<}<\alpha_{\min,k}^{=}$. Hence, $\varsigma_{\max,k}$
represents an upper bound on the largest stepsize that may be computed.

######  Lemma 6.

Suppose that Assumptions 1, 2, and 3 hold, and let
$\kappa_{d}\in\mathbb{R}_{>0}$ be defined by Lemma 4. Then, for all
$k\in[k_{\max}]$ and $g_{[k-1]}$, and with the stepsizes
$(\alpha_{\min,k}^{<},\alpha_{\min,k}^{=},\varsigma_{\max,k})$ defined as in
(22), one finds that

$\displaystyle\ \mathbb{E}_{k}[{\cal A}_{k}{\cal T}_{k}\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})]$ $\displaystyle\leq$
$\displaystyle\
(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\kappa_{g}\kappa_{d}M_{\tau}\mathbb{P}_{k}[E_{k,3}]+\theta\beta_{k}^{2}\tau_{k-1}\kappa_{g}\kappa_{d}\sqrt{M}.$

###### Proof.

Consider arbitrary $k\in[k_{\max}]$ and $g_{[k-1]}$, and for ease of
exposition, let us denote $\mathbb{E}_{k,j}=\mathbb{E}_{k}[\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})|E_{k,j}]$ for all
$j\in\\{1,2,3\\}$. By the Law of Total Expectation, the fact that
$0<\tau_{\min}\leq{\cal T}_{k}\leq\tau_{k-1}$ under $E$, and the definitions
of $\alpha_{\min,k}^{<}$, $\alpha_{\min,k}^{=}$, and $\varsigma_{\max,k}$, one
finds that

$\displaystyle\ \mathbb{E}_{k}[{\cal A}_{k}{\cal T}_{k}\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})]$ $\displaystyle=$
$\displaystyle\ \mathbb{E}_{k}[{\cal A}_{k}{\cal T}_{k}\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm
true}})|E_{k,1}]\mathbb{P}_{k}[E_{k,1}]$ $\displaystyle\ +\mathbb{E}_{k}[{\cal
A}_{k}{\cal T}_{k}\nabla f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm
true}})|E_{k,2}]\mathbb{P}_{k}[E_{k,2}]$ $\displaystyle\ +\mathbb{E}_{k}[{\cal
A}_{k}{\cal T}_{k}\nabla f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm
true}})|E_{k,3}]\mathbb{P}_{k}[E_{k,3}]$ $\displaystyle\leq$ $\displaystyle\
\varsigma_{\max,k}\tau_{k-1}\mathbb{E}_{k,1}\mathbb{P}_{k}[E_{k,1}]+\alpha_{\min,k}^{=}\tau_{k-1}\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}]+\alpha_{\min,k}^{<}\tau_{\min}\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}].$

Using this inequality, the Law of Total Expectation, and Lemma 4
($\mathbb{E}_{k}[D_{k}]=d_{k}^{\text{\rm true}}$), one obtains three upper
bounds by adding and subtracting like terms:

$\displaystyle\mathbb{E}_{k}[{\cal A}_{k}{\cal T}_{k}\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})]$ $\displaystyle\leq$
$\displaystyle\
\varsigma_{\max,k}\tau_{k-1}\mathbb{E}_{k,1}\mathbb{P}_{k}[E_{k,1}]+\varsigma_{\max,k}\tau_{k-1}\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}]-\theta\beta_{k}^{2}\tau_{k-1}\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}]$
$\displaystyle\
+\varsigma_{\max,k}\tau_{k-1}\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}]+(\alpha_{\min,k}^{<}\tau_{\min}-\varsigma_{\max,k}\tau_{k-1})\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}]$
$\displaystyle=$ $\displaystyle\
-\theta\beta_{k}^{2}\tau_{k-1}\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}]+(\alpha_{\min,k}^{<}\tau_{\min}-\varsigma_{\max,k}\tau_{k-1})\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}]$
and $\displaystyle\mathbb{E}_{k}[{\cal A}_{k}{\cal T}_{k}\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})]$ $\displaystyle\leq$
$\displaystyle\
\alpha_{\min,k}^{=}\tau_{k-1}\mathbb{E}_{k,1}\mathbb{P}_{k}[E_{k,1}]+\theta\beta_{k}^{2}\tau_{k-1}\mathbb{E}_{k,1}\mathbb{P}_{k}[E_{k,1}]+\alpha_{\min,k}^{=}\tau_{k-1}\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}]$
$\displaystyle\
+\alpha_{\min,k}^{=}\tau_{k-1}\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}]+(\alpha_{\min,k}^{<}\tau_{\min}-\alpha_{\min,k}^{=}\tau_{k-1})\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}]$
$\displaystyle=$ $\displaystyle\
\theta\beta_{k}^{2}\tau_{k-1}\mathbb{E}_{k,1}\mathbb{P}_{k}[E_{k,1}]+(\alpha_{\min,k}^{<}\tau_{\min}-\alpha_{\min,k}^{=}\tau_{k-1})\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}]$
and $\displaystyle\mathbb{E}_{k}[{\cal A}_{k}{\cal T}_{k}\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})]$ $\displaystyle\leq$
$\displaystyle\
\alpha_{\min,k}^{<}\tau_{\min}\mathbb{E}_{k,1}\mathbb{P}_{k}[E_{k,1}]+(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\mathbb{E}_{k,1}\mathbb{P}_{k}[E_{k,1}]$
$\displaystyle\
+\alpha_{\min,k}^{<}\tau_{\min}\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}]+(\alpha_{\min,k}^{=}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}]$
$\displaystyle\
+\alpha_{\min,k}^{<}\tau_{\min}\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}]$
$\displaystyle=$ $\displaystyle\
(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\mathbb{E}_{k,1}\mathbb{P}_{k}[E_{k,1}]+(\alpha_{\min,k}^{=}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}].$

Averaging these three upper bounds and the definition of $\varsigma_{\max,k}$,
one obtains

$\displaystyle\mathbb{E}_{k}[{\cal A}_{k}{\cal T}_{k}\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})]$ $\displaystyle\leq$
$\displaystyle\
\tfrac{1}{3}((\alpha_{\min,k}^{=}+2\theta\beta_{k}^{2})\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\mathbb{E}_{k,1}\mathbb{P}_{k}[E_{k,1}]$
$\displaystyle\
+\tfrac{1}{3}((\alpha_{\min,k}^{=}-\theta\beta_{k}^{2})\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}]$
$\displaystyle\
+\tfrac{1}{3}(2\alpha_{\min,k}^{<}\tau_{\min}-(2\alpha_{\min,k}^{=}+\theta\beta_{k}^{2})\tau_{k-1})\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}]$
$\displaystyle=$ $\displaystyle\
\tfrac{1}{3}((\alpha_{\min,k}^{=}+2\theta\beta_{k}^{2})\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})(\mathbb{E}_{k,1}\mathbb{P}_{k}[E_{k,1}]+\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}])$
$\displaystyle\
-\theta\beta_{k}^{2}\tau_{k-1}\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}]$
$\displaystyle\
-\tfrac{1}{3}((2\alpha_{\min,k}^{=}+\theta\beta_{k}^{2})\tau_{k-1}-2\alpha_{\min,k}^{<}\tau_{\min})\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}].$
(23)

This bound can be rewritten as follows. By the Law of Total expectation,

$\displaystyle\
\mathbb{E}_{k,1}\mathbb{P}_{k}[E_{k,1}]+\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}]$
$\displaystyle=$ $\displaystyle\ \mathbb{E}_{k}[\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm
true}})]-\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}]=-\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}],$
(24)

and along with Lemma 4 and (2) one finds

$\displaystyle-\mathbb{E}_{k,2}\mathbb{P}_{k}[E_{k,2}]$
$\displaystyle=-\mathbb{E}_{k}[\nabla f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm
true}})|E_{k,2}]\mathbb{P}_{k}[E_{k,2}]$
$\displaystyle\leq\mathbb{E}_{k}[\|\nabla f(x_{k})\|\|D_{k}-d_{k}^{\text{\rm
true}}\||E_{k,2}]\mathbb{P}_{k}[E_{k,2}]$
$\displaystyle=\mathbb{E}_{k}[\|\nabla f(x_{k})\|\|D_{k}-d_{k}^{\text{\rm
true}}\|]$ $\displaystyle\quad-\mathbb{E}_{k}[\|\nabla
f(x_{k})\|\|D_{k}-d_{k}^{\text{\rm true}}\||E_{k,1}]\mathbb{P}_{k}[E_{k,1}]$
$\displaystyle\quad-\mathbb{E}_{k}[\|\nabla f(x_{k})\|\|D_{k}-d_{k}^{\text{\rm
true}}\||E_{k,3}]\mathbb{P}_{k}[E_{k,3}]$
$\displaystyle\leq\mathbb{E}_{k}[\|\nabla f(x_{k})\|\|D_{k}-d_{k}^{\text{\rm
true}}\|]$ $\displaystyle\leq\kappa_{g}\mathbb{E}_{k}[\|D_{k}-d_{k}^{\text{\rm
true}}\|]\leq\kappa_{g}\kappa_{d}\sqrt{M}.$ (25)

In addition, Lemma 4 and (2) also yield that

$\displaystyle-\mathbb{E}_{k,3}\mathbb{P}_{k}[E_{k,3}]$
$\displaystyle=-\mathbb{E}_{k}[\nabla f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm
true}})|E_{k,3}]\mathbb{P}_{k}[E_{k,3}]$
$\displaystyle\leq\mathbb{E}_{k}[\|\nabla f(x_{k})\|\|D_{k}-d_{k}^{\text{\rm
true}}\||E_{k,3}]\mathbb{P}_{k}[E_{k,3}]$
$\displaystyle\leq\kappa_{g}\kappa_{d}M_{\tau}\mathbb{P}_{k}[E_{k,3}].$ (26)

Combining (23), (24), (25), and (26), the desired result follows. ∎∎

Now, conditioned on given $k\in[k_{\max}]$ and $g_{[k-1]}$, let us define

$\hat{{\cal T}}_{k}:=\min\\{{\cal T}_{k},\tau_{k}^{\rm\text{trial},\text{\rm
true}}\\}.$ (27)

######  Lemma 7.

Suppose that Assumptions 1, 2, and 3 hold and let
$\kappa_{d}\in\mathbb{R}_{>0}$ be defined by Lemma 4. Then, for all
$k\in[k_{\max}]$ and $g_{[k-1]}$, one finds that

$\displaystyle\ \mathbb{E}_{k}[\Delta q(x_{k},\hat{{\cal
T}}_{k},G_{k},H_{k},D_{k})]$ $\displaystyle\leq$ $\displaystyle\
\mathbb{E}_{k}[\Delta q(x_{k},\hat{{\cal T}}_{k},\nabla
f(x_{k}),H_{k},d_{k}^{\text{\rm
true}})]+\tfrac{1}{2}(\tau_{k-1}+\tau_{\min})\zeta^{-1}M$ $\displaystyle\
+(\tau_{k-1}-\tau_{\min})(\kappa_{d}\sqrt{M}(2\kappa_{g}+\sqrt{M})+\kappa_{H}\kappa_{d}^{2}(M+\tfrac{3}{2}\kappa_{g}^{2})).$

###### Proof.

By the definition of $\Delta q$ in (10), one has that

$\displaystyle\ \mathbb{E}_{k}[\Delta q(x_{k},\hat{{\cal
T}}_{k},G_{k},H_{k},D_{k})]$ $\displaystyle=$ $\displaystyle\
\mathbb{E}_{k}[-\hat{{\cal
T}}_{k}(G_{k}^{\top}D_{k}+\tfrac{1}{2}\max\\{D_{k}^{\top}H_{k}D_{k},0\\})+\|c_{k}\|_{1}]$
$\displaystyle=$ $\displaystyle\ \mathbb{E}_{k}[-\hat{{\cal
T}}_{k}(G_{k}^{\top}D_{k}-\nabla f(x_{k})^{\top}d_{k}^{\text{\rm
true}}+\tfrac{1}{2}\max\\{D_{k}^{\top}H_{k}D_{k},0\\}$
$\displaystyle\qquad-\tfrac{1}{2}\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}},0\\})]$ $\displaystyle\
+\mathbb{E}_{k}[-\hat{{\cal T}}_{k}(\nabla f(x_{k})^{\top}d_{k}^{\text{\rm
true}}+\tfrac{1}{2}\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}},0\\})+\|c_{k}\|_{1}]$
$\displaystyle=$ $\displaystyle\ \mathbb{E}_{k}[\hat{{\cal T}}_{k}(\nabla
f(x_{k})^{\top}d_{k}^{\text{\rm
true}}-G_{k}^{\top}D_{k}+\tfrac{1}{2}\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}},0\\}$ $\displaystyle\
-\tfrac{1}{2}\max\\{D_{k}^{\top}H_{k}D_{k},0\\})]+\mathbb{E}_{k}[\Delta
q(x_{k},\hat{{\cal T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})].$
(28)

Now, for simplicity of notation, define

$\displaystyle Q_{k}:=$ $\displaystyle\ \nabla f(x_{k})^{\top}d_{k}^{\text{\rm
true}}-G_{k}^{\top}D_{k}$ $\displaystyle\
+\tfrac{1}{2}\max\\{(d_{k}^{\text{\rm true}})^{\top}H_{k}d_{k}^{\text{\rm
true}},0\\}-\tfrac{1}{2}\max\\{D_{k}^{\top}H_{k}D_{k},0\\}.$

Let $E_{Q}$ denote the event that $Q_{k}\geq 0$ occurs and let $E_{Q}^{c}$
denote the event that $Q_{k}<0$ occurs. By the Law of Total Expectation, one
has that

$\displaystyle\mathbb{E}_{k}[\hat{{\cal T}}_{k}Q_{k}]$
$\displaystyle=\mathbb{E}_{k}[\hat{{\cal
T}}_{k}Q_{k}|E_{Q}]\mathbb{P}_{k}[E_{Q}]+\mathbb{E}_{k}[\hat{{\cal
T}}_{k}Q_{k}|E_{Q}^{c}]\mathbb{P}_{k}[E_{Q}^{c}]$
$\displaystyle\leq\tau_{k-1}\mathbb{E}_{k}[Q_{k}|E_{Q}]\mathbb{P}_{k}[E_{Q}]+\tau_{\min}\mathbb{E}_{k}[Q_{k}|E_{Q}^{c}]\mathbb{P}_{k}[E_{Q}^{c}].$

Therefore, by the Law of Total Probability, Lemma 5, Jensen’s inequality, and
convexity of $\max\\{\cdot,0\\}$, it follows that

$\displaystyle\mathbb{E}_{k}[\hat{{\cal T}}_{k}Q_{k}]\leq$ $\displaystyle\
\tau_{k-1}\mathbb{E}_{k}[Q_{k}|E_{Q}]\mathbb{P}_{k}[E_{Q}]+\tau_{k-1}\mathbb{E}_{k}[Q_{k}|E_{Q}^{c}]\mathbb{P}_{k}[E_{Q}^{c}]$
$\displaystyle\
+(\tau_{\min}-\tau_{k-1})\mathbb{E}_{k}[Q_{k}|E_{Q}^{c}]\mathbb{P}_{k}[E_{Q}^{c}]$
$\displaystyle=$ $\displaystyle\
\tau_{k-1}\mathbb{E}_{k}[Q_{k}]+(\tau_{\min}-\tau_{k-1})\mathbb{E}_{k}[Q_{k}|E_{Q}^{c}]\mathbb{P}_{k}[E_{Q}^{c}]$
$\displaystyle=$ $\displaystyle\ \tau_{k-1}(\nabla
f(x_{k})^{\top}d_{k}^{\text{\rm true}}-\mathbb{E}_{k}[G_{k}^{\top}D_{k}]$
$\displaystyle\ +\tfrac{1}{2}\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm
true}},0\\}-\tfrac{1}{2}\mathbb{E}_{k}[\max\\{D_{k}^{\top}H_{k}D_{k},0\\}])$
$\displaystyle\
+(\tau_{\min}-\tau_{k-1})\mathbb{E}_{k}[Q_{k}|E_{Q}^{c}]\mathbb{P}_{k}[E_{Q}^{c}]$
$\displaystyle\leq$ $\displaystyle\
\tau_{k-1}\zeta^{-1}M+(\tau_{\min}-\tau_{k-1})\mathbb{E}_{k}[Q_{k}|E_{Q}^{c}]\mathbb{P}_{k}[E_{Q}^{c}],$

and by similar reasoning one finds that

$\displaystyle\mathbb{E}_{k}[\hat{{\cal T}}_{k}Q_{k}]\leq$ $\displaystyle\
\tau_{\min}\mathbb{E}_{k}[Q_{k}|E_{Q}]\mathbb{P}_{k}[E_{Q}]+\tau_{\min}\mathbb{E}_{k}[Q_{k}|E_{Q}^{c}]\mathbb{P}_{k}[E_{Q}^{c}]$
$\displaystyle\
+(\tau_{k-1}-\tau_{\min})\mathbb{E}_{k}[Q_{k}|E_{Q}]\mathbb{P}_{k}[E_{Q}]$
$\displaystyle=$ $\displaystyle\
\tau_{\min}\mathbb{E}_{k}[Q_{k}]+(\tau_{k-1}-\tau_{\min})\mathbb{E}_{k}[Q_{k}|E_{Q}]\mathbb{P}_{k}[E_{Q}]$
$\displaystyle\leq$ $\displaystyle\
\tau_{\min}\zeta^{-1}M+(\tau_{k-1}-\tau_{\min})\mathbb{E}_{k}[Q_{k}|E_{Q}]\mathbb{P}_{k}[E_{Q}].$

Averaging these two upper bounds, one finds that

$\displaystyle\mathbb{E}_{k}[\hat{{\cal T}}_{k}Q_{k}]\leq$ $\displaystyle\
\tfrac{1}{2}(\tau_{k-1}+\tau_{\min})\zeta^{-1}M+\tfrac{1}{2}(\tau_{k-1}-\tau_{\min})\mathbb{E}_{k}[Q_{k}|E_{Q}]\mathbb{P}_{k}[E_{Q}]$
$\displaystyle\
+\tfrac{1}{2}(\tau_{\min}-\tau_{k-1})\mathbb{E}_{k}[Q_{k}|E_{Q}^{c}]\mathbb{P}_{k}[E_{Q}^{c}].$
(29)

Our goal now is to bound the latter two terms in (29). Toward this end,
observe that by the triangle and Cauchy-Schwarz inequalities, the proof of
Lemma 4, Assumption 3, Jensen’s inequality, and concavity of the square root
over $\mathbb{R}_{\geq 0}$, one finds that

$\displaystyle\ \mathbb{E}_{k}[|\nabla f(x_{k})^{\top}d_{k}^{\text{\rm
true}}-G_{k}^{\top}D_{k}|]$ $\displaystyle\leq$ $\displaystyle\
\mathbb{E}_{k}[|\nabla f(x_{k})^{\top}d_{k}^{\text{\rm
true}}-G_{k}^{\top}d_{k}^{\text{\rm
true}}|]+\mathbb{E}_{k}[|G_{k}^{\top}d_{k}^{\text{\rm
true}}-G_{k}^{\top}D_{k}|]$ $\displaystyle\leq$ $\displaystyle\
\|d_{k}^{\text{\rm true}}\|\mathbb{E}_{k}[\|\nabla
f(x_{k})-G_{k}\|]+\mathbb{E}_{k}[\|G_{k}\|\|d_{k}^{\text{\rm true}}-D_{k}\|]$
$\displaystyle\leq$ $\displaystyle\
\kappa_{d}\kappa_{g}\sqrt{\mathbb{E}_{k}[\|\nabla
f(x_{k})-G_{k}\|^{2}]}+\kappa_{d}\mathbb{E}_{k}[\|G_{k}\|\|\nabla
f(x_{k})-G_{k}\|]$ $\displaystyle\leq$ $\displaystyle\
\kappa_{d}\kappa_{g}\sqrt{\mathbb{E}_{k}[\|\nabla f(x_{k})-G_{k}\|^{2}]}$
$\displaystyle\ +\kappa_{d}\mathbb{E}_{k}[(\|G_{k}-\nabla f(x_{k})\|+\|\nabla
f(x_{k})\|)\|\nabla f(x_{k})-G_{k}\|]$ $\displaystyle\leq$ $\displaystyle\
\kappa_{d}\kappa_{g}\sqrt{M}+\kappa_{d}(M+\kappa_{g}\sqrt{M})=\kappa_{d}\sqrt{M}(2\kappa_{g}+\sqrt{M}).$
(30)

In addition, by the Cauchy-Schwarz inequality, the proof of Lemma 4, and
Assumption 3, and the fact that $\|a\|^{2}\leq 2(\|a-b\|^{2}+\|b\|^{2})$ for
any $(a,b)\in\mathbb{R}^{n}\times\mathbb{R}^{n}$, one finds

$\displaystyle\ \mathbb{E}_{k}[|\tfrac{1}{2}\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm
true}},0\\}-\tfrac{1}{2}\max\\{D_{k}^{\top}H_{k}D_{k},0\\}|]$
$\displaystyle\leq$ $\displaystyle\ |\tfrac{1}{2}\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm
true}},0\\}|+\mathbb{E}_{k}[|\tfrac{1}{2}\max\\{D_{k}^{\top}H_{k}D_{k},0\\}|]$
$\displaystyle\leq$ $\displaystyle\ \tfrac{1}{2}\|H_{k}\|\|d_{k}^{\text{\rm
true}}\|^{2}+\tfrac{1}{2}\|H_{k}\|\mathbb{E}_{k}[\|D_{k}\|^{2}]$
$\displaystyle\leq$ $\displaystyle\ \tfrac{1}{2}\|H_{k}\|\|d_{k}^{\text{\rm
true}}\|^{2}+\tfrac{1}{2}\kappa_{d}^{2}\|H_{k}\|\mathbb{E}_{k}[\|G_{k}\|^{2}]$
$\displaystyle\leq$ $\displaystyle\ \tfrac{1}{2}\|H_{k}\|\|d_{k}^{\text{\rm
true}}\|^{2}+\kappa_{d}^{2}\|H_{k}\|\mathbb{E}_{k}[\|G_{k}-\nabla
f(x_{k})\|^{2}+\|\nabla f(x_{k})\|^{2}]$ $\displaystyle\leq$ $\displaystyle\
\tfrac{1}{2}\kappa_{H}\kappa_{d}^{2}\kappa_{g}^{2}+\kappa_{H}\kappa_{d}^{2}(M+\kappa_{g}^{2})\leq\kappa_{H}\kappa_{d}^{2}(M+\tfrac{3}{2}\kappa_{g}^{2}).$
(31)

By the Law of Total Expectation, (30), and (31), it follows that

$\displaystyle\mathbb{E}_{k}[Q_{k}|E_{Q}]\mathbb{P}_{k}[E_{Q}]$
$\displaystyle=\mathbb{E}_{k}[|Q_{k}||E_{Q}]\mathbb{P}_{k}[E_{Q}]$
$\displaystyle=\mathbb{E}_{k}[|Q_{k}|]-\mathbb{E}_{k}[|Q_{k}||E_{Q}^{c}]\mathbb{P}_{k}[E_{Q}^{c}]$
$\displaystyle\leq\kappa_{d}\sqrt{M}(2\kappa_{g}+\sqrt{M})+\kappa_{H}\kappa_{d}^{2}(M+\tfrac{3}{2}\kappa_{g}^{2}),$

and by a similar argument, one finds that

$\displaystyle-\mathbb{E}_{k}[Q_{k}|E_{Q}^{c}]\mathbb{P}_{k}[E_{Q}^{c}]$
$\displaystyle=\mathbb{E}_{k}[|Q_{k}||E_{Q}^{c}]\mathbb{P}_{k}[E_{Q}^{c}]$
$\displaystyle=\mathbb{E}_{k}[|Q_{k}|]-\mathbb{E}_{k}[|Q_{k}||E_{Q}]\mathbb{P}_{k}[E_{Q}]$
$\displaystyle\leq\kappa_{d}\sqrt{M}(2\kappa_{g}+\sqrt{M})+\kappa_{H}\kappa_{d}^{2}(M+\tfrac{3}{2}\kappa_{g}^{2}).$

The conclusion follows by combining these equations, (28), and (29). ∎∎

Our next lemma bounds differences between expected reductions in the model of
the merit function that account for cases when $\hat{\cal T}_{k}<{\cal
T}_{k}$.

######  Lemma 8.

Let Assumptions 1, 2, and 3 hold and let $\kappa_{d}\in\mathbb{R}_{>0}$ be
defined by Lemma 4. Then, for all $k\in[k_{\max}]$ and $g_{[k-1]}$, with
$(\alpha_{\min,k}^{<},\alpha_{\min,k}^{=},\varsigma_{\max,k})$ defined as in
(22) and $\hat{{\cal T}}_{k}$ defined in (27), one finds that

$\displaystyle\ \mathbb{E}_{k}[{\cal A}_{k}\Delta q(x_{k},\hat{{\cal
T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})]-\mathbb{E}_{k}[{\cal
A}_{k}\Delta q(x_{k},{\cal T}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm
true}})]$ $\displaystyle\leq$ $\displaystyle\
(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\kappa_{d}\kappa_{g}^{2}(1+\tfrac{1}{2}\kappa_{H}\kappa_{d})$

and

$\displaystyle\ \mathbb{E}_{k}[{\cal A}_{k}\Delta q(x_{k},{\cal
T}_{k},G_{k},H_{k},D_{k})]-\mathbb{E}_{k}[{\cal A}_{k}\Delta
q(x_{k},\hat{{\cal T}}_{k},G_{k},H_{k},D_{k})]$ $\displaystyle\leq$
$\displaystyle\
(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\kappa_{d}(2+\kappa_{H}\kappa_{d})(M+\kappa_{g}^{2}).$

###### Proof.

Under the stated assumptions, it follows from the stated lemma and
definitions, along with the definition of $\Delta q$ in (10), that

$\displaystyle\ \mathbb{E}_{k}[{\cal A}_{k}\Delta q(x_{k},\hat{{\cal
T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})]-\mathbb{E}_{k}[{\cal
A}_{k}\Delta q(x_{k},{\cal T}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm
true}})]$ $\displaystyle=$ $\displaystyle\ \mathbb{E}_{k}[{\cal A}_{k}({\cal
T}_{k}-\hat{{\cal T}}_{k})(\nabla f(x_{k})^{\top}d_{k}^{\text{\rm
true}}+\tfrac{1}{2}\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}},0\\})]$ $\displaystyle\leq$
$\displaystyle\
(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})|\nabla
f(x_{k})^{\top}d_{k}^{\text{\rm true}}+\tfrac{1}{2}\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}},0\\}|$ $\displaystyle\leq$
$\displaystyle\
(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})(\kappa_{d}\kappa_{g}^{2}+\tfrac{1}{2}\kappa_{H}\kappa_{d}^{2}\kappa_{g}^{2}),$

and, along with $\|a\|^{2}\leq 2(\|a-b\|^{2}+\|b\|^{2})$ for any
$(a,b)\in\mathbb{R}^{n}\times\mathbb{R}^{n}$, one finds

$\displaystyle\ \mathbb{E}_{k}[{\cal A}_{k}\Delta q(x_{k},{\cal
T}_{k},G_{k},H_{k},D_{k})]-\mathbb{E}_{k}[{\cal A}_{k}\Delta
q(x_{k},\hat{{\cal T}}_{k},G_{k},H_{k},D_{k})]$ $\displaystyle=$
$\displaystyle\ \mathbb{E}_{k}[{\cal A}_{k}(\hat{{\cal T}}_{k}-{\cal
T}_{k})(G_{k}^{\top}D_{k}+\tfrac{1}{2}\max\\{D_{k}^{\top}H_{k}D_{k},0\\})]$
$\displaystyle\leq$ $\displaystyle\
(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\mathbb{E}_{k}[|G_{k}^{\top}D_{k}+\tfrac{1}{2}\max\\{D_{k}^{\top}H_{k}D_{k},0\\}|]$
$\displaystyle\leq$ $\displaystyle\
(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})(\kappa_{d}+\tfrac{1}{2}\kappa_{d}^{2}\kappa_{H})\mathbb{E}_{k}[\|G_{k}\|^{2}]$
$\displaystyle\leq$ $\displaystyle\
(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})(\kappa_{d}+\tfrac{1}{2}\kappa_{d}^{2}\kappa_{H})(2(M+\kappa_{g}^{2})),$

which together are the desired conclusions. ∎∎

Our next two lemmas are critical elements of our analysis. For both lemmas, we
define, for any $s\in\mathbb{N}$ and $\delta\in(0,1)$, the quantities

$\hat{\delta}:=\frac{\delta}{\sum_{j=0}^{\max\\{s_{\max}-1,0\\}}\binom{k_{\max}}{j}}$
(32)

and

$\ell(s,\hat{\delta}):=s+\log(1/\hat{\delta})+\sqrt{\log(1/\hat{\delta})^{2}+2s\log(1/\hat{\delta})}.$
(33)

The first of these lemmas bounds, with high probability, the sum of the
probabilities of the occurrences of event $E_{k,3}$ over the run of the
algorithm.

######  Lemma 9.

Suppose Assumptions 1, 2, and 3 hold. Then, for any $\delta\in(0,1)$,

$\mathbb{P}\left[\sum_{k=0}^{k_{\max}}\mathbb{P}[E_{k,3}|E,\mathcal{F}_{k}]\leq\ell(s_{\max},\hat{\delta})+1\Bigg{|}E\right]\geq
1-\delta.$ (34)

###### Proof.

This result is proved in Appendix 7. ∎∎

For our next lemma, let us define the random index set

${\cal K}_{\tau}:=\\{k\in[k_{\max}]:{\cal T}_{k}^{\rm\text{trial},\text{\rm
true}}<{\cal T}_{k-1}\\}.$ (35)

By the manner in which $\\{{\cal T}_{k}\\}$, $\\{{\cal
T}_{k}^{\rm\text{trial},\text{\rm true}}\\}$, and $\\{\hat{{\cal T}}_{k}\\}$
are defined, this set is always a superset of the iterations in which
$\hat{{\cal T}}_{k}<{\cal T}_{k}$; hence, by bounding the cardinality of (35),
one bounds the cardinality of the set of iterations in which $\hat{{\cal
T}}_{k}<{\cal T}_{k}$, which is needed for our main theorem. The reason that
we consider the set ${\cal K}_{\tau}$ in (35) is the fact that, conditioned on
the algorithm having generated a particular set of stochastic gradients up to
the beginning of iteration $k$, whether or not
$\tau_{k}^{\rm\text{trial},\text{\rm true}}<\tau_{k-1}$ holds has already been
determined; in other words, the occurrence of this inequality does not depend
on $G_{k}$. This means that $G_{k}$ is conditionally independent of the event
${\cal T}_{k}^{\rm\text{trial},\text{\rm true}}<{\cal T}_{k-1}$ given
$g_{[k-1]}$ and $E$, which is a fact that is exploited in the proof of the
lemma.

######  Lemma 10.

Suppose Assumptions 1, 2, 3, and 4 hold and let ${\cal K}_{\tau}$ be defined
as in (35). Then, for any $\delta\in(0,1)$, it follows that

$\mathbb{P}\left[|\mathcal{K}_{\tau}|\leq\left\lceil\frac{\ell(s_{\max},\hat{\delta})+1}{p_{\tau}}\right\rceil\Bigg{|}E\right]\geq
1-\delta.$ (36)

###### Proof.

This result is proved in Appendix 7. ∎

We are now prepared to prove a convergence rate result.

######  Theorem 2.

Suppose Assumptions 1, 2, 3, and 4 hold, let $s_{\max}\geq 1$, let
$\kappa_{d}\in\mathbb{R}_{>0}$ be defined by Lemma 4, define

$A_{\min}:=\ \frac{\xi_{\min}\tau_{\min}}{\tau_{\min}L+\Gamma}\ \ \text{and}\
\ A_{\max}:=\frac{\xi_{-1}\tau_{-1}}{\tau_{-1}L+\Gamma},$

suppose that $\beta_{k}=\beta$ for all $k\in[k_{\max}]$ where

$\beta:=\frac{\gamma}{\sqrt{k_{\max}+1}}\ \ \text{for some}\ \
\gamma\in\left(0,\frac{A_{\min}}{A_{\max}+\theta}\right],$ (37)

define

$\displaystyle{\overline{M\mkern 4.0mu}\mkern-4.0mu}{}:=$ $\displaystyle\
\tfrac{1}{4}(A_{\max}+\theta\beta)(\tau_{-1}+\tau_{\min})\zeta^{-1}M$
$\displaystyle\
+\tfrac{1}{2}(A_{\max}+\theta\beta)(\tau_{-1}-\tau_{\min})(\kappa_{d}\sqrt{M}(2\kappa_{g}+\sqrt{M})+\kappa_{H}\kappa_{d}^{2}(M+\tfrac{3}{2}\kappa_{g}^{2}))$
$\displaystyle\ +\theta\tau_{-1}\kappa_{g}\kappa_{d}\sqrt{M}$
$\displaystyle\kappa_{E_{3}}:=$ $\displaystyle\
((A_{\max}+\theta\beta)\tau_{-1}-A_{\min}\tau_{\min})\kappa_{g}\kappa_{d}M_{\tau},$
$\displaystyle\kappa_{\Delta q,1}:=$ $\displaystyle\
((A_{\max}+\theta\beta)\tau_{-1}-A_{\min}\tau_{\min})\kappa_{d}\kappa_{g}^{2}(1+\tfrac{1}{2}\kappa_{H}\kappa_{d})\
\ \text{and}$ $\displaystyle\kappa_{\Delta q,2}:=$ $\displaystyle\
((A_{\max}+\theta\beta)\tau_{-1}-A_{\min}\tau_{\min})\kappa_{d}(1+\tfrac{1}{2}\kappa_{H}\kappa_{d})(M+\kappa_{g}^{2}),$

and, for all $k\in[k_{\max}]$ and $g_{[k-1]}$, let $\hat{{\cal T}}_{k}$ be
defined as in (27). Then, for any $\delta\in(0,1)$, it follows with $K^{*}$
having a discrete uniform distribution over $[k_{\max}]$ and $\hat{\delta}$
and $\ell$ defined as in (32) and (33) that, with probability at least
$1-\delta$,

$\displaystyle\ \mathbb{E}[\Delta q(X_{K^{*}},\hat{{\cal T}}_{K^{*}},\nabla
f(X_{K^{*}}),H_{K^{*}},D_{K^{*}}^{\rm true})|E]$ $\displaystyle\leq$
$\displaystyle\
2\left(\frac{\tau_{-1}(f_{0}-f_{\min})+\|c_{0}\|_{1}+{\overline{M\mkern
4.0mu}\mkern-4.0mu}{}\gamma^{2}+\kappa_{E_{3}}\gamma(\ell(s_{\max},\hat{\delta}/2)+1)/\sqrt{k_{\max}+1}}{A_{\min}\gamma\sqrt{k_{\max}+1}}\right)$
$\displaystyle\ +\frac{2(\kappa_{\Delta q,1}\gamma+\kappa_{\Delta
q,2}\gamma^{2}/\sqrt{k_{\max}+1})}{A_{\min}\gamma(k_{\max}+1)}\left\lceil\frac{\ell(s_{\max},\hat{\delta}/2)+1}{p_{\tau}}\right\rceil.$
(38)

###### Proof.

First, consider arbitrary $k\in[k_{\max}]$. By Lemmas 3 and 6, one has that

$\displaystyle\ \mathbb{E}_{k}[\phi(x_{k}+{\cal A}_{k}D_{k},{\cal
T}_{k})]-\mathbb{E}_{k}[\phi(x_{k},{\cal T}_{k})]$ $\displaystyle\leq$
$\displaystyle\ \mathbb{E}_{k}[-{\cal A}_{k}\Delta q(x_{k},{\cal T}_{k},\nabla
f(x_{k}),H_{k},d_{k}^{\text{\rm true}})+\tfrac{1}{2}{\cal A}_{k}\beta\Delta
q(x_{k},{\cal T}_{k},G_{k},H_{k},D_{k})$ $\displaystyle\ +{\cal A}_{k}{\cal
T}_{k}\nabla f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})]$
$\displaystyle\leq$ $\displaystyle\ \mathbb{E}_{k}[-{\cal A}_{k}\Delta
q(x_{k},{\cal T}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm
true}})+\tfrac{1}{2}{\cal A}_{k}\beta\Delta q(x_{k},{\cal
T}_{k},G_{k},H_{k},D_{k})]$ $\displaystyle\
+(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\kappa_{g}\kappa_{d}M_{\tau}\mathbb{P}_{k}[E_{k,3}]+\theta\beta^{2}\tau_{k-1}\kappa_{g}\kappa_{d}\sqrt{M}.$
(39)

Our next aim is to prove that, roughly speaking, one in fact finds that

$\mathbb{E}_{k}[\phi(x_{k}+{\cal A}_{k}D_{k},{\cal
T}_{k})]-\mathbb{E}_{k}[\phi(x_{k},{\cal T}_{k})]\\\
\leq-\tfrac{1}{2}A_{\min}\beta\mathbb{E}_{k}[\Delta q(x_{k},\hat{{\cal
T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})]+\text{``noise.''}$
(40)

Such a bound does not follow directly from (39) since the first term on the
right-hand side in (39) involves a model reduction with respect to ${\cal
T}_{k}$ (which cannot be tied to a stationarity measure), whereas the first
term on the right-hand side of the bound in (40) involves a model reduction
with respect to $\hat{\cal T}_{k}$ (which can be tied to a stationarity
measure). Toward the aim of proving a bound of the form in (40), first observe
that it follows with Lemma 7 that

$\displaystyle\ \mathbb{E}_{k}[-{\cal A}_{k}\Delta q(x_{k},\hat{{\cal
T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})+\tfrac{1}{2}{\cal
A}_{k}\beta\Delta q(x_{k},\hat{{\cal T}}_{k},G_{k},H_{k},D_{k})]$
$\displaystyle\
+(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\kappa_{g}\kappa_{d}M_{\tau}\mathbb{P}_{k}[E_{k,3}]+\theta\beta^{2}\tau_{k-1}\kappa_{g}\kappa_{d}\sqrt{M}$
$\displaystyle\leq$ $\displaystyle\ -A_{\min}\beta\mathbb{E}_{k}[\Delta
q(x_{k},\hat{{\cal T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})]$
$\displaystyle\
+\tfrac{1}{2}(A_{\max}\beta+\theta\beta^{2})\beta\mathbb{E}_{k}[\Delta
q(x_{k},\hat{{\cal T}}_{k},G_{k},H_{k},D_{k})]$ $\displaystyle\
+((A_{\max}\beta+\theta\beta^{2})\tau_{k-1}-A_{\min}\beta\tau_{\min})\kappa_{g}\kappa_{d}M_{\tau}\mathbb{P}_{k}[E_{k,3}]+\theta\beta^{2}\tau_{k-1}\kappa_{g}\kappa_{d}\sqrt{M}$
$\displaystyle\leq$ $\displaystyle\
-(A_{\min}-\tfrac{1}{2}(A_{\max}+\theta\beta)\beta)\beta\mathbb{E}_{k}[\Delta
q(x_{k},\hat{{\cal T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})]$
$\displaystyle\
+\tfrac{1}{4}(A_{\max}+\theta\beta)\beta^{2}(\tau_{k-1}+\tau_{\min})\zeta^{-1}M$
$\displaystyle\
+\tfrac{1}{2}(A_{\max}+\theta\beta)\beta^{2}(\tau_{k-1}-\tau_{\min})(\kappa_{d}\sqrt{M}(2\kappa_{g}+\sqrt{M})+\kappa_{H}\kappa_{d}^{2}(M+\tfrac{3}{2}\kappa_{g}^{2}))$
$\displaystyle\
+((A_{\max}+\theta\beta)\tau_{k-1}-A_{\min}\tau_{\min})\beta\kappa_{g}\kappa_{d}M_{\tau}\mathbb{P}_{k}[E_{k,3}]+\theta\beta^{2}\tau_{k-1}\kappa_{g}\kappa_{d}\sqrt{M}$
$\displaystyle\leq$ $\displaystyle\
-\tfrac{1}{2}A_{\min}\beta\mathbb{E}_{k}[\Delta q(x_{k},\hat{{\cal
T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})]$ $\displaystyle\
+\kappa_{E_{3}}\beta\mathbb{P}_{k}[E_{k,3}]+{\overline{M\mkern
4.0mu}\mkern-4.0mu}{}\beta^{2},$ (41)

where the final inequality follows due to the fact that
$(A_{\max}+\theta\beta)\beta\leq A_{\min}$ holds by the definitions of
$\beta$, $\gamma$, $A_{\min}$, and $A_{\max}$.

Let us now combine (39) and (41) to prove a bound of the form in (40) by
considering two complementary events. In particular, let $E_{k,\tau}$ be the
event that ${\cal T}_{k}^{\rm\text{trial},\text{\rm true}}<\tau_{k-1}$ and let
$E_{k,\tau}^{c}$ be the complementary event that ${\cal
T}_{k}^{\rm\text{trial},\text{\rm true}}\geq\tau_{k-1}$. Observe that whether
$E_{k,\tau}$ or $E_{k,\tau}^{c}$ occurs is determined by the condition that
$G_{[k-1]}=g_{k-1}$. Hence, the bound in Lemma 7—and in Lemma 8 as well, which
is used below—holds even if one conditions on the occurence of $E_{k,\tau}$ or
of $E_{k,\tau}^{c}$. Consequently, the bounds in (39) and (41) hold even if
one also conditions on the occurrence of $E_{k,\tau}$ or of $E_{k,\tau}^{c}$.
Let us now consider $E_{k,\tau}^{c}$ and $E_{k,\tau}$ in turn. Conditioning on
$E_{k,\tau}^{c}$, one finds from (39), (41), and the fact that ${\cal
T}_{k}^{\rm\text{trial},\text{\rm true}}\geq\tau_{k-1}\geq{\cal
T}_{k}=\hat{\cal T}_{k}$ (by (27)) in $E_{k,\tau}^{c}$ that

$\displaystyle\ \mathbb{E}_{k}[\phi(x_{k}+\alpha_{k}D_{k},{\cal
T}_{k})|E_{k,\tau}^{c}]-\mathbb{E}_{k}[\phi(x_{k},{\cal
T}_{k})|E_{k,\tau}^{c}]$ $\displaystyle\leq$ $\displaystyle\
\mathbb{E}_{k}[-{\cal A}_{k}\Delta q(x_{k},{\cal T}_{k},\nabla
f(x_{k}),H_{k},d_{k}^{\text{\rm true}})+\tfrac{1}{2}{\cal A}_{k}\beta\Delta
q(x_{k},{\cal T}_{k},G_{k},H_{k},D_{k})|E_{k,\tau}^{c}]$ $\displaystyle\
+(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\kappa_{g}\kappa_{d}M_{\tau}\mathbb{P}_{k}[E_{k,3}|E_{k,\tau}^{c}]+\theta\beta^{2}\tau_{k-1}\kappa_{g}\kappa_{d}\sqrt{M}$
$\displaystyle=$ $\displaystyle\ \mathbb{E}_{k}[-{\cal A}_{k}\Delta
q(x_{k},\hat{{\cal T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm
true}})+\tfrac{1}{2}{\cal A}_{k}\beta\Delta q(x_{k},\hat{{\cal
T}}_{k},G_{k},H_{k},D_{k})|E_{k,\tau}^{c}]$ $\displaystyle\
+(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\kappa_{g}\kappa_{d}M_{\tau}\mathbb{P}_{k}[E_{k,3}|E_{k,\tau}^{c}]+\theta\beta^{2}\tau_{k-1}\kappa_{g}\kappa_{d}\sqrt{M}$
$\displaystyle\leq$ $\displaystyle\
-\tfrac{1}{2}A_{\min}\beta\mathbb{E}_{k}[\Delta q(x_{k},\hat{{\cal
T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})|E_{k,\tau}^{c}]$
$\displaystyle\
+\kappa_{E_{3}}\beta\mathbb{P}_{k}[E_{k,3}|E_{k,\tau}^{c}]+{\overline{M\mkern
4.0mu}\mkern-4.0mu}{}\beta^{2}.$

On the other hand, one finds from (39), (41), and Lemma 8 that

$\displaystyle\ \mathbb{E}_{k}[\phi(x_{k}+{\cal A}_{k}D_{k},{\cal
T}_{k})|E_{k,\tau}]-\mathbb{E}_{k}[\phi(x_{k},{\cal T}_{k})|E_{k,\tau}]$
$\displaystyle\leq$ $\displaystyle\ \mathbb{E}_{k}[-{\cal A}_{k}\Delta
q(x_{k},{\cal T}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm
true}})+\tfrac{1}{2}{\cal A}_{k}\beta\Delta q(x_{k},{\cal
T}_{k},G_{k},H_{k},D_{k})|E_{k,\tau}]$ $\displaystyle\ +\mathbb{E}_{k}[-{\cal
A}_{k}\Delta q(x_{k},\hat{{\cal T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm
true}})+\tfrac{1}{2}{\cal A}_{k}\beta\Delta q(x_{k},\hat{{\cal
T}}_{k},G_{k},H_{k},D_{k})|E_{k,\tau}]$ $\displaystyle\ -\mathbb{E}_{k}[-{\cal
A}_{k}\Delta q(x_{k},\hat{{\cal T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm
true}})+\tfrac{1}{2}{\cal A}_{k}\beta\Delta q(x_{k},\hat{{\cal
T}}_{k},G_{k},H_{k},D_{k})|E_{k,\tau}]$ $\displaystyle\
+(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\kappa_{g}\kappa_{d}M_{\tau}\mathbb{P}_{k}[E_{k,3}|E_{k,\tau}]+\theta\beta^{2}\tau_{k-1}\kappa_{g}\kappa_{d}\sqrt{M}$
$\displaystyle\leq$ $\displaystyle\ \mathbb{E}_{k}[-{\cal A}_{k}\Delta
q(x_{k},{\cal T}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm
true}})+\tfrac{1}{2}{\cal A}_{k}\beta\Delta q(x_{k},{\cal
T}_{k},G_{k},H_{k},D_{k})|E_{k,\tau}]$ $\displaystyle\
-\tfrac{1}{2}A_{\min}\beta\mathbb{E}_{k}[\Delta q(x_{k},\hat{{\cal
T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})|E_{k,\tau}]$
$\displaystyle\ -\mathbb{E}_{k}[-{\cal A}_{k}\Delta q(x_{k},\hat{{\cal
T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})+\tfrac{1}{2}{\cal
A}_{k}\beta\Delta q(x_{k},\hat{{\cal T}}_{k},G_{k},H_{k},D_{k})|E_{k,\tau}]$
$\displaystyle\
+\kappa_{E_{3}}\beta\mathbb{P}_{k}[E_{k,3}|E_{k,\tau}]+{\overline{M\mkern
4.0mu}\mkern-4.0mu}{}\beta^{2}$ $\displaystyle\leq$ $\displaystyle\
-\tfrac{1}{2}A_{\min}\beta\mathbb{E}_{k}[\Delta q(x_{k},\hat{{\cal
T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})|E_{k,\tau}]$
$\displaystyle\
+(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\kappa_{d}\kappa_{g}^{2}(1+\tfrac{1}{2}\kappa_{H}\kappa_{d})$
$\displaystyle\
+\tfrac{1}{2}(\varsigma_{\max,k}\tau_{k-1}-\alpha_{\min,k}^{<}\tau_{\min})\kappa_{d}(2+\kappa_{H}\kappa_{d})(M+\kappa_{g}^{2})\beta$
$\displaystyle\
+\kappa_{E_{3}}\beta\mathbb{P}_{k}[E_{k,3}|E_{k,\tau}]+{\overline{M\mkern
4.0mu}\mkern-4.0mu}{}\beta^{2}$ $\displaystyle\leq$ $\displaystyle\
-\tfrac{1}{2}A_{\min}\beta\mathbb{E}_{k}[\Delta q(x_{k},\hat{{\cal
T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})|E_{k,\tau}]$
$\displaystyle\
+\kappa_{E_{3}}\beta\mathbb{P}_{k}[E_{k,3}|E_{k,\tau}]+{\overline{M\mkern
4.0mu}\mkern-4.0mu}{}\beta^{2}+\kappa_{\Delta q,1}\beta+\kappa_{\Delta
q,2}\beta^{2}.$

Hence, by the laws of total probability and expectation, one finds that

$\displaystyle\ \mathbb{E}_{k}[\phi(x_{k}+{\cal A}_{k}D_{k},{\cal
T}_{k})]-\mathbb{E}_{k}[\phi(x_{k},{\cal T}_{k})]$ $\displaystyle=$
$\displaystyle\ (\mathbb{E}_{k}[\phi(x_{k}+{\cal A}_{k}D_{k},{\cal
T}_{k})|E_{k,\tau}]-\mathbb{E}_{k}[\phi(x_{k},{\cal
T}_{k})|E_{k,\tau}])\mathbb{P}_{k}[E_{k,\tau}]$ $\displaystyle\
+(\mathbb{E}_{k}[\phi(x_{k}+{\cal A}_{k}D_{k},{\cal
T}_{k})|E_{k,\tau}^{c}]-\mathbb{E}_{k}[\phi(x_{k},{\cal
T}_{k})|E_{k,\tau}^{c}])\mathbb{P}_{k}[E_{k,\tau}^{c}]$ $\displaystyle\leq$
$\displaystyle\ -\tfrac{1}{2}A_{\min}\beta\mathbb{E}_{k}[\Delta
q(x_{k},\hat{{\cal T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})]$
$\displaystyle\ +\kappa_{E_{3}}\beta\mathbb{P}_{k}[E_{k,3}]+{\overline{M\mkern
4.0mu}\mkern-4.0mu}{}\beta^{2}+(\kappa_{\Delta q,1}\beta+\kappa_{\Delta
q,2}\beta^{2})\mathbb{P}_{k}[E_{k,\tau}].$

Summing this inequality for all $k\in[k_{\max}]$ yields

$\displaystyle\ \sum_{k=0}^{k_{\max}}(\mathbb{E}_{k}[\phi(x_{k}+{\cal
A}_{k}D_{k},{\cal T}_{k})]-\mathbb{E}_{k}[\phi(x_{k},{\cal T}_{k})])$
$\displaystyle\leq$ $\displaystyle\
\sum_{k=0}^{k_{\max}}(-\tfrac{1}{2}A_{\min}\beta\mathbb{E}_{k}[\Delta
q(x_{k},\hat{{\cal T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm true}})])$
$\displaystyle\
+\sum_{k=0}^{k_{\max}}(\kappa_{E_{3}}\beta\mathbb{P}_{k}[E_{k,3}]+(\kappa_{\Delta
q,1}\beta+\kappa_{\Delta
q,2}\beta^{2})\mathbb{P}_{k}[E_{k,\tau}])+(k_{\max}+1){\overline{M\mkern
4.0mu}\mkern-4.0mu}{}\beta^{2}.$

Let us now turn to analyzing the overall behavior of the algorithm through
iterations $k\in[k_{\max}]$. Let $f_{G_{[k_{\max}]}}$ denote the probability
density function of $G_{[k_{\max}]}$ and observe that, for all
$k\in[k_{\max}]$, one finds $\mathbb{P}_{k}[E_{k,\tau}]\in\\{0,1\\}$ since,
when conditioned on $E$ and ${\cal F}_{k}$, the event $E_{k,\tau}$ is
independent of $G_{k}$. Therefore, by the bound above, the law of total
expectation, Lemma 9, Lemma 10, and the union bound, it follows that, with
probability at least $1-\delta$, one finds

$\displaystyle\ \sum_{k=0}^{k_{\max}}(\mathbb{E}[\phi(X_{k}+{\cal
A}_{k}D_{k},{\cal T}_{k})|E,{\cal F}_{k+1}]-\mathbb{E}[\phi(X_{k},{\cal
T}_{k})|E,{\cal F}_{k+1}])$ $\displaystyle=$ $\displaystyle\
\int_{g_{[k_{\max}]}\in{\cal
F}_{k_{\max}+1}}\sum_{k=0}^{k_{\max}}\mathbb{E}[\phi(x_{k}+{\cal
A}_{k}D_{k},{\cal T}_{k})-\phi(x_{k},{\cal
T}_{k})|E,G_{[k_{\max}]}=g_{[k_{\max}]}]$ $\displaystyle\hskip 93.95122pt\cdot
f_{G_{[k_{\max}]}}(g_{[k_{\max}]})\textrm{d}g_{[k_{\max}]}$
$\displaystyle\leq$ $\displaystyle\ \int_{g_{[k_{\max}]}\in{\cal
F}_{k_{\max}+1}}\Bigg{(}-\tfrac{1}{2}A_{\min}\beta\sum_{k=0}^{k_{\max}}\mathbb{E}[\Delta
q(x_{k},\hat{{\cal T}}_{k},\nabla f(x_{k}),H_{k},d_{k}^{\text{\rm
true}})|E,G_{[k_{\max}]}=g_{[k_{\max}]}]$ $\displaystyle\hskip
93.95122pt+\kappa_{E_{3}}\beta\sum_{k=0}^{k_{\max}}\mathbb{P}[E_{k,3}|E,G_{[k_{\max}]}=g_{[k_{\max}]}]$
$\displaystyle\hskip 93.95122pt+(\kappa_{\Delta q,1}\beta+\kappa_{\Delta
q,2}\beta^{2})\sum_{k=0}^{k_{\max}}\mathbb{P}[E_{k,\tau}|E,G_{[k_{\max}]}=g_{[k_{\max}]}]\Bigg{)}$
$\displaystyle\hskip 93.95122pt\cdot
f_{G_{[k_{\max}]}}(g_{[k_{\max}]})\textrm{d}g_{[k_{\max}]}$ $\displaystyle\
+(k_{\max}+1){\overline{M\mkern 4.0mu}\mkern-4.0mu}{}\beta^{2}$
$\displaystyle=$ $\displaystyle\
-\tfrac{1}{2}A_{\min}\beta\sum_{k=0}^{k_{\max}}\mathbb{E}[\Delta
q(X_{k},\hat{{\cal T}}_{k},\nabla f(X_{k}),H_{k},D_{k}^{\text{\rm
true}})|E,{\cal F}_{k}]$ $\displaystyle\
+\kappa_{E_{3}}\beta\sum_{k=0}^{k_{\max}}\mathbb{P}[E_{k,3}|E,{\cal
F}_{k}]+(\kappa_{\Delta q,1}\beta+\kappa_{\Delta
q,2}\beta^{2})\mathbb{E}[|{\cal K}_{\tau}||E]+(k_{\max}+1){\overline{M\mkern
4.0mu}\mkern-4.0mu}{}\beta^{2}$ $\displaystyle\leq$ $\displaystyle\
-\tfrac{1}{2}A_{\min}\beta\sum_{k=0}^{k_{\max}}\mathbb{E}[\Delta
q(X_{k},\hat{{\cal T}}_{k},\nabla f(X_{k}),H_{k},D_{k}^{\text{\rm
true}})|E,{\cal F}_{k}]$ $\displaystyle\
+\kappa_{E_{3}}\beta(\ell(s_{\max},\hat{\delta}/2)+1)$ $\displaystyle\
+(\kappa_{\Delta q,1}\beta+\kappa_{\Delta
q,2}\beta^{2})\left\lceil\frac{\ell(s_{\max},\hat{\delta}/2)+1}{p_{\tau}}\right\rceil+(k_{\max}+1){\overline{M\mkern
4.0mu}\mkern-4.0mu}{}\beta^{2}.$ (42)

The left-hand side of this inequality satisfies

$\displaystyle\ \sum_{k=0}^{k_{\max}}(\mathbb{E}[\phi(X_{k}+{\cal
A}_{k}D_{k},{\cal T}_{k})|E,{\cal F}_{k+1}]-\mathbb{E}[\phi(X_{k},{\cal
T}_{k})|E,{\cal F}_{k+1}])$ $\displaystyle=$ $\displaystyle\
\sum_{k=0}^{k_{\max}}\Bigg{(}\mathbb{E}[{\cal T}_{k}(f(X_{k}+{\cal
A}_{k}D_{k})-f_{\min})+\|c(X_{k}+{\cal A}_{k}D_{k})\|_{1}|E,{\cal F}_{k+1}]$
$\displaystyle\hskip 32.52127pt-\mathbb{E}[{\cal
T}_{k}(f(X_{k})-f_{\min})+\|c(X_{k})\|_{1}|E,{\cal F}_{k+1}]\Bigg{)}.$ (43)

By the merit parameter updating strategy and the definition of the filtration
(which guarantees that ${\cal T}_{k-1}$ and $X_{k}$ are fully determined by
$G_{[k-1]}$, and are therefore conditionally independent of ${\cal F}_{k+1}$)
that, for all $k\in[k_{\max}]$, one finds

$\displaystyle\ -\mathbb{E}[{\cal
T}_{k}(f(X_{k})-f_{\min})+\|c(X_{k})\|_{1}|E,{\cal F}_{k+1}]$
$\displaystyle\geq$ $\displaystyle\ -\mathbb{E}[{\cal
T}_{k-1}(f(X_{k})-f_{\min})+\|c(X_{k})\|_{1}|E,{\cal F}_{k+1}]$
$\displaystyle=$ $\displaystyle\ -\mathbb{E}[{\cal
T}_{k-1}(f(X_{k})-f_{\min})+\|c(X_{k})\|_{1}|E,{\cal F}_{k}].$

Thus, from (43), it follows that

$\displaystyle\ \sum_{k=0}^{k_{\max}}(\mathbb{E}[\phi(X_{k}+{\cal
A}_{k}D_{k},{\cal T}_{k})|E,{\cal F}_{k+1}]-\mathbb{E}[\phi(X_{k},{\cal
T}_{k})|E,{\cal F}_{k+1}])$ $\displaystyle\geq\mathbb{E}[{\cal
T}_{k_{\max}}(f(X_{k_{\max}+1})-f_{\min})+\|c(X_{k_{\max}+1})\|_{1}|E,{\cal
F}_{k_{\max}+1}]-\tau_{-1}(f_{0}-f_{\min})-\|c_{0}\|_{1}$
$\displaystyle\geq-\tau_{-1}(f_{0}-f_{\min})-\|c_{0}\|_{1}.$

Combining this with (42), one obtains that

$\displaystyle\
\frac{\beta}{\sum_{k=0}^{k_{\max}}\beta}\sum_{k=0}^{k_{\max}}\mathbb{E}[\Delta
q(X_{k},\hat{{\cal T}}_{k},\nabla f(X_{k}),H_{k},D_{k}^{\text{\rm
true}})|E,{\cal F}_{k}]$ $\displaystyle\leq$ $\displaystyle\
2\left(\frac{\tau_{-1}(f_{0}-f_{\min})+\|c_{0}\|_{1}+(k_{\max}+1){\overline{M\mkern
4.0mu}\mkern-4.0mu}{}\beta^{2}+\kappa_{E_{3}}\beta(\ell(s_{\max},\hat{\delta}/2)+1)}{A_{\min}{\sum_{k=0}^{k_{\max}}\beta}}\right)$
$\displaystyle\ +\frac{2(\kappa_{\Delta q,1}\beta+\kappa_{\Delta
q,2}\beta^{2})}{A_{\min}{\sum_{k=0}^{k_{\max}}\beta}}\left\lceil\frac{\ell(s_{\max},\hat{\delta}/2)+1}{p_{\tau}}\right\rceil.$

Hence, by the definitions of $K^{*}$ and $\beta$, the desired conclusion
follows. ∎∎

The following corollary translates the result of the preceding theorem to a
result pertaining to a stationary measure of (1); recall (3).

######  Corollary 1.

Under the assumptions, conditions, and definitions of Theorem 2, it holds with
probability at least $1-\delta\in(0,1)$ that

$\displaystyle\ \mathbb{E}\left[\frac{\|\nabla
f(X_{K^{*}})+J_{K^{*}}^{\top}Y_{K^{*}}^{true}\|^{2}}{\kappa_{H}^{2}}+\|c(X_{K^{*}})\|_{1}\Bigg{|}E\right]$
$\displaystyle\leq$ $\displaystyle\
2(\kappa_{\Psi}+1)\left(\frac{\tau_{-1}(f_{0}-f_{\min})+\|c_{0}\|_{1}+{\overline{M\mkern
4.0mu}\mkern-4.0mu}{}\gamma^{2}}{\kappa_{q}\tau_{\min}A_{\min}\gamma\sqrt{k_{\max}+1}}\right)$
$\displaystyle\
+2(\kappa_{\Psi}+1)\left(\frac{\kappa_{E_{3}}\gamma(\ell(s_{\max},\hat{\delta}/2)+1)}{\kappa_{q}\tau_{\min}A_{\min}\gamma\sqrt{k_{\max}+1}}\right)$
$\displaystyle\ +(\kappa_{\Psi}+1)\left(\frac{2(\kappa_{\Delta
q,1}\gamma+\kappa_{\Delta
q,2}\gamma^{2}/\sqrt{k_{\max}+1})}{\kappa_{q}\tau_{\min}A_{\min}\gamma(k_{\max}+1)}\right)\left\lceil\frac{\ell(s_{\max},\hat{\delta}/2)+1}{p_{\tau}}\right\rceil.$

Hence, the complexity bound described in Section 2.2 $($see (7)$)$ holds.

###### Proof.

The result follows by Lemma 1, Lemma 2, Theorem 2, and (15), which implies
that $\|\nabla
f(X_{K^{*}})+J_{K^{*}}^{\top}Y_{K^{*}}^{true}\|=\|H_{k^{*}}D^{true}_{K^{*}}\|\leq\kappa_{H}\|D^{true}_{K^{*}}\|$.
The worst-case complexity bound described in Section 2.2 follows by combining
this result with the definitions of $\kappa_{E_{3}}$, $\kappa_{\Delta q,1}$,
$\kappa_{\Delta q,2}$, and Lemma 22 in Appendix 7. ∎∎

This result, as well as that of Theorem 2, is proven under the assumption that
$s_{\max}\geq 1$. When $s_{\max}=0$, this result simplifies to a deterministic
complexity bound with the terms dependent on $s_{\max}$ and $\delta$ ommitted.
Under the condition $s_{\max}=0$, the proof follows by noting that
$\mathbb{P}_{k}[E_{k,3}]=\mathbb{P}_{k}[E_{k,\tau}]=0$ for all
$k\in[k_{\max}]$ (where $E_{k,\tau}$ is defined in the proof of Theorem 2)
along with a similar argument to the proof of Theorem 2.

Again, we remark that this result, when viewed in terms of the squared norm of
the gradient of the Lagrangian, matches the worst-case complexity of the
stochastic gradient method for the unconstrained setting [11].

###  4.5 Complexity Result for Symmetric Sub-Gaussian Distributions

In this section, we show that Assumption 3, Assumption 4, and the event $E$ in
(17) occur with high probability when each stochastic gradient is unbiased and
has a symmetric, sub-Gaussian distribution and the ratio parameter sequence
remains constant. For these purposes, we make the following assumption.

######  Assumption 5.

There exists $M\in\mathbb{R}_{>0}$ such that, for all $k\in[k_{\max}]$ and any
realization $g_{[k-1]}$ of $G_{[k-1]}$, one finds that

$\displaystyle\mathbb{E}[G_{k}|G_{[k-1]}=g_{[k-1]}]$ $\displaystyle=\nabla
f(x_{k})$ $\displaystyle\text{and}\ \ \mathbb{E}[\exp(\|G_{k}-\nabla
f(x_{k})\|^{2}/M)|G_{[k-1]}=g_{[k-1]}]$ $\displaystyle\leq\exp(1),$ (44)

and the random vectors $G_{k}-\nabla f(x_{k})$ and $\nabla f(x_{k})-G_{k}$
have equal distributions. Finally, for all $k\in[k_{\max}]$, the ratio
parameter $\Xi_{k}$ satisfies $\Xi_{k}=\xi_{\min}$.

Our first lemma shows that, under Assumption 5, Assumption 4 holds.

######  Lemma 11.

Under Assumptions 1, 2, and 5, it follows for all $k\in[k_{\max}]$ and any
realization $g_{[k-1]}$ of $G_{[k-1]}$ that

$\mathbb{P}[G_{k}^{\top}D_{k}+\max\\{D_{k}^{\top}H_{k}D_{k},0\\}\geq\nabla
f(x_{k})^{\top}d_{k}^{\text{\rm true}}+\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}},0\\}|g_{[k-1]}]\geq\tfrac{1}{2}.$

###### Proof.

Consider arbitrary $k\in[k_{\max}]$. Let $Z_{k}$ be a basis for the null space
of $J_{k}$, which under Assumption 1 is a matrix in
$\mathbb{R}^{n\times(n-m)}$. Then, let $W_{k}\in\mathbb{R}^{n-m}$ be a random
vector such that $U_{k}=Z_{k}W_{k}$, and let $w_{k}^{\text{\rm
true}}\in\mathbb{R}^{n-m}$ be such that $u_{k}^{\text{\rm
true}}=Z_{k}w_{k}^{\text{\rm true}}$. By (9),
$Z_{k}W_{k}=-Z_{k}(Z_{k}^{\top}H_{k}Z_{k})^{-1}Z_{k}^{\top}(G_{k}+H_{k}v_{k})$,
so that

$\displaystyle\ G_{k}^{\top}D_{k}+D_{k}^{\top}H_{k}D_{k}$ $\displaystyle=$
$\displaystyle\
v_{k}^{\top}H_{k}^{1/2}(I-H_{k}^{1/2}Z_{k}(Z_{k}^{\top}H_{k}Z_{k})^{-1}Z_{k}^{\top}H_{k}^{1/2})(H_{k}^{-1/2}G_{k}+H_{k}^{1/2}v_{k})$

and similarly

$\displaystyle\ \nabla f(x_{k})^{\top}d_{k}^{\text{\rm
true}}+(d_{k}^{\text{\rm true}})^{\top}H_{k}d_{k}^{\text{\rm true}}$
$\displaystyle=$ $\displaystyle\
v_{k}^{\top}H_{k}^{1/2}(I-H_{k}^{1/2}Z_{k}(Z_{k}^{\top}H_{k}Z_{k})^{-1}Z_{k}^{\top}H_{k}^{1/2})(H_{k}^{-1/2}\nabla
f(x_{k})+H_{k}^{1/2}v_{k}).$

Hence, the random variables

$\displaystyle\ G_{k}^{\top}D_{k}+\max\\{D_{k}^{\top}H_{k}D_{k},0\\}-\nabla
f(x_{k})^{\top}d_{k}^{\text{\rm true}}-\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}},0\\}$ $\displaystyle=$
$\displaystyle\
v_{k}^{\top}H_{k}^{1/2}(I-H_{k}^{1/2}Z_{k}(Z_{k}^{\top}H_{k}Z_{k})^{-1}Z_{k}^{\top}H_{k}^{1/2})(H_{k}^{-1/2}(G_{k}-\nabla
f(x_{k})))$

and

$\displaystyle\ \nabla f(x_{k})^{\top}d_{k}^{\text{\rm
true}}+\max\\{(d_{k}^{\text{\rm true}})^{\top}H_{k}d_{k}^{\text{\rm
true}},0\\}-G_{k}^{\top}D_{k}-\max\\{D_{k}^{\top}H_{k}D_{k},0\\}$
$\displaystyle=$ $\displaystyle\
v_{k}^{\top}H_{k}^{1/2}(I-H_{k}^{1/2}Z_{k}(Z_{k}^{\top}H_{k}Z_{k})^{-1}Z_{k}^{\top}H_{k}^{1/2})(H_{k}^{-1/2}(\nabla
f(x_{k})-G_{k}))$

are equivalent in distribution by Assumption 5. Therefore,

$\displaystyle\
\mathbb{P}[G_{k}^{\top}D_{k}+\max\\{D_{k}^{\top}H_{k}D_{k},0\\}-\nabla
f(x_{k})^{\top}d_{k}^{\text{\rm true}}-\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}},0\\}\geq 0|g_{[k-1]}]$
$\displaystyle=$ $\displaystyle\ \mathbb{P}[\nabla
f(x_{k})^{\top}d_{k}^{\text{\rm true}}+\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm
true}},0\\}-G_{k}^{\top}D_{k}-\max\\{D_{k}^{\top}H_{k}D_{k},0\\}\geq
0|g_{[k-1]}]$

and

$\displaystyle 1$
$\displaystyle=\mathbb{P}[G_{k}^{\top}D_{k}+\max\\{D_{k}^{\top}H_{k}D_{k},0\\}-\nabla
f(x_{k})^{\top}d_{k}^{\text{\rm true}}-\max\\{(d_{k}^{\text{\rm
true}})^{\top}H_{k}d_{k}^{\text{\rm true}},0\\}\geq 0|g_{[k-1]}]$
$\displaystyle+\mathbb{P}[\nabla f(x_{k})^{\top}d_{k}^{\text{\rm
true}}+\max\\{(d_{k}^{\text{\rm true}})^{\top}H_{k}d_{k}^{\text{\rm
true}},0\\}-G_{k}^{\top}D_{k}-\max\\{D_{k}^{\top}H_{k}D_{k},0\\}\geq
0|g_{[k-1]}]$ $\displaystyle-\mathbb{P}[\nabla f(x_{k})^{\top}d_{k}^{\text{\rm
true}}+\max\\{(d_{k}^{\text{\rm true}})^{\top}H_{k}d_{k}^{\text{\rm
true}},0\\}-G_{k}^{\top}D_{k}-\max\\{D_{k}^{\top}H_{k}D_{k},0\\}=0|g_{[k-1]}],$

which combined leads to the desired conclusion. ∎∎

Next, we state a result based on well-known properties of sub-Gaussian random
variables. This lemma follows in the same manner as [16, Lemma 5].

######  Lemma 12.

Suppose Assumption 5 holds. Then, for any $\delta\in(0,1)$,

$\mathbb{P}\left[\underset{k\in[k_{\max}]}{\max}\|G_{k}-\nabla
f(X_{k})\|\leq\sqrt{M\left(1+\log\left(\frac{k_{\max}+1}{\delta}\right)\right)}\right]\geq
1-\delta.$

We conclude this subsection by showing that, under Assumption 5, both
Assumption 3 and event $E$ occur with high probability.

######  Lemma 13.

Suppose that Assumptions 1, 2, and 5 hold, let $\kappa_{v}$ be defined as in
[2, Lemma 2.9], let $\kappa_{c}$ be an upper bound for $\|c_{k}\|_{2}$ for all
$k\in[k_{\max}]$ $($the existence of which follows under Assumption 1$)$, and
define

$\displaystyle\kappa_{\tau_{\min}}:=$ $\displaystyle\
\kappa_{v}\Bigg{(}\kappa_{g}+\sqrt{M\left(1+\log\left(\frac{k_{\max}+1}{\delta}\right)\right)}$
$\displaystyle\
+\frac{\kappa_{H}}{\zeta}\left(\sqrt{M\left(1+\log\left(\frac{k_{\max}+1}{\delta}\right)\right)}+\kappa_{g}+\zeta+\kappa_{H}\kappa_{v}\kappa_{c}\right)\Bigg{)}.$

Then, for any $\delta\in(0,1)$, it follows with probability at least
$1-\delta$ that the conditions in Assumption 3 and event $E$ hold with

$\displaystyle M_{\tau}$
$\displaystyle=\sqrt{M\left(1+\log\left(\frac{k_{\max}+1}{\delta}\right)\right)},\
\ \tau_{\min}=\frac{(1-\sigma)(1-\epsilon_{\tau})}{\kappa_{\tau_{\min}}},$
$\displaystyle\text{and}\ \ s_{\max}$
$\displaystyle=\min\left\\{k_{\max}+1,\left\lceil\frac{\log\left(\frac{\tau_{-1}\kappa_{\tau_{\min}}}{(1-\sigma)(1-\epsilon_{\tau})}\right)}{\log\left(\frac{1}{1-\epsilon_{\tau}}\right)}\right\rceil\right\\}.$

###### Proof.

By Lemma 12, the event considered in that lemma holds with probability at
least $1-\delta$. Hence, for the purposes of this proof, suppose that event
holds. By Jensen’s inequality, convexity of $\exp(\cdot)$, and (44), it
follows that

$\mathbb{E}[\|G_{k}-\nabla f(x_{k})\|^{2}|G_{[k-1]}=g_{[k-1]}]\leq M.$

In addition, it follows from the event in Lemma 12 that (20) holds with
$M_{\tau}$ as stated in the lemma. This accounts for Assumption 3. Now
consider event $E$. First, it follows from the arguments of [2, Lemma 2.15 and
2.16] combined with the event in Lemma 12 that ${\cal T}_{k}\geq\tau_{\min}$
and ${\cal T}_{k}^{\rm\text{trial},\text{\rm true}}\geq\tau_{\min}$ for all
$k\in[k_{\max}]$ for $\tau_{\min}$ as stated in the lemma. Second, it follows
from the stated value of $\tau_{\min}$ and (18) that $|\\{k\in[k_{\max}]:{\cal
T}_{k}<{\cal T}_{k-1}\\}|\leq s_{\max}$ for $s_{\max}$ as stated in the lemma.
Finally, the desired behavior of $\\{\Xi_{k}\\}$ follows from Assumption 5. ∎∎

###  4.6 Adaptive Ratio Parameter

In this section, we state a convergence rate result, which can be translated
to a worst-case complexity result, that relaxes the definition of the event
$E$ considered in prior sections. In particular, we remove the assumption that
$\Xi_{k}=\xi_{\min}\in(0,\infty)$ for all $k\in[k_{\max}]$. Importantly, it
has been proved in [2, Lemma 3.5] that, under our remaining assumptions, there
still exists $\xi_{\min}\in(0,\infty)$ such that $\Xi_{k}\geq\xi_{\min}$ for
all $k\in[k_{\max}]$. Therefore, by the manner in which the ratio parameter
sequence is set, it follows that there exists a maximum number of
$k\in[k_{\max}]$ such that $\Xi_{k}<\Xi_{k-1}$. Denoting this limit as
$r_{\max}\in\mathbb{N}$, it follows (for the same reasons as the bound for
$s_{\max}$ in (18)) that

$r_{\max}\leq\min\left\\{k_{\max}+1,\left\lceil\frac{\log(\xi_{\min}/\xi_{-1})}{\log(1-\epsilon_{\xi})}\right\rceil\right\\}.$

To formalize our new assumption, we define

$E_{\xi}:=E(k_{\max},s_{\max},r_{\max},\tau_{\min},\xi_{\min})$

as the event such that, in every realization of the algorithm, the merit
parameters $\\{\tau_{k}\\}^{k_{\max}}_{k=0}$ and ratio parameters
$\\{\xi_{k}\\}^{k_{\max}}_{k=0}$ satisfy

  * •

$\tau_{k}\geq\tau_{\min}>0$ for all $k\in[k_{\max}]$,

  * •

$\tau_{k}^{\rm\text{trial},\text{\rm true}}\geq\tau_{\min}>0$ for all
$k\in[k_{\max}]$,

  * •

$\xi_{k}\geq\xi_{\min}>0$ for all $k\in[k_{\max}]$,

  * •

$|\\{k\in[k_{\max}]:\tau_{k}<\tau_{k-1}\\}|\leq s_{\max}$, and

  * •

$|\\{k\in[k_{\max}]:\xi_{k}<\xi_{k-1}\\}|\leq r_{\max}$.

Since $\\{\Xi_{k}\\}$ is bounded below deterministically, this event is
identical to the event $E$ defined in (17), except that one may have
$\xi_{0}>\xi_{\min}$.

For the purposes of this section, redefining

$\mathbb{P}_{k}[\cdot]:=\mathbb{P}[\cdot|E_{\xi},G_{[k-1]}=g_{[k-1]}]\ \
\text{and}\ \
\mathbb{E}_{k}[\cdot]:=\mathbb{P}[\cdot|E_{\xi},G_{[k-1]}=g_{[k-1]}],$

our analysis of this case considers the following replacement of Assumption 3.

######  Assumption 6.

There exists $M\in\mathbb{R}_{>0}$ such that, for all $k\in[k_{\max}]$ and any
realization $g_{[k-1]}$ of $G_{[k-1]}$, one finds that

$\mathbb{E}_{k}[G_{k}]=\nabla
f(x_{k})\quad\text{and}\quad\mathbb{E}_{k}[\|G_{k}-\nabla
f(x_{k})\|_{2}^{2}]\leq M.$

In addition, there exist $M_{1}\in\mathbb{R}_{>0}$, $M_{2}\in\mathbb{R}_{>0}$,
and $M_{3}\in\mathbb{R}_{>0}$ such that, for all $k\in[k_{\max}]$ and any
realization $g_{[k-1]}$ of $G_{[k-1]}$, one finds that

$\displaystyle\text{either}\ \ \mathbb{P}_{k}[\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}}))<0,{\cal
T}_{k}<\tau_{k-1},\Xi_{k}=\xi_{k-1}]$ $\displaystyle=0$
$\displaystyle\text{or}\ \ \mathbb{E}_{k}[\|G_{k}-\nabla f(x_{k})\||\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}}))<0,{\cal
T}_{k}<\tau_{k-1},\Xi_{k}=\xi_{k-1}]$ $\displaystyle\leq\kappa_{1};$
$\displaystyle\text{either}\ \ \mathbb{P}_{k}[\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}}))<0,{\cal
T}_{k}=\tau_{k-1},\Xi_{k}<\xi_{k-1}]$ $\displaystyle=0$
$\displaystyle\text{or}\ \ \mathbb{E}_{k}[\|G_{k}-\nabla f(x_{k})\||\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}}))<0,{\cal
T}_{k}=\tau_{k-1},\Xi_{k}<\xi_{k-1}]$ $\displaystyle\leq\kappa_{2};$
$\displaystyle\text{and either}\ \ \mathbb{P}_{k}[\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}}))<0,{\cal
T}_{k}<\tau_{k-1},\Xi_{k}<\xi_{k-1}]$ $\displaystyle=0$
$\displaystyle\text{or}\ \ \mathbb{E}_{k}[\|G_{k}-\nabla f(x_{k})\||\nabla
f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}}))<0,{\cal
T}_{k}<\tau_{k-1},\Xi_{k}<\xi_{k-1}]$ $\displaystyle\leq\kappa_{3}.$

We claim that this assumption holds with high probability under Assumption 5
(without the assumption that $\Xi_{k}=\xi_{\min}$ for all $k\in[k_{\max}]$), a
result that can be derived by modification of the techniques used in Section
4.5.

The complexity analysis for this case follows by essentially the same
arguments as those used to derive a complexity result under Assumption 3. A
slight modification of Lemma 6 is needed to include the three events related
to the sign of $\nabla f(x_{k})^{\top}(D_{k}-d_{k}^{\text{\rm true}})$ that
appear in Assumption 6 (as opposed to the one in Assumption 3), which yields a
result in terms of the probabilities of these three events. Then, a slightly
modified Lemma 9 and the union bound can be applied two additional times to
derive a complexity result. Since the analysis is a straightforward, but
tedious extension of the results in Section 4.4, we simply state the extension
of (7) to this case without proof.

######  Theorem 3.

Suppose that Assumptions 1, 2, 4, and 6 hold and consider arbitrary
$\delta\in(0,1)$. Then, within $k_{\max}+1$ iterations, it holds with
probability at least $1-\delta$ that the algorithm generates
$x_{k^{*}}\in\mathbb{R}^{n}$ corresponding to which there exists an associated
Lagrange multiplier $y_{k^{*}}^{\text{true}}\in\mathbb{R}^{m}$ such that

$\displaystyle\ \mathbb{E}[\|\nabla
f_{k^{*}}+J_{k^{*}}^{\top}y_{k^{*}}^{true}\|^{2}+\|c_{k^{*}}\||E_{\xi}]$
$\displaystyle=$ $\displaystyle\
\mathcal{O}\Bigg{(}\frac{\tau_{-1}(f_{0}-f_{\text{\rm
low}})+\|c_{0}\|_{1}+M}{\sqrt{k_{\max}+1}}$
$\displaystyle\qquad+\frac{(\tau_{-1}\xi_{-1}-\tau_{\min}\xi_{\min})((s_{\max}+r_{\max})\log(k_{\max})+\log(1/\delta))}{\sqrt{k_{\max}+1}}\Bigg{)}.$

##  5 Conclusion

We proved a worst-case complexity bound (in terms of iterations, function
evaluations, and (stochastic) derivative evaluations) for the stochastic
sequential quadratic optimization method for solving optimization problems
involving a stochastic objective function and deterministic equality
constraints proposed in [2]. While key to the practical performance of the
algorithm, the adaptivity of the merit parameter introduced a number of
theoretical challenges to overcome. Under mostly standard assumptions, we
proved that, with high probability, a measure of primal-dual stationarity
decays at a rate of $k^{-4}$ (ignoring log factors), which translates into a
worst-case complexity bound on par with the stochastic gradient method in the
unconstrained setting.

While our analytical approach has been developed for an SQP method that uses
the merit function in (4), it may be applicable to a wide variety of
algorithmic frameworks for constrained stochastic optimization. For example,
our approach may be modified to apply to methods that adaptively update
critical parameters at each iteration, such as adaptive penalty methods [5, 6,
17], adaptive augmented Lagrangian methods [9], adaptive barrier methods [20],
and penalty-interior point methods [8]. In addition, many constrained
optimization algorithms generate (often unconstrained) subproblems defined by
an auxilliary parameter sequence that is updated dynamically based off of the
solution to the previous subproblem. Algorithms of this type include penalty
methods, augmented Lagrangian methods, and interior point methods [21]. In
cases when the objective is stochastic, this auxilliary sequence would also be
a random process, in which case analyzing the behavior of such a process would
be paramount to proving a complexity result for such a method. We believe that
the techniques that we have devised for this paper are broadly applicable and
foundational for performing complexity analyses of deterministically
constrained stochastic optimization methods.

## References

  * [1] A. S. Berahas, F. E. Curtis, M. J. O’Neill, and D. P. Robinson, A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians.  arXiv 2106.13015, 2021.
  * [2] A. S. Berahas, F. E. Curtis, D. P. Robinson, and B. Zhou, Sequential quadratic optimization for nonlinear equality constrained stochastic optimization, SIAM Journal on Optimization, 31 (2021), pp. 1352–1379.
  * [3] D. P. Bertsekas, Network optimization: continuous and discrete models, Athena Scientific Belmont, 1998.
  * [4] J. T. Betts, Practical methods for optimal control and estimation using nonlinear programming, SIAM, 2010.
  * [5] R. H. Byrd, G. Lopez-Calva, and J. Nocedal, A line search exact penalty method using steering rules, Mathematical Programming, 133 (2012), pp. 39–73.
  * [6] R. H. Byrd, J. Nocedal, and R. A. Waltz, Steering exact penalty methods for nonlinear programming, Optimization Methods and Software, 23 (2008), pp. 197–213.
  * [7] C. Chen, F. Tung, N. Vedula, and G. Mori, Constraint-aware deep neural network compression, in Proceedings of the European Conference on Computer Vision (ECCV), 2018, pp. 400–415.
  * [8] F. E. Curtis, A penalty-interior-point algorithm for nonlinear constrained optimization, Mathematical Programming Computation, 4 (2012), pp. 181–209.
  * [9] F. E. Curtis, H. Jiang, and D. P. Robinson, An adaptive augmented lagrangian method for large-scale constrained optimization, Mathematical Programming, 152 (2015), pp. 201–245.
  * [10] F. E. Curtis and D. P. Robinson, Exploiting negative curvature in deterministic and stochastic optimization, Mathematical Programming, 176 (2019), pp. 69–94.
  * [11] D. Davis and D. Drusvyatskiy, Stochastic model-based minimization of weakly convex functions, SIAM Journal on Optimization, 29 (2019), pp. 207–239.
  * [12] S. Ghadimi, G. Lan, and H. Zhang, Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization, Mathematical Programming, 155 (2016), pp. 267–305.
  * [13] S. P. Han and O. L. Mangasarian, Exact penalty functions in nonlinear programming, Math. Programming, 17 (1979), pp. 251–269, https://doi.org/10.1007/BF01588250, http://dx.doi.org/10.1007/BF01588250.
  * [14] E. Hazan and H. Luo, Variance-reduced and projection-free stochastic optimization, in International Conference on Machine Learning, PMLR, 2016, pp. 1263–1271.
  * [15] F. Kupfer and E. W. Sachs, Numerical solution of a nonlinear parabolic control problem by a reduced sqp method, Computational Optimization and Applications, 1 (1992), pp. 113–135.
  * [16] X. Li and F. Orabona, A high probability analysis of adaptive sgd with momentum, arXiv preprint 2007.14294, (2020).
  * [17] M. Mongeau and A. Sartenaer, Automatic decrease of the penalty parameter in exact penalty function methods, European Journal of Operational Research, 83 (1995), pp. 686–699.
  * [18] S. Na, M. Anitescu, and M. Kolar, An adaptive stochastic sequential quadratic programming with differentiable exact augmented lagrangians, arXiv preprint arXiv:2102.05320, (2021).
  * [19] Y. Nandwani, A. Pathak, Mausam, and P. Singla, A primal dual formulation for deep learning with constraints, in NeurIPS, 2019.
  * [20] J. Nocedal, A. Wächter, and R. A. Waltz, Adaptive barrier update strategies for nonlinear interior methods, SIAM Journal on Optimization, 19 (2009), pp. 1674–1693.
  * [21] J. Nocedal and S. J. Wright, Numerical optimization, Springer Science & Business Media, 2006.
  * [22] T. Rees, H. S. Dollar, and A. J. Wathen, Optimal solvers for pde-constrained optimization, SIAM Journal on Scientific Computing, 32 (2010), pp. 271–298.
  * [23] S. K. Roy, Z. Mhammedi, and M. Harandi, Geometry aware constrained optimization techniques for deep learning, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018, pp. 4460–4469.
  * [24] D. Stirzaker, Elementary probability, Cambridge University Press, 2003\.
  * [25] R. B. Wilson, A simplicial algorithm for concave programming, Ph. D. Dissertation, Graduate School of Bussiness Administration, (1963).

##  6 Proof of Theorem 1 (Deterministic Algorithm Complexity)

In this appendix, we prove Theorem 1, which states a worst-case complexity
bound for Algorithm 2.1 of [2]. We refer to quantities defined and employed in
the analysis in [2]. In particular, in this appendix, for all
$k\in\mathbb{N}$, we suppose that $g_{k}=\nabla f(x_{k})$ and
$d_{k}=u_{k}+v_{k}$ with $u_{k}\in\operatorname{Null}(J_{k})$ and
$v_{k}\in\operatorname{Range}(J_{k}^{\top})$ is the search direction computed
by solving the SQP subproblem with $g_{k}=\nabla f(x_{k})$. As seen in [2],
the convergence properties of Algorithm 2.1 in that paper are driven by
reductions in a model of the merit function in each iteration. Our first lemma
proves a useful lower bound for such a reduction.

######  Lemma 14.

Define
$(\kappa_{uv},\kappa_{H},\kappa_{v},\tau_{\min},\zeta,\sigma)\in(0,\infty)^{5}\times(0,1)$
as in [2] and let

$\hat{\kappa}:=\min\left\\{1,\frac{1}{(1+\kappa_{uv})\kappa_{v}\kappa_{H}^{2}}\right\\}\
\ \text{and}\ \
\tilde{\kappa}:=\tfrac{1}{4}\zeta\kappa_{uv}\kappa_{v}\hat{\kappa}.$ (45)

Then, for any $\varepsilon\in(0,1)$, if
$\|g_{k}+J_{k}^{\top}y_{k}\|>\varepsilon$ and/or
$\sqrt{\|c_{k}\|_{1}}>\varepsilon$, then

$\Delta
q(x_{k},\tau_{k},g_{k},H_{k},d_{k})\geq\min\left\\{\sigma\hat{\kappa},\tau_{\min}\tilde{\kappa}\right\\}\varepsilon^{2}.$
(46)

###### Proof.

Consider arbitrary $(\varepsilon,k)\in(0,1)\times\mathbb{N}$ such that
$\|g_{k}+J_{k}^{\top}y_{k}\|>\varepsilon$ and/or
$\sqrt{\|c_{k}\|_{1}}>\varepsilon$. Let us consider two cases. First, suppose
that $\|c_{k}\|_{1}>\hat{\kappa}\varepsilon^{2}$. Then, by [2, equation
(2.9)],

$\Delta
q(x_{k},\tau_{k},g_{k},H_{k},d_{k})\geq\tfrac{1}{2}\tau_{k}\max\\{d_{k}^{\top}H_{k}d_{k}0\\}+\sigma\|c_{k}\|_{1}\geq\sigma\|c_{k}\|_{1}\geq\sigma\hat{\kappa}\varepsilon^{2},$

which implies (46), as desired. Second, suppose that
$\|c_{k}\|_{1}\leq\hat{\kappa}\varepsilon^{2}\leq\varepsilon^{2}$, which by
the definition of $(\varepsilon,k)$ implies that
$\|g_{k}+J_{k}^{\top}y_{k}\|>\varepsilon$. It follows from this fact that
$\|d_{k}\|>\varepsilon/\kappa_{H}$; indeed, if
$\|d_{k}\|\leq\varepsilon/\kappa_{H}$, then by [2, equation (2.6) and
Assumption 2.4] one would find

$\|g_{k}+J_{k}^{\top}y_{k}\|=\|H_{k}d_{k}\|\leq\kappa_{H}\|d_{k}\|\leq\varepsilon,$

which is a contradiction. Hence, $\|d_{k}\|>\varepsilon/\kappa_{H}$, and by
[2, Lemma 2.9], it follows that
$\|v_{k}\|^{2}\leq\kappa_{v}\|c_{k}\|\leq\kappa_{v}\|c_{k}\|_{1}\leq\kappa_{v}\hat{\kappa}\varepsilon^{2}$,
which combined shows that

$\varepsilon^{2}/\kappa_{H}^{2}<\|d_{k}\|^{2}=\|u_{k}\|^{2}+\|v_{k}\|^{2}\leq\|u_{k}\|^{2}+\kappa_{v}\hat{\kappa}\varepsilon^{2}.$

From this fact and the definition of $\hat{\kappa}$, it follows that

$\|u_{k}\|^{2}>\frac{\varepsilon^{2}}{\kappa_{H}^{2}}-\kappa_{v}\hat{\kappa}\varepsilon^{2}\geq\frac{\varepsilon^{2}}{\kappa_{H}^{2}}\left(1-\frac{1}{(1+\kappa_{uv})}\right)=\frac{\kappa_{uv}\varepsilon^{2}}{(1+\kappa_{uv})\kappa_{H}^{2}}\geq\kappa_{uv}\kappa_{v}\hat{\kappa}\varepsilon^{2}\geq\kappa_{uv}\|v_{k}\|^{2},$

which along with [2, Lemma 2.10] implies
$d_{k}^{\top}H_{k}d_{k}\geq\tfrac{1}{2}\zeta\|u_{k}\|^{2}\geq\tfrac{1}{2}\zeta\kappa_{uv}\kappa_{v}\hat{\kappa}\varepsilon^{2}$.
Thus,

$\displaystyle\Delta q(x_{k},\tau_{k},g_{k},H_{k},d_{k})$
$\displaystyle\geq\tfrac{1}{2}\tau_{k}\max\\{d_{k}^{\top}H_{k}d_{k}0\\}+\sigma\|c_{k}\|_{1}\geq\tfrac{1}{4}\tau_{\min}\zeta\kappa_{uv}\kappa_{v}\hat{\kappa}\varepsilon^{2},$

which implies (46), as desired. ∎∎

We now prove Theorem 1, further details of which are provided in the statement
below.

######  Theorem 4.

Define $(\tau_{-1},f_{\text{\rm
low}},\alpha_{\min},\tau_{\min},\eta,\sigma)\in(0,\infty)^{4}\times(0,1)^{2}$
as in [2] and $(\hat{\kappa},\tilde{\kappa})\in(0,1]\times(0,\infty)$ as in
(45). Then, for any $\varepsilon\in(0,1)$, Theorem 1 holds with (6) given by

$\overline{K}_{\varepsilon}:=\left(\frac{\tau_{-1}(f_{0}-f_{\text{\rm
low}})+\|c_{0}\|_{1}}{\eta\alpha_{\min}\min\\{\sigma\hat{\kappa},\tau_{\min}\tilde{\kappa}\\}}\right)\varepsilon^{-2}.$

###### Proof.

To derive a contradiction, suppose (5) does not hold for all
$k\in\\{0,\dots,\overline{K}_{\varepsilon}\\}$. Then, along with Lemma 14 and
[2, equation (2.10) and Lemma 2.17], it follows for all such $k$ that

$\phi(x_{k}+\alpha_{k}d_{k},\tau_{k})-\phi(x_{k},\tau_{k})\leq-\eta\alpha_{k}\Delta
q(x_{k},\tau_{k},g_{k},H_{k},d_{k})\leq-\eta\alpha_{\min}\min\\{\sigma\hat{\kappa},\tau_{\min}\tilde{\kappa}\\}\varepsilon^{2}.$

By the definition of $\phi$, this means for all such $k$ that

$\tau_{k}f_{k+1}+\|c_{k+1}\|_{1}\leq\tau_{k}f_{k}+\|c_{k}\|_{1}-\eta\alpha_{\min}\min\\{\sigma\hat{\kappa},\tau_{\min}\tilde{\kappa}\\}\varepsilon^{2}.$

Summing this inequality for all
$k\in\\{0,\dots,\overline{K}_{\varepsilon}\\}$, one can deduce that

$\|c_{\overline{K}_{\varepsilon}+1}\|_{1}-\|c_{0}\|_{1}+\tau_{\overline{K}_{\varepsilon}}f_{\overline{K}_{\varepsilon}+1}-\tau_{0}f_{0}+\sum_{k=1}^{\overline{K}_{\varepsilon}}f_{k}(\tau_{k-1}-\tau_{k})\leq-(\overline{K}_{\varepsilon}+1)\eta\alpha_{\min}\min\\{\sigma\hat{\kappa},\tau_{\min}\tilde{\kappa}\\}\varepsilon^{2}.$

Since $\\{\tau_{k}\\}$ is monotonically nonincreasing,
$\|c_{\overline{K}_{\varepsilon}+1}\|_{1}\geq 0$, and $f_{k}\geq f_{\text{\rm
low}}$ for all $k\in\mathbb{N}$,

$-\|c_{0}\|_{1}+\tau_{\overline{K}_{\varepsilon}}f_{\text{\rm
low}}-\tau_{0}f_{0}+f_{\text{\rm
low}}(\tau_{0}-\tau_{\overline{K}_{\varepsilon}})\leq-(\overline{K}_{\varepsilon}+1)\eta\alpha_{\min}\min\\{\sigma\hat{\kappa},\tau_{\min}\tilde{\kappa}\\}\varepsilon^{2}.$

Rearranging this inequality, one arrives at the conclusion that

$\overline{K}_{\varepsilon}+1\leq\left(\frac{\tau_{0}(f_{0}-f_{\text{\rm
low}})+\|c_{0}\|_{1}}{\eta\alpha_{\min}\min\\{\sigma\hat{\kappa},\tau_{\min}\tilde{\kappa}\\}}\right)\varepsilon^{-2}\leq\left(\frac{\tau_{-1}(f_{0}-f_{\text{\rm
low}})+\|c_{0}\|_{1}}{\eta\alpha_{\min}\min\\{\sigma\hat{\kappa},\tau_{\min}\tilde{\kappa}\\}}\right)\varepsilon^{-2}\equiv\overline{K}_{\varepsilon},$

which is a contradiction. Therefore, one arrives at the desired conclusion
that Algorithm 2.1 yields an iterate satisfying (5) in at most
$\overline{K}_{\varepsilon}$ iterations. ∎∎

##  7 Proofs of Lemmas 9 and 10

In this appendix, we prove Lemmas 9 and 10. Toward this end, we prove for any
$\delta\in(0,1)$ with $\hat{\delta}$ as defined in (32) and
$\ell(s_{\max},\hat{\delta})$ as defined in (33), one finds

$\mathbb{P}\left[\sum_{i=0}^{k_{\max}}\mathbb{P}[{\cal T}_{i}<{\cal
T}_{i-1}|E,G_{[i-1]}]\leq\ell(s_{\max},\hat{\delta})+1\Bigg{|}E\right]\geq
1-\delta.$ (47)

We build to this result, ultimately proved as Lemma 5, with a series of
preliminary lemmas.

As our first preliminary result, we state a particular form of Chernoff’s
bound in the following lemma, which will prove instrumental in deriving (47).

######  Lemma 15.

For any $k\in\mathbb{N}$, let $\\{Y_{0},\dots,Y_{k}\\}$ be independent
Bernoulli random variables. Then, for any $s\in\mathbb{N}$ and
$\bar{\delta}\in(0,1)$, it follows that

$\mu:=\sum_{j=0}^{k}\mathbb{P}[Y_{j}=1]\geq\ell(s,\bar{\delta})\ \ \implies\ \
\mathbb{P}\left[\sum_{j=0}^{k}Y_{j}\leq s\right]\leq\bar{\delta}.$ (48)

###### Proof.

Suppose that $\mu\geq\ell(s,\bar{\delta})$. By the multiplicative form of
Chernoff’s bound, it follows for $\rho:=1-s/\mu$ (which is in the interval
$(0,1)$ by (48)) that

$\mathbb{P}\left[\sum_{j=0}^{k}Y_{j}\leq s\right]\leq
e^{-\tfrac{1}{2}\mu\rho^{2}}=e^{-\tfrac{1}{2}\mu(1-s/\mu)^{2}}.$

Hence, to prove the result, all that remains is to show that
$e^{-\tfrac{1}{2}\mu(1-s/\mu)^{2}}\leq\bar{\delta}$, i.e., that
$-\tfrac{1}{2}\mu(1-s/\mu)^{2}\leq\log(\bar{\delta})$. Using
$\log(\bar{\delta})=-\log(1/\bar{\delta})$, this inequality is equivalent to

$0\leq\tfrac{1}{2}\mu(1-s/\mu)^{2}-\log(1/\bar{\delta})=\tfrac{1}{2\mu}(\mu-s)^{2}-\log(1/\bar{\delta}),$

which holds if and only if $\mu^{2}-2\mu(s+\log(1/\bar{\delta}))+s^{2}\geq 0$.
Viewing the left-hand side of this inequality as a convex quadratic function
in $\mu$, one finds that the inequality holds as long as $\mu$ is greater than
or equal to the positive root of the quadratic, i.e.,

$s+\log(1/\bar{\delta})+\sqrt{(s+\log(1/\bar{\delta}))^{2}-s^{2}}=s+\log(1/\bar{\delta})+\sqrt{\log(1/\bar{\delta})^{2}+2s\log(1/\bar{\delta})}.$

This holds since $\mu\geq\ell(s,\bar{\delta})$; hence, the result is proved.
∎∎

Now, we turn our attention to proving (47). For any realization of a run of
the algorithm up to iteration $k\in[k_{\max}]$, let $w_{k}$ denote the number
of times that the merit parameter has been decreased up to the beginning of
iteration $k$ and let $\mkern 1.5mu\overline{\mkern-1.5mup}_{k}$ denote the
probability that the merit parameter is decreased during iteration $k$. The
_signature_ of a realization up to iteration $k\in\mathbb{N}$ is $(\mkern
1.5mu\overline{\mkern-1.5mup}_{0},\dots,\mkern
1.5mu\overline{\mkern-1.5mup}_{k},w_{0},\dots,w_{k})$, which encodes all of
the pertinent information regarding the behavior of the merit parameter
sequence up to the start of iteration $k$.

One could imagine using all possible signatures to define a tree whereby each
node contains a subset of all realizations of the algorithm. To construct such
tree, one could first consider the root node, which could be denoted by
$\tilde{N}(\mkern 1.5mu\overline{\mkern-1.5mup}_{0},w_{0})$, where $\mkern
1.5mu\overline{\mkern-1.5mup}_{0}$ is uniquely defined by the starting
conditions of our algorithm and $w_{0}=0$. All realizations of our algorithm
follow the same initialization, so $\mkern 1.5mu\overline{\mkern-1.5mup}_{0}$
and $w_{0}$ would be in the signature of every realization. Now, one could
define a node $\tilde{N}(\mkern 1.5mu\overline{\mkern-1.5mup}_{[k]},w_{[k]})$
at depth $k\in[k_{\max}]$ (where the root node has a depth of $0$) in the tree
as the set of all realizations of our algorithm for which the signature of the
realization up to iteration $k$ is $(\mkern
1.5mu\overline{\mkern-1.5mup}_{0},\dots,\mkern
1.5mu\overline{\mkern-1.5mup}_{k},w_{0},\dots,w_{k})$. One could then define
the edges in the tree by connecting nodes at adjacent levels, where node
$\tilde{N}(\mkern 1.5mu\overline{\mkern-1.5mup}_{[k]},w_{[k]})$ is connected
to node $\tilde{N}(\bar{p}_{[k]},\mkern
1.5mu\overline{\mkern-1.5mup}_{k+1},w_{[k]},w_{k+1})$ for any $\mkern
1.5mu\overline{\mkern-1.5mup}_{k+1}\in[0,1]$ and
$w_{k+1}\in\\{w_{k},w_{k}+1,\dots\\}$.

Unfortunately, the construction described in the previous paragraph may lead
to nodes in the tree representing realizations with probability zero
occurrence. In order to remedy this, we instead construct a tree where the
nodes contain all realizations whose probability signatures fall within
specified intervals. To define such intervals, consider arbitrary
$B\in\mathbb{N}\setminus\\{0\\}$ and let us restrict the sequence of values
$p_{[k]}$ used to define our nodes as those with

$p_{[k]}=(p_{0},\dots,p_{k})\in\left\\{0,\tfrac{1}{B},\dots,\tfrac{B-1}{B}\right\\}^{k+1}.$
(49)

For $p\in\\{0,1/B,\dots,(B-1)/B\\}$, these define the open probability
intervals $\iota(p)$ given by

$\iota(p)=\begin{cases}\left[p,p+\tfrac{1}{B}\right)&\text{if}\;p\in\left\\{0,\tfrac{1}{B},\dots,\tfrac{B-2}{B}\right\\},\\\
\left[\tfrac{B-1}{B},1\right]&\text{if}\;p=\tfrac{B-1}{B}.\end{cases}$

Now, we can construct our tree as follows. As before, first consider the root
node, which we denote by $N(p_{0},w_{0})$, where
$p_{0}\in\\{0,1/B,\dots,(B-1)/B\\}$ is uniquely defined by the starting
conditions of our algorithm so that $\mathbb{P}[{\cal
T}_{0}<\tau_{-1}|E]\in\iota(p_{0})$ and $w_{0}=0$. All realizations of our
algorithm follow the same initialization, so with
$\bar{p}_{0}=\mathbb{P}[{\cal T}_{0}<\tau_{-1}|E]$ one finds that
$\bar{p}_{0}\in\iota(p_{0})$ and $w_{0}$ are in the signature of every
realization. We define a node $N(p_{[k]},w_{[k]})$ at depth $k\in[k_{\max}]$
as the set of all realizations for which the signature of the realization at
iteration $k$ exactly matches $w_{[k]}$ and has probabilities that fall within
the intervals defined by $p_{[k]}$; i.e., a realization with signature
$(\mkern 1.5mu\overline{\mkern-1.5mup}_{[k]},w_{[k]})$ is a member of
$N(p_{[k]},w_{[k]})$ if and only if, for all $j\in[k]$, one finds that $\mkern
1.5mu\overline{\mkern-1.5mup}_{j}\in\iota(p_{j})$. The edges in the tree
connect nodes in adjacent levels, where $N(p_{[k]},w_{[k]})$ is connected to
$N(p_{[k]},p_{k+1},w_{[k]},w_{k+1})$ for any
$p_{k+1}\in\\{0,1/B,\dots,(B-1)/B\\}$ and
$w_{k+1}\in\\{w_{k},w_{k}+1,\dots\\}$.

Notationally, since the behavior of a realization of the algorithm up to
iteration $k\in\mathbb{N}$ is completely determined by the initial conditions
and the realization of $G_{[k-1]}$, we say that a realization described by
$G_{[k-1]}$ belongs in node $N(p_{[k]},w_{[k]})$ by writing that

$G_{[k-1]}\in N(p_{[k]},w_{[k]}).$

The initial condition, denoted for consistency as $G_{[-1]}\in
N(p_{0},w_{0})$, occurs with probability one. Based on the description above,
the nodes of our tree satisfy: For any node at a depth of $k\geq 2$, the event
$G_{[k-1]}\in N(p_{[k]},w_{[k]})$ occurs if and only if

$\displaystyle\mathbb{P}[{\cal T}_{k}<{\cal T}_{k-1}|E,G_{[k-1]}]$
$\displaystyle\in\iota(p_{k}),$ (50) $\displaystyle
S_{k-1}:=\sum_{i=0}^{k-1}{\cal I}[{\cal T}_{i}<{\cal T}_{i-1}]$
$\displaystyle=w_{k},$ $\displaystyle\text{and}\ \ G_{[k-2]}$
$\displaystyle\in N(p_{[k-1]},w_{[k-1]}).$

Let us now define certain important sets of nodes in the tree. First, let

${\cal L}_{\text{\rm
good}}:=\left\\{N(p_{[k]},w_{[k]}):\left(\sum_{i=0}^{k}p_{i}\leq\ell(s_{\max},\hat{\delta})+1\right)\land(w_{k}=s_{\max}\lor
k=k_{\max})\right\\}$

be the set of nodes at which the sum of the elements of $p_{[k]}$ is
sufficiently small and either $w_{k}$ has reached $s_{\max}$ or $k$ has
reached $k_{\max}$. Second, let

${\cal L}_{\text{\rm
bad}}:=\left\\{N(p_{[k]},w_{[k]}):\sum_{i=0}^{k}p_{i}>\ell(s_{\max},\hat{\delta})+1\right\\}$

be the nodes in the complement of ${\cal L}_{\text{\rm good}}$ at which the
sum of the elements of $p_{[k]}$ has exceeded the threshold
$\ell(s_{\max},\hat{\delta})+1$. Going forward, we restrict attention to the
tree defined by the root node and all paths from the root node that terminate
at a node contained in ${\cal L}_{\text{\rm good}}\cup{\cal L}_{\text{\rm
bad}}$. It is clear from this restriction and the definitions of ${\cal
L}_{\text{\rm good}}$ and ${\cal L}_{\text{\rm bad}}$ that this tree is finite
with the elements of ${\cal L}_{\text{\rm good}}\cup{\cal L}_{\text{\rm bad}}$
being leaves.

Let us now define relationships between nodes. The parent of a node is defined
as

$P(N(p_{[k]},w_{[k]}))=N(p_{[k-1]},w_{[k-1]}).$

On the other hand, the children of node $N(p_{[k]},w_{[k]})$ are defined as

$C(N(p_{[k]},w_{[k]}))=\begin{cases}\\{N(p_{[k]},p_{k+1},w_{[k]},w_{k+1})\\}&\text{if
$N(p_{[k]},w_{[k]})\not\in{\cal L}_{\text{\rm good}}\cup{\cal L}_{\text{\rm
bad}}$}\\\ \emptyset&\text{otherwise.}\end{cases}$

This ensures that paths down the tree terminate at nodes in ${\cal
L}_{\text{\rm good}}\cup{\cal L}_{\text{\rm bad}}$, making these nodes the
leaves of the tree. For convenience in the remainder of our discussions, let
$C(\emptyset)=\emptyset$.

We define the height of node $N(p_{[k]},w_{[k]})$ as the length of the longest
path from $N(p_{[k]},w_{[k]})$ to a leaf node, i.e., the height is denoted as

$h(N(p_{[k]},w_{[k]})):=\left(\min\\{j\in\mathbb{N}\setminus\\{0\\}:C^{j}(N(p_{[k]},w_{[k]}))=\emptyset\\}\right)-1,$

where $C^{j}(N(p_{[k]},w_{[k]}))$ is shorthand for applying the mapping
$C(\cdot)$ consecutively $j$ times. From this definition,
$h(N(p_{[k]},w_{[k]}))=0$ for all $N(p_{[k]},w_{[k]})\in{\cal L}_{\text{\rm
good}}\cup{\cal L}_{\text{\rm bad}}$.

Next, let us define two more sets of nodes that will be useful later. Let
$C_{dec}(N(p_{[k]},w_{[k]}))$ denote the set of children of
$N(p_{[k]},w_{[k]})$ such that the merit parameter decreases and let
$C_{\text{\rm dec}}^{c}(N(p_{[k]},w_{[k]}))$ denote set of children of
$N(p_{[k]},w_{[k]})$ such that it does not decrease, so

$\displaystyle C_{\text{\rm dec}}(N(p_{[k]},w_{[k]})):=\\{$ $\displaystyle
N(p_{[k]},p_{k+1},w_{[k]},w_{k+1}):$
$\displaystyle(N(p_{[k]},p_{k+1},w_{[k]},w_{k+1})\in C(N(p_{[k]},w_{[k]})))$
$\displaystyle\land(w_{k+1}=w_{k}+1)\\}$ (51)

and

$\displaystyle C_{\text{\rm dec}}^{c}(N(p_{[k]},w_{[k]})):=\\{$ $\displaystyle
N(p_{[k]},p_{k+1},w_{[k]},w_{k+1}):$
$\displaystyle(N(p_{[k]},p_{k+1},w_{[k]},w_{k+1})\in C(N(p_{[k]},w_{[k]})))$
$\displaystyle\land(w_{k+1}=w_{k})\\}.$ (52)

Finally, let us define the event $E_{\text{\rm bad},B}$ as the event that for
some $j\in[k_{\max}]$ one finds

$\left(\sum_{i=0}^{j}\mathbb{P}[{\cal T}_{i}<{\cal
T}_{i-1}|E,G_{[i-1]}]>\ell(s_{\max},\hat{\delta})+\tfrac{k_{\max}+1}{B}+1\right).$
(53)

With respect to our goal of proving (47), the event $E_{\text{\rm bad},B}$ is
of interest since it is the event that the given probabilities accumulated up
to iteration $j\in[k_{\max}]$ (and beyond) exceed the threshold found in (47)
plus a factor that is inversely proportional to $B$.

Let us now prove some properties of the leaf nodes.

######  Lemma 16.

For any $k\in[k_{\max}]$ and $(p_{[k]},w_{[k]})$ with
$N(p_{[k]},w_{[k]})\in{\cal L}_{\text{\rm good}}$, one finds

$\mathbb{P}[G_{[k-1]}\in N(p_{[k]},w_{[k]})\land E_{\text{\rm bad},B}|E]=0.$

On the other hand, for all $k\in[k_{\max}]$ and $(p_{[k]},w_{[k]})$ with
$N(p_{[k]},w_{[k]})\in{\cal L}_{\text{\rm bad}}$, one finds

$\displaystyle\mathbb{P}[G_{[k-1]}\in N(p_{[k]},w_{[k]})\land E_{\text{\rm
bad},B}|E]$
$\displaystyle\leq\hat{\delta}\prod_{i=1}^{k}\mathbb{P}\left[\mathbb{P}[{\cal
T}_{i}<{\cal
T}_{i-1}|E,G_{[i-1]}]\in\iota(p_{i})\big{|}E,S_{i-1}=w_{i},G_{[i-2]}\in
N(p_{[i-1]},w_{[i-1]})\right].$

###### Proof.

Consider an arbitrary index $k\in[k_{\max}]$ and an arbitrary pair
$(p_{[k]},w_{[k]})$ such that $N(p_{[k]},w_{[k]})\in{\cal L}_{\text{\rm
good}}$. By the definition of ${\cal L}_{\text{\rm good}}$, it follows that

$\sum_{i=0}^{k}p_{i}\leq\ell(s_{\max},\hat{\delta})+1.$ (54)

Since the maximum depth of a node is $k_{\max}$, it follows from (54) that

$\displaystyle\mathbb{P}\left[\sum_{i=0}^{k}\mathbb{P}[{\cal T}_{i}<{\cal