FASOLE: Fast Algorithm for Structured Output LEarning

Vojtech Franc

Abstract

This paper proposes a novel Fast Algorithm for Structured Ouput LEarning (FASOLE). FASOLE implements the sequential dual ascent (SDA) algorithm for solving the dual problem of the Structured Output Support Vector Machines (SO-SVM). Unlike existing instances of SDA algorithm applied for SO-SVM, the proposed FASOLE uses a different working set selection strategy which provides nearly maximal improvement of the objective function in each update. FASOLE processes examples in an on-line fashion and it provides certificate of optimality. FASOLE is guaranteed to find the ε-optimal solution in $\mathcal{O}(\frac{1}{\varepsilon^2})$ time in the worst case. In the empirical comparison FASOLE consistently outperforms the existing state-of-the-art solvers, like the Cutting Plane Algorithm or the Block-Coordinate Frank-Wolfe algorithm, achieving up to an order of magnitude speedups while obtaining the same precise solution.
BibTeX
@inproceedings{franc2014fasole,
  author = {Vojtech Franc},
  title = {{FASOLE: Fast Algorithm for Structured Output LEarning}},
  booktitle = {ECML/PKDD},
  year = {2014},
  doi = {10.1007/978-3-662-44848-9\_26},
}

Loading related content...

Figure