Relative Loss Bounds for On-Line Density Estimation with the Exponential Family of Distributions.
We consider on-line density estimation with a parameterized density from the exponential family. The on-line algorithm receives one example at a time and maintains a parameter that is essentially an average of the past examples. After receiving an example the algorithm incurs a loss, which is the negative log-likelihood of the example with respect to the current parameter of the algorithm. An off-line algorithm can choose the best parameter based on all the examples. We prove bounds on the additional total loss of the on-line algorithm over the total loss of the best off-line parameter. These relative loss bounds hold for an arbitrary sequence of examples. The goal is to design algorithms with the best possible relative loss bounds. We use a Bregman divergence to derive and analyze each algorithm. These divergences are relative entropies between two exponential distributions. We also use our methods to prove relative loss bounds for linear regression.
Introduction
A main focus of statistical decision theory consists of the following:
After receiving statistical information in the form of sampling data,
the goal is to make decisions that minimize a loss or an expected loss
with respect to an underlying distribution that is assumed to model the
data. This distribution is often dened in terms of certain parameters.
The statistical decisions depend on the specic values chosen for the
parameters. Thus, for statistical decision theory, there are three important
elements: parameters and the values they can take, decisions, and
loss functions that evaluate the decisions.
y An extended abstract appeared in UAI  99 (AW99)
z Supported by NSF grant CCR 9700201 and CCR-9821087
c
2000 Kluwer Academic Publishers. Printed in the Netherlands.
K. S. Azoury and M. K. Warmuth
In Bayesian statistical decision theory, a prior distribution on the parameters
of the data distribution is an additional important element of
information that is needed to assess decision performance. As a simple
case, suppose we are given a sample of T data points fx 1
(also referred to as T examples), and assume that the examples were
independently generated by a Gaussian with an unknown mean and
a known variance. One wants to nd a parameter setting (here the
mean) that minimizes the expected loss on a new example that is drawn
from the same data distribution. In the Bayesian framework, a prior
distribution on the mean would also enter into the decision making
process.
In the context of learning theory, this setup, Bayesian or not, would
be described as a batch or o-line learning model, since all the examples
are given to the learner ahead of time and the decisions are made based
on the information from the entire data set.
In this paper, we focus on on-line learning models. As with o-line
learning, we have the same fundamental elements: parameters, deci-
sions, and loss functions. The dierence, however, is that the examples
are given to the learner one at a time. Thus, on-line learning is naturally
partitioned into trials, where in each trial one example is processed. A
trial proceeds as follows. It begins with a current parameter setting
(hypothesis). Then the next example is presented and the learner or
the on-line algorithm incurs a loss. The loss is a function of this most recent
example and the current parameter setting. Finally, the algorithm
updates its parameter setting and a new trial begins.
In the context of on-line learning, the decisions are the parameter
updates of the learner. The goal is to design on-line learning algorithms
with good bounds on their total loss. Clearly, there cannot be meaningful
bounds on the total loss of an on-line algorithm that stand alone
and also hold for an arbitrary sequence of examples. However, in the
on-line learning literature, a certain type of \relative" loss bound is
desirable and has been used successfully. The term \relative" means
that there is a comparison to the best parameter chosen o-line after
seeing the whole batch of T examples. The parameter space is called
the comparison class. The relative loss bounds quantify the additional
total loss of the on-line algorithm over the total loss of the best o-
line parameter (comparator). Since the on-line learner does not see the
sequence of examples in advance, the additional loss (sometimes called
regret) is the price of hiding the future examples from the learner.
In this paper we design and motivate on-line algorithms and their
parameter updates so that they utilize the available information in the
best possible manner and lead to good relative loss bounds. We focus on
Relative Loss Bounds 3
two types of learning problems: on-line density estimation and on-line
regression.
For density estimation, the on-line algorithm receives a sequence of
unlabeled examples or data vectors fx 1 g. At the start of
the learner has a current parameter setting  t
which is used to predict the next example x t . After making a predic-
tion, the algorithm receives the example x t and incurs a loss L(
Then the algorithm updates its parameter setting to  t+1 . In con-
trast, on-line regression problems receive a labeled sequence of examples
are called instances and
the y t are the labels. In trial t, the learner starts with the current
parameter  t and receives the instance x t . The learner then makes a
prediction
y t for the label y t . This prediction depends on  t and x t .
A loss L( incurred and the parameter is updated to  t+1 .
For both types of problems, density estimation and regression, we use
the abbreviated notation L t ( t ) to denote the loss incurred in trial t.
The subscript t indicates the dependence on the example presented in
trial t. The total loss of the on-line algorithm is
and the
total loss of the best o-line (batch) parameter B is
a charge for the \size" of B . Relative loss bounds give upper bounds
on the dierence between the two total losses.
We prove relative loss bounds for density estimation when the underlying
model is a member of the exponential family of distributions
and also for on-line linear regression. We consider two algorithms. The
rst algorithm is called the Incremental O-line Algorithm. It predicts
(i.e., chooses its parameter) as the best o-line algorithm would have
predicted based on the examples seen so far. The second algorithm
is called the Forward Algorithm. This algorithm is called \forward"
because it uses a guess of a future example and the corresponding
future loss when forming its prediction. It is motivated by Vovk's work
on linear regression.
Our relative loss bounds for both algorithms grow logarithmically
with the number of trials T . The motivation for the parameter updates
has a Bayesian probabilistic interpretation. However, the relative loss
bounds we prove hold for an arbitrary (or worst-case) sequence of ex-
amples. A key element in the design and analysis of the on-line learning
algorithms is a generalized notion of distance called the Bregman diver-
gence. This divergence can be interpreted as a relative entropy between
two exponential distributions.
4 K. S. Azoury and M. K. Warmuth
Outline
The rest of this paper is organized as follows. In Section 2, we present a
brief overview of previous work. In Section 3, we dene Bregman divergences
and give the relevant background for the exponential family of
distributions. We show that relative entropies between two exponential
distributions (Ama85) are special Bregman divergences. We conclude
this section by listing some basic properties of Bregman divergences.
In Section 4, we introduce the Incremental O-line Algorithm in a
general setting and then apply this algorithm to the problem of density
estimation with the exponential family and to linear regression. We give
a number of relative loss bounds for specic examples.
In Section 5, we dene and motivate the Forward Algorithm, which
can be seen as a generalization of the Incremental O-line Algorithm.
Again, we apply this algorithm to density estimation with the exponential
family. For the case of linear regression, we reprove the relative
loss bounds obtained by Vovk (Vov97). Our proofs are more concise.
An alternate simple proof for the \forward" linear regression algorithm
is given in (For99).
In Section 6, we brie
y discuss an alternate method developed by
Vovk for proving relative loss bounds that uses integration over a generalized
posterior and discuss the advantages of our methods. Finally, we
conclude (Section 7) with a discussion of a number of open problems.
2. Overview of previous work
The method of proving bounds on the additional total loss of an on-line
algorithm over the total loss of the the best parameter in a comparison
class essentially goes back to the work of the Blackwell (Bla56)
and Hannnan (Han57). They investigated such bounds in the context
of game theory where the comparison class consists of all mixture
strategies. Later Cover (Cov91) proved such bounds in the context
of mathematical nance. He used the comparison class of all constant
rebalanced portfolios.
The research of this paper is rooted in the study of relative loss
bounds for on-line learning algorithms of the computational learning
theory community. Even though these bounds may underestimate
the performance on natural data, they have been used as a powerful
yardstick for analyzing and comparing on-line algorithms. In the
computational learning theory community this line of research was
initiated by Littlestone with the discovery of the Winnow algorithm
(Lit88). Littlestone also pioneered a style of amortized analysis for
Relative Loss Bounds 5
proving relative loss bounds which use certain divergence functions as
potential functions. Winnow is designed for disjunctions as the comparison
class and the total number of mistakes is used as the loss.
The next wave of on-line algorithms were designed for a nite set
of experts as a comparison class and a wide range of loss functions
algorithms were developed
for the on-line linear least squares regression, i.e., when the
comparison class consists of linear neurons (linear combination of ex-
perts) (LLW95; CBLW96; KW97). This work has been generalized to
the case where the comparison class is the set of sigmoided linear neurons
(HKW95; KW98). Also starting with Littlestone's work, relative
loss bounds for the comparison class of linear threshold functions have
been investigated (Lit88; GLS97).
All the on-line algorithms cited in the previous paragraph use xed
learning rates. In the simple settings the relative loss bounds do not
grow with the number of trials. However, already for linear regression
with the square loss, the relative loss bounds for algorithms with xed
learning rates grow with the square root of the loss of the best linear
predictor (CBLW96; KW97) and the best loss is often linear in the
number of trials T .
In contrast, our algorithms use a variable learning rate and our
relative loss bounds grow logarithmically with T . Such bounds have
been proven for a generalization of Bayes' Algorithm
XB97; Yam98) which maintains a posterior on all parameters of the
comparison class. We outline this method for proving relative loss
bounds in Section 6. Bounds that grow logarithmically with T have also
been proven previously for on-line linear regression
important insight we gained from this research is that O(log T ) relative
loss bounds seem to require the use of variable learning rates. In this
paper, the learning rate applied in trial t is O(1=t). The use of O(1=t)
learning rates for the exponential family was also suggested by Gordon
as a possible strategy for leading to better bounds. However,
no specic examples were worked out. In the case of linear regression,
the O(1=t) learning rates become inverses of the covariance matrix of
the past examples.
General frameworks of on-line learning algorithms were developed in
(GLS97; KW97; KW98; Gor99). We follow the philosophy of Kivinen
and Warmuth (KW97) of starting with a divergence function. From
the divergence function we derive the on-line update and then use the
same divergence as a potential in the amortized analysis. A similar
method was developed in (GLS97) for the case when the comparison
class consists of linear threshold functions. They start with an update
and construct the appropriate divergence that is used in the analysis.
6 K. S. Azoury and M. K. Warmuth
Recently we have learned that the divergences used in on-line learning
have been employed extensively in convex optimization and are
called Bregman-distances (Bre67; CL81; Csi91; JB90). Bregman's method
is to pick from a set of allowable models the one of minimal distance to
the current model. In other words the current hypothesis is projected
onto a convex set of allowable models. Some mild additional assumptions
assure the uniqueness of the projections. With these assumptions
a generalized Pythagorean Theorem can be proven for Bregman divergences
HW98). The latter theorem often
contradicts the triangular inequality and this is the reason why we use
the term \divergence" instead of \distance".
Projections with respect to Bregman divergences have recently been
applied in (HW98) for the case when the o-line comparator is allowed
to shift over time. The projections are used to keep the parameters
of the algorithm in reasonable regions. This aids the recovery process
when the underlying model shifts.
3. Bregman Divergences and the Exponential Family
In this paper, we use a notion of divergence due to Bregman (Bre67) for
deriving and analyzing on-line learning algorithms. These divergences
can be interpreted as relative entropies between distributions from an
exponential family. We begin this section by dening Bregman divergences
and then review some important features of the exponential
family of distributions that are relevant to this paper. We conclude
this section with some properties of the divergences.
For an arbitrary real-valued convex and dierentiable function G()
on the parameter space   R d , the Bregman divergence between two
parameters e
and  in  is dened as
Here r  denotes the gradient with respect to . Throughout the paper,
all vectors are column vectors and we use \" to denote the dot product
between vectors.
Note that the Bregman divergence G ( e
minus the
rst two terms of the Taylor expansion of G( e ) around . In other
words, G ( e
is the tail of the Taylor expansion of G( e ) beyond the
linear term. Since G() is convex, G ( e
properties will
be listed in Section 3.4.
For example, let the parameter space be
2 . In this case the Bregman divergence becomes the squared
Relative Loss Bounds 7
Euclidean distance, i.e.,
Also if
e  e  ( e
e
3.1. The Exponential Family
The features of the exponential family that are used throughout this
paper include a measure of divergence between two members of the
family and an intrinsic duality relationship. See (BN78; Ama85) for a
more comprehensive treatment of the exponential family.
A multivariate parametric family FG of distributions is said to be
an exponential family when its members have a density function of the
where  and x are vectors in R d , and P 0 (x) represents any factor of
the density which does not depend on .
The d-dimensional parameter  is usually called the natural (or
canonical ) parameter. Many common parametric distributions are
members of this family, including the Gaussian. The function G()
is a normalization factor dened by
Z
The space   R d , for which the integral above is nite, is called the
natural parameter space. The exponential family is called regular if
is an open subset of R d . It is well known (BN78; Ama85) that  is a
convex set, and that G() is a strictly convex function on . The function
G() is called the cumulant function, and it plays a fundamental
role in characterizing members of this family of distributions.
We use g() to denote the gradient r  G() and r 2
G() to denote
the Hessian of G(). Let
represent the log-likelihood which is viewed as a function of . Under
some standard regularity conditions, log-likelihood functions satisfy
well-known moment identities (MN89). Applying these identities to
the exponential family reveals the special role played by the cumulant
function G().
8 K. S. Azoury and M. K. Warmuth
be the expectation with respect to the distribution PG (xj).
The rst moment identity of log-likelihood functions is
The gradient of the log-likelihood in (3.2) is linear in x:
r  G (;
Applying (3.3), we get
This shows that the mean of x is equal to the gradient of G(). We let
call  the expectation parameter.
Since the cumulant function G is strictly convex, the map
has an inverse. We denote the image of  under the map g(:) by M
and the inverse map from M to  by g 1 . The set M is called
the expectation space, which may not necessarily be a convex set.
The second moment identity for log-likelihood functions is
where 0 denotes the transpose. For the exponential family we have
and r 2
Thus, by the second moment identity, the variance-covariance matrix
for x is the Hessian of the cumulant function G() (also
called the Fisher Information Matrix). Since G() is strictly convex,
this Hessian is symmetric positive denite.
3.2. Duality Between the Natural Parameters and the
Expectation Parameters
Sometimes, it is more convenient to parameterize a distribution in the
exponential family by using its expectation parameter  instead of
its natural parameter . This pair of parameterizations have a dual
relationship. We provide the aspects of the duality that are relevant
to this paper. First, dene a second function on the range M of g as
follows:
Let f() := rF () denote the gradient of F ().
Relative Loss Bounds 9
Note that by taking the gradient of F () in (3.6) with respect to
and treating  as a function of , we get
where r is the Jacobian of  with respect to .
Thus, f() is the inverse map g 1 () and the two parameterizations
and  are related by the following transformations
Since g() has a positive denite Jacobian for all  2 , g 1 () has
a positive denite Jacobian for all  2 M. Thus, the second function
F () is strictly convex as well. This function is called the dual of G()
(Ama85). Furthermore, F () is the negative entropy of PG (xj) with
respect to the reference measure P 0 (x), i.e.,
It follows from (3.8) that the Hessian of F () is the inverse of the
Fisher Information Matrix, i.e., r 2
Now consider
the function V
G(f()), which is the Fisher Information
Matrix expressed in terms of the expectation parameter. This function
is dened on the expectation space M, takes values in the space of
symmetric d  d matrices, and is called the variance function. The
variance function plays an important role in characterizing members in
the exponential family (Mor82; GPS95). The matrix V () is positive
denite for all  2 M, and V
. Thus, in the context
of exponential families the functions F and G are not arbitrary convex
functions but must have positive denite Hessians.
3.3. Divergence Between two Exponential Distributions
Consider two distributions PG (xj e
with an old parameter setting e
and PG (xj) with a new parameter setting . Following Amari (Ama85)
one may see the exponential family FG as a manifold. The parameters
e  and  represent two points on this manifold. Several measures of
distance (divergence) between these two points have been proposed
in the literature. Amari introduced  divergences (Ama85), and other
related \distances" were introduced by Csiszar (Csi91) known as f
divergences (we use the letter h below). Also Cherno distances and
Renyi's  information are related (Ama85). These divergences all have
K. S. Azoury and M. K. Warmuth
the following general form:

where h(:) is some continuous convex function.
Our main choice for h is which gives the relative
entropy
Another interesting choice is which gives the \opposite"
These two entropies are, respectively, called 1 and +1 divergences by
Amari (Ama85).
3.4. Properties of Divergences
In this section we give some simple properties of the divergences. For
these properties we do not need that G() has a positive denite
Hessian. Hence the properties hold for the more general denition
of Bregman divergence (3.1) where we allow G() to be an arbitrary
real-valued dierentiable convex function G() on the parameter space
.
Throughout the paper we use  to represent r  G().
1. G ( e ; ) is convex in its rst argument since G( e ) is convex.
2. G strictly convex then equality holds i
e
3. The gradient of the divergence with respect to the rst argument
has the following simple form
r e
4. Divergences are usually not symmetric, i.e., G ( e
5. The divergence is a linear operator, i.e.,
and  aG for a  0:
Relative Loss Bounds 11
6. The divergence is not aected by adding a linear term to G():
if G()
then G
7. For any  1 ;  2 and  3 ,
The dot product can usually have any sign. When it is negative then
the above contradicts the triangular inequality. The case when the
dot product is zero is exploited in the proof of the generalization of
the Pythagorean Theorem to Bregman divergences (See for example
8. If G() is strictly convex, then the denition of the dual convex
function F () and the parameter transformations still hold (3.6-
3.8) and Bregman divergences have the following duality property:
The rst six properties are immediate. Property 7 is proven in the
appendix. This property was rst used in (WJ98) for proving relative
loss bounds. The last property follows from the denition of the dual
function F () (also called convex conjugate (Roc70)). Note that the
order of the arguments in G ( e
is switched. In this
paper, we only need Property 8 for the case when G() is strictly con-
vex. However, for any real-valued dierentiable convex function G()
one can dene the dual function as F
parameter in  such that r  (Roc70). With this denition
Property 8 still holds.
We note that Gordon (Gor99) gives an elegant generalization of
Bregman divergences to the case when the convex function G() is not
necessarily dierentiable. For the sake of simplicity we restrict ourselves
to the dierentiable case in this paper.
Finally, when G() is dierentiable, the Bregman divergence can
also be written as a path integral:
This integral version of the divergence has been used to dene a notion
of a convex loss \matching" the increasing transfer function g() of an
articial neuron (AHW95; HKW95; KW98).
12 K. S. Azoury and M. K. Warmuth
4. The Incremental O-line Algorithm
In this section we give our most basic algorithm and show how to
prove relative loss bounds in a general setting. Learning proceeds in
In each trial t an example is processed. For density
estimation, the examples are data vectors x t from some domain X . In
the regression setting, the t-th example consists of an instance x t from
some instance domain X and a label y t from some label domain Y.
The setup for a learning problem is dened by three parts. A parameter
space   R d , a real-valued loss function and a divergence
function that is a measure of \distance" to an initial parameter setting.
The parameter space  represents the models to which the algorithms
are compared. The loss of parameter vector  on the t th example
is denoted by L t () and L 1::t () is shorthand for
Usually
losses are non-negative. The third component of the setup is an initial
parmeter  0 and a Bregman divergence U0 (;  0 ) to the initial pa-
rameter. The initial parameter  0 may be interpreted as a summary of
any prior learning and the divergence U0 (;  0 ) represents a measure
of \distance" to the initial parameter.
The o-line (or batch) algorithm sees all T examples at once and it
sets its parameter to
where U T+1
Assumptions: The losses L t () (for 1  t  T ) and U 0 () are dier-
entiable and convex functions from the parameter space  to the reals.
Furthermore, we assume that argmin  U T+1 () always has a solution
in .
Note that this o-line algorithm trades the total loss on the examples
against closeness to the original parameter. Alternatively the
divergence U 0
may be interpreted as the \size" of parameter .
With this interpretation, the o-line algorithm nds a parameter that
minimizes the sum of size and total loss.
The on-line algorithm sees one example at a time according to the
following protocol:
On-line protocol of the Incremental O-line Algorithm
Initial hypothesis is  0 .
For to T do
Predict with  t .
Get t-th example.
Incur loss L
Update hypothesis  t to  t+1 .
Relative Loss Bounds 13
The goal of the on-line algorithm is to incur a loss that is never
too much larger than the loss of the o-line algorithm which sees all
examples at once. At the end of trial t the on-line algorithm knows the
rst t examples and expects to see the next example. One reasonable
and desirable setup for the parameter update at this point is to make
the on-line algorithm do exactly what an o-line algorithm would have
done after seeing t examples. We use the name Incremental O-line for
the on-line algorithm with this property.
The Incremental O-line Algorithm
where U t+1
Additional assumptions: Here we assume that the argmin  U t+1 ()
(for 1  t  T ) always have a solution in .
If there is more than one solution for
then this is interpreted as  t+1 2 argmin  U t+1 (). In the learning
problems that we use as examples in this paper, U t+1 () is typically
strictly convex and so there is only one solution. Note that the nal
parameter  T+1 of the Incremental O-line Algorithm coincides with
the parameter B chosen by the batch algorithm.
When which is
consistent with the protocol given above. While not necessary here, we
begin the indexing of  t at to parallel the indexing of a second
on-line algorithm given in the next section. This second algorithm is
called the Forward Algorithm because it uses a guess of the next loss
when updating the parameter.
The setup for the update in (4.1) does not seem truly on-line since it
needs all the previous t examples. A truly on-line, yet equivalent setup,
is given by the following lemma:
LEMMA 4.1. For the Incremental O-line Algorithm and 1  t  T ,
Proof: Note that since rU t ( t
Thus, since U t ( t ) is a constant, the argmin for  t+1 used in the
denition (4.1) is the same as the argmin of the lemma. Q.E.D.
We are now ready to show the key lemma for the Incremental O-
line Algorithm. In this lemma we compare the total loss of the on-line
algorithm to the total loss of any comparator , where the total loss of
the comparator includes the divergence term U 0 (;  0 ).
14 K. S. Azoury and M. K. Warmuth
LEMMA 4.2. For the Incremental O-line Algorithm, any sequence of
T examples, and any  2 ,
U t+1
Proof: For 0  t  T , we expand the divergence U t+1 (;  t+1 ) and
use rU t+1 ( t+1 This gives us
U t+1 (;  t+1
Since U t+1
For the special case of
Subtracting (4.3) from (4.4) and applying U t () U t ( t
(a version of (4.2)) gives
By summing the above over all T trials we obtain:
U
The lemma now follows from the equality U 1
This equality follows from Property 6, because
linear in . Q.E.D.
To obtain relative loss bounds we choose the best o-line parameter
B as the comparator  and bound the right-hand-side of the equation
of the lemma. Note that in case of the Incremental O-line Algorithm,
and thus the last divergence on the right-hand-side is zero.
The divergence U t+1
represents the cost of the update of
t to  t+1 incurred by the on-line algorithm. Relative loss bounds are
bounds on the total cost
of the on-line updates.
Relative Loss Bounds 15
4.1. Incremental Off-line Algorithm for the Exponential
Family
We now apply the Incremental O-line Algorithm to the problem of
density estimation for the exponential family of distributions. We rst
give a general treatment and then prove relative loss bounds for specic
members of the family in the subsections that follow.
We make the most obvious choice for a loss function, namely, the
negative log-likelihood. So using the general form of the log-likelihood
(3.2), the loss of parameter  on the example x t is
For the purpose of the relative loss bounds (see Lemma 4.2) changing
the loss by a constant that does not depend on  is inconsequential.
Thus, the form of the reference measure P 0 (x) is immaterial.
As before, we allow the algorithm to have an initial parameter value
at  0 and choose U 0 () as a multiple of the cumulant function, i.e.,
Thus, in the context of density estimation
with the exponential family, the Incremental O-line Algorithm
becomes
where U t+1
Throughout the paper we use the notation  1 to denote trade-o
parameters. This has two reasons. First, the inverse of the trade-o
parameters will become the learning rates of the algorithms and learning
rates are commonly denoted by . Also, we use  1 instead of
1=, because in linear regression the  parameters are generalized to
matrices.
The setup (4.5) can be interpreted as nding a maximum a-posteriori
(MAP) parameter where the divergence term corresponds to the conjugate
prior and  1
is a hyper parameter. When  1
the divergence term disappears and we have maximum likelihood esti-
mation. Alternatively one can think of  0 an initial parameter estimate
based on some hypothetical examples seen before the rst real example
0 as the number of those examples. Also one can interpret
the parameter  1
0 as a trade-o parameter between staying close to
the initial parameter  0 and minimizing the loss on the t examples seen
by the end of trial t.
Yet another interpretation of (4.5) follows from rewriting U t+1 () as
K. S. Azoury and M. K. Warmuth
Thus, U t+1 () corresponds to the negative log-likelihood of an exponential
density with the cumulant function ( 1
and the example
is  1
We now develop the alternate on-line motivation given in Lemma
4.1. Let  1
is linear in ,
it follows from the properties of the divergences that U t
Thus, the on-line motivation of Lemma
4.1 becomes
Now the divergence measures the distance to the last parameter and
the trade-o parameter is  1
The updated parameter  t+1 can be obtained by minimizing U t+1 ()
(as dened in (4.5)) which is a strictly convex function in . The
gradient of this function in terms of the expectation parameters is
Setting the above to zero, for 0  t  T , gives the update of the
expectation parameter of the Incremental O-line Algorithm:
For 1  t  T , we can also express  t+1 as a convex combination of  t
and the last instance x
Note that  t  1
Alternate recursive forms of the update, that
are used later on, are (for 1  t  T
Thus, the on-line update may be seen as gradient descent with different
learning rates. The update (4.9) uses the gradient of the loss at
t+1 , while (4.10) uses the gradient of the loss evaluated at  t .
In the special case when  1
is not valid for which is consistent
with updates (4.8) and (4.10).
Relative Loss Bounds 17
The relative loss bounds are proven by using Lemma 4.2. Thus, for
density estimation this equality simplies to:
The following lemma gives a concise expression for the minimum of
U t+1 () (see (4.5)) in terms of the dual of the cumulant function.
This lemma and the following discussion is interesting in its own right.
Although it is not essential for the main development of this paper,
we will use it in the Bernoulli example discussed later. By combining
(4.11) with this lemma one can also get an expression for the total loss
of the on-line algorithm (Lemma 3.1 of (AW99)).
LEMMA 4.3.
min
Proof: We rewrite the right-hand-side of the equality of the lemma
using the denition of the dual function F () (3.6) and the expression
We rewrite the above using  1
and the denitions of the
loss and divergence:
The above is equal to U t+1 ( t+1 ). Q.E.D.
When  1
(the case of maximum likelihood), the above can be
rewritten as:
K. S. Azoury and M. K. Warmuth
where
Thus, essentially the inmum of the average loss on the data equals
the expected loss at the parameter that minimizes the average loss,
i.e., the maximum likelihood parameter. The above relationship was
used in (Gru98).
In the remaining subsections we discuss specic examples and give
their relative loss bounds.
4.1.1. Density Estimation with a Gaussian
Here we derive relative loss bounds for the Gaussian density estimation
problem. Consider a Gaussian density over R d with a known and xed
Without loss of generality, we will develop the bounds for the special
case when  is the identity matrix. Similar bounds immediately follow
for the general case of xed but arbitrary variance-covariance matrix
by a linear transformation argument.
The Gaussian density with the identity matrix as the variance-covariance
matrix is
(Here, x 2 is shorthand for x  x.) This density is a member of the
exponential family with natural parameter :
Cumulant
Parameter transformations:
functions).
Dual convex function: F
Loss: L t
const.
Note that the constant in the loss is immaterial for the bounds and
therefore, we set it to zero.
For the sake of simplicity, set  2. Recall that
for the Incremental O-line Update,
with the dierence between the total loss of the Incremental
O-line Algorithm and the o-line algorithm is
Relative Loss Bounds 19
We use the on-line updates (e.g. (4.9), (4.10)) to rewrite the divergences
on the right-hand-side:
We want to allow  1
In this case, update (4.9) cannot be applied
1. However, by update (4.8), we have that for any  1
1 , for any  1
(4.12) can rewritten as follows:
It is easy to nd two examples x 1 and x 2 for which the dierence
(4.14) depends on the order in which the two examples are presented.
We now develop an upper bound that is permutation invariant, i.e.,
it does not depend on order in which the examples are presented. We
drop the negative terms from (4.14), use


Since
we obtain the following relative loss bound:
K. S. Azoury and M. K. Warmuth
THEOREM 4.4. For Gaussian density estimation with the Incremental
O-line Algorithm and


t .
Note that in the special case when  1
then the o-line algorithm
chooses a maximum likelihood parameter and the above bound
simplies to 1
4.1.2. Density Estimation with a Gamma
Here we give the relative loss bounds for the Gamma distribution. The
density with shape parameter  and inverse scale parameter
is
This is a member of the exponential family with natural parameter
the density above in terms of  can be written as
We assume  is known and xed. The parameter  scales the loss and
the divergences. The inverse of  is called the dispersion parameter.
So for the sake of simplicity we drop  just as we ignored the xed
variance in the case of Gaussian density estimation.
Cumulant
Parameter transformations:
Dual convex function: F
Loss: L t
We bound the divergence between  t and  t+1 , which leads to a relative
loss bound for the Incremental O-line Algorithm (see (4.11)):
(4.
Relative Loss Bounds 21
Using the update (4.10) and the notation r

because the  t are convex combinations of the
elements of fx g. If  1
then the sum of the
divergences on the right-hand-side of (4.11) can be bounded by
In summary we have the following relative loss bound:
THEOREM 4.5. For density estimation with a Gamma distribution
using the Incremental O-line Algorithm and  1

Better relative loss bounds that include the case when  1
be possible by bounding (4.15) more carefully.
4.1.3. Density Estimation for the General Exponential Family
Here we give a brief discussion of the form the bounds take for any
member of the exponential family. We rewrite the divergence between
After doing a second order Taylor expansion of F ( t+1 ) at  t , this last
=e  t
=e  t
22 K. S. Azoury and M. K. Warmuth
where e
t is a convex combination of  t and  t+1 . If r 2
F () is constant
then we essentially have a Gaussian. The general case may be seen
as a local Gaussian with the time-varying curvature. Any reasonable
methods have to proceed on a case-by-case basis (Mor82; GPS95) based
on the form of r 2
F (), which is the inverse of the variance function.
Recall that  summing the last term should always
give a log(T )-style bound. Sometimes the range of the x t needs to
be restricted as done in the previous subsections for density estimation
with Gaussian and Gamma distributions.
4.1.4. Linear Regression
In this subsection the bounds for linear regression are developed. Here
the instance domain X is R d and the label domain Y is R. The parameter
domain  is also R d and the d components of the parameter
vectors  2  are the d linear weights. For a given example
parameter vector , the linear model predicts with x t  . The square
loss
is used to measure the discrepancy between
the prediction and the label for that example. Note that L t () is not
strictly convex in . Thus, we make U 0 () strictly convex so that the
initial divergence U 0
strictly convex and our updates
always have a unique solution. We use U
positive denite matrix. Now the divergence to
the initial parameter becomes U 0 (;  0
Thus, for linear regression, the update (4.1) of the Incremental O-line
Update becomes:
where U t+1
Note that we use the transpose notation x 0
q  instead of the dot product
because the subsequent derivations will use matrix algebra. The
above setup for linear regression is usually interpreted as a conditional
density estimation problem for a Gaussian label y t given x t , where the
cumulant function in trial t is 1
and the divergence corresponds
to a Gaussian prior on .
Again we develop the alternate on-line version of (4.16) as done in
general in Lemma 4.1. Since U t () equals 1
linear
terms, the on-line version becomes
Relative Loss Bounds 23
By dierentiating (4.16) for 0  t  T , we obtain the Incremental
O-line Update for linear regression:
This is the standard linear least squares update. It is easy to derive the
following recursive versions (for 1  t  T
Note the correspondence of the above updates to the updates (4.7-
4.10) for density estimation. Also Lemma 4.2 becomes the following
quadratic equation (See (4.11) for the corresponding equation in density
We now reprove a bound obtained by Vovk (Vov97) for the Incremental
O-line Algorithm. (For the sake of simplicity we choose  1
0 as
a multiple of the identity matrix I.) A similar bound was proven by Foster
for the same algorithm. However, he assumes that the comparator
is a probability vector (Fos91).
THEOREM 4.6. For linear regression with the Incremental O-line
Algorithm and  1

a
Tg.
Note that this theorem assumes that the predictions x 0
of the labels
y t at trial t lie in [ Y; Y ]. If this assumption is not satised, we might
use clipping, i.e., the algorithm predicts with the number in [-Y,Y] that
is closest to x 0
clipping requires the algorithm to know Y .
K. S. Azoury and M. K. Warmuth
There is little incentive to work out the details for the Incremental O-
line Algorithm because for the algorithm of the next section we can
prove a better relative loss bound and the predictions don't need to lie
in [ Y; Y ].
Proof: We apply the Update (4.19) twice to the divergence in the
sum of the right-hand-side of (4.20). This give the rst two equalities
below. The third equality follows from Lemma A.1 of the appendix.2 ( t  t+1

In the last inequality we used the assumption that x 0
the fact that z 1  ln z. Note that the last inequality may not hold
without the assumption x 0
The theorem now follows from applying these crude approximations
to the equality of Lemma (4.2):
d

a

a
The last inequality follows from the assumption that x q;i  X 2 . The
second to last inequality follows from the fact that  1
aI and that
the determinant of a symmetric matrix is at most the product of the
diagonal elements (See (BB65), Chapter 2, Theorem 7). Q.E.D.
Ideally we don't want to use this crude bounding method. The goal
is to rewrite the sum of divergences so that further telescoping occurs.
For the Incremental On-line Update we have not been able to do that.
Below is a partial attempt that follows what we did for Gaussian density
Relative Loss Bounds 25
estimation (4.13).2 ( t  t+1
In the last equality we use the fact that  t 1 is symmetric. Note that
the last two terms in the nal expression do not telescope as they did
for the Gaussian case (4.13). Surprisingly, for the Forward Algorithm
that will be introduced in the next section, the corresponding two terms
do telescope. Thus, for Forward Algorithm, one can prove a bound as
the one given in Theorem 4.6 except that the last term in the bound
is now 1
a 1), a quarter of what it was in Theorem 4.6.
In the related problem for density estimation with a Gaussian, the
corresponding improved bound (with factor 1
holds for the
Incremental O-line Algorithm.
5. Estimating the Future Loss - the Forward algorithm
In this section we present our second algorithm called the Forward
Algorithm and give some lemmas that are used for proving relative
loss bounds. In trial t, the Forward Algorithm expects to see the next
example and we allow it to incorporate an estimate of the loss on this
next example when choosing its parameter.
In regression, \part" of the example, namely the instance x t , is available
at trial t before the algorithm must commit itself to a parameter
t . So the algorithm can use the instance x t to form an estimate ^
of the loss at trial t. As we shall see in linear regression, incorporating
such an estimate in the motivation can be used to include the current
instance into the learning rate of the algorithm and this leads to better
relative loss bounds. In density estimation, however, there are no
instances, yet the algorithm still uses an estimate of the future loss.
26 K. S. Azoury and M. K. Warmuth
On-line protocol of the Forward Algorithm
Regression: Density estimation:
Initial hypothesis is  0 . Initial hypothesis is  0 .
For to T do For to T do
Get instance x t . ::::::::::::
Guess loss on t-th example. Guess loss on t-th example.
Update hypothesis  t 1 to  t . Update hypothesis  t 1 to  t .
Predict with  t . Predict with  t .
Get label y t of t-th example. Get example x t .
Incur loss L Incur loss L
We now dene the update analogous to the previous section by
minimizing a sum of a divergence plus the losses in the past t trials
and an estimate of the loss ^
in the next trial.
The Forward Algorithm
where U t+1
Assumption: The losses L t () (for 1  t  T ), the estimated losses
are dierentiable and convex
functions from the parameter space  to the reals. Furthermore, we
assume that the argmin  U t+1 () (for 1  t  T ) always have a solution
in .
Note that the Incremental O-line Algorithm is a special case of the
Forward Algorithm where all the estimated losses ^
are zero. As
before there is an alternate on-line motivation of the update using a
divergence to the last parameter vector.
LEMMA 5.1. For the Forward Algorithm and 1  t  T ,
U
we can rewrite the argument of the argmin as:
Relative Loss Bounds 27
Thus, since U t ( t ) is a constant, the argmin for  t+1 used in the
denition (5.1) is the same as the argmin of the lemma. Q.E.D.
The following key lemma is a generalization of Lemma 4.2 for the
Incremental O-line Algorithm.
LEMMA 5.2. For the Forward Algorithm, any sequence of T examples
and any  2 ,
U t+1
Proof: For 0  t  T , we expand the divergence U t+1 (;  t+1 ) and
use rU t+1 ( t+1 As in the proof of Lemma 4.2, this gives us
U t+1 (;  t+1
Since U t+1
obtain
For the special case of
Subtracting (5.3) from (5.4) and applying U t () U t ( t
(a version of (5.2)), we obtain
U t+1
The equation of the lemma follows by summing the above over all T
trials and subtracting U 0
sides. Q.E.D.
Any relative loss bound for the Forward Algorithm must be based
on bounding the right-hand-side of this lemma.
5.1. Density Estimation with the Exponential Family
Here we apply the Forward Algorithm to the problem of density estimation
with the exponential family of distributions. We choose U 0
28 K. S. Azoury and M. K. Warmuth
0 G() as done for the Incremental O-line Algorithm. Thus, the
initial divergence becomes U 0
For the estimated future loss we use ^
const. This may be seen as the average loss of a number of examples
for which (
lies in the instance
domain, then  0 can be seen as a guess for the future instance with
the corresponding loss being
(). The estimated loss ^
we rewritten as G (;  const. Thus, with the above choices, the
Forward Algorithm (5.1) becomes the following (for
where U t+1
This is the same as the Incremental O-line Algorithm (4.5) except that
the trade-o parameter is now  1
0 . For 1  t  T ,
the on-line motivation becomes
This is the same as the on-line motivation of the Incremental O-
line Algorithm (4.6) except that  1
t 1 is increased by one to  1
t . The
updates (4.7-4.10) and Lemma 4.3 remain the same but the learning
rates are shifted:
The above updates hold for 1  t  T . The rst one holds for
well which shows that  our choice of the estimate ^
Since the estimated loss is independent of the trial, the estimated
losses in the last equality of Lemma 5.2 cancel and we get:
Relative Loss Bounds 29
5.2. Density Estimation with a Gaussian
In this section, we give a bound for the Forward Algorithm that is
better than the corresponding bound for the Incremental O-line Al-
gorithm. Following the same steps as in (4.13), we simplify the following
divergence:
Using this, (5.9) becomes
We now set  0 (and thus  1 ) to zero and choose
T+1 .
Thus, the last three terms of the above equation can be rewritten as:2  2
0: (5.11)
Equation (5.10) is bounded by2 X 2


THEOREM 5.3. For Gaussian density estimation with the Forward
Algorithm and
t .
K. S. Azoury and M. K. Warmuth
Note that the above bound for the Forward Algorithm is better than
the bound for the Incremental O-line algorithm (See Theorem 4.4).
The improvement is essentially 2X 2 .
5.3. Density Estimation with a Bernoulli
In this subsection we give the relative loss bounds for the Bernoulli
distribution. Here the examples x t are coin
ips in f0; 1g and the
distribution is typically expressed as P
is the probability of 1. Let
1  . So the distribution in terms
of  is
This is a member of the exponential family with natural parameter .
Cumulant
Parameter transformations:
1+e  and
Dual function: F
Loss: L t
Consider the Forward Algorithm with  1
In this case
(maximum likelihood) and the
Forward Algorithm uses  t+1 =2
t+1 . We rst develop a concise
expression for the total loss of the algorithm.
LEMMA 5.4. For Bernoulli density estimation with the Forward Algorithm
Y
Proof: We rst rewrite the loss at trial t in various ways. Let s t
abbreviate
We now develop a formula for
Note that in all trials t in
which x increases by one), the loss L contains the
Relative Loss Bounds 31
term ln(s t2 ). Over all T trials, these terms contribute
Similarly, in all trials t in which x
by one), the loss L contains the term ln(t s t2 ). Over all T
trials, these terms contribute
From this and the fact
that the lemma follows. Q.E.D.
Note that the right-hand-side of the expression of the lemma is
independent of the order in which the examples were seen. Thus, for
Bernoulli distribution, the total loss of the forward algorithm is permutation
invariant. By Lemma 4.3, L 1::T
and thus
Y
An equivalent expression using the Gamma function was rst derived
by Freund (Fre96) based on the Laplace method of integration.
Using the standard approximations of the Gamma function one can
bound the right-hand-side of the above by 1
THEOREM 5.5. (Fre96) For Bernoulli density estimation with the
Forward Algorithm and
5.4. Linear Regression
In this subsection we derive relative loss bounds for the Forward Algorithm
when applied to linear regression. As for the Incremental O-line
Algorithm, we let U 0
positive
denite. The divergence to the initial  0 is again U
We use the estimated future loss ^
i.e., the next label y t+1 is guessed as x 0
the Forward Update (5.1) for linear regression becomes:
K. S. Azoury and M. K. Warmuth
where U t+1
With this denition, U 1 (;  0
is minimized at  0 , and thus  dierentiating U t+1 (), we
obtain the Forward Update for linear regression (0  t  T
where
Note that  t+1 depends on x t+1 . Thus, the Forward Algorithm is different
from the Incremental O-line Algorithm (4.17) in that it uses
the current instance to form its prediction.
For the sake of simplicity we assume for the rest of this section
that  Recursive versions of the above update are the following
We now rewrite the equality of Lemma 5.2 for linear regression.
Following the same steps we used for the Incremental O-line Algorithm
(4.22) we
Relative Loss Bounds 33
Using the above, the argument of the sum on the right-hand-side of
Equation (5.15) can be simplied as
Note that the last two terms telescope. In the corresponding derivation
for the Incremental O-line Update, the last two terms did not telescope
(4.22). So now (5.15) with
As in Gaussian density estimation (5.10), we will now show that the
last three terms of the above equation are zero. First we rewrite B as:
where I is the identity matrix.
The last term becomes:2
The second to last term simplies to:2 ( T x T+1 x 0
We now sum the last three terms while pulling out the factor 1
34 K. S. Azoury and M. K. Warmuth
Thus, the last three terms are zero just as they were for Gaussian
density estimation with the Forward algorithm (5.11).
Finally, we can use the upper bound (see Theorem 4.6)2 y 2
t . Now the sums on the right-hand-side of (5.16)
can be bounded by 1
a ).
We now summarize the relative loss bound we proved for the Forward
Algorithm:
THEOREM 5.6. For linear regression with the Forward Algorithm and

a
t .
Note the above bound for the Forward algorithm is better than the
corresponding bound for the Incremental O-line Algorithm (See Theorem
4.6). The improvement is by a factor of four. The above bound
was rst proven by Vovk (Vov97) using integration. An alternate
proof for the exact expression (5.17) was given by Forster (For99).
6. Relationship to the Bayes' Algorithm
There is an alternate method pioneered by Vovk (Vov97), Freund
and Yamanishi (Yam98) for proving relative loss bounds. In this section
we sketch this method and compare it to ours. A distribution is
maintained on the set of parameters . The parameters can be names
of algorithms and are called experts in the on-line learning literature
97). The initial work only considered the case when  is nite
However, the method can also be applied
when  is continuous Yam98). At the beginning of trial
Relative Loss Bounds 35
t, the distribution on  has the form
R
e
where P 1 is a prior and  > 0 a learning rate. The following type of
inequality is the main part of the method:
Z
Z
Z
Here LA (t) denotes the loss of the algorithm at trial t. An important
special case occurs when when and the loss L q () is a
negative log-likelihood with respect to a parameterized density, i.e.,
We call this the Bayes' Algorithm. In this case,
P t as given in (6.1) is the posterior distribution after seeing the rst
examples. If the algorithm in trial t predicts with the predictive
distribution
then (6.2) is an equality (DMW88).
In the more general setting (when  6= 1 and the losses are not
necessarily negative log-likelihoods), the prediction of the algorithm is
chosen so that inequality (6.2) holds no matter what the t-th example
will be. Also, the larger the learning rate , the better the resulting
relative loss bounds. The learning rate  is chosen as large as possible so
that a prediction is always guaranteed to exist for which inequality (6.2)
holds. The same learning rate is used in all T trials. The inequality is
often tight when the examples lie on the boundary of the set of possible
examples. By summing the inequality (6.2) over all trials, one gets the
bound
Z
If the above integral cannot be computed exactly, then it is bounded using
Laplace's method of integration around the best o-line parameter
We would like to point out the following distinction between the
above method and the algorithms presented in this paper. The prediction
of the Bayes' Algorithm (i.e., the predictive distribution) is
usually not represented by a parameter (or expert) in . Instead, the
algorithms analyzed in this paper chooses a MAP parameter in  in
each trial. In the case of the Bernoulli distribution, the Bayes' Algorithm
based on Jerey's prior coincides with the Forward
36 K. S. Azoury and M. K. Warmuth
Algorithm when  1
(Section 5.3). Similarly, in the case
of linear regression with the Gaussian prior, Vovk's algorithm (Vov97)
coincides with the Forward Algorithm for linear regression (Section
5.4). However, it is not clear that for other density estimation problems
in the exponential family the predictions of the Bayes' Algorithm
(or the algorithms produced by for the more general case
when  6= 1) are represented by parameters in the parameter space.
In contrast, our method of proving relative loss bounds avoids the
use of the involved integration methods needed for (6.3)
CO96). The parameter we maintain is based on a simple average
of the past examples, which is a su-cient statistic for the exponential
family.
7. Conclusion
In this paper, we presented techniques for proving relative loss bound
for density estimation with the exponential family. We gave a number
of examples of how to apply our methods, including the case of linear
regression. For an exponential density with cumulant function G, we use
the Bregman divergence G ( e
as the measure of distances between
the parameters e  and . Thus, the loss L
divergence are based on the same function G. However, lemmas 4.2
and 5.2 and the methodology for proving relative loss bounds are more
general in that the initial divergence and the loss do not need to be
related. These lemmas might be further extended to non-dierentiable
convex functions using the generalized notion of Bregman divergences
that was introduced by Gordon (Gor99).
The parameters maintained by our algorithms are invariant to permuting
the past examples. However, the total on-line loss of the algorithms
is not permutation invariant. Therefore, an adversary could use
this fact and present the examples in an order disadvantageous to the
learning algorithm. This suggests that there are algorithms with better
relative loss bounds.
The Incremental O-line Algorithm and the Forward Algorithm are
incomparable in the sense that either one may have a larger total
loss. However, we believe that in some sense the Forward Algorithm
is better and this needs to be formalized. This belief is inspired by
the phenomenon of the Stein estimator in statistics (Ste56), since like
the Stein estimator, the Forward Update uses a shrinkage factor when
compared to the Incremental O-line Update.
We still need to explore how the bounds obtained in this paper relate
to the large body of research from the Minimum Description Length
Relative Loss Bounds 37
literature (Ris89; Ris96). In this literature, lower and upper bounds
on the relative loss of the form d
explored
extensively, where d is the number of parameters. However, in contrast
to the setup used in this paper, the work in the Minimum Description
Length literature does not require that the algorithm predicts with a
parameter in the parameter space.
The methodology developed in this paper for proving relative loss
bounds still needs to be worked out for more learning problems. For
instance, is there always a log(T )-style relative loss bound for any
member of the exponential family (See Section 4.1.3). Another open
problem is to prove log(T )-style bounds for logistic regression?
Finally, lower bounds on the relative loss need to explored for the
case when the algorithm is restricted to predict with a parameter in the
parameter space. Such bounds have been shown for linear regression
(Vov97). In particular, it was proven that the constant before ln(T )
in the relative loss bound of the Forward Algorithm (Theorem 5.6) is
tight. However, no general log(T )-style lower bounds is known for an
arbitrary member of the exponential family.

Acknowledgments

Thanks to Leonid Gurvitz for introducing us to Bregman divergences,
and to Claudio Gentile, Peter Grunwald, Georey Gordon, Eiji Taki-
moto, and two anonymous referees for many valuable comments.



--R

Exponentially many local minima for single neurons.

Relative loss bounds for on-line density estimation with the exponential family of distributions

An analog of the minimax theorem for vector payo

The relaxation method of



An iterative row-action method for interval convex pro- gramming
Universal portfolios with side information.
Universal portfolios.
Why least squares and maximum entropy?
Learning probabilistic prediction functions.

Prediction in the worst case.
Predicting a binary sequence almost as well as the optimal biased coin.
General convergence results for linear discriminant updates.

Technical report CMU-CS-99-143

The Minimum Discription Length Principle and reasoning under uncertainty.
Approximation to Bayes risk in repeated play
Learning algorithms for tracking changing concepts and an investigation into the error surfaces of single arti

Sequential prediction of individual sequences under general loss functions.
Tracking the best regressor.
Conf. on Comput.

Additive versus exponentiated gradient updates for linear prediction.
Relative loss bounds for multidimensional regression problems.
Learning when irrelevant attributes abound: A new linear-threshold algorithm

Journal of Computational Complexity
The weighted majority algorithm.
Generalized Linear Models.
Natural exponential families with quadratic variance functions.
Stochastic Complexity in Statistical Inquiry
Fisher information and stochastic complexity.
Convex Analysis.
Inadmissibility of the usual estimator for the mean of a multivariate normal distribution.
Asymptotically minimax regret for exponential families.
In
Asymptotically minimax regret by Bayes mixtures.
Aggregating strategies.
Competitive on-line linear regression
Continuous and discrete time nonlinear gradient descent: relative loss bounds and convergence.
Minimax redundancy for the class of memoryless sources.
IEEE Transactions on Information Theory
A decision-theoretic extension of stochastic complexity and its applications to learning

--TR

--CTR
Arindam Banerjee , Inderjit Dhillon , Joydeep Ghosh , Srujana Merugu, An information theoretic analysis of maximum likelihood mixture estimation for exponential families, Proceedings of the twenty-first international conference on Machine learning, p.8, July 04-08, 2004, Banff, Alberta, Canada
Shai Shalev-Shwartz , Yoram Singer, A primal-dual perspective of online learning algorithms, Machine Learning, v.69 n.2-3, p.115-142, December  2007
Jrgen Forster , Manfred K. Warmuth, Relative Loss Bounds for Temporal-Difference Learning, Machine Learning, v.51 n.1, p.23-50, April
Srujana Merugu , Joydeep Ghosh, A privacy-sensitive approach to distributed clustering, Pattern Recognition Letters, v.26 n.4, p.399-410, March 2005
S. V.N. Vishwanathan , Nicol N. Schraudolph , Alex J. Smola, Step Size Adaptation in Reproducing Kernel Hilbert Space, The Journal of Machine Learning Research, 7, p.1107-1133, 12/1/2006
Nicol Cesa-Bianchi , Claudio Gentile , Luca Zaniboni, Worst-Case Analysis of Selective Sampling for Linear Classification, The Journal of Machine Learning Research, 7, p.1205-1230, 12/1/2006
Claudio Gentile, The Robustness of the p-Norm Algorithms, Machine Learning, v.53 n.3, p.265-299, December
Arindam Banerjee , Srujana Merugu , Inderjit S. Dhillon , Joydeep Ghosh, Clustering with Bregman Divergences, The Journal of Machine Learning Research, 6, p.1705-1749, 12/1/2005
Mark Herbster , Manfred K. Warmuth, Tracking the best linear predictor, The Journal of Machine Learning Research, 1, p.281-309, 9/1/2001
bregman divergences;relative loss bounds;worst-case loss bounds;linear regression;exponential family of distributions;on-line algorithms