SVM optimization: inverse dependence on training set size

ABSTRACT

We discuss how the runtime of SVM optimization should decrease as the size of the training data increases. We present theoretical and empirical results demonstrating how a simple subgradient descent approach indeed displays such behavior, at least for linear kernels.

REFERENCES

• 1: Peter L. Bartlett , Shahar Mendelson, Rademacher and gaussian complexities: risk bounds and structural results, The Journal of Machine Learning Research, 3, 3/1/2003
• 2: Bottou, L. (Web Page). Stochastic gradient descent examples. http://leon.bottou.org/projects/sgd.
• 3: Bottou, L., & Bousquet, O. (2008). The tradeoffs of large scale learning. Advances in Neural Information Processing Systems 20.
• 4: Bottou, L., & LeCun, Y. (2004). Large scale online learning. Advances in Neural Information Processing Systems 16.
• 5: Bottou, L., & Lin, C.-J. (2007). Support vector machine solvers. In L. Bottou, O. Chapelle, D. DeCoste and J. Weston (Eds.), Large scale kernel machines. MIT Press.
• 6: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 7: Thorsten Joachims, Training linear SVMs in linear time, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150429]
• 8: Lin, C.-J. (2002). A formal analysis of stopping criteria of decomposition methods for support vector machines. IEEE Transactions on Neural Networks, 13, 1045--1052.
• 9: John C. Platt, Fast training of support vector machines using sequential minimal optimization, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 10: Shai Shalev-Shwartz , Yoram Singer , Nathan Srebro, Pegasos: Primal Estimated sub-GrAdient SOlver for SVM, Proceedings of the 24th international conference on Machine learning, p.807-814, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273598]
• 11: Smola, A., Vishwanathan, S., & Le, Q. (2008). Bundle methods for machine learning. Advances in Neural Information Processing Systems 20.
• 12: Sridharan, K. (2008). Fast convergence rates for excess regularized risk with application to SVM. http://ttic.uchicago.edu/~karthik/con.pdf.
• 13: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Gradient methods

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory