Group zero-norm regularized robust loss minimization: proximal MM method and statistical error bound
Ling Liang, Shujun Bi · 2025
Read Group zero-norm regularized robust loss minimization: proximal MM method and statistical error bound by Ling Liang, Shujun Bi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23294.txt.
Introduction
Liang and Bi take on group zero-norm problems with loss terms, using a proximal method that works by steps of majorization, in work from 2025. The task fits data with many inputs, where whole groups should sit at zero and stray points should not skew the fit. Their method works on a matched stand-in form, a difference-of-convex form. A dual semismooth Newton step cracks the hard sub-tasks with less work.
The method settles on an answer as a whole, if the Kurdyka-Lojasiewicz trait holds. Near the end, its speed is pinned down as slower than straight-line in one regime and straight-line in the next. For straight-line models, the team bounds how far iterates sit from truth, when a named check on eigenvalues holds. Fake data and known benchmark sets show the method beats proximal ADMM on speed.
Catalog record
| CREATOR | Ling Liang, Shujun Bi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 137 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-23294
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Group zero-norm regularized robust loss minimization: proximal MM method and statistical error bound Ling Liang, Shujun Bi Abstract This study focuses on solving group zero-norm regularized robust loss minimization problems. We propose a proximal Majorization-Minimization (PMM) algorithm to address a class of equivalent Difference-of-Convex (DC) surrogate optimization problems. First, we present the core principles and iterative framework of the PMM method. Under the Kurdyka-Łojasiewicz (KL) property assumption of the potential function, we establish the global convergence of the algorithm and characterize its local (sub)linear convergence rate. Furthermore, for linear observation models with design matrices satisfying restricted eigenvalue conditions, we derive statistical estimation error bounds between the PMM-generated iterates (including their limit points) and the ground truth solution. These bounds not only rigorously quantify the approximation accuracy of the algorithm but also extend previous results on element-wise sparse composite optimization from reference [57]. To efficiently implement the PMM framework, we develop a proximal dual semismooth Newton method for solving critical subproblems. Extensive numerical experiments on both synthetic data and the UCI benchmark demonstrate the superior computational efficiency of our PMM method compared to the proximal Alternating Direction Method of Multipliers (pADMM). I Introduction Group sparse optimization extends traditional sparse modeling by incorporating structural sparsity constraints. Whereas conventional approaches focus on element-wise sparsity through \ell_{1} -norm regularization, modern applications increasingly require group-wise selection mechanisms to handle clustered variable structures-a critical capability absent in classical formulations. This paradigm shift has positioned group sparse optimization as a pivotal methodology in high-dimensional statistics. I-A Motivation Consider a feature space partitioned by disjoint index sets \bigcup_{i=1}^{m}J_{i} satisfying \bigcup_{i=1}^{m}J_{i}=\{1,2,\ldots,p\} with J_{i}\cap J_{j}=\emptyset for all i\neq j\in\{1,2,\ldots,m\} . The fundamental group sparse recovery problem seeks solutions to underdetermined systems: b=\sum^{m}_{i=1}A_{J_{i}}{x^{*}}_{J_{i}}+\varpi, (1) where x^{*}\in\mathbb{R}^{p} denotes the ground true coefficients, A_{J_{i}}\in\mathbb{R}^{n\times|J_{i}|}(i=1,2,\ldots,m) the design submatrices, and \varpi\sim(0,\sigma^{2}I_{n}) the measurement noise. Notably, this generalizes standard sparse regression when |J_{i}|=1 for arbitrary \{i\} . Pioneered by Yuan and Lin [ 52 ] , the canonical formulation employs group zero-norm regularization: \min_{x\in\mathbb{R}^{p}}\Theta_{\nu,\mu}(x):=f(x)+\nu\|x\|_{\rm gz}, (2) where \|x\|_{\rm gz}:=\sum_{i=1}^{m}{\rm sign}(\|x_{J_{i}}\|_{2}) counts nonzero groups. The nonconvex, discontinuous nature of \|\cdot\|_{\rm gz} induces NP-hardness, necessitating specialized optimization strategies. Group sparse optimization has emerged as a cornerstone methodology with multidisciplinary applications. In computational imaging, it serves as a powerful regularizer for inverse problems including image denoising, deblurring, and inpainting. Through strategic partitioning of image attributes (color channels, texture patches) into coherent groups and enforcing inter-group sparsity constraints, this approach achieves superior reconstruction fidelity by preserving structural coherence [ 24 , 49 , 22 , 53 ] . The statistical learning domain benefits from its dual capability in feature selection and model compression. By imposing group-wise sparsity on correlated feature clusters, the framework automatically prunes redundant variables while retaining discriminative feature groups—a mechanism proven to enhance generalization performance through intrinsic dimension reduction. Beyond single-task learning, multi-task variants leverage inter-task correlations via shared sparsity patterns, where parameter groups across tasks are jointly regularized to capture common representations while maintaining task-specific adaptations [ 52 , 39 , 40 , 28 , 54 , 32 , 27 ] . Compressive sensing theory further reveals its theoretical advantages: As a structured sparsity paradigm, block or group sparsity not only generalizes standard sparse signal models but also permits tighter sampling bounds and improved recovery guarantees compared to element-wise sparsity [ 25 , 47 , 21 , 22 ] . Emerging applications in computational biology demonstrate its utility for genomic feature selection, where gene regulatory networks naturally exhibit group-structured sparsity [ 32 ] . These developments have spurred extensions of classical sparse recovery algorithms to handle block-sparse constraints. Notable approaches include convex relaxation via the \ell_{2,1} -norm [ 52 , 39 , 10 , 17 ] , iterative hard thresholding (IHT) methods [ 7 ] and nonconvex surrogate formulations that approximate the original NP-hard problem ( 2 ) through tractable alternatives [ 14 , 12 , 13 ] ; The nonconvex surrogates typically replace the discontinuous group zero-norm with non-Lipschitz \ell_{\alpha} -norm regularizers ( 0<\alpha<1 ) [ 8 , 9 ] , smoothing concave approximations [ 6 , 16 ] and folded concave penalties including SCAD and MCP [ 11 , 18 ] . Recent advancements in nonconvex optimization have inspired new algorithmic developments. D. Sun et al. [ 1 ] pioneered a PMM method for square-root-loss regression problems, which was subsequently extended by Zhang et al. [ 57 ] to handle Difference-of-Convex (DC) surrogates of zero-norm regularized optimization. While these works advanced element-wise sparse modeling, they remain limited in addressing group-structured sparsity. Motivated by these foundations, the authors propose the following group zero-norm regularized robust loss composite optimization problems \min_{x\in\mathbb{R}^{p}}\Theta_{\nu,\mu}(x):=\vartheta(Ax-b)+\frac{\mu}{2}\|x\|^{2}+\nu\|g(x)\|_{\rm gz}+\mathbb{I}_{\mathcal{X}}(x), (3) where \mathcal{X}\subseteq\mathbb{R}^{p} denotes a closed convex set, f(x)\!:=\vartheta(Ax\!-\!b)+\frac{\mu}{2}\|x\|^{2} with \vartheta\!:\mathbb{R}^{n}\to\mathbb{R} being a lower-bounded finite-valued convex function, g(x)\!:=Bx encodes structured sparsity patterns through linear mapping, A\in\mathbb{R}^{n\times p},B\in\mathbb{R}^{N\times p} and b\in\mathbb{R}^{n} are given data, \mu>0 ensures coercivity of f over non-compact set \mathcal{X} (redundant when \mathcal{X} is compact). The group sparse structure is explicitly characterized by G(x)\!:=(\|g_{\!{}_{J_{1}}}\!(x)\|,\ldots,\|g_{\!{}_{J_{m}}}\!(x)\|) (4) with composite regularization \theta_{\nu}(x)\!:=\nu\|g(x)\|_{\rm gz}+\mathbb{I}_{\mathcal{X}}(x) . Noted that \|g(x)\|_{\rm gz}=\|G(x)\|_{0} represents the nonzero elements of G(x) . Key advances beyond reference [ 57 ] : 1). Group-structured sparsity: \|\cdot\|_{\rm gz} operates on predefined groups \{J_{i}\}_{i=1}^{m} rather than individual elements 2). Structural encoding: Matrix B models inter-group dependencies 3). Generalized constraints: \mathbb{I}_{\mathcal{X}}(\cdot) accommodates convex domain restrictions. I-B Prior Arts and Contributions In fact, the model ( 3 ) covers various problems in many pieces of literature previously mentioned. In addition, when the smooth mapping g is taken as an identity mapping namely g(x)=x and \{J_{i}\}=i , the model ( 3 ) is reduced to the case in [ 57 ] . When the smooth mapping g is taken as an identity mapping namely g(x)=x , this model is a general group zero-norm optimization problem ( 2 ). When g(x)=Bx , and B takes a special matrix, the model can correspond to the group sparse optimization problem of clustering [ 23 ] . Therefore, this paper considers a general form, namely g is a smooth mapping. The authors provide a unified mechanism for the group zero-norm regularized composite optimization problem ( 3 ) in a more general manner. As is well known, group variable selection models with nonconvex penalties are not without drawbacks. Although nonconvex penalties are beneficial for coefficient estimation, they can lead to nonconvex optimization problems. In nonconvex programming, optimization problems typically have multiple local optimal solutions that are not global. Solutions generated by algorithms such as gradients or coordinate descent methods may be trapped in local optima. [ 4 ] provided several local optimality conditions for a class of stationary points of problem ( 3 ), which is the closest to the one from an algorithm. Based on this, the authors provide an improved PMM algorithm and analyze its global convergence and local (sub)linear rate of the iterative sequence generated, and also explores the statistical properties of group Lasso. As a matter of fact, many scholars have conducted extensive research on the statistical properties of Lasso. For example, [ 48 ] investigated consistency results for estimators with general tree-structured norm regularizer, where group Lasso is its special case. [ 41 ] demonstrated the asymptotic properties of adaptive Lasso estimates. [ 43 , 42 ] explored multi-task