Linear Programming

The important question is not which feasible vector is best according to an objective. The first question is whether a vector exists that satisfies every training constraint.

Programming

From Perfect Classification to Feasibility

In the realizable setting, the training data can be classified perfectly by a homogeneous halfspace. Realizable empirical risk minimization therefore does not need to compare imperfect candidate predictors. Instead, it searches for one vector w whose associated halfspace makes no training mistakes. This changes the task into a feasibility problem: find a vector that satisfies every requirement imposed by the labeled examples.

How does satisfying every example-specific constraint produce a zero-error halfspace?

Key point

The important question is not which feasible vector is best according to an objective. The first question is whether a vector exists that satisfies every training constraint.

The Signed Inner-Product Test

For each labeled example (x_i, y_i), where the label is positive or negative, the required condition is y_i ⟨w, x_i⟩ ≥ 1. The label is multiplied into the inner product so that both positive and negative examples can be handled by the same inequality. A vector w is suitable when this inequality holds for every training example.

What inequality must w satisfy for a positive or negative labeled example to be classified correctly?

Worked example

Testing Two Labeled Instances

Consider (x_1, y_1) = ((1, 0), 1), (x_2, y_2) = ((0, 1), -1), and w = (2, -3). Check whether w satisfies the requirement for each instance.

1
First instance
The signed inner product is y_1⟨w, x_1⟩ = 1 multiplied by the inner product of (2, -3) and (1, 0), which equals 2. Since 2 is at least 1, the first requirement is satisfied.
2
Second instance
The inner product of (2, -3) and (0, 1) equals -3. Multiplying by y_2 = -1 gives 3. Since 3 is at least 1, the second requirement is also satisfied.
3
Conclusion
Both labeled instances meet the required inequality, so this vector passes the two-example feasibility check.

Result

The vector w = (2, -3) satisfies both signed inner-product constraints.

Building the Constraint Matrix

The individual constraints can be placed into matrix form by attaching each label to its instance. For example i, form the signed vector y_i x_i. Its inner product with w is exactly y_i ⟨w, x_i⟩. Therefore, the signed vectors can be used as the rows of a single matrix A.

How does each labeled example become one row of A and one corresponding LP constraint?

Worked example

Constructing A and v

Use the two labeled instances (x_1, y_1) = ((1, 0), 1) and (x_2, y_2) = ((0, 1), -1).

1
Sign the first instance
Compute y_1x_1 = 1(1, 0) = (1, 0). This becomes the first row of A.
2
Sign the second instance
Compute y_2x_2 = -1(0, 1) = (0, -1). This becomes the second row of A.
3
Assemble the matrix
The rows give A = ((1, 0), (0, -1)). The right-hand-side vector v contains one entry for each example, so v = (1, 1).
4
Check with w
Multiplying A by w = (2, -3) gives (2, 3). Both components are at least the corresponding components of v.

Result

The matrix inequality Aw ≥ v records the two original signed inner-product checks.

The complete constraint system is written as Aw ≥ v, where A contains the signed training instances as rows and v consists of ones. The matrix inequality is not a new requirement; it is a compact way to record all of the individual requirements at once.

The Dummy Objective

The LP convention uses a maximization objective, but this realizable ERM formulation does not need to prefer one feasible vector over another. Every vector satisfying all the constraints is an acceptable output hypothesis. The formulation therefore uses the dummy objective u = (0, ..., 0). Maximizing u · w does not distinguish among feasible vectors, so the constraints carry the substantive meaning.

Part of the LP	Role in this formulation
Constraint system Aw ≥ v	Requires the candidate vector to satisfy every training-example requirement.
Objective u · w	Uses u = (0, ..., 0), so it does not distinguish among feasible vectors.
Solver output	Any vector satisfying all constraints can serve as the ERM output.

The constraints determine acceptability; the objective is only a dummy objective.

Solver to Predictor

What steps connect the labeled data, matrix constraints, solver output, and final halfspace predictor?

1
Start with the labeled training instances (x_i, y_i).
2
Multiply each instance x_i by its label y_i.
3
Place the signed instances y_i x_i as the rows of A.
4
Create v with one entry for each training example.
5
Give the solver the constraints Aw ≥ v and the dummy objective u = (0, ..., 0).
6
Use a feasible output vector w as the ERM halfspace predictor.

The solver's role is to find a vector that passes all the constraints. Once such a vector is available, it defines the homogeneous halfspace associated with the ERM predictor. Because every training requirement was enforced, the resulting predictor makes no training mistakes in the realizable setting.

Common Construction Mistakes

Common mistake
Using x_i directly as a row of A for every example.
What it looks like
Putting (0, 1) into A for an example whose label is -1.
Why it fails
The row must represent y_i x_i so that its inner product with w equals y_i⟨w, x_i⟩.
Do this instead
Multiply each instance by its label first. The negative example becomes (0, -1).
Common mistake
Checking only whether the prediction is on the correct side of zero.
What it looks like
Treating a signed inner product below 1 as sufficient.
Why it fails
The required condition is y_i⟨w, x_i⟩ ≥ 1.
Do this instead
Check the full margin-style inequality for every example.
Common mistake
Trying to optimize a meaningful preference among feasible vectors.
What it looks like
Assuming the LP must choose the largest or smallest feasible w.
Why it fails
This formulation accepts any feasible vector and uses a zero objective.
Do this instead
Focus on satisfying Aw ≥ v; the dummy objective does not distinguish feasible outputs.
Common mistake
Checking only some of the rows of A.
What it looks like
Verifying the constraint for the positive example but not for the negative example.
Why it fails
A zero-error predictor must satisfy the requirement contributed by every labeled training instance.
Do this instead
Treat all rows of A as simultaneous constraints.

Check Your Construction

MEDIUM

For the generated data set (x_1, y_1) = ((1, 0), 1), (x_2, y_2) = ((0, 1), -1), and w = (2, -3), write the two signed rows of A and decide whether w satisfies Aw ≥ v.

Hints

Compute y_1x_1 and y_2x_2 separately.
Use one entry of 1 in v for each training example.
Multiply A by w and compare the result componentwise with v.

Your attempt (not saved)

What do you think happens?

If a vector w makes every component of Aw at least the corresponding component of v, what can you conclude in the realizable ERM formulation?

It is a feasible vector and can define a zero-error halfspace predictor.
It must be the unique optimal vector.
It violates at least one training constraint.
The objective function must be nonzero.

Reveal answer

Answer:

It is a feasible vector and can define a zero-error halfspace predictor.

The constraints encode the signed inner-product requirement for every training example. Satisfying all of them gives a feasible vector, and any feasible vector is acceptable in this formulation.

Key Takeaways

1
Realizable ERM for homogeneous halfspaces searches for a vector that makes no training mistakes.
2
Each labeled example contributes the inequality y_i⟨w, x_i⟩ ≥ 1.
3
Multiplying each instance by its label creates the rows of A, producing the matrix system Aw ≥ v with v consisting of ones.
4
The objective u = (0, ..., 0) is a dummy objective because any feasible vector is acceptable.
5
An LP solver can return a feasible vector w, which is then used as the ERM halfspace predictor.

At a glance

Realizable ERM becomes a feasibility problem when the goal is zero training error.
The required condition for every example is y_i⟨w, x_i⟩ ≥ 1.
The signed training instances y_i x_i become the rows of A, giving Aw ≥ v.
The zero objective does not rank feasible vectors; it simply accompanies the constraint system.
A feasible solver output w defines the desired zero-error halfspace predictor.

Related concepts

More concepts starting with L