Leave-One-Out Error

Definition

For a sample $S_{n+1}=Z_1,\dots ,Z_{n+1}$ let $S^{-k}$ be the sample without $Z_k$. The leave-one-out error averages the error of the algorithm trained on $S^{-k}$ on the left-out point $Z_k$.

Formula

$$E\left(\text{test error after training on }n\text{ points}\right)=E(\frac{1}{n+1}\sum _{k=1}^{n+1}1\{\text{the algorithm trained on }{S}^{-k}\text{ errs on }{Z}_k\})$$

The reason: the data is i.i.d., so training on $S_n$ and testing on $Z_{n+1}$ has the same distribution as training on $S^{-k}$ and testing on $Z_k$. The generalization bound of the perceptron uses it: points that never trigger an update can be left out without changing the output. The idea “how much does the output change if one point is removed or replaced” is stability (Lecture 4).

Appears in

• Lecture 2, proof of Theorem 2
• Lecture 2, the principle and stability

Related concepts

• Perceptron
• Algorithmic Stability