Combinatorial Penalties: Which structures are preserved by convex relaxations?

Abstract

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.

Cited by in corpus (4)

• Only Train Once: A One-Shot Neural Network Training And Pruning Framework
• Non-submodular Function Maximization subject to a Matroid Constraint, with Applications
• Half-Space Proximal Stochastic Gradient Method for Group-Sparsity Regularized Problem
• Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets