PaperlayerView exact revision on arXiv

Source-linked AI summary

A knowledge-driven nonconvex square-root regularization framework for joint group sparsity and structured smoothness

Wanling Xie, Hu Yang

arXiv:2610.35428v1stat.MLcs.LGstat.CO

TL;DR

Structured sparse methods often use squared loss and convex penalties, and commonly do not jointly represent group sparsity and smoothness. NS3R combines a σ-free square-root loss with a joint nonconvex penalty, and the authors report better finite-sample performance than state-of-the-art methods on synthetic and real-world gene-expression data.

  • Problem

    Many structured regularization methods use squared loss and convex penalties, seldom jointly model group sparsity and smoothness, and require tuning tied to unknown noise levels.

    Source: §1 · p. 3

  • Method

    NS3R combines a σ-free square-root loss with a joint nonconvex ℓ2,q penalty to encode group sparsity and structured smoothness.

    Source: §1 · pp. 3–4

  • Results

    NS3R delivers consistently better finite-sample performance than state-of-the-art regularization methods on synthetic and real-world gene-expression datasets.

    Source: §6 · p. 24

  • Takeaways & Limitations

    The framework provides non-asymptotic error guarantees under mild regularity conditions, and its algorithm has provable global convergence under mild initial-value conditions.

    Source: §1 · p. 4

    The analysis assumes non-overlapping groups and Gaussian noise with unknown covariance σ²I_n.

    Source: §1 · p. 2, §2.1 · p. 5

Abstract

from arXiv · show

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 $\sigma$ 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 (NS$^3$R), which unifies the $\sigma$-free square-root loss with a joint nonconvex $\ell_{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 NS$^3$R 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 NS$^3$R consistently outperforms state-of-the-art methods in finite-sample settings.

1. Introduction

Structured sparse methods often model group sparsity or smoothness separately, while squared-loss tuning depends on unknown noise and convex penalties can bias estimates. NS3R combines a σ-free square-root loss with a joint nonconvex penalty, alongside theoretical guarantees and a convergent algorithm.

1. Introduction

  • Existing structured methods often fail to jointly model group sparsity and smoothness, while squared-loss tuning depends on unknown noise and convex penalties incur estimation bias.The introduction identifies these as limitations of existing structured square-root regularization methods.Source: §1 · pp. 2–3
  • NS3R combines a σ-free square-root loss with a joint nonconvex ℓ2,q penalty to encode group sparsity and structured smoothness.The framework is proposed for high-dimensional linear regression.Source: §1 · pp. 3–4
  • The NS3R estimator has non-asymptotic oracle inequalities under mild regularity conditions, providing theoretical guarantees for high-dimensional use.The introduction describes the conditions as among the mildest in the literature.Source: §1 · p. 4
  • DS-IRLS-th uses nested double screening to reduce computational cost and improve numerical stability, with global convergence under mild initial-value conditions.Experiments on synthetic and real-world data are reported to validate fast convergence and favorable performance in p ≫ n settings.Source: §1 · p. 4

2. Methodology

NS3R combines square-root loss with a joint nonconvex penalty to model group sparsity and within-group smoothness. Its theoretical guarantees use a weak (2,q)-GRCC and include noise-level-independent tuning.

2.1. The NS3R model

  • The model assumes predefined groups do not overlap, so each feature belongs to at most one group..Source: §2.1 · p. 5
  • NS3R combines square-root residual loss with a joint nonconvex ℓ2,q penalty to encode group sparsity and structured smoothness.The paper presents it as a general nonconvex extension of SSASR.Source: §2.1 · pp. 5–6
  • The first penalty induces group-level sparsity, while the nonconvex Inner Group Total Variation term imposes smoothness within groups.The two tuning parameters control the penalties separately; α balances their relative contributions.Source: §2.1 · p. 5
  • The nonconvex regularization alleviates convex-penalty estimation bias and provides stronger sparsity induction and smoothness modeling, especially for weak signals in high dimensions.These comparisons are made against the convex SSASR counterpart.Source: §2.1 · p. 6

2.2. Theoretical Properties of NS3R

  • Under the weak (2,q)-GRCC, the estimator has oracle inequalities, although its rates are not superior to classical ℓ2,1 group Lasso rates.The weaker condition covers cases where standard group restricted eigenvalue conditions fail and group Lasso may be inconsistent.Source: §2.2 · pp. 8–9
  • The tuning parameters are independent of the unknown noise level σ, avoiding the need to estimate σ for regularization tuning.The paper notes that σ is difficult to estimate in high-dimensional settings.Source: §2.2 · p. 9

3. Algorithm and global convergence analysis

The section develops DS-IRLS-th for the nonconvex square-root objective and proves global convergence to a stationary point under stated regularity and threshold conditions.

3.1. Subdifferential and optimality conditions

  • The section derives the subdifferential and optimality conditions for the nonconvex objective, defining stationary points through the generalized Fermat rule.These conditions support both the algorithm construction and convergence analysis.Source: §3.1 · p. 10

3.2. Double-screened IRLS with thresholding algorithm

  • DS-IRLS-th applies majorization-minimization through reweighted least-squares steps, with nested screening of group coefficients and within-group differences.It optimizes over the shrinking group support and constrains coefficients to be constant within groups whose within-group differences fall below the screening threshold.Source: §3.2 · pp. 11–12

3.3. Global convergence analysis

  • Under a uniformly positive residual norm and specified threshold bounds, DS-IRLS-th converges globally to a stationary point and has finite length.The proof uses the Kurdyka–Łojasiewicz framework and does not require the proximal term used in most existing KL-based analyses.Source: §3.3 · pp. 13–15

4. Numerical experiments

The experiments tune DS-IRLS-th, assess its convergence, and compare NS3R with competing methods across simulated signal structures and conditions. NS3R performs best overall across the reported scenarios.

4. Numerical experiments

  • The simulations use n=250, p=1000, 100 groups of 10 features, and vary the number of active groups; coefficients within active groups are set to 3.The experiments use 100 independently generated datasets per sparsity level and set σ=0.01.Source: §4 · pp. 15–16

4.1. Choice of 휏1, 휏2

  • τ1=10^-2 and τ2=10^-6 provide the reported balance between model-selection accuracy and computational efficiency, and are fixed for subsequent experiments.The threshold comparison averages success rates and running times over 100 trials.Source: §4.1 · p. 16, Figure 1 · p. 17

4.2. Choice of 푞

  • q=0.5 gives the best overall performance among the tested exponents, while q=0.9 performs worst; the experiments fix q=0.5 thereafter.The comparison tests q values from 0.1 to 0.9 across sparsity levels.Source: §4.2 · pp. 16–17, Figure 2 · p. 17

4.3. Convergence of the DS-IRLS-th algorithm

  • Across the DS-IRLS-th experiments at sparsity levels of 1% and 20%, relative errors decrease monotonically and converge rapidly within just a few iterations, demonstrating fast convergence.Figure 3 presents objective function values and relative errors across 50 iterations.Source: §4.3 · pp. 17–18

4.4. Comparisons to other methods

  • The comparisons use EBIC tuning and evaluate false discovery rate, false negative rate, estimation error, and test-set prediction mean squared error.For methods with two tuning parameters, λ2=θλ1, with θ selected from a predefined grid.Source: §4.4 · pp. 18–19

4.4.1. Piecewise Constant Signals

  • The piecewise-constant signal scenarios vary noise and covariate correlation, with one active group carrying a weak signal of magnitude 1.The other four active groups have magnitudes 4, 5, 6, and 7 in the baseline setting.Source: §4.4.1 · pp. 19–20

4.4.2. Complex Smooth Signals

  • The complex-smooth scenarios assign active groups distinct linear, sinusoidal, quadratic, or exponential patterns and vary noise and covariate correlation.The baseline uses σ=1 and an identity correlation matrix.Source: §4.4.2 · p. 20

4.4.3. Numerical Results

  • NS3R consistently outperforms competitors in variable selection, estimation, and prediction across all simulation scenarios, with the smallest replication standard deviations.SSASR ranks second in all cases; NS3R’s advantage is more pronounced with independent covariates, and its performance declines only mildly as noise rises from σ=1 to σ=5.Source: §4.4.3 · pp. 20–21, Table 1 · p. 21

5. An application to gene expression microarray analysis

The gene-expression analysis uses biological evidence to group genes and compares NS3R with square-root fused Lasso and xtune Lasso. NS3R selects smaller, more stable gene sets with lower mean PMSE, while frequently selected genes include validated bone-metabolism regulators.

5. An application to gene expression microarray analysis

  • The analysis groups genes using published functional evidence and bone-metabolism pathways, retaining biologically informed groups and sorting genes by marginal importance to bone density.The dataset contains 22,815 probe sets from bone biopsies of 84 women; the outcome is standardized hip T-scores.Source: §5 · p. 22
  • Across 100 test-set simulations, NS3R selects substantially fewer genes with lower variability and achieves the lowest mean PMSE versus xtune Lasso and square-root fused Lasso.Table 2 reports mean selected-gene counts and mean PMSE, with standard deviations, across the replications.Source: §5 · p. 22, Table 2 · p. 23
  • Genes selected by NS3R in at least 30% of simulations include Wnt regulators DKK1, SOST, and WIF1, which are robustly identified across all 100 simulations.The competing methods select more genes at lower frequencies; most low-frequency selections lack validated functional links to bone metabolism.Source: §5 · pp. 22–23
  • The authors conclude that NS3R balances sparse selection, prediction, and biological interpretability for high-dimensional gene-expression analysis.They attribute this approach to incorporating structured smoothness adapted to gene-group structure.Source: §5 · p. 23

6. Conclusions and future works

The conclusions present NS3R as a square-root-loss framework with a joint nonconvex penalty, theoretical error bounds, and a convergent algorithm. Experiments support its finite-sample performance, while future work proposes broader priors, penalties, and data structures.

6. Conclusions and future works

  • NS3R combines a sigma-free square-root loss and joint nonconvex ℓ2,q penalty to encode group sparsity and structured smoothness, with non-asymptotic error bounds under a mild regularity condition.The design is intended to mitigate convex-regularizer over-shrinkage and tuning dependence on unknown noise level sigma.Source: §6 · p. 23
  • DS-IRLS-th has proven global convergence under mild initial-value conditions, and experiments report convergence within few iterations and runtime below 1 second for moderate-sized datasets.Its nested double-screening uses support shrinking to reduce computational complexity across iterations.Source: §6 · pp. 23–24
  • Synthetic and real-world gene-expression experiments show better finite-sample performance than state-of-the-art regularization methods.The conclusion describes these experiments as comprehensive.Source: §6 · p. 24
  • Future work proposes bi-level selection, additional nonconvex penalties, and graph-structured data to address more flexible priors and complex settings.The named penalties include group SCAD, group MCP, and capped folded concave penalties.Source: §6 · p. 24

A.1. Subdifferential

The appendix introduces regular and limiting subdifferentials for proper lower-semicontinuous functions, with both defined at points in the function's domain.

A.1. Subdifferential

  • The appendix recalls subdifferential definitions as background for its technical material.It identifies the function class as proper and lower semicontinuous.Source: §A.1 · p. 24
  • The regular subdifferential is defined at x in the domain of phi.The passage introduces this definition but does not include its formula.Source: §A.1 · p. 24
  • The limiting subdifferential is also defined at x in the domain of phi.The passage introduces this definition but does not include its formula.Source: §A.1 · p. 24

A.2. KL Property and Semi-Algebraic Functions

The appendix reviews the KL property and semi-algebraic functions used in convergence analysis. It states that the NS3R objective is semi-algebraic, hence a KL function, for rational q in (0, 1).

A.2. KL Property and Semi-Algebraic Functions

  • The KL property is described as fundamental to convergence analysis of many optimization algorithms.The appendix notes that semi-algebraic, subanalytic, and log-exp functions are KL functions.Source: §A.2 · p. 25
  • A function with the KL property at every point of its limiting subdifferential domain is called a KL function.The appendix presents the KL inequality as part of the property’s definition.Source: §A.2 · p. 25
  • The appendix introduces semi-algebraic sets and functions through their defining properties.It identifies a real semi-algebraic set as a subset of R^p and a semi-algebraic function through its graph.Source: §A.2 · p. 25
  • For rational q in (0, 1), the NS3R objective is semi-algebraic and therefore has the KL property at every point relevant to the convergence analysis.The argument uses the semi-algebraicity of the square-root loss and penalty terms, along with closure under finite sums and compositions.Source: §A.2 · pp. 25–26

A.3. Supporting Preliminary Lemmas

The preliminary appendix supplies inequalities used in the main proofs and establishes that the algorithm’s group-support and difference-active sets stabilize after finitely many steps.

A.3. Supporting Preliminary Lemmas

  • The appendix identifies two technical lemmas as key inequalities for proving the main results.The displayed preliminary lemma statements include norm relations, but their inequalities are not stated in the supplied text.Source: §A.3 · p. 26
  • For 0 < q < 1, the preliminary inequalities use concavity of t^q to bound a sum of q-powers when the corresponding norms sum to at most M.The proof applies Jensen’s inequality under u + v ≤ M.Source: §A.3 · pp. 26–27
  • The group-support and difference-active sets shrink monotonically and reach fixed sets in finitely many steps when the number of groups is finite.The lemma states G_k+1 ⊆ G_k and A_k+1 ⊆ A_k.Source: §A.3 · p. 28

Appendix B Technical Proofs of Main Results

The appendix proves the paper’s main theoretical and algorithmic claims through technical bounds and optimality arguments. It establishes convergence of the DS-IRLS-th iterates to a stationary point and a finite-length property.

Appendix B Technical Proofs of Main Results

  • The proof characterizes the objective’s groupwise subdifferential, including the case where a group coefficient or its difference is zero.In those cases, at least one penalty subdifferential is the full R^T_j space.Source: Appendix B · p. 33
  • For the constrained subproblem, the proof invokes positive definiteness of the Lagrangian Hessian and linearly independent equality-constraint gradients to establish uniqueness of the Lagrange multiplier.The stated conditions apply at a KKT point.Source: Appendix B · p. 36
  • When the screened group set is unchanged, the objective does not increase; when it shrinks, its increase is bounded by the number of removed groups times ||X||_2 τ_1.The proof also states that the objective sequence is bounded.Source: Appendix B · p. 37
  • The DS-IRLS-th iterate sequence converges to a stationary point of F(β), and the sequence has the finite-length property.The proof uses sufficient descent, relative boundedness of subdifferentials, bounded iterates, and the Kurdyka–Łojasiewicz property.Source: Appendix B · p. 41
Loading 2610.35428v1…