Three uses of randomness

Markov: $P(X \ge 16) \le 4/16 = 0.25$. Option A is $(4/16)^2$ — the tempting move of "squaring because Chebyshev has a square", but you have no variance, so Chebyshev is unavailable. D is wrong because Markov needs only non-negativity and the mean, both of which you have.

Convert the absolute threshold into $\sigma$-units first: $k\sigma = 20 \Rightarrow k = 20/5 = 4$. Then $P \le 1/k^2 = 1/16 = 0.0625 \approx \mathbf{0.06}$.

The trap answer is $1/20^2 = 0.0025$, from forgetting to divide by $\sigma$.

A is false: Markov demands $X \ge 0$. (You could apply it to $X + 3$, but not to $X$.)

C is false: Chebyshev is a statement about a single random variable — no independence anywhere. Independence is Hoeffding's requirement.

D is true: $e^{-2nt^2}$ beats $\sigma^2/(nt^2)$ eventually, and "eventually" arrives fast.

Here $X_i \in [0,1]$ so $b-a=1$, and $t = 0.1$. Require $e^{-2n(0.01)} \le 0.05$, i.e. $-0.02n \le \ln 0.05 = -2.9957$, giving $n \ge 149.79$. So $n = \mathbf{150}$.

Note this is the one-sided form. If the question had asked for $P(|\bar X - 0.5| \ge 0.1)$, you would first union-bound the two tails to get $2e^{-2nt^2} \le 0.05$, and $n$ would rise to $185$.

Union bound gives $\le 100 \times 0.001 = 0.1$, and that is all you can say. A and D both assume something extra: D is the answer if the events were independent, which you were never told. This distinction is the entire reason the union bound is the tool of choice in the JL proof — the pairwise events there are dependent, and $1-(1-p)^m$ is not available.

$k \in O(\log n/\epsilon^2)$ has no $d$ in it. Doubling $d$ changes nothing about $k$; it only makes the reduction more worthwhile. What does change is the cost of applying the map, $O(ndk)$, which doubles.

$k \in O(\log n/\epsilon^2)$, so the ratio is $\dfrac{\log 10^6}{\log 10^3} = \dfrac{6}{3} = \mathbf{2}$ (the base of the log cancels, and so does the unnamed constant).

A thousand-fold increase in data costs only a doubling of the embedding dimension — the $\log n$ is what makes JL practical at scale. The trap answer is $1000$, from reading $k$ as linear in $n$.

Recall the construction: $M = \dfrac{R}{\sqrt k}$ with $R \in \mathbb{R}^{k\times d}$ and $R_{ij} \sim \mathcal N(0,1)$.

