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.
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.