Estimating the covariance function of a random process from noisy discrete samples is a nonparametric problem that suffers from the curse of dimensionality. The covariance is defined on a product domain — if the original data lives in d dimensions, the covariance lives in 2d dimensions.
Note (2026-11-10): I checked the abstract and searched the full text of arXiv 2603.23302. The comparison is as the essay says, with two qualifiers. The deep learning rate for the structured class is minimax only up to polylogarithmic factors, and the one-dimensional suboptimality is shown in the dense regime for a smoothness class from earlier work. The paper's structured classes are those of Cai and Yuan (2010), where deep learning matches smoothing splines up to polylogarithmic factors; I did not find the words compositional or hierarchical in the text. The essay's description of them as compositional, and its account that deep networks are composition machines that match compositional targets, are the essay's own explanation. The abstract says the rates “suggest” that structural adaptation can mitigate the curse of dimensionality.
The authors (arXiv:2603.23302) establish an oracle inequality for general learning-based covariance estimators, covering both sparse and dense observation regimes. They show that deep learning estimators achieve minimax-optimal rates for structured covariance function classes — those with compositional or hierarchical structure.
The surprise is in the comparison. For one-dimensional smoothness classes, deep learning is suboptimal — local linear smoothing achieves a faster rate. But for structured function classes (where the covariance has compositional form), deep learning wins and local linear smoothing is suboptimal.
The through-claim: whether deep learning helps depends on whether the structure of the covariance matches the structure of the network. Deep networks are composition machines; they excel when the target function is itself a composition. Smooth but unstructured covariance functions are better served by local methods. The adaptivity-variance tradeoff in covariance estimation is architecture-dependent — there is no universally best estimator.