Timezone: »

 
Poster
Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms
Yunwen Lei · Urun Dogan · Alexander Binder · Marius Kloft

Thu Dec 10 08:00 AM -- 12:00 PM (PST) @ 210 C #77
in Poster Session »

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.

[ PDF] 

Author Information

Yunwen Lei (City University of Hong Kong)
Urun Dogan (Microsoft)
Alexander Binder (Technical University of Berlin and Singapore University of Technology and Design)
Marius Kloft (Humboldt University of Berlin)

More from the Same Authors