Disc e e In o ma ion Geome y
o Compu a ional Uni e se:
Rela i e En opy, Fishe S uc u e
and Task-Sensi i e Dis ance
Haobo Ma1Wenlin Zhang2
1Independen Resea che
2Na ional Uni e si y o Singapo e
No embe 24, 2025
Abs ac
Unde axioma ized amewo k o “compu a ional uni e se” Ucomp = (X, T,C,I),
complexi y geome y cha ac e izes “how much ime/cos needed o each ce ain
con igu a ion”. Howe e , complexi y geome y alone insu icien o desc ibe “how
high quali y in o ma ion hese cos s exchange o ”. Fo his, his pape cons uc s
se o “disc e e in o ma ion geome y” heo y ma ching compu a ional uni e se in
comple ely disc e e se ing.
We i s in oduce obse a ion ope a o amily O={Oj}j∈J, whe e each Oj
maps con igu a ion x∈X o p obabili y dis ibu ion p(j)
xon some ini e ou come
se . Unde ixed ask o obse a ion scheme, hese dis ibu ions p o ide “obse able
in o ma ion s a e” o each con igu a ion x. Based on his, we de ine ask-sensi i e
ela i e en opy s uc u e DQ(x∥y), om which de i e amily o in o ma ion dis-
ances, e.g., Jensen–Shannon ype dis ance dJS,Q(x, y). These dis ances locally
induce disc e e Fishe s uc u e, i.e., nea some e e ence con igu a ion x0, Hessian
o second-o de ela i e en opy DQ(x∥x0) gi es disc e e in o ma ion me ic enso
a ound x0.
This pape p o es, unde na u al egula i y assump ions, disc e e in o ma ion
s uc u e can con e ge in app op ia e limi o Riemannian- ype in o ma ion man-
i old (SQ, gQ), whe e gQFishe - ype me ic; co espondingly, “in o ma ion geome-
y on con igu a ion space” can be ealized h ough map ΦQ:X→ SQ, p ojec ing
each con igu a ion x o i s obse able in o ma ion s a e. We u he discuss olume
g ow h o in o ma ion balls Bin o
R(x0) and “in o ma ion dimension”, gi e gene al in-
equali y be ween in o ma ion dimension and complexi y dimension, cha ac e izing
“in o ma ion esolu ion limi achie able unde gi en complexi y budge ”.
Finally, we cons uc ask-sensi i e in o ma ion–complexi y join ac ion unc-
ional AQ, whose local Eule –Lag ange equa ion gi es local desc ip ion o op imal
compu a ion ajec o y “maximizing in o ma ion quali y” unde ini e ime bud-
ge , p o iding disc e e in o ma ion geome y ounda ion o subsequen comple e
“ ime–in o ma ion–complexi y a ia ional p inciple”.
Keywo ds: Disc e e in o ma ion geome y; Rela i e en opy; Fishe in o ma ion me ic;
1
Jensen–Shannon dis ance; Task-sensi i e dis ance; In o ma ion dimension; Complexi y-
in o ma ion inequali y
1 In oduc ion
In compu a ional uni e se axioma ic sys em, uni e se abs ac ed as disc e e con igu a ion
space X, one-s ep upda e ela ion T, single-s ep cos Cand in o ma ion quali y unc ion
I, such ha any ac ual compu a ion p ocess co esponds o ini e pa h on con igu a ion
g aph, complexi y dis ance d(x, y) cha ac e izes minimum cos needed o go om x o
y. P e ious wo k al eady cons uc ed “disc e e complexi y geome y” based on his,
desc ibing p oblem di icul y and complexi y ho izon h ough complexi y ball olume
and disc e e Ricci cu a u e.
Howe e , complexi y geome y conce ns “how a walked”, no “wha seen”. To
unde s and geome ic s uc u e o “in o ma ion quali y” in compu a ional uni e se, need
o in oduce ano he dimension: obse a ion and ask. Speci ically, “use ul in o ma ion”
o same con igu a ion xdepends no only on xi sel , bu also on how we ead i ou ,
wha kind o ask we ca e abou . Di e en asks co espond o di e en “in o ma ion
geome ies”, and compu a ion p ocess ajec o ies on hese in o ma ion geome ies a e
ue objec s e lec ing “how much in o ma ion we ex ac ed wi hin gi en ime”.
Goal o his pape is o es ablish se o ask- ela ed “disc e e in o ma ion geome y”
o compu a ional uni e se in comple ely disc e e backg ound:
A disc e e le el, assign each con igu a ion xp obabili y s a e pxde e mined by
obse a ion scheme, cons uc in o ma ion dis ances using ela i e en opy, Jensen–
Shannon dis ance, e c.;
Locally, h ough second-o de expansion o ela i e en opy ob ain Fishe - ype me -
ic, es ablish disc e e in o ma ion mani old s uc u e;
Globally, h ough in o ma ion ball olume and in o ma ion dimension cha ac e ize
“unde ce ain ask, complexi y o dis inguishable s a es in uni e se”.
Mo e impo an ly, in o ma ion geome y and complexi y geome y mus ma ch: com-
plexi y geome y ells us which con igu a ions allowed o mo e be ween unde esou ce
cons ain s, in o ma ion geome y ells us how much in o ma ion gain hese mo emen s
b ing in “ ask- ele an s a e space”. Coupling o bo h will ul ima ely lead o uni ied
“ ime–in o ma ion–complexi y ac ion unc ional”.
Main h ead s uc u e o his pape as ollows. Sec ion 2 in oduces obse a ion
ope a o s and ask-sensi i e disc e e ela i e en opy s uc u e. Sec ion 3 cons uc s
disc e e in o ma ion dis ances and in o ma ion balls, de ines in o ma ion dimension. Sec-
ion 4 discusses local Fishe s uc u e and in o ma ion mani old limi . Sec ion 5 gi es
in o ma ion–complexi y inequali y and ask-sensi i e join ac ion unc ional p o o ype.
Appendix p o ides de ailed p oo s o main p oposi ions and heo ems.
2 Obse a ion Ope a o s and Task-Sensi i e Rela-
i e En opy
This sec ion in oduces obse a ion ope a o s and ask-sensi i e p obabili y s uc u e a
con igu a ion laye o compu a ional uni e se.
2
2.1 Obse a ion Ope a o Family and Obse able S a es
In compu a ional uni e se Ucomp = (X, T,C,I), con igu a ion x∈Xis in e nal s a e
o en i e uni e se. Obse e wi hin ce ain ime window can only access i h ough
ini e expe imen s o eadou p ocesses. To cha ac e ize his poin , in oduce obse a ion
ope a o amily.
De ini ion 2.1 (Obse a ion Ope a o Family).Le (Yj)j∈Jbe amily o ini e ou come
se s. An obse a ion ope a o amily is map collec ion
O={Oj:X→∆(Yj)}j∈J,
whe e ∆(Yj) p obabili y simplex on Yj, and o each x∈X,j∈J,Oj(x) = p(j)
xis
ou come dis ibu ion on esul se Yj om one expe imen .
In ui i ely, Ojdesc ibes obse a ional p ocess execu able on con igu a ion x, whose
ou pu dis ibu ion p(j)
xis s a is ical in o ma ion obse e can “see” on his con igu a ion.
To a oid edundancy, we o en deno e ask o obse a ion scheme as ini e subse
Q⊂J, de ine “join obse able s a e” unde his ask.
De ini ion 2.2 (Join Obse able S a e unde Task Q).Fo gi en ini e ask se Q⊂J,
de ine obse able ou come se
YQ=Y
j∈Q
Yj,
de ine con igu a ion x’s join obse able s a e as join dis ibu ion p(Q)
xon YQ. Simples
cons uc ion assumes obse a ions independen , in which case
p(Q)
x(y) = Y
j∈Q
p(j)
x(yj), y = (yj)j∈Q∈YQ.
Mo e gene ally, can allow known coupling s uc u e be ween di e en obse a ions,
hen p(Q)
xgi en by ask-speci ic obse a ion model. This pape mainly conside s indepen-
den case.
2.2 Task-Sensi i e Rela i e En opy
A e ixing ask Q, each con igu a ion xmapped o p obabili y dis ibu ion p(Q)
x∈∆(YQ).
This allows us o in oduce ela i e en opy o ask Q.
De ini ion 2.3 (Rela i e En opy unde Task Q).Fo con igu a ions x, y ∈X, i o all
y∈YQha e p(Q)
y(y)>0 implies p(Q)
x(y)>0, de ine
DQ(x∥y) = X
z∈YQ
p(Q)
x(z) log p(Q)
x(z)
p(Q)
y(z),
o he wise de ine DQ(x∥y) = +∞.
DQ(x∥y) is “dis inguishabili y deg ee” o con igu a ions xand yunde ask Q: la ge
means mo e “in o ma ion dis an ” be ween xand yunde his ask.
Clea ly, DQ(x∥y)≥0, and DQ(x∥y) = 0 i and only i p(Q)
x=p(Q)
y.
No e DQgene ally no symme ic and doesn’ sa is y iangle inequali y, hus no
me ic. To ob ain in o ma ion dis ance, we will use symme ized o m de i ed om DQ.
3
3 Disc e e In o ma ion Dis ances and In o ma ion
Balls
This sec ion de ines amily o in o ma ion dis ances om ask-sensi i e ela i e en opy,
cons uc s in o ma ion ball s uc u e and in o ma ion dimension.
3.1 Jensen–Shannon Dis ance
Mos na u al symme ized o m is Jensen–Shannon di e gence.
De ini ion 3.1 (Jensen–Shannon Dis ance unde Task Q).De ine JS di e gence
JSQ(x, y) = 1
2DQ(x∥mxy) + 1
2DQ(y∥mxy),
whe e mxy =1
2(p(Q)
x+p(Q)
y) midpoin dis ibu ion. Then
dJS,Q(x, y) = qJSQ(x, y)
de ines me ic on con igu a ion space (up o equi alence ela ion p(Q)
x=p(Q)
y).
P oposi ion 3.2 (Me ic P ope ies o JS Dis ance).dJS,Q sa is ies:
1. Symme y: dJS,Q(x, y) = dJS,Q(y, x);
2. T iangle inequali y: dJS,Q(x, z)≤dJS,Q(x, y) + dJS,Q(y, z);
3. Posi i i y: dJS,Q(x, y)≥0, equals ze o i p(Q)
x=p(Q)
y.
P oo . Symme y ob ious om de ini ion. T iangle inequali y ollows om End es-Schindelin
(2003) p oo . See Appendix A.
3.2 In o ma ion Balls and In o ma ion Volume
Gi en in o ma ion dis ance, can de ine in o ma ion balls.
De ini ion 3.3 (In o ma ion Ball).Fo con igu a ion x0∈Xand adius R > 0,
Bin o
R(x0) = {x∈X:dJS,Q(x, x0)≤R}
is in o ma ion ball o adius Rcen e ed a x0unde ask Q.
In o ma ion ball cha ac e izes se o con igu a ions “in o ma ionally close” o x0unde
ask Q. I s ca dinali y |Bin o
R(x0)|measu es “how many dis inguishable s a es exis wi hin
in o ma ion dis ance R om x0”.
4
3.3 In o ma ion Dimension
De ini ion 3.4 (In o ma ion Dimension).I limi
dimin o(x0) = lim
R→0
log |Bin o
R(x0)|
log(1/R)
exis s, call i in o ma ion dimension a x0unde ask Q.
In o ma ion dimension measu es “how densely in o ma ion s a es pack” nea x0. High
dimension means many dis inguishable s a es nea by, low dimension means spa se in o -
ma ion s uc u e.
4 Local Fishe S uc u e and In o ma ion Mani old
Limi
This sec ion cons uc s local Fishe in o ma ion me ic om second-o de expansion o
ela i e en opy, discusses con inuous limi o disc e e in o ma ion geome y.
4.1 Disc e e Fishe In o ma ion Ma ix
Conside small pe u ba ions nea e e ence con igu a ion x0. Assume con igu a ion space
has local pa ame e ep esen a ion: nea x0exis pa ame e s θ= (θ1, . . . , θn) such ha
con igu a ions uniquely co espond o θ alues.
De ini ion 4.1 (Disc e e Fishe In o ma ion Ma ix).Fo pa ame e ized con igu a ion
amily x(θ) nea x0=x(θ0), de ine disc e e Fishe in o ma ion ma ix a θ0as
g(Fishe )
ab (θ0) = ∂2
∂θa∂θbDQx(θ)∥x(θ0)θ=θ0
when his quan i y well-de ined.
4.2 Second-O de Expansion
P oposi ion 4.2 (Quad a ic App oxima ion o Rela i e En opy).Unde smoo hness
assump ions on p(Q)
x(θ)in θ,
DQx(θ)∥x(θ0)=1
2X
a,b
g(Fishe )
ab (θ0)δθaδθb+O(|δθ|3)
whe e δθ =θ−θ0.
P oo . Taylo expansion o second o de . Fi s -o de e m anishes by de ini ion. See
Appendix B.
This shows Fishe ma ix de ines local Riemannian me ic on pa ame e space, mea-
su ing in o ma ion dis ance o small pe u ba ions.
5
4.3 Con inuous Limi and In o ma ion Mani old
When con igu a ion space has con inuous limi (e.g., disc e ized ield con igu a ions con-
e ging o con inuous ields), disc e e in o ma ion geome y con e ges o con inuous in-
o ma ion mani old.
Theo em 4.3 (Con e gence o In o ma ion Mani old).Unde app op ia e egula i y con-
di ions on obse a ion ope a o s and e inemen sequence o disc e e con igu a ions, dis-
c e e Fishe me ics con e ge o con inuous Fishe in o ma ion me ic gQon con inuous
con igu a ion mani old SQ, o ming Riemannian mani old (SQ, gQ).
P oo . Uses s anda d echniques om in o ma ion geome y. See Ama i-Nagaoka (2000)
and Appendix C.
5 In o ma ion–Complexi y Inequali y and Join Ac-
ion Func ional
This sec ion es ablishes quan i a i e ela ionship be ween in o ma ion dimension and
complexi y dimension, cons uc s join ac ion unc ional coupling in o ma ion and com-
plexi y.
5.1 In o ma ion–Complexi y T ade-o
Theo em 5.1 (In o ma ion–Complexi y Inequali y).Fo any compu a ion pa h γ: [0, T]→
Xo complexi y cos C(γ), in o ma ion gain along pa h bounded by
∆IQ(γ)≤ C(γ),dimcomp,dimin o
whe e unc ion o complexi y cos , complexi y dimension dimcomp and in o ma ion
dimension dimin o.
P oo . Combines complexi y ball olume bounds om disc e e complexi y geome y wi h
in o ma ion ball bounds. See Appendix D.
This heo em cha ac e izes undamen al limi : gi en ini e complexi y budge , maxi-
mum achie able in o ma ion esolu ion bounded by in e play o complexi y and in o ma-
ion dimensions.
5.2 Task-Sensi i e Join Ac ion Func ional
To uni y complexi y cos and in o ma ion gain, de ine join ac ion.
De ini ion 5.2 (In o ma ion–Complexi y Join Ac ion).Fo compu a ion pa h γin ime
in e al [0, T], de ine
AQ[γ] = ZT
0αC(˙γ( )) −βIQ(γ( ))d
whe e C(˙γ) ins an aneous complexi y cos a e, IQ(γ) ins an aneous in o ma ion qual-
i y unde ask Q,α, β > 0 ade-o weigh s.
Minimizing AQyields ajec o ies balancing complexi y cos and in o ma ion gain.
6
5.3 Eule –Lag ange Equa ion
P oposi ion 5.3 (Op imal T ajec o y Condi ion).C i ical poin s o AQsa is y
α∇˙γC(˙γ) = β∇IQ(γ)
whe e ∇app op ia e de i a i es on con igu a ion space.
This gi es local cha ac e iza ion o op imal compu a ion ajec o ies maximizing in-
o ma ion quali y unde complexi y cons ain s.
6 Discussion and Ou look
This pape cons uc ed disc e e in o ma ion geome y amewo k o compu a ional uni-
e se, complemen ing complexi y geome y om p e ious wo k. Key achie emen s:
1. De ined ask-sensi i e ela i e en opy and in o ma ion dis ances;
2. Es ablished disc e e Fishe s uc u e and in o ma ion mani old limi ;
3. In oduced in o ma ion dimension and p o ed in o ma ion–complexi y inequali ies;
4. Cons uc ed join ac ion unc ional coupling in o ma ion and complexi y.
Fu u e di ec ions:
Ex end o quan um in o ma ion geome y o quan um compu a ional uni e se;
De elop nume ical me hods o compu ing in o ma ion me ics;
Apply o conc e e p oblems in machine lea ning and op imiza ion;
Comple e uni ied ime–in o ma ion–complexi y a ia ional p inciple.
This amewo k p o ides ounda ion o unde s anding no jus “how compu a ion
happens” bu “wha in o ma ion compu a ion ex ac s”.
A P oo o T iangle Inequali y o JS Dis ance
This appendix p o es P oposi ion ??.
A.1 End es-Schindelin P oo
The key esul (End es-Schindelin, 2003): √JS sa is ies iangle inequali y.
Fo h ee dis ibu ions p, q, , de ine midpoin s mpq,mq ,mp . Th ough ca e ul con-
exi y a gumen s and da a p ocessing inequali y, show
pJS(p, )≤pJS(p, q) + pJS(q, )
Applied o ou se ing wi h p=p(Q)
x, e c., gi es iangle inequali y.
7
B Second-O de Expansion o Rela i e En opy
This appendix p o es P oposi ion ??.
B.1 Taylo Expansion
W i e
DQ(x(θ)∥x(θ0)) = X
y
p(Q)
x(θ)(y) log p(Q)
x(θ)(y)
p(Q)
x(θ0)(y)
Expand bo h nume a o and denomina o o second o de in δθ:
p(Q)
x(θ)(y) = p0(y) + X
a
∂ap0(y)δθa+1
2X
ab
∂a∂bp0(y)δθaδθb+O(|δθ|3)
whe e p0=p(Q)
x(θ0).
A e subs i u ion and simpli ica ion using no maliza ion condi ions, i s -o de e ms
cancel, second-o de e ms gi e Fishe ma ix.
C Con e gence o Con inuous In o ma ion Mani old
This appendix ske ches p oo o Theo em ??.
C.1 Re inemen Sequence
Conside sequence o disc e e con igu a ion spaces Xnwi h la ice spacing an→0. As-
sume obse a ion ope a o s Oncon e ge app op ia ely o con inuous obse a ion unc-
ionals.
Disc e e Fishe ma ices g(n)
ab o m app oxima ions o con inuous Fishe me ic gab.
Unde egula i y (Sobole es ima es on p obabili y densi ies), g(n)
ab →gab in sui able
opology.
De ails in ol e ca e ul measu e- heo e ic a gumen s, see Ama i-Nagaoka (2000) o
s anda d p oo s in classical in o ma ion geome y se ing.
D P oo o In o ma ion–Complexi y Inequali y
This appendix p o es Theo em ??.
D.1 Volume Compa ison
Key idea: complexi y ball o adius Rcomp con ains a mos ce ain numbe o in o ma ion-
dis inguishable s a es, bounded by a io o olumes in complexi y s. in o ma ion geome-
ies.
Speci ically, i complexi y ball Bcomp
Rcomp (x0) has olume Vcomp ∼Rdimcomp
comp , and ypical
in o ma ion sepa a ion scale is ϵin o, hen numbe o dis inguishable s a es
8
Ndis ≲Vcomp
ϵdimin o
in o
In o ma ion gain along pa h o complexi y cos Cbounded by log Ndis wi h app o-
p ia e Rcomp ∼C.
De ailed calcula ion shows inequali y o Theo em ??.
9
