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.

先进的算法是一种越来越强大的工具，可以通过智能手机，传感器网络或高通量科学研究在互联网上收集大量数据，从而收集大量的数据。由于这些方法变得无处不在，因此了解其全部潜力至关重要。我们希望从某种类型的数据中提取哪种信息？ Viceversa，我们应该积累多少数据以推断某些信息？什么是阻止我们提取更多信息的瓶颈？这些问题已经在古典统计数据中进行了研究，但是现代应用程序提出了全新的挑战，经典概念仅部分有用。尤其是，计算资源成为现代数据集的至关重要的瓶颈。在许多情况下，尽管该数据原则上包含感兴趣的信息，但发现它是一条爆炸问题的问题，并且无法在人类时标上完成。该项目的目的是在几个核心问题中表征这些基本局限性，并开发可以达到这些限制的算法。各个信息理论和复杂性理论都无法捕获对统计学习任务的基本局限性。该项目遵循一种不同的方法，旨在分析广泛的算法类别，并在其行为之间建立联系。更确切地说，该项目考虑了三个这样的类别，这些类别本质上涵盖了当今大多数算法：经验风险最小化；半决赛编程层次结构；和本地算法。重点是与许多应用相关的两个具体统计估计问题：图上的组同步；非线性高维回归和分类。 在这些和类似的问题中，看似不同类型的算法的行为通常非常相似。 了解这种相似性及其含义的起源是这项研究的重点。

项目成果

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

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

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

An Instability in Variational Inference for Topic Models

• 发表时间: 2018-02
• 作者: B. Ghorbani;H. Javadi;A. Montanari