PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximation Property of Dropout Neural Networks: Sobolev Rates and Confidence Bounds

Jia-He Yao

arXiv:2610.02253v1cs.LGcs.NAmath.NA

TL;DR

The paper asks how large a dropout network must be for one random realization to approximate a Sobolev target uniformly, given that edge deletion adds variability to deterministic approximation. It combines localized local modules with a multiscale Taylor construction and proves complementary lower bounds, matching the accuracy exponent under fixed or logarithmic depth budgets.

  • Problem

    For dropout networks, deterministic expressivity alone does not specify the size needed to control random variation while one sampled network approximates the target uniformly.

    Source: §1 · p. 3

  • Method

    The construction combines localization on successful approximation events with bounded local subnetworks and a multiscale Taylor-difference decomposition.

    Source: §1 · p. 3, §9.1 · p. 23

  • Results

    The upper and lower bounds match in the accuracy exponent under fixed or logarithmic depth budgets, and for d ≤ 2n they match in confidence up to accuracy logarithms.

    Source: §1 · p. 3, §9 · p. 22

  • Takeaways & Limitations

    Spatial capacity and random output fluctuation impose separate necessary costs, and the construction meets them at the larger polynomial order rather than their product.

    Source: §9 · p. 22

    The optimal retention dependence and logarithmic factors remain open, and optimality of the sufficient confidence range for the full Sobolev class is unproved.

    Source: §9 · p. 23

Abstract

from arXiv · show

The universal approximation property of dropout neural networks does not by itself describe the network size required for an accurate random realization. In this work, we study approximation of the unit ball of $W^{n,\infty}([0,1]^d)$ by ReLU networks whose edges are retained independently with probability $p$. The approximation error is measured uniformly over the input domain, and the guarantee holds with probability at least $1-\delta$ for a single sampled network. We construct networks of constant depth and size $\widetilde O_{n,d}(p^{-9}\varepsilon^{-\max\{d/n,2\}} \log(1/\delta))$. The construction combines bounded local subnetworks, localization on a successful approximation event, and a multiscale Taylor decomposition. Conversely, Sobolev capacity imposes a lower bound on the number of surviving edges, while approximation of a fixed affine function requires an output-layer cost of order $((1-p)/p)\varepsilon^{-2}\log(1/\delta)$ at sufficiently high confidence. For fixed $p\in(0,1)$ and $\delta<\min\{1/2,1-p\}$, the upper and lower bounds match in the accuracy exponent under a fixed or logarithmic depth budget. When $d\leq2n$, they also match in confidence up to logarithms of accuracy. We extend the lower bounds to $W^{n,r}$ targets with $L^s$ error, and distinguish this extension from the upper bound for $W^{n,\infty}$. The optimal retention dependence and logarithmic factors remain open.

1 Introduction

This work studies how network size and random deletion jointly affect uniform approximation by dropout networks. It develops a constant-depth construction and complementary lower bounds for Sobolev targets, identifying when their accuracy exponents match.

1 Introduction

  • Independent edge dropout retains each edge with probability p, and the same sampled network must approximate the target uniformly over all inputs.Weights are chosen before masks are sampled, making this stronger than pointwise accuracy in expectation.Source: §1 · p. 3
  • For fixed p and sufficiently high confidence, the construction accommodates spatial and random-fluctuation costs at the larger accuracy exponent, up to logarithmic factors.The relevant exponent is max{d/n, 2}.Source: §1 · p. 3
  • The construction uses bounded local subnetworks, localization on successful approximation events, and differences between successive Taylor resolutions.Small fine-scale corrections need lower relative precision, while summing within scales preserves that saving.Source: §1 · p. 3
  • The lower bounds identify two distinct costs: Sobolev capacity requires enough surviving edges, while even an affine target requires order ε^-2 log(1/δ) incoming output edges at fixed p.The affine-target bound allows arbitrary hidden depth and arbitrary real weights.Source: §1 · p. 3
  • The upper bound matches the lower-bound accuracy exponent under fixed or logarithmic depth, and for d ≤ 2n the confidence dependence also matches up to accuracy logarithms.For d > 2n, the corresponding joint lower bound is not established.Source: §1 · p. 3

