×

Inexact proximal Newton methods for self-concordant functions. (English) Zbl 1386.90105

Authors’ abstract: We analyze the proximal Newton method for minimizing a sum of a self-concordant function and a convex function with an inexpensive proximal operator. We present new results on the global and local convergence of the method when inexact search directions are used. The method is illustrated with an application to L1-regularized covariance selection, in which prior constraints on the sparsity pattern of the inverse covariance matrix are imposed. In the numerical experiments the proximal Newton steps are computed by an accelerated proximal gradient method and multifrontal algorithms for positive definite matrices with chordal sparsity patterns are used to evaluate gradients and matrix-vector products with the Hessian of the smooth component of the objective.
Reviewer: Do Van Luu (Hanoi)

MSC:

90C25 Convex programming

Keywords:

90C53
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Andersen MS, Vandenberghe, L (2015) CHOMPACK: a python package for chordal matrix computations, Version 2.2.1. cvxopt.github.io/chompack
[2] Andersen MS, Dahl J, Vandenberghe L (2013) Logarithmic barriers for sparse matrix cones. Optim Methods Softw 28(3):396-423 · Zbl 1266.65045 · doi:10.1080/10556788.2012.684353
[3] Andersen M, Dahl J, Vandenberghe L (2015) CVXOPT: a python package for convex optimization. www.cvxopt.org · Zbl 1257.90042
[4] Becker SR, Candès EJ, Grant MC (2011) Templates for convex cone problems with applications to sparse signal recovery. Math Program Comput 3(3):165-218 · Zbl 1257.90042 · doi:10.1007/s12532-011-0029-5
[5] Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J Imaging Sci 2(1):183-202 · Zbl 1175.94009 · doi:10.1137/080716542
[6] Bertsekas DP (2009) Convex optimization theory. Athena Scientific, Belmont · Zbl 1242.90001
[7] Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[8] Byrd RH, Nocedal J, Oztoprak F (2016) An inexact successive quadratic approximation method for L-1 regularized optimization. Math Program 157(2):375-396 · Zbl 1342.49037
[9] Davis TA, Hu Y (2011) The University of Florida sparse matrix collection. ACM Trans Math Softw 38:1-25 · Zbl 1365.65123
[10] Dembo RS, Eisenstat SC, Steihaug T (1982) Inexact Newton methods. SIAM J Numer Anal 19(2):400-408 · Zbl 0478.65030 · doi:10.1137/0719025
[11] Dempster AP (1972) Covariance selection. Biometrics 28:157-175 · doi:10.2307/2528966
[12] Eisenstat SC, Walker HF (1996) Choosing the forcing terms in an inexact Newton method. SIAM J Sci Comput 17(1):16-32 · Zbl 0845.65021 · doi:10.1137/0917003
[13] Hastie T, Tibshirani R, Wainwright M (2015) Statistical learning with sparsity. The lasso and generalizations. CRC Press, Boca Raton · Zbl 1319.68003
[14] Hiriart-Urruty J-B, Lemaréchal C (1993) Convex analysis and minimization algorithms I, volume 305 of Grundlehren der mathematischen Wissenschaften. Springer, New York · Zbl 0795.49001 · doi:10.1007/978-3-662-02796-7
[15] Hsieh C-J, Sustik MA, Dhillon IS, Ravikumar P (2011) Sparse inverse covariance matrix estimation using quadratic approximation. Adv Neural Inf Process (NIPS) 24:2330-2338
[16] Kyrillidis A, Karimi-Mahabadi R, Tran-Dinh Q, Cevher V (2014) Scalable sparse covariance estimation via self-concordance. In: Proceedings of the 28th AAAI conference on artificial intelligence, pp 1946-1952
[17] Lee JD, Sun Y, Saunders MA (2014) Proximal Newton-type methods for minimizing composite functions. SIAM J Optim 24(3):1420-1443 · Zbl 1306.65213 · doi:10.1137/130921428
[18] Moreau JJ (1965) Proximité et dualité dans un espace hilbertien. Bull Math Soc Fr 93:273-299 · Zbl 0136.12101 · doi:10.24033/bsmf.1625
[19] Nesterov Y (2004) Introductory lectures on convex optimization. Kluwer Academic Publishers, Dordrecht · Zbl 1086.90045 · doi:10.1007/978-1-4419-8853-9
[20] Nesterov Y (2012) Towards non-symmetric conic optimization. Optim Methods Softw 27(4-5):893-917 · Zbl 1260.90129 · doi:10.1080/10556788.2011.567270
[21] Nesterov Y, Nemirovskii A (1994) Interior-point polynomial methods in convex programming, volume 13 of studies in applied mathematics. SIAM, Philadelphia · Zbl 0824.90112
[22] Olsen PA, Oztoprak F, Nocedal J, Rennie SJ (2012) Newton-like methods for sparse inverse covariance estimation. Adv Neural Inf Process (NIPS) 25:764-772
[23] Renegar J (2001) A mathematical view of interior-point methods in convex optimization. SIAM, Philadelphia · Zbl 0986.90075 · doi:10.1137/1.9780898718812
[24] Scheinberg K, Goldfarb D, Bai X (2014) Fast first-order methods for composite convex optimization with backtracking. Found Comput Math 14:389-417 · Zbl 1304.90161 · doi:10.1007/s10208-014-9189-9
[25] Scheinberg, K.; Ma, S.; Sra, S. (ed.); Nowozin, S. (ed.); Wright, SJ (ed.), Optimization methods for sparse inverse covariance selection, 455-477 (2012), Cambridge
[26] Scheinberg K, Tang X (2013) Complexity of inexact proximal Newton methods. Technical Report 13T-02-R1, COR@L. Lehigh University, 2013 · Zbl 1366.90166
[27] Tran-Dinh Q, Kyrillidis A, Cevher V (2014) An inexact proximal path-following algorithm for constrained convex optimization. SIAM J Optim 24(4):1718-1745 · Zbl 1311.90104 · doi:10.1137/130944539
[28] Tran-Dinh Q, Kyrillidis A, Cevher V (2015) Composite self-concordant minimization. J Mach Learn Res 16:371-416 · Zbl 1337.68231
[29] Vandenberghe L, Andersen MS (2014) Chordal graphs and semidefinite optimization. Found Trends Optim 1(4):241-433 · doi:10.1561/2400000006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.