Multigrade Neural Network Approximation

Shijun Zhang; Zuowei Shen; Yuesheng Xu

cs.LGJan 23, 2026

Multigrade Neural Network Approximation

Authors: Shijun Zhang, Zuowei Shen, Yuesheng Xu

Organizations: Department of Applied Mathematics, Hong Kong Polytechnic University · Department of Mathematics, National University of Singapore · Department of Mathematics and Statistics, Old Dominion University

Abstract

We study multigrade deep learning (MGDL) as a principled framework for structured error refinement in deep neural networks. While the approximation power of neural networks is now relatively well understood, training very deep architectures remains challenging due to highly nonconvex and often ill-conditioned optimization landscapes. In contrast, for relatively shallow networks, most notably certain one-hidden-layer ReLU models, training admits convex reformulations with global guarantees under appropriate settings, motivating learning paradigms that improve stability while scaling to depth. MGDL builds on this insight by training deep networks grade by grade: previously learned grades are frozen, and each newly added grade-wise subnetwork is composed on top of the previously learned grades and trained to fit the residual left by the current approximation, yielding a structured and interpretable hierarchical refinement process. We develop an operator-theoretic foundation for MGDL and prove that, for any continuous target function defined on a hypercube, there exists a fixed-width multigrade ReLU scheme whose residuals are pointwise nonincreasing in magnitude and converge uniformly to zero, with strict $L^p$ -norm decay at every nontrivial grade for $p\in [1,\infty)$ . To the best of our knowledge, this work provides the first rigorous constructive approximation guarantee showing that a grade-wise residual refinement scheme can achieve vanishing error in a fixed-width multigrade ReLU architecture.

Figures & tables

Figure 1: Overview of the framework and its grade-wise training procedure. Training proceeds grade by grade: at each grade, only the newly added block and the output map are optimized, while all previously learned blocks are frozen and serve as adaptive basis components. The network

\Phi_{k}

approximates the target function via a recursive residual refinement process.

Figure 2: Overview of the MGDL grade-wise training procedure.

Panel of Figure 3 — Figure 3: The target functions $f_{1}$ and $f_{2}$ used in the numerical experiments, with $f_{2}$ shown as a heatmap and a surface plot.

Figure 4: Error curves for

f_{1}

(top row) and

f_{2}

(bottom row). The curves and translucent envelopes denote the mean and one standard deviation over

32

independent trials, respectively. The shaded regions mark individual grades (

\mathrm{G}1

–

\mathrm{G}4

for

f_{1}

and

\mathrm{G}1

–

\mathrm{G}3

for

f_{2}

). The horizontal axis denotes training epochs, and the vertical axis reports the base-10 logarithm of the error.

	Training error (MSE)		Test error (MSE)		Test error (MaxE)
	FCNN	MGDL	FCNN	MGDL	FCNN	MGDL
$f_{1}$	$-4.35\pm 0.49$	$-6.05\pm 0.88$	$-4.28\pm 0.47$	$-5.48\pm 0.74$	$-1.10\pm 0.31$	$-1.40\pm 0.42$
$f_{2}$	$-3.13\pm 0.11$	$-3.45\pm 0.09$	$-3.12\pm 0.10$	$-3.37\pm 0.08$	$-0.53\pm 0.08$	$-0.66\pm 0.07$

Table 1: Final error comparison between the end-to-end FCNN baseline and the MGDL model. All entries are reported as mean

\pm

standard deviation over

32

independent trials, computed after applying the base-10 logarithm to each error.

Figure 5: Comparison of FCNN and MGDL via error curves for

f_{1}

(top row) and

f_{2}

(bottom row). The curves show the mean over

32

independent trials, and the translucent envelopes around the curves indicate one standard deviation. The background shaded regions indicate the MGDL grade schedule:

\mathrm{G}1

–

\mathrm{G}4

for

f_{1}

and

\mathrm{G}1

–

\mathrm{G}3

for

f_{2}

. The horizontal axis represents training epochs, and the vertical axis displays the base-

10

logarithm of the error.

Figure 6: An illustration of cutoff functions associated with a target function

g

, where

v_{1}=\varepsilon\|g\|_{L^{\infty}([0,1]^{d})}

and

v_{2}=(1-\varepsilon)\|g\|_{L^{\infty}([0,1]^{d})}

Figure 7: An illustration of

\psi

Figure 8: An illustration of the network architecture used to realize

h_{k}

for

{\bm{x}}\in[0,1]^{d}

Neural Network Approximation Theory

Neural network approximation theory studies how network size, depth, activations, and structure determine the accuracy of functions and operators.

See all 242 papers

Apr 22, 2026

Layer-wise Geometric Approximation Rates for Deep Networks

Depth is widely viewed as a central contributor to the success of deep neural networks, whereas standard neural network approximation theory typically provides guarantees only for the final output and leaves the role of intermediate layers largely unclear. We address this gap by developing a quantitative framework in which depth admits a precise scale-dependent interpretation. Specifically, we design a single shared mixed-activation architecture of fixed width

2dN+d+2

and any prescribed finite depth such that each intermediate readout

Φ_\ell

is itself an approximant to the target function

f

. For

f\in L^p([0,1]^d)

with

p\in [1,\infty)

, the approximation error of

Φ_\ell

is controlled by

(2d+1)

times the

L^p

modulus of continuity at the geometric scale

N^{-\ell}

for all

\ell

. The estimate reduces to the geometric rate

(2d+1)N^{-\ell}

f

1

-Lipschitz. Our network design is inspired by multigrade deep learning, where depth serves as a progressive refinement mechanism. For every prescribed terminal depth, the construction yields a finite nested family of prefix readouts whose earlier correction terms remain embedded in later readouts. Thus the approximation may be truncated within the prescribed depth range once the desired certified accuracy is reached.

Shijun Zhang, Zuowei Shen, Yuesheng Xu

Department of Applied Mathematics Hong Kong Polytechnic University · Department of Mathematics National University of Singapore · Department of Mathematics and Statistics Old Dominion University

Neural Network Approximation Theory Neural Network Expressivity

Ask PDF

Oct 20, 2026

Depth Separation for Neural Networks under Gaussian Measure

We revisit the problem of depth separation for neural networks, as studied by Eldan and Shamir, Daniely, and others. Specifically, we consider the natural setting of

L^2

approximation of radial functions under the standard Gaussian measure in

d

dimensions. We show that there is a radial function in

L^2

under the standard Gaussian measure that can be approximated to a fixed sufficiently small

L^2

error by a depth-3 ReLU neural network of polynomial size in

d

but can only be approximated by depth-2 networks with subexponentially bounded weights if their size is at least exponential in

d

. For that, we prove a general result showing that if a radial function has substantial mass in the high frequencies of its Hermite expansion, then it cannot be well approximated by a depth-2 neural network with small width and bounded weights. All theorems, lemmas, propositions, and corollaries are verified in Lean~4.

Cynthia Bortolotto, Francisco Ganacim, Roberto I. Oliveira

Neural Network Approximation Theory ReLU Neural Networks

Ask PDF

Sep 14, 2026

Approximating Smooth Functionals with ReLU Networks

We study the uniform approximation of smooth scalar-valued functionals on an infinite-dimensional separable Hilbert space by ReLU neural networks. A key feature in deep learning for functional data is the varying importance of different coordinates/dimensions. Representing the functional input in a basis expansion, we quantify the importance of each coordinate through both the magnitude of its corresponding basis score and the directional sensitivity of the target functional. Our analysis combines coordinate truncation, anisotropic partitioning, local Taylor approximation, and ReLU network realization, while allowing unrestricted interactions among the retained coordinates. We establish a general nonasymptotic upper bound for the uniform approximation error and a complementary pseudo-dimension-based lower bound for the worst-case approximation error. Under generalized exponential coordinate decay

w_ds_d\asymp\exp(-cd^ρ)

, with

ρ>0

, the upper and lower bounds match at the leading order, which is stretched-exponential in the logarithm of the network size budget, and thus yield the nearly optimal approximation rate. This is the first work to characterize neural network approximation error for infinite-dimensional functional inputs explicitly through the joint dimensional decay of coordinate magnitudes and directional sensitivities.

Shuhao Jiao

Department of Biostatistics, City University of Hong Kong, Hong Kong SAR, China.

ReLU Neural Networks Neural Network Approximation Theory

Ask PDF

Abstract

Neural Network Approximation Theory

Explore similar work

Layer-wise Geometric Approximation Rates for Deep Networks

Depth Separation for Neural Networks under Gaussian Measure

Approximating Smooth Functionals with ReLU Networks