Skip to content

Sequential minimal optimisation

SMO trains a support vector machine by solving constrained two-multiplier subproblems. A checked example shows why a single-coordinate update cannot move.

Sequential minimal optimisation (SMO) is an algorithm for training a support vector machine by repeatedly optimising two dual multipliers while holding the others fixed. It makes each inner optimisation small enough to solve analytically. For a quant fitting a classifier to financial features, SMO concerns how the chosen SVM is fitted; it does not introduce a new classifier or establish whether its signal predicts future returns. Fan, Chen and Lin describe this two-variable decomposition in Algorithm 1.

The constraint that makes two the minimum

Consider binary labels yi∈{−1,+1}y_i\in\{-1,+1\}, a free, unpenalised intercept bb, and the soft-margin objective
min⁡w,b  12∥w∥2+C∑i=1nmax⁡{0,1−yi(w⊤ϕ(xi)+b)}.\min_{w,b}\;\frac12\lVert w\rVert^2+ C\sum_{i=1}^{n}\max\{0,1-y_i(w^\top\phi(x_i)+b)\}.
Here C>0C>0 multiplies the sum, not the average, of hinge losses. The equivalent slack-variable formulation has ξi≥0\xi_i\ge0 and yif(xi)≥1−ξiy_i f(x_i)\ge1-\xi_i. With Kij=ϕ(xi)⊤ϕ(xj)K_{ij}=\phi(x_i)^\top\phi(x_j), its dual is the quadratic programme
max⁡αW(α)=∑iαi−12∑i,jαiαjyiyjKij,subject to0≤αi≤C,∑iyiαi=0.\begin{aligned} \max_\alpha\quad W(\alpha) &=\sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_jK_{ij},\\ \text{subject to}\quad &0\le\alpha_i\le C,\qquad\sum_i y_i\alpha_i=0. \end{aligned}
These are the C-SVC conventions in LIBSVM §2.1. Replacing the loss sum with its average while retaining the same numerical CC changes the problem: the equivalent average-loss coefficient is nCnC.

The equality comes from stationarity of the Lagrangian in bb. At a feasible point, changing only αi\alpha_i by Δαi\Delta\alpha_i requires yiΔαi=0y_i\Delta\alpha_i=0. Since yiy_i is nonzero, the only feasible change is zero.

Free a second multiplier and the permissible changes instead satisfy

yiΔαi+yjΔαj=0.y_i\Delta\alpha_i+y_j\Delta\alpha_j=0.
The two box constraints cut this line down to a segment. SMO maximises the restricted quadratic along that segment. The remaining training observations still contribute to the subproblem; this is not an SVM trained on just two observations. Fixing or penalising the intercept changes the dual constraints, so the single-coordinate obstruction above belongs to the stated free-intercept formulation. The general pair subproblem appears in Fan et al., §1.

A complete pair step

Take two fictional, dimensionless feature vectors with a linear kernel:

x1=(1,0),y1=+1,x2=(0,1),y2=−1,C=2.x_1=(1,0),\quad y_1=+1,\qquad x_2=(0,1),\quad y_2=-1,\qquad C=2.

The equality is α1−α2=0\alpha_1-\alpha_2=0. Writing both multipliers as aa gives 0≤a≤20\le a\le2 and

W(a,a)=2a−a2=1−(a−1)2.W(a,a)=2a-a^2=1-(a-1)^2.

Starting from (0,0)(0,0), the exact pair optimum is (1,1)(1,1), with dual value 11. The endpoints (0,0)(0,0) and (2,2)(2,2) both have value 00. A move from (0,0)(0,0) to (1,0)(1,0) would improve the unconstrained objective, but violates the equality.

Fictional two-observation SVM with C equal to 2. Feasible multipliers lie on alpha 1 equals alpha 2 inside the square from 0 to 2. Along this line the dual value 2a minus a squared peaks at a equal to 1 with value 1.
Fictional two-observation SVM with C equal to 2. Feasible multipliers lie on alpha 1 equals alpha 2 inside the square from 0 to 2. Along this line the dual value 2a minus a squared peaks at a equal to 1 with value 1.
Original deterministic example. The left panel shows the feasible pair; the right shows the objective restricted to that pair. A horizontal single-coordinate move leaves the feasible line.

