# Multi-Grade Deep Learning

Yuesheng Xu Department of Mathematics and Statistics, Old Dominion University,
Norfolk, VA 23529, USA. E-mail address<EMAIL_ADDRESS>
###### Abstract

Deep learning requires solving a nonconvex optimization problem of a large
size to learn a deep neural network. The current deep learning model is of a
single-grade, that is, it learns a deep neural network by solving a single
nonconvex optimization problem. When the layer number of the neural network is
large, it is computationally challenging to carry out such a task efficiently.
The complexity of the task comes from learning all weight matrices and bias
vectors from one single nonconvex optimization problem of a large size.
Inspired by the human education process which arranges learning in grades, we
propose a multi-grade learning model: Instead of solving one single
optimization problem of a large size, we successively solve a number of
optimization problems of small sizes, which are organized in grades, to learn
a shallow neural network for each grade. Specifically, the current grade is to
learn the leftover from the previous grade. In each of the grades, we learn a
shallow neural network stacked on the top of the neural network, learned in
the previous grades, which remains unchanged in training of the current and
future grades. By dividing the task of learning a deep neural network into
learning several shallow neural networks, one can alleviate the severity of
the nonconvexity of the original optimization problem of a large size. When
all grades of the learning are completed, the final neural network learned is
a stair-shape neural network, which is the superposition of networks learned
from all grades. Such a model enables us to learn a deep neural network much
more effectively and efficiently. Moreover, multi-grade learning naturally
leads to adaptive learning. We prove that in the context of function
approximation if the neural network generated by a new grade is nontrivial,
the optimal error of the grade is strictly reduced from the optimal error of
the previous grade. Furthermore, we provide several proof-of-concept numerical
examples which demonstrate that the proposed multi-grade model outperforms
significantly the traditional single-grade model and is much more robust than
the traditional model.

Keywords: multi-grade deep learning, deep neural network, adaptive learning

##  1 Introduction

The immense success of deep learning (LeCun et al., 2015; Goodfellow et al.,
2016) has been widely recognized. Its great impact to science and technology
has been witnessed (Häggström et al., 2019; Krizhevsky et al., 2012; Shen et
al., 2017; Torlai et al., 2018) and will continue to deepen. From a
mathematical perspective, such successes are mainly due to the powerful
expressiveness of deep neural networks in representing a function (Daubechies
et al., 2022; Shen et al., 2021). The deep neural networks are learned by
solving optimization problems which determine their parameters (weight
matrices and bias vectors) that define them with activation functions. The
optimization problems are highly nonconvex and have large numbers of
parameters. Solving such optimization problems is challenging. Due to having
large numbers of parameters, finding a global minimizer is difficult. By
employing the stochastic gradient descent method (Bottou 1998; Bottou et al.,
2012; Kingma and Ba, 2015) to solve the optimization problems, most likely
only local minimizers may be found, since gradient-based optimization starting
from random initialization appears to often get stuck in poor solutions
(Bengio et al., 2007). Moreover, convergence of the iteration is very slow.
This has been recognized as a major computational obstacle of deep learning.

The current model of deep learning uses a single optimization problem to train
all parameters needed for the desired deep neural network. We will refer it to
as the single-grade model. When solving a single-grade learning model, the
more layers the neural network possesses, the severer its nonconvexity is, and
thus, more difficulty we would encounter when trying to solve it. The single-
grade deep learning model is like to teach a middle school student to learn
Calculus, who has no required preliminary knowledge such as elementary
algebra, trigonometry or college algebra. Even if it is not an impossible
mission, it is extremely difficult.

The goal of this study is to address this challenge. Inspired by human
learning process, we propose multi-grade deep learning models in which deep
neural networks are learned grade-by-grade from shallow to depth, with
redundancy. Instead of solving one single optimization problem with a big
number of parameters, we will solve several optimization problems, each with a
significantly smaller number of parameters which determine a shallow neural
network. After several grades of learning, we build a deep neural network with
a structure different from the one learned by the single-grade learning but
with a comparable approximation accuracy (or even better). The neural network
learned from the proposed multi-grade learning model is the superposition of
stairs-shape neural networks. Since often it is easier to learn several
shallow neural networks than a deep one, such models enable us to learn deep
neural networks much more effectively and efficiently, avoiding solving one
single optimization problem with a large number of parameters.

The proposed multi-grade deep learning model imitates the human learning
process. In our modern society, human education is often organized in five
large stages, which include elementary school, middle school, high school,
college and graduate school. Each of these stages of schooling is further
divided into different grades. For example, elementary school is normally
divided into five grades and its curriculums are designed according to the
grades, with substantial amount of redundancy, proceeding from the surface to
the inner essence, from an easy level to a sophisticated level. The knowledge
that students had learned in a current grade would serve as a basis to learn
new knowledge in the next grade. At the end of each grade, there are
examinations to ensure that students do learn what are required to know. The
human learning experience shows that the multi-grade learning is effective and
efficient.

At the technical level, the development of multi-grade learning models is
influenced by the multilevel augmentation method for solving nonlinear system
of a large size which results from discretization of Hammerstein equations, a
class of nonlinear integral equations, (Chen et al., 2009), see also (Chen et
al., 2015). Solving a Hammerstein equation by projecting it onto a piecewise
polynomial subspace that has a multiscale structure including higher levels of
resolutions boils down to solving a discrete nonlinear system of a large size.
The more levels of resolutions are included in the subspace, the higher the
accuracy of the approximate solution has. However, solving a nonlinear system
of a large size is computational expansive. With the help of the multiscale
analysis (Chen et al., 1999; Daubechies, 1992; Micchelli and Xu, 1994), we
reformulated the process of solving the nonlinear system of a large size into
two major steps: First, we solve a nonlinear system which result from
projecting the Hammerstein equation onto a subspace that contains only lower
resolution levels. We then compensate the error by solving a linear system
corresponding to the subspace that contains high resolution levels, and this
two-step process is repeated. With this reformulation, we avoid solving a
nonlinear system of a large size, and instead, we solve a nonlinear system of
a small size several times with subsidizing by solving linear systems of large
sizes. It was proved in (Chen et al., 2009) that this method generates an
approximate solution having the same accuracy order as solving the original
nonlinear system of a large size, but with significantly less computational
costs. Inspired by such an idea, we propose in this paper to reformulate the
optimization problem for learning the entire neural network as many
optimization problems for learning parts of a deep neural network. These
optimization problems are arranged in grades in the way that learning of the
current grade is to abstract information from the remainder of learning of the
previous grade. In each of the grades, we solve an optimization problem of a
significantly smaller size, which is much easier to solve than the original
entire problem. The present grade is to learn from the leftover of the
previous grade. In fact, according to (Wu et al., 2005; Wu and Xu, 2002) under
certain conditions, online gradient methods for training a class of nonlinear
feedforward shallow neural networks has guaranteed deterministic convergence.
The multi-grade learning model takes this advantage by training a number of
shallow neural networks which is a substantially easier task, avoiding
training a deep neural network which is a much difficult task.

A deep neural network learned by a multi-grade learning model differs
significantly from deep neural networks learned by the existing learning
models. In a multi-grade learning model, each grade updates the knowledge
gained from learning of the previous grades and the total knowledge learned up
to the current grade is the accumulation of the knowledge learned in all
previous grades plus the update in the current grade. Mathematically, the deep
neural network learned up to the current grade is the superposition of all the
neural networks learned in all grades so far, (see, Figure 3.1 for an
illustration). Such a neural network has great redundancy which enhances the
expressiveness in presenting data/functions.

The multi-grade learning is suitable for adaptive computation. It naturally
allows us to add a new shallow neural network to the neural network learned
from the previous grades without changing it. In particular, the multi-grade
learning model is natural for learning a solution of an operator equation such
as a partial differential equation and an integral equation, especially when
its solution has certain singularity, since it has a innate posterior error.

We organize this paper in seven sections. In section 2, we review the single-
grade learning model. Section 3 is devoted to the development of multi-grade
models. We then establish in section 4 theoretical results that justify the
proposed model. In section 5, we discuss crucial issues related to the
implementation of the proposed multi-grade learning models. In section 6, we
provide several proof-of-concept numerical examples. Finally, we make
conclusive remarks in section 7.

##  2 Deep Neural Networks: Single-Grade Learning

In this section, we recall the definition of the standard single-grade deep
learning model, and discuss its computational challenges.

Many real world problems require to learn a function from given data. Let
$s,t\in\mathbb{N}$. Suppose that we are given $m$ pairs of points
$({\bf{x}}_{i},{\bf{y}}_{i})$, $i\in\mathbb{N}_{m}:=\\{1,2,\dots,m\\}$, where
${\bf{x}}_{i}\in\mathbb{R}^{s}$ and ${\bf{y}}_{i}\in\mathbb{R}^{t}$. We wish
to learn from this set of data a function
${\bf{f}}:\mathbb{R}^{s}\to\mathbb{R}^{t}$, which represents intrinsic
information embedded in the data. Deep neural networks furnish us with an
excellent representation of the function due to their gifted expressiveness as
a result of their special structure.

We first recall the definition of a deep neural network. A deep neural network
of $n$ layers composed of $n-1$ hidden layers and one output layer is
constructed with $n$ weight matrices ${\bf{W}}_{k}$ and bias vectors
${\bf{b}}_{k}$, $k\in\mathbb{N}_{n}$, through a pre-selected activation
function $\sigma:\mathbb{R}\to\mathbb{R}$. Specifically, we suppose that
$d\in\mathbb{N}$, and for a vector
${\bf{x}}:=[x_{1},x_{2},\dots,x_{d}]^{\top}\in\mathbb{R}^{d}$, we define the
vector-valued function by the activation function

$\sigma({\bf{x}}):=[\sigma(x_{1}),\dots,\sigma(x_{d})]^{\top}.$ (2.1)

As in (Xu and Zhang, 2021), for $n$ vector-valued functions $f_{k}$,
$k\in\mathbb{N}_{n}$, such that the range of $f_{k}$ is contained in the
domain of $f_{k+1}$, $k\in\mathbb{N}_{n-1}$, the consecutive composition of
$f_{k}$, $k\in\mathbb{N}_{n}$, is denoted by

$\bigodot_{k=1}^{n}f_{k}:=f_{n}\circ f_{n-1}\circ\cdots\circ f_{2}\circ
f_{1},$ (2.2)

whose domain is that of $f_{1}$. For ${\bf{W}}_{i}\in\mathbb{R}^{m_{i}\times
m_{i-1}}$, with $m_{0}:=s$, $m_{n}:=t$ and
${\bf{b}}_{i}\in\mathbb{R}^{m_{i}}$, $i\in\mathbb{N}_{n}$, a deep neural
network is a function defined by

${\cal{N}}_{n}({\bf{x}}):=\left({\bf{W}}_{n}\bigodot_{i=1}^{n-1}\sigma({\bf{W}}_{i}\cdot+{\bf{b}}_{i})+{\bf{b}}_{n}\right)({\bf{x}}),\
\ {\bf{x}}\in\mathbb{R}^{s}.$ (2.3)

The $n$-th layer is the output layer. Clearly,
${\cal{N}}_{n}:\mathbb{R}^{s}\to\mathbb{R}^{t}$ is a vector-valued function.
From (2.3) and the definition (2.1), we have the recursion

${\cal{N}}_{1}({\bf{x}}):=\sigma({\bf{W}}_{1}{\bf{x}}+{\bf{b}}_{1})$ (2.4)