2 Related Work

The paper places its results alongside deterministic approximation, capacity estimates, and work on random networks, while distinguishing those questions from uniform approximation by one dropout realization. It presents the quantitative bounds—not the underlying tools—as its contribution.

2 Related Work

  • Yarotsky [11] provides the local Taylor and arithmetic-implementation starting point, but independent edge deletion also randomizes connections that merely copy intermediate values.This prevents direct use of the deterministic implementation.Source: §2 · p. 4
  • The analysis applies Bartlett et al.’s capacity estimates to deterministic dropout realizations after removing constant graph parts, and uses Siegel’s [7, Theorem 22] for a finite-integrability lower-bound extension.The Siegel result is a deterministic approximation tool, not a dropout-specific lower bound.Source: §2 · p. 4
  • Manita et al.’s masked-subnetwork identity is used only for a fixed-size local window and clipped coordinate, since applying it to the whole network would cost exponentially in its edge count.Bounded masked subnetworks with common breakpoints permit uniform concentration without paying for the window slope.Source: §2 · p. 4
  • Fault-tolerance, training, and statistical-estimation studies address different questions from optimizing for a Sobolev ball and requiring one realization to succeed uniformly over inputs.The paper also distinguishes its unrestricted-real-weight network class from bounded, sparse, or quantized network comparisons.Source: §2 · p. 4
  • The paper does not claim novelty for the algebraic debiasing identity, deterministic capacity estimates, or local Taylor representation; its quantitative bounds are assessed under a common model.The literature comparisons do not settle publication priority for those bounds.Source: §2 · pp. 4–5

3 Theoretical Contributions and Common Mechanisms

The section explains how spatial resolution and random fluctuation set separate approximation costs, then describes construction choices that avoid multiplying those costs. Localization, local debiasing, and a multiscale decomposition preserve the larger polynomial order under stated conditions.

3.1 Spatial complexity and random fluctuation

  • A resolution h entails order h^-d local pieces and Taylor remainder h^n, while independently retained output contributions impose an additional redundancy cost.The two necessary costs combine through their maximum, not their product; the construction meets that larger polynomial order.Source: §3.1 · p. 5

3.2 Localization on the event that matters

  • Localization is required only on the successful approximation event: shifting the last bias of a globally accurate nonnegative local module makes it vanish wherever its target is zero on that event.This limits contributing errors to the bounded number of overlapping branches and supports composition at random inputs.Source: §3.2 · p. 5

3.3 Why a narrow window need not be expensive

  • A narrow window’s large slopes need not raise the reliability cost when the whole small circuit is debiased, because its masked outputs are bounded and its affine-piece count is independent of window width.Uniform concentration is controlled by common breakpoints, not their locations or slopes; the argument uses unrestricted weight magnitudes.Source: §3.3 · pp. 5–6

3.4 Small corrections require fewer copies

  • The construction implements differences between Taylor resolutions rather than only the finest approximation, assigning fewer copies to smaller-amplitude corrections.At scale j, there are O(2^jd) terms of amplitude O(2^-jn), yielding the max{d/n, 2} exponent up to retention and logarithmic factors.Source: §3.4 · p. 6
  • For local accuracy cost η^-β, the scale accounting formally gives exponent max{d/n, β}, conditional on uniform local modules, bounded overlap, and a saving-preserving summation.The paper verifies these conditions for β = 2, not for other noise models.Source: §3.4 · p. 6
  • Summing positive and negative terms within each scale limits the final module to 2(J + 1) values; connecting every branch directly to one final module would lose the multiscale saving.The direct-connection alternative restores a factor equal to the total number of branches.Source: §3.4 · p. 6

