Phase transition and higher order analysis of L_q regularization under dependence

2022/11/19 by Huang, Hanwen, Zeng, Peng, Yang, Qinglong
#Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2211.10541

Abstract

We study the problem of estimating a k-sparse signal β₀∈\bf R^p from a set of noisy observations \bf y∈\bf Rⁿ under the model \bf y=\bf Xβ+\bf w, where \bf X∈\bf R^{n× p} is the measurement matrix the row of which is drawn from distribution N(0,Σ). We consider the class of L_q-regularized least squares (LQLS) given by the formulation β(λ,q)=argmin_β∈\bf R^p(1)/(2)‖\bf y-\bf Xβ‖²₂+λ‖β‖_q^q, where ‖⋅‖_q (0≤ q≤ 2) denotes the L_q-norm. In the setting p,n,k→∞ with fixed k/p=ε and n/p=δ, we derive the asymptotic risk of β(λ,q) for arbitrary covariance matrix Σ which generalizes the existing results for standard Gaussian design, i.e. X_ij\overseti.i.d∼N(0,1). We perform a higher-order analysis for LQLS in the small-error regime in which the first dominant term can be used to determine the phase transition behavior of LQLS. Our results show that the first dominant term does not depend on the covariance structure of Σ in the cases 0≤ q< 1 and 1< q≤ 2 which indicates that the correlations among predictors only affect the phase transition curve in the case q=1 a.k.a. LASSO. To study the influence of the covariance structure of Σ on the performance of LQLS in the cases 0≤ q< 1 and 1

Related

• Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques
• LASSO risk and phase transition under dependence
• Low noise sensitivity analysis of Lq-minimization in oversampled systems
• Does ℓ_p-minimization outperform ℓ₁-minimization?
• Does generalization performance of l^q regularization learning depend on q? A negative example