Training very large scale nonlinear SVMs using Alternating Direction Method of Multipliers coupled with the Hierarchically Semi-Separable kernel approximations
Typically, nonlinear Support Vector Machines (SVMs) produce significantly higher classification quality when compared to linear ones but, at the same time, their computational complexity is prohibitive for large-scale datasets: this drawback is essentially related to the necessity to store and manip...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2022-01-01
|
| Series: | EURO Journal on Computational Optimization |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2192440622000223 |
| _version_ | 1811201343153504256 |
|---|---|
| author | S. Cipolla J. Gondzio |
| author_facet | S. Cipolla J. Gondzio |
| author_sort | S. Cipolla |
| collection | DOAJ |
| description | Typically, nonlinear Support Vector Machines (SVMs) produce significantly higher classification quality when compared to linear ones but, at the same time, their computational complexity is prohibitive for large-scale datasets: this drawback is essentially related to the necessity to store and manipulate large, dense and unstructured kernel matrices. Despite the fact that at the core of training an SVM there is a simple convex optimization problem, the presence of kernel matrices is responsible for dramatic performance reduction, making SVMs unworkably slow for large problems. Aiming at an efficient solution of large-scale nonlinear SVM problems, we propose the use of the Alternating Direction Method of Multipliers coupled with Hierarchically Semi-Separable (HSS) kernel approximations. As shown in this work, the detailed analysis of the interaction among their algorithmic components unveils a particularly efficient framework and indeed, the presented experimental results demonstrate, in the case of Radial Basis Kernels, a significant speed-up when compared to the state-of-the-art nonlinear SVM libraries (without significantly affecting the classification accuracy). |
| first_indexed | 2024-04-12T02:20:19Z |
| format | Article |
| id | doaj.art-b8ffb841671b4d0db9f64294bb0c43a3 |
| institution | Directory Open Access Journal |
| issn | 2192-4406 |
| language | English |
| last_indexed | 2024-04-12T02:20:19Z |
| publishDate | 2022-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | EURO Journal on Computational Optimization |
| spelling | doaj.art-b8ffb841671b4d0db9f64294bb0c43a32022-12-22T03:52:09ZengElsevierEURO Journal on Computational Optimization2192-44062022-01-0110100046Training very large scale nonlinear SVMs using Alternating Direction Method of Multipliers coupled with the Hierarchically Semi-Separable kernel approximationsS. Cipolla0J. Gondzio1Corresponding authors.; The University of Edinburgh, School of Mathematics, United Kingdom of Great Britain and Northern IrelandCorresponding authors.; The University of Edinburgh, School of Mathematics, United Kingdom of Great Britain and Northern IrelandTypically, nonlinear Support Vector Machines (SVMs) produce significantly higher classification quality when compared to linear ones but, at the same time, their computational complexity is prohibitive for large-scale datasets: this drawback is essentially related to the necessity to store and manipulate large, dense and unstructured kernel matrices. Despite the fact that at the core of training an SVM there is a simple convex optimization problem, the presence of kernel matrices is responsible for dramatic performance reduction, making SVMs unworkably slow for large problems. Aiming at an efficient solution of large-scale nonlinear SVM problems, we propose the use of the Alternating Direction Method of Multipliers coupled with Hierarchically Semi-Separable (HSS) kernel approximations. As shown in this work, the detailed analysis of the interaction among their algorithmic components unveils a particularly efficient framework and indeed, the presented experimental results demonstrate, in the case of Radial Basis Kernels, a significant speed-up when compared to the state-of-the-art nonlinear SVM libraries (without significantly affecting the classification accuracy).http://www.sciencedirect.com/science/article/pii/S2192440622000223Computational scienceSupport vector machinesHierarchically Semi-Separable kernel approximationsAlternating Direction Method of Multipliers |
| spellingShingle | S. Cipolla J. Gondzio Training very large scale nonlinear SVMs using Alternating Direction Method of Multipliers coupled with the Hierarchically Semi-Separable kernel approximations EURO Journal on Computational Optimization Computational science Support vector machines Hierarchically Semi-Separable kernel approximations Alternating Direction Method of Multipliers |
| title | Training very large scale nonlinear SVMs using Alternating Direction Method of Multipliers coupled with the Hierarchically Semi-Separable kernel approximations |
| title_full | Training very large scale nonlinear SVMs using Alternating Direction Method of Multipliers coupled with the Hierarchically Semi-Separable kernel approximations |
| title_fullStr | Training very large scale nonlinear SVMs using Alternating Direction Method of Multipliers coupled with the Hierarchically Semi-Separable kernel approximations |
| title_full_unstemmed | Training very large scale nonlinear SVMs using Alternating Direction Method of Multipliers coupled with the Hierarchically Semi-Separable kernel approximations |
| title_short | Training very large scale nonlinear SVMs using Alternating Direction Method of Multipliers coupled with the Hierarchically Semi-Separable kernel approximations |
| title_sort | training very large scale nonlinear svms using alternating direction method of multipliers coupled with the hierarchically semi separable kernel approximations |
| topic | Computational science Support vector machines Hierarchically Semi-Separable kernel approximations Alternating Direction Method of Multipliers |
| url | http://www.sciencedirect.com/science/article/pii/S2192440622000223 |
| work_keys_str_mv | AT scipolla trainingverylargescalenonlinearsvmsusingalternatingdirectionmethodofmultiplierscoupledwiththehierarchicallysemiseparablekernelapproximations AT jgondzio trainingverylargescalenonlinearsvmsusingalternatingdirectionmethodofmultiplierscoupledwiththehierarchicallysemiseparablekernelapproximations |