4 Preliminaries and Main Results

The section defines independent edge dropout and a worst-case size budget for uniform approximation by a single sampled network. It states matching accuracy exponents under specified depth and confidence conditions, with a separate confidence match only when d ≤ 2n.

Preliminaries

  • Each edge, including edges into the scalar output, is independently retained with probability p; biases are unmasked, and network weights are fixed before sampling.Size counts edges, non-input units, and one additional unit; depth counts computational layers including the output.Source: §4 · p. 6
  • The worst-case size budget requires that each target admit an architecture and weights whose sampled network approximates it uniformly with probability at least 1 − δ.The architecture may depend on the target function.Source: §4 · p. 7

Main results

  • The matching accuracy exponent is max{d/n, 2} for the stated depth range; a fixed depth cap at least L_n,d also suffices.The scaling is stated up to powers of log(1/ε).Source: §4 · p. 8
  • For d ≤ 2n, the joint accuracy and confidence bounds match up to accuracy logarithms; the corresponding joint lower bound is not established for d > 2n.The results do not establish optimal logarithmic factors or optimal dependence on p.Source: §4 · p. 8

5 Lower Bounds for Random Approximation

The lower bounds separate deterministic Sobolev capacity from the extra redundancy required for random output edges. Together they constrain accuracy and confidence, but do not multiply the two costs.

5.1 The output-layer obstruction

  • For f0(x) = (1 + x1)/2, any network uniformly approximating it with probability at least 1−δ has at least m ≥ 1−p incoming output edges, with hidden depth and weights unrestricted and output affine or ReLU.Source: §5.1 · p. 10
  • For p ≥ 1/2, one edge reproduces f0 exactly with probability p, so the strict confidence threshold cannot generally be removed.This exception does not contradict the Sobolev capacity lower bound, which uses other hard functions.Source: §5.1 · p. 10

5.2 The Sobolev capacity obstruction

  • The Sobolev capacity bound uses localized smooth functions to force deterministic networks to realize many sign patterns, then applies VC-dimension bounds.A successful mask can depend on the target; no common successful mask is required.Source: §5.2 · p. 11

5.3 Counting retained edges

  • Every successful realization for a hard Sobolev target must retain at least K edges, yielding a binomial necessary condition on retained edges and original network size.The target and K can be chosen independently of p and δ; having K retained edges is not claimed sufficient for success.Source: §5.3 · pp. 12–13
  • The retained-edge argument gives depth-dependent lower bounds on original size, using VC-dimension bounds for masked deterministic networks.After masking, a realization with k retained edges can be represented with at most k edges and k + 1 non-input units.Source: §5.3 · pp. 11–12
  • For a budget that must cover the whole Sobolev ball, the two lower bounds combine by taking their maximum, not their product.The capacity and affine-target bounds may use different targets.Source: §5.3 · p. 13

6 Approximation of Basic Functions

The construction develops bounded random modules for basic operations, then combines them using localization that is required only on successful approximation events. These modules support uniform approximation without relying on protected edges or all-mask support preservation.

6.1 Affine combinations

  • Affine combinations of nonnegative inputs can be uniformly approximated with one hidden layer, with cost scaling as p^-2 ε^-2 log(1/δ) times the weighted input size.The estimate remains valid when inputs come from an earlier random module on its successful event.Source: §6.1 · p. 13

6.2 Localization and composition

  • A nonzero ReLU-output network cannot preserve a local function’s support for every mask, so localization is instead enforced on the successful approximation event.Subtracting η from the output bias gives 0 ≤ H_R ≤ q, error at most 2η, and H_R(x) = 0 wherever q(x) = 0.Source: §6.2 · p. 14
  • Composition with high-probability localization controls outer error by the active overlap count and inner accuracy, plus the outer approximation error.For k active coordinates, the stated bound is 2kL_ρη + ε_out.Source: §6.2 · pp. 14–15

