Generalization in Machine Learning via Analytical Learning Theory

Kenji Kawaguchi
Massachusetts Institute of Technology

arXiv:1802.07426v1 [stat.ML] 21 Feb 2018

Abstract
This paper introduces a novel measure-theoretic
learning theory to analyze generalization behaviors of practical interest. The proposed learning
theory has the following abilities: 1) to utilize
the qualities of each learned representation on
the path from raw inputs to outputs in representation learning, 2) to guarantee good generalization errors possibly with arbitrarily rich hypothesis spaces (e.g., arbitrarily large capacity and
Rademacher complexity) and non-stable/nonrobust learning algorithms, and 3) to clearly distinguish each individual problem instance from
each other. Our generalization bounds are relative to a representation of the data, and hold
true even if the representation is learned. We
discuss several consequences of our results on
deep learning, one-shot learning and curriculum
learning. Unlike statistical learning theory, the
proposed learning theory analyzes each problem
instance individually via measure theory, rather
than a set of problem instances via statistics. Because of the differences in the assumptions and
the objectives, the proposed learning theory is
meant to be complementary to previous learning
theory and is not designed to compete with it.

1. Introduction
Statistical learning theory provides tight and insightful results under its assumptions and for its objectives (e.g., Vapnik 1998; Mukherjee et al. 2006; Mohri et al. 2012). As the
training datasets are considered as random variables, statistical learning theory was initially more concerned with the
study of data-independent bounds based on the capacity of
the hypothesis space (Vapnik, 1998), or the classical stability of learning algorithm (Bousquet & Elisseeff, 2002).
Given the observations that these data-independent bounds
could be overly pessimistic for a “good” (training) dataset,
data-dependent bounds have also been developed in statistical learning theory, such as the luckiness framework
(Shawe-Taylor et al., 1998; Herbrich & Williamson, 2002),
empirical Rademacher complexity of a hypothesis space
(Koltchinskii & Panchenko, 2000; Bartlett et al., 2002), and
the robustness of learning algorithm (Xu & Mannor, 2012).

Yoshua Bengio
University of Montreal, CIFAR Fellow
Along this line of reasoning, we notice that the previous
bounds, including data-dependent ones, can be pessimistic
for a “good” problem instance, which is defined by a tuple
of a true (unknown) measure, datasets and a learned model
(see Section 3 for further details). Accordingly, this paper
proposes a learning theory designed to be strongly dependent on each individual problem instance. To achieve this
goal, we directly analyse the generalization gap (difference
between expected error and empirical error) and datasets
as non-statistical objects via measure theory. This is in
contrast to the setting of statistical learning theory wherein
these objects are treated as random variables.
The non-statistical nature of our proposed theory can be of
practical interest on its own merits. For example, the nonstatistical nature captures well a situation wherein a dataset
to learn a model is specified and fixed first (e.g., a UCL
dataset, ImageNet, a medical image dataset, etc.), rather
than remaining random with a certain distribution. Once
a dataset is actually specified, there is no randomness remaining over the dataset (although one can artificially create randomness via an empirical distribution). For example, Zhang et al. (2017) empirically observed that given a
fixed (deterministic) dataset (i.e., each of CIFAR10, ImageNet, and MNIST), test errors can be small despite the
large capacity of hypothesis space and a possible instability
of the learning algorithm. Understanding and explaining
this empirical observation has become an active research
area (Arpit et al., 2017; Krueger et al., 2017; Hoffer et al.,
2017; Wu et al., 2017; Dziugaite & Roy, 2017; Dinh et al.,
2017; Bartlett et al., 2017; Brutzkus et al., 2017).
For convenience within this paper, the proposed theory is
called analytical learning theory, due to its non-statistical
nature. A firm understanding of analytical learning theory
might be conceptually challenging, as it requires a different
style of thinking and a shift of technical basis from statistics (e.g., concentration inequalities) to measure theory. We
present the foundation of analytical learning theory in Section 3, several applications in Sections 4-5, and additional
discussions in Section 6.

2. Preliminaries
In machine learning, a typical goal is to return a model
ŷA(Sm ) via a learning algorithm A given a dataset

Generalization in Machine Learning via Analytical Learning Theory

Sm = {s(1) , . . . , s(m) } such that the expected error
Eμ [LŷA(Sm ) ] , Ez [LŷA(Sm ) (z)] with respect to a true
(unknown) normalized measure μ is minimized. Here, Lŷ
is a function that combines a loss function ` and a model
ŷ; e.g., in supervised learning, Lŷ(z) = `(ŷ(x), y), where
z = (x, y) is a pair of an input x and a target y. Because
the expected error Eμ [LŷA(Sm ) ] is often not computable,
we usually approximate the expected error by an empiriP m0
cal error ÊZm0 [LŷA(Sm ) ] , m10 i=1 LŷA(Sm ) (z (i) ) with
0
a dataset Zm0 = {z (1) , . . . , z (m ) }. Accordingly, we define
the generalization gap , Eμ [LŷA(Sm ) ] − ÊZm0 [LŷA(Sm ) ],
where the case of Zm0 = Sm is of particular interest (e.g.,
in the empirical risk minimization). One of the goals of
learning theory is to explain and validate when and how
minimizing ÊSm [LŷA(Sm ) ] is a sensible approach to minimizing Eμ [LŷA(Sm ) ] by analyzing the generalization gap.
2.1. Discrepancy and variation
In the following, we define a quality of a dataset, called
discrepancy, and a quality of a function, called variation
in the sense of Hardy and Krause. These definitions have
been used in harmonic analysis, number theory, and numerical analysis (Krause, 1903; Hardy, 1906; Hlawka, 1961;
Niederreiter, 1978; Aistleitner et al., 2017). This study
adopts these definitions in the context of machine learning. Intuitively, the star-discrepancy D∗ [Tm , ν] evaluates
how well a dataset Tm = {t(1) , . . . , t(m) } captures a normalized measure ν, and the variation V [f ] in the sense of
Hardy and Krause computes how a function f varies in
total w.r.t. each small perturbation of every cross combination of its variables.
Discrepancy of dataset with respect to a measure. For
any t = (t1 , . . . , td ) ∈ [0, 1]d , let Bt , [0, t1 ] × ∙ ∙ ∙ ×
[0, td ] be a closed axis-parallel box with one vertex at the
origin. The local discrepancy D[Bt ; Tm , ν] of a dataset
Tm = {t(1) , . . . , t(m) } with respect to a normalized Borel
measure ν on a set Bt is defined as
m

1 X
D[Bt ; Tm , ν] ,
1Bt (t(i) ) − ν Bt
m i=1

where 1Bt is the indicator function of a set Bt . Figure 1 in Appendix A.1 shows an illustration of the local
discrepancy D[Bt ; Tm , ν] and related notation. The stardiscrepancy D∗ [Tm , ν] of a dataset Tm = {t(1) , . . . , t(m) }
with respect to a normalized Borel measure ν is defined as
D ∗ [Tm , ν] , sup

D[Bt ; Tm , ν] .

t∈[0,1]d

Variations of a function. Let ∂l be the partial derivative
operator; that is, ∂l g(t1 , . . . , tk ) is the partial derivative of
a function g with respect to the l-th coordinate at a point
(t1 , . . . , tk ). Let ∂1,...,k , ∂1 , . . . , ∂k . A partition P of
P
[0, 1]k with size mP
1 , . . . , mk is a set of finite sequences

(0)

(mP
l )

(1)

tl , t l . . . , t l

(mP
l )

(1)
tl

(0)

(l = 1, . . . , k) such that 0 = tl

≤

≤ ∙ ∙ ∙ ≤ tl
= 1 for l = 1, . . . , k. We define a difference operator ΔP
l with respect to a partition P as: given
(i)
a function g and a point (t1 , . . . tl−1 , tl , tl+1 , . . . , tk ) in
the partition P (for i = 0, . . . , mP
l − 1),
(i)

ΔP
l g(t1 , . . . tl−1 , tl , tl+1 , . . . , tk )
(i+1)

= g(t1 , . . . tl−1 , tl

, tl+1 , . . . , tk )

(i)

− g(t1 , . . . tl−1 , tl , tl+1 , . . . , tk ),
(i+1)

