PaperlayerView exact revision on arXiv

Source-linked AI summary

A Corrective View of Neural Networks: Representation, Memorization and Learning

Guy Bresler, Dheeraj Nagaraj

arXiv:2002.00274v2cs.LGmath.STstat.MLstat.TH

TL;DR

The paper asks how neural networks represent functions, memorize arbitrary data, and learn low-degree polynomials with tractable guarantees. It introduces iterative residual correction across groups of nonlinear units and applies it to shallow networks and random features. The resulting guarantees include near-linear-unit memorization, improved smooth-function representation with effective-dimension refinements, and the first subpolynomial neuron bound for gradient-based polynomial learning.

  • Problem

    Existing guarantees leave neural-network representation, arbitrary-label memorization, and gradient-based learning of low-degree polynomials insufficiently understood, especially for shallow networks.

    Source: §1 · p. 1

  • Method

    The paper divides nonlinear units into groups that successively approximate the current residual, using smoothed ReLUs and random features with gradient-based optimization.

    Source: §1.4 · p. 6

  • Results

    The results give ˜O(n/θ^4) ReLUs for memorizing separated arbitrary labels, improved shallow-network representation rates with effective-dimension dependence, and O(subpoly(1/ε)) neurons for learning low-degree polynomials.

    Source: Memorization · pp. 3–4, §1.1 · p. 5

  • Takeaways & Limitations

    Iterative correction extends strong representation and learning guarantees to two-layer networks while preserving convex optimization in the random-features setting.

    Source: §1.4 · p. 6

    The guarantees require separation or smoothness assumptions, and the correction procedure can continue only while the residual remains sufficiently smooth.

    Source: §2 · p. 7

Abstract

from arXiv · show

We develop a corrective mechanism for neural network approximation: the total available non-linear units are divided into multiple groups and the first group approximates the function under consideration, the second group approximates the error in approximation produced by the first group and corrects it, the third group approximates the error produced by the first and second groups together and so on. This technique yields several new representation and learning results for neural networks. First, we show that two-layer neural networks in the random features regime (RF) can memorize arbitrary labels for arbitrary points under under Euclidean distance separation condition using $\tilde{O}(n)$ ReLUs which is optimal in $n$ up to logarithmic factors. Next, we give a powerful representation result for two-layer neural networks with ReLUs and smoothed ReLUs which can achieve a squared error of at most $\epsilon$ with $O(C(a,d)\epsilon^{-1/(a+1)})$ for $a \in \mathbb{N}\cup\{0\}$ when the function is smooth enough (roughly when it has $\Theta(ad)$ bounded derivatives). In certain cases $d$ can be replaced with effective dimension $q \ll d$. Previous results of this type implement Taylor series approximation using deep architectures. We also consider three-layer neural networks and show that the corrective mechanism yields faster representation rates for smooth radial functions. Lastly, we obtain the first $O(\mathrm{subpoly}(1/\epsilon))$ upper bound on the number of neurons required for a two layer network to learn low degree polynomials up to squared error $\epsilon$ via gradient descent. Even though deep networks can express these polynomials with $O(\mathrm{polylog}(1/\epsilon))$ neurons, the best learning bounds on this problem require $\mathrm{poly}(1/\epsilon)$ neurons.

1. Introduction

The paper studies neural-network representation, memorization, and learning through a corrective mechanism that repeatedly approximates and corrects residual errors. It develops shallow-network representation results, near-linear memorization guarantees, low-dimensional refinements, and subpolynomial learning guarantees for low-degree polynomials.

1.1. The Corrective Mechanism

  • Two-layer networks with smoothed ReLUs achieve representation rates previously obtained with deep networks, using smoother activations near zero while matching ReLU elsewhere.The construction addresses the poorly behaved Fourier transform of ReLU by convolving it with a probability density.Source: §1 · p. 2, §1.1 · p. 4

