A Learning Theory Approach to Algorithmic Game Theory, Database Privacy, and Clustering

机器学习理论关注的是设计具有可证明的保证的算法，以从数据中学习，并了解哪些类型的保证是固有的。 事实证明，这与数学博弈论、数据库隐私和聚类中的关键问题有许多重要的联系。 该项目旨在进一步发展和扩展这些联系，以解决所有三个领域的基本问题。无政府博弈论的一个主要目标是通过“无政府状态的价格”的概念来量化无效率的自利行为。 然而，假设用户根据纳什均衡进行行为可能过于乐观，特别是在大型或信息有限的设置中（即使对于集中式控制器，这些均衡也很难在计算上找到）。 相反，通过在线学习算法实现的简单保证可以直接对自利行为的最小概念进行建模，即使在大型、信息贫乏的领域也有意义。 这项工作将开发一种替代方法来分析系统的自利实体的基础上，这个想法。在数据库隐私的领域，很明显，保护隐私的数据库中所涉及的，同时仍然提供有用的统计数据是一项具有挑战性的任务。 不幸的是，虽然已经取得了积极的成果，交互式问答机制，大多数结果，实际上释放一个数据库满足严格的条件，称为差分隐私一直是负面的。 然而，学习理论提出了一种可能的方法：与其试图保留所有可能的统计数据，不如定义有趣的统计数据类（很像PAC学习中的概念类），并问：什么时候可以近似保留该类中的所有统计数据，同时仍然满足隐私？ 我们已经能够产生计算效率低的机制，适用于广泛的收集这样的类，这项工作的一个主要目标是开发计算上听话proceeding.Finally，虽然许多不同的算法已经开发的数据聚类，什么样的数据信息是足够的，能够准确地聚类的理论仍然没有得到很好的理解。 理论模型要么做出强有力的统计假设（如高斯混合），要么旨在优化可能与错误率不直接相关的基于图的目标。在这项工作中，我们的目标是创建一个类似的PAC学习模型的集群，能够直接解决这个问题。 在最近的工作中，我们在这个方向上取得了初步进展，本项目旨在更充分地发展这种方法。

Machine Learning Theory is concerned with designing algorithms with provable guarantees for learning from data, and understanding what types of guarantees are inherently achievable. This turns out to have a number of important connections to key problems in Algorithmic Game Theory, Database Privacy, and Clustering. This project intends to further develop and expand these connections in order to address fundamental questions in all three areas.A major thrust of Algorithmic Game Theory has been quantifying the inefficiency self-interested behavior via the notion of "Price of Anarchy". However, the assumption made that users behave according to a Nash equilibrium can be overly optimistic, especially in large or information-limited settings (even for a centralized controller these equilibria can be computationally hard to find). Instead, simple guarantees achieved by online learning algorithms can directly model a minimal concept of self-interested behavior, and make sense even in large, information-poor arenas. This work will develop an alternative approach to analyzing systems of self-interested entities based on this idea.In the area of Database Privacy, it is clear that protecting privacy of those involved in a database while still providing useful statistics is a challenging task. Unfortunately, while positive results have been achieved for interactive query-answering mechanisms, most results for actually releasing a database satisfying the stringent condition known as differential privacy have been negative. Learning Theory, however, suggests a possible approach: rather than attempting to preserve all possible statistics, one can instead define interesting classes of statistics (much like concept classes in PAC learning) and ask: when can one approximately preserve all statistics in this class while still satisfying privacy? We have been able to produce computationally inefficient mechanisms that apply to a broad collection of such classes, and one main thrust of this work is to develop computationally tractable procedures.Finally, while many different algorithms have been developed for data clustering, the theory of what information about data is sufficient to be able to cluster it accurately remains not well understood. Theoretical models either make strong statistical assumptions (such as mixtures of Gaussians) or else aim to optimize graph-based objectives that may not be directly related to error rate. In this work we aim to create an analog of the PAC learning model for clustering that is able to directly address this issue. In recent work we have made initial progress in this direction and this project aims to more fully develop this approach.