Greedy and IHT Algorithms for Non-Convex Optimization with Monotone Costs of Non-Zeros

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.