A proximal-gradient method for problems with overlapping group-sparse regularization: support identification complexity

We consider the proximal-gradient method for minimizing the sum of a smooth function and a convex non-smooth overlapping group-ℓ1 regularizer, which is known to promote sparse solutions with respect to its groups. A feature that distinguishes our work from most in the literature is that the proximal operator for the overlapping group-ℓ1 function does not admit a closed-form solution, which introduces challenges when proving convergence of the iterates and especially when proving that the iterates correctly identify the group-sparse structure of the optimal solution. To address these challenges, we present an implementable termination condition for the proximal-gradient algorithm, and a specialized primal-dual subproblem solver that is designed to ensure that a group-sparse structure identification property holds. In particular, we give an upper bound on the maximum number of iterations before the correct support (i.e. group-sparse structure) of an optimal solution is identified.