RI: Small: Statistically Sound and Computationally Efficient Data Analysis Through Algorithmic Applications of Rademacher Averages

RI：小：通过 Rademacher 平均值的算法应用进行统计上合理且计算高效的数据分析

基本信息

批准号：
1813444
负责人：
Eli Upfal
金额：
$ 45万
依托单位：
Brown University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-09-01 至 2023-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1813444&HistoricalAwards=false
关键词：
RI Small Statistically Sound Computationally

项目摘要

Machine learning and data mining are among the most influential contributions of computer science in the last decade. Given sufficiently large datasets and computational power one can discover patterns and make reasonably accurate predictions. While there has been tremendous progress in designing efficient algorithms for analyzing massive datasets, there has been less progress in providing rigorous measures of statistical significance or robustness of the analysis. As we analyze large and noisy datasets to model complex relationships in data, it is critical to develop formally proven methods with clear performance guarantees. This project advocates a responsible approach to data analysis, based on well-founded mathematical and statistical concepts. Such an approach enhances the effectiveness and reliability of evidence- based decision making in medicine, policy and other social applications of big data analysis. Capacity-building activities of this project include: (1) Creation and dissemination of algorithms and software that implement rigorous, interpretable, and usable computational and statistical approaches to big data analysis; and (2) Educational initiatives at the graduate and undergraduate level to build a bigger and more diverse workforce of data scientists with the appropriate foundational skills both to apply analytical tools to existing datasets and to develop new approaches to future datasets.The goal of this project is developing practical data analysis algorithmic applications based on the theoretical machine learning concept of Rademacher complexity. This project is motivated by preliminary results that have shown that the analytical properties of the Rademacher complexity, combined with its efficient sampling properties, provide a unique opportunity to develop general tools to begin bridging the gap between theory and practice in large scale data analysis. In particular, the project is focused on the following aims: improve the efficiency of rigorous data analysis algorithms through better sample complexity bounds; improve multi-comparisons and overfitting control through Rademacher generalization bounds; develop theory and practical applications of Cartesian and Chaos Rademacher Complexities; develop efficient algorithms for estimating the empirical Rademacher complexity; and explore new rigorous data analysis algorithms through the application of Rademacher theory.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.

机器学习和数据挖掘是过去十年中计算机科学最有影响力的贡献之一。给定足够大的数据集和计算能力，可以发现模式并做出合理准确的预测。尽管设计有效的算法用于分析大规模数据集，但在提供统计显着性或鲁棒性的严格度量方面取得了较少的进展。当我们分析大型和嘈杂的数据集以模拟数据中的复杂关系时，至关重要的是，开发具有明确性能保证的正式证明的方法。该项目基于基于基础良好的数学和统计概念提倡一种负责任的数据分析方法。这种方法增强了大数据分析中基于证据的决策，政策和其他社会应用的有效性和可靠性。该项目的能力建设活动包括：（1）创建和传播算法和软件，以实施严格，可解释和可用的计算和统计方法来进行大数据分析；（2）在研究生和本科层面的教育计划，以建立具有适当基础技能的数据科学家的更大，更多样化的劳动力，既可以将分析工具应用于现有数据集应用于现有数据集，又可以为未来的数据集开发新方法。该项目的目标是开发基于理论机器学习概念的实用数据分析应用程序分析应用程序分析应用程序。该项目的激励是由初步结果激发的，这些结果表明，Rademacher复杂性的分析特性与其有效的采样属性相结合，为开发一般工具提供了一个独特的机会，以开始在大规模数据分析中开始弥合理论和实践之间的差距。特别是，该项目的重点是以下目的：通过更好的样本复杂性界限提高严格数据分析算法的效率；通过Rademacher泛化界限改善多核子和过度拟合控制；发展笛卡尔和混乱的Rademacher复杂性的理论和实际应用；开发有效的算法来估计经验降解器的复杂性；并通过应用Rademacher理论探索新的严格数据分析算法。该奖项反映了NSF的法定任务，并且使用基金会的知识分子优点和更广泛的影响标准，被认为值得通过评估来获得支持。

项目成果

期刊论文数量（17）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

RePBubLik: Reducing Polarized Bubble Radius with Link Insertions

DOI：
10.1145/3437963.3441825
发表时间：
2021-01
期刊：
Proceedings of the 14th ACM International Conference on Web Search and Data Mining
影响因子：
0
作者：
Shahrzad Haddadan;Cristina Menghini;Matteo Riondato;E. Upfal
通讯作者：
Shahrzad Haddadan;Cristina Menghini;Matteo Riondato;E. Upfal

Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds