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.
Cite
Text
El Halabi et al. "Combinatorial Penalties: Which Structures Are Preserved by Convex Relaxations?." International Conference on Artificial Intelligence and Statistics, 2018.Markdown
[El Halabi et al. "Combinatorial Penalties: Which Structures Are Preserved by Convex Relaxations?." International Conference on Artificial Intelligence and Statistics, 2018.](https://mlanthology.org/aistats/2018/halabi2018aistats-combinatorial/)BibTeX
@inproceedings{halabi2018aistats-combinatorial,
title = {{Combinatorial Penalties: Which Structures Are Preserved by Convex Relaxations?}},
author = {El Halabi, Marwa and Bach, Francis R. and Cevher, Volkan},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2018},
pages = {1551-1560},
url = {https://mlanthology.org/aistats/2018/halabi2018aistats-combinatorial/}
}