, tl+1 , . . . , tk ) is the subsequent
where (t1 , . . . tl−1 , tl
point in the partition P along the coordinate l. Let
P
P
ΔP
1,...,k , Δ1 . . . Δk . Given a function f of d variables, let fj1 ...jk be the function restricted on k ≤ d variables such that fj1 ...jk (tj1 , . . . , tjk ) = f (t1 , . . . , td ), where
tl ≡ 1 for all l ∈
/ {j1 , j2 , . . . jk }. That is, fj1 ...jk is a
function of (tj1 , . . . , tjk ) with other original variables being fixed to be one. The variation of fj1 ...jk on [0, 1]k in
the sense of Vitali is defined as
V (k) [fj1 ...jk ]
, sup

mP
1 −1

X

P ∈Pk i =1
1

∙∙∙

mP
k −1

X

(i )

(i )

1
k
ΔP
1,...,k fj1 ...jk (tj1 , . . . , tjk ) ,

ik =1

where Pk is the set of all partitions of [0, 1]k . The variation
of f on [0, 1]d in the sense of Hardy and Krause is defined
as
d
X
X
V [f ] =
V (k) [fj1 ...jk ].
k=1 1≤j1 <∙∙∙<jk ≤d

The following proposition might be helpful in intuitively
understanding the concept of the variation as well as in
computing it when applicable. All the proofs in this paper
are presented in Appendix B.
Proposition 1. Suppose that fj1 ...jk is a function for which
∂1,...,k fj1 ...jk exists on [0, 1]k . Then,
V (k) [fj1 ...jk ] ≤

sup
(tj1 ,...,tj )∈[0,1]k
k

|∂1,...,k fj1 ...jk (tj1 , . . . , tjk )| .

If ∂1,...,k fj1 ...jk is also continuous on [0, 1]k ,
V (k) [fj1 ...jk ] =

Z

[0,1]k

|∂1,...,k fj1 ...jk (tj1 , ..., tjk )| dtj1 ∙ ∙ ∙ dtjk .

3. A basis of analytical learning theory
This study considers the problem of analyzing the generalization gap Eμ [LŷA(Sm ) ] − ÊZm0 [LŷA(Sm ) ], including the case of Zm0 = Sm . Whenever we write Zm0 ,
it is always including the case of Zm0 = Sm . With our
notation, one can observe that the generalization gap is
fully and deterministically specified by a tuple or a problem instance (μ, Sm , Zm0 , LŷA(Sm ) ), where we identify

Generalization in Machine Learning via Analytical Learning Theory

Table 1. A simplified comparison, wherein GG denotes the generalization gap

GG is characterized by
GG is decomposed via
Statistical assumption
Relative advantage when
Relative advantage in

Statistical Learning Theory
hypothesis space H or learning algorithm A
statistics
is required
a (training) dataset Sm remains random
worst-case analysis

an omitted measure space (Z, Σ, μ) by the measure μ
for brevity. Indeed, the expected error is defined by the
Lebesgue integral of a function LŷA(Sm ) on a (unknown)
normalized
measure space (Z, Σ, μ) as Eμ [LŷA(Sm ) ] =
R
Lŷ
dμ, which is a deterministic mathematical obA(S
)
m
Z
ject. Accordingly, we introduce the following notion of
strong instance-dependence:
– A mathematical object ϕ in the theory of the generalization gap of the tuple (μ, Sm , Zm0 , LŷA(Sm ) ) is said to be
strongly instance-dependent if the object ϕ is invariant under any change of any mathematical object that contains or
depends on any μ
ˉ 6= μ, any ŷ 6= ŷA(Sm ) , or any Sˉm such
ˉ
that Sm 6= Sm and Sˉm 6= Zm0 .

Any generalization bound that depends on a non-singleton
hypothesis space H 6= {ŷA(Sm ) }, such as ones with
Rademacher complexity and VC dimension, is not strongly
instance-dependent because the non-singleton hypothesis
space contains ŷ 6= ŷA(Sm ) , and the bound is not invariant under an arbitrary change of H. The definition of stability itself depends on Sˉm that is not equal to Sm and
Zm0 (Bousquet & Elisseeff, 2002), making the corresponding bounds be not strongly instance-dependent. Moreover,
a generalization bound that depends on a concept of random datasets Sˉp
m different from Sm and Zm0 (e.g., an additive term O( 1/m) that measures a deviation from an
expectation over Sˉm 6= Sm , Zm0 ) is not strongly instancedependent, because the bound is not invariant under an arbitrary change of Sˉm .
Data dependence does not imply strong instancedependence. For example, in the data-dependent bounds of
the luckiness framework (Shawe-Taylor et al., 1998; Herbrich & Williamson, 2002), the definition of ω-smallness
of the luckiness function contains a non-singleton hypothesis space H, a sequence of non-singleton hypothesis spaces
(ordered in a data-dependent way by a luckiness function),
and a supremum over H with the probability over datasets
Sˉm 6= Sm (with Zm0 = Sm ) (e.g., see Definition 4 in Herbrich & Williamson 2002 with contraposition). The datadependent bounds with empirical Rademacher complexity
(Koltchinskii & Panchenko, 2000; Bartlett et al., 2002) also
depend on a non-singleton hypothesis space and its empirical Rademacher complexity. These bounds can be made
more data-dependent by considering a sequence of hypothesis spaces instead, but such data-dependent bounds still

Analytical Learning Theory
a learned model ŷA(Sm )
measure theory
can be additionally used
a (training) dataset Sm is specified
beyond worst-case analysis

contain the complexity of a non-singleton hypothesis space
(and its ordering). Moreover, the definition of robustness
itself depends on Sˉm , which is not equal to Sm or Zm0 (Xu
& Mannor, 2012). Therefore, all of these data-dependent
bounds are not strongly instance-dependent.
Analytical learning theory is designed to be strongly
instance-dependent. To achieve this goal, unlike statistical
learning theory, analytical learning theory directly analyzes
the (deterministic) mathematical object Eμ [LŷA(Sm ) ] −
ÊZm0 [LŷA(Sm ) ]. Because of the difference in the settings
and the aims, analytical learning theory is not designed
to compete with previous learning theory results, which
are based on a statistical viewpoint. Table 1 summarizes
the major simplified differences between statistical learning theory and analytical learning theory, as the rest of this
paper clarifies these differences. See Appendix A.2 for a
graphical illustration of the difference.
3.1. Analytical decomposition of expected error
Let (Z, Σ, μ) be any (unknown) normalized
R measure space
that defines the expected error, Eμ [Lŷ] = Z Lŷ dμ. Here,
the measure space may correspond to an input-target pair as
Z = X × Y for supervised learning, the generative hidden
space Z of X × Y for unsupervised / generative models,
or anything else of interest (e.g., Z = X ). Let T∗ μ be the
pushforward measure of μ under a map T . Let T (Zm0 ) =
0
{T (z (1) ), . . . , T (z (m ) )} be the image of the dataset Zm0
under T . Let |ν|(E) be the total variation of a measure ν
on E. For vectors a, b ∈ [0, 1]d , let [a, b] = {t ∈ [0, 1]d :
a ≤ t ≤ b}, where ≤ denotes the product order; that is,
a ≤ t if and only if aj ≤ tj for j = 1, . . . , d. This study
adopts the convention that the infimum of the empty set is
positive infinity.
Theorem 1 is introduced to exploit the various structures in machine learning through the decomposition
LŷA(Sm ) (z) = (f ◦ T )(z) where T (z) is the output of
a representation function and f outputs the associated loss.
Here, T (z) can be any intermediate representation on the
path from the raw data (when T (z) = z) to the output
(when T (z) = Lŷ(z)). The proposed theory holds true
even if the representation T (z) is learned, or even if the
decomposition (f ◦ T ) is unknown. The empirical error
ÊZm0 [LŷA(Sm ) ] can be the training error with Zm0 = Sm
or the test/validation error with Zm0 6= Sm . We can
also set Sm to be the whole training-validation-test dataset

Generalization in Machine Learning via Analytical Learning Theory

with Zm0 = Sm or Zm0 being any other dataset. While
Zm0 ⊆ Z (to define the ÊZm0 [LŷA(Sm ) ]), a dataset Sm is
arbitrary and Sm * Z is allowed when Zm0 6= Sm .
Theorem 1. For any Lŷ, let F [Lŷ] be a set of all pairs
(T , f ) such that T : (Z, Σ) → ([0, 1]d , B([0, 1]d )) is a
measurable function, f : ([0, 1]d , B([0, 1]d )) → (R, B(R))
is of bounded variation as V [f ] < ∞, and
Lŷ(z) = (f ◦ T )(z)

for all z ∈ Z,

where B(A) indicates the Borel σ-algebra on A. Then, for
any dataset pair (Sm , Zm0 ) (including Zm0 = Sm ) and any
LŷA(Sm ) ,
(i) Eμ [LŷA(Sm ) ]

≤ ÊZm0 [LŷA(Sm ) ] + inf

(T ,f )∈F̂

V [f ]D∗ [T∗ μ, T (Zm0 )],

where F̂ = F [LŷA(Sm ) ], and
(ii) for any (T , f ) ∈ F [LŷA(Sm ) ] such that f is rightcontinuous component-wise,
Eμ [LŷA(Sm ) ] − ÊZm0 [LŷA(Sm ) ]


Z
m0
X
1
(T∗ μ)([0, t]) −
1[0,t] (T (zi )) dνf (t),
=
m0 i=1
[0,1]d

where zi ∈ Zm0 , and νf is a signed measure corresponding to f as f (t) = νf ([t, 1]) + f (1) and
|νf |([0, 1]d ) = V [f ].

Theorem 1 holds for each individual instance
(μ, Sm , Zm0 , LŷA(Sm ) ), for example, without taking
a supremum over a set of other instances. In contrast,
typically in previous bounds, when asserting that an upper
bound holds on Eμ [Lŷ] − ÊSm [Lŷ] for any ŷ ∈ H (with
high probability), what it means is that the upper bound
holds on supŷ∈H (Eμ [Lŷ] − ÊSm [Lŷ]) (with high probability). Thus, in classical bounds including data-dependent
ones, as a H gets larger and more complex, the bounds
tend to become more pessimistic for the actual instance
ŷA(Sm ) (learned with the actual instance Sm ).
Remark 1. The bound and the equation in Theorem 1 are
strongly instance-dependent, and in particular, invariant to
hypothesis spaces H and the properties of learning algorithm A over datasets different from a given dataset Sm
(and Zm0 ) (e.g., stability and robustness). They are fully
determined by each given instance (μ, Sm , Zm0 , LŷA(Sm ) )
without dependence on other instances.
Remark 2. Theorem 1 together with Remark 1 has a significant consequence in practice. For example, even if the
true model is contained in some “small” hypothesis space
H1 , we might want to use a much more complex “larger”
hypothesis space H2 in practice such that the optimization
becomes easier and the training trajectory reaches a better

model ŷA(Sm ) in the end of the learning process (e.g., overparameterization in deep learning potentially makes the
non-convex optimization easier; see Dauphin et al. 2014;
Choromanska et al. 2015; Soudry & Hoffer 2017). This
is consistent with both Theorem 1 and practical observations in deep learning, although it can be puzzling from
the viewpoint of previous results that explicitly or implicitly penalizes the use of more complex “larger” hypothesis
spaces (e.g., see Zhang et al. 2017).
Remark 3. The reason why both analytical learning theory and certain practical observations can possibly obtain
results that might appear to contradict statistical learning
theory is the difference in the settings or the sets of assumptions. The larger complexities of a hypothesis space and instability/nonrobustness (or other properties of the learning
algorithm) indeed degrade the statistical guarantee over different random problem instances particularly with a worstcase distribution μ
ˉ 6= μ; however, it can improve the analytical guarantee and practical performances for “good”
problem instances (μ, Sm , Zm0 , LŷA(Sm ) ).
For example, no free lunch theorems in machine learning
are well-known results, typically proven with the worstcase distribution μ
ˉ 6= μ for a fixed A or H over random
different instances, rather than each individual instance
(μ, Sm , Zm0 , LŷA(Sm ) ).
3.2. Additionally using statistical assumption and
general bounds on D ∗
By additionally using the standard i.i.d. assumption,
Proposition 2 provides a general bound on the stardiscrepancy D∗ [T∗ μ, T (Zm0 )] that appears in Theorem 1.
Proposition 2 is a direct consequence of (Heinrich et al.,
2001, Theorem 2).
0

Proposition 2. Let T (Zm0 ) = {T (z (1) ), . . . , T (z (m ) )} =
0
{t(1) , . . . , t(m ) } be a set of i.i.d. random variables with
values on [0, 1]d and distribution T∗ μ. Then, there exists
a positive constant c1 such that for all m0 ∈ N+ and all
c2 ≥ c1 , with probability at least 1 − δ,
r
d
∗
D [T∗ μ, T (Zm0 )] ≤ c2
m0
where δ =

c2

1
√

2

d

2

(c1 c22 e−2c2 )d with c1 c22 e−2c2 < 1.

Remark 4. Proposition 2 is not probabilistically vacuous
in the sense that we can increase c2 to obtain 1 − δ > 0, at
the cost of increasing the constant c2 in the bound. Forcing
1 − δ > 0 still keeps c2 constant without dependence on
relevant variables such as d and m0 . This is because 1 −
2
δ > 0 if c2 is large enough such that c1 c22 < e2c2 , which
depends only on the constants.
Using Proposition 2, one can immediately provide a statistical bound via Theorem 1 over random Zm0 . To see
how such a result differs from that of statistical learning
theory, consider the case of Zm0 = Sm . Whereas statistical

Generalization in Machine Learning via Analytical Learning Theory

learning theory applies a statistical assumption to the whole
object Eμ [LŷA(Sm ) ] − ÊSm [LŷA(Sm ) ], analytical learning
theory first decomposes Eμ [LŷA(Sm ) ] − ÊSm [LŷA(Sm ) ]
into V [f ]D ∗ [T∗ μ, T (Sm )] and then applies the statistical
assumption only to D ∗ [T∗ μ, T (Sm )]. This makes V [f ]
strongly instance-dependent even with the statistical assumption. For example, with f (z) = LŷA(Sm ) (z) and
T (z) = z, if the training dataset Sm satisfies the standard
i.i.d. assumption, we have that with high probability,
q
d
Eμ [LŷA(Sm ) ] − ÊSm [LŷA(Sm ) ] ≤ c2 V [LŷA(Sm ) ] m
, (1)
where the term V [LŷA(Sm ) ] is strongly instancedependent. Indeed, in this case, the whole bound in
Equation (1) is strongly instance-dependent. See Appendix
A.3 for a conceptual discussion of using a statistical
assumption when Zm0 = Sm .

In Equation (1), it is unnecessary for m to approach infinity in order for the generalization gap to go to zero. This is
because it is multiplied by V [LŷA(Sm ) ], which is a quality
of a learned model ŷA(Sm ) . This strongly supports the concept of one-shot learning, in contrast to traditional results.
For the purpose of the non-statistical decomposition of
Eμ [LŷA(Sm ) ] − ÊSm [LŷA(Sm ) ], instead of Theorem 1, we
might be tempted to conduct a simpler decomposition with
the Hölder inequality or its variants. However, such a simpler decomposition is dominated by a difference between
the true measure and the empirical measure on an arbitrary set in high-dimensional space, which suffers from the
curse of dimensionality. Indeed, the proof of Theorem 1
is devoted to reformulating Eμ [LŷA(Sm ) ] − ÊSm [LŷA(Sm ) ]
via the equivalence in the measure and the variation before
taking any inequality, so that we can avoid such an issue.
That is, the star-discrepancy evaluates the difference in the
measures on high-dimensional boxes with one vertex at the
origin, instead of on an arbitrary set.
The following proposition proves the existence of a dataset
Zm0 with a convergence rate that is asymptotically faster in
terms of the dataset size m0 . This is a direct consequence
of (Aistleitner & Dick, 2014, Theorem 2).
Proposition 3. Assume that T is a surjection. Let T∗ μ
be any (non-negative) normalized Borel measure on [0, 1]d .
Then, for any m0 ∈ N+ , there exists a dataset Zm0 such
that
√ (2 + log2 m0 )(3d+1)/2
D ∗ [T∗ μ, T (Zm0 )] ≤ 63 d
.
m0

4. Linear models possibly with rich
hypothesis spaces, algorithmic instability
and nonrobustness
Even in the classical setting of linear regression models,
recent papers (Zhang et al. 2017, Section 5; Kawaguchi

et al. 2017, Section 3; Poggio et al. 2017, Section 5) point
out the need for further theoretical studies to better understand precisely what makes a learned model generalize
well. Moreover, numerous related papers, even with their
focus on deep learning, essentially ask the open question of
understanding generalization with rich hypothesis spaces,
algorithmic instability and nonrobustness (e.g., see Bartlett
et al. 2017), which is applicable to linear models.
Theorem 1 with Remarks 1-3 answers the above open question abstractly for machine learning and deep learning in
general. This section provides a more concrete answer for
the case of linear models, which is a simple case that still
captures the essence of the question.
Let Sm = {s(i) }m
i=1 be the training dataset of the inputtarget pairs as s(i) = (x(i) , y (i) ). Let ŷA(Sm ) = Ŵ φ(∙) be
the learned model at the end of any training process. For
example, in empirical risk minimization, Ŵ is an output of
the training process, Ŵ := minimizeW ÊSm [ 12 kW φ(x) −
yk22 ]. Here, φ : (X , Σx ) → ([0, 1]dφ , B([0, 1]dφ )) is any
normalized measurable function, corresponding to fixed
features. For any given variable v, let dv be the dimensionality of the variable v. The goal is to minimize the expected
error Es [ 12 kŴ φ(x) − yk22 ] of the learned model Ŵ φ(∙).
4.1. Domains with structured labels
In this subsection only, we assume that the target output y
is structured such that y = W ∗ φ(x) + ξ, where ξ is a zeromean random variable independent of x. Many columns
of W ∗ can be zeros (i.e., sparse) such that W ∗ φ(x) uses a
small portion of the feature vector φ(x). Thus, this structured label assumption can be satisfied by including a sufficient number of elements from a basis with uniform approximation power (e.g., polynomial basis, Fourier basis, a
set of step functions, etc.) to the feature vector φ(x) up to
a desired approximation error. Note that we do not assume
any knowledge of W ∗ .
Let μx be the (unknown) normalized measure for the input
x (corresponding to the marginal distribution of (x, y)). Let
(i) (i) m
Xm = {x(i) }m
i=1 and S̃m = {(x , ξ )}i=1 be the input
part and the (unknown) input-noise part of the same training dataset as Sm , respectively. We do not assume access
to S̃m . Let Wl be the l-th column of the matrix W .
Theorem 2. Assume that the labels are structured as described above and kŴ − W ∗ k < ∞. Then, Theorem 1
implies that




1
1
Es kŴ φ(x) − yk22 − ÊSm
kŴ φ(x) − yk22 (2)
2
2
≤ V [f ]D ∗ [φ∗ μx , φ(Xm )] + A1 + A2 ,

where f (t) = 12 kŴ t − W ∗ tk22 , A1 = ÊS̃m [ξ > (Ŵ −
W ∗ )φ(x)], A2 = Eξ [kξk22 ] − ÊS̃m [kξk22 ], and

Generalization in Machine Learning via Analytical Learning Theory

V [f ] ≤

dφ
X
l=1

+

k(Ŵl − Wl∗ )> (Ŵ − W ∗ )k1
X

1≤l<l0 ≤d

φ

|(Ŵl − Wl∗ )> (Ŵl0 − Wl∗0 )|.

Remark 5. The bound in Theorem 2 (i.e., the right-handside of Equation (2)) is minimized (to be the noise term
A2 only) if and only if Ŵ = W ∗ (see Appendix A.4 for
pathological cases). Therefore, minimizing the bound in
Theorem 2 is equivalent to minimizing the expected error
Es [kŴ φ(x)−yk22 ] or generalization error (see Appendix A.4
for further details). Furthermore, the bound in Theorem 2
holds with equality if Ŵ = W ∗ . Therefore, the bound in
Theorem 2 is tight in terms of both the minimizer and its
value.
In contrast to the conventional wisdom,1 Theorem 2 tightly
concludes that all that matters is how close Ŵ is to W ∗
in the end of the learning process, producing a strongly
instance-dependent bound. As in other important theories,
although it becomes apparent in hindsight, Theorem 2 provides a crucial practical insight: we should make Ŵ closer
to W ∗ at the end of the learning process, even if it increases
the bound on the norm kW k as well as the capacity and
complexity of a hypothesis space, and even if it decreases
the stability and robustness of the learning algorithm.
Remark 6. For D∗ [φ∗ μx , φ(Xm )] and A2 , we can
straightforwardly apply the probabilistic bounds under the
standard i.i.d. statistical assumption. From Proposition
2,
p
with high probability, D∗ [φ∗ μx , φ(Xm )] ≤ O( dφ /m).
From Hoeffding’s inequality p
with M ≥ kξk22 , with probability at least 1 − δ, A2 ≤ M ln(1/δ)/2m.
It is not necessary for D ∗ [φ∗ μx , φ(Xm )] to approach zero
to minimize the expected error; irrespective of whether the
training dataset satisfies a certain statistical assumption to
bound D ∗ [φ∗ μx , φ(Xm )], we can minimize the expected
error via making Ŵ closer to W ∗ as shown in Theorem 2.
4.2. Domains with unstructured/random labels
In this subsection, we discard the structured label assumption in the previous subsection and consider the worst case
scenario where y is a variable independent of x. This
corresponds to the random label experiment by Zhang
et al. (2017), which posed another open question: how to
theoretically distinguish the generalization behaviors with
structured labels from those with random labels. Generalization behaviors in practice are expected to be significantly
different in problems with structured labels or random labels, even when the hypothesis space (and Rademacher
complexity) and learning algorithm remain unchanged.
As desired, Theorem 3 (unstructured labels) predicts a
completely different generalization behavior from that in
1
A good description of the conventional wisdom is given in
(Zhang et al., 2017; Bartlett et al., 2017).

Theorem 2 (structured labels), even with an identical hypothesis space (and the same Rademacher complexity and
capacity) and learning algorithm. Here, we consider the
normalization of y such that y ∈ [0, 1]dy . Let μs be the
(unknown) normalized measure for the pair s = (x, y).
Theorem 3. Assume the unstructured labels as described
above. Let M = supt∈[0,1] kŴ t − yk∞ . Assume that
kŴ k < ∞ and M < ∞. Then, Theorem 1 implies that




1
1
2
2
Es kŴ φ(x) − yk2 − ÊSm
kŴ φ(x) − yk2 (3)
2
2
≤ V [f ]D ∗ [T∗ μs , T (Sm )],

where T (s) = (φ(x), y), f (t, y) = 12 kŴ t − yk22 , and
dφ
X
X
V [f ] ≤ (M + 1)
kŴl k1 +
|Ŵl> Ŵl0 | + dy M.
l=1

1≤l<l0 ≤dφ

Unlike in the structured case (Theorem 2), minimizing the
bound on the generalization gap in this case requires us
to bound the norm of Ŵ . This corresponds to the traditional wisdom from statistical learning theory, except that
we do not require a pre-defined bound on kW k over random problem instances; Theorem 3 is only sensitive to the
actual value of kŴ k at the end of learning process with
the given problem instance, producing a strongly instancedependent bound. The generalization gap goes to zero as
D∗ [T∗ μs , T (Sm )] approaches zero via certain statistical
assumption as in statistical learning theory. We can guarantee it via Proposition 2p
as follows: with high probability,
D ∗ [T∗ μs , T (Sm )] ≤ O( (dφ + dy )/m).
For linear models with over-parameterization, a recent impactful paper (Zhang et al. 2017, Section 5) poses open
questions: “is it then possible to generalize with such a
rich model class and no explicit regularization?” and “do
all global minima generalize equally well?”. Theorems 2
and 3 shed light on those questions with a mathematically
tight reasoning for each problem instance (see Remark 5).

5. General results for machine/deep learning
In this section, we consider the applications of Theorem
1 to general models in machine learning including deep
neural networks, in order to understand the qualitative nature of learning under the setting wherein the generalization
gap is decomposed without statistical assumptions. Deriving more concrete statements for each specific model type
(e.g., convolutional neural networks with ReLU units) is
left to future work. We first state that the results from the
previous section can be applied to deep learning.
Remark 7. Theorems 2 and 3 hold true, with learned representations φ, instead of fixed features. Let φ(x) represent
the last hidden layer in a neural network or the learned representation in representation learning in general. Consider

Generalization in Machine Learning via Analytical Learning Theory

the squared loss (square of output minus target). Then, the
identical proofs of Theorems 2 and 3 work with the learned
representation φ.
5.1. Theory with intermediate learned representation
An important question in representation learning such as
deep learning is how to consider the quality of learned representations. The following example provides a general result to answer such a question with practical insights.
General Example 1. (Decomposition at a space of learned
representation) Let T (z) = (φ(x), v) where φ is a map
of any learned representation and v is a variable such
that there exists a function f satisfying LŷA(Sm ) (z) =
f (φ(x), v) (for supervised learning, setting v := y always
satisfies this condition regardless of the information contained in φ(x)). For example, φ(x) may represent the output of any intermediate hidden layer in deep learning (possibly the last hidden layer), and v may encode the noise
left in the label y. Let f be a map such that LŷA(Sm ) =
f (T (z)). Then, if V [f ] < ∞, Theorem 1 implies that for
any dataset pair (Sm , Zm0 ) (including Zm0 = Sm ),
Eμ [LŷA(Sm ) ] ≤ ÊZm0 [LŷA(Sm ) ] + V [f ]D ∗ [T∗ μ, T (Zm0 )].

General Example 1 partially supports the concept of
the disentanglement in deep learning (Bengio et al.,
2009b) and proposes a new concrete method to measure
a degree of the disentanglement as follows. In the defiPd
P
(k)
[fj1 ...jk ],
nition of V [f ] =
k=1
1≤j1 <∙∙∙<jk ≤d V
(k)
each term V [fj1 ...jk ] can be viewed as measuring how entangled the j1 , . . . , jk -th variables
are in a space of a learned (hidden) representation.
We can observe this from the definition of
(k)
[f
] or from Proposition 1 as: V (k) [fj1 ...jk ] =
V
j
...j
1
k
R
|∂1,...,k fj1 ...jk (tj1 , . . . , tjk )| dtj1 ∙ ∙ ∙ dtjk , where ∂1,...,k
[0,1]k
fj1 ...jk (tj1 , . . . , tjk ) is the k-th order cross partial derivatives across the j1 , . . . , jk -th variables. If all the variables
in a space of a learned (hidden) representation are completely disentangled in this sense, V (k) [fj1 ...jk ] = 0 for all
Pd
k ≥ 2 and V [f ] is minimized to V [f ] = j1 =1 V (1) [fj1 ].

It has been empirically observed that deep networks (particularly in the unsupervised setting) tend to transform the
data distribution into a flatter one closer to a uniform distribution in a space of a learned representation (e.g., see Bengio et al. 2013). If the distribution T∗ μ with the learned representation T is uniform, then there exist better bounds
p on
D∗ [T∗ μ, T (Zm0 )] such as D ∗ [T∗ μ, T (Zm0 )] ≤ 10 d/m0
(Aistleitner, 2011). Intuitively, if the measure T∗ μ is nonflat and concentrated near a highly curved manifold, then
there are more opportunities for a greater mismatch between T∗ μ and T (Zm0 ) to increase D∗ [T∗ μ, T (Zm0 )] (see
Appendix A.5 for pathological cases). This intuitively suggests the benefit of the flattening property that is sometimes
observed with deep representation learning: it is often illus-

trated with generative models or auto-encoders by showing
how interpolating between the representations of two images (in representation space) corresponds (when projected
in image space) to other images that are plausible (are on or
near the manifold of natural images), rather than to the simple addition of two natural images (Bengio et al., 2009b).
If D ∗ [T∗ μ, T (Zm0 )] is small, it means that the learned representation φ is effective at minimizing the generalization
gap. This insight can be practically exploited by aiming to
make T∗ μ flatter and spread out the data points T (Zm0 ) in
a limited volume. It would also be beneficial to directly
regularize an approximated D ∗ [T∗ μ, T (Zm0 )] with the unknown μ replaced by some known measures (e.g., a finitesupport measure corresponding to a validation dataset).
Furthermore, General Example 1 suggests a method of regularization or model selection to control higher derivatives
of a learned model w.r.t. a learned representation. Let
f (t) = `(Ŷ (t), Y (t)); here, Ŷ and Y represent the learned
model yA(Sm ) and the target output y as a function of
t = T (z), respectively. Then, for example, if ` is the
square loss, and if Ŷ and Y are smooth functions, V [f ]
goes to zero as ∇k Ŷ − ∇k Y → 0 for k = 1, 2, ..., which
can be upper bounded by k∇k Ŷ k + k∇k Y k.
5.2. Theory with raw space and loss space
This subsection applies Theorem 1 to a raw representation
space T (z) = z and a loss space T (z) = (ι◦LŷA(Sm ) )(z),
where ι : {0, 1} → [0, 1] is an inclusion map.
General Example 2. (Decomposition in the space of Z)
Consider a normalized domain Z = [0, 1]dz and a Borel
measure μ on Z. For example, Z can be an unknown
hidden generative space or an input-output space (Z =
X ×Y). Let us apply Theorem 1 to this measure space with
T (z) = z and f = LŷA(Sm ) . Then, if V [LŷA(Sm ) ] < ∞,
Theorem 1 implies that for any dataset pair (Sm , Zm0 ) (including Zm0 = Sm ) and any LŷA(Sm ) ,
Eμ [LŷA(Sm ) ] ≤ ÊZm0 [LŷA(Sm ) ] + V [LŷA(Sm ) ]D ∗ [μ, Zm0 ].

This indicates that we can regularize V [LŷA(Sm ) ] in some
space Z to control the generalization gap. For example, letting the model yA(Sm ) be invariant to a subspace
that is not essential for prediction decreases the bound on
V [LŷA(Sm ) ]. As an extreme example, if x = g(y, ξ) with
some generative function g and noise ξ (i.e., a setting considered in an information theoretic approach), ŷA(Sm ) being invariant to ξ results in a smaller bound on V [LŷA(Sm ) ].
This is qualitatively related to an information theoretic observation such as in (Achille & Soatto, 2017).
General Example 3. (Decomposition in the loss space)
Consider multi-class classification with 0-1 loss. Let
T = ι ◦ LŷA(Sm ) . Let f be an identity map. Then,
V [f ] = 1 and LŷA(Sm ) (z) = (f ◦ T )(z) for all z ∈
Z. Then, the pair of T and f satisfies the condition in

Generalization in Machine Learning via Analytical Learning Theory

Theorem 1 as LŷA(Sm ) and ι are measurable functions.
Thus, from Theorem 1, Eμ [LŷA(Sm ) ] − ÊZm0 [LŷA(Sm ) ] ≤
V [f ]D∗ [T∗ μ, T (Zm0 )] = |(T∗ μ)({1}) − EZm0 [LŷA(Sm ) ]|)
(see Appendix B.7 for this derivation), which establishes a
tightness of Theorem 1 with the 0-1 loss as follows: for any
dataset pair (Sm , Zm0 ) (including Zm0 = Sm ),
Eμ [LŷA(Sm ) ] − ÊZm0 [LŷA(Sm ) ] = V [f ]D∗ [T∗ μ, T (Zm0 )].

6. Discussion
By generating strongly instance-dependent bounds,
throughout this paper, Theorem 1 has been shown to
answer the following open questions: 1) how to mathematically analyze generalization behaviors of machine
learning models possibly with arbitrarily rich hypothesis
spaces (large capacity, Rademacher complexity, etc.) and
non-stable/non-robust learning algorithms, and 2) how
to theoretically distinguish generalization behaviors with
structured labels from unstructured random labels. Perhaps
more importantly, Theorem 1 presents a way to measure
the quality of the learned model yA(Sm ) along with each
instance (μ, Sm , Zm0 , LŷA(Sm ) ), and has produced several
new theoretical insights on the generalization gap.
Theorem 1 also provides a different theoretical insight that
has another immediate practical consequence on how to
handle a dataset. In Theorem 1, the quality of a dataset
Sm is determined by the product of its similarity to μ (the
star-discrepancy) and the quality of the learned function
LŷA(Sm ) through the dataset (the variation). That is, while
conventional wisdom based on statistical learning theory
tells us to collect a statistically “good” (e.g., i.i.d.) dataset
from a distribution closer to the true μ, Theorem 1 tells
us that there may be better choices. According to Theorem 1, collecting a dataset that can induce a better model
ŷA(Sm ) with a lower empirical error and lower variation
of LŷA(Sm ) also results in better generalization gap and
expected error, even if the similarity to μ is reduced and
the statistical property (e.g., independence) becomes invalid (e.g., in Example 2, even if D ∗ [μ, Sm ] approaches
infinity, if V [LŷA(Sm ) ] goes to zero faster, the generalization gap approaches zero). This is consistent with emerging
practical heuristics in deep learning; it is becoming a common practice to add new data points to explicitly improve a
currently learned model (e.g., by probing the model), rather
than considering the statistical property in the dataset.
As we discussed in Section 3.2, Theorem 1 produces generalization bounds that can be zero even with m = 1
(and m0 = 1), supporting the concept of one-shot learning. This is true in general, even if the dataset completely differs from the measure μ (e.g., learning with
different distributions). This is because although it increases D∗ , it can decrease V [f ] in the generalization
bounds of V [f ]D∗ [T∗ μ, T (Sm )]. Furthermore, by being

