Efficient k-support-norm regularized minimization via fully corrective Frank-Wolfe method

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

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1760-1766
Number of pages7
JournalIJCAI International Joint Conference on Artificial Intelligence
Volume2016-January
StatePublished - 2016
Event25th International Joint Conference on Artificial Intelligence, IJCAI 2016 - New York, United States
Duration: Jul 9 2016Jul 15 2016

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Efficient k-support-norm regularized minimization via fully corrective Frank-Wolfe method'. Together they form a unique fingerprint.

Cite this