NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:4644
Title:Learning to Screen

Reviewer 1

The paper is extremely well written, very nice read! Still, the connection to hiring is a bit tenuous. I understand motivating this as related to the secretary problem, but with types / multiple open positions, but the abstract/intro are really application-focused for what quickly becomes an entirely theory matching paper. I'm positive on the matching results, but perhaps the connection to real hiring is a bit oversold. Some more in-depth comments/questions follow in the Improvements section.

Reviewer 2

The paper presents very solid theoretical result. It is also related to a classical problem in online algorithm (the online secretary problem). Overall, the paper is nicely written. There is a couple of suggestions that I have, but nothing major. Line 43 and 44 could be clarified a bit. First, it is said that they consider "algorithms" (plural), but on line 44 is used only "algorithm" (singular). Also, in either case, what are those algorithms considered there? I would suggest rewriting that entire paragraph. "As we shall see in the next section, learning from the training set allows one to retain exponentially less items than is implied by the theorem above" -- I don't see how is this the case. Both of the results are linear in k. Was is the idea to say that there is an exponential improvement in 1/delta? The paper does not study a pure online question. In online settings, one is supposed to commit to a decision immediately, while here it is not the case that a candidate should be assigned/hired immediately. The studied setting in this paper falls more into streaming setting, where one makes a pass over the stream, collects a small number of elements and at the end of the stream performs final computation. Moreover, there has been a number of papers studied streaming with random arrivals (submodular maximization, computing matching and estimating their size, randomized greedy for maximal independent set ...). It would be nice to mention this in the paper. I find this paper as a good fit for the program of NeurIPS. As discussed already, it would be beneficial to comment about fallback options. --- Updated review --- Thank you for the feedback. The feedback addresses my "fallback" question, so I increased the score. It still would be nice to be more careful in which way is this problem addressed -- as already discussed, this problem does not fall into the standard category of online problems, so I hope that this will be addressed/discussed in a revised version.

Reviewer 3

my main concerns about the paper are: (1) Note that the authors considered d properties instead of one in previous research with the complex feasibility constraints. This makes the problem rather challenge and practical. However, the method the authors adopted for the d scenarios is relatively simple due to an independent assumption on the d properties, which may weaken the contribution here. (2) Is it meaningful to provide a bound on the minimum possible number of retained items? (See line 16) Is this a typo? In my opinion, it is more practical and meaningful to provider a bound on the maximum possible or expected number of retained items. (3) How to set the number of considate items, k_1, k_2, ..., k_d with regards to each properties in the first stages? And also, how to set the total condidate number k here? (4) In line 113, the notation for the edge (l, r) is legal, where l \in {1,2, ..., k}, r \in {1,2, ..., n}. However, the notation for v_l(r) represents the value of item r associated with property P_l, where l \in {1,2, ..., d}. There exists inconsistence. (5) In line 196-197, Assume towards contradiction that T retains an item cj \notin S..., should it be "reject" instead of "retain"? (6) The paragraph for "Formulation as bipartite matching" seems redundant here since it is no longer referred in the later part.