6.3 A two-layer square module with every edge masked

  • The two-layer square module obtains a uniform error bound by concentration on a grid, then uses monotonicity to extend the estimate between grid points.The resulting uniform error is at most η without requiring a Lipschitz bound on bad random realizations.Source: §6.3 · p. 15

6.4 Multiplication, signs, and transmission between layers

  • Nonnegative multiplication is implemented in six layers by combining affine, square, and affine-ReLU modules, with size at most CRp^-2η^-2 log(CR/(ηζ)).All edges, including those carrying values between stages, are independently masked.Source: §6.4 · p. 16

6.5 Bounded subnetworks and uniform debiasing

  • For fixed-size bounded scalar circuits, debiasing and concentration over common breakpoints yield uniform approximation without a cost tied to breakpoint locations or weight magnitudes.Fixed-size bounded circuits avoid the exponentially many subnetworks that would arise from applying the same subset expansion to a full network.Source: §6.5 · pp. 16–18

6.6 A local module uniform in the spatial resolution

  • Windows and clipped coordinates admit bounded-depth uniform dropout approximations whose constants do not depend on their scale parameters.The local module combines these factors with multiplication and a final signed affine-ReLU module; its cost is dominated by p^-9.Source: §6.5 · p. 17, §6.6 · p. 18

7 Approximation of Sobolev Functions

The upper bound combines local Taylor approximations across resolutions while keeping the random implementation’s summation cost controlled. Small normalized Taylor differences and summation within each scale yield a constant-depth construction.

7 Approximation of Sobolev Functions

  • For fixed n,d ≥1, Theorem 7.1 gives every f ∈ F_{n,d}, 0<p≤1, and 0<ε,δ≤1/2 a network of depth at most L_{n,d} and a size upper bound.The suppressed factors are powers of 1 + log(1/ε); optimality of the power of p and logarithmic factors is not asserted.Source: §7 · p. 19

7.1 Taylor differences have small normalized coefficients

  • Successive Taylor-resolution differences have small normalized coefficients, allowing each scale’s terms to be represented as signed localized products with bounded overlap.The normalized coefficient scale is a_j = A*2^-jn.Source: §7.1 · pp. 19–20

7.2 Network assembly without an expensive global summation

  • Summing within each level before combining levels avoids the unnecessary product of the total number of branches and ε^-2.The geometric sum is bounded for d < 2n, equals J + 1 for d = 2n, and is O_{n,d}(ε^-(d-2n)/n) for d > 2n.Source: §7.2 · p. 21

8 Other Sobolev Integrability and Error Norms

The lower-bound extension covers finite Sobolev integrability with L^s error, while the earlier upper construction remains for W^{n,∞} targets. For that original target class, its uniform guarantee also implies L^s guarantees on the unit-volume domain.

8 Other Sobolev Integrability and Error Norms

  • For finite r, the paper does not supply a corresponding upper bound for the larger W^{n,r} target class.The earlier uniform construction is for W^{n,∞}.Source: §8 · p. 21
  • The lower bounds extend to W^{n,r} targets with L^s error, including a retained-edge necessary condition of the same order.The result gives necessary costs only and makes no claim about approximation in a derivative norm.Source: §8 · pp. 21–22
  • The stochastic lower bound uses the affine target f0 and yields an output-edge cost of order (1 − p)ε^-2 log(1/δ)/p.The capacity and stochastic necessary costs are combined as separate constraints.Source: §8 · p. 22
  • For the W^{n,∞} target ball, the uniform upper construction also controls every L^s error norm because the domain has volume one.The fixed-confidence accuracy-exponent match and, when d ≤ 2n, the joint accuracy-confidence match extend under the same depth conditions.Source: §8 · p. 22

9 Discussion

The discussion separates spatial capacity from random output fluctuation and states where the bounds match. It also identifies open questions in confidence, retention dependence, logarithmic factors, and extensions beyond the stated approximation setting.

