Carathéodory's Theorem

The compressed object is a subset of training points, not the weight vector itself.

Programming

The Compression Question

A linear classifier may appear to depend on every training example. The construction studied here searches for a much smaller description: a subset of training points from which the classifier's separating vector can be reconstructed. The important distinction is that the compressed object is not the weight vector itself. It is a selected subset of training points.

The classifier is determined by a vector, but the compressed description consists of training points that can be used to rebuild that vector.

Homogeneous Halfspaces

For a vector w, a homogeneous halfspace is determined by the sign of the dot product between an input point x and w. A positive dot product places x on one side of the hyperplane, a negative dot product places it on the other side, and a zero dot product places it on the boundary. The hyperplane passes through the origin because there is no separate offset term in this description.

How does the sign of a dot product place a point on one side of, the other side of, or the boundary of a homogeneous hyperplane?

This sign rule explains why the vector selected from the training sample matters: if it has the required dot-product sign for every training point, it defines a separator for the sample.

Finding the Closest Hull Point

Start with the convex hull of the training sample. The construction selects the point w in that convex hull whose Euclidean norm is as small as possible. Geometrically, w is the point where the line from the origin reaches the convex hull most closely. Equivalently, w is the Euclidean projection of the origin onto the convex hull.

How does the minimum-norm point of the convex hull determine a hyperplane that separates linearly separable data?

Following the geometric selection

Given a linearly separable training sample, identify the vector used by the compression construction.

Form the hull: Combine the training points through their convex hull. The construction works with this geometric object rather than examining the points as an unrelated list.

Search for the closest point: Among all points in the convex hull, select w, the point with the smallest Euclidean norm. It is the point in the hull closest to the origin.

Use w as the separator: The selected vector is used as the separating vector for the homogeneous hyperplane.

The target of the compression process is the minimum-norm point w of the training sample's convex hull.

Why Separation Follows

The minimum-norm property does more than choose a convenient point. It forces w to separate the training data. Suppose, for contradiction, that some training point xi had a nonpositive dot product with w. Moving a suitable amount from w toward xi would stay inside the same convex hull while producing a point closer to the origin. That would contradict the choice of w as the closest point in the hull.

What do you think happens?

What would contradict the claim that w is the minimum-norm point of the convex hull?

Finding a training point with a nonpositive dot product with w
Finding that w belongs to the convex hull
Writing w as a convex combination
Using fewer points to describe the sample

Reveal answer

Answer: Finding a training point with a nonpositive dot product with w

A suitable move from w toward that training point would remain in the convex hull and get closer to the origin, contradicting the minimum-norm choice.

Carathéodory's Point Bound

Because w lies in the convex hull of the training sample, it can be written as a convex combination of sample points. Carathéodory's theorem gives a representation using at most d plus 1 points in d-dimensional space. In this construction, there is an additional geometric fact: the minimum-norm point lies on a face of the convex hull. The face property reduces the representation to a convex combination of d sample points.

How can the same convex-hull vector be represented using at most dimension-plus-one training points and, in this construction, d points with corresponding coefficients?

Geometric fact	Representation consequence
w lies in the convex hull	w can be written as a convex combination of training points
Carathéodory's theorem applies in d dimensions	At most d plus 1 points are needed in general
w lies on a face of the convex hull	This construction uses d points

The general theorem and the additional face property play different roles.

Compression and Reconstruction

The process has two different stages. First comes compression: retain the small subset of training points that participates in a convex-combination representation of w. The points are the compressed description. Second comes reconstruction: use those selected points and their convex-combination coefficients to recover w. The classifier is then determined by the reconstructed vector.

What happens first when the training sample is compressed to a subset of points, and how is the relevant vector reconstructed afterward?

Treating w itself as the compressed object
The construction defines the compressed description as selected training points from which w can be reconstructed.
Fix: Separate the roles: the subset is stored as the compressed description, and w is rebuilt from it.
Assuming any correctly classifying examples form the compressed subset
The selected points come from a convex-combination representation of the minimum-norm point.
Fix: Tie selection to the geometry of the convex hull and the representation of w.
Stopping at the general d plus 1 bound
The face property gives the stronger d-point representation for this construction.
Fix: State both results: Carathéodory's general bound is d plus 1, while the additional face property reduces this case to d.

A Complete Trace

Tracing the full compression construction

Explain how a linearly separable training sample becomes a compact description of a classifier.

Begin with the sample: Take the complete set of training points and consider its convex hull.

Select w: Find the point in that convex hull with minimum Euclidean norm. This is the point closest to the origin.

Use the separation property: If any training point had a nonpositive dot product with w, moving toward that point would create a closer hull point. Therefore the minimum-norm argument supplies a separating vector.

Represent w: Because w belongs to the convex hull, express it as a convex combination of sample points.

Reduce the representation: Carathéodory's theorem gives at most d plus 1 points in general. Since w lies on a face in this construction, use d points.

Reconstruct later: Store the selected points as the compressed description. When needed, combine them with their coefficients to recover w and therefore the classifier.

The sample is compressed by retaining points, while the separating vector is reconstructed from those points rather than being treated as the compressed object.

The order matters. The minimum-norm point is selected before the small representation is extracted. Carathéodory's theorem does not by itself choose the classifier; it limits how many sample points are needed after the relevant convex-hull vector has been identified.

Practice Check

MEDIUM

A training sample lies in d-dimensional space. Explain, in order, how to obtain a compressed description using the minimum-norm point of its convex hull. Your answer should identify the object selected first, explain why it separates the sample, state the general Carathéodory bound, state the stronger bound available here, and distinguish the stored subset from the reconstructed vector.

Hints

Begin with the convex hull rather than with an arbitrary training point.
Use the contradiction involving a nonpositive dot product to explain separation.
Mention both d plus 1 and d, and explain why they differ.

Your attempt (not saved)

Carathéodory's theorem supports a compression construction for a linearly separable training sample. The process selects the minimum-norm point w of the sample's convex hull. That point separates the training data because a nonpositive dot product would allow a closer point in the same hull. Since w is in the convex hull, it has a convex-combination representation. Carathéodory's theorem gives at most d plus 1 points in general, and the face property reduces this construction to d points. Those selected training points are the compressed description; their coefficients are used later to reconstruct w.

Key Takeaways

A homogeneous halfspace is defined by the sign of a dot product with a vector.
The construction selects the minimum-norm point of the training sample's convex hull.
The minimum-norm point separates the training data because a nonpositive dot product would contradict its closest-point property.
Carathéodory's theorem gives a representation using at most d plus 1 points, while the face property reduces this construction to d points.
The compressed object is a subset of training points, and the separating vector is reconstructed from that subset.