Maximization of non-submodular set functions has been attracting a lot of attention since many set functions that appear in practice lack submodularity. In this paper, we study maximization of weakly modular functions, which has both weak submodularity and weak supermodularity . Actually, weakly modular maximization (WMM) can model various important (possibly non-submodular) maximization problems including feature selection and production planning. We reveal two theoretical properties of WMM: We prove a hardness result related to improving an existing approximation guarantee achieved by the greedy algorithm, and we show that WMM is fixed-parameter tractable under certain conditions. The latter result provides a new time--accuracy trade-off for @math -constrained minimization as a corollary. We then prove that efficient multi-stage algorithms can perform well for WMM; the obtained theoretical guarantees generalize and improve some existing results. Experiments confirm the practical utility of the multi-stage algorithms.
@cite_27: 
@cite_21: We study the problem of minimizing the expected loss of a linear predictor while constraining its sparsity, i.e., bounding the number of features used by the predictor. While the resulting optimization problem is generally NP-hard, several approximation algorithms are considered. We analyze the performance of these algorithms, focusing on the characterization of the trade-off between accuracy and sparsity of the learned predictor in different scenarios.
@cite_32: The use of M-estimators in generalized linear regression models in high dimensional settings requires risk minimization with hard L0 constraints. Of the known methods, the class of projected gradient descent (also known as iterative hard thresholding (IHT)) methods is known to offer the fastest and most scalable solutions. However, the current state-of-the-art is only able to analyze these methods in extremely restrictive settings which do not hold in high dimensional statistical models. In this work we bridge this gap by providing the first analysis for IHT-style methods in the high dimensional statistical setting. Our bounds are tight and match known minimax lower bounds. Our results rely on a general analysis framework that enables us to analyze several popular hard thresholding style algorithms (such as HTP, CoSaMP, SP) in the high dimensional regression setting. Finally, we extend our analysis to the problem of low-rank matrix recovery.
@cite_23: Non-convex optimization methods, such as greedy-style algorithms and iterative hard thresholding (IHT), for @math -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 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.
proposed for atom selection, which basically corresponds to the case where @math is quadratic. However, its theoretical guarantee has not been proved. We extend their algorithm to the case where @math is RSC RSM and prove its guarantee. Many recent studies on @math -constrained minimization have been devoted to projected-gradient-based methods such as and @cite_32 @cite_27 @cite_23 , which are typically faster than greedy-style methods. However, their theoretical guarantees imply that projected-gradient-based methods can be affected by the ill condition more negatively than greedy-style methods. For example, to achieve @math -error guarantees, forward greedy selection and require @math and @math , respectively (see, @cite_21 @cite_32 ), where @math is a condition number ; a larger @math implies a worse condition.