9 Discussion

  • For d < 2n, output-layer cost dominates, while for d > 2n spatial complexity dominates under a logarithmic depth budget.With arbitrary depth, the capacity argument gives only ε^(-d/(2n))/p, without a matching theorem.Source: §9 · p. 22
  • When d ≤ 2n, the construction and output argument match confidence dependence up to accuracy logarithms; for d > 2n, no ε^(-d/n) log(1/δ) lower bound is established.The lower bound in the latter regime is only the maximum of capacity and stochastic terms.Source: §9 · p. 22
  • The upper bound has p^-9 retention dependence, and the optimal retention dependence and powers of log(1/ε) remain open.The sufficient confidence range is sharp for the affine-target obstruction when p ≥ 1/2, but its optimality for the full Sobolev class is unproved.Source: §9 · p. 23
  • The lower-bound extension covers W^{n,r} targets with L^s error, but an upper bound for that larger class requires additional analysis.Derivative-norm control likewise requires estimates beyond the function-value approximations proved here.Source: §9 · p. 23
  • The results establish network existence and size, not training algorithms, sample complexity, or generalization guarantees.Constants may depend strongly on n and d, large real weights are allowed, and bounded-weight or limited-precision implementations remain separate questions.Source: §9 · p. 23

9.1 Conclusion

  • The constant-depth construction matches the accuracy exponent forced by spatial capacity and random output fluctuation under the stated depth and confidence assumptions.The multiscale decomposition keeps these costs from multiplying in their accuracy exponents.Source: §9 · p. 22, §9.1 · p. 23

10 Development from the Earlier Drafts

The revision retains the random-approximation problem and Taylor representation while replacing invalid localization and improving the accuracy exponent through bounded circuits and multiscale assembly. It adds lower bounds and documents the scope of its AI assistance and verification.

10.1 What was retained and what was changed

  • The revision retained the dropout approximation problem and local Taylor partition, but added matching lower-bound analysis absent from the earlier drafts.The new analysis includes output-layer and retained-edge capacity arguments, plus an L^s transfer.Source: §10.1 · pp. 23–24
  • Localization was changed because a nonzero ReLU-output subnetwork cannot vanish outside its local region for every independent edge mask.The replacement shifts an existing output bias and recovers the zero set on the same event as the global approximation guarantee.Source: §10.1 · p. 24

10.2 Why the improvement changes the exponent

  • The multiscale gain comes from bounded local circuits and Taylor differences: level j has 2^(jd) terms of amplitude 2^(-jn), so its replication cost scales as 2^(j(d−2n)).Terms are combined within each scale before amplitude-weighted outputs are assembled, preserving the saving.Source: §10.2 · p. 24
  • The bounded-circuit and multiscale construction has accuracy exponent max{d/n, 2}, compared with 2 + (d + 2)/n for the valid single-scale construction.The earlier draft stated 2 + (2d + 2)/n, but that row does not certify its proof; the multiscale bound uses p^-9 rather than the single-scale p^-2 factor.Source: §10.2 · pp. 24–25

10.3 Scope of AI assistance and verification

  • The revision reports AI assistance with draft comparison, argument development, verification scripts, and text preparation, while stating that finite checks are not formal proof or independent peer review.The mathematical claims are supported by the paper's arguments, not by the fact that an automated assistant generated them.Source: §10.3 · p. 25
  • The revision makes explicit that biases are unmasked, every connecting edge is counted, and signed targets use an affine output.It retains the depth and confidence restrictions in matching statements and adds no experimental or training guarantees.Source: §10.3 · p. 25

A A Single-Scale Construction

The appendix records a valid single-scale upper bound and constructs global approximations from local Taylor terms. Its modules account for masked connections and control approximation error and failure probability across the domain.

