![](https://csdnimg.cn/release/download_crawler_static/12279615/bg6.jpg)
Kawaguchi, Kaelbling, and Bengio
Figure 1: An illustration of differences in assumptions. Statistical learning theory analyzes
the generalization behaviors of f
A(S
m
)
over randomly-drawn unspecified datasets S
m
∈ D
according to some unspecified distribution P ∈ P. Intuitively, statistical learning theory
concerns more about questions regarding a set P × D because of the unspecified nature of
(P, S
m
), whereas certain empirical studies (e.g., Zhang et al. 2017) can focus on questions
regarding each specified point (P, S
m
) ∈ P × D.
Lower bounds, necessary conditions and tightness in statistical learning theory are typi-
cally defined via a worst-case distribution P
worst
∈ P. For instance, classical “no free lunch”
theorems and certain lower bounds on the generalization gap (e.g., Mohri et al. 2012, Sec-
tion 3.4) have been proven for the worst-case distribution P
worst
∈ P. Therefore, “tight”
and “necessary” typically mean “tight” and “necessary” for the set P × D (e.g., through
the worst or average case), but not for each particular point (P, S
m
) ∈ P × D. From this
viewpoint, we can understand that even if the quality of the set P × D is “bad” overall,
there may exist a “good” point (P, S
m
) ∈ P × D.
Several approaches in statistical learning theory, such as the data-dependent and Bayesian
approaches (Herbrich and Williamson, 2002; Dziugaite and Roy, 2017), use more assump-
tions on the set P×D to take advantage of more prior and posterior information; these have
an ability to tackle Problem 1. However, these approaches do not apply to Problem 2 as
they still depend on other factors than the given (P, S
m
, f ). For example, data-dependent
bounds with the luckiness framework (Shawe-Taylor et al., 1998; Herbrich and Williamson,
2002) and empirical Rademacher complexity (Koltchinskii and Panchenko, 2000; Bartlett
et al., 2002) still depend on a concept of hypothesis spaces (or the sequence of hypothesis
spaces), and the robustness approach (Xu and Mannor, 2012) depend on different datasets
than a given S
m
via the definition of robustness (i.e., in Section 2, ζ(S
m
) is a data-dependent
term, but the definition of ζ itself and Ω depend on other datasets than S
m
).
We note that analyzing a set P × D is of significant interest for its own merits and is a
natural task along the field of computational complexity (e.g., categorizing a set of problem
instances into subsets with or without polynomial solvability). Indeed, the situation where
theory focuses more on a set and many practical studies focus on each element in the set
is prevalent in computer science (see the discussion in Appendix B.1 for more detail). We
further validate the logical consistency in our observations in Appendix B.2 and propose
several practical roles of generalization theory in Appendix B.3.
4. Direct Analyses of Neural Networks
In the previous section, we extended Problem 1 to Problem 2, and identified the different
assumptions in theoretical and empirical studies. Accordingly, this section aims to solve
these problems, both in the case of each specified dataset and the case of random unspecified
datasets. To achieve this goal, this section presents a direct analysis of neural networks,
6