Combinatorial Penalties: Which structures are preserved by convex relaxations?
We consider the homogeneous and the non-homogeneous convex relaxations for combinatorial penalty functions defined on support sets. Our study identifies key differences in the tightness of the resulting relaxations through the notion of the lower combinatorial envelope of a set-function along with new necessary conditions for support identification. We then propose a general adaptive estimator for convex monotone regularizers, and derive new sufficient conditions for support recovery in the asymptotic setting.
AISTATS_2018_structure.pdf
Publisher's version
openaccess
659.27 KB
Adobe PDF
06ce7113ccd123aada5ad1ff56ef39a3
structure-preprint.pdf
Preprint
openaccess
9.27 MB
Adobe PDF
84b18d56b70482f28d9cf6452e2e2ba2