Back

Training linear SVMs in linear time

Thorsten Joachims

article2006KDD2,195 citations

Presents a cutting-plane algorithm based on an equivalent structural optimization formulation that provably trains linear Support Vector Machines in linear time, dramatically outperforming traditional decomposition methods on large, high-dimensional datasets.

Listen

Modern data applications in domains such as text categorization, search ranking, and computational drug design frequently process datasets containing hundreds of thousands to millions of examples with tens of thousands of features. Linear Support Vector Machines provide state-of-the-art accuracy for these high-dimensional, sparse data problems. However, traditional training algorithms exhibit super-linear computational scaling relative to the number of examples, making large-scale training slow or computationally intractable. For ordinal regression tasks, existing solvers experience quadratic growth in effective problem size, typically stalling on datasets with more than a few thousand records.

The article develops and evaluates a cutting-plane optimization algorithm, implemented as SVM-Perf, designed to train linear Support Vector Machines in provably linear time for binary classification and near-linear time for ordinal regression. The objective is to eliminate scalability bottlenecks while maintaining exact equivalence to standard soft-margin models.

To evaluate this approach, the author reformulates the standard training problem into an equivalent structural formulation that shares a single slack variable across exponentially many subset constraints. This structure allows a cutting-plane method to greedily identify the most violated constraint in each iteration, guaranteeing convergence within a constant number of steps that does not grow with the training set size. The method was evaluated across five diverse, large-scale benchmarks spanning text classification, physics, and forestry, comprising up to 804,414 examples and 99,757 features. Performance was directly benchmarked against the standard decomposition solver SVM-Light.

The experimental and theoretical results demonstrate substantial performance gains. First, the algorithm achieves provable computational complexity of O(sn) for classification and O(sn log n) for ordinal regression, where s is the average number of non-zero features and n is the sample size. Second, SVM-Perf delivers dramatic speedups over SVM-Light, executing approximately 100 times faster on large text datasets (150 CPU-seconds versus 20,075 CPU-seconds on Reuters CCAT) and roughly 150 times faster on forest cover data. Third, empirical training times grew sub-linearly with the number of examples (roughly proportional to n^0.8), driven by an iteration count that remains bounded or even decreases on larger samples. Fourth, SVM-Perf successfully solved ordinal regression problems on over 800,000 examples in minutes, whereas SVM-Light became computationally intractable beyond approximately 4,000 examples. Finally, these efficiency gains caused no loss in statistical accuracy; predictive performance remained virtually identical between solvers across regularized parameters.

These findings mean that organizations can train linear models on massive datasets at a fraction of the computational time and infrastructure cost previously required. The algorithm also introduces an intuitive stopping tolerance directly tied to training loss, preventing wasteful over-optimization. For operations reliant on search ranking or ranking metrics like the area under the receiver operating characteristic curve, the approach turns previously intractable ranking tasks into routine computations.

Decision-makers and engineering teams managing large-scale text or sparse tabular data should adopt cutting-plane methods like SVM-Perf in place of legacy decomposition solvers for linear classification and ranking. Future development should focus on implementing parallel, out-of-core memory variants of the algorithm to process datasets that exceed system RAM, as well as exploring sampling and matrix approximation techniques to adapt the approach to non-linear kernel models.

These performance advantages apply specifically to linear models trained on sparse, high-dimensional data. For dense data with few features, other specialized solvers remain competitive, and extending the cutting-plane method directly to standard non-linear kernels introduces substantial computational overhead. Within the defined scope of linear models on sparse data, the theoretical proofs and consistent experimental benchmarks provide high confidence in the algorithm's speed and reliability.

Cornell Universityoptimizationoptimization problemssupport vectorTrainingTimeAlgorithm
Joachims (2006).pdf
  • Paper: LIBLINEAR: A Library for Large Linear Classification, Rong-En Fan et al. (2008). LIBLINEAR extends the linear SVM cutting-plane principles of the source paper into a comprehensive, high-performance open-source library for massive linear classification tasks.
Cover for Training linear SVMs in linear time

Abstract

