104 citations · 270 across the 46 of their papers we have counts for
5 papers · 1 filter
Sample-efficient proper PAC learning with approximate differential privacy
Badih Ghazi, Noah Golowich, Ravi Kumar +1
In this paper we prove that the sample complexity of properly learning a class of Littlestone dimension with approximate differential privacy is , ignoring priva…
Tight last-iterate convergence rates for no-regret learning in multi-player games
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis
We study the question of obtaining last-iterate convergence rates for no-regret learning algorithms in multi-player games. We show that the optimistic gradient (OG) algorithm with…
Near-tight closure bounds for Littlestone and threshold dimensions
Badih Ghazi, Noah Golowich, Ravi Kumar +1
We study closure properties for the Littlestone and threshold dimensions of binary hypothesis classes. Given classes of Boolean functions wit…
Pure Differentially Private Summation from Anonymous Messages
Badih Ghazi, Noah Golowich, Ravi Kumar +3
The shuffled (aka anonymous) model has recently generated significant interest as a candidate distributed privacy framework with trust assumptions better than the central model but…
Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis +1
In this paper we study the smooth convex-concave saddle point problem. Specifically, we analyze the last iterate convergence properties of the Extragradient (EG) algorithm. It is w…