Lp-norm Sauer–Shelah lemma for margin multi-category classifiers

作者：

Highlights：

• An Lp-norm Sauer–Shelah lemma for margin multi-category classifiers is proved.

• It is dimension-free (independent of the sample size) for every finite value of p.

• The corresponding guaranteed risks depend sublinearly on the number of categories.

摘要

•An Lp-norm Sauer–Shelah lemma for margin multi-category classifiers is proved.•It is dimension-free (independent of the sample size) for every finite value of p.•The corresponding guaranteed risks depend sublinearly on the number of categories.

论文关键词：Margin multi-category classifiers,Guaranteed risks,ϵ-Entropy,γ-Dimension,Generalized Sauer–Shelah lemmas

论文评审过程：Received 24 September 2016, Revised 22 April 2017, Accepted 6 June 2017, Available online 19 June 2017, Version of Record 7 August 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.06.003