Learning-Augmented Algorithms with Explicit Predictors

We thank the reviewer for highlighting the positive aspects of our work and pointing out a typo.

As far as I understand it one can model the traditional black-box setting via the agnostic setting by using a singleton hypothesis class and the 'traditional' prediction error as loss. Is this true?

Yes, the classical setting of learning-augmented algorithms is indeed subsumed by the case where the hypothesis class contains only a single hypothesis. We will make sure to clarify this in the final version of our manuscript.

A minor weakness can be the algorithmic novelty for the concrete applications.

In our framework, we achieve better bounds than the works on multiple black-box predictions using simpler algorithms (e.g. see our results for non-clairvoyant scheduling and caching). This can be viewed as a strength rather than a weakness. Moreover, the idea of separating the learning and algorithmic parts is novel.

Another minor weakness is the close relation to the established 'multiple prediction' setting.

Our setting is able to model the established 'multiple prediction' setting. However, our setting is more general and flexible. As can be seen from our results, it naturally leads to clean and simple algorithms which we find important.

We thank the reviewer for their feedback. Most (if not all) works on learning augmented algorithms solve some learning problem in an ad-hoc manner by assuming a black-box access to some predicitions. In our framework, we "open the box" and define the learning problem explicitly. This allows for a deeper and methodical integration of results from learning theory in learning-augmented algorithms, and as we demonstrate, gives rise to simple and clean algorithms with better performance bounds than previous works. We hope that our "white-box" perspective will inspire further work.

how does the ability to (1) have a hypothesis class of information for the prediction and (2) update the prediction allow us to further surpass worst case lower bounds?

We use hypothesis classes to model the learning problem (as is standard in learning theory). Thus, when the input is compatible with one of the hypothesis in the class, our algorithms can outperform algorithms in the standard learning augmented framework. This can be illustrated by a simple example of a bi-modal input: there are only two possible scenarios, and there is no single set of pre-computed predictions which works well for both. In our framework, we can learn the actual input sequence while processing it and then apply the approriate set of predicitons. As illustrated in the paper, this idea naturally extends to more than just two inputs and as well as to noisy scenarios.

Similar situations happen in other frameworks of beyond-worst case analysis. For example, the input may be stochastic in the first scenario while possessing some specific pattern in the second scenario.

One might argue that the argument above does not apply to problems like caching, where previous works did consider predictions that are generated over time. As noted by reviewer qEgX, in such a setting, the predictor may adapt its predictions based on the part of the input seen so far. Our framework captures this in a principled way which allows theoretical analysis of such adaptability without committing to specific ad-hoc predictions.

It’s unclear to me how large the hypothesis class should be.

In principle, the hypothesis class reflects prior knowledge the algorithm design has on the learning problem. In practice the class can be determined e.g. using collected statistics of past inputs. Our framework is effective when one can indeed define a restricted hypothesis class which can capture the regularities in the inputs. (Otherwise we are back in the classical worst-case setting where any input is possible.)

Our framework allows one to try and reduce the size of the hypothesis class by ``clustering'' the hypotheses. Indeed this is likely to increase the distance of the actual input to the class. We specify the performance as a function of the size of the class and the maximum distance of an input to the class. Studying the relation between these parameters for specific applications is a nice direction for further research.

A few times, you mention something like “each hypothesis h(I) provided sufficient information about the instance in order to determine an offline optimal solution OPT(I)”. This statement cannot be literally true, as you study a problem whose offline version is NP hard.

We mean that $h(I)$ contains enough information to determine an offline optimal solution. We do not require that this could be done in polynomial time nor use it to compute an optimal solution: e.g. our algorithm for load balancing uses $h(I)$ to compute an approximate solution in polynomial time.

Thank you for pointing out that B.1 and C.1 are repeated. We will fix this.

We thank the reviewer for their feedback. However, their claim about our performance bound for non-clairvoyant scheduling being meaningless is incorrect. We study non-clairvoyant scheduling with the classical objective of minimizing the sum of completion times which has a different magnitude than the length of the schedule (or makespan). In particular, if all jobs have size 1 and the length of the schedule is $n$, as the reviewer suggests, then the sum of completion times is about $n^2$. Our regret bound is of order $n^{5/3}$, i.e. it is sublinear.

The algorithms, for example for caching, must iterate over the entire set of hypothesis every time.

It would be more natural if one would learn from all of them [hypotheses] simultaneously (so for ex 'learn' something from the first half of one past input and the second half of another).

Our paper describes a basic framework, and we focused mainly on the approximation guarantees and not on other (important) resources such as running time. However, our framework does allow for optimization of other desired resources. For example, to avoid the need of iterating over all hypotheses in caching, we can replace HEDGE in our predictor by a suitable algorithm for the bandit setting like EXP4 (which considers a single hypothesis in each time-step). Similarly, if we want to capture inputs partitioned into several intervals, each resembling different hypothesis, we can use, for example, the classical SHARE algorithm instead. Furthermore, our analysis readily implies how the regret guarantees of these algorithms (e.g. EXP4 or SHARE) translate to approximation guarantees of the implied learning-augmented online algorithm.

While in some scenarios it might be the case that the black-box predictor satisfies the two properties pointed out by the reviewer, in other scenarios it might not. Our framework allows to optimize and analyze the predictor explicitly towards achieving these properties and other desired properties.

There are no experiments, even simple synthetic ones. It would be interesting to see even in synthetic case if the framework can actually be carried out.

Our work is proposing a new theoretical framework for modeling of learning augmented algorithms. We have decided to focus on theoretical analysis. Experimenting with our framework is an interesting direction for future research.

There are no algorithms in the main body and it is hard to judge algorithmic improvements.

We have tried to informally convey the main ideas behind our algorithms in the main body. However we will try to further clarify these in subsequent versions (and welcome any suggestions toward this end).

We thank the reviewer for their positive words and for their useful suggestions to improve our manuscript. We respond the questions of the reviewer explicitly.

To what extent can these techniques be generalized? E.g., what can be said about -server?

Our framework can be extended to $k$-server, even to any Metrical Task System (MTS). In the lines of our results on caching, we can obtain the following bounds. In the realizable case, where one of the hypothesis is the input sequence itself, we can achieve regret $O(D\ln \ell)$, where $D$ is the diameter of the metric space. In the agnostic case, we can obtain regret $O(D\mu^* + D\ln \ell)$, where $\mu^*$ is the number of mistakes in the best hypothesis, where a mistake is considered each time the predicted request (or cost function) is not exactly the same as the real one. Our paper is already quite dense and adding MTS and k-server requires several additional definitions. We tried to illustrate the framework without making it too hard to read.

Only the case of finite $H$ is considered. Can anything be said about infinite but "low complexity" $H$?

The case of infinite hypothesis classes with low complexity of some kind is very interesting. This is a great direction for future work.

There is no experimental evaluation.

Our work is proposing a new theoretical framework for modeling of learning augmented algorithms. We have decided to focus on theoretical analysis. Experimenting with our framework is an interesting direction for future research.