54 citations · 151 across the 13 of their papers we have counts for
14 papers
A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees
Tarun Kathuria
Let be positive semidefinite matrices of rank at most , with and $\norm{A_i}\le\varepsilon$. We prove that one sign can be assigned to each origi…
Leveraging Pretrained Language Models as Energy Functions for Glauber Dynamics Text Diffusion
Tarun Kathuria, Sachin Kumar
We present a discrete diffusion-based language model using Glauber dynamics from statistical physics. Our main insight is that instead of trying to train a discrete state space dif…
A Matrix Bernstein Inequality for Strong Rayleigh Distributions
Tarun Kathuria
The Entropy method provides a powerful framework for proving scalar concentration inequalities by establishing functional inequalities like Poincare and log-Sobolev inequalities. T…
A Faster Interior Point Method for Semidefinite Programming
Haotian Jiang, Tarun Kathuria, Yin Tat Lee +2
Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, a…
A Potential Reduction Inspired Algorithm for Exact Max Flow in Almost Time
Tarun Kathuria
We present an algorithm for computing - maximum flows in directed graphs in time. Our algorithm is inspired by potential reduction interi…
Scalar Poincaré Implies Matrix Poincaré
Ankit Garg, Tarun Kathuria, Nikhil Srivastava
We prove that every reversible Markov semigroup which satisfies a Poincaré inequality satisfies a matrix-valued Poincaré inequality for Hermitian matrix valued function…
On Concentration Inequalities for Random Matrix Products
Tarun Kathuria, Satyaki Mukherjee, Nikhil Srivastava
Consider complex random matrices of size sampled i.i.d. from a distribution with mean . While the concentration of averages of these matric…
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria +2
We study efficient algorithms for linear regression and covariance estimation in the absence of Gaussian assumptions on the underlying distributions of samples, making assumptions…
Fair and Diverse DPP-based Data Summarization
L. Elisa Celis, Vijay Keswani, Damian Straszak +3
Sampling methods that choose a subset of the data proportional to its diversity in the feature space are popular for data summarization. However, recent studies have noted the occu…
Batched Gaussian Process Bandit Optimization via Determinantal Point Processes
Tarun Kathuria, Amit Deshpande, Pushmeet Kohli
Gaussian Process bandit optimization has emerged as a powerful tool for optimizing noisy black box functions. One example in machine learning is hyper-parameter optimization where…
How to be Fair and Diverse?
L. Elisa Celis, Amit Deshpande, Tarun Kathuria +1
Due to the recent cases of algorithmic bias in data-driven decision-making, machine learning methods are being put under the microscope in order to understand the root cause of the…
On the Complexity of Constrained Determinantal Point Processes
L. Elisa Celis, Amit Deshpande, Tarun Kathuria +2
Determinantal Point Processes (DPPs) are probabilistic models that arise in quantum physics and random matrix theory and have recently found numerous applications in computer scien…
On Sampling and Greedy MAP Inference of Constrained Determinantal Point Processes
Tarun Kathuria, Amit Deshpande
Subset selection problems ask for a small, diverse yet representative subset of the given data. When pairwise similarities are captured by a kernel, the determinants of submatrices…
Efficient and Provable Multi-Query Optimization
Tarun Kathuria, S. Sudarshan
Complex queries for massive data analysis jobs have become increasingly commonplace. Many such queries contain com- mon subexpressions, either within a single query or among multip…