Understanding Machine Learning: From Theory to Algorithms

23.7 Exercises 341

matrixW∈Rn,d, where each element ofW is independently distributed

according toN(0, 1 /n), we have

|〈Wu,Wv〉−〈u,v〉|≤

for everyu,v∈Q.
Hint: Use JL to bound both‖W‖u(u++vv‖)‖and‖W‖u(u−−vv‖)‖.
2.(*)Letx 1 ,...,xmbe a set of vectors inRdof norm at most 1, and assume
that these vectors are linearly separable with margin ofγ. Assume that
d 1 /γ^2. Show that there exists a constantc >0 such that if we randomly
project these vectors intoRn, forn=c/γ^2 , then with probability of at least
99% it holds that the projected vectors are linearly separable with margin
γ/2.