Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work considers the problem of online learning with movement cost, and studies the metrics of competitive ratio and dynamic regret for polyhedral and quadratically-growing functions. For competitive ratio, while studying simple algorithms (a positive) that ignore switching costs, the upper bounds offered here improve over the best known in both settings (for distinct switching cost in each case). For dynamic regret, the paper suggests a modification of a dynamic-regret-guaranteeing algorithm to the switching cost setting with optimal dynamic regret.
main_review: On the competitive ratio front, the paper presents concrete improvements for special cases of polyhedral and quadratically growing functions (~strong convexity around minimum).

As for dynamic regret: It is well-known that OGD gets the correct dynamic regret as long as the step size choice is allowed to depend on the path length of the comparator (an oracle quantity). Therefore, existing algorithms essentially run Mult Weights over guesses of choices of exponentially spaced learning rates. The modification here for accomodating movement cost is to penalize the experts (corresponding to learning rate guesses) for not just their decision, but also for their movement. This is natural choice.

Questions:
1. Previous work in this setting could operate on locally polyhedral functions. Can such functions be accomodated here? If not, what is the precise obstruction to this?
2. What is the claim of novelty in section 3.3? In the reviewer's reading, the upper bound in Goel et al (Beyond OBD) matches the lower bound exactly for squared l2 movement (see discussion below Theorem 4 there). Theorem 3 here seems to offer strictly worse bounds, contradicting "the constants in our bound are much smaller."
limitations_and_societal_impact: Please see above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies smoothed online learning by targeting two performance metrics: competitive ratio and dynamic regret with switching cost. The paper first improves the competitive ratio of the naive approach and the greedy algorithm. Then the paper proposes a novel algorithm called SAder which achieves optimal dynamic regret with switching cost under the lookahead setting.

main_review: Strengths:

The contribution of this paper is solid. It contains two parts. The first part (section 3) provides better competitive ratios for the naive approach and the greedy algorithm. The second part (section 4) includes a novel algorithm with optimal dynamic regret under the lookahead setting. 

Weakness:

1. These two parts of the contribution are independent of each other to some extent. Is it possible to study one algorithm which can simultaneously improve both competitive ratio and the dynamic regret? Notice that the OBD and ROBD algorithms have theoretical guarantees on both competitive ratio and the dynamic regret, though their results are not optimal.

2. The paper does not contain the lower bound of polyhedral functions and quadratic growth functions.
limitations_and_societal_impact: See main review
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study online convex optimization with switching costs, a well-known problem which has attracted much recent attention in the past few years, and which is closely related to convex body chasing. The authors make the following two contributions: first, they improve on some of the competitive ratio bounds presented in Goel et al and Lin et al, and second, they present an algorithm with optimal dynamic regret, along with a matching lower bound. 
main_review: Theorem 1 claims to improve on the competitive ratio presented in Lin et al, but the improvement is minor and the proof is trivial. I do not believe this theorem will be of interest to the broader ML community. Theorems 2 and 3 are more interesting, and use a careful analysis to simplify and improve results from Goel et al. The proofs are simple and clean, and they are also able to match a lower bound proved in Goel et al. It's nice to see the exact constants nailed down. Theorems 4 and 5 prove dynamic regret bounds for a modified version of the Ader algorithm introduced in Zhang et al; Theorem 6 proves a matching lower bound. The algorithm they propose is only a slight modification of vanilla Ader, so I think the main contribution here is the analysis and the new lower bound.

I do have a suggestion for the authors - they write on line 141 that the squared L2 distance considered in the dynamic regret bounds of Goel et al is "not suitable for general convex functions." It seems to me that the point the authors are making is that the dynamic regret bounds proved in Goel et al rely on strong convexity, whereas their regret bounds do not. While this is true, it does not imply that L2 switching cost is always a superior metric to squared L2 switching cost - different metrics are more relevant for different problems. One advantage of the squared L2 distance is that it is related to LQR control problems, as shown by Goel and Wierman. I think it would be helpful to add a paragrpah explaining the different roles that different choices of switching cost play, instead of writing as if one choice is strictly superior to other choices.

