Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation

arXiv:2606.07931v1 Announce Type: cross Abstract: We prove a variance-aware pointwise majorizing-measure theorem for centered Gaussian processes. Classical generic chaining characterizes the scalar quantity mathbb Esup_{xin T}X_x; the theorem here gives a simultaneous high-probability envelope for the entire field. For an ambient prior mu, the envelope at x is governed by a pointwise Fernique-Talagrand functional [Phi_mu(x):=int_0^{4sigma(x)}sqrt{logfrac{1}{mu(B_d(x,arepsilon))}},darepsilon,] together with the corresponding Gaussian tail term. The theorem provides a reusable field-level refinement of classical generic chaining and a Gaussian-process counterpart of pointwise empirical-process bounds for deep neural networks. We also record a Bayesian algorithmic lower envelope from the interactive Fano/data-processing principle. For a known prior pi, an observation channel, and a concrete estimator widehat t(Y), the lower bound is expressed through the exact ghost small-ball mass mathbb E_{Ysim Q}pi(B_d(widehat t(Y),Delta)), rather than a worst-case covering number. In Gaussian location experiments, comparison decoders convert Bayes location error into lower bounds on decision-aligned Gaussian ranges. We then construct an elementary weighted-basis example separating the usual Fano relaxation for a fixed prior, the Bayesian algorithmic lower envelope, the pointwise Gaussian envelope on the selected subatlas, and the full-class minimax risk/global Gaussian scale. Together, these results show that algorithmic lower bounds provide local-geometric certificates of pointwise complexity for fixed estimators in overparameterized ambient classes, precisely in regimes where classical minimax theory becomes either too coarse or oracle-dependent.

Source: arXiv cs.LG | 2026-06-09