New Non-Convex Sparsity-Inducing Regularizations for Sparse Optimization

Regularization, or penalization, is a simple yet effective method to promote some desired solution structure and to prevent the over-fitting phenomenon. In many applications, a sparsity-inducing regularization is introduced to obtain a less complex model via feature selection. Two classical examples of sparsity-inducing regularizations are the cardinality function and the convex ℓ1-norm. One of the key advantages of these two regularizations is that their proximal operator admits a closed-form expression, called the hard thresholding function and soft thresholding function, respectively. As a result, the corresponding sparse optimization problems can be solved efficiently. However, they still have some drawbacks: the cardinality function is discontinuous so the resulting optimization algorithm can be numerically unstable, while the ℓ1-norm usually over-shrinks coefficients which have large magnitude. Recently, researchers have started to look into several continuous non-convex sparsity-inducing regularizations, which overcome the disadvantages of the two former regularizations in terms of numerical performance. Some well-known non-convex regularizations are the ℓq quasi-norm with 0 < q < 1, the SCAD and the MCP. There have been theoretical developments regarding the effectiveness of these non-convex regularizations under certain problem settings, which may not hold in some applications. Thus, their numerical performance can be vastly different in practical problems. Therefore, it is of interest to study new non-convex regularizations and test whether they can perform better than the currently known regularizations under several problem conditions. In this thesis, we introduce two new continuous non-convex sparsity-inducing regularizations, which we name Inverse Log regularization and Bézier regularization. The Inverse Log regularization can model the jump in the cardinality regularization better than the ℓq quasi-norm, which potentially leads to a solution with better sparsity. Meanwhile, the Bézier regularization is a generalization of the popular MCP in the literature. It is constructed so that it leads to a continuous threshold function which gives a tighter approximation to the hard thresholding function. We then discuss some useful properties of the new regularizations which play a key role in constructing the numerical algorithms. We also establish some convergence analysis for the algorithms. Finally, we conduct numerical experiments to test the performance of the numerical algorithms using the two proposed sparsity-inducing regularizations