JMLR: Workshop and Conference Proceedings 1:1–20, 2018

workshop title

Aggregating Strategies for Long-term Forecasting
Alexander Korotin

a.korotin@skoltech.ru

Skolkovo Institute of Science and Technology,
Nobel street, 3, Moscow, Moskovskaya oblast’, Russia

arXiv:1803.06727v1 [cs.LG] 18 Mar 2018

Vladimir V’yugin∗

vyugin@iitp.ru

Institute for Information Transmission Problems,
Bolshoy Karetny per. 19, build.1, Moscow, Russia

Evgeny Burnaev†

e.burnaev@skoltech.ru

Skolkovo Institute of Science and Technology,
Nobel street, 3, Moscow, Moskovskaya oblast’, Russia

Editor: Editor’s name

Abstract
The article is devoted to investigating the application of aggregating algorithms to the
problem of the long-term forecasting. We examine the classic aggregating algorithms based
on the exponential reweighing. For the general Vovk’s aggregating algorithm we provide its
generalization for the long-term forecasting. For the special basic case of Vovk’s algorithm
we provide its two modifications for the long-term forecasting. The first one is theoretically
close to an optimal algorithm and is based on replication of independent copies. It provides
the time-independent regret bound with respect to√
the best expert in the pool. The second
one is not optimal but is more practical and has O( T ) regret bound, where T is the length
of the game.
Keywords: aggregating algorithm, long-term forecasting, prediction with experts’ advice,
delayed feedback.

1. Introduction
We consider the online game of prediction with experts’ advice. A master (aggregating)
algorithm at every step t = 1, . . . , T of the game has to combine aggregated prediction from
predictions of a finite pool of N experts (see e.g. Littlestone and Warmuth (1994), Freund
and Schapire (1997), Vovk (1990), Vovk (1998), Cesa-Bianchi and Lugosi (2006), Adamskiy
et al. (2016) among others). We investigate the adversarial case, that is, no assumptions
are made about the nature of the data (stochastic, deterministic, etc.).
In the classical online scenario, all predictions at step t are made for the next step t + 1.
The true outcome is revealed immediately at the beginning of the next step of the game
and the algorithm suffers loss using a loss function.
∗
†

Vladimir V’yugin was supported by the Russian Science Foundation grant (project 14-50-00150).
Evgeny Burnaev was supported by the Ministry of Education and Science of Russian Federation, grant
No. 14.606.21.0004, grant code: RFMEFI60617X0004.

c 2018 A. Korotin, V. V’yugin & E. Burnaev.

Korotin V’yugin Burnaev

In contrast to the classical scenario, we consider the long-term forecasting. At each step
t of the game, the predictions are made for some pre-determined point t + D ahead (where
D ≥ 1 is some fixed known horizon), and the true outcome is revealed only at step t + D.
The performance of the aggregating algorithm is measured by the regret over the entire
game. The regret RT is the difference between the cumulative loss of the online aggregating
algorithm and the loss of some offline comparator. A typical offline comparator is the best
fixed expert in the pool or the best fixed convex linear combination of experts. The goal of
an aggregating algorithm is to minimize the regret, that is, RT → min.
It turns out that there exists a wide range of aggregating algorithms for the classic
scenario (D = 1). The majority of them are based on the exponential reweighing methods
(see Littlestone and Warmuth (1994), Freund and Schapire (1997), Vovk (1990), Vovk
(1998), Cesa-Bianchi and Lugosi (2006), Adamskiy et al. (2016), etc.). At the same time,
several algorithms come from the general theory of online convex optimization by Hazan
(2016). Such algorithms are based on online gradient descent methods.
There is no right answer to the question which category of algorithms is better in
practice. Algorithms from both groups theoretically have good performance. Regret (with
respect to some offline comparator) is usually bounded by a sublinear function of T :
1. RT ≤ O(T ) for Fixed Share with constant share by Herbster and Warmuth (1998);
√
2. RT ≤ O( T ) for Regularized Follow The Leader according to Hazan (2016);
3. RT ≤ O(ln T ) for Fixed Share with decreasing share by Adamskiy et al. (2016);
4. RT ≤ O(1) in aggregating algorithm by Vovk (1998);
and so on. In fact, the applicability of every particular algorithm and the regret bound
depends on the properties of the loss function (convexity, Lipschitz, exponential concavity,
mixability, etc.).
When it comes to long-term forecasting, many of these algorithms do not have theoretical
guaranties of performance or even do not have a version for the long-term forecasting. Longterm forecasting implies delayed feedback. Thus, the problem of modifying the algorithms
for the long-term forecasting can be partially solved by the general results of the theory of
forecasting with the delayed feedback.
The main idea in the field of the forecasting with the delayed feedback belongs to
Weinberger and Ordentlich (2002). They studied the simple case of binary sequences
prediction under fixed known delay feedback D. According to their results, an optimal1
predictor p∗D (xt+D |xt , . . . , x1 ) for the delay D can be obtained from an optimal predictor
p∗1 (xt+1 |xt , . . . , x1 ) for the delay 1. The method implies running D independent copies of
predictor p∗1 on D disjoint time grids GRd = {t | t ≡ d (mod D)} for 1≤ d ≤ D. Thus,
p∗D (xt+D |xt , . . . , x1 ) = p∗1 (xt+D |xt , xt−D , xt−2D , . . . )
for all t. We illustrate the optimal partition of the timeline in Figure 1.
It turns out, their result also works for the general problem of forecasting under the
fixed known delay feedback, in particular, for the prediction with expert advice (we prove
1. An optimal predictor is any predictor with the regret which is less or equal to the minimax regret. There
may exist more than one optimal predictor.

2

Aggregating Strategies for Long-term Forecasting

Figure 1: The optimal approach to the problem of forecasting with the fixed known delay
D. The timeline is partitioned into D disjoint grids GRd . Games on different
grids are considered separately. Each game has fixed known delay 1 (not D).

this in Appendix A). Thus, it is easy to apply any 1-step-ahead forecasting aggregating
algorithm to the problem of long-term forecasting by running its D independent copies on
D disjoint grids GRd (for d = 1, . . . , D). We call algorithms obtained by this method as
replicated algorithms.
Nevertheless, one may say that such a theoretically optimal approach is practically far
1
from optimal because it uses only D
of observed data at every step of the game. Moreover,
separate learning processes on grids GRd (for d = 1, . . . , D) do not even interact.
Gradient-descent-based aggregating algorithms have several non-replicated adaptations
for the long-term forecasting. The most obvious adaptation is the delayed gradient descent
by Quanrud and Khashabi (2015). Also, the problem of prediction with experts’ advice can
be considered as a special case of online convex
optimization with memory by Anava et al.
√
(2015). Both approaches provide RT ≤ O( T ) classical regret bound.2 Thus, the practical
and theoretical problem of modifying the gradient descent based aggregating algorithms for
long-term forecasting can be considered as solved.
In this work, we investigate the problem of modifying aggregating algorithms based on
exponential reweighing for the long-term forecasting. We consider the general aggregating
algorithm by Vovk (1999) for the 1-step-ahead forecasting and provide its reasonable nonreplicated generalization for the D-th-step-ahead forecasting. These algorithms are denoted
by G1 and GD respectively. We obtain a general expression for the regret bound of GD .
2. We do not include the value of the forecasting horizon D in regret bounds because in this article we
are interested only in the regret asymptotic behavior w.r.t. T . In all algorithms that we discuss the
asymptotic behavior w.r.t. D is sublinear or linear.

