Combinatorial Penalties: Which structures are preserved by convex relaxations?

Marwa El Halabi, Francis Bach, Volkan Cevher
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1551-1560, 2018.

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 this Paper

BibTeX
@InProceedings{pmlr-v84-el-halabi18a, title = {Combinatorial Penalties: Which structures are preserved by convex relaxations?}, author = {El Halabi, Marwa and Bach, Francis and Cevher, Volkan}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {1551--1560}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/el-halabi18a/el-halabi18a.pdf}, url = {https://proceedings.mlr.press/v84/el-halabi18a.html}, 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. } }
Endnote
%0 Conference Paper %T Combinatorial Penalties: Which structures are preserved by convex relaxations? %A Marwa El Halabi %A Francis Bach %A Volkan Cevher %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-el-halabi18a %I PMLR %P 1551--1560 %U https://proceedings.mlr.press/v84/el-halabi18a.html %V 84 %X 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.
APA
El Halabi, M., Bach, F. & Cevher, V.. (2018). Combinatorial Penalties: Which structures are preserved by convex relaxations?. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:1551-1560 Available from https://proceedings.mlr.press/v84/el-halabi18a.html.

Related Material