Cross validation in sparse linear regression with piecewise continuous nonconvex penalties and its acceleration
Open Access
- 18 September 2019
- journal article
- research article
- Published by IOP Publishing in Journal of Physics A: Mathematical and Theoretical
- Vol. 52 (41) , 414003
Abstract
We investigate the signal reconstruction performance of sparse linear regression in the presence of noise when piecewise continuous nonconvex penalties are used. Among such penalties, we focus on the smoothly clipped absolute deviation (SCAD) penalty. The contributions of this study are three-fold: we first present a theoretical analysis of a typical reconstruction performance, using the replica method, under the assumption that each component of the design matrix is given as an independent and identically distributed (i.i.d.) Gaussian variable. This clarifies the superiority of the SCAD estimator compared with in a wide parameter range, although the nonconvex nature of the penalty tends to lead to solution multiplicity in certain regions. This multiplicity is shown to be connected to replica symmetry breaking in the spin-glass theory, and associated phase diagrams are given. We also show that the global minimum of the mean square error between the estimator and the true signal is located in the replica symmetric phase. Second, we develop an approximate formula efficiently computing the cross-validation error without actually conducting the cross-validation, which is also applicable to the non-i.i.d. design matrices. It is shown that this formula is only applicable to the unique solution region and tends to be unstable in the multiple solution region. We implement instability detection procedures, which allows the approximate formula to stand alone and resultantly enables us to draw phase diagrams for any specific dataset. Third, we propose an annealing procedure, called nonconvexity annealing, to obtain the solution path efficiently. Numerical simulations are conducted on simulated datasets to examine these results to verify the consistency of the theoretical results and the efficiency of the approximate formula and nonconvexity annealing. The characteristic behaviour of the annealed solution in the multiple solution region is addressed. Another numerical experiment on a real-world dataset of Type Ia supernovae is conducted; its results are consistent with those of earlier studies using the formulation. A MATLAB package of numerical codes implementing the estimation of the solution path using the annealing with respect to in conjunction with the approximate CV formula and the instability detection routine is distributed in Obuchi (2019https://github.com/T-Obuchi/SLRpackage_AcceleratedCV_matlab).Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- The Elements of Statistical Learning: Data Mining, Inference, and PredictionJournal of the Royal Statistical Society Series A: Statistics in Society, 2010
- Nearly unbiased variable selection under minimax concave penaltyThe Annals of Statistics, 2010
- Sparse inverse covariance estimation with the graphical lassoBiostatistics, 2007
- Randomly Spread CDMA: Asymptotics Via Statistical PhysicsIEEE Transactions on Information Theory, 2005
- Adaptive and self-averaging Thouless-Anderson-Palmer mean-field theory for probabilistic modelingPhysical Review E, 2001
- Tractable Approximations for Probabilistic Models: The Adaptive Thouless-Anderson-Palmer Mean Field ApproachPhysical Review Letters, 2001
- Heuristics of instability and stabilization in model selectionThe Annals of Statistics, 1996
- Statistical mechanics of the maximum-likelihood density estimationPhysical Review E, 1994
- Scaling laws in learning of classification tasksPhysical Review Letters, 1993
- Stability of the Sherrington-Kirkpatrick solution of a spin glass modelJournal of Physics A: General Physics, 1978