Abstract
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.
Introduction
Regularized regression is a cornerstone of high-dimensional statistics, typically used to identify a small subset of relevant features from a large pool ($p \gg n$). While the Lasso ($\ell_1$ regularization) is effective for simple sparsity, it often falls short when dealing with "rare features"—variables that appear infrequently in the data. In domains like genomics or natural language processing, these rare features may individually lack sufficient signal for accurate estimation but may share similar underlying effects.
Jalali, Javanmard, and Fazel propose a framework that moves beyond simple sparsity to "doubly-sparse" models. These models perform feature selection and aggregation simultaneously, pooling signal from multiple rare features to improve estimation accuracy.
The Doubly-Sparse Norm
The core contribution is the doubly-sparse norm ($||\cdot||_{k \square d}$), designed to promote vectors that are both sparse and have clustered coefficient values. Specifically, it targets vectors with at most $k$ non-zero entries that take at most $d$ distinct values.
By forcing coefficients to share values, the model effectively increases the "sample size" for those coefficients, which is particularly beneficial for rare features.
Computational Framework and Projection Oracles
To make optimization with such structured norms tractable, the authors develop a unified framework based on orthogonal projection oracles. They demonstrate that projecting onto the set of $d$-valued vectors is equivalent to a 1D K-means clustering problem.
Furthermore, they show that this projection can be represented as a Quadratically Constrained Quadratic Program (QCQP). This representation allows the structured norm to be integrated into standard proximal gradient algorithms, bridging the gap between discrete combinatorial structures and continuous convex optimization.
Statistical Guarantees and the Relative Diameter
A significant theoretical hurdle in regularized regression is that many standard proofs rely on "decomposability," a property shared by the Lasso and nuclear norms but not necessarily by more complex structured norms.
The authors introduce a new geometric quantity called the relative diameter ($\phi$). This measure of model complexity allows for the derivation of statistical error bounds for any norm-based regularizer, regardless of decomposability. The relative diameter accounts for the global structure of the norm ball, providing a more faithful tracking of true model complexity than local measures like tangent cone width.
Results and Discussion
Theoretical analysis shows that when the underlying model is indeed doubly-sparse, the proposed estimator achieves prediction error bounds significantly tighter than the Lasso. The gain is proportional to the ratio between the number of non-zeros ($k$) and the number of distinct values ($d$). Synthetic simulations confirm that the relative diameter accurately tracks error across various regimes of model complexity.
Despite these gains, challenges remain. The QCQP formulation, while a breakthrough for representability, is computationally more intensive than simple soft-thresholding. Future work may focus on scaling these methods to massive datasets and developing automated techniques for tuning the hyperparameters $k$ and $d$. Additionally, extending the statistical bounds to handle heavy-tailed noise or model misspecification remains an open area of research.
Summary updated