A knowledge-driven nonconvex square-root regularization framework for joint group sparsity and structured smoothness
Authors: Wanling Xie, Hu Yang
Organizations: College of Mathematics and Statistics, Hunan University of Technology and Business, Changsha, Hunan 410205, China · College of Mathematics and Statistics, Chongqing University, Chongqing, 401331, China
Structured sparse learning is a leading paradigm for high-dimensional data modeling, as it enables rigorous integration of domain-validated structural priors into the learning process. Among these priors, pre-defined grouped structure and piecewise smoothness are ubiquitous in real-world applications. However, most existing structured regularization methods are built on squared loss and convex penalties, rarely jointly model these two complementary structural priors, and suffer from two key limitations. Their optimal tuning parameters are sensitive to the unknown noise level σ due to the squared loss. Meanwhile, convex penalties induce inherent estimation bias and severe over-shrinkage of large magnitudes. To address these issues, we propose a knowledge-driven Nonconvex Structured Smooth Adjustment for Square-Root Regularization (NS3R), which unifies the σ-free square-root loss with a joint nonconvex ℓ2,q penalty (0<q<1) to simultaneously encode group sparsity and structured smoothness priors. Theoretically, we establish rigorous non-asymptotic error bounds for the NS3R estimator under a mild (2,q)-group restricted compatibility condition. Computationally, we develop an efficient double-screened IRLS with thresholding (DS-IRLS-th) algorithm, which adopts a nested double-screening strategy to reduce computational cost and improve numerical stability, with provable global convergence for the resulting nonconvex optimization problem. Extensive experiments on synthetic and real-world data demonstrate that NS3R consistently outperforms state-of-the-art methods in finite-sample settings.
Figures & tables
Figure 1: The success rates and average running times of DS-IRLS-th algorithm with different threshold τ2 .
Figure 2: The success rates and false positive rates of DS-IRLS-th algorithm with different exponent q .
Figure 3: Convergence performance of the DS-IRLS-th algorithm under sparsity levels 1% and 20% .
Smooth lasso
Spline lasso
SRFL
GSRL
SSASR
NS 3 R
Example 1
FDR
47.00(0.02)
47.00(0.03)
5.54(0.05)
0.00(0.00)
0.00(0.00)
0.00(0.00)
FNR
1.28(0.02)
1.45(0.02)
0.00(0.00)
0.00(0.00)
10.20(0.10)
0.00(0.00)
EE
30.56(3.14)
30.71(3.32)
3.43(1.72)
2.64(0.92)
1.51(0.52)
0.20(0.05)
PMSE
31.77(3.16)
31.93(3.34)
4.44(1.73)
3.68(0.93)
2.53(0.52)
1.20(0.05)
Example 2
Table 1: Simulation results across all examples, evaluating FDR, FNR, EE, and PMSE across 100 replications.
Method
Frequently selected genes ( ≥30% in 100 simulations)
Recently, several instances of non-Euclidean SGD, including SignSGD, Lion, and Muon, have attracted significant interest from the optimization community due to their practical success in training deep neural networks. Consequently, a number of works have attempted to explain this success by developing theoretical convergence analyses. Unfortunately, these results cannot properly justify the superior performance of these methods, as they could not beat the convergence rate of vanilla Euclidean SGD. We resolve this important open problem by developing a new unified convergence analysis under the structured smoothness and gradient noise assumption. In particular, our results indicate that non-Euclidean SGD (i) can exploit the sparsity or low-rank structure of the upper bounds on the Hessian and gradient noise, (ii) can provably benefit from popular algorithmic tools such as extrapolation or momentum variance reduction, and (iii) can match the state-of-the-art convergence rates of adaptive and more complex optimization algorithms such as AdaGrad and Shampoo.
We propose a unified fractional regularization framework for sparse signal recovery based on the ℓ1/ℓpq model. This model generalizes several widely used sparsity-promoting regularizers and provides additional flexibility through the parameters p and q. Our main theoretical contribution is the characterization of the equivalence between the first-order stationary points of the ℓ1/ℓpq formulation and the subtractive ℓ1−αℓp model, thereby offering a unified perspective on these nonconvex regularizers. In addition, we establish a new sufficient recovery condition under the Restricted Isometry Property (RIP), which shows that the proposed framework can provide relaxed recovery guarantees and improved robustness. To solve the resulting nonconvex problem, we develop a majorization--minimization (MM) algorithm and prove its convergence by using the Kurdyka--Łojasiewicz (KL) property. Numerical experiments on sparse recovery problems with different sensing matrices and MRI reconstruction demonstrate that the proposed approach outperforms existing methods in recovery accuracy.
Yinhao Zhao, Yaohua Hu, Hao Wang
School of Information Science and Technology, ShanghaiTech University, 201210
Sparse recovery in linear systems underpins applications from signal processing to high-dimensional regression. Sparse Bayesian Learning, grounded in the principle of automatic relevance determination (ARD), offers a practical Bayesian mechanism for feature sparsity via marginal likelihood optimization. Yet, its reliance on a homoscedastic noise model renders it sensitive to data contaminations such as outliers or misspecified noise, harming model fit and predictions. Instead, we propose jointly learning individual feature and sample relevancies, enabling simultaneous model and data sparsification via a single Bayesian objective. This symmetric pruning of model and data offers a natural extension that preserves conjugacy, admits closed-form updates for standard optimization procedures, and aligns with perspectives from robust regression and influence functions. Empirical results across diverse regression tasks affirm that a joint ARD approach consistently yields both sparse and robust prediction models.
Alexander Timans, Thomas Möllenhoff, Christian A. Naesseth +2
1UvA-Bosch Delta Lab, University of Amsterdam · 2RIKEN Center for AI Project, Tokyo, Japan · Department of Computer Science, Johns Hopkins University.