and

${\cal{N}}_{k+1}({\bf{x}})=\sigma({\bf{W}}_{k+1}{\cal{N}}_{k}({\bf{x}})+{\bf{b}}_{k+1}),\
\ {\bf{x}}\in\mathbb{R}^{s},\ \ \mbox{for all}\ \ k\in\mathbb{N}_{n-1}.$ (2.5)

Note that when $k:=n-1$, $\sigma$ in (2.5) is viewed as the identity map.

We now return to learning a function from a given data set. For $m$ pairs of
given data points $({\bf{x}}_{i},{\bf{y}}_{i})$, $i\in\mathbb{N}_{m}$, one can
learn a function

${\cal{N}}_{n}({\bf{x}}):={\cal{N}}_{n}(\\{{\bf{W}}_{j}^{*},{\bf{b}}_{j}^{*}\\}_{j=1}^{n};{\bf{x}}),\
\ {\bf{x}}\in\mathbb{R}^{s}$ (2.6)

by solving the parameters $\\{{\bf{W}}_{j}^{*},{\bf{b}}_{j}^{*}\\}_{j=1}^{n}$
with ${\bf{W}}_{j}^{*}\in\mathbb{R}^{m_{j}\times m_{j-1}}$ and
${\bf{b}}_{j}^{*}\in\mathbb{R}^{m_{j}}$ from the minimization problem

$\min\left\\{\sum_{k=1}^{m}\|{\cal{N}}_{n}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{n};{\bf{x}}_{k})-{\bf{y}}_{k}\|_{\ell_{2}}^{2}:{\bf{W}}_{j}\in\mathbb{R}^{m_{j}\times
m_{j-1}},{\bf{b}}_{j}\in\mathbb{R}^{m_{j}},j\in\mathbb{N}_{n}\right\\},$ (2.7)

where $\|\cdot\|_{\ell_{2}}$ denotes the Euclidean vector norm of
$\mathbb{R}^{t}$. When we actually solve problem (2.7) we may need to add an
appropriate regularization term if overfitting occurs. We postpone this issue
until later so that we can concentrate on crucial conceptual issues.

Learning problem (2.7) has a continuous counterpart in the context of function
approximation. For a vector-valued function
${\bf{g}}:=[g_{1},\dots,g_{t}]^{\top}:\mathbb{D}\subseteq\mathbb{R}^{s}\to\mathbb{R}^{t}$,
we define

$\|{\bf{g}}\|:=\left[\sum_{j=1}^{t}\|g_{j}\|_{2}^{2}\right]^{\frac{1}{2}},\ \
\mbox{where}\ \
\|g_{j}\|_{2}:=\left(\int_{\mathbb{D}}|g_{j}({\bf{x}})|^{2}d{\bf{x}}\right)^{\frac{1}{2}}.$

By $L_{2}(\mathbb{D},\mathbb{R}^{t})$ we denote the Hilbert space of the
functions ${\bf{g}}:\mathbb{D}\to\mathbb{R}^{t}$ with $\|{\bf{g}}\|<\infty$.
The inner-product of the space $L_{2}(\mathbb{D},\mathbb{R}^{t})$ is defined
by

$\left<{\bf{f}},{\bf{g}}\right>:=\sum_{j=1}^{t}\int_{\mathbb{D}}f_{j}({\bf{x}})g_{j}({\bf{x}})d{\bf{x}},\
\ \mbox{for}\ \ {\bf{f}},{\bf{g}}\in L_{2}(\mathbb{D},\mathbb{R}^{t}).$

Below, we describe a continuous version of learning problem (2.7). Given a
function ${\bf{f}}\in L_{2}(\mathbb{D},\mathbb{R}^{t})$, we wish to learn a
deep neural network ${\cal{N}}_{n}$ in the form of (2.6) by solving
$\\{{\bf{W}}_{j}^{*},{\bf{b}}_{j}^{*}\\}_{j=1}^{n}$ from the continuous
minimization problem

$\min\left\\{\|{\bf{f}}(\cdot)-{\cal{N}}_{n}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{n};\cdot)\|^{2}:{\bf{W}}_{j}\in\mathbb{R}^{m_{j}\times
m_{j-1}},{\bf{b}}_{j}\in\mathbb{R}^{m_{j}},j\in\mathbb{N}_{n}\right\\}.$ (2.8)

The function ${\cal{N}}_{n}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{n};\cdot)$
is called a best approximation from the set $\Omega_{n}$ of deep neural
networks having the form (2.3) to ${\bf{f}}$. Note that the set $\Omega_{n}$
is a nonconvex closed subset of $L_{2}(\mathbb{D},\mathbb{R}^{t})$.

Learning a deep neural network from either discrete data or a continuous
function boils down to finding the optimal weight matrices and bias vectors by
solving minimization problem (2.7) or (2.8). The single-grade learning model
learns the parameters of all layers together in one single grade. It is like
to ask a college student to learn Linear Algebra without any backgrounds in
High School Algebra or College Algebra, and learn all of these courses all
together. Or image how difficult will be for a college freshman who has no
College Algebra or Trigonometry knowledge to learn Calculus. Computational
challenges in solving these minimization problems come from their severe
nonconvexity, which is the result of learning all parameters at once, besides
their ill-posedness. Due to their severe nonconvexity, often their global
minimizers cannot be found. Even using the mainstream method the stochastic
gradient descent (Bottou 1998; Bottou and Bousquet, 2012) in solving
minimization problems of this type, it is time consuming. Training a deep
neural network in high dimensions requires even much more computing time.

After a deep neural network is learned, if we realize that its accuracy is not
satisfactory, then we need to train a new deep neural network with more
layers. In this case, we have to start it over to train the new one in the
single-grade learning model. This is not computationally efficient. One should
have a model which allows updating the learned neural network to form a new
one without training a complete new neural network. The multi-grade learning
model to be proposed in the next section will address these issues.

##  3 Multi-Grade Learning Models

Motivated by the human education system, we introduce in this section multi-
grade learning models to learn deep neural networks.

We first consider learning a neural network that approximates ${\bf{f}}\in
L_{2}(\mathbb{D},\mathbb{R}^{t})$. Instead of learning it by the single-grade
model (2.8), we organize the “curriculum” in $l$ grades and allow the system
to learn it in a multi-grade manner. Specifically, we choose
$k_{j}\in\mathbb{N}$, $j\in\mathbb{N}_{l}$ so that $n-1=\sum_{j=1}^{l}k_{j}$.
For each $k_{j}$, we choose a set of matrix widths
$\\{m_{k}:k=0,1,\dots,k_{j}\\}$, which may be different for different $k_{j}$,
and $m_{k_{j}}=t$. For simplicity, our notation does not indicate the
dependence of the matrix widths $m_{k}$ on $k_{j}$.

We first describe learning in grade 1. The goal of the first grade learning is
to learn the neural network ${\cal{N}}_{k_{1}}$ that takes the form of (2.3)
with $n:=k_{1}$. To this end, we define the error function of grade 1 by

${\bf{e}}_{1}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};{\bf{x}}):={\bf{f}}({\bf{x}})-{\cal{N}}_{k_{1}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};{\bf{x}}),\
\ {\bf{x}}\in\mathbb{R}^{s},$ (3.1)

where $\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}}$ are parameters to be
learned. We find the parameters
$\\{{\bf{W}}_{1,j}^{*},{\bf{b}}_{1,j}^{*}\\}_{j=1}^{k_{1}}$ from the
optimization problem

$\min\\{\|{\bf{e}}_{1}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};\cdot)\|^{2}:{\bf{W}}_{j}\in\mathbb{R}^{m_{j}\times
m_{j-1}},{\bf{b}}_{j}\in\mathbb{R}^{m_{j}},j\in\mathbb{N}_{k_{1}}\\},$ (3.2)

with $m_{0}:=s$. Once the optimal parameters
$\\{{\bf{W}}_{1,j}^{*},{\bf{b}}_{1,j}^{*}\\}_{j=1}^{k_{1}}$ are learned, we
let

${\bf{f}}_{1}({\bf{x}})={\cal{N}}^{*}_{k_{1}}({\bf{x}}):={\cal{N}}_{k_{1}}(\\{{\bf{W}}_{j}^{*},{\bf{b}}_{j}^{*}\\}_{j=1}^{k_{1}};{\bf{x}}),\
\ {\bf{x}}\in\mathbb{R}^{s},$

which is the “knowledge” about ${\bf{f}}$ that we have learned in grade 1 and
we define the optimal error of grade 1 by setting

${\bf{e}}^{*}_{1}({\bf{x}}):={\bf{f}}({\bf{x}})-{\bf{f}}_{1}({\bf{x}}),\ \
\mbox{for}\ \ {\bf{x}}\in\mathbb{R}^{s}.$

Usually, $\|{\bf{e}}^{*}_{1}\|$ is not small and thus the learning will
continue.

In grade 2, we will learn a shallow neural network on the top of
${\cal{N}}^{*}_{k_{1}}$ from ${\bf{e}}^{*}_{1}$, which is the leftover from
learning of grade 1. Specifically, we define the error function of grade 2 by

${\bf{e}}_{2}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{2}};{\bf{x}}):={\bf{e}}_{1}^{*}({\bf{x}})-({\cal{N}}_{k_{2}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{2}};\cdot)\circ{\cal{N}}^{*}_{k_{1}})({\bf{x}}),\
\ {\bf{x}}\in\mathbb{R}^{s},$ (3.3)

where ${\cal{N}}^{*}_{k_{1}}$ has been learned in grade 1 and its parameters
will be fixed in learning of the future grades. The shallow neural network
${\cal{N}}_{k_{2}}$, which has the form (2.3) with $n:=k_{2}$, will be learned
in grade 2. We find
$\\{{\bf{W}}_{2,j}^{*},{\bf{b}}_{2,j}^{*}\\}_{j=1}^{k_{1}}$ from the
optimization problem

$\min\\{\|{\bf{e}}_{2}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{2}};\cdot)\|^{2}:{\bf{W}}_{j}\in\mathbb{R}^{m_{j}\times
m_{j-1}},{\bf{b}}_{j}\in\mathbb{R}^{m_{j}},j\in\mathbb{N}_{k_{2}}\\},$ (3.4)

with $m_{0}:=t$ and $m_{k_{2}}:=t$, and we let

${\bf{f}}_{2}({\bf{x}})=({\cal{N}}^{*}_{k_{2}}\circ{\cal{N}}^{*}_{k_{1}})({\bf{x}}):=({\cal{N}}_{k_{2}}(\\{{\bf{W}}_{2,j}^{*},{\bf{b}}_{2,j}^{*}\\}_{j=1}^{k_{1}};\cdot)\circ{\cal{N}}^{*}_{k_{1}})({\bf{x}}),\
\ {\bf{x}}\in\mathbb{R}^{s}.$

Note that ${\bf{f}}_{2}$ is the newly learned neural network
${\cal{N}}_{k_{2}}^{*}$ stacked on the top of the neural network
${\cal{N}}_{k_{1}}^{*}$ learned in the previous grade. The optimal error of
grade 2 is defined by

${\bf{e}}^{*}_{2}({\bf{x}}):={\bf{e}}^{*}_{1}({\bf{x}})-{\bf{f}}_{2}({\bf{x}}),\
\ \mbox{for}\ \ {\bf{x}}\in\mathbb{R}^{s}.$

