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

References

• [1] Adcock B, Dexter N (2021) The gap between theory and practice in function approximation with deep neural networks. SIAM J. Math. Data Sci. 3(2):624–655.Crossref, Google Scholar
• [2] Adcock B, Hansen AC (2021) Compressive Imaging: Structure, Sampling, Learning (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [3] Adcock B, Bao A, Brugiapaglia S (2019) Correcting for unknown errors in sparse high-dimensional function approximation. Numerische Mathematik 142(3):667–711.Crossref, Google Scholar
• [4] Adcock B, Brugiapaglia S, King-Roskamp M (2022) Do log factors matter? On optimal wavelet approximation and the foundations of compressed sensing. Foundations Comput. Math. 22(1):99–159.Crossref, Google Scholar
• [5] Adcock B, Brugiapaglia S, Webster CG (2022) Sparse Polynomial Approximation of High-Dimensional Functions, vol. 25 (SIAM, Philadelphia).Crossref, Google Scholar
• [6] Adly S, Cibulka R (2014) Quantitative stability of a generalized equation: Application to non-regular electrical circuits. J. Optim. Theory Appl. 160(1):90–110.Crossref, Google Scholar
• [7] Bastounis A, Cucker F, Hansen AC (2023) When can you trust feature selection? I. A condition-based analysis of LASSO and generalised hardness of approximation. Preprint, submitted December 18, https://arxiv.org/abs/2312.11425.Google Scholar
• [8] Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1):183–202.Crossref, Google Scholar
• [9] Belloni A, Chernozhukov V, Wang L (2011) Square-root LASSO: Pivotal recovery of sparse signals via conic programming. Biometrika 98(4):791–806.Crossref, Google Scholar
• [10] Belloni A, Chernozhukov V, Wang L (2014) Pivotal estimation via square-root Lasso in nonparametric regression. Ann. Statist. 42(2):757–788.Crossref, Google Scholar
• [11] Berk A, Brugiapaglia S, Hoheisel T (2023) LASSO reloaded: A variational analysis perspective with applications to compressed sensing. SIAM J. Math. Data Sci. 5(4):1102–1129.Crossref, Google Scholar
• [12] Berk A, Brugiapaglia S, Hoheisel T (2024) Square root LASSO: Well-posedness, Lipschitz stability and the tuning trade off. SIAM J. Optim. 34(3):2609–2637.Crossref, Google Scholar
• [13] Binev P, Bonito A, DeVore R, Petrova G (2024) Optimal learning. Calcolo 61(1):15.Crossref, Google Scholar
• [14] Bolte J, Pauwels E, Silveti-Falls A (2024) Differentiating nonsmooth solutions to parametric monotone inclusion problems. SIAM J. Optim. 34(1):71–97.Crossref, Google Scholar
• [15] Bonnans JF, Shapiro A (2000) Perturbation Analysis of Optimization Problems (Springer, New York).Crossref, Google Scholar
• [16] Campbell SL, Meyer CD (2009) Generalized Inverses of Linear Transformations (SIAM, Philadelphia).Crossref, Google Scholar
• [17] Chen Z, Jiang J (2018) Stability analysis of optimization problems with kth order stochastic and distributionally robust dominance constraints induced by full random recourse. SIAM J. Optim. 28(2):1396–1419.Crossref, Google Scholar
• [18] Colbrook MJ, Antun V, Hansen AC (2022) The difficulty of computing stable and accurate neural networks: On the barriers of deep learning and Smale’s 18th problem. Proc. Natl. Acad. Sci. USA 119(12):e2107151119.Crossref, Google Scholar
• [19] Cui Y, Hoheisel T, Nghia TT, Sun D (2026) Lipschitz stability of least-squares problems regularized by functions with c2-cone reducible conjugates. Math. Oper. Res., ePub ahead of print January 5, https://doi.org/10.1287/moor.2024.0692.Google Scholar
• [20] Cutler J, Díaz M, Drusvyatskiy D (2026) The radius of statistical efficiency. Found Comput Math., ePub ahead of print February 6, https://doi.org/10.1007/s10208-026-09743-z.Google Scholar
• [21] Dontchev AL, Rockafellar RT (2014) Implicit Functions and Solution Mappings, vol. 543 (Springer-Verlag, New York).Crossref, Google Scholar
• [22] Fadili J, Nghia TTA, Phan DN (2023) Geometric characterizations for strong minima with applications to nuclear norm minimization problems. Preprint, submitted August 18, https://arxiv.org/abs/2308.09224.Google Scholar
• [23] Foucart S (2023) The sparsity of LASSO-type minimizers. Appl. Computational Harmonic Anal. 62:441–452.Crossref, Google Scholar
• [24] Gilbert JC (2017) On the solution uniqueness characterization in the L1 norm and polyhedral gauge recovery. J. Optim. Theory Appl. 172(1):70–101.Crossref, Google Scholar
• [25] Golub GH, Van Loan CF (1996) Matrix Computations, 3rd ed. (SIAM, Philadelphia).Google Scholar
• [26] Guo S, Xu H (2023) Data perturbations in stochastic generalized equations: Statistical robustness in static and sample average approximated models. Math. Programming 202(1):135–168.Crossref, Google Scholar
• [27] Hastie T, Tibshirani R, Friedman J (2009) The Elements of Statistical Learning (Springer, New York).Crossref, Google Scholar
• [28] Hoffman AJ (1952) On approximate solutions of systems of linear inequalities. J. Res. National Bureau Standards 49(4):263–265.Crossref, Google Scholar
• [29] Horn R, Johnson CR (2013) Matrix Analysis, Springer Monographs in Mathematics, 2nd ed. (Cambridge University Press, Cambridge, UK).Google Scholar
• [30] Ioffe AD (2017) Variational Analysis of Regular Mappings: Theory and Applications (Springer, Cham, Switzerland).Crossref, Google Scholar
• [31] Kanzow C, Lechner T (2021) Globalized inexact proximal Newton-type methods for nonconvex composite functions. Comput. Optim. Appl. 78(2):377–410.Crossref, Google Scholar
• [32] Klatte D (1987) Lipschitz continuity of infima and optimal solutions in parametric optimization: The polyhedral case. Guddat J, Jongen HT, Kummer B, Nožička F, eds. Parametric Optimization and Related Topics, Math Research, vol. 35 (Akademie-Verlag, Berlin), 229–248.Google Scholar
• [33] Lee JD, Sun Y, Saunders MA (2014) Proximal Newton-type methods for minimizing composite functions. SIAM J. Optim. 24(3):1420–1443.Crossref, Google Scholar
• [34] Lewis AS, Pang CHJ (2010) Lipschitz behavior of the robust regularization. SIAM J. Control Optim. 48(5):3080–3104.Crossref, Google Scholar
• [35] Li W (1994) Sharp Lipschitz constants for basic optimal solutions and basic feasible solutions of linear programs. SIAM J. Control Optim. 32(1):140–153.Crossref, Google Scholar
• [36] Lockhart R, Taylor J, Tibshirani RJ, Tibshirani R (2014) A significance test for the lasso. Ann. Statist. 42(2):413–468.Crossref, Google Scholar
• [37] Mangasarian OL, Shiau TH (1987) Lipschitz continuity of solutions of linear inequalities, programs, and complementarity problems. SIAM J. Control Optim. 25(3):583–595.Crossref, Google Scholar
• [38] Meng K, Wu P, Yang X (2025) Lipschitz continuity of solution multifunctions of extended ℓ1 regularization problems. Preprint, submitted July 19, https://arxiv.org/abs/2406.16053.Google Scholar
• [39] Milzarek A, Ulbrich M (2014) A semismooth Newton method with multidimensional filter globalization for l_1-optimization. SIAM J. Optim. 24(1):298–333.Crossref, Google Scholar
• [40] Mordukhovich BS (2006) Variational Analysis and Generalized Differentiation: I. Basic Theory (Springer-Verlag, Berlin).Crossref, Google Scholar
• [41] Mordukhovich BS (2018) Variational Analysis and Applications (Springer, Cham, Switzerland).Crossref, Google Scholar
• [42] Mordukhovich BS, Outrata JV, Sarabi ME (2014) Full stability of locally optimal solutions in second-order cone programs. SIAM J. Optim. 24(4):1581–1613.Crossref, Google Scholar
• [43] Nesterov Y (2018) Lectures on Convex Optimization (Springer, Cham, Switzerland).Crossref, Google Scholar
• [44] Nghia TT (2024) Geometric characterizations of Lipschitz stability for convex optimization problems. SIAM J. Optim. 35(2):927–958.Google Scholar
• [45] Robinson SM (1980) Strongly regular generalized equations. Math. Oper. Res. 5(1):43–62.Link, Google Scholar
• [46] Robinson SM (1981) Some continuity properties of polyhedral multifunctions. König H, Korte B, Ritter K, eds. Math. Programming Oberwolfach, Math. Programming Stud., vol 14 (Springer, Berlin, Heidelberg).Google Scholar
• [47] Robinson SM (2007) Solution continuity in monotone affine variational inequalities. SIAM J. Optim. 18(3):1046–1060.Crossref, Google Scholar
• [48] Rockafellar RT, Wets RB (1998) Variational Analysis (Springer, Berlin).Crossref, Google Scholar
• [49] Tian X, Loftus JR, Taylor JE (2018) Selective inference with unknown variance via the square-root lasso. Biometrika 105(4):755–768.Google Scholar
• [50] Tibshirani R (1996) Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser. B Methodological 58(1):267–288.Crossref, Google Scholar
• [51] Tibshirani RJ (2013) The lasso problem and uniqueness. Electronic J. Statist. 7:1456–1490.Crossref, Google Scholar
• [52] Tibshirani RJ, Taylor J (2011) The solution path of the generalized lasso. Ann. Statist. 39(1):1335–1371.Google Scholar
• [53] van de Geer S (2016) Estimation and Testing Under Sparsity (Springer, Cham, Switzerland).Crossref, Google Scholar
• [54] Wang H, Li G, Jiang G (2007) Robust regression shrinkage and consistent variable selection through the LAD-Lasso. J. Bus. Econom. Statist. 25(3):347–355.Crossref, Google Scholar
• [55] Yen ND (1995) Lipschitz continuity of solutions of variational inequalities with a parametric polyhedral constraint. Math. Oper. Res. 20(3):695–708.Link, Google Scholar
• [56] Zhang J, Xu H, Zhang L (2016) Quantitative stability analysis for distributionally robust optimization with moment constraints. SIAM J. Optim. 26(3):1855–1882.Crossref, Google Scholar
• [57] Zhang H, Yin W, Cheng L (2015) Necessary and sufficient conditions of solution uniqueness in 1-norm minimization. J. Optim. Theory Appl. 164(1):109–122.Crossref, Google Scholar
• [58] Zheng XY, Ng K (2010) Metric subregularity and calmness for nonconvex generalized equations in Banach spaces. SIAM J. Optim. 20(5):2119–2136.Crossref, Google Scholar
• [59] Zou H (2006) The adaptive lasso and its oracle properties. J. Amer. Statist. Assoc. 101(476):1418–1429.Crossref, Google Scholar