A Proofs of Main Upper and Lower Bounds

Lemma 4.2, we have that k x At test time, if we encounter this rare scenario of mapping to a bucket with no value learnt in it, we simply run an approximate nearest neighbor search among the train points. This leads to our stated sample complexity bound. Hence the total time taken would be O ( dk log( L/)) . The above theorem uses a lemma about Euclidean LSH, which we prove next. The total time required for a forward pass on a new test sample is O ( dk log(1 /)) .