Export Reviews, Discussions, Author Feedback and Meta-Reviews

"NIPS Neural Information Processing Systems 8-11th December 2014, Montreal, Canada",,, "Paper ID:","132" "Title:","Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation" Current Reviews First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. The paper considers the effect of memory constraints on some classes of online and distributed algorithms. The main goal of the authors is to show that there exist learning problems where imposing a memory constraint provably hurts the performance of any algorithm, in the sense that the best achievable performance guarantees are worse than some known upper bound on an algorithm that operates without memory constraints. The authors also provide a lower bound on the regret of online algorithms that operate under a specific feedback constraint. The results of the paper follow from an elegant information-theoretic argument concerning hide-and-seek problems where a learner has to detect a biased coordinate of i.i.d.