Practical Submodular Optimisation Beyond the Standard Greedy Algorithm

点击翻译按钮获取中文摘要

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.