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)较弱但相关的近似模型和算法用于重复摄动子问题。随着最近的结果缩小了各种环境下一阶优化的可能收敛速度的差距，这些问题已经变得至关重要，使下一次在运行时将受限决策扩大到以用户为中心的应用程序。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.