QP Algorithms with Guaranteed Accuracy and Run Time for Support Vector Machines

By Don R. Hush, Patrick A. Kelly, Clint Scovel, Ingo Steinwart. 2006

88 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, methodology): “Further, note that Hush et al. [2006] show that we can obtain an ǫ -accurate solution to the primal problem with an O ( ǫ 2 )-accurate solution to the dual problem.”
Stochastic dual coordinate ascent methods for regularized loss (2012, positive): “For SVM, [4, Theorem 2] showed that in order to obtain a primal (cid:15) P -sub-optimal solution, we need a dual (cid:15) D -sub-optimal solution with (cid:15) D = O ( λ(cid:15) 2 P ) ; therefore a convergence result for dual solution can only translate into a primal convergence result with worse…”
Safety in numbers: Learning categories from few examples with multi model knowledge transfer (2010, methodology): “We match the complexity of a plain SVM, which in the worst case is known to be O(l(3)) [13], and is the standard out-of-the-shelf classification method commonly used on datasets with more than 10(3) images.”
Radial kernels and their reproducing kernel Hilbert spaces (2010, background): “Moreover, efficient learning algorithms have been developed for arbitrary kernels in e. g. [17] [16] [20].”
Learning Categories From Few Examples With Multi Model Knowledge Transfer (2014, background): “Thus, we match the complexity of a plain SVM, which in the worst case is known to be O(N3) [36].”
Block-Coordinate Gradient Descent Method for Linearly Constrained Nonsmooth Separable Optimization (2009, methodology): “currently best bounds for decomposition methods [26, 32, 33 ]; see Sect.”
Primal-Dual Rates and Certificates (2016, result): “For the SVM case, this rate is consistent with the result of (Hush et al., 2006).”
Support Vector Machine Solvers (2007, methodology): “• The asymptotic convergence and finite termination properties of this particular case of the decomposition method are very well understood (e.g. Keerthi and Gilbert, 2002; Takahashi and Nishi, 2005; Chen et al., 2006; Hush et al., 2006).”
The Tradeoffs of Large Scale Learning (2007, background): “…(2008) rigorously extend the analysis to regularized risk formulations with linear parametrization and ﬁnd again that, for learning purposes, SGD algorithms are often more attractive than standard primal or dual algorithms with good optimization complexity (Joachims, 2006; Hush et al., 2006).”
From N to N+1: Multiclass Transfer Incremental Learning (2013, background): “Note that this complexity is better than the one of a classical OVA SVM which in worst case is known to be in O(M3N) [10].”