  We consider a regularized least squares problem, with regularization by
structured sparsity-inducing norms, which extend the usual $\ell_1$ and the
group lasso penalty, by allowing the subsets to overlap. Such regularizations
lead to nonsmooth problems that are difficult to optimize, and we propose in
this paper a suitable version of an accelerated proximal method to solve them.
We prove convergence of a nested procedure, obtained composing an accelerated
proximal method with an inner algorithm for computing the proximity operator.
By exploiting the geometrical properties of the penalty, we devise a new active
set strategy, thanks to which the inner iteration is relatively fast, thus
guaranteeing good computational performances of the overall algorithm. Our
approach allows to deal with high dimensional problems without pre-processing
for dimensionality reduction, leading to better computational and prediction
performances with respect to the state-of-the art methods, as shown empirically
both on toy and real data.
