CIF:Small:Information-theoretic and Computational Thresholds in Statistical Learning

先进的算法是一种越来越强大的工具，可以从互联网、智能手机、传感器网络或高通量科学研究收集的大量数据中提取信息。随着这些方法变得无处不在，了解它们的全部潜力至关重要。我们希望从某种类型的数据中提取什么样的信息？反之亦然，为了能够推断出某条信息，我们应该积累多少数据？阻碍我们获取更多信息的瓶颈是什么？这些问题已经在经典统计学中进行了研究，但现代应用提出了全新的挑战，经典概念仅部分有用。特别是，计算资源成为现代数据集的关键瓶颈。在许多情况下，虽然数据原则上包含感兴趣的信息，但找到它是大海捞针的问题，并且无法在人类的时间尺度上完成。该项目旨在描述几个核心问题中的这些基本限制，并开发能够实现这些限制的算法。信息理论和复杂性理论都没有抓住统计学习任务的基本限制。这个项目采用了一种不同的方法，旨在分析广泛的算法类别，并在它们的行为之间建立联系。更准确地说，该项目考虑了三个这样的类别，基本上涵盖了目前使用的大多数算法：经验风险最小化；半定规划层次；还有局部算法。重点是与许多应用程序相关的两个具体的统计估计问题：图上的组同步；非线性高维回归与分类。在这些和类似的问题中，看似不同类型的算法的行为往往惊人地相似。了解这种相似性的起源及其含义是本研究的重点。

Advanced algorithms are an increasingly powerful tool to extract information from vast amount of datathat are gathered over the Internet, by smartphones, sensors networks, or high-throughput scientific studies.As these methods become ubiquitous, it is crucial to understand their full potential. What kind ofinformation can we hope to extract from a certain type of data? Viceversa, how much data shouldwe accumulate in order to be able to infer a certain piece of information? What is the bottleneck that prevents us from extracting more information? These questions have been studied within classical statistics, but modern applications pose entirely new challenges and classical concepts are only partially useful.In particular, computational resources become a crucial bottleneck for modern datasets. In many cases,although the data contain in principle the information of interest, finding it is a needle-in-haystack problem, and cannot be done on human timescales. This project aims at characterizing these fundamental limitations in several central problems, and develop algorithms that can achieve those limits.Both information theory and complexity theory fall short of capturing the fundamental limitations to statistical learning tasks. This project follows a different approach which aims at analyzing broad classes of algorithms, and draw connections between their behavior. More precisely, the project considers three such classes that essentially encompass most algorithms used nowadays: empirical risk minimization;semidefinite programming hierarchies; and local algorithms. The focus is on two concrete statistical estimation problems that are relevant for a number of applications: group synchronization on graphs; non-linear high-dimensional regression and classification. In these and analogous problems, the behavior of seemingly different types of algorithms is often surprisingly similar. Understanding the origin of this similarity and its implications is a key focus of this research.