Suppose that the neural networks ${\cal{N}}^{*}_{k_{i}}$ of grades $i$, for
$i\in\mathbb{N}$, have been learned and the optimal error of grade $i$ is
given by ${\bf{e}}_{i}^{*}$. We define the error function of grade $i+1$ by

${\bf{e}}_{i+1}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i+1}};{\bf{x}}):={\bf{e}}_{i}^{*}({\bf{x}})-({\cal{N}}_{k_{i+1}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i+1}};\cdot)\circ{\cal{N}}^{*}_{k_{i}}\circ\cdots\circ{\cal{N}}^{*}_{k_{1}})({\bf{x}}),\
\ {\bf{x}}\in\mathbb{R}^{s},$

where ${\cal{N}}_{k_{i+1}}$ is a neural network to be learned in grade $i+1$
and it has the form (2.3) with $n:=k_{i+1}$. We then find
$\\{{\bf{W}}_{i+1,j}^{*},{\bf{b}}_{i+1,j}^{*}\\}_{j=1}^{k_{i+1}}$ from the
optimization problem

$\min\\{\|{\bf{e}}_{i+1}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i+1}};\cdot)\|^{2}:{\bf{W}}_{j}\in\mathbb{R}^{m_{j}\times
m_{j-1}},{\bf{b}}_{j}\in\mathbb{R}^{m_{j}},j\in\mathbb{N}_{k_{i+1}}\\},$ (3.5)

with $m_{0}:=t$ and $m_{k_{i+1}}:=t$, and we let

${\bf{f}}_{i+1}({\bf{x}}):=({\cal{N}}^{*}_{k_{i+1}}\circ{\cal{N}}^{*}_{k_{i}}\circ\cdots\circ{\cal{N}}^{*}_{k_{1}})({\bf{x}}),\
\ {\bf{x}}\in\mathbb{R}^{s},$

where
${\cal{N}}^{*}_{k_{i+1}}:={\cal{N}}_{k_{i+1}}(\\{{\bf{W}}_{i+1,j}^{*},{\bf{b}}_{i+1,j}^{*}\\}_{j=1}^{k_{i+1}};\cdot)$.
Clearly, ${\bf{f}}_{i+1}$ is a best approximation from the set

$\Omega_{i+1}:=\\{{\cal{N}}_{k_{i+1}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i+1}};\cdot)\circ{\cal{N}}^{*}_{k_{i}}\circ\cdots\circ{\cal{N}}^{*}_{k_{1}}:{\bf{W}}_{j}\in\mathbb{R}^{m_{j}\times
m_{j-1}},{\bf{b}}_{j}\in\mathbb{R}^{m_{j}},j\in\mathbb{N}_{k_{i+1}}\\}$ (3.6)

to ${\bf{e}}^{*}_{i}$. Again, ${\bf{f}}_{i+1}$ is the newly learned neural
network ${\cal{N}}_{k_{i+1}}^{*}$ stacked on the top of the neural network
${\cal{N}}_{k_{i}}^{*}\circ\cdots\circ{\cal{N}}_{k_{1}}^{*}$ learned in the
previous grades. The optimal error of grade $i+1$ is defined by

${\bf{e}}^{*}_{i+1}({\bf{x}}):={\bf{e}}^{*}_{i}({\bf{x}})-{\bf{f}}_{i+1}({\bf{x}}),\
\ \mbox{for}\ \ {\bf{x}}\in\mathbb{R}^{s}.$

Finally, the $l$ grade learning model generates the neural network

$\overline{{\bf{f}}}_{l}:=\sum_{i=1}^{l}{\bf{f}}_{i}.$ (3.7)

Unlike the neural network ${\cal{N}}_{n}$ learned by (2.8), the neural network
$\overline{{\bf{f}}}_{l}$ defined by (3.7) learned by the $l$-grade model is
the accumulation of the knowledge learned from all the grades. In each grade,
the system learns based on the knowledge gained from learning of the previous
grades. Mathematically, the neural network $\overline{{\bf{f}}}_{l}$ is the
superposition of all $l$ networks ${\bf{f}}_{i}$, $i\in\mathbb{N}_{l}$,
learned in $l$ grades, and each ${\bf{f}}_{i}$ is a shallow network learned in
grade $i$ composed with the shallow networks learned from the previous grades.
In general, the neural network $\overline{{\bf{f}}}_{l}$ has a stairs-shape.
We illustrate a three grade learning model in Figure 3.1. Note that the neural
network that results from a three grade learning model is the sum of three
networks: the network (left) learned from grade 1 plus the network (center)
learned from grade 2, which is stacked on the top of the network learned in
grade 1, and plus the network (right) learned from grade 3, which is stacked
on the top of the network learned in grade 2. The parts, bounded by dash
lines, of the networks of grades 2 and 3 are the exact copy of the networks
learned from the previous grades. They keep unchanged in training of a new
grade.

Figure 3.1: Illustration of a three-grade learning model: The stairs-shape
network - the superposition of three networks.

From the structure of the neural network, we find it suitable for adaptive
learning since when the norm of the optimal error of the current grade is not
within a given tolerance we add a new grade without changing the neural
networks learned in the previous grades. In passing, we would like to point
out that the neural network learned from the multi-grade learning model has
the flavor of the adaptive mode decomposition originally introduced in (Huang
et al., 1998), see also (Chen et al., 2006; Xu et al., 2006).

Learning a function from $m$ pairs of discrete data points
$\\{({\bf{x}}_{i},{\bf{y}}_{i})\\}_{j=1}^{m}$ may be conducted in the same
way, with the modification specified below. First of all, the error functions
are now defined by

${\bf{e}}_{1}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};{\bf{x}}_{k}):={\bf{y}}_{k}-{\cal{N}}_{k_{1}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};{\bf{x}}_{k}),\
\ k\in\mathbb{N}_{m},$

the optimal error of grade 1 by

${\bf{e}}^{*}_{1}({\bf{x}}_{k}):={\bf{e}}_{1}(\\{{\bf{W}}_{j}^{*},{\bf{b}}_{j}^{*}\\}_{j=1}^{k_{1}};{\bf{x}}_{k}),\
\ k\in\mathbb{N}_{m},$

and for $i=2,3,\dots,l$,

${\bf{e}}_{i}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i}};{\bf{x}}_{k}):={\bf{e}}_{i-1}^{*}({\bf{x}}_{k})-({\cal{N}}_{k_{i}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};\cdot)\circ{\cal{N}}^{*}_{k_{i-1}}\circ\cdots\circ{\cal{N}}^{*}_{k_{1}})({\bf{x}}_{k}),\
\ k\in\mathbb{N}_{m},$

and the optimal error of grade $i$ by

${\bf{e}}^{*}_{i}({\bf{x}}_{k}):={\bf{e}}_{i}(\\{{\bf{W}}_{j}^{*},{\bf{b}}_{j}^{*}\\}_{j=1}^{k_{i}};{\bf{x}}_{k}),\
\ k\in\mathbb{N}_{m}.$

The $L_{2}$-norm square in the minimization problems (3.2), (3.4) and (3.5) is
replaced by the discrete forms

$\|{\bf{e}}_{1}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};\cdot)\|_{m}^{2}:=\sum_{k=1}^{m}\|{\bf{y}}_{k}-{\cal{N}}_{k_{1}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};{\bf{x}}_{k})\|_{\ell_{2}}^{2}$
(3.8)

and for $i=2,3,\dots,l$,

$\|{\bf{e}}_{i}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i}};\cdot)\|_{m}^{2}:=\sum_{k=1}^{m}\|{\bf{e}}_{i-1}^{*}({\bf{x}}_{k})-({\cal{N}}_{k_{i}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};\cdot)\circ{\cal{N}}^{*}_{k_{i-1}}\circ\cdots\circ{\cal{N}}^{*}_{k_{1}})({\bf{x}}_{k})\|_{\ell_{2}}^{2}.$
(3.9)

Everything else remains the same as the function approximation case.

Learning a solution of an operator equation, such as initial/boundary value
problems of linear/nonlinear differential equations, integral equations and
functional equations, can be carried out in the same way. Note that learning a
solution of nonlinear differential equations by the single-grade learning
model was recently considered by (Raissi 2018; Xu and Zeng, 2023). Let
${\cal{G}}$ denote a nonlinear operator and we consider the operator equation

${\cal{G}}({\bf{f}})=0,$ (3.10)

where ${\bf{f}}:\mathbb{R}^{s}\to\mathbb{R}^{t}$ is a solution to be learned.
For an initial value problem or a boundary value problem of a differential
equation, the operator ${\cal{G}}$ includes the initial value conditions
or/and the boundary value conditions.

We will learn a solution ${\bf{f}}$ of equation (3.10) by the $l$-grade
learning model. We define the error function of grade 1 by

${\bf{e}}_{i}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};\cdot):={\cal{G}}({\cal{N}}_{k_{1}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};\cdot)).$

We then find $\\{{\bf{W}}_{1,j}^{*},{\bf{b}}_{1,j}^{*}\\}_{j=1}^{k_{1}}$ by
solving

$\min\left\\{\sum_{k=1}^{m}\|{\bf{e}}_{i}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};{\bf{x}}_{k}))\|_{\ell_{2}}^{2}:{\bf{W}}_{j}\in\mathbb{R}^{m_{j}\times
m_{j-1}},{\bf{b}}_{j}\in\mathbb{R}^{m_{j}},j\in\mathbb{N}_{k_{1}}\right\\},$
(3.11)

with $m_{0}:=s$ and $m_{k_{1}}:=t$, and obtain the knowledge of grade 1 for
the solution of equation (3.10), which has the form

${\bf{f}}_{1}:={\cal{N}}_{k_{1}}^{*}={\cal{N}}_{k_{1}}(\\{{\bf{W}}_{1,j}^{*},{\bf{b}}_{1,j}^{*}\\}_{j=1}^{k_{1}};\cdot).$
(3.12)

For $i=2,3,\dots,l$, we successively define the error function of grade $i$ by

${\bf{e}}_{i}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i}};{\bf{x}}):={\cal{G}}\left(\sum_{\mu=1}^{i-1}{\bf{f}}_{\mu}({\bf{x}})+({\cal{N}}_{k_{i}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i}};\cdot)\circ{\bf{f}}_{i-1}\circ\cdots\circ{\bf{f}}_{1})({\bf{x}})\right)$

and find $\\{{\bf{W}}_{i,j}^{*},{\bf{b}}_{i,j}^{*}\\}_{j=1}^{k_{i}}$ by
solving the minimization problems

$\min\left\\{\sum_{k=1}^{m}\left\|{\bf{e}}_{i}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i}};{\bf{x}}_{k})\right\|_{\ell_{2}}^{2}:{\bf{W}}_{j}\in\mathbb{R}^{m_{j}\times
m_{j-1}},{\bf{b}}_{j}\in\mathbb{R}^{m_{j}},j\in\mathbb{N}_{k_{i}}\right\\},$
(3.13)

with $m_{0}:=t$ and $m_{k_{i}}:=t$. We let

${\bf{f}}_{i}:={\cal{N}}_{k_{i}}(\\{{\bf{W}}_{i,j}^{*},{\bf{b}}_{i,j}^{*}\\}_{j=1}^{k_{i}};\cdot)\circ{\bf{f}}_{i-1}\circ\cdots\circ{\bf{f}}_{1},\
\ i=2,3,\dots l.$ (3.14)

