From Margin to Sparsity. Graepel, T., Herbrich, R., & Williamson, R. C In *Advances in Neural Information Processing Systems 13*, pages 210--216, Denver, 2000. The MIT Press. Paper abstract bibtex We present an improvement of Novikoff's perceptron convergence theorem. Reinterpreting this mistake bound as a margin dependent sparsity guarantee allows us to give a PAC-style generalisation error bound for the classifier learned by the dual perceptron learning algorithm. The bound value crucially depends on the margin a support vector machine would achieve on the same data set using the same kernel. Ironically, the bound yields better guarantees than are currently available for the support vector solution itself.

@inproceedings{DBLP:conf/nips/GraepelHW00,
abstract = {We present an improvement of Novikoff's perceptron convergence theorem. Reinterpreting this mistake bound as a margin dependent sparsity guarantee allows us to give a PAC-style generalisation error bound for the classifier learned by the dual perceptron learning algorithm. The bound value crucially depends on the margin a support vector machine would achieve on the same data set using the same kernel. Ironically, the bound yields better guarantees than are currently available for the support vector solution itself.},
address = {Denver},
author = {Graepel, Thore and Herbrich, Ralf and Williamson, Robert C},
booktitle = {Advances in Neural Information Processing Systems 13},
file = {:Users/rherb/Dropbox/Documents/tex/nips2000/sparsity/perc.pdf:pdf},
pages = {210--216},
publisher = {The MIT Press},
title = {{From Margin to Sparsity}},
url = {http://www.herbrich.me/papers/perc.pdf},
year = {2000}
}

Downloads: 0

{"_id":{"_str":"51ff9fa2d40bcbb041000348"},"__v":11,"authorIDs":["5456e9a38b01c8193000005e","54576c282abc8e9f370003ae"],"author_short":["Graepel, T.","Herbrich, R.","Williamson, R. C"],"bibbaseid":"graepel-herbrich-williamson-frommargintosparsity-2000","bibdata":{"bibtype":"inproceedings","type":"inproceedings","abstract":"We present an improvement of Novikoff's perceptron convergence theorem. Reinterpreting this mistake bound as a margin dependent sparsity guarantee allows us to give a PAC-style generalisation error bound for the classifier learned by the dual perceptron learning algorithm. The bound value crucially depends on the margin a support vector machine would achieve on the same data set using the same kernel. Ironically, the bound yields better guarantees than are currently available for the support vector solution itself.","address":"Denver","author":[{"propositions":[],"lastnames":["Graepel"],"firstnames":["Thore"],"suffixes":[]},{"propositions":[],"lastnames":["Herbrich"],"firstnames":["Ralf"],"suffixes":[]},{"propositions":[],"lastnames":["Williamson"],"firstnames":["Robert","C"],"suffixes":[]}],"booktitle":"Advances in Neural Information Processing Systems 13","file":":Users/rherb/Dropbox/Documents/tex/nips2000/sparsity/perc.pdf:pdf","pages":"210--216","publisher":"The MIT Press","title":"From Margin to Sparsity","url":"http://www.herbrich.me/papers/perc.pdf","year":"2000","bibtex":"@inproceedings{DBLP:conf/nips/GraepelHW00,\nabstract = {We present an improvement of Novikoff's perceptron convergence theorem. Reinterpreting this mistake bound as a margin dependent sparsity guarantee allows us to give a PAC-style generalisation error bound for the classifier learned by the dual perceptron learning algorithm. The bound value crucially depends on the margin a support vector machine would achieve on the same data set using the same kernel. Ironically, the bound yields better guarantees than are currently available for the support vector solution itself.},\naddress = {Denver},\nauthor = {Graepel, Thore and Herbrich, Ralf and Williamson, Robert C},\nbooktitle = {Advances in Neural Information Processing Systems 13},\nfile = {:Users/rherb/Dropbox/Documents/tex/nips2000/sparsity/perc.pdf:pdf},\npages = {210--216},\npublisher = {The MIT Press},\ntitle = {{From Margin to Sparsity}},\nurl = {http://www.herbrich.me/papers/perc.pdf},\nyear = {2000}\n}\n","author_short":["Graepel, T.","Herbrich, R.","Williamson, R. C"],"key":"DBLP:conf/nips/GraepelHW00","id":"DBLP:conf/nips/GraepelHW00","bibbaseid":"graepel-herbrich-williamson-frommargintosparsity-2000","role":"author","urls":{"Paper":"http://www.herbrich.me/papers/perc.pdf"},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://herbrich.me/bib/herbrich.bib","downloads":0,"keywords":[],"search_terms":["margin","sparsity","graepel","herbrich","williamson"],"title":"From Margin to Sparsity","title_words":["margin","sparsity"],"year":2000,"dataSources":["y2DvMgAcqeDpXQ6ds"]}