Publications (10)
Improved Spectral Density Estimation via Explicit and Implicit Deflation
Rajarshi Bhattacharjee, Rajesh Jayaram, Cameron Musco +2
We study algorithms for approximating the spectral density of a symmetric matrix that is accessed through matrix-vector product queries. By combining a previously studied Cheby…
Adaptive and Robust Watermark for Generative Tabular Data
Dung Daniel Ngo, Archan Ray, Akshay Seshadri +6
In recent years, watermarking generative tabular data has become a prominent framework to protect against the misuse of synthetic data. However, while most prior work in watermarki…
MetaTT: A Global Tensor-Train Adapter for Parameter-Efficient Fine-Tuning
Javier Lopez-Piqueres, Pranav Deshpande, Archan Ray +3
We present MetaTT, a Tensor Train (TT) adapter framework for fine-tuning of pre-trained transformers. MetaTT enables flexible and parameter-efficient model adaptation by using a si…
A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
Tyler Chen, Akshay Seshadri, Mattia J. Villani +7
Shapley values have emerged as a critical tool for explaining which features impact the decisions made by machine learning models. However, computing exact Shapley values is diffic…
Sublinear Time Eigenvalue Approximation via Random Sampling
Rajarshi Bhattacharjee, Gregory Dexter, Petros Drineas +2
We study the problem of approximating the eigenspectrum of a symmetric matrix with bounded entries (i.e., ).…
Sublinear Time Approximation of Text Similarity Matrices
Archan Ray, Nicholas Monath, Andrew McCallum +1
We study algorithms for approximating pairwise similarity matrices that arise in natural language processing. Generally, computing a similarity matrix for data points requires…
A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems
Tyler Chen, Junhyung Lyle Kim, Archan Ray +3
We describe and analyze a simple algorithm for sampling from the solution to a linear system . We assume…
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra
Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco +3
Let satisfy , where is the all ones matrix and is the spectral norm. It is well-kn…
GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches
Tyler Chen, Pradeep Niroula, Archan Ray +3
A litany of theoretical and numerical results have established the sketch-and-precondition paradigm as a powerful approach to solving large linear regression problems in standard c…
Provably faster randomized and quantum algorithms for -means clustering via uniform sampling
Tyler Chen, Archan Ray, Akshay Seshadri +6
The -means algorithm (Lloyd's algorithm) is a widely used method for clustering unlabeled data. A key bottleneck of the -means algorithm is that each iteration requires time…