On the working set selection in gradient projection-based decomposition techniques for support vector machines.

*(English)*Zbl 1116.90115Summary: This work deals with special decomposition techniques for the large quadratic program arising in training support vector machines. These approaches split the problem into a sequence of quadratic programming (QP) subproblems which can be solved by efficient gradient projection methods recently proposed. Owing to the ability of decomposing the problem into much larger subproblems than standard decomposition packages, these techniques show promising performance and are well suited for parallelization. Here, we discuss a crucial aspect for their effectiveness: the selection of the working set; that is, the index set of the variables to be optimized at each step through the QP subproblem. We analyze the most popular working set selections and develop a new selection strategy that improves the convergence rate of the decomposition schemes based on large sized working sets. The effectiveness of the proposed strategy within the gradient projection-based decomposition techniques is shown by numerical experiments on large benchmark problems, both in serial and in parallel environments.

##### MSC:

90C52 | Methods of reduced gradient type |

65K05 | Numerical mathematical programming methods |

68T05 | Learning and adaptive systems in artificial intelligence |

##### Keywords:

support vector machines; quadratic programs; decomposition techniques; gradient projection methods; large-scale problems
PDF
BibTeX
Cite

\textit{T. Serafini} and \textit{L. Zanni}, Optim. Methods Softw. 20, No. 4--5, 583--596 (2005; Zbl 1116.90115)

Full Text:
DOI

##### References:

[1] | Cristianini N., An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods (2000) · Zbl 0994.68074 |

[2] | Vapnik V. N., Statistical Learning Theory (1998) · Zbl 0935.62007 |

[3] | Chang, C. C. and Lin, C. J. 2002. ”LIBSVM: a library for support vector machines”. Available online at:www.csie.ntu.edu.tw/cjlin/libsvm |

[4] | DOI: 10.1023/A:1012474916001 · Zbl 0998.68107 |

[5] | DOI: 10.1162/089976601300014493 · Zbl 1085.68629 |

[6] | Platt J. C., Advances in Kernel Methods–Support Vector Learning (1998) |

[7] | DOI: 10.1162/15324430152733142 · Zbl 1052.68111 |

[8] | DOI: 10.1023/A:1012427100071 · Zbl 0998.68108 |

[9] | Joachims T., Advances in Kernel Methods–Support Vector Learning (1998) |

[10] | Osuna, E., Freund, R. and Girosi, F. Training support vector machines: an application to face detection. Proceedings of the CVPR’97, pp.130–136. IEEE Computer Society, Puerto Rico. |

[11] | DOI: 10.1016/S0167-8191(03)00021-8 |

[12] | DOI: 10.1080/10556780512331318182 · Zbl 1072.90026 |

[13] | Zanghirati, G. and Zanni, L. 2003. ”Variable projection method for large quadratic programs in training support vector machines”. Department of Mathematics, University of Ferrara. Technical Report 339 · Zbl 1054.65062 |

[14] | Dai, Y. H. and Fletcher, R. 2003. ”New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds”. Department of Mathematics, University of Dundee. Research Report NA/216 · Zbl 1134.90030 |

[15] | DOI: 10.1007/BF01585748 · Zbl 0711.90061 |

[16] | Galligani E., Equilibrium Problems and Variational Models, Nonconvex Optimization and Its Application 68 pp 186– (2003) |

[17] | DOI: 10.1023/A:1004605612267 · Zbl 0962.90036 |

[18] | Ruggiero V., Recent Trends in Numerical Analysis pp 299– (2000) |

[19] | DOI: 10.1109/72.857780 |

[20] | DOI: 10.1109/72.963765 |

[21] | Lin, C. J. 2001. ”Linear convergence of a decomposition method for support vector machines”. Department of Computer Science and Information Engineering, National Taiwan University. Technical Report |

[22] | DOI: 10.1023/A:1012431217818 · Zbl 0998.68109 |

[23] | DOI: 10.1109/72.977319 |

[24] | DOI: 10.1080/10556780512331318209 · Zbl 1072.90042 |

[25] | DOI: 10.1109/72.788643 |

[26] | Murphy, P. M. and Aha, D. W. 1992. ”UCI repository of machine learning databases. Avabilable online at”. www.ics.uci.edu/mlearn/MLRepository.html |

[27] | LeCun, Y. ”The MNIST Database of handwritten digit”. Available online at: yann.lecun.com/exdb/mnist |

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.