×
Huo, Xiaoming; Chen, Jie

Complexity of penalized likelihood estimation. (English) Zbl 1195.62035

J. Stat. Comput. Simulation 80, No. 7, 747-759 (2010).
Summary: We show that for a class of penalty functions, finding the global optimizer in the penalized least-squares estimation is equivalent to the ‘exact cover by 3-sets’ problem, which belongs to a class of NP-hard problems. The NP-hardness result is then extended to the cases of penalized least absolute deviations regression and a special class of penalized support vector machines. We discuss its implication in statistics. To the best of our knowledge, this is the first formal documentation on the complexity of this type of problem.

Cited in 5 Documents

MSC:

62G05 Nonparametric estimation
68T05 Learning and adaptive systems in artificial intelligence
65Y20 Complexity and performance of numerical algorithms
62-04 Software, source code, etc. for problems pertaining to statistics
68Q25 Analysis of algorithms and problem complexity

Keywords:

NP-hardness; regularization; penalized likelihood estimator; penalized least squares estimates; penalized least absolute deviations regression; penalized support vector machines
Cite Review PDF
Full Text: DOI

References:

[1] Eggermont P. P.B., Maximum Penalized Likelihood Estimation, Vol. I: Density Estimation (2001) · Zbl 0984.62026
[2] DOI: 10.1198/016214501753382273 · Zbl 1073.62547 · doi:10.1198/016214501753382273
[3] DOI: 10.1198/016214501753208942 · Zbl 1072.62561 · doi:10.1198/016214501753208942
[4] Fan, J. and Li, R. Proceedings of the Madrid International Congress of Mathematicians. Statistical Challenges with High Dimensionality: Feature Selection in Knowledge Discovery,
[5] Garey M. R., Computers and Intractability. A Guide to the Theory of NPcompleteness (1979)
[6] DOI: 10.1137/S0097539792240406 · Zbl 0827.68054 · doi:10.1137/S0097539792240406
[7] DOI: 10.1214/009053606000001334 · Zbl 1125.62079 · doi:10.1214/009053606000001334
[8] Ni X. S., New results in detection, estimation, and model selection (2006)
[9] DOI: 10.1080/00949658208810560 · Zbl 0482.65080 · doi:10.1080/00949658208810560
[10] Tibshirani R., J. Roy. Statist. Soc. Ser. B 58 pp 267– (1996)
[11] DOI: 10.2307/1269656 · Zbl 0775.62288 · doi:10.2307/1269656
[12] DOI: 10.1093/biomet/81.3.425 · Zbl 0815.62019 · doi:10.1093/biomet/81.3.425
[13] DOI: 10.1137/S0036139997327794 · Zbl 0991.94015 · doi:10.1137/S0036139997327794
[14] Gentle J. E., Commun. Statist. B 6 pp 313– (1977)
[15] Bloomfield P., Least Absolute Deviations: Theory, Applications, and Algorithms (1983) · Zbl 0536.62049
[16] Zhu J., Neural Information Processing Systems 16 (2003)
[17] DOI: 10.1214/009053607000000802 · Zbl 1142.62027 · doi:10.1214/009053607000000802
[18] DOI: 10.1111/j.1467-9868.2008.00674.x · doi:10.1111/j.1467-9868.2008.00674.x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.