B is false: $M$ never depends on the data — only on $d$, $n$, $\epsilon$. (Strictly, $n$ enters through $k$, so adding enough points eventually nudges $k$; but no recomputation is triggered by the point's values, which is what the option claims.)

C is false: that is exactly the exact-isometry condition proved impossible for $k < d$.

A is true — unbiasedness is exact, not asymptotic. D is true — probabilistic method, deterministic conclusion.

All $\binom{n}{2}$ events are driven by the same random matrix $M$, so they are heavily dependent — the product formula is simply invalid. The union bound is looser (A is backwards) but it needs no independence, which is the entire point. D is wrong too: the events overlap freely.

$k \propto 1/\epsilon^2$, so halving $\epsilon$ quadruples $k$. Accuracy is expensive: the $\epsilon^{-2}$ dependence, not the $\log n$, is what usually makes $k$ large in practice.

Compute both radii first: $r = 2$ and $cr = 3 \times 2 = 6$.

Distance $5$ satisfies neither condition — it is not $\le 2$, and it is not $\ge 6$. It lies strictly inside the annulus $r < 5 < cr$, and there the definition asserts nothing at all.

The trap: compare against $cr$, not against $c$. Reading "$c = 3$ and $5 \ge 3$" leads straight to B. Change the numbers and the answer moves: at distance $7 \ge 6$ it would be B, and at distance $1 \le 2$ it would be A. C is never right for any distance — each regime gives a one-sided bound, never a two-sided sandwich.

$\rho = \dfrac{\log(1/0.9)}{\log(1/0.3)} = \dfrac{0.10536}{1.20397} = \mathbf{0.0875}$.

The base of the logarithm cancels — use whichever you like. Note how a wide $p_1/p_2$ gap gives a tiny $\rho$, hence very few tables: $L = \theta n^{0.0875}$ is almost constant.

AND requires all $k$ coordinates to match, so collisions get strictly harder — both $p_1^k$ and $p_2^k$ shrink. C confuses the two knobs: $k$ is the depth of each table, $L$ is the number of tables. Increasing $k$ does not change $L$.

The mnemonic: AND ↓ both rates (fixes FPR, damages TPR). OR ↑ both rates (fixes TPR, damages FPR). You need both, in that order.

Setting $n\,p_2^k = 1$ and solving gives the standard choice

$\log_2(10^6) = 6\log_2 10 = 6 \times 3.3219 = 19.93$, and $\log_2(1/0.5) = 1$. So $k = 19.93 \approx \mathbf{20}$.

Check it does what it is supposed to: $n\,p_2^k = 10^6 \times 2^{-20} = 10^6/1{,}048{,}576 \approx 0.95 \approx 1$. ✓ The choice of $k$ is precisely "make expected false-positive collisions equal to one".

With $L = \theta n^{\rho}$ and $p_1^k = n^{-\rho}$, the rate collapses to $\mathrm{TPR} = 1 - (1-n^{-\rho})^{\theta n^{\rho}} \approx 1 - e^{-\theta}$.

The $n$ cancels exactly — that is the point of choosing $L$ proportional to $n^\rho$. You get a fixed recall guarantee that does not degrade as the dataset grows, and you pay for it in $n^\rho$ tables rather than $n$ distance computations. $\rho$ governs cost and FPR, $\theta$ governs recall.

The family is $h_{ab}(x) = \left\lfloor \dfrac{a^\top x + b}{w}\right\rfloor$ with $a \sim \mathcal N(0, I_d)$ and $b \sim \mathrm{Unif}[0,w]$.

A, B: the pre-image of a fixed integer is $\{x : jw \le a^\top x + b < (j+1)w\}$ — the region between two parallel hyperplanes with normal $a$. An intersection of two half-spaces, hence convex.

C: the conditional probability $\max(0, 1-|\Delta|/w)$ increases in $w$ for every $\Delta$, so the average does too. Wider buckets, more collisions — for good and bad pairs alike, which is why $w$ must be tuned via $\hat\rho(w)$ rather than simply maximised.

D: $\Delta \sim \mathcal N(0, \|x-y\|^2)$ depends on the pair only through that norm. The collision probability is rotation- and translation-invariant.

Exact: $\mathrm{FPR} = 1 - (1 - 0.4^{10})^{20}$. Since $0.4^{10} = 1.0486\times10^{-4}$, this is $\approx 20 \times 1.0486\times10^{-4} = 2.097\times10^{-3}$. Times $8000$ gives $\mathbf{16.8 \approx 17}$.

The professor's slide quotes $\approx 20$, using the cleaner asymptotic $\theta n^{\rho} = 2 \times 10^{0.2435\times4} \approx 20$, which counts against all $n = 10^4$ points rather than only the $8000$ bad ones. Both are right at this level of precision — but if a paper gives you exact $k$, $L$ and a bad-point count, compute directly from $1-(1-p_2^k)^L$.

The full SVD is $A = U\Sigma V^\top$, and $\Sigma$ has the same shape as $A$: $U$ is $5000\times5000$, $\Sigma$ is $5000\times200$, $V^\top$ is $200\times200$. Only the top $200\times200$ block of $\Sigma$ is non-zero; the bottom $4800$ rows are all zeros. Option A is the shape in the thin/economy SVD — a real distinction, so read which one the question asks for.

C is false — and it is the classic swap. $A^\top A = V\Sigma^2V^\top$ gives the right singular vectors; $AA^\top = U\Sigma^2U^\top$ gives the left ones. Mnemonic: "$A^\top A$ is $n\times n$, lives in feature space, gives $V$."

B is true: both equal $\{\sigma_i^2 : \sigma_i > 0\}$; they differ only in how many extra zeros they carry ($AA^\top$ has $m-n$ more).

Eckart–Young: the error is $\sigma_{k+1}$ with $k = 3$, so $\sigma_4 = \mathbf{3}$.

Traps: $\sigma_3 = 6$ (off-by-one — the error is the first value you discard, not the last you keep) and $\sqrt{3^2+1^2} = \sqrt{10}$ (that would be the Frobenius-norm error, a different theorem that this course does not state).

$\ell = k + p = 25$, so $Q$ is $10^6 \times 25$ and $B = Q^\top A$ is $\mathbf{25} \times 5000$. That is the entire point: you run an exact SVD on a $25\times5000$ matrix rather than a $10^6\times5000$ one.

Note $B$ has $\ell$ rows, not $k$. The truncation to $k$ happens later, at the pull-back step.

A flat spectrum is precisely the failure mode Davis–Kahan predicts: $\|QQ^\top - U_kU_k^\top\| \lesssim \sigma_{k+1}/\sigma_k \approx 0.98$, i.e. no guarantee at all. Power iteration replaces that ratio with $0.98^{2q+1}$ — with $q = 10$, $0.98^{21} = 0.65$. Oversampling (A) helps the probability of a good sketch but does nothing about an intrinsically indistinguishable spectrum.

B is false: $A\Omega$ combines columns — $A\omega = \sum_i \omega_i a_i$ where $a_i$ are columns. (Row combinations would be $\Omega^\top A$.)

D is false: the error term $\epsilon$ degenerates as $p \to 0$ — with $\ell = k$ exactly there is no slack in the sketch. Oversampling is structurally required, not a tuning nicety.

$(AA^\top)^qA = U\Sigma^{2q+1}V^\top$, so the exponent is $2q+1 = 2(2)+1 = \mathbf{5}$.

Common slips: answering $2q = 4$, or $q = 2$. Remember the odd power comes from the trailing single $A$ — $q$ full "squarings" plus one.

Edges leaving $\{1,2\}$: $\{2,6\}$ and $\{2,4\}$. The edge $\{1,2\}$ is internal and does not count. So the cut is $\mathbf{2}$.

Check with the quadratic form, $f = (1,1,0,0,0,0)$: contributions from $\{2,6\}$ and $\{2,4\}$ are $1$ each, everything else $0$. ✓

The unnormalized Laplacian is $L = D - W$, with $D_{ii} = \sum_j w_{ij}$ on the diagonal and $-w_{ij}$ off it.

C is false, and it follows from B: a zero eigenvalue means $L$ is singular. This is exactly why the sparsification formula needs the pseudo-inverse $L^\dagger$ rather than $L^{-1}$.

D is the reason for B: $L\mathbf 1 = 0$ directly, since $L_{ii} = \sum_j w_{ij}$ and the off-diagonals are $-w_{ij}$.

Without it, the minimiser is $f = \tfrac{1}{\sqrt n}\mathbf 1$ with objective $0$ — "put everything in one cluster". Forcing orthogonality to $\mathbf 1$ deletes that direction and promotes the answer to $f_2$. C is a property of $L$ that holds regardless of any constraint.

A ring is not convex, so it can never be a Voronoi cell — k-means will slice both rings along a diameter regardless of initialisation. In the similarity graph, though, each ring is densely connected internally and weakly connected to the other, so the cheapest cut separates them, and the Fiedler vector finds it. Linear separability (C) is irrelevant: after the spectral embedding, the clusters become separable, which is precisely the point.

$w' = w/p = 0.6/0.2 = \mathbf{3}$ — you divide by $p$, which makes surviving edges heavier, not lighter. B multiplies instead, and is the natural wrong answer.

D is false, and this is the key conceptual point: unbiasedness holds for any $p_{ij} > 0$, since the $p$ and $1/p$ cancel. Effective resistance is chosen to control variance — so the estimate concentrates and the $(1\pm\epsilon)$ guarantee holds w.h.p., with few enough edges.

The bridge has the highest effective resistance — no alternative path exists, so removing it disconnects the graph and destroys the spectrum. It must be kept with probability $\approx 1$. Clique-internal edges are redundant ($p \propto 1/n$). C is a distractor: high weight does not imply high effective resistance — a heavy edge buried in a clique is still replaceable. D is the trap from the previous question.

$|F| = O(n\log n) = 10^6 \times \log(10^6)$. With natural log, $\ln 10^6 \approx 13.8$, giving $\approx 1.4\times10^7$; with $\log_2$, $\approx 20$, giving $2\times10^7$. Either way the exponent is $t = \mathbf{7}$.

That is a reduction of roughly four orders of magnitude — from $5\times10^{11}$ to $\sim10^7$ — which is the difference between "impossible" and "runs on a laptop".

The professor is deliberate about this distinction. NP-hard = no polynomial algorithm known, a complexity-theoretic barrier — that describes the balanced binary cut problem. Computationally expensive = polynomial but slow, which is what dense eigen-decomposition (C, D) is, and what sparsification addresses. The relaxation attacks the first problem; sparsification attacks the second.

Every quantity with a subscript $D$ is an expectation over the unknown distribution, so none of A, C, D is computable. Only the train error is an average over points in your hand.

This is the reason the decomposition is written as $\mathrm{er}_S[h_S] - \mathrm{er}_D^*$ and not the other way round: it starts from the one number you have and walks to the one you want.

A and B are the two nesting facts. D holds because the Bayes error is a probability. C is the trap: the generalisation error is the one unsigned term.

The May-2025 papers asked exactly A and B as an MSQ, with $\le 0$ versions as the distractors. They also asked separately whether the Bayes error is "non-negative", "zero" or "positive" — the answer is non-negative: it is zero when the classes do not overlap and positive when they do, so neither of the stronger claims is always true.

Densities: $f_1 = \tfrac14$ on $[-1,3]$; $f_0 = \tfrac12$ on $[-2,0]$. Priors are equal, so compare densities directly.

• $x\in[-2,-1)$: $f_1=0 < f_0=\tfrac12$ ⇒ $h^*=0$
• $x\in[-1,0]$: $f_1=\tfrac14 < f_0=\tfrac12$ ⇒ $h^*=0$
• $x\in(0,3]$: $f_1=\tfrac14 > f_0=0$ ⇒ $h^*=1$

So $h^*(x)=1$ exactly on $[0,3]$. Errors: class-$1$ points landing in $[-1,0]$, and class-$0$ points landing in $[0,\,0]$ (measure zero).

Trap: the overlap region is $[-1,0]$, and it is tempting to charge both classes for it. You only charge the class that $h^*$ gets wrong there — and $h^*$ says $0$ throughout $[-1,0]$, which is right for class $0$ and wrong for class $1$. This was Q179 on both May-2025 papers.

First the general test error. For $r\le1$ the circle sits inside the green disc, so it never mislabels a red point, and it misses the green points beyond $r$. Since $x\mid y=1$ is uniform on a unit disc, $P(\|x\|>r\mid y=1) = 1-r^2$:

(For the annulus, area $= 4\pi-\pi = 3\pi$, so the fraction inside radius $r$ is $(r^2-1)/3$.)

At $r=0.5$: $\mathrm{er}_D[h_{0.5}] = 0.5(1-0.25) = 0.375$.

The class minimum is at $r=1$ — the first branch decreases to $0$, the second increases from $0$ — so $\mathrm{er}_D[H] = 0$. Hence

And the approximation error is $0$: $h_1$ is perfect, so $\mathrm{er}_D[H]=0=\mathrm{er}_D^*$. That was the follow-up question, worth two marks for one line of reasoning — always check whether the class contains a zero-error classifier before grinding through an integral.

$h^*$ is defined by a threshold on $P(y=1\mid x)$, which is a property of $D$. The obstruction is informational, not computational — a distinction worth keeping crisp, because the ERM obstruction later in the syllabus is exactly the other way round (you have everything you need, but the optimisation is NP-hard).

A is that later fact, misapplied. C is close but wrong in kind: even infinite data gives you $D$ only in the limit, and the statement is about $D$ being unknown, not about sample size. D is false — $h^*$ lives in the class of all classifiers.

Hoeffding compares a sample average to its mean — a fixed number. When $h$ is chosen from the data, the "mean" $\mathrm{er}_D[h_S]$ moves with the sample too, and the inequality has nothing to say.

A is false ($z_i\in\{0,1\}$). C is false for a fixed $h$ — the points are i.i.d. and so are the losses. D is a real problem but a different one, and it is Unit 09's subject; the failure here bites even when $|H|=2$.

$h_S\in H$, so $A$ occurring forces the maximum over $H$ to be at least $\epsilon$: $A\subseteq B$, hence $P(A)\le P(B)$. This is the subset bound from Week 1, Lecture 5 — the same two-line utility inequality, reused eight weeks later.

C is wrong because $B$ can occur through some other classifier while $h_S$ itself is fine. The inclusion is genuinely one-directional.

Sanity check the sensitivity, because that is what gets examined: halving $\epsilon$ from $0.1$ to $0.05$ multiplied $n$ by $4$. Halving $\delta$ would have added only $200\ln 2 \approx 139$. Accuracy is quadratically expensive; confidence is logarithmically cheap.

B is the headline misreading. The theorem equates two errors; it never claims either is small. A class of two terrible classifiers satisfies it perfectly with both errors at $0.5$.

D is false — $|H|$ enters as $\log|H|$. Going from $10^3$ to $10^6$ classifiers triples the requirement rather than multiplying it by a thousand, which is why "finite but astronomically large" classes are still learnable.

C is the "algorithm-agnostic" property, and it is what makes the theorem usable at all: you prove it for the whole class, so you need not model the algorithm.

Expectation is linear whether or not the terms are independent, so the unbiasedness computation only needs each $(x_i,y_i)$ to have the same law, giving each term the same value $\mathrm{er}_D[h]$.

Independence is needed one step later, for Hoeffding. That is the clean way to remember the split: i.d. buys you unbiasedness, independence buys you concentration. This is the same division of labour as in the JL proof, where unbiasedness of $\|Mu\|^2$ came free and only the tail bound needed the coordinates to be independent.

Only contiguous runs are achievable. Count them: $\binom52 = 10$ runs of length $\ge2$, plus $5$ singletons, plus the empty (all-zeros) labeling:

Traps: $2^5 = 32$ is the count for all classifiers. $15$ forgets the all-zeros labeling. And the board's $(n+1)+n+\cdots+1 = 21$ is a valid upper bound of the right order but over-counts — do not use it when the question says "maximum number of labelings".

Sanity check against the VC dimension: at $n=2$ the formula gives $3+1=4=2^2$ (shattered ✓); at $n=3$ it gives $6+1=7<8$ (not shattered ✓). Consistent with $\mathrm{VCdim}=2$.

A cuboid is one interval per coordinate: $[a_1,b_1]\times[a_2,b_2]\times[a_3,b_3]$, so $2\times3 = \mathbf{6}$ free parameters, and the VC dimension matches.

$\ge6$: put the six points at $\pm e_1, \pm e_2, \pm e_3$ — the six face centres. Any subset can be captured, because each of the six box faces can be pushed independently to include or exclude its own point.

$<7$: given any $7$ points, take the six achieving the extreme coordinate in each of the six directions (a point may serve twice; that only helps). Label those $1$ and some remaining point $0$. The tightest box containing all six extremes contains every other point, so the $0$ cannot be excluded.

Generalises immediately: axis-parallel boxes in $\mathbb{R}^d$ have VC dimension $2d$, and the $\mathbb{R}^2$ case $\mathrm{VCdim}(H_{\mathrm{apr}}) = 4$ is the professor's worked example.

The right object to count is sign changes. A non-zero polynomial of degree $\le4$ has at most $4$ real roots, so its sign can flip at most $4$ times along the line — carving $\mathbb{R}$ into at most $5$ constant-sign blocks.

$\ge5$: take any $5$ points. Any labeling of them needs at most $4$ sign changes; drop a root into each gap where the label flips and take $p(x) = \pm\prod(x-r_j)$ (pad with extra roots outside the data, or a positive constant factor, to fix the leading sign). Degree stays $\le4$. ✓

$<6$: for any $6$ points, ask for the fully alternating labeling $+,-,+,-,+,-$. That is $5$ sign changes, so it needs $5$ roots — impossible at degree $4$. ✓

So $\mathrm{VCdim} = 4+1 = \mathbf 5$, and the general rule is $\deg \le m \Rightarrow \mathrm{VCdim} = m+1$. Check it at $m=1$: $\mathrm{sign}(ax+b)$ is a threshold rule, VC dimension $2$ — which matches linear-with-bias in $\mathbb{R}^1$. ✓

Trap: $\mathcal P_4$ has $5$ coefficients and the answer is also $5$, so the parameter-count heuristic gets the right number here — but the reason is the root count, and that is the argument to write down.

A union of three intervals can produce at most three positive runs.

$\ge6$: take $6$ points. The worst labeling has positives at alternating positions — at most $3$ separate runs of $1$s among $6$ points — and three intervals can cover exactly that. Every labeling of $6$ points needs at most $3$ positive runs, so all $2^6$ are reachable. ✓

$<7$: for any $7$ points ask for $+,-,+,-,+,-,+$ — four positive runs, more than three intervals can produce. ✓

So $\mathbf 6$, matching the $6$ free endpoints. General rule: a union of $m$ intervals has VC dimension $2m$. (Q172 on both May-2025 papers.)

The classifier only ever sees $\|x\|$, so it is a threshold rule on a single non-negative number — and thresholds are monotone: if the nearer point is labelled $1$, so is everything nearer still.

$\ge1$: one point $x$ with $\|x\|=1$; take $r=2$ for label $1$, $r=0$ for label $0$. ✓

$<2$: for any two points, say $\|x_1\| \le \|x_2\|$, ask for $h(x_1)=0$, $h(x_2)=1$. Any circle containing $x_2$ contains $x_1$. ✓ (If the norms are equal, ask for different labels — impossible for the same reason.)

Trap: "circle in the plane" invites the answer $3$ (VC dimension of arbitrary discs) or $2$ (a parameter count of centre-plus-radius). Centring at the origin removes both centre parameters and leaves a one-dimensional monotone family. Always read what is being held fixed. (Q174 on both May-2025 papers.)

Shattering $k$ points requires $2^k$ distinct labelings, and each labeling needs at least one classifier, so $2^k \le |H|$:

Traps: $7$ would need $128 > 100$ classifiers. $100$ and $50$ ignore the exponential. And note the direction: this is an upper bound — the actual VC dimension of a specific $100$-element class could be anything from $0$ to $6$.

This is also the sanity check on the whole unit: $\mathrm{VCdim} \le \log_2|H|$ is exactly why "$\log|H| \to d$" is the right substitution in the sample-complexity formula. (Q183 on both May-2025 papers.)

Each of the $5$ points independently takes one of $3$ labels: $3^5 = \mathbf{243}$.

The binary case $2^n$ generalises to $c^n$ for $c$ classes — a one-line question testing whether you know why $2^n$ appears in the bound, rather than having memorised the symbol. Trap: $5^3 = 125$ inverts base and exponent; $2^5=32$ forgets there are three classes. (Q171 on both May-2025 papers.)

Write both in exponential form: $2^ne^{-2n\epsilon^2} = e^{n(\ln 2 - 2\epsilon^2)}$, which grows whenever $\epsilon^2 < \tfrac{\ln 2}{2}$ — i.e. for every $\epsilon$ you would actually care about. Meanwhile $n^de^{-2n\epsilon^2} = e^{d\ln n - 2n\epsilon^2}$, and $d\ln n$ is beaten by $2n\epsilon^2$ for every fixed $d$ and $\epsilon$.

A is false for small $n$ and is anyway not the point — the issue is asymptotic rate, not pointwise size. C is plainly false. D confuses the mechanism: Hoeffding is applied per labeling, and the labeling count is exactly what was fixed.

The definition is ∃ a shatterable set of size $k$ and ∀ larger sets, not shatterable.

B is too strong and is the most common misreading: in $\mathbb{R}^2$, three collinear points cannot be shattered by lines through the origin, yet the VC dimension is still $2$. Degenerate configurations are allowed to fail; you only need one good configuration.

D is too weak. "Some set of $k+1$ points fails" is compatible with a different set of $k+1$ points succeeding, which would push the dimension up. You need all of them to fail.

ERM minimises $\mathrm{er}_S[h] = \frac1n\sum\mathbb 1[h(x_i)\ne y_i]$, the misclassification rate — so it maximises $1 - \mathrm{er}_S = $ accuracy, and nothing else.

F1 and precision weight the two error types asymmetrically and require a different objective (and are exactly why ERM behaves badly on imbalanced data). Log loss is a surrogate — a convex stand-in you minimise because the $0$–$1$ loss is NP-hard — so it is a means, not the target. This opened the 2025 T3 end term.

Write out what each point demands of $w = (w_1,w_2)$:

Rows 3 and 4 are directly contradictory, so at least one error is unavoidable — the lower bound is $1/4$. Rows 1 and 2 force $w_2\ge w_1$ and $w_1\ge w_2$, hence $w_1 = w_2 = t$.

Take $t > 0$, e.g. $w = (1,1)$: the first two points give $w^\top x = 0 \ge 0$ ⇒ predict $1$ ✓✓; $(-1,-1)$ gives $-2 < 0$ ⇒ predict $0$ ✓; $(1,1)$ gives $2\ge0$ ⇒ predict $1$ ✗. Exactly one mistake:

Traps: $0$ assumes a linear classifier can always fit four points — this is XOR-shaped and it cannot. $0.5$ is what you get if you miss that $w=(1,1)$ salvages the first three. And the tie-break matters: the convention $w^\top x \ge 0 \Rightarrow 1$ is what makes the two boundary points come out right. (Q9 on the 2025 T3 end term.)

Keep four positive points: the leftmost, rightmost, lowest and highest. Decompression rebuilds the bounding rectangle from their coordinates, and because the true labels came from some rectangle, that bounding box contains every positive and excludes every negative.

Same number as $\mathrm{VCdim}(H_{\mathrm{apr}}) = 4$ — and the intervals case matches too ($2$ and $2$). Whether that coincidence is a theorem is the open sample compression conjecture. (Q10 on the 2025 T3 end term; asked as an MSQ about $H_{\mathrm{int}}$ on both May-2025 papers.)

A is false, and it is the central point of the unit. The approximation error involves no sample at all — both terms are population quantities. Collecting a billion more points changes it by exactly zero. This is the one gap data cannot buy your way out of.

B: if the Bayes classifier is itself in $H$ then $\mathrm{er}_D[H] = \mathrm{er}_D^*$. C: a minimum over a superset can only fall. D: SRM searches a nested family precisely to let the approximation error fall while keeping the complexity penalty honest.

The $0$–$1$ loss is non-convex and piecewise constant — gradients are zero almost everywhere and uninformative elsewhere. Hinge, logistic and exponential losses are convex upper bounds that restore tractability.

B is the opposite of the truth: ERM is statistically excellent here (that is the estimation-error bound). C is a non-sequitur — least-squares regression also searches an infinite set and is solved in closed form. D is factually wrong: $\mathrm{VCdim}(H_{\mathrm{lin}}) = d$, finite, which is exactly why the statistical side works.

Keep the two obstructions apart: the Bayes classifier fails on information; ERM fails on computation.

The chain ends at $|\mathrm{er}_D[\hat h]-\mathrm{er}_D[H]| \le 2\max_h|\mathrm{er}_S[h]-\mathrm{er}_D[h]|$. So the event "estimation error $\ge\epsilon$" implies "$2\max \ge \epsilon$", i.e. "$\max \ge \epsilon/2$" — the $2$ is divided across.

D is the tempting near-miss: two classifiers do appear, and that is why the factor is $2$ — but the question asks why $\epsilon$ is halved, which is the algebraic consequence of the bound, not the count of classifiers. Practical upshot: since $n$ scales as $1/\epsilon^2$, the halving costs a factor of four in sample size.

A is the whole content of the definition — otherwise you could keep nothing and declare victory. B is what makes it compression rather than model fitting: you select points, you do not manufacture them.

C is the known direction. D is the open conjecture — unresolved for thirty-plus years — and any option asserting it as known is wrong.

Write $p = \frac{e^{0.1}}{1+e^{0.1}} = \frac{1.10517}{2.10517} = 0.52498$ (truth) and $q = \frac{1}{1+e^{0.1}} = 0.47502$ (flip). Now match each coordinate:

Independence across people, so multiply:

Method: compare $X$ and $Y$ coordinate by coordinate, count agreements $a$ and disagreements $f$, then answer $p^{a}q^{f}$. That is all these questions ever are. Traps: mixing up which of $p,q$ is bigger ($p > \tfrac12$ always, for $\epsilon > 0$), and forgetting that $Y$ is the intermediate vector — no debiasing is involved. (Q11 on the 2025 T3 end term.)

Agreements at positions $1, 3, 4$ (three truths); disagreements at $2$ and $5$ (two flips):

The accepted range on the paper was $0.030$ to $0.035$. Worth a sanity check: the all-ones pattern from a data vector with three ones needs $3$ truths and $2$ lies, and since $p\approx q\approx\tfrac12$ at this tiny $\epsilon$, the answer must be near $2^{-5} = 0.031$. ✓ (Q190 / Q273 on the May-2025 papers.)

Sensitivity of the average of $n$ bits is $\Delta = 1/n = 1/200$. The Laplace spread is

Traps: $\Delta = 1$ (that is the sensitivity of the sum, not the average — the $1/n$ is the entire point); and multiplying by $\epsilon$ instead of dividing. Remember the two directions: more people → less noise; stricter privacy (smaller $\epsilon$) → more noise.

A: the deviation is $O(1/(\epsilon\sqrt n))$, so larger $\epsilon$ ⇒ smaller error. B is backwards — privacy is $e^\epsilon$, and a larger ratio means the adversary distinguishes $x$ from $x'$ more easily. C: at $\epsilon=0$ the flip probability is exactly $\tfrac12$, so $y_i$ is a fair coin independent of $x_i$ — perfect privacy, zero utility.

D is the trap, and it is a good one. $n$ appears only in the utility bound; the privacy proof cancels the other $n-1$ factors and never mentions $n$ at all. Surveying more people does not make any individual more private — it makes the estimate better. That asymmetry is what lets you set $\epsilon$ and $n$ independently.

Randomized response has a discrete output space, so a per-pattern statement is meaningful there. The Laplace mechanism outputs a real number, and $P(M(x) = c) = 0$ for every $c$ — so a per-output ratio is $0/0$ and says nothing. Quantifying over measurable sets is the fix.

A is the near-miss: in the discrete case the two formulations are equivalent, because for disjoint outcomes bounding every ratio bounds the ratio of the sums. So the set version is not stronger — it is the version that still means something when the output is continuous.

Basic composition: $k$ mechanisms each $(\epsilon,\delta)$-DP compose to $(k\epsilon, k\delta)$-DP. So $\epsilon_{\text{total}} = 5\times0.2 = \mathbf{1.0}$, and $\delta_{\text{total}} = 5\times10^{-6}$.

Contrast with advanced composition, whose leading term is $\epsilon\sqrt{k\log(1/\delta')}$ — the $k$ becomes $\sqrt k$. That is the entire reason DP-SGD uses Gaussian noise: releasing a noisy gradient at every step is composition with $k$ = number of iterations, and $k\epsilon$ exhausts the budget in a handful of steps while $\epsilon\sqrt k$ survives thousands.

Trap: advanced composition is available for the Gaussian mechanism, not for Laplace — for Laplace only the basic bound holds.

Laplace uses $\ell_1$ sensitivity: $\Delta_1 = \sum_{i=1}^{100}\tfrac1n = \tfrac{100}{n}$, so the spread is $\tfrac{100}{n\epsilon}$ — linear in $d$.

Gaussian uses $\ell_2$: $\Delta_2 = \sqrt{100\cdot\tfrac1{n^2}} = \tfrac{10}{n}$, and the standard deviation carries $\sqrt{\ln(1/\delta)}$, giving $\tfrac{10\sqrt{\ln(1/\delta)}}{n\epsilon}$ — $\sqrt d$.

Tenfold less noise at $d=100$, for the price of a $\delta$ and a logarithmic factor. C is the misconception that the two mechanisms differ only cosmetically; the norm they measure sensitivity in is exactly what differs, and it is what produces the $d$ versus $\sqrt d$ gap.

Revenue at $p=10$: all three buy, $10\times3 = 30$. Revenue at $p=30$: only the $500$-buyer, $30\times1 = 30$. Identical scores, and the mechanism's probability depends on the score alone:

A is what the Laplace approach would do — noise around $p^\star=500$ makes $30$ far likelier — and that mismatch is precisely the defect the exponential mechanism was built to remove. D is wrong because $\epsilon$ scales both exponents identically, so the ratio is $1$ for every $\epsilon$.

B is exactly the trap, and it is the reason the model exists. Trust concerns the curator, not the world. An adversary who knows $n-1$ records and sees the exact average subtracts and recovers the last one — total breach in one arithmetic step. What is trusted is who holds the data; what is dangerous is what gets published.

C is the structural difference: one perturbation instead of $n$. D is its consequence: $O\!\left(\frac{1}{\epsilon n}\right)$ against $O\!\left(\frac{1}{\epsilon\sqrt n}\right)$ — quadratically better, so quadratically fewer people are needed for the same accuracy.

The canonical case is the Netflix Prize: an anonymised user × movie ratings matrix was released, and researchers de-anonymised users by correlating it with public IMDb reviews. Removing identifiers does not remove the pattern, and a pattern plus a second database is an identity.

A and C describe the cryptographic objection and the too-much-noise objection respectively. The point about anonymisation is sharper: it offers no guarantee at all — it is heuristic rather than provable, which is why the course replaces it with a definition you can prove theorems about.

The approximated object goes on the outside; the approximation is sandwiched. $H$ approximates $G$, so $\theta^\top L_H\theta$ sits in the middle with $(1\pm\epsilon)\theta^\top L_G\theta$ as the bounds.

Traps: A has the roles reversed (a statement about $G$ approximating $H$, which is not what "$H$ is a sparsification of $G$" means). C and D each mix $G$ and $H$ across the two bounds, so they are not even a sandwich — they compare a quantity to itself scaled two different ways. Sanity check any candidate by setting $\epsilon=0$: the correct form must collapse to $\theta^\top L_H\theta = \theta^\top L_G\theta$. Only B does.

Each point takes one of $3$ labels, independently: $3^5 = \mathbf{243}$.

This tests whether you understand where the $2^n$ in the uniform-convergence argument comes from. Traps: $5^3=125$ (base and exponent swapped); $2^5=32$ (forgot three classes); $15 = 5\times3$ (added instead of exponentiated).

Three intervals produce at most three positive runs on a sorted set of points.

$\ge6$: take any $6$ points. Whatever the labeling, its $1$s form at most $3$ maximal runs (you cannot fit $4$ separated runs into $6$ positions), and each run is covered by one interval. All $2^6$ labelings are reachable. ✓

$<7$: for any $7$ points ask for $+,-,+,-,+,-,+$ — four positive runs, one more than three intervals can supply. ✓

So $\mathrm{VCdim} = \mathbf 6$, matching the $6$ free endpoints. Trap: "three intervals, each of VC dimension $2$" invites $2$ or $3$; the parameter count $2m$ is the right instinct.

The best rank-1 approximation keeps only the top singular triplet:

Trace $= 3+0+0 = \mathbf 3$.

Two shortcuts to notice. First, the messy $\tfrac1{\sqrt2}$ block is in $u_2,u_3$ — completely irrelevant to a rank-1 approximation. Second, the question already tells you $B$ is diagonal, which confirms you only need $u_1v_1^\top$. Traps: $6 = 3+2+1$ (the trace of $A$ itself, i.e. keeping everything); $2$ or $1$ (wrong singular value — $\sigma_1$ is the largest).

The classifier reads only $\|x\|$, so it is a monotone threshold on one number: if a point is labelled $1$, every point nearer the origin is too.

$\ge1$: a single point at $\|x\|=1$ takes label $1$ with $r=2$ and label $0$ with $r=0$. ✓

$<2$: for any two points with $\|x_1\|\le\|x_2\|$, the labeling $h(x_1)=0$, $h(x_2)=1$ is impossible — a circle containing the farther point contains the nearer one. ✓

Traps: $3$ is the VC dimension of arbitrary discs in $\mathbb{R}^2$; $2$ is a parameter count that wrongly includes a centre. Centring at the origin is doing all the work — it removes two parameters and leaves a one-dimensional monotone family. Read what is held fixed.

Identify each by which two levels it compares, and the names follow:

• (1) best-in-$H$ vs Bayes → how well $H$ can approximate the optimum → approximation
• (2) train vs test for the same classifier → does it generalise beyond the sample → generalisation
• (3) what you got vs best-in-$H$ → how well the algorithm estimated the best member → estimation

The reliable tell: the generalisation term is the only one containing $\mathrm{er}_S$, and the approximation term is the only one containing $\mathrm{er}_D^*$. Spot those two and the third is forced — you never need to recall all three names at once.

Both are "a minimum over a smaller set cannot beat a minimum over a bigger one":

• $\mathrm{er}_D^* = \min$ over all classifiers $\le \min$ over $H$ $= \mathrm{er}_D(H)$ ⇒ A.
• $\mathrm{er}_D(H) = \min_{h\in H}\mathrm{er}_D(h) \le \mathrm{er}_D(h_S)$ since $h_S\in H$ ⇒ B.

C and D are the negations. Both quantities can be zero (if $h^*\in H$, or if the algorithm happens to return the best member), which is consistent with $\ge0$ — a common source of doubt on this MSQ. Note that the generalisation term is deliberately absent from all four options, because it is the one with no guaranteed sign.

$\mathrm{er}_D^*$ is a probability, so $\ge0$ always. The phrase "most appropriate" is doing real work here: B and C are each true only sometimes.

Zero when the class-conditional densities have disjoint support (the concentric-circles example on the T3 paper — $\mathrm{er}_D^*=0$). Positive when they overlap (the exponential example — $\mathrm{er}_D^*=0.375$). Only "non-negative" holds for every $D$, and D is impossible.

The wider lesson for MCQs on this paper: when several options are ordered by strength, the answer is the weakest claim that is always true, not the most impressive-sounding one.

Priors are equal, so compare densities. $f_1 = \tfrac{1}{3-(-1)} = \tfrac14$ on $[-1,3]$; $f_0 = \tfrac{1}{0-(-2)} = \tfrac12$ on $[-2,0]$.

B is the trap, and it is the good one. It says $h^*=1$ throughout the support of $x\mid y=1$ — i.e. "predict $1$ wherever class $1$ is possible". But on $[-1,0]$ both classes are possible and class $0$ is twice as dense, so $h^*$ must say $0$ there. Overlap is resolved by which density is larger, not by which is non-zero.

The narrower uniform has the higher density — $U[-2,0]$ packs the same mass into half the width — which is exactly why it wins the contested region. Worth sketching: two rectangles of heights $\tfrac14$ and $\tfrac12$.

$h^*$ says $1$ exactly on $[0,3]$. Charge each class only where $h^*$ gets that class wrong:

Class $1$: $x\sim U[-1,3]$, so $P(x<0) = \tfrac{1}{4}$ (length $1$ out of $4$). Class $0$: $x\sim U[-2,0]$, so $P(x\ge0)=0$ (a single point, measure zero).

Trap: charging both classes for the overlap region $[-1,0]$ gives $0.5\cdot\tfrac14 + 0.5\cdot\tfrac12 = 0.375$ — wrong, because $h^*$ is correct for class $0$ throughout that region. The Bayes error counts the mass of the losing density in each region, never both.

Cross-check the geometry: on $[-1,0]$ the two density heights are $\tfrac14$ and $\tfrac12$; the Bayes error is the area under the lower curve, $\tfrac14\times1 = 0.25$, times the prior $0.5$, giving $0.125$. ✓

(180) The feature $x_1+x_2$ takes value $0$ at $(0,0)$ and $1$ or $2$ at the other three points. So the threshold $\theta=1$ separates them perfectly:

$\theta^\star = \mathbf 1$. (Check the neighbours: $\theta=0$ predicts $1$ everywhere — one error; $\theta=2$ misses $(1,0)$ and $(0,1)$ — two errors.)

(181) Zero errors out of four, so $\mathrm{er}_S = \mathbf 0$.

(182) Generalisation error $= \mathrm{er}_S[h_1] - \mathrm{er}_D[h_1] = 0 - \mathrm{er}_D[h_1]$, so compute the test error. $h_1$ predicts $0$ only at $(0,0)$, so:

So $|$generalisation error$| = |0-0.125| = \mathbf{0.125}$.

What the two given PMF entries are for: $P((0,0)\mid y=0)=1$ means class $0$ always lands on $(0,0)$, so $h_1$ never errs on class $0$ — that whole term vanishes. $P((0,0)\mid y=1)=0.25$ is the only other number needed. The remaining three probabilities under $y=1$ sum to $0.75$ but are never used individually. The paper hands you exactly two entries and no more; if you find yourself wanting a third, you have taken a wrong turn.

Trap: a zero train error tempts you to answer $0$ for the generalisation error too. Train and test errors are different objects — a perfect fit on four points says nothing about a distribution where $25\%$ of class-$1$ mass sits on the one point you label $0$.

Shattering $k$ points means realising all $2^k$ labelings, and each labeling needs at least one distinct classifier:

Check: $2^6 = 64 \le 100$ ✓, $2^7 = 128 > 100$ ✗.

This is the general fact $\mathrm{VCdim}(H)\le\lfloor\log_2|H|\rfloor$ — and it is exactly why "$\log|H| \to d$" is the right substitution when moving from the finite to the infinite uniform-convergence theorem. Traps: $100$ and $50$ ignore the exponential; $7$ forgets to floor.

VC dimension $2$: two points are shattered (interval over both, over each singly, over neither); three points $x_1<x_2<x_3$ defeat it with $+,-,+$, since an interval containing $x_1$ and $x_3$ must contain $x_2$.

Compression size $2$: keep the two extreme positive points; the interval they span reproduces every label.

B and D are $H_{\mathrm{apr}}$'s numbers (axis-parallel rectangles) — the paper is checking that you have not merged the two classes. The safest way to keep them apart: count free endpoints. An interval has $2$ ($a,b$); a rectangle has $4$ ($a,b,c,d$). Both the VC dimension and the compression size follow that count for these two classes.

$a^\top r = \sum_i a_ir_i$ is a linear combination of independent $\mathcal N(0,1)$ variables, so it is Gaussian with

So $a^\top r \sim \mathcal N(0, \|a\|^2)$ — the single fact the entire JL proof rests on, and the same one that makes $\Delta = a^\top(x-y)\sim\mathcal N(0,\|x-y\|^2)$ in the LSH collision analysis.

Traps: $2$ for the variance is $\|a\|$ rather than $\|a\|^2$. And the $-1$ must be squared — anyone who computes $\sum a_i = 2$ and reports that has confused the mean with a sum of coefficients. Note the mean is $0$ regardless of $a$; only the variance sees the vector.

The construction, read off the wording. "Exact match" within a table means all $k$ hashes agree — an AND, giving $p^k$. "At least one of $L$ tables" is an OR, so take the complement of "all $L$ fail": $1-(1-p^k)^L$.

TPR uses near pairs, which collide with probability $\ge p_1$: $1-(1-p_1^k)^L$. FPR uses far pairs, probability $\le p_2$: $1-(1-p_2^k)^L$. C and D are the miss probabilities — the complements — and are the standard distractor pair.

(189) No. Since $p_1>p_2>0$ we get $p_1^k > p_2^k$, hence $1-p_1^k < 1-p_2^k$, hence $(1-p_1^k)^L < (1-p_2^k)^L$, hence TPR $>$ FPR — strictly, for every $k$ and $L$. The paper says "avoid all approximations and use the formulae", which is a direct instruction to run this monotonicity chain rather than reason from the $\rho$ approximations.

Why the answer is reassuring: if TPR could equal FPR the scheme would be worthless — the whole point of amplification is that AND and OR move both rates but never let the far curve catch the near one. Every step of $t\mapsto t^k$ and $t\mapsto 1-(1-t)^L$ is strictly increasing.

Truth probability $p = \frac{e^{0.1}}{1+e^{0.1}} = 0.52498$; flip probability $q = \frac{1}{1+e^{0.1}} = 0.47502$. Compare coordinatewise:

Accepted range on the paper: $0.030$–$0.035$.

The recipe, once and for all: count agreements $a$ and disagreements $f$ between $X$ and the requested $Y$, then answer $p^aq^f$ with $a+f=n$. Independence across people is what lets you multiply.

Traps: swapping $p$ and $q$ (remember $p>\tfrac12$ whenever $\epsilon>0$); and reading $Y$ as the debiased vector $Z$ — the question says "intermediate", which is the reported bits before any debiasing. Sanity check: at $\epsilon=0.1$ both $p,q\approx\tfrac12$, so any five-bit pattern must have probability near $2^{-5}=0.031$. ✓

$h_S^{\mathrm{ERM}} = \arg\min_{h\in H}\mathrm{er}_S[h]$ and $\mathrm{er}_S$ is the fraction misclassified, so ERM maximises $1-\mathrm{er}_S = $ accuracy.

F1 and precision weight false positives and false negatives differently and would require a different objective — which is precisely why plain ERM behaves poorly on imbalanced data. Log loss is the subtlest distractor: it is a surrogate, a convex stand-in minimised because the $0$–$1$ loss is NP-hard. Minimising it is a means to the end, not the end ERM is defined by. And note the wording "by design" — the question is about the definition, not about downstream behaviour.

A and B are free: the question tells you $f$ is linear, and $f(x)=Mx$ satisfies both by definition of matrix multiplication. Do not overthink them.

The whole question is C versus D, and this is the single most important distinction in the JL unit. The lemma guarantees distortion bounds on the $\binom n2$ pairs of the dataset — that is what the union bound was taken over, and where the $\log n$ in $k\in O(\log n/\epsilon^2)$ comes from. Extending to all of $\mathbb{R}^d$ would be a union bound over uncountably many pairs, and it is false: since $k<d$, the map has a non-trivial kernel, so there exist $x\ne y$ with $f(x)=f(y)$ and a distortion of $-100\%$.

That is Step 1 of the unit — no exact isometry exists — reappearing as a wrong option. If you ticked D you also contradicted the very first lemma of the JL derivation.

Near pairs collide often; far pairs collide rarely. Close ($\le r$) ⇒ probability at least $p_1$ (the big one). Far ($\ge cr$) ⇒ probability at most $p_2$ (the small one).

C and D are the same two implications with the conclusions swapped — a family satisfying them would hash distant points together and nearby points apart, which is worse than useless.

Two things to carry into the exam. First, memorise the pairing, not the symbols: small distance goes with the large probability. Second, note what the definition says about the annulus $r < \|x-y\| < cr$: nothing at all. Every LSH regime question turns on computing $cr$ and checking which of the three zones the distance lands in.

A is the definition. C follows because every row of $L$ sums to zero, so $L\mathbf1 = 0$ — the all-ones vector is an eigenvector with eigenvalue $0$.

D is the mark-loser: $L$ is positive semi-definite, never positive definite. The two facts are directly linked — a zero eigenvalue means $L$ is singular, so it cannot be PD. C and D are logically incompatible, and spotting that is faster than recalling either fact separately.

B fails the row-sum test instantly (its diagonal would be $-D_{ii}$ and its off-diagonals $+w_{ij}$, giving $L=-L_{\text{true}}$, which has non-positive eigenvalues). And note the practical consequence of C: the sparsification formula needs the pseudo-inverse $L^\dagger$, because $L^{-1}$ does not exist.

Eckart–Young: $\|A-A_k\|_2 = \sigma_{k+1}$. With $k=3$, that is $\sigma_4 = \mathbf 1$.

The off-by-one is the entire question. $\sigma_{k+1}$ is the first singular value you discard, not the last you keep. Sorted descending: $\sigma_1=1000$, $\sigma_2=100$, $\sigma_3=10$ (kept), $\sigma_4=1$, $\sigma_5=0.1$ (discarded).

Traps: $10$ is $\sigma_3$, the last kept. $0.1$ is $\sigma_5$, the smallest. $\sqrt{1^2+0.1^2}\approx1.005$ is the Frobenius error, and the question says $\|\cdot\|_2$ — spectral norm, which is a single singular value. The values are spaced by factors of ten precisely so that every wrong answer is unmistakably distinguishable.

An interval labels a contiguous run of the sorted points as $1$. Count the achievable runs:

equivalently $\frac{n(n+1)}{2}+1$ at $n=5$.

Traps. $32=2^5$ is the count for all classifiers, and is what you get if you forget the class is restricted. $15$ drops the all-zeros labeling — easy to miss, since it comes from intervals that avoid every point. And $21 = 6+5+4+3+2+1$ is the professor's board count $(n+1)+n+\cdots+1$, which is a legitimate $O(n^2)$ upper bound for the uniform-convergence argument but over-counts here, because it recounts the all-zeros labeling once per left-endpoint position. When a question asks for the maximum number of labelings, it wants the exact figure.

Cross-check against $\mathrm{VCdim}(H_{\mathrm{int}})=2$: at $n=2$ the formula gives $3+1=4=2^2$ (shattered ✓); at $n=3$, $6+1=7<8$ (not shattered ✓).

A cuboid is $[a_1,b_1]\times[a_2,b_2]\times[a_3,b_3]$: one interval per axis, $2\times3 = \mathbf 6$ free parameters.

$\ge6$: place the points at the six face centres $\pm e_1,\pm e_2,\pm e_3$. Each of the six faces of the box can be slid independently, so each point can be included or excluded on its own — all $2^6$ labelings. ✓

$<7$: for any $7$ points, select the six that achieve the extreme coordinate in each of the six directions (one point may hold two extremes; that only makes it easier). Label those six $1$ and any remaining point $0$. The smallest cuboid containing all six extremes contains everything, so the $0$ cannot be excluded. ✓

The hint is in the question: the professor derived $\mathrm{VCdim}(H_{\mathrm{apr}})=4$ in $\mathbb{R}^2$, and $4 = 2\times2$. The general rule is $2d$. Traps: $3$ (dimension of the space); $4$ (the $\mathbb{R}^2$ answer, not generalised); $8$ (vertices of a cube).

Turn each labelled point into a constraint on $w=(w_1,w_2)$, using $h_w(x)=1$ iff $w^\top x\ge0$:

Rows 3 and 4 demand $w_1+w_2$ be both positive and negative — at least one error is forced, so $\mathrm{er}_S \ge \tfrac14$. Rows 1 and 2 force $w_1=w_2=t$.

Take $t>0$, say $w=(1,1)$: the two positives give $w^\top x = 0 \ge 0$ ⇒ predict $1$ ✓✓; $(-1,-1)$ gives $-2<0$ ⇒ predict $0$ ✓; $(1,1)$ gives $2\ge0$ ⇒ predict $1$ ✗. Exactly one error:

Traps. $0$ assumes a homogeneous linear classifier can always fit four points — the labels here are XOR-shaped and it cannot. $0.5$ is what you get by giving up after seeing rows 3 and 4 conflict, without checking that $w=(1,1)$ rescues the other three. And the tie-break convention matters: the two positive points sit exactly on the boundary $w^\top x = 0$, and the rule $\ge 0 \Rightarrow 1$ is what makes them correct. Flip that convention and the answer becomes $0.75$.

Keep four positive points: leftmost, rightmost, lowest, highest. Decompression rebuilds the bounding rectangle from their coordinates; because the labels came from some rectangle, that box contains every positive and excludes every negative.

Equals $\mathrm{VCdim}(H_{\mathrm{apr}}) = 4$ — as does the intervals pair ($2$ and $2$). Whether that coincidence is a theorem is the open sample compression conjecture: compression size $k$ implies VC dimension $O(k)$, but the converse has been unresolved for over thirty years. A one-mark question if you know the number, and unanswerable if you do not.

$p = \frac{e^{0.1}}{1+e^{0.1}} = \frac{1.10517}{2.10517} = 0.52498$ (report truth); $q = \frac{1}{1+e^{0.1}} = 0.47502$ (flip). Compare coordinatewise:

Accepted range: $0.03$–$0.09$ — generous, because the graders expected sign confusion between $p$ and $q$. (Note $q^2p^2$ is the same number here, so the two-and-two split is self-correcting; a three-and-one split would not be.)

Traps: using $e^\epsilon = e^{0.1}$ as a probability rather than forming the ratio; and treating $Y$ as the debiased $Z$. Sanity check: with $\epsilon$ this small the mechanism is nearly a fair coin, so any four-bit pattern must have probability near $2^{-4}=0.0625$. ✓

The quantity to count is sign changes. A non-zero polynomial of degree $\le4$ has at most $4$ real roots, and its sign can only flip at a root — so along the real line it has at most $4$ flips, i.e. at most $5$ constant-sign blocks.

$\ge5$: take any $5$ points $x_1<\cdots<x_5$ and any labeling. Reading left to right, the label changes at most $4$ times. Put a simple root in each gap where it changes, take $p(x)=\pm\prod_j(x-r_j)$, and pad with extra roots outside the data range (or an overall sign) to fix the leftmost sign. Degree stays $\le4$. ✓

$<6$: for any $6$ points ask for the fully alternating labeling $+,-,+,-,+,-$. That is $5$ sign changes, requiring $5$ roots — impossible at degree $4$. ✓

So $\mathrm{VCdim} = 4+1 = \mathbf 5$, and the general rule is $\deg\le m \Rightarrow \mathrm{VCdim} = m+1$. Check the base case: $\mathrm{sign}(ax+b)$ is a one-dimensional threshold rule with VC dimension $2$, matching linear-with-bias in $\mathbb{R}^1$. ✓

Traps. $4$ is the degree, and it is the answer to a subtly different question. $9$ counts the dimension of a degree-$4$ feature map in two variables. The $5$-coefficient parameter count happens to agree here, which makes it a dangerous crutch — the argument to write down is the root count, because that is what generalises.

$\ge7$: place $7$ points on a circle. For any labeling, the positives form at most $3$ contiguous arcs (with $7$ points you cannot get $4$ separated arcs), and a triangle can be chosen so that each of its three sides cuts off one negative arc, keeping all positive arcs inside. ✓

$<8$: with $8$ points on a circle, label them alternately $+,-,+,-,+,-,+,-$. That is $4$ separated positive arcs, and a triangle's boundary is only $3$ lines — each line can exclude at most one arc of negatives, so $4$ separated positive groups cannot all be captured. ✓

Why this is a good zero-mark question. A triangle has $6$ parameters (three vertices in $\mathbb{R}^2$), so the parameter-count heuristic predicts $6$ — and it is wrong. The extra unit comes from the fact that a triangle's three lines can be positioned more cleverly than three independent points suggest. Take it as the reminder that the heuristic generates a guess, and the two-player game generates the answer. Every other VC question on these papers is a class where the count does happen to work.

(14) Generalisation error. Train minus test for the same classifier. The tell is that it is the only one of the three gaps containing $\mathrm{er}_S$. Estimation and approximation both compare two $\mathrm{er}_D$ quantities; Bayes error is a single number, not a gap.

(15) $P(A)\le P(B)$. Since $h_S\in H$, if $A$ occurs then the maximum over $H$ is at least $\epsilon$ too, so $A\subseteq B$. This is the subset bound from Week 1, and it is the pivot of the entire uniform-convergence proof: $A$ mentions a data-dependent classifier and Hoeffding cannot touch it, while $B$ ranges only over classifiers fixed in advance. Equality fails because $B$ can be triggered by some other $h$ while $h_S$ itself is fine.

(16) From $n_0 = \frac{1}{2\epsilon^2}\log\frac{2|H|}{\delta}$:

• $\epsilon\downarrow \Rightarrow n_0\uparrow$ — true, and quadratically so.
• $|H|\uparrow \Rightarrow n_0\uparrow$ — true, logarithmically.
• $\delta\uparrow \Rightarrow n_0\uparrow$ — false. $\delta$ is the allowed failure probability; tolerating more failure needs less data. $n_0$ carries $\log(1/\delta)$, which decreases as $\delta$ grows.
• $n_0$ independent of $|H|$ — false. It is in there; a logarithm is not an absence.

The $\delta$ option is the mark-loser on this whole paper. Read $\delta$ as "probability of the bad event", never as "confidence" — confidence is $1-\delta$, and conflating the two flips the direction of the answer.

The test error of a general $h_r$. Uniform on a disc means $P(\|x\|\le t) = t^2$ for $t\le1$; uniform on the annulus (area $4\pi-\pi = 3\pi$) means $P(\|x\|\le t\mid y=0) = \frac{t^2-1}{3}$ for $1<t\le2$.

(17) At $r = 0.5$: $\;\mathrm{er}_D[h_{0.5}] = 0.5(1-0.25) = 0.375$. The class minimum: the first branch decreases to $0$ at $r=1$ and the second increases from $0$, so $\mathrm{er}_D[H] = 0$, attained at $r=1$. Hence

(18) $h_1$ is a perfect classifier — it labels exactly the green disc $1$ — so $\mathrm{er}_D[H] = 0$. The regions are disjoint, so the Bayes classifier is also perfect and $\mathrm{er}_D^* = 0$. Therefore

The two-mark shortcut. Before integrating anything, ask: does $H$ contain a zero-error classifier? Here it obviously does — the true decision boundary is a circle of radius $1$ centred at the origin, and $h_1\in H$. That single observation answers Q18 in one line and hands you $\mathrm{er}_D[H]=0$ for Q17.

Traps: forgetting that "uniform on a disc" makes probability scale with $r^2$, not $r$ (a linear reading gives $0.5(1-0.5) = 0.25$); using $4\pi$ instead of $3\pi$ for the annulus area; and multiplying by the wrong prior — both are $0.5$ here, which is a mercy.

(19) Equal priors, so cross the densities. $f_1(x) = 2e^{-2x}$, $f_0(x) = e^{-x}$:

The shape is worth a ten-second sketch: $\mathrm{Exp}(2)$ starts higher ($f_1(0)=2$ against $f_0(0)=1$) but decays faster, so class $1$ owns the region near zero and class $0$ owns the tail. The question's stated form of $h^*$ confirms it.

(20) $h^*$ says $1$ on $[0,\ln2]$ and $0$ beyond, so it errs on class-$1$ points in the upper tail and class-$0$ points in the lower:

Now $e^{-2\ln2} = 2^{-2} = \tfrac14$ and $e^{-\ln2} = \tfrac12$:

Traps. Charging the wrong tail to the wrong class — class $1$ errs above $\theta$, class $0$ below, and the two contributions ($0.125$ and $0.25$) are unequal, so swapping them changes nothing about the total here but would in any asymmetric variant. Also: use the given CDF rather than integrating, and exploit $e^{-\lambda\ln2} = 2^{-\lambda}$ to keep the arithmetic exact. The accepted range was a wide $0.32$–$0.45$.

Let $Z = \|X\| \ge 0$ with $\mathbb{E}[Z] = 10$. Markov: $P(Z \ge 50) \le 10/50 = 0.2$. Complement: $p = P(Z \le 50) \ge 1 - 0.2 = \mathbf{0.8}$.

Traps: D is the raw Markov number without the complement. B has the complement but keeps the inequality direction — an upper bound on the tail is a lower bound on $p$. C is true but weaker, and the question says "tightest".

$k \in O(\log n/\epsilon^2)$ — no $d$. Same $n$, same $\epsilon$ ⟹ the same $k$ works for both.

Traps: A and B encode "a 1000× bigger space needs a 1000× bigger embedding" — exactly the intuition JL demolishes. The load-bearing phrase is "same number of data-points": that is the only quantity that matters.

"Whenever $X$ occurs, $Y$ occurs" is set containment $X \subseteq Y$: the smaller event sits inside. Hence $P(X) \le P(Y)$ — the subset inequality used throughout the JL proof.

Trap: B is the reversed containment and is the most common error — the arrow in "$X \to Y$" makes it feel like $X$ should be the bigger, outer set. Implication shrinks the event.

The singular values of a Gaussian matrix concentrate in a narrow band — for aspect ratio $\beta = 10^4/10^5 = 0.1$ they lie roughly in $\sqrt N(1\pm\sqrt\beta) \approx [0.68, 1.32]\sqrt N$. Plotted from zero, that band is a spike.

This is the matrix-level restatement of JL: $\sigma_{\min} \approx \sigma_{\max}$ means the map is nearly a scaled isometry — the sphere goes to a nearly spherical ellipsoid. Same fact as the "$\sigma_i \approx \sqrt{d/k}$" line in the Week 2 linear-algebra lecture.

Trap: A is the reflex — "Gaussian entries, so Gaussian singular values". Singular values are a highly non-linear function of the entries.

$\operatorname{Cov}(A\omega) = A\operatorname{Cov}(\omega)A^\top = AA^\top$. Row 1 of $A$ is $(1,4)$: $1+16 = 17$. Row 2 is $(3,1)$: $9+1 = 10$. Cross: $3+4 = 7$.

Trap: B is $A^\top A$ — same trace, same off-diagonal, only the diagonal order differs, so it survives a glance. This is the identity behind randomized SVD ($\operatorname{Cov}(A\omega) = AA^\top$, whose eigenvectors are the left singular vectors); getting it backwards breaks that whole story. C squares each entry.

Level sets of $\lfloor(a^\top x + b)/w\rfloor$ are parallel slabs perpendicular to $a$, of equal width $w$. The direction of $a$ is random (any slope allowed) and $b$ shifts them, so both stripe pictures are realisable.

Traps: B is seductive — "Euclidean LSH, so round buckets" — but rings hash by norm: two antipodal points on the same ring collide despite being maximally far apart. C is half-right: a single linear projection can never carve out a bounded closed region. And since this is an MSQ, ticking only A scores zero.

$P(p) = 1-(1-p^k)^L$ is strictly increasing in $L$ for every $p \in (0,1)$. So it lifts the rate for near pairs ($p \ge p_1$) and for far pairs ($p \le p_2$) at the same time. More tables buy recall and pay in precision, memory, and candidate-filtering time.

Trap: D comes from conflating $L$ with $k$. It is $k$ (the AND) that drives both rates down. Ticking only A also loses the marks — the point of the question is that both move the same way.

Step 1 — diameter upstairs. For $x,y$ on the unit sphere, the triangle inequality through the origin gives $\|x-y\| \le \|x\| + \|y\| = 2$.

Step 2 — apply JL, then square-root. $\|f(x)-f(y)\|^2 \le (1+\epsilon)\|x-y\|^2$, so

Traps: (i) Using diameter $1$ instead of $2$ — the points lie on the unit sphere, so the farthest pair is antipodal. (ii) Multiplying the distance by $(1+\epsilon)$ instead of $\sqrt{1+\epsilon}$, giving $2.0402$. The value $\epsilon = 0.0201$ is engineered so $\sqrt{1+\epsilon} = 1.01$ exactly — that is the examiner telling you to take a square root.

Eckart–Young: $\|A - A_k\|_2 = \sigma_{k+1}$. With $k=4$, that is $\sigma_5 = \mathbf{0.01}$.

Traps: $\sigma_4 = 1$ (off-by-one — the error is the first value discarded). Or the Frobenius answer $\sqrt{0.01^2 + 0.001^2} \approx 0.01005$ — the subscript $2$ means spectral norm, so only the largest discarded value counts. The tiny $\sigma_6 = 0.001$ exists purely to make that mistake feel reasonable.

For a singleton, the cut equals the weighted degree. Degrees: $d_1 = 1+2 = 3$, $d_2 = 1+3 = 4$, $d_3 = 2+3 = 5$, and identically $3, 4, 5$ for vertices $4,5,6$. Minimum is $\mathbf{3}$ at $A = \{1\}$ or $\{4\}$.

Trap: The graph is deliberately disconnected, so the global mincut really is $0$ (take $A = \{1,2,3\}$). The constraint $|A| = 1$ forbids that. Reading past the cardinality constraint is the entire trap. Secondary slip: answering $1$, the smallest single edge weight, instead of summing all edges at the vertex.

Diagonal = weighted degrees $(3,4,5,3,4,5)$; off-diagonal $= -w_{ij}$; zeros across the blocks because the components are disconnected. Since there are two components, $\lambda = 0$ has multiplicity $2$.

Trap: The distractor is $-W$ — right off-diagonals, right sparsity, but a zero diagonal. Kill it with the row-sum test: every row of a Laplacian sums to $0$; in $-W$ every row sums to a negative number. (The source PDF is truncated here, so options C and D are not recoverable.)

For square orthogonal $Q$, $\|Qv\|^2 = v^\top Q^\top Q v = \|v\|^2$ — an exact isometry on $\mathbb{R}^k$. So $\|QMx\| = \|Mx\|$ and $QM$ inherits the identical $\epsilon$. And $Q$ orthogonal ⟹ $Q^\top = Q^{-1}$ is orthogonal too, so the same argument gives B.

Trap: C targets students half-remembering "$Q^\top Q = I$ but $QQ^\top \ne I$". That caveat is for rectangular matrices with orthonormal columns. Here $Q$ is explicitly square, so both products are $I$ and A and B stand or fall together — which makes C self-defeating.

The structural fact: each hash's level set is a slab (convex), so a bucket of $g$ is an intersection of $k$ slabs — also convex. If $x_1, x_2$ share a bucket, the whole segment between them does.

A: $x_3$ is a convex combination, so it's on the segment. ✓

C: pure algebra — $x_3 + (1-\lambda)x_1 + \lambda x_2 = \lambda x_1 + (1-\lambda)x_2 + (1-\lambda)x_1 + \lambda x_2 = x_1 + x_2$. It is literally the same point, so it trivially collides with itself. Expand before you think geometrically.

D: $= \tfrac\lambda2 x_1 + (1-\tfrac\lambda2)x_2$, a convex combination with $\mu = \lambda/2 \in (0,\tfrac12)$. ✓

Trap — B, and it is one word: $\forall \beta \in \mathbb{R}$. Convexity protects $\beta \in [0,1]$ only. Outside that you are on the line's extension, which walks out of the slab. Convex hull, not affine hull.

$Z \ge 0$, and by linearity of expectation (which needs no independence) $\mathbb{E}[Z] = 30$. Markov: $P(Z \ge 60) \le 30/60 = \mathbf{0.5}$.

Trap: "with the available information" is load-bearing. No variance, no independence ⟹ Chebyshev and Hoeffding are unavailable and $0.5$ genuinely is the tightest derivable bound. Splitting into $P(X\ge20) + P(Y\ge40) \le 1$ via the union bound is legal but strictly weaker.

Each row satisfies $r_i^\top u \sim \mathcal N(0, \|u\|^2)$, so $\mathbb{E}[(r_i^\top u)^2] = \|u\|^2 = 100$. Over $k = 25$ rows: $\mathbb{E}\|Ru\|^2 = 25 \times 100 = 2500$. Then $A = R/5$ scales the squared norm by $1/25$:

Note $5 = \sqrt{25} = \sqrt k$ — this is $M = R/\sqrt k$, and the answer coming out as exactly $\|u\|^2$ is the unbiasedness result, not a coincidence.

Traps: forgetting the scaling ($2500$); dividing by $5$ once instead of $25$ ($500$) — the scalar squares inside $\|\cdot\|^2$. The ambient $10000$ is a pure red herring, which is itself the JL punchline.

With $X_{uv} \sim \mathrm{Bernoulli}(p_{uv})$ indicating retention,

so the difference has expectation $\mathbf{0}$, for every fixed $f$.

Trap: grinding out algebra expecting an $f$-dependent mess — the whole design of the $1/p$ reweighting is to make this identically zero. Deeper trap: unbiasedness holds for any $p_{uv} > 0$. Effective resistance buys concentration, not correctness-on-average. Zero expected error is not zero error.

Q85 → C. Euclidean (Datar) LSH buckets are parallel slabs of width $w$ perpendicular to a random direction. Two points in the same slab differ by at most $w$ along that direction; ANDing $k$ of them bounds the separation in $k$ random directions, hence the Euclidean distance w.h.p.

Q86 → B. Cosine similarity depends only on the angle and is scale-invariant, so its buckets must be cones through the origin — exactly what lines through the origin produce (SimHash: $h_a(x) = \mathrm{sign}(a^\top x)$, collision probability $1-\theta/\pi$).

Traps: A and D bucket by norm — antipodal points on the same ring always collide, which is anti-locality-sensitive; and no single linear hash can produce a bounded region. The paired structure is deliberate: answering both with the same partition guarantees losing one. Discriminator: is the similarity scale-invariant? Cosine yes → wedges. Euclidean no → stripes.

Setup. Using the paper's hint $D^\top D = \sum_j i_j v_jv_j^\top$. Since the $v_j$ are orthonormal this is the spectral decomposition: eigenvalues $12, 9, 2, 1, 1$ plus $0$ with multiplicity $d - 5 = 5$.

Q87 → 25. $n = 12+9+2+1+1$. Note $n = 25$, $d = 10$, $\mathrm{rank} = 5$ are three different numbers, each used in a different sub-question.

Q88 → A, B, C ($0$, $1$, $3$). Singular values are square roots: $\sqrt{12}\approx3.46$, $\sqrt9 = 3$, $\sqrt2$, $1$, $1$, and $0$ (five times, since $d > \mathrm{rank}$). $12$ is an eigenvalue of $D^\top D$, not a singular value of $D$ — the multiplicities are handed to you looking like an answer list. Also easy to miss $0$.

Q89 → 0.48. Decode $W$ first: a 0/1 column summing to $1$ is a random standard basis vector, so $D^\top\varepsilon_t$ is the $t$-th row of $D$ — one uniformly sampled data point. This is a sampling sketch, not a Gaussian one. With $\ell=1$, $\mathrm{span}(Z_\ell)$ is a single line, and since the $v_j$ are orthonormal it contains $v_1$ iff the sampled point is $v_1$: $12/25 = \mathbf{0.48}$.

Q90 → 0.93. $\ell = k+p = 4$ draws; $v_1$ is captured iff at least one hits: $1 - 0.52^4 = \mathbf{0.9269}$. Three extra columns take failure from $52\%$ to $7\%$ — the whole argument for oversampling, in one number.

Q91 → 0.93, unchanged. $Z^{(2)} = (D^\top D)Z^{(1)}$ multiplies each sampled column $v_j$ by the positive scalar $i_j$, which does not change the span. Power iteration improves accuracy, never coverage — if no draw was $v_1$, nothing conjures it.

Traps: answering $1$ on Q89 by reading $W$ as Gaussian; answering $0.2$ by sampling uniformly over the 5 directions instead of the 25 points (the multiplicities are the sampling weights — this is why leverage-score sampling exists); $4 \times 0.48 = 1.92 > 1$ on Q90; and expecting Q91 to go up.

Weighted degrees: $d_1 = 3+2+10 = 15$, $d_2 = 3+2 = 5$, $d_3 = 2+1 = 3$, $d_4 = 10+2+1 = 13$.

Q92 → 13. $V\setminus A = \{4\}$, so the cut is just $d_4 = 10+2+1 = \mathbf{13}$. Trap: summing the edges inside $A$ ($3+2+0 = 5$), or missing $w_{34}=1$ (drawn as a long curved arc along the bottom — that layout is deliberate).

Q93 → A, B, D, i.e. $A^* = \{1,2,4\}$. Enumerate: $\mathrm{cut}\{1\} = 15$, $\{2\} = 5$, $\{3\} = 3$, $\{4\} = 13$, $\{1,2\} = 14$, $\{1,3\} = 14$, $\{1,4\} = 8$. The smallest non-zero value is $\mathbf{3}$, achieved by the complementary pair $\{3\}$ and $\{1,2,4\}$; the key commits to the large side. Vertex 3 is the loosely-attached one, so peeling it off is cheapest — exactly what the Fiedler vector would find.

Careful: $\{3\}$ and $\{1,2,4\}$ have identical cut value, so this MSQ is genuinely ambiguous. Reasoning toward the singleton makes you tick only C and score zero. Heuristic: when three of four membership options are true, the large side is intended. Also note "non-zero" — without it, $A = \emptyset$ gives $0$ and the question is degenerate.

Q94 → 17. $L_{11} = d_1 = 15$ and $L_{42} = -w_{42} = -2$, so $15 - (-2) = \mathbf{17}$. The double negative is the whole point of asking for a difference. Secondary traps: using the unweighted degree $3$ for $L_{11}$; and indexing — the paper says "indices start from one" for a reason.

Markov: $P(T \ge 25) \le 4/25 = 0.16$. Complement: $P(T < 25) \ge 1 - 0.16 = \mathbf{0.84}$.

The complement step is the recurring archetype — it appeared in both past papers.

The union-bound step is $P(E) \le n^2 e^{-c\,k\epsilon^2} \le \delta$, so $k$ is driven by $n$, $\epsilon$ and $\delta$ — never $d$. $\delta$ counts because it enters when you solve that inequality, though only inside a logarithm, so its influence is weak.

The headline $k \in O(\log n/\epsilon^2)$ suppresses $\delta$ by treating it as a fixed constant. That is fine for the big-oh statement, but the question asks what $k$ depends on — so D counts. If you ticked only A and C you would score zero on an MSQ.

$r = 1$, $cr = 4\times1 = 4$. Distance $3.5$ satisfies neither $\le 1$ nor $\ge 4$ — it lies in the annulus $(1,4)$, where the definition asserts nothing. Always compute $cr$; never compare against $c$ alone.

$\mathrm{rank}(A) = $ number of non-zero singular values $= 3$. And $\|A - A_2\|_2 = \sigma_3 = 2$. Product $= 3 \times 2 = \mathbf 6$.

Trap on the rank: it is not $\min(6,4) = 4$, because $\sigma_4 = 0$.

$\deg(2) = 2$ so $L_{22} = 2$. Vertices $1$ and $3$ are not adjacent, so $w_{13} = 0$ and $L_{13} = -0 = \mathbf{0}$. Sum $= \mathbf{2}$.

For reference, $L = \begin{bmatrix}1&-1&0&0\\-1&2&-1&0\\0&-1&2&-1\\0&0&-1&1\end{bmatrix}$ — check each row sums to zero.

$(b-a)^2 = (6-2)^2 = 16$. So the bound is $e^{-2n(0.25)/16} = e^{-n/32}$.

Traps: B uses $b-a = 2$ (the lower endpoint, not the range); C uses $b^2 = 36$; D silently assumes $[0,1]$. The range matters, not the endpoints individually — the bound is invariant to shifting the interval.

D is false: $\Omega$ is $n \times \ell$, so that $Y = A\Omega$ works dimensionally ($m\times n$ times $n\times\ell$). Getting $\Omega$'s orientation wrong breaks the whole pipeline, and it is the easiest shape to invert mentally.

Shape chain to memorise: $\Omega_{n\times\ell} \to Y_{m\times\ell} \to Q_{m\times\ell} \to B_{\ell\times n} \to \hat U_{m\times k}$.

Solving $n\,p_2^k = 1$ gives $k = \dfrac{\log n}{\log(1/p_2)}$. Base-2 throughout: $\log_2 n = 20$, $\log_2(1/0.25) = \log_2 4 = 2$. So $k = 20/2 = \mathbf{10}$.

Check: $n p_2^k = 2^{20} \times 4^{-10} = 2^{20}/2^{20} = 1$. ✓  Bonus: $\rho = \log(1/0.5)/\log(1/0.25) = 1/2$, so $L = \theta n^{0.5} = \theta \cdot 1024$.

Two details separate B from C: $f_1$ is discarded (it is the constant vector at $\lambda_1 = 0$ and carries no clustering information), and normalisation comes before k-means, not after — the point of projecting the embeddings onto the unit sphere is to make k-means' job easy.

$w' = 8/0.25 = \mathbf{32}$. Expected contribution $= p \cdot w' \cdot (f_u-f_v)^2 = 0.25 \times 32 \times 3 = \mathbf{24}$, which equals $w \cdot (f_u-f_v)^2 = 8 \times 3 = 24$. ✓ Unbiased, as designed.

Note the variance is enormous here: the contribution is $96$ a quarter of the time and $0$ otherwise. That is exactly why the choice of $p$ matters — it controls variance, not the mean.

B is false — the output is an approximation, guaranteed only to be within $(1+\epsilon)\sigma_{k+1}$ with probability $\ge 1-\delta$. Exactness is precisely what you trade away.

C is the real precondition: if the spectrum is flat, $\sigma_{k+1}/\sigma_k \approx 1$ and the subspace bound is vacuous — you then need power iteration.

$\sigma = 3$, so $12 = 4\sigma$ and Chebyshev gives $P(|X| \ge 12) \le 1/16$, hence $P(X \ge 12) \le 1/16$ too.

B is wrong because Markov needs $X \ge 0$, and a mean-zero non-degenerate variable is not non-negative. C is wrong because Hoeffding needs many independent bounded variables — you have one variable of unknown range. This question is really asking: which hypotheses do you actually have?

Singleton cuts are the weighted degrees: $d_1 = 5+1 = 6$, $d_2 = 5+1 = 6$, $d_3 = 1+1 = \mathbf 2$. On three vertices every non-trivial cut is a singleton (or its complement), so the minimum is $\mathbf 2$, at $A = \{3\}$.

Note where the heavy edge ends up: the mincut keeps $1$ and $2$ together precisely because $w_{12} = 5$ is expensive to cross.

Exponentiating first is what turns Markov's weak $1/a$ decay into exponential decay: the free $\lambda$ can then be optimised, which is what produces a bound of the form $e^{-c\,k\epsilon^2}$. Applying Markov to $\|x\|^2$ directly (A) gives only $1/(1+\epsilon)$ — useless.

The MGF of each $x_i^2 \sim \chi^2_1$ is $(1-2\lambda)^{-1/2}$, and independence lets you take the product over the $k$ coordinates.

$\rho = \dfrac{\ln(1/0.8)}{\ln(1/0.2)} = \dfrac{0.2231}{1.6094} = \mathbf{0.1386} \approx 0.14$.

$L = \theta n^\rho = 3 \times (10^6)^{0.1386} = 3 \times 10^{0.8316} = 3 \times 6.78 \approx \mathbf{20}$.

Sanity: $\theta = 3$ ⟹ TPR $= 1 - e^{-3} = 0.95$. Twenty tables gives 95% recall on a million points — that is the headline result of the whole unit.

C is false and is the crux of the relaxation: we abandoned $\{0,1\}^n$ (NP-hard) for $\mathbb{R}^n$. The entries are arbitrary reals, which is exactly why a thresholding or 1-D k-means step is needed afterwards to recover a discrete partition.

A and D restate each other: orthogonality to $\mathbf 1$ deletes the trivial $\lambda_1 = 0$ direction, so the constrained minimum is $\lambda_2$.

Diameter upstairs is $2\times 5 = 10$. JL is on squared distances, so the multiplier on the distance is $\sqrt{1+\epsilon} = \sqrt{1.04} = 1.0198$. Bound $= 10 \times 1.0198 = \mathbf{10.198} \approx 10.2$.

B is $(1+\epsilon)\times10$ — forgetting the square root. C uses the radius instead of the diameter. This is the T2 Q9 archetype with different numbers.

The guarantee is $\|A - QQ^\top A\|_2 = (1+\epsilon)\,\sigma_{k+1}$ with probability at least $1-\delta$.

A is the guarantee as stated. B is why oversampling is structurally required rather than a tuning nicety: with $\ell = k$ exactly the sketch has no slack, and one unlucky draw loses a direction outright.

C is false, and this is the striking part. The quality of the approximation is governed by the spectrum and by how much you oversample — not by how big the matrix is. A $10^6\times10^5$ matrix and a $100\times50$ matrix with the same singular-value profile get the same guarantee from the same $\ell$. That is what makes the method scale.

D is true: $\epsilon = 0$ gives $\|A-QQ^\top A\|_2 = \sigma_{k+1}$, which by Eckart–Young is exactly the best any rank-$k$ approximation achieves — i.e. $QQ^\top = U_kU_k^\top$.

B is false: spectral clustering still needs $k$ — you choose how many eigenvectors to keep, and you still run k-means at the end. It fixes the shape limitation, not the model-selection problem.

All of A, C, D are the same fact in three costumes: Euclidean proximity is the wrong similarity; graph connectivity is the right one.

That is the course in one line, and the same three-beat pattern each time: exact is too expensive → randomize → concentrate. The concentration inequalities of Week 1 are the shared engine; the union bound is what upgrades a per-item guarantee into an all-items-at-once guarantee.

And the loop closes: JL (Week 1) is the tool used to compute effective resistances quickly (Week 6), which is what makes sparsification — and hence spectral clustering at scale — practical.

A, B and D are all properties of $D$ (and $H$) alone — fixed numbers, unknown but not random. $h_S$ is chosen from the sample, so it inherits the sample's randomness, and therefore so does its test error.

This is the exact reason Hoeffding cannot be applied directly to $|\mathrm{er}_S[h_S]-\mathrm{er}_D[h_S]|$: both sides move with $S$. The $A\subseteq B$ trick exists to trade that expression for one where the classifiers are all fixed in advance.

Densities: $f_1 = \tfrac12$ on $[0,2]$; $f_0 = \tfrac14$ on $[1,5]$. Equal priors, so compare densities directly.

• $[0,1)$: $f_1=\tfrac12 > f_0=0$ ⇒ $h^*=1$
• $[1,2]$: $f_1=\tfrac12 > f_0=\tfrac14$ ⇒ $h^*=1$  (class 1 still denser)
• $(2,5]$: $f_1=0 < f_0=\tfrac14$ ⇒ $h^*=0$

So $h^*=1$ exactly on $[0,2]$. Class $1$ never lands outside $[0,2]$, so it is never misclassified; the only errors are class-$0$ points landing in $[1,2]$, which happens with probability $\tfrac{2-1}{4} = \tfrac14$:

Traps. $0.375$ charges both classes for the overlap $[1,2]$ — but in the overlap $h^*$ picks the denser class ($1$) and is correct for it, so only class $0$ pays. $0.25$ forgets to multiply by the prior.

A is what "uniform" means, and it is precisely what lets the bound be applied to $h_S$ whichever member the algorithm returned. C: $|H|$ enters logarithmically, which is why a class of $10^6$ classifiers needs only about twice the data of one with $10^3$. D: Hoeffding needs independence — the unbiasedness step needs only identical distribution, but the concentration step needs both.

B is the headline misreading. The theorem equates the train and test errors; it never claims either is small.

One interval per coordinate, $2$ endpoints each: $2d = 2\times 5 = \mathbf{10}$.

Same argument as the $\mathbb{R}^3$ cuboid on the T3 paper. Lower bound: put the $10$ points at $\pm e_1,\dots,\pm e_5$ — the face centres — and slide each of the $10$ faces independently. Upper bound: for any $11$ points, take the $10$ achieving the extreme coordinate in each of the $10$ directions, label them $1$ and one remaining point $0$; the bounding box of the extremes swallows everything.

Traps: $5$ (the dimension), $32 = 2^5$ (vertices of a hypercube), $6$ (the $\mathbb{R}^3$ answer not generalised).

$e^{\epsilon} = 3$, so $p = \tfrac{3}{4}$ (truth) and $q = \tfrac14$ (flip) — the reason $\ln 3$ is a pleasant choice.

Compare coordinatewise: $X=(0,1,1)$ against $Y=(0,0,1)$ — agree at $1$ and $3$, flip at $2$.

Method check: $\#\text{agree} + \#\text{flip} = 3$ ✓. And note that unlike the $\epsilon=0.1$ past-paper questions (where $p\approx q$ and a sign error is nearly invisible), here $p$ and $q$ differ by a factor of three — swapping them gives $\tfrac{3}{64}=0.047$, which is obviously wrong. Practising at $\ln 3$ exposes the error that $\epsilon = 0.1$ hides.

Infinite VC dimension means the labeling count is $2^n$, so the bound $2^ne^{-2n\epsilon^2}$ does not go to zero and there is no uniform convergence. Without it, the train error carries no information about the test error — and with an unrestricted class you can always drive the train error to zero by memorising.

A and D each require a generalisation or estimation guarantee that does not exist here. B additionally requires the approximation error to vanish, which is a separate matter entirely. This is the formal content of "overfitting".

Laplace uses $\ell_1$ sensitivity: $\Delta_1 = \sum_{i=1}^{64}\tfrac1n = \tfrac{64}{n}$, giving spread $\tfrac{64}{n\epsilon}$.

Gaussian uses $\ell_2$: $\Delta_2 = \sqrt{64\cdot\tfrac{1}{n^2}} = \tfrac{8}{n}$, giving spread $\tfrac{8}{n\epsilon}$ up to the log factor.

Notice $n$ and $\epsilon$ cancel — the ratio is $\sqrt d$ regardless. That is the entire payoff of relaxing to $(\epsilon,\delta)$-DP: quadratically less noise in the output dimension, for the price of a $\delta$ and a logarithm.

A: $\log_2 256 = 8$. C is the same inequality read backwards — shattering $10$ points needs $2^{10}=1024$ distinct labelings, hence at least that many classifiers. B is the conceptual point: the two uniform-convergence theorems agree at the boundary, which is why "replace $\log|H|$ by $d$" is the right mental substitution.

D is the trap — it is an upper bound. A class of $256$ classifiers could have VC dimension $0$ (if they all agree on every point) or anything up to $8$.

With the board variant $\log\frac{|H|}{\delta}$ it is $50\ln(10000) = 460.5 \Rightarrow 461$ — the two conventions differ by $50\ln 2 \approx 35$, which is why a well-posed question always states the form.

Sensitivity worth noticing: multiplying $|H|$ by $10$ adds only $50\ln 10 \approx 115$, whereas halving $\epsilon$ would quadruple the whole thing. Accuracy is the expensive axis.

$h^*$ is defined by a threshold on $P(y=1\mid x)$, a property of the unknown $D$ — you lack the information, not the compute. ERM has everything it needs in hand and still cannot run: minimising the $0$–$1$ loss over $H_{\mathrm{lin}}$ is NP-hard.

Keeping the two apart also explains the two fixes: you approximate $h^*$ by learning from data, and you approximate ERM by swapping in a convex surrogate. Different problems, different escapes.

Basic composition: $k$ mechanisms each $(\epsilon,\delta)$-DP compose to $(k\epsilon,\,k\delta)$-DP.

An $\epsilon$ of $2.1$ means $e^{2.1}\approx 8.2$ — the adversary's likelihood ratio between neighbouring datasets is now a factor of eight, which is a weak guarantee. That degradation is why advanced composition matters: its leading term is $\epsilon\sqrt{k\log(1/\delta')}$, so the $k$ becomes $\sqrt k$.

Trap: advanced composition is available for the Gaussian mechanism only — with Laplace you are stuck with $k\epsilon$. That single fact is why DP-SGD adds Gaussian noise.

A: you keep the extremes in each of the four directions, all from the positive class — negatives carry no information about where the rectangle's edges go. B is the defining requirement. D is the professor's own stated caveat: with no positives there is nothing to retain, and the sketch as given breaks. Complete versions handle the corner cases; the exam only asks for the size.

C is false and is what makes this compression: $T \subseteq S$. You select points, you do not synthesise them. A scheme allowed to invent points would be model fitting, and the connection to VC dimension would evaporate.

Revenue is $S(x,p) = p \times \#\{i : v_i \ge p\}$. Check the only prices that can be optimal — the valuations themselves, since revenue only drops between them:

• $p=5$: all four buy ⇒ $5\times 4 = 20$
• $p=100$: one buys ⇒ $100\times 1 = \mathbf{100}$

So $OPT = \mathbf{100}$ at $p^\star = 100$.

Why the optimum sits at a valuation: raising the price between two valuations loses no buyers and gains revenue, so the maximum is always attained at some $v_i$. That reduces the search to $n$ candidates — and it is also why the revenue curve is a sawtooth rather than smooth, which is what breaks naive Laplace perturbation of the price.

Trap: $115 = 20+100$ adds the two branches; the seller sets one price.

SRM runs ERM inside each $H_i$ of a nested family and scores the results by $\mathrm{er}_S[h_i^{\mathrm{ERM}}] + \sqrt{\frac{d_i\log(n/d_i)+\log(1/\delta)}{n}}$. Bigger classes fit better but pay more penalty, which is exactly the approximation-versus-estimation trade-off made explicit.

C is false — the professor is emphatic that SRM is impractical (ERM alone is NP-hard, and SRM wants many of them). In practice the same effect is achieved indirectly by regularisation, with $\lambda$ playing the penalty's role and cross-validation choosing it. A is the wrong error (SRM targets approximation, not generalisation); D would defeat the purpose.

Contiguous runs (choose a first and last point: $\binom82 + 8 = 28+8 = 36$) plus the empty labeling.

Compare with $2^8 = 256$ for unrestricted classifiers. The restriction has cut the effective class size by a factor of seven at $n=8$, and the gap widens fast — that is why uniform convergence survives for $H_{\mathrm{int}}$ and dies for the class of all functions. Traps: $36$ (forgot all-zeros); $45 = 9+8+\cdots+1$ (the board's over-counting bound).

A is what makes the definition usable for continuous outputs, where every single output has probability zero. B is the definition of "neighbouring" — and note it generalises beyond bit flips: swap one point of $\mathcal X^n$ for any other point of $\mathcal X$. C is the post-processing property, and it is what lets you hand a private release to anyone without further accounting.

D is backwards. Privacy is the ratio bound $e^\epsilon$; $\epsilon \to 0$ drives the ratio to $1$, meaning the output distribution is identical for neighbouring datasets — maximal privacy. Larger $\epsilon$ lets the adversary distinguish more easily.

The train error is computed only from the $n$ labelled points, so identical labelings force identical train errors. The test error is an expectation over all of $D$, and the two classifiers can disagree everywhere off the sample — $h_{3,7.5}$ and $h_{3.001,7.499}$ label the same points identically but are different functions.

This is precisely the gap the professor flags when he says the labeling-count argument needs a symmetrisation trick to become a real theorem, and defers it to a full learning-theory course. For this course, the conclusion to carry is that the effective class size is what appears in the bound — with an honest asterisk about how the proof is completed.

The class-conditional densities are identical, so $x$ carries no information about $y$ — the feature is useless. Bayes' rule gives $P(y=1\mid x) = P(y=1) = 0.8 \ge 0.5$ for every $x$, so $h^*(x) = 1$ everywhere.

The lesson: the Bayes error is the irreducible noise floor. No classifier — in any hypothesis class, with any amount of data — beats $0.2$ here. It is also a clean illustration of why $\mathrm{er}_D^*$ need not be zero, and why "the Bayes error is zero" was a wrong option on both May-2025 papers.

Traps: $0.5$ ignores the prior and assumes a coin flip; $0$ assumes optimal always means perfect.

The spread is $\tfrac{\Delta}{\epsilon} = \tfrac{1}{n\epsilon}$. Smaller $\epsilon$ ⇒ larger spread. Intuitively, a stricter privacy requirement means the two output densities must overlap more, which needs wider noise.

A goes the other way: more people dilute each individual, so $\Delta = \tfrac1n$ shrinks and less noise is needed. C is the opposite of B. D is inverted — the sum has $\Delta = 1$ while the average has $\Delta = \tfrac1n$, so switching to the average needs $n$ times less noise.

Three uses of the same tool. Weeks 1–6: probability as an algorithmic tool — randomise the computation, then use a tail bound to show the answer is nearly right. Weeks 7–10: probability as an analytical tool — the same Hoeffding and the same union bound, now proving that a train error measured on $n$ random points predicts behaviour on unseen data. Weeks 11–12: probability as a shield — inject calibrated noise so the output reveals the population but not the person.

D is exactly backwards, and it is the misconception worth killing before the exam: the uniform convergence proof is Hoeffding plus the union bound plus the subset bound $A\subseteq B \Rightarrow P(A)\le P(B)$ — all three straight from Week 1. Nothing was replaced; the Week 1 toolkit was pointed at a new question.