Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
Ohad Shamir Weizmann Institute of Science
Abstract
Many machine learning approaches are characterized by information constraints on how they interact with the training data. These include memory and sequential access constraints (e.g. fast first-order methods to solve stochastic optimization problems); communication constraints (e.g. distributed learning); partial access to the underlying data (e.g. missing features and multi-armed bandits) and more. However, currently we have little understanding how such information constraints fundamentally affect our performance, independent of the learning problem semantics. For example, are there learning problems where any algorithm which has small memory footprint (or can use any bounded number of bits from each example, or has certain communication constraints) will perform worse than what is possible without such constraints? In this paper, we describe how a single set of results implies positive answers to the above, for several different settings.
中文速览
机器学习算法在实际应用中往往受到各种信息约束——比如内存有限、机器间通信带宽受限、或者每轮只能看到部分数据——但究竟这些约束会让学习性能差到什么程度，此前缺乏统一的理论框架来回答。本文提出了一类名为"(b,n,m)协议"的通用信息约束模型，将在线学习、分布式学习、稀疏估计等场景统一纳入同一框架，并利用信息论工具推导出一系列下界结果：在线部分信息学习的遗憾下界为Ω(√(d/b·T))，稀疏PCA和稀疏协方差估计需要至少Ω̃(d²)比特的内存或通信才能达到统计最优，甚至某些随机优化问题中线性内存的算法（如随机梯度下降）从根本上无法达到最优样本复杂度。这些结果首次从理论上证明了信息约束与统计性能之间存在不可避免的权衡，为理解各类受限学习算法的本质局限性提供了坚实基础。
原文 arXiv:1311.3494;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1311.3494v6