Linear SVM with Subgradient Descent - Supervised Learning

Linear SVM with Subgradient Descent

Train a linear Support Vector Machine by full-batch (sub)gradient descent on the L2-regularised hinge loss.

Background

An SVM looks for the hyperplane x · w + b = 0 with the widest margin between the classes. The soft-margin version trades margin width (small ||w||) against hinge-loss violations. The hinge max(0, 1 - margin) has a kink at margin 1, so we use a subgradient: the gradient of whichever piece is active. Uses the loss from Hinge Loss.

Objective

J(w, b) = (lam/2) * ||w||^2 + (1/m) * sum_i max(0, 1 - y_i * (X_i · w + b))

• X_i: row i of X, shape (n,); w: shape (n,); b: scalar
• y_i in {-1, +1}
• lam (lambda_param): regularisation strength. The bias is not regularised.

Subgradient

Let V = { i : y_i * (X_i · w + b) < 1 } be the samples that violate the margin (strictly less than 1; a margin of exactly 1 counts as satisfied). Then

dJ/dw = lam * w - (1/m) * sum_{i in V} y_i * X_i
dJ/db =         - (1/m) * sum_{i in V} y_i

The regularisation term lam * w appears once, whatever the samples do; samples outside V contribute nothing to the hinge part.

Algorithm

1. Start from w = zeros(n), b = 0.
2. Repeat iterations times: compute all margins with the current w, b, find V, compute both subgradients, then w -= learning_rate * dJ/dw and b -= learning_rate * dJ/db.

Inputs

• X: features, shape (m, n)
• y: labels in {-1, +1}, shape (m,)
• learning_rate, lambda_param: floats; iterations: int

Expected Return Format

A tuple (w, b):

• w: NumPy array of shape (n,), rounded to 4 decimals
• b: Python float, rounded to 4 decimals

Predict with np.sign(X @ w + b).

Constraints

• NumPy only, vectorised over samples (a boolean mask for V); no sklearn.
• This objective is the one minimised by sklearn.linear_model.SGDClassifier(loss='hinge', penalty='l2', alpha=lam), but sklearn uses stochastic updates and a learning-rate schedule, so its numbers differ. LinearSVC uses C (roughly 1 / (lam * m)) and the squared hinge by default.

Follow-up

• Why does the solution depend only on the support vectors?
• How would you swap the linear score for a kernel, and why is that natural in the dual but not in this primal formulation?

Input: linear_svm(np.array([[2, 1], [3, 2], [-2, -1], [-3, -2]]), np.array([1, 1, -1, -1]), 0.01, 0.01, 1000)
Output: (array([0.4009, 0.2231]), 0.0)

Input: Same data, learning_rate=0.1, iterations=1
Output: (array([0.25, 0.15]), 0.0)

import numpy as np

def linear_svm(X, y, learning_rate=0.01, lambda_param=0.01, iterations=1000):
    """
    Train a linear SVM by subgradient descent on
    (lambda_param / 2) * ||w||^2 + mean(max(0, 1 - y * (X @ w + b))).

    Args:
        X: Features, shape (m, n)
        y: Labels in {-1, +1}, shape (m,)
        learning_rate: Step size
        lambda_param: L2 regularization strength (bias not regularized)
        iterations: Number of full-batch updates

    Returns:
        w: Learned weights, shape (n,), rounded to 4 decimals
        b: Learned bias (Python float), rounded to 4 decimals
    """
    m, n = X.shape
    w = np.zeros(n)
    b = 0.0

    # Your gradient descent implementation here
    pass

    return np.round(w, 4), round(float(b), 4)