# Does generalization performance of $l^{q}$ regularization learning depend on
$q$? A negative example ††thanks: The research was supported by the National
973 Programming (2013CB329404), the Key Program of National Natural Science
Foundation of China (Grant No. 11131006), and the National Natural Science
Foundations of China (Grants No. 61075054).

Shaobo Lin1 Chen Xu2 Jinshan Zeng1 Jian Fang1

###### Abstract

$l^{q}$-regularization has been demonstrated to be an attractive technique in
machine learning and statistical modeling. It attempts to improve the
generalization (prediction) capability of a machine (model) through
appropriately shrinking its coefficients. The shape of a $l^{q}$ estimator
differs in varying choices of the regularization order $q$. In particular,
$l^{1}$ leads to the LASSO estimate, while $l^{2}$ corresponds to the smooth
ridge regression. This makes the order $q$ a potential tuning parameter in
applications. To facilitate the use of $l^{q}$-regularization, we intend to
seek for a modeling strategy where an elaborative selection on $q$ is
avoidable. In this spirit, we place our investigation within a general
framework of $l^{q}$-regularized kernel learning under a sample dependent
hypothesis space (SDHS). For a designated class of kernel functions, we show
that all $l^{q}$ estimators for $0<q<\infty$ attain similar generalization
error bounds. These estimated bounds are almost optimal in the sense that up
to a logarithmic factor, the upper and lower bounds are asymptotically
identical. This finding tentatively reveals that, in some modeling contexts,
the choice of $q$ might not have a strong impact in terms of the
generalization capability. From this perspective, $q$ can be arbitrarily
specified, or specified merely by other no generalization criteria like
smoothness, computational complexity, sparsity, etc..

Keywords: Learning theory, $l^{q}$ regularization learning, sample dependent
hypothesis space, learning rate
MSC 2000: 68T05, 62G07.

1\. Institute for Information and System Sciences, School of Mathematics and
Statistics, Xi’an Jiaotong University Xi’an 710049, P R China

2\. The Methodology Center, The Pennsylvania State University, Department of
Statistics, 204 E. Calder Way, Suite 400, State College, PA 16801, USA

##  1 Introduction

Contemporary scientific investigations frequently encounter a common issue of
exploring the relationship between a response and a number of covariates. In
machine learning research, the subject is typically addressed through learning
a underling rule from the data that accurately predicates future values of the
response. For instance, in banking industry, financial analysts are interested
in building a system that helps to judge the risk of a loan request. Such a
system is often trained based on the risk assessments from previous loan
applications together with the empirical experiences. An incoming loan request
is then viewed as a new input, upon which the corresponding potential risk
(response) is to be predicted. In such applications, the predictive accuracy
of a trained rule is of the key importance.

In the past decade, various strategies have been developed to improve the
prediction (generalization) capability of a learning process, which include
$l^{q}$ regularization as an well-known example [33]. The $l^{q}$
regularization learning prevents over-fitting by shrinking the model
coefficients and thereby attains a higher predictive value. To be specific,
suppose that the data ${\bf z}=\\{x_{i},y_{i}\\}$ for $i=1,\ldots,m$ are
collected independently and identically according to an unknown but definite
distribution, where $y_{i}$ is a response of $i$th unit and $x_{i}$ is the
corresponding $d$-dimensional covariates. Let

$\mathcal{H}_{K,{\bf
z}}:=\left\\{\sum_{i=1}^{m}a_{i}K_{x_{i}}:a_{i}\in\mathbf{R}\right\\}$

be a sample dependent space (SDHS) with $K_{t}(\cdot)=K(\cdot,t)$ and
$K(\cdot,\cdot)$ being a positive definite kernel function. The coefficient-
based $l^{q}$ regularization strategy ($l^{q}$ regularizer) takes the form of

$f_{{\bf z},\lambda,q}=\arg\min_{f\in\mathcal{H}_{K,{\bf
z}}}\left\\{\frac{1}{m}\sum_{i=1}^{m}(f(x_{i})-y_{i})^{2}+\lambda\Omega^{q}_{\bf
z}(f)\right\\},$ (1)

where $\lambda=\lambda(m,q)>0$ is a regularization parameter and $\Omega_{\bf
z}^{q}(f)$ $(0<q<\infty)$ is defined by

$\Omega^{q}_{\bf z}(f)=\sum_{i=1}^{m}|a_{i}|^{q}\ \mbox{when}\
f=\sum_{i=1}^{m}a_{i}K_{x_{i}}\in\mathcal{H}_{K,{\bf z}}.$

With different choices of order $q$, (1) leads to various specific forms of
the $l_{q}$ regularizer. In particular, when $q=2$, $f_{{\bf z},\lambda,q}$
corresponds to the ridge regressor [23], which smoothly shrinks the
coefficients toward zero. When $q=1$, $f_{{\bf z},\lambda,q}$ leads to the
LASSO [29], which set small coefficients exactly at zero and thereby also
serves as a variable selection operator. When $0<q<1$, $f_{{\bf z},\lambda,q}$
coincides with the bridge estimator [8], which tends to produce highly sparse
estimates through a non-continuous shrinkage.

The varying forms and properties of $f_{{\bf z},\lambda,q}$ make the choice of
order $q$ crucial in applications. Apparently, an optimal $q$ may depend on
many factors such as the learning algorithms, the purposes of studies and so
forth. These factors make a simple answer to this question infeasible in
general. To facilitate the use of $l^{q}$-regularization, alteratively, we
intend to seek for a modeling strategy where an elaborative selection on $q$
is avoidable. Specifically, we attempt to reveal some insights for the role of
$q$ in $l^{q}$-learning via answering the following question:

Problem 1. Are there any kernels such that the generalization capability of
(1) is independent of $q$?

In this paper, we provides a positive answer to Problem 1 under the framework
of statistical learning theory. Specifically, we provide a featured class of
positive definite kernels, under which the $l_{q}$ estimators for $0<q<\infty$
attain similar generalization error bounds. We then show that these estimated
bounds are almost essential in the sense that up to a logarithmic factor the
upper and lower bounds are asymptotically identical. In the proposed modeling
context, the choice of $q$ does not have a strong impact in terms of the
generalization capability. From this perspective, $q$ can be arbitrarily
specified, or specified merely by other no generalization criteria like
smoothness, computational complexity, sparsity, etc..

The reminder of the paper is organized as follows. In Section 2, we provide a
literature review and explain our motivation of the research. In Section 3, we
present some preliminaries including spherical harmonics, Gegenbauer
polynomials and so on. In Section 4, we introduce a class of well-localized
needlet type kernels of Petrushev and Xu [22] and show some crucial properties
of them which will play important roles in our analysis. In Section 5, we then
study the generalization capabilities of $l^{q}$-regularizer associated with
the constructed kernels for different $q$. In Section 6, we provide the proof
of the main results. We conclude the paper with some useful remarks in the
last section.

##  2 Motivation and related work

###  2.1 Motivation

In practice, the choice of $q$ in (1) is critical, since it embodies certain
potential attributions of the anticipated solutions such as sparsity,
smoothness, computational complexity, memory requirement and generalization
capability of course. The following simple simulation illustrates that
different choice of $q$ can lead to different sparsity of the solutions.

The samples are identically and independently drawn according to the uniform
distribution from the two dimensional Sinc function pulsing a Gaussian noise
$N(0,\delta^{2})$ with $\delta^{2}=0.1$. There are totally 256 training
samples and 256 test samples. In Fig. 1, we show that different choice of $q$
may deduce different sparsity of the estimator for the kernel
$K_{0.1}(x):=\exp\left\\{-\|x-y\|^{2}/0.1\right\\}$. It can be found that
$l^{q}$ $(0<q\leq 1)$ regularizers can deduce sparse estimator, while it
impossible for $l^{2}$ regularizer.

Figure 1: Sparsity for $l^{q}$ learning schemes

Therefore, for a given learning task, how to choose $q$ is an important and
crucial problem for $l^{q}$ regularization learning. In other words, which
standards should be adopted to measure the quality of $l^{q}$ regularizers
deserves study. As the most important standard of statistical learning theory,
the generalization capability of $l^{q}$ regularization scheme (1) may depend
on the choice of kernel, the size of samples $m$, the regularization parameter
$\lambda$, the behavior of priors, and, of course, the choice of $q$. If we
take the generalization capability of $l^{q}$ regularization learning as a
function of $q$, we then automatically wonder how this function behaves when
$q$ changes for a fixed kernel. If the generalization capabilities depends
heavily on $q$, then it is natural to choose the $q$ such that the
generalization capability of the corresponding $l^{q}$ regularizer is the
smallest. If the generalization capabilities is independent of $q$, then $q$
can be arbitrarily specified, or specified merely by other no generalization
criteria like smoothness, computational complexity, sparsity.

However, the relation between the generalization capability and $q$ depends
heavily on the kernel selection. To show this, we compare the generalization
capabilities of $l^{2}$, $l^{1}$, $l^{1/2}$ and $l^{2/3}$ regularization
schemes for two kernels: $\exp\left\\{-\|x-y\|^{2}/0.1\right\\}$ and
$\exp\left\\{-\|x-y\|/10\right\\}$ in the simulation. The one case shows that
the generalization capabilities of $l^{q}$ regularization schemes may be
independent of $q$ and the other case shows that the generalization capability
of (1) depends heavily on $q$. In the left of Fig. 2, we report the relation
between the test error and regularization parameter for the kernel
$\exp\left\\{-\|x-y\|^{2}/0.1\right\\}$. It is shown that when the
regularization parameters are appropriately tuned, all of the aforementioned
regularization schemes may possess the similar generalization capabilities. In
the right of Fig. 2, for the kernel $\exp\left\\{-\|x-y\|/10\right\\}$, we see
that the generalization capability of $l^{q}$ regularization depends heavily
on the choice of $q$.

Figure 2: Comparisons of test error for $l^{q}$ regularization schemes with
different $q$.

From these simulations, we see that finding kernels such that the
generalization capability of (1) is independent of $q$ is of special
importance in theoretical and practical applications. In particular, if such
kernels exist, with such kernels, $q$ can be solely chosen on the basis of
algorithmic and practical considerations for $l^{q}$ regularization. Here we
emphasize that all these conclusions can, of course only be made in the
premise that the obtained generalization capabilities of all $l^{q}$
regularizers are (almost) optimal.

###  2.2 related work

There have been several papers that focus on the generalization capability
analysis of the $l^{q}$ regularization scheme (1). Wu and Zhou [33] were the
first, to the best of our knowledge, to show a mathematical foundation of
learning algorithms in SDHS. They claimed that the data dependent nature of
the algorithm leads to an extra error term called hypothesis error, which is
essentially different form regularization schemes with sample independent
hypothesis spaces (SIHSs). Based on this, the authors proposed a coefficient-
based regularization strategy and conducted a theoretical analysis of the
strategy by dividing the generalization error into approximation error, sample
error and hypothesis error. Following their work, Xiao and Zhou [34] derived a
learning rate of $l^{1}$ regularizer via bounding the regularization error,
sample error and hypothesis error, respectively. Their result was improved in
[24] by adopting a concentration inequality technique with $l^{2}$ empirical
covering numbers to tackle the sample error. On the other hand, for $l^{q}$
$(1\leq q\leq 2)$ regularizers, Tong et al. [30] deduced an upper bound for
generalization error by using a different method to cope with the hypothesis
error. Later, the learning rate of [30] was improved further in [11] by giving
a sharper estimation of the sample error.

In all those researches, some sharp restrictions on the probability
distributions (priors) have been imposed, say, both spectrum assumption of the
regression function and concentration property of the marginal distribution
should be satisfied. Noting this, for $l^{2}$ regularizer, Sun and Wu [28]
conducted a generalization capability analysis for $l^{2}$ regularizer by
using the spectrum assumption to the regression function only. For $l^{1}$
regularizer, by using a sophisticated functional analysis method, Zhang et al.
[36] and Song et al. [25] built the regularized least square algorithm on the
reproducing kernel Banach space (RKBS), and they proved that the regularized
least square algorithm in RKBS is equivalent to $l^{1}$ regularizer if the
kernel satisfies some restricted conditions. Following this method, Song and
Zhang [26] deduced a similar learning rate for the $l^{1}$ regularizer and
eliminated the concentration property assumption on the marginal distribution
.

