Zero-One Loss and Surrogate Losses

The hard-SVM proof begins with a classifier produced from a training sample. That output is a vector called w_S, where the subscript indicates that it is determined by the sample S through Equation (26.19). The proof must then connect two facts: how well w_S performs on the observed sample and how well it is expected to perform on new examples from the same distribution.

It is useful to keep two roles separate. First, w_S is the vector selected by hard-SVM from S. Second, w_S is the classifier whose loss is analyzed. The theorem is not merely stating that an optimization procedure returns a vector; it establishes a generalization statement for the classifier represented by that vector, under specific assumptions about the data distribution.

The hard-SVM generalization result applies in a separable setting with a required margin condition. The distributional assumption guarantees that there is a vector w⋆ such that y〈w⋆, x〉 ≥ 1 with probability 1. The input vectors also satisfy ||x||_2 ≤ R with probability 1. These are distribution-level assumptions: they are required almost surely for examples drawn from the distribution.

The target of the argument involves zero-one loss, but the proof begins by fixing the ramp loss. The ramp loss is useful because it has three properties needed by the generalization argument: it is 1-Lipschitz, it takes values in the interval [0, 1], and it upper bounds zero-one loss.

The important direction is the upper-bound relationship. If ramp loss is at least as large as zero-one loss on the relevant examples, then controlling ramp loss also controls zero-one loss. The ramp loss therefore acts as a surrogate: it is the loss used in the proof, while its upper-bound property lets the conclusion address zero-one loss.

After fixing the ramp loss, the proof introduces the bounded class H using B = ||w⋆||_2. Under the distributional assumptions and the definition of hard-SVM, the output w_S belongs to H with probability 1. The same argument establishes that its empirical loss is zero: L_S(w_S) = 0.

The equality L_S(w_S) = 0 is not an isolated observation. It is the empirical-loss input to the generalization argument. The proof has placed w_S inside the bounded class H and has established that the observed-sample loss is zero. Theorem 26.12 can then be invoked with these facts, producing the generalization statement used for Theorem 26.13.

The proof of Theorem 26.13 can be read as a sequence of preparations followed by one theorem invocation. First, fix the ramp loss. Next, use B = ||w⋆||_2 to define the bounded class H. The distributional assumptions and the hard-SVM definition then give two facts about w_S: it belongs to H with probability 1, and L_S(w_S) = 0. Finally, invoke Theorem 26.12. According to the source, Theorem 26.12 connects these facts to the high-probability generalization statement asserted by Theorem 26.13.