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