New Computational and Statistical Aspects of Regularized Regression with Application to Rare Feature Selection and Aggregation
This work addresses a challenge in high-dimensional statistics and machine learning for researchers dealing with rare features, though it appears incremental as it builds on existing norm-based regularization methods.
The authors tackled the problem of regularized regression with rare features by developing a unified computational framework for norms that promote structured models, resulting in statistical bounds for automatic feature selection and aggregation.
Prior knowledge on properties of a target model often come as discrete or combinatorial descriptions. This work provides a unified computational framework for defining norms that promote such structures. More specifically, we develop associated tools for optimization involving such norms given only the orthogonal projection oracle onto the non-convex set of desired models. As an example, we study a norm, which we term the doubly-sparse norm, for promoting vectors with few nonzero entries taking only a few distinct values. We further discuss how the K-means algorithm can serve as the underlying projection oracle in this case and how it can be efficiently represented as a quadratically constrained quadratic program. Our motivation for the study of this norm is regularized regression in the presence of rare features which poses a challenge to various methods within high-dimensional statistics, and in machine learning in general. The proposed estimation procedure is designed to perform automatic feature selection and aggregation for which we develop statistical bounds. The bounds are general and offer a statistical framework for norm-based regularization. The bounds rely on novel geometric quantities on which we attempt to elaborate as well.