A New Perspective on Learning Linear Separators with Large L_qL_p Margins

Maria-Florina Balcan, Christopher Berlind
Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:68-76, 2014.

Abstract

We give theoretical and empirical results that provide new insights into large margin learning. We prove a bound on the generalization error of learning linear separators with large L_qL_p margins (where L_q and L_p are dual norms) for any finite p \ge 1. The bound leads to a simple data-dependent sufficient condition for fast learning in addition to extending and improving upon previous results. We also provide the first study that shows the benefits of taking advantage of margins with p < 2 over margins with p \ge 2. Our experiments confirm that our theoretical results are relevant in practice.

Cite this Paper

BibTeX
@InProceedings{pmlr-v33-balcan14, title = {{A New Perspective on Learning Linear Separators with Large $L_qL_p$ Margins}}, author = {Balcan, Maria-Florina and Berlind, Christopher}, booktitle = {Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics}, pages = {68--76}, year = {2014}, editor = {Kaski, Samuel and Corander, Jukka}, volume = {33}, series = {Proceedings of Machine Learning Research}, address = {Reykjavik, Iceland}, month = {22--25 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v33/balcan14.pdf}, url = {https://proceedings.mlr.press/v33/balcan14.html}, abstract = {We give theoretical and empirical results that provide new insights into large margin learning. We prove a bound on the generalization error of learning linear separators with large L_qL_p margins (where L_q and L_p are dual norms) for any finite p \ge 1. The bound leads to a simple data-dependent sufficient condition for fast learning in addition to extending and improving upon previous results. We also provide the first study that shows the benefits of taking advantage of margins with p < 2 over margins with p \ge 2. Our experiments confirm that our theoretical results are relevant in practice.} }
Endnote
%0 Conference Paper %T A New Perspective on Learning Linear Separators with Large L_qL_p Margins %A Maria-Florina Balcan %A Christopher Berlind %B Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2014 %E Samuel Kaski %E Jukka Corander %F pmlr-v33-balcan14 %I PMLR %P 68--76 %U https://proceedings.mlr.press/v33/balcan14.html %V 33 %X We give theoretical and empirical results that provide new insights into large margin learning. We prove a bound on the generalization error of learning linear separators with large L_qL_p margins (where L_q and L_p are dual norms) for any finite p \ge 1. The bound leads to a simple data-dependent sufficient condition for fast learning in addition to extending and improving upon previous results. We also provide the first study that shows the benefits of taking advantage of margins with p < 2 over margins with p \ge 2. Our experiments confirm that our theoretical results are relevant in practice.
RIS
TY - CPAPER TI - A New Perspective on Learning Linear Separators with Large L_qL_p Margins AU - Maria-Florina Balcan AU - Christopher Berlind BT - Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics DA - 2014/04/02 ED - Samuel Kaski ED - Jukka Corander ID - pmlr-v33-balcan14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 33 SP - 68 EP - 76 L1 - http://proceedings.mlr.press/v33/balcan14.pdf UR - https://proceedings.mlr.press/v33/balcan14.html AB - We give theoretical and empirical results that provide new insights into large margin learning. We prove a bound on the generalization error of learning linear separators with large L_qL_p margins (where L_q and L_p are dual norms) for any finite p \ge 1. The bound leads to a simple data-dependent sufficient condition for fast learning in addition to extending and improving upon previous results. We also provide the first study that shows the benefits of taking advantage of margins with p < 2 over margins with p \ge 2. Our experiments confirm that our theoretical results are relevant in practice. ER -
APA
Balcan, M. & Berlind, C.. (2014). A New Perspective on Learning Linear Separators with Large L_qL_p Margins. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 33:68-76 Available from https://proceedings.mlr.press/v33/balcan14.html.

Related Material