- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper studies the problem of online learning with expert advice, and investigates the choice of a "step" parameter for a specific FTPL mechanism. The main contribution is to show the reduction of that parameter (relative to exponential weighting) so that the regret can be kept bounded.
Critical strengths
The online learning with expert advice is a very general and useful problem to understand, and the FTPL-style algorithm is interesting so any meaningful results are useful. However the motivation of this work is not very clear to me.
Critical weaknesses
The motivation and the overall contribution is not very clear to me, with some detailed comments in the Questions section.
Questions for authors
-
the motivation of this paper is not very clear to me. The central question of this paper seems to be “against an \eta-mixable loss, by what factor must the step \eta of exponential weights be divided for the regret of the mechanism to stay bounded, and what determines that factor?” My understanding is that, the authors would like to understand how much the \eta parameter in the exponential weighting needs to be reduced if we use an FTPL-style mechanism. However, given the discussions above, I don’t see the significance of this question.
-
the contribution of the paper is also not very clear to me. In the abstract it is stated “we determine the price on every product…” so it seems that “price” is a central object. But then I don’t find the actual definition of “price” in the paper. Does this refer to the temperature \kappa^*?
-following the above, it seems to me that the contribution is to determine the reduction in \eta to guarantee a bounded regret (Proposition 1). I don’t quite understand why this result is significant. Similarly, Theorem 1 characterizes the temperature, for which (given above) I don’t quite see the significance
- At the beginning of Section 1.1. It is stated “the setting is the one the two literatures share”. What two literatures? The paper then describes the setup using text, which is quite unclear to me in general. I only found the formal definition of the problem (and the notion of regret) in the middle of Section 2 Settings, after Definition 1/2. This writing seems quite suboptimal to me.
2 comments
Response to Reviewer HT4u (2/2)
"Price" and the temperature. Yes, the "price" of the submitted abstract was the temperature , and the revised paper no longer uses the word. The abstract now asks by what factor the learning rate of exponential weights must be divided. The introduction defines the temperature as the least such that, at the step , every update lowers the potential of the mechanism by at least the step times the mix loss of the round, whatever the energy and the losses. The potential is the expected maximum of the perturbed objective, and the mix loss is for the weights and the losses of the experts. Proposition 1 shows that the temperature is exactly the factor that the abstract asks for.
Why Proposition 1 and Theorem 1 matter. In Proposition 1 we prove that at every constant step the regret is at most at every horizon, for every energy and every loss sequence, and that above this step some energy and some loss sequence make the regret grow linearly. Here , the potential range displayed in Section 1.1, depends on the energy but not on the losses. So is the largest constant step that keeps the regret bounded.
Proposition 1 alone leaves the temperature defined by an inequality that must hold at every energy and every state of the learner. In Theorem 1 we compute it. On every product decision set, the configuration space of a graphical model, the temperature equals the fractional certificate complexity . This is the value of a linear program, displayed in Section 1.1, that involves only the decision set and the readout , the map from a configuration to what the loss depends on. The step therefore depends only on and on these two, and it is known before any loss is seen. When the loss may be any function of the values of variables, the step is whatever the energy. When it depends on the variables only through a function of them, the temperature can be smaller than their number. For odd , the majority of bits depends on all bits and has temperature , about half of . The address function, which returns the data bit selected by address bits, depends on bits and has temperature , exponentially smaller. Dividing the step by the number of bits that the loss depends on, which is always enough (Theorem 2(c)), would make the regret bound for this function exponentially larger than necessary.
On every decision set the temperature lies between and (Theorems 1 and 2). For the Gumbel-Matching distribution of Mena et al. (2018), which perturbs every entry of an score matrix and whose decision set, the permutations, is not a product, the temperature is exactly when the loss depends on the whole matching (Corollary 1). Table 1 lists these values.
The two literatures and the formal problem. The two literatures are online learning, where the method is follow-the-perturbed-leader with one Gumbel per variable-value pair, and structured prediction, where it is perturb-and-MAP. The revised introduction names both and explains that the two methods run the same procedure, the mechanism. Section 1.1 now begins with the definitions and the mechanism (Definition 1), followed by the game, in which each output of the readout is an expert with a forecast. The learner combines the forecasts into one prediction, weighting each expert by the probability with which the mechanism outputs it, and updates the scores of the outputs by the losses. The regret, measured by the mix loss of each round, is displayed together with the inequality by which it bounds the ordinary regret of the predictions. For the log loss at , with the mixture of the forecasts as the prediction, the two regrets are equal, so the paper bounds the ordinary regret of the learner that predicts with this mixture. The main results follow as formulas, items (i) to (iv), with Table 1.
We hope that the revised introduction makes the motivation and the contribution clear, and we would be glad to clarify any passage that you still find unclear. Thank you again for the effort that you have devoted to our work in this review. Your questions on the motivation and the contribution have made the paper clearer.
Response to Reviewer HT4u (1/2)
Thank you for your careful review and for your questions on the motivation and the contribution of the paper. We agree that the submitted version had shortcomings in the clarity of its writing and presentation, and that it did not present its motivation and its contribution as clearly as it should have. We have substantially rewritten the introduction and Section 1.1, using the additional page allowed in the discussion period. They now show first why the question matters and then state the problem formally and give the main results as formulas. The numbered statements of the submission are unchanged in content, and new and substantively changed text is marked in red in the revised paper.
Why the question matters. Against an η-mixable loss, such as the log loss, exponential weights run at the step η keeps the regret bounded at every horizon. In combinatorial online learning and in structured prediction an action is a configuration of many variables, such as a labeling of a graphical model, a subset or a matching, and the actions are exponentially many. Exponential weights over the actions can be sampled with one independent Gumbel per action and one maximization, but that noise has exponentially many entries. The methods in use perturb the variables instead. Follow-the-perturbed-leader in the oracle form of Kalai and Vempala (2005), run with Gumbel noise, and perturb-and-MAP both draw one Gumbel per variable-value pair and make one call to an optimizer per sample, for a graphical model a maximum a posteriori (MAP) solver. We call this procedure the mechanism. Perturb-and-MAP was introduced for random fields in computer vision (Papandreou and Yuille, 2011) and has since been applied to subsets, permutations, matchings and other structures (Tarlow et al., 2012; Mena et al., 2018; Paulus et al., 2020; Berthet et al., 2020; Niepert et al., 2021). The output distribution of the mechanism in general differs from that of exponential weights, and neither literature had determined at which step the mechanism keeps the regret bounded against a mixable loss. We prove that at the step η its regret can grow linearly, and we determine the largest step at which it stays bounded.
The revised introduction shows this on an Ising model. Each joint label of k≥2 sites is an expert. The learner keeps the energy of the model as a fixed prior and weights the experts by the exact probabilities with which the mechanism outputs them. Whatever the energy of the model, the step η/k keeps the regret bounded at every horizon, while at every larger step, the step η included, some sequence of losses makes it grow linearly (the new Corollary C.2). A loss on the joint labels of 3 of 100 sites thus calls for the step η/3, whatever the other 97 sites and the energy. Appendix E computes the regret on Ising chains of three sites at four coupling strengths, with the loss on all three labels and η=1. At the step η it grows at a rate of 0.021 to 0.114 per round, and at the step η/3 it stays below 3.5. The learner in this example uses the exact probabilities. One that only draws samples of the mechanism keeps its expected regret bounded with two samples per round, at a step smaller by a constant factor and for losses of bounded range (the new Proposition 2).
A learner that runs the mechanism needs to know exactly by what factor to divide the step η. With too small a divisor the regret can grow linearly, and with too large a divisor the regret bound, which is proportional to the divisor, is larger than it needs to be. Sometimes the answer is that the learner need not shrink the step at all. On the one-hot encoding of n≥2 experts the mechanism is follow-the-perturbed-leader with independent logistic noise, the difference of two Gumbels. Its output distribution is not a softmax, yet its factor is one, so the learner can keep the full step η of exponential weights with regret bounded at every horizon (end of Section 4). The paper determines this factor, and with it the step that the learner should use.