Memorization.

  • For arbitrary labels on d-dimensional points separated by at least θ, two-layer ReLU networks memorize via gradient descent using ˜O(n/θ^4) nonlinear units, optimal in n up to logarithmic factors.Earlier results cited in the paper required O(n^12/θ^4) units under the same distance condition.Source: Memorization · p. 3
  • Learning low-degree polynomials with gradient descent is reduced to convex least-squares optimization in the random-features model, while the paper claims an O(subpoly(1/ε)) neuron bound.Fixed random weights leave only linear coefficients to optimize, and gradient descent reaches the target optimization accuracy in O(1/ε) steps.Source: Memorization · p. 3, §1.4 · p. 6

1.1. The Corrective Mechanism

  • The corrective mechanism partitions units into groups that successively approximate the current residual, yielding squared-error rates of O(1/N^a) under suitable smoothness conditions.The remainder becomes less smooth after each correction, so the number of usable correction stages depends on the original function’s smoothness.Source: §1.1 · p. 4

1.2. Functions with Low-Dimensional Structure

  • The dimension-dependent factor in representation guarantees can be replaced by an effective dimension q when the target has low-dimensional structure.The paper defines such functions by combining component functions over q-dimensional projections of the input.Source: §1.1 · p. 5, §1.2 · p. 5

1.4. Random Features Model and Training

  • Random features keep hidden weights fixed and optimize only output coefficients, converting training into smooth convex linear regression.The paper uses this setup to establish high-probability approximation followed by gradient-descent training guarantees.Source: §1.4 · p. 6

2. Memorization

The paper constructs two-layer random-feature networks that memorize arbitrary labels on separated points, using iterative correction of successive approximation errors. With fixed random weights, the resulting optimization over output coefficients is convex and can be solved by GD/SGD.

Theorem 1

  • With probability at least 1 −δ, a two-layer ReLU network with N random features fits arbitrary labels on θ-separated points to squared error at most ϵ.The construction assumes bounded inputs, arbitrary labels in [0, 1], and a sufficiently large feature count depending on n, θ, ϵ, and δ.Source: §2 · pp. 7, 9

Training guarantee

  • Keeping random weights and thresholds fixed makes the loss a convex function of the output coefficients, so GD/SGD reaches the optimum for those free parameters.The learning guarantee first establishes a good coefficient vector and then uses gradient descent to optimize the remaining parameters.Source: §2 · p. 7

Scope of the guarantee

  • The stated guarantees no longer contain the earlier extra factor of d^2 after a refined analysis.This improvement is recorded as a revision to the initial version of the paper.Source: §2 · p. 7

Approximation procedure

  • The proof begins by smoothing the target on the sample points through a Gaussian Fourier construction, then replaces sinusoidal representations with ReLU features and estimates them empirically.The Gaussian scale is chosen relative to the separation θ and log n, while the empirical estimator samples Gaussian weights and uniform biases.Source: §2 · pp. 7–9

Iterative correction

  • The network uses iterative correction: each independently sampled group approximates the current remainder, and the remainders contract geometrically across groups.The first remainder is the label function minus its approximation; later groups approximate and subtract each successive remainder.Source: §2 · p. 9

Network construction

  • The final predictor is a two-layer network with lN ReLU units formed by summing the estimators from all correction rounds.Unrolling the recursion identifies the accumulated estimator as a network using the same fixed random-feature distribution.Source: §2 · p. 9

3. Representation via the Corrective Mechanism

The corrective mechanism repeatedly approximates a function's residual with successive groups of units, producing increasingly fast representation rates under Fourier-norm smoothness conditions. Smoothed ReLUs enable this iteration, and effective dimension can replace ambient dimension in low-dimensional settings.

3. Representation via the Corrective Mechanism

  • O(C(a)ε^-1/(a+1)) activation functions suffice for squared error at most ε under the theorem's Fourier-norm assumptions.The rate follows from iterating residual correction through a=0,...,a stages.Source: §3 · pp. 10–11
  • Each corrective stage approximates the current residual, reducing squared error from O(1/N) to 1/N^2 and onward to 1/N^a.The construction allocates units across stages and decreases the smoothing parameter as residuals become less smooth.Source: §3 · p. 11
  • For low-dimensional functions, the representation bound depends on effective dimension q rather than ambient dimension d.The corresponding network uses ReLU and SReLUk units for the component functions in the low-dimensional decomposition.Source: §3 · p. 11

