CS229r:DualitybetweenBrascamp-LiebInequality&
SubadditivityofEntropy
JuspreetSinghSandhuandPrayaagVenkat
1Introduction
TheBrascamp-Lieb(BL)inequalityisageneralinequalitywhichcapturesmanywell-knowninequalitiesas
specialcases.
Theorem1
(Brascamp-LiebInequality,generalform[
BCCT08
])
.
Let
{
B
i
}
m
i
=1
beacollectionofsurjective
linearmaps
B
i
:
R
n
→
R
n
i
and
{
c
i
}
m
i
=1
beacollectionofpositivescalarssuchthat:
m
X
i
=1
c
i
n
i
=
n.
(1)
Thenforanycollection
{
f
i
}
m
i
=1
ofnon-negativefunctions
f
i
:
R
n
i
→
R
≥
0
suchthat
R
x
∈
R
n
i
|
f
i
(
x
)
|
dx<
∞
,
thefollowinginequalityholds
Z
x
∈
R
n
m
Y
i
=1
f
i
(
B
i
x
)
c
i
dx
≤
D
m
Y
i
=1
!
Z
x
∈
R
n
i
f
i
(
x
)
dx
"
c
i
,
(2)
where
D
isaconstantthatdependsonlyon
{
B
i
}
m
i
=1
and
{
c
i
}
m
i
=1
.
InTheorem
1
,
{
B
i
}
m
i
=1
aretobetho* D E M O *jectionsof
R
n
ontolowerdimensional* D E M O *hly,
thisinequalityallowsonetoupperboundtheintegralofaproductoffunctionsonlower-dimensionalspaces
bytheproductofintegrals.Condition
1
isaconditionwhichensuresthatthe“dimensions”oneitherside
oftheinequality“match”.InInequality
2
,theconstant
D
hasbeenexplictlycharacter* D E M O *lution
ofacertainoptimizationprobleminvolving
{
B
i
}
m
i
=1
and
{
c
i
}
m
i
=1
.Inthefollowing,wewillgiveseveral
examplestoprovideintuitionan* D E M O *thekeyaspectsofTheorem
1
.
Hölder’sInequality
Pick
m
=2
,
c
1
=
1
p
1
,c
2
=
1
p
2
for
p
1
,p
2
≥
1
andlet
u,v
:
R
n
→
R
≥
0
befunctions
suchthat
R
x
∈
R
n
u
(
x
)
p
1
dx,
R
x
∈
R
n
v
(
x
)
p
2
dx<
∞
.Set
f
1
=
u
p
1
and
f
2
=
v
p
2
a* D E M O *heprojections
B
1
,B
2
tobetheidentitymap.Then,Condition
1
iseasilyseentobesatisfiedwhen
1
p
1
+
1
p
2
=1
andInequality
2
simplifiestoHölder’sinequality:
|h
f,g
i|≤k
f
k
p
1
k
g
k
p
2
.
ThisexampleillustratestheflexibilityofCondition
1
;itallowsustochoose
c
i
insuchawaysoastocontrol
theleft-handsideofInequality
2
bydifferentnormsofthefunctions.Awell-knownspecial-caseofHolder’s
inequalityisthe
Cauchy-SchwarzInequality
,whichcanberetreivedbysetting
p
1
=
p
2
=2
.
1
Loomis-WhitneyInequality
Pick
m
=
n
,
c
1
=
...c
n
=
1
n
−
1
,and
B
i
:
R
n
→
R
n
−
1
bethepro-
jectionontothe
i
thcoordinatehyperplane(meaning
B
i
(
x
1
,...,x
n
)=(
x
1
,...,x
i
−
1
,x
i
+1
,...,x
n
)
),for
i
=1
,...,n
.Again,Condition
1
isstraightforwardtocheck.For
i
=1
,...,n
,takeany
f
i
:
R
n
−
1
→
R
≥
0
suchthat
R
x
∈
R
n
−
1
f
i
(
x
)
n
−
1
dx<
∞
.Then,Inequality
2
appliedtothefunctions
f
n
−
1
i
simplifiestothe
Loomis-Whitneyinequality:
Z
x
∈
R
n
m
Y
i
=1
f
i
(
B
i
(
x
))
dx
≤
m
Y
i
=1
k
f
i
k
n
−
1
.
Weremarkthatthisi* D E M O *usversionof)aspecialcaseofShearer’sLemma,see
7
.Shearer’sLemma
itselfcanberecoveredthroughdifferentchoicesof
{
B
i
}
and
{
c
i
}
.Thisexampleillustratestwoimportant
featuresofTheorem
1
.First,weprovestatementsaboutacollection
{
f
1
,...,f
n
}
ofmanyf* D E M O *stead
ofjust
m
=2
,asinHölder).Second,wecanchoosetheprojections
{
B
i
}
m
i
=1
toreplaceanintegralover
R
n
withintegralsover
R
n
i
,thelat* D E M O *aybeeasiertoevaluateinapplications.Moreover,the
{
B
i
}
and
{
c
i
}
donothavetoallbethesame.
TogetabetterunderstandingofwhattheLoomis-Whitneyinequalityissaying,let
S
⊂
R
n
beameasurable
setandtake
f
i
=
I
1
/
(
n
−
1)
B
i
(
S
)
tobetheindicatorfunction(raisedtothe
1
/
(
n
−
1)
power)fortheprojectionof
S
ontothe
i
thcoordinateplane.Notethatif
x
∈
S
then
Q
n
i
=1
f
i
(
B
i
(
x
))=1
.Thatis,ifapointisintheset
thenallofits
(
n
−
1)
-dimensi* D E M O *ionsareinthe
(
n
−
1)
-dimensionalprojectionsoftheset.This
means,thattheleft-handsideoftheLoomis-Whitneyinequalityisanupperboundon
vol
(
S
)
,where
vol
(
·
)
denotesthevolumeofasetin
R
n
.Alongthesamevein,consideringeachofthetermsontheright-hand
side,wehavethat
k
f
i
k
n
−
1
=
#
Z
x
∈
R
n
−
1
I
B
i
(
S
)
$
1
/
(
n
−
1)
=(
vol
(
B
i
(
S
)))
1
/
(
n
−
1)
.
Substituting,theLoomis-Whitneyinequalitythenstatesthat:
vol
(
S
)
≤
n
Y
i
=1
vol
(
B
i
(
S
))
1
/
(
d
−
1)
.
Inotherwords,weobtainanupperboundonthevolumeofasetintermsofthevolumesofitslower-
dimensionalprojections.Forexample,when
n
=2
,thissaysthattheareaofasetisatmostitslength
(alongtheverticaly-axis)timesitswidth(alongthehorizontalx-axis).Theaboveinequalitygeneralizes
thistohigherdimensions.
ThisexampleillustrateshowTheorem
1
isoftenapplied;thefunctions
f
i
◦
B
i
aretakentobeindicator
functionsoflowerdimensionalprojectionsaset,sothattheleft-handsideofInequality
2
representsthe
v* D E M O *etandtheright-handsideinvolvesvolumesofthelower-dimensionalprojections.Seethe
lecturenotesofBall[
B
+
97
]forfurtherapplicationsofthistechniqueinconvexgeometry.
Application:Countingtrianglesinlargerandomgraphs
WenowpresentanotherspecialcaseoftheBL
inequalitythatwasrecentlyusedbyLubetzyandZhao[
LZ15
]toanalyzethenumberoftrianglesappearing
inlargerandomgraphs.Specifically,oneofthetechnicallemmastheyprovedstatesthatif
f
:[0
,
1]
2
→
[0
,
1]
isamea* D E M O *tionsuchthat
f
(
x,y
)=
f
(
y,x
)
,then:
%
%
%
%
%
Z
(
x,y,z
)
∈
[0
,
1]
3
f
(
x,y
)
f
(
y,z
)
f
(
z,x
)
dxdydz
%
%
%
%
%
≤
"
Z
(
x,y
)
∈
[0
,
1]
2
f
(
x,y
)
2
dxdy
!
3
/
2
.
(3)
2
Roughlyspeaking,thetripleofpairs
(
x,y
)
,
(
y,z
)
,
(
z,x
)
correspondstoatriangleinagraphandthequantity
ontheleft-handsideof
3
representsthedensityoftrianglesinacertainrandomgraphassociatedwiththe
function
f
.Thisinequalityallowsonetoestimatethenumberoftrianglesinthisgraphbasedonthenumber
ofedges,whichisasimplerquantitytounderstandinthesettingof[
LZ15
].
Tosolvetheproblemofcountinglargersubgraphsthantriangles,theyderiveageneralizedversionofin-
equality
3
.However,itisstraightforwardtoseethatinequality
3
isjustaspecialcaseoftheLoomis-Whitney
inequalityandthegeneralizedversionisjustanextensionofHölder’sInequality,whichisagainaspecial
caseofTheorem
1
.
1.1PastworkontheBrascamp-Liebinequalities
Inthissection,weprovideabriefsummaryofthehistoryoftheBLinequality.Originallyproveninvarious
s* D E M O *byLieb[
Lie02
],Brascamp,LiebandLuttinger[
BLL74
]andBrascampandLieb[
BL76
],the
generalformoftheBL-inequalitygiveninTheorem
1
isduet* D E M O *l.[
BCCT08
].Inequalitiesofthis
typehaveapplicationinmathematicalphysics[
CLL05
],convexgeometry[
B
+
97
]andbeyond.
WebrieflymentionaninterestingconnectionbetweentheBLinequalityandtheoreticalcomputerscience.
Asdiscussedpreviously,theconstant
D
inInequality
2
wascharacterizedin[
BCCT08
]asthesolutionofan
optimizationproblem.Recently,Gargetal.[
GGOW18
]studiedthealgorithmictaskofcomputing
D
,given
theprojections
{
B
i
}
m
i
=1
andconstants
{
c
i
}
m
i
=1
.AlthoughallspecialcasesofTheorem
1
consideredinthis
reportsatisfytheinequalitywith
D
=1
,untiltheworkofGargetal.,itwasnotknownhowtocompute
D
ingeneralinpolynomialtime.
2Subadditivityofentropy
Webeginbyintroducingthebasicsubadditivityofentropyinequalityandthenstatingaslightgeneralization
ofit(Han’sInequality(
5
)),yieldingaconnectiontoShearer’sLemma(
7
).Weendwithageneralstatement
aboutthesubadditivityofentropy(
8
).
Theorem2
(
BasicSubadditivityofEntropy
)
.
Forrandomvariables
X
1
,..,X
n
,weh* D E M O *wing:
H
(
X
1
,..,X
n
)
≤
n
X
i
=1
H
(
X
i
)
(4)
Thisstatementisasimpleresultthatcanbederivedfromthechainruleofentropyandthefactthatcondi-
t* D E M O *lydescreaseentropy.Equalityin
4
holdsiff
X
i
⊥
X
j
,
∀
i,j
∈
[
n
]
.Thisstatementhintsata
connectionbetweena
global
quantity(
JointEntropy
)anda
local
quantity(
projectedentropies
).
Weno* D E M O *Inequality(
5
),whichisaslightgeneralizationofthestatementaboveandisthekey
ingredientinthespecialcaseofaversionofShearer’sLemma(
7
).
Han
´
sInequality
Han’sinequalityallowsustocontrolthejointentropyofasystemviathemarginal
entropies:
H
(
X
1
,..,X
n
)
≤
1
n
−
1
n
X
i
=1
H
(
X
1
,..,X
i
−
1
,X
i
+1
,..,X
n
)
(5)
•
Han’sinequalitycanbeprovedbyrewritingthejointentropyasaconditionalsumofentropies(for
some
i
∈
[
n
]
),droppingconditioningonallcoordinates
>i
,repeatingthis
∀
i
,andthensummingup
thetermsandapplyingthechain-ruleforentropy.
3
•
Inthespiritofgeneralizingfurther,Han’sinequalitycanbeappliedtorelativeentropiesaswell.Given
afinitealphabet
X
,aproductdistribution
P
=
n
Y
i
=1
p
i
on
X
n
,andajointdistribution
Q
on
X
n
,itholds
that:
D
KL
(
Q
k
P
)
≥
1
n
−
1
n
X
i
=1
D
KL
(
Q
(
i
)
k
P
(
i
)
)
(6)
where
P
(
i
)
,Q
(
i
)
denotethemarginaldistributionsfor
P,Q
respectively.
Shearer’sLemma&Han’sInequality
S* D E M O *ma
isastatementthatallowsustoboundthevol-
umeofadiscretehigh-dimensionalobjectbylookingatitslow-dimensionalprojections.
Theorem3
(
Shearer’sLemma
)
.
Givensome
n
,
k
,
N
∈
Z
+
where
k
≤
n
,anobject
F
=(
f
1
,..,f
n
)
⊆
[
N
]
n
,andthe
k
-dimensionalprojections
F
S
=
{
(
f
i
1
,..,f
i
k
)
|
i
j
∈
S
,
S
⊂
[
n
]
}
,thefollowinginequality
holds:
|
F
|
(
n
−
1
k
−
1
)
≤
Y
S
⊂
[
n
]
,
|
S
|
=
k
|
F
S
|
(7)
IfwereformulateShearer’sLemmabyreplacingthevolumeterms
|·|
in
7
bytheirentropiccounterparts,then
werecoverHan’sInequality
5
when
k
=
n
−
1
,andBasicSubadditivityofEntropy
4
when
k
=1
.Thishints
ataconnectionbetweensubadditivityofentropyandproblemsingeometrythatinvolveestimatinghigh-
dimensionalvolumesbylookingatlow-dimensionalprojections.Sincethestatementofthe
Brascamp-Lieb
inequality
(
2
)canbeinuitivelyinterpretedastryingtoboundthevolumeofahigh-dimensionalcontin-
uousobjectviaitslow-dimensionalprojections,itisnaturaltoquestionwhethersubadditivityofentropy
(initsgeneralform)isrelatedto
2
.Ageneralformofsubadditivityofentropy,whichsubsumes
4
,
5
and
6
is:
Theorem4
(
SubadditivityofEntropy
,[
BLM13
])
.
Givenindependentrandomvariables
X
1
,..,X
n
taking
valuesinacountableset
X
withtheproductdistribution:
P
=
n
Y
i
=1
p
i
and
Z
=
f
:
X
n
→
[0
,
∞
)
apositive,boundedrandomvariable,thefollowinginequalityholds:
Ent
[
Z
]
≤
E
P
[
n
X
i
=1
Ent
(
i
)
[
Z
]]
1
(8)
Thisequationhasasimilarskeletalstructureto
4
,andbasicallyassertsthatthejointentropyofthesystem
is* D E M O *abovebytheaverageofthesumofthemarginalentropies.Thegeneralized
Ent
[
Z
]
term
allowsustocontrolhighermoments,formingthebasisofthe
EntropyMethod
forprovingconcentration
inequalities.
2
1
Ent
[
Z
]
isageneralizationofentropyand
Ent
(
i
)
[
Z
]
isamarginalofthegeneraliz* D E M O *ne
Ent
[
Z
]=
E
[
Z
log(
Z
)]
−
E
[
Z
]log(
E
[
Z
])
,andthecorrespondingmarginal:
Ent
(
i
)
[
Z
]
=
E
(
i
)
[
Z
log(
Z
)]
−
E
(
i
)
[
Z
]log(
E
(
i
)
[
Z
])
.Referto[
BLM13
]fora
completetreatment.
2
Toseehow
8
cantigthenaconcentratio* D E M O *,refertoChapter-4of[
BLM13
].Fortheex* D E M O *badditivitytomore
generalentropies,refertoChapter-14in[
BLM13
].
4
3DualityofsubadditivityofentropyandBrascamp-LiebInequality
WhilethereareseveralproofsofTheorem
1
,thefirstofwhichwasduetoBennettetal.[
BCCT08
],wenow
* D E M O *ternativeapproachduetoCarlenandCordero-Erausquin[
CCE09
].Amongotherthings,they
showthatInequality
2
isdual(inaprecisesensetobeexplainedbelow)toacontinuousversionof
8
(see
9
).
ThisexactlyquantifiesandgeneralizestheconnectionwebrieflysawinSection
2
.
3.1Statementofthemainresult
WenowgiveoneofthemainresultsofCarlenandCordero-Erausquin,whichestablishesadualitybetween
theBLinequalityandsubadditivityofentropy.Foraprobabilitydensityfunction
f
:
R
n
→
R
≥
0
with
R
x
∈
R
n
f
(
x
)
dx
=1
,wecandefinetheentropyas
S
(
f
)=
Z
x
∈
R
n
f
(
x
)log
f
(
x
)
dx.
Infact,thisisactuallythe
negative
entropy,butitwillbesimplertoworkwiththisversion.So,aswewillsee,
"subadditivity"ofthisdefinitionofentropyreallymeanssuperadditivity.Foraprojection
B
i
:
R
n
→
R
n
i
,
weuse
f
B
i
todenotethemarginalprobabilitydensityfunctionof
f
under* D E M O *on
B
i
3
.Withthese
definitions,wecanstatethemainresult.
Theorem5
(Theorem2.1of[
CCE09
])
.
Let
{
B
i
}
m
i
=1
and
{
c
i
}
m
i
=1
beasinTheorem
1
.Thenthefollowing
statementsareequivalent:
1.(BLinequality)Foranycollection
{
f
i
}
m
i
=1
ofnon-negativefunctions
f
i
:
R
n
i
→
R
≥
0
suchthat
R
x
∈
R
n
i
|
f
i
(
x
)
|
dx<
∞
,Inequality
2
holds.
2.(Subadditivityofentropy)Foranyprobabilitydensityfunction
f
:
R
n
→
R
≥
0
with
R
x
∈
R
n
f
(
x
)
dx
=1
and
S
(
f
)
<
∞
,thefollowinginequalityholds:
m
X
i
=1
c
i
S
(
f
B
i
)
≤
S
(
f
)+log
D.
(9)
HavingstatedTheorem
5
,wecanseethatbothInequalities
2
and
9
arestatementsthatrelateintegralsofa
functiontointegralsofitsmarginals.Moreover,notethatTheorem
5
preservestheconstant
D
whenmoving
between
2
and
9
.CarlenandCordero-Erausquin[
CCE09
]exploitthisfacttocharacterizethefunctions
whichmaketheBLinequalitytight.
3.2Dualrelationship
WecanconnectentropyandtheBLinequalitythroughthefollowingformulafrom[
CCE09
].
Theorem6.
Let
f
beaprobabilitydensityfunctionon
R
n
and
φ
:
R
n
→
R
beanyfunctionsuchthat
R
x
∈
R
n
e
φ
(
x
)
dx<
∞
.Then,thefollowingholds:
log
!
Z
x
∈
R
n
e
φ
(
x
)
dx
"
≥h
f,φ
i−
S
(
f
)
.
(10)
Thequantityo* D E M O *ndsideofInequality
10
isknowninothercontextsasthelogarithmofthemoment
generatingfunction(orthecumulantgeneratingfunction)of
φ
.Inequality
10
simplysaysthatthedual
4
of
entropy
S
(
f
)
isthelogarithmofthemomentgeneratingfunction.
3
Thismeansthatiftherandomvariable
X
isdistributedaccordingto
f
,then
B
i
X
isdistributedaccordingto
f
B
i
.
4
Formally,thisiscalled
Fenchel-Legendreduality
,awell-studiednotiononitsownright.See[
Roc15
]forareference.
5
Proof.
Ourstartingpointistherelativeentropybetween
φ
and
f
,whichcanbesimplifiedtogettheright-
handsideoftheinequalitywewanttoprove:
Z
x
∈
R
n
f
(
x
)log
"
e
φ
(
x
)
f
(
x
)
!
dx
=
h
f,φ
i−
S
(
f
)
,
wherewehaveusedtheinnerproduct
h
f,φ
i
=
R
x
∈
R
n
f
(
x
)
g
(
x
)
dx
.Bytheconcavityofthelogarithmand
Jensen’sinequality,wecanupperboundtherelativeentropyas:
Z
x
∈
R
n
f
(
x
)log
"
e
φ
(
x
)
f
(
x
)
!
dx
≤
log
"
Z
x
∈
R
n
f
(
x
)
e
φ
(
x
)
f
(
x
)
dx
!
=log
#
Z
x
∈
R
n
e
φ
(
x
)
dx
$
.
Combiningthepreviousinequalitywiththeoriginalequalitygivestheresult.
3.3ProofofTheorem
5
TheproofstrategyforTheorem
5
issimple.WewillassociatetheBLinequalitywiththeleft-handsideof
Formula
10
andInequality
9
withtheright-handside,allowingustopassbackandforthbetweentwo.
Proof.
Forthefirstdirection,assumethatInequality
2
holdsandlet
f
beanyprobabilitydensityfunction
on
R
n
with
S
(
f
)
<
∞
.Instantiatingthedualityformula
10
with
φ
=
P
m
i
=1
c
i
log
f
B
i
◦
B
i
andrearranging,
wehavethat:
S
(
f
)
≥
m
X
i
=1
c
i
#
Z
x
∈
R
n
i
f
B
i
(
x
)log
f
B
i
(
x
)
dx
$
−
log
"
Z
x
∈
R
n
m
Y
i
=1
f
B
i
(
B
i
x
)
c
i
!
.
Ontheright-handsideoftheaboveinequality,weapplytheBLinequalitytocontroltheintegralofproducts
sothatweget
Z
x
∈
R
n
m
Y
i
=1
f
B
i
(
B
i
x
)
c
i
≤
D
m
Y
i
=1
#
Z
x
∈
R
n
i
f
B
i
(
x
)
dx
$
c
i
=
D,
whereweusedthefactthateach
f
B
i
isadensityfunctionwhichintegratesto1.Substitutingthisintothe
aboveinequality,wehave:
S
(
f
)
≥
m
X
i
=1
c
i
#
Z
x
∈
R
n
i
f
B
i
(
x
)log
f
B
i
(
x
)
dx
$
−
log
D
=
m
X
i
=1
c
i
S
(
f
B
i
)
−
log
D,
completingthefirstdirectionoftheproof.Thereversedirectionissimilar,soweomitthedetails.
Theproofillustratesthatthelogarithmofthemomentgeneratingfunctionmakesiteasiertoworkwith
marginals,sincetheexponentialofasumfactorsintoaproductofexponentials.
4Conclusion
Inthisreport,wesawthattheBLinequalityisageneraltoolforboundingintegralsofproductsoffunctions
byproductsofintegrals,whichariseinvariousapplications.
ThemaintakeawayofTheorem
5
isthatwecannowproveBL-typeinequalitiesbymakinguseoftools
frominformationtheorytoprovethecorrespondingsubadditivityofentropyinequalities.Insomecases,
thelattertaskissignificantlyeasier(asdemonstratedbyCarlenandCordero-Erausquin[
CCE09
]).As
asimpleexampleofthis,instantiateTheorem
5
with
{
B
i
}
n
i
=1
astheprojectionsontothe
n
coordinate
hyperplanes.ThenInequality
9
becomesHan’sInequality
5
andInequality
2
becomestheLoomis-Whitney
Inequality.
6
Acknowledgements
TheauthorswouldliketothankProfessorMadhuSudanforhisfeedbackonthisreportandcorresponding
presentation.
References
[B
+
97]KeithBalletal.Anelementaryintroductiontomodernconvexgeometry.
Flavorsofgeometry
,
31:1–58,1997.
[BCCT08]JonathanBennett,AnthonyCarbery,MichaelChrist,andTerenceTao.Thebrascamp–
liebinequalities:finiteness,structureandextremals.
GeometricandFunctionalAnalysis
,
17(5):1343–1415,2008.
[BL76]HermJanBrascampandElliottHLieb.Bestconstantsinyoung’sinequality,itsconverse,
anditsgeneralizationtomorethanthreefunctions.
AdvancesinMathematics
,20(2):151–173,
1976.
[BLL74]HermJBrascamp,ElliottHLieb,andJML* D E M O *eneralrearrangementinequalityfor
multipleintegrals.
Journalo* D E M O *analysis
,17(2):227–237,1974.
[BLM13]StéphaneBoucheron,GáborLugosi,andPascalMassart.
Concentrationinequalities:A
nonasymptotictheoryofindependence
.Oxforduniversitypress,2013.
[CCE09]EricACarlenandDarioCordero-Erausquin.Subadditiv* D E M O *ropyanditsrelationto
brascamp–liebtypeinequalities.
GeometricandFunctionalAnalysis
,19(2):373–405,2009.
[CLL05]EricCarlen,ElliottHLieb,andMichaelLoss.Aninequalityofhadamardtypeforpermanents.
arXivpreprintmath/0508096
,2005.
[GGOW18]AnkitGarg,LeonidGurvits,RafaelOliveira,andAviWigderson.Algorithmicandoptimiza-
tionaspectsofbrascamp-liebinequalities,viaoperatorscaling.
GeometricandFunctional
Analysis
,28* D E M O *,2018.
[Lie02]ElliottHLieb.Gaussiankernelshaveonlygau* D E M O *zers.In
Inequalities
,pages595–
624.Springer,2002.
[LZ15]EyalLubetzkyandYufeiZhao.Onreplicasymmetryoflargedeviationsinrandomgraphs.
RandomStructures&Algorithms
,47(1):109–146,2015.
[Roc15]RalphTyrellRockafellar.
Convexanalysis
.Princetonuniversitypress,2015.
7