Timezone: »

 
Poster
Lower Bounds on Rate of Convergence of Cutting Plane Methods
Xinhua Zhang · Ankan Saha · S.V.N. Vishwanathan

Wed Dec 08 12:00 AM -- 12:00 AM (PST) @
in Poster Session »
In a recent paper Joachims (2006) presented SVM-Perf, a cutting plane method (CPM) for training linear Support Vector Machines (SVMs) which converges to an $\epsilon$ accurate solution in $O(1/\epsilon^{2})$ iterations. By tightening the analysis, Teo et al. (2010) showed that $O(1/\epsilon)$ iterations suffice. Given the impressive convergence speed of CPM on a number of practical problems, it was conjectured that these rates could be further improved. In this paper we disprove this conjecture. We present counter examples which are not only applicable for training linear SVMs with hinge loss, but also hold for support vector methods which optimize a \emph{multivariate} performance score. However, surprisingly, these problems are not inherently hard. By exploiting the structure of the objective function we can devise an algorithm that converges in $O(1/\sqrt{\epsilon})$ iterations.
[ PDF] 

Author Information

Xinhua Zhang (University of Illinois at Chicago (UIC))
Ankan Saha (Linkedin Corporation)
S.V.N. Vishwanathan (UCSC)

More from the Same Authors