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

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