A solution path algorithm for general parametric quadratic programming problem

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

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.

Original languageEnglish
Article number8123882
Pages (from-to)4462-4472
Number of pages11
JournalIEEE Transactions on Neural Networks and Learning Systems
Volume29
Issue number9
DOIs
StatePublished - Sep 2018

Keywords

  • Cross validation (CV)
  • QR decomposition
  • parametric quadratic programming (PQP)
  • solution path

Fingerprint Dive into the research topics of 'A solution path algorithm for general parametric quadratic programming problem'. Together they form a unique fingerprint.

  • Cite this