Learning from compressed observations
Learning From Compressed Observations
Maxim Raginsky
Beckman Institute and University of Illinois
405 N Mathews Ave, Urbana, IL 61801
maxim@uiuc.edu
Abstract— The problem of statistical learning is to construct
a predictor of a random variable Y as a function of a related
random variable X on the basis of an i.i.d. training sample from
the joint distribution of (X,Y ). Allowable predictors are drawn
from some specified class, and the goal is to approach asymp-
totically the performance (expected loss) of the best predictor
in the class. We consider the setting in which one has perfect
observation of the X-part of the sample, while the Y -part has
to be communicated at some finite bit rate. The encoding of the
Y -values is allowed to depend on the X-values. Under suitable
regularity conditions on the admissible predictors, the underlying
family of probability distributions and the loss function, we give
an information-theoretic characterization of achievable predictor
performance in terms of conditional distortion-rate functions.
The ideas are illustrated on the example of nonparametric
regression in Gaussian noise.
I. INTRODUCTION AND PROBLEM STATEMENT
Let X and Y be jointly distributed random variables, where
X takes values in an input space X and Y takes values in an
output space Y . The problem of statistical learning is about
constructing an accurate predictor of Y as a function of X on
the basis of some number of independent copies of (X,Y ),
often with very little or no prior knowledge of the underlying
distribution. A very general decision-theoretic framework for
learning was proposed by Haussler [1]. In a slightly simplified
form it goes as follows. Let P be a family of probability
distributions on Z = X ×Y . Each member P of P represents
a possible relationship between X and Y . Also given are a
loss function ℓ : Y × Y → R+ and a set F of functions
(hypotheses) from X into Y . For any f ∈ F and any P ∈ P
we have the expected loss (or risk)
L(f, P ) = E ℓ(f(X), Y ) ≡
ℓ(f(x), y)dP (x, y),
which expresses quantitatively the average performance of f
as a predictor of Y from X when (X,Y ) ∼ P . Let us define
the minimum expected loss
L∗(F , P ) △= inf
L(f, P )
and assume that the infimum is achieved by some f∗ ∈ F .
Then f∗ is the best predictor of Y from X in the hypothesis
class F when (X,Y ) ∼ P . The problem of statistical learning
is to construct, for each n, an approximation to f∗ on the
basis of a training sequence {Zi}ni=1, where Zi = (Xi, Yi)
are i.i.d. according to P , such that this approximation gets
better and better as the sample size n tends to infinity. This
formulation of the learning problem is referred to as agnostic
(or model-free) learning, reflecting the fact that typically only
minimal assumptions are made on the causal relation between
X and Y and on the capability of the hypotheses in F
to capture this relation. It is general enough to cover such
problems as classification, regression and density estimation.
Formally, a learning algorithm (or learner, for short) is a
sequence {f̂n}∞n=1 of maps f̂n : Zn × X → Y , such that
f̂n(Z
n, ·) ∈ F for all n and all Zn ∈ Zn. Let Z = (X,Y ) ∼
P be independent of the training sequence Zn. The main
quantity of interest is the generalization error of the learner,
L(f̂n, P )
f̂n(Z
n, X), Y
)∣∣∣Zn
ℓ(f̂n(Z
n, x), y)dP (x, y).
The generalization error is a random variable, as it depends
on the training sequence Zn. One is chiefly interested in the
asymptotic probabilistic behavior of the excess loss L(f̂n, P )−
L∗(F , P ) as n → ∞. (Clearly, L(f̂n, P ) ≥ L∗(F , P ) for
every n.) Under suitable conditions on the loss function ℓ, the
hypothesis class F , and the underlying family P of probability
distributions, one can show that there exist learning algorithms
which not only generalize, i.e., EL(f̂n, P ) → L∗(F , P ) as
n → ∞ for every P ∈ P (which is the least one could ask
for), but are also probably approximately correct (PAC), i.e.
Zn : L(f̂n, P ) > L
∗(F , P ) + ǫ
= 0 (1)
for every ǫ > 0 and every P ∈ P . (See, e.g., Vidyasagar [2].)
This formulation assumes that the training data are available
to the learner with arbitrary precision. This assumption may
not always hold, however. For example, the location at which
the training data are gathered may be geographically separated
from the location where the learning actually takes place.
Therefore, the training data may have to be communicated to
the learner over a channel of finite capacity. In that case, the
learner will see only a quantized version of the training data,
and must be able to cope with this to the extent allowed by the
fundamental limitations imposed by rate-distortion theory. In
this paper, we consider a special case of such learning under
rate constraints, when the learner has perfect observation of the
input part Xn = (X1, . . . , Xn) of the training sequence, while
the output part Y n = (Y1, . . . , Yn) has to be communicated
via a noiseless digital channel whose capacity is R bits per
sample. This situation, shown in Figure 1, may arise, for
example, in remote sensing, where the Xi’s are the locations
of the sensors and the Yi’s are the measurements of the sensors
http://arxiv.org/abs/0704.0671v1
ENCODER DECODER
LEARNER
BINARY DATA
AT RATE R
Fig. 1. The set-up for learning from compressed data with side information.
having the form f0(Xi) + Zi, where f0 : X → [0, 1] is some
unknown function and the Zi’s are i.i.d. zero-mean Gaussian
random variables with variance σ2. Assuming that the sensors
are dispersed at random over some bounded spatial region
X and the location of each sensor is known following its
deployment, the task of the sensor array is to deliver, over a
rate-limited channel, an approximation Ŷ n of the measurement
vector Y n = (Y1, . . . , Yn) to some central location, where the
vector Xn of the sensor locations and the compressed version
Ŷ n of the sensor measurements will be fed into a learner that
will approximate f0 by some function f̂n(X
n, Ŷ n, ·) from a
given hypothesis class F .
In this paper, we establish information-theoretic upper
bounds on the achievable generalization error in this setting.
In particular, we relate the problem of agnostic learning under
(partial) rate constraints to conditional rate-distortion theory
[3, Section 6.1], [4], [5, Appendix A], which is concerned with
lossy source coding in the presence of side information both at
the encoder and at the decoder. In the set-up shown in Figure 1,
the input part Xn = (X1, . . . , Xn) of the training sequence,
which is available both to the encoder and to the decoder
(hence to the learner), plays the role of the side information,
while the output part Y n = (Y1, . . . , Yn) is to be coded using
a lossy source code operating at the rate of R bits per symbol.
Furthermore, because the distribution of (X,Y ) is known only
to be a member of some family P , the lossy codes must be
robust in the presence of this uncertainty.
Let us formally state the problem. Let P ,F , ℓ be given.
A scheme for agnostic learning under partial rate constraints
(from now on, simply a scheme) operating at rate R is
specified by a sequence of triples {(en, dn, f̂n)}∞n=1, where
en : Xn × Yn → {1, . . . , 2nR} is the encoder, dn : Xn ×
{1, . . . , 2nR} → Yn is the decoder, and f̂n : Xn × Yn → F
is the learner. We shall often abuse notation and let f̂n denote
also the function f̂n(X
n, Ŷ n, ·). For each n, the output of
the learner is a hypothesis f̂n(X
n, Ŷ n, ·) ∈ F , where Ŷ n =
n, en(X
n, Y n)) is the reproduction of Y n given the side
information Xn. For any P ∈ P , the main object of interest
associated with the scheme is the generalization error
L(f̂n, P )
f̂n(X
n, Ŷ n, X), Y
)∣∣∣Xn, Y n
where (X,Y ) ∼ P is assumed independent of {(Xi, Yi)}ni=1
(to keep the notation simple, we suppress the dependence
of the generalization error on the encoder and the decoder).
In particular, we are interested in the achievable values of
the asymptotic expected excess risk. We say that a pair
(R,∆) is achievable for (F ,P , ℓ) if there exists a scheme
{(en, dn, f̂n)}∞n=1 operating at rate R, such that
lim sup
EL(f̂n, P ) ≤ L∗(F , P ) + ∆
for every P ∈ P . After listing the basic assumptions in
Sec. II, we derive in Sec. III sufficient conditions for (R,∆)
to be achievable. We then apply our results to the setting of
nonparametric regression in Sec. IV. Discussion of results and
an outline of future directions are given in Sec. V.
A. Related work
Previously, the problem of statistical estimation from com-
pressed data was considered by Zhang and Berger [6],
Ahlswede and Burnashev [7] and Han and Amari [8] from
the viewpoint of multiterminal information theory. In these
papers, the underlying family of distributions of (X,Y ) is
parametric, i.e., of the form P = {Pθ}θ∈Θ, where Θ is a
subset of Rk for some finite k, and one wishes to estimate
the “true” parameter θ∗. The i.i.d. observations {(Xi, Yi)}ni=1
are drawn from Pθ∗ , and the input part X
n is communicated
to the statistician at some rate R1, while the output part
Y n is communicated at some rate R2. The present work
generalizes to the nonparametric setting the case considered
by Ahlswede and Burnashev [7], namely when R1 = ∞.
To the best of the author’s knowledge, this paper is the
first to consider the problem of nonparametric learning from
compressed observations with side information.
II. ASSUMPTIONS
We begin by stating some basic assumptions on F , P and ℓ.
Additional assumptions will be listed in the sequel as needed.
The input space X is taken to be a measurable subset of Rd,
while the output space is either a finite set (as in classification)
or the set of reals R (as in regression or function estimation).
We assume throughout that the family P of distributions on
X ×Y is such that the mutual information I(X ;Y ) <∞ for
every P ∈ P . All information-theoretic quantities will be in
bits, unless specified otherwise.
We assume that there exists a learning algorithm which
generalizes optimally in the absence of any rate constraints.
Therefore, our standing assumption on (F ,P , ℓ) will be that
the induced function class LF = {ℓf : f ∈ F}, where
ℓf(z)
= ℓ(f(x), y) for all z = (x, y) ∈ Z , satisfies the
uniform law of large numbers (ULLN) for every P ∈ P , i.e.,
∣∣∣∣∣
ℓf (Zi)− E ℓf (Z)
∣∣∣∣∣ → 0, a.s. (2)
where Z,Z1, Z2, . . . are i.i.d. according to P . Eq. (2) implies
that, for any sequence {fn} ⊂ F ,
∣∣∣∣∣
ℓfn(Zi)− E ℓfn(Z)
∣∣∣∣∣ → 0, a.s.
This holds even in the case when each fn is random, i.e.,
fn(·) = fn(Zn, ·). The ULLN is a standard ingredient in
proofs of consistency of learning algorithms: if (F ,P , ℓ) are
such that (2) holds, then the Empirical Risk Minimization
algorithm (ERM), given by
f̂n = argmin
ℓf(Zi),
is PAC in the sense of (1) [2, Theorem 3.2].
Next, we assume that the loss function ℓ has the follow-
ing “generalized Lipschitz” property: there exists a concave,
continuous function η : R+ → R+, such that for all f ∈ F ,
x ∈ X and u, u′ ∈ Y
|ℓ(f(x), u)− ℓ(f(x), u′)| ≤ η(ℓ(u, u′)). (3)
This holds, for example, in the following cases:
• Suppose that ℓ is a metric on Y . Then, by the triangle
inequality we have ℓ(y, u) ≤ ℓ(y, u′) + ℓ(u′, u) for all
y, u, u′ ∈ Y , so (3) holds with η(t) = t.
• Suppose that Y = [0, 1] and ℓ(u, u′) = |u−u′|p for some
p ≥ 1. Then one can show that
|ℓ(f(x), u)− ℓ(f(x), u′)| ≤ p|u− u′|
for all f : X → Y , x ∈ X and u, u′ ∈ Y , so (3) holds
with η(t) = pt1/p.
Finally, we need to pose some assumptions on the metric
structure of the class P with respect to the variational distance
[9, Sec. 5.2], which for any two probability distributions
P1, P2 on a measurable space (Z,A) is defined by
dV (P1, P2)
= 2 sup
|P1(A)− P2(A)|.
A finite set {P1, . . . , PM} ⊂ P is called an (internal) ǫ-net
for P with respect to dV if
1≤m≤M
dV (P, Pm) ≤ ǫ.
The cardinality of a minimal ǫ-net, denoted by N(ǫ,P), is
called the ǫ-covering number of P w.r.t. dV , and the Kol-
mogorov ǫ-entropy of P is defined as H(ǫ,P) △= logN(ǫ,P)
[10]. We assume that the class P satisfies Dobrushin’s entropy
condition [11], i.e., for every c > 0
H(ǫ,P)
= 0. (4)
This condition is satisfied, for example, in the following cases:
(1) X and Y are both finite sets; (2) P is a finite family; (3)
Z is a compact subset of a Euclidean space, and all P ∈ P
are absolutely continuous with densities satisfying a uniform
Lipschitz condition [10], [11].
III. THE RESULTS
To state our results we shall need some notions from condi-
tional rate-distortion theory [3, Sec. 6.1], [4], [5, Appendix A].
Fix some P ∈ P . Given a pair (X,Y ) ∼ P and a nonnegative
real number D, define the set M(D) to consist of all Y-
valued random variables Ŷ jointly distributed with (X,Y ) and
satisfying the constraint E ℓ(Y, Ŷ ) ≤ D, where the expectation
is taken with respect to the joint distribution of X,Y, Ŷ . Then
the conditional rate-distortion function of Y given X w.r.t. P
is defined by
RY |X(D,P )
= inf
I(Y ; Ŷ |X) : Ŷ ∈ M(D)
where I(Y ; Ŷ |X) is the conditional mutual information be-
tween Y and Ŷ given X . Our assumption that I(X ;Y ) <
∞ ensures the existence of RY |X(D,P ) [5]. In operational
terms, RY |X(D,P ) is the minimum number of bits needed
to describe Y with expected distortion of at most D given
perfect observation of a correlated random variable X (the
side information) when (X,Y ) ∼ P . As a function of D,
RY |X(D,P ) is convex and strictly decreasing everywhere it
is finite, hence it is invertible. The inverse function is called
the conditional distortion-rate function of Y given X and is
denoted by DY |X(R,P ). Finally, let
DY |X(R,P)
= sup
DY |X(R,P ).
We assume that DY |X(R,P) <∞ for all R ≥ 0.
We shall also need the following lemma, which can be
proved by a straightforward extension of Dobrushin’s random
coding argument from [11] to the case of side information
available to the encoder and to the decoder:
Lemma 3.1. Let P satisfy Dobrushin’s entropy condition (4).
Assume that the loss function ℓ either is bounded or satisfies
a uniform moment condition
E[ℓ(Y, y0)
1+δ] <∞ (5)
for some δ > 0 with respect to some fixed reference letter
y0 ∈ Y . Then for every rate R ≥ 0 there exists a sequence
{(en, dn)}∞n=1 of encoders en : Xn×Yn → {1, . . . , 2nR} and
decoders dn : Xn × {1, . . . , 2nR} → Yn, such that
lim sup
E ℓn(Y
n, Ŷ n) ≤ DY |X(R,P),
where Ŷ n = dn(X
n, en(X
n, Y n)) and ℓn(Y
n, Ŷ n) =
i=1 ℓ(Yi, Ŷi) is the normalized cumulative loss between
Y n and Ŷ n.
Our main result can then be stated as follows:
Theorem 3.1. Under the stated assumptions, for any R ≥ 0
there exists a scheme {(en, dn, f̂n)} operating at rate R, such
lim sup
EL(f̂n, P ) ≤ L∗(F , P ) + 2η(DY |X(R,P)).
Thus, (R, 2η(DY |X(R,P))) is achievable for every R ≥ 0.
Proof: Given n, Zn ∈ Zn and f ∈ F , define the
empirical risk
L̂Zn(f)
ℓf (Z
and the minimum empirical risk
L̂∗Zn(F)
= inf
L̂Zn(f).
We shall write L̂Xn,Y n(f) and L̂
Xn,Y n(F) whenever we need
to emphasize separately the roles of Xn and Y n.
Suppose that the encoder en and the decoder dn are given.
Let Ŷ n denote the reproduction of Y n given the side infor-
mation Xn, i.e., Ŷ n = dn(X
n, en(X
n, Y n)). We then define
our learner f̂n by
f̂n = argmin
Xn,bY n
(f). (6)
In other words, having received the side information Xn and
the reproduction Ŷ n, the learner performs ERM over F on
{(Xi, Ŷi)}ni=1. Using the property (3) of the loss function ℓ
and the concavity of η, we have the following estimate:
∣∣L̂Xn,Y n(f)− L̂Xn,bY n(f)
≤ sup
∣∣ℓ(f(Xi), Yi)− ℓ(f(Xi), Ŷi)
η(ℓ(Yi, Ŷi))
n, Ŷ n)
. (7)
In particular, this implies that
∣∣L̂Xn,Y n(f̂n)− L̂Xn,bY n(f̂n)
∣∣ ≤ η
n, Ŷ n)
∣∣L̂∗Xn,Y n(F)− L̂∗Xn,bY n(F)
∣∣ ≤ η
n, Ŷ n)
. (9)
We then have
L̂Xn,Y n(f̂n)
Xn,bY n
(f̂n) + η
n, Ŷ n)
= L̂∗
Xn,bY n
(F) + η
n, Ŷ n)
≤ L̂∗Xn,Y n(F) + 2η
n, Ŷ n)
where (a) follows from (8), (b) from the definition of f̂n, and
(c) from (9). Suppose that the data are distributed according
to a particular P ∈ P . Taking expectations and using the
concavity of η and Jensen’s inequality, we obtain
E L̂Zn(f̂n) ≤ E L̂∗Zn(F) + 2η
E ℓn(Y
n, Ŷ n)
Using this bound and the continuity of η, we can write
lim sup
EL(f̂n, P )− L∗(F , P )
≤ lim
L(f̂n, P )− L̂Zn(f̂n)
+ lim
L̂∗Zn(F)− L∗(F , P )
lim sup
E ℓn(Y
n, Ŷ n)
. (10)
The two leading terms on the right-hand side of this inequality
are zero by the ULLN. Moreover, given R, Lemma 3.1
asserts the existence of a sequence {(en, dn)}∞n=1 of encoders
en : Xn × Yn → {1, . . . , 2nR} and decoders dn : Xn ×
{1, . . . , 2nR} → Yn, such that
lim sup
E ℓn(Y
n, Ŷ n) ≤ DY |X(R,P), ∀P ∈ P .
Substitution of this into (10) proves the theorem.
Corollary 3.2. All pairs (R,∆) with ∆ ≥ 2η(DY |X(R,P))
are achievable.
Remark 3.1. In the Appendix, we show that a correspond-
ing lower bound derived by the usual methods for proving
converses in lossy source coding is strictly weaker than
the “obvious” lower bound based on the observation that
EL(f̂n, P ) ≥ L∗(F , P ) for any f̂n. It may be possible to
obtain nontrivial lower bounds in the minimax setting, which
we leave for future work (see also Sec. V).
Remark 3.2. Under some technical conditions on the function
class {ℓf : f ∈ F} (see, e.g., [12]), one can show that
E sup
∣∣∣L̂Zn(f)− L(f, P )
∣∣∣ ≤ C/
n, ∀P ∈ P
for some constant C that depends on F , ℓ. Using this fact and
the same bounding method that led to Eq. (10), but without
taking the limit superior, we can get the following finite-
sample bound for every scheme {(en, dn, f̂n)}∞n=1 with f̂n
given by (6) and arbitrary en, dn:
EL(f̂n, P ) ≤ L∗(F , P ) + 2η
E ℓn(Y
n, Ŷ n)
+ C′/
where C′ = 2C.
The following theorem shows that we can replace condition
(3) with the requirement that ℓ be a power of a metric:
Theorem 3.3. Suppose that the loss function ℓ is of the form
ℓ(y, u) = d(y, u)r for some r ≥ 1, where d is a metric on Y .
Then for any rate R ≥ 0 the scheme constructed in the proof
of Theorem 3.1 is such that
lim sup
L(f̂n, P )
≤ L∗(F , P )1/r + 2DY |X(R,P)1/r
holds for every P ∈ P .
Proof: We proceed essentially along the same lines as in
the proof of Theorem 3.1, except that the bound (7) is replaced
with an argument based on Minkowski’s inequality to yield
L̂Zn(f̂n)
L̂∗Zn(F)1/r
E ℓn(Y
n, Ŷ n)
The rest is immediate using the ULLN as well as concavity
and continuity of t 7→ t1/r for t ≥ 0.
IV. EXAMPLE: NONPARAMETRIC REGRESSION
As an example, let us consider the setting of nonparametric
regression. Let X be a compact subset of Rd and Y = R. The
training data are of the form
Yi = f0(Xi) + Zi, 1 ≤ i ≤ n (11)
where the regression function f0 belongs to some specified
class F of functions from X into [0, 1], the Xi’s are i.i.d. ran-
dom variables drawn from the uniform distribution on X ,
and the Zi’s are i.i.d. zero-mean normal random variables
with variance σ2, independent of Xn. We take ℓ(y, u) =
|y − u|2, the squared loss. Note that ℓ satisfies the condition
of Theorem 3.3 with r = 2.
Because f0 is unknown, we take as the underlying family
P the class of all absolutely continuous distributions with
densities of the form pf (x, y) = V
−1N (y; f(x), σ2), f ∈ F ,
where V is the volume of X and N (y; f(x), σ2) is the one-
dimensional normal density with mean f(x) and variance σ2.
Because the functions in F are bounded between 0 and 1,
it is easy to show that the uniform moment condition (5) of
Lemma 3.1 is satisfied with δ = 1 and y0 = 0.
We suppose that ℓ and F are such that the function class LF
satisfies the ULLN.1 Let Q denote the uniform distribution on
X and for any square-integrable function f on X define the
L2 norm by
‖f‖22,Q
f2(x)dQ(x) ≡ 1
f2(x)dx.
Let us denote by N2,Q(ǫ,F) the ǫ-covering number of F w.r.t.
‖ · ‖2,Q, i.e., the smallest number M such that there exist M
functions {fm}Mm=1 in F satisfying
1≤m≤M
‖f − fm‖2,Q ≤ ǫ.
We assume that F is such that for every c > 0
logN2,Q(ǫ,F)
= 0. (12)
This condition holds, for example, if the functions in F are
uniformly Lipschitz or if X is a bounded interval in R and F
consists of functions satisfying a Sobolev-type condition [10].
Lemma 4.1. If F satisfies (12), then P satisfies Dobrushin’s
entropy condition (4).
Proof: Given f ∈ F , let Pf denote the distribution with
the density pf . It is straightforward to show that
I(Pf‖Pg) =
‖f − g‖22,Q, ∀f, g ∈ F
where I(·‖·) is the relative entropy (information divergence)
between two probability distributions, in nats. Using Pinsker’s
inequality dV (P1, P2) ≤
2I(P1‖P2) [9, Lemma 5.2.8], we
dV (Pf‖Pg) ≤
‖f − g‖2,Q, ∀f, g ∈ F . (13)
Given ǫ > 0, let {fm}Mm=1 ⊂ F be a σǫ-net for F w.r.t. ‖·‖2,Q.
Then from (13) it follows that
1≤m≤M
dV (Pf , Pfm) ≤ sup
1≤m≤M
‖f − fm‖2,Q
1See Györfi et al. [13] for a detailed exposition of the various conditions
when this is true.
i.e., {Pfm}Mm=1 is an ǫ-net for P w.r.t. dV . This implies, in
particular, that N(ǫ,P) ≤ N2,Q(σǫ,F) for every ǫ > 0. This,
together with (12), proves the lemma.
Lemma 4.2. For any R ≥ 0, DY |X(R,P) = σ22−2R.
Proof: Fix some f ∈ F and consider a pair (X,Y ) ∼
Pf . Then Y = f(X) + Z , where Z ∼ Normal(0, σ2)
is independent of X . Because ℓ is a difference distortion
measure, Theorem 7 of [4] says that, for any measurable
function ψ : X → Y ,
DY |X(R,Pf ) = DY−ψ(X)|X(R,Pf−ψ),
where Pf−ψ is the distribution of
Y − ψ(X) ≡ f(X)− ψ(X) + Z;
furthermore, if Y − ψ(X) is independent of X , then
DY |X(R,Pf ) = DY−ψ(X)(R), the (unconditional) distortion-
rate function of Y − ψ(X). Taking ψ = f , we get
DY |X(R,Pf ) = D(R, σ
2), the distortion-rate function of a
memoryless Gaussian source with variance σ2 w.r.t. squared
error loss, which is equal to σ22−2R [3, Theorem 9.3.2]. Hence
DY |X(R,Pf ) is independent of f . Taking the supremum over
F finishes the proof.
Now we can state and prove the main result of this section:
Theorem 4.1. Consider the regression setting of (11). Under
the stated assumptions, for any R ≥ 0 there exists a scheme
{(en, dn, f̂n)}∞n=1, such that
lim sup
L(f̂n, Pf )
≤ σ(1 + 2−R+1) (14)
holds for every f ∈ F .
Proof: As follows from the above, the triple (F ,P , ℓ)
satisfies all the assumptions of Theorem 3.3. Therefore for any
R ≥ 0 there exists a scheme {(en, dn, f̂n)}∞n=1 operating at
rate R, such that
lim sup
L(f̂n, Pf )
≤ L∗(F , Pf )1/2 + 2−R+1σ, (15)
holds for every f ∈ F (we have also used Lemma 4.2). It is
not hard to show that
L(g, Pf) = ‖f − g‖22,Q + σ2, ∀f, g ∈ F ,
whence it follows that L∗(F , Pf ) = σ2 for every f ∈ F .
Substituting this into (15), we get (14).
V. DISCUSSION AND FUTURE WORK
We have derived information-theoretic bounds on the
achievable generalization error in learning from compressed
data (with side information). There is a close relationship
between this problem and the theory of robust lossy source
coding with side information at the encoder and the decoder.
A major difference between this setting and the usual set-
ting of learning theory is that the techniques are no longer
distribution-free because restrictions must be placed on the
underlying family of distributions in order to guarantee the
existence of a suitable source code. The theory was applied to
the problem of nonparametric regression in Gaussian noise,
where we have shown that the penalty incurred for using
compressed observations decays exponentially with the rate.
We have proved Theorems 3.1 and 3.3 by adopting ERM
as our learning algorithm and optimizing the source code to
deliver the best possible reconstruction of the training data. In
effect, this imposes a separation structure between learning
and source coding. While this “modular” approach is simplistic
(clearly, additional performance gains could be attained by
designing the encoder, the decoder and the learner jointly), it
may be justified in such applications as remote sensing. For
instance, if the source code and the learner were designed
jointly, then any change made to the hypothesis class (say,
if we decided to replace the currently used hypothesis class
with another based on tracking the prior performance of the
network) might call for a complete redesign of the source code
and the sensor network, which may be a costly step. With the
modular approach, no such redesign is necessary: one merely
makes the necessary adjustments in the learning algorithm,
while the sensor network continues to operate as before.
Let us close by sketching some directions for future work.
First of all, it would be of interest to derive information-
theoretic lower bounds on the generalization performance
of rate-constrained learning algorithms. In particular, just as
Ahlswede and Burnashev had done in the parametric case [7],
we could study the asymptotics of the ninimax excess risk
δn(R)
= inf
(en,dn, bfn)
EL(f̂n, P )− L∗(F , P )
where the infimum is over all encoders, decoders and learners
operating on a length-n training sequence at rate R. Secondly,
we could dispense with the assumption that the learner has
perfect observation of the input part of the training sample, in
analogy to the situation dealt with by Zhang and Berger [6].
Finally, keeping in mind the motivating example of sensor
networks, it would be useful to replace the block coding
approach used here with an efficient distributed scheme.
ACKNOWLEDGMENTS
Discussions with Todd Coleman are gratefully acknowledged.
This work was supported by the Beckman Fellowship.
APPENDIX
Let us assume for simplicity that P is a singleton, P = {P},
and that Y is a finite set. Consider a scheme {(en, dn, f̂n)}
operating at rate R. Fix n and define the n-tuple Wn via
= f̂n(X
n, Ŷ n, Xi), 1 ≤ i ≤ n.
Also, let J = en(X
n, Y n). Then we can write
nR ≥ H(J |Xn)
≥ H(Ŷ n|Xn)
≥ I(Ŷ n;Y n|Xn)
= H(Y n|Xn)−H(Y n|Xn, Ŷ n)
= H(Y n|Xn)−H(Y n|Xn, Ŷ n,Wn) (A.1)
[H(Yi|Xi)−H(Yi|Xn, Ŷ n,Wn, Y i−1)]
[H(Yi|Xi)−H(Yi|Xi,Wi)]
I(Yi;Wi|Xi)
RY |X(E ℓ(Wi, Yi), P )
≥ nRY |X(E ℓn(Wn, Y n), P ),
where (A.1) follows from the fact that Wn is a function
of Ŷ n and Xn. The remaining steps follow from standard
information-theoretic identities and from convexity. Therefore,
lim inf
E ℓn(W
n, Y n) ≥ DY |X(R,P ).
Because EL(f̂n, P ) = E ℓn(W
n, Y n) + o(1) by the ULLN,
lim inf
EL(f̂n, P ) ≥ DY |X(R,P ). (A.2)
Now, given any f ∈ F , we can interpret f(X) as a zero-rate
approximation of Y (using only the side information X), so
L(f, P ) ≥ DY |X(0, P ) ≥ DY |X(R,P ) for any R ≥ 0. In
particular, L∗(F , P ) ≥ DY |X(R,P ) for all R, and
lim inf
EL(f̂n, P ) ≥ L∗(F , P ) ≥ DY |X(R,P )
for all R. Thus, the information-theoretic lower bound (A.2)
is weaker than the bound lim inf
EL(f̂n, P ) ≥ L∗(F , P ).
REFERENCES
[1] D. Haussler, “Decision-theoretic generalizations of the PAC model for
neural net and other learning applications,” Inform. Comput., vol. 100,
pp. 78–150, 1992.
[2] M. Vidyasagar, Learning and Generalization, 2nd ed. London:
Springer-Verlag, 2003.
[3] T. Berger, Rate Distortion Theory. Englewood Cliffs, NJ: Prentice-Hall,
1971.
[4] R. M. Gray, “Conditional rate-distortion theory,” Stanford Electronics
Laboratories, Tech. Rep. 6502-2, 1972.
[5] A. D. Wyner, “The rate-distortion function for source coding with side
information at the decoder II: general sources,” Inform. Control, vol. 38,
pp. 60–80, 1978.
[6] Z. Zhang and T. Berger, “Estimation via compressed information,” IEEE
Trans. Inform. Theory, vol. 34, no. 2, pp. 198–211, March 1988.
[7] R. Ahlswede and M. V. Burnashev, “On minimax estimation in the
presence of side information about remote data,” Ann. Statist., vol. 18,
no. 1, pp. 141–171, 1990.
[8] T. S. Han and S. Amari, “Statistical inference under multiterminal data
compression,” IEEE Trans. Inform. Theory, vol. 44, no. 6, pp. 2300–
2324, October 1998.
[9] R. M. Gray, Entropy and Information Theory. New York: Springer-
Verlag, 1990.
[10] A. N. Kolmogorov and V. M. Tihomirov, “ǫ-entropy and ǫ-capacity of
sets in function spaces,” in Amer. Math. Soc. Transl., ser. 2, 1961, vol. 17,
pp. 277–364.
[11] R. L. Dobrushin, “Unified methods for optimal quantization of mes-
sages,” in Problemy Kibernetiki, A. A. Lyapunov, Ed. Moscow: Nauka,
1970, vol. 22, pp. 107–156, in Russian.
[12] S. Mendelson, “A few notes on statistical learning theory,” in Advanced
Lectures in Machine Learning, ser. Lecture Notes in Computer Science,
S. Mendelson and A. J. Smola, Eds. Springer, 2003, vol. 2600, pp.
1–40.
[13] L. Györfi, M. Kohler, A. Krzyżak, and H. Walk, A Distribution-Free
Theory of Nonparametric Regression. New York: Springer, 2002.
	Introduction and problem statement
	Related work
	Assumptions
	The results
	Example: nonparametric regression
	Discussion and future work
	Appendix
	References
