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 $\geq 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.