Limiting $q$ within $[1,2]$ is certainly incomplete to judge whether the
generalization capability of $l^{q}$ regularization depends on the choice of
$q$. Moreover, in the context of learning theory, to intrinsically
characterize the generalization capability of a learning strategy, the
essential generalization bound [10] rather than the upper bound is required,
that is, we must deduce a lower and an upper bound simultaneously for the
learning strategy and prove that the upper and lower bounds can be
asymptotically identical. We notice, however, that most of the previously
known estimations on generalization capability of learning schemes (1) are
only concerned with the upper bound estimation. Thus, their results can not
serve the answer to Problem 1. Different from the pervious work, the essential
bound estimation of generalization error for $l^{q}$ regularization schemes
(1) with $0<q<\infty$ will be presented in the present paper. As a
consequence, we provide an affirmative answer to Problem 1.

##  3 Preliminaries

In this section, we introduce some preliminaries on spherical harmonics,
Gegenbauer polynomial and orthonormal basis construction., which will be used
in the construction of the positive definite needlet kernel.

###  3.1 Gegenbauer polynomial

The Gegenbauer polynomials are defined by the generating function [31]

$(1-2tz+z^{2})^{-\mu}=\sum_{n=0}^{\infty}G_{n}^{\mu}(t)z^{n},$

where $|z|<1,|t|\leq 1,$ and $\mu>0$. The coefficients $G_{n}^{\mu}(t)$ are
algebraic polynomials of degree $n$ which are called the Gegenbauer
polynomials associated with $\mu$. It is known that the family of polynomials
$\\{G_{n}^{\mu}\\}_{n=0}^{\infty}$ is a complete orthogonal system in the
weighted space $L^{2}(I,w)$, $I:=[-1,1]$,
$w_{\mu}(t):=(1-t^{2})^{\mu-\frac{1}{2}}$ and there holds

