Summary
This paper studies the logarithmic pooling method for prediction using expert advice. At each step, $m$ experts report distributions $p^1, p^2, \ldots, p^m$ over a size-$n$ domain. The goal is to make predictions with a vanishing regret in terms of the log loss.
The usual logarithmic pooling returns an aggregated distribution $p^*$ such that each $p^*(j)$ is proportional to $\prod_{i=1}^m[p^i(j)]^{1/m}$, the geometric mean of the predicted probabilities. This paper considers a generalization in which the exponent for each expert is replaced by $w_1, w_2, \ldots, w_m$ that sum up to 1 (instead of $1/m$ identically), and the goal is to learn the right set of weights to achieve a low regret.
Formally, each round of the prediction proceeds as follows: First, algorithm selects weights. Then, adversary chooses the experts' forecasts and the outcome subject to a *calibration* condition. The two steps are in sequential order, so that the forecaster is prevented from outputting an arbitrary distribution.
The main result of the paper (Theorem 3.2) states that the regret can be upper bounded by roughly $m^{3/2}n\sqrt{T}\log T$ in the $T \gg m, n$ regime. The algorithm uses online mirror descent with the Tsallis entropy regularizer.
Strengths
The problem setting is quite natural and well-motivated. The authors did a good job in explaining why certain assumptions are necessary by providing illustrative examples. While the solution is based on online mirror descent, the analysis of the algorithm requires several new ideas that seem to be non-trivial and of independent interest.
Weaknesses
- The scope of the setting is limited to logarithmic pooling and the log loss.
- The tightness of the bound is unclear; an $\Omega(\sqrt{T})$ lower bound is proved for a restricted class of algorithms, while the polynomial dependence on $m$ and $n$ might be sub-optimal.
- Several aspects of the setting don't seem sufficiently convincing; see questions below.
Questions
- The setting assumes that the adversary chooses the forecasts and outcome after seeing the weights selected by the algorithm. If both parties act simultaneously, would the setting become significantly easier? (In particular, the obstacle of Example 1.1 still seems to be there?)
- What if the weights don't need to sum up to 1? Would that change the expressivity of the aggregation? (Multiplying $w_1, \ldots, w_m$ by the same factor seems to give a different distribution.)
- Lines 63--70 argue that we need to keep the algorithm from seeing the experts' advice, so that the algorithm cannot "output an essentially arbitrary function of the forecasts". What would be the practical motivation/justification of this choice?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The main limitations are the assumptions made regarding the setting (e.g., the adversarial choices of outcomes and forecasts must satisfy the calibration condition). These have been clearly pointed out in the abstract and introduction and, the assumptions are formally stated in the paper.