Reviews: Private Learning Implies Online Learning: An Efficient Reduction

A theory paper showing that a reduction from online learning to differentially private PAC learning, e.g., a differentially private PAC learner for concept class H can be used in a black-box fashion to obtain a low regret bound for online learning with 0/1 loss for concept class H. The key contribution here is that this is a computationally efficient reduction, which resolves an open problem of Neel/Roth/Wu and improves on the information theoretic result of Feldman/Xiao. In addition to the strong result, the reviewers point out that the paper contains many interesting observations along the way (e.g., an innovative use of online boosting).