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: The authors study online learning in a parameter-free setting. These settings have the benefit of being applicable to settings where the domain is unbounded and where prior information is not available. They generalize some existing algorithms to include switching costs. Switching costs can model a scenario where the learner is incentivized to not change its prediction significantly. They give an algorithm for Online linear optimization that is more or less optimal in several useful metrics. They also experiment on both synthetic datasets as well as real-world datasets, surpassing the baseline significantly.

strengths_and_weaknesses: Originality & Significance -  The models and framework seem to be standard.  The work done in the paper seems to be original to the best of my limited knowledge. Related to the prior work, I find the current work to be incremental and is of moderate significance.

Quality & Clarity - The paper is well-written and the exposition is easy to follow.  The quality of writing is above-average and the arguments made in the non-technical parts of the paper were cogent. Due to my lack of domain knowledge and time constraints I did not verify all technical details of the paper.

questions: The result for Algorithm 1 is when G is exactly known. Quantitatively, how much does the bound worsen if only an upper bound on G is known?

limitations: None.
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: This work studies a meaningful problem called online linear optimization with switching costs. Previous progress on this problem, [ZCP22a], obtains a suboptimal regret bound through a complicated coin betting algorithm. This work improves the previous result in several aspects with a simpler and more elegant algorithm based on some specially designed potential functions. This work also extends the above result to higher dimensions and bounded domains. Besides, in LEA with switching cost, with more structural information, this work proposes a novel reduction from bounded to unbounded domains, which improves the previous bound even without the existence of switching cost. Finally, empirical studies evaluate the effectiveness of the proposed method.
strengths_and_weaknesses: Strengths:

1. The problem of OLO with switching cost is meaningful due to its deep connection with some online decision-making problems, such as online non-stochastic control.

2. The main algorithm, i.e., Algorithm 1, is simple and elegant. And the corresponding theoretical result improves the suboptimal one in [ZCP22a] in multiple aspects.

3. The result in LEA with switching cost is novel, which also imports some novel ideas in the LEA-OLO reduction, even without the existence of switching cost. The illustration in Figure 1 is clear enough.

Weaknesses: please mainly refer to the “Questions” part below.

questions: 1. Actually, [ZCP22a] already obtained an optimal dependence on $\lambda$, i.e., $O(\sqrt{\lambda})$, through a mini-batching technique (see Algorithm 3 in [ZCP22a] for more details), but the authors do not mention it in the draft. Can the authors explain about this?

2. The work [ZCP22b] seems to share much in common with this work, such as potential functions. While in my opinion, the authors did not sufficiently compare the difference between this work and that of [ZCP22b], which is inappropriate. Can the authors give a more detailed comparison of their work and [ZCP22b], in terms of both problems and techniques?

3. Although the main algorithm, i.e., Algorithm 1, is pretty simple and thus elegant, it is not intuitive enough, at least for me. For example, what is the intuition behind the potential function in (3)? The authors said that there is a corresponding analysis in Appendix A.1. Can the authors explain more about the intuition that guides the algorithm design?

4. I guess the extension to online non-stochastic control as in [ZCP22a] is straightforward by reducing the control problem to OCO with memory with a particular policy parametrization?

5. The problem of OLO with switching cost is meaningful due to its deep connection with some online decision-making problems, such as online non-stochastic control. As a suggestion, the authors can make this connection clearer in the main paper, at least in the introduction part.

limitations: Not much.
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: The authors design an algorithm for online linear optimization (OLO) with switching cost, and prove the optimality of the proposed algorithm, as an improvement of an existing algorithm. The trade-off between adaptivity and switching cost, as well as an extension of the algorithm to the learning with expert advice (LEA) are discussed.
strengths_and_weaknesses: Strengths:
1. While the problem of OLO with switching cost is not new, the authors improve the result on the regret bound, and show the optimality of their result in several forms.
2. The key idea that incorporating switching costs by scaling on the dual space seems new and interesting.
3. Overall the paper is well-organized and mostly easy to follow.

Weakness:
1. As authors point out, the result requires the knowledge of the Lipschitz constant G and assumes $\lambda$ is time-invariant, which might limit the application of the method in practice.
2. Please see my additional questions/concerns in the next part.

questions: 1. I am a bit confused by the argument from line 156 to 163. Suppose the sum of switching cost is $1+|u|O(\sqrt{T\log(|u|T)})$, then this "budget" reduces to $O(1)$ only when $u=0$, which implies the comparator is not far away from the initial $x$. For far-away comparators, the budget grows at $O(\sqrt{T})$. I do not see how the conclusion is drawn.

2. In Algorithm 1, the authors set a hyperparameter $C$, and there is also another parameter $\alpha$ in the potential function. Will the performance be sensitive to these two parameters? Should one always choose $\alpha = 4\lambda G^{-1}+2$ in practice?

3. Is it easy and fast to compute the discrete derivative $\bar{\nabla}_SV(t,S)$ in Algorithm 1, when the dimension is not small?

4. What does $||\cdot||_*$ stand for? (e.g., in line 94)
limitations: The authors adequately discuss the limitation and potential improvement for the paper.
review_title: null

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 the problem of parameter-free online learning in the presence of switching cost. Based on a novel dual space scaling strategy, the authors obtain the optimal regret bound for unconstrained OLO with switching cost. The results are also extended to the expert setting, and numerical results on portfolio selection problem are reported. 
strengths_and_weaknesses: Strengths: 

