Decomposition Method for Lipschitz Stability of General LASSO-type Problems

This paper introduces a decomposition-based method to investigate the Lipschitz stability of solution mappings for general LASSO-type problems with convex data fidelity and $\ell_1$-regularization terms. The solution mappings are considered as set-valued mappings of the measurement vector and the regularization parameter. Based on the proposed method, we provide two regularity conditions for Lipschitz stability: the weak and strong conditions. The weak condition implies the Lipschitz continuity of solution mapping at the point in question, regardless of solution uniqueness. The strong condition yields the local single-valued and Lipschitz continuity of solution mapping. When applied to the LASSO and Square Root LASSO (SR-LASSO), the weak condition is new, while the strong condition is equivalent to some sufficient conditions for Lipschitz stability found in the literature. Specifically, our results reveal that the solution mapping of the LASSO is globally (Hausdorff) Lipschitz continuous without any assumptions. In contrast, the solution mapping of the SR-LASSO is not always Lipschitz continuous. A sufficient and necessary condition is proposed for its local Lipschitz property. Furthermore, we fully characterize the local single-valued and Lipschitz continuity of solution mappings for both problems using the strong condition.
Comment: 31 pages