strongly instance-dependent, particularly on the learned
model LŷA(Sm ) in the end, Theorem 1 supports the concept of curriculum learning (Bengio et al., 2009a), which
directly guides the learning to obtain a good model yA(Sm )
in the end. Moreover, consider certain types of curriculum learning that can violate statistical assumptions and
degrade statistical guarantees. Theorem 1 supports even
such types of curriculum learning, because learning a better model yA(Sm ) in the end decreases V [f ].

As we discussed in Section 3.2, V [f ] is always
strongly instance-dependent, but a probabilistic bound on
D ∗ [T∗ μ, T (Sm )] may not always remain strongly instancedependent, depending on the choice of T . For example, if
T is learned with Sm , we cannot directly adopt the probabilistic bound on D ∗ [T∗ μ, T (Sm )] from Section 3.2, because T (Sm ) does not satisfy the i.i.d. assumption. In such
a case, one can derive new probabilistic bounds on D∗ with
learned representation T via the following standard statistical approach. Consider a set Φ such that T ∈ Φ and Φ is
independent of Sm . Then, by applying Proposition 2 with
a union bound over a cover of Φ, we can obtain probabilistic bounds on D∗ with the log of the covering number of
Φ for all representations T 0 ∈ Φ, including the learned T .
As in data-dependent approaches (e.g., Shawe-Taylor et al.
1998), one can also consider a sequence of sets {Φj }j such
that T ∈ ∪j Φj . However, in both cases, the bounds on
D ∗ [T∗ μ, T (Sm )] now depend on the set Φ (via its covering
number) or the sequence {Φj }j (via the ordering in j and a
complexity of Φj ) that depends on ŷ 6= ŷA(Sm ) , and hence
are not strongly instance-dependent. This is a limitation of
our result toward a complete learning theory with strong
instance-dependence, and solving it is left to future work.
From a practical viewpoint, this might not be a major limitation, since a probabilistic bound on D ∗ is unnecessary
for the convergence of the generalization gap. The convergence of V [f ] to zero (faster than the increase rate of
D ∗ ) is sufficient for the convergence of generalization gap,
and D ∗ would also decrease deterministically. Moreover,
one can simply measure the empirical error with another
dataset Zm0 6= Sm (e.g., p
held-out validation dataset) to get
D ∗ [T∗ μ, T (Zm0 )] ≤ O( d/m0 ) (with high probability),
where the representation T is learned with Sm (since the
i.i.d. condition can now be straightforwardly satisfied).
The fact that Theorem 1 is invariant to a hypothesis space
H and certain details of a learning algorithm A can make it
difficult to understand their effects. However, as we move
towards the goal of artificial intelligence, H and A would
become extremely complex, which can pose a challenge in
theory. From this viewpoint, our theory can also be considered as a methodology to avoid such a challenge, producing
theoretical insights for intelligent systems with arbitrarily
complex H and A, so long as other conditions are imposed
on the actual functions being computed by them.