$\int_{I}G_{m}^{\mu}(t)G_{n}^{\mu}(t)w_{\mu}(t)dt=\left\\{\begin{array}[]{cc}0,&m\neq
n\\\ h_{n,\mu},&m=n\end{array}\right.\ \mbox{with}\
h_{n,\mu}=\frac{\pi^{1/2}(2\mu)_{n}\Gamma(\mu+\frac{1}{2})}{(n+\mu)n!\Gamma(\mu)},$

where

$(a)_{0}:=0,(a)_{n}:=a(a+1)\dots(a+n-1)=\frac{\Gamma(a+n)}{\Gamma(a)}.$

Define

$U_{n}:=(h_{n,d/2})^{-1/2}G_{n}^{d/2},\ n=0,1,\dots.$ (2)

Then it is easy to see that $\\{U_{n}\\}_{n=0}^{\infty}$ is a complete
orthonormal system for the weighted $L^{2}$ space $L^{2}(I,w)$, where
$w(t):=(1-t^{2})^{\frac{d-1}{2}}$. Let $\mathbf{B}^{d}$ be the unit ball in
$\mathbf{R}^{d}$, $\mathbf{S}^{d-1}$ be the unit sphere in $\mathbf{R}^{d}$
and $\mathcal{P}_{n}$ be the set of algebraic polynomials of degree not larger
than $n$ defined on $\mathbf{B}^{d}$. Denote by $d\omega_{d-1}$ the aero
element of $\mathbf{S}^{d-1}$. Then
$\Omega_{d-1}:=\int_{\mathbf{S}^{d-1}}d\omega_{d-1}=\frac{2\pi^{\frac{d}{2}}}{\Gamma(\frac{d}{2})}.$
The following important properties of $U_{n}$ are established in [21].

######  Lemma 1.

Let $U_{n}$ be defined as above. Then for each $\xi,\eta\in\mathbf{S}^{d-1}$
we have

$\int_{\mathbf{B}^{d}}U_{n}(\xi\cdot x)P(x)dx=0\ \mbox{for}\
P\in\mathcal{P}_{n-1},$ (3) $\int_{\mathbf{B}^{d}}U_{n}(\xi\cdot
x)U_{n}(\eta\cdot x)dx=\frac{U_{n}(\xi\cdot\eta)}{U_{n}(1)},$ (4)
$K_{n}^{*}+K_{n-2}^{*}+\dots+K_{\varepsilon_{n}}^{*}=\frac{v_{n}^{2}}{U_{n}(1)}U_{n},$
(5)

and

$\int_{\mathbf{S}^{d-1}}U_{n}(\xi\cdot
x)U_{n}(\xi\cdot\eta)d\omega_{d-1}(\xi)=\frac{U_{n}(1)}{v_{n}^{2}}U_{n}(\eta\cdot
x),$ (6)

where $v_{n}:=\left(\frac{(n+1)_{d-1}}{2(2\pi)^{d-1}}\right)^{\frac{1}{2}}$,
and
$K_{n}^{*}:=\frac{2k+d-2}{(d-2)\Omega_{d-1}}G_{k}^{\frac{d-2}{2}}(\xi\cdot\eta)$.

###  3.2 Spherical harmonics

For any integer $k\geq 0$, the restriction to $\mathbf{S}^{d-1}$ of a
homogeneous harmonic polynomial with degree $k$ is called a spherical harmonic
of degree $k$. The class of all spherical harmonics with degree $k$ is denoted
by $\mathbf{H}^{d-1}_{k}$, and the class of all spherical polynomials with
total degrees $k\leq n$ is denoted by $\Pi_{n}^{d-1}$. It is obvious that
$\Pi_{n}^{d-1}=\bigoplus_{k=0}^{n}\mathbf{H}^{d-1}_{k}$. The dimension of
$\mathbf{H}^{d-1}_{k}$ is given by

$D_{k}^{d-1}:=\mbox{dim
}\mathbf{H}^{d-1}_{k}:=\left\\{\begin{array}[]{ll}\frac{2k+d-2}{k+d-2}{{k+d-2}\choose{k}},&k\geq
1;\\\ 1,&k=0,\end{array}\right.$

and that of $\Pi_{n}^{d-1}$ is $\sum_{k=0}^{n}D^{d-1}_{k}=D_{n}^{d}\sim
n^{d-1},$ where $A\sim B$ denotes that there exist absolute constants $C_{1}$
and $C_{2}$ such that $C_{1}A\leq B\leq C_{2}A$.

The well known addition formula is given by (see [20] and [31])

$\sum_{l=1}^{D_{k}^{d-1}}Y_{k,l}(\xi)Y_{k,l}(\eta)=\frac{2k+d-2}{(d-2)\Omega_{d-1}}G_{k}^{\frac{d-2}{2}}(\xi\cdot\eta)=K_{n}^{*}(\xi\cdot\eta),$
(7)

where $\\{Y_{k,l}:l=1,\dots,D_{k}^{d-1}\\}$ is arbitrary orthonormal basis of
$\mathbf{H}_{k}^{d-1}$.

For $r>0$ and $a\geq 1$, we say that a finite subset
$\Lambda\subset\mathbf{S}^{d-1}$ is an $(r,a)$-covering of $\mathbf{S}^{d-1}$
if

$\mathbf{S}^{d-1}\subset\bigcup_{\xi\in\Lambda}D(\xi,r)\ \ \mbox{and}\ \
\max_{\xi\in\Lambda}\left|\Lambda\bigcap D(\xi,r)\right|\leq a,$

where $|A|$ denotes the cardinality of the set $A$ and
$D(\xi,r)\subset\mathbf{S}^{d-1}$ denotes the spherical cap with the center
$\xi$ and the angle $r$. The following positive cubature formula can be found
in [2].

######  Lemma 2.

There exists a constant $\gamma>0$ depending only on $d$ such that for any
positive integer $n$ and any $(\delta/n,a)$-covering of $\mathbf{S}^{d-1}$
satisfying $0<\delta<a^{-1}\gamma$. There exists a set of numbers
$\\{\eta_{\xi}\\}_{\xi\in\Lambda}$ such that

$\int_{\mathbf{S}^{d-1}}Q(\zeta)d\omega_{d-1}(\zeta)=\sum_{\xi\in\Lambda}\eta_{\zeta}Q(\zeta)\
\ \mbox{for}\ \mbox{any \ \ }Q\in\Pi_{4n}^{d-1}.$

###  3.3 Basis and reproducing kernel for $\mathcal{P}_{n}$

Define

$P_{k,j,i}(x)=v_{k}\int_{\mathbf{S}^{d-1}}Y_{j,i}(\xi)U_{k}(x\cdot\xi)d\omega(\xi).$
(8)

Then it follows from [15] (or [21]) that

$\\{P_{k,j,i}:k=0,\dots,n,j=k,k-2,\dots,\varepsilon_{k},i=1,2,\dots,D_{j}^{d-1}\\}$

consists an orthonormal basis for $\mathcal{P}_{n}$, where

$\varepsilon_{k}:=\left\\{\begin{array}[]{cc}0,&k\ \mbox{even},\\\ 1,&k\
\mbox{odd}\end{array}\right..$

Of course,

$\\{P_{k,j,i}:k=0,1,\dots,j=k,k-2,\dots,\varepsilon_{k},i=1,2,\dots,D_{j}^{d-1}\\}$

is an orthonormal basis for $L^{2}(\mathbf{B}^{d})$. The following Lemma 3
defines a reproducing kernel of $\mathcal{P}_{n}$, whose proof will be
presented in Appendix A.

######  Lemma 3.

The space
$(\mathcal{P}_{n},\langle\cdot,\cdot\rangle_{L^{2}(\mathbf{B}^{d})})$ is a
reproducing kernel Hilbert space. The unique reproducing kernel of this space
is

$K_{n}(x,y):=\sum_{k=0}^{n}v_{k}^{2}\int_{\mathbf{S}^{d-1}}U_{k}(\xi\cdot
x)U_{k}(\xi\cdot y)d\omega(\xi).$ (9)

##  4 The needlet kernel: Construction and Properties

In this section, we construct a concrete positive definite needlet kernel [22]
and show its properties. A function $\eta$ is said to be admissible if
$\eta\in C^{\infty}[0,\infty),$ $\eta(t)\geq 0$, and $\eta$ satisfies the
following condition [22]:

$\mbox{supp}\eta\subset[0,2],\eta(t)=1\ \mbox{on}\ [0,1],\ \mbox{and}\
0\leq\eta(t)\leq 1\ \mbox{on}\ [1,2].$

Such a function can be easily constructed out of an orthogonal wavelet mask
[7]. We define a kernel $L_{2n}(\cdot,\cdot)$ as the following

$L_{2n}(x,y):=\sum_{k=0}^{\infty}\eta\left(\frac{k}{n}\right)v_{k}^{2}\int_{\mathbf{S}^{d-1}}U_{k}(x\cdot\xi)U_{k}(y\cdot\xi)d\omega(\xi).$
(10)

As $\eta(\cdot)$ is admissible, the constructed kernel $L_{2n}(x,y),$ called
the needlet kernel (or localized polynomial kernel) [22] henceforth, is
positive definite. We will show that so defined kernel function $L_{2n}(x,y)$,
deduces the $l^{q}$ regularization learning whose learning rate is independent
of the choice of $q$. To this end, we first show several useful properties of
the needlet kernel.

The following Proposition 1 which can be deduced directly from Lemma 3 and the
definition of $\eta(\cdot)$ reveals that $L_{2n}$ possesses reproducing
property for $\mathcal{P}_{n}$.

######  Proposition 1.

Let $L_{2n}$ be defined as in (10). For arbitrary $P\in\mathcal{P}_{n}$, there
holds

$P(x)=\int_{\mathbf{B}^{d}}L_{2n}(x,y)P(y)dy.$ (11)

Since $\eta(\cdot)$ is an admissible function by definition, it follows that
$L_{2n}(x,\cdot)$ is an algebraic polynomial of degree not larger than $2n$
for any fixed $x\in\mathbf{B}^{d}$. At the first glance, as a polynomial
kernel, it may have good frequency localization property while have bad space
localization property. The following Proposition 2, which can be found in [22,
Theorem 4.2], however, advocates that $L_{2n}$ is actually a polynomial kernel
possessing very good spacial localized properties. This makes it widely
applicable in approximation theory and signal processing [12, 22].

######  Proposition 2.

Let $L_{2n}$ be defined as in (10). For arbitrary $l\in\mathbf{N}$, there
exists a constant $c_{l}$ depending only on $l$, $d$ and $\eta$ such that

$\max_{x,y\in\mathbf{B}^{d}}|L_{2n}(x,y)|\leq
c_{l}\frac{n^{d}}{(\sqrt{1-|x|^{2}}+n^{-1})(\sqrt{1-|y|^{2}}+n^{-1})(1+d(x,y))^{l}}.$
(12)

Let

$E_{n}(f)_{p}:=\inf_{P\in\mathcal{P}_{n}}\|f-P\|_{L^{p}(\mathbf{B}^{d})}$

be the best approximation error of $\mathcal{P}_{n}$. Define

$(\mathcal{L}_{2n}f)(x):=\int_{\mathbf{B}^{d}}L_{2n}(x,y)f(y)dy.$ (13)

It has been shown in [22, Remak 4.8] that the integral operator
$\mathcal{L}_{2n}f$ possesses the following compressive property:

######  Proposition 3.

If $\mathcal{L}_{2n}f$ is defined as in (13), then, for arbitrary $f\in
L^{p}(\mathbf{B}^{d})$, there exists a constant $C$ depending only on $d$ and
$p$ such that

$\|\mathcal{L}_{2n}f\|_{L^{p}(\mathbf{B}^{d})}\leq
C\|f\|_{L^{p}(\mathbf{B}^{d})}.$

By Propositions 1, 2 and 3, a standard method in approximation theory [9]
yields the following best approximation property of $\mathcal{L}_{2n}f$.

######  Proposition 4.

Let $1\leq p\leq\infty,$ and $\mathcal{L}_{2n}$ be defined in (13), then for
arbitrary $f\in L^{p}(\mathbf{B}^{d})$, there exists a constant $C$ depending
only on $d$ and $p$ such that

$\|f-\mathcal{L}_{2n}f\|_{L^{p}(\mathbf{B}^{d})}\leq CE_{n}(f)_{p}.$ (14)

##  5  Almost essential learning rate

In this section, we conduct a detailed generalization capability analysis of
the $l^{q}$ regularization scheme (1) when the kernel function $K$ is
specified as $L_{2n}(x,y)$. Our aim is to derive an almost essential learning
rate of $l^{q}$ regularization strategy (1). We first present a quick review
of learning theory. Then, we given the main result of this paper, where a
$q$-independent learning rate of $l^{q}$ regularization schemes (1) is
deduced. At last, we present some remarks on the main result.

###  5.1 Statistical learning theory

Let $X\subseteq\mathbf{B}^{d}$ be an input space and $Y\subseteq\mathbf{R}$ an
output space. Assume that there exists a unknown but definite relationship
between $x\in X$ and $y\in Y$, which is modeled by a probability distribution
$\rho$ on $Z:=X\times Y$. It is assumed that $\rho$ admits the decomposition

$\rho(x,y)=\rho_{X}(x)\rho(y|x).$

Let ${\bf z}=(x_{i},y_{i})_{i=1}^{m}$ be a set of finite random samples of
size $m$, $m\in\mathbf{N}$, drawn identically, independently according to
$\rho$ from $Z$. The set of examples ${\bf z}$ is called a training set.
Without loss of generality, we assume that $|y_{i}|\leq M$ almost everywhere.

The aim of learning is to learn from a training set a function $f:X\rightarrow
Y$ such that $f(x)$ is an effective estimate of $y$ when $x$ is given. One
natural measurement of the error incurred by using $f$ of this purpose is the
generalization error,

$\mathcal{E}(f):=\int_{Z}(f(x)-y)^{2}d\rho,$

which is minimized by the regression function [3, 4] defined by

$f_{\rho}(x):=\int_{Y}yd\rho(y|x).$

We do not know this ideal minimizer $f_{\rho}$, since $\rho$ is unknown, but
we have access to random examples from $X\times Y$ sampled according to
$\rho$.

Let $L^{2}_{\rho_{{}_{X}}}$ be the Hilbert space of $\rho_{X}$ square
integrable functions on $X$, with norm $\|\cdot\|_{\rho}.$ In the setting of
$f_{\rho}\in L^{2}_{\rho_{{}_{X}}}$, it is well known that, for every $f\in
L^{2}_{\rho_{X}}$, there holds

$\mathcal{E}(f)-\mathcal{E}(f_{\rho})=\|f-f_{\rho}\|^{2}_{\rho}.$ (15)

The goal of learning is then to construct a function $f_{\bf z}$ that
approximates $f_{\rho}$, in the norm $\|\cdot\|_{\rho}$, using the finite
sample ${\bf z}$.

One of the main points of this paper is to formulate the learning problem in
terms of probability estimates rather than expectation estimates. To this end,
we present a formal way to measure the performance of learning schemes in
probability. Let $\Theta\subset L_{\rho_{X}}^{2}$ and $\mathcal{M}(\Theta)$ be
the class of all Borel measures $\rho$ on $Z$ such that $f_{\rho}\in\Theta$.
For each $\varepsilon>0$, we enter into a competition over all estimators
established in the hypothesis space $\mathcal{H}$,
$\Psi_{m}:Z^{m}\rightarrow\mathcal{H},{\bf z}\mapsto f_{\bf z},$ and we define
the accuracy confidence function by [10]

${\bf AC}_{m}(\Theta,\mathcal{H},\varepsilon):=\inf_{f_{\bf
z}\in\Psi_{m}}\sup_{\rho\in\mathcal{M}(\Theta)}P^{m}\\{{\bf
z}:\|f_{\rho}-f_{\bf z}\|_{\rho}^{2}>\varepsilon\\}.$

Furthermore, we define the accuracy confidence function for all possible
estimators based on $m$ samples $\Phi_{m}:{\bf z}\mapsto f_{\bf z}$ by

${\bf AC}_{m}(\Theta,\varepsilon):=\inf_{f_{\bf
z}\in\Phi_{m}}\sup_{\rho\in\mathcal{M}(\Theta)}P^{m}\\{{\bf
z}:\|f_{\rho}-f{\bf z}\|_{\rho}^{2}>\varepsilon\\}.$

From these definitions, it is obvious that

${\bf AC}_{m}(\Theta,\varepsilon)\leq{\bf
AC}_{m}(\Theta,\mathcal{H},\varepsilon)$

for all $\mathcal{H}$.

###  5.2 $q$-independent learning rate

The sample dependent hypothesis space (SDHS) associated with
$L_{2n}(\cdot,\cdot)$ is then defined by

$\mathcal{H}_{L,{\bf
z}}:=\left\\{\sum_{i=1}^{m}a_{i}L_{2n}(x_{i},\cdot):a_{i}\in\mathbf{R}\right\\}$

and the corresponding $l^{q}$ regularization scheme is defined by

$f_{{\bf z},\lambda,q}=\arg\min_{f\in\mathcal{H}_{L,{\bf
z}}}\left\\{\frac{1}{m}\sum_{i=1}^{m}(f(x_{i})-y_{i})^{2}+\Omega_{\bf
z}^{q}(f_{{\bf z},\lambda,q})\right\\},$ (16)

where

$\Omega_{\bf z}^{q}(f):=\lambda\sum_{i=1}^{m}|a_{i}|^{q},\mbox{for}\
f=\sum_{i=1}^{m}a_{i}L_{2n}(x_{i},\cdot).$

The projection operator $\pi_{M}$ from the space of measurable functions
$f:X\rightarrow\mathbf{R}$ to $[-M,M]$ is defined by

$\pi_{M}(f)(x):=\left\\{\begin{array}[]{ll}M,&\mbox{if }\ f(x)>M,\\\
f(x),&\mbox{if }\ -M\leq f(x)\leq M,\\\ -M,&\mbox{if}\
f(x)\leq-M.\end{array}\right.$

As $y\in[-M,M]$ by assumption, it is easy to check [37] that

$\|\pi_{M}f_{{\bf z},\lambda,q}-f_{\rho}\|_{\rho}\leq\|f_{{\bf
z},\lambda,q}-f_{\rho}\|_{\rho}.$

Also, for arbitrary $H\subset L^{2}(\mathbf{B}^{d})$, we denote
$\pi_{M}H:=\\{\pi_{M}f:f\in H\\}$.

We also need to introduce the class of priors. For any $f\in
L^{2}(\mathbf{B}^{d})$, denote by $\mathcal{F}(f)$ or $\hat{f}$ the Fourier
transformation of $f$,

$\hat{f}(u):=(2\pi)^{d/2}\int_{\mathbf{R}^{d}}f(x)e^{iu\cdot x}dx,$

where $u\in\mathbf{B}^{d}$. The inverse Fourier transformation will be denoted
by $\mathcal{F}^{-1}$. In the space $L^{2}(\mathbf{B}^{d})$, the derivative of
$f$ with order $\alpha$ is defined as

$D^{\alpha}f:=\mathcal{F}^{-1}\\{|u|^{\alpha}\mathcal{F}(u)\\},$

where $|u|:=\sqrt{u_{1}^{2}+\cdot+u_{d}^{2}}$. Here, Fourier transformation
and derivatives are all taken sense in distribution. Let $r$ be any positive
number. We consider the Sobolev class of functions

$W_{2}^{r}:=\left\\{f:\max_{0\leq\alpha\leq
r}\|D^{\alpha}f\|_{L^{2}(\mathbf{B}^{d})}<\infty\right\\}.$

It follows from the well known Sobolev embedding theorem that
$W_{2}^{r}\subset C(\mathbf{B}^{d})$ provided $r>\frac{d}{2}.$

Now, we state the main result of this paper, whose proof will be given in the
next section.

######  Theorem 1.

Let $f_{\rho}\in W_{2}^{r}$ with $r>d/2$, $m\in\mathbf{N}$, $\varepsilon>0$ be
any numbers, and $n\sim\varepsilon^{-r/d}$. If $f_{{\bf z},\lambda,q}$ is
defined as in (16) with $\lambda=m^{-1}\varepsilon$ and $0<q<\infty$, then
there exist positive constants $C_{i},$ $i=1,\dots,4,$ depending only on $M$,
$\rho$, $q$ and $d$, $\varepsilon_{0}>0$ and
$\varepsilon_{m}^{-},\varepsilon_{m}^{+}$ satisfying

$C_{1}m^{-2r/(2r+d)}\leq\varepsilon_{m}^{-}\leq\varepsilon_{m}^{+}\leq
C_{2}(m/\log m)^{-2r/(2r+d)},$ (17)

such that for any $\varepsilon<\varepsilon_{m}^{-}$,

$\sup_{f_{\rho}\in W_{2}^{r}}P^{m}\\{{\bf z}:\|f_{\rho}-\pi_{M}f_{{\bf
z},\lambda,q}\|_{\rho}^{2}>\varepsilon\\}\geq{\bf
AC}_{m}(W_{2}^{r},\pi_{M}\mathcal{H}_{L,{\bf z}},\varepsilon)\geq{\bf
AC}_{m}(W_{2}^{r},\varepsilon)\geq\varepsilon_{0},$ (18)

and for any $\varepsilon\geq\varepsilon_{m}^{+}$,

$\displaystyle e^{-C_{3}m\varepsilon}$ $\displaystyle\leq$ $\displaystyle{\bf
AC}_{m}(W_{2}^{r},\varepsilon)\leq{\bf
AC}_{m}(W_{2}^{r},\pi_{M}\mathcal{H}_{L,{\bf z}},\varepsilon)$ (19)
$\displaystyle\leq$ $\displaystyle\sup_{f_{\rho}\in W_{2}^{r}}P^{m}\\{{\bf
z}:\|f_{\rho}-\pi_{M}f_{{\bf z},\lambda,q}\|_{\rho}^{2}>\varepsilon\\}\leq
e^{-C_{4}m\varepsilon}.$

###  5.3 Remarks

We explain Theorem 1 below in more detail. At first, we explain why the
accuracy function is used to characterize the generalization capability of the
$l^{q}$ regularization schemes (16). In applications, we are often faced with
the following problem: There are $m$ data available, and we are asked to
product an estimator with tolerance at most $\varepsilon$ by using these $m$
data only. In such circumstance, we have to know the probability of success.
It is obvious that such probability depends on $m$ and $\varepsilon$. For
example, if $m$ is too small, we can not construct an estimator within small
tolerance. This fact is quantitatively verified by Theorem 1. More
specifically, (18) shows that if there are $m$ data available and $f_{\rho}\in
W_{2}^{r}$ with $r>d/2$, then $l^{q}$ $(0<q<\infty)$ regularization scheme
(16) is impossible to yield an estimator with tolerance error smaller than
$\varepsilon_{m}^{-}$. This is not a negative result, since we can see in (18)
also that the main reason of impossibility is the lack of data rather than
inappropriateness of the learning scheme (16). More importantly, Theorem 1
reveals a quantitive relation between the probability of success and the
tolerance error based on $m$ samples. It says in (19) that if the tolerance
error $\varepsilon$ is relaxed to $\varepsilon_{m}^{+}$ or larger, then the
probability of success of $l^{q}$ regularization is at least
$1-e^{-{C_{4}m\varepsilon}}$. The first inequality (lower bound) of (19)
implies that such confidence can not be improved further. That is, we have
presented an optimal confidence estimation for $l^{q}$ regularization scheme
(16) with $0<q<\infty$. Thus, Theorem 1 basically concludes the following
thing: If $\varepsilon<\varepsilon_{m}^{-}$, then every estimator deduced from
$m$ samples by $l^{q}$ regularization can not approximate the regression
function with tolerance smaller than $\varepsilon$, while if
$\varepsilon\geq\varepsilon_{m}^{+}$, then the $l^{q}$ regularization schemes
with any $0<q<\infty$ can definitely yield the estimators that approximate the
regression function with tolerance $\varepsilon$.

The values $\varepsilon_{m}^{-}$ and $\varepsilon_{m}^{+}$ thus are critical
for indicating the generalization error of a learning scheme. Indeed, the
upper bound of generalization error of a learning scheme depends heavily on
$\varepsilon_{m}^{+}$, while the lower bound of generalization error is
relative to $\varepsilon_{m}^{-}$. Thus, in order to have a tight
generalization error estimate of a learning scheme, we naturally wish to make
the interval $[\varepsilon_{m}^{-},\varepsilon_{m}^{+}]$ as short as possible.
Theorem 1 shows that, for $l^{q}$ regularization scheme (16),
$\varepsilon_{m}^{-}\geq C_{1}m^{-2r/(2r+d)}$, and $\varepsilon_{m}^{+}\leq
C_{2}(m/\log m)^{-2r/(2r+d)}$, which shows that the interval
$[\varepsilon_{m}^{-},\varepsilon_{m}^{+}]$ is almost the shortest one in the
sense that up to a logarithmic factor, the upper bound and lower bound are
asymptotical identical. Noting that the learning rate established in Theorem 1
is independent of $q$, we thus can conclude that the generalization capability
of $l^{q}$ regularization does not depend on the choice of $q$. This gives an
affirmative answer to Problem 1.

The other advantage of using the accuracy confidence function to measure the
generalization capability is that it allows to expose some phenomenon that can
not be founded if the classical expectation standard is utilized. For example,
Theorem 1 shows a sharp phase transition phenomenon of $l^{q}$ regularization
learning, that is, the behavior of the accuracy confidence function changes
dramatically within the critical interval
$[\varepsilon_{m}^{-},\varepsilon_{m}^{+}]$. It drops from a constant
$\varepsilon_{0}$ to an exponentially small quantity. We might call
$[\varepsilon_{m}^{-},\varepsilon_{m}^{+}]$ the interval of phase transition
for a corresponding learning scheme. To make this more intuitive, let us
conduct a simulation on the phase transition of the confidence function below.
Without loss of generality, we implemented the $l^{2}$ regularization strategy
(16) associated with the kernel (10) for $d=1$ and $n=8$ to yield the
estimator. The regularization parameter $\lambda$ was chosen as
$\varepsilon/m$. The training samples were drawn independently and identically
according to the uniform distribution from the well known $Sinc$ function,
that is $f(x):=sinx/x$. The number of the training samples $m$ was chosen from
$1$ to $100$ and the tolerance $\varepsilon$ was chosen from $10^{-4}$ to $1$
with step-length $10^{-4}$. Then, there were totally 1000 test data
$(s_{i},t_{i})_{i=1}^{1000}$ drawn i. i. d according to the uniform
distribution from $sinC$. The test error was defined as
$\delta_{test}:=\sqrt{\frac{1}{100}\sum_{i=1}^{100}(f_{{\bf
z},\lambda,2}(s_{i})-t_{i})^{2}}.$ We repeated 100 times simulations at each
point, and labeled its value as $1$ if $\delta_{test}$ is smaller than the
tolerance error and $0$ otherwise. Simulation result is shown in Fig.3. We can
see from Fig.3 that in the upper right part, the colors of all points are red,
which means that in those setting, the probability that $\delta_{test}$ is
smaller than the tolerance is approximately $0$. Thus, if the number of
samples is small, then $l^{2}$ regularization schemes can not provide an
estimation with very small tolerance. In the lower left area, the colors of
all points are blue, which means that the probability of $\delta_{test}$
smaller than the tolerance is approximately $1$. Between these two areas,
there exists a band, that could be called the phase transition area, in which
the colors of points vary from red to blue dramatically. It is seen that the
length of phase transition interval monotonously decreases with $m$. All these
coincide with the theoretical assertions of Theorem 1.

Figure 3: The phase transition phenomenon of generalization with $l^{2}$
regularization

For comparison, we also present a generalization error bound result in terms
of expectation error. Corollary 1 below can be directly deduced from Theorem 1
and [10, Chapter 3], if we notice the identity:

$E_{\rho^{m}}(\mathcal{E}(f_{\rho})-\mathcal{E}(f_{{\bf
z},\lambda,q}))=\int_{0}^{\infty}P^{m}\\{\mathcal{E}(f_{\rho})-\mathcal{E}(f_{{\bf
z},\lambda,q})>\varepsilon\\}d\varepsilon.$

######  Corollary 1.

Let $f_{\rho}\in W_{2}^{r}$ with $r>d/2$, $q_{0}>0$, $m\in\mathbf{N}$, and
$n\sim\varepsilon^{-r/d}$. If $f_{{\bf z},\lambda,q}$ is defined as in (16)
with $\lambda\sim\frac{m^{-2r/(2r+d)}}{m+1}$ and $0<q<\infty$, then there
exist constants $C_{5}$ and $C_{6}$ depending only on $M$, $d$, $q$ and $\rho$
such that

$\displaystyle C_{5}m^{-2r/(2r+d)}\leq\inf_{f_{\bf
z}\in\Phi_{m}}\sup_{\rho\in\mathcal{M}(W_{2}^{r})}E_{\rho^{m}}\\{\|f_{\rho}-f_{\bf
z}\|_{\rho}^{2}\\}$ $\displaystyle\leq$ $\displaystyle\inf_{f_{\bf
z}\in\pi\mathcal{H}_{L,{\bf
z}}}\sup_{\rho\in\mathcal{M}(W_{2}^{r})}E_{\rho^{m}}\\{\|f_{\rho}-f_{\bf
z}\|_{\rho}^{2}\\}$ $\displaystyle\leq$ $\displaystyle\sup_{f_{\rho}\in
W_{2}^{r}}E_{\rho^{m}}\left\\{\|f_{\rho}-f_{{\bf
z},\lambda,q}\|^{2}\right\\}\leq C_{6}(m/\log m)^{-2r/(2r+d)},$

where $\Phi_{m}$ is the set of all possible estimators based on $m$ samples.

It is noted that the representation theorem in learning theory [27] implies
that the generalization capability of an optimal learning algorithm in SDHS is
not worse than that of learning in RKHS with convex loss function. Corollary 1
then shows that if $f_{\rho}\in W_{2}^{r}$, then the generalization capability
of an optimal learning scheme in SDHS associated with $L_{2n}$ is not worse
than that of any optimal learning algorithms in the corresponding RKHS. More
specifically, (1) shows that as far as the learning rate is concerned, all
$l^{q}$ regularization schemes (16) for $0<q<\infty$ can realize the same
almost optimal theoretical rate. That is to say, the choice of $q$ has no
influence on the generalization capability of the learning schemes (16). This
also gives an affirmative answer to Problem 1 in the sense of expectation.
Here, we emphasize that the independence of generalization of $l^{q}$
regularization on $q$ is based on the understanding of attaining the same
almost optimal generalization error. Thus, in application, $q$ can be
arbitrarily specified, or specified merely by other no generalization criteria
(like complexity, sparsity, etc.).

##  6 Proof of Theorem 1

###  6.1 Methodology

The methodology we adopted in the proof of Theorem 1 seems of novelty.
Traditionally, the generalization error of learning schemes in SDHS is divided
into the approximation, hypothesis and sample errors (three terms) [33]. All
of the aforementioned results about coefficient regularization in SDHS falled
into this style. According to [33], the hypothesis error has been regarded as
the reflection of nature of data dependence of SDHS (sample dependent
hypothesis space), and an indispensable part attributed to an essential
characteristic of learning algorithms in SDHS, compared with the learning in
SIHS (sample independent hypothesis space). With the specific kernel function
$L_{2n}$, we will divide the generalization error of $l^{q}$ regularization in
this paper into the approximation and sample errors (two terms) only. Both of
these two terms are dependent of the samples. The success in this paper then
reveals that for at least some kernels, the hypothesis error is negligible, or
can be avoided in estimation when $l^{q}$ regularization learning are analyzed
in SDHS. We show that such new methodology can bring an important benefit of
yielding an almost optimal generalization error bound for a large types of
priors. Such benefit may reasonably be expected to beyond the $l^{q}$
regularization.

We sketch the methodology to be used as follows. Due to the sample dependent
property, any estimators constructed in SDHS may be a random approximant. To
bound the approximation error, we first deduce a probabilistic cubature
formula for algebraic polynomial. Then we can discretize the near-best
approximation operator $\mathcal{L}_{2n}f$ based on the probabilistic cubature
formula. Thus, the well known Jackson-type error estimate [9] can be applied
to derive the approximation error. To bound the sample error, we will use a
different method from the tranditional approaches [3, 32]. Since the
constructed approximant in SDHS is a random approximant, the concentration
inequality such as Bernstein inequality [4] can not be available. In our
approach, based on the prominent property of the constructed approximant, we
will bound the sample error by using the concentration inequality established
in [3] twice. Then the relation between the so-called Pseudo-dimension and
covering number [18] yields the sample error estimate for $l^{q}$
regularization schemes (16) with arbitrary $o<q<\infty$. Hence, we divide the
proof into four subsections. The first subsection is devoted to establish the
probabilistic cubature formula. The second subsection is to construct the
random approximant and study the approximation error. The third subsection is
to deduce the sample error and the last subsectionis to derive the final
learning rate. We present the details one by one below.

###  6.2 A probabilistic cubature formula

In this subsection, we establish a probabilistic cubature formula. At first,
we need several lemmas. The weighted $L^{p}$ norm on the $d+1$-dimensional
unit sphere $\mathbf{S}^{d}$ is defined as follows. Let
$\alpha=(\alpha_{(1)},\dots,\alpha_{(d+1)})\in\mathbf{S}^{d}$ and
$w_{\alpha}=|\alpha_{(d+1)}|$. Define

$\|f\|_{p,w_{\alpha}}:=\left\\{\begin{array}[]{cc}\left(\int_{\mathbf{S}^{d}}|f(\alpha)|^{p}w_{\alpha}d\omega_{d}(\alpha)\right)^{1/p},&1\leq
p\leq\infty,\\\
\max_{\alpha\in\mathbf{S}^{d}}|f(\alpha)|w_{\alpha},&p=\infty.\end{array}\right.$

The following [6, Lemma 2.3] gives a weighted Nikolskii inequality for
spherical polynomial.

######  Lemma 4.

Let $1\leq p\leq q\leq\infty$. Then for any $Q\in\Pi_{n}^{d}$,

$\|Q\|_{q,w_{\alpha}}\leq Cn^{d(1/p-1/q)}\|Q\|_{p,w_{\alpha}},$

where $C$ is a positive constant depending only on $d,p$ and $q$.

Lemma 5 establishes a relation between cubature formula on the unit sphere and
cubature formula on the unit ball, which can be found in [35, Theorem 4.2].

######  Lemma 5.

If there is a cubature formula of degree $n$ on $\mathbf{S}^{d}$ given by

$\int_{\mathbf{S}^{d}}f(\alpha)w_{\alpha}d\omega_{d}(\alpha)=\sum_{i=1}^{m}a_{i}f(\alpha_{i}),$

whose nodes are all located on $\mathbf{S}^{d}$, then there exists a cubature
formula of degree $n$ on $\mathbf{B}^{d}$, that is,

$2\int_{\mathbf{B}^{d}}f(x)dx=\sum_{i=1}^{m}a_{i}f(x_{i}),$

where $x_{i}\in\mathbf{B}^{d}$ are the first $d$ components of $\alpha_{i}$.

The following Lemma 6 is known as the Bernstein inequality for random
variables, which can be found in [3].

######  Lemma 6.

Let $\xi$ be a random variable on a probability space $Z$ with mean $E(\xi)$,
variance $\sigma^{2}(\xi)=\sigma^{2}$. If $|\xi(z)-E(\xi)|\leq M_{\xi}$ for
almost all ${\bf z}\in Z$. then, for all $\varepsilon>0$,

$\mbox{Prob}_{{\bf z}\in
Z^{m}}\left\\{\left|\frac{1}{m}\sum_{i=1}^{m}\xi(z_{i})-E(\xi)\right|\geq\varepsilon\right\\}\leq
2\exp\left\\{-\frac{m\varepsilon^{2}}{2\left(\sigma^{2}+\frac{1}{3}M_{\xi}\varepsilon\right)}\right\\}.$

We also need a lemma showing that if
$\Xi:=\\{\alpha_{i}\\}_{i=1}^{m}\subset\mathbf{S}^{d}$ is a set of independent
random variables drawn identically according to a distribution $\mu$, then
with high confidence the cubature formula holds.

######  Lemma 7.

Let $0<\varepsilon<1$, and $1\leq p\leq\infty$. If
$\\{\alpha_{i}\\}_{i=1}^{m}$ are i.i.d. random variables drawn according to
arbitrary distribution $\mu$ on $\mathbf{S}^{d}$, then there exits a set of
real numbers $\\{a_{i}\\}_{i=1}^{m}$ such that

$\int_{\mathbf{S}^{d}}Q_{n}(\alpha)w_{\alpha}d\omega_{d}(\xi)=\sum_{i=1}^{m}a_{i}Q_{n}(\alpha_{i})$

holds with confidence at least

$1-2\exp\left\\{-\frac{Cm\varepsilon^{2}}{n^{d}(1+\varepsilon)}\right\\},$

subject to

$\sum_{i=1}^{m}|a_{i}|^{p}\leq\frac{\Omega_{d}}{1-\varepsilon}m^{1-p}.$

Proof. For the sake of brevity, we write $w=w_{\alpha}$ in the following.
Since the sampling set $\Xi$ consists of a sequence of i.i.d. random variables
on $\mathbf{S}^{d}$, the sampling points are a sequence of functions
$\alpha_{j}=\alpha_{j}(\omega)$ on some probability space
$(\Omega,\mathbf{P})$. Without loss of generality, we assume
$\|Q_{n}\|_{p,w}=1$ for arbitrary fixed $p$. If we set
$\xi_{j}^{p}(Q_{n})=|Q_{n}(\alpha_{j})|^{p}w$, then we have

$\frac{1}{m}\sum_{i=1}^{m}|Q_{n}(\alpha_{i})|^{p}w(\alpha_{i})-E\xi_{j}^{p}=\frac{1}{m}\sum_{i=1}^{m}|Q_{n}(\alpha_{i})|^{p}w(\alpha_{i})-\|Q_{n}\|_{p,w}^{p},$

where we have used the equality

$E\xi_{j}^{p}=\int_{\Omega}|Q_{n}(\alpha(\omega_{j}))|^{p}wd\omega_{j}=\int_{S}|Q_{n}(\alpha)|^{p}w(\alpha)d\omega_{d}(\alpha)=\|Q_{n}\|_{p,w}^{p}=1.$

Furthermore,

$|\xi_{j}^{p}-E\xi_{j}^{p}|\leq\sup_{\omega\in\Omega}\left||Q_{n}(\alpha(\omega))|^{p}w(\omega)-\|Q_{n}\|_{p,w}^{p}\right|\leq\|Q_{n}\|_{\infty,w}^{p}-\|Q_{n}\|_{p,w}^{p}.$

It follows from Lemma 4 that

$\|Q_{n}\|_{\infty,w}\leq Cn^{\frac{d}{p}}\|Q_{n}\|_{p,w}=Cn^{\frac{d}{p}}.$

Hence

$|\xi_{j}^{p}-E\xi_{j}^{p}|\leq Cn^{d}-1.$

On the other hand, we have

$\displaystyle\sigma^{2}$ $\displaystyle=$ $\displaystyle
E((\xi_{j}^{p})^{2})-(E(\xi_{j}^{p}))^{2}\leq\int_{\Omega}|Q_{n}(\alpha(\omega))|^{2p}w(\alpha)d\omega-\left(\int_{\Omega}|Q_{n}(\alpha(\omega))|^{p}w(x)d\omega\right)^{2}$
$\displaystyle=$ $\displaystyle\|Q_{n}\|_{2p,w}^{2p}-\|Q_{n}\|_{p,w}^{2p}.$

Then using Lemma 4 again, there holds

$\sigma^{2}\leq
Cn^{2dp(\frac{1}{p}-\frac{1}{2p})}\|Q_{n}\|_{p,w}^{2p}-\|Q_{n}\|_{p,w}^{2p}=Cn^{d}-1.$

Thus it follows from Lemma 6 that with confidence at least

$1-2\mbox{exp}\left\\{-\frac{m\varepsilon^{2}}{2\left(\sigma^{2}+\frac{1}{3}M_{\xi}\varepsilon\right)}\right\\}\geq
1-2\mbox{exp}\left\\{-\frac{m\varepsilon^{2}}{2\left((Cn^{d}-1)+\frac{1}{3}(Cn^{d}-1)\varepsilon\right)}\right\\},$

there holds

$\left|\frac{1}{m}\sum_{i=1}^{m}|Q_{n}(\alpha_{i})|^{p}w(\alpha_{i})-\|Q_{n}\|_{p,w}^{p}\right|\leq\varepsilon.$

This means that if $\Xi$ is a sequence of i.i.d. random variables, then the
Marcinkiewicz-Zygmund inequality

$(1-\varepsilon)\|Q_{n}\|_{p,w}^{p}\leq\frac{1}{m}\sum_{i=1}^{m}|Q_{n}(\alpha_{i})|^{p}w(x)\leq(1+\varepsilon)\|Q_{n}\|_{p,w}^{p}\quad\forall
Q_{n}\in\Pi_{n}^{d}$ (21)

holds with probability at least

$1-2\mbox{exp}\left\\{-\frac{Cm\varepsilon^{2}}{n^{d-1}(1+\varepsilon)}\right\\}.$

Then, almost same argument as that in [19, Theorem 4.1] or [5, Theorem 4.2]
implies Lemma 7. $\Box$

By virtue of the above lemmas, we can prove the following Proposition 5.

######  Proposition 5.

Let $1\leq p\leq\infty$ and ${\bf x}:=(x_{i})_{i=1}^{m}\subset\mathbf{B}^{d}$
be a set of random variables independently and identically drawn according to
arbitrary distribution $\mu$. Then there exits a set of real numbers
$\\{a_{i}\\}_{i=1}^{m}$ and a constant $C$ depending only on $d$ such that the
equality

$\int_{\mathbf{B}^{d}}P_{n}(x)dx=\sum_{i=1}^{m}a_{i}P_{n}(x_{i}),\quad
P_{n}\in\mathcal{P}_{n}$

holds with confidence at least

$1-2\mbox{exp}\left\\{-\frac{Cm}{n^{d}}\right\\},$

subject to

$\sum_{i=1}^{m}|a_{i}|^{p}\leq Cm^{1-p}.$

###  6.3 Error decomposition and an approximation error estimate

To estimate the upper bound of

$\mathcal{E}(\pi_{M}f_{{\bf z},\lambda,q})-\mathcal{E}(f_{\rho}),$

we first introduce an error decomposition strategy. It follows from the
definition of $f_{{\bf z},\lambda,q}$ that, for arbitrary
$f\in\mathcal{H}_{L,{\bf z}}$,

$\displaystyle\mathcal{E}(\pi_{M}f_{{\bf z},\lambda,q})-\mathcal{E}(f_{\rho})$
$\displaystyle\leq$ $\displaystyle\mathcal{E}(\pi_{M}f_{{\bf
z},\lambda,q})-\mathcal{E}(f_{\rho})+\lambda\Omega_{\bf z}^{q}(f_{{\bf
z},\lambda,q})$ $\displaystyle\leq$ $\displaystyle\mathcal{E}(\pi_{M}f_{{\bf
z},\lambda,q})-\mathcal{E}_{\bf z}(\pi_{M}f_{{\bf
z},\lambda,q})+\mathcal{E}_{\bf z}(f)-\mathcal{E}(f)$ $\displaystyle+$
$\displaystyle\mathcal{E}_{\bf z}(\pi_{M}f_{{\bf
z},\lambda,q})+\lambda\Omega_{\bf z}^{q}(f_{{\bf
z},\lambda,q})-\mathcal{E}_{\bf z}(f)-\lambda\Omega_{\bf z}^{q}(f)$
$\displaystyle+$
$\displaystyle\mathcal{E}(f)-\mathcal{E}(f_{\rho})+\lambda\Omega_{\bf
z}^{q}(f)$ $\displaystyle\leq$ $\displaystyle\mathcal{E}(\pi_{M}f_{{\bf
z},\lambda,q})-\mathcal{E}_{\bf z}(\pi_{M}f_{{\bf
z},\lambda,q})+\mathcal{E}_{\bf z}(f)-\mathcal{E}(f)$ $\displaystyle+$
$\displaystyle\mathcal{E}(f)-\mathcal{E}(f_{\rho})+\lambda\Omega_{\bf
z}^{q}(f).$

Since $f_{\rho}\in W_{2}^{r}$ with $r>\frac{d}{2}$, it follows from the
Sobolev embedding theorem that $f_{\rho}\in C(\mathbf{B}^{d})$. Thus, it can
be deduced from Proposition 3 and Proposition 4 that there exists a
$P_{\rho}\in\mathcal{P}_{n}$ such that

$\|P_{\rho}\|\leq c\|f_{\rho}\|\quad\mbox{and}\quad\|f_{\rho}-P_{\rho}\|\leq
CE_{[n/2]}(f_{\rho}),$ (22)

where $[t]$ denotes the largest integer not larger than $t$ and $\|\cdot\|$
denotes the uniform norm on $\mathbf{B}^{d}$. The above inequalities together
with the well known Jackson inequality [9] imply that there exists a
$P_{\rho}\in\mathcal{P}_{n}$ such that for all $f_{\rho}\in W_{2}^{r}$ with
$r>\frac{d}{2}$, there holds

$\|P_{\rho}\|\leq
c\|f_{\rho}\|\quad\mbox{and}\quad\|f_{\rho}-P_{\rho}\|^{2}\leq Cn^{-2r}.$ (23)

Let $\mathcal{H}_{L,{\bf z}}^{*}:=\left\\{f\in\mathcal{H}_{L,{\bf
z}}:\|f\|\leq cM\right\\}$, where $c$ is defined as in (22). Define

$f_{\bf z}^{*}:=\arg\min_{f\in\mathcal{H}_{L,{\bf
z}}^{*}}\|f-f_{\rho}\|_{\rho}^{2}+\lambda\Omega_{\bf z}^{q}(f).$ (24)

Then we have

$\displaystyle\mathcal{E}(\pi_{M}f_{{\bf z},\lambda,q})-\mathcal{E}(f_{\rho})$
$\displaystyle\leq$ $\displaystyle\left\\{\mathcal{E}(f_{\bf
z}^{*})-\mathcal{E}(f_{\rho})+\lambda\Omega_{\bf z}^{q}(f_{\bf
z}^{*})\right\\}$ $\displaystyle+$
$\displaystyle\left\\{\mathcal{E}(\Pi_{M}f_{{\bf
z},\lambda,q})-\mathcal{E}_{\bf z}(\Pi_{M}f_{{\bf
z},\lambda,q})+\mathcal{E}_{\bf z}(f_{\bf z}^{*})-\mathcal{E}(f_{\bf
z}^{*})\right\\}$ $\displaystyle=:$ $\displaystyle\mathcal{D}({\bf
z},\lambda,q)+\mathcal{S}({\bf z},\lambda,q),$

where $\mathcal{D}({\bf z},\lambda,q)$ and $\mathcal{S}({\bf z},\lambda,q)$ is
called the approximation error and sample error, respectively.

######  Proposition 6.

Let $m,n\in\mathbf{N}$, $r>d/2$ and $f_{\rho}\in W_{2}^{r}$. Then, with
confidence at least $1-2\exp\\{{-cm/n^{d}}\\},$ there holds

$\mathcal{D}({\bf z},\lambda,q)\leq C\left(n^{-2r}+\lambda m\right),$ (25)

where $C$ and $c$ are constants depending only on $d$ and $r$.

Proof. From Proposition 1, it is easy to deduce that

$P_{\rho}(x)=\int_{\mathbf{B}^{d}}P_{\rho}(y)L_{2n}(x,y)dy.$

Thus, Lemma 5 with $\varepsilon=\frac{1}{2}$ yields that with confidence at
least $1-2\exp\\{{-cm/n^{d}}\\},$ there exists a set of real numbers
$\\{a_{i}\\}_{i=1}^{m}$ satisfying $\sum_{i=1}^{m}|a_{i}|^{q}\leq
2\Omega_{d}m^{1-q}$ for $q\geq 1$ such that

$P_{\rho}(x)=\sum_{i=1}^{m}a_{i}P_{\rho}(x_{i})L_{2n}(x_{i},x).$

The above observation together with (23) implies that with confidence at least
$1-2\exp\\{{-cm/n^{d}}\\},$ there exists a

$g^{*}(x):=\sum_{i=1}^{m}a_{i}P_{\rho}(x_{i})L_{2n}(x_{i},x)\in\mathcal{H}_{L,{\bf
z}}^{*}$

such that for arbitrary $f_{\rho}\in W_{2}^{r}$, there holds

$\|g^{*}-f_{\rho}\|_{\rho}^{2}\leq\|g^{*}-f_{\rho}\|^{2}\leq Cn^{-2r},$

and

$\Omega_{\bf
z}^{q}(g^{*})=\sum_{i=1}^{m}|a_{i}P_{\rho}(x_{i})|^{q}\leq(cM)^{q}\sum_{i=1}^{m}|a_{i}|^{q}\leq
Cm,$

where $C$ is a constant depending only on $d$ and $M$. Indeed, if $q\geq 1$,
we have $\sum_{i=1}^{m}|a_{i}|^{q}\leq 2\Omega_{d}m^{1-q}$. Without loss of
generality, we assume $m\geq cM$. Then there holds

$\sum_{i=1}^{m}|a_{i}P_{\rho}(x_{i})|^{q}\leq(cM)^{q}2\Omega_{d}m^{1-q}\leq
2\Omega_{d-1}m.$

If $0<q<1$, it follows from the Hölder inequality that

$\sum_{i=1}^{m}|a_{i}|^{q}\leq\left(\sum_{i=1}^{m}|a_{i}|\right)^{q}\left(\sum_{i=1}^{m}1\right)^{1-q}\leq
m^{1-q}(2\Omega_{d})^{q}\leq 2\Omega_{d}m.$

Thus, for all $q_{0}\leq q\leq\infty$, there holds

$\sum_{i=1}^{m}|a_{i}P_{\rho}(x_{i})|^{q}\leq 2cM\Omega_{d-1}m.$

It thus follows from the definition of $f_{\bf z}^{*}$ that the inequalities

$\mathcal{D}({\bf
z},\lambda,q)\leq\|g^{*}-f_{\rho}\|_{\rho}^{2}+\lambda\Omega_{\bf
z}^{q}(g^{*})\leq C\left(n^{-2r}+\lambda m\right)$ (26)

holds with confidence at least $1-2\exp\\{{-cm/n^{d}}\\}.$ $\Box$

###  6.4 A sample error estimate

For further use, we also need introducing some quantities to measure the
complexity of a space [14, 16]. Let $B$ be a Banach space and $V$ a compact
set in $B$. The quantity $H_{\varepsilon}(V,B)=\log_{2}N_{\varepsilon}(V,B)$,
where $N_{\varepsilon}(V,B)$ is the number of elements in least
$\varepsilon$-net of $V$, is called $\varepsilon$-entropy of $V$ in $B$. The
quantity $N_{\varepsilon}(V,B)$ is called the $\varepsilon$-covering number of
$V$. For any $t\in\mathbf{R}$, define

$\mbox{sgn}(t):=\left\\{\begin{array}[]{cc}1,&\mbox{if}\ t\geq 0,\\\
-1,&\mbox{if}\ t<0.\end{array}\right.$

If a vector ${\bf t}=(t_{1},\dots,t_{n})$ belongs to $\mathbf{R}^{n}$, then we
denote by $\mbox{sgn}({\bf t})$ the vector $(\mbox{sgn}(t_{1}),$
$\dots$,$\mbox{sgn}(t_{n}))$. The VC dimension of a set $V$ over
$\mathbf{B}^{d}$, denoted as $VCdim(V,\mathbf{B}^{d})$, is the maximal natural
number $m$ such that there exists a collection $(\mu_{1},\dots,\mu_{m})$ in
$\mathbf{B}^{d}$ such that the cardinality of the sgn-vectors set

$S=\\{(\mbox{sgn}(v(\mu_{1})),\dots,\mbox{sgn}(v(\mu_{m}))):v\in V\\}$

equals to $2^{m}$, that is, the set $S$ coincides with the set of all vertexes
of unit cube in $\mathbf{R}^{m}$. The quantity

$Pdim(V,\mathbf{B}^{d}):=\max_{g}VCdim(V+g,\mathbf{B}^{d}),$

is called pseudo-dimension of the set $V$ over $\mathbf{B}^{d}$, where $g$
runs all functions defined on $\mathbf{B}^{d}$ and $V+g=\\{v+g:v\in V\\}$ .

Mendelson and Vershinin [18] (see also [16]) has established the following
important relation between Pseudo-dimension and $\varepsilon$-entropy.

######  Lemma 8.

Let $V(\mathbf{B}^{d})$ be a class of functions which consists of all
functions $f\in V$ satisfying $|f(x)|\leq R$ for all $x\in\mathbf{B}^{d}$.
Then,

$H_{\varepsilon}(V(\mathbf{B}^{d}),L^{2}(\mathbf{B}^{d}))\leq
c{Pdim}(V,\mathbf{B}^{d})\log_{2}\frac{R}{\varepsilon},$

where $c$ is an absolute positive constant.

The following Lemma 9 [13] further shows that the pseudo-dimension of
arbitrary $m$-dimensional vector space is $m$.

######  Lemma 9.

Let $\mathcal{H}$ be an $m$-dimensional vector space of functions from
$\mathbf{B}^{d}$ into $\mathbf{R}$. Then
${Pdim}(\mathcal{H},\mathbf{B}^{d})=m$.

We also need to apply the following concentration inequality [3].

######  Lemma 10.

Let $\mathcal{G}$ be a set of functions on $Z$ such that, for some $c\geq 0$,
$|g-E(g)|\leq B$ almost everywhere and $E(g^{2})\leq cE(g)$ for each
$g\in\mathcal{G}$. Then, for every $\varepsilon>0$,

$\mbox{Prob}_{z\in
Z^{m}}\left\\{\sup_{f\in\mathcal{G}}\frac{E(g)-\frac{1}{m}\sum_{i=1}^{m}g(z_{i})}{\sqrt{E(g)+\varepsilon}}\leq\sqrt{\varepsilon}\right\\}\leq\mathcal{N}_{\varepsilon}(\mathcal{G},C(\mathbf{B}^{d}))\mbox{exp}\left\\{-\frac{m\varepsilon}{2c+\frac{2B}{3}}\right\\}.$

The following Proposition 7 give an upper bound of sample error.

######  Proposition 7.

Let $m,n\in\mathbf{N}$, $\varepsilon>0$, and $f_{\bf z,\lambda,q}$ be defined
as in (16). Then with confidence at least

$\displaystyle
1-\exp\left\\{cn^{d}\log\frac{Cn^{d+2}\max\\{m^{1-1/q},1\\}M^{\frac{2}{q}+1}}{\lambda^{1/q}\varepsilon}-\frac{3m\varepsilon}{128M^{2}}\right\\}$
$\displaystyle-\exp\left\\{Cn^{d}\log\left(\frac{32M+32cM}{\varepsilon}\right)-\frac{3m\varepsilon}{16(c+3)^{2}M^{2}}\right\\}$

there holds

$\mathcal{S}({\bf z},\lambda,q)\leq\frac{1}{2}(\mathcal{E}(\pi_{M}f_{{\bf
z},\lambda,q})-\mathcal{E}(f_{\rho}))+\frac{1}{2}\mathcal{D}({\bf
z},\lambda,q)+2\varepsilon.$

Proof. If we set $\xi_{1}:=(\pi_{M}f_{{\bf
z},\lambda,q}(x)-y)^{2}-(f_{\rho}(x)-y)^{2},$ and $\xi_{2}:=(f_{\bf
z}^{*}(x)-y)^{2}-(f_{\rho}(x)-y)^{2},$ then

$E(\xi_{1})=\mathcal{E}(\pi_{M}f_{{\bf z},\lambda,q})-\mathcal{E}(f_{\rho}),\
\mbox{and}\ E(\xi_{2})=\mathcal{E}(f_{\bf z}^{*})-\mathcal{E}(f_{\rho}),$

both of which are random variables. Hence, we can rewrite the sample error as

$S({\bf
z},\lambda,q)=\left\\{E(\xi_{1})-\frac{1}{m}\sum_{i=1}^{m}\xi_{1}(z_{i})\right\\}+\left\\{\frac{1}{m}\sum_{i=1}^{m}\xi_{2}(z_{i})-E(\xi_{2})\right\\}=:\mathcal{S}_{1}+\mathcal{S}_{2}.$

Define

$\mathcal{B}_{R}^{q}:=\left\\{f=\sum_{i=1}^{m}a_{i}L_{2n}(x_{i},x):\sum_{i=1}^{m}|a_{i}|^{q}\leq
R\right\\}.$

As $f_{{\bf z},\lambda,q}:=\sum_{i=1}^{m}b_{i}L_{2n}(x_{i},x)$, it follows
from (16) that

$\lambda\sum_{i=1}^{m}|b_{i}|^{q}\leq\frac{1}{m}\sum_{i=1}^{m}(0-y_{i})^{2}+0\leq
M^{2},$

which implies $f_{{\bf z},\lambda,q}\in\mathcal{B}^{q}_{M^{2}/\lambda}$. Let

$\mathcal{F}_{\lambda}:=\left\\{g=(\pi_{M}f(x)-y)^{2}-(f_{\rho}(x)-y)^{2}:f\in\mathcal{B}^{q}_{M^{2}/\lambda}\right\\}.$

Then, for any fixed $g\in\mathcal{F}_{\lambda},$ there exists
$f\in\mathcal{B}^{q}_{M^{2}/\lambda}$ such that
$g(z)=(\pi_{M}f(x)-y)^{2}-(f_{\rho}(x)-y)^{2}$. It is easy to deduce that

$E(g)=\mathcal{E}(\pi_{M}f)-\mathcal{E}(f_{\rho})\geq 0,$
$\frac{1}{m}\sum_{i=1}^{m}g(z_{i})=\mathcal{E}_{\bf
z}(\pi_{M}f)-\mathcal{E}_{\bf z}(f_{\rho}),$

and

$g({z})=\left(\pi_{M}f(x)-f_{\rho}(x)\right)\left[\left(\pi_{M}f(x)-y\right)+\left(f_{\rho}(x)-y\right)\right].$

Since $|y|\leq M$ and $|f_{\rho}(x)|\leq M$ almost everywhere, we find that

$|g({z})|\leq(M+M)(M+3M)\leq 8M^{2}.$

Of course, we have

$|g({z})-E(g)|\leq B:=16M^{2}$

almost everywhere and

$\displaystyle E(g^{2})$ $\displaystyle=$ $\displaystyle
E\left[\left(\pi_{M}f(x)-f_{\rho}(x)\right)^{2}\left\\{\left(\pi_{M}f(x)-y\right)+\left(f_{\rho}(x)-y\right)\right\\}^{2}\right]$
$\displaystyle\leq$ $\displaystyle
16M^{2}\|\pi_{M}f-f_{\rho}\|_{\rho}^{2}=16M^{2}E(g),$

Therefore, we can apply Lemma 10 to the set of functions
$\mathcal{F}_{\lambda}$ with $B=c=16M^{2}$, yielding

$\sup_{f\in\mathcal{B}^{q}_{M^{2}/\lambda}}\frac{\mathcal{E}(\pi_{M}f)-\mathcal{E}(f_{\rho})-\left(\mathcal{E}_{\bf
z}(\pi_{M}f)-\mathcal{E}_{\bf
z}(f_{\rho})\right)}{\sqrt{\mathcal{E}(\pi_{M}f)-\mathcal{E}(f_{\rho})+\varepsilon}}\leq\sqrt{\varepsilon}$
(27)

with confidence at least

$1-\mathcal{N}_{\varepsilon/4}\left(\mathcal{F}_{\lambda},C(\mathbf{B}^{d})\right)\exp\left\\{-\frac{m\varepsilon}{2B+\frac{2}{3}c}\right\\}\geq
1-\mathcal{N}_{\varepsilon/4}\left(\mathcal{F}_{\lambda},C(\mathbf{B}^{d})\right)\exp\left\\{-\frac{3m\varepsilon}{128M^{2}}\right\\}.$

For every $f_{1},f_{2}\in\mathcal{B}^{q}_{M^{2}/\lambda}$ , we have

$\left|(\pi_{M}f_{1}(x)-y)^{2}-(\pi_{M}f_{2}(x)-y)^{2}\right|\leq
4M\|f_{1}-f_{2}\|.$

Thus, a $\left(\frac{\varepsilon}{4M}\right)$-covering of
$\mathcal{B}^{q}_{M^{2}/\lambda}$ provides an $\varepsilon$-covering of
$\mathcal{F}_{\lambda}$ for any $\varepsilon>0$. This implies

$\mathcal{N}_{\varepsilon/4}\left(\mathcal{F}_{\lambda},C(\mathbf{B}^{d})\right)\leq\mathcal{N}_{\varepsilon/(16M)}\left(\mathcal{B}^{q}_{M^{2}/\lambda},C(\mathbf{B}^{d})\right)\leq\mathcal{N}_{\varepsilon/(16M)}\left(\mathcal{B}^{q}_{M^{2}/\lambda},L^{2}(\mathbf{B}^{d})\right).$

It is also needed to derive an upper bound estimation for
$\mathcal{N}_{\varepsilon/(16M)}\left(\mathcal{B}^{q}_{M^{2}/\lambda},L^{2}(\mathbf{B}^{d})\right)$.
For $q\geq 1$, and $f\in\mathcal{B}_{M^{2}/\lambda}^{q}$, it follows from
Proposition 2 and the Hölder inequality that

$\left|\sum_{i=1}^{m}b_{i}L_{2n}(x_{i},x)\right|\leq\max_{x,y\in\mathbf{B}^{d}}L_{2n}(x,y)\sum_{i=1}^{m}|b_{i}|\leq
Cn^{2+d}(M^{2}/\lambda)^{\frac{1}{q}}m^{1-1/q}.$

For $0<q<1$, and $f\in\mathcal{B}_{M^{2}/\lambda}^{q}$, using (12) again we
can obtain

$\left|\sum_{i=1}^{m}b_{i}L_{2n}(x_{i},x)\right|\leq\max_{x,y\in\mathbf{B}^{d}}L_{2n}(x,y)\sum_{i=1}^{m}|b_{i}|\leq
Cn^{2+d}(M^{2}/\lambda)^{\frac{1}{q}}.$

Consequently, for arbitrary $f\in\mathcal{B}_{M^{2}/\lambda}^{q}$ and
arbitrary $0<q<\infty$, there holds

$\left|\sum_{i=1}^{m}b_{i}L_{2n}(x_{i},x)\right|\leq
Cn^{2+d}\max\\{m^{1-1/q},1\\}(M^{2}/\lambda)^{\frac{1}{q_{0}}}.$

Noting that $\mathcal{H}_{L,{\bf z}}$ is a finite dimensional linear space
with its dimension not larger than $cn^{d}$, it follows from Lemma 9 and Lemma
8 that

$\log\mathcal{N}_{\varepsilon/(16M)}\left(\mathcal{B}^{q}_{M^{2}/\lambda},L^{2}(\mathbf{B}^{d})\right)\leq
cn^{d}\log\frac{Cn^{d+2}\max\\{m^{1-1/q},1\\}M^{\frac{2}{q}+1}}{\lambda^{1/q}\varepsilon}.$

Accordingly,

$\mathcal{N}_{\varepsilon/4}\left(\mathcal{F}_{\lambda},C(\mathbf{B}^{d})\right)\leq\exp\left\\{cn^{d}\log\frac{Cn^{d+2}\max\\{m^{1-1/q},1\\}M^{\frac{2}{q}+1}}{\lambda^{1/q}\varepsilon}\right\\},$

which together with (27) further yields

$\mathcal{S}_{1}\leq\frac{1}{2}(\mathcal{E}(\pi_{M}f_{{\bf
z},\lambda,q})-\mathcal{E}(f_{\rho}))+\varepsilon$ (28)

with confidence at least

$1-\exp\left\\{cn^{d}\log\frac{Cn^{d+2}\max\\{m^{1-1/q},1\\}M^{\frac{2}{q}+1}}{\lambda^{1/q}\varepsilon}-\frac{3m\varepsilon}{128M^{2}}\right\\}.$

Now, we turn to estimate $\mathcal{S}_{2}$. By definition of $f_{\bf z}^{*}$,
we have $\|f_{\bf z}^{*}\|\leq cM$. Let

$\mathcal{G}:=\left\\{g=(f(x)-y)^{2}-(f_{\rho}(x)-y)^{2}:f\in\mathcal{H}^{*}_{L,{\bf
z}}\right\\}.$

Then for any fixed $g\in\mathcal{G},$ there exists an
$f\in\mathcal{\mathcal{missing}}H_{L,{\bf z}}^{*}$ such that
$g(z)=(f(x)-y)^{2}-(f_{\rho}(x)-y)^{2}$. Similarly, we have

$E(g)=\mathcal{E}(f)-\mathcal{E}(f_{\rho})\geq
0\quad\mbox{and}\quad\frac{1}{m}\sum_{i=1}^{m}g(z_{i})=\mathcal{E}_{\bf
z}(f)-\mathcal{E}_{\bf z}(f_{\rho}).$

Since $|y|\leq M$, $|f_{\rho}(x)|\leq M$ and $\|f\|\leq cM$ almost everywhere,
we get

$|g({z})|\leq(c+3)^{2}M^{2}\quad\mbox{and}\quad|g({z})-E(g)|\leq
B:=2(c+3)^{2}M^{2}$

almost everywhere. Furthermore,

$E(g^{2})\leq 2(c+3)^{2}M^{2}\|f-f_{\rho}\|_{\rho}^{2}=2(c+3)^{2}M^{2}E(g).$

Then we apply Lemma 10 again to the set of functions $\mathcal{G}$ with
$B=c=2(c+3)^{2}M^{2}$ and obtain

$\sup_{f\in\mathcal{H}_{L,{\bf
z}}}\frac{\mathcal{E}(f)-\mathcal{E}(f_{\rho})-\left(\mathcal{E}_{\bf
z}(f)-\mathcal{E}_{\bf
z}(f_{\rho})\right)}{\sqrt{\mathcal{E}(f)-\mathcal{E}(f_{\rho})+\varepsilon}}\leq\sqrt{\varepsilon}$
(29)

with confidence at least

$1-\mathcal{N}_{\varepsilon/4}\left(\mathcal{G},C(\mathbf{B}^{d})\right)\exp\left\\{-\frac{m\varepsilon}{2B+\frac{2}{3}c}\right\\}\geq
1-\mathcal{N}_{\varepsilon/4}\left(\mathcal{G},C(\mathbf{B}^{d})\right)\exp\left\\{-\frac{3m\varepsilon}{16(c+3)^{2}M^{2}}\right\\}.$

For every $f_{1},f_{2}\in\mathcal{H}_{L,{\bf z}}^{*}$ , we have

$\left|(f_{1}(x)-y)^{2}-(f_{2}(x)-y)^{2}\right|\leq(2c+2)M\|f_{1}-f_{2}\|.$

Thus, for any $\varepsilon>0$, a
$\left(\frac{\varepsilon}{2cM+2M}\right)$-covering of $\mathcal{H}^{*}_{L,{\bf
z}}$ provides an $\varepsilon$-covering of $\mathcal{G}$. This means

$\mathcal{N}_{\varepsilon/4}\left(\mathcal{G},C(\mathbf{B}^{d})\right)\leq\mathcal{N}_{\varepsilon/(8M+8cM)}\left(\mathcal{H}_{L,{\bf
z}}^{*},C(\mathbf{B}^{d})\right)$

By definition of $\mathcal{H}_{L,{\bf z}}^{*}$, we then deduce from [4,
Theorem 5.3] that

$\log\mathcal{N}_{\varepsilon/(8M+8cM)}\left(\mathcal{H}_{L,{\bf
z}}^{*},C(\mathbf{B}^{d})\right)\leq
Cn^{d}\log\left(\frac{32M+32cM}{\varepsilon}\right).$

Hence,

$\mathcal{N}_{\varepsilon/4}\left(\mathcal{G},C(\mathbf{B}^{d})\right)\leq\exp\left\\{Cn^{d}\log\left(\frac{32M+32cM}{\varepsilon}\right)\right\\},$

which together with (29) yields

$\mathcal{S}_{2}\leq\frac{1}{2}(\mathcal{E}(f_{\bf
z}^{*})-\mathcal{E}(f_{\rho}))+\varepsilon$ (30)

with confidence at least

$1-\exp\left\\{Cn^{d}\log\left(\frac{32M+32cM}{\varepsilon}\right)-\frac{3m\varepsilon}{16(c+3)^{2}M^{2}}\right\\}.$

This finishes the proof of Proposition 7. $\Box$

###  6.5 Learning rate analysis

Now we are in a position to deduce the final learning rate of $l^{q}$
regularization schemes (16). Firstly, it follows from Propositions 6 and 7
that

$\displaystyle\mathcal{E}(\pi_{M}f_{{\bf
z},\lambda,q})-\mathcal{E}(f_{\rho}))$ $\displaystyle\leq$
$\displaystyle\mathcal{D}({\bf
z},\lambda,q)+\mathcal{S}_{1}+\mathcal{S}_{2}\leq C\left(n^{-2r}+\lambda
m\right)$ $\displaystyle+$
$\displaystyle\frac{1}{2}(\mathcal{E}(\pi_{M}f_{{\bf
z},\lambda,q})-\mathcal{E}(f_{\rho}))+\varepsilon+\frac{1}{2}(\mathcal{E}(f_{\bf
z}^{*})-\mathcal{E}(f_{\rho}))+\varepsilon$

holds with confidence at least

$\displaystyle
1-2\exp\\{{-cm/n^{d}}\\}-\exp\left\\{cn^{d}\log\frac{Cn^{d+2}\max\\{m^{1-1/q},1\\}M^{\frac{2}{q_{0}}+1}}{\lambda^{1/q_{0}}\varepsilon}-\frac{3m\varepsilon}{128M^{2}}\right\\}$
$\displaystyle-$
$\displaystyle\exp\left\\{Cn^{d}\log\left(\frac{32M+32cM}{\varepsilon}\right)-\frac{3m\varepsilon}{16(c+3)^{2}M^{2}}\right\\}.$

Then, by setting $\varepsilon\geq\varepsilon_{m}^{+}\geq C(m/\log
m)^{-2r/(2r+d)}$, $n=\left[c_{0}\varepsilon^{-1/(2r)}\right]$ and
$\lambda=m^{-1}\varepsilon$, it follows from $r>d/2$ that

$\displaystyle
1-2\exp\\{-Cm\varepsilon^{d/(2r)}\\}-\exp\left\\{C\varepsilon^{-d/(2r)}\log\frac{1}{\varepsilon}-3m\varepsilon/(16(c+3)^{2}M^{2})\right\\}$
$\displaystyle-$ $\displaystyle\exp\left\\{C\varepsilon^{-d/(2r)}\left(\log
1/\varepsilon+\log\lambda^{-1/q_{0}}\right)-3m\varepsilon/(128M^{2})\right\\}$
$\displaystyle\geq$ $\displaystyle
1-2\exp\\{-Cm\varepsilon\\}-\exp\left\\{C\varepsilon^{-d/(2r)}\log
m-3m\varepsilon/(16(c+3)^{2}M^{2})\right\\}$ $\displaystyle-$
$\displaystyle\exp\left\\{C\varepsilon^{-d/(2r)}\log
m-3m\varepsilon/(128M^{2})\right\\}$ $\displaystyle\geq$ $\displaystyle
1-\exp\\{-Cm\varepsilon\\}.$

That is, for $\varepsilon\geq\varepsilon^{+}$

$\mathcal{E}(\pi_{M}f_{{\bf z},\lambda,q})-\mathcal{E}(f_{\rho})\leq
6\varepsilon$

holds with confidence at least $1-\exp\\{-Cm\varepsilon\\}$.

The lower bound can be more easily deduced. Actually, it follows from [10,
Equation (3.27)] (see also [17]) that for any estimator $f_{\bf
z}\in\Phi_{m}$, there holds

$\sup_{f_{\rho}\in W_{2}^{r}}P_{m}\\{{\bf z}:\|f_{\bf
z}-f_{\rho}\|_{\rho}^{2}\geq\varepsilon\\}\geq\left\\{\begin{array}[]{cc}\varepsilon_{0},&\varepsilon<\varepsilon^{-},\\\
e^{-cm\varepsilon},&\varepsilon\geq\varepsilon^{-},\end{array}\right.$

where $\varepsilon_{0}=\frac{1}{2}$ and $\varepsilon^{-}=cm^{-2r/(2r+d)}$ for
some universal constant $c$. With this, the proof of Theorem 1 is completed.

##  7 Further discussion and conclusion

In studies and applications, regularization is a fundamental skill to improve
on performance of a learning machine. The $l^{q}$ regularization schemes (1)
with $0<q<\infty$ are well known to be central in use. In this paper, we have
studied the dependency problem of the generalization capability of $l^{q}$
regularization with the choice of $q$. Through formulating a new methodology
of estimation of generalization error, we have shown that there is at least a
positive definite kernel, say, $L_{2n}$, such that associated with such a
kernel, the learning rate of the $l^{q}$ regularization schemes is independent
of the choice of $q$. (To be more precise, we verified that with the kernel
$L_{2n}$, all $l^{q}$ regularization schemes (1) can attain the same almost
optimal learning rate in the following sense: up to a logarithmic factor, the
upper and lower bounds of generalization error of the $l^{q}$ regularization
schemes are asymptotically identical). This implies that for some kernels, the
generalization capability of $l^{q}$ regularization may not depend on $q$.
Therefore, as far as the generalization capability is concerned, for those
kernels, the choice of $q$ is not important, which then relaxes the model
selection difficulty in applications. The problem is, however, far
complicated. We have also illustrated in Section 2 that there exists a kernel
with which the generalization capability of $l^{q}$ regularization heavily
depends on the choice of $q$. Thus, answering completely whether or not the
choice of $q$ affects the generalization of $l^{q}$ regularization is by no
means easy and completed.

Though we have constructed a concrete kernel example, the localized polynomial
kernel $L_{2n}$, with which implementing the $l^{q}$ regularization in SDHS
can realize the almost optimal learning rate, and this is independence of the
choice of $q$, we have not provided a practically feasible algorithm to
implement the learning with the almost optimal generalization capability. This
is because the kernel $L_{2n}$ we have constructed is not easily computed in
practice, even though we can use the cubature formula (Lemma 2) to discretize
it. Thus, seeking the kernels that possesses the similar property as that of
$L_{2n}$ and can be implemented easily deserve study. This is under our
current investigation.

## Appendix A: Proof of Lemma 3

To prove Lemma 3, we need the following Aronszajn Theorem (see [1]).

######  Lemma 11.

Let $\mathcal{H}$ be a separable Hilbert space of functions over $X$ with
orthonormal basis $\\{\phi_{k}\\}_{k=0}^{\infty}$. $\mathcal{H}$ is a
reproducing kernel Hilbert space if and only if

$\sum_{k=0}^{\infty}|\phi_{k}(x)|^{2}<\infty$

for all $x\in X$. The unique reproducing kernel $K$ is defined by

$K(x,y):=\sum_{k=0}^{\infty}\phi_{k}(x)\phi_{k}(y).$

Proof of Lemma 3. Since

$\\{P_{k,j,i}:k=0,\dots,n,j=k,k-2,\dots,\varepsilon_{k},i=1,2,\dots,D_{j}^{d-1}\\}$

is an orthonormal basis for $\mathcal{P}_{n}$, for arbitrary
$P\in\mathcal{P}_{n}$, there exists a set of real numbers $a_{k,j,i}$ such
that

$P(x)=\sum_{k=0}^{n}\sum_{j}\sum_{i=1}^{D_{j}^{d-1}}a_{k,j,i}P_{k,j,i}(x),$

where the summation concerning the index $j$ is $k,k-2,\dots,\varepsilon_{k}$.
On the other hand, it follows from (8) that

$\displaystyle\sum_{j}\sum_{i=1}^{D_{j}^{d-1}}P_{k,j,i}(x)P_{k,j,i}(y)$
$\displaystyle=$
$\displaystyle\sum_{j}\sum_{i=1}^{D_{j}^{d-1}}v_{k}^{2}\int_{\mathbf{S}^{d-1}}Y_{j,i}(\xi)U_{k}(x\cdot\xi)d\omega_{d-1}(\xi)\int_{\mathbf{S}^{d-1}}Y_{j,i}(\eta)U_{k}(y\cdot\eta)d\omega_{d-1}(\eta)$
$\displaystyle=$ $\displaystyle
v_{k}^{2}\sum_{j}\int_{\mathbf{S}^{d-1}}U_{k}(x\cdot\xi)\int_{\mathbf{S}^{d-1}}U_{k}(y\cdot\eta)\sum_{i=1}^{D_{j}^{d-1}}Y_{j,i}(\xi)Y_{j,i}(\eta)d\omega(\xi)d\omega_{d-1}(\eta).$

Thus, the addition formula (7) yields

$\sum_{j}\sum_{i=1}^{D_{j}^{d-1}}P_{k,j,i}(x)P_{k,j,i}(y)=v_{k}^{2}\sum_{j}\int_{\mathbf{S}^{d-1}}U_{k}(x\cdot\xi)\int_{\mathbf{S}^{d-1}}U_{k}(y\cdot\eta)K^{*}_{j}(\xi\cdot\eta)d\omega_{d-1}(\xi)d\omega_{d-1}(\eta).$

The above equality together with (5) and (6) implies

$\displaystyle\sum_{j}\sum_{i=1}^{D_{j}^{d-1}}P_{k,j,i}(x)P_{k,j,i}(y)$
$\displaystyle=$ $\displaystyle
v_{k}^{2}\int_{\mathbf{S}^{d-1}}U_{k}(x\cdot\xi)\int_{\mathbf{S}^{d-1}}U_{k}(y\cdot\eta)\sum_{j}K_{j}^{*}(\xi\cdot\eta)d\omega_{d-1}(\xi)d\omega_{d-1}(\eta)$
$\displaystyle=$
$\displaystyle\frac{v_{k}^{4}}{U_{k}(1)}\int_{\mathbf{S}^{d-1}}U_{k}(x\cdot\xi)\int_{\mathbf{S}^{d-1}}U_{k}(y\cdot\eta)U_{k}(\xi\cdot\eta)d\omega_{d-1}(\xi)d\omega_{d-1}(\eta)$
$\displaystyle=$ $\displaystyle v_{k}^{2}\int_{\mathbf{S}^{d-1}}U_{k}(\xi\cdot
x)U_{k}(\xi\cdot y)d\omega_{d-1}(\xi).$

Therefore, there holds

$K_{n}(x,y)=\sum_{k=0}^{\infty}\sum_{j}\sum_{i=1}^{D_{j}^{d-1}}P_{k,j,i}(x)P_{k,j,i}(y).$

The above equality together with Lemma 11 yields Lemma 3.

## References

  * [1] N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc., 68 (1950), 337-404.
  * [2] G. Brown, F. Dai, Approximation of smooth functions on compact two-point homogeneous spaces, J. Funct. Anal., 220 (2005), 401-423.
  * [3] F. Cucker, S. Smale, On the mathematical foundations of learning, Bull. Amer. Math. Soc.,39 (2001), 1-49.
  * [4] F. Cucker, D. X. Zhou, Learning Theory: An Approximation Theory Viewpoint, Cambridge University Press, 2007.
  * [5] F. Dai, Multivariate polynomial inequalities with respect to doubling weights and $A_{\infty}$ weights, J. Funct. Anal., 235 (2006), 137-170.
  * [6] F. Dai, H. P. Wang, Optimal cubature formulas in weighted Besov spaces with $A_{\infty}$ weights on multivariate domains, Constr. Approx., 37 (2013), 167-194.
  * [7] I. Daubechies., Ten Lectures on Wavelets, SIAM, Philadelphia, 1992.
  * [8] I. Daubechies, R. A. Devore, M. Fornasier, C. Güntürk, Iteratively re-weighted least squares minimization for sparse recovery, Commun. Pure Appl. Math., 63 (2010), 1-38.
  * [9] R. A. DeVore, G. G. Lorentz, Constructive Approximation, Springer-Verlag, 1993.
  * [10] R. A. Devore, G. Kerkyacharian, D. Picard, V. Temlyakov, Approximation methods for supervised learning, Found. Comput. Math., 6 (2006), 3-58.
  * [11] Y. L. Feng, S. G. Lv, Unified approach to coefficient-based regularized regression, Comput. Math. Appl., 62 (2011), 506-515.
  * [12] G. Kerkyacharian, T. Ngoc, D. Picard, Localized spherical deconvolution, Ann. Statist., 39 (2011), 1042-1068.
  * [13] V. Maiorov, J. Ratsaby, On the degree of approximation by manifolds of finite pseudo-dimension, Constr. Approx., 15 (1999), 291-300.
  * [14] V. Maiorov, R. Meir, Lower bounds for multivariate approximation by affine-invariant dictionaries, IEEE Trans. Inform. Theory, 47 (2001), 1569-1575.
  * [15] V. Maiorov, On best approximation of classes by radial functions, J. Approx. Theory, 120 (2003), 36-70.
  * [16] V. Maiorov, Pseudo-dimension and entropy of manifolds formed by affine invariant dictionary, Adv. Comput. Math., 25 (2006), 435-450.
  * [17] V. Maiorov, Approximation by neural networks and learning theory, J. Complex., 22 (2006), 102-117.
  * [18] S. Mendelson, R. Vershinin, Entropy and the combinatorial dimension, Invent. Math., 125 (2003), 37-55.
  * [19] H. N. Mhaskar, F. J. Narcowich, J. D. Ward, Spherical Marcinkiewicz-Zygmund inequalities and positive quadrature, Math. Comput., 70 (2000), 1113-1130.
  * [20] C. Müller, Spherical Harmonics. Lecture Notes in Mathematics 17, Springer, 1966.
  * [21] P. P. Petrushev, Approximation by ridge functions and neural networks, SIAM J. Math. Anal., 30 (1999), 155-189.
  * [22] P. P. Petrushev, Y. Xu, Localized polynomial frames on the ball, Constr. Approx., 27 (2008), 121-148.
  * [23] B. Schölkopf, A. J. Smola, Learning with Kernel: Support Vector Machine, Regularization, Optimization, and Beyond (Adaptive Computation and Machine Learning), MIT Press, 2001.
  * [24] L. Shi, Y. L. Feng, D. X. Zhou, Concentration estimates for learning with $l^{1}$-regularizer and data dependent hypothesis spaces, Appl. Comput. Harmon. Anal., 31 (2011), 286-302.
  * [25] G. Song, H. Z. Zhang, F. J. Hickernell, Reproducing kernel Banach spaces with the $l^{1}$ norm, Appl. Comput. Harmon. Anal., 34 (2013), 96-116.
  * [26] G. Song, H. Z. Zhang, Reproducing kernel Banach spaces with the $l^{1}$ norm II: error analysis for regularized least square regression, Neural Comput., 23 (2011), 2713-2729.
  * [27] I. Steinwart and A. Christmann. Support Vector Machines. Springer, New York, 2008.
  * [28] H. W. Sun, Q. Wu, Least square regression with indefinite kernels and coefficient regularization, Appl. Comput. Harmon. Anal., 30 (2011), 96-109.
  * [29] R. Tibshirani, Regression shrinkage and selection via the LASSO, J. ROY. Statist. Soc. Ser. B, 58 (1995), 267-288.
  * [30] H. Tong, D. R. Chen, F. Yang, Least square regression with $l^{p}$-coefficient regularization, Neural Comput., 22 (2010), 3221-3235.
  * [31] K. Y. Wang, L. Q. Li, Harmonic Analysis and Approximation on The Unit Sphere, Science Press, 2000.
  * [32] W. Wu, Y. M. Ying, D. X. Zhou, Learning rates of least square regularized regression, Found. Comput. Math., 6 (2006), 171-192.
  * [33] Q. Wu, D. X. Zhou, Learning with sample dependent hypothesis space, Comput. Math. Appl., 56 (2008), 2896-2907.
  * [34] Q. Xiao, D. X. Zhou, Learning by nonsymmetric kernel with data dependent spaces and $l^{1}$-regularizer, Taiwanese J. Math., 14 (2010), 1821-1836.
  * [35] Y. Xu, Orthogonal polynomials and cubature formula on spheres and on balls, SIAM J. Math. Anal., 29 (1998), 779-793.
  * [36] H. Z. Zhang, Y. S. Xu, J. Zhang, Reproducing kernel Banach spaces for Machine learning, J. Mach. Learn. Res., 10 (2009), 2741-2775.
  * [37] D. X. Zhou, K. Jetter, Approximation with polynomial kernels and SVM classifiers, Adv. Comput. Math., 25 (2006), 323-344.