PaperlayerView exact revision on arXiv

Source-linked AI summary

Bridging the Gap Between Approximation and Learning via Optimal Approximation by ReLU MLPs of Maximal Regularity

Ruiyang Hong, Anastasis Kratsios

arXiv:2409.12335v4cs.LGcs.NAcs.NEmath.FAmath.NAstat.ML

TL;DR

Approximation theory and learning theory emphasize different properties of neural networks, leaving open whether a class can be expressive and generalize. The paper constructs structured ReLU MLPs using Kuhn triangulation and proves optimal approximation with preserved regularity. It also establishes limits on what the approximation guarantee covers.

  • Problem

    Approximation-focused MLPs may lack the regularity needed for reliable statistical behavior, while learning-focused classes may be too constrained to approximate universally.

    Source: §1 · p. 1

  • Method

    The paper constructs ReLU MLP approximators using Kuhn triangulation, whose regularity-preserving role is tied to a uniqueness result for regular approximation.

    Source: §6.1 · p. 16

  • Results

    Theorem 1.1 establishes optimal approximation by ReLU MLPs that preserve the target’s Hölder regularity.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper’s result fills a gap in guarantees that Lipschitz constraints need not reduce neural-network expressivity.

    Source: §2.1 · p. 6

    The result does not guarantee approximation in the Lipschitz norm, which is impossible for ReLU MLPs under that norm’s nonseparable function space.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

The foundations of deep learning are supported by the seemingly opposing perspectives of approximation or learning theory. The former advocates for large/expressive models that need not generalize, while the latter considers classes that generalize but may be too small/constrained to be universal approximators. Motivated by real-world deep learning implementations that are both expressive and statistically reliable, we ask: "Is there a class of neural networks that is both large enough to be universal but structured enough to generalize?" This paper constructively provides a positive answer to this question by identifying a highly structured class of ReLU multilayer perceptions (MLPs), which are optimal function approximators and are statistically well-behaved. We show that any $(L,\alpha)$-H\"{o}lder function from $[0,1]^d$ to $[-n,n]$ can be approximated to a uniform $\mathcal{O}(1/n)$ error on $[0,1]^d$ with a sparsely connected ReLU MLP with the same H\"{o}lder exponent $\alpha$ and coefficient $L$, of width $\mathcal{O}(dn^{d/\alpha})$, depth $\mathcal{O}(\log(d))$, with $\mathcal{O}(dn^{d/\alpha})$ nonzero parameters, and whose weights and biases take values in $\{0,\pm 1/2\}$ except in the first and last layers which instead have magnitude at-most $n$. Further, our class of MLPs achieves a near-optimal sample complexity of $\mathcal{O}(\log(N)/\sqrt{N})$ when given $N$ i.i.d. normalized sub-Gaussian training samples. We achieve this through a new construction that perfectly fits together linear pieces using Kuhn triangulations, along with a new proof technique which shows that our construction preserves the regularity of not only the H\"{o}lder functions, but also any uniformly continuous function. Our results imply that neural networks can solve the McShane extension problem on suitable finite sets.

1 Introduction

The paper seeks ReLU MLPs that combine strong approximation with reliable generalization. It presents structured networks with optimal approximation rates and maximal regularity, then develops geometric and interpolation results supporting that construction.

1 Introduction

  • The proposed ReLU MLP class is both a universal approximator and statistically well-behaved, including in the overparameterized regime.The paper reports a nearly optimal, dimension-free generalization rate that does not explode as width and depth grow.Source: §1 · pp. 2–3
  • Theorem 1.1 gives optimal approximation while preserving the target’s Hölder exponent and coefficient under structural constraints.The network’s width and parameter count scale as O(dn^(d/α)), and its depth as O(log(d)).Source: §1 · p. 2
  • For i.i.d. normalized sub-Gaussian training samples, the class has a nearly optimal O(log(N)/√N) generalization rate that remains convergent when width and depth exceed sample size.The passage describes the bound as dimension-free and non-exploding in the overparameterized regime.Source: §1 · p. 3

