week-06

TARGET DECK MachineLearning::Week-06

Cross-Cutting Synthesis

What do logistic regression and hard-margin SVM have in common, and how do they differ?

Common: same hypothesis class — a linear function of $\mathbf{x}$ (or $\varphi (\mathbf{x})$): $h(\mathbf{x})={\mathbf{w}}^{\top }\mathbf{x}+b$. Both produce linear decision boundaries. Different: the fitting criterion.

• Logistic regression: minimise cross-entropy (probabilistic / MLE-derived); every training point contributes to the gradient.
• Hard-margin SVM: maximise margin (geometric); only support vectors determine the boundary.

Same hypothesis, different objectives — leads to different solutions even on the same data.

Compare the three optimization algorithms covered: gradient descent, Newton-Raphson/IRLS, and SMO. When do you use each?

Algorithm	Used for	Per-iteration cost	Iterations
Gradient descent	Logistic regression, neural networks	$O(Nd)$	Many; needs $\eta$
Newton-Raphson / IRLS	Logistic regression (small $d$)	$O(d^3)$ Hessian inverse	Few; no $\eta$
SMO	SVM dual (soft- or hard-margin)	$O(N)$ analytic pair update	Many but cheap

GD scales with parameters; IRLS uses curvature but doesn’t scale; SMO exploits the dual’s structure (equality + box constraints).

For an SVM with $N=1,000$ examples and a Gaussian kernel, why is the dual preferred over the primal?

The Gaussian kernel implies an infinite-dimensional $\varphi$ — the primal would have infinitely many variables. The dual has only $N=1,000$ variables (one per training point), and the kernel trick computes $k(\mathbf{x},\mathbf{z})$ in $O(d)$ regardless of $\dim \varphi$. The dual depends only on inner products, so $\varphi$ is never explicitly formed.

Why does the kernel trick work, and what does Mercer's condition guarantee?

The kernel trick replaces $\varphi (\mathbf{x}{)}^{\top }\varphi (\mathbf{z})$ everywhere with $k(\mathbf{x},\mathbf{z})$ — sidestepping any explicit construction of $\varphi$. Mercer’s condition (symmetric + positive-semidefinite Gram matrix) guarantees that some embedding $\varphi$ exists such that $k={\varphi }^{\top }\varphi$, even if you can’t write it down. PSD also keeps the SVM dual a convex QP.

How does basis expansion $\varphi$ change the optimisation problem for logistic regression and SVM?

Procedurally: substitute $\mathbf{x}\to \varphi (\mathbf{x})$ everywhere — the loss/objective, gradient, Hessian, and update rules are otherwise unchanged. Functionally: the model is still linear in $\mathbf{w}$, so convexity is preserved. The decision boundary becomes non-linear in the original $\mathbf{x}$-space (e.g. a circle for $\varphi =(\Vert \mathbf{x}{\Vert }^2,x_1,x_2)$).

What's the role of complementary slackness in producing SVM sparsity?

KKT complementary slackness: $a^{(n)}{f}_n({\mathbf{w}}^{\ast })=0$ for every constraint $f_n$. For SVM, $f_n=1-y^{(n)}h({\mathbf{x}}^{(n)})\le 0$. So either:

• $a^{(n)}=0$ — point strictly outside the margin, contributes nothing.
• $f_n=0$ — point exactly on the margin (a support vector); $a^{(n)}>0$ allowed.

Only support vectors enter ${\mathbf{w}}^{\ast }={\sum }_n{a}^{(n)}{y}^{(n)}\varphi ({\mathbf{x}}^{(n)})$. Sparsity is structural, not heuristic.

What does strong duality require for the SVM, and what does it buy us?

Strong duality requires:

• Convex primal (yes — quadratic objective, linear constraints)
• Slater’s condition: a strictly feasible point exists (yes for separable data, or for soft-margin)

When it holds, ${\max }_{\mathbf{a}}{\min }_{\mathbf{x}}L={\min }_{\mathbf{x}}{\max }_{\mathbf{a}}L$ — solving the dual is exactly equivalent to solving the primal. We get all the benefits (kernel trick, smaller variable count) without any loss of optimality.

What's the relationship between the hard-margin and soft-margin SVM dual?

Identical except for one constraint:

• Hard-margin: $a^{(n)}\ge 0$
• Soft-margin: $\boxed{0\le a^{(n)}\le C}$ — the box constraint

Slack variables and their multipliers vanish in the dual derivation; the entire effect of slack collapses to the upper bound $a^{(n)}\le C$. The kernel trick, KKT conditions, and prediction formulas are otherwise unchanged.

Conceptual Foundations

What is i.i.d. and why do all generalisation arguments rely on it?

Independent and identically distributed: training and test examples are independent draws from the same fixed joint $P(\mathbf{x},y)$. Generalisation guarantees say things like “training error close to test error with high probability” — they require the test data to follow the same distribution as the training data. Distribution shift breaks every such guarantee.

When is logistic regression's loss strictly convex, and why does that matter?

The cross-entropy loss $E(\mathbf{w})=-{\sum }_i[y^{(i)}\ln \sigma ({\mathbf{w}}^{\top }{\mathbf{x}}^{(i)})+(1-y^{(i)})\ln (1-\sigma ({\mathbf{w}}^{\top }{\mathbf{x}}^{(i)}))]$ is strictly convex in $\mathbf{w}$ (assuming the design matrix has full column rank). It matters because every local minimum is a global minimum — gradient descent converging to a stationary point converges to the optimum. No worries about getting stuck in suboptimal valleys.

The polynomial kernel $k(\mathbf{x},\mathbf{z})=(1+{\mathbf{x}}^{\top }\mathbf{z}{)}^p$ corresponds to what implicit feature space?

All monomials of degree $\le p$ in the components of $\mathbf{x}$. For $\mathbf{x}\in {\mathbb{R}}^d$, the implicit feature space has $\left(\genfrac{}{}{0ex}{}{d+p}{d}\right)=O(d^p)$ dimensions. The kernel computes in $O(d)$ regardless of how large that becomes — e.g., $d=100,p=5$ implies $\sim 10^7$ feature dimensions but only 100 multiplications per kernel evaluation.

Why does maximising the margin give better generalisation than just any separating hyperplane?

Geometrically, a wide margin means small perturbations to a training point (or any new test point) won’t flip its class — the boundary is robust. Theoretically (formalised in week 9), restricting to fat hyperplanes of margin $\ge \rho$ shrinks the effective VC dimension to $\lceil R^2/{\rho }^2\rceil +1$ — independent of input dimension. This explains why high-dimensional kernel SVMs generalise even with infinite-dimensional $\varphi$.