Generalization in Machine Learning via Analytical Learning Theory

Acknowledgements
We gratefully acknowledge support from NSF grants
1420316, 1523767 and 1723381, from AFOSR FA955017-1-0165, from ONR grant N00014-14-1-0486, and from
ARO grant W911NF1410433, as well as support from
NSERC, CIFAR and Canada Research Chairs. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not
necessarily reflect the views of our sponsors.

References
Achille, Alessandro and Soatto, Stefano. On the emergence
of invariance and disentangling in deep representations.
arXiv preprint arXiv:1706.01350, 2017.
Aistleitner, Christoph. Covering numbers, dyadic chaining
and discrepancy. Journal of Complexity, 27(6):531–540,
2011.
Aistleitner, Christoph and Dick, Josef. Low-discrepancy
point sets for non-uniform measures. Acta Arithmetica,
163(4):345–369, 2014.
Aistleitner, Christoph and Dick, Josef. Functions of
bounded variation, signed measures, and a general
Koksma-Hlawka inequality. Acta Arithmetica, 2(167):
143–171, 2015.
Aistleitner, Christoph, Pausinger, Florian, Svane,
Anne Marie, and Tichy, Robert F. On functions of
bounded variation. In Mathematical Proceedings of
the Cambridge Philosophical Society, volume 162, pp.
405–418. Cambridge University Press, 2017.
Arpit, Devansh, Jastrzebski, Stanislaw, Ballas, Nicolas,
Krueger, David, Bengio, Emmanuel, Kanwal, Maxinder S, Maharaj, Tegan, Fischer, Asja, Courville, Aaron,
Bengio, Yoshua, et al. A closer look at memorization in
deep networks. In International Conference on Machine
Learning, 2017.
Ash, Robert B and Doleans-Dade, Catherine. Probability
and measure theory. Academic Press, 2000.
Bartlett, Peter L, Boucheron, Stéphane, and Lugosi, Gábor.
Model selection and error estimation. Machine Learning, 48(1):85–113, 2002.
Bartlett, Peter L, Foster, Dylan J, and Telgarsky, Matus J. Spectrally-normalized margin bounds for neural
networks. In Advances in Neural Information Processing Systems, pp. 6241–6250, 2017.
Bengio, Yoshua, Louradour, Jérôme, Collobert, Ronan, and
Weston, Jason. Curriculum learning. In Proceedings
of the 26th annual international conference on machine
learning, pp. 41–48, 2009a.

Bengio, Yoshua, Mesnil, Grégoire, Dauphin, Yann, and Rifai, Salah. Better mixing via deep representations. In International Conference on Machine Learning, pp. 552–
560, 2013.
Bengio, Yoshua et al. Learning deep architectures for AI.
Foundations and trends R in Machine Learning, 2(1):1–
127, 2009b.
Bousquet, Olivier and Elisseeff, André. Stability and generalization. Journal of Machine Learning Research, 2
(Mar):499–526, 2002.
Brutzkus, Alon, Globerson, Amir, Malach, Eran, and
Shalev-Shwartz, Shai. Sgd learns over-parameterized
networks that provably generalize on linearly separable
data. arXiv preprint arXiv:1710.10174, 2017.
Choromanska, Anna, Henaff, MIkael, Mathieu, Michael,
Ben Arous, Gerard, and LeCun, Yann. The loss surfaces
of multilayer networks. In Proceedings of the Eighteenth
International Conference on Artificial Intelligence and
Statistics, pp. 192–204, 2015.
Dauphin, Yann N, Pascanu, Razvan, Gulcehre, Caglar,
Cho, Kyunghyun, Ganguli, Surya, and Bengio, Yoshua.
Identifying and attacking the saddle point problem in
high-dimensional non-convex optimization. In Advances
in Neural Information Processing Systems, pp. 2933–
2941, 2014.
Dinh, Laurent, Pascanu, Razvan, Bengio, Samy, and Bengio, Yoshua. Sharp minima can generalize for deep nets.
In International Conference on Machine Learning, 2017.
Dudley, Richard M. A course on empirical processes. In
Ecole d’été de Probabilités de Saint-Flour XII-1982, pp.
1–142. Springer, 1984.
Dziugaite, Gintare Karolina and Roy, Daniel M. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than
training data. In Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, 2017.
Hardy, Godfrey H. On double Fourier series and especially
those which represent the double zeta-function with real
and incommensurable parameters. Quart. J. Math, 37
(1):53–79, 1906.
Heinrich, Stefan, Woźniakowski, Henryk, Wasilkowski,
Grzegorz, and Novak, Erich. The inverse of the stardiscrepancy depends linearly on the dimension. Acta
Arithmetica, 3(96):279–302, 2001.
Herbrich, Ralf and Williamson, Robert C. Algorithmic
luckiness. Journal of Machine Learning Research, 3:
175–212, 2002.

Generalization in Machine Learning via Analytical Learning Theory

Hestness, Joel, Narang, Sharan, Ardalani, Newsha, Diamos, Gregory, Jun, Heewoo, Kianinejad, Hassan, Patwary, Md, Ali, Mostofa, Yang, Yang, and Zhou, Yanqi.
Deep learning scaling is predictable, empirically. arXiv
preprint arXiv:1712.00409, 2017.

Niederreiter, Harald. Quasi-monte carlo methods and
pseudo-random numbers. Bulletin of the American
Mathematical Society, 84(6):957–1041, 1978.

Hlawka, Edmund. Funktionen von beschränkter variatiou
in der theorie der gleichverteilung. Annali di Matematica
Pura ed Applicata, 54(1):325–333, 1961.

Poggio, Tomaso, Kawaguchi, Kenji, Liao, Qianli, Miranda,
Brando, Rosasco, Lorenzo, Boix, Xavier, Hidary, Jack,
and Mhaskar, Hrushikesh. Theory of deep learning iii:
explaining the non-overfitting puzzle. arXiv preprint
arXiv:1801.00173, 2017.

Hoffer, Elad, Hubara, Itay, and Soudry, Daniel. Train
longer, generalize better: closing the generalization gap
in large batch training of neural networks. arXiv preprint
arXiv:1705.08741, 2017.

Shawe-Taylor, John, Bartlett, Peter L, Williamson,
Robert C, and Anthony, Martin. Structural risk minimization over data-dependent hierarchies. IEEE transactions on Information Theory, 44(5):1926–1940, 1998.

Kawaguchi, Kenji. Bounded optimal exploration in MDP.
In Proceedings of the 30th AAAI Conference on Artificial
Intelligence (AAAI), 2016.

Soudry, Daniel and Hoffer, Elad. Exponentially vanishing
sub-optimal local minima in multilayer neural networks.
arXiv preprint arXiv:1702.05777, 2017.

Kawaguchi, Kenji, Kaelbling, Leslie Pack, and LozanoPérez, Tomás. Bayesian optimization with exponential
convergence. In Advances in Neural Information Processing (NIPS), 2015.

