acceptodds
Under review as a conference paper at ICLR 2027

The Exact Mixability of Follow-the-Perturbed-Leader

Abstract

Follow-the-perturbed-leader with Gumbel noise in online learning and perturb-and-MAP in structured prediction run the same device, an independent standard Gumbel for every variable-value pair of a decision set followed by a single call to the optimizer. One Gumbel per action would make the perturbed maximizer an exact sample of exponential weights, whose regret against a mixable loss stays bounded at every horizon, but the actions are exponentially many. Noise on the variables keeps the single call and loses that exactness, at a price in learning rate that neither literature has determined. We determine that price on every product decision set, the configuration space of a graphical model, where it is exactly the fractional certificate complexity of what the loss reads. Dividing the learning rate of exponential weights by that complexity keeps the regret bounded at every horizon, whatever the energies of the model, and no smaller divisor does. A measure from Boolean function complexity thereby acquires an operational meaning, as the cost of a single optimizer call.

Primary area:
learning theory
Keywords:
online learning, follow-the-perturbed-leader, perturb-and-MAP, mixability, exponential weights, fractional certificate complexity

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_HT4uOpenReview ↗
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
AuthorsOpenReview ↗

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 η\eta-mixable loss, such as the log loss, exponential weights run at the step η\eta 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 η\eta 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≥2k\ge 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\eta/k keeps the regret bounded at every horizon, while at every larger step, the step η\eta included, some sequence of losses makes it grow linearly (the new Corollary C.2). A loss on the joint labels of 33 of 100100 sites thus calls for the step η/3\eta/3, whatever the other 9797 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\eta=1. At the step η\eta it grows at a rate of 0.0210.021 to 0.1140.114 per round, and at the step η/3\eta/3 it stays below 3.53.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 η\eta. 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≥2n\ge 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 η\eta 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.

AuthorsOpenReview ↗

Response to Reviewer HT4u (2/2)

"Price" and the temperature. Yes, the "price" of the submitted abstract was the temperature κ∗(M)\kappa^{\ast}(M), 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 κ\kappa such that, at the step η/κ\eta/\kappa, 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 −η−1log⁡∑ypye−ηℓy-\eta^{-1}\log\sum_y p_y e^{-\eta\ell_y} for the weights pyp_y and the losses ℓy\ell_y 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 α≤η/κ∗(M)\alpha\le\eta/\kappa^{\ast}(M) the regret is at most Γ/α\Gamma/\alpha 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 Γ\Gamma, the potential range displayed in Section 1.1, depends on the energy but not on the losses. So η/κ∗(M)\eta/\kappa^{\ast}(M) 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 FC(M)\mathrm{FC}(M). This is the value of a linear program, displayed in Section 1.1, that involves only the decision set and the readout MM, the map from a configuration to what the loss depends on. The step therefore depends only on η\eta and on these two, and it is known before any loss is seen. When the loss may be any function of the values of kk variables, the step is η/k\eta/k 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 nn, the majority of nn bits depends on all nn bits and has temperature (n+1)/2(n+1)/2, about half of nn. The address function, which returns the data bit selected by mm address bits, depends on m+2mm+2^m bits and has temperature m+1m+1, 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 FC(M)\mathrm{FC}(M) and 2FC(M)2\mathrm{FC}(M) (Theorems 1 and 2). For the Gumbel-Matching distribution of Mena et al. (2018), which perturbs every entry of an n×nn\times n score matrix and whose decision set, the permutations, is not a product, the temperature is exactly n/2n/2 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 η=1\eta=1, 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.

Reviewer_ehzKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies follow-the-perturbed-leader (FTPL) with Gumbel noises. From what I understood, FTPL with independent Gumbel noise over each action produces the canonical Gibbs distribution, yet in applications with combinatorial action sets, the size of the action set might be exponentially large, so imposing independent Gumbel noise over each action in FTPL might be expensive. Instead, in this work, the authors consider an ‘inexact’ FTPL, which imposes only Gumbel noise over the value set DiD_i of each base element ii in combinatorial setting. Thiss reducing the number of sampling from ∏i=1n∣Di∣\prod_{i=1}^{n} |D_i| to ∑i=1n∣Di∣\sum_{i=1}^{n} |D_i|. The statistical cost of doing this is the mix-loss regret might no longer be “bounded”. Thus the authors investigate how to divide the learning rate η\eta by a factor κ∗(M)\kappa^*(M), which can in turn make the ‘inexact’ FTPL still have ‘bounded’ mix loss regret.