1.1 Technical Contributions: New Proof Techniques

  • Kuhn triangulation avoids the tiny regions and steep interpolating segments of standard constructions, enabling approximators with maximal regularity.The paper states that this geometric construction is essentially unique, up to reflections, for minimal-Lipschitz approximation.Source: Figure 1 · p. 3, §1.1 · p. 4

1.2 Further Results

  • The results also cover arbitrary regularity, global Lipschitz control, extrapolation, and approximation of regular discontinuous targets to their minimal achievable error.The paper additionally presents optimal interpolation results, including a shallow one-dimensional construction with minimal parameter usage and Lipschitz constant.Source: §1.2 · pp. 5–6

1.3 Organization of Paper

  • The paper organizes its discussion from related approximation work and preliminaries to main approximation and generalization results, consequences, and proofs.It also discusses the uniqueness of the Kuhn triangulation in its theory-landscape section.Source: §1.3 · p. 6

2 Related Literature

Prior work studies constrained or regular ReLU networks, but leaves gaps in expressivity under Lipschitz constraints, exact regularity matching, global extrapolation rates, and generalization bounds. The paper’s results address these gaps across approximation and learning theory.

2.1 Lipschitzness in Neural Networks

  • Lipschitz-constrained networks are used in several deep-learning areas, but prior work offered no guarantee that enforcing Lipschitzness preserves model expressivity.The authors say their main result fills this gap.Source: §2.1 · p. 6

2.2 Approximators with Parameter Restrictions

  • Earlier parameter-restricted ReLU approximation results allow weight bounds that yield Lipschitz guarantees diverging as approximation error tends to zero, unlike the paper’s optimal bound.The cited literature gives the tightest available approximation results with weight and bias size limits [72, Theorem 3.1].Source: §2.2 · pp. 6–7

2.3 Approximation of Functions and Their Derivatives

  • Prior derivative-approximation guarantees do not ensure exact Lipschitz implementation, especially for lower-regularity functions such as sub-Hölder targets.The cited results primarily cover once continuously differentiable Lipschitz functions.Source: §2.3 · p. 7

2.4 Global Universal Approximation

  • Earlier global approximation theorems are qualitative, with extrapolation rates unknown; Theorem 4.1 and Corollary 5.2 provide global modulus matching and an extrapolation-rate guarantee.The stated guarantee applies to uniformly continuous functions, including Hölder and Lipschitz functions.Source: §2.4 · p. 7

2.5 Deficits of Parametric Generalization Bounds for Overparameterized MLPs

  • Existing Rademacher and VC bounds become weaker or diverge as width and depth grow, whereas the paper studies generalization for its constrained MLP class.The passage describes the existing bounds as weaker and notes that VC bounds diverge as W and Δ tend to infinity.Source: §2.5 · pp. 7–8

3 Preliminaries

The preliminaries establish notation and define continuity, regularity, and ReLU MLP classes. They also distinguish continuous targets from potentially discontinuous regular functions, for which the best uniform approximation error may remain positive.

3 Preliminaries

  • The preliminaries set notation for the paper and define ReLU as the componentwise activation σ(t)=max(0,t).The network classes are then described through layerwise weight matrices and biases.Source: §3 · p. 8, §3.1 · p. 8, §3.3 · pp. 10–11

3.2.1 Uniform, Lipschitz, and H¨older Continuity

  • A modulus of continuity bounds how much function values can differ at nearby inputs; choosing ω(t)=Lt^α defines α-Hölder continuity with constant L.The α=1 case is L-Lipschitz.Source: §3.2.1 · p. 8

3.2.2 Uniform Regularity, Best Achievable Approximation Error, and Discontinuity

  • The paper extends its scope beyond continuous targets to functions satisfying a modulus of regularity, which need not be continuous.The Heaviside function is an example with ω(t)=1 for t>0 and 0 at t=0.Source: §3.2.2 · p. 9, Figure 3 · p. 10
  • For discontinuous regular targets, the best uniform approximation error can be positive, while continuous targets admit asymptotically vanishing error.The modulus of regularity quantifies the best achievable error.Source: §3.2.2 · p. 9
  • Regularity does not guarantee measurability: the paper notes that a Vitali-set perturbation of a Lipschitz function need not be Lebesgue measurable.This is a scope caveat for the broader class of regular functions.Source: §3.2.2 · p. 10