3

Korotin V’yugin Burnaev

As an important special case, we consider the classical exponentially reweighing algorithm
V1 by Vovk (1998), that is a case of G1 , designed to compete with the best expert in the
pool. The algorithm V1 can be considered close to an optimal one because it provides
constant T -independent regret bound. We provide its replicated modification VD for the
long-term forecasting. We also propose a non-replicated modification VDF C for the long-term
forecasting of V1 (motivated by reasonable
practical approach).3 Our main result here is
√
F
C
that the regret bound for VD is O( T ).
All the algorithms that we develop and investigate require the loss function to be exponentially concave. This is a common assumption (see e.g. Kivinen and Warmuth (1999))
for the algorithms based on the exponential reweighing.4
The main contributions of this article are the following:
1. Developing the general non-replicated exponentially reweighing aggregating algorithm
GD for the problem of long-term prediction with experts’ advice and estimating its
regret.
2. Developing the non-replicated adaptation VDF C of the
√ powerful aggregating algorithm
V1 by Vovk (1998). The obtained algorithm has O( T ) regret bound with respect to
the best expert in the pool.
In our previous work (see Korotin et al. (2017)) we also studied the application of
algorithm V1 to the long-term forecasting. We applied the method of Mixing Past Posteriors
by Bousquet and Warmuth (2003) to connect the independent learning processes on separate
grids GRd (for d = 1, . . . , D). We obtained the algorithm VDGC that partially connects the
learning processes on these grids.5
In contrast to our previous work, in this article we consider the general probabilistic
framework for the long-term forecasting (algorithms G1 and GD ). We obtain the algorithm
VDF C that fully connects the learning processes on different grids, see details in Subsection
4.3.
The article is structured as follows.
In Section 2 we set up the problem of long-term prediction with experts’ advice and
state the protocol of the online game.
In Section 3 we discuss the aggregating algorithms for the 1-step-ahead forecasting. In
Subsection 3.1 we describe the general model G1 by Vovk (1999) and consider its special
case V1 in Subsection 3.2.
In Section 4 we discuss aggregating algorithms for the D-th-step-ahead forecasting:
we develop general model GD in Subsection 4.1. Then we discuss its two special cases:
algorithm VD in Subsection 4.2 that is a replicated
√ version of V1 and our non-replicated
version VDF S in Subsection 4.3. We prove the O( T ) regret bound for VDF C .
In Appendix A we generalize the result by Weinberger and Ordentlich (2002) to the case
of long-term prediction with experts’ advice and prove that the approach with replicating
1-step-ahead predictors for D-th-step-ahead forecasting is optimal.
3. FC — full connection.
4. Usually, even more general assumption is used that the loss function is mixable.
5. GC — grid connection.

4

Aggregating Strategies for Long-term Forecasting

