×

zbMATH — the first resource for mathematics

Nondegenerate piecewise linear systems: finite Newton algorithm and applications in machine learning. (English) Zbl 1256.65062
Summary: We investigate Newton-type optimization methods for solving piecewise linear systems (PLSs) with nondegenerate coefficient matrix. Such systems arise, for example, from the numerical solution of a linear complementarity problem, which is useful to model several learning and optimization problems. In this letter, we propose an effective damped Newton method, PLS-DN, to find the exact (up to machine precision) solution of nondegenerate PLSs. PLS-DN exhibits provable semiiterative property, that is, the algorithm converges globally to the exact solution in a finite number of iterations. The rate of convergence is shown to be at least linear before termination. We emphasize the applications of our method in modeling, from a novel perspective of PLSs, some statistical learning problems such as box-constrained least squares, elitist Lasso [M. Kowalski and B. TorrĂ©sani, Signal Image Video Process. 3, No. 3, 251–264 (2009)], and support vector machines [C. Cortes and V. Vapnik, Mach. Learn. 20, No. 3, 273–297 (1995; Zbl 0831.68098)]. Numerical results on synthetic and benchmark data sets are presented to demonstrate the effectiveness and efficiency of PLS-DN on these problems.

MSC:
65K05 Numerical mathematical programming methods
65F10 Iterative numerical methods for linear systems
68T05 Learning and adaptive systems in artificial intelligence
90C20 Quadratic programming
90C53 Methods of quasi-Newton type
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1017/CBO9780511804441 · doi:10.1017/CBO9780511804441
[2] DOI: 10.1137/070681867 · Zbl 1155.90457 · doi:10.1137/070681867
[3] DOI: 10.1137/08072749X · Zbl 1190.90233 · doi:10.1137/08072749X
[4] DOI: 10.1063/1.3241581 · Zbl 1180.65083 · doi:10.1063/1.3241581
[5] DOI: 10.1023/A:1009715923555 · Zbl 05470543 · doi:10.1023/A:1009715923555
[6] DOI: 10.1016/0021-9991(90)90091-E · Zbl 0681.76022 · doi:10.1016/0021-9991(90)90091-E
[7] DOI: 10.1162/neco.2007.19.5.1155 · Zbl 1123.68101 · doi:10.1162/neco.2007.19.5.1155
[8] DOI: 10.1016/j.laa.2010.06.025 · Zbl 1202.65042 · doi:10.1016/j.laa.2010.06.025
[9] DOI: 10.1137/S1052623494240456 · Zbl 0861.65053 · doi:10.1137/S1052623494240456
[10] DOI: 10.1109/JSTSP.2007.910264 · doi:10.1109/JSTSP.2007.910264
[11] Cortes C., Machine Learning 20 pp 40– (1995)
[12] Cottle R. W., The linear complementarity problem (1992) · Zbl 0757.90078
[13] DOI: 10.1109/18.382009 · Zbl 0820.62002 · doi:10.1109/18.382009
[14] DOI: 10.1145/62038.62043 · Zbl 0667.65040 · doi:10.1145/62038.62043
[15] DOI: 10.1287/mnsc.17.9.612 · Zbl 0228.15004 · doi:10.1287/mnsc.17.9.612
[16] DOI: 10.1007/BF02192160 · Zbl 0839.90121 · doi:10.1007/BF02192160
[17] Fischer A., Mathematical Programming: Series A and B 74 pp 279– (1996)
[18] Harker P. T., Computational solution of nonlinear systems of equations (1990)
[19] DOI: 10.1007/BF01582262 · Zbl 0724.90071 · doi:10.1007/BF01582262
[20] DOI: 10.1017/CBO9780511840371 · doi:10.1017/CBO9780511840371
[21] DOI: 10.1007/s10107-007-0196-3 · Zbl 1164.65018 · doi:10.1007/s10107-007-0196-3
[22] DOI: 10.1145/1553374.1553431 · doi:10.1145/1553374.1553431
[23] DOI: 10.1214/aoms/1177697089 · Zbl 0193.45201 · doi:10.1214/aoms/1177697089
[24] Kowalski M., Signal, Image and Video Processing (2008)
[25] Kummer B., Mathematical research: Advances in mathematical optimization (1988)
[26] DOI: 10.1287/moor.15.2.311 · Zbl 0716.90090 · doi:10.1287/moor.15.2.311
[27] DOI: 10.1137/050623723 · Zbl 1128.90058 · doi:10.1137/050623723
[28] DOI: 10.1287/moor.18.1.227 · Zbl 0776.65037 · doi:10.1287/moor.18.1.227
[29] Schmidt M., International Conference on Artificial Intelligence and Statistics (2009)
[30] DOI: 10.1002/fld.537 · Zbl 1062.76541 · doi:10.1002/fld.537
[31] DOI: 10.1137/1.9781611971453 · doi:10.1137/1.9781611971453
[32] DOI: 10.1111/j.1467-9868.2005.00532.x · Zbl 1141.62030 · doi:10.1111/j.1467-9868.2005.00532.x
[33] Yuan X., Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (2011)
[34] Zhou Y., Proc. of the International Conference on Artificial Intelligence and Statistics (2010)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.