Sample Complexity
Regression loss functions measure more than whether a prediction is wrong: they quantify the discrepancy between prediction and target.
Why Regression Needs Loss
A regression model rarely produces only perfectly correct or completely incorrect answers. If the actual value is 3 kg, predictions of 3.00001 kg and 4 kg are both different from the target, but they are not equally bad. Regression therefore needs a loss function: a rule that converts the discrepancy between a prediction and the actual value into a numerical penalty.
A loss function evaluates the quality of one prediction by measuring how far that prediction is from its target. The choice of loss is part of the modeling choice because it determines what the learning procedure treats as a small or large error.
| Prediction | Actual value | Interpretation |
|---|---|---|
| 3.00001 kg | 3 kg | Small discrepancy |
| 4 kg | 3 kg | Larger discrepancy |
Two Penalties for One Error
Squared loss and absolute value loss begin with the same discrepancy between a prediction and a target, but they apply different penalty rules. For a prediction of 4 and an actual value of 3, the discrepancy is 1. Squared loss makes the penalty 1 squared, which is 1. Absolute value loss makes the penalty the absolute value of 1, which is also 1. The two losses agree for this particular discrepancy, but they do not generally assign the same penalty.
Applying Both Losses
A model predicts 5 for a target value of 3. Calculate squared loss and absolute value loss.
Find the discrepancy: The prediction minus the target is 5 − 3 = 2.
Apply squared loss: Square the discrepancy: 2 squared = 4.
Apply absolute value loss: Take the absolute value of the discrepancy: absolute value of 2 = 2.
Squared loss is 4, while absolute value loss is 2.
From One Loss to Empirical Risk
A loss function evaluates one example at a time. When squared loss is used across a data set, the resulting empirical risk function is called Mean Squared Error. The individual squared-loss expression describes one prediction's penalty; Mean Squared Error describes the empirical-risk calculation associated with applying squared loss across the sample.
Averaging Squared Losses
Suppose three examples have squared losses of 4, 1, and 9. Find the empirical risk associated with squared loss.
Collect the individual losses: The sample contributes losses of 4, 1, and 9.
Add the losses: Their total is 4 + 1 + 9 = 14.
Average across the examples: Divide the total by the three examples: 14 divided by 3.
The empirical risk is 14 divided by 3, and for squared loss this empirical-risk function is called Mean Squared Error.
Calling the loss on one prediction Mean Squared Error.
Mean Squared Error is the empirical risk function associated with squared loss across a data set.
Fix:
Use squared loss for one example and Mean Squared Error for the empirical-risk calculation across examples.
Discretizing Linear Hypotheses
Sample-complexity analysis can become difficult when the hypothesis class contains continuously varying linear-regression parameters. One possible route is the discretization trick. Instead of allowing every possible parameter value, discretization restricts the available values to a finite set. The resulting collection of permitted linear hypotheses is finite, which makes finite-class analysis relevant.
Meaning of Sample Complexity
Sample complexity gives the number of examples required for a probably approximately correct solution. More specifically, it describes how much training data is needed before a result can be guaranteed to be probably approximately correct for a hypothesis class H under specified accuracy and confidence requirements.
Sample complexity is a function rather than one permanent number. Write it as m_H(ε, δ), where H identifies the hypothesis class, ε identifies the accuracy requirement, and δ identifies the confidence requirement. The relevant value can change when any of these learning requirements or class properties change.
| Part of m_H(ε, δ) | Role |
|---|---|
| ε | Specifies the accuracy requirement. |
| δ | Specifies the confidence requirement. |
| H | Identifies the hypothesis class whose learning requirements are being studied. |
Sample complexity depends on the requested guarantee and on the class being learned.
Valid Bounds and Minimal Complexity
PAC learnability may permit many functions that satisfy the requirements. Therefore, a function that gives a sufficient number of examples can be valid even when it is larger than necessary. The precisely defined sample complexity is the minimal function: for each ε and δ, it returns the smallest integer that satisfies the PAC requirements.
Every minimal sample-complexity value is a valid sufficient bound, but a valid bound need not be minimal. The word minimal refers to the smallest integer that meets the PAC requirements for the specified ε and δ.
Why the Class Matters
Two learning problems can use the same accuracy and confidence parameters while involving different hypothesis classes. Their sample-complexity requirements need not be the same because sample complexity also reflects properties of H. For a finite hypothesis class, one relevant dependence is on the logarithm of the size of H.
When discussing sample complexity, always name the hypothesis class as well as the accuracy and confidence parameters. Saying only “the sample complexity” hides which learning problem is being analyzed.
Check Your Understanding
A regression model predicts 7 for an actual value of 4. Calculate the squared loss and the absolute value loss. Then explain which quantity would describe one example and which named empirical-risk function would be used when squared loss is applied across a data set.
Hints
- First find the discrepancy between 7 and 4.
- Apply the two penalty rules separately.
- Remember that empirical risk combines losses across examples.
Explain why discretizing the allowed parameter values of a linear-regression hypothesis class can help with sample-complexity analysis. In your answer, distinguish the original class from the restricted class.
Hints
- Focus on whether the available parameter values are continuous or restricted.
- Identify whether the resulting collection of hypotheses is finite.
Treating sample complexity as one fixed number.
The function depends on ε, δ, and properties of H.
Fix:
State the relevant accuracy, confidence, and hypothesis class when discussing the number of examples.Assuming any sufficient bound must be the minimal sample complexity.
PAC requirements may be satisfied by multiple functions.
Fix:
Call the smallest sufficient function the minimal sample complexity function.Using a binary-classification VC-dimension analysis directly for linear regression.
Linear regression is not a binary prediction task, so its sample complexity cannot be analyzed using VC-dimension in the described binary-classification way.
Fix:
Recognize discretization as one possible route for analyzing the linear-regression setting.
Key Takeaways
- Regression loss measures the size of a discrepancy, not merely whether a prediction differs from its target.
- Squared loss and absolute value loss use different penalty rules for the same prediction and target.
- The loss on one example is different from the empirical risk across a data set; with squared loss, that empirical-risk function is Mean Squared Error.
- Discretization can restrict continuous linear-regression parameters so that the resulting hypothesis class is finite for sample-complexity analysis.
- Sample complexity is a function of accuracy ε, confidence δ, and properties of the hypothesis class H; the minimal function gives the smallest sufficient number of examples.
Key Takeaways
- Loss functions quantify how far a regression prediction is from its target.
- Squared loss and absolute value loss can assign different penalties to the same discrepancy.
- Mean Squared Error is the empirical risk associated with squared loss across a data set, not the loss on one example.
- Discretization can turn an infinite linear-regression hypothesis class into a finite class for analysis.
- Sample complexity specifies the examples needed for PAC learning and depends on ε, δ, and H; its minimal version is the smallest sufficient function.