Appendix A. Smoothed ReLU functions and Integral Representations

  • The technical representation strategy expresses cosine functions through SReLUk units and combines this with Fourier inversion to represent target functions.The cosine representation is introduced as a prerequisite for the later approximation theorems.Source: Appendix A · p. 16, §A.1 · p. 16

A.1. Smoothing the ReLU

  • SReLUk equals ReLU outside a neighborhood of zero while becoming smoother as k increases, enabling residuals to remain sufficiently smooth for iteration.The functions are constructed by convolving ReLU with compactly supported probability densities.Source: §3 · p. 10, §A.1 · p. 16
  • Smoother activation functions have worse κ upper bounds because they track high-frequency oscillations less effectively.This creates a trade-off between activation smoothness and the ability to represent rapidly oscillating cosine terms.Source: §A.1 · p. 17

Appendix B. Proof of Theorem 7: Unbiased Estimator for the Function and its Fourier transform

These appendices develop the analytic and estimator foundations for representing a function and its Fourier transform. They establish approximation, remainder, derivative, decay, smoothing-filter, and density properties needed for subsequent bounds.

Appendix B. Proof of Theorem 7: Unbiased Estimator for the Function and its Fourier transform

  • Theorem 16 gives an unbiased two-layer SReLU estimator whose squared approximation error is of order 1/N, with constants depending on the Fourier norm.The estimator averages N independent single-unit estimators sampled from μ_l × ν_g,k, with l ≥ 2 ensuring finite second moments.Source: Appendix B · pp. 18, 19, 22
  • The proof makes the Fourier transform unbiased and integrable by replacing SReLU with compactly supported smoothed triangles, then truncating and mollifying perpendicular directions.These modifications address one-dimensional singular Fourier transforms, nonintegrability of SReLU units, and unbiasedness restricted to B_q^2(r).Source: Appendix B · pp. 19–20
  • The modified estimator and target function have integrable Fourier transforms, and the estimator’s Fourier transform is unbiased for the target Fourier transform at every frequency.The construction uses a cutoff γ that equals one on the target ball and vanishes outside a larger compact set.Source: Appendix B · pp. 21–22
  • The remainder’s expected Fourier norm decreases by order 1/√N, under l = 3, R = r, and the stated smoothness-range condition on s.The proof combines the estimator bound and remainder bound with Markov’s inequality and a union bound to obtain simultaneous inequalities with probability at least 1/2.Source: Appendix B · pp. 22–23

Appendix C. Integral Representations for Cosine Functions

  • The Appendix C filter is a symmetric, continuous probability density supported on [−w0,w0], with Fourier transform strictly positive and at most one.Its further derivative and decay properties are established under fixed α0 and w0, supporting the preceding integral-representation arguments.Source: Appendix C · p. 23
  • Claim 2 expresses each derivative of 1/f as a linear combination of products involving powers of 1/f, with coefficients independent of f.The claim is proved by induction on the derivative order.Source: Appendix C · pp. 24–25
  • Claim 3 establishes bounds on derivatives of the auxiliary function g and its scaled or shifted versions, with constants depending on derivative order and representation parameters.For large |ξ|, derivatives are controlled by bounded trigonometric numerators divided by polynomial powers of ξ; the small-|ξ| case is bounded directly.Source: Appendix C · p. 25
  • The appendix applies Claims 2 and 3 to obtain derivative bounds for the reciprocal and scaled functions, completing the proof of Lemma 21.The resulting estimates depend on the parameters k, w0, α0, and the derivative order.Source: Appendix C · p. 25
  • The setup assumes infinitely differentiable compactly supported real-valued functions and a symmetric continuous probability density supported on [−w0, w0].The identity operator on the space of compactly supported smooth functions is also introduced.Source: Appendix C · p. 25

Proof