Critical strengths
  1. Motivation: I think the motivation to study ‘inexact’ FTPL with only the Gumbel noise imposed over the value set DiD_i of each base element ii is interesting and of practical interest. The authors managed to show that dividing the learning rate η\eta by a factor κ∗(M)\kappa^*(M) secures the ‘bounded’ mix loss regret guarantee of ‘inexact’ FTPL.
Critical weaknesses
  1. Motivation: On the negative side, I have to say that some parts of the paper are not well-motivated. For instance, in online learning community, I believe the most common and natural learning objective is to minimize the vanilla regret

    RT=∑t=1T⟨pt−p∗,ℓt⟩.R_T=\sum_{t=1}^T \langle p_t - p^{*},\ell_t\rangle.

​ It's therefore unclear to me why we need to study mix loss regret. I would highly recommend the authors provide sufficient discussion on the motivation for studying mix-loss regret, instead of the vanilla regret.

  1. Computational efficiency: If I understood correctly, the main contribution of this work lies in reducing the number of samples from ∏i=1n∣Di∣\prod_{i=1}^{n} |D_i| to ∑i=1n∣Di∣\sum_{i=1}^{n} |D_i|, while re-scaling the learning rate to maintain the statistical efficiency. However, I think even if we could reduce the number of sampling from the Gumbel distribution, we still need to enumerate over VV to solve v∗v^*, right? In light of this, I think the overall computation complexity remains at least in Ω(V)\Omega(V), which thus makes the contribution of reducing the number of samples less important.

  2. Presentation: I have to say that some parts of this work are a bit difficult to follow. Specifically,

    1. Some key terms/concepts are not formally defined or sufficiently explained before they are used. For instance,
      • what exactly is the meaning of 'η\eta-mixable loss'?
      • what does MAP mean?
      • what does the 'mixable regime' mean on Line 45?
      • Definition 3 is called 'fractional certificate complexity'. Why is it called 'fractional'? Is it because each ziz_i need not to be an integeter? Then why is it called a 'certificate'? The overall naming 'fractional certificate complexity' does not seem to sound very natural.
      • In many parts of this work, the authors use the term 'Exponential weights'. Do the authors refer to Hedge/Exp-3-type update? I understand that the distribution of the sampled action in FTPL with independent Gumbel noise over each action has the same form as Hedge/Exp-3. But what's 'perturb-and-MAP'? Is it a kind of FTPL method? Both the terminology FTPL and 'perturb-and-MAP' appear in this work, making me a bit confused.
    2. Some descriptions on the techniques/results only have natural language descriptions in the introduction part, which are difficult for the audience to understand without going through the corresponding parts in Sec. 2-4. Especially, from Line 66-Line 134, the are only natural language descriptions for the results. I think it would be much better to just replace the natural language descriptions with the concrete math formulas of the results. I believe this will make Sec. 1.1 less heavy and improve the readability of the presentation.
    3. I would suggest the authors include a (sub)section to provide formal descriptions for the algorithm considered as well as its pseudocode.
Questions for authors

Please see the weakness part above.

4 comments
AuthorsOpenReview ↗

Response to Reviewer ehzK (1/2)

Thank you for your careful and thorough review, for finding the motivation of practical interest, and for your detailed suggestions on the presentation. Following them, we have rewritten the introduction and Section 1.1, which now explain the terms where they first appear and state the main results as formulas, and we have added Algorithm 1. 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 mix-loss regret. The mix-loss regret bounds the regret of the predictions that the learner makes. A loss ℓ\ell is η\eta-mixable when the forecasts ft,yf_{t,y} of the experts, weighted by any distribution ptp_t, can always be combined into one prediction fˉt\bar f_t, a substitute, whose loss on every outcome is at most the mix loss mt=−η−1log⁡∑ypt,ye−ηℓt(y)m_t=-\eta^{-1}\log\sum_y p_{t,y}e^{-\eta\ell_t(y)}, where ℓt(y)\ell_t(y) is the loss of the forecast of expert yy on that outcome. With oto_t the outcome of round tt and LT(y)L_T(y) the cumulative loss of expert yy, it follows that

∑t≤Tℓ(fˉt,ot)−min⁡yLT(y)≤RT=∑t≤Tmt−min⁡yLT(y).\sum_{t\le T}\ell(\bar f_t,o_t)-\min_y L_T(y) \le R_T=\sum_{t\le T}m_t-\min_y L_T(y).

For the log loss at η=1\eta=1, with the mixture as the substitute, the two sides are equal, so RTR_T is then the ordinary regret of the predictions.

The vanilla regret that you write down compares the expected loss of following an expert drawn from ptp_t with the loss of the best expert, and by Jensen's inequality this expected loss is at least mtm_t in every round. A learner that follows a drawn expert cannot keep this regret below order T\sqrt T on every sequence of losses, even with two experts. This is the classical lower bound for linear losses (Cesa-Bianchi and Lugosi, 2006). Proposition 2(a) shows that it persists under the log loss when the learner predicts with the forecast of one sampled expert, even an expert drawn from exact exponential weights, because the expected loss of such a learner is linear in its distribution. Combining the forecasts is what makes bounded regret possible, and the mix-loss regret is the quantity that the aggregating algorithm of Vovk bounds in this setting. The revised paper defines mixability in the first paragraph of the introduction and displays the inequality above in Section 1.1.

The contribution and the computation. Follow-the-perturbed-leader in the oracle form of Kalai and Vempala (2005), run with Gumbel noise, and perturb-and-MAP already draw one Gumbel for every variable-value pair, ∑i∣Di∣\sum_i\lvert D_i\rvert in all, and compute each sample, one action, by maximizing the perturbed objective. At the step of exponential weights itself the regret of this procedure can grow linearly, and our paper determines by what factor that step must be divided to keep the mix-loss regret bounded. This factor is the temperature κ∗(M)\kappa^{\ast}(M), which equals the fractional certificate complexity FC(M)\mathrm{FC}(M) on product decision sets and lies between FC(M)\mathrm{FC}(M) and 2FC(M)2\mathrm{FC}(M) on every decision set.

A solver for the base model, the problem without the noise, maximizes over VV without enumerating it: the Hungarian algorithm for maximum-weight assignment, dynamic programming for the most probable configuration (MAP) of a tree-structured model, a minimum cut for MAP with submodular pairwise binary energies. A sample is the action vv that maximizes the perturbed objective θv+sM(v)+Ξ(v)\theta_v+s_{M(v)}+\Xi(v), the sum of its base score, the score of its output M(v)M(v) and its noise. In the paper the experts are these outputs, the part or the function of an action that the loss depends on, and the score of an output is −α-\alpha times its cumulative loss at the step α\alpha. The noise Ξ\Xi is a sum of unary terms, one for each variable, so the perturbed base score θv+Ξ(v)\theta_v+\Xi(v) stays in every class of problems closed under adding unary terms, and the solver still applies. When the loss is additive over the variables that it reads, the output score is a sum of unary terms as well, and one run of the solver gives a sample. For an arbitrary loss on the values of kk variables, the learner fixes these variables to each of their feasible joint values in turn, runs the solver with the same noise every time, and takes the best run after adding its output score, so a sample takes one run for each of these joint values. For a ferromagnetic Ising model on nn sites, for example, a sample takes one minimum cut for an additive loss and 2k2^k minimum cuts for an arbitrary loss on kk labels, while VV has 2n2^n labelings. Section 2.1 of the revision describes this computation.

AuthorsOpenReview ↗

Response to Reviewer ehzK (2/2)

