Greedy and IHT Algorithms for Non-convex Optimization with Monotone Costs of Non-zeros

Shinsaku Sakaue
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:206-215, 2019.

Abstract

Non-convex optimization methods, such as greedy-style algorithms and iterative hard thresholding (IHT), for $\ell_0$-constrained minimization have been extensively studied thanks to their high empirical performances and strong guarantees. However, few works have considered non-convex optimization with general non-zero patterns; this is unfortunate since various non-zero patterns are quite common in practice. In this paper, we consider the case where non-zero patterns are specified by monotone set functions. We first prove an approximation guarantee of a cost-benefit greedy (CBG) algorithm by using the {\it weak submodularity} of the problem. We then consider an IHT-style algorithm, whose projection step uses CBG, and prove its convergence guarantee. We also provide many applications and experimental results that confirm the advantages of the algorithms introduced.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-sakaue19a, title = {Greedy and IHT Algorithms for Non-convex Optimization with Monotone Costs of Non-zeros}, author = {Sakaue, Shinsaku}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {206--215}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/sakaue19a/sakaue19a.pdf}, url = {https://proceedings.mlr.press/v89/sakaue19a.html}, abstract = {Non-convex optimization methods, such as greedy-style algorithms and iterative hard thresholding (IHT), for $\ell_0$-constrained minimization have been extensively studied thanks to their high empirical performances and strong guarantees. However, few works have considered non-convex optimization with general non-zero patterns; this is unfortunate since various non-zero patterns are quite common in practice. In this paper, we consider the case where non-zero patterns are specified by monotone set functions. We first prove an approximation guarantee of a cost-benefit greedy (CBG) algorithm by using the {\it weak submodularity} of the problem. We then consider an IHT-style algorithm, whose projection step uses CBG, and prove its convergence guarantee. We also provide many applications and experimental results that confirm the advantages of the algorithms introduced.} }
Endnote
%0 Conference Paper %T Greedy and IHT Algorithms for Non-convex Optimization with Monotone Costs of Non-zeros %A Shinsaku Sakaue %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-sakaue19a %I PMLR %P 206--215 %U https://proceedings.mlr.press/v89/sakaue19a.html %V 89 %X Non-convex optimization methods, such as greedy-style algorithms and iterative hard thresholding (IHT), for $\ell_0$-constrained minimization have been extensively studied thanks to their high empirical performances and strong guarantees. However, few works have considered non-convex optimization with general non-zero patterns; this is unfortunate since various non-zero patterns are quite common in practice. In this paper, we consider the case where non-zero patterns are specified by monotone set functions. We first prove an approximation guarantee of a cost-benefit greedy (CBG) algorithm by using the {\it weak submodularity} of the problem. We then consider an IHT-style algorithm, whose projection step uses CBG, and prove its convergence guarantee. We also provide many applications and experimental results that confirm the advantages of the algorithms introduced.
APA
Sakaue, S.. (2019). Greedy and IHT Algorithms for Non-convex Optimization with Monotone Costs of Non-zeros. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:206-215 Available from https://proceedings.mlr.press/v89/sakaue19a.html.

Related Material