Structured Sparse Regression via Greedy Hard-thresholding
Several learning applications require solving high-dimensional regression problems where the relevant features belong to a small number of (overlapping) groups. For very large datasets and under standard sparsity constraints, hard thresholding methods have proven to be extremely efficient, but such methods require NP hard projections when dealing with overlapping groups. In this paper, we show that such NP-hard projections can not only be avoided by appealing to submodular optimization, but such methods come with strong theoretical guarantees even in the presence of poorly conditioned data (i.e. say when two features have correlation 0.99), which existing analyses cannot handle. These methods exhibit an interesting computation-accuracy trade-off and can be extended to significantly harder problems such as sparse overlapping groups. Experiments on both real and synthetic data validate our claims and demonstrate that the proposed methods are orders of magnitude faster than other greedy and convex relaxation techniques for learning with group-structured sparsity.
The authors consider an \ell_0 penalized overlapping group regularization problem, and a corresponding greedy iterative hard thresholding method. The main challenge is in the projection step encountered in the latter method. For this, the authors proposed to use submodular optimization to produce an approximate projection. Statistical analysis is provided for the resulting estimator.
I generally like the proposal and find the use of submodular optimization for the approximate projection to be interesting. But at the same time, I'm really not convinced that the proposal is actually useful, either theoretically, or practically. Various claims made throughout the paper are quite confusing to me, and this certainly doesn't help.  You criticize other works at the bottom of page 2 for assuming RIP, and also earlier in lines 26-28, but then you go and assume RSC above Definition 1. Aren't these essentially very similar assumptions ...? And furthermore, all in all, it seems to me that your results are pretty comparable to those from convex methods, if not a little weaker. So I'm left wondering: what is the point, theoretically?  From a practical perspective, I could see Algorithms 1 and 2 be appealing for their simplicity. I could also imagine them being efficient. But the experiments given in the paper are pretty limited. The same can be said of the one experiment in the supplement. I think a much more thorough analysis and comparison should be conducted (especially if the theory is about on par with existing theory).   What are FW, CoGEnT, and GOMP? It's not helpful to have the reader guess, but rather it would be worth spending the time explaining what these are down, even just briefly. I can guess was GOMP is, but FW = Frank-Wolfe is just a generic algorithm that can be applied to a wide range of optimization problems so that is not helpful, and I have no idea what CoGEnT is. Are any of these (perhaps FW) being applied to the same problem you are considering in (4) (or (5))? Are any of these considering the convex analog of (4) (or (5))? I don't think so, and convex analogs should really be compared, especially given your high-level discussion throughout the paper comparing your results/approach to convex ones.  Other specific comments:  - Lines 23-25: "In practice, IHT methods tend to be significantly more scalable than the (group-)lasso style methods that solve a convex program. But, these methods require a certain projection operator which in general is NP-hard to compute..." I know what you mean to convey here, but it reads a little funny. You mean that IHT methods are scalable in practice, becuase they only approximately solve the problems that they are designed for. Exact solutions are NP-hard.  - The notation in (1) is a little crazy. It is almost universal to use \beta as the regression parameter. You use it as the noise variable. And you use \lambda as the noise variance, which is also confusing, because this is often reserved as a regularization parameter (say, penalty parameter for the group lasso).  Again it is almost universal to use \sigma.   - I'm confused about the discussion at the top of page 2. First of all, in the 2nd paragraph, you say that the improvements in sample complexity from the group lasso over the lasso are only logarithmic, which means that \log{p} becomes \log{M}, with M being the number groups and p being the number of features. (An aside, I don't see this as a bad thing; the feature dependence is already logarithmic to begin with, so what more could you ask for?) But isn't this precisely analogous to what you are claiming in the 4th paragraph, with your IHT group sparsity results, over IHT standard sparsity results?  Furthermore, I don't understand the point of paragraph 3 and how it relates to your own work that you describe in paragraph 4. You say in paragraph 3 that "Greedy, Iterative Hard Thresholding (IHT) methods have been considered for group sparse regression 46 problems, but ... the guarantees they provide are along the same lines as the ones that exist for convex methods."  Then in paragraph 4, you say that "In this paper, we show that IHT schemes with approximate projections for the group sparsity problem yield much stronger guarantees." This doesn't really make sense as written; are you using different approximation schemes, is that the point? And also, the guarantees that you describe in paragraph 4 for your method still do sounds quite similar to those from convex programming...