# Combinatorial Penalties: Which structures are preserved by convex relaxations?

arXiv: https://arxiv.org/abs/1710.06273 · HTML: https://mlsanity.com/paper/1710.06273/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2017.

## Built on by (most cited first, 6 of 6)

- [Only Train Once: A One-Shot Neural Network Training And Pruning Framework](https://mlsanity.com/paper/2107.07467/) (2021)
- [Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions](https://mlsanity.com/paper/2208.04055/) (2022)
- [Maximizing approximately k-submodular functions](https://mlsanity.com/paper/2101.07157/) (2021)
- [Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2205.07217/) (2022)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)

## Abstract (arXiv)

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.