How Much Data Does Nearsightedness Cost? Range-Indexed Minimax Rates for Vision Models

Convolutional networks see the world through a blur. Their effective receptive field, meaning the region of the input that measurably influences an output unit, is roughly Gaussian and widens only with the square root of depth. Statistical learning theory, meanwhile, tells us how fast any learner can improve with more data on a given problem class, through minimax rates: the best worst-case error achievable with $n$ samples. These two facts have never been joined. When a task requires relating two image regions a distance $r$ apart, we do not know how many extra training examples a model with a narrow effective receptive field needs, or whether a cheap global-routing module such as criss-cross attention fully removes the penalty.

This note proposes a function class of image targets indexed by an interaction range $r$, together with a matched pair of results. The first is a minimax rate for any estimator, in which the range costs only a logarithmic price. The second is a rate for estimators whose effective receptive field is a Gaussian of width $\sigma$, in which the range costs a data multiplier that grows like $\exp(k r^2/\sigma^2)$, where $k$ is the number of pixels per interacting patch. The prediction is sharp and cheap to falsify. On synthetic tasks, the logarithm of the extra data a local model needs should be linear in $r^2/\sigma^2$ with slope $k$. The rate should then serve as a diagnostic that ranks real architectures by data efficiency better than receptive-field size or parameter count does.

Core Claim

Take an $N \times N$ image $x$. Let $P_i(x)$ denote the $k$-pixel patch at location $i$. The target class $\mathcal{H}(\beta, k, r)$ contains functions

$$f(x) = \frac{1}{N^2}\sum_i g\big(P_i(x), P_{i+\delta}(x)\big),$$

where $g$ is a $\beta$-Hölder function on $2k$ inputs ("$\beta$-smooth": its derivatives up to order $\beta$ are bounded) and the offset $\delta$ is unknown with $|\delta| \le r$. Spatial locality is thus built in, but the relevant dependency may be long-range.

The first claim concerns an unconstrained learner. We conjecture that the minimax squared-error risk over $\mathcal{H}$ is of order $n^{-2\beta/(2\beta+2k)} + (\log r)/n$. The first term is the standard nonparametric rate in the patch-pair dimension $2k$, not the ambient dimension $N^2$. The second term comes from a Fano-type argument over the roughly $r^2$ candidate offsets. The range enters only logarithmically.

The second claim concerns a learner whose features see the partner patch through a Gaussian window. That patch is attenuated by $\varepsilon = \exp(-|\delta|^2/2\sigma^2)$. Rescaling an input block by $\varepsilon$ inflates the Hölder constant of the effective target by $\varepsilon^{-\beta}$. The minimax risk over a Hölder ball of radius $L$ scales as $L^{2d/(2\beta+d)} n^{-2\beta/(2\beta+d)}$ with $d = 2k$. Setting the two risks equal gives the data inflation

$$\frac{n_{\text{local}}}{n_{\text{global}}} \asymp \varepsilon^{-2k} = \exp\!\big(k|\delta|^2/\sigma^2\big).$$

The exponent of the rate is unchanged; only the constant explodes. A nearsighted model is therefore not "unable" to learn long-range structure. It is exponentially data-hungry for it, and this is the quantitative statement the literature lacks.

We state this bound for the lazy, kernel-like training regime, where the receptive field is fixed near its initialization profile. Whether it survives feature learning is an empirical question the program tests directly.

Relation to Prior Work

Two papers motivate the gap. Understanding the Effective Receptive Field in Deep Convolutional Neural Networks proves, via a random-walk and Central Limit Theorem argument, that the receptive field's influence is Gaussian with width $O(\sqrt{\text{depth}})$. It never asks what this costs in samples. We supply that cost and reuse its $\sigma$ as the parameter of our bound.

The optimality of kernel classifiers in Sobolev space shows that wide networks trained by gradient flow reach minimax rates governed by a smoothness $s$. It estimates $s \approx 0.486$ for MNIST and $s \approx 0.199$ for CIFAR-10. However, it treats images as unstructured vectors, so its rate has no notion of range. Our class adds exactly that index.

Two papers supply method. Minimax bounds for structured prediction uses Assouad's lemma to show that global accuracy on factor graphs is bounded by how well local pairwise potentials are learned. Our lower bound borrows its packing construction, but it replaces fixed graph neighbors with an unknown offset $\delta$, which is what continuous receptive-field mechanisms actually search over.

The manifold-adaptivity results in Diffusion Models are Minimax Optimal Distribution Estimators and Conditional Diffusion Models are Minimax-Optimal and Manifold-Adaptive for Conditional Distribution Estimation show that rates can depend on an intrinsic dimension rather than the ambient one. Our patch-pair dimension $2k$ plays that role. Unlike those papers, we constrain the estimator's connectivity rather than assuming unconstrained ReLU networks.

The architectures we analyze each claim to remove nearsightedness in a different way, which gives our theory distinct predictions for each:

Two further papers constrain the design and are not direct targets. EccoMamba shows that flattening images to one-dimensional scans breaks neighborhoods, which in our class splits a single offset $\delta$ into scan-dependent distances. Multi-Scale Vision Longformer mixes windowed attention with global memory tokens.

Research Program

The theoretical work has three parts. We first prove the unconstrained lower bound, via Fano over offsets combined with the standard Hölder packing on $2k$ dimensions. We then prove a matching upper bound with an estimator that selects the offset by held-out validation and then runs a local-polynomial fit on patch pairs. Finally, we prove the attenuation bound for kernel estimators whose kernel factorizes through a Gaussian spatial window. This last kernel stands in for a convolutional network in the lazy regime.