The proof establishes convergence properties for an operator-based approximation scheme and uses them to derive integral representations with smoothed ReLU activations. These representations support unbiased estimators for functions and their Fourier transforms.

Operator convergence

  • Uniform convergence of the iterated operator establishes the limiting representation used throughout the proof.The argument applies Fourier and dominated-convergence methods to show convergence of h_n^(2) and weighted variants uniformly on the relevant interval.Source: Proof · pp. 27–29
  • The filter conditions ensure that the limiting function is a Schwartz function and that h admits an integral representation.Lemma 24 imposes Fourier-domain regularity conditions on the filter, while the specialized filter satisfies those conditions.Source: Proof · pp. 27–28

Smoothed ReLU construction

  • The proof specializes the construction to smoothed ReLU activations obtained by convolving ReLU with a compactly supported density.The resulting SReLU activation agrees with ReLU outside a controlled neighborhood and is used to represent localized cosine functions.Source: Proof · pp. 26, 30

Fourier estimates

  • Fourier-domain estimates bound the limiting function and its weighted moments, completing the analytic control needed for the representation theorem.The proof uses decay of the Fourier transform and its derivatives, followed by inversion and dominated-convergence arguments.Source: Proof · pp. 30–32

Estimator construction

  • The resulting representation is extended to higher-dimensional functions and yields an unbiased estimator whose Fourier transform is also unbiased.The construction introduces κ and the measure νg,k, then verifies the estimator identity on the relevant ball.Source: Proof · pp. 26, 32

Appendix D. Neural Network Approximation with Function Independent Sampling

Appendix D replaces function-dependent sampling with a fixed distribution and applies the corrective mechanism to construct smooth two-layer approximations. Theorem 31 extends this construction to effective-dimensional and composite-function settings.

Appendix D. Neural Network Approximation with Function Independent Sampling

  • The fixed-measure theory requires the Fourier transform to be an ordinary function, not a generalized function or measure such as a Dirac delta.A weaker technical restriction on an exponent is also noted as possible with a more delicate proof.Source: Appendix D · pp. 33, 35
  • Function-independent sampling uses a fixed distribution ν0 for weights, unlike the function- and smoothness-dependent measure νg,k.The appendix notes that νg,k cannot be sampled during training because g is unknown, motivating ν0-based guarantees.Source: Appendix D · p. 33
  • The sampled estimators are unbiased for g and have controlled smoothness, integrability, and derivatives under the stated moment and Fourier assumptions.The construction establishes almost-sure C2k regularity for individual estimators and for their expectation.Source: Appendix D · pp. 34–35
  • The remainder is recursively approximated by successive groups of ReLU and smoothed-ReLU units, with each group correcting the preceding approximation error.Dividing N units across a+1 stages yields a final squared-error order of 1/N^(a+1) under the relevant smoothness conditions.Source: Appendix D · p. 38

Theorem 31

  • Theorem 31 gives a random one-hidden-layer network with N ReLU and smoothed-ReLU activations whose approximation and derivative errors hold with high probability.The theorem assumes l sufficiently large relative to q and a, and its bounds hide factors depending on l, q, r, and a.Source: Theorem 31 · pp. 39–40
  • The construction supports effective dimension q by sampling weights in the spans of component matrices, while Theorem 32 extends the result to functions on R^d built from such components.The ambient dimension can therefore be separated from the lower-dimensional subspaces governing the function components.Source: Theorem 31 · p. 39

Appendix E. Proofs of Lemmas

These proofs establish auxiliary bounds for Fourier-based estimators used in the approximation analysis. They control estimator norms and use ReLU growth, concentration, and Cauchy–Schwarz arguments.

E.1. Proof of Lemma 3

  • Lemma 3’s proof derives its first estimates directly from the definition of F and the triangle inequality, then uses the chosen activation’s properties for the remaining item.The final step invokes the definition of the smoothed approximation and the selected σ function.Source: §E.1 · p. 41

