Low Degree Hardness for Broadcasting on Trees
Authors: Han Huang
Elchanan Mossel
Venue: NeurIPS 2024 poster (2024)
Keywords: Broadcasting Process
low degree hardness
statistically-computational gap
Primary area: probabilistic_methods

Abstract: We study the low-degree hardness of broadcasting on trees.
Broadcasting on trees has been extensively studied in statistical physics, 
in computational biology in relation to phylogenetic reconstruction and in statistics and computer science in the context of block model inference,  and as a simple data model for algorithms that may require depth for inference. 

The inference of the root can be carried by celebrated Belief Propagation (BP) algorithm which achieves Bayes-optimal performance. Despite the fact that this algorithm runs in linear time (using real operations), recent works indicated that this algorithm in fact requires high level of complexity. 
Moitra, Mossel and Sandon constructed a chain for which estimating the root better than random (for a typical input) is $NC1$ complete. Kohler and Mossel constructed chains such that for trees with $N$ leaves, recovering the root better than random requires a polynomial of degree $N^{\Omega(1)}$. Both works above asked if such complexity bounds hold in general below the celebrated {\em Kesten-Stigum} bound. 

In this work, we prove that this is indeed the case for low degree polynomials. 
We show that for the broadcast problem using any Markov chain on trees with $N$ leaves, below the Kesten Stigum bound, any $O(\log N)$ degree polynomial has vanishing correlation with the root.  

Our result is one of the first low-degree lower bound that is proved in a setting that is not based or easily reduced to a product measure.

Low Degree Hardness for Broadcasting on Trees
Han Huang
Elchanan Mossel Department of Mathematics MIT Cambridge, MA 02139 elmos@mit. @du
Department of Mathematics
University of Missouri Columbia, MO 65203 thuang@missouri... edu
Abstract
We study the low-degree hardness of broadcasting on trees. Broadcasting trees has been extensively studied in statistical physics, in computational biology in relation phylogenetic reconstruction and in statisties and computer science in the context of block model inference, and as a simple data model for algorithms that may require depth for inference.
The inference of the root can carried by celebrated Belief Propagation (BP) algorithm which achieves Bayes-optimal performance. Recent works indicated that this algorithm fact requires high level of complexity, Moitra, Mossel and Sandon constructed chain for which estimating the root better than random (for typical input) is NC1 complete. Kohler and Mossel constructed chains such that for trees with N leaves, recovering the root better than random requires polynomial of degree NR(I) Both works above asked if such complexity bounds hold in general below the celebrated Kesten- Kesten-Stigum bound.
In this work, we prove that this is indeed the case for low degree polynomials. We show that for the broadcast problem using any Markov chain on trees with N leaves, below the Kesten Stigum bound, any Ollog N) degree polynomial has vanishing correlation with the root.
Our result is one of the first low-degree lower bound that is proved in setting that is not based or easily reduced to a product measure.
Introduction
Understanding the computational complexity inference problems of random instances has been extensively studies in different research areas including statistics, cryptography. computational complexity, computational learning theory and statistical physics. The emerging field of research
mainly devoted to the study of popprratiionalt-ssttttttttt gaps. (3 24]
Recently, low-degree polynomials have emerged popular tool for predicting computational- to-statistical gaps, especially in the context of the Bayesian framework. Our work follows 23 in studying the polynomial hardness of broadcasting on trees.
very exciting line of work, including 19 18 25
26
recently showed that the
"low-degree heuristic" can be used predict computationallsstatiiiiio gaps for variety of problems such as recovery in general stochastic block models, sparse PCA, tensor PCA, the planted clique problem, certification in the zero- -erpperrrrererre Sherrington Kirkttrrriiikki model, the planted sparse vector problem, and for finding solutions in random k-SAT problems.
Interestingly, it was observed that the predictions from this method often agree with predictions from statistical physics heuristics based on the replica and cavity methods which are closely related to the analysis of BP/AMP fixed points, e.g. [12 13
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

It is often argued that low-degree polynomials algorithms are relatively easy to use (e.g. compared to proving SOS lower bounds), and that low degree polynomials capture the power of the "local algo- rithms" framework used in e.g. [6 I0] as well as algorithms which incorporate global information, such as spectral methods or constant number of iterations of Approximate Message Passing [29].
In this work, we continue to study the power of low-degree polynomials for the (average case) broadcast on trees problem. In broadcasting on trees the goal is to estimate the value of the Markov process at the root given its value at the leaves and the goal is to do so for arbitrarily deep trees. Two key parameters of the model are the arity of the tree d and the magnitude of the second eigenvalue of the broadcast chain.
A fundamental result in this area 22 is that when d|A|2 >> 1 nontrivial reconstruction of the root is possible by counting the number of the leaves of different types, an algorithm that could be described as linear function of the leave values. In contrast, when d/A/² < 1, such linear estimators have no mutual information with the root (but more complex statistics of the leaves may) 30 36..
This threshold d| = 1 is known as the Kesten-Stigunt threshold. A series of works showed that the KS threshold is the information theory threshold for non-trivial root inference for some specific channels, including the binary symmetric channel 66 14 21 20) and binary channels that are close
to symmetric 8 as well as 3 x 3 symmetric channels for large d [39].
While the Kesten-Stigum Stigum bound is easy to compute, it turns out that in many cases, it is nor the cnermation-thhoreetee threshold for root recovery. This was first established 30 for symmetric channels with sufficiently many states, specifically when q 2 C for some large constant C. Later it was shown for symmetric channels with q 2 5 states [39]. Recently, the results 37 provide more information about the case of q = 3 and q = 4. Many of the finer results in this area prove predictions from statistical physics. The connection between the broadcast problems and phase transitions in statistical physics was made in
[27]. and more recent predictions include [5 2 38) Moreover, the information -hheorett threshold may depend on the specific structure of the channel rather than solely on d and A. Notably, [30] also showed that there exists channels where non-trivial predictions of the root are achievable even when ||| = O.
Much of the interest in Kesten-Stigum threshold comes from the fundamental role it plays in problems, such as algorithmic recovery in the stochastic block model [
35 and phylogenetic reconstruction (31. Count statistics can be viewed as degree 1 polynomials of the leaves, which begs
3
the question of what information more general polynomials can extract from the leaves. See [32 for surveys on the topic.
In 2 was shown that À even polynomials of degree N where N = dd is the number of leaves of for a d-ary tree of depth f, for a small e >> 0 are not able to correlate with the root label (as l tends to oo), whereas computationally efficient reconstruction is generally possible as long as is a sufficiently large constant [30].
The main motivation of 23 was prove that low degree polynomials fail below the Kesten Stigum
bound: "It is natural to wonder the Kesten-Stigum threshold d|A|2 = 1 is sharp for low-degree
polynomial reconstruction, analogous to how it is sharp for robust reconstruction." However the main result of (23) only established this in the very special case of X = 0. This problem is also stated in the ICM 2022 paper and talk on the broadcast process (34): The authors of (23 ask if similar phenomenon holds through the non-linear regime. For example, is it true that polynomials of bounded
degree have vanishing correlation with X, in the regime where d\² < 1? 'The main results of this paper prove that this is indeed the case. We proceed with formal definitions and statement of the main result.
1.1 Definitions and Main Result
Rooted Tree
Recall that every rooted tree T inherently defines a partial order relation among its vertices: For a pair of distinct vertices, u is said to be an ancestor of v (and v descendant of u), denoted as < in this paper, u is contained in the unique path from v to the root p. Specifically, if v and u are directly connected by an edge, we also refer to
child vertex of u (and u as the parent vertex of v). By S u we mean that u is either a descendant of u or e = u. In general, if v < u and the path distance between them is k is referred to kth-descendant of (and the kth ancestor of v).

---

For nonnegative integer k, the kth layer of the tree refers to the set of kth descendants of the root (The root here is considered at the Oth layer of the tree.) The depth of the tree is defined as the largest non-negative integer É for which the ?th layer is not empty, and we denote the /th layer by L.
The height of vertex is defined
h(u) e- the layer of
In particular, when the set of leaves, then h(u) is simply the distance from u to L. In this paper, we may abuse the notation by writing T or S _ 'I' to mean that is vertex S is subset of vertices in the tree T.
The standard rooted d-ary tree with depth é is tree where each vertex & L has exactly d children vertices. Let us start by defining the type of trees we will be investigating in this paper, which is slight generalization of d-ary tree.
u
Figure 1: An example of binary rooted tree of depth 5 is shown. The vertex u is at the 3rd layer and h(u) = 2. Further, the following relationships hold: v < u and v a child of u, s E is a 2nd descendant of u, is the parent of u, and is the 2nd ancestor of
Definition 1.1. A rooted tree with root p has degree dominated d 2 with parameter R 2 1 if for every vertex u and positive integer k, the number of kth descendants of u is at most Rd
With the above definition, d-ary rooted tree has degree dominated by d > 1 with parameter R 1. Further, a typical realization a Galton- Watson tree of Poisson type with average degree and of depth & (a random tree in which each vertex & L has average d children vertices) has degree dominated by d 2 with parameter R = log(E).
Broadcasting Process Rooted Trees
Next, we will define the broadcasting process rooted tree T with root p. Consider x ergodic transition matrix M, where 2 2. Recall that every eigenvalue of a transition matrix M has an absolute value at most 1. Let < À 1 represent the second largest absolute value among the cigenvalues of M. Additionally, we define the stationary distribution of M as π.
The broadcasting process X = (X,)eeT, with state space [g] {1, 2....... q) and transition matrix M, can be formally described as follows: We initialize the value of X, according to some initial distribution As we reveal the values layer by layer, when the value X,, is revealed, the value X, for any child vertex v of is independently distributed according to a specific row M depending on the value of X.,:
P(X, Xx, s) Ma1-
In other words, each vertex's 's value depends only its parent vertex's value. The definition of the process is given below:
Definition 1.2 (Broadcasting Process Tree). Let q 2 be positive integer. For any rooted tree T with root p and a q x q ergodic transition matrix M, the broadcasting process X = (Xe)ver with state space (q), according to transition matrix M with an initial distribution v for X po is random process with joint distribution given by:
Yr -xx)veT [.]T P(X r) v(xpp) II
M M (v,44
3

---

where the product is taken over all pairs (v, u) such that is a child vertex of u.
For subset of vertices A T, let us denote
XA= (X.)oEA
If the tree just a path, then the process reduces to a Markov chain. If we assume V n, then , as (Xe) for every downward path of T forms a Markov Chain with
X, ~ π for every transition matrix M. Further, let us make a remark about the Markov property of the process.
Remark 1.3 (Markov Property). The broadcasting process establishes Markov Random Field on tree T: Given any three disjoint subsets A, B, and C of T, T vertex in C passes through vertex in B, then the random variables X, and X conditionally independent given XB-
every path from a vertex in to
Polynomials of Fr, and the Main Result
Definition 1.4. Let [q]_. For let zgg (No)egw- For subset U T, let Iu (Iu)uEV-
The next definition is about the notion of degrees for functions with variables æy = (oo)eeL. This is the generalization of degree polynomial. Definition 1.5 -Efron-Stein Degree). A function f with variables æ has Efron-Stein degree most if can be expressed as
I=E
where the summation is over a finite set of indices o, and each fo is a function of the variable as for some S S with |S| < k.
Now, we could properly formulate the main result of the paper:
Theorem 1.6. Let T be a rooted tree with root p of depth l and has degree dominated by 2 with parameter R 1. Consider the broadcasting process T with q transition matrix M and X, ~ т. If M is ergodic and dx2 < 1, then there exists a constant c >> O which depends on M and 2x² such that the following holds: For any function (xL) of Effon-Stein degree S. "IHlgghyy we have
(E (f(x) xx,) 1 fmaxfdd2,
Remark 1.7. Given that d13 implies X² < 1, and À < 1 if and only if X2 < 1, we can infer that À from the given conditions. Consequently, the term max(dX2, }} < 1 follows from the assumptions of the theorem. Therefore, the R.H.S. of the inequality decays exponentially with the depth of the tree.
Follows from the theorem and propteries of conditonal expectation, we have the following corollary.
Corollary 1.8. With the same setting as in Theorem 1.6 for any function (x1. of Efron-Stein degree
S C (55 and any function g( of the root value, their correlation satisfies
Cor((((x1),((x))) = [(( - (x(X)))(X(XX,) -Eg(x))) < (max(dx),)))
(Var(f(2))/Vartot))
The proof of the theorem is based recursion notion of fractal capacity of functions. Indeed, the main result is optimal in the fractal sense (Thcorem 1.16). as we will later demonstrate that all functions with fractal capacity up to level proportional to exhibit vanishing correlation with the root, whereas all functions of the leaves have fractal capacity at most + 1. Let us introduce the necessary definitions and notations introduce both the fractal capacity and the proof overview.
1.2 Fractal Capacity and Proof Overview
To provide clearer illustration, we establish correspondence between the vertices of 7 and words of varying lengths from 0 to e, with vertices at the kth layer represented as words of length k. We

---

denote the root the empty word (). For each vertex represented by the word (b1, .......uu b we define du as the number of children vertices of u. and we identify these children vertices as (bi, .e.... be, i) with i E [dw]] {1. 21,2... ..2,...,,d Notice that v is descendant of is equivalent to (br....,be) by) E 7 and [du]. let
is prefix of v. For brevity, for each
u, = (u, 1) .b......
....... bk. 1).
For 7
[du], let
u1 (usteEI.
Furthermore, we denote the parent vertex of as p(u) = (b1.... bb-1) and the set of children vertices u as c(u) U[da].
(11)
(12)
U.
(111)
(121)
(122) (181)
(183)
(211)
(212)
U,
1/
U
Figure 2: the these figures, we present the vertices words and adapt the notations #1, etc.
for the descendants of u. For the right figure, if $ = fu21. 122, U32 } then p(S) = I(S) = (2, 3}.
and S2 (221, ]. S3 = ]. Further, S E A3. S2 E Ag, and S3 E As.
Definition 1.9. For a non-emply subset C L, we introduce the notation p(S) to represent the nearest common ancestor of the vertices in S. meaning that P(S) is the vertex with smallest height that is an ancestor of all vertices in S.
Here we consider the case when |S] > 1. Notice that p(S) is not at the lth layer L. For each child p(S); of for [do(s)], we define the set as
S = Sn E L 8 p(S):)
which is the collection of vertices that are descendants of p(S), Let
((S) (i E [dp(s)] S; # 0).
Then, can be expressed as the disjoint union of the sets forort i E I(S):
L
We call the above disjoint union the branch decomposition of S, and each So i E T(S) a branch part of S.
The branch decomposition is key concept in the proof, and we define the fractal capacity according the number of iterations decompose S into singletons.
Definition 1.10. Let
A = {u) : uE C (2)100)
be the collection of singletons of L. We say subcollection A S 2d (0) is closed under decompo- sition with base A₁ for every E A', we have S, E A I(S).
Definition 1.11. For any AS 20) let
B(A) C 2
be a new subcollection defined according to the following rules:
For any S (00, S B if and only if one of the following two conditions holds
5

---

1. S E A1
2. S $ A1 and S; E Afor E 1(S).
For example, ((A) contains sets of size S
Lemma 1.12. Af C C (0) is subcollection closed under decomposition with base A then the collection B B((A) contains A and it is also closed under decomposition with base A1.
Proof. To show A C B, it is sufficient to show A/A C B. For any S E A', because A is closed under decomposition. S; E A for i E I(S). Hence, S follows from the definition of B. Now, for S B A1, each S; with I(S) is contained in A C B, which in turn implies B is closed under decomposition.
Now, define recursively that
A BB
(2)
for positive integer k > 2. Observe the following facts: Consider any non-singleton set S C L and S; with i E T(S). First, E A& = S; E A 1 by the definition A Second, p(S) > p(S:) by the definition of branch decomposition. Given these two facts, can prove inductively that
h(p(S)) = k + S E Ai+1-
Since that there are only e layers of the tree, conclude that every non-emptyset of S L is in A4t1. Therefore, together with Lemma 1.12 we have the following chain of subcollections:
Hu} [E - A2 -... S A = (00).
Definition 1.13 (Fractal Capacity). For any non-empty subset S C L,, we define the fractal capacity of S as the smallest k such that S E As.
We introduce the notion of fractal capacity, borrowing terminology from fractal geometry. The recursive nature of our definition subsets of trees mirrors the self-similar complexity found in fractal structures. This recursive and inherently intricate structure motivates our choice of the term fractal capacity, capturing the fractal- properties that emerge in the collections (A*))
Definition 1.14. Given collection A 20) A function f [q]TT R is called A- polynomial if we can express
f(x) Σ fs(xs)
SEA
where each fs is a function xs = (xo)vEs. A functio f :qi R has fractal capacity S k if it is Asppolynomial.
Remark 1.15. It is not hard to verify that A& contains all non-empty subsets S C L with |S| < k. Thus, for any function f with variables Tz.
Efron-Stein degree of f S k + is an A --looynomial.
On the other hand, is worth to remark that for the d-ary tree of depth 2 there exists S A with |S| = =-1, (Namely, taking S (u E I, < u) for some with li()) = k 1.) Thus, an A&- Asppolonoia could have an Efron-Stein degree exponential in k.
The main result of the paper in terms of the fractal capacity is the following:
Theorem 1.16. With the same setting as in Theorem [.6] there exists a constant c > which depends on M and dX2 such that the following holds: For any function f(x1. with fractal capacity 8 C CTToog(Ry we have
Var (ar(EE
Indeed, Theorem 1.6 is direct consequence Theorem 1.16 as As-polynonials contains all polynomials of Efron-Stein degree < k. Further, in terms of fractal capacity, the theorem is optimal because the correlation decay persists up to an order proportional while fractal capacity S includes all functions of the leaves.

---

Overview of the Proof Idea: For illustration, let consider the case where T is a binary tree of
[1+A
1-A
depth l with M = 1 1 such matrix has eigenvalues À and Here we assume 2X² < 1.
2
We recall that for this binary symmetric broadcasting process, it is information-theorriicall impossi- ble to recover the root label from the leaves below the KS bound. This implies that all polynomials of Xg have vanishing correlation with Xp. Still, idea as our arguments for low-degree polynomials generalize to general broadcasting processes below the Kesten-Stignn to estimate the root from the leaves non-trivially (in such cases there exist functions f so that lim inf Corr(f(X2), Xp) > 0).
this simple process to illustrate the proof
threshold, including cases where it is information theoretically possible
Now, let us consider degree-1 polynomials. Suppose f Appolyyoomial (equivalently, of Efron- Stein degree 1), we can express it in the form
f(LL)
Eu(u))
WEL
where each fu is function of Za. Given our focus on the variance, we may assume (X,, for each L. Then, our goal is to prove E| (EIf(X)) xxl)) I [(( Following from the Cauchy- Sechwar inequality that
is negligible comparing to
a,)
Σ {m(m!
1 a.)2 S m
a
EE mm)
[E(A]
we have
[(((((()))
|
Σ [[ [
(3)
NEL.
2
2 2 (X.))) = (2X3) Σ B (X.))))
WEL
uEL
where the second inequality is derived from the variance decay property of in a Markov Chain. Thus, if we can establish EVEL [x)) is at the same order as IE [ff((L))) the proof is complete.
Notice that
[(U((X))) = Σ (lf((X.)) = Σ ((()(X + Σ ((
uDELL
HEL
WFEEL
Thus, the goal here is to show
Σ ((fx(X.)fx(X.,]
<c Σ E((()(
(4)
net
for some constant e (0, 1), which in turn implies the desired result:
[x() S (2 Σ [((G((,)))] (2x²) 1 [[((x)))))] WEL
Roughly speaking, holds for most pairs u and v within L, the correlation between Su (X,) and (Xx) is sufficiently small, which is the case for degree-1 polynomials.
Now, let us take a closer look. Fix any two vertices and in L, with their nearest common and S w2. Let Xgw, (X )u' gw-- We have (X = -IEBL (x.) X Xx
ancestor. Suppose
(5)
S EV (X.m) X SSh(w)
(X.))((X.))
where the last inequality follows from the variance decay of the Markov Chain for length h(w). The above inequality implies that the correlation between fa (X.)) and (X,,) is most of order Ab(w),
7

---

The above bound can be improved to X by also taking the conditional expectation (X.)) X Xxwl into account, which requires the Markov Property that X, and X, are independent conditioned on X From here, one can properly arrange the terms and apply Cauchy-Schwarl inequality to show holds.
Our proof of the main theorem tries to generalize the argument above to low degree polynomials. Let us summarize it by the following five pieces of descriptions.
Bounding Covariance: First, we generalized the idea on how Suppose fa and fa are two functions so that the following holds.
5 works for degree-1 polynomials.
1. fa (ars) function of x for some set S S L such that
(X() g)))) < (E(fa(Xss)²
where we use a < to indicate a is much smaller than b. We keep this not precise to avoid technical details, but expect that the ratio is exponentially small in h(w').
2. (3()))) is a function of zs with S" C L. satisfying S' n {v' v S w/) = 0.
Then, following the same derivation as shown in (5) we have
(Xs) [X [X <
<VL (E((s(Xs:))
(See Figure 3 for illustration.)
Figure 3: In the left figure, the purple dots represent the corresponding input variables for fa. and the yellow dots represent the corresponding input variables for f3. In the right figure, the purple dots represent the corresponding input variables for B[fa (X) X gg, and the variables do not involve for vertex v not illustrated due to the Markov property.
II Choosing a good decomposition of the function: In essence, our proof strategy for any given function (x1 with (X(x revolves around decomposing í (x11 into of functions fa (x) for a in some index set I, such that
1. I 2
2. For each a, EX,((x)) and E[EE]. |X
E(()((
3. Whenever + B, we can find E T so that Sa and ʃa satisfy the covariance bound in I. (Possibly with a switch of the roles and (3).
Let us remark that while we are writing (xr.), it does not mean that fa depends on every leave variables.
this is the case, then we could follow the argument in the degree case to show that desired result holds.
III. From A& polynomials to A&+1 polynomials: The proof of the main theorem builds on and II and advancing through recursion on the fractal capacity of the function. This recursive approach relies on the following property:
Suppose we have shown the second moment decay A& polyoooooialss with mean 0 in the following sense: For every Aş Asppolynomial (xx)) with mean and variable æs where S C (u E L v S p'} for some vertex p/.
E (E
X 1
(6)

---

where AA is some penalty constant depending on Ag. (The bigger the value hA the weaker the second moment decay.)
Consider a specifie type of A A Fix a pivot vertex w with h(w) large enough, let Fig;; (Zu)oSu; for i [2]. Let be function of the form
(x) g IZwz)
Σ 90.1 ( 20.2( aE3
where J is a finite index set and every 9a.i is an A polynomial whose variables are 2sw. (more precisely, its variables x.. where S' C (u E L. function g(x) is Ak+1-polynomial with variable æs for S C T. ausssn w).
w:)) and Ega, (Xx = 0. Then, the
Observe that, if we fix u2 then Igen + g(I Iswa) ) is Au-polynomial with variable zş for S {u v S w and mean This allows us to apply the assumption for As polynomials to show
[ Swi Fgww)) xx (dA3) ( hav
Swi +
Clearly, the same inequality holds with the roles of Tgg and iggun switched.
Base on this, one key step in the paper is to show g satisfies
[[(E[g( ( Sgw X X xm, S (dA (dA))h(()~haaBBCC Blo(( X) for i E [2].
(7)
This inequality is immediate if X Xgw and X Xww, are independent, which is not the case in the broadcasting process. One of the main technical challenges the proof is to show that the inequality holds when Xzm, and Xgw, are conditionally independent given X by the Markov Property. It
turns to impose significant technical challenge when some entries of M can be 0.
Observe that (7) not only implies g satisfies the desired second moment decay for (I). but also ((1) with w' to be either Wi u2. Indeed, these two properties will also hold for g(x) g(x) - Eg(X). the normalized with mean 0, due to (E)( is negligible comparing to Eg(X)
IV. A closer look at the decomposition:
Consider any Au4i-polynomial of variable us for S {o E : v S p'} for some vertex p'. Before we proceed to the discussion of the decomposition, we remark that one cannot simply express the form of described above with any pivot vertex w.
Let us give an example to illustrate why: Consider two functions f1. f2, where fi is a function of Is with S {ue cannot be expressed in the form with any pivot w by using the property "if we fix Jsw2, then Tzgw, + g( )gww)) is Au-polynomial" discuessed in III to derive contradiction.
p and S' E Ax+1 AA. Let f fi f2. Then one can justify that
The way decompose f is to express it sum of functions of the form ğ(x) in III. While the actual decomposition requires more adjustment, it follows from the idea to decompose f form
Σ fw. WEI
where the index I is the set of vertices of T' with height slightly greater than hA, (to ensure correlation decay). Each far is function with variable xs for S S (u E L u I w) satisfies the description of ((x) in III.
Observe that this decomposition satisfies the description in II:
The size of I is bounded by 2 2 +... 2
The second moment decay property of fw follows from III.
< u, say v S u1, then fu and fo satisies the covariance bound condition stated in with fa = far fa f2, and n' = u2. The case when u < e is similar. When u and are not comparable, then following the Markov Property, (
Finally, consider u, v E
[ with being the nearest common E Xx
ancestor of u and v and z = (Xwr) )wr gwss which makes it easier to show the covariance bound. (See Figure 4 for an illustration.)

---

M
Figure 4: In both figures, the purple dots represent the corresponding input variables for fa. and the yellow dots represent the corresponding input variables for fe. In the left figure, we have S < In the right figure, we have u and v are incomparable and is the nearest common ancestor.
With this desirable decomposition, one could try to apply some argument similar to the degree-1 case show the second moment decay (6) for mean -polynomiass with slightly bigger penalty constant b than A
V. Overview the induction Given the decomposition of f described in IV, together with the second moment assumption 6 on pollooonomsals described in III, the proof of the main theorem proceeds by induction. The goal is show that the penalty constant hA, associated with Ak. which appeared (6), satisfies the following recursive inequality:
hAR S hA, + C, and hA SC
for some constant C' depending on M and dA². If true, by taking to be proportional to E/C, then the theorem follows. The proof of the theorem requires careful analysis of the covariance and variance decay to demonstrate that it resembles the behavior observed in the degree-1 case, in order capture the Kesten- -tiguum bound.
Comparison to other work in low-degree polynomials While some high-level ideas align with previous work in low degree polynomials mentioned fore, approach focuses establishing low- degree lower bounds in setting where direct comparisons are challenging due to structural differences. Specifically, work addresses the broadcasting process trees, where the underlying structures are highly correlated and do not naturally lend themselves to a product measure representation, presenting unique technical challenges not encountered in more independent setups.
10

---

Acknowledgments
Han Huang was supported by Elchanan Mossel's Vannevar Bush Faculty Fellowship ONR-N00014- 20-1-2826 and by Elchanan Mossel's Simons Investigator award (622132). Elchanan Mossel was partially supported by Bush Faculty Fellowship ONR-N00014-20- 1-2226,, Simons Investigator award (622132), ARO MURI W91 INF1910211 and NSF award CCF 1918421.
References
[1] Emmanuel Abbe. Community detection and stochastic block models: recent developments, The Journal of Machine Leurning Research, 18(1):6446-6511 2017.
[2] Emmanuel Abbe and Colin Sandon. Proof of the achievability conjectures for the general stochastic block model. Communications on Pure and Applied Mathematics, 71(7):1334 1406, 2018.
[3] Afonso Bandeira, Amelia Perry, and Alexander S. Wein. Notes computaationalllossttiiiiioo gaps: predictions using statistical physics. Port. Math., 75(2), 2018.
[4] Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein. Computational hardness of certifying bounds on constrained pea problems. In ITCS, 2020.
[5] Jess Banks, Cristopher Moore, Joe Neeman, and Praneeth Netrapalli. thooooicion-hhcorrtiic thresholds for community detection sparse networks. In Conference on Learning Theory, pages 383-416. PMLR, 2016.
[6] P. M. Bleher, J. Ruiz, and V. A. Zagrebnov. On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice. J. Statist. Phys., (9(1-2):473-44 482, 1995.
[7] Charles Bordenave, Mare Lelarge, and Laurent Massoulié. Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs. Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium pages 1347-1357. IEEE, 2015.
[8] C. Borgs, J. Chayes, E. Mossel, and S. Roch. The kesten-stigum reconstruction bound tight for roughly symmetric binary channels. In Proceedings of IEEE FOCS 2006, pages 518-530, 2006.
[9] Guy Bresler and Brice Huang. The algorithmic phase transition of random k--sat for low degree polynomials. FOCS, 2021.
[10] Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman. Suboptimality of local algorithms for a class of max-cut problems. The Annals of Probability, 177311157-- 2019.
[11] A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová. Asymptotic analysis of the stochas- tie block model for modular networks and its algorithmic applications. Physics Review E, 84:066106, Dee 2011.
[12] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6):066166, 2011.
[13] Yash Deshpande and Andrea Montanari. Finding hidden cliques of size / NNee in nearly linear time. Foundations of Computational Mathematics, 15(4): 1069-110691128 2015.
[14] W. S. Evans, C. Kenyon, Yuval Y. Peres, and I.. J. Schulman. Broadcasting trees and the Ising model. Ann. Appl. Probab., 10(2):410-4333 2000.
[15] David Gamarnik, Aukosh Jagannath, and Alexander S Wein. Low-degree hardness of random optimization problems. 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 131-140. IEEE, 2020.

---

[16] David Gamarnik and Madhu Sudan. Limits of local algorithms over sparse random graphs. In Proceedings of the Sth conference on Innovations in theoretical computer science, pages 369-376, 2014.
[17] Justin Holmgren and Alexander S Wein. Counterexamples to the low-degree conjecture. In ITCS, 2020.
[18] Samuel Hopkins. Statistical inference and the sum of squares method. PhD thesis, Cornell University, 2018.
[19] Samuel Hopkins and David Steurer. Efficient bayesian estimation from few samples: community detection and related problems. 20/7 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 379-390. IEEE, 2017.
[20] D. Ioffe. Extremality of the disordered state for the Ising model on general trees. In Trees (Versaillex, 1995), volume of Progr. Probab., pages 3-14. Birkhäuser, Basel, 1996.
[21] D. loffe. On the extremality of the disordered state for the Ising model on the Bethe lattice. Lett. Math. Phys., 37(2):137-144 1996.
[22] Harry Kesten and Bernt P Stigum. Additional limit theorems for indecomposable multidi- mensional galton-watson processes. The Annals of Mathematical Statistics, 3766):1463-1481, 1966.
[23] Frederic Koehler and Elchanan Mossel. Reconstruction on trees and low-degree polynomials. Advances Neural Information Processing Systems, 13:18942--199 2022.
[24] D. Kunisky, A.S. Wein, and A.S. Bandeira. Notes on computational hardness of hypothesis test- ing: Predictions using the low-degree likelihood ratio. Mathematical Analysis, its Applications and Compulation. ISAAC 2019. Springer Proceedings in Mathematics and Statistics, 385, 2022.
[25] Dmitriy Kunisky, Alexander Wein, and Afonso S Bandeira. Notes on computational hard- ness of hypothesis testing: Predictions using the low-degree likelihood ratio. arXiv preprint arXiv:1907.11663 1636, 2019.
[26] Cheng Mao and Alexander S Wein. Optimal spectral recovery of a planted vector a subspace. arXiv preprint arXiv:2
[27] M. Mézard and A. Montanari. Reconstruction trees and the spin glass transition. Journal of Statistical Physics, 124:1317-135,, 2006.
[28] Sidhanth Mohanty, Siqi Liu, and Prasad Raghavendra. On statistical inference when fixed points of belief propagation are unstable. In IEEE 62st Annual Symposiun Foundations of Computer Science (FOCS), 2021.
[29] Andrea Montanari and Alexander S. Wein. Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation. Probability Theory and Related Fields, 2024.
[30] E. Mossel. Reconstruction on trees: beating the second eigenvalue. Ann. Appl. Probab., 11(1):285330, 2001.
[31] E. Mossel. Phase transitions in phylogeny. Trans. Amer. Math. Soc., 356(6):2379-2404 (electronic), 2004.
[32] E. Mossel. Survey: Information flow on trees. Nestril and Winkler, editors, Graphs, Morphisms and Statistical Physics. DIMACS series in discrete mathematics and theoretical computer science, pages 155-170. 2004.
[33] E. Mossel, Neeman, and A. Sly. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, (3-4):431-461, 2015, The Arxiv version of this paper is titled Stochastic Block Models and Reconstruction.
[34] Elchanan Mossel. Combinatorial statistics and the sciences. International Congress of Mathematicians: 2022 July 6-14, volume 6, chapter 5553, pages 1-20. 2023.
12

---

[35] Elchanan Mossel, Joe Neeman, and Allan Sly. A proof of the block model threshold conjecture. Combinatorica, 38(3):665-7088 2018.
[36] Elchanan Mossel and Yuval Peres. Information flow on trees. The Annals of Applied Probability, 13(3):8178444, 2003.
[37] Elchanan Mossel, Allan Sly, and Youngtak Sohn. Exact phase transitions for stochastic block models and reconstruction on trees. In STOC 2023: Proceedings of the 55th Annual ACM Symposium Theory of Computing, pages 96-102, 2023.
[38] Federico Dicci-Tersenghi. Guilhem Semerjian, and Lenka Zdeborová. Typology phase transitions in bayesian inference problems. Physical Review E, 99(4):042109, 2019.
[39] A. Sly. Reconstruction of random colourings. Comm. Math. Phys., 288, 2009.
[40] Alexander S Wein. Optimal low-degree hardness of maximum independent set. arXiv preprint arXiv:2010.06563, 2020.
[41] Lenka Zdeborova and Florent Krzakala. Statistical physics of inference: Thresholds and algorithms. Advances in Physics, 65(5), 2016.
13

---

Appendix
Overview
Section
we give additional notations and basic tools.
In Section
we formulate the main theorem we want to prove as an induction statement.
we discuss the case for degree 1 polynomial, which prove the base case of the induction in the theorem, and the results for degree polynomial will be used in the inductive step.
In Section
In Section give procedure to decompose B-polynomial f for given collection B. we derive the proof of Theorem B.6 the inductive step for proving
In Section
H and
Theorem B.1
In Section G and
H
derive the main result in the general case.
In Section !
provide a proof of Proposition C3 which is one technical obstacle for getting our main result from Theorem B.1 to the general setting (Theorem T.6p. It is
postponed this section due the proof is essentially result about Markov Chain.
In Section
J
we provided some standard result for decay of Markov Chain.
A
Additional Notations and Tools
Let us begin with the proof of Remark 1.15 which shows As, contains all non- non-empty subsets of L of size k:
Proof of Remark 1.15 The proof will be carried out by induction on The base case with = follows from the definition A {(r v E L.. Suppose the claim holds up to some positive integer k. Let 0 # S C L of size |8| S k k If [S| < k. then S As C B(As) A In the case S = k + 2 2. we first observe that p(S) is not leave. Consider the branch decomposition
of S (See Definition 1.9
= LJEss
Because |((S] 1, for each i E I(S) we have |S| < ||| = k + 1. Therefore, S E As for i ISS, which in turn implies S E B((AA) Ak+1- Therefore, the claim follows.
Now, to show the second statement. For every node w. let Sw, = {o layers above T., then S., are the (k - 1)th descendants of w, which has size |S.| d
v S w). Observe that
We claim that for w which are k- - layers above L, then S., E A Let us prove the claim by L, S., {w} Aj. Suppose the statement holds up k. Take any w which is & layer above L. Then, the branch decomposition of Sn, = S. With each we is k layer above L, we have S.,, E Ag. Hence, S., E Ac+1 due to Ac+1 = B(AA).
induction. First, is clear that for
A.1 Additional notations
For any positive integer n, let [n] denote the of positive integers from n, inclusive: [n] 1, .2.....2. n. For integers a and b where a < b, let [a, b] {a, a + 1.....b).
Additional Notation for Trees
For T. we define
[x(u)
to be the set of kith descendants of u. For brevity, let La = La (p). Further, for h E [0, h(w)), let a and h(v)) h), namely the of descendants of which has height h. Observe that
Du(u) (u ET
Dz(u)= (u))
14

---

Last, let
T. be the induced subgraph of I' with vertex set {u E T S uj and L, = Tw n L. It is worth noting that Tu can be seen rooted tree with root u and h(u) layers, and the h(u)th layer is Lu.
Additional Notation for collection A - 2" {0}
Definition A.1. For a given collection of of subsets A C (0), we define the following subcol- lections: For each T. let Au = {S A p(S) = u). Açu {5 A p(S) S u). and Aça == (S E A ((S) < u..
Notation for Conditional Expectation
Definition A.2. Recall that antichain U C T is collection of vertices such that two vertices U are compurable under the relation. For x [g] we can decompose x in the form
I = (x TU, ggU),
where
E<U (I, Bu E U s.t. v S u), and EgU (D. Vu U, $ u).
(See Figure for an illustration.)
Figure 5: In this figure, the purple dots represent the set U. The yellow dots represent the vertices corresponding to the variables x-UU, and the green dots represent the vertices corresponding to the variables ZgU.
Definition A.3. [Conditional Expectation]
For each antichain U T T and f [a] + R let
(Eu ()(x) = E. [(x)) Xu Ju, Xzu zgu
To rephrase it, the function (Exr))()) represents the expected value of f(X) condition X,, x. for all vertices v that are not descendents of any u E U. In the case when U = {u). we will abuse the notation and denote E,, [qquy for E T. Futher, for any h E [0, set
(E) = E fXX Yo E T with h(v) 2 h, X. = _o]
Remark A.4 (Conditional Expectation and the Markov Property). Suppose f is function of xy and an antichain of T. Let
i= 3u s.t. v S u) and L'= - = L.
We remark that by the Markov Property,
Exf(z) Eu f(v. x
function of zy and mzz To see that, by the Markov Property, x<U and agu are independent conditioned on zv. Thus,
(Eu æzu) =B f(X Xx:)
Xu = TU. X&u = Zzu
-B
[5x [(X;
Xu = xU
which implies Ey is a function of xy and vv. (See Figure 6 for illustration.)
15

---

The purple dots represent the set U. In the left figure, the yellow dots represent the vertices corresponding to the variables f. the right figure, the yellow dots represent the vertices corresponding to the variable of f.
Figure 6:
A.2
Basis Functions on [a] and some decay properties
The following lemma is well-known statement from Markov-Chain. Let formulate it using the Broadcasting Process. (For completeness, we include a proof of this lemma in Section J
Lemma A.S. Suppose M irreducible and aperiodic, then there exists following hold: For any u E ' and l E N so that (u) = popo...ppu)) the kth ancester of
C(M) > so that the
times
exists. For every function with variable Vu.
Var (EE (x)) s X Var[a(Xw.]
(8)
and
C-1
max aa()) - -Ba(Xx)) < Vary SC
max a()) Ea(Xx))
(9)
RElul
PEly.
And from the above two inequalities, adjusting the constant C if necessary. we also have
max
(Ep)(u)a)()) - Ea(X.)l & C max (a()) - Ea(X,))
(10)
0E(n]
AE[g]
In this paper, we will fix basis for the space of functions from [g] to R for Markov chain M. Definition A.6. For given X ergodic and irreducible transition matrix M, we fix a basis (di 1] for the space of f iq] to such that dg is the constant function 1 and @:
for E are functions such that
By) =0 and BVY)
Definition A.7. Suppose given layer rooted tree T and g x q transition matrix described in Lemma A.5 have been given. For [0,4 1]2, let
S(a) = {u: o + #0 L, the set of vertices in L in which a is non-zero. Let |o| = -(())), When |o| 2 1, we define
p(a) = P(S(a))
And when |o| 2 2, we define
I(o) = ((S()))
Further, let
2o (x) = II (In)) = II (xw))
VEL
vES(a)
and
(x) do (x) Edd (X).
Remark A.8. We remark that da (z) is function with variables (()))
The fact that 6o, Φ1, ... - forms basis implies that:
16

---

Fact A.9. Every function f 11 + R can be expressed uniquely in the form
f(z)=
Σ
co)o(r).
(11)
a:S(o)CU
Remark A.10. With the above representation, the Efron-Stein degree of function f equals to the largest magnitude of |a| among those such that Ca O.
Definition A.11. Given tree T and q q ergodic transition matrix M, let (de)sela-11 be the functions described in Lemma A.5 For collection of subsets A M00,, let
F(A) = for E 10,q-11 -(()) E
(12)
For any a E F(A) with |o| 1, lei
(o(r)= = II (r)()),
(13)
iEI())
where, for each I(o), Po is the restriction of to S(o);:
(P:o)(v) o(v)1(v S(o)))
B The overall inductive argument
Here we present the version of the theorem with additional assumption on the transition matrix M that
CM
min Mij 0. [
(14)
Theorem B.1. Given the rooted tree T and the transition matrix M described in Theorem 1.6 and under the additional assumption that cM = min Mij > O, there exists c > O dependent on and dx2 (and implicitly on eM as well) so that the following holds: For any function J of the leaves with fractal capacity S "oogaayy
(a [x,) & (max(d)2,A)) (ar//N)(((())))
We will first derive the version mentioned above, as it substantially reduces the technical complexity without compromising the structural integrity of the proof in the general setting where cM might be
The proof of Theorem 1.6 will be carried out by induction Ac-polynomials. Let us introduce the necessary notations to outline this induction process.
Definition B.2. Let be the constant such that
max max(dx? A} = exp(-
The constant is introduced to improve the readability of the paper. Intuitively, aim to define ax² = exp( but we relax this definition slightly so that incqualities like the following hold when L is sufficiently large:
(d2)( S exp(-el).
Assumption B.3, We say that satisfies assumption B.3 with parameters (h²,,") where 1 and 0 < < < if
A CAC 20)
is closed under decomposition, and morever,
For any v E with h(v) 2 ht and Ago f.
Var [LE (I..) s exp - =(h(o) Var (fx)].
(15)
17

---

2. For any E T {p) with h(v) 2 h and Ag polynomial with Ef(X) = 0,
1 E [e (16)
[E S EI [(( Xp()) =0 S
c*
for all e [g].
The inequality ( bears a resemblance to the inequality we aim to prove in Theorem
B. The
second inequality, (16), will later be
crucial step proving the inductive phase of our proof. Indeed, in the case where Cm > 0, the condition (16) can be easily satisfied by appropriately choosing c"
Lemma B.4, For any given A1 S A S 200 which is closed under decomposition. If satisfies (15) with given parameter h" and CM >> O, then A satisfies Assumption B.3 with parameter h" and
min (cM: min; x(j) >0
In other words, can choose e* with dependence either l or A.
Proof. Consider an arbitrary function f with variables (I : u I v) for some v E T\(p). Let g(x) == (z). By the Markov Property (z) is function of ze which in turn implies g(x) = gxx)). Now, for any 0 [4], fix an index jo [q] such that g(io) 2 Ex(X,). Relying on y is non-negative function,
Elg(X,,) p(u) = 0
Σ Mojg(i) 2 Mojog(io) 2 cas Ex()). jE(μ
By unraveling the definition of g. satisfy the first inequality of (66) as long as c* < CM- The proof for the second incquality follows a similar logic, using the condition c* miny x()) and the trival inequality max.j Mij- < 1.
Given this notation, the proof Theorem B.1 proceeds by induction, with the base case and inductive articulated in the subsequent two statements.
Proposition B.5. Given the rooted tree T and the transition matrix M described in Theorem 1.6 and under the additional assumption that Cm = minn,jely M,j > O. There exists C = CCM, 2 that the following holds:
Fix pl E T and S m S h(p)), if f(x) is a degree 1 polynomials of variables (x., U. (m)))). then
Var [X)x S exp (-E(b(p')
C(log( R) + 1ar))a)((((()
(17)
Theorem B.6. Given the rooted tree T and the transition matrix M described in Theorem I.6 and
under the additional assumption that CM mini,jeigl Mú > O. Suppose A is a collection of subsets satisfying Assumption B.3 with parameters (h", c²). Then, there exists = C(M, d, c*) 2 1 such
that ((A) satisfies Assumption B.3 with parameters (h** + C(log( R + 1), e*).
Let us derive the proof of Theorem B. based on the above two statements.
Proof of Theorem B.7 We apply Proposition B.5 and Lemma B.4 get Ai satisfies Assumption B.3 with parameter h Cha log( RR) + 1), where CiaM = C(M, d) is the constant introduced in the Proposition and
min cas- min, π (j)
Then, by applying Theorem B.6 inductively on the chain As, we can conclude that A satisfies Assumption B.3 with parameter h Cllog R) 1)k: and the same e" described above, provided
that C C(M, d, c²) is the maximum of the constants described in Proposition B.5 and Theorem
B.6 In other words, for any poypoolyllaal f.
Var (Ix,())))( < exp ( a(l - (llg((R) + 1)4)) [arl
The theorem follows by choosing k 2C(Ing(
18

---

C Variance Decomposition and Variance Estimate for degree 1 polynomials
To describe the goal of this section, let begin with the variance decomposition of degree polynomials in a slight generalized form. Essentially, the following statement is a direct consequence of the conditional variance formula. We will state the main results first and provide the proof later in this section.
Lemma C.1. Fix p' T and 0 S k S h(p'), consider function g 14] T. of the form
g(x)
Σ
Go(x)) where (x = Io (x
"EDA(P)
For w E TPMe with h(w) 2 k + 1, ler
[w(x) = E (o(x).
vED2(w)
Then,
Varlg(X)] =Var (Bp +
E
EVar (Ew)))())))(x))) Xp(w)]
wET, Me Mo'Hhhw)2
EVar [go X
VE (AD)
Our goal is to show that when dX3 1, Varlg(X)] is of the same order as ΣVEDAGO Varlge (X)], based on the above lemma.
Lemma C.2. Suppose the transition matrix M satisfies dA2 < 1 and the tree T has growth factor R. Then, there exists constant C C(M,)) 2 1 so that the following holds. Let d' E := and k E 1"). Consider function of the form g(x) "nEDioo' 90 (zo). Then,
1== h(p'),
Varlg(X)] S CR
Varlg
(18)
vEDa(P")
The opposite bound does not depend on dx2 < However, the proof in the general case where = O is not Braight-forward, We state it in full generality but will defer the general proof and prove here in the simpler case where cas >
Proposition C.3. There exists constant C = C(M, 2 1 so that the following holds. Let pl E T, and l [0, h(p')), For any degree-1 function g with variables (x,
Dx(p')). There exists
functions (x) = (x(x))for u E Dx(p') so that the following holds:
1. 9(X) EveDuio') (x)) almost surely. (They may not agree functions from [q]" T to IR.)
2. For any E Tp with h(u)) 2 k.
Σ
Varlg.(X.))) & CR&Var (E)
Var
Σ
9o(X.)]
(19)
(e)
In particular, taking pl we have
Varlg.(X.)] S Carlgg)(
(20)
DEDx(R)
We postpone the proof of Proposition in full generality in Appendix [ due to the technical complexity of the proof and the fact that the proof is about properties of Markov Chain. Instead, statement of the proposition and its proof in the case where cM > 0 is provided in this section.
Now, the purpose of this section is twofold.
First, the derivation of the variance related estimates: Lemma Proposition C.3 with the additional assumption that cm > 0. Additionally, we summarise
Lemma C and
the estimates into a single statements, as stated in Lemma C.7
Second, it is the derivation of the base case of the induction, Proposition B.5
19

---

C.1
Variance Decomposition and Estimates
Before we proceed the proof of Lemma C.1 lemma.
let us remark on the following consequence of the
Remark C.4. For any described in Lemma C.1
we define h(x) := (Exg)(x) =
EvEDatory (Zv)))) and hx())) = (Zu), then by applying the lemma to both g and h, conclude that
Varlg(X)] = (x] +
EVar (x)) [.]].
"EDe(p")
Proof of Lemma
C.7
First, for ETMMO with h(v) 2 k
5o(x) gn( - (X).
Notice the following holds:
((x) = g(x) -g(()== = E (x)
vEDa(0")
Let us start decomposing the variance of g.
Varlg(X)] Varlğ(X)]
Σ
E (X)
(X)
Σ
Σ
B[āo gg.
(X)] + Σ
[[O((X))
(e oft))))))=))))) p(w,)))=
vEDa(D")
By the Markov Property and rearrangement of the terms, for each w E Tp with h(w) > k.
E
E (X)((X)) (X)]
Da
Σ
E (() (X)]
Σ
Σ
(()) (X)]
v,v'EDe(w) ple,)))<w
-IE (Lro
Σ
E )(
Hence,
Varl
Σ
(E(
- Σ [(BB + Σ vEDa(o))
E [X)(
wET, (
w w'Ec(w)
Σ
(((
((m) + Σ E[(((X)
wET, (()))
w' sh(w))))
vEDr(P)
= E (B +
Σ
E (EEw@w ) ((x) - (Ep(w) 3xx (xx)]
wET, Morr))
+ Σ
[[ - E (L. + (E. ( - ( P(x))
vED
=B[ ((())
Σ
EVar [ (Xx ( Xp(w)]++
Σ
EVar (x) X.)
WET, MoT
vEDa(o")
20

---

Next, let us show the proof of Lemma C.2
Proof of Lemma C.2 Let Co Co(M, d) denote the constant introduced in the statement of the Lemma. Its precise value will be determined along the proof. Without lose of generality, we may assume both (x((X) = 0 and (X,) 0 for E Da()"), and the variance of each function is simply its the second moment. For brevity, let Tu = (B(gu (E))x(x)))) for u Da(p') and == h(p').
By 8 from Lemma A.5 for s E I1' - kc.
E (w) (Xp(()) - A..
2. X
20
(21)
where
45 the constant introduced in the Lemma. In particular, if p(u, u/) = p*()) for
u, u' E D& (p')) then
Bgg (X) )gw (X)
= TE P. (w) (x
<( (w) ( (Xp=( 1/2 (B((Epra)))))) (Xpre))))
24 20 Tu.
Then,
E(g(X))² < Σ
(X))
v,w'EDe(o")
Σ
Σ
Ca
25 Tais
sE('' -X] DEDe+a (e') u.M!
where the sum E En. taken over all ordered pairs (u, u') with u, u' Dz(u) with p(u, w') v. By relaxing the constraint of the summation we have
E(g(X)) <
Σ
Σ
A.1
2q 20
Tu Tu²
sE(r
Dic (or) (D(()
Σ
Σ
A
24 26
Tu
sEiV -kj b] DEDe+a(p")
DEDa
Σ
Σ
24 2 Rd
Σ
2
AF
sEllr k] DKI x00))
WE (E)
Σ
24 28
Rd
A.5
Tu
sE(
DEDx(p')
Next,
20 x Rd
RC A.
29
exp((111es)) = CoR.
Hence, Co depends E, 9, and C 2.3 is constant which is determined by M and
Let us formulate Proposition under the additional assumption that cı min Mij > Indeed, in this case, the bound does not depend on R.
Proposition C.S. Suppose the transition matrix M satisfies Cas > 0. There exists a constant C C(M, E) 1 so that the following holds: Let p' T. == h(p'), and k E [0,1], For any function = [q] + R of the form
g(x) = Σ (o()))
vEDu(o")
21

---

The following holds: For any E Tor with h(u) 2 k,
Σ
Varlge(X.)] S CVar
Σ
[o(X.)]
(22)
(ED
(EDa(")
In particular, taking u = p' we have
Σ
Varlg.(X.)] S CVarlg(X)]-
(23)
(e
The proof of the Proposition relies the following immediate consequence of cM >> 0:
Lemma C.6. Suppose M is a x q ergodic transition matrix with сM ming,je(o) Mi 0. There
exists C = C(M) 2 so that the following holds. For any E Mpp and a function h(z) = h(Tu),
1 [Var[h(X..) Xp(ui] 2 C(M) Var[h(X.)].
Proof. Let 0, = argmingeig (0) and 02 = argmax 1())). (In the case of tie, we may choose any of the minimizers or maximizers.) First, we have
Varlh(X.)] (h(02) h(02))2
Next, for any 3 E [4], we have
max [[[ Xp(w) = B] ((11),, [[() X Xp(x) = = - -1(0))) > 2 [h(02) - ((01))
Let i E 21,2} be the index such that [[(((x,) X xp(x) 3] h(0e)) > } (b()2) h(0 }1, and we
will use this together with сы > 0 to give lower bound on the conditional variance:
Xp(w) = |] 2 (..) Xp(w) = 3] - h(0.)) = 0, Xp(w)) = B}} Varlh(Xx) (
(h(02) h((11)) cMs-
4
Since it holds for every B E (q). we conclude that
1 (1((2)) - h(01))² 2 CM Var[h(X.))]
EVar(I(X..) x(w)]
Proof of Proposition C.5 We adapt the notation from Lemma C.I
For w S p' with h(w) > kt let
far (xr
Σ (x).
(w)
Now, we apply Lemma C. and Lemma C.6 get
Varig(X)] = Var [1 gor)
Σ
EVar [wwgg (X..) Xp(w)]
WET, MoT
EVar (xor) x.)
(eD
Σ
EVar (Engn) Xp(w)]
NEDx(P)
Varlga(X.,
DE (P('')
where we used the fact that all the terms are non-negative, the first inequality is obtained by looking at the second terms for the summands with h(w) k and Goz is the -ddependent constant introduced
in Lemma C.6
22

---

Lemma C.7. Suppose dx2 < 1 and the growth factor is at most R. There exists a constant C= C(M d) 2 1 so that the following holds. Fix p' ' and 0 I m S h(p'), if fm (z) is functio in the form
[m(x)
E fo(rg)).
vEDm(l))
with
Bf (X)= =0
Then, there exists fo(gg)) for E (p') such that their sun fm(x) (o) Fulago) satisfies
(x(X) = (m(X) almost surely,
and for of with h(u)= 2 m
E BP(()) SE (m)
Σ F(X))² vEDm(())
CCR E E vEDm(u)
(24)
CR
The statement of the lemma using fm and fo covers also the case CM = O. We will prove the Lemma by using either Proposition C.3 or Proposition C.5 with the assumption cı > O. In the later case, suffice to simply take (z (=gg))
Remark C.8. Note that the lemma implies the following: For any S p' with h(u) 2 m, let
fm,a(x) = Σ
fo(z).
(25)
vEDm (3)
Then, for any given m S k <
W & h(pp) and E (p'(p'), we have
E Efm (X) S CR
Σ EX) CR Σ Σ
Σ
(X),
vEDm(u)
mEDx(u) vEDm(w)
wEDx(w)
where the first inequality follows from the second inequality of 24 and the second inequality follows from the first inequality of 24
Proof of Lemma C.7
Let
hxx) = (Bm)))(t==
Σ (E...)(IN).
vEDin(p')
Note that degree one function of the variables (x, E (p))))). Thus, we could apply Proposition C.3 to show the existence of 1-variable functions (x for E Dm such that
A(X) = Σ
(x()
almost surely
(26)
vEDm(p')
and for any T(p)) with h(u)) m,
Σ
(arlh((x)) < CoaR Var
Σ
ho()))]
(27)
De veDm.tu
Ve DEDm
where [oR]
is the constant introduced in Proposition C.3
Since Eh(X) B(EEm (X) 0, may also assume that
(,) = 0
for (m))'), constant shift of the functions will not affect (26) and 27 following functions: For u E Dm(p') let
Now, consider the
fx(go)) - (,,
and
Fm(x)=
Σ fo(x).
ve
23

---

First, since f((gge) is defined as the sum of three terms with mean 0, we have (X 0.
Second,
Fm(()== E
(Erfo) ((xfx))-(E ho(Xo))
NEDm(PP)
=mm( - 1(()+ +
Σ
ho()v)
vEDm(o')
a.s. (X)).
By Remark C.4
Varl Σ [x(X)] =aar (Em Σ
[x)(
Σ
EVar(f((X) X.)
(w)
(EDm(u)
DED (u)
-aar E (E))
+
Σ
EVar[fo - (Ex.)) + ho (X.) Xx,]
vEDm(u)
vEDm(u)
Var
Σ [x)(
+
Σ [Var[L(()) X
(28)
(w)
(ED
To estimate the lower bound, we rely on own choice of h By have
28
Var(ho(X)
Σ
EVar X,)
vEDm(u) (w)
(M))
Σ
[Var|Mo(X]] + EVar ( X.I)
VE Dm(((
(w)
(X)]
DE. (w)
As for the upper bound, we can apply Lemma C.2
and repeat the same derivation as above get
28
182
Var (ar[h,())]
Σ
[X)
WE (M.(())))
(E))(a))
R
Σ
Var[Fx(X)]-
WE (..(()))
Therefore, by taking the constant C stated in the lemma be the maximum of Chaaa and ( the
proof follows.
C.2 Proof of the base Case of Proposition B.5
We now prove the base case of Proposition B.5
Lemma C.9. There exists constant C' = C(M, d) 2 1 so that the following holds. For any degree 1 function f with variables (xa u E Dx(p')) for some ş with k S h(p'),
Var [[( X=]] s CRA (arr))))))
Var(f
(29)
where h' = -h(p')- k.
Proof. Let fu for De(p') be the functions from Proposition C.3 that
f(x)= = Σ
fx(X.) almost surely.
(30)
wEDi(P')
24

---

We can assume Ef(X) = 0 and (X) = 0 for every u E Da(p') without affecting (30). From
Proposition
C.3 we have
[[f(( < C
wEDa(p)
where C Co denotes the constant C introduced in the Proposition.
We could apply Lemma A.5 to get
[(Ep fo) (Xp))
(PM)))
22 2
Σ
[[f(( S Co34A3 (h') (d)))
B(
DED
where AA denotes the constant C stated in the Lemma.
Proof of the Base Case Proposition B.5
Given pf T and 0 m m h(p'') described the Proposi-
tion. Let h h(p') m. By Lemma C.9 any function f(x) EoEDDm()) fx(2) satisfies
(Er (X)]
(M)) Var(S(X)),
where C Crm denotes the M ddependent constant introduced in the Lemma. With
g (d')") Caa (h')*
exp ( (- t-e(h' C1 Clog((R) + 1))),
for some C₁ 2 which depends on M, d.
D Decomposition of Polynomials
In this section study the representation of functions in terms of d and th Roughly speaking tho are "more orthogonal" than the dg. More formally we will show that under appropriate conditioning expections of vi, factorize. Thus some of the effort in the proof and particularly in this section is devoted to relating the & and v representations and bounding moments of such representations.
and growth factor of R. there exists C C'M, d) so that the following holds. Let A S B C (0) be collection of subsets which is closed under decomposition. a positive integer kn and p' T with 1' == h(pp)) > ky. For every function f of the form
Lemma D.1. Assuming dx2
f(x)
Σ
(x)
with
Ef(X)= =0,
here exists decomposition of
S(X)
Σ
fa(X) almost surely,
uSS =h())2
where, for each u S pf with h(u) 2 k1, we have a function fa(x) = fu fu( and
1. For u E Tp with h(u)) > K1, fu (x) is a linear combination of vo (x) with a E F(B.)) and
fx(xx) fa(z) Ef,
2. For < pl with h(w) 2 k1 we have
Σ
((() S Σ
Ia(x))
< CRR.
Σ
[(x))
(31)
CR
WE DED (w)
DEDi (w)
DED (mc)
25

---

We may group the fu according to h(u) and define for 1ı S S h(p),,
fx(x) = Σ fu(r).
DEDN(p))
In other words.
f(x)
E
(x) almost surely.
To prove the main lemma, let us begin by comparing do (x) and to (ar) (See Definition A.11 Lemma D.2. For a E F(B.). @o (2)) can be expressed the form
Φ (x)
II iET(a)
(p)((x) - (c,o(x) - ac (2) Oc,os
(32)
where:
(c)o is linear combination of (x) for df E F(Bu) such that I(o') is proper subset of [()).
(x) is a linear combination of oo (z) for o' E F(Beu) (recall that Ben {5 E B p(S) u)), and
Oc.ar is a constant.
Proof. Fix E F(B) and let u = p(S) and = S(r). Recall that Pio 10"" is the projection of a to S. We can also decompose the function 0, according to (P,o)e
(x(x)
II (p) kET(S)
(33)
Before we proceed, let us note that by Lemma 1.12 and the definition of B, we have P.o F(B Now, let expand the function t/o according to its definition:
II (x) iET(S)
II (or - (x)r(()) #EI(S)
CII
Epr Exr: (I{)Errr))))
11.12
iEh
ieL2
where the summation is taken over all possible partition L la (()). Next, can group the summands into four types based on [[]] and [Z2]
Type 1 = [[()) The summand is simply (x).
Type 2 2 < |4 S [[(6)|-1
Each summand is constant multiple of dor (x) where a' is the projection of to the indices Lier, S, Clearly, S(o') Lier, S.. With [Tl 2 2, we have p(a') = u. Further, each S. E Asu, for E [oo), follows that S(a') B., which in turn implies a' E F(B.).
We denote the sum of summands of this type by (r))
Type 3
1 = 1. Each summand is a constant multiple of &r.a (z), where i is the element in //- Notice that Pi E F(Acu) F(Bc.) where the inclusion follows from Lemma 1.12 We denote the sum of summands of this type as (z).
Type 4 |1| = 0 There is only one summand, which is constant. We denote this constant by Oa,
With this decomposition,
32
follows.
Given the expressions for v/r (x)) terms dh (x) and vice-versa, for any given u E T T., we can convert linear combination of d (z) with F(B.) to that of th (x) with E F(B.).
26

---

Lemma D.3. For u E L, consider any any function of the form
Pu(x)= = Σ
codo (T).
DEF((B.)
Then there exists decomposition
Pa(x)= =f((x) + (2) + Cu.
where:
Fu(x) = - - and fu(z) is a linear combination of th (x) for E F(B,).
(c,,(()) a linear combination of &a (x) with a FBB and
Cu is constant.
Proof. The decomposition constructed through recursion on the following expression:
r(pa) == (1( E F(.), co + 0}.
Suppose r(p.) = 2. Then the statement of simply follows from Lemma D.2
Suppose the statement of the lemma holds whenever r(pw) for 2 < Rd. Consider any function Pu. with r(p.) =r r 1:
Pa (a(x)
(T) OEF(B.):)NO))sH
Σ
E
(x)
Σ
Co Oo)
(()
rEF(B.) ([ Sr
()rr+((())
Px)
According to the decomposition of do (x) in Lemma D.2 let
fur+i(z)
OEF(B.. [0))=++11 (2)((x))
Σ
Peurrt(()) =
Σ
(1))
where be C, Then,
(2) (2) + Pc,ur+1())) (&,,,r-1()) Pe,ur+1(2).
(34)
N Observe that Pu, Sr (x) + Pc,u,r+1 (r) is a linear combination of do (z) with o E F(B.) and [(a)] r. Thus, by the inductive assumption, the summation can be expressed in the form
Pa,s((x) + Pc..r+i(z) = Fx(x) + P'c, (z) + cn.
Finally, let
fa(z) =f (2) + fu)) (x,a(z) = u (I) + P (x)))
Cu = P'a E [(fur+i(X))
and we have
px(x) =furti (2:) Pe,,urt(z)) + (our)t1() + (x) (l) + da
=f)(x) (P) + Cu.
27

---

Proof of Lemma D.1 We will construct (x) for u starting from top layer (u = p') to bottom layer.
For [K,, 1], when (x) is constructed for E Tp with h(u) k; we define
fzx(z) = f(x)=
Σ fx(x).
(35)
where fu(x) = fa( (X). Without lose of generality, let fgr (x) = f(x).
Fix le E [kg + 1,17 For the induction step, suppose {Su (f(()) Ab())S (fso()) have been constructed such that (x) can be expressed in the form
=cd
E
(2)
E
(z)
(36)
rEF(B):
Clearly, this holds when kt = l'.
For each u with h(u) = ki let (T( = EOEF(B.) (oo(1)) and define Pe, and cu
according to Lemma D.3 Then,
Σ fa(a)
u: hh
=d'
Σ
(00(x) +
Σ
(x)
oEF(B) 1k th sho (p<,a()) + cw).
oEF(2') MMPl))sh
u:: u=:(()=k
Recall from Lemma D.3 that P<,a (x) is linear combination of @o (x with F(Beu), the function fgk-1(2) (x) satishes (36) as well (with & been replaced by k - 1).
Once the induction terminated layer K1, obtain
(x)=
Σ
Σ
Co 8o (z).
DEDe, (e)) (EF(2L-((0))
Now, observe that for hn < k S h(p)), we have fa( is defined as the sum of fo for E Da(D'), which are functions of mean 0. Together with the assumption that E.f(X) we have
h(pp)
Efa, (X) = BS(x)
Σ Bfa(X) 0.
k=
Notice that fk, satisfies the assumption of the function stated in Lemma C.7 with k1- By replacing fo. by fr, and fu by fa for each u E DR, (p'), the second statement follows while the third statement of the Lemma remains true. Hence, the proof is completed.
E Induction Step 1: Decay of fa
The goal this section and next section to prove Theorem B.6 Let us restate the theorem here.
Theorem. Given the rooted tree T and the transition matrix M described Theorem L.6 and under the additional assumption that CM = min;,jelg) Mi > O. Suppose A is collection of subsets satisfying Assumption B.3 with parameters h" and c². Then, there exists C = C(M, d,c") )²== 2 such
that B(AA satisfie Assumption B.3 with parameters h + C(log( (R) + 1) and
In this and the following section, we will fix a collection A that meets Assumption parameters and c* Additionally, we abbreviate
B.3 with some
B= B(A).
28

---

Further, we will fix p' T and function f described in the Assumption B.3 and assume
[f( 0.
The proof grounded in the decomposition of f as described in Lemma D.1 which splits into summation of S& and subsequently into summations of fu. Accordingly, this section is devoted to derive the variance decay properties of fa stated as Proposition [.. below. The proposition will be used to derive variance decay properties of Sk. and toward the proof of Theorem [.6]in next section.
Proposition E.1. There exists C C(M, 1 so that the following holds. For any T, consider a function Ju of the form
fa(x)
Σ
(x).
0f0EF((B.)
Then, for O E [q], have the following bounds on (Eu (recall that that by the Markov
Property (B)fu)(z) is a function of xw):
(Eu.u)) S exp(-2x - C(log(R) + -1 1t))),BB331
(37)
and
(E exp((2e<bbu)) C(log( + -
(38)
Additionally, for any function a(x) having inputs involving only (x. Tu,) for some i [d.]]
([Ix(())a(X)1 < exp (h(u) - C(log( + -1) br)) (11n))))BBBB
1)
(39)
Remark E.2. The statement of the Proposition E.1 is exactly the statement of Theorem B. restricted to functions all of whose non-zero e, have p(o) = p'. Thus in some sense in this section we prove the Theorem for the most complex terms. And in the next section we will control the correlations between different terms.
This is an analogue in our setting to the classical fact in Fourier analysis that high amplitude functions have sharp decay under noise.
Remark F.3. We remark that the proposition holds immediately whenever |dwl S 1, since B,
Before we proceed further, we need to decompose fu(z).
Definition E.4. For u E L and fu(s) = EOEF(B.) Ca (x),
(z) = E
(oda(I), and
(40)
((F
: (X,,
(41)
for each I [dhu] with |7| 2.
Given the above definition, we have
fu(x) =
Σ
fu.((x).
Proposition E.S. There exists = C(M,c') that the following holds. For any u T L and I C [du] with [7] 2 2. Consider a function of the form
a(x)
Σ
Co Gorboo (x).
oEF(B.):(0)=1
Then, for I' I, let
U U= U=T\(U) Tw.), JET'
and we have
((Br))(z))² exp (- C (Bra)))))
(42)
29

---

Roughly speaking the proposition states that under the decay of correlation in Assumption B33 for functions all of whose coefficient Cr have S(o) for some large set we get variance decay of the form exp(-<//|h(e on some of the subtrees. This an analogue our setting to the classical fact in Fourier analysis that high amplitude functions have sharp decay under noise.
For later applications the statement is more general allowing to condition
Proof. We fix u E L and I S [d..] Without lose of generality, assume I' = [s].
Let Co (M, c*) denote the constant described the statement of the Proposition. The precise value of Co will be determined during the proof.
For brevity, we introduce some notations that only used in this proof.
1. Decomposition of x E : Consider the representation of
(Iis 30, #1 ;1:-..,
where, Ak E [s]. = (xo ux), and Ty (xv, :0 u U {u)).
Further, let
Igk (xo, ;1,...;2kk)
For h E [0,
(xg)) = E [a(x) X, = zu and X Zggk
Before we proceed to the proof, observe that applying Jenson's inequality on conditional expectation, we can form a chain of inequalities
(Eva)² (xx (Z))gg)(z) s (Eva))) I (Evogz) S ... (Evoz,) (Egaa)
h(u) < Co + h", then the statement of the Proposition is weaker than the inequality aB s (EEgaa) (1r) stated above. So the lemma follows immediately in that case. From now on we assume
huu)
Co + h
(43)
We will improve each inequality in the above chain by leveraging the assumption 15 Given the definition of a(x).
a(x)
Σ Co II
(F0) II (x;
6E(e]
By the Markov Property the random variables (X, Iu]ie|ooal are independent. This gives rise to:
(c)(x) =E
C
II eP. (Xo)
II T (X,) Xu = xu and X Izsk
(EN(
vE(a]
II iE\\[
Tr. (vo) II
II (Eagro))zu) se[k+1,s]
vE(A]
This part is freezed.
This part is function of zu.
Now, fix [s] and express aga(x= TT Tx). An essence of this proof is that the mapping:
yk + ac -5k-
a linear combination of 6o (3)) with a E F(Au,) and the coefficients are functions of (Nuy Iggk-1); which gives us room to apply the inductive assumption, or [15) from Assumption B.3
30

---

To aid our analysis, we introduce Ys. an independent copy of X3. By 11 we have
(E) -ea Y,)) S
- Br) [ (Ta Yo)].
(44)
The reason introduce Y& is that the I.H..S. and R.H.S. of the above inequality related to (any moments of) conditional expectation of a ()) However, can still be used with some adjustment, relying on (16) from Assumption B.3
Given the assumption on Co being greater than or equal to 1, we have
43
h(ux)) huuu)
h" + Co h²
Applying (16 to our function yı: + agk (Zur 11 21 get
Eyi (azg I5 Yn)]
min Evi (ea Yu O]
nE(n)
Ey, [a (Cu Y = zu].
(45)
c
On the other hand,
(xx)) (asu T 13t = =x,))² < (B
Combining the above expression, and (45). we conclude that
(B Y. = =xu])² (Ix)
exp(-e(h(x) Br) (Tu, Yx. Yu = xa].
(46)
Notice that the expression inside the square in I.H.S. is
E Elagn(an Tgk-1 Yx) Yu In]
=[aca((fa Xx) X zn]
=E aga X X. Fus Pu, xgk-1
-ach-1 (x).
Similarly,
Ey (2,, Ys) Yu xx]]
=13 [a (Iur xx) Xx xn]
=E a (X,, X Xx),, Xv
zu, X = ICC-1
=a (x).
By imposing the first assumption on Co that
Cu N log c minnelly )
it follows from 46 that
( (x) < exp(-e(h(w) C. (r))) X,, Fu and X xs
By taking Conditional Expectation on both sides.
(Brr S exp(-e(h(u) - Co - hh) (Bv
Finally, we apply this incquality consecutively for e [s] we obtain
(E)a)?(x) S (xp(==(['((b(u) Co - h (E)a)()))
31

---

Corollary E.6. Fix u E T and a function fu(x) following the form described in Definition E.4 If I,J S [du] are subsets of [d,] of size least then for every 8 E [g].
(BBr,,,))0)) Sexp (- -
$/1 (h(u) - C -hh1) (EE,,,,2)0
(47)
(oxpp--110 (- (h(u) - C - -hh))) (Euf,,))O) V (B,fi,)))), (48)
(Eufus : f()))(0)) S <cxp
2
where C = CCM,cc) c") is the constant introduced in Proposition E.5 and TAJ == (1 (T)J)
Proof. For the first statement, it follows from Proposition E.5 with ==z)= = (2) and I= I.
To prove the second statement, begin by noting that the inputs of fu.r(x)) and fu,)(x) do not UsenyJ Tu.), respectively. Thus, we can apply the Markov Property and that fact that if Y, Z, W are ind pendent then:
include (I. Usery Tu,) and (2e
E[g(Y, (),(Z, W)] (Y, Z), W) 2]] OY, W)]
and this in turn becomes:
E|
W]).
to obtain
(Bufu, fu,
=E E (x,
X U &
U Tu.]
E (X)
Xo: & U To: iEJU
X 2x x
In terms of absolute value, by Proposition
E.5 we have
sn,)(())))
<B
E fu. (X) (X)ff
X. u0 U Te,
X, xo : x u
iESAJ
E
E (X)
X, :u:ud
U Tu.
E (X)
X : u U Tu,
X. = xo : x
NEN
iEJi1
SE
(xpp-=///11((x)-CCC--- E ((,)())
X. Uo: U Tu
iET
-xpp-=
- - h²)) B (x) X : u $ U Tw
E
X, =x :
iEJi
<exp -
C -C
E
E (x) Xx:
U Tu.
X,= x. 1 8
NENW
E
E (2), X, ou &
U Ty
X, xu : 1 xx
NEJY
=exp (
-C (--IA)(tt)-C-- (EWWL,))) (E,),,)()),
where the second to last inequality follows from Hölder's inequality.
Corollary E.7. There exists C = C(M, d, c*) 2 so that the following holds. If T T L with
h(u)) 2 hi + +C(1 + log( R)), then for any fx(x) in the form described in Definition E.4
vo E lal. 2
Σ
(E. < (B).
(49)
Ic(2)):1122
32

---

Proof. Let C. Co(M, d. c*) denote the constant introduced in the statement of the Lemma. Its value will be determined along the proof.
The statement of the Corollary trivial when du < 2 since in that case B,, = 0, implying fu = O. From now on, assume d, 2.
First,
(E)
E (En = h 2Euufu, (x)
re[a_]: 11/22
(1.3)
where Enr,, refers to the sum over unordered pairs (T,J} with and J being distinct subsets of [dw]] of size at least 2.
We can apply (48) to estimate the absolute value of the difference.
Σ
2(Enfu, fx)
(1,3)
(- ||
$ Σ 2exp
(h(u) BB5
h h+)) V (En.).))())) / (Bn....)))x)
(50)
2
where the constant a, R,
E35 the constant
C
F.5 introduced in Proposition E.5
By 2/ab
a² + 12 for
2 (Bu (Bn2,.))(z)
/ (Bufl.))
s (Bufa,)) + (E (E. (Euf,.))
Hence,
exp (- EV/AJ (h(u)
50
Σ (Enlu,)(s)
Σ
1ond h
2
|c|d.]:11122
JC(d.):14J
With || S [dw]
|/JJ|
=i} 13|==
(du) di
exp
(h(u)
B h
exp
Ei (h(u)
F55 hr))
s 1/4.
2
2
JC
i=
(51)
provided that huu)
E.
log (du) h" 2 16
Now, we impose the first assumption on Co that
(gg())
16
Cp 2
+
+
then
log(dw)
h(w)) 2 h" + Co(log(R) +1) 2 E.
+ + hh
Hence,
(E.. (2))
(En
S
1
Σ
(52)
/E|4]
and the proof follows.
Proof of Proposition E. Let Co = Co(M, d, c") denote the constant introduced in the statement of the Proposition. Its precise value will be determined along the proof. From Remark F..3 it is sufficient to consider the case when [d,] 2 Further, suffices to prove the case when
h(u) 2 h" + Clog R)) + 1),
(53)
33

---

since otherwise the statements follow from either Cauchy-Schwarc or Jenson's 's inequality.
Part I: Derivation of 37 and
38
First, by 47
(Bufa) = Σ
(B)J
(54)
1gld.]:1/222
Σ
=|11 (h(u)
1r²) .
2
exp
19/2.):11222
Σ 12
exp
BB
h
Σ
(E.l.))))
where applied Bauchy-Schward inequality in the last inequality; the constant C' introduced Proposition
E.5 the constant
E.3
With the coarse estimate
| S [ull : | = -11= = (ds) S di S (Rd)',
we have
Σ exp (-el7](h(uu)
PM h))))
ICId.):1112
06
log (lt) + log(d) - 11') 11+)
Σ
exp
- (((w)
Lead
(55)
&
The geometric series above is finite if (u) is large enough, and this can be achieved by imposing assumption of Co and relying on (53). Now, let impose the first assumption on Co:
Co
E5
(2 + 2log(d) + 100)/E.
(56)
Then, by 533 we have
log( R) log(d)
100
h(u) 2 h1
Co (Rog(R)) + 1)
h" + 695
E
which in term implies the R.H.S. of 55 is
exp
2e
hhu))
log RR) Hog
h1²))
exp
(h(u)
log( R) log())+log(d)
11*
cxp
25
h((u)
2B
log R) +log(d))
h1")
<
100
exp
25 (h(u)
log( RR) + llogdd)
-h-) 11²)
1
log( R) + -log(d)
log 88 2z
exp
- 2a (h(u)
25
h"
< 7 exp
- (h(u)) - Coogo (?) + +1)-h")
Substituting the above estimate into (54). together with (49 we have
(En.fu)?( < exp 2: (b())) Co R) + 1) -n))
Σ
(E))
ICldwli4 22
2 exp ( (- (h2x(h(u) - Coog R) + 1) h²)) (B.)
(57)
34

---

Therefore, we have derived an inequality which is slightly stronger than (37
To derive 38 let us first show B ) is relatively small using 57 and Jesnon's is inequality:
1
(E[f((X))) S (E.J & exp (- (-2 2b(w)( Co(log R) + 1) - hh) E (x)
Thus, the variance and the second moment of (X) are the same up to a factor of 2:
E [x][())] ([(x)]=[[A[(])) [[][(()() - (EII(()))) ([X())))E(LL(()))) [[()(
(58)
We conclude that
TE [T( (Rn,f.x))
2 exp ( (~2e(h(u) Co R) + +1 1 [[]a(x]]
exp
$ eexp(-2E(( -2e(huu) Co(1 + log(R)) h-" ) 1n)) [X]]]
Therefore, complete the proof of (38).
Part II: Derivation of 39..
remains to show
(39 and the proof is similar. Fix I C [du] with ||| 2 2, let I' = [if and we
represent x E 44] T (To, 11), where
To = (xo E UT,,)
and
x ==x= UE T.,). jer
jer
With this notation, we have a(x) a (xro). Thus,
E (X)xxx(
E Fu,, (X) Xo) a(Xo))] =E
E (LL (u. x /BB 1 (Xo))
3
R. [R.. (X) xx))²]
VR[a2(X0) (Xo)]
eexp |r (b)((((u)))))))))))))()))))))(
555 h²) E V [x)] [B[]
where the last inequality follows from Proposition E.5
Hence,
(X)(aI)
Σ exp (-g E (7) (i)(((())
h²)) v [[(2, BB(o((X)]
2
1
1/2
Σ
exp ( E/! \ (h)((((u)
h²)) h²))
Σ
[X],,(x)]
1C
Icld.1:11122
(59)
Next, we impose the second assumption on Co that
Co
where Caa is the constant introduced in Corollary E.7
Together our assumption h(u) > h Clogo R) + 1) at the beginning of the proof, we can apply the Corollary and (58) to get
Ef², < (E(f (X)))
(60)
1C
35

---

Repeating the same argument as in the proof of (38
and relying on the assumption (36 of Co.
=e((bh()) (((u) - A.. h" log Rd)
exp(-e\\\((((hh())
h )
exp
(- Et
E
1 S
- (-e(h(() h((u) Co((lo(()) + +1)-11 h1'))))
exp
4
(61)
Therefore, combining (60), 611, and (59) get
B ([)((())(())]] & exp 2
(h(u)
+ -1)) VV[[a(X)] VE[e2(X)]
Induction Step Decay of fk and the proof of Theorem B.6
As continuation of the inductive step, adapt the notation introduced in the previous section. Building on the properties of an single component fu from Proposition E. our objective is to deduce variance and covariance decay of fg. which is stated in Proposition F. below. Once it is established, we will be ready to prove Theorem B.6
F1 Properties of fk
The main goal of this subsection is derive the following Proposition. Proposition F.l. There exists C' C(M, d, c*) 2 1 so that the following holds. For any o' e T satisfying
h(p') 2 h + C(1 + lo)(
Fix a positive integer kę such that
h(p') 2 h + C(1 + log(H))
Consider a ffnctiin
f(x) =c
Σ
co (Z)
(EF(Bgar)
with EE(() O. We decompose f according to Lemma holds:
D.1 with the given ky. Then, the following
for h E [k1 + 1,h((/))
[TE [x) exp (-e(h(p') k C(log(R) +1 1))++120000 2
(62)
for k -hi
)2(xxr]] exp (-e(h(p') - C(log(1)+++ 11)) Bf (X), and (63)
for ki mm < k: 5 h(('),
E (x)) sexp (-g _
((lo((R)) 1))) (1)_()))++++))))))))))) (1)
(64)
36

---

Before we prove the Proposition, let us prove the following second moment bounds for the partial sums of fu-
Lemma F.2. There exists a constant C C(M, d, c²) 2 1 so that the following holds. Consider the same description stated in Proposition F.1 and K1 hh + C(log(R) (R) + 1). Let (h, k) be pair of
integers satisfying 1 < h S k S For u E Dx(p'). let
[n,(())= Σ (z(z). vEDN(w)
In other words,
fx(2)= E fna((x).
MEDa(0)
The following holds: First, for u E Dx(p'),
1 2
Σ (
Σ (X(
(EDr(())
MEDa(M)
Second,
Efr (f) 44
E (X),
LEL'(D")
wELx(P")
Proof. Let Co = Co(M, d')') denote the constant introduced in the statement of the Lemma. Its precise value will be determined along the proof.
Let us fix Dx(p'). Consider the following conditional expectation of fn,u(x).
(Bnsn.)()) = [[fma(X)] X. = h(e) h4]= = Σ
(Zr.))
vEDa(P)
(Ev Comparing the second moments of fn,u(z) = EvEra(u) Fo and (En we get
Σ f((x))
= E
E (x)
+
E
(m)
(E)
Σ (X)
E
E (X),
Xp(m.on]
(E)
(u))) :ngtor
(B) + Σ [x]] [I(RE,,))(x))))
(w)
DEDi(w)
eep (Ee(h-
p + log -
vEDx(u)
(65)
where the last inequality follow from Proposition E.1 and C C is the constant C introduced in Proposition E.
Here we impose the first assumption on Co:
Co > 10 ma
Then, due ki h"* + (ollgg(I)) + 1), have exp(-E(h- C [ 1 ++ log (oog(R)) -))-))))) - exp(-e(ks E (1 (o))())))))h)) s exp(-=-0.9C)) s 1/2,
and thus 65 can be simplified to
E ( 2 Σ [[]((x)
1
(66)
(e)
37

---

With the lower bound been established, the upper bound can also be derived in the same fashion. Let us first recycle the first three lines of (65):
E
Σ F((x)
Σ
(ExA)()))
+ Σ
VEDA(M)
(a("))
VEDa(N)
Σ (B,I))(x))²
+ E
(x)x
TE (E
(EDA(1)
Notice that we can apply Lemma C.2 for the first summand in the above expression.
E Σ (Exlo)x))** = Σ (x.)))
Σ
(B...)((,,)
(EDa(u)
(E)i(.)
vEDa(M)
where Ccra is the constant introduced in Lemma we have
Again, applying the estimate from Proposition
Lomn
Σ
(Ex,)) S
C Topp i exp
(-2 -2=(h
C 1 + log(R)) -1n)
Σ
EX)
vEDa(u)
of vEDi(w)
Here we impose the second assumption on Co that
log(
C 2m
C
(67)
2x
Then, relying on > Aa 2 hi + Co(log Rt) + 1),
Coa R exp
(-26) 2e
+ log (R)) - -h²))
log(
log I7)
S exp
25
log( RR) - -h
2c
11.
which in turn implies
Σ E()(())
(M)
Now it remains to show the second statement. Notice that fn fh.p' immediately have
Σ BB(() (A(() 22 Σ Bス(()
T/
(ED
VE DEDD((P)
Together with
Σ (X) Σ EF(() S2 Σ Ex)((X), (EDx(P)
rEDA(P)
aE nEDR(r")
the second statement of the lemma follows.
Proof of Proposition F.1 Let Co = Co d, ct) denote the constant introduced in the statement of
Lemma. Its precise value will be determined along the proof. Let us make first assumption on Co that
Co
N
where Crem the constant introduced in Lemma Lemma.
Now, we could apply the statements of the
Part 1: Derivation of 62
38

---

Fix k E [k1 + 1,2"] Applying Lemma F.2 with the parameters h and & in the Lemma setting to be k,
E(L(())) 22
E E(f((x))²
(68)
uEDx(P)
The next step is to compare the sum of (X) with (1) By Jenson's 's inequality.
E
Σ
(Bx)))()x))]
(B
)
MEDE(P)
< |DA(O')
Σ (Ep
mEDe(P)
=IDx(p') Σ
MEDa(p)
For each summand, apply 8 from Lemma A.5 to get the following estimate.
[[ ( xx,r) )] Cam 2 [(((....((X..)
where C CA. is the constant introduced the Lemma. Together with Dx(D')) s Rd from the from the definiton of E,
assumption T and dX3 I Rex"pex k))
E
E (EDi(P)
E (()E
exp CC -
E [EE fu) (Xx)] (69)
uEDx(e"
where we set
='=1+ (1 (1+ max 21 exp(-0.1em) < +00. nEN
By Proposition
we have
E (.)...)))))) S exp(-2eE(k CF log(R)) (
(70)
where CA1
is the constant C introduced in the Proposition. Substituting this inequality into (69).
together with (68) from first step,
E [((
S exp (- (( k (C' EXT (log( (R) + +1) 100--21. 2hh)) 11))-2h))
Σ
E()x(X))²
NEDD)(P)
expp(=e(' k (C' + (ral) (log( 1) ((x)))
Now, we impose the second assumption on Co that
Co 2 (C" 6.
we finished the proof of (62)
Part 2: Derivation of 663
Let us consider
he (x) = (LEn fbr (xx = [f (X) X., = x.. :uc u DR, (p')].
In other words, we may view hg, (xr) as linear function with variables T., for u E DR, (p') with Ehe, (X) = ESe, (X) = 0. Then,
E
= [(Eprra, )xxx)) & exp( e(h(p') - 11 - CBs Eh (X)
< exp =(h(p') k
B
Ef2 (X)
39

---

The first inequality follows from Proposition B.5 inequality. Here we impose the third assumption on Cg that
The second inequality follows from Jensen
Co 35
the derivation of 66 follows.
Part 3: Derivation of (64
For w S with S h(w) S let
f (m)
E fo(x).
VED,(w)
Let us make remark that either by second property of f from Lemma D.I when when = ki or by Lemma F.2 in the case when m > hi, we have the following: w S p and m S k S h(w))
Σ (ED
Efm.a
1/2
S
<
R2
E
m (X)) 1/2
(71)
With this notation,
(f
Σ
fm,())
Σ
Efa(X) (X)
We NEDu(m)
E
mfa(())maaX))
+
Σ
E
(Eu (X) (mar (ptenar)
(EDx((")
(. (o)): suaetu
Σ
Σ
+ MEDa(p)
Σ
mma(()
(72)
(PD
(e
B
MEDa(P") We will estimate the three summands individually.
Part 3.1: Estimating first summand of 722 First, we apply Cauchy-Schwarz inequallty..
E Σ
(E)))(())
(E (E.fm, (X))
(e))
NEDu(N)
S (E(((B)))(()) ([B,))X))))((BB
(73)
Now, combining 770 and 68
we have
V [E[((E.F))(()) s v2 exp =E(k: CET log((t) -B))))))))((/((
(74)
By setting
( log(2) log (D.I +2).
G
we can conclude that
R
Σ (Bx()(X)) Σ
(En (Bu.fm.) uEDa(o")
(eD
< <exp(-e(k: (log())) +1) - (1)( -1)))
(75)
Part 3.2: Estimating second summand of (72) For the second summand of (22). we begin with the estimate for each E Dx(p'):
(X), m, (x)l Σ
(l) (X))
sE(d.]
40

---

Since for each i [du] we have fm. (x) = fm, (Irg.)), we apply (3) from Proposition E.1 to fu
and alx) = fm. (x) to get
(m kE(d.)
E exp
- (-2
log R + +1) + ( (X))
xE
where CETIS is the constant introduced in the Proposition. Applying Jensen's inequalyy and 71 with W = u and = k -
1/2 S (Rd) 12 12 (Bfm,.()))
Σ CEE (x)) - 2d 22/2 Ed(
Σ
tE(d.)
Hence,
(l)a(())mmm (X)1 (()))) (
122 exp (- 8 (
CaTT log (R) +
Sexp
- (k: C2(1og( (2) + 1) --1--hh) (,, (76)
8
2
where
3 + log(d) + log Log(Oun)
1
C2 = 8 2 2
Now, returning to the summation, we apply (76) and Cauchy-Schward inequality to get
Σ
mfu(X)mmmxx))
MEDe(P)
Σ exp (- E (k: (-
C2(log(R) + 1) (k=-C2(lo[(R++
(EDx(P)
< Sexp
1-(
E (k- 15--Ch (62(oolog( 1) 11))
Σ
1((()) 1/2
Σ
E Bsm (x))
1/2
WE (ED
(ED
<20 R² exp ( - (- (k- C2(log(R) + 11 (k)
(Bff())) 1/2
1/2
E (k: Cz(log R)) +) 1r')) E (X
S <exp
(-2
(77)
2
, BP((X)) 1/2 and for In the derivation above, applied Lemma F.2 for the term 1/2
the term (EneDwor) Esm (x)) inequality is defined as
in the secont to last inequality. The constant C2 in the last
C
(log( (2 12 (2 + 2) + Cz-
Part 3.3: Estimating third summand of 72) It remains to bound the third summand, it can be
reduced to the upper bound for first summand. Applying the Cauchy-Sehwarr inequality and Hölder's inequality we have
E (X) (ED
Σ
<
((),
aE aEDu(r')
(Bn (Bxf))(X))) 1/2
Σ ( 1/2 u/g
<E
(P))
DEDa(p")
1/2
E Σ (Bulmma)(()) 1/2
E
Σ
(B
NED
(ED)(N")
<v2expl ( -E(kk- [
log( R?)) -h*))
CD.
R2 (X
41

---

where in the last inequality we applied (74) and
By setting
1 ( log(2) + (p.)) +2). Cs =
we conclude that
Σ
(E. sexp (- -- =l: C1(1 + log(R)) hn)) E
(ED
(78)
Now, combining the three estimates of the summands 775 77 and (88) for 72 we conclude that
[X]((X)/m, S expp (k C5 (2) h²)) (X))
where
Cs == log(3) + max Ca, Ca}.
Now we impose the forth assumption on Co that
Co 2 Cs:
and 64 follows.
E22 Proof of Theorem B.6
Let C. = Co (M, dd c²) denote the constant introduced in the statement of the Lemma. Its precise value will be determined along the proof.
Let 1 be a positive integer with the precise value to be determined later. Here we impose our first assumption on kn that
kn GET log R + 1) + h²
where | is a constant that appears in Proposition F.T
Now, 1et us consider function f described in the Theorem. Without lose of generality, we may Then, it is equivalent to estimate the second moments.
assume E (X)
Further, let us assume h(p') 2 kn and the decomposition of f according to Lemma D.1
f(x)
Σ
fx(X).
(79)
k((k),
Our first goal to show
ES(X)²
Σ 1(X),
h(o'))
by showing Effa (X)(()) (X) is insignificant whenever h + m.
For kı S m < k. by Propostion F.I
(X) <2cxp
2 log
R) + 1) h1') (BX
2
eexp
(k:
C
Log R + +1) h²') Ex)(
2
E (At log ()) + 1) - h L En
+ exp
2
Applying the above inequality to bound the second moment f(X) we get
E (x) =E
Σ
(X)(X)
k. (RL
Σ Ef((X) (1-
Σ exp
(-
E -
log R) 1) - -h²))
Tea
2
kElk),ble")
velky,(pp))
42

---

Notice that there exists to which depends on E so that
exp
21 S
By setting
hn = [h* + Tra (lo((R) R)) + 1) + tol,
get
Ef (X) 22
Σ (x)
(80)
kElki b(('),
Our second goal is comparing IE (R, S (x }] and 2o norm comparison from Lemma A.5
and Exe(hs (X) Starting with the variance
(E. (k) ]
(T SE
max G.Elo ke(ki h(('))
max [xE(
(E,r (x)
kc kpp))
Σ
E(E (x))(x))) ?
A.5
ke(k),b(p"))
where (A. is the constant introduced in the Lemma.
By 62 from Proposition for [k1 + h,)()')
E [E fx)) 1 exp E(k h²)) exp ( =(h(p') -Cp log(R) - 1) - h+*) E
And for k k1 = [h*
F log( R)) + 1) + tul, we apply (63 to get
SM. (X S exp ( =(h(p') - ki - AA log (R) + 1))) (X)
exp ( - = -1))
exp - (<e(ppp') 20 E log Rt) + - -1" -)) EE (X).
Substituting these estimate and by Cauchy-Schwarc inequality we have
f)( I CAL
<(h(p')
20a log(()) + 1) - -h1))
exp(e(to + 1)) +
Σ exp( -e))
Σ Ef((x)
t=
kE(K),
c
C CA. 11.512en Cepp ( (<e(h(p') 20 + h²') b²))
Now, by taking
Co max 22 + log Ca. C12), FT + to + +1]
we conclude that
[[(E, sex exp <(h(p') Co(log( (R) +1 -1)))++))))))
It remains to show the case when h(pp)) < kj. From the assumption that Co > to + 1 and
k < hi + RR) + 1) + la + 1, we have
exp - =(h(p') Collog( + 1) hh)) 2 1.
Hence, the statement follows directly from Jensen's 's inequality.
43

---

G
General Case: Base Case
Now, we want to establish Theorem 1.6 which does not rely on the assumption CM > Let us first
establish analogues of Assumption B.3 (the inductive assumption), Proposition B.5 (the base case), and Theorem (the Assumption G.1. By stating that A satisfies this assumption with given parameter h we mean A S A S 2 M00 is closed under decomposition, and the following holds:
(the inductive step) the general case.
For every E T and any Agu-Polynomials functions f and we have
Var (E.))) & exp(-=(h(u) Varl
(81)
Further, suppose 13f Eg and h(u) 2 h. Notice that by the Markov Property (Ir), and (Z) are functions of Ty. Then,
(L).
max (E) Efgl I exp *E(n]
2 (h(u) -h)) min,EE,,f))) min((
(82)
The main difference of this assumption and Assumption B.3 is the difference of 82 and 16
Proposition G.2. Consider the rooted tree T and transition matrix M described Theorem 1.6 There exists C = C(M, d) 2 1 such that A1 satisfies Assumption G.1 with some parameter h satisfying
he & C(log(R) R) + +).
(83)
Theorem G.3. Consider the rooted tree T and transition matrix M described in Theorem 1.6 There
exists = C(M, d) > so that the following holds. Suppose A satisfies Assumption G.1 with some parameter h. Let B ((A) (see Definition 1.17y. Then, B satisfies Assumption G.1 with parameter
h + C(log(R) 1).
Proof of Theorem 1.6 The proof of Theorem 1.6 is analogous to that of Theorem B. employing similar strategy by leveraging Proposition G.2 and Theorem G.3 in the former, and Proposition B.5 and Theorem B.6 in the latter.
In this section we will prove the Base Case Proposition G.2
Lemma G.4. There exists constant C' C(M,s) 2 1 so such that for any p' T and 0 I z h(p")::
Consider two degree polynomials f and with variables (Iu .uE (p)). Suppose
s(X)= Σ fa(X) almost surely.
vEDm((p))
where fu(x)) = fu (z)) and EXfa(X)] = 0, and we assume the same conditions for the polynomial and 9u. Then,
max (Ep EEfll s CRexp(-c(h(o)) m)) DE[gi
Σ
EF2(X)
Σ
(x)(X).
(p')
Proof. Let C= CM, d) denote the constant introduced in the statement of the Lemma. Its value will be determined along the proof.
First of all,
max #E
(E, fg)(() EEgg 0E1g)
max
Σ (uB))))))) - Efago
u.vEDm((p')
Σ
max
(E, (() -Efugol
ØElg
44

---

Our proof will be carried out by estimating each summand. Fix any pair 24, E (m and consider
((Eprfugh) Efugolloc 0 E (x(()g. Efug. X2 = 0||
Let w = p(u, v). Since fu and gu are functions of z'w. relying on the Markov Property we know the function (Ewfa (z) is a function of zw with expected value
With
(Ep (ugw)(a)))) = (u Xx xpch
applying (10) from Lemma
A.5
(ugoo) - Efugell <Css hpp) -(w=))))0))>> (En))))) Efugelloo
where (A. is the -ddependent constant introduced in the Lemma.
Next, will estimate f. (0) fugg |1 In the case # u, there exists # j such that wy and I w. which in turn implies that (X X zw) and (Xgul Xw Fw) are jointly independent by the Markov Property] Thus,
(Rrcsa9o)()) = (B0
which implies
max (w)) < max (E., (w))
max (Eungr.)))) DE
0E (E(q)
h(w) X m) /BB (EJE(X)
where we applicd (T)) and from Lemma A.5 in the last inequality. If u = v. then the same estimate follows immediately without relying (10).
Now, we convert the above estimate to that of [E.. (ag. Efugolloo which relies on the simple bound that (X) I maxøe(1) (Ew..ug) Thus,
(Ew.)ug)) Efugolloo
max (Ew.uu.))
<2G 43 h(w) 30)
Together we conclude that for pair u, E (m()') with = p(u,
fuge) - lougello <20 h (w) - m) (h(p') h(w)ww()))) ((()) VE
AB h(p') m) mm) b())))((((()))----->))>>>>)))>)) 2m (B
Relying on this estimate, we are ready to bound the 1. of (E. Efg.
max [P) - Efgl
6E[g)
Σ
max [E, Sw..) - Efugo
AE
w.d0 L.vED... (ot)
Σ
Σ
Σ
max (Ep.fug.)) E.fuvll 8E(1]
kefm,hlp") wEDi (e') u.v. p(v:p(u.))=w
Σ
Σ
Σ
20 A. h(p')
2B (84)
kE(m,h(p') we De p.
Next, relaxing the condition p(u, v) = w in the summation,
(+) Σ
Σ
Σ
h((p') m)) 34 h(o')) x
KE (Emmm ]] wE
(m.) (10)
Σ
Σ
20 2.. h((p))
Σ
V Egg(X))
kE(m, (e")
D,n (ar)
NE (w)
45

---

jn Itsl follows from Jenson's inequality applying to the function t + 8² and the uniform measure on [n]. Now apply this incquality to the collection (VE) and ( (X)) respectively, together with (Dm (w)l I Rd" from our tree asscumption, we have
Notice the inequality Eiein R4l I
v
(+)
Σ
Σ
20 A5
(1(p') - m)30 b(p'"> 2m Ra
h(p') I wSp wEDr(p")
Σ
(X((
(x)(X)
(w)
wE (w)
Σ
hipp) m)) ( h6o' 2m 2m Rack
kE m(,')
E
E
(X)())
E
Exā(X)
wSp'
(w)
"Sp' li(w)=k (w)
20
m) 34 الوم ) )+
2m
Rac
Σ
E
E
(X),
k((m,
(P)
(EDm((o
(85)
where the last inequality follows from Cauchy-Schward inequality. Finally,
h(p') - m) m) ((p')+(p 2m Rd
ke (m (()))))))))))))))))))))))))))))
<2 22 R(h(') m) (hip') m) m)) h(0))-
A gk
max
ke ((p'))
22 R(((')) m)88 (h(p') m) (max ^1) h(o') )
=2 ((((p m m))mm 3 exp( 1xp(-1111e(M 1.1e(((pp)) m))
< CCRRexp(-s(((( m));
where
Co = 2C
A. max ni 3 exp(-0.1en) < +00 neN
is a constant depending on M and e. Combining the above estimate with
85) we conclude that
max
(g) - Efgl < CeRexp ( =(h(p')( - m)), 8E]y]
Σ
(f
Σ
Ex²(X),
uEDm(l")
and the lemma follows.
The statement of Lemma G.4 together with Proposition implies the following:
Corollary G.5. There exists constant C = C(M, 2 so that the following holds. For pf ET and 0 < m < hp'), consider two degree I polynomials f and g with variables (In Dm (p')) with (f(X) = Ex(X)= = 0. Notice that by the Markov Property
(E)))))x) is a function of N.p.
Then,
max (g) Efgl < CR exp(-e(h(p')) -):0)mmm)))))))))) m)) (g 0E
Remark G.6. By taking the degree polynomial f = with the assumption that (E)(() we get
E
max (o)rff)(()-(f))) - < exp((222(()) 8Elg]
(86)
In other words, if h((p)) is sufficiently large, (2)x)))) is almost the same as (x2(X) with small fluctuation. Let state this as seperate lemma.
46

---

Lemma G.7. There exists C' = ((M, d) so that the following holds. For of E T with
h(p') 2 C(log( (R) +1
any degree I polynomial f of variables (Inu E Lipr) with Ef satisfies
max(E, (0) - 2
min (Epp' f (0). DEly)
8E[4]
Proof. By Corollary G.5
for every 0 E [g).
(E, - v C Coalt exp( exp(<eh(("))Bf((
where Crena is the constant introduced in Lemma G.5 lemma as
Now, we set the constant described in the
C
log(4C(r.s) + 4).
which implies
Rexp(-ee(pp)) - exp (- (<e((pp') C(log(R) + 1))).
Cr
Then, with h(p') 2 C(log(R) + 1)
& (X)(
which in term implies
max (n) (B)
(Xf( <2
minsely (E I {xf((
Proof of Proposition G.2 Let Co denote the constant introduced in the statement of the Proposition. Its precise value will determined along the proof.
Let pl E T with h' = h(p'). By Lemma (Ir E Lpr) satisfies
C.9 any degree-1 polynomial f(x) with variables
Var
< CaaRt (1/)) Varls(X)), (N)3
where Cro denotes the M M-dependent constant introduced in the Lemma. For the term in front of Varlf(X (x)])())),
Ica (2A)))))))
(ean R.d (1/)22 exp(-1.1eh") S exp ( a - Ci + 1)))
where
C = log COAs
4 max 24 exp((000.eg) nEN
Thus, we impose the first assumption on Co that
Co 2 Cı.
then the first condition (8I Assumption holds for A if take he > Co(1 log(
It remains to establish 822 Let f.g g be two degree-1 polynomials in the variables (s, u E T.p')
satisfying (XX = Eg X = 0. First, by Corollary G.5
max (E (9) - Effgl [E[g]
GG. exp( ((-=sh(p)) (BP
where Crenp the constant introduced in Corollary G.5 Assuming
Next, we would like apply Lemma G.7
Cem log R) 1)
h(u)= >
47

---

where CG. is the constant introduced in the Lemma, we can apply the lemma to get
E f2 (x)
S 2 min (0)
0
and the same holds for Together we may conclude that
max
(1) Efgl
22 Ca
exp(- /mnee /njn(E
min(EE (0)
6
6E(g]
Now, we impose the second assumption on Co that
Co 2 max {
[ogg(2((s)) (c3)) + +4) G.7
Then, we conclude that
(-e(b(l') Co(log(IB) + +1)) (Boooo))Co((oo(( /min((E.. (²)(0) m (0)
max ((E,,))( Efsl S exp 8E(d]
provided that
h(p') 2 Co R) + 1).
Therefore, we can conclude that A satisfies Assumption G.1 with
h = Co Rt) + 1).
H Inductive Step in General Case
The goal this section is to prove Theorem G.3 Let us restate the theorem here:
Theorem. Consider the rooted tree T and transition matrix M described in Theorem L.6. There exists C = C(M, d) > so that the following holds. Suppose A satisfies Assumption G. with some parameter h² Let ((A) (see Definition 1.17). Then, satisfies Assumption G.1 with parameter
h C(log(R)+++ +1)
In this section, we fix a subcollection A satisfying Assumption G.1 with a given parameter h and let B ((A).
We begin with the following lemma, which allows us to recycle some of the results from the case CM 0.
Lemma H.I. Suppose A satisfies Assumption G.
with parameter h? Then, then satisfies
Assumption B.3 with h = + log(2) and c 2
Proof. Let f be a polyynommia. If we set h 2 h. then 15 follows immediately from 81
Now, we assume that Ex(x) = 0 and h(v) > h We could apply 82) with g = f to get
( ( exp ( _ (b)
h2) EF
max 8E[g]
If efexp (- (b((b) -h)) } or equivalently,
2 h(w)) 2 h + log(2), E
then, for every 0 E [g].
3
Eh² Eh² (X) S (B)
- Eh (X).
Therefore, if we set ht > h + 2 log(2) and ~" 1.4 both 15 and 16 hold.
48

---

In the remainning of this section, we set
2 h" h log(2) and
(87)
2
and will rely the fact that A satisfies Assumption B.3 with these parameters. In partieular, c,,, 1/2) such that for any
we could apply Theorem B.6 to show the existence Bgo-polynoiial f.
B.6
Var ((r((,)))))) < exp [ h G log 11) Var
Therefore, to establish Theorem G.3 polynomaass f and g with h(()) 2 ho + C(log (R) + 1) and (f(X) = Eg(X) = satisfy
it remains show the existence of C C(M, d) so that any
max (0) Efg exxp ( (h(v) - C(log(R) R) + 1)) min (3) min(E /E[g
2
To establish the above inequality, the higher level structure essentially the same that for deriving Theorem B.6 We again decompose and according to Lemma D.1 To the proof of the theorem, similarly it contains three steps:
1. Establish properties of Fu and I.. see Proposition H.2
2. Estalbish properties of fa and gk. see Proposition H.6
3. Establish Theorem G.3
H.1 Properties of fu
The main goal want prove in this subsection is the following Proposition.
Proposition H.2. There exsits C = C(M, d) 2 1 so that the following holds. For a given E L with
h(u)) 2 h + C(log(R) 1),
suppose Ju and are two functions which are linear combination of (x(x) with a E F(B.). Then, for any 0,0 0' E [4)
((En.fgw)(() ((En.aaaa)))
<exp -- --20(1 (b(w) C(log(R) + 1) - hº)) mmin(E..f3) min(Eng])(
With a minor modification to our approach, we are able to obtain an analogous result wherein fa and Iu are substituted by Ju and Iu. respectively:
Corollary H.3. There exsits C C(M, d) 2 that the following holds. For given T with
h((u) he + C(log( R) + +1,
suppose Jn and gu are two functions which are linear combination of vs(x) with S E F(B.). Then, for any 8, E (g).
(EuTfo)))))) -(E.F..)B)))
< <exp --
1-2-0bt (h(u) C(oog + 1) - -h)) minn(E. min (E)
Let us prove Corollary first
Proof. Let Co denote the constant introduced in the Corollary. Its value will be dervied during the proof.
From the identity
(x(z).. = -
49

---

it follows that (Eufuuu)()) (e)) s (E. (1))(()) (Eufugu) + (X) (Bnff)((')
+ B (Eugu) - (E))
(Bu. (0) (Bu.agg) (f') + max (u) max (E)g(())
First, we apply Propostion E.1 with the fact that satisfies Assumption G. with parameter h* h + 2 1og(2) and c*
max
max (B. (() S exp(-22(h(u) G log R)) + 1) h")) max (B.
where C To = C(M, d, () the constant introduced the Proposition.
Second, applying Proposition H.2 with Ju = we have
max max (0) min ( (0')
8 (b(u)
Cuz log R) +1) h²)) min (Ei)(
S exp
2
where CH.2 is the constant introduced Proposition H.2
Let us impose the first assumption that Co 2 Then, with h(u) 2 h + Co(log(R) + 1), we can conclude that
max (O') s 2 min (0').
8'
6'
Clearly, the same derivation also holds for ga. Therefore, conclude that
(E (Pn.fa.)(() (0) (En.fuon)('))
(Eufagu)()) (Bn.
+ 8 8exp(-22 (22e(((w)) - Ci (log(A) (R) + 1) - -h"),, min(E.,f)l min (0)
8
<exp ( (h(u)) Cha log( R) + 1) - -h)) V min (3)
E. (0)
exxxp ( 2s [h(u) ET log (R) + 1) - h - 2
5 log(2)) (2)
min (E., (0) min(E.ge)C
<exp (-2 (h(u) - Co(log(R) R) + 1--1)) -h)) min(BB. min min)E..)))())
where the last inequality follows by imposing the second assumption on Co that
Co 2
log(2) + max
{ {CHE
1 log(2)
1og(8)} }
2
This completes the proof of the Corollary.
The main technical part for proving Proposition H.2 is the following:
Lemma H.4. For any T with exp (- (h(u) - h))) S 1 the following holds: Let I C [duy] be subset of size at least 2. For any u(æ) and b(xx) which are linear combinations of vb (1x) with Bu satisfying ((a) I, we have
(E) -EE,ab) SAdRexp ( E (b(())- -h9))-h)))))) miin(E,a) min(E,b?)(()))
max Elg)
Remark H.5. From the assumption that h(u) satisfies
AdRexp ( 8 -h((w) - ho)) s 1 <l 2 log(4dR).
By taking a(x) b(x) we have
max < 2 min (E,,a*) (0).
(88)
50

---

Proof. Let a(x), and b(z) be the vertex and functions described in the Lemma. Let us introduce some notations for the ease of expressing the calculation later. For brevity, let
8 exp ( (b(u) (h))
For E [al", let
Fa.l (Bu))EL)
For any given function hxx) with variables in (Øe User Tu.), we define
EE., (Eu, = E ((x) Ye & Ufw < u.}, X. = Zu
iET
Observe that
(z));, (b) and (E,,
functions with input I- This is due the fact that and b -add consequently ab- are functions of variables (Ie : 2o E Uier I and Markov Property
The function u + (E,,, rab) (1 is Lipschitz continuous with respect to the Hamming Distance with Lipschitz constant
Claim:
28 V
(m,, (zu,)), Ra.1
max(En,, (z
(89)
Bu.1
We begin with the proof of the claim. Fix an index in E I. Without lose of generality, we assume I [k] and 1. For [q]", let
Vi =IgN:
for S [dw). and set
(x2 . rn).
With this notation above, we can express
(xx =a(ro- x1)
and
b(x) =b(20, x1).
Fix any value of zo, the function
+ a(To.
a linear combination of den (x1) with 01 E F(Asu). Notably, this implies that Ea(ro: X1) The same properties hold for the function 21 + 6(x0,
Now, given the assumption exp (- [h(()) h))) < from Assumption G.I to get that
and implies h(u) 2 hi, we can apply 82
1
E [a(Fo, X1 X1)b(zo, X1) Xu, 01] E[a(zo, (o((xo,X))bb X1)0(2o, X1) Xu, 02]
max 6
<2 max #E(d]
E [[a[zo X (6(2))(((0))))))) X1) X 01] -E(xxo X
<28 V
min E a² a2(2zzo00 X1) Xn, min E (2 X1) Xm., 0
For any x E [q]". let æuo = (Iazy Tesi Lus. ). By the Markov Property for any e [g].
(Xol Xan Tngs Xm, 0) -Xool Xug = Fuoo and
(X, Xms Dug X,, 0) = =(X,, X A)
are jointly independent. Hence,
E[a(Xo,X X1)6(Xx, X Ruo Xu, 0]
-B|a(Yo, X1 (1), X1) Xa, =
51

---

where Yo is an independent copy of (Xo Xu, = Tus) We have
E
aa Xo, X1)66XX, X1) u Fug: X 0) Blaa(xo X1)6(Xo, X1) Xuo =uo X 0']
Ey.
Ex, (a(% X1 (Y),(Y6, Xi)) Xu, =0] Exx,a((Yor X2) X1) Xx,, =81]
X1)6(Yo; Xi)) X = 0 -xx (a Yo: Xi) Xi) /m, 071]
(min Ex, [a (1,.Xi) Xu, = =0) 1/2 min Ex, (Yo. X1) | = 07) 07)
<20Ex,
220 [xx [min Ex, Ja (Yo X1) Xu, AI) 1/2 (Ex, min Ex, [b2 (Yo, X1) Xxx, = =811) 1/2
#
where the last inequality follows from Hölder's inequality. Further,
Ey, min Ex, [a2 (Y,, X1) Xw, O]] I min Ey, Ex, [a2 (Y,,,, X1) Xus = 811
8
min E la (X) Xuo Fuar Xa1 0
max(Eu, a ) (In..).
Iu,
Applying the same derivation 6 we get
Ey, min Ex, [b (Y,, X1) Xx, = = max 1²²) (FF,))))
uu.!
Therefore, our claim follows: For any 0, [g).
[[
Xuo = Fug Tua = B[a(X)6((X) Xuo Ru Lus = 81
$2
max(Ea") fa.1
Fu.1
With the Lipschitz continuity been established, essentially the lemma follows when d is sufficiently small. Let us proceed with the remaining argument. Let
I'u, -argmin,.., (Eu, (Fu.r) and z",, -argmax,,,,.. (Eu, (zu.)).
Applying 189 with the assumption alx) b(x) and the fact [1] S du.
(au, - (a), 5 (a) (d',t))
and hence
1
max (2) (Iu.I) _ - 2d Du
min min(E (in (2 < 1 2d
min(Bna²)(ss
(90)
provided that 0 < 1.
Again, the same derivation also holds for b. Combining 0, 8' E (g).
(89 and 90 we conclude that for any
(B) (E, S max (B,,
min(E E, ab) (x',,)))
2n,1
2
< 1 2d,
(nin(E,,2
min (ninnE,,b21 (2)0))
6"
With our assumption on the tree that d, S Rd, our assumption
(-g (b(u)) - ho)) s 'Rdd'
1
exp
implies that
2d
< 4Rd5.
1 - -
We conclude that
(() - (B))) S4Rdexp (5 - -1)) (nin(E,,a))) (() min (E,, (00))
52

---

Proof of Proposition H.2 Let Co = (M, d) denote the constant introduced in the statement of the Proposition. Recall the decomposition of fu into f from Definition E.4 consider the decomposition
fu(z)=
E
fa)( and gu(z)=
Σ
I
rg(d.):|1122
[g|d.):|1222
The proof of the Proposition will proceed by bounding summands in the formula below: (Bwfugw)()) - (Ewfugw)())
Σ
(E.fu.19..))(0) - (Eufa,19u (91)
I. IJC
Estimate of summands in (9T:: For any J, S [du)] with J have
consider:
First, we consider the case f J. Notice that, by Lemma H.T A satisfies Assumption B.3 with
parameters (ho + 2 12g(2), 5). This allows us invoke Corollary E.6 yielding
(En.u, In, (0) (Bufu, (Bufu.19a..)(11
22 max (E..fu.19u.)) [E[4]
<2exp
(-
h 6 M, d, 2) is the constant introduced in the Corollary.
(h(u)
2 1og(2))
(max((B,f()))))) DE
(
2
E
øelgl
where C
Let us impose the first assumption on Co that
2 (1 + (og((d));
C.
which implies that hi(u) > h + Clog Rt) + +) 2 h1 + log(AdR)) With this assumption, we
could apply the remark 88 of Lemma H.4 to get
(max(E,,f (u, (0)) 1/2 < (Ein(Euwf
and the same holds for Ju,J. Hence, for I + J we have
((e..u..1...))(0) (Bafu.19...)(00')
<4exp e|TAJ]] (h(u)= E.6 h + g
2 1og(2))) min (Eu)(,))())
min (E))),)) 1/2
8E[g8
8elg)
Second, consider the case I J. Here simply apply Lemma H.4
yielding
((1 - (E..f..19..,)(00)
<ARdexp ( _ (h(u)) hn)) 2
min (E., (B) (in
(O))
AEl9.
Let us unify the above two estimates by introducing
log(2) log(8), 2 + log(24d))} Cea
C max
e
Then,
(...ff..1u..)((0 (E.
(92)
exp (- max[[ 1H((w)) - (log + ho))
E
min (En (E. (0)) 8Elgl
min (E. (E.....) (0)) 1/2 9E[g8
0
:=8,
(93)
for every pair I, J C [du] with [/| 2 2 and |J| 2 2.
53

---

Using this inequality, 91 becomes
(Bufugu) - (Eufugu)('))
-
Σ
alLaL = ã" A3 & ||l|| ||||||||] |||]| (94)
where ã
11/22 and JSL4 Further, | 11122 3 (3)
and || are the & norms of and B, respectively, and |||] is the operator norm of A.
Estimate of operator norm of A: Notice that A is symmetric matrix. Thus, can fix unit vector 7 satisfying ||||| = 77 Aς. For each pair J [dw) with |/] 2 and |J| 2 2, since ar,J 2
L1 11 + a1.J 13
S CLL1jiL
2
and thus,
|||||
Σ
OIJLES S
Σ d
Σ a..))
(95)
Igld.1:11222
JC[d.l :/1122
For each 1 C [d,] with //| 2 2, the number of J C [d.] with |ATL| k is bounded above by d S (Rd)*. Then, with the given estimate of aI,J in 92
Σ
exp (- --(((u) - Clogo + 1) - -h)))
LI
JC
Rdd) exp (- ((h((u) C1 (logg R) + 1) - hn))
(96)
Now, we impose the second assumption Co that
Co 2 C1 + 2 (1 log(2d))
With the assumption that h(u) 2 h + Coog) R) + 1), the geometric sum in 96 has decay rate smaller than 1/2. Therefore,
Σ JC
E (b(u)) C2og(( 1) hb)) -1))))))
a1
exp
2
where
2 2 ( + log(d))
C1+
Now applying the above estimate, together with Eig(d.) 77 = 1, to 95 we obtain the following bound:
E |||| S exp (- (- (h(u) - (log(()) + -))-
Comparison of E, mingely! (En,2, and mingety! (E., ()) (and the same for g): Here is the last step toward the proof of the Proposition. Returning 94 have
(E..f.w)(( (Eu.
S exp (- 8
_ (h(u)) (log(() 1) 1)- hh))
min (IE,, (2,)) #E(a)
min ( (0). Σ
PE(a)
Let us impose the third assumption on Co that
2
C
log(2)
F.7
E
54

---

where 7 in Corollary invoke this Corollary yield:
E.7 Recall that we have h = h1 + 2 log(2) from (8
We can
40 E [al.
Σ ((EnJH,))))) & (2)
Let fg [g] be the value minimizing
(0). Then,
min 22E/2(0) (2
min (B..a. (()). Σ 0E gl
BE[gl
Clearly, the same derivation also holds for Iu. Together we conclude that (BnLuDu)(0) (Bu.Sugu)(0')
Sexp
2 (b(uu) C2(1og(II) +1 -h)) min (0)) min (0))
dEl
8E(el
Finally, if we impose the forth assumption on Co that
Co 2 Cz
then the Proposition follows.
H.2 Properties of fs: Products
The goal of this subsection is to establish the following.
Proposition H.6. There exists C = C(M,)) d) 2 1 so that the following holds. For any p' E T satisfying
h(p') h C(log(R)++1 +1
and a positive integer h C'log R) + 1) S S h(p'). Consider a function and g are Be polynomials with (X) (X) = 0. We decompose f and according to Lemma D.1 with the given kj. Then, the following holds: For k S m, S h(p'),
-ff k} > kn,
max 0,0'
(E, fm (0) - (E, fagm)
sexp _ (2h(p') maxfk, m) ((log(()))))))))) + ((lg((()
If m = ki
max (
fagm)(0) - (E, (o.m))
exp (- _ (2h(p')
2k: C(log Rt) + ( (x)
The proof mirrors the structure used in Proposition and Proposition H.2 Through this subsection, let
F.1 In this case, we rely on both Proposition E.
C = (M,
be the constant described in the Proposition. The functions f. g, and are introduced in the Proposition.
55

---

Assuming without lose of generality that m S k, we apply the reasoning from 72 yielding
in Proposition
(Epr (0)
-E Σ
(EnFW))))
Σ (Eusm.a(X)) Xx xx=xx// - =0}
E
fugm...)
"EDx(o))
WEDE(M)
WE WEDx(()
E (eD
X 0).
and hence,
(Br - (Epr
(Epr (Bx (0) - (Bx (BA,))) (6')
Σ (ED)(P")
(ugm,,) (0) (Ber sus
Σ
((Ep' (Euf (Fugm.))))
(En (EL)))) (8))
(97)
oEDa(o')
Similar to the derivation of 64 from Proposition above three summands.
The proof is dedicated into estimating the
We begin with the following estimate:
Lemma H.7. There exists a constant C = (MM, d) that the following holds. Suppose C 2 Ch
where Tigg is the constant introduced Proposition H.2 Then, the following holds: For u E (P)
1. h >> ki, then
(up...u)m, Epr 0.0)
max
I exp
- 2 (2h(()) - k- C(log((())))
+1 1) -K-Colog(AA (2)
(C (x))
2. k: m = ki, then
max 0.0'E
(Bp'
fugm,,,
_ (2h(p') -2k (E (x)) (x))
exp
Proof. Step 1. Bound Tul (X) ))mm, (X) E.iummmul from above: By Hölder's inequality,
Var [ar[(Bulaua (aaaaaalm,a)XX
max 8E4y]
(E..ugmm.u - E./ummaa E (EuJumn w) (Xa) Efugma
n--momm
4n-orm
En noom
CA.3 Var (Be.J w (X,)] (Ifa(X)) mm, (X)
Var (aaFaaaaamm S CAw ( (2)0 (X)= T.a.Ima
(98)
where applied (9) from Lemma A.5 with C7.33 is the constant introduced in the Lemma. Further, relying on (98). together with 9 and (8) from the Lemma A.5 we have
(Epr fn.mm,mm) (0) Br fustm,.))('))
max 0.0'
(ugmm. (0) Rffgmm
max /E[g]
<20 Am h(p²)) - b('' b( max
(En, f.w.m.mmmmmmmmmmmmmm ()) fn
EE n)
<20 A.5 (1(p') - b(') - C
13] Fu gm,, (X) x)= - EF Funmaal
=C
exp(-e(ppppppeeeeeeee (e((pp)))) f. (x) (X)) - Efuggmull
(99)
56

---

where
C1 20 5/2
n
exp(- 00.1en).
nEN
Case 1: m < k. Here we can simply recycle the estimate from (76):
Rafummal (0m))mmm(x)))
sexp 2 C2(log( + 1) -))
( (X))
(100)
where
2 3/3 3 log(d) lpg + 2
2
C2
81
2 log(2),
where CD. is the constant introduced in Lemma D.I and is the constant introduced in Proposi- tion
E
Case 2: l < m k.
This is the case where we need Proposition H.2
With the assumption that C 2
where
2
is the constant introduced in the Proposition, we have
m = k1 2 h + C (log( + 1) 2 h + 42 log( + 1),
so that could apply the Proposition to get
E f (m) - Efugmuul
< max 8,0'
(B...un))()) - S Iu (())
E (k
C log [2) + 1) (1) (x))
I exp
Case 3: Kj
k The last case is straightforward:
Efugm,ul
S 2 Ex)( Eggh
By taking C3 = maxxCC, C22 C C (.)) the statement of the Lemma follows with = C3-
As an analogue of the above Lemma, we also have
Lemma H.8. There exists constant C = C(M, d) that the following holds. Suppose C the constant introduced Proposition H.2 Then, the following holds: For u E Dz(p'),
12
1. k k1, then
(LEpr ((....)) (O) ((E, (B..))
max 0.0'
< exp (- - (2h((')) k C(log( 1 -1) (B) (E92 (2))
2. h m ki, then
(B.. ((Epr (B..
- (2h(o') 2k: -c) (x)) (X))
exp
Since the proof is simpler and the structure the same as that for Lemma H.7 we will outline sketch proof in this case.
57

---

Proof. Let au (xx)= (Bufu) and bw = (Bu9m.u)(zu)) Repeating the first step of the proof of Lemma H.7 we have
max (L Ey anb)) S01 exp( exp((e(h(p') - (a) (X))) 8,0'
bia,bul
with
2G C
max n² exp(-0.1en); nEN
which is exactly the same constant stated in Lemma Next,
E Ea, & 2X) & 2 Ea (X) Bb (X) & 2 2 (X) (B
If k >> k1, we could apply 38 from Proposition E.1 to fu. and get
(X) exxp
25(k
C log [) + +1 -1 log(2)) [f)(())
Indeed, this tail bound is stronger than what we got from Lemma H.7 The remainning part involves combining these estimates with a suitable constant C' so that the lemma holds. Given the argument was already presented in the proof of Lemma H.7 we will omit these details.
Before bounding the summands (97 let us bound ΣMEDi (p) (X)(X) and EUEDa(O' Ey (X) from above by (X) and Ege (X), respectively.
Lemma H.9. Suppose
C
(2g(
where C 22 is the constant introduced in Lemma
F.2 Then,
Σ vEDx(p")
Eg (X) max { 4, RT
Eg (X),
and
Σ Ef max { 2 R*} D.RR
(X).
DEDa(p")
Proof. Given that Co >
log(2), we have
2
h 2 h1 + C* (log ( 1) h +
log(2) + Caa (azlog [ + +1 = h² + Gran (Ig( + 1),
and thus we could apply Lemma
F2
When m > k1, the lemma yields
Σ Eg (X)
E
Σ
(x(x)
Σ
Σ
2E < 4Eg (X).
mEDa(p")
nEDe(P)
ve Dm (u)
DEDx vEDm(u)
And in the case when m = ki, we use the same derivation with Lemma Lemma to get
F2 been replaced by
31 in
(X) &
CD..R R
CD
REgg (X).
HE (P))
Clearly, the same derivation also holds for the comparison of ΣnEDi(R) (x and EX((X).
Now, relying the above two lemmas, we will estimate the second and third summand of 997 Corollary H.10. There exists constant C' = C(M, d) > 1 so that the following holds. Suppose
2
C max
log( (2)
where the constants introduced in Proposition H.2 and Lemma respectively. Then,
58

---

1. if >> k1, then
Σ
(REg) (m)ma))0) (Teyr (ugm..))))))
"EDa(p")
Σ
((Ep' (Bu (B.
(EDN(()
cxp
(2h(p')
k ((og(() R) + +1) - -1)) (Ef (X))
2. if m k1, then the above term above can be bounded by
exp (2h((')) 2k -I))
Proof. Let C₁ be the maximum of the two constants introduced in Lemma H.7 and Lemma convenience, let
H88 For
U Σ
((Bp.Jumm,, (B, (ulmm,)((0))
MEDe(P)
Σ ((E,/
((E,pr (Fu ()))
By the two lemmas together with the triangle inequality, in the case when 1: k we have
US Σ 2exp
( 2 (2h(p') k Ci (log( (t) + 1) h1) (E (EE 1/2 (10 (X)) 1/2
WE (e))
+ <2 exp (- (2h(p') - (1)
Σ
Bi²(X)
Ey
mEDa(o")
MEDE
<2 max {4, B.r R! (ff( (X),
(101)
where the last inequality follows from Lemma
H.9 Similarly, when m k1, we have
U <2exp
( (2 - -2k-
Σ
Ex2(X)
Σ
Eg (X).
(102)
De
By setting
2 (C1 + +og(44 + log log((g
C =
D.
the corollary follows.
It remains estimate the first summand of 997
Lemma H.11. There exists a constant C CCM d) 2 so that the following holds. Suppose
log(2)
where a CF is the constant introduced in Lemma F2 Then,
1. if ky, then
(E,r (Ex (Eagg))) (0) - (B.. (0')
max
0,0 0,0'
exp
- (-e(k(p))-C(logg C(log( + + - 11 hº) (x) Egg (X).
(-e(h(
2. if k m = K1, then the above term is bounded by
exp(-e(b(p') - ki Cloo((R) R) + 1))) E (X) Egd
59

---

Proof. Observe that both (Z)f = EnE (Bufu)(aw) (Ba and (Eagm)(2)
EuEDi(er (B)0 both degree-I polynomials with variables (Ia E Dz(p')) sat- isfying
E (Eagm))( =x
This allows to apply Lemma
G.4
yielding
max 0.0
(Epr (Bx (E (0) (B
2 max (E,, EE fk) (E (0)
E (x
$2 220 R.x. cxx((<<(hh())) k))
E [[En.f,)(X]]]
[[(Engm,)) (XX)]
DEDa(p)
(ED
where Cca 2 1 is the constant introduced in Lemma G.4 Next, apply Lemma H.9 why we need the assumption on C?) to get
(which is
Σ
(mE (X))
Σ
Bg S V max {4, R
R-) (X).
uEDe(P)
MEDe(p")
As for V /EuED(e' E (EEuFu))(()) = m = k1, then we can apply the same derivation to get
[[(Eaaa((X)] $ max {4, G4..B.R R*) (x2(
(ED
This leads
(Ep [k) () (Bas)
max 0
<20 max
2 exp exp(-e(h((')) k)) ( Eg
If k > k1, then we can apply Proposition E.1 and Lemma
H.9 to get
Σ [[((A,))((X)]
V dEDa(P')
S Exxp ( ( e(k: - 1 log + +1) -
2 1og(2)))
Σ
E
uEDx((')
SV max {4, Go R2 exp (-E(k: -Ci log((R) +1 h log(2))) V
5
In this case, have
max 8
(E (Ex.f) - (Ba
2 log (og(2)) (F Eg
<20 max {4, C R$) R*) exp (-e(h(p') (E. R) 1) h
E
By taking
2 log(2) + log Mog(2C(a) (4 log P + 4).
C E.
both statements of the lemma follows.
Proof of Proposition H.6
Without lose of generality, is sufficient to prove the case when m < k.
First, we impose the first assumption that
2
log(2) )
0 2 max
22P2
60

---

where the constants are introduced in Proposition H.2 and Lemma respectively. apply Corollary H.10
This allows us to
and and Lemma H.II For simplicity, let
C1 = max
H.10
Then, combining the Corollary and the Lemma to the estimate l S m I k with & > ki,
we can conclude that: For
max 6.0
(0) - (E fkgm) (0))
c (2h(p') - Ci Rt) + 1) - (1=))))))(())))))((((()))))))
exp
2
and in the case where k k1, the above term is bounded by
exx
2 (2h(p') 24 C1 (log + (E)
Then, the proof of the proposition follows by making the second assumption C' that
0 Ci log(2).
H.3
Proof of Theorem G.3
Proof. Now we are ready to establish the main theorem. usual, Co = Co(M, d) denote the constant introduced in the statement of the Theorem. The value of Co will be determined as the proof proceeds.
Applying Theorem B.6 with A and h' = h + _ 1og(2) and c* = 1/2, we conclude that
Var [E, (x)] & exp <(h(p) B... log R 1) ha) Vax(
for any We impose the first assumption on Co that
f. where C3. C'M,, d, 1/2) is the constant introduced by the theorem.
2
Co 2
log(2),
and conclude that
Var (xpp S exp (- <(h(p') - Co(log( +1) Var
Now, remains to show that with the suitable choice of Co. for any pf with h(p') 2 h Co(log(RR) 1) and any two Bs pEoyynoolsss f and g, we have
(E, S exp ( c (- (Cooo)))) minn(E, (3) min(EE, E (0)
max #E(n]
Let
C = max
Cira
log(2) +
to
where
to is the constant such that Σ
exp
< 1
CH. is the constant introduced in Proposition H.6 and
C(M, d, 1/2) is the constant introduced in Proposition F.1
PM
61

---

Next, let
kj [h + C₁ (log + 1)1.
The chocie of C1 and L allow us to apply Proposition H.6 and Proposition F.1 toward both f and Next, we impose the second assumption on Co that
Co 2 201 + 2.
This assumption implies that there is a gap between h(p') and k1, which is necessary for the proof.
Now, we fix such p' and consider two gg f and g with Ef(X) = Eg(X) = 0. Further, consider the decomposition of f and g according Lemma D.Iwith the above chosen l1.
First, by our choice of C1, we have
2 log(2) + + log( R) + 1) to]- h1 [h
=h-
This assumption allow us to recycle the partial step in the proof of Theorem B.6 to obtain (80):
E
(x) < (x) and
(x²(X) < (X).
(103)
kE (((k)
Second, with our assumption that 2 [h + Cu log( R?) + 1)], we can apply Proposition H.6 to get
((E,()))0) - ((Ep)
E
Sagm fu ((0 - (E, fk.mm (0')
max 6.)
max 0.0'
m, (.k
Σ
akm Cn ā A || ||||||||||@|
m. m. (..kk(ka,h(p')))
where á = (akk .,. (h(pp)))))))))) with og = (EF((X),
(Bk, Pka Pr(pe) with Am
V Eggh (X), and
(akm ) k. ((o')) with [hh(p') - h(p') max (k, m) M.
exp
log( R2) + - hP))
max fax mk > ki
akm
exp
(h(p') - h(p') 2k1 CH log R + 1))
k == m = Ki.
Together with (T03.. we have
a | BIAX
The next goal is bound ||A]] from above. Notice the fact that the matrix A is symmetric implies there exists unit vector 7 such that ||A|| = 7T Ag. Now we fix such vector 7. Relying the fact that 0km 2 O,
|||||
Σ
akm Tik Tm S
akm
(yE + 22) =
ajem
2
k,m((Hy,hh(o))
k.m (As b(p)))
me mE h(o)))
Clearly, from the definition of ajms the term Σ ΣnE(k),h(o') Okm maximized when m kj.
Opki = exp (
1---0 (h(p') + h((') 2ki C log([)) + 1)))
Σ exp - (h(p') + h((p)) - -- -KCCHE
H. log [t) + 1) hn))
kE
(h(p') -.. log( R) + 1 ho))
exp 2
[exp
(h(6') - 2h h9)) + Σ
exp ( (h(p') (1000())) -R)))
kElk),h(p'))
62

---

First,
E
(xp(-1110
E (h(p') - -k))
1 4
1 expl-e/2) $
Second,
exp
(-g - 21, +1)) Sexp
(o((lo(RR)+ 1) 2(hh +
+ 1) + +))+))++++++ +)) +))+))++++)+)))
sexp
(Co 2C 2) +1) 1
2
which in turn implies that
exp (- E (b((d) 2h: + hh))
E
( exp (- -h(0))) (o((d')-k)] -k)) S
Hence, we conclude that
||||| S exp
E (- (h(p')
C log R) + - -h?)
Together we conclude that when h(p) 2 h1 + Ci + 1), any two -eo and with Ex() Eg(X)= = 0 satisfies
max
(g)) - (0)
(104)
0,0' Elg
10
(- 8 (h(p') -nr C + 1) 1111--h9 -1)) (Bgg()
& exp
Now, we impose the third assumption on Co that
Co H66
log(20/E),
then
10 exp
E (-g((()) -w (lo ((rlo')CCrrlllogl(
(1) s exp (-
10
+1) 1/2.
Next, we apply (104) to the special case that f= g:
(X²(X) min (R. ()) S max #E(g]
(R,r (R. (g) S < 0.0'Elg)
EX) < 2 min (E (2) (0).
Clearly, the same statemnet holds for as well. Substituting these estimates back to (044, we can conelude that when h(p) ho (o(log(RR) 1), any two B polyyommals f and g with Ef(X) = EX( = satisfies
max (E. (g))
8,0' Elgl
20
(x (-1(h(pp)) (log())((R)) +) -h9))
6 exp
minn(EE (2) *E(g)
min ()))))(
V
@E(g)
< exp
(h(p') Collog( R) 1) ho))
min (E (2)() 0E(g)
min (E (8). DEig
2
Therefore, the theorem follows.
63

---

I Variance Estimate for degree polynomial
This section is dedicated to prove Proposition C.3 Let restate it here:
Proposition I.1. There exists a constant = C(M. d) 2 so that the following holds: Fix pl E ET, and 0 < k I h(p'), ), then for any degree function I with variables (In. E Dz(D')), There exists functions Ju( = (T for u E (x(p') ) so that the following holds:
1. [(X) EnEDuLR (u(Xu) almost surely. (They may not agree as functions from [g] to IR.)
2. For any E To with h(u) 2 k,
Σ
Var[fu(X.)] S Var Σ fu(Xu)] wEDx(1)
NEDx(1)
Example I.2. Suppose u, c(p') for u, u, o T and consider
1
0
07
0
M
2
0
0
1
Let us consider the function f(x) = fu(x) + (a) where
fu(z) 11,((2)) {
if xn. E {1,3),
otherwise.
and fo(x) (0()))-11,(11)) -11,(()))
Condition X, S(X.) (X on X, E {2, 4), almost surely. However, observe that the uniform measure [4], which implies
condition X₂r E [1,3} and condition
= 0- Put it differntly, Var[[(X)] = 0 since f(X) =
Var[fu(X.)] Varlfo
0.
Therefore, it is not true that (2 holds for the standard (Efron-Stein) decomposition of f(x) EveD Jo(x.).
Let us make simple observation to give the insight for the construction. If f(X.) is function of Xp(u). then for each E (4]. the functtion f must take the same value for all possible outcomes of X,, conditioned on Xp(w) In other words, the values of f are constant the set
S; supp(row; (amp(row,MM) (M))
(105)
for every [q]. Now, let us consider the case where f (X,, a function of Xpr(u)- This can be a function of Xp)+((u) Equivalently,
reformulated as follows: for &s E [0, 1], E (Xx,) (w)( the values of M are constant on the set S: for every i E [g].
Therefore, it is evident that the construction of the basis should primarily revolve around the sets (Sthel and their interaction with M.
Following from this discussion, the proof of the Proposition I. is divided into the following steps:
Step (Section I.I): We try to give a precise description of when f(X.) a function of Xxp(x)) for some i E N. To this end, introduce the following notation.
Definition I.3, We define the following partial order relation < on the collection of all partitions of [q]: Specifically, for two partitions P and P', say that P P' ifP' is finer than equal to P.
Further, there exists E such that p for 2 r the trivial partition.
Lemma 1.4. There exists chain of paritions
p0,0 > pp10 .2.....> pro ....
A function f : R satisfies that f(X,) is a function of X Xpr(v. (p((w) for some E N if and only if f is linear combination of 1p for P pro
64

---

(The double index for the partitions is due to technical reason, which will be clear in the construction of the partitions.)
Step 2 (Section I.2): Next, we try to extract basis of functions according to the partitions fro the previous step, along with suitable quantitative estimates:
Proposition I.5. Let M be an ergodic and irreducible transition matrix defined on the state space [g]. We can construct
basis of functions from [q] to I. denoted
(Swlwew:
where W set of size q.
a function
r: W WW
and constant C >
(which depends on M)
so that the following holds:
1. Let
To
max r(w). WEW
There exists unique wo E W such that r(wo) = ro. Moreover, Eno
2.
For each w + Wo. (w) is function of X, where v = -p((w) (u) and (Xw(Xx) = 0.
3.
Var Σ (Xw)(( S SC( max w:r(wW)ero
lcwl)2
4. For any 0 S r < such that {w E W r(w) r'} is not empty,
EVar B
Σ
(X))(
Xp(e) w:r(w)-rr
max
lowl)
W: W:r(w)=r'
5. For any 0 S r' < such that {w E W r(w) <r'} is not empty,
EVar
E
Σ
(X [xn]] Xpcw]] S C(
max low ))
(ww)
Remark 1.6. For w E W and / E [r(w]], let
M'Ew:
(106)
where we treated & as vector in Ø441, Equivalently,
()) B[E(X.) X. = 0) where v E T are vertices such that = p' (u).
Step 3 (Section L.3): Finally, we will use the basis from the previous step to decompose degree- polynomials to prove Proposition [.]
1.1 Partitions of [q]
Let us begin with the following observation.
Lemma 1.7. Suppose )aE is a collection of non-empty subsets of [q]. Then, there exists unique partition of [g) that satisfies the following conditions:
1. For each E I and P P. either Oa P or Oc 0.
65

---

2. For any other partition P' that also satisfies the above property, P' < P.
Proof. The proof can be carried out by constructing the partition P.
Without lose of generality, we may assume the collection {Oa contains {{0) se(e]' since for singleton {0} and a set P, it is always true that either {0} P or {0} np= 0. Consequently, we may assume
U - [g]- aε1
(107)
First, we define equivalence relation on {Oa)ae Jatr follows: For any a, a,a' I, we denote ....... 04)) such that Oo.,, O Oa # for i E [7]. Let
Oa O,' there exists chain (a, (e,,a....... Ii...., INo C / be the partition of such that {Oa)oEn, for h [oo] form the equivalence classes of the relation. Now, = (PI,.... Pkg where
Ps = Jael Ok.
Claim 1:
For every I and k E [No]] either O~ S Pa or On Pp
To prove this claim, consider any a and k described above. Suppose O, Ps + 0. Let O₂ n and pick an index a' Is such that 0 E Ozt Such an index exists because Ps. = Un"ET, Oct Then, we have O, n Ow + 0, implying a E 4. Consequently, O₂ C Ps. Therefore, the claim is proven.
Claim 2: is a partition of [g]-
We need to verify three properties:
1. URE[ku] Ps lgl.
2. Vk [Ko], Pk + 0, and
3. Pk Pe = whenever K.
First, for each [g]. by (107). there exists a E such that 0 E O.. Then, A O₂, E Pk where is the index such that Ix. Hence, we conclude that Uke(Ra] Ps [4]-
Second, for each & [Ko], let E 4g. We have + Oa S Ps. Thus, Ps is not empty set. Finally, for any distinct k' E [No], suppose Pk n Pv. By (107), let a E be the index that E Oa. Hence, both O₂ n P& and O n Pk.. .. In particular, it is necessary that a E L and a E I which forces k', leading to contradiction. Therefore, Pş P whenever is # k. Hence, the claim follows.
Claim 3: P' < P for any P' described in the statement.
To prove the claim, it suffices to show that for any P' E P' and Pa E P with &: E [ko], P'n + then Ps P
Let us consider an arbitrary pair of p' E P' and Ps P and assume that P' n Pr o 0. There exists an index such that O, O P' n PA f Based on the assumptions regarding P and P', we have It and O2 P'.
For every other a' It. there exists a chain (a = ao, a1..... 04 = a') such that Oa,, n0 * for E [1o). Observe that if Oaq-1 Pl, then O.. C P', due to O., P' Oo, 7Oac. # 0. With On C P' as our starting point, we can apply this observation repeatedly to conclude that O.r C P Since the argument works for every a' E Tk. conclude that Ps = Untel Oa" C P'.
Definition I.8. For any given collection of subsets (Oataer of (g), ler P((Oa)oer) denote the partition P defined in Lemma 1.7
66

---

For any given partition Q of [g), let
Psc(Q)= P(1Q)Qeq (S.hiel))
Remark 1.9. Clearly, (sc(Q) Q. Definition I.10. Let and
p0.0 (2), (2) {a}}
p = )sc()
Let us remark that p1. is the finest partition of [g] that each part P p0.0 either contains S, or disjoint from S; for i [q].
We use double indices for indexing the partitions because constructing such chain of partitions requires the creation of multiple partitions along the way, as we will illustrate shortly.
To proceed, let us begin with a simple observation.
Lemma L11. If P pl.0, then
M1p = =1
where
Q= fie [g] S; S..
Suppose P1. = (2,, PRo) J. Then, the collection Q == (Q1, ....... Qk where
Mlp, = lq.
also a partition provided that M irreducible.
Proof. For i with S, = 0. it is immediate that (M1p); = 0. Conversely, when S it necessary that S, P. Consequently, (M1p); Σeę(} My = 1.
To establish that is partition, need to demonstrate the following three conditions:
1. Qk n Qu = for all distinct k,, k' E [Ko]-
2. URE(M] Qs = [q].
3. Qk + 0 for all & e [Ko]-
For the first condition, suppose there exists E Q₁ n QN some distinct and k', By definition, S, C Pk. and S, C Pkr, which is contradiction. Hence, Qs Q 0.
For the second condition, for every i [g]. we know that S P& for some k. Consequently. e Qu. ensuring Uae [M] Q= [q).
For the third condition, if we assume Qs = 0. implying that no E [q] satisfies S; S Pk. then M is irreducible, since the states in Ps. cannot reached.
Definition I.12. Let PI.l Q where Q the partition described in Lemma L.I Lemma 1.13. If P is a finite union of parts in P1.0 then
M1p =1
(108)
where Q is a finite union of parts in p1.1 The above map induces bijection between subsets of [4] that are finite union of parts of p1.0 and subsets of [g] that are finite union of parts of p1.1, in which preserve the inclusion relation is preserved.
Proof. Let express p1o0- Pa,........ P and p1.1 (Q1, 22..Q... Quoo where le. M1p,
For each I C [ko], let Pı Uker Ph and Qı -Uker Qu. Since 1p, Eker 1p and 1Qr
Eker IQ., clearly we have
1Q, M1p,
Since naturally both finite union of parts of P and of Q are identified with a subset C [ko] in the above way, the statement of the lemma follows.
D
67

---

An immediate consequence is the following.
Corollary 1.14. The transition matrix M induces a bijection between partitions that are S P1.0 and partitions that < pp.1, For convenience, we adopt the following definitions:
1. For any partition P such that P S Pl.00 define
MP = {Q 3P E P such that 1Q= M1p) - PP..
2. Given any P < P1.0 and for each P E P. let MP represent part MP where
1Mp M1p.
Next, we will build collection of partitions p for 2 0 and 0 S s S starting with p0,0
{{1), (2).....(9)) and establishing the relationship illustrated by the diagram below.
p0.0
P
N
22,0
N
p3.0
N
P4.0
SC
p11
p2.
p3.1
p4.
SC
+
p2.
>
P3.2
N
P1.2
SC
+
p3,3
P1.
SC
p4,
( (In the above diagram, P Q indicates that Q = .P: Q
P indicates P = Psc(Q).)
SC
Indeed, the initial definition of p0,0 and the relation diagram determine the collection of partitions completely. Let us summarise it as statement:
Lemma I.15, There exists a unique collection of partitions (Pr*) that satisfies the following properties: For S <,
1. p0.0 ((1), (
2. pra < pP.00
3. pratt MP
4. pr+1,s prss
5. pr+1.- Psr(P
Proof of Lemma 1.15 The proof is proceeded by induction. We assume that P is constructed and uniquely determined for < To and r for some ro 0 that satisfies the properties described in the lemma.
We will define the partitions in the next column (Pro.e [pro.*)eejonn) ee(( by starting with pro Psc (Pro-_..r)))))
Besides constructing the rest of partitions, we also need show that these partitions satisfy the following list of conditions let us denote it as List A): For E r0. -1],
1. Pro. < P1.00
2. pro.s < 1, for E 10 1].
3. pro.st1 M
68

---

By definition of the map Psc, the first and second condition in the list are satisfied for ro 1. Relying on Pro-fo-1 1 < Pl.0, we can define Pro.ro M. Hence, the third condition the list is also satisfied for rp 1.
It remains to construct pre. for 10, 2] and they satisfy those conditions in the list. This can be proceeded inductively starting from 8 = To - 2.
Claim: For E 10, - 2]. if Pro.et1 < P pro-1 then there exists unique partition pr which satisfies the conditions List A for s.
Suppose the Claim holds. With Pro:ro-1 & pr0-1.70-1, we could apply the claim repeatedly and the lemma follows. The rest of the proof show the claim holds.
Let us assume pro.e+1 < pro-Let1 for some [0 2]. First, from our assumption on (Prs) for s To - 1, P 1.0-1,s+11 _MMMPr-- 1, By Corollary L.14 P 1,0-1,+111 S pll, Since prestt < < we conclude that p pl..
P
Applying Corollary I.14 again, we know there exists an unique partition P < P1:0 so that Pro,s+1 MP. We set P = P. In particular, the choice of p is unique in order to satisfy the first and third condition from the list.
It remains to show that Pro.* also satisfies the second condition in List A. Notice that from Corollary I.14 the induced map of M on partitions preserves S relation. Hence, pro.st1 pro-11s41 implies 1 < pro-1.s, Therefore, the claim holds.
Proof of Lemmal I.4
We start with the proof on the = implication. Suppose f is a function satisfied the first condition described in the lemma.
Since f(x.) is a function of (a)( this is equivalent to
E Var (f(Xx) X [wr(w]]
Relying on the identity Var[Y] = IEVar[Y Y [] + Var [E[Y [1] and (Xp=(u): (ppr()::pr--ypp Xp-- X.) Ks)is is Markov Chain,
E Var (X(x) xpr E Var [f(x)) [pr(ii]]
for E [r]. which in turn implies [x[((..) (p) conditioned on Xpr (u) a constant function for each s [r]. Equivalently, _ takes the same value for all elements in each S; for [g].
Hence, 1E [e(var[f(X.) [xp
Claim: For [r), if can expressed in the form f ΣpEp 1. 1l then it can be expressed in the form f = EpEP pp.
Clearly, the claim holds, then we can apply it repeatedly to draw the conclusion that f is linear combination of 1p for P Pel pr:
Now, we fix [r] and assume - 1, Then,
[[[(X.) Xpr a]
Σ P.P
Σ
Ca- 1,-1,
PEP
where for each / 10-100 ps-1 ps-1,s-1 is the corresponding part such that Ms-11p 1 1p-11 1. In other words, M is linear combination of 1p for P E p
Because M takes the same value not only for all elements in each S; for E [g]. but also for all elements in each P for P E 1s-1,--1 1,s-1 each P' (sc(P==---
implies M= f takes the same value for all elements in
ps..-1
Together with the fact that the induced map of M on partitions preserves & relation, we conclude that Ce-1,P; Ce-1.P% for P1, Pa E p8-1,0 whenever Pt and P2 are both contained in some P E p=.0
69

---

Equivalently, within each P E ps.,, f is constant function. Hence, we can express f as linear combination of 1p for P ps...
For the = implication, suppose f is a linear combination of 1p with P E pr,
What we need to show is for E [0, 11, M takes the same values for all elements in each S; for E .gl. From the chain pr.b + P + + prr and by (188), for 8 [0,r - 11. M f is
linear combination of 1p with P E pr...
Since p*+1,* Psc (bP < Pl.0 and p 2 implies . f takes the same values for all elements in each S; for E [q). Therefore, the proof is completed.
pr we have P < p which
Now, it remains to prove the second statement of the lemma.
First, if there exists r N such that pnd is trivial. Then p is also trivial for > since Pro & Pr. Hence, it is enough to show the existence of r such that pr.0 is trivial, 00 is trivial.
From the assumption M, knew that the stationary distribution of M satisfies min T() 0 and M converges entry-wise to the matrix whose row is identically и. Therefore, for sufficiently large r, min (M") 0.
Now, let us fix such and assume pro is not trivial. Let express p PP ..... Pr:") with for 8 E [0, and k 2 2 where the index is assigned so that P/ MP First,
MP for s E [r] and E [ky]
1 pm M rr..
With 1 pr. is non-negative and not zero, every component of M M' pr [a]. which contradicts to the assumption that por is non-trivial.
pro is non-zero. This forces
1.2 A basis of functions from [q] + IR according to the partition
From now on, let ro be the smallest non-negative integer such that p is trivial. Consider the collection
(P, 5) s [0,ro], P p=ed
We will establish identification between elements of the set described above and words whose alphabet consists neg-tigetive integers. This identification is constructed through induction, following these steps:
First, we identify (lg), with the word (1).
Assuming that elements in {(P, ( P E p=+1.01 have already been identified with unique words,
proceed follows: For each (P,s 1), suppose there are A pairs of (P', s) such that P P. We identify these l pairs with the words (w, i) for E [0, 1]. in any order of preference. For each (P',s), s), due to ps.0 is finer than equal to 1,+ there exists an unique pair (P, + 1) so that C P. This guarantees the above procedure assigns each (P', 8) unique word.
We denote the of words described above W, and adopt the notation (P, s) to indicate that (P,s) 8) associated with the word w. For given w E W, we represent the corresponding pair as (Pws rww),, where r(w)= + len(w).
Now, let make the following observations
1. If w E W is a word with len(w) < ro + 1, then (w, E W.
2. Each sP)s) corresponds to word of length + 1-
3. Suppose w, w/ W such that w is prefix of w. Then, Pw C Pw.
70

---

Let Tw be the tree defined on W using the prefix relation. In this tree, edges are drawn from w' to w r((') r(w) + and Pw, S Pwr Now, we will select q parts from these elements (P; s) based on their corresponding words.
Lemma 1.16. Let W S W be the subcollection of words which end with a positive integer. Then, [W] 9-
Proof. First of all, there are exactly q words W with length r+ since p0.0 ((i))xe() has parts. For each E [g). let w/ be the word corresponding to ((t),)) 0) and let w; be the longest word ending with a positive integer so that is either prefix of equals to w/. This is well-defined since every word in W is word starting with 1.
The proof of the lemma follows if we show the following claim: W1, W2....g Wy are distinct and are all words which ends with positive integer.
To prove the claim, we begin by showing w, o w; whenever i o Suppose = w, for some distinct pair i.j E [g]. Let be the longest prefix of w1, w/. necessarily we have w, = w, is either prefix of w w itself. Further, the length of w is less equal than r, since otherwise it implies w/ = -wj, which is contradiction.
Now, let (w, e.) and (w.e,) e,) be the two words which are prefix of w/ and w/. respectively. From the definition that w is the longest common prefix, e; and e, are distinct non-negative integers. Since W; a prefix of (w, e;), necessary that e; = O, otherwise violates the definition of w,. For the same reason, ej = 0. Therefore, we reach contradiction.
The remaining part to prove the claim is to show that (wi are all the words in W ending with positive integer. Suppose w is a word in which ends with positive integer. If len(w) < + 1, we keep fill 0 until its length is 1 and denote the resulting word by w'. Observe that w/ E W. Together with the length of w' is + 1, necessarily w' = w/ for some i. Recall the definition of w, we conclude w,. Therefore, the claim follows.
Lemma L.7. For any given S r' T, suppose Wp := {w W r(w) = r'} con-empty. Consider linear combination Emew. cw. If it can be expressed as linear combination of 1p for E pr'+10 then Cw are identically O.
Proof. Let Wi,..,, Wk. be the words with r(wx) = - 1 and corresponding to each part of pr'+1,0 Then, the words that corresponds to pairs of the form (P,r') with P E pr are
{ ((we )EEE))))eE(
where tą are non-negative integers. Now, we express
Σ
Lr Σ
Σ tElko]tE(tt)
C(we,t) I Poweas)"
wEW.
For each E [ko] and any E Pu we have
C(wga)) o 1 Pom (0)
Σ ((mx,t) Pomper) (0).
E[kok tEltyrl
tE(tu]
Therefore, Ewew,, Cp can be expressed as ExEjko) Owe 1mm if and only ErE(ta) (mma) a constant on Pun.
For each k E [ko], let 0 E 0) then we have
Σ Σ (( 1 Pingria (0) Σ C(mr.)) ( L (0) 0,
('E sE(twr)
tE(te)
which forces C(wy.t) = 0 for every > 0 (if it exists). Therefore, the proof is complete.
Definition 1.18. Let B = (Ewlwew be collection of functions from [g] to R. defined as follows:
71

---

1. Ifw = (1), Ew 1p. =1
2. If w + (1),
(w( = 10 - Pp (Y)).
Remark 1.19. The remaining goal in this subsection show that B the desired basis described
in Proposition 1.5 We also remark that the first two properties stated in Proposition 1.5 are already
satisfied with this construction: argmax
(1) with E() [o] Ew (x,) a function
of X where (u)
Lemma 1.20. The collection B forms a linear basis for functtions from [g] to
Proof. Since there are exactly q functions, our goal is show
RR jo = span( (ww))
and the R.H.S. is the same span( (1 hwew). It suffices to show for each i E [g], (()) can be expressed as a linear combination of 1,, with w E W.
To prove this statement, we will use induction, showing that for from ro to 0, each 1p with P EE p can be expressed as a linear combination of of 1p, with w E W. Since p0.0 {(1),..., {4) the proof follows once establish this inductive statement.
First, when т. since [g] the only part in pro.0 and [q] = P(1)- the statement holds for ro-
Now, suppose the inductive hypothesis holds for s+1 with ro- Pick any PE ps:0, let w (w',t) be the word associate with (P, 8). t = 0, then
1 1p - E' 1pm
where the sum is taken over all parts P" E PP. contained in Pw. Each p" in the summation (if exists) must corresponds to word of the form (w',t") with t" > 0, equivalently (w', e W. From the induction hypothesis, 1p, is linear combination of 1p, with w E W. Therefore, we then W, and
conclude that 1p also linear combination of 1p, with w W. If the same conclusion follows immediately. With no restriction on the choice of P, the induction hypothesis holds for 8 as well.
Therefore, the lemma follows from induction.
Lemma 1.21. For any given r' < r, suppose W, == {w W : ([()=r)) is non-empty, Then, there exists constant C 2 1 (which could depends on M) such that the following holds: Let u, T be two vertices such that p" (u). We have
EVar Σ
cwEw( X
Xp(n)]
2 C
max lcwl)2 wEW,
(109)
wEW,,
Proof. First, both sides of (109) scale by a factor h? if every term e, is multiplied by h E R. Hence, it suffices to establish the inequality in the case
max |cwl = 1. weW,,,
Given this, consider the set {cw)wew,, maxwew,, /owl = C W.,, is compact set and
VVar E Σ cuEm((u)) X.] Xp(e)
(110)
wEW..
is continuous in (Cw) wew,, (it is polynomial of cw). By compact argument one can estalbish the existence of C described in the lemma for every (Gw) )wew,, with maxwew,, |ow| 1,
EVar E Σ
cwew(XWw)
X.]
X Xp(e) > 0.
WEW.
72

---

We can simplify this by observing that
Σ weW,
CwSw
Ow pp + constant,
wEW,
and hence,
EVar
E Σ
Xo]
Xp(o) - -BVar E Σ
cwlp, (Xu) Xp(v]
Xu]
(111)
wEW,
weW,
=EVar
Σ
cw (X Xptw)
weW,
where the second equality follows from that Ewew, Cw P. (X.) is function of X, by Lemma I.4
Moreover, to show EVar Emew,, cwlp, (Xu)
Xp(w)
> 0, this is the same as showing
Σ cw (Xu)
wEW
is not function of X p(()- By Lemma 1.4 this is equivalent to show Σwew, Cw is not linear
combination of 1p for P E pr'+1, which was proven in Lemma [.17 Therefore, the proof is complete.
Lemma 1.22. For any given 0 S r' r, suppose Wer == {w E W r(w) < r'} non-empty.
Then, there exists 1 that the following holds: Let u, U. be two nodes such that = p" (u). We have
EVar E
Σ
CwEw (X.) X.]
X
$ SC( max lc,l))² WEW ce!
(112)
WEW
Proof. The proof is more straightforward compared to the arguments presented in the proof of Lemma 1.21 First, both sides (112) scale by a factor h²2 if we scaled each ew by h E R. Therefore,
suffices to establish the inequality when
EVar
Σ
Cw [x.] Xptw)]
WEW
there no (cw)wew.rr satisfying the above condition, then the proof is completed. Now we assume this set not empty. Notice that EVar E P[E (wSw((X)) X,] Xp(v) is a continuous function of (ow)weWerr which takes value O when (ow)weWerr Ō. Thus, there is open ball B C TW centered at such that for (sw)wew, E B, Σ (X,) [x.] Xp(u)] <
EVar
WEW
On the other hand, by choosing C sufficiently large, the set
(cw)wew,
max WEW
(cul)) 1/C].
which is the cube of side length 2/C1/2 centered at Ö, is contained in B. Therefore, the lemma follows.
Proof of Proposition 1.5 From Remark I.19 and Lemma 1.20 remains to show B satisfies the last
3 properties stated in the Proposition.
As for the third property. notice that the variance of Σwew cwE (X,) is not zero as long as ow are identically 0 for w & Wu. Following the same arguments in the proof of Lemma 1.21 the property follows if C 2 1 is sufficiently large.
The last follows by applying Lemma I.21 and Lemma 1.22 every 0 < r' and choosing the constant C' can be chosen to be the maximum of those constants C' from the two lemmas.
73

---

1,3 Proof of Proposition L.1
In this subsection, we consider soley degree polynomial of the leave values.
Definition 1.23. For any given p' 'T' and a degree-I polynomial f of {Iu (uut, the function can be expressed uniquely in the form
f(x)
E
CwruEw(a (X.u)
(113)
WEW, NEL,'
where (Ewl is the basis introduced in Proposition L.5
Observe that from this definition, for each For u Twi, let fa(x) ,eE., (w,nEw((t)) 0 S 1 r.
f(z)= = E fu(x).
WET, :b(w)=)
Further, for u E Ty Lpp, let
Σ
Cas, as
Cm.v.
vE
Remark 1.24. From the definition above, for each pf E T and degree-1 polynomial f of variables (au we have
Vu E Tpr, Vx E R2, (Bufu)()) = Σ Cw.usw (Iu):
where (2)( is introduced in Remark L.6
Proposition I.25. There exists constant C = C(M, d) 2 so that the following holds: Suppose
f(x)
Σ
HELP,
where p' T is node satisfying h(p') S ro and
Cu,u Cu,o
for E Lp satisfying h((u,, v)) S r(w), where p(u, v) is the lowest common ancestor of u and Then,
Σ
NEL
If Proposition 1.25 is proven, then Proposition
I. follows as corollary:
Proof of Proposition I.I Reduction h(p') < ro: Without loss of generality, it is sufficient to consider degree functions of L, rather than degree functions of variables Dz(u) for some u in the tree and 0 < t/ < h(u).
Recall that
Dr. (p) = tw T h(w) = ro).
We know that we can express f(x) = EmEp, (n) fw) so that each of them a degree-1 polynomial with variables (zu JwEL..
Together with the variance decomposition for degree-1 polynomials (See Lemma
Varls(X)] Z Σ EVar(fw X
wED,
suffices to prove the same statement for degree-1 polynomials of xn with u E Top for p' satisfying h((p)) ro-
74

---

Now, we fix such p' and consider
f(x)=
E W.NET,
Gw.uSw(Fu).
Averaging the Coefficients: For each 21, 02 E La.
W and for each Dr'w) know that for any
(w(,,,) = (m()))
almost surely. As consequene, have
Ener, Co. (x(X
E DEL.
Σ
Trul
vEL.
almost surely. Now, we repeat this averaging process for each w W and for each E Dr(w) (p').
We denote the resulting function by f. While and may not be the same function, f(X) f(X) almost surely. On the other hand, is a function which satisfies the condition in Proposition 1.25
Following from the proposition, have
Σ
EVar[fu CRLEVar((()) Xx] Va)) [xp]
WET.
The proof is complete.
Let us begin with an intermediate step toward the proof of the Proposition 1.25
Lemma 1.26. Suppose is function described in Definition I.23] For any given S l < such that Wi = {w E W r(w) = 1} is non-empty. Let u E Tp with h(u) = r(w). suppose
1. max |Cw.ul >> 0. wEW;
Then one of the following statement holds:
Either Vaa (IE.. (
Auin f2, or 2Ca
/fTmin t.
max=eW Cw.al
2Co
Here, Co 2 1 is the constant C described in Proposition I.5 and Tiin minoelyi T()).
Further, in the case when 1 = 0, then simply have EVa [ (E.. (Xx) Xp(w)] 2 1
Proof. We decompose (Z) into three components:
(Eufa(x))
Σ w:r(w)<l
Cu Cw (Iu) +
Cu,aSu ell (Iu) +
C (!)) (Nu),
(w)
wor(w)>d
where ( is introduced in Remark L.
For each w with r(w) > I, ( (Xu) is function of X, with v e= pr(w)-((u). Hence, the last compo-
nent En Ewerwwss Sw (Ix)) is constant function whenever condition on Xp(u)- Consequently,
EVar (BwFF) [p(w)] EVar
Σ
Car (Xx) +
cl1
Σ
Cu. = (Xx) Xp(w)]
ell)
w:r(w)<t
w:r(w)=l
(114)
From Proposition L.5
we know that
12
EVar
Σ
Cw,a
ell) (Xu) X Xp(u))
2
(115)
Co
(w)
75

---

where the constant Co is the constant C' stated in the Proposition. Intuitively, from (15) it should be clear that if the R.H.S. of (144) is small, then EVar Ewer(w)et CuraS (Xw) Xp(m)) cannot be small. Let derive this with coarse estimate.
By (15), we know there exists 0 E [q] such that
1²
Var
Σ
Cwreru (Xu) Xp(u) =0
Co
W (w))
Now, suppose Var Emir(w)ert Su (Xa) Xp(u) =
Lh 30%"
We could apply triangle inequal-
ity to get
Var
Σ
GuuuS ell (Xa) (Xaa) +
Σ
CwyuSw (Xa)
Xp(u) =
w wir(w)<l
(wr(w)=l
Var
Σ
CwjaS (Xru)
(
Xp(a) =0)
Var Σ
Cw (Xa) Xp(x) = 0)
W wir(w)=l
wir(w)<t <l
20%
and together with (14).
(Ear((B.) Xp(w)] (a)
Σ wir(w)<[
Cw,u cll) (Xu) +
Cw, uw
cl0) (Xu) Xp(w)
w:n(w)=l
Tmin ,2.
2C
Consider the opposite case where Var
(1)) (X,) Σ Emer(w)et Cunuuu
X Xp(u)
1² First,
10%
EVar
Cu, ell) (Xw)
X Xp(x)=
mmin 42 4Co
W :r (W)
By applying the 4th property stated in Proposition 1.5 we conclude that
Tuiin
max Cw.al w:r(w<<
20%
In the when 1 0. The argument is simpler, which follows directly from 114 and the Proposition [.5
Let = max,, MEL, lowaal and let w/ W and u' Lo be the pair such that to = |Cwt,er Further, let to r(w') and pt p'(n').
Proof of Proposition L.5
If 0, then we have
low mo! =
Iowrol 2 1ow sul = lo:
vEL.
where the first equality follows from the assumptions of the coefficients. We will try to construct sequence of triples (4,, tx, ux) indexed by & such that (4))20 is strictly decreasing such that Wi, + 0, h((u)) = lx. and la = maxwew,, |0w, I-
Suppose we have triple (lk, tk. ux) such that la 2 O, h(ue)) = 4. Wie * 0. and to maxwew,, /cw,ua for some index 2 0.
We apply Lemma 1.26 to get
1. Either EVar (E.,, for (Xuue) Xp(uus)]
Tmju
20g
76

---

2. ca /cw.uel
Amnin
(This case cannot happen if & 0.)
If the first case is true, then we terminate the process of finding next triple (1x-1: tk+1, Mk+1).
If the second is true, let w" W be the vertex such that Jow'r maxweWee (Cauul and set f = r("".. Since
Cw,uk
Cw,u:
oE DEDi (Mx)
we have
1++1
maa NETog :h(x) Exi1
Gwaal
Rdc Ex+s
|Cumull
Rdc -f411 lk-
(116)
Further, let ux+11 argmax,ET,, h(u)=fe+1 low,ll-
In this way, we produce new triple satisfying the same assumption as (4x, (k. us) described above. Since to > I > 12... is monotone decreasing chain of non-negative number, it means this argument must terminated in ro steps. Now, suppose it terminates at the k-th step, resulting a triple (lk, th uk), and
EVar (Bu. (X Xp(mml
min
116
Tinn
Tmin Rd)
2ro 22
2CD
20%
2C,
On the other hand, from Proposition
I.5
Σ
Var[fa(X,)] S CR.
Therefore, we conclude that
Σ
Varlfu(Xx)] S C(M, ((X))
MEL
Properties of Markov Chains and Galton- Watson Tree
J.0.1 Proof of Lemma A.5
Recall that real Jordon Canonical form of M is diag(J JJ,...,JJ, J,,) for some $1 S q.
q diagonal block matrix J
Since M is ergodic, the eigenspace corresponds to eigenvalue is I-dimensional. Thus, We may assume Ju [1] is the unique Jordan block corresponds to eigenvalue 1.
X
For each E [1, J, is either m, x m, matrix of the form J.
for some Ag IR satisfying Aal < x; or a Jo is a 2m, x 2m, matrix of the form J,
T R, I
R,
cos(())) sin(O.) cos(O.) sin (0.)
where Dad S X, and R.
is a rotation ma-
l R.
trix in IR2 with parameter 0g (0, 2m). In the later case, corresponds the conjugate pair of eigenvalues (coos((),) + iis)n).))
77

---

According to Jordon Decomposition, there exists an invertible matrix P such that M = PJP-! For i [1, 9 - 1], let be the i 1th column of P. Because P is invertible, (di)eeyl form linear basis of functions from [4] to I.
Since is a left-eigenvector of M with eigenvalue we have
Ey By~+o:(Y) Φ = O,
because @ is a sum of up to two generalized eigenvectors with eigenvalues not equal to 1.
(A generalized eigenvector v with eigenvalue of M a vector which satisfies (M X) v for some positive integer k. Whenever X + 1,
e = (1 - x)2 a T (M- - X3 (MM-x)9pe (1 X) T -
index i corresponds to J, which associated with a real eigenvalue, then Φ; is a generalized eigenvector with eigenvalue A;: And if J, associates with complex conjugate pair eigenvalues, then Φb a sum of two generalized eigenvectors with eigenvalues A. (cos((0.. (0.) + isin(0.)) and (f,) s0,)), respectively. ) As consequence, every function f [q] + R can be uniquely decomposed the form
f= Efff
Σ
8,0,
(117)
KE(A-1
With this unique decomposition, let define semi-norm
|lfll
max 16,/- sEl4-1]
Lemma J.1. There exists > 0 so that every f : [q]
11 S Vary (f(Y)) = Cl
(118)
Proof. Without lose of generality, let f = Eie(2.0) S,0. since both |[ and Vary=x(f(Y)) are invariant under a constant shift.
Let D diag(m TT. ..... Tq). Also, let 8 8= (0, 60,, 84). Then,
Il =1101|<
and
Vary~a =ō P D.Pă.
Let mmx and 8min be the maximum and minimum singular value of PT D2 P. respectively. Together
with 1/21|8112 I |1 =0 < |8]|22 we have
2 a 11 2 1|01 s Vary (f(Y)) muax 11012
52 2 Il
(119)
8min > O, then we can complete the proof by taking C = max 4/ 2 remains to show that Smin > 0, or equvialently PT D is invertible. Because M is ergodic, each entry of is positive, and thus D,, is invertible. Hence, PT D, is invertible because is product of three invertible matrices.
Lemma J.2. There exists 0 so that for every f [g] R.
C-1Ilfl S |lf Ey (Y) S Cllfllas
(120)
Proof. This simply follows from both M and || Eff are both norms on the finite dimensional space { lq] R Ey f(Y) 0}.
Lemma J.3. There exists C' 2 depending on M such that For any function f [g] + and k e N,
|| fllM S Ck* C1
(121)
78

---

Remark J.4. Notice that M can be interpreted as
[[x(X X (pr(w) = = (M*
for every u where (u) is well-defined.
Proof.
[| AI =I]
Σ xE(g]
deee)ll = (|J Σ
Sze;) S max sE(2.g] 1.jE(2,0]
|6:ll max [
(122)
2E(2.0]
Notice that _ is the diagonal block matrix whose blocks J for & E [81]- The block J can be computed directly: In the when J, corresponds complex conjugate pair of eigenvalues,
X ARR2
R
(m--1) -- m. R m
1
J
(123)
1A N
where treat ( Of k. It can be verified directly by induction, relying the identity (+=)+ ( Further, removing the Rg terms in the above equation we obtain the formula for J when J. corresponds to real eigenvalue.
Therefore, with ()) < A9, Ag S X", and max,, Rai < for r 2 1, we obtain the bound
max max (J, )osl S C² .{[2.]] (JE(
(124)
where C" is constant which depends q and X. Now we substitute the above bound into 122 to get
|| fllm s 'C'
The proof is completed by taking - -C'.
Proof of Lemma A.S The proof of Lemma A.5 follows from the || 1|lr decay from Lemma J.3 and that both Var and |l (Lemma J.I and Lemma
Ef ol are comparable to || within constant multiplicative factor
79

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] [NA]-
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA] is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best judgment and write a justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claim in the abstract and introduction is Theorem 1.6] The appendix is dedicated to the proof of the theorem.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The result is theoretical result which justifies low degree hardness for the tree reconstruction model. This is first indication that Kesten-Stigum bound appears to be the computational-statisiiee barrier for the problem. In terms of the limitation, the paper does not recover the same result as shown in the paper of Kohler and Moseel 23 where they only deal with the case O.
Justification:
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
80

---

Justification: The paper provides full set of assumptions and the appendix is dedicated to the complete proof for Theorem 1.6
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The result in the paper is a theoretical result. The paper does not include any experimental results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification: The result in the paper is a theoretical result. The paper does not include any experimental results.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The result in the paper is a theoretical result. The paper does not include any experimental results.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The result in the paper is theoretical result. The paper does not include any experimental results.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification:
The result in the paper is a theoretical result. The paper does not include any experimental results.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper conforms with the NeurIPS Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
The result of the paper is a theoretical result, which suggests a previous known bound (Kesten-Stigum) likely a statistical-compune compptiiolllommptttiioonaallllll bound for the tree reconstruction model. It is an generic result that suggest it is hard to design efficient algorithm for the problem below the Kesten-Stigum bound. On the other hand, the result does not have any direct societal impact.
Justification:
81

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The result in the paper is a theoretical result. The paper does not process and realease any data or models.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not existing assets.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
82


Reviews:
[{"review_id": "5UmO4XIZHc", "reviewer": "Reviewer_d9ko", "summary": "This submission considers the broadcasting on trees problem, where given a rooted tree, information is propagated from the root to the leaves using a Markov process. The algorithmic task is to infer the information at the root given only the information at the leaves. Previous works had identified that the KS-threshold (a threshold based on the spectral gap of the Markov process and the degree-structure of the tree) is the critical threshold when this is possible information-theoretically in some specific cases. However, in general it is not the right information-theoretic threshold, i.e., in some cases inference is possible even below it. The submission gives evidence that it is indeed the right threshold however when considering computationally bounded algorithms. In particular, it establishes hardness in the low-degree framework below the KS-threshold.", "questions": "No questions.", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Previous work had asked the question whether the KS-threshold is the correct threshold for efficient algorithms. This work answers this question in the affirmative. The ideas used in the proof are novel and clever.", "weaknesses": "The first part of the introduction is a bit hard to follow for non-experts, maybe some additional context would help.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mzsZ286KlU", "reviewer": "Reviewer_j6Pu", "summary": "This paper obtained low degree hardness results for broadcasting on trees (BOT). \nThe BOT problem is as follows. \nConsider a rooted tree and an associated Markov process defined by a transition matrix $M$. \nThe process is initialized by a distribution on the root. \nThen for each vertex with state $s$, its children are i.i.d. according to the $s$-th row of $M$. \nThe goal is to infer the state of the root given all leaves. \n\nThis paper shows that below the Kesten--Stigum threshold, any polynomial of the leaves of degree at most $\\log N$ fails to recover the root state. \nThis is particularly interesting since for some channels the KS threshold is information theoretically sharp and therefore they exhibit a stat-comp gap.", "questions": "I'm not familiar with this literature but I did try to check some of the cited papers to get a sense. \nThe result of this paper is certainly above the bar. \nHowever, there's (big) room for improvement of the presentation. \nIn fact, given the relevance of BOT and low-deg, upon proper revision of the exposition, the authors may want to send this paper to a journal instead. \n\nMajor comments: \n\n1. A related work section at the level of technique (i.e., low-deg) is needed. \nTo balance the space, the authors may want to reduce some parts of Sec 1.1 which are quite standard. \n\n1. Do the notions of $\\mathcal{B}(\\mathcal{A})$ and fractal capacity exist in the literature, or did the authors introduce them?\nIt's better to make it clear since the mere definitions of these are a nontrivial contribution IMO. \n\nMinor comments: \n\n1. Line 9, what do you mean by \"high level of complexity\"? It was just mentioned that BP runs in linear time.\n\n1. Line 10, at this point, it's not even clear what \"chain\" means. Please try to make the abstract self-contained. \n\n1. Line 20, based on. \n\n1. Line 22 doesn't parse grammatically. \n\n1. Line 22-25, please provide references. \n\n1. I don't understand line 37. Why compare low-deg **algorithms** to SoS **lower bounds**?\nAlso, what does \"easy to use\" mean?\n\n1. Line 40, [36] doesn't seem to involve AMP. Do you mean https://arxiv.org/abs/2212.06996 ?\n\n1. Line 42, \"broadcast on trees\" or \"broadcasting on trees\"? Please unify the terminology. \n\n1. Line 47, What do you mean by \"a linear estimator in the number of leaves\"?\nThe estimator is a linear function of the leaves? \nOr it runs in linear time as a function of the number of leaves?\n\n1. Line 54, our --> out\n\n1. Line 56, does \"sufficiently many states\" mean $q\\ge C$ for $C>5$? If so, it's better to make this clear. \n\n1. Line 60, broken reference. \n\n1. The discussion in line 54-61 is written in a chaotic way. \nPlease reorganize the relevant existing results. \n\n1. Line 68, leaves of for \n\n1. I don't understand the point of line 67-70.\nIs the message that for **small** $d$, large degree polynomials fail, but for **large** $d$, efficient reconstruction is possible?\nIn any case, these lines can be made more clear. \n\n1. Line 93, the notation $T$ hasn't even been introduced, so no need to abuse it. \n\n1. Line 96, begin with define\n\n1. Line 126, the notation $X_A = (X_v)_{v\\in A}$ hasn't been defined so far (correct me otherwise). \n\n1. Could the authors comment on the equation between line 139-140?\nIt says that conditioned on the root, the variance of (a low degree function of) the leaves will drop drastically (exponentially in depth). \nThis seems to imply that $f(X_L)$ is highly correlated with $X_\\rho$ and the correlation is **increasing** with the depth. \nApparently my interpretation is very wrong and contradicts the main message of the paper. \nCould the authors remark on why this is the correct statement to prove and how this implies Corollary 1.8?\n\n1. Corollary 1.8: Please define the correlation $\\mathrm{Cor}$. \n\n1. Line 146, \"the main result is optimal in the fractal sense\". This is interesting. \nCould the authors expand on this (maybe after the fractal capacity and stuff are properly defined later)?\n\n1. Line 154, the font of $b_1, \\dots, b_k$ changed. \n\n1. Definition 1.11, to make sure I understand it correctly, $\\mathcal{B}(\\mathcal{A})$ is **not** the closure (under decomposition) of $\\mathcal{A}$, right?\n\n1. Line 171, for $i$ for $i$\n\n1. Line 178, redundant line between end of proof and $\\square$. \n\n1. Definition 1.14, an $\\mathcal{A}$-polynomial\n\n1. Line 193, $2$-ary --> binary\n\n1. Line 194, eigenvalue --> eigenvalues\n\n1. Line 199, including in cases\n\n1. End of page 6, comparing to --> compared to\n\n1. The last equation of page 6 is unnecessary. \n\n1. Equation in line 202, is last $\\lesssim$ simply $=$?\n\n1. I(1), what is $S$?\n\n1. I(2), what is $S'$? In fact $S'$ is not even used in I(2). \n\n1. Line 229, What is $X$? I don't think $X$ is the whole tree?\nAlso, there's a missing right parenthesis. \n\n1. Line 230, satisfies --> satisfy. \n\n1. Line 234, \"builds on this strategy\", which strategy? This sentence feels out of place. \n\n1. Equation above line 242, what is $\\mathcal{J}$?\n\n1. Line 242, whose variables is --> are\n\n1. Below line 244, $x_{x_{\\le w_1}}$. \n\n1. Line 252, will also holds --> hold\n\n1. Equation above line 262, the argument of the function is included on the LHS but not on the RHS of the equation. \n\n1. Somewhere near the end of page 9, the font of $h_{\\mathcal{A}_k}$ changed.\n\n1. Not that it matters, but I don't think the authors used the latest version of the NeurIPS template which has a more tedious checklist.", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "NA", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sHYKrVWppO", "reviewer": "Reviewer_Pvza", "summary": "The paper shows that for a Markov process in a tree, propagating a starting state at the root to the leaves it is \"hard\" to infer the starting state from the leaf states. \nConcretely they show that for any function $f$ of the leaf states with bounded Efron-Stein degree the variance of $f$ conditioned on the root state is bounded by a function of the total variance of $f$. That is, the output of such a function varies relatively little with respect to the choice of the root value which means that little can be inferred about the root value from the leaf values.\nIn particular since bounded degree polynomials have bounded Efron-Stein degree this implies that any low degree polynomial of the leaf values can not be correlated with the root, i.e. as tree depth goes to infinity the correlation goes to zero.This holds even for cases where it would be possible to recover some information about the root, so the result really does imply some bound on the power of low-degree functions.", "questions": "- p2,l60 there is a broken reference\n- On page 6 the application of the CS-inequality has a typo in the final term, it should be $i\\in [m]$ below the sum\n- p7,l203: of in a Markov Chain -> of a / in a \n- p8,l229 there is a missing \")\" before the first square", "limitations": "No Limitations, this is theoretical research first and foremost", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper shows a very nice result, and I feel like the overview in the main body gives a good idea of how the proof of the result proceeds.", "weaknesses": "There are no real weaknesses to the paper, however due to space constraints it is not really possible to ascertain the claimed results from the main body of the paper. I could not check the appendix carefully.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k8g8h7Wdax", "reviewer": "Reviewer_8xrJ", "summary": "The authors study hardness of broadcasting on trees for low degree polynomials. The main result shows that log(N) degree polynomials of the leaf values have vanishing correlation with the root, resolving the main open question of Kohler and Mossel (NeurIPS 2022).\n\nThe tree broadcasting problem consists of a $d$-ary depth $\\ell$ tree T (or some relaxation thereof), an ergodic Markov chain $M$ over state space $[q]$, and a starting root distribution $\\nu$ over $[q]$. The broadcasting process starts by drawing $j \\sim \\nu$, then `broadcasts’ a value to every child in the tree based on the transition matrix $M$. This is repeated $\\ell$ times until the process terminates when it hits all leaves. Roughly speaking, the broadcasting problem asks whether it is possible to infer the starting value at the root given the values at the leaves of the tree given by the above process.\n\nThe most basic algorithm for tree broadcasting looks at linear statistics of the leaves, e.g. count statistics of how many times each state in [q] appears. There is a well-known threshold for linear algorithms called the Kesten-Stigum bound which states that such inference is possible if and only if $d\\lambda^2 < 1$, where $\\lambda$ is the 2nd largest eigenvalue of $M$. It is a natural (and known open) question whether this bound continues to hold against *low degree polynomials* of the leaves. This work answers this question in the positive for polynomials up to degree $\\log(|T|)$: all such functions have vanishing correlation with the root.", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Broadcasting is a well studied and useful model. The question of how well low-degree statistics of the leaves correlate with the root is extremely natural mathematically, and is supported by a number of recent works showing the general power of low-degree polynomials in predicting statistical-computational gaps. The only known bounds for this general problem were for the very specialized $\\lambda=0$ case.\n\nThe techniques introduced by the authors, including the notion of fractal capacity (a more involved proxy for low degree functions that aids their proof), and the resulting inductive method for low-degree (low fractal capacity) functions may be of independent interest. As the authors note, it is one of the first methods for dealing with strongly non-product structures in this context, which is a very frequent barrier throughout related areas (e.g. analysis of Markov chains, boolean function analysis, etc).\n\nThe authors give a nice overview of their method in the symmetric linear case that is easy to follow (though a bit dense with the notions of fractal capacity introduced before this overview). Moving to the low-degree case requires highly non-trivial modifications of this method, but the intuition given there is very helpful.", "weaknesses": "I do not see any substantial weaknesses in this work. \n\nOne could of course ask for lower bounds against super-logarithmic degree polynomials as in known in the $\\lambda=0$ case, but the results in this paper still mark a major step forward on this problem.\n\nI would request the authors run a grammar/syntax check. There are a huge number of typographical/syntax errors that slow down the reading of the work to some extent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper answers a natural open problem regarding efficient algorithms for broadcasting on trees. The reviewers agree that the technical contribution of the paper is substantial and clearly above the NeurIPS bar. The only doubt I have is that this paper seems better suited for a theory conference (like STOC or FOCS) than for an ML conference. On the other hand, some of the cited related work appeared in ML venues, and none of the reviewers seemed bothered by the choice of venue, so I recommend acceptance. The reviewers pointed out many places where the presentation quality is suboptimal, and I expect the authors to work on this aspect of the paper for the camera-ready version.
Decision: Accept (poster)