Barely Random Algorithms and Collective Metrical Task Systems

We thank the reviewer for their interest and their careful reading. We note that the reviewer's appreciation of our results seems very positive, and that their only concern is whether the paper is a good fit for NeurIPS. We attempt to convince the reviewer that this is indeed the case, in the hope that they would increase their rating in a way that reflects their appreciation of the paper's inherent quality.

While metrical task systems (MTS) is a problem that originated in the 1990s from the community of theoretical computer science (TCS), we observe that in the last 5 years the problem has gained a strong interest in the machine learning community, with many contributions on learning augmented algorithms [1,17,2,18,3] and on concrete applications of MTS [37, 25]. Most of these papers were published at NeurIPS.

We note that our work has a flavor that is very similar to learning-augmented algorithms. Learning-augmented algorithms use predictions coming from a black-box algorithm, in the hope to improve over the performance of competitive algorithms when predictions are accurate. In a similar fashion, our method tracks a fully fractional configuration seen as coming from a black-box algorithm, and makes it barely fractional in a competitive way. We therefore expect our methods could be relevant to researchers working on learning-augmented algorithms, for instance when they need to interpolate smoothly between black-box configurations coming from one or many predictors.

Our work is also motivated by concrete applications. The method we propose is very easy to implement and can be applied to concrete problems such as dynamic power management [2], distributed systems [30,21] or asset management (Remark 2.3). For a very immediate example of an application of our work to a power management problem, we encourage the reviewer to read the second item of our response to Reviewer stvh.

The result on the existence of a barely random algorithm for MTS has indeed a theoretical flavor. But it is only one of the consequences of our analysis. Our results also imply for e.g. that a deterministic (finite) team of agents can be competitive in a way no single agent can be – which echoes of the study of intelligence in multi-agent systems. A totally different interpretation of our results is in advice complexity (Corollary 1.4) a subject which is very connected to learning-augmented algorithms. For more details on this aspect of the paper, we encourage the reviewer to read the first item of our response to Reviewer stvh.

Before submitting this paper to NeurIPS, we carefully verified the "NeurIPS 2024 Call for Paper" which lists the topics in the scope of the conference. We felt that our paper falls entirely within the scope described by this document (specifically, at the intersection of Theory, Optimization and Online Machine Learning). We encourage the reviewer to check these guidelines when finalizing their rating.

Finally, we understand and truly appreciate the intent of the Reviewer to make the results of the paper known to the TCS community. We will not miss other opportunities (workshops, seminars or other submissions) to engage with this community as well, in the hope to develop application-driven and theoretically-grounded works for online settings.

• Regarding the reviewer’s question, we believe that our techniques could help to prove new results for other online problems (such as k-servers or metrical service systems), even though there is no immediate reduction.

We thank the reviewer for their constructive feedback and suggestions. We answer the reviewer's questions below.

• The reference "Online Computation with Advice" by Emek et al. pointed out by the reviewer is very relevant and will be added to the paper: Emek et al. study the situation where $b$ bits of advice are provided at each time-step to a deterministic MTS algorithm, for $b$ of order $\log n$. The total amount of advice in this reference is therefore of order $B = \Theta(\log n*T)$, where $T$ is the number of time-steps. One surprising consequence of our results (Corollary 1.4) is that we present a deterministic MTS algorithm that has a competitive ratio of $O(\log^2 n)$ using a single advice of total size $B = 2\log n$, i.e. $B$ is now independent of the number of time-steps $T$. As suggested by the reviewer, we will add a brief discussion on this matter in the revised version of the paper.

