# Online Forecasting of Total-Variation-bounded Sequences

Dheeraj Baby
<EMAIL_ADDRESS>Yu-Xiang Wang
<EMAIL_ADDRESS>
(UC Santa Barbara)

###### Abstract

We consider the problem of online forecasting of sequences of length $n$ with
total-variation at most $C_{n}$ using observations contaminated by independent
$\sigma$-subgaussian noise. We design an $O(n\log n)$-time algorithm that
achieves a cumulative square error of
$\tilde{O}(n^{1/3}C_{n}^{2/3}\sigma^{4/3}+C_{n}^{2})$ with high probability.
We also prove a lower bound that matches the upper bound in all parameters (up
to a $\log(n)$ factor). To the best of our knowledge, this is the first
_polynomial-time_ algorithm that achieves the optimal $O(n^{1/3})$ rate in
forecasting total variation bounded sequences and the first algorithm that
_adapts to unknown_ $C_{n}$. Our proof techniques leverage the special
localized structure of Haar wavelet basis and the adaptivity to unknown
smoothness parameters in the classical wavelet smoothing (Donoho et al.,
1998). We also compare our model to the rich literature of dynamic regret
minimization and nonstationary stochastic optimization, where our problem can
be treated as a special case. We show that the workhorse in those settings —
online gradient descent and its variants with a fixed restarting schedule —
are instances of a class of _linear forecasters_ that require a suboptimal
regret of $\tilde{\Omega}(\sqrt{n})$. This implies that the use of more
adaptive algorithms is necessary to obtain the optimal rate.

##  1 Introduction

Nonparametric regression is a fundamental class of problems that has been
studied for more than half a century in statistics and machine learning
(Nadaraya, 1964; De Boor et al., 1978; Wahba, 1990; Donoho et al., 1998;
Mallat, 1999; Scholkopf and Smola, 2001; Rasmussen and Williams, 2006). It
solves the following problem:

  * •

Let $y_{i}=f(u_{i})+\text{Noise}$ for $i=1,...,n$. How can we estimate a
function $f$ using data points $(u_{1},y_{1}),...,(u_{n},y_{n})$ and the
knowledge that $f$ belongs to a function class $\mathcal{F}$?

Function class $\mathcal{F}$ typically imposes only weak regularity
assumptions on the function $f$ such as boundedness and smoothness, which
makes nonparametric regression widely applicable to many real-life
applications especially those with unknown physical processes.

A recent and successful class of nonparametric regression technique called
trend filtering (Steidl et al., 2006; Kim et al., 2009; Tibshirani, 2014; Wang
et al., 2014) was shown to have the property of _local adaptivity_ (Mammen and
van de Geer, 1997) in both theory and practice. We say a nonparametric
regression technique is _locally adaptive_ if it can cater to local
differences in smoothness, hence allowing more accurate estimation of
functions with varying smoothness and abrupt changes. For example, for
functions with bounded total variation (when $\mathcal{F}$ is a total
variation class), standard nonparametric regression techniques such as kernel
smoothing and smoothing splines have a mean square error (MSE) of
$O(n^{-1/2})$ while trend filtering has the optimal $O(n^{-2/3})$.

Trend filtering is, however, a batch learning algorithm where one observes the
entire dataset ahead of the time and makes inference about the past. This
makes it inapplicable to the many time series problems that motivate the study
of trend filtering in the first place (Kim et al., 2009). These include
influenza forecasting, inventory planning, economic policy-making, financial
market prediction and so on. In particular, it is unclear whether the
advantage of trend filtering methods in estimating functions with
heterogeneous smoothness (e.g., sharp changes) would carry over to the online
forecasting setting. The focus of this work is in developing theory and
algorithms for locally adaptive online forecasting which predicts the
immediate future value of a function with heterogeneous smoothness using only
noisy observations from the past.

###  1.1 Problem Setup

1. Fix action time intervals $1,2,...,n$ 2. The player declares a forecasting strategy $\mathcal{A}_{i}:\mathbb{R}^{i-1}\rightarrow\mathbb{R}$ for $i=1,...,n$. 3. An adversary chooses a sequence $\theta_{1:n}=[\theta_{1},\theta_{2},\ldots,\theta_{n}]^{T}\in\mathbb{R}^{n}$. 4. For every time point $i=1,...,n$: (a) We play $x_{i}=\mathcal{A}_{i}(y_{1},...,y_{i-1})$. (b) We receive a feedback $y_{i}=\theta_{i}+Z_{i}$, where $Z_{i}$ is a zero-mean, independent subgaussian noise. 5. At the end, the player suffers a cumulative error $\sum_{i=1}^{n}\big{(}x_{i}-\theta_{i}\big{)}^{2}$.

Figure 1: _Nonparametric online forecasting model. The focus of the proposed
work is to design a forecasting strategy that minimizes the expected
cumulative square error. Note that the problem depends a lot on the choice of
the sequence $\theta_{i}$. Our primary interest is on sequences with bounded
total variation (TV) so that $\sum_{i=2}^{n}|\theta_{i}-\theta_{i-1}|\leq
C_{n}$, but we will also talk about the adaptivity our our method to easier
problems such as forecasting Sobolev and Holder functions._

We propose a model for nonparametric online forecasting as described in Figure
1. This model can be re-framed in the language of the online convex
optimization model with three differences.

  1. 1.

We consider only quadratic loss functions of the form
$\ell_{t}(x)=(x-\theta_{t})^{2}$.

  2. 2.

The learner receives independent _noisy_ gradient feedback, rather than the
exact gradient.

  3. 3.

The criterion of interest is redefined as the _dynamic regret_ (Zinkevich,
2003; Besbes et al., 2015):

$R_{\text{dynamic}}(\mathcal{A},\ell_{1:n}):=\mathbb{E}\left[\sum_{t=1}^{n}\ell_{t}(x_{t})\right]-\sum_{t=1}^{n}\inf_{x_{t}}\ell_{t}(x_{t}).$
(1)

The new criterion is called a dynamic regret because we are now comparing to a
stronger dynamic baseline that chooses an optimal $x$ in every round. Of
course in general, the dynamic regret will be linear in $n$ (Jadbabaie et al.,
2015). To make the problem non-trivial, we restrict our attention to sequences
of $\ell_{1},...,\ell_{n}$ that are _regular_ , which makes it possible to
design algorithms with _sublinear_ dynamic regret. In particular, we borrow
ideas from the nonparametric regression literature and consider sequences
$[\theta_{1},...,\theta_{n}]$ that are discretizations of functions in the
continuous domain. Regularity assumptions emerge naturally as we consider
canonical functions classes such as the Holder class, Sobolev class and Total
Variation classes (see, e.g., Tsybakov, 2008, for a review).

###  1.2 Assumptions

We consolidate all the assumptions used in this work and provide necessary
justifications for them.

$\bullet$

(A1) The time horizon for the online learner is known to be $n$.

$\bullet$

(A2) The parameter $\sigma^{2}$ of subgaussian noise in the observations is
known.

$\bullet$

(A3) The ground truth denoted by
$\theta_{1:n}=[\theta_{1},...,\theta_{n}]^{T}$ has its total variation bounded
by some positive $C_{n}$, i.e., we take $\mathcal{F}$ to be the total
variation class
$\mathrm{TV}(C_{n}):=\\{\theta_{1:n}\in\mathbb{R}^{n}:\|D\theta_{1:n}\|_{1}\leq
C_{n}\\}$ where $D$ is the discrete difference operator. Here
$D\theta_{1:n}=[\theta_{2}-\theta_{1},\ldots,\theta_{n}-\theta_{n-1}]^{T}$.

$\bullet$

(A4) $|\theta_{1}|\leq U$.

The knowledge of $\sigma^{2}$ in assumption (A2) is primarily used to get the
optimal dependence of $\sigma$ in minimax rate. This assumption can be relaxed
in practice by using the Median Absolute Deviation estimator as described in
Section 7.5 of Johnstone (2017) to estimate $\sigma^{2}$ robustly. Assumption
(A3) features a samples from a large class of functions with spatially
inhomogeneous degree of smoothness. The functions residing in this class need
not even be continuous. Our goal is to propose a policy that is locally
adaptive whose empirical mean squared error converges at the minimax rate for
this function class. We stress that we do _not_ assume that the learner knows
$C_{n}$. The problem is open and nontrivial even when $C_{n}$ is known.
Assumption (A4) is very mild as it puts restriction only to the first value of
the sequence. This assumption controls the inevitable prediction error for the
first point in the sequence.

###  1.3 Our Results

The major contributions of this work are summarized below.

  * •

It is known that the minimax MSE for _smoothing_ sequences in the TV class is
$\tilde{\Omega}(n^{-2/3})$. This implies a lowerbound of
$\tilde{\Omega}(n^{1/3})$ for the dynamic regret in our setting. We present a
policy Arrows (Adaptive Restarting Rule for Online averaging using Wavelet
Shrinkage) with a nearly minimax dynamic regret $\tilde{O}(n^{1/3})$ and a
run-time complexity of $O(n\log n)$.

  * •

We show that a class of forecasting strategies — including the popular Online
Gradient Descent (OGD) with fixed restarts (Besbes et al., 2015), moving
averages (MA) (Box and Jenkins, 1970) — are fundamentally limited by
$\tilde{\Omega}(\sqrt{n})$ regret.

  * •

We also provide a more refined lower bound that characterized the dependence
of $U,C_{n}$ and $\sigma$, which certifies the adaptive optimality of Arrows
in all regimes. The bound also reveals a subtle price to pay when we move from
the smoothing problem to the forecasting problem, which indicates the
separation of the two problems when $C_{n}/\sigma\gg n^{1/4}$, a regime where
the forecasting problem is _strictly_ harder (See Figure 3).

  * •

Lastly, we consider forecasting sequences in Sobolev classes and Holder
classes and establish that Arrows can automatically _adapt_ to the optimal
regret of these _simpler_ function classes as well, while OGD and MA cannot,
unless we change their tuning parameter (to behave suboptimally on the TV
class).

##  2 Related Work

The topic of this paper sits well in between two amazing bodies of literature:
nonparametric regression and online learning. Our results therefore contribute
to both fields and hopefully will inspire more interplay between the two
communities. Throughout this paper when we refer $\tilde{O}(n^{1/3})$ as the
optimal regret, we assume the parameters of the problem are such that it is
acheivable (see Figure 3).

Nonparametric regression. As we mentioned before, our problem — online
nonparametric forecasting — is motivated by the idea of using locally adaptive
nonparametric regression for time series forecasting (Mammen and van de Geer,
1997; Kim et al., 2009; Tibshirani, 2014). It is more challenging than
standard nonparametric regression because we do not have access to the data in
the future. While our proof techniques make use of several components (e.g.,
universal shrinkage) from the seminal work in wavelet smoothing (Donoho et
al., 1990, 1998), the way we use them to construct and analyze our algorithm
is new and more generally applicable for converting non-parametric regression
methods to forecasting methods.

Adaptive Online Learning. Our problem is also connected to a growing
literature on adaptive online learning which aims at matching the performance
of a stronger time-varying baseline (Zinkevich, 2003; Hall and Willett, 2013;
Besbes et al., 2015; Chen et al., 2018b; Jadbabaie et al., 2015; Hazan and
Seshadhri, 2007; Daniely et al., 2015; Yang et al., 2016; Zhang et al., 2018a,
b; Chen et al., 2018a). Many of these settings are highly general and we can
apply their algorithms directly to our problem, but to the best of our
knowledge, none of them achieves the optimal $\tilde{O}(n^{1/3})$ dynamic
regret.

In the remainder of this section, we focus our discussion on how to apply the
regret bounds in non-stationary stochastic optimization (Besbes et al., 2015;
Chen et al., 2018b) to our problem while leaving more elaborate discussion
with respect to alternative models (e.g. the constrained comparator approach
(Zinkevich, 2003; Hall and Willett, 2013), adaptive regret (Jadbabaie et al.,
2015; Zhang et al., 2018a), competitive ratio (Bansal et al., 2015; Chen et
al., 2018a)), as well as the comparison to the classical time series models to
Appendix A.

Regret from Non-Stationary Stochastic Optimization The problem of non-
stationary stochastic optimization is more general than our model because
instead of considering only the quadratic functions,
$\ell_{t}(x)=(x-\theta_{t})^{2}$, they work with the more general class of
strongly convex functions and general convex functions. They also consider
both noisy gradient feedbacks (stochastic first order oracle) and noisy
function value feedbacks (stochastic zeroth order oracle).

In particular, Besbes et al. (2015) define a quantity $V_{n}$ which captures
the total amount of “variation” of the functions $\ell_{1:n}$ using
$V_{n}:=\sum_{i=1}^{n-1}\|\ell_{i+1}-\ell_{i}\|_{\infty}.$ 111The $V_{n}$
definition in (Besbes et al., 2015) for strongly convex functions are defined
a bit differently, the $\|\cdot\|_{\infty}$ is taken over the convex hull of
minimizers. This creates some subtle confusions regarding our results which we
explain in details in Appendix I. Chen et al. (2018b) generalize the notion to
$V_{n}(p,q):=\left(\sum_{i=1}^{n-1}\|\ell_{i+1}-\ell_{i}\|_{p}^{q}\right)^{1/q}$
for any $1\leq p,q\leq+\infty$ where
$\|\cdot\|_{p}:=(\int|\cdot(x)|^{p}dx)^{1/p}$ is the standard $L_{p}$ norm for
functions222We define $V_{n}(p,q)$ to be a factor of $n^{-1/q}$ times bigger
than the original scaling presented in (Chen et al., 2018b) so the results
become comparable to that of (Besbes et al., 2015).. Table 1 summarizes the
known results under the non-stationary stochastic optimization setting.

Table 1: Summary of known minimax dynamic regret in the non-stationary
stochastic optimization model. Note that the choice of $q$ does not affect the
minimax rate in any way, but the choice of $p$ does. “-” indicates that the no
upper or lower bounds are known for that setting.

| Noisy gradient feedback | Noisy function value feedback
---|---|---
Assumptions on $\ell_{1:n}$ | $p=+\infty$ | $1\leq p<+\infty$ | $p=+\infty$ | $1\leq p<+\infty$
Convex & Lipschitz | $\Theta(n^{2/3}V_{n}^{1/3})$ | $O(n^{\frac{2p+d}{3p+d}}V_{n}(p,q)^{\frac{p}{3p+d}})$ | - | -
Strongly convex & Smooth | $\Theta(n^{1/2}V_{n}^{1/2})$ | $\Theta(n^{\frac{2p+d}{4p+d}}V_{n}(p,q)^{\frac{2p}{4p+d}})$ | $\Theta(n^{2/3}V_{n}^{1/3})$ | $\Theta(n^{\frac{4p+d}{6p+d}}V_{n}(p,q)^{\frac{2p}{6p+d}})$

Our assumption on the underlying trend $\theta_{1:n}\in\mathcal{F}$ can be
used to construct an upper bound of this quantity of variation $V_{n}$ or
$V_{n}(p,q)$. As a result, the algorithms in non-stationary stochastic
optimization and their dynamic regret bounds in Table 1 will apply to our
problem (modulo additional restrictions on bounded domain). However, our
preliminary investigation suggests that this direct reduction does _not_ , in
general, lead to optimal algorithms. We illustrate this observation in the
following example.

######  Example 1.

Let $\mathcal{F}$ be the set of all bounded sequences in the total variation
class $TV(1)$. It can be worked out that $V_{n}(p,q)=O(1)$ for all $p,q$.
Therefore the smallest regret from (Besbes et al., 2015; Chen et al., 2018b)
is obtained by taking $p\rightarrow+\infty$, which gives us a regret of
$O(n^{1/2})$. Note that we expect the optimal regret to be
$\tilde{O}(n^{1/3})$ according to the theory of locally adaptive nonparametric
regression.

In Example 1, we have demonstrated that one cannot achieve the optimal dynamic
regret using known results in non-stationary stochastic optimization. We show
in section 3.1 that “Restarting OGD” algorithm has a fundamental lower bound
of $\tilde{\Omega}(\sqrt{n})$ on dynamic regret in the TV class.

Online nonparametric regression. As we finalize our manuscript, it comes to
our attention that our problem of interest in Figure 1 can be cast as a
special case of the “online nonparametric regression” problem (Rakhlin and
Sridharan, 2014; Gaillard and Gerchinovitz, 2015a). The general result of
Rakhlin and Sridharan (2014) implies the _existence_ of an algorithm that
enjoys a $\tilde{O}(n^{1/3})$ regret for the TV class without explicitly
constructing one, which shows that $n^{1/3}$ is the minimax rate when
$C_{n}=O(1)$ (see more details in Appendix A). To the best of our knowledge,
our proposed algorithm remains the first _polynomial time_ algorithm with
$\tilde{O}(n^{1/3})$ regret and our results reveal more precise (optimal)
upper and lower bounds on all parameters of the problem (see Section 3.4).

##  3 Main results

We are now ready to present our main results.

###  3.1 Limitations of Linear Forecasters

Restarting OGD as discussed in Example 1, fails to achieve the optimal regret
in our setting. A curious question to ask is whether it is the algorithm
itself that fails or it is an artifact of a potentially suboptimal regret
analysis. To answer this, let’s consider the class of linear forecasters —
estimators that outputs a fixed linear transformation of the observations
$y_{1:n}$. The following preliminary result shows that Restarting OGD is a
linear forecaster . By the results of Donoho et al. (1998), linear smoothers
are fundamentally limited in their ability to estimate functions with
heterogeneous smoothness. Since forecasting is harder than smoothing, this
limitation gets directly translated to the setting of linear forecasters.

######  Proposition 1.

Online gradient descent with a fixed restart schedule is a linear forecaster.
Therefore, it has a dynamic regret of at least $\tilde{\Omega}(\sqrt{n})$.

###### Proof.

First, observe that the stochastic gradient is of form $2(x_{t}-y_{t})$ where
$x_{t}$ is what the agent played at time $t$ and $y_{t}$ is the noisy
observation $\theta_{t}+\text{Independent noise}$. By the online gradient
descent strategy with the fixed restart interval and an inductive argument,
$x_{t}$ is a linear combination of $y_{1},...,y_{t-1}$ for any $t$. Therefore,
the entire vector of predictions $x_{1:t}$ is a fixed linear transformation of
$y_{1:t-1}$. The fundamental lower bound for linear smoothers from Donoho et
al. (1998) implies that this algorithm will have a regret of at least
$\tilde{\Omega}(\sqrt{n})$. ∎

The proposition implies that we will need fundamentally new _nonlinear_
algorithmic components to achieve the optimal $O(n^{1/3})$ regret, if it is
achievable at all!

###  3.2 Policy

In this section, we present our policy Arrows (Adaptive Restarting Rule for
Online averaging using Wavelet Shrinkage). The following notations are
introduced for describing the algorithm.

$\bullet$

$t_{h}$ denotes start time of the current bin and $t$ be the current time
point.

$\bullet$

$\bar{y}_{t_{h}:t}$ denotes the average of the $y$ values for time steps
indexed from $t_{h}$ to $t$.

$\bullet$

$pad_{0}(y_{t_{h}},...,y_{t})$ denotes the vector
$(y_{t_{h}}-\bar{y}_{t_{h}:t},...,y_{t}-\bar{y}_{t_{h}:t})^{T}$ zero-padded at
the end till its length is a power of 2. _i.e_ , a re-centered and padded
version of observations.

$\bullet$

$T(x)$ where $x$ is a sequence of values, denotes the element-wise soft
thresholding of the sequence with threshold $\sigma\sqrt{\beta\log(n)}$

$\bullet$

H denotes the orthogonal discrete Haar wavelet transform matrix of proper
dimensions

$\bullet$

Let $Hx=\alpha=[\alpha_{1},\alpha_{2},...,\alpha_{k}]^{T}$ where $k$ being a
power of 2 is the length of $x$. Then the vector
$[\alpha_{2},...,\alpha_{k}]^{T}$ can be viewed as a concatenation of
$\log_{2}k$ contiguous blocks represented by
$\alpha[l],l=0,...,\log_{2}(k)-1$. Each block $\alpha[l]$ at level $l$
contains $2^{l}$ coefficients.

Arrows: inputs - observed $y$ values, time horizon $n$, std deviation
$\sigma$, $\delta\in(0,1]$, a hyper-parameter $\beta>24$ 1. Initialize
$t_{h}=1$, $newBin=1$, $y_{0}=0$ 2. For $t$ = $1$ to $n$: (a) If $newBin==1$,
predict $x_{t}^{t_{h}}=y_{t-1}$, else predict
$x_{t}^{t_{h}}=\bar{y}_{t_{h}:t-1}$ (b) set $newBin=0$, observe $y_{t}$ and
suffer loss $(x_{t}^{t_{h}}-\theta_{t})^{2}$ (c) Let
$\tilde{y}=pad_{0}(y_{t_{h}},...,y_{t})$ and $k$ be the padded length. (d) Let
$\hat{\alpha}(t_{h}:t)=T(H\tilde{y})$ (e) Restart Rule: If
$\frac{1}{\sqrt{k}}\sum_{l=0}^{\log_{2}(k)-1}2^{l/2}\|\hat{\alpha}(t_{h}:t)[l]\|_{1}>\frac{\sigma}{\sqrt{k}}$
then i. set $newBin=1$ ii. set $t_{h}=t+1$

Our policy is the byproduct of following question: How can one lift a batch
estimator that is minimax over the TV class to a minimax online algorithm?

Restarting OGD when applied to our setting with squared error losses reduces
to partitioning the duration of game into fixed size chunks and outputting
online averages. As described in Section 3.1, this leads to suboptimal regret.
However, the notion of averaging is still a good idea to keep. If within a
time interval, the Total Variation (TV) is adequately small, then outputting
sample averages is reasonable for minimizing the cumulative squared error.
Once we encounter a bump in the variation, a good strategy is to restart the
averaging procedure. Thus we need to adaptively detect intervals with low TV.
For accomplishing this, we communicate with an oracle estimator whose output
can be used to construct a lowerbound of TV within an interval. The decision
to restart online averaging is based on the estimate of TV computed using this
oracle. Such a decision rule introduces non-linearity and hence breaks free of
the suboptimal world of linear forecasters.

The oracle estimator we consider here is a slightly modified version of the
soft thresholding estimator from Donoho (1995). We capture the high level
intuition behind steps (d) and (e) as follows. Computation of Haar
coefficients involves smoothing adjacent regions of a signal and taking
difference between them. So we can expect to construct a lowerbound of the
total variation $\|D\theta_{1:n}\|_{1}$ from these coeffcients. The extra
thresholding step $T(.)$ in (d) is done to denoise the Haar coefficients
computed from noisy data. In step (e), a weighted L1 norm of denoised
coefficients is used to lowerbound the total variation of the true signal. The
multiplicative factors $2^{l/2}$ are introduced to make the lowerbound
tighter. We restart online averaging once we detect a large enough variation.
The first coefficient $\hat{\alpha}(t_{h}:t)_{1}$ is zero due to the re-
centering caused by $pad_{0}$ operation. The hyper-parameter $\beta$ controls
the degree to which we shrink the noisy wavelet coefficients. For sufficiently
small $\beta$, It is almost equivalent to the universal soft-thresholding of
(Donoho, 1995). The optimal selection of $\beta$ is described in Theorem 1.

We refer to the duration between two consecutive restarts inclusive of the
first restart but exclusive of the second as a bin. The policy identifies
several bins across time, whose width is adaptively chosen.

Figure 2: _An illustration of Arrows on a sequence with heterogeneous
smoothness. We compare qualitatively (on the left) and quantitatively (on the
right) to two popular baselines: (a) restarting online gradient descent
(Besbes et al., 2015); (b) the moving averages (Box and Jenkins, 1970) with
optimal parameter choices. As we can see, Arrows achieves the optimal
$\tilde{O}(n^{1/3})$ regret while the baselines are both suboptimal. _

###  3.3 Dynamic Regret of Arrows

In this section, we provide bounds for non-stationary regret and run-time of
the policy.

######  Theorem 1.

Let the feedback be $y_{t}=\theta_{t}+Z_{t}$, $t=1,\ldots,n$ and $Z_{t}$ be
independent, $\sigma$-subgaussian random variables. If
$\beta=24+\frac{8\log(8/\delta)}{\log(n)}$, then with probability at least
$1-\delta$, Arrows achieves a dynamic regret of
$\tilde{O}(n^{1/3}\|D\theta_{1:n}\|_{1}^{2/3}\sigma^{4/3}+|\theta_{1}|^{2}+\|D\theta_{1:n}\|_{2}^{2}+\sigma^{2})$
where $\tilde{O}$ hides a logarithmic factor in $n$ and $1/\delta$.

###### Proof Sketch.

Our policy is similar in spirit to restarting OGD but with an adaptive restart
schedule. The key idea we used is to reduce the dynamic regret of our policy
in probability roughly to a sum of squared error of a soft thresholding
estimator and number of restarts. This was accomplished by using a Follow The
Leader (FTL) reduction. For bounding the squared error part of the sum we
modified the threshold value for the estimator in Donoho (1995) and proved
high probability guarantees for the convergence of its empirical mean. To
bound the number of times we restart, we first establish a connection between
Haar coefficients and total variation. This is intuitive since computation of
Haar coefficients can be viewed as smoothing the adjacent regions of a signal
and taking their difference. Then we exploit a special condition called
“uniform shrinkage” of the soft-thresholding estimator which helps to
optimally bound the number of restarts with high probability. ∎

Theorem 1 provides an upper bound of the minimax dynamic regret for
forecasting the TV class.

######  Corollary 1.

Suppose the ground truth $\theta_{1:n}\in TV(C_{n})$ and $|\theta_{1}|\leq U$.
Then $\|D\theta_{1:n}\|_{1}\leq C_{n}$. By noting that
$\|D\theta_{1:n}\|_{2}\leq\|D\theta_{1:n}\|_{1}$, under the setup in Theorem 1
Arrows achieves a dynamic regret of
$\tilde{O}(n^{1/3}C_{n}^{2/3}\sigma^{4/3}+U^{2}+C_{n}^{2}+\sigma^{2})$ with
probability at-least $1-\delta$.

######  Remark 1 (Adaptivity to unknown parameters.).

Observe that Arrows does not require the knowledge of $C_{n}$.It adapts
optimally to the unknown TV radius $C_{n}:=\|D\theta_{1:n}\|_{1}$ of the
ground truth $\theta_{1:n}$. The adaptivity to $n$ can be achieved by a
standard doubling trick. $\sigma$, if unknown, can be robustly estimated from
the first few observations by a Median Absolute Deviation estimator (eg.
Section 7.5 of Johnstone (2017)), thanks to the sparsity of wavelet
coefficients of TV bounded functions.

###  3.4 A lower bound on the minimax regret

We now give a matching lower bound of the expected regret, which establishes
that Arrows is adaptively minimax.

######  Proposition 2.

Assume $\min\\{U,C_{n}\\}>2\pi\sigma$ and $n>3$, there is a universal constant
$c$ such that

$\inf_{x_{1:n}}\sup_{\theta_{1:n}\in\mathrm{TV}(C_{n})}\mathbb{E}\left[\sum_{t=1}^{n}\big{(}x_{t}(y_{1:t-1})-\theta_{t}\big{)}^{2}\right]\geq
c(U^{2}+C_{n}^{2}+\sigma^{2}\log n+n^{1/3}C_{n}^{2/3}\sigma^{4/3}).$

The proof is deferred to the Appendix I. The result shows that our result in
Theorem 1 is optimal up to a logarithmic term in $n$ and $1/\delta$ for almost
all regimes (modulo trivial cases of extremely small
$\min\\{U,C_{n}\\}/\sigma$ and $n$)333When both $U$ and $C_{n}$ are moderately
small relative to $\sigma$, the lower bound will depend on $\sigma$ a little
differently because the estimation error goes to $0$ faster than $1/\sqrt{n}$.
We know the minimax risk exactly for that case as well but it is somewhat
messy (see e.g. Wasserman, 2006). When they are both much smaller than
$\sigma$, e.g., when $\min\\{U,C_{n}\\}\leq\sigma/\sqrt{n}$, then outputting
$0$ when we do not have enough information will be better than doing online
averages. .

######  Remark 2 (The price of forecasting).

The result also shows that _forecasting is strictly harder than smoothing_.
Observe that a term with $C_{n}^{2}$ is required even if $\sigma=0$, whereas
in the case of a one-step look-ahead oracle (or the smoothing algorithm that
sees all $n$ observations) does not have this term. This implies that the
total amount of variation that _any_ algorithm can handle while producing a
sublinear regret has dropped from $C_{n}=o(n)$ to $C_{n}=o(\sqrt{n})$.
Moreover, the regime where the $n^{1/3}C_{n}^{2/3}\sigma^{4/3}$ term is
meaningful only when $C_{n}=o(n^{1/4})$. For the region where $\sigma
n^{1/4}\ll C_{n}\ll\sigma n^{1/2}$, the minimax regret is essentially
proportional to $C_{n}^{2}$. This is illustrated in Figure 3.

Figure 3: _An illustration of the minimax (dynamic) regret of forecasters and
smoothers as a function of $C_{n}$. The non-trivial regime for forecasting is
when $C_{n}$ lies between $\sigma\sqrt{\frac{\log(n)}{n}}$ and
$\sigma\>n^{1/4}$ where forecasting is just as hard as smoothing. When
$C_{n}>\sigma\>n^{1/4}$, forecasting is harder than smoothing. The yellow
region indicates the extra loss incurred by any minimax forecaster. The green
region marks the extra loss incurred by a linear forecaster compared to
minimax forecasting strategy. The figure demonstrates that linear forecasters
are sub-optimal even in the non-trivial regime. When $C_{n}>\sigma\>n^{1/2}$,
it is impossible to design a forecasting strategy with sub-linear regret. For
$C_{n}>\sigma\>n$, identity function is optimal estimator for smoothing and
when when $C_{n}<\sigma\sqrt{\frac{\log(n)}{n}}$, online averaging is optimal
for both problems._

We note that in much of the online learning literature, it is conventional to
consider a slightly more restrictive setting with bounded domain, which could
reduce the minimax regret. The following remark summarizes a variant of our
results in this setting.

######  Remark 3 (Minimax regret in bounded domain).

If we consider predicting sequences from a subset of the $TV(C_{n})$ ball
having an extra boundedness condition $|\theta_{i}|\leq B$ for $i=1\ldots n$,
it can be shown that Arrows achieves a dynamic regret of
$\tilde{O}(n^{1/3}C_{n}^{2/3}\sigma^{4/3}+B^{2}+BC_{n}+\sigma^{2})$ with
probability at least $1-\delta$. The discussion in Appendix I, establishes a
matching lower bound in this more constrained setting. In particular,
forecasting is still strictly harder than smoothing due to the $BC_{n}$ factor
in the bound.

###  3.5 The adaptivity of Arrows to Sobolev and Holder classes

It turns out that Arrows is also adaptively optimal in forecasting sequences
in the discrete Sobolev classes and the discrete Holder classes, which are
defined as

$\displaystyle\mathcal{S}(C_{n}^{\prime})=\\{\theta_{1:n}:\|D\theta_{1:n}\|_{2}\leq
C_{n}^{\prime}\\},$
$\displaystyle\mathcal{H}(B_{n}^{\prime})=\\{\theta_{1:n}:\|D\theta_{1:n}\|_{\infty}\leq
B_{n}^{\prime}\\}.$ (2)

These classes feature sequences that are more spatially homogeneous than those
in the TV class. The minimax cumulative error of nonparametric estimation in
the discrete Sobolev class is
$\Theta(n^{2/3}[C^{\prime}_{n}]^{2/3}\sigma^{4/3})$ (see e.g., Sadhanala et
al., 2016, Theorem 5 and 6).

######  Corollary 2.

Let the feedback be $y_{t}=\theta_{t}+Z_{t}$ where $Z_{t}$ is an independent,
$\sigma$-subgaussian random variable. Let
$\theta_{1:n}\in\mathcal{S}(C_{n}^{\prime})$ and $|\theta_{1}|\leq U$. If
$\beta=24+\frac{8\log(8/\delta)}{\log(n)}$, then with probability at least
$1-\delta$, Arrows achieves a dynamic regret of
$\tilde{O}(n^{2/3}[C_{n}^{\prime}]^{2/3}\sigma^{4/3}+U^{2}+[C_{n}^{^{\prime}}]^{2}+\sigma^{2})$
where $\tilde{O}$ hides a logarithmic factor in $n$ and $1/\delta$.

Table 2: _Minimax rates for cumulative error
$\sum_{i=1}^{n}(\hat{\theta}_{i}-\theta)^{2}$ in various settings and policies
that achieve those rates. Arrows is adaptively minimax across all of the
described function classes while linear forecasters fail to perform optimally
over the TV class. For simplicity, we assume $U$ is small and hide a $\log n$
factors in all the forecasting rates._

Class |  | Minimax rate for
---
Forecasting
| Minimax rate for
---
Smoothing
| Minimax rate for
---
Linear Forecasting
TV | $\|D\theta_{1:n}\|_{1}\leq C_{n}$ | $n^{1/3}C_{n}^{2/3}\sigma^{4/3}+C_{n}^{2}+\sigma^{2}$ | $n^{1/3}C_{n}^{2/3}\sigma^{4/3}+\sigma^{2}$ | $n^{1/2}C_{n}\sigma+C_{n}^{2}+\sigma^{2}$
Sobolev | $\|D\theta_{1:n}\|_{2}\leq C_{n}^{\prime}$ | $n^{2/3}[C_{n}^{\prime}]^{2/3}\sigma^{4/3}+[C_{n}^{\prime}]^{2}+\sigma^{2}$ | $n^{2/3}[C_{n}^{\prime}]^{2/3}\sigma^{4/3}+\sigma^{2}$ | $n^{2/3}[C_{n}^{\prime}]^{2/3}\sigma^{4/3}+[C_{n}^{\prime}]^{2}+\sigma^{2}$
Holder | $\|D\theta_{1:n}\|_{\infty}\leq L_{n}$ | $nL_{n}^{2/3}\sigma^{4/3}+nL_{n}^{2}+\sigma^{2}$ | $nL_{n}^{2/3}\sigma^{4/3}+\sigma^{2}$ | $nL_{n}^{2/3}\sigma^{4/3}+nL_{n}^{2}+\sigma^{2}$
1-52.5 Minimax Algorithm | Arrows |  | Wavelet Smoothing
---
Trend Filtering
| Restarting OGD
---
Moving Averages
1-52.5 |  |  |  |

Canonical Scaling444The “canonical scaling” are obtained by discretizing functions in canonical function classes. Under the canonical scaling, Holder class $\subset$ Sobolev class $\subset$ TV class, as shown in the figure on the left. Arrows is optimal for the Sobolev and Holder classes inscribed in the TV class. MA and Restarting OGD on the other hand require different parameters and prior knowledge of variational budget (i.e $C_{n}$ or $C^{\prime}_{n}$) to achieve the minimax linear rates for the TV class and the Sobolev/Holder class. |  | Forecasting
---
| Smoothing
---
| Linear Forecasting
---
TV | $C_{n}\asymp 1$ | $n^{1/3}$ | $n^{1/3}$ | $n^{1/2}$
Sobolev | $C_{n}^{\prime}\asymp 1/\sqrt{n}$ | $n^{1/3}$ | $n^{1/3}$ | $n^{1/3}$
Holder | $L_{n}\asymp 1/n$ | $n^{1/3}$ | $n^{1/3}$ | $n^{1/3}$

Thus despite the fact that Arrows is designed for total variation class, it
adapts to the optimal rates of forecasting sequences that are spatially
regular. To gain some intuition, let’s minimally expand the Sobolev ball to a
TV ball of radius $C_{n}=\sqrt{n}C_{n}^{\prime}$. The chosen scaling of
$C_{n}$ activates the embedding $\mathcal{S}(C^{\prime}_{n})\subset TV(C_{n})$
(see the illustration in Table 3.5) with both classes having same minimax rate
in the batch setting. This implies that dynamic regret of Arrows is
simultaneously minimax optimal over $\mathcal{S}(C^{\prime}_{n})$ and
$TV(C_{n})$ wrt the term containing $n$. It can be shown that Arrows is
optimal wrt to the additive $[C_{n}^{^{\prime}}]^{2},U^{2},\sigma^{2}$ terms
as well. Minimaxity in Sobolev class implies minimaxity in Holder class since
it is known that a Holder ball is sandwiched between two Sobolev balls having
the same minimax rate (see e.g., Tibshirani, 2015). A proof of the Corollary
and related experiments are presented in Appendix F and J.

###  3.6 Fast computation

Last but not least, we remark that there is a fast implementation of Arrows
that reduces the overall time-complexity for $n$ step from $O(n^{2})$ to
$O(n\log n)$.

######  Proposition 3.

The run time of Arrows is $O(n\log(n))$, where $n$ is the time horizon.

The proof exploits the sequential structure of our policy and sparsity in
wavelet transforms, which allows us to have $O(\log n)$ incremental updates in
all but $O(\log n)$ steps. See Appendix G for details.

###  3.7 Experimental Results

To empirically validate our results, we conducted a number of numerical
simulations that compares the regret of Arrows, (Restarting) OGD and MA.
Figure 2 shows the results on a function with heterogeneous smoothness (see
the exact details and more experiments in Appendix B) with the hyperparameters
selected according to their theoretical optimal choice for the TV class (See
Theorem 2, 3 for OGD and MA in Appendix C). The left panel illustrates that
Arrows is locally adaptive to heterogeneous smoothness of the ground truth.
Red peaks in the figure signifies restarts. During the initial and final
duration, the signal varies smoothly and Arrows chooses a larger window size
for online averaging. In the middle, signal varies rather abruptly.
Consequently Arrows chooses a smaller window size. On the other hand, the
linear smoothers OGD and MA use a constant width and cannot adapt to the
different regions of the space. This differences are also reflected in the
quantitative evaluation on the right, which clearly shows that OGD and MA has
a suboptimal $\tilde{O}(\sqrt{n})$ regret while Arrows attains the
$\tilde{O}(n^{1/3})$ minimax regret!

##  4 Concluding Discussion

In this paper, we studied the problem of online nonparametric forecasting of
bounded variation sequences. We proposed a new forecasting policy Arrows and
proved that it achieves a cumulative square error (or dynamic regret) of
$\tilde{O}(n^{1/3}C_{n}^{2/3}\sigma^{4/3}+\sigma^{2}+U^{2}+C_{n}^{2})$ with
total runtime of $O(n\log n)$. We also derived a lower bound for forecasting
sequences with bounded total variation which matches the upper bound up to a
logarithmic term which certifies the optimality of Arrows in all parameters.
Through connection to linear estimation theory, we assert that no linear
forecaster can achieve the optimal rate. Arrows is highly adaptive and has
essentially no tuning parameters. We show that it is adaptively minimax (up to
a logarithmic factor) simultaneously for all discrete TV classes, Sobolev
classes and Holder classes with unknown radius. Future directions include
generalizing to higher order TV class and other convex loss functions.

### Acknowledgement

DB and YW were supported by a start-up grant from UCSB CS department and a
gift from Amazon Web Services. The authors thank Yining Wang for a preliminary
discussion that inspires the work, and Akshay Krishnamurthy and Ryan
Tibshirani for helpful comments to an earlier version of the paper.

## References

  * Bansal et al. (2015) 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. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.
  * Baum and Petrie (1966) Leonard E Baum and Ted Petrie.  Statistical inference for probabilistic functions of finite state markov chains.  _The annals of mathematical statistics_ , 37(6):1554–1563, 1966.
  * Besbes et al. (2015) Omar Besbes, Yonatan Gur, and Assaf Zeevi.  Non-stationary stochastic optimization.  _Operations research_ , 63(5):1227–1244, 2015\.
  * Bickel et al. (1981) PJ Bickel et al.  Minimax estimation of the mean of a normal distribution when the parameter space is restricted.  _The Annals of Statistics_ , 9(6):1301–1309, 1981\.
  * Birge and Massart (2001) Lucien Birge and Pascal Massart.  Gaussian model selection.  _Journal of the European Mathematical Society_ , 3(3):203–268, 2001.
  * Box and Jenkins (1970) George EP Box and Gwilym M Jenkins.  _Time series analysis: forecasting and control_.  John Wiley & Sons, 1970.
  * Chen et al. (2018a) Niangjun Chen, Gautam Goel, and Adam Wierman.  Smoothed online convex optimization in high dimensions via online balanced descent.  In _Conference on Learning Theory (COLT-18)_ , 2018a.
  * Chen et al. (2018b) Xi Chen, Yining Wang, and Yu-Xiang Wang.  Non-stationary stochastic optimization under lp, q-variation measures.  _Operations Research, to appear._ , 2018b.
  * Daniely et al. (2015) Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz.  Strongly adaptive online learning.  In _International Conference on Machine Learning_ , pages 1405–1411, 2015.
  * De Boor et al. (1978) Carl De Boor, Carl De Boor, Etats-Unis Mathématicien, Carl De Boor, and Carl De Boor.  _A practical guide to splines_ , volume 27.  Springer-Verlag New York, 1978.
  * Donoho et al. (1990) David Donoho, Richard Liu, and Brenda MacGibbon.  Minimax risk over hyperrectangles, and implications.  _Annals of Statistics_ , 18(3):1416–1437, 1990\.
  * Donoho (1995) David L Donoho.  De-noising by soft-thresholding.  _IEEE transactions on information theory_ , 41(3):613–627, 1995.
  * Donoho et al. (1998) David L Donoho, Iain M Johnstone, et al.  Minimax estimation via wavelet shrinkage.  _The annals of Statistics_ , 26(3):879–921, 1998\.
  * Gaillard and Gerchinovitz (2015a) Pierre Gaillard and Sébastien Gerchinovitz.  A chaining algorithm for online nonparametric regression.  In _Conference on Learning Theory_ , pages 764–796, 2015a.
  * Gaillard and Gerchinovitz (2015b) Pierre Gaillard and Sébastien Gerchinovitz.  A chaining algorithm for online nonparametric regression.  In _COLT_ , 2015b.
  * Hall and Willett (2013) Eric Hall and Rebecca Willett.  Dynamical models and tracking regret in online convex programming.  In _International Conference on Machine Learning (ICML-13)_ , pages 579–587, 2013.
  * Hazan and Seshadhri (2007) Elad Hazan and Comandur Seshadhri.  Adaptive algorithms for online decision problems.  In _Electronic colloquium on computational complexity (ECCC)_ , volume 14, 2007.
  * Hodrick and Prescott (1997) Robert J Hodrick and Edward C Prescott.  Postwar us business cycles: an empirical investigation.  _Journal of Money, credit, and Banking_ , pages 1–16, 1997.
  * Hutter and Rigollet (2016) Jan-Christian Hutter and Philippe Rigollet.  Optimal rates for total variation denoising.  In _Conference on Learning Theory (COLT-16)_ , 2016.  to appear.
  * Jadbabaie et al. (2015) Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan.  Online optimization: Competing with dynamic comparators.  In _Artificial Intelligence and Statistics_ , pages 398–406, 2015\.
  * Johnstone (2017) Iain M. Johnstone.  _Gaussian estimation: Sequence and wavelet models_.  2017\.
  * Kim et al. (2009) Seung-Jean Kim, Kwangmoo Koh, Stephen Boyd, and Dimitry Gorinevsky.  $\ell_{1}$ trend filtering.  _SIAM Review_ , 51(2):339–360, 2009.
  * Koolen et al. (2015) Wouter M Koolen, Alan Malek, Peter L Bartlett, and Yasin Abbasi.  Minimax time series prediction.  In _Advances in Neural Information Processing Systems (NIPS’15)_ , pages 2557–2565. 2015.
  * Kotłowski et al. (2016) Wojciech Kotłowski, Wouter M. Koolen, and Alan Malek.  Online isotonic regression.  In _Annual Conference on Learning Theory (COLT-16)_ , volume 49, pages 1165–1189. PMLR, 2016.
  * Mallat (1999) Stéphane Mallat.  _A wavelet tour of signal processing_.  Elsevier, 1999.
  * Mammen and van de Geer (1997) Enno Mammen and Sara van de Geer.  Locally apadtive regression splines.  _Annals of Statistics_ , 25(1):387–413, 1997\.
  * Nadaraya (1964) Elizbar A Nadaraya.  On estimating regression.  _Theory of Probability & Its Applications_, 9(1):141–142, 1964.
  * Rakhlin and Sridharan (2014) Alexander Rakhlin and Karthik Sridharan.  Online non-parametric regression.  In _Conference on Learning Theory_ , pages 1232–1264, 2014.
  * Rakhlin and Sridharan (2015) Alexander Rakhlin and Karthik Sridharan.  Online nonparametric regression with general loss functions.  _CoRR_ , abs/1501.06598, 2015.
  * Rasmussen and Williams (2006) Carl Edward Rasmussen and Christopher KI Williams.  _Gaussian processes for machine learning_.  MIT Press, 2006.
  * Sadhanala et al. (2016) Veeranjaneyulu Sadhanala, Yu-Xiang Wang, and Ryan Tibshirani.  Total variation classes beyond 1d: Minimax rates, and the limitations of linear smoothers.  _Advances in Neural Information Processing Systems (NIPS-16)_ , 2016\.
  * Scholkopf and Smola (2001) Bernhard Scholkopf and Alexander J Smola.  _Learning with kernels: support vector machines, regularization, optimization, and beyond_.  MIT press, 2001.
  * Steidl et al. (2006) Gabriel Steidl, Stephan Didas, and Julia Neumann.  Splines in higher order TV regularization.  _International Journal of Computer Vision_ , 70(3):214–255, 2006.
  * Tibshirani (2015) Ryan Tibshirani.  Nonparametric Regression: Statistical Machine Learning, Spring 2015, 2015.  URL: http://www.stat.cmu.edu/~larry/=sml/nonpar.pdf. Last visited on 2019/04/29.
  * Tibshirani (2014) Ryan J Tibshirani.  Adaptive piecewise polynomial estimation via trend filtering.  _Annals of Statistics_ , 42(1):285–323, 2014\.
  * Tsybakov (2008) Alexandre B. Tsybakov.  _Introduction to Nonparametric Estimation_.  Springer Publishing Company, Incorporated, 1st edition, 2008.
  * Wahba (1990) Grace Wahba.  _Spline models for observational data_ , volume 59.  Siam, 1990.
  * Wang et al. (2014) Yu-Xiang Wang, Alex Smola, and Ryan Tibshirani.  The falling factorial basis and its statistical applications.  In _International Conference on Machine Learning (ICML-14)_ , pages 730–738, 2014.
  * Wasserman (2006) Larry Wasserman.  _All of Nonparametric Statistics_.  Springer, New York, 2006.
  * Yang et al. (2016) Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi.  Tracking slowly moving clairvoyant: optimal dynamic regret of online learning with true and noisy gradient.  In _International Conference on Machine Learning (ICML-16)_ , pages 449–457, 2016.
  * Zhang et al. (2018a) Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou.  Adaptive online learning in dynamic environments.  In _Advances in Neural Information Processing Systems (NeurIPS-18)_ , pages 1323–1333, 2018a.
  * Zhang et al. (2018b) Lijun Zhang, Tianbao Yang, Zhi-Hua Zhou, et al.  Dynamic regret of strongly adaptive methods.  In _International Conference on Machine Learning (ICML-18)_ , pages 5877–5886, 2018b.
  * Zinkevich (2003) Martin Zinkevich.  Online convex programming and generalized infinitesimal gradient ascent.  In _International Conference on Machine Learning (ICML-03)_ , pages 928–936, 2003.

##  Appendix A Discussion on other related works

#### Regret from Adaptive Optimistic Mirror Descent.

In Jadbabaie et al. (2015), the authors propose Adaptive Optimistic Mirror
Descent (AOMD) algorithm that minimizes the dynamic regret against a
comparator sequence $\\{u_{t}\\}_{t=1}^{n}$. Their learning framework is the
full information setting where learner predict $x_{t}\in\mathcal{X}$ for a
convex set $\mathcal{X}\subseteq R^{d}$. Then a loss function $f_{t}(x)$ is
revealed to the learner. To capture the regularity of the comparator, they
define a quantity
$C_{n}(u_{1},u_{2},...,u_{n}):=\sum_{t=1}^{n}\|u_{t}-u_{t-1}\|.$ They capture
the regularity of loss functions by incorporating some external knowledge
about their gradients via a predictable sequence $\\{M_{t}\\}_{t=1}^{n}$. They
define: $D_{n}:=\sum_{t=1}^{n}\|\nabla f_{t}(x_{t})-M_{t}\|_{*}^{2}$. Finally
to account for the temporal variability of $f_{t}$, they introduce $V_{n}$ as
discussed earlier. The final regret bound is expressed in terms of these three
quantities. However, their algorithm is adaptive and requires no prior
knowledge about them.

We note that our problem can be reduced to their framework if one considers
loss functions $f_{t}(x)=(x-y_{t})^{2}$. Then the expected dynamic regret
against the comparator sequence $\\{\theta_{t}\\}_{t=1}^{n}$ is given by

$\displaystyle\sum_{t=1}^{n}E[(x-y_{t})^{2}-(\theta_{t}-y_{t})^{2}]$
$\displaystyle=E[\sum_{t=1}^{n}(x-\theta_{t})^{2}],$ (3)

where the expectation at right hand side is over the randomness of forecasting
strategy. Hence we observe that their regret bound can be directly applied to
bound the dynamic regret of our problem. It can be shown that (see Appendix H)
given a fixed total variation bound $C_{n}=O(1)$, then $V_{n}$ and $D_{n}$ can
be proved to be $O(n)$ with high probability. Plugging this into their regret
bound yields an $\tilde{O}(\sqrt{n})$ rate in probability. However, it is
unclear that whether AOMD is fundamentally limited by this rate or is there a
potential suboptimality in their analysis of regret on our particular problem.

#### Other Dynamic Regret minimizing policies.

(Yang et al., 2016) defines a path variation budget that is equivalent to our
$C_{n}$ to characterize the sequence of convex loss functions. However, under
the noisy gradient feedback structure, they use a version of restarting OGD to
get $C^{1/2}n^{1/2}$ regret rate. This is very similar to the policy in
(Besbes et al., 2015). Since OGD is a linear forecaster, it is sub-optimal for
predicting bounded variation sequences under the squared error metric.

In (Koolen et al., 2015), they consider minimizing the dynamic regret wrt to a
comparator class that obeys $\|D\theta_{1:n}\|_{2}\leq C^{\prime}_{n}$. This
is basically the discrete Sobolev class. As shown in appendix E, our policy is
minimax for forecasting such sequences as well when the observed values are
noisy versions of the ground truth. However it should be noted that (Koolen et
al., 2015) does not have this distributional assumption on the observations.

(Chen et al., 2018a) considers the Smoothed Online Convex Optimization
framework where they simultaneously minimize the hitting loss $f_{t}$ and a
switching cost. They provide dynamic regret bounds on this composite cost in
the setting that $f_{t}$ is known to the learner before making the prediction.
If we consider $f_{t}(x)=(x-y_{t})^{2}$, then the baseline they compare
against reduces to the offline Trend Filtering (TF) estimate when
$\sum_{i=2}^{n}|x_{t}-x_{t-1}|\leq L=C_{n}$. Then Theorem 10 of (Chen et al.,
2018a) states that the cumulative composite cost incurred by their proposed
policy differs from that of the TF estimate by a term that is
$O(\sqrt{nC_{n}})$. However, this doesn’t translate to a meaningful regret
bound in our setting.

(Hall and Willett, 2013) proposes the Dynamic Mirror Descent (DMD) algorithm
that make use of a family of dynamical models for making prediction at each
time step. They achieve a dynamic regret bound of
$O(\sqrt{n}(1+V_{\phi_{t}}(\boldsymbol{\theta}_{T})))$ where the second term
measures the quality of the dynamical models in predicting ground truth.

#### Comparison to Online Isotonic Regression.

(Kotłowski et al., 2016) considers the dynamic regret minimization,

$\displaystyle\sum_{t=1}^{n}(x_{t}-y_{t})^{2}-\min_{(\theta_{1},...,\theta_{n})}\sum_{t=1}^{n}(\theta_{t}-y_{t})^{2},$
(4)

where $y_{t}\leq B$ is a label revealed by the environment, $x_{t}\leq B$ is
the prediction of the learner, and the comparator sequence should obey
$0\leq\theta_{1}\leq...\leq\theta_{n}\leq B$. Here $B$ is a fixed positive
number. Note that their setting and our framework are mutually reducible to
each other in terms of regret guarantees via 3. They propose a minimax policy
that achieves a dynamic regret of $\tilde{O}(n^{1/3})$ which translates to an
$\tilde{O}(n^{1/3})$ in probability in our setting under the isotonic ground
truth restriction.

We note that the isotonic comparator sequence belong to a TV class of
variational budget $C_{n}=B$. By using an argument similar to that in appendix
H which involves converting to deterministic noise setting and conditioning on
a high probability event, it can be shown that our policy is out of the box
minimax with high probability in isotonic framework when observations are
noisy versions of an isotonic sequence.

#### Comparison to Online Non-Parametric regression methods.

We note that our problem falls into the more general framework of online non-
parametric regression setting studied in (Rakhlin and Sridharan, 2015). We can
reduce our dynamic regret minimization to their framework by using a similar
argument as above through (3). Since the bounded TV class is sandwiched
between Besov spaces $B^{1}_{1,q}$ for the range $1\leq q\leq\infty$, the
discussion in section 5.8 of (Rakhlin and Sridharan, 2015) establishes that
minimax growth w.r.t $n$ as $O(n^{1/3})$ in the online setting for TV class.
Thus our bounds, modulo logarithmic factor, matches with theirs though we give
the precise dependence on $C_{n}$ and $\sigma$ as well. It is worthwhile to
point out that while the bound in (Rakhlin and Sridharan, 2015) is non-
constructive, we achieve the same bound via an efficient algorithm.

(Gaillard and Gerchinovitz, 2015b) proposes a minimax policy wrt to
comaparator functions that are Holder smooth. In particular, for the Holder
class $H_{1}$ that satisfy $|f(x)-f(y)|\leq\lambda|x-y|$, their algorithm
yields a regret of $\tilde{O}(n^{1/3})$. It is known ((Tibshirani, 2015)) that
$H_{1}$ is sandwiched between two Sobolev balls having the same minimax rate
in the iid batch statistical learning setting. Since our policy is optimal for
Sobolev space (appendix F), it is also optimal over Holder ball $H_{1}$ when
the observations are noisy versions of a Holder smooth functions. Though the
framework of (Gaillard and Gerchinovitz, 2015b) doesn’t impose this
distributional assumption. The runtime of their policy for $H_{1}$ class is
$O(n^{7/3}\log n)$. It should be noted that Sobolev and Holder classes are
arguably easier to tackle than the TV class since both of them can be embedded
inside a TV class.

#### Strongly Adaptive Regret.

Daniely et al. (2015) introduced the notion of Strongly Adaptive (SA) regret
where the online learner is guaranteed to have low static regret for any
interval within the duration of the game. They also propose a meta algorithm
which can convert an algorithm of good static regret to one with good SA
regret. However low static regret for any interval doesn’t help in our setting
because in each interval we are competing with a stronger dynamic adversary. A
notion of SA dynamic regret would an interesting topic to explore.

For minimizing dynamic regret, Zhang et al. (2018b) proposed a meta policy
that uses an algorithm with good SA regret as its subroutine. Hence we can use
their framework with squared error loss functions as discussed above. They
show that OGD has an SA regret of $O(\log(n))$ for strongly convex loss
functions. Using OGD as the subroutine and applying corollary 7 of their paper
yields a bound $\tilde{O}(n)$. By a similar argument one gets the same linear
regret rate when online newton step is used as the subroutine. However, we
should note that their algorithm works without the knowledge of radius of the
TV ball $C_{n}$.

#### Classical time series forecasting models.

Finally, we note that our work is complementary to much of the classical work
in time-series forecasting (e.g., Box-Jenkins method/ARIMA Box and Jenkins
(1970), Hidden Markov Models (Baum and Petrie, 1966)). These methods aim at
using dynamical systems to capture the recurrent patterns under a stationary
stochastic process, while we focus on harnessing the nonstationarity. Our work
is closer to the “trend smoothing” literature (e.g., the celebrated Hodrick-
Prescott filter (Hodrick and Prescott, 1997), trend filtering (Kim et al.,
2009; Tibshirani, 2014; Hutter and Rigollet, 2016)).

##  Appendix B Additional Experiments

Figure 4: _An illustration of Arrows on a linear trend which has homogeneous
smoothness_

Figure 5: _An illustration of Arrows on a step trend with abrupt
inhomogeneity._

The function that we generated in Figure 2 is a hybrid function which in the
first half is a “discretized cubic spline” with more knots closely placed
towards the end. In the second half it is a Doppler function
$f(t)=\sin\left(\frac{2\pi(1+\epsilon)}{t/n+0.38}\right)$ with $n$ being the
time horizon. We observe noisy data $y_{i}=f(i/n)+z_{i}$, $i=1,...,n$ and
$z_{i}$ are iid normal variables with $\sigma=1$. The value of $C_{n}$ for
$n>60K$ is around 17. Hence for all $n>83521$, we are under the $n^{1/3}$
regime of $\sigma\sqrt{\log(n)/n}<C_{n}<\sigma n^{1/4}$.

The window size for moving averages and partition width of OGD were tuned
optimally for the TV class (see Appendix C for details). Figure 2 depicts the
estimated signals and dynamic regret averaged across 5 runs in a log log plot.
The left panel illustrates that Arrows is locally adaptive to heterogeneous
smoothness of the ground truth. Red peaks in the figure signifies restarts.
During the initial and final duration, the signal varies smoothly and Arrows
chooses a larger window size for online averaging. In the middle, signal
varies rather abruptly. Consequently Arrows chooses a smaller window size. On
the other hand, the linear smoothers OGD and MA attains a suboptimal
$\tilde{O}(\sqrt{n})$ regret.

In Figure 4 and 5 we plot the estimates and log-log regret for two more
functions: A linear function that is homogeneously smooth and less challenging
and a step function which has an abrupt discontinuity making it more
inhomogeneous than linear but have lesser inhomogeneity w.r.t hybrid signal
considered in 3.7. Both OGD and MA were optimally tuned for the TV class as in
Appendix C.

The red peaks corresponds to restarts by Arrows. For linear functions we can
see that ARROWS chooses inter-restart duration/bin-widths that are constant
throughout. This is expected as a linear trend is spatially homogeneous. For
the step function, we see that Arrows restart only once since the start.
Further, notice that it quickly restarts once the bump is hit. For both of
these functions, necessary scaling is done so that we are in the $n^{1/3}$
regime quite early.

##  Appendix C Upper bounds of linear forecasters

In this section we compute the optimal batch size for Restarting OGD and
optimal window size for moving averages to yield the $\tilde{O}(\sqrt{n})$
regret rate.

######  Theorem 2.

Let the feedback be $y_{t}=\theta_{t}+Z_{t}$ where $Z_{t}$ is an independent,
$\sigma$-subgaussian random variable. Let $\theta_{1:n}\in\mathrm{TV}(C_{n})$.
Restarting OGD with batch size of $\sqrt{n\log n}\frac{\sigma}{C_{n}}$
achieves an expected dynamic regret of $\tilde{O}(U^{2}+C_{n}^{2}+\sigma
C_{n}\sqrt{n})$.

###### Proof.

Note that in our setting with squared error losses
$f_{t}(x)=(x-\theta_{t})^{2}$, the update rule of restarting OGD reduces to
computing online averages. Thus OGD essentially divides the time horizon $n$
into fixed size batches and output online averages within each batch. Our
objective here is to compute the optimal batch size that minimizes the dynamic
regret.

We will bound the expected regret. Let $x_{t}$ be the estimate of OGD at time
$t$. Let batches be numbered as $1,...,\lceil n/L\rceil$ where $L$ is the
fixed batch size. Let the total variation of ground truth within batch $i$ be
$C_{i}$. Time interval of batch $i$ is denoted by $[t_{h}^{(i)},t_{l}^{(i)}]$.
Due to bias variance decomposition within a batch we have,

$\displaystyle
R_{i}=\sum_{t=t_{h}^{(i)}}^{t_{l}^{(i)}}E[(x_{t}-\theta_{t})^{2}]$
$\displaystyle=(\theta_{t_{h}^{(i)}-1}-\theta_{t_{h}^{(i)}})^{2}+\sum_{t=t_{h}^{(i)}+1}^{t_{l}^{(i)}}(\theta_{t}-\bar{\theta}_{t_{h}^{(i)}:t-1})^{2}+\frac{\sigma^{2}}{t-t_{h}^{(i)}},$
(5)
$\displaystyle\leq(\theta_{t_{h}^{(i)}-1}-\theta_{t_{h}^{(i)}})^{2}+LC_{i}^{2}+\sigma^{2}(2+\log
L),$ (6)

with the convention $\theta_{0}=0$ and at start of bin our prediction is just
the noisy realization of the previous data point.

Summing across all bins gives,

$\displaystyle\sum_{i=1}^{\lceil n/L\rceil}R_{i}$ $\displaystyle\leq
LC_{n}^{2}+2\sigma^{2}\frac{n(2+\log L)}{L}+U^{2}+C_{n}^{2}.$ (7)

where we have used assumption (A4) to bound the bias of the first prediction.
The above expression can be minimized by setting $L=\sqrt{n\log
n}\frac{\sigma}{C_{n}}$ to yield a regret bound of $O(U^{2}+C^{2}+\sigma
C_{n}\sqrt{n\log n})$ ∎

######  Theorem 3.

Under the same setup as in Theorem 2, moving averages with window size
$\frac{\sigma\sqrt{n}}{C_{n}}$ yields a dynamic regret of $O(\sigma
C_{n}\sqrt{n}+U^{2}+C_{n}^{2})$

###### Proof.

Let the window size of moving averages be denoted by $m$. Consider the
prediction at a time $x_{t},t\geq m$. By bias variance decomposition we have,

$\displaystyle E[(x_{t}-\theta_{t})^{2}]$
$\displaystyle=\left(\theta_{i}-\frac{\sum_{j=i-m}^{i-1}\theta_{j}}{m}\right)^{2}+\frac{\sigma^{2}}{m}.$
(8)

By Jensen’s inequality,

$\displaystyle\left(\theta_{i}-\frac{\sum_{j=i-m}^{i-1}\theta_{j}}{m}\right)^{2}$
$\displaystyle\leq\frac{\sum_{j=i-m}^{i-1}(\theta_{j}-\theta_{i})^{2}}{m},$
(9)
$\displaystyle\leq\frac{2\sum_{j=i-m}^{i-1}(j-i+1+m)(\theta_{j+1}-\theta_{j})^{2}}{m}\text{
,by $(a+b)^{2}\leq 2a^{2}+2b^{2}$}.$ (10)

Notice that the term $(\theta_{i}-\theta_{i-1})^{2}$ will be multiplied by a
factor $m$ in the above bias bound at time point $i$, $m-1$ times in the next
time point $i+1$ and so on. By summing this bias bound across the times
points, we obtain

$\displaystyle\sum_{i=m}^{n}\frac{2\sum_{j=i-m}^{i-1}(j-i+1+m)(\theta_{j+1}-\theta_{j})^{2}}{m}$
$\displaystyle\leq 4m\sum_{i=1}^{n-1}(\theta_{i}-\theta_{i+1})^{2}+U^{2},$
(11) $\displaystyle\leq 4mC_{n}^{2}+U^{2}.$ (12)

The squared bias for the initial points can be bounded by.

$\displaystyle\sum_{i=1}^{m-1}(\theta_{i}-\hat{\theta}_{(1:i-1)})^{2}$
$\displaystyle\leq U^{2}+C_{n}^{2}.$ (13)

Summing the variance terms yields,

$\displaystyle\sum_{t=1}^{n}\mathrm{Var}{(x_{t})}$
$\displaystyle=\sum_{t=1}^{m-1}\frac{\sigma^{2}}{t}+\sum_{t=m}^{n}\frac{\sigma^{2}}{m},$
(14) $\displaystyle\leq\frac{(1+\log m+n)\sigma^{2}}{m}.$ (15)

Thus the total MSE can be minimized by setting
$m=\frac{\sigma\sqrt{n}}{C_{n}}$, we obtain a dynamic regret bound of
$O(\sigma C_{n}\sqrt{n}+U^{2}+C_{n}^{2})$

∎

##  Appendix D Proof of useful lemmas

We begin by recording an observation that follows directly from the policy.

######  Lemma 1.

For $m^{th}$ bin that spans the interval $[t_{h}^{(m)},t_{l}^{(m)}]$,
discovered by the policy, let the lengths of
$\hat{\alpha}(t_{h}^{(m)}:t_{l}^{(m)}-1)$ and
$\hat{\alpha}(t_{h}^{(m)}:t_{l}^{(m)})$ be $k$ and $k^{+}$ respectively. The

$\sum_{l=0}^{\log_{2}(k)-1}2^{l/2}\|\hat{\alpha}(t_{h}^{(m)}:t_{l}^{(m)}-1)[l]\|_{1}\leq\sigma$
and
$\sum_{l=0}^{\log_{2}(k^{+})-1}2^{l/2}\|\hat{\alpha}(t_{h}^{(m)}:t_{l}^{(m)})[l]\|_{1}>\sigma$

Next we prove the marginal sub-gaussianity of the wavelet coefficients.

######  Lemma 2.

Consider the observation model $y_{i}=\theta_{i}+\sigma z_{i}$, where $z_{i}$
is iid sub-gaussian with parameter 1, $i=1,..,n$. Let $\alpha_{i}$ denote the
wavelet coefficients of the sequence $z=pad_{0}(y_{1},...y_{n})$. Then each
$\alpha_{i}$ is sub-gaussian with parameter $2\sigma$.

###### Proof.

Without loss of generaility let’s charecterize $\alpha_{1}$. Let
$\boldsymbol{u}=[u_{1},...u_{n}]^{T}$ denote the first row of the orthonormal
wavelet transform matrix. Then,

$\displaystyle\alpha_{1}=\sum_{i=1}^{n}y_{i}\left(u_{i}(1-\frac{1}{n})-\sum_{j=1,j\neq
i}^{n}\frac{u_{j}}{n}\right).$ (16)

Thus $\alpha_{1}$ is a differentiable function of iid sub-gaussian noise
$z_{i}$. We can find its Lipschtiz constant by bounding the gradient w.r.t
$z_{i}$ as follows,

$\displaystyle\|\nabla\alpha_{1}(z_{1},...,z_{n})\|_{2}$
$\displaystyle\leq\sigma\left(\sum_{i=1}^{n}2u_{i}^{2}(1-\frac{1}{n})^{2}+\frac{2}{n}\sum_{j=1,j\neq
i}^{n}u_{j}^{2}\right)^{\frac{1}{2}},$ (17)
$\displaystyle\leq\sigma\left(2+2\right)^{\frac{1}{2}},$ (18)
$\displaystyle=2\sigma.$ (19)

By proposition 2.12 in Johnstone (2017) we conclude that $\alpha_{1}$ sub-
gaussian with parameter $2\sigma$. ∎

In the next lemma, we record the uniform shrinkage property of soft-
thresholding estimator.

######  Lemma 3.

For any interval $[t_{h},t_{l}]$, let $Y=pad_{0}(y_{t_{h}},...,y_{t_{l}})$ and
$\Theta=pad_{0}(\theta_{t_{h}},...,\theta_{t_{l}})$. Then
$|(T(HY))_{i}|\leq|(H\Theta)_{i}|$ with probability at-least
$1-2n^{3-\beta/8}$ for each co-ordinate $i$.

###### Proof.

Consider a fixed bin $[\underaccent{\bar}{l},\bar{l}]$ with zero padded vector
$Y\in R^{k}$. Due to sub-gaussian tail inequality, we have
$|(HY)_{i}-(H\Theta)_{i}|\leq\sigma\sqrt{\beta\log(n)}$ with probability at-
least $1-2/n^{\beta/8}$. Consider the case
$(H\Theta)_{i}\geq\sigma\sqrt{\beta\log(n)}$. Then both the scenarios
$(HY)_{i}\leq\sigma\sqrt{\beta\log(n)}$ and
$(HY)_{i}>\sigma\sqrt{\beta\log(n)}$ leads to shrinkage to a value that is
smaller than $|(H\Theta)_{i}|$ in magnitude due to soft-thresholding with
threshold set to $\sigma\sqrt{\beta\log(n)}$. Now consider the case when
$0\leq(H\Theta)_{i}\leq\sigma\sqrt{\beta\log(n)}$. Again, soft-thresholding in
both scenarios $(HY)_{i}\leq\sigma\sqrt{\beta\log(n)}$ and
$\sigma\sqrt{\beta\log(n)}\leq(HY)_{i}\leq(H\Theta)_{i}+\sigma\sqrt{\beta\log(n)}$
leads to shrinkage to a value that is smaller than $|(H\Theta)_{i}|$ in
magnitude. One can come up with a similar argument for the case where
$(H\Theta)_{i}\leq 0$. Now applying a union bound across all $O(n)$ co-
ordinates and all $O(n^{2})$ bins, we get the statement of the lemma. ∎

######  Lemma 4.

The number of bins, $M$, discovered by the policy is at-most
$\max\\{1,2n^{1/3}C_{n}^{2/3}\sigma^{-2/3}\log(n)\\}$ with probability at-
least $1-2n^{3-\beta/2}$.

###### Proof.

Let $\Theta_{m}=[\theta_{1}^{(m)},\theta_{2}^{(m)},...,\theta_{p}^{(m)}]^{T}$
be the mean subtracted and zero padded ground truth sequence values in
$m^{th}$ bin $[\underaccent{\bar}{l},\bar{l}]$ discovered by our policy.
$y^{(m)}=[y_{1}^{(m)},y_{2}^{(m)},...,y_{p}^{(m)}]^{T}$ be the corresponding
mean subtracted and zero padded observations. Note that due to zero padding
$p\leq 2(\bar{l}-\underaccent{\bar}{l})$ and some of the last values in the
vector can be zeroes. Let $\alpha_{m}(\underaccent{\bar}{l}:\bar{l})=H\Theta$
denotes the discrete wavelet coefficient vector. We can view the computation
of the Haar coefficients as a recursion. At each level $l$ of the recursion,
the entire length $p$, is divided into $2^{l}$ intervals. Let the sample
averages of elements of $\Theta_{m}$ in these intervals be denoted by the
sequence
$\\{\tilde{\theta}_{1},\tilde{\theta}_{2},...,\tilde{\theta}_{2^{l}}\\}$. Let
$\alpha_{m}^{(l)}\in\mathbb{R}^{2^{l}}$ denotes the vector of Haar
coefficients at level $l$.

First note that the Haar coefficient
$\alpha_{m}^{(l)}(i)=\frac{1}{2}\sqrt{\frac{p}{2^{l}}}(\tilde{\theta}_{2i}-\tilde{\theta}_{2i-1})$
with $i=1,...,2^{l}$.

$\displaystyle\|\alpha_{m}^{(l)}\|_{1}^{2}$
$\displaystyle\leq\frac{p}{2^{l+2}}\left(\sum_{i=1}^{2^{l}}|\tilde{\theta}_{2i}-\tilde{\theta}_{2i-1}|\right)^{2},$
(20)
$\displaystyle\leq\frac{pTV^{2}[\underaccent{\bar}{l}-1:\bar{l}]}{2^{l}},$
(21)

where $TV[a,b]$ denotes the total variation of the true sequence in the
interval $[a,b]$. The last inequality holds because the total variation of the
smoothed sequence must be at-most four times the entire total variation of
true sequence. The factor 4 is due to the fact that total variation when we
pad a mean zero sequence with zeroes is at-most twice the total variation
before zero padding.

We have,

$\displaystyle\frac{1}{\sqrt{p}}\sum_{l=0}^{\log_{2}(p)-1}2^{l/2}\|\alpha_{m}^{(l)}\|_{1}$
$\displaystyle\leq\log p\>TV[\underaccent{\bar}{l}-1:\bar{l}].$ (22)

In the policy we compute
$\hat{\alpha}_{m}(\underaccent{\bar}{l}:\bar{l})=T(Hy^{(m)})$ with the soft
thresholding factor of $\sigma\sqrt{\beta\log(n)}$. From lemma 3, we have
$|(T(Y))_{i}|\leq|(H\Theta)_{i}|\>\forall i\in[1,p]$ with probability at-least
$1-2n^{3-\beta/8}$. Since $[\underaccent{\bar}{l},\bar{l}]$ is a bin
discovered by policy, lemma 1 gives a lowerbound on
$\|\alpha_{m}(\underaccent{\bar}{l}:\bar{l})\|$ . Putting it all together
yields the relation,

$\frac{\sigma}{\sqrt{p}}<\frac{1}{\sqrt{p}}\sum_{l=0}^{\log_{2}(p)-1}2^{l/2}\|\hat{\alpha}_{m}^{(l)}(\underaccent{\bar}{l}:\bar{l})\|_{1}\leq\frac{1}{\sqrt{p}}\sum_{l=0}^{\log_{2}(p)-1}2^{l/2}\|\alpha_{m}^{(l)}(\underaccent{\bar}{l}:\bar{l})\|_{1}\leq\log(p)\>TV[\underaccent{\bar}{l}-1:\bar{l}],$
(23)

with probability at-least $1-2n^{3-\beta/8}$.

Thus the total variation in the time interval
$[\underaccent{\bar}{l}-1,\bar{l}]$ can be lower bounded in probability as

$TV[\underaccent{\bar}{l}-1:\bar{l}]>\frac{\sigma}{\sqrt{p}\log n}.$ (24)

Due to assumption $(A3)$ we have,

$\sum_{i=1}^{M}TV[\underaccent{\bar}{l}^{i}-1:\bar{l}^{i}]=C_{n},$ (25)

where $[\underaccent{\bar}{l}^{i}:\bar{l}^{i}]$ are the bins discovered by the
policy.

Let $p_{i}$ be the padded width of bin $i$ discovered by the policy. Then,

$\displaystyle C_{n}\log n$
$\displaystyle\geq\sum_{i=1}^{M}\frac{\sigma}{\sqrt{p_{i}}},$ (26)
$\displaystyle\geq\frac{M^{2}\sigma}{\sum_{i=1}^{M}\sqrt{p_{i}}},$ (27)

where the last line is obtained via Jensen’s inequality. Now using Holder’s
inequality $\|x\|_{\beta}\leq
d^{\frac{1}{\beta}-\frac{1}{\alpha}}\|x\|_{\alpha}$ for $0<\beta\leq\alpha$,
$x\in\mathbb{R}^{d}$ with $\alpha=1/2$, $\beta=1$ and noting that
$\sum_{i=1}^{M}p_{i}\leq 2T$ gives,

$\displaystyle\sigma M^{2}$ $\displaystyle\leq C_{n}\log
n\sum_{i=1}^{M}\sqrt{p_{i}},$ (28) $\displaystyle\leq C_{n}\log n\sqrt{Mn}.$
(29)

Hence we get $M\leq(2n)^{1/3}(C_{n}\log n)^{2/3}\sigma^{-2/3}\leq
2n^{1/3}C_{n}^{2/3}\sigma^{-2/3}\log(n)$.

When $C_{n}=0$, (23) implies that our policy will not restart with probability
at-least $1-2n^{3-\beta/8}$ making $M=1$. ∎

We restate two useful results from Donoho (1995).

######  Lemma 5.

Consider the observation model $y=\alpha+Z$, where $y\in R^{k}$ and
$|Z_{i}|\leq\delta\forall\>i\in[1,k]$. Let $\hat{\alpha}_{\delta}$ be the soft
thresholding estimator with input $y$ and threshold $\delta$, then

$\|\hat{\alpha}_{\delta}-\alpha\|^{2}\leq\sum_{i=1}^{k}min\\{\alpha_{i}^{2},4\delta^{2}\\}.$
(30)

######  Lemma 6.

Consider the observation model $y=\alpha+Z$, where $y\in R^{k}$, $\alpha\in A$
and each $Z_{i}$ is sub-gaussian with parameter $\sigma^{2}$. If A is solid
and orthosymmetric, then

$\inf_{\hat{\alpha}}\sup_{\alpha\in
A}E[\|\hat{\alpha}-\alpha\|^{2}]\geq\frac{1}{2.22}\sup_{A}\sum_{i=1}^{k}min\\{\alpha_{i}^{2},\sigma^{2}\\}.$
(31)

Let’s pause a moment to ponder how remarkable the above lemma is. The
observations need not be even iid. Given $A$ is solid and orthosymmetric, all
that is required is the marginal sub-gaussianity as the soft-thresholding
operation works co-ordinate wise. Now we reprove theorem 4.2 from Donoho
(1995) with a slight modification of threshold value in the estimator.

######  Theorem 4.

With probability at-least $1-2n^{1-\beta/2}$, under the model in lemma 6, the
soft thresholding estimator $\hat{\alpha}_{\delta}$ with
$\delta=\sigma\sqrt{\beta\log(n)}$ obeys

$\|\hat{\alpha}_{\delta}-\alpha\|^{2}\leq
80(1+\log(n))\inf_{\hat{\alpha}}\sup_{\alpha\in
A}E[\|\hat{\alpha}-\alpha\|^{2}].$ (32)

###### Proof.

Consider the soft thresholding estimator $\hat{\alpha}_{\delta}$. By Gaussian
tail inequality and union bound we have $P(\sup_{i}|Z_{i}|\geq\delta)\leq
2n^{1-\beta/2}$. Conditioning on the event $\sup_{i}|Z_{i}|\leq\delta$ and
applying lemma 5,

$\displaystyle\|\hat{\alpha}_{\delta}-\alpha\|^{2}$
$\displaystyle\leq\sum_{i=1}^{k}min\\{\alpha_{i}^{2},4\delta^{2}\\},$ (33)
$\displaystyle=\sum_{i=1}^{k}min\\{\alpha_{i}^{2},4\beta\sigma^{2}\log(n)\\},$
(34) $\displaystyle\leq
max\\{1,4\beta\log(n)\\}\sum_{i=1}^{k}min\\{\alpha_{i}^{2},\sigma^{2}\\},$
(35) $\displaystyle\leq(1+4\beta\log(n))\sup_{\alpha\in
A}\sum_{i=1}^{k}min\\{\alpha_{i}^{2},\sigma^{2}\\},$ (36) $\displaystyle\leq
4\beta(1+\log(n))\>2.22\>\inf_{\hat{\alpha}}\sup_{\alpha\in
A}E[\|\hat{\alpha}-\alpha\|^{2}],$ (37)

where the last line follows from lemma 6. ∎

It can be shown that wavelet coefficients of functions residing in the TV
class is solid and orthosymmetric. As shown in lemma 2, the noisy wavelet
coefficients are marginally sub-gaussian. Thus in the coefficient space, we
are under the same observation model as in lemma 6. Using a uniform bound
argument across all $O(n^{2})$ bins and lemma 2 leads to the following
corollary.

######  Corollary 3.

The soft-thresholded wavelet coefficients of re-centered and zero padded noisy
data within any interval $[t_{h},t_{l}]$ satisfy relation (32) with
probability atleast $1-2n^{3-\beta/8}$.

Next, we record an important preliminary bound that will be used in proving
the main result.

######  Lemma 7.

With probability at-least $1-\frac{\delta}{2}$, the total squared error for
online averaging between two arbitrarily chosen time points $t_{h}$ and
$t_{l}$ satisfies

$\sum_{t=t_{h}}^{t_{l}}(x_{t}^{t_{h}}-\theta_{t})^{2}\leq
4\sigma^{2}\log(4n^{3}/\delta)(2+\log(t_{l}-t_{h}+1))+2(\theta_{t_{h}-1}-\theta_{t_{h}})^{2}+2\sum_{t=t_{h}+1}^{t_{l}}(\bar{\theta}_{t_{h}:t-1}-\theta_{t})^{2}.$
(38)

###### Proof.

Throughout this lemma we assume the notation $\theta_{0}=0$. For proving this,
first we bound the squared error for online sample averages within a bin,
$b[\underaccent{\bar}{l},\bar{l}]$, that starts and ends at fixed times
$\underaccent{\bar}{l}$ and $\bar{l}$ respectively. Then a uniform bound
argument will be used for bounding the squared error within any arbitrarily
chosen bin. Note that $b[\underaccent{\bar}{l},\bar{l}]$ represents any fixed
time interval and may not be even chosen by the policy. For
$t\in[\underaccent{\bar}{l},\bar{l}]$, consider the prediction
$x_{t}^{\underaccent{\bar}{l}}$, with same notation as used in the policy.
Define a random variable $Z_{t}$ as

$Z_{t}=\frac{(x_{t}^{\underaccent{\bar}{l}}-\theta_{t})-(\lambda_{t}-\theta_{t})}{\sigma\sqrt{1/[t-\underaccent{\bar}{l}]_{1+}}},$
(39)

where $[x]_{1+}=max\\{1,x\\}$, $\lambda_{l}=\theta_{\underaccent{\bar}{l}-1}$
and $\lambda_{t}=\bar{\theta}_{\underaccent{\bar}{l}:t-1},\forall
t>\underaccent{\bar}{l}$. $Z_{t}$ is subgaussian with variance parameter 1 and
mean 0. Hence by sub-gaussian tail inequality, we have
$P(|Z_{t}|\geq\sqrt{2\log(4/\delta)})\leq\delta/2$. By noting that length of a
bin is $O(n)$ and applying uniform bound across all time points within the
current bin we have

$P\left(\sup_{\underaccent{\bar}{l}\leq
t\leq\bar{l}}|Z_{t}|\geq\sqrt{2\log(4n^{3}/\delta)}\right)\leq\delta/2n^{2}.$
(40)

Hence with probability at-least $1-\delta/2n^{2}$,

$|x_{t}^{\underaccent{\bar}{l}}-\theta_{t}|\leq|\lambda_{t}-\theta_{t}|+\sigma\sqrt{\frac{2\log(4n^{3}/\delta)}{[t-\underaccent{\bar}{l}]_{1+}}},\forall
t\in[\underaccent{\bar}{l},\bar{l}].$ (41)

So the squared error within a bin can be bounded in probability as

$\sum_{t=\underaccent{\bar}{l}}^{\bar{l}}(x_{t}^{\underaccent{\bar}{l}}-\theta_{t})^{2}\leq
2(\theta_{\underaccent{\bar}{l}-1}-\theta_{\underaccent{\bar}{l}})^{2}+2\sum_{t=\underaccent{\bar}{l}+1}^{\bar{l}}(\bar{\theta}_{\underaccent{\bar}{l}:t-1}-\theta_{t})^{2}+2\sum_{t=\underaccent{\bar}{l}}^{\bar{l}}\sigma^{2}\frac{2\log(4n^{3}/\delta)}{[t-\underaccent{\bar}{l}]_{1+}}.$
(42)

Here we applied the inequality $(a+b)^{2}\leq 2a^{2}+2b^{2}$ on (41).
Ultimately we are interested in analyzing the MSE within a bin detected by the
policy. However the observations within a bin satisfies the restarting
criterion of the policy and cannot be regarded independent. To break free of
this constraint, we uniformly bound the quantity of interest — MSE here —
across all possible bins. Noting that number of bins is $O(n^{2})$ and
applying uniform bound across all bins gives the following single sided tail
bound.

Let E denote the event:
$\sup_{b[\underaccent{\bar}{l}:\bar{l}]}(x_{t}^{\underaccent{\bar}{l}}-\theta_{t})^{2}-2(\theta_{\underaccent{\bar}{l}-1}-\theta_{\underaccent{\bar}{l}})^{2}-2\sum_{t=\underaccent{\bar}{l}+1}^{\bar{l}}(\bar{\theta}_{\underaccent{\bar}{l}:t-1}-\theta_{t})^{2}-2\sum_{t=\underaccent{\bar}{l}}^{\bar{l}}\sigma^{2}\frac{2\log(4n^{3}/\delta)}{[t-\underaccent{\bar}{l}]_{1+}}\geq
0$.

Then,

$\displaystyle P(E)$ $\displaystyle\leq\delta/2.$ (43)

Hence with probability at-least $1-\delta/2$, any bin $b[t_{h}:t_{l}]$
satisfies (38). ∎

Since (38) holds for any arbitrary interval of the time axis, it is
particularly true for the bins discovered by the policy. Therefore the total
squared error $T$ of the policy is upper bounded in probability by the sum of
bin bounds of the form,

$T\leq\sum_{m=1}^{M}4\sigma^{2}\log(4n^{3}/\delta)(2+\log(t_{l}^{(m)}-t_{h}^{(m)}+1))+2(\theta_{t_{h}^{(m)}-1}-\theta_{t_{h}^{(m)}})^{2}+2\sum_{t=t_{h}^{(m)}+1}^{t_{l}^{(m)}}(\bar{\theta}_{t_{h}^{(m)}:t-1}-\theta_{t})^{2},$
(44)

where the outer sum iterates over the bins and $M$ is the total number of
bins. The first term inside the outer summation can be controlled if we can
upper bound $M$. Now we set out to prove our main theorem.

##  Appendix E Proof of Theorem 1

From the discussion in section 1.1, the goal of bounding dynamic regret of the
policy can be achieved by bounding the total squared error of its predictions.
Our solution proceeds in two steps. First we upper bound the total squared
error within a bin. Then we construct an upper bound for the number of bins
spawned by the policy. With these two bounds in place, we bound the total
squared error of the policy (44).

Let’s first proceed to get a bound on the last summation term in (44). We use
a reduction towards Follow The Leader (FTL) strategy. The term is basically
the regret incurred by an FTL game with quadratic loss function for the
duration $[t_{h},t_{l}]$.

Let
$\Theta(t_{h}:t_{l}-1)=pad_{0}(\theta_{t_{h}},...,\theta_{t_{l}-1})=[\Theta_{t_{h}},...,\Theta_{t_{h}+k-1}]^{T}$
denotes mean subtracted the zero padded true sequence in the interval
$[t_{h},t_{l}-1]$. Then,

$\displaystyle\sum_{t=t_{h}}^{t_{l}}(\bar{\theta}_{t_{h}:t-1}-\theta_{t})^{2}$
$\displaystyle=(\bar{\theta}_{t_{h}:t_{l}-1}-\theta_{t_{l}})^{2}+\sum_{t=t_{h}}^{t_{l}-1}(\bar{\theta}_{t_{h}:t-1}-\theta_{t})^{2},$
(45)
$\displaystyle\leq(\bar{\theta}_{t_{h}:t_{l}-1}-\theta_{t_{l}})^{2}+\sum_{t=t_{h}}^{t_{l}-1}\frac{(\bar{\theta}_{t_{h}:t-1}-\theta_{t})^{2}}{(t-t_{h}+1)}+\sum_{t=t_{h}}^{t_{l}-1}(\bar{\theta}_{t_{h}:t_{l}-1}-\theta_{t})^{2},$
(46)
$\displaystyle=(\bar{\theta}_{t_{h}:t_{l}-1}-\theta_{t_{l}})^{2}+\sum_{t=t_{h}}^{t_{l}-1}\frac{(\bar{\theta}_{t_{h}:t-1}-\theta_{t})^{2}}{(t-t_{h}+1)}+\|\Theta(t_{h}:t_{l}-1)\|^{2}.$
(47)

We have applied FTL reduction for online game of predicting the true sequence
$\theta_{t_{h}},...,\theta_{t_{l}-1}$ to get (47).

In the discussion below we assume that $\|D\theta_{1:n}\|_{1}\leq C_{n}$ and
$|\theta_{1}|\leq U$.

Now let’s try to bound the term $\|\Theta(t_{h}:t_{l}-1)\|_{2}^{2}$. This is
basically the regret of the best expert. By triangle inequality,

$\displaystyle\|\Theta(t_{h}:t_{l}-1)\|^{2}$
$\displaystyle\leq\|\hat{\alpha}(t_{h}:t_{l}-1)\|_{1}^{2}+\|\hat{\alpha}(t_{h}:t_{l}-1)-\alpha(t_{h}:t_{l}-1)\|_{2}^{2},$
(48)
$\displaystyle\leq\left(\sum_{l=0}^{\log_{2}(p)-1}2^{l/2}\|\hat{\alpha}(t_{h}:t_{l}-1)[l]\|_{1}\right)^{2}$
$\displaystyle\qquad+\|\hat{\alpha}(t_{h}:t_{l}-1)-\alpha(t_{h}:t_{l}-1)\|_{2}^{2},$
(49)

where $p$ is the padded length.

We can base our online averaging restart rule on the output of wavelet
smoother. Suppose we decide to restart when
$\|\hat{\alpha}(t_{h}:t_{l})\|_{1}\geq Kn^{-1/3}$ for a constant $K$. Then the
first term of (49) gives the optimal rate of $O(n^{1/3})$ when summed across
all bins. But the estimation error term
$\|\hat{\alpha}(t_{h}:t_{l}-1)-\Theta(t_{h}:t_{l}-1)\|^{2}$ should also be
controlled. If the smoother is minimax over any bin $[t_{h},t_{l}]$, then we
can hope to get minimaxity over the entire horizon. However, the total
variation inside the bin is not known to the smoother. This is where the
adaptive minimaxity of wavelet smoother comes to rescue.

Suppose $\mathcal{F}$ denotes the class of functions $f$ with total variation
$TV(f)\leq C_{n}$. Let $\mathcal{A}$ denote the set of all coefficients of the
continuous wavelet transform of functions $f\in\mathcal{F}$. Then
$\mathcal{A}\subset\Theta_{1,\infty}^{1/2}(C_{n})$, where
$\Theta_{1,\infty}^{1/2}(C_{n})$ is a Besov body as defined in Donoho et al.
(1998). The minimax rate of estimation in this Besov body is
$O(n^{-2/3}C_{n}^{2/3}\sigma^{4/3})$ where n is the number of observations.
However, this is the rate of convergence of the $L_{2}$ function norm instead
of the discrete (input-averaged) norm that we consider here. Over the Besov
spaces, these two norms are close enough that the rates do not change (see
section 15.5 of Johnstone (2017)). Hence Corollary 3 can be used to control
the bias.

Let $\hat{y}(t_{h}:t)$ denotes the soft-thresholding estimates of the vector
$pad_{0}(y_{t_{h}:t})$. i.e $\hat{y}(t_{h}:t)=H^{T}T(H\>pad_{0}(y(t_{h}:t)))$.

$\displaystyle(\bar{\theta}_{t_{h}:t_{l}-1}-\theta_{t_{l}})^{2}$
$\displaystyle\leq
2(\theta_{t_{l}-1}-\theta_{t_{l}})^{2}+2(\bar{\theta}_{t_{h}:t_{l}-1}-\theta_{t_{l}-1})^{2},$
(50) $\displaystyle\leq
2(\theta_{t_{l}-1}-\theta_{t_{l}})^{2}+4(\hat{y}(t_{h}:t_{l}-1)[t_{l}-1]-(\bar{\theta}_{t_{h}:t_{l}-1}-\theta_{t_{l}-1}))^{2}$
$\displaystyle\quad+4(\hat{y}(t_{h}:t_{l}-1)[t_{l}-1])^{2}.$ (51)

Since L1 norm is greater than L2 norm, the policy’s restart rule implies that

$\displaystyle(\hat{y}(t_{h}:t_{l}-1)[t_{l}-1])^{2}$
$\displaystyle\leq\sigma^{2}$ (52)

Combining (51) and (52), we get

$\displaystyle(\bar{\theta}_{t_{h}:t_{l}-1}-\theta_{t_{l}})^{2}$
$\displaystyle\leq
2(\theta_{t_{l}}-\theta_{t_{l}-1})^{2}+\gamma_{1}(t_{l}-t_{h})^{1/3}\>TV^{2/3}[t_{h}:t_{l}]\>\sigma^{4/3}+\sigma^{2},$
(53)

where last line holds with probablity atleast $1-2n^{3-\beta/8}$ due to
Corollary 3. Here $\gamma_{1}$ is a constant which can depend logarithmically
on the width $t_{l}-t_{h}$.

Now let’s bound the second term in (47). For any $t\in[t_{h},t_{l}-1]$ we
have,

$\displaystyle\sum_{t=t_{h}}^{t_{l}-1}\frac{(\bar{\theta}_{t_{h}:t-1}-\theta_{t})^{2}}{(t-t_{h}+1)}$
$\displaystyle\leq\sum_{t=t_{h}}^{t_{l}-1}\frac{2(\theta_{t}-\theta_{t-1})^{2}+2(\bar{\theta}_{t_{h}:t-1}-\theta_{t-1})^{2}}{t-t_{h}+1},$
(54) $\displaystyle\leq\sum_{t=t_{h}}^{t_{l}-1}2(\theta_{t}-\theta_{t-1})^{2}$
$\displaystyle\quad+\sum_{t=t_{h}}^{t_{l}-1}\frac{4(\hat{y}(t_{h}:t-1)[t-1]-(\bar{\theta}_{t_{h}:t-1}-\theta_{t-1}))^{2}+4(\hat{y}(t_{h}:t-1)[t-1])^{2}}{t-t_{h}+1},$
(55)
$\displaystyle\leq\sum_{t=t_{h}}^{t_{l}-1}2(\theta_{t}-\theta_{t-1})^{2}+(\gamma_{2}(t_{l}-t_{h})^{1/3}\>TV^{2/3}[t_{h}:t_{l}]\>\sigma^{4/3}+4\sigma^{2})(1+\log
n),$ (56)

where the last line holds with probability at-least $1-2n^{3-\beta/8}$.

$\displaystyle\|\Theta(t_{h}:t_{l}-1)\|_{2}^{2}$
$\displaystyle\leq\left(\sum_{l=0}^{\log_{2}(p)-1}2^{l/2}\|\hat{\alpha}(t_{h}:t_{l}-1)[l]\|_{1}\right)^{2},$
$\displaystyle\qquad+\gamma_{3}(t_{l}-t_{h})^{1/3}\>TV^{2/3}[t_{h}:t_{l}]\>\sigma^{4/3},$
(57)
$\displaystyle\leq\sigma^{2}+\gamma_{3}(t_{l}-t_{h})^{1/3}\>TV^{2/3}[t_{h}:t_{l}]\>\sigma^{4/3},$
(58)

with probability at-least $1-2n^{3-\beta/8}$ for some constant $\gamma_{3}$
which can depend logarithmically on the width $t_{l}-t_{h}$.

Due to Corollary 3 the bounds (53), (56), (58) all simultaneously holds with
probability at-least $1-2n^{3-\beta/8}$. Combining these bounds, we get

$\displaystyle\sum_{t=t_{h}}^{t_{l}}(\bar{\theta}_{t_{h}:t-1}-\theta_{t})^{2}$
$\displaystyle\leq
2\|D\theta_{t_{h}:t_{l}}\|_{2}^{2}+\gamma(t_{l}-t_{h})^{1/3}\>TV^{2/3}[t_{h}:t_{l}]\>\sigma^{4/3}+6\sigma^{2}(1+\log(n)),$
(59)

with probability at-least $1-2n^{3-\beta/8}$ and
$\gamma=\gamma_{1}+\gamma_{2}(1+\log(n))+\gamma_{3}$.

When summed across all bins as in (44), with probability at-least
$1-2n^{3-\beta/8}$ we have,

$\displaystyle\sum_{m=1}^{M}\sum_{t=t_{h}^{(m)}}^{t_{l}^{(m)}}(\bar{\theta}_{t_{h}^{(m)}:t-1}-\theta_{t})^{2}$
$\displaystyle\leq U^{2}+2\|D\theta_{1:n}\|_{2}^{2}+6M\sigma^{2}(1+\log n)$
$\displaystyle\quad+\sum_{m=1}^{M}\gamma\>(k^{(m)})^{1/3}\>TV^{2/3}[t_{h}^{(m)}:t_{l}^{(m)}]\>\sigma^{4/3},$
(60) $\displaystyle\leq U^{2}+2\|D\theta_{1:n}\|_{2}^{2}+6M\sigma^{2}(1+\log
n)$
$\displaystyle\qquad+\gamma\sigma^{4/3}n^{1/3}\left(\sum_{m=1}^{M}\frac{k^{(m)}}{n}\right)^{\frac{1}{3}}\left(\sum_{m=1}^{M}TV[t_{h}^{(m)}:t_{l}^{(m)}]\right)^{\frac{2}{3}},$
(61) $\displaystyle\leq U^{2}+2\|D\theta_{1:n}\|_{2}^{2}+6M\sigma^{2}(1+\log
n)$ $\displaystyle\qquad+2\gamma\sigma^{4/3}n^{1/3}C_{n}^{2/3}.$ (62)

Here $k^{(m)}$ is the length of $\Theta(t_{h}^{(m)}:t_{l}^{(m)}-1)$. The term
$(\theta_{t_{h}^{(m)}-1}-\theta_{t_{h}^{(m)}})^{2}$ is at-most $U^{2}$ for the
first bin. We arrive at (61) by applying Holder’s inequality
$x^{T}y\leq\|x\|_{p}\|y\|_{q}$ with $p=3$ and $q=3/2$. For both (61) and (62)
we use the fact that $\sum_{m=1}^{M}k^{(m)}\leq 2n$ where the factor 2 is an
artifact of zero-padding.

By appealing to lemma 4, we have with probability at-least $1-4n^{3-\beta/8}$,

$\displaystyle\sum_{m=1}^{M}\sum_{t=t_{h}^{(m)}}^{t_{l}^{(m)}}(\bar{\theta}_{t_{h}^{(m)}:t-1}-\theta_{t})^{2}$
$\displaystyle\leq U^{2}+2\|D\theta_{1:n}\|_{2}^{2}+12\sigma^{2}\log n$
$\displaystyle\qquad+24(\log(n))^{2}n^{1/3}C_{n}^{2/3}\sigma^{4/3}+\gamma\sigma^{4/3}n^{1/3}C_{n}^{2/3}.$
(63)

Next, we proceed to bound the first summation terms in (44). For this, we
upperbound the number of bins to control the concentration terms in (44) when
summed across all bins. Essentially our decision rule should not lead to over
binning. Observe that the sum of total variations across all bins is $C_{n}$.
If the decision rule guarantees (at-least in probability) that total variation
inside any detected bin is $\tilde{\Omega}(n^{-1/3})$, then the number of bins
is optimally $O(n^{1/3})$. Such a TV lower bounding property is satisfied by
wavelet soft-thresholding as described in lemma 4. This is facilitated by the
uniform shrinkage property of soft-thresholding estimator. More precisely,

Let’s denote

$\displaystyle V_{m}$
$\displaystyle=4\sigma^{2}\log(2n^{3}/\delta)(2+\log(t_{l}^{(m)}-t_{h}^{(m)}+1)).$
(64)

Then,

$\displaystyle\sum_{m=1}^{M}V_{m}$ $\displaystyle\leq
4\sigma^{2}\log(4n^{3}/\delta)(2+\log(n))\max\\{1,2n^{1/3}C_{n}^{2/3}\sigma^{-2/3}\log(n)\\},$
(65) $\displaystyle\leq 4\sigma^{2}\log(4n^{3}/\delta)(2+\log(n))$
$\displaystyle\qquad+8n^{1/3}C_{n}^{2/3}\sigma^{4/3}\log(n)\log(4n^{3}/\delta)(2+\log(n)),$
(66)

with probability at-least $1-2n^{3-\beta/8}$. Here $[t^{m}_{h},t^{m}_{l}]$
corresponds to the $m^{th}$ bin discovered by the policy. This relation
follows due to Lemma 4.

Combining (66) and (63) we have with probability at-least
$1-4n^{3-\beta/8}-\delta/2$

$\displaystyle\begin{split}T\leq{}&8n^{1/3}C_{n}^{2/3}\sigma^{4/3}(2+\log(n))\log(n)\\\
&+4\sigma^{2}\log(4n^{3}/\delta)(2+\log(n))\\\
&+U^{2}+2\|D\theta_{1:n}\|_{2}^{2}+12\sigma^{2}\log n\\\
&\qquad+24(\log(n))^{2}n^{1/3}C_{n}^{2/3}\sigma^{4/3}+2\gamma\sigma^{4/3}n^{1/3}C_{n}^{2/3}.\end{split}$
(67)

By observing that $\|D\theta_{1:n}\|_{2}\leq\|D\theta_{1:n}\|_{1}=C_{n}$ we
get the bound,

$\displaystyle\begin{split}T\leq{}&8n^{1/3}C_{n}^{2/3}\sigma^{4/3}(2+\log(n))\log(n)\\\
&+4\sigma^{2}\log(4n^{3}/\delta)(2+\log(n))\\\
&+U^{2}+2C_{n}^{2}+12\sigma^{2}\log n\\\
&\qquad+24(\log(n))^{2}n^{1/3}C_{n}^{2/3}\sigma^{4/3}+2\gamma\sigma^{4/3}n^{1/3}C_{n}^{2/3}.\end{split}$
(68)

The above bounds holds with probability at-least $1-\delta$, if we set
$\beta=24+\frac{8\log(8/\delta)}{\log(n)}$.

We conclude our proof by observing that the above arguments can be readily
extended to any batch smoother that satisfy the following criteria.

$\bullet$

Adaptive minimaxity over any interval within the time horizon.

$\bullet$

The restart decision rule optimally lowerbounds the total variation of any
spawned bin.

Thus our policy can be viewed as a meta-algorithm that lifts a “well behaved
smoother” to an optimal forecaster in the online setting.

Next we remark how the proof can be adapted to the setting where an extra
boundedness constraint is put on the ground truth. i.e, $\theta_{1:n}\in
TV(C_{n})$ and $|\theta_{i}|\leq B,i=1,\ldots,n$. Then the $U^{2}$ term in
(67) becomes $B^{2}$. The additive $\|D\theta_{1:n}\|_{2}^{2}$ term can be
bounded as,

$\displaystyle\|D\theta_{1:n}\|_{2}^{2}$
$\displaystyle=\sum_{i=2}^{n}(\theta_{i}-\theta_{i-1})^{2},$ (69)
$\displaystyle\leq\sum_{i=2}^{n}(|\theta_{i}|+|\theta_{i-1}|)(|\theta_{i}-\theta_{i-1}|),$
(70) $\displaystyle\leq 2BC_{n}.$ (71)

Thus when $\|\theta_{1:n}\|_{\infty}\leq B$ and if we set
$\beta=24+\frac{8\log(8/\delta)}{\log(n)}$ then with probability at-least
$1-\delta$,

$\displaystyle\begin{split}T\leq{}&8n^{1/3}C_{n}^{2/3}\sigma^{4/3}(2+\log(n))\log(n)\\\
&+4\sigma^{2}\log(4n^{3}/\delta)(2+\log(n))\\\
&+B^{2}+4BC_{n}+12\sigma^{2}\log n\\\
&\qquad+24(\log(n))^{2}n^{1/3}C_{n}^{2/3}\sigma^{4/3}+2\gamma\sigma^{4/3}n^{1/3}C_{n}^{2/3}.\end{split}$
(72)

##  Appendix F Adaptive Optimality in Discrete Sobolev class

In this section, we establish that despite the fact that Arrows is designed
for the total variation class, it adapts to the optimal rates forecasting
sequences that are more regular.

The discrete Sobelov class is defined as

$\displaystyle\mathcal{S}(C_{n}^{\prime})=\\{\theta_{1:n}:\|D\theta_{1:n}\|_{2}\leq
C_{n}^{\prime}\\}.$ (73)

The minimax cumulative error of nonparametric estimation in the discrete
Sobolev class is $\theta_{1:n}(n^{2/3}[C^{\prime}_{n}]^{2/3}\sigma^{4/3})$
(see e.g., Sadhanala et al., 2016, Theorem 5 and 6).

Recall that the discrete Total Variation class that we considered in this
paper is defined as

$\displaystyle\mathcal{T}(C_{n})=\\{\theta_{1:n}:\|D\theta_{1:n}\|_{1}\leq
C_{n}\\}.$ (74)

By the norm inequalities, we know that T(C_n’) ⊂S(C_n’) ⊂T(C_n’n).

The following refinement of our main theorem establishes that Arrows also
achieves the minimax rate in discrete Sobolev classes.

######  Theorem 5.

Let the feedback be $y_{t}=\theta_{t}+Z_{t}$ where $Z_{t}$ is an independent,
$\sigma$-subgaussian random variable. Let
$\theta_{1:n}\in\mathcal{S}(C_{n}^{\prime})$. If
$\beta=24+\frac{8\log(8/\delta)}{\log(n)}$, then with probability at least
$1-\delta$, Arrows achieves a dynamic regret of
$\tilde{O}(n^{2/3}[C_{n}^{\prime}]^{2/3}\sigma^{4/3}+U^{2}+[C_{n}^{^{\prime}}]^{2}+\sigma^{2})$
where $\tilde{O}$ hides a logarithmic factor in $n$ and $1/\delta$.

###### Proof.

Let’s minimally expand the Sobolev ball to a TV ball of radius
$C_{n}=\sqrt{n}C_{n}^{\prime}$. This chosen radius of the TV ball is in
accordance with the canonical scaling introduced in (Sadhanala et al., 2016).
This activates the following embedding:

$\displaystyle\mathcal{S}_{1}(C_{n}^{\prime})\subseteq TV(C_{n}).$ (75)

We can rewrite (67) as

$\displaystyle\begin{split}T\leq{}&8n^{1/3}\|D\theta_{1:n}\|_{1}^{2/3}\sigma^{4/3}(2+\log(n))\log(n)\\\
&+4\sigma^{2}\log(4n^{3}/\delta)(2+\log(n))\\\
&+U^{2}+2\|D\theta_{1:n}\|_{2}^{2}+12\sigma^{2}\log n\\\
&\qquad+24(\log(n))^{2}n^{1/3}\|D\theta_{1:n}\|_{1}^{2/3}\sigma^{4/3}+2\gamma\sigma^{4/3}n^{1/3}\|D\theta_{1:n}\|_{1}^{2/3}.\end{split}$
(76)

The above representation reveals the optimality of our policy over Sobolev
class $S_{1}(C_{n}^{\prime})$. Enlarging the Sobolev class to the TV class
that contains it does not change the minimax rate in the smoothing setting.
See, e.g., Theorem 5 and 6 of (Sadhanala et al., 2016) and take $d=1$, and
$C^{\prime}_{n}=n^{-1/2}C_{n}$. By using $\|x\|_{1}\leq n^{1/2}\|x\|_{2}$ for
$x\in\mathbb{R}^{n}$,

$\displaystyle\frac{\|D\theta_{1:n}\|_{1}}{n^{1/2}}\leq\|D\theta_{1:n}\|_{2}\leq
C^{\prime}_{n}=\frac{C_{n}}{n^{1/2}}.$ (77)

Plugging this bound on $\|D\theta_{1:n}\|_{1}$ in (76) recovers the minimax
regret for the Sobolev class of radius $C^{\prime}_{n}$. The additional term
of $\|D\theta_{1:n}\|_{2}^{2}$ — similar to as shown in in appendix I — is
unavoidable in the online setting for predicting discrete Sobolev sequences.

∎

######  Remark 4.

Note that $\mathcal{T}(C_{n}^{\prime})\subset\mathcal{S}(C_{n}^{\prime})$,
therefore our lower bound from Proposition 2 still applies, which suggests
that the additional $[C_{n}^{^{\prime}}]^{2}+\sigma^{2}$ is required and that
Arrows is an optimal forecaster for sequences in Sobolev classes as well.

##  Appendix G Fast Computation

We describe the proof of $O(n\log n)$ runtime guarantee below.

We use an inductive argument. Without loss of generality let the start of
current bin be at time 1. Suppose we know the wavelet transform of points upto
time $t$. Let the next highest power of 2 for both $t$ and $t+1$ be $p$. We
identify this value as a pivot for time $t$ and $t+1$. Zero padding is done to
hit this pivot. We can view the $pad_{0}$ operation at time $t+1$ as the
difference between the padded original data and and a step signal. This step
signal assume the value $\bar{y}_{1:t+1}$ in time $[1,t+1]$ and 0 in
$[t+2,p]$. For computing wavelet transform of the step, we need to update only
$O(\log(p))$ coefficients. Inputs to the Haar transform of the padded data at
times $t$ and $t+1$ differs by just one co-ordinate. Hence coefficients of
only $\log(p)$ wavelets need to be changed. Each such change can be performed
in $O(1)$ time in an incremental fashion.

Now let’s consider the case when the pivot for time $t+1$ is $2t$. Suppose we
know the Haar wavelet coefficients upto time $t$. In this case, we need to
compute the coefficients of $\log(t)$ newly introduced wavelets that span the
interval $[t,2t]$ since the zero padding will force most of the new wavelet
coefficients to be zero. The computation of each of those new coefficients can
be done in $O(1)$ due to sparsity of signal in interval $[t,2t]$. We also need
to change the first two wavelet coefficients which can be done again in in
$O(1)$ time. In all these cases, we only need to do soft-thresholding to the
newly updated coefficients. At the base case, when the pivot is just 2, then
the computation can be in $O(1)$ time. Thus within a pivot $p$, the number of
computations required is $O(p\log(p))$ which translates to
$O(k^{(m)}\log(k^{(m)}))$ computations within the $m^{th}$ bin. Summing across
all the bins yields a runtime complexity of $O(n\log(n))$.

##  Appendix H Regret of AOMD

In this section we prove that for any predictable sequence
$\\{M_{t}\\}_{t=1}^{n}$, the AOMD algorithm has a dynamic regret of
$\tilde{O}(\sqrt{n})$ when applied to our problem. As discussed in Section 2,
consider loss functions $f_{t}(x)=(x-y_{t})^{2}$ and comparator sequence
$\\{u_{t}\\}_{t=1}^{n}$. First let’s consider a deterministic noise setting
(Donoho, 1995):

$y_{t}=\theta_{t}+\delta\>\sigma\sqrt{20\log(n)},$ (78)

where $|\delta|\leq 1$ is chosen by a clever adversary. Let’s proceed to get a
bound on the quantity $D_{n}$. The gradient of our loss function is
$2(x-y_{t})$. So after observing the values of $x_{t}$ and $M_{t}$, an
adversary can pick a suitable $\delta$ such that each term of $D_{n}$

$D_{n}=\sum_{t=1}^{n}\|\nabla f_{t}(x_{t})-M_{t}\|_{*}^{2}.$ (79)

can be made $O(1)$. This gives an $O(n)$ bound for $D_{n}$.

We can show that $V_{n}$ is $O(n)$ if we assume that $\mathcal{X}$ is compact
and all of the $y_{t}$ is bounded. Boundedness of $y_{t}$ follows from the
assumptions (A3) and (A4). By appealing to assumption (A3) we see that

$C_{n}(u_{1},u_{2},...,u_{n})=\sum_{t=1}^{n}\|u_{t}-u_{t-1}\|.$ (80)

$C_{n}(\theta_{1},...,\theta_{n})$ is $O(1)$. Plugging this into the regret
bound specified in Jadbabaie et al. (2015) bounds the dynamic regret in our
setting as $\tilde{O}(\sqrt{n})$.

We now relate this deterministic noise setting to the guassian setting where
the observations are produced according to $y_{t}=\theta_{t}+Z_{t}$, where
$Z_{t}$ is a zero mean sub gaussian with parameter $\sigma^{2}$. As described
in proof of theorem 4, $P(\sup_{i}|Z_{i}|\geq\sigma\sqrt{20\log(n)})\leq
2n^{-9}$. Hence by conditioning on the event that
$\sup_{i}|Z_{i}|\leq\sigma\sqrt{20\log(n)}$, the regret bound of the
deterministic noise setting applies to gaussian setting with high probability.

##  Appendix I Lower bound proof

###### Proof of Proposition 2.

First, a lower bound of $\Omega(n^{1/3}C_{n}^{2/3}\sigma^{4/3})$ is given by
(Donoho et al., 1998) for the smoothing estimator $x_{1:n}$ that has more
information than we do. The argument uses the fact that the TV-ball is
sandwiched between two Besov-bodies with identical minimax rate. To the best
of our knowledge, the dependence on $C_{n}$ and $\sigma$ is first made
explicit in, e.g., (Birge and Massart, 2001).

By the fact that “the max is larger than the mean”, we have that for any prior
distribution $\mathcal{P}$,

$\displaystyle\sup_{\theta_{1:n}\in\mathrm{TV}(C_{n})}\mathbb{E}\left[\sum_{t=1}^{n}(x_{t}-\theta_{t})^{2}\right]\geq\mathbb{E}_{\theta_{1:n}\sim\mathcal{P}}\left[\mathbb{E}[\sum_{t=1}^{n}(x_{t}-\theta_{t})^{2}|\theta_{1:n}]\right].$

Take $\mathcal{P}$ such that

  1. 1.

$\theta_{1}=U$ with probability $0.5$ and $-U$ otherwise.

  2. 2.

$\theta_{2}=\theta_{1}+C_{n}$ with probability $0.5$ and $\theta_{1}-C_{n}$
otherwise.

  3. 3.

$\theta_{t}=\theta_{2}$ for $t=3,4,...,n$.

Note that $x_{1}$ does not observe anything yet, therefore $x_{1}=0$ is the
Bayes optimal decision rule. This gives a trivial lower bound of
$\mathbb{E}\left[(x_{1}-\theta_{1})^{2}\right]\geq U^{2}$. Now, let’s reveal
$\theta_{1}$ to $x_{2}$ an additional information, then by the same argument,
we have that $\mathbb{E}\left[(x_{2}-\theta_{2})^{2}\right]\geq C_{n}^{2}$.

Consider an alternative $\mathcal{P}$ when $\theta_{1}=...=\theta_{n}=\theta$.
Let the noise be iid Gaussian with variance $\sigma^{2}$. In this case the
problem reduces to a naive statistical estimation problem with
$\theta\in[-U,U]$. For each $t$ which observes $t-1$ iid samples from
$\mathcal{N}(\theta,\sigma^{2})$, then by Bickel et al. (1981), the minimax
risk for this problem is inf_^θsup_θ∈[-U,U] E(^θ-θ)^2 = σ2t - π2σ4tU2 \+
o(σ4tU2). Summing over $t=2,3,...,n$, and apply the upper/lower bounds of the
harmonic series, we have a lower bound of E[∑_t=1^n (x_t-θ_t)^2 ]≥max{0, σ^2
log(n+1) - π2σ4U2 (1+log(n)) (1+ o(1))}. Take the condition that
$U>2\pi\sigma$ and $n>3$, the above expression can be further lower bounded by
$0.5\sigma^{2}\log(n)$. Note that this bound applies even if $C_{n}=0$.

Finally, we can similarly apply the same argument to the case when
$\theta_{1}=0$ and $\theta_{2}=...=\theta_{n}=\theta$ and where the constraint
is that $-C_{n}\leq\theta\leq C_{n}$. This gives us a lower bound of E[∑_t=2^n
(x_t-θ_t)^2 ]≥max{0, σ^2 log(n) - π2σ4Cn2 (1+log(n-1)) (1+ o(1))}. If
$C_{n}>2\pi\sigma$ and $n>3$, we can again bound it below by
$0.5\sigma^{2}\log(n)$. In other word, we get the $\sigma^{2}\log(n)$ lower
bound provided that either $C_{n}$ or $U$ is greater than $2\pi\sigma$.

The proof is complete by taking the average of lower bounds above. We can take
$c=1/6$. ∎

###  I.1 Lower bound with extra boundedness constraint on ground truth

Suppose we assume $|\theta_{i}|\leq B,i=1,\ldots,n$. Then we can adapt the
proof presented above by considering a prior $\mathcal{P}$ such that
$\theta_{i}=\epsilon_{i}B,i=1,\ldots,1+\lfloor C_{n}/2B\rfloor$.
$\theta_{i}=\theta_{1+\lfloor C_{n}/2B\rfloor},\forall i>1+\lfloor
C_{n}/2B\rfloor$. Here $\epsilon_{i}$ are independent random variables
assuming value $+1$ with probability 0.5 and $-1$ with probability 0.5. Assume
that we reveal to learner the probability law of observations $\theta_{i}$.
Under this setting we can see that
$\mathbb{E}\left[\sum_{t=1}^{n}(x_{t}-\theta_{t})^{2}\right]\geq
B^{2}+BC_{n}/2$.

###  I.2 Connections to other lower bounds in literature

(Besbes et al., 2015) derived a lower bound of $O(n^{1/2}V_{n}^{1/2})$ by
packing a sequence of quadratic loss functions. Note that this is larger than
the upper bound that we attain with quadratic losses. Though this observation
seems confusing, a careful study reveals that there is no contradiction. For
constructing the lowerbound, (Besbes et al., 2015) used a variational budget
$V_{n}$ as , $V_{n}=\sum_{t=2}^{n}\sup_{x\in
conv(\theta_{1},...\theta_{n})}|f_{t}(x)-f_{t-1}(x)|=\sum_{t=2}^{n}\sup_{x\in[\theta_{min},\theta_{max}]}|(x-\theta_{t})^{2}-(x-\theta_{t-1})^{2}|$,
where $conv(.)$ denotes the convex hull of a sequence of points. This is
different from the variational budget they use in section 2 of their paper and
is also different from $C_{n}$ that we use for the TV class. When applied to
our setting this $V_{n}$ is no longer proportional to our $C_{n}$, instead, it
is proportional to $(\theta_{max}-\theta_{min})C_{n}$.

The packing set constructed through the functions defined in equation (A-12)
of (Besbes et al., 2015) obeys
$(\theta_{max}-\theta_{min})=\frac{1}{2}V_{n}^{1/4}n^{-1/4}$. So we have
$C_{n}=\frac{V_{n}}{V_{n}^{1/4}n^{-1/4}}=V_{n}^{3/4}n^{1/4}$, where we have
subsumed proportionality constants. Thus we see that
$V_{n}=\frac{C_{n}^{4/3}}{n^{1/3}}$. Putting this into their lowerbound
recovers exactly our $n^{1/3}C^{2/3}$ bound.

The additional $C_{n}^{2}$ term that appears in our upper bound is required
for any methods that do online forecasting of sequences in the TV class. The
reason why OGD appears to not require $C_{n}^{2}$ according to (Besbes et al.,
2015) is because they require the $\theta_{t}$ to be bounded for all $t$,
while we only require $\theta_{1}$ to be bounded by $U$ (see Theorem 2).

The lowerbound discussed in (Yang et al., 2016) considers a more general
setting of smooth non-strongly convex sequence of loss functions. Such a
lowerbound will not apply in our more restrictive setting.

##  Appendix J Optimality of linear forecasters in Discrete Sobolev class

In this section we first establish that just like Arrows, linear strategies
such as OGD and MA are also optimal forecasters for sequences in Discrete
Sobolev class. Then we substantiate it using experiments.

######  Theorem 6.

Let the feedback be $y_{t}=\theta_{t}+Z_{t}$ where $Z_{t}$ is an independent,
$\sigma$-subgaussian random variable. Let
$\theta_{1:n}\in\mathcal{S}(C_{n}^{\prime})$. Restarting OGD with batch size
of $\frac{\sigma^{2/3}(n\log n)^{1/3}}{[C_{n}^{\prime}]^{2/3}}$ achieves an
expected dynamic regret of
$\tilde{O}(U^{2}+[C_{n}^{\prime}]^{2}+n^{2/3}[C_{n}^{\prime}]^{2/3}\sigma^{4/3})$.

###### Proof.

We stick to the same notations as in Appendix C. Let’s start the analysis from
(5). Let $t^{\prime}=t-t_{h}^{(i)}$.

$\displaystyle(\theta_{t}-\bar{\theta}_{t_{h}^{(i)}:t-1})^{2}$
$\displaystyle\leq\frac{\left(\sum_{i=t_{h}^{(i)}}^{t-1}(\theta_{t}-\theta_{i})\right)^{2}}{[t^{\prime}]^{2}},$
(81)
$\displaystyle\leq\frac{t^{\prime}}{[t^{\prime}]^{2}}\sum_{i=t_{h}^{(i)}}^{t-1}(\theta_{t}-\theta_{i})^{2},$
(82) $\displaystyle\raisebox{-3.69899pt}{~{}\shortstack{$<$ \\\ [-0.07cm]
$\sim$}}~{}L[C^{\prime}_{i}]^{2}.$ (83)

Hence summing across all points yields,

$\displaystyle R_{i}$ $\displaystyle\raisebox{-3.69899pt}{~{}\shortstack{$<$
\\\ [-0.07cm] $\sim$}}~{}L^{2}[C^{\prime}_{i}]^{2}+\sigma^{2}\log L.$ (84)

So the total expected regret becomes,

$\displaystyle\sum_{i=1}^{\lceil n/L\rceil}R_{i}$
$\displaystyle\raisebox{-3.69899pt}{~{}\shortstack{$<$ \\\ [-0.07cm]
$\sim$}}~{}L^{2}[C^{\prime}_{n}]^{2}+\frac{n}{L}\sigma^{2}\log L.$ (85)

By choosing $L=\frac{\sigma^{2/3}(n\log n)^{1/3}}{[C_{n}^{\prime}]^{2/3}}$ we
get the theorem. The additive term $[C_{n}^{\prime}]^{2}$ arises similarly as
in proof of Theorem 2 ∎

The optimality of Moving Averages can be proved similarly.

######  Remark 5.

Thus from Theorems 1, 2, 2, 6 we see that Arrows is minimax over both the
classes $TV(C_{n})$ and $\mathcal{S}(C_{n}/\sqrt{n})$ while linear forecasters
such as OGD and MA require different tuning parameters to perform optimally in
each class.

Next, we give numerical experiments substantiating the claims. Experimental
results:

Figure 6: Regret plot for policies calibrated according to Sobolev radius for
a Doppler function

Here we consider a doppler function
$f(t)=\sin\left(\frac{2\pi(1+\epsilon)}{t/n+0.01}\right)$ with $n$ being the
time horizon. For this function
$C^{\prime}_{n}=\|D\theta\|_{2}=O(C_{n}/\sqrt{n})$ when $n$ is sufficiently
large and $\|D\theta\|_{2}=O(C_{n})$ for small $n$ for a TV bound
$C_{n}=O(1)$. Thus for sufficiently large $n$, this sequence belong to a small
Sobolev ball with radius $O(1/\sqrt{n})$ while the TV class that encloses that
Sobolev ball as per Theorem 5 has radius $O(1)$.

We observe noisy data $y_{i}=f(i/n)+z_{i}$, $i=1,...,n$ and $z_{i}$ are iid
normal variables with $\sigma=1$.Figure 6 plots the regret averaged across 5
runs in a log log scale. The necessary input calibration was made as per
Remark 4 while running Arrows. We can see that in this case all the algorithms
perform in an optimal manner.

Specifically we identify two regimes one for small $n$ and other for larger
$n$. When $n$ is large, we obtain the minimax regret rate $\tilde{O}(n^{1/3})$
due to small $C^{\prime}_{n}$ which can be considered as $O(1/\sqrt{n})$.
Numerically for $n>10^{5}$, $C^{\prime}_{n}$ is less than 0.1% of $C_{n}$. For
smaller values of $n$ where $C^{\prime}_{n}$ can be not too small, we attain a
regret in accordance with the $\tilde{O}(n^{2/3})$ minimax rate. Numerically
when $n<10^{4}$, $C^{\prime}_{n}$ is atleast 8.5% of $C_{n}$ which can be
considered as $O(C_{n})=O(1)$.