We define the optimal error of grade $i$ by
${\bf{e}}_{i}^{*}:={\bf{e}}_{i}(\\{{\bf{W}}_{j}^{*},{\bf{b}}_{j}^{*}\\}_{j=1}^{k_{i}};{\bf{x}}).$
The learning stops if $\|{\bf{e}}^{*}_{i}\|_{\ell_{2}}$ is within a given
tolerant error bound or we reach the maximal grade number $l$. When the
$l$-grade learning process is completed, we obtain the neural network

$\overline{{\bf{f}}}_{l}:=\sum_{i=1}^{l}{\bf{f}}_{i},$ (3.15)

which serves as an approximate solution of the operator equation (3.10).

The proposed multi-grade learning is particularly suitable for adaptive
solutions of operator equations. In this case, we have a nature posterior
error $\|{\bf{e}}^{*}_{i}\|_{\ell_{2}}$ to control the stop of learning.
Moreover, the multi-grade learning model allows us to add a new term
${\bf{f}}_{i+1}$ to $\overline{{\bf{f}}}_{i}$ if
$\|{\bf{e}}^{*}_{i}\|_{\ell_{2}}$ is not within the given tolerance, without
starting over to learn the entire neural network.

The proposed multi-grade model works for other norms. As an example, we
consider classification using the categorical cross entropy loss function
(Brownlee 2019). Given data
$\\{({\bf{x}}_{k},y_{k})\\}_{k=1}^{m}\subset\mathbb{R}^{s}\times\mathbb{N}_{t}$,
where ${\bf{x}}_{k}$ are observations and $y_{k}$ are labels, we wish to find
a classifier ${\cal{C}}:\mathbb{R}^{s}\to\mathbb{N}_{t}$ such that it
correctly classifies the training data pairs and as well as new data points
not in the given data set. For a given true label
${\bf{y}}:=[y_{1},\dots,y_{t}]^{\top}\in\mathbb{R}^{r}$ and its prediction
$\hat{\bf{y}}:=[\hat{y}_{1},\dots,\hat{y}_{t}]^{\top}$, we define the
individual categorical cross entropy by

$L({\bf{y}},\hat{\bf{y}}):=\sum_{k=1}^{t}y_{k}\ln(\hat{y}_{k}).$ (3.16)

The standard deep learning model for classification is to find
${\bf{W}}_{j}^{*}\in\mathbb{R}^{m_{j}\times m_{j-1}}$,
${\bf{b}}_{j}^{*}\in\mathbb{R}^{m_{j}}$, $j\in\mathbb{N}_{n}$ with $m_{0}:=s$
and $m_{n}:=t$ such that

$\min\left\\{-\frac{1}{m}\sum_{k=1}^{m}L({\bf{y}}_{k},{\cal{N}}_{n}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{n};{\bf{x}}_{k})):{\bf{W}}_{j}\in\mathbb{R}^{m_{j}\times
m_{j-1}},{\bf{b}}_{j}\in\mathbb{R}^{m_{j}},j\in\mathbb{N}_{n}\right\\},$
(3.17)

where $L$ is defined by (3.16). When the dimension $t$ of the vector-valued
prediction function is large, solving the nonconvex optimization problem
(3.17) with a large number $n$ of layers is a challenging task if it is not
impossible. The proposed multi-grade model can overcome this computational
challenge since instead of solving one nonconvex optimization problem of a
large size for one deep neural network, we solve nonconvex optimization
problems of small sizes for several shallow neural networks.

We now describe the $l$-grade learning model for the classification problem.
We first learn ${\bf{W}}_{1,j}^{*}\in\mathbb{R}^{m_{j}\times m_{j-1}}$,
${\bf{b}}_{1,j}^{*}\in\mathbb{R}^{m_{j}}$, $j\in\mathbb{N}_{k_{1}}$ with
$m_{0}:=s$ and $m_{k_{1}}:=t$ such that

$\min\left\\{-\frac{1}{m}\sum_{k=1}^{m}L({\bf{y}}_{k},{\cal{N}}_{k_{1}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{1}};{\bf{x}}_{k})):{\bf{W}}_{j}\in\mathbb{R}^{m_{j}\times
m_{j-1}},{\bf{b}}_{j}\in\mathbb{R}^{m_{j}},j\in\mathbb{N}_{k_{1}}\right\\},$
(3.18)

and define prediction ${\bf{f}}_{1}$ of grade 1 in the same way as in (3.12).
For $i=2,3,\dots,l$, we define possible predictions of grade $i$ by

$\tilde{\bf{y}}_{i}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i}};{\bf{x}}_{k}):=\sum_{\mu=1}^{i-1}{\bf{f}}_{\mu}({\bf{x}}_{k})+({\cal{N}}_{k_{i}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i}};\cdot)\circ{\bf{f}}_{i-1}\circ\cdots\circ{\bf{f}}_{1})({\bf{x}}_{k}).$

We then successively learn ${\bf{W}}_{i,j}^{*}\in\mathbb{R}^{m_{j}\times
m_{j-1}}$, ${\bf{b}}_{i,j}^{*}\in\mathbb{R}^{m_{j}}$, $j\in\mathbb{N}_{k_{i}}$
with $m_{0}=m_{k_{i}}:=t$ such that

$\min\left\\{-\frac{1}{m}\sum_{k=1}^{m}L({\bf{y}}_{k},\tilde{\bf{y}}_{i}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i}};{\bf{x}}_{k})):{\bf{W}}_{j}\in\mathbb{R}^{m_{j}\times
m_{j-1}},{\bf{b}}_{j}\in\mathbb{R}^{m_{j}},j\in\mathbb{N}_{k_{1}}\right\\},$
(3.19)

and define prediction ${\bf{f}}_{i}$ of grade $i$ by setting

${\bf{f}}_{i}({\bf{x}}):=({\cal{N}}_{k_{i}}(\\{{\bf{W}}_{i,j}^{*},{\bf{b}}_{i,j}^{*}\\}_{j=1}^{k_{i}};\cdot)\circ{\bf{f}}_{i-1}\circ\cdots\circ{\bf{f}}_{1})({\bf{x}}),\
\ {\bf{x}}\in\mathbb{R}^{s}.$

When all $l$ grades of learning are completed, we obtain our prediction
$\overline{{\bf{f}}}_{l}$ which has the same form as in (3.15).

##  4 Analysis of the Multi-Grade Learning Model

We analyze in this section the proposed multi-grade learning model. The main
result is the optimal error of a multi-grade learning model decreases as the
number of grades increases. To this end, we first present several useful
observations regarding a best approximation from a nonconvex set, which are
interesting in their own right.

Let ${\cal{H}}$ denote a Hilbert space and $\Omega$ a closed set (not
necessarily convex) in ${\cal{H}}$. We wish to understand a best approximation
from $\Omega$ to an ${\bf{f}}\in{\cal{H}}$. We first present a necessary
condition and a sufficient condition for an element to be a best
approximation. To this end, we define a star-shape set centered at a given
${\bf{g}}_{0}\in\Omega$ by

$\Omega({\bf{g}}_{0}):=\\{{\bf{g}}\in\Omega:\lambda{\bf{g}}+(1-\lambda){\bf{g}}_{0}\in\Omega\
\mbox{for all}\ \lambda\in(0,1)\\}.$ (4.1)

Clearly, a point ${\bf{g}}$ of $\Omega$ is in $\Omega({\bf{g}}_{0})$ if and
only if the line segment connecting the two points ${\bf{g}}_{0}$ and
${\bf{g}}$ is completely located in $\Omega$.

###### Theorem 4.1

Suppose that ${\cal{H}}$ is a Hilbert space and $\Omega$ is a closed set in
${\cal{H}}$. Let ${\bf{f}}\in{\cal{H}}\setminus\Omega$.

(i) If ${\bf{g}}_{0}\in\Omega$ is a best approximation from $\Omega$ to
${\bf{f}}$, then for all ${\bf{g}}\in\Omega({\bf{g}}_{0})$,

$\left<{\bf{f}}-{\bf{g}}_{0},{\bf{g}}-{\bf{g}}_{0}\right>\leq 0.$ (4.2)

(ii) If ${\bf{g}}_{0}\in\Omega$ and (4.2) holds for all ${\bf{g}}\in\Omega$,
then ${\bf{g}}_{0}$ is a best approximation from $\Omega$ to ${\bf{f}}$.

Proof: (i) Assume that (4.2) does not hold for all
${\bf{g}}\in\Omega({\bf{g}}_{0})$. Then, there exists some
${\bf{g}}\in\Omega({\bf{g}}_{0})$ such that

$\left<{\bf{f}}-{\bf{g}}_{0},{\bf{g}}-{\bf{g}}_{0}\right>>0.$

Since ${\bf{g}}\in\Omega({\bf{g}}_{0})$, by the definition of
$\Omega({\bf{g}}_{0})$, we observe that

${\bf{g}}_{\lambda}:=\lambda{\bf{g}}+(1-\lambda){\bf{g}}_{0}\in\Omega,\ \
\mbox{for all}\ \ \lambda\in(0,1).$

Hence, we have that

${\bf{f}}-{\bf{g}}_{\lambda}={\bf{f}}-{\bf{g}}_{0}-\lambda({\bf{g}}-{\bf{g}}_{0}).$

This, with a direct computation, leads to

$\|{\bf{f}}-{\bf{g}}_{\lambda}\|^{2}=\|{\bf{f}}-{\bf{g}}_{0}\|^{2}-\lambda(2\left<{\bf{f}}-{\bf{g}}_{0},{\bf{g}}-{\bf{g}}_{0}\right>-\lambda\|{\bf{g}}-{\bf{g}}_{0}\|^{2}).$

Upon choosing $\lambda$ to satisfy

$0<\lambda<\min\left\\{1,\frac{2\left<{\bf{f}}-{\bf{g}}_{0},{\bf{g}}-{\bf{g}}_{0}\right>}{\|{\bf{g}}-{\bf{g}}_{0}\|^{2}}\right\\},$

we obtain that $\|{\bf{f}}-{\bf{g}}_{\lambda}\|<\|{\bf{f}}-{\bf{g}}_{0}\|$.
That is, ${\bf{g}}_{0}$ is not a best approximation from $\Omega$ to
${\bf{f}}$, a contradiction. The contradiction implies that (4.2) must hold
for all ${\bf{g}}\in\Omega({\bf{g}}_{0})$.

(ii) By hypothesis, for all ${\bf{g}}\in\Omega$, we observe that

$\displaystyle\|{\bf{f}}-{\bf{g}}_{0}\|^{2}$
$\displaystyle=\left<{\bf{f}}-{\bf{g}}_{0},{\bf{f}}-{\bf{g}}\right>+\left<{\bf{f}}-{\bf{g}}_{0},{\bf{g}}-{\bf{g}}_{0}\right>$
$\displaystyle\leq\left<{\bf{f}}-{\bf{g}}_{0},{\bf{f}}-{\bf{g}}\right>$
$\displaystyle\leq\|{\bf{f}}-{\bf{g}}_{0}\|\|{\bf{f}}-{\bf{g}}\|.$

This implies that

$\|{\bf{f}}-{\bf{g}}_{0}\|\leq\|{\bf{f}}-{\bf{g}}\|,\ \ \mbox{for all}\ \
{\bf{g}}\in\Omega.$

That is, ${\bf{g}}_{0}$ is a best approximation from $\Omega$ to ${\bf{f}}$.
$\Box$

Note that in general, $\Omega({\bf{g}}_{0})\neq\Omega$, and thus, the
necessary condition stated in Theorem 4.1 is not the same as the sufficient
condition. However, under some condition, they can be the same. The following
special result is a corollary of Theorem 4.1.

