# Average margin bounds for separable SVM

Suppose we're training a linear separator in the realizable PAC setting. Given $$m$$ labeled examples $$(x_i,y_i)$$ in $$\mathbb R^d\times\{-1,1\}$$, a (consistent) linear separator is a vector $$w\in\mathbb R^d$$ with $$||w||=1$$, such that $$y_i(w\cdot x_i)=:\gamma_i>0$$ for all $$1\le i\le m$$. Putting $$R_i=||x_i||$$, we can define the margin of the $$i$$th example as $$R_i/\gamma_i$$ and the sample margin as $$\min_{1\le i\le m} R_i/\gamma_i.$$ This quantity is known to control the generalization error, see e.g. here https://www.cs.bgu.ac.il/~karyeh/opt-svm.pdf for the precise statements.

Question: are there any generalization bounds for the above setting in terms of the average margin, $$\frac1m\sum_{i=1}^m R_i/\gamma_i$$ --- as opposed to the worst-case one, as above?

• dl.acm.org/citation.cfm?id=656008 – Sariel Har-Peled Oct 15 '18 at 3:24
• Nice! But you don't actually use the quantity $\frac1m\sum_{i=1}^m R_i/\gamma_i$, right? – Aryeh Oct 15 '18 at 8:07
• No. That why it was not an answer. Just a remotely relevant result. – Sariel Har-Peled Oct 18 '18 at 16:15