CAREER: Statistical and Computational Complexities of Modern Learning Problems

本提案的研究目标是发展一种与数据学习的统计和计算复杂性相关的数学理论。通过对这些复杂性的综合研究，PI旨在填补对统计与计算之间基本联系的理解的空白。本提案中考虑的问题与以下重叠方向一致：(1)正则化对统计和计算保证的影响；(2)估计和优化的信息论局限性；(3)统计性能与计算时间之间的权衡，以及预算约束的影响；(4)序列预测方法作为优化和统计学习之间的纽带；(5)有限反馈模型及其在序列预测和优化中的价值。从理论和实践的角度来看，沿着这些方向发展具有重要意义。统计学习理论在设计和分析从数据中提取模式并做出智能决策的算法方面取得了成功。学习方法的应用无处不在：它们包括人脸检测和人脸识别系统、股票市场和天气模式预测系统、学习医疗策略系统、语音识别系统、学习用户搜索偏好系统、投放相关广告系统等等。随着统计学习方法成为许多计算机化系统的重要组成部分，新的挑战出现了。这些挑战包括大量数据、高维度、有限的反馈以及恶意行为的可能性。所有这些挑战对(a)统计性能和(b)执行手头任务所需的计算时间都有深远的影响。同时研究这两个方面的工作很少，本项目的目标就是填补这一空白。更好地理解统计和计算之间的相互作用可能会导致更快、更精确的方法，从而对技术和社会产生积极影响。该项目更广泛的影响包括通过开发新课程、研讨会、讲习班和暑期学校项目整合跨学科研究和教育的组成部分。

The research objective of this proposal is to develop a mathematical theory relating statistical and computational complexities of learning from data. Through an integrated study of these complexities, the PI aims to fill the gap in the understanding of fundamental connections between Statistics and Computation. The problems considered in this proposal are aligned with the following overlapping directions: (1) effects of regularization on statistical and computational guarantees; (2) information-theoretic limitations of estimation and optimization; (3) trade-offs between statistical performance and computation time, as well as the effect of budget constraints; (4) sequential prediction methods as a link between optimization and statistical learning; and (5) limited-feedback models and the value of feedback in sequential prediction and optimization. Progress along these directions is of great significance from both theoretical and practical points of view. Statistical Learning Theory has been successful in designing and analyzing algorithms that extract patterns from data and make intelligent decisions. Applications of learning methods are ubiquitous: they include systems for face detection and face recognition, prediction of stock markets and weather patterns, learning medical treatment strategies, speech recognition, learning user's search preferences, placement of relevant ads, and much more. As statistical learning methods become an essential part of many computerized systems, new challenges appear. These challenges include large amounts of data, high dimensionality, limited feedback, and a possibility of malicious behavior. All these challenges have a profound impact on (a) the statistical performance and (b) the computation time required to perform the task at hand. Little work exists on studying these two aspects simultaneously, and the goal of this project is to fill this gap. Better understanding of the interaction between Statistics and Computation is likely to lead to faster and more precise methods, thus positively impacting technology and society. The project's broader impact includes components for integration of interdisciplinary research and education through the development of new courses, seminars, workshops, and a summer school program.