Vapnik, Vladimir. Statistical learning theory, volume 1.
Wiley New York, 1998.

Kawaguchi, Kenji, Maruyama, Yu, and Zheng, Xiaoyu.
Global continuous optimization with error bound and
fast convergence. Journal of Artificial Intelligence Research, 56:153–195, 2016.
Kawaguchi, Kenji, Kaelbling, Leslie Pack, and Bengio,
Yoshua. Generalization in deep learning. arXiv preprint
arXiv:1710.05468, 2017.
Koltchinskii, Vladimir and Panchenko, Dmitriy.
Rademacher processes and bounding the risk of
function learning. In High dimensional probability II,
pp. 443–457. Springer, 2000.
Krause, M.
Über fouriersche reihen mit zwei
veränderlichen grössen. Leipziger Ber, 55:164–197,
1903.
Krueger, David, Ballas, Nicolas, Jastrzebski, Stanislaw,
Arpit, Devansh, Kanwal, Maxinder S, Maharaj, Tegan,
Bengio, Emmanuel, Fischer, Asja, and Courville, Aaron.
Deep nets don’t learn via memorization. In Workshop
Track of International Conference on Learning Representations, 2017.
Mohri, Mehryar, Rostamizadeh, Afshin, and Talwalkar,
Ameet. Foundations of machine learning. MIT press,
2012.
Mukherjee, Sayan, Niyogi, Partha, Poggio, Tomaso, and
Rifkin, Ryan. Learning theory: stability is sufficient for
generalization and necessary and sufficient for consistency of empirical risk minimization. Advances in Computational Mathematics, 25(1):161–193, 2006.

Wu, Lei, Zhu, Zhanxing, et al. Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv preprint arXiv:1706.10239, 2017.
Xu, Huan and Mannor, Shie. Robustness and generalization. Machine learning, 86(3):391–423, 2012.
Zahavy, Tom, Kang, Bingyi, Sivak, Alex, Feng, Jiashi, Xu,
Huan, and Mannor, Shie. Ensemble robustness and generalization of stochastic deep learning algorithms. arXiv
preprint arXiv:1602.02389, 2016.
Zhang, Chiyuan, Bengio, Samy, Hardt, Moritz, Recht, Benjamin, and Vinyals, Oriol. Understanding deep learning
requires rethinking generalization. In International Conference on Learning Representations, 2017.

Generalization in Machine Learning via Analytical Learning Theory

Appendix
Appendix A contains additional explanations to facilitate
understanding this paper. Appendix B includes all the
proofs of the theoretical results.
q

A. Additional explanations
Both statistical learning theory and analytical learning theory have relative advantages and disadvantages, because of
the difference in the objectives and the sets of assumptions.
To recognize certain differences in analytical learning theory and statistical learning theory, it is good to remember
the basics of the mathematical logics such as the difference
in “∀x, ∃y” v.s. “∃y, ∀x”. Typically in statistical learning
theory, some upper bound holds over a fixed H or a fixed A
with a certain property with high probability over different
datasets. Usually in analytical learning theory, some upper
bound holds individually for each problem instance.
A.1. An illustration of discrepancy
Figure 1 shows an illustration of the local discrepancy
D[Bt ; Tm , ν] and related notation in two dimensional
space.
Figure 1. The local discrepancy
D[Bt ; Tm , ν] evaluates the difference between the empirical
measure of the box Bt (the normalized number of data points
in the box Bt , which is 4/10)
and the measure ν of the box Bt
(the measure of the blue region)

A.2. An illustration of a difference in the scopes of
statistical and analytical learning theories
Figure 2 shows a graphical illustration of a difference in the
scopes of statistical learning theory and analytical learning
theory. Here, μm is the product measure.
In the setting of statistical learning theory (Figure 2 (a)),
our typical goal is to analyze the random expected error
Eμ [LŷA(Sm ) ] over the random datasets Sm by fixing a
hypothesis space and/or learning algorithm over random
datasets. Due to the randomness over Sm , we do not know
where q exactly lands in Q. The lower bound and necessary condition in the setting of statistical learning theory is
typically obtained via a worst-case instance q 0 in Q. For example, classical no free lunch theorems and lower bounds
on the generalization gap via VC dimension (e.g., Mohri
et al. 2012, Section 3.4) have been derived with the worst-

q'

(a) Statistical learning theory

q
(b) Analytical learning theory

Figure 2. An illustration of a difference in the scopes with Zm0 =
Sm : q represents a query about the generalization gap of a learned
model yA(Sm ) , which is a deterministic quantity of the tuple
(μ, Sm , LŷA(Sm ) ). Intuitively, whereas analytical learning theory analyzes q directly, statistical learning theory focuses more
on analyzing the set Q that contains q. The set Q is defined
by the sets of possible measures μ and randomly-drawn different datasets Sm and the hypothesis space H or learning algorithm
A.

case distribution characterizing q 0 in Q. Such a necessary
condition is only proven to be necessary for the worst-case
q 0 ∈ Q, but is not proven to be necessary for others q 6= q 0 .
Intuitively, we are typically analyzing the quality of the set
Q, instead of each individual q ∈ Q.
In this view, it becomes clear what is going on in some
potentially surprising empirical observations such as in
(Zhang et al., 2017). Intuitively, whereas statistical learning theory focuses more on analyzing the set Q, each element such as q (e.g., a “good” case or structured label case)
and q 0 (e.g., the worst-case or random label case) can significantly differ from each other. Data-dependent analyses
in statistical learning theory can be viewed as the ways to
decrease the size of Q around each q.
In contrast, analytical learning theory (Figure 2 (b)) ignores
the set Q, and focuses on each q only, allowing tighter results for each “good” q ∈ Q beyond the possibly “bad”
quality of the set Q overall.
It is important to note that analyzing the set Q is of great
interest on its own merits, and statistical learning theory
has advantages over our proposed learning theory in this
sense. Indeed, analyzing a set Q is a natural task along
the way of thinking in theoretical computer science (e.g.,
categorizing a set Q of problem instances into polynomial
solvable set or not). This situation where theory focuses

Generalization in Machine Learning via Analytical Learning Theory

more on Q and practical studies care about each q ∈ Q
is prevalent in computer science even outside the learning
theory. For example, the size of Q analyzed in theory for
optimal exploration in Markov decision processes (MDPs)
has been shown to be often too loose for each practical
problem instance q ∈ Q, and a way to partially mitigate
this issue was recently proposed (Kawaguchi, 2016). Similarly, global optimization methods including Bayesian optimization approaches may suffer from a large complex Q
for each practical problem instance q ∈ Q, which was partially mitigated in recent studies (Kawaguchi et al., 2015;
2016).

imize the expected error in Theorem 1 by minimizing V [f ]
(and/or D∗ [T∗ μ, T (Sm )] as deterministic quantity) such
that V [f ]D∗ [T∗ μ, T (Sm )] becomes marginal without the
randomness over Sm .

Furthermore, the issues of characterizing a set Q only via
a worst-case instance q 0 (i.e., worst-case analysis) are wellrecognized in theoretical computer science, and so-called
beyond worst-case analysis (e.g., smoothed analysis) is an
active research area to mitigate the issues.

In Section 4.1, the optimal solution to minimize the expected error Es [ 12 kŴ φ(x) − yk22 ] is attained at Ŵ = W ∗ .
To see this, we can expand the expected error as


1
2
Es kŴ φ(x) − yk2
2


1
∗
2
= Ex kŴ φ(x) − W φ(x)k2
2



1
2
>
∗
+ Ex,ξ
kξk2 + ξ W φ(x) − Ŵ φ(x)
2




1
1
∗
2
2
= Ex kŴ φ(x) − W φ(x)k2 + Eξ
kξk2 ,
2
2

Moreover, a certain qualitative property of the set Q might
tightly capture that of each instance q ∈ Q. While proving such an assertion seems challenging in general (proving that a upper bound on ∀q ∈ Q matches a lower bound
∃q 0 ∈ Q is not sufficient), one can study it with empirical
experiments (e.g., see Hestness et al. 2017).
A.3. On usage of statistical assumption with Zm0 = Sm
Using a statistical assumption on a dataset Zm0 with Zm0 6=
Sm is consistent with a practical situation where a dataset
Sm is given first instead of remaining random. For Zm0 =
Sm , we can view this formulation as a mathematical modeling of the following situation. Consider Sm as a random
variable when collecting a dataset Sm , and then condition
on the event of getting the collected dataset Sm once Sm
is specified, focusing on minimization of the (future) expected error Eμ [LŷA(Sm ) ] of the model ŷA(Sm ) learned
with this particular specified dataset Sm .
In this view, we can observe that if we draw an i.i.d. dataset
Sm , a dataset Sm is guaranteed to be statistically “good”
∗
with high probability in
q terms of D [T∗ μ, T (Sm )] (e.g.,

d
via Proposition 2). Thus, colD∗ [T∗ μ, T (Sm )] ≤ c2 m
lecting a training dataset in a manner that satisfies the i.i.d.
condition is an effective method. However, once a dataset
Sm is actually specified, there is no longer randomness over
Sm , and the specified dataset Sm is “good” (high probability event) or “bad” (low probability event). We get a “good”
dataset with high probability, and we obtain probabilistic
guarantees such as Equation (1).

In many practical studies, a dataset to learn a model is
specified first as, for example, in studies with CIFAR-10,
ImageNet, or UCI datasets. Thus, we might have a statistically “bad” dataset Sm with no randomness over Sm
when these practical studies begin. Even then, we can min-

Several recent studies also consider a stochastic property of
learning algorithms (e.g., Zahavy et al. 2016).
A.4. Supplementary explanation in Remark 5
The bound is always minimized if Ŵ = W ∗ , but it is not
a necessary condition in a pathological case where the stardiscrepancy D∗ is zero and A1 can be zero with Ŵ 6= W ∗ .

where the last line follows that ξ is a zero-mean random
variable independent of x. From the last line of the above
equation, we can conclude the above statement about the
minimizer.
A.5. Pathological cases for non-flat measures
If T∗ μ is concentrated in a single point, then
D ∗ [T∗ μ, T (Zm0 )] = 0, but it implies that there is
only a single value of LŷA(Sm ) (z) = f (φ(x), v) because
(φ(x), v) takes only one value. Hence, this is tight and
consistent. On the other hand, to minimize the empirical
error ÊZm0 [LŷA(Sm ) ] with diverse label values, T∗ μ should
not concentrate on the small number of finite points.