Overall opinion: while the paper does not provide any new algorithmic insights per se, it does present small improvements on existing results on a problem that has attracted much recent attention in the ML community. The paper is well-written and acknowledges previous work properly. 
limitations_and_societal_impact: No problems here.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies smoothed online learning and considers two performance metrics: the competitive ratio and the dynamic regret. For the competitive ratio part, the authors study the greedy algorithm which minimizes the weighted sum of the hitting costs and the switching cost. They improve the existing competitive ratio results by some constant factors in three different settings. For the dynamic regret part, the authors show that a small modification of Ader, SAder, can attain the same dynamic regret bound as the case without switching costs. They also show that if the agent can observe next step's hitting cost before making decisions, the Lookahead SAder algorithm can achieve the optimal dynamic regret bound without the bounded gradient assumption.

Update: I partly agree with the points made in the response. So I adjust the score to 6.
main_review: I have some concern with the originality of this work. Most algorithms considered in this paper have already been studied in similar settings, and the authors failed to convince me about the novelty of their proof techniques. I hope the authors can briefly clarify this in the rebuttal. Are these proofs trivial extensions of previous works? If not, what is the most significant challenge and how do you overcome it?

This paper is technically sound. All claims are supported by rigorous proofs. Although I did not check the details in the appendix, I think the results make sense.

The writing of this paper needs to be improved much. First, the overall organization is a bit messy. The authors present five different problem settings and analyze four different algorithms, but do not discuss much about their connections.  Second, the authors should focus more on the intuitions and novelties in their remarks, rather than only comparing the final bounds. I believe presentation issues can usually be fixed in the revision, but they may affect my evaluation of originality and significance.

My major concern is about the significance of this work. I hope the authors can help me understand the following issues better in the rebuttal:
1. I do not think the improvements in Thm 1 and Thm 2 are significant from a theoretical perspective. It is clear from the form of the competitive ratio that the problem becomes more challenging as $\alpha$ and $\lambda$ converges to zero. The new results in this paper are in the order of $O(1/\alpha)$ or $O(1/\lambda)$, which are the same as previous results. Since there are no lower bound results to rule out competitive ratios in the order of $O(1/\sqrt{\alpha})$, the presented results may still be far from optimal for small $\alpha$. Given this, the claim “It seems safe to ignore the switching cost” in line 211 looks weird to me.
2. In Section 3.3, the proposed algorithm is a special case of the ROBD algorithm in [Goel et al., 2019]. The problem setting becomes slightly more general in this paper, but the proof technique looks similar with the ROBD proof in [Goel et al., 2019]. I hope the authors can clarify why they think the new setting (convex + quadratic growth hitting costs) is important, and what is new in the proof.
3. In Section 4.1, the authors emphasize that “the only modification” they make to Ader is incorporating the switching costs. Does this lead to significant changes in the proof?

In summary, I suggest to reject this paper because I feel the contribution of this work is incremental, and the presentation is not good enough. I understand that the presentation issues may affect my evaluation of other aspects, so I am open to adjust the score if the authors can address some of my concerns.
limitations_and_societal_impact: The two open problems at the end of the paper discuss the limitations of this work. I think they are appropriate.

Some constructive suggestions: I feel the authors can consider more about the applications of smoothed online learning, and use them to justify the assumptions they make on the hitting and switching costs. The switching costs may have more complicated forms than $\ell_2$ norm or $\ell_2$ norm squared, and the hitting costs may become much simpler (e.g. quadratic).
review_title: null

Meta-review: The paper considers the analysis of competitive ratio/dynamic regret for problems with hitting cost and switching cost. They provide concrete improvements in terms of nailing down the constants for the ratios in the case of polyhedral function and quadratic growth functions achieving this with a relatively simple algorithm and a clean analysis. The reviewers have appreciated the clarity and simplicity of the paper and the approach, the concreteness of the improvements achieved as well as the right attribution and discussion of previous work. Nevertheless, the paper does not provide any novel algorithmic insights and analyses a well-known algorithm in various settings with improvements in guarantees. Overall while the paper is close to the borderline post the discussion, the reviewers unanimously agreed that the paper is slightly above the borderline due to the concrete improvements for well-known and well-studied problems and there by I am proposing an accept. 
Decision: Accept (Poster)