3.3 Multilayer Perceptrons (MLPs) with ReLU Activation Function

  • ReLU MLPs are specified by their layer widths, weights, and biases; parameter-vector norms depend on representation, unlike the function’s optimal Lipschitz constant.The classes are also indexed by depth, width, and Lipschitz constraints.Source: §3.3 · pp. 10–11

4 Main Results

The main results give ReLU MLPs with controlled size and regularity for approximation, and bound generalization for the constrained network class. They also establish exact extension from finite sets and allow flexible choices of network width and depth.

4.1 Approximation Guarantees

  • Theorem 4.1 bounds network width by 8d(n+1)^d, depth by ⌊log2 d⌋+4, and nonzero parameters by 16d(n+1)^d.The theorem presents these bounds for an optimal regular, sample-interpolating approximation.Source: §4.1 · p. 11
  • For finite dyadic-grid subsets, the results give a uniformly continuous ReLU MLP extension that matches the function on the subset.The theorem statement specifies exact agreement on A.Source: §4.1 · p. 12
  • The approximation guarantee can be implemented with virtually any specified width or depth, subject to the stated allocation constraint.The result specifies total width allocation of (n+1)^d across layers.Source: §4.1 · p. 13
  • The constructed network retains the target’s modulus of regularity on [0,1]^d.The theorem also provides a sample-interpolation guarantee.Source: §4.1 · pp. 11, 13

4.2 Statistical Guarantees

  • The generalization bound for the constrained class remains bounded as depth and width increase, under the stated data and loss assumptions.The discussion contrasts this with a bound for the larger network class that diverges as depth or width grows.Source: §4.2 · pp. 13–14

5 Implications of Theorem 4.1

The results extend regularity control beyond the unit cube and use it to bound extrapolation error. The global approximation statement uses an additive correction rather than discounting error with a weight function.

5.1 Approximation Theory: Extrapolation Rates

  • The paper extends the interpolator’s domain to all of R^d while maintaining its regularity.The distance to the unit cube is used in formulating this extension.Source: §5.1 · p. 14
  • The approximator can preserve the target’s modulus of regularity globally, with one additional layer and at most 18d(n+1)^d nonzero parameters.The global-regularity construction is given with depth at most ⌊log2 d⌋+5.Source: §5.1 · pp. 14–15
  • The global approximation result uses an additive correction term rather than the multiplicative corrective weight used in cited global approximation work.The comparison includes [16, Theorem 4.13], [32, Corollary 9], and [1, Theorem 4.11].Source: §5.1 · p. 15
  • The extrapolation result bounds error beyond [0,1]^d using the moduli of both the target and its approximator.The paper describes this as quantifying how fast error grows outside the cube.Source: §5.1 · pp. 14–15

6 Discussion

The discussion explains why Kuhn triangulations support regularity-preserving approximation and argues that this choice is unique up to reflections. It contrasts the construction with a state-of-the-art approximation method and discusses what path norms reveal about network regularity.

6.1 The Kuhn Triangulation is Unique for Regular Approximation

  • The Kuhn triangulation is the only triangulation, up to reflections, for which the cited regularity-preservation lemma holds when n=1.The paper identifies it as the key geometric step in the proof of Theorem 4.1.Source: §6.1 · pp. 15–16

6.2 Parameter Usage Compared to State-of-the-Art Approximation

  • The cited state-of-the-art construction uses more irregular approximators, while the Kuhn-based construction needs no trifling regions.The paper also states that its multidimensional version achieves the same approximation rate with the dimension dependence in the constant reduced from exponential to linear.Source: §6.2 · p. 16

6.3 Path Norms and Lipschitz Constants

  • The parameter-based path norm provides a computable upper bound on a network’s Lipschitz constant, but it can severely overestimate the implemented function’s constant.The text distinguishes this bound from the exact Lipschitz constant, which can be difficult to compute in practice.Source: §6.3 · pp. 16–17

7.1 Additional Notation During Proofs

This section sets conventions for describing network classes, layer composition, norms, and piecewise-linear functions. It distinguishes the norms used for domain regularity and approximation error.

