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 $\ell_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.

本文研究了多分类算法的泛化性能，首次获得一种基于数据的泛化误差界限，并在现有数据相关泛化分析的线性依赖条件基础上，显著提高了类大小的对数依赖性。理论分析促使我们引入了一种基于$\ell_p$-范数正则化的新型多分类分类机器，其中参数$p$控制相应限制的复杂度。我们基于Fenchel对偶理论导出了一种高效的优化算法。对几个真实世界数据集的基准测试表明，所提出的算法可以实现显着的精度提高。

多类支持向量机：从更紧密的数据相关泛化界限到新颖的算法