LPBoost And Maximum-Margin Reweighting

Why Reweighting and Margin Maximization Are Linked

Boosting combines weak rules, but it also changes how much attention each training example receives. LPBoost makes these two perspectives part of one optimization problem: its primal chooses a convex combination of rules to raise the smallest training margin, while its dual chooses example weights that make even the best available rule have a small weighted edge.

This equivalence gives a useful interpretation of reweighting. A dual distribution is not merely a record of which examples a procedure happened to emphasize. It is an optimization certificate: it identifies a distribution under which no weak rule can achieve a weighted advantage above the dual objective. The formulation below uses a finite training sample and binary-valued rules so that both sides are ordinary linear programs.

Margins and the LPBoost Primal

Let the training sample be \((x_i,y_i)\), \(i=1,\ldots,n\), with labels \(y_i\in\{-1,+1\}\). Let \(\mathcal H=\{h_1,\ldots,h_M\}\) be a nonempty finite set of weak rules, each taking values in \(\{-1,+1\}\). Write \(A_{ij}=y_i h_j(x_i)\), the signed prediction of rule \(h_j\) on example \(i\).

Definition: A convex combination of the weak rules has coefficients \(\alpha_j\geq 0\) with \(\sum_{j=1}^M\alpha_j=1\), and score \(F_\alpha(x)=\sum_{j=1}^M\alpha_jh_j(x)\). Its empirical margin on example \(i\) is \(m_i(\alpha)=y_iF_\alpha(x_i)=\sum_{j=1}^M\alpha_jA_{ij}\). The hard-margin LPBoost problem maximizes the smallest of these margins:

\begin{aligned} \rho^*=\max_{\alpha,\rho}\quad &\rho\\ \text{subject to}\quad &\sum_{j=1}^M\alpha_j A_{ij}\geq \rho,\qquad i=1,\ldots,n,\\ &\sum_{j=1}^M\alpha_j=1,\qquad \alpha_j\geq 0. \end{aligned}

The variable \(\rho\) is unrestricted in sign. If no convex combination gives every example a positive margin, the optimum can be zero or negative. That does not make the program infeasible: a feasible \(\alpha\) always exists, and \(\rho\) can be chosen below its smallest margin. Since every \(A_{ij}\) is either \(-1\) or \(+1\), all mixture margins lie in \([-1,1]\), so the optimal value is finite.

Worked Example: Three Rules That Each Miss One Example

Suppose the signed-prediction matrix is

A= \begin{pmatrix} 1&1&-1\\ 1&-1&1\\ -1&1&1 \end{pmatrix}.

Each rule is correct on two examples and incorrect on one. With \(\alpha_1=\alpha_2=\alpha_3=1/3\), each margin is \((1+1-1)/3=1/3\), so \(\rho^*\geq 1/3\). For any mixture, the sum of its three margins is \(1\): each column of \(A\) sums to \(1\), and the coefficients sum to \(1\). The smallest margin cannot exceed the average margin, which is \(1/3\). Therefore \(\rho^*=1/3\), attained by the equal mixture.

This calculation gives a direct primal certificate: a mixture achieves \(1/3\), and no mixture can do better because its average margin is fixed at \(1/3\).

The Dual: A Distribution Over Examples

A weight vector \(D=(D_1,\ldots,D_n)\) is a probability distribution on the training examples when \(D_i\geq0\) and \(\sum_iD_i=1\). The weighted edge of rule \(h_j\) under these weights is \(\sum_iD_iA_{ij}\). The dual LPBoost problem minimizes the largest such edge:

\begin{aligned} \gamma^*=\min_{D,\gamma}\quad &\gamma\\ \text{subject to}\quad &\sum_{i=1}^nD_iA_{ij}\leq\gamma,\qquad j=1,\ldots,M,\\ &\sum_{i=1}^nD_i=1,\qquad D_i\geq0. \end{aligned}

The constraint for each rule matters: the dual seeks weights under which every available weak rule has edge at most \(\gamma\). For a binary rule, its weighted error is \(\sum_iD_i\mathbf{1}\{y_i\ne h_j(x_i)\}\), and its weighted edge equals one minus twice that error. Thus, minimizing the largest edge makes the strongest rule’s weighted advantage as small as possible.

