Efficient Sparse Recovery via Adaptive Non-Convex Regularizers with Oracle Property

Ming Lin Tsinghua University, Rong Jin Michigan State University, Changshui Zhang Tsinghua University
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:441-450, 2014.

Abstract

The main shortcoming of sparse recovery with a convex regularizer is that it is a biased esti- mator and therefore will result in a suboptimal performance in many cases. Recent studies have shown, both theoretically and empirically, that non-convex regularizer is able to overcome the biased estimation problem. Although multiple algorithms have been developed for sparse recov- ery with non-convex regularization, they are ei- ther computationally demanding or not equipped with the desired properties (i.e. optimal recovery error, selection consistency and oracle property). In this work, we develop an algorithm for effi- cient sparse recovery based on proximal gradient descent. The key feature of the proposed algo- rithm is introducing adaptive non-convex regu- larizers whose shrinking threshold vary over it- erations. The algorithm is compatible with most popular non-convex regularizers, achieves a ge- ometric convergence rate for the recovery er- ror, is selection consistent, and most importantly has the oracle property. Based on the proposed framework, we suggest to use a so–called ACCQ regularizer, which is equivalent to zero proximal projection gap adaptive hard-thresholding. Ex- periments with both synthetic data sets and real images verify both the efficiency and effective- ness of the proposed method compared to the state-of-the-art methods for sparse recovery.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-university14m, title = {Efficient Sparse Recovery via Adaptive Non-Convex Regularizers with Oracle Property}, author = {University, Ming Lin Tsinghua and University, Rong Jin Michigan State and University, Changshui Zhang Tsinghua}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {441--450}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/university14m/university14m.pdf}, url = {https://proceedings.mlr.press/r12/university14m.html}, abstract = {The main shortcoming of sparse recovery with a convex regularizer is that it is a biased esti- mator and therefore will result in a suboptimal performance in many cases. Recent studies have shown, both theoretically and empirically, that non-convex regularizer is able to overcome the biased estimation problem. Although multiple algorithms have been developed for sparse recov- ery with non-convex regularization, they are ei- ther computationally demanding or not equipped with the desired properties (i.e. optimal recovery error, selection consistency and oracle property). In this work, we develop an algorithm for effi- cient sparse recovery based on proximal gradient descent. The key feature of the proposed algo- rithm is introducing adaptive non-convex regu- larizers whose shrinking threshold vary over it- erations. The algorithm is compatible with most popular non-convex regularizers, achieves a ge- ometric convergence rate for the recovery er- ror, is selection consistent, and most importantly has the oracle property. Based on the proposed framework, we suggest to use a so–called ACCQ regularizer, which is equivalent to zero proximal projection gap adaptive hard-thresholding. Ex- periments with both synthetic data sets and real images verify both the efficiency and effective- ness of the proposed method compared to the state-of-the-art methods for sparse recovery.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Efficient Sparse Recovery via Adaptive Non-Convex Regularizers with Oracle Property %A Ming Lin Tsinghua University %A Rong Jin Michigan State University %A Changshui Zhang Tsinghua University %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-university14m %I PMLR %P 441--450 %U https://proceedings.mlr.press/r12/university14m.html %V R12 %X The main shortcoming of sparse recovery with a convex regularizer is that it is a biased esti- mator and therefore will result in a suboptimal performance in many cases. Recent studies have shown, both theoretically and empirically, that non-convex regularizer is able to overcome the biased estimation problem. Although multiple algorithms have been developed for sparse recov- ery with non-convex regularization, they are ei- ther computationally demanding or not equipped with the desired properties (i.e. optimal recovery error, selection consistency and oracle property). In this work, we develop an algorithm for effi- cient sparse recovery based on proximal gradient descent. The key feature of the proposed algo- rithm is introducing adaptive non-convex regu- larizers whose shrinking threshold vary over it- erations. The algorithm is compatible with most popular non-convex regularizers, achieves a ge- ometric convergence rate for the recovery er- ror, is selection consistent, and most importantly has the oracle property. Based on the proposed framework, we suggest to use a so–called ACCQ regularizer, which is equivalent to zero proximal projection gap adaptive hard-thresholding. Ex- periments with both synthetic data sets and real images verify both the efficiency and effective- ness of the proposed method compared to the state-of-the-art methods for sparse recovery. %Z Reissued by PMLR on 04 October 2026.
APA
University, M.L.T., University, R.J.M.S. & University, C.Z.T.. (2014). Efficient Sparse Recovery via Adaptive Non-Convex Regularizers with Oracle Property. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:441-450 Available from https://proceedings.mlr.press/r12/university14m.html. Reissued by PMLR on 04 October 2026.

Related Material