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