Greedy and IHT Algorithms for Nonconvex Optimization with Monotone Costs of Nonzeros
[edit]
Proceedings of Machine Learning Research, PMLR 89:206215, 2019.
Abstract
Nonconvex optimization methods, such as greedystyle 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 nonconvex optimization with general nonzero patterns; this is unfortunate since various nonzero patterns are quite common in practice. In this paper, we consider the case where nonzero patterns are specified by monotone set functions. We first prove an approximation guarantee of a costbenefit greedy (CBG) algorithm by using the {\it weak submodularity} of the problem. We then consider an IHTstyle 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.
Related Material


