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复杂性的理论和实际应用;开发用于估计经验Rademacher复杂性的有效算法;该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

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
• 作者: Shahrzad Haddadan;Cristina Menghini;Matteo Riondato;E. Upfal

Learning Simulation-Based Games from Data

• 发表时间: 2019-05
• 作者: Enrique Areyan Viqueira;A. Greenwald;Cyrus Cousins;E. Upfal

Tiered Sampling: An Efficient Method for Counting Sparse Motifs in Massive Graph Streams

分层采样：一种计算海量图流中稀疏图案的有效方法

• DOI: 10.1145/3441299
• 发表时间: 2021
• 期刊: ACM Transactions on Knowledge Discovery from Data
• 影响因子: 3.6
• 作者: Stefani, Lorenzo De;Terolli, Erisa;Upfal, Eli
• 通讯作者: Upfal, Eli

Democratizing Data Science through Interactive Curation of ML Pipelines

• DOI: 10.1145/3299869.3319863
• 发表时间: 2019-06
• 期刊: Proceedings of the 2019 International Conference on Management of Data
• 作者: Zeyuan Shang;Emanuel Zgraggen;Benedetto Buratti;Ferdinand Kossmann;P. Eichmann;Yeounoh Chung;Carsten Binnig;E. Upfal;Tim Kraska

Uncertainty and the Social Planner’s Problem: Why Sample Complexity Matters

不确定性和社会规划者的问题：为什么样本复杂性很重要

• DOI: 10.1145/3531146.3533243
• 发表时间: 2022
• 期刊: and Transparency
• 作者: Cousins, Cyrus