Approximation Theory for Dropout Neural Networks: Sobolev Rates and Confidence Bounds

Background: Beyond Universal Approximation

The Universal Approximation Property of neural networks tells us that a sufficiently wide or deep network can approximate any continuous function. But this classical result has a blind spot that is often overlooked: it says nothing about a far more practical question — how large does a network actually need to be to achieve a given accuracy? When Dropout is introduced as a stochastic regularization mechanism — where each edge is independently retained with probability $p$ — the problem becomes considerably more subtle. Whether a randomly sampled network can reliably produce a high-accuracy approximation is no longer a deterministic guarantee; it becomes a probabilistic statement.

This arXiv preprint (arXiv:2610.02253v1) addresses precisely this gap. The authors focus on target functions drawn from the unit ball of the Sobolev space $W^{n,\infty}([0,1]^d)$, and study how well ReLU networks with Dropout can approximate them, measuring approximation quality via uniform error over the entire input domain.

The Sobolev space $W^{n,\infty}([0,1]^d)$ is the standard setting for function approximation theory. Intuitively, functions in $W^{n,\infty}$ are not only continuous — all their partial derivatives up to order $n$ are bounded in the $L^\infty$ sense, endowing them with well-controlled smoothness. The parameter $n$ can be thought of as the "smoothness order" and $d$ as the input dimension. This space is a natural choice: it is general enough to cover smooth function classes that arise in practice, yet classical approximation rate theory is well developed for it. In the deterministic (no-Dropout) setting, the optimal approximation rate — parameterized by $\varepsilon^{-d/n}$ in terms of parameter complexity — was established long ago by Barron, DeVore, and others. This paper asks exactly how much additional cost Dropout incurs on top of that baseline.

Core Setup: Approximation with Probabilistic Guarantees

The key to understanding this work lies in its error metric. Traditional approximation analysis targets deterministic networks, whereas here the focus is on the behavior of a single sampled network. Specifically, the authors require that the approximation error holds uniformly over the entire domain $[0,1]^d$, and that this guarantee is valid with probability at least $1-\delta$ over a randomly sampled network.

This setup closely mirrors how Dropout is actually used: during inference or training, network connections are randomly dropped, and we want the network to reliably accomplish the approximation task even under this randomness. The parameter $\delta$ quantifies the "failure probability" — what fraction of sampled networks are permitted to fall short of the target accuracy.

The Constructive Upper Bound

The authors' positive result is an explicit network construction. They prove that there exists a network of constant depth and size

$$\widetilde O_{n,d}\left(p^{-9}\varepsilon^{-\max{d/n,2}} \log(1/\delta)\right)$$

that satisfies the above probabilistic approximation requirement. This expression contains three key factors:

• Dependence on retention probability $p^{-9}$: The lower the Dropout retention probability, the more sharply the required network size grows — as a ninth power.
• Accuracy exponent $\varepsilon^{-\max{d/n,2}}$: This reflects the curse of dimensionality — when the input dimension $d$ is large relative to the smoothness order $n$, the exponent is dominated by $d/n$; otherwise it is floored at the constant 2.
• Confidence factor $\log(1/\delta)$: The logarithmic cost means that improving reliability is relatively cheap.

The construction combines three technical ingredients: bounded local sub-networks, localization over "successful approximation events," and multiscale Taylor decomposition. The overall strategy is to use low-degree polynomials for local approximation in each patch, stitch them together across multiple scales to cover the full domain, and employ redundancy to guard against random failures caused by Dropout.

Multiscale Taylor decomposition is the central technique for constructing the upper bound. The basic idea is: on each local patch, use the $n$-th order Taylor expansion of the target function as a polynomial approximation, with the error controlled by the patch size and the bound on $n$-th order derivatives. The domain $[0,1]^d$ is then divided into small patches, and local ReLU sub-networks are built on each one to realize the corresponding polynomial. "Multiscale" refers to the fact that, to guard against Dropout failures, multiple redundant copies of each local sub-network are deployed at different levels of redundancy matching different failure probabilities. This redundancy design is the source of the high-degree $p^{-9}$ dependence — each approximation step requires that at least one copy survives with high probability, and the multiplicative effect of multiple such steps accumulates, ultimately manifesting as a high-power dependence on $p$.

