Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms

Yunwen Lei, Ürün Dogan, Alexander Binder, Marius Kloft

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

36 Citations (Scopus)


This paper studies the generalization performance of multi-class classification algorithms, for which we obtain-for the first time-A data-dependent generalization error bound with a logarithmic dependence on the class size, substantially improving the state-of-the-art linear dependence in the existing data-dependent generalization analysis. The theoretical analysis motivates us to introduce a new multi-class classification machine based on lp-norm regularization, where the parameter p controls the complexity of the corresponding bounds. We derive an efficient optimization algorithm based on Fenchel duality theory. Benchmarks on several real-world datasets show that the proposed algorithm can achieve significant accuracy gains over the state of the art.

Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 28
EditorsC. Cortes, N. Lawrence, D. Lee, M. Sugiyama, R. Garnett
Number of pages9
ISBN (Electronic)9781510825024
Publication statusPublished - Dec 2015
Event29th Annual Conference on Neural Information Processing Systems, NIPS 2015 - Montreal, Canada
Duration: 7 Dec 201512 Dec 2015


Conference29th Annual Conference on Neural Information Processing Systems, NIPS 2015
Internet address

Scopus Subject Areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Cite this