Recover the primal quantities:

w=∑iαiyixi=(1,−1),b=0.w=\sum_i\alpha_i y_i x_i=(1,-1),\qquad b=0.
Both multipliers lie strictly between 00 and CC, so both functional margins must equal one. Indeed, y1f(x1)=y2f(x2)=1y_1f(x_1)=y_2f(x_2)=1. The two slack variables are zero, and the primal objective is 12(12+(−1)2)=1\tfrac12(1^2+(-1)^2)=1, matching the dual. These are functional margins; each point's geometric distance to the boundary is 1/21/\sqrt2. A soft-margin model can have zero slack on a separable example.

What the training loop adds

With f(x)=∑kαkykK(xk,x)+bf(x)=\sum_k\alpha_k y_kK(x_k,x)+b and Ei=f(xi)−yiE_i=f(x_i)-y_i, use

η=Kii+Kjj−2Kij.\eta=K_{ii}+K_{jj}-2K_{ij}.

When η>0\eta>0, the pair step is

αjnew=clip⁡[L,H](αj+yj(Ei−Ej)η),αinew=αi+yiyj(αj−αjnew).\begin{aligned} \alpha_j^{\text{new}} &=\operatorname{clip}_{[L,H]} \left(\alpha_j+\frac{y_j(E_i-E_j)}{\eta}\right),\\ \alpha_i^{\text{new}} &=\alpha_i+y_i y_j(\alpha_j-\alpha_j^{\text{new}}). \end{aligned}
The interval [L,H][L,H] enforces both boxes and the equality. Here E1=−1E_1=-1, E2=1E_2=1, η=2\eta=2 and [L,H]=[0,2][L,H]=[0,2], yielding α2new=1\alpha_2^{\text{new}}=1. Reversing eta's sign requires changing the update. Zero curvature can occur with valid kernels; Platt compares endpoints instead of dividing by zero. Platt, §2.1.

The loop must also:

  • Choose a useful pair. Platt prioritises KKT violators and non-bound multipliers, choosing partners through error differences and fallback searches.
  • Update the intercept. For the +b+b convention, binew=b−Ei−yiΔαiKii−yjΔαjKijb_i^{\text{new}}=b-E_i-y_i\Delta\alpha_iK_{ii}-y_j\Delta\alpha_jK_{ij} enforces f(xi)=yif(x_i)=y_i. Use an interior multiplier's candidate, or their mean if neither is interior.
  • Refresh errors and repeat. Stop at the chosen KKT tolerance. Platt, §§2.2–2.5.

The Karush–Kuhn–Tucker conditions require, at an optimum,

{yif(xi)≥1,αi=0,yif(xi)=1,0<αi<C,yif(xi)≤1,αi=C.\begin{cases} y_i f(x_i)\ge1,&\alpha_i=0,\\ y_i f(x_i)=1,&0<\alpha_i<C,\\ y_i f(x_i)\le1,&\alpha_i=C. \end{cases}
A boundary point can have margin exactly one; these implications do not make margin one exclusive to interior multipliers. LIBSVM §4.1 discusses stopping criteria and intercept recovery.
Kernel evaluations and repeated scans can dominate runtime even though the pair solve is cheap. LIBSVM caches recently used kernel columns rather than requiring the entire dense matrix in memory. Its SMO-type solver uses later working-set selection methods, so it should not be identified with every detail of Platt's 1998 heuristic. LIBSVM §§4.1 and 5.2.

A tighter optimisation tolerance improves solution accuracy for the specified training objective. It does not repair future information in the features, choose CC or the kernel, or demonstrate out-of-sample forecasting performance.

For the broader derivation, Soft-Margin SVMs and the SMO Algorithm connects the slack formulation to the dual and pairwise optimisation. The preview is public; the full lesson requires membership.

Sources

Last updated
  • support vector machines
  • optimisation
  • kernel methods
  • smo
Keep connecting the ideas
← Back to the glossaryBack to top ↑