acceptodds
Withdrawn from ICLR 2027

The Support Vector Machine Tree

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Support vector machines (SVMs) are an established binary classification model which enjoys good generalization performance. However, a long-standing problem is their high training and inference time. We propose a new model, the Support Vector Machine Tree, which applies a divide-and-conquer strategy but where, crucially, both the tree partition and the leaf SVMS are jointly optimized with an RKHS penalty. This brings several important improvements compared to the exact SVM as well as to existing approximate approaches. Computationally, the memory and runtime (at either training or inference) are far smaller, because the heavy SVM cost is confined to each leaf of the tree, which drastically reduces the number of support vectors in an instance-dependent way. The test accuracy is also improved, particularly in larger datasets, where other approaches cannot even run. Finally, the tree structure provides some interpretability.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
machine learning, kernel methods, tree-based methods

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_1sb1OpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper "THE SUPPORT VECTOR MACHINE TREE" merges the SVM concept into the decision tree in two components. The decision function is linear as in the CART approach but with an L1 regularization on the weight and the leaf functions are also SVMs, if separation is needed. Thus, the hope is to have only few features accessed during the tree part and much fewer support vectors active in the leafs during inference and training.

Whereas the general idea is sound and worth exploring, literature analysis, theory, and experiments need much more expansion before this algorithm is ready to be published. Please keep working on it!

Critical strengths
  • The algorithm idea is reasonable and sufficiently well presented.
  • Scaling to 4M examples.
  • Potential savings in inference and training.
  • joint optimization of tree and leaf SVMs.
  • By combining the power of decision trees and SVMs, there is potential to be superior to Random Forest and gradient boosting trees.
Critical weaknesses
  • The state of the art is omitting significant parts like "A hybrid SVM based decision tree", CART, gradient-boosted trees, random forests, and there are probably many more missing.
  • No statistical significance is reported.
  • The references are not appropriate. I would have expected to also see decision trees in the mix. Not even, the algorithm from "Alternating optimization of decision trees" is visible in the comparison. You cannot say, this is not an SVM and then just compare against SVMs.
  • The arguments on speed up need measurement (and not just FLOPS). It also needs to account for additional hyperparameters tuning.
  • The model definition does not truly apply because it gets later on modified with L1 instead of L0 loss.
  • There are several bold and incorrect statements without evidence.

Other issues:

  • "While they are widely praised for their generalization ability," - This requires citation and I am not sure that is still the case.
  • "linear on N at inference time" This is incorrect. It's linear in the number of support vectors.
  • "support vector (SVs), which are a (usually large) subset of the training instances" - This needs evidence and I don't think, it is always true.
  • "we find that, with hyperparameters determined by cross-validation" - This sounds like overfitting of hyper parameters without validation dataset.
  • "existing fast approximate approaches" - It's missing decision trees and random forests
  • https://www.sciencedirect.com/science/article/abs/pii/S0031320310003067 needs to be compared against. "A hybrid SVM based decision tree", M. Arun Kumar, M. Gopal, Pattern Recognition, Volume 43, Issue 12, 2010
  • some other literature on hybrid SVM extensions might be missing like relative margin machines
  • missing comparison to ordinary decision trees, gradient boosting trees, and random forest preferably on Kaggle competitions
  • the paper claims, the SVM is in the nodes and there is a reduced problem but then advertises that tree and leaf nodes are jointly optimized. This is contradictory. Also, if every node is an SVM, you basically solve more and not less SVM problems.
  • The tree is not a normal tree because the node decisions are linear classifications. This feels a bit like a boosting tree. A respective literature analysis on the tree side is missing.
  • "the entire SVM tree model can be written as a sum of a basis function over each training instance" is incorrect AND unproven.
  • Appendix B says, an approximation is used. However, it is not investigated how this interferes with the original objective function.
  • It is not clear to me where equation 3 comes from. Why did the decision tree part get replaced by gj(x)
  • Figure 8 highlights the low number of inference SVs but is ignoring that because of the in-between decisions, there are still more support vectors that define the decision boundaries.
  • The initialization procedure is not clear and it is not clear, how a local minimum is avoided.
  • train-test-validation procedure is completely undocumented.
  • I am missing time measurements for training and testing to confirm the efficiency claims.
Questions for authors
  • How was the splitting into training, testing, and validation data?
  • How do the results of reference algorithms compare to the results in the reference literature?
  • How would the algorithm work for regression or multi-class?
  • What were the criteria for selecting the benchmark datasets?
  • What are the respective leading values on Kaggle?
  • How do you avoid local minima with the iterative approach?
  • What are "random median splits"?
Reviewer_RVpDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SVMTree, a hybrid classifier than combines logistic regression nodes which hyperplanes separate the data and SVM leaves which classify the data only from their individual node. The classifier is greedily trained by alternating node and leaf freeze/train (a practical 'joint' optimization). The optimization objective combines hinge loss, an L1 penalty on the decision nodes, and RKHS regularization on the leaf classifiers. Because the leaf SVM classifiers receive potentially exponentially less data than a global SVM, the approach avoids the pitfalls of SVM for datasets with large number of examples. The approach is evaluated on nine classic datasets (covertype, poker-hand, etc.) and shows linear training time and generally better accuracy and fewer support vectors.

Critical strengths
  • Novel combination of existing techniques by joint optimization.
  • Exponential reduction in training and inference time without loss of accuracy compared to full SVM
  • Thorough evaluation on 9 datasets of varying sizes (up to 4M)
  • Well designed and mathematically grounded alternating optimization algorithm
  • Figures are useful. Figure 2 is a great illustration of the concept. The learning curves in Figures 5–6 and the hyperparameter analysis in Figure 10 help explain the interaction between tree depth, classification accuracy, and support-vector complexity.
