Convex Learning Problems and Regularization

From Prediction Rule to Parameters

A learning problem can be described in two connected ways. The function-based view asks what prediction rule a hypothesis uses. The parameter-based view asks which parameter vector represents that hypothesis. Linear regression becomes especially useful for convex learning because each hypothesis can be represented by a vector w, and the learning problem can then be examined with respect to that vector.

In the function-based description, a hypothesis is a rule that maps an input x to a prediction. In the parameter-based description, the same hypothesis is identified by its parameter vector w. The source expresses the prediction used in the loss as the inner product <w,x>. Different parameter vectors represent different members of the hypothesis class.

The Convexity Check

A learning problem is convex when two ingredients have the required structure. First, the hypothesis class must be a convex set. Second, the loss must be convex with respect to the parameter that describes a hypothesis. For this linear-regression example, the hypothesis class is H = R^d, and the source identifies this set as convex.

H = R^d

The second check concerns the loss. The squared loss is written as (<w,x> - y)^2. It first forms the prediction <w,x>, subtracts the real-valued outcome y, and squares the difference. The source identifies this expression as convex with respect to w. Because the hypothesis class is convex and the loss is convex in the parameter describing the hypothesis, linear regression with squared loss is a convex learning problem.

Following One Training Example

(prediction - target)^2

Regularization in Scope

The supplied material establishes the convex-learning formulation for linear regression with squared loss. It does not specify a regularization term, describe a particular regularizer, or state how such a term changes the objective. Therefore, the verified conclusion here is limited to the unregularized convexity check: H = R^d is convex, and the squared loss is convex with respect to w.

Common Reasoning Errors

• Checking only the loss function

  The convex-learning check requires both a convex hypothesis class and a loss that is convex with respect to the parameter describing the hypothesis.

  Fix: Check H = R^d and the squared loss separately, then combine the two conclusions.

• Treating the hypothesis as only a function name

  The convex formulation examines the loss with respect to w, so the parameter-based description is essential.

  Fix: Connect the function-based prediction rule to its parameter vector and then identify the resulting hypothesis class.

• Forgetting the subtraction before squaring

  Squared loss squares the difference between prediction and target, not the prediction by itself.

  Fix: Calculate (3 - 5)^2, which equals 4.

• Assuming regularization details that are not given

  The supplied material does not specify a regularizer or analyze a combined objective.

  Fix: Limit the conclusion to the stated linear-regression and squared-loss formulation.

Check Your Understanding

1. A parameter vector w represents each linear-regression hypothesis. The hypothesis class is H = R^d, which the source identifies as convex. The squared loss is (<w,x> - y)^2, formed by predicting, subtracting the real-valued outcome, and squaring. This loss is convex with respect to w. Together, the convex hypothesis class and convex loss make this a convex learning problem. The supplied material does not provide enough detail to analyze a specific regularization term.