Generalization Bounds for Linear Predictors

From Training Separation to Generalization

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 central question is whether this vector does more than fit the observed sample: does its performance extend to new examples drawn from the same distribution? The proof of Theorem 26.13 answers this through a generalization bound.

The notation w_S emphasizes that the vector depends on the training sample S. It is not merely an arbitrary vector from the hypothesis class. It is the particular hard-SVM output selected by Equation (26.19). Under the theorem's assumptions, this output separates the training data with the required margin and has zero empirical loss.

The Assumptions Before the Bound

The generalization result is conditional. The distributional assumption guarantees a vector w⋆ satisfying y〈w⋆, x〉 ≥ 1 with probability 1. The input vectors also satisfy ||x||_2 ≤ R with probability 1. These conditions describe a margin-separable setting with bounded inputs.

• There is a vector w⋆ satisfying y〈w⋆, x〉 ≥ 1 with probability 1.
• The input vectors satisfy ||x||_2 ≤ R with probability 1.
• The hard-SVM output is considered under the required margin-separation setting.
• The proof places w_S in the bounded class H determined by B = ||w⋆||_2.
• The hard-SVM output has zero empirical loss under these assumptions.

Why Ramp Loss Enters the Proof

The target statement concerns zero-one loss, but the proof begins by fixing the ramp loss. This choice supplies the properties required for the theorem application: ramp loss is 1-Lipschitz, takes values in the interval [0, 1], and upper bounds zero-one loss.

The proof therefore uses ramp loss as a bridge. First, Theorem 26.12 can be applied to a loss with the required boundedness and Lipschitz properties. Then, because ramp loss upper bounds zero-one loss, the resulting control supports the zero-one-loss generalization statement in Theorem 26.13.

The Proof Trace

The proof of Theorem 26.13 follows a fixed sequence. It does not invoke Theorem 26.12 immediately after naming w_S. Instead, it first verifies that the theorem's loss and class requirements are available for this particular output.

1. Fix the ramp loss.
2. Introduce the bounded class H using B = ||w⋆||_2.
3. Use the distributional assumptions and the definition of hard-SVM to establish that w_S belongs to H with probability 1.
4. Use the hard-SVM definition and the margin-separation assumption to establish L_S(w_S) = 0.
5. Invoke Theorem 26.12 for w_S in the class H.
6. Obtain the high-probability generalization statement asserted by Theorem 26.13, with ramp loss providing the connection to zero-one loss.

Why Zero Empirical Loss Matters

The equality L_S(w_S) = 0 says that the empirical loss of the hard-SVM output on the training sample is zero under the theorem's assumptions. This is the bridge between the training result and the generalization theorem: when Theorem 26.12 is specialized to w_S, the empirical-loss contribution has value zero rather than contributing an additional positive term.

Mistakes in Reading the Proof

• Treating w_S as an arbitrary vector rather than the hard-SVM output.

  w_S is specifically the vector determined by the hard-SVM definition, and the proof uses that definition to establish its relevant properties.

  Fix: Track w_S as the sample-dependent hard-SVM output defined by Equation (26.19).

• Applying Theorem 26.12 before checking class membership.

  The proof first places w_S in the bounded class H using B = ||w⋆||_2.

  Fix: Explicitly establish that w_S belongs to H with probability 1 before invoking Theorem 26.12.

• Assuming that zero empirical loss alone proves the generalization result.

  The theorem application also depends on the bounded class and the properties of ramp loss.

  Fix: Treat L_S(w_S) = 0 as one input to the theorem application, not as the entire argument.

• Confusing ramp loss with the final target loss.

  Ramp loss is an intermediate loss chosen because it is 1-Lipschitz, bounded in [0, 1], and upper bounds zero-one loss.

  Fix: Describe ramp loss as the theorem-friendly bridge to the zero-one loss guarantee.

Practice the Proof Trace

1. w_S is the hard-SVM vector defined by Equation (26.19), learned from the training sample.
2. The theorem applies in a margin-separable setting with a vector w⋆ satisfying y〈w⋆, x〉 ≥ 1 with probability 1 and bounded inputs satisfying ||x||_2 ≤ R with probability 1.
3. Ramp loss is selected because it is 1-Lipschitz, takes values in [0, 1], and upper bounds zero-one loss.
4. The proof places w_S in the bounded class H using B = ||w⋆||_2.
5. The equality L_S(w_S) = 0 removes the empirical-loss contribution when Theorem 26.12 is applied, leading to the high-probability statement of Theorem 26.13.