937 citations · 3.8k across the 80 of their papers we have counts for
5 papers · 1 filter
Distance-based and continuum Fano inequalities with applications to statistical estimation
John C. Duchi, Martin J. Wainwright
In this technical note, we give two extensions of the classical Fano inequality in information theory. The first extends Fano's inequality to the setting of estimation, providing l…
Optimal rates for zero-order convex optimization: the power of two function evaluations
John C. Duchi, Michael I. Jordan, Martin J. Wainwright +1
We consider derivative-free algorithms for stochastic and non-stochastic convex optimization problems that use only function values rather than gradients. Focusing on non-asymptoti…
Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation
John C. Duchi, Michael I. Jordan, Martin J. Wainwright
We provide a detailed study of the estimation of probability distributions---discrete and continuous---in a stringent setting in which data is kept private even from the statistici…
Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
Yuchen Zhang, John C. Duchi, Martin J. Wainwright
We establish optimal convergence rates for a decomposition-based scalable approach to kernel ridge regression. The method is simple to describe: it randomly partitions a dataset of…
Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates
John C. Duchi, Michael I. Jordan, Martin J. Wainwright
Working under a model of privacy in which data remains private even from the statistician, we study the tradeoff between privacy guarantees and the utility of the resulting statist…