Terminology. Each of the terms you list is now explained in the introduction or in Section 2.

  • An η\eta-mixable loss is defined in the first paragraph of the introduction, as in our answer on the mix-loss regret, and the log loss is 11-mixable, with the mixture as the substitute. The phrase "mixable regime" is gone, and the introduction speaks of bounded regret at a constant step against a mixable loss.
  • MAP stands for maximum a posteriori. A MAP solver maximizes the score over the configurations of a graphical model, for instance by dynamic programming on a tree or by a minimum cut.
  • In "fractional certificate complexity", a certificate at an action vv is a set CC of variables such that every action that agrees with vv on CC has the output of vv, so the values of vv on CC certify its output. For a Boolean function the least size of such a set, maximized over vv, is its certificate complexity, a standard measure of query complexity (Buhrman and de Wolf, 2002). "Fractional" refers, as you suggest, to weights ziz_i, which need not be integers, on the variables. A fractional certificate asks that every action with a different output differ from vv on variables of total weight at least one, and with weights in {0,1}\lbrace 0,1\rbrace it says that the variables of weight one form a certificate. This linear-programming relaxation of certificate complexity was introduced as fractional certificate complexity by Tal (2013) and by Gilmer, Saks and Srinivasan (2013). Section 2.3 explains the name in these terms.
  • Yes. By exponential weights at the step η\eta with the initial weights eθve^{\theta_v} we mean the rule that draws an action vv with probability proportional to eθv−ηL(v)e^{\theta_v-\eta L(v)}, where L(v)L(v) is its cumulative loss. With linear losses this is Hedge, and Exp3 is its bandit version. In our setting, where the loss is mixable and the learner sees the whole loss vector, the aggregating algorithm runs exponential weights over the experts and predicts with the substitute.
  • Follow-the-perturbed-leader with one Gumbel per variable-value pair and perturb-and-MAP are the same procedure in two literatures. In online learning it is follow-the-perturbed-leader in the oracle form of Kalai and Vempala, run with Gumbel noise. In structured prediction it is perturb-and-MAP (Papandreou and Yuille, 2011; Hazan and Jaakkola, 2012), which perturbs the energy of a graphical model and calls a MAP solver. The introduction says so and calls the procedure the mechanism.

Results as formulas, and the algorithm. Section 1.1 now states the problem formally and then lists the main results as formulas: the largest step η/κ∗(M)\eta/\kappa^{\ast}(M) that keeps the regret bounded (Proposition 1), the identity κ∗(M)=FC(M)\kappa^{\ast}(M)=\mathrm{FC}(M) on product decision sets (Theorem 1), the bounds FC(M)≤κ∗(M)≤2FC(M)\mathrm{FC}(M)\le\kappa^{\ast}(M)\le 2\mathrm{FC}(M) on every decision set (Theorems 1 and 2), and the step for two samples per round (the new Proposition 2). Table 1 gives the temperature in examples. Algorithm 1 in Section 2.2 gives the pseudocode of the learner that draws NtN_t samples of the mechanism in each round and predicts from the empirical distribution of their outputs, and by Proposition 2 two samples per round suffice for losses of bounded range. With the exact distribution of the output in place of the empirical one, it is the learner of Proposition 1.

We hope that these answers address your points and that the paper is now easier to follow, and we would be glad to discuss any of them further. Thank you again for the effort and expertise that you have devoted to our work in this review. Your suggestions on the presentation have made the paper clearer.

I thank the authors for their response. However, due to time constraints, I am unable to go through the entire response in the remaining time. During the post-rebuttal phase, I will finish reading the authors' response and participate in the discussion with the AC and the other reviewers.

We are sorry that our response came so late and left you little time to read it. We wanted to answer all the reviewers' questions with care, and doing so called for a new result and a substantial revision of the paper, which took us longer than we had hoped. Thank you for your reply and for taking the time to finish reading our response. We are grateful for your detailed suggestions on the presentation, which have made the paper clearer.

Reviewer_U1xROpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

While the exponential weighting scheme provides optimality in terms of achieving a constant regret (with respect to the time horizon) against a mixable loss, the method cannot be implemented generically as the action space becomes combinatorially large, since it has to be realized structure by structure. Follow-the-perturbed-leader (FTPL) with Gumbel noise is a computationally efficient detour: it injects independent noise into each variable-value pair and applies an existing solver once (the authors call this device the mechanism), instead of applying an independent Gumbel noise to each action. However, as FTPL applies independent Gumbel noise to each variable-value pair rather than to each action, the output distribution is no longer that of exponential weights (the Gumbel-max trick requires one independent Gumbel per action), so the constant-regret guarantee of exponential weights does not carry over directly.

In this paper, the authors introduce the temperature as the key quantity that determines the step at which FTPL achieves constant regret like the exponential weighting scheme. Specifically, instead of using the mixability constant of the loss as the learning rate, the authors prove that setting the learning rate to the mixability constant divided by the temperature makes FTPL achieve constant regret, and that this step is critical: any larger constant step can be made to incur linear regret.

Critical strengths
  • Irrespective of the technical details, the paper is clear and easy to follow. In particular, the detailed review of and comparison with previous works (e.g., follow-the-perturbed-leader, perturb-and-MAP, exponential weighting algorithms) make it clear why the exact derivation of the temperature is important, even without the technical details.

  • The exact characterization of the temperature in terms of the decision set VV and the readout MM alone further makes the theoretical findings concrete.

