CAREER: Statistical Inference Under Information Constraints: Efficient Algorithms and Fundamental Limits

数据科学和机器学习系统必须优化对数据可用性、计算时间、存储内存和隐私问题的约束。例如，当在移动设备上执行网络搜索时，人们希望应用程序体积小，尽可能少地通信数据，并尽可能少地泄露关于用户的信息。这些限制往往相互抵触。提供强大隐私保障的系统可能需要更多数据和计算，而使用较少数据的系统可能需要更多计算。从根本上理解受限资源(如样本、时间、内存、通信和隐私)之间的限制和权衡，对于解决摆在数据科学面前的许多挑战至关重要。尽管数据科学有许多成功的故事，但即使在一些最简单的环境中，人们对这些权衡也知之甚少。该项目旨在建立这些资源之间的基本权衡，并设计实现这些资源的有效方案。项目成果可以帮助设计更快、更节省通信、保护隐私和节省空间的学习系统。该项目旨在通过面向本科生和代表性不足的社区的外展活动，让不同的研究人员参与到这个项目中来。调查人员将制定和研究基本的统计推断任务，如在上述信息约束下的分布估计、假设检验和分布性质估计。一个特别感兴趣的方向是共享随机性的可用性对分布式机器学习系统的其他约束的影响。虽然随机性在通信复杂性问题中的作用已经被研究，但它在机器学习系统中的作用往往被忽视。该项目将整合来自计算机科学、信息论、机器学习和统计学的想法，寻求在这些社区的研究人员之间架起桥梁。该项目的所有发现将通过出版物发布，并将在研究人员的网站上公布。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Data science and machine learning systems have to optimize constraints on the availability of data, computation time, memory for storage, and privacy concerns. For example, while performing web search on mobile devices, one would like the applications to be small in size, communicate as little data as possible, and leak as little about the user as possible. These constraints are often at odds with each other. A system that provides strong privacy guarantees might require more data and computation, and a system that uses little data might require more computation. A fundamental understanding of the limits and trade-offs between constrained resources such as samples, time, memory, communication, and privacy is critical for tackling the many challenges in data science that lay ahead. In spite of many success stories of data science, these trade-offs are poorly understood even in some of the simplest settings. This project aims to establish the fundamental trade-offs between these resources, as well as design efficient schemes that achieve them. The project outcomes can help design faster, communication-frugal, privacy-preserving, and space-efficient learning systems. The project seeks to involve the participation of a diverse group of researchers in this project through outreach activities that target undergraduate students and under-represented communities.The investigator will formulate and study fundamental statistical inference tasks such as distribution estimation, hypothesis testing, and distribution property estimation under the information constraints mentioned above. A particular direction of interest is the impact of the availability of shared randomness on the other constraints for distributed machine learning systems. While the role of randomness has been studied in problems in communication complexity, its role in machine learning systems is often overlooked. The project will integrate ideas from computer science, information theory, machine learning, and statistics, seeking to bridge researchers from these communities. All findings of this project will be disseminated through publications, and will be made publicly available on the investigator's website.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.