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 smoothed online convex optimization. In particular, the authors proposed an online GD method with different step size predicted by the discounted normal predictor. The proposed combination is claimed to be simpler than previous literature while maintaining a similar regret bound. 
strengths_and_weaknesses: Strength: This paper is well written and easy to follow. The proposed algorithm is clear and simpler than the previous literature. Merging the DNP into the online gradient descent sounds novel to me.

Weakness: 
1. No experiments are added to justify the advantage of the result. 
2. It would be better demonstrated which role DHP is playing in the main algorithm to better highlight the contribution of this paper.

questions: NA
limitations: NA
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: This paper proposes a new algorithm based on Discounted-Normal-Predictor to combine multiple experts for SOCO.  First, a modified Discounted-Normal-Predictor (DNP-cu) which uses a conservative update instead of the traditional projected update is proposed as the meta algorithm, followed by the prediction performance bound. Then a combiner based on DNP-cu is proposed to predict the combining weight for multi-expert SOCO. With OGD as the experts, the smoothes OGD in Algorithm 4 combines multiple experts by the proposed combiner. The authors give nearly optimal bounds for both the adaptive regret and dynamic regret for any lambda and any interval.
strengths_and_weaknesses: **Originality \& Significance**

An effective design to better exploit multiple experts in online optimization is really important and desirable. The idea to combine the experts by predicting the combining weight based on DNP-cu is novel and very inspiring. 

**Quality**

The regret analysis in this paper is solid. Both the dynamic regret and the more fundamental adaptive regret are bounded to match the state-of-the-art regret bound.

**clarity**

The paper is well-written and easy to follow. 

Typos:  Line 532 in appendix, Theorem 6,  the output of OGD is $w_t$ in stead of $x_t$?

Line 551 in appendix, Eqn. (47), there should be a sum notation after the first "$\leq$".


questions: The proposed expert combiner is really interesting and the theoretical results can recover many recent SOCO and even general online optimization works. I like this work while I have some minor questions:
1. Comparing with the expert combiner for SOCO in Zhang et al. [2021a], the dynamic regret bound of this paper is up to a logarithmic factor. Could the authors discuss more about the comparisons with the combiner in Zhang et al. [2021a]?
2. I noice that the dynamic regret bound nearly match the lower bound. Is it possible to derive a lower bound regret of the proposed algorithm to show what performance the algorithm can achieve?
limitations: The limitations are adequately addressed.
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 this paper, the authors propose a simple algorithm for smoothed online convex optimization (SOCO), which aims to minimize both the hitting cost and the switching cost. The key idea is to use a variant of Discounted-Normal-Predictor to combine different instances of online gradient descent (OGD). Based on the advantageous properties of Discounted-Normal-Predictor and OGD, they prove that the proposed algorithm attains nearly optimal (static and dynamic) regret bounds on every interval, even when the switching cost is present.
strengths_and_weaknesses: Strengths:
1. The writing of this paper is good, and the authors compare their bounds with previous results clearly. The proposed algorithm is the first attempt to simultaneously minimize adaptive regret and dynamic regret.

2. Although the analysis of Discounted-Normal-Predictor is quite involved, after we understand its property (Theorem 1) and usage (Lemma 1), it can be used as a black-box meta-algorithm, and the rest analysis is easy to follow. In this sense, the algorithm/analysis in this paper is simpler than that of Zhang et al. [2021c].

3. The theoretical guarantee of this paper is stronger than existing studies, since the proposed algorithm can minimize the dynamic regret with switching costs in every interval. For comparison, the dynamic regret bound of Zhang et al. [2021a] is non-adaptive, and the adaptive regret bound of Zhang et al. [2021c] only supports static regret.

Weaknesses:
1. As stated in the abstract, this paper is motivated by Kapralov and Panigrahy [2010] and Daniely and Mansour [2019], and thus the technical novelty is a bit limited. On the other hand, I do admit that the authors have made some modifications in Algorithms 2 and 3.

2. The authors have not discussed the competitive ratio of their algorithm.

