AF: Small: Towards New Relaxations for Online Algorithms

我们都经常被要求在面对不确定性时做出决定：我们决定如何开车上班最好，或者如何以及以什么价格买卖东西（从房子到杂货）。我们的计算机也会做出这样的选择，以便为用户提供良好的性能：处理任务q的顺序以最大化吞吐量或最小化用户延迟，或者将哪些页面保存在快速内存中（因为它们很快就会被访问），以及将哪些页面移到较慢的内存中。这些问题不属于经典的“一次性”计算框架，即算法读取输入，处理并产生输出。相反，它们属于顺序决策领域，特别是在线算法，它提供了一个框架，我们可以在其中形式化这些问题，并对其解决方案进行推理。对于这样的问题，两种相互竞争的欲望之间存在着一种自然的紧张关系：(a)做出决定，使即时满足最大化，但从长远来看可能会很糟糕，或者(b)等待并调整到一个有利的位置，以便在未来获得收益。该项目旨在开发通用算法，为在线优化中广泛的优化问题找到在这两个极端之间对冲的最佳方法。例如，考虑k-server问题，它是该领域的中心问题。在这种情况下，一个人控制k个服务器，它们在度量空间的某些位置之间移动。随着时间的推移，请求序列到达，其中每个请求指定一个位置，并且必须将其中一个服务器从其当前位置移动到该请求的位置。我们的目标是尽量减少总的服务器移动。给定一个请求，应该移动哪个服务器？如上所述，在贪心和移动离请求位置最近的服务器和移动较远的服务器以便为将来的请求提供更好的位置之间存在权衡。为这个问题和相关问题开发好的算法一直是该领域的主要挑战。该项目将研究解决这一挑战的三种方法：(a)制定设计随机设置的广泛适用算法的一般原则，特别是将经典功函数算法（在确定性设置中接近最优）扩展到随机设置；(b)得到k-server及其推广的可扩展鲁棒凸松弛，并利用这些松弛得到好的算法；(c)为典型情况制订更广泛的框架，而不是集中于最坏情况。我们的工作将借鉴线性和凸优化、随机优化和最优停止理论以及在线学习的思想，以加深我们对这些和其他不确定条件下优化的核心问题的理解。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

We all are regularly asked to make decisions in the face of uncertainty: we decide how best to drive to work or how and at what prices to buy and sell things (everything from houses to groceries). And our computers make such choices as well to give good performance to their users: which order to process tasks q to maximize the throughput or minimize user delay, or which pages to keep in fast memory (because they will be accessed again soon) and which others moved to slower memory. These questions do not fall in the classical ``one-shot'' framework of computation, where an algorithm reads in the input, processes it and produces its output. Instead, they fall in the area of sequential decision-making, and specifically of online algorithms, which provides a framework in which we can formalize such questions and also reason about their solutions. For such problems, there is a natural tension between two competing desires: (a) to make decisions that maximize the instantaneous gratification but may be poor in the long run, or (b) to wait and maneuver into a good position to make gains in the future. This project aims to develop general-purpose algorithms that find optimal ways of hedging between these two extremes for a broad class of optimization problems in online optimization.As an example, consider the k-server problem, which is a central problem in this area. In this, one controls k servers which move between some locations in a metric space. A sequence of requests arrives over time, where each request specifies a location, and one must move one of the servers from its current position to this requested location. The goal is to minimize the total server movement. Given a request, which server should be moved? As mentioned above, there is a tradeoff between being greedy and moving the servers closest to the requested location and moving more distant servers to be in a better position for future requests. Developing good algorithms for this and related problems has been a major challenge in the area. This project will investigate three ways of addressing the challenge: (a) To develop general principles for designing broadly-applicable algorithms for randomized settings, and in particular, to extend the classical work function algorithm (which is near-optimal for the deterministic setting) to randomized settings; (b) To get extendable, robust convex relaxations for k-server and its generalizations, and to use these relaxations to obtain good algorithms; (c) To develop a broader framework for typical instances, instead of focusing on the worst-case instances. Our work will draw on ideas from linear and convex optimization, stochastic optimization and optimal stopping theory, and online learning in order to deepen our understanding of these and other central questions in optimization under uncertainty.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.