A New Perspective on Learning Linear Separators with Large L_qL_p Margins
Maria-Florina Balcan, Christopher G. Berlind · 2014
We give theoretical and empirical results that provide new insights into large margin learn-ing. We prove a bound on the generaliza-tion error of learning linear separators with large LqLp margins (where Lq and Lp are dual norms) for any finite p ≥ 1. The bound leads to a simple data-dependent sufficient condition for fast learning in addition to ex-tending 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 ≥ 2. Our experi-ments confirm that our theoretical results are relevant in practice. 1