1. The proposed algorithm is parameter-free and improves the suboptimal result in [ZCP22a] to the optimal rate. The results can also extend to the expert setting.

2. This paper is clear-written and technically sound. The theoretical analyses are supported by rigorous proofs which are sound to me.

Weakness:

My main concerns are contribution and novelty.
1. As for contribution, since there already exist methods such as [ZJLY21], that achieve optimal $\mathcal{O}(\sqrt{T})$ (dynamic) regret for OCO problem. Although the proposed method in this paper does not require the diameter of the domain, this improvement seems not significant enough.

2. As for novelty, the proposed method and the proofs are not very different from [ZCP22b], which have already been mentioned in the paper. So, it seems to me that the method is not novel enough. 
questions: In this paper, the switching costs are in the form of $L_{1}$ norm and the authors claim that the proposed strategy can be extended to other norms. Since $L_{2}$ norm or $L_{2}$ norm squared are also widely used for switching costs, I wonder how to extend the strategy to $L_{2}$ norm, especially for higher-dimensional domains? 

(I mean, for higher dimensions, the authors run Algorithm 1 on each coordinate separately to solve it. This is valid for $L_{1}$ norm, since the $L_{1}$ switching cost is the sum of the cost of each coordinate. However, would it be problematic for $L_{2}$ norm or $L_{2}$ norm squared?)
limitations: No problems here.
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 theoretical article is about "parameter-free" regret minimization for (linear) online learning with switching cost

For non-specialists like me, this appealing notion of "parameter-free" needs to be clarified somehow. When analysing an algorithm like stochastic gradient descent, its convergence time upper bound is often given according to some hyper-parameters like the learning rate. The best convergence time is then obtained by setting the learning rate that minimizes this convergence time. If this learning rate is unknown, tuning this parameter has a cost which impacts the convergence time. It has been shown that his cost depends on the square root of the logarithm of the distance between the initial point of the optimization and the (unknown) target.
It seems however that some "parameters" of the problem, like the Lipschitz constant G, that are required by the algorithms are not taken into account in this definition. In other words "parameter-free" means that we integrate the cost of tuning -- some -- parameters in the analysis.

The ability for an online algorithm to handle switching costs is appealing for practical applications where mixing policies is costly or not desirable. By essence, a parameter-free algorithm has to be more adaptable hence more reactive than a classical algorithm, but the switching cost favors algorithms with stable behaviours. This leads to a balance

The key contribution of this article is to provide a new dual approach that improves the parameter-free regret bound provided in [Zhang et al. 2022a] for this switching cost setting.

The Online Linear Optimization algorithm is then transposed to solve the Online Learning with Expert's Advices problem (with switching cost). And it is evaluated through simulations on a portfolio selection problem with transaction costs. It compares favorably against the [Zhang et al. 2022a] baseline.

The proofs are detailed along 20 pages of supplementary material. Some code is provided as well.
strengths_and_weaknesses: Weaknesses / General remarks:
- The paper is far from being self-contained. It has been written for researchers who are already well read on "parameter-free" online learning. As a newcomer I had to follow a full tutorial on the subject to understand the introduction. I think the author should make an effort to write a more readable introduction. Maybe by providing a few concrete historical examples of parameter-free algorithms.
- The "parameter-free" appellation used by this community is "historic" but still a bit of an overstatement for an algorithm, like Algorithm 1, which requires to know or guess the Lipschitz constant G and the switching cost lambda parameter in order to work.

Strengths:
- The integration of switching costs in the Online Learning with Expert's Advices (LEA) problem is an important problem both from the practical point of view and from the theoretical point of view.
- An efficient online learning algorithm able to cope with this problem with as few parameters as possible is a clear contribution (even if G and lambda are still required).
- Once into it, the paper is correctly written, and the maths seem solid (but I did not check the proofs).
- The author provided a code to reproduce their experiments in supplementary material.

questions: The algorithm being not really parameter-free, why not change the title to "Optimal almost-parameter-free Online Learning with Switching Cost" ?
You set the G and lambda parameters respectively to G=1 and lambda=0.1 in your synthetic market experiments. Did you inform your algorithm of these parameters beforehand ? Did you try running your algorithm with the wrong parameters ?
Do the coin betting strategy proposed in [Zhang et al. 2022a] require such parameters ? Is the comparison fair on that ground ?

limitations: The limitations are explicitly given in the conclusion.
The authors underline that the Lipschitz constant G and the time-invariant switching cost lambda are required by their algorithms. Hence admitting that their algorithms are not really "parameter-free". 

Adapting to changing costs and dropping the G parameter is left as future work.
review_title: null

Meta-review: metareview: This is a technical, but interesting paper on online linear optimization. The nice contribution is a control of the switching cost (moving from one action to another) which makes the problem highly non-trivial.

The contribution is to consider a "smaller" set of assumptions (hence a weaker asymptotic result) than in the existing literature, but this allows to get better parametric rates.

This might not be the most breathtaking paper, but the reviewers and myself find it sufficiently interesting to be accepted at NeurIPS.

Congratulations !
confidence: Certain
Decision: Accept