B. Proofs
We use the following fact in our proof.
Lemma 1. (theorem 3.1 in Aistleitner et al. 2017) Every
real-valued function f on [0, 1]d such that V [f ] < ∞ is
Borel measurable.
B.1. Proof of Proposition 1
Proof. By the definition, we have that
(i )

(i )

1
k
ΔP
j1 ,...,jk fj1 ...jk (tj1 , . . . , tjk )


(i1 )
(ik )
P
= ΔP
j1 ,...,jk−1 Δjk fj1 ...jk (tj1 , . . . , tjk )

Generalization in Machine Learning via Analytical Learning Theory

By the mean value theorem on the single variable tjk ,
(i )

(i )

1
k
ΔP
jk fj1 ...jk (tj1 , . . . , tjk )


(i )
(i )
(i +1)
(i )
= ∂k fj1 ...jk (tj11 , . . . , cjkk ) (tjkk
− tjkk ),

(i )

(i +1)

(i )

where cjkk ∈ (tjkk , tjkk ). Thus, by repeatedly applying
the mean value theorem,

follows the proof of theorem 1.6.12 in (Ash & DoleansDade, 2000); we proceed from simpler cases to more general cases as follows. In the case of f being an indicator
function of some set A as f = 1A , we have that
Z
f (T (z))dμ(z) = μ(Z ∩ T −1 A)
Z

= (T∗ μ)(Ω ∩ A)
Z
f (ω)d(T∗ μ)(ω).
=

(i1 )
(ik )
ΔP
jk fj1 ...jk (tj1 , . . . , tjk )

=



(i )
(i )
∂1,...,k fj1 ...jk (cj11 , . . . , cjkk )

(i )

V

Ω

(i +1)
(tjkk

l=1

(i +1)

where cjll ∈ (tjll
(k)

k
Y

−

(i )
tjkk ),

(i )

, tjll ) for all l ∈ {1, . . . , k}. Thus,

[fj1 ...jk ]

= sup

mP
1 −1

X

P ∈Pk i =1
1

∙∙∙

mP
k −1

X

(i )

Z

f (T (z))dμ(z) =

Z

(i )

∂1,...,k fj1 ...jk (cj11 , . . . , cjkk )

=

ik =1
k
Y

(i +1)
(tjkk

l=1

−

=

(i )
tjkk ).

(i )

(i )

By taking supremum for ∂1,...,k fj1 ...jk (cj11 , . . . , cjkk )
and taking it out from the sum, we obtain the first
statement.
The second statement follows the fact
(i )
(i )
that if ∂1,...,k fj1 ...jk (tj11 , . . . , tjkk ) is continuous, then
(i )

n
X
i=1
n
X

αi
αi

i=1

∙

(i )

|∂1,...,k fj1 ...jk (tj11 , . . . , tjkk )| is continuous and Riemann
integrable. Thus, the right hand side on the above equation coincides with the definition of the Riemann integral
(i )
(i )
of |∂1,...,k fj1 ...jk (tj11 , . . . , tjkk )| over [0, 1]k .
B.2. Proof of Theorem 1
The proof of Theorem 1 relies on several existing proofs
from different fields. Accordingly, along the proof, we
also track the extra dependencies and structures that appear only in machine learning, to confirm the applicability
of the previous proofs in the problem of machine learning.
Thus, while presenting the proof is necessary for the purpose of this paper, each component of the proof by itself
is not intended to be an original contribution. Let 1A be
an indicator function of a set A. Let Ω = [0, 1]d . Let
1 = (1, 1, . . . , 1) ∈ Ω and 0 = (0, 0, . . . , 0) ∈ Ω as in a
standard convention. The following lemma follows theorem 1.6.12 in (Ash & Doleans-Dade, 2000).
Lemma 2. For any (T , f ) ∈ F [LŷA(Sm ) ],
Z
Z
f (T (z))dμ(z) =
f (ω)d(T∗ μ)(ω).
Z

In thePcase of f being a non-negative simple function as
n
f = i=1 αi 1Ai ,

Ω

Proof of Lemma 2. By Lemma 1, f is a Borel measurable function. The rest of the proof of this lemma directly

Z

Ω

Z
Z

Z

Ω

1Ai (T (z))dμ(z)

1Ai (ω)d(T∗ μ)(ω)

f (ω)d(T∗ μ)(ω),

where the second line follows what we have proved for the
case of f being an indicator function.
In the case of f being a non-negative Borel measurable
function, let (fk )k∈N be an increasing sequence of simple functions such that f (ω) = limk→∞ fk (ω), ω ∈
Ω. Then, by Rwhat we have proved
R for simple functions, we have Z fk (T (z))dμ(z) = Ω fk (ω)d(T∗ μ)(ω).
Then,
by the monotone
R convergence theorem, we have
R
f
(T
(z))dμ(z)
=
f (ω)d(T∗ μ)(ω).
Z
Ω
In the case of f = f + − f − being an arbitrary Borel
measurable function, we have already proved the desired
statement for each f + and f − , and by the definition of
Lebesgue integration, the statement for f holds.

Proof of Theorem 1. With Lemmas 1 and 2, the proof follows that of theorem 1 in (Aistleitner & Dick, 2015). For
any (T , f ) ∈ F [LŷA(Sm ) ],
Z

0

Z

=
=

LŷA(Sm ) (z)dμ(z) −
Z

Z

m
1 X
LŷA(Sm ) (zi )
m0 i=1
0

Z

f (T (z))dμ(z) −

m
1 X
f (T (zi ))
m0 i=1
0

Ω

f (ω)d(T∗ μ)(ω) −

m
1 X
f (T (zi ))
m0 i=1

where the second line follows the condition of T and f
and the third line follows Lemma 2. In the following, we

Generalization in Machine Learning via Analytical Learning Theory

first consider the case where f is left-continuous, and then
discard the left-continuity condition later.
Consider the case where f is left-continuous (for the
second statement): Suppose that f is left-continuous
coordinate-wise at every point in the domain. Given a pair
of vectors (a, b), we write a ≤ b if the relation holds for
every coordinate. Let f˜(ω) = f (1 − ω) − f (1) for all
ω ∈ Ω. Then, by theorem 3 and equation (20) in (Aistleitner & Dick, 2015), there exists signed Borel measure μf˜
on Ω such that f˜(ω) = μf˜([0, ω]) for all ω ∈ Ω and
|μf˜|(Ω) = V [f ] + |f˜(0)| = V [f ]. Let νf be the reflected
measure of μf˜ as νf (A) = μf˜(1 − A) for any Borel set
A ⊂ Ω where 1 − A = {1 − t : t ∈ A}. It follows that νf
is a signed Borel measure and

plies that
Z

≤ |dνf (t)|(Ω)D∗ [T∗ μ, T (Zm0 )]
= V [f ]D ∗ [T∗ μ, T (Zm0 )].

