**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.
over features and labels for a binary
classification problem. Consider two finite hypothesis classes
and
such that
. It is given that if
, then
with a high
probability for classifiers drawn from
. Which of the following is most likely to be true?
6406537408565.
If
, then
with a high probability for
classifiers drawn from
6406537408566.
There exists
such that, if
, then
with a high probability for classifiers drawn from
6406537408567.
The hypothesis class
is too big for any guarantees to hold on the
generalization error.
Published solution
**1. State a finite-class guarantee:** For independent samples and binary loss, a typical uniform-convergence bound is
\[P\!\left(\sup_{h\in\mathcal H}|er_S(h)-er_D(h)|\ge\epsilon\right)\le2|\mathcal H|e^{-2n\epsilon^2}.\]
**2. Compare class sizes:** The second class has 10,000 times as many hypotheses. The union-bound factor is larger, so the old sample size is not automatically enough for the same accuracy/confidence.
**3. Increase sample size:** Both classes are finite, so a sufficiently large sample still gives a guarantee. One may choose \(n_2\ge n_1\); the sufficient increase in this bound is proportional to \(\ln(10{,}000)/(2\epsilon^2)\), not necessarily a 10,000-fold sample increase.
**Answer: B.**
A: **Incorrect:** The original sample guarantee need not transfer unchanged to a larger class.
B: **Correct:** A sufficiently large sample exists for the larger finite class as well.
C: **Incorrect:** Every fixed finite class admits finite-sample uniform-convergence guarantees.
If we want a strong privacy guarantee in the randomized response mechanism with privacy
parameter
, which of the following is a good course of action?
6406537408568.
Increase
6406537408569.
Decrease
6406537408570.
Keep
constant
6406537408571.
The privacy guarantee is independent of
Published solution
**1. Read the privacy parameter:** Epsilon-differential privacy bounds the likelihood ratio of the same output under neighboring inputs by \(e^\varepsilon\).
**2. Interpret smaller epsilon:** Decreasing epsilon moves this bound toward one, making outputs harder to distinguish between different private inputs.
**3. Select the action:** Reduce epsilon for stronger privacy. This generally requires more randomization and can reduce statistical utility at a fixed sample size.
**Answer: B.**
A: **Incorrect:** Increasing epsilon allows a larger distinguishability bound and weakens privacy.
B: **Correct:** A smaller epsilon gives the stronger guarantee.
C: **Incorrect:** Keeping it unchanged does not strengthen the existing guarantee.
D: **Incorrect:** Epsilon directly controls the differential-privacy bound.
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.”
6406537408576.
True
6406537408577.
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. Represent the linear map:** A dense JL map from dimension d to k is a k-by-d matrix, already supplied by the question.
**2. Count one transformed point:** Computing k outputs, each a dot product of length d, takes order dk arithmetic operations.
**3. Transform n points:** Total work is \(O(ndk)\) using ordinary dense multiplication. Generating the map is excluded. Specialized sparse/structured projections could have different costs but are not specified here.
**Answer: B.**
A: **Incorrect:** nk omits the d-term work in each output dot product.
B: **Correct:** n points times k coordinates times d products gives O(ndk).
C: **Incorrect:** A second factor of k is unnecessary.
D: **Incorrect:** Dividing by k does not describe dense matrix-vector multiplication.
**1. Express each sampled edge’s contribution:** Let its indicator be \(I_e\), inclusion probability \(p_e>0\), and retained weight \(w_e/p_e\). Its Laplacian contribution is \(I_e(w_e/p_e)b_eb_e^{\mathsf T}\).
**2. Take expectation:** Since \(E[I_e]=p_e\), the expected contribution is \(w_eb_eb_e^{\mathsf T}\). Summing edges gives \(E[L_H]=L_G\), hence \(E[x^{\mathsf T}L_Hx]=x^{\mathsf T}L_Gx\) for each fixed x under this sampling process.
**3. Compare edge sets:** H retains/reweights edges of G, so \(F\subseteq E\). Unbiasedness does not say a particular random H equals G exactly.
**Answer: A, C.**
A: **Correct:** Inverse-probability reweighting gives the stated unbiased quadratic-form identity.
B: **Incorrect:** The deterministic G side cannot equal every realization of a randomly sampled H.
C: **Correct:** Sampling retains a subset of the original edges.
D: **Incorrect:** H need not retain every original edge, so E need not be contained in F.
Which of the following hypothesis classes have infinite VC dimension? The feature space is
. All
classifiers mentioned in the options are from
to
.
6406537408594.
The set of all decision trees classifiers, where each tree can be trained to
arbitrary depth.
6406537408595.
The set of all functions from
to
.
6406537408596.
The set of all linear classifiers.
6406537408597.
The set of all classifiers whose decision boundary is a circle centered at the
origin.
Published solution
**1. Recall shattering:** Infinite VC dimension means arbitrarily large finite sets can receive every binary labeling using members of the class.
**2. Identify unrestricted capacity:** Arbitrarily deep decision trees can isolate any finite collection of distinct points; all binary functions can directly specify any labels. Their VC dimensions are infinite.
**3. Compare restricted boundaries:** Linear separators in the plane have finite VC dimension 3. Origin-centered circular boundaries give a constrained radial-threshold class with finite VC dimension. Thus only A and B are infinite.
**Answer: A, B.**
A: **Correct:** Unbounded tree depth allows arbitrarily large finite samples to be shattered.
B: **Correct:** The class of all functions realizes every finite labeling.
C: **Incorrect:** Planar linear separators have finite capacity.
D: **Incorrect:** A radius-controlled circular family has finite capacity.
**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 pieces of information are indispensable if we need to apply the Markov
inequality? Select all that apply.
6406537408598.
The non-negativity of the random variable.
6406537408599.
Availability of the variance of the random variable.
6406537408600.
Availability of the third moment of the random variable.
6406537408601.
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 that consists of all linear classifiers that pass through the origin having the
following property: the slope of the decision boundary of the classifier, denoted by
, satisfies
. Find the VC-dimension of
.
Published solution
**1. Count distinct decision boundaries:** The line passes through the origin and has slope m with |m|=1, so its boundary is either y=x or y=-x. Each line permits two label orientations, giving four distinct half-plane classifiers away from boundary conventions.
**2. Shatter two points:** Choose (1,0) and (0,1). The two orientations of y=x produce opposite labels on these points; the two orientations of y=-x produce the two equal-label patterns. All four labelings occur.
**3. Bound larger sets:** Three points require eight labelings, but this class has at most four distinct classifiers. It cannot shatter three points, so VC dimension is 2. This assumes the usual consistent boundary-label convention.
**Answer: 2.**
Consider a binary classification problem with a single feature 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 most
. Enter the value of
.
Published solution
**1. State the far-point LSH condition:** An \((r,c,p_1,p_2)\)-sensitive family has collision probability at most \(p_2\) when distance is at least cr.
**2. Substitute:** Here r=1, c=3 and \(\|x-y\|\ge3=cr\), so the far-point condition applies.
**3. Read the bound:** \(P[h(x)=h(y)]\le p_2=0.1\). This is a guaranteed upper bound rather than an assertion of exact equality.
**Answer: 0.1.**
**1. Complete the distributions:** P(y=0)=0.3 and P(y=1)=0.7. At x=-1,0,1, class-one conditionals are (0.6,0.2,0.2); class-zero conditionals are (0.2,0.2,0.6).
**2. Compute joint masses:** For class zero the masses are (0.06,0.06,0.18); for class one they are (0.42,0.14,0.14).
**3. Choose the more probable class:** Predict one at -1 and 0, and zero at 1. This minimizes error separately at each feature value.
**Answer: B.**
A: **Incorrect:** It selects the opposite class at each of the three feature values.
B: **Correct:** It predicts zero only at x=1, matching the joint-mass comparisons.
C: **Incorrect:** Always-one fails at x=1 where class-zero mass is 0.18 versus 0.14.
D: **Incorrect:** Always-zero fails at -1 and 0.
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. Find joint probabilities:** Multiplying the supplied conditionals by priors 0.3 and 0.7 gives class-zero masses (0.06,0.06,0.18) and class-one masses (0.42,0.14,0.14) at x=-1,0,1.
**2. Select unavoidable errors:** The Bayes rule predicts the larger mass and misclassifies the smaller. The three smaller masses are 0.06,0.06 and 0.14.
**3. Sum:** \[er_D^*=0.06+0.06+0.14=0.26.\] The two-decimal answer is 0.26.
**Answer: 0.26.**
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.**
