New Computational and Statistical Aspects of Regularized Regression with
  Application to Rare 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.
