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.