Lower Bounds: The Unavoidable Cost of Randomness

An upper bound alone is insufficient to tell the full story — what makes the result truly valuable is a matching lower bound. The authors establish the necessity of network size from two angles.

The first comes from Sobolev capacity constraints, which impose a lower bound on the number of "surviving edges" — no matter how the network is designed, the number of retained edges required to achieve target accuracy cannot be too small. The second is more illuminating: even for approximating a fixed affine function, achieving sufficiently high confidence requires that the output layer incur a cost of at least

$$\frac{1-p}{p},\varepsilon^{-2}\log(1/\delta)$$

This result is elegant. It reveals precisely how the randomness of Dropout translates into computational cost. When the retention probability $p$ is small, the term $(1-p)/p$ grows large, showing that a high Dropout rate necessarily demands a more redundant output layer — a hard constraint imposed by the variance of random sampling.

When Do Upper and Lower Bounds Match?

The scientific value of theoretical work depends heavily on whether upper and lower bounds align. The authors give explicit matching conditions:

For fixed $p\in(0,1)$ and $\delta<\min{1/2,1-p}$, under a fixed or logarithmic depth budget, the upper and lower bounds agree exactly in terms of the accuracy exponent. Furthermore, when $d\leq 2n$ (i.e., the smoothness order is sufficiently high relative to the dimension), they also match in terms of confidence dependence, up to logarithmic factors in accuracy.

This means that within these parameter regimes, the construction given in the paper is "optimal" in terms of order of magnitude — no asymptotically significantly smaller network exists.

Sobolev capacity is a tool from functional analysis for quantifying the "information content" of a function class. The core idea is: if the target function class is sufficiently complex (containing enough mutually distinguishable functions), then any approximation scheme must use a sufficient number of parameters (or "surviving edges") to tell them apart. In the Dropout setting, the capacity lower bound translates into a constraint on the expected number of surviving edges — even if the total number of edges is large, if each is retained only with probability $p$, then the number of edges that can carry information in expectation is limited. This perspective bridges combinatorial information theory and probabilistic analysis, and is the standard route to lower bounds on total network size.

Matching upper and lower bounds in theoretical research means that the construction has achieved information-theoretic optimality: no asymptotically more efficient scheme exists. The matching here holds in the $\widetilde O$ sense (i.e., up to polylogarithmic factors), not as an exact equality. The condition $d \leq 2n$ means that the function's smoothness is high enough relative to the input dimension, so the complexity of the function class is not entirely dominated by the curse of dimensionality, allowing the upper and lower bounds to also align in their confidence dependence (i.e., the $\log(1/\delta)$ term). When $d > 2n$, a gap in the confidence dependence remains unresolved — this corresponds to one of the open problems left by the paper. Whether the $p^{-9}$ factor in the current upper bound is optimal, and the precise characterization of logarithmic factors in the high-dimensional, low-smoothness regime, await future work.

Extensions and Open Problems

Beyond the main results, the authors extend their lower bounds to a more general setting: approximating targets in $W^{n,r}$ with $L^s$ error. They explicitly distinguish this extension from the upper bounds for the $W^{n,\infty}$ case, showing that the choice of error metric and target function space materially affects the conclusions.

The paper also honestly leaves open problems on the table: the optimal dependence on the retention probability $p$ (whether the $p^{-9}$ factor in the upper bound can be improved) and the precise characterization of logarithmic factors remain unresolved, pointing the way for future research.

Significance and Outlook

The value of this work lies not in proposing a new network architecture, but in establishing a non-asymptotic, probabilistically guaranteed approximation theory for Dropout — a widely used technique. It refines the qualitative statement that "networks can approximate" into the quantitative question of "how large a network is needed, and with what probability does it succeed," providing matching upper and lower bounds over a fairly wide range of parameters.

For theorists, results of this kind fill an important gap in the approximation theory of stochastic networks. For practitioners, they carry a concrete message: excessively high Dropout rates (i.e., very small $p$) exact a steep price in approximation capacity, a tradeoff worth considering when designing regularization strategies. Of course, as a theoretical preprint, the conclusions remain within a rigorous mathematical framework and are still some distance from directly guiding engineering practice.