Theorem: For a finite nonempty set of binary weak rules, the hard-margin primal and the dual above have optimal solutions and equal optimal values: \(\rho^*=\gamma^*\).

Proof. First, for any primal-feasible \(\alpha\) and any distribution \(D\), the smallest margin is at most its \(D\)-weighted average. That average is a mixture of the rules’ weighted edges, and so it cannot exceed the largest edge:

\min_i\sum_j\alpha_jA_{ij} \leq \sum_iD_i\sum_j\alpha_jA_{ij} =\sum_j\alpha_j\sum_iD_iA_{ij} \leq \max_j\sum_iD_iA_{ij}.

Taking the maximum over \(\alpha\) and then the minimum over \(D\) proves \(\rho^*\leq\gamma^*\). For the reverse equality, apply finite-dimensional linear programming duality. To see the dual variables explicitly, write the primal margin constraints as \(\rho-\sum_j\alpha_jA_{ij}\leq0\). Assign nonnegative multipliers \(D_i\) to these constraints and a free multiplier \(\lambda\) to \(\sum_j\alpha_j=1\). The Lagrangian for the maximization is

\rho-\sum_iD_i\left(\rho-\sum_j\alpha_jA_{ij}\right) +\lambda\left(1-\sum_j\alpha_j\right) = \rho\left(1-\sum_iD_i\right) +\lambda+\sum_j\alpha_j\left(\sum_iD_iA_{ij}-\lambda\right).

Its supremum over unrestricted \(\rho\) is finite only if \(\sum_iD_i=1\). Its supremum over \(\alpha_j\geq0\) is finite only if \(\sum_iD_iA_{ij}\leq\lambda\) for every \(j\). Under those conditions the supremum is \(\lambda\), giving exactly the stated dual LP with \(\gamma=\lambda\). Both programs are feasible and have finite optima; the primal is bounded by the margin range, and the dual is feasible, for example with uniform \(D\) and \(\gamma=1\). Strong duality for finite linear programs therefore gives equality and attainment. \(\square\)

Worked Example: Matching Primal and Dual Certificates

For the matrix in the first example, equal mixture weights give all three margins \(1/3\). Now take \(D_i=1/3\) for all three examples. Each column of \(A\) sums to \(1\), so each rule’s weighted edge is \(1/3\). This makes \(\gamma=1/3\) dual-feasible. The primal solution gives \(\rho^*\geq1/3\), and the dual solution gives \(\gamma^*\leq1/3\). Since weak duality gives \(\rho^*\leq\gamma^*\), both optima equal \(1/3\).

The two certificates have different roles: the mixture exhibits a margin of \(1/3\), while the example weights show that no mixture can exceed \(1/3\).

Reweighting in a Small Example

The dual solution need not put equal weight on the examples. Consider two rules on three examples with signed-prediction columns \((-1,1,-1)\) and \((-1,-1,1)\). The first example is wrong under both rules. The dual objective, for a distribution \(D\), is the larger of the two weighted edges.

Worked Example: The Dual Emphasizes a Shared Failure

Write \(D_1+D_2+D_3=1\). The two edges are

-D_1+D_2-D_3=2D_2-1,\qquad -D_1-D_2+D_3=2D_3-1.

Choosing \(D=(1,0,0)\) gives edge \(-1\) for each rule, so \(\gamma^*\leq-1\). No distribution can give an edge below \(-1\), because each signed prediction is at least \(-1\) and a weighted average of values at least \(-1\) is also at least \(-1\). Hence \(\gamma^*=-1\). The primal mixture with \(\alpha_1=\alpha_2=1/2\) has margins \((-1,0,0)\), so its minimum margin is \(-1\). This attains the primal optimum.

Here the dual puts all its weight on an example that both rules get wrong. The primal and dual agree on the limitation: the available rules cannot avoid a minimum margin of \(-1\).

Soft Margins and Bounded Example Weights

A hard minimum can be sensitive to a single difficult example. One common soft-margin formulation permits nonnegative slacks \(\xi_i\), penalizing their total. For a specified \(\nu\in(0,1]\), define

