Kernel SVM with Pegasos

The problem, from first principles

Linear SVM via gradient descent on hinge loss trains a weight vector directly, which only works while the decision boundary is a hyperplane in the original feature space. A kernel SVM never forms that weight vector. Instead it keeps one coefficient per training point, and the decision function is a kernel-weighted vote of those points. Any kernel from the previous four questions can drive it.

Pegasos is a stochastic sub-gradient method for the SVM objective. Here it runs in a deterministic form: at step t it visits training point i = (t - 1) mod n, checks whether that point violates the margin under the current model, and if it does, increments that point's coefficient. The coefficient counts how many times the point has caused an update, so the final vector is a list of non-negative integers.

Given a precomputed Gram matrix K of shape (n, n), labels y in {-1, +1}, a regularization strength lam, and a number of iterations T, return the coefficient vector alpha of shape (n,).

Constraints

• Return a float array of shape (n,).
• At each step t from 1 to T, let i = (t - 1) % n and compute the decision value decision = sum_j alpha_j * y_j * K[j, i] / (lam * t).
• If y_i * decision < 1, increase alpha_i by 1. Otherwise leave every coefficient unchanged.
• The model's prediction for a new point with kernel row k is sign(sum_j alpha_j * y_j * k_j), which the tests use directly.
• iterations = 0 returns all zeros.
• Do not modify K or y.

Hints

Open one at a time. Each gives away a little more than the last.