48 citations · 62 across the 5 of their papers we have counts for
6 papers
Privately Estimating a Gaussian: Efficient, Robust and Optimal
Daniel Alabi, Pravesh K. Kothari, Pranay Tankala +2
In this work, we give efficient algorithms for privately estimating a Gaussian distribution in both pure and approximate differential privacy (DP) models with optimal dependence on…
Efficient algorithms for certifying lower bounds on the discrepancy of random matrices
Prayaag Venkat
We initiate the study of the algorithmic problem of certifying lower bounds on the discrepancy of random matrices: given an input matrix , output a v…
Near-optimal fitting of ellipsoids to random points
Aaron Potechin, Paxton Turner, Prayaag Venkat +1
Given independent standard Gaussian points in dimension , for what values of does there exist with high probability an origin-symmetric ellipsoid tha…
Optimal Regularization Can Mitigate Double Descent
Preetum Nakkiran, Prayaag Venkat, Sham Kakade +1
Recent empirical and theoretical studies have shown that many learning algorithms -- from linear regression to neural networks -- can have test performance that is non-monotonic in…
A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates
Zhixian Lei, Kyle Luh, Prayaag Venkat +1
We study the algorithmic problem of estimating the mean of heavy-tailed random vector in , given i.i.d. samples. The goal is to design an efficient estimator that…
Select and Permute: An Improved Online Framework for Scheduling to Minimize Weighted Completion Time
Samir Khuller, Jingling Li, Pascal Sturmfels +2
In this paper, we introduce a new online scheduling framework for minimizing total weighted completion time in a general setting. The framework is inspired by the work of Hall et a…