Publications

Trimmed MLE achieves near-optimal error rate for Generalized Linear Models under adversarial corruptions.

First differentially private PCA algorithm with $\tilde{O} (d)$ sample complexity for sub-Gaussian data.

We prove nonparametric MLE achieves minimax optimal rate for nonparametric mixture of Poisson distributions.

A general receipe for minimax optimal algorithm (exponential time) on differentially private and robust mean estimation, linear regression, covariance estimation, PCA.

First differentially private robust mean estimation algorithm for high dimensional distributions.

A meta-algorithm that adapts to the optimal model complexity with regret bound $\tilde{O}(d_*T^{2/3})$.

Smooth time/sample complexity trade-off between the number of tasks and the dataset size of each task. Algorithmic contribution includes an optimal robust PCA algorithm.

First poly time/sample complexity algorithm for $k$-mixture linear regression by utilizing a small set of tasks each with $\tilde{O}(\sqrt{k})$ examples.

Estimate the distribution of treatment effects.

Estimate optimal policy value of contextual bandits with $K$ disjoint $d$-dimensional arms in $\tilde{O} (\sqrt{d}K)$ rounds, minimax optimal up to log factors.

$n$ different coins, each tossed $t$ times, estimate distribution of coin biases with Wasserstein error $O(1/\sqrt{t\log n})$ when $n<2^t$, minimax optimal.

Solve $\epsilon$ corrupted linear regression up to $\tilde{O}(\epsilon)$ error under gaussianity assumption, minimax optimal, previous work achieves $\sqrt{\epsilon}$.

Estimate optimal prediction error of linear regression/classification with $O(\sqrt{d})$ examples, minimax optimal.

Approximate graph Laplacian specturm in constant time.

$n$ different coins, each tossed $t$ times, estimate distribution of coin biases with Wasserstein error $O(1/{t})$ when $n\ge 2^t$, minimax optimal.

First algorithm consistently estimates eigenvalues of covariance with $o(d)$ samples.