AF: Small: Foundations for Learning in the Age of Big Data---New Frameworks and Algorithms for Interactive, Distributed, and Multi-Task Machine Learning

机器学习是一门广泛的学科，具有重要的应用领域，包括计算机视觉、机器人、可持续性和生物监测。它过去的成功演变在很大程度上受到了为从标记数据泛化的核心问题而开发的数学基础的影响。然而，在大数据时代，随着机器学习在科学、工程和计算领域的各种应用，重新审视该领域的潜在基础已经变得势在必行。该项目旨在通过为一些重要的现代学习范式开发基础和算法，实质性地推进机器学习领域。其中包括交互式学习，与被动观察标记数据的经典方法相比，算法和领域专家进行双向对话，以促进从更少的数据中更准确地学习；分布式学习，其中大型数据集分布在多个服务器上，挑战在于在有限的通信下学习；多任务学习，其目标是利用学习任务之间的关系，从较少的数据中解决多个相关的学习问题。该项目还旨在开发机器学习和属性测试之间的新联系，属性测试是理论计算机科学的一个蓬勃发展的领域。除了解决这些方向上的基本问题外，该项目还将突出并利用这些主题之间的协同作用。更具体地说，本项目的重点研究方向是：(1)通过分析学习算法与领域专家之间新的交互形式，建立交互式学习的数学基础，通过明智地利用领域专家的能力，实现对困难任务的快速有效学习。(2)开发分布式学习的新算法，分布式学习是数据分布在多个位置的重要现代场景。该项目将开发协议，以权衡这些设置（计算、通信和领域专业知识）中涉及的各种类型的资源。(3)通过明智地利用给定任务之间明确已知或潜在的关系，开发具有可证明保证的新算法，以从有限数量的标记数据和大量未标记数据中学习多个相关任务。(4)发展属性测试的数学基础，其问题是通过使用比实际找到规则本身所需的数据少得多的数据，快速确定是否存在期望形式的低误差规则。该项目将特别关注活动和分布式场景，目标是使用测试作为提高学习效率本身的一种方式。更广泛的影响包括在计算机科学领域指导妇女，并积极组织跨学科领域的讲习班和研讨会。

Machine learning is a broad discipline with important application domains including computer vision, robotics, sustainability, and bio-surveillance. Its past successful evolution was heavily influenced by mathematical foundations developed for core problems of generalizing from labeled data. However, with the variety of applications of machine learning across science, engineering, and computing in the age of Big Data, re-examining the underlying foundations of the field has become imperative. This project aims to substantially advance the field of machine learning by developing foundations and algorithms for a number of important modern learning paradigms. These include interactive learning, where the algorithm and the domain expert engage in a two-way dialogue to facilitate more accurate learning from less data compared to the classic approach of passively observing labeled data; distributed learning, where a large dataset is distributed across multiple servers and the challenge lies in learning with limited communication; and multi-task learning, where the goal is to solve multiple related learning problems from less data by taking advantage of relationship among the learning tasks. The project also aims to develop new connections between machine learning and property testing, a flourishing area of theoretical computer science. In addition to solving fundamental questions in each of these directions, the project will highlight and leverage synergies between these topics.More specifically, the key research directions of this project are: (1) Developing mathematical foundations for interactive learning by analyzing new forms of interactions between the learning algorithm and the domain expert that could lead to fast and efficient learning of difficult tasks by wisely exploiting the capabilities of domain experts. (2) Developing new algorithms for distributed learning, an important modern scenario where data is distributed among several locations. This project will develop protocols that trade off the various types of resources involved in such settings (computation, communication, and domain expertise). (3) Developing new algorithms with provable guarantees for learning multiple related tasks from limited amounts of labeled data and massive amounts of unlabeled data by wisely exploiting explicitly known or latent relationships between the given tasks. (4) Developing mathematical foundations for property testing, where the question is to quickly determine whether there exists a low-error rule of a desired form by using significantly less data than needed to actually find the rule itself. This project will specifically focus on active and distributed scenarios, with the goal of using testing as a way to improve learning efficiency itself.Broader impacts include mentoring women in CS and actively organizing workshops and seminars in the interdisciplinary area.