NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:5285
Title:Dying Experts: Efficient Algorithms with Optimal Regret Bounds

Reviewer 1

I feel like I have little to say about the paper. It tackles a reasonable problem variation, is well written, and contains some clearly interesting ideas in handling the problem. I enjoyed reading the paper and felt I learned something from it. If there is a possible negative comment it might be that the paper seems arguably "safe" or "incremental" -- it's not going to break open a new area. But it's well written, it covers a natural collection of variations, it has a number of good ideas, and it gets good theoretical results. Good ideas include there being a smaller number of "effective experts", that is not all K! orderings are important. The background is well explained. There is a nicely proven new lower bound. The Hedge-based algorithms are clearly presented as well. The proofs are clearly given in the appendix and are also well presented.

Reviewer 2

The paper investigates an interesting special case of the specialist experts protocol, namely, the case where the experts can sleep from some point on, i.e., die. An algorithm is constructed and upper and lower bounds are provided. The paper appears to have thoroughly studied the question. A particularly strong point of the paper is some non-asymptotic lower bounds for the hedge algorithm. I think this is really interesting work.

Reviewer 3

The dying expert setting is interesting, it would be appreciated to give more examples. The overall writing is good and easy to follow. I have a simple question on the performance measure, ranking regret. In the definition of (1), authors claim \sigma^t(\pi) is the first alive expert of ordering \pi in round t. So why do we need to specify the "first" alive expert, rather than the alive expert with the optimal performance? Meanwhile, a contrary setting -- growing expert -- should be mentioned in the related work. [1] Mourtada, Jaouad, and Odalric-Ambrym Maillard. "Efficient tracking of a growing number of experts." ALT (2017). Both upper bound and lower bound for dying expert setting are established, and this paper distinguishes the hardness of known versus unknown dying order. Minor issues: I would like to mention paper of [2] gives the non-asymptotic lower bound for expert advice problem, though the form is not as neat as Thm 4.1. [2] Orabona, Francesco, and Dávid Pál. "Optimal non-asymptotic lower bound on the minimax regret of learning with expert advice." arXiv preprint arXiv:1511.02176 (2015). line 222: missing one ")"