Summary
The paper considers a binary prediction game on $0-1$ loss, it proposed efficient sampling scheme via an modification of the exponentiated weight forecaster, which selectively acquire labels $y_t$ based on $Ber(q_t)$, where the design of $q_t$ is correlated to the disagreement among experts’ predictions at each round for the exponentiated weight forecaster.
Ultimately, the proposed algorithms achieves the regret of the exponentiated weight forecaster $O(\ln N \sqrt{ n} )$ over time horizon $n$ and $N$ number of experts, the design labelling acquisition parameter $q_t$ resultant to a labelling complexity of $O( \frac{\sqrt{n}}{\Delta^2} )$, where $0 < \Delta \le \mathbb{E} [\ell_{t,i} - \ell_{t,i^{\ast}}], \forall t \in [n], i \neq i^{\ast}$ represents the lower bound expected loss gap comparing to the optimal expert with index $i^{\ast}$, which also signifies the difficulty of identifying the optimal experts.
Strengths
The paper is well written and easy to follow. It first introduces the intuition of sampling parameter $q_t$ if there is a perfect expert, then extended to general case. The paper also provided an graphical illustration on the lower bound of $q_t$ which matches with expectation.
The result is novel comparing to previous result in two folds. (1) There is no assumption on how $y_t$ is generated. The proposed algorithm is able to attain the $O(\ln N \sqrt{n})$ regret without less labels. (2) In contrast to previous work on sampling by disagreement, the label complexity can be quantified as $O(\frac{\sqrt{n}}{ \Delta^2})$.
$q_t$ is easy to compute, numerical experiment with respect to time horizon $n$ shows the expected regret and expected number of labels which matches with theoretical results. Experiment with respect to number of label (number of weights update) shows labelling efficient algorithm proposed in the paper matches the minimax rate in active learning asymptotically.
Weaknesses
It seems that the assumption $0 > \Delta \ge \mathbb{E} [\ell_{t,i} - \ell_{t,i^{\ast}}], \forall t \in [n], i \neq i^{\ast}$ is required only for bounding the labelling complexity, ( in order to track how $q_{t+1}$ evolves in line 493), without this assumption the regret still holds.
I am a bit concern such assumption is very strong, it generally asks the best expert $i^{\ast}$ is wining over every other expert at every round. In addition, the assumption is $\ell_{t,i} \in \{ 0, 1\}$, if we are at a specific iteration $t$ where $\ell_{t,i^{\ast}} = 1$, then what values can $\ell_{t,i}, \forall i \neq i^{\ast}$ take in order to satisfy the condition for a strictly positive $\Delta$?
Whether labelling complexity can be bounded without this assumption?
Questions
Appendix C:
From line 437 to line 438, whether intermediate steps could be further elaborated. I am concerned about the proof, which seems primarily confused on the relationship of combining minimum values: $\min_i (a_i + b_i)$ VS $\min_i(a_i)+ \min(b_i)$.
My understanding is that from the last equation line of line 437, we have
$$ L_{n |1}^{w_{.,0} } \le \frac{n \eta }{ 8 } \underbrace{ - \frac{\eta}{8 } + A_{1,1} + (1 - 2 A_{1,1})y_1 + \mathbb{E} \left[ \min_{i} \left( L_{i, n} + \frac{\ln w_{i,0}}{\eta} + \frac{q_1}{\eta} ( \ln w_{i,0} - \ln w_{i,1} ) - \ell_{i,1} \right) \right]}_{A} $$
To show the desired result claimed in the theorem, we aim to show
$$ A \le \mathbb{E} \left[ \min_{i} \left( L_{i,n} - \frac{\ln w_{i,0}}{\eta} \right) \right] $$
That is to show
$$ A_{1,1} + (1 - 2 A_{1,1})y_1 + \mathbb{E} \left[ \min_{i} \left( L_{i, n} + \frac{\ln w_{i,0}}{\eta} + \frac{q_1}{\eta} ( \ln w_{i,0} - \ln w_{i,1} ) - \ell_{i,1} \right) \right] \le \frac{\eta}{8 } + \mathbb{E} \left[ \min_{i} \left( L_{i,n} - \frac{\ln w_{i,0}}{\eta} \right) \right] $$
From the claim in line 438, it seems we need to show above inequality should hold even without expectation, that is:
$$ A_{1,1} + (1 - 2 A_{1,1})y_1 + \min_{i} \left( L_{i, n} + \frac{\ln w_{i,0}}{\eta} + \frac{q_1}{\eta} ( \ln w_{i,0} - \ln w_{i,1} ) - \ell_{i,1} \right) - \min_{i} \left( L_{i,n} - \frac{\ln w_{i,0}}{\eta} \right) \le \frac{\eta}{8 } $$
It seems the paper used
$$\min_{i} \left( L_{i, n} + \frac{\ln w_{i,0}}{\eta} + \frac{q_1}{\eta} ( \ln w_{i,0} - \ln w_{i,1} ) - \ell_{i,1} \right) - \min_{i} \left( L_{i,n} - \frac{\ln w_{i,0}}{\eta} \right) \le \min_{i} \left( \frac{q_1}{\eta} ( \ln w_{i,0} - \ln w_{i,1} ) - \ell_{i,1} \right) $$
which doesn't seem to be true. These intermediate steps are just my personal guess. I wonder whether details to understand those two lines in the manuscript can be further explained.
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.