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

机器学习和数据挖掘是过去十年来计算机科学最有影响力的贡献之一。考虑到足够大的数据集和计算能力，人们可以发现模式并做出相当准确的预测。虽然在设计用于分析海量数据集的有效算法方面取得了巨大的进展，但在提供分析的统计意义或稳健性的严格度量方面进展较少。当我们分析大型且有噪声的数据集以建模数据中的复杂关系时，开发具有明确性能保证的正式验证的方法是至关重要的。这个项目倡导一种负责任的数据分析方法，基于有充分依据的数学和统计概念。这种方法提高了大数据分析在医学、政策和其他社会应用中基于证据的决策的有效性和可靠性。这个项目的能力建设活动包括：(1)创建和传播算法和软件，对大数据分析实施严格、可解释和可用的计算和统计方法；(2)研究生和本科生层面的教育倡议，建立一支更大、更多样化的数据科学家队伍，他们具有适当的基础技能，将分析工具应用于现有数据集，并开发未来数据集的新方法。该项目的目标是开发基于Rademacher复杂性理论机器学习概念的实用数据分析算法应用程序。这个项目的动机是初步结果，这些结果表明，Rademacher复杂性的分析特性与其有效的抽样特性相结合，为开发通用工具开始弥合大规模数据分析的理论和实践之间的差距提供了独特的机会。特别是，该项目专注于以下目标：通过更好的样本复杂性界限提高严格数据分析算法的效率；通过Rademacher泛化界限改善多重比较和过拟合控制；开发笛卡尔和混沌Rademacher复杂性的理论和实际应用；开发用于估计经验Rademacher复杂性的高效算法；以及通过Rademacher理论的应用探索新的严格数据分析算法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.