Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies algorithms for the online prediction with experts problem in the multi-scale setup where the losses of the different experts have varying (and unknown) scale parameters. Within this setup, the work looks for an algorithm which is adaptive to the simpler stochastic (or lucky) case. The solution is an algorithm, called MUSCADA, and its regret analysis in both the worst-case and stochastic setup. The paper also presents an optimistic version of this and applies the resulting algorithm to zero-sum multiscale games.
strengths_and_weaknesses: The paper proposes a simple algorithm based on Follow the Regularized Leader approach and analyses its regret bound. The overall algorithm and its intuition is well explained as are the problem setup. The paper even instantiates the results for a simple example, that of single scale uniform prior, to provide some intuition about the algorithm.

In terms of techniques, the paper does not bring out the challenge and novelty which prohibit existing techniques from working for this particular setup. For instance, would a simple application of the Chen et al 2021 to Bubeck et al.'s 2019 algorithm work or is something more nuanced required here?
questions: - Is there a lower bound for the algorithm proposed by Bubeck et al. 2019 under the Massart's easiness condition which shows that it cannot obtain the constant regret bound?
- What are some example applications where multiscale zero-sum games and the techniques proposed in this paper would be useful?
limitations: The paper is a theoretical work and does not have potential social negative impact. It clearly mentions the assumptions under which the results hold and also provides several directions for future work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper extends online prediction with expert advice to a multiscale setting, where the experts' losses have different ranges. The proposed MUSCADA algorithm simultaneously guarantees the minimax regret that grows with the scale of the best expert and has a constant expected pseudo regret in the stochastic lucky case.  MUSCADA refined the Follow The Regularized Leader (FTRL) with a multiscale entropy regularizer, which has a second-order variance-like adaptation. Regret bounds for MUSCADA under two tuning schemes are further provided. Moreover, the authors build an optimistic version of MUSCADA and apply it to solve multiscale zero-sum games, then further experimentally demonstrate its superiority compared to the single-scale algorithms. Finally, the results are discussed with Freund's 2016 open problem.
strengths_and_weaknesses: ### Strengths

The proposed algorithm, tuning schemes, and theoretical results seem interesting and novel. The algorithm does not need knowledge of the game's length in advance and does not need to store any doubling trick. Stochastic luckiness is studied with quantified data easiness. And the constant regret for easy data is witnessed in the experiments on synthetic data.
However, I am not an expert in the related domain, and I did not carefully check the proof, so I cannot precisely assess the quality and significance of this work. 

### Weaknesses

1. The structure of the paper causes some difficulties in understanding

Section 1.1 presents the results before the introduction of MUSCADA with some notations and concepts unknown. 

2. The experiment setting is unclear, and some important descriptions are put in Appendix.


questions: I suggest the authors modify the paper structure for better presentation. 
limitations: Yes, the limitations are discussed in the open problem section.
review_title: null

final_score: 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.
review_content: summary: The paper considers the setting of prediction with expert advice where the (known) loss ranges for each expert ($\sigma_k$ for expert $k$) may vary drastically (the “multi-scale” setting). They improve existing regret bounds that currently have the optimal dependence on $\sigma_k$ by replacing dependence on $t$ with a novel variance-like term $v_k$, which they show leads to constant regret in the multi-scale stochastic-with-a-gap setting. Until now, constant regret was only known in the single-scale case; the multi-scale case resulted in regret of size $\log(t)$. They also extend this to an optimistic variant, and apply this in the now-standard way to the game-matrix setting.
strengths_and_weaknesses: Overall, the paper is very clearly written, provides a well-defined and useful contribution that I think will be valued in the literature, and does so using some new algorithmic and technical tools that can hopefully be reused. I read the proofs at a high level and did not find any issues. I have no major concerns, just a few questions for the authors that may help place this work in the literature slightly more clearly and provide a picture of what the follow-up works might be. 
questions: 1. If you pick an expert to compete against, the $\sigma_k$’s do not need to be known in advance. Can the authors confirm that there are *no* multi-scale results that similarly do not require $\sigma_k$ knowledge, and can they comment on whether relaxing the assumption of their prior knowledge seems possible?

2. Can the authors include in their simulations a comparison with multi-scale dependence on quantities that become small in in stochastic settings, such as the adaptive variants of PROD? This would be useful to see that they do not obtain multi-scale constant regret in the stochastic setting, and it is not just the fact that we don’t know how to prove they achieve this because of the limitations of Bernstein’s inequality.

3. The author’s arguments seem to rely rather heavily depend on limiting statements in $t$. It would be good if they can state some finite-time bounds (with additive errors that may be bounded as $t$ gets large) to allow for comparison with other finite time regret bounds for quantile regret, even if the main informal theorem statement is asymptotic in $t$ to highlight the salient terms.

limitations: I see no negative societal impacts of this theoretical work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In multiscale online learning, the range of losses differs from an expert to another. People aims at designing algorithms with regret depending on the scale of the best experts instead of the maximum scaling. Several algorithms have already be proposed in the literature with worst-case analysis. However, none of them achieves a constant regret under Massart's condition. The authors introduce a new algorithm called Muscada which entails similar guarantees as previous algorithms in the worst case but also achieves constant regret in benign statistical case (Massart's condition). They also analyze an optimistic version of their algorithm and conduct numerical experiments.
strengths_and_weaknesses: This work follows the line of research of FTRL with multiscale entropy regularization. The main contribution is to refine this method with corrections terms added to the losses and to give an analysis under Massart's condition. But it is not limited to this key result and explore several aspects of the proposed method with an analysis of several tunings, an optimistic version, a discussion with Freund's open problem...
The paper is well written. Theorems and proofs are clear and precise.
I checked only a tiny fraction of the proofs and arguments seems to add up.
The contribution is significant and the techniques developed are interesting. It is a nice contribution to the multiscale literature.
questions: Would be interesting to compare numerically Muscada against FTRL with multiscale entropy (without your refinement).
Do you observe non-constant regret for other algorithms under Massart distribution ?

Typos:
l.232: incurrs -> incurs 
l'281 an refinement -> a refinement
limitations: As discussed at the end of the paper, the main limitation is that it does not extend to countable may experts but it offers a good opportunity to future work.
review_title: null

Meta-review: metareview: The reviewers were generally happy with this paper. There were some comments about better experiments and one comment about properly comparing this work to Bubeck et al (e.g. difference in rates and comparative advantages). I encourage the authors to better explain this related work and also incorporate some of the clarifying discussions with reviewers in the final version of the paper.
confidence: Certain
Decision: Accept