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.

More than ever before, our daily lives are being shaped by algorithms. These algorithms, fed by an unprecedented amount of data, promise to enable more efficient infrastructure, communications, and decision-making. To deliver on this promise, we need a way to identify which algorithmic approaches are likely to be most successful for new applications. At the same time, we need to be able to trust that the optimisation algorithms we employ are producing answers that are indeed close to the best possible.

This project aims to develop improved algorithms that are applicable to wide classes of optimisation problems, together with a mathematical theory providing strong guarantees. The guarantees we seek will ensure that, even in the worst possible cases, these algorithms produce solutions that are reasonably close to optimal. Algorithms for submodular optimisation are already being successfully used for several applications in machine learning, data science, and operational research, either alone or as a key component of other complex systems. However, for many natural variants of these optimisation problems, our mathematical theory currently lags behind practical experience. Here, we propose closing this gap, either by improving guarantees for existing algorithms, or identifying situations in which known algorithms do break down and developing techniques to cope with this.

The optimisation problems that form the basis of the current proposal are key components for several large-scale machine learning technologies, which have the potential to enable new data-driven sectors of the economy, and to develop intelligent systems for infrastructure, healthcare, and finance. By improving and enlarging the scope of these tools, the proposed research will directly impact and accelerate national development in these areas, but also have potential to enhance our understanding of existing and emerging technologies.