Structured Sparse Regression via Greedy Hard-Thresholding

High dimensional problems where the regressor belongs to a small number of groups play a critical role in many machine learning and signal processing applications, such as computational biology [9] and multitask learning [14]. In most of these cases, the groups overlap, i.e., the same feature can belong to multiple groups. For example, gene pathways overlap in computational biology applications, and parent-child pairs of wavelet transform coefficients overlap in signal processing applications. The existing state-of-the-art methods for solving such group sparsity structured regression problems can be categorized into two broad classes: a) convex relaxation based methods, b) iterative hard thresholding (IHT) or greedy methods. 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 NPhard to compute and often certain simple heuristics are used with relatively weak theoretical guarantees. Moreover, existing guarantees for both classes of methods require relatively restrictive assumptions on the data, like Restricted Isometry Property or variants thereof [2, 8, 18, 14], that are unlikely to hold in most common applications. In fact, even under such settings, the group sparsity based convex programs offer at most polylogarithmic gains over standard sparsity based methods [18].