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 [1]}
can be applied to derive the approximation error. To bound the
sample error, we will use a different method from the tranditional
approaches [2]}, [3]}. 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 [2]} twice.
Then the relation between the so-called Pseudo-dimension and
covering number [6]} yields the sample error
estimate for \(l^q\)  regularization schemes (REF ) 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.
