CRII: AF: Faster Iterative Decisions within First-order Optimization Methods

目前，大多数以用户为中心的算法的核心是一个优化引擎，它试图根据迄今为止观察到的信息及时提供最佳决策。示例包括向新消费者推荐首选项目，在交通变化的道路网络中计算最不拥挤的路线，在需求变化的电网上径向分配电力，等等。所有这些问题都有一个固有的“组合”结构，它限制了人们可以采取的可能决策。当这些决定需要兼顾公平性和减少差异影响时，这种组合结构变得更加复杂，例如当搜索“科学家”时，女性/男性科学家的平衡代表。这些组合问题在计算上具有挑战性，需要严格而快速的算法来在必须实时做出决策的现实场景中有效地运行这些问题。在学习应用中流行的一大类优化方法，即所谓的一阶优化方法，是通过重复解决类似组合子问题的扰动来工作的。该研究项目将探索在一阶优化方法中如何计算先前子问题的解决方案的知识是否可以用于加快后续迭代的计算速度。如上所述，当必须实时做出具有组合结构的约束决策时，该项目具有加速广泛应用的潜力。这项工作的跨学科性质，跨越一阶优化方法和组合算法，将使学生受益，帮助他们培养更强大、更全面的STEM劳动力，并在本科生和研究生阶段的大量应用中产生影响。该项目为一阶优化方法(如Frank-Wolfe （FW)，镜像下降（MD）及其变体）和组合优化理论的合理整合提供了基础，具有广泛的应用。它将数据结构理论、近似算法、组合优化中的参数分析和迭代一阶优化方法的计算需求结合在一起，以实现总体运行时的平摊速度提升。MD和FW变体在每次迭代中仅依赖于单个数据点的函数值和梯度信息，这一特性使得这些方法可以用于许多实时机器学习应用。当如上所述进行约束组合决策时，这些方法重复计算两个主要的子问题：(i) FW变量的每次迭代中的线性优化，以及（ii） MD变量的每次迭代中的投影或凸最小化。有了这个奖项，研究者将探索(a)一阶方法中适合平摊分析的组合基元的识别，(b)在镜像下降变量中使用先前发现的紧切迭代投影，(c)凸问题的分解，(d)一阶优化的智能热启动解决方案的构建，(e)重复扰动子问题的较弱但相关的近似模型和算法。随着最近的结果缩小了各种设置下一阶优化可能收敛率的差距，这些问题对于使约束决策的运行时扩展到实时以用户为中心的应用程序变得至关重要。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

At the heart of most user-centric algorithms today is an optimization engine trying to provide the best decision with the information observed so far in time. Examples include recommending preferred items to new consumers, computing least congested routes in a road network with changing traffic, distributing power radially over electricity grids with changing demand, and so on. All these problems have an inherent "combinatorial" structure that constrains the possible decisions one can take. This combinatorial structure becomes even more complex when these decisions are required to incorporate fairness and reduce disparate impact, such as a balanced representation of female/male scientists when a search query for "scientists" is made. These combinatorial problems are computationally challenging, necessitating rigorous yet fast algorithms to run these efficiently in real-world scenarios where decisions must be made in real-time. A large class of optimization methods prevalent in learning applications, the so-called first-order optimization methods, work by repeatedly solving perturbations of similar combinatorial subproblems. This research project will explore whether the knowledge of "how" the solution was computed to previous subproblems within first-order optimization methods can be used to speed up computations in subsequent iterations. This project has the potential of speeding up a wide range of applications whenever a constrained decision with combinatorial structure must be made in real-time as mentioned above. The interdisciplinary nature of this work, spanning first-order optimization methods and combinatorial algorithms, will benefit students helping prepare a stronger and a holistic STEM workforce with impact in a large number of applications - at both undergraduate and graduate levels.This project serves as a cornerstone for proper integration of first-order optimization methods (like Frank-Wolfe (FW), mirror descent (MD) and their variants) and the theory of combinatorial optimization with wide-ranging applications. It brings together the theory of data structures, approximation algorithms, parametric analysis in combinatorial optimization and the computational requirements of iterative first-order optimization methods to achieve amortized speeds ups in overall runtime. MD and FW variants rely only on the function value and gradient information at a single data point in each iteration and this property has rendered these methods to be used in numerous real-time machine learning applications. When making constrained combinatorial decisions as described above, these methods repeatedly compute two main subproblems: (i) linear optimization in each iteration of the FW variants, and (ii) projections or convex minimization in each iteration of the MD variants. With this award, the investigator will explore (a) identification of combinatorial primitives suitable for amortized analysis within first-order methods, (b) use of previously discovered tight cuts for iterative projections within mirror descent variants, (c) decomposition of convex problems, (d) construction of smarter warm start solutions for first-order optimization, (e) weaker but relevant approximate models and algorithms for repeated perturbed subproblems. With recent results closing the gap of possible convergence rates for first-order optimization in various settings, these questions have become of paramount importance to enable the next scale up in runtime of constrained decision-making to real-time user-centric applications.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.