AF:Small: Continuous Perspectives on Accelerated Methods for Combinatorial Optimization

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

Efficient algorithms are at the heart of any modern computing systems. In the classical study of algorithms, the notion of efficiency has long been taken to equal polynomial running time in the size of the input. However, the recent rise of massive datasets, for which even quadratic running times may be practically infeasible, has led to a rethinking of this assumption. This effort has led to a number of breakthroughs on fundamental problems, such as computing the maximum flow through a network, which can now be solved in essentially linear time in many cases. These advances are largely based on novel algorithmic tools stemming from convex and numerical optimization, which heavily rely on continuous mathematics. Based on this paradigm, the PIs aim to provide improved algorithms for two classes of problems that are important both in theory and practice: maximum flow problems and submodular optimization problems. These problems are central to computer science and have wide applicability to many real-life problems. The project will support and train two Ph.D. students and a postdoc in algorithm design and optimization at Boston University. The proposed research requires a useful exchange of ideas between theoretical computer science and continuous optimization, strengthening existing ties as well as forging new connections between the two areas. The continuous viewpoint provides a new perspective on algorithm design that the PIs plan to disseminate broadly and to incorporate into their optimization courses at Boston University.In this project, the PIs will delve deeply into the connection between efficient discrete optimization and continuous mathematics by considering the following continuous approach to algorithm design: algorithms are initially conceived as continuous trajectories through the space of solutions to the problems, e.g., as described by a set of differential equations; these trajectories are discretized to yield true discrete-time algorithms that are provably fast. We plan to exploit the new understanding of algorithms obtained through this framework to provide improved algorithms for two classes of problems that are important both in theory and practice: maximum flow problems and submodular optimization problems. The main technical focus of the project will be understanding and leveraging the idea of "acceleration", which plays a central role in convex optimization, as it yields optimal gradient-descent algorithms for a large class of functions. A very recent line of work initiated the study of accelerated methods from a continuous-time perspective using ordinary differential equations (ODEs) and classical discretization tools. More precisely, these works aim to represent a class of accelerated methods via ODEs whose dynamics describe the continuous-time limits of the discrete algorithms, while the discrete algorithms can be interpreted as appropriate discretizations of the continuous-time curves described by the ODEs.The project will build on this recently established viewpoint to make progress on central combinatorial optimization problems involving graphs and submodular functions. In particular, the project aims to exploit the rich combinatorial structure present in these problems to construct improved discretization procedures for known dynamical systems corresponding to accelerated algorithms. Specific problems of interest include: (a) Maximum s-t flows and connectivity problems in graphs and networks - The emphasis will be on leveraging convex optimization techniques such as acceleration in order to obtain faster approximate solutions for these problems in undirected and directed graphs. (b) Constrained submodular maximization problems - A particular area of focus will be on designing new continuous algorithms and discretization for solving known continuous relaxations of submodular objectives under structured constraints, such as packing and covering constraints.