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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.