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

Yunbei Xu

Source-linked AI summary

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

Yunbei Xu

arXiv:2606.07931v2Jun 6, 2026math.PRcond-mat.stat-mechcs.ITcs.LGmath.ST

TL;DR

The paper addresses the gap between scalar global complexity measures and field- or estimator-specific behavior in Gaussian and overparameterized problems. It develops a variance-aware pointwise Gaussian envelope and an exact ghost-mass Bayesian algorithmic lower bound, then uses a separating example to compare these with classical Fano and full-class minimax quantities. The results support local-geometric validation for fixed estimators and recast the separation as penalty-range information relaxation.

Problem
Classical generic chaining and minimax criteria can miss pointwise field structure or become too coarse, prior-dependent, or oracle-dependent for concrete estimators in overparameterized classes.
Method
The paper proves a variance-aware simultaneous Gaussian envelope, derives estimator-specific Bayesian lower bounds from exact ghost small-ball mass and Gaussian comparison decoders, and constructs a weighted-basis separation with a penalty-range minimax reformulation.
Results
The ghost-mass lower envelope and pointwise Gaussian upper envelope match on the estimator-selected subatlas, while full-class minimax risk and global Gaussian scale are much larger.
Takeaways & Limitations
Algorithmic lower bounds can locally validate pointwise complexity for fixed estimators, and penalty-range information relaxation provides a minimax language for this decision-aligned comparison.
Takeaways & Limitations
The pointwise simultaneous envelope carries peeling logarithms that disappear only in the optimized global in-expectation bound.

Abstract

from arXiv · show

We prove a variance-aware pointwise majorizing-measure theorem for centered Gaussian processes. Classical generic chaining characterizes the scalar quantity $\mathbb E\sup_{x\in T}X_x$; the theorem here gives a simultaneous high-probability envelope for the entire field. For an ambient prior $μ$, the envelope at $x$ is governed by a pointwise Fernique-Talagrand functional \[Φ_μ(x):=\int_0^{4σ(x)}\sqrt{\log\frac{1}{μ(B_d(x,\varepsilon))}}\,d\varepsilon,\] 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 $π$, an observation channel, and a concrete estimator $\widehat t(Y)$, the lower bound is expressed through the exact ghost small-ball mass $\mathbb E_{Y\sim Q}π(B_d(\widehat t(Y),Δ))$, 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 example separating the usual Fano relaxation, the Bayesian algorithmic lower envelope, the pointwise Gaussian envelope, and the full-class minimax risk. Together, these results show that algorithmic lower bounds provide local-geometric validations of pointwise complexity for fixed estimators in overparameterized ambient classes, precisely in regimes where classical minimax theory becomes either too coarse or oracle-dependent. This separation can also be recast in minimax language as penalty-range information relaxation, highlighting an important question of algorithmic robustness for classical high-dimensional models and regularized algorithms.

1 Introduction and Main Results

The paper refines Gaussian generic chaining into a variance-aware simultaneous pointwise envelope and pairs it with estimator-specific Bayesian lower bounds. An elementary separation shows these local, decision-aligned quantities can be sharp while Fano relaxations, full-class minimax risk, and global Gaussian scales are much larger.

Separation and implications: The separating example makes the ghost-mass lower envelope and pointwise upper envelope sharp on the estimator-selected subatlas while full-class benchmarks are much larger.The paper argues that full minimax can be too pessimistic and restricted minimax can be oracle-dependent when the relevant subatlas is selected by the prior and algorithm.
Separation and implications: The results motivate criteria localized to the estimator and reference law for validating pointwise complexity in overparameterized ambient classes.This addresses settings where classical minimax or Bayes-risk criteria are too coarse, prior-dependent, or oracle-dependent.
Pointwise Gaussian theorem: Theorem 1.1 gives a simultaneous high-probability envelope for every field value, refining scalar control of E sup_x X_x with local pointwise complexity.The theorem is stated as a variance-aware pointwise Gaussian majorizing-measure bound and uses an ambient prior.
Pointwise Gaussian theorem: Replacing the global metric bound by the local variance scale 4σ(x) is the theorem's key technical refinement.The Gaussian proof also avoids the advanced symmetrization and mixed empirical-ghost metric required in the cited neural-network analogue.
Pointwise Gaussian theorem: Optimizing the pointwise envelope over the ambient prior recovers the anchored generic-chaining scale sharply up to universal constants.The peeling logarithms disappear at the global in-expectation level, although they are needed to extract the simultaneous pointwise envelope.
Bayesian algorithmic bounds: The Bayesian algorithmic lower envelope retains the exact ghost small-ball mass of a concrete estimator rather than replacing it with a class-wide worst-case small-ball term.In Gaussian location experiments, comparison decoders convert Bayes location error into lower bounds on decision-aligned Gaussian ranges, while the pointwise envelope supplies matching upper bounds when estimates coincide.

2 Proof of Pointwise Gaussian Majorizing-Measure Theorem

The proof builds the pointwise Gaussian envelope through subset-homogeneous majorizing-measure bounds and two applications of uniform pointwise peeling. Fernique–Talagrand control, ambient-prior localization, and Gaussian concentration yield the simultaneous envelope and its absolute-value version.

Subset-homogeneous estimate: The proof combines anchored Fernique–Talagrand bounds, ambient pointwise-dimension equivalence, and Borell–Tsirelson concentration on arbitrary subsets.The subset-homogeneous construction is then lifted to the full index set through peeling.
Uniform pointwise peeling: Two peeling steps separately localize the Fernique–Talagrand integral and the variance scale, avoiding unrealistic Bernstein-type or rigid sub-root assumptions.The first peeling controls the residual complexity, while the second handles the variance profile.
Ambient equivalence: The ambient prior is localized through a nearest-point pushforward, converting ambient ball masses into subset ball masses at a doubled radius.This supplies the comparison needed to control the localized integral on each subset.
Final envelope: Theorem 1.1 yields a simultaneous high-probability pointwise Gaussian envelope, with the absolute-value form obtained by applying the argument to both X and −X.The result holds uniformly over the field and combines the localized complexity with Gaussian tail terms.
Expectation consequence: After integrating the tail and optimizing over the ambient prior, the in-expectation global bound is sharp up to universal constants.The variance-radius term is part of the anchored generic-chaining scale rather than an additional loss.

3 Proof of Bayesian Algorithmic Lower and Upper Bounds

The Bayesian lower-envelope proof applies an interactive Fano/data-processing inequality to the exact ghost small-ball mass of a specified estimator. In Gaussian location experiments, comparison decoders convert the resulting Bayes location bound into a decision-aligned Gaussian-range bound, while pointwise envelopes provide the matching upper control.

Bayesian lower envelope: The Bayesian lower envelope is derived for a concrete estimator, prior, observation channel, radius, and reference law through an interactive Fano argument.The proof introduces the ghost law and rearranges the resulting information inequality into the stated lower bound.
Ghost-law formulation: The exact ghost small-ball mass remains tied to the estimator’s output under reference data rather than a worst-case class-wide relaxation.This preserves the estimator- and reference-law dependence of the lower bound.
Gaussian comparison: In Gaussian location experiments, an approximate comparison-decoder condition relates Bayes location error to a Gaussian range through the identity Y = vΘ + τZ.The proof expands the squared-distance comparison and uses expectation and Jensen’s inequality.
Upper control: A simultaneous pointwise Gaussian envelope supplies the corresponding algorithmic upper bound on decoding risk.The argument applies the absolute pointwise envelope to an anchored process and restricts back to the original index set.

4 Proof of Separation Example and Pointwise Validation

The finite weighted-basis construction separates fixed-prior Fano, algorithmic ghost-mass, pointwise Gaussian, and full-class minimax scales. It shows that the actual regularized estimator aligns with the low-norm decision subatlas even when the ambient cloud dominates global complexity.

Construction: The construction explicitly separates the full ambient class, a decision-dependent subatlas, a fixed prior, and an unrestricted minimum-norm estimator.The example is finite-dimensional and keeps each benchmark distinct.
Bayes risk: The actual estimator has Bayes risk of order R, and the Bayes-optimal risk is also of order R, despite the ambient cloud.The lower bound follows by reducing accurate location estimation on the low-norm points to index classification.
Fano versus ghost mass: The usual fixed-prior Fano relaxation is vacuous, whereas the exact algorithmic ghost mass gives a sharp Bayes estimation lower bound for the same prior, channel, and estimator.The worst-case relaxation yields only log 2, while the exact ghost-mass argument remains informative.
Full-class minimax: The full-class minimax risk is of order S, and exceeds the Bayes scale by a factor governed by log N / log M when that ratio diverges.The ambient cloud drives the minimax benchmark even though it is irrelevant to the specified Bayesian decision problem.
Pointwise validation: The selected low-norm subatlas has decision-aligned Gaussian scale R√log M, while the full ambient Gaussian scale is larger by order log N / log M.The same separation appears between the pointwise envelope on the subatlas and the global Gaussian supremum.
Interpretation: The fixed numerical penalty identifies the relevant subatlas without depending on the prior or problem parameters, while restricted minimax validation can remain oracle-dependent.The construction therefore treats the actual estimator and reference law as the appropriate validation objects.

5 Proof of Penalty-Range Information-Relaxation Reformulation

The penalty-range reformulation studies regularized estimators over tuning intervals rather than a single oracle penalty. Above the critical penalty the cloud is suppressed and the estimator’s range matches the selected subatlas, while below it the cloud is selected and the risk reaches the ambient scale.

Penalty threshold: The proof analyzes regularized scores over penalty ranges, with a critical threshold separating cloud suppression from cloud selection.The score comparison is performed under both the ghost and true Gaussian location laws.
Optimal penalty range: For penalties above the critical value, the estimator selects the low-norm subatlas with high probability under the ghost law.A Gaussian tail bound and union bound suppress selection of every cloud point.
Ghost-mass control: The ghost mass is at most C/M in the optimal penalty range, enabling the Bayesian algorithmic lower bound.Exchangeability makes the selected hub point uniform conditional on remaining in the subatlas.
Under-regularization: For penalties below the threshold, the decoder selects a cloud point with probability tending to one and incurs risk of order S.This lower bound holds even over all measurable estimators, while the matching upper bound follows from the ambient diameter.
Ambient comparison: The full-class minimax and Gaussian supremum scales remain of order S and S√log N, respectively, creating the same ambient-versus-subatlas separation.Thus the penalty range determines whether the estimator reflects the localized or global complexity scale.
Decision-aligned range: For penalties above the threshold, the algorithmic Gaussian range is of order R√log M, matching the selected-subatlas pointwise scale.The comparison conditions hold with zero optimization, penalty, and comparison error.

6 Conclusion

The paper develops pointwise Gaussian envelopes and Bayesian algorithmic lower bounds, then uses them to separate estimator-selected local complexity from global worst-case scales.

The Gaussian refinement is a simultaneous pointwise envelope that preserves local field information before taking a final supremum.It is sharp in expectation after optimizing over the prior and recovers the anchored Fernique–Talagrand scale.
The Bayesian algorithmic lower envelope applies to every estimator through the exact ghost small-ball mass at a single testing radius.Comparison decoders convert Bayes distance error into lower bounds on decision-aligned Gaussian ranges.
The weighted-basis hub–cloud example matches the algorithmic lower and pointwise upper envelopes on an estimator-selected subatlas, while global benchmarks are much larger.The separation concerns fixed estimators in overparameterized ambient classes, where full minimax theory can be too coarse or oracle-dependent.
The same separation admits a penalty-range information-relaxation formulation that treats robust tuning information as a statistical resource for a fixed algorithmic family.This connects the construction to algorithmic information gaps, adaptivity, and classical regularization phenomena such as the Lasso.
Finite-cutoff renormalization and graph local time exhibit the same mechanism: trajectory-aligned or selected-subatlas complexity can be smaller than full-cover complexity.These analogies extend the pointwise-versus-global distinction beyond Gaussian-process and decision-theoretic settings.
Taken together, the results distinguish genuine full-class hardness from tractability validated on geometry selected by a field, estimator, or renormalization trajectory.The minimax reformulation frames this distinction as an algorithmic-robustness question for traditional high-dimensional models.

A.1 Structural analogy between finite-cutoff RG and feature-learning DNN

The appendix aligns finite-cutoff RG with feature-learning DNN through shared feature/operator inner-product structures while emphasizing their different coordinates and scope.

A.1 Structural analogy between finite-cutoff RG and feature-learning DNN: Both finite-cutoff RG and feature-learning DNN use an exact telescoping structure with local response or feature Gram matrices.The correspondence is structural rather than a claim that RG coupling vectors are identical to DNN matrix weights.
A.1 Structural analogy between finite-cutoff RG and feature-learning DNN: DNN layers use rectangular matrix weights and shared input-feature matrices, whereas truncated RG steps use finite-dimensional coupling vectors after integrating out fluctuations.Consequently, the DNN pointwise metric has Kronecker repetition, while generic RG secant Grams do not provide that structure automatically.
A.1 Structural analogy between finite-cutoff RG and feature-learning DNN: The appendix separates Bayesian lower-envelope radii from multiresolution chaining scales and distinguishes metric resolutions from RG levels.Finite-cutoff or finite-step refers to a non-infinitesimal telescoping argument, not to the testing radius used by the Bayesian bound.
A.1 Structural analogy between finite-cutoff RG and feature-learning DNN: Its RG claims are finite-dimensional, finite-cutoff complexity statements rather than continuum-construction or scale-uniform results.They do not establish reflection positivity, Gaussianization, or a Yang–Mills mass gap.
A.1 Structural analogy between finite-cutoff RG and feature-learning DNN: The intended use is to layer pointwise local-chart/global-atlas complexity over a finite RG map when stability, curvature, and truncation estimates are available.Model-specific Ising/Φ4 and Yang–Mills estimates remain separate inputs.

A.2 Pointwise complexity of composite renormalization maps

The appendix derives pointwise complexity bounds for composite RG maps by telescoping finite replacements, controlling them with secant-response Grams, and assigning hierarchical local-chart/global-atlas priors.

A.2 Pointwise complexity of composite renormalization maps: An exact hybrid-trajectory telescoping identity decomposes the difference between two coupling sequences into one-scale RG replacements.Each consecutive hybrid changes only one scale, providing the basis for metric domination.
A.2 Pointwise complexity of composite renormalization maps: The resulting metric is controlled by finite-scale secant response Grams under later-flow stability and one-step replacement domination.Cauchy–Schwarz introduces a factor depending on the number of RG levels when the increments are summed.
A.2 Pointwise complexity of composite renormalization maps: For exponential-family RG, the secant Gram is the Gram matrix of finite-scale response functions, making it the precise analogue of a learned DNN feature Gram.Unlike DNN metrics, the generic RG Gram acts on coupling vectors and lacks Kronecker repetition without extra channel structure.
A.2 Pointwise complexity of composite renormalization maps: The hierarchical prior combines phase labels, effective ranks, reference subspaces, and local Euclidean charts to lower-bound neighborhood mass uniformly over trajectories.Its local term is effective dimension, while its atlas term pays for making the prior independent of the realized trajectory.
A.2 Pointwise complexity of composite renormalization maps: Directions whose response eigenvalues fall below the finite resolution are excluded, while relevant and marginal directions remain active in the pointwise complexity sum.The construction is the RG counterpart of the DNN Riemannian-dimension calculation.
A.2 Pointwise complexity of composite renormalization maps: The framework leaves atlas-cost control explicit because balancing global and local costs requires physical operator structure absent from a generic RG coupling representation.The nonconvex phase-atlas example supplies an instance of such cost balancing without DNN-style matrix structure.

A.3 A finite nonconvex phase-atlas example

The finite phase-atlas construction shows how stable local charts yield anisotropic Gaussian concentration even when the global mixture is nonconvex, with selected-phase bounds potentially beating full-class covers.

A.3 A finite nonconvex phase-atlas example: A globally multimodal measure can be analyzed through stable phase charts whose local fluctuation integration has Schur-complement curvature.The resulting local Gaussian or ellipsoidal cost is supplemented by the code length of the phase/subspace atlas.
A.3 A finite nonconvex phase-atlas example: Under chartwise strong convexity, coarse marginals form phase-atlas mixtures and centered linear processes are sub-Gaussian with an anisotropic comparison metric.Pointwise envelopes follow from chaining and peeling, while simultaneous phase control adds an atlas code through the allocated failure probabilities.
A.3 A finite nonconvex phase-atlas example: Selected-phase validation can be strictly smaller than a full-class cover when the prior assigns sufficient mass to the relevant phase.If the prior is uniform over all phases, the selected bound pays the same phase uncertainty and the atlas advantage disappears.
A.3 A finite nonconvex phase-atlas example: The explicit finite construction uses phase-indexed Gaussian coordinates and observable subfamilies to realize the selected-phase versus full-class comparison.Its mixture is genuinely non-log-concave, so the example is not reducible to one globally convex chart.
A.3 A finite nonconvex phase-atlas example: Pure-phase charts for finite-volume double-well Φ4 models satisfy the required positive-curvature condition, but a full decomposition also needs droplet or interface charts.The appendix therefore establishes chart-restricted applicability rather than a complete global double-well analysis.
A.3 A finite nonconvex phase-atlas example: The construction is a finite-cutoff bridge between convex concentration, high-dimensional geometry, and interacting-field intuition, not a solution to the KLS problem.It assumes stable charts with explicit cutoff curvature and obtains anisotropic Gaussian comparison locally rather than global dimension-free control.

