Holder's Inequality
The H1 proof reduces a Rademacher-complexity calculation to a finite-set problem.
The Proof's Destination
The H1 proof turns a hypothesis-class calculation into a finite-set calculation. Its three tools have separate jobs: Holder's inequality controls an inner product, coordinate vectors convert the sample into vectors in R^m, and Massart lemma controls the Rademacher complexity of the resulting finite set.
The central reduction is from a Rademacher-complexity expression for H1 to the finite set V = {v1, ..., vn, -v1, ..., -vn}.
Rademacher Complexity of a Vector Set
For a finite set V of vectors in R^m, its Rademacher complexity is written as R(V) = (1/m) Eσ[max over v in V of the sum from i = 1 to m of σ_i v_i]. Here, the σ_i are random signs, the maximum selects the vector that gives the largest signed sum, and the factor 1/m normalizes the result by the sample size.
This definition has three moving parts. The random signs produce the Rademacher averaging. The maximum measures how well the best vector in V aligns with those signs. The normalization by m turns the signed sum into an average-scale quantity. In the H1 proof, the goal is not to analyze an arbitrary infinite collection directly; it is to rewrite the relevant expression using a finite V so that Massart lemma applies.
Holder's Norm Connection
|<u, v>| ≤ ||u||1 ||v||∞Holder's inequality bounds the absolute value of an inner product by multiplying the 1-norm of one vector by the infinity-norm of the other. In the H1 proof, this is the step that replaces an inner-product expression with quantities that can be controlled using norms.
Bounding an inner product
Suppose u and v are vectors. How can the inner product <u, v> be controlled using ||u||1 and ||v||∞?
Take the absolute value: Work with |<u, v>| so that the quantity being bounded is nonnegative.
Apply Holder's inequality: Replace the inner product by the product of the 1-norm of u and the infinity-norm of v.
Read the roles of the norms: The 1-norm measures the first vector in the bound, while the infinity-norm measures the largest-coordinate scale of the second vector.
|<u, v>| ≤ ||u||1 ||v||∞
Coordinate Vectors from the Sample
Begin with a sample S = (x1, ..., xm), where each xi is a vector in R^n. Instead of treating every sample vector as one indivisible object, inspect one coordinate position at a time. For each j from 1 to n, form vj = (x1,j, ..., xm,j) in R^m. The vector vj collects coordinate j across all m sample vectors.
Reading a coordinate vector
Given sample vectors x1, ..., xm in R^n, identify the vector associated with coordinate j.
Choose a coordinate: Fix one coordinate index j between 1 and n.
Read that coordinate through the sample: Take the j-th coordinate from x1, then x2, and continue through xm.
Collect the entries: Place those m values into vj = (x1,j, ..., xm,j), which is a vector in R^m.
Each coordinate position in R^n becomes one vector in R^m.
The Finite Set V
V = {v1, ..., vn, -v1, ..., -vn}The proof includes both every coordinate vector and its negative. The coordinate vectors represent the n coordinate positions of the original sample. Their negatives provide the corresponding opposite signed directions. Thus, the original sample is converted into a finite collection in R^m with the vectors needed for the maximum in the Rademacher expression.
Norm Control and Massart
||vj||2 ≤ √m max over i of ||xi||∞The source gives the same 2-norm control for every coordinate vector vj. Since V also contains the negatives, and negating a vector does not change its 2-norm, the same bound controls the vectors used by Massart lemma. The size of the finite collection is |V| = 2n when the listed vectors are counted as the n coordinate vectors and their n negatives.
R(V) ≤ (1/m) √(2 log |V|) max over v in V of ||v||2
A Symbolic Proof Trace
Following the H1 reduction
Trace the proof from a sample S = (x1, ..., xm) with xi in R^n to a finite-set Rademacher-complexity bound.
Start with the sample: The sample contains m vectors, and each sample vector has n coordinates.
Apply Holder's inequality: The inner-product part of the H1 expression is bounded by a product involving a 1-norm and an infinity-norm.
Transpose the viewpoint: For each coordinate j, collect the j-th coordinate from all m sample vectors to form vj in R^m.
Add both signs: Form V = {v1, ..., vn, -v1, ..., -vn}. This is the finite collection used in the Rademacher calculation.
Control the vector norms: Use ||vj||2 ≤ √m max over i of ||xi||∞, with the same control for -vj.
Invoke Massart lemma: Use the finite-set size and the largest 2-norm to bound R(V). The source identifies the relevant right-hand side of the preceding equation as mR(V), and applying Massart lemma completes the proof.
The H1 proof is reduced to a finite-set Rademacher-complexity problem controlled by the number and 2-norms of the vectors in V.
What do you think happens?
Before applying Massart lemma, which two properties of V must be supplied?
Reveal answer
Answer: Its number of vectors and the largest 2-norm among its vectors
The finite-set form of Massart lemma uses log |V| and max over v in V of ||v||2. In this proof, those quantities are controlled using |V| = 2n and the coordinate-vector norm bound.
Common Proof Mistakes
Treating vj as one of the original sample vectors.
The source defines vj by collecting coordinate j across all m sample vectors, so vj is in R^m rather than being one of the xi in R^n.
Fix:
Write vj = (x1,j, ..., xm,j) and identify j as the coordinate index.Leaving out the negative coordinate vectors.
The finite set in the H1 proof is defined to contain both the coordinate vectors and their negatives.
Fix:
Use V = {v1, ..., vn, -v1, ..., -vn}.Using the wrong norms in Holder's inequality.
The stated Holder connection for this proof is between the 1-norm of one vector and the infinity-norm of the other.
Fix:
Use |<u, v>| ≤ ||u||1 ||v||∞.Applying Massart lemma before identifying the finite set.
Massart lemma is applied to a finite collection, so the proof must identify both the collection and its norm control.
Fix:
Construct V first, then supply its size and the maximum 2-norm.
Practice the Reduction
Suppose a sample has m vectors in R^n. Describe the finite set used in the H1 proof, state the dimension of each member of that set, and identify the two quantities needed when applying Massart lemma.
Hints
- First define one coordinate vector vj by reading coordinate j across the sample.
- Remember to include both each vj and its negative.
- Massart lemma needs the size of the finite set and a bound on the largest 2-norm.
- A complete answer should identify V = {v1, ..., vn, -v1, ..., -vn}, state that its vectors lie in R^m, give |V| = 2n, and use the bound ||vj||2 ≤ √m max over i of ||xi||∞ when invoking Massart lemma.
Proof Takeaways
- Holder's inequality converts an inner product into 1-norm and infinity-norm control. The sample is reorganized coordinate by coordinate into vectors vj in R^m. The finite set V contains those coordinate vectors and their negatives. The coordinate vectors satisfy a 2-norm bound based on √m and the largest infinity-norm of the sample vectors. Massart lemma then uses the size of V and its largest 2-norm to bound R(V), completing the finite-set step of the H1 proof.
Key Takeaways
- Holder's inequality gives |<u, v>| ≤ ||u||1 ||v||∞.
- For each coordinate j, the proof forms vj = (x1,j, ..., xm,j) in R^m.
- The finite collection is V = {v1, ..., vn, -v1, ..., -vn}.
- The vectors satisfy ||vj||2 ≤ √m max over i of ||xi||∞.
- Massart lemma combines the size and norm control of V to bound its Rademacher complexity.