Regularization

Convexity of a learning problem has two requirements.

Programming

Two Tests for Convexity

A learning problem is convex only when two requirements hold together. First, the hypothesis class must be a convex set. Second, for every example in the example set, the loss function must be convex as a function of the hypothesis. If either requirement fails, the learning problem is not convex under this definition.

How do the convex hypothesis class and the per-example convex loss function jointly determine whether a learning problem is convex?

Think of convexity as a two-part checklist. The hypothesis class must pass one test, and the loss must pass another test separately for every example.

Hypothesis Class Geometry

In this setting, hypotheses are real-valued vectors in a subset of R^d. The hypothesis class is the collection of hypotheses being considered. Calling this class convex means that combining hypotheses in the relevant convex way stays within the class. The important point is not merely that individual hypotheses are vectors; the entire allowed collection must satisfy the convex-set requirement.

What does it mean for a hypothesis class to be convex, and how does combining two hypotheses stay within the class?

For a convexity check, ask: if the learning problem combines two allowed hypotheses in the required convex manner, does the result remain an allowed hypothesis? If the class does not have this property, the first requirement fails, regardless of what happens with the loss.

Loss Across Every Example

The second requirement concerns the loss function viewed as a function of the hypothesis. That function must be convex for every example in the example set. It is not enough for the loss to have the required shape for only some examples or merely in an overall average. The definition imposes the condition example by example.

How does the loss vary across hypotheses for an individual training example, and why must that shape be convex for every example rather than only on average?

What do you think happens?

A learning problem has a convex hypothesis class. The loss is convex for most examples but not for one example. Is the learning problem convex under this definition?

Yes, because most examples satisfy the condition
Yes, if the average loss is convex
No, because the loss must be convex for every example

Reveal answer

Answer: No, because the loss must be convex for every example.

Both requirements must hold together, and the loss requirement applies separately to every example.

Regularized Loss Minimization

A learning rule can evaluate a hypothesis using empirical risk. Regularized Loss Minimization, or RLM, adds a regularization function to that evaluation. RLM jointly considers empirical risk and the regularization function, then outputs a hypothesis.

How are empirical risk and the regularization penalty combined to produce the objective minimized by the learning rule?

RLM is not a rule that minimizes empirical risk alone and not a rule that minimizes the regularization function alone. It jointly minimizes both parts and produces a hypothesis.

Weight-Vector Calculation

To calculate the ℓ2 norm, square each component of the vector, add the squared components, and take the square root. If Tikhonov regularization is then applied, multiply the resulting norm by the positive value of λ.

Evaluating Tikhonov Regularization

Let w = (1, 2, 2) and λ = 3. Calculate ‖w‖₂ and then calculate R(w) = λ ‖w‖₂.

Square the components: The components produce 1², 2², and 2².

Add the squares: 1² + 2² + 2² = 1 + 4 + 4 = 9.

Take the square root: ‖w‖₂ = √9 = 3.

Apply λ: R(w) = λ ‖w‖₂ = 3 × 3 = 9.

‖w‖₂ = 3 and R(w) = 9.

‖w‖₂ = √(1² + 2² + 2²) = 3;  R(w) = 3 × 3 = 9

How are the individual weights transformed and combined to calculate the length of a weight vector?

Common Reasoning Errors

Checking only the hypothesis class
Convexity also requires the loss function to be convex in the hypothesis for every example.
Fix: Check both requirements and reject convexity if either one fails.
Checking the loss only on average
The definition requires convexity of the loss for every individual example.
Fix: Inspect the loss condition example by example.
Treating RLM as empirical-risk minimization alone
RLM jointly considers empirical risk and a regularization function.
Fix: Describe RLM as a two-part evaluation that produces a hypothesis.
Using λ as part of the norm calculation
The ℓ2 norm is calculated from the components of w, while λ is applied afterward as a positive scaling factor.
Fix: First calculate ‖w‖₂, then calculate R(w) = λ ‖w‖₂.

Practice Checklist

MEDIUM

Classify a learning problem using the two convexity requirements. Then, for w = (2, 1, 2) and λ = 2, calculate ‖w‖₂ and R(w) = λ ‖w‖₂.

Hints

Ask separately whether the hypothesis class is convex and whether the loss is convex for every example.
For the norm, square the components, add them, and take the square root.
Apply the positive λ only after calculating the norm.

Your attempt (not saved)

Use this sequence when solving a problem: check the convexity of the hypothesis class; check the loss for every example; if both pass, the learning problem is convex under this definition; for RLM, combine empirical risk with a regularization function; for Tikhonov regularization, calculate the ℓ2 norm first and multiply it by positive λ.

Key Takeaways

A convex learning problem requires both a convex hypothesis class and a loss function that is convex in the hypothesis for every example.
Hypotheses in this setting are real-valued vectors in a subset of R^d, and the whole hypothesis class must satisfy the convex-set requirement.
Regularized Loss Minimization jointly considers empirical risk and a regularization function, then outputs a hypothesis.
Tikhonov regularization uses R(w) = λ ‖w‖₂ with positive λ.
The ℓ2 norm is found by squaring components, summing them, and taking the square root.