<figure><img src="image_1.png" /></figure>

HAL
open science

# Support Vector Machines

Yoann Pull

► To cite this version:

Yoann Pull. Support Vector Machines. Master. Support Vector Machines, France. 2025, pp.30.
hal-05331339

HAL Id: hal-05331339

https://hal.science/hal-05331339v1

Submitted on 25 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Support Vector Machines

Geometry, Convex Optimization, and Kernels

Yoann Pull

Laboratoire d'Economie d'Orléans
Square Research Center

Version: October 23, 2025
## About this course

This course is taught as part of the **ESA Master's programme** at the University of Orléans.
It is intended for Master's-level students with prerequisite knowledge of basic statistical learning, functional analysis, linear algebra, and optimization. Certain sections involve more advanced mathematics; supplementary resources are indicated throughout the text.

**Contact** — For typos, errors or suggestions, please write to yoann pull pro@gmail.com.

**Figure code** — The code used to generate the figures is available on GitHub:
https://github.com/YoannPull/svmCourses.

<figure><img src="image_3.png" /></figure>

### Technical section.

Sections prefixed with this pictogram are more technical. At the end of these sections, a box entitled "Further reading" provides additional references.

**References** The main references used to write this course are:

- Bishop (2006)

- Hastie et al. (2009)

- Boyd and Vandenberghe (2004)

- Hurlin (2025)

**Selected application studies** Selection of SVM/SVR Applications in Risk Management and other fields

- **Risk Management.** (Baesens et al., 2003; Loterman et al., 2012; Tobback et al., 2014; Yao et al., 2015, 2017)

- **Text categorisation.** (Joachims, 1998)

- **Bioinformatics.** (Guyon et al., 2002)

- **Remote sensing.** (Mela gani and Bruzzone, 2004)

- **Computer vision.** (Osuna et al., 1997)
# Contents

1 A brief history of SVMs and linear classifiers 4

2 Euclidean geometry essentials 4

2.1 Euclidean space, inner product and norm 4

2.2 Classical inequalities 5

2.3 Affine subspaces, hyperplanes, and normal vectors 5

2.4 Projections: scalar and vector 5

2.5 Point-hyperplane distances (signed and unsigned) 6

3 Rosenblatt's Perceptron 6

3.1 Losses and perceptron formulation 7

3.2 Algorithm and convergence 8

3.3 Limitations 9

4 Support Vector Classifier (Hard-Margin) 9

4.1 Large-margin principle and hard-margin SVC formulation 9

4.2 Primal formulation, dual derivation (hard-margin) 11

5 Support Vector Classifier (Soft-Margin) 13

5.1 From max M to soft-margin: intuition and convexity 13

5.2 Primal formulation, dual derivation (soft-margin) 15

6 Support Vector Machine (SVM): Kernel Trick 16

6.1 Intuition and examples of kernels 17

6.2 Formalization of the kernel trick 19

7 Practical Aspects and Extensions of SVMs 20

7.1 Probabilistic outputs: from margin to probability 20

7.2 Multiclass SVMs 21

7.3 Least-Squares SVM 21

7.4 Support Vector Regression 22

7.5 Modelling: practical principles and hyperparameter tuning 24
# 1 A brief history of SVMs and linear classifiers

The first milestone goes back to the **Perceptron** of Rosenblatt (1958), an iterative algorithm that updates the model parameters through successive corrections. Soon after, Novikoff (1962) established its convergence under the assumption of linear separability, thereby providing the first theoretical framework for linear classifiers.

In the 1960s and 1970s, Vapnik (1998) (with Chervonenkis) shifted the core question: rather than explaining *how* to learn, they investigated *when* learning generalizes. With the VC dimension and the principle of *Structural Risk Minimization* (SRM), they provided a compass: controlling model complexity to ensure out-of-sample performance. This shift—from weight updates to generalization bounds—paved the way for a method that is both geometrically and statistically grounded.

In the early 1990s, the modern version of Support Vector Machines took shape. Boser et al. (1992) formulated margin maximization as a convex quadratic program and made nonlinear boundaries natural through the *kernel trick*—already sketched by Aizerman et al. (1964)—which replaces explicit feature projections with implicit inner products. Cortes and Vapnik (1995) extended the approach to non-separable cases with the *soft margin* (parameter C) and the *hinge loss*, balancing error tolerance with model complexity control.

On the theoretical side, the anchoring in Reproducing Kernel Hilbert Spaces (RKHS) and the *representer theorem* (Kimeldorf and Wahba, 1971; Schölkopf and Smola, 2002) explain why the optimal solution can be written as a linear combination of kernels centered on only a few observations: the *support vectors*. In short, the field moved from a local update rule (Perceptron) to a global optimization principle (SVM) that unites geometry, regularization, and statistical foundations of generalization.

# 2 Euclidean geometry essentials

Before introducing SVMs, we fix the notation and recall a few tools from vector geometry used throughout the course.

## 2.1 Euclidean space, inner product and norm

**Definition 2.1** (Euclidean space). A Euclidean space is a finite-dimensional real vector space $E$ endowed with an inner product $\langle \cdot, \cdot \rangle : E \times E \to \mathbb{R}$ that is symmetric, bilinear, and positive definite. The associated norm is $\|x\| = \sqrt{\langle x, x \rangle}$ and the distance is $\text{dist}(x, y) = \|x - y\|$.

We work in $\mathbb{R}^d$ with the **Euclidean inner product**

$$ \langle x, z \rangle = \sum_{k=1}^{d} x_k z_k, $$

and the associated **Euclidean norm**

$$ \|x\| = \sqrt{\langle x, x \rangle} = \left( \sum_{k=1}^{d} x_k^2 \right)^{1/2}. $$

**Definition 2.2** (Orthogonal and collinear vectors). Two vectors $u, v \in \mathbb{R}^d$ are *orthogonal* if $\langle u, v \rangle = 0$. They are *collinear* if there exists $\lambda \in \mathbb{R}$ such that $u = \lambda v$.

*Remark 2.1* (Pythagoras). If $u \perp v$, then $\|u + v\|^2 = \|u\|^2 + \|v\|^2$. This is the generalization of Pythagoras' theorem.
## 2.2 Classical inequalities

**Theorem 2.1 (Cauchy-Schwarz).** For all $\mathbf{u}, \mathbf{v} \in \mathbb{R}^d$,

$$|\langle \mathbf{u}, \mathbf{v} \rangle| \le \|\mathbf{u}\| \|\mathbf{v}\|,$$

with equality iff $\mathbf{u}$ and $\mathbf{v}$ are collinear.

**Theorem 2.2 (Triangle inequality).** For all $\mathbf{u}, \mathbf{v} \in \mathbb{R}^d$,

$$\|\mathbf{u} + \mathbf{v}\| \le \|\mathbf{u}\| + \|\mathbf{v}\|.$$

Sketch of proof. By expansion, $\|\mathbf{u} + \mathbf{v}\|^2 = \|\mathbf{u}\|^2 + \|\mathbf{v}\|^2 + 2\langle \mathbf{u}, \mathbf{v} \rangle \le (\|\mathbf{u}\| + \|\mathbf{v}\|)^2$ via Cauchy-Schwarz, then take square roots.

**Remark 2.2 (Length of a vector (Pythagoras)).** In the canonical basis, $\|\mathbf{x}\| = \sqrt{x_1^2 + \cdots + x_d^2}$; this is the “length” of $\mathbf{x}$, derived from Pythagoras’ theorem in dimension $d$.

## 2.3 Affine subspaces, hyperplanes, and normal vectors

**Definition 2.3 (Affine subspace).** An affine subspace is a set of the form

$$A = x_0 + V = \{x_0 + v : v \in V\},$$

where $x_0 \in \mathbb{R}^d$ and $V$ is a linear subspace.

**Definition 2.4 (Hyperplane).** A hyperplane in $\mathbb{R}^d$ is an affine subspace of dimension $d-1$, equivalently a set

$$H = \{x \in \mathbb{R}^d : \langle w, x \rangle + b = 0\},$$

where $w \in \mathbb{R}^d \setminus \{0\}$ and $b \in \mathbb{R}$. The vector $w$ is a normal vector to $H$ (orthogonal to every direction in $H$).

**Remark 2.3.** A hyperplane splits the space into two. This property underlies the classification rule used later.

**Definition 2.5 (Normal line to a hyperplane through a point).** Let $H = \{x : \langle w, x \rangle + b = 0\}$ and $x_0 \in \mathbb{R}^d$. The normal line to $H$ passing through $x_0$ is

$$\mathcal{N}(x_0) = \{x(t) = x_0 + t w : t \in \mathbb{R}\}.$$

## 2.4 Projections: scalar and vector

**Definition 2.6 (Scalar projection).** The scalar projection of $v$ onto $u \ne 0$ is

$$\mathrm{comp}_u(v) = \frac{\langle v, u \rangle}{\|u\|}.$$

**Definition 2.7 (Vector projection onto a direction).** The vector projection of $v$ onto the line spanned by $u \ne 0$ is

$$\mathrm{proj}_u(v) = \frac{\langle v, u \rangle}{\|u\|^2} u.$$

**Proposition 2.1 (Orthogonal projection onto a hyperplane).** Let $H = \{x : \langle w, x \rangle + b = 0\}$ with $w \ne 0$ and any $x_0 \in \mathbb{R}^d$. The orthogonal projection $\Pi_H(x_0)$ of $x_0$ onto $H$ is

$$\Pi_H(x_0) = x_0 - \frac{\langle w, x_0 \rangle + b}{\|w\|^2} w.$$

Justification. Subtract from $x_0$ its component along the normal $w$.
## 2.5 Point-hyperplane distances (signed and unsigned)

**Definition 2.8 (Point-hyperplane distance).** The (unsigned) distance from a point $x_0$ to the hyperplane $H = \{x : \langle w, x \rangle + b = 0\}$ is

$$ \mathrm{dist}(x_0, H) = \frac{|\langle w, x_0 \rangle + b|}{\|w\|} $$

**Definition 2.9 (Signed distance).** Fixing the orientation by the normal $w$, the signed distance is

$$ \mathrm{sdist}_w(x_0, H) = \frac{\langle w, x_0 \rangle + b}{\|w\|} $$

It is positive on the side where $\langle w, x \rangle + b > 0$ and negative on the other.

*Remark 2.4 (Distance between two parallel hyperplanes).* If $H_1 = \{x : \langle w, x \rangle + b_1 = 0\}$ and $H_2 = \{x : \langle w, x \rangle + b_2 = 0\}$ with the same normal $w$, then

