A General Theory of Concave Regularization for High-Dimensional Sparse Estimation Problems

By Cun-Hui Zhang, Tong Zhang. 2011

353 citations recorded by the source corpus.

Concave regularization methods provide natural procedures for sparse recovery. However, they are difficult to analyze in the high dimensional setting. Only recently a few sparse recovery results have been established for some specific local solutions obtained via specialized numerical procedures. Still, the fundamental relationship between these solutions such as whether they are identical or their relationship to the global minimizer of the underlying nonconvex formulation is unknown. The current paper fills this conceptual gap by presenting a general theoretical framework showing that under appropriate conditions, the global solution of nonconvex regularization leads to desirable recovery performance; moreover, under suitable conditions, the global solution corresponds to the unique sparse local solution, which can be obtained via different numerical procedures. Under this unified framework, we present an overview of existing results and discuss their connections. The unified view of this work leads to a more satisfactory treatment of concave high dimensional sparse estimation procedures, and serves as guideline for developing further numerical procedures for concave regularization.

Subfields: Computational Mechanics, Mathematical Physics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Best Subset Selection via a Modern Optimization Lens (2015, background): “…the usefulness of estimators obtained as minimizers of nonconvex penalized problems (1.3) over Lasso; see, for example, Fan and Lv (2011, 2013), Loh and Wainwright (2013), Lv and Fan (2009), van de Geer, Bühlmann and Zhou (2011), Zhang (2010a), Zhang and Zhang (2012), Zheng, Fan and Lv (2014).”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, neutral): “1.5.3].”
The Spike-and-Slab LASSO (2018, methodology): “To begin with, the threshold always satisfies (Zhang and Zhang 2012).”
Confidence intervals for low dimensional parameters in high dimensional linear models (2011, methodology): “We use the results in Sun and Zhang (2012), where properties of estimators (10) and (11) were established on the basis of a compatibility factor (van de Geer and Bühlmann, 2009) and sparse eigenvalues.”
Goodness‐of‐fit tests for high dimensional linear models (2015, methodology): “We refer the reader to van de Geer and Bühlmann (2009) and Zhang and Zhang (2012) for further details.”
Variable Selection in Heterogeneous Datasets: A Truncated-rank Sparse Linear Mixed Model with Applications to Genome-wide Association Studies (2017, neutral): “These methods overcome many of the aforementioned limitations at the cost of introducing nonconvexity in the optimization problem; a recent review of these methods can be found in [8].”
High‐dimensional quantile regression: Convolution smoothing and concave regularization (2021, background): “It is now a consensus that the 𝓁1-penalty induces non-negligible bias (Fan & Li, 2001; Zhang & Zhang, 2012; Zou, 2006), due to which the selected model tends to include spurious variables unless stringent conditions are imposed on the design matrix, such as the strong irrepresentable condition…”
What Objective Does Self-paced Learning Indeed Optimize? (2015, background): “, the hard and linear SPL regimes are equivalent to the optimizations on losses with the capped-norm penalty [11, 12, 13] and minimax concave plus penalty (MCP) [14], respectively.”
Regularized M-estimators with nonconvexity: statistical and algorithmic theory for local optima (2013, methodology): “Much existing work [3, 14] only establishes statistical consistency of global minima and then provides specialized algorithms for obtaining specific local optima that are provably close to global optima.”
Asymptotic normality and optimalities in estimation of large Gaussian graphical models (2013, background): “…has led to the sparse Riesz [Zhang and Huang (2008)], restricted eigenvalue [Bickel, Ritov and Tsybakov (2009), Koltchinskii (2009)], compatibility [van de Geer and Bühlmann (2009)], cone invertibility [Ye and Zhang (2010), Zhang and Zhang (2012)] and other similar conditions on the design matrix.”
STRONG ORACLE OPTIMALITY OF FOLDED CONCAVE PENALIZED ESTIMATION (2012, methodology): “Many have tried to address this issue (Zhang, 2010a; Fan and Lv, 2011; Zhang and Zhang, 2012).”