Minimizing Nonconvex Non-Separable Functions

Yaoliang Yu, Xun Zheng, Micol Marchetti-Bowick, Eric Xing
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:1107-1115, 2015.

Abstract

Regularization has played a key role in deriving sensible estimators in high dimensional statistical inference. A substantial amount of recent works has argued for nonconvex regularizers in favor of their superior theoretical properties and excellent practical performances. In a different but analogous vein, nonconvex loss functions are promoted because of their robustness against "outliers". However, these nonconvex formulations are computationally more challenging, especially in the presence of nonsmoothness and non-separability. To address this issue, we propose a new proximal gradient meta-algorithm by rigorously extending the proximal average to the nonconvex setting. We formally prove its nice convergence properties, and illustrate its effectiveness on two applications: multi-task graph-guided fused lasso and robust support vector machines. Experiments demonstrate that our method compares favorably against other alternatives.

Cite this Paper

BibTeX
@InProceedings{pmlr-v38-yu15, title = {{Minimizing Nonconvex Non-Separable Functions}}, author = {Yu, Yaoliang and Zheng, Xun and Marchetti-Bowick, Micol and Xing, Eric}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {1107--1115}, year = {2015}, editor = {Lebanon, Guy and Vishwanathan, S. V. N.}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/yu15.pdf}, url = {https://proceedings.mlr.press/v38/yu15.html}, abstract = {Regularization has played a key role in deriving sensible estimators in high dimensional statistical inference. A substantial amount of recent works has argued for nonconvex regularizers in favor of their superior theoretical properties and excellent practical performances. In a different but analogous vein, nonconvex loss functions are promoted because of their robustness against "outliers". However, these nonconvex formulations are computationally more challenging, especially in the presence of nonsmoothness and non-separability. To address this issue, we propose a new proximal gradient meta-algorithm by rigorously extending the proximal average to the nonconvex setting. We formally prove its nice convergence properties, and illustrate its effectiveness on two applications: multi-task graph-guided fused lasso and robust support vector machines. Experiments demonstrate that our method compares favorably against other alternatives.} }
Endnote
%0 Conference Paper %T Minimizing Nonconvex Non-Separable Functions %A Yaoliang Yu %A Xun Zheng %A Micol Marchetti-Bowick %A Eric Xing %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-yu15 %I PMLR %P 1107--1115 %U https://proceedings.mlr.press/v38/yu15.html %V 38 %X Regularization has played a key role in deriving sensible estimators in high dimensional statistical inference. A substantial amount of recent works has argued for nonconvex regularizers in favor of their superior theoretical properties and excellent practical performances. In a different but analogous vein, nonconvex loss functions are promoted because of their robustness against "outliers". However, these nonconvex formulations are computationally more challenging, especially in the presence of nonsmoothness and non-separability. To address this issue, we propose a new proximal gradient meta-algorithm by rigorously extending the proximal average to the nonconvex setting. We formally prove its nice convergence properties, and illustrate its effectiveness on two applications: multi-task graph-guided fused lasso and robust support vector machines. Experiments demonstrate that our method compares favorably against other alternatives.
RIS
TY - CPAPER TI - Minimizing Nonconvex Non-Separable Functions AU - Yaoliang Yu AU - Xun Zheng AU - Micol Marchetti-Bowick AU - Eric Xing BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-yu15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 1107 EP - 1115 L1 - http://proceedings.mlr.press/v38/yu15.pdf UR - https://proceedings.mlr.press/v38/yu15.html AB - Regularization has played a key role in deriving sensible estimators in high dimensional statistical inference. A substantial amount of recent works has argued for nonconvex regularizers in favor of their superior theoretical properties and excellent practical performances. In a different but analogous vein, nonconvex loss functions are promoted because of their robustness against "outliers". However, these nonconvex formulations are computationally more challenging, especially in the presence of nonsmoothness and non-separability. To address this issue, we propose a new proximal gradient meta-algorithm by rigorously extending the proximal average to the nonconvex setting. We formally prove its nice convergence properties, and illustrate its effectiveness on two applications: multi-task graph-guided fused lasso and robust support vector machines. Experiments demonstrate that our method compares favorably against other alternatives. ER -
APA
Yu, Y., Zheng, X., Marchetti-Bowick, M. & Xing, E.. (2015). Minimizing Nonconvex Non-Separable Functions. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:1107-1115 Available from https://proceedings.mlr.press/v38/yu15.html.

Related Material