Sparse Models
The ℓ1 constraint restricts the hypothesis class through ‖w‖1 ≤ B and is associated with sparse models.
The Restriction Begins
A sparse model is not obtained by considering every possible weight vector. The ℓ1 setting begins with candidate vectors w in R^d and retains only those satisfying ‖w‖1 ≤ B. This retained collection is the hypothesis class H. Any generalization statement is therefore about predictors from this restricted class, not about every possible weight vector.
The ℓ1 constraint is the restriction ‖w‖1 ≤ B. It limits the ℓ1 size of the predictor's weight vector and defines the hypothesis class used in the corresponding result.
Why the Constraint Is Called Sparse
The ℓ1 constraint is associated with sparse models. In this context, sparse means that a model can be represented with weight concentrated on a relatively small number of features, with many coefficients equal to zero. The important idea is not merely that the total weight size is limited. The shape of the restriction can favor weight vectors with many zero coefficients.
Reading the ℓ1 Restriction
Suppose the candidate predictors are all vectors w in Rd, but the learning problem retains only vectors satisfying ‖w‖1 ≤ B. What does the learner's search space become?
- 1Start with candidates
Begin with all candidate weight vectors in Rd.
- 2Apply the restriction
Discard every vector that does not satisfy the ℓ1 limit ‖w‖1 ≤ B.
- 3Interpret the retained class
The remaining vectors form the hypothesis class H. This class is associated with sparse models because the constraint can favor vectors with many zero coefficients.
The generalization statement concerns predictors selected from the restricted class H, rather than from every possible weight vector.
Matching Predictors to Instances
The ℓ1 and ℓ2 settings differ in two linked ways. In the ℓ1 result, the predictor is restricted through an ℓ1 bound on w, while the instances satisfy an ℓ∞ bound, ‖x‖∞ ≤ R, with probability 1 under the distribution being considered. In the ℓ2 result, the corresponding restrictions concern an ℓ2 measure of w and a low ℓ2-norm assumption on x.
| Question | ℓ1 setting | ℓ2 setting |
|---|---|---|
| How is the predictor restricted? | ‖w‖1 ≤ B | An ℓ2 restriction on w |
| What is assumed about instances? | ‖x‖∞ ≤ R with probability 1 | A low ℓ2-norm assumption on x |
| What does the corresponding result include? | An additional log(d) factor | The source distinguishes it from the ℓ1 result through the different norm setting |
The same letters B and R appear in both results, but they do not have the same meanings.
This matching process is the main decision rule. Prior knowledge about good predictors determines which weight norm is appropriate. Prior knowledge about the instance set determines which instance norm is appropriate. The question is not whether ℓ1 is universally better than ℓ2; it is which pair of assumptions fits what is already known.
Reading B, R, and log(d)
In the ℓ1 result, B controls the allowed ℓ1 size of w. R controls the ℓ∞ size of each instance x. These parameters describe different sides of the learning problem: B describes the predictor class, while R describes the scale of the inputs.
The corresponding theorem also carries an additional log(d) factor. Here d is the dimension of the weight and instance vectors. The factor records a dimension-dependent part of the ℓ1 generalization result. It should be interpreted only after the predictor norm and instance norm have been matched correctly.
Conditions Behind the Bound
The theorem considers a distribution D over X × Y in which the instances satisfy ‖x‖∞ ≤ R with probability 1. It uses the class H of vectors w in R^d satisfying ‖w‖1 ≤ B. The loss must have the specified form, be ρ-Lipschitz in its first argument for every y, and remain bounded by c over the relevant interval from −BR to BR. Under these assumptions, an independent and identically distributed sample of size m receives a high-probability generalization bound.
Common mistake Treating the ℓ1 constraint as an assumption about the input instances.
What it looks likeReading ‖w‖1 ≤ B as though it meant that x has a small ℓ1 or ℓ∞ norm.
Why it failsThe constraint is on the predictor weights. In the ℓ1 result, the instance assumption is ‖x‖∞ ≤ R.
Do this insteadTrack the two sides separately: B restricts w, while R bounds x.
Common mistake Assuming that B and R have the same interpretation in the ℓ1 and ℓ2 results.
What it looks likeComparing the symbols without checking which norms they accompany.
Why it failsThe source uses the same letters for different norm settings.
Do this insteadRead each parameter together with its norm: ℓ1 for w and ℓ∞ for x in the ℓ1 result; ℓ2 restrictions in the ℓ2 result.
Common mistake Ignoring the dimension-dependent log(d) factor.
What it looks likeDescribing the ℓ1 result without mentioning its additional log(d) term.
Why it failsThe ℓ1 comparison includes this additional factor.
Do this insteadRecord the dimension term after identifying the predictor and instance norms.
Common mistake Choosing ℓ1 or ℓ2 without using prior knowledge.
What it looks likeDeclaring one constraint universally better.
Why it failsThe useful choice depends on what is known about good predictors and the instance set.
Do this insteadMatch predictor knowledge to the weight norm and instance knowledge to the instance norm.
Choosing a Constraint Setting
A Matching Decision
You know that useful predictors are expected to be sparse, and that the instance set is naturally described by an ℓ∞ bound. Which constraint setting should you investigate first?
- 1Use predictor knowledge
The expectation of sparse good predictors points toward the ℓ1 weight restriction, which is associated with sparse models.
- 2Use instance knowledge
The ℓ∞ description of the instance set matches the ℓ1 result's assumption ‖x‖∞ ≤ R.
- 3Check the result's extra term
Interpret the resulting generalization statement while accounting for its additional log(d) factor.
The ℓ1 constraint setting is the natural match for these stated assumptions. The choice follows from matching both the predictor structure and the instance norm, not from treating ℓ1 as universally superior.
A second problem has prior knowledge suggesting that useful predictors fit an ℓ2 restriction and that the instance set is naturally described by a low ℓ2 norm. Which setting should you compare first, and what two pieces of evidence support your choice?
Hints
- Match the expected structure of w to the predictor norm.
- Match the known geometry of x to the instance norm.
- 1Choose the ℓ2 setting first: both the expected predictor structure and the instance assumption match the ℓ2 result. The general rule is to match prior knowledge about w to the weight norm and prior knowledge about x to the instance norm.
Key Takeaways
- The ℓ1 constraint ‖w‖1 ≤ B filters candidate vectors in R^d and defines a restricted hypothesis class H.
- The ℓ1 restriction is associated with sparse models and can favor weight vectors with many zero coefficients.
- In the ℓ1 result, B controls the predictor's ℓ1 size, while R controls the instance's ℓ∞ size.
- The ℓ1 generalization result includes an additional log(d) factor.
- Choose between ℓ1 and ℓ2 by matching both the expected structure of good predictors and the known norm behavior of the instance set.
At a glance
- An ℓ1 norm bound restricts the hypothesis class to vectors w satisfying ‖w‖1 ≤ B.
- This restriction is associated with sparse models and can favor weight vectors with many zero coefficients.
- The ℓ1 theorem pairs an ℓ1 predictor restriction with an ℓ∞ instance bound ‖x‖∞ ≤ R.
- The ℓ1 result contains an additional log(d) factor, so dimension must be considered after the norms are matched.
- The right constraint setting depends on prior knowledge about both good predictors and the instance set.