Part VII · Selected Topics Chapter 33

Machine-Learning Algorithms

Three learning methods examined the way this book examines everything else: as algorithms with approximation ratios, regret bounds, and convergence rates.

The newest chapter in the 4th edition, and its angle is what makes it worth reading. This is not a statistics or neural-networks treatment. It takes three learning problems and analyses them with the tools of Parts I to VI: clustering gets an approximation-ratio proof, multiplicative weights gets a regret bound proved by a potential function, and gradient descent gets a convergence rate. Chapter 1 said machine learning is for problems you cannot specify; this chapter shows that the resulting methods are still just algorithms, and still analysable.

4th edition note. This chapter is entirely new. It covers clustering, multiplicative-weights algorithms, and gradient descent.

The setting
Clustering
k-means
k-center and a 2-approximation
Multiplicative weights
The regret bound
Gradient descent
Stochastic gradient descent
Recap

The setting

Paradigm	Input	Goal	Example here
Unsupervised	Unlabelled data	Find structure	Clustering
Online / adversarial	A sequence of predictions and outcomes	Do nearly as well as the best fixed choice	Multiplicative weights
Supervised	Labelled examples	Minimise a loss function	Gradient descent

Notice how much of the book these connect to. Clustering is an approximation algorithm problem in the sense of Chapter 35 — the exact version is NP-hard. Multiplicative weights is an online algorithm in the sense of Chapter 27, measured against an offline best. Gradient descent is numerical optimisation in the sense of Chapters 28 and 29. The chapter is a synthesis, not a departure.

Clustering

Partition n points into k groups so that points in a group are similar and points in different groups are not. Two standard objectives, and they behave differently:

Objective	Minimise	Character
k-means	Sum of squared distances to the nearest center	Optimises the average; sensitive to outliers
k-center	The maximum distance from any point to its center	Optimises the worst case; every point is covered
k-median	Sum of distances (not squared)	More robust to outliers than k-means

All three are NP-hard, even in the plane and even for k = 2 in general metric spaces. So the algorithms below are heuristics or approximations, never exact solvers — exactly the situation Chapter 35 is about.

k-means

LLOYD'S ALGORITHM  (the k-means algorithm)

1. Choose k initial centers.
2. repeat
       assign  each point to its nearest center
       recompute  each center as the centroid of its assigned points
   until no assignment changes.

Why it terminates. Each of the two steps can only decrease the objective, and there are finitely many possible assignments, so the algorithm cannot cycle and must stop. This is a monotone decrease plus finite state space argument — the same shape as a loop bound function from a correctness proof.

Termination is not optimality. Lloyd’s algorithm converges to a local minimum that can be arbitrarily worse than the global one, and the result depends entirely on the initial centers. It also has an exponential worst-case number of iterations, though in practice it converges in a handful.

The standard repair is k-means++, which chooses initial centers with probability proportional to the squared distance from the nearest already-chosen center. It spreads the seeds out, and it converts a heuristic into an algorithm with a guarantee:

k-means++ is O(lg k)-competitive in expectation against the optimum.

This is the chapter’s method in miniature: take a widely used heuristic with no guarantee, change the initialisation using randomization from Chapter 5, and obtain a provable approximation ratio. The algorithm barely changed; the analysis became possible.

k-center and a 2-approximation

The k-center objective admits a genuinely simple greedy algorithm with a tight bound.

GREEDY-K-CENTER  (farthest-point traversal)

1. Pick any point as the first center.
2. repeat k-1 times:
       add as the next center the point farthest from all
       centers chosen so far.

Theorem. Greedy farthest-point traversal is a 2-approximation for k-center: the maximum distance it achieves is at most twice the optimum. Moreover, unless P = NP, no polynomial-time algorithm achieves a ratio better than 2 — so the greedy algorithm is optimal among efficient algorithms.

The proof is a pigeonhole argument. If the greedy solution had a point at distance more than 2r* from every center, then those k+1 points would be pairwise more than 2r* apart, and no k balls of radius r* could cover them all — contradicting the definition of r*.

Multiplicative weights

A beautiful and very general online algorithm. You must make a prediction each day. n experts each offer advice, and you know nothing about their reliability. Afterwards the truth is revealed and you learn who was right.

MULTIPLICATIVE-WEIGHTS

1. Give every expert i an initial weight wᵢ = 1.
2. Each round:
       predict according to a weighted vote of the experts
       (or pick expert i with probability proportional to wᵢ)
       observe the outcome
       for each expert i that was wrong:
           wᵢ = wᵢ · (1 - ε)                 // penalise, do not eliminate