Critical weaknesses

(If possible,) I think adding experimental results that support the theoretical findings would help the audience understand their significance more clearly.

Questions for authors

See Critical Weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer U1xR

Thank you for your careful review and for your positive assessment of the paper. Following your suggestion, we have added numerical illustrations in the new Appendix E, with their code as supplementary material. We have also further improved the writing and the presentation of the paper. The numbered statements of the submission are unchanged in content, and new and substantively changed text is marked in red in the revised paper. The proposition on the cube readout is now Proposition 3, after the new Proposition 2 on predictions from samples.

Numerical illustrations. Appendix E illustrates three results, all with η=1\eta=1. For the first two we compute the output distributions in closed form or by numerical integration, without sampling, and for the third we simulate the learner that predicts from samples.

The first example shows the critical step. When the loss reads the values of kk variables, the theory says that η/k\eta/k is the largest constant step at which the regret stays bounded. On binary variables, the two-round cycle of losses from the proof of Proposition 1 gives bounded regret at every step up to η/k\eta/k, for kk from 11 to 1616, and linear regret already at 1.05η/k1.05\eta/k, the next step of the grid, so the change appears where the theory places it. On Ising chains with interactions between neighboring sites, three sites with the loss on all three labels and four sites with the loss on the two middle labels, a two-round cycle of losses makes the regret of the learner that runs the mechanism grow at a rate of 0.0100.010 to 0.1140.114 per round at the step η\eta of exponential weights, while at the step η/k\eta/k the regret never exceeds 3.53.5 (Figure E.1). On these models the step of exponential weights thus leads to linear regret, and the step divided by kk does not.

The second example shows how close the regret comes to the bound of Proposition 1(a). On the cube readout of Proposition 3, at the critical step, an adversary that charges the same loss vector in every round already forces regret whose limit lies between 0.840.84 and 0.930.93 times this bound, for each of the eight values of nn in Table E.1, from 33 to 3232. On this readout the bound is therefore within a factor of 1.21.2 of the regret that an adversary can force.

The third example concerns a learner that cannot compute the output distribution and predicts from samples of the mechanism. In the new Proposition 2 we prove that, for losses of bounded range, two samples per round keep its expected regret bounded at a smaller constant step, that more samples allow a step closer to the critical one, and that one sample per round is not enough at any step. Appendix E simulates this learner on the one-hot encoding of eight experts, where the mechanism is follow-the-perturbed-leader with logistic noise and has critical step η\eta. With two samples at the step 2η/52\eta/5 of Proposition 2(b), and with 201201 samples at the step 0.90η0.90\eta, which Proposition 2(c) allows, the mean regret stays below the bound of Proposition 2 in both cases (Figure E.2). With one sample per round it grows, even at the step η/20\eta/20. Two samples per round are thus enough in these runs and one is not, as Proposition 2 states.

Related work. The comparison with exponential weights, follow-the-perturbed-leader and perturb-and-MAP that you found helpful is now in the first two paragraphs of the introduction. The detailed discussion of related work is Appendix F, and the paragraph "Related work" at the end of Section 1.1 keeps the closest connections.

We hope that these illustrations make the significance of the results clearer, and we would be glad to answer any further questions. Thank you again for the effort and expertise that you have devoted to our work in this review. Your suggestion has made it a better paper.

Reviewer_hxisOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper study a mechanism that sample certain r.v. from a Gumble distribution and that induces a maximization problem then being Optimized. The sample r.v. can be thought of as a relaxed version of the true exact random variables one wants to sample, but it is computationally infeasible. Unfortunately that relaxation leads to inexactness in the distribution which the paper wants to account for.

They specifically look for a measure that is directly related to the use in regret bound, and they analyze how this relaxation affects mix-loss. The underlying assumption is that the learner optimizes the mix-loss, but the analysis is also useful if one wishes to obtain regret with fixed horizon - though, the unmixed case has been discussed in previous literature. Overall the result is solid and has technical contribution.

The paper does a poor job of motivating and presenting the problem. While it discusses previous work, it provides little insight into the technical barriers or the motivation for the improvements. For example, the paragraph explaining that, for mixable losses, "the noise on the variables has never been priced" is particularly unclear. It abruptly shifts from finite-horizon issues to mixable losses, without explaining the connection. The subsequent claim that this is due to the absence of a closed-form solution is equally vague. As this paragraph appears central to motivating the paper, its lack of clarity is particularly problematic.

