Non-Concave Penalized Likelihood with NP-Dimensionality

Jianqing Fan; Jinchi Lv

Source-linked AI summary

Non-Concave Penalized Likelihood with NP-Dimensionality

Jianqing Fan, Jinchi Lv

arXiv:0910.1119v1Oct 6, 2009math.ST

TL;DR

The paper addresses whether penalized likelihood can support consistent variable selection with oracle properties when GLM dimensionality grows at non-polynomial order. It analyzes folded-concave penalties, their global and restricted optimality, and coordinate-optimization solution paths, finding the claimed oracle results in this NP-dimensional setting while noting a limitation when p diverges.

Problem
The paper asks how large p can be relative to n while penalized likelihood methods retain oracle properties for variable selection in GLMs.
Method
The paper studies GLM penalized likelihood with folded-concave penalties, analyzes global optimality and oracle properties, and uses coordinate optimization to obtain solution paths.
Results
The methods achieve model-selection consistency with oracle properties for NP-dimensionality, with results also covering the L1 penalty at the boundary of the considered class.
Takeaways & Limitations
Penalized likelihood methods can be applicable to NP-dimensional variable-selection problems in GLMs under the paper’s stated conditions.
Takeaways & Limitations
When p diverges with n, the rate established in Theorem 3 does not itself provide the oracle property established in Theorem 4.

Abstract

from arXiv · show

Penalized likelihood methods are fundamental to ultra-high dimensional variable selection. How high dimensionality such methods can handle remains largely unknown. In this paper, we show that in the context of generalized linear models, such methods possess model selection consistency with oracle properties even for dimensionality of Non-Polynomial (NP) order of sample size, for a class of penalized likelihood approaches using folded-concave penalty functions, which were introduced to ameliorate the bias problems of convex penalty functions. This fills a long-standing gap in the literature where the dimensionality is allowed to grow slowly with the sample size. Our results are also applicable to penalized likelihood with the $L_1$-penalty, which is a convex function at the boundary of the class of folded-concave penalty functions under consideration. The coordinate optimization is implemented for finding the solution paths, whose performance is evaluated by a few simulation examples and the real data analysis.

1 Introduction

The paper studies variable selection in generalized linear models when the number of variables has non-polynomial growth relative to sample size. It develops penalized likelihood methods using folded-concave penalties and connects them to existing high-dimensional selection approaches.

Problem: NP-dimensionality is defined by log p = O(n^a) for some a ∈ (0, 1), extending variable-selection analysis beyond slowly growing dimensionality.The setting concerns GLMs with sparse regression coefficients and a deterministic design matrix.
Approach: Folded-concave penalties provide the paper’s main penalization framework, while the L1 penalty lies at the boundary of the considered class.The likelihood is regularized using a penalty function pλ(·) and tuning parameter λn.
Research gap: The paper asks whether penalized likelihood methods can retain oracle properties when dimensionality grows at NP order.Oracle properties combine model-selection consistency with estimation that mimics an estimator knowing the true model in advance.
Related work: The paper situates its contribution among prior work on LASSO, the Dantzig selector, covariance estimation, and earlier oracle-property results for lower-dimensional settings.Earlier generalized-likelihood results allowed p = o(n^1/5) or o(n^1/3).
Paper roadmap: The paper characterizes penalized-likelihood estimators, studies weak and full oracle properties, and develops coordinate optimization for concave-penalty solution paths.The stated organization also includes numerical studies and real-data analysis.

2 Non-concave penalized likelihood estimation

The section defines folded-concave penalized likelihood estimation for GLMs, characterizes local and global optimality, and extends global-optimality analysis to high-dimensional coordinate subspaces.

2.1 Penalty function: Condition 1 requires the normalized penalty to be increasing and concave, with a continuous derivative whose right derivative at zero is positive.Its derivative must also increase with λ, while the derivative at zero remains independent of λ.
2.1 Penalty function: SCAD and MCP satisfy Condition 1 and provide unbiasedness, sparsity, and continuity, whereas L1 satisfies the condition but lacks unbiasedness.The paper’s results also apply to L1-penalized regression, which lies at the boundary of the considered class.
2.2 Non-concave penalized likelihood estimator: Analytical study generally focuses on local maximizers because nonconcavity makes the global maximizer difficult to analyze directly.The restricted coordinate-subspace result provides a separate global-optimality perspective for p > n.
2.2 Non-concave penalized likelihood estimator: The estimator’s local optimality is characterized through conditions involving active and inactive coordinates, with strict inequalities yielding a strict local maximizer.For L1, concavity makes the objective concave, so global optimality is characterized by KKT conditions and subgradient constraints.
2.3.1 Global optimality: Under rank and curvature conditions, the NCPMLE is a global maximizer within a suitable likelihood sublevel set.For penalized least squares, the condition holds for sufficiently large SCAD or MCP parameters when covariate correlations are not too strong.
2.3.2 Restricted global optimality: When p > n, global optimality is studied on the union of s-dimensional coordinate subspaces; under conditions on each 2s-column submatrix, SCAD recovers the oracle estimator there.If the penalized estimator equals the oracle estimator, it has the oracle property.

3 Nonasymptotic weak oracle properties

The weak oracle property combines sparsity and L∞ consistency for non-concave penalized likelihood estimators under design, signal, response, and dimensionality conditions. The results allow exponentially growing dimensionality, extend to L1-penalized likelihood, and clarify its stronger design requirement.

The weak oracle property means estimated coefficients outside the true support are zero with probability tending to one, while active coefficients are L∞-consistent.This property is weaker than the oracle property of Fan and Li (2001).
3.1 Regularity conditions: The theory conditions on a standardized design matrix partitioned into active and inactive covariates, with assumptions controlling weighted correlations and eigenvalues.The relevant weighted multiple-regression coefficients quantify dependence between inactive and active covariates.
3.1 Regularity conditions: Condition (16) permits weighted inactive-on-active regression coefficients to grow at O(n^α1), whereas L1 regularization requires a uniformly less-than-one bound.For finite nonsparsity size, the condition is usually satisfied; the allowable dimensionality depends on correlations between active and inactive covariates.
3.2 Deviation bounds: The analysis derives estimator properties from concentration bounds for X^T Y around its mean under bounded or moment-controlled unbounded responses.The response assumptions include Gaussian and Poisson settings under the stated conditions, as well as sub-Gaussian errors.
3.3 Sampling properties: Theorem 2 allows log p = O(n^(1−2α)) and gives a probability bound tending to one for a non-concave penalized likelihood estimator with weak oracle properties.The theorem assumes s = o(n); the L∞ estimation loss is bounded by three terms under the technical assumptions.
3.3 Sampling properties: With concave penalties, γ can reach 1/2, but larger γ imposes more stringent design conditions and can reduce the dimensionality supported by penalized least squares.In the classical γ = 1/2 setting, the L2 consistency rate is O_P(√(s n^−1/2)).
3.3 Sampling properties of L1-based PMLE: For L1 penalization, the local maximizer is global, and the estimator has model-selection consistency with active-coordinate rate O(n^−γ log n).For penalized least squares, the result holds without a normality assumption when the probability bound is satisfied.

4 Oracle properties

Under regularity conditions, the non-concave penalized likelihood estimator has a sparse strict local maximizer with a convergence rate, and under additional conditions it achieves the oracle property. The required conditions relate dimensionality, minimum signal strength, penalty behavior, and sparsity.

The paper notes that the estimator has the convergence rate from Theorem 3 but not the oracle property from Theorem 4 when p diverges with n.This issue persists with growing dimensionality and was previously identified in finite-dimensional settings.
Theorem 3 establishes a strict local maximizer with bβ2 = 0 with probability tending to 1 and ∥bβ − β0∥2 = OP(√(s)n−1/2).The result holds under Conditions 1, 4, 5, and probability bound (22).
The oracle-property conditions connect the dimensionality that can be handled with the minimum signal strength required for favorable estimator properties.Theorem 3 emphasizes the signal-strength question, while Theorem 2 addresses the dimensionality question through related conditions.
Asymptotic normality requires an additional Lyapunov-related condition beyond the conditions used for existence and sparsity.Condition 6 supplies this additional requirement for Theorem 4.
Theorem 4 adds the oracle property when Condition 6 holds and s = o(n1/3).The theorem is stated under the conditions of Theorem 3 and yields the oracle-property result for the estimator.
For Gaussian linear regression, the additional restriction s = o(n1/3) can be relaxed because the corresponding term vanishes.This relaxation is specific to the Gaussian linear regression model.

5 Implementation

The paper uses iterative coordinate ascent to compute solution paths for penalized likelihoods with concave penalties. The algorithm updates coordinates through univariate penalized quadratic approximations while maintaining an ascent property.

Algorithm: Iterative coordinate ascent successively maximizes the penalized likelihood along coordinates for a sequence of regularization parameters.It is designed for large-scale problems with both n and p large.
Algorithm: Each coordinate update uses a second-order approximation of the likelihood and accepts the update only when the penalized likelihood strictly increases.Thus, the sequence of objective values is increasing for fixed λ.
Coordinate updates: The coordinatewise subproblem is a univariate penalized least-squares problem with analytical solutions for many common penalties.The same framework applies to commonly used GLMs, with formulas supplied for three popular models.
Path following: The solution path starts at a sufficiently large λ producing the zero maximizer and proceeds through decreasing regularization parameters.Iterations continue across coordinates and parameter values until convergence or prescribed iteration limits.
Path following: Figure 1 compares methods using boxplots of PE, L2 loss, and #S across 100 logistic-regression simulations with p = 25.The top panel uses BIC and the bottom panel uses SIC.

