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.

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