The two design decisions carry the whole result. Weights decrease multiplicatively, not additively, so a persistently wrong expert loses influence exponentially fast. And a wrong expert is never eliminated — an expert who is wrong for a hundred rounds and right thereafter can still recover, which is what makes the algorithm robust to changing conditions.

The regret bound

Theorem. After T rounds with n experts, the expected number of mistakes made by multiplicative weights satisfies

E[mistakes] ≤ (1 + ε) · (mistakes of the best expert) + (ln n)/ε

The second term is the regret: how much worse you do than the best expert in hindsight. Choosing ε = √(ln n / T) gives regret O(√(T ln n)), so the average regret per round goes to zero as T grows.

You end up nearly as good as the best expert without knowing in advance who that is, and the dependence on the number of experts is only logarithmic. You may consult thousands of experts and pay only ln n for the privilege.

The proof is a potential-function argument in the exact style of Chapter 16. Track the total weight Φ = ∑ wᵢ. Every mistake by the algorithm means a substantial fraction of the weight was on wrong experts, so Φ drops by a constant factor. But Φ is bounded below by the best expert’s surviving weight, (1-ε)m*. Squeezing the two bounds together yields the theorem.

Multiplicative weights is a meta-algorithm, not a niche trick. The same framework, under different names, gives boosting (AdaBoost) in machine learning, approximate solutions to linear programs, algorithms for zero-sum games, and portfolio selection. It is one of the most reused ideas in theoretical computer science.

Gradient descent

The supervised-learning workhorse. Minimise a differentiable function f(x) by repeatedly stepping downhill.

GRADIENT-DESCENT(f, x₀, η)

1. x = x₀
2. repeat
       x = x  -  η · ∇f(x)          // step against the gradient
   until convergence

The gradient ∇f points in the direction of steepest increase, so its negation is the direction of steepest decrease. η is the step size or learning rate.

Step size `η`	Behaviour
Too small	Converges, but very slowly
Too large	Overshoots the minimum; may oscillate or diverge
Well chosen	Converges at the rate below

Convergence depends on the shape of f. For a convex function, every local minimum is global and gradient descent finds it, at rate O(1/t) after t steps, or linearly (error shrinking by a constant factor per step) if the function is also strongly convex. For a non-convex function — every neural network — there are no such guarantees, and you converge to some stationary point with no bound on its quality.

This is the same convex-versus-not distinction that separated Chapter 29’s linear programs, which are solvable, from integer programs, which are not.

Stochastic gradient descent

The scaling problem. With m training examples, one exact gradient costs Θ(m) work — every example must be touched for every step. With millions of examples and thousands of steps, that is intolerable.

Stochastic gradient descent estimates the gradient from a single randomly chosen example, or a small mini-batch, instead of all m. The estimate is noisy but unbiased — correct in expectation — and it costs O(1) instead of O(m). You take far more steps, each far cheaper, and make much faster progress per unit of work.

	Batch GD	SGD
Cost per step	`Θ(m)`	`O(1)`
Gradient quality	Exact	Noisy but unbiased
Path	Smooth descent	Jittery
Practical	Only for small data	The default everywhere

The noise is sometimes a feature. On non-convex objectives, SGD’s randomness can shake it out of a poor local minimum or a saddle point that exact gradient descent would settle into. It is another instance of the Chapter 5 theme: injecting randomness to avoid being trapped by structure in the input.

Recap

The eight things to carry forward

The chapter treats learning methods as algorithms with provable bounds — approximation ratios, regret bounds, convergence rates — not as statistics.
Clustering objectives: k-means minimises summed squared distance, k-center minimises the maximum distance. All are NP-hard.
Lloyd’s algorithm terminates because both steps monotonically decrease the objective, but converges only to a local minimum that depends on initialisation.
k-means++ seeds proportional to squared distance and is O(lg k)-competitive — a heuristic turned into a guaranteed algorithm by randomizing the start.
Greedy farthest-point traversal is a 2-approximation for k-center, and no polynomial algorithm does better unless P = NP.
Multiplicative weights penalises wrong experts by a factor (1-ε) and never eliminates them, achieving regret O(√(T ln n)) — only logarithmic in the number of experts.
The regret proof is a potential-function argument on total weight, in the style of Chapter 16. The framework also yields boosting, LP approximation, and game-solving.
Gradient descent converges provably on convex functions and not otherwise. SGD uses a cheap unbiased estimate per step, and its noise helps escape poor local minima.

Where this goes next

Chapter 34 is the theoretical climax of the book: NP-completeness. It makes precise the intuition from Chapter 1 that some problems have no known efficient algorithm, defines the reduction machinery that relates their difficulty, and proves that a large family of natural problems stand or fall together.

← Ch 32 — String Matching Ch 34 — NP-Completeness →