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

• URL: http://arxiv.org/abs/2606.07931v1
• Date: Sat, 06 Jun 2026 01:50:06 GMT
• Title: Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation
• Abstract summary: We prove a variance-aware pointwise majorizing-measure theorem for centered Gaussian processes.<n>The theorem provides a reusable field-level refinement of classical generic chaining.<n>We show that algorithmic lower bounds provide local-geometric certificates of pointwise complexity for fixed estimators.
• Score: 5.082462420126421
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 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.

Related papers

• Local and Global Contraction Principles for MCMC Mixing [2.889268075288957]
  We develop a contraction-based framework for proving mixing-time bounds for Monte Carlo algorithms.<n>For Langevin Langevin's compact convex domain, we show an explicit global contraction coefficient.<n>We recover sharp existing moment-based convergence rates when $mathbb E_q[wp]infty$ for somep regimes $p1$ where no finite moment exists.
  arXiv  Detail & Related papers  (2026-06-02T02:16:52Z)
• Intrinsic Wasserstein Rates for Score-Based Generative Models on Smooth Manifolds [61.14405512940818]
  We show that Score-based generative models are trained in high-dimensional ambient spaces.<n>We use a ReLU implementation of nearest-projection coordinates via finite intrinsic anchors and Gauss Newton.
  arXiv  Detail & Related papers  (2026-05-15T10:20:05Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs [8.162867143465382]
  We leverage our technique to establish reduction-based computational lower bounds for several canonical high-dimensional statistical models under widely-believed conjectures in average-case complexity.<n>We show that computational lower bounds proved for spiked tensor PCA with Gaussian noise are universal, in that they extend to other non-Gaussian noise distributions within our class.
  arXiv  Detail & Related papers  (2025-10-08T17:16:36Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians [2.311583680973075]
  We study the problem of computationally efficient robust estimation of the covariance/scatter matrix of elliptical distributions.<n>We obtain the first efficiently computable, nearly optimal robust covariance estimators that extend beyond the Gaussian case.
  arXiv  Detail & Related papers  (2025-02-10T15:31:57Z)
• SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications [37.208622097149714]
  We prove that there is a universal constant $C>0$ so that for every $d inmathbb N$, every centered subgaussian distribution $mathcal D$ on $mathbb Rd$, and every even $p inmathbb N$, the $d-optimal inmathbb N$, and the $d-optimal inmathbb N$. This establishes that every subgaussian distribution is emphS-certifiably subgaussian -- a condition that yields efficient learning algorithms for a wide variety of
  arXiv  Detail & Related papers  (2024-10-28T16:36:58Z)
• Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
  We introduce a new adaptive $k$-nearest neighbours ($kK$-NN) algorithm that explores the local curvature at a sample to adaptively defining the neighborhood size. Results on many real-world datasets indicate that the new $kK$-NN algorithm yields superior balanced accuracy compared to the established $k$-NN method.
  arXiv  Detail & Related papers  (2024-09-08T13:08:45Z)
• Optimal score estimation via empirical Bayes smoothing [13.685846094715364]
  We study the problem of estimating the score function of an unknown probability distribution $rho*$ from $n$ independent and identically distributed observations in $d$ dimensions. We show that a regularized score estimator based on a Gaussian kernel attains this rate, shown optimal by a matching minimax lower bound.
  arXiv  Detail & Related papers  (2024-02-12T16:17:40Z)
• Noise Stability Optimization for Finding Flat Minima: A Hessian-based Regularization Approach [18.009376840944284]
  We present an algorithm that can effectively regularize the Hessian loss matrices leading to regions with bound loss surfaces. Our approach is effective for improving generalization in pretraining CLIP and chain-of-thought fine-tuning datasets.
  arXiv  Detail & Related papers  (2023-06-14T14:58:36Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Order-Optimal Error Bounds for Noisy Kernel-Based Bayesian Quadrature [42.129843613950285]
  We consider functions in a em Reproducing Kernel Hilbert Space (RKHS) with the Mat'ern-$nu$ kernel. We find that when the black-box queries are subject to Gaussian noise having variance $sigma2$, any algorithm making at most $T$ queries must incur a mean absolute error of $Omega(T-fracnud-1 + sigma T-frac12)$.
  arXiv  Detail & Related papers  (2022-02-22T01:49:41Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.