**1. Use a norm identity:** Since A is invertible, \(AA^{-1}=I\). The spectral norm is submultiplicative, so \(\|I\|_2\le\|A\|_2\|A^{-1}\|_2\).
**2. Rearrange:** \(\|I\|_2=1\) and A is nonzero, hence \[\|A^{-1}\|_2\ge\frac1{\|A\|_2}.\]
**3. Explain possible strictness:** The two norms involve the reciprocal of the smallest singular value and the largest singular value. They need not be equal unless all singular values coincide. For diag(2,1), inverse norm is 1 while reciprocal original norm is 1/2.
**Answer: A.**
A: **Correct:** This follows from submultiplicativity and AA inverse equal to identity.
B: **Incorrect:** The reverse bound fails for diag(2,1).
C: **Incorrect:** Equality holds for special matrices, not every invertible matrix.
D: **Incorrect:** A=2I has inverse norm 1/2 and original norm 2.
Is the following statement true or false?
Using the uniform convergence theorem for finite hypothesis classes, one can conclude
that the train error is a good proxy for the Bayes' error for very large datasets, for every
finite hypothesis class.
6406537372642.
True
6406537372643.
False
Published solution
**1. State what uniform convergence controls:** For a finite hypothesis class and enough independent samples, empirical error is close to population error simultaneously for every classifier in the class.
**2. Distinguish Bayes error:** Bayes error is the best possible population error over all measurable classifiers. A restricted finite class may not contain a classifier close to that optimum.
**3. Give a counterexample:** A class containing only a constant-zero classifier can have large error on a perfectly predictable task. Its train and test errors converge to each other, while the Bayes error is zero. More data does not remove this approximation error.
**Answer: B — Selected: False.**
A: **Incorrect:** Uniform convergence does not guarantee that an arbitrary hypothesis class approximates the Bayes rule.
B: **Correct:** It links empirical and population errors within the class, not necessarily Bayes error.
Is the given statement true or false?
Given a desired utility and privacy, the number of users who need to be surveyed is
quadratically smaller in the case of the randomized response mechanism than for the
Laplace mechanism.
6406537372644.
True
6406537372645.
False
Published solution
**1. Distinguish privacy settings:** Randomized response randomizes each user’s report before the curator sees it, giving local privacy. The central Laplace mechanism lets a trusted curator compute the true aggregate before adding noise.
**2. Compare estimation noise:** For a binary mean, central Laplace noise scales as \(1/(n\varepsilon)\). Standard locally private randomized-response estimation has noise of order \(1/(\varepsilon\sqrt n)\) in the high-privacy regime, alongside ordinary sampling variation.
**3. Judge the direction:** Local randomized response generally needs more, not quadratically fewer, users for comparable accuracy/privacy. Exact sample bounds also depend on confidence and the error criterion, so the stated blanket advantage is false.
**Answer: B — Selected: False.**
A: **Incorrect:** The asserted randomized-response sample advantage has the wrong direction.
B: **Correct:** Local reporting noise generally makes randomized response less sample-efficient than the trusted-curator mechanism.
**1. Expand the Laplacian quadratic form:** For an undirected graph with nonnegative weights,
\[x^{\mathsf T}Lx=\sum_{\{u,v\}\in E}w_{uv}(x_u-x_v)^2.\]
**2. Check signs:** Every weight and squared difference is nonnegative, so their sum is nonnegative for every real vector x.
**3. Conclude:** L is positive semidefinite. Constant vectors give zero; graphs with a positive-weight edge also admit vectors giving a positive value. Negative values cannot occur.
**Answer: A.**
A: **Correct:** Every term in the quadratic form is nonnegative.
B: **Incorrect:** The form is not universally nonpositive for a graph with a positive edge.
C: **Incorrect:** It is zero on special vectors, not all vectors for a nontrivial graph.
D: **Incorrect:** A negative quadratic-form value is impossible under these assumptions.
**1. Compare the events:** E1 says the classifier selected by the training algorithm has an error gap at least epsilon. E2 says at least one classifier in the whole hypothesis class has such a gap.
**2. Use membership:** The trained classifier belongs to that class. Therefore whenever E1 occurs, its classifier also witnesses E2, giving \(E_1\subseteq E_2\).
**3. Take probabilities:** Event inclusion implies \(P(E_1)\le P(E_2)\). The reverse inclusion need not hold because a badly generalizing classifier may exist without being chosen.
**Answer: A, C.**
A: **Correct:** A bad selected classifier is also a bad member of the class.
B: **Incorrect:** A bad classifier somewhere in the class need not be the trained one.
C: **Correct:** Probability respects event inclusion.
D: **Incorrect:** The reverse probability inequality is not guaranteed.
Which of the following hypothesis classes have finite VC dimensions? The feature space is
and
all classifiers in the options are from
to
.
6406537372662.
The set of all decision trees classifiers, where each tree can be trained to
arbitrary depth.
6406537372663.
The set of all functions from
to
.
6406537372664.
The set of all linear classifiers.
6406537372665.
The set of all classifiers whose decision boundary is a circle centered at the
origin.
Published solution
**1. Define finite VC dimension:** A class has finite VC dimension if there is a fixed upper limit on how many arbitrary point labels it can realize simultaneously.
**2. Identify unbounded classes:** Arbitrarily deep decision trees can isolate arbitrarily many distinct points. The set of all binary functions can assign arbitrary labels to any finite point set. Both have infinite VC dimension on the stated continuous feature space.
**3. Identify constrained classes:** Affine linear separators in the plane have VC dimension 3. Origin-centered circles have only radius and a possible label orientation to vary, giving a finite-capacity radial threshold family. Thus C and D are finite.
**Answer: C, D — Selected: The set of all linear classifiers.; The set of all classifiers whose decision boundary is a circle centered at the origin.**
A: **Incorrect:** Unlimited tree depth permits unbounded shattering capacity.
B: **Incorrect:** All functions can realize every labeling of any finite set.
C: **Correct:** Planar affine halfspaces have finite VC dimension.
D: **Correct:** Radius-based circular boundaries form a constrained finite-VC family.
users of a product. The users respond to the survey by saying "Yes" (1) if
they find the product useful and "No" (0) if they don't. The trusted curator of the survey uses the
Laplace mechanism with the average function to ensure privacy even while he publishes a report
on the usefulness of the product. Which of the following is/are true?
6406537372666.
The curator outputs the exact average value of the inputs he receives from the
users.
6406537372667.
The curator outputs a noisy version of the average value of the inputs he
receives from the users.
6406537372668.
The curator is given a randomized version of the users' data.
6406537372669.
The curator is given the users' data exactly without any randomization.
Published solution
**1. Identify the trusted-curator model:** Users send their original binary answers to the curator. This differs from locally randomized reporting.
**2. Compute sensitivity:** Changing one binary answer changes the average by at most \(1/n\).
**3. Privatize the released statistic:** The curator publishes \(\bar x+Z\), where \(Z\sim\operatorname{Laplace}(1/(n\varepsilon))\). The private output is noisy even though the curator’s input data are exact.
**Answer: B, D — Selected: The curator outputs a noisy version of the average value of the inputs he receives from the users.; The curator is given the users' data exactly without any randomization.**
A: **Incorrect:** Publishing the exact average alone is not the stated Laplace mechanism.
B: **Correct:** Noise is added to the average before release.
C: **Incorrect:** The stated trusted-curator mechanism does not randomize user data before collection.
D: **Correct:** The curator receives the true inputs and protects the published aggregate.
Which of the following pieces of information are indispensable if we need to apply Markov's
inequality for a random variable? Select all that apply.
6406537372674.
The non-negativity of the random variable.
6406537372675.
Availability of the variance of the random variable.
6406537372676.
Availability of the third moment of the random variable.
6406537372677.
Availability of the expected value of the random variable.
Published solution
**1. State Markov’s inequality:** For a nonnegative random variable X and a>0,
\[P(X\ge a)\le\frac{E[X]}a.\]
**2. Explain the conditions:** Nonnegativity lets a probability be bounded using the contribution of large values to the expectation. A finite known expectation, or a usable upper bound on it, supplies the numerical bound.
**3. Distinguish other moments:** Variance and the third moment are unnecessary for this direct inequality. They belong to other tail bounds or applications to transformed variables.
**Answer: A, D — Selected: The non-negativity of the random variable.; Availability of the expected value of the random variable.**
A: **Correct:** Nonnegativity is a condition of this direct Markov bound.
B: **Incorrect:** Variance is not required by the formula.
C: **Incorrect:** A third moment is not required.
D: **Correct:** The expectation, or a bound on it, is what appears in the bound.
Consider a binary classification problem with features in
and labels in
. Let
be the
hypothesis class of classifiers from
that predict
on at most
distinct points.
Formally, let
, where
Find the VC dimension of
.
Published solution
**1. Show five points can be shattered:** Choose any five distinct real inputs. For any desired labeling, put exactly the positively labeled inputs into S. Since \(|S|\le5\), the corresponding hypothesis realizes the labeling.
**2. Show six cannot be shattered:** The all-positive labeling of six distinct inputs would require S to contain six points, violating the class definition.
**3. Conclude:** The largest shattered size is exactly 5, so \(VCdim(\mathcal H)=5\).
**Answer: 5.**
Consider a binary classification problem with features in
and labels in
. Let
be a hypothesis class.
is defined as:
If
has a sample compression scheme of size
, find
.
Published solution
**1. Identify the class:** A hypothesis labels the union of two intervals positive and all other real points negative.
**2. Compress each positive block:** In a realizable sample, retain the leftmost and rightmost positive examples in each of the at most two positive blocks. Reconstruct the union of the two resulting closed intervals. No sample point with a negative label lies between the retained endpoints within a true positive block.
**3. Count stored examples:** At most two endpoints per block times two blocks gives four retained examples. Thus the standard endpoint-based sample compression scheme has size k=4. Empty blocks require fewer retained points; the scheme’s size is its worst-case bound.
**Answer: 4.**
Students who have just received their board exam results are being surveyed about their
performance. Each student has either passed or failed. The students have to reply with one of two
answers to the surveyor: pass/fail. To guarantee privacy, the surveyor asks each student to follow
the randomized mechanism given below:
1. Flip a fair coin.
2. If tails, respond truthfully.
3. If heads, then flip a fair coin again. Respond "pass" if heads and "fail" if tails.
This randomized response mechanism is
-differentially private, where
. Enter the most
appropriate integer
.
Published solution
**1. Compute reporting probabilities:** A truthful report is used with probability 1/2. The other half uses a fair second coin. Thus a passed student reports pass with probability \(1/2+1/4=3/4\), while a failed student reports pass with probability 1/4.
**2. Bound the likelihood ratio:** The largest ratio for the same report under the two possible true inputs is \((3/4)/(1/4)=3\). The fail report gives the symmetric ratio.
**3. Find epsilon:** Differential privacy needs \(e^\varepsilon\ge3\), with tight parameter \(\varepsilon=\ln3\). Since the question writes \(\varepsilon=\log_e k\), the requested integer is k=3.
**Answer: 3.**
. The probability that both these points are hashed
to the same value by a hash function sampled from this family is at least
. Enter the value of
.
Published solution
**1. Recall locality-sensitive hashing:** An \((r,c,p_1,p_2)\)-sensitive family has collision probability at least \(p_1\) for points within distance r, and at most \(p_2\) for points at least cr apart.
**2. Match the near-point condition:** Here \((r,c,p_1,p_2)=(1,3,0.9,0.1)\) and \(\|x-y\|\le1=r\).
**3. Read the guaranteed lower bound:** \(P[h(x)=h(y)]\ge p_1=0.9\). This is a bound, not necessarily the exact probability.
**Answer: 0.9.**
**1. Complete the conditionals:** The class priors are P(y=0)=0.6 and P(y=1)=0.4. At x=-1,0,1, class-zero conditional probabilities are 0.6,0.2,0.2; class-one probabilities are 0.2,0.2,0.6.
**2. Compare joint class masses:** Multiply conditional probability by prior. The class-zero masses are (0.36,0.12,0.12); class-one masses are (0.08,0.08,0.24).
**3. Choose the larger at each input:** Predict zero at -1 and 0, and one at 1. Bayes classification minimizes the probability of error pointwise; posterior normalization is unnecessary because the denominator is the same for both classes.
**Answer: A.**
A: **Correct:** It predicts one only at x=1, matching all three joint-mass comparisons.
B: **Incorrect:** It reverses the required labels at every feature value.
C: **Incorrect:** Always-one ignores the larger zero-class mass at -1 and 0.
D: **Incorrect:** Always-zero is wrong at x=1, where one-class mass is larger.
Consider a binary classification problem with labels in
with a single feature that can take
one of three values in the set
. The underlying distribution,
, over the feature-label
space is given as follows:
1. the prior probability for choosing class-
is given as:
.
2. the class conditional values for the probability mass function are given for a few values of
and
:
•
,
•
,
Based on the above data, answer the given subquestions.
Compute the Bayes' error,
. Enter your answer correct to two decimal places.
Published solution
**1. Compute joint masses:** At x=-1,0,1, the class-zero joint probabilities are (0.36,0.12,0.12) and the class-one probabilities are (0.08,0.08,0.24), using priors 0.6 and 0.4 and the supplied conditionals.
**2. Identify unavoidable error at each x:** The Bayes rule chooses the larger class mass, leaving the smaller mass as errors. These smaller masses are 0.08,0.08 and 0.12.
**3. Sum:** \[er_D^*=\sum_x\min_yP(x,y)=0.08+0.08+0.12=0.28.\] The requested two-decimal value is 0.28.
**Answer: 0.28.**
Consider a binary classification problem with features in
and labels in
. Let
be a hypothesis class.
is defined as:
A dataset
that has
points, where each point is a feature-label pair denoted as
, is given below:
Based on the above data, answer the given subquestions.
Find
. Enter your answer correct to one decimal place.
Published solution
**1. Reduce the data to the tested feature:** The rule predicts one when \(z=x_1+x_3\ge a\). The five (z,label) pairs are (-2,1), (0,1), (0,1), (0,1), (2,0).
**2. Check threshold regions:** If a≤-2, all predictions are one, so only the final negative example is wrong: one error. If -2<a≤0, the first positive and final negative are wrong: two errors. If 0<a≤2, all five are wrong. If a>2, the four positive examples are wrong.
**3. Minimize:** The minimum is one error among five, giving \(er_S[h^{ERM}]=1/5=0.2\).
**Answer: 0.2.**
Consider a binary classification problem with features in
and labels in
. Let
be a hypothesis class.
is defined as:
A dataset
that has
points, where each point is a feature-label pair denoted as
, is given below:
Based on the above data, answer the given subquestions.
Find the largest integer
such that
.
Published solution
**1. Compute the relevant scalar values:** The supplied sample has (x1+x3,label) pairs (-2,1), three copies of (0,1), and (2,0).
**2. Identify empirical-risk minimizers:** To avoid misclassifying the positive at -2, the threshold must satisfy a≤-2. Such a threshold predicts one on all five sample inputs and makes one error, the minimum possible for this upward-threshold family. Higher thresholds make at least two errors.
**3. Select the largest integer:** The minimizing region is \(( -\infty,-2]\), so its largest integer is -2. Inclusion of equality follows from the rule’s greater-than-or-equal sign.
**Answer: -2.**
