Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods

References

• Aragón Artacho F, Geoffroy M (2008) Characterization of metric regularity of subdifferentials. J. Convex Anal. 15(2):365–380.Google Scholar
• Aravkin A, Burke J, Pillonetto G (2013) Sparse/robust estimation and Kalman smoothing with nonsmooth log-concave densities: Modeling, computation, and theory. J. Machine Learn. Res. 14(1):2689–2728.Google Scholar
• Aravkin A, Lozano A, Luss R, Kambadur P (2014) Orthogonal matching pursuit for sparse quantile regression. Proc. IEEE Internat. Conf. Data Mining, ICDM (IEEE Computer Society, Washington, DC), 11–19.Google Scholar
• Azé D, Corvellec JN (2014) Nonlinear local error bounds via a change of metric. J. Fixed Point Theory Appl. 16(1–2):351–372.Crossref, Google Scholar
• Basu S, Pollack R, Roy M (2006) Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics) (Springer, New York).Crossref, Google Scholar
• Bauschke H, Borwein J (1993) On the convergence of Von Neumann’s alternating projection algorithm for two sets. Set-Valued Anal. 1(2):185–212.Crossref, Google Scholar
• 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
• Bolte J, Nguyen T, Peypouquet J, Suter B (2016) From error bounds to the complexity of first-order descent methods for convex functions. Math. Programming 435(2):1701–1709.Google Scholar
• Burke J (1985) Descent methods for composite nondifferentiable optimization problems. Math. Programming 33(3):260–279.Crossref, Google Scholar
• Burke J (1987) Second order necessary and sufficient conditions for convex composite NDO. Math. Programming 38(3):287–302.Crossref, Google Scholar
• Burke J, Ferris M (1993) Weak sharp minima in mathematical programming. SIAM J. Control Optim. 31(5):1340–1359.Crossref, Google Scholar
• Burke J, Ferris M (1995) A Gauss-Newton method for convex composite optimization. Math. Programming 71(2, Ser. A):179–194.Crossref, Google Scholar
• Burke J, Poliquin R (1992) Optimality conditions for non-finite valued convex composite functions. Math. Programming 57(1, Ser. B):103–120.Crossref, Google Scholar
• Cartis C, Gould NIM, Toint PL (2011) On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming. SIAM J. Optim. 21(4):1721–1739.Crossref, Google Scholar
• Chu W, Keerthi SS, Ong CJ (2004) Bayesian support vector regression using a unified loss function. Trans. Neur. Netw. 15(1):29–44.Crossref, Google Scholar
• Cromme L (1977/78) Strong uniqueness. A far-reaching criterion for the convergence analysis of iterative procedures. Numer. Math. 29(2):179–193.Crossref, Google Scholar
• Dong Y (2009) An extension of Luque’s growth condition. Appl. Math. Lett. 22(9):1390–1393.Crossref, Google Scholar
• Dontchev A, Lewis A, Rockafellar R (2003) The radius of metric regularity. Trans. Amer. Math. Soc. 355(2):493–517 (electronic).Crossref, Google Scholar
• Drusvyatskiy D, Ioffe A (2015) Quadratic growth and critical point stability of semi-algebraic functions. Math. Programming 153(2, Ser. A):635–653.Crossref, Google Scholar
• Drusvyatskiy D, Lewis A (2013) Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential. SIAM J. Optim. 23(1):256–267.Crossref, Google Scholar
• Drusvyatskiy D, Lewis A (2016) Error bounds, quadratic growth, and linear convergence of proximal methods. Preprint arXiv:1602.06661.Google Scholar
• Drusvyatskiy D, Paquette C (2016) Efficiency of minimizing compositions of convex functions and smooth maps. Preprint arXiv:1605.00125.Google Scholar
• Drusvyatskiy D, Ioffe A, Lewis A (2016) Nonsmooth optimization using Taylor-like models: Error bounds, convergence, and termination criteria. Preprint arXiv:1610.03446.Google Scholar
• Drusvyatskiy D, Mordukhovich B, Nghia T (2014) Second-order growth, tilt stability, and metric regularity of the subdifferential. J. Convex Anal. 21(4):1165–1192.Google Scholar
• Fletcher R (1982) A model algorithm for composite nondifferentiable optimization problems. Math. Programming Stud. (17):67–76.Crossref, Google Scholar
• Ioffe A (2000) Metric regularity and subdifferential calculus. Uspekhi Mat. Nauk 55(3(333)):103–162.Google Scholar
• Klatte D, Kummer B (2002) Nonsmooth equations in optimization. Nonconvex Optimization and Its Applications, Vol. 60 (Kluwer Academic Publishers, Dordrecht, Netherlands).Google Scholar
• Lee J (2013) Introduction to smooth manifolds. Graduate Texts in Mathematics, Second ed., Vol. 218 (Springer, New York).Google Scholar
• Lewis A, Wright S (2016) A proximal method for composite minimization. Math. Program. 158(1–2):501–546.Crossref, Google Scholar
• Li G, Pong T (2016) Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods. arXiv:1602.02915.Google Scholar
• Luo ZQ, Tseng P (1993) Error bounds and convergence analysis of feasible descent methods: A general approach. Ann. Oper. Res. 46/47(1–4):157–178.Crossref, Google Scholar
• Luo ZQ, Tseng P (1993) On the convergence rate of dual ascent methods for linearly constrained convex minimization. Math. Oper. Res. 18(4):846–867.Link, Google Scholar
• Mordukhovich B (2006) Variational Analysis and Generalized Differentiation I: Basic Theory. Grundlehren der mathematischen Wissenschaften, Vol. 330 (Springer, Berlin).Crossref, Google Scholar
• Mordukhovich B, Nghia T (2013) Second-order variational analysis and characterizations of tilt-stable optimal solutions in infinite-dimensional spaces. Nonlinear Anal. 86:159–180.Crossref, Google Scholar
• Mordukhovich B, Nghia T (2015) Second-order characterizations of tilt stability with applications to nonlinear programming. Math. Program. 149(1–2, Ser. A):83–104.Crossref, Google Scholar
• Mordukhovich B, Outrata J (2013) Tilt stability in nonlinear programming under Mangasarian-Fromovitz constraint qualification. Kybernetika (Prague) 49(3):446–464.Google Scholar
• Mordukhovich B, Rockafellar RT (2012) Second-order subdifferential calculus with applications to tilt stability in optimization. SIAM J. Optim. 22(3):953–986.Crossref, Google Scholar
• Mordukhovich B, Outrata J, Ramírez CH (2015) Second-order variational analysis in conic programming with applications to optimality and stability. SIAM J. Optim. 25(1):76–101.Crossref, Google Scholar
• Necoara I, Nesterov Y, Glineur F (2015) Linear convergence of first order methods for non-strongly convex optimization. Preprint arXiv:1504.06298.Google Scholar
• Nesterov Y (2004) Introductory Lectures on Convex Optimization (Kluwer Academic, Dordrecht, Netherlands).Crossref, Google Scholar
• Poliquin R, Rockafellar R (1996) Prox-regular functions in variational analysis. Trans. Amer. Math. Soc. 348:1805–1838.Crossref, Google Scholar
• Poliquin R, Rockafellar R (1998) Tilt stability of a local minimum. SIAM J. Optim. 8(2):287–299.Crossref, Google Scholar
• Poliquin R, Rockafellar R (2010) A calculus of prox-regularity. J. Convex Anal. 17(1):203–210.Google Scholar
• Polyak B (1979) Sharp minima. Institute of Control Sciences Lecture Notes, Presented at the IIASA Workshop on Generalized Lagrangians and Their Applications (IIASA, Laxenburg, Austria).Google Scholar
• Powell M (1983) General algorithms for discrete nonlinear approximation calculations. Approximation Theory, IV (Academic Press, New York), 187–218.Google Scholar
• Powell M (1984) On the global convergence of trust region algorithms for unconstrained minimization. Math. Programming 29(3):297–303.Crossref, Google Scholar
• Rockafellar R (1970) Convex Analysis, Princeton Mathematical Series (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Rockafellar R (1976) Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5):877–898.Crossref, Google Scholar
• Rockafellar R, Dontchev A (2009) Implicit Functions and Solution Mappings, (Springer, Berlin).Google Scholar
• Rockafellar R, Wets R J-B (1998) Variational Analysis. Grundlehren der mathematischen Wissenschaften, Vol. 317 (Springer, Berlin).Crossref, Google Scholar
• Tseng P (2010) Approximation accuracy, gradient methods, and error bound for structured convex optimization. Math. Program. 125(2, Ser. B):263–295.Crossref, Google Scholar
• Wright S (1990) Convergence of an inexact algorithm for composite nonsmooth optimization. IMA J. Numer. Anal. 10(3):299–321.Crossref, Google Scholar
• Yuan Y (1985) On the superlinear convergence of a trust region algorithm for nonsmooth optimization. Math. Programming 31(3):269–285.Crossref, Google Scholar
• Zhang H (2016) The restricted strong convexity: Analysis of equivalence to error bound and quadratic growth. Preprint arXiv:1511.01635.Google Scholar
• Zhou Z, So AC (2017) A unified approach to error bounds for structured convex optimization problems. Math. Programming 67(3):489–520.Google Scholar
• Zou H, Hastie T (2005) Regularization and variable selection via the elastic net. J. R. Stat. Soc. Ser. B Stat. Methodol. 67(2):301–320.Crossref, Google Scholar