The following paragraph introduces the main question, but again fails to motivate it clearly. The "temperature" is first defined as the factor by which the exponential weights step size must be divided to keep regret bounded, but is then defined through the mixability inequality, two allegedly different definitions. Although the paper eventually establishes this connection, the introduction does not. Thus, the paper moves from a poorly motivated problem to poorly motivated definitions. Our result paragraph also is confusing: First two paragraph reiterate the setting, third paragraph jumps to reiterate kappa and its hard to understand what is the main result.

On a technical perspective, I think the paper, because it deals with mixed loss should account to the error from sampling. The paper correctly state that it prices a single sampling, but with a mixed-loss there is a further error from the approximation, which should be accounted for, and the overall price should include the number of samples needed inorder to obtain the constant regret the paper aims for.

Critical strengths

As written in the review

Critical weaknesses

As written in the review

Questions for authors

as written in the review.

4 comments
AuthorsOpenReview ↗

Response to Reviewer hxis (1/2)

Thank you for your careful review, for your assessment that the result is solid and makes a technical contribution, and for your point on sampling, which led to a new result. We agree that the submitted introduction did not motivate the problem and its definitions 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, and following your technical point we have added Proposition 2 on predictions from samples. The numbered statements of the submission are unchanged in content, and new and substantively changed text is marked in red in the revised paper.

From finite horizons to mixable losses. The revised introduction (page 2) now explains this connection. The analyses of follow-the-perturbed-leader for linear losses obtain regret of order T\sqrt T by scaling the perturbation with the horizon or with the observed losses, so they do not address a constant step. Against a mixable loss the aggregating algorithm keeps the regret bounded at every horizon, and it does so with a constant step, thanks to one property of the log-sum-exp potential of exponential weights: at each update the potential falls by exactly the step times the mix loss of the round, and summing these falls bounds the regret. The potential of the mechanism is an expected maximum over the actions, and whether it falls by at least this much at every update depends on the step. At a step where it falls by less at some state of the learner, an adversary steers the learner to that state and makes the regret grow linearly with a repeated cycle of losses.

The technical barrier is that this expected maximum has no closed form in general, so we work directly with the Gumbel variables. To show that the potential falls by at least the step times the mix loss, we condition on the noise of all variables but one. Given that noise the mechanism is a softmax over the values of the remaining variable, so the comparison with the log-sum-exp potential can be made one variable at a time, and the weights of a fractional certificate, one weight per variable, combine these comparisons.

A single definition of the temperature. What read as two definitions are a definition and a proposition about it, and the revised introduction gives them in this order. The temperature κ∗(M)\kappa^{\ast}(M) is defined (Definition 2, unchanged from the submission) as the least κ\kappa for which, at the step η/κ\eta/\kappa, every update lowers the potential by at least the step times the mix loss of the round, whatever the losses and whatever the base score, the learner's model of the actions. Proposition 1 then proves that the temperature is exactly the factor by which the step of exponential weights must be divided to keep the regret bounded. At every step α≤η/κ∗(M)\alpha\le\eta/\kappa^{\ast}(M) the regret is at most Γ/α\Gamma/\alpha at every horizon, where Γ\Gamma depends on the base score but not on the losses, and above this step some base score and some loss sequence make the regret grow linearly. The introduction states this result before Section 1.1, and Section 1.1 states the game formally and then gives the main results as formulas, items (i) to (iv). The main result is that on every product decision set the temperature equals the fractional certificate complexity FC(M)\mathrm{FC}(M) of the readout MM, the map from an action to what the loss depends on, so the largest step that keeps the regret bounded is η/FC(M)\eta/\mathrm{FC}(M).

AuthorsOpenReview ↗

Response to Reviewer hxis (2/2)

