Competitive on-line statistics

Volodya Vovk

Computer Learning Research Centre and Department of Computer Science Royal Holloway, University of London Egham, Surrey TW20 0EX, England

vovk@dcs.rhbnc.ac.uk

Technical Report

CLRC-TR-00-03

March 2000

����� ����� �����

Department of Computer Science Egham, Surrey TW20 0EX, England

Abstract

A radically new approach to statistical modelling, which combines mathematical techniques of Bayesian statistics with the philosophy of the theory of competitive on-line algorithms, has arisen over the last decade in computer science (to a large degree, under the influence of Dawid’s prequential statistics). In this approach, which we call “competitive on-line statistics”, it is not assumed that data are generated by some stochastic mechanism; the bounds derived for the performance of competitive on-line statistical procedures are guaranteed to hold (and not just hold with high probability or on the average). This paper reviews some results in this area; the new material in it includes the proofs for the performance of the Aggregating Algorithm in the problem of linear regression with square loss.

Introduction 1

1 Introduction

1.1 Problem

Making rational decisions is a central problem in science and everyday life. (Polynomials of which degree should I use to fit my data sets? Should I take my umbrella today, tomorrow, etc? Which stocks should I buy and sell this year?) Only rarely we can readily choose the best course of action; more often we will have a more or less extensive (maybe infinite) family of potentially successful decision strategies. (Whether a decision strategy is successful will depend not only on the merits of this strategy but also on the future events which we do not know yet.) However, at the end of the day we must choose one specific decision strategy, so we naturally arrive at this problem: given a family of decision strategies, find a new decision strategy which will perform, under any circumstances, almost as well as the best (under those circumstances) decision strategy in the family.

At first, this task might appear hopeless for even moderately interesting families of decision strategies. (Recall that we want the constructed decision strategy to perform almost as well as the best strategy in the family always; we do not make any stochastic assumptions about the generation of the future events.) However, for one specific loss function a good merging algorithm has been known for a long time (the Bayesian mixture) and for many more loss functions good merging algorithms have been found in recent years.

The usual statistical model is a family of probability distributions reflecting our knowledge or our assumptions about some piece of the world. The Bayesian framework involves another element, the prior distribution on the parameter set, which allows the Bayesian to replace the statistical model by a single probability distribution: the statistical model {Q_{θ} | θ ∈ Θ} with the prior distribution P (dθ) in Θ is replaced by the Bayesian mixture Q = ∫_{Θ} Q_{θ}P (dθ). This formula, reinterpreted and generalized, lies at the centre of competitive on-line statistics.

In competitive on-line statistics the statistical model is replaced by the decision pool, which is a family of decision strategies; the statistician’s goal is to replace this family with a single decision strategy. Recall that the competitive online statistician is agnostic: she does not assume anything about the stochastic mechanism generating the data; she does not even assume the existence of such a mechanism.

In the bulk of this paper (Sections 1–4) we describe in some detail only one of the existing merging algorithms (the Aggregating Algorithm [52, 55, 56]) and apply it to only one problem (linear regression with square loss function); a more balanced review of the field will be given in Section 5.

1.2 Aggregating Algorithm

Let Ω be some sample space, Γ be a decision space and Θ be a parameter space (the decision strategies in our decision pool will be indexed by θ ∈ Θ). We consider the following perfect-information game between three players, Statistician (usually called Learner in the machine learning literature), Decision Pool and Nature: at each trial t = 1, 2, …,

⋄ Decision Pool makes a prediction ξ_{t} : Θ → Γ; ξ_{t}(θ) is interpreted as the decision recommended by the decision strategy θ ∈ Θ;

⋄ Statistician makes her own decision γ_{t} ∈ Γ;

⋄ Nature chooses some outcome ω_{t} ∈ Ω.

There is some fixed loss function λ : Ω × Γ → [0, ∞]; Statistician’s goal is to ensure that her cumulative loss

L_{T} (Statistician) = ∑_{t=1}^{T} λ(ω_{t}, γ_{t})

is almost as good as the loss

L_{T} (θ) = ∑_{t=1}^{T} λ(ω_{t}, ξ_{t}(θ))

of all or most of the decision strategies θ ∈ Θ. Assuming that the number n = |Θ| of decision strategies in the pool is finite, it is possible to prove, for a wide class of games (Ω, Γ, λ), that Statistician can ensure that, for all T and θ,

L_{T} (Statistician) ≤ cL_{T} (θ) + a ln n,  (1)

where c and a are some constants. For a wide class of games the Aggregating Algorithm (described in the next section and, in more detail, in [55, 56]) ensures that (1) holds with optimal c and a; that algorithm does not require, however, that the decision pool should be finite. Since it is possible to improve c at the expense of deteriorating a and vice versa, the algorithm involves a learning rate η ∈ (0, ∞), and the optimal constants c = c(η) and a = a(η) in (1) depend on η.

The constants c(η) and a(η) have been found for many games; especially important are the perfectly mixable games, for which c(η) = 1 for some η. The most important for statistics games are perhaps the log-loss games; assuming for simplicity that Ω is finite, in the log-loss game with the sample space Ω the decision space Γ is the set of all probability distribution in Ω and the loss function is λ(ω, γ) = − ln γ{ω}. For this game the Aggregating Algorithm with learning rate η = 1 coincides with the Bayesian mixture (assuming the uniform prior); the constants are c(1) = a(1) = 1. Also important, especially in the problems of regression, is the following square-loss game: Ω = Γ = [−1, 1] and λ(ω, γ) = (ω − γ)^{2}. (We assume that the outcomes never exceed some known bound Y; without loss of generality we take Y = 1.) In the case of the squareloss game, c(η) = 1 and a(η) = 2 for some η. In general, a game is perfectly mixable if its loss function is “strictly convex” in some sense.

1.3 Linear regression

Even if the decision pool is infinite, in a surprisingly wide class of problems it is possible to derive good bounds for competitive on-line procedures; see Section 5 below. In this paper the methods of on-line competitive statistics will be illustrated on the problem of linear regression with the square loss. There are several competitive on-line algorithms for this problem; some of them will be discussed below (Subsection 5.1); we will consider in detail just one of them [54].

We have to extend slightly the protocol of the previous section: we will assume that at the beginning of every trial t Nature outputs a “signal” x_{t} to be used by Decision Pool and Statistician in making their decisions. We assume that the signals are taken from the L_{∞}-ball^{1} {x ∈ IR^{n} | ∥x∥_{∞} ≤ X} of radius X; the decision pool is indexed by the L_{1}-ball Θ = {θ ∈ IR^{n} | ∥θ∥_{1} ≤ C} of radius C; the decision strategy θ recommends prediction θ · x_{t} at trial t. Applying the Aggregating Algorithm to this decision pool and a Gaussian prior, the standard bounds for that algorithm imply

L_{T} (Statistician) ≤ L_{T} (θ) + C^{2}X^{2} + nC^{2}X^{2} ln(T + 1),  (2)

for all T and θ. (For the proof of this inequality and its elaborations, see Section 4 below; the assumptions that the signal and parameter spaces should be bounded were made only for simplicity; the essential assumption is that the responses ω_{t} should be bounded by a known constant.) To see that bound (2) is tight, assume that n = 1, θ ∈ [−1, 1], x_{t} = 1 for all t, and ω_{t} are generated by the iid process with the probability \frac{1+θ}{2} of ω_{t} = 1 and the probability \frac{1−θ}{2} of ω_{t} = −1. It is easy to check (for details, see Subsection 3.3 below) that, when θ = 0 and Statistician uses the Maximum Likelihood estimator for computing γ_{t}, the expected value of the difference between the right-hand and left-hand sides of (2) does not exceed the minute quantity of \frac{1}{T}.

As well known from traditional statistics (see, eg, [23], Chap 5), linear regression algorithms and their properties (such as (2)) can be immediately extended to apparently more general regression problems. For example, our results presented below will immediately imply the following (for simplicity we assume n = 1 and x_{t}, ω_{t} ∈ [−1, 1], ∀t):

Aggregating Algorithm 4

⋄ if the decision pool consists of all polynomials of degree d, Statistician has a strategy guaranteeing

1In this paper we will often make use of the norms L_{p}, p ≥ 1. Recall that, for any p > 0, the L_{p} norm ∥x∥_{p} of a vector x ∈ IR^{n} with coordinates x_{i} is (∑_{i=1}^{n} |x_{i}|^{p})^{1/p}; by definition, ∥x∥_{∞} = max_{i} |x_{i}|. It is well known that ∥x∥_{p} ≤ ∥x∥_{q} when p > q > 0 (see, eg, Beckenbach and Bellman [5], Section 1.16).

L_{T} (Statistician) ≤ inf_{θ} (L_{T} (θ) + ∥θ∥_{2}^{2}) + (d + 1) ln(T + 1)

(∥θ∥_{2}^{2} being the squared L_{2} norm of the polynomial’s coefficients);

⋄ if the decision pool consists of all splines of degree d with k nodes (chosen a priori), Statistician has a strategy guaranteeing

L_{T} (Statistician) ≤ inf_{θ} (L_{T} (θ) + ∥θ∥_{2}^{2}) + (d + k + 1) ln(T + 1).

1.4 This paper

This introductory section is essentially a revision of the conference version [59] of this paper. In the next section we will discuss in more detail the Aggregating Algorithm and its applications to some particular games. In Sections 3 and 4 we state and prove some elaborations of the results mentioned above about linear regression. In Section 5 we give a brief review of competitive on-line statistics; inevitably, many important results are not even mentioned in it. In the concluding Section 6 we briefly discuss limitations of competitive on-line statistics and put it in a more general context.

2 Aggregating Algorithm

2.1 Generic algorithm

In this subsection we describe the Aggregating Algorithm (AA), first when specialized to the case of perfectly mixable games and then in general (following [55] and [56]). Sometimes (following the tradition of the computational learning literature) we will say “expert” instead of “decision strategy”; the reader can imagine that each decision strategy in the pool is advocated by some expert; “pool of experts” is the same as “decision pool”. We will assume that the set Θ of experts is equipped with a σ-algebra; the decision (or prediction) space Γ is a topological space equipped with the σ-algebra generated by the open sets, the outcome space Ω is just a set, without any additional structure. The functions ξ_{t} : Θ → Γ chosen by Decision Pool are required to be measurable.

We fix a learning rate η > 0, put β = e^{−η}, and fix a probability distribution P_{0} in the pool Θ; the prior distribution P_{0} specifies the initial weights assigned to the experts.

First we describe an algorithm (the Aggregating Pseudo-Algorithm, or APA) that is allowed to make not permitted predictions γ ∈ Γ but “mixtures”, in some sense, of permitted predictions. A generalized prediction is defined to be any function of the type Ω → [0, ∞]; a permitted prediction γ ∈ Γ is identified with the generalized prediction g defined by g(ω) = λ(ω, γ). The APA suffers a loss of g_{t}(ω_{t}) after choosing generalized prediction g_{t} when the actual outcome is ω_{t}.

The APA works as follows. At every trial t = 1, 2, … Statistician updates the experts’ weights,

P_{t}(dθ) = β^{λ(ω_{t},ξ_{t}(θ))}P_{t−1}(dθ), θ ∈ Θ,  (3)

where P_{0} is the prior distribution. (So the weight of an expert θ whose prediction ξ_{t}(θ) leads to a large loss λ(ω_{t}, ξ_{t}(θ)) gets slashed. Recall that (3) is equivalent, by definition, to

P_{t}(E) = ∫_{E} β^{λ(ω_{t},ξ_{t}(θ))}P_{t−1}(dθ),

for all measurable E ⊆ Θ.) The generalized prediction chosen by the APA at trial t is the weighted average of the experts’ predictions:

g_{t}(ω) = log_{β} ∫_{Θ} β^{λ(ω,ξ_{t}(θ))}P_{t−1}^{∗}(dθ),  (4)

where P_{t−1}^{∗} are the normalized weights,

P_{t−1}^{∗}(dθ) = \frac{P_{t−1}(dθ)}{P_{t−1}(Θ)}  (5)

(assuming that the denominator is positive; if it is 0, P_{0}-almost all experts have suffered infinite loss and, therefore, the AA is allowed to choose any prediction). Later on (see the proof of Lemma 1 and Subsection 2.2) we will see that rules (3) and (4) are very natural and generalize Bayes’s rule.

The AA is obtained from the APA by replacing each generalized prediction g_{t} by a permitted prediction γ_{t} = Σ(g_{t}), where the substitution function Σ maps every generalized prediction g : Ω → [0, ∞] into a permitted prediction Σ(g) ∈ Γ. The AA as described in [55] requires that a “minimax” substitution function should be chosen, but it is often convenient to relax this requirement (in order to make the algorithm more efficient in some important cases, such as linear regression). Notice that the generalized predictions output by the APA are always of the form

ω ↦ log_{β} ∫_{Θ} β^{λ(ω,γ)}Q(dγ),

Q ranging over the probability distributions in Γ; we let P(λ, η) stand for the set of all generalized predictions of this form. We say that a substitution function Σ is perfect (for given λ and η) if, for every generalized prediction g ∈ P(λ, η),

λ(ω, Σ(g)) ≤ g(ω).

First we will assume that such a substitution function exists (in this case we will say that our game (Ω, Γ, λ) is η-mixable).

Now we can describe how the AA works: its only difference from the APA is that it outputs Σ(g_{t}) instead of the APA’s generalized prediction g_{t}, where Σ is a fixed perfect substitution function. When Statistician follows AA(η, P_{0}) (ie, the AA with learning rate η and prior P_{0}) we will write L_{T} (AA(η, P_{0})) in place of L_{T} (Statistician); we will also use analogous notation for the APA and other algorithms.

All our proofs are based on the following property of the APA (see [55]).

Lemma 1 For any learning rate η > 0, prior P_{0}, and T = 1, 2, …,

