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

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

CC BY-SA 4.0
2018-10-15T03:24:55.240Z
https://dl.acm.org/citation.cfm?id=656008
Sariel Har-Peled
CC BY-SA 4.0
2018-10-15T08:07:38.860Z
Nice! But you don't actually use the quantity $\frac1m\sum_{i=1}^m R_i/\gamma_i$, right?
Aryeh
CC BY-SA 4.0
2018-10-18T16:15:08.413Z
No. That why it was not an answer. Just a remotely relevant result.
Sariel Har-Peled
<machine-learning><lg.learning><st.statistics><svm>
Average margin bounds for separable SVM
Aryeh
# Average margin bounds for separable SVM

(Asked by: username_0 on 2018-10-14)

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?

**Tags:** machine-learning, lg.learning, st.statistics, svm
> **Comments:**
> **username_1**: https://dl.acm.org/citation.cfm?id=656008  
> **username_0**: Nice! But you don't actually use the quantity $\frac1m\sum_{i=1}^m R_i/\gamma_i$, right?  
> **username_1**: No. That why it was not an answer. Just a remotely relevant result.  

---

## 0 answers