E.2. Proof of Lemma 5

  • Lemma 5 bounds the relevant expectation by combining Lemma 3, the inequality ReLU(x) ≤ |x|, and Cauchy–Schwarz.The proof controls the inner product term on a Gaussian event and its complement using concentration and fourth-moment bounds.Source: §E.2 · p. 42

E.3. Proof of Lemma 6

The proof of Lemma 6 decomposes the squared error and bounds the Gaussian inner-product contribution by conditioning on a concentration event.

E.3. Proof of Lemma 6

  • The argument begins with a bias–variance decomposition and then applies the preceding lemma to control the resulting terms.Several constants and logarithmic factors are absorbed into a universal constant during the chain of inequalities.Source: §E.3 · pp. 42–43
  • Conditioning on At = {|⟨ξ1, xk⟩| ≤ σt} separates the bounded inner-product event from its Gaussian tail complement.Cauchy–Schwarz, Gaussian concentration, and fourth-moment control bound both pieces.Source: §E.3 · p. 43
  • The proof selects t logarithmically in n and concludes the stated estimate after combining Equations (56) and (58).The displayed fragments indicate the resulting dependence includes logarithmic powers of n and the relevant scale parameters.Source: §E.3 · p. 43

E.4. Proof of Lemma 18

The proof of Lemma 18 establishes regularity and integrability bounds for sampled Fourier-feature estimators by analyzing their geometric decomposition and truncated activation factors.

E.4. Proof of Lemma 18

  • Lemma 33 bounds the estimator almost surely by separating the cases Tj > 1 + w0 and Tj ≤ 1 + w0.The first case is trivial because the estimator vanishes; the second is handled using bounds on the truncated factor.Source: §E.4 · pp. 43–44
  • The proof controls the truncated activation through its L1 norm, supremum, convolution representation, and Jensen’s inequality.These bounds are used to control the estimator when the threshold parameter lies in its active range.Source: §E.4 · p. 44
  • For nonzero ωj, the analysis decomposes x into components parallel and perpendicular to ωj, reducing the geometric integral to lower-dimensional sections.The perpendicular component depends only on x⊥ωj, which enables the product-measure decomposition.Source: §E.4 · p. 44

Proof of Lemma 18

The proofs establish integrability and Fourier-transform bounds for the constructed functions, using convolution, coordinate decompositions, polar coordinates, and moment assumptions.

Proof of Lemma 18

  • The construction defines a piecewise-linear function Δ from three ReLU terms and obtains its smoothed version SΔ by convolution.The Fourier transform of Δ is then used to analyze SΔ through the convolution theorem.Source: Proof of Lemma 18 · p. 45
  • The nonzero-frequency case reduces the Fourier analysis to the direction of ω_j and its orthogonal complement, identified with R^(q−1).This decomposition permits separate treatment of the one-dimensional ReLU-derived factor and the perpendicular smoothing factor.Source: Proof of Lemma 18 · p. 45
  • Integrability of ĝ_j follows by separating the cases T_j > 1 + w_0, ω_j = 0, and ω_j ≠ 0, with l ≥ 2 ensuring the required threshold moment is finite.The argument also uses Fubini’s theorem and bounds involving Γ_q,R and SΔ.Source: Proof of Lemma 18 · pp. 44–46

E.5. Proof of Lemma 19

  • Lemma 19 bounds the relevant spherical and radial integrals using Jensen’s inequality, polar decomposition, and a sphere-coordinate estimate for q ≥ 2.The proof selects sufficiently large decay order n and uses finite fourth moments when l ≥ 3.Source: §E.5 · pp. 46–48
  • The q = 1 case is handled separately, and the resulting integral bounds complete the estimate required by Lemma 19.The final integrability condition is checked through the stated one-dimensional integral and the definition of β_g,k.Source: §E.5 · pp. 46, 49

E.6. Proof of Lemma 28

The proof of Lemma 28 establishes smoothness, compact support, derivative bounds, and integrability for the constructed Fourier-domain functions.