2. Preliminaries
We use bold font to denote vectors (e.g. w ∈ RM for some integer M ). In most cases,
superscript refers to index/coordinate of an element in the vector (e.g. (w1 , . . . , wN ) = w).
Subscript is always used to indicate time (e.g. lt , RT , ωτ , wtn , etc.).
For any integer M we denote the probability simplex of dimension M by
∆M = {p such that (p ∈ RM
+ ) ∧ (kpk1 = 1) ∧ (p > 0)}.
We use the notation e ∈ RM
+ to denote the unit vector (1, 1, . . . , 1). The dimension M
e
of the vector is always clear from the context. Note that M
∈ ∆M .
The words prediction and forecasting are absolute synonyms in this paper.
2.1. A Game of Long-Term Forecasting with Experts’ Advice
We consider the online game of D-th-step-ahead forecasting of time series ωt ∈ Ω by
aggregating a finite pool of N forecasting experts. We use N = {1, . . . , N } to denote the
pool and n ∈ N as an index of an expert.
n
At each integer step t = 1, 2, . . . , T − D experts n ∈ N present their forecasts ξt+D
∈Ξ
T
of time series {ωτ }τ =1 for the time moment t+D. The master (aggregating) algorithm combines these forecasts into a single (aggregated) forecast γt+D ∈ Γ ⊂ Ξ for the time moment
t + D.
After the corresponding outcome ωt+D is revealed (on the step t + D of the game), both
experts and algorithm suffer losses using a loss function λ : Ω × Ξ → R+ . We denote the
n ) and the loss of the aggregating
n
= λ(ωt+D , ξt+D
loss of expert n ∈ N on step t + D by lt+D
algorithm by ht+D = λ(ωt+D , γt+D ). We fix the protocol of the game below.
Protocol (D-th-step-ahead forecasting with Experts’ advice)
Get the experts n ∈ N predictions ξtn ∈ Ξ for steps t = 1, . . . , D.
Compute the aggregated predictions γt ∈ Γ for steps t = 1, . . . , D.
FOR t = 1, . . . , T
1. Observe the true outcome ωt ∈ Ω.
2. Suffer losses from past predictions
(a) Compute the losses ltn = λ(ωt , ξtn ) for all n ∈ N of the experts’ forecasts ξtn made at the
step t − D.
(b) Compute the loss ht = λ(ωt , γt ) of the aggregating algorithm’s forecast γt made at the
step t − D.
3. Make the forecast for the next step (if t ≤ T − 1)
n
(a) Get the experts n ∈ N predictions ξt+D
∈ Ξ for the step t + D.

(b) Compute the aggregated prediction γt+D ∈ Γ of the algorithm.
ENDFOR

We assume that the forecasts ξtn of all experts n ∈ N for first D time moments t =
1, . . . , D are given before the game.
5

Korotin V’yugin Burnaev

P
P
The variables LnT = Tt=1 ltn (for all n ∈ N ) and HT = Tt=1 ht correspond to the cumulative losses of expert n and the aggregating algorithm over the entire game respectively. We
1
N ).
also denote the vector of experts’ forecasts for the step t + D by ξt+D = (ξt+D
, . . . , ξt+D
In the general protocol sets Ξ and Γ ⊂ Ξ may not be equal. For example, the problem
of combining N soft classifiers into a hard one has Ξ = [0, 1] and Γ = {0, 1} ( Ξ. In this
article we assume that the sets of possible experts’ and algorithm’s forecasts are equal, that
is Ξ = Γ. Moreover, we assume that Ξ = Γ is a convex set. We will not use the notation of
Ξ anymore.
The performance of the algorithm is measured by the (cumulative) regret. The cumulative regret is the difference between the cumulative loss of the aggregating algorithm and
the cumulative loss of some off-line comparator. A typical approach is to compete with the
best expert in the pool. The cumulative regret with respect to the best expert is
RT = HT − min LnT .
n∈N

(1)

The goal of the aggregating algorithm is to minimize the regret, that is, RT → min.
In order to theoretically guarantee algorithm’s performance, some upper bound is usually
proved for the cumulative regret RT ≤ f (T ).
In the base setting (1), sub-linear upper bound f (T ) for the regret leads to asymptotic
performance of the algorithm equal to the performance of the best expert. More precisely,
we have limT →∞ RTT = 0.
2.2. Exponentially concave loss functions
We investigate learning with exponentially concave loss functions. Loss function λ : Ω × Γ → R+
is called η-exponentially concave (for some η > 0) if for all ω ∈ Ω and all probability distributions π on set Γ the following holds true:
Z
−ηλ(ω,γπ )
e
≥
e−ηλ(ω,γ) π(dγ),
(2)
γ∈Γ

where

Z
γπ =

γπ(dγ) = Eπ γ.

(3)

γ∈Γ

In (2) variable γπ is called aggregated prediction. Since Γ is convex, we have γπ ∈ Γ.
If a loss function is η-exponentially concave, it is also η 0 -exponentially concave for all
0
η ∈ (0, η]. This fact immediately follows from the general properties of exponentially
concave functions. For more details see the book by Hazan (2016).
Note that the basic square loss and the log loss functions are both exponentially concave.
This fact is proved by Kivinen and Warmuth (1999).

3. Aggregating Algorithm for 1-Step-Ahead Forecasting
In this section we discuss basic aggregating algorithms for 1-step-ahead forecasting based
on exponential reweighing. Our framework is built on the general aggregating algorithm
G1 by Vovk (1999), we discuss it in Subsection 3.1. The simplest and earliest version V1 by
Vovk (1998) of this algorithm is discussed in Subsection 3.2.
6

Aggregating Strategies for Long-term Forecasting

3.1. General Model
We investigate the adversarial case, that is, no assumptions (functional, stochastic, etc)
are made about the nature of data and experts. However, it turns out that in this case it
is convenient to develop algorithms using some probabilistic interpretations.
Recall that ξt = (ξt1 , . . . , ξtN ) is a vector of experts’ predictions of ωt . Loss function
λ : Ω × Γ → R+ is η-exponentially concave for some η > 0.
We assume that data is generated using some probabilistic model with hidden states.
The model is shown in Figure 2.

Figure 2: Probabilistic model of data generation process.
We suppose that there is some hidden sequence of experts nt ∈ N (for t = 1, 2, . . . , T )
that generates the experts predictions ξt . Particular, hidden expert nt at step t is called
active expert. The conditional probability to observe the vector ξt of experts’ predictions
at step t is
nt

e−ηλ(ωt ,ξt )
p(ξt |nt ) =
,
Zt
R
where Zt = ξ∈Γ e−ηλ(ωt ,ξ) dξ is the normalizing constant.6 We denote Ξt = (ξ1 , . . . , ξt ) and
Ωt = (ω1 , . . . , ωt ) for all t = 1, . . . , T .
For the first active expert n1 some known prior distribution is given p(n1 ) = p0 (n1 ).
The sequence (n1 , . . . , nT ) of active experts is generated step-by-step. For t ∈ {1, . . . , T −1}
each nt+1 is sampled from some known distribution p(nt+1 |Nt ), where Nt = (n1 , . . . , nt ).7
Thus, active expert nt+1 depends on the previous experts Nt .
The considered probabilistic model is:8
6. Constant Zt is nt -independent. In the article we do not need to compute the exact value of the normalizing constant Zt .
7. In case p(nt+1 |Nt ) = p(nt+1 |nt ), we obtain traditional Hidden Markov Process. The hidden state at
step t + 1 depends only on the previous hidden state at step t.
8. The correct way is to include the time series values ωt as the conditional parameter in the model
probabilistic distribution, that is, p(NT , ΞT |ΩT ). We omit the values ωt in probabilities p(·) in order
not to overburden the notation.

7

Korotin V’yugin Burnaev


p(NT , ΞT ) = p(NT ) · p(ΞT |NT ) = p0 (n1 )

T
Y

 Y

T
p(nt |Nt−1 ) ·
p(ξt |nt ) .

t=2

(4)

t=1

The similar equation holds true for t ≤ T :

p(Nt , Ξt ) = p(Nt ) · p(Ξt |Nt ) = p0 (n1 )

t
Y

 Y

t
p(nτ |Nτ −1 ) ·
p(ξτ |nτ ) .

τ =2

τ =1

The probability p(NT ) is that of hidden states (active experts).9
Suppose that the current time moment is t. We observe the experts’ predictions Ξt
made earlier, time series Ωt and predictions ξt+1 for the step t + 1. Since we observe Ωt
and Ξt , we are able to estimate the conditional distribution p(Nt |Ξt ) of hidden variables
Nt . This estimate allows us to compute the conditional distribution on the active expert
nt+1 at the moment t + 1. We denote for all nt+1 ∈ N
n

X

t+1
wt+1
= p(nt+1 |Ξt ) =

Nt

p(nt+1 |Nt )p(Nt |Ξt ).

(5)

∈N t

1 , . . . , w N ) to combine the aggregated prediction
We use the weight vector wt+1 = (wt+1
t+1
for the step t + 1:

X

γt+1 =

nt+1
p(nt+1 |Ξt )
ξt+1

= hwt+1 , ξt+1 i =

nt+1 ∈N

N
X

n
n
wt+1
ξt+1
.

n=1

The aggregating algorithm is shown below. We denote it by G1 = G1 (p), where p
indicates the probability distribution p(NT ) of active experts to which the algorithm is
applied.
Algorithm G1 (p) (Aggregating algorithm for distribution p of active experts)
Set initial prediction weights w1n1 = p0 (n1 ).
Get the experts n ∈ N predictions ξ1n ∈ Γ for the step t = 1.
Compute the aggregated prediction γ1 = hw1 , ξ1 i for the step t = 1.
FOR t = 1, . . . , T
1. Observe the true outcome ωt ∈ Ω.
2. Update the weights
(a) Calculate the prediction weights wt+1 = (wt1 , . . . , wtN ), where
n

wt t+1 = p(nt+1 |Ξt )
for all nt+1 ∈ N .
3. Make forecast for the next step (if t ≤ T − 1)
Q
9. The form p(NT ) = p0 (n1 ) tt=2 p(nt |Nt−1 ) is used only for convenience and association with online
scenario. It does not impose any restrictions on the type of probability distribution. In fact, p(NT ) may
be any distribution on N T of any form.

8

Aggregating Strategies for Long-term Forecasting

n
(a) Get the experts n ∈ N predictions ξt+1
∈ Γ for the step t + 1.

(b) Combine the aggregated prediction γt+1 = hwt+1 , ξt+1 i ∈ Γ of the algorithm.
ENDFOR

To estimate the performance of the obtained algorithm, we prove Theorem 1. Recall
that HT is the cumulative loss of the algorithm over the entire game.
Theorem 1 For the algorithm G1 applied to to the model (4) the following upper bound
for the cumulative loss over the entire game holds true:


 −ηLNT 
1
T
HT ≤ − ln Ep(NT ) e
.
η

(6)

Similar results were obtained by Vovk (1999). In this article we reformulate these results
in terms of our interpretable probabilistic framework. This is required for the completeness
of the exposition and theoretical analysis of algorithm GD (see Subsection 4.1).
Proof Define the mixloss at the step t:

1  X −ηλ(ωt ,ξtnt )
mt = − ln
· wtnt .
e
η

(7)

nt ∈N

Since λ is η-exponentially concave function, for the aggregated prediction γt = hwt , ξt i and
probability distribution wt we have
X
nt
e−ηλ(ωt ,γt ) ≥
e−ηλ(ωt ,ξt ) wtnt ,
nt ∈N

which is equal to e−ηht ≥ e−ηmt . We conclude that ht ≤ mt for all t ∈ {1, . . . , T }. Thus,
the similar inequality is true for the cumulative loss of the algorithm and the cumulative
mixloss:
HT =

T
X

ht ≤

t=1

T
X

m t = MT .

t=1

Now lets compute MT .
For all t

1  X −ηλ(ωt ,ξtnt )
mt = − ln
e
· p(nt |Ξt−1 ) =
η
nt ∈N

1  X
− ln
Zt · p(ξt |nt ) · p(nt |Ξt−1 ) =
η
nt ∈N

1
1  X
− ln Zt − ln
p(ξt |nt ) · p(nt |Ξt−1 ) =
η
η
nt ∈N

1
1
− ln Zt − ln p(ξt |Ξt−1 )
η
η
9

Korotin V’yugin Burnaev

We compute
T
X

T

T

1 Y
1 Y
ln
Zt − ln
p(ξt |Ξt−1 ) =
η
η
t=1
t=1
t=1


T
 −ηLNT 
1 Y
1
1
T
ln
Zt − ln p(ΞT ) = − ln Ep(NT ) e
η
η
η

HT ≤ MT =

mt =

(8)

t=1

and finish the proof.
In the current form it is difficult to understand the meaning of the theorem. However,
the main idea is partially shown in the following corollary.
Corollary 2 The regret of the algorithm G1 (p) with respect to the sequence NT∗ = {n∗1 , . . . , n∗T }
of experts has the following upper bound:
RT (NT∗ )

= HT −

T
X
t=1

1
n∗
lt t ≤ − ln p(NT∗ ).
η

(9)

Proof We simply bound (6):



T
∗
X
NT
 −ηLNT 
1
1
1
n∗
∗
−ηL
T
T
HT ≤ − ln Ep(NT ) e
≤ − ln p(NT ) · e
=
lt t − ln p(NT∗ ).
η
η
η
t=1

Applying algorithm G1 to different probability models p makes it possible to change the
upper regret bound with respect to concrete sequences NT .10 Choosing different p makes it
possible to obtain adaptive algorithms (e.g. Fixed Share by Herbster and Warmuth (1998),
Adamskiy et al. (2016), Vovk (1999)). Such algorithms provide low regret not only with
respect to the best constant sequence of experts, but also with some more complicated
sequences.
For example, suppose we are to obtain minimal possible regret bound with respect to
the sequences (N T )∗ ⊂ N T . In this case it is reasonable to set p(NT ) = |(N1T )∗ | for all
NT ∈ (N T )∗ and p(NT ) = 0 for all other NT .
Nevertheless, the most popular approach is to compete with the best (fixed) expert.
This approach is simple and, at the same time, serves as the basis for each research.
3.2. Case of Hidden Markov Process: Classical Vovk’s Algorithm
Consider the simplified dependence of active experts shown on Figure 3. For all t expert
nt+1 depends only on the previous expert nt , that is, p(nt+1 |NT ) = p(nt+1 |nt ).
10. In this article we do not raise the question of computational efficiency of algorithm G1 (p). In fact,
computational time and required memory can be pretty high for complicated distributions p, even O(N T ).
Nevertheless, all the special algorithms that we consider (V1 , VD , VDF C ) are computationally efficient.
They require ≤ O(N T ) computational time and ≤ O(N D) memory.

10

Aggregating Strategies for Long-term Forecasting

Figure 3: Hidden Markov Model model for data generation process.
The classic Vovk’s aggregating algorithm is obtained from G1 by applying it to the
simple distribution p. We put p(n1 ) = N1 (for all n1 ∈ N ) and p(nt |nt−1 ) = [nt = nt−1 ] (for
all t > 1 and nt , nt−1 ∈ N ). We denote the algorithm G1 for the described p by V1 .
According to Corollary 2, algorithm V1 has the following regret bound with respect to
the best constant expert NT∗ = (n∗ , . . . , n∗ ):
RT (NT∗ )

= HT −

T
X
t=1

1
ln N
∗
ltn ≤ − ln p(NT∗ ) =
.
η
η

(10)

At the same time, it is easy to recurrently compute the weights wt step by step, that
is, w1 → w2 → . . . . We get
nt

nt

e−ηLt
wtnt e−ηlt
nt+1
wt+1
= p(nt |Ξt ) = PN
=
.
PN
−ηLn
n e−ηltn
T
e
w
n=1
n=1 t
Thus, algorithm V1 is a powerful and computationally efficient tool to aggregate experts
in the game of the 1-step-ahead forecasting.

4. Aggregating Algorithm for Long-Term Forecasting
The Section is devoted to aggregating algorithms for the long-term forecasting. In
Subsection 4.1 we provide a natural long-term forecasting generalization GD of algorithm
G1 by Vovk (1999). We provide the general regret bound and discuss the difficulties that
prevent us from obtaining general bound in a simple form. In Subsection 4.2 we show how
the replicated version VD for the long-term forecasting of V1 fits into the general model,
FC
and prove its regret bound. In Subsection 4.3 we
√ describe non-replicated version VD for
the long-term forecasting of V1 and prove its O( T ) regret bound.
4.1. General Model
We describe the natural algorithm obtained by enhancing G1 for the problem of the
D-th-step-ahead forecasting below and denote it by GD . Note that weights wt in GD differ
for different D (for the same probability model p).
11

Korotin V’yugin Burnaev

Algorithm GD (p) (Aggregating algorithm for distribution p of active experts)
Set initial prediction weights wtnt = p(nt ) for all t = 1, . . . , D and nt ∈ N .
Get the predictions ξtn ∈ Γ of experts n ∈ N for steps t = 1, . . . , D.
Compute the aggregated predictions γt = hwt , ξt i for steps t = 1, . . . , D.
FOR t = 1, . . . , T
1. Observe the true outcome ωt ∈ Ω.
2. Update the weights
(a) Calculate the prediction weights wt+D = (wt1 , . . . , wtN ), where
n

wt t+D = p(nt+D |Ξt )
for all nt+D ∈ N .
3. Make forecast for the next step (if t ≤ T − 1)
n
∈ Γ of experts n ∈ N for the step t + D.
(a) Get the predictions ξt+D

(b) Combine the aggregated prediction γt+D = hwt+D , ξt+D i ∈ Γ of the algorithm.
ENDFOR

Despite the fact that algorithm GD (for D > 1) is the direct modification of G1 , it seems
hard to obtain the adequate general bound of the loss of the form (6). Indeed, let us try to
apply the ideas of Theorem 1 proof to algorithm GD .
Denote by mt the mixloss from (7). Recall that the weights wtnt here are equal to the
probabilities p(nt |Ξt−D ) but not p(nt |Ξt−1 ). Again, for η-exponentially concave function
we have ht ≤ mt . Similar to the proof of Theorem 1, we compute for all t
1
1
mt = − ln Zt − ln p(ξt |Ξt−D ),
η
η
where we assume Ξt−D = ∅ for t ≤ D. The cumulative mixloss is equal to
Ht ≤ Mt =

T
X
t=1

T

T

t=1

t=1

1 Y
1 Y
mt = ln
Zt − ln
p(ξt |Ξt−D ).
η
η

(11)

Unfortunately, for D > 1 in the general case this expression can not be simplified in the
same way as in Theorem 1 for G1 .
However, there exist some simple theoretical cases when this bound can be simplified.
For a fixed D, the obvious one is when
p(NT ) =

T
Y

bt ),
p(N

(12)

t=T −D+1

bt = (. . . , nt−2D , nt−D , nt ) for all t = 1, . . . , T . Note that (12) means that
where we use N
probability distributions on separate grids GRd (for d = 1, . . . , D) are independent. In this
case, the learning process separates into D disjoint one-step ahead forecasting games on
b t−D ) and (11) is simplified to
grids GRd . We have p(ξt |Ξt−D ) = p(ξt |Ξ
12

Aggregating Strategies for Long-term Forecasting

T

Ht ≤ Mt =

1 Y
1
ln
Zt − ln
η
η
t=1

1
ln
η

T
Y
t=1

1
Zt − ln
η

T
Y

T
Y

b t) =
p(Ξ

t=T −D+1



t=T −D+1


 −ηLNT 
1
b
T
,
p(Ξt ) = − ln Ep(NT ) e
η

b t = {ξt , ξt−D , ξt−2D , . . . } for all t.
where Ξ
In Appendix A we prove that the approach (12) may be considered as optimal when
the goal is to compete with the best expert. Nevertheless, there are no guaranties that this
approach is optimal in the general case.
4.2. Optimal Approach: Replicated Vovk’s Algorithm
Algorithm V1 can be considered as close to optimal (for the 1-step-ahead forecasting
and competing with the best expert in the pool) because of its low constant regret bound
RT ≤ lnηN . One can obtain the aggregating algorithm VD for the long-term forecasting
whose regret is close to optimal when competing with the best constant active expert.
The idea is to run D independent one-step-ahead forecasting algorithms V1 on D disjoint
subgrids GRd (for d ∈ {1, . . . , D}). This idea is motivated by Theorem 4 from Appendix
A.
To show how this method fits into the general model GD , we define p(ND ) ≡ ( N1 )D for
all ND ∈ N D . Next, for all t > D we set p(nt+1 |Nt ) = p(nt+1 |nt+1−D ) = [nt+1 = nt+1−D ],
that is, active expert nt+1 depends only on expert nt+1−D that was active D steps ago. The
described model is shown in Figure 4.

Figure 4: The probabilistic model for algorithm VD .
For simplicity, we assume that T is a multiple of D. Since VD runs D independent copies
of V1 , it is easy to estimate its regret with respect to the best expert:
RT (NT∗ )

= HT −

T
X
t=1

1
ln N
∗
ltn ≤ − ln p(NT∗ ) = D
.
η
η

13

Korotin V’yugin Burnaev

At the same time, the weights’ updating process is simple (it can be separated into
grids). We have
wtnt

nt

b nt

e−ηLt−D

= p(nt |Ξt−D ) = P
N

bn

−η Lt−D
n=1 e

nt
wt−D
e−ηlt−D

= PN

n
−ηlt−D
n
n=1 wt−D e

,

b nt = Pt lnt for all t. This formula allows efficient recurrent computation
where L
t
τ =1 t
· · · → wt−D → wt → wt+D → . . . .
4.3. Practical Approach: Non-Replicated Vovk’s Algorithm
Despite the fact that algorithm VD is theoretically close to optimal for competing with
the best expert, it has several practically obvious disadvantages. With the increase of
T
D the overall length of subgames decreases (∼ D
) and subgrids become more infrequent.
Moreover, to set the forecasting weight wt+D at step t we use only ≈ Dt previous observations
and forecasts.
One may wonder why not use all the observed losses to set the weight wt+D . We apply
the algorithm GD to the probability distribution p from Subsection 3.2 which is a case of
model from Figure 3. We denote the obtained algorithm by VDF C .
The weights are efficiently recomputed · · · → wt−1 → wt → wt+1 → . . . according to
the formula
nt

nt

wtnt

e−ηLt−D

= p(nt |Ξt−D ) = PN

−ηLn
t−D
n=1 e

nt −ηlt−D
wt−1
e

= PN

n
−ηlt−D
n
n=1 wt−1 e

.

Theorem 3 For the η λ -exponentially concave (for some η λ ) and L-Lipshitz for all ω w.r.t.
second argument γ ∈ Γ and k · kΓ loss function
λ : Ω × Γ → [0, H] ⊂ R+
with maxγ∈Γ kγkΓ ≤ B there exists T0 such that for all T ≥ T0 the following holds true:
there exists η λ > η ∗ > 0 such that algorithm VDF C = GD (p) with N experts and learning
rate η ∗ has regret bound
√
√
RT ≤ O( N ln N · T )
with respect to the best expert in the pool.
Proof We use the superscript (. . .)D to denote the variables obtained by algorithm GD (p)
(for example, weights wtD , predictions γtD , etc.). Our main idea is to prove that the weights
wtD are approximately equal to the weights wt1 obtained in the one-step-ahead forecasting
game G1 (p) with the same experts and same time series ωt . Thus, the forecasts γtD and γt1
1
have approximately the same losses hD
t and ht respectively.
We compare both algorithms with the same (yet unknown) learning rate η. Note that
1
D . For all t we have
wt+1
= wt+D
nt
)D ∼ (wtnt )D · e
(wtnt )1 = (wt+D−1

14

n

t
−ηL[t−D+1,t−1]

,

Aggregating Strategies for Long-term Forecasting

P
nt
t
= t−1
where Ln[t−D+1,t−1]
τ =t−D+1 lτ . We estimate the difference between the cumulative
losses HT1 and HTD of forecasts of aggregating algorithms G1 (p) = V1 and GD (p) = VDF C for
the given p from Subsection 3.2.

|HT1

−

HTD |

=|

T
X

h1t

−

t=1

L

T
X

kγt1 − γtD kΓ = L

t=1

T
X
t=1
T
X

hD
t |

≤

T
X

|h1t

−

hD
t |

=

t=1

T
X
t=1

khwt1 , ξt i − hwtD , ξt ikΓ = L

t=1

L

T X
N
X

|λ(ωt , γt1 ) − λ(ωt , γtD )| ≤
T
X

khwt1 − wtD , ξt ikΓ ≤

t=1

|(wtn )1 − (wtn )D | · kξtn kΓ ≤ BL

t=1 n=1

T X
N
X

|(wtn )1 − (wtn )D | ≤

t=1 n=1

BLT N · max |(wtn )1 − (wtn )D |
t,n

(13)

Our goal is to estimate the maximum. In fact, we are to estimate the maximum possible
single weight change over D − 1 steps in algorithm G1 (p) or GD (p).
W.l.o.g. we assume that the maximum is achieved at step t on the
1-st coordinate
−ηLn
[t−D+1,t−1] (so that
(n = 1). We denote x = wtD ∈ ∆N and a ∈ ∆N , where an ∼ e
(wtn )1 ∼ an xn ). The latter equation imposes several restrictions on a. In fact, for all
n, n0 ∈ N the following must be true: aan0 ≤ e−η(D−1)H , where H is the upper bound for
n
the loss λ(ω, γ). We denote the subset of such vectors a by ∆0N ( ∆N .
Note that wt1 ∼ (x1 · a1 , x2 · a2 , . . . , xN · aN ). We are to bound the maximum




x1 a1
max max0 |x1 − PN
| .
x∈∆N a∈∆N
n=1 xn an
We consider the case x1 > PNx1 a1
(the other case is similar). In this case
n=1 xn an




 




x1 a1
a1
max max0 x1 − PN
= max x1 max0 1 − PN
.
x∈∆N a∈∆N
x∈∆N
a∈∆N
n=1 xn an
n=1 xn an


We examine the behavior of 1 − PN a1
under the fixed x.
n=1


1 − PN

a1

n=1 xn an

xn an

 PN


→ max0

n=2 xn an

⇐⇒

a1

a∈∆N
PN

=

N
X
an
n=2

a1


xn → max0

(14)

a∈∆N

x a

Since aan1 ≤ e−η(D−1)H , we have n=1a1 n n ≤ (1 − x1 )e−η(D−1)H , and the argument a
that maximizes (14) does not depend on x2 , . . . , xN . W.l.o.g. we can assume that a =
1
1−a
1−a
e−η(D−1)H
(a, N1−a
−1 , N −1 , . . . , N −1 ), where a = (N −1)+e−η(D−1)H < N . At the same time, we can assume
1−x
1−x
that x = (x, N1−x
−1 , N −1 , . . . , N −1 ). Thus,






x1 a1
xa
max max0 x1 − PN
= max x −
.
(1−x)(1−a)
x∈∆N a∈∆N
x∈(0,1)
xa +
n=1 xn an
N −1


15

Korotin V’yugin Burnaev

√

The derivative is equal to zero at
e−η(D−1)H
(N −1)+e−η(D−1)H

x∗

=

1−a−

a(1−a)(N −1)
.
1−aN

Substituting x = x∗ and a =

we obtain the N -independent expression:
√
2
1 − e−η(D−1)H
.
1 − e−η(D−1)H

(15)

We are interested in the behavior near η = 0. A closer look at the Maclaurin series of
numerator and denominator give us the decomposition
2

2

H
0 + 0η + η 2 (D−1)
+ ...
4
.
0 + η(D − 1)H + . . .

At η → 0 the function is equal to 0. There exist some η 0 > 0, such that forall 0 ≤ η <η0
+  η.
expression (15) can be bounded by some η-linear function U (D, H) · η = (D−1)H
4
Thus, expression (13) is bounded by


T N · B · L · N · U (D, H) · η = F N T η
We set F = B · L · U (D, H). Next,

ln N 
HTD ≤ HT1 + |HT1 − HTD | ≤ L∗T +
+ F N T η,
η
 PT n 
where L∗T = minn∈N LnT = minn∈N
loss of the best constant expert.
t=1 lt is the
q


Choosing η ∗ = arg minη>0 lnηN + F N T η = FlnNNT , we obtain
√
√
√
√
RT ≤ 2 F N ln N · T = O( N ln N T )
regret bound with respect to the best expert in the pool.
Note that in order to use linear approximation of maximum we need η ≤ η 0 . Moreover, to bound the loss HT1 weqneed η ∗ -exponentially concave function λ. This means that
η ∗ ≤ min{η 0 , η λ }. Since η ∗ = FlnNNT ∼
the required conditions are met.

√1 ,
T

there exists some huge T0 such that for T ≥ T0

5. Conclusion
The problem of long-term forecasting is of high importance. In the article we developed
general algorithm GD (p) for the D-th-step ahead forecasting with experts’ advice (where
p is the distribution over active experts). The algorithm uses the ideas of the general
aggregating algorithm G1 by Vovk (1999). We also provided the expression for the upper
bound for the loss of algorithm GD (p) for any probability √
distribution p over active experts.
For its important special case VDF C we proved the O( T ) regret bound w.r.t. the best
expert in the pool. Algorithm VDF C is a practical long-term forecasting modification of
algorithm V1 by Vovk (1998).
16

Aggregating Strategies for Long-term Forecasting

It seems possible to apply the approach from the proof of Theorem 3 in order to obtain simpler and more understandable loss bound for algorithm GD (p) for any probability
distribution p. This statement serves as the challenge for our further research.

References
Dmitry Adamskiy, Wouter M. Koolen, Alexey Chernov, and Vladimir Vovk. A closer look
at adaptive regret. Journal of Machine Learning Research, 17(23):1–21, 2016. URL
http://jmlr.org/papers/v17/13-533.html.
Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory:
Price of past mistakes. In Proceedings of the 28th International Conference on Neural
Information Processing Systems - Volume 1, NIPS’15, pages 784–792, Cambridge, MA,
USA, 2015. MIT Press. URL http://dl.acm.org/citation.cfm?id=2969239.2969327.
Olivier Bousquet and Manfred K. Warmuth. Tracking a small set of experts by mixing
past posteriors. J. Mach. Learn. Res., 3:363–396, March 2003. ISSN 1532-4435. URL
http://dl.acm.org/citation.cfm?id=944919.944940.
Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge
University Press, New York, NY, USA, 2006. ISBN 0521841089.
Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning
and an application to boosting. Journal of Computer and System Sciences, 55(1):119
– 139, 1997. ISSN 0022-0000. doi: https://doi.org/10.1006/jcss.1997.1504. URL http:
//www.sciencedirect.com/science/article/pii/S002200009791504X.
Elad Hazan. Introduction to online convex optimization. Found. Trends Optim., 2(34):157–325, August 2016. ISSN 2167-3888. doi: 10.1561/2400000013. URL https:
//doi.org/10.1561/2400000013.
Mark Herbster and Manfred K. Warmuth. Tracking the best expert. Mach. Learn., 32(2):
151–178, August 1998. ISSN 0885-6125. doi: 10.1023/A:1007424614876. URL https:
//doi.org/10.1023/A:1007424614876.
Jyrki Kivinen and Manfred K. Warmuth. Averaging expert predictions. In Paul Fischer
and Hans Ulrich Simon, editors, Computational Learning Theory, pages 153–167, Berlin,
Heidelberg, 1999. Springer Berlin Heidelberg. ISBN 978-3-540-49097-5.
Alexander Korotin, Vladimir V’yugin, and Eugeny Burnaev. Long-term sequential prediction using expert advice. CoRR, abs/1711.03194, 2017. URL http://arxiv.org/abs/
1711.03194.
Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Inf. Comput.,
108(2):212–261, February 1994. ISSN 0890-5401. doi: 10.1006/inco.1994.1009. URL
http://dx.doi.org/10.1006/inco.1994.1009.

17

Korotin V’yugin Burnaev

Kent Quanrud and Daniel Khashabi.
Online learning with adversarial delays.
In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages
1270–1278. Curran Associates, Inc., 2015. URL http://papers.nips.cc/paper/
5833-online-learning-with-adversarial-delays.pdf.
V Vovk. A game of prediction with expert advice. J. Comput. Syst. Sci., 56(2):153–173,
April 1998. ISSN 0022-0000. doi: 10.1006/jcss.1997.1556. URL http://dx.doi.org/10.
1006/jcss.1997.1556.
V. Vovk. Derandomizing stochastic prediction strategies. Machine Learning, 35(3):247–282,
Jun 1999. ISSN 1573-0565. doi: 10.1023/A:1007595032382. URL https://doi.org/10.
1023/A:1007595032382.
Volodimir G. Vovk. Aggregating strategies. In Proceedings of the Third Annual Workshop
on Computational Learning Theory, COLT ’90, pages 371–386, San Francisco, CA, USA,
1990. Morgan Kaufmann Publishers Inc. ISBN 1-55860-146-5. URL http://dl.acm.
org/citation.cfm?id=92571.92672.
M. J. Weinberger and E. Ordentlich. On delayed prediction of individual sequences. IEEE
Transactions on Information Theory, 48(7):1959–1976, Jul 2002. ISSN 0018-9448. doi:
10.1109/TIT.2002.1013136.

Appendix A. Optimal Approach to Delayed Feedback Forecasting with
Experts’ Advice
The appendix is devoted to obtaining the minimax regret bound for the problem of
the D-th-step-ahead forecasting as a function of the minimax bound for the 1-step-ahead
forecasting. We consider the general protocol of the D-th-step-ahead forecasting game with
experts’ advice from Subsection 2.1. Within the framework of the task, we desire to compete
with the best expert in the pool.
We use Ωt to denote the sequence (ω1 , ..., ωt ) of time series values at first t steps. Pair
It = (Ωt , Ξt+D ) is the information that an online algorithm knows on the step t of the game.
Let SD,t be the set of all possible online randomized prediction aggregation algorithms with
the forecasting horizon D and game length t. Each online algorithm s ∈ SD,t for given time

series Ωt and experts answers Ξt provides a sequence of distributions π1s (γ), ..., πts (γ) ,
where each distribution πτs (γ) is a function of Iτ −D for τ = 1, . . . , t. We write πτs (γ) =
π s (γ|Iτ −D ).
The expected cumulative loss of the algorithm s ∈ SD,t on a given IT is
HtD (s, It )

t
X


=
Eπτs λ(ωτ , γ)
τ =1

and the cumulative loss of expert n:
Lnt (It ) =

t
X
τ =1

18

λ(ωτ , ξτn )

Aggregating Strategies for Long-term Forecasting

The online performance of the algorithm s ∈ SD,t for the given It is measured by the
expected cumulative regret over t rounds:
RtD (s, It ) = HtD (s, It ) − min Lnt (It )
n∈N

with respect to the best expert. Here λ(ω, γ) : Ω × Γ → R+ is some loss function, not
necessary convex, Lipshitz or exponentially concave. The performance of the strategy s is
RtD (s) = max RtD (s, It ),
It

that is the maximal expected regret over all possible games It . The strategy s∗D,t that
achieves the minimal regret
s∗D,t = arg min RtD (s)
sD ∈SD,t

is called optimal (may not be unique).
Theorem 4 For the given ΩT , ΞT , forecasting horizon D and game length T (such that T
is a multiple of D) we have
RTD (sD,T ) ≥ D · RT1 /D (s1,T /D ).
Proof Let s = s∗D,T ∈ SD,T be the optimal strategy. We define new one-step ahead
forecasting strategy s00 ∈ S1,T based on s. Let
00
πts

1
=
D

t
[D
]D+D

X

πτs

t
τ =[ D
]D+1

1
=
D

t
[D
]D+D

X

π s (γ|Iτ −D ).

t
τ =[ D
]D+1

For every one-step ahead forecasting game IT0 /D = (Ω0T /D , Ξ0T /D ) we create a new D-step
n
0
)0 for all
and (ξtn )00 = (ξ[t/D]+1
ahead forecasting game IT00 = (Ω00T , Ξ00T ). We set ωt00 = ω[t/D]+1
t = 1, 2, . . . , T and n ∈ N .
The last step is to define one-step ahead forecasting strategy s0 for one-step ahead
0
s00
forecasting game IT0 /D . We set πts = π(t−1)D+1
.
We compute the loss of the algorithm s on IT00 /D .
HTD (s, It00 ) =

T
X



Eπts λ(ωt00 , γ) =

t=1
T
X



0
Eπts λ(ω[t/D]+1
, γ) =

t=1

t=1

T /D 

X
t=1

T /D  D
X X

(t−1)D+1

τ =1
T /D 



D · Eπs00




00
s
Eπ(t−1)D+τ
λ(ωt , γ) =

X


λ(ωt00 , γ) = D
Eπs00
t=1
T /D 

=D

X
t=1

(t−1)D+1




00
λ(ωt , γ) =




00
Eπs0 λ(ωt , γ) = D · HT1 /D (s0 , IT0 /D )
t

19

Korotin V’yugin Burnaev

Also note that
LnT (IT00 ) = D · LnT /D (IT0 /D ).

(16)

Thus, for every IT0 /D we have
RTD (s, It00 ) = D · RT1 /D (s0 , IT0 /D ).
According to the definition of the minimax regret, for the one-step forecasting game of
length T /D there exists such IT0 /D that
RT1 /D (s0 , IT0 /D ) ≥ RT1 /D (s1,T /D )
.
For IT0 /D and the corresponding sequence we obtain
RTD (s) ≥ RTD (s, It00 ) = D · RT1 /D (s0 , IT0 /D ) ≥ D · RT1 /D (s1,T /D )
This ends the proof.
In fact, from Theorem 4 we can conclude that an optimal aggregating algorithm A∗D for
the long-term forecasting with experts’ advice and competing with the best expert can be
obtained by a simple replicating technique from the optimal algorithm A∗1 for the 1-step
ahead forecasting and competing with the best expert.
However, if the goal is not to compete with the best expert (but, for example, to compete
with the best alternating sequence of experts with no more than K switches or some other
limited sequence), this theorem may also work. All the computations still remain true in the
general case, except for (16). This equality should be replaced (if possible) by the analogue.

20

