> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-vii-selected-topics/33.-machine-learning-algorithms.md).

# 33. Machine-Learning Algorithms

## Exercises

### 33.1-1

Let $$N = \vert{}S^{(\ell)}\vert{}$$ and consider the sum of pairwise squared distances for points within this single cluster $$S^{(\ell)}$$. The derivation below uses equation (33.3) from the book and the expansion from the proof of Theorem 33.1 (in vector from). The latter helps establish the boxed equality below without repeating the details. Since the distance from a point to itself is zero ($$\Delta(\mathbf{x}, \mathbf{x}) = 0$$), we can drop the $$\mathbf{x} \neq \mathbf{y}$$ restriction from the summation without altering the result.

$$
\begin{align\*}
\sum\_{\mathbf{x} \in S^{(\ell)}} \sum\_{\mathbf{y} \in S^{(\ell)}} \Vert{}\mathbf{x} - \mathbf{y}\Vert{}^2 &= \sum\_{\mathbf{x} \in S^{(\ell)}} \sum\_{\mathbf{y} \in S^{(\ell)}} \left( \Vert{}\mathbf{x}\Vert{}^2 - 2\mathbf{x}^T\mathbf{y} + \Vert{}\mathbf{y}\Vert{}^2 \right) \\
&= \sum\_{\mathbf{x} \in S^{(\ell)}} \left( \sum\_{\mathbf{y} \in S^{(\ell)}} \Vert{}\mathbf{x}\Vert{}^2 \right) - 2 \sum\_{\mathbf{x} \in S^{(\ell)}} \sum\_{\mathbf{y} \in S^{(\ell)}} \mathbf{x}^T\mathbf{y} + \sum\_{\mathbf{x} \in S^{(\ell)}} \left( \sum\_{\mathbf{y} \in S^{(\ell)}} \Vert{}\mathbf{y}\Vert{}^2 \right) \\
&= N \sum\_{\mathbf{x} \in S^{(\ell)}} \Vert{}\mathbf{x}\Vert{}^2 - 2 \left( \sum\_{\mathbf{x} \in S^{(\ell)}} \mathbf{x}^T \right) \left( \sum\_{\mathbf{y} \in S^{(\ell)}} \mathbf{y} \right) + N \sum\_{\mathbf{y} \in S^{(\ell)}} \Vert{}\mathbf{y}\Vert{}^2 \\
&= 2N \sum\_{\mathbf{x} \in S^{(\ell)}} \Vert{}\mathbf{x}\Vert{}^2 - 2(N\mathbf{c}^{(\ell)})^T(N\mathbf{c}^{(\ell)}) \\
&\therefore \boxed{\sum\_{\mathbf{x} \in S^{(\ell)}} \sum\_{\mathbf{y} \in S^{(\ell)}} \Vert{}\mathbf{x} - \mathbf{y}\Vert{}^2 = 2N \left( \sum\_{\mathbf{x} \in S^{(\ell)}} \Vert{}\mathbf{x} - \mathbf{c}^{(\ell)}\Vert{}^2 \right)}.
\end{align\*}
$$

Summing this identity over all $$k$$ clusters proves that the objective function $$f(S, C)$$ of equation (33.2) may be alternatively written as

$$
f(S, C) = \sum\_{\ell=1}^k \frac{1}{2\vert{}S^{(\ell)}\vert{}} \sum\_{\mathbf{x} \in S^{(\ell)}} \sum\_{\mathbf{y} \in S^{(\ell)} : \mathbf{x} \neq \mathbf{y}} \Delta(\mathbf{x}, \mathbf{y}).
$$

### 33.1-2

Let the 4 points be the vertices of an equilateral triangle $$v\_1, v\_2, v\_3$$ and its centroid $$c$$. By randomly initializing the centers at $$c^{(1)}=v\_1$$ and $$c^{(2)}=v\_3$$ (step 1) and utilizing arbitrary tie-breaking, the algorithm may form in step 2 the $$C\_1 = {v\_1, v\_2}$$ and $$C\_2 = {c, v\_3}$$ configuration, permanently trapping it in a suboptimal state, rather than finding the optimal $$C\_1 = {v\_1}$$ and $$C\_2 = {c, v\_2, v\_3}$$ clustering.

