Anna C. Gilbert

ICML Conference 2024 Conference Paper

Wasserstein Wormhole: Scalable Optimal Transport Distance with Transformer

• Doron Haviv
• Russell Zhang Kunes
• Thomas Dougherty
• Cassandra Burdziak
• Tal Nawy
• Anna C. Gilbert
• Dana Pe'er

Optimal transport (OT) and the related Wasserstein metric ($W$) are powerful and ubiquitous tools for comparing distributions. However, computing pairwise Wasserstein distances rapidly becomes intractable as cohort size grows. An attractive alternative would be to find an embedding space in which pairwise Euclidean distances map to OT distances, akin to standard multidimensional scaling (MDS). We present Wasserstein Wormhole, a transformer-based autoencoder that embeds empirical distributions into a latent space wherein Euclidean distances approximate OT distances. Extending MDS theory, we show that our objective function implies a bound on the error incurred when embedding non-Euclidean distances. Empirically, distances between Wormhole embeddings closely match Wasserstein distances, enabling linear time computation of OT distances. Along with an encoder that maps distributions to embeddings, Wasserstein Wormhole includes a decoder that maps embeddings back to distributions, allowing for operations in the embedding space to generalize to OT spaces, such as Wasserstein barycenter estimation and OT interpolation. By lending scalability and interpretability to OT approaches, Wasserstein Wormhole unlocks new avenues for data analysis in the fields of computational geometry and single-cell biology.

JMLR Journal 2022 Journal Article

Project and Forget: Solving Large-Scale Metric Constrained Problems

• Rishi Sonthalia
• Anna C. Gilbert

Many important machine learning problems can be formulated as highly constrained convex optimization problems. One important example is metric constrained problems. In this paper, we show that standard optimization techniques can not be used to solve metric constrained problem. To solve such problems, we provide a general active set framework, called Project and Forget, and several variants thereof that use Bregman projections. Project and Forget is a general purpose method that can be used to solve highly constrained convex problems with many (possibly exponentially) constraints. We provide a theoretical analysis of Project and Forget and prove that our algorithms converge to the global optimal solution and have a linear rate of convergence. We demonstrate that using our method, we can solve large problem instances of general weighted correlation clustering, metric nearness, information theoretic metric learning and quadratically regularized optimal transport; in each case, out-performing the state of the art methods with respect to CPU times and problem sizes. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2022. ( edit, beta )

UAI Conference 2020 Conference Paper

Spectral Methods for Ranking with Scarce Data

• Lalit Jain
• Anna C. Gilbert
• Umang Varma

Given a number of pairwise preferences of items, a common task is to rank all the items. Examples include pairwise movie ratings, New Yorker cartoon caption contests, and many other consumer preferences tasks. What these settings have in common is two-fold: a scarcity of data (it may be costly to get comparisons for all the pairs of items) and additional feature information about the items (e. g. , movie genre, director, and cast). In this paper we modify a popular and well studied method, RankCentrality for rank aggregation to account for few comparisons and that incorporates additional feature information. This method returns meaningful rankings even under scarce comparisons. Using diffusion based methods, we incorporate feature information that outperforms state-of-the-art methods in practice. We also provide improved sample complexity for RankCentrality in a variety of sampling schemes.

STOC Conference 2010 Conference Paper

Approximate sparse recovery: optimizing time and measurements

• Anna C. Gilbert
• Yi Li 0002
• Ely Porat
• Martin J. Strauss

A Euclidean approximate sparse recovery system consists of parameters k,N, an m-by-N measurement matrix , Φ, and a decoding algorithm, D. Given a vector, x, the system approximates x by ^x=D(Φ x), which must satisfy || x - x|| 2 ≤ C ||x - x k || 2 , where x k denotes the optimal k-term approximation to x. (The output ^x may have more than k terms). For each vector x, the system must succeed with probability at least 3/4. Among the goals in designing such systems are minimizing the number m of measurements and the runtime of the decoding algorithm, D.

