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

a Xi :1304.0678 2 [cs.SY] 21 Jul 2014 Randomized Me hods o Design o Unce ain Sys ems: Sample Complexi y and Sequen ial Algo i hms T. Alamo a, R. Tempo b, A. Luque a, D.R. Rami ez a aDepa amen o de Ingenie ´ıa de Sis emas y Au om´a ica, Uni e sidad de Se illa, Escuela Supe io de Ingenie os, Camino de los Descub imien os s/n, 41092 Se illa. Spain bCNR-IEIIT, Poli ecnico di To ino, Co so Duca degli Ab uzzi 24, To ino 10129, I aly Abs ac In his pape , we s udy andomized me hods o eedback design o unce ain sys ems. The i s con ibu ion is o de i e he sample complexi y o a ious cons ained con ol p oblems. In pa icula , we show he key ole played by he binomial dis ibu ion and ela ed ail inequali ies, and compu e he sample complexi y. This con ibu ion signi ican ly imp o es he exis ing esul s by educing he numbe o equi ed samples in he andomized algo i hm. These esul s a e hen applied o he analysis o wo s -case pe o mance and design wi h obus op imiza ion. The second con ibu ion o he pape is o in oduce a gene al class o sequen ial algo i hms, deno ed as Sequen ial P obabilis ic Valida ion (SPV). In hese sequen ial algo i hms, a each i e a ion, a candida e solu ion is p obabilis ically alida ed, and co ec ed i necessa y, o mee he equi ed speci ica ions. The esul s we de i e p o ide he sample complexi y which gua an ees ha he solu ions ob ained wi h SPV algo i hms mee some p e-speci ied p obabilis ic accu acy and con idence. The pe o mance o hese algo i hms is illus a ed and compa ed wi h o he exis ing me hods using a nume ical example dealing wi h obus sys em iden i ica ion. Key wo ds: andomized and p obabilis ic algo i hms, unce ain sys ems, sample complexi y 1 In oduc ion The use o andomized algo i hms o sys ems and con- ol has ma u ed hanks o he conside able esea ch e o s made in ecen yea s. Key a eas whe e we ha e seen con incing de elopmen s include unce ain and hy- b id sys ems [37,41]. A salien ea u e o his app oach is he use o he heo y o a e e en s and la ge de ia ion inequali ies, which sui ably bound he ail o he p oba- bili y dis ibu ion. These inequali ies a e c ucial in he a ea o s a is ical lea ning heo y [39], which has been u ilized o eedback design o unce ain sys ems [42]. Design in he p esence o unce ain y is o majo el- e ance in di e en a eas, including ma hema ical op i- miza ion and obus ness [7,31]. The goal is o ind a ea- sible solu ion which is op imal in some sense o all pos- sible unce ain y ins ances. Un o una ely, he ela ed semi-in ini e op imiza ion p oblems a e o en NP-ha d Email add esses: alamo@ca uja.us.es (T. Alamo), obe o. empo@poli o.i (R. Tempo), amalia@ca uja.us.es (A. Luque), dani @ca uja.us.es (D.R. Rami ez). (examples o NP-ha d p oblems in sys ems and con- ol can be ound in [8,9]), and his may se iously limi hei applicabili y om he compu a ional poin o iew. The e a e wo app oaches o esol e his NP-ha d issue. The i s app oach is based on he compu a ion o de e - minis ic elaxa ions o he o iginal p oblem, which a e usually polynomial ime sol able. Howe e , his migh lead o o e ly conse a i e solu ions [35]. An al e na- i e is o assume ha a p obabilis ic desc ip ion o he unce ain y is a ailable. Then, a andomized algo i hm may be de eloped o compu e, in polynomial ime, a so- lu ion wi h p obabilis ic gua an ees [37,41]. S ochas ic p og amming me hods [34] a e simila in spi i o he me hods s udied in his pape and ake ad an age ha , o andom unce ain y, he unde lying p obabili y dis- ibu ions a e known o can be es ima ed. The goal is o ind a solu ion ha is easible o almos all possible unce ain y ealiza ions and maximizes he expec a ion o some unc ion o he decisions a iables. The ield o p obabilis ic me hods [38,14,37] has ecei ed a g owing a en ion in he sys ems and con ol commu- ni y. Two complemen a y app oaches, non-sequen ial and sequen ial, ha e been p oposed. A classical ap- P ep in submi ed o Au oma ica 22 July 2014 p oach o non-sequen ial me hods is based upon s a is- ical lea ning heo y [39], [41]. Subsequen wo k along his di ec ion includes [27], [42], [43], [2], [18]. Fu he - mo e, in [4], [3] and [29] he case in which he design pa ame e se has ini e ca dinali y is analyzed. The ad an age o hese me hods is ha he p oblem unde a en ion may be non-con ex. Fo con ex op imiza ion p oblems, a non-sequen ial pa adigm, deno ed as he scena io app oach, has been in oduced in [11] and [12], see also [16], [17], [10], [4] o mo e ad anced esul s, and [33], [40] o ecen de elopemen s in he a eas o s ochas ic hyb id sys ems and mul i-s age op imiza ion, espec i ely. Finally, we e e o [23] o a andomized app oach o sol e app oxima e dynamic p og amming. In non-sequen ial me hods, he o iginal obus ness p ob- lem is e o mula ed as a single op imiza ion p oblem wi h sampled cons ain s, which a e andomly gene - a ed. A ele an ea u e o hese me hods is ha hey do no equi e any alida ion s ep and he sample com- plexi y is de ined a p io i. The main esul o his line o esea ch is o de i e explici lowe bounds o he e- qui ed sample size. Howe e , he ob ained explici sam- ple bounds can be o e ly conse a i e because hey ely on a wo s -case analysis and g ow (a leas linea ly) wi h he numbe o decision a iables. Fo sequen ial me hods, he esul ing i e a i e algo- i hms a e based on s ochas ic g adien [15], [32], el- lipsoid i e a ions [26], [30]; o analy ic cen e cu ing plane me hods [13], [44], see also [5,19] o o he classes o sequen ial algo i hms. Con e gence p ope ies in ini e- ime a e one o he ocal poin s o hese pape s. Va ious con ol p oblems ha e been sol ed using hese sequen ial andomized algo i hms, including obus LQ egula o s [32], swi ched sys ems [28] and unce ain lin- ea ma ix inequali ies (LMIs) [15]. Sequen ial me hods a e o en used o unce ain con ex easibili y p oblems because he compu a ional e o a each i e a ion is a o dable. Howe e , hey ha e been s udied also o non-con ex p oblems, see [2], [25]. The common ea u e o mos o hese sequen ial algo- i hms is he use o he alida ion s a egy p esen ed in [30] and [22]. The candida e solu ions p o ided a each i e a ion o hese algo i hms a e es ed using a alida ion se which is d awn acco ding o he p obabili y measu e associa ed o he unce ain y. I he candida e solu ion sa is ies he design speci ica ions o e e y sampled ele- men o his alida ion se , hen i is classi ied as p oba- bilis ic solu ion and he algo i hm e mina es. The main poin in his alida ion scheme is ha he ca dinali y o he alida ion se inc eases e y mildly a each i e - a ion o he algo i hm. The s a egy gua an ees ha , i a p obabilis ic solu ion is ob ained, hen i mee s some p obabilis ic speci ica ions. In his pape , we de i e he sample complexi y o a - ious analysis and design p oblems ela ed o unce ain sys ems. In pa icula we p o ide new esul s which gua an ee ha he ail o he binomial dis ibu ion is bounded by a p e-speci ied alue. These esul s a e hen applied o he analysis o wo s -case pe o mance and cons ain iola ion. Wi h ega d o design p oblems, we conside he special cases o ini e amilies and o- bus con ex op imiza ion p oblems. This con ibu ion imp o es he exis ing esul s by educing he numbe o samples equi ed o sol e he design p oblem. We e- ma k ha he esul s we ha e ob ained a e ai ly gene al and he assump ions on con exi y and on ini e amilies appea only in Sec ion 4 which deals wi h p obabilis ic analysis and design. The second main con ibu ion o his pape is o p opose a sequen ial alida ion scheme, deno ed as Sequen ially P obabilis ic Valida ion (SPV), which allows he candi- da e solu ion o iola e he design speci ica ions o one (o mo e) o he membe s o he alida ion se . The idea o allowing some iola ions o he cons ain s is no new and can be ound, o example, in he con ex o sys em iden i ica ion [6], chance-cons ained op imiza ion [17] and s a is ical lea ning heo y [2]. This scheme makes sense in he p esence o so cons ain s o when a so- lu ion sa is ying he speci ica ions o all he admissible unce ain y ealiza ions can no be ound. In his way, we imp o e he exis ing esul s wi h his elaxed alida- ion scheme ha educes he chance o no de ec ing he solu ion e en when i exis s. Fu he mo e, we also show ha a s ic alida ion scheme may no be well-sui ed o some obus design p oblems. This pape is based on he p e ious wo ks o he au- ho s [4] and [1]. Howe e , some esul s a e comple ely new (P ope y 4) and o he s (Theo em 2, P ope y 1 and P ope y 3 and hei p oo s) a e signi ican imp o e- men s o he p elimina y esul s p esen ed in he con e - ence pape s. Fu he mo e, he uni ying app oach s ud- ied he e, which combines sample complexi y esul s wi h SPV algo i hms, was no p esen in p e ious pape s. Fi- nally, he nume ical example in Sec ion 8, which com- pa es a ious app oaches a ailable in he li e a u e, is also new. The es o he pape is o ganized as ollows. In he nex sec ion, we i s in oduce he p oblem o - mula ion. In Sec ion 3, we p o ide bounds o he bino- mial dis ibu ion which a e used in Sec ion 4 o analyze he p obabilis ic p ope ies o di e en schemes in ol- ing andomiza ion. In Sec ion 5, we in oduce he p o- posed amily o p obabilis ically alida ed algo i hms. The sample complexi y o he alida ing se s is analyzed in Sec ion 6. A de ailed compa ison wi h he alida ion scheme p esen ed in [30] is p o ided in Sec ion 7. A nu- me ical example whe e di e en schemes a e used o ad- d ess a obus iden i ica ion p oblem is p esen ed in Sec- ion 8. The pape ends wi h a sec ion o conclusions and an appendix which con ains some auxilia y p ope ies and p oo s ha a e used in he p e ious sec ions. 2 2 P oblem S a emen We assume ha a p obabili y measu e P Wo e he sample space Wis gi en. Gi en W, a collec ion o N independen iden ically dis ibu ed (i.i.d.) samples w = {w(1),...,w(N)}d awn om Wbelongs o he Ca e- sian p oduc WN=W × · · · × W (N imes). Mo eo e , i he collec ion w o Ni.i.d. samples {w(1),...,w(N)} is gene a ed om Wacco ding o he p obabili y mea- su e P W, hen he mul isample w is d awn acco ding o he p obabili y measu e P WN. The scala s η∈(0,1) and δ∈(0,1) deno e p obabilis ic pa ame e s called ac- cu acy and con idence, espec i ely. Fu he mo e, ln(·) is he na u al loga i hm and e is he Eule numbe . Fo x∈R,x≥0, ⌊x⌋deno es he la ges in ege smalle han o equal o x;⌈x⌉deno es he smalles in ege g ea e o equal han x. Fo α > 1, ξ(α) := ∞ X k=1 1 kα deno es he Riemann ze a unc ion. In a obus ness p oblem, he con olle pa ame e s and auxilia y a iables a e pa ame e ized by means o a deci- sion a iable ec o θ, which is deno ed as design pa am- e e and is es ic ed o a se Θ. Fu he mo e, he unce - ain y wis bounded in he se Wand ep esen s one o he admissible unce ain y ealiza ions. We also conside a bina y measu able unc ion g: Θ × W → {0,1}and a eal measu able unc ion : Θ × W → Rwhich helps o o mula e he speci ic design p oblem unde a en ion. Mo e p ecisely, he bina y unc ion g: Θ × W → {0,1}, is de ined as g(θ, w) := (0 i θmee s design speci ica ions o w 1 o he wise, whe e design speci ica ions a e, o example, H∞no m bounds on he sensi i i y unc ion, see speci ic examples in [37], o he nume ical example in Sec ion 8. Gi en θ∈Θ, he cons ain g(θ, w) = 0 is sa is ied o a subse o W. This concep is igo ously o malized by means o he no ion o p obabili y o iola ion, which is now in oduced. De ini ion 1 [p obabili y o iola ion] Conside a p ob- abili y measu e P Wo e Wand le θ∈Θbe gi en. The p obabili y o iola ion o θ o he unc ion g: Θ×W → {0,1}is de ined as E(θ) := P W{g(θ, w) = 1 }. Using his no ion we s udy he obus op imiza ion p ob- lem min θ∈ΘJ(θ) subjec o E(θ)≤η, (1) whe e J: Θ →(−∞,∞) is a measu able unc ion which ep esen s he con olle pe o mance and η∈(0,1) is a p obabilis ic accu acy. Gi en accu acy η∈(0,1) and con idence δ∈(0,1), he main poin o he p obabilis ic app oach is o design an algo i hm such ha any p ob- abilis ic solu ion ˆ θob ained by unning he algo i hm, sa is ies E(ˆ θ)≤ηwi h p obabili y no smalle han 1−δ. E en in analysis p oblems when θ∈Θ is gi en, i is o - en e y ha d o compu e he exac alue o he p oba- bili y o iola ion E(θ) because his equi es o sol e a mul iple in eg al wi h a usually non-con ex domain o in eg a ion. Howe e , we can app oxima e i s alue us- ing he concep o empi ical mean. Fo gi en θ∈Θ, and mul isample w = {w(1),...,w(N)}d awn acco ding o he p obabili y measu e P WN, he empi ical mean o g(θ, w) wi h espec o w is de ined as ˆ E(θ, w) := 1 N N X i=1 g(θ, w(i)). Clea ly, he empi ical mean ˆ E(θ, w) is a andom a iable. Since g(·,·) is a bina y unc ion, ˆ E(θ, w) is always wi hin he closed in e al [0,1]. The powe o andomized algo i hms s ems om he ac ha hey can app oxima ely sol e non-con ex design p oblems (wi h no- iola ion) o he ype min θ∈ΘJ(θ) subjec o g(θ, w) = 0, o all w∈ W.(2) In his se ing, we d aw Ni.i.d. samples {w(1),...,w(N)} om Wacco ding o p obabili y P Wand sol e he sam- pled op imiza ion p oblem min θ∈ΘJ(θ) subjec o g(θ, w(ℓ)) = 0, ℓ = 1,...,N. (3) Since ob aining a global solu ion o his p oblem is s ill a di icul ask in gene al, in his pape we analyze he p obabilis ic p ope ies o any subop imal solu ion. Fu - he mo e, i a mos m iola ions o he Ncons ain s a e allowed, he ollowing sampled p oblem can be used o ob ain a p obabilis ic elaxa ion o he o iginal p ob- lem (2) min θ∈ΘJ(θ) subjec o N X ℓ=1 g(θ, w(ℓ))≤m. (4) 3 Randomized s a egies o sol e p oblems (3) and (4) ha e been s udied in [2], see also [37]. In o de o an- alyze he p obabilis ic p ope ies o any easible solu- ion o p oblem (4), we in oduce he de ini ions o non- con o ming easible se and p obabili y o ailu e. De ini ion 2 [non-con o ming easible se ] Gi en N, he in ege mwhe e 0≤m < N,η∈(0,1),g: Θ× W → {0,1}and mul isample w = {w(1),...,w(N)}, d awn acco ding o he p obabili y measu e P WN, he non-con o ming easible se Θ(w, η, m)is de ined as Θ(w, η, m) := {θ∈Θ : ˆ E(θ, w) ≤m Nand E(θ)> η }. De ini ion 3 [p obabili y o ailu e] Gi en N, he in e- ge mwhe e 0≤m < N,η∈(0,1) and g: Θ × W → {0,1}, he p obabili y o ailu e, deno ed by p(N, η, m)is de ined as p(N, η, m) := P WN{Θ(w, η, m) is no emp y}. The p obabili y p(N, η, m) de ined he e is sligh ly di e - en han he p obabili y o one-sided cons ained ailu e in oduced in [2]. We no ice ha he non-con o ming ea- sibili y se is emp y wi h p obabili y 1−p(N, η, m). This means ha e e y easible solu ion θ∈Θ o p oblem (4) sa is ies E(θ)≤ηwi h p obabili y 1−p(N, η, m). Gi en he con idence pa ame e δ∈(0,1), he objec i e is o ob ain explici exp essions yielding a minimum numbe o samples Nsuch ha p(N, η, m)≤δ. 3 Sample complexi y o he binomial dis ibu- ion In his sec ion, we p o ide bounds o he binomial dis- ibu ion which a e used in Sec ion 4. Gi en a posi i e in ege Nand a nonnega i e in ege m,m≤N, and η∈(0,1), he binomial dis ibu ion unc ion is gi en by B(N, η, m) := m X i=0 N i!ηi(1 −η)N−i. The p oblem we add ess in his sec ion is he explici compu a ion o he sample complexi y, i.e. a unc ion ˜ N(η, m, δ) such ha he inequali y B(N, η, m)≤δholds o any N≥˜ N(η, m, δ), whe e δ∈(0,1). As i will be illus a ed in he ollowing sec ion, he inequali y B(N, η, m)≤δplays a undamen al ole in p obabilis ic me hods. Al hough some explici exp essions a e a ail- able, e.g. he mul iplica i e and addi i e o ms o Che - no bound [20], he esul s ob ained in his pape a e uned on he speci ic inequali ies s emming om he p oblems desc ibed in Sec ion 4. The ollowing echnical lemma p o ides an uppe bound o he binomial dis ibu ion B(N, η, m). Lemma 1 Suppose ha η∈(0,1) and ha he nonnega- i e in ege mand he posi i e in ege Nsa is y m≤N. Then, B(N, η, m)≤amη a+ 1 −ηN,∀a≥1. P oo : The p oo o he lemma ollows om he ollow- ing sequence o inequali ies: 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 no ice ha each pa icula choice o a≥1 p o ides an uppe bound o B(N, η, m). When using Lemma 1 o ob ain a speci ic sample complexi y, he selec ed alue o aplays a signi ican ole. Lemma 2 Gi en δ∈(0,1) and he nonnega i e in ege m, suppose ha he in ege Nand he scala s η∈(0,1) and a > 1sa is y he inequali y N≥1 ηa a−1ln 1 δ+mln a.(5) Then, m < N and B(N, η, m)≤δ. P oo : We i s p o e ha i inequali y (5) is sa is ied hen m < N. Since η∈(0,1) and δ∈(0,1), (5) implies N > a a−1ln am. Nex , we no ice ha d daa a−1ln a=−1 (a−1)2ln a+1 a−1. Since ln a < a −1 o e e y a > 1, i ollows ha d daa a−1ln a>−1 (a−1)2(a−1) + 1 a−1= 0. Using his ac , we conclude ha a (a−1) ln ais a s ic ly inc easing unc ion o a > 1. This means ha N > a a−1ln am≥lim ˆa→1ˆa ˆa−1ln ˆam=m. 4 We now p o e ha (5) gua an ees ha am(η a+1−η)N≤ δ. The inequali y (5) can be ew i en as Nη a−1 a≥ln 1 δ+mln a. (6) Since x≤ − ln (1 −x) o e e y x∈(0,1), and η(a−1 a)∈ (0,1), om inequali y (6), we ob ain a sequence o in- equali ies −Nln 1−ηa−1 a≥ln 1 δ+mln a ln δ≥mln a+Nln 1−ηa−1 a δ≥amη a+ 1 −ηN . We ha e he e o e p o ed ha inequali y (5) implies m≤ Nand am(η a+ 1 −η)N≤δ. The claim o he p ope y ollows di ec ly om Lemma 1. ✷ Ob iously, he bes sample size bound is ob ained ak- ing he in imum wi h espec o a > 1. Howe e , his e- qui es o sol e nume ically a one-dimensional op imiza- ion p oblem o gi en η,δand m. We obse e ha a subop imal alue can be immedia ely ob ained se ing aequal o he Eule cons an , which yields he sample complexi y N≥1 ηe e−1ln 1 δ+m.(7) Since e e−1<1.59, we ob ain N≥1.59 ηln 1 δ+m, which is (nume ically) a signi ican imp o emen o he bound gi en in [10] and o he bounds a ailable in he li e a u e [14]. We also no ice ha , i m > 0 hen he choice a= 1 + ln 1 δ m+s2ln 1 δ m p o ides a less conse a i e bound a he p ice o a mo e in ol ed exp ession [4]. Based on ex ensi e nume ical compu a ions o se e al alues o η,δand mwe con- clude ha his bound is e y close o he “op imal” one. No e, howe e , ha he op imal alue can be ob ained nume ically using he Lambe W unc ion [21]. In he nex co olla y, we p esen ano he mo e in ol ed sample complexi y bound which imp o es (7) o some alues o he pa ame e s. Co olla y 1 Gi en δ∈(0,1) and he nonnega i e in e- ge m, suppose ha he in ege Nand he scala η∈(0,1) sa is y he inequali y N≥1 η m+ ln 1 δ+ 2mln 1 δ!.(8) Then, m < N and B(N, η, m)≤δ. The p oo o his co olla y is shown in he appendix. 4 Sample complexi y o p obabilis ic analysis and design We now s udy some p oblems in he con ex o andom- ized algo i hms whe e one encoun e s inequali ies o he o m B(N, η, m)≤δ. In pa icula , we show how he esul s o he p e ious sec ion can be used o de i e ex- plici sample size bounds which gua an ee ha he p ob- abilis ic solu ions ob ained om di e en andomized app oaches mee some p e-speci ied p obabilis ic p op- e ies. In Subsec ion 4.2 we de i e bounds on p(N, η, m) when Θ consis s o a ini e numbe o elemen s. On he o he hand, i Θ consis s o an in ini e numbe o elemen s, a deepe analysis in ol ing s a is ical lea ning heo y is needed [37], [41]. In Subsec ion 4.3 we s udy he p oba- bilis ic p ope ies o he op imal solu ion o p oblem (3) unde he assump ion ha g(θ, w) = 0 is equi alen o (θ, w)≤0, whe e : Θ × W → Ris a con ex unc- ion wi h espec o θin Θ. In his case, he esul is no exp essed in e ms o p obabili y o ailu e because i applies only o he op imal solu ion o p oblem (3), and no o e e y easible solu ion. 4.1 Wo s -case pe o mance analysis We ecall a esul shown in [36] o he p obabilis ic wo s -case pe o mance analysis. Theo em 1 Gi en he unc ion : Θ×W → Rand ˆ θ∈ Θ, conside he mul isample w = {w(1),...,w(N)}d awn om WNacco ding o p obabili y P WNand de ine γ= max ℓ=1,...,N (ˆ θ, w(ℓ)).I N≥ln 1 δ ln 1 1−η , hen P W{w∈ W : (ˆ θ, w)> γ} ≤ ηwi h p obabili y no smalle han 1−δ. The p oo o his s a emen can be ound in [36] and is based on he ac ha P W{w∈ W : (ˆ θ, w)> γ} ≤ η wi h p obabili y no smalle han 1−(1−η)N. The e o e, i su ices o ake Nsuch ha B(N, η, 0) = (1−η)N≤δ. 5 4.2 Fini e amilies o design We conside he non-con ex sampled p oblem (4) o he special case when Θ consis s o a se o ini e ca dinali y nC. As a mo i a ion, we s udy he case when, a e an app op ia e no maliza ion p ocedu e, he design pa am- e e se is ew i en as ˆ Θ = {θ∈Rnθ:kθk∞≤1}. Suppose also ha a g idding app oach is adop ed. Tha is, o each componen θj,j= 1, . . . , nθo he design pa ame e s θ∈Rnθ, only nCjequally spaced alues a e conside ed. Tha is, θjis cons ained in o he se Υj={ −1 + 2( −1) (nCj−1) : = 1, . . . , nCj}.Wi h his g idding p ocedu e, he ollowing ini e ca dinali y se Θ = {[θ1,...,θnθ]T:θj∈Υj, j = 1,...,nθ}is ob ained. We no ice ha he ca dinali y o he se is nC=Qnθ j=1 nCj. Ano he si ua ion in which he ini e ca dinali y assump ion holds is when a ini e numbe o andom samples in he space o design pa ame e a e d awn acco ding o a gi en p obabili y, see e.g. [24,42]. The ollowing heo em s a es he ela ion be ween he binomial dis ibu ion and he p obabili y o ailu e unde his ini e ca dinali y assump ion. Theo em 2 Suppose ha he ca dinali y o Θis no la ge han nC,nC>0,η∈(0,1) and m < N. Then, p(N, η, m)< nCB(N, η, m). P oo : I he e is no elemen in Θ wi h p obabili y o iola ion la ge han η, hen he non-con o ming easible se is emp y o e e y mul isample w and p(N, η, m) = 0< nCB(N, η, m). Suppose now ha he subse o Θ o elemen s wi h p ob- abili y o iola ion la ge han ηis no emp y. Deno e {θ(1), θ(2),...,θ(˜n)}such a se . In his case, gi en a mul- isample w, he non-con o ming easible se is no emp y i and only i he empi ical mean is smalle o equal han m N o a leas one o he elemen s o his se . The e o e p(N, η, m) = P WN{Θ(w, η, m) is no emp y} = P WN{min 1≤k≤˜n ˆ E(θ(k),w) ≤m N} ≤ ˜n X k=1 P WN{ˆ E(θ(k),w) ≤m N} = ˜n X k=1 B(N, E(θ(k)), m) < ˜n X k=1 B(N, η, m) = ˜nB(N, η, m). No ice ha he las inequali y is due o he ac ha E(θ(k))> η,k= 1,...,˜nand ha he binomial dis i- bu ion is a s ic ly dec easing unc ion o ηi m < N (see P ope y 4 in he Appendix). To conclude he p oo i su ices o no ice ha ˜n≤nC.✷ Conside now he op imiza ion p oblem (4). I ollows om Lemma 2 ha o gua an ee ha e e y easible so- lu ion ˆ θ∈Θ sa is ies E(ˆ θ)≤ηwi h p obabili y no smalle han 1 −δ, i su ices o ake N > m such ha nCB(N, η, m)≤δ, whe e nCis an uppe bound on he ca dinali y o Θ. As i will be shown nex , he equi ed sample complexi y in his case g ows wi h he loga i hm o nC. This means ha we can conside ini e amilies wi h high ca dinali y and s ill ob ain e y easonable sample complexi y bounds. Theo em 3 Suppose ha he ca dinali y o Θis no la ge han nC. Gi en he nonnega i e in ege m, η∈(0,1) and δ∈(0,1), i N≥in a>1 1 ηa a−1ln nC δ+mln a(9) hen p(N, η, m)≤δ. Mo eo e , i N≥1 ηm+ ln nC δ+ 2mln nC δ hen p(N, η, m)≤δ. P oo : F om Lemma 2 we ha e ha p(N, η, m)≤δ p o ided ha m < N and B(N, η, m)≤δ nC. The wo claims o he p ope y now ollow di ec ly om Lemma 2 and Co olla y 1 espec i ely. ✷ F om he de ini ion o p(N, η, m) and Theo em 3 we con- clude ha i one d aws Ni.i.d. samples {w(1),...,w(N)} om Wacco ding o p obabili y P W, hen wi h p oba- bili y no smalle han 1 −δ, all he easible solu ions o p oblem (4) ha e a p obabili y o iola ion no la ge han η, p o ided ha he ca dinali y o Θ is uppe bounded by nCand he sample complexi y is gi en by N≥1 ηm+ ln nC δ+ 2mln nC δ. We ema k ha aking aequal o he Eule cons an in (9), he ollowing sample size bound N≥1 ηe e−1ln nC δ+m is immedia ely ob ained om Theo em 3. I m > 0 hen a subop imal alue o ais gi en by a= 1 + ln nC δ m+ 2ln nC δ m. 6 4.3 Op imal obus op imiza ion o design In his subsec ion, we s udy he so-called scena io ap- p oach o obus con ol in oduced in [12]. To add ess he semi-in ini e op imiza ion p oblem (2), we sol e he andomized op imiza ion p oblem (3). Tha is, we gen- e a e Ni.i.d. samples {w(1),...,w(N)} om Wacco d- ing o he p obabili y P Wand hen sol e he ollowing sampled op imiza ion p oblem: min θ∈ΘJ(θ) subjec o g(θ, w(ℓ)) = 0, ℓ = 1,...,N. (10) We conside he e he pa icula case in which J(θ) = cTθ, he cons ain g(θ, w) = 0 is con ex in θ o all w∈ Wand he solu ion o (10) is unique. These assump ions a e now s a ed p ecisely. Assump ion 1 [con exi y] Le Θ⊂Rnθbe a con ex and closed se . We assume ha J(θ) := cTθand g(θ, w) := (0i (θ, w)≤0, 1o he wise whe e : Θ × W → [−∞,∞]is con ex in θ o e e y ixed alue o w∈ W. Assump ion 2 [ easibili y and uniqueness] Fo all pos- sible mul isample ex ac ions {w(1),. . .,w(N)}, he op- imiza ion p oblem (10) is always easible and a ains a unique op imal solu ion. Mo eo e , i s easibili y domain has a nonemp y in e io . Uniqueness may be assumed essen ially wi hou loss o gene ali y, since in case o mul iple op imal solu ions one may always in oduce a sui able ie-b eaking ule [12]. We now s a e a esul ha ela es he binomial dis ibu ion o he p obabilis ic p ope ies o he op imal solu ion ob ained om (10). See [16,10,17]. Lemma 3 Le Assump ions 1 and 2 hold. Suppose ha N,η∈(0,1) and δ∈(0,1) sa is y he inequali y nθ−1 X i=0 N i!ηi(1 −η)N−i≤δ. (11) Then, wi h p obabili y no smalle han 1−δ, he op imal solu ion ˆ θN o he op imiza ion p oblem (10) sa is ies he inequali y E(ˆ θN)≤η. We now s a e an explici sample size bound, which im- p o es upon p e ious bounds, o gua an ee ha he p obabili y o iola ion is smalle han ηwi h p obabil- i y a leas 1 −δ. Theo em 4 Le Assump ions 1 and 2 hold. Gi en η∈ (0,1) and δ∈(0,1), i N≥in a>1 1 ηa a−1ln 1 δ+ (nθ−1) ln a(12) o N≥1 η ln 1 δ+ (nθ−1) + 2(nθ−1) ln 1 δ!(13) hen, wi h p obabili y no smalle han 1−δ, he op imal solu ion ˆ θN o he op imiza ion p oblem (10) sa is ies he inequali y E(ˆ θN)≤η. P oo : F om Lemma 3 i ollows ha i su ices o ake N such ha B(N, η, nθ−1) ≤δ. Bo h inequali ies (12) and (13) gua an ee ha B(N, η, nθ−1) ≤δ(see Lemma 2 and Co olla y 1 espec i ely). This comple es he p oo . ✷ Taking aequal o he Eule cons an in (12), we ob ain N≥1 ηe e−1ln 1 δ+nθ−1 which imp o es he bound gi en in [10] and o he bounds a ailable in he li e a u e [14]. Mo e p ecisely, he con- s an 2 appea ing in [10] is educed o e (e−1) ≈1.59, which is (nume ically) a subs an ial imp o emen o small alues o η. I nθ>1 a subop imal alue o ais gi en by a= 1 + ln 1 δ nθ−1+s2ln 1 δ nθ−1. 5 Sequen ial algo i hms wi h p obabilis ic ali- da ion In his sec ion, we p esen a gene al amily o andom- ized algo i hms, which we deno e as Sequen ial P oba- bilis ic Valida ion (SPV) algo i hms. The main ea u e o his class o algo i hms is ha hey a e based on a p obabilis ic alida ion s ep. This amily includes mos o he sequen ial andomized algo i hms ha ha e been p esen ed in he li e a u e and a e discussed in he in- oduc ion o his pape . Each i e a ion o an SPV algo i hm includes he com- pu a ion o a candida e solu ion o he p oblem and a subsequen alida ion s ep. The esul s p o ided in his pape a e basically independen o he pa icula s a - egy chosen o ob ain candida e solu ions. The e o e, in he ollowing discussion we es ic ou sel es o a gene ic 7 candida e solu ion. The accu acy η∈(0,1) and con i- dence δ∈(0,1) equi ed o he p obabilis ic solu ion play a ele an ole when de e mining he sample size o each alida ion s ep. The main pu pose o his pa o he pape is o p o ide a alida ion scheme which gua - an ees ha , o gi en accu acy ηand con idence δ, all he p obabilis ic solu ions ob ained unning he SPV al- go i hm ha e a p obabili y o iola ion no la ge han η wi h p obabili y no smalle han 1 −δ. We enume a e each i e a ion o he algo i hm by means o an in ege k. We deno e by mk he numbe o io- la ions ha a e allowed a he alida ion s ep o i e a- ion k. We assume ha mkis a unc ion o k, ha is, mk=m(k) whe e he unc ion m:N→Nis gi en. We also deno e by Mk he sample size o he alida- ion s ep o i e a ion k. We assume ha Mkis a unc- ion o k,ηand δ. Tha is, Mk=M(k, η, δ) whe e M:N×R×R→Nhas o be app op ia ely designed in o de o gua an ee he p obabilis ic p ope ies o he al- go i hm. In ac , one o he main con ibu ions o [30,22] is o p o ide his unc ion o he pa icula case mk= 0 o e e y k≥1. The unc ions m(·) and M(·,·,·) a e de- no ed as le el unc ion and ca dinali y unc ion espec- i ely. We now in oduce he s uc u e o an SPV algo i hm (i) Se accu acy η∈(0,1) and con idence δ∈(0,1) equal o he desi ed le els. Se kequal o 1. (ii) Ob ain a candida e solu ion ˆ θk o he obus op i- miza ion p oblem (1). (iii) Se mk=m(k) and Mk=M(k, η, δ). (i ) Ob ain alida ion se Vk={ (1),..., (Mk)}d aw- ing Mki.i.d. alida ion samples om Wacco ding o p obabili y P W. ( ) I Mk P ℓ=1 g(ˆ θk, (ℓ))≤mk, hen ˆ θkis a p obabilis ic solu ion. ( i) Exi i he exi condi ion is sa is ied. ( ii) k=k+ 1. Go o (ii). Al hough he exi condi ion can be qui e gene al, a ea- sonable choice is o exi a e a gi en numbe o candi- da e solu ions ha e been classi ied as p obabilis ic solu- ions o when a gi en compu a ional ime has elapsed since he s a ing o he algo i hm. A e exi ing one could choose he p obabilis ic solu ion which maximizes a gi en pe o mance index. We no ice ha in s ep (i ) we need o sa is y he i.i.d. assump ion, and he e o e sample euse echniques a e no applicable. In he nex sec ion, we p opose a s a egy o choose he ca dinali y o he alida ion se a i e a ion kin such a way ha , wi h p obabili y no smalle han 1 −δ, all candida e so- lu ions classi ied as p obabilis ic solu ions by he algo- i hm mee he accu acy η. 6 Adjus ing he alida ion sample size The ca dinali y adjus ing s a egy p o ided in his sec- ion cons i u es a gene aliza ion o ha p esen ed in [30] and [22]. To ob ain he esul s o his sec ion we ely on some con ibu ions on he sample complexi y p esen ed in he p e ious sec ions. We now o mally in oduce he ailu e unc ion. De ini ion 4 ( ailu e unc ion) The unc ion µ: N→Ris said o be a ailu e unc ion i i sa is ies he ollowing condi ions: (i) µ(k)∈(0,1) o e e y posi i e in ege k. (ii) ∞ P k=1 µ(k)≤1. We no ice ha he unc ion µ(k) = 1 ξ(α)kα, whe e ξ(·) is he Riemann ze a unc ion, is a ailu e unc- ion o e e y α > 1. This is due o he ac ha ∞ P i=1 1 kα con e ges o e e y scala αg ea e han 1 o ξ(α). This amily has been used in he con ex o alida ion schemes in [22] and in [30] o he pa icula alue α= 2. P ope y 1 Conside an SPV algo i hm wi h gi en accu acy pa ame e η∈(0,1), con idence δ∈(0,1), le el unc ion m(·)and ca dinali y unc ion M(·,·,·). I m(k)< M(k, η, δ), o all k≥1, and he e exis s a ailu e unc ion µ(·)such ha m(k) X i=0 M(k, η, δ) i!ηi(1 −η)M(k,η,δ)−i≤δµ(k),∀k≥1 hen, wi h p obabili y g ea e han 1−δ, all he p obabilis- ic solu ions ob ained unning he SPV algo i hm ha e a p obabili y o iola ion no g ea e han η. The p oo o his p ope y ollows he same lines as he p oo o Theo em 9 in [30]. P oo : We deno e by δk he p obabili y o classi ying a i e a ion k he candida e solu ion ˆ θkas a p obabilis ic solu ion unde he assump ion ha he p obabili y o iola ion E(ˆ θk) is la ge han η. Fu he mo e, le Mk= M(k, η, δ), hen δk= P WMk{ˆ 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. P ope y 4 in he Appendix, mk< Mk, and E(ˆ θk)> η ha e been used o de i e he las inequali y. Then, we ob ain δk< m(k) X i=0 M(k, η, δ) i!ηi(1 −η)M(k,η,δ)−i≤δµ(k). The e o e, he p obabili y o misclassi ica ion o a can- dida e solu ion a i e a ion kis smalle han δµ(k). We conclude ha he p obabili y o e oneously classi ying one o mo e candida e solu ions as p obabilis ic solu- ions is bounded by ∞ X k=1 δk< ∞ X k=1 δµ(k) = δ ∞ X k=1 µ(k)≤δ. ✷ To design a ca dinali y unc ion M(·,·,·) sa is ying he condi ions o P ope y 1 we may use Co olla y 1. We now p esen he main con ibu ion o his pa o he pape , which is a gene al exp ession o he ca dinali y o he alida ion se a each i e a ion o he algo i hm. Theo em 5 Conside an SPV algo i hm wi h gi en ac- cu acy η∈(0,1), con idence δ∈(0,1) and le el unc ion m(·). Suppose also ha µ(·)is a ailu e unc ion. Then, he ca dinali y unc ion M(k, η, δ) = &1 η m(k) + ln 1 δµ(k)+s2m(k) ln 1 δµ(k)!' gua an ees ha , wi h p obabili y g ea e han 1−δ, all he p obabilis ic solu ions ob ained unning he SPV al- go i hm ha e a p obabili y o iola ion no g ea e han η. P oo : Co olla y 1 gua an ees ha he p oposed choice o he ca dinali y unc ion sa is ies m(k)< M(k, η, δ), o all k≥1, and m(k) X i=0 M(k, η, δ) i!ηi(1 −η)M(k,η,δ)−i≤δµ(k),∀k≥1. The esul hen ollows om a di ec applica ion o P op- e y 1. ✷ We no ice ha he p oposed ca dinali y unc ion M(k, η, δ) in Theo em 5 depends on he p e ious se- lec ion o he le el unc ion m(·) and he ailu e unc- ion µ(·). A easonable choice o hese unc ions is m(k) = ⌊ak⌋, whe e ais a non-nega i e scala and µ(k) = 1 ξ(α)kαwhe e αis g ea e han one. We ecall ha his choice gua an ees ha µ(k) is a ailu e unc- ion. As shown in he ollowing sec ion, he p oposed le el and ailu e unc ions allow us o eco e , o he pa icula choice a= 0 he alida ion s a egies p o- posed in [22] and [30]. In he nex co olla y, we speci y he gene ic s uc u e o he SPV algo i hm wi h he le el unc ion m(k) = ⌊ak⌋, and s a e a p obabilis ic esul . Co olla y 2 Conside an SPV algo i hm o he o m gi en in Sec ion 5 in which s eps (i) and (iii) a e subs i- u ed by (i) Se accu acy η∈(0,1), con idence δ∈(0,1) and scala s a≥0, α > 1 equal o he desi ed le els. Se kequal o 1. (iii) Se mk=⌊ak⌋and Mk=&1 η mk+ ln ξ(α)kα δ+ 2mkln ξ(α)kα δ!'. Then, wi h p obabili y g ea e han 1−δ, all he p ob- abilis ic solu ions ob ained unning he SPV algo i hm ha e a p obabili y o iola ion no g ea e han η. P oo : The esul is ob ained di ec ly om Theo em 5 using as le el unc ion m(k) = ⌊ak⌋and ailu e unc ion µ(k) = 1 ξ(α)kα.✷ Since he p obabilis ic p ope ies o he algo i hm p e- sen ed in Co olla y 2 a e independen o he pa icula alue o α > 1, a easonable choice o αis o selec his pa ame e o minimize he ca dinali y o he alida ion sample se . 7 Compa ison wi h o he alida ion schemes In his sec ion, we p o ide compa isons wi h he alida- ion schemes p esen ed in [30,22]. We no ice ha se ing a= 0 and α= 2 in Co olla y 2 we ob ain m(k) = 0 o e e y i e a ion kand M(k) = 1 ηln ξ(2)k2 δ=1 ηln π2k2 6δ. This is he same ca dinali y unc ion p esen ed in [30] i one akes in o accoun ha o small alues o η,−ln (1− η) can be app oxima ed by η. In he same way, a= 0 and α= 1.1 lead o he ca dinali y unc ion p esen ed in [22]. We no ice ha no allowing any ailu e in each alida ion es makes pe ec sense o con ex p oblems i he easi- bili y se Θ ={θ∈Θ : g(θ, w) = 0 o all w∈ W } is no emp y. Unde his assump ion, he algo i hm akes 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) Wi h his de ini ion we ha e 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 conside he e wo cases, m−Nη < 0 and m−Nη ≥ 0. In he i s case we ha e om equa ion (A.1) ha ϕi(η)<0, o i= 0,...,m. This ac , along wi h equa- ion (A.2) implies ha he de i a i e wi h espec o η is nega i e and he e o e he claim o he p ope y is p o ed o his case. Conside now he case m−Nη ≥0. In his case we ha e ha ϕi(η)>0, o i > m. Since m < N we ob ain 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 no ice ha in he las s ep o he p oo he iden i y (x+y)N= N X i=0 N i!xiyN−i has been used. ✷ P ope y 5 Suppose ha Lis a posi i e in ege and ha sis a s ic ly posi i e scala . Then, L P k=1 1 ks≤ Φ(s, ⌈log2L⌉)whe e, gi en s≥0and he in ege ≥0, Φ(s, ) :=          1−2(1−s)( +1) 1−21−si s6= 1 + 1 o he wise. P oo : Gi en L > 0 and s > 0, de ine := ⌈log2(L)⌉and S( ) := 2 P k=1 1 ks. Then we ha e L P k=1 1 ks≤ 2 P k=1 1 ks=S( ). Nex we show ha S( )≤1 + 21−sS( −1) o e e y in ege g ea e han 0. Since S(0) = 1 and S(1) = 1 + 2−s, he inequali y is clea ly sa is ied o = 1. We now p o e he inequali y o g ea e han 1 S( ) = 2 X k=1 1 ks= 2 −1 X k=1 1 (2k)s+1 (2k−1)s = 2−s 2 −1 X k=1 1 ks+ 2 −1 X k=1 1 (2k−1)s ≤2−sS( −1) + 1 + 2 −1 X k=2 1 (2k−2)s = 2−sS( −1) + 1 + 2−s 2 −1−1 X k=1 1 ks ≤2−sS( −1) + 1 + 2−s 2 −1 X k=1 1 ks = 1 + 21−sS( −1). We ha e he e o e p o ed he inequali y S( )≤1 + 21−sS( −1) o e e y in ege g ea e han 0. Using his inequali y in a ecu si e way wi h S(0) = 1 we ob ain S( )≤ P k=0 2(1−s)k= Φ(s, ).This p o es he esul . ✷ 16