$$ \mathrm{dist}(H_1, H_2) = \frac{|b_1 - b_2|}{\|w\|} $$

**Proposition 2.2 (Orthogonal decomposition with respect to a hyperplane).** For any $x \in \mathbb{R}^d$,

$$ x = \underbrace{\left(x - \frac{\langle w, x \rangle + b}{\|w\|^2} w\right)}_{\text{projection onto } H} + \underbrace{\frac{\langle w, x \rangle + b}{\|w\|^2} w}_{\text{normal component}} $$

The two components are orthogonal.

## 3 Rosenblatt's Perceptron

We first recall the linear decision rule and the partition of the space induced by a hyperplane, then introduce the perceptron, its loss function, the associated optimization problem, and finally the algorithm with its classical convergence result.

Let

$$ \mathcal{T} = \{(x_1, y_1), \dots, (x_N, y_N)\} $$

be our training data composed of $N$ instances in a space $\mathcal{X} \subseteq \mathbb{R}^d$, such that $\forall i \in \{1, \dots, N\}$, $x_i \in \mathcal{X}$ and $y_i \in \{-1, 1\}$. The goal is to separate $\mathcal{T}$ into two classes using a hyperplane

$$ h(\mathbf{x}) = \langle \mathbf{w}, \mathbf{x} \rangle + b, $$

where $\mathbf{w} \in \mathbb{R}^d$ is a normal vector to the hyperplane and $b \in \mathbb{R}$ is a bias.

This hyperplane induces two half-spaces

$$ H^+ = \{x \in \mathcal{X} : h(x) = \langle w, x \rangle + b \ge 0\}, \quad H^- = \{x \in \mathcal{X} : h(x) = \langle w, x \rangle + b < 0\}, $$

to which we associate classes +1 and -1, respectively; see Figure 1.

**Definition 3.1 (Sign function and decision rule).** Let $h(x) = \langle w, x \rangle + b$ be the equation of a hyperplane in $\mathcal{X}$. Define sign : $\mathbb{R} \to \{-1, 1\}$ by

$$ \mathrm{sign}(t) = \begin{cases} 1, & \text{if } t \ge 0, \\ -1, & \text{if } t < 0. \end{cases} $$

For a new instance $x_{\mathrm{new}}$, the predicted class is

$$ \hat{y} = \mathrm{sign}(h(x_{\mathrm{new}})) = \mathrm{sign}(\langle w, x_{\mathrm{new}} \rangle + b). $$

*Remark.* By convention, points $x$ such that $h(x) = 0$ (on the hyperplane) are assigned to class +1. If one wishes to distinguish this case, use $\mathrm{sign}_0 : \mathbb{R} \to \{-1, 0, 1\}$ with $\mathrm{sign}_0(0) = 0$.
<figure><img src="image_4.png" /><figcaption>Figure 1 – Illustration of a separating hyperplane and the decision rule.</figcaption></figure>

## 3.1 Losses and perceptron formulation

**Guiding idea.** The perceptron seeks a hyperplane that makes all signed margins $m_i = y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b)$ positive. The perceptron loss looks only at misclassified (or on-the-boundary) points and pushes $(\mathbf{w}, b)$ in the direction that fixes the current error.

**Definition 3.2 (Linear score and signed margin).** Given a hyperplane $h(\mathbf{x}) = \langle \mathbf{w}, \mathbf{x} \rangle + b$, the linear score is $h(\mathbf{x})$. For $(\mathbf{x}_i, y_i)$ with $y_i \in \{-1, 1\}$, the signed margin is

$$m_i(\mathbf{w}, b) = y_i h(\mathbf{x}_i) = y_i (\langle \mathbf{w}, \mathbf{x}_i \rangle + b). \quad (3.1)$$

Then $m_i > 0$ means that $\mathbf{x}_i$ is correctly classified, $m_i < 0$ that it is misclassified, and $m_i = 0$ that it lies on the hyperplane.

*Remark 3.1 (Why the product $y_i h(\mathbf{x}_i)$?).* Without the factor $y_i$, the sign of $h(\mathbf{x}_i)$ is interpreted differently across classes. Multiplying by $y_i \in \{-1, 1\}$ unifies the correct-classification condition:

$$(\mathbf{x}_i, y_i) \text{ correctly classified} \iff y_i h(\mathbf{x}_i) > 0.$$

This single expression simplifies modeling and updates.

**Definition 3.3 (Perceptron loss).** The perceptron loss penalizes only the misclassified (or zero-margin) observations:

$$\ell(z) = \max(0, -z), \quad L(\mathbf{w}, b) = \sum_{i=1}^{N} \ell(y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b)) = \sum_{i=1}^{N} \max(0, -y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b)). \quad (3.2)$$

**Proposition 3.1 (Convex optimization problem).** The perceptron solves

$$\min_{\mathbf{w} \in \mathbb{R}^d, b \in \mathbb{R}} L(\mathbf{w}, b) = \min_{\mathbf{w}, b} \sum_{i=1}^{N} \max(0, -y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b)). \quad (3.3)$$

The function $L$ is convex in $(\mathbf{w}, b)$ (a maximum of affine functions), but non-differentiable when $y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b) = 0$.

**Proposition 3.2 (Subgradients).** Writing $h_i = \langle \mathbf{w}, \mathbf{x}_i \rangle + b$ and $\mathcal{M}(\mathbf{w}, b) = \{i : y_i h_i < 0\}$ for the error set, a subgradient of $L$ at $(\mathbf{w}, b)$ is

$$\frac{\partial L(\mathbf{w}, b)}{\partial \mathbf{w}} = - \sum_{i \in \mathcal{M}(\mathbf{w}, b)} y_i \mathbf{x}_i, \quad \frac{\partial L(\mathbf{w}, b)}{\partial b} = - \sum_{i \in \mathcal{M}(\mathbf{w}, b)} y_i. \quad (3.4)$$

At the non-differentiable point $y_i h_i = 0$, any vector between 0 and $-y_i \mathbf{x}_i$ is a valid subgradient for the ith term.
## 3.2 Algorithm and convergence

The perceptron algorithm is an *online* subgradient descent: we loop over examples and update only upon error (or zero margin). The augmented notation folds the bias into the weight vector.

*Remark 3.2 (Augmented variables).* Let

$$ \tilde{x}_i = \begin{pmatrix} x_i \\ 1 \end{pmatrix} \in \mathbb{R}^{d+1}, \quad \tilde{w} = \begin{pmatrix} w \\ b \end{pmatrix} \in \mathbb{R}^{d+1}, $$

so that $h(x_i) = \langle \tilde{w}, \tilde{x}_i \rangle$ and updates can be written compactly.

<caption>**Algorithm 1** Perceptron algorithm (online subgradient descent)</caption>

**Require:** Data $\{(x_i, y_i)\}_{i=1}^N$, step size $\eta > 0$, iterations $T$
1: Initialize $\tilde{w}^{(0)} = 0 \in \mathbb{R}^{d+1}$ ▷ or a small random value
2: **for** $t = 0, 1, \dots, T-1$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 1$ **to** $N$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute $s_i = y_i \langle \tilde{w}^{(t)}, \tilde{x}_i \rangle$
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $s_i \le 0$ **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\tilde{w}^{(t)} \leftarrow \tilde{w}^{(t)} + \eta y_i \tilde{x}_i$
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
8: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
9: **end for**
10: **return** $\tilde{w}^{(T)}$ (hence $w$ and $b$)

**Definition 3.4** (Linearly separable data). A labeled set $\mathcal{T} = \{(x_i, y_i)\}_{i=1}^N$ with $x_i \in \mathbb{R}^d$ and $y_i \in \{-1, 1\}$ is said to be *linearly separable* if there exist $w \in \mathbb{R}^d$ and $b \in \mathbb{R}$ (and, equivalently, a margin $M > 0$ after rescaling $(w, b)$) such that

$$ y_i (\langle w, x_i \rangle + b) \geq M > 0, \quad \forall i = 1, \dots, N. \qquad (3.5) $$

In other words, the two classes are strictly separated by the hyperplane $\{x : \langle w, x \rangle + b = 0\}$.

<figure><img src="image_5.png" /><figcaption>Figure 2 – Visual comparison between separable and non separable cases.</figcaption></figure>

**Theorem 3.1** (Novikoff (1962), mistake bound). Assume $\|x_i\| \le R$ for all $i$ and that the data are linearly separable with geometric margin $M > 0$. Then the perceptron algorithm makes at most $(R/M)^2$ updates (mistakes) and therefore stops in a finite number of steps.
<figure><img src="image_6.png" /><figcaption>Figure 3 – Examples of separating hyperplanes obtained by the perceptron depending on initialization and presentation order: the solution is not unique under separability.</figcaption></figure>

## 3.3 Limitations

The perceptron algorithm nevertheless exhibits several **limitations** (see, e.g., Ripley (1996)):

- **Non-uniqueness under separability.** When the data are separable, there are generally infinitely many separating hyperplanes (see Figure 3). The perceptron may converge to different solutions depending on the initialization and the order of examples.

- **No convergence on non-separable data.** When the data are not linearly separable, the algorithm *does not converge* and may enter *cycles* (oscillating updates), especially in the presence of label noise or outliers.

- **Potentially long convergence time.** Theorem 3.1 shows that the number of perceptron updates is bounded by $(R/M)^2$. Intuitively, the smaller the margin $M$ (points “skimming” the hyperplane), the more corrections may be needed before stabilization. Thus, *the smaller the margin* (data “barely” separable), *the slower the convergence can be*.

We will later see how the initial problem in (3.3) can be modified to address these limitations.

# 4 Support Vector Classifier (Hard-Margin)

In the literature, several names refer to this model: Support Vector Machines with a hard margin (hard-margin SVM), Optimal Separating Hyperplanes (Hastie et al. (2009)), and Support Vector Classifier (SVC) with a hard margin. Hereafter, we refer to this model as the hard-margin SVC. We present the *large-margin* intuition and the logic that naturally leads from the “maximize the margin” problem to the convex formulation “minimize $\frac{1}{2}\|w\|^2$” under separation constraints. We then give the primal problem, its Lagrange dual, the KKT conditions, and the primal-dual equivalence.

## 4.1 Large-margin principle and hard-margin SVC formulation