Summary:
Although this paper is somehow incremental, the results are new and significant. It is still important to reveal the fact that Discounted-Normal-Predictor can be applied to SOCO and achieves better bounds, which may advance the theoretical and algorithmic developments of SOCO.
questions: 1. In this paper, the authors choose the $\ell_2$-norm to measure the switching cost. Can the results be extended to other switching costs such as $\ell_1$-norm and $\ell_\infty $-norm? 

2. The switching cost of $u_t$ is ignored in Theorem 4. Please explain the reason.

3. Currently, all the proofs are provided in the supplementary. It'd be better if the authors could highlight the sketch of analysis in the main content.

4. Competitive ratio is a popular performance measure for SOCO. The authors may need to explain why they have not used a competitive ratio.

limitations: N/A
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 this paper, the authors study algorithms for smoothed online convex optimization (SOCO). Compared to classical online convex optimization (OCO), in SOCO the player also suffer a switching cost between rounds depending on how much the iterates changed from one round to another. In this work the authors propose an algorithm the incurs low dynamic and adaptive regret simultaneously. To do so, they instantiate around $O(\log T)$ instances of online gradient descent with different step-sizes, and combine these algorithms using a technique called "Discounted-Normal-Predictor" originally developed for online bit prediction. Their results either match previous guarantees (in the case of adaptive regret), or are the one of the first of its kind for SOCO (for dynamic regret), matching the known lower-bounds up to logarithmic factors.
strengths_and_weaknesses: ### Strengths
- The technique uses in a sleek method from online bit prediction to combine different OCO algorithms. Although this bit prediction method is a bit mysterious, the high-level idea of the final algorithm is well-explained and intuitive;
- The fact that one single algorithm manages to control both dynamic and adaptive regret simultaneously is neat;
- The paper is quite well-written, with an excellent literature review

### Weaknesses 
- I noticed the authors did try to explain the main ideas behind the bit prediction strategy, but I had a very hard time parsing the bounds in Theorem 1. This influences later on the understanding of the remainder of the algorithm and the intuition behind some of its construction;
- I was a bit confused about when the $b_t$'s should be in $[0,1]$ and when they should be in $[-1,1]$. The beginning of sec 2.3 talks about it being in $[-1,1]$. But when describing the work of Daniely and Mansour, the predictions (coming from eq (7) according to Alg 1) end up in $[0,1]$. At the beginning of sec 3.1 the authors also say "(...) but require the prediction to lie in [0,1] (...)", what made me believe previous work was mostly on $[-1,1];
- Related to the confusions above, the remark on line 222 was not quite immediate.

### Minor observations
- In (9) you use $\hat{g}$ but never defined it. Was it supposed to be (7)?
- Line 165: what do you mean that the "property" of $g$ has been "revealed"?
- Line 216: you use "meta-regret" without defining it, which caused a bit of confusion when I was reading. Maybe something that sounds less formal like "the difference in the costs between the sub-algorithms and the main one" would avoid this;
- In Lemma 1 $\mathcal{A}$ is the final algorithm and in Algorithm 3 it is the bit prediction algorithm, which is confusing since Lemma 1 is about Algorithm 3;
- Using $\cap$ to denote "AND" was a bit unusual for me. If other reviewers find it weird as well, consider changing, but it may be just me in this case;
- It is a bit "unsettling" to call a real number a bit; 
questions: - Could you help me understand which works on bit prediction were with bits on $[-1,1]$ and which ones were on $[0,1]$;
- Could the authors try to give intuition behind (10)? The presence of $U(n)$ and $\mu$ make it a bit harder to digest (and maybe with more time to read the paper I'd be able to get the intuition);
limitations: The authors do a good discussion, afaik, of related work and how their work can be placed on the literature. Maybe some discussion of computational efficiency/cost of the algorithm would have been interesting, but it certainly is not crucial.
review_title: null

Meta-review: metareview: All the reviewers were happy with this paper. There were some comments about experiments and additional results (e.g. a lower bound), but the reviewers generally thought the work in the paper is solid enough to merit acceptance. I encourage the authors to incorporate the discussions that clarify various points in the final manuscript. It would also be nice to have some (at least toy) experiments to corroborate the theory.

 
confidence: Certain
Decision: Accept