TY - JOUR

T1 - A solution path algorithm for general parametric quadratic programming problem

AU - Gu, Bin

AU - Sheng, Victor S.

N1 - Funding Information:
Manuscript received October 15, 2016; revised June 15, 2017 and October 30, 2017; accepted November 1, 2017. Date of publication November 29, 2017; date of current version August 20, 2018. This work was supported in part by the Priority Academic Program Development of Jiangsu Higher Education Institutions, in part by the Natural Science Foundation under Grant BK20161534, in part by the Six Talent Peaks Project under Grant XYDXX-042, in part by the 333 Project in Jiangsu Province under Grant BRA2017455, in part by the U.S. National Science Foundation under Grant IIS-1115417, and in part by the National Natural Science Foundation of China under Grant 61232016, Grant 61573191, Grant 61572259, and Grant 61728205. (Corresponding author: Bin Gu.) B. Gu is with the Jiangsu Engineering Center of Network Monitoring, Nanjing University of Information Science and Technology, Nanjing 210044, China, and also with the School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044, China (e-mail: jsgubin@nuist.edu.cn).
Publisher Copyright:
© 2012 IEEE.

PY - 2018/9

Y1 - 2018/9

N2 - Parameter in learning problems (usually arising from the tradeoff between training error minimization and regularization) is often tuned by cross validation (CV). A solution path provides a compact representation of all optimal solutions, which can be used to determine the parameter with the global minimum CV error, without solving original optimization problems multiple times based on grid search. However, existing solution path algorithms do not provide a unified implementation to various learning problems. In this paper, we first introduce a general parametric quadratic programming (PQP) problem that can be instantiated to an extensive number of learning problems. Then, we propose a generalized solution path (GSP) for the general PQP problem. Particularly, we use the QR decomposition to handle singularities in GSP. Finally, we analyze the finite convergence and the time complexity of GSP. Our experimental results on a variety of data sets not only confirm the identicality between GSP and several existing solution path algorithms but also show the superiority of our GSP over the existing solution path algorithms on both generalization and robustness. Finally, we provide a practical guild of using the GSP to solve two important learning problems, i.e., generalized error path and Ivanov SVM.

AB - Parameter in learning problems (usually arising from the tradeoff between training error minimization and regularization) is often tuned by cross validation (CV). A solution path provides a compact representation of all optimal solutions, which can be used to determine the parameter with the global minimum CV error, without solving original optimization problems multiple times based on grid search. However, existing solution path algorithms do not provide a unified implementation to various learning problems. In this paper, we first introduce a general parametric quadratic programming (PQP) problem that can be instantiated to an extensive number of learning problems. Then, we propose a generalized solution path (GSP) for the general PQP problem. Particularly, we use the QR decomposition to handle singularities in GSP. Finally, we analyze the finite convergence and the time complexity of GSP. Our experimental results on a variety of data sets not only confirm the identicality between GSP and several existing solution path algorithms but also show the superiority of our GSP over the existing solution path algorithms on both generalization and robustness. Finally, we provide a practical guild of using the GSP to solve two important learning problems, i.e., generalized error path and Ivanov SVM.

KW - Cross validation (CV)

KW - QR decomposition

KW - parametric quadratic programming (PQP)

KW - solution path

UR - http://www.scopus.com/inward/record.url?scp=85037650683&partnerID=8YFLogxK

U2 - 10.1109/TNNLS.2017.2771456

DO - 10.1109/TNNLS.2017.2771456

M3 - Article

C2 - 29990069

AN - SCOPUS:85037650683

VL - 29

SP - 4462

EP - 4472

JO - IEEE Transactions on Neural Networks and Learning Systems

JF - IEEE Transactions on Neural Networks and Learning Systems

SN - 2162-237X

IS - 9

M1 - 8123882

ER -