Despite being tremendously overparameterized, it is appreciated that deep
neural networks trained by stochastic gradient descent (SGD) generalize
surprisingly well. Based on the Rademacher complexity of a pre-specified
hypothesis set, different norm-based generalization bounds have been developed
to explain this phenomenon. However, recent studies suggest these bounds might
be problematic as they increase with the training set size, which is contrary
to empirical evidence. In this study, we argue that the hypothesis set SGD
explores is trajectory-dependent and thus may provide a tighter bound over its
Rademacher complexity. To this end, we characterize the SGD recursion via a
stochastic differential equation by assuming the incurred stochastic gradient
noise follows the fractional Brownian motion. We then identify the Rademacher
complexity in terms of the covering numbers and relate it to the Hausdorff
dimension of the optimization trajectory. By invoking the hypothesis set
stability, we derive a novel generalization bound for deep neural networks.
Extensive experiments demonstrate that it predicts well the generalization gap
over several common experimental interventions. We further show that the Hurst
parameter of the fractional Brownian motion is more informative than existing
generalization indicators such as the power-law index and the upper
Blumenthal-Getoor index.

通过探究 SGD 的轨迹依赖假设集，建立基于 Hausdorff 维数的 Rademacher 复杂度，并通过假设集稳定性推导具有预测力的 DNN 的新型泛化边界。

利用分数布朗运动得出的深度神经网络的轨迹相关的泛化界

Trajectory-dependent Generalization Bounds for Deep Neural Networks via Fractional Brownian Motion

Despite its success in a wide range of applications, characterizing the
generalization properties of stochastic gradient descent (SGD) in non-convex
deep learning problems is still an important challenge. While modeling the
trajectories of SGD via stochastic differential equations (SDE) under
heavy-tailed gradient noise has recently shed light over several peculiar
characteristics of SGD, a rigorous treatment of the generalization properties
of such SDEs in a learning theoretical framework is still missing. Aiming to
bridge this gap, in this paper, we prove generalization bounds for SGD under
the assumption that its trajectories can be well-approximated by a \emph{Feller
process}, which defines a rich class of Markov processes that include several
recent SDE representations (both Brownian or heavy-tailed) as its special case.
We show that the generalization error can be controlled by the \emph{Hausdorff
dimension} of the trajectories, which is intimately linked to the tail behavior
of the driving process. Our results imply that heavier-tailed processes should
achieve better generalization; hence, the tail-index of the process can be used
as a notion of "capacity metric". We support our theory with experiments on
deep neural networks illustrating that the proposed capacity metric accurately
estimates the generalization error, and it does not necessarily grow with the
number of parameters unlike the existing capacity metrics in the literature.

本文提出了一种使用 Feller 过程来逼近 SGD 轨迹以及使用 Hausdorff 维度控制相关广义误差的学习理论框架，同时提出了使用 Feller 过程的尾部指数作为 “容量度量” 的概念，可用于估计广义误差，并且与参数数量不同于现有文献中的容量度量。

神经网络中的豪斯多夫维数、重尾及泛化

Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks

We construct random metric spaces by gluing together an infinite sequence of
pointed metric spaces that we call blocks. At each step, we glue the next block
to the structure constructed so far by randomly choosing a point on the
structure and then identifying it with the distinguished point of the block.
The random object that we study is the completion of the structure we obtain
after an infinite number of steps. We introduce a sequence $(w_n)_{n\geq1}$
that we call the weights of the blocks. The probability at each step that the
next block is glued onto any of the preceding blocks is proportional to its
weight. We suppose that the blocks are i.i.d. copies of the same random metric
space, scaled by deterministic factors that we call $(\lambda_n)_{n\geq 1}$. We
work under some conditions on the distribution of the blocks ensuring that they
a.s. have dimension $d$, for some $d>0$. The main contribution of this paper is
the computation of the Hausdorff dimension of the set $\mathcal{L}$ of points
which appear during the completion procedure, which we call the leaves, when
$(\lambda_n)_{n\geq 1}$ and $(w_n)_{n\geq1}$ typically behave like a power of
$n$, say $n^{-\alpha}$ for the scaling factors and $n^{-\beta}$ for the
weights. For a large domain of $\alpha$ and $\beta$, we have
$\mathrm{dim_H}(\mathcal{L})=\alpha^{-1}$. However for $\beta>1$ and
$\alpha<1/d$, our results reveal an interesting phenomenon: the dimension has a
non-trivial dependence in $\alpha$, $\beta$ and $d$, namely
$\mathrm{dim_H}(\mathcal{L})=\alpha^{-1}(2\beta-1-2\sqrt{(\beta-1)(\beta-d\alpha)})$.}

本文研究了随机构造的度量空间中叶子集合的 Hausdorff 维度，当缩放因子和权重通常遵循幂律时，如 n ^ -α 和 n ^ -β。我们发现，对于一定的 α 和 β 范围，叶子的 Hausdorff 维度为 α-1。但是，当 β>1 且 α<1/d 时，维度具有 α，β 和 d 的非平凡依赖关系，即 Hausdorff 维度为 α^-1 (2β-1-2sqrt ((β-1)(β-dα)))。

度量空间的随机粘合

Random gluing of metric spaces

We study the geometry of the space of measures of a compact ultrametric space
X, endowed with the L^p Wasserstein distance from optimal transportation. We
show that the power p of this distance makes this Wasserstein space affinely
isometric to a convex subset of l^1. As a consequence, it is connected by
1/p-H\"older arcs, but any a-H\"older arc with a>1/p must be constant. This
result is obtained via a reformulation of the distance between two measures
which is very specific to the case when X is ultrametric; howeverthanks to the
Mendel-Naor Ultrametric Skeleton it has consequences even when X is a general
compact metric space. More precisely, we use it to estimate the size of
Wasserstein spaces, measured by an analogue of Hausdorff dimension that is
adapted to (some) infinite-dimensional spaces. The result we get generalizes
greatly our previous estimate that needed a strong rectifiability assumption.
The proof of this estimate involves a structural theorem of independent
interest: every ultrametric space contains large co-Lipschitz images of
\emph{regular} ultrametric spaces, i.e. spaces of the form {1,...,k}^N with a
natural ultrametric. We are also lead to an example of independent interest: a
space of positive lower Minkowski dimension, all of whose proper closed subsets
have vanishing lower Minkowski dimension.

研究了紧超度量空间 X 的测度空间的几何形状，表明此 Wasserstein 空间的幂 p 使其成为 l^1 的凸子集，证明了关于超度量情况下 Wasserstein 空间的边界和尺寸估计，以及证明了关于超度量空间包含大的 co-Lipschitz 图像的结构定理。