Critical weaknesses
  • lack of comparison to Random Forests and gradient-boosted decision trees. This is fairly critical as the proposed method is not just a SVM, it is a new nonlinear classification architecture, so it should be compared to SOTA methods for structured-data classifiers.
  • to understand the effect of the joint optimization (a central aspect of the paper) it would be better to have an ablation with fixed random median tree and independently optimized leaf SVMs.
  • weak statistical results: since the method uses random intiialization, it is necessary to report stats over multiple runs, a single run can have strong bias.
  • running different experiments on different types of machines is ok to compare accuracy, but not ok when comparing runtime.
  • hSVM is not Cited explicitly, it is likely Chen et. al. 2017, but it needs to be made explicit.
Questions for authors

see weaknesses

Reviewer_S8QJOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes combining a decision tree with kernel SVM classifiers to make classification faster on large datasets. More specifically, an oblique decision tree with splits using combinations of input features, routes each example to one leaf. That leaf contains a smaller SVM trained only on the examples assigned to it which reduces the number of kernel evaluations needed for prediction. The main contribution is jointly learning the routing tree and the leaf SVMs. Training alternates between 1) fitting each leaf SVM using the examples currently reaching it, and 2) updating each split to route examples toward the subtree that gives lower prediction loss. The objective combines hinge loss, a sparsity penalty on the routing weights, and RKHS regularization of the leaf classifiers. The authors report lower classification errors and reduced computational costs compared with standard SVMs, kernel approximations, and selected scalable SVM methods. They also show that updating the routing improves performance over the initial random partition.

Critical strengths

The paper’s main strength is to make kernel SVMs more efficient while preserving and potentially improving accuracy. More specifically, the proposed technique:

  1. learns the partition rather than fixing it beforehand.
  2. use conditional computing
  3. has empirical results on large scale datasets
Critical weaknesses

The main 2 weakness I see:

  1. The efficiency claim made by the authors is not well supported. While Table 2 compares the tree’s support-vector counts with “equivalent support vectors” for RFF and Nyström, these methods normally predict using explicit feature maps and linear weights. As such the reported counts do not reflect their actual prediction cost. In addition, the FLOP comparison calculation is not clearly explained.
  2. There is an inconsistency in the objective nad the appendix which cast doubts on what did the implementation follow. More specifically, Equation (1) penalizes the entire leaf function, while Appendix C introduces an unregularized intercept. The pure-leaf result in Theorem 3.1 relies on the latter formulation.
Questions for authors
  1. Does the claimed inference advantage hold when RFF and Nyström use explicit feature maps followed by linear prediction, and how do the reported FLOPs and “equivalent support vector” counts reflect these implementations?
  2. How is the leaf intercept treated in the implemented objective, and how does this relate to Equation (1) and the formulation in Appendix C?
  3. How is scale invariance handled in the routing regularizer, given that scaling a split’s weights and intercept preserves routing while reducing its l1 penalty?
  4. Can the reported inference advantage be confirmed through prediction latency on the same hardware, using efficient baseline implementations and configurations with comparable test error?
Reviewer_d1QYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes the SVM Tree: an oblique binary decision tree where each leaf applies a kernel SVM instead of a constant label. The predictive function is still a basis-function (support vector) expansion like a global SVM, but the coefficients are instance-dependent and sparse. Each leaf's SVM only uses support vectors from its own reduced training subset, and a test point only follows one root-to-leaf path.

Critical strengths

(1) The paper solve a real bottleneck of SVM: the computational complexity.

(2) Convincing scalability story: SVM Tree trains where CascadeSVM/DC-SVM time out or OOM, and the complexity analysis matches what's observed empirically (linear scaling in N for fixed depth).

(3) Original contribution: the paper explicitly notes the model is neither an exact nor approximate SVM but a different model class, and that it's orthogonal to exact-SVM-approximation techniques.

Critical weaknesses

(1) Missing head-to-head baseline comparison. The paper's central novelty claim — joint optimization beats disjoint heuristic partition-then-fit — is only tested indirectly (via TAO-iteration ablations starting from a random partition). It's never compared against the actual family of heuristic local-SVM methods it discusses in related work (DTSVM, CSVM, BCSVM, L-SVM, FL-SVMs, LGSVM). The chosen baselines (CascadeSVM, DC-SVM, hSVM, RFF, Nyström) are mostly global-SVM-approximation methods.

(2) All experiments use a complete binary tree of fixed depth; the paper admits in §1 that real trees are unbalanced and some leaves get pruned, but the empirical section doesn't show how performance degrades under that more realistic imbalance, only under the idealized complete-tree sweep.

(3) Binary classification only — no discussion of whether/how this extends to multi-class, which limits the scope of the "SVM Tree is a new model class" contribution.

Questions for authors

(1) Why no comparison against the local-SVM-with-fixed-partition baselines (DTSVM/L-SVM/CSVM/LGSVM) you discuss in related work?

(2) All results are on binary classification with one tree structure (complete binary tree of depth Δ). Any sense of how unbalanced/pruned trees perform relative to the idealized complete-tree analysis in §4?

(3) Depth Δ and hyperparameters (λ, μ) are chosen by cross-validation per dataset: how expensive is that search relative to the reported training-time wins? If CV cost isn't amortized, the "fast" claim needs a caveat.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.