Rademacher Complexity and Generalization Bounds
Rademacher complexity is a measure of the complexity of a set of functions or vectors.
Why a Set Matters
Rademacher complexity measures the complexity of a collection of functions or vectors. The word collection is important: the object being measured is not one isolated function or one isolated vector, but a set of possible functions or vectors. The definition can be introduced through a function set F and a set S, or stated more generally for a set of vectors A contained in Rm.
From Functions to Vectors
In the function-based view, the definition uses a function set F with respect to a set S. Evaluating members of F on the elements of S gives the function-based data that the definition examines. This connects the function view to the vector view: the evaluations can be regarded as coordinates, while the general definition works directly with a set of vectors A contained in Rm.
Rademacher complexity is a measure of the complexity of a set of functions or vectors. In the function-based definition, the set is described through F with respect to S. In the more general definition, the set is described as A contained in Rm.
Reading the Random Signs
The definition also uses random-sign variables written as σ_i. Each σ_i independently takes one of two values: 1 or -1. The two values are equally likely. Thus, the signs provide a random pattern that is used while examining the functions or vectors in the collection.
The σ variables are not the function set or the vector set. They are the random signs used in the definition. F, S, and σ therefore play different roles: F supplies possible functions, S supplies the set with respect to which the functions are considered, and σ supplies independent random signs.
Following One Sign Pattern
Separating the Definition's Roles
Suppose a definition names a function set F, a set S, and independent random-sign variables σ_i. Identify what each named object contributes to the definition.
- 1Locate F
F is the collection of functions whose complexity is being described. The measured object is therefore a set, not one isolated function.
- 2Locate S
S is the set with respect to which the function-based definition is stated. Function evaluations on S provide the connection to the vector-based view.
- 3Locate σ
The σ_i are independent random-sign variables. Each one is equally likely to be 1 or -1.
- 4Compare with the general form
The same structural idea can be stated more generally for a set of vectors A contained in Rm.
F identifies the collection being measured, S identifies the set used in the function-based view, and σ identifies the random signs used to examine that collection.
The useful mental model is a comparison under a random sign pattern. The collection supplies candidate functions or vectors, the signs assign positive or negative orientation to coordinates or evaluations, and the comparison identifies the strongest signed alignment. This is a structural reading of the definition rather than a numerical calculation.
Complexity and Generalization Bounds
Rademacher complexity is connected to generalization bounds because it supplies a measure of the complexity of the relevant set of functions or vectors. A generalization-bound statement uses that complexity measure when describing a bound on the gap between empirical and expected performance. The key relationship to remember is that complexity is an ingredient in the bound, not a separate function or vector being evaluated.
Common Reading Errors
Common mistake Treating Rademacher complexity as a property of one isolated function.
What it looks likeReading F as though it names only one function.
Why it failsThe measure is defined for a set of functions or vectors.
Do this insteadIdentify the complete collection, such as F or A, before interpreting the random signs.
Common mistake Treating σ_i as members of the function set.
What it looks likeCalling the random signs the functions being measured.
Why it failsThe σ_i are independent random-sign variables used in the definition.
Do this insteadSeparate the measured collection from the random variables used to examine it.
Common mistake Forgetting that the signs have two equally likely values.
What it looks likeAssuming a sign can take an arbitrary value.
Why it failsEach σ_i is equally likely to be 1 or -1.
Do this insteadRead every σ_i as an independent random choice between 1 and -1.
Common mistake Confusing the function-based and vector-based statements.
What it looks likeAssuming F with respect to S and A contained in R^m describe unrelated ideas.
Why it failsThe function-based view connects to vectors through evaluations, while the vector statement gives the more general form.
Do this insteadAsk whether the definition starts with functions and S or directly with a vector set A.
Check Your Understanding
A definition contains F, S, A, and σ_i. Explain which symbols belong to the function-based view, which symbol belongs to the vector-based view, and what values each σ_i can take.
Hints
- F is a collection of functions considered with respect to S.
- A is a set of vectors contained in Rm.
- Each σ_i independently takes one of two equally likely values.
In your own words, explain why the definition begins with a set of functions or vectors rather than one isolated object.
Hints
- Rademacher complexity measures the complexity of a collection.
- The collection may be described by F or by A.
Key Takeaways
- Rademacher complexity measures the complexity of a set of functions or vectors.
- The function-based definition uses a function set F with respect to a set S.
- The more general definition uses a vector set A contained in Rm.
- The variables σ_i are independent random signs, and each is equally likely to be 1 or -1.
- Rademacher complexity serves as a complexity measure used in describing generalization bounds.