7.1 Additional Notation During Proofs

  • The paper uses the ℓ1 norm for domain regularity and the uniform L∞ norm for approximation estimates.The ℓp and L∞ vector norms are also defined in this notation section.Source: §7.1 · p. 17
  • A continuous piecewise-linear function is linear on each interval in a finite covering, and a break point marks a change in its left and right derivatives.The ReLU function is given as an example with a break point at zero.Source: §7.1 · pp. 17–18
  • The notation NN(c1; …; cm) denotes functions implemented by ReLU MLPs satisfying the listed conditions.For example, conditions can specify input dimension, depth, width, and output dimension.Source: §7.1 · p. 18
  • Network composition is written as successive transformations from input x through hidden layers to output Φ(x).Layers without activation functions can be integrated with the following layer when estimating network size.Source: §7.1 · p. 18

7.2 Computational Lemmata

This section develops ReLU MLP constructions for exact function operations and one-dimensional sample memorization, with attention to preserving input regularity. It describes interpolation between ordered samples, derivative-jump batching in deeper networks, and the resulting networks’ widths and parameter use.

7.2.1 The Median Function

  • For d ∈ N and 2d+1 real inputs, if at least d+1 inputs lie in [y−ε,y+ε], where y ∈ R and ε > 0, their median also lies in that interval.Source: §7.2.1 · p. 19
  • A ReLU MLP computes the median of 2d + 1 non-negative inputs with width 6d + 3 and depth 11d + 3.The construction iteratively updates a candidate using distances to the inputs until it reaches the median.Source: §7.2.1 · pp. 19–21
  • A continuous piecewise-linear interpolant through sampled function values retains the function’s modulus of regularity and has an L∞ error estimate.The supplied passage states that an error estimate holds but does not include its formula.Source: §7.2.1 · p. 21

7.2.2 One-Dimensional Memorizers with Optimal Regularity

  • Proposition 7.1 introduces efficient universal memorization by two-hidden-layer MLPs with optimal regularity for one-dimensional memorizers.The supplied proposition passage gives its title and opening but no further statement details.Source: §7.2.2 · p. 23
  • For M groups of N ordered samples, a ReLU MLP of width vector [M, 4N - 2] memorizes all MN labels with at most 2MN + 2M + 8N - 4 nonzero parameters.Its output is linear between consecutive samples and constant on the two exterior intervals.Source: §7.2.2 · pp. 23, 26
  • For any ordered sample set, Theorem 7.1 gives a ReLU MLP with hidden-layer widths n1,...,nL that memorizes the labels and is linear between samples and constant on both exterior intervals.The theorem also gives an upper bound on nonzero parameters, though its formula is not legible in the supplied passage.Source: §7.2.2 · p. 27
  • As the minimum hidden-layer width nmin grows, parameter-use efficiency tends to 100% when depth L is fixed or grows more slowly than nmin.The passage notes that the displayed constants can be improved and states the same efficiency conclusion for Proposition 7.1.Source: §7.2.2 · p. 27
  • The deeper construction divides the target function’s break points into L - 1 batches and sums functions that match derivative jumps in different intervals.The construction extends the jump-matching approach of Proposition 7.1 to the prescribed hidden-layer widths.Source: §7.2.2 · pp. 27–28
  • For each batch, subtracting the line through the interval endpoints yields a function that matches that batch’s derivative jumps and vanishes outside its interval.Source: §7.2.2 · p. 28
  • Adjusting each batch network’s second hidden layer lets it serve the next batch, merging adjacent layers to reduce depth and parameter usage.Source: §7.2.2 · pp. 29–30
  • Each corrected batch function matches the target on its interval and is linear outside it, so subtracting their sum leaves derivative jumps that can be canceled to obtain a linear residual.Source: §7.2.2 · p. 31
  • The final network has hidden-layer widths at most (n1, n2, ..., nL, 8).Source: §7.2.2 · p. 33
  • A width-W, depth-D 1D MLP can memorize O(W^2D) data points with an optimal Lipschitz constant.The construction applies to samples whose inputs are sorted.Source: §7.2.2 · p. 33
  • The memorizing MLP is linear between consecutive sample inputs and constant on both exterior intervals.It has width at most W and depth at most D.Source: §7.2.2 · p. 34
  • The construction uses at most 2K + (23W - 121)D nonzero parameters for K samples.Source: §7.2.2 · p. 34

