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

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

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

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

Department of Mathematics

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

38 Citations (Scopus)

Abstract

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 l_p-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 language	English
Title of host publication	Advances in Neural Information Processing Systems 28
Editors	C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, R. Garnett
Pages	2035-2043
Number of pages	9
Volume	28
ISBN (Electronic)	9781510825024
Publication status	Published - Dec 2015
Event	29th Annual Conference on Neural Information Processing Systems, NIPS 2015 - Montreal, Canada Duration: 7 Dec 2015 → 12 Dec 2015 https://neurips.cc/Conferences/2015 https://proceedings.neurips.cc/paper/2015

Conference

Conference	29th Annual Conference on Neural Information Processing Systems, NIPS 2015
Country/Territory	Canada
City	Montreal
Period	7/12/15 → 12/12/15
Internet address	https://neurips.cc/Conferences/2015 https://proceedings.neurips.cc/paper/2015

Scopus Subject Areas

Computer Networks and Communications
Information Systems
Signal Processing

Access to Document

https://proceedings.neurips.cc/paper/2015/file/3a029f04d76d32e79367c4b3255dda4d-Paper.pdf

Cite this

Lei, Y., Dogan, Ü., Binder, A., & Kloft, M. (2015). Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, & R. Garnett (Eds.), Advances in Neural Information Processing Systems 28 (Vol. 28, pp. 2035-2043) https://proceedings.neurips.cc/paper/2015/file/3a029f04d76d32e79367c4b3255dda4d-Paper.pdf

@inproceedings{d744714a52f34cfcb06ce0783e145dc9,

title = "Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms",

abstract = "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.",

author = "Yunwen Lei and {\"U}r{\"u}n Dogan and Alexander Binder and Marius Kloft",

note = "Publisher copyright: {\textcopyright} (2015) by Neural Information Processing Systems; 29th Annual Conference on Neural Information Processing Systems, NIPS 2015 ; Conference date: 07-12-2015 Through 12-12-2015",

year = "2015",

month = dec,

language = "English",

volume = "28",

pages = "2035--2043",

editor = "C. Cortes and N. Lawrence and D. Lee and M. Sugiyama and R. Garnett",

booktitle = "Advances in Neural Information Processing Systems 28",

url = "https://neurips.cc/Conferences/2015, https://proceedings.neurips.cc/paper/2015",

}

Lei, Y, Dogan, Ü, Binder, A & Kloft, M 2015, Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms. in C Cortes, N Lawrence, D Lee, M Sugiyama & R Garnett (eds), Advances in Neural Information Processing Systems 28. vol. 28, pp. 2035-2043, 29th Annual Conference on Neural Information Processing Systems, NIPS 2015, Montreal, Canada, 7/12/15. <https://proceedings.neurips.cc/paper/2015/file/3a029f04d76d32e79367c4b3255dda4d-Paper.pdf>

Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms. / Lei, Yunwen; Dogan, Ürün; Binder, Alexander et al.
Advances in Neural Information Processing Systems 28. ed. / C. Cortes; N. Lawrence; D. Lee; M. Sugiyama; R. Garnett. Vol. 28 2015. p. 2035-2043.

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Multi-class SVMs

T2 - 29th Annual Conference on Neural Information Processing Systems, NIPS 2015

AU - Lei, Yunwen

AU - Dogan, Ürün

AU - Binder, Alexander

AU - Kloft, Marius

PY - 2015/12

Y1 - 2015/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84965178544&partnerID=8YFLogxK

M3 - Conference proceeding

AN - SCOPUS:84965178544

VL - 28

SP - 2035

EP - 2043

BT - Advances in Neural Information Processing Systems 28

A2 - Cortes, C.

A2 - Lawrence, N.

A2 - Lee, D.

A2 - Sugiyama, M.

A2 - Garnett, R.

Y2 - 7 December 2015 through 12 December 2015

ER -

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

Abstract

Conference

Scopus Subject Areas

Access to Document

Other files and links

Cite this