A new regularization for sparse optimization

Abstract

Several numerical studies have shown that non-convex sparsity-induced regularization can outperform the convex ℓ₁-penalty. In this article, we introduce a new non-convex and non-smooth regularization. This new regularization is a continuous and separable function which provides a tighter approximation to the cardinality function than any ℓ_q-penalty (0 < q < 1). We then apply the Proximal Gradient Method to solve a regularized optimization problem with the new regularization. The convergence analysis shows that the algorithm converges to a critical point and we also provide a pseudo-code for fast implementation. In addition, we conduct a simple numerical experiment with a regularized least square problem to illustrate the performance of the new regularization.

References

• H. Attouch, J. Bolte, and B. F. Svaiter. “Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss–Seidel methods”. In: Math. Program. 137 (2013), pp. 91–129. doi: 10.1007/s10107-011-0484-9.
• A. Beck. “First-order methods in optimization”. In: MOS-SIAM Series on optimization. Society for Industrial and Applied Mathematics, 2017. doi: 10.1137/1.9781611974997.
• J. Bolte, A. Daniilidis, A. Lewis, and M. Shiota. “Clarke subgradients of stratifiable functions”. In: SIAM J. Optim. 18 (2007), pp. 556–572. doi: 10.1137/060670080.
• R. Chartrand. “Exact reconstruction of sparse signals via nonconvex minimization”. In: IEEE Sig. Process. Lett. 14.10 (2007), pp. 707–710. doi: 10.1109/LSP.2007.898300.
• D. L. Donoho, M. Elad, and V. N. Temlyakov. “Stable recovery of sparse overcomplete representations in the presence of noise”. In: IEEE Trans. Inform. Theory 52.1 (2006), pp. 6–18. doi: 10.1109/TIT.2005.860430.
• L. van den Dries and P. Speissegger. “The field of reals with multisummable series and the exponential function”. In: Proc. London Math. Soc. 81 (2000), pp. 513–565. doi: 10.1112/S0024611500012648.
• J. Fan and R. Li. “Variable selection via nonconcave penalized likelihood and Its oracle properties”. In: J. Am. Stat. Assoc. 96 (2001), pp. 1348–1360. doi: 10.1198/016214501753382273.
• T. Hastie, R. Tibshirani, and M. Wainwright. Statistical learning with sparsity: The lasso and generalizations. Chapman and Hall, 2015. doi: 10.1201/b18401.
• J. Lv and Y. Fan. “A unified approach to model selection and sparse recovery using regularized least squares”. In: Annal. Stat. 37.6A (2009), pp. 3498–3528. doi: 10.1214/09-AOS683.
• G. Marjanovic and V. Solo. “On lq optimization and matrix completion”. In: IEEE Trans. Signal Process. 60.11 (2012), pp. 5714–5724. doi: 10.1109/TSP.2012.2212015.
• R. Mazumder, J. H. Friedman, and T. Hastie. “SparseNet: Coordinate descent with nonconvex penalties”. In: J. Am. Stat. Assoc. 106 (2011), pp. 1125–1138. doi: 10.1198/jasa.2011.tm09738.
• F. Wen, L. Chu, P. Liu, and R. C. Qiu. “A Survey on nonconvex regularization-based sparse and low-rank recovery in signal processing, statistics, and machine learning”. In: IEEE Access 6 (2018), pp. 69883–69906. doi: 10.1109/ACCESS.2018.2880454. on pp. C74, C77).
• C.-H. Zhang. “Nearly unbiased variable selection under minimax concave penalty”. In: Annal. Stat. 38.2 (2010), pp. 894–942. doi: 10.1214/09-aos729.