The number of samples. Two samples per round suffice, and two is the minimum. A learner that cannot compute the output distribution sees it through samples, and by the convexity of −log⁡-\log the expected mix loss of the empirical distribution is at least the exact mix loss, as you point out. In Proposition 2 (Section 2.2) we determine how many samples per round keep the expected regret bounded. Let the losses of each round have range at most BB and be fixed before the samples of the round are drawn, and let the learner weight the forecasts by the empirical distribution of its samples and predict with the substitute, the single prediction that mixability provides (Algorithm 1). With two samples per round, on every decision set, the step α=2min⁡{η,1/B}/(5κ∗(M))\alpha=2\min\lbrace\eta,1/B\rbrace/(5\kappa^{\ast}(M)) keeps the expected regret at most Γ/α\Gamma/\alpha at every horizon, the bound of Proposition 1. This step is two fifths of η/κ∗(M)\eta/\kappa^{\ast}(M) when ηB≤1\eta B\le 1, so the regret bound is then larger by a factor of 52\frac52 than with the exact distribution. With N>e2ηBN\gt e^{2\eta B} samples per round the step (1−e2ηB/N)η/κ∗(M)(1-e^{2\eta B}/N)\eta/\kappa^{\ast}(M) suffices, and it approaches η/κ∗(M)\eta/\kappa^{\ast}(M) as NN grows. Each sample is one call to an optimizer for the perturbed objective.

The proof rests on one comparison in each round. Write XX for the loss of one sample, and call −r−1log⁡Ee−rX-r^{-1}\log\mathbb{E}e^{-rX} the mix loss at the rate rr, so that the mix loss of the game is the one at the rate η\eta. At a step α≤η/κ∗(M)\alpha\le\eta/\kappa^{\ast}(M), the inequality that defines the temperature, applied at the rate r=κ∗(M)α≤ηr=\kappa^{\ast}(M)\alpha\le\eta in place of η\eta, makes the potential fall by at least α\alpha times the mix loss at the rate rr. Summed as in Proposition 1, these falls bound the expected regret by Γ/α\Gamma/\alpha once the learner's expected mix loss is at most this mix loss in every round, and a step below η/κ∗(M)\eta/\kappa^{\ast}(M) leaves room for this comparison, since a mix loss grows as its rate falls. To second order, the mix loss of a distribution at a rate lies below its mean by half the rate times its variance. This gives EX−r2VarX\mathbb{E}X-\frac{r}{2}\mathrm{Var}X for the exact distribution at the rate rr and, since the empirical distribution of two independent samples has variance 12VarX\frac12\mathrm{Var}X in expectation, EX−η4VarX\mathbb{E}X-\frac{\eta}{4}\mathrm{Var}X in expectation for the learner, so the comparison goes the right way when r≤η/2r\le\eta/2. Lowering the rate of the learner's mix loss from η\eta to λ=min⁡{η,1/B}\lambda=\min\lbrace\eta,1/B\rbrace can only raise it, and the step of Proposition 2(b) gives r≤2λ5r\le\frac{2\lambda}{5}, below λ2\frac{\lambda}{2}. Since λB≤1\lambda B\le 1, the higher-order terms change the two second-order amounts, λ4VarX\frac{\lambda}{4}\mathrm{Var}X for the learner and at most λ5VarX\frac{\lambda}{5}\mathrm{Var}X for the mix loss at the rate rr, by factors of at least 1516\frac{15}{16} and at most 1513\frac{15}{13}. The learner is thus charged in expectation at most EX−1564λVarX\mathbb{E}X-\frac{15}{64}\lambda\mathrm{Var}X, the mix loss at the rate rr is at least EX−313λVarX\mathbb{E}X-\frac{3}{13}\lambda\mathrm{Var}X, and 313<1564\frac{3}{13}\lt\frac{15}{64} (Appendix C).

Two is the minimum because with one sample per round the empirical distribution is a point mass. The learner is then charged the loss of the sampled expert, and its expected loss is linear in its distribution, as in the expert game with linear losses. So at every step and every horizon TT some loss sequence gives expected regret at least BT/8B\sqrt{T/8}. This holds for every learner that weights the forecasts by a single sample, whatever distribution the sample comes from, so also for exact exponential weights implemented by sampling.

For the log loss at η=1\eta=1, the range of a round's losses is the logarithm of the ratio between the largest and the smallest probability that the experts give to the realized outcome. When every such probability is at least ε∈(0,1)\varepsilon\in(0,1), Proposition 2(b) with B=log⁡(1/ε)B=\log(1/\varepsilon) and its largest step gives expected regret at most 52κ∗(M)Γmax⁡{1,log⁡(1/ε)}\frac52\kappa^{\ast}(M)\Gamma\max\lbrace 1,\log(1/\varepsilon)\rbrace.

