Learning-Augmented Algorithms with Explicit Predictors

Summary

The paper introduces a new framework for learning-augmented online algorithms. Learning-augmented algorithms (aka algorithms with predictions) are a very active subfield of beyond worst-case algorithm analysis. For online algorithms, which cope with uncertainty on their input, it gives an algorithm an addition information in form of a prediction. This prediction can be the (unknown) online instance or any other form of additional information. A learning-augmented algorithm is usually analyzed w.r.t. the quality of the given prediction. In the most commonly used setup for online algorithm, the prediction is assumed to be generated upfront from some black-box predictor, or arrives online together with requests. There are also models where multiple predictions are initially available to an algorithm. The authors of this paper introduce a new framework which integrates both the predictor and the learning-augmented algorithm. The main motivation is that a predictor might update its prediction while the online instance is being revealed, and, thus, increase the prediction's quality over time. In their model, they assume that there are given a set of hypotheses, which can be thought of different characteristics which the coming input could have. The predictor can compute at any time a new prediction using these hypotheses and the input which has been revealed up to that time. The authors distinguish between two settings: the easier "realizable" setting, which assumes that the hypothesis which corresponds to the actual input is contained in the hypotheses class, and the harder "agnostic" setting, which does not make this assumption. The authors then apply this framework to three well-studied online problems in the learning-augmented area: caching, load balancing and non-clairvoyant scheduling. Some of their new bounds improve over previous work.

Strengths

- The paper introduces an interesting generalization of the traditional learning-augmented framework. I think that this new view on learning-augmented algorithm can have an impact on this rapidly evolving field, since it untangles concepts which have already been used partially. I also appreciate the clear structure of the framework into predictor and algorithm. - The framework is conceptually well motivated and the authors show that it can be applied to at least three different and well-studied problems, which proves that it is practicable and can be used for relevant problems. - The authors present improved guarantees for previously well-studied online problems.

Weaknesses

- A minor weakness can be the algorithmic novelty for the concrete applications. It seems that the algorithms follow in many cases the predictions given by the predictor. The predictors are tailored to the specific applications and are also rather simple. - Another minor weakness is the close relation to the established 'multiple prediction' setting. From my understanding, one can see the hypothesis class the set of given predictions, and the goal (in the agnostic setting) is to guarantee a bound w.r.t. the best one.

Questions

- 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? I am not sure if I missed this, but I think this could also be an interesting insight. Further comments: - Line 1140: there is a comma before the second inequality.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

As far as I see, all limitations have been properly addressed.

Summary

This paper proposes a new framework to use machine learned predictions to improve online algorithms. Recent work that has done this (in a slightly different framework) goes under the name learning-augmented algorithms (LA algorithms) or algorithms with predictions. The main difference in this work compared to the usual LA algorithms is that these authors propose integrating the learning problem into the algorithmic problem by allowing the algorithm to adaptively update its prediction based on the new information it receives. Additionally, instead of maintaining a single prediction, this framework maintains a hypothesis class of information about the instance. The paper exemplifies this framework on caching, online load balancing, and online non-clairvoyant scheduling. For all 3 problems they study a realizable and agnostic setting, where in the realizable setting, the hypothesis class contains h(I) for I the actual underlying offline instance, and in the agnostic setting, the information corresponding to the true offline instance is not necessarily in the class.

Strengths

- This framework could indeed be a better way to study algorithms with predictions. In combining the learning process with the algorithmic procedure we get the benefit of (1) demystifying how the prediction is obtained and (2) allowing ourselves the flexibility of updating the prediction as we receive new information about the input. - Using this more all-encompassing approach, the framework is able to improve upon some bounds from LA algorithms. - The authors did a good job in the related work differentiating their model from that on algorithms with a prediction pf portfolios, as well as data driven algorithms.

Weaknesses

The algorithms proposed are augmenting simple procedures with this richer, more flexible hypothesis class, and the analyses involved are very straightforward. This isn’t inherently a bad thing. But there is a lot of work in the LA algorithms scene lately, and the work that stands out to me the most is the work that highlights some interesting technicality of the problem that wasn’t understood through classic worst-case analysis approaches. I’m afraid the problems that this model has been applied on did not result in technical components that stood out, and thus could lead to this paper blending into an already noisy scene. I will leave more specific related questions that may address this fear under “questions”.

Questions

- How do you see this framework allowing us to understand the complexity of problems (from a beyond-worst case analysis perspective) in a better way than the standard LA algorithms framework or other beyond worst-case analysis frameworks? In other words, 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? - It’s unclear to me how large the hypothesis class should be. You get this trade off in the agnostic setting between having a large \ell should lead to smaller \mu^* indoor bounds, or a small \ell might imply larger \mu^*. Have you thought at all for the problems you study about how you can balance these? - 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. I think you mean something like, h(I) provides sufficient information about the instance in order to find an offline solution \alpha OPT(I) for alpha the apx factor, and then alpha comes into your completive ratio or regret bound. - Something seems weird in the appendix, section B.1 and C.1 have the exact text repeated. It seems B.1 is maybe a totally unnecessary section.

Rating

6

Confidence

5

Soundness

4

Presentation

3

Contribution

3

Limitations

yes

Summary