Linear Support Vector Machines (SVMs) have become one of the most prominent machine learning techniques for high-dimensional sparse data commonly encountered in applications like text classification, word-sense disambiguation, and drug design. These applications involve a large number of examples n as well as a large number of features N, while each example has only s << N non-zero features. This paper presents a Cutting-Plane Algorithm for training linear SVMs that provably has training time O(sn) for classification problems and O(s n log(n)) for ordinal regression problems. The algorithm is based on an alternative, but equivalent formulation of the SVM optimization problem. Empirically, the Cutting-Plane Algorithm is several orders of magnitude faster than decomposition methods like SVM-Light for large datasets.

Topics

optimizationoptimization problemssupport vectorsvmtext classificationword senseadaptive boostingmulti-class classification

Keywords

TrainingTimeAlgorithmClassi CationSVMsLinearNumberOrdinal RegressionSVMSVM-Perf

Table of Contents

  • 1. INTRODUCTION
  • 2. STRUCTURAL SVMS
  • 2.1 Classification
  • 2.2 Ordinal Regression
  • 3. CUTTING-PLANE ALGORITHM
  • 3.1 Classification
  • 3.2 Ordinal Regression
  • 4. EXPERIMENTS
  • 4.1 How Fast are the Algorithms Compared to Existing Methods?
  • 4.2 How does Training Time Scale with the Number of Training Examples?
  • 4.3 Is the Prediction Performance of SVMPerf Different from SVM-Light?
  • 4.4 How Small does ϵ need to be?
  • 4.5 How does Training Time Scale with ϵ ?
  • 4.6 Is the Solution Computed by SVM-Perf Close to Optimal?
  • 4.7 How does Training Time Scale with C?
  • 5. ACKNOWLEDGMENTS
  • 6. CONCLUSIONS
  • 7. REFERENCES

Knowls

  1. Knowl 1 — Structural Formulation of Linear Classification SVM and Equivalence

    model/method

    The standard primal formulation of a linear binary classification Support Vector Machine (with bias b=0b=0) on training data (x1,y1),…,(xn,yn)(x_1, y_1), \dots, (x_n, y_n) where xi∈RNx_i \in \mathbb{R}^N and yi∈{−1,+1}y_i \in \{-1, +1\} is given by:

    min⁡w,ξi≥012wTw+Cn∑i=1nξis.t.∀i∈{1,…,n}:yi(wTxi)≥1−ξi\min_{w, \xi_i \ge 0} \frac{1}{2} w^T w + \frac{C}{n} \sum_{i=1}^n \xi_i \quad \text{s.t.} \quad \forall i \in \{1, \dots, n\}: y_i(w^T x_i) \ge 1 - \xi_i

    where w∈RNw \in \mathbb{R}^N is the weight vector, C>0C > 0 is the regularization parameter, and ξi\xi_i are individual slack variables.

    The equivalent structural formulation introduces a single slack variable ξ≥0\xi \ge 0 shared across 2n2^n linear constraints, each corresponding to a binary selection vector c=(c1,…,cn)∈{0,1}nc = (c_1, \dots, c_n) \in \{0, 1\}^n:

    min⁡w,ξ≥012wTw+Cξs.t.∀c∈{0,1}n:1nwT∑i=1nciyixi≥1n∑i=1nci−ξ\min_{w, \xi \ge 0} \frac{1}{2} w^T w + C\xi \quad \text{s.t.} \quad \forall c \in \{0, 1\}^n: \frac{1}{n} w^T \sum_{i=1}^n c_i y_i x_i \ge \frac{1}{n} \sum_{i=1}^n c_i - \xi

    Any optimal weight vector w∗w^* of the structural formulation is also an optimal solution to the standard formulation (and vice versa), with the optimal slacks satisfying ξ∗=1n∑i=1nξi∗\xi^* = \frac{1}{n} \sum_{i=1}^n \xi_i^*.

  2. Knowl 2 — Cutting-Plane Algorithm for Linear Classification SVM

    algorithm

    The cutting-plane algorithm trains a linear classification SVM by iteratively identifying and adding the most violated constraint from the exponential set of structural constraints into a working set WW. In each iteration, it solves a quadratic program over WW, finds the most violated constraint vector c∈{0,1}nc \in \{0, 1\}^n in linear time O(sn)O(sn) by checking yi(wTxi)<1y_i(w^T x_i) < 1 for each example, and stops when the violation of the most violated constraint is at most ϵ\epsilon.

    For any training sample SS and tolerance ϵ>0\epsilon > 0, the algorithm terminates with a solution (w,ξ)(w, \xi) that satisfies 12wTw+Cξ≤12(w∗)Tw∗+Cξ∗\frac{1}{2} w^T w + C\xi \le \frac{1}{2} (w^*)^T w^* + C\xi^* (where (w∗,ξ∗)(w^*, \xi^*) is the true optimum) and for which (w,ξ+ϵ)(w, \xi + \epsilon) is feasible in the structural primal problem.

    Input: Training sample S=((x1,y1),…,(xn,yn))S = ((x_1, y_1), \dots, (x_n, y_n)), regularization parameter C>0C > 0, tolerance ϵ>0\epsilon > 0
    Output: Primal solution (w,ξ)(w, \xi)
    W←∅W \leftarrow \emptyset
    repeat
        (w,ξ)←argmin⁡w,ξ≥012wTw+Cξ(w, \xi) \leftarrow \operatorname{argmin}_{w, \xi \ge 0} \frac{1}{2} w^T w + C\xi
            subject to ∀c∈W:1nwT∑i=1nciyixi≥1n∑i=1nci−ξ\forall c \in W: \frac{1}{n} w^T \sum_{i=1}^n c_i y_i x_i \ge \frac{1}{n} \sum_{i=1}^n c_i - \xi
        for i=1,…,ni = 1, \dots, n do
            if yi(wTxi)<1y_i (w^T x_i) < 1 then
                ci←1c_i \leftarrow 1
            else
                ci←0c_i \leftarrow 0
            end if
        end for
        W←W∪{c}W \leftarrow W \cup \{c\}
    until 1n∑i=1nci−1n∑i=1nciyi(wTxi)≤ξ+ϵ\frac{1}{n} \sum_{i=1}^n c_i - \frac{1}{n} \sum_{i=1}^n c_i y_i (w^T x_i) \le \xi + \epsilon
    return (w,ξ)(w, \xi)

  3. Knowl 3 — Iteration Bound and Time Complexity of Classification Cutting-Plane Algorithm

    theoretical result

    For any training set S=((x1,y1),…,(xn,yn))S = ((x_1, y_1), \dots, (x_n, y_n)) with bounded L2L_2-norm ∥xi∥2≤R=max⁡i∥xi∥2\|x_i\|_2 \le R = \max_i \|x_i\|_2, regularization parameter C>0C > 0, and precision ϵ>0\epsilon > 0:

    1. The cutting-plane algorithm terminates after adding at most:

    max⁡(2ϵ,8CR2ϵ2)\max\left( \frac{2}{\epsilon}, \frac{8 C R^2}{\epsilon^2} \right)

    constraints to the working set WW. This upper bound on the number of iterations is completely independent of the training set size nn.

    1. Each iteration runs in O(sn)O(sn) time for a constant working set size ∣W∣|W|, where ss is the average number of non-zero features per example (and N≤snN \le sn). Computing nn inner products wTxiw^T x_i requires O(sn)O(sn) operations, and forming the Hessian for the dual over WW takes O(∣W∣2sn)O(|W|^2 sn) operations.

    2. Consequently, for any distribution generating feature vectors of bounded L2L_2-norm and any fixed C>0C > 0 and ϵ>0\epsilon > 0, the overall training time complexity of the cutting-plane algorithm is O(sn)O(sn), scaling strictly linearly with sample size nn and sparsity ss.

  4. Knowl 4 — Structural Formulation of Linear Ordinal Regression SVM and Equivalence

    model/method

    In ordinal regression, examples (x1,y1),…,(xn,yn)(x_1, y_1), \dots, (x_n, y_n) have ordinal rank labels yi∈{1,…,R}y_i \in \{1, \dots, R\}. The pairwise formulation learns a ranking function h(x)=wTxh(x) = w^T x by optimizing over the set of ordered pairs P={(i,j):yi>yj}P = \{(i, j) : y_i > y_j\} with m=∣P∣m = |P|:

    min⁡w,ξij≥012wTw+Cm∑(i,j)∈Pξijs.t.∀(i,j)∈P:wTxi≥wTxj+1−ξij\min_{w, \xi_{ij} \ge 0} \frac{1}{2} w^T w + \frac{C}{m} \sum_{(i, j) \in P} \xi_{ij} \quad \text{s.t.} \quad \forall (i, j) \in P: w^T x_i \ge w^T x_j + 1 - \xi_{ij}

    The structural ordinal regression formulation collapses the m∈O(n2)m \in O(n^2) slack variables into a single slack variable ξ≥0\xi \ge 0 over 2m2^m joint constraints indexed by binary vectors c∈{0,1}mc \in \{0, 1\}^m:

    min⁡w,ξ≥012wTw+Cξs.t.∀c∈{0,1}m:1mwT∑(i,j)∈Pcij(xi−xj)≥1m∑(i,j)∈Pcij−ξ\min_{w, \xi \ge 0} \frac{1}{2} w^T w + C\xi \quad \text{s.t.} \quad \forall c \in \{0, 1\}^m: \frac{1}{m} w^T \sum_{(i, j) \in P} c_{ij} (x_i - x_j) \ge \frac{1}{m} \sum_{(i, j) \in P} c_{ij} - \xi

    Any optimal solution w∗w^* of the structural ordinal regression formulation is also an optimal solution of the pairwise ordinal regression problem and vice versa, with ξ∗=1m∑(i,j)∈Pξij∗\xi^* = \frac{1}{m} \sum_{(i, j) \in P} \xi_{ij}^*. When R=2R=2, this optimization directly maximizes the ROC-Area of the linear decision rule.

  5. Knowl 5 — Condensed Cutting-Plane Algorithm for Linear Ordinal Regression SVM

    algorithm

    To avoid enumerating m∈O(n2)m \in O(n^2) pairwise difference constraints, the structural ordinal regression constraint is represented compactly using counts ci+c_i^+ (the number of pairs in which xix_i appears with positive sign) and ci−c_i^- (the number of pairs in which xix_i appears with negative sign):

    1mwT∑i=1n(ci+−ci−)xi≥12m∑i=1n(ci++ci−)−ξ\frac{1}{m} w^T \sum_{i=1}^n (c_i^+ - c_i^-) x_i \ge \frac{1}{2m} \sum_{i=1}^n (c_i^+ + c_i^-) - \xi

    where 1m∑(i,j)∈Pcij=12m∑i=1n(ci++ci−)\frac{1}{m} \sum_{(i, j) \in P} c_{ij} = \frac{1}{2m} \sum_{i=1}^n (c_i^+ + c_i^-). The algorithm computes the most violated constraint in O(nlog⁡n+Rn)O(n \log n + Rn) time by first sorting SS according to wTxiw^T x_i, then maintaining prefix/suffix counts across ranks r∈{2,…,R}r \in \{2, \dots, R\}.

    Input: Training sample S=((x1,y1),…,(xn,yn))S = ((x_1, y_1), \dots, (x_n, y_n)), regularization parameter C>0C > 0, tolerance ϵ>0\epsilon > 0
    Output: Primal solution (w,ξ)(w, \xi)
    W←∅W \leftarrow \emptyset
    repeat
        (w,ξ)←argmin⁡w,ξ≥012wTw+Cξ(w, \xi) \leftarrow \operatorname{argmin}_{w, \xi \ge 0} \frac{1}{2} w^T w + C\xi
            subject to ∀(c+,c−)∈W:1mwT∑i=1n(ci+−ci−)xi≥12m∑i=1n(ci++ci−)−ξ\forall (c^+, c^-) \in W: \frac{1}{m} w^T \sum_{i=1}^n (c_i^+ - c_i^-) x_i \ge \frac{1}{2m} \sum_{i=1}^n (c_i^+ + c_i^-) - \xi
        sort SS by decreasing wTxiw^T x_i
        c+←0c^+ \leftarrow 0; c−←0c^- \leftarrow 0
        for r=2,…,Rr = 2, \dots, R do
            nr←number of examples with yi=rn_r \leftarrow \text{number of examples with } y_i = r
            i←1i \leftarrow 1; j←1j \leftarrow 1; a←0a \leftarrow 0; b←0b \leftarrow 0
            while i≤ni \le n do
                if yi=ry_i = r then
                    while (j≤n) and (wTxi−wTxj<1)(j \le n) \text{ and } (w^T x_i - w^T x_j < 1) do
                        if yj<ry_j < r then
                            b←b+1b \leftarrow b + 1
                            cj−←cj−+(nr−a+1)c_j^- \leftarrow c_j^- + (n_r - a + 1)
                        end if
                        j←j+1j \leftarrow j + 1
                    end while
                    a←a+1a \leftarrow a + 1
                    ci+←ci++bc_i^+ \leftarrow c_i^+ + b
                end if
                i←i+1i \leftarrow i + 1
            end while
        end for
        W←W∪{(c+,c−)}W \leftarrow W \cup \{(c^+, c^-)\}
    until 12m∑i=1n(ci++ci−)−1m∑i=1n(ci+−ci−)(wTxi)≤ξ+ϵ\frac{1}{2m} \sum_{i=1}^n (c_i^+ + c_i^-) - \frac{1}{m} \sum_{i=1}^n (c_i^+ - c_i^-) (w^T x_i) \le \xi + \epsilon
    return (w,ξ)(w, \xi)

  6. Knowl 6 — Time Complexity Bound of Ordinal Regression Cutting-Plane Algorithm

    theoretical result

    For any distribution generating feature vectors with bounded L2L_2-norm ∥x∥2≤max⁡i∥xi∥2\|x\|_2 \le \max_i \|x_i\|_2, fixed regularization parameter C>0C > 0, and precision ϵ>0\epsilon > 0:

    1. The condensed cutting-plane algorithm for ordinal regression terminates after adding at most:

    max⁡(2ϵ,8CR2ϵ2)\max\left( \frac{2}{\epsilon}, \frac{8 C R^2}{\epsilon^2} \right)

    constraints to the working set WW, where R=2max⁡i∥xi∥2R = 2 \max_i \|x_i\|_2. The bound is independent of nn and the number of pairs mm.

    1. Each iteration runs in O(sn+nlog⁡n+Rn)O(sn + n \log n + Rn) time for a constant working set size ∣W∣|W|, dominated by computing nn dot products (O(sn)O(sn)), sorting instances by score (O(nlog⁡n)O(n \log n)), and making R−1R-1 linear passes over nn items (O(Rn)O(Rn)).

    2. For any fixed number of ranks RR, fixed C>0C > 0, and fixed ϵ>0\epsilon > 0, the overall time complexity of training a linear ordinal regression SVM (or optimizing ROC-Area) is O(snlog⁡n)O(sn \log n), compared to O(sn3)O(sn^3) typical for conventional decomposition methods on pairwise constraints.

  7. Knowl 7 — Dual Formulation of Structural Classification SVM

    equation

    The Wolfe dual of the structural linear classification SVM optimization problem optimizes non-negative Lagrange multipliers αc≥0\alpha_c \ge 0 for each binary vector c∈{0,1}nc \in \{0, 1\}^n:

    max⁡α≥0∑c∈{0,1}n∥c∥1nαc−12∑c∈{0,1}n∑c′∈{0,1}nαcαc′xcTxc′s.t.∑c∈{0,1}nαc≤C\max_{\alpha \ge 0} \sum_{c \in \{0, 1\}^n} \frac{\|c\|_1}{n} \alpha_c - \frac{1}{2} \sum_{c \in \{0, 1\}^n} \sum_{c' \in \{0, 1\}^n} \alpha_c \alpha_{c'} x_c^T x_{c'} \quad \text{s.t.} \quad \sum_{c \in \{0, 1\}^n} \alpha_c \le C

    where ∥c∥1=∑i=1nci\|c\|_1 = \sum_{i=1}^n c_i is the L1L_1-norm of cc (the count of ones in cc), and xc∈RNx_c \in \mathbb{R}^N is the condensed feature vector defined as:

    xc=1n∑i=1nciyixix_c = \frac{1}{n} \sum_{i=1}^n c_i y_i x_i

    The optimal weight vector is recovered as w=∑cαcxcw = \sum_{c} \alpha_c x_c. In the cutting-plane algorithm, solving this dual restricted to the working set WW depends computationally only on ∣W∣×∣W∣|W| \times |W| matrix operations once the condensed vectors xcx_c are computed.

  8. Knowl 8 — Empirical Training Time Comparison of SVM-Perf and SVM-Light

    data/table
    Classification Ordinal Regression
    Dataset nn NN ss SVM-Perf SVM-Light SVM-Perf SVM-Light
    Reuters CCAT 804,414 47,236 0.16% 149.7 20,075.5 304.1 NA
    Reuters C11 804,414 47,236 0.16% 178.9 5,187.4 499.1 NA
    Arxiv astro-ph 62,369 99,757 0.08% 16.9 80.1 26.1 NA
    Covertype 1 522,911 54 22.22% 171.7 25,514.3 1,109.1 NA
    KDD04 Physics 150,000 78 38.42% 31.9 1,040.2 132.5 NA

    The table compares training time in CPU-seconds on a 3.6 GHz Intel Xeon processor under Linux (2GB RAM) using ϵ=0.001\epsilon = 0.001 and dataset-specific optimal CC (C=10,000C=10,000 for CCAT, C=50,000C=50,000 for C11, C=20,000C=20,000 for astro-ph, C=1,000,000C=1,000,000 for Covertype 1, and C=20,000C=20,000 for KDD04 Physics) on full joined datasets.

    For binary classification, the cutting-plane method (SVM-Perf) delivers speedups of over two orders of magnitude compared to the decomposition method SVM-Light on large tasks (e.g., ~134x faster on Reuters CCAT and ~148x faster on Covertype 1). For ordinal regression (optimizing ROC-Area), SVM-Perf scales to hundreds of thousands of examples in hundreds of seconds, whereas SVM-Light is marked NA because pairwise decomposition is computationally intractable for n>4,000n > 4,000.

  9. Knowl 9 — Empirical Scaling of Cutting-Plane Iterations and Runtime with n, epsilon, and C

    empirical result

    Empirical experiments on large-scale classification and ordinal regression benchmarks demonstrate the following practical scaling properties of SVM-Perf:

    1. Scaling with Sample Size nn: Classification runtime scales empirically as roughly O(n0.8)O(n^{0.8}), exhibiting sub-linear empirical behavior over large ranges of nn. The number of cutting-plane iterations is not only bounded independent of nn but remains constant or decreases slightly as nn grows, amortizing fixed QP solver overhead.

    2. Scaling with Tolerance ϵ\epsilon: The empirical number of iterations scales as roughly O(ϵ−0.3)O(\epsilon^{-0.3}) and CPU time as O(ϵ−0.4)O(\epsilon^{-0.4}), substantially outperforming the theoretical worst-case bound of O(ϵ−2)O(\epsilon^{-2}). A tolerance of ϵ=0.001\epsilon = 0.001 achieves generalization performance (Accuracy and PRBEP) matching exact solvers, yielding a relative objective error between 0.1%0.1\% and 1%1\%. Setting ϵ≤0.01\epsilon \le 0.01 maintains accuracy within 0.5 percentage points of ϵ=0.001\epsilon = 0.001.

    3. Scaling with Regularization CC: The empirical number of iterations scales as O(C)O(\sqrt{C}), outperforming the theoretical linear upper bound O(C)O(C) and leading to sub-linear runtime scaling in CC over practical ranges of CC.

Coverage note — None was omitted; all primary theoretical formulations, equivalence theorems, algorithms, complexity bounds, and empirical findings were extracted.

References

  1. 1.R. Caruana, T. Joachims, and L. Backstrom. Kddcup 2004: Results and analysis. ACM SIGKDD Newsletter, 6(2):95–108, 2004.
  2. 2.C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
  3. 3.R. Collobert and S. Bengio. Svmtorch: Support vector machines for large-scale regression problems. Journal of Machine Learning Research (JMLR), 1:143–160, 2001.
  4. 4.J. Dıez, J. del Coz, and A. Bahamonde. A support vector method for ranking minimizing the number of swapped pairs. Technical report, Artificial Intelligence Centre, Universidad de Oviedo at Gijon, 2006.
  5. 5.S. Dumais, J. Platt, D. Heckerman, and M. Sahami. Inductive learning algorithms and representations for text categorization. In Proceedings of ACM-CIKM98, November 1998.
  6. 6.M. Ferris and T. Munson. Interior-point methods for massive support vector machines. SIAM Journal of Optimization, 13(3):783–804, 2003.
  7. 7.G. Fung and O. Mangasarian. Proximal support vector classifiers. In ACM SIGKDD International Conference On Knowledge Discovery and Data Mining (KDD), 2001.
  8. 8.R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In Advances in Large Margin Classifiers, pages 115–132. MIT Press, Cambridge, MA, 2000.
  9. 9.D. Hush and C. Scovel. Polynomial-time decomposition algorithms for support vector machines. Machine Learning, 51:51–71, 2003.
  10. 10.T. Joachims. Text categorization with support vector machines: Learning with many relevant features. In Proceedings of the European Conference on Machine Learning, pages 137 – 142, Berlin, 1998. Springer.
  11. 11.T. Joachims. Making large-scale SVM learning practical. In B. Schölkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods - Support Vector Learning, chapter 11, pages 169–184. MIT Press, Cambridge, MA, 1999.
  12. 12.T. Joachims. Optimizing search engines using clickthrough data. In Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD), 2002.
  13. 13.T. Joachims. Learning to align sequences: A maximum-margin approach. online manuscript, August 2003.
  14. 14.T. Joachims. A support vector method for multivariate performance measures. In International Conference on Machine Learning (ICML), 2005.
  15. 15.S. Keerthi and D. DeCoste. A modified finite newton method for fast solution of large scale linear svms. Journal of Machine Learning Research (JMLR), 6:341–361, 2005.
  16. 16.J. Kelley. The cutting-plane method for solving convex programs. Journal of the Society for Industrial Applied Mathematics, 8:703–712, 1960.
  17. 17.D. Lewis, Y. Yang, T. Rose, and F. Li. Rcv1: A new benchmark collection for text categorization research. Journal of Machine Learning Research (JMLR), 5:361–397, 2004.
  18. 18.O. Mangasarian and D. Musicant. Lagrangian support vector machines. Journal of Machine Learning Research (JMLR), 1:161–177, 2001.
  19. 19.J. Platt. Fast training of support vector machines using sequential minimal optimization. In B. Schölkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods - Support Vector Learning, chapter 12. MIT-Press, 1999.
  20. 20.A. Rakotomamonjy. Svms and area under roc curve. Technical report, PSI-INSA de Rouen, 2004.
  21. 21.B. Schoelkopf and A. J. Smola. Learning with Kernels. The MIT Press, Cambridge, MA, 2002.
  22. 22.B. Schölkopf, A. J. Smola, R. C. Williamson, and P. L. Bartlett. New support vector algorithms. Neural Computation, 12:1207–1245, 2000.
  23. 23.I. Tsang, J. Kwok, and P.-M. Cheung. Core vector machines: Fast svm training on very large data sets. Journal of Machine Learning Research (JMLR), 6:363–392, 2005.
  24. 24.I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun. Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research (JMLR), 6:1453 – 1484, September 2005.

Citation

MLA
Joachims, T. “Training Linear SVMs in Linear Time”. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006, pp. 217–26, https://doi.org/10.1145/1150402.1150429.
APA
Joachims, T. (2006). Training linear SVMs in linear time. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 217–226. https://doi.org/10.1145/1150402.1150429
Chicago
Joachims, T. 2006. “Training Linear SVMs in Linear Time”. Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 217–26. https://doi.org/10.1145/1150402.1150429.
Harvard
Joachims, T. (2006) “Training linear SVMs in linear time”, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp. 217–226. Available at: https://doi.org/10.1145/1150402.1150429.
Vancouver
1. Joachims T (2006) Training linear SVMs in linear time. In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 217–226

BibTeX

@inproceedings{Joachims_2006, series={KDD06}, title={Training linear SVMs in linear time}, url={http://dx.doi.org/10.1145/1150402.1150429}, DOI={10.1145/1150402.1150429}, booktitle={Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher={ACM}, author={Joachims, Thorsten}, year={2006}, month=Aug, pages={217–226}, collection={KDD06} }
Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF