Abstract.
In this paper, we mainly study tilt stability and Lipschitz stability of convex optimization problems. Our characterizations are geometric and fully computable in many important cases. As a result, we apply our theory to the group Lasso problem and the nuclear norm minimization problem and reveal that the Lipschitz stability of the solution mapping in these problems is automatic whenever the solution mapping is single-valued.
Keywords
- Lipschitz stability
- tilt stability
- convex optimization
- variational analysis and nonsmooth optimization
- second-order analysis
- group Lasso problems
- nuclear norm minimization problems
MSC codes
- 49J52
- 49J53
- 49K40
- 90C25
- 90C31
Get full access to this article
View all available purchase options and get full access to this article.
Get Access
Acknowledgments.
The author is deeply grateful to Tim Hoheisel and Defeng Sun for many fruitful discussions about this research topic. He is indebted to Ebrahim Sarabi for helpful remarks on characterizing tilt stability via second subderivatives. The author is also thankful to both anonymous referees for their careful readings, constructive suggestions, as well as deep remarks on other works that helped improve the original presentation significantly.
References
1.
F. J. Aragón Artacho and M. H. Geoffroy, Characterizations of metric regularity of subdifferentials, J. Convex Anal., 15 (2008), pp. 365–380, https://www.heldermann-verlag.de/jca/jca15/jca0686_b.pdf.
2.
A. Berk, S. Brugiapaglia, and T. Hoheisel, Lasso reloaded: A variational analysis perspective with applications to compressed sensing, SIAM J. Math. Data Sci., 5 (2023), pp. 1102–1129, https://doi.org/10.1137/22M1498991.
3.
M. Benko, H. Gfrerer, and B. S. Mordukhovich, Characterizations of tilt-stable minimizers in second-order cone programming, SIAM J. Optim., 29 (2019), pp. 3100–3130, https://doi.org/10.1137/18M1213117.
4.
J. Bolte, T. Le, E. Pauwels, and A. Silveti-Falls, Nonsmooth implicit differentiation for machine learning and optimization, in Advances in Neural Information Processing Systems (NeurIPS 2021), Vol. 34, Curran Associates, Red Hook, NY, 2021, pp. 13537–13549.
5.
J. Bolte, E. Pauwels, and A. Silveti-Falls, Differentiating nonsmooth solutions to parametric monotone inclusion problems, SIAM J. Optim., 34 (2024), pp. 71–97, https://doi.org/10.1137/22M1541630.
6.
J. Bolte, T. P. Nguyen, J. Peypouquet, and B. W. Suter, From error bounds to the complexity of first-order descent methods for convex functions, Math. Program., 165 (2017), pp. 471–507, https://doi.org/10.1007/s10107-016-1091-6.
7.
J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer Ser. Oper. Res., Springer, New York, 2000.
8.
A. Blake and A. Zisserman, Visual Reconstruction, MIT Press, Cambridge, MA, 1987.
9.
N. H. Chieu, L. V. Hien, and T. T. A. Nghia, Characterization of tilt stability via subgradient graphical derivative with applications to nonlinear programming, SIAM J. Optim., 28 (2018), pp. 2246–2273, https://doi.org/10.1137/17M1130794.
10.
N. H. Chieu, L. V. Hien, T. T. A. Nghia, and H. A. Tuan, Quadratic growth and strong metric subregularity of the subdifferential via subgradient graphical derivative, SIAM J. Optim., 31 (2021), pp. 545–568, https://doi.org/10.1137/19M1242732.
11.
V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky, The convex geometry of linear inverse problems, Found. Comput. Math., 12 (2012), pp. 805–849, https://doi.org/10.1007/s10208-012-9135-7.
12.
E. Candès and Y. Plan, Matrix completion with noise, Proc. IEEE, 98 (2010), pp. 925–936, https://doi.org/10.1109/JPROC.2009.2035722.
13.
E. Candès and B. Recht, Exact matrix completion via convex optimization, Found Comput. Math., 9 (2009), pp. 717–772, https://doi.org/10.1007/s10208-009-9045-5.
14.
E. Candès and B. Recht, Simple bounds for recovering low-complexity models, Math. Program., 141 (2013), pp. 577–589, https://doi.org/10.1007/s10107-012-0540-0.
15.
Y. Cui, Large Scale Composite Optimization Problems with Coupled Objective Functions: Theory, Algorithms and Applications, Thesis, National University of Singapore, Singapore, 2016.
16.
Y. Cui and C. Ding, Nonsmooth Composite Matrix Optimization: Strong Regularity, Constraint Nondegeneracy and Beyond, preprint, arXiv:1907.13253, 2016.
17.
Y. Cui, C. Ding, and X. Zhao, Quadratic growth conditions for convex matrix optimization problems associated with spectral functions, SIAM J. Optim., 27 (2017), pp. 2332–2355, https://doi.org/10.1137/17M1116325.
18.
D. Drusvyatskiy and A. S. Lewis, Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential, SIAM J. Optim, 23 (2013), pp. 256–267, https://doi.org/10.1137/120876551.
19.
D. Drusvyatskiy, B. S. Mordukhovich, and T. T. A. Nghia, Second-order growth, tilt stability, and metric regularity of the subdifferential, J. Convex Anal., 21 (2014), pp. 1165–1192, https://www.heldermann.de/JCA/JCA21/JCA214/jca21061.htm.
20.
D. Drusvyatskiy and A. D. Ioffe, Quadratic growth and critical point stability of semi-algebraic functions, Math. Program., 153 (2015), pp. 635–653, https://doi.org/10.1007/s10107-014-0820-y.
21.
A. L. Dontchev and R. T. Rockafellar, Implicit Functions and Solution Mappings, A View from Variational Analysis, Springer, Dordrecht, Netherlands, 2009.
22.
J. Fadili, T. T. A. Nghia, and T. T. T. Tran, Sharp, strong and unique minimizers for low complexity robust recovery, Inf. Inference, 12 (2023), pp. 1461–1513, https://doi.org/10.1093/imaiai/iaad005.
23.
J. Fadili, T. T. A. Nghia, and D. N. Phan, Geometric Characterizations for Strong Minima with Applications to Nuclear Norm Minimization Problems, preprint, arXiv:2308.09224v1, 2023.
24.
J. Fadili, T. T. A. Nghia, and D. N. Phan, Solution uniqueness of convex optimization problems via the radial cone, J. Optim. Theory Appl., to appear.
25.
P. D. Khanh, B. S. Mordukhovich, and V. T. Phat, A generalized Newton method for subgradient systems, Math. Oper. Res., 48 (2023), pp. 1811–2382, https://doi.org/10.1287/moor.2022.1320.
26.
H. Gfrerer, On a globally convergent semismooth\(^*\) newton method in nonsmooth nonconvex optimzation, Comput. Optim. Appl., 91 (2025), pp. 67–124, https://doi.org/10.1007/s10589-025-00658-z.
27.
H. Gfrerer and J. V. Outrata, On a semismooth Newton method for solving generalized equations, SIAM J. Optim., 31 (2021), pp. 489–517, https://doi.org/10.1137/19M1257408.
28.
H. Gfrerer and J. V. Outrata, On Lipschitzian properties of implicit multifunctions, SIAM J. Optim., 26 (2016), pp. 2160–2189, https://doi.org/10.1137/15M1052299.
29.
H. Gfrerer and J. V. Outrata, On (local) analysis of multifunctions via subspaces contained in graphs of generalized derivatives, J. Math. Anal. Appl., 508 (2022), 125895, https://doi.org/10.1016/j.jmaa.2021.125895.
30.
H. Gfrerer and B. S. Mordukhovich, Complete characterizations of tilt stability in nonlinear programming under weakest qualification conditions, SIAM J. Optim., 25 (2015), pp. 2081–2119, https://doi.org/10.1137/15M1012608.
31.
M. Hebiri and S. van de Geer, The smooth-lasso and other \(\ell_1+\ell_2\)-penalized methods, Electron. J. Stat., 5 (2011), pp. 1184–1226, https://doi.org/10.1214/11-EJS638.
32.
H. Liu and J. Zhang, Estimation consistency of the group lasso and its applications, J. Mach. Learn. Res., 5 (2009), pp. 376–383, https://proceedings.mlr.press/v5/liu09a.
33.
A. S. Lewis and S. Zhang, Partial smoothness, tilt stability, and generalized Hessians, SIAM J. Optim., 23 (2013), pp. 74–94, https://doi.org/10.1137/110852103.
34.
Y. Liu, S. Pan, and S. Bi, Isolated calmness of solution mappings and exact recovery conditions for nuclear norm optimization problems, Optimization, 70 (2021), pp. 481–510, https://doi.org/10.1080/02331934.2020.1723584.
35.
W. Ouyang and A. Milzarek, Variational Properties of Decomposable Functions: Part II: Strong Order Theory, preprint,arXiv:2311.07276, 2023.
36.
R. A. Poliquin and R. T. Rockafellar, Tilt stability of a local minimum, SIAM J. Optim., 8 (1998), pp. 287–299, https://doi.org/10.1137/S1052623496309296.
37.
B. S. Mordukhovich, Sensitivity analysis in nonsmooth optimization, in Theoretical Aspects of Industrial Design, SIAM Proc. Appl. Math. 58, D. A. Field and V. Komkov, eds., SIAM, Philadelphia, 1992, pp. 32–46 B. S. Mordukhovich, Sensitivity analysis in nonsmooth optimization, in Theoretical Aspects of Industrial Design, SIAM Proc. Appl. Math. 58, D. A. Field and V. Komkov, eds., SIAM, Philadelphia, 1992, pp. 32–46.
38.
B. S. Mordukhovich, Variational Analysis and Generalized Differentiation, Springer, New York, 2006.
39.
B. S. Mordukhovich, T. T. A. Nghia, and R. T. Rockafellar, Full stability in finite-dimensional optimization, Math. Oper. Res., 40 (2015), pp. 226–252, https://doi.org/10.1287/moor.2014.0669.
40.
B. S. Mordukhovich and M. E. Sarabi, Generalized Newton algorithms for tilt-stable minimizers in nonsmooth optimization, SIAM J. Optim., 31 (2021), pp. 1184–1214, https://doi.org/10.1137/20M1329937.
41.
B. S. Mordukhovich and R. T. Rockafellar, Second-order subdifferential calculus with applications to tilt stability in optimization, SIAM J. Optim., 22 (2012), pp. 953–986, https://doi.org/10.1137/110852528.
42.
B. S. Mordukhovich and T. T. A. Nghia, Second-order characterizations of tilt stability with applications to nonlinear programming, Math. Program., 149 (2015), pp. 83–104, https://doi.org/10.1007/s10107-013-0739-8.
43.
J. Mairal and B. Yu, Complexity analysis of the lasso regularization path, in Proceedings of the 29th International Conference on Machine Learning, Omnipress, Madison, WI, 2012, pp. 1835–1842.
44.
S. M. Robinson, Strongly regular generalized equations, Math. Oper. Res., 5 (1980), pp. 43–62, https://doi.org/10.1287/moor.5.1.43.
45.
S. M. Robinson, Some continuity properties of polyhedral multifunctions, Mathematical Programming at Olberwolfach, Math. Program. Study 14, Springer, Berlin, 1981, pp. 206–214, https://doi.org/10.1007/BFb0120929.
46.
R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970.
47.
R. T. Rockafellar, Augmented Lagrangians and hidden convexity in sufficient conditions for local optimality, Math. Program, 198 (2023), pp. 159–194, https://doi.org/10.1007/s10107-022-01768-w.
48.
R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer, Berlin, 1998.
49.
D. Sun, The strong second-order sufficient condition and constraint nondegeneracity in nonlinear semidefinite programming and their applications, Math. Oper. Res., 31 (2006), pp. 761–776, https://doi.org/10.1287/moor.1060.0195.
50.
R. J. Tibshirani, The Lasso problem and uniqueness, Electron. J. Stat., 7 (2013), pp. 1456–1490, https://doi.org/10.1214/13-EJS815.
51.
S. Vaiter, C. Deledalle, J. Fadili, G. Peyré, and C. Dossal, The degrees of freedom of partly smooth regularizers, Ann. Inst. Statist. Math., 69 (2017), pp. 791–832, https://doi.org/10.1007/s10463-016-0563-z.
52.
M. Yuan and Y. Lin, Model selection and estimation in regression with grouped variables, J. R. Stat. Soc. Ser. B Stat. Methodol., 68 (2006), pp. 49–67, https://doi.org/10.1111/j.1467-9868.2005.00532.x.
53.
G. A, Watson: Characterization of the subdifferential of some matrix norms, Linear Algebra Appl., 170 (1992), pp. 33–45, https://doi.org/10.1016/0024-3795(92)90407-2.
54.
M. J. Wainwright, High-Dimensional Statistics. A Non-Asymptotic Viewpoint, Cambridge University Press, Cambridge, 2019.
55.
R. Zhang and J. Treiman, Upper-Lipschitz multifunctions and inverse subdifferentials, Nonlinear Anal., 24 (1995), pp. 273–286, https://doi.org/10.1016/0362-546X(94)E0025-C.
56.
H. Zou and T. Hastie, Regularization and variable selection via the elastic net, J. Royal Stat. Soc. B Stat. Methodol., 67 (2005), pp. 301–320, https://doi.org/10.1111/j.1467-9868.2005.00503.x.
57.
Z. Zhou and A. M.-C. So, A unified approach to error bounds for structured convex optimization, Math. Program., 165 (2017), pp. 689–728, https://doi.org/10.1007/s10107-016-1100-9.
