261 citations · 836 across the 30 of their papers we have counts for
34 papers
Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Norm
Meena Jagadeesan, Ilya Razenshteyn, Suriya Gunasekar
We provide a function space characterization of the inductive bias resulting from minimizing the norm of the weights in multi-channel convolutional neural networks with li…
A Study of Performance of Optimal Transport
Yihe Dong, Yu Gao, Richard Peng +2
We investigate the problem of efficiently computing optimal transport (OT) distances, which is equivalent to the node-capacitated minimum cost maximum flow problem in a bipartite g…
Non-Adaptive Adaptive Sampling on Turnstile Streams
Sepideh Mahabadi, Ilya Razenshteyn, David P. Woodruff +1
Adaptive sampling is a useful algorithmic tool for data summarization problems in the classical centralized setting, where the entire dataset is available to the single processor p…
Scaling up Kernel Ridge Regression via Locality Sensitive Hashing
Michael Kapralov, Navid Nouri, Ilya Razenshteyn +2
Random binning features, introduced in the seminal paper of Rahimi and Recht (2007), are an efficient method for approximating a kernel matrix using locality sensitive hashing. Ran…
Randomized Smoothing of All Shapes and Sizes
Greg Yang, Tony Duan, J. Edward Hu +3
Randomized smoothing is the current state-of-the-art defense with provable robustness against adversarial attacks. Many works have devised new randomized smoothing schemes…
Scalable Nearest Neighbor Search for Optimal Transport
Arturs Backurs, Yihe Dong, Piotr Indyk +2
The Optimal Transport (a.k.a. Wasserstein) distance is an increasingly popular similarity measure for rich data domains, such as images or text documents. This raises the necessity…
Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
Hadi Salman, Greg Yang, Jerry Li +4
Recent works have shown the effectiveness of randomized smoothing as a scalable technique for building neural network-based classifiers that are provably robust to -norm ad…
SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Search
Hao Chen, Ilaria Chillotti, Yihe Dong +3
The -Nearest Neighbor Search (-NNS) is the backbone of several cloud-based services such as recommender systems, face recognition, and database search on text and images. In…
On Mean Estimation for General Norms with Statistical Queries
Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn +1
We study the problem of mean estimation for high-dimensional distributions, assuming access to a statistical query oracle for the distribution. For a normed space $X = (\mathbb{R}^…
Learning Space Partitions for Nearest Neighbor Search
Yihe Dong, Piotr Indyk, Ilya Razenshteyn +1
Space partitions of underlie a vast and important class of fast nearest neighbor search (NNS) algorithms. Inspired by recent theoretical work on NNS for general metr…
Adversarial Examples from Cryptographic Pseudo-Random Generators
Sébastien Bubeck, Yin Tat Lee, Eric Price +1
In our recent work (Bubeck, Price, Razenshteyn, arXiv:1805.10204) we argued that adversarial examples in machine learning might be due to an inherent computational hardness of the…
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev +1
We introduce and study the notion of an outer bi-Lipschitz extension of a map between Euclidean spaces. The notion is a natural analogue of the notion of a Lipschitz extension of a…
Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn
Consider an instance of Euclidean -means or -medians clustering. We show that the cost of the optimal solution is preserved up to a factor of under a projec…
Approximate Nearest Neighbor Search in High Dimensions
Alexandr Andoni, Piotr Indyk, Ilya Razenshteyn
The nearest neighbor problem is defined as follows: Given a set of points in some metric space , build a data structure that, given any point , returns a point in…
Adversarial examples from computational constraints
Sébastien Bubeck, Eric Price, Ilya Razenshteyn
Why are classifiers in high dimension vulnerable to "adversarial" perturbations? We show that it is likely not due to information theoretic limitations, but rather it could be due…
Practical Data-Dependent Metric Compression with Provable Guarantees
Piotr Indyk, Ilya Razenshteyn, Tal Wagner
We introduce a new distance-preserving compact representation of multi-dimensional point-sets. Given points in a -dimensional space where each coordinate is represented usin…
Approximate Near Neighbors for General Symmetric Norms
Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov +2
We show that every symmetric normed space admits an efficient nearest neighbor search data structure with doubly-logarithmic approximation. Specifically, for every , $d = n^{o(1…
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn +1
[See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the -Approximate Near Neighbor Search problem. For the -dimensional…
Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors
Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn +1
We show tight lower bounds for the entire trade-off between space and query time for the Approximate Near Neighbor search problem. Our lower bounds hold in a restricted model of co…
On the Complexity of Inner Product Similarity Join
Thomas D. Ahle, Rasmus Pagh, Ilya Razenshteyn +1
A number of tasks in classification, information retrieval, recommendation systems, and record linkage reduce to the core problem of inner product similarity join (IPS join): ident…
Practical and Optimal LSH for Angular Distance
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven +2
We show the existence of a Locality-Sensitive Hashing (LSH) family for the angular distance that yields an approximate Near Neighbor Search algorithm with the asymptotically optima…
Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing
Alexandr Andoni, Ilya Razenshteyn
We prove a tight lower bound for the exponent for data-dependent Locality-Sensitive Hashing schemes, recently used to design efficient solutions for the -approximate nearest…
Nearly-optimal bounds for sparse recovery in generic norms, with applications to -median sketching
Arturs Backurs, Piotr Indyk, Eric Price +2
We initiate the study of trade-offs between sparsity and the number of measurements in sparse recovery schemes for generic norms. Specifically, for a norm , sparsity par…
Optimal Data-Dependent Hashing for Approximate Near Neighbors
Alexandr Andoni, Ilya Razenshteyn
We show an optimal data-dependent hashing scheme for the approximate near neighbor problem. For an -point data set in a -dimensional space our data structure achieves query t…