\begin{aligned} \max_{\alpha,\rho,\xi}\quad &\rho-\frac{1}{\nu n}\sum_{i=1}^n\xi_i\\ \text{subject to}\quad &\sum_j\alpha_jA_{ij}\geq\rho-\xi_i,\qquad i=1,\ldots,n,\\ &\sum_j\alpha_j=1,\qquad \alpha_j\geq0,\qquad \xi_i\geq0. \end{aligned}

The dual keeps the same edge constraints but adds the upper bound \(D_i\leq1/(\nu n)\). To derive it, write each margin constraint as \(\rho-\xi_i-\sum_j\alpha_jA_{ij}\leq0\), with multiplier \(D_i\geq0\). The Lagrangian includes the terms \(\rho(1-\sum_iD_i)\) and \(\xi_i(D_i-1/(\nu n))\). A finite supremum over unrestricted \(\rho\) requires \(\sum_iD_i=1\); a finite supremum over \(\xi_i\geq0\) requires \(D_i\leq1/(\nu n)\). As before, the coefficients of \(\alpha_j\geq0\) require each weighted edge to be at most the dual objective. LP duality then gives the soft-margin dual:

\min_{D,\gamma}\ \gamma \quad\text{subject to}\quad \sum_iD_iA_{ij}\leq\gamma\ (j=1,\ldots,M),\quad \sum_iD_i=1,\quad 0\leq D_i\leq\frac{1}{\nu n}.

The cap prevents the dual from placing too much mass on one example. The parameter \(\nu\) changes that cap; it is not a guarantee that a particular fraction of examples will be misclassified.

Worked Example: A Soft-Margin Cap Changes the Dual Weights

Use the two-rule matrix from the preceding example and set \(n=3\), \(\nu=3/4\). The cap is \(1/(\nu n)=4/9\). The edge expressions are \(2D_2-1\) and \(2D_3-1\). Since \(D_1\leq4/9\), we must have \(D_2+D_3\geq5/9\). The largest of \(D_2,D_3\) is therefore at least \(5/18\), so the largest edge is at least \(2(5/18)-1=-4/9\). Taking \(D=(4/9,5/18,5/18)\) makes both edges exactly \(-4/9\), proving the dual optimum is \(-4/9\).

For a matching primal solution, take \(\alpha_1=\alpha_2=1/2\). The margins are \((-1,0,0)\). Set \(\rho=0\) and \(\xi=(1,0,0)\). The objective is \(0-(4/9)(1)=-4/9\), so this feasible solution attains the dual value. The weight cap has changed the dual certificate from the all-on-one-example distribution to a distribution that shares weight across all three examples.

What the Optimization Does—and Does Not—Say

LPBoost’s primal and dual explain complementary features of the same fit. A primal solution describes how the weak rules combine; its objective is the smallest empirical margin, or a slack-penalized version of that quantity. A dual solution describes a distribution on the sample under which every rule has bounded weighted edge. Equal optimal values let either solution certify the other side’s limit.

This is an empirical optimization statement. A large training margin, or a particular dual reweighting, does not by itself establish a population-level error bound. Generalization claims require their own conditions and arguments, such as those used in margin bounds. The LP identifies an optimal mixture and a matching sample-based certificate; it does not replace those arguments.

Common mistake: “The dual puts weight on difficult examples, so its objective is the error of the final boosted classifier.” This is incorrect. The dual objective is the largest weighted edge among the available individual weak rules, not the error of the primal mixture. For binary rules, each individual edge is \(1-2\) times its weighted error; the dual minimizes the best rule’s edge. The primal mixture’s margins are a different quantity, although strong duality makes the two optimization problems’ optimal values equal.

Key takeaway: The primal maximizes the minimum margin of a convex combination of weak rules. The dual finds example weights that minimize the strongest rule’s weighted edge. These are equal-value views of one linear program, not interchangeable descriptions of an individual classifier’s error.

Check Your Understanding

Check that you can move between the mixture and reweighting interpretations.

Why must the primal mixture coefficients be nonnegative and sum to one for this formulation?
For a fixed distribution \(D\), express a weak rule’s weighted edge in terms of its weighted error.
What does the inequality \(\rho^*\leq\gamma^*\) say, and how does strong duality complete the equality?
In the soft-margin dual, what role does the upper bound on each \(D_i\) play?
Why does equality of the primal and dual optima not mean that the dual objective is the training error of the primal mixture?