An Online Algorithm for Smoothed Regression and LQR Control

Gautam Goel Adam Wierman

Abstract
We consider Online Convex Optimization (OCO)
in the setting where the costs are m-strongly
convex and the online learner pays a switching cost for changing decisions between rounds.
We show that the recently proposed Online Balanced Descent (OBD) algorithm is constant competitive in this setting, with competitive ratio
3 + O(1/m), irrespective of the ambient dimension. We demonstrate the generality of our approach by showing that the OBD framework canbe used to construct competitive algorithms fora variety of online problems across learning andcontrol, including online variants of ridge regression, logistic regression, maximum likelihood estimation, and LQR control.

1. Introduction

place strong restrictions on the class of loss functions,or (iii) require algorithms to make use of predictions of
future cost functions. For example, a series of papers(LWAT11), (BGK+ 15) developed competitive algorithms
for one-dimensional action spaces. Until earlier this year
there were no known algorithms that were competitive for
SOCO beyond one dimension without requiring the use ofpredictions. Finally, (CGW18) presented the first algorithm
that is constant-competitive beyond one dimension, but thealgorithm was shown to be constant competitive only inthe case of polyhedral cost functions, a restrictive class that
does not include most loss functions used in machine learning. Beyond this result, the most general positive results all
assume predictions of future cost functions are available,
e.g. (LLWA12), (CAW+ 15), (CCL+ 16), (LQL18).
The existing work on SOCO highlights a crucial open question: Does there exist a competitive algorithm for highdimensional SOCO problems with cost functions that capture standard losses for online learning problems, e.g., logistic loss or least-squares loss?

In this paper we study the problem of smoothed online convex optimization (SOCO), a variant of OCO where the online learner incurs a switching cost for changing its actions
between rounds. More concretely, the online learner plays
a series of rounds t = 1 . . . T . In each round, the learnerreceives a convex loss function ft , picks a point xt from a
convex action space χ ⊂ Rd , and pays a hitting cost ft (xt )as well as a switching cost c(xt , xt−1 ) which penalizes thelearner for changing its action between rounds.

In this paper we answer this question by proving that the
recently introduced Online Balanced Descent (OBD) algorithm is constant-competitive for SOCO with strongly
convex costs. Additionally, highlighting the importance ofthe class of strongly convex costs, we show that the OBD
framework can be used to construct the first competitive algorithms for problems as diverse as online ridge regression,
online logistic regression, and LQR control, which was notpossible with previous approaches.

This problem was first introduced in the context of the
dynamic management of service capacity in data centers(LWAT11), where the switching costs represent the performance and wear-and-tear costs associated with changing
server configurations. Since then, SOCO has attracted considerable interest, both theoretical and applied, due to its
use in dozens of applications across learning, distributed
systems, networking, and control, such as speech animation (KYTM15), video streaming (JdV12), management ofelectric vehicle charging (KG14), geographical load balancing (LLWA12), and multi-timescale control (GCW17).
See (CGW18) for an extensive list of applications.

Contributions of this paper. This paper makes two main
contributions to the literature on SOCO.

Unfortunately, despite a large and growing literature, all existing results identifying competitive algorithms for SOCO
either (i) place strong restrictions on the action space, (ii),First, in Section 3 we show that OBD is constant competitive for SOCO when the costs are strongly convex (Theorem 1). This establishes OBD as the first constant competitive algorithm for strongly convex costs beyond onedimensional action spaces. The key to our proof is a novel
potential function argument that exploits essential properties of `2 geometry. In particular, controlling the change in
potential rests upon comparing the side lengths of certain
triangles (see Figure 1), which can be done via the Law of
Cosines.
Second, in Section 4 we show novel applications of OBD
to problems arising in statistics, learning, and control, in-An Online Algorithm for Smoothed Regression and LQR Control

cluding ridge regression, logistic regression, and maximum
likelihood estimation. A highlight of this section is a reduction of LQR control to SOCO, giving the first competitivealgorithm for LQR control (results for LQR control typically make strong distributional assumptions). We emphasize that none of these applications could be handled byprevious work on SOCO, which highlights the importanceof deriving a competitive bound for OBD in the strongly
convex setting.
Related work. There is a vast literature on OCO; fora recent survey see (H+ 16). OCO with switching costs
was first studied in the scalar setting in (LWAT11), whichused SOCO to model dynamic right-sizing in data centersand gave a 3-competitive algorithm. In subsequent work,(BGK+ 15) improved the competitive ratio to 2, also in thescalar setting. The first constant-competitive algorithm beyond one dimension was given in (CGW18), which introduced the OBD framework and showed that it was competitive for SOCO with polyhedral costs. The results inthis paper highlight that OBD is also constant-competitive
for strongly convex cost functions, a class that is particularly important for learning and control applications, and iswholly disjoint from the class of polyhedral cost functions
when the minimizer of the cost function is zero.
A special case of SOCO is the Convex Body Chasingproblem, first introduced in (FL93). The connection between Convex Body Chasing and SOCO was observedin (ABN+ 16). A recent series of papers (BBE+ 18),
(ABC+ 18) identified competitive algorithms in the setting
where the bodies are nested.
Before this paper, the only class of SOCO problems forwhich positive results for strongly convex cost functions
existed is when the learner had access to accurate predictions of future cost functions. The study of SOCOwith predictions began with (LLWA12) and then continued with a stream of work in the following years, e.g.,(CAW+ 15; CCL+ 16). The most relevant to this work is(LQL18), which shows a lower bound on the dynamic regret of SOCO with strongly convex cost functions.
In Section 4 we apply OBD to diverse problems like maximum likelihood estimation and LQR control. These problems have been widely studied; we refer the reader to(BV04) and (AM10) for a survey.
Finally, we note that SOCO can be viewed as a continuousversion of the classic Metrical Task Systems (MTS) problem, one of the most widely studied problems in the online
algorithms community, e.g (BLS92), (BBBT97), (BB00).
A special case of the MTS is the celebrated k-server problem, first proposed in (MMS90), which has received significant attention in recent years, for example in (BCL+ 18).

2. Smoothed Online Convex Optimization
An instance of SOCO consists of a convex action set χ ⊂Rd , an initial point x0 ∈ χ, a sequence of non-negative
convex costs f1 . . . fT : Rd → R+ , and a non-negative
function c : Rd × Rd → R+ . In each round t, the online
learner observes the cost function ft , picks a point xt , andpays the sum of the hitting cost ft (xt ) and the movement
or switching cost c(xt , xt−1 ). The switching cost acts asa regularizer, penalizing the online learner for changing its
decisions between rounds. The goal of the online learneris to minimize its aggregate cost so as to approximate theoffline optimal cost:
min

T
X

x1 ...xT ∈χft (xt ) + c(xt , xt−1 )t=1More generally, xt could be matrix-valued and ft , c could
be functions on matrices. Note that we make no restrictions on the sequence of cost functions f1 . . . fT other thanstrong convexity; they could be adversarial, or even adaptively chosen to hurt the online learner.
We emphasize that SOCO differs from OCO in two important ways. Firstly, unlike in OCO, the costs incurredin each round of SOCO depend on the previous choice,coupling the online learner’s decisions across rounds. Secondly, the online learner can observe the cost function ft
before picking xt . This is a standard assumption in the
SOCO literature, e.g. in (BGK+ 15), (LWAT11), (CGW18)
and isolates the complexity of SOCO onto the coupling
across timesteps due to the switching costs instead of theuncertainty in the costs.
In this paper, we measure the performance of OBD in termsof its dynamic regret and competitive ratio. The dynamic
regret is defined asTX

ft (xt ) + c(xt , xt−1 ) −

t=1

" T
X

#
ft (x∗t ) + c(x∗t , x∗t−1 )t=1Here x1 . . . xT are the points picked by the online learnerand x∗1 . . . x∗T are the offline optimal points. We note that
this is a more natural performance metric for SOCO thanstatic regret, since the main motivation for SOCO is to understand the effects of switching costs on online learning.
In contrast, in the static regret setting the comparator nevermoves and hence incurs no switching cost, making it a lessideal performance metric for SOCO.
Instead of using an additive metric the competitive ratio
uses a multiplicative metric:
PT

t=1 ft (xt ) + c(xt , xt−1 )∗∗∗t=1 ft (xt ) + c(xt , xt−1 )PT

An Online Algorithm for Smoothed Regression and LQR Control

We note that (ABL+ 13) showed that, in general, no online
algorithm can have both sublinear static regret and constantcompetitive ratio.
Much attention has been focused on the setting where theswitching cost is a norm: c(xt , xt−1 ) = kxt − xt−1 k,e.g. (LWAT11), (BGK+ 15). Note that in the onedimensional setting, all `p norms are identical, making the
choice of norm somewhat vacuous. The first algorithm towork beyond the one dimensional setting was proposed in(CGW18), which considered a setting where the switching
cost is given by the Euclidean distance and the loss functions are polyhedral, meaning that they at grow at least linearly as one moves away from the minimizer.
We instead focus on the setting where the cost functions
f1 . . . fT are m-strongly convex with respect to the Euclidean norm and the switching cost is quadratic:c(xt , xt−1 ) =1
kxt − xt−1 k22
2

In Section 4, we show that OBD can be used with many important loss functions, such as the least-squares loss and the`2 regularized logistic loss, none of which could be handled
by previous work.
We assume that the domain χ is all of Rd . Note that thispresents no real restriction, since we can always defineft (x) = ∞ for all x 6∈ χ. The objective becomesmin

x1 ...xT ∈RdTX

1ft (xt ) + kxt − xt−1 k22
2
t=1

(1)

Notation. We use k · k to denote the `2 norm. We often
use Ht and Mt to denote the hitting cost ft (xt ) and the
movement cost 12 kxt − xt−1 k2 , respectively. The offline
costs Ht∗ and Mt∗ are defined analogously. We let ALG
denote the total cost incurred by OBD across all rounds
and define OP T to be the analogous offline cost. We let vt
denote the minimizer of the cost function ft .

Algorithm 1 Online Balanced Descent (OBD)
1: for t = 1, . . . , T do
2:
Receive ft . Let vt be the minimizer of ft .
3:
Let x(l) = ΠKtl (xt−1 ). Initialize l = ft (vt ). HereKtl is the l-sublevel set of ft , i.e., Ktl = {x |ft (x) ≤ l}.
4:
Increase l. Stop either when x(`) = vt or 12 kx(l) −xt−1 k22 = βl.
5:Set xt = x(l).
6: end for

3. A Competitive Algorithm
Our main technical result shows that a recently proposed
algorithm, Online Balanced Descent (OBD), is constantcompetitive for SOCO problems with strongly convex costfunctions.
OBD was introduced in (CGW18), where it was analyzed
for the class of polyhedral costs. The detailed workings of
OBD are summarized in Algorithm 1. The key insight of
OBD is to exploit the full geometry of the level sets of thecurrent cost function ft when choosing the point xt in sucha way as to take switching costs into account.
OBD works by iteratively projecting the previously chosen point onto a level set of the current cost function. The
level set Kt picked by OBD is the level set such that theswitching cost incurred while traveling from xt−1 to Kt is
equal to βft (xt ), where xt is the projection onto Kt andβ is the balance parameter which can be tuned to get different performance guarantees. We note that OBD can be
efficiently implemented via a binary search over the levelsets (CGW18).
We can now state our main result, a bound on the competitive ratio of OBD for strongly convex costs.
Theorem 1. OBD is competitive for the problem (1) for all4β> m. Furthermore, if β is set to be 2 + 10
m , the competitive ratio of OBD is at most 3 + O(1/m), irrespective of
the ambient dimension.
We note that (CGW18) proved a bound on the competitive
ratio of OBD of the form 3+O(1/α) where α measures the“steepness” of the costs. While this superficially resembles
the bound in Theorem 1, we emphasize that the settings arequite different; their work applied to the class of polyhedral cost functions while we focus on strongly convex costfunctions. In the case where the cost functions have minimum value zero these classes are wholly disjoint. We are
led to consider strongly convex costs due to the fact many
common learning and control problems have loss functions
that are strongly convex (e.g., see Section 5). Until thispaper, there existed no competitive algorithms for SOCO
problems with strongly convex costs.

An Online Algorithm for Smoothed Regression and LQR Control

4. Applications
In this section we show several applications of OBD to diverse problems across learning and control. We emphasizethat none of these applications would be possible without acompetitive algorithm for strongly convex costs, which has
not been attainable with previous approaches.
4.1. Smoothed Online Regression
We consider the problem of a learner who wishes to fit aseries of regularized regressors or classifiers to a changing
dataset, without changing the estimators too much between
rounds. This is naturally modeled by the objectiveminθ1 ...θT ∈Rd

T
X
t=1

ft (θt ) +λ2
λ1kθt k22 + kθt − θt−1 k22
2
2

(2)

Here ft represents an estimation or classification task attimestep t, θt is the regressor at time t, and λ1 , λ2 areparameters that control the strength of the `2 and smoothing regularizations, respectively. We impose no constraint
on ft other than convexity; in particular, ft need not
be strongly convex (though if ft happens to be strongly
convex, we can optionally drop the regularization term
λ1
2
2 kθt k ). OBD gives a constant-competitive algorithm inthis setting:
Corollary 1. The competitive ratio of OBD with balanceparameter β = 2 + 10
m on problem 2 is 3 + O(λ2 /λ1 ).
Before we turn to the proof, we emphasize that the boundon competitive ratio does not vary with respect to dimension; hence OBD can be applied to estimation problems
with thousands or millions of parameters.
Proof. We first divide the objective by λ2 . Notice thatλ1kθt k22 is (λ1 /λ2 )the function f˜t (θ) = λ12 ft (θ) + 2λ2strongly convex in θ whenever ft is convex, hence Theorem 1 implies that OBD achieves competitive ratio 3 +O(λ2 /λ1 ).

• Maximum Likelihood Estimation. More generally,
we can perform smoothed online maximum likelihood
estimation using OBD. Here θt are parameters of amodel and ft (θt ) is the likelihood function of somedataset at time t. If the likelihood function is convex
then OBD can be applied. For example, the problemof estimating a series of covariance matrices Σt of aseries of Gaussian distributions N (0, Σt ) given independent samples arranged as a matrix Yt can be posedas the problem
min(ΣY ) − log det ΣΣwhich is a convex optimization problem (see (BV04),
p. 357). We can apply OBD over the set of positive
definite matrices to find a series of covariance matrices Σt that fit the data well but don’t vary too much
between rounds.
4.2. Linear Quadratic Regulator (LQR) control
Our second application comes from the controls community. Consider the classical problem of LQR control:min

u1 ...uT

T
X
1

1
x0t Qt xt + u0t Rut22
t=1

with dynamics given by
xt+1 = Axt + But + wt
Here u is a control action, x a state variable, and Qt , R are
assumed to be positive definite. Usually, the noise increments wt are assumed to be i.i.d. Gaussian, and the goal
is to design a control policy to minimize the expected cost.
Instead of an in-expectation result, we can use OBD to design a controller with a strong pathwise guarantee, withno distributional or boundedness assumptions on the noise.
We focus on the setting where A = I, i.e. the system isstationary in the absence of noise or control actions.

• Ridge Regression. We take ft (θ) = kXt θ − yt k2 ,where Xt ∈ Rn×d is a data matrix and yt ∈ Rn is the
response variable.

Corollary 2. Suppose that A = I and B is invertible, andthe matrices Qt each have their lowest eigenvalue bounded
below by λ > 0. The LQR problem can be rewritten as a
SOCO problem, and the competitive ratio of OBD is
λmax (R)3+O.
λmin (B)2 λ• Logistic Regression.
We take ft (θ)=
Pnt>− n1t i=1
log (1 + e−yi,t θ xi,t ) where xi,t ∈ Rd isa vector of features, yi,t ∈ {0, 1} is a binary outcome,and nt is the number of samples in round t. OBD
hence fits a series of binary classifiers which don’tvary too much between rounds. Our approach easily
extends to the multiclass setting as well.

Note that λmin (B) can be interpreted as a lower bound on
the gain of the control action u; intuitively, systems withhigh control gain are easier to regulate, since each control action gets amplified. Similarly, it is intuitive that as
λmax (R) decreases the competitive ratio improves, since
R controls the cost incurred by using the controller.

Our approach applies to many common learning problems:An Online Algorithm for Smoothed Regression and LQR Control

Appendices

Proof. We haveφ(xt , x∗t )Proof of Theorem 1
To prove Theorem 1, we use the potential function
φ(x, x∗ ) = ηkx − x∗ k2 . Clearly φ(x, x∗ ) ≥ 0 andφ(x0 , x∗0 ) = 0. Before we turn to the proof of Theorem 1,
we prove a series of crucial lemmas relating to the potentialfunction. Lemmas 1 and 2 show how the potential changes
depending on the relative positions of its arguments, andhighlight the role of the geometry associated with the `2
norm. Lemma 3 relates the potential to the hitting costs atevery timestep.

=ηkxt − x∗t k2≤

η(kxt − vt k + kx∗t − vt k)2≤2ηkxt − vt k2 + 2ηkx∗t − vt k2
4η
4η
Ht + Ht∗mm≤

The first inequality is just the triangle inequality; the second follows from the AM-GM inequality; and in the last2
step we used the fact that ft (x) ≥ m
2 kx − vt k .

Lemma 1. The change in potential satisfies
φ(a, c) − φ(a, b) ≤ −φ(b, c)
for all a, b, c ∈ Rd such that the angle θ between the vectors a − c and b − c lies in [π/2, 3π/2].
Proof. Consider the triangle with vertices a, b, c. According to the Law of Cosines we have:

Now we return to the proof of Theorem 1. Note that it suffices to show that OBD is constant competitive in the casewhere minimum value of each cost function is zero, sinceotherwise the competitive ratio can only improve. In thiscase, we always have Mt = βHt since Ht shrinks to zero
as we move towards the minimizer while Mt increases.

ka − bk = ka − ck + kb − ck − 2ka − ckkb − ck cos θ.

Proof. To bound the cost charged to OBD in each step, we
first consider two cases.

Rearranging gives

Case 1: Ht ≤ Ht∗

2

2

2

ka − ck2 − ka − bk2 = −kb − ck2 + 2ka − ckkb − ck cos θ.
Since θ lies in [π/2, 3π/2], the cosine term must be nonpositive, immediately yielding the claim.

This case is easy; the cost charged to OBD is
Ht + Mt + ∆φ ≤≤Lemma 2. The change in potential satisfies
φ(a, c) − φ(a, b) ≤ 2φ(b, c) + φ(a, b)
for all a, b, c ∈ Rd .

4η4η
Ht + Mt + Ht + Ht∗
m
m

8η
∗
Ht
1+β+
m

Here in the first inequality we threw away the negative potential term and used Lemma 3. In the second inequality
we used the fact that Mt = βHt and the inequality defining the case.

Proof. We apply the Law of Cosines again:

Case 2: Ht > Ht∗ka − ck2 − ka − bk2 = kb − ck2 − 2ka − bkkb − ck cos θThis is the hard case. Unlike in the previous case, we cannot directly bound the cost charged to OBD in terms of theoffline cost, since Ht∗ is less than Ht . Our strategy will be
to show that the change in potential was negative, offsetting
the hitting and movement costs incurred by OBD.

where θ is the angle between the vectors a − b and b − c.
The second term on the right is at most 2ka − bkkb − ck;
applying the AM-GM inequality to this expression gives
the claim.
Lemma 3. At all timesteps t, the potential satisfies
φ(xt , x∗t ) ≤4η
4η
Ht + Ht∗mm

Since Ht∗ < Ht , the offline point x∗t must lie strictly in theinterior of Kt , where Kt is the Ht -level set of ft . Noticethat the angle θ made between the line segments xt−1 xt
and xt x∗t must be obtuse, since xt was the projection onto
the level set, and x∗t lies strictly on the opposite side of the
supporting hyperplane tangent to Kt at xt (see Figure 1).
We haveAn Online Algorithm for Smoothed Regression and LQR Control

have:
T
X

Ht + Mt

≤

T 
X

t=1

1+β+

t=1

+

T
X

2ηMt∗ +

t=1

Figure 1. An illustration of the situation arising in Case 2. The
ellipse represents the level set Kt of ft which OBD has selected;
xt is the projection of xt−1 onto this level set. The offline pointx∗t must lie strictly inside the level set, since Ht∗ < Ht . The angle
θ must be obtuse, since x∗t lies on the other side of the supporting
hyperplane at xt , shown by the dotted line.

Ht + Mt + ∆φ

=
≤
=

≤



Ht∗

T
X
4η
t=1

m

Ht−1

1
By the balance condition, Ht = 1+β(Ht + Mt ). We immediately obtain



12η
ALG ≤ max
1+β+
, 2η OP T
m
4η
+
ALG
m(1 + β)4η< 1;
Let us assume that that β, η are picked so that m(1+β)
rearranging gives
max 1 + β + 12η
ALG
m , 2η
≤4η
OP T
Ht + Mt + (φ(xt , x∗t ) − φ(xt−1 , x∗t ))1 − m(1+β)
+ φ(xt−1 , x∗t ) − φ(xt−1 , x∗t−1 )Now we seek to minimize the competitive ratio by approHt + Mt − φ(xt , xt−1 )priately picking β, η, subject to the constraints. Notice that∗∗∗+2φ(xt , xt−1 ) + φ(xt−1 , xt−1 )the competitive ratio is always increasing in η. Since we∗Ht + Mt − ηMt + 2ηMt
know that we must have η ≥ 1 + β1 , this must be the op+φ(xt−1 , x∗t−1 )timal value of η. We can hence immediately rewrite our
optimization problem purely in terms of β:1
1 + − η Mt + 2ηMt∗



β
1
1
max 1 + β + 12
(1
+
,
2(1
+
)
m
β
β
4η
4η ∗
min4
+ Ht−1 + Ht−1
4
1 − mββ> mmm

In the first inequality we use Lemma 1 to bound the firstchange in potential and Lemma 2 to bound the second. In
the second inequality we apply the fact that Mt = βHt andLemma 3.
Bounding the competitive ratio
We have now bounded the cost charged to OBD in each of
the two cases. Putting both cases together, we see that wealways have
Ht + Mt + ∆φ

12η
m

≤

1+β+

8η
m



Note that this proves that OBD is competitive for all β >4m . Instead of trying to find the exact optimal solution,
we instead select a simple choice of β which gives a small
competitive ratio. Setting β = 2 + 10
m immediately gives
an upper bound on the competitive ratio of 3 + O(1/m) as
claimed.

Proof of Corollary 2
Proof. Defineyt =Ht∗ + 2ηMt∗

4η
4η ∗+ Ht−1 + Ht−1
m
m

t
X

Bui ,

vt = −

i=1

t
X

wi .

i=1

Notice thatx t = y t − vt ,ut = B −1 (yt − yt−1 ),so the LQR problem can be rewritten as
where we assume that β, η were picked so that η ≥ 1 + β1 .
Adding up across all timesteps and collecting terms, wemin

y1 ...yT

T
X
1

2
t=1

1
(yt −vt )0 Qt (yt −vt )+ (yt −yt−1 )0 Z(yt −yt−1 )2

An Online Algorithm for Smoothed Regression and LQR Control

where
Z = (B −1 )0 RB −1
Now define11

zt = R 2 B −1 yt ,st = R 2 B −1 vt .

The optimization problem becomesmin

z1 ...zT

T
X
1

2
t=1

1
(zt − st )0 Pt (zt − st ) + kzt − zt−1 k22
2

where
1

1

Pt = (BR− 2 )0 Qt BR− 2

This is just a special case of the SOCO problem. Noticethat the costs are strongly convex with parameter λmin (Pt ),which is bounded below by
λmin B 2 λλmax (R)which in light of Theorem 1 proves the claim.

References[ABC+ 18] CJ Argue, Sébastien Bubeck, Michael B Cohen, Anupam Gupta, and Yin Tat Lee. A
nearly-linear bound for chasing nested convex bodies. arXiv preprint arXiv:1806.08865,
2018.
[ABL+ 13] Lachlan Andrew, Siddharth Barman, Katrina
Ligett, Minghong Lin, Adam Meyerson, Alan
Roytman, and Adam Wierman. A tale oftwo metrics: Simultaneous bounds on competitiveness and regret. In Conference on Learning Theory, pages 741–763, 2013.
[ABN+ 16] Antonios Antoniadis, Neal Barcelo, Michael
Nugent, Kirk Pruhs, Kevin Schewior, andMichele Scquizzato. Chasing convex bodies and functions. In Latin American Symposium on Theoretical Informatics, pages 68–81.
Springer, 2016.
[AM10] Karl Johan Aström and Richard M Murray.
Feedback systems: an introduction for scientists and engineers. Princeton university press,
2010.
[BB00] Avrim Blum and Carl Burch. On-line learningand the metrical task system problem. Machine Learning, 39(1):35–58, 2000.

[BBBT97] Yair Bartal, Avrim Blum, Carl Burch, and Andrew Tomkins. A polylog (n)-competitive algorithm for metrical task systems. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 711–719.
ACM, 1997.
[BBE+ 18] Nikhil Bansa, Martin Böhm, Marek Eliáš,
Grigorios Koumoutsos, and Seeun William
Umboh. Nested convex bodies are chaseable.
In Proceedings of the Twenty-Ninth Annual
ACM-SIAM Symposium on Discrete Algorithms, pages 1253–1260. SIAM, 2018.
[BCL+ 18] Sebastien Bubeck, Michael B Cohen, Yin Tat
Lee, James R Lee, and Aleksander Madry.
k-server via multiscale entropic regularization. In Proceedings of the 50th Annual ACM
SIGACT Symposium on Theory of Computing,pages 3–16. ACM, 2018.
[BGK+ 15] Nikhil Bansal, Anupam Gupta, Ravishankar
Krishnaswamy, Kirk Pruhs, Kevin Schewior,
and Cliff Stein. A 2-competitive algorithm
for online convex optimization with switching costs. In LIPIcs-Leibniz International Proceedings in Informatics, volume 40, 2015.
[BLS92] Allan Borodin, Nathan Linial, and Michael E
Saks. An optimal on-line algorithm for metrical task system. Journal of the ACM (JACM),
39(4):745–763, 1992.
[BV04] Stephen Boyd and Lieven Vandenberghe.
Convex optimization. Cambridge university
press, 2004.
[CAW+ 15] Niangjun Chen, Anish Agarwal, Adam Wierman, Siddharth Barman, and Lachlan LH Andrew. Online convex optimization using predictions. In ACM SIGMETRICS Performance
Evaluation Review, volume 43, pages 191–
204. ACM, 2015.
[CCL+ 16] Niangjun Chen, Joshua Comden, Zhenhua
Liu, Anshul Gandhi, and Adam Wierman. Using predictions in online optimization: Looking forward with an eye on the past. ACM SIGMETRICS Performance Evaluation Review,
44(1):193–206, 2016.
[CGW18] Niangjun Chen, Gautam Goel, and Adam
Wierman. Smoothed online convex optimization in high dimensions via online balanced
descent. In Proceedings of the 31st Conference On Learning Theory, volume 75 ofProceedings of Machine Learning Research,
pages 1574–1594. PMLR, 2018.

An Online Algorithm for Smoothed Regression and LQR Control[FL93] Joel Friedman and Nathan Linial. On convex
body chasing. Discrete & Computational Geometry, 9(3):293–321, 1993.
[GCW17] Gautam Goel, Niangjun Chen, and Adam
Wierman. Thinking fast and slow: Optimization decomposition across timescales. In Decision and Control (CDC), 2017 IEEE 56th Annual Conference on, pages 1291–1298. IEEE,2017.
[H+ 16] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends R
in Optimization, 2(3-4):157–325, 2016.
[JdV12] V. Joseph and G. de Veciana. Jointly optimizing multi-user rate adaptation for video transport over wireless systems: Mean-fairnessvariability tradeoffs. In 2012 Proceedings
IEEE INFOCOM, pages 567–575, March2012.
[KG14] Seung-Jun Kim and Geogios B Giannakis.
Real-time electricity pricing for demand response using online convex optimization. In
Innovative Smart Grid Technologies Conference (ISGT), 2014 IEEE PES, pages 1–5.
IEEE, 2014.
[KYTM15] Taehwan Kim, Yisong Yue, Sarah Taylor, andIain Matthews. A decision tree frameworkfor spatiotemporal sequence prediction. In
Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 577–586. ACM,
2015.
[LLWA12] M. Lin, Z. Liu, A. Wierman, and L. L. H. Andrew. Online algorithms for geographical loadbalancing. In 2012 International Green Computing Conference (IGCC), pages 1–10, June
2012.
[LQL18] Yingying Li, Guannan Qu, and Na Li. Using predictions in online optimization withswitching costs: A fast algorithm and a fundamental limit. In 2018 Annual American
Control Conference (ACC), pages 3008–3013.
IEEE, 2018.
[LWAT11] M. Lin, A. Wierman, L. L. H. Andrew, and
E. Thereska. Dynamic right-sizing for powerproportional data centers.
In 2011 Proceedings IEEE INFOCOM, pages 1098–1106,
April 2011.

[MMS90] Mark S Manasse, Lyle A McGeoch, andDaniel D Sleator. Competitive algorithms
for server problems. Journal of Algorithms,
11(2):208–230, 1990.