Convex Loss Functions
Tikhonov regularization augments the loss with λ ‖w‖2.
From Fitting to Stability
A learning rule can fit the available data and still be unreliable when the data changes slightly. Algorithmic stability addresses this concern: stable rules do not overfit. The result studied here combines the RLM rule with Tikhonov regularization so that the resulting procedure is stable.
The Regularized Objective
Tikhonov regularization augments the loss in an RLM objective with the term λ ‖w‖2. The essential change is not merely that the objective becomes longer. The added term changes the structural properties of the objective: the regularized RLM objective is strongly convex.
regularized RLM objective = original RLM loss + λ ‖w‖2Tracking the Added Term
Suppose an RLM objective is represented by an original loss term. What changes when Tikhonov regularization is applied?
Start: Begin with the loss used by the RLM objective.
Augment: Add the Tikhonov term λ ‖w‖2 to that loss.
Identify the structural result: The resulting regularized RLM objective is strongly convex.
Connect to optimization: Strong convexity ensures a unique minimum.
Tikhonov regularization changes the RLM objective from an ordinary convex loss setting to a strongly convex objective with a unique minimum.
Convex Sets and Line Segments
A set is convex when every line segment joining two points in the set stays inside the set. To test the definition, choose any two vectors in the set and check whether every point on the segment between them also remains in the set.
A convex combination of two points uses non-negative coefficients that sum to 1. For points u and v, the expression αu + (1 − α)v represents a point on the line segment joining them when α ranges from 0 to 1. The endpoints occur at the two extreme coefficient choices, and intermediate coefficients select points between those endpoints.
αu + (1 − α)v, with non-negative coefficients whose sum is 1Recognizing Convexity
Consider a set containing two points u and v together with every point of the segment αu + (1 − α)v for non-negative coefficients that sum to 1. Does this satisfy the definition of a convex set?
Choose two points: Select u and v from the set.
Form the segment: Use αu + (1 − α)v to represent the points joining them.
Check containment: By the description of the set, every such segment point remains inside the set.
Yes. The set satisfies the convexity definition because the full line segment between the selected points stays inside the set.
Convex Functions
A function is convex when its value at a convex combination is no greater than the matching convex combination of its endpoint values. For points u and v and a non-negative coefficient pair summing to 1, the defining comparison is between f(αu + (1 − α)v) and αf(u) + (1 − α)f(v).
f(αu + (1 − α)v) ≤ αf(u) + (1 − α)f(v)
| Idea | What is being tested | Defining condition |
|---|---|---|
| Convex set | The locations of points | Every line segment joining two points in the set remains in the set |
| Convex combination | How points are combined | Coefficients are non-negative and sum to 1 |
| Convex function | Function values at combined inputs | f(αu + (1 − α)v) is no greater than αf(u) + (1 − α)f(v) |
Stability Assumptions
The stability result assumes that the loss is convex and is either Lipschitz or smooth. Under these assumptions, the RLM rule together with Tikhonov regularization produces the strongly convex objective used in the stability argument.
Treating an ordinary convex objective as automatically strongly convex.
The source result emphasizes the transition created by regularization.
Fix:
Identify the added λ ‖w‖2 term and then describe the regularized RLM objective as strongly convex.Confusing a convex set with a convex function.
A convex set is tested by geometric containment, while a convex function is tested by an inequality involving function values.
Fix:
For a set, check the entire segment between two points. For a function, check the inequality at a convex combination.Forgetting the coefficient conditions in a convex combination.
Those coefficient conditions are part of the definition.
Fix:
Verify both requirements before applying the line-segment interpretation.Listing unsupported assumptions about the loss.
The stated result assumes a convex loss that is either Lipschitz or smooth.
Fix:
State the convexity assumption and the either-Lipschitz-or-smooth condition explicitly.
Check Your Understanding
Explain the full chain in your own words: start with a convex loss, add Tikhonov regularization to the RLM objective, identify the resulting structural property, and state how that property supports algorithmic stability.
Hints
- Name the term added by Tikhonov regularization.
- State what strong convexity ensures.
- Include the assumptions that the loss is convex and either Lipschitz or smooth.
For a set, describe the test you would perform to decide whether it is convex. Then explain how the same line-segment idea appears in the expression αu + (1 − α)v.
Hints
- Choose two points from the set.
- Consider every point on the segment joining them.
- Remember that the coefficients in a convex combination are non-negative and sum to 1.
State the inequality that defines a convex function and identify which part concerns the function evaluated at the combined input.
Hints
- Use the points u and v.
- Use the coefficient α and its complementary coefficient 1 − α.
- Compare the function of the combination with the combination of the function values.
Key Takeaways
- Tikhonov regularization augments an RLM loss with λ ‖w‖2.
- The regularized RLM objective is strongly convex, and strong convexity ensures a unique minimum.
- The stability result assumes a convex loss that is either Lipschitz or smooth.
- A convex set contains every line segment joining any two of its points.
- A convex function satisfies f(αu + (1 − α)v) ≤ αf(u) + (1 − α)f(v).