# SVM perturbation bounds

Let $$B$$ be the unit ball of $$\mathbb{R}^d$$. Suppose that $$x_1,\ldots,x_n$$ are vectors in $$B$$ with labels $$y_i\in\{-1,1\}$$. We say that $$w\in B$$ separates this labeled set with margin $$\gamma$$ if $$y_i(w\cdot x_i)\ge\gamma$$ for all $$i\in[n]$$.

Let $$\gamma_0>0$$ be the largest possible margin on a given labeled set, achieved by the vector $$w_0\in B$$. Suppose now that $$x_i'$$ is an $$\varepsilon$$-perturbed version of $$x_i$$, namely $$||x_i-x_i'||\le\varepsilon<\gamma_0^2$$. The perturbed data set is still linearly separable (Theorem 13 here https://www.jmlr.org/papers/v10/kontorovich09a.html ). Let $$\gamma_1$$ be the maximum margin achievable on the perturbed dataset, achieved by the vector $$w_1\in B$$.

Question: What is known about $$||w_0-w_1||$$? Can a bound of $$O(\varepsilon)$$ be proven?

• This seems related to the phenomenom of boundary tilting, but I haven't seen any results that answer this question. – D.W. May 5 at 19:00