Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The authors study online linear optimization in the case of known strongly convex constraints sets. They show that the simple method of online subgradient descent, which is known to achieve $O(\sqrt{N})$ regret in the adversarial case, also achieves $O(\log(N))$ regret in the i.i.d. case. This result is more elegant than and slightly improves upon existing results in the strongly convex case.
main_review: Strengths:
- The paper improves upon the state of the art results for online linear optimization in the strongly convex case
- The result is elegant as it pertains to the basic online subgradient descent method instead of a more complicated algorithm
- Online linear optimization is a significant problem

Weaknesses:
- My main concern is about the significance of the results given that the paper entirely focuses on the specific case of strongly convex domains. I'm not sure that the authors do enough to justify a paper that focuses entirely on this special case, and therefore I find the significance to be largely limited
- Additionally, although it is nice that the results pertain to a simpler and more popular algorithm than prior results, the complexity bounds only improve slightly by a factor of $\sqrt{log{N}}$ in the adversarial case.  
- The writing of the paper can be improved substantially, both for clarity and language/grammar etc.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers the problem of online linear optimization under a full information feedback setting on a strongly convex domain. In this setting, the authors show that the classical lazy subgradient method is optimal both in the adversarial and stochastic settings.  In particular, the authors show that for the same choice of hyper-parameters, the lazy sub-gradient method achieves O(\sqrt{N}) regret in the adversarial setting and O(log{N}) regret in the stochastic setting. To show this result, the authors have to do a more nuanced analysis of the algorithm (that relies on differential geometry methods) than existing works. 


main_review: Although the problem setting is very narrow, I feel the result is interesting. Unlike past works which come up with complex algorithms, the paper shows that a simple lazy sub-gradient method works well both in adversarial and stochastic settings.

I found the paper to be a little bit terse. In particular, I'd appreciate a little bit more insights into proof techniques (maybe a high-level proof sketch before jumping into the proof of Theorem 1).  Also, I think a more thorough literature review needs to be performed (more on this below).

Here are my main comments on the paper:
1)  Regarding the experiments on the lazy subgradient method presented in Figures 1,2: similar to Figure 2b, can the authors try to fit a curve through the points (fit both D1*sqrt{n}+C1 and D2*log(n+1)+C2) and see which is a better fit? Do the experiments support the theory that the regret scales with log{N} in the stochastic setting?

2) Regarding the greedy subgradient method: in line 244, the authors mention that the worst-case regret of this technique could be Omega(sqrt{N}) in the stochastic setting. This seems a bit counterintuitive to me. The greedy subgradient method is nothing but the projected stochastic gradient descent (SGD) method.  Projected SGD is a well-studied problem. Many works have shown that it converges at O(1/N) rate to an optimum for strongly convex losses (for example, see the works of Francis Bach). Given this, I find it a little bit hard to believe that for linear losses on strongly convex domains, SGD only converges at O(1/sqrt{N}) rate to an optimum. Can the authors explain this?

3) I believe a more thorough literature review needs to be performed. One line of work that is missed is the optimistic online learning algorithms of [1]. Look at section 4 in [1] where the algorithms learn to adapt to the adversary. Can these algorithms not be made to adjust to the stochastic setting and achieve O(log{N}) regret?  
Given the relation between lazy subgradient method and SGD, some relevant literature on SGD should also be cited.

4) As mentioned before, the setting considered in this paper is a bit narrow. So it would be good to see if the results can be generalized. Can the results be generalized to general convex functions on strongly convex domains? Will the same results hold for lazy Online Mirror Descent? 

Finally, please avoid revealing the funding sources in the future. This defeats the purpose of the double-blind review process.


[1] Rakhlin, A. and Sridharan, K., 2013, June. Online learning with predictable sequences. In Conference on Learning Theory (pp. 993-1019). PMLR.
limitations_and_societal_impact: the authors adequately addressed the potential negative societal impact of their work
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors study online linear optimization and show that the Lazy Online Subgradient Algorithm is *universal* on strongly convex domains: it simultaneously achieves the optimal $O(\sqrt T)$ regret when the costs are adversarial and the optimal $O(\log T)$ regret when the costs are stochastic. This result is a clear improvement over previous work of Huang et al, who described a more complex algorithm and didn't achieve the optimal rates. The proof is based on an intricate analysis, drawing from differential geometry, of the points selected by the algorithm, and in particular, how much of each step affects regret against the minimizer $x^*$ and how much is orthogonal to the direction $x_i - x^*$ and doesn't affect regret. This technique may be of interest to the broader ML community.
main_review: This is a neat paper, and is especially cool because it uses differential geometry in a nontrivial way to say something non-obvious about the regret when the costs are stochastic. It is well known that OGD-style algorithms achieve $O(\sqrt T)$ regret in the worst-case, and FTL gives low regret when the costs are stochastic, but this paper shows that in fact gradient-based algorithms can also achieve low regret when the costs are stochastic, at least if the domain is sufficiently smooth.