###### Corollary 4.2

Suppose that ${\cal{H}}$ is a Hilbert space and $\Omega$ is a closed set in
${\cal{H}}$. Let ${\bf{f}}\in{\cal{H}}\setminus\Omega$. If
${\bf{g}}_{0}\in\Omega$ such that $\Omega({\bf{g}}_{0})=\Omega$, then
${\bf{g}}_{0}\in\Omega$ is a best approximation from $\Omega$ to ${\bf{f}}$ if
and only if

$\left<{\bf{f}}-{\bf{g}}_{0},{\bf{g}}-{\bf{g}}_{0}\right>\leq 0,\ \ \mbox{for
all}\ \ {\bf{g}}\in\Omega({\bf{g}}_{0}).$ (4.3)

Proof: When $\Omega({\bf{g}}_{0})=\Omega$, the two conditions in Items (i) and
(ii) of Theorem 4.1 are identical, which gives a characterization of a best
approximation in this special case. $\Box$

In particular, when $\Omega$ is a convex set, for any ${\bf{g}}_{0}\in\Omega$,
we have that $\Omega=\Omega({\bf{g}}_{0})$. Thus, Corollary 4.2 reduces to the
well-known characterization of a best approximation from a convex set, see,
for example, (Deutsch 2001). For this reason, Theorem 4.1 is a natural
extension of the characterization of a best approximation from a convex set to
that from a nonconvex set. In fact, Theorem 4.1 leads to a characterization of
a best approximation from a nonconvex set, which we present next. For a given
${\bf{f}}\in{\cal{H}}$ and a fixed ${\bf{g}}_{0}\in\Omega$, we let
$r_{0}:=\|{\bf{f}}-{\bf{g}}_{0}\|$ and define the open ball

$B({\bf{f}},r_{0}):=\\{{\bf{g}}\in{\cal{H}}:\|{\bf{f}}-{\bf{g}}\|<r_{0}\\}.$

Moreover, for a given ${\bf{g}}_{0}\in\Omega$, we let

$\tilde{\Omega}({\bf{g}}_{0}):=\Omega\setminus\Omega({\bf{g}}_{0})$

and

$d({\bf{f}},\tilde{\Omega}({\bf{g}}_{0})):=\inf\\{\|{\bf{f}}-{\bf{g}}\|:{\bf{g}}\in\tilde{\Omega}({\bf{g}}_{0})\\}.$

###### Theorem 4.3

Suppose that ${\cal{H}}$ is a Hilbert space and $\Omega$ is a closed set in
${\cal{H}}$. Let ${\bf{f}}\in{\cal{H}}\setminus\Omega$ and
${\bf{g}}_{0}\in\Omega$. The following statements are equivalent:

(i) The element ${\bf{g}}_{0}$ is a best approximation from $\Omega$ to
${\bf{f}}$.

(ii) There holds the equation

$B({\bf{f}},r_{0})\cap\Omega=\emptyset.$ (4.4)

(iii) The element ${\bf{g}}_{0}$ satisfies the conditions

$\left<{\bf{f}}-{\bf{g}}_{0},{\bf{g}}-{\bf{g}}_{0}\right>\leq 0,\ \ \mbox{for
all}\ \ {\bf{g}}\in\Omega({\bf{g}}_{0})$ (4.5)

and

$\|{\bf{f}}-{\bf{g}}_{0}\|\leq d({\bf{f}},\tilde{\Omega}({\bf{g}}_{0})).$
(4.6)

Proof: We first show that Items (i) and (ii) are equivalent. Suppose that
equation (4.4) holds. Let ${\bf{g}}\in\Omega$ be arbitrary. Because of (4.4),
we find that ${\bf{g}}\notin B({\bf{f}},r_{0})$. Hence, we have that
$\|{\bf{f}}-{\bf{g}}\|\geq r_{0}$. Equivalently, we find that

$\|{\bf{f}}-{\bf{g}}_{0}\|\leq\|{\bf{f}}-{\bf{g}}\|,\ \ \mbox{for all}\ \
{\bf{g}}\in\Omega.$ (4.7)

That is, ${\bf{g}}_{0}$ is a best approximation from $\Omega$ to ${\bf{f}}$.
Conversely, suppose that ${\bf{g}}_{0}$ is a best approximation from $\Omega$
to ${\bf{f}}$. Then, inequality (4.7) holds. This implies that for all
${\bf{g}}\in\Omega$, ${\bf{g}}\notin B({\bf{f}},r_{0})$. That is, equation
(4.4) holds.

We next show that Items (i) and (iii) are equivalent. Suppose that
${\bf{g}}_{0}\in\Omega$ is a best approximation from $\Omega$ to ${\bf{f}}$.
By Item (i) of Theorem 4.1, we have that (4.5). Condition (4.6) follows from
the definition of ${\bf{g}}_{0}$ being a best approximation from $\Omega$ to
${\bf{f}}$ and the fact that $\tilde{\Omega}({\bf{g}}_{0})\subseteq\Omega$.
Conversely, suppose that ${\bf{g}}_{0}\in\Omega$ satisfies both (4.5) and
(4.6). By Item (ii) of Theorem 4.1, ${\bf{g}}_{0}$ is a best approximation
from $\Omega({\bf{g}}_{0})$ to ${\bf{f}}$. That is, we have that

$\|{\bf{f}}-{\bf{g}}_{0}\|\leq\|{\bf{f}}-{\bf{g}}\|,\ \ \mbox{for all}\ \
{\bf{g}}\in\Omega({\bf{g}}_{0}).$

This together with condition (4.6) implies that

$\|{\bf{f}}-{\bf{g}}_{0}\|\leq\|{\bf{f}}-{\bf{g}}\|,\ \ \mbox{for all}\ \
{\bf{g}}\in\Omega:=\Omega({\bf{g}}_{0})\cup\tilde{\Omega}({\bf{g}}_{0}).$

In other words, ${\bf{g}}_{0}$ is a best approximation from $\Omega$ to
${\bf{f}}$. $\Box$

Figure 4.2 illustrates the characterization of a best approximation from a
nonconvex set to an element in a Hilbert space. As shown in the figure,
$\Omega$ is a nonconvex set of ${\cal{H}}$, ${\bf{f}}$ is an element in
${\cal{H}}$, not in $\Omega$, and ${\bf{g}}_{0}\in\Omega$ is a best
approximation from $\Omega$ to ${\bf{f}}$, the shaded domain is the set
$\Omega({\bf{g}}_{0})$, and $\tilde{\Omega}({\bf{g}}_{0})$ is the rest in
$\Omega$ not in $\Omega({\bf{g}}_{0})$. Intuitively, the set
$\Omega({\bf{g}}_{0})$ consists of all points in $\Omega$ which one can “see”
from the point ${\bf{g}}_{0}$. Clearly, ${\bf{g}}_{0}$ is a best approximation
from $\Omega({\bf{g}}_{0})$ to ${\bf{f}}$ and the distance of ${\bf{f}}$ to
$\tilde{\Omega}({\bf{g}}_{0})$ is larger than
$r_{0}:=\|{\bf{f}}-{\bf{g}}_{0}\|$. Therefore, ${\bf{g}}_{0}$ is a best
approximation from $\Omega$ to ${\bf{f}}$.

Figure 4.2: Projection to a Nonconvex Set

We now return to the multi-grade learning model. In the next theorem, we
represent the original function ${\bf{f}}$ in terms of the “knowledge” (neural
networks) learned in all grades and show that the norms of the optimal errors
are nonincreasing.

###### Theorem 4.4

Let ${\bf{f}}\in L_{2}(\mathbb{D},\mathbb{R}^{t})$. The following statements
hold:

(i) For all $l\in\mathbb{N}$,

${\bf{f}}({\bf{x}})=\sum_{i=1}^{l}({\cal{N}}^{*}_{k_{i}}\circ{\cal{N}}^{*}_{k_{i-1}}\circ\cdots\circ{\cal{N}}^{*}_{k_{1}})({\bf{x}})+{\bf{e}}^{*}_{l}({\bf{x}}),\
\ {\bf{x}}\in\mathbb{R}^{s}.$ (4.8)

(ii) For all $i\in\mathbb{N}$,

$\|{\bf{e}}_{i}^{*}\|^{2}\geq\|{\bf{f}}_{i+1}\|^{2}+\|{\bf{e}}^{*}_{i+1}\|^{2}.$
(4.9)

(iii) For all $i\in\mathbb{N}$,

$\|{\bf{e}}^{*}_{i+1}\|\leq\|{\bf{e}}^{*}_{i}\|,$ (4.10)

and the sequence $\|{\bf{e}}_{i}^{*}\|$, $i\in\mathbb{N}$, has a nonnegative
limit.

(iv) For each $i\in\mathbb{N}$, either ${\bf{f}}_{i+1}={\bf 0}$ or

$\|{\bf{e}}^{*}_{i+1}\|<\|{\bf{e}}^{*}_{i}\|.$ (4.11)

Proof: (i) By induction on $l$, we can express the original function
${\bf{f}}$ as

${\bf{f}}=\sum_{i=1}^{l}{\bf{f}}_{i}+{\bf{e}}^{*}_{l}.$ (4.12)

By the $l$-grade learning model, we find for each $i\in\mathbb{N}_{l}$ that

${\bf{f}}_{i}({\bf{x}}):=({\cal{N}}^{*}_{k_{i}}\circ{\cal{N}}^{*}_{k_{i-1}}\circ\cdots\circ{\cal{N}}^{*}_{k_{1}})({\bf{x}}),\
\ {\bf{x}}\in\mathbb{R}^{s}.$

Upon substituting the equation above into the right-hand-side of equation
(4.12), we obtain formula (4.8).

(ii) Note that for all $i\in\mathbb{N}$,
${\bf{e}}^{*}_{i}={\bf{f}}_{i+1}+{\bf{e}}^{*}_{i+1}$. Hence, we have that

$\|{\bf{e}}^{*}_{i}\|^{2}=\left<{\bf{f}}_{i+1}+{\bf{e}}^{*}_{i+1},{\bf{f}}_{i+1}+{\bf{e}}^{*}_{i+1}\right>.$

Expanding the inner-product on the right-hand-side of the equation above
yields that

$\|{\bf{e}}^{*}_{i}\|^{2}=\|{\bf{f}}_{i+1}\|^{2}+\|{\bf{e}}^{*}_{i+1}\|^{2}+2\left<{\bf{f}}_{i+1},{\bf{e}}^{*}_{i+1}\right>.$
(4.13)

We next apply Theorem 4.1 with ${\cal{H}}:=L_{2}(\mathbb{D},\mathbb{R}^{t})$,
${\bf{f}}:={\bf{e}}_{i}^{*}$, ${\bf{g}}_{0}:={\bf{f}}_{i+1}$ and
${\bf{g}}:={\bf 0}$. According to the definition (3.6) of $\Omega_{i+1}$, we
see that

${\bf 0}\in\Omega_{i+1}\ \ \mbox{and}\ \ \lambda{\bf
0}+(1-\lambda){\bf{f}}_{i+1}\in\Omega_{i+1},\ \ \mbox{for all}\ \
\lambda\in(0,1).$

Hence, by the definition (4.1) of set $\Omega_{i+1}({\bf{f}}_{i+1})$ with
$\Omega:=\Omega_{i+1}$ and ${\bf{g}}_{0}:={\bf{f}}_{i+1}$, we conclude that
${\bf 0}\in\Omega_{i+1}({\bf{f}}_{i+1})$. By Item (i) of Theorem 4.1, we
observe that

