On The Projection Operator to A Three-view Cardinality Constrained Set

Haichuan Yang, Shupeng Gui, Chuyang Ke, Daniel Stefankovic, Ryohei Fujimaki, Ji Liu
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:3871-3880, 2017.

Abstract

The cardinality constraint is an intrinsic way to restrict the solution structure in many domains, for example, sparse learning, feature selection, and compressed sensing. To solve a cardinality constrained problem, the key challenge is to solve the projection onto the cardinality constraint set, which is NP-hard in general when there exist multiple overlapped cardinality constraints. In this paper, we consider the scenario where the overlapped cardinality constraints satisfy a Three-view Cardinality Structure (TVCS), which reflects the natural restriction in many applications, such as identification of gene regulatory networks and task-worker assignment problem. We cast the projection into a linear programming, and show that for TVCS, the vertex solution of this linear programming is the solution for the original projection problem. We further prove that such solution can be found with the complexity proportional to the number of variables and constraints. We finally use synthetic experiments and two interesting applications in bioinformatics and crowdsourcing to validate the proposed TVCS model and method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-yang17c, title = {On The Projection Operator to A Three-view Cardinality Constrained Set}, author = {Haichuan Yang and Shupeng Gui and Chuyang Ke and Daniel Stefankovic and Ryohei Fujimaki and Ji Liu}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {3871--3880}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/yang17c/yang17c.pdf}, url = {https://proceedings.mlr.press/v70/yang17c.html}, abstract = {The cardinality constraint is an intrinsic way to restrict the solution structure in many domains, for example, sparse learning, feature selection, and compressed sensing. To solve a cardinality constrained problem, the key challenge is to solve the projection onto the cardinality constraint set, which is NP-hard in general when there exist multiple overlapped cardinality constraints. In this paper, we consider the scenario where the overlapped cardinality constraints satisfy a Three-view Cardinality Structure (TVCS), which reflects the natural restriction in many applications, such as identification of gene regulatory networks and task-worker assignment problem. We cast the projection into a linear programming, and show that for TVCS, the vertex solution of this linear programming is the solution for the original projection problem. We further prove that such solution can be found with the complexity proportional to the number of variables and constraints. We finally use synthetic experiments and two interesting applications in bioinformatics and crowdsourcing to validate the proposed TVCS model and method.} }
Endnote
%0 Conference Paper %T On The Projection Operator to A Three-view Cardinality Constrained Set %A Haichuan Yang %A Shupeng Gui %A Chuyang Ke %A Daniel Stefankovic %A Ryohei Fujimaki %A Ji Liu %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-yang17c %I PMLR %P 3871--3880 %U https://proceedings.mlr.press/v70/yang17c.html %V 70 %X The cardinality constraint is an intrinsic way to restrict the solution structure in many domains, for example, sparse learning, feature selection, and compressed sensing. To solve a cardinality constrained problem, the key challenge is to solve the projection onto the cardinality constraint set, which is NP-hard in general when there exist multiple overlapped cardinality constraints. In this paper, we consider the scenario where the overlapped cardinality constraints satisfy a Three-view Cardinality Structure (TVCS), which reflects the natural restriction in many applications, such as identification of gene regulatory networks and task-worker assignment problem. We cast the projection into a linear programming, and show that for TVCS, the vertex solution of this linear programming is the solution for the original projection problem. We further prove that such solution can be found with the complexity proportional to the number of variables and constraints. We finally use synthetic experiments and two interesting applications in bioinformatics and crowdsourcing to validate the proposed TVCS model and method.
APA
Yang, H., Gui, S., Ke, C., Stefankovic, D., Fujimaki, R. & Liu, J.. (2017). On The Projection Operator to A Three-view Cardinality Constrained Set. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:3871-3880 Available from https://proceedings.mlr.press/v70/yang17c.html.

Related Material