{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T02:42:26Z","timestamp":1770432146408,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,2,13]],"date-time":"2008-02-13T00:00:00Z","timestamp":1202860800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,5]]},"DOI":"10.1007\/s00224-007-9094-6","type":"journal-article","created":{"date-parts":[[2008,2,12]],"date-time":"2008-02-12T19:20:08Z","timestamp":1202844008000},"page":"568-595","source":"Crossref","is-referenced-by-count":16,"title":["Provably Fast Training Algorithms for Support Vector Machines"],"prefix":"10.1007","volume":"42","author":[{"given":"Jos\u00e9 L.","family":"Balc\u00e1zar","sequence":"first","affiliation":[]},{"given":"Yang","family":"Dai","sequence":"additional","affiliation":[]},{"given":"Junichi","family":"Tanaka","sequence":"additional","affiliation":[]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,2,13]]},"reference":[{"key":"9094_CR1","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF01582137","volume":"61","author":"I. Adler","year":"1993","unstructured":"Adler, I., Shamir, R.: A randomized scheme for speeding up algorithms for linear and convex programming with high constraints-to-variable ratio. Math. Program. 61, 39\u201352 (1993)","journal-title":"Math. Program."},{"key":"9094_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/3-540-45583-3_11","volume-title":"Proceedings of 12th International Conference on Algorithmic Learning Theory (ALT\u201901)","author":"J.L. Balc\u00e1zar","year":"2001","unstructured":"Balc\u00e1zar, J.L., Dai, Y., Watanabe, O.: A Random sampling technique for training support vector machines: for a primal-form maximal-margin classifiers. In: Proceedings of 12th International Conference on Algorithmic Learning Theory (ALT\u201901). Lecture Notes in Computer Science, vol. 2225, pp. 119\u2013134. Springer, London (2001)"},{"key":"9094_CR3","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/ICDM.2001.989499","volume-title":"Proceedings of First IEEE International Conference on Data Mining (ICDM\u201901)","author":"J.L. Balc\u00e1zar","year":"2001","unstructured":"Balc\u00e1zar, J.L., Dai, Y., Watanabe, O.: Provably fast training algorithms for support vector machines. In: Proceedings of First IEEE International Conference on Data Mining (ICDM\u201901), pp. 43\u201350. IEEE, Los Alamitos (2001)"},{"key":"9094_CR4","first-page":"19","volume-title":"Proceedings of SIAM Workshop in Discrete Mathematics and Data Mining","author":"J.L. Balc\u00e1zar","year":"2002","unstructured":"Balc\u00e1zar, J.L., Dai, Y., Watanabe, O.: Provably fast support vector regression using random sampling. In: Proceedings of SIAM Workshop in Discrete Mathematics and Data Mining, pp. 19\u201329. SIAM, Philadelphia (2002)"},{"key":"9094_CR5","first-page":"57","volume-title":"Proceedings of 17th International Conference on Machine Learning (ICML\u20192000)","author":"K.P. Bennett","year":"2000","unstructured":"Bennett, K.P., Bredensteiner, E.J.: Duality and geometry in SVM classifiers. In: Proceedings of 17th International Conference on Machine Learning (ICML\u20192000), pp. 57\u201364. Morgan Kaufmann, San Mateo (2000)"},{"key":"9094_CR6","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/380995.380999","volume":"2","author":"K.P. Bennett","year":"2000","unstructured":"Bennett, K.P., Campbell, C.: Support Vector Machines: Hype or Hallelujah? SIGKDD Explorations 2, 2 (2000)","journal-title":"SIGKDD Explorations"},{"key":"9094_CR7","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1080\/10556789208805504","volume":"1","author":"K.P. Bennett","year":"1992","unstructured":"Bennett, K.P., Mangasarian, O.L.: Robust linear programming discrimination of two linearly inseparable sets. Optim. Methods Softw. 1, 23\u201334 (1992)","journal-title":"Optim. Methods Softw."},{"key":"9094_CR8","volume-title":"Nonlinear Programming","author":"D.P. Bertsekas","year":"1995","unstructured":"Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1995)"},{"key":"9094_CR9","first-page":"539","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS\u201902)","author":"J. Bi","year":"2002","unstructured":"Bi, J., Bennett, K.P.: Duality, geometry, and support vector regression. In: Proceedings of Advances in Neural Information Processing Systems (NIPS\u201902), pp. 539\u2013600. MIT Press, Cambridge (2002)"},{"key":"9094_CR10","first-page":"144","volume-title":"Proceedings of 5th Annual Conference on Computational Learning Theory (COLT\u201992)","author":"B.E. Boser","year":"1992","unstructured":"Boser, B.E., Guyon, I.M., Vapnik, V.N.: A training algorithm for optimal margin classifiers. In: Proceedings of 5th Annual Conference on Computational Learning Theory (COLT\u201992), pp. 144\u2013152. ACM, New York (1992)"},{"key":"9094_CR11","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/978-1-4615-0005-6_12","volume-title":"Handbook of Massive Datasets","author":"P.S. Bradley","year":"2002","unstructured":"Bradley, P.S., Mangasarian, O.L., Musicant, D.R.: Optimization methods in massive datasets. In: Abello, J., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Massive Datasets, pp. 439\u2013471. Kluwer Academic, Dordrecht (2002)"},{"key":"9094_CR12","first-page":"409","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS\u201900)","author":"G. Cauwenberghs","year":"2000","unstructured":"Cauwenberghs, G., Poggio, T.: Incremental and decremental support vector machine learning. In: Proceedings of Advances in Neural Information Processing Systems (NIPS\u201900), pp. 409\u2013415. MIT Press, Cambridge (2000)"},{"key":"9094_CR13","first-page":"452","volume-title":"Proceedings of 29th IEEE Symposium on Foundations of Computer Science (FOCS\u201988)","author":"K.L. Clarkson","year":"1988","unstructured":"Clarkson, K.L.: A Las Vegas algorithm for linear programming when the dimension is small. In: Proceedings of 29th IEEE Symposium on Foundations of Computer Science (FOCS\u201988), pp. 452\u2013456. IEEE, Los Alamitos (1988). (See [15] for a better version.)"},{"key":"9094_CR14","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"K.L. Clarkson","year":"1995","unstructured":"Clarkson, K.L.: Las Vegas algorithms for linear and integer programming. J. ACM 42, 488\u2013499 (1995)","journal-title":"J. ACM"},{"key":"9094_CR15","first-page":"273","volume":"20","author":"C. Cortes","year":"1995","unstructured":"Cortes, C., Vapnik, V.: Support-vector networks. Mach. Learn. 20, 273\u2013297 (1995)","journal-title":"Mach. Learn."},{"key":"9094_CR16","volume-title":"An Introduction to Support Vector Machines","author":"N. Cristianini","year":"2000","unstructured":"Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines. Cambridge University Press, Cambridge (2000)"},{"issue":"1","key":"9094_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-01-00923-5","volume":"39","author":"F. Cucker","year":"2001","unstructured":"Cucker, F., Smale, S.: On the mathematical foundations of learning. Bull. Am. Math. Soc. 39(1), 1\u201349 (2001)","journal-title":"Bull. Am. Math. Soc."},{"key":"9094_CR18","doi-asserted-by":"crossref","unstructured":"Evgeniou, T., Pontil, M., Poggio, T.: A unified framework for regularization networks and support vector machines. AI Memo No.\u00a01654, AI Lab MIT (1999)","DOI":"10.7551\/mitpress\/1113.003.0014"},{"key":"9094_CR19","first-page":"243","volume":"2","author":"S. Fine","year":"2001","unstructured":"Fine, S., Scheinberg, K.: Efficient SVM training using low-rank kernel representations. J. Mach. Learn. Res. 2, 243\u2013264 (2001)","journal-title":"J. Mach. Learn. Res."},{"issue":"4","key":"9094_CR20","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/s00454-001-0006-2","volume":"25","author":"B. G\u00e4rtner","year":"2001","unstructured":"G\u00e4rtner, B., Welzl, E.: A simple sampling lemma: Analysis and applications in geometric optimization. Discrete Comput. Geom. 25(4), 569\u2013590 (2001)","journal-title":"Discrete Comput. Geom."},{"key":"9094_CR21","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1023\/A:1021877911972","volume":"51","author":"D. Hush","year":"2003","unstructured":"Hush, D., Scovel, C.: Polynomial-time decomposition algorithms for support vector machines. Mach. Learn. 51, 51\u201371 (2003)","journal-title":"Mach. Learn."},{"issue":"1\u20133","key":"9094_CR22","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1023\/A:1012431217818","volume":"46","author":"S.S. Keerthi","year":"2002","unstructured":"Keerthi, S.S., Gilbert, E.G.: Convergence of a generalized SMO algorithm for SVM classifier design. Mach. Learn. 46(1\u20133), 351\u2013360 (2002)","journal-title":"Mach. Learn."},{"key":"9094_CR23","volume-title":"CD Proceedings of the SIAM International Conference on Data Mining","author":"Y. Lee","year":"2001","unstructured":"Lee, Y., Mangasarian, O.L.: RSVM: Reduced Support Vector Machines. In: CD Proceedings of the SIAM International Conference on Data Mining, Chicago, 5\u20137 April 2001. SIAM, Philadelphia (2001). (Available from http:\/\/www.cs.wisc.edu\/\u00a0olvi\/olvi.html.)"},{"key":"9094_CR24","unstructured":"Lin, C.J.: Linear convergence of a decomposition method for support vector machines. Technical Report. http:\/\/www.csie.ntu.edu.tw\/~cjlin\/papers\/linearconv.pdf (2001)"},{"key":"9094_CR25","first-page":"1267","volume":"14","author":"C.J. Lin","year":"2002","unstructured":"Lin, C.J.: On the convergence of the decomposition method for support vector machines. IEEE Trans. Neural Networks 14, 1267\u20131281 (2002)","journal-title":"IEEE Trans. Neural Networks"},{"key":"9094_CR26","doi-asserted-by":"crossref","unstructured":"Mart\u00edn, M.: On-line support vector machine regression. In: Proceedings of 13th European Conference on Machine Learning (ECML\u201902), pp. 282\u2013294 (2002).","DOI":"10.1007\/3-540-36755-1_24"},{"key":"9094_CR27","unstructured":"Osuna, E., Freund, R., Girosi, F.: An improved training algorithm for support vector machines. In: Proceedings of IEEE Workshop on Neural Networks for Signal Processing, pp. 276\u2013285 (1997)"},{"key":"9094_CR28","unstructured":"Pavlov, D., Mao, J., Dom, B.: Scaling up support vector machines using boosting algorithm. In: Proceedings of International Conference Pattern Rec., pp. 2219\u20132222 (2000)"},{"key":"9094_CR29","first-page":"185","volume-title":"Advances in Kernel Methods\u2014Support Vector Learning","author":"J. Platt","year":"1999","unstructured":"Platt, J.: Fast training of support vector machines using sequential minimal optimization. In: Sch\u00f6lkopf, B., Burges, C.J.C., Smola, A.J. (eds.) Advances in Kernel Methods\u2014Support Vector Learning, pp. 185\u2013208. MIT Press, Cambridge (1999)"},{"key":"9094_CR30","unstructured":"Sch\u00f6lkopf, B., Burges, C., Vapnik, V.: Extracting support data for a given task. In: Proceedings of First International Conference on Knowledge Discovery and Data Mining (KDD\u201995), pp. 252\u2013257 (1995)"},{"key":"9094_CR31","first-page":"330","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS\u201999)","author":"B. Sch\u00f6lkopf","year":"1999","unstructured":"Sch\u00f6lkopf, B., Smola, A., Williamson, R.C.: A new support vector regression algorithm. In: Proceedings of Advances in Neural Information Processing Systems (NIPS\u201999), pp. 330\u2013336. MIT Press, Cambridge (1999)"},{"key":"9094_CR32","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1162\/089976600300015565","volume":"12","author":"B. Sch\u00f6lkopf","year":"2000","unstructured":"Sch\u00f6lkopf, B., Smola, A., Williamson, R.C., Bartlett, P.L.: New support vector algorithms. Neural Comput. 12, 1207\u20131245 (2000)","journal-title":"Neural Comput."},{"key":"9094_CR33","unstructured":"Smola, A.J., Sch\u00f6lkopf, B.: A tutorial on support vector regression. NeuroCOLT Technical Report NC-TR-98-030, Royal Holloway College, University of London (1998)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9094-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9094-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9094-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T09:06:17Z","timestamp":1708592777000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9094-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2,13]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["9094"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9094-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2,13]]}}}