Generalized Metric Subregularity with Applications to High-Order Regularized Newton Methods

References

• [1] Ahookhosh M, Nesterov Y (2024) High-order methods beyond the classical complexity bounds: Inexact high-order proximal-point methods. Math. Programming 208:365–407. Crossref, Google Scholar
• [2] Ahookhosh M, Themelis A, Patrinos P (2021) A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: Superlinear convergence to nonisolated local minima. SIAM J. Optim. 31(1):653–685.Crossref, Google Scholar
• [3] Ahookhosh M, Aragón-Artacho FJ, Fleming RM, Vuong PT (2019) Local convergence of the Levenberg–Marquardt method under Hölder metric subregularity. Adv. Comput. Math. 45:2771–2806.Crossref, Google Scholar
• [4] Aragón-Artacho FJ, Geoffroy MH (2014) Metric subregularity of the convex subdifferential in Banach spaces. J. Nonlinear Convex Anal. 15(1):35–47.Google Scholar
• [5] Attouch H, Bolte J (2009) On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Programming 116:5–16.Crossref, Google Scholar
• [6] Attouch H, Bolte J, Svaiter BF (2013) Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Programming 137:91–129.Crossref, Google Scholar
• [7] Behmandpoor P, Latafat P, Themelis A, Moonen M, Patrinos P (2024) SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization. Comput. Optim. Appl. 88:71–106.Crossref, Google Scholar
• [8] Bento G, Mordukhovich BS, Mota T, Nesterov Y (2025) Convergence of descent optimization algorithms under Polyak-Łojasiewicz-Kurdyka conditions. J. Optim. Theory Appl. 207(3):1–29.Crossref, Google Scholar
• [9] Bierstone E, Milman P (1988) Semianalytic and subanalytic sets. Publications Math. IHES 67:5–42.Crossref, Google Scholar
• [10] Bolte J, Daniilidis A, Lewis AS (2007) The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4):1205–1223.Crossref, Google Scholar
• [11] Boţ RI, Dao MN, Li G (2021) Extrapolated proximal subgradient algorithms for fractional programs. Math. Oper. Res. 47(3):2415–2443.Link, Google Scholar
• [12] Cai J-F, Huang M, Li D, Wang Y (2022) The global landscape of phase retrieval II. Quotient intensity models. Ann. Appl. Math. 38(1):62–114.Crossref, Google Scholar
• [13] Cai J-F, Huang M, Li D, Wang Y (2023) Nearly optimal bounds for the global geometric landscape of phase retrieval. Inverse Problems 39(7):075011. Crossref, Google Scholar
• [14] Cartis C, Gould NIM, Toint PL (2011) Adaptive cubic regularisation methods for unconstrained optimization. Part II: Worst-case function- and derivative-evaluation complexity. Math. Programming 130:295–319.Crossref, Google Scholar
• [15] Chandra R, Zhong Z, Hontz J, McCulloch V, Studer C, Goldstein T (2017) PhasePack: A phase retrieval library. Matthews MB, ed. 51st Asilomar Conf. Signals Systems Comput. (IEEE, New York), 1617–1621. Google Scholar
• [16] Chen X, Jiang B, Lin T, Zhang S (2022) Accelerating adaptive cubic regularization of Newton’s method via random sampling. J. Machine Learn. Res. 23(90):1–38.Google Scholar
• [17] Drusvyatskiy D, Mordukhovich BS, Nghia TTA (2014) Second-order growth, tilt stability, and metric regularity of the subdifferential. J. Convex Anal. 21(4):1165–1192.Google Scholar
• [18] Facchinei F, Pang J-S (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. I–II (Springer, New York).Google Scholar
• [19] Gaydu M, Geoffroy MH, Jean-Alexis C (2011) Metric subregularity of order q and the solving of inclusions. Central Eur. J. Math. 9(1):147–161.Google Scholar
• [20] Gfrerer H, Outrata JV (2021) On a semismooth* Newton method for solving generalized equations. SIAM J. Optim. 31(1):489–517.Crossref, Google Scholar
• [21] Grapiglia GN, Nesterov Y (2017) Regularized Newton methods for minimizing functions with Hölder continuous Hessians. SIAM J. Optim. 27(1):478–506.Crossref, Google Scholar
• [22] Hirsch MW (1976) Differential Topology, Graduate Texts in Mathematics, vol. 33 (Springer-Verlag, New York).Crossref, Google Scholar
• [23] Hsia Y, Sheu R-L, Yuan Y-X (2017) Theory and application of p-regularized subproblems for p > 2. Optim. Methods Software 32(5):1059–1077.Crossref, Google Scholar
• [24] Izmailov AF, Solodov MV (2014) Newton-Type Methods for Optimization and Variational Problems (Springer, New York).Crossref, Google Scholar
• [25] Khanh PD, Mordukhovich BS, Phat VT, Tran DB (2024) Globally convergent coderivative-based generalized Newton methods in nonsmooth optimization. Math. Programming 205:373–429.Crossref, Google Scholar
• [26] Klatte D, Kummer B (2002) Nonsmooth Equations in Optimization: Regularity, Calculus, Applications (Kluwer, Boston).Google Scholar
• [27] Li G, Mordukhovich BS (2012) Hölder metric subregularity with applications to proximal point method. SIAM J. Optim. 22(4):1655–1684.Crossref, Google Scholar
• [28] Li G, Pong TK (2018) Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods. Foundations Comput. Math. 18:1199–1232.Crossref, Google Scholar
• [29] Li X, Sun D, Toh K-C (2018) A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems. SIAM J. Optim. 28(1):433–458.Crossref, Google Scholar
• [30] Li J, Zhou T, Wang C (2018) On global convergence of gradient descent algorithms for generalized phase retrieval problem. J. Comput. Appl. Math. 329:202–222.Crossref, Google Scholar
• [31] Lindstrom SB, Lourenço BF, Pong TK (2023) Error bounds, facial residual functions and applications to the exponential cone. Math. Programming 200:229–278.Crossref, Google Scholar
• [32] Liu Y, Pan S, Qian Y (2025) An inexact q-order regularized proximal Newton method for nonconvex composite optimization. SIAM J. Optim. 35(2):959–988.Crossref, Google Scholar
• [33] Luo Z-Q, Tseng P (1993) Error bounds and convergence analysis of feasible descent methods: A general approach. Ann. Oper. Res. 46:157–178.Crossref, Google Scholar
• [34] Mordukhovich BS (2006) Variational Analysis and Generalized Differentiation. I. Basic Theory. II. Applications (Springer, Berlin).Google Scholar
• [35] Mordukhovich BS (2024) Second-Order Variational Analysis in Optimization, Variational Stability, and Control: Theory, Algorithm, Applications (Springer, Cham, Switzerland).Crossref, Google Scholar
• [36] Mordukhovich BS, Ouyang W (2015) Higher-order metric subregularity and its applications. J. Global Optim. 63:777–795.Crossref, Google Scholar
• [37] Mordukhovich BS, Sarabi ME (2021) Generalized Newton algorithms for tilt-stable minimizers in nonsmooth optimization. SIAM J. Optim. 31(2):1184–1214.Crossref, Google Scholar
• [38] Mordukhovich BS, Yuan X, Zeng S, Zhang J (2023) A globally convergent proximal Newton-type method in nonsmooth convex optimization. Math. Programming 198:899–936.Crossref, Google Scholar
• [39] Nabou Y, Necoara I (2024) Efficiency of higher-order algorithms for minimizing composite functions. Comput. Optim. Appl. 87:441–473.Crossref, Google Scholar
• [40] Nesterov Y (2021) Implementable tensor methods in unconstrained convex optimization. Math. Programming 186:157–183.Crossref, Google Scholar
• [41] Nesterov Y (2023) Inexact accelerated high-order proximal-point methods. Math. Programming 197:1–26.Crossref, Google Scholar
• [42] Nesterov Y, Polyak BT (2006) Cubic regularization of Newton method and its global performance. Math. Programming 108:177–205.Crossref, Google Scholar
• [43] Ochs P (2019) Unifying abstract inexact convergence theorems and block coordinate variable metric iPiano. SIAM J. Optim. 29(1):541–570.Crossref, Google Scholar
• [44] Ouyang W, Liu Y, Pong TK, Wang H (2025) Kurdyka-Łojasiewicz exponent via Hadamard parametrization. SIAM J. Optim. 35(1):62–91.Crossref, Google Scholar
• [45] Poon C, Peyré G (2021) Smooth bilevel programming for sparse regularization. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. Adv. Neural Inform. Processing Systems 34 (NeurIPS 2021) (Curran Associates, Red Hook, NY), 1543–1555.Google Scholar
• [46] Poon C, Peyré G (2023) Smooth over-parameterized solvers for non-smooth structured optimization. Math. Programming 201:897–952.Crossref, Google Scholar
• [47] Rockafellar RT, Wets RJ-B (1998) Variational Analysis (Springer, Berlin).Crossref, Google Scholar
• [48] Themelis A, Ahookhosh M, Patrinos P (2019) On the acceleration of forward-backward splitting via an inexact Newton method. Bauschke H, Burachik R, Luke R, eds. Splitting Algorithms, Modern Operator Theory, and Applications (Springer, New York), 363–412.Crossref, Google Scholar
• [49] Yao JC, Zheng XY, Zhu J (2017) Stable minimizers of φ-regular functions. SIAM J. Optim. 27(2):1150–1170.Crossref, Google Scholar
• [50] Yu P, Li G, Pong TK (2022) Kurdyka-Łojasiewicz exponent via inf-projection. Foundations Comput. Math. 22:1171–1217.Crossref, Google Scholar
• [51] Yue M-C, Zhou Z, So AM-C (2019) On the quadratic convergence of the cubic regularization method under a local error bound condition. SIAM J. Optim. 29(1):904–932.Crossref, Google Scholar
• [52] Zălinescu C (2002) Convex Analysis in General Vector Spaces (World Scientific, Singapore).Crossref, Google Scholar
• [53] Zeng L, Pong TK (2022) ρ-regularization subproblems: Strong duality and an eigensolver-based algorithm. Comput. Optim. Appl. 81:337–368.Crossref, Google Scholar
• [54] Zhang B, Ng KF, Zheng XY, He Q (2016) Hölder metric subregularity for multifunctions in C2 type Banach spaces. Optimization 65(11):1963–1982.Crossref, Google Scholar
• [55] Zheng XY, Zhu J (2016) Generalized metric subregularity and regularity with respect to an admissible function. SIAM J. Optim. 26(1):535–563.Crossref, Google Scholar
• [56] Zhou Z, So AM-C (2017) A unified approach to error bounds for structured convex optimization problems. Math. Programming 165:689–728.Crossref, Google Scholar
• [57] Zhu W, Cartis C (2024) Global convergence of high-order regularization methods with sums-of-squares Taylor models. Preprint, submitted April 3, https://arxiv.org/abs/2404.03035v2.Google Scholar