On the inability of Gaussian process regression to optimally learn compositional functions
Authors: Matteo Giordano
Kolyan Ray
Johannes Schmidt-Hieber
Venue: NeurIPS 2022 Accept (2022)
Keywords: Gaussian processes
Bayesian nonparametrics
posterior contraction
minimax estimation
large-sample asymptotics

Abstract: We rigorously prove that deep Gaussian process priors can outperform Gaussian process priors if the target function has a compositional structure. To this end, we study information-theoretic lower bounds for posterior contraction rates for Gaussian process regression in a continuous regression model. We show that if the true function is a generalized additive function, then the posterior based on any mean-zero Gaussian process can only recover the truth at a rate that is strictly slower than the minimax rate by a factor that is polynomially suboptimal in the sample size $n$.

On the inability of Gaussian process regression to optimally learn compositional functions
Matteo Giordano" Department of Statistics
Kolyan Ray" Department of Mathematics Imperial College London
University of Oxford
matteo. sitieeo.giirdannssttttt.ssss ox. ww.p:o....ccuu... ak
kolyan. raySimperial ac.uk
Johannes Schmidt-Hieber Department of Applied Mathematics
University of Twente
a achmidt-hiieerruuteent .nl
Abstract
We rigorously prove that deep Gaussian process priors can outperform Gaussian process priors if the target function has a compositional structure. To this end, we study information-thcorede Gaussian process regression in continuous regression model. We show that if the true function is a generalized additive function, then the posterior based on any mean-zere zero Gaussian process can only recover the truth rate that is strictly slower than the minimax rate by factor that is polynomially suboptimal in the sample size n.
lower bounds for posterior contraction rates for
Introduction
Hierarchical methods are the heart of modern machine learning and provide state of the art performance for variety of different problems. While the role of the depth in deep neural networks has been extensively investigated [37 44 45 24 333, the theory underlying deep Gaussian process priors is still in its infancy. In this work we identify structured recovery problem for which deep Gaussian process priors are known to achieve near optimal behavior. By proving that for this problem any Gaussian process prior will lead to sub-optimal posterior shrinkage behavior, provide theoretical justification for the use deep methods for Bayesians.
Gaussian process (GP) priors are arguably the most widely used Bayesian nonparametric priors in machine learning. having found success multiple settings (26). Reasons for their popularity include their interpretability. ability to flexibly model target functions, model spatial or temporal correlations, incorporate prior knowledge such as stationarity, periodicity or smoothness, and their provision of uncertainty quantification. This work establishes information--teerreie bounds the inability of GPs to optimally model generalized additive models, thereby quantifying certain limitations of GP methods.
We will study the performance of GPs continuous analogue of nonparametric regression via quantifying the speed of posterior concentration/contrace frequentist assessment that measures the typical behaviour of the posterior distribution under the true generative model. The performance of Bayesian methods is known to be sensitive to the choice of prior, particularly in high- and
around the true regression function. This
settings
20 and therefore
All authors contributed equally.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

crucial to understand under what conditions and prior calibrations Bayesian inference is reliable. The frequentist analysis of Bayesian methods has become a standard tool for such tasks in both the
statistics and machine learning literatures ge 36 25
43 42
6
27
28 see the monograph [12].
Precise definitions and further discussion are provided below.
If the regression function is a generalized additive model, it has been shown that deep neural networks with properly chosen network architecture achieve the optimal minimax rate of convergence [32]. We show here that for this structural constraint, any mean-zero Gaussian process, irrespective of the choice of covariance kernel, will concentrate around the truth at a rate that is strictly slower than the minimax rate by factor that is polynomially suboptimal in the sample size Thus any posterior GP places a significant portion of its posterior probability on functions that are further from the truth in L L'-distance than the minimax rate of estimation, which has negative implications for both Bayesian estimation and uncertainty quantification.
In contrast, it has recently been shown that deep Gaussian processes 23 g which consist of iterations
of Gaussian processes and can be viewed Bayesian analogue of deep neural networks, are able to attain the minimax rate of contraction for arbitrary compositional classes (10). As these compositional classes contain generalized additive models as special case, we have shown that deep GPs provably outperform GPs from a statistical perspective and should thus be preferred.
In related work, it has been established that (not necessarily Bayesian) linear estimators can only attain polynomially suboptimal linear estimation rates over certain spatially inhomogeneous Besoy classes [9] for functions with discontinuities [21]. Agapiou and Wang [1] use the results of [9] to show that GPs also cannot concentrate faster than the linear rate for such Besov classes, see also 3I for some related examples. Castillo 4 establishes lower bounds for concentration rates in terms of abstract conditions on the 'concentration function"' of the GP, which can be verified for certain specific GP choices. The lower bound ideas of [9] 21 have also been extended to various spatially inhomogeneous and discontinuous functions settings to demonstrate the theoretical advantages of Finally, for generalized additive models, 32 shows that (possibly nonlinear) wavelet methods can only achieve suboptimal rates.
deep learning over linear estimators [15 34 35 38
Most of the above works exploit the results from 9 21 showing that minimax rates for linear estimators are slower than full minimax rates in these settings. Since linear rates are unavailable for generalized additive functions, and seem difficult prove using existing techniques, we instead use a different and novel proof approach. We exploit the specific structure of the GP posterior mean in regression construct direct lower bound for its prediction risk. In an effort to develop the new tools needed to solve such problems, we further provide second proof in the supplement that involves first reducing the regression setting simplified sparse sequence model in which we derive linear rates. While these do not imply linear rates in the full model we consider, they prove sufficient to construct lower bounds for arbitrary GP posterior means.
2 Main results
2.1 Problem setup and posterior contraction rates
In the usual multivariate nonparametric regression model we observe n training samples arising as
(Xi, Yi)..., (X,,
Y= f(x) +
We N 1),
(1)
where the design points X, are either independent and uniformly distributed random variables on [0, 1]2 or equally spaced lattice points in [0, 1jd. To simplify technical arguments due to the discretization and provide a clearer exposition, a standard approach in statistical theory is to consider instead the "continuous" analogue of this model [19. The discrete model (T) is asympiotically
equivalent (30 (as n + xc) to observing a realisation Y = y (Yz : x E [0, 1)d) of the multidimensional Gaussian white noise model
dY. f(x)dr + dW.. 2+
x 10,0
(2)
where ==
= (W,: : x E [0, 119) is a d-dimensional Brownian motion. For large n, the two models thus behave identically from statistical perspective.
2

---

Notation: For a domain D and p oc, denote by (D) the space of all measurable functions f D + I that have finite norm ( == (fl if < 0C, and are essentially bounded on D p co. If there is no ambiguity, write L for [0, 1]4 and (f.g)2 = fo.1j (u)g( for the corresponding imner product. Let P, P7 denote the probability distribution of Y Y arising from
(2 with corresponding expectation E.y.
We consider the Bayesian setting where we assign to f a (possibly n-ddppedent) mean-zero Gaussian process prior II II, on [0, 1J with covariance kernel K, i.e. II is a (Borel) Gaussian probability [0,
measure on [ 1 such that for f ~ II, we have
E f 0,
[[f()f(()) = ((x,)).
y.y [0,
The posterior (-YY) is then computed as usual using Bayes formula and is again GP by conjugacy. exactly as in the discrete model (I) (26). see 7 for the exact expression. We make the following
frequentist assumption:
Assumption 1. There is a true fo E 12 1]d generating the data Y ~ Pto according to
We study the behaviour of the posterior distribution II, (-YY) under Assumption in which case can be treated as random probability distribution whose (frequentist) randomness depends on Y. We next introduce the notion of uniform posterior contraction.
Definition 1. We say that the posterior contracts about fo rate en + uniformly over a sequence of classes Fn C = 11dh if as + 00
sup fo
F (J: -off-ollee 2 en () - O.
Posterior contraction is often stated in the equivalent form
II II foll 2 En.YY) +
in Ps probability
as 71 + 0o, which says that the posterior puts all but a vanishingly small amount of probability on Lalballs of shrinking radius en about the true fo generating the data [12]. We are typically interested in the size of the smallest such L-2-ball, i.e. the fastest rate e - such that Definition | holds. Such results not only quantify the typical distance between point estimator (e.g. posterior mean or median) and the truth, but also the typical spread of the posterior about the truth. Ideally, most of the posterior probability should concentrate the minimax estimation rate, see Section C. for more details. Indeed, since posterior contraction at rate en automatically yields point estimator with convergence rate (112), Theorem 8.7), the minimax rate provides an information-theoreti lower bound for En. Posterior contraction at a fast rate is necessary condition for statistically good Bayesian estimation and uncertainty quantification.
ball centered at the true fo with radius proportional to
We use the E expecttaiio formulation of contraction to quantify the uniformity over fo E F, needed to make our lower bounds precise and meaningful. Such uniformity captures that the true fo is unknown and rules out unrealistic and trivial situations, such as taking a GP with prior mean equal to the true fu and arbitrarily small covariance. Since we consider worst case (uniform) rates in Definition and it is well-known that the covariance kernel K of the GP determines the characteristics of the corresponding GP (26). including its posterior contraction rates 40) we without loss of generality restrict to mean-zero GPs.
There is by now an extensive literature on proving upper bounds for contraction rates 12). including for GPs [40]. These contraction rates are usually uniform over suitable function classes F,,, although the results might not be formulated in this way in the literature.
2.2 Lower bounds for posterior concentration in Gaussian processes regression
While the classical approach in nonparametric statisties is to make smoothness assumptions the regression function fo- recent work in the deep learning literature has studied compositional assumptions. A special case are generalized additive models of the form
fo(
h
Σ ge (xi) i=1
3

---

with 91.... ..... Id. h univariate and Lipschitz continuous functions such that all Lipschitz constants are bounded by A and [[gi [0. I 1 [o.1]. [|]]] I A. The class of all functions of this form denoted by (A) and define (()). Generalized additive models are among the most
popular structural constraints in function estimation [4].
Equation (13) in 32 and the subsequent discussion shows that the minimax estimation rate R., R., (G()) satisfies
en cn R, (G C(log n) -1/3
for some C. > O. Up to logarithmic factors, this rate is obtained by carefully calibrated deep GP priors that first assign hyperprior to different compositional structures and subsequently put GP priors all functions in the function composition [TO].
We are now ready to state the main lower bound results of this paper. which we emphasize applies to any GP, irrespective of the choice of covariance kernel (which may itself depend on n.).
Theorem 1. Let TT be any sequence of mean-zero Gaussian process priors on 1.2 1jd. For any 0 < 8 < 1/4 and (dd, 5) large enough, the corresponding posterior distributions satisfy
sup E (f Ilf follez 2 Can 4444 (Y) 2 1/4- foeg
where Ca 10:23
In particular, if the posterior distributions contract at rate e
2(442)
uniformly over G, that is
sup Fo [a( : II Sollaa Enl +
feed
as T1 OC, then En Can
4441
For dimension 2 3, the above rate is strictly slower than the minimax rate n 1/3 by the polynomial d-2 factor ा=+T2.__ As the domain dimension d tends infinity, our lower bound is approximately n 1/44 in which case Theorem says the GP posterior will place at least probability 1/4 - 5 on posterior
draws f ~ II, (-IY') having suboptimal reconstruction error ||f - foll 2 n 1/4, In contrast, posteriors based properly calibrated deep GPs will place almost all their probability on draws with minimax optimal reconstruction error of order n -1/3 [10]. Thus GP posteriors provide poor reconstructions of fo E G compared to deep GPs.
2nd
Theorem says that no GP can attain faster rate than n 4+44 attains this suboptimal rate, and specific GPs can perform much worse than this bound. We in fact conjecture that our lower bound can be improved to show that even this rate is not attainable by any GP, see Section 2.3 for more discussion. Nonetheless the main message from Theorem i already clear, namely that GPs underperform in this setting by an already significant factor that is polynomial the sample size n.
It does not say that given GP even
The last result says that generic posterior draws will be poor reconstructions of So with significant posterior probability. The same holds for the posterior mean.
Theorem 2. Let II, be any sequence of mean-zero Gaussian process priors L 1]d. Then the corresponding posterior means fn = E. [ satisfy for n 2 +)).
sup Fl SOll 2 C/n" foeg
-444,
4444,
2t4
where C²= - 2[(+2]]
Theorem states that the posterior mean fn will also be suboptimal reconstruction. Since the posterior is also Gaussian by conjugacy, and hence centered fa. this captures the notion that posteriors draws from the "center' of the posterior will also poor this is thus generic behaviour and not artifact of unusual behaviour in the posterior tails.
Our results also have implications for Bayesian uncertainty quantification (UQ) through the use of credible sets, which is one the main motivations for using GPs. Bayesian credible sets are often

---

used as frequentist confidence sets, practice which can be rigorously justified in low dimensional settings ((3)) Section 10.2), but is much more subtle in high-dimensional settings like GPs (... Whether a resulting credible set contains the truth will depend on the size of the posterior standard deviation relative to the distance between the posterior mean and the truth, which Theorem 2 says is greater than the minimax rate with than the latter and thus the credible set will provide honest and reliable UQ. However, in this case the posterior standard deviation must be at least of the order of the contraction rate, and hence the resulting credible sets will be (polynomially) much too large and uninformative. In the worse case, when the posterior standard deviation is smaller, the credible sets will not contain the truth and provide misleading (useless) UQ.
In the best case scenario, the former is greater
Note that we are considering UQ for the entire function fo it may still be possible for the GP posterior to provide efficient UQ for certain low-dimensional functionals of interest, which is itself a current topic of research 5 29].
The proof's are based on number of inequalities that are easy to state. Relying on an exponential concentration inequality and Anderson's 's inequality, we show that Theorem follows from the lower bound for the posterior mean in Theorem (cf. Section 4.Ip. For Theorem we provide two different proofs. In the first, we lower bound the - of the posterior mean over arbitrary finite subsets fff.....
fm] } C L 2 1]d (cf. Lemma 7). with the lower bound expressed in terms of expansions of the functions fi in the basis coming from the Karhumen-
expansion of the GP. We then construct a suitable collection of orthogonal generalized additive models for which the lower bound is maximized independently of the choice of GP basis, as is needed to deal with arbitrary GPs (cf. Section 4.3). Given specific choice of GP, our lower bound techniques can yield more refined results by tailoring the alternatives fi...., f. to be especially poorly aligned (difficult to learn) for that specific covariance function, see Section 2.3
In second proof of Theorem 2 presented in Section B in the supplement, we reduce the problem of studying orthogonal generalized additive models the sub-problem of studying the risk of linear estimators in one-sparse sequence model (cf. Section B.I). For the latter, we exactly compute the linear minimax risk in Lemma (9] bound in Theorem[] This second proof sheds additional light on the limitations of GP regression by furnishing new tools to study problems that can be connected to sparse models.
which, by exploiting the orthogonality, in turn implies the lower
2.3 A sharper lower bound for a specific class of Gaussian processes
While Theorem hoold for arbitrary GPs, we now show that our methods can yield sharper lower bounds in the case of specific GPs, implying even stronger suboptimality in the associated reconstruction error. We illustrate this by considering Gaussian wavelet series priors. Wavelets have been extensively used in Bayesian nonparametries to construct priors in function spaces, including applications in inverse problems [1 21, and image and signal processing 3 [8 among the others; see e.g. [22] for an overview.
Let (vi, Y E T), with r = ( = kj,k) -1, k E I,), be a compactly supported wavelet basis of L,² (R) restricted (with boundary correction) to [o. 1). cf. 77 or also [ Chapter 4]. The collection (Vhy, y = ( Ta) r4), with r = rx. T (e times) and thyy (x1...., ra)
IT M. (z:) provides a tensor product wavelet basis of [
Consider a mean-zero Gaussian wavelet series prior on 1,2 1]d with Karhunen-Loovv expansion
f(x) = Σ (TTEyNMa1))
x = (II, (I1...., xa) [0, 1jd,
TEX
for some arbitrary index set I rd, coefficients A,y > 0 and Ey ,nd NO, 1). Compared to the proof of the general lower bound in Theorem [] fixing a specific GP basis allows to consider compositional functions that are especially difficult for that GP to approximate. For wavelet bases, such approximation theory was developed in (32), which we employ to obtain the next lower bound.
Theorem 3. Let II, be any sequence of mean-zero Gaussian wavelet series priors on L 1] defined as in (4) with possibly n-dependent Xay > O. For any < ô 1/4 and n N(d, 8) large enough, the corresponding posterior distributions satisfy
sup E (f Il folle= 2 On अेत YY 2 1/4 8, foes
5

---

where C = C(d, 3) > O only depends on d and the wavelet basis. Furthermore, the corresponding
posterior means fn E [ satisfy for all
F. Sollea 2 C'n
sup
feeg
where C" = (d, v) > 0 only depends on d and the wavelet basis.
Thus, for the class of Gaussian wavelet series priors, Theorem
B provides sharper lower bound than Theorem | as n2 ==a >> тकम for all d. Furthermore, the former rate deteriorates as d grows, showing that the performance of Gaussian wavelet priors suffers from a form of curse of dimensionality. In particular, when d is large, the fastest rate Iों achievable by Gaussian wavelet priors is much slower than the minimax rate n 11/3 achieved by deep GPs.
3 Discussion
In this work, showed that no mean-zero Gaussian process can attain the minimax estimation rate over a class of generalized additive models. We proved this by developing new tools for lower bounding posterior contraction rates for GPs. We provided two different proofs, each of which sheds different light on these phenomena.
It remains open whether even sharper lower bounds can be obtained. In this context, important question is whether all GPs suffer from a curse of dimensionality in their posterior contraction rate, which we showed was incurred for a specific wavelet-based GP. Our lower bound n (2+d)/(4++6) for arbitrary GPs in Theorem d. While the obtained lower bound already demonstrates the suboptimality of GPs by a polynomial
never slower than 11/4 irrespective of the domain dimension
factor in n, say when compared to deep GPs, our stronger lower bound n -1/((++)) for Gaussian wavelet series priors becomes arbitrarily slow with increasing d. We thus proved that for this subclass of GPs, stronger curse of dimensionality is unavoidable
To avoid the curse of dimensionality, common two-stage approach is to first map the input features to a learned lower dimensional space and then apply Gaussian process regression to these new features. Our results do not apply to this scenario, in partieular when the feature extraction map can be be nonlinear, since the transformed underlying function may no longer be compositional in terms of the new learned features.
We expect similar results to hold for non-uniformly distributed input variables and heteroscedastic noise. Let be positive function and / density on [0, 1jd. If p, are bounded away from zero and infinity, we conjecture that, up to constants, the same lower bounds can be derived working in the more general nonparametric regression model (L) with, conditionally on X,, independent noise variables WX ~ (0, (X.)) and X; ,id p.
Ideally, one wants to develop a broader understanding of which structures in the data-generte generating distribution or regression function (deep) Gaussian processes can or cannot adapt to. order to understand the advantages of deep learning there is an extensive theoretical literature comparing shallow to deep nets. More refined versions show that for certain approximation rates a minimal network depth is necessary (24). To gain some insights into the role of depth in deep Gaussian processes, it would be desirable to explore similar limitations if the depth is fixed and highly structured function needs to be learned.
4 Proofs
We first start with some preliminary facts concerning GPs and the Gaussian white noise model (2). For IT a GP prior on [,2 1]d we can express its covariance kernel K in (3) in terms of
the normalized eigenfunctions {Ør k 2 1} of the compact, self-adjoint, trace-class operator |0 1 and its associated eigenvalues d > 0, which are summable, via the expansion K(x, y) = Σ A (x). In particular, we can realize the Gaussian random element f ~ II through its series expansion
g + fo.1j K(, dy)
x
f
V A
Ek idd N(0, 1),
(5)

---

known as the Karhumen-Loeve expansion. The corresponding reproducing kernel Hilbert space (RKHS) H is
H h
hROE
|
AR
For any orthonormal basis {Øx k 2 1f of L210, 1js, in particular the Karhunen-Loew basis of the prior (5), the Gaussian white noise model (2) is equivalent to observing the sequence model (Yx k 1):
Yu = f dx(x)dY, (dx, 2) 0.11
I ox(x)dW, =: 0: Vn p0.1
1
(6)
for k 1,2.3.... and where wy (O, | I (). To be precise, the observations
(Yx: : 2 1) in the last equation and the original white noise model (2) are equivalent in the sense that each be perfectly recovered from the other, Section C.2 the supplement for more details.
Viewing the prior II through its series expansion (5. II can be viewed as a prior on the space of coef- ficients in the basis expansion of (dhs) leading to the prior distribution f= (0x)s 60 NO, Ax). Denoting by Pj = Pfj the distribution of the sequence representation (6) we have likelihood
Pf = - (O 1/n).
Using this representation, one can use posterior conjugacy to show that the posterior takes the form
ndx YK ni
dE
OROK.
0g Y and N
+1
nd +
see Section C.2 in the supplement for full details. In particular, the posterior mean is
20
nd nd +
Jn = E ( Σ YROGe.
(8)
4.1 Reducing the lower bound for posterior contraction one for the I,2riskk of the posterior mean
We will show that lower bound on the Li-kisk of the posterior mean implies a corresponding lower bound for the posterior contraction rate, so that it will suffice to consider the former. The proofs of the following lemmas deferred Section[A.Ilin the supplement due to space constraints. We start by showing that the squared estimation error of the posterior mean is of the order of its expectation with high probability.
Lemma 4. Let fo L3 1jd, Fn [f[ denote the posterior mean based on a mean-zero Gaussian process prior II on L [ 11dt and set 2h El fo lo Then for n 2
Pro (ll folli < / < 4e
We next show that contraction rate for Gaussian process priors implies that the corresponding posterior means converge to the truth at the same rate with frequentist probability tending to one.
Lemma 5. Let HI be a sequence of mean-zero Gaussian process priors on T,2 1)d. Then the corresponding posterior means fr Fl [fl) satisfy
Pio (l - Solle= 2 27m) s 22 Nn follz 2 ralY)
for any sequence and n 2 1.
Combining the last two lemmas allows us to transfer an 1.2-rikk bound for the posterior mean to one for posterior contraction.

---

Lemma 6. Let fo E L2 1 II be a sequence of mean-2ero Gaussian process priors with
corresponding posterior means fr. E="[[[[] and set p fl follia Then for 1,
Ef Ilf foll / 2 4 1 - 4e
Furthermore, suppose Fu C L satisfy foPF. 5 fn fulliz 2 % > 0 for some sequence In for which ni 32 log
n Then for any 0 < 6 1/4 and such that my z
1-V1-43
sup (f llf Sollza 2 To/ mv/5lD 2 1/4 6.
fe
In particular, the posteriors cannot contract at rate 7n/5 uniformly over F...
4.2 A general lower bound for the -rik of the posterior mean
By Lemma 6 suffices to prove lower bound for the L rrrkrisk of the posterior mean. We next prove such a general lower bound.
Lemma 7. Let fn be an estimator of the form 8 with corresponding orthonormal basis fØr k 2 1}.
For functions f1....;f E L3
max j=
B 11 - I1
Σ Ug b2) L
n
(9)
k=1
Moreover, if fi,,.., Jm are orthogonal and max, ||5s 1l2a S m/n, then
m
E1,1fon -sllie
1
max I=
J=1
In particular, if cm/n & 1|5 S all j and some O < c S 1, then one can take the lower bound be em/n.
Proof. Using the bias variance decomposition, the expected prediction loss of an estimator of the form is
By M1 = Σ
nd
1) (S, (N)) + (1 ni (T
21 ) nde
1 nd
k=1
Setting a2 == -nnt nnd))) and Ti
1 ΣØ=1 (fi, 0k) 1,2
the last equation yields
max j_
E,, 1lf f31122 2 m j=1
E,, 1lfm f51122
(ak -
+
m
n
j=1 k=1
a
Σ aa
2)
Optimizing over as shows that the hight-hand side is minimized of nTTaa (1 + nTx)). For this choice, we obtain using + nTx 2 V (nTx).
Te
Ten
Th 1 nTr
max j= 1
Σ
(1+
(1 nT+)
A
Tx
proving the first claim.
To see the second claim, observe that ||S
S m/n and the orthogonality of the Sj imply
fz
0n >'
1 du )
1 11
Th m 5=1
Therefore Tg A 1/n Tk and using (9) and that (5xx) is basis,
m
m
1 m
E,, Jm -bll
Σ
du)i m j=1
Σ>
Σ
(S.s 22)
Σ
|| ||
max j=L.... m
m
m j=1
8

---

4.3 Construction of local functions and proof of Theorems 1 and 2
Lemma 8. Let m k for some integer Then there exist finnctins fi..... fm having disjoint support and satisfying [lf = 2d422) m for = I....,m. m.
2nd
Proof. For f = 1, ..... k consider the midpoints 21 = (f. - 1/2) /h: of the intervals [(e ((e- 1)/k: e/k.) Overall, there are m kd points in the grid
{(t)) ................................ zta)² Els...,la kI,...,k))
Consider the functions,
fa(x)
2k - -ax a/2 a11)
a= (a1,..., ET
These functions can be viewed as generalized additive models fa) = h(Ein (z.)) with f(u)) = (1/(2k) - u)+ and (as(x;) = I ag]. All these functions have Lipschitz constant bounded by 1. Moreover, max 1iixae,,=11.... 99s [o.1] S and |||]| (-))) = 1/(2k) S 1. Thus, fa E G.
Since |xc - 1 2 Jxc a co the support of the function Sa is contained the hypercube x== (a: 1/(2k), a, + 1/(2k)]. Since a; is of the form (L 1/2) with l an integer, the functions fo must have disjoint support and are therefore orthogonal.
It thus remains to compute the L norm of these functions, which by translation the same as that of fo( = (1/(2k) - |x|1)+ on R Note that the support of fo can be decomposed as supp(fo) =
Re, where
R
x E R sign(x;) = Et.
Σ j=1
20 S
2k
Since the T.2-norm of fo on each of these 2d quadrants is equal, we have
llfull: = 2d /
fo
R,
11(22)
11(28)-21
1/(2h)
28-1
2d
(1_
2k
21
xa) dx dxz ... dx
==1=
===0
===
Using repeatedly that p.a obtain
M -r (M - - yy
+ (M - r)(+1 for 0 S r S M and > 0, we
d+2
1
1
Iolli 2d
k --2
(d + 2)!
2k
2(d + 2)!
Proof of Theorems Mand 2 Letra 2(d22) k = [(ran) (d 2d=2
and kd. By Lemma 8 there
exist orthogonal functions fi,..., Jm E 9 with || ram 2nd For such a choice of l and m, cm/n S Ilfy 1 < m/n holds if and only if
(ran) x
czalz
(rann) adtt
K+1 for all x 2 E N. so that the right side lower bounded by 1/2 for (ram)ade zdtz > 1, or equivalently 2 1/ra- For 2 1/ra, therefore holds that cm/n < ||5 I m/n with c (1 (1/2)20+3
after rearranging the inequalities. Now the function (p(x) = x/[2]] satisfies ((x)) 2 *
Applying Lemma 7 thus gives the risk bound
sup E foll22 2 max foeg
Fr m
f/ 11
cm
22d+2 T 38+2 n
n

---

which proves Theorem 2
Set
4+2
((d 2(d + 2)!2 12/
32 log
v1
40
and note that NNd, 2 1/rd. Theorem then follows from the second last display and applying Lemma 6 with Fn = fm c g and 7 = 2 2 2642
244
72
Acknowledgments. We grateful to three anonymous referees for helpful comments that im- proved the manuscript. The research of MG has been supported by the European Research Council under ERC grant agreement No.8 N3.834275 (GTBB). The research of JSH has been supported by the NWO/STAR grant 613.009.034b and the NWO Vidi grant VI. Vidi 192.021.
References
[1] AGAPIOU, S., AND WANG, S. Laplace priors and spatial inhomogeneity in Bayesian inverse problems, 2021.
[2] AYKROYD, R. G., AND ALIOHANI, H. A Bayesian approach to wavelet-based modelling of discontinuous functions applied inverse problems. Comm. Statist. Simulation Comput. 49, 1 (2020), 207-225.
[3] BIOUCAS-DIAS, J. M. Bayesian wavelet-based image deconvolution: a GEM algorithm exploiting class of heavy-tailed priors. IEEE Trans. Image Process. 15, 4 (2006), 937-951.
[4] CASTILLO, I. Lower bounds for posterior rates with Gaussian process priors. Electron. J. Stat.
2 (2008). 1281-1299.
[5] CASTILLO, I., AND ROUSSEAU, J. A vernstein-von Mises theorem for smooth functionals in semiparametric models. Ann. Statist. 43, (2015),
[6] CHÉRIEF-ABDELLAATI B.-E. Convergence rates of variational inference in sparse deep learning. In Proceedings of the 37th International Conference on Machine Learning (13-18 Jul 2020), vol. 119 of Proceedings of Machine Learning Research, PMLR, pp. 1831-1842.
[7] COHEN, A., DAUBECHIES, I., AND VIAL, P. Wavelets the interval and fast wavelet transforms. Appl. Comput. Harmon. Anal. 1, (1993), 54-81.
[8] DAMIANOU, A., AND LAWRENCE, N. D. Deep Gaussian processes. Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics (29 Apr-01 May 2013), vol. 31 Proceedings of Machine Learning Research, PMLR, pp. 207-215.
[9] DONOHO, D. L., AND JOHNSTONE, I. M. Minimax estimation via wavelet shrinkage. Ann. Statist. 26, 3 (1998), 879-921.
[10] FINOCCHIO, G., AND SCIMIDT-HIEBER, J. Posterior contraction for deep Gaussian process priors, 2021.
[11] FREEDMAN, D. On the Bernstein-von Mises theorem with infinite-dimensional parameters. Ann. Statist. 27, 4 (1999), 1119-1140.
[12] GHOSAL, S., AND VAN DER VAART, A. W. Fundamentals of Nonparametric Bayesian Inference. Cambridge University Press, New York, 2017.
[13] GINÉ, E., AND NICKL, R. Mathematical foundations of iifnite-dimeessionll statistical models. Cambridge Series in Statistical and Probabilistic Mathematics, [40]. Cambridge University Press, New York, 2016.
[14] HASTIE, T. J., AND TIBSHIRANI, R. Generalized additive models, vol. 43 of Monographs on Statistics and Applied Probability. Chapman and Hall, Ltd., London, 1990.
[15] HAYAKAWA, S., AND SUZUKI, T. the minimax optimality and superiority of deep neural network learning over sparse parameter spaces. Neural Networks 123 (2020), 343-361.
10

---

[16] IMAIZUMI, M., AND FUKUMIZU, K. Deep neural networks learn non-smooth functions effectively. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019 (2019), vol. 89 of Proceedings of Machine Learning Research, PMLR, pp. 869- 878.
[17] IMAIZUMI, M., AND FUKUMIZU, K. Advantage of deep neural networks for estimating functions with singularity on hypersurfaces, 2020.
[18] JACOBSEN, D., AND MØ LLER, Frequentist and Bayesian inference for Gaussian- -oog- Gaussian wavelet trees and statistical signal processing applications. Stat 6 (2017), 248-256.
[19] JOHNSTONE, I. Gaussian estimation: Sequence and wavelet models. available from https //imjohnstone. su. domains//eett Ltapiissee____11_____11 pdf 2019.
[20] JOHNSTONE, I. M. High dimensional Bernstein-von Mises: simple examples. In Borrowing strength: theory powering applications Festschrift for Lawrence Brown, vol. 6 of Inst. Math. Stat. (IMS) Collect. Inst. Math. Statist., Beachwood, OH, 2010, pp. 87-98.
[21] KOROSTELEV, A. P., AND TSYBAKOV, A. B. Minimax theory of image reconstruction, vol. 82 of Lecture Notes in Statistics. Springer-Verkee Verlag, New York, 1993.
[22] MÜLLER, P., AND VIDAKOVIC, B., Eds. Bayesian inference in wavelet- models, vol. 141 of Lecture Notes in Statistics. Springer-Verlag, Verlag, New York, 1999.
[23] NEAL, R. M. Bayesian Learning for Neural Networks. Springer- Veraer,,,ergg,, Berlin, Heidelberg, 1996.
[24] PETERSEN, P., AND VOIGTLAENDER, Optimal approximation of piecewise smooth functions using deep ReLU neural networks. Neural Networks 108 (2018), 296-330.
[25] POLSON, N. G., AND ROčKOVÁ, V. Posterior concentration for sparse deep learning. In Advances in Neural Information Processing Systems (2018), pp. 930-941.
[26] RASMUSSEN, C. E., AND WILLIAMS, C. K. I. Gaussian processes for machine learning. Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, 2006.
[27] RAY, K., SZABO, B., AND CLARA, G. Spike and slab variational Bayes for high dimensional logistic regression. In Advances in Neural Information Processing Systems (2020), vol. 33, Curran Associates, Inc., pp. 14423-14434
[28] RAY, AND SZABÓ, B. Variational Bayes for high-dimensional linear regression with sparse priors. Journal of the American Statistical Association (2021), 1-12.
[29] RAY, K., AND VAN DER VAART, A. Semiparametrie Bayesian causal inference. Ann. Statist. 48, 5 (2020), 2999-3020.
[30] REISS, M. Asymptotic equivalence for nonparametric regression with multivariate and random design. Ann. Statist. 36, 4 (2008), 1957-1982.
[31] ROCKOVA, V., AND ROUSSEAU, J. Ideal Bayesian spatial adaptation, 2021.
[32] SCHMIDT-HIEBER, J. Nonparametric regression using deep neural networks with ReLU activation function. Ann. Statist. 48, (2020), 1875-1897
[33] CCHMIDT--HBBER, J. The Kolmogonvv-Amold representation theorem revisited. Neural Networks 137 (2021), 119-126.
[34] SUZUKI, T. Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019 (2019), OpenReview.net.
[35] SUZUKI, T., AND NITANDA, A. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropie Besov space. In Advances in Neural Information Processing Systems (2021), vol. 34, Curran Associates, Inc., pp. 3609-3621.

---

[36] TANG, J., MENG, Z., NGUYEN, X., MEI, Q., AND ZHANG, M. Understanding the limit- ing factors of topic modeling via posterior contraction analysis. In Proceedings of the 31st International Conference on Machine Learning (Bejing, China, 22-24 Jun 2014), vol. 32 of Proceedings of Machine Learning Research, PMLR, pp. 190-198.
[37] TELGARSKY, M. Benefits of depth in neural networks. In 29th Anmual Conference on Learning Theory (Columbia University, New York, New York, USA, 23-26 Jun 2016), vol. 49 of Proceedings of Machine Learning Research, PMLR, pp. 1517-1539.
[38] TSUJI, K., AND SUZUKI, T. Estimation error analysis of deep learning on the regression problem the variable exponent Besov space. Electronic Journal of Statistics 15, (2021), 1869 1908.
[39] VAN DER VAART, A. W. Asymptotic statistics, vol. 3 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 1998.
[40] VAN DER VAART, A. W., AND VAN ZANTEN, J. H. Rates of contraction of posterior distribu- tions based on Gaussian process priors. Ann. Statist. 36, 3 (2008), 1435-1463.
[41] VÄNSKÄ, S., LASSAS, M., AND SILTANEN, S. Statistical X-ray tomography using empirical Besov priors. Int. J. Tomogr. Stat. 11, S09 (2009), 3-32.
[42] WANG, Y., AND BLEI, D. Variational Bayes under model misspecification. In Advances in Neural Information Processing Systems 32. 2019, pp. 13357-13367.
[43] WANG, Y., AND BLEI, M. Frequentist consistency of variational Bayes. Amer. Statist. Assoc. 114, 527 (2019), 1147-1161.
[44] YAROTSKY, D. Error bounds for approximations with deep ReLU networks. Neural Networks 94 (2017), 103-114.
[45] YAROTSKY, D. Optimal approximation of continuous functions by very deep ReLU networks. In Proceedings of the 31st Conference On Learning Theory (06-09 Jul 2018), vol. 75 of Proceedings of Machine Learning Research, PMLR, pp. 639-649.
12

---

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] The claims are reflected Theorems 1 and
(b) Did you descrihe the limitations of your work? [Yes] See the discussion in Section 3
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] The paper conforms to the indicated guidelines
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] General assumptions stated in Section 2.1 specific assumptions in the statement of every theorem
(b) Did you include complete proofs of all theoretical results? [Yes] All the proofs are in Section 4 and in the Supplementary material
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 URL)? [N/A]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing 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 assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or 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, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "t5RY0cjPPLi", "reviewer": "Reviewer_txpX", "summary": "In this paper, the authors studied information-theoretic lower bounds of posterior contraction rate for Gaussian process regression with compositional assumptions. Specifically, if the true function is a generalized additive function, the posterior contraction rate of any zero-mean Gaussian process (irrespective of the choice of kernel) is strictly slower than the minimax rate. Even the posterior mean will be a suboptimal reconstruction and implies an uninformative uncertainty quantification. A sharper lower bound is also studied, showing that the performance under the Gaussian wavelet series priors suffers from the curse of dimensionality. \n\nOverall, the paper is well written and easy to follow. ", "questions": "The following questions may be considered by the authors. \n\n1. How would the range ([0,1]) and the distribution of points x affect the theorem results? Since the points may not follow U [0,1] in real applications.\n\n2. How would the feature extraction methods (neural networks, projections, etc.) affect the correctness of Theorem 1? As lots of works with high-dimensional points or multi-modal data will first project the data to a low-dimensional feature space with better expressiveness. If the dimension is lower than 3, according to Theorem 1, then the contraction rate can be accepted.\n\n\n", "limitations": "This paper concentrates on the zero-mean Gaussian process with sample data generating process and the underlying function with a special case of the compositional functions, it would be better to extend it to general mean function. ", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Various proofs and frequentist assessments are provided to measure the speed of posterior contraction around the true regression function, which is a solid work that helps people to understand the theory underlying deep Gaussian process and the curse of dimensionality. For varied research backgrounds, it is recommended to add an extra paragraph to elaborate on the notations and mathematical operators used throughout the paper. \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": "m2fdwXc9h7o", "reviewer": "Reviewer_SNzg", "summary": "In the domain of frequentist guarantees of Bayesian nonparametric models, the paper exhibits a case where Gaussian processes learn slower than the minimax rate. This is of particular interest because for the same function class a recent paper showed that deep Gaussian do achieve the minimax rate. The sub-optimality of the GP is shown to be at least polynomial under very general assumptions. The function class in question is a type of generalized additive model. So together with the previous paper on deep GPs this is a formalization of the idea that deep methods do better when the \"true\" function is compositional in a certain particular sense. There is a relatively self contained exposition of the necessary background. The compositional function class considered does not easily fall into the domain of previous theoretical work lower bounding the rates of linear methods so providing a proof method is the main part of the technical novelty. ", "questions": "I have no questions.", "limitations": "As far as I can see there is no potential negative societal impact of this work unless one was against science and mathematics in general. The scientific limitations are very clearly communicated and discussed leaving ample opportunities for follow up work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Clarity: I found the exposition of the results very clearly written considering that this is a notoriously challenging area of the literature. Work like this would often appear in a statistics journal and it felt like a particular effort had been made to make the work accessible to the NeurIPS theory community. Each non-trivial statement was carefully referenced. I hope to learn from such exposition in my own work. Make though mistake though, the work is still technically quite challenging for an average non-theoretical NeurIPS reader and the proof section is very heavy going I suspect for the big majority of potential readers. So be it.\n\nOriginality: There is a very clearly defined research question for the paper and this topic is to the best of my knowledge novel. Answering the question requires highly non trivial proof methods.\n\nQuality: The expositional sections are of a high quality. I spent a significant amount of time on the paper and the proof method looks sensible to me but to carefully verify it would take more time than is available particularly given heavy reviewing loads this year. Given that similar work appears for instance in the Annals of Statistics where peer review takes significantly longer it is difficult to verify it to that level in this venue. It helps that there are two independent proof methods for Theorems 1 and 2 and that the result is not entirely unexpected.\n\nSignificance: The work is significant enough for publication in this venue in my opinion. At a broad level all work in this area is somewhat abstracted from practical reality. The work is in a sense \"doubly\" asymptotic since it requires both the reformulation in terms of a \"statistically equivalent\" SDE to be valid and then the number of data points to be sufficiently large on top of that. Of course chaining asymptotes is fine if this is your only goal but it does of course make it harder to understand the implications for numbers of data points and dimensionality encountered in practice. Similarly work in this area neglects computational constraints. After all both GPs and deep GP posteriors require approximation in practice. This is again fine as long as this is understood. More specifically to this paper the most general difference in rate (Theorems 1 and 2) is proven to be a polynomial and the level of difference is bounded as the dimension increases. It is tantalizing that the authors speculate that the more dramatic difference in rate proven under the special conditions of Theorem 3 may apply more generally. This obviously would increase the significance of the work but I appreciate how difficult such results are to obtain.", "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": "l4v46ytwvtg", "reviewer": "Reviewer_sPbe", "summary": "This paper derives a novel lower bound for the GP posterior contraction rate when the true function has an additive structure. The result shows that for any GP in such scenario, the contraction rate is worse than the minimax estimation rate of deep GP. The authors further demonstrate that the contraction rate is even more suboptimal on a specific GP (e.g., Gaussian wavelet series). This is a purely theoretical work and there is no empirical study.", "questions": "- In line 113, when the minimax rate is introduced, I had to assume that this is the rate for deep GP prior based on the motivation of this work. Eq. (13) of [32] seems to suggest that the analysis is for general nonparametric regression with deep NN. Can you elaborate on the extension of this to GP with deep prior?\n- Also [32] seems to suggest that the deep architecture has to satisfy certain conditions to achieve such rate. Can you provide a brief summarization of what those conditions entail, and whether they are realistic in practice? For example, in practice we also have to train the weights of the network, and I suppose a large architecture would affect the convergence rate. \n- As a non-expert, I am quite curious if a contraction rate for deep GP has been lower bounded for general $f_0$ ? If so, how would the difference compare to the additive scenario? \n- How do we arrive at the expectation in line 18 of the appendix?", "limitations": "The authors have not discussed negative societal impact of their work. However, since this is a purely theoretical work, I do not think there is any potential problem.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper provides two original proving strategies to obtain the lower bounds of GP posterior and posterior mean contraction rates in the generalized additive function setting. The first strategy directly derives these lower bounds, whereas the second strategy reduces the regression to a one-sparse sequence model then lower bounds the minimax risk for its linear estimators. To the best of my ability, I have verified that both proofs are sound and original. Nonetheless, I acknowledge that I have taken some derivation steps for granted and my lingering questions are listed in the section below.\n\nThe paper is generally well presented and its high level ideas are quite easy to follow, although there are some small issues with the notations and technical clarity. For example:\n- The symbol $L$ is overloaded to imply both Lipschitz constant and the $L^2$ space. \n- In line 109, it seems to me that $f_i$ was overloaded to imply both the $i^{\\text{th}}$ additive component of $f_0$ and later on $f_0(x_i)$ with $x_i$ being the $i^{\\text{th}}$ observed input. I could be wrong, so I invite the authors to clarify this.\n- The subscript $i$ in $x_i$ is also used to denote both the $i^{\\text{th}}$ observed input and the $i^{\\text{th}}$ dimension of an arbitrary input.\n\nOverall, I believe the paper delivers a good theoretical contribution, and it is sufficient without empirical demonstration. However, it would be more compelling to see if the proposed theory aligns with practice, especially in settings that specifically construct the latent function $f_0$ to be of additive form, as assumed in this paper.\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