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

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

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.