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?

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.