Convergence Rate for $l^{q}$ -Coefficient Regularized Regression With Non-i.i.d. Sampling

Many learning algorithms use hypothesis spaces which are trained from samples, but little theoretical work has been devoted to the study of these algorithms. In this paper, we show that mathematical analysis for the kernel-based coefficient least squares for regression with $l^{q}$ -regularizer, $1\leq q\leq 2$ , which is essentially different from that for algorithms with hypothesis spaces independent of the sample or depending only on the sample size. The error analysis was carried out under the assumption that the samples are drawn from a non-identical sequence of probability measures and satisfy the $\beta $ -mixing condition. We use the drift error analysis and the independent-blocks technique to deal with the non-identical and dependent setting, respectively. When the sequence of marginal distributions converges exponentially fast in the dual of a Hölder space and the sampling process satisfies polynomially $\beta $ -mixing, we obtain the capacity dependent error bounds of the algorithm. As a byproduct, we derive a significantly faster learning rate that can be arbitrarily close to the best rate $O(m^{-1})$ for the independent and identical samples.