Practical Submodular Optimisation Beyond the Standard Greedy Algorithm

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

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.