Practical Submodular Optimisation Beyond the Standard Greedy Algorithm

超越标准贪婪算法的实用子模优化

• 批准号: EP/T006781/1
• 负责人: Justin Ward
• 金额: $ 15.5万
• 依托单位: Queen Mary University of London
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2019
• 资助国家: 英国
• 起止时间: 2019 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FT006781%2F1
• 关键词: Practical; Submodular; Optimisation; Beyond; Standard

Algorithms for submodular optimisation have been successfully applied to a variety of difficult problems at the heart of data science, machine learning, and operational research. Behind these successes is a rich mathematical theory that precisely specifies the conditions under which simple heuristics will always produce nearly optimal solutions to problems. This proposal will enlarge this theory to allow existing approaches to be brought to bear on new classes of problems, and, where necessary, develop new algorithms for problems that lie beyond their reach.Intuitively, submodular optimisation concerns the problem of finding the best set of items from some large collection in the presence of "diminishing returns." For example, suppose a company wants to select where to place 100 advertisements with the aim of maximising future sales. The marginal benefit of any given ad placement in the campaign will probably be larger if only 10 ads have already been placed than if 99 have been placed! Due to this diminishing returns property, one can prove that this problem is difficult to solve optimally. However, this same property can also be used to show that a simple "greedy" algorithm is mathematically guaranteed to produce solutions that are nearly optimal.Unfortunately, even seemingly minor variations in the formulation of an optimisation problem can have drastic affects on these guarantees. For example, our company might decide that instead of having a fixed budget for its marketing campaign, it could simply account for the cost of each advertisement explicitly and then try to maximise the total expected revenue minus the advertisement cost. This relatively small change in formulation is enough to make existing guarantees break down completely, since now the value (i.e. profit) of a set of items (i.e. advertisements) may become negative.The goal of this project is to obtain new, practical optimisation algorithms with rigorous, mathematical quality guarantees for new classes of problems such as the example given above that cannot be handled efficiently using existing notions of submodularity. Specifically, we aim to develop techniques for dealing with some classes of problems in which our notion of value is possibly negative, decreasing, or non-submodular, and also to develop scalable algorithms for treating problems that cannot be handled with greedy approaches. For problems where existing optimisation algorithms work well in practice but do not have guarantees, we aim to identify the underlying structures and problem characteristics that explain why. For problems where this is not the case, we seek to develop new algorithmic techniques that address legitimate shortcomings of standard approaches. Our goal is thus to expand the interface between theory and practice. From a theoretical perspective, we aim to develop a more precise understanding of those properties make problems easy or hard to solve approximately. From a practical perspective, we aim to develop insight and tools that can be use to model problems, design and select algorithms, and interpret the results of these algorithms with confidence.

子模块优化算法已经成功地应用于数据科学、机器学习和运筹学的核心问题。在这些成功的背后是一个丰富的数学理论，它精确地规定了在什么条件下，简单的启发式方法总是能产生问题的近乎最优的解决方案。这一建议将扩展这一理论，使现有的方法能够应用于新的问题类别，并在必要时为超出其范围的问题开发新的算法。实际上，子模块优化涉及的是在存在“收益递减”的情况下从某个大型集合中寻找最佳项目集的问题。例如，假设一家公司想要选择在哪里投放100个广告，目的是最大化未来的销售。如果只有10个广告已经被放置，那么在活动中任何给定广告放置的边际收益可能会比99个广告被放置的边际收益更大！由于收益递减的性质，可以证明这个问题很难得到最优解决。然而，同样的性质也可以用来证明一个简单的“贪婪”算法在数学上可以保证产生近乎最优的解。不幸的是，即使在优化问题的公式中看起来很小的变化也会对这些保证产生巨大的影响。例如，我们的公司可能会决定，它可以只对每个广告的成本进行明确的核算，然后尝试最大化总预期收入减去广告成本，而不是为其营销活动制定固定的预算。这种相对较小的公式变化足以使现有的保证完全崩溃，因为现在一组项目(即广告)的价值(即利润)可能变为负值。该项目的目标是获得新的、实用的优化算法，对新的问题类别具有严格的数学质量保证，例如上面给出的例子，这些问题不能使用子模块的现有概念有效地处理。具体地说，我们的目标是开发技术来处理某些类型的问题，在这些问题中，我们的价值概念可能是负的、递减的或非子模块的，并且我们还旨在开发可扩展的算法来处理不能用贪婪的方法处理的问题。对于现有优化算法在实践中工作良好但不能得到保证的问题，我们的目标是确定解释原因的潜在结构和问题特征。对于不是这样的问题，我们寻求开发新的算法技术，以解决标准方法的合法缺陷。因此，我们的目标是扩大理论和实践之间的接口。从理论的角度来看，我们的目标是更准确地理解那些使问题容易或难以近似解决的性质。从实践的角度来看，我们的目标是开发可用于建模问题、设计和选择算法并自信地解释这些算法的结果的洞察力和工具。

项目成果

Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression

• 发表时间: 2021-02
• 作者: Theophile Thiery;Justin Ward

FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective

具有覆盖目标的 (ell) -Matchoid 问题的 FPT 算法

• DOI: 10.1137/21m1442267
• 发表时间: 2023
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Huang C

Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

2023 年年度 ACM-SIAM 离散算法研讨会 (SODA) 论文集

• DOI: 10.1137/1.9781611977554.ch42
• 发表时间: 2023
• 作者: Thiery T

Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints

改进的多通道流算法，用于具有拟阵约束的子模最大化

• 发表时间: 2020
• 作者: Huang C.-C.