Regularization for regression and ranking

Abstract

Regularization is a method for learning and approximation which uses some additional information to avoid overfitting in statistics and machine learning. The information usually aims at improving the generalization ability by restrictions on regularity of potential functions. In this thesis, we mainly focus on the elastic net for regression and regularized least squares ranking algorithms. The elastic net regularization is analyzed in two settings, according to their hypothesis spaces. One assumes a data independent hypothesis space composed by features independent of samples. Within this setting, significant contributions are made in several aspects. First, concentration estimates for sample error are presented by introducing ℓ2-empirical covering number and utilizing an iteration process. Second, a constructive approximation approach for estimating approximation error is presented. Third, the elastic-net learning with infinite features is studied and the role that the tuning parameter ζ plays is also discussed. Finally, our learning rate is shown to be faster compared with existing results. The other assumes a data dependent hypothesis space which is a subspace of a Reproducing Kernel Hilbert Space. Based on the capacity condition of the Reproducing Kernel Hilbert Space, a learning rate for elastic net is obtained by a stepping stone technique and an ℓ2-empirical covering number technique. The role of parameters is also discussed. The regularized least squares ranking algorithm is analyzed in Reproducing Kernel Hilbert Spaces. By Hoeffding's decomposition, a U-statistic could be decomposed into an independent term and a degenerate U-statistic term. These two terms can be analyzed individually. The optimal learning rate is achieved.

Date of Award	15 Jul 2013
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Dingxuan ZHOU (Supervisor)