![](https://csdnimg.cn/release/download_crawler_static/12279619/bg4.jpg)
Generalization in Machine Learning via Analytical Learning Theory
with Z
m
0
= S
m
or Z
m
0
being any other dataset. While
Z
m
0
⊆ Z (to define the
ˆ
E
Z
m
0
[Lˆy
A(S
m
)
]), a dataset S
m
is
arbitrary and S
m
* Z is allowed when Z
m
0
6= S
m
.
Theorem 1. For any Lˆy, let F[Lˆy] 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
Lˆy(z) = (f ◦ T )(z) for all z ∈ Z,
where B(A) indicates the Borel σ-algebra on A. Then, for
any dataset pair (S
m
, Z
m
0
) (including Z
m
0
= S
m
) and any
Lˆy
A(S
m
)
,
(i) E
μ
[Lˆy
A(S
m
)
]
≤
ˆ
E
Z
m
0
[Lˆy
A(S
m
)
] + inf
(T ,f)∈
ˆ
F
V [f]D
∗
[T
∗
μ, T (Z
m
0
)],
where
ˆ
F = F[Lˆy
A(S
m
)
], and
(ii) for any (T , f) ∈ F[Lˆy
A(S
m
)
] such that f is right-
continuous component-wise,
E
μ
[Lˆy
A(S
m
)
] −
ˆ
E
Z
m
0
[Lˆy
A(S
m
)
]
=
Z
[0,1]
d
(T
∗
μ)([0, t]) −
1
m
0
m
0
X
i=1
1
[0,t]
(T (z
i
))
dν
f
(t),
where z
i
∈ Z
m
0
, and ν
f
is a signed measure cor-
responding to f as f(t) = ν
f
([t, 1]) + f(1) and
|ν
f
|([0, 1]
d
) = V [f].
Theorem 1 holds for each individual instance
(μ, S
m
, Z
m
0
, Lˆy
A(S
m
)
), 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
μ
[Lˆy] −
ˆ
E
S
m
[Lˆy] for any ˆy ∈ H (with
high probability), what it means is that the upper bound
holds on sup
ˆy∈H
(E
μ
[Lˆy] −
ˆ
E
S
m
[Lˆy]) (with high proba-
bility). 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(S
m
)
(learned with the actual instance S
m
).
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 algo-
rithm A over datasets different from a given dataset S
m
(and Z
m
0
) (e.g., stability and robustness). They are fully
determined by each given instance (μ, S
m
, Z
m
0
, Lˆy
A(S
m
)
)
without dependence on other instances.
Remark 2. Theorem 1 together with Remark 1 has a sig-
nificant consequence in practice. For example, even if the
true model is contained in some “small” hypothesis space
H
1
, we might want to use a much more complex “larger”
hypothesis space H
2
in practice such that the optimization
becomes easier and the training trajectory reaches a better
model ˆy
A(S
m
)
in the end of the learning process (e.g., over-
parameterization 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 observa-
tions in deep learning, although it can be puzzling from
the viewpoint of previous results that explicitly or implic-
itly penalizes the use of more complex “larger” hypothesis
spaces (e.g., see Zhang et al. 2017).
Remark 3. The reason why both analytical learning the-
ory 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 assump-
tions. The larger complexities of a hypothesis space and in-
stability/nonrobustness (or other properties of the learning
algorithm) indeed degrade the statistical guarantee over dif-
ferent random problem instances particularly with a worst-
case distribution ˉμ 6= μ; however, it can improve the an-
alytical guarantee and practical performances for “good”
problem instances (μ, S
m
, Z
m
0
, Lˆy
A(S
m
)
).
For example, no free lunch theorems in machine learning
are well-known results, typically proven with the worst-
case distribution ˉμ 6= μ for a fixed A or H over random
different instances, rather than each individual instance
(μ, S
m
, Z
m
0
, Lˆy
A(S
m
)
).
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 star-
discrepancy D
∗
[T
∗
μ, T (Z
m
0
)] that appears in Theorem 1.
Proposition 2 is a direct consequence of (Heinrich et al.,
2001, Theorem 2).
Proposition 2. Let
T (Z
m
0
) = {T (z
(1)
), . . . , T (z
(m
0
)
)} =
{t
(1)
, . . . , t
(m
0
)
}
be a set of i.i.d. random variables with
values on [0, 1]
d
and distribution T
∗
μ. Then, there exists
a positive constant c
1
such that for all m
0
∈ N
+
and all
c
2
≥ c
1
, with probability at least 1 − δ,
D
∗
[T
∗
μ, T (Z
m
0
)] ≤ c
2
r
d
m
0
where δ =
1
c
2
√
d
(c
1
c
2
2
e
−2c
2
2
)
d
with c
1
c
2
2
e
−2c
2
2
< 1.
Remark 4. Proposition 2 is not probabilistically vacuous
in the sense that we can increase c
2
to obtain 1 − δ > 0, at
the cost of increasing the constant c
2
in the bound. Forcing
1 − δ > 0 still keeps c
2
constant without dependence on
relevant variables such as d and m
0
. This is because 1 −
δ > 0 if c
2
is large enough such that c
1
c
2
2
< e
2c
2
2
, which
depends only on the constants.
Using Proposition 2, one can immediately provide a sta-
tistical bound via Theorem 1 over random Z
m
0
. To see
how such a result differs from that of statistical learning
theory, consider the case of Z
m
0
= S
m
. Whereas statistical