Publications (9)
On the Approximation Properties of Random ReLU Features
Yitong Sun, Anna Gilbert, Ambuj Tewari
We study the approximation properties of random ReLU features through their reproducing kernel Hilbert space (RKHS). We first prove a universality theorem for the RKHS induced by r…
Revisiting the Necessity of Graph Learning and Common Graph Benchmarks
Isay Katsman, Ethan Lou, Anna Gilbert
Graph machine learning has enjoyed a meteoric rise in popularity since the introduction of deep learning in graph contexts. This is no surprise due to the ubiquity of graph data in…
Shedding Light on Problems with Hyperbolic Graph Learning
Isay Katsman, Anna Gilbert
Recent papers in the graph machine learning literature have introduced a number of approaches for hyperbolic representation learning. The asserted benefits are improved performance…
Sparse Recovery for Orthogonal Polynomial Transforms
Anna Gilbert, Albert Gu, Christopher Re +2
In this paper we consider the following sparse recovery problem. We have query access to a vector $\vx \in \R^N$ such that $\vhx = \vF \vx$ is -sparse (or nearly -sparse) for…
But How Does It Work in Theory? Linear SVM with Random Features
Yitong Sun, Anna Gilbert, Ambuj Tewari
We prove that, under low noise assumptions, the support vector machine with random features (RFSVM) can achieve the learning rate faster than on a training…
Wasserstein Wormhole: Scalable Optimal Transport Distance with Transformers
Doron Haviv, Russell Zhang Kunes, Thomas Dougherty +4
Optimal transport (OT) and the related Wasserstein metric (W) are powerful and ubiquitous tools for comparing distributions. However, computing pairwise Wasserstein distances rapid…
Metric repair is two problems: Which edges, and what weights
Asaf Etgar, Anna Gilbert
Real distance data rarely cooperate: measurements are noisy, observations are missing, and the numbers that result seldom satisfy the triangle inequality. A family of methods exist…
Theoretical and Experimental Analysis of a Randomized Algorithm for Sparse Fourier Transform Analysis
Jing Zou, Anna Gilbert, Martin Strauss +1
We analyze a sublinear RAlSFA (Randomized Algorithm for Sparse Fourier Analysis) that finds a near-optimal B-term Sparse Representation R for a given discrete signal S of length N,…
Property Testing for Differential Privacy
Anna Gilbert, Audra McMillan
We consider the problem of property testing for differential privacy: with black-box access to a purportedly private algorithm, can we verify its privacy guarantees? In particular,…