Learning Sparse Combinatorial Representations via Two-stage Submodular Maximization

Eric Balkanski, Baharan Mirzasoleiman, Andreas Krause, Yaron Singer
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2207-2216, 2016.

Abstract

We consider the problem of learning sparse representations of data sets, where the goal is to reduce a data set in manner that optimizes multiple objectives. Motivated by applications of data summarization, we develop a new model which we refer to as the two-stage submodular maximization problem. This task can be viewed as a combinatorial analogue of representation learning problems such as dictionary learning and sparse regression. The two-stage problem strictly generalizes the problem of cardinality constrained submodular maximization, though the objective function is not submodular and the techniques for submodular maximization cannot be applied. We describe a continuous optimization method which achieves an approximation ratio which asymptotically approaches 1-1/e. For instances where the asymptotics do not kick in, we design a local-search algorithm whose approximation ratio is arbitrarily close to 1/2. We empirically demonstrate the effectiveness of our methods on two multi-objective data summarization tasks, where the goal is to construct summaries via sparse representative subsets w.r.t. to predefined objectives.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-balkanski16, title = {Learning Sparse Combinatorial Representations via Two-stage Submodular Maximization}, author = {Balkanski, Eric and Mirzasoleiman, Baharan and Krause, Andreas and Singer, Yaron}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2207--2216}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/balkanski16.pdf}, url = {https://proceedings.mlr.press/v48/balkanski16.html}, abstract = {We consider the problem of learning sparse representations of data sets, where the goal is to reduce a data set in manner that optimizes multiple objectives. Motivated by applications of data summarization, we develop a new model which we refer to as the two-stage submodular maximization problem. This task can be viewed as a combinatorial analogue of representation learning problems such as dictionary learning and sparse regression. The two-stage problem strictly generalizes the problem of cardinality constrained submodular maximization, though the objective function is not submodular and the techniques for submodular maximization cannot be applied. We describe a continuous optimization method which achieves an approximation ratio which asymptotically approaches 1-1/e. For instances where the asymptotics do not kick in, we design a local-search algorithm whose approximation ratio is arbitrarily close to 1/2. We empirically demonstrate the effectiveness of our methods on two multi-objective data summarization tasks, where the goal is to construct summaries via sparse representative subsets w.r.t. to predefined objectives.} }
Endnote
%0 Conference Paper %T Learning Sparse Combinatorial Representations via Two-stage Submodular Maximization %A Eric Balkanski %A Baharan Mirzasoleiman %A Andreas Krause %A Yaron Singer %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-balkanski16 %I PMLR %P 2207--2216 %U https://proceedings.mlr.press/v48/balkanski16.html %V 48 %X We consider the problem of learning sparse representations of data sets, where the goal is to reduce a data set in manner that optimizes multiple objectives. Motivated by applications of data summarization, we develop a new model which we refer to as the two-stage submodular maximization problem. This task can be viewed as a combinatorial analogue of representation learning problems such as dictionary learning and sparse regression. The two-stage problem strictly generalizes the problem of cardinality constrained submodular maximization, though the objective function is not submodular and the techniques for submodular maximization cannot be applied. We describe a continuous optimization method which achieves an approximation ratio which asymptotically approaches 1-1/e. For instances where the asymptotics do not kick in, we design a local-search algorithm whose approximation ratio is arbitrarily close to 1/2. We empirically demonstrate the effectiveness of our methods on two multi-objective data summarization tasks, where the goal is to construct summaries via sparse representative subsets w.r.t. to predefined objectives.
RIS
TY - CPAPER TI - Learning Sparse Combinatorial Representations via Two-stage Submodular Maximization AU - Eric Balkanski AU - Baharan Mirzasoleiman AU - Andreas Krause AU - Yaron Singer BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-balkanski16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2207 EP - 2216 L1 - http://proceedings.mlr.press/v48/balkanski16.pdf UR - https://proceedings.mlr.press/v48/balkanski16.html AB - We consider the problem of learning sparse representations of data sets, where the goal is to reduce a data set in manner that optimizes multiple objectives. Motivated by applications of data summarization, we develop a new model which we refer to as the two-stage submodular maximization problem. This task can be viewed as a combinatorial analogue of representation learning problems such as dictionary learning and sparse regression. The two-stage problem strictly generalizes the problem of cardinality constrained submodular maximization, though the objective function is not submodular and the techniques for submodular maximization cannot be applied. We describe a continuous optimization method which achieves an approximation ratio which asymptotically approaches 1-1/e. For instances where the asymptotics do not kick in, we design a local-search algorithm whose approximation ratio is arbitrarily close to 1/2. We empirically demonstrate the effectiveness of our methods on two multi-objective data summarization tasks, where the goal is to construct summaries via sparse representative subsets w.r.t. to predefined objectives. ER -
APA
Balkanski, E., Mirzasoleiman, B., Krause, A. & Singer, Y.. (2016). Learning Sparse Combinatorial Representations via Two-stage Submodular Maximization. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2207-2216 Available from https://proceedings.mlr.press/v48/balkanski16.html.

Related Material