The nested Sinkhorn divergence to learn the nested distance

Pichle , Alois; Weinha d , Michael A icle — Published Ve sion The nes ed Sinkho n di e gence o lea n he nes ed dis ance Compu a ional Managemen Science P o ided in Coope a ion wi h: Sp inge Na u e Sugges ed Ci a ion: Pichle , Alois; Weinha d , Michael (2021) : The nes ed Sinkho n di e gence o lea n he nes ed dis ance, Compu a ional Managemen Science, ISSN 1619-6988, Sp inge , Be lin, Heidelbe g, Vol. 19, Iss. 2, pp. 269-293, h ps://doi.o g/10.1007/s10287-021-00415-7 This Ve sion is a ailable a : h ps://hdl.handle.ne /10419/286812 S anda d-Nu zungsbedingungen: Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen Zwecken und zum P i a geb auch gespeiche und kopie we den. Sie dü en die Dokumen e nich ü ö en liche ode komme zielle Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich machen, e eiben ode ande wei ig nu zen. So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen (insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en, gel en abweichend on diesen Nu zungsbedingungen die in de do genann en Lizenz gewäh en Nu zungs ech e. Te ms o use: Documen s in EconS o may be sa ed and copied o you pe sonal and schola ly pu poses. You a e no o copy documen s o public o comme cial pu poses, o exhibi he documen s publicly, o make hem publicly a ailable on he in e ne , o o dis ibu e o o he wise use he documen s in public. I he documen s ha e been made a ailable unde an Open Con en Licence (especially C ea i e Commons Licences), you may exe cise u he usage igh s as speci ied in he indica ed licence. h ps://c ea i ecommons.o g/licenses/by/4.0/ Compu a ional Managemen Science (2022) 19:269–293 h ps://doi.o g/10.1007/s10287-021-00415-7 ORIGINAL PAPER The nes ed Sinkho n di e gence o lea n he nes ed dis ance Alois Pichle 1 ·Michael Weinha d 1 Recei ed: 10 Feb ua y 2021 / Accep ed: 13 Sep embe 2021 / Published online: 27 Sep embe 2021 © The Au ho (s) 2021 Abs ac The nes ed dis ance builds on he Wasse s ein dis ance o quan i y he di e ence o s ochas ic p ocesses, including also he e olu ion o in o ma ion modelled by il a- ions. The Sinkho n di e gence is a elaxa ion o he Wasse s ein dis ance, which can be compu ed conside ably as e . Fo his eason we employ he Sinkho n di e gence and ake ad an age o he ela ed ( ixed poin ) i e a ion algo i hm. Fu he mo e, we in es iga e he ansi ion o he en opy h oughou he s ages o he s ochas ic p ocess and p o ide an en opy- egula ized nes ed dis ance o mula ion, including a cha ac- e iza ion o i s dual. Nume ical expe imen s a i m he compu a ional ad an age and sup emacy. Keywo ds Nes ed dis ance ·Op imal anspo ·Sinkho n di e gence ·En opy Ma hema ics Subjec Classi ica ion 90C08 ·90C15 ·60G07 1 In oduc ion The Wasse s ein dis ance, also known as Monge–Kan o o ich dis ance, is used in op imal anspo heo y o desc ibe and cha ac e ize op imal ansi ions be ween p ob- abili y measu es. They a e cha ac e ized by he lowes (o cheapes ) a e age cos s o ully ans e a p obabili y measu e in o ano he . The cos s a e mos ypically p opo - ional o he dis ance o loca ions o be connec ed. Rache and Rüschendo (1998) p o ide a comp ehensi e discussion o he Wasse s ein dis ance and Villani (2009) summa izes he op imal anspo heo y. The nes ed dis ance gene alizes and ex ends he heo y om p obabili y measu es o s ochas ic p ocesses. I is based on he Wasse s ein dis ance and has been in oduced Alois Pichle : DFG, Ge man Resea ch Founda ion—P ojec -ID 416228727—SFB 1410. BAlois Pichle [email p o ec ed] 1Facul y o Ma hema ics, Uni e si y o Technology, Chemni z, 90126 Chemni z, Ge many 123 270 A. Pichle , M. Weinha d by P lug (2009), c . also P lug and Pichle (2012). The nes ed dis ance quan i ies he dis ance o s ochas ic p ocesses and mul is age s ochas ic p og ams a e con inuous wi h espec o he nes ed dis ance. Mul is age s ochas ic p og amming has applica- ions in many sec o s, e.g., he inancial sec o (Edi isinghe 2005; B od 1983), in managemen science o in ene gy economics (Analui and P lug 2014; Bel án e al. 2017; Ca pen ie e al. 2012,2015). The p ices, demands, e c., a e o en modeled as a s ochas ic p ocess ξ=(ξ0,...,ξ T)and he op imal alues a e a ely ob ained analy ically. Fo he nume ical app oach he s ochas ic p ocess is eplaced by a ini e alued s ochas ic scena io p ocess ˜ ξ=(˜ ξ0,...,˜ ξT), which is a ini e ee. Na u ally, he app oxima ion e o should be minimized wi hou unnecessa ily inc easing he complexi y o he compu a ional e o . Ki ui e al. (2020) p o ide a Julia package o gene a ing scena io ees and scena io la ices o mul is age s ochas ic p og amming. Maggioni and P lug (2019) p o ide gua an eed bounds and Ho ejšo á e al. (2020) in es iga e co esponding educ ion echniques. This pape add esses he Sinkho n di e gence in place o he Wasse s ein dis ance. This pseudo-dis ance is also called Sinkho n dis ance o Sinkho n loss. In con as o he exac implemen a ion o Be sekas and Cas anon (1989), e.g., Sinkho n di e gence co esponds o a egula iza ion o he Wasse s ein dis ance, which is s ic ly con ex and which allows o imp o e he e iciency o he compu a ion by applying Sinkho n’s ( ixed-poin ) i e a ion p ocedu e. The elaxa ion i sel is simila o he modi ied objec- i e o in e io -poin me hods in nume ical op imiza ion. A co ne s one is he heo em by Sinkho n (1967) ha shows bo h a unique decomposi ion o non-nega i e ma i- ces and ensu es con e gence o he associa ed i e a i e scheme. Cu u i (2013) has shown he po en ial o he Sinkho n di e gence and made i known o a wide audi- ence. Nowadays, Sinkho n di e gence is used in s a is ical applica ions, c . Bigo e al. (2019) and Luise e al. (2018), o image ecogni ion and machine lea ning, c . Kolou i e al. (2017) and Gene ay e al. (2018), among many o he applica ions. Ex ending Sinkho n’s algo i hm o mul is age s ochas ic p og amming has been p oposed ecen ly in T an (2020, Sec ion 5.2.3, pp. 97–99), whe e a nume ical example indica ing compu a ional ad an ages is also gi en. This pape esumes his idea and assesses he en opy elaxed nes ed dis ance om heo e ical pe spec i e. We add ess i s app oxima ing p ope ies and de i e i s con ex conjuga e, he dual. Mo eo e , nume ical es s included con i m he compu a ional ad an age ega ding he simplici y o he implemen a ion as well as signi ican gains in speed. Ou line o he pape The ollowing Sec . 2in oduces he no a ion and p o ides he de ini ions o discuss he nes ed dis ance. Addi ionally, he impo ance o he il a ion and he complexi y o he compu a ion is shown. Sec ion 3in oduces he Sinkho n di e gence and de i e i s dual. In Sec . 4we egula ize he nes ed dis ance and show he equali y be ween wo di e en app oaches. Resul s and compa isons a e isualized and discussed in Sec . 5. Sec ion 6summa izes and concludes he pape . 123 The nes ed Sinkho n di e gence o lea n he nes ed dis ance 271 2 P elimina ies This sec ion ecalls he de ini ion o dis ances gene ally, o he Wasse s ein dis ance and nes ed dis ance and p o ides an example o highligh he impac o in o ma ion a ailable, which is inc easing g adually o e ime and s ages. Th oughou , we shall base ou exposi ion on a p obabili y space (, F,P). 2.1 Wasse s ein dis ance The Wasse s ein dis ance is a dis ance o p obabili y measu es. I is he building block o he p ocess dis ance, which in ol es in o ma ion in addi ion and i s egula ized e sion, which we add ess he e, he Sinkho n di e gence. The Sinkho n di e gence is no a dis ance in i sel . To poin ou he di e ences we highligh he de ining elemen s. De ini ion 2.1 (Dis ance o measu es)Le Pbe a se o p obabili y measu es on .A unc ion d:P×P→[0,∞)is called dis ance, i i sa is ies he ollowing condi ions: (i) Nonnega i i y: o all P1,P2∈P, d(P1,P2)≥0; (ii) Symme y: o all P1,P2∈P, d(P1,P2)=d(P2,P1); (iii) T iangle inequali y: o all P1,P2and P3∈P, d(P1,P2)≤d(P1,P3)+d(P3,P2); (i ) De ini eness: i d(P1,P2)=0, hen P1=P2. Rache (1991) p esen s a huge a ie y o p obabili y me ics. He e, we ocus on he Wasse s ein dis ance, which allows a gene aliza ion o s ochas ic p ocesses. Fo his we assume ha he sample space =Rdis equipped wi h a me ic d. De ini ion 2.2 (Wasse s ein dis ance)Le Pand ˜ Pbe wo p obabili y measu e on endowed wi h a dis ance d:×→Rwi h ini e momen o o de .The Wasse s ein dis ance o o de ≥1is d (P,˜ P):= in π× d(ξ, ˜ ξ) π(dξ,d˜ ξ), whe e he in imum is o e all p obabili y measu es πon ×wi h ma ginals Pand ˜ P, espec i ely. Rema k 2.3 (Dis ance e sus cos unc ions) The de ini ion o he Wasse s ein dis- ance p esen ed he e s a s wi h a dis ance don and he Wasse s ein dis ance is 123 272 A. Pichle , M. Weinha d a dis ance on Pin he sense o De ini ion 2.1 abo e. We men ion ha he li e a u e occasionally de elops he heo y o cos unc ions c:X×X→Rins ead o he dis ance d. Also, he esul s p esen ed below ex end o cos unc ions in place o he dis ance on he unde lying space. In a disc e e amewo k, p obabili y measu es a e o he o m P=n i=1piδξiwi h pi≥0 and n i=1pi=1 and he suppo o P({ξi:i=1,2,...,n}⊂) is ini e. By De ini ion 2.1, he Wasse s ein dis ance d o wo disc e e measu es P=n i=1piδξi and ˜ P=˜n j=1˜pjδ˜ ξjis he - h oo o he op imal alue o minimize in π n  i=1 ˜n  j=1 πij d ij subjec o ˜n  j=1 πij =pi,i=1,...,n, n  i=1 πij =˜pj,j=1,...˜nand πij ≥0,(2.1) whe e dij:=d(ξi,˜ ξj)(2.2) is an nטn-ma ix collec ing all dis ances. The op imal measu e in (2.1) is deno ed πW and called an op imal anspo plan. The con ex, linea dual o (2.1)is maximize in λand μ n  i=1 piλi+ ˜n  j=1 ˜pjμj(2.3a) subjec o λi+μj≤d ij o all i=1,...nand j=1,... ˜n.(2.3b) Rema k 2.4 The p oblem (2.1) can be w i en as linea op imiza ion p oblem minimize in xcx subjec o Ax =b, x≥0, whe e x=(π11,π 21,...,π n˜n),c=(d11,d21,...,dn˜n),b=(p1,...,pn,˜p1,..., ˜p˜n)and Ais he ma ix A=1˜n⊗In I˜n⊗1n 123 The nes ed Sinkho n di e gence o lea n he nes ed dis ance 273 2 2 1 1 1 2 2 +3 1 1 2 22 1 1 2 3 1 2 1 Fig. 1 Two p ocesses illus a ing wo di e en lows o in o ma ion, c . Hei sch e al. (2006), Ko ace ic and Pichle (2015). The a cs o he s ochas ic ee display he ansi ion p obabili ies wi h 1=(1,...,1); he e, ⊗deno es he K onecke p oduc . 2.2 The dis ance o s ochas ic p ocesses Be wo p obabili y spaces. We now conside wo s ochas ic p ocesses wi h ealiza ions ξ,˜ ξ∈and :=0×1×···×T. The e a e many me ics dsuch ha (, d)is a me ic space. Wi hou loss o gene ali y we may se  =R o all ∈{0,1,...,T} and employ he 1-dis ance, i.e., d(ξ, ˜ ξ) =T =0|ξ −˜ ξ |.Asin(2.1) abo e, he dis ance ma ix dij collec s he dis ances o scena ios o disc e e measu es, c . (2.2). A s ochas ic p ocess wi h ini ely many s a es (i.e., ou comes) o ∈{0,1,...,T} is a scena io ee. Scena io ees a e equen ly employed in op imiza ion unde unce - ain y o model he andom ou come in he e olu ion o a p ocess which desc ibes he andom p ice, say, o an unde lying asse . They a e con enien , because hey can be implemen ed in compu e s o assess each indi idual ajec o y as possible ealiza ion o he s ochas ic p ocess. The Figs. 1and 3depic such scena io ee, hey indica e he ansi ion p obabili ies in addi ion. Rema k 2.5 Figu e 1illus a es ha he Wasse s ein dis ance does no cap u e he di e en in o ma ion (knowledge) a ailable a he in e media e s age. Indeed, wi h >0, he ma ix collec ing he dis ances o he ajec o ies aken om bo h ees is d=2+ 20  and he op imal anspo plan o he Wasse s ein dis ance is π=1 210 01 . The Wasse s ein dis ance, acco ding (2.1), is d=i,jdij πij =/2, whe e a small alue o indica es ha he p ocesses a e simila . Howe e , he in o ma ion a ailable a s age 1 is e y dis inc in bo h ees in Fig. 1. When obse ing 2 +a s age 1 in he i s ee i is ce ain ha he nex obse a ion is 3, and i will be 1 when obse ing 2. In con as , he second p ocess does no p o ide any ce ain y whe he he esul will be 1 o 3 a e obse ing 2 a he i s s age. We conclude om he p eceding ema k ha he Wasse s ein dis ance is no sui able o dis inguish s ochas ic p ocesses wi h di e en lows o in o ma ion. The eason is 123 274 A. Pichle , M. Weinha d ha his app oach does no in ol e condi ional p obabili ies a s ages =0,1,...,T− 1, bu only p obabili ies a he inal s age =T, whe e all he in o ma ion a ailable a in e media e s ages is igno ed. We ollow he usual con en ion and exp ess in o ma ion, which is accessible, by co esponding se s. The in o ma ion a ailable a e e y s age includes in o ma ion om p eceding s ages, which ha e been e ealed, bu excludes in o ma ion om la e , u u e s ages. Fo his eason he se s A1×···× A × +1×···×T,A ⊂ measu able, encode he in o ma ion a ailable a s age , hey cons i u e he σ-algeb a F (˜ F , esp.). The ollowing gene aliza ion o he Wasse s ein dis ance akes his low o inc easing in o ma ion explici ly in o accoun . We s a e he de ini ion in ol ing gene al p obabili y measu es he e, al hough we wo k wi h disc e e measu es only in wha ollows. De ini ion 2.6 (The nes ed dis ance)Thenes ed dis ance o o de ≥1 o wo il e ed p obabili y spaces P=(, (F ), P)and ˜ P=(˜ , ( ˜ F ), ˜ P)wi h ini e momen o o de wi h espec o he dis ance d:ט →Ris he op imal alue o he op imiza ion p oblem minimize in πט  d(ξ, ˜ ξ) π(dξ,d˜ ξ)1 / (2.4) subjec o π(Aט |F ⊗˜ F )=P(A|F )a.s. o e e y A∈F , =1,...,T, (2.5) π( ×B|F ⊗˜ F )=˜ P(B|˜ F )a.s. o e e y B∈˜ F , =1,...,T, (2.6) whe e he in imum is among all bi a ia e p obabili y measu es π∈P( ט ).The op imal alue o (2.1), he nes ed dis ance o o de , is deno ed by d (P,˜ P). Fo disc e e s ochas ic p ocesses we use ees o model he whole space and il- a ion. In he s ochas ic ee, N (˜ N , esp.) deno es he se o all nodes a he s age . Fu he mo e, a p edecesso mo he node i, no necessa ily he immedia e p e- decesso , is indica ed by m≺i. He e, we may eplace he condi ional p obabili ies in (2.5) and (2.6) by he genuine ansi ion p obabili ies. The a cs o he ee in Fig. 1 exempla ily display hese ansi ion p obabili ies. 123 The nes ed Sinkho n di e gence o lea n he nes ed dis ance 275 Algo i hm 1: Nes ed compu a ion o he nes ed dis ance d (P,˜ P)o wo ee- p ocesses Pand ˜ P. Inpu : o all combina ions o lea nodes i∈NTand j∈˜ NTwi h p edecesso s (i0,i1,...,iT−1,i)and (j0,j1,..., jT−1,j)se d T(i,j):= d(ξ0,ξ i1,...,ξ i), (˜ ξ0,˜ ξj1,...,˜ ξj) Ou pu : he op imal anspo plan a he lea nodes i∈NTand j∈˜ NTis π(i,j)=π1(i1,j1|i0,j0)·····πT−1(i,j|iT−1,jT−1). o =T−1down o 0and e e y combina ion o inne nodes i∈N and j∈˜ N do sol e he linea p og ams minimize in π i∈i +,j∈j + π(i,j|i ,j )·d +1(i,j) subjec o  j∈j + π(i,j|i ,j )=P(i|i ), i∈i +,  i∈i + π(i,j|i ,j )=˜ P(j|j ), j∈j +, π(i,j|i ,j )≥0(2.9) and deno e i s op imal alue by d (i ,j ). Resul : The nes ed dis ance is d (P,˜ P):=d 0(0,0). The nes ed dis ance o s ochas ic ees is he - h oo o he op imal alue o minimize in π i,j πij ·d ij subjec o  jj π(i,j|i ,j )=P(i|i ), i ≺i,j ,  ii π(i,j|i ,j )=˜ P(j|j ), j ≺j,i , πij ≥0 and  i,j πij =1,(2.7) whe e i∈NTand j∈˜ NTa e he lea nodes and i ∈N as well as j ∈˜ N a e nodes a he same s age and P(i|i ):= P(i) P(i )is he condi ional p obabili y. Analogously, he condi ional p obabili ies π(i,j|i ,j )a e π(i,j|i ,j ):= πij ii ,jj πij .(2.8) Rema k 2.7 Employing he de ini ion (2.8) o π(i,j|i ,j ) e eals ha he p ob- lem (2.7) is indeed a linea p og am in π(c . (2.1)). 123 276 A. Pichle , M. Weinha d 2.3 Rapid, nes ed compu a ion o he p ocess dis ance This subsec ion add esses an ad anced app oach o sol ing he linea p og am (2.7). We i s ecall he owe p ope y, which allows an impo an simpli ica ion o he cons ain s in (2.4). Lemma 2.8 To compu e he nes ed dis ance i is enough o condi ion on he immedi- a ely ollowing σ-algeb a: he condi ions πA×|F ⊗˜ F  o all A ∈FT in (2.4)may be eplaced by πA×|F ⊗˜ F  o all A ∈F +1. P oo The p oo is based on he owe p ope y o he expec a ion and can be ound in P lug and Pichle (2014, Lemma 2.43).  As a esul o he owe p ope y he ull p oblem (2.7) can be calcula ed as e in a ecu si e way and he ma ix o he cons ain s does no ha e o be s o ed. We employ his esul in an algo i hm below. Fo u he de ails we e e o P lug and Pichle (2014, Chap e 2.10.3). The collec ion o all di ec successo s o node i (j , esp.) is deno ed by i +(j +, esp.). 3 Sinkho n di e gence In wha ollows we conside he en opy- egula iza ion o he Wasse s ein dis- ance (2.1) and cha ac e ize i s dual. Mo eo e , we ecall Sinkho n’s algo i hm, which allows and p o ides a conside ably as e implemen a ion. These esul s a e combined hen o accele a e he compu a ion o he nes ed dis ance. 3.1 En opy- egula ized Wasse s ein dis ance In e io poin me hods add a loga i hmic penal y o he objec i e o o ce he op imal solu ion o he modi ied p oblem in o he s ic in e io . The Sinkho n dis ance p oceeds simila ly. The egula izing e m H(x):=−i,jxij log xij is added o he cos unc ion in p oblem (2.1). This has shown bene icia y in o he p oblem se ings as well. Rema k 3.1 The mapping ϕ(y):=ylog yis con ex and nega i e o y∈(0,1)wi h con inuous ex ensions ϕ(0)=ϕ(1)=0 so ha H(x)≥0, p o ided ha all xij ∈ [0,1]. 123 The nes ed Sinkho n di e gence o lea n he nes ed dis ance 283 4.1 Nes ed Sinkho n di e gence Le de( )be he ma ix o inc emen al di e gences o sub- ees a s age . Analogously o (2.9) we conside he condi ional e sion o he p oblem (3.1a) and deno e by βi j and γj i he pai o op imal Lag ange pa ame e s associa ed wi h he p oblem minimize inπ i∈i +,j∈j + π(i,j|i ,j )·de( +1)(i,j) +1 λπ(i,j|i ,j )·log π(i,j|i ,j ) subjec o  j∈j + π(i,j|i ,j )=P(i|i ), i∈i +,  i∈i + π(i,j|i ,j )=˜ P(j|j ), j∈j +, π(i,j|i ,j )>0,(4.1) whe e π(i,j|i ,j )=exp −λde( +1) i j −βi j −γj i −1. The op imal alue is he new di e gence de( )(i ,j ). Compu ing he nes ed dis ance ecu si ely om = T−1down o0wege πij =π1(i1,j1|i0,j0)·...·πT−1(i,j|iT−1,jT−1) =e−λ(de(1) i0j0−βi0j0−γj0i0)−1·...·e−λ(de(T) iT−1jT−1−βiT−1jT−1−γjT−1iT−1)−1 =exp −T−λ T−1  =0 de( +1) i j −βi j −γj i ,(4.2) whe e i∈NTand j∈˜ NTa e he lea nodes wi h p edecesso s (i0,i1,...,iT−1,i) and (j0,j1,..., jT−1,j). As abo e in oduce ˜ βi j := exp λβ i jj−1 /2and ˜γj i := exp λγj i −1 /2. Combining he componen s i ollows ha πij =exp −T−λ T−1  =0 de( +1) i j −βi j −γj i  = T−1  =0 ˜ βi j exp −λde( +1) i j ˜γj i , whe e he p oduc is he en y-wise p oduc (Hadama d p oduc ). The ollowing heo em summa izes he ela ion o he nes ed dis ance wi h he Sinkho n di e gence. 123 284 A. Pichle , M. Weinha d Theo em 4.1 (En opic elaxa ion o he nes ed dis ance) The ecu si e solu ion (4.1) ((4.2), esp.) coincides wi h he op imal anspo plan gi en by minimize in π n  i=1 ˜n  j=1 πij ·d ij +1 λπij ·log πij subjec o  jj + π(i,j|i ,j )=P(i|i ), i ≺i,j ,  ii + π(i,j|i ,j )=˜ P(j|j ), j ≺j,i , πij >0and  i,j πij =1.(4.3) P oo Fi s de ine π:= T =1π , whe e π is he condi ional ansi ion p obabili y, i.e., he solu ion a s age and he ma ices a e mul iplied elemen -wise ( he Hadama d p oduc ) as in equa ion (4.2) abo e. I ollows ha d ·π+1 λπlog π=d · T  =1 π +1 λ· T  =1 π log T  =1 π  =d · T  =1 π +1 λ· T  =1 π · T  =1 log π .(4.4) Obse e ha π (A)=E(1A|F ⊗˜ F )(c . Lemma (2.8)). Deno e he -dis ance o sub ees a s age by de . By linea i y o he condi ional expec a ion we ha e wi h (4.4) a he las s age deT−1=Ede T+1 λlog πTFT−1⊗˜ FT−11 / and om calcula ion in backwa d ecu si e way deT−2=Ede T−1+1 λlog πT−1FT−2⊗˜ FT−21 / =EEde T+1 λlog πTFT−1⊗˜ FT−1+1 λlog πT−1FT−2⊗˜ FT−21 / =EEde T+1 λlog πT+1 λlog πT−1FT−1⊗˜ FT−1FT−2⊗˜ FT−21 / , 123 The nes ed Sinkho n di e gence o lea n he nes ed dis ance 285 whe e we ha e used he owe p ope y o he condi ional expec a ion in (4.5). By induc ion and he de ini ion o de a s age , i ollows inally ha de0=Ede 1+1 λlog π1F0⊗˜ F01 / =EE...Ede T+1 λlog πTFT−1⊗˜ FT−1...F1⊗˜ F1+1 λlog π1F0⊗˜ F01 / =EE...Ede T+1 λ T  =1 log π FT−1⊗˜ FT−1...F1⊗˜ F1F0⊗˜ F01 / (4.5) =Ede T+1 λ T  =1 log π F0⊗˜ F01 / =Ede T+1 λ T  =1 log π 1 / ,(4.6) whe e we ha e used he owe p ope y o he condi ional expec a ion again in (4.5). The asse ion (4.3) o he heo em hus ollows.  Rema k 4.2 The op imiza ion p oblem in Theo em 4.1 conside s all cons ain s as he ull nes ed p oblem (2.7), only he objec i e di e s. Fo his eason he op imal solu ion o (4.3) is easible o he p oblem (2.7) and ice e sa. No ice as well ha he owe p ope y can be used in a o wa d calcula ion. Simila ly o P oposi ion 3.5 we ha e he ollowing ex ension o he nes ed Sinkho n di e gence. Co olla y 4.3 Fo he nes ed dis ance and he nes ed Sinkho n di e gence, he same inequali ies as in P oposi ion 3.5 apply, i.e., 0≤d S−d ≤1 λH(π S)−H(πW)and 0≤d −de S≤1 λH(π S) ≤1 λH(p·p), whe e πS(πW, esp.) is he op imal anspo plan om (4.3)((2.7), esp.) wi h disc e e, uncondi ional p obabili ies p and ˜p a he inal s age T . P oo The p oo ollows he lines o he p oo o he P oposi ions 3.4 and 3.5. Mo eo e , we ha e he ollowing gene al inequali y ha allows an e o bound depending on he o al To s ages. 123 286 A. Pichle , M. Weinha d Co olla y 4.4 Le m ( ˜m, esp.) be he maximum numbe o immedia e successo s in he p ocess P(˜ P, esp.), i.e., m =max {|i+|:i∈N , =1,...,T−1}. I holds ha de S−d ≤log m+log ˜m λ·T,(4.7) whe e T is he o al numbe o s ages. P oo Recall om Rema k 3.6 ha H(π S)≤log(n˜n)=log n+log ˜n o e e y con- di ional p obabili y measu es, whe e nand ˜na e he numbe o immedia e successo s in bo h ees. The esul ollows wi h n≤mT(˜n≤˜mT, esp.) and log n≤Tlog m and he nes ed p og am (4.1).  4.2 Nes ed Sinkho n duali y The nes ed dis ance is o impo ance in s ochas ic op imiza ion because o i s dual, which is cha ac e ized by he Kan o o ich–Rubins ein heo em, c . (2.3a)–(2.3b) abo e. The nes ed dis ance allows o a cha ac e iza ion by duali y as well. He e we de elop he duali y o he nes ed Sinkho n di e gence. In line wi h Theo em 4.1 we need o conside he p oblem minimize in π d(ξ, ˜ ξ) +1 λlog π(ξ, ˜ ξ)π(dξ,d˜ ξ)1 / subjec o π(Aט |F ⊗˜ F )=P(A|F ), A∈F , =1,...,T, (4.8a) π( ×B|F ⊗˜ F )=˜ P(B|˜ F ), B∈˜ F , =1,...,T. (4.8b) Howe e , we i s e o mula e he p oblem (3.9a)–(3.9b). By ansla ing he dual a i- ables, ˆ β:= − β+Eβand ˆ γ:=−γ+˜ Eγ, and de ining M0:=−Eβ−˜ Eγwe ha e he al e na i e ep esen a ion maximize in M0M0 subjec o Eˆ β=0,˜ Eˆγ=0,  ξ,˜ ξ exp −λd(ξ, ˜ ξ) −ˆ β(ξ) −ˆγ(˜ ξ)−M0−1=1, ˆ β∈Rn,ˆγ∈R˜n. To es ablish he dual ep esen a ion o he nes ed dis ance we in oduce he p ojec ions p oj :L1(FT⊗˜ FT)→L1(F ⊗˜ FT) ˆ β⊗ˆγ→ E(ˆ β|F )⊗ˆγ 123 The nes ed Sinkho n di e gence o lea n he nes ed dis ance 287 and ˜ p oj :L1(FT⊗˜ FT)→L1(FT⊗˜ F ) ˆ β⊗ˆγ→ ˆ β⊗E(ˆγ|˜ F ), whe e β⊗γis he unc ion de ined by β⊗γ(ξ, η):=β(ξ) ·γ(η) and whe e we no e ha he condi ional expec a ion is a andom a iable i sel . We ecall he ollowing cha ac e iza ion o he measu abili y cons ain s (4.8a)– (4.8b) and e e o P lug and Pichle (2014, P oposi ion 2.48) o i s p oo . P oposi ion 4.5 The measu e πsa is ies he ma ginal condi ion π(Aט |F ⊗˜ F )=P(A|F )a.s. o all A ∈ i and only i Eπβ=Eπp oj β o all βmeasu able wi h espec o FT⊗˜ FT. Mo eo e , p oj (β) =Eπ(β |F ⊗˜ FT)i πhas ma ginal P. Theo em 4.6 The in imum o he nes ed dis ance including he en opy de (P,˜ P)o p oblem (4.3)equals he sup emum o all numbe s M0such ha e−λ(d(ξ,˜ ξ) −MT(ξ,˜ ξ))−1∈P( ט ), (ξ, ˜ ξ) ∈ט , whe e P( ט ) is a se o p obabili y measu es on ( ט ) and M is an R- alued p ocess on ט o he o m M =M0+  s=1 ˆ βs+ˆγs(4.9) and he unc ions ˆ β , measu able wi h espec o F ⊗˜ F −1, and ˆγ , measu able wi h espec o F −1⊗˜ F , sa is y p oj −1(ˆ β )=0and ˜ p oj −1(ˆγ )=0. P oo Wi h P oposi ion 4.5 ew i e he dual p oblem as in π>0sup M0, ,g Eπd +1 λlog π+M0·(1−Eπ1)+ − T−1  s=0Eπ s+1−Eπp ojs( s+1)− T−1  s=0Eπgs+1−Eπ˜ p ojs(gs+1), 123 288 A. Pichle , M. Weinha d whe e he second line encodes he measu abili y cons ain s. By he minmax heo em (c . Sion 1958) his is equi alen o sup M0, ,g M0+in π>0 Eπd +1 λlog π−M0·1 − T−1  s=0 ( s+1−p ojs( s+1)) − T−1  s=0 (gs+1−˜ p ojs(gs+1)). The in eg al exis s and he minimum is ob ained by a p obabili y measu e π=exp ⎛ ⎝−λ⎛ ⎝d − T−1  s=0 ( s+1−p ojs( s+1)) − T−1  s=0 (gs+1−˜ p ojs(gs+1)−M0⎞ ⎠−1⎞ ⎠. Se ˆ βs:= s−p ojs−1( s)and ˆ γs:=gs−˜ p ojs−1(gs). Consequen ly, he p oblem eads maximize in M0M0 subjec o exp −λd − T  s=1 ˆ βs− T  s=1 ˆγs−M0−1∈P( ט ) p oj −1(ˆ β )=0,˜ p oj −1(ˆγ )=0, and hus he asse ion.  The ollowing co olla y links he op imal p obabili y measu e and he s ochas ic p ocess (4.9) o he op imal componen s ˆ βand ˆγ. Co olla y 4.7 The p ocess M in (4.9), o which he sup emum is a ained, is a ma - ingale wi h espec o he op imal measu e π. P oo The p oo o P lug and Pichle (2014, Theo em 2.49) applies wi h mino adap- ions only.  5 Nume ical esul s The nes ed Sinkho n di e gence d Sas well as de Sdepend on he egula iza ion pa am- e e λ. We discuss his dependency, he e o , speed o con e gence and nume ical issues in compa ison o he non- egula ized nes ed dis ance d . We compa e Algo i hms 1and 2wi h espec o he nes ed dis ance d and he nes ed Sinkho n di e gence wi h and wi hou he en opy 1 λH(π S)as well as he equi ed compu a ional ime o wo ini e alued s ochas ic scena io p ocesses isualized in Fig. 3. Figu e 2displays he esul s. We see ha he egula ized nes ed dis ance d S(g een) and de S( ed) con e ge o he nes ed dis ance d o inc easing λ. In con as o d S, he 123 The nes ed Sinkho n di e gence o lea n he nes ed dis ance 289 (b) (a) Fig. 2 Resul s om compu a ion o an a bi a y chosen p ocesses gi en in Fig. 3wi h d(ξi,˜ ξj)=|ξi−˜ ξj| and =1 Fig. 3 Two a bi a y chosen p ocesses wi h heigh T=3 123 290 A. Pichle , M. Weinha d Table 1 A e age dis ance and di e gence wi h co esponding compu a ional ime in seconds on i5-3210M CPU S ages Wasse s ein Sinkho n Di e ence Time Td Time d Sde STime d −de SAccele a ion 1 1.8 0.06s 1.81 1.75 0.006s 0.06 10× 2 5.1 0.13s 5.12 4.97 0.022s 0.14 5.8× 3 5.8 0.50s 5.81 5.66 0.062s 0.15 8.1× 4 7.3 1.54s 7.32 7.08 0.368s 0.24 4.2× 5 10.1 10.29s 10.05 9.72 2.873s 0.35 3.6× All s a es and p obabili ies a e gene a ed andomly. The egula iza ion pa ame e is λ=20 and =1 egula ized nes ed dis ance including he en opy con e ges slowe o d . The eason is ha o la ge λ he weigh o he en opy in he cos unc ion in (3.1a) dec eases and he en opy o πSand πWcoincide (c . (4.7)). Compu ing he dis ances wi h Sinkho n’s algo i hm in ecu si e way, in con as o sol ing he linea p oblem o he Wasse s ein dis ance, is abou six imes as e . In addi ion, he equi ed ime o he egula ized nes ed dis ance wi h and wi hou he en opy a ies much less by con as wi h he compu a ional ime o he nes ed dis ance. Fu he mo e, he di e ences be ween d and d Sand de S, espec i ely, is apidly dec easing and insigni ican o λ>20. Mo eo e , he ime displayed in Fig. 2b does no depend on he egula iza ion pa ame e λ. The ollowing wo examples illus a e he compu a ional accele a ions. Example 5.1 We now ix λ=20 and a y he s ages T∈{1,2,3,4,5}. The i s ini e ee has he b anching s uc u e [123234]and he second ee has a simple s uc u e [122132](i.e., he i s ee has 144 lea nodes and he second ee 24). All s a es and p obabili ies in he ees a e gene a ed andomly. Table 1summa izes he esul s collec ed. We no ice ha he Sinkho n algo i hm is up o 10 imes as e compa ed wi h he usual Wasse s ein dis ance, al hough he speed ad an age dec eases o la ge ees. The Sinkho n algo i hm also leads o small e o s which inc ease ma ginally o ees wi h mo e s ages. Example 5.2 To p o ide an addi ional pe o mance compa ison we ix λ=20 and a y T∈{1,2,3,4,5,6}. The i s ini e ee has he s uc u e [1453446]and he second ee [1221323]. This means ha he i s ee has 5760 lea nodes while he second ee has only 72. All s a es and p obabili ies in he ees a e gene a ed andomly. Table 2summa izes he esul s a e summa ized Addi ionally, we ied o imp o e he speed by modi ying he ecu si e algo i hm. Ins ead o compu ing once om T−1 down o 0 we compu ed om T−1down o0 se e al imes o achie e a con e gence in he op imal anspo plan πS. This app oach has no ad an ages. Rema k 5.3 The en ies kij o he ma ix (3.12) a e small o dij = 0, pa icula ly o λ1 (i.e., λla ge) and 1. In his case, he en ies o he ec o s ˜ βand ˜γ 123 The nes ed Sinkho n di e gence o lea n he nes ed dis ance 291 Table 2 A e age dis ance and di e gence (c . Table 1) S ages Wasse s ein Sinkho n Di e ence Time Td Time d Sde STime d −de SAccele a ion 1 2.3 0.05s 2.3 2.2 0.008s 0.09 5.8x 2 5.6 0.2s 5.6 5.4 0.060s 0.19 3.2x 3 6.3 1.4s 6.3 6.1 0.233s 0.22 5.8x 4 7.7 6.2s 7.7 7.4 0.202s 0.33 3.1x 5 11.4 58s 11.3 10.8 17.16s 0.58 3.4x 6 13.4 717s 10.2 9.7 347.5s 3.75 2.0x Table 3 The nes ed dis ance and di e gence o wo ees wi h 3 s ages and lea es and b anching 2. The egula iza ion pa ame e is λ=10 S ages Wasse s ein Sinkho n O de d d Sde 1 0.8615 0.8737 0.6194 2 1.0532 1.0554 0.9348 3 1.2021 1.2026 1.1454 4 1.3188 1.3189 1.2925 5 1.4134 1.4134 1.4014 in Algo i hm 2can g ow ex ao dina y high. Fo his eason, escaling he ec o s is necessa y. Fu he , an adequa e balance be ween λ, modelling he app oxima ion quali y, and accele a ion desi ed is c ucial in eal applica ions. See also Rema k 3.11 o he same issue. Example 5.4 Table 3in es iga es he app oxima ion quali y o a ying o de s .The ees compa ed ha e 3 s ages and each node b anches in o wo di ec ions. Fo la ge 1 i is impo an o ecall Rema k 5.3 he e, bu on he o he side he app oxima ion quali y imp o es o inc easing o de . 6 Summa y S ochas ic p ocesses wi h in o ma ion e ol ing in ini ely many s ages and ini ely many s a es a e encoded in s ochas ic ees. The nes ed dis ance, which builds on he Wasse s ein dis ance, allows dis inguishing s ochas ic p ocesses and s ochas ic ees. In his pape we egula ize he Wasse s ein dis ance by employing he Sinkho n di e gence. This app oach ex ends o mul iple s ages and allows in oducing a nes ed Sinkho n di e gence o s ochas ic p ocesses. We elabo a e i s p ope ies and desc ibe he accele a ions, which can be achie ed in his way. In conclusion, we can summa ize ha he Sinkho n di e gence o e s a good ade- o be ween he egula iza ion e o and he speed ad an age. Fu he wo k should ocus on de ining a (nes ed) dis ance o neu onal ne wo ks and ex ending he imple- 123 292 A. Pichle , M. Weinha d men a ion o Sinkho n di e gence in he Julia package o as e ee gene a ion and compu a ion. Acknowledgemen s We a e hank ul o Benoî T an o poin ing ou u he e e ences, pa icula ly on con e gence, in his hesis T an (2020) supe ised by Ma ianne Akian and Jean-Philippe Chancelie . Funding Open Access unding enabled and o ganized by P ojek DEAL. Open Access This a icle is licensed unde a C ea i e Commons A ibu ion 4.0 In e na ional License, which pe mi s use, sha ing, adap a ion, dis ibu ion and ep oduc ion in any medium o o ma , as long as you gi e app op ia e c edi o he o iginal au ho (s) and he sou ce, p o ide a link o he C ea i e Commons licence, and indica e i changes we e made. The images o o he hi d pa y ma e ial in his a icle a e included in he a icle’s C ea i e Commons licence, unless indica ed o he wise in a c edi line o he ma e ial. I ma e ial is no included in he a icle’s C ea i e Commons licence and you in ended use is no pe mi ed by s a u o y egula ion o exceeds he pe mi ed use, you will need o ob ain pe mission di ec ly om he copy igh holde . To iew a copy o his licence, isi h p://c ea i ecommons.o g/licenses/by/4.0/. Re e ences Al schule J, Weed J, Rigolle P (2017) Nea -linea ime app oxima ion algo i hms o op imal anspo ia Sinkho n i e a ion. In: P oceedings o he 31s in e na ional con e ence on neu al in o ma ion p ocessing sys ems, pp 1961–1971. Cu an Associa es Inc., a xi :1705.09634 Analui B, P lug GCh (2014) On dis ibu ionally obus mul ipe iod s ochas ic op imiza ion. Compu Manag Sci 11(3):197–220. h ps://doi.o g/10.1007/s10287-014-0213-y Bachem A, Ko e B (1979) On he RAS-algo i hm. Compu ing 23(2):189–198. h ps://doi.o g/10.1007/ b 02252097 Bel án F, de Oli ei a W, Fina di EC (2017) Applica ion o scena io ee educ ion ia quad a ic p ocess o medium- e m hyd o he mal scheduling p oblem. IEEE T ans Powe Sys 32(6):4351–4361. h ps:// doi.o g/10.1109/ pw s.2017.2658444 Be sekas DP, Cas anon DA (1989) The auc ion algo i hm o he anspo a ion p oblem. Ann Ope Res 20(1):67–96. h ps://doi.o g/10.1007/b 02216923 Bigo J, Cazelles E, Papadakis N (2019) Cen al limi heo ems o en opy- egula ized op imal anspo on ini e spaces and s a is ical applica ions. Elec on J S a 13(2):5120–5150. h ps://doi.o g/10.1214/ 19-EJS1637 B od AI (1983) Min-mad li e: a mul i-pe iod op imiza ion model o li e insu ance company in es men decisions. Insu ance Ma h Econ 2(2):91–102 Ca pen ie P, Chancelie J-P, Cohen G, De La a M, Gi a deau P (2012) Dynamic consis ency o s ochas ic op imal con ol p oblems. Ann Ope Res 200(1):247–263. h ps://doi.o g/10.1007/s10479-011-1027- 8 Ca pen ie P, Chancelie J-P, Cohen G, De La a M (2015) S ochas ic mul i-s age op imiza ion. Sp inge In e na ional Publishing, Be lin. h ps://doi.o g/10.1007/978-3-319-18138-7 Cu u i M (2013) Sinkho n dis ances: Ligh speed compu a ion o op imal anspo . In: Ad ances in neu al in o ma ion p ocessing sys ems Edi isinghe NCP (2005) Mul ipe iod po olio op imiza ion wi h e minal liabili y: bounds o he con ex case. Compu Op im Appl 32(1–2):29–59. h ps://doi.o g/10.1007/s10589-005-2053-8 Gene ay A, Pey é G, Cu u i M (2018) Lea ning gene a i e models wi h Sinkho n di e gences. In: S o key A, Pe ez-C uz F (eds) P oceedings o he wen y- i s in e na ional con e ence on a i icial in elligence and s a is ics, olume 84 o p oceedings o machine lea ning esea ch, pp 1608–1617. PMLR h p:// p oceedings.ml .p ess/ 84/gene ay18a.h ml Hei sch H, Römisch W, S uga ek C (2006) S abili y o mul is age s ochas ic p og ams. SIAM J Op im 17(2):511–525 Ho ejšo á M, Vi ali S, Kopa M, Mo iggia V (2020) E alua ion o scena io educ ion algo i hms wi h nes ed dis ance. CMS 17(2):241–275. h ps://doi.o g/10.1007/s10287-020-00375-4 123