Venue: NeurIPS 2022 Conference

Reviews:

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: This work studies regret bounds for online convex optimization that interpolates between stochastic i.i.d. and fully adversarial losses. The author leverages the smoothness of the expected loss to reduce the dependence of the regret bound on the maximal gradient norm to the cumulative stochastic variance and the adversarial variation.
strengths_and_weaknesses: Strengths:
1. This work provides upper bound and tight lower bound up to additive constants of regret bounds for (strongly) convex smooth function.

2. Such results can be extended to the intermediate case between stochastic iid to fully adversary.


Weaknesses:
1. The writing needs to be improved. It’s hard to find the definition of some math parameters. For example, there’s no context regarding $D, \kappa, \sigma_{max}, \Sigma_{max}$ when introducing the bound in line 47-49. When comparing with the literature, it’d be helpful to list the concrete differences. For example, line 93 mentioned the main theorem under stronger assumptions than previous literature without mentioning what’s the assumption in this work versus the literature. In Remark 4 line 212, the author does not give any formal definition of $g_t$ and $M_t$.

2. The author introduces the smoothness of the expected loss function as one additional assumption besides bounded gradient. To the best of my knowledge, there exists expected-smoothness assumption [1] that also try to leverage the smoothness of the function, yet can replace the bounded gradient and bounded variance assumption. I’m wondering whether the author considers other methods to try to eliminate some of the assumptions.


[1] Gower, Robert Mansel, et al. "SGD: General analysis and improved rates." International Conference on Machine Learning. PMLR, 2019.






questions: 1. For theorem 5, can you elaborate more on why you specifically choose $\nu=LD^2+DG^2$ and $\nu=2DG$ after deriving eq(3)?

2. Why in theorem 6 and theorem 8 we need $\bar\sigma_T\geq\sigma$ and $\bar\Sigma_T\geq \Sigma$ since there’s no $\sigma$ and $\Sigma$ show up in the bound?

3. It’d be helpful to also provide the lower bound for adversarially corrupted i.i.d. model to see whether the dependence on C is tight. Also, does it natural to bound the sum of perturbation by $C$, instead of per sample perturbation $\max_{t\in T}\max_{x\in X}\|\nabla c_t(x)\|\leq C$? Since the latter case might provide an $O(\sqrt{T})$ bound. It’d also be helpful if we can have a lower bound for Random Order Models.

4. Some typo: in the appendix proof of theorem 5, I think eq(9) the constant before $D^2G^2/\mu$ should be 6 instead of 4. line 569-571 some of the summation is not consistent, which should be from 1 to $T-1$. It seems a missing constant in front of $G$ in the equation after line 569.



##############After reading the rebuttal################
I thank the author for the detailed response to my question. Most of my concerns have been addressed. I therefore raise my score to 6 for now.
limitations: Yes.
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: The paper gives tight results on optimization in a regime between stochastic and adversarial data, interpolating known results in these extremes. Using smoothness of the expected loss, the paper establishes convergence rates depending on stochastic variance and adversarial variation of the gradients via a unifying analysis of OFTRL. The authors discuss applications of the result in the intermediate regime, including adversarial corruption and in the random order model. 

strengths_and_weaknesses: Strengths:
- The paper is very clearly written and discusses relevant works.
- In terms of technical novelty, this work proposes a new analysis of optimistic FTRL that takes into account a negative term not explicitly stated in classical analysis. 
- The regret analysis is unified for the adversarial and stochastic cases, and the regret bounds are not only tight up to constants, but also match known results in the extreme cases. 

Weaknesses:
- See questions.

Minor Typos:
- Page 7, $\Sigma_{[1:T]}^2 \le G\sqrt{2T}$, should there be a square on the lhs?
- Appendix Page 16, Eq. (9), should it be $\frac{6D^2G^2}{\nu}$?

questions: - The regret in the corruption model is against the corrupted data. Could the authors comment on scenarios where this makes sense? 
- Could the authors give some examples of problems where the results for random order models can be applied?

limitations: Yes.
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: Examines a range of stochastic optimization settings from IID to Adversarial. 
Provides regret bounds for optimistic FTRL in terms of a combination "within round variances" and "between round variances", the former representing the stochastic part of the gradients and the latter representing the adversarial part, recovering good known bounds for both of the pure iid and pure adversarial cases if they prevail, and interpolating "naturally" between these cases. 
Both in the convex and strongly convex cases.
Lower bounds that match time-dependent term.




 
strengths_and_weaknesses: Strengths:
- Interesting, novel setting. 
- Results are intuitive and interpretable in the context of related work.
- "best of both worlds" gets optimal rates in multiple settings without knowledge of the setting to tune the algorithm.
- the examples provided on pgs 4/5 make it clear that this these results are useful and flexible as they can be applied to a wide range of settings that are of practical relevance.
- proofs seem to me to be correct.
- topic of "between iid and adversarial" is timely and interesting

Weaknesses:
- The proof techniques are not novel. The novelty of the results is essentially due to the setting that was introduced and application of the corresponding definitions the authors introduced. However, this is not a big detractor, in my opinion, since the results themselves are interesting regardless. 

questions: - unclear why lag-1 variability of the gradient is the right notion of "adversarial". if the player has access to f( . , \xi_t) for all past t, for example, then one could predict with the average of the history instead of the lag-1 predictor. does this lead to a different upper/lower bound? is there a way in which not using all the history is better? I imagine one could do better using the full history.
limitations: some discussion of other settings between iid and adversarial that would not be covered, or would not achieve their respective optimal bounds using these methods would be useful to provide context to the reader.
review_title: null

Meta-review: metareview: While the reviewers had some concerns that were raised in the reviews, overall the reviewers seem to be leaning towards an accept. The setting/motivation is a nice one and the result is clean. I agree with the reviewers in that the paper should be accepted for publication.
confidence: Certain
Decision: Accept