$\left<{\bf{f}}_{i+1},{\bf{e}}^{*}_{i+1}\right>=\left<{\bf{f}}_{i+1},{\bf{e}}^{*}_{i}-{\bf{f}}_{i+1}\right>\geq
0.$

This together with (4.13) establishes Item (ii).

(iii) Inequality (4.10) follows directly from Item (ii). The existence of the
limit of the sequence $\|{\bf{e}}_{i}^{*}\|$, $i\in\mathbb{N}$, is a direct
consequence of its nonincreasingness (4.10) and nonnegativity.

(iv) If ${\bf{f}}_{i+1}\neq{\bf 0}$, then $\|{\bf{f}}_{i+1}\|>0$. By
inequality (4.9), we obtain (4.11). $\Box$

We observe from (4.8) that the network ${\bf{f}}_{l}$ learned from the
$l$-grade model has much redundancy: ${\cal{N}}_{k_{i}}^{*}$ appears in the
network $l-i+1$ times, for $i\in\mathbb{N}_{l}$. The redundancy increases
significantly the expressiveness of the neural network.

For multi-grade learning of discrete data, we have results similar to those of
Theorem 4.4.

###### Theorem 4.5

(i) There holds for $l\in\mathbb{N}$ that

${\bf{y}}_{k}=\sum_{i=1}^{l}({\cal{N}}^{*}_{k_{i}}\circ{\cal{N}}^{*}_{k_{i-1}}\circ\cdots\circ{\cal{N}}^{*}_{k_{1}})({\bf{x}}_{k})+{\bf{e}}^{*}_{l}({\bf{x}}_{k}),\
\ k\in\mathbb{N}_{m}.$ (4.14)

(ii) For all $i\in\mathbb{N}$,

$\|{\bf{e}}_{i}^{*}\|_{m}^{2}\geq\|{\bf{f}}_{i+1}\|_{m}^{2}+\|{\bf{e}}^{*}_{i+1}\|_{m}^{2}.$
(4.15)

(iii) For all $i\in\mathbb{N}$,

$\|{\bf{e}}^{*}_{i+1}\|_{m}\leq\|{\bf{e}}^{*}_{i}\|_{m},$ (4.16)

and the sequence $\|{\bf{e}}_{i}^{*}\|_{m}$, $i\in\mathbb{N}$, has a
nonnegative limit.

(iv) For each $i\in\mathbb{N}$, either ${\bf{f}}_{i+1}={\bf 0}$ or

$\|{\bf{e}}^{*}_{i+1}\|_{m}<\|{\bf{e}}^{*}_{i}\|_{m}.$ (4.17)

Item (i) of Theorem 4.5 indicates that for an $l$-grade learning model, the
neural network
$\sum_{i=1}^{l}{\cal{N}}^{*}_{k_{i}}\circ{\cal{N}}^{*}_{k_{i-1}}\circ\cdots\circ{\cal{N}}^{*}_{k_{1}}$
“interpolates” the data points $({\bf{x}}_{k},{\bf{y}}_{k})$, for
$k\in\mathbb{N}_{m}$, up to the error ${\bf{e}}^{*}_{l}({\bf{x}}_{k})$.

Theorems 4.4 and 4.5 ensure that every grade of a multi-grade model reduces
the global approximation error if the network learned from the grade is
nontrivial.

##  5 Implementation

We discuss in this section several crucial issues in implementing the multi-
grade learning model proposed in the previous sections. These issues include
regularization to overcome over-fitting, removal of output layers for each
grade, design of the grades, and the posterior error for adaptive computation.

Solving the optimization problems involved in the multi-grade learning models
described earlier may suffer from over-fitting as solving the one involved in
the single-grade learning model does (Rice et al., 2020). When over-fitting
occurs, regularization may be necessary. One may use the $\ell_{2}$
regularization. We prefer employing the $\ell_{1}$ regularization, because it
can alleviate over-fitting and at the same time promote the sparsity (Liu et
al., 2022). Specifically, we add the vector $\ell_{1}$-norm of the weight
matrix to the minimization problems for our multi-grade learning models. We
first recall the definition of the vector $\ell_{1}$-norm of a matrix. Given a
matrix ${\bf{A}}:=[a_{ij}]\in\mathbb{R}^{t\times s}$, its vector
$\ell_{1}$-norm is defined by

$\|{\bf{A}}\|_{1}:=\sum_{i=1}^{t}\sum_{j=1}^{s}|a_{ij}|,$

the sum of the absolute values of all entries of the matrix. Note that the
vector $\ell_{1}$ norm, different from the standard $\ell_{1}$ matrix norm,
see (Horn and Johnson, 2012), is the $\ell_{1}$-norm of a matrix when it is
treated as a vector in $\mathbb{R}^{ts}$.

We next take the minimization problem (3.13) as an example to illustrate how a
regularization term is added. Instead of solving minimization problem (3.13),
we find $\\{{\bf{W}}_{i,j}^{*},{\bf{b}}_{i,j}^{*}\\}_{j=1}^{k_{i}}$ by solving
the following regularization problem

$\min\left\\{\sum_{k=1}^{m}\|{\bf{e}}_{i}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{i}};{\bf{x}}_{k})\|_{\ell_{2}}^{2}+\sum_{j=1}^{k_{i}}\lambda_{j}\|{\bf{W}}_{j}\|_{1}:{\bf{W}}_{j}\in\mathbb{R}^{m_{j}\times
m_{j-1}},{\bf{b}}_{j}\in\mathbb{R}^{m_{j}},j\in\mathbb{N}_{k_{i}}\right\\},$
(5.1)

where $\lambda_{j}>0$ are the regularization parameters. A similar
regularization approach was used in (Xu and Zeng, 2022) in training deep
neural networks. Parameter choice strategies for the $\ell_{1}$ regularization
proposed in (Liu et al., 2022) is suitable for the case when the fidelity term
is convex. One needs to extend the strategies to treat the regularization
problem (5.1) when the fidelity term is nonconvex.

In the multi-grade learning models described in section 3, each grade has an
output layer for the purpose of defining the error function for the grade. We
recommend that after the shallow neural network of the grade is learned, its
output layer be removed before entering the next grade of learning. For
example, when defining the error function
${\bf{e}}_{2}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{2}};{\bf{x}})$ of
grade 2, instead of using (3.3), we employ the modified error function

$\tilde{\bf{e}}_{2}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{2}};{\bf{x}}):={\bf{e}}_{1}^{*}({\bf{x}})-({\cal{N}}_{k_{2}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{2}};\cdot)\circ\tilde{\cal{N}}^{*}_{k_{1}})({\bf{x}}),\
\ {\bf{x}}\in\mathbb{R}^{s},$

where $\tilde{\cal{N}}^{*}_{k_{1}}$ is the shallow neural network of grade 1
after removing the output layer and the column size of
${\cal{N}}_{k_{2}}(\\{{\bf{W}}_{j},{\bf{b}}_{j}\\}_{j=1}^{k_{2}};\cdot)$ is
changed accordingly. We make the same modification for the error functions of
grades $i>2$. In this way, the learning will be more efficient.

Proper defining the “grades” is vital to the success of a multi-grade learning
model. It depends on specific applications. In general, we should take the
following factors into consideration: In each of the grades, we prefer to
training a shallow neural network because it is more efficient to learn a
shallow neural network than a deep one. However, the more grades we have, the
more overhead we pay. The overhead includes output layers of the grades.
Hence, we need to balance the depth of the shallow neural networks and the
overhead.

In the first a few grades, it is not necessary to learn networks of these
grades with high accuracy since the leftover will be learned in future grades.
If one tries to learn them with high accuracy in the first a few grades, one
may end up with spending too much times on these grades.

One of the advantages of the multi-grade learning is that it is suitable for
adaptive computation. The multi-grade learning model naturally allows us to
continuously add new grades without starting over which a single-grade
learning model would do. This requires the availability of a posterior error.
For most of learning problems, the error function for each grade can serve as
an innate posterior error.

Finally, we comment that one can use more than one activation functions to
build a neural network. Numerical examples presented in section 6 show the
advantages of using different activation functions in one neural network.
Different activation functions serve different purposes. Using different
activation functions will not change the theoretical results of Theorems 4.4
and 4.5.

##  6 Numerical Examples

We present in this section three proof-of-concept numerical examples to
demonstrate the robustness of the proposed multi-grade learning model in
comparison to the classical single-grade learning model. We will learn three
functions, which are either oscillatory or singular. For each of the
functions, we consider both noise free and noisy cases.

All the experiments reported in this section are performed with Python on an
Intel Core i7 CPU with 1.80GHz, 16 Gb RAM and 12 Gb NVIDIA GeForce MX150 GPU.

Below, we describe our experiment data for a given function $f$.

Training data: $\\{(x_{n},y_{n})\\}_{n=1}^{N}\subset[a,b]\times\mathbb{R}$,
where $N:=5,000$, $x_{n}$’s are equally spaced on $[a,b]$, and given $x_{n}$,
the corresponding $y_{n}$ is computed by $y_{n}=f(x_{n})+e_{n}$. For the noise
free cases, $e_{n}=0$ and for the noisy cases, $e_{n}$’s are independent and
identically distributed Gaussian random variables with mean 0 and standard
deviation 0.05.

Testing data:
$\\{(x^{\prime}_{n},y^{\prime}_{n})\\}_{n=1}^{N^{\prime}}\subset[a,b]\times\mathbb{R}$,
where $N^{\prime}:=1,000$, $x^{\prime}_{n}$’s are equally spaced on $[a,b]$
and given $x^{\prime}_{n}$, the corresponding $y^{\prime}_{n}$ is computed by
$y^{\prime}_{n}=f(x^{\prime}_{n})$.

Validation data: Due to the high frequency of the target function, we prefer
to have as much training data as we can. Therefore, instead of leaving out
some training data as validation data, we randomly copy $20\%$ of the training
data and add Gaussian noise with mean $0$ and standard deviation $0.01$ to the
corresponding $y$ values. The validation data remains the same for both the
multi-grade model and the classical single-grade model.

Given predictions $\hat{y}_{n}$ for $y_{n}$, the mean squared error for
training is defined by

$\mathrm{mse\ (train)}:=\frac{1}{N}\sum_{n=1}^{N}(\hat{y}_{n}-y_{n})^{2}$
(6.1)

and the relative squared error for training is defined by

$\mathrm{rse\
(train)}:=\frac{\sum_{n=1}^{N}(\hat{y}_{n}-y_{n})^{2}}{\sum_{n=1}^{N}y_{n}^{2}}.$
(6.2)

Likewise, suppose that $\hat{y}_{n}$ is an approximation for $y^{\prime}_{n}$
and we define the mean squared error and the relative squared error on the
testing data respectively by

$\mathrm{mse\
(test)}:=\frac{1}{N^{\prime}}\sum_{n=1}^{N^{\prime}}(\hat{y}_{n}-y^{\prime}_{n})^{2}$
(6.3)

and

$\mathrm{rse\
(test)}:=\frac{\sum_{n=1}^{N^{\prime}}(\hat{y}_{n}-y^{\prime}_{n})^{2}}{\sum_{n=1}^{N^{\prime}}(y^{\prime}_{n})^{2}}.$
(6.4)