B.1 Local time versus cover and blanket time

The section transfers pointwise Gaussian-field envelopes to local-time bounds through the second Ray–Knight theorem, yielding target-set cover and blanket criteria without first proving full cover.

Motivation: The construction is motivated by field-level questions where local observables are more informative than the scalar Gaussian supremum or global maxima.Examples include local times on graphs and local observables in constructive and lattice field theory.
Ray–Knight transfer: The second Ray–Knight theorem transfers simultaneous pinned-GFF envelope bounds into local-time estimates on a target set H.The method uses an independent pinned GFF copy and the identity at inverse local time.
Target-set envelope: A deterministic envelope for the pinned GFF on H yields, with probability at least 1 −δ, simultaneous local-time control for every x ∈H.The envelope may be obtained by restricting the field or by evaluating one ambient-field envelope on H.
Cover and blanket criteria: The resulting criterion guarantees target cover and controls local-time ratios under a small-envelope condition, strengthening ordinary cover-time information with a blanket-time comparison.The proof first bounds local times above and below, then derives visitation and ratio conclusions.

B.2 Separating examples: target subatlas versus full cover

Phase-star examples separate target-subatlas control from full-cover analysis: an ambient pointwise envelope preserves target code length and local-chart geometry, whereas full cover pays for all phases.

Collapsed star: Target cover has inverse-root-local-time quantile log |I| + Oδ(1), while full cover has quantile log N + Oδ(1).If log(|I|/q(I)) = o(log N), the direct target route is asymptotically smaller than validation through full cover.
Decorated phase-star: In decorated phase-stars, the envelope cost combines target-atlas code with a compressed within-chart term controlled by the clique conductance and size.The within-chart term is small when κ(K + 1) is large.
Separation: If E_I,K(δ)^2 = o(log N), selected target cover is asymptotically smaller than the full-cover route, whose obstruction remains log N + Oδ(1).Full cover requires visiting every phase center, producing the coupon-collector scale.
Relation to cover-time theory: The examples ask a local question distinct from global cover-time theory: whether local time on a selected target can be controlled before proving full cover.This is a strict separation from the global Ding–Lee–Peres cover characterization.
Pointwise versus global routes: An ambient pointwise envelope can be fixed before target selection and then evaluated on the selected subatlas, retaining dependence on log(|I|/q(I)).A full-cover proof discards this target dependence and pays the coupon-collector scale log N.

C Technical variants and Sudakov-type consequences

The section derives a localized Sudakov-type consequence from Bayesian algorithmic lower bounds, while identifying the localization condition needed for nearest-neighbor comparisons and distinguishing this route from classical multiscale theory.

Nearest-neighbor comparison: Nearest-neighbor comparison yields the global supremum relaxation, while localized priors produce a localized estimate when Vπ ≤ C0∆^2.The localization condition ensures the hard prior is spread at the testing radius.
Localization requirement: The variance condition Vπ ≲∆^2 is essential: without it, the Gaussian channel requires larger noise and the nearest-neighbor route loses the corresponding factor.This is a scope condition on the algorithmic comparison, not a cosmetic technical assumption.
Localized packing: The localized packing form applies to a 2∆-separated set contained in a C0∆-ball, connecting the comparison to finite local packings.The stated regime requires the packing size M to exceed a universal constant.
Fractional covering: Fractional-covering duality optimizes the small-ball term but does not remove the information-radius factor Vπ from the Bayesian lower bound.Thus fractional covering identifies an entropy-hard prior, while nearest-neighbor comparison additionally requires second moment of order ∆^2.
Sudakov relaxation: The Bayesian algorithmic lower envelope becomes a Sudakov-type obstruction after replacing exact ghost mass by class-wide small-ball mass and optimizing over localized priors.The unrestricted Sudakov and majorizing-measure lower bounds still require the classical Gaussian machinery.