Timezone: »
Poster
Semismooth Newton Algorithm for Efficient Projections onto $\ell_{1, \infty}$-norm Ball
Dejun Chu · Changshui Zhang · Shiliang Sun · Qing Tao
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 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 $\ell_{1, \infty}$-norm ball constraint.
Author Information
Dejun Chu (Tsinghua University)
Changshui Zhang (Tsinghua University)
Shiliang Sun (East China Normal University)
Qing Tao (Army Academy of Artillery and Air Defense)
More from the Same Authors
-
2021 Poster: SagaNet: A Small Sample Gated Network for Pediatric Cancer Diagnosis »
Yuhan Liu · Shiliang Sun -
2021 Spotlight: SagaNet: A Small Sample Gated Network for Pediatric Cancer Diagnosis »
Yuhan Liu · Shiliang Sun -
2021 Poster: K-shot NAS: Learnable Weight-Sharing for NAS with K-shot Supernets »
Xiu Su · Shan You · Mingkai Zheng · Fei Wang · Chen Qian · Changshui Zhang · Chang Xu -
2021 Spotlight: K-shot NAS: Learnable Weight-Sharing for NAS with K-shot Supernets »
Xiu Su · Shan You · Mingkai Zheng · Fei Wang · Chen Qian · Changshui Zhang · Chang Xu