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.


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.

Related Material