7.3 ReLU Approximations on Polytopes via the Kuhn Triangulation

Using Kuhn triangulations, the section extends continuous piecewise-linear ReLU approximation to higher dimensions and studies the resulting interpolants on polytopes. These approximators can achieve about the same global error with a lower Lipschitz constant despite requiring more width, and preserve an ℓ1 modulus of regularity determined solely by lattice-point values.

7.3 ReLU Approximations on Polytopes via the Kuhn Triangulation

  • Compared with the approximators in Theorem 6.2, the higher-dimensional continuous piecewise-linear approximators require more width but achieve about the same global error with a lower Lipschitz constant.Source: §7.3 · p. 34
  • A periodic, symmetric family of hyperplanes triangulates every unit cube in R^d using the Kuhn triangulation, with intersections of d hyperplanes at a single point lying on the integer lattice.The hyperplanes include coordinate planes x_i = k and pairwise-sum or difference planes x_i ± x_j = 2k.Source: §7.3 · pp. 34–36
  • An explicit hat-function construction yields a continuous piecewise-linear interpolant on each unit cube that matches f at every integer grid point; this is the hat function discussed in.The interpolant is formed as a linear combination of hat functions centered at the grid points, weighted by f’s values there.Source: §7.3 · p. 37
  • The Kuhn-based interpolant preserves the input function’s modulus of regularity under the ℓ1 norm when it is continuous piecewise linear on each unit cube and matches the function at every integer grid point.Lemma 7.8 states that if ω is a modulus of regularity for f, it is also a modulus of regularity for Φ.Source: §7.3 · p. 38
  • The interpolant Φ has ω-regularity under the ℓ1 norm on R^d, established by constructing paths within simplices and using induction on their faces.The paths preserve linearly changing ℓ1 distances and reach the points at the same time, allowing concavity of ω to extend regularity from path endpoints to intermediate points.Source: §7.3 · pp. 40, 42
  • The regularity modulus can be the minimum concave function satisfying the bounds on lattice-point differences, so it depends only on f’s lattice values.The resulting modulus is polygonal.Source: §7.3 · p. 44
  • Corollary 7.2 applies this result to continuous piecewise-linear Φ on each unit cube, provided Φ agrees with f at every lattice point.Any monotone increasing, concave function satisfying the stated bounds on lattice-point differences is a modulus of regularity for Φ under the ℓ1 norm.Source: §7.3 · p. 44

7.4 Proof of the Main Result (Theorem 4.1)

The proof builds an approximating network by scaling the target and interpolating its values on a lattice. The construction matches the target on grid points, preserves its modulus of regularity, and has explicit width and depth bounds.

7.4 Proof of the Main Result (Theorem 4.1)

  • The construction scales the target function onto [0,n]^d before building a continuous piecewise-linear interpolant on unit cubes.The interpolant is affine on simplices of the specified triangulation and agrees with the scaled function at lattice points.Source: §7.4 · pp. 44–45
  • The constructed network matches the target function at every point of the finite lattice grid.The proof defines the grid using N(n)=(1+n)^d sample points and establishes Φ(x_i)=f(x_i).Source: §7.4 · p. 45
  • The approximation preserves the target's modulus of regularity, with |Φ(x)−Φ(y)|≤ω(‖x−y‖_1) on [0,1]^d.The proof first establishes regularity for the scaled construction, then transfers the bound to Φ.Source: §7.4 · p. 45
  • The paper shows that Φ can be implemented by a ReLU MLP, with width at most 8d(n+1)^d and depth at most ⌈log2 d⌉+4.Source: §7.4 · pp. 45, 47

7.5 Proof of Secondary Approximation Results

The secondary approximation proofs arrange subnetworks across layers and use coordinate-wise projection onto the unit cube to extend the construction while preserving its regularity. The statistical proof bounds complexity using network norm constraints and concentration for sub-Gaussian inputs.

7.5 Proof of Secondary Approximation Results

  • The construction distributes (n+1)^d subnetworks across L layers, with nonzero parameters bounded by 16d(n+1)^d + L(d+2).The proof also bounds the resulting width using the largest number of subnetworks assigned to a layer.Source: §7.5 · pp. 48–49
  • Coordinate-wise projection onto [0,1]^d keeps the approximator within the domain and preserves its modulus of regularity.The projection is nonexpansive in the ℓ1 norm, so composing with it preserves the stated regularity bound.Source: §7.5 · p. 49
  • The projected network has width at most 8d(n+1)^d and depth at most ⌊log2 d⌋ + 5.The proof obtains these bounds for a uniformly continuous ReLU MLP with the specified modulus of regularity.Source: §7.5 · pp. 49–50

7.5.1 Proof of Statistical Result - Theorem 4.2

  • The statistical proof bounds empirical Rademacher complexity using network norm constraints and matrix-norm estimates.It also applies a concentration result for independent sub-Gaussian, isotropic rows to control a random matrix's maximal singular value.Source: §7.5.1 · p. 51

7.6 Proof of Neural McShane Theorem

A finite-set function with modulus of regularity ω can be extended to the cube as an ω-uniformly continuous function. Applying Theorem 4.1 then yields a neural-network extension that agrees with the original function on the finite set.

7.6 Proof of Neural McShane Theorem

  • The proof extends f from a finite nonempty set A to an ω-uniformly continuous function F on [0,1]^d, then applies Theorem 4.1 to obtain agreement on A.A is contained in a sufficiently fine dyadic grid, where the theorem's interpolation property applies.Source: §7.6 · p. 52

7.7 Proof of Results in the Discussion Section

The proofs establish uniqueness of the Kuhn triangulation under a regularity-preservation condition and construct a Hölder-regular approximator using medians of networks over shifted cuboid partitions. They define cuboid centers and an interpolating piecewise linear function, then use the median’s regularity-preserving property to conclude.

Proof of Theorem 6.1

  • For n=1, the Kuhn triangulation is unique up to reflections among triangulations whose piecewise-linear approximators preserve every Lipschitz function’s linear regularity modulus.The proof considers the stronger statement in the setting of Lemma 7.8.Source: §7.7 · pp. 52–53
  • Each cube-face restriction of a qualifying triangulation is itself a triangulation and, by induction, a reflected Kuhn triangulation.Extending a counterexample on a face to the cube would contradict regularity preservation.Source: §7.7 · p. 53
  • The proof forces the separating hyperplanes to match the Kuhn arrangement: the remaining hyperplanes involving x_d must all have one consistent form, since a mixed choice would intersect at a non-lattice point.For pairs among the first d−1 coordinates, the separating hyperplanes are x_i − x_j = 0; the remaining choices are consistently x_i − x_d = 0 or x_i + x_d = 1, up to reflections.Source: §7.7 · pp. 54–55

Proof of Theorem 6.2

  • Using a median of 2d+1 MLPs instead of 3^d as in [80] permits larger trifling regions and yields a lower Lipschitz constant.The networks use different trifling regions, with sample values assigned on the other cuboids.Source: §7.7 · p. 55
  • The construction maps each cuboid to a distinct constant with a projection network of width (2n+1)^d and depth 3, then memorizes cuboid-center values with a width 2⌊(n+1)^d/2⌋ network of depth 3.The memorizer is linear between successive integer inputs.Source: §7.7 · pp. 55–57
  • Every input lies in at least d+1 of the 2d+1 cuboid collections, so taking the median retains controlled approximation error.On each covered cuboid, the estimate uses the function value at its center, with error bounded by ν times the center-to-input distance raised to α.Source: §7.7 · pp. 57–58

7.7 Proof of Results in the Discussion Section

  • The proof indexes a cuboid using digits a_1 through a_d in base n + 1, with each digit in {0, 1, ..., n}, and identifies its center.The center is that of the unique cuboid in Q_k corresponding to the index.Source: §7.7 · p. 58
  • The function ϕ_k is the unique continuous piecewise linear function through the specified points, linear between adjacent points.The points are indexed from j = 0 to (n + 1)^d − 1 and pair p_j with f(P_k(p_j)).Source: §7.7 · p. 58
  • The proof concludes by applying Lemma 7.3, which states that the median function preserves regularity.The passage then says, “This concludes our proof.”Source: §7.7 · p. 58
Loading 2409.12335v4…