This paper considers a new formulation for learning-augmented algorithms/algorithms with predictions and applies it to the fundamental problems of online caching, online load balancing, and non-clairvoyant scheduling. In the new formulation, the predictions/predictor is made more explicit and is a part of the solution process. The predictions are given by a hypothesis class ${\cal H}$ of size $\ell$, which contains information about the "plausible instances" we are trying to solve. One can think of ${\cal H}$ as coming from past data and the goal is to use this information to get improved algorithms. This is done in two settings: the realizable and agnostic settings. In the realizable setting, the true instance is realized in ${\cal H}$, so we can compare to the optimal cost in hindsight. For this, the paper provides algorithms with the following bounds: - Caching: ${\rm OPT}+ k \log \ell$ - Load Balancing: $O(\log \ell \cdot {\rm OPT})$ - Non-clairvoyant scheduling: ${\rm OPT} + \ell \sqrt{ 2 \rm OPT}$ In the agnostic setting, the true instance may not be realized in ${\cal H}$, so instead we compare to the best hypothesis in ${\cal H}$. For this, the paper provides algorithms with the following bounds: - Caching: ${\rm OPT} + O(\mu^* + k \log \ell)$ - Load Balancing: $O( \mu^* \cdot \log \ell \cdot {\rm OPT})$ - Non-clairvoyant scheduling: ${\rm OPT} + \mu^* + O(n^{5/3} \log \ell)$ where in each, $\mu^*$ is a problem-dependent notion of distance from ${\cal H}$ to the true instance. Some lower bounds are given showing tightness or almost-tightness for these results.

Strengths

This paper gives a very different approach to learning-augmented algorithms that is interesting and has the potential to generate more ideas. While the algorithms once given the predictions are simple (they are all essentially some notion of follow-the-prediction), this work shows that these simple algorithms can work well if fed carefully constructed predictions (given by the prediction algorithms designed in this paper). Lower bounds are given showing that the results are somewhat tight.

Weaknesses

- I think it would help the presentation to give examples of hypothesis classes to make the main conceptual idea more clear and provide a stronger connection to practice. - There is no experimental evaluation. While some works in this area lack an experimental evaluation, there is a standard setup that has been used for the caching problem by Lykouris and Vassilvitskii [32] as well as Antoniadis et al. [4]. Providing such an evaluation could elucidate the construction of hypothesis classes and provide further evidence in favor of this paper's approach. - The writing has some awkward phrases and grammar throughout, e.g. the following (among others): - line 62 "... will be much smaller then ..." -> "... will be much smaller than ..." - lines 107-108 "... using arguably simpler approach ..." -> "... using an arguably simpler approach ..." - lines 306-307 "... under certain assumptions about input." -> "... under certain assumptions about the input." - lines 374-375 "In offline setting, ..." -> "In the offline setting, ..."

Questions

- To what extent can these techniques be generalized? E.g., what can be said about $k$-server? - Only the case of finite ${\cal H}$ is considered. Can anything be said about infinite but "low complexity" ${\cal H}$?

Rating

7

Confidence

4

Soundness

3

Presentation

2

Contribution

4

Limitations

Limitations and assumptions have been made clear. Potential negative societal impacts from this work are very unlikely.

Summary

The paper studies three online algorithms in the learning augmented model: caching, load balancing, and non-clairvoyant scheduling. The goal seems to be to 'online learning' flavored learning-augmented algorithms. Rather than having a single predictor that synthesizes or predict something about the online input, the authors propose a framework where we have access to a large class of hypothesis such as the set of all past inputs. The goal is to be competitive with respect to the best hypothesis for the online input in hindsight. For example in the caching problem, the hypothesis are a large set of input sequences, and the goal is to get close to OPT in the case that the online sequence is actually one of these inputs in our set of hypothesis. In the cases where the online input is not part of the set of hypothesis, the authors obtain error guarantees depending on the hamming distance of the online input and the closest one in the hypothesis. For the problems studied, the authors match or improve upon (in some parameter regimes) prior works which can be interpreted to be in their framework.

Strengths

- The motivation of the formulation is natural: having access say to the entire history of past inputs could allow one to directly learn the best predictor from data - The framework matches the best bounds for load balancing, and improves the caching result.

Weaknesses

- The $n^(5/3)$ additive error for non-clairvoyant scheduling seems to be a meaningless guarantee, since there are $n$ jobs which are assumed to have maximum job length $1$. So any scheduling guarantees that the jobs will finish in $n$ time. - The algorithms, for example for caching, must iterate over the entire set of hypothesis every time, which seems quite inefficient. - I'm also not sure if the formulation exactly captures the motivation of directly learning a good predictor from data. For example in caching, the performance seems to be 'bottle-necked' by a single past instance in the set of hypothesis, in the sense that we can only ever expect to do as good as the 'most similar' input in our set of past inputs. Rather, it would be more natural if one would learn from all of them simultaneously (so for ex 'learn' something from the first half of one past input and the second half of another). This is not the fault of their algorithms (which already achieve close to optimal performance), but rather the formulation itself. This is why I still think the standard prediction framework maybe more natural since a predictor can learn to synthesize information and implicitly combine different aspects of different past inputs seen, rather than relying on a single past input alone. - 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. - There are no algorithms in the main body and it is hard to judge algorithmic improvements.

Questions

- Can the authors clarify the n^(5/3) issue?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

No societal consequences.

Response to Rebuttal

I thank the authors for their rebuttal, and for answering my question about the connection to the traditional setting. My opinion about the paper and my score remain unchanged.