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

高效的算法是任何现代计算系统的核心。在算法的经典研究中，效率的概念一直被认为是等于输入大小的多项式运行时间。然而，最近出现的大规模数据集，甚至二次运行时间可能实际上是不可行的，导致重新思考这个假设。这一努力导致了一些基本问题的突破，例如计算网络中的最大流量，现在在许多情况下可以在基本线性时间内解决。这些进步主要基于凸优化和数值优化的新算法工具，这些工具严重依赖于连续数学。基于这种范式，PI的目标是提供改进的算法，在理论和实践中都很重要的两类问题：最大流问题和子模块优化问题。这些问题是计算机科学的核心，并广泛适用于许多现实生活中的问题。该项目将支持和培养两名博士。他是波士顿大学算法设计和优化专业的学生和博士后。拟议的研究需要理论计算机科学和持续优化之间进行有益的思想交流，加强现有的联系，并在两个领域之间建立新的联系。连续的观点为算法设计提供了一个新的视角，PI计划广泛传播并将其纳入波士顿大学的优化课程。在这个项目中，PI将通过考虑以下算法设计的连续方法，深入研究有效离散优化和连续数学之间的联系：算法最初被设想为通过问题的解的空间的连续轨迹，例如，如一组微分方程所描述的;这些轨迹被离散化以产生可证明快速的真正离散时间算法。我们计划利用通过这个框架获得的算法的新的理解，提供改进的算法，在理论和实践中都很重要的两类问题：最大流问题和子模块优化问题。该项目的主要技术重点将是理解和利用“加速”的思想，这在凸优化中起着核心作用，因为它为一大类函数产生最佳梯度下降算法。最近的一系列工作开始从连续时间的角度使用常微分方程（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.