Alexander Rakhlin - US grants

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.

Learning theory studies the extent to which meaningful patterns can be extracted from data. Two popular frameworks for the analysis of learning algorithms are statistical learning and worst-case online learning. Recent developments suggest that these two seemingly disparate frameworks are, in fact, two endpoints of a spectrum of problems which can be studied in a unified manner. The goals of this project are (a) to understand learnability and to develop efficient algorithms for a spectrum of problems corresponding to various probabilistic and non-probabilistic assumptions on the data; (b) to extend learnability results to encompass performance criteria beyond the classical notion of regret; (c) to understand the inherent complexity of reinforcement learning and to develop novel algorithms inspired by the learnability analysis; (d) to study learnability in settings with imperfect or partial information, and to understand algorithmic implications of dealing with uncertainty.

Algorithms that extract patterns from data are becoming increasingly important in the information age. However, classical methods that assume a "static" nature of the world are unable to capture the evolving character of data. Recent advances in learning theory have been on the dynamic interaction between the world and the learner. Being able to tailor the algorithms to particular assumptions on data is arguably a central goal of learning theory. The intellectual merit of this proposal includes the development of a unified theoretical framework, increasing our understanding of what is learnable by computers. Advances in this direction will likely facilitate the development of more intelligent systems, having a positive impact on technology. The interdisciplinary nature of the project will likely increase collaboration between Computer Science and Statistics.

The research program ``Mathematics of Machine Learning'', hosted by the Centre de Recerca Matematica (Barcelona, Spain), will take place from April 7th to July 14th, 2014. The aim of the program is to bring together leading researchers from the fields of Statistics, Optimization, and Computer Science. The dialogue between these fields has been crucial to the understanding of modern machine learning problems. The research program will focus on several aspects of theoretical machine learning, including the interplay of computation and statistics, connections between learning and optimization, as well as the theory of sequential prediction methods. Over the course of fourteen weeks, the investigators will organize three thematic 3-day workshops, one large 5-day workshop on learning theory, as well as many short and long-term visits. The program will also be co-located with the conference Journees de Statistique and the Conference on Learning Theory.

Machine learning approaches to dealing with large scale data ultimately rely on our understanding of computational and statistical demands. By attracting the leading experts in the respective fields, the program organizers are aiming to focus on the theoretical issues of modern machine learning problems. As machine learning methods form an essential part of many computerized systems, the research is likely to have a positive impact on technology and society through the development of faster algorithms with better performance. The program naturally integrates research and education. The short and long-term visitors will be given a unique opportunity to conduct cutting-edge research, while the thematic workshops during this period will provide a forum for learning and the exchange of ideas with the broader audience. In particular, student participation will be crucial to fostering the next generation of researchers that study both computational and statistical aspects of learning. Conference web page is located at http://stat.wharton.upenn.edu/~rakhlin/crm/

Terabytes of data are collected by companies and individuals every day. These data possess no value unless one can efficiently process them and use them to make decisions. The scale and the streaming nature of data pose both computational and statistical challenges. The objective of this research project is to develop novel approaches to making online, real-time decisions when data are constantly evolving and highly structured. In particular, this project focuses on online prediction problems involving multiple users in dynamic networks. The project also aims to tackle the privacy issues arising in such multi-user scenarios.

In recent years, it was shown that a majority of online machine learning algorithms can be viewed as solutions to approximate dynamic programming (ADP) problems that incorporate one additional datum per step. Along with directly addressing the computational concerns, the ADP framework also provides guaranteed performance on prediction problems. This project is to use and extend the ADP framework to develop prediction algorithms that simultaneously address the issues of computation, robustness, non-stationarity, privacy, and multiplicity of users.

The success of deep learning has had a major impact across industry, commerce, science and society. But there are many aspects of this technology that are very different from classical methodology and that are poorly understood. Gaining a theoretical understanding will be crucial for overcoming its drawbacks. The Collaboration on the Theoretical Foundations of Deep Learning aims to address these challenges: understanding the mathematical mechanisms that underpin the practical success of deep learning, using this understanding to elucidate the limitations of current methods and extending them beyond the domains where they are currently applicable, and initiating the study of the array of mathematical problems that emerge. The team has planned a range of mechanisms to facilitate collaboration, including teleconference and in-person research meetings, a centrally organized postdoc program, and a program for visits between institutions by postdocs and graduate students. Research outcomes from the collaboration have strong potential to directly impact the many application domains for deep learning. The project will also have broad impacts through its education, human resource development and broadening participation programs, in particular through training a diverse cohort of graduate students and postdocs using an approach that emphasizes strong mentorship, flexibility, and breadth of collaboration opportunities; through an annual summer school that will deliver curriculum in the theoretical foundations of deep learning to a diverse group of graduate students, postdocs, and junior faculty; and through targeting broader participation in the collaboration?s research workshops and summer schools.

The collaboration?s research agenda is built on the following hypotheses: that overparametrization allows efficient optimization; that interpolation with implicit regularization enables generalization; and that depth confers representational richness through compositionality. The team aims to formulate and rigorously study these hypotheses as general mathematical phenomena, with the objective of understanding deep learning, extending its applicability, and developing new methods. Beyond enabling the development of improved deep learning methods based on principled design techniques, understanding the mathematical mechanisms that underlie the success of deep learning will also have repercussions on statistics and mathematics, including a new point of view of classical statistical methods, such as reproducing kernel Hilbert spaces and decision forests, and new research directions in nonlinear matrix theory and in understanding random landscapes. In addition, the research workshops that the collaboration will organize will be open to the public and will serve the broader research community in addressing these key challenges.

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.