Proceedings

Efficient k-Support-Norm Regularized Minimization via Fully Corrective Frank-Wolfe Method

Bo Liu, Xiao-Tong Yuan, Shaoting Zhang, Qingshan Liu, Dimitris N. Metaxas

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 1760-1765.

Abstract

The k-support-norm regularized minimization has recently been applied with success to sparse prediction problems. The proximal gradient method is conventionally used to minimize this composite model. However it tends to suffer from expensive iteration cost as the proximity operator associated with k-support-norm needs exhaustive searching operations and thus could be time consuming in large scale settings. In this paper, we reformulate the k-support-norm regularized formulation into an identical constrained formulation and propose a fully corrective Frank-Wolfe algorithm to minimize the constrained model. Our method is inspired by an interesting observation that the convex hull structure of the k-support-norm ball allows the application of Frank-Wolfe-type algorithms with low iteration complexity. The convergence behavior of the proposed algorithm is analyzed. Extensive numerical results in learning tasks including logistic regression and matrix pursuit demonstrate the substantially improved computational efficiency of our algorithm over the state-of-the-art proximal gradient algorithms.

Bo Liu, Xiao-Tong Yuan, Shaoting Zhang, Qingshan Liu, and Dimitris N. Metaxas. 2016. Efficient k-Support-Norm Regularized Minimization via Fully Corrective Frank-Wolfe Method. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 1760–1765. https://ijcai.org/proceedings/2016/252
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards