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.


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.

Related Material