Accelerated nested proximal gradient algorithm for structured sparse optimization with capped-ℓ1 penalty

In this paper, we study a class of structured sparse optimization problems characterized by a convex, possibly non-smooth loss function and a capped-ℓ1 penalty. This model can provide an exact continuous relaxation for the problems with a cardinality penalty. First, we propose an Accelerated Nested Proximal Gradient (ANPG) algorithm, which employs a nested proximal structure and selective extrapolation to enhance computational efficiency. Under some mild and easily verifiable conditions, we prove the subsequence convergence of the ANPG algorithm to the lifted stationary points of the considered problem, which correspond to the strong local minimizers of the corresponding cardinality penalty problems. Moreover, we establish an O(k-1) convergence rate on the objective function values, while a refined extrapolation strategy ensures sequence convergence of the iterates, albeit with a potential reduction in the theoretical convergence rate on the objective values. Second, for the cases with a smooth loss function, we further propose an Accelerated Proximal Gradient (APG) algorithm that guarantees the sequence convergence on the iterates and achieves a faster convergence rate of o(k-2) in terms of objective values. Finally, the effectiveness of the ANPG and APG algorithms, as well as the high quality of the solutions they produce, are verified through numerical experiments on the least absolute deviation regression problem and the sparse logistic regression problem, respectively.