### 33.1-3

As a first step, we create a set of unique points from the input. Afterward, we leverage the `RANDOM_SAMPLE` procedure from [Exercise 5.3-5](https://evarga.gitbook.io/sh-intro-to-algs/part-vii-selected-topics/pages/mQYLcUFZsQrVTnpSqO7i#id-5.3-5) with $$m=k$$.

The only minor edge case to be aware of is if the number of unique points in the input happens to be strictly less than $$k$$. In that scenario, we might need a fallback to simply select all available unique points (to maximize distinct centers) and then fill the remaining slots with arbitrary duplicates from the input.

### 33.1-4

Read the paper [Ckmeans.1d.dp: Optimal k-means Clustering in One Dimension by Dynamic Programming](https://pmc.ncbi.nlm.nih.gov/articles/PMC5148156/).

### 33.2-1

The result follows from the fact that the best expert may make $$m^*$$ mistakes. Therefore, the number of times they will be removed from the set $$S$$ equals $$m^*$$, which also matches the number of times that a set $$S$$ can become empty. Therefore, the total number of mistakes of an algorithm is at most $$(m^\*+1)\lceil  \lg n \rceil$$. The +1 correctly accounts for the final operating phase after the last reset.

### 33.2-2

Here is another way, besides the one described in the hint. Let's create a function $$f(x)$$ and prove that it is always greater than or equal to zero for the interval $$0 < x \le 1/2$$:

$$
f(x) = \ln(1-x) + x + x^2.
$$

We see that $$f(0)=0$$. If the first derivative is non-negative on the whole interval, then the function never drops below zero. Thus,

$$
f'(x) = \frac{-1}{1-x} + 1 + 2x= \frac{x(1 - 2x)}{1-x}.
$$

Because the numerator is non-negative and the denominator is strictly positive, the derivative $$f'(x) \ge 0$$ everywhere in the interval $$(0, 1/2]$$. This confirms that

$$
\ln(1-x) + x + x^2 \ge 0 \implies \ln(1-x) \ge -x - x^2.
$$

Substitute $$x=\gamma$$ to get the required inequality.

### 33.2-3

Let $$S\_t$$ be the set of remaining experts at step $$t$$, and $$s\_t = \vert{}S\_t\vert{}$$ be the number of experts in that set. Initially, $$s\_1 = n$$. At any step $$t$$, suppose an arbitrary number of experts, $$w\_t$$, make an incorrect prediction. Because the algorithm chooses an expert uniformly at random from the remaining pool $$S\_t$$, the probability of selecting an incorrect expert (and thus making a mistake) is $$\frac{w\_t}{s\_t}$$. After the outcome is learned, the set $$S\_{t+1}$$ is updated to remove all $$w\_t$$ experts who made an incorrect prediction. The new size becomes $$s\_{t+1} = s\_t - w\_t$$. The expert who always makes the correct prediction will always remain in the set, guaranteeing the final set size $$s\_{final} \ge 1$$.

We can bound the probability of making a mistake at step $$t$$:

$$
\frac{w\_t}{s\_t} \le \frac{1}{s\_t} + \frac{1}{s\_t - 1} + \dots + \frac{1}{s\_t - w\_t + 1}=H\_{s\_t} - H\_{s\_{t+1}}.
$$

The total expected number of mistakes $$E\[M]$$, by linearity of expectation, is the sum of the probabilities at each step (expected value of an indicator random variable for each step). Applying the bound established above generates a telescoping sum:

$$
E\[M] = \sum\_t \frac{w\_t}{s\_t} \le \sum\_t (H\_{s\_t} - H\_{s\_{t+1}})  \le H\_{s\_1} - H\_{s\_{final}}=H\_n - 1.
$$

By equation (A.17), we have

$$
E\[M] \le \lg n \le \lceil \lg n \rceil.
$$

### 33.2-4

Wikipedia describes in detail the [randomized weighted majority algorithm](https://en.wikipedia.org/wiki/Randomized_weighted_majority_algorithm) including the analysis that exactly matches the form required by this exercise.

### 33.3-1

Let's follow the hint from the book. The [proof for one-dimensional case](https://math.stackexchange.com/a/1761839/753413) is available at StackExchange for Mathematics. Note that the cited text assumes $$y\<x$$. The generalization to $$n$$-dimensional space is a natural extension of this 1D logic. The transition simply swaps scalar multiplication for the inner product and the scalar derivative for the gradient vector. Lemma 33.6 formalizes the global bounding property.

Because a convex function always lies above its tangent hyperplane, this property is the structural reason why any local minimum is guaranteed to be a global minimum. If you find a point where the gradient $$\nabla f(\bold{y}) = 0$$, the tangent hyperplane is perfectly horizontal, meaning the entire function must sit at or above that value.

### 33.3-2

The proof is by induction on the number of repeated application of the definition of convexity in inequality (33.18). The base case $$T=1$$ gives that $$f(\bold{x}^{(0)})=f(\bold{x}^{(0)})$$. The base case $$T=2$$ follows from inequality (33.18) with $$\lambda=1/2$$.

The inductive step is trivally proven by using $$0<\lambda =\frac {T-1}{T}<1$$ and assuming the statement is true for $$T-1$$. We have

$$
\begin{align\*}
f\left(\frac{1}{T}\bold{x}^{(T-1)} + \frac{T-1}{T}\frac{\sum\_{i=0}^{T-2} \bold{x}^{(i)}}{T-1}\right) &\le \frac{1}{T}f(\bold{x}^{(T-1)}) + \frac{T-1}{T}f\left(\frac{\sum\_{i=0}^{T-2} \bold{x}^{(i)}}{T-1}\right) \\
&\le \frac{1}{T}f(\bold{x}^{(T-1)}) + \frac{T-1}{T}\left(\frac{\sum\_{i=0}^{T-2} f(\bold{x}^{(i)})}{T-1}\right) && \text{(by the inductive hypothesis)} \\
&= \frac{\sum\_{i=0}^{T-1} f(\bold{x}^{(i)})}{T}.
\end{align\*}
$$

### 33.3-3

The proof relies directly on the relationship between the squared Euclidean norm and the inner product, defined as $$\Vert{}\bold{x}\Vert{}^2 = \langle \bold{x}, \bold{x} \rangle$$. This gives

$$
\begin{align\*}
\Vert{}\bold{a} + \bold{b}\Vert{}^2 &= \langle \bold{a} + \bold{b}, \bold{a} + \bold{b} \rangle \\
&= \langle \bold{a}, \bold{a} \rangle + \langle \bold{a}, \bold{b} \rangle + \langle \bold{b}, \bold{a} \rangle + \langle \bold{b}, \bold{b} \rangle \\
&= \Vert{}\bold{a}\Vert{}^2 + 2\langle \bold{b}, \bold{a} \rangle + \Vert{}\bold{b}\Vert{}^2 \\
&\therefore \Vert{}\bold{a} + \bold{b}\Vert{}^2 - \Vert{}\bold{a}\Vert{}^2 = 2\langle \bold{b}, \bold{a} \rangle + \Vert{}\bold{b}\Vert{}^2.
\end{align\*}
$$

### 33.3-4

The Hessian matrix of a linear function is identically zero, which is a positive semi-definite matrix, confirming convexity.

### 33.3-5

Let $$E(\bold{w})$$ be the loss function as given in equation (3.33). The $$j$$-the term of the gradient is

$$
\frac{\partial E}{\partial w\_j} = 2\sum\_{i=1}^m  \underbrace{\left(w\_0 + \sum\_{k=1}^n w\_k x\_k^{(i)} - y^{(i)}\right)}\_{e^{(i)}} x\_j^{(i)}.
$$

We first compute the individual errors $$e^{(i)}$$ for all $$m$$ samples using the current set of weights. Afterward, a double loop can compute all entries of the gradient in $$O(nm)$$ time.

### 33.3-6

Taking the norm of the gradient derived in the previous exercise yields (in vector form):

$$
\begin{align\*}
\Vert{}\nabla E(\mathbf{w})\Vert{} &= \Vert{} 2 \sum\_{i=1}^m \underbrace{(\mathbf{w}^T \mathbf{x}^{(i)} - y^{(i)})}*{\mathbf{e}^{(i)}} \mathbf{x}^{(i)} \Vert{} \\
&\le 2 \sum*{i=1}^m (\Vert{}\mathbf{w}\Vert{} \Vert{}\mathbf{x}^{(i)}\Vert{} + \vert{}y^{(i)}\vert{}) \Vert{}\mathbf{x}^{(i)}\Vert{} \\
&\le B \left( 2 \sum\_{i=1}^m \Vert{}\mathbf{x}^{(i)}\Vert{}^2 \right) + \left( 2 \sum\_{i=1}^m \vert{}y^{(i)}\vert{} \Vert{}\mathbf{x}^{(i)}\Vert{} \right) \\
&\therefore L = O(B).
\end{align\*}
$$

The second line applies the triangle and the Cauchy-Schwarz inequalities. The conclusion follows from the fact only the weights are regarded as variables.

### 33.3-7

The partial derivative of the objective function $$f(S,C)$$ with respect to $$\mathbf{c}^{(l)}$$ is

$$
\nabla\_{\mathbf{c}^{(l)}} f(S,C) = \sum\_{\mathbf{x} \in S^{(l)}} \nabla\_{\mathbf{c}^{(l)}} \Vert{}\mathbf{x} - \mathbf{c}^{(l)}\Vert{}^2 = \sum\_{\mathbf{x} \in S^{(j)}} -2(\mathbf{x} - \mathbf{c}^{(l)}).
$$

Move each centroid in the opposite direction of its gradient by scaling it with a small positive step size (learning rate) $$\gamma$$:

$$
\mathbf{c}^{(l)}*{new} = \mathbf{c}^{(l)}*{old} - \gamma \nabla\_{\mathbf{c}^{(l)}} f(S,C)= \mathbf{c}^{(l)}*{old} + 2\gamma \sum*{\mathbf{x} \in S^{(l)}} (\mathbf{x} - \mathbf{c}^{(l)}\_{old}).
$$

With the centroids moved to new coordinates, you need to re-evaluate the closest points (reassign the clusters) and repeat the gradient updates until the centroids stop moving.

## Problems

### 33-1 Newton’s method

#### a.

$$
0=f'(x^{(t)})(x^{(t+1)} – x^{(t)}) + f(x^{(t)}) \implies x^{(t+1)}=x^{(t)}-\frac{f(x^{(t)}}{f'(x^{(t)})}.
$$

#### b.

We start with the equation (33.4)

$$
f(x^*) = f(x^{(t)}) + f'(x^{(t)})(x^* - x^{(t)}) + \frac{1}{2}f''(\gamma^{(t)})(x^\* - x^{(t)})^2.
$$

Since $$f(x^\*)=0$$, we have

$$
f(x^{(t)}) = -f'(x^{(t)})(x^\* - x^{(t)}) - \frac{1}{2}f''(\gamma^{(t)})(x^\* - x^{(t)})^2.
$$

Using the iterative formula from part (a), we get

$$
\begin{align\*}
x^{(t+1)} &= x^{(t)} - \frac{-f'(x^{(t)})(x^\* - x^{(t)}) - \frac{1}{2}f''(\gamma^{(t)})(x^\* - x^{(t)})^2}{f'(x^{(t)})} \\
&= x^{(t)} + (x^\* - x^{(t)}) + \frac{f''(\gamma^{(t)})}{2f'(x^{(t)})}(x^\* - x^{(t)})^2 \\
&= x^\* + \frac{f''(\gamma^{(t)})}{2f'(x^{(t)})}(x^\* - x^{(t)})^2 \\
&\therefore x^{(t+1)} - x^\* = \frac{f''(\gamma^{(t)})}{2f'(x^{(t)})}(x^\* - x^{(t)})^2 \implies \epsilon^{(t+1)} = \frac{\vert{}f''(\gamma^{(t)})\vert{}}{2\vert{}f'(x^{(t)})\vert{}} (\epsilon^{(t)})^2.
\end{align\*}
$$

#### c.

To find the number of iterations $$t$$ required to reach an accuracy of $$\delta$$, we must unroll the recurrence relation created by the quadratic convergence bound. We have

$$
\epsilon^{(t+1)} \le c(\epsilon^{(t)})^2 \implies c\epsilon^{(t+1)} \le (c\epsilon^{(t)})^2.
$$

Iterating the recurrence gives

$$
\epsilon^{(t)} \le \frac{1}{c}(c\epsilon^{(0)})^{2^t}.
$$

We want $$\epsilon^{(t)} \le \delta$$, thus (assuming $$c\epsilon^{(0)} < 1$$)

$$
t \ge \lg \left( \frac{\lg(c\delta)}{\lg(c\epsilon^{(0)})} \right)=O(\lg \lg (1/\delta)).
$$

#### d.

For the provided function, Newton's method reduces to

$$
x^{(t+1)} = x^{(t)} - \frac{(x^{(t)} - 3)^2}{2(x^{(t)} - 3)} = x^{(t)} - 0.5(x^{(t)} - 3) \implies  x^{(t+1)} - 3 = 0.5(x^{(t)} - 3).
$$

It turns out that $$\epsilon^{(t+1)} = \epsilon^{(t)}/2$$, which is not a quadratic convergence anymore. Because $$x = 3$$ is a multiple root (the derivative is zero at the root), the assumption required for quadratic convergence is violated. We would need lots of iterations to reach a tolerance of $$\delta$$.

The gradient descent update rule is

$$
x^{(t+1)} = x^{(t)} - 2\gamma(x^{(t)} - 3) \implies x^{(t+1)} - 3 = (1 - 2\gamma)(x^{(t)} - 3).
$$

With $$\gamma=0.5$$, gradient descent will jump precisely to 3 and find the exact minimizer in 1 iteration.

This problem highlights a degenerate case. Because the root and the minimizer are identical, Newton's method for root-finding mathematically behaves exactly like gradient descent with a suboptimal fixed learning rate of $$\gamma = 0.25$$, whereas properly tuned gradient descent solves the quadratic problem instantly.

### 33-2 Hedge

Read section 2.1 of the [CS5275 lecture notes](https://www.comp.nus.edu.sg/~scarlett/CS5275_notes/06-MWU.pdf). See also [Exercise 33.2-4](#id-33.2-4).

### 33-3 Nonoptimality of Lloyd’s procedure in one dimension

Let $$k=2$$ with the following set of points $$S={-1,0,0.5,1.5}$$. If the initial centroids (randomly picked) are $${-1,0.5}$$ then the procedure would create two clusters $$C\_1={-1}$$ and $$C\_2={0,0.5,1.5}$$. This is suboptimal, since $$C\_1={-1,0}$$ and $$C\_2={0.5,1.5}$$ is a better solution.

### 33-4 Stochastic gradient descent

A good overview of this method is available in IBM's [article about stochastic gradient descent](https://www.ibm.com/think/topics/stochastic-gradient-descent). It includes a Python based implementation.

Because the index $$i$$ is drawn uniformly at random, the stochastic gradient computed on $$(x\_i, y\_i)$$ is an unbiased estimator of the full gradient. When you follow the standard gradient descent analysis (which relies on bounding the distance to the optimum using the gradient norm), you replace the exact gradient with the stochastic gradient. Because the expectations pass linearly through the dot products in the proof, the deterministic upper bound of standard gradient descent holds in expectation for SGD. Thus,

$$
\mathbb{E}\[\text{Error}] \le \frac{RL}{\sqrt{T}}.
$$