EfficientAlgorithmsforUniversalPortfolios
AdamKalaiSantoshVempala
DepartmentofMathematics
MassachusettsInstituteofTechnologyCambridgeMA,02139Editor:PhilipM.Long
akalai@mit.edu
vempala@math.mit.edu
Abstract
Aconstantrebalancedportfolioisaninvestmentstrategythatkeepsthesamedistributionofwealthamongasetofstocksfromdaytoday.TherehasbeenmuchworkonCover’sUniversalalgorithm,whichiscompetitivewiththebestconstantrebalancedportfoliode-terminedinhindsight(Cover,1991,Helmboldetal,1998,BlumandKalai,1999,FosterandVohra,1999,Vovk,1998,CoverandOrdentlich,1996a,Cover,1996c).Whilethisal-gorithmhasgoodperformanceguarantees,allknownimplementationsareexponentialinthenumberofstocks,restrictingthenumberofstocksusedinexperiments(Helmboldetal,1998,CoverandOrdentlich,1996a,OrdentlichandCover,1996b,Cover,1996c,BlumandKalai,1999).WepresentanefficientimplementationoftheUniversalalgorithmthatisbasedonnon-uniformrandomwalksthatarerapidlymixing(ApplegateandKannan,1991,LovaszandSimonovits,1992,FriezeandKannan,1999).Thissameimplementationalsoworksfornon-financialapplicationsoftheUniversalalgorithm,suchasdatacompression(Cover,1996c)andlanguagemodeling(Chenetal,1999).
1.Introduction
Aconstantrebalancedportfolio(CRP)isaninvestmentstrategywhichkeepsthesamedistributionofwealthamongasetofstocksfromdaytoday.Thatis,theproportionoftotalwealthinagivenstockisthesameatthebeginningofeachday.Recentlytherehasbeenworkonon-lineinvestmentstrategieswhicharecompetitivewiththebestCRPdeterminedinhindsight(Cover,1991,Helmboldetal,1998,BlumandKalai,1999,FosterandVohra,1999,Vovk,1998,CoverandOrdentlich,1996a,OrdentlichandCover,1996b,Cover,1996c).Specifically,thedailyperformanceofthesealgorithmsonamarketapproachesthatofthebestCRPforthatmarket,choseninhindsight,asthelengthsofthesemarketsincreasewithoutbound.
AsanexampleofausefulCRP,considerthefollowingmarketwithjusttwostocks(Helmboldetal,1998,OrdentlichandCover,1996b).Thepriceofonestockremainsconstant,andthepriceoftheotherstockalternatelyhalvesanddoubles.Investingina
1
singlestockwillnotincreasethewealthbymorethanafactoroftwo.However,a(12,2)CRPwillincreaseitswealthexponentially.Attheendofeachdayittradesstocksothatithasanequalworthineachstock.Onalternatedaysthetotalvaluewillchangebyafactor
c2002AdamKalaiandSantoshVempala.
KalaiandVempala
113113
of12(1)+2(2)=4and2(1)+2(2)=2,thusincreasingtotalworthbyafactorof9/8everytwodays.
ThemaincontributionofthispaperisanefficientimplementationofCover’sUNIVER-SALalgorithmforportfolios(Cover,1991).Ithasbeenshown(CoverandOrdentlich,1996a)that,inamarketwithnstocks,overtdays,
performanceofUNIVERSAL1
≥.
performanceofbestCRP(t+1)n−1Byperformance,wemeanthereturnperdollaronaninvestment.Theaboveratioisa
decreasingfunctionoft.However,theaverageper-dayratio,(1/(t+1)n−1)1/t,increasesto1astincreaseswithoutbound.Forexample,ifthebestCRPmakes1.5timesasmuchaswedoeachdayoveraperiodof22years,itisonlymakingafactorof1.51/22≈1.02asmuchaswedoperyear.Inthispaper,wedonotconsidertheDirichlet(1/2,...,1/2)UNIVERSAL
(CoverandOrdentlich,1996a)whichhasthebetterguaranteedratioof21/(t+1)n−1.
AllpreviousimplementationsofCover’salgorithmareexponentialinthenumberofstockswithworst-caseruntimesofΘ(tn−1).Insomesense,Cover’salgorithmdividesitsmoneyevenlyamongallCRPs.Unfortunately,forsomemarketsequences,thenumberofCRPswhichperformnearoptimallycanbeassmallas1/Θ(tn−1).Inthesecases,BlumandKalai’srandomizedapproximationbasedonsamplingfromtheuniformdistribution,requiresΘ(tn−1)samplestoperformnearlyaswellasUNIVERSAL,withhighprobability.
Weshowthatbysamplingportfoliosfromanon-uniformdistribution,onlypolynomi-allymanysamplesarerequiredtohaveahighprobabilityofperformingnearlyaswellasUNIVERSAL.Thisnon-uniformsamplingcanbeachievedbyrandomwalksonthesimplexofportfolios.
2.NotationandDefinitions
Apricerelativeforagivenstockisthenonnegativeratioofclosingpricetoopeningpriceduringagivenday.IfthemarkethasnstocksandtradingtakesplaceduringTdays,then
x2,...,xT),xi∈themarket’sperformancecanbeexpressedbyTpricerelativevectors,(x1,
j
n+,wherexiisthenonnegativepricerelativeofthejthstockfortheithday.
Aportfolioissimplyadistributionofwealthamongthestocks.Assuch,itisreallyann−1dimensionalquantitywherethelastcomponentcanbedeterminedfromtheothern−1.Weviewthesetofportfoliosasthe(n−1)-dimensionalsimplex,
∆={b∈n−1|
n−1j=1
bj≤1∧bj≥0}.
Wealsoconsideraportfolioalsoasann-dimensionalvector,where
bn=1−
n−11
bj.
Thisabuseofnotationallowsustoviewtheportfolioasanncomponentvectorandthe
setofportfoliosasan(n−1)-dimensionalset,whereverconvenient.Thisisespecially
424
AlgorithmsforUniversalPortfolios
valuable,sincetherandomwalkresultwewillbeusing(FriezeandKannan,1999)isforafull-dimensionalsetsuchas∆.
,redistributesitswealthTheCRPinvestmentstrategyforaparticularportfoliob,CRPb
attheendofeachdaysothattheproportionofmoneyinthejthstockisbj.Aninvestmentusingaportfoliobduringadaywithpricerelativesxincreasesone’swealthbyafactorof
nis,b·x=1bjxj.Therefore,overtdays,thewealthachievedbyCRP
b
b)=Pt(
ti=1
b·xi.
(1)
Finally,weletµbetheuniformdistributionon∆.
3.UniversalPortfolios
Beforewedefinetheuniversalportfolio,considertheproblemofbeingcompetitivewith
respecttothebestsinglestock.Inotherwords,youwanttomaximizetheworst-caseratioofyourwealthtothatofthebeststock.Inthiscase,agoodstrategyissimplytodivide
1
timesasyourmoneyamongthenstocksandletitsit.Youwillalwayshaveatleastnmuchmoneyasthebeststock.Notethatthisdeterministicstrategyachievestheexpectedwealthoftherandomizedstrategythatjustplacesallitsmoneyinarandomstock.
NowconsidertheproblemofcompetingwiththebestCRP.Cover’suniversalportfolioalgorithmissimilartotheabove.ItsplitsitsmoneyevenlyamongallCRPsandletsitsitintheseCRPstrategies.(Itdoesnottransfermoneybetweenthestrategies.)Likewise,italwaysachievestheexpectedwealthoftherandomizedstrategywhichinvestsallitsmoneyinarandomCRP.Inparticular,thebookkeepingworksasfollows:
Definition1(UNIVERSAL)Theuniversalportfolioalgorithmattimethasportfoliout,whichforstockjis,onthefirstdayuj0=1/n,andontheendofthetthday,
j
v)dµ(v)∆vPt(uj,i=1,2,...=t
P(v)dµ(v)t∆(Recallthatµistheuniformdistributionoverthe(n−1)-dimensionalsimplexofportfolios,
∆.)
ThisistheforminwhichCoverdefinesthealgorithm.Healsonotes(CoverandOr-dentlich,1996a)thatUNIVERSALachievestheaverageperformanceofallCRPs,i.e.,
PerformanceofUNIVERSAL=
=
∆Tt=1
ut−1·xtPT(v)dµ(v)
4.EfficientApproximation
Unfortunately,thestraightforwardmethodofevaluatingtheintegralinthedefinitionof
UNIVERSALtakestimeexponentialinthenumberofstocks.SinceUNIVERSALisreally
425
KalaiandVempala
justanaverageofCRP’s,itisnaturaltoapproximatetheportfoliobysampling(BlumandKalai,1999).Simplyimaginedividingthewealthintomanyrandomportfoliosandseewhatdistributionofwealthonewouldhave.Inparticular,youwouldjusttakeaweightedaverageoftheportfoliosyou’vechosen,withweightsproportionaltotheirperformance.Theproblemisthattheremaybeaverysmallsetofportfoliosthatdidwellwhilemostportfoliosdidverypoorly.Inordertogetagoodsample,onewouldneedtogetadrawfromthisset,whichcanrequireΩ(tn−1)samplesintheworstcase.
Thekeytoouralgorithmissamplingaccordingtoabiaseddistribution.Insteadofsamplingaccordingtoµ,theuniformdistributionon∆,wesampleaccordingtoρt,whichweightsportfoliosinproportiontotheirperformance,i.e.,
b)dµ(b)Pt(dρt(b)=v)dµ(v)∆Pt(
UNIVERSALcanbethoughtofascomputingeachcomponentoftheportfoliobytakingjjtheexpectationofdrawsfromρt,i.e.,ujv)=Ev∈ρtv.t=∆vdρt(
Weuseexistingrandomwalktheoremstoshowonecansamplefromρtintimepolyno-mialintandn.Thecurrentbestprovableboundsareforsamplingonadiscretizationofthesimplex,althoughmanyotherrandomwalksmightalsowork.Forthepurposeofthisrandomwalk,wewillneedthefollowingmodificationQtofthewealthfunctionPt:
n
−2δb0
Qt(,1.(2)b)=Pt(b)minexp
nδR-UNIVERSAL(δ0,δ,m,S)//δ0=minimumcoordinate//δ=spacingofgrid
//m=numberofsamples
//S=numberofstepsinrandomwalk
Oneachday,wetaketheaverageofmsamplesobtainedasfollows:
111
1.Starteachoneatthepointr=(n,n,...,n).
2.Fromeachofthem,takeSstepsofthefollowingrandomwalk:
(a)Choose1≤j≤n−1atrandom
//We’lltrytoincrementordecrementrjwithequalprobability.(b)ChooseX∈{−1,+1}randomly.Ifδ0≤ri+Xδandδ0≤rn−Xδ,
i.Letx:=Qt(r1,r2,...,rn).
ii.Lety:=Qt(r1,r2,...,rj+Xδ,...,rn−1,rn−Xδ).iii.WithprobabilityMin(1,x/y),
•rj:=rj+Xδ•rn:=rn−Xδ
ThefunctionQtisaslightly“damped”versionofPt:itisequaltoPtonaslightlysmallersimplex,namelytheset{b∈∆|bn≥2δ0}andfallsoffrapidlyoutsidethisset.We
426
AlgorithmsforUniversalPortfolios
introduceitfortechnicalreasons;itisquitepossiblethatthealgorithmbelowworkswithPtinplaceofQt(seeSection7).Theparameterδ0willbespecifiedinSection5.3.Wealsoonlysamplegridpointswhosecoordinatesareatleastδ0each(againfortechnicalreasons).WerefertothealgorithmasR-UNIVERSALbecauseit’sarandomizedapproximation.
AlsoQtcanbeevaluatedintimeO(nt).ThustheruntimeofthealgorithmondaytisO(mSnt).Intheanalysissection,wewillshowthatmandScanbechosentobepolynomialinnandt.
5.Analysis
Hereweshowthat,withnon-uniformsampling,thealgorithmapproximatestheportfolioefficiently.Withhighprobability(1−η),wecanachieveperformanceofatleast(1−)timestheperformanceofUNIVERSAL,withS(numberofsteps)polynomialin1/,log(1/η),n(thenumberofstocks),andT(thenumberofdays).Wewillshowthefollowing:Theorem2ThereisaconstantAsuchthat,forall,η,δ,andδ0with
δ0≤
δ01=,δlog,
8nT(n+T)2δA(n+T)2Tm≥64T2(n+T)ln(nT/η)/2samplesoneachday,andS≥Anlogn+δstepsoftherandomδ2walkpersample,R-UNIVERSALperformsatleast(1−)timesaswellasUNIVERSALwithprobabilityatleast1−η.
Aswillbecomeclearinthenexttwosections,therandomwalk,whichisthebasisofoursamplingalgorithm,tendstoastationarydistributionproportionaltothefunctionQt.Thekeyobservationthatleadstoapolynomial-timeimplementationisthefactthatQtisalog-concavefunction(asisPt).Suchfunctionscanbesampledinpolynomial-time,albeitwithseveraltechnicalrestrictions.Itisthelatterthatforceustointroducetheparameterδ0andalsotouseQtinsteadofjustPt.UsingFriezeandKannan’stheorem(ourTheorem3),weshowthattherandomwalkquicklyconvergestoitsstationarydistribution(Theorem11)inSection6.
Itthenremainstoshowthattheapproximationprovidedbytherandomwalkissufficientforthealgorithm.ThisisdoneinSection5.3.TheabovetheoremfollowsfromTheorems4and11.Let’sbeginbydescribingwhathasbeenanalyzed.5.1AnalysisOverview
Tocomputeut,WewouldliketocomputetheexpectationofrandompointsdrawnaccordingtothedistributionPt.Aswewillshow,Ptisalog-concavefunction.Thissuggestsusingexistingtechnologybasedonrandomwalksforsamplingfromlog-concavedistributions(FriezeandKannan,1999)overanarbitraryconvexsetK.However,theiralgorithmsworkbydiscretizingspaceintocubesandsamplingfromcubecenters.OneimportantparameteroftheiralgorithmisthetotalprobabilityofcubesthatarenotcompletelycontainedinK.Inourapplication,theshapeofoursetisasimplex,soitisimpossibletodiscretizeitinsuchawaythattherearefewsuchbordercubes.However,wewillshowthatthemeanofPtisnotneartheborderofthesimplex.Then,weuseadampedfunctionQttoreducethe
427
KalaiandVempala
probabilityofbordercubes,insuchawaythatthemeanofQtisneartothemeanofPtandQtislog-concavewhilesufficientlysmallnearthebordersofthesimplex.5.2SummaryofFrieze-Kannan’97(FriezeandKannan,1999)
Supposeyouhavesomenonnegativelog-concavefunctionfonn,meaningsimplythatlogfisaconcavefunction.ThegoalistosamplefromfrestrictedtosomeconvexsetK⊂n.Theyfirstdividethespaceintocubesofsidelengthδ.Thespacingδhastobe
Figure1:AconvexsetKandthesetofallcubesthatintersectK.Thecentersofthese
cubesformthesetC,whileC1/2isthesetofcentersofthecubesthathavemorethanhalfoftheirvolumeintheset.Thesecubesaretheunshadedcubes.smallenoughsothatthefunctionfvariesbyafactorofatmostaconstantfactorwithinacube.ThentheyperformallfutureoperationsonthecentersofthecubeswhichintersectK,asetcalledC,asshowninthefigure.LetC(x)bethecubecenteredatx∈Cofwidthδ.
Considerthefollowingwalk.•Startatsomearbitrarycubecenterx∈C.
•Choosearandomcoordinateandaddorsubtractδinthatcoordinatewithequalprobability,togetanothercubecentery.•Ify∈C(haven’tsteppedoutoftheset),thenmovetoywithprobabilitymin(1,f(y)/f(x)).Theyfirstobservethatthestationarydistributionofthiswalkis
π(x)=f(x)
x)x∈Cf(
∀x∈C
Thisfollowsfromthefactthatthewalkistimereversible.Thatis,whenintheabove
distribution,onasinglestep,theprobabilityofbeingatxandmovingtoyisequaltothe
428
AlgorithmsforUniversalPortfolios
probabilityofbeingatyandgoingtox,i.e.,
1f(y)f(x)
min1,=)2nf(xf(x)x∈C
=
1
min(f(y),f(x)))2nf(xx∈C
f(y)1f(x)min1,.)2nf(xf(y)x∈C1
Now,thereareseveralparametersfortheanalysisofthiswalk.ThediameterofKis
d.Thedimensionalityisn.Thestationarydistributionisπ,andπ∗=minπ.Letpsbethedistributionobtainedaftersstepsofthewalk.Forany0≤θ≤1,letCθ={x∈
(x)p(x)p00x).Finally,letM=maxC|vol(C(x)∩K)≥θδn}andπθ=x∈Cπ(x∈/Cθπ(x)logπ(x).Theorem3(Theorem1ofFriezeandKannan,1999)Assumed≥δn1/2.Thenthereis
anabsoluteconstantγ>0suchthat,
2γsδ2Mπ1/2nd21−2+2|ps(x)−π(x)|≤endlog.π∗γδ2x∈C
Inourproblem,thedimensionalityisactuallyn−1iftherearenstocks,butthiscanbe
absorbedbyγ.ForusMcanbeverylarge,butwe’llchooseparametersthatmakeπ1/2smallenoughtocompensate.5.3ApproximationSuffices
ToapplyTheorem3,wefirstneedtoensurethatπvariesbyatmostaconstantfactorwithintheδ-cubearoundanygridpoint.Thisisthetechnicalreasonwhyweuseaslightlysmallersimplex∆.Inthefullsimplex∆,thefunctionPt(andhenceρt)canvaryalotwithinasmalldistance.Inthissection,weshowthatthisapproximationisgoodenoughforthealgorithm.
Therandomwalkactuallysamplesfromthefollowingsimplex:
v∈∆|vj≥δ0forj=1,2,...,n}.∆={
LetCdenotethesetofcubecenterscontainedin∆.Thestationarydistributionofthe
x∈C,walkisproportionaltoQt;letitbecalledπt.Notethatforany
x)=πt(
x)Qt(
.Q(y)ty∈C
Lettheactualdistributionobtainedonthem(aftersomenumberofstepsoftherandom
walk)beπ˜t.Themaintheoremofthissectionshowsthatthissufficesaslongasπ˜tissufficientlyclosetoπt.
0,δ≤8T(δTheorem4Supposethatδ0≤8nT(nn+T),andwecansamplegridpointsin+T)2thesimplex∆accordingtoadistributionπ˜twhere
.|π˜t(x)−πt(x)|≤
4T(n+T)
x∈C
Thenwithm≥64T2(n+T)ln(nT/η)/2,thealgorithmR-UNIVERSALperformsatleast
(1−)aswellasUNIVERSALwithprobabilityatleast1−η.
429
KalaiandVempala
Toprovethetheorem,wewillneedseverallemmas.First,weobservethatsubsetsofthesimplexofsufficientsizewillhavelargevolumeunderρt.
Lemma5Letβbeasubsetofthesimplex,shrunkenbyafactorof1−zfor0≤z≤1,i.e.,forsomew∈∆,
,v∈∆}.β=zw+(1−z)∆={v∈∆|v=zw+(1−z)v
(3)
Theprobabilitythatarandomportfolioselectedinproportiontoitsperformanceisinβisatleast,
ρt(β)≥(1−z)t+n−1Proof.Geometrically,βisalsoasimplex,translatedbywandshrunkenbyafactorof(1−z).Sincethesimplexhasdimensionn−1,thissethasvolumeatleast,
µ(β)=(1−z)n−1,
undertheuniformmeasureµonthesimplex.
∈∆.Furthermore,Asindicatedin(3),thereisasimplebijectionbetweenv∈βandv
onanydaytheperformanceofvmustbeatleast(1−z)timesasgoodastheperformance
sincea(1−z)fractionofitsholdingsaredistributedexactlylikeofthecorrespondingv
.Overtdays,weseethatv
)v)≥(1−z)tPt(vPt(Consequently,theperformanceofauniformlyrandomportfolioinβisatleast(1−z)tas
goodasauniformlyrandomportfolioin∆.Sincea(1−z)n−1fractionoftheportfoliosareinβ,
ρt(β)≥(1−z)t(1−z)n−1=(1−z)t+n−1
Acorollary,whichwewilluselateris,Corollary6Forallj≤nandt,
ujt≥
1
n+t
Proof.WLOGj=1.Usingthelemma,itiseasytoseethatu1t≥1/(e(n+t)).Thisis
111becauseut=Eρt[v]andthesetofportfolioswithv≥1/(n+t)hasvolumeatleast1/e,
i.e.,
t+n−1
1111ρt≥(1,0,0,...,0)+1−∆≥1−
n+tn+tn+teToremove1the1/efactor,notethattheexpectationofarandomvariable0≤X≤1is
E[X]=0Prob(X≥z)dz.
1
u1v∈ρt[v]t=E
1=ρt({v∈∆|v1≥z})dz
0
430
AlgorithmsforUniversalPortfolios
=
≥=
0
1
,v∈∆})dzρt({v∈∆|v=z(1,0,0,...,0)+(1−z)v(1−z)t+n−1dz
1
1
n+t
0
Lemma7ForanygridpointzinC,andanypointv∈C(z),wehave
z)≤Pt(v)≤(1+δ/δ0)TPt(z).(1−δ/δ0)TPt(
Proof.Sincev∈C(z)andz∈∆,
vj
≤zj+δ≤(1+δ/δ0)zj
(Theaboveholdsforδ/2aswell.)Therefore,overtdays,
v)=Pt(
≤
ti=1
ti=1
v·xi
(1+δ/δ0)z·xi
=(1+δ/δ0)tPt(z)
TheRHSfollowsfromt≤T,andtheotherinequalityissimilar.
Themainlemmaofthissectionisthefollowing.Itsaysthattheaverageover∆isclose
totheonecomputedbyUNIVERSALover∆.
Thenforeachstockjonanydayt,jj
Eπt[v]≥1−ut.
2T
Proof.Theuniversalportfoliois
utvjdρt(v)j=
∆
Pt(v)vjdµ(v)∆
=v)dµ(v)∆Pt(Lemma8Letδ0≤
,8nT(n+T)2δ≤
δ08T(n+T).
(4)
WearesamplingthefunctionQtovercubecenterscontainedin∆ratherthantheset∆.Whatwehaveis,
j
Eπt[v]=πt(v)vj
v∈∆
=
v)vjv∈CQt(.Q(v)tv∈C
(5)
431
KalaiandVempala
So,inordertoprovethelemma,wehavetoshowthatin(5),thenumeratorislargeenoughandthedenominatorissmallenoughcomparedtothequantitiesin(4).
Now,byLemma7,wecansaythattheintegraloveracubeisboundedbyitsvalueinthecenterz,i.e.,
1
(1−δ/δ0)TPt(z)≤Pt(v)dµ(v),and
δn−1v∈C(z)
1
(1+δ/δ0)T+1Pt(z)zj≥Pt(v)vjdµ(v)n−1δv∈C(z)Alsonoticethattheunionofallcubeswithcentersin∆iscontainedin∆.Toseethis,
takeanygridpointz∈Candv∈C(z).Clearlythefirstn−1coordinatesofvareallatleastδ0−δ/2>0andthenthcoordinateis,
v
n
=z+
n
n−11
zj−vj
≥δ0−nδ/2≥0.
v)≤Pt(v)forallpoints,thedenominatorin(5)isatmost,Sov∈∆.SinceQt(
11
Qt(v)≤Pt(v)dµ(v)Tδn−1(1−δ/δ)0v∈∆
v∈C
Inordertolowerboundthenumeratorof(5),weconsidertheset∆whichisentirely
containedintheunionofcubeswithcentersin∆,
∆={v∈∆|vn≥2δ0}.
Toseethat∆iscontainedinthisset,takeanypointv∈∆andletzbethecenterofthe
cubethatcontainsit.Sincevj≥δ0for1≤j≤n−1,wealsohave1zj≥δ0+δ/2.Finally,vn≥2δ0so
zn=vn+
n−11
vj−zj
≥2δ0−nδ/2≥δ0.
Thisshowsthatz∈∆.
v)=Qt(v)Since∆isentirelycontainedintheunionofcubeswithcentersCandPt(
forv∈∆,11
Qt(v)vj≥Pt(v)vjdµ(v)Tn−1(1+δ/δ)δ0z∈∆
v∈C
1.Wehavechosenδ0andplacedthegridsothat(δ0,δ0,...,δ0)∈n−1isacornerofacube.
432
AlgorithmsforUniversalPortfolios
Puttingthesetogetherwith(5),weget
v)vjv∈CQt(j
Eπt[v]=v)v∈CQt(
v)vjdµ(v)1−δ/δ0T+1Pt(v∈∆≥
1+δ/δ0v)dµ(v)v∈∆Pt(
vjdρt(v)≥(1−2δ/δ0)T+1
v∈∆
≥(1−2(T+1)δ/δ0)vjdρt(v)
v∈∆
WeneedtocomparethistoUNIVERSAL,whichisanintegraloverallof∆.UsingLemma
5ontheset,
β=(δ0,δ0,...,δ0,2δ0)+(1−(n+1)δ0)∆,weget,
ρt(∆)≥(1−(n+1)δ0)T+n−1
≥1−(T+n−1)(n+1)δ0
≥1−
4T(n+T)
Hence,
∆
vjdρt(v)=
≥≥
∆
ujt−ujt−
vjdρt(v)−
∆\\∆
vjdρt(v)
ρt(∆\\∆)
j
≥(1−)u.
4T(n+T)4Tt
Thisfinallyimpliesthat
j
)uEπt[vj]≥(1−2(T+1)δ/δ0)(1−
4Tt
j
≥(1−2(T+1))(1−)u
8T(n+T)4Tt
j
≥(1−)(1−)u
4T4Ttj)u.≥(1−
2Tt
Proof(ofTheorem4).
Wewillfirstshowthatoneachday,theexpectedvalueofeachstockjascomputedbythealgorithmisclosetoujt.
jj
|π˜t(v)−πt(v)|vj|Eπ˜t[v]−Eπt[v]|≤
v∈C
433
KalaiandVempala
≤≤≤
v∈C
|π˜t(v)−πt(v)|
4T(n+T)ju.4Tt
Herewehaveusedtheassumptionofthetheoremthatπ˜tisclosetoπtandthenCorollary
j
6whichstatesthateachutisatleast1/(n+t).
Next,usingLemma8,wehavethat
jjj
Eπu˜t[v]≥Eπt[v]−
4Ttjj)ut−u≥(1−2T4Tt3j
≥(1−)u.
4Tt
Finally,weapplyChernoffboundstoshowthatwithprobability1−η,thevalueajtofeachstockjoneachdaytsatisfies
ajt≥(1−
j
)u.Tt
Then,onanyindividualday,theperformanceoftheatisatleast(1−/T)timesasgoodastheperformanceofut.Thus,overTdays,ourapproximation’sperformanceisatleast(1−/T)T≥1−timestheperformanceofUNIVERSAL.
ThemultiplicativeChernoffboundforapproximatingarandomvariable0≤X≤1,
¯,bythesumSofmindependentdrawsis,withmeanX
¯2
¯PrS<(1−α)Xm≤e−mXα/2.
¯≥1/2(n+T)andweInourcase,weareusingmsamplesforeachstock.InourcaseX
wantα=/4T.SincethismustholdfornTdifferentajt’s,itsufficesfor,
e−m
2/(64T2(n+T))
≤
η
,nT
whichholdsforthenumberofsamplesmchoseninthetheorem.
6.TimePerSample
Inthissectionweshowthattherandomwalkquicklyproducessamplesfromadistributionπ˜(x)satisfyingtherequirementsofTheorem4.TherandomwalkhasstationarydistributionproportionaltoQt.WebeginwiththeobservationthatQtislog-concave.Lemma9ThefunctionQt(b)islog-concavefornonnegativevectors.
434
AlgorithmsforUniversalPortfolios
Proof.First,weprovethatPtislog-concave.Thisfollowseasilyfromtheconcavityofthelogfunction.
ta+ba+b
=log·xilogPt
22
i=1
==≥=
n
ti=1
ti=1ti=1
a+blog·xi
2b·xia·xi+
log
2loga·xi+logb·xi
2
logPt(a)+logPt(b)
2
2δ0n1Nextweobservethatexp(b−nδ)isalog-concavefunction(itslogislinearinb=1−b−
···bn−1);finallywerecallthattheminimumoftwolog-concavefunctionsislog-concave,andsoistheirproduct.
Themainissueishowfasttherandomwalkapproachesitsstationarydistribution,πt,whichisproportionaltoQt(x).ToanalyzethiswewillusethetheoremofFriezeandKannan.Toapplytheirtheorem,wefirstneedtoensurethatπtvariesbyatmostaconstantfactorwithintheδ-cubearoundanygridpoint.Inthefullsimplex∆,thefunctionPt(andhenceρt)canvaryalotwithinasmalldistance.2Withthesmallersimplexhowever,thevariationcanbeboundedusingLemma7.Corollary10Withδ≤
δ0T,
foranygridpointz∈Candanyv∈C(z),
1
Qt(z)≤Qt(v)≤5Qt(z).5
Proof.¿FromLemma7,
(1−1/T)TPt(z)≤Pt(v)≤(1+1/T)TPt(z).
Thisgivesboundsof1/eandeontheLHSandRHS,respectively.Also,wecanboundthe
maximumdifference,
−1nnnjj|z−v|=v−z<δn/2
1
)/Pt(w)=min(1,exp(wThereforeQt(w
v.Finally,e3/2<5.
n−2δ0nδ))differsbyatmostafactorofe1/2atzand
2.Forexample,oneCRPmayhave0performancePtwhilethecenterofitscubemayhavenonzeroperformance
435
KalaiandVempala
Consideranyparticulardayt,andletthedistributionattainedbytherandomwalkaftersstepsbeps,i.e.ps(x)istheprobabilitythatthewalkisatthegridpointxafterssteps.Thenexttheoremboundstheprogressoftherandomwalktowardsitsstationarydistribution.
Theorem11ThereisaconstantAsuchthatwithδ0 Anδ2Tlogn+δsteps, 1 ,(n+T)2δlog1δ=δ0,A(n+T)2and x∈C |ps(x)−πt(x)|≤ √ . 4T(n+T) Proof.Thediameterofoursetis2.ApplyingthetheoremofFriezeandKannanwegetthat 22Mπ1/2nsγδ21 +|ps(x)−πt(x)|≤e−2nlog(6)22πγδ∗ x∈C whereγ>0isaconstant,π∗isminz∈Cπ(z),and π1= 2 x∈C: vol(C(x)∩∆)1≤2vol(C(x))π(x). p0(z)p0(z)than1fractionoftheirvolume.TheparameterMismaxlogz∈C2πt(z)πt(z). Therearetwotermsin(6).IfthesetKwe’resamplingfromwereaperfectcube,thenwewouldhavenocubesthatwereonlypartlyinK,andπ1/2inthesecondtermwouldbe0.Whileitwouldprobablybepossibletoreprovetheirtheoremwithsimplexesratherthancubes,insteadwechosetomodifythewalktomakeπ1/2verysmall.Aswewillshow,the Inwords,π1/2istheprobabilityofthegridpointswhosecubesintersectthesimplexinless dampingterminQtdoesexactlythat,reducingbordercubesbyafactorofe−nδ.Withthevalueofδ0wehavechosen, e 0−nδδ δ0=δ A(n+T)2 n,(7) aquantitythatissmallerthanbasicallyanyotherquantitywearedealingwith,forsuffi-cientlylargeA. Firstweboundπ∗.Foranyv,w∈∆,weseethatvj≥δ0wj,for1≤j≤n,sothateachdayCRPvdoesatleastδ0aswellasCRPw.Thisimpliesthat T v)≥δ0Pt(w)Pt( T−nδQt(v)≥δ0eQt(w) v)Qt( v)=πt( )w∈CQt(w T−nδe/(#cubes)≥δ0 δ0δ0436 AlgorithmsforUniversalPortfolios Becauseδ−nisanupperboundonthenumberofcubes(theyallfitinsidetheunitcube)and(7), 1π∗ ≤ 0−Tnδδ−nδ0e δ ≤δ −2 A(n+T)2 n(8) NextweboundM.Leto=(1/n,1/n,...,1/n).Sincewearestartingwithp0(o)=1,wehaveM=log(1/πt(o))/πt(o).Followinglogicsimilartoabove,ifvisanyportfolio,theneachdayCRPodoesatleast1/naswellasCRPv.So,overtdays, Pt(o)≥n−TPt(v)o)≥n−T/(#cubes)πt( ≥n−TδnM ≤nTδ−nlog(nTδ−n)≤δ−2n−2T Toboundπ1,wedefineKtothebethefollowingset: 2(9) K={y∈∆|yn≥δ0+(n−1)δ/2}. WiththisdefinitionofK,FriezeandKannan’swalkbecomesexactlythewalkinR-UNIVERSAL.Toshowthis,wemustshowthatthesetofcentersofcubesthatintersectKisexactlyC.Recallthat(δ0,δ0,...,δ0)∈n−1waschosenasacornerofacube.First, j≥δforsupposev∈Kandv∈C(z)forgridpointz.Now,becauseofourgridposition,z0n−1j nnjnnj=1,2,...,n−1.Further,z=v+1v−zsoz≥v−(n−1)δ/2,whichmeans thatz∈∆.Conversely,supposez∈C,sozj≥δ0+δ/2forj z∈/K,i.e.,δ0≤zn<δ0+(n−1)δ/2.Thatisbecausethosepointszsuchthatz∈Cbut anycutthroughthecenterofacubedividesitintotwocongruentpieces,soanycutthatdoesnotpassthroughthecenterdividesitintoalargerandsmallerpiece,withthecenterinthelargerpiece.LetthissetofgridpointsbedenotedbyF.Foranyz∈F, −δ0+nδ/2 Qt(Pt(z)≤expz) nδ ≤e−nδe1/2Pt(z). Moreover,ifδ0were1/(n+T)thenatmosta1−1/efractionofPtwouldbein∆\\∆, byLemma5.Theδ0weareusingismuchsmaller,3sowecaneasilysay, Pt(v)≤Pt(v), v∈Fv∈C 13.Thisistheonlyreasonwehaverequiredδ0<(n+,whichisprobablysmallerthannecessaryatthisT)2point.Butthefinalδ0willbemuchsmalleranyway. δ0437 KalaiandVempala andthus, v∈F Qt(v)≤e 01/2−nδδ e v∈C Pt(v). v∈C,SincePt=Qtfor π1/2≤e =δ 01/2−nδδ e A(n+t)2 ne1/2 Anδ2Tlogn+δ, (10) Substituting(8),(9),and(10)into(6)andusings≥ 2 2 |ps(x)−πt(x)| ≤δ n+T Aγ/2 2A(n+ n T)2 x∈C 1 log+ δ 2δ−2n−2Tδ A(n+t)2 ne1/2n γδ2. Sinceδ1/<,bothtermsontherighthandsidebecomesmallerthan/(n+T)toanyconstantpowerforsufficientlylargeA. 7.PracticalConsiderations Inthissection,wegivesomesuggestionswhichmayhelpspeedthingsupinpractice.Ouralgorithmhasanunnaturalasymmetryinthatwetreatcoordinatendifferentlythantherest.IfitwerenotforthetaperingfunctionQt,thenonecouldpicktwoarbitrarycoordinatesi=j,increasevi,anddecreasevj.Alternatively,onecoulddotaperinginanydirection.Thetaperingseemstobeanartifactofouranalysisandthefactthatwearetryingtoanalyzeawalkonasimplexbyagrid.Thisislikefittingatriangularpegintoasquarehole.Itseemsmorenaturaltoimplementitwithoutanytapering. EvaluatingPtcanbecostlyforlongmarketsequences.Wecansavesomeevaluationsasfollows.Imaginethatthewaywebranchinstep(iii)isbychoosingarandomα∈[0,1]andcheckingifα Thenaivesamplingapproachdescribedearlier,i.e.pickrandomportfoliosandaveragethemweightedbytheirperformance,hasbeenshowntorequireanumberofsamplesthatisontheorderoftheratiooftheperformanceoftheaverageCRPtothebestCRP.For 438 AlgorithmsforUniversalPortfolios manymarketsorforshortperiodsoftime,thisratiomaybesmall.Thus,forcalmmarketswithsmallchanges,randomwalksareprobablynotnecessary.Inanycase,itwouldbeinterestingtofindthesituationsandimprovementstothealgorithmwhichmakerandomwalksdobetterthanthenaivesamplingapproach. 8.Conclusions WehavepresentedanefficientrandomizedapproximationoftheUNIVERSALalgorithm.Withhighprobability(1−η)itiswithin(1−)timestheperformanceofuniversal,andrunsintimepolynomialinlog(1/η),1/,thenumberofdays,andthenumberofstocks.Withmoney,itisespeciallyimportanttoachievethisexpectation.Forexample,a50%chanceat10milliondollarsmaynotbeasvaluabletomostpeopleasaguaranteed5milliondollars. WhileourimplementationcanbeusedforotherapplicationsofUNIVERSAL,suchasdatacompression(Cover,1996c)andlanguagemodeling(Chenetal,1999),wedonotknowanimplementationforthecaseoftransactioncosts(BlumandKalai,1999)orfortheDirichlet(1/2,...,1/2)UNIVERSAL(CoverandOrdentlich,1996a). Acknowledgments WearegratefultoPhilipLongandtheanonymousrefereesforverymanyhelpfulsuggestionsandimprovements.ThisresearchwassupportedbyNSFCAREERawardCCR-9875024andanNSFpostdoctoralresearchfellowship. References D.ApplegateandR.Kannan.Samplingandintegrationofnearlog-concavefunctions.ProceedingsoftheTwenty-ThirdAnnualACMSymposiumonTheoryofComputing,156-163,1991. A.BlumandA.Kalai.UniversalPortfoliosWithandWithoutTransactionCosts.MachineLearning,35(3):193-205,1999. T.M.Cover.Universalportfolios.Math.Finance,1(1):1-29,1991. T.M.CoverandE.Ordentlich.Universalportfolioswithsideinformation.IEEETransac-tionsonInformationTheory,42(2):348-363,1996. E.Ordentlich.andT.M.Cover.Onlineportfolioselection.Proceedingsofthe9thAnnualConferenceonComputationalLearningTheory,310-313,1996. T.M.Cover.Universaldatacompressionandportfolioselection.Proceedingsofthe37thIEEESymposiumonFoundationsofComputerScience,534-538,1996. A.FriezeandR.Kannan.Log-Sobolevinequalitiesandsamplingfromlog-concavedistri-butions.AnnalsofAppliedProbability,9:14-26,1999. D.P.FosterandR.V.Vohra.RegretintheOn-lineDecisionProblem.GamesandEconomicBehavior,29(1/2):7-35,1999. 439 KalaiandVempala D.Helmbold,R.Schapire,Y.Singer,andM.Warmuth.On-lineportfolioselectionusingmultiplicativeupdates.MathematicalFinance,8(4):325-347,1998. D.Helmbold,R.Schapire,Y.Singer,M.Warmuth.AcomparisonofnewandoldalgorithmsforamixtureestimationProblem.MachineLearning27(1):97-119,1997. A.Kalai,S.Chen,A.Blum,andR.Rosenfeld.On-lineAlgorithmsforCombiningLanguageModels.ProceedingsoftheInternationalConferenceonAccoustics,Speech,andSignalProcessing,2:745-748,1999. R.Kannan,L.LovaszandM.Simonovits.RandomwalksandanO∗(n5)volumealgorithmforconvexbodies.RandomStructuresandAlgorithms,11(1):1-50,1997. A.KalaiandS.Vempala.Efficientalgorithmsforuniversalportfolios.Proceedingsofthe41stAnnualSymposiumontheFoundationsofComputerScience,486-491,2000.L.LovaszandM.Simonovits.Ontherandomizedcomplexityofvolumeanddiameter.ProceedingsoftheIEEESymp.onFoundationofComputerScience,482-491,1992.N.Metropolis,Rosenberg,Rosenbluth,TellerandTeller.Equationofstatecalculationbyfastcomputingmachines.InJournalofChemicalPhysics,21:1087-1092,1953. V.VovkandC.J.H.C.Watkins.UniversalPortfolioSelection.Proceedingsofthe11thAnnualConferenceonComputationalLearningTheory,12-23,1998. 440 因篇幅问题不能全部显示，请点此查看更多更全内容