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,20,29]. 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 [9,25,30] (which includes the class of augmented Lagrangian methods) and sequential quadratic optimization (commonly known as SQP) methods [2,23]. 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. See [28] for further commentary on the advantages and disadvantages of penalty methods.
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 [32].
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 (i) one knows a threshold for the merit parameter below which knowledge of the exact gradient would not lead to a merit parameter decrease in any iteration (which, for one thing, is a threshold for the merit function to be exact [18]) and (ii) the algorithmic rule that might otherwise modify the merit parameter is skipped, the number of iterations required until the method generates a point at which first-order necessary conditions for optimality hold in expectation with accuracy ε ∈ (0, ∞) is O(ε -4 ). This is the type of result that one should expect, since this is the same bound proved to hold for a stochastic gradient method employed to solve an unconstrained nonconvex problem [14]. 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 due to the uncertainty of the behavior of the adaptive merit parameter sequence that is a consequence of the uncertainty due to the stochastic gradient estimates, and it does not reflect any uncertainty of the behavior of the method during situations in which the merit parameter sequence remains constant. A major challenge in our analysis is accounting for the transient behavior of the adaptive merit parameter sequence in the sense that our analysis accounts for the real possibilities that (i) different runs of the algorithm may decrease the merit parameter by varying amounts and (ii) it is not possible to bound the number of iterations until the merit parameter settles on a sufficiently small value. In other words, since our loose assumptions do not allow for one to presume that the algorithm experiences two distinct phases (e.g., one in which-over a bounded number of iterations-the merit parameter is reduced down to a threshold, then a second in which it remains fixed), our analysis must account for the possibility that the merit parameter is transient through any number of iterations, which leads to significant complications that are not present in the context of unconstrained optimization.
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 [14,16,26] and Frank-Wolfe type methods [19]. (One exception is a complexity bound proved for the SQP algorithm proposed in [23], 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.) After the initial release of this paper, the article [24] appeared that proposes an SQP method that uses stochastic estimates of the objective gradient and Hessian of the Lagrangian and computes search directions using a sketch-and-project framework. The algorithm in that paper does not use a merit function and requires that the stepsizes remain within prescribed intervals that are non-adaptive to the stochastic gradients. Under standard assumptions, that algorithm offers a worst-case complexity result that is comparable to the one we derive in this paper, as well as an asymptotic convergence rate. 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.
The algorithm that we consider is designed to solve problems of the form min x∈R n f (x) s.t. c(x) = 0, with f (x) = E[F(x, ω)], (1) where f : R n → R, c : R n → R m , ω is a random variable with associated probability space (Ω, F, P), F : R n × Ω → R, and E represents expectation with respect to P.
In particular, similar to [2], we make the following assumption.
The objective function f : R n → R is continuously differentiable and bounded below by f low ∈ R and the corresponding gradient function ∇ f : R n → R n is bounded and Lipschitz continuous with constant L ∈ (0, ∞). The constraint function c : R n → R m (where m ≤ n) and the corresponding Jacobian function J := ∇c : R n → R m×n are bounded, each gradient function ∇c i : R n → R n is Lipschitz continuous with constant γ i for all i ∈ {1, . . . , m}, and the singular values of J ≡ ∇c are bounded below and away from zero.
Defining the Lagrangian : R n × R m → R corresponding to (1) by (x, y) := f (x) + c(x) y, first-order primal-dual stationarity conditions for (1), which are necessary for optimality under Assumption 1, are given by 0 = ∇ x (x, y) ∇ y (x, y) = ∇ f (x) + ∇c(x)y c(x) .
(2)
We adopt the notation that • denotes the 2 -norm for vectors and the vector-induced 2 -norm for matrices. We denote by S n the set of n × n dimensional real symmetric matrices. The set of nonnegative integers is denoted as N := {0, 1, 2, . . . , }. For any integer k ∈ N, we use [k] to denote the subset of nonnegative integers up to k, namely, [k] := {0, . . . , k}. Correspondingly, to represent a set of vectors {v 0 , . . . , v k }, we define v [k] := {v 0 , . . . , v k }.
Given φ : R → R and ϕ : R → [0, ∞), we write
The algorithm that we analyze is iterative, generating in each realization a sequence {x k }. (See Sect. 4.1 for a complete description of the stochastic process generated by the algorithm.) We also append the iteration number to other quantities corresponding an iteration, e.g., f k := f (x k ) for all k ∈ N.
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 Sect. 3, followed by our main result and analysis, which are provided in Sect. 4. Finally, we provide concluding thoughts and mention future directions in Sect. 5.
Our algorithm of consideration is derived from Algorithm 3.1 in [2], which is proposed for the stochastic setting. As a precursor, Algorithm 2.1 was proposed in [2] for the deterministic setting, many of the features of which are used in Algorithm 3.1 in [2] for the stochastic setting. In Algorithm 2.1 in [2] for the deterministic setting, the kth search direction d k ∈ R n is computed by solving a 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 ∈ R n . This computation also results in a Lagrange multiplier vector y k ∈ R m . The subsequent iterate is set by
In particular, based on properties of the search direction d k , a value of the merit parameter τ k ∈ (0, τ k-1 ] is set by the algorithm, after which α k ∈ (0, ∞) is computed to ensure that φ(x k , τ k ) -φ(x k+1 , τ k ) is sufficiently positive. This description of the algorithm suffices for providing an outline of our main results; for further details about the algorithm that we analyze, see Sect. 3.
To motivate our main result for the stochastic setting, it is instructive to state a worstcase complexity bound for the deterministic algorithm. Such a result is the following; further details and a proof are provided in Appendix A. The approximate stationarity conditions in (3) have been defined for consistency between the primal and dual stationarity measures; the reason that this choice leads to such consistency is revealed in the analysis in Appendix A. [2] and suppose that Assumption 1 holds along with Assumption 2.4 from [2] (see also the similar Assumption 2 on page 8 for our stochastic setting). Let τ -1 ∈ R >0 be the initial value of the merit parameter sequence and let τ min ∈ (0, τ -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 ε ∈ (0, 1), there exists
in a number of iterations no more than
Theorem 1 is notable since it shows that Algorithm 2.1 in [2] has the standard worst-case iteration, function-evaluation, and derivative-evaluation complexity for a first-order-derivative-based algorithm for solving equality constrained optimization problems; see [8] for a comparable complexity bound for another "short-step" algorithm for solving equality constrained problems. That said, the O(ε -2 ) bound in Theorem 1 is not surprising. After all, such a complexity bound is well-known for gradient-based algorithms for solving unconstrained nonconvex optimization problems as well. 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. There are ways for achieving improved worst-case complexity if higher-order derivatives are employed in a constrained-optimization algorithm (see, e.g., [7,13,17]), but the use of such higherorder derivatives-especially in the stochastic setting-is outside of our scope.
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 13 and the beginning of the proof of Theorem 4) that the improvement in the merit function from any iterate that is not ε-stationary (see (3)) is at least proportional to min{1, τ min }ε -2 , even if the current value of the merit parameter is greater than τ 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 devised new analytical approaches that confront the fact that {τ 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 27. 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 8. We also assume, as is common for stochastic gradient methods, that the stochastic gradient estimates are unbiased with variance bounded by M ∈ (0, ∞), along with some related assumptions; see Assumption 3 on page 14. Furthermore, our analysis conditions on the occurrence of an event that we call E (see (15)); this event captures situations in which, over a total of k max + 1 ∈ N iterations, the merit parameter is reduced at most s max ∈ [k max ] times and the merit parameter is bounded below by τ min ∈ (0, ∞). Under these conditions, our main complexity result shows that, within k max + 1 iterations, it holds with probability 1 -δ ∈ (0, 1) that the algorithm generates x k * ∈ R n corresponding to which there exists an associated Lagrange multiplier
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 = O(log(k max )) (more on this below), it holds with probability 1 -δ that the algorithm requires at most O(ε -4 ) iterations to generate x k * with corresponding
The probability in this result is with respect to the distribution of the stochastic gradients conditioned on the occurrence of the event E.
The first three quantities on the right-hand side of the convergence rate, namely, in (5a), 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 [14,16,26]. The final term in (5b), 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 τ min , then one could set τ -1 = τ 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 (5a) (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 the merit parameter sequence is provably bounded below, which in turn means that s max is bounded by a value that is independent from k max + 1 (at least as long as k max is sufficiently large relative to τ -1 /τ min ); this follows from a deterministic lower bound on τ 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 Sect. 4.5 that if the distributions of the stochastic gradient estimates are sub-Gaussian, then with probability 1-δ one finds that s max = O(log(log( k max δ ))), meaning that our proved convergence rate is not ruined by the term in (5b). There are certainly other special cases in which similar types of relationships between s max and k max hold, but for our purposes we simply provide the example in Sect. 4.5.
For ease of reference, in this section we present Algorithm 3.1 from [2] (slightly modified, as explained at the end of this section), 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 ∈ N by solving
where g k is a stochastic gradient estimate at x k and H k ∈ S n is chosen independently from g k . Under Assumption 1 and the following Assumption 2 (that we make throughout the remainder of the paper), the solution of ( 6) can be obtained from the unique solution of the linear system
, where for all k ∈ N the matrix H k ∈ S n is chosen independently from g k . In addition, there exists ζ ∈ R >0 such that, for all k ∈ N, the matrix
After computation of (d k , y k ), the remainder of the kth 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
and the reduction function Δq :
Specifically, in order to ensure in iteration k that τ k ≤ τ k-1 and
holds for all τ ≤ τ k , the algorithm sets, for user-defined σ ∈ (0, 1), the value
and then sets, for some τ ∈ (0, 1), the merit parameter value
Then, for use in the stepsize computation (as motivated in [2]) it sets
for some ξ ∈ (0, 1), which, for one thing, ensures ξ k ≤ ξ trial k . The last component in the kth iteration is to set the stepsize, the magnitude of which is controlled by a prescribed sequence {β k } ⊂ (0, 1], which is employed in the following projection interval that is used in the stepsize computation:
where Proj(• | B) represents the projection operator onto the interval B ⊂ R. As in other stochastic-gradient-based methods, the convergence properties of the method depend on properties of {β k }, which in many analyses is considered to be a constant or diminishing sequence. We establish our complexity result for the case of constant
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 ) 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., [14]. It amounts to uniform sampling over the iterates when constant {β 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 [12].
Require:
Compute (d k , y k ) as the solution of (7) 3: Set
We begin our complexity analysis by describing the algorithm as a stochastic process (Sect. 4.1), then formalizing the assumptions that we make about the stochastic gradient estimates (Sect. 4.2). We then state, in some cases in a slightly modified form, some key lemmas from [2] that are needed for our analysis (Sect. 4.3). Our generic complexity result, which has been outlined in Sect. 2, is then stated and proved (Sect. 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 (Sect. 4.5). Finally, we conclude this section by outlining a form of our generic complexity result that relaxes one of our minor simplifying assumptions (Sect. 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 ∈ N, we express d k = u k + v k , where u k ∈ Null(J k ) and v k ∈ Range(J k ). 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 ∈ N, conditioned on the event that the algorithm has reached x k as the kth iterate, if the true gradient ∇ 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
which may be decomposed as
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
This definition of τ trial,true k guarantees that, for any τ ≤ τ trial,true k , one finds
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
where, for all k ∈ 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 T k , ratio parameter Ξ k , and stepsize A k . For all k ∈ N, a realization of the corresponding element of this process has been denoted
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
where, for all k ∈ N, the random variables are: the normal search direction component V k , the tangential search direction component U k , the true search direction D true k , the true tangential search direction component U true k , the true Lagrange multiplier estimate Y true k , and the true trial merit parameter T trial,true k . For all k ∈ N, a realization of the corresponding element of this process has been denoted
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 ∈ N the random variable S k represents the number of merit parameter decreases up to the end of the kth iteration, i.e., the number of iterations in which
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 G k denote the σ -algebra generated by the random variables {G 0 , . . . , G k-1 }, a realization of which (along with all initial conditions of the algorithm, including X 0 = x 0 ) determines the realizations of
For completeness, let G 0 = σ (x 0 ). As a result, {G k } k≥0 is a filtration.
Our analysis presumes certain good behavior of the sequences of merit and ratio parameters that are set adaptively by the algorithm. Formally, given
, our main result characterizes the worst-case behavior of Algorithm 1 conditioned on the event denoted as
which we define as the event such that
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 {Ξ k } is constant over all iterations is not actually essential for our analysis; rather, it is made for the sake of simplicity. Indeed, in Sect. 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 {Ξ 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 {Ξ 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, since stochasticity in the gradient estimates can cause the merit parameter to vanish, even in settings when the merit parameter would remain bounded below in the deterministic algorithm. That said, in Sect. 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 τ 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 τ min ) that s max exists and satisfies
That said, for simplicity and generality in our analysis, we define s max as a quantity that is decoupled from the above (conservative) inequality.
In summation, while our analysis requires the existence of a lower bound for the merit parameter sequence, and correspondingly an upper bound on the number of potential decreases in the merit parameter, it does not presume other convenient behavior of the merit parameter sequence. For example, our analysis does not presume that the merit parameter sequence eventually settles on a sufficiently small value in a number of iterations that can be bounded in a convenient manner. Rather, our analysis respects the stochastic, transient behavior of the merit parameter sequence that one finds in the actual behavior of the algorithm in practice. We have strived to derive a complexity bound that, under relatively loose assumptions in the highly stochastic regime, matches (up to logarithmic factors) in a constrained setting the results that are considered stateof-the-art for the unconstrained setting, even though the algorithm needs to discover for itself, in an adaptive manner, an appropriate balance between the objective function and constraint violation measure. Given our focus on event E, we now introduce the filtration defined by
where, for all k ∈ N, we use
Here and throughout the remainder of the paper, we let
) denote probability (respectively, expectation) conditioned on F k , which encodes information up to the start of iteration k ∈ N, i.e., we define
Our analysis assumes the following about the stochastic gradient estimates. Such an assumption, namely, that conditioned on the filtration one has that the stochastic gradient is unbiased and has bounded variance, is common in analyses of stochastic optimization methods.
In addition, there exists
Observe that (19b) follows from (18) if there exists p ∈ (0, 1] such that, for any
After all, in this setting with andZ c k representing the complement of Z k , one finds along with Jensen's inequality that
so (19b) holds with M τ = √ M/ p. Such a p exists, 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 τ ∈ (0, 1] such that, for all k ∈ [k max ], one finds
Similar to [2, Proposition 3.16], Assumption 4 allows us to prove that, with high probability, the number of iterations in which T k > T trial,true k is not too large. In [2, Example 3.17], it was shown that the inequality in this assumption holds with p τ = 1 2 when, conditioned on having reached a realized iterate x k , the stochastic gradient G k has a Gaussian distribution. We show in Sect. 4.5 that this result can be extended to other settings as well.
In this section, we state key preliminary results from [2] that are needed for our analysis. It is important to note that these results are written in [2] in the context of conditioning, for all k ∈ N, on a particular realization of the algorithm up to the beginning of iteration k, which is different from our setting in which we condition on F k . That said, one finds that these results from [2] carry over, with nearly the same line of arguments, to our setting. After all, for any random variable X that is F k -measurable and any random variable
This property, combined with the arguments found in [2], is sufficient to prove the results of this section, so we state them without proof. By [2, Lemma 2.10], there exists
, where ζ is defined in Assumption 2. Correspondingly, let us define
The following Lemmas 1 and 2 show that there exists a common quantity that both bounds from above the squared-norm of the true search direction plus the constraint violation and bounds from below the reduction in the model of the merit function. Essentially, the combination of these results shows that the search direction offers sufficient decrease relative to its norm. Here, Lemma 1 is stated using a different norm for c(X k ) than in [2, Lemma 2.11]. The result holds in the same manner (with a different value for κ Ψ ) due to the norm equivalence between • and • 1 in R m . We state the result in this manner for consistency with the measure used in our final results.
Lemma 1 ([2, Lemma 2.11]) Let Assumptions 1 and 2 hold. Then, there exists κ Ψ ∈ R >0 such that, for all k ∈ [k max ], the true search direction and constraint violation satisfy
Lemma 2 ([2, Lemma 2.12]) Let Assumptions 1 and 2 hold. Then, there exists κ q ∈ R >0 such that, for all k ∈ [k max ] and
The next lemma shows that the reduction in the merit function is at least a reduction in the model of the merit function defined with respect to the true gradient and true search direction, except for two terms that may be attributed to the noise in the stochastic gradient estimates. Observe that the requirement in the lemma that
can be enforced in practice, despite the fact that {Ξ k } and {T k } evolve randomly. After all, since {Ξ k } and {T k } are monotonically nonincreasing, one need only choose β ∈ R >0 sufficiently small such that
Lemma 3 ([2, Lemma 3.7]) Let Assumptions 1 and 2 hold and suppose that
The next two lemmas bound (in expectation) differences and products between stochastic and true quantities. These bounds are critical in the analysis.
, and
Proof Except for the last inequality, the result follows from the assumptions and (the proof of) [2, Lemma 3.8]. As for the last inequality, observe as in [2, Lemma 3.8] that
as desired.
Lemma 5 ([2, Lemma 3.9]) Let Assumptions 1, 2, and 3 hold. Then, for all k ∈ [k max ], it follows that
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. 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 F k , this term is the product of three correlated random variables:
A critical aspect of our derived bound is that we isolate a term for the event when
, since this happens to be an event that complicates subsequent aspects of our analysis. In Lemma 9, we prove a highprobability bound on the sum of the probabilities of the occurrences of this event over a run of the algorithm. 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 T trial,true k ≥ T k for all k ∈ 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 { T k } (not generated by the algorithm) such that Tk := min{T k , T trial,true
In Lemmas 7 and 8, we analyze behaviors of the algorithm with respect to this auxiliary sequence, and in Lemma 9 we provide a high-probability bound on the total number of iterations in which T trial,true k < T k may occur. (More precisely, Lemma 9 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 F k . Conditioned on F k , let us define three events:
-
. We now derive an upper bound on the final term in (21). In the following lemma, we use, given k ∈ [k max ], the stepsize values
The first value here represents a lower bound on the smallest stepsize that may be computed in the event that T k < T k-1 , whereas the second value is the smallest stepsize that may be computed in the event that T k = T k-1 ; it is easily verified that α < min,k < A = min,k . Hence, A 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 κ d ∈ R >0 be defined by Lemma 4. Then, for all k ∈ [k max ], and with the stepsizes (α < min,k , A = min,k , A max,k ) defined as in (22), one finds that
and for ease of exposition, let us denote
] for all j ∈ {1, 2, 3}. By the Law of Total Expectation, the fact that 0 < τ min ≤ T k ≤ T k-1 under E, (20), and the definitions of α < min,k , A = min,k , and A max,k , one finds that
Using this inequality, the Law of Total Expectation, (20), and Lemma 4 (E k [D k ] = D true k ), one obtains three upper bounds by adding and subtracting like terms:
From averaging these upper bounds And the definition of A max,k , one obtains
This bound can be rewritten as follows. By the Law of Total Expectation, Lemma 4, and
and along with Lemma 4 one finds that
In addition, Lemma 4 also yields that
Combining ( 23), ( 24), (25), and ( 26), the desired result follows.
Now, for all k ∈ [k max ], let us define
Lemma 7 Suppose that Assumptions 1, 2, and 3 hold and let κ d ∈ R >0 be defined by Lemma 4. Then, for all k ∈ [k max ], one finds that
Proof By the definition of Δq in ( 8), one has that
Now, for simplicity of notation, define
Let E Q denote the event that Q k ≥ 0 occurs and let E c Q denote the event that Q k < 0 occurs. By the Law of Total Expectation and ( 20), one has that
Therefore, by the Law of Total Probability, Lemma 5, (20), Jensen's inequality, and convexity of max{•, 0}, it follows that
and by similar reasoning one finds that
Averaging these two upper bounds, one finds that
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, (20), Jensen's inequality, and concavity of the square root over R ≥0 ,
In addition, by the Cauchy-Schwarz inequality, the proof of Lemma 4, Assumption 3, (20), and since
By the Law of Total Expectation, (30), and ( 31), it follows that
and by a similar argument, one finds that
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 Tk < T k .
Let Assumptions 1, 2, and 3 hold and let κ d ∈ R >0 be defined by Lemma 4.
Then, for all k ∈ [k max ], with (α < min,k , A = min,k , A max,k ) defined as in (22) and Tk defined in (27), one finds that
and
Proof Under the stated assumptions and definitions, one finds that
Hence, under the stated assumptions, it follows from the stated lemma and definitions, along with the definition of Δq in (8) and equation (20), that
and, along with
which together are the desired conclusions.
Our next lemma is a critical element of our analysis. For any s ∈ N and δ ∈ (0, 1), let
and
This lemma provides a bound on two quantities with high probability, the first of which is the sum of the probabilities of the occurrences of event E k,3 over the run of the algorithm.
The following lemma also provides a bound on the cardinality of the random index set,
By the manner in which {T k }, {T trial,true k }, and { Tk } are defined, this set is always a superset of the iterations in which Tk < T k ; hence, by bounding the cardinality of (34), one bounds the cardinality of the set of iterations in which Tk < T k , which is needed for our main theorem. The reason that we consider the set K τ in (34) is the fact that the event T trial,true k < T k-1 and its complement are members of F k ; in other words, the occurrence of the event defined by this inequality does not depend on G k . Lemma 9 Suppose Assumptions 1, 2, and 3 hold. Then, for any δ ∈ (0, 1),
In addition, suppose Assumption 4 holds as well. Then, for any δ ∈ (0, 1), (35) holds and
Proof This result is proved in Appendix B.
Our proof of Lemma 9 uses a novel tree structure for analyzing the behavior of the adaptive merit parameter sequence in the context of an algorithm for solving constrained stochastic optimization problems; see also [1,Appendix B] for the use of such a tree structure in a different context. Starting with the initialization at a root node, each subsequent level of the tree captures different sets of realizations of the algorithm in terms of the number of decreases of the merit parameter and the probability that the parameter will be decreased further in the next iteration. The leaves of the tree represent either bad situations when the sum of the probabilities that the merit parameter could decrease exceeds a critical threshold (defined with respect to the function defined in (33)) or good situations in which this sum remains below the threshold and the maximum number of merit parameter decreases has occurred and/or the iteration limit has been reached. Essentially, in this manner, bad situations are when the algorithm repeatedly has a high probability of decreasing the merit parameter, but does not do so a sufficient number of times. The proof of Lemma 9 ultimately relies on applications of Chernoff's bound-employed with respect to independent random variables that are defined carefully with respect to the non-independent random variables in the stochastic process defined by the algorithm-to show that the probability is small that the algorithm ends at a bad leaf node.
We are now prepared to prove a convergence rate result.
Theorem 2 Suppose Assumptions 1, 2, 3, and 4 hold, let s max ∈ N \ {0}, let κ d ∈ R >0 be defined by Lemma 4, define
where
and, for all k ∈ [k max ], let Tk be defined as in (27). Then, for any δ ∈ (0, 1), it follows with K * having a discrete uniform distribution over [k max ] and δ and defined as in (32) and (33) that, with probability at least 1 -δ,
Proof First, consider arbitrary k ∈ [k max ]. By Lemmas 3 and 6 and equation ( 20), one has that
Our next aim is to prove that, roughly speaking, one in fact finds that
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 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 Tk (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
where the final inequality follows due to the fact that (A max + θβ)β ≤ A min holds by the definitions of β, γ , 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,τ be the event that T trial,true
and let E c k,τ be the event that T trial,true
Observe that E k,τ and E c k,τ only depend on the history of the algorithm prior to iteration k and thus the σ -algebras generated by E k,τ and E c k,τ are included in F k . Therefore, by [15, Theorem 4.1.13], for any random variable Z , we have
Hence, we can use Lemma 7-and Lemma 8 as well, which is used below-even if one conditions on the occurrence of E k,τ or of E c k,τ . Let us now consider E c k,τ and E k,τ in turn. Conditioning on E c k,τ , one finds from (39), ( 41), (42), and the fact that
On the other hand, one finds from (39), ( 41), (42), and Lemma 8 that
Hence, by the laws of total probability and expectation, one finds that
123
Next, by Lemma 9, it follows that, with probability at least 1 -δ, one finds
Taking the total expectation (conditioned on E) of the above inequality,
The left-hand side of this inequality satisfies
Since {T k } is a non-decreasing sequence and f (X k ) ≥ f min , one finds
Thus, from (44), it follows that
Combining this with (43) and dividing by A min k max k=0 β, one obtains that
Hence, by the definitions of K * and β, 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 (2).
Hence, the complexity bound described in Sect. 2.2 (see (5)) holds.
Proof The result follows by Lemma 1, Lemma 2, Theorem 2, and ( 13), which implies that ∇ f
The worst-case complexity bound in Sect. 2.2 follows by combining this result with the definitions of κ E 3 , κ Δq,1 , κ Δq,2 , and Lemma 21 in Appendix C. This result, as well as that of Theorem 2, is proven under the assumption that s max ≥ 1. When s max = 0, this result simplifies to a deterministic complexity bound with the terms dependent on s max and δ omitted. Under the condition s max = 0, the proof follows by noting that
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 [14].
In this section, we show that if each stochastic gradient is unbiased with a symmetric, sub-Gaussian distribution and (for simplicity) the ratio parameter sequence remains constant, then the conditions involved in Assumptions 3 and 4 and the event E in (15) occur with high probability. Specifically, this is shown under Assumptions 1, 2, and Assumption 5 below, where it is important to note that Assumption 5 conditions on elements of G k , not F k . Overall, our analysis in this section shows that if one makes Assumptions 1, 2, and Assumption 5, then one can be assured that the conditions required for Assumptions 3 and 4 and the event E occur with high probability, meaning that if, in turn, one makes Assumptions 3 and 4 and assumes that E occurs, then our main results of the prior subsection hold.
and the random vectors
Our first lemma shows that, under Assumptions 1, 2, and 5, an inequality of the form in Assumption 4 holds.
Proof Consider arbitrary k ∈ [k max ]. Let Z k be a basis for the null space of J (X k ), which under Assumption 1 is a matrix in R n× (n-m) . Then, let
Hence, when conditioned on G k , the random variables
are equivalent in distribution by Assumption 5. Therefore,
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 [21, Lemma 5].
Lemma 11 Suppose Assumption 5 holds. Then, for any δ ∈ (0, 1),
We conclude by showing that, under Assumptions 1, 2, and 5, the conditions involved in Assumption 3 and E occur with high probability.
Lemma 12 Suppose that Assumptions 1, 2, and 5 hold, let
all k ∈ N (whose existence follows from Assumption 1 and [2, Lemma 2.9]), let κ c be an upper bound for c(X k ) 2 for all k ∈ N (whose existence follows from Assumption 1), and define
Then, for any δ ∈ (0, 1), it follows with probability at least 1 -δ that the conditions in Assumption 3 and event E hold with
and s max = min
Proof By Lemma 11, the event considered in that lemma holds with probability at least 1 -δ. Hence, for the purposes of this proof, suppose that event holds. By Jensen's inequality, convexity of exp(•), and (45), it follows that
In addition, it follows from the event in Lemma 11 that ( 19) holds with M τ 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 11 that T k ≥ τ min and T trial,true k ≥ τ min for all k ∈ [k max ] for τ min as stated in the lemma. Second, it follows from the stated value of τ min and ( 16) that |{k ∈ [k max ] : T k < T k-1 }| ≤ s max for s max as stated in the lemma. Finally, the desired behavior of {Ξ k } follows from Assumption 5.
In this section, we state a convergence rate result, which can be translated to a worstcase complexity result, that relaxes the definition of the event E considered in prior sections. In particular, we remove the assumption that
Importantly, it has been proved in [2, Lemma 3.5] that, under our remaining assumptions, there still exists
Therefore, by the manner in which the ratio parameter sequence is set, it follows that there exists a maximum number of k ∈ [k max ] such that Ξ k < Ξ k-1 . Denoting this limit as r max ∈ N, it follows (for the same reasons as the bound for s max in ( 16)) that
To formalize our new assumption, we define
as the event such that
Since {Ξ k } is bounded below deterministically, this event is identical to the event E defined in (15), except that one may have ξ -1 > ξ min .
For the purposes of this section, redefining
our analysis of this case considers the following replacement of Assumption 3. Like in Assumption 3, the latter part of the assumption only needs to involve probabilities and expectations conditioned on the event that one or the other parameter decreases, i.e., T k < T k-1 and/or Ξ k < Ξ k-1 .
Assumption 6 There exists
In addition, there exist
We claim that this assumption holds with high probability under Assumption 5 (without the assumption that Ξ k = ξ min for all k ∈ [k max ]), a result that can be derived by modification of the techniques used in Sect. 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 ∇ f (x k ) (D k -D true k ) 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 similar, but tedious extension of the results in Sect. 4.4, we simply state the extension of (5) to this case without proof.
Theorem 3 Suppose that Assumptions 1, 2, 4, and 6 hold and consider arbitrary δ ∈ (0, 1). Then, within k max + 1 iterations, it holds with probability at least 1 -δ that the algorithm generates x k * ∈ R n corresponding to which there exists an associated Lagrange multiplier y true k * ∈ R m such that
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 an 1 -norm exact merit function, 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,22], adaptive augmented Lagrangian methods [11], adaptive barrier methods [27], and penalty-interior point methods [10].
In addition, many constrained optimization algorithms generate (often unconstrained) subproblems defined by an auxiliary 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 [28]. In cases when the objective is stochastic, this auxiliary 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.
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 ∈ N, we suppose that
is the search direction computed by solving the SQP subproblem with g k = ∇ 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.
as in [2] and let
Then, for any ε ∈ (0, 1),
Let us consider two cases. First, suppose that c k 1 > κε 2 . Then, by [2, equation (2.9)],
which implies (47), as desired. Second, suppose that c k 1 ≤ κε 2 ≤ ε 2 , which by the definition of (ε, k) implies that g k + J k y k > ε. It follows from this fact that
From this fact and the definition of κ, it follows that
which implies (47), as desired.
We now prove Theorem 1, further details of which are provided in the statement below.
Theorem 4 Define (τ -1 , f low , α min , τ min , η, σ ) ∈ (0, ∞) 4 × (0, 1) 2 as in [2] and ( κ, κ) ∈ (0, 1] × (0, ∞) as in (46). Then, for any ε ∈ (0, 1), Theorem 1 holds with (4) given by
Proof To derive a contradiction, suppose (3) does not hold for all k ∈ {0, . . . , K ε }.
Then, along with Lemma 13 and [2, equation (2.10) and Lemma 2.17], it follows for all such k that
By the definition of φ, this means for all such k that
Summing this inequality for all k ∈ {0, . . . , K ε }, one can deduce that
Since {τ k } is monotonically nonincreasing, c K ε +1 1 ≥ 0, and
Rearranging this inequality, one arrives at the conclusion that
which is a contradiction. Therefore, one arrives at the desired conclusion that Algorithm 2.1 yields an iterate satisfying (3) in at most K ε iterations.
In this appendix, we prove Lemma 9. Toward this end, we prove for any δ ∈ (0, 1) with δ as defined in (32) and (s max , δ) as defined in (33), one finds
We build to this result, ultimately proved as Theorem 5, with a series of preliminary lemmas.
As our first preliminary result, we state a particular form of Chernoff's bound [31] in the following lemma, which will prove instrumental in deriving (48).
For any k ∈ N, let {Y 0 , . . . , Y k } be independent Bernoulli random variables. Then, for any s ∈ N and δ ∈ (0, 1), it follows that
Proof Suppose that μ ≥ (s, δ). By the multiplicative form of Chernoff's bound, it follows for ρ := 1s/μ (which is in the interval (0, 1) by ( 49)) that
Hence, to prove the result, all that remains is to show that e -1 2 μ(1-s/μ) 2 ≤ δ, i.e., that
which holds if and only if μ 2 -2μ(s + log(1/ δ)) + s 2 ≥ 0. Viewing the left-hand side of this inequality as a convex quadratic function in μ, one finds that the inequality holds as long as μ is greater than or equal to the positive root of the quadratic, i.e.,
This holds since μ ≥ (s, δ); hence, the result is proved. Now, we turn our attention to proving (48). For any realization of a run of the algorithm up to iteration k ∈ [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 p k denote the Notationally, since the behavior of the algorithm up to iteration k ∈ N is determined by the initial conditions and stochastic gradients in G [k-1] , we write
to denote the event that the signature of the algorithm up to k is a member of N ( p [k] , w [k] ). The initial condition, denoted for consistency as G [-1] ∈ 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 ≥ 2, the event
and
where I[•] denotes the indicator function of any given event.
Let us now define certain important sets of nodes in the tree. First, let
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 . A node in this set is of interest since, due to the iteration and/or merit parameter decrease limit having been reached, the probability is zero that a certain "bad" event can occur over all realizations with signatures that are members of the node; see Lemma 15 on page 38. Second, let
be the nodes in the complement of L good at which the sum of the elements of p [k] has exceeded the threshold (s max , δ) + 1. A node in this set is of interest since, due to this threshold having been exceeded, all realizations with signatures that are members of this node correspond to poor behavior of the algorithm (and there is no need to consider the behavior of the algorithm beyond this point). 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 L good ∪ L bad . It is clear from this restriction and the definitions of L good and L bad that this tree is finite with the elements of L good ∪ L bad being leaves.
Let us now define relationships between nodes. The parent of a node is defined as
On the other hand, the children of node N ( p [k] , w [k] ) are defined as
This ensures that paths down the tree terminate at nodes in L good ∪ L bad , making these nodes the leaves of the tree. For convenience in the remainder of our discussions, let
We define the height of node
) as the length of the longest path from
) to a leaf node, i.e., the height is denoted as
Next, let us define two more sets of nodes that will be useful later. Let
) such that the merit parameter decreases and let
) such that it does not decrease, so
and
Finally, let us define the event E bad,B as the event that for some j ∈
With respect to our goal of proving (48), the event E bad,B is of interest since it is the event that the given probabilities accumulated up to iteration j ∈ [k max ] (and beyond) exceed the threshold found in (48) plus a factor that is inversely proportional to B.
Let us now prove some properties of the leaf nodes.
On the other hand, for all k ∈ [k max ] and ( p
Proof Consider an arbitrary index k ∈ [k max ] and an arbitrary pair
By the definition of L good , it follows that
Since the maximum depth of a node is k max and the gap between the discrete values in (50) is 1 B , it follows along with (55) that
Therefore, for any j ∈ {1, . . . , k}, one finds from conditional probability that
In addition, (54) cannot hold for j = 0 since (s max , δ)+1 > 1. Hence, along with the conclusion above, it follows that E bad,B does not occur when a signature up to iteration j ∈ {1, . . . , k} falls into a node along any path from the root node to
). Now, by the definition of L good , at least one of w k = s max or k = k max holds. Let us consider each case in turn. If k = k max , then it follows by the preceding arguments that
Otherwise, if w k = s max , then it follows by the definition of the event E that P[T i < T i-1 |F i ] = 0 for all i ∈ {k, . . . , k max }, and therefore the equation above again follows. Overall, it follows that
) ∧ E bad,B |E] = 0, as desired. Next, we remark that
Hence, using the initial condition that G
Our goal is to bound (56). Toward this end, define
which by the definition of w [k] form a partition of {1, . . . , k}. For any i ∈ I dec ,
On the other hand, for any i ∈ I c dec ,
Thus, it follows that the latter term in (56) satisfies
Now let us bound this term. By the definition of L bad , one finds that
In addition, by the definition of s max , it follows that w k ≤ s max for all k ∈ [k max ], from which it follows that |I dec | ≤ s max . Now, let {Z 0 , . . . , Z k-1 } be independent Bernoulli random variables such that, for all i ∈ {0, . . . , k -1}, one has
By (57), it follows from the definition of these random variables that k-1 i=0 P[Z i = 1] ≥ (s max , δ). Then, it follows by Lemma 14 and the preceding argument that
Combining this with (56), the desired conclusion follows.
Next, we present a lemma about nodes in the sets defined in (52) and (53). The lemma essentially states that a certain probability of interest, defined as the product of probabilities along a path to a child node, can be reduced to a product of probabilities to the child's parent node by partitioning the childen into those at which a merit parameter decrease has occurred and children at which a merit parameter decrease has not occurred.
and, similarly, one finds that
where by the definitions of C dec and C c dec it follows that the value of w k+1 in the sum in the former equation is one greater than the value of w k+1 in the sum in the latter equation.
)), all elements in the latter sum have S k = w k+1 = w k + 1, meaning that the sum is exhaustive over all possible outcomes with the same conditions, and hence the sum is 1.
The proof of the second desired conclusion follows in the same manner with C c dec in place of C dec and S k = w k+1 = w k in place of S k = w k+1 = w k + 1.
Next, we derive a result for certain nodes containing realizations with w k = s max -1.
Proof By the supposition that
in which case the desired conclusion follows from Lemma 15. With this base case being established, we now prove the result by induction. Suppose that the result holds for all ( p
)) ≤ j for some j ∈ N. Our goal is to show that the same statement holds with j replaced by j +1. For this purpose, consider arbitrary ( p
Observe that by the definition of the child operators C, C dec , and C c dec , it follows that
Since w k = s max -1, it follows from the definition of C dec that for any ( p k+1 , w k+1 ) with
By the definition of s max , this implies that P[T k+1 < T k |F k+1 ] = 0, so p k+1 = 0. In addition, since
) ∈ L good . Consequently, from above and Lemma 15, one finds
)). Therefore, by the induction hypothesis and the result of Lemma 16, it follows that
which completes the proof.
Using the preceding lemma as a base case, we now perform induction on the difference s max -w k to prove a similar result for arbitrary s max .
The result holds in this case according to Lemma 15 since one finds that
∈ L good and s max -w k = 1, the result follows from Lemma 17. Hence, to prove the remainder of the result by induction, one may assume that it holds for all ( p
)) ≤ t for some t ∈ N, and s max -w k = r for some r ∈ N\{0}, and show that it holds for all ( p (59) ,w [k] ) = t + 1 > r -1 = s max -w k-1 -1, which combined with (59) proves the result for this case as well.
We now prove our first main result of this section.
Theorem 5 For any δ ∈ (0, 1) with δ as defined in (32) and (s max , δ) as defined in (33), one finds that (48) holds.
Proof First, consider the case where s max = 0. Then, by the definition of s max ,
for all k = [k max ], so the result holds trivially. Now, let s max ∈ N \ {0}. By construction of our tree and the definitions of L good and L bad , one finds that h(N ( p 0 , w 0 )) ≤ k max . In addition, by the definition of s max , s max -1 < k max , so min{s max -w 0 -1, h(N ( p 0 , w 0 ))} = s max -1 ≥ 0. Consider arbitrary B ∈ N \ {0} (see (54)). By Lemma 18 and (32), Next, we present some preliminary results that are required to prove the second statement of Lemma 9. Recall the random index set K τ defined in (34). Our next lemma shows a property about any iteration k ∈ [k max ] in which k ∈ K τ .
Proof In any iteration where T trial,true k < T k-1 , it follows that T trial,true k < ∞, so
and thus
By the definition of T k , if
in an iteration such that T trial,true k < T k-1 , then
meaning that T k < T k-1 . Observe that the event k ∈ K τ only depends on the history of the algorithm prior to iteration k and thus the σ -algebra generated by k ∈ K τ is included in F k . Therefore, by [15,Theorem 4.1.13], for any random variable Z , we have
Therefore, with 1( Ẽ) denoting the indicator of event Ẽ, it follows from Assumption 4 that
as desired.
The previous lemma guarantees that in any iteration in which T trial,true k < T k-1 , the probability is at least p τ that the merit parameter decreases. By the scheme for setting Proof By the law of total probability,
Now, similar to the previous lemma, we note that k ∈ K τ only depends on the history of the algorithm prior to iteration k. Denoting the indicator of the event k ∈ K τ as 1(k ∈ K τ ), it follows by Lemma 19 that