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. May 5 at 19:00

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.