Rademacher Complexity of Linear Classes

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.

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 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.

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.

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.

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.

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.

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.