For the three examples, both the noise free and noisy cases, each grade of the
multi-grade model is trained with the Adam optimizer and with batch size 32
and a learning rate decay $1.0\times 10^{-2}$. For the single-grade learning
model, we use three different epochs in training for different examples,
aiming at obtaining the best outcome for each individual example. The epochs
will be specified in each example. The training time reported in this section
is measured in seconds.

Example 1: We consider approximating the oscillatory function

$f(x)=\mathrm{sin}(100x),\ x\in[a,b]:=[0,1].$

For this example, we use the following three grade model:

$\displaystyle\mbox{Grade 1}:\ [1]\to[256]\to[256]\to[1],$
$\displaystyle\mbox{Grade 2}:\
[1]\to[256]_{\mbox{F}}\to[256]_{\mbox{F}}\to[128]\to[128]\to[64]\to[1],$
$\displaystyle\mbox{Grade 3}:\
[1]\to[256]_{\mbox{F}}\to[256]_{\mbox{F}}\to[128]_{\mbox{F}}\to[128]_{\mbox{F}}\to[64]_{\mbox{F}}\to[64]\to[32]\to[32]\to[1].$

Here, $[n]$ indicates a fully connected layer with $n$ neurons, and
$[n]_{\mbox{F}}$ indicates $[n]$ with all parameters fixed during training. We
choose the activation function for hidden layers in the first grade to be the
$\mathrm{sin}$ function and that for the remaining hidden layers to be the
ReLU function. No activation function is applied to the last layer of each
grade.

Figure 6.3: Example 1 (noise free): The training, testing and validation data.

The corresponding classic single-grade architecture is given by

$[1]\to[256]\to[256]\to[128]\to[128]\to[64]\to[64]\to[32]\to[32]\to[1],$

in which the activation function for the first two hidden layers is the
$\mathrm{sin}$ function and that for the remaining hidden layers is the ReLU
function, the same as in the multi-grade model. No activation is applied to
the last layer. The classical single-grade network is trained with Adam:
learning rate $0.01$ with decay $1.0\times 10^{-2}$ and batch size 32 for 550
epochs.

Table I: Example 1 (noise free): Training time and accuracy for each grade. grade | learning rate | epochs | training time | mse (train) | rse (train)
---|---|---|---|---|---
1 | $0.1$ | $5$ | $4.4092$ | $1.7961\times 10^{-2}$ | $3.5771\times 10^{-2}$
2 | $0.01$ | $20$ | $14.5209$ | $1.1362\times 10^{-4}$ | $2.2629\times 10^{-4}$
3 | $0.01$ | $40$ | $30.0601$ | $2.0203\times 10^{-5}$ | $4.0237\times 10^{-5}$

The training, testing and the validation data for the noise free case of
Example 1 are plotted in Figure 6.3. Numerical results for this case are
listed in Tables I and II. The corresponding figures are plotted in Figures
6.4 and 6.5.

Table II: Example 1 (noise free): multi-grade vs single-grade. method | training time | mse (train) | rse (train) | mse (test) | rse (test)
---|---|---|---|---|---
multi-grade | 48.9902 | $2.0203\times 10^{-5}$ | $4.0237\times 10^{-5}$ | $2.1450\times 10^{-5}$ | $4.2746\times 10^{-5}$
single-grade | 485.7447 | $3.1399\times 10^{-1}$ | $6.2534\times 10^{-1}$ | $3.1374\times 10^{-1}$ | $6.2522\times 10^{-1}$
|
---|---
|
Figure 6.4: Example 1 (noise free): Loss curves during training: (a)-(c)
multi-grade; (d) single-grade.

|
---|---

---

Figure 6.5: Example 1 (noise free) - Predictions on the testing set: (a) after
each grade of multi-grade; (b) multi-grade; (c) single-grade.

The training, testing and the validation data for the noisy case of Example 1
are plotted in Figure 6.6. Numerical results for this case are listed in
Tables III and IV, and the corresponding figures are plotted in Figures 6.7
and 6.8.

Figure 6.6: Example 1 (noisy case): The training, testing and the validation data. Table III: Example 1 (noisy case): Training time and accuracy for each grade. grade | learning rate | epochs | training time | mse (train) | rse (train)
---|---|---|---|---|---
1 | $0.1$ | $5$ | $4.3172$ | $4.3381\times 10^{-2}$ | $8.6013\times 10^{-2}$
2 | $0.01$ | $20$ | $13.9507$ | $2.5290\times 10^{-3}$ | $5.0143\times 10^{-2}$
3 | $0.01$ | $40$ | $29.8275$ | $2.4058\times 10^{-3}$ | $4.7701\times 10^{-2}$
Table IV: Example 1 (noisy case): multi-grade vs single-grade. method | training time | mse (train) | rse (train) | mse (test) | rse (test)
---|---|---|---|---|---
multi-grade | 48.0953 | $2.4058\times 10^{-3}$ | $4.7701\times 10^{-3}$ | $1.1476\times 10^{-4}$ | $2.2869\times 10^{-4}$
single-grade | 474.8579 | $3.1994\times 10^{-1}$ | $6.3436\times 10^{-1}$ | $3.1720\times 10^{-1}$ | $6.3213\times 10^{-1}$
|
---|---
|
Figure 6.7: Example 1 (noisy case): Loss curves during training. (a)-(c)
multi-grade; (d) single-grade.

|
---|---

---

Figure 6.8: Example 1 (noisy case): Predictions on the testing set. (a) after
each grade of multi-grade; (b) multi-grade; (c) single-grade.

Example 2: We consider approximating the oscillatory function with a variable
magnitude

$f(x):=x\mathrm{sin}(100x),\ \ x\in[a,b]:=[0,1].$

Figure 6.9: Example 2 (noise free): The training, testing and validation data.

For this example, we use a three grade model:

$\displaystyle\mbox{Grade 1}:\ [1]\to[256]\to[256]\to[1],$
$\displaystyle\mbox{Grade 2}:\
[1]\to[256]_{\mbox{F}}\to[256]_{\mbox{F}}\to[128]\to[64]\to[64]\to[1],$
$\displaystyle\mbox{Grade 3}:\
[1]\to[256]_{\mbox{F}}\to[256]_{\mbox{F}}\to[128]_{\mbox{F}}\to[64]_{\mbox{F}}\to[64]_{\mbox{F}}\to[64]\to[32]\to[32]\to[1].$

The activation function for hidden layers in the first grade is the $\sin$
function and the activation function for the rest of hidden layers is the ReLU
function. No activation function is applied to the last layer of each grade.
The corresponding classic architecture is given by

$[1]\to[256]\to[256]\to[128]\to[64]\to[64]\to[64]\to[32]\to[32]\to[1],$

in which the activation function for the first two hidden layers is the
$\mathrm{sin}$ function and the activation for the rest of hidden layers is
the ReLU function. No activation is applied to the last layer. The single-
grade network is trained with Adam: learning rate $0.01$ with decay $1.0\times
10^{-2}$ and batch size $32$ for $800$ epochs.

For the noise free case of Example 2, the training, testing and the validation
data are plotted in Figure 6.9. Numerical results for this case are listed in
Tables V and VI, and the corresponding figures are plotted in Figures 6.10 and
6.11.

Table V: Example 2 (noise free): Training time and accuracy for each grade. grade | learning rate | epochs | training time | mse (train) | rse (train)
---|---|---|---|---|---
1 | $0.1$ | $5$ | $4.7529$ | $3.1325\times 10^{-2}$ | $1.8554\times 10^{-1}$
2 | $0.01$ | $20$ | $15.1325$ | $1.1796\times 10^{-5}$ | $6.9869\times 10^{-5}$
3 | $0.01$ | $40$ | $39.5186$ | $3.8516\times 10^{-6}$ | $2.2813\times 10^{-5}$
Table VI: Example 2 (noise free): multi-grade vs single-grade. method | training time | mse (train) | rse (train) | mse (test) | rse (test)
---|---|---|---|---|---
multi-grade | 59.4039 | $3.8516\times 10^{-6}$ | $2.2813\times 10^{-5}$ | $3.9175\times 10^{-6}$ | $2.3210\times 10^{-5}$
single-grade | 734.3698 | $7.7438\times 10^{-3}$ | $4.5867\times 10^{-2}$ | $7.7376\times 10^{-3}$ | $4.5842\times 10^{-2}$
|
---|---
|
Figure 6.10: Example 2 (noise free) - Loss curves during training: (a)-(c)
multi-grade; (d) single-grade.

|
---|---

---

Figure 6.11: Example 2 (noise free) - Predictions on the testing set: (a)
after each grade of multi-grade; (b) multi-grade; (c) single-grade.

For the noisy case of Example 2, the training, testing and the validation data
are plotted in Figure 6.12. Numerical results for this case are listed in
Tables VII and VIII, and the corresponding figures are plotted in Figures 6.13
and 6.14.

Figure 6.12: Example 2 (noisy case): The training, testing and validation data. Table VII: Example 2 (noisy case): Training time and accuracy for each grade. grade | learning rate | epochs | training time | mse (train) | rse (train)
---|---|---|---|---|---
1 | $0.1$ | $5$ | $2.9456$ | $9.4412\times 10^{-3}$ | $5.5099\times 10^{-2}$
2 | $0.01$ | $20$ | $10.7950$ | $2.5191\times 10^{-3}$ | $1.4701\times 10^{-2}$
3 | $0.01$ | $40$ | $24.0130$ | $2.4562\times 10^{-3}$ | $1.4334\times 10^{-2}$
Table VIII: Example 2 (noisy case): multi-grade vs single-grade. method | training time | mse (train) | rse (train) | mse (test) | rse (test)
---|---|---|---|---|---
multi-grade | 37.7535 | $2.4562\times 10^{-3}$ | $1.4334\times 10^{-2}$ | $9.8123\times 10^{-5}$ | $5.8133\times 10^{-4}$
single-grade | 684.0808 | $1.3066\times 10^{-2}$ | $7.6253\times 10^{-2}$ | $1.0483\times 10^{-2}$ | $6.2108\times 10^{-2}$
|
---|---
|
Figure 6.13: Example 2 - Loss curves during training: (a)-(c) multi-grade; (d)
single-grade.

|
---|---

---

Figure 6.14: Example 2 - Predictions on the testing set: (a) after each grade
of multi-grade; (b) multi-grade; (c) single-grade.

Example 3: In this example, we consider a non-differentiable function

$f(x):=(x+1)(f_{4}\circ f_{3}\circ f_{2}\circ f_{1})(x),\ x\in[a,b]:=[-1,1],$
(6.5)

where $(f\circ g)(x)$ means the composition $f(g(x))$ assuming the image of
$g$ lies in the domain of $f$, and $f_{k}$’s are given by

$\displaystyle f_{1}(x):=|\mathrm{cos}(\pi(x-0.3))-0.7|,$ $\displaystyle
f_{2}(x):=|\mathrm{cos}(2\pi(x-0.5))-0.5|,$ $\displaystyle
f_{3}(x):=-|x-1.3|+1.3,$ $\displaystyle f_{4}(x):=-|x-0.9|+0.9.$

Figure 6.15: Example 3 (noise free): The training, testing and the validation
data.

For this example, we use the following three grades:

