Optimal Comparator Adaptive Online Learning with Switching Cost
Authors: Zhiyu Zhang
Ashok Cutkosky
Ioannis Paschalidis
Venue: NeurIPS 2022 Accept (2022)
Keywords: parameter-free online learning
adaptive online learning
switching cost

Abstract: Practical online learning tasks are often naturally defined on unconstrained domains, where optimal algorithms for general convex losses are characterized by the notion of comparator adaptivity. In this paper, we design such algorithms in the presence of switching cost - the latter penalizes the typical optimism in adaptive algorithms, leading to a delicate design trade-off. Based on a novel dual space scaling strategy discovered by a continuous-time analysis, we propose a simple algorithm that improves the existing comparator adaptive regret bound [ZCP22a] to the optimal rate. The obtained benefits are further extended to the expert setting, and the practicality of the proposed algorithm is demonstrated through a sequential investment task.

Optimal Comparator Adaptive Online Learning with Switching Cost
Zhiyu Zhang Boston University zhiyuz@bu. edu
Ashok Cutkosky Boston University ashok@cutkosky.com com
Ioannis Ch. Paschalidis Boston University yannisp@bu. edu
Abstract
Practical online learning tasks are often naturally defined on unconstrained do- mains, where optimal algorithms for general convex losses characterized by the notion of comparator adaptiviry. In this paper, we design such algorithms the presence of switching cost the latter penalizes the typical optimism in adaptive algorithms, leading to a delicate design trade-off. Based on a novel dual space scaling strategy discovered by continuous-time analysis, propose simple algorithm that improves the existing comparator adaptive regret bound [ZCP22a] to the optimal rate. The obtained benefits are further extended the expert setting, and the practicality of the proposed algorithm is demonstrated through sequential investment task.'
Introduction
Online learning [CBL06, Haz16, Ora19] powerful framework for modeling sequential decision making tasks, such as neural network training, financial investment and robotic control. In each round, an agent picks a prediction xi in convex domain X, receives convex and Lipschitz loss function 4 that depends on æ1..... 2,, and suffers the loss (xx)). The goal is to ensure that in any environment, the cumulative loss of the agent is never much worse than that of any fixed decision X. That is. one aims to upper-bound the regret Eim (xx.) - [e(m)], for all time horizon E N4, comparator E X and loss sequence IT...,,IT.
If there exists best fixed decision w* = max, Σ (xx in hindsight, then the regret with respect to any u E X' is dominated by the regret with respect to u" In the context of training machine learning models, u" corresponds to the model parameter that minimizes the training error. Hence, intuitively, the regret bound characterizes how fast the algorithm finds u" through training.
Most classical online learning algorithms are minimax in nature, only tuned to optimize the worst-case regret. For example, if the domain X' bounded. then the maximum distance between the best fixed decision u² and the initialization I of the algorithm is the diameter D of X. Only considering this worst case, it suffices to use Online Gradient Descent (OGD) [Zin03] with learning rate π) x D/ The result is a ODDTT) regret bound that holds uniformly for all comparators u X. Such minimax reasoning is prevalent, limited two substantial ways.
1. requires a bounded domain. Many practical problems are naturally unconstrained, making such arguments inapplicable.
Practical applications are usually not the worst case, which means that the minimax bound O(DVT) is typically loose. Think about the situation where we have a prior guess of u², from either domain knowledge pre-training. Using this prior as the initial prediction I1, we should
Future versions available at Attpp:://rrxiss wtt.:/r/////////./// 06846.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

expect a provable gain over arbitrarily initializing the algorithm specifically. had we known the correct distance ||u" ll, we could have picked Tt & I|u* x1ll /vt in OGD, resulting in O(IIu* - z1 || VT) regret. Achieving this goal without the prior knowledge of I|u - x1 l| is of both theoretical and practical importance.
Recent studies of comparator alaptive online learning [LS15, OP16, CO18) aim to address these issues. The domain does not need to be bounded, and the regret bound is Õdd(u, uu, 21 (T) where d(:,-) is some suitable distance measure. Intuitively, these algorithms are both optimistic and robust: given prior information on u", we can pick such that d(u", ,I1), and consequently the regret bound, are both low. Meanwhile, even when our initialization 2 is wrong (i.e., d(u" .x) ) is large), the regret bound is still almost as good (up to logarithmic factors) as that of the minimax algorithm with the best tuning in hindsight. Such properties have shown benefits in diverse applications, e.g.. [OT17, JO19, vdH19].
In this paper, we extend the design of these algorithms classical setting with switching costs. Here the agent is penalized not only by its loss but also by how fast it changes its predictions. Practically, switching costs are useful whenever the smooth operation of system favored, such in network routing, control of electrical grid, portfolio management with transaction costs, etc. Recently they also naturally show up in online decision problems with long term effects, such as nonstochastic control [ABH* 19J. With a given weight À 2 O and a norm ||-]], our goal is to guarantee a comparator adaptive bound for the augmented regret
E (1(=)))((0)) + Σ 10, T2+1ll-
While gradient descent can incorporate switching costs by simply scaling its learning rate, extending comparator adaptive algorithms is lot harder. Just like other adaptive algorithms [DHSI 1. DGSS15), the key idea of comparator adaptivity is to quickly respond to the incoming information and hedge aggressively. Switching costs, the other hand, encourage the agent to stay still. Therefore, achieving our goal requires a delicate balance between these two opposite considerations.
Similar trade-offss between adaptivity and switching costs have led to intriguing results in the past. For example, Gofer [Gof14] showed that the gradient variance adaptivity well-studied the switching- free setting is impossible with normed switching costs, thus establishing clear separation caused by the latter. Daniely and Mansour [DM19] showed that a common analytical technique for switching costs is incompatible to the so-called "strong adaptivity" (i.e., form of adaptivity w.r.t. nonsta- tionary comparators). Regarding comparator adaptivity, our prior work [ZCP22a] proposed the first comparator adaptive algorithm with switching costs, but the obtained regret bound does not achieve the optimality criterion of the switching-fre free setting. The present paper closes this gap.
1.1 Contribution
We develop comparator adaptive algorithms for two classical settings: (1) Online Linear Optimization (OLO) with switching cost: (ii) Learning with Expert Advice (LEA) with switching cost.
1. For one-dimensional unconstrained OLO with switching costs, assuming loss gradients Igel S 1 and initial prediction x1 0, we propose an algorithm that guarantees
Σ Ex( u) + xt z141 S CVXT + Oul (ovlo(VVTTT) (VATlog(C--Jul))
where C > 0 is any hyperparameter chosen by the user (Section 2). Our bound achieves several forms of optimality with respect to X, |u| and T, improving the prior work [ZCP22a]. Extensions to bounded domains and general dimensional domains are presented, which include some new technical components (Appendix B).
Converting the above result from OLO LEA, we demonstrate how classical conversion tech- niques [LS15, OP16] are designed to have large switching costs, and then propose a fix with a clear geometric interpretation. This leads to the first comparator adaptive algorithm for LEA with switching costs (Section 3).
2 Also called parameter-free online learning due to historical reasons.
For general 21, we replace |u] in the regret bound by lu xı].
2

