Reconstruction on Trees and Low-Degree Polynomials
Authors: Frederic Koehler
Elchanan Mossel
Venue: NeurIPS 2022 Accept (2022)
Keywords: kernel
polynomials
lower bounds
computational and statistical gaps
statistical query
belief propagation
graphical models
theory

Abstract: The study of Markov processes and broadcasting on trees has deep connections to a variety of areas including statistical physics, graphical models, phylogenetic reconstruction, Markov Chain Monte Carlo, and community detection in random graphs. Notably, the celebrated Belief Propagation (BP) algorithm achieves Bayes-optimal performance for the reconstruction problem of predicting the value of the Markov process at the root of the tree from its values at the leaves.

Recently, the analysis of low-degree polynomials has emerged as a valuable tool for predicting computational-to-statistical gaps. In this work, we investigate the performance of low-degree polynomials for the reconstruction problem on trees. Perhaps surprisingly, we show that there are simple tree models with $N$ leaves and bounded arity where (1) nontrivial reconstruction of the root value is possible with a simple polynomial time algorithm and with robustness to noise, but not with any polynomial of degree $N^{c}$ for $c > 0$ a constant depending only on the arity, and (2) when the tree is unknown and given multiple samples with correlated root assignments, nontrivial reconstruction of the root value is possible with a simple Statistical Query algorithm but not with any polynomial of degree $N^c$. These results clarify some of the limitations of low-degree polynomials vs. polynomial time algorithms for Bayesian estimation problems. They also complement recent work of Moitra, Mossel, and Sandon who studied the circuit complexity of Belief Propagation.  As a consequence of our main result, we are able to prove a result of independent interest regarding the performance of RBF kernel ridge regression for learning to predict the root coloration: for some $c' > 0$ depending only on the arity, $\exp(N^{c'})$ many samples are needed for the kernel regression to obtain nontrivial correlation with the true regression function (BP). We pose related open questions about low-degree polynomials and the Kesten-Stigum threshold. 

Reconstruction on Trees and Low-Degree Polynomials
Frederic Koehler" Stanford University Ekostler@sstanford.eee
Elchanan Mossel
Massachusetts Institute of Technology e Ammo@mmitend
Abstract
The study of Markov processes and broadcasting on trees has deep connections to a variety of areas including statistical physics, graphical models, phylogenetic reconstruction, Markov Chain Monte Carlo, and community detection in ran- dom graphs. Notably, the celebrated Belief Propagation (BP) algorithm achieves Bayes-optimal performance for the reconstruction problem of predicting the value of the Markov process at the root of the tree from its values at the leaves.
Recently, the analysis of low-degree polynomials has emerged as valuable tool for predicting computational--t -o-stttittittt gaps. In this work, we investigate the performance of low-degree polynomials for the reconstruction problem on trees. Perhaps surprisingly, we show that there are simple tree models with N leaves and bounded arity where (1) nontrivial reconstruction of the root value is possible with simple polynomial time algorithm and with robustness to noise, but not with any polynomial of degree N for с > a constant depending only on the arity, and (2) when the tree is unknown and given multiple samples with correlated root assignments, nontrivial reconstruction of the root value is possible with simple Statistical Query algorithm but not with any polynomial of degree N These results clarify some of the limitations of low-degree polynomials vs. polynomial time algorithms for Bayesian estimation problems. They also complement recent work of Moitra, Mossel, and Sandon who studied the circuit complexity of Belief Propagation. As consequence of our main result, of independent interest regarding the performance RBF kernel ridge regression for learning to predict the root coloration: for some d' depending only the arity, exp(Ne' many samples needed for the kernel regression obtain nontrivial correlation with the true regression function (BP). We pose related open questions about low-degree polynomials and the Kesten-Stigum threshold.
able to prove a result
Introduction
Understanding the computational complexity of random instances has been the goal of an extensive line of research spanning multiple decades and different research areas such as cryptography, high- dimensional statistics, complexity theory, and statistical physics. In particular, this includes work on satisfiability and refutation of random constraint satisfaction problems and on computational- to-statistical gaps. In much of this work, evidence for computational hardness is indirect because there are well-know barriers to proving hardness from classical worst-case assumptions such as
"Supported in part by E. Mossel's Vannevar Bush Faculty Fellowship ONR-N00014-20-1122 NSF award CCF- 1704477 NSF Award IIS-1908774, and Anari's Sloan Research Fellowship. Part of this work was completed while at MIT and while participating in the program Computational Complexity of Statistical Infer- ence at the Simons Institute for the Theory of Computing.
SSppported by Simons-NSi NSF collaboration on deep learning NSF 20M8-003883, by Vannevar Bush Faculty Fellowship award ONR-N00014-20 1-2826 and by a Simons Investigator Award in Mathematics (622132)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

NP-hardness (Feigenbaum and Fortnow 1993; Akavia et al. 2006 Bogdanov and Trevisan 2006 Applebaum al. 2008).
Recently, low-degree polynomials have emerged as a powerful tool for predicting computational-to- statistical gaps. cumpputational-tosttatiin mial time algorithms to estimate a desired quantity of interest from the data, even though compu- tationally inefficient ("information-tthorrtti""" algorithms can succeed the same task. Heuristics based on low-degree polynomials have especially been used in the context of Bayesian estimation and testing problems and partially motivated by connections with (lower bounds for) the powerful Sum-of-Squaree proof system. More specifically, a recent line of work (e.g. Hopkins and Steurer 2017| Hopkins 2018 Kunisky et al. 2019; Bandeira et al. 2020; Gamarnik al. 2020) Holmgren and Wein 2020; Wein 2020; Bresler and Huang [02T] Mao and Wein 202T) showed that a suitable "low-degree heuristic" can be used to predict cemputational-statiiii
gaps are situations where it is impossible for polyno-
gaps for a variety of prob- lems such as recovery in the multicommunity stochastic block model, sparse PCA, tensor PCA, the planted clique problem, certification the rero-temperature Sherrington-Krrte planted sparse vector problem, and for finding solutions in random k-SAT problems. Furthermore, was observed that the predictions from this method generally agree with those conjectured us- ing other techniques (for example, statistical physics heuristics based on studying BP/AMP fixed points, see e.g. Decelle et al. 2011 Deshpande and Montanari [015 Mohanty et al. 202I). Some of the merits of the low-degree polynomial framework include that is relatively easy to use (e.g. compared to proving SOS lower bounds), and that low degree polynomials capture the power of the "local algorithms" framework used in c.g. (Gamarnik and Sudan 2014] Chen al. 2019) as well as algorithms which incorporate global information, such as spectral methods or a constant number of iterations of Approximate Message Passing (Wein 2020).
model, the
In this work, we investigate the power of low-degree polynomials for the (average case) reconstruc- tion problem on trees. We define the model and results in the next sections, but first give an informal summary. The goal for reconstruction on trees is to estimate the value of the Markov process at the root given its value at the leaves (in the limit where the depth of the tree goes to infinity), and two key parameters of the model are the arity of the tree d and the magnitude of the second eigenvalue Ag of the broadcast chain. Importantly, when 2 > 1 it is known (Kesten and Stigum 1966) that nontrivial reconstruction of the root is possible just from knowing the counts of the leaves of differ- types, whereas when 2 < such count statistics have mutual information with the root (but more complex statistics of the leaves may) Mossel and Peres 2003 This threshold d| d|A2|² = is known the Kesten-Stigum threshold (Kesten and Stigum 1966 and it plays a fundamental role in other problems, such as algorithmic recovery in the stochastic block model (Abbe 2017] and phylogenetic reconstruction (Daskalakis et al. (006). Count statistics can be viewed degree polynomials of the leaves, which begs the question of what information more general polynomials can extract from the leaves.
In this paper, we answer this question in the limit case A2 = 0. Perhaps surprisingly, we find that the Kesten-Stigum threshold remains tight in the sense that even polynomials of degree N for small c > are not able to correlate with the root label (Theorem 6 whereas computationally efficient reconstruction is generally possible as long as d is a sufficiently large constant (Theorem 5 and even when a constant fraction of leaves are replaced by noise. Building on the polynomial lower bound, we prove superpolynomiallyy (in fact, subexponentially) many samples are needed for Gaussian Kernel Ridge Regression (KRR) to (weakly) learn to regression function which predicts the root from the leaf colorations (Theorem 20 This gives a simple and natural model where KRR provably fails that is outside the reach of existing lower bounds such as (Kamath et al. 2020
We also consider an analogous question where the tree is unknown, and the algorithm has access to m i.idd. samples of the Markov process where the root is biased towards an unknown label Y*. In this setting, polynomials of degree No again fail correlate with the label Y but we show that a simple algorithm, straightforwardly implementable in the Statistical Query (SQ) model (Kearns Together, these results show that low-
1998). can recover Y in polynomial time (Theorem degree polynomials behave very differently in our setting than one might intuit based on previous work in related settings, such as in random constraint satisfaction problems or the block model.
2

---

1.1 Preliminaries
Notation. We use the standard notation (a(+) to denote an upper bound with an implied constant which is allowed to depend a; the notation poly, a (-) is similar for denoting bound which is poly- nomial in its parameters. We let drv (P, Q) denote the total variation distance between distributions P and Q normalized to be in [0. 1] and we use Y Z) for the conditional mutual information of random variables X, Y conditional on Z: see (Cover 1999). Given a vector x and a subset of coordinates S, we let gg denote the dimmennnsll vector corresponding to elements of S.
Markoy processes on frees. We consider Markov processes with state space Σ [g] (1.....q) of where q 2 1 is the size of the alphabet. Let M : :q x be the transition matrix of a homogenonge Markov chain on E, also referred to as the broadcast channel. For simplicity, we always assume henceforth that M is ergodic (irreducible and aperiodic, see (Durrett 2019)) so has unique stationary distribution TM. Let T (V, E, p) be rooted tree with vertex set V. root E V, and where E is the set of directed edges (u, v) where u is the parent of v in the correspond- ing tree. The broadcast process on tree T of depth with transition matrix M and root prior v probability measure on [g] is given by
(t,(()): == ((5p))
M Ma..a." (N.D)E
II
When not otherwise indicated, is the stationary distribution for M. The probability measure μ is a Markov Random Field on the tree T. This means that if A, B are subsets of the vertices of T and all paths in T from A to B pass through third set of vertices S, then XA and Xg are conditionally independent given Xg. This is called the Markov property, see e.g. (Lauritzen 1996). In this paper, focus on the setting of complete d-ary trees (i.e. trees where every non-leaf node has d children. and all leaf nodes are at the same depth). For the d-ary tree of depth E 2 O, we let L be the set of leaves of the tree, i.e. the set of vertices in the tree at depth l.
Definition 1. We say that reconstruction is possible on the dlarr tree with channel M if
inf max drv (Ln, Xx = (XL X, c)) >0 E21 c,et
where the notation C,,(X) denotes the conditional law of X under μ given event E' occurs, μe is the corresponding broadcast process on the depth tree with root p and L Le is the set of leaves.
When reconstruction is possible, the Bayes-optimal estimate of the root given the leaves can be computed in linear time by passing messages up the tree using the Belief Propagation algorithm (Mezard and Montanari 2009); for our purposes, we will not need the explicit formula for BP, which can be derived by applying Bayes rule, but refer the interested reader to the reference.
Given a matrix M, we let (M) denote the second-largest eigenvalue of M in absolute value. The Kesten-Stigum (KS) threshold on the d-ary tree is given by the equation d 222 (M) = 1. Building upon the original work of (Kesten and Stigum 1966). it was shown that the KS threshold is sharp for the problem of count reconstruction on trees (Mossel and Peres 2003 count reconstruction is possible when di (M))) > 1 and impossible when di (M)) < 1.
Definition 2. Let Cxx) := (# x4 = cf)ce(al be the function which computes count statistics of an input vector x with entries in (4] We say that ceunt-reconstruuction is possible on the d-ary tree with channel M if infes maxx,e'E(g) (Tv(L,,(C(Xi)) ) | X, c), Lue (C(Xz) Xx = d') > 0 where the notation EE denotes the conditional law of X given event E, μr is the corresponding broadcast process on the depth tree and L Le is the set of leaves on this tree.
Next, we define notion of noisy reconstruction which plays an important role in this paper:
Definition 3. For 10, we say that e-noisy reconstruction is possible on the d-ary tree with channel M if infe>1 max.,d (Cue = Xx, c), (X', = X, c()) > 0 where X" the e-noisy version of the broadcast process values X, generated by independently for each vertex v, setting (X1)), = (XL), with probability 1 - and otherwise sampling (XL)) from Uni
MMore generally, results hold where the noise is from any full support distribution on [g].
3

---

Note that in this definition, the law of XL X, can equivalently be written as Lu (X Xx e)T' where T. is the usual noise operator that independently resamples each coordinate of its input vector with probability 6, see e.g. O'Donnell 2014, Hopkins 2018 Finally, we recall from (Janson and Mossel 2004) the following standard definition: we say that robust reconstruction on the d-ary tree with channel M is possible if c-noisy reconstruction is possible for every E (0, 1).
gaps. As discussed in the introduction, low degree polynomials have been studied in wide variety of contexts and settings. The recent work (Schramm and Wein 2020) showed that a version of the low-degree polynomial heuristic can predict the recovery threshold for natural Bayesian estimation problems, even when the recovery threshold below the detection/testing threshold. In the present work, we will use the following key definition from their paper
Low-degree polynomials and computational-stttiste
Definition (Degree- Maximum Correlation (Schramm and Wein 2020 Suppose that (X,Y) ~ P where X is random vector in R and Y is random variable valued in R. The degree-) maximum correlation is defined to be
sup Eplf(X) Y
CP
Ee v [x
where R[ D is the space of degree at most D multivariate polynomials in variables X1...., XN
with real- coefficients.
As explained there, when the target label Y* is vector this definition can be applied with Y equal to each of the coordinates of Y We note that we could rephrase our results in terms of a testing problem (as in much of the prior work the low-degree method), but the above definition is more natural in our context (it avoids the need to introduce a "null distribution" Q)- In what follows, we omit the distribution P the expectation is taken over long it is clear from context.
Instead of referring to polynomial degree directly, we usually use the following more conve- nient and equivalent definition. Suppose f is function [s]" + R. We define the (Efron- Stein) degree of I to be the minimal D such that there exist functions Is : [g]|S] + IR so that f(z) = Esc())ss &D fs(ss). One such minimal choice of fs is the Sfron-Stein decomposition over U Uni[ul", see e.g. (O' D'Donnelll20 22014b; this notion is also equivalent to the minimal degree poly- nomial representing f where the variables are the one-hot encoding x + (1(z, = ())
Reconstruction below the KS threshold. In this paper, we will largely consider the problem of tree reconstruction with matrices M with A²(M) O; these exactly correspond to Markov chains which mix perfectly within a bounded number of steps. (There are many examples of such chains, for concreteness we give a very small example below in Example
Obviously, for such a chain M, d|Aa|² = 0 for any value of d so such a model is always below the Kesten-Stigum threshold. Nevertheless, based on general results from existing work know that near-perfect reconstruction of the root is possible (e.g. using Belief Propagation, which computes the exact posterior distribution This is true as long as is sufficiently large, and even with a constant
(Mezard and Montanari 2009
amount of noise E:
Theorem (Mossel and Peres 2003, Theorem 22 below). Suppose M is a the transition matrix of Markov chain with pairwise distinct row i.e. for all i, [q] the rows M; and Mj are distinct vectors. Let E (0, 1) be arbitrary. There exists do = do(M. 8) and such that for all 2 do, c-noisy reconstruction is possible on the d-ary tree and furthermore there exists polynomial-time computable functtioo f fM.E valued in [q] such that
max Pr(f((() + X, x)=c)<b eE[g]
where X₁, is the e-noisy version of Xt. (see Definition 30.
This exact statement does not appear Mossel and Peres 2003 but follows from arguments pre- sented there; for completeness, we include proof in the appendix (Theorem 22 From the proof, we can see that very simple recursive estimator is enough to solve this problem.
'In our notation X and y are swapped compared to theirs. to match the convention in the broadcast process. 'This condition is needed to rule out the case of e.g. rank one matrix M where reconstruction is clearly impossible. See also (Mossel and Peres 2003) for more complex and precise condition.

---

1.2 Our Results
We study the power of low-degree polynomials for the problem of reconstructing the root of a Markov process. We consider this question in the context of two very closely related versions of the model which have both been extensively studied in the literature.
Reconstruction with a known free. In this setting, the algorithm is given access to the leaf values from single realization of the Markov process, and the goal is estimate the root (where are going to be interested in estimators which are low-degree polynomials of the leaves). The tree structure known and the estimator/polyoomial allowed depend on this information directly.
Reconstruction with an unknown tree. In this setting, the data is still generated by a complete d- ary tree but the tree (in other words, the true ordering of the leaves) is unknown to the algorithm. This version of the model has been extensively studied due to close connections to the problem of phylogenetic reconstruction in biology, see e.g. Felsenstein 2004 Daskalakis et al. 2006, Steel 2016 Because this task is more difficult m i.i.d. samples from the broadcast model; we give more precise definition of the model below.
ly the algorithm is given access to
Results for reconstruction with a known tree. We consider the problem of tree reconstruction with matrices M with (MM = O; these exactly correspond to Markov chains which mix perfectly within a bounded number of steps. As discussed above in Preliminaries, while such models are always below the tions on M the reconstruction problem is still solvable for d sufficiently large (Theorem (5). This is true even with noise and with very simple reconstruction algorithm. As main result we show that despite the algorithmic tractability of this problem, only very high degree polynomials are able to get any correlation with the root, in the same sense Definition 4
threshold for any value of the the arity d, under fairly weak condi-
Theorem 6 (Corollary 15 below). Let M be the transition matrix of Markov chain on [gl and suppose that S k S is such that M is a rank-one matrix. For any function f [gl + R of Efron-Stein degree al most 21e/Ok-1)] of the leaves Xr. and any prior v on the root,
B(f(XE) (1(Xp c) 100--vee v(c))] =.
Remark (Tightness). For fixed h, this result tight up to the base of the exponent. When M satisfies the assumption of Theorem 5 there is function on a constant-degree subtree to recover the root and (by Fourier expansion) this is a polynomial of degree e())
To interpret this result, observe that N = d', so taking d a constant, the Theorem shows that poly- nomials of degree even No for explicit constant e = c(d, R) > 0 fail get any correlation with the root label. In comparison, in the previously mentioned contexts in the low-degree polynomi- als literature, the threshold for polynomials of degree Olog N) matches the conjectured threshold for polynomial time algorithms (see e.g. Hopkins and Steurer 2017] Hopkins 2018 Kunisky et al. 2019) and polynomials of degree N correspond to conjectural thresholds for subexponential time algorithms (see e.g. Ding et al. 2019 Bandeira et al. 2020)
A consequence: subexponential sample complexity lower bound for the RBF kernel. As consequence of our main result, we can analyze the behavior of kernel regression methods in our model. Kernel ridge regression is one of the canonical methods for solving supervised learning problems, including classification problems (see e.g. Muthukumar et al. 2021). In many high- dimensional settings, believed that the function learned using standard kernel (e.g. Gaussian or polynomial) is essentially a low-degree polynomial. Standard results in learning theory (Shalev- Shwartz and Ben-David 2014) imply that kernel ridge regression with Gaussian/RBE (Radial Basis Function) kernel in N dimensions can learn a degree l polynomial on the hypercube or sphere using roughly O(N') samples. Establishing lower bounds on KRR generally much harder. In certain particularly tractable settings (e.g. data from the uniform distribution on the hypercube) it has been recently shown explicitly that kernel regression (only) learns a low-degree polynomial (Ghorbani et al. 2 Mei et al. 1)
seems plausible to guess that kernel ridge regression with a standard kernel will require subex- ponentially many samples of (leaf label, root label) pairs in order to learn to predict the root. We
'Note that in the single-sample case (m = 1), the information available to the algorithm would only be count statistics, which we know are insufficient for reconstruction below the KS threshold (Mossel 2004
5

---

0.25
KRR RecMaj
0.20
Squared loss
0.15
0.10
0.05
0.00
0.05
0.10
0.15
0.20
0.25
0.30
lambda2
Figure 1: RBF Kernel Ridge Regression (KRR, blue line) test error in squared loss for predicting the root from leaves with data generated by broadcast operator Ma, := (1- M + / and varying Ag. Mo is from ( and can be directly checked that A2 is the second eigenvalue of Mx2- The tree is 10-ary with depth 3, and the prior is (0.5, 0.5, 0). RecMaj (orange dotted line) is baseline estimator which generalizes the one used proof of Theorem 5 Consistent with Theorem 8 the output of KRR fails to correlate with the root coloration when A2 0 (since 0.25 is the null risk, the squared loss for the optimal constant predictor), even though RecMaj correlates significantly with the root for all values of Ag. In fact, KRR fails to correlate for all values of A2 up to around 0.1, suggesting that the failure of KRR and low-degree polynomials should extend beyond X2 =
are able verify this prediction in the case of the popular RBF (Radial Basis Function) kernel. See Section C.I.I for formal notation and background on kernel ridge regression.
Theorem 8 (Theorem 20 below). Let M be the transition matrix of Markov chain on igl and suppose that < k < is such that M = ππェ is a rank-one matrix, and suppose that x has at least two nonzero entries. Then the for any color e [q] and prior for the root coloration Xp, the following is true. Given m i..d. samples (I1, B1)...., (Ims Vm.) from the broadcast model on the d-ary tree with N leaves and broadcast channel M, where x; one-hot encoded vector of leaf colorations and = 1(X, c) - v(c) is the centered indicator of the leaf coloration, we have that for any bandwidth a 2 0 and ridge parameter X 2 O, for w the output of ridge regression in RKHS space with those parameters and feature map s,, that with probability at least 1 -
Exo. (o (w. ((x)))) ((/1/N)
Ezo.go [V6]
provided that m/ö OeeN") where a = a(M,d) d) > 0 is independent of the depth of the tree.
This establishes a new and illustrative example where KRR performs poorly in high dimen- sions, even though the ground truth is a relatively "simple" and the labels are closely related to the structure of the input data. Note that the conclusion implies that E((y0 - (w, ( Z (1 - O(1/v(11)) E()()) i.e. kernel ridge regression does not significantly outperform the constant zero estimator ("null risk") unless it is given at least subexponential number of samples. Also, as with Remark / this result is tight up to the power of the exponent c, since a subexponential degree polynomial exists which predicts the root well and it provably be learned with subexponential number samples by KRR
and Ben-David 2014).
In Figure we test kernel ridge regression in simulation in both the case X2 0 and A > 0: consistent with our result, KRR fails beat the null risk when X = O; interestingly, it also fails for moderately small values of X2 as well, which is related to the Open Problem we discuss later. In the figure, KRR is performed using 2000 i.i.d. samples colorations and the centered indicator that the root color is 1, as in Theorem g Bandwidth and ridge penalty are selected via grid search on a validation set. The results for the baseline (RecMaj) averaged over 16000 samples.
(ar, 3) pairs with æ the one-hot encoded leaf

---

Results for reconstruction with an unknown free. Formally, we consider the following variant of the generative model which is variant of models in the phylogeneties literature. Briefly, in this model we generate m i.i.d. realizations of the broadcasting model, where the tree is random and the prior on the root biased towards a random root label. We include a parameter e 2 0 which can be used to add noise to the final output the of model, just as above.
Definition 9 (c-Noisy Repeated Broadcast Model on Random Tree), Let f 2 1, d 2 2, m 2 1.92 1, 2 0 and let M be a Markov chain on [g]. Define R- = M., by the following process:
1. Sample Y ~ Uni((q]), and 7 ~ Uni(SN) is a random permutation. Let T be the d-ary tree on the set of leaves ordered by T, e.g. vertices r(1) and 7(2) are siblings in T.
2. Sample ( ,..., ((m) i.i.d. from the c-noisy broadcast process (see Definition 3 on T with prior (2/3)ōy- + (1/3)Uni((q) and transition matrix M, where öy. is a delta distribution on Y*. Let X = x((")
The goal of the learning algorithm in the unknown tree model is this: given m samples of the leaves of the broadcast process, encoded in X, reconstruct the root label Y which the prior is biased toward We discuss the reasons for defining the model this way: The permutation T ensures that the coordinates of x-() behave in symmetric way, or equivalently that the order of those coordinates is not semantically meaningful: observe that if we omitted it, then the first d coordinates would always be neighbors in the tree. This is standard in the phylogenetics literature (Steel (206)) and this kind of symmetry is also assumed in the literature on low-degree polynomial hardness, see e.g. discussion in Holmgren and Wein 2020, in sparse PCA this is analogous to how the support of the planted sparse vector is chosen uniformly at random among size-k subsets. 2. The choice that root assignments are drawn from tilted/biased distribution is different from the previous literature motivated by phylogenetics, where the root value is generally sampled fresh each time. This does not have significant effect on how the algorithms used to estimate the tree work. The reason for our setup is to allow for straightforward comparison between SQ and low-degree polynomial models. the root value was sampled from unbiased measure each time, it would not make sense for an SQ algorithm to estimate it, since SQ has no concept of individual samples.
To be formal, we define the Statistical Query VSTAT oracle analogue of R in the usual way (Feldman et al. 2017). The oracle is defined conditional on Y* and the tree T, so the order of leaves in the tree will be consistent between different calls to the oracle. As reminder, vector-valued queries are implemented in the SQ model by querying each coordinate of the vector individually.
Definition 10 (V ST (T Oracle). Let Y*, T, T. and M be as in Definition 9 Conditional on
Y = y² and the tree T = l, we define (T) be an arbitrary oracle which given query function y [q] -> [o, 1). returns p- Eop where p = Ex(((((())) Y y" T f] where Gp is
arbitrary (can be adversarily chosen) such that |<p1 < max
P(1 D)
172
We now state our results in this model. Just in the known tree case, there is relatively simple algorithm which achieves nearly optimal performance in this setting when X² = 0 and is large constant, and furthermore this algorithm can straightforwardly be implemented in the SQ model described above. Establishing this requires proving a new result in tree reconstruction, since (for example) the setting (M) = O which we care about rules the use of Steel's evolutionary distance (see e.g. Steel 2016) Moitra 2018) commonly used in reconstruction algorithms in phy- logeny, as Steel's distance is only well-defined for nonsingular phylogenies. and some kinds of tree models with singular matrices are actually computationally hard to learn (Mossel and Roch 2005).
Theorem 11 (Theorem 30 below). Suppose M is the transition matrix of a Markov chain with pairwise distinct rows, iee. for all i, E [g] the rows M, and Mj are distinct vectors, and suppose X2 0. There exists d > 1 and >> 0 so that the following result holds true for the complete d-ary tree with any depth f 2 1. For any 8 >> O, there exist a polynomial time algorithm with sample complexity
polyss (log N, 1og(1/8)) from the e-noisy repeated broadcast model (Definition 9 5: 1) outputs the true tree T (equivalently, the true permutation T). 2) outputs y such that Y = Y Also, this algorithm can be implemented using a V AT((m oracle with m = polyM (log(N/5) (N))) and polynomially many queries.
which with probability at least
We could also consider the model where the root label is always Y The soft bias we consider is nicer for minor technical reasons, and seems natural given we allow to add noise elsewhere in the model.
7

---

The lower bound for polynomials also applies here, just like in Theorem 6 Since it is very similar, we leave the formal statement to the appendix (Theorem 27
1.3 Further Discussion
Related work: complexity of reconstruction on trees. Our work follows a line of previous work which identified the Kesten-Stigum threshold as a potential complexity barrier in the context of the broadcast model on trees. The work (Mossel 2016) showed that algorithms that do not use cor- relation between different features (named "shallow algorithms") cannot recover phylognies above the Desten-Stigum threshold, where other ("deeper") algorithms can do so efficiently; the motiva- tion in (Mossel 2016) was to find simple data models where depth is needed for inference. More standard complexity measures were studied in Moitra et al. 2020 who obtained a number of results on the circuit complexity of inferring the root in the broadcast process. They conjectured that be- low the Bestenn-Stigmm threshold, inferring the root is NC11ccopleee and proved it for one specific chain satisfying A2 = O. Although there are some connections between low-degree polynomials and certain circuit classes (Linial et al. 1993), the results of this work and (Moitra et al. 2020) are incom- parable and the techniques for establishing the lower bound very different. Finally, we note the algorithms on finite alphabets: they proved such algorithms fail recover all the way down the Kesten-Stigum threshold, even in the simplest case of the binary symmetric channel with g = 2.
work (Jain et al. (019) which studied the power of message-passin
Message passing vs. low-degree polynomials. One of the attractive properties of the class of low-degree polynomials is that it generally captures the power of constant (or sufficiently slowly growing) number of iterations of message-passing algorithms such as BP, AMP, and Survey Prop- agation (see e.g. Bresler and Huang 2021 and Appendix A of Gamarnik et al. 2020 which is interesting since a constant number of steps of these algorithms are indeed useful for many statisti- cal tasks. On the other hand, in our models, belief propagation (which computes the exact posterior) succeeds with high probability whereas low-degree polynomials fail. This is not contradiction: in our setting, BP requires (log N) iterations for the messages to pass from the leaves to the root and this is (as our main result shows) too large to simulate with low-degree polynomials.
SQ and Low-Degres Polynomials. The recent work (Brennan et al. 2021) established sufficient conditions for predictions to match between the Statistical Query (SQ) and low-degree polynomial heuristic, in a general setting. Nevertheless, in the unknown tree setting we consider above we saw that SQ algorithms perform significantly better than low-degree polynomials. The results of (Brennan et al. (202T) cannot be immediately applied to our setting, because we have phrased the problem as an estimation problem instead of a testing (a.k.a. distinguishing) problem; however, this is itself not the reason for the discrepancy as we could rephrase our problem in terms of testing the color of the root. Instead, the reason seems to be due to the "niceness condition" needed for their theory to apply. They show that the niceness condition will be satisfied for noise-robust problems when the "null distribution" in the testing problem is product measure. Our setup is indeed noise robust (see Theorem 5). However, if we rephrased our problem as testing one the null distribution will be a graphical model (with no bias at the root) and not a product measure.
Recently there has also been interest in understanding lower bounds against kernel learning algo- rithms (including polynomial kernels), in part motivated by connections neural networks, and this involves connections to the SQ framework. See e.g. (Kamath et al. (020) and references within. These methods can, for example, prove strong lower bounds against learning parities with kernel ridge regression since parities have large SQ-dimension. See also (Koehler and Risteski (018) for another example where polynomial degree lower bounds were established for a Bayesian inference task, though only polylogarithmic in the dimension.
Noise robustness and learning parities. It was shown in (Janson and Mossel 2004) that the KS threshold is sharp for robust reconstruction, where we recall from above that (by definition) robust reconstruction on the d-ary tree with channel M is possible if for all noise levels E (0, 1), e-noisy reconstruction is possible. At first glance, this appears similar to the idea in the low-degree polyno- mials literature that the model should be slightly noisy to rule out the example of learning parities (which can be solved in the noiseless setting by Gaussian elimination, but not when there is noise). In fact the two notions are quite different: the robust reconstruction result shows that reconstruction
8

---

becomes impossible for large noise levels e > 6, above a critical threshold c,, whereas for small (but fixed) >> 0 the e-noisy reconstruction problem often remains solvable - see Theorem [ Our examples are fundamentally different to the parity example: (1) for the unknown tree version of our model, we showed that the problem is solvable with an SQ oracle whereas parities are well-known to be hard for SQ (Blum et al. 2003), (2) relatedly, the algorithms which solve our problems are not "algebraic" in nature, and (3) our results hold irrespective of adding a small amount of noise, whereas learning parities with any constant amount of noise is conjecturally hard (Valiant 2012) Altogether, we can think of these results as suggesting a new, more nuanced picture of low degree robustness to noise. Whereas before the main dichotomy in the computational complexity of in- ference literature has been between zero noise and any noise, in our model reconstruction algorithms such BP can tolerate small amount of noise, but fail when the noise level crosses some critical threshold. At least in our setting with )2 M)] = 0, low-degree polynomials appear to capture the latter "large noise" behavior instead of the "small noise" difficulty of the problem.
Open Problem. What happens when (M) * O? It is natural to wonder if the Kesten-Stie SestennStigum threshold di >21² = is sharp for low-degree polynomial reconstruction, analogous to how it is sharp for robust reconstruction. Our main lower bound result (Theorem e is consistent with this intuition. Also consistent with this intuition, our simulation result Figure | suggests that Kernel Ridge Regression may continue to fail for small but nonzero values of (2 See Appendix for more formal statement and more discussion of this important question.
2 Technical Overview
The detailed proofs of all results are given in the Appendix. Here, we explain the high-level proof ideas, which we believe are relatively clean and conceptual.Befin proceeding, we give the following concrete example of a Markov chain Mo with (M)) and q 3:
0.5
0.5
00.55
0.5
0.257
Mo
0.25
0.5
0.25
M =
0.25
0.5
0.25
(I)
0.25
0.5
0.25
Since M2 is rank one, it must be the case that (M O.
Failure of low-degree polynomials (Theorem 6 We want to show that any low-degree poly- nomial of the leaves of the broadcast tree fails to correlate with the root. In general, it may be very difficult to compute the maximal correlation among all low-degree polynomials; what makes it possible in our case is that the correlation is exactly zero. If [q] a color and v is the prior at the root, we want to show [[f(X))(((X) = c) v(c))] = O. (Recall L is the set of leaves and Xt the leaf colorations.) The first step is use linear of expectation to break f(X) into monomials: more formally, if f(X) = Eisis fs(X) is the Efron-Stein decomposition for a polynomial of degree D, then to show the goal it clearly suffices to show
(X))(X))(((X, c) -0(]) = 0.
Crucially, the monomial fs is function which depends only on a set of at most D leaf colorations Xp. Therefore, the result follows if we can show those leaves by themselves are independent of the root coloration. This is shown by performing an iterative trimming procedure on the minimal subtree spanned by the root and the leaves in S: every time there is an isolated path of length k (where M is rank one: = in the example above) all information is lost from the start of the path to its end. Using this idea and some elementary combinatorics, we can prove that if [S] is small, the trimming procedure will delete everything, and so the root indeed independent of these leaves.
Failure of RBF Kernel Ridge Regression (Theorem polynomials result. First, we show that if the bandwidth parameter in the kernel is taken too small, then the output of Kernel Ridge Regression (KRR) is close to zero on new test point and so it fails to learn anything. Otherwise, we can directly show that any function with a substantial high degree polynomial component has large RKHS norm. We can also construct an interpolator of the training data which has much smaller RKHS norm, by showing that every training sample has a small "fingerprint" which uniquely identifies it and is detectable with low-degree polynomial. It then follows that whatever the output of KRR is, must have a small RKHS norm and cannot correlate with the true regression function.
This result builds on the low-degree

---

Success of noise robust reconstruction using "high degree" algorithms (Mossel and Peres 2003). We briefly explain why noise robust reconstruction is possible with simple and compu- tationally efficient algorithms. The key is to consider the case of a depth 1 tree: because the rows of M are distinet, if the degree of the tree is a sufficiently large constant, then by the Law of Large Numbers the empirical distribution of its children will be close to the row of M corresponding to the state of the parent, letting us reconstruct the parent with say 99.9% probability of success. Given this, it is not too hard to argue this argument works recursively and in the presence of small ad- versarial noise. Note that this algorithm recursively integrates global information on the tree across multiple scales in contrast, the lower bound used the fact that low-degree polynomials can only aggregate information between small sets of variables in limited (linear) way.
The lower bound for low-degree poly- nomials in this setting can be reduced to the previous low-degree polynomial lower bound, which leaves proving that efficient (and SQ) algorithms can successfully solve this problem. Once we construct the tree, we can run any algorithm for reconstructing the root given the leaves, e.g. the one described just above or BP. As far reconstructing the tree, we first explain how to reconstruct the first layer. We prove that the joint distribution of any two leaves has enough information to tell us if they are immediate neighbors, which determines the location of all of their parents in the tree (such a test is easy to construct if we look at the generalized eigenvectors of M). Now that the bottom layer of the tree structure determined. we use the fact that we have very good estimates of their parents colorations using the algorithm described before. Crucially, since that algorithm's 's accuracy guarantee for reconstructing the internal node's 's colors is very strong and does not decay as we go further and further up the tree, we can indeed apply this argument recursively to get the whole tree.
Unknown tree results (Theorem 1 and Theorem 27
Implementing this algorithmic approach in the SQ framework is straightforward: at the end of the day it is based on computing the joint distributions of pairs of (estimated) vertex colorations, and those are all averages over the data. On the other hand, note that this method very strongly relies on the ability of an SQ algorithm to make adaptive queries, since the queries made are based on the partially reconstructed tree structure, which is unknown to the algorithm before it starts.
References
Neyman, Jerzy and Egon Sharpe Pearson (1933). "IX. On the problem of the most efficient tests of statistical hypotheses". Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of Mathematical Physical Character 231.694-706 pp. 289-337.
Kesten, Harry and Bernt P Stigum (1 (1966). "Additional limit theorems for indecomposable multi- dimensional Wattonn processes". The Annals of Mathematical Statistics 37.6, pp. 1463- 1481.
Feigenbaum, Joan and Lance Fortnow (1993). "Random--elf--rddccciltt of complete sets". SIAM Journal on Computing 22.5, pp. 994-1005. Linial, Nathan, Yishay Mansour, and Noam Nisan (1993). "Constant depth circuits, Fourier trans- form, and Icarnability" Journal of the ACM (JACM) 40.3, pp. 607-620. Lauritzen, Steffen L (1996). Graphical models. Vol. 17. Clarendon Press.
Kearns, Michael (1998). "Efficient noise-tolerant learning from statistical queries". Journal of the
ACM (JACM) 45.6. pp. 983-1006.
Cover, Thomas M (1999). Elements of information theory. John Wiley & Sons.
Mossel, Elchanan (2001). "Reconstruction on trees: beating the second eigenvalue". Annals of Ap- plied Probability, pp. 285-300.
Blum, Avrim, Adam Kalai, and Hal Wasserman (2003). "Noise-tolerant learning, the parity problem, and the statistical query model". Journal of the ACM (JACM) 50.4, pp. 506-519. Mossel, Elchanan and Yuval Peres (2003). "Information flow on trees". The Annals of Applied Prob- ability 13.3, pp. 817-844.
Felsenstein, J. (2004). Inferring Phylogenies. New York, New York: Sinauer.
Janson, Svante and Elchanan Mossel (2004). "Robust reconstruction on trees is determined by the second eigenvalue". The Annals of Probability 32.3B. pp. 2630-2649.
Mossel, Elchanan (2004). "Survey: Information flow trees". arXiv preprint math/0406446. Mossel, Elchanan and Sébastien Roch (2005). "Learning nonsingular phylogenies and hidden Markov models". Proceedings of the thirty-seventh annual ACM symposium on Theory of com- puling, pp. 366-375.
10

---

Akavia, Adi, Oded Goldreich, Shaf Goldwasser, and Dana Moshkovitz (2006). "On basing one-w me- functions on uu-hardness".. Proceedings of the thirty-eighth annual ACM symposium on Theory
of computing. pp. 701-710.
Bogdanov, Andrej and Luca Trevisan (2006). "On worst-case to average-case reductions for NP problems". SIAM Journal on Computing 36.4, pp. 1119-1159.
Daskalakis, Constantinos, Elchanan Mossel, and Sébastien Roch (2006). "Optimal phylogenetic re- construction". Proceedings of the tighth- annual ACM symposium on Theory of computing, pp. 159-168.
Applebaum, Benny, Boaz Barak, and David Xiao (2008). "On basing bower-bounds for learning on worst-case assumptions". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE, pp. 211-220.
Mezard, Marc and Andrea Montanari (2009). Information, physics, and computation. Oxford Uni- versity Press.
Dembo, Amir and Ofer Zeitouni (2010). Large Deviations Techniques and Applications. Sppringrions.Spinggeer.. Artin, Michael (2011). Algebra. Pearson.
Decelle, Aurelien, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová (2011). "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications".
Physical Review E 84.6, p. 066106.
Valiant, Gregory (2012). "Finding correlations in subquadratic time, with applications to learning parities and juntas". 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE, pp. 1 11-20.
Gamarnik, David and Madhu Sudan (2014). "Limits of local algorithms over sparse random graphs". Proceedings of the 5th conference on Innovations theoretical computer science, pp. 369-376. Mossel, Elchanan, Joe Neeman, and Allan Sly (2014). "Belief propagation, robust reconstruction and optimal recovery of block models". Conference on Learning Theory. PMLR, pp. 356-370. O' Donnelll Ryan (2014), Analysis of boolean functions. Cambridge University Press.
Shalev-Shwartz, Shai and Shai Ben-David (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.
Deshpande, Yash and Andrea Montanari (2015). "Finding hidden cliques of size vN/e in nearly linear time". Foundations of Computational Mathematics 15.4, pp. 1069-1128. Mossel, Elchanan (2016). "Deep learning and hierarchal generative models". arXiv preprint arXiv:
Steel, Mike (2016). Phylogeny: discrete and random processes in evolution. SIAM.
Abbe, Emmanuel (2017). "Community detection and stochastic block models: recent develop- ments". The Journal of Machine Learning Research 18.1, pp. 6446-6531.
Feldman, Vitaly, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao (2017). "Sta- tistical algorithms and lower bound for detecting planted cliques". Journal of the ACM (JACM)
64.2, pp. 1-37.
Hopkins, Samuel and David Steurer (2017). "Efficient bayesian estimation from few samples: com- munity detection and related problems". 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, pp. 379-390.
Hopkins, Samuel (2018). "Statistical inference and the sum of squares method". PhD thesis. Cornell University.
Koehler, Frederic and Andrej Risteski (2018). "Representational power of ReLU networks and poly- nomial kernels: beyond worst-case analysis". arXivv preprint arXiv: / / 1405.
Moitra, Ankur (201 8). Algorithmic aspects of machine learning. Cambridge University Press. Vershynin, Roman (2018). High-dimensional probability; An introduction with applications in data science. Vol. 47. Cambridge university press.
Chen, Wei-Kuo, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman (2019). "Suboptimal-- ity of local algorithms for class of max-cut problems". The Annals of Probability 47.3, pp. 1587- 1618.
Ding, Yunzi, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira (2019). "Subexponential- time algorithms for sparse PCA". arXiv preprint 190.
Durrett, Rick (2019). Probability: theory and examples. Vol. 49. Cambridge university press. Jain, Vishesh, Frederic Koehler, Jingbo Liu, and Elchanan Mossel (2019). "Accuracy-memory tradeoffs and phase transitions in belief propagation". Conference Learning Theory. PMLR, pp. 1756-1771.
11

---

Kunisky, Dmitriy, Alexander S Wein, and Afonso S Bandeira (2019). "Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio". arXiv preprint arXiv: 1636.
Bandeira, Afonso S, Dmitriy Kunisky, and Alexander $ Wein (2020). "Computational hardness of certifying bounds on constrained PCA problems". ITCS. Gamarnik, David, Aukosh Jagannath, and Alexander Wein (2020). "Low-degree hardness of ran- dom optimization problems". 2020 IEEE 61st Annual Symposium Foundations of Computer Science (FOCS). IEEE, pp. 131-140.
Holmgren, Justin and Alexander Wein (2020). "Counterexamples to the low-degree conjecture". ITCS.
Kamath, Pritish, Omar Montasser, and Nathan Srebro (2020). "Approximate is good enough: Proba-
bilistic variants of dimensional and margin complexity". Conference on Learning Theory. PMLR,
pp. 2236-2262.
Moitra, Ankur, Elchanan Mossel, and Colin Sandon (2020). "Parallels Between Phase Transitions and Circuit Complexity?" Conference on Learning Theory. PMLR, pp. 1910-2946.
Schramm, Tselil and Alexander S Wein (2020). "Computational barriers to estimation from low- degree polynomials" arXiv preprint arXiv:2008.00 02269.
Wein, Alexander S (2020). "Optimal low-degree hardness of maximum independent set". arXiv preprint ar arXiv:2010.0653 066663...6
Brennan, Matthew Guy Bresler, Samuel Hopkins, Jerry Li, and Tselil Schramm (2021). "Statistical query algorithms and low-degree tests are almost equivalent", COLT. Bresler, Guy and Brice Huang (2021). "The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials". FOCS.
Ghorbani, Behrooz, Song Mei, Theodor Misiakiewicz, and Andrea Montanari (2021). "Linearized two-layers neural networks in high dimension". The Annals of Statistics 49.2, pp. 1029-1054. Mao. Cheng and Alexander S Wein (2021). "Optimal Spectral Recovery of Planted Vector in Subspace", arXiv preprint arXiv:2105.155
Mei, Song, Theodor Misiakiewicz, and Andrea Montanari (2021). "Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration". arXiv preprint
arXiv:2101.10588
Mohanty, Sidhanth, Siqi Liu, and Prasad Raghavendra (2021). "On statistical inference when fixed points of belief propagation are unstable". IEEE 62st Annual Symposium on Foundations of Com- puter Science (FOCS).
Muthukumar, Vidya, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai (2021). "Classification vs regression in overparameterized regimes: Does the loss function matter?" Journal of Machine Learning Research 22.222, pp. 1-69.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi-
ments multiple times)? [N/A] Error bars were computed but ended up being visually negligible because of large sample size
12

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] Only used trivial resources.
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "zSSiwCI-14j", "reviewer": "Reviewer_zt31", "summary": "This paper studies the problem of tree reconstruction on $d$-ary trees; the root of the tree is given a spin $X_\\rho \\sim \\nu$, which is then propagated down to the leaves according to a Markov channel $M$. The problem is then, given the spins $X_L$ at the leaves, to recover the original root spin $X_\\rho$. Several variants of this model are considered: with/without noise at the leaves, with the underlying tree known or not, or with several realizations of the same tree process.\n\nThe focus in this paper is on low-degree polynomial reconstruction: for which values of $M$ can $X_\\rho$ be estimated by a low-degree polynomial in the leaves, i.e. a function of the form\n$$ f(X_L) = \\sum_{S\\subset L, |S| = D} f_S(X_S) , $$\nwhere $X_S$ is the subset of leaves in $S$. It is already known that when $d |\\lambda_2(M)|^2 > 1$, a linear ($D = 1$) estimator suffices; on the other hand, general reconstruction using belief propagation is possible for almost all $M$.\n\nThe authors show that if $\\lambda_2(M) = 0$, then no polynomial algorithm of degree $\\leq N^c$, where $N$ is the number of leaves, can recover the true root spin. The proof is based on the property that $M^k$ is of rank 1 for some k, and hence the correlation between a vertex $x$ and its $k$-th ancestor is 0. As a corollary, they show that a kernel ridge regression method needs at least $e^{N^c}$ samples to learn the tree reconstruction problem, since it needs to approximate a polynomial of degree at least $N^c$.\n\nThe article also contains a positive result: for the case where the underlying tree is unknown (equivalently, where the leaves are known up to permutation), they show that for a fixed root spin $X_\\rho$ and a polynomial number of samples from the tree process started at $X_\\rho$, there exists a reconstruction algorithm that recovers $X_\\rho$ better than random chance.", "questions": "- In Fig.1, is it a one-off run or are the results averaged over multiple samples ? It seems weird that the RecMaj algorithm is so inconsistent depending on $\\lambda_2(M)$.\n- Can those results be extended to similar tree distributions, with the same growth rate ? For example, using the br(T) value of Evans et al. '00.", "limitations": "The limitations have been adequately addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The tree reconstruction problem is ubiquitous in many inference problems (e.g. community detection), for which computational-to-statistical gaps are still fairly unexplained. It's interesting to see a low degree polynomial approach to this problem, which bridges the gap between the census reconstruction problem and BP approaches. The paper is overall well-written and easy to read; the introduced notions are clearly defined (with the notable exception of the VSTAT oracle), and the results are nicely presented. It is especially interesting that the impossibility result extends to $O(N^c)$ degrees, although this might just be a consequence of $\\lambda_2(M) = 0$.\n\nThe main weakness of this paper, in my opinion, is its specificity: all proofs hinge on the specific properties that occur when $M^k$ is of rank one, which implies very string independence properties between tree nodes. The tree structure is similarly rigid, with only the $d$-ary tree considered. However, this is a good first step which I hope will inspire more work on this topic. ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "lK1RPfCR7sw", "reviewer": "Reviewer_APcw", "summary": "Investigates the problem of tree reconstruction (from leaves to root) through low degree polynomials.\n", "questions": "None.", "limitations": "The main limitation I can see is that the tree structure that makes this analysis go through is somewhat limited.\n", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Low-degree polynomials as a computational model used to study (in)tractability of learning/inference problems seems to be a useful and important model, so studying when it does/doesn't reflect the wider class of polynomial-time algorithms is very important. The results in this paper provide an important insight in this direction. The assumptions are pretty carefully justified, and the authors are largely working in standard models.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "krO3MHmJoE", "reviewer": "Reviewer_Rmuy", "summary": "This paper studies the problem of reconstruction on trees through low degree polynomials. The authors show that there exists simple tree models in which nontrivial reconstruction of the root value is possible in polynomial time, and if the tree is unknown but given samples with correlated root assignments, nontrivial reconstruction is possible with a statistical query algorithm. The paper also provide a result related to RBF kernel ridge regression for predicting root coloration. An open question about low degree polynomials and the KS threshold is also proposed.", "questions": "- Some acronyms are used without introduction, for example, MCMC and CSP.\n- It would be great if the authors could provide some high level interpretation of their results for those who are not familiar with this line of work.", "limitations": "Not applicable.\n  ", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The topic of this paper is completely out of my area, and any technical comments I make will probably be unfair to the authors.\n\nRegarding organization: I can hardly follow the paper. Partly it is because the topic is out of my area. However in the current shape, everything including introduction, preliminaries, definitions, theorems, remarks, are all mixed into the two massive sections. While I understand there might be a lot of contents in the paper, I think the presentation can definitely be improved. \n\nI also don't know what are the exact contributions in this paper. For example Theorem 5 (Mossel and Peres 2003) appears under Section 1.2 Our Results. Is it a new result, or from a prior work?\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cGpf3WOqVWa", "reviewer": "Reviewer_bRPZ", "summary": "This paper studies the effectiveness of using the restricted computational model class of low-degree polynomials for assessing statistical-computation gaps for high-dimensional statistical inference problems.  Using the problem of reconstruction on trees, the authors identify problem settings for which average-case reconstruction is impossible using low-degree polynomials yet reconstruction is possible with computationally efficient methods.  ", "questions": "N/A", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths (major)\n- significance: Information-computation tradeoffs for high dimensional statistical inference problems are important.  There are several restricted computational models that have been used to study gaps for different problems (planted clique, sparse PCA, etc.).  Low-degree polynomials are a prominent model.  The authors show that there are problems where thresholds identified using low-degree polynomials do not match thresholds for existence of computationally efficient methods.  \n- The extension of the lower bound to investigate when kernel ridge regression would fail is interesting.\n- The authors provide substantial discussions.\n\nStrengths (minor)\n- While work is theoretical, the authors include an experiment (Fig 1) investigate performance of low-degree polynomials for small but non-zero $\\lambda_2$, suggesting that the inaccuracy of low-degree polynomials to capture computational hardness may not narrowly occur on the limit case (of $\\lambda_2=0$) analytically studied in the paper.\n\nWeaknesses \n- I did not identify any major weaknesses.\n\nVery minor notes: \n- line 30, acronym CSP not defined\n- line 78 – the acronym for statistical query ‘SQ’ is used multiple times before being defined \n- Line 95 - Notation $c$ not introduced yet, why not $x_r$ for realization of root variable?\n- Line 103 – $\\rho$, a subscript appearing in the conditioning event, is not defined. \n- Lines 117 and 122 missing parenthesis\n- line 189 – a constant $c$ for $N^c$ is discussed, but that is different than the $c$ as the root variable realization, right? If so, I’d suggest not overloading notation.\n- line 210 capitalize ‘markov’\n- Line 212 should ‘Suppose that …’ be there?  Line 218 has a condition on $m/\\delta$ and in 212 the notation $m$, $\\delta$, $\\epsilon$, and $c$ not yet specified\n- Line 217-218, I don’t think the notation $\\varphi(\\cdot)$ was introduced yet\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept