# On the inability of Gaussian process regression to optimally learn compositional functions

arXiv: https://arxiv.org/abs/2205.07764 · HTML: https://mlsanity.com/paper/2205.07764/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 61 references that are in the map.
- First posted on arXiv 16 May 2022.

## Builds on (most cited first, 19 of 19)

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Optimal approximation of continuous functions by very deep ReLU networks](https://mlsanity.com/paper/1802.03620/) (2018)
- [Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality](https://mlsanity.com/paper/1810.08033/) (2018)
- [The Kolmogorov-Arnold representation theorem revisited](https://mlsanity.com/paper/2007.15884/) (2020)
- [Frequentist Consistency of Variational Bayes](https://mlsanity.com/paper/1705.03439/) (2017)
- [Deep Neural Networks Learn Non-Smooth Functions Effectively](https://mlsanity.com/paper/1802.04474/) (2018)
- [Posterior Concentration for Sparse Deep Learning](https://mlsanity.com/paper/1803.09138/) (2018)
- [Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space](https://mlsanity.com/paper/1910.12799/) (2019)
- [Variational Bayes for high-dimensional linear regression with sparse priors](https://mlsanity.com/paper/1904.07150/) (2019)
- [Convergence Rates of Variational Inference in Sparse Deep Learning](https://mlsanity.com/paper/1908.04847/) (2019)
- [On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces](https://mlsanity.com/paper/1905.09195/) (2019)
- [Variational Bayes under Model Misspecification](https://mlsanity.com/paper/1905.10859/) (2019)
- [Advantage of Deep Neural Networks for Estimating Functions with Singularity on Hypersurfaces](https://mlsanity.com/paper/2011.02256/) (2020)
- [Spike and slab variational Bayes for high dimensional logistic regression](https://mlsanity.com/paper/2010.11665/) (2020)
- [Estimation error analysis of deep learning on the regression problem on the variable exponent Besov space](https://mlsanity.com/paper/2009.11285/) (2020)
- [Frequentist and Bayesian inference for Gaussian-log-Gaussian wavelet trees, and statistical signal processing applications](https://mlsanity.com/paper/1405.0379/) (2014)

## Built on by (most cited first, 7 of 7)

- [What Can Be Learnt With Wide Convolutional Neural Networks?](https://mlsanity.com/paper/2208.01003/) (2022)
- [How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning](https://mlsanity.com/paper/2407.05664/) (2024)
- [Deep Horseshoe Gaussian Processes](https://mlsanity.com/paper/2403.01737/) (2024)
- [PI-JEPA: Label-Free Surrogate Pretraining for Coupled Multiphysics Simulation via Operator-Split Latent Prediction](https://mlsanity.com/paper/2604.01349/) (2026)
- [Deep Latent Force Models: ODE-based Process Convolutions for Bayesian Deep Learning](https://mlsanity.com/paper/2311.14828/) (2023)
- [Preference Learning with Response Time: Robust Losses and Guarantees](https://mlsanity.com/paper/2505.22820/) (2025)
- [Support Collapse of Deep Gaussian Processes with Polynomial Kernels for a Wide Regime of Hyperparameters](https://mlsanity.com/paper/2503.12266/) (2025)

## Abstract (arXiv)

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.