Nonparametric Minimax Risk and the Varshamov–Gilbert Lemma

A minimax lower bound asks how well any estimator can perform over a class of possible functions. One approach selects many functions that are separated in the estimation loss but difficult to distinguish from the data. The Varshamov–Gilbert lemma supplies the combinatorial part of this construction: a large collection of binary vectors separated in Hamming distance.

We first set out the estimation models in which these lower-bound constructions are used. Briefly, for a standard statistical problem involving i.i.d. real-valued random variables \(X_1, \dots, X_n\), whose common distribution is absolutely continuous with respect to the Lebesgue measure on \(\mathbb R\), say we want to estimate its density function \(p : \mathbb R \to [0,\infty)\). If we think \(p\) belongs to some family of functions \(\{g(x,\theta): \theta \in \Theta \subset \mathbb R^k\}\), then we say the estimation problem is parametric. If the model permits an infinite-dimensional class of densities, the problem is nonparametric; the class may still be specified by smoothness or shape restrictions.

1. Preliminaries

For regression, consider the observation model: suppose \(\{(X_i,Y_i)\}_{1 \leq i \leq n}\) is a collection of independent observations (random variables) such that

\[\begin{aligned} Y_i = f(X_i) + \xi_i ~~,~~ X_i \in [0,1] ~. \end{aligned}\]

Here, \(f: [0,1] \to \mathbb R\) is prespecified (called the regression function), and \(\mathbb{E}[\xi_i\mid X_i]=0\) for all \(i\). As is typically the case, we suppose \(f \in \mathcal F\), where \(\mathcal F\) is a class of functions with no prespecified form. To approximate the model illustrated above, we consider a Gaussian white noise model of the form

\[\begin{aligned} \dif Y(t) = f(t) \dif t + \varepsilon \dif W(t) \quad t \in [0,1] ~,~ \varepsilon \in (0,1) \end{aligned}\]

for some function \(f \in \mathcal F\). We observe a sample path \(\mathbf X = \{ Y(t) : 0 \leq t \leq 1 \}\). We also observe a full infinite sequence of Gaussian observations

\[\begin{aligned} y_j = \int_0^1 \varphi_j (t) \dif Y(t) = \theta_j + \varepsilon \xi_j ~~,~ j \in \mathbb N ~. \end{aligned}\]

Here, \((\varphi_j)\) is a complete orthonormal basis of \(L^2[0,1]\), and \(\xi_j = \int_0^1 \varphi_j (x) \dif W(x)\) are i.i.d. standard normal random variables.

Assume \(f\in L^2[0,1]\), and define \(\theta_j=\int_0^1 f(t)\varphi_j(t)\,dt\). Integrating the white-noise equation against each deterministic basis function gives the sequence representation above. For any finite list of indices, the Wiener integrals are jointly Gaussian, centered, and satisfy

\[E(\xi_j\xi_k)=\int_0^1\varphi_j(t)\varphi_k(t)\,dt=\mathbf1\{j=k\}.\]

Their joint Gaussian law therefore makes them independent, not merely uncorrelated. Parseval's identity translates squared function-estimation error into sequence error: \(\|\hat f-f\|_2^2=\sum_j(\hat\theta_j-\theta_j)^2\) whenever \(\hat f,f\in L^2\). This is the connection used by sequence-space lower-bound constructions; equivalence of a general regression experiment with white noise requires additional conditions and is not asserted here.

1.1. Ancillary Technical Results

Let \(H(x,y) = \sum_{1 \leq i \leq n} \mathbb 1\{x_i \neq y_i\}\) for \(x,y \in \{0,1\}^n\) denote the Hamming distance. An important result that is frequently used in combinatorial arguments is the Varshamov-Gilbert lemma: it addresses the question of how massive can be the set of all binary sequences with pairwise Hamming separation proportional to the dimension.

Lemma 1 (Varshamov-Gilbert). Let \(m \geq 8\). Then, there exists a subset \(\{x_0,\dots,x_M\} \subset \Xi \triangleq \{0,1\}^m\) such that with \(x_0 = (0,0,\dots,0) \in \{0,1\}^m\),

\[\begin{aligned} H(x_j, x_k) \geq \frac{m}{8} ~~, \quad \text{for all }\: 0 \leq j < k \leq M ~, \end{aligned}\]

and \(M \geq 2^{m/8}\).

Proof. The construction is greedy: choose a vector, exclude its nearby neighbors, and repeat. Start with \(x_0=0\) and successively choose a binary vector outside all previously removed Hamming balls of radius \(D=\lfloor m/8\rfloor\). Stop when the excluded balls cover the cube. Since each choice excludes only a bounded number of vectors, covering the whole cube requires many choices. The selected vectors have pairwise distance at least \(D+1>m/8\). Each ball contains

\[V_m(D)=\sum_{i=0}^{D}\binom mi\]

points, including its center. Consequently,

\[(M+1)V_m(D)\geq2^m.\tag{1}\]

If \(B\sim\operatorname{Bin}(m,1/2)\), Hoeffding’s inequality gives

\[2^{-m}V_m(D)=\mathbf P(B\leq D)\leq e^{-9m/32}<2^{-m/4}.\]

One can verify the binomial estimate directly. Write \(B=\sum_{i=1}^m B_i\), with independent fair Bernoulli variables. For \(t>0\),

\[E e^{-t(B-m/2)}=\{\cosh(t/2)\}^m\le e^{mt^2/8}.\]

The inequality follows by integrating \(\tanh u\le u\) to get \(\log\cosh u\le u^2/2\). Since \(D\le m/8\), Markov's inequality gives

\[P(B\le D)\le\exp(-3tm/8+mt^2/8).\]

Taking \(t=3/2\) yields \(e^{-9m/32}\). The exponent is smaller than \(-m\log2/4\). Finally, put \(a=2^{m/8}\ge2\): then \(2^{m/4}=a^2\ge a+1\), so the estimate on the number of centers gives the stated estimate on \(M\), which excludes the initial center.

Hence \(M+1>2^{m/4}\geq2^{m/8}+1\) for \(m\geq8\), proving the claim. ◻