Optimisation for Game Theory and Machine Learning

博弈论和机器学习的优化

• 批准号: EP/X040461/1
• 负责人: Paul Wilfred Goldberg
• 金额: $ 79.55万
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FX040461%2F1
• 关键词: Optimisation; Game; Theory; Machine; Learning

The project lies in the general area of mathematical analysis of algorithms, and computational complexity. Thus it focuses on provable performance guarantees of algorithms, and the fundamental limits to solvability of certain computational problems. This line of work is important in developing our understanding of why and how the associated problems are solved.The problems of interest to this project consist of various related problems in optimisation (both continuous and discrete), some of which arise in Algorithmic Game Theory, and some arising in machine learning and neural networks. For example, the process of training a neural network involves searching for values of the weights of the neural network that minimise its disagreement with a data set. This usually uses some version of gradient descent, and is thus treated as a problem of continuous local optimisation. A widespread observation is that the efficacy of such learning systems is poorly understood: both the predictive power of the system, and the ability (in practice) of the local optimsation of find a solution reasonably quickly, deserve to be better understood. Multiple solutions may exist, and we address questions about the trade-off between quality of solution, and how hard it is to find. "Generative Adversarial Networks" have attracted widespread interest recently; these neural networks model the problem of learning a probability distribution, as a zero-sum game. This in turn leads to new "minimax" optimisation problems, and questions about how efficiently they can be solved.The resulting optimisation problems are diverse, and include problems of discrete optimisation (in the case of clustering) and multi-objective optimisation is the case of generative adversarial networks, for example. But their complexity-theoretic analysis is a unifying theme, using tools from the study of search problems for which efficiently-checkable solutions are guaranteed to exist. The project aims to advance the theory of hard problems in this domain, which in turn assists with the explanation of efficaceous algorithms, via an understanding of what features of problems in practice they exploit. We are also interested in designing novel algorithms, or novel refinements of existing algorithms, having better performance guarantees than pre-existing ones. For example, this might build on "optimistic gradient descent" which has been shown to have desirable properties in some scenarios of multi-objective optimisation.

该项目在于算法数学分析和计算复杂性的一般领域。因此，它着重于算法的可证明的性能保证，以及对某些计算问题的解决性的基本限制。这项工作对于发展我们为什么解决相关问题的理解至关重要。该项目感兴趣的问题包括优化中的各种相关问题（连续和离散），其中一些在算法游戏理论中引起，以及机器学习和神经网络中出现的一些问题。例如，训练神经网络的过程涉及搜索神经网络权重的值，以最大程度地减少其与数据集的分歧。这通常使用某种版本的梯度下降，因此被视为连续局部优化的问题。一个广泛的观察是，这种学习系统的功效知之甚少：系统的预测能力，以及（实践中）的能力（实际上）合理地找到解决方案的局部优化能力，应该得到更好的理解。可能存在多种解决方案，我们解决了有关解决方案质量之间的权衡以及找到的难度。最近，“生成对抗网络”引起了广泛的兴趣。这些神经网络将学习概率分布的问题建模为零和游戏。这反过来又导致了新的“最小值”优化问题，以及有关如何有效解决它们的问题。产生的优化问题是多种多样的，包括离散优化的问题（在聚类的情况下）和多目标优化是生成对抗网络的一种情况。但是，他们的复杂性理论分析是一个统一的主题，它使用了研究搜索问题的工具，可以保证存在有效检查的解决方案。该项目的目的是通过了解他们利用的实践中的问题特征，进而推动该领域中的严重问题理论的解释。我们也有兴趣设计新颖的算法或现有算法的新颖改进，比预先存在的算法具有更好的性能保证。例如，这可能基于“乐观的梯度下降”，在多目标优化的某些方案中已证明具有理想的属性。