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

高效的算法是任何现代计算系统的核心。在算法的经典研究中，效率的概念一直被认为等于输入大小的多项式运行时间。然而，最近大规模数据集的兴起，即使是二次运行时间也可能实际上是不可行的，这导致了对这一假设的重新思考。这一努力已经在一些基本问题上取得了突破，比如计算网络的最大流量，现在在许多情况下，这个问题基本上可以在线性时间内解决。这些进步很大程度上是基于源自凸优化和数值优化的新颖算法工具，这些工具严重依赖于连续数学。基于这种范式，pi旨在为两类在理论和实践中都很重要的问题提供改进的算法：最大流量问题和子模块优化问题。这些问题是计算机科学的核心，并广泛适用于许多现实生活中的问题。该项目将支持和培养波士顿大学算法设计与优化方向的两名博士生和一名博士后。拟议的研究需要在理论计算机科学和持续优化之间进行有益的思想交流，加强现有的联系，并在两个领域之间建立新的联系。连续的观点为算法设计提供了一个新的视角，pi计划广泛传播，并将其纳入波士顿大学的优化课程中。在这个项目中，pi将通过考虑以下连续的算法设计方法来深入研究有效的离散优化和连续数学之间的联系：算法最初被认为是通过问题解空间的连续轨迹，例如，由一组微分方程描述；这些轨迹被离散化以产生可证明是快速的真正的离散时间算法。我们计划利用通过该框架获得的对算法的新理解，为两类在理论和实践中都很重要的问题提供改进的算法：最大流量问题和子模块优化问题。该项目的主要技术重点将是理解和利用“加速”的概念，这在凸优化中起着核心作用，因为它为一大类函数产生了最优的梯度下降算法。最近的一项工作是从连续时间的角度出发，利用常微分方程（ode）和经典离散化工具研究加速方法。更准确地说，这些工作旨在通过ode表示一类加速方法，其动力学描述了离散算法的连续时间限制，而离散算法可以解释为ode所描述的连续时间曲线的适当离散化。该项目将建立在这个最近建立的观点上，在涉及图和子模函数的中心组合优化问题上取得进展。特别是，该项目旨在利用这些问题中存在的丰富组合结构来构建与加速算法相对应的已知动力系统的改进离散化程序。感兴趣的具体问题包括：(a)图和网络中的最大s-t流和连通性问题-重点将放在利用凸优化技术，如加速，以便在无向图和有向图中更快地获得这些问题的近似解。(b)约束子模最大化问题-一个特别的重点领域将是设计新的连续算法和离散化，以解决结构化约束下已知的子模目标的连续松弛，例如包装和覆盖约束。

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.