A Sequential Lightbulb Problem

The light bulb problem is a fundamental unsupervised learning problem about identifying correlations amidst noise. In this report, we explore an online formulation of the light bulb problem. In light of the fact that the known offline approaches to the problem require super-linear space, we develop a simple algorithm which can solve the online problem using (O(n)) space in (\tilde O(n)) rounds. We then provide an enhanced algorithm which can toggle a tradeoff between space and rounds: namely, for any (\alpha\in (0,1)), one can solve the online lightbulb problem with (O(n^{1-\alpha})) space and (\tilde O(n^{1+\alpha})) rounds. This method can be extended to allow for constant space, at the expense of quadratic rounds. Finally, we prove relevant lower bounds for the problem.