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.

On the working set selection in gradient projection-based decomposition techniques for support vector machines / Serafini, Thomas; Zanni, Luca. - In: OPTIMIZATION METHODS & SOFTWARE. - ISSN 1055-6788. - STAMPA. - 20:4-5(2005), pp. 583-596. [10.1080/10556780500140714]

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

SERAFINI, Thomas;ZANNI, Luca
2005

Abstract

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.
2005
20
4-5
583
596
On the working set selection in gradient projection-based decomposition techniques for support vector machines / Serafini, Thomas; Zanni, Luca. - In: OPTIMIZATION METHODS & SOFTWARE. - ISSN 1055-6788. - STAMPA. - 20:4-5(2005), pp. 583-596. [10.1080/10556780500140714]
Serafini, Thomas; Zanni, Luca
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/303699
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 19
social impact