k-Support and Ordered Weighted Sparsity for Overlapping Groups: Hardness and Algorithms
The k-support and OWL norms generalize the 1 norm, providing better prediction accuracy and better handling of correlated variables. We study the norms obtained from extending the k-support norm and OWL norms to the setting in which there are overlapping groups. The resulting norms are in general NP-hard to compute, but they are tractable for certain collections of groups. To demonstrate this fact, we develop a dynamic program for the problem of projecting onto the set of vectors supported by a fixed number of groups. Our dynamic program utilizes tree decompositions and its complexity scales with the treewidth. This program can be converted to an extended formulation which, for the associated group structure, models the k-group support norms and an overlapping group variant of the ordered weighted 1 norm. Numerical results demonstrate the efficacy of the new penalties.
Summary: 
This paper designs new norms for group sparse estimation. The authors extend the k-support norm and the ordered weighted norm to the group case (with overlaps). The resulting (latent) norms are unfortunately NP-hard to compute, though. The main contribution is an algorithm based on tree decomposition and dynamic programming for computing the best approximation (under the Euclidean norm) under group cardinality constraints. This algorithm improves the previous work by a factor of m (# of groups). A second contribution is an extended formulation for the proposed latent group norms. Such formulation can be plugged into standard convex programming toolboxes, as long as the underlying tree width is small. Some synthetic experiments are provided to justify the proposed norms (and their extended formulations).
Overall this paper appears hard to follow, largely due to its technical nature. The organization is also a bit off: the utility of the dynamic programming algorithm in section 3 is largely unclear, and the experiment section did not verify this part at all. While being mostly a computational paper, strangely, the experiment section only compared the statistical performances of different norms, without conducting any computational comparison. While the technical results seem to be solid and improve previous work, it will be more convincing if more can be said on what kind of problems can benefit from the authors' results. With these much more sophisticated norms, one becomes easily overwhelmed by the fine mathematical details but somehow also gets more suspicious about their practical relevance (which unfortunately is not well addressed by the current experiments). 
Other comments:
Lines 93-95: the parameter nu disappears in the convex envelope?
Line 97: the weights need to be nonnegative.
Line 343: this proof of Theorem 2.1 works only for 1 < p < infty? For instance, if p = 1, then Omega = |.|_1 always. Please fully justify the claim "Omega is the ell_p norm if and only if ...", as the experiments did use p=infty. 
Line 346: please justify "if lambda < 1, the solution is (1-lambda)y if and only if ..."
Line 141:  I do not see why the claim N <= |V| is correct. do you mean max_j |X_j| <= |V|?
Experiments: should also include a set of experiments that favors the latent group norm, to see that if the proposed norms perform (much?) worse under an unfavorable condition. Also, please compare with the elastic net regularizer (in the correlated design case).