Rademacher Complexity of Linear Classes

From Linear Predictors to Finite Vectors

The H1 proof reduces a Rademacher-complexity calculation to a finite-set problem. The reduction has three main moves. First, Holder's inequality controls an inner product by pairing a 1-norm with an infinity-norm. Next, the sample vectors are reorganized coordinate by coordinate into vectors in R^m. Finally, the resulting finite set is handled with Massart lemma.

Rademacher Complexity of a Vector Set

The important structure is the order of operations. A sample supplies vectors. Random signs create signed combinations of those vectors. The supremum selects the largest value available from the hypothesis class or vector set. The resulting quantity is the Rademacher complexity, which can be used to bound the generalization error of the class.

Holder's Norm Pairing

Holder's inequality supplies the norm control at the beginning of the proof. For an inner product between two vectors, it pairs the 1-norm of one vector with the infinity-norm of the other. In the form used for the H1 argument, the inner-product expression is bounded by the product of a vector's 1-norm and the other vector's infinity-norm.

|<a, b>| ≤ ||a||1 ||b||∞

This pairing is useful because it turns an inner-product optimization into norm control. The 1-norm measures the total absolute size of the coordinates of one vector, while the infinity-norm supplies the largest absolute coordinate of the other vector. The proof uses this inequality before reorganizing the sample into coordinate vectors.

Coordinate Vectors Across the Sample

Let the sample be S = (x1, ..., xm), where every xi is a vector in R^n. Instead of keeping the sample organized by points, the proof reorganizes it by coordinates. For each coordinate index j in [n], form the vector vj = (x1,j, ..., xm,j) in R^m. Thus, vj collects coordinate j from every sample vector.

The change in viewpoint is the essential step: the original sample vectors live in R^n, but each coordinate vector vj lives in R^m because it contains one selected coordinate from each of the m sample points.

The Signed Finite Set

V = {v1, ..., vn, -v1, ..., -vn}

After forming the coordinate vectors, the proof includes both every coordinate vector and its negative. The resulting set V is finite: it contains the n vectors v1 through vn together with their n negatives. This signed construction lets the finite-set argument account for both signs of each coordinate vector.

The set is indexed in two ways. The coordinate index j identifies which sample coordinate was collected, and the sign identifies whether the vector is vj or -vj. This is the finite object to which Massart lemma is applied.

Norm Control for Massart's Lemma

||vj||2 ≤ √m max over i of ||xi||∞

The source gives a common 2-norm control for every coordinate vector. Its 2-norm is at most √m times the largest infinity-norm among the sample vectors. Because V also contains -vj, the same norm control applies to the negative vectors: changing a vector's sign does not change its 2-norm.

This bound supplies the norm ingredient required by Massart lemma. The other ingredient is the number of vectors in the finite set. Since V contains n coordinate vectors and n negatives, its construction provides those two pieces of information: a finite-set size determined by the coordinates and a maximum 2-norm controlled by the sample's infinity-norms.

Tracing the Complete Reduction

The proof's division of labor is worth remembering. Holder's inequality handles the inner product. Coordinate vectors translate the sample into R^m. The signed set V makes the collection finite and symmetric under negation. Massart lemma then handles the finite-set Rademacher complexity using the set's size and norm control.

Common Proof Mistakes

• Treating vj as one of the original sample vectors.

  The original xi vectors lie in R^n, whereas vj collects one coordinate across all m sample vectors and lies in R^m.

  Fix: Describe vj as a coordinate vector formed by fixing j and reading that coordinate across x1 through xm.

• Leaving out the negative coordinate vectors.

  The finite set used in the H1 proof contains both each coordinate vector and its negative.

  Fix: Construct V with the n coordinate vectors and all n corresponding negatives.

• Using the infinity-norm bound as though it were already a finite-set complexity bound.

  That inequality controls the vector norms, but Massart lemma is still needed to turn finite-set size and norm control into a bound on R(V).

  Fix: Use the norm inequality as one input to Massart lemma and the size of V as the other.

• Assigning Holder's inequality the job of completing the proof.

  Holder's inequality controls the inner product, while the coordinate-vector construction and Massart lemma complete the finite-set argument.

  Fix: Keep the proof stages separate: Holder control, coordinate reorganization, signed-set construction, and Massart application.

Proof-Reading Checklist

Key Takeaways

1. Rademacher complexity measures the complexity of a hypothesis class through signed combinations and a supremum over the class.
2. Holder's inequality bounds an inner product using a 1-norm and an infinity-norm.
3. For a sample in R^n, the proof forms vj = (x1,j, ..., xm,j) in R^m for each coordinate j.
4. The finite set is V = {v1, ..., vn, -v1, ..., -vn}.
5. Massart lemma uses the finite-set size and maximum vector norm to bound R(V), completing the H1 proof.