# Proof of upper bound on the leave-one-out-cross-validation error of linear SVM

I have to show that for a two-class SVM classifier trained on a linearly separable dataset $$(x_i, y_i)_{i =1}^n$$ the following upper bound on the leave-one-out-cross-validation error holds true:

$$L_1OCV = \frac{1}{n} \sum_{i = 1}^n [y_i \ne f_i(x_i)] \le \frac{|SV|}{n},$$

where for all $$i = 1, \dots, n$$ $$f_i(x_i)$$ is the SVM classifier fitted on the entire data without the observation $$(x_i, y_i)$$ and $$|SV|$$ is the number of support vectors of the SVM classifier fitted on the entire data.

I have no idea about how to start. Has someone an idea?

Hint: Start with the dual SVM objective with $$\ell_2$$ regularization

$$\text{maximize}\quad J(\mathbf{\Lambda}) = \sum_{i=1}^n \lambda_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \lambda_i \lambda_j y_i y_j \mathbf{K}(\mathbf{x}_i, \mathbf{x}_j)$$ $$\text{subject to}\quad \lambda_i \geq 0; \; \forall \; i.$$

Note that we take the hard-margin SVM, because of the linear separability assumption.

Denote the objective for the SVM trained without point $$\mathbf{x}_k$$ as $$J_{(-k)}(\mathbf{\Lambda}_{(-k)})$$, or

$$J_{(-k)}(\mathbf{\Lambda}_{(-k)}) = \sum_{i \neq k}^n \alpha_i - \frac{1}{2} \sum_{i \neq k}^n \sum_{j \neq k}^n \lambda_i \lambda_j y_i y_j \mathbf{K}(\mathbf{x}_i, \mathbf{x}_j).$$

In terms of these variables, an equivalent statement of your theorem is that your leave-one-out cross validation error is bounded by

$$\frac{1}{n} \sum_{k=1}^n \mathbf{1}\left[y_k \sum_{i\neq k}\lambda^k_i y_i \mathbf{K}(\mathbf{x}_i, \mathbf{x}_k) < 0\right]$$

where $$\lambda^k_i$$ is the $$i$$th element of $$\mathbf{\Lambda}^k$$, the result of training without point $$\mathbf{x}_k$$. This is because $$|SV|$$ is the number of nonzero $$\lambda^*_i$$, via complementary slackness.

We can prove this statement by analyzing the effect of "adding back" an arbitrary missing point in leave-one-out CV. To do this, show the following.

a) Let $$\lambda_k^*$$ be the optimal dual variable corresponding to the left-out $$\mathbf{x}_k$$. Show that when $$\mathbf{x}_k$$ is "added back" into the dataset, for fixed $$\lambda^*_k$$, the resulting objective to optimize, i.e. $$\mathbf{J}(\mathbf{\Lambda}_{(-k)})$$, is

$$J_{(-k)}(\mathbf{\Lambda}_{(-k)}) - \lambda^*_k y_k \sum_{i \neq k} \lambda_i y_i \mathbf{K}(\mathbf{x}_i, \mathbf{x}_k).$$

b) Let $$\mathbf{\Lambda}^k_{(-k)}$$ be the unique maximizer of $$J_{(-k)}(\mathbf{\Lambda}_{(-k)})$$, and $$\mathbf{\Lambda}^*_{(-k)}$$ be the unique maximizer of $$J(\mathbf{\Lambda}_{(-k)})$$. Use the statement $$J(\mathbf{\Lambda}^*_{(-k)}) \geq J(\mathbf{\Lambda}_{(-k)})$$ to conclude that

$$y_k \sum_{i\neq k} \lambda_i^k y_i \mathbf{K}(\mathbf{x}_i, \mathbf{x}_k) \geq y_k \sum_{i\neq k} \lambda_i^* y_i \mathbf{K}(\mathbf{x}_i, \mathbf{x}_k)$$

where $$\lambda_i^*, \lambda_i^k$$ are simply specific elements of $$\mathbf{\Lambda}^*_{(-k)}, \mathbf{\Lambda}_{(-k)}$$, respectively.

c) Does your reasoning in part b) still make sense when $$\lambda^*_k = 0$$? Reason about why the bound still holds in that case (or simply justify why $$\lambda^*_k = 0$$ doesn't affect part b), if that's what you find).

Detail to consider: what assumptions do I need to make to ensure these maximizers are unique?

d) [Edit: reworded this part] Use the bound in part b) to show that

$$\frac{1}{n} \sum_{k=1}^n \mathbf{1}\left[y_k \sum_{i\neq k}\lambda^k_i y_i \mathbf{K}(\mathbf{x}_i, \mathbf{x}_k) < 0\right] = \frac{1}{n} \sum_{k=1}^n \mathbf{1}\left[\lambda^*_k < 0\right].$$

Use the fact that support vectors correspond to nonzero $$\lambda_k^*$$ to conclude.

• Thanks @tchainzzz. You wrote that you went through the full prove. Can I ask you where you found it (in which book oder paper), so I can also see the steps in between?
– ghxk
Nov 21, 2021 at 9:41
• I have problems in justifying why that $\lambda_{k}^{*}=0$ does not affect part b and I also do not really see the answer in part d....Could xou give me some hints more?
– ghxk
Nov 21, 2021 at 14:46
• For the $\lambda_k^* = 0$ case, you probably had to divide by $\lambda_k^*$ to reach the statement you need to show for part b). But $\lambda_k^* = 0$ makes the bound trivial because then, repeating the expansion in part b), you'd get something like $0 \geq 0$, so everything still holds. Nov 21, 2021 at 19:45
• For part d), yes, I apologize -- this was the part of the original proof that I had the most trouble justifying to myself. I've tried to argue it here via the perspective of "count the nonzero elements of $\mathbf{\Lambda}^*$." Using the bound in part b), the sign of the LHS represents the leave-one-out model prediction. If this is negative, the model is incorrect -- you were trying to bound this. Nov 21, 2021 at 19:49
• In part a: Shouldnt there be a minus instead of a plus? $J_{(-k)}(\mathbf{\Lambda}_{(-k)}) - \lambda^*_k y_k \sum_{i \neq k} \lambda_i y_i \mathbf{K}(\mathbf{x}_i, \mathbf{x}_k)$
– ghxk
Nov 22, 2021 at 7:52