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

CIF：小：统计学习中的信息理论和计算阈值

• 批准号: 1714305
• 负责人: Andrea Montanari
• 金额: $ 45万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-01 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1714305&HistoricalAwards=false
• 关键词: CIF; Small; Information; theoretic; Computational

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.

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

项目成果

Discussion of: “Nonparametric regression using deep neural networks with ReLU activation function”

• DOI: 10.1214/19-aos1910
• 发表时间: 2020-08
• 期刊: The Annals of Statistics
• 作者: B. Ghorbani;Song Mei;Theodor Misiakiewicz;A. Montanari

Optimization of the Sherrington--Kirkpatrick Hamiltonian

Sherrington--Kirkpatrick 哈密顿量的优化

• DOI: 10.1137/20m132016x
• 发表时间: 2021
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Montanari, Andrea

Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit

两层神经网络的平均场理论：无维数界限和核极限

• 发表时间: 2019
• 期刊: Proceedings of the Thirty-Second Conference on Learning Theory
• 作者: Mei, Song;Misiakiewicz, Theodor;Montanari, Andrea
• 通讯作者: Montanari, Andrea

The threshold for SDP-refutation of random regular NAE-3SAT

• DOI: 10.1137/1.9781611975482.140
• 发表时间: 2018-04
• 期刊: ArXiv
• 作者: Y. Deshpande;A. Montanari;R. O'Donnell;T. Schramm;S. Sen

On the Connection Between Learning Two-Layer Neural Networks and Tensor Decomposition

论学习两层神经网络与张量分解的联系

• 发表时间: 2019
• 期刊: Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics
• 作者: Marco Mondelli, Andrea Montanari