E.6. Proof of Lemma 28

  • Fourier decay implies that SΔ_k is 2k times continuously differentiable, so ĝ_j is almost surely C^2k.The proof also uses the support interval of SΔ_k to sharpen derivative bounds.Source: §E.6 · p. 49
  • The constructed derivative ∂^b ĝ_j is continuous and compactly supported almost surely, hence belongs to L1(R^q).Compact support follows from the bounded support of the perpendicular smoothing function and the one-dimensional support constraint.Source: §E.6 · p. 50
  • The proof bounds derivatives by expressing them as finite combinations of terms controlled uniformly by constants independent of g, T_j, and ω_j.The resulting bound absorbs dependencies on α_0, q, r, k, R, and w_0 into B_k.Source: §E.6 · p. 50
  • Repeated differentiation is handled inductively, while dominated convergence establishes continuity of derivatives of the averaged function g(x; R).The integrability argument uses a quadratic bound in |T_j| together with the assumed finite second moment.Source: §E.6 · p. 50

F.1. Proof of Theorem 8

Theorem 8 is proved by partitioning neurons across successive approximations, each correcting the remainder left by earlier groups, and finishing with a random ReLU approximation.

F.1. Proof of Theorem 8

  • For a = 0, the required approximation error follows directly from the ReLU construction in Theorem 16.The proof separately handles this base case before applying the recursive correction argument for a ≥ 1.Source: §F.1 · p. 51
  • The corrective construction starts with a two-layer SReLU network approximating g, then repeatedly approximates the current remainder with progressively indexed SReLU units.For 1 ≤ b ≤ a − 1, each stage produces an approximation ĝ^(b) and a new remainder g_rem,b.Source: §F.1 · p. 51
  • The final remainder is approximated by a random ReLU network, yielding a two-layer network with ReLU and SReLU units.The total network uses N nonlinear units distributed across the a + 1 approximation stages.Source: §F.1 · pp. 51–52
  • The SReLU units are selected non-randomly, whereas only the final ReLU units are random, so the expectation in the error bound is over ReLU randomness.The residual identity shows that the combined output equals g minus the accumulated approximation components.Source: §F.1 · p. 52

F.2. Proof of Theorem 9

Theorem 9 constructs independent lower-dimensional random networks for component functions, then averages their outputs to obtain the final estimator.

F.2. Proof of Theorem 9

  • Each component f_i is approximated by an independent one-hidden-layer random network whose weights lie in the span of the corresponding subspace B_i.The ambient sampling measure is replaced by its measure induced on span(B_i).Source: §F.2 · p. 52
  • The component networks are juxtaposed and their outputs averaged to form the estimator f̂.The construction distributes the available neurons across the m component networks.Source: §F.2 · p. 52
  • Independence of distinct component approximations allows the expected error bound to combine across components, and the expectation implies existence of a configuration achieving it.The proof explicitly uses independence when i ≠ j.Source: §F.2 · p. 53

F.3. Proof of Theorem 10

The proof constructs a q-dimensional orthonormal basis for each polynomial component, extends it with a bump function, and applies a sampling theorem to obtain Theorem 10.

Basis construction

  • Each component pV is represented on a q-dimensional span using active standard basis vectors, supplemented by distinct coordinates when fewer than q are active.This construction ensures |BV| = q and identifies span(BV) with R^q.Source: §F.3 · p. 53

Schwartz extension

  • Multiplying pV by a compactly supported bump function produces a Schwartz function that agrees with pV on the relevant domain.The bump equals one on [-1,1] and vanishes outside |t| >= 2.Source: §F.3 · p. 53

Fourier control

  • The proof verifies that pV has finite Fourier norms after being viewed over span(BV), enabling the sampling procedure required by Theorem 32.The associated Fourier-norm quantities are bounded through H, which depends only on q and a.Source: §F.3 · p. 53

Application of Theorem 32

  • Because the bases BV are explicitly known, the sampling procedure can be performed without knowing the polynomial, and a direct application of Theorem 32 proves Theorem 10.The polynomial case differs from the general low-dimensional function setting by a scaling factor m, which multiplies the error by m^2 and coefficients κj by m.Source: §F.3 · pp. 53–54
Loading 2002.00274v2…