Private Learning Implies Online Learning: An Efficient Reduction

Differential Private Learning and Online Learning are two well-studied areas in machine learning. While at a first glance these two subjects may seem disparate, recent works gathered a growing amount of evidence which suggests otherwise. For example, Adaptive Data Analysis [15, 14, 24, 19, 3] shares strong similarities with adversarial frameworks studied in online learning, and on the other hand exploits ideas and tools from differential privacy. A more formal relation between private and online learning is manifested by the following fact: Every privately learnable class is online learnable. This implication and variants of it were derived by several recent works [20, 9, 1] (see the related work section for more details). One caveat of the latter results is that they are non-constructive: they show that every privately learnable class has a finite Littlestone dimension. Then, since the Littlestone dimension is known to capture online learnability [26, 5], it follows that privately learnable classes are indeed online learnable. Consequently, the implied online learner is not necessarily efficient, even if the assumed private learner is.