{
  "id": "1506.04359",
  "version": "v1",
  "published": "2015-06-14T08:07:23.000Z",
  "updated": "2015-06-14T08:07:23.000Z",
  "title": "Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms",
  "authors": [
    "Yunwen Lei",
    "Ürün Dogan",
    "Alexander Binder",
    "Marius Kloft"
  ],
  "categories": [
    "cs.LG"
  ],
  "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 $\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-06-14T08:07:23.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "tighter data-dependent generalization bounds",
      "multi-class svms",
      "novel algorithms",
      "achieve significant accuracy gains",
      "data-dependent generalization error bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150604359L"
    }
  }
}