Efficient inexact proximal gradient algorithms for structured sparsity-inducing norm. (October 2019)

• Record Type: Journal Article
• Authors: Gu, Bin; Geng, Xiang; Li, Xiang; Zheng, Guansheng
• Is Part Of: Neural networks. Volume 118(2019)
• Page Start: 352
• Page End: 362
• Publication Date: 2019-10
• Subjects: Structured-sparsity regularization -- l1∕l∞ norm -- Inexact proximal operator -- overlapping groups; Neural computers -- Periodicals; Neural networks (Computer science) -- Periodicals; Neural networks (Neurobiology) -- Periodicals; Nervous System -- Periodicals; Ordinateurs neuronaux -- Périodiques; Réseaux neuronaux (Informatique) -- Périodiques; Réseaux neuronaux (Neurobiologie) -- Périodiques; Neural computers; Neural networks (Computer science); Neural networks (Neurobiology); Periodicals; 006.32
• DOI: 10.1016/j.neunet.2019.06.015
• Languages: English
• ISSNs: 0893-6080

Abstract

Abstract: Structured-sparsity regularization is popular for sparse learning because of its flexibility of encoding the feature structures. This paper considers a generalized version of structured-sparsity regularization (especially for l 1 ∕ l ∞ norm) with arbitrary group overlap. Due to the group overlap, it is time-consuming to solve the associated proximal operator. Although Mairal et al. have proposed a network-flow algorithm to solve the proximal operator, it is still time-consuming, especially in the high-dimensional setting. To address this challenge, in this paper, we have developed a more efficient solution for l 1 ∕ l ∞ group lasso with arbitrary group overlap using inexact proximal gradient method. In each iteration, our algorithm only requires to calculate an inexact solution to the proximal sub-problem, which can be done efficiently. On the theoretic side, the proposed algorithm enjoys the same global convergence rate as the exact proximal methods. Experiments demonstrate that our algorithm is much more efficient than the network-flow algorithm while retaining similar generalization performance.