Randomized methods for design of uncertain systems: Sample complexity and sequential algorithms

arXiv:1304.0678v2 [cs.SY] 21 Jul 2014 Randomized Methods for Design of Uncertain Systems: Sample Complexity and Sequential Algorithms T. Alamo a, R. Tempo b, A. Luque a, D.R. Ramirez a aDepartamento de Ingenier´ıa de Sistemas y Autom´atica, Universidad de Sevilla, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla. Spain bCNR-IEIIT, Politecnico di Torino, Corso Duca degli Abruzzi 24, Torino 10129, Italy Abstract In this paper, we study randomized methods for feedback design of uncertain systems. The first contribution is to derive the sample complexity of various constrained control problems. In particular, we show the key role played by the binomial distribution and related tail inequalities, and compute the sample complexity. This contribution significantly improves the existing results by reducing the number of required samples in the randomized algorithm. These results are then applied to the analysis of worst-case performance and design with robust optimization. The second contribution of the paper is to introduce a general class of sequential algorithms, denoted as Sequential Probabilistic Validation (SPV). In these sequential algorithms, at each iteration, a candidate solution is probabilistically validated, and corrected if necessary, to meet the required specifications. The results we derive provide the sample complexity which guarantees that the solutions obtained with SPV algorithms meet some pre-specified probabilistic accuracy and confidence. The performance of these algorithms is illustrated and compared with other existing methods using a numerical example dealing with robust system identification. Key words: randomized and probabilistic algorithms, uncertain systems, sample complexity 1 Introduction The use of randomized algorithms for systems and control has matured thanks to the considerable research efforts made in recent years. Key areas where we have seen convincing developments include uncertain and hybrid systems [37,41]. A salient feature of this approach is the use of the theory of rare events and large deviation inequalities, which suitably bound the tail of the probability distribution. These inequalities are crucial in the area of statistical learning theory [39], which has been utilized for feedback design of uncertain systems [42]. Design in the presence of uncertainty is of major relevance in different areas, including mathematical optimization and robustness [7,31]. The goal is to find a feasible solution which is optimal in some sense for all possible uncertainty instances. Unfortunately, the related semi-infinite optimization problems are often NP-hard Email addresses: [email protected] (T. Alamo), [email protected] (R. Tempo), [email protected] (A. Luque), [email protected] (D.R. Ramirez). (examples of NP-hard problems in systems and control can be found in [8,9]), and this may seriously limit their applicability from the computational point of view. There are two approaches to resolve this NP-hard issue. The first approach is based on the computation of deterministic relaxations of the original problem, which are usually polynomial time solvable. However, this might lead to overly conservative solutions [35]. An alternative is to assume that a probabilistic description of the uncertainty is available. Then, a randomized algorithm may be developed to compute, in polynomial time, a solution with probabilistic guarantees [37,41]. Stochastic programming methods [34] are similar in spirit to the methods studied in this paper and take advantage that, for random uncertainty, the underlying probability distributions are known or can be estimated. The goal is to find a solution that is feasible for almost all possible uncertainty realizations and maximizes the expectation of some function of the decisions variables. The field of probabilistic methods [38,14,37] has received a growing attention in the systems and control community. Two complementary approaches, non-sequential and sequential, have been proposed. A classical ap- Preprint submitted to Automatica 22 July 2014 proach for non-sequential methods is based upon statistical learning theory [39], [41]. Subsequent work along this direction includes [27], [42], [43], [2], [18]. Furthermore, in [4], [3] and [29] the case in which the design parameter set has finite cardinality is analyzed. The advantage of these methods is that the problem under attention may be non-convex. For convex optimization problems, a non-sequential paradigm, denoted as the scenario approach, has been introduced in [11] and [12], see also [16], [17], [10], [4] for more advanced results, and [33], [40] for recent developements in the areas of stochastic hybrid systems and multi-stage optimization, respectively. Finally, we refer to [23] for a randomized approach to solve approximate dynamic programming. In non-sequential methods, the original robustness problem is reformulated as a single optimization problem with sampled constraints, which are randomly generated. A relevant feature of these methods is that they do not require any validation step and the sample complexity is defined a priori. The main result of this line of research is to derive explicit lower bounds to the required sample size. However, the obtained explicit sample bounds can be overly conservative because they rely on a worst-case analysis and grow (at least linearly) with the number of decision variables. For sequential methods, the resulting iterative algorithms are based on stochastic gradient [15], [32], ellipsoid iterations [26], [30]; or analytic center cutting plane methods [13], [44], see also [5,19] for other classes of sequential algorithms. Convergence properties in finite-time are one of the focal points of these papers. Various control problems have been solved using these sequential randomized algorithms, including robust LQ regulators [32], switched systems [28] and uncertain linear matrix inequalities (LMIs) [15]. Sequential methods are often used for uncertain convex feasibility problems because the computational effort at each iteration is affordable. However, they have been studied also for non-convex problems, see [2], [25]. The common feature of most of these sequential algorithms is the use of the validation strategy presented in [30] and [22]. The candidate solutions provided at each iteration of these algorithms are tested using a validation set which is drawn according to the probability measure associated to the uncertainty. If the candidate solution satisfies the design specifications for every sampled element of this validation set, then it is classified as probabilistic solution and the algorithm terminates. The main point in this validation scheme is that the cardinality of the validation set increases very mildly at each iteration of the algorithm. The strategy guarantees that, if a probabilistic solution is obtained, then it meets some probabilistic specifications. In this paper, we derive the sample complexity for various analysis and design problems related to uncertain systems. In particular we provide new results which guarantee that the tail of the binomial distribution is bounded by a pre-specified value. These results are then applied to the analysis of worst-case performance and constraint violation. With regard to design problems, we consider the special cases of finite families and robust convex optimization problems. This contribution improves the existing results by reducing the number of samples required to solve the design problem. We remark that the results we have obtained are fairly general and the assumptions on convexity and on finite families appear only in Section 4 which deals with probabilistic analysis and design. The second main contribution of this paper is to propose a sequential validation scheme, denoted as Sequentially Probabilistic Validation (SPV), which allows the candidate solution to violate the design specifications for one (or more) of the members of the validation set. The idea of allowing some violations of the constraints is not new and can be found, for example, in the context of system identification [6], chance-constrained optimization [17] and statistical learning theory [2]. This scheme makes sense in the presence of soft constraints or when a solution satisfying the specifications for all the admissible uncertainty realizations can not be found. In this way, we improve the existing results with this relaxed validation scheme that reduces the chance of not detecting the solution even when it exists. Furthermore, we also show that a strict validation scheme may not be well-suited for some robust design problems. This paper is based on the previous works of the authors [4] and [1]. However, some results are completely new (Property 4) and others (Theorem 2, Property 1 and Property 3 and their proofs) are significant improvements of the preliminary results presented in the conference papers. Furthermore, the unifying approach studied here, which combines sample complexity results with SPV algorithms, was not present in previous papers. Finally, the numerical example in Section 8, which compares various approaches available in the literature, is also new. The rest of the paper is organized as follows. In the next section, we first introduce the problem formulation. In Section 3, we provide bounds for the binomial distribution which are used in Section 4 to analyze the probabilistic properties of different schemes involving randomization. In Section 5, we introduce the proposed family of probabilistically validated algorithms. The sample complexity of the validating sets is analyzed in Section 6. A detailed comparison with the validation scheme presented in [30] is provided in Section 7. A numerical example where different schemes are used to address a robust identification problem is presented in Section 8. The paper ends with a section of conclusions and an appendix which contains some auxiliary properties and proofs that are used in the previous sections. 2 2 Problem Statement We assume that a probability measure PrWover the sample space Wis given. Given W, a collection of N independent identically distributed (i.i.d.) samples w = {w(1),...,w(N)}drawn from Wbelongs to the Cartesian product WN=W × · · · × W (Ntimes). Moreover, if the collection w of Ni.i.d. samples {w(1),...,w(N)} is generated from Waccording to the probability measure PrW, then the multisample w is drawn according to the probability measure PrWN. The scalars η∈(0,1) and δ∈(0,1) denote probabilistic parameters called accuracy and confidence, respectively. Furthermore, ln(·) is the natural logarithm and e is the Euler number. For x∈R,x≥0, ⌊x⌋denotes the largest integer smaller than or equal to x;⌈x⌉denotes the smallest integer greater or equal than x. For α > 1, ξ(α) := ∞ X k=1 1 kα denotes the Riemann zeta function. In a robustness problem, the controller parameters and auxiliary variables are parameterized by means of a decision variable vector θ, which is denoted as design parameter and is restricted to a set Θ. Furthermore, the uncertainty wis bounded in the set Wand represents one of the admissible uncertainty realizations. We also consider a binary measurable function g: Θ × W → {0,1}and a real measurable function f: Θ × W → Rwhich helps to formulate the specific design problem under attention. More precisely, the binary function g: Θ × W → {0,1}, is defined as g(θ, w) := (0 if θmeets design specifications for w 1 otherwise, where design specifications are, for example, H∞norm bounds on the sensitivity function, see specific examples in [37], or the numerical example in Section 8. Given θ∈Θ, the constraint g(θ, w) = 0 is satisfied for a subset of W. This concept is rigorously formalized by means of the notion of probability of violation, which is now introduced. Definition 1 [probability of violation] Consider a probability measure PrWover Wand let θ∈Θbe given. The probability of violation of θfor the function g: Θ×W → {0,1}is defined as E(θ) := PrW{g(θ, w) = 1 }. Using this notion we study the robust optimization problem min θ∈ΘJ(θ) subject to E(θ)≤η, (1) where J: Θ →(−∞,∞) is a measurable function which represents the controller performance and η∈(0,1) is a probabilistic accuracy. Given accuracy η∈(0,1) and confidence δ∈(0,1), the main point of the probabilistic approach is to design an algorithm such that any probabilistic solution ˆ θobtained by running the algorithm, satisfies E(ˆ θ)≤ηwith probability no smaller than 1−δ. Even in analysis problems when θ∈Θ is given, it is often very hard to compute the exact value of the probability of violation E(θ) because this requires to solve a multiple integral with a usually non-convex domain of integration. However, we can approximate its value using the concept of empirical mean. For given θ∈Θ, and multisample w = {w(1),...,w(N)}drawn according to the probability measure PrWN, the empirical mean of g(θ, w) with respect to w is defined as ˆ E(θ, w) := 1 N N X i=1 g(θ, w(i)). Clearly, the empirical mean ˆ E(θ, w) is a random variable. Since g(·,·) is a binary function, ˆ E(θ, w) is always within the closed interval [0,1]. The power of randomized algorithms stems from the fact that they can approximately solve non-convex design problems (with no-violation) of the type min θ∈ΘJ(θ) subject to g(θ, w) = 0,for all w∈ W.(2) In this setting, we draw Ni.i.d. samples {w(1),...,w(N)} from Waccording to probability PrWand solve the sampled optimization problem min θ∈ΘJ(θ) subject to g(θ, w(ℓ)) = 0, ℓ = 1,...,N. (3) Since obtaining a global solution to this problem is still a difficult task in general, in this paper we analyze the probabilistic properties of any suboptimal solution. Furthermore, if at most mviolations of the Nconstraints are allowed, the following sampled problem can be used to obtain a probabilistic relaxation to the original problem (2) min θ∈ΘJ(θ) subject to N X ℓ=1 g(θ, w(ℓ))≤m. (4) 3 Randomized strategies to solve problems (3) and (4) have been studied in [2], see also [37]. In order to analyze the probabilistic properties of any feasible solution to problem (4), we introduce the definitions of nonconforming feasible set and probability of failure. Definition 2 [non-conforming feasible set] Given N, the integer mwhere 0≤m < N,η∈(0,1),g: Θ× W → {0,1}and multisample w = {w(1),...,w(N)}, drawn according to the probability measure PrWN, the non-conforming feasible set Θ(w, η, m)is defined as Θ(w, η, m) := {θ∈Θ : ˆ E(θ, w) ≤m Nand E(θ)> η }. Definition 3 [probability of failure] Given N, the integer mwhere 0≤m < N,η∈(0,1) and g: Θ × W → {0,1}, the probability of failure, denoted by p(N, η, m)is defined as p(N, η, m) := PrWN{Θ(w, η, m) is not empty}. The probability p(N, η, m) defined here is slightly different than the probability of one-sided constrained failure introduced in [2]. We notice that the non-conforming feasibility set is empty with probability 1−p(N, η, m). This means that every feasible solution θ∈Θ to problem (4) satisfies E(θ)≤ηwith probability 1−p(N, η, m). Given the confidence parameter δ∈(0,1), the objective is to obtain explicit expressions yielding a minimum number of samples Nsuch that p(N, η, m)≤δ. 3 Sample complexity for the binomial distribution In this section, we provide bounds for the binomial distribution which are used in Section 4. Given a positive integer Nand a nonnegative integer m,m≤N, and η∈(0,1), the binomial distribution function is given by B(N, η, m) := m X i=0 N i!ηi(1 −η)N−i. The problem we address in this section is the explicit computation of the sample complexity, i.e. a function ˜ N(η, m, δ) such that the inequality B(N, η, m)≤δholds for any N≥˜ N(η, m, δ), where δ∈(0,1). As it will be illustrated in the following section, the inequality B(N, η, m)≤δplays a fundamental role in probabilistic methods. Although some explicit expressions are available, e.g. the multiplicative and additive forms of Chernoff bound [20], the results obtained in this paper are tuned on the specific inequalities stemming from the problems described in Section 4. The following technical lemma provides an upper bound for the binomial distribution B(N, η, m). Lemma 1 Suppose that η∈(0,1) and that the nonnegative integer mand the positive integer Nsatisfy m≤N. Then, B(N, η, m)≤amη a+ 1 −ηN,∀a≥1. Proof: The proof of the lemma follows from the following sequence of inequalities: B(N, η, m) = am m X i=0 N i!a−mηi(1 −η)N−i ≤am m X i=0 N i!a−iηi(1 −η)N−i ≤am N X i=0 N i!η ai (1 −η)N−i =amη a+ 1 −ηN . ✷ We notice that each particular choice of a≥1 provides an upper bound for B(N, η, m). When using Lemma 1 to obtain a specific sample complexity, the selected value for aplays a significant role. Lemma 2 Given δ∈(0,1) and the nonnegative integer m, suppose that the integer Nand the scalars η∈(0,1) and a > 1satisfy the inequality N≥1 ηa a−1ln 1 δ+mln a.(5) Then, m < N and B(N, η, m)≤δ. Proof: We first prove that if inequality (5) is satisfied then m < N. Since η∈(0,1) and δ∈(0,1), (5) implies N > a a−1ln am. Next, we notice that d daa a−1ln a=−1 (a−1)2ln a+1 a−1. Since ln a < a −1 for every a > 1, it follows that d daa a−1ln a>−1 (a−1)2(a−1) + 1 a−1= 0. Using this fact, we conclude that a (a−1) ln ais a strictly increasing function for a > 1. This means that N > a a−1ln am≥lim ˆa→1ˆa ˆa−1ln ˆam=m. 4 We now prove that (5) guarantees that am(η a+1−η)N≤ δ. The inequality (5) can be rewritten as Nη a−1 a≥ln 1 δ+mln a. (6) Since x≤ − ln (1 −x) for every x∈(0,1), and η(a−1 a)∈ (0,1), from inequality (6), we obtain a sequence of inequalities −Nln 1−ηa−1 a≥ln 1 δ+mln a ln δ≥mln a+Nln 1−ηa−1 a δ≥amη a+ 1 −ηN . We have therefore proved that inequality (5) implies m≤ Nand am(η a+ 1 −η)N≤δ. The claim of the property follows directly from Lemma 1. ✷ Obviously, the best sample size bound is obtained taking the infimum with respect to a > 1. However, this requires to solve numerically a one-dimensional optimization problem for given η,δand m. We observe that a suboptimal value can be immediately obtained setting aequal to the Euler constant, which yields the sample complexity N≥1 ηe e−1ln 1 δ+m.(7) Since e e−1<1.59, we obtain N≥1.59 ηln 1 δ+m, which is (numerically) a significant improvement of the bound given in [10] and other bounds available in the literature [14]. We also notice that, if m > 0 then the choice a= 1 + ln 1 δ m+s2ln 1 δ m provides a less conservative bound at the price of a more involved expression [4]. Based on extensive numerical computations for several values of η,δand mwe conclude that this bound is very close to the “optimal” one. Note, however, that the optimal value can be obtained numerically using the Lambert Wfunction [21]. In the next corollary, we present another more involved sample complexity bound which improves (7) for some values of the parameters. Corollary 1 Given δ∈(0,1) and the nonnegative integer m, suppose that the integer Nand the scalar η∈(0,1) satisfy the inequality N≥1 η m+ ln 1 δ+r2mln 1 δ!.(8) Then, m < N and B(N, η, m)≤δ. The proof of this corollary is shown in the appendix. 4 Sample complexity for probabilistic analysis and design We now study some problems in the context of randomized algorithms where one encounters inequalities of the form B(N, η, m)≤δ. In particular, we show how the results of the previous section can be used to derive explicit sample size bounds which guarantee that the probabilistic solutions obtained from different randomized approaches meet some pre-specified probabilistic properties. In Subsection 4.2 we derive bounds on p(N, η, m) when Θ consists of a finite number of elements. On the other hand, if Θ consists of an infinite number of elements, a deeper analysis involving statistical learning theory is needed [37], [41]. In Subsection 4.3 we study the probabilistic properties of the optimal solution of problem (3) under the assumption that g(θ, w) = 0 is equivalent to f(θ, w)≤0, where f: Θ × W → Ris a convex function with respect to θin Θ. In this case, the result is not expressed in terms of probability of failure because it applies only to the optimal solution of problem (3), and not to every feasible solution. 4.1 Worst-case performance analysis We recall a result shown in [36] for the probabilistic worst-case performance analysis. Theorem 1 Given the function f: Θ×W → Rand ˆ θ∈ Θ, consider the multisample w = {w(1),...,w(N)}drawn from WNaccording to probability PrWNand define γ= max ℓ=1,...,N f(ˆ θ, w(ℓ)).If N≥ln 1 δ ln 1 1−η , then PrW{w∈ W :f(ˆ θ, w)> γ} ≤ ηwith probability no smaller than 1−δ. The proof of this statement can be found in [36] and is based on the fact that PrW{w∈ W :f(ˆ θ, w)> γ} ≤ η with probability no smaller than 1−(1−η)N. Therefore, it suffices to take Nsuch that B(N, η, 0) = (1−η)N≤δ. 5 4.2 Finite families for design We consider the non-convex sampled problem (4) for the special case when Θ consists of a set of finite cardinality nC. As a motivation, we study the case when, after an appropriate normalization procedure, the design parameter set is rewritten as ˆ Θ = {θ∈Rnθ:kθk∞≤1}. Suppose also that a gridding approach is adopted. That is, for each component θj,j= 1, . . . , nθof the design parameters θ∈Rnθ, only nCjequally spaced values are considered. That is, θjis constrained into the set Υj={ −1 + 2(t−1) (nCj−1) :t= 1, . . . , nCj}.With this gridding procedure, the following finite cardinality set Θ = {[θ1,...,θnθ]T:θj∈Υj, j = 1,...,nθ}is obtained. We notice that the cardinality of the set is nC=Qnθ j=1 nCj. Another situation in which the finite cardinality assumption holds is when a finite number of random samples in the space of design parameter are drawn according to a given probability, see e.g. [24,42]. The following theorem states the relation between the binomial distribution and the probability of failure under this finite cardinality assumption. Theorem 2 Suppose that the cardinality of Θis no larger than nC,nC>0,η∈(0,1) and m < N. Then, p(N, η, m)< nCB(N, η, m). Proof: If there is no element in Θ with probability of violation larger than η, then the non-conforming feasible set is empty for every multisample w and p(N, η, m) = 0< nCB(N, η, m). Suppose now that the subset of Θ of elements with probability of violation larger than ηis not empty. Denote {θ(1), θ(2),...,θ(˜n)}such a set. In this case, given a multisample w, the non-conforming feasible set is not empty if and only if the empirical mean is smaller or equal than m Nfor at least one of the elements of this set. Therefore p(N, η, m) = PrWN{Θ(w, η, m) is not empty} = PrWN{min 1≤k≤˜n ˆ E(θ(k),w) ≤m N} ≤ ˜n X k=1 PrWN{ˆ E(θ(k),w) ≤m N} = ˜n X k=1 B(N, E(θ(k)), m) < ˜n X k=1 B(N, η, m) = ˜nB(N, η, m). Notice that the last inequality is due to the fact that E(θ(k))> η,k= 1,...,˜nand that the binomial distribution is a strictly decreasing function of ηif m < N (see Property 4 in the Appendix). To conclude the proof it suffices to notice that ˜n≤nC.✷ Consider now the optimization problem (4). It follows from Lemma 2 that to guarantee that every feasible solution ˆ θ∈Θ satisfies E(ˆ θ)≤ηwith probability no smaller than 1 −δ, it suffices to take N > m such that nCB(N, η, m)≤δ, where nCis an upper bound on the cardinality of Θ. As it will be shown next, the required sample complexity in this case grows with the logarithm of nC. This means that we can consider finite families with high cardinality and still obtain very reasonable sample complexity bounds. Theorem 3 Suppose that the cardinality of Θis no larger than nC. Given the nonnegative integer m, η∈(0,1) and δ∈(0,1), if N≥inf a>1 1 ηa a−1ln nC δ+mln a(9) then p(N, η, m)≤δ. Moreover, if N≥1 ηm+ ln nC δ+r2mln nC δ then p(N, η, m)≤δ. Proof: From Lemma 2 we have that p(N, η, m)≤δ provided that m < N and B(N, η, m)≤δ nC. The two claims of the property now follow directly from Lemma 2 and Corollary 1 respectively. ✷ From the definition of p(N, η, m) and Theorem 3 we conclude that if one draws Ni.i.d. samples {w(1),...,w(N)} from Waccording to probability PrW, then with probability no smaller than 1 −δ, all the feasible solutions to problem (4) have a probability of violation no larger than η, provided that the cardinality of Θ is upper bounded by nCand the sample complexity is given by N≥1 ηm+ ln nC δ+r2mln nC δ. We remark that taking aequal to the Euler constant in (9), the following sample size bound N≥1 ηe e−1ln nC δ+m is immediately obtained from Theorem 3. If m > 0 then a suboptimal value for ais given by a= 1 + ln nC δ m+r2ln nC δ m. 6 4.3 Optimal robust optimization for design In this subsection, we study the so-called scenario approach for robust control introduced in [12]. To address the semi-infinite optimization problem (2), we solve the randomized optimization problem (3). That is, we generate Ni.i.d. samples {w(1),...,w(N)}from Waccording to the probability PrWand then solve the following sampled optimization problem: min θ∈ΘJ(θ) subject to g(θ, w(ℓ)) = 0, ℓ = 1,...,N. (10) We consider here the particular case in which J(θ) = cTθ, the constraint g(θ, w) = 0 is convex in θfor all w∈ Wand the solution of (10) is unique. These assumptions are now stated precisely. Assumption 1 [convexity] Let Θ⊂Rnθbe a convex and closed set. We assume that J(θ) := cTθand g(θ, w) := (0if f(θ, w)≤0, 1otherwise where f: Θ × W → [−∞,∞]is convex in θfor every fixed value of w∈ W. Assumption 2 [feasibility and uniqueness] For all possible multisample extractions {w(1),. . .,w(N)}, the optimization problem (10) is always feasible and attains a unique optimal solution. Moreover, its feasibility domain has a nonempty interior. Uniqueness may be assumed essentially without loss of generality, since in case of multiple optimal solutions one may always introduce a suitable tie-breaking rule [12]. We now state a result that relates the binomial distribution to the probabilistic properties of the optimal solution obtained from (10). See [16,10,17]. Lemma 3 Let Assumptions 1 and 2 hold. Suppose that N,η∈(0,1) and δ∈(0,1) satisfy the inequality nθ−1 X i=0 N i!ηi(1 −η)N−i≤δ. (11) Then, with probability no smaller than 1−δ, the optimal solution ˆ θNto the optimization problem (10) satisfies the inequality E(ˆ θN)≤η. We now state an explicit sample size bound, which improves upon previous bounds, to guarantee that the probability of violation is smaller than ηwith probability at least 1 −δ. Theorem 4 Let Assumptions 1 and 2 hold. Given η∈ (0,1) and δ∈(0,1), if N≥inf a>1 1 ηa a−1ln 1 δ+ (nθ−1) ln a(12) or N≥1 η ln 1 δ+ (nθ−1) + r2(nθ−1) ln 1 δ!(13) then, with probability no smaller than 1−δ, the optimal solution ˆ θNto the optimization problem (10) satisfies the inequality E(ˆ θN)≤η. Proof: From Lemma 3 it follows that it suffices to take N such that B(N, η, nθ−1) ≤δ. Both inequalities (12) and (13) guarantee that B(N, η, nθ−1) ≤δ(see Lemma 2 and Corollary 1 respectively). This completes the proof. ✷ Taking aequal to the Euler constant in (12), we obtain N≥1 ηe e−1ln 1 δ+nθ−1 which improves the bound given in [10] and other bounds available in the literature [14]. More precisely, the constant 2 appearing in [10] is reduced to e (e−1) ≈1.59, which is (numerically) a substantial improvement for small values of η. If nθ>1 a suboptimal value for ais given by a= 1 + ln 1 δ nθ−1+s2ln 1 δ nθ−1. 5 Sequential algorithms with probabilistic validation In this section, we present a general family of randomized algorithms, which we denote as Sequential Probabilistic Validation (SPV) algorithms. The main feature of this class of algorithms is that they are based on a probabilistic validation step. This family includes most of the sequential randomized algorithms that have been presented in the literature and are discussed in the introduction of this paper. Each iteration of an SPV algorithm includes the computation of a candidate solution for the problem and a subsequent validation step. The results provided in this paper are basically independent of the particular strategy chosen to obtain candidate solutions. Therefore, in the following discussion we restrict ourselves to a generic 7 candidate solution. The accuracy η∈(0,1) and confidence δ∈(0,1) required for the probabilistic solution play a relevant role when determining the sample size of each validation step. The main purpose of this part of the paper is to provide a validation scheme which guarantees that, for given accuracy ηand confidence δ, all the probabilistic solutions obtained running the SPV algorithm have a probability of violation no larger than η with probability no smaller than 1 −δ. We enumerate each iteration of the algorithm by means of an integer k. We denote by mkthe number of violations that are allowed at the validation step of iteration k. We assume that mkis a function of k, that is, mk=m(k) where the function m:N→Nis given. We also denote by Mkthe sample size of the validation step of iteration k. We assume that Mkis a function of k,ηand δ. That is, Mk=M(k, η, δ) where M:N×R×R→Nhas to be appropriately designed in order to guarantee the probabilistic properties of the algorithm. In fact, one of the main contributions of [30,22] is to provide this function for the particular case mk= 0 for every k≥1. The functions m(·) and M(·,·,·) are denoted as level function and cardinality function respectively. We now introduce the structure of an SPV algorithm (i) Set accuracy η∈(0,1) and confidence δ∈(0,1) equal to the desired levels. Set kequal to 1. (ii) Obtain a candidate solution ˆ θkto the robust optimization problem (1). (iii) Set mk=m(k) and Mk=M(k, η, δ). (iv) Obtain validation set Vk={v(1),...,v(Mk)}drawing Mki.i.d. validation samples from Waccording to probability PrW. (v) If Mk P ℓ=1 g(ˆ θk, v(ℓ))≤mk, then ˆ θkis a probabilistic solution. (vi) Exit if the exit condition is satisfied. (vii) k=k+ 1. Goto (ii). Although the exit condition can be quite general, a reasonable choice is to exit after a given number of candidate solutions have been classified as probabilistic solutions or when a given computational time has elapsed since the starting of the algorithm. After exiting one could choose the probabilistic solution which maximizes a given performance index. We notice that in step (iv) we need to satisfy the i.i.d. assumption, and therefore sample reuse techniques are not applicable. In the next section, we propose a strategy to choose the cardinality of the validation set at iteration kin such a way that, with probability no smaller than 1 −δ, all candidate solutions classified as probabilistic solutions by the algorithm meet the accuracy η. 6 Adjusting the validation sample size The cardinality adjusting strategy provided in this section constitutes a generalization of that presented in [30] and [22]. To obtain the results of this section we rely on some contributions on the sample complexity presented in the previous sections. We now formally introduce the failure function. Definition 4 (failure function) The function µ: N→Ris said to be a failure function if it satisfies the following conditions: (i) µ(k)∈(0,1) for every positive integer k. (ii) ∞ P k=1 µ(k)≤1. We notice that the function µ(k) = 1 ξ(α)kα, where ξ(·) is the Riemann zeta function, is a failure function for every α > 1. This is due to the fact that ∞ P i=1 1 kα converges for every scalar αgreater than 1 to ξ(α). This family has been used in the context of validation schemes in [22] and in [30] for the particular value α= 2. Property 1 Consider an SPV algorithm with given accuracy parameter η∈(0,1), confidence δ∈(0,1), level function m(·)and cardinality function M(·,·,·). If m(k)< M(k, η, δ), for all k≥1, and there exists a failure function µ(·)such that m(k) X i=0 M(k, η, δ) i!ηi(1 −η)M(k,η,δ)−i≤δµ(k),∀k≥1 then, with probability greater than 1−δ, all the probabilistic solutions obtained running the SPV algorithm have a probability of violation no greater than η. The proof of this property follows the same lines as the proof of Theorem 9 in [30]. Proof: We denote by δkthe probability of classifying at iteration kthe candidate solution ˆ θkas a probabilistic solution under the assumption that the probability of violation E(ˆ θk) is larger than η. Furthermore, let Mk= M(k, η, δ), then δk= PrWMk{ˆ E(ˆ θk,w) ≤mk Mk } = mk X i=0 Mk i!E(ˆ θk)i(1 −ˆ θk)Mk−i 8 < mk X i=0 Mk i!ηi(1 −η)Mk−i. Property 4 in the Appendix, mk< Mk, and E(ˆ θk)> η have been used to derive the last inequality. Then, we obtain δk< m(k) X i=0 M(k, η, δ) i!ηi(1 −η)M(k,η,δ)−i≤δµ(k). Therefore, the probability of misclassification of a candidate solution at iteration kis smaller than δµ(k). We conclude that the probability of erroneously classifying one or more candidate solutions as probabilistic solutions is bounded by ∞ X k=1 δk< ∞ X k=1 δµ(k) = δ ∞ X k=1 µ(k)≤δ. ✷ To design a cardinality function M(·,·,·) satisfying the conditions of Property 1 we may use Corollary 1. We now present the main contribution of this part of the paper, which is a general expression for the cardinality of the validation set at each iteration of the algorithm. Theorem 5 Consider an SPV algorithm with given accuracy η∈(0,1), confidence δ∈(0,1) and level function m(·). Suppose also that µ(·)is a failure function. Then, the cardinality function M(k, η, δ) = &1 η m(k) + ln 1 δµ(k)+s2m(k) ln 1 δµ(k)!' guarantees that, with probability greater than 1−δ, all the probabilistic solutions obtained running the SPV algorithm have a probability of violation no greater than η. Proof: Corollary 1 guarantees that the proposed choice for the cardinality function satisfies m(k)< M(k, η, δ), for all k≥1, and m(k) X i=0 M(k, η, δ) i!ηi(1 −η)M(k,η,δ)−i≤δµ(k),∀k≥1. The result then follows from a direct application of Property 1. ✷ We notice that the proposed cardinality function M(k, η, δ) in Theorem 5 depends on the previous selection of the level function m(·) and the failure function µ(·). A reasonable choice for these functions is m(k) = ⌊ak⌋, where ais a non-negative scalar and µ(k) = 1 ξ(α)kαwhere αis greater than one. We recall that this choice guarantees that µ(k) is a failure function. As shown in the following section, the proposed level and failure functions allow us to recover, for the particular choice a= 0 the validation strategies proposed in [22] and [30]. In the next corollary, we specify the generic structure of the SPV algorithm with the level function m(k) = ⌊ak⌋, and state a probabilistic result. Corollary 2 Consider an SPV algorithm of the form given in Section 5 in which steps (i) and (iii) are substituted by (i) Set accuracy η∈(0,1), confidence δ∈(0,1) and scalars a≥0, α > 1 equal to the desired levels. Set kequal to 1. (iii) Set mk=⌊ak⌋and Mk=&1 η mk+ ln ξ(α)kα δ+r2mkln ξ(α)kα δ!'. Then, with probability greater than 1−δ, all the probabilistic solutions obtained running the SPV algorithm have a probability of violation no greater than η. Proof: The result is obtained directly from Theorem 5 using as level function m(k) = ⌊ak⌋and failure function µ(k) = 1 ξ(α)kα.✷ Since the probabilistic properties of the algorithm presented in Corollary 2 are independent of the particular value of α > 1, a reasonable choice for αis to select this parameter to minimize the cardinality of the validation sample set. 7 Comparison with other validation schemes In this section, we provide comparisons with the validation schemes presented in [30,22]. We notice that setting a= 0 and α= 2 in Corollary 2 we obtain m(k) = 0 for every iteration kand M(k) = 1 ηln ξ(2)k2 δ=1 ηln π2k2 6δ. This is the same cardinality function presented in [30] if one takes into account that for small values of η,−ln (1− η) can be approximated by η. In the same way, a= 0 and α= 1.1 lead to the cardinality function presented in [22]. We notice that not allowing any failure in each validation test makes perfect sense for convex problems if the feasibility set Θr={θ∈Θ : g(θ, w) = 0 for all w∈ W } is not empty. Under this assumption, the algorithm takes 9 =iηi−1(1 −η)N−i−(N−i)ηi(1 −η)N−i−1 = (i(1 −η)−(N−i)η)ηi−1(1 −η)N−i−1 = (i−Nη)ηi−1(1 −η)N−i−1.(A.1) With this definition we have d dηB(N, η, m) = d dη m X i=0 N i!ηi(1 −η)N−i = m X i=0 N i!ϕi(η).(A.2) We consider here two cases, m−Nη < 0 and m−Nη ≥ 0. In the first case we have from equation (A.1) that ϕi(η)<0, for i= 0,...,m. This fact, along with equation (A.2) implies that the derivative with respect to η is negative and therefore the claim of the property is proved for this case. Consider now the case m−Nη ≥0. In this case we have that ϕi(η)>0, for i > m. Since m < N we obtain d dηB(N, η, m) = m X i=0 N i!ϕi(η) < N X i=0 N i!ϕi(η) = N X i=0 N i!d dηηi(1 −η)N−i =d dη N X i=0 N i!ηi(1 −η)N−i =d dη(η+ (1 −η))N=d dη(1)N= 0. We notice that in the last step of the proof the identity (x+y)N= N X i=0 N i!xiyN−i has been used. ✷ Property 5 Suppose that Lis a positive integer and that sis a strictly positive scalar. Then, L P k=1 1 ks≤ Φ(s, ⌈log2L⌉)where, given s≥0and the integer t≥0, Φ(s, t) :=          1−2(1−s)(t+1) 1−21−sif s6= 1 t+ 1 otherwise. Proof: Given L > 0 and s > 0, define t:= ⌈log2(L)⌉and S(t) := 2t P k=1 1 ks. Then we have L P k=1 1 ks≤ 2t P k=1 1 ks=S(t). Next we show that S(t)≤1 + 21−sS(t−1) for every integer tgreater than 0. Since S(0) = 1 and S(1) = 1 + 2−s, the inequality is clearly satisfied for t= 1. We now prove the inequality for tgreater than 1 S(t) = 2t X k=1 1 ks= 2t−1 X k=1 1 (2k)s+1 (2k−1)s = 2−s 2t−1 X k=1 1 ks+ 2t−1 X k=1 1 (2k−1)s ≤2−sS(t−1) + 1 + 2t−1 X k=2 1 (2k−2)s = 2−sS(t−1) + 1 + 2−s 2t−1−1 X k=1 1 ks ≤2−sS(t−1) + 1 + 2−s 2t−1 X k=1 1 ks = 1 + 21−sS(t−1). We have therefore proved the inequality S(t)≤1 + 21−sS(t−1) for every integer tgreater than 0. Using this inequality in a recursive way with S(0) = 1 we obtain S(t)≤ t P k=0 2(1−s)k= Φ(s, t).This proves the result. ✷ 16