The perceptron puts each point on the “correct side” of a hyperplane without caring about its distance to the boundary. Yet, as soon as the data are separable, there are infinitely many valid hyperplanes; the solution then depends on initialization and example order, and can be
<figure><img src="image_7.png" /><figcaption>Figure 4 – Geometric margin in a hard-margin SVC: the band delimited by $\langle w, x \rangle + b = \pm 1$ has a margin $M = 1/\|w\|$ and a band width $2/\|w\|$, and the points in contact are the support vectors.</figcaption></figure>

unstable to small perturbations. The large-margin idea is to prefer, among all correct separators, the one that leaves the largest “safety cushion” around the decision boundary.

For a pair $(w, b)$ and an example $(x_i, y_i)$, define

$$ \widehat{M}_i(w, b) := y_i (\langle w, x_i \rangle + b) $$

as the example’s functional margin: it is positive if the example is correctly classified and larger the more comfortably it lies on the correct side. Aggregating via the minimum,

$$ \widehat{M}(w, b) := \min_i \widehat{M}_i(w, b), $$

but this quantity depends on scale, since $(\lambda w, \lambda b)$ describes the same hyperplane while multiplying $\widehat{M}$ by $\lambda > 0$.

We remove the scale dependence by dividing by the norm of the normal vector: the geometric margin

$$ M(w, b) := \min_i \frac{\widehat{M}_i(w, b)}{\|w\|} = \min_i \frac{y_i(\langle w, x_i \rangle + b)}{\|w\|} $$

coincides with the minimal signed distance of the points to the hyperplane and depends only on the geometric position of the boundary. This is the quantity we want to maximize for a robust separator; Figure 4 illustrates this.

Since $(w, b)$ and $(\lambda w, \lambda b)$ represent the same hyperplane, we fix the scale by the canonical normalization

$$ \min_i y_i(\langle w, x_i \rangle + b) = 1. $$

Support vectors satisfy $y_i(\langle w, x_i \rangle + b) = 1$, the margin is $M(w, b) = 1/\|w\|$ and the width of the margin band (between $\langle w, x \rangle + b = \pm 1$) is $2/\|w\|$.

With the canonical normalization above,

$$ \max_{w,b} M(w, b) \iff \max_{w,b} \frac{1}{\|w\|} \quad \text{s.t.} \quad y_i(\langle w, x_i \rangle + b) \ge 1 \quad \forall i. $$

Maximizing $1/\|w\|$ is equivalent to minimizing $\|w\|$, and for analytic convenience we use the convex quadratic objective $\frac{1}{2}\|w\|^2$.
## 4.2 Primal formulation, dual derivation (hard-margin)

Under the canonical normalization $\min_i y_i(\langle w, x_i \rangle + b) = 1$, maximizing the geometric margin amounts to minimizing $\|w\|$. We obtain a convex quadratic program with affine constraints.

**Definition 4.1 (Hard-margin SVM — primal formulation).**

$$ \begin{array}{ll} \min_{w \in \mathbb{R}^d, b \in \mathbb{R}} & \frac{1}{2} \|w\|^2 \\ \text{s.t.} & y_i(\langle w, x_i \rangle + b) \ge 1, \quad i = 1, \dots, N. \end{array} \qquad (4.1) $$

**Comment on the primal.** The objective is strictly convex and the constraints are linear. Under strict separability, there exists at least one primal feasible solution. The direction of $w^*$ is then unique in general position, and the bias $b^*$ follows from the support vectors.

*From primal to dual: construction and dual function.* For each constraint $y_i(\langle w, x_i \rangle + b) \ge 1$, introduce a Lagrange multiplier $\lambda_i \ge 0$. The Lagrangian associated with (4.1) is

$$ \mathcal{L}(w, b, \lambda) = \frac{1}{2} \|w\|^2 - \sum_{i=1}^{N} \lambda_i (y_i(\langle w, x_i \rangle + b) - 1), \quad \text{with } \lambda = (\lambda_1, \dots, \lambda_N)^\top, \lambda_i \ge 0. $$

Define the dual function $g(\lambda)$ as the infimum of $\mathcal{L}$ with respect to the primal variables:

$$ g(\lambda) = \inf_{w \in \mathbb{R}^d, b \in \mathbb{R}} \mathcal{L}(w, b, \lambda). $$

Minimize first over $w$. The term in $w$ is

$$ \frac{1}{2} \|w\|^2 - \langle w, \sum_{i=1}^{N} \lambda_i y_i x_i \rangle, $$

a strictly convex quadratic form in $w$. Its unique minimizer is given by the first-order condition

$$ \frac{\partial \mathcal{L}}{\partial w} = 0 \quad \Rightarrow \quad w^* = \sum_{i=1}^{N} \lambda_i y_i x_i. $$

Replacing $w$ with $w^*$, the contribution in $w$ becomes

$$ \frac{1}{2} \|w^*\|^2 - \langle w^*, \sum_{i=1}^{N} \lambda_i y_i x_i \rangle = \frac{1}{2} \|w^*\|^2 - \|w^*\|^2 = -\frac{1}{2} \|w^*\|^2 = -\frac{1}{2} \left\| \sum_{i=1}^{N} \lambda_i y_i x_i \right\|^2. $$

Next minimize over $b$. The Lagrangian is affine in $b$ via the term $-b \sum_{i=1}^{N} \lambda_i y_i$. If $\sum_i \lambda_i y_i \neq 0$, the infimum in $b$ is $-\infty$. To make $g(\lambda)$ finite, we therefore impose the dual equality constraint

$$ \sum_{i=1}^{N} \lambda_i y_i = 0. $$

In that case the dependence on $b$ vanishes, yielding

$$ g(\lambda) = -\frac{1}{2} \left\| \sum_{i=1}^{N} \lambda_i y_i x_i \right\|^2 + \sum_{i=1}^{N} \lambda_i. $$

Expanding the squared norm gives the classical bilinear form

$$ g(\lambda) = \sum_{i=1}^{N} \lambda_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_i \lambda_j y_i y_j \langle x_i, x_j \rangle. $$
**Proposition 4.1** (Hard-margin SVM — dual formulation).

$$
\begin{equation} \tag{4.2}
\begin{aligned}
\max_{\lambda \in \mathbb{R}^N} & \quad \sum_{i=1}^{N} \lambda_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_i \lambda_j y_i y_j \langle \mathbf{x}_i, \mathbf{x}_j \rangle \\
\text{s.t.} & \quad \lambda_i \ge 0, \quad i = 1, \dots, N, \\
& \quad \sum_{i=1}^{N} \lambda_i y_i = 0.
\end{aligned}
\end{equation}
$$

**Comment on the dual.** The dual is a concave quadratic program over a polyhedron (cone $\lambda_i \ge 0$ and hyperplane $\sum_i \lambda_i y_i = 0$). At the optimum, the coefficients $\lambda_i^*$ are zero for points that do not influence the boundary and strictly positive for points that “support” the hyperplane—hence the term *support vectors*.

**Proposition 4.2** (Slater's condition for the hard-margin SVC). Assume the data are linearly separable, i.e., there exists ($\mathbf{w}_0, b_0$) such that

$$y_i(\langle \mathbf{w}_0, \mathbf{x}_i \rangle + b_0) > 0, \quad i = 1, \dots, N.$$

Then there exists ($\mathbf{w}, b$) such that

$$y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b) > 1, \quad i = 1, \dots, N.$$

In particular, for the primal problem (4.1), Slater's condition holds. Since the problem is convex with affine constraints, strong duality holds: the optimal primal value matches the optimal dual value, and the KKT conditions characterize optimality.

*Sketch of proof.* By separability, define $m := \min_i y_i(\langle \mathbf{w}_0, \mathbf{x}_i \rangle + b_0) > 0$. For any $c > 1/m$, set $\mathbf{w} = c \mathbf{w}_0$ and $b = c b_0$. Then, for all $i$,

$$y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b) = c y_i(\langle \mathbf{w}_0, \mathbf{x}_i \rangle + b_0) \ge cm > 1.$$

We have thus exhibited a strictly feasible primal point. By Slater's condition (for affine inequalities in a convex problem), strong duality follows and the KKT conditions are necessary and sufficient. □

**Definition 4.2** (Karush-Kuhn-Tucker (KKT) conditions). In a convex problem satisfying Slater's condition, a triplet ($\mathbf{w}^*, b^*, \lambda^*$) is optimal iff the following four families of conditions hold:

1. *Primal feasibility:* for all $i$, $y_i(\langle \mathbf{w}^*, \mathbf{x}_i \rangle + b^*) \ge 1$.

2. *Dual feasibility:* for all $i$, $\lambda_i^* \ge 0$, and $\sum_{i=1}^N \lambda_i^* y_i = 0$.

3. *Stationarity:* $\mathbf{w}^* = \sum_{i=1}^N \lambda_i^* y_i \mathbf{x}_i$. The condition $\sum_i \lambda_i^* y_i = 0$ comes from minimization with respect to $b$.

4. *Complementary slackness:* for all $i$,

$$\lambda_i^* (y_i(\langle \mathbf{w}^*, \mathbf{x}_i \rangle + b^*) - 1) = 0.$$

Complementary slackness reads constraint-by-constraint. For a given index $i$, the product of the multiplier $\lambda_i^*$ and the “at-threshold” functional margin $y_i(\langle \mathbf{w}^*, \mathbf{x}_i \rangle + b^*) - 1$ is zero. Two exclusive cases occur.

— If $y_i(\langle \mathbf{w}^*, \mathbf{x}_i \rangle + b^*) > 1$, then $\lambda_i^* = 0$. Point $i$ lies strictly outside the margin band; it does not contribute to $\mathbf{w}^*$ in the decomposition $\mathbf{w}^* = \sum_j \lambda_j^* y_j \mathbf{x}_j$.
— If $y_i(\langle \mathbf{w}^*, \mathbf{x}_i \rangle + b^*) = 1$, the constraint is active; typically $\lambda_i^* > 0$. Point $i$ is on the margin: a support vector. Only these active points determine $\mathbf{w}^*$.

*Reconstructing the classifier from the dual.* Once optimal $\mathbf{\lambda}^*$ are computed, reconstruct the normal $\mathbf{w}^* = \sum_i \lambda_i^* y_i \mathbf{x}_i$. To determine the bias, use any point $k$ such that $\lambda_k^* > 0$<fnref n="1" /> (hence $y_k(\langle \mathbf{w}^*, \mathbf{x}_k \rangle + b^*) = 1$) and set

$$b^* = y_k - \langle \mathbf{w}^*, \mathbf{x}_k \rangle.$$

In practice, average this value over several support vectors to reduce numerical noise.

