Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity

Quanming Yao, James Kwok
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2645-2654, 2016.

Abstract

The use of convex regularizers allow for easy optimization, though they often produce biased estimation and inferior prediction performance. Recently, nonconvex regularizers have attracted a lot of attention and outperformed convex ones. However, the resultant optimization problem is much harder. In this paper, for a large class of nonconvex regularizers, we propose to move the nonconvexity from the regularizer to the loss. The nonconvex regularizer is then transformed to a familiar convex regularizer, while the resultant loss function can still be guaranteed to be smooth. Learning with the convexified regularizer can be performed by existing efficient algorithms originally designed for convex regularizers (such as the standard proximal algorithm and Frank-Wolfe algorithm). Moreover, it can be shown that critical points of the transformed problem are also critical points of the original problem. Extensive experiments on a number of nonconvex regularization problems show that the proposed procedure is much faster than the state-of-the-art nonconvex solvers.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-yao16, title = {Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity}, author = {Yao, Quanming and Kwok, James}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2645--2654}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/yao16.pdf}, url = {https://proceedings.mlr.press/v48/yao16.html}, abstract = {The use of convex regularizers allow for easy optimization, though they often produce biased estimation and inferior prediction performance. Recently, nonconvex regularizers have attracted a lot of attention and outperformed convex ones. However, the resultant optimization problem is much harder. In this paper, for a large class of nonconvex regularizers, we propose to move the nonconvexity from the regularizer to the loss. The nonconvex regularizer is then transformed to a familiar convex regularizer, while the resultant loss function can still be guaranteed to be smooth. Learning with the convexified regularizer can be performed by existing efficient algorithms originally designed for convex regularizers (such as the standard proximal algorithm and Frank-Wolfe algorithm). Moreover, it can be shown that critical points of the transformed problem are also critical points of the original problem. Extensive experiments on a number of nonconvex regularization problems show that the proposed procedure is much faster than the state-of-the-art nonconvex solvers.} }
Endnote
%0 Conference Paper %T Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity %A Quanming Yao %A James Kwok %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-yao16 %I PMLR %P 2645--2654 %U https://proceedings.mlr.press/v48/yao16.html %V 48 %X The use of convex regularizers allow for easy optimization, though they often produce biased estimation and inferior prediction performance. Recently, nonconvex regularizers have attracted a lot of attention and outperformed convex ones. However, the resultant optimization problem is much harder. In this paper, for a large class of nonconvex regularizers, we propose to move the nonconvexity from the regularizer to the loss. The nonconvex regularizer is then transformed to a familiar convex regularizer, while the resultant loss function can still be guaranteed to be smooth. Learning with the convexified regularizer can be performed by existing efficient algorithms originally designed for convex regularizers (such as the standard proximal algorithm and Frank-Wolfe algorithm). Moreover, it can be shown that critical points of the transformed problem are also critical points of the original problem. Extensive experiments on a number of nonconvex regularization problems show that the proposed procedure is much faster than the state-of-the-art nonconvex solvers.
RIS
TY - CPAPER TI - Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity AU - Quanming Yao AU - James Kwok BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-yao16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2645 EP - 2654 L1 - http://proceedings.mlr.press/v48/yao16.pdf UR - https://proceedings.mlr.press/v48/yao16.html AB - The use of convex regularizers allow for easy optimization, though they often produce biased estimation and inferior prediction performance. Recently, nonconvex regularizers have attracted a lot of attention and outperformed convex ones. However, the resultant optimization problem is much harder. In this paper, for a large class of nonconvex regularizers, we propose to move the nonconvexity from the regularizer to the loss. The nonconvex regularizer is then transformed to a familiar convex regularizer, while the resultant loss function can still be guaranteed to be smooth. Learning with the convexified regularizer can be performed by existing efficient algorithms originally designed for convex regularizers (such as the standard proximal algorithm and Frank-Wolfe algorithm). Moreover, it can be shown that critical points of the transformed problem are also critical points of the original problem. Extensive experiments on a number of nonconvex regularization problems show that the proposed procedure is much faster than the state-of-the-art nonconvex solvers. ER -
APA
Yao, Q. & Kwok, J.. (2016). Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2645-2654 Available from https://proceedings.mlr.press/v48/yao16.html.

Related Material