CAREER: Machine Learning Theory with Connections to Algorithmic Game Theory and Combinatorial Optimization

多年来，机器学习已经成为一门非常广泛的学科，在许多领域都有重要的应用，包括计算机视觉、语音识别、机器人和生物监测，仅举几例。此外，许多这些应用领域都面临着各种可用数据量的巨大增长。为了能够使用所有这些数据，已经提出了许多新的学习方法。这些方法已经在机器学习社区进行了深入的探索，有许多启发式和特定的算法，以及实验结果。然而，不幸的是，标准的理论模型并没有捕捉到这些学习技术中涉及的关键问题，而且很明显，为了在这些设置中开发健壮、通用和通用的算法，更基本的理解是必要的。本项目将为这些具有重要实践意义但现有理论模型无法解释的学习范式提供理论基础。该项目还将在机器学习、博弈论和组合优化之间建立新的联系，这将有助于推进和解决这三个领域的重要问题。本项目重点研究方向为：1、研究方向：为标准模型不能很好地捕获的重要机器学习范式开发数学基础和算法。这包括新的分析框架以及用于半监督学习和主动学习的新的实践和理论上合理的算法，这两种重要的新兴方法用于在学习过程中整合未标记数据和交互。该项目还将探索一种全新的分析聚类的方法——这是分析和探索数据的经典中心任务，现有的理论已经非常脆弱。这个框架将使从业者能够以一种正式的方式描述他们认为是真实的数据属性，然后使用这些属性来选择或设计适合他们需要的正确算法。在机器学习和算法博弈论之间建立新的基本联系，以解决先前方法无法解决的多智能体系统中的难题。特别是，许多多智能体相互作用具有坏均衡，开发方法帮助处于这种坏状态的智能体转向更好的平衡是很重要的。该项目将开发理解和影响这类游戏中自然动态行为的技术，通过使用与机器学习中重要概念的联系，例如从不可信的专家的建议中学习。发展机器学习和组合优化之间的基本联系，以推进这两个领域。其中包括近似算法和基于学习的聚类目标之间的新联系，以及学习子模块函数的新算法和计算理论。描述收益递减规律的子模块函数在经济优化问题中无处不在，从观察数据中学习它们的方法可以帮助设计改进的决策过程。总之，该项目将通过开发和利用这些领域之间的新联系，推进机器学习、算法博弈论和组合优化。这项工作开发的理论将为机器学习和多智能体系统提供下一代强大的算法。它还将影响计算机视觉、机器人、生物监测和在线拍卖设计等广泛的应用领域。更广泛地说，该项目的研究成果将对许多科学、医学和工业领域产生影响。PI的教育计划进一步促进了项目的影响。除了就与本项目直接相关的项目向不同的学生提供建议外，本研究的进展将通过介绍理论进展及其应用的特殊课程来影响课程设置。该倡议还将有助于增加妇女对计算科学的参与。

Over the years, Machine Learning has become a very broad discipline with important applications to many areas including computer vision, speech recognition, robotics, and bio-surveillance, to name just a few. Moreover, many of these application areas have faced a huge increase in the volume of available data of various kinds. In order to be able to use all this data a number of new learning approaches have been proposed. These approaches have been intensely explored in the machine learning community, with many heuristics and specific algorithms, as well as experimental results reported. Unfortunately, however, the standard theoretical models do not capture the key issues involved in these learning techniques, and it has become clear that for developing robust, versatile, and general algorithms in these settings a more fundamental understanding is necessary. This project will develop theoretical foundations for such learning paradigms which are of significant practical importance but are not explained by existing theoretical models. This project will also develop fundamental new connections between Machine Learning, Game Theory, and Combinatorial Optimization, that will aid in advancing and solving important problems in all three areas.The key research directions of this project are:1. Developing mathematical foundations and algorithms for important machine learning paradigms that are not captured well by standard models. This includes new analysis frameworks as well as new practical and theoretically justified algorithms both for semi-supervised learning and active learning, two important emerging approaches for incorporating unlabeled data and interaction in the learning process. This project will also explore a fundamentally new approach to analyzing clustering -- a classic central task in the analysis and exploration of data, for which the existing theory has been very brittle. This framework will enable practitioners to describe in a formal way the properties they believe to be true about their data, and then use these properties to choose or design the right algorithm for their needs.2. Developing novel fundamental connections between Machine Learning and Algorithmic Game Theory in order to solve difficult problems in multi-agent systems that have resisted previous approaches. In particular, many multi-agent interactions have bad equilibria, and it is important to develop methods for helping agents in such bad states to move to better ones. This project will develop techniques for understanding and influencing the behavior of natural dynamics in games of this type, by using connections to important concepts in Machine Learning, such as learning from untrusted experts' advice.3. Developing fundamental connections between Machine Learning and Combinatorial Optimization in order to advance both areas. These include new connections between approximation algorithms and learning-based objectives for clustering, and new algorithms and computational theory for learning submodular functions. Submodular functions, which describe laws of diminishing returns, are ubiquitous in economic optimization problems, and methods for learning them from observed data can aid in designing improved decision procedures.Altogether, this project will advance Machine Learning, Algorithmic Game Theory, and Combinatorial Optimization, by developing and exploiting novel connections between these areas. The theory developed by this work will enable the next generation of powerful algorithms for machine learning and multi-agent systems. It will additionally impact a wide range of application areas including computer vision, robotics, bio-surveillance, and online auction design. More broadly, the research results of this project will have impact across a number of scientific, medical, and industrial fields. The PI's education plan further contributes to the project's impact. In addition to advising a diverse set of students on projects directly related to this project, the progress in this research will be used to influence the curriculum via special courses presenting the theoretical advances along with their applications. The PI will also contribute to increasing the participation of women in computational sciences.