A Decomposition Method for Lipschitz Stability of General LASSO-Type Problems

This paper introduces a decomposition method to analyze the Lipschitz stability of solution mappings for general least absolute shrinkage and selection operator–type (LASSO-type) problems with convex data fidelity and ${\mathcal{\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 establish two regularity conditions for Lipschitz stability: a weak condition and a strong condition. The weak condition guarantees the Lipschitz continuity of solution mapping at a given point, even when the solution is not unique. In contrast, the strong condition ensures both local single valuedness and Lipschitz continuity. When applied to the LASSO and square root LASSO (SR-LASSO), the weak condition is new, whereas the strong condition coincides with certain known sufficient conditions for Lipschitz stability in the literature. Notably, our results show that the solution mapping for the LASSO is globally (Hausdorff) Lipschitz continuous without any additional assumptions. In contrast, the solution mapping for the SR-LASSO is not always Lipschitz continuous, and we prove that the weak condition is both necessary and sufficient for its local Lipschitz continuity. Furthermore, we fully characterize the local single valuedness and Lipschitz continuity of solution mappings for both problems using the strong condition.

Funding: This work was supported by the National Key R&D Program of China [Grant 2023YFA1011400] and the National Natural Science Foundation of China [Grant 12571321].