Support Vector Machines and Margin-Based Learning

Hard-SVM is designed for a setting in which the training data can be separated with the required margin condition. Its output is a vector called w_S, determined by Equation (26.19). The proof of the generalization result asks more than whether this vector fits the observed sample. It shows how the hard-SVM output can be placed inside a bounded class and then uses Theorem 26.12 to obtain a high-probability statement about performance beyond the sample.

The symbol w_S denotes the vector produced by the hard-SVM optimization problem for the sample S. In the source, this output is defined by Equation (26.19). It is therefore not an arbitrary vector selected after the proof; it is the particular vector returned by the hard-SVM procedure when applied to the sample.

Under the theorem's assumptions, the hard-SVM output satisfies L_S(w_S) = 0. The required separating margin means that the output has zero empirical loss on the sample in the setting considered by the theorem. This fact will later simplify the empirical-loss part of the generalization argument.

The desired conclusion concerns zero-one loss, but the proof begins by fixing the ramp loss. The ramp loss is useful because it has three properties required by the argument: it is 1-Lipschitz, it takes values in the interval from 0 to 1, and it upper bounds zero-one loss. These properties let the proof apply a result about a bounded, well-behaved loss while still controlling the zero-one loss of interest.

The hard-SVM generalization result is conditional. The distributional assumption guarantees that there is a vector w⋆ satisfying y〈w⋆, x〉 ≥ 1 with probability 1. The input vectors also satisfy ||x||_2 ≤ R with probability 1. Together with the hard-SVM definition, these conditions allow the proof to place the output w_S in a bounded class H determined by B = ||w⋆||_2.

The proof of Theorem 26.13 uses Theorem 26.12 only after its prerequisites have been assembled. First, the proof fixes the ramp loss. Next, it introduces the bounded class H using B = ||w⋆||_2. The distributional assumptions and the hard-SVM definition then show that w_S belongs to H with probability 1. At the same time, the hard-SVM margin condition gives L_S(w_S) = 0. With these facts available, the proof applies Theorem 26.12 and obtains the high-probability generalization statement asserted by Theorem 26.13.

The statement L_S(w_S) = 0 matters because it simplifies the empirical-loss contribution in the bound supplied by Theorem 26.12. Once the proof knows that the hard-SVM output has zero empirical loss, that contribution is replaced by zero rather than remaining an unknown quantity. The remaining argument still depends on the ramp-loss properties, the bounded class, and the distributional assumptions.