Convex Sets
Convexity of a learning problem has two requirements.
Why the Line Segment Matters
Convexity begins with a simple question about two points: if both points belong to a set, what happens to every point on the line segment connecting them? A set is convex when that entire segment stays inside the set. This geometric idea also supports the definition of a convex learning problem, where both the hypothesis class and the loss function must satisfy their own convexity requirements.
The word every is essential. Convexity requires the segment joining any two points in the set to remain inside the set, not merely the segment joining one convenient pair of points.
Convex Combinations
A convex combination of two points u and v has the form αu + (1 − α)v. The coefficients must be non-negative and must sum to 1. For the two coefficients shown here, that means α is non-negative and 1 − α is also non-negative, while their sum is exactly 1. As the weight changes, the resulting point moves along the line segment joining u and v. The endpoint weights select the endpoints, and weights between the endpoints select points between them.
αu + (1 − α)vChecking a Convex Combination
Suppose two points are u and v, and choose α = 0.25. Describe the resulting combination.
Substitute the weight: The expression becomes 0.25u + 0.75v because 1 − α equals 0.75.
Check the coefficients: Both coefficients are non-negative, and 0.25 + 0.75 equals 1.
Interpret the result: The resulting point lies on the line segment joining u and v, closer to v than to u because v has the larger coefficient.
0.25u + 0.75v is a convex combination of u and v.
Recognizing Convex Sets
A set is convex when every line segment joining two points in the set stays inside the set. Equivalently, for any two points u and v in the set, the points represented by the convex combination αu + (1 − α)v must also remain in the set when the coefficients are non-negative and sum to 1.
To test a proposed set, choose two points from that set and examine the entire segment between them. If even one point on that segment leaves the set, the set fails the definition of convexity. If the test is required for every pair of points, one successful segment is not enough to establish convexity.
A Set That Passes the Segment Test
Consider the set of all points on a line segment joining two points u and v. Is this set convex?
Choose two points: Take any two points that belong to the set.
Connect them: The segment between those two points is contained within the original segment joining u and v.
Apply the definition: The connecting segment stays inside the set, so the set satisfies the line-segment requirement.
The set is convex under the stated definition.
A Set That Fails the Segment Test
Consider a set containing two points u and v but not every point between them. Is this set convex?
Choose the two included points: Both u and v belong to the set.
Inspect their segment: The line segment joining u and v contains points that are not in the set.
Apply the definition: Because the entire segment does not remain inside the set, the required condition fails.
The set is not convex under the stated definition.
Convex Learning Problems
A convex learning problem has two requirements that must hold together. First, the hypothesis class must be a convex set. In this setting, hypotheses are real-valued vectors in a subset of R^d, so the line-segment test is applied to the possible hypothesis vectors. Second, for every example in the example set, the loss function must be convex as a function of the hypothesis.
The loss requirement is universal over examples. It is not enough for the loss to be convex for one example or for some examples. It must be convex as a function of the hypothesis for every example in the example set.
- Check whether the hypothesis class is a convex set.
- Check whether the loss function is convex in the hypothesis for every example.
- Conclude that the learning problem is convex only when both requirements hold.
- If either requirement fails, the learning problem is not convex under this definition.
The Loss Inequality
A convex function has a value at a convex combination that is no greater than the matching convex combination of its endpoint values. For a loss function viewed as a function of the hypothesis, the loss at αu + (1 − α)v must be no greater than α times the loss at u plus (1 − α) times the loss at v.
L(αu + (1 − α)v) ≤ αL(u) + (1 − α)L(v)Applying the Convex Function Test
Suppose a loss function produces L(u) = 4, L(v) = 10, and L(αu + (1 − α)v) = 6 when α = 0.5. Does this numerical check satisfy the convexity inequality?
Compute the weighted endpoint losses: The right side is 0.5(4) + 0.5(10), which equals 7.
Compare the combined loss: The left side is 6, while the right side is 7.
Apply the inequality: Because 6 is no greater than 7, this check satisfies the required inequality.
This particular check is consistent with convexity. A complete learning-problem judgment still requires the hypothesis-class condition and the loss condition for every example.
Set Versus Function
A convex set and a convex function use related language but answer different questions. For a set, convexity is about membership: when two points belong to the set, does every point on the segment between them also belong to it? For a function, convexity is about values: is the function value at a convex combination no greater than the matching convex combination of the endpoint values?
| Object | What is being tested? | Required condition |
|---|---|---|
| Convex set | Whether points remain in the set | Every line segment joining two points in the set stays inside the set |
| Convex function | Whether function values satisfy an inequality | The value at a convex combination is no greater than the matching convex combination of endpoint values |
| Convex learning problem | Whether both learning components satisfy convexity | The hypothesis class is convex and the loss is convex in the hypothesis for every example |
Common Testing Mistakes
Checking only one pair of points in a proposed set.
The definition requires the condition for every pair of points in the set.
Fix:
Treat one successful pair as evidence for that pair only; convexity requires the universal line-segment condition.Allowing arbitrary coefficients in a convex combination.
A convex combination uses non-negative coefficients that sum to 1.
Fix:
Check both coefficient requirements before applying the line-segment interpretation.Checking the loss for only one example.
The loss must be convex as a function of the hypothesis for every example.
Fix:
Apply the loss condition across the entire example set.Treating one failed requirement as harmless.
The two requirements must hold together.
Fix:
If either the hypothesis-class condition or the loss condition fails, the learning problem is not convex under this definition.Confusing set membership with function values.
Set convexity concerns whether line segments stay inside a set, while function convexity concerns an inequality between values.
Fix:
Identify whether the current test concerns the hypothesis class or the loss function.
Convexity Decision Practice
A learning problem has a hypothesis class that passes the line-segment test. Its loss satisfies the convex-function inequality for some examples, but the condition fails for one example. Is the learning problem convex under the definition in this article? Explain which requirement fails.
Hints
- List the two requirements separately.
- Pay attention to the word every in the loss requirement.
- Both conditions must hold together.
Practice Solution
A hypothesis class is convex, but the loss inequality fails for one example. Is the learning problem convex?
Check the hypothesis class: The first requirement is satisfied because the hypothesis class is a convex set.
Check the loss function: The second requirement is not satisfied because the loss must be convex in the hypothesis for every example.
Combine the results: The requirements are conjunctive: both must hold together.
The learning problem is not convex under this definition.
Key Takeaways
- A convex set contains the entire line segment joining any two of its points.
- A convex combination has the form αu + (1 − α)v with non-negative coefficients that sum to 1.
- A convex function has a value at a convex combination no greater than the matching convex combination of endpoint values.
- A convex learning problem requires both a convex hypothesis class and a loss function that is convex in the hypothesis for every example.
- A set concerns where points belong; a function concerns how values compare.
Key Takeaways
- Convexity of a set is tested by checking whether every line segment between two points remains inside the set.
- The expression αu + (1 − α)v describes a convex combination when its coefficients are non-negative and sum to 1.
- Convexity of a function is defined by an inequality comparing the function at a combination with the corresponding combination of function values.
- A convex learning problem requires both a convex hypothesis class and a loss function convex in the hypothesis for every example.
- Set convexity is a membership question, while function convexity is a value-comparison question.