4 papers
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…
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…
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…
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…