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.
