Summary
This paper focuses on the contextual sequential probability assignments, and specifically examines cases where the contexts $x_{1:T}$ are generated by $\sigma$-smooth adversaries as introduced in [Haghtalab et al. 2021], and where the labels $y_{1:T}$ are adversarially generated. The primary findings pertain to the minimax regrets under the logarithmic loss, as compared to a generic set of experts $\mathcal{F}$. More specifically, the paper demonstrates the following:
1. If the class $\mathcal{F}$ possesses a scale-sensitive VC-dimension of order $\epsilon^{-p}$, then the information-theoretical minimax regret grows as $T^{p/(p+1)}\cdot \text{poly}\log(T/\sigma)$, which is tight up to polylogarithmic factors.
2. An efficient algorithm exists, given an MLE oracle, that attains regret of order $T^{2/(2+w)}\sqrt{1/\sigma}$, provided the Rademacher complexity of $\mathcal{F}$ is of order $T^{-w}$. For the VC-class, specifically where $w=1/2$, this algorithm yields a regret bound of order $T^{4/5}$.
3. For the VC-class, it demonstrates that the information-theoretical regret is of the order $d\log(T/\sigma)$ up to a constant factor (the same result was also found in concurrent work [Wu et al. 2023]).
The principal contribution of this paper that distinguishes it from previous work on contextual sequential probability assignments is the introduction of an oracle-efficient algorithm that achieves sublinear regret. Although the primary techniques are rooted in the FTPL (Follow The Perturbed Leader) framework as outlined in [Haghtalab et al. 2022], this unique contribution sets a new precedent in this line of research.
Strengths
The primary strength of this work lies in the oracle-efficient algorithm, which presents the first known instance of computationally efficient sublinear regrets under log-loss for general non-parametric classes, albeit using an MLE oracle. This is likely to inspire further research in this field.
Weaknesses
The main weakness is the novelty of the techniques used in this paper. From a purely technical standpoint, Algorithm 1 and its analysis seem to merely mimic those used in [Haghtalab et al. 2022]. In fact, there are many places in the proof that appear to be verbatim copied!
There are also some presentation and technical issues, which I outline below:
- There are many places where the index of summation is $i$ but the summand is written as $s_t$, for instance, in Lemma 4.2. I suggest the authors conduct a thorough proofreading, including the appendix, to correct issues like this;
- I recommend that the authors include a proof for Corollary 4.1.1. It's unclear to me how Theorem 4.1 implies this bound for certain values of $n$, $\alpha$, and $m$;
- The authors claim that a $T^{3/4}$ bound could be achieved for an alternative oracle. This is not clear to me at all. Are you refering to the Theorem 7 of [Block et al., 2022]? If so, it should be properly cited and clearly explained by what you mean "mixed objective function";
- In line 636 (appendix), it appears that Lemma 3.3 from [Haghtalab et al., 2021] requires $\epsilon> \frac{\sigma}{T\log T}$? The choice of $\epsilon=\frac{\sigma}{T^2}$ does not align with the condition stated in that Lemma. I believe a stronger concentration result, such as Lemma 21 from [Wu et al., 2023], would be required in this context;
- In the proof of Lemma 4.4, presented in Appendix G, you assert that the distributions $P, Q$ are solely dependent on the ensembles $\\{n_0(x),n_1(x)\\}$. However, I contend that this is not a self-evident fact. It is essential, at the very least, to posit that your OPT oracle is permutation invariant with respect to the input sample sequence. This assumption, it should be noted, does not necessarily hold for all optimization methods; stochastic gradient descent, for example, may not exhibit this property.
These are the primary reasons I give a "weak accept".
Questions
I have the following questions for the authors:
1. It seems that your FTPL algorithm relies on an exact ERM oracle. I'm curious, how would the performance or operation of the algorithm change if the oracle was only approximately optimal?
2. Is there any computational lower bounds as in [Haghtalab et al. 2022] that can be proved for the log-loss?
3. Your bound in Theorem 4.1 seems to rely solely on the Rademacher complexity. Does this suggest that your analysis isn't capable of achieving a $\log(T)$ dependency for the VC-class? For instance, consider the linear function $|\langle w,x\rangle|$ with $w,x$ in a unit ball (of a Hilbert space). This class admits a $1/\sqrt{T}$ Rademacher complexity, but it's known that the information theoretical lower bound is $T^{2/3}$.
4. Is it possible to achieve better dependency on $T$ with your FTPL algorithm if the contexts are generated from an i.i.d. process (i.e., with $\sigma=1$)?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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.
Limitations
No issue with negative societal impact.