Figure E.2 simulates the mechanism on the one-hot encoding of eight experts, where it is follow-the-perturbed-leader with logistic noise. With two samples at the step 2η/52\eta/5 of Proposition 2(b), and with 201201 samples at the step 0.90η0.90\eta, which Proposition 2(c) allows, the mean regret stays below its bound Γ/α\Gamma/\alpha in both cases. With one sample per round it grows, even at the step η/20\eta/20.

We hope that the revised introduction and Proposition 2 address your concerns, and we would be glad to discuss any point further. Thank you again for the effort and expertise that you have devoted to our work in this review. Your point on sampling and your comments on the introduction have made the paper stronger.

Thank you for addressing my concerns. I will further read proposition 2 as well as the other revisions, and will reassess my score at the reviewer-ac discussion period.

We are sorry that our response came so late. We wanted to answer all the reviewers' questions with care, and doing so called for a new result and a substantial revision of the paper, which took us longer than we had hoped. Thank you for your reply and for taking the time to read the revisions. We are grateful for your point on sampling, which led to Proposition 2.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the Revision

We thank the reviewers for their careful reading and their questions. We have uploaded a revised paper, with new and substantively changed text marked in red, together with the code for the numerical illustrations as supplementary material. At the request of several reviewers, we have rewritten the introduction and Section 1.1 to make the paper easier to follow, and we have added a result on predictions from samples, pseudocode of the learner and numerical illustrations. The numbered statements of the submission are unchanged in content. The new result on samples is Proposition 2, so the former Proposition 2 is now Proposition 3.

Presentation (Reviewers HT4u, hxis and ehzK). The introduction now starts from bounded regret against a mixable loss, which it defines, and from the two methods that share one procedure, follow-the-perturbed-leader with Gumbel noise in online learning and perturb-and-MAP in structured prediction. Both draw one Gumbel for every variable-value pair and make one call to an optimizer per sample, and we call this procedure the mechanism. The introduction then shows on an Ising model why the learning rate of the mechanism matters. For a loss on the joint labels of k≥2k\ge 2 sites, whatever the energy, the step η\eta of exponential weights can make the regret grow linearly, and so can every step above η/k\eta/k, while the step η/k\eta/k keeps it bounded at every horizon (the new Corollary C.2). Next it explains that this is a question about constant steps, which the analyses of the perturbed leader for linear losses do not address. After this it states the question of the paper, by what factor the step of exponential weights must be divided for the regret of the mechanism to stay bounded. By Proposition 1 this factor is exactly the temperature, which has a single definition (Definition 2) and replaces the word "price" that Reviewer HT4u asked about. On every product decision set the temperature equals the fractional certificate complexity of what the loss depends on (Theorem 1).

Section 1.1 now opens with the formal problem, that is, the mechanism, the game and the regret, and it displays the inequality by which the mix-loss regret bounds the regret of the predictions. It then gives the main results as formulas, with a table of the temperature in examples. To make room, the discussion of related work has moved to Appendix F, and Section 1.1 closes with a short paragraph on related work. The terms that Reviewer ehzK lists are explained in the introduction and in Section 2, where Algorithm 1 gives the pseudocode of the learner.

Predictions from samples (Reviewer hxis). At the request of Reviewer hxis, the new Proposition 2 in Section 2.2 treats a learner that only draws samples of the mechanism. For losses of bounded range, two samples per round suffice to keep its expected regret bounded at a smaller constant step, and two is the minimum.

Computation (Reviewer ehzK). Section 2.1 now explains how one sample is computed. The noise is a sum of one term per variable, so a solver for the base model, such as the Hungarian algorithm, dynamic programming on a tree or a minimum cut, still applies after the noise is added, and a sample takes one run of this solver when the loss is additive over the variables that it reads.

Numerical illustrations (Reviewer U1xR). The new Appendix E illustrates three results. In the first, the regret changes from bounded to linear at the step η/k\eta/k, as the theory says. In the second, on the cube readout of Proposition 3, the bound of Proposition 1(a) is within a factor of 1.21.2 of the regret that an adversary can force. In the third, a simulation, the learner that predicts from samples keeps its mean regret below the bound of Proposition 2 with two samples per round, while with one sample its regret grows.

The remaining changes keep the rest of the paper consistent with these revisions or adjust wording to improve clarity.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.