$\displaystyle\mbox{Grade 1}:\ [1]\to[128]\to[128]\to[1],$
$\displaystyle\mbox{Grade 2}:\
[1]\to[128]_{\mbox{F}}\to[128]_{\mbox{F}}\to[64]\to[64]\to[64]\to[1],$
$\displaystyle\mbox{Grade 4}:\
[1]\to[128]_{\mbox{F}}\to[128]_{\mbox{F}}\to[64]_{\mbox{F}}\to[64]_{\mbox{F}}\to[64]_{\mbox{F}}\to[32]\to[32]\to[32]\to[1].$

The activation function for hidden layers in the first grade is the $\sin$
function and the activation function for the rest of hidden layers is the ReLU
function. No activation function is applied to the last layer of each grade.
The corresponding classic architecture is given by

$[1]\to[128]\to[128]\to[64]\to[64]\to[64]\to[32]\to[32]\to[32]\to[1],$

in which the activation function for the first two hidden layers is the $\sin$
function and the activation for the rest of hidden layers is the ReLU
function. No activation is applied to the last layer. The single-grade network
is trained with Adam: learning rate $0.01$ with decay $1.0\times 10^{-2}$ and
batch size $32$ for $500$ epochs.

For the noise free case of Example 3, the training, testing and the validation
data are plotted in Figure 6.15. Numerical results for this case are listed in
Tables IX and X. The corresponding figures are plotted in Figures 6.16 and
6.17.

Table IX: Example 3 (noise free): Training time and accuracy for each grade. grade | learning rate | epochs | training time | mse (train) | rse (train)
---|---|---|---|---|---
1 | $0.1$ | $5$ | $3.9165$ | $2.9048\times 10^{-3}$ | $6.9275\times 10^{-3}$
2 | $0.01$ | $10$ | $6.7180$ | $8.8397\times 10^{-6}$ | $2.1081\times 10^{-5}$
3 | $0.01$ | $40$ | $26.5470$ | $2.8498\times 10^{-6}$ | $6.7963\times 10^{-6}$
Table X: Example 3 (noise free): multi-grade vs single-grade. method | training time | mse (train) | rse (train) | mse (test) | rse (test)
---|---|---|---|---|---
multi-grade | 37.1816 | $2.8498\times 10^{-6}$ | $6.7963\times 10^{-6}$ | $3.0007\times 10^{-6}$ | $7.1605\times 10^{-6}$
single-grade | 377.6011 | $1.3259\times 10^{-2}$ | $3.1620\times 10^{-2}$ | $1.3243\times 10^{-2}$ | $3.1602\times 10^{-2}$
|
---|---
|
Figure 6.16: Example 3 (noise free) - Loss curves during training: (a)-(c)
multi-grade; (d) single-grade.

|
---|---

---

Figure 6.17: Example 3 (noise free) - Predictions on the testing set: (a)
after each grade of multi-grade; (b) multi-grade; (c) single-gade.

The training, testing and the validation data for the noisy case of Example 3
are plotted in Figure 6.18. Numerical results for this case are listed in
Tables XI and XII, and the corresponding figures are plotted in Figures 6.19
and 6.20.

Figure 6.18: Example 3 (noisy case): The training, testing and the validation data.  Table XI: Example 3 (noisy case): Training time and accuracy for each grade. grade | learning rate | epochs | training time | mse (train) | rse (train)
---|---|---|---|---|---
1 | $0.1$ | $5$ | $4.0153$ | $2.8773\times 10^{-2}$ | $6.8177\times 10^{-2}$
2 | $0.01$ | $10$ | $6.8856$ | $2.6177\times 10^{-3}$ | $6.2027\times 10^{-3}$
3 | $0.01$ | $25$ | $16.3114$ | $2.5108\times 10^{-3}$ | $5.9495\times 10^{-3}$
Table XII: Example 3 (noisy case): multi-grade vs single-grade. method | training time | mse (train) | rse (train) | mse (test) | rse (test)
---|---|---|---|---|---
multi-grade | 27.2122 | $2.5108\times 10^{-3}$ | $5.9495\times 10^{-3}$ | $1.5818\times 10^{-4}$ | $3.7746\times 10^{-4}$
single-grade | 406.6714 | $1.8728\times 10^{-2}$ | $4.4376\times 10^{-2}$ | $1.6499\times 10^{-2}$ | $3.9372\times 10^{-2}$
|
---|---
|
Figure 6.19: Example 3 (noisy case) - Loss curves during training: (a)-(c)
multi-grade; (d) single-grade.

|
---|---

---

Figure 6.20: Example 3 (noisy case) - Predictions on the testing set: (a)
after each grade of multi-grade; (b) multi-grade; (c) single-grade.

We observe from the numerical results presented in this section that for all
examples (for both noise free and noisy cases) the multi-grade model
outperforms significantly the single-grade model in terms of training time,
training accuracy and prediction accuracy in all counts. Moreover, multi-grade
models are much easier to train than their corresponding single-grade models.

##  7 Conclusive Remarks

To address computational challenges in learning deep neural networks, we have
proposed multi-grade learning models, inspired by the human education process
which arranges learning in grades. Unlike the deep neural network learned from
the standard single-grade model, the neural network learned from a multi-grade
model is the superposition of the neural networks, in a stair-shape, each of
which is learned from one grade of the learning. We have proved that for
function approximation if the neural network generated by a new grade is
nontrivial, the optimal error of the grade is strictly reduced from the
optimal error of the previous grade. Three proof-of-concept numerical examples
presented in the paper demonstrate that the proposed the multi-grade deep
learning model outperforms significantly the single-grade deep learning model
in all aspects, including training time, training accuracy and prediction
accuracy. Our computational experiences show that the multi-grade model is
much easier to train than the corresponding single-grade model. We conclude
that the proposed multi-grade model is much more robust than the traditional
single-grade model.

Acknowledgement: The author is indebted to graduate student Mr. Lei Huang for
his assistance in preparation of the numerical examples presented in section 6
and to Dr. Tingting Wu for helpful discussion of issues related to
approximation of the oscillatory function. The author of this paper is
supported in part by US National Science Foundation under grants DMS-1912958
and DMS-2208386, and by the US National Institutes of Health under grant
R21CA263876.

## References

  * Y. Bengio, P. Lamblin, D. Popovici, and H. Larochelle, Greedy layer-wise training of deep networks, in “Advances in Neural Information Processing Systems,” 2007, pp. 153–160.
  * [1] L. Bottou, Online algorithms and stochastic approximations, in “Online Learning and Neural Networks”, Cambridge University Press, 1998. ISBN 978-0-521-65263-6.
  * [2] L. Bottou and O. Bousquet, The tradeoffs of large scale learning, in “Optimization for Machine Learning”, S. Sra, S. Nowozin, S. J. Wright, (eds.), MIT Press, Cambridge, 2012, pp. 351–368.
  * [3] J. Brownlee, Probability for machine learning: Discover how to harness uncertainty with Python, Machine Learning Mastery, 2019.
  * [4] Q. Chen, N. Huang, S. Riemenschneider and Y. Xu, A B-spline approach for empirical mode decompositions, Advances in Computational Mathematics 24 (1-4) (2006), 171-195
  * [5] Z. Chen, C. A. Micchelli and Y. Xu, A construction of interpolating wavelets on invariant sets, Mathematics of Computation 68 (228) (1999), 1569-1587.
  * [6] Z. Chen, C. A. Micchelli and Y. Xu, Multiscale Methods for Fredholm Integral Equations, Cambridge University Press, New York, 2015.
  * [7] Z. Chen, B. Wu and Y. Xu, Fast multilevel augmentation methods for solving Hammerstein equations, SIAM Journal on Numerical Analysis 47 (3) (2009), 2321-2346.
  * [8] I. Daubechies, Ten Lectures on Wavelets, SIAM, Philadelphia, 1992.
  * [9] I. Daubechies, R. DeVore, S. Foucart, B. Hanin, and G. Petrova, Nonlinear approximation and (deep) ReLU networks, Constructive Approximation 55 (2022), 127–172.
  * [10] F. Deutsch, Best Approximation in Inner Product Spaces, Springer-Verlag, New York, 2001.
  * [11] I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning, MIT Press, Cambridge, 2016.
  * [12] I. Häggström, C. R. Schmidtlein, G. Campanella, T. J. Fuchs, DeepPET: A deep encoder–decoder network for directly solving the PET image reconstruction inverse problem, Medical Image Analysis 54 (2019) 253-262.
  * [13] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd Edition, Cambridge University Press, New York, 2012.
  * [14] N. E. Huang, Z. Shen, S. R. Long, M. C. Wu, H. H. Shih, Q. Zheng, N.-C. Yen, C. C. Tung, H. H. Liu, The empirical mode decomposition and the Hilbert spectrum for nonlinear and non-stationary time series analysis, Proc. Roy. Soc. London A 454 (1998), 903-995.
  * [15] D. P. Kingma and J. L. Ba, ADAM: A method for stochastic optimization, Published as a conference paper at ICLR 2015.
  * [16] A. Krizhevsky, I. Sutskever, and G. Hinton, ImageNet classification with deep convolutional neural networks, Neural Information Processing Systems (NIPS), Lake Tahoe, Nevada, 2012.
  * [17] Y. LeCun, Y. Bengio, and G. Hinton, Deep learning, Nature 521 (2015), no. 7553, 436–444, 2015.
  * [18] Q. Liu, R. Wang, Y. Xu and M. Yan, Parameter choices for sparse regularization with the $\ell_{1}$ norm, Inverse Problems 39 (2023) 025004 (34pp)
  * [19] C. A. Micchelli and Y. Xu, Using the matrix refinement equation for the construction of wavelets on invariant sets, Applied and Computational Harmonic Analysis 1 (4) (1994), 391-401.
  * [20] M. Raissi, Deep hidden physics models: Deep learning of nonlinear partial differential equations, Journal of Machine Learning Research 19 (2018) 1-24.
  * [21] L. Rice, E. Wong, and J. Z. Kolter, Overfitting in adversarially robust deep learning, in “Proceedings of the 37 th International Conference on Machine Learning,” Vienna, Austria, PMLR 119, 2020.
  * [22] D. Shen, G. Wu, and H. Suk, Deep learning in medical image analysis, Annu Rev Biomed Eng. 19 (2017) 221-248.
  * [23] Z. Shen, H. Yang, and S. Zhang, Deep network with approximation error being reciprocal of width to power of square root of depth, Neural Comput. 33 (2021), no. 4, 1005–1036.
  * [24] G. Torlai, G. Mazzola, J. Carrasquilla, M. Troyer, R. Melko, G. Carleo, Neural-network quantum state tomography, Nature Physics 14 (5) (2018), 447–450.
  * [25] W. Wu, G. Feng, Z. Li, and Y. Xu, Deterministic convergence of an online gradient method for BP neural networks, IEEE Transactions on Neural Networks 16 (3) (2005), 533-540.
  * [26] W. Wu and Y. Xu, Deterministic convergence of an online gradient method for neural networks, Journal of Computational and Applied Mathematics 144 (1-2) (2002), 335-347.
  * [27] Y. Xu, B. Liu, J. Liu, and S. Riemenschneider, Two-dimensional empirical mode decomposition by finite elements, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 462 (2006), 3081-3096.
  * [28] Y. Xu and T. Zeng, Sparse deep neural network for nonlinear partial differential equations, Numer. Math. Theor. Meth. Appl. 16 (2023), 58-78.
  * [29] Y. Xu and H. Zhang, Convergence of deep ReLU networks, arXiv preprint arXiv:2107.12530.
  * [30] Y. Xu and H. Zhang, Convergence of deep convolutional neural networks, Neural Networks, 153 (2022), 553–563.