Unified approach to coefficient-based regularized regression.

*(English)*Zbl 1228.62044Summary: We consider the coefficient-based regularized least-squares regression problem with the \(l^{q}\)-regularizer (\(1\leq q\leq 2\)) and data dependent hypothesis spaces. Algorithms for data dependent hypothesis spaces perform well with the property of flexibility. We conduct a unified error analysis by a stepping stone technique. An empirical covering number technique is also employed in our study to improve sample errors. Comparing with existing results, we make a few improvements: First, we obtain a significantly sharper learning rate that can be arbitrarily close to \(O(m^{ - 1})\) under reasonable conditions, which is regarded as the best learning rate in learning theory. Second, our results cover the case \(q=1\), which is novel. Finally, our results hold under very general conditions.

##### Keywords:

data dependent hypothesis spaces; \(l^{q}\)-regularizer; \(\ell ^{2}\)-empirical covering number; learning rates
PDF
BibTeX
XML
Cite

\textit{Y.-L. Feng} and \textit{S.-G. Lv}, Comput. Math. Appl. 62, No. 1, 506--515 (2011; Zbl 1228.62044)

Full Text:
DOI

##### References:

[1] | Aronszajn, N., Theory of reproducing kernels, Trans. amer. math. soc., 68, 337-404, (1950) · Zbl 0037.20701 |

[2] | Bartlett, P.L., The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network, IEEE trans. inform. theory, 44, 525-536, (2002) · Zbl 0901.68177 |

[3] | Wu, Q.; Zhou, D.X., Learning with sample dependent hypothesis spaces, Comput. math. appl., 56, 2896-2907, (2008) · Zbl 1165.68388 |

[4] | I. Steinwart, D. Hush, C. Scovel, Optimal rates for regularized least square regression, in: Proceedings of the 22nd Annual Conference on Learning Theory, 2009, pp. 79-93. |

[5] | Sun, H.W.; Wu, Q., Least square regression with indefinite kernels and coefficient regularization, Appl. comput. harmon. anal., 30, 96-109, (2011) · Zbl 1225.65015 |

[6] | Xiao, Q.W.; Zhou, D.X., Learning by nonsymmetric kernels with data dependent spaces and \(l^1\)-regularizer, Taiwanese J. math., 14, 1821-1836, (2010) · Zbl 1221.68204 |

[7] | Donoho, D., For most large undetermined systems of linear equations the minimal \(l^1\)-norm solution is the sparsest solution, Comm. pure appl. math., 59, 797-829, (2006) · Zbl 1113.15004 |

[8] | Tong, H.Z.; Chen, D.R.; Yang, F.H., Least square regression with \(l^p\)-coefficient regularization, Neural comput., 38, 526-565, (2010) |

[9] | Wu, Q.; Zhou, D.X., SVM soft margin classifier: linear programming versus quadratic programming, Neural comput., 15, 1397-1437, (2003) |

[10] | Smale, S.; Zhou, D.X., Estimating the approximation error in learning theory, Anal. appl., 1, 17-41, (2003) · Zbl 1079.68089 |

[11] | Cucker, F.; Zhou, D.X., Learning theory: an approximation theory viewpoint, (2007), Cambridge University Press · Zbl 1274.41001 |

[12] | Smale, S.; Zhou, D.X., Shannon sampling II: connection to learning theory, Appl. comput. harmon. anal., 19, 285-302, (2005) · Zbl 1107.94008 |

[13] | Wu, Q.; Ying, Y.M.; Zhou, D.X., Learning rates of least-square regularized regression, Found. comput. math., 6, 171-192, (2006) · Zbl 1100.68100 |

[14] | Wu, Q.; Ying, Y.M.; Zhou, D.X., Multi-kernel regularized classifiers, J. complexity, 23, 108-134, (2007) · Zbl 1171.65043 |

[15] | Zhou, D.X., The covering number in learning theory, J. complexity, 18, 739-767, (2002) · Zbl 1016.68044 |

[16] | Pontil, M., A note on different covering numbers in learning theory, J. complexity, 19, 665-671, (2003) · Zbl 1057.68044 |

[17] | Zhou, D.X., Capacity of reproducing kernel spaces in learning theory, IEEE trans. inform. theory, 49, 1743-1752, (2003) · Zbl 1290.62033 |

[18] | Z.C. Guo, D.X. Zhou, Concentration estimates for learning with unbounded sampling (submitted for publication). · Zbl 1283.68289 |

[19] | Wu, Z.M., Compactly supported positive definite radial functions, Adv. comput. math., 4, 283-292, (1995) · Zbl 0837.41016 |

[20] | Y.L. Feng, Regularized least-squares regression with dependent samples and \(q\)-penalty, Appl. Anal. (in press). · Zbl 1271.68203 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.