*Primal-dual equality and optimal value.* Under Slater's condition, the duality gap is zero. The optimal primal value equals the optimal dual value. In particular,

$$\frac{1}{2} \|\mathbf{w}^*\|^2 = \sum_{i=1}^{N} \lambda_i^* - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_i^* \lambda_j^* y_i y_j \langle \mathbf{x}_i, \mathbf{x}_j \rangle.$$

*Further reading.* For the basics of convex duality, Slater's condition, and KKT, see for instance Boyd and Vandenberghe (2004).

# 5 Support Vector Classifier (Soft-Margin)

The hard-margin model assumes perfect separability: all observations can be held at distance at least $1/\|\mathbf{w}\|$ from the hyperplane. In many real-world situations, the data are only almost separable*: there is noise, a few outliers, and sometimes slightly overlapping classes. It is then desirable to allow controlled violations of the margin rather than forcing an unrealistic separation.

## 5.1 From $\max M$ to soft-margin: intuition and convexity

Starting point. In the hard-margin case, we pose the problem directly as a maximization of the geometric margin $M$, fixing the scale with $\|\mathbf{w}\| = 1$ (unit normal):

$$\max_{\mathbf{w},b,M} M \quad \text{s.t.} \quad y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b) \geq M, \quad i = 1, \dots, N, \quad \|\mathbf{w}\| = 1.$$

This means: with a unit normal, the quantity $y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b)$ is exactly the signed distance from $\mathbf{x}_i$ to the hyperplane, and $M$ is the smallest of these distances.

Almost separable” case. When classes overlap or noise is present, we keep the idea “maximize $M$” but allow controlled violations via slack variables $\xi_i \ge 0$ (one per point), see Figure 5, while penalizing their sum. Two natural ways to relax the margin constraint exist. *Additive slack.*

Allow an *absolute deficit* $\xi_i$ relative to the target $M$:

$$y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b) \geq M - \xi_i, \quad \xi_i \geq 0, \quad \max_{i} M - \alpha \sum_{i} \xi_i, \quad \|\mathbf{w}\| = 1.$$

Intuition: $\xi_i$ is expressed “in meters” (same unit as $M$), so each point may encroach by some *distance* on the global margin. Non-convexity. To see the issue, eliminate $M$ by working at free scale. Let

$$\tilde{\mathbf{w}} = \frac{\mathbf{w}}{M}, \quad \tilde{b} = \frac{b}{M}, \quad \tilde{\xi}_i = \frac{\xi_i}{M} \quad (M > 0).$$

The constraint becomes

$$y_i(\langle \tilde{\mathbf{w}}, \mathbf{x}_i \rangle + \tilde{b}) \geq 1 - \tilde{\xi}_i,$$

which is *affine* in $(\tilde{\mathbf{w}}, \tilde{b}, \tilde{\xi})$. However, the objective rewrites as

$$M - \alpha \sum_{i} \xi_i = \frac{1}{\|\tilde{\mathbf{w}}\|} - \alpha \sum_{i} \frac{\tilde{\xi}_i}{\|\tilde{\mathbf{w}}\|} = \frac{1 - \alpha \sum_{i} \tilde{\xi}_i}{\|\tilde{\mathbf{w}}\|},$$

<footnote n="1">1. The attentive reader will note that $k$ is therefore a support vector</footnote>
<figure><img src="image_8.png" /><figcaption>Figure 5 – Soft-margin with slack variables $\xi_i$: $0 < \xi_i < 1$ for a point inside the band but correctly classified, $\xi_i \ge 1$ for a misclassified point.</figcaption></figure>

which couples $\tilde{w}$ and $\tilde{\xi}$ nonlinearly (a ratio linear/||$\tilde{w}$||). This is neither concave (for maximization) nor easily convexified: the problem is non-convex. This is the difficulty noted in Hastie et al. (2009) for the “additive” choice.

*Multiplicative slack.* Require each point to meet a fraction $(1 - \xi_i)$ of the global margin:

$$y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b) \geq M(1 - \xi_i), \quad \xi_i \geq 0, \quad \max M - \alpha \sum_i \xi_i, \quad \|\mathbf{w}\| = 1.$$

Intuition: $\xi_i$ is a percentage of “tolerance”; e.g., $\xi_i = 0.1$ allows point $i$ to lie at 90% of the target margin. Towards a convex form. Divide again by $M$ and set

$$\tilde{w} = \frac{w}{M}, \quad \tilde{b} = \frac{b}{M}.$$

We obtain the same affine constraint as above:

$$y_i(\langle \tilde{w}, \mathbf{x}_i \rangle + \tilde{b}) \geq 1 - \xi_i,$$

but now $\xi_i$ is not rescaled. Moreover, $\|\mathbf{w}\| = 1$ implies $M = 1/\|\tilde{w}\|$, so maximizing $M - \alpha \sum_i \xi_i$ amounts to maximizing

$$\frac{1}{\|\tilde{w}\|} - \alpha \sum_i \xi_i.$$

Rather than maximizing $1/\|\tilde{w}\|$ (non-convex), we adopt the convex quadratic objective $\frac{1}{2}\|\tilde{w}\|^2$, which is monotone with respect to $1/\|\tilde{w}\|$ (these criteria rank solutions the same way after choosing a parameter). This leads to the standard SVC:

$$\min_{\mathbf{w},b,\xi \ge 0} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^{N} \xi_i \quad \text{s.t.} \quad y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b) \ge 1 - \xi_i, \quad i = 1, \dots, N. \quad (5.1)$$

Here everything is convex: a strictly convex quadratic objective in $\mathbf{w}$, affine constraints, domain $\xi_i \ge 0$. The parameter $C > 0$ plays the same role as $\alpha$ after rescaling and controls the trade-off between margin width and the amount of violations.

Geometric reading. With the constraint $y_i(\langle \mathbf{w}, \mathbf{x}_i \rangle + b) \ge 1 - \xi_i$, we recover the same margin band as in the hard-margin case: $H_{\pm}: \langle \mathbf{w}, \mathbf{x} \rangle + b = \pm 1$. A point has $\xi_i = 0$ if it is outside the
band (or on ±1); it has 0 < ξᵢ < 1 if it lies inside the band but on the correct side; it has ξᵢ ≥ 1 if it is misclassified. Increasing C reduces violations but shrinks the margin; decreasing C widens the margin but accepts more errors.

## 5.2 Primal formulation, dual derivation (soft-margin)

At the canonical scale (target margin fixed at 1), allowing controlled margin violations introduces slack variables ξᵢ ≥ 0 and penalizes their sum. We obtain a convex quadratic program with affine constraints.

**Definition 5.1 (Soft-margin SVM — primal formulation).**

$$ 
\begin{array}{ll}
\min_{w \in \mathbb{R}^d, b \in \mathbb{R}, \xi \in \mathbb{R}_+^N} & \frac{1}{2} \|w\|^2 + C \sum_{i=1}^N \xi_i \\
\text{s.t.} & y_i(\langle w, x_i \rangle + b) \ge 1 - \xi_i, \quad i = 1, \dots, N, \\
& \xi_i \ge 0, \quad i = 1, \dots, N.
\end{array}
\qquad (5.2) $$

*Remark 5.1 (Comment on the primal).* The objective is strictly convex in $w$; the constraints are linear. The parameter $C > 0$ controls the trade-off between margin width (via $\|w\|$) and total violation (via $\sum_i \xi_i$). Geometrically, $\xi_i = 0$ means a point outside the band (or on the margin), $0 < \xi_i < 1$ a point inside the band but on the correct side, and $\xi_i \ge 1$ a misclassified point.

*From primal to dual: construction and dual function.* For the constraints $y_i(\langle w, x_i \rangle + b) - 1 + \xi_i \ge 0$, introduce multipliers $\lambda_i \ge 0$; for $\xi_i \ge 0$, multipliers $\nu_i \ge 0$. The Lagrangian is

$$ \mathcal{L}(w, b, \xi, \lambda, \nu) = \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{N} \xi_i - \sum_{i=1}^{N} \lambda_i (y_i(\langle w, x_i \rangle + b) - 1 + \xi_i) - \sum_{i=1}^{N} \nu_i \xi_i. $$

The dual function $g(\lambda) = \inf_{w,b,\xi} \mathcal{L}$ follows by minimizing successively:

* In $w$:

$$ \frac{\partial \mathcal{L}}{\partial w} = 0 \implies w^* = \sum_{i=1}^{N} \lambda_i y_i x_i, \quad \inf_w \left( \frac{1}{2} \|w\|^2 - \langle w, \sum_i \lambda_i y_i x_i \rangle \right) = -\frac{1}{2} \left\| \sum_i \lambda_i y_i x_i \right\|^2. $$

* In $b$:

$$ \frac{\partial \mathcal{L}}{\partial b} = - \sum_{i=1}^{N} \lambda_i y_i = 0 \implies \sum_{i=1}^{N} \lambda_i y_i = 0, $$

otherwise the infimum in $b$ equals $-\infty$.

* In $\xi_i$:

$$ \frac{\partial \mathcal{L}}{\partial \xi_i} = C - \lambda_i - \nu_i = 0 \implies \nu_i = C - \lambda_i \quad (\ge 0) \implies \boxed{0 \le \lambda_i \le C}. $$

The dependence on $\xi$ then disappears. We obtain

$$ g(\lambda) = \sum_{i=1}^{N} \lambda_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_i \lambda_j y_i y_j \langle x_i, x_j \rangle, $$

valid under $\sum_i \lambda_i y_i = 0$ and $0 \le \lambda_i \le C$.

**Proposition 5.1 (Soft-margin SVM — dual formulation).**

$$ 
\begin{array}{ll}
\max_{\lambda \in \mathbb{R}^N} & \displaystyle \sum_{i=1}^{N} \lambda_i - \frac{1}{2} \lambda^\top (YKY) \lambda \\
\text{s.t.} & 0 \le \lambda_i \le C, \quad i = 1, \dots, N, \\
& y^\top \lambda = 0.
\end{array}
\qquad (5.3) $$
Here $K \in \mathbb{R}^{N \times N}$ is the Gram matrix, $K_{ij} = \langle x_i, x_j \rangle$, and $Y = \text{diag}(y_1, \dots, y_N)$. The dual thus depends on the data only through inner products $\langle x_i, x_j \rangle$—the key structure for the kernel trick. Remark 5.2 (Reading the dual). This is a concave quadratic program over the polyhedron $\{ \lambda : 0 \le \lambda_i \le C, y^\top \lambda = 0 \}$. At the optimum, only a few components $\lambda_i^*$ are nonzero: active indices correspond to support vectors.