6 Numerical examples

Numerical experiments compare Lasso, SCAD, and MCP in logistic and Poisson regression across moderate and high dimensions. The non-concave penalties generally achieve sparse recovery, while Lasso selects larger models and can incur larger losses.

Logistic regression: In logistic regression with p = 25, SCAD and MCP had FN = 0 over 100 simulations under both BIC and SIC.Lasso also had median FN = 0 but selected larger models and had larger median losses.
Logistic regression: In logistic regression with p = 500 and 1000, SCAD and MCP had FN = 0 over almost all simulations, whereas Lasso had many nonzeros of FN.Five-fold cross-validation based on prediction error was used because information criteria broke down when p exceeded n.
Logistic regression: LASSO selected far larger model sizes than SCAD and MCP in high-dimensional logistic regression.The paper attributes this pattern to Lasso’s L1-penalty bias and the smaller λ selected by cross-validation.
Poisson regression: In high-dimensional Poisson regression with p = 500 and 1000, SCAD and MCP had FN = 0 over 100 simulations, while Lasso had median FN = 0 with some nonzeros.The tuning parameter was selected by BIC and five-fold cross-validation.

7 Discussions

The discussion concludes that non-concave penalized likelihood methods achieve model-selection consistency with oracle properties for NP-dimensional GLMs. Coordinate optimization is used to obtain solution paths, and numerical studies illustrate its performance.

Main conclusions: The paper establishes model-selection consistency with oracle properties for a class of non-concave penalized likelihood methods under NP-dimensionality in GLMs.NP-dimensionality is the setting where log p = O(n^a) for some a ∈ (0, 1).
Penalty class: The results include the L1 penalty as the convex boundary of the folded-concave penalty class under consideration.The discussion relates concave penalties to reduced bias relative to convex penalties.
Empirical illustration: Coordinate optimization was used to find solution paths, and simulations plus real-data analysis illustrated the performance of the non-concave methods.

8 Proofs

The proofs establish local and global properties of penalized-likelihood estimators through KKT conditions, curvature, concentration bounds, and sparse-support arguments. They also derive estimation and support-recovery guarantees under the stated conditions.

Local optimality: A local maximizer of the penalized likelihood satisfies KKT conditions, with subgradient behavior differing between zero and nonzero coefficients.The proof then applies second-order conditions on the active support.
Local optimality: Strict concavity on the active coordinate subspace gives a unique local maximizer, while projection arguments extend strict local maximality to the full parameter space.The comparison uses the penalized likelihood values of a vector and its projection onto the active subspace.
Global optimality: Concavity of the likelihood and suitable curvature conditions place the global maximizer within a convex level set where local maximization implies global maximization.The proof compares points on rays extending from the level-set boundary.
Estimation guarantees: Under the proof conditions, the estimator recovers the true sign pattern and has sup-norm error O(n^-γ log n), while inactive coefficients are zero.The resulting estimator is a strict local maximizer of the non-concave penalized likelihood.

A.1 Three commonly used GLMs

This section presents formulas used by the ICA algorithm for linear, logistic, and Poisson regression models. It also describes penalized-likelihood updates within the algorithm.

ICA uses model-specific formulas for linear, logistic, and Poisson generalized linear models.
Maximizing the penalized likelihood Q_n(β) is expressed as a penalized least-squares problem.
During coordinate updates, the subvector excluding the updated component remains identical to the current estimate.
For logistic regression, the GLM function is b(θ) = log(1 + e^θ) with dispersion parameter φ = 1.
For Poisson regression, the GLM function is b(θ) = e^θ with dispersion parameter φ = 1.

A.2 SCAD penalized least squares solution

This section derives the solution to a univariate SCAD-penalized least-squares problem. The solution is characterized by sign, magnitude, and piecewise threshold conditions.

The univariate problem minimizes an objective R(β) with SCAD penalty p_λ, using z ∈ R and Λ > 0.
The minimizer has the same sign as z and magnitude no greater than |z|, so it lies between 0 and z.
When λ < |z| ≤ aλ, the piecewise-linear gradient yields threshold-dependent solution behavior around (Λ + 1)λ.
For |z| > aλ, the solution equals z whenever |z| > (Λ + 1)λ; otherwise, it is selected by comparing R(z0) and R(z).