Algorithms for Data Science · End Term · May 2025 · FN

A subgraph/sparsifier \(H = (V, F, W')\) is an **\(\epsilon\)-spectral approximation** of a weighted undirected graph \(G = (V, E, W)\) if for all vectors \(\theta \in \mathbb{R}^n\), the quadratic forms of their Laplacians \(L_G\) and \(L_H\) satisfy: \[(1 - \epsilon)\,\theta^T L_G \theta \le \theta^T L_H \theta \le (1 + \epsilon)\,\theta^T L_G \theta\] **Answer: B (\((1 - \epsilon)\theta^T L_G \theta \le \theta^T L_H \theta \le (1 + \epsilon)\theta^T L_G \theta, \text{ for all } \theta \in \mathbb{R}^n\))** A: **Incorrect:** Places \(L_H\) in the outer bounds and \(L_G\) in the middle; the standard definition bounds \(\theta^T L_H \theta\) relative to \(\theta^T L_G \theta\). B: **Correct:** Defines \(L_H\) as an \(\epsilon\)-spectral sparsifier of \(L_G\): \((1-\epsilon)\theta^T L_G \theta \le \theta^T L_H \theta \le (1+\epsilon)\theta^T L_G \theta\). C: **Incorrect:** Mixes \(L_G\) on the left bound with \(L_H\) on the right bound. D: **Incorrect:** Compare \(\theta^T L_G \theta\) with itself on the left.

**Step 1: Count the number of possible class assignments for each data point.** There are \(n = 5\) data points, and each data point can be assigned to any of the \(c = 3\) classes independently. **Step 2: Compute the total number of distinct labellings \(k\).** \[k \le 3^5 = 243\] **Answer: 243**

**Step 1: Analyze the hypothesis class \(\mathcal{H}\).** Each hypothesis \(h_{a_1 \dots a_6}(x)\) classifies a point \(x \in \mathbb{R}\) as `1` if \(x\) falls inside the union of **3 disjoint closed intervals** \([a_1, a_2] \cup [a_3, a_4] \cup [a_5, a_6]\), and `0` otherwise. **Step 2: Determine the VC dimension.** For the class of unions of \(k\) disjoint intervals on the real line \(\mathbb{R}\), the VC dimension is \(2k\): - Any set of \(6\) points \(x_1 < x_2 < x_3 < x_4 < x_5 < x_6\) can be shattered because even the alternating labelling \((1, 0, 1, 0, 1, 0)\) needs at most 3 intervals (\([x_1, x_1], [x_3, x_3], [x_5, x_5]\)). - No set of \(7\) points can be shattered because the alternating labelling \((1, 0, 1, 0, 1, 0, 1)\) has 4 separated runs of `1`s, requiring at least 4 intervals. Thus, \(\text{VC}(\mathcal{H}) = 2 \times 3 = 6\). **Answer: 6**

**Step 1: Recall the Eckart-Young theorem for the best rank-1 approximation.** Given the SVD \(A = U \Sigma V^T\) with singular values \(\sigma_1 = 3 > \sigma_2 = 2 > \sigma_3 = 1\), the best rank-1 approximation of \(A\) is: \[B = \sigma_1 u_1 v_1^T\] **Step 2: Substitute \(\sigma_1 = 3\), \(u_1 = [1, 0, 0]^T\), and \(v_1 = [1, 0, 0]^T\).** \[B = 3 \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 3 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}\] **Step 3: Sum the diagonal entries of \(B\).** \[\text{Tr}(B) = 3 + 0 + 0 = 3\] **Answer: 3**

**Step 1: Map each point \(x \in \mathbb{R}^2\) to its squared distance from the origin \(z = \|x\|^2 \ge 0\).** A classifier \(h_r(x) = \mathbb{I}(\|x\|^2 \le r^2)\) labels \(x\) as `1` if and only if \(z = \|x\|^2 \le r^2\). **Step 2: Check shatterability for 1 point and 2 points.** - **1 point \(\{x_1\}\)**: Choosing \(r^2 = \|x_1\|^2\) gives label `1`; choosing \(r^2 < \|x_1\|^2\) (or a negative threshold if allowed, or for \(\|x_1\| > 0\), \(r = 0\)) gives label `0`. Thus, 1 point can be shattered. - **2 points \(\{x_1, x_2\}\)**: Without loss of generality, suppose \(\|x_1\|^2 \le \|x_2\|^2\). Whenever \(h_r(x_2) = 1\) (so \(\|x_2\|^2 \le r^2\)), we automatically have \(\|x_1\|^2 \le \|x_2\|^2 \le r^2\), which forces \(h_r(x_1) = 1\). Thus, the labelling \((h_r(x_1) = 0, h_r(x_2) = 1)\) is impossible, so no 2 points can be shattered. Therefore, the VC dimension of \(\mathcal{H}\) is **1**. **Answer: 1**

Let us match each error decomposition term to its standard statistical learning theory definition: 1. **\(\text{er}_D(\mathcal{H}) - \text{er}_D^*\)**: The gap between the best possible classifier in hypothesis class \(\mathcal{H}\) and the Bayes optimal classifier \(h^*\) is the **approximation error** (inductive bias of \(\mathcal{H}\)). 2. **\(\text{er}_S(h_S) - \text{er}_D(h_S)\)**: The difference between the training (empirical) error on sample \(S\) and the true (population) error on distribution \(D\) for the learned classifier \(h_S\) is the **generalization error**. 3. **\(\text{er}_D(h_S) - \text{er}_D(\mathcal{H})\)**: The gap between the true error of the learned classifier \(h_S\) and the best true error achievable within \(\mathcal{H}\) is the **estimation error**. **Answer: A ((1) = approximation error, (2) = generalization error, (3) = estimation error)** A: **Correct:** (1) is approximation error, (2) is generalization error, and (3) is estimation error. B: **Incorrect:** Swaps approximation error and generalization error. C: **Incorrect:** Permutes all three error definitions. D: **Incorrect:** Swaps generalization error and estimation error.

Let us check the sign of both error differences: 1. **Approximation error \(\text{er}_D(\mathcal{H}) - \text{er}_D^* \ge 0\)**: Since the Bayes optimal classifier \(h^*\) minimizes the true risk \(\text{er}_D(h)\) over *all* measurable functions, no hypothesis in \(\mathcal{H}\) can have a strictly smaller true risk than \(\text{er}_D^*\). Thus, \(\text{er}_D(\mathcal{H}) - \text{er}_D^* \ge 0\) (**Option A is true**). 2. **Estimation error \(\text{er}_D(h_S) - \text{er}_D(\mathcal{H}) \ge 0\)**: Since \(h_S \in \mathcal{H}\) and \(\text{er}_D(\mathcal{H}) = \inf_{h \in \mathcal{H}} \text{er}_D(h)\), the true risk of \(h_S\) is always at least \(\text{er}_D(\mathcal{H})\). Thus, \(\text{er}_D(h_S) - \text{er}_D(\mathcal{H}) \ge 0\) (**Option B is true**). **Answer: A, B** A: **Correct:** No classifier in \(\mathcal{H}\) can beat the Bayes optimal error \(\text{er}_D^*\), so \(\text{er}_D(\mathcal{H}) - \text{er}_D^* \ge 0\). B: **Correct:** Since \(h_S \in \mathcal{H}\) and \(\text{er}_D(\mathcal{H}) = \min_{h \in \mathcal{H}} \text{er}_D(h)\), we always have \(\text{er}_D(h_S) - \text{er}_D(\mathcal{H}) \ge 0\). C: **Incorrect:** The approximation error cannot be negative. D: **Incorrect:** The estimation error cannot be negative.

The **Bayes error** \(\text{er}_D^* = \mathbb{P}_{(x, y) \sim D}(h^*(x) \ne y)\) is a probability (the expected 0-1 misclassification loss of the Bayes optimal classifier). Because any probability lies in \([0, 1]\)—and can be \(0\) in noise-free separable problems or strictly positive \(> 0\) when class-conditional distributions overlap—the statement that is always true in general is that **the Bayes error is non-negative** (\(\text{er}_D^* \ge 0\)). **Answer: A (The Bayes error is non-negative.)** A: **Correct:** As a misclassification probability, the Bayes error always satisfies \(\text{er}_D^* \ge 0\). B: **Incorrect:** The Bayes error is zero only when the classes are deterministically separable with no label noise. C: **Incorrect:** The Bayes error is not strictly positive if the classes have disjoint supports and deterministic labels. D: **Incorrect:** A probability can never be negative.

**Step 1: Write the class-conditional densities \(f(x \mid y = 1)\) and \(f(x \mid y = 0)\).** - Given \(x \mid y = 1 \sim U[-1, 3]\), the density is: \[f(x \mid y = 1) = \frac{1}{3 - (-1)} = \frac{1}{4} = 0.25 \quad \text{for } x \in [-1, 3]\] - Given \(x \mid y = 0 \sim U[-2, 0]\), the density is: \[f(x \mid y = 0) = \frac{1}{0 - (-2)} = \frac{1}{2} = 0.50 \quad \text{for } x \in [-2, 0]\] **Step 2: Apply Bayes' decision rule with equal priors \(P(y = 1) = P(y = 0) = 0.5\).** Since the priors are equal, the Bayes classifier \(h^*(x)\) predicts `1` when \(f(x \mid y = 1) > f(x \mid y = 0)\) and `0` when \(f(x \mid y = 0) > f(x \mid y = 1)\): - For \(x \in [-2, -1)\): \(f(x \mid y = 0) = 0.5 > 0 = f(x \mid y = 1) \implies h^*(x) = 0\). - For \(x \in [-1, 0)\): \(f(x \mid y = 0) = 0.5 > 0.25 = f(x \mid y = 1) \implies h^*(x) = 0\). - For \(x \in (0, 3]\): \(f(x \mid y = 1) = 0.25 > 0 = f(x \mid y = 0) \implies h^*(x) = 1\). Combining these regions gives: \[h^*(x) = \begin{cases} 1, & 0 \le x \le 3 \\ 0, & -2 \le x < 0 \end{cases}\] **Answer: A** A: **Correct:** On \([-2, 0)\), \(f(x|y=0) = 0.5 > f(x|y=1)\), so \(h^*(x) = 0\); on \([0, 3]\), \(f(x|y=1) = 0.25 > 0\), so \(h^*(x) = 1\). B: **Incorrect:** On the overlap \([-1, 0]\), class 0 has density \(0.5\) while class 1 has density \(0.25\), so \(h^*(x)\) must predict `0`, not `1`. C: **Incorrect:** Always predicting `1` misclassifies all points in \([-2, 0]\) where class 0 is more likely. D: **Incorrect:** Always predicting `0` misclassifies all points in \((0, 3]\) where only class 1 has positive density.

**Step 1: Identify where the Bayes classifier \(h^*(x)\) makes an error.** From Q#261, \(h^*(x) = 0\) on \([-2, 0)\) and \(h^*(x) = 1\) on \([0, 3]\): - When \(y = 0\), \(x \sim U[-2, 0]\), so \(x\) always lies in \([-2, 0]\) where \(h^*(x) = 0\) (except at the single point \(x = 0\) of measure zero). Thus, \(P(h^*(x) \ne 0 \mid y = 0) = 0\). - When \(y = 1\), \(x \sim U[-1, 3]\). The Bayes classifier predicts \(h^*(x) = 0 \ne 1\) whenever \(x \in [-1, 0)\). The probability of this interval under \(U[-1, 3]\) is: \[P(h^*(x) \ne 1 \mid y = 1) = P(-1 \le x < 0 \mid y = 1) = \frac{0 - (-1)}{3 - (-1)} = \frac{1}{4} = 0.25\] **Step 2: Compute total Bayes error.** \[\text{er}_D(h^*) = P(y = 0)\,P(h^*(x) \ne 0 \mid y = 0) + P(y = 1)\,P(h^*(x) \ne 1 \mid y = 1) = 0.5 \times 0 + 0.5 \times 0.25 = 0.125\] **Answer: 0.125**

**Step 1: Evaluate \(x_1 + x_2\) for each point in the training dataset \(S\).** - Point \((0, 0)\) belongs to class `0`: \(x_1 + x_2 = 0 + 0 = 0\). - Point \((1, 0)\) belongs to class `1`: \(x_1 + x_2 = 1 + 0 = 1\). - Point \((0, 1)\) belongs to class `1`: \(x_1 + x_2 = 0 + 1 = 1\). - Point \((1, 1)\) belongs to class `1`: \(x_1 + x_2 = 1 + 1 = 2\). **Step 2: Find the integer threshold \(\theta^* \in \mathbb{Z}\) that minimizes training error.** The classifier \(h_\theta(x) = \mathbb{I}(x_1 + x_2 \ge \theta)\) classifies \((0, 0)\) as `0` and \((1, 0), (0, 1), (1, 1)\) as `1` with **zero training error** if and only if \(0 < \theta \le 1\). Since \(\theta \in \mathbb{Z}\), the unique integer solution is: \[\theta^* = 1\] **Answer: 1**

From Q#263, the Empirical Risk Minimizer \(h_S^{\text{ERM}} = h_1(x) = \mathbb{I}(x_1 + x_2 \ge 1)\) predicts: - \(h_1(0, 0) = 0\) (matches true label `0`) - \(h_1(1, 0) = 1\) (matches true label `1`) - \(h_1(0, 1) = 1\) (matches true label `1`) - \(h_1(1, 1) = 1\) (matches true label `1`) Since every point in the training set \(S\) is classified correctly, the training error is: \[\text{er}_S(h_S^{\text{ERM}}) = 0\] **Answer: 0**

**Step 1: Compute the true error \(\text{er}_D(h_S^{\text{ERM}})\) of \(h_1(x) = \mathbb{I}(x_1 + x_2 \ge 1)\).** Note that on \(\{0, 1\}^2\), \(h_1(x) = 0\) if and only if \(x = (0, 0)\), and \(h_1(x) = 1\) for all other points \((1, 0), (0, 1), (1, 1)\). - **When \(y = 0\)**: Given \(P((0, 0) \mid y = 0) = 1\), every sample from class `0` is \((0, 0)\), which \(h_1\) correctly classifies as `0`. Thus, \(P(h_1(x) \ne 0 \mid y = 0) = 0\). - **When \(y = 1\)**: \(h_1\) makes an error if and only if \(x = (0, 0)\) (where \(h_1(0, 0) = 0 \ne 1\)). We are given \(P((0, 0) \mid y = 1) = 0.25\). Thus, the true population risk is: \[\text{er}_D(h_S^{\text{ERM}}) = P(y = 0) \cdot 0 + P(y = 1) \cdot P((0, 0) \mid y = 1) = 0.5 \times 0.25 = 0.125\] **Step 2: Compute the absolute value of the generalization error.** \[|\text{er}_S(h_S^{\text{ERM}}) - \text{er}_D(h_S^{\text{ERM}})| = |0 - 0.125| = 0.125\] **Answer: 0.125**

**Step 1: Recall the finite hypothesis class bound on VC dimension.** If a hypothesis class \(\mathcal{H}\) shatters a set of \(d\) points, then \(\mathcal{H}\) must be able to realize all \(2^d\) distinct binary labellings on those \(d\) points, which requires: \[2^d \le |\mathcal{H}| \implies d \le \log_2(|\mathcal{H}|)\] **Step 2: Substitute \(|\mathcal{H}| = 100\).** \[d \le \lfloor \log_2(100) \rfloor = \lfloor 6.6438 \rfloor = 6\] (Since \(2^6 = 64 \le 100 < 128 = 2^7\), the tightest integer upper bound is **6**.) **Answer: 6**

Let us evaluate the properties of \(\mathcal{H}_{\text{int}}\), the hypothesis class of single interval classifiers \(h_{a,b}(x) = \mathbb{I}(x \in [a, b])\) on \(\mathbb{R}\): 1. **VC dimension**: Any 2 distinct points \(x_1 < x_2\) can be shattered by \([a, b]\), whereas 3 points \(x_1 < x_2 < x_3\) cannot realize the labelling \((1, 0, 1)\) because any interval containing \(x_1\) and \(x_3\) must also contain \(x_2\). Thus, **the VC dimension of \(\mathcal{H}_{\text{int}}\) is 2** (**Option A is true**, B is false). 2. **Sample compression scheme**: To reconstruct an interval that correctly classifies any realizable training set, we only need to retain at most **2** extreme positive training points: the minimum positive point \(x_{\min}^+\) and the maximum positive point \(x_{\max}^+\), defining \([x_{\min}^+, x_{\max}^+]\). Thus, **\(\mathcal{H}_{\text{int}}\) has a sample compression scheme of size 2** (**Option C is true**, D is false). **Answer: A, C** A: **Correct:** A single interval on \(\mathbb{R}\) can shatter any 2 points but cannot shatter 3 points (cannot label \((1, 0, 1)\)). B: **Incorrect:** The VC dimension of single intervals is 2, not 4. C: **Correct:** Retaining the leftmost and rightmost positive examples (at most 2 points) suffices to reconstruct a consistent interval. D: **Incorrect:** Only 2 points (not 4) are needed for the sample compression scheme of a single interval.

**Step 1: Use linearity of expectation.** Since \(r = (r_1, r_2, r_3, r_4)^T\) has standard normal entries \(r_i \sim \mathcal{N}(0, 1)\), we have \(\mathbb{E}[r_i] = 0\) for each \(i\). Therefore, for \(a = (1, -1, 1, 1)^T\): \[\mathbb{E}[a^T r] = a^T \mathbb{E}[r] = 1(0) - 1(0) + 1(0) + 1(0) = 0\] **Answer: 0**

**Step 1: Compute the variance of the linear combination \(a^T r\).** Assuming the entries of the standard normal vector \(r \sim \mathcal{N}(0, I_4)\) are independent with \(\text{Var}(r_i) = 1\): \[\text{Var}(a^T r) = \sum_{i=1}^4 a_i^2 \text{Var}(r_i) = \|a\|_2^2 = 1^2 + (-1)^2 + 1^2 + 1^2 = 1 + 1 + 1 + 1 = 4\] **Answer: 4**

In Locality-Sensitive Hashing (LSH) with an \((r, c, p_1, p_2)\)-sensitive hash family \(\mathcal{H}\), using \(k\) independent hash functions per table (AND-construction) and \(L\) independent tables (OR-construction): - For a true near neighbor (at distance \(\le r\)), the probability of colliding in a single hash function is \(p_1\). - The probability of matching on all \(k\) hash functions in a single table is \(p_1^k\). - The probability of *not* matching in a single table is \(1 - p_1^k\), and the probability of not matching in any of the \(L\) independent tables is \((1 - p_1^k)^L\). - Therefore, the **True Positive Rate (TPR)** (collision in at least one of the \(L\) tables) is: \[\text{TPR} = 1 - (1 - p_1^k)^L\] **Answer: A (\(1 - (1 - p_1^k)^L\))** A: **Correct:** With AND-of-\(k\) and OR-of-\(L\), the collision probability for a close pair (\(p_1\)) is \(1 - (1 - p_1^k)^L\). B: **Incorrect:** Uses \(p_2\) (far-point probability), which gives the False Positive Rate (FPR) rather than TPR. C: **Incorrect:** \((1 - p_1^k)^L\) is the False Negative Rate (probability of missing in all \(L\) tables). D: **Incorrect:** \((1 - p_2^k)^L\) is the True Negative Rate.

For a far point (at distance \(\ge c r\)), the collision probability under a single hash function is \(p_2\): - The probability of matching on all \(k\) hash functions in one table is \(p_2^k\). - The probability of not colliding in any of the \(L\) independent tables is \((1 - p_2^k)^L\). - Therefore, the **False Positive Rate (FPR)** (colliding in at least one of the \(L\) tables) is: \[\text{FPR} = 1 - (1 - p_2^k)^L\] **Answer: B (\(1 - (1 - p_2^k)^L\))** A: **Incorrect:** \(1 - (1 - p_1^k)^L\) is the True Positive Rate (TPR). B: **Correct:** Using the far-point collision probability \(p_2\), the FPR across \(L\) tables of length \(k\) is \(1 - (1 - p_2^k)^L\). C: **Incorrect:** \((1 - p_1^k)^L\) is the False Negative Rate. D: **Incorrect:** \((1 - p_2^k)^L\) is the True Negative Rate.

For any valid \(k \ge 1\) and \(L \ge 1\), the function \(g(p) = 1 - (1 - p^k)^L\) is **strictly increasing** for \(p \in [0, 1]\). Since a valid LSH family satisfies \(p_1 > p_2\), we strictly have: \[\text{TPR} = 1 - (1 - p_1^k)^L > 1 - (1 - p_2^k)^L = \text{FPR}\] Therefore, the TPR can **never** equal the FPR (**No**). **Answer: B (No)** A: **Incorrect:** Because \(p_1 > p_2\) and \(1 - (1 - p^k)^L\) is strictly monotonic, TPR cannot equal FPR for finite \(k, L \ge 1\). B: **Correct:** Strict monotonicity of \(p \mapsto 1 - (1 - p^k)^L\) for \(p_1 > p_2\) guarantees \(\text{TPR} > \text{FPR}\).

**Step 1: Recall the bit-flipping probabilities in the \(\epsilon\)-differentially private randomized response mechanism.** For each bit \(X_i \in \{0, 1\}\) independently: - Probability of keeping the true bit (\(Y_i = X_i\)): \[p = \frac{e^\epsilon}{1 + e^\epsilon}\] - Probability of flipping the bit (\(Y_i \ne X_i\)): \[1 - p = \frac{1}{1 + e^\epsilon}\] **Step 2: Compare \(X = (1, 0, 1, 1, 0)\) and \(Y = (1, 1, 1, 1, 1)\).** - Positions where \(Y_i = X_i\) (bits 1, 3, 4): **3 positions** keep their value (probability \(p^3\)). - Positions where \(Y_i \ne X_i\) (bits 2, 5): **2 positions** flip their value (probability \((1 - p)^2\)). **Step 3: Substitute \(\epsilon = 0.1\) and compute the probability.** \[P(Y = (1, 1, 1, 1, 1) \mid X = (1, 0, 1, 1, 0)) = p^3 (1 - p)^2 = \frac{e^{3\epsilon}}{(1 + e^\epsilon)^5}\] With \(\epsilon = 0.1\), \(e^{0.1} \approx 1.1051709\) and \(e^{0.3} \approx 1.3498588\): \[P(Y \mid X) = \frac{1.3498588}{(2.1051709)^5} = \frac{1.3498588}{41.32252} \approx 0.032666\] Rounded to three decimal places (within the accepted range `0.030 to 0.035`), this is **0.033**. **Answer: 0.033**

In the randomized response mechanism for \(X_i \in \{0, 1\}\), the intermediate bit \(Y_i \in \{0, 1\}\) satisfies: \[\mathbb{E}[Y_i] = X_i \cdot \frac{e^\epsilon}{1 + e^\epsilon} + (1 - X_i) \cdot \frac{1}{1 + e^\epsilon} = X_i \left(\frac{e^\epsilon - 1}{e^\epsilon + 1}\right) + \frac{1}{1 + e^\epsilon}\] To make the output \(Z_i\) an **unbiased estimator** of the true bit \(X_i\) (so that **\(\mathbb{E}[Z_i] = X_i\)**, **Option A**), we solve for \(X_i\) by subtracting \(\frac{1}{1 + e^\epsilon}\) and multiplying by \(\frac{e^\epsilon + 1}{e^\epsilon - 1}\): \[Z_i = \left(Y_i - \frac{1}{1 + e^\epsilon}\right) \cdot \left(\frac{e^\epsilon + 1}{e^\epsilon - 1}\right)\] which matches **Option B**. **Answer: A, B** A: **Correct:** The debiased output \(Z_i\) is constructed specifically so that its expectation equals the true value: \(\mathbb{E}[Z_i] = X_i\). B: **Correct:** Rescaling \(Y_i\) via \(Z_i = (Y_i - \frac{1}{1+e^\epsilon}) \cdot (\frac{e^\epsilon+1}{e^\epsilon-1})\) yields \(\mathbb{E}[Z_i] = X_i\). C: **Incorrect:** \(\mathbb{E}[Z_i] = X_i\), whereas \(Y_i\) is biased toward \(1/2\). D: **Incorrect:** Has the wrong signs and inverted scaling factor.