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

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