For criss-cross routing, the offset is realized as the composition of two axis-aligned hops. The open question is whether the intermediate feature, which aggregates a whole row, dilutes the specific partner patch. We will derive the rate when attention can select sharply, and measure the rate when it cannot. For oversized one-dimensional kernels, axis-aligned offsets should incur no penalty. Diagonal offsets require composing horizontal and vertical kernels, which is again a two-hop question.

The empirical work builds a synthetic generator for $\mathcal{H}(\beta, k, r)$. Backgrounds are textured, and labels come from a smooth $g$ of two patches at offset $\delta$. The generator controls $r$, $k$, $\beta$, and whether $\delta$ is axis-aligned or diagonal. For every architecture we trace learning curves, meaning excess risk against $n$ on log-spaced training sizes. From these curves we extract the data multiplier needed to reach fixed error targets. We measure each trained network's actual receptive-field width using the gradient-based procedure of Luo et al., both at initialization and after training, and feed both values of $\sigma$ into the prediction.

Baselines

The naive reference point is a purely local convolutional network whose theoretical receptive field is smaller than $r$. It cannot represent the target, so its excess risk should plateau regardless of $n$. This anchors the curves and checks that the synthetic tasks truly require range $r$.

The main local competitor is a deep ResNet-style convolutional network, with depth and dilation varied to sweep $\sigma$. This is the model the attenuation bound is about. Dilated variants are included because they are the cheapest practical fix for small receptive fields.

The strongest existing global-routing methods are CCNet, ParCNetV2-style oversized kernels, and SegFormer's Mix-FFN encoder. On real data, the numbers to beat come from SegFormer: SegFormer-B5 reports 84.0% mIoU on Cityscapes validation, and SegFormer-B4 reports 50.3% mIoU on ADE20K. CCNet reports 81.9% mIoU on Cityscapes test and 45.76% on ADE20K validation. We will not try to beat these full-data numbers. Our claims concern data efficiency, which those papers do not report; no reported result was found on Lacuna for reduced-data Cityscapes or ADE20K training of these models.

All models are matched in FLOPs, trained from scratch with the same augmentation, and given an identical hyperparameter search budget per training size. Every point is averaged over five seeds.

The key ablation isolates routing. We take one architecture and replace its global attention with windowed attention of radius below $r$, keeping parameters and compute fixed. A second ablation runs full dense self-attention with no convolutional stem, which is predicted to lose locality and pay a higher-dimensional rate.

"Beating" the baselines means something specific for a theory paper. On synthetic data, the fitted slope of log data-multiplier against $r^2/\sigma^2$ must fall within 25% of $k$ across at least three values of $k$. On real data, the range-indexed diagnostic must rank architectures by reduced-data mIoU with higher rank correlation than either measured receptive-field width alone or parameter count.

Why not just…?

Why not just measure the effective receptive field and correlate it with accuracy? That correlation cannot tell a representational failure from a data-hungry one. It also cannot say how the gap should change with $n$. Our bound predicts that the penalty sits in the constant, not the exponent. Local and global curves should therefore be parallel on log-log axes, offset by $\exp(k r^2/\sigma^2)$. Receptive-field width alone predicts nothing about the dependence on $k$. The varied-$k$ synthetic sweep is the experiment that separates the two accounts.

Why not just use dense self-attention everywhere? Our theory predicts that dense attention without a locality prior learns in a much higher effective dimension than $2k$. It should therefore lose at small $n$ even though it has no range penalty. This matches the observation in ConvFormer that hybrids trained from scratch do well on small medical datasets, including 0.925 mean Dice on MM-WHS CT. The dense-attention ablation tests this directly. If dense attention matches hybrids at small $n$ on our synthetic tasks, the locality half of the theory is wrong.

Why not just apply existing kernel minimax theory, as in Lai et al.? Fully connected kernel rates contain no $r$. A fully connected kernel model on our synthetic tasks should show no range effect, while convolutional kernels should show a strong one. Running the fully connected neural tangent kernel as a control makes this contrast visible.

Why not assume trained networks simply learn to widen their receptive field? This is a real threat, because the Gaussian result of Luo et al. describes the network near initialization. We handle it by predicting with both the initial and the trained $\sigma$. If the trained-$\sigma$ prediction fits and the initial one does not, the theory still holds, but with feature learning acting on $\sigma$ itself. If neither fits, the bound is confined to the lazy regime, and we will say so.

Decisive Experiments

Four checks settle the proposal. The first is the synthetic slope test: log data-multiplier against $r^2/\sigma^2$, for $k \in \{4, 9, 16\}$ and $\beta \in \{1, 2\}$. The prediction is linearity with slope near $k$ and learning-curve exponents unchanged by $r$.

The second is the axis-aligned versus diagonal offset test for CCNet and oversized-kernel models. The theory predicts no penalty on axis-aligned offsets and an extra penalty on diagonal ones, which would show up as a measurable anisotropy.

The third is transfer to real data. We train all architectures on 1/32, 1/8, and 1/2 of Cityscapes and ADE20K. We estimate each class's typical context distance from co-occurrence statistics of disambiguating classes, and check whether the per-class gap between local and global models grows with that distance as the attenuation formula predicts.

The fourth is a long-range stress test on SelvaBox. Its high-resolution tree crowns push the relevant range well past typical convolutional receptive fields.

If the synthetic slope test fails, the central claim is wrong. If it passes but the real-data ranking does not beat receptive-field width alone, the theory is correct but not yet useful, which is still a clear outcome.