STOC Conference 2007 Conference Paper

One sketch for all: fast algorithms for compressed sensing

• Anna C. Gilbert
• Martin J. Strauss
• Joel A. Tropp
• Roman Vershynin

Compressed Sensing is a new paradigm for acquiring the compressible signals that arise in many applications. These signals can be approximated using an amount of information much smaller than the nominal dimension of the signal. Traditional approaches acquire the entire signal and process it to extract the information. The new approach acquires a small number of nonadaptive linear measurements of the signal and uses sophisticated algorithms to determine its information content. Emerging technologies can compute these general linear measurements of a signal at unit cost per measurement.

SODA Conference 2005 Conference Paper

Improved range-summable random variable construction algorithms

• A. Robert Calderbank
• Anna C. Gilbert
• Kirill Levchenko
• S. Muthukrishnan 0001
• Martin J. Strauss

SODA Conference 2003 Conference Paper

Approximation of functions over redundant dictionaries using coherence

• Anna C. Gilbert
• S. Muthukrishnan 0001
• Martin J. Strauss

STOC Conference 2003 Conference Paper

On the fractal behavior of TCP

• Anna C. Gilbert
• Howard J. Karloff

We propose a natural, mathematically tractable model of TCP which captures both its additive-increase, multiplicative-decrease behavior and its feedback mechanism. Neither a fluid nor a mean-field model, our model does not explicitly model the loss process; the losses are entirely determined by the rates of the sources at the time of buffer overflow. The system involves two sources competing to send packets into one recipient buffer of size B , from which bytes are drained at the rate of d per step. We prove that for many choices of the pairs (B,d) , the long term behavior of the system is fractal. We conjecture that this fact continues to hold for all B > d and d > 2 .

STOC Conference 2002 Conference Paper

Fast, small-space algorithms for approximate histogram maintenance

• Anna C. Gilbert
• Sudipto Guha
• Piotr Indyk
• Yannis Kotidis
• S. Muthukrishnan 0001
• Martin J. Strauss

(MATH) A vector A of length N is defined implicitly, via a stream of updates of the form "add 5 to A 3 ." We give a sketching algorithm, that constructs a small sketch from the stream of updates, and a reconstruction algorithm, that produces a B -bucket piecewise-constant representation (histogram) H for A from the sketch, such that || A—H ||≤(1+ε)|| A—H opt ||, where the error || A—H || is either $\ell_1$ (absolute) or $\ell_2$ (root-mean-square) error. The time to process a single update, time to reconstruct the histogram, and size of the sketch are each bounded by poly( B ,log( N ),log|| A ,1/ε. Our result is obtained in two steps. First we obtain what we call a robust histogram approximation for A , a histogram such that adding a small number of buckets does not help improve the representation quality significantly. From the robust histogram, we cull a histogram of desired accruacy and B buckets in the second step. This technique also provides similar results for Haar wavelet representations, under $\ell_2$ error. Our results have applications in summarizing data distributions fast and succinctly even in distributed settings.

STOC Conference 2002 Conference Paper

Near-optimal sparse fourier representations via sampling

• Anna C. Gilbert
• Sudipto Guha
• Piotr Indyk
• S. Muthukrishnan 0001
• Martin J. Strauss

(MATH) We give an algorithm for finding a Fourier representation R of B terms for a given discrete signal signal A of length N , such that $\|\signal-\repn\|_2^2$ is within the factor (1 +ε) of best possible $\|\signal-\repn_\opt\|_2^2$. Our algorithm can access A by reading its values on a sample set T ⊆[0, N ), chosen randomly from a (non-product) distribution of our choice, independent of A . That is, we sample non-adaptively. The total time cost of the algorithm is polynomial in B log( N )log( M )ε (where M is the ratio of largest to smallest numerical quantity encountered), which implies a similar bound for the number of samples.