**Proposition 5.2** (Slater's condition for the soft-margin SVC). For any dataset, there exists a strictly feasible primal point. For example, $\mathbf{w} = 0$, $b = 0$, $\xi_i = 2$ satisfy $y_i(\langle \mathbf{w}^*, x_i \rangle + b) - 1 + \xi_i = 1 > 0$ and $\xi_i > 0$ for all $i$. Slater's condition is therefore satisfied; strong duality holds and the KKT conditions characterize optimality.

**Definition 5.2** (Karush-Kuhn-Tucker (KKT) conditions — soft margin). A quintuplet $(\mathbf{w}^*, b^*, \xi^*, \lambda^*, \nu^*)$ is optimal iff:

1. Primal feasibility: $y_i(\langle \mathbf{w}^*, x_i \rangle + b^*) \ge 1 - \xi_i^*$ and $\xi_i^* \ge 0$ for all $i$;

2. Dual feasibility: $\lambda_i^* \ge 0$, $\nu_i^* \ge 0$ for all $i$, and $\sum_i \lambda_i^* y_i = 0$;

3. Stationarity: $\mathbf{w}^* = \sum_i \lambda_i^* y_i x_i$ and $C - \lambda_i^* - \nu_i^* = 0$ for all $i$;

4. Complementary slackness: for all $i$,

$$ \lambda_i^*(y_i(\langle \mathbf{w}^*, x_i \rangle + b^*) - 1 + \xi_i^*) = 0, \quad \nu_i^* \xi_i^* = 0. $$

*Interpretation.* If $0 < \lambda_i^* < C$, then $\nu_i^* > 0$ so $\xi_i^* = 0$, and the constraint is active: $y_i(\langle \mathbf{w}^*, x_i \rangle + b^*) = 1$ (a “free” support vector, on the margin). If $\lambda_i^* = C$, then $\nu_i^* = 0$ and $y_i(\langle \mathbf{w}^*, x_i \rangle + b^*) = 1 - \xi_i^* \le 1$ (a “bound” support vector, inside the band or misclassified if $\xi_i^* \ge 1$). If $\lambda_i^* = 0$, then $\nu_i^* = C$ and $\xi_i^* = 0$, hence $y_i(\langle \mathbf{w}^*, x_i \rangle + b^*) \ge 1$ (outside the band, non-support).

*Reconstructing the classifier from the dual.* We have $\mathbf{w}^* = \sum_{i=1}^N \lambda_i^* y_i x_i$. For the bias, choose $k$ such that $0 < \lambda_k^* < C$ (a “free” support) and set

$$ b^* = y_k - \langle \mathbf{w}^*, x_k \rangle, $$

then average over several “free” supports for numerical stability. The decision function is

$$ f(\mathbf{x}) = \text{sign} \left( \sum_{i=1}^{N} \lambda_i^* y_i \langle \mathbf{x}_i, \mathbf{x} \rangle + b^* \right). $$

*Primal-dual equality and optimal value.* Under Slater's condition, the duality gap is zero; in particular,

$$ \frac{1}{2} \|\mathbf{w}^*\|^2 + C \sum_{i=1}^{N} \xi_i^* = \sum_{i=1}^{N} \lambda_i^* - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_i^* \lambda_j^* y_i y_j \langle \mathbf{x}_i, \mathbf{x}_j \rangle. $$

*Further reading.* For convex duality (Slater's condition, KKT), see e.g. Boyd and Vandenberghe (2004). A didactic presentation of the soft-margin SVM (primal/dual, hinge loss) is given by Hastie et al. (2009). For the origin and a more theoretical treatment, see Cortes and Vapnik (1995) and Vapnik (1998).

# 6 Support Vector Machine (SVM): Kernel Trick

Extending the soft-margin SVC to nonlinear decision boundaries consists in replacing the Euclidean inner product $\langle x, x' \rangle$ by a kernel $K(x, x')$ that implicitly induces an embedding $\phi$ into a space (often high- or even infinite-dimensional) where the separation becomes linear again. This idea is supported by Cover (1965): “Projecting data nonlinearly into a higher-dimensional space generally increases the probability of linear separability.” In the feature space, the classifier’s complexity is controlled by the norm of the normal vector (or, in an RKHS, by $\|f\|_{H_K}$), while the parameter $C$ preserves regularization of the margin/violation trade-off. The foundational works of Boser et al. (1992); Cortes and Vapnik (1995) formalized this framework, which we detail below.
## 6.1 Intuition and examples of kernels

*Starting point:* to make a linear separation possible when boundaries are nonlinear in $\mathbb{R}^d$, consider an embedding $\phi: \mathbb{R}^d \to \mathcal{H}$ into a Hilbert space $(\mathcal{H}, \langle \cdot, \cdot \rangle_{\mathcal{H}})$ where the data become (almost) separable. The soft-margin SVC “in $\mathcal{H}$” reads

$$ \min_{w \in \mathcal{H}, b \in \mathbb{R}, \xi \ge 0} \frac{1}{2} \|w\|_{\mathcal{H}}^2 + C \sum_{i=1}^{N} \xi_i \quad \text{s.t.} \quad y_i(\langle w, \phi(\mathbf{x}_i) \rangle_{\mathcal{H}} + b) \ge 1 - \xi_i. $$

Cover (1965) formalizes the intuition: a nonlinear embedding into a higher-dimensional space generally increases the probability of linear separability (Figure 6). However, estimating $w \in \mathcal{H}$ directly quickly becomes impractical: for a Gaussian kernel, $\mathcal{H}$ is infinite-dimensional; even for a polynomial kernel of degree $p$, the embedding dimension (all monomials up to degree $p$) grows combinatorially with $d$. The kernel trick circumvents this difficulty: one never needs to construct $\phi$ nor store $w$ in $\mathcal{H}$, because the SVC dual depends on the data only through inner products of the form

$$ \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle_{\mathcal{H}} =: K(\mathbf{x}_i, \mathbf{x}_j), $$

where $K$ is a kernel function. By replacing every $\langle \mathbf{x}_i, \mathbf{x}_j \rangle$ with $K(\mathbf{x}_i, \mathbf{x}_j)$, the optimization is solved as if we were working linearly in $\mathcal{H}$, without ever computing $\phi$.

<figure><img src="image_9.png" /><figcaption>Figure 6 – Embedding $\mathbb{R}^2$ into $\mathbb{R}^3$</figcaption></figure>

*Informal definition:* a kernel $K: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}$ is a function for which there exist a Hilbert space $\mathcal{H}$ and a feature map $\phi$ satisfying

