Concepts / Convex Sets

Convex Sets

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.

  • Programming

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.

Point uin the setLine segmentinside the setPoint vin the setjoinjoin
What happens to the line segment connecting two points in a set, and does the entire segment remain inside the set?
Key point

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.

Formula
uα = 1αu + (1 − α)v0 < α < 1vα = 0decrease αdecrease α
How does changing the weight between two points move the resulting point along the line segment between them?
Worked example

Checking a Convex Combination

Suppose two points are u and v, and choose α = 0.25. Describe the resulting combination.

  1. 1
    Substitute the weight

    The expression becomes 0.25u + 0.75v because 1 − α equals 0.75.

  2. 2
    Check the coefficients

    Both coefficients are non-negative, and 0.25 + 0.75 equals 1.

  3. 3
    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.

Result

0.25u + 0.75v is a convex combination of u and v.

Recognizing Convex Sets

Definition

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.

Worked example

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?

  1. 1
    Choose two points

    Take any two points that belong to the set.

  2. 2
    Connect them

    The segment between those two points is contained within the original segment joining u and v.

  3. 3
    Apply the definition

    The connecting segment stays inside the set, so the set satisfies the line-segment requirement.

Result

The set is convex under the stated definition.

Worked example

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?

  1. 1
    Choose the two included points

    Both u and v belong to the set.

  2. 2
    Inspect their segment

    The line segment joining u and v contains points that are not in the set.

  3. 3
    Apply the definition

    Because the entire segment does not remain inside the set, the required condition fails.

Result

The set is not convex under the stated definition.

u to ventire segment insideConvex setcondition holdsu to vsome segment point outsideNon-convex setcondition failstest passestest fails
Does the complete line segment between two selected points remain inside the set?

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.

Learning problemHypothesis classconvex setConvex learningproblemboth conditions holdLoss functionconvex in hypothesisEvery exampleloss condition appliesrequiresrequiresforandand
How do the hypothesis class and the loss function each need to satisfy convexity for the overall learning problem to be convex?
Key point

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

Definition

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.

Formula
L(u)endpoint lossαL(u) + (1 − α)L(v)weighted endpoint lossesL(v)endpoint lossL(αu + (1 − α)v)loss at combined hypothesisweight αweight 1 − αno greater than
How does the loss at a weighted average of two hypotheses compare with the weighted average of their individual losses?
Worked example

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?

  1. 1
    Compute the weighted endpoint losses

    The right side is 0.5(4) + 0.5(10), which equals 7.

  2. 2
    Compare the combined loss

    The left side is 6, while the right side is 7.

  3. 3
    Apply the inequality

    Because 6 is no greater than 7, this check satisfies the required inequality.

Result

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?

ObjectWhat is being tested?Required condition
Convex setWhether points remain in the setEvery line segment joining two points in the set stays inside the set
Convex functionWhether function values satisfy an inequalityThe value at a convex combination is no greater than the matching convex combination of endpoint values
Convex learning problemWhether both learning components satisfy convexityThe hypothesis class is convex and the loss is convex in the hypothesis for every example

The geometric and functional meanings of convexity must be kept separate.

Common Testing Mistakes

  • Common mistake

    Checking only one pair of points in a proposed set.

    What it looks like

    One selected segment stays inside the set, so the set is declared convex.

    Why it fails

    The definition requires the condition for every pair of points in the set.

    Do this instead

    Treat one successful pair as evidence for that pair only; convexity requires the universal line-segment condition.

  • Common mistake

    Allowing arbitrary coefficients in a convex combination.

    What it looks like

    Using coefficients that are negative or that do not sum to 1.

    Why it fails

    A convex combination uses non-negative coefficients that sum to 1.

    Do this instead

    Check both coefficient requirements before applying the line-segment interpretation.

  • Common mistake

    Checking the loss for only one example.

    What it looks like

    The loss is convex in the hypothesis for a selected example, so the entire learning problem is called convex.

    Why it fails

    The loss must be convex as a function of the hypothesis for every example.

    Do this instead

    Apply the loss condition across the entire example set.

  • Common mistake

    Treating one failed requirement as harmless.

    What it looks like

    The hypothesis class is convex, but the loss condition fails for an example.

    Why it fails

    The two requirements must hold together.

    Do this instead

    If either the hypothesis-class condition or the loss condition fails, the learning problem is not convex under this definition.

  • Common mistake

    Confusing set membership with function values.

    What it looks like

    Using the loss inequality as though it directly described whether a point belongs to a hypothesis class.

    Why it fails

    Set convexity concerns whether line segments stay inside a set, while function convexity concerns an inequality between values.

    Do this instead

    Identify whether the current test concerns the hypothesis class or the loss function.

Convexity Decision Practice

MEDIUM

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.
Worked example

Practice Solution

A hypothesis class is convex, but the loss inequality fails for one example. Is the learning problem convex?

  1. 1
    Check the hypothesis class

    The first requirement is satisfied because the hypothesis class is a convex set.

  2. 2
    Check the loss function

    The second requirement is not satisfied because the loss must be convex in the hypothesis for every example.

  3. 3
    Combine the results

    The requirements are conjunctive: both must hold together.

Result

The learning problem is not convex under this definition.

Key Takeaways

  1. 1
    A convex set contains the entire line segment joining any two of its points.
  2. 2
    A convex combination has the form αu + (1 − α)v with non-negative coefficients that sum to 1.
  3. 3
    A convex function has a value at a convex combination no greater than the matching convex combination of endpoint values.
  4. 4
    A convex learning problem requires both a convex hypothesis class and a loss function that is convex in the hypothesis for every example.
  5. 5
    A set concerns where points belong; a function concerns how values compare.

At a glance

  • 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.

Related Topics

Related concepts

More concepts starting with C