• As the reviewer points out, we also provide a randomized algorithm which requires very few random bits (again, $B= 2\log n$, independently of the input size). The method is therefore helpful in any setting where acquiring random bits is costly. In concrete implementations, we also expect that barely fractional configurations (which are discrete objects) are generally much more practical to handle for computers than fully fractional configurations (which are arbitrary real numbers). But perhaps the most applied consequence of our results is that a deterministic team of k agents can be competitive in a way that no single agent could be (provided that $k\geq n^2$). This has for instance a very direct implication in energy management [2]. Consider a computer with three energy modes (on, sleep, off) with a switching cost of $1$ between on and sleep and another switching cost of (say) $5$ between sleep and off. At each time $t$ the request is either that

  • the computer is used: in which case $c(t) = (1, +\infty, +\infty)$ so the computer must be in state on ; or
  • the computer is not used: in which case $c(t) = (1, 0.5, 0)$ so the computer would rather be off than sleep, and sleep than on.

  This simple setting was presented by S. Bubeck to motivate the relevance of MTS in a series of lectures in 2019 (Five miracles of mirror descents, available on Youtube). Consider the variant of the problem, where the computer is in fact composed of $k = 9$ components (e.g. screen, CPU cores, etc.) that can each individually switch between one of the three modes (on, sleep, off). The energy spent by the computer is the sum of energy spent by its constituents. Since $n=3$ and $k > n^2$, our results imply that this system can enjoy the randomized competitive ratio (up to a factor 2) against a deterministic adversary!

• Typos will be corrected.

We thank the Reviewer for their interest and their thoughtful questions.

• To the best of our knowledge, the use of the Birkhoff-von Neumann theorem in the context of competitive analysis is new. We build upon this theorem in Proposition 2.2 of Section 2.2. As the reviewer points out, the purpose of Proposition 2.1 (which is well-known in the literature) is just to give more intuition on the more complex setting. We will highlight this in the revised version of the paper. The other key novel technical part of our analysis is in Section 3 where we develop a first-order method that displays a hysteresis phenomenon to track a fully fractional configuration with a barely fractional configuration. This shows the existence of $O(\log^2 n)$-competitive barely fractional configurations, which in turn has implications for randomized algorithms, collective algorithms and advice complexity.

• The application suggested in Remark 2.3 is quite natural: since our algorithm only moves significant amounts of mass, it is not sensitive to (small) fixed transaction costs ; this comes in contrast with fully fractional algorithms, because they move arbitrarily small amounts of mass. We believe that this application is also new and was out of reach for previous methods.

• As suggested by the reviewer, we will add a (very short) pseudocode to highlight the simplicity of our method.

• Section 3 is reminiscent of offline first order optimization in many ways. Gradient descent of a function $f(\cdot)$ is also known as the explicit Euler method, where one can write the $t+1$-th iterate of the method as the minimizer of the sum of the first order approximation of $f(\cdot)$ at the previous iterate and a quadratic cost, i.e.

$ x(t+1) = \arg\min_x \nabla f(x(t))(x-x(t)) + ||x-x(t)||^2.

$

A very closely related method is the implicit Euler method where the $t+1$-th iterate is the minimizer of the sum of $f(\cdot)$ and a quadratic cost,

$

x(t+1) = \arg\min_x f(x) +||x-x(t)||^2,

$

which is also known as the Proximal operator. Our Equation (2) is reminiscent of this Proximal operator, which has important stability properties. One key difference is that we replace the squared norm by an optimal transport cost, and that the offline objective function $f(\cdot)$ is replaced by a potential which is defined online. Note that quite recently, the notion of Wasserstein proximal operator has also appeared as a central object of study in the context of diffusion and partial differential equations (see e.g. the review of Santambrogio on Gradient Flows). A key difference with our Equation (2) is that we consider the Wasserstein-1 metric (aka, the earthmover distance) and not the Wasserstein-2 metric. We will add a discussion on the reviewer's question in the final version of the paper.

• If the reviewer is satisfied with the novelty of our method, and with the proposed revisions, we kindly encourage them to positively reassess their rating of the submission.

• We will correct all typos, put more emphasis on the potential function and add citations in lines 141-148.

We thank the reviewer for their encouraging review!