---

Technically, our improvement over [ZCP22a] relies on novel dual space scaling strategy. This actually not guessed, but systematically discovered by a continuous-time analysis (Section 2.4). whose procedure follows another prior work of ours [ZCP22b]. In the continuous-time limit, it becomes evident what kinds of algorithmic structures from the switching-fres setting are transferable to the setting with switching costs. Indeed, revealing generalizable knowledge is key benefit of the continuous-tine analysis, which was not demonstrated in [ZCP22b]. As an added bonus, both our OLO algorithm and its analysis are considerably simpler than those from [ZCP22a].
Concluding these theoretical results, our OLO algorithm is applied a portfolio management task with transaction costs (Appendix D). Numerical results support its superiority over the existing approach [ZCP22a].
1.2 Related work
Online learning basics Throughout this paper we will only consider linear losses. The generality of our setting is preserved, since convex losses can be reduced to linear losses through the relation Ei=14e(z))) - [u)] & called Online Linear Optimization (OLO). As its important special case, Learning with Expert Advice (LEA) considers OLO on a probability simplex, but aims at a different form of regret bound due to its different geometry.
(V4(2) 24 - u) [Haz16, Ora19]. Online learning with linear losses
Classical minimax approaches in online learning include Online Mirror Descent (OMD) and Follow the Regularized Leader (FTRL), with Online Gradient Descent (OGD) being their most well-knows special case. We write "gradient descent" as the minimax baseline for the ease of exposition. Moreover, both OMD and FTRL have elegant duality interpretations [Ora19, Section 6.4.1 1 and 7.3), involving simultaneous updates on the primal space (the domain X) and the dual space (the space of gradients). We will exploit this duality in our analysis.
Comparator adaptive online learning Also known as parameter-freence comparator adaptive online learning aims at matching the performance of the optimally- gradient descent in hindsight, without knowing the correct tuning parameter. The associated regret bound can appear in different forms, depending the specific learning setting.
1. For LEA, a comparator adaptive bound has the form O (VT (L((())) where u and x are distributions on the expert space representing the comparator and user-chosen prior. Such an idea was initiated in [CFH09], and the analysis was improved and extended by series of works [CV10, LS15, KVE15, CLW21, NBC+21, PLH22] Notably, comparator adaptive LEA algorithm naturally induces a bound on the E-quantile regret- the regret with respect to the E-quantile best expert. The latter particularly meaningful when the number of experts is large. Lower bounds were considered in [NBC*211 21].
We will present nonasymptotic improvement of the VKL divergence in this paper. Frameworks that generalize root KL to f-divergences have been studied in [Alq21, NBC* but to our knowledge, existing algorithm guarantees better divergence term than root KL, even without switching costs.
For OLO, typical comparator adaptive bounds are C+ ||w||| O (VTlog(C- |u|l, T)) or CVT
||u|| O (v (VTlog(C- [)).)) where a prior x1 can be incorporated by letting u < u 21. These two bounds are both Pareto-optimal (see [ZCP22b] for detailed explanation), as they represent different trade-offs on the loss (the regret at u = Xi) and the asymptotic regrel (when |/u xn is large). Existing works [MO14, CO18, FRSI8 88 MK20, JC22] were mostly independent of the LEA setting, but unified views were presented in [FRS15, OP16). Lower bounds were studied in [SM12, Ora13, ZCP22b].
Switching cost Motivated by numerous applications, switching costs in online decision making have been studied from many different angles. For example, beside online learning, the online algorithm community has investigated settings like smoothed online optimization [CGW18, GLSW19, LQL20] and convex body chasing [BLLS19, Se120J, where the loss function 1, is observed before the agent picks the prediction Iz. There, the switching cost is the key consideration that prevents the trivial strategy s, E arg min, (x). As for online learning, an additional complication is that o; (e-g., the investment portfolio) should be selected without knowing (e.g., tomorrow's 's stock price).
3

---

Even within online learning, there are several ways to model switching costs. In cases like network routing, every switch means changing the packet route, which can be costly. Therefore, one needs a lazy agent whose amount of switches (or its expectation) [KV05, GVW 10, AT18, CYL.220, SK21] as low as possible
good modeling candidate 21 * F4+1]. Alternatively, one could take smooth view [ABL+ 13, BCKP21, WWYZ21, ZJLY21] where the agent can perform as many switches as it wishes, as long as the cumulative distance of switching is low in this view, switching cost can be a norm || Z141 || or its smoothed variant | d++1 II? The present work primarily considers the L1 norm switching cost motivated by the transaction cost in some financial applications. Notably, for LEA, the L1 norm unifies the lazy view and the smooth view [DM19, Section 5.2].
Although switching costs have been extensively studied, existing works on the combination of adaptivity and switching cost are quite sparse. As one should carefully trade off these two opposite requirements, there have been interesting impossibility results [Gofl4, DMI9], highlighted in our introduction. In this regard, one should not believe that every classical adaptivity can be naturally achieved with switching costs. The present paper shows that the optimal comparator adaptivity can indeed be achieved, thus improving the suboptimal result from [ZCP22a].
Relation to downstream problems More generally, incorporating switching costs amounts to considering history-dependent adversary: can pick loss functions that depend not only on the instantancous prediction Zt, but also on the previous prediction 2z-1- One could further generalize this setting to online learning with memory (CBDSI3, 13, AHMI5], where the loss depends on a fixed- length prediction history, and finally to dynamical systems [ABH* 19, SSH20, Sim20], where the entire history matters. In fact, a common procedure in nonstochastic control [ABH* 19] is to bound the risk in the future by properly scaled switching cost. Achieving comparator adaptivity with switching costs may benefit these important downstream problems as well, by making algorithms easy to combine 19ut19, Cut20, ZCP22a].
Continuous- approach to online learning Finally, on the technical side, our methodology builds on emerging continuous-time perspective of online learning. From theoretical angle, Kohn and Serfaty [KS10] demonstrated a rigorous connection between Partial Differential Equations (PDE) and discrete-ting tiieeteee-meeeeee repeated games. More recently, such connection has led to algorithmic benefits in minimax LEA [Zhul4, Rok17, DK20, KKW20, HLPR20, BEZ20a, BEZ20b, GHP22], e-quantile bounds [PLH22] and comparator adaptive OLO [ZCP22b]. The key idea is that online learning algorithms in the continuous-time limit can be more easily parameterized and analyzed. In this paper we will show additional bonus: generalizing algorithmic insights is also easier in the continuous-time limit.
1.3
Notation
Let f* be the Fenchel conjugate of a function f. A(d) represents the d-dimensional probability simplex; KL and TV denote the KL divergence and the total variation distance, respectively. For two integers S b, [a is the set of all integers such that c S 6. log represents the natural logarithm when the base is omitted. Throughout this paper, "increasing" and "positive" are not strict (i.e., include equality as well).
For a twice differentiable function (tt, where represents time and represents spatial variable, let V.V. V.VV V and VssV be the first and second order partial derivatives. In addition, we define discrete derivatives as
VsV(L,) = 1
1 V(t, -V(t 1)],
(1)
V(c5+++)) -V,
2 OLO with switching cost
This section presents our main result, a comparator adaptive OLO algorithm with switching costs. We will focus on the 1D unconstrained setting. Due to limited space, extensions to general settings deferred to Appendix B.

---

2.1 The 1D unconstrained setting
We consider the domain = R. Lipschitz constant G > 0 for the loss gradients, and a weight for switching costs. In the t-th round, the agent predicts 24 R, receives a loss gradient gr [-G, G] that depends on past predictions Tist. and suffers an augmented loss g. + A |xz 21-1 1 (w.l.o.g. let To 21 0). The performance metrie is the augmented regret for all E R and T E N+:
T (u) == Σ 9h - u) + A Σ 0 - 81+1/- 1m1
Ignoring the dependence on G' for now, our goal is to show comparator adaptive bound
Ô (lul ATT) more specifically the optimal rates C + |u| O (VTToogC--X((( or CVXT
lul O (V log |ul) for any hyperparameter C' > 0. These two cases are equivalent via the standard doubling trick [S$11], 1], as discussed [ZCP22b].
For minimax algorithms like bounded domain gradient descent [Zin03], one can use scaled learning rates T) x 1/VAt to ensure that both sums in (2) are (VTT) thus obtaining a combined
(VXT) regret bound. However, such a divide-and andde-uued approach does not apply to comparator adaptive algorithms, as cannot separately show the desirable bound the two sums in (2). To this, suppose one could guarantee the second sum alone is at most 1 + |u| O loTlog(la T) here we only focus on the dependence on |u| and T. Since this cumulative switching cost is an algorithmic quantity independent of the comparator, we can take infimum with respect
and obtain a "budget" of I for this sum. Following this argument, |ærl S [2g] + + Σr=1 I2+ r++1l = O(1). That is, the algorithm should only predict around the origin, which clearly leads to large regret with respect to far-away comparators, under certain loss sequences.
The challenge can be motivated in another way. As shown in [Ora19, Figure 9.1]. the one-step switching cost |a,, -tt+| of comparator adaptive algorithms can grow exponentially with respect to t, whereas such a quantity is uniformly bounded in gradient descent. In fact, the exponential growth the key mechanism for comparator adaptive algorithms to cover an unconstrained domain fast enough (thus improving minimax algorithms). This is however problematic when switching is also penalized, as one can no longer control the switching cost by uniformly scaling | F141/-
2.2 Switching-adjusted potential
To address these issues, one should bound the switching cost and the standard OLO regret in unified framework, instead of treating them separately. Our prior work [ZCP22a] used the classical coin- betting approach from [OP16, CO18), which is included in Appendix A. for completeness. In the 1-th round, the algorithm maintains quantity Wealth, 1; by picking betting fraction Br [0, 1], the prediction is set to x, = 3e Wealth,-- 1. To further ensure low switching costs, the betting fraction 3 is capped by decreasing upper bound ((I/T)). Although hard threshold is conservative, which could be the reason of our previous suboptimal result.
analytically nontrivial, such a
In contrast, the present paper follows the potential framework explored by a parallel line of works [MO14, FRS18, MK20, ZCP22b]. Generally, these algorithms are defined by potential function S), where represents the time index, and S represents "sufficient statistic" that summarizes the history. In each round, the algorithm computes S = - E g./G, and the prediction x, is the derivative V evaluated at (t, S,_1). We will specifically consider Algorithm 1, which is variant based on the discrete derivative VsV. cf. (I).
One could think of the potential framework as the dual approach of FTRL the potential function and the regularizer are naturally Fenchel conjugates. While the FTRL analysis relies on a one-step regret bound on the primal space (the domain X, cf. [Ora19, Lemma 7.1)). the potential framework constructs a similar one-step relation on the dual spuce (the space of S.. cf. [ZCP22b, Lemma 1J). Along this interpretation, our key idea is to incorporate switching costs by scaling on the dual space, rather than only on the primal space. That is, given a potential function that works without switching costs, we scale the sufficient statistic sent to its second argument by function of X.
5

---

Algorithm One-dimensional unconstrained OLO with switching costs.
Require: A hyperparameter C' > 0, the Lipschitz constant G, and potential function ((L, S) that implicitly depends on and G. Initialize So = 0.
1: for / = 1, 2, do
2: Predict 2; = V s (t, St-1), and receive the loss gradient 9t. Let S, = S - gt/G.
3: end for
To better demonstrate this idea, let us first consider a quadratic potential (tt, S) = (1/2) CGS The potential method suggests the prediction
(t, = CE = It-1 - which is simply gradient descent with learning rate C. Scaling on the primal space means scaling V directly, while scaling on the dual space means scaling the sufficient statistic S. It is clear that both cases are equivalent scaling the effective learning rate, which the standard way incorporate switching costs in bounded domain gradient descent. In other words, for this gradient descent potential, the two types of scaling are essentially the same.
Now, to achieve optimal comparator adaptivity, we need a better potential where scaling on the dual space actually makes a difference. With parameter a that will eventually depend on X, we consider Algorithm induced by the potential
(t, CVat 2 {
///vaat
("esple))ed du
When the Lipschitz constant G 1, it has been shown [ZCP22b] that a 1/2 leads comparator adaptivity without switching costs. Here we use = 4XG - 2, which amounts to scaling both the primal space and the dual space: on the primal space, we scale up the overall prediction by O(VAG-1+ and on the dual space scale down the sufficient statistic S by O(I/VAG-1 1). The latter gives us the optimal comparator adaptive bound (i.e., Pareto-optimal rate in Ju| and T), while the former helps us obtain the optimal rate Due to incorporating À into the potential function Va. we call our approach the switching adjjssed potential method.
Although the dual space scaling strategy and the particular structure of Va may mysterious at first glance, they are actually derived from a continuous-time analysis. To proceed, we will first present the performance guarantee in the next subsection, and then revisit the derivation of this strategy in Section 2.4.
2.3 Optimal comparator adaptive bound
Despite its simplicity, our approach improves the result from our prior work [7CP22a] by consider- able margin.
Theorem 1. Ifa 44G-1 1 +2 then Algorithm induced by the potential Va guarantees
C +2 +
(w) & V(AG C+ |u|
(v Alog
(1+
[4]
for all u E IR and T E N
Theorem simultaneously achieves several forms of optimality.
1. Pareto-optimal loss-regret trade-off: considering the dependence and T, (ug
O (Iul V ju] while the cumulative loss satisfies Regret,) (0) O(VT). An existing lower bound [ZCP22b, Theorem 10] shows that even without switching costs, all algorithms satisfying a O(VT) loss bound must suffer Ω (lu] /T (u) regret bound. In this sense, algorithm attains a Pareto-optimal loss-regret trade-off, in strictly generalized setting with switching costs. On T alone: Regreti (u) O(VT). Despite achieving comparator adaptivity, the asymptotic rate on T is still the optimal one, matching the well-known minimax lower bound.
On À alone: Regret) (u) O(V)). Our bound has the optimal dependence on the switching cost weight [GVW10, Theorem 5].

---

To compare Theorem 1 to [ZCP22a], we have to convert them to the same loss loss-regret trade-off, i.e. both guaranteeing Regretý (0) = O(1) or Regret, (0) = O(vT). Here we take the first approach details are presented in Appendix A.4. Let us only consider the dependence on a and ( (VTlog(C |u| T)) which
T.4 By doubling trick, our bound can be converted to C' + +|ul O
improves the rate C + |u| O (vT (oo(C=+||u[T) from [ZCP22a, Theorem 1J. Specifically, our converted upper bound also attains Pareto-optimalin in this regime (i.e., matching the lower bound [Iu] V [ ()) [Oral3]), whereas the existing approach does not.
The proof of Theorem is sketched below, with the formal analysis deferred to Appendix A.3. It mostly follows standard potential argument, which is another benefit over the existing approach the idea of this proof is easier to interpret and generalize.
Proof sketch of Theorem To begin with, the first step is to show a one-step bound on the growth rate of the potential. If there is no switching cost, then the Discrefe Itó formula can serve this purpose, which applies to any convex potential V. is an established result the probability literature [Kud82, Fuj08, Kle13], and Harvey et al. [HLPR20] first applied it to minimax LEA. The version below is from our prior work, which is a small variant that removes the LEA context.
Lemma 2.1 (Lemma 3.1 of [ZCP22b]). the potential function V S) convex in S, then against any adversary, Algorithm I guarantees for all f. E N++
Vtt, St) V(t 1, S -G (t, + (1/2) (tsV(tt
Our key observation the following lemma, which incorporates switching costs into Va- Note that the structure of V, is important here.
Lemma 2.2. For all a > O, consider Algorithm I induced by the potential Va- For all & E N+,
s m++1| S (V, -
Combining the above, if we define
A, : (t, +
+ -
then telescopic sum yields a cumulative loss bound
T Regret> - (g.z) + +A/0 - x141)) -G -G. Va + G Σ A
T
To proceed, we need to control the residual term A., which may seem problematic due to its complicated form. Fortunately, a careful analysis shows that As vanishes with proper choice of a. Lemma 2.3. !f a 2 4XG-1 2, then for all I and against any adversary, A, S 0.
Finally, with the updated loss bound Regret, (0) < G (T, ST), our regret bound follows from the classical loss-regret duality [MO14, Ora19].
2.4 Continuous-time derivation
Now let us derive our dual space scaling strategy from a continuous-time perspective. Technically, the procedure is analogous to another prior work of ours [ZCP22b], which studies optimal potential functions for the standard OLO setting without switching costs. Before starting, we need generalized definition of the discrete derivative, with tunable gap increment 6.
VVV
(t, 5) S(t,S-
Note that the choice of 8 = 1 recovers V S) Algorithm 1. The Lipschitz constant will be set to I for the ease of exposition.
*Comparing the dependence is more subtle, discussed in Appendix A.I.
7

---

Step 1: discrete-time recursive inequality First, let us consider the following inequality that characterizes "admissible" potentials for Algorithm 1. For all and S, ((t - V()- 2 max (v S g) +V S) + V (V 1, 0c |5|-1,1)
(5)
Finding solutions of this inequality is sufficient for constructing regret bounds. To see this, suppose the above holds for some V. We can then plug in 5 and guarantee that for gr E [-
ge + X [2 Ie+1l S V(I 1,-) - St,.
A telescopic sum further leads to cumulative loss bound Regret S (0 VTT, ST), and regret bound on Regret) then follows from the standard loss-regret duality [MO14].
Step 2: E-scaled recursion Since we ideally need optimal potential functions that satisfy the inequality (5) without any slack, let us turn (5) into an equality and try to approximately solve it. Intuitively this challenging task, as there is no natural way to parameterize the dependence of V on the discrete time t. However, if we decrease the discrete time interval, solutions V will be "smoother" and easier to describe. Concretely, let e > be parameter that will later approach O. On (5), we scale
1. the unit time by s²:
the loss gradient g. the switching cost weight À and the gap increment by E. Both scaling factors are justified in the switching-fre free setting [ZCP22b, Appendix A.2]. Notably, since 9 and À have the same "unit", it is natural that they scaled by the same rate. With that, obtain a scaled recursion
V(t - =2
max (V(),S-8g)- +g -V sE[-1.1]
(6)
Step 3: continuous-time PDE
To proceed, we take the second-order Taylor approximation on all components of (6). Calculations are simple, and defer the details to Appendix A.5. Both the zeroth and the first order terms of & naturally vanish. Only keeping the second order terms, we have
V.V(I,))+ + max 9E(-1,1]
( ss (1, + > \g ss Vs
As typical potential functions are convex in the sufficient statistic S, it is reasonable to impose an additional condition V ss V (t, S) 2 Then, the above becomes the ID backward heat equation
V.V + VV = 0,
where a A 1/2. Compared to the switching-free setting [ZCP22b, Eq. 5], we obtain the same PDE, but change the negative thermal diffusivity from 1/2 to 1/2 + X. This concisely characterizes the effect of switching costs on the structure the online learning problem.
Step 4: solving the PDE
The final step is to solve the backward heat equation. With a hyperparam- eter c, consider solutions of the form
(1, = V4at
Plug it in, the backward heat equation reduces to the Hermite Ordinary Differrntiall Equation (ODE) g" 2zg'(z) + 4cg(z) =0, 0,
which is independent of a. This is crucial observation, as it reveals the correct way to generalize the knowledge from the switching free setting to the setting with switching costs. More specifically,
In the switching-free free setting, we can take solution g(2) of the Hermite ODE, plug in the argument S/V2t and obtain a potential function V..
When switching costs are considered, the above derivation suggests to take the same function g(z) as before, and plug in a scaled argument = S/ 4ax.. This is precisely dual space scaling, Finally, as shown in [ZCP22b], particularly good choice of e 1/2. Using this choice yields the switching-adjuue potential (3).
8

---

Remark To summarize, through this derivation we aim to demonstrate a key benefit of the continuous-timg time analysis: makes the generalization of algorithmic structures easier. This was not presented in our prior work [ZCP22b), but could be useful in the broader online learning context.
Meanwhile, we do not intend overclaim its strength although the continuous-time analysis provides useful intuition, we ultimately care about discrete-time regret bounds. Discretizing such arguments relies on an obscure argument that has not been made concrete yet: "Va derived in the continuous time also serves as a good potential in the discrete time." Indeed, verifying this property technically nontrivial (Section 2.3), and doing so requires a slightly more conservative choice of (i.e., 4A + 2) than what is suggested above.
2.5
Extension beyond the 1D unconstrained setting
So far we have only considered the ID unconstrained setting. Our results can be extended to higher dimensional domains and bounded domains, which deferred to Appendix B.
Most notably, we present an algorithm (Algorithm 5) for ID bounded domain: if the domain has diameter D, then the switching cost alone of this algorithm is bounded by Ö(DVT) on any time interval of length т. Such a property is erucial in [ZCP22a] for the construction of a strongly adaptive OCO with memory algorithm. However, the proof in [ZCP22a] critically relies on hard-thresholding a betting fraction, which, as we demonstrated in Section 2.2, is suboptimal. In contrast, our new result simultaneously achieves this property and the optimal augmented regret bound.
3 LEA with switching cost
Our improved results can also be applied to LEA with switching cost, leading to the first comparator adaptive algorithm there. Conversion techniques (from OLO to LEA) without switching costs were studied in [LS15, OP16], and since then, they have become standard tools for the online learning community. Here we present a different view on this conversion problem, based on its connection to the well-known constrained domain reduction [CO18] (surveyed in Appendix B). In particular, leads to a mechanism for incorporating switching costs, with a clear geometric interpretation.
The setting of LEA with switching cost is a special case of the high-dimensional OLO problem (Appendix B). Let d be the number of experts, and we define the domain X' as the d-dimensional probability simplex Add) Loss gradients Jr satisfy l1g:llo S G, and switching costs are measured by the L1 norm. The performance metric is still the augmented regret, now defined as
T-1
Regret = Σ (g,, Ft u)
Σ
- - 1111
However, the main difference with OLO is the form of comparator adaptive bounds - here we aim at Regret> (u) = O(v (L(w(==) where π E Add) is prior chosen at the beginning. Achieving such a root KI bound relies on techniques different from the OLO setting.
Existing approaches [LS15, OP16] have the following procedure. Given a 1D OLO algorithm that predicts on R,, independent copies created for each coordinate and updated using certain surrogate losses. A meta-algorithm queries the coordinate-wise predictions {Wr,;; E [1 d}} collects them into weight vector w; [w,, 1,,.,, Wr.a], and finally predicts the scaled weight x frt=w//lue w,/llur, I|, on (d). Despite its general success, such an approach has a discontinuity problem when switching costs are incorporated if two consecutive weights we and W are both close the origin, then simply scaling them to A(d) can lead to a large switching cost, even when |/w W I is small. This problem is exacerbated by the typical setting' of w = 0, due to the associated analysis. graphical demonstration provided in Figure 1 (Left).
In contrast, our solution is based on a unified view of the LEA-OLO reduction and the constrained domain reduction [CO18]. Starting without switching costs, we observe that the general Banach version of the latter can also convert OLO to LEA, therefore specialized techniques are not required
'When Wa = 0. æz can be arbitrary A(d by definition. However, as changes continuously w.r.t. the observed information, could hover around 0 some point, thus experiencing the sketched problem.

---

WE
We
Existing approaches
Our approach
Black: when weights are inside ((d)
X
Xt
Green: when weights are outside A(d)
Xt+1
W++1
Xt+1
We+1
Wt
W
A(d)
A(d)
Wz+1
W2+1
Figure I: Switching costs in LEA-OLO reductions. Left: existing approaches. Right: ours, where the projection of contains two cases. (i) ||w|]| 1, shown in green; (it) ||w:]] ||]l<] 1, shown in black.
for this task. Algorithmically, we set I2 E arg min ze ( || wella as opposed to I; = wt/ //xx II The surrogate losses for the base algorithms are also different, which we elaborate in Appendix C.3.
A major benefit of this unified view is the non-uniqueness of the L1 norm projection - if || < 1, then any 2t (d) satisfying { 2 we,; Vi} minimizes || - well, on Add). This brings more flexibility to the algorithm design. Specifically,
adopt
1. the orthogonal projection 2; w, d d [ewlll) when ||wl| 1; the scaling 2, w ///lw/l12 when [ 1.
The orthogonal projection is better for controlling switching costs, as shown in Figure 1 (Right). Concretely, this leads to the first comparator adaptive algorithm for LEA with switching costs.
Theorem 2. For LEA with switching cost, given any prior т in the relative interior of (dd) Algo- rithm 7 from Appendix C.2 guarantees
T-1
Ir J2 u) +
Σ
a - xe+1ll1 (VTV(ul))) - (LL()l)))KKL(Il)) +1] OV(AG+(+V)
for all u E (d) and E+
We emphasize two strengths of this bound.
1. Since it is comparator adaptive, such a bound only implicitly depends on d through the divergence term /TV KL. In favorable cases we may have a good prior π such that (u]|[))-KL(x// = O(1); this will save us vlog d factor compared to minimax algorithms (with switching costs), such as Follow the Lazy Leader [KV05] and Shrinking Dartboard [GVW10].
Even without switching costs, we improve the VKL divergence term in existing comparator adaptive bounds [CFH09, LS15, OP16] to vTV KL. The latter better since (i) TV is al- ways less than 1, and (fi) there exist q E (d) such that TV(plgg) KL[pp (q) S 1 but KL(pllg) Vlog o o() (cf. Appendix C.3). In other words, compared to /KL, the <TV KL bound is never worse (up constants), and can save at least (log d/ factor in certain cases. Generalizations of root KL to f-iieergges have been considered in [Alq21, NBC+21], but to our knowledge, existing algorithm guarantees better divergence term than root KL.
Experiment We complement our theoretical results by experiments on a portfolio selection task. Due to limited space, it is presented in Appendix D.
Conclusion
We defer discussions the conclusion, limitations and future works Appendix E.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their feedback. This research was partially supported by the NSF under grants 118-1914792, DMS- 166444464 and CNNS166566) by the ONR under grants N00014- 19-1-2571 and N00014-21-1-2844, by the DOE under grants DF-AR-0001282 and FF-F0090966 by the NIH under grants R01 GM135930 and UL54 TR004130, and by Boston University.
10

---

References
[9] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, pages 111-119. PMLR, 2019.
[ABL*13) 13] Lachlan Andrew, Siddharth Barman, Katrina Ligett, Minghong Lin, Adam Meyerson, Alan Roytman, and Adam Wierman, A tale of two metries: Simultancous bounds competitiveness and regret. In Conference on Learning Theory, pages 741-763. PMLR, 2013.
[AHM15] Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversarics with memory: price of past mistakes, Advances Neural Information Processing Systems, 28, 2015.
[Alq21] Pierre Alquier. Non-exponentially weighted aggregation: Regret bounds for unbounded loss functions. In International Conference on Machine Learning, pages 207-218. PMLR, 2021.
[AT18] Jason Altschuler and Kunal Talwar. Online learning over a finite action set with limited switching. In Conference On Learning Theory, pages 1569-1573, PMLR, 2018.
[BCKP21] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit, Power of hints for online learning with movement costs. In International Conference on Artificial Intelligence and Statistics, pages 2818 2826. PMLR, 2021.
[BEZ20a] Erhan Bayraktar, Ibrahim Ekren, and Xin Zhang. Finite-time 4-expert prediction problem. Com- munications in Partial Differential Equations, 45(7):714-757, 2020.
[BEZ20b] Erhan Bayraktar, Ibrahim Ekren, and Yili Zhang. On the asymptotic optimality of the comb strategy for prediction with expert advice. The Annals of Applied Probability, 3066)25177-2566 2020.
[BK99] Avrim Blum and Adam Kalai, Universal portfolios with and without transaction costs. Muchine Learning, 35-3):193-205, 1999.
[BLLS19] Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Competitively chasing convex bodies. In Proceedings of the 51st Annual ACM SIGACT Symposiun on Theory of Computing. pages 861-868, 2019.
[CBDS13] Nicolo Cesa- Bianchi, Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. Advances in Neural Information Processing Systems, 26, 2013.
[CBL06] Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[CF1109] Kamalika Chaudhuri, Yoav Freund, and Daniel J Hsu. A parameter-free hedging algorithm. Advances in neural information processing systems, 22, 2009.
[CGW18] Niangjun Chen, Gautam Goel, and Adam Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. Conference On Learning Theory, pages 1574-1594. PMLR, 2018.
[CLO22] Keyi Chen, John Langford, and Francesco Orabona. Better parameter-free stochastic optimization with ode updates for coin-betting. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 6239-6666600 6239-6247, 2022.
[CLW21] Liyu Chen, Haipeng Luo, and Cu Wei. Impossible tuning made possihle: A new expert algorithm and its applications. In Conference Learning Theory, pages 1216-1259. PMLR, 2021.
[CO96] Thomas Cover and Erik Ordentlich. Universal portfolios with side information. IEEE Transac- tions on Information Theory, 42(2):348-363, 1996.
[CO18] Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in banach spaces. In Conference On Learning Theory, pages 1993-1529 PMLR, 2018
[Cov91] Thomas M Cover. Universal portfolios. Mathematical Finance, 1(1):1-29, 1991.
[Cut19] Ashok Cutkosky. Combining online learning guarantees. In Conference on Learning Theory. pages 895-913, 913, PMLR, 2019.

---

[Cut20] Ashok Cutkosky. Parameter-free, dynamic, and strongly-adaptive online learning. In International Conference Machine Learning, pages 2250-2259. PMLR, 2020.
[CV10] Alexey Chernov and Vladimir Vovk. Prediction with advice of unknown number of experts. In Proceedings of the Twenty-Sixh Conference on Uncertainty Artificial Intelligence, pages 117-125, 2010.
[CYLK20] Lin Chen, Qian Yu, Hannah Lawrence, and Amin Karbasi. Minimax regret of online convex optimization: No phase transition. Advances Neural Information Processing Systems, 33:3477-3486, 2020.
[DGSS15] Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. In International Conference on Machine Learning, pages 1405-1411. PMLR, 2015.
[DHS1I] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 2011.
2011.
[DK20] Nadejda Drenska and Robert V Kohn. Prediction with expert advice: A PDE perspective. Journal of Nonlinear Science, 30(1): 1):1377173,, 2020.
[DM19] Amit Daniely and Yishay Mansour. Competitive ratio vs regret minimization: achieving the best of both worlds. In Algorithmic Learning Theory, pages 333-368. PMLR. 2019.
[Doc16] Robert Dochow. Online algorithms for the portfolio selection problem. Springer, 2016.
[Doo84] Joseph Doob. Classical potential theory and its probabilistic counterpart. Springer, 1984.
[FRS15] Dylan Foster, Alexander Rakhlin, and Karthik Sridharan. Adaptive online learning. Advances Neural Information Processing Systems, 28:3375-3333 -3833,33333033 2015.
[RSS18] Dylan Foster, Alexander Rakhlin, and Karthik Sridharan. Online learning: Sufficient statistics and the Burkholder method. In Conference On Learning Theory, pages 3028-3064. PMLR, 2018.
[Fuj08] Takahiko Fujita. random walk analogue of Lévy's 's theorem. Studia scientiarum mathematicarum Hungarica, 45(2):223-233, 2008
[GHP22] Laura Greenstrect, Nicholas JA Harvey, and Victor Sanches Portella, Efficient and optimal fixed- time regret with two experts. In International Conference on Algorithmic Learning Theory, pages 436-464. PMLR, 2022.
[GLSW19] Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman, Beyond online balanced descent: An optimal algorithm for smoothed online optimization. Advances in Neural Information Processing Systems, 32, 2019.
[Gof14] Eyal Gofer. Higher-order regret bounds with switching costs. In Conference Learning Theory, pages 210 243. PMLR, 2014.
[GVW10] Sascha Geulen, Berthold Vöcking, and Melanie Winkler. Regret minimization for online buffering problems using the weighted majority algorithm. In Conference on Learning Theory, pages 132-143, 2010.
[Haz16] Elad Hazan. Introduction online convex optimization. Foundations and Trends@ Optimization. 233-5):15--325, 2016.
[HLPR20] Nicholas JA Harvey, Christopher Liaw, Edwin A Perkins, and Sikander Randhawa. Optimal anytime regret for two experts. In 2020 IEEE 6l Annual Symposium on Foundations of Computer Science (FOCS), pages 1404-144 1415. IEEE, 2020.
[HSSW98] David P Helmbold, Robert Schapire, Yoram Singer. and Manfred K Warmuth. On-line portfolio selection using multiplicative updates. Mathematical Finance, 8(4):325-347, -47, 1998.
[JC22] Andrew Jacohsen and Ashok Cutkasky. Parameter-free mirror descent. In Conference on Learning Theory, pages 41 4160-4211. PMLR, 2022.
[J019] Kwang-Sung Jun and Francesco Orabona. Parameter-free locally diffcrentially private stochastic subgradient descent. arXiv preprint weXiv:1911.09550 2019.
KKW20J Vladimir A Kobzar, Robert V Kohn, and Zhilei Wang. New potential based bounds for prediction with expert advice. In Conference Learning Theory, pages 2370 2405. PMLR, 2020.
12

---

[Kle13] Achim Klenke. Probubility theory: comprehensive course. Springer Science & Business Media, 2013.
[KS10] Robert V Kohn and Sylvia Serfaty. A deterministic -bared approach to fully nonlinear parabolic and elliptic equations. Commanications on pure and applied mathematics, 63(10)11298- 13500, 2010.
[Kud82] R Kudžma, Ito's formula for random walk. Lithuanian Mathematical Journal, 2203):302-366, 1982.
[KV02] Adam Tauman Kalai and Santosh Vempala. Efficient algorithms for universal portfolios. Journal Machine Learning Research, pages 423 023-440, 2002.
[KV05] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307, 2005.
[KVE15] Wouter M Koolen and Tim Van Erven. Second-order quantile methods for experts and combinato- rial games. In Conference on Learning Theory, pages 1155 1175. PMLR, 2015.
[LH14] Bin Li and Steven CH Hoi. Online porttolio selection: A survey, ACM Computing Surveys (CSUR), 46(3):1-3,, 2014.
[LQL20] Yingying Li, Guannan Qu, and Na Li. Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit. IEEE Transactions on Automatic Control, 66( 66(10))7761- 4768, 2020.
[LS115] Haipeng Luo and Robert Schapire. Achieving all with no parameters: Adanormalhedge. In Conference on Learning Theory, pages 1286-1304. PMLR, 2015.
[LWZ18] Haipeng Luo, Chen-Yu Wei, and Kai Zheng. Efficient online portfolio with logarithmic regret. Advances in Neural Information Processing Systems, 31, 2018.
[MK20] Zakaria Mhammedi and Wouter M Koolen. Lipschitz and comparator-norm adaptivity in online learning. In Conference on Learning Theory, pages (887. PMLR, 2020.
[MO14] H Brendan McMahan and Francesco Orabona. Unconstrained online linear learning in hilbert spaces: Minimax algorithms and normal approximations. Conference on Learning Theory, pages 1020-1039. PMLR, 2014.
[MR22] Zakaria Mhammedi and Alexander Rakhlin. Damped Online Newton Step for portfolio selection. In Conference on Learning Theory, pages
PMLR, 2022.
[NBC+21] Jeffrey Negrea, Blair Bilodeau, Nicolò Campolongo, Francesco Orabona, and Dan Roy. Minimax optimal quantile and semi-adversarial regret via root-logarithmic regularizers. Advances in Neural Information Processing Systems, 34, 2021.
[OLL17] Laurent Orseau, Tor Lattimore, and Shane Legg. Soft-bayes: Prod for mixtures of experts with log-loss. International Conference on Algorithmic Learning Theory, pages 372-399. PMLR, 2017.
[OP16] Francesco Orahona and Dávid Pál. Coin betting and parameter-free online learning. Advances in Neural Information Processing Systems, 29, 2016.
[Ora13] Francesco Orabona. Dimension free exponentiated gradient. Advances Neural Information Processing Systems, 26, 2013.
[Ora19] Francesco Orabona. modern introduction online learning. arXiv preprint 1912v
2019.
[OT17] Francesco Orabona and Tatiana Tommasi. Training deep networks without learning rates through coin betting, Advances in Neural Information Processing Systems, 30:2160-211 -2700, 2017.
[PLH22] Victor Sanches Portella, Christopher Liaw, and Nicholas JA Harvey. Continuous prediction with experts' advice. arXiv preprint arXiv:2206. 00236, 2022.
[Rok17] Dmitry B Rokhlin. PDE approach to the problem of online prediction with expert advice: a construction of potential- based strategies. arXiv preprint 7755v:1705.0109,, 2017.
[Se120] Mark Sellke. Chasing convex bodies optimally. In Proceedings of the Fourteenth Annual ACM- SIAM Symposium Discrete Algorithms, pages 1509-1518 SIAM, 2020.
13

---

[Sim20] Max Simchowitz. Making non-stochastic control (almost) as easy stochastic. Advances in Neural Information Processing Systems, 33:18318-18329, 2020.
[SK21] Uri Sherman and Tomer Koren. Lazy OCO: Online convex optimization switching budget. In Conference on Learning Theory, pages 3972-3988. PMLR, 2021.
[SM12] Matthew Streeter and Brendan Mcmahan. No-regret algorithms for unconstrained online convex optimization. Advances in Neural Information Processing Systems, 25, 2012.
[SS11] Shai Shalcv-Shwartz. Online learning and online convex optimization. Foundations and trends in Machine Learning, 4(2):107-194, 2011.
[SSH20] Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
[vdH19] Dirk van der Hoeven. User-specified local differential privacy in unconstrained adaptive online learning. Advances Neural Information Processing Systems, 32, 2019.
[WWYZ21] Guanghui Wang, Yuanyu Wan, Tianbao Yang, and Lijun Zhang. Online convex optimization with continuous switching constraint. Advances in Neural Information Processing Syxtems, 34, 2021.
[ZAK22] Julian Zimmert, Naman Agarwal, and Satyen Kale. Pushing the efficiency-regret pareto frontier for online learning portfolios and quantum states. Conference on Learning Theory, pages 182-226. PMLR, 2022.
[ZCP22a] Zhiyu Zhang, Ashok Cutkosky, and Ioannis Paschalidis. Adversarial tracking control via strongly adaptive online learning with memory. In International Conference on Artificial Intelligence and Statistics, pages 8458 8492. PMLR, 2022.
[ZCP22b] Zhiyu Zhang, Ashok Cutkosky, and loannis Paschalidis. PDE-based optimal strategy for uncon- strained online leamning International Conference on Machine Learning, pages 26085 26115. PMLR, 2022.
[hhu14] Kangping Zhu. Two problems in applications of PDE. PhD thesis, New York University, 2014.
[Zin03] Martin Zinkevich. Online convex programming and generalized intinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pages 928-99 928-936, 2003.
[Z]LY21] Lijun Zhang, Wei Jiang, Shiyin Lu, and Tianbao Yang. Revisiting smoothed online learning. Advances in Neural Information Processing Systems, 34, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Appendix E.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The present work is mainly theoretical.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] In supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix D.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes]
14

---

(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [No] Our experiments are not computationally demanding.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "kXxikA6Sogq", "reviewer": "Reviewer_PZQr", "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. ", "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? \n\n(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.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1. 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.\n\n2. This paper is clear-written and technically sound. The theoretical analyses are supported by rigorous proofs which are sound to me.\n\nWeakness:\n\nMy main concerns are contribution and novelty.\n1. 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.\n\n2. 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VuQRq1NJWBd", "reviewer": "Reviewer_NFWC", "summary": "This theoretical article is about \"parameter-free\" regret minimization for (linear) online learning with switching cost\n\nFor 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.\nIt 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.\n\nThe 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\n\nThe 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.\n\nThe 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.\n\nThe proofs are detailed along 20 pages of supplementary material. Some code is provided as well.", "questions": "The algorithm being not really parameter-free, why not change the title to \"Optimal almost-parameter-free Online Learning with Switching Cost\" ?\nYou 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 ?\nDo the coin betting strategy proposed in [Zhang et al. 2022a] require such parameters ? Is the comparison fair on that ground ?\n", "limitations": "The limitations are explicitly given in the conclusion.\nThe 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\". \n\nAdapting to changing costs and dropping the G parameter is left as future work.\n", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weaknesses / General remarks:\n- 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.\n- 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.\n\nStrengths:\n- 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.\n- 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).\n- Once into it, the paper is correctly written, and the maths seem solid (but I did not check the proofs).\n- The author provided a code to reproduce their experiments in supplementary material.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SAI4Xa3y7L", "reviewer": "Reviewer_KR3f", "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.", "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?\n\n2. 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?\n\n3. 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?\n\n4. 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?\n\n5. 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.\n", "limitations": "Not much.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. 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.\n\n2. 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.\n\n3. 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.\n\nWeaknesses: please mainly refer to the “Questions” part below.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "6JbO2KjduAq", "reviewer": "Reviewer_cFUB", "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.\n", "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?\n", "limitations": "None.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nQuality & 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3algeuBdqST", "reviewer": "Reviewer_1xnT", "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.", "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.\n\n2. 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?\n\n3. Is it easy and fast to compute the discrete derivative $\\bar{\\nabla}_SV(t,S)$ in Algorithm 1, when the dimension is not small?\n\n4. What does $||\\cdot||_*$ stand for? (e.g., in line 94)", "limitations": "The authors adequately discuss the limitation and potential improvement for the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. 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.\n2. The key idea that incorporating switching costs by scaling on the dual space seems new and interesting.\n3. Overall the paper is well-organized and mostly easy to follow.\n\nWeakness:\n1. 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.\n2. Please see my additional questions/concerns in the next part.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept