Where we left off

• Session 1: ERM, generalization
• 1-NN/\(k\)-NN,
• PCA, linear regression \(h(x) = \langle w, x \rangle\)

Polynomial map

What if the linear classifier \(\langle w, x \rangle\) is not enough?

• Use non-linear mapping of the input before predicting

\[ \phi: x \mapsto [x, x^2, \ldots, x^p], \qquad h(x) = \langle w, \phi(x) \rangle \]

• Still linear ERM — just on \(\phi(x)\) instead of \(x\)

Interactions need more than powers

\[ x^{\otimes p} = x \otimes \cdots \otimes x \quad (p \text{ times}), \qquad \langle a\otimes a',\, b\otimes b'\rangle = \langle a,b\rangle\langle a',b'\rangle \]

• Element-wise \(\phi\) misses cross-terms
• \(x[i]^k x[j]^l\) corresponds to \(x\otimes x\) (outer product or tensor product)
• \(O(d^p)\) memory!

Periodic maps

\[ \phi: x \mapsto [\sin(f_0 x), \sin(2f_0 x), \dots, \sin(p f_0 x)] \]

• Known periodicity (seasons, dates, …) \(\Rightarrow\) bake it into \(\phi\)

Generalizing the direction

\[ \phi: x \mapsto [\sin(\omega_1^\top x), \dots, \sin(\omega_p^\top x)], \qquad \omega_i \sim \mathcal{N}(0,\sigma) \]

• What does the inner product encode?