A few questions/suggestions: first, I am interpreting the lazy online subgradient algorithm as special case of OGD, but with subgradients instead of gradients. In this case, the costs are linear, so one can just use gradients without resorting to subgradients. Is that correct? How does the lazy version differ from the greedy version? I think it would be helpful to add a few sentences in the introduction explaining the similarities/differences between the lazy online subgradient algorithm, the greedy online subgradient algorithm, and OGD.

I believe that the bandit result of Zimmert and Seldin (2018) only works if one sets the step size knowing whether the instance is adversarial or stochastic. The authors may wish to point out that their analysis does not suffer from this restriction; the same step-size gets the optimal rate in both settings.

It may be interesting to say something about what goes wrong when the domain is not strongly convex. Can you show an example of a domain where the regret is $\Omega(\log T)$?

Trivial points: the standard notation in online learning is to use $\Pi_S(x)$ to denote the projection of $x$ onto the set $S$. The authors use $P_S(x)$ and may wish to consider altering their notation in the final version. Similarly, people generally use "orthogonal" instead of "perpindicular", especially when talking about geometries beyond $\ell_2$.

Verdict: Surprising result, clean analysis, timely problem. Clear accept.
limitations_and_societal_impact: No problem here.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: They authors show that for linear optimization on strongly convex domains the lazy subgradient method achieves a best-of-both-worlds behavior of a expected regret bound of O(\sqrt{N}) and O(\log(N)) for adversarial and stochastic adversaries, respectively. The best known prior bounds were O(\sqrt{log(N)}) adversarial regret with a more complicated algorithm (based on A,B-prod). On a technical side, the analysis for lazy subgradient is much more intricate and considers loss contributions in the direction of the comparator separately from other directions, and may be of interest in other online linear optimization settings.

Simulations are provided that convincingly argue for the proposed method in the proposed setting. 

main_review: The introduction is generally well written and the contributions are clearly explained and well-positioned in the literature. I think the results are impressive and that the ideas borrowed from differential geometry would be a great introduction to the neurips community.

However, I found the sections requiring differential geometry to be hard to understand. For example, what is y on line 117 (a assume it is a typo for \alpha)? Why is the statement on l120 "the line from y_n...to any x has slope of absolute value Omega(\sqrt{n}) true (in particular, please indicate that this is a high probability statement)? Why does alpha_n = beta_n (this only holds when sum a_n / n is not in \mathcal X, which does happen with high probability), etc. A picture would help, too. You clearly have a strong geometric intuition, but it does not come through clearly. 

While I'm excited to see ideas from higher branches of mathematics percolate into this conference, their rarity means that there is significant burden on the authors to explain the ideas in way comprehensible to the community. I'm afraid that I don't feel this burden has been met in this submission. I feel that even the level of detail provided in the appendix may not be sufficient, but the main body definitely needs to be fleshed out. Some other questions I (and I would imagine other readers) would have are:
-Since \Vert\cdot\Vert is defined as the Euclidean norm, is geodesic distance in Definition 1 is always the Euclidean distance?
- Please explain l130: the normal direction to the surface. Which surface?
- How do you define a coordinate patch and what are its derivatives?
- Additionally, most of the NeurIPS community will not think of derivatives as linear maps, so the notation \nabla N(z)v will probably be confusing.

typos/suggestions:
you didn't define before using it

It would also be good to delineate which lemmas and propositions are novel and which are standard results from differential geometry. 

So in summary, I'm very positive about the paper this submission could be if a better introduction to differential geometry were provided.

Post-rebuttal: I believe the authors will revise the paper enough to clarify the presentation, so I increased my score.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The paper has received mixed reviews; while some reviewers found the results not super significant (essentially simplifying existing results in the literature) and the problem setting restrictive, others found the realization that simple plain lazy OGD is “universal” compelling, and the proof interesting and overall elegant.  All considered---and while I agree with the criticism---I think that there is a fair chance that the paper’s observations will draw some attention and promote further investigation, and I support its acceptance.

One remaining concern the authors should carefully consider is that the differential geometry background, and more importantly - the motivation and justification for appealing to such techniques, is lacking.  I trust the authors to improve this part of their exposition for their final version.

Decision: Accept (Poster)