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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.