$$ K(\mathbf{x}, \mathbf{x}') = \langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle_{\mathcal{H}}. $$

The learned decision then takes the form

$$ f(\mathbf{x}) = \text{sign} \left( \sum_{i=1}^{N} \lambda_i^* y_i K(\mathbf{x}_i, \mathbf{x}) + b^* \right), $$

where only the support vectors (indices $i$ with $\lambda_i^* > 0$) appear: neither $w$ nor $\phi(\mathbf{x})$ are explicitly manipulated.

*Some common kernels:*
— Linear: $K(x, x') = \langle x, x' \rangle$ (baseline case, identity $\phi$).

— Polynomial (degree $p$): $K(x, x') = (\langle x, x' \rangle + c)^p, p \in \mathbb{N}, c \ge 0$ (finite embedding: monomials up to degree $p$).

— Gaussian / RBF: $K(x, x') = \exp(-\gamma \|x - x'\|^2), \gamma > 0$ (an infinite-dimensional embedding).

— Sigmoid (neural-network type): $K(x, x') = \tanh(\kappa \langle x, x' \rangle + \theta)$ (p.s.d. only for certain parameter ranges).

Explicit example — quadratic polynomial kernel with $c = 1$ in dimension 2. Let $x = (x_1, x_2)$ and $x' = (x'_1, x'_2) \in \mathbb{R}^2$, and

$$K(x, x') = (\langle x, x' \rangle + 1)^2 = (x_1x'_1 + x_2x'_2 + 1)^2.$$

Expanding,

$$(\langle x, x' \rangle + 1)^2 = (x_1x'_1 + x_2x'_2)^2 + 2(x_1x'_1 + x_2x'_2) + 1 = x_1^2x'_1^2 + 2x_1x_2x'_1x'_2 + x_2^2x'_2^2 + 2x_1x'_1 + 2x_2x'_2 + 1.$$

This can be written as a Euclidean inner product in dimension 6:

$$K(x, x') = \langle \phi(x), \phi(x') \rangle_{\mathbb{R}^6},$$

where a corresponding feature map (one realization of the feature space associated with $K$) is

$$\phi: \mathbb{R}^2 \to \mathbb{R}^6, \quad \phi(x) = (x_1^2, \sqrt{2}x_1x_2, x_2^2, \sqrt{2}x_1, \sqrt{2}x_2, 1).$$

With this normalization, one checks directly that

$$\langle \phi(x), \phi(x') \rangle = x_1^2 x_1'^2 + 2x_1 x_2 x_1' x_2' + x_2^2 x_2'^2 + 2x_1 x_1' + 2x_2 x_2' + 1 = (\langle x, x' \rangle + 1)^2 = K(x, x').$$

Remark 6.1. The feature map $\phi$ is not unique (any orthogonal transformation of $\phi$ also works); what is determined by $K$ is the equivalence class of the feature space (isomorphic to the associated RKHS).

Without the kernel trick, Using a degree-2 polynomial kernel would require estimating a normal vector $w$ in $\mathbb{R}^6$ (and, for higher degrees and/or larger $d$, in a combinatorially explosive dimension); with the kernel, it suffices to evaluate $K(x_i, x_j)$ and to optimize the dual in dimension $N$ via the kernel Gram matrix $K = [K(x_i, x_j)]_{i,j}$.

The preceding reasoning also clarifies the algorithmic choice. In the kernelized primal, the normal vector $w$ lives in $\mathcal{H}$, whose dimension can be huge (even infinite for an RBF): estimating $w$ directly is quickly impractical. Using the Lagrangian, the KKT conditions instead yield the representation

$$w^* = \sum_{i=1}^{N} \lambda_i^* y_i \phi(x_i), \quad 0 \le \lambda_i^* \le C, \quad \sum_{i=1}^{N} \lambda_i^* y_i = 0,$$

and lead to the dual

$$\max_{\lambda \in [0, C]^N} \sum_{i=1}^{N} \lambda_i - \frac{1}{2} \sum_{i,j=1}^{N} \lambda_i \lambda_j y_i y_j \underbrace{\langle \phi(x_i), \phi(x_j) \rangle_{\mathcal{H}}}_{K(x_i, x_j)} \quad \text{s.t.} \quad \sum_{i=1}^{N} \lambda_i y_i = 0.$$

In other words, the entire numerical challenge concentrates in the kernel Gram matrix $K = [K(x_i, x_j)]_{i,j}$: we manipulate only inner products in $\mathcal{H}$, never building $\phi$ nor storing $w$. This is precisely why one prefers the dual: the complexity depends primarily on $N$ (sample size), not on $\dim(\mathcal{H})$, which may blow up in the primal.
## 6.2 Formalization of the kernel trick

**Definition 6.1 (Hilbert space).** A Hilbert space is a real vector space $\mathcal{H}$ endowed with an inner product $\langle \cdot, \cdot \rangle_{\mathcal{H}}$, complete for the induced norm $\|u\|_{\mathcal{H}} = \sqrt{\langle u, u \rangle_{\mathcal{H}}}$. Completeness means that every Cauchy sequence (for the norm) converges in $\mathcal{H}$.

**Definition 6.2 (p.s.d. kernel and RKHS, (Aronszajn, 1950)).** Let $\mathcal{X}$ be a nonempty set. A symmetric function $K: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ is positive semidefinite (p.s.d.) if, for every $n \in \mathbb{N}$ and every choice $(x_1, \dots, x_n) \subset \mathcal{X}$,

$$ \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j K(x_i, x_j) \geq 0 \quad \text{for all } (\alpha_1, \dots, \alpha_n) \in \mathbb{R}^n, $$

i.e., the Gram matrix $K_n = [K(x_i, x_j)]_{i,j}$ is p.s.d. By the Moore-Aronszajn theorem, every p.s.d. kernel $K$ is associated with a reproducing kernel Hilbert space (RKHS) $(\mathcal{H}_K, \langle \cdot, \cdot \rangle_{\mathcal{H}_K})$ and a canonical map

$$ \Phi: \mathcal{X} \to \mathcal{H}_K, \quad \Phi(x) := K_x := K(x, \cdot), $$

such that, for all $x, z \in \mathcal{X}$,

$K(x, z) = \langle \Phi(x), \Phi(z) \rangle_{\mathcal{H}_K}$ and $\forall f \in \mathcal{H}_K, f(x) = \langle f, K_x \rangle_{\mathcal{H}_K}$ (reproducing property).

**Remark 6.2 (Two equivalent views of a kernel).** Saying that $K$ is a p.s.d. kernel is equivalent to (i) the existence of a feature map $\Phi$ into a Hilbert space $(\mathcal{H}_K, \langle \cdot, \cdot \rangle)$ such that $K(x, z) = \langle \Phi(x), \Phi(z) \rangle$, or (ii) every Gram matrix formed with $K$ is p.s.d. The first view is geometric (feature map); the second is algorithmic (well-posed QP in the dual).

**Remark 6.3 (Examples and closure properties).** Common p.s.d. examples: $K_{\text{lin}}(x, z) = \langle x, z \rangle$, $K_{\text{poly}}(x, z) = (\langle x, z \rangle + c)^p$ ($c \geq 0, p \in \mathbb{N}$), $K_{\text{RBF}}(x, z) = \exp(-\gamma \|x - z\|^2)$ ($\gamma > 0$). Closure: if $K_1, K_2$ are p.s.d., then $aK_1 + bK_2$ ($a, b \geq 0$), $K_1 \cdot K_2$, and $x \mapsto \phi(x)^{\top} A \phi'(x)$ with $A \succeq 0$ are also p.s.d. (useful for building domain-adapted kernels).

**Theorem 6.1 (Representer theorem, Kimeldorf and Wahba (1971); Schölkopf and Smola (2002)).** Let $(\mathcal{H}_K, \|\cdot\|_{\mathcal{H}_K})$ be an RKHS, $\Omega: \mathbb{R}_+ \to \mathbb{R}$ a strictly increasing regularizer, and $L: \mathbf{Y} \times \mathbb{R} \to \mathbb{R}_+$ a loss. For

$$ \min_{f \in \mathcal{H}_K} \Omega(\|f\|_{\mathcal{H}_K}) + \sum_{i=1}^{N} L(y_i, f(x_i)), $$

every minimizer admits a finite representation

$$ f^*(\cdot) = \sum_{i=1}^{N} \alpha_i K(x_i, \cdot). $$

*Proof sketch.* Decompose $f = g + h$ with $g \in \text{span}\{K_{x_i}\}_{i=1}^N$ and $h \perp \text{span}\{K_{x_i}\}$. By the reproducing property, $f(x_i) = g(x_i)$ for all $i$; thus the data-fitting term depends only on $g$. Since $\Omega$ is increasing and $\|f\|^2 = \|g\|^2 + \|h\|^2$, keeping $h \neq 0$ never helps: at the optimum $h = 0$, yielding the finite form. $\square$

**Remark 6.4 (Direct connection to the kernelized SVM).** With $\Omega(t) = \frac{1}{2}t^2$ and the hinge loss $L(y, u) = \max(0, 1 - yu)$, one obtains the SVC in RKHS:

$$ \min_{f \in \mathcal{H}_K, b \in \mathbb{R}} \frac{1}{2} \|f\|_{\mathcal{H}_K}^2 + C \sum_{i=1}^{N} \max(0, 1 - y_i(f(x_i) + b)). $$

By **Theorem 6.1**, $f(\cdot) = \sum_i \alpha_i K(x_i, \cdot)$. Introducing slack variables and writing the dual as in the linear case, all inner products $\langle x_i, x_j \rangle$ are replaced by $K(x_i, x_j)$:

$$ \max_{\lambda} \sum_{i=1}^{N} \lambda_i - \frac{1}{2} \sum_{i,j=1}^{N} \lambda_i \lambda_j y_i y_j K(x_i, x_j) \quad \text{s.t.} \quad 0 \le \lambda_i \le C, \sum_i \lambda_i y_i = 0, $$
and the decision function

$$f(x) = \sum_{i=1}^{N} \lambda_{i}^{*} y_{i} K(x_{i}, x) + b^{*}.$$

The kernel thus allows us to operate as if we were linear in a (potentially infinite-)dimensional $\mathcal{H}_K$, without ever making $\Phi$ explicit or estimating $\mathbf{w}$ in that space.

**Remark 6.5** (Role of the RKHS norm and complexity control). In a kernelized SVM, the quantity $\|f\|_{\mathcal{H}_K}$ plays the role of the normal vector norm in feature space: minimizing $\frac{1}{2}\|f\|_{\mathcal{H}_K}^2$ amounts to maximizing the margin in $\mathcal{H}_K$. The parameter $C$ balances this margin against hinge-type violations. This realizes the intuition behind Cover's theorem (improved separability after embedding) while avoiding overfitting via explicit RKHS regularization.

**Remark 6.6** (Why kernelization resolves the infinite-dimensional issue). Attempting to optimize directly over $\mathbf{w} \in \mathcal{H}$ (e.g., with an RBF kernel) would yield an infinite-dimensional decision variable. The dual never exposes $\mathbf{w}$: it manipulates only the kernel Gram matrix $K = [K(x_i, x_j)]$ of size $N \times N$, and the dual coefficients $\lambda_i$. Feasibility and concavity of the dual rely precisely on the p.s.d.-ness of $K$.

*Further reading.* For a clear introduction to the kernel trick and feature maps $\varphi(\cdot)$, see Hastie et al. (2009) and Bishop (2006). For a rigorous presentation via reproducing kernel Hilbert spaces (RKHS), the positive-definiteness axiom, and the representer theorem, see Schölkopf and Smola (2002).

# 7 Practical Aspects and Extensions of SVMs

## 7.1 Probabilistic outputs: from margin to probability

The SVM returns a *margin score*

$$h(\mathbf{x}) = \sum_{i=1}^{N} \lambda_{i}^{*} y_{i} K(\mathbf{x}_{i}, \mathbf{x}) + b^{*} \quad (\text{linear when } K(\mathbf{x}_{i}, \mathbf{x}) = \langle \mathbf{x}_{i}, \mathbf{x} \rangle),$$

which quantifies the signed distance to the decision boundary. This score is well ordered (the larger $h(\mathbf{x})$, the higher the confidence for class +1), but it is *not* a probability. To obtain an estimate of $\mathrm{Pr}(Y = 1 | \mathbf{x})$, one applies a *calibration* to the score.

**Definition 7.1** (Logistic calibration). Use the sigmoid $\sigma(t) = \frac{1}{1 + e^{-t}}$ to transform $h(\mathbf{x})$ into a probability:

$$\mathrm{Pr}(Y = 1 | \mathbf{x}) = \sigma(\theta_1 + \theta_2 h(\mathbf{x})).$$

The “plain sigmoid” case fixes $(\theta_1, \theta_2) = (0, 1)$, i.e. $\mathrm{Pr}(Y = 1 | \mathbf{x}) = \sigma(h(\mathbf{x}))$. In practice, it is preferable to *learn* $(\theta_1, \theta_2)$ by maximum likelihood on a validation set (or via cross-validation), from the pairs $(h(\mathbf{x}_i), t_i)$ with $t_i = \frac{1+y_i}{2} \in \{0, 1\}$:

$$\min_{\theta_1, \theta_2} - \sum_{i=1}^{N} \left[ t_i \log \sigma(\theta_1 + \theta_2 h(\mathbf{x}_i)) + (1 - t_i) \log(1 - \sigma(\theta_1 + \theta_2 h(\mathbf{x}_i))) \right].$$

**Remark 7.1** (Intuition and practice). Very positive margins ($h(\mathbf{x}) \gg 0$) yield probabilities close to 1, very negative margins ($h(\mathbf{x}) \ll 0$) close to 0, and $h(\mathbf{x}) \approx 0$ a probability near 1/2. Estimation of $(\theta_1, \theta_2)$ must be performed *out of sample* to avoid optimism (hold-out or k-fold CV). When the link between $h$ and probability is more complex, a nonparametric alternative is *isotonic calibration* (more flexible but more prone to overfitting). These techniques apply unchanged to kernelized SVMs (only the expression of $h$ changes).
## 7.2 Multiclass SVMs

Many applications involve $K \ge 3$ classes. While the SVM is defined for binary labels $y \in \{-1, +1\}$, multiclass classification is handled effectively via reduction strategies that keep the geometry and regularization of the binary SVMs intact (kernelization applies unchanged). We present the two standard schemes and their practical implications.

**Definition 7.2 (One-vs-Rest (OvR))**. Let $\mathcal{Y} = \{1, \dots, K\}$. For each class $k$, create binary labels

$$y_i^{(k)} = \begin{cases} +1 & \text{if } y_i = k, \\ -1 & \text{otherwise,} \end{cases} \quad i = 1, \dots, N,$$

and train a (linear or kernel) soft-margin SVM

$$f_k(x) = \sum_{i=1}^{N} \lambda_i^{(k)} y_i^{(k)} K(x_i, x) + b^{(k)}.$$

Prediction is by winner-takes-all:

$$\hat{y}(x) = \arg \max_{k \in \{1, \dots, K\}} f_k(x).$$

Class imbalance is inherent (positives are typically $N_k \ll N$): use class weighting and stratified folds within the standard pipeline $\{\text{StandardScaler} \to \text{SVM}\}$.

**Definition 7.3 (One-vs-One (OvO))**. For each ordered pair $(a, b)$ with $1 \le a < b \le K$, train a binary SVM $f_{ab}$ using only samples with $y \in \{a, b\}$ (labels +1 for $a$, -1 for $b$). At prediction time:

- **Majority vote**: each $f_{ab}$ casts one vote for $a$ if $f_{ab}(x) > 0$ and for $b$ otherwise; choose the class with most votes.

- **Margin aggregation (tie-breaker)**: for each class $c$, define

$$S_c(x) = \sum_{\substack{b=1 \\ b \neq c}}^{K} s_{cb}(x), \quad s_{cb}(x) = \begin{cases} f_{cb}(x) & \text{if } c < b, \\ -f_{bc}(x) & \text{if } c > b, \end{cases}$$

then predict $\hat{y}(x) = \arg \max_c S_c(x)$.

Both OvR and OvO accept any kernel from Section 6; the decision functions remain linear combinations of kernels centered at support vectors.

## 7.3 Least-Squares SVM

Least-Squares SVM (LS-SVM) (Suykens and Vandewalle (1999); Suykens et al. (2002)) is a variant of the soft-margin SVM that replaces the *hinge* loss and inequality constraints with a quadratic penalty on margin residuals and equality constraints. The problem remains convex, and training reduces to solving a linear system, with the same kernelization scheme as for standard SVMs.

**Definition 7.4 (LS-SVM — primal formulation (classification))**. Let $(\mathcal{H}, \langle \cdot, \cdot \rangle_{\mathcal{H}})$ be a feature space, $\phi: \mathbb{R}^d \to \mathcal{H}$ a feature map, labels $y_i \in \{-1, 1\}$, and $\gamma > 0$. The LS-SVM primal problem is

$$\min_{w \in \mathcal{H}, b \in \mathbb{R}, \xi \in \mathbb{R}^N} \quad \frac{1}{2} \|w\|_{\mathcal{H}}^2 + \frac{\gamma}{2} \sum_{i=1}^{N} \xi_i^2 \qquad (7.1)$$

$$\text{s.t.} \quad y_i(\langle w, \phi(x_i) \rangle_{\mathcal{H}} + b) = 1 - \xi_i, \quad i = 1, \dots, N.$$
**Remark 7.2 (Comments).** (i) The slack variables $\xi_i$ are not sign-constrained; the penalty is symmetric around the target margin 1. (ii) The objective is strictly convex in $\mathbf{w}$ and the constraints are affine; the problem is a well-posed convex program. (iii) The parameter $\gamma$ controls the trade-off between regularization and fitting the margin residuals.

**Proposition 7.1 (Stationarity conditions and linear system).** *Introduce Lagrange multipliers $\lambda_i \in \mathbb{R}$ for the equalities and the Lagrangian*

$$ \mathcal{L}(\mathbf{w}, b, \xi, \lambda) = \frac{1}{2} \|\mathbf{w}\|_{\mathcal{H}}^2 + \frac{\gamma}{2} \sum_{i=1}^{N} \xi_i^2 - \sum_{i=1}^{N} \lambda_i (y_i(\langle \mathbf{w}, \phi(\mathbf{x}_i) \rangle_{\mathcal{H}} + b) - 1 + \xi_i). $$

Stationarity yields

$$ \begin{align*} \frac{\partial \mathcal{L}}{\partial \mathbf{w}} = 0 &\iff \mathbf{w} = \sum_{i=1}^{N} \lambda_i y_i \phi(\mathbf{x}_i), & \frac{\partial \mathcal{L}}{\partial b} = 0 &\iff \sum_{i=1}^{N} \lambda_i y_i = 0, \\ \frac{\partial \mathcal{L}}{\partial \xi_i} = 0 &\iff \gamma \xi_i - \lambda_i = 0 \quad \text{for all } i \text{ hence } \xi_i = \lambda_i / \gamma. \end{align*} $$

Substituting into the constraints of (7.1) and writing $K(\mathbf{x}_i, \mathbf{x}_j) = \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle_{\mathcal{H}}$ and $\Omega_{ij} = y_i y_j K(\mathbf{x}_i, \mathbf{x}_j)$, we obtain the block system

$$ \begin{bmatrix} 0 & \mathbf{y}^{\top} \\ \mathbf{y} & \Omega + \gamma^{-1} I_N \end{bmatrix} \begin{bmatrix} b \\ \mathbf{\lambda} \end{bmatrix} = \begin{bmatrix} 0 \\ \mathbf{1}_N \end{bmatrix}, \quad \mathbf{y} = (y_1, \dots, y_N)^{\top}, \quad \mathbf{\lambda} = (\lambda_1, \dots, \lambda_N)^{\top}. \quad (7.2) $$

**Definition 7.5 (Decision function).** Let $(b, \lambda)$ solve (7.2). The decision function is

$$ f(\mathbf{x}) = \sum_{i=1}^{N} \lambda_i y_i K(\mathbf{x}_i, \mathbf{x}) + b, \quad \hat{y} = \mathrm{sign}(f(\mathbf{x})). $$

**Proposition 7.2 (Dual formulation).** *Eliminating $(\mathbf{w}, b, \xi)$ in the Lagrangian leads to the dual problem*

$$ \max_{\lambda \in \mathbb{R}^N} \mathbf{1}_N^\top \lambda - \frac{1}{2} \lambda^\top (\Omega + \gamma^{-1} I_N) \lambda \quad \text{s.t.} \quad \mathbf{y}^\top \lambda = 0. $$

**Remark 7.3 (Geometric view, strengths and limitations).** Writing $f(\mathbf{x}_i) = \sum_{j=1}^N \lambda_j y_j K(\mathbf{x}_j, \mathbf{x}_i) + b$, the primal constraints give $\xi_i = 1 - y_i f(\mathbf{x}_i)$. We have $\xi_i \le 0$ for points beyond the margin on the correct side, $0 < \xi_i < 1$ for points inside the margin band but correctly classified, and $\xi_i \ge 1$ for misclassified points. *Strengths:* training reduces to a linear system of size $(N+1) \times (N+1)$; kernelization is identical to the standard SVM. *Limitations:* the solution is typically *dense* (less sparsity), and the quadratic penalty increases sensitivity to *outliers*.

## 7.4 Support Vector Regression

Support Vector Regression (SVR) (Smola and Schölkopf (2004)) seeks to estimate an affine function in feature space, $f(\mathbf{x}) = \langle \mathbf{w}, \phi(\mathbf{x}) \rangle_{\mathcal{H}} + b$, that tolerates deviations up to a threshold $\epsilon > 0$ without penalty ($\epsilon$-insensitive loss). Geometrically, this amounts to fitting a *tube* of width $2\epsilon$ around the predictor (see Figure 7): points inside the tube incur no penalty, whereas points outside give rise to slack variables.

**Definition 7.6 (SVR — primal formulation).** Let $(\mathcal{H}, \langle \cdot, \cdot \rangle_{\mathcal{H}})$ be a feature Hilbert space, $\phi: \mathbb{R}^d \to \mathcal{H}$ an embedding, $(\mathbf{x}_i, y_i) \in \mathbb{R}^d \times \mathbb{R}$ observations, and $C > 0$. The SVR primal problem is

$$ \begin{align} \min_{\mathbf{w} \in \mathcal{H}, b \in \mathbb{R}, \xi_i \in \mathbb{R}_+^N, \xi^* \in \mathbb{R}_+^N} & \frac{1}{2} \|\mathbf{w}\|_{\mathcal{H}}^2 + C \sum_{i=1}^N (\xi_i + \xi_i^*) \nonumber \\ \text{s.t.} & \quad y_i - (\langle \mathbf{w}, \phi(\mathbf{x}_i) \rangle_{\mathcal{H}} + b) \le \epsilon + \xi_i, \quad i = 1, \dots, N, \tag{7.3} \\ & \quad (\langle \mathbf{w}, \phi(\mathbf{x}_i) \rangle_{\mathcal{H}} + b) - y_i \le \epsilon + \xi_i^*, \quad i = 1, \dots, N, \nonumber \\ & \quad \xi_i \ge 0, \quad \xi_i^* \ge 0, \quad i = 1, \dots, N. \nonumber \end{align} $$
<figure><img src="image_10.png" /><figcaption>Figure 7 – SVR and the $\epsilon$-insensitive tube. Estimated curve $f(\boldsymbol{x})$ (solid line), $\epsilon$-tube (purple bands). Points outside the tube generate slack variables $(\xi_i, \xi_i^*)$ and become support vectors of the regression.</figcaption></figure>

**Proposition 7.3** (Stationarity conditions and box constraints). Let $\lambda_i, \lambda_i^* \ge 0$ be the Lagrange multipliers associated with the two families of inequalities in (7.3), and let $\mu_i, \mu_i^* \ge 0$ be those associated with $\xi_i \ge 0$, $\xi_i^* \ge 0$. Writing $K(\boldsymbol{x}_i, \boldsymbol{x}_j) = \langle \phi(\boldsymbol{x}_i), \phi(\boldsymbol{x}_j) \rangle_H$, the Lagrangian stationarity conditions yield

$$ \boldsymbol{w} = \sum_{i=1}^{N} (\lambda_i^* - \lambda_i) \phi(\boldsymbol{x}_i), \quad \sum_{i=1}^{N} (\lambda_i^* - \lambda_i) = 0. $$

We also have $C - \lambda_i - \mu_i = 0$ and $C - \lambda_i^* - \mu_i^* = 0$ for all $i$, with complementarity $\mu_i \xi_i = 0$ and $\mu_i^* \xi_i^* = 0$. It follows that the dual variables satisfy the box bounds

$$ 0 \le \lambda_i \le C, \quad 0 \le \lambda_i^* \le C, \quad i = 1, \dots, N. $$

**Proposition 7.4** (Kernelized dual). Eliminating $(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\xi}^*, \boldsymbol{\mu}, \boldsymbol{\mu}^*)$ from the Lagrangian associated with (7.3) leads to the dual problem

$$ \begin{array}{ll} \max_{\boldsymbol{\lambda}, \boldsymbol{\lambda}^*} & -\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} (\lambda_i - \lambda_i^*)(\lambda_j - \lambda_j^*) K(\boldsymbol{x}_i, \boldsymbol{x}_j) \\ & - \epsilon \sum_{i=1}^{N} (\lambda_i + \lambda_i^*) + \sum_{i=1}^{N} y_i (\lambda_i - \lambda_i^*) \qquad (7.4) \\ \text{s.t.} & \sum_{i=1}^{N} (\lambda_i - \lambda_i^*) = 0, \quad 0 \le \lambda_i, \lambda_i^* \le C, \quad i = 1, \dots, N. \end{array} $$

**Definition 7.7** (Predictor and bias computation). For a solution $(\boldsymbol{\lambda}, \boldsymbol{\lambda}^*)$ of (7.4), the prediction function is

$$ f(\boldsymbol{x}) = \sum_{i=1}^{N} (\lambda_i - \lambda_i^*) K(\boldsymbol{x}_i, \boldsymbol{x}) + b. $$

The term $b$ follows from the KKT conditions by selecting an index $i$ such that $0 < \lambda_i < C$ or $0 < \lambda_i^* < C$. For instance,

$$ b = y_i - \epsilon - \sum_{j=1}^{N} (\lambda_j - \lambda_j^*) K(\boldsymbol{x}_j, \boldsymbol{x}_i) \quad \text{if } 0 < \lambda_i < C, $$
and

$$b = y_i + \epsilon - \sum_{j=1}^{N} (\lambda_j - \lambda_j^*) K(\mathbf{x}_j, \mathbf{x}_i) \quad \text{if } 0 < \lambda_j^* < C.$$

In practice, one averages $b$ over several admissible indices for improved numerical stability.

**Remark 7.4** (Geometric interpretation and role of hyperparameters). Points with $0 < \lambda_i < C$ or $0 < \lambda_i^* < C$ lie on the tube and are support vectors; those with $\lambda_i = C$ or $\lambda_i^* = C$ are outside the tube. The parameter $\epsilon$ controls the tube thickness: a larger value induces a smoother model and fewer support vectors, but higher bias. The parameter $C$ tunes the penalty for overshooting: a large value favors tighter fit (higher variance), whereas a small value allows more tolerance (lower variance). Kernelization enters solely through $K(\mathbf{x}_i, \mathbf{x}_j)$, exactly as in classification.

## 7.5 Modelling: practical principles and hyperparameter tuning

This section gathers the modelling choices that drive SVM performance: (i) feature handling, (ii) the effect of hyperparameters on the geometry of the decision boundary, and (iii) a lean tuning/evaluation protocol. The figures illustrate the effect of a very large $C$ (Figure 8) and a very large $\gamma$ for an RBF kernel (Figure 9).

**Feature handling** — SVMs are scale-sensitive. We work within a pipeline that includes standardisation $z = (x - \mu)/\sigma$, fitted exclusively on the training folds inside cross-validation. Categorical variables are one-hot encoded. The presence of outliers justifies mild robust scaling (or winsorisation) to stabilise the margin when $C$ is large. With class imbalance, use class weighting (class_weight="balanced" or manual weights) and imbalance-aware metrics (AUC-PR, F1, balanced accuracy).

**Hyperparameters** —

- (i) Linear SVM: $C > 0$ sets the margin-violation trade-off. A large $C$ tightens the margin and reduces training errors (variance $\uparrow$); a small $C$ widens the margin (bias $\downarrow$). The squared hinge loss strengthens the penalty on large violations, Figure 8

- (ii) RBF: two coupled parameters shape the boundary, $C$ and $\gamma > 0$ (effective kernel width). A large $\gamma$ yields highly local, wiggly boundaries (variance $\uparrow$); a small $\gamma$ gives smooth boundaries (bias $\downarrow$). Search must be joint in $(C, \gamma)$, Figure 9.

- (iii) Polynomial (optional): the degree $p$ sets global complexity (in practice $p \in \{2, 3\}$), while $c_0 \ge 0$ modulates the influence of lower-order terms.

**Remark 7.5.** Bias-variance view. Increasing $C$ or $\gamma$ reduces bias but raises variance; under RBF these effects compound. Decreasing them smooths the boundary at the cost of higher bias.

**Tuning and evaluation** — Use a pipeline {StandardScaler → SVM} with stratified K-fold CV ($K=5$ by default). For RBF, explore logarithmic grids $C \in [10^{-3}, 10^3]$, $\gamma \in [10^{-4}, 10^1]$; a useful starting heuristic is

$$\gamma \approx \frac{1}{\text{median}(\|\mathbf{x}_i - \mathbf{x}_j\|^2)},$$

computed on a subsample. If calibrated probabilities are required (see Section 7.1), apply calibration (Platt or isotonic) after model selection, on a dedicated validation split.
<figure><img src="image_11.png" /><figcaption>Figure 8 – **Effect of C (soft margin)** on the margin and the set of support vectors.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 9 – **Effect of γ (RBF)** on the decision boundary and the apparent margin.</figcaption></figure>
References

Mark A. Aizerman, Eduard M. Braverman, and Lev I. Rozonoer. Theoretical foundations of the potential function method in pattern recognition. In *Automation and Remote Control*, volume 25, pages 821–837, 1964.

Nachman Aronszajn. Theory of reproducing kernels. *Transactions of the American mathematical society*, 68(3):337–404, 1950.

Bart Baesens, Tony Van Gestel, Stijn Viaene, Maria Stepanova, Johan A. K. Suykens, and Jan Vanthienen. Benchmarking state-of-the-art classification algorithms for credit scoring. *Journal of the Operational Research Society*, 54(6):627–635, 2003. doi: 10.1057/palgrave.jors.2601545.

Christopher M. Bishop. *Pattern Recognition and Machine Learning*. Springer, New York, 2006.

Bernhard E. Boser, Isabelle Guyon, and Vladimir N. Vapnik. A training algorithm for optimal margin classifiers. In *Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory (COLT)*, pages 144–152, 1992.

Stephen Boyd and Lieven Vandenberghe. *Convex Optimization*. Cambridge University Press, Cambridge, 2004.

Corinna Cortes and Vladimir Vapnik. Support-vector networks. *Machine Learning*, 20(3):273–297, 1995.

Thomas M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. *IEEE Transactions on Electronic Computers*, EC-14(3): 326–334, 1965.

Isabelle Guyon, Jason Weston, Stephen Barnhill, and Vladimir Vapnik. Gene selection for cancer classification using support vector machines. *Machine Learning*, 46(1):389–422, 2002. doi: 10.1023/A:1012487302797.

Trevor Hastie, Robert Tibshirani, and Jerome Friedman. *The Elements of Statistical Learning*. Springer, New York, 2 edition, 2009.

C. Hurlin. Support vector machine, September 2025. URL https://doi.org/10.5281/zenodo.17115854.

Thorsten Joachims. Text categorization with support vector machines: Learning with many relevant features. In *Proceedings of the 10th European Conference on Machine Learning (ECML 1998)*, volume 1398 of *Lecture Notes in Computer Science*, pages 137–142. Springer, 1998. doi: 10.1007/BFb0026683.

George Kimeldorf and Grace Wahba. Some results on tchebycheffian spline functions. *Journal of Mathematical Analysis and Applications*, 33(1):82–95, 1971.

Gert Loterman, Iain Brown, David Martens, Christophe Mues, and Bart Baesens. Benchmarking regression algorithms for loss given default modeling. *International Journal of Forecasting*, 28 (1):161–170, 2012. doi: 10.1016/j.ijforecast.2011.01.006.

Farid Melgani and Lorenzo Bruzzone. Classification of hyperspectral remote sensing images with support vector machines. *IEEE Transactions on Geoscience and Remote Sensing*, 42(8): 1778–1790, 2004. doi: 10.1109/TGRS.2004.831865.

A. B. J. Novikoff. On convergence proofs on perceptrons. *Proceedings of the Symposium on the Mathematical Theory of Automata*, 12:615–622, 1962.
Edgar Osuna, Robert Freund, and Federico Girosi. Training support vector machines: An application to face detection. In *Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)*, pages 130–136. IEEE, 1997. doi: 10.1109/CVPR.1997.598362.

Brian D Ripley. *Pattern recognition and neural networks*. Cambridge university press, 1996.

Frank Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. *Psychological Review*, 65(6):386–408, 1958.

Bernhard Schölkopf and Alexander J. Smola. *Learning with Kernels*. MIT Press, Cambridge, MA, 2002.

Alex J. Smola and Bernhard Schölkopf. A tutorial on support vector regression. *Statistics and Computing*, 14(3):199–222, 2004.

Johan A. K. Suykens and Joos Vandewalle. Least squares support vector machine classifiers. *Neural Processing Letters*, 9(3):293–300, 1999.

Johan A. K. Suykens, Tony Van Gestel, Jos De Brabanter, Bart De Moor, and Joos Vandewalle. *Least Squares Support Vector Machines*. World Scientific, Singapore, 2002.

Ellen Tobback, David Martens, Tony Van Gestel, and Bart Baesens. Forecasting loss given default models: impact of account characteristics and the macroeconomic state. *Journal of the Operational Research Society*, 65(3):376–392, 2014. doi: 10.1057/jors.2013.158.

Vladimir N. Vapnik. *The Nature of Statistical Learning Theory*. Springer, New York, 1995.

Vladimir N. Vapnik. *Statistical Learning Theory*. Wiley, New York, 1998.

Xiao Yao, Jonathan Crook, and Galina Andreeva. Support vector regression for loss given default modelling. *European Journal of Operational Research*, 240(2):528–538, 2015. doi: 10.1016/j.ejor.2014.06.043.

Xiao Yao, Jonathan Crook, and Galina Andreeva. Enhancing two-stage modelling methodology for loss given default with support vector machines. *European Journal of Operational Research*, 263(2):679–689, 2017. doi: 10.1016/j.ejor.2017.05.017.