In high dimensions, the performance of nearest neighbor algorithms depends crucially on structure in the data. While traditional nearest neighbor datasets consisted mostly of hand-crafted feature vectors, an increasing number of datasets comes from representations learned with neural networks. We study the interaction between nearest neighbor algorithms and neural networks in more detail. We find that the network architecture can significantly influence the efficacy of nearest neighbor algorithms even when the classification accuracy is unchanged. Based on our experiments, we propose a number of training modifications that lead to significantly better datasets for nearest neighbor algorithms. Our modifications lead to learned representations that can accelerate nearest neighbor queries by 5×.
This paper investigates learning representations for the problem of nearest neighbor (NN) search by exploring various deep learning architectural choices. The crux of the paper is the connection between NN and the angles between the closest neighbors -- the higher this angle, more data points need to be explored for finding the nearest one, and thus more computational expense. Thus, the paper proposes to learn a network that tries to reduce the angles between the inputs and the corresponding class vectors in a supervised framework using softmax cross-entropy loss. Three architectural choices are investigated, (i) controlling the norm of output layers of the CNN (using batch norm essentially), (ii) removing relu so that the outputs are well-distributed in both positive and negative orthants, and (iii) normalizing the class vectors. Experiments are given on multiMNIST and Sports 1M and show improvements. 
Pros:
1) The paper explores different architectural choices for the deep network to some depth and show extensive results.
2) The results do demonstrate clearly the advantage of the various choices and is useful
3) The theoretical connections between data angles and query times are quite interesting,
Cons:
1) Unclear Problem Statement. 
I find the problem statement a bit vague. Standard NN search finds a data point in the database closest to a query under some distance metric. While, the current paper uses the cosine similarity as the distance, the deep framework is trained on class vectors using cross-entropy loss. I do not think class labels are usually assumed to be given in the standard definition of NN, and it is not clear to me how the proposed setup can accommodate NN without class labels.  Thus as such, I see this paper is perhaps proposing a classification problem and not an NN problem per se. 
2) Lacks Focus
The paper lacks a good organization in my opinion. Things that are perhaps technically important are moved to the Appendix. For example, I find the theoretical part of the paper (e.g., Theorem 1) quite elegant and perhaps the main innovation in this paper. However, that is moved completely to the Appendix. So it cannot be really considered a contribution. It is also not clear if those theoretical results are novel. 
2) Disconnect/Unclear Assumptions
There seems to be some disconnect between LSH and deep learning architectures explored in Sections 2 and 3 respectively. Are the assumptions used in the theoretical results for LSH also assumed in the deep networks? For example, as far as I know, the standard LSH works assumes the projection hyperplanes are randomly chosen and the theoretical results are based on such assumptions. It is not clear how a softmax output of a CNN, which is trained in a supervised way, follow such assumptions. It would be important if the paper could clarify such assumptions to make sure the sections are congruent. 
3) No Related Work
There have been several efforts for adapting deep frameworks into KNN. The paper ignores all such works. Thus, it is not clear how significant is the proposed contribution. There are also not comparisons what-so-ever to competitive prior works.
4) Novelty
The main contribution of this paper is basically a set of experiments looking into architectural choices. However, the results of this study do not provide any surprises. It appears that batch normalization is essential for good performances, while using RELU is not so when one wants to use all directions for effective data encoding. Thus, as such, the novelty or the contributions of this paper are minor.
Overall, while I find there are some interesting theoretical bits in this paper, it lacks focus, the experiments do not offer any surprises, and there are no comparisons with prior literature. Thus, I do not think this paper is ready to be accepted in its present form.