Discard the left-continuity condition of f (for the first
statement): Let f be given and fixed without left-continuity
condition. For each fixed f , by the law of large numbers (strong law of large numbers and the multidimensional
Glivenko–Cantelli theorem), for any  > 0, there exists a
ωi }ni=1 such that both of the
number n and a set Aˉn = {ˉ
following two inequalities hold:

|νf |(Ω) = |μf˜|(Ω) = V [f ].

Z

By using these, we can rewrite f as
f (ω) = f (1) + f˜(1 − ω)
Z
= f (1) +
1[0,1−ω] (t)dμf˜(t)
ZΩ
= f (1) +
1[ω,1] (t)dνf (t)
Ω
Z
1[0,t] (ω)dνf (t),
= f (1) +
Ω

where the second line follows from {1 − t : t ∈ [ω, 1]} =
[0, 1 − ω]. Then, by linearity,
Z
m
m
1 X
1 X
f (T (zi ))−f (1) =
1[0,t] (T (zi ))dνf (t),
0
m0 i=1
Ω m i=1
0

0

and by the Fubini–Tonelli theorem and linearity,
Z
f (ω)d(T∗ μ)(ω) − f (1)
Ω
Z Z
1[0,t] (ω)d(T∗ μ)(ω)dνf (t)
=
ZΩ Ω
= (T∗ μ)([0, t])dνf (t).
Ω

n

Ω

f (ω)d(T∗ μ)(ω) −

and

ωi }i=1 be such a set. For each fixed f , let fn
Let Aˉn = {ˉ
be a left-continuous function such that fn (ω) = f (ω) for
all ω ∈ Aˉn ∪ T (Zm0 ) and V [fn ] ≤ V [f ]. This definition
of fn is non-vacuous and we can construct such a fn as
follows. Let G be the d-dimensional grid generated by the
set {0}∪{1}∪Aˉn ∪T (Zm0 ); G is the set of all points ω ∈ Ω
such that for k ∈ {1, . . . , d}, the k-th coordinate value of
ω is the k-th coordinate value of some element in the set
{0} ∪ {1} ∪ Aˉn ∪ T (Zm0 ). We can construct a desired fn
by setting fn (ω) = f (succn (ω)), where succn (ω) outputs
an unique element t ∈ G satisfying the condition that t ≥ ω
and t ≤ t0 for all t0 ∈ {t0 ∈ G : t0 ≥ ω}.
Then, by triangle inequality, we write
Z
≤

0

m
1 X
f (ω)d(T∗ μ)(ω) − 0
f (T (zi ))
m i=1 | {z }
Ω

=fn (T (zi ))

Z

0

m
1 X
fn (ω)d(T∗ μ)(ω) − 0
fn (T (zi ))
m i=1
Ω
n

m0
X

1
f (ω)d(T∗ μ)(ω) − 0
f (T (zi ))
m
Ω
i=1


Z
m0
X
1
(T∗ μ)([0, t]) −
=
1[0,t] (T (zi )) dνf (t),
m0 i=1
Ω

which proves the second statement of this theorem by
noticing that f (t) = νf ([t, 1]) + f (1). Moreover, this im-

1X
f (ˉ
ωi ) ≤ ,
n i=1

D ∗ [T∗ μ, Aˉn ] ≤ .

Therefore,
Z

0

m
1 X
f (ω)d(T∗ μ)(ω) − 0
f (T (zi ))
m i=1
Ω

+

1X
fn (ˉ
ωi ) −
n i=1 | {z }
=f (ˉ
ωi )

+

Z

Z

Ω

fn (ω)d(T∗ μ)(ω)
n

1X
f (ω)d(T∗ μ)(ω) −
f (ˉ
ωi ) .
n i=1
Ω

Because fn is left-continuous, we can apply our previous
result to the first and the second terms; the first term is
at most V [fn ]D ∗ [T∗ μ, T (Zm0 )] ≤ V [f ]D ∗ [T∗ μ, T (Zm0 )],

Generalization in Machine Learning via Analytical Learning Theory

and the second term is at most V[fn ]D ∗ [T∗ μ, Aˉn ] ≤ V[f ].
The third term is at most  by the definition of Aˉn . Since
 > 0 can be arbitrarily small, we have that for each
(f, T ) ∈ F [LŷA(Sm ) ], (deterministically,)
Z

1
1
kW φ(x) − yk22 = kW φ(x) − W ∗ φ(x)k22
2
2
1
+ kξk22 − ξ > (W φ(x) − W ∗ φ(x)) ,
2

Putting together: for any (T , f ) ∈ F [LŷA(Sm ) ],

we have




1
1
2
2
Es kŴ φ(x) − yk2 − ÊSm
kŴ φ(x) − yk2
2
2

0

m
1 X
LŷA(Sm ) (z)dμ(z) − 0
LŷA(Sm ) (zi )
m i=1
Z

≤ V [f ]D∗ [T∗ μ, T (Zm0 )]
R

P m0

Thus, Z LŷA(Sm ) (z)dμ(z) −
i=1 LŷA(Sm ) (zi ) is
a lower bound of a set Q = {V [f ]D∗ [T∗ μ, T (Zm0 )] :
(T , f ) ∈ F [LŷA(Sm ) ]}. By the definition of infimum,
R
P m0
LŷA(Sm ) (z)dμ(z) − m10 i=1 LŷA(Sm ) (zi ) ≤ inf Q,
Z
if inf Q exists. Because Q is a nonempty subset of real and
lower bounded by 0, inf Q exists. Therefore,
Z
≤

1
m0

0

Z

LŷA(Sm ) (z)dμ(z) −
inf

(T ,f )∈F [LŷA(Sm ) ]

B.5. Proof of Theorem 2
Proof. Let LŷA(Sm ) (x) = 12 kŴ φ(x) − W ∗ φ(x)k22 (Z =
X ). Since

0

m
1 X
f (ω)d(T∗ μ)(ω) − 0
f (T (zi ))
m i=1
Ω

≤ V [f ]D∗ [T∗ μ, T (Zm0 )].

Z

Because T is a surjection, for such a Tm0 , there exists Zm0
such that T (Zm0 ) = Tm0 .

m
1 X
LŷA(Sm ) (zi )
m0 i=1

= Eμx [LŷA(Sm ) ] − ÊXm [LŷA(Sm ) ] + A1 + A2
≤ V [f ]D ∗ [φ∗ μx , φ(Xm )] + A1 + A2 ,

where the last line is obtained by applying Theorem 1 to
Eμx [LŷA(Sm ) ] − ÊXm [LŷA(Sm ) ] as follows. Let T (x) =
φ(x) and f (t) = 12 kŴ t − W ∗ tk22 , where t ∈ Rdφ . Then,
LŷA(Sm ) (x) = (f ◦ T )(x), and (T , f ) ∈ F [LŷA(Sm ) ] in
Theorem 1 if V [f ] < ∞. Therefore, by Theorem 1, if
V [f ] < ∞,
Eμx [LŷA(Sm ) ] − ÊXm [LŷA(Sm ) ] ≤ V [f ]D ∗ [φ∗ μx , φ(Xm )].

V [f ]D∗ [T∗ μ, T (Zm0 )],

which implies the first statement of this theorem.

B.3. Proof of Proposition 2

To upper bound V [f ] and to show V [f ] < ∞, we in∂f
voke Proposition 1 as follows. We have that ∂t
= (Ŵl −
l
∂f
∗ >
∗
∗ >
Wl ) (Ŵ −W )t, and ∂tl ∂t 0 = (Ŵl −Wl ) (Ŵl0 −Wl∗0 ).
l
Because the second derivatives are constant over t, the third
and higher derivatives are zeros. Let t̃l = (t1 , . . . , tdφ )>
with tj ≡ 1 for all j 6= l. Then, we have that

Proof. From theorem 2 in (Heinrich et al., 2001), there
√ exists a positive constant c1 such that for all s ≥ c1 d and
for all m0 ∈ N+ ,
o 1  c s 2 d
n
2
1
∗
0 −1/2
0
≤
e−2s ,
P D [T∗ μ, T (Zm )] ≥ sm
s
d

d
X

where we used the fact that the VC dimension of the set of
the axis-parallel boxes contained in [0, 1]d with one vertex
at √
the origin is d (e.g., see Dudley 1984). By setting s =
c2 d for any c2 ≥ c1 , we obtain the desired result.

≤

B.4. Proof of Proposition 3

l=1

=

d Z
X
l=1

=

d
X
l=1

d
X
l=1

[0,1]

|(Ŵl − Wl∗ )> (Ŵ − W ∗ )t̃l |dtl

k(Ŵl − Wl∗ )> (Ŵ − W ∗ )k1

Z

[0,1]

kt̃l k∞ dtl .

k(Ŵl − Wl∗ )> (Ŵ − W ∗ )k1 ,

and

Proof. From theorem 1 in (Aistleitner & Dick, 2014), for
any m0 ∈ N+ , there exists a set Tm0 of points t1 , . . . , tm0 ∈
[0, 1]d such that
√ (2 + log2 m )
D [T∗ μ, Tm0 ] ≤ 63 d
m0
∗

V (1) [fl ]

0 (3d+1)/2

.

X

V (2) [fll0 ]

1≤l<l0 ≤d

≤

X

1≤l<l0 ≤d

|(Ŵl − Wl∗ )> (Ŵl0 − Wl∗0 )|.

Generalization in Machine Learning via Analytical Learning Theory

Since higher derivatives exist and are zeros, from Proposition 1, V (k) [fj1 ...jk ] = 0 for k = 3, . . . , d. By the definition of V [f ], we obtain the desired bound for V [f ], and we
have V [f ] < ∞ if kŴ − W ∗ k < ∞ (where there is no
need to specify the particular matrix norm because of the
equivalence of the norm).

Thus,
X

1≤j1 <j2 ≤dφ +dy

=

Proof. Let Wl0 l be the (l0 , l)-th entry of the matrix W . Let
LŷA(Sm ) (s) = 12 kŴ φ(x)−yk22 (Z = X ×Y). Let T (s) =
(φ(x), y) and f (t, y) = 12 kŴ t − yk22 . Then, `(s) = (f ◦
T )(s), and (T , f ) ∈ F [LŷA(Sm ) ] in Theorem 1 if V [f ] <
∞. Therefore, by Theorem 1, if V [f ] < ∞,
Es





1
1
kŴ φ(x) − yk22 − ÊSm
kŴ φ(x) − yk22
2
2

≤ V [f ]D ∗ [T∗ μs , T (Sm )].



To upper bound V [f ] and to show V [f ] < ∞, we invoke
Proposition 1 as follows. For the first derivatives, we have
∂f
∂f
that ∂t
= Ŵl> (Ŵ t − y) and ∂y
= −(Ŵ t − y)l . For the
l
l
second derivatives, we have that
∂2f
=
∂yl ∂yl0

(

2

∂ f
∂tl ∂tl0

=

Ŵl> Ŵl0 ,

1 if l = l0
0 if l 6= l,

2

and ∂t∂l ∂yf 0 = −Ŵl0 l . Because the second derivatives are
l
constant in t and y, the third and higher derivatives are ze∂f
∂f
ros. Then, because | ∂t
| ≤ M kŴl k1 and | ∂y
| ≤ M , with
l
l
l = j1 ,
dφ
X

V

(1)

j1 =1

[fj1 ] ≤ M

dφ
X
l=1

kŴl k1 ,

and
dφ +dy

X

j1 =dφ +1

V (1) [fj1 ] ≤ dy M.

Furthermore, for j1 , j2 ∈ {1, . . . , dφ }, with l = j1 and
l 0 = j2 ,
V (2) [fj1 j2 ] ≤ |Ŵl> Ŵl0 |.
For j1 ∈ {1, . . . , dφ } and j2 ∈ {dφ + 1, . . . , dφ + dy }, with
l = j1 and l0 = j2 − dφ ,
V (2) [fj1 j2 ] ≤ |Ŵl0 l |,
and for j1 , j2 ∈ {dφ + 1, . . . , dφ + dy },
V

(2)

[fj1 j2 ] ≤

X

|Ŵl> Ŵl0 |

X

|Ŵl> Ŵl0 | +

1≤l<l0 ≤dφ

B.6. Proof of Theorem 3



V (2) [fj1 j2 ]

(

1
0

if j1 = j2
otherwise.

=

1≤l<l0 ≤dφ

+

dφ d y
X
X

l=1 l0 =1

dφ
X
l=1

|Ŵl0 l |

kŴl k1 .

Therefore,
V [f ]
dφ +dy

=

X

k=1

=

X

V (k) [fj1 ...jk ]

1≤j1 <∙∙∙<jk ≤dφ +dy

2
X

X

V (k) [fj1 ...jk ]

k=1 1≤j1 <∙∙∙<jk ≤dφ +dy

≤ (M + 1)

dφ
X
l=1

kŴl k1 +

X

1≤l<l0 ≤dφ

|Ŵl> Ŵl0 | + dy M.

Here, we have V [f ] < ∞ because kŴ k < ∞ and M < ∞
(and the equivalence of the norm).
B.7. Proof of the inequality in General Example 3
Let μT (Zm0 ) be a (empirical) normalized measure with the
finite support on T (Zm0 ). Then,
Eμ [LŷA(Sm ) ] − ÊZm0 [LŷA(Sm ) ]

≤ V [f ]D ∗ [T∗ μ, T (Zm0 )]
= max{|(T∗ μ)({0}) − μT (Zm0 ) ({0})|,

|(T∗ μ({0, 1})) − μT (Zm0 ) ({0, 1})|}

= |T∗ μ({0}) − μT (Zm0 ) ({0})|

= |1 − T∗ μ({1}) − 1 + μT (Zm0 ) ({1})|

= |T∗ μ({1}) − μT (Zm0 ) ({1})|.

Rewriting μT (Zm0 ) ({1}) = EZm0 [LŷA(Sm ) ] yields the desired inequality in General Example 3.

