New Perspectives on k-Support and Cluster Norms

The norm is obtained by taking an infimum of certain quadratic functions, which are parameterized by a set Θ . By varying the set, the regularizer can be tailored to assumptions on the underlying model, which should lead to more accurate learning. The norm is defined for w R d, as ‖ w ‖ Θ inf θ Θ d i 1 w 2 i θ i (1) where Θ is a convex bounded subset of the positive orthant. This family is sufficiently rich to encompasses standard regularizers such as the p norms [Micchelli and Pontil, 2005] for p [1, 2], the group Lasso Y uan and Lin [2006], Group Lasso with Overlap [Jacob et al., 2009b], the norm in [Jacob et al., 2009a], and the structured sparsity norms of [Micchelli et al., 2013]. Our work builds upon a recent line of papers which considered convex regularizers defined as an infimum problem over a parametric family of quadratics, as well as related infimal convolution problems [see Jacob et al., 2009b, Maurer and Pontil, 2012, Obozinski and Bach, 2012, and references therein].