NeurIPS 2020

### Review 1

Strengths: - The secretary problem is one of the central problems in online learning; understanding how to design algorithms for it given external advice is a natural and important direction. The other two online problems studied in the paper are also very natural. - Authors develop algorithms which effectively achieve a “best-of-both-worlds” guarantee for the three online problems they study, achieving at least the (best known) no-advice competitive ratio for two of the three problems. - Their techniques lead to a new no-advice deterministic online algorithm for the graphic matroid secretary problem a new no-advice truthful mechanism for the online bipartite matching mechanism (in a specific constrained setting).

Weaknesses: - It would be nice if there was some general statement connecting all three settings. What property does the problem need for these sorts of algorithms to work? - Is there any sense in which you can show that the tradeoffs you find between competitive ratio for different values of eta are tight? (I suspect this might be very hard).

Correctness: I have not checked the proofs of the propositions carefully, but they appear correct/reasonable at a first glance.

Clarity: The paper was well-written and easy to understand.

Relation to Prior Work: This paper cites the relevant prior work. It is a significant improvement over prior work; to my knowledge this is one of the first papers (the first paper?) studying the secretary problem and variants with machine-learned advice.

Reproducibility: Yes

Additional Feedback: I enjoyed reading this paper a lot. I think it is a strong paper; incorporating external advice into online learning algorithms is an active and interesting area of research, and this paper represents significant contributions to this area. Questions: - In the graphic matroid secretary problem, the advice is the form of “for each vertex, the maximum edge-weight adjacent to that node”. Does this actually encode the optimal spanning tree? To me it seems like it encodes some subset of the spanning tree, but not enough to necessarily recover the spanning tree. In this sense it feels a little bit weird - Is there a “for any c>=1” missing from the statement of Theorem 1.2?

### Review 2

Summary and Contributions: The paper considers secretary problems (and related problems) in the setting where one seeks to maximize the expected value of the outcome and one is given a prediction as to what the maximum value is.

Strengths: The model and approach appear sensible. The results are fairly clearly written and make sense. The work appears novel, and in general these kinds of problems are of relevance to the NeurIPS community. The rapidly growing area of "algorithms with predictions" is nicely added to.

Weaknesses: The results are fairly straightforward if well executed. The role of prediction offers only slight variations on the standard analysis here. Their strategy is not shown to be optimal and because of its simplicity is suggests it can be improved on readily in future work.

Correctness: The work (proofs) appears to be correct.

Clarity: Generally the paper is well written although by necessity a lot appears in the supplemental. It's not especially clear when reading through why Lambert's function is making an appearance; while space is at a premium, I'd suggest making that clearer if at all possible in the main paper.

Relation to Prior Work: The paper discusses prior work suitably.

Reproducibility: Yes

Additional Feedback: Perhaps my main reasons for not pushing harder for acceptance are the following: 1) the value maximization version of the secretary problem is generally "easier" than the version trying to maximize the probability of finding the highest; and in that sense, this corresponds to their analysis being fairly straightforward. (Though, given the generalizations to multiple problems, quite useful.) 2) They do not provide lower bounds; it's a bit unclear that the "3-phased" approach given (observe, try to get prediction, then do the best you can) is optimal, although it would be very interesting if it were! Overall this is nice work and I'd generally be in favor of acceptance. Post author-feedback: I don't think the feedback affected my overall picture of the paper significantly. I still think it is a reasonably good paper and my rating reflects that it is marginally above the acceptance threshold.

### Review 3

Strengths: 1) The paper is written at a very high mathematical standard. 2) The secretary problem (and its variants) are theoretically important (and practically to a lesser extent) so a study through the lens of the advice framework would be of interests to researchers in online algorithms and algorithmic game theory.

Weaknesses: 1) The algorithms (although rigorously analyzed) are somewhat obvious modifications of the best known ones from the online literature. 2) The bounds have o(1) terms and start improving over the previously known results for arbitrarily long inputs. I am not sure how large these inputs needs to be, but it seems that this would seriously limit the applications of this approach. 3) I am a bit skeptical about how the competitive ratio results are presented. Ideally, I would have liked a result like the meta-result (or similar tradeoff) using only \lambda (or only c) and the prediction error. Instead the actual statements contain both the \lambda and c confidence parameters. This could be ok, but I don't think that a good tradeoff is obtained for all combination of values \lambda and c. So, is \lambda chosen first and then c optimised accordingly, for the worst case value of the prediction error? Is it the other way around? Since OPT is unknown, just knowing \lambda seems to provide very little information regarding the accuracy of the prediction and I don't think it's obvious at all what the actual tradeoff is, given the current statements. From a theoretical standpoint there are advantages to this presentation, but in this case I would prefer something different.

Correctness: I didn't have time to thoroughly examine the proofs, almost all of which are in the supplementary material. But, a quick read seems to indicate that the paper is written to a high mathematical standard and the arguments (including the flow of lemmata and theorems) sound logical.

Clarity: The paper is very well written in the mathematical and bibliographic exposition, but the theorem statements are quite hard to parse in their current form. There is some qualitative intuition, but I would have liked a clearer punchline.

Relation to Prior Work: The related work is thoroughly discussed.

Reproducibility: Yes

Additional Feedback: After reading the rebuttal and discussing with the other reviewers, I remain unconvinced that the parameters of the algorithms can be feasibly chosen, thus I cannot improve my score.

### Review 4

Summary and Contributions: This paper considers the secretary and similar online non-adversarial problems in the setting where a machine learning estimator can provide some form of advice (with some prediction error). This is a recent setting where the goal is to use this advice to improve the competitive ratio of the online algorithm in the case where the advice is accurate, while not being penalized too much (within a constant factor) when the advice is inaccurate. In the case of the secretary problem, there is a stream of n numbers arriving in random order and the goal is to pick one so to maximize (the expected value of) its ratio to the maximum number. The typical approach picks the first number larger than the first n/e observed numbers and gives the well-known competitive ratio of 1/e. Now, given a prediction p of the highest number OPT (with unknown prediction error |p - OPT|), the authors introduce a generalization of the secretary algorithm which depends on a user-provided confidence parameter \lambda (how doubtful we are about the prediction accuracy) and a penalty parameter c (in case the prediction is wrong, we tolerate a 1/(ce) competitive ratio). The algorithm works as follows: (i) observe n/f(c) numbers and let z be their maximum; (ii) for n/g(c) steps, pick any number larger than max(z, p-\lambda); (iii) otherwise, ignore the prediction p, and pick any number larger than the ones seen so far. When the prediction p is close to OPT and lambda is small, this algorithm will beat the 1/e competitive ratio, otherwise it will pay at most 1/(ce). Analogous approaches are applied to online maximum-weight bipartite matching (with edges coming in a uniformly random order) and the graphic matroid secretary problem (which is equivalent to maximum-weight forest). In my opinion the problems and setting are interesting but it is hard to understand the significance of the competitive ratio improvements, especially considering that now the user is in charge of picking two hyper-parameters. I would have liked to see an experimental section to see the impact of these hyper-parameters: for example given a certain (small) c, how much of an accurate prediction and high confidence is needed in order to improve the competitive ratio. Minor: - L260: "I removed the footnote..." I believe this paragraph was unintended. - It's worth pointing out that for your secretary algorithm, \lambda doesn't need to be set until phase 2, after having seen a reasonable amount of samples. - Can any lower bound be proved in this setting?

Strengths: - Theoretically sound - Interesting setting

Weaknesses: - No experimental section - Setting of hyper-parameters may be non-trivial.

Correctness: Results are sound to me.

Clarity: The paper is well written but I would have liked the authors to elaborate more the consequences and corollaries of their main theorems.

Relation to Prior Work: Related work are properly presented.

Reproducibility: Yes