A A Single-Scale Construction

  • Theorem A.1 gives a fixed-depth dropout-network approximation guarantee for every target in the stated Sobolev class, with size bounded as a function of the parameters.The guarantee concerns a sampled mask, not an additional guarantee obtained by replacing masks with their expectations.Source: A A Single-Scale Construction · p. 25
  • Signed targets require an affine output, since a ReLU output cannot approximate f ≡ −1 to error less than one.For the subclass f ≥ 0, the output may also be ReLU.Source: A A Single-Scale Construction · p. 25

A.1 Global approximation of a signed local Taylor term

  • A local Taylor term is implemented using bounded-factor products and a signed affine-ReLU gate, with gate and stage counts depending only on n and d.The construction replaces affine, copying, square, and product operations with dropout modules; later register bounds depend only on n and d.Source: §A.1 · p. 26
  • Uniform accuracy is obtained by budgeting module tolerances and failure probabilities across all modules, then intersecting their uniform success events.The fixed number of module costs is summed, and padding to common depth includes the costs and errors of the added identity modules.Source: §A.1 · p. 26

A.2 Assembly and its exact error and probability budgets

The assembly combines local Taylor branches while controlling their overlap, approximation error, and joint success probability. A final affine-output module aggregates signed branch values on the event where the local outputs are controlled.

A.2 Assembly and its exact error and probability budgets

  • The assembly uses T = 2A(N + 1)^d nonnegative branches, with at most 2dA nonzero at any input and total branch sum at most A.Here A counts multi-indices with order below n.Source: §A.2 · p. 27
  • The Taylor partition has bounded overlap and remainder at most C_{n,d}N^-n, while each coefficient c_{m,α} has magnitude at most one.The derivatives below order n use continuous representatives, including boundary limits.Source: §A.2 · p. 27
  • Local branch outputs are shifted so that, with probability at least 1 − δ/2, they are nonnegative, bounded by their targets, and zero whenever their targets are zero.These simultaneous bounds place the output vector in the set of nonnegative vectors with sum at most A.Source: §A.2 · p. 27
  • The signed branch sum is then approximated by an affine-output module with accuracy ε/4 and failure probability δ/2, and the resulting size bound follows after adding the Taylor error.The proof adds two outer layers while retaining common bounded depth across local branches.Source: §A.2 · p. 27

B Cut Sets and Reliability

The cut-set results bound the reliability of approximating nonconstant targets, while the algebraic and numerical checks provide supplementary verification of parts of the proofs. The checks do not establish the general theoretical claims, which rely on the analytical proofs.

B Cut Sets and Reliability

  • The cut-set bounds apply to any continuous nonconstant target without a smoothness assumption, and use the network's realized depth rather than its allowed depth budget.A zero-sized layer is incompatible with success.Source: B Cut Sets and Reliability · p. 28
  • (1-p)^k ≤ δ for a cut set of k masked edges when a continuous target has oscillation greater than 2ε and the approximation succeeds with probability at least 1-δ.Removing every edge in the cut set makes the output constant, whose uniform error is at least half the target's oscillation.Source: B Cut Sets and Reliability · p. 28

C Algebraic and Numerical Checks

  • Six finite verification scripts check identities, error constants, bounded subnetworks, graph properties, and constants used in the confidence lower bound.The authors describe these checks as supplementary to the analytical proofs.Source: C Algebraic and Numerical Checks · p. 28
  • The multiscale checks use rational evaluations for circuits with up to six edges and piecewise-linear evaluations of masked local windows, clipped coordinates, and affine combinations.Error and probability budgets are checked for d < 2n, d = 2n, and d > 2n.Source: C Algebraic and Numerical Checks · p. 28
  • The scripts verify 22,295 normalized difference coefficients, 2,304 localized telescoping identities, and 768 complete multiscale identities, including boundary centers.The evaluations do not infer an approximation rate or simulate a full network at the asymptotic size budget; universal claims require the preceding proofs.Source: C Algebraic and Numerical Checks · p. 29

Related papers

Loading 2610.02253v1…