L_{T} (APA(η, P_{0})) = log_{β} ∫_{Θ} β^{L_{T} (θ)}P_{0}(dθ).  (6)

Proof We are required to deduce (6) from the weight update rule (3) and the formula (4) for computing pseudopredictions. It is more natural, however, to move in another direction, from (6) and (3) to (4). If we want to achieve goal (6) (this goal is the generalization of the formula Q = ∫_{Θ} Q_{θ}P (dθ) for Bayesian mixture; see Subsection 2.2 below), we have little choice but to compute pseudopredictions using (4) and (3). Indeed, noticing that

P_{T −1}(dθ) = β^{L_{T −1}(θ)}P_{0}(dθ)

(this immediately follows from (3)) and assuming (6), we obtain:

g_{T} (ω_{T}) = L_{T} (APA(η, P_{0})) − L_{T −1}(APA(η, P_{0})) = log_{β} \frac{∫_{Θ} β^{L_{T} (θ)}P_{0}(dθ)}{∫_{Θ} β^{L_{T −1}(θ)}P_{0}(dθ)}

= log_{β} \frac{∫_{Θ} β^{L_{T −1}(θ)+λ(ω_{T} ,ξ_{T} (θ))}P_{0}(dθ)}{∫_{Θ} β^{L_{T −1}(θ)}P_{0}(dθ)} = log_{β} \frac{∫_{Θ} β^{λ(ω_{T} ,ξ_{T} (θ))}P_{T −1}(dθ)}{P_{T −1}(Θ),}

which coincides with (4). Reversing this argument, we can see that (4) is not only necessary but also sufficient for (6).

For an η-mixable game, Lemma 1 implies

L_{T} (AA(η, P_{0})) ≤ log_{β} ∫_{Θ} β^{L_{T} (θ)}P_{0}(dθ).  (7)

In particular, if there are only finitely many experts and every expert is assigned the same weight \frac{1}{n} (n is the number of experts), we have, for any θ ∈ Θ,

L_{T} (AA(η, P_{0})) ≤ log_{β} (\frac{1}{n} ∑_{θ∈Θ} β^{L_{T} (θ)}) ≤ log_{β} (\frac{1}{n}β^{L_{T} (θ)}) = L_{T} (θ) + \frac{ln n}{η},

which coincides with (1) with c = 1 and a = \frac{1}{η}.

Recall that a game is called perfectly mixable if it is η-mixable for some learning rate η > 0. Now we will discuss the case where our game is not perfectly mixable (or the game is perfectly mixable but we are interested in η for which it is not η-mixable). In this case no perfect substitution function exists, so we need a different criterion for choosing the substitution function Σ; our choice of Σ will depend on η. First we define the important notion of the mixability curve c(η). For any η ∈ (0, ∞) we put

c(η) = inf {c | ∀g ∈ P(λ, η) ∃δ ∈ Γ ∀ω: λ(ω, δ) ≤ cg(ω)} ,  (8)

where inf ∅ is set to ∞. A related function is a(η) = \frac{c(η)}{η} (cf (14)). As shown in [55], c(η) and a(η) are continuous and monotonic functions (c(η) nondecreasing and a(η) nonincreasing).

We will always assume that our substitution function Σ = Σ_{η} satisfies

∀η ∀ω: λ(ω, Σ_{η}(g)) ≤ c(η)g(ω)  (9)

for any pseudoprediction g ∈ P(λ, η). We can satisfy this requirement provided that the infimum in (8) is attained; it is under mild assumptions (for details, see [55] and [56]) about the game (Ω, Γ, λ).

A natural way to ensure assumption (9) is to require that, for every pseudoprediction g,

Σ_{η}(g) ∈ arg min_{γ∈Γ} sup_{ω∈Ω} \frac{λ(ω, γ)}{g(ω)}  (10)

(where \frac{0}{0} is set to 0); a pleasant feature of such a definition would be the independence of Σ_{η} from η.

The following approach, however, seems to be more computationally efficient in many situations: we require that

Σ_{η}(g) ∈ arg min_{γ∈Γ} sup_{ω∈Ω} (λ(ω, γ) − c(η)g(ω))  (11)

(again min is attained under mild assumptions about the game (Ω, Γ, λ)) and

(g_{1}(ω) − g_{2}(ω) does not depend on ω) ⟹ (Σ_{η}(g_{1}) = Σ_{η}(g_{2})) . (12)

(Assumption (12) is always compatible with (11) but is typically incompatible with (10).) A crucial advantage of assumption (12) is that when running the AA we do not need to normalize the weights P_{t}(dθ), since the pseudoprediction

ω ↦ log_{β} ∫_{Θ} β^{λ(ω,ξ_{t}(θ))}P_{t−1}(dθ)

calculated from the unnormalized weights will differ from the pseudoprediction (4) calculated from the normalized weights by only an additive constant. Besides avoiding normalization of the weights at every trial, which is often computationally difficult, this way of defining the substitution function can lead to significant simplifications of the AA in particular applications; see, eg, Subsection 2.4 below.

We usually drop the index η of Σ_{η}.

For a game which is not necessarily η-mixable, we have, instead of (7),

L_{T} (AA(η, P_{0})) ≤ c(η) log_{β} ∫_{Θ} β^{L_{T} (θ)}P_{0}(dθ);  (13)

the other inequalities given above will also remain true if their right-hand side is multiplied by c(η). In particular, in the case of n < ∞ experts we have

L_{T} (AA) ≤ c(η)L_{T} (θ) + a(η) ln n,  (14)

where a(η) = \frac{c(η)}{η}; cf (1).

2.2 Log-loss games

Let us assume, for simplicity, that the sets Ω and Θ are finite. In the log-loss game, Γ is defined to be the set of all probability distributions in Ω and the loss function is defined as λ(ω, γ) = − ln γ(ω) (to simplify the notation, we let γ(ω) stand for the more formal γ({ω})). Let P_{0} be a prior probability distribution in Θ; set η = 1 (and, therefore, β = 1/e). With every decision strategy θ ∈ Θ we associate the unique probability distribution Q_{θ} in Ω^{∞} such that the expert θ’s prediction ξ_{t}(θ) = ξ_{t}^{θ} (the notation with θ as an upper index will be more convenient in this subsection) is (a variant of) the conditional Q_{θ}-probability for different values of ω_{t} given ω_{1}, …, ω_{t−1}. In other words, expert θ is a Bayesian whose subjective probability distribution is Q_{θ}; at the beginning of every trial t this expert quotes his subjective probabilities for ω_{t} given the past ω_{1} … ω_{t−1}.

The weight update rule (3),

P_{t}(θ) = β^{λ(ω_{t},ξ_{t}^{θ})}P_{t−1}(θ),

becomes

P_{t}(θ) = ξ_{t}^{θ}(ω)P_{t−1}(θ);

therefore, the normalized version (cf (5))

P_{t}^{∗}(θ) = \frac{Q_{θ}(ω_{1} … ω_{t})P_{0}(θ)}{∑_{θ} Q_{θ}(ω_{1} … ω_{t})P_{0}(θ)}

of P_{t} is identical to the posterior probability of θ after observing ω_{1} … ω_{t}.

It is easy to see that the integral in (4) is the predictive distribution of the Bayesian mixture ∫_{Θ} Q_{θ}P_{0}(dθ); therefore, generalized prediction (4) corresponds to a permitted prediction (viz the predictive distribution). It is clear that the AA (identical, in this case, to the APA) corresponds to the Bayesian mixture in the same sense as every decision strategy θ corresponds to Q_{θ} (ie, at every trial t the AA outputs the predictive distribution, according to the Bayesian mixture, of ω_{t} given the past).

To summarize, in the case of the log-loss game:

⋄ the weight update rule (3) is identical to Bayes’s theorem;

⋄ the AA is identical to the predictive version of the Bayesian mixture;

⋄ the APA is identical to the predictive version of the Bayesian mixture; this fact is also expressed by Lemma 1.

[figure: y; 1; x; 1; γ = 0; γ = 1]

Figure 1 The substitution function for the simple prediction game

2.3 Simple prediction game

Let us consider the following game (Ω, Γ, λ), which we call the simple prediction game:

