Combinatorial Penalties: Which structures are preserved by convex relaxations?

Marwa El Halabi, Francis Bach, Volkan Cevher

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 tigh…