Semismooth Newton Algorithm for Efficient Projections onto $\ell_1, ∞$-norm Ball

Dejun Chu, Changshui Zhang, Shiliang Sun, Qing Tao
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:1974-1983, 2020.

Abstract

The structured sparsity-inducing $\ell_{1, \infty}$-norm, as a generalization of the classical $\ell_1$-norm, plays an important role in jointly sparse models which select or remove simultaneously all the variables forming a group. However, its resulting problem is more difficult to solve than the conventional $\ell_1$-norm constrained problem. In this paper, we propose an efficient algorithm for Euclidean projection onto $\ell_{1, \infty}$-norm ball. We tackle the projection problem via semismooth Newton algorithm to solve the system of semismooth equations. Meanwhile, exploiting the structure of the Jacobian matrix via LU decomposition yields an equivalent algorithm which is proved to terminate after a finite number of iterations. Empirical studies demonstrate that our proposed algorithm outperforms the existing state-of-the-art solver and is promising for the optimization of learning problems with the $\ell_{1, \infty}$-norm ball constraint.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-chu20b, title = {Semismooth {N}ewton Algorithm for Efficient Projections onto $\ell_{1, ∞}$-norm Ball}, author = {Chu, Dejun and Zhang, Changshui and Sun, Shiliang and Tao, Qing}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {1974--1983}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/chu20b/chu20b.pdf}, url = {https://proceedings.mlr.press/v119/chu20b.html}, abstract = {The structured sparsity-inducing $\ell_{1, \infty}$-norm, as a generalization of the classical $\ell_1$-norm, plays an important role in jointly sparse models which select or remove simultaneously all the variables forming a group. However, its resulting problem is more difficult to solve than the conventional $\ell_1$-norm constrained problem. In this paper, we propose an efficient algorithm for Euclidean projection onto $\ell_{1, \infty}$-norm ball. We tackle the projection problem via semismooth Newton algorithm to solve the system of semismooth equations. Meanwhile, exploiting the structure of the Jacobian matrix via LU decomposition yields an equivalent algorithm which is proved to terminate after a finite number of iterations. Empirical studies demonstrate that our proposed algorithm outperforms the existing state-of-the-art solver and is promising for the optimization of learning problems with the $\ell_{1, \infty}$-norm ball constraint.} }
Endnote
%0 Conference Paper %T Semismooth Newton Algorithm for Efficient Projections onto $\ell_1, ∞$-norm Ball %A Dejun Chu %A Changshui Zhang %A Shiliang Sun %A Qing Tao %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-chu20b %I PMLR %P 1974--1983 %U https://proceedings.mlr.press/v119/chu20b.html %V 119 %X The structured sparsity-inducing $\ell_{1, \infty}$-norm, as a generalization of the classical $\ell_1$-norm, plays an important role in jointly sparse models which select or remove simultaneously all the variables forming a group. However, its resulting problem is more difficult to solve than the conventional $\ell_1$-norm constrained problem. In this paper, we propose an efficient algorithm for Euclidean projection onto $\ell_{1, \infty}$-norm ball. We tackle the projection problem via semismooth Newton algorithm to solve the system of semismooth equations. Meanwhile, exploiting the structure of the Jacobian matrix via LU decomposition yields an equivalent algorithm which is proved to terminate after a finite number of iterations. Empirical studies demonstrate that our proposed algorithm outperforms the existing state-of-the-art solver and is promising for the optimization of learning problems with the $\ell_{1, \infty}$-norm ball constraint.
APA
Chu, D., Zhang, C., Sun, S. & Tao, Q.. (2020). Semismooth Newton Algorithm for Efficient Projections onto $\ell_1, ∞$-norm Ball. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:1974-1983 Available from https://proceedings.mlr.press/v119/chu20b.html.

Related Material