Ω = Γ = \{0, 1\}, λ(ω, γ) = \{ \begin{matrix}0, if ω = γ, \\ 1, otherwise. \end{matrix}

(Therefore, in this game Statistician is trying to predict a binary classification, 0 or 1; at every trial she suffers a loss of 1 if she makes a mistake.) Suppose the pool contains a finite number n of decision strategies. To clarify the notions of pseudoprediction, substitution function, etc, in the rest of this subsection we will apply the AA to predicting in the simple prediction game using advice of n experts. (In this case the AA becomes the Weighted Majority Algorithm; see [43] and [53].)

In the case where there are just two possible outcomes, say 0 and 1 (as in the simple prediction game), it is convenient to represent every prediction γ ∈ Γ as the point (λ(0, γ), λ(1, γ)) of the (x, y)-plane. There are two permitted predictions in the simple prediction game, 0 and 1, which are depicted as small filled circles in Figure 1. It is also convenient to represent every pseudoprediction g : Ω → [0, ∞] as the point (g(0), g(1)) of the (x, y)-plane. Possible mixtures

(log_{β} (βp + (1 − p)) , log_{β} (p + β(1 − p)))  (15)

(see (4); this expression only depends on the total weight p = P_{t−1}^{∗}(Θ_{t}(1)) of the experts Θ_{t}(1) = {θ ∈ Θ | ξ_{t}(θ) = 1} who predict 1 at trial t; notice that 1 − p is the total weight P_{t−1}^{∗}(Θ_{t}(0)) of the experts Θ_{t}(0) = {θ ∈ Θ | ξ_{t}(θ) = 0} who predict 0 at trial t) of the permitted predictions are shown in Figure 1 by the curve (which we will call the pseudoprediction curve) connecting the two permitted predictions; (15) is a parametric equation of this curve (the parameter p ranges between 0 and 1).

{trial \atop no} Pool’s weights Pool’s predictions Statistician’s pseudoprediction Her pre- diction

{out- \atop come}

Pool’s losses

1  (1.00, 1.00, 1.00) (1, 1, 0)  (−0.55, −0.86) 1  0  (1, 1, 0)
2  (0.37, 0.37, 1.00) (0, 1, 1)  (0.14, −0.41)  1  1  (1, 0, 0)
3  (0.14, 0.37, 1.00) (0, 1, 0)  (−0.24, 0.24)  0  1  (1, 0, 1)

Table 1 Example of execution of the AA for the simple prediction game

It is clear from Figure 1 that in the simple prediction game 1/c(η) (see (8)) equals the abscissa (equivalently, the ordinate) of the intersection of the pseudoprediction curve and the straight line x = y; this intersection corresponds to p = 1/2 in (15), which gives

\frac{1}{c(η)} = log_{β} (\frac{1 + β}{2} );

equivalently,

c(η) = \begin{matrix}ln & \frac{1}{β} \\ ln & \frac{2}{1+β} \end{matrix} = \frac{η}{ln \frac{2}{1+exp(−η)}} .

Now it is clear that for every η there is essentially only one substitution function Σ_{η} satisfying (9): if g is above the line x = y, Σ_{η} should map g to the prediction γ = 0; if g is below the line x = y, Σ_{η} should map g to the prediction γ = 1; and only if g is exactly on the line x = y, Σ_{η}(g) can be defined arbitrarily. Notice that (15) being above the line x = y means that x < y, i.e.,

log_{β} (βp + (1 − p)) < log_{β} (p + β(1 − p)) ,

which is equivalent to p < 1/2; analogously, (15) being below the line x = y is equivalent to p > 1/2. This means that the AA predicts according to the weighted majority of the experts, which explains the name “Weighted Majority Algorithm”.

We conclude this subsection with an example of execution of the AA for the simple prediction game. Table 1 describes the AA’s behaviour in the first 3 trials in the situation where: there are three experts with equal initial weights who give predictions (1, 1, 0), (0, 1, 1) and (0, 1, 0); the actual outcomes (Nature’s moves) are 0, 1 and 1; the learning rate is 1 (and so β = 1/e). The weights given in Table 1 are unnormalized, and instead of (15) we use its unnormalized version

(log_{β} (βp + q) , log_{β} (p + βq)) ,  (16)

where p = P_{t−1}(Θ_{t}(1)) is the total unnormalized weight of the experts Θ_{t}(1) = {θ ∈ Θ | ξ_{t}(θ) = 1} who predict 1 at trial t and q = P_{t−1}(Θ_{t}(0)) is the total unnormalized weight of the experts Θ_{t}(0) = {θ ∈ Θ | ξ_{t}(θ) = 0} who predict 0 at trial t. We simplify (16) to

(ln \frac{1}{q + p/e}, ln \frac{1}{p + q/e}) .

2.4 Some results about the square-loss game

In this section we discuss the square-loss game; recall that in this game

Ω = [−1, 1], Γ = IR, λ(ω, γ) = (ω − γ)^{2}.

It is shown in [52] that this game is perfectly mixable if and only if η ≤ \frac{1}{2}, under the restriction ω_{t} ∈ {−1, 1}. Haussler et al [33] proved that this restriction can be removed. The goal of this section is to prove these facts and to find an explicit expression for a substitution function in the square-loss game.

First we consider the restricted square-loss game in which it is required that ω_{t} ∈ {−1, 1}. The following lemma is proven in [52] and Haussler et al [33], but we will give a simple independent proof.

Lemma 2 The restricted square-loss game is η-mixable if and only if η ≤ \frac{1}{2}.

Proof Let us represent (analogously to the previous subsection) a pseudoprediction (g(−1), g(1)) in the restricted square-loss game by the point

(x, y) = (e^{−ηg(−1)}, e^{−ηg(1)}) ∈ [0, 1]^{2}

of the (x, y)-plane. Therefore, the set of permitted predictions will be represented by the parametrical curve

(x(γ), y(γ)) = (e^{−η(−1−γ)^{2}}, e^{−η(1−γ)^{2}}) ,

where γ ranges over [−1, 1]. The game is η-mixable if and only if this curve veers to the left (when moving in the direction in which γ increases), ie if and only if

det ( \begin{matrix}x′(γ) & y′(γ) \\ x′′(γ) & y′′(γ) \end{matrix} ) ≥ 0, ∀γ.  (17)

Computing the derivatives we find

(x′(γ), x′′(γ)) ∝ (−(1 + γ), −1 + 2η(1 + γ)^{2}),
(y′(γ), y′′(γ)) ∝ ((1 − γ), −1 + 2η(1 − γ)^{2}),

with positive proportionality constants; therefore, condition (17) can be equivalently transformed as

−(1 + γ)(−1 + 2η(1 − γ)^{2}) − (1 − γ)(−1 + 2η(1 + γ)^{2}) ≥ 0, ∀γ;

η(1 − γ^{2}) ≤ \frac{1}{2}, ∀γ;

η ≤ \frac{1}{2}.

The following lemma is an elaboration of Haussler et al’s [33] result that the restriction ω_{t} ∈ {−1, 1} (assumed in [52]) can be removed. It asserts that any substitution function for the restricted game is also a substitution function in the full game.

Lemma 3 Fix Y_{1} and Y_{2} such that Y_{1} < Y_{2}. Let y and p range over [Y_{1}, Y_{2}] and IR, respectively, and λ(y, p) = (y − p)^{2} be the square loss function. Let P be a probability distribution in IR; put

f(y) = log_{β} ∫ β^{(y−p)^{2}}P (dp).

(So f is the pseudoprediction corresponding to P.) For every γ ∈ IR,

(λ(Y_{1}, γ) ≤ f(Y_{1}) & λ(Y_{2}, γ) ≤ f(Y_{2})) ⟹ (λ(y, γ) ≤ f(y), ∀y ∈ [Y_{1}, Y_{2}]) .

Proof It is sufficient to prove that for any fixed γ the function λ(y, γ) − f(y) is convex in y ∈ IR. Since

λ(y, γ) − f(y) = (y − γ)^{2} − log_{β} ∫ β^{(y−p)^{2}}P (dp)

= (y − γ)^{2} + \frac{1}{η} ln ∫ e^{−η(y−p)^{2}}P (dp),

it suffices to notice that

\frac{∂^{2}}{∂y^{2}} ln ∫ e^{−η(y−p)^{2}}P (dp) = \frac{1}{(∫ e^{−η(y−p)^{2}}P (dp))^{2}}

×(∫ e^{−η(y−p)^{2}}(−2η(y − p))^{2}P (dp) ∫ e^{−η(y−p)^{2}}P (dp)

+ ∫ e^{−η(y−p)^{2}}(−2η)P (dp) ∫ e^{−η(y−p)^{2}}P (dp)

− (∫ e^{−η(y−p)^{2}}(−2η(y − p))P (dp))^{2})

≥ \frac{1}{(∫ e^{−η(y−p)^{2}}P (dp))^{2}} (∫ e^{−η(y−p)^{2}}(−2η)P (dp) ∫ e^{−η(y−p)^{2}}P (dp)) = −2η

(the inequality follows from the Schwarz inequality; see, eg, [5], Section 1.18).

In the case of the square-loss game with y_{t} ∈ [−Y, Y], the minimax in the sense of (10) substitution function is

Σ(g) = Y \frac{\sqrt{g(−Y)} − \sqrt{g(Y)}}{\sqrt{g(−Y)} + \sqrt{g(Y)}}.

As explained in Subsection 2.1, it is likely that we obtain more efficient algorithms if we use (11) and (12) instead. It is clear that γ = Σ_{η}(g) will satisfy

(−Y − γ)^{2} − g(−Y) = (Y − γ)^{2} − g(Y),

which gives

γ = \frac{g(−Y) − g(Y)}{4Y}.  (18)

(This expression is one of the bounds in [33].)

In the case y_{t} ∈ [−Y, Y], η = \frac{1}{2} of Lemma 2 should be replaced by η = \frac{1}{2Y^{2}} .

Remark 1 Kivinen and Warmuth [41] ask the question when the weighted average will be a perfect substitution function, ie, when it is true that

∀ω∀P: λ (ω, ∫_{Γ} γP (dγ)) ≤ log_{β} ∫_{Γ} β^{λ(ω,γ)}P (dγ),

with P running over the probability distributions in Γ (cf (9)). We can see that the weighted average will be a perfect substitution function if and only if the function β^{λ(ω,γ)} in concave in γ. For the square-loss game this is equivalent to

\frac{∂^{2}}{∂γ^{2}} e^{−η(ω−γ)^{2}} ≤ 0, ∀ω, γ;

for ω, γ ∈ [−Y, Y], simple calculations give that this is true if and only if η ≤ \frac{1}{8Y^{2}} (which is 4 times worse than the constant in Lemma 2; we will meet this factor of 4 again in Section 3 below).

2.5 Other games

As we already mentioned, the log-loss and square-loss games are perfectly mixable. Some important games are not perfectly mixable, such as the simple prediction game, where

c(η) = \frac{η}{ln \frac{2}{1+exp(−η)}} , a(η) = \frac{1}{ln \frac{2}{1+exp(−η)}} .

When we take Γ = [0, 1] instead (the absolute loss game), c(η) and a(η) are halved (as evident from Figure 1) and the game becomes “almost perfectly mixable”, in the sense that c(η) → 1 as η → 0 (this is also true if Ω = [0, 1]).

Unfortunately, some important perfectly mixable games, such as the squareloss game, cease to be perfectly mixable when the sets of possible predictions and outcomes are widened; in the case of the square-loss game c(η) will jump to ∞ (for any η ∈ (0, ∞)) when the predictions and outcomes are allowed to take values in the whole real line IR. It is interesting to characterize the loss functions λ(ω, γ) giving perfectly mixable games when ω and γ are allowed to run over the whole of IR. An obvious example of such a game is

Ω = Γ = IR, λ(ω, γ) = (tanh ω − tanh γ)^{2},

but perhaps there are less trivial examples.

There are many interesting loss functions for which the mixability curves have not been found, such as the “robust” loss functions mentioned in Press et al [45], Section 15.7: the Lorentzian loss function

λ(ω, γ) = ln (1 + \frac{(ω − γ)^{2}}{2} ) ,

Andrew’s loss function

λ(ω, γ) = \{ \begin{matrix}1 − cos \frac{ω−γ}{c} , if |ω − γ| < cπ, \\ 2, otherwise, \end{matrix}

and Tukey’s biweight function

λ(ω, γ) = \{ \begin{matrix}1 − (1 − \frac{(ω−γ)^{2}}{c^{2}} )^{3} , if |ω − γ| < c, \\ 1, otherwise \end{matrix}

An important class of games of prediction are the probability games, in which the predictions γ and the outcomes ω are probability distributions in some set, which we, for simplicity, will assume to be finite and of the form {1, …, K}. The most important probability games are perhaps the Kullback–Leibler game, the Hellinger game and the χ^{2}-game with

Ω = Γ = {1, …, K}

and the loss functions

λ(ω, γ) = E_{ω} ln \frac{ω}{γ} = ∑_{k=1}^{K} ω_{k} ln \frac{ω_{k}}{γ_{k}} ,

λ(ω, γ) = ∑_{k=1}^{K} (\sqrt{ω_{k}} − \sqrt{γ_{k}})^{2} ,

λ(ω, γ) = ∑_{k=1}^{K} \frac{(ω_{k} − γ_{k})^{2}}{γ_{k}} ,

respectively (some applications of these loss functions are described in [8, 51]). Notice that the Kullback–Leibler game includes the log-loss game as a special case (take the degenerate ωs). The following result was proven in Haussler et al [33] (Example 4.3) under the assumption that K = 2.

Lemma 4 The Kullback–Leibler game is 1-mixable. The AA for the Kullback– Leibler game with learning rate 1 coincides with the Bayesian mixture.

Proof Fix learning rate η = 1. From considering the log-loss game it is clear that if the Kullback–Leibler game is 1-mixable, the weighted average (see Remark 1 above) must be the only substitution function. Let us prove that it will indeed be a substitution function. Suppose p + q = 1 and γ, δ ∈ Γ; we are required to prove

λ(ω, pγ + qδ) ≤ log_{β} (pβ^{λ(ω,γ)} + qβ^{λ(ω,δ)}) ,

where β = 1/e; or, after equivalent transformations:

β^{λ(ω,pγ+qδ)} ≥ pβ^{λ(ω,γ)} + qβ^{λ(ω,δ)},

e^{− ∑_{k} ω_{k} ln \frac{ω_{k}}{pγ_{k}+qδ_{k}}} ≥ pe^{− ∑_{k} ω_{k} ln \frac{ω_{k}}{γ_{k}}} + qe^{− ∑_{k} ω_{k} ln \frac{ω_{k}}{δ_{k}}} ,
e^{∑_{k} ω_{k} ln(pγ_{k}+qδ_{k})} ≥ pe^{∑_{k} ω_{k} ln γ_{k}} + qe^{∑_{k} ω_{k} ln δ_{k}},

∏_{k}(pγ_{k} + qδ_{k})^{ω_{k}} ≥ p ∏_{k} γ_{k}^{ω_{k}} + q ∏_{k} δ_{k}^{ω_{k}}.

The last inequality follows from the concavity of the function

f : (γ_{1}, …, γ_{K}) ↦ ∏_{k} γ_{k}^{ω_{k}}.

To check that this function is indeed concave, notice that the following quadratic form is negative definite:

∑_{k,j} \frac{∂^{2}f}{∂γ_{k}∂γ_{j}} x_{k}x_{j} ≈ ∑_{k≠j} \frac{ω_{k}ω_{j}}{γ_{k}γ_{j}} x_{k}x_{j} + ∑_{k} \frac{ω_{k}(ω_{k} − 1)}{γ_{k}^{2}}x_{k}^{2}

≈ ∑_{k≠j} ω_{k}ω_{j}y_{k}y_{j} + ∑_{k} ω_{k}(ω_{k} − 1)y_{k}^{2} = ∑_{k,j} ω_{k}ω_{j}y_{k}y_{j} − ∑_{k} ω_{k}y_{k}^{2}

= (∑_{k} ω_{k}y_{k})^{2} − ∑_{k} ω_{k}y_{k}^{2} = (E_{ω}y)^{2} − E_{ω}(y^{2})

(where ≈ means that the quadratic forms on both sides of this sign are either simultaneously negative definite or not); the negative definiteness of the last expression follows from Lyapunov’s inequality (see, eg, [5], Section 1.16).

Another interesting class of games are connected with finance; the simplest game of this kind is Cover’s game:

Ω = [0, ∞)^{K}, Γ = {(p_{1}, …, p_{K}) ∈ [0, ∞)^{K} | p_{1} + ⋯ + p_{K} = 1},

λ((y_{1}, …, y_{K}), (p_{1}, …, p_{K})) = − ln ∑_{k=1}^{K} y_{k}p_{k};

the financial meaning of this game is described in, eg, [18, 58]. Like the Kullback–Leibler game, Cover’s game is also a generalization of the log-loss game (with a finite sample space): it suffices to consider “degenerate” ω ∈ Ω of the form (0, …, 0, 1, 0, …, 0). (Such “degenerate” ω can be regarded as “crisp events”; they can be generalized to “fuzzy events” ω = (y_{1}, …, y_{K}) ∈ [0, 1]^{K}, where y_{k} is interpreted as the weight of evidence in favour of k occurring.) Cover’s “universal portfolio” algorithm [17, 18] is the AA applied to this game and a particular decision pool, the constant rebalanced portfolios (cf [58]); however, the AA and Cover’s algorithm were found independently of each other (the AA was obtained by bridging the Weighted Majority Algorithm and the Bayesian mixing rule).

Cover’s game ignores transaction costs and the possibility of “short selling” in financial markets. The long-short game, introduced by Watkins [58], takes the possibility of “short selling” into account. Both Cover’s game and the longshort game are perfectly mixable. Taking into account transaction costs leads to a plethora of new games (cf Blum and Kalai [7] and Vovk and Watkins [58]).

Regression: results 16

The constants c(η) and a(η) for the games mentioned above were found in [22, 43, 33, 18, 52, 55, 58]. We have already noticed that a game is perfectly mixable if its loss function is “strictly convex” in some sense. The exact statement in the binary case (ie, where the outcome space Ω consists of only 2 elements) can be found in [52] (Lemma 2) and [33]; it is an open problem to find a simple general criterion.

3 Regression: results

In this section we will show in detail how to apply the AA to the problem of linear regression with the square loss; our main assumption is that the response variable is bounded. It turns out that for this particular problem the AA (when applied to the decision pool of linear functions with a Gaussian prior) resembles, but is different from, the well-known Ridge Regression (RR) procedure. From general results about the AA we deduce a guaranteed bound on the difference between the AA’s performance and the best, in some sense, linear regression function’s performance. We show that the AA attains the optimal constant in our bound, whereas the constant attained by the RR procedure in general can be 4 times worse.

3.1 Explicit algorithm

In the problem of regression, we consider the following protocol of interaction between Statistician and Nature (a modification of the protocol of the previous section):

FOR t = 1, 2, …

Nature chooses x_{t} ∈ IR^{n}

Statistician chooses prediction γ_{t} ∈ IR Nature chooses y_{t} ∈ [−Y, Y]

END FOR.

(Notice that we now use the notation y_{t}, rather than ω_{t}, for the outcomes chosen by Nature; this (x, y) notation is conventional in the regression literature.) This is a “perfect-information” protocol: either player can see the other player’s moves. The parameters of our protocol are: a fixed positive number n (the dimensionality of our regression problem) and an upper bound Y > 0 on the value y_{t} returned by Nature. It is important, however, that our algorithm for playing this game (on the part of Statistician) does not need to know Y.

In this subsection we only give a description of our regression algorithm; its rigorous derivation from the general AA will be given in the next section. (It is usually a non-trivial task to represent the AA in a computationally efficient form, and the case of on-line linear regression is not an exception.) Here we will only briefly describe the main idea of how the AA is applied to our regression problem. Let Σ be a perfect substitution function for the square-loss game and η = \frac{1}{2Y^{2}} . Our experts are indexed by θ ∈ IR^{n}. At trial t, expert θ outputs the prediction ξ_{t}(θ) = θ · x_{t}; all such predictions are averaged in accordance with the experts’ weights and Σ is applied to the resulting generalized prediction. (For details, see the next section.)

Fix n and a > 0. The algorithm is as follows:

A = aI; b = 0

FOR TRIAL t = 1, 2, …:

read new x_{t} ∈ IR^{n}
A = A + x_{t}x′_{t}
output prediction γ_{t} = b′A^{−1}x_{t}
read new y_{t} ∈ IR
b = b + y_{t}x_{t}

END FOR.

In this description, A is an n × n matrix (which is always symmetrical and positive definite), b ∈ IR^{n}, I is the unit n × n matrix, and 0 is the all-0 vector. As usual, vectors are identified with one-column matrices; B′ stands for the transpose of matrix B.

This algorithm will be denoted AAR (the AA for Regression), or AAR(n, a). It should be remembered, however, that in principle the AA can be applied to the problem of regression in many different ways, and the AAR was derived from the AA under some strong extra assumptions (including a Gaussian prior on the decision pool).

3.2 Upper bounds

In this subsection we state results describing the predictive performance of the AAR; they (as well as the results stated in the rest of this section) will be proven in the next section. Recall that our decision pool consists of the linear functions x_{t} ↦ θ · x_{t}, where θ ∈ IR^{n}. At every trial t expert θ and Statistician suffer loss (y_{t} −θ ·x_{t})^{2} and (y_{t} −γ_{t})^{2}, respectively. A typical bound for the AAR that we would like to prove is: assuming that the signals x_{t} and the parameter θ are confined to the unit balls in the metrics L_{∞} and L_{1}, respectively,

L_{T} (AAR) ≤ L_{T} (θ) + n ln(T + 1) + 1,  (19)

for all T and θ (this is (2) with C = X = 1).

Remark 2 In the case n = 1 and x_{t} = 1, ∀t, inequality (19) differs from Freund’s [27] Theorem 4 only in the additive constant. In that paper Freund noticed that for the problems that he considered the adversarial bounds of competitive on-line statistics are only a tiny amount worse than the averagecase bounds for some stochastic strategies for Nature; this paper shows other manifestations of this phenomenon.

For compact pools of experts (which, in our setting, corresponds to the set of possible weights θ being bounded and closed) it is usually possible to derive bounds (such as (19)) where Statistician’s loss is compared to the best expert’s loss. In the case of non-compact pool, however, we need to give Statistician a start on remote experts. Specifically, instead of comparing Statistician’s performance to inf_{θ} L_{T} (θ), we compare it to inf_{θ} (L_{T} (θ) + a∥θ∥_{2}^{2}) (thus giving Statistician a start of a∥θ∥_{2}^{2} on expert θ), where a > 0 is a constant reflecting our prior expectations about the “complexity” ∥θ∥_{2} = \sqrt{∑_{i=1}^{n} θ_{i}^{2}} of successful experts.

This idea of giving a start to Statistician allows us to prove stronger results; eg, the following elaboration of (19) holds:

L_{T} (AAR) ≤ inf_{θ} (L_{T} (θ) + ∥θ∥_{2}^{2}) + n ln(T + 1)  (20)

(this inequality still assumes that ∥x_{t}∥_{∞} ≤ 1 and |y_{t}| ≤ 1 for all t, but θ is unbounded).

Theorem 1 For any positive integer n and any a > 0,

L_{T} (AAR(n, a)) ≤ inf_{θ} (L_{T} (θ) + a∥θ∥_{2}^{2}) + Y^{2} ln det (I + \frac{1}{a} ∑_{t=1}^{T} x_{t}x′_{t})

≤ inf_{θ} (L_{T} (θ) + a∥θ∥_{2}^{2}) + Y^{2} ∑_{i=1}^{n} ln (1 + \frac{1}{a} ∑_{t=1}^{T} x_{t,i}^{2}) .

If, in addition, ∥x_{t}∥_{∞} ≤ X, ∀t,

L_{T} (AAR(n, a)) ≤ inf_{θ} (L_{T} (θ) + a∥θ∥_{2}^{2}) + nY^{2} ln (\frac{T X^{2}}{a} + 1) . (21)

The last inequality of this theorem implies inequalities (20) (it suffices to put X = Y = a = 1) and (2) (put a = X^{2}).

To interpret the term

ln det (I + \frac{1}{a} ∑_{t=1}^{T} x_{t}x′_{t})

in Theorem 1, notice that it can be rewritten as

n ln T + ln det (\frac{1}{T} I + \frac{1}{a}cov(X_{1}, …, X_{n})) ,

where cov(X_{1}, …, X_{n}) is the empirical covariance matrix of the predictor variables (in other words, cov(X_{1}, …, X_{n}) is the covariance matrix of the random vector which takes the values x_{1}, …, x_{T} with equal probability \frac{1}{T}). We can see that this term is typically close to n ln T.

3.3 Lower bounds

The following simple argument (sketched in Subsection 1.3 above) shows that bound (19) is tight in a certain (rather weak) sense. Let n = 1, θ ∈ [−1, 1] and, for all t, x_{t} = 1 and y_{t} ∈ {−1, 1} (ie, we are interested in the problem of classification in the absence of any signals from Nature). Suppose the data are generated stochastically by the iid process with probability \frac{1+θ}{2} of y_{t} = 1 and probability \frac{1−θ}{2} of y_{t} = −1. (Therefore, we are essentially assuming the Bernoulli model.) A good estimate of θ after trial T is the Maximum Likelihood Estimate (MLE): p_{T} = \frac{1}{T} ∑_{t=1}^{T} y_{t} (with, say, p_{0} = 0). The expected loss of this estimator at trial T + 1 is

E ((p_{T} − y_{T +1})^{2}) = E ((p_{T} − θ)^{2}) + E ((θ − y_{T +1})^{2}) = \frac{1}{T} (1 − θ^{2}) + (1 − θ^{2})

(when T = 0, \frac{1}{T} (1−θ^{2}) should be replaced by θ^{2}); therefore, its cumulative loss over the first T trials is

θ^{2} + (1 − θ^{2}) ∑_{t=1}^{T −1} \frac{1}{t} + T (1 − θ^{2})

≥ θ^{2} + (1 − θ^{2}) ∫_{1}^{T} \frac{1}{t} + T (1 − θ^{2}) = θ^{2} + (1 − θ^{2}) ln T + T (1 − θ^{2}).

On the other hand, the expected loss of the best expert over the first T trials is

E ∑_{t=1}^{T} (y_{t} − \frac{Y_{T}}{T} )^{2}

= ∑_{t=1}^{T} E(y_{t} − θ)^{2} − 2 ∑_{t=1}^{T} E (y_{t} − θ) (\frac{Y_{T}}{T} − θ) + ∑_{t=1}^{T} E (\frac{Y_{T}}{T} − θ)^{2}

= T (1 − θ^{2}) − 2T \frac{1}{T} (1 − θ^{2}) + T \frac{1}{T^{2}} T (1 − θ^{2}) = T (1 − θ^{2}) − (1 − θ^{2}),

where Y_{T} = ∑_{t=1}^{T} y_{t}. We can see that

E(L_{T} (MLE) − L_{T}^{∗}) ≥ (1 − θ^{2}) + θ^{2} + (1 − θ^{2}) ln T = 1 + (1 − θ^{2}) ln T,

L_{T}^{∗} being the loss of the best expert after T trials. For θ = 0 we obtain

EL_{T} (MLE) ≥ EL_{T}^{∗} + ln T + 1,

so the MLE cannot much improve on (19) even on the average; the improvement of at most ln(T + 1) − ln T ≤ \frac{1}{T} is minute. We can see that even in the case where Nature is not adversarial but instead follows a simple stochastic strategy, inequality (19) is tight.^{2}

∑_{t=1}^{T −1} \frac{1}{t} ≥ ∫_{1}^{T} \frac{1}{t} = ln T

2Replacing the inequality

A weakness of this argument is that, despite the common belief that the MLE is a reasonable estimator in the case of the Bernoulli model, it is desirable to have some lower bounds applicable to any strategy for Statistician. The next theorem is a step in this direction.

Theorem 2 Fix n (the number of attributes), Y (the upper bound on |y_{t}|) and a > 0. For any ϵ > 0 there exist a constant C and a stochastic strategy for Nature such that ∥x_{t}∥_{∞} = 1 and |y_{t}| = Y, for all t, and, for any stochastic strategy for Statistician,

E (L_{T} (Statistician) − inf_{θ} (L_{T} (θ) + a∥θ∥_{2}^{2})) ≥ (n − ϵ)Y^{2} ln T − C, ∀T

(cf inequality (21)).

In the proof of this theorem (see the next section) we will exhibit a suitable strategy for Nature (it will be just a mixture of the iid processes considered above with a beta prior).

3.4 Comparisons with Ridge Regression

The first method proposed for linear regression (by Gauss) was the Least Squares method; in the square-loss game, this means that we choose the best expert. Of course, the expert who has been the best in the past may perform badly in the future; to overcome this danger of overfitting, the RR procedure was proposed. In its simplest form, this procedure is just another implementation of the idea of giving Statistician a start on remote experts: as an estimate of θ we take the value where the inf in (21) is attained. The explicit formula is

θ = (aI + ∑_{t=1}^{T} x_{t}x′_{t})^{−1} (∑_{t=1}^{T} y_{t}x_{t})

(see Subsection 4.5 below), where a is a positive ridge constant; the Least Squares procedure corresponds to a = 0. Using this estimate to predict y_{T +1}, we obtain the following RR prediction:

θ′x_{T +1} = (∑_{t=1}^{T} y_{t}x_{t})′ (aI + ∑_{t=1}^{T} x_{t}x′_{t})^{−1} x_{T +1};  (22)

the on-line prediction algorithm using this formula for computing its predictions will be called the RR procedure. Notice that the RR procedure is very similar to the AAR; it can be obtained by swapping two lines in the AAR:

∑_{t=1}^{T −1} \frac{1}{t} ≥ 1 + ∫_{2}^{T} \frac{1}{t} = ln T + 1 − ln 2,

used above by the more accurate we can see that our worst-case bound for the AAR is actually better than the precise averagecase bound for the MLE when T > 2.

A = aI; b = 0

FOR TRIAL t = 1, 2, …:

read new x_{t} ∈ IR^{n}
output prediction γ_{t} = b′A^{−1}x_{t}
A = A + x_{t}x′_{t}
read new y_{t} ∈ IR
b = b + y_{t}x_{t}

END FOR.

Correspondingly, the predictions output by the AAR are given by a formula very similar to (22):

γ_{T +1} = (∑_{t=1}^{T} y_{t}x_{t})′ (aI + ∑_{t=1}^{T +1} x_{t}x′_{t})^{−1} x_{T +1}.

It is easy to see that the RR procedure amounts to applying the Least Squares procedure (RR with a = 0) to an enlarged training set: we add n more observations, specifically (x_{−n+1}, y_{−n+1}), …, (x_{0}, y_{0}), where (x_{−n+i}, y_{−n+i}) = (\sqrt{a}e_{i}, 0), e_{i} is the ith column of the unit n × n matrix, and a > 0 is the ridge constant. In the AAR, we add one more observation to our training set: namely, the observation (x_{T +1}, 0), where x_{T +1} are the attributes of the example to be classified. Therefore, the AAR makes a further step towards shrinking the predictions to 0; hopefully, this extra shrinking will make the algorithm even more resistant to overfitting.

It is possible to deduce an explicit relation between the AAR’s prediction γ_{T} and the RR’s prediction r_{T} at trial T (this was first done by Kostas Skouras): by the Sherman-Morrison formula (40),

γ_{T} = b′_{T −1}A_{T}^{−1}x_{T} = b′_{T −1}A_{T −1}^{−1}x_{T} − b′_{T −1} \frac{(A_{T −1}^{−1}x_{T} ) (A_{T −1}^{−1}x_{T} )′}{1 + x′_{T} A_{T −1}^{−1}x_{T}} x_{T}

= r_{T} − \frac{b′_{T −1}A_{T −1}^{−1}x_{T} x′_{T} A_{T −1}^{−1}x_{T}}{1 + x′_{T} A_{T −1}^{−1}x_{T}} = r_{T} (1 − \frac{x′_{T} A_{T −1}^{−1}x_{T}}{1 + x′_{T} A_{T −1}^{−1}x_{T}} ) = \frac{r_{T}}{1 + x′_{T} A_{T −1}^{−1}x_{T}} ,

where the notations A_{t} and b_{t} are used in the sense of the AAR, ie A_{t} = aI + ∑_{s=1}^{t} x_{s}x′_{s}, b_{t} = ∑_{s=1}^{t} y_{s}x_{s}. Now we can see the nature of the dependence of γ_{T} on x_{T}: γ_{T} is a rational function, namely a linear function divided by a quadratic function. The limiting behaviour of γ_{T} and r_{T} is very different as x_{T} → ∞: typically, r_{T} → ∞, whereas always γ_{T} → 0. Notice that, according to this formula, in the problem of classification (where the outcome space is {−1, 1}) the AAR gives the same categorical prediction, + or −, as the RR procedure.

It can be seen that the RR sometimes gives results that are not sensible in our framework where y_{t} ∈ [−Y, Y] and the goal is to compete against the best linear regression function. For example, suppose that n = 1, Y = 1, and Nature generates outcomes (x_{t}, y_{t}), t = 1, 2, …, where

a ≪ x_{1} ≪ x_{2} ≪ …, y_{t} = \{ \begin{matrix}1, if t odd, \\ −1, if t even. \end{matrix}

At trial t = 2, 3, … the RR (more accurately, its natural modification which truncates its predictions to [−1, 1]) will give prediction γ_{t} = y_{t−1} equal to the previous response, and so will suffer a loss of about 4T over T trials. On the other hand, the AAR’s prediction will be close to 0, and so the cumulative loss of the AAR over the first T trials will be about T, which is close to the best expert’s loss. We can see that the RR procedure in this situation is forced to suffer a loss 4 times as big as the AA’s loss. (It is interesting that the same constant 4 occurs in Theorem 4 below; cf Theorem 1.)

The lower bound proven in Subsection 3.3 does not imply that our regression algorithm is better than the RR in our adversarial framework. (Moreover, the idea of the proof of Theorem 2 given in the next section is to lower bound the performance of the RR in the situation where the expected loss of the RR is optimal.) Theorem 1 asserts that

L_{T} (Statistician) ≤ inf_{θ} (L_{T} (θ) + a∥θ∥_{2}^{2}) + Y^{2} ∑_{i=1}^{n} ln (1 + \frac{1}{a} ∑_{t=1}^{T} x_{t,i}^{2}) (23)

when Statistician follows the AAR. The next theorem shows that the RR sometimes violates this inequality.

Theorem 3 Let n = 1 (the number of attributes) and Y = 1 (the upper bound on |y_{t}|); fix a > 0. Nature has a strategy such that, when Statistician follows RR(n, a),

L_{T} (Statistician) = 4T + o(T),  (24)
inf_{θ} (L_{T} (θ) + a∥θ∥_{2}^{2}) ≤ T,  (25)

ln (1 + \frac{1}{a} ∑_{t=1}^{T} x_{t}^{2}) = 2T ln 2 + O(1)  (26)

as T → ∞ (and, therefore, (23) is violated).

Nature’s strategy that ensures the inequality of Theorem 3 is very simple: she generates, for t = 1, 2, …,

x_{t} = 2^{t−1}, y_{t} = \{ \begin{matrix}1, if t is odd, \\ −1, if even. \end{matrix}

Regression: proofs 23

The RR prediction can be obtained as the mean of the posterior distribution (as proven in Subsection 4.5), whereas the AAR’s prediction is obtained by using a more sophisticated substitution function. Let RR^{Y} be the modification of the RR procedure in which the experts’ predictions θ · x_{t} at every trial t are clipped to [−Y, Y] before averaging. The properties of the posterior mean as a substitution function have been studied by Kivinen and Warmuth [41]; their result (reproduced in Remark 1 above) immediately implies the following theorem (for details see the next section).

Theorem 4 For any fixed n, Y > 0 and a > 0,

L_{T} (RR^{Y} (n, a)) ≤ inf_{θ} (L_{T} (θ) + a∥θ∥_{2}^{2}) + 4Y^{2} ln det (I + \frac{1}{a} ∑_{t=1}^{T} x_{t}x′_{t})

≤ inf_{θ} (L_{T} (θ) + a∥θ∥_{2}^{2}) + 4Y^{2} ∑_{i=1}^{n} ln (1 + \frac{1}{a} ∑_{t=1}^{T} x_{t,i}^{2}) ,

provided all y_{t} belong to [−Y, Y].

It is not clear if this remains true when RR^{Y} is replaced with RR (but this is not a particularly interesting question in view of the better bound of Theorem 1).

4 Regression: proofs

4.1 Derivation of the AAR

Let a > 0 be an arbitrary constant. Consider the prior distribution P_{0} in the set IR^{n} of possible weights θ with the Gaussian density

(aη/π)^{n/2}e^{−aη∥θ∥_{2}^{2}}dθ  (27)

(the value of the normalizing constant is given in, eg, [5], Chap 2, Theorem 3). The loss of expert θ over the first T trials is

∑_{t=1}^{T}(y_{t} − x′_{t}θ)^{2} = θ′ (∑_{t=1}^{T} x_{t}x′_{t}) θ − 2 (∑_{t=1}^{T} y_{t}x′_{t}) θ + ∑_{t=1}^{T} y_{t}^{2}.  (28)

Therefore, the loss of the APA is

log_{β} ∫_{IR}_{n} dθ(aη/π)^{n/2}

× exp (−ηθ′ (aI + ∑_{t=1}^{T} x_{t}x′_{t}) θ + 2η (∑_{t=1}^{T} y_{t}x′_{t}) θ − η ∑_{t=1}^{T} y_{t}^{2}) . (29)

In accordance with (18) and (29), the AA’s prediction should be^{3}

γ_{T} = \frac{1}{4Y} log_{β} \frac{β^{g_{T} (−Y)}}{β^{g_{T} (Y)}}

= \frac{1}{4Y} log_{β} \frac{∫_{IR}_{n} e^{−ηθ′(aI+∑_{t=1}^{T} x_{t}x′_{t})θ+2η(∑_{t=1}^{T −1} y_{t}x′_{t}−Y x′_{T} )θ−η(∑_{t=1}^{T −1} y_{t}^{2}+Y^{2})}dθ}{∫_{IR}_{n} e^{−ηθ′(aI+∑_{t=1}^{T} x_{t}x′_{t})θ+2η(∑_{t=1}^{T −1} y_{t}x′_{t}+Y x′_{T} )θ−η(∑_{t=1}^{T −1} y_{t}^{2}+Y^{2})}dθ}

3See below for the explanation of some steps in this derivation.

= \frac{1}{4Y} log_{β} \frac{∫_{IR}_{n} e^{−ηθ′(aI+∑_{t=1}^{T} x_{t}x′_{t})θ+2η(∑_{t=1}^{T −1} y_{t}x′_{t}−Y x′_{T} )θ}dθ}{∫_{IR}_{n} e^{−ηθ′(aI+∑_{t=1}^{T} x_{t}x′_{t})θ+2η(∑_{t=1}^{T −1} y_{t}x′_{t}+Y x′_{T} )θ}dθ}  (30)

= \frac{1}{4Y} log_{β} e^{−ηF(aI+∑_{t=1}^{T} x_{t}x′_{t},−2 ∑_{t=1}^{T −1} y_{t}x′_{t},2Y x′_{T} )}  (31)
= \frac{1}{4Y} F (aI + ∑_{t=1}^{T} x_{t}x′_{t}, −2 ∑_{t=1}^{T −1} y_{t}x′_{t}, 2Y x′_{T} )

= (∑_{t=1}^{T −1} y_{t}x′_{t}) (aI + ∑_{t=1}^{T} x_{t}x′_{t})^{−1} x_{T}  (32)

(notice that η and Y disappeared), where we used the notation

F (A, b, x) = inf_{θ∈IR^{n}} (θ′Aθ + b′θ + x′θ) − inf_{θ∈IR^{n}} (θ′Aθ + b′θ − x′θ)

and the fact that the function F can be transformed as follows:

F (A, b, x) = inf_{θ∈IR^{n}} (θ′Aθ + b′θ + x′θ) − inf_{θ∈IR^{n}} (θ′Aθ + b′θ − x′θ)

= −\frac{1}{4}(b + x)′A^{−1}(b + x) + \frac{1}{4}(b − x)′A^{−1}(b − x) = −b′A^{−1}x.

To see why the transition from (30) to (31) is justified, notice that a horizontal translation

(θ + c)′A(θ + c) = θ′Aθ + 2c′Aθ + c′Ac

of a positive definite quadratic form θ′Aθ can have an arbitrary vector coefficient 2c′A in front of θ; therefore, the quadratic forms in the numerator and denominator of (30) can be obtained from each other by horizontal translation and adding a constant. It is clear that the ratio of the integrals in (30) depends only on this additive constant, which is written in the form F (…) in (31).

4.2 Upper bounds: Proof of Theorem 1

The proof of the first inequality in Theorem 1 (whose derivation from known properties of the general AA does not present any difficulties) will be given in the next paragraph; the second inequality follows from, eg, [5], Chap 2, Theorem 7; the third inequality is trivial.

Set η = \frac{1}{2Y^{2}} (cf Subsection 2.4). Let the maximum of the expression under the exp sign in (29) be attained at a point θ = θ_{0} (this is also the point where the minimum is attained in the statement of the theorem). Subtracting the “regularized” loss

θ′_{0} (aI + ∑_{t=1}^{T} x_{t}x′_{t}) θ_{0} − 2 (∑_{t=1}^{T} y_{t}x′_{t}) θ_{0} + ∑_{t=1}^{T} y_{t}^{2}

of expert θ_{0} (see (28)) from (29), we obtain

log_{β} ∫_{IR_{n}} dθ(aη/π)^{n/2}e^{−ηB(θ)},  (33)

where B(θ) is a translation (ie, horizontal translation plus a constant) of the quadratic form

θ′ (aI + ∑_{t=1}^{T} x_{t}x′_{t}) θ;  (34)

since inf_{θ} B(θ) = 0, B(θ) is a horizontal translation of (34) (cf the last paragraph of the previous section), and so (33) equals

log_{β} ∫_{IR_{n}} dθ(aη/π)^{n/2} exp (−ηθ′ (aI + ∑_{t=1}^{T} x_{t}x′_{t}) θ) .

Directly evaluating the integral (see, eg, [5], Chap 2, Theorem 3), we can transform this expression to

log_{β} ((aη/π)^{n/2} \frac{π^{n/2}}{\sqrt{det (aηI + η ∑_{t=1}^{T} x_{t}x′_{t})}}) = −\frac{1}{2} log_{β} det (I + \frac{1}{a} ∑_{t=1}^{T} x_{t}x′_{t})

= \frac{1}{2η} ln det (I + \frac{1}{a} ∑_{t=1}^{T} x_{t}x′_{t}) = Y^{2} ln det (I + \frac{1}{a} ∑_{t=1}^{T} x_{t}x′_{t}) .

4.3 Lower bounds I: Proof of Theorem 2

Our stochastic strategy for Nature will be such that x_{t,i} ∈ {0, 1}, for all t = 1, 2, … and i = 1, …, n. First we consider the 1D case (n = 1), where we will have x_{t} = 1, ∀t (it will be easy to generalize to arbitrary n). Without loss of generality we will only consider the case of Y = \frac{1}{2}: the general case can be obtained by a simple rescaling of y_{t}s and θ. It is clear that instead of assuming y_{t} ∈ \{−\frac{1}{2}, \frac{1}{2}\} we can, and will, assume y_{t} ∈ \{0, 1\} (since x_{t} = 1, we can shift θ and y_{t} by \frac{1}{2}); we will see that the best value of θ will satisfy θ ∈ [0, 1].

Nature’s strategy is as follows: first she generates p ∈ [0, 1] from the beta distribution with parameters (A, A), where A is a large positive constant; at trial t she sets y_{t} = 1 with probability p and y_{t} = 0 with probability 1 − p, independently of the previous trials.

Since Nature’s strategy is known, it is easy to find the best, on the average, strategy for Statistician (the Bayesian strategy). The prior density is proportional to

p^{A−1}(1 − p)^{A−1};

therefore, taking k to denote the number of 1s among the first T trials, we obtain that the posterior density is proportional to

p^{k+A−1}(1 − p)^{T −k+A−1}

after the first T trials. Since Nature generates 1 at trial T + 1 with probability

∫_{0}^{1} \frac{p^{k+A}(1 − p)^{T −k+A−1}}{B(k + A, T − k + A)}dp = \frac{B(k + A + 1, T − k + A)}{B(k + A, T − k + A)}

= \frac{Γ(k + A + 1)Γ(T − k + A)/Γ(T + 2A + 1)}{Γ(k + A)Γ(T − k + A)/Γ(T + 2A)} = \frac{k + A}{T + 2A}

(conditional on what has happened in the first T trials) and square loss is a proper scoring rule (see, eg, Dawid [20]), the Bayesian strategy for Statistician will output

p_{T} = \frac{k + A}{T + 2A}

at trial T + 1.

For a fixed p, the expected loss of the Bayesian strategy at trial T + 1 is

E_{p} (p_{T} − y_{T +1})^{2} = E_{p} (p_{T} − p)^{2} + E_{p} (y_{T +1} − p)^{2}

= E_{p} (\frac{k + A}{T + 2A} − p)^{2} + p(1 − p)

= E_{p} (\frac{k + A}{T + 2A} − \frac{pT + A}{T + 2A})^{2} + (p − \frac{pT + A}{T + 2A})^{2} + p(1 − p)

= E_{p} (\frac{k − pT}{T + 2A})^{2} + (\frac{2Ap − A}{T + 2A})^{2} + p(1 − p)

= \frac{T p(1 − p)}{(T + 2A)^{2}} + (\frac{2Ap − A}{T + 2A})^{2} + p(1 − p);

the first equality in this chain follows from the fact that it holds conditionally on the first T trials and the third equality follows from

E_{p} \frac{k + A}{T + 2A} = \frac{pT + A}{T + 2A}.

Therefore, the expected value (for p fixed) of the loss of the Bayesian strategy over the first T trials is

E_{p}L_{T} (Statistician) = ∑_{t=0}^{T −1} (\frac{tp(1 − p)}{(t + 2A)^{2}} + (\frac{2Ap − A}{t + 2A})^{2} + p(1 − p))

= p(1 − p)T + p(1 − p) ln T + O(1).

Averaging over the prior distribution and using

∫ p(1 − p)\frac{p^{A−1}(1 − p)^{A−1}}{B(A, A)} dp = \frac{B(A + 1, A + 1)}{B(A, A)} = \frac{A^{2}}{(2A + 1)(2A)} = \frac{A}{4A + 2},

(35)

we find

EL_{T} (Statistician) = \frac{A}{4A + 2}T + \frac{A}{4A + 2} ln T + O(1).  (36)

Now we find the expected cumulative loss over the first T trials, for a fixed p, of the best expert θ = k/T:

E_{p} ∑_{t=1}^{T} (y_{t} − \frac{k}{T} )^{2} = E_{p} ∑_{t=1}^{T} y_{t}^{2} − 2E_{p} ∑_{t=1}^{T} y_{t} \frac{k}{T} + E_{p}T (k/T)^{2}

= T p − \frac{2}{T} ∑_{t,s} E_{p}(y_{t}y_{s}) + \frac{1}{T} ((pT)^{2} + p(1 − p)T )

= T p − \frac{2}{T} (T^{2} − T)p^{2} − \frac{2}{T} T p + \frac{1}{T} ((pT)^{2} + p(1 − p)T )

= T (p − 2p^{2} + p^{2}) + O(1) = p(1 − p)T + O(1).

Again using (35), we further obtain

E inf_{θ} L_{T} (θ) = E ∑_{t=1}^{T} (y_{t} − \frac{k}{T} )^{2} = \frac{A}{4A + 2}T + O(1).  (37)

Now the statement of Theorem 2 for n = 1 immediately follows from comparison of (36) and (37): for any ϵ > 0 we will be able to take A large enough.

In the case of n > 1 the following stochastic strategy for Nature will satisfy the requirement of Theorem 2. She starts by independently generating n numbers p_{i} ∈ [0, 1], i = 1, …, n, from the beta distribution with parameters (A, A); at trial t she sets x_{t} = (0, …, 0, 1, 0, …, 0), where the only 1 is the ith component of the vector x_{t} and

i = \{ \begin{matrix}n, if t mod n = 0, \\ t mod n, otherwise, \end{matrix}

y_{t} = Y with probability p_{i} and y_{t} = −Y with probability 1 − p_{i}, independently of the previous trials. This construction implies a subtrahend of anY^{2} in the right-hand side of the inequality in the statement of the theorem (anY^{2} is an upper bound on a∥θ∥_{2}^{2}), but we included this subtrahend in the constant C.

4.4 Lower bounds II: Proof of Theorem 3

In this subsection we will prove Theorem 3; Nature will play the strategy described after the statement of the theorem. First let us prove that γ_{T} −y_{T −1} → 0 as T → ∞ (that is, Statistician’s prediction is almost the repetition of the last observed response). After trial T ≫ 1 the observed (x_{t}, y_{t}) are

(1, 1), (c, −1), (c^{2}, 1), …  (38)

if we take x_{T} (resp y_{T}) to be our unit of length for measuring the xs (resp ys); here c = \frac{1}{2}. Let us imagine that the data set (38) is infinite; for large T, this will be a good approximation. The best least-squares approximation y = θx to this data set is determined from the condition

(1 − θ)^{2} + (1 + cθ)^{2} + (1 − c^{2}θ)^{2} + (1 + c^{3}θ)^{2} + … → min .

Differentiating this function in θ and summing the geometrical progressions, we obtain

\frac{1}{1 − c^{2}} θ = \frac{1}{1 + c},

Review of literature 28

which gives θ = 1 − c. After observing x_{T +1} = \frac{1}{c} at the next trial, Statistician will give prediction

γ_{T +1} = \frac{θ}{c} = \frac{1 − c}{c} = 1.

This completes the proof of γ_{T} − y_{T −1} → 0 (T → ∞).

Equations (24) and (25) are now obvious; (26) is also easy to check:

ln (1 + \frac{1}{a} ∑_{t=1}^{T} x_{t}^{2}) = ln (∑_{t=1}^{T} 2^{2(t−1)}) + O(1) = 2T ln 2 + O(1).

4.5 Derivation of the RR and proof of Theorem 4

Recall that the RR estimate was defined as the arg min in (21). First we “derive” the RR prediction showing that it is precisely the mean of the posterior distribution. (This is a well-known fact, but its proof is so simple that we give it here.)

Taking the same prior over θ as before, (27), and associating with the expert θ the probability forecasting system whose prediction at trial t is the Gaussian distribution with mean x′_{t}θ and variance \frac{1}{2η}, we obtain that the posterior distribution is proportional to

exp (−aη∥θ∥_{2}^{2} − ηL_{T} (θ)) ∝ exp (−ηθ′ (aI + ∑_{t=1}^{T} x_{t}x′_{t}) θ + 2η (∑_{t=1}^{T} y_{t}x′_{t}) θ)

(cf (29)). The posterior mean equals the minimum of these expressions; minimizing the first expression, we obtain our original definition of the RR estimate; minimizing the second one,

\frac{∂}{∂θ} (−ηθ′ (aI + ∑_{t=1}^{T} x_{t}x′_{t}) θ + 2η (∑_{t=1}^{T} y_{t}x′_{t}) θ) = 0,

we obtain the RR formula (22).

To prove Theorem 4, it suffices to take η = \frac{1}{8Y^{2}} instead of η = \frac{1}{2Y^{2}} in the proof in Subsection 4.2 (cf Remark 1).

5 Review of literature

The first paper on competitive on-line statistics was, probably, DeSantis et al [22], which performed a competitive analysis of the Bayesian mixing scheme for the log-loss prediction game. Later Littlestone and Warmuth [43] and Vovk [53] introduced an on-line algorithm (called the Weighted Majority Algorithm by the former authors) for the simple prediction game. These two algorithms (the Bayesian mixing scheme and the Weighted Majority Algorithm) were generalized by the AA, proposed in Vovk [52]. The AA has been proven to be optimal in some simple cases (see Haussler et al [33], Vovk [55], Watkins’s theorem stated in [56]). The AA is a member of a wide family of algorithms called “multiplicative weight” or “exponential weight” algorithms.

We call this area “competitive on-line statistics” because of the closeness of its ideology to that of the theory of competitive on-line algorithms (see, eg, [46]). The adjective “competitive” refers to inequalities such as (1) and (2) above (or analogous inequalities for competitive on-line algorithms); in this approach, the goal of the algorithm to perform as well as the best, retrospectively, decision strategy. The adjective “on-line” means that the data ω_{t} (or (x_{t}, y_{t})) arrive sequentially; this is more or less a computer-science analogue of “prequential” in “prequential statistics”.

In the rest of this section we will give a brief review of several selected subareas of competitive on-line statistics (those which are especially closely connected with the material presented in this paper) and, in conclusion, discuss some connections between competitive on-line statistics and more traditional statistics and information theory. Many exciting developments and applications will not be discussed; the interested reader can consult the literature on sleeping experts and World-wide Web applications (see, eg, Freund et al [31], Cohen and Singer [16]), boosting, game theory and linear programming (Freund and Schapire [30, 28, 29]), pruning decision trees (Helmbold and Schapire [35], Pereira and Singer [44], Takimoto et al [49]), etc.

5.1 Competitive on-line regression

First we review the subarea of competitive on-line statistics most closely connected to the rest of this paper, regression with the square loss function.

The competitive approach to regression started, probably, from Foster [26], who considered a variant of the RR procedure. In particular, his Theorem 1 asserts that, in the situation where the response variable takes values in {0, 1}, the examples x_{t} belong to [0, 1]^{n} and the weights are nonnegative and satisfy ∥θ∥_{1} = 1,

L_{T} ≤ L_{T}^{∗} + n ln(n(T + 1)) + 2;

this result is very similar to inequality (19). No lower bounds are given in [26].

Cesa-Bianchi et al [12] performed, under the square loss, a competitive analysis of the standard Gradient Descent Algorithm and Kivinen and Warmuth [40] complemented it by a competitive analysis of a modification of the Gradient Descent, which they call the Exponentiated Gradient Algorithm. The bounds obtained by Cesa-Bianchi et al [12] and Kivinen and Warmuth [40] are of the following type: at every trial T,

L_{T} ≤ cL_{T}^{∗} + O(1),  (39)

where L_{T} is the loss (over the first T trials) of the on-line algorithm, L_{T}^{∗} is the loss of the best (by trial T) linear regression function, and c is a constant, c > 1; specifically, c = 2.25 for the Gradient Descent and c = 3 for the Exponentiated Gradient. (See though Remark 4 below.) These bounds hold under the following assumptions: for the Gradient Descent, it is assumed that the L_{2} norm of the weights and of all data items are bounded by constant 1; for the Exponentiated Gradient, that the L_{1} norm of the weights and the L_{∞} norm of all data items are bounded by 1.

In many interesting cases bound (39) might appear weak. For example, suppose that our comparison class contains a “true” regression function, but its values are corrupted by Gaussian noise (that is, we assume that y_{t} = θ · x_{t} + ξ_{t}, where ξ_{t} are independent N (0, σ^{2}) random variables, σ^{2} > 0); we also assume that ∥θ∥_{1} ≤ 1 and ∥x_{t}∥_{∞} ≤ 1 for all t. The performance of the AAR is given by (19); therefore, the difference L_{T} −L_{T}^{∗} is bounded by a logarithmic function of T. As concerns (39), L_{T}^{∗} will grow linearly in T, and inequality (39) will only bound the difference L_{T} − L_{T}^{∗} by a linear function of T. However, the bounds proven in [12, 40] have some important advantages before our bounds (such as (19)); for example:

⋄ O(1) in (39) depends on the number of parameters n logarithmically in the case of the Exponentiated Gradient Algorithm and does not depend on n at all in the case of Gradient Descent, whereas our bound depends on n linearly.

⋄ Our bounds are not as good as, say, the bound

L_{T} (GD) ≤ 2.25 inf_{θ} (L_{T} (θ) + X∥θ∥_{2}^{2})

([12], Theorem IV.1; the only assumption here is that all ∥x_{t}∥_{2} ≤ X) in the noise-free case where L_{T} (θ) = 0 for some θ.

⋄ The most naive implementation of the AAR would require O(n^{3}) arithmetic operations at every trial. It is easy to see that there are ways to implement it more efficiently; for example, we can use the value A_{t−1}^{−1} of the inverse to A at trial t − 1 to compute its value A_{t}^{−1} at trial t: by the Sherman-Morrison formula ([45], Section 2.10),

A_{t}^{−1} = A_{t−1}^{−1} − \frac{(A_{t−1}^{−1}x_{t}) (A_{t−1}^{−1}x_{t})′}{1 + x′_{t}A_{t−1}^{−1}x_{t}} .  (40)

Therefore, we only need O(n^{2}) arithmetic operations per trial. This is still not as good as for the Gradient Descent Algorithm and Exponentiated Gradient Algorithm: they require only O(n) operations per trial.

It remains to be seen if it is possible to combine the advantages of the AAR, Gradient Descent and Exponentiated Gradient in one algorithm. A step in this direction is done by Azoury and Warmuth [3], who obtained the bound of our Theorem 1 (see Theorem 3.5 in [3]) for an algorithm motivated by the methodology of [12] and [40]. Another approach might be to try the AA with a different prior.

Remark 3 Let us formally verify the above claim that L_{T}^{∗} grows linearly in T. Our model is Y = Xθ + ξ, where Y = (y_{1}, …, y_{T})′ is the observed sequence of responses and X = (x_{1}, …, x_{T})′ is the observed sequence of signals. Without loss of generality we assume that the true value of θ is 0; for simplicity, we consider the 1D case, n = 1. The least squares estimate of θ (ie, the best expert) is

θ̂ = (X′X)^{−1}X′Y

(cf (22)), and so the residual sum of squares is

Y′Y − Y′Xθ̂ = Y′Y − Y′X(X′X)^{−1}X′Y = ξ′ξ − ξ′X(X′X)^{−1}X′ξ

= ∑_{t=1}^{T} ξ_{t}^{2} − \frac{(∑_{t=1}^{T} ξ_{t}x_{t})^{2}}{∑_{t=1}^{T} x_{t}^{2}} .

The minuend of the final expression is the loss suffered by the true regression function, which grows as σ^{2}T (by the law of large numbers); the subtrahend is much smaller by Chebyshev’s inequality: it is non-negative and

E\frac{(∑_{t=1}^{T} ξ_{t}x_{t})^{2}}{∑_{t=1}^{T} x_{t}^{2}} = σ^{2}.

Notice that the Gaussian noise model violates the assumption |y_{t}| ≤ Y, but this does not matter since we know in advance that ∥x_{t}∥_{∞} ≤ 1 and ∥θ∥_{1} ≤ 1.

Remark 4 Cesa-Bianchi et al [12] and Kivinen and Warmuth [40] also construct some “semi-on-line” algorithms; such algorithms must be a priori given a good upper estimate K on the loss of the best regression function. For such algorithms, they derive bounds of the type L_{T} ≤ L_{T}^{∗} + O(\sqrt{K}). Using the usual “doubling trick” (Cesa-Bianchi et al [10]), it is possible to obtain bounds of the type L_{T} ≤ L_{T}^{∗} + O(\sqrt{L_{T}^{∗}}) in the pure on-line setting (see Cesa-Bianchi et al [12], Theorem IV.4). In our example of a true regression function corrupted by Gaussian noise, the difference L_{T} − L_{T}^{∗} will be bounded by a linear function of \sqrt{T}, which is still worse than (19) (even though the AA is purely on-line and does not require a priori estimates of L_{T}^{∗}).

Yamanishi [64] analyzed the application of the AA to a wide class of decisions pools and obtained loss bounds analogous to (19) in a very general setting. One of the decision pools (Examples 1 and 9 of [64]) is the following: the weights θ and examples x_{t} are known to belong to the unit L_{2}-ball in IR^{n} and all their components are nonnegative; responses y_{t} are known to belong to [0, 1]. Taking the uniform distribution as the prior for the AA, Yamanishi obtained the following analogue of our inequality (19):

L_{T} (AA) ≤ inf_{θ} (L_{T} (θ)) + \frac{n}{4} ln \frac{2T n}{π} + \frac{1}{2} ln \frac{π^{n/2}}{Γ(1 + n/2)} + o(1).  (41)

Comparing this to (21) with Y = \frac{1}{2} (recall that Yamanishi assumes y_{t} ∈ [0, 1]), we can see that the coefficients before the leading term ln T match; it should be borne in mind that (41) is a special case of a much more general result (Theorem 2 in [64]; it first appeared in Yamanishi [63]). In the more recent paper [65] Yamanishi proves non-asymptotic results of the same kind and proves lower bounds matching his upper bounds.

Forster [25] has discovered a surprising property of the AAR predictions: according to his Theorem 1, they minimize the maximal extra loss, compared to the best expert, that might be suffered in trial T. He also gives a simplified proof of our Theorem 1.

Feder and Singer [24] obtain results very similar to ours in the case of linear autoregression with square loss. In the case where the order p of autoregression is known, they obtain the bound

L_{T} (Universal Algorithm) ≤ inf_{θ} L_{T} (θ) + 4A^{2}p ln T + O(1)  (42)

(this bound follows from Theorem 2 in [24]; Theorem 1 has a similar form), where A is the a priori bound on the values taken by y_{t} (which is to be predicted using the values y_{t−1}, …, y_{t−p}) and O(1) stays bounded as T → ∞. Notice that (42) involves an extra factor of 4 (familiar from Subsection 3.4) before ln T as compared to (21). This must have happened because they used the posterior mean as a substitution function (see the discussion in Subsection 3.4) rather than following the more opportunistic approach of the AA.

A distinctive feature of the competitive approach to regression is that one does not make any assumptions about stochastic properties of the data-generating mechanism; for example, in Section 3 our only assumption about the data was that |y_{t}| ≤ Y, ∀t. In some situations (if the data were generated by a partially known stochastic mechanism) this feature is a disadvantage, but often it will be an advantage.

The assumption that y_{t} are bounded is natural in many applications (the problem of classification, in which always y_{t} ∈ {−1, 1}, predicting a student’s score ranging from 0% to 100%, etc), but in some other applications it might look artificial. It would be very interesting to relax or remove this assumption; some ideas on “tuning” the lower and upper bounds a and b can be found in Vovk and Gammerman [57].

5.2 Tracking the best expert

So far we have been interested in competing against the best linear regressor y = θ · x; the components of θ are some fixed weights. Paper [37] by Herbster and Warmuth considers the case where θ is allowed to (slowly) change over time. This is a special case of a more general problem of tracking the best expert, which originated in Littlestone and Warmuth [43] and was further studied by, among others, Herbster and Warmuth [36], Auer and Warmuth [2], Vovk [56]. In the problem of tracking the best expert we start with a pool of “basic” decision strategies. It is known that the strategies in the pool are too inflexible to attain a good performance, but we expect that first one of the strategies will work well, then another, etc, hoping that we will only rarely have to switch between the strategies. Two main approaches to the problem of tracking the best expert are:

⋄ We can try to modify the known merging algorithms to make them more adaptive; this approach was used in, eg, [36].

⋄ We can construct the pool of “superstrategies” (an example of a superstrategy: start in the morning following strategy 3, at 1:15 pm switch to strategy 1 and at 5 pm switch to strategy 2) and then apply the AA or another “static” merging algorithm; this approach was used in [56].

Typical bounds for the total on-line loss of a merging algorithm tracking the best expert are the sum of the loss of the best “switching schedule” between the basic strategies plus the total cost for switching between the experts (say, a constant times the number of switches) plus a small overhead (such as the logarithm of the number of experts). The work on tracking the best expert has been applied to predicting disk idle times [34] and load balancing problems [6]; there is no doubt that this work will find further important applications.

5.3 Bandit problems and reinforcement learning

We already mentioned that the philosophy of competitive on-line statistics, as described above, only “works” when Nature is oblivious to Statistician’s decisions (ω_{T} does not depend on γ_{1}, …, γ_{T −1}): if Nature is not oblivious, it is not longer possible to interpret inequality (1) as saying that Statistician performs not much worse than the best of the decision strategies: if we had followed strategy θ we would perhaps have observed a different sequence of outcomes. The assumption that Nature is oblivious is always justified when γ_{t} are predictions (say, the atmosphere does not care about our predicting rain), but it can also be justified for decisions different from predictions, such as portfolio selection by a small investor (see Subsection 2.5).

The situation is changing now: eg, papers [1] and [9] present competitive on-line results for bandit problems, in which Nature by no means is oblivious. It turns out that it is even possible to study the exploration—exploitation tradeoff in the competitive on-line framework.

5.4 Predictive complexity

A recent application of the Aggregating Algorithm is to generalize the notion of Kolmogorov complexity (see, eg, Li and Vitanyi [42]). The idea is to apply the AA (or some other merging algorithm) to the “universal decision pool” containing every computable decision strategy (such a pool can be constructed from a universal Turing machine). The loss of the resulting “decision strategy” (actually it will be a decision strategy only in a generalized sense) on a data sequence x is called the predictive complexity of x. When applied to the logloss game, this leads to a variant of Kolmogorov complexity. As well as being a fundamental concept per se, the notion of predictive complexity allows us to define the notion of randomness for prediction games different from the log-loss game; for details, see [50]. (Though even the standard notion of logloss randomness seems to be grossly under-used presently: see [60].) Another application is to generalizing the MDL principle to games different from the log-loss one: see [57]. For further information about predictive complexity the reader can consult Kalnichkan [39, 38] and Vovk and Watkins [58].

5.5 Statistics and information theory

It is clear from Subsection 2.2 that the log loss function plays a fundamental role in probability theory and statistics (esp Bayesian statistics); the role of the log loss function is as prominent in information theory, where it is interpreted as the code length^{4}. To make the connections between the usual statistical notions, such as log-likelihood, maximum likelihood estimate (MLE) and observed Fisher information, and competitive on-line statistics clearer, we will explain how they can be generalized to different loss functions.

Let μ be a prior probability density in Θ and η > 0 be some learning rate; as usual, we set β = e^{−η}. As described earlier, when Statistician can predict with “pseudo-predictions”, we will have at each trial

L_{T} (Statistician) = log_{β} ∫ β^{L_{T} (θ)}μ(θ)dθ.

When Statistician has to make permitted predictions γ ∈ Γ, we will instead obtain

L_{T} (Statistician) ≤ c(η) log_{β} ∫ β^{L_{T} (θ)}μ(θ)dθ.  (43)

The function L(θ) = L_{T} (θ) is a generalization of the minus log-likelihood function in statistics. Let us for simplicity consider only the 1D case where Θ ⊆ IR. The two most important characteristics of the “minus log-likelihood function” L(θ) are the maximum likelihood estimate

θ̂ = arg min_{θ} L(θ)

and the observed Fisher information

ĵ = L′′(θ̂)

(the usual Fisher information is the expectation of the observed Fisher information). The functions θ̂ and ĵ have a long history in statistics; eg, it was Fisher’s idea (Dawid [21], Section 6) that to make the maximum likelihood estimator θ̂ sufficient it should be complemented by the “ancillary statistic” ĵ.

4This is true for lossless compression; the competitive on-line theory of lossy compression would require more sophisticated loss functions.

Let us simplify (43) under “regularity conditions” (without specifying them precisely). Function β^{L(θ)} rapidly vanishes outside the interval centered at θ̂ of length about 1/\sqrt{ĵ} (because

L(θ) − L(θ̂) ≈ \frac{1}{2}ĵ(θ − θ̂)^{2}

near θ̂), but inside that interval it is close to β^{L(θ̂)}. So we obtain from (43):

L(Statistician) ≤ c(η) log_{β} (β^{L(θ̂)}μ(θ̂)/\sqrt{ĵ}) + const,

ie,

L(Statistician) ≤ c(η)L(θ̂) + a(η) ln \frac{\sqrt{ĵ}}{μ(θ̂)} + const.  (44)

(Using Laplace’s approximation, the constant const can be evaluated to a(η) ln \sqrt{2π}.)

In many cases ĵ will be of the order of magnitude T, the ordinal number of the trial. Therefore, (44) gives an O(log T) “overhead” for perfectly mixable games; a similar logarithmic term, n ln(T + 1), occurs in (19). These terms are analogous to the term \frac{n}{2} ln T occurring in the analysis of the log-loss game and its generalizations, in particular in Rissanen’s theory of stochastic complexity ([48]; extended to more general loss functions by Yamanishi [64]), Wallace’s theory of minimum message length (Wallace and Boulton [61], Wallace and Freeman [62]), minimax regret analysis (Barron and Xie [4]).

We showed above that our upper bound for the problem of regression is in some sense optimal; viz, we have shown that the coefficient n before n ln(T + 1) in (19) cannot be improved. Related results are Rissanen’s [48] proof that his term \frac{n}{2} ln T is optimal.

In traditional statistics it is usually assumed that the outcomes ω_{t} are generated by some true distribution, and in some papers the log loss is averaged with respect to the true distribution, which naturally leads to considering the Kullback–Leibler distance: see Clarke and Barron [13, 14]. It is natural to assume that the results of those papers can be extended to the Kullback–Leibler game (see Subsection 2.5 above); as proven in Subsection 2.5, the AA for this game is exactly the Bayesian mixing rule, which was considered in [13, 14]. In the recent paper by Clarke and Dawid [15] no assumptions are made about true distributions; it is entirely competitive on-line.

Competitive on-line statistics is concerned with, of course, the on-line performance of statistical procedures. Many procedures, like the RR, can be used in both batch and on-line setting. Dawid’s [19] prequential approach to statistics recommends using on-line performance as a measure of quality of batch algorithms; therefore, competitive on-line results also provide a justification for the use of the corresponding algorithms in the batch setting (provided the philosophy of prequential statistics is accepted).

Discussion 36

6 Discussion

It is not completely clear yet how far competitive on-line statistics can be developed; some of its limitations are well understood and others still wait to be disclosed. One serious limitation is that for some interesting games (especially those with non-compact Ω and Γ) the constants c(η) and a(η) are infinite; as we already mentioned, they become infinite if we remove the assumption that the response variable is bounded in the square-loss game.^{5} Another limitation is that Nature is often implicitly assumed to be oblivious. However, the advantages of competitive on-line statistics turned out to be clear enough to generate a lot of interesting research in computational learning community, as described in the previous section. (And, as we mentioned there, there have been attempts to alleviate these limitations.)

The main ideas of competitive on-line statistics can be summarized as follows. The basic “recipe” is:

1. Set a complete protocol of the interaction between the statistician and her environment, including the game (Ω, Γ, λ) to be played and possible side information (such as the attributes of the object to be classified).

2. Choose the “yardstick class” {ξ_{θ} | θ ∈ Θ} of decision strategies for the statistician.

3. Decide on the prior probability distribution P_{0}(dθ) in Θ.

4. Choose a “learning rate” η ≥ 0.

5. Find the “Bayesian mixture” of the decision strategies in the yardstick class, with the learning rate η and the weights given by the prior P_{0}.

6. When making a decision, replace the “pseudodecision” generated by the Bayesian mixture with a real prediction.

(When merging algorithms different from the AA are used, the last two steps can be combined.)

Remark 5 There are two main modes of application of merging algorithms such as the AA:

1. Apply the merging algorithm directly to the decision pool.

2. Apply the merging algorithm “on the top” of another algorithm (eg, merging Maximum Likelihood predictions made by polynomials of different degrees).

5In such situations one might want to replace the minimax approximation method used by the AA by something different, say to choose an action with the smallest average wr to the distribution Q(dω) ∫_{Θ} β^{λ(ω,ξ(θ))}P_{t−1}(dθ) in Ω, where Q is some prior distribution in Ω (say, uniform, if it exists); this method is, like the AA, a generalization of both the Weighted Majority Algorithm and the Bayesian mixing scheme. Related ideas can be found in Grünwald [32].

The second option can be applied as soon as some method encounters the problem of overfitting.

Now we will briefly discuss how to implement the steps of the basic recipe, starting with how to choose the prior. In view of inequalities such as (13), a natural idea for choosing μ is: the bigger the better. It would be ideal to take Levin’s “universal enumerable semimeasure” M (see Li and Vitanyi [42], 4.3 and 4.4; M is also known as a priori semimeasure) as the prior if it were computable. Since under this choice we have

M(dθ) ≥ ϵP_{0}(dθ)2^{−K(P_{0})},

where ϵ is a universal constant and K(P_{0}) is the prefix complexity of any prior P_{0}, the right-hand side of (13) will increase by at most

c(η) log_{β} (ϵ2^{−K(P_{0})}) = c(η) (\frac{C}{η} + \frac{K(P_{0})}{η} ln 2)

(C is a universal constant) when we use M in place of P_{0}. Following Rissanen [47], we can instead take “computable approximations” to the universal enumerable semimeasure. In that paper Rissanen gave a relatively rigorous interpretation of Jeffreys’s idea of “noninformative priors” (ie, priors reflecting Statistician’s ignorance). He suggested the prior

P_{0}\{θ\} = \frac{1}{θ ln^{∗} θ}

on the integers; we could also use the prior density μ on [0, 1] that is uniform in the middle, of the type

μ(θ) = \frac{1}{θ ln^{∗}(1/θ)}

near the left end, and of the type

μ(1 − θ) = \frac{1}{θ ln^{∗}(1/θ)}

near the right end. Another popular approach to choosing the prior is to take the “optimal” P_{0}, typically according to some minimax criterion of optimality; see, eg, Clarke and Barron [14], Barron and Xie [4], Freund [27].

A difficult question is how to choose the loss function. In some situations we might have a clear “true” loss function (when we can precisely evaluate consequences of our predictions); in other situations we do not know where our predictions will be used. In the former, “decision” situations, we are already given a loss function and the problem is to study its properties (is it perfectly mixable? what is the mixability curve?); in the latter, “inference” situations, we can use some conventional loss functions like the square loss.

As concerns choosing the learning rate η, in the situation where our decision pool is finite or countable a natural (though vague) principle [52] is:

REFERENCES 38

⋄ if we expect that the performance of some strategy with very big weight is not very bad, η should be close to 0 (we should learn well, even if slowly);

⋄ if we expect that some strategy with not very small weight performs very well, η should be big (we should learn quickly, even if badly).

Sometimes we will want to make η “infinitesimal”, without actually setting η = 0 (eg, in the case of the absolute loss function, where c(η) → 1 as η → 0); some way of doing this is described in Cesa-Bianchi et al [10]. Cesa-Bianchi et al [11] discuss using a prior distribution in the set of possible values of η (it would be natural to take an approximation to the “universal prior”). In the case of perfectly mixable games the most natural thing to do is to take the largest η such that c(η) = 1 (in other words, to minimize a(η) under the constraint c(η) = 1).

In conclusion we will place the approach of competitive on-line statistics in the more general framework of the theory of decision making under uncertainty. There are several popular principles of decision making under uncertainty, such as Laplace’s principle, Wald’s minimax principle and Savage’s minimax regret principle, but all of them have been criticized as arbitrary. Competitive on-line statistics is based on the following version of the minimax regret principle: a decision strategy is acceptable if its regret (in the simplest case, the loss of the aggregating strategy minus the loss of the best decision strategy in the pool) is always small (according to (1) the maximum regret of the AA is small if there are not too many experts). This restricted version of the minimax regret principle is far less objectionable than the general principle.

Acknowledgments

I am grateful to Phil Dawid, Meir Feder, Mark Herbster, Kostas Skouras, Manfred Warmuth, and Kenji Yamanishi for useful discussions and illuminating comments (and to Manfred also for finding a mistake in an earlier draft).

This work was partially supported by EPSRC through grants GR/L35812 (“Support Vector and Bayesian learning algorithms”), GR/M14937 (“Predictive complexity: recursion-theoretic variants”), and GR/M16856 (“Comparison of Support Vector Machine and Minimum Message Length methods for induction and prediction”).

References

[1] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 322–331, 1995.

[2] Peter Auer and Manfred K Warmuth. Tracking the best disjunction. Machine Learning, 32:127–150, 1998.

[3] Katy S Azoury and Manfred K Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. Manuscript. An extended abstract appeared in Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence, pages 31–40, San Francisco, CA, 1999. Morgan Kaufmann.

[4] Andrew R Barron and Q Xie. Asymptotic minimax regret for data compression, gambling, and prediction. Technical report, Statistics Department, Yale University, 1996. Submitted to IEEE Trans on Inform Theory.

[5] Edwin F Beckenbach and Richard Bellman. Inequalities. Springer, Berlin, 1965.

[6] Avrim Blum and Carl Burch. On-line learning and the metrical task system problem. In Proceedings of the 10th Annual Conference on Computational Learning Theory, pages 45–53, New York, 1997. Assoc Comput Mach. Also published in Mach Learning.

[7] Avrim Blum and Adam Kalai. Universal portfolios with and without transaction costs. In Proceedings of the 10th Annual Conference on Computational Learning Theory, pages 309–313, New York, 1997. Assoc Comput Mach.

[8] A A Borovkov. Mathematical statistics (in Russian). Nauka, Moscow, 1984.

[9] Nicolò Cesa-Bianchi and P Fischer. Finite-time regret bounds for the multiarmed bandit problem. In 5th International Conference on Machine Learning, pages 100–108. Morgan Kaufmann, 1998.

[10] Nicolò Cesa-Bianchi, Yoav Freund, David Haussler, David P Helmbold, Robert E Schapire, and Manfred K Warmuth. How to use expert advice. Journal of the Association for Computing Machinery, 44:427–485, 1997.

[11] Nicolò Cesa-Bianchi, David P Helmbold, and Sandra Panizza. On Bayes methods for on-line boolean prediction. Algorithmica, 22:112–137, 1998.

[12] Nicolò Cesa-Bianchi, Philip M Long, and Manfred K Warmuth. Worst-case quadratic loss bounds for on-line prediction of linear functions by gradient descent. IEEE Trans Neural Networks, 7:604–619, 1996.

[13] Bertrand Clarke and Andrew R Barron. Information theoretic asymptotics of Bayes methods. IEEE Trans on Inform Theory, 36:453–471, 1990.

[14] Bertrand Clarke and Andrew R Barron. Jeffreys’ prior is asymptotically least favourable under entropy risk. J Statist Planning and Inference, 41:37–60, 1994.

[15] Bertrand Clarke and A Philip Dawid. On-line prediction with experts under a log-scoring rule. Manuscript, 1999.

[16] William W Cohen and Yoram Singer. Context-sensitive learning methods for text categorization. In SIGIR: Proceedings of the 19th International Conference on Research and Development in Information Retrieval, 1996.

[17] T Cover. Universal portfolios. Mathematical Finance, 1:1–29, 1991.

[18] T Cover and E Ordentlich. Universal portfolios with side information. IEEE Trans Inform Theory, 42:348–363, 1996.

[19] A Philip Dawid. Statistical theory: the prequential approach. J R Statist Soc A, 147:278–292, 1984.

[20] A Philip Dawid. Probability forecasting. In S Kotz, N L Johnson, and C B Read, editors, Encyclopedia of Statistical Sciences, volume 7, pages 210–218. Wiley-Interscience, New York, 1986.

[21] A Philip Dawid. Fisherian inference in likelihood and prequential frames of reference (with discussion). J R Statist Soc B, 53:79–109, 1991.

[22] A DeSantis, G Markowsky, and M N Wegman. Learning probabilistic prediction functions. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 110–119, Los Alamitos, CA, 1988. IEEE Comput Soc.

[23] N R Draper and H Smith. Applied Regression Analysis. Wiley, New York, 2nd edition, 1981.

[24] Meir Feder and Andrew C Singer. Universal data compression and linear prediction. In Proceedings of the 1998 IEEE Data Compression Conference, 1998.

[25] Jürgen Forster. On relative loss bounds in generalized linear regression. Manuscript, 1999.

[26] D P Foster. Prediction in the worst case. Ann Statist, 19:1084–1090, 1991.

[27] Yoav Freund. Predicting a binary sequence almost as well as the optimal biased coin. In Proceedings of the 9th Annual Conference on Computational Learning Theory, pages 89–98, New York, 1996. Assoc Comput Mach.

[28] Yoav Freund and Robert E Schapire. Game theory, on-line prediction and boosting. In Proceedings, 9th Annual Conference on Computational Learning Theory, pages 325–332, New York, 1996. Assoc Comput Mach.

[29] Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Manuscript, 1997.

[30] 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:119–139, 1997.

[31] Yoav Freund, Robert E Schapire, Yoram Singer, and Manfred Warmuth. Using and combining predictors that specialize. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, New York, 1997. Assoc Comput Mach.

[32] Peter Grünwald. The Minimum Description Length principle and reasoning under uncertainty. PhD thesis, Institute for Logic, Language and Computation, Universiteit van Amsterdam, 1998.

[33] David Haussler, Jyrki Kivinen, and Manfred K Warmuth. Tight worst-case loss bounds for predicting with expert advice. Technical Report UCSC-CRL-94-36, University of California at Santa Cruz, revised December 1994. Short version in Paul Vitányi, editor, Computational Learning Theory, Lecture Notes in Computer Science, volume 904, pages 69–83, Springer, Berlin, 1995.

[34] David P Helmbold, D D E Long, and B Sherrod. A dynamic disk spin-down technique for mobile computing. In Proceedings of the 2nd Annual ACM International Conference on Mobile Computing and Networking, 1996.

[35] David P Helmbold and Robert E Schapire. Predicting nearly as well as the best pruning of a decision tree. Machine Learning, 27:51–68, 1997.

[36] Mark Herbster and Manfred Warmuth. Tracking the best expert. In Proceedings of the 12th International Conference on Machine Learning, pages 286–294. Morgan Kaufmann, 1995. To appear in Machine Learning.

[37] Mark Herbster and Manfred Warmuth. Tracking the best regressor. In Proceedings of the 11th Annual Conference on Computational Learning Theory, pages 24–31. Assoc Comput Mach, 1998.

[38] Yuri Kalnichkan. General linear relations among different types of predictive complexity. In Proceedings of the 1990 Annual Conference on Algorithmic Learning Theory, 1999. To be published.

[39] Yuri Kalnichkan. Linear relations between square-loss and Kolmogorov complexity. In Proceedings of the 12th Annual Conference on Computational Learning Theory, New York, 1999. Assoc Comput Mach.

[40] Jyrki Kivinen and Manfred K Warmuth. Exponential Gradient versus Gradient Descent for linear predictors. Inform Computation, 132:1–63, 1997.

[41] Jyrki Kivinen and Manfred K Warmuth. Averaging expert predictions. Manuscript, 1999.

[42] Ming Li and Paul Vitányi. An introduction to Kolmogorov complexity and its applications. Springer, New York, 2nd edition, 1997.

[43] Nick Littlestone and Manfred K Warmuth. The Weighted Majority Algorithm. Inform Computation, 108:212–261, 1994.

[44] F Pereira and Yoram Singer. An efficient extension to mixture techniques for prediction and decision trees. In Proceedings, 10th Annual Conference on Computational Learning Theory, pages 114–121. Assoc Comput Mach, 1997.

[45] William H Press, Brian P Flannery, Saul A Teukolsky, and William T Vetterling. Numerical Recipes in C. Cambridge University Press, Cambridge, 1992.

[46] P Raghavan (ed). Special issue on competitive on-line algorithms. Algorithmica, 11:1–91, 1994.

[47] Jorma Rissanen. A universal prior for integers and estimation by minimum description length. Annals of Statistics, 11:416–431, 1983.

[48] Jorma Rissanen. Stochastic complexity (with discussion). Journal of Royal Statistical Society B, 49:223–239 and 252–265, 1987.

[49] Eiji Takimoto, Akira Maruoka, and Volodya Vovk. Predicting nearly as well as the best pruning of a decision tree through dynamic programming scheme. Submitted for publication, 1998.

[50] Volodya Vovk. Probability theory for the Brier game. Accepted for publication in Theoretical Computer Science. Preliminary version in Ming Li and Akira Maruoka, editors, Algorithmic Learning Theory, Lecture Notes in Computer Science, volume 1316, pages 323–338, 1997. Full version: Technical Report CSD-TR-97-09, Department of Computer Science, Royal Holloway, University of London, revised February 1998.

[51] Volodya Vovk. On a randomness criterion. Soviet Mathematics Doklady, 35:656–660, 1987.

[52] Volodya Vovk. Aggregating strategies. In M Fulk and J Case, editors, Proceedings of the 3rd Annual Workshop on Computational Learning Theory, pages 371–383, San Mateo, CA, 1990. Morgan Kaufmann.

[53] Volodya Vovk. Universal forecasting algorithms. Information and Computation, 96:245–277, 1992.

[54] Volodya Vovk. Competitive on-line linear regression. In M I Jordan, M J Kearns, and S A Solla, editors, Advances in Neural Information Processing Systems, pages 364–370, Cambridge, MA, 1998. MIT Press.

[55] Volodya Vovk. A game of prediction with expert advice. J Comput Syst Sci, 56:153–173, 1998.

[56] Volodya Vovk. Derandomizing stochastic prediction strategies. Machine Learning, 35(3):247–282, 1999.

[57] Volodya Vovk and Alex Gammerman. Complexity Approximation Principle. Computer Journal, 42, 1999. 318–322.

[58] Volodya Vovk and Chris J H C Watkins. Universal portfolio selection. In Proceedings of the 11th Annual Conference on Computational Learning Theory, pages 12–23, New York, 1998. Assoc Comput Mach.

[59] Volodya Vovk. Competitive on-line statistics. In Bulletin of the International Statistical Institute. The 52nd Session, Proceedings, volume LVIII, book 1, pages 231–234, 1999.

[60] Volodya Vovk and Alex Gammerman. Statistical applications of algorithmic randomness. In Bulletin of the International Statistical Institute. The 52nd Session, Contributed Papers, volume LVIII, book 3, pages 469–470, 1999.

[61] Chris S Wallace and D M Boulton. An information measure for classification. Computer Journal, 11:185–195, 1968.

[62] Chris S Wallace and P R Freeman. Estimation and inference by compact coding (with discussion). J R Statist Soc B, 49:240–265, 1987.

[63] Kenji Yamanishi. Generalized stochastic complexity and its applications to learning. In Proceedings of the 1994 Conference on Information Science and and Systems, volume 2, pages 763–768, 1994.

[64] Kenji Yamanishi. A decision-theoretic extension of stochastic complexity and its applications to learning. IEEE Trans Inform Theory, 20:100–114, 1998.

[65] Kenji Yamanishi. Minimax relative loss analysis for sequential prediction aalgorithms using parametric hypotheses. In Proceedings of the 11th Annual Conference on Computational Learning Theory, pages 32–43, New York, 1998. Assoc Comput Mach.

RÉSUMÉ

Cet article décrit une approche nouvelle à modelage statistique combinant les techniques mathematiques de statistique Bayesienne avec la philosophie de la theorie de algorithmes compétitives en ligne. Dans cette approche, qui émergeait durant le décennie dernière dans l’informatique, on ne suppose pas que les données sont produites par une mécanisme stochastique ; au lieu de cela, il est prouvé que les procédures statistiques compétitives en ligne atteignent toujours (et non, par exemple, avec haute probabilité) quelque but desirable (explicitant la bonne performance sur les données réeles). Cet article passe en revue des plusieurs résultats dans cette domaine ; son matériel neuf comprend les preuves pour la performance de le “algorithme agrégeant” dans le problème de la régression linéaire avec la perte carrée.