\[ \sin(a)\sin(b) = \tfrac12[\cos(a-b) - \cos(a+b)] \] \[ \langle \phi(x), \phi(x') \rangle = \frac12\sum_{i=1}^p \big[\cos(\omega_i^\top(x-x')) - \cos(\omega_i^\top(x+x'))\big] \]

• Almost shift-invariant except for the \(x+x'\) term

Why training error lies

• Training error decreases monotonically with \(p\)
• Same story as in \(k\)-NN: \(k=1\) always wins on training error, and is almost always the wrong choice

As usual, training error cannot be trusted for selecting hyper-parameters

Why regularize

• Cross-validation is point-wise evaluation, can be an unlucky sample
• Instead of restricting the hypothesis class (choosing \(p\)), penalize complex solutions everywhere: \[ \mathcal{L}_\Omega(w) = \frac1n \sum_i \ell(w^\top x_i, y_i) + \Omega(w) \]

Ridge / Tikhonov — setup

Prevent parameters from blowing up:

\[ \mathcal{L}(w) = \frac1n\sum_i \ell(x_i^\top w, y_i) + \lambda\|w\|^2 \]

Bonus: Fixes the pseudo-inverse’s instability when \(X^\top X\) has small eigenvalues (e.g., \(\mathrm{rank}(X) < d\))

Ridge / Tikhonov — derivation

Setting the derivative of the augmented risk to \(0\): \[ \frac{\partial \mathcal{L}}{\partial w} = 0 = \frac{2}{n}\big(X^\top X w - X^\top Y\big) + 2\lambda w \]

Ridge / Tikhonov — why it works

• Adding \(\lambda I\) offsets every eigenvalue of the covariance by \(\lambda\) (“ridge”)
• Two effects: (1) the whole space becomes spanned, making inversion numerically stable; (2) larger dimensions get compressed, making the data look more spherical
• Similar effect to a whitened PCA: multiply the PCA projector by the inverse square root of the eigenvalues so the projected covariance is the identity

LASSO — setup

Assume some parameters are harmful and should be \(0\):

\[ \mathcal{L}_\Omega(w) = \frac1n \sum_i \ell(w^\top x_i, y_i) + \lambda \|w\|_1 \]

• The natural sparse regularizer is \(\|w\|_0\), but that’s combinatorial to optimize (test every subset of active components)
• \(\ell_1\) instead: still convex (if \(\ell\) is), and tractable
• Bonus: a sparse \(w\) tells you which features actually matter

LASSO — derivation setup

To see why \(\ell_1\) gives sparsity, project \(X\) onto its own eigenspace via SVD, \(X = VSU^\top\): \[ \mathcal{L}(w) = \|Y - XUw\|^2 + \lambda\|w\|_1 = \|Y - VSw\|^2 + \lambda\|w\|_1 \] (using \(U^\top U = I\))

LASSO — setting the gradient to zero

\[ \frac{\partial \mathcal{L}}{\partial w} = 0 = -2SV^\top Y + 2S^2 w + \lambda\, \mathrm{sign}(w) \]

\[ \Rightarrow \quad w = S^{-1}V^\top Y - S^{-2}\,\frac{\lambda\,\mathrm{sign}(w)}{2} \]

Let \(\tilde{w} = S^{-1}V^\top Y\); note \(\mathrm{sign}(w) = \mathrm{sign}(\tilde w)\).

LASSO — case analysis

If \(\mathrm{sign}(w_i) = \mathrm{sign}(\tilde w_i) = +1\): \[ w_i = \underbrace{\tilde w_i}_{>0}\left(1 - \frac{\lambda S_i^{-2}}{2|\tilde w_i|}\right) > 0 \]

which only makes sense if the parenthesis is positive, i.e. \[ w_i = \tilde w_i \max\left(0,\ 1 - \frac{\lambda S_i^{-2}}{2|\tilde w_i|}\right) \]

The case \(\mathrm{sign} = -1\) gives the identical formula by symmetry.

LASSO — soft thresholding

• Whenever \(\lambda\) is large enough relative to \(|\tilde w_i|\), the \(\max\) clamps to \(0\): the coefficient is exactly zeroed, not just shrunk
• Ridge only ever shrinks whereas LASSO can delete
• (Analysis in \(X\)’s eigenspace only, but the soft-thresholding behavior carries over to the general case)

Elastic net

Why not combine both?

• No blow-up
• No extra variables

\[ \mathcal{L}_\Omega(w) = \frac1n \sum_i \ell(w^\top x_i, y_i) + \lambda_1 \|w\|_1 + \lambda_2 \|w\|_2^2 \]

\(\lambda_1\) and \(\lambda_2\) chosen by cross-validation

Occam’s razor, formalized

Among predictors with equal (zero) empirical risk, prefer the simplest one.

Can we prove it’s a good one?

• Split a predictor family \(\mathcal{H}\) into nested subsets \(S_0 \subset S_1 \subset \dots\) ordered by complexity
• If all have zero empirical risk, picking from \(S_0\) minimizes the chance of unnecessary capacity \(\Rightarrow\) less risk of overfitting

Shattering coefficient

For binary classification with \(y \in \{-1,1\}\), a dataset of size \(m\) has \(2^m\) possible labelings.

• \(\hat{m}_{\mathcal{H}}(\mathcal{A})\) is the number of distinct labeling produced by \(\mathcal{H}\) on \(\mathcal{A}\)
• If \(m_{\mathcal{H}} = 2^m\), \(\mathcal{H}\) shatters those \(m\) points, it realizes every possible labeling
• Higher shattering number \(\Rightarrow\) more complex family

Risk bound via shattering

with \(\mathcal{A}_{2m}\) an independent auxiliary dataset of size \(2m\).

Proof sketch: symmetrization

• Trades the incomputable true risk \(\mathcal{R}(h)\) for the gap between two empirical risks on two halves of a \(2n\)-sample dataset

Proof sketch: union bound + Hoeffding

• \(\mathcal{H}\) has only \(\hat{m}_{\mathcal{H}}(\mathcal{A}_{2m})\) distinct predictors on \(\mathcal{A}_{2m}\) \(\Rightarrow\) the sup over \(h\) becomes a finite union over those predictors
• For one fixed predictor, the gap between the two halves is a difference of Bernoulli sums \(\Rightarrow\) Hoeffding gives \(P(\cdot > \varepsilon/2) \leq 2e^{-m\varepsilon^2/8}\)
• Union bound over \(\mathbb{E}[\hat{m}_{\mathcal{H}}(\mathcal{A}_{2m})]\) predictors, combine with symmetrization, solve for \(\varepsilon\) at confidence \(\delta\) \(\Rightarrow\) the theorem
• Exact same recipe as session 1’s PAC bound: union bound + concentration inequality

From shattering to VC dimension

• The shattering coefficient still depends on the data distribution (via the expectation over \(\mathcal{A}_{2m}\))
• We are not going to sample many dataset of size \(2m\) and try to label them arbitrarily!
• We want a bound that characterizes \(\mathcal{H}\) alone
• \(\ln \mathbb{E}[\hat{m}_{\mathcal{H}}(\mathcal{A}_{2m})] \leq \ln m_{\mathcal{H}} =: \mathcal{G}_{\mathcal{H}}(m)\), the growth coefficient

VC dimension

• If \(\mathcal{G}_{\mathcal{H}}(m)\) is dominated by \(m\), the bound’s second term vanishes as \(m\) grows: learning is always eventually successful
• If \(\mathcal{H}\) has maximal capacity (\(\mathcal{G}_{\mathcal{H}}(m) = m \ln 2\) for all \(m\)), the term never vanishes: no guarantee, ever

Named after Vapnik and Chervonenkis who developped the theory in the 60s

Risk bound via VC dimension

For finite VC dimension, one can show \(\mathcal{G}_{\mathcal{H}}(m) \leq m_{\mathrm{VC}}(\ln \frac{m}{m_{\mathrm{VC}}}+1)\) for \(m > m_{\mathrm{VC}}\).

• \(m \gg m_{\mathrm{VC}} \Rightarrow\) the bound tightens; infinite VC dimension \(\Rightarrow\) no guarantee regardless of \(m\)
• Finding \(m_{\mathrm{VC}}\) needs two things:
  • a shattered set of that size
  • a proof that no set of size \(+1\) can be shattered

⚡ VC dimension of linear classifiers

Try all possible labeling exhaustively

⚡ VC dimension of axis-aligned rectangles

From VC bound to margin

VC dimension of linear predictors in \(\mathbb{R}^d\) is \(d+1\): no generalization guarantee below \(d+1\) training samples.

• Vapnik: a tighter bound exists using the margin \(\Delta\), if \(\|x_i\|\leq R\): \[ m_{\mathrm{VC}} \leq \min\left(\frac{R^2}{\Delta^2},\, d\right) + 1 \]

Defining the margin

For \(h(x) = w^\top x + b\), the decision boundary is the hyperplane orthogonal to \(w\): \[ \Delta = \min_{x_i \in \mathcal{A}} \frac{|w^\top x_i + b|}{\|w\|} \]

• The margin is inversely proportional to \(\|w\|\)
• Bigger margin \(\Rightarrow\) smaller effective VC dimension \(\Rightarrow\) tighter bound, independent of the ambient dimension \(d\)
• This is the whole motivation for SVM: maximize the margin

Hard margin SVM

Fix \(\Delta=1\) (conveniently, where the hinge loss becomes zero) and minimize \(\|w\|\) under that constraint: \[ \min_{w,b} \frac12\|w\|^2 \quad \text{s.t.}\quad \forall i,\ y_i(w^\top x_i+b) \geq 1 \]

• Following SRM: minimizing \(\|w\|\) minimizes the VC-dimension bound
• Problem: assumes linear separability. If the data isn’t separable, the feasible set is empty.

Soft margin SVM

Cortes & Vapnik: allow constraint violations \(\zeta_i \geq 0\): \[ \min_{w,b,\zeta}\ \frac{\lambda}{2}\|w\|^2 + \frac1n\sum_i \zeta_i \quad \text{s.t.}\quad y_i(w^\top x_i+b) \geq 1-\zeta_i,\ \zeta_i\geq 0 \]

• \(\lambda\) trades margin size against how much points are allowed to violate it

The hinge loss

The soft-margin problem is equivalent to an unconstrained problem with the hinge loss: \[ \min_{w,b}\ \frac{\lambda}{2}\|w\|^2 + \frac1n \sum_i \max\big(0,\ 1-y_i(w^\top x_i+b)\big) \]

• Zero loss once a point is correctly classified with margin \(\geq 1\), linear penalty otherwise
• Solvable with plain SGD

The Lagrangian

Back to the hard-margin problem. Its Lagrangian, with \(\alpha_i \geq 0\): \[ \mathcal{L}(w,b,\alpha) = \frac12\|w\|^2 - \sum_{i=1}^n \alpha_i\big(y_i(w^\top x_i+b)-1\big) \]

• KKT optimality conditions will tell us the shape of the solution \(w^\star\)

Deriving \(w^\star\)

Set the derivative with respect to \(w\) to zero at the optimum: \[ \frac{\partial \mathcal{L}}{\partial w}(w^\star) = w^\star - \sum_i \alpha_i y_i x_i = 0 \]

\[ \Rightarrow\quad w^\star = \sum_{i=1}^n \alpha_i y_i x_i \]

• The optimal weight is a combination of training points

Complementary slackness: support vectors

KKT’s complementary slackness condition: \(\forall i,\ \alpha_i\big(y_i(w^{\star\top}x_i+b)-1\big) = 0\).

\[ \Rightarrow\quad y_i(w^{\star\top}x_i + b) \neq 1 \ \Rightarrow\ \alpha_i = 0 \]

Why this matters

• The solution is supported by a small subset of the training set, the support vectors
• Every other point could be deleted from \(\mathcal{A}\) without changing \(w^\star\) at all
• Special case of a much more general fact about representer theorems

From primal to dual

The dual problem re-expresses everything in terms of \(\alpha\) only: \[ \max_\alpha \inf_{w,b} \mathcal{L}(w,b,\alpha), \quad \text{s.t.}\ \alpha_i\geq 0 \]

• Substitute \(w^\star = \sum_i \alpha_i y_i x_i\) to remove \(w\)
• The optimality condition on \(b\) gives \(\sum_i \alpha_i y_i = 0\), removing \(b\) too

Deriving the dual objective

\[ \inf_{w,b}\mathcal{L}(w,b,\alpha) = \sum_i \alpha_i - \frac12 \sum_{i,j}\alpha_i\alpha_j y_i y_j\, x_i^\top x_j \]

• Depends on the data only through inner products \(\langle x_i, x_j\rangle\)

The kernel trick

Since the dual only needs inner products, we can map to a higher-dimensional space \(\phi(x)\) without ever computing \(\phi\) explicitly.

Kernelized SVM problem

Soft-margin dual with a kernel (\(C = 1/(n\lambda)\)): \[ \max_\alpha\ \sum_i \alpha_i - \frac12\sum_{i,j}\alpha_i\alpha_j y_i y_j\, k(x_i,x_j) \quad \text{s.t.}\ 0\leq \alpha_i \leq C,\ \sum_i \alpha_i y_i = 0 \]

Decision function: \[ h(x) = \sum_{i=1}^n \alpha_i y_i\, k(x,x_i) + b \]

• Larger \(C\) = less regularization (support vectors can contribute more)

Popular kernels

• Linear: \(k(x,x') = \langle x,x'\rangle\) — recovers the linear SVM
• Polynomial: \(k(x,x') = (1+\langle x,x'\rangle)^p\) — same expressivity as the polynomial map, without forming the \(O(d^p)\) feature vector
• Gaussian: \(k(x,x') = e^{-\gamma\|x-x'\|^2}\) — infinite-dimensional feature space

Building new kernels

• Finding the right kernel = injecting prior knowledge into the problem — the same role \(\phi\) played for generalized linear models

⚡ VC dimension of Gaussian kernel

SDCA

• We fix \(b=0\): removes the \(\sum_i \alpha_i y_i=0\) constraint, so each coordinate can be updated independently

SDCA — why it works

• Stochastic coordinate ascent: at each step, improve one \(\alpha_i\) keeping the others fixed
• The update uses an approximate second-order step: the true Hessian is the kernel matrix \(K\), we approximate by its diagonal \(k(x_i,x_i)\)
• \(\max(0,\min(C,\cdot))\) projects back into the box constraint after each step

Why stop at SVM?

• SVM’s support-vector sparsity came from one specific problem (hinge loss + \(\ell_2\) penalty). Is that a coincidence, or a general phenomenon?
• It’s general: representer theorems say that any regularized ERM solution is confined to the span of the training data, regardless of the loss

Reproducing Kernel Hilbert Space

• \(k\) is said to have the reproducing property
• Every sample \(x_i\) corresponds to a function \(\phi_{x_i} \in \mathcal{H}\)
• This is the space any kernelized solution has to live in

Representer theorem for linear prediction

• Note how general this is: any loss, any increasing penalty on the norm

Proof: orthogonal decomposition

Split \(w^\star\) into the part spanned by the data and an orthogonal residual: \[ w^\star = w_{\mathcal{A}} + w_\perp = \sum_{i=1}^n \alpha_i x_i + w_\perp \]

• \(w_\perp \perp x_i\) for all \(i\) \(\Rightarrow\) \(\langle w_\mathcal{A}, x_i\rangle = \langle w^\star, x_i\rangle\): the loss term is unchanged by dropping \(w_\perp\)
• \(\|w_\mathcal{A}\| \leq \|w^\star\|\) (triangle) and \(g\) is increasing \(\Rightarrow\) \(g(\|w_\mathcal{A}\|) \leq g(\|w^\star\|)\): the regularizer can only decrease
• So \(w_\perp\) is never helping, the minimizer has \(w_\perp = 0\)

Representer theorem for RKHS

The same argument goes through in a general RKHS, replacing \(x_i\) with \(\phi_{x_i} = k(x_i, \cdot)\):

• This is the same form we used for the kernel SVM decision function \(h(x) = \sum_i \alpha_i y_i k(x,x_i) + b\)

Why this matters

• Following ERM, even regularized, the solution cannot escape the training set
• Fundamental limitation of the ERM principle: you only get combinations of what you’ve already seen
• Explains why the SVM dual, kernel ridge regression, etc, all reduce to solving something on the \(n\times n\) Gram matrix: representer theorems guarantee that’s always enough
• Powerful but not weak: even for medium datasets, the space of possible combinations is gigantic

Why approximate the kernel

• Kernel methods need the Gram matrix \(K \in \mathbb{R}^{n\times n}\) with \(O(n^2)\) memory, quickly intractable
• If we find an explicit map \(\phi\) with \(k(x,x')\approx \langle\phi(x),\phi(x')\rangle\), we map the data once and go back to linear-method cost
• This is the generalized-linear-model idea again, now justified by kernel approximation instead of hand-designed features

Random Fourier Features — the map

For shift-invariant kernels (like the Gaussian kernel): \[ \phi(x) = \frac{1}{\sqrt{D}}\big[\cos(\omega_1^\top x), \sin(\omega_1^\top x), \dots, \cos(\omega_D^\top x), \sin(\omega_D^\top x)\big] \] with \(\omega_1,\dots,\omega_D \sim \mathcal{N}(0,\sigma^2 I)\) random and fixed in advance.

Random Fourier Features — why it approximates a kernel

Using \(\cos(a-b) = \cos(a)\cos(b)+\sin(a)\sin(b)\): \[ \langle \phi(x),\phi(x')\rangle = \frac1D \sum_{k=1}^D \cos\big(\omega_k^\top(x-x')\big) \]

• Unbiased estimator of the Gaussian kernel; converges to it in probability as \(D \to \infty\)
• Exactly the periodic map from the start of the session, now with its missing shift-invariance fixed (no more \(x+x'\) term, since we kept both \(\cos\) and \(\sin\) instead of only \(\sin\))

Nyström approximation

Instead of approximating the kernel function, approximate the Gram matrix directly via a low-rank decomposition: \[ K = ULU^\top, \qquad \text{keep only the } m \text{ leading eigenvectors} \] \[ \phi(x) = L_m^{-1/2} U_m^\top K(x), \qquad K(x) = [k(x_i,x)]_{1\leq i \leq n} \]

Nyström vs. RFF

• Nyström limits the effective VC dimension to \(m\) (the rank of the approximation)
• Works for any kernel, not just shift-invariant ones (unlike RFF)
• Require large Gram matrix computation

Kernelizing PCA — setup

Recall linear PCA: find \(w\), \(\|w\|=1\), maximizing \(w^\top \Sigma w\) with \(\Sigma = \frac1n \sum_i x_i x_i^\top\).

Do the same in feature space: replace \(x_i\) with \(\phi(x_i)\), \[ \Sigma_\phi = \frac1n \sum_i \phi(x_i)\phi(x_i)^\top \]

• Problem: \(\phi\) may be implicit or infinite-dimensional and \(\Sigma_\phi\) can never be formed explicitly

Kernelizing PCA — representer theorem

Since the objective only involves inner products of \(\phi(x_i)\) with \(w\), the optimal direction lives in the span of the data: \[ w = \sum_{i=1}^n \alpha_i \phi(x_i) \]

• Same argument that gave us support vectors for SVM, the solution can only be a combination of what it has seen

Kernelizing PCA — reducing to the Gram matrix

Substitute into the eigenproblem \(\Sigma_\phi w = \lambda w\), then project both sides onto each \(\phi(x_k)\). Every inner product \(\phi(x_i)^\top\phi(x_j)\) becomes \(K_{ij} = k(x_i,x_j)\): \[ K^2 \alpha = n\lambda K \alpha \quad\Longleftarrow\quad K\alpha = n\lambda\alpha \]

• An eigenproblem on the Gram matrix \(K\), \(\alpha\) is an eigenvector

Kernelizing PCA — centering

Linear PCA subtracts the mean first. In feature space we can’t compute \(\frac1n\sum_i \phi(x_i)\) explicitly, but we can center the Gram matrix instead: \[ \tilde K = K - \mathbf{1}_n K - K \mathbf{1}_n + \mathbf{1}_n K \mathbf{1}_n \] with \(\mathbf{1}_n\) the \(n\times n\) matrix of all \(1/n\) entries.

Kernelizing PCA — projecting new points

Once \(\alpha^{(k)}\) solves \(\tilde K \alpha^{(k)} = n\lambda_k \alpha^{(k)}\), the \(k\)-th kernel-PCA coordinate of a (possibly new) point \(x\) is \[ y_k(x) = \sum_{i=1}^n \alpha_i^{(k)}\, k(x_i, x) \]

• Same pattern as every kernelized algorithm this session: solve on the Gram matrix, project using \(k(\cdot,\cdot)\)

Recap

• GLM: non-linear features + linear ERM; controlling their complexity (degree, \(p\)) needs cross-validation or regularization (Ridge, LASSO)
• SRM/VC theory: why margins matter, independent of ambient dimension
• SVM: margin maximization \(\Rightarrow\) sparse solution in support vectors
• Kernels: the same trick (inner-product-only dependence) turns any representer-theorem algorithm non-linear for free: SVM, ridge regression, PCA
• RFF/Nyström: when the kernel matrix itself becomes the bottleneck, go back to explicit (approximate) feature maps