Stat.Concentration.VC

Given a real-valued function class on an observation space, a class index, and an observation-threshold pair, the strict subgraph classifier returns true exactly when the threshold is strictly below the selected function's value at the observation.

Given a real-valued function class on an observation space and a nonnegative integer $d$, the pseudo-dimension-at-most-$d$ property holds exactly when, for every finite collection of observation-threshold pairs, the VC dimension of the strict-subgraph labelings induced by the class on that collection is at most $d$.

Given a measure $Q$ on an observation space and two real-valued functions on that space, their measure-based $L^2$ semidistance is $\sqrt{\int (f-g)^2\,dQ}$.

Given a measure $Q$ on an observation space, a real-valued function class, a radius $r$, and a finite set of class indices, the open $L^2(Q)$ cover property holds exactly when every class member lies at strictly less than distance $r$ from a member indexed by that finite set.

Given a measure $Q$ on an observation space, a real-valued function class, a radius $r$, and a nonnegative integer $N$, the $L^2(Q)$ covering-number-at-most-$N$ property holds exactly when there is a finite set of at most $N$ class indices that forms an open $L^2(Q)$ cover at radius $r$.

Given a nonnegative integer $d$ and a real number $\varepsilon$, the explicit VC-subgraph cover bound is the least integer no smaller than $(16/\varepsilon)^{8(d+1)}$.

Given an observation space, an auxiliary parameter set $S$, an index set depending on the parameter, a parameter-indexed family of real-valued function classes, and a parameter-indexed envelope, the uniform polynomial $L^2$ covering property over $S$ holds exactly when there are one real entropy base and one nonnegative-integer exponent such that every parameter's class has the corresponding polynomial $L^2$ covering certificate with its designated envelope.

Given a real-valued function class on an observation space, an envelope $U$, an entropy base $A$, and an exponent $v$, the polynomial empirical $L^2$ covering property holds exactly when, for every positive sample size and every sample of that size, and for every radius $\varepsilon$ with $0<\varepsilon\le 1$, there is a finite index set forming an $L^2$ cover under the empirical measure at radius $\varepsilon U$ and its cardinality is at most $(A/\varepsilon)^v$.

Given an entropy base $A$, an envelope $U$, and a variance scale $\sigma$, the normalized logarithmic complexity is $\log(\max\{e,AU/\sigma\})$. This normalization makes the logarithm at least one.

Given an envelope $U$, a variance scale $\sigma$, an entropy base $A$, an exponent $v$, and a sample size $n$, the variance-adaptive VC-type rate is $\sigma\sqrt{vL/n}+vUL/n$, where $L=\log(\max\{e,AU/\sigma\})$.

The fixed numerical constant for the variance-adaptive VC-type expected maximal inequality is $16384$.

Given an index set of coefficients and a real bound, the coefficient box is the set of real coefficient vectors indexed by that set for which every coordinate has absolute value at most $B$.

Given a finite index set, a real-valued feature family, a coefficient bound, a coefficient vector in the corresponding box, and an evaluation point, the linear parameter class evaluation is the sum of each coefficient times its corresponding feature value at that point.

Given a Boolean classifier family and a natural number, the property of having VC dimension at most that number means that, for every finite sample, the VC dimension of the label patterns realized on that sample is at most $d$.

Given a natural dimension, the Euclidean point space is the real Euclidean space of that dimension.

Given a natural dimension, the point-radius space is the set of pairs consisting of a point in the corresponding real Euclidean space and an arbitrary real radius threshold.

Given a natural dimension, a center point, and a point together with a radius threshold, the moving-center closed-ball classifier returns true exactly when the point lies at distance no greater than the threshold from the center.

Given a natural dimension, a center point, and a point together with a radius threshold, the moving-center exterior classifier returns true exactly when the point lies at distance strictly greater than the threshold from the center.

Given a natural dimension, the closed-ball parameter space is the set of pairs consisting of a point in that real Euclidean space and a nonnegative real radius.

Given a natural dimension, a closed-ball parameter, and a point in the corresponding Euclidean space, the closed-ball classifier returns true exactly when the point lies in the closed ball specified by that parameter.

Given a natural dimension, a bandwidth, two relative annulus endpoints, a natural-number degree, a center point, and an evaluation point, the radial annulus monomial equals $(\operatorname{dist}(z,x)/q)^k$ when the distance to the center lies between $aq$ and $bq$, and is zero otherwise.

Given a natural dimension and a maximal natural-number degree, the radial-monomial parameter space consists of a center in that Euclidean space paired with a degree from zero through $p$.

Given a natural dimension, a maximal degree, a bandwidth and two relative annulus endpoints, a center-and-degree parameter, and a Euclidean evaluation point, the radial-monomial class maps that parameter and point to the corresponding radial annulus monomial.

Given a natural dimension, the fixed-degree radial pseudo-dimension bound is the explicit Boolean-combination bound $2^{3(d+3)+1}$.

Given a natural dimension and a maximal degree, the radial pseudo-dimension bound is the explicit finite-union bound $2^{(p+1)(2^{3(d+3)+1}+1)+1}$ obtained by combining $p+1$ fixed-degree bounds.

For an upper relative radius $b$ and a nonnegative integer $p$, the radial-monomial envelope is $(\max\{1,b\})^p$.

Given an observation space $\Omega$, a Euclidean dimension $d$, a maximum degree $p$, a location map from observations to $d$-dimensional Euclidean space, a bandwidth $q$, annulus radii $a$ and $b$, a radial-monomial parameter θ, and an observation $\omega$, the radial monomial evaluated at that observation is the corresponding radial-monomial class function evaluated at the mapped location.

For a sample of $n$ observations in a measurable space, the finite-sample measure assigns equal mass $1/n$ to each observation, equivalently forming the normalized sum of point masses at the observations (with the displayed formula also determining the value when $n=0$).

For a measure on a measurable sample space, a class of real-valued functions indexed by a set, an envelope bound, a radius, a covering constant, and an entropy exponent, the class has uniform VC-type entropy exactly when (1) the radius is positive, (2) the radius is strictly smaller than the envelope bound, (3) the covering constant is at least $e$, (4) the entropy exponent is at least one, (5) every function in the class is measurable, (6) every function is bounded in absolute value by the envelope bound at every sample point, (7) every function has population $L^2$ distance at most the radius from the zero function, and (8) for every sequence of indices, the resulting sequence of functions has the stipulated polynomial empirical $L^2$ covering property.

For a measure on a measurable sample space, a class of real-valued functions, a countable enumeration of that class, and a finite sample, the countable empirical-process supremum is the extended nonnegative real supremum, over the enumerated functions, of the absolute centered empirical average.