AitF: FULL: From Worst-Case to Realistic-Case Analysis for Large Scale Machine Learning Algorithms

点击翻译按钮获取中文摘要

The aim of this project is to develop mathematical models, analysis, and algorithms that will advance both the design and understanding of large-scale machine learning systems. In recent years, machine learning has come into widespread use across a range of applications, and we have also seen significant advances in the theoretical understanding of learning processes. Yet despite these successes, there remains a gulf between theory and application. For example, applications often demonstrate success on problems that theory tells us are intractable in the worst case. Furthermore, as modern machine learning applications scale up from learning of single tasks to learning many tasks simultaneously, new theory is needed to analyze these larger scale multi-task learning settings. This project aims to bridge this gap by developing and applying theory targeted toward realistic-case analysis of learning problems, which capture the structures that enable applications to succeed even when theoretical analyses show the impossibility of doing so in the worst case. This work will be guided by problems at the core of NELL and InMind, two current learning systems that address large-scale multi-task machine learning problems, for reading the web and providing highly personalized electronic assistants to hundreds of interconnected mobile phone users.More specifically, this project has three main components:(1) To develop computationally efficient algorithms for clustering, constrained optimization, and related optimization tasks crucial to large-scale machine learning, with provable guarantees under natural, realistic non-worst-case analysis models.(2) To develop foundations and practical algorithms for multi-task and life-long learning that exploit explicit and implicit structure to minimize key resources including computation time and human labeling effort, as well as address key constraints such as privacy.(3) To apply the algorithms developed to solve key challenges in two current large-scale learning systems, NELL and InMind.The proposed work will aid the development of large-scale machine learning applications, as well as create important connections between multiple areas of significant importance in modern machine learning and theoretical computer science. In addition to advising students on topics connected to this project, research progress (on multi-task learning, life-long learning, and clustering) will be integrated in the curricula of several courses at CMU and course materials will be made available on the world wide web. Course projects based on this research will be available to students in the introductory machine learning course at CMU, which enrolls over 600 students each year. In addition, students seeking topics for undergraduate thesis or independent study may also pursue research affiliated with this project.