[warnfilt]latexfontCommand invalid in math mode [warnfilt]

# Fractal Structure and Generalization Properties of Stochastic Optimization
Algorithms

Alexander Camuto<EMAIL_ADDRESS>
Department of Statistics, University of Oxford & Alan Turing Institute George
Deligiannidis<EMAIL_ADDRESS>
Department of Statistics, University of Oxford & Alan Turing Institute Murat
A. Erdogdu<EMAIL_ADDRESS>
Department of Computer Science and Department of Statistical Sciences at
University of Toronto & Vector Institute Mert Gürbüzbalaban∗
<EMAIL_ADDRESS>
Department of Management Science and Information Systems, Rutgers Business
School Umut Şimşekli∗<EMAIL_ADDRESS>
INRIA - Département d’Informatique de l’École Normale Supérieure - PSL
Research University Lingjiong Zhu<EMAIL_ADDRESS>
Department of Mathematics, Florida State University
The authors are in alphabetical order
∗ Corresponding authors

###### Abstract

Understanding generalization in deep learning has been one of the major
challenges in statistical learning theory over the last decade. While recent
work has illustrated that the dataset and the training algorithm must be taken
into account in order to obtain meaningful generalization bounds, it is still
theoretically not clear which properties of the data and the algorithm
determine the generalization performance. In this study, we approach this
problem from a dynamical systems theory perspective and represent stochastic
optimization algorithms as _random iterated function systems_ (IFS). Well
studied in the dynamical systems literature, under mild assumptions, such IFSs
can be shown to be ergodic with an invariant measure that is often supported
on sets with a _fractal structure_. As our main contribution, we prove that
the generalization error of a stochastic optimization algorithm can be bounded
based on the ‘complexity’ of the fractal structure that underlies its
invariant measure. Leveraging results from dynamical systems theory, we show
that the generalization error can be explicitly linked to the choice of the
algorithm (e.g., stochastic gradient descent – SGD), algorithm hyperparameters
(e.g., step-size, batch-size), and the geometry of the problem (e.g., Hessian
of the loss). We further specialize our results to specific problems (e.g.,
linear/logistic regression, one hidden-layered neural networks) and algorithms
(e.g., SGD and preconditioned variants), and obtain analytical estimates for
our bound. For modern neural networks, we develop an efficient algorithm to
compute the developed bound and support our theory with various experiments on
neural networks.

##  1 Introduction

In statistical learning, many problems can be naturally formulated as a risk
minimization problem

$\displaystyle\min\limits_{w\in\mathbb{R}^{d}}\Bigl{\\{}\mathcal{R}(w):=\mathbb{E}_{z\sim\pi}[\ell(w,z)]\Bigr{\\}},$
(1)

where $z\in\mathcal{Z}$ denotes a data sample coming from an unknown
distribution $\pi$, and
$\ell:\mathbb{R}^{d}\times\mathcal{Z}\to\mathbb{R}_{+}$ is the composition of
a loss and a function from the hypothesis class parameterized by
$w\in\mathbb{R}^{d}$. Since the distribution $\pi$ is unknown, one needs to
rely on empirical risk minimization as a surrogate to (1),

$\displaystyle\min\nolimits_{w\in\mathbb{R}^{d}}\Bigl{\\{}\hat{\mathcal{R}}(w,\mathbf{S}_{n}):=({1}/{n})\sum\nolimits_{i=1}^{n}\ell(w,z_{i})\Bigr{\\}},$
(2)

where $\mathbf{S}_{n}:=\\{z_{1},\dots,z_{n}\\}$ denotes a _training set_ of
$n$ points that are independently and identically distributed (i.i.d.) and
sampled from $\pi$, and model training often amounts to using an optimization
algorithm to solve the above problem.

Statistical learning theory is mainly interested in understanding the behavior
of the _generalization error_ , i.e.,
$\hat{\mathcal{R}}(w,\mathbf{S}_{n})-\mathcal{R}(w)$. While classical results
suggest that models with large number of parameters should suffer from poor
generalization [SSBD14, AB09], modern neural networks challenge this classical
wisdom: they can fit the training data perfectly, yet manage to generalize
well [ZBH+17, NBMS17]. Considering that the generalization error is influenced
by many factors involved in the training process, the conventional algorithm-
and data-agnostic uniform bounds are typically overly pessimistic in a deep
learning setting. In order to obtain meaningful, non-vacuous bounds, the
underlying data distribution and the choice of the optimization algorithm need
to be incorporated in the generalization bounds [ZBH+17, DR17].

Our goal in this study is to develop novel generalization bounds that
explicitly incorporate the data and the optimization dynamics, through the
lens of dynamical systems theory. To motivate our approach, let us consider
stochastic gradient descent (SGD), which has been one of the most popular
optimization algorithms for training neural networks. It is defined by the
following recursion:

$\displaystyle
w_{k}=w_{k-1}-\eta\nabla\tilde{\mathcal{R}}_{k}(w_{k-1}),\quad\mbox{where}\quad\nabla\tilde{\mathcal{R}}_{k}(w):=\nabla\tilde{\mathcal{R}}_{\Omega_{k}}(w):=(1/b)\sum\limits_{i\in\Omega_{k}}\nabla\ell(w,z_{i}).$

Here, $k$ represents the iteration counter, $\eta>0$ is the step-size (also
called the learning-rate), $\nabla\tilde{\mathcal{R}}_{k}$ is the stochastic
gradient, $b$ is the batch-size, and $\Omega_{k}\subset\\{1,2,\dots,n\\}$ is a
random subset drawn with or without replacement with cardinality
$|\Omega_{k}|=b$ for all $k$.

Constant step-size SGD forms a Markov chain with a stationary distribution
$w_{\infty}\sim\mu$, which exists and is unique under mild conditions [DDB20,
YBVE20], and intuitively we can expect that the generalization performance of
the trained model to be intimately related to the behavior of the risk
$\mathcal{R}(w)$ over this limit distribution $\mu$. In particular, the Markov
chain defined by the SGD recursion can be written by using random functions
$h_{\Omega_{k}}$ at each SGD iteration $k$, i.e.,

$w_{k}=h_{\Omega_{k}}(w_{k-1}),\ \ \text{ with }\ \
h_{\Omega_{k}}(w)=w-\eta\nabla\tilde{\mathcal{R}}_{k}(w).$ (3)

Figure 1:  Middle-third Cantor set as the support of the stationary
distribution of constant step-size SGD for $\ell(w,z_{1})=w^{2}/2$ and
$\ell(w,z_{2})=w^{2}/2-w$.

Here, the randomness in $h_{\Omega_{k}}$ is due to the selection of the subset
$\Omega_{k}$. In fact, such a formulation is not specific to SGD; it can cover
many other stochastic optimization algorithms if the random function
$h_{\Omega_{k}}$ is selected accordingly, including second-order algorithms
such as _preconditioned SGD_ [Li17]. Such random recursions (3) and
characteristics of their stationary distribution have been studied extensively
under the names of _iterated random functions_ [DF99] and _iterated function
system_ (IFS) [Fal04]. In this paper, from a high level, we relate the
‘complexity of the stationary distribution’ of a particular IFS to the
generalization performance of the trained model.

We illustrate our context in two toy examples. In the first one, we consider a
1-dimensional quadratic problem with $n=2$ and $\ell(w,z_{1})=w^{2}/2$ and
$\ell(w,z_{2})=w^{2}/2-w$. We run SGD with constant step-size $\eta$ to
minimize the resulting empirical risk. We simply choose
$\Omega_{k}\subset\\{1,2\\}$ uniformly random with batch-size $b=1$, and we
plot the histograms of stationary distributions for different step-size
choices $\eta\in\\{1/100,1/3,2/3\\}$ in Figure 1. We observe that the
_support_ of the stationary distribution of SGD depends on the step-size: As
the step-size increases the support becomes less dense and a _fractal
structure_ in the stationary distribution can be clearly observed. This
behavior is not surprising, at least for this toy example. It is well-known
that the set of points that is invariant under the resulting IFS (termed as
the attractor of the IFS) for the specific choice of $\eta=2/3$ is the famous
‘middle-third Cantor set’ [FW09], which coincides with the support of the
stationary distribution of the SGD.

As another example, we run SGD with constant step-size in order to train an
ordinary linear regression model for a dataset of $n=5$ samples and $d=2$
dimensions, i.e., $a_{i}^{\top}w\approx y_{i}$, where for $i=1,\dots,5$,
$y_{i}$ and each coordinate of $a_{i}$ are drawn uniformly at random from the
interval $[-1,1]$. Figure 2 shows the heatmap of the resulting stationary
distributions for different step-size choices $\eta$ ranging from $0.1$ to
$0.9$ (bright colors represent higher density). We observe that for small
step-size choices, the stationary distribution is dense, whereas a fractal
structure can be clearly observed as the step-size gets larger.

Fractals are complex patterns and the level of this complexity is typically
measured by the _Hausdorff dimension_ of the fractal, which is a notion of
dimension that can take fractional values111The Hausdorff dimension of the
middle-third Cantor set in Figure 1 is $\log_{3}(2)\approx 0.63$ whereas the
ambient dimension is $1$ [Fal04, Example 2.3]., and can be much smaller than
the ambient dimension $d$. Recently, assuming that SGD trajectories can be
well-approximated by a certain type of stochastic differential equations
(SDE), it is shown that the generalization error can be controlled by the
Hausdorff dimension of the trajectories of the SDE, instead of their ambient
dimension $d$ [ŞSDE20]. That is, the ambient dimension that appears in
classical learning theory bounds is replaced with the Hausdorff dimension. The
fractal geometric approach presented in [ŞSDE20] can capture the ‘low
dimensional structure’ of fractal sets and provides an alternative perspective
to the compression-based approaches that aim to understand why
overparametrized networks do not overfit [AGNZ18, SAN20, SAM+20, HJTW21].

However, SDE approximations for SGD often serve as mere heuristics, and
guaranteeing a good approximation typically requires unrealistically small
step-sizes [LTE19]. For more realistic step-sizes, theoretical concerns have
been raised about the validity of conventional SDE approximations for SGD
[LMA21, GŞZ20, Yai19]. Another drawback of the SDE approximation is that the
bounds in [ŞSDE20] are implicit, in the sense that they cannot be related to
algorithm hyperparameters, problem geometry, or data. We address these issues
and present a direct, _discrete-time_ analysis by exploiting the connections
between IFSs and stochastic optimization algorithms.

Our contributions are summarized as follows:

  * •

We extend [ŞSDE20] and show that the generalization error can be linked to the
Hausdorff dimension of _invariant measures_ (rather than the Hausdorff
dimension of _sets_ as in [ŞSDE20]). More precisely, under appropriate
conditions, we establish a generalization bound for the stationary
distribution of IFS $w_{\infty}\sim\mu$. That is, with probability at least
$1-2\zeta$,

$\displaystyle|\hat{\mathcal{R}}(w_{\infty},\mathbf{S}_{n})-\mathcal{R}(w_{\infty})|\lesssim\sqrt{\frac{\overline{\dim}_{\mathrm{H}}\mu\,\log^{2}(n)}{n}+\frac{\log(1/\zeta)}{n}},$
(4)

for $n$ large enough, where $\overline{\dim}_{\mathrm{H}}\mu$ is the (upper)
Hausdorff dimension of the measure $\mu$.

  * •

By leveraging results from IFS theory, we further link
$\overline{\dim}_{\mathrm{H}}\mu$ to (i) the form of the recursion (e.g.,
$h_{\Omega_{k}}$ in (3)), (ii) algorithm hyperparameters (e.g., $\eta$, $b$),
and (iii) problem geometry (e.g., Hessian of $\tilde{\mathcal{R}}_{k}$),
through a single term, which encapsulates all these components and their
interaction.

  * •

We establish bounds on $\overline{\dim}_{\mathrm{H}}\mu$ for SGD and
preconditioned SGD algorithms, when used to minimize various empirical risk
minimization problems such as least squares, logistic regression, support
vector machines. In all cases, we explicitly link the generalization
performance of the model to the hyperparameters of the underlying training
algorithm.

  * •

Finally, we numerically compute key quantities that appear in our
generalization bounds, and show empirically that they have a statistically
significant correlation with the generalization error.

(a) $\eta=0.3$ (b) $\eta=0.5$ (c) $\eta=0.7$ (d) $\eta=0.9$

Figure 2: The stationary distribution of constant step-size SGD for linear
regression, where we have $n=5$ data points and $w\in\mathbb{R}^{2}$.

Notation and preliminaries.  $B_{d}(x,r)\subset\mathbb{R}^{d}$ denotes the
closed ball centered around $x\in\mathbb{R}^{d}$ with radius $r$.

A function $f:\mathbb{R}^{d_{1}}\to\mathbb{R}^{d_{2}}$ is said to be (Fréchet)
differentiable at $x\in\mathbb{R}^{d_{1}}$ if there exists a $d_{1}\times
d_{2}$ matrix ${\displaystyle
J_{f}(x):\mathbb{R}^{d_{1}}\to\mathbb{R}^{d_{2}}}$ such that $\lim_{\|h\|\to
0}\|f(x+h)-f(x)-J_{f}(x)h\|/\|h\|=0$. The matrix $J_{f}(x)$ is called the
differential of $f$, also known as the Jacobian matrix at $x$, and determinant
of $J_{f}(x)$ is called the Jacobian determinant [HS74]. For real-valued
functions $f,g$, we define $f(n)=\omega(g(n))$ if
$\lim_{n\rightarrow\infty}|f(n)|/g(n)=\infty$. For a set $A$, $|A|$ denotes
its cardinality.

##  2 Technical Background on Fractal Geometry

Fractal sets emerge virtually in all branches of science, and fractal-based
techniques have been used in machine learning [SHTY13, MSS19, DSD20, ŞSDE20,
AGZ21]. The inherent ‘complexity’ of a fractal set often plays an important
role and it is typically measured by its _fractal dimension_ , where several
notions of dimension have been proposed [Fal04]. In this section, we briefly
mention two important notions of fractal dimension, which will be used in our
theoretical development.

Minkowski dimension of a set.  The Minkowski dimension (also known as the box-
counting dimension [Fal04]) is defined as follows. Let
$F\subset\mathbb{R}^{d}$ be a set and for $\delta>0$, let $N_{\delta}(F)$
denote a collection of sets that contains the smallest number of closed balls
of diameter at most $\delta$ which cover $F$. Then the upper-Minkowski
dimension of $F$ is defined as follows:

$\overline{\dim}_{\mathrm{M}}F:=\limsup\limits_{\delta\to
0}\Bigl{[}{\log|N_{\delta}(F)|}\>/\>{\log(1/\delta)}\Bigr{]}.$ (5)

To visualize the upper-Minkowski dimension of a set $F$, consider the set $F$
lying on an evenly spaced grid and count how many boxes are required to cover
the set. The upper-Minkowski dimension measures how this number changes as the
grid is made finer using a box-counting algorithm.

Hausdorff dimension of a set.  An alternative to the purely geometric
Minkowski dimension, the Hausdorff dimension [Hau18] is a measure theoretical
notion of fractal dimension. It is based on the _Hausdorff measure_ , which
generalizes the traditional notions of area and volume to non-integer
dimensions [Rog98]. More precisely, for $s\geq 0$, let
$F\subset\mathbb{R}^{d}$ and $\delta>0$, and denote
$\mathcal{H}_{\delta}^{s}(F):=\inf\sum_{i=1}^{\infty}\operatorname{diam}(A_{i})^{s}$,
where the infimum is taken over all the $\delta$-coverings $\\{A_{i}\\}_{i}$
of $F$, that is, $F\subset\cup_{i}A_{i}$ with
$\operatorname{diam}(A_{i})<\delta$ for every $i$. The $s$-dimensional
Hausdorff measure of $F$ is defined as the monotone limit
$\mathcal{H}^{s}(F):=\lim_{\delta\rightarrow 0}\mathcal{H}_{\delta}^{s}(F)$.
When $s\in\mathbb{N}$, $\mathcal{H}^{s}$ is the $s$-dimensional Lebesgue
measure up to a constant factor; hence the generalization of ‘volume’ to
fractional orders.

Based on the Hausdorff measure, the _Hausdorff dimension_ of a set
$F\subset\mathbb{R}^{d}$ is then defined as follows:

$\dim_{\mathrm{H}}F:=\sup\left\\{s>0:\mathcal{H}^{s}(F)>0\right\\}=\inf\left\\{s>0:\mathcal{H}^{s}(F)<\infty\right\\}.$

In other words, the Hausdorff dimension of $F$ is the ‘moment’ $s$ when
$\mathcal{H}^{s}(F)$ drops from $\infty$ to $0$, that is,
$\mathcal{H}^{r}(F)=0$ for all $r>\dim_{\mathrm{H}}F$ and
$\mathcal{H}^{r}(F)=\infty$ for all $r<\dim_{\mathrm{H}}F$.

We always have $0\leq\dim_{\mathrm{H}}F\leq d$, and when $F$ is bounded, we
always have $0\leq\dim_{\mathrm{H}}F\leq\overline{\dim}_{\mathrm{M}}F\leq d$
[Fal04]. Furthermore, the Hausdorff dimension of $\mathbb{R}^{d}$ equals $d$,
and the Hausdorff dimension of smooth Riemannian manifolds correspond to their
intrinsic dimension, e.g. $\dim_{\mathrm{H}}\mathbb{S}^{d-1}=d-1$, where
$\mathbb{S}^{d-1}$ is the unit sphere in $\mathbb{R}^{d}$.

Hausdorff dimension of a probability measure.  IFSs generate invariant
measures as the number of iterates goes to infinity, and random fractals arise
from such invariant measures. There has been a growing literature that studies
the structure of such random fractals [Saz00, NSB02, MS02, Ram06, FST06,
JR08], where the notion of fractal dimension can be extended to measures, and
our theory will rely on the Hausdorff dimension of invariant measures
associated with stochastic optimization algorithms. In particular, we will
mainly use the _upper Hausdorff dimension_ $\overline{\dim}_{\mathrm{H}}\mu$
of a Borel probability measure $\mu$ on $\mathbb{R}^{d}$, which is defined as
follows:
$\overline{\dim}_{\mathrm{H}}\mu:=\inf\left\\{\dim_{\mathrm{H}}A:\mu(A)=1\right\\}$.
In other words, $\overline{\dim}_{\mathrm{H}}\mu$ is the smallest Hausdorff
dimension of all measurable sets with full measure.

##  3 Generalization Bounds for Stochastic Optimization Algorithms as IFSs

In this section, we will present our main theoretical results which relate the
generalization error to the upper-Hausdorff dimension of the invariant measure
associated with a stochastic optimization algorithm. We consider a standard
supervised learning setting, where $\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$,
where $\mathcal{X}$ is the space of features and $\mathcal{Y}$ is the space of
labels, and $\pi$ is the unknown data distribution on $\mathcal{Z}$.

For mathematical convenience, in order to construct the training set with $n$
elements, we first consider an _infinite sequence_ of i.i.d. data samples from
the data distribution $\pi$, then we take the first $n$ elements from this
infinite sequence. More precisely, we consider the (countable) product measure
$\pi^{\infty}=(\pi\otimes\pi\otimes\dots)$ defined on the cylindrical sigma-
algebra. Then, we consider the infinite i.i.d. data sequence as
$\mathbf{S}\sim\pi^{\infty}$, i.e., $\mathbf{S}=(z_{j})_{j\geq 1}$ with
$z_{j}\stackrel{{\scriptstyle\mathclap{\mbox{\tiny{i.i.d.}}}}}{{\sim}}\pi$ for
all $j=1,2,\dots$. Finally, we define the training set as
$\mathbf{S}_{n}:=(z_{1},\dots,z_{n})$, i.e., we take the first $n$ elements of
$\mathbf{S}$. To avoid technical complications, throughout the paper we will
assume that all the encountered functions and sets are measurable. All the
proofs are given in the supplement.

Given a dataset $\mathbf{S}_{n}$, we represent the _training algorithm_ as an
IFS, which is based on the following recursion:
$w_{k}=h_{\Omega_{k}}(w_{k-1};\mathbf{S}_{n})$, where the mini-batch
$\Omega_{k}$ is i.i.d. sampled according to some distribution (e.g., sampling
without-replacement uniformly among all possible mini-batches). This compact
representation enables us to cover a broad range of optimization algorithms
with a unified notation, including SGD (see (3)), as well as preconditioned
SGD, and stochastic Newton methods. For example, if we take
$h_{\Omega_{k}}(w;\mathbf{S}_{n})=w-\eta{H}_{k}(w)^{-1}\nabla\tilde{\mathcal{R}}_{k}(w)$
where ${H}_{k}(w)$ is an estimate of the Hessian of $\tilde{\mathcal{R}}_{k}$,
we cover stochastic Newton methods [EM15]. Similar constructions can be made
for other popular algorithms, such as SGD-momentum [Qia99], RMSProp [HSS12],
or Adam [KB15].

Notice that there are only finitely many values that $\Omega_{k}$ can take.
For example, in the case of without-replacement mini-batch sampling with
batch-size $b$, there are in total $m_{b}=\binom{n}{b}$ many subsets of
$\\{1,2,\dots,n\\}$ with cardinality $b$. Alternatively, a more realistic
setup would be to divide the dataset into $m_{b}=n/b$ batches with each batch
having $b$ elements, and at each iteration $k$, we can randomly choose one of
the batches. In both examples we can enumerate as
$S_{1},S_{2},\dots,S_{m_{b}}$. If the probability of sampling the mini-batch
$\Omega_{k}=S_{i}$ is $p_{i}$ for every $i$, then, with a slight abuse of
notation, we can rewrite the IFS recursion as:

$w_{k}=h_{U_{k}}(w_{k-1};\mathbf{S}_{n}),$ (6)

where $U_{k}$ is a random variable taking values in $\\{1,2,\dots,m_{b}\\}$
and $p_{i}:=\mathbb{P}(U_{k}=i)$. If the mini-batch sampling is uniform (i.e.,
the default option in practice), we have $p_{i}=1/m_{b}$; however, we are not
restricted to this option, the sampling scheme is allowed to be more general.
We finally call the triple
$(\mathbb{R}^{d},\\{h_{i}(\cdot;\mathbf{S}_{n})\\}_{i=1}^{m_{b}},\\{p_{i}\\}_{i=1}^{m_{b}})$
an iterated function system (IFS).

Given a dataset $\mathbf{S}_{n}$, we are interested in the limiting behavior
of the training algorithm (6). We characterize this behavior by considering
the invariant measure $\mu_{W|\mathbf{S}_{n}}$ of the IFS (also called
stationary distribution), that is a Borel probability measure on
$\mathbb{R}^{d}$, such that $w_{\infty}\sim\mu_{W|\mathbf{S}_{n}}$. To be able
to work in this context, we first need to ensure that the recursion (6) admits
an invariant measure, i.e., $\mu_{W|\mathbf{S}_{n}}$ exists. Accordingly, we
require the following mild conditions on the IFS (6). Let $U$ be a random
variable with the same distribution as $U_{k}$. If the recursion (6) is
_Lipschitz on average_ , i.e.,

$\displaystyle\mathbb{E}[L_{U}\>|\>\mathbf{S}_{n}]<\infty,\quad\mbox{with}\quad
L_{U}:=\sup\limits_{x,y\in\mathbb{R}^{d}}\frac{\|h_{U}(x;\mathbf{S}_{n})-h_{U}(y;\mathbf{S}_{n})\|}{\|x-y\|},$
(7)

and is _contractive on average_ , i.e., if

$\mathbb{E}\left[\log(L_{U})\>|\>\mathbf{S}_{n}\right]=\sum\limits_{i=1}^{m_{b}}p_{i}\log(L_{i})<0,\qquad\text{with
\phantom{aa} $p_{i}>0$, for any $i=1,\dots,m_{b}$},$ (8)

then it can be shown that the process is ergodic and admits a unique invariant
measure where the limit

$\rho:=\lim\limits_{k\to\infty}(1/k)\log\left\|h_{U_{k}}h_{U_{k-1}}\cdots
h_{U_{1}}\right\|$

exists almost surely and is a constant [Elt90], where $\rho$ is called the
_Lyapunov exponent_. Furthermore, under further technical assumptions, it can
be shown that (6) is geometrically ergodic [DF99].

Our goal will be to relate the generalization error to
$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$. To achieve this goal, at
first sight, it might seem tempting to extract a full-measure set $A$ by using
the definition of $\mu_{W|\mathbf{S}_{n}}$, such that
$\mu_{W|\mathbf{S}_{n}}(A)=1$ and
$\dim_{\mathrm{H}}A\approx\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$,
and then directly invoke the results from [ŞSDE20], which would link the
generalization error to $\dim_{\mathrm{H}}A$, hence, also to
$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$. However, since [ŞSDE20]
does not consider an IFS framework, the conditions they require (e.g.,
boundedness of $A$, $\dim_{\mathrm{M}}A=\dim_{\mathrm{H}}A$) are not suited to
IFSs, and hence prevent us from directly using their results.

As a remedy, we make a detour and show that we can find _almost full-measure_
sets $A$, such that $\mu_{W|\mathbf{S}_{n}}(A)\approx 1$ and
$\overline{\dim}_{\mathrm{M}}A\approx\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$
(notice that in this case we directly use the Minkowski dimension of $A$, as
opposed to its Hausdorff dimension). To achieve this goal, we require the
following geometric regularity condition on the invariant measure.

######  H 1.

For $\pi^{\infty}$-almost all $\mathbf{S}$ and all $n\in\mathbb{N}_{+}$, the
recursion (6) satisfies (7) and (8) and the limit

$\lim_{r\to 0}\Bigl{[}{\log\mu_{W|\mathbf{S}_{n}}(B_{d}(w,r))}\>/\>{\log
r}\Bigr{]}$

exists for $\mu_{W|\mathbf{S}_{n}}$-almost every $w$.

This is a common condition [Pes08] and is satisfied for a large class of
measures. For instance, ‘sufficiently regular’ measures with the property that
$C_{1}r^{s}\leq\mu(B(x,r))\leq C_{2}r^{s}$ for some constant $s>0$ and
positive constants $C_{1}$, $C_{2}$ will satisfy this assumption. Such
measures are called Ahlfors-regular (cf. [ŞSDE20, Assumption H4] for a related
condition), and it is known that IFSs that satisfy certain ‘open set
conditions’ lead to Ahlfors regular invariant measures (see [MT10, Section
8.3]). Yet, our assumption is more general and does not immediately require
Ahlfors-regularity. Under H 1, we now formalize our key observation, which
serves as the basis for our bounds.

######  Proposition 1.

Assume that H 1 holds. Then for every $\varepsilon>0$, $n\in\mathbb{N}_{+}$,
and $\pi^{\infty}$-almost every $\mathbf{S}$, there exists
$\delta:=\delta(\varepsilon,\mathbf{S}_{n})\in(0,1]$ and a bounded measurable
set $A_{\mathbf{S}_{n},\delta}\subset\mathbb{R}^{d}$, such that

$\displaystyle\mu_{W|\mathbf{S}_{n}}(A_{\mathbf{S}_{n},\delta})\geq
1-\delta,\quad\text{and}\quad\overline{\dim}_{\mathrm{M}}A_{\mathbf{S}_{n},\delta}\leq\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}+\varepsilon,$
(9)

and $\delta(\varepsilon,\mathbf{S}_{n})\to 0$ as $\varepsilon\to 0$.

Thanks to this result, we can now leverage the proof technique presented in
[ŞSDE20, Theorem 2], and link the generalization error to
$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$ through
$\overline{\dim}_{\mathrm{M}}A_{\mathbf{S}_{n},\delta}$. We shall emphasize
that, mainly due to the sets $A_{\mathbf{S}_{n},\delta}$ not being of full-
measure, our framework introduces additional non-trivial technical
difficulties that we need to tackle in our proof.

We now introduce our second assumption, which roughly corresponds to a
‘topological stability’ condition, and is adapted from [ŞSDE20, Assumption
H5]. Formally, consider the (countably infinite) collection of closed balls of
radius $\beta$, whose centers are on the fixed grid
$N_{\beta}:=\left\\{\left(\frac{(2j_{1}+1)\beta}{2\sqrt{d}},\dots,\frac{(2j_{d}+1)\beta}{2\sqrt{d}}\right):j_{i}\in\mathbb{Z},i=1,\dots,d\right\\}$,
and for a set $A\subset\mathbb{R}^{d}$, define $N_{\beta}(A):=\\{x\in
N_{\beta}:B_{d}(x,\beta)\cap A\neq\emptyset\\}$, which is the collection of
the centers of the balls that intersect $A$.

######  H 2.

Let $\mathcal{Z}^{\infty}:=(\mathcal{Z}\times\mathcal{Z}\times\cdots)$ denote
the countable product endowed with the product topology and let $\mathfrak{B}$
be the Borel $\sigma$-algebra generated by $\mathcal{Z}^{\infty}$. For a Borel
set $A\subset\mathbb{R}^{d}$, let $\mathfrak{F},\mathfrak{G}$ be the
sub-$\sigma$-algebras of $\mathfrak{B}$ generated by the collections of random
variables given by
$\\{\hat{\mathcal{R}}(w,\mathbf{S}_{n}):w\in\mathbb{R}^{d},n\geq 1\\}$ and
$\Big{\\{}\mathds{1}\left\\{w\in
N_{\beta}(A)\right\\}:\beta\in\mathbb{Q}_{>0},w\in N_{\beta},n\geq 1\Big{\\}}$
respectively. There exists a constant $M\geq 1$ such that for any
$F\in\mathfrak{F}$, $G\in\mathfrak{G}$ we have $\mathbb{P}\left(F\cap
G\right)\leq M\mathbb{P}\left(F\right)\mathbb{P}(G)$ for all Borel sets $A$.

H 2 simply ensures that the dependence between the training error and the
topological properties of the support of $\mu_{W|\mathbf{S}_{n}}$ can be
controlled via $M$. Hence, it can be seen as a form of _algorithmic stability_
[BE02], where $M$ measures the level of stability of the topology of
$\mu_{W|\mathbf{S}_{n}}$: a small $M$ indicates that the geometrical structure
of $\mu_{W|\mathbf{S}_{n}}$ does not heavily depend on the particular value of
$\mathbf{S}_{n}$. The constant $M$ is also related to the mutual information
[XR17, AAV18], but may be better behaved than the mutual information as it
relies on very specific functions of the random variables.

We require one final assumption, which states that the loss $\ell$ is sub-
exponential.

######  H 3.

$\ell$ is $L$-Lipschitz continuous in $w$, and when $z\sim\pi$, for all $w$,
$\ell(w,z)$ is $(\nu,\kappa)$-sub-exponential, that is, for all
$|\lambda|<1/\kappa$, we have
$\log\mathbb{E}_{z\sim\pi}\left[\exp\left(\lambda\left(\ell(w,z)-\mathcal{R}(w)\right)\right)\right]\leq\nu^{2}\lambda^{2}/\kappa$.

Armed with these assumptions, we can now present our main result.

######  Theorem 1.

Assume that H 1, 2 and 3 hold and
$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}=\omega(\log\log(n)/\log(n))$,
$\pi^{\infty}$-almost-surely. Then, the following bound holds for sufficiently
large $n$:

$\displaystyle|\hat{\mathcal{R}}(W,\mathbf{S}_{n})-\mathcal{R}(W)|\leq
8\nu\sqrt{\frac{\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\log^{2}(nL^{2})}{n}+\frac{\log(13M/\zeta)}{n}},$
(10)

with probability at least $1-2\zeta$ over the joint distribution of
$\mathbf{S}\sim\pi^{\infty}$, $W\sim\mu_{W|\mathbf{S}_{n}}$.

This theorem shows that the Hausdorff dimension of the invariant measure acts
as a ‘capacity metric’ and the generalization error is therefore directly
linked to this metric, i.e., the complexity of the underlying fractal
structure has close links to the generalization performance. On the other
hand, the condition
$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}=\omega(\log\log(n)/\log(n))$
is very mild and makes sure that the dimension of the IFS does not decrease
very rapidly with increasing number of data points $n$. Theorem 1 enables us
to access the rich theory of IFSs, where bounds on the Hausdorff dimension are
readily available, and connect them to statistical learning theory. The
following result is a direct corollary to Theorem 1 and [Ram06, Theorem 2.1]
(see Theorem 2 in the Appendix).

######  Corollary 1.

Assume that the conditions of Theorem 1 hold. Furthermore, consider the
recursion (6) and assume that $h_{i}$ are continuously differentiable with
derivatives $h^{\prime}_{i}$ that are $\alpha$-Hölder continuous for some
$\alpha>0$. Then, there exists a constant $M>1$ such that for sufficiently
large $n$:

$\displaystyle|\hat{\mathcal{R}}(W,\mathbf{S}_{n})-\mathcal{R}(W)|\leq
8\nu\sqrt{\frac{\mathrm{Ent}\log^{2}(nL^{2})}{\left[\sum\limits_{i=1}^{m_{b}}p_{i}\int_{\mathbb{R}^{d}}\log(\|J_{h_{i}}(w)\|)\mathrm{d}\mu_{W|\mathbf{S}_{n}}(w)\right]n}+\frac{\log(13M/\zeta)}{n}},$
(11)

with probability $1-2\zeta$ over $\mathbf{S}\sim\pi^{\infty}$,
$W\sim\mu_{W|\mathbf{S}_{n}}$, where
$\mathrm{Ent}:=\sum_{i=1}^{m_{b}}p_{i}\log(p_{i})$ denotes the negative
entropy of the mini-batch sampling scheme, $\|\cdot\|$ denotes the operator
norm, and $J_{h_{i}}$ is the Jacobian of $h_{i}$ defined in the notation
section.

By this result, we discover an interesting quantity,
$\sum\nolimits_{i=1}^{m_{b}}p_{i}\int_{\mathbb{R}^{d}}\log(\|J_{h_{i}}(w)\|)\mathrm{d}\mu_{W|\mathbf{S}_{n}}(w)$,
which _simultaneously_ captures the effects of the data and the algorithm. To
see it more clearly, let us consider the SGD recursion (3), where
$\|J_{h_{i}}(w)\|=\|I-\eta\nabla^{2}\tilde{\mathcal{R}}_{S_{i}}(w)\|$ and
$\\{S_{i}\\}_{i=1}^{m_{b}}$ denotes the enumeration of the mini-batches. Then,
the overall quantity becomes

$\displaystyle\mathbb{E}_{U,W}\bigl{[}\log\|I-\eta\nabla^{2}\tilde{\mathcal{R}}_{S_{U}}(W)\|\bigr{]},$
(12)

where the expectation is taken over the mini-batch index
$U\in\\{1,\dots,m_{b}\\}$ with $\mathbb{P}(U=i)=p_{i}$, and
$W\sim\mu_{W|\mathbf{S}_{n}}$. We clearly observe that this term depends on
(i) the algorithm choice through the form of $h_{i}$, (ii) step-size $\eta$,
(iii) batch-size through $m_{b}$, (iv) problem geometry through
$\nabla^{2}\tilde{\mathcal{R}}$, and (v) data distribution through
$\mu_{W|\mathbf{S}_{n}}$. We believe that such a compact representation of all
these constituents and their interaction is novel and will open up interesting
future directions.

##  4 Analytical Estimates for the Hausdorff Dimension

The generalization bound presented in Theorem 1 applies to a number of
stochastic optimization algorithms that can be represented with an IFS and to
a large class of losses that can be non-convex or convex. It is controlled by
the Hausdorff dimension of the invariant measure $\mu_{W|\mathbf{S}_{n}}$
which needs to be estimated. In the numerical experiments section, we will
discuss how this quantity can be estimated from the dataset $\mathbf{S}_{n}$
and the iterates of the underlying algorithm.

Corollary 1 shows that for smooth losses, the Hausdorff dimension can be
controlled with the expectation of the norm of the logarithm of the Jacobian
$\log(\|J_{h_{i}}(w)\|)$ with respect to the invariant measure
$\mu_{W|\mathbf{S}_{n}}$. In general, an explicit characterization of the
invariant measure is not known. Nevertheless, under additional appropriate
assumptions that can hold in practice, such as boundedness of the data of the
loss, we next discuss that it is possible to get uniform lower and upper
bounds on the quantity $\|J_{h_{i}}(w)\|$ which leads to analytical upper
bounds on $\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$.

As illustrative examples; in the following, we will consider the setting where
we divide $\mathbf{S}_{n}$ into $m_{b}=n/b$ batches with each batch having $b$
elements, and then we discuss how analytical estimates on the (upper)
Hausdorff dimension $\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$ can
be obtained for some particular problems including least squares, regularized
logistic regression, and one hidden-layer networks. In the Appendix, we also
discuss how similar bounds can be obtained for support vector machines and
other algorithms such as preconditioned SGD and stochastic Newton methods.

Least squares.  We consider the least squares problem, with data points
$z_{i}=(a_{i},y_{i})$ and loss

$\displaystyle\ell(w,z_{i}):=\left(a_{i}^{T}w-y_{i}\right)^{2}/2+\lambda\|w\|^{2}/2,$
(13)

where $\lambda>0$ is a regularization parameter.

######  Proposition 2 (Least squares).

Consider the least squares problem (13). Assume the step-size
$\eta\in(0,\frac{1}{R^{2}+\lambda})$, where $R:=\max_{i}\|a_{i}\|$ is finite.
Then, we have the following upper bound:

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log\left(n/b\right)}{\log(1/(1-\eta\lambda))}.$
(14)

Note that here $\ell$ is only pseudo-Lipschitz $|\ell(w)-\ell(w^{\prime})|\leq
L(1+\|w\|+\|w^{\prime}\|)\|w-w^{\prime}\|$, rather than globally Lipschitz.
However; the conditions in Proposition 2 ensure that $w$ will stay in a
bounded region, in which case $\ell$ becomes Lipschitz. Also note that only
the logarithm of the Lipschitz constant directly enters the bound.

We observe that, for fixed $n$,the upper bound for
$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$ is decreasing both in
$\eta$ and $b$. This behavior is not surprising: large $\eta$ results in
chaotic behaviors (cf. Figures 1,2), and in the extreme case where $b=n$, the
algorithm becomes deterministic and hence converges to a single point, in
which case the Hausdorff dimension becomes $0$. However, the decrement due to
$b$ does not automatically grant good generalization performance: since the
algorithm becomes deterministic, the stability constant $M$ in H 2 can get
arbitrarily large, hence the bound in Theorem 1 could become vacuous. This
outcome reveals an interesting tradeoff between the Hausdorff dimension and
the constant $M$, through the batch-size $b$, and investigating this tradeoff
is an interesting future direction.

We further notice that the numerator in (14) is increasing with $n$, which
suggests that the batch-size should be taken in proportion with $n$ (i.e.,
setting $m_{b}$ to a constant value), in order to have a control over
$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$. Finally, regarding the
remaining bounds in this section, even though their forms might differ from
(14), similar remarks also apply. Hence, we will omit the discussion.

Regularized logistic regression.  Given the data points $z_{i}=(a_{i},y_{i})$,
consider regularized logistic regression with the loss:

$\ell(w,z_{i}):=\log\left(1+\exp\left(-y_{i}a_{i}^{T}w\right)\right)+\lambda\|w\|^{2}/2,$
(15)

where $\lambda>0$ is a regularization parameter. We have the following result.

######  Proposition 3 (Regularized logistic regression).

Consider the regularized logistic regression (15). Assume the step-size
$\eta<1/\lambda$ and the input data is bounded, i.e.
$R:=\max_{i}\|a_{i}\|<2\sqrt{\lambda}$. We have:

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log\left(n/b\right)}{\log(1/(1-\eta\lambda+\frac{1}{4}\eta
R^{2}))}.$ (16)

Next, we consider a non-convex formulation for logistic regression, with
$z_{i}=(a_{i},y_{i})$ and the loss

$\ell(w,z_{i}):=\rho\left(y_{i}-\langle
w,a_{i}\rangle\right)+\lambda_{r}\|w\|^{2}/2,$ (17)

where $\lambda_{r}>0$ is a regularization parameter and $\rho$ is a non-convex
function, where a standard choice is _Tukey’s bisquare loss_ defined as
$\rho_{\text{Tukey}}(t)=1-(1-(t/t_{0})^{2})^{3}$ for $|t|\leq t_{0}$, and
$\rho_{\text{Tukey}}(t)=1$ for $|t|\geq t_{0}$, and exponential squared loss:
$\rho_{\exp}(t)=1-e^{-|t|^{2}/t_{0}}$, where $t_{0}>0$ is a tuning parameter.

######  Proposition 4 (Non-convex formulation for logistic regression).

Consider the non-convex formulation for logistic regression (17). Assume the
step-size $\eta<\frac{1}{\lambda_{r}+R^{2}(2/t_{0})}$, where
$R=\max_{i}\|a_{i}\|<\sqrt{\lambda_{r}t_{0}/2}$. Then, we have the following
upper bound for the Hausdorff dimension:

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log\left(n/b\right)}{\log(1/(1-\eta\lambda_{r}+\eta
R^{2}\frac{2}{t_{0}}))}.$ (18)

One hidden-layer neural network. Given the data points $z_{i}=(a_{i},y_{i})$.
Let $a_{i}\in\mathbb{R}^{d}$ be the input and $y_{i}\in\mathbb{R}^{m}$ be the
corresponding output, and let $w_{r}\in\mathbb{R}^{d}$ be the weights of the
$r$-th hidden neuron of a one hidden-layer network, and $b_{r}\in\mathbb{R}$
is the output weight of hidden unit $r$. For simplicity of the presentation,
following [ZMG19, DZPS19], we only optimize the weights of the hidden layer,
i.e. $w=\begin{bmatrix}w_{1}^{T}w_{2}^{T}\dots w_{m}^{T}\end{bmatrix}$ is the
decision variable with the regularized squared loss:

$\ell(w,z_{i}):=\|y_{i}-\hat{y}_{i}\|^{2}+\lambda\|w\|^{2}/2,\quad\hat{y}_{i}:=\sum\limits_{r=1}^{m}b_{r}\sigma\left(w_{r}^{T}a_{i}\right),$
(19)

where the non-linearity $\sigma:\mathbb{R}\to\mathbb{R}$ is smooth and
$\lambda>0$ is a regularization parameter.

######  Proposition 5 (One hidden-layer network).

Consider the one hidden-layer network (19). Assume the step-size
$\eta<\frac{1}{2\lambda}$. Then, we have the following upper bound for the
Hausdorff dimension:

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log\left(n/b\right)}{\log(1/(1-\eta(\lambda-C)))},$
(20)

where
$C:=M_{y}\|b\|_{\infty}\|\sigma^{\prime\prime}\|R^{2}+\left(\max_{j}\|v_{j}\|_{\infty}\right)^{2}<\lambda$,
where $R:=\max_{i}\|a_{i}\|$, $M_{y}:=\max_{i}\|y_{i}-\hat{y}_{i}\|$, and
$v_{i}:=\left[b_{1}\sigma^{\prime}(w_{1}^{T}a_{i})a_{i}\,b_{2}\sigma^{\prime}(w_{2}^{T}a_{i})a_{i}\,\cdots\\\
b_{m}\sigma^{\prime}(w_{m}^{T}a_{i})a_{i}\right]^{T}$.

##  5 Experiments

Figure 3: Estimates of $R$ plotted against the generalization error
($|\mathrm{training\ loss}-\mathrm{test\ loss}|$) for VGG11 and FCNs trained
on CIFAR10, SVHN and BHP with varying $\eta,b$. The linear regression of best
fit is plotted in red, where shading corresponds to the $95\%$ confidence
interval. For all plots the one-sided p-value, testing whether the null
hypothesis that the slope of the line is in-fact negative and not positive, is
significantly less than $0.001$, indicating that it is highly likely that $R$
and the generalization error are positively correlated.

Our aim now is to empirically demonstrate that the bound in Corollary 1 is
informative, in that it is predictive of a neural network’s generalization
error. As the second term of this bound cannot be evaluated, we focus our
efforts on the first term. Further, because the denominator of the first term
is the only term that depends on the invariant measure, we want to establish
that the inverse of this denominator is predictive of a neural network’s
generalization error. Note however that for complex models, such as modern
neural networks, analytically bounding $\|J_{h_{i}(x)}\|$ becomes highly non-
trivial.

In our experiments, we fix the algorithm to SGD and we develop a numerical
method for computing the term (12). Noting that
$J_{h_{i}}(w)=I-\eta\nabla^{2}\tilde{\mathcal{R}}_{i}(w)$, for simplicity we
denote the inverse of (12) as the ‘complexity’:

$R=1/\left[\sum\limits_{i=1}^{m_{b}}p_{i}\int_{\mathbb{R}^{d}}\log\left(\|J_{h_{i}}(w)\|\right)\mathrm{d}\mu_{W|\mathbf{S}_{n}}(w)\right].$

To approximate the expectations, we propose the following simple Monte Carlo
strategy:

$\displaystyle
R^{-1}\approx\Bigl{[}1/(N_{W}N_{U})\Bigr{]}\sum\limits_{i=1}^{N_{W}}\sum\limits_{j=1}^{N_{U}}\log\left(\|J_{h_{U_{j}}}(W_{i})\|\right),$
(21)

where $U_{j}$ denotes i.i.d. random mini-batch indices that are drawn without-
replacement from $\\{1,\dots,n\\}$ and
$W_{i}\stackrel{{\scriptstyle\mathclap{\mbox{\tiny{i.i.d.}}}}}{{\sim}}\mu_{W|S}$.
Assuming (8) is ergodic [DF99], we treat the iterates $w_{k}$ as i.i.d.
samples from $\mu_{W|\mathbf{S}_{n}}$ for large $k$, hence,
$\log(\|J_{h_{U_{j}}}(W_{i})\|)$ can be computed on these iterates, and (21)
can be computed accordingly. Our implementation for computing
$\|J_{h_{U_{j}}}(W_{i})\|$ for neural networks with millions of parameters is
detailed in the Appendix. Though the size of $J_{h_{i}}$ is very large in our
experiments ($\approx 20\text{M}\times 20\text{M}$ on average), our algorithm
can efficiently compute the norms without constructing $J_{h_{U_{j}}}(W_{i})$,
by extending the approach presented in [YGKM20].

Figure 4: Estimated $R$ plotted against $\eta$ for 2 layer FCN trained on BHP.

In Figure 3 we plot the estimates of $R$ for a variety of convolutional (CONV)
and fully connected network (FCN) architectures trained on CIFAR10, SVHN and
Boston House Prices (BHP). For the full details of the models, the hardware
used, their run-time, and the convergence criterion used, see Section F in the
supplement. The plot demonstrates that $R$ and generalization error are
positively correlated and that this correlation is significant (p-value $\ll
0.001$) for all model architectures. This provides evidence that the bound on
the generalization error in Corollary 1 is informative.

To support our findings in Section 4 that the bound for the Hausdorff
dimension $\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$ is
monotonically decreasing in the step-size $\eta$, we plot $R$ against $\eta$
in Figure 4 for the networks trained on BHP in Figure 3. $R$ decreases with
increasing $\eta$, clearly backing our findings. We note that these results
were inconclusive for classification models trained with a cross-entropy loss,
in that we could not clearly observe a negative or positive correlation.
Future work will further study this lack of correlation, particular to
classification models.

##  6 Conclusion

In this work, we investigated stochastic optimization algorithms through the
lens of IFSs and studied their generalization properties. Under some
assumptions, we showed that the generalization error can be controlled based
on the Hausdorff dimension of the invariant measure determined by the
iterations, which can lead to tighter bounds than the standard bounds based on
the ambient dimension. We proposed an efficient methodology to estimate the
Hausdorff dimension in deep learning settings and supported our theory with
several experiments on neural networks. We also illustrated our bounds on
specific problems and algorithms such as SGD and its preconditioned variants,
which unveil new links between generalization, algorithm parameters and the
Hessian of the loss.

Our study does not have a direct societal impact as it is largely theoretical.
The limitation of our study is its asymptotic nature due to operating on
invariant measures. Future work will address obtaining nonasymptotic bounds in
terms of the number of iterations $k$.

## Acknowledgments

M.G.’s research is supported in part by the grants Office of Naval Research
Award Number N00014-21-1-2244, National Science Foundation (NSF) CCF-1814888,
NSF DMS-2053485, NSF DMS-1723085. U.Ş.’s research is supported by the French
government under management of Agence Nationale de la Recherche as part of the
“Investissements d’avenir program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA
Institute). L.Z. is grateful to the support from a Simons Foundation
Collaboration Grant and the grant NSF DMS-2053454 from the National Science
Foundation. A. C. was supported by an EPSRC Studentship.

## References

  * [AAV18] Amir Asadi, Emmanuel Abbe, and Sergio Verdú.  Chaining mutual information and tightening generalization bounds.  In Advances in Neural Information Processing Systems (NeurIPS), pages 7234–7243, 2018.
  * [AB09] Martin Anthony and Peter L Bartlett.  Neural Network Learning: Theoretical Foundations.  Cambridge University Press, 2009.
  * [AGNZ18] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang.  Stronger generalization bounds for deep nets via a compression approach.  In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 254–263. PMLR, 10–15 Jul 2018.
  * [AGZ21] Naman Agarwal, Surbhi Goel, and Cyril Zhang.  Acceleration via fractal learning rate schedules.  arXiv preprint arXiv:2103.01338, 2021.
  * [Anc16] Andreas Anckar.  Dimension bounds for invariant measures of bi-Lipschitz iterated function systems.  Journal of Mathematical Analysis and Applications, 440(2):853–864, 2016.
  * [BE02] Olivier Bousquet and André Elisseeff.  Stability and generalization.  Journal of Machine Learning Research, 2(Mar):499–526, 2002.
  * [Bog07] Vladimir I Bogachev.  Measure Theory, volume 1.  Springer, 2007.
  * [DDB20] Aymeric Dieuleveut, Alain Durmus, and Francis Bach.  Bridging the gap between constant step size stochastic gradient descent and Markov chains.  Annals of Statistics, 48(3):1348–1382, 2020.
  * [DF99] Persi Diaconis and David Freedman.  Iterated random functions.  SIAM Review, 41(1):45–76, 1999.
  * [DR17] Gintare Karolina Dziugaite and Daniel M Roy.  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 (UAI), 2017.
  * [DSD20] Nadav Dym, Barak Sober, and Ingrid Daubechies.  Expression of fractals through neural network functions.  IEEE Journal on Selected Areas in Information Theory, 1(1):57–66, 2020.
  * [DZPS19] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  In International Conference on Learning Representations, 2019.
  * [Elt90] John H Elton.  A multiplicative ergodic theorem for Lipschitz maps.  Stochastic Processes and their Applications, 34(1):39–47, 1990\.
  * [EM15] Murat A Erdogdu and Andrea Montanari.  Convergence rates of sub-sampled Newton methods.  Advances in Neural Information Processing Systems, 28:3052–3060, 2015.
  * [Fal97] Kenneth J. Falconer.  Techniques in Fractal Geometry.  Wiley, 1997.
  * [Fal04] Kenneth Falconer.  Fractal Geometry: Mathematical Foundations and Applications.  Wiley, 2004.
  * [FST06] Ai Hua Fan, Károly Simon, and Hajnal R. Tóth.  Contracting on average random IFS with repelling fixed point.  Journal of Statistical Physics, 122:169–193, 2006.
  * [FW09] De-Jun Feng and Yang Wang.  On the structures of generating iterated function systems of Cantor sets.  Advances in Mathematics, 222(6):1964–1981, 2009.
  * [GŞZ20] Mert Gürbüzbalaban, Umut Şimşekli, and Lingjiong Zhu.  The heavy-tail phenomenon in SGD.  arXiv e-prints, page arXiv:2006.04740, June 2020.
  * [Hau18] Felix Hausdorff.  Dimension und äusseres Mass.  Mathematische Annalen, 79(1-2):157–179, 1918.
  * [HJTW21] Daniel Hsu, Ziwei Ji, Matus Telgarsky, and Lan Wang.  Generalization bounds via distillation.  In International Conference on Learning Representations, 2021.
  * [HS74] Morris W. Hirsch and Stephen Smale.  Differential Equations, Dynamical Systems, and Linear Algebra.  Academic Press, 1974.
  * [HSS12] Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky.  Overview of mini-batch gradient descent.  Neural Networks for Machine Learning, 575, 2012.
  * [JR08] Joanna Jaroszewska and Michał Rams.  On the Hausdorff dimension of invariant measures of weakly contracting on average measurable IFS.  Journal of Statistical Physics, 132:907, 2008.
  * [KB15] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In International Conference on Learning Representations, 2015.
  * [Li17] Xi-Lin Li.  Preconditioned stochastic gradient descent.  IEEE Transactions on Neural Networks and Learning Systems, 29(5):1454–1466, 2017.
  * [LMA21] Zhiyuan Li, Sadhika Malladi, and Sanjeev Arora.  On the validity of modeling SGD with stochastic differential equations (SDEs).  arXiv preprint arXiv:2102.12470, 2021.
  * [LTE19] Qianxiao Li, Cheng Tai, and Weinan E.  Stochastic modified equations and dynamics of stochastic gradient algorithms i: Mathematical foundations.  Journal of Machine Learning Research, 20(40):1–47, 2019.
  * [MS02] Józef Myjak and Tomasz Szarek.  On Hausdorff dimension of invariant measures arising from non-contractive iterated function systems.  Annali di Matematica Pura ed Applicata, 181:223–237, 2002.
  * [MSS19] Eran Malach and Shai Shalev-Shwartz.  Is deeper better only when shallow is good?  In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
  * [MT10] John M Mackay and Jeremy T Tyson.  Conformal Dimension: Theory and Application, volume 54.  American Mathematical Society, 2010.
  * [NBMS17] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro.  Exploring generalization in deep learning.  In Advances in Neural Information Processing Systems (NIPS), pages 5947–5956, 2017.
  * [NSB02] Matthew Nicol, Nikita Sidorov, and David Broomhead.  On the fine structure of stationary measures in systems which contract-on-average.  Journal of Theoretical Probability, 15:715–730, 2002.
  * [Pes08] Yakov B Pesin.  Dimension Theory in Dynamical Systems: Contemporary Views and Applications.  University of Chicago Press, 2008.
  * [Qia99] Ning Qian.  On the momentum term in gradient descent learning algorithms.  Neural Networks, 12(1):145–151, 1999.
  * [Ram06] Michał Rams.  Dimension estimates for invariant measures of contracting-on-average iterated function systems.  arXiv preprint math/0606420, 2006.
  * [RKM16] Farbod Roosta-Khorasani and Michael W Mahoney.  Sub-sampled Newton methods II: Local convergence rates.  arXiv preprint arXiv:1601.04738, 2016.
  * [Rog98] Claude Ambrose Rogers.  Hausdorff Measures.  Cambridge University Press, 1998.
  * [SAM+20] Taiji Suzuki, Hiroshi Abe, Tomoya Murata, Shingo Horiuchi, Kotaro Ito, Tokuma Wachi, So Hirai, Masatoshi Yukishima, and Tomoaki Nishimura.  Spectral pruning: Compressing deep neural networks via spectral analysis and its generalization error.  In International Joint Conference on Artificial Intelligence, pages 2839–2846, 2020.
  * [SAN20] Taiji Suzuki, Hiroshi Abe, and Tomoaki Nishimura.  Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network.  In International Conference on Learning Representations, 2020.
  * [Saz00] Tomasz Sazarek.  The dimension of self-similar measures.  Bulletin of the Polish Academy of Sciences. Mathematics, 48:293–202, 2000.
  * [SHTY13] Mahito Sugiyama, Eiju Hirowatari, Hideki Tsuiki, and Akihiro Yamamoto.  Learning figures with the Hausdorff metric by fractals—towards computable binary classification.  Machine Learning, 90(1):91–126, 2013.
  * [SSBD14] Shai Shalev-Shwartz and Shai Ben-David.  Understanding Machine Learning: From Theory to Algorithms.  Cambridge University Press, 2014.
  * [ŞSDE20] Umut Şimşekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu.  Hausdorff dimension, heavy tails, and generalization in neural networks.  In Advances in Neural Information Processing Systems, volume 33, 2020.
  * [Wai19] Martin J. Wainwright.  High-Dimensional Statistics: A Non-Asymptotic Viewpoint, volume 48.  Cambridge University Press, 2019.
  * [XR17] Aolin Xu and Maxim Raginsky.  Information-theoretic analysis of generalization capability of learning algorithms.  In Advances in Neural Information Processing Systems (NeurIPS), pages 2524–2533, 2017.
  * [Yai19] Sho Yaida.  Fluctuation-dissipation relations for stochastic gradient descent.  In International Conference on Learning Representations, 2019.
  * [YBVE20] Lu Yu, Krishnakumar Balasubramanian, Stanislav Volgushev, and Murat A Erdogdu.  An analysis of constant step size SGD in the non-convex regime: Asymptotic normality and bias.  arXiv preprint arXiv:2006.07904, 2020.
  * [YGKM20] Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W. Mahoney.  PyHessian: Neural networks through the lens of the Hessian.  In 2020 IEEE International Conference on Big Data (Big Data), pages 581–590, 2020.
  * [ZBH+17] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  In International Conference on Learning Representations, 2017.
  * [ZMG19] Guodong Zhang, James Martens, and Roger Grosse.  Fast convergence of natural gradient descent for overparameterized neural networks.  In Advances in Neural Information Processing Systems, volume 32, 2019.

Appendix

The appendix is organized as follows:

  * •

Technical background for the proofs.

    * –

In Section A, we provide additional background on dimension theory. In
particular we define the Minkowski dimension and the local dimension for a
_measure_. Then, we provide three existing theoretical results that will be
used in our proofs.

  * •

Additional theoretical results.

    * –

In Section B, we provide an upper-bound on the Hausdorff dimension of the
invariant measure of SGD, when applied on support vector machines. This result
is a continuation of the results given in Section 4.

    * –

In Section C, we provide upper-bounds on the Hausdorff dimension of the
invariant measure of _preconditioned_ SGD on different problems.

    * –

In Section D, we provide an upper-bound on the Hausdorff dimension of the
invariant measure of the _stochastic Newton algorithm_ applied on linear
regression.

  * •

Details of the experimental results.

    * –

In Section E, we provide the details of the algorithm that we developed for
computing the operator norm $\|I-\eta\nabla^{2}\tilde{R}_{k}(w)\|$ for neural
networks.

    * –

In Section F, we provide the details of the SGD hyperparameters, network
architectures, and information regarding hardware/run-time.

  * •

Proofs.

    * –

In Section G, we provide the proofs all the theoretical results presented in
the main document and the Appendix.

##  A Further Background on Dimension Theory

###  A.1 Minkowski dimension of a measure

Based on the definition of the Minkowski dimension of sets as given in Section
2, we can define the Minkowski dimension of a finite Borel measure $\mu$, as
follows [Pes08]:

$\displaystyle\overline{\dim}_{\mathrm{M}}\mu:=$
$\displaystyle\lim_{\delta\rightarrow
0}\inf\left\\{\overline{\dim}_{\mathrm{M}}Z:\mu(Z)\geq 1-\delta\right\\}.$
(22)

Note that in general, we have

$\overline{\dim}_{\mathrm{M}}\mu\leq\inf\left\\{\overline{\dim}_{\mathrm{M}}Z:\mu(Z)=1\right\\},$

where the inequality can be strict, see [Pes08, Chapter 7].

###  A.2 Local dimensions of a measure

It is sometimes more convenient to consider a dimension notion that is defined
in a pointwise manner. Let $\mu$ be a finite Borel regular measure on
$\mathbb{R}^{d}$. The lower and upper local (or pointwise) dimensions of $\mu$
at $x\in\mathbb{R}^{d}$ are respectively defined as follows:

$\displaystyle\underline{\dim}_{\mathrm{loc}}\mu(x):=\liminf_{r\to
0}\frac{\log\mu(B(x,r))}{\log r},$ (23)
$\displaystyle\overline{\dim}_{\mathrm{loc}}\mu(x):=\limsup_{r\to
0}\frac{\log\mu(B(x,r))}{\log r},$ (24)

where $B(x,r)$ denotes the ball with radius $r$ about $x$. When the values of
these dimensions agree, the common value is called the local (or pointwise)
dimension of $\mu$ at $x$, and is denoted by $\dim_{\mathrm{loc}}\mu(x)$. The
local dimensions describe the power-law behavior of $\mu(B(x,r))$ for small
$r$ [Fal97]. These dimensions are closely linked to the Hausdorff dimension.

###  A.3 Existing Results

The following result upper-bounds the Hausdorff dimension of the invariant
measure of an IFS to the constituents of the IFS. We translate the result to
our notation.

######  Theorem 2.

[Ram06, Theorem 2.1] Consider the IFS (6) and assume that conditions (7) and
(8) are satisfied and $h_{i}$ are continuously differentiable with derivatives
$h^{\prime}_{i}$ that are $\alpha$-Hölder continuous for some $\alpha>0$. The
invariant measure $\mu_{W|\mathbf{S}_{n}}$ of the IFS satisfies

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq
s\quad\mbox{where}\quad
s:=\frac{\mathrm{Ent}}{\sum_{i=1}^{m_{b}}p_{i}\int_{x\in\mathbb{R}^{d}}\log(\|J_{h_{i}}(w)\|)\mathrm{d}\mu_{W|\mathbf{S}_{n}}(w)},$

where $\mathrm{Ent}:=\sum_{i=1}^{m_{b}}p_{i}\log(p_{i})$ is the (negative)
entropy. Furthermore, if $h_{i}$ are conformal and either SOSC or ROSC is
satisfied, then we have

$\dim_{\mathrm{H}}(\mu_{W|\mathbf{S}_{n}})=\underline{\dim}_{\mathrm{H}}(\mu_{W|\mathbf{S}_{n}})=s.$

The next two results link the Hausdorff and Minkowski dimensions of a measure
to its local dimension.

######  Proposition 6.

[Fal97, Propositions 10.3] For a finite Borel measure $\mu$, the following
identity holds:

$\displaystyle\overline{\dim}_{\mathrm{H}}\mu=$
$\displaystyle\inf\left\\{s:\underline{\dim}_{\mathrm{loc}}\mu(x)\leq s\text{
for }\mu\text{-almost all }x\right\\}.$ (25)

######  Theorem 3.

[Pes08, Theorem 7.1] Let $\mu$ be a finite Borel measure on $\mathbb{R}^{d}$.
If $\overline{\dim}_{\mathrm{loc}}\mu(x)\leq\alpha$ for $\mu$-almost every
$x$, then $\overline{\dim}_{\mathrm{M}}\mu\leq\alpha$.

The next theorem, called Egoroff’s theorem, will be used in our proofs
repeatedly. It provides a condition for measurable functions to be uniformly
continuous in an almost full-measure set.

######  Theorem 4 (Egoroff’s Theorem).

[Bog07, Theorem 2.2.1] Let $(X,\mathcal{A},\mu)$ be a space with a finite
nonnegative measure $\mu$ and let $\mu$-measurable functions $f_{n}$ be such
that $\mu$-almost everywhere there is a finite limit
$f(x):=\lim_{n\rightarrow\infty}f_{n}(x)$. Then, for every $\varepsilon>0$,
there exists a set $X_{\varepsilon}\in\mathcal{A}$ such that
$\mu\left(X\backslash X_{\varepsilon}\right)<\varepsilon$ and the functions
$f_{n}$ converge to $f$ uniformly on $X_{\varepsilon}$.

##  B Additional Analytical Estimates for SGD

Support vector machines. Given the data points $z_{i}=(a_{i},y_{i})$ with the
input data $a_{i}$ and the output $y_{i}\in\\{-1,1\\}$, consider support
vector machines with smooth hinge loss:

$\ell(w,z_{i}):=\ell_{\sigma}(y_{i}a_{i}^{T}w)+\lambda\|w\|^{2}/2,$ (26)

where $\sigma>0$ is a smoothing parameter, $\lambda>0$ is the regularization
parameter and $\ell_{\sigma}(z):=1-z+\sigma\log(1+e^{-\frac{1-z}{\sigma}})$.
This loss function is a smooth version of the hinge loss that can be easier to
optimize in some settings. In fact, it can be shown that as $\sigma\to 0$,
this loss converges to the (non-smooth) hinge loss pointwise.

######  Proposition 7 (Support vector machines).

Consider the support vector machines (26). Assume the step-size
$\eta<\frac{1}{\lambda+\|R\|^{2}/(4\rho)}$, where $R:=\max_{i}\|a_{i}\|$ is
finite. Then, we have:

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log\left(n/b\right)}{\log(1/(1-\eta\lambda))}.$
(27)

##  C Analytical Estimates for Preconditioned SGD

We consider the pre-conditioned SGD methods

$\displaystyle w_{k}=w_{k-1}-\eta H^{-1}\nabla\tilde{R}_{k}(w_{k-1}),$ (28)

for a fixed square matrix $H$. Some choices of $H$ includes a diagonal matrix,
a block diagonal matrix or the Fisher-information matrix (see e.g. [ZMG19]).
We assume that $H$ is a positive definite matrix, and by Cholesky
decomposition, we can write $H=SS^{T}$, where $S$ is a real lower triangular
matrix with positive diagonal entries. If we have $H=JJ^{T}$, where $J$ is the
Jacobian, then the corresponding least square problems is called the Gauss-
Newton methods for least squares. Assume that $H$ there exist some $m,M>0$
such that:

$0\prec mI\preceq H\preceq MI.$ (29)

As illustrative examples; in the following, we will consider the setting where
we divide $\mathbf{S}_{n}$ into $m_{b}=n/b$ batches with each batch having $b$
elements, and then we discuss how analytical estimates on the (upper)
Hausdorff dimension $\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$ can
be obtained for some particular problems including least squares, regularized
logistic regression, support vector machines, and one hidden-layer network.

Least squares.  We consider the least square problem with data points
$z_{i}=(a_{i},y_{i})$ and the loss

$\ell(w,z_{i}):=\frac{1}{2}\left(a_{i}^{T}w-y_{i}\right)^{2}+\frac{\lambda}{2}\|w\|^{2},$
(30)

where $\lambda>0$ is a regularization parameter. If we apply preconditioned
SGD this results in the recursion (6) with

$\displaystyle h_{i}(w)=M_{i}w+q_{i}\quad\text{ with}\quad
M_{i}:=I-\eta\lambda H^{-1}-\eta H^{-1}H_{i},$ (31)
$\displaystyle{H}_{i}:=\frac{1}{b}\sum\limits_{j\in S_{i}}a_{j}a_{j}^{T},\quad
q_{i}:=\frac{\eta}{b}H^{-1}\sum\limits_{j\in S_{i}}a_{j}y_{j}\,,$

where $a_{j}\in\mathbb{R}^{d}$ are the input vectors, and $y_{j}$ are the
output variables, and $\\{S_{i}\\}_{i=1}^{m_{b}}$ is a partition of
$\\{1,2,\dots,n\\}$ with $|S_{i}|=b$, where $i=1,2,\ldots,m_{b}$ with
$m_{b}=n/b$. We have the following result.

######  Proposition 8 (Least squares).

Consider the pre-conditioned SGD method (28) for the least square problem
(30). Assume that the step-size $\eta<\frac{m}{R^{2}+\lambda}$, where
$R:=\max_{i}\|a_{i}\|$ is finite. Then, we have the following upper bound for
the Hausdorff dimension:

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log\left(n/b\right)}{\log(1/(1-\eta
M^{-1}\lambda))}.$ (32)

Regularized logistic regression.  We consider the regularized logistic
regression problem with the data points $z_{i}=(a_{i},y_{i})$ and the loss:

$\ell(w,z_{i}):=\log\left(1+\exp\left(-y_{i}a_{i}^{T}w\right)\right)+\frac{\lambda}{2}\|w\|^{2},$
(33)

where $\lambda>0$ is the regularization parameter.

######  Proposition 9 (Regularized logistic regression).

Consider the pre-conditioned SGD method (28) for regularized logistic
regression (33). Assume that the step-size $\eta<m/\lambda$ and
$R:=\max_{i}\|a_{i}\|<2\sqrt{m\lambda/M}$. Then, we have the following upper
bound for the Hausdorff dimension:

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log\left(n/b\right)}{\log(1/(1-\eta
M^{-1}\lambda+\frac{1}{4}\eta m^{-1}R^{2}))}.$ (34)

Next, we consider a non-convex formulation for logistic regression. Consider
the data points $z_{i}=(a_{i},y_{i})$ and the loss:

$\ell(w,z_{i}):=\rho\left(y_{i}-\langle
w,a_{i}\rangle\right)+\frac{\lambda_{r}}{2}\|w\|^{2},$ (35)

where $\lambda_{r}>0$ is a regularization parameter and $\rho$ is a non-convex
function. We have the following result.

######  Proposition 10 (Non-convex formulation for logistic regression).

Consider the pre-conditioned SGD method (28) in the non-convex logistic
regression setting (35). Assume that the step-size
$\eta<\frac{m}{\lambda_{r}+R^{2}(2/t_{0})}$ and
$R:=\max_{i}\|a_{i}\|<\sqrt{\lambda_{r}t_{0}m/(2M)}$. Then, we have the
following upper bound for the Hausdorff dimension:

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log\left(n/b\right)}{\log(1/(1-\eta
M^{-1}\lambda_{r}+\eta m^{-1}R^{2}\frac{2}{t_{0}}))}.$ (36)

Support vector machines.  We have the following result for pre-conditioned SGD
when applied to the support vector machines problem (26).

######  Proposition 11 (Support vector machines).

Consider pre-conditioned SGD (28) for support vector machines (26). Assume
that the step-size $\eta<\frac{m}{\lambda+\|R\|^{2}/(4\rho)}$ where
$R:=\max_{i}\|a_{i}\|$ is finite. Then, we have the following upper bound for
the Hausdorff dimension:

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log\left(n/b\right)}{\log(1/(1-\eta
M^{-1}\lambda))}.$ (37)

One hidden-layered neural network.  Consider the one-hidden-layer neural
network setting as in Proposition 5, where the objective is to minimize the
regularized squared loss with the loss function:

$\ell(w,z_{i}):=\|y_{i}-\hat{y}_{i}\|^{2}+\frac{\lambda}{2}\|w\|^{2},\quad\hat{y}_{i}:=\sum_{r=1}^{m}b_{r}\sigma\left(w_{r}^{T}a_{i}\right),$
(38)

where the non-linearity $\sigma:\mathbb{R}\to\mathbb{R}$ is smooth and
$\lambda>0$ is the regularization parameter.

######  Proposition 12 (One hidden-layer network).

Consider the one-hidden-layer network (38). Assume that
$\eta<\frac{m}{C+\lambda}$ and $\lambda>\frac{M}{m}C$, where $C$ is defined in
Corollary 5. Then, we have the following upper bound for the Hausdorff
dimension:

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log\left(n/b\right)}{\log(1/(1-\eta(M^{-1}\lambda-m^{-1}C)))}.$
(39)

##  D Analytical Estimates for Stochastic Newton

We consider the stochastic Newton method

$\displaystyle w_{k}=w_{k-1}-\eta[\tilde{H}_{k}(w_{k-1})]^{-1}\nabla
R_{k}(w_{k-1}),\quad\mbox{where}\quad\tilde{H}_{k}(w):=(1/b)\sum\limits_{i\in\Omega_{k}}\nabla^{2}\ell(w,z_{i}),$

see e.g. [RKM16], where $\Omega_{k}=S_{i}$ with probability $p_{i}$ with
$i=1,2,\ldots,m_{b}$, where $m_{b}=n/b$.

For simplicity, we focus on the least square problem, with the data points
$z_{i}=(a_{i},y_{i})$ and the loss:

$\ell(w,z_{i}):=\frac{1}{2}\left(a_{i}^{T}w-y_{i}\right)^{2}+\frac{\lambda}{2}\|w\|^{2},$
(40)

where $\lambda>0$ is a regularization parameter. If we apply stochastic Newton
this results in the recursion (6) with

$\displaystyle h_{i}(w)=M_{i}w+q_{i}\quad\text{ with}\quad M_{i}:=(1-\eta)I,$
(41) $\displaystyle\tilde{H}_{i}:=\frac{1}{b}\sum\limits_{j\in
S_{i}}a_{j}a_{j}^{T}+\lambda I,\quad
q_{i}:=\frac{\eta}{b}\tilde{H}_{i}^{-1}\sum\limits_{j\in S_{i}}a_{j}y_{j}\,,$

where $a_{j}\in\mathbb{R}^{d}$ are the input vector, and $y_{j}$ are the
output variable, and $\\{S_{i}\\}_{i=1}^{m_{b}}$ is a partition of
$\\{1,2,\dots,n\\}$ with $|S_{i}|=b$, where $i=1,2,\ldots,m_{b}$ with
$m_{b}=n/b$. Therefore, $J_{h_{i}}(w)=(1-\eta)I$. By following the similar
argument as in the proof of Proposition 8, we conclude that for any
$\eta\in(0,1)$,

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log\left(n/b\right)}{\log(1/(1-\eta))},$
(42)

where the upper bound is decreasing in step-size $\eta$ and batch-size $b$.

##  E Estimating the Complexity $R$ for SGD

Estimating $R$, as detailed in Equation (21), requires drawing $N_{W}$ samples
from the invariant measure and $N_{U}$ batches of from the training data. As
mentioned in the main text, to approximate the summation over $N_{W}$ samples
from the invariant measure, assuming (8) is ergodic [DF99], we treat the
iterates $w_{k}$ as i.i.d. samples from $\mu_{W|S}$ for large $k$, hence, the
norm of the Jacobian $\log(\|J_{h_{I_{j}}}(W_{i})\|)$ can be efficiently
computed on these iterates. Thus, we first we train a neural-network to
convergence, whereby convergence is defined as the model reaching some
accuracy level (if the dataset is a classification task) and achieving a loss
below some threshold on training data. We assume that after convergence the
SGD iterates will be drawn from the invariant measure. As such we run the
training algorithm for another 200 iterates, saving a snapshot of the model
parameters at each step, such that $N_{W}=200$ in Equation (21). For each of
these snapshots we estimate the spectral norm $\|J_{h_{I}}(W)\|$ using a
simple modification of the power iteration algorithm of [YGKM20], detailed in
Section E.1 below. This modified algorithm is scalable to neural networks with
millions of parameters and we apply it to 50 of the batches used during
training, such that $N_{U}=50$ in (21).

###  E.1 Power Iteration Algorithm for $\|J_{h_{i}}(w)\|$

We re-purpose the power iteration algorithm of [YGKM20] adding a small
modification that allows for the estimation of the spectral norm
$\|J_{h_{i}}(w)\|$. We first note that

$J_{h_{i}}(w)=I-\eta\nabla^{2}\tilde{\mathcal{R}}_{i}(w)$ (43)

where $\nabla^{2}\tilde{\mathcal{R}}_{i}(w)$ is the Hessian for the $i^{th}$
batch. As such our power iteration algorithm needs to estimate the operator
norm of the matrix $I-\eta\nabla^{2}\tilde{\mathcal{R}}_{i}(w)$ and not just
that of the Hessian of the network. To do this we just need to change the
‘vector-product’ step of the power-iteration algorithm of [YGKM20]. Our
modified method has the same convergence guarantees, namely that the method
will converge to the ‘true’ top eigenvalue if this eigenvalue is ‘dominant’,
in that it dominates all other eigenvalues in absolute value, i.e if
$\lambda_{1}$ is the top eigenvalue then we must have that:

$|\lambda_{1}|>|\lambda_{2}|\geq\dots|\lambda_{n}|$

to guarantee convergence.

Input: Network Parameters: $w$, Loss function: $f$, Learning rate: $\eta$

1 Compute the gradient of $\theta$ by backpropagation, i.e., compute
$g_{w}=\frac{df}{dw}$.

2Draw a random vector $v$ from $N(0,1)$ (same dimension as $w$).

3Normalize $v$, $v=\frac{v}{\|v\|_{2}}$

4for  _i $=1,2,\ldots$_ do // Power Iteration

Compute $gv=g_{\theta}^{T}v$

// Inner product

5

Compute $Hv$ by backpropagation, $Hv=\frac{d(gv)}{dw}$

// Get Hessian vector product

Compute $J_{h_{i}}v$, $J_{h_{i}}v=(I-\eta H)v=v-\eta Hv$

// Get $J_{h_{i}}$ vector product

6 Normalize and reset $v$, $v=\frac{J_{h_{i}}v}{\|J_{h_{i}}v\|_{2}}$

7 end for

Algorithm 1 Power Iteration for Top Eigenvalue Computation of $J_{h_{i}}(w)$

##  F Experiment Hyperparameters

#### Training Parameters:

All models in Figures 3 and 4 were trained using SGD with batch sizes of $50$
or $100$ and were considered to have converged for CIFAR10 and SVHN if they
reached $100\%$ accuracy and less than $0.0005$ loss on the training set. For
BHP convergence was considered to have been achieved after $100000$ training
steps. For all models except VGG16 in Figures 3 and 4 we use learning rates in

$\displaystyle\big{\\{}0.0075,0.02,0.025,0.03,0.04,0.06,0.07,0.075,0.08,0.09,0.1,0.11,0.12,$
$\displaystyle
0.13,0.14,0.15,0.16,0.17,0.18,0.19,0.194,0.2,0.22,0.24,0.25,0.26\big{\\}}.$

VGG16 models were trained with learning rates in
$\\{0.0075,0.02,0.03,0.06,0.07,0.08\\}$.

#### Network Architectures:

BHP FCN had 2 hidden layers and were 10 neurons wide. Similarly CIFAR10 FCN
were 5 and 7 layers deep with 2048 neurons per layer. 9-layer CONV networks
were VGG11 networks with the final 2 layers removed. 16-layer CONV networks
were simply the standard implementation of VGG16 networks.

#### Run-time:

The full battery of fully connected models split over two GeForce GTX 1080
GPUs took two days to train to convergence and the subsequent power iterations
took less than a day. Similarly the full gamut of VGG11 models took a day to
train to convergence over four GeForce GTX 1080 GPUs and the subsequent power
iterations took less than a day to converge. The VGG16 models took a day to
train over four GeForce GTX 1080 GPUs but the power iterations for each model
took roughly 24 hours on a single GeForce GTX 1080 GPU.

##  G Postponed Proofs

###  G.1 Proof of Proposition 1

###### Proof.

Denote $\alpha:=\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$. By
Assumption H 1, we have

$\underline{\dim}_{\mathrm{loc}}\mu_{W|\mathbf{S}_{n}}(w)=\overline{\dim}_{\mathrm{loc}}\mu_{W|\mathbf{S}_{n}}(w),$

for $\mu_{W|\mathbf{S}_{n}}$-a.e. $w$, and by Proposition 6 we have

$\displaystyle\overline{\dim}_{\mathrm{loc}}\mu_{W|\mathbf{S}_{n}}(w)\leq\alpha+\epsilon,$
(44)

for all $\epsilon>0$ and for $\mu_{W|\mathbf{S}_{n}}$-a.e. $w$. By invoking
Theorem 3, we obtain

$\displaystyle\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}}\leq\alpha+\epsilon.$
(45)

Since this holds for any $\epsilon$,
$\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}}\leq\alpha$.

By definition, we have for almost all $\mathbf{S}_{n}$:

$\displaystyle\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}}=\lim_{\delta\rightarrow
0}\inf\left\\{\overline{\dim}_{\mathrm{M}}A:\mu_{W|\mathbf{S}_{n}}(A)\geq
1-\delta\right\\}.$ (46)

Hence, given a sequence $(\delta_{k})_{k\geq 1}$ such that
$\delta_{k}\downarrow 0$, and $\mathbf{S}_{n}$, and any $\epsilon>0$, there is
a $k_{0}=k_{0}(\epsilon)$ such that $k\geq k_{0}$ implies

$\displaystyle\inf\left\\{\overline{\dim}_{\mathrm{M}}A:\mu_{W|\mathbf{S}_{n}}(A)\geq
1-\delta_{k}\right\\}\leq$
$\displaystyle\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}}+\epsilon$
(47) $\displaystyle\leq$ $\displaystyle\alpha+\epsilon.$ (48)

Hence, for any $\epsilon_{1}>0$ and $k\geq k_{0}$, we can find a bounded Borel
set $A_{\mathbf{S}_{n},k}$, such that
$\mu_{W|\mathbf{S}_{n}}(A_{\mathbf{S}_{n},k})\geq 1-\delta_{k}$, and

$\displaystyle\overline{\dim}_{\mathrm{M}}A_{\mathbf{S}_{n},k}\leq\alpha+\epsilon+\epsilon_{1}.$
(49)

Note that the boundedness of $A_{\mathbf{S}_{n},k}$ follows from the fact that
its upper-Minkowski dimension is finite. By choosing
$\epsilon=\epsilon_{1}=\frac{\varepsilon}{2}$, it yields the desired result.
This completes the proof. ∎

###  G.2 Proof of Theorem 1

###### Proof.

We begin similarly to the proof of Proposition 1.

Denote

$\alpha(\mathbf{S},n):=\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}.$

By Assumption H 1, we have
$\underline{\dim}_{\mathrm{loc}}\mu_{W|\mathbf{S}_{n}}(w)=\overline{\dim}_{\mathrm{loc}}\mu_{W|\mathbf{S}_{n}}(w)$
for $\mu_{W|\mathbf{S}_{n}}$-almost every $w$, and by Proposition 6 we have

$\displaystyle\overline{\dim}_{\mathrm{loc}}\mu_{W|\mathbf{S}_{n}}(w)\leq\alpha(\mathbf{S},n)+\epsilon,$
(50)

for all $\epsilon>0$ and for $\mu_{W|\mathbf{S}_{n}}$-a.e. $w$. By invoking
Theorem 3, we obtain

$\displaystyle\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}}\leq\alpha(\mathbf{S},n)+\epsilon.$
(51)

Since this holds for any $\epsilon>0$,
$\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}}\leq\alpha(\mathbf{S},n)$.

By definition, we have for all $\mathbf{S}$ and $n$:

$\displaystyle\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}}=\lim_{\delta\to
0}\inf\left\\{\overline{\dim}_{\mathrm{M}}A:\mu_{W|\mathbf{S}_{n}}(A)\geq
1-\delta\right\\}.$ (52)

Hence, for each $n$, there exists a set $\Omega_{n}$ of full measure such that

$\displaystyle
f^{n}_{\delta}(\mathbf{S}):=\inf\left\\{\overline{\dim}_{\mathrm{M}}A:\mu_{W|\mathbf{S}_{n}}(A)\geq
1-\delta\right\\}\to\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}},$ (53)

for all $\mathbf{S}\in\Omega_{n}$. Let $\Omega^{\ast}:=\cap_{n}\Omega_{n}$.
Then for $\mathbf{S}\in\Omega^{\ast}$ we have that for all $n$

$\displaystyle
f^{n}_{\delta}(\mathbf{S})\to\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}},$
(54)

and therefore, on this set we also have

$\sup_{n}\frac{1}{\xi_{n}}\min\left\\{1,\left|f^{n}_{\delta}(\mathbf{S})-\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}}\right|\right\\}\to
0,$

where $\xi_{n}$ is a monotone increasing sequence such that $\xi_{n}\geq 1$
and $\xi_{n}\to\infty$.

By applying Theorem 4 to the collection of random variables:

$\displaystyle
F_{\delta}(\mathbf{S}):=\sup_{n}\frac{1}{\xi_{n}}\min\left\\{1,\left|f^{n}_{\delta}(\mathbf{S})-\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}}\right|\right\\},$
(55)

for any $\zeta>0$, we can find a subset
$\mathfrak{Z}\subset\mathcal{Z}^{\infty}$, with probability at least $1-\zeta$
under $\pi^{\infty}$, such that on $\mathfrak{Z}$ the convergence is uniform,
that is

$\displaystyle\sup_{\mathbf{S}\in\mathfrak{Z}}\sup_{n}\frac{1}{\xi_{n}}\min\left\\{1,\left|f^{n}_{\delta}(\mathbf{S})-\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}}\right|\right\\}\leq
c(\delta),$ (56)

where for any $\zeta$, $c(\delta):=c(\delta;\zeta)\to 0$ as $\delta\to 0$.

Hence, for any $\delta$, $\mathbf{S}\in\mathfrak{Z}$, and $n$, we have

$\displaystyle f^{n}_{\delta}(\mathbf{S})\leq$
$\displaystyle\overline{\dim}_{\mathrm{M}}\mu_{W|\mathbf{S}_{n}}+\xi_{n}c(\delta)$
(57) $\displaystyle\leq$ $\displaystyle\alpha(\mathbf{S},n)+\xi_{n}c(\delta).$
(58)

Consider a sequence $(\delta_{k})_{k\geq 1}$ such that $\delta_{k}\downarrow
0$. Then, for any $\mathbf{S}\in\mathfrak{Z}$ and $\epsilon>0$, we can find a
bounded Borel set $A_{\mathbf{S}_{n},k}$, such that
$\mu_{W|\mathbf{S}_{n}}(A_{\mathbf{S}_{n},k})\geq 1-\delta_{k}$, and

$\displaystyle\overline{\dim}_{\mathrm{M}}A_{\mathbf{S}_{n},k}\leq\alpha(\mathbf{S},n)+\xi_{n}c(\delta_{k})+\epsilon.$
(59)

Define the set

$\displaystyle\mathcal{W}_{n,\delta_{k}}:=\bigcup_{\mathbf{S}\in\mathcal{Z}^{\infty}}A_{\mathbf{S}_{n},k}.$
(60)

By using
$\mathcal{G}(w):=|\mathcal{R}(w)-\hat{\mathcal{R}}(w,\mathbf{S}_{n})|$, under
the joint distribution of $(W,\mathbf{S}_{n})$, such that
$\mathbf{S}\sim\pi^{\infty}$ and $W\sim\mu_{W|\mathbf{S}_{n}}$, we have:

$\displaystyle\mathbb{P}\left(\mathcal{G}(W)>\varepsilon\right)\leq$
$\displaystyle\zeta+\mathbb{P}\left(\\{\mathcal{G}(W)>\varepsilon\\}\cap\\{\mathbf{S}\in\mathfrak{Z}\\}\right)$
(61) $\displaystyle\leq$
$\displaystyle\zeta+\delta_{k}+\mathbb{P}\left(\\{\mathcal{G}(W)>\varepsilon\\}\cap\\{W\in
A_{\mathbf{S}_{n},k}\\}\cap\\{\mathbf{S}\in\mathfrak{Z}\\}\right)$ (62)
$\displaystyle\leq$
$\displaystyle\zeta+\delta_{k}+\mathbb{P}\left(\left\\{\sup_{w\in
A_{\mathbf{S}_{n},k}}\mathcal{G}(w)>\varepsilon\right\\}\cap\\{\mathbf{S}\in\mathfrak{Z}\\}\right).$
(63)

Now, let us focus on the last term of the above equation.

First we observe that as $\ell$ is $L$-Lipschitz, so are $\mathcal{R}$ and
$\hat{\mathcal{R}}$. Hence, by considering the particular forms of the
$\beta$-covers in H 2, for any $w^{\prime}\in\mathbb{R}^{d}$ we have:

$\displaystyle\mathcal{G}(w)\leq\mathcal{G}(w^{\prime})+2L\left\|w-w^{\prime}\right\|,$
(64)

which implies

$\displaystyle\sup_{w\in A_{\mathbf{S}_{n},k}}\mathcal{G}(w)\leq\max_{w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})}\mathcal{G}(w)+2L\beta_{n}.$ (65)

Now, notice that the $\beta$-covers of H 2 still yield the same Minkowski
dimension in (5) [ŞSDE20]. Then by definition, we have for all $\mathbf{S}$
and $n$:

$\displaystyle\limsup_{\beta\to
0}\frac{\log|N_{\beta}(A_{\mathbf{S}_{n},k})|}{\log(1/\beta)}=\lim_{\beta\to
0}\sup_{r<\beta}\frac{\log|N_{r}(A_{\mathbf{S}_{n},k})|}{\log(1/r)}=\overline{\dim}_{\mathrm{M}}A_{\mathbf{S}_{n},k}:=d_{\mathrm{M}}(\mathbf{S},n,k).$
(66)

Hence for each $n$

$\displaystyle g^{n,k}_{\beta}(\mathbf{S}):=\sup_{\mathbb{Q}\ni
r<\delta}\frac{\log|N_{r}(A_{\mathbf{S}_{n},k})|}{\log(1/r)}\to
d_{\mathrm{M}}(\mathbf{S},n,k),$ (67)

almost surely. By using the same reasoning in (53), we have, for each $n$,
there exists a set $\Omega^{\prime}_{n}$ of full measure such that

$\displaystyle g^{n,k}_{\beta}(\mathbf{S})=\sup_{\mathbb{Q}\ni
r<\beta}\frac{\log|N_{r}(A_{\mathbf{S}_{n},k})|}{\log(1/r)}\to
d_{\mathrm{M}}(\mathbf{S},n,k),$ (68)

for all $\mathbf{S}\in\Omega^{\prime}_{n}$. Define
$\Omega^{\ast\ast}:=(\cap_{n}\Omega^{\prime}_{n})\cap\Omega^{\ast}$. Hence, on
$\Omega^{\ast\ast}$ we have:

$\displaystyle
G^{k}_{\beta}(\mathbf{S}):=\sup_{n}\frac{1}{\xi_{n}}\min\left\\{1,\left|g^{n,k}_{\beta}(\mathbf{S})-d_{\mathrm{M}}(\mathbf{S},n,k)\right|\right\\}\to
0,$ (69)

By applying Theorem 4 to the collection
$\\{G^{k}_{\beta}(\mathbf{S})\\}_{\beta}$, for any $\zeta_{1}>0$ we can find a
subset $\mathfrak{Z}_{1}\subset\mathcal{Z}^{\infty}$, with probability at
least $1-\zeta_{1}$ under $\pi^{\infty}$, such that on $\mathfrak{Z}_{1}$ the
convergence is uniform, that is

$\displaystyle\sup_{\mathbf{S}\in\mathfrak{Z}_{1}}\sup_{n}\frac{1}{\xi_{n}}\min\\{1,|g^{n,k}_{\beta}(\mathbf{S})-d_{\mathrm{M}}(\mathbf{S},n,k)|\\}\leq
c^{\prime}(\beta),$ (70)

where for any $\zeta_{1}$,
$c^{\prime}(\beta):=c^{\prime}(\beta;\zeta_{1},\delta_{k})\to 0$ as $\beta\to
0$.

Hence, denoting $\mathfrak{Z}^{\ast}:=\mathfrak{Z}\cap\mathfrak{Z}_{1}$ by
using (59) we have:

$\displaystyle\\{\mathbf{S}\in\mathfrak{Z}^{\ast}\\}\subseteq\bigcap_{n}\left\\{\left|N_{\beta}\left(A_{\mathbf{S}_{n},k}\right)\right|\leq\left(\frac{1}{\beta}\right)^{\alpha(\mathbf{S},n)+\xi_{n}c(\delta_{k})+\xi_{n}c^{\prime}(\beta)+\epsilon}\right\\}.$

Let $(\beta_{n})_{n\geq 0}$ be a decreasing sequence such that
$\beta_{n}\in\mathbb{Q}$ for all $n$ and $\beta_{n}\to 0$. We then have

$\displaystyle\mathbb{P}\Biggl{(}\\{\mathbf{S}\in\mathfrak{Z}\\}\cap$
$\displaystyle\left\\{\max_{w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})}\mathcal{G}_{n}(w)\geq\varepsilon\right\\}\Biggr{)}$
$\displaystyle\leq\mathbb{P}\Biggl{(}\\{\mathbf{S}\in\mathfrak{Z}^{\ast}\\}\cap\Big{\\{}\max_{w\in
N_{\beta_{n}}(A_{\textbf{S}_{n},k})}\mathcal{G}_{n}(w)\geq\varepsilon\Big{\\}}\Biggr{)}+\zeta_{2}.$

For $\rho>0$ and $m\in\mathbb{N}_{+}$ let us define the interval
$J_{m}(\rho):=(m\rho,(m+1)\rho]$. Furthermore, for any $t>0$ define

$\displaystyle\varepsilon(t):=\sqrt{\frac{2\nu^{2}}{n}\Big{[}\log(1/\beta_{n})\left(t+\xi_{n}c(\delta_{k})+\xi_{n}c^{\prime}(\beta_{n})+\epsilon\right)+\log(M/\zeta_{2})\Big{]}}.$
(71)

For notational simplicity, denote
$N_{\beta_{n},k}:=N_{\beta_{n}}(\mathcal{W}_{n,\delta_{k}})$ and

$\displaystyle\tilde{\alpha}(\mathbf{S},n,k,\epsilon):=\alpha(\mathbf{S},n)+\xi_{n}c(\delta_{k})+\xi_{n}c^{\prime}(\beta_{n})+\epsilon.$
(72)

Let $d^{\ast}$ be the smallest real number such that $\alpha(\mathbf{S},n)\leq
d^{\ast}$ almost surely222Notice that we trivially have $d^{\ast}\leq d$; yet,
$d^{\ast}$ can be much smaller than $d$., we therefore have:

$\displaystyle\mathbb{P}\Biggl{(}\\{\mathbf{S}\in\mathfrak{Z}\\}\cap\left\\{\max_{w\in
N_{\beta_{n}}(A_{\textbf{S}_{n},k})}\mathcal{G}_{n}(w)\geq\varepsilon(\alpha(\mathbf{S},n))\right\\}\Biggr{)}$
$\displaystyle\leq\zeta_{2}+\mathbb{P}\Biggl{(}\left\\{\left|N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\right|\leq\left(\frac{1}{\beta_{n}}\right)^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\right\\}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\cap\Big{\\{}\max_{w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n}},k)}|\hat{\mathcal{R}}_{n}(w)-\mathcal{R}(w)|\geq\varepsilon(\alpha(\mathbf{S},n))\Big{\\}}\Biggr{)}$
$\displaystyle=\zeta_{2}+\sum_{m=0}^{\lceil\frac{d^{\ast}}{\rho}\rceil}\mathbb{P}\Biggl{(}\left\\{\left|N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\right|\leq\left(\frac{1}{\beta_{n}}\right)^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\right\\}$
$\displaystyle\qquad\qquad\qquad\qquad\cap\Big{\\{}\max_{w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})}\mathcal{G}_{n}(w)\geq\varepsilon(\alpha(\mathbf{S},n))\Big{\\}}\cap\left\\{\alpha(\mathbf{S},n)\in
J_{m}(\rho)\right\\}\Biggr{)}$
$\displaystyle=\zeta_{2}+\sum_{m=0}^{\lceil\frac{d^{\ast}}{\rho}\rceil}\mathbb{P}\Biggl{(}\left\\{\left|N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\right|\leq\left(\frac{1}{\beta_{n}}\right)^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\right\\}\cap\left\\{\alpha(\mathbf{S},n)\in
J_{m}(\rho)\right\\}$ $\displaystyle\qquad\qquad\qquad\cap\bigcup_{w\in
N(\beta_{n})}\bigg{(}\left\\{w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\right\\}\cap\left\\{\mathcal{G}_{n}(w)\geq\varepsilon(\alpha(\mathbf{S},n))\right\\}\bigg{)}\Biggr{)}$
$\displaystyle\leq\zeta_{2}+\sum_{m=0}^{\lceil\frac{d^{\ast}}{\rho}\rceil}\sum_{w\in
N_{\beta_{n},k}}\mathbb{P}\Bigg{(}\Big{\\{}\mathcal{G}_{n}(w)\geq\varepsilon(m\rho)\Big{\\}}$
$\displaystyle\qquad\cap\Big{\\{}w\in
N_{\delta_{n}}(A_{\mathbf{S}_{n},k})\Big{\\}}\cap\left\\{\left|N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\right|\leq\left(\frac{1}{\beta_{n}}\right)^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\right\\}\cap\left\\{\alpha(\mathbf{S},n)\in
J_{m}(\rho)\right\\}\Bigg{)},$

where we used the fact that on the event $\alpha(\mathbf{S},n)\in
J_{m}(\rho)$, $\varepsilon(\alpha(\mathbf{S},n))\geq\varepsilon(m\rho)$.

Notice that the events

$\Big{\\{}w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\Big{\\}},\left\\{|N_{\beta_{n}}(A_{\mathbf{S}_{n},k})|\leq(1/\beta_{n})^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\right\\},\left\\{\alpha(\mathbf{S},n)\in
J_{m}(\rho)\right\\}$

are in $\mathfrak{G}$.

On the other hand, the event $\\{\mathcal{G}_{n}(w)\geq\varepsilon(m\rho)\\}$
is clearly in $\mathfrak{F}$ (see H 2 for definitions).

Therefore, we have

$\displaystyle\mathbb{P}\Biggl{(}\\{\mathbf{S}\in\mathfrak{Z}\\}\cap\left\\{\max_{w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})}\mathcal{G}_{n}(w)\geq\varepsilon(\alpha(\mathbf{S},n))\right\\}\Biggr{)}$
$\displaystyle\leq\zeta_{2}+M\sum_{m=0}^{\lceil\frac{d^{\ast}}{\rho}\rceil}\sum_{w\in
N_{\beta_{n},k}}\mathbb{P}\left(\Big{\\{}\mathcal{G}_{n}(w)\geq\varepsilon(m\rho)\Big{\\}}\right)$
$\displaystyle\qquad\times\mathbb{P}\Biggl{(}\Big{\\{}w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\Big{\\}}\cap\left\\{\left|N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\right|\leq\left(\frac{1}{\beta_{n}}\right)^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\right\\}\cap\left\\{\alpha(\mathbf{S},n)\in
J_{m}(\rho)\right\\}\Bigg{)},$

Recall that
$\mathcal{G}_{n}(w)=\frac{1}{n}\sum_{i=1}^{n}[\ell(w,z_{i})-\mathbb{E}_{z\sim\pi}\ell(w,z)]$.
Since the $(z_{i})_{i}$ are i.i.d. by Assumption 3 it follows that
$\mathcal{G}_{n}(w)$ is $(\nu/\sqrt{n},\kappa/n)$-sub-exponential and from
[Wai19, Proposition 2.9] we have that

$\mathbb{P}\left(\Big{\\{}\mathcal{G}_{n}(w)\geq\varepsilon(m\rho)\Big{\\}}\right)\leq
2\exp\left(-\frac{n\varepsilon(m\rho)^{2}}{2\nu^{2}}\right),$

as long as $\varepsilon(m\rho)\leq\nu^{2}/\kappa$.

For $n$ large enough we may assume that
$\varepsilon(d^{\ast})\leq\nu^{2}/\kappa$, and thus

$\displaystyle\mathbb{P}\Biggl{(}\\{\mathbf{S}\in\mathfrak{Z}\\}\cap\left\\{\max_{w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})}\mathcal{G}_{n}(w)\geq\varepsilon(\alpha(\mathbf{S},n))\right\\}\Biggr{)}$
$\displaystyle\leq
2M\sum_{m=0}^{\lceil\frac{d}{\rho}\rceil}\mathrm{e}^{-\frac{2n\varepsilon^{2}(m\rho)}{B^{2}}}\sum_{w\in
N_{\beta_{n},k}}\mathbb{P}\Biggl{(}\Big{\\{}w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\Big{\\}}\cap\left\\{\left|N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\right|\leq\left(\frac{1}{\beta_{n}}\right)^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\right\\}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\cap\left\\{\alpha(\mathbf{S},n)\in
J_{m}(\rho)\right\\}\Bigg{)}+\zeta_{2}$ $\displaystyle\leq
2M\sum_{m=0}^{\lceil\frac{d}{\rho}\rceil}\mathrm{e}^{-\frac{n\varepsilon^{2}(m\rho)}{2\nu^{2}}}\sum_{w\in
N_{\beta_{n},k}}\mathbb{E}\Biggl{[}\mathds{1}\Big{\\{}w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\Big{\\}}$
$\displaystyle\qquad\qquad\qquad\times\mathds{1}\left\\{\left|N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\right|\leq\left(\frac{1}{\beta_{n}}\right)^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\right\\}\times\mathds{1}\left\\{\alpha(\mathbf{S},n)\in
J_{m}(\rho)\right\\}\Bigg{]}+\zeta_{2}$ $\displaystyle\leq
2M\sum_{m=0}^{\lceil\frac{d}{\rho}\rceil}\mathrm{e}^{-\frac{n\varepsilon^{2}(m\rho)}{2\nu^{2}}}\mathbb{E}\Biggl{[}\sum_{w\in
N_{\beta_{n},k}}\mathds{1}\Big{\\{}w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\Big{\\}}$
$\displaystyle\qquad\qquad\qquad\times\mathds{1}\left\\{\left|N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\right|\leq\left(\frac{1}{\beta_{n}}\right)^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\right\\}\times\mathds{1}\left\\{\alpha(\mathbf{S},n)\in
J_{m}(\rho)\right\\}\Bigg{]}+\zeta_{2}$ (73) $\displaystyle\leq
2M\sum_{m=0}^{\lceil\frac{d}{\rho}\rceil}\mathrm{e}^{-\frac{n\varepsilon^{2}(m\rho)}{2\nu^{2}}}\mathbb{E}\Biggl{[}|N_{\beta_{n}}(A_{\mathbf{S}_{n},k})|\times\mathds{1}\left\\{\left|N_{\beta_{n}}(A_{\mathbf{S}_{n},k})\right|\leq\left(\frac{1}{\beta_{n}}\right)^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\right\\}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\times\mathds{1}\left\\{\alpha(\mathbf{S},n)\in
J_{m}(\rho)\right\\}\Bigg{]}+\zeta_{2}$
$\displaystyle=\zeta_{2}+2M\sum_{m=0}^{\lceil\frac{d}{\rho}\rceil}\mathrm{e}^{-\frac{n\varepsilon^{2}(m\rho)}{2\nu^{2}}}\mathbb{E}\left[\left[\frac{1}{\beta_{n}}\right]^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\times\mathds{1}\left\\{\alpha(\mathbf{S},n)\in
J_{m}(\rho)\right\\}\right],$

where (73) follows from Fubini’s theorem.

Now, notice that the mapping $t\mapsto\varepsilon^{2}(t)$ is linear with
derivative bounded by

$\frac{2\nu^{2}}{n}\log(1/\beta_{n}).$

Therefore, on the event $\\{\alpha(\mathbf{S},n)\in J_{m}(\rho)\\}$ we have

$\displaystyle\varepsilon^{2}(\alpha(\mathbf{S},n))-\varepsilon^{2}(m\rho)\leq$
$\displaystyle(\alpha(\mathbf{S},n)-m\rho)\frac{2\nu^{2}}{n}\log(1/\beta_{n})$
(74) $\displaystyle\leq$
$\displaystyle\rho\frac{2\nu^{2}}{n}\log(1/\beta_{n}).$ (75)

By choosing $\rho=\rho_{n}=1/\log(1/\beta_{n})$, we have

$\varepsilon^{2}(m\rho_{n})\geq\varepsilon^{2}\left(\alpha(\mathbf{S},n)\right)-\frac{2\nu^{2}}{n}.$

Therefore, we have

$\displaystyle\mathbb{P}\Biggl{(}\\{\mathbf{S}\in\mathfrak{Z}\\}\cap\Bigl{\\{}\max_{w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})}\mathcal{G}_{n}(w)\geq\varepsilon(\alpha(\mathbf{S},n))\Bigr{\\}}\Biggr{)}$
$\displaystyle\leq\zeta_{2}+2M\mathbb{E}\left[\sum_{m=0}^{\lceil\frac{d}{\rho_{n}}\rceil}\mathrm{e}^{-\frac{n\varepsilon^{2}(m\rho_{n})}{2\nu^{2}}}\left[\frac{1}{\beta_{n}}\right]^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\times\mathds{1}\left\\{\alpha(\mathbf{S},n)\in
J_{m}(\rho_{n})\right\\}\right]$
$\displaystyle\leq\zeta_{2}+2M\mathbb{E}\left[\sum_{m=0}^{\lceil\frac{d}{\rho_{n}}\rceil}\mathrm{e}^{-\frac{n\varepsilon^{2}(\alpha(\mathbf{S},n))}{2\nu^{2}}+1}\left[\frac{1}{\beta_{n}}\right]^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\times\mathds{1}\left\\{\alpha(\mathbf{S},n)\in
J_{m}(\rho_{n})\right\\}\right]$
$\displaystyle=\zeta_{2}+2M\mathbb{E}\left[\mathrm{e}^{-\frac{n\varepsilon^{2}(\alpha(\mathbf{S},n))}{2\nu^{2}}+1}\left[\frac{1}{\beta_{n}}\right]^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}\right].$

By the definition of $\varepsilon(t)$, for any $\mathbf{S}$ and $n$ we have
that:

$\displaystyle
2M\mathrm{e}^{-\frac{n\varepsilon^{2}(\alpha(\mathbf{S},n))}{2\nu^{2}}+1}\left[\frac{1}{\beta_{n}}\right]^{\tilde{\alpha}(\mathbf{S},n,k,\epsilon)}$
$\displaystyle=2\mathrm{e}\zeta_{2}.$

Therefore,

$\displaystyle\mathbb{P}\Biggl{(}\\{\mathbf{S}\in\mathfrak{Z}\\}\cap\Bigl{\\{}\max_{w\in
N_{\beta_{n}}(A_{\mathbf{S}_{n},k})}\mathcal{G}_{n}(w)\geq\varepsilon(\alpha(\mathbf{S},n))\Bigr{\\}}\Biggr{)}\leq(1+2\mathrm{e})\zeta_{2}.$

Therefore, by using the definition of $\varepsilon(t)$, (63), and (65), with
probability at least $1-\zeta-\delta_{k}-(1+2\mathrm{e})\zeta_{2}$, we have

$\displaystyle|\hat{\mathcal{R}}(W,\mathbf{S}_{n})-\mathcal{R}(W)|\leq
2\sqrt{\frac{2\nu^{2}}{n}\left[\log\left(\frac{1}{\beta_{n}}\right)\Bigl{(}\alpha(\mathbf{S},n)+\xi_{n}c(\delta_{k})+\xi_{n}c^{\prime}(\beta_{n})+\epsilon\Bigr{)}+\log\left(\frac{M}{\zeta_{2}}\right)\right]}$
$\displaystyle\qquad\qquad\qquad+2L\beta_{n}.$

Choose $k$ such that $\delta_{k}\leq\zeta/2$,
$\zeta_{2}=\zeta/(2+4\mathrm{e})$, $\xi_{n}=\log\log(n)$,
$\epsilon=\alpha(\mathbf{S},n)$, and $\beta_{n}=\sqrt{2\nu^{2}/L^{2}n}$. Then,
with probability at least $1-2\zeta$, we have

$\displaystyle|\hat{\mathcal{R}}(W,\mathbf{S}_{n})-\mathcal{R}(W)|$ (76)
$\displaystyle\leq
4\sqrt{\frac{4\nu^{2}}{n}\left[\frac{1}{2}\log\left(nL^{2}\right)\Bigl{(}2\alpha(\mathbf{S},n)+c(\delta_{k})\log\log(n)+o(\log\log(n))\Bigr{)}+\log\left(\frac{13M}{\zeta}\right)\right]}.$
(77)

Finally, as we have $\alpha(\mathbf{S},n)\log(n)=\omega(\log\log(n))$, for $n$
large enough, we obtain

$\displaystyle|\hat{\mathcal{R}}(W,\mathbf{S}_{n})-\mathcal{R}(W)|\leq
8\nu\sqrt{\frac{\alpha(\mathbf{S},n)\log^{2}\left(nL^{2}\right)}{n}+\frac{\log\left({13M}/{\zeta}\right)}{n}}.$
(78)

This completes the proof. ∎

###  G.3 Proof of Proposition 2

###### Proof.

If we apply SGD this results in the recursion (6) with

$\displaystyle h_{i}(w)=M_{i}w+q_{i}\quad\text{ with}\quad
M_{i}:=(1-\eta\lambda)I-\eta{H_{i}},$ (79) $\displaystyle
H_{i}:=\frac{1}{b}\sum\limits_{j\in S_{i}}a_{j}a_{j}^{T},\quad
q_{i}:=(\eta/b)\sum\limits_{j\in S_{i}}a_{j}y_{j}\,,$

where $a_{j}\in\mathbb{R}^{d}$ are the input vector, and $y_{j}$ are the
output variable, and $\\{S_{i}\\}_{i=1}^{m_{b}}$ is a partition of
$\\{1,2,\dots,n\\}$ with $|S_{i}|=b$ with $i=1,2,\ldots,m_{b}$ and
$m_{b}=n/b$. Let $L_{i}$ be the Lipschitz constant of $a_{i}$. It can be seen
that $\nabla\ell(w,z_{i})$ is Lipschitz with constant
$L_{i}=R_{i}^{2}+\lambda$, where $R_{i}=\max_{j\in S_{i}}\|a_{j}\|$. We assume
$\eta<2/L=2/(R^{2}+\lambda)$, where $R=\max_{i}R_{i}$, otherwise the
expectation of the iterates can diverge from some initializations and for some
choices of the batch-size. We have

$h_{i}(u)-h_{i}(v)=M_{i}(u-v),$

where

$0\preceq\left(1-\eta\lambda-\eta R_{i}^{2}\right)I\preceq
M_{i}\preceq(1-\eta\lambda)I.$

Hence, $h_{i}$ is bi-Lipschitz in the sense of [Anc16] where

$\gamma_{i}(u-v)\leq\|h_{i}(u)-h_{i}(v)\|\leq\Gamma_{i}(u-v),$

with

$\displaystyle\gamma_{i}=\min\left(\left|1-\eta\lambda-\eta
R_{i}^{2}\right|,\left|1-\eta\lambda\right|\right),$ (80)
$\displaystyle\Gamma_{i}=\max\left(\left|1-\eta\lambda-\eta
R_{i}^{2}\right|,\left|1-\eta\lambda\right|\right)<1,$ (81)

as long as $\gamma_{i}>0.$ For simplicity of the presentation, we assume
$\eta<\frac{1}{R^{2}+\lambda}$ in which case the expressions for $\gamma_{i}$
and $\Gamma_{i}$ simplify to:

$\gamma_{i}=1-\eta\lambda-\eta R_{i}^{2},\quad\Gamma_{i}=1-\eta\lambda.$

In this case, it is easy to see that

$0<\gamma_{i}\leq\|J_{h_{i}}(w)\|\leq\Gamma_{i}<1,$

and it follows from Theorem 2 that

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\mathrm{Ent}}{\sum_{i=1}^{m_{b}}p_{i}\log(\Gamma_{i})}=\frac{-\mathrm{Ent}}{\sum_{i=1}^{m_{b}}p_{i}\log(1/\Gamma_{i})}.$
(82)

By Jensen’s inequality, we have

$-\mathrm{Ent}=\sum_{i=1}^{m_{b}}p_{i}\log\left(\frac{1}{p_{i}}\right)\leq\log\left(\sum_{i=1}^{m_{b}}p_{i}\cdot\frac{1}{p_{i}}\right)=\log(m_{b}),$
(83)

where $m_{b}=\binom{n}{b}$.

When $\eta<\frac{1}{R^{2}+\lambda}$, we recall that
$\gamma_{i}=1-\eta\lambda-\eta R_{i}^{2}$ and $\Gamma_{i}=1-\eta\lambda$.
Therefore,

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{-\mathrm{Ent}}{\sum_{i=1}^{m_{b}}p_{i}\log(1/\Gamma_{i})}\leq\frac{\log\left(m_{b}\right)}{\log(1/(1-\eta\lambda))}=\frac{\log\left(n/b\right)}{\log(1/(1-\eta\lambda))}.$
(84)

The proof is complete. ∎

###  G.4 Proof of Proposition 3

###### Proof.

When the batch-size is equal to $b$, we can compute that the Jacobian is given
by

$J_{h_{i}}(w)=\frac{1}{b}\sum_{j\in S_{i}}\left(1-\eta\lambda+\eta
y_{j}^{2}\left[\frac{e^{-y_{j}a_{j}^{T}w}}{(1+e^{-y_{j}a_{j}^{T}w})^{2}}\right]a_{j}a_{j}^{T}\right),$
(85)

where $\\{S_{i}\\}_{i=1}^{m_{b}}$ is a partition of $\\{1,2,\dots,n\\}$ with
$|S_{i}|=b$, where $i=1,2,\ldots,m_{b}$ and $m_{b}=n/b$. Note that the input
data is bounded, i.e. $R_{i}:=\max_{j\in S_{i}}\|a_{j}\|<\infty$, and
$R:=\max_{i}R_{i}<2\sqrt{\lambda}$. Recall that the step-size is sufficiently
small, i.e. $\eta<1/\lambda$. One can provide the upper bound on
$J_{h_{i}}(w)$:

$\displaystyle\|J_{h_{i}}(w)\|\leq\Gamma_{i}:=1-\eta\lambda+\frac{1}{4}\eta
R_{i}^{2}\leq 1-\eta\lambda+\frac{1}{4}\eta R^{2},$ (86)

so that

$\displaystyle\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$
$\displaystyle\leq\frac{\mathrm{Ent}}{\sum_{i=1}^{m_{b}}p_{i}\log(\Gamma_{i})}=\frac{-\mathrm{Ent}}{\sum_{i=1}^{m_{b}}p_{i}\log(1/(1-\eta\lambda+\frac{1}{4}\eta
R_{i}^{2}))}$ $\displaystyle\leq\frac{\log
m_{b}}{\log(1/(1-\eta\lambda+\frac{1}{4}\eta R^{2}))}$ (87)
$\displaystyle=\frac{\log\left(n/b\right)}{\log(1/(1-\eta\lambda+\frac{1}{4}\eta
R^{2}))},$ (88)

where we used (86) and (83) in (87).

The proof is complete. ∎

###  G.5 Proof of Proposition 4

###### Proof.

We can compute that

$\displaystyle\nabla\ell(w,z_{i})=-a_{i}\rho^{\prime}\left(y_{i}-\langle
w,a_{i}\rangle\right)+\lambda_{r}w,$ (89) $\displaystyle
h_{i}(w)=\frac{1}{b}\sum_{j\in S_{i}}(1-\eta\lambda_{r})w+\eta
a_{j}\rho^{\prime}\left(y_{j}-\langle w,a_{j}\rangle\right),$ (90)
$\displaystyle J_{h_{i}}(w)=\frac{1}{b}\sum_{j\in
S_{i}}(1-\eta\lambda_{r})I-\eta
a_{j}a_{j}^{T}\rho^{\prime\prime}\left(y_{j}-\langle w,a_{j}\rangle\right),$
(91)

where $\\{S_{i}\\}_{i=1}^{m_{b}}$ is a partition of $\\{1,2,\dots,n\\}$ with
$|S_{i}|=b$, where $i=1,2,\ldots,m_{b}$ with $m_{b}=n/b$. Furthermore,
$\|\rho_{\exp}^{\prime\prime}\|_{\infty}=\rho_{\exp}^{\prime\prime}(0)=\frac{2}{t_{0}}$.
Therefore, for $\eta\in(0,\frac{1}{\lambda_{r}+R^{2}(2/t_{0})})$,

$0<(1-\eta\lambda_{r})-\eta
R^{2}\frac{2}{t_{0}}\leq\|J_{h_{i}}(w)\|\leq(1-\eta\lambda_{r})+\eta
R^{2}\frac{2}{t_{0}},$ (92)

where $R=\max_{i}\|a_{i}\|<\sqrt{\lambda_{r}t_{0}/2}$. We have

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log
m_{b}}{\log(1/(1-\eta\lambda_{r}+\eta
R^{2}\frac{2}{t_{0}}))}=\frac{\log\left(n/b\right)}{\log(1/(1-\eta\lambda_{r}+\eta
R^{2}\frac{2}{t_{0}}))},$ (93)

where we used (92) and (83). The proof is complete.

∎

###  G.6 Proof of Proposition 7

###### Proof.

We can compute that

$\displaystyle\nabla\ell(w,z_{i})=y_{i}\ell_{\sigma}^{\prime}\left(y_{i}a_{i}^{T}w\right)a_{i}+\lambda
w,$
$\displaystyle\nabla^{2}\ell(w,z_{i})=y_{i}^{2}\ell_{\sigma}^{\prime\prime}\left(y_{i}a_{i}^{T}w\right)a_{i}a_{i}^{T}+\lambda,$
$\displaystyle h_{i}(w)=w-\frac{\eta}{b}\sum_{j\in S_{i}}\nabla\ell(w,z_{j}),$

where $\\{S_{i}\\}_{i=1}^{m_{b}}$ is a partition of $\\{1,2,\dots,n\\}$ with
$|S_{i}|=b$, where $i=1,2,\ldots,m_{b}$ with $m_{b}=n/b$, so that

$J_{h_{i}}(w)=I-\frac{\eta}{b}\sum_{j\in
S_{i}}\nabla^{2}\ell(w,z_{j})=(1-\eta\lambda)I-\frac{\eta}{b}\sum_{j\in
S_{i}}y_{j}^{2}\ell_{\sigma}^{\prime\prime}\left(y_{j}a_{j}^{T}w\right)a_{j}a_{j}^{T},$

with

$\ell_{\sigma}^{\prime\prime}(z)=\frac{1}{\sigma}\frac{e^{-(1-z)/\sigma}}{(1+e^{-(1-z)/\sigma})^{2}}\geq
0,\quad\|\ell_{\sigma}^{\prime\prime}\|_{\infty}=\ell_{\sigma}^{\prime\prime}(1)=\frac{1}{4\rho}.$

Therefore, if $\eta\in(0,\frac{1}{\lambda+\|R\|^{2}/(4\rho)})$ and
$R:=\max_{i}\|a_{i}\|$, then

$1-\eta\lambda-\eta\frac{1}{4\rho}R^{2}\leq\|J_{h_{i}}(w)\|\leq
1-\eta\lambda.$

This implies that

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log
m_{b}}{\log(1/(1-\eta\lambda))}=\frac{\log\left(n/b\right)}{\log(1/(1-\eta\lambda))},$
(94)

where we used (83). The proof is complete. ∎

###  G.7 Proof of Proposition 5

###### Proof.

We recall that the loss is given by:

$\ell(w,z_{i}):=\|y_{i}-\hat{y}_{i}\|^{2}+\lambda\|w\|^{2}/2,\quad\hat{y}_{i}:=\sum\limits_{r=1}^{m}b_{r}\sigma\left(w_{r}^{T}a_{i}\right),$
(95)

where the non-linearity $\sigma:\mathbb{R}\to\mathbb{R}$ is smooth and
$\lambda>0$ is a regularization parameter. Note that we can re-write (95) as
$\ell(w,z_{i})=\left\|y_{i}-b^{T}\sigma\left(w_{r}^{T}a_{i}\right)\right\|^{2}+\lambda\|w\|^{2}/2$.
We can compute that

$\frac{\partial\ell(w,z_{i})}{\partial
w_{r}}=-(y_{i}-\hat{y}_{i})\frac{\partial\hat{y}_{i}}{\partial w_{r}}+\lambda
w_{r}=-(y_{i}-\hat{y}_{i})b_{r}\sigma^{\prime}(w_{r}^{T}a_{i})a_{i}+\lambda
w_{r}.$ (96)

Therefore,

$\nabla\ell(w,z_{i})=-(y_{i}-\hat{y}_{i})v_{i}+\lambda
w,\quad\text{where}\quad
v_{i}:=\begin{bmatrix}b_{1}\sigma^{\prime}(w_{1}^{T}a_{i})a_{i}\\\
b_{2}\sigma^{\prime}(w_{2}^{T}a_{i})a_{i}\\\ \cdots\\\
b_{m}\sigma^{\prime}(w_{m}^{T}a_{i})a_{i}\\\ \end{bmatrix},$

with

$h_{i}(w)=w-\frac{\eta}{b}\sum_{j\in S_{i}}\nabla\ell(w,z_{i}),$

and

$\displaystyle J_{h_{i}}(w)$
$\displaystyle=(1-\eta\lambda)I-\frac{\eta}{b}\sum_{j\in S_{i}}v_{j}\otimes
v_{j}^{T}$ $\displaystyle\quad+\frac{\eta}{b}\sum_{j\in
S_{i}}(y_{j}-\hat{y}_{j})\begin{bmatrix}b_{1}\sigma^{\prime\prime}(w_{1}^{T}a_{j})a_{j}a_{j}^{T}&0_{d}&\ldots&0_{d}\\\
0_{d}&b_{2}\sigma^{\prime\prime}(w_{2}^{T}a_{j})a_{j}a_{j}^{T}&\ldots&0_{d}\\\
\vdots&\vdots&\ddots&\vdots\\\
0_{d}&0_{d}&\ldots&b_{m}\sigma^{\prime\prime}(w_{m}^{T}a_{j})a_{j}a_{j}^{T}\\\
\end{bmatrix}$ $\displaystyle=(1-\eta\lambda)I-\frac{\eta}{b}\sum_{j\in
S_{i}}\mbox{diag}(\\{B_{r}^{(j)}\\}_{r=1}^{m}),$ (97)

where $\\{S_{i}\\}_{i=1}^{m_{b}}$ is a partition of $\\{1,2,\dots,n\\}$ with
$|S_{i}|=b$, where $i=1,2,\ldots,m_{b}$ with $m_{b}=n/b$, and

$B_{r}^{(i)}:=b_{r}\left[-(y_{i}-\hat{y}_{i})\sigma^{\prime\prime}(w_{r}^{T}a_{i})+(\sigma^{\prime}(w_{r}^{T}a_{i}))^{2}\right]a_{i}a_{i}^{T},$
(98)

and $0_{d}$ is a $d\times d$ zero matrix and
$\mbox{diag}(\\{B_{r}^{(i)}\\}_{r=1}^{m})$ denotes a block diagonal matrix
with the matrices $B_{r}^{(i)}$ on the diagonal. We assume the output $y_{i}$
and the activation function $\sigma$ and its second derivative
$\sigma^{\prime\prime}$ is bounded. This would for instance clearly hold for
classification problems where $y_{i}$ can take integer values on a compact set
with a sigmoid or hyperbolic tangent activation function. Then, under this
assumption, there exists a constant $M_{y}>0$ such that
$\max_{i}\|y_{i}-\hat{y}_{i}\|\leq M_{y}$. Then for
$\eta\in(0,\frac{1}{2\lambda})$ and $\lambda>C$ where
$C:=M_{y}\|b\|_{\infty}\|\sigma^{\prime\prime}\|R^{2}+\left(\max_{j}\|v_{j}\|_{\infty}\right)^{2}$,
we get

$1-\eta(C+\lambda)\leq\|J_{h_{i}}(w)\|\leq 1-\eta(\lambda-C).$

This implies that

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log
m_{b}}{\log(1/(1-\eta(\lambda-C)))}=\frac{\log\left(n/b\right)}{\log(1/(1-\eta(\lambda-C)))},$
(99)

where we used (83). The proof is complete.

∎

###  G.8 Proof of Proposition 8

###### Proof.

Recall that $H$ is positive-definite and there exist some $m,M>0$:

$0\prec mI\preceq H\preceq MI.$ (100)

We have

$h_{i}(u)-h_{i}(v)=M_{i}(u-v),$

where

$0\preceq\left(1-\eta\lambda m^{-1}-\eta m^{-1}R_{i}^{2}\right)I\preceq
M_{i}\preceq\left(1-\eta\lambda M^{-1}\right)I,$ (101)

where $R_{i}:=\max_{j\in S_{i}}\|a_{j}\|$, and we recall the assumption that
$\eta<\frac{m}{R^{2}+\lambda}$, with $R:=\max_{i}R_{i}$. Hence, $h_{i}$ is bi-
Lipschitz in the sense of [Anc16] where

$\gamma_{i}(u-v)\leq\|h_{i}(u)-h_{i}(v)\|\leq\Gamma_{i}(u-v),$

with

$\displaystyle\gamma_{i}=\min\left(\left|1-\eta\lambda m^{-1}-\eta
m^{-1}R_{i}^{2}\right|,\left|1-\eta M^{-1}\lambda\right|\right),$ (102)
$\displaystyle\Gamma_{i}=\max\left(\left|1-\eta\lambda m^{-1}-\eta
m^{-1}R_{i}^{2}\right|,\left|1-\eta M^{-1}\lambda\right|\right)<1,$ (103)

as long as $\gamma_{i}>0.$ We recall the assumption
$\eta<\frac{m}{R^{2}+\lambda}$, where $R:=\max_{i}R_{i}$, in which case the
expressions for $\gamma_{i}$ and $\Gamma_{i}$ simplify to:

$\gamma_{i}=1-\eta m^{-1}\lambda-\eta m^{-1}R_{i}^{2},\quad\Gamma_{i}=1-\eta
M^{-1}\lambda.$

In this case, it is easy to see that

$0<\gamma_{i}\leq\|J_{h_{i}}(w)\|\leq\Gamma_{i}<1,$

and it follows from Theorem 2 that

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\mathrm{Ent}}{\sum_{i=1}^{m_{b}}p_{i}\log(\Gamma_{i})}\leq\frac{\log
m_{b}}{\log(1/(1-\eta
M^{-1}\lambda))}=\frac{\log\left(n/b\right)}{\log(1/(1-\eta M^{-1}\lambda))},$
(104)

where we used (83). The proof is complete.

∎

###  G.9 Proof of Proposition 9

###### Proof.

Similar as in the proof of Proposition 3, we can compute that the Jacobian is
given by

$J_{h_{i}}(w)=\frac{1}{b}\sum_{j\in S_{i}}\left(1-\eta H^{-1}\lambda+\eta
H^{-1}y_{j}^{2}\left[\frac{e^{-y_{j}a_{j}^{T}w}}{(1+e^{-y_{j}a_{j}^{T}w})^{2}}\right]a_{j}a_{j}^{T}\right),$
(105)

where $\\{S_{i}\\}_{i=1}^{m_{b}}$ is a partition of $\\{1,2,\dots,n\\}$ with
$|S_{i}|=b$, where $i=1,2,\ldots,m_{b}$ with $m_{b}=n/b$, and $H$ is a
positive-definite matrix with $0\prec mI\preceq H\preceq MI$. recall that the
input data is bounded, i.e. $\max_{j\in S_{i}}\|a_{j}\|\leq R_{i}$ for some
$R_{i}$, and $R:=\max_{i}R_{i}$ satisfying $R<2\sqrt{m\lambda/M}$. Also recall
the step-size is sufficiently small, i.e. $\eta<m/\lambda$. One can provide
upper bounds and lower bounds on $J_{h_{i}}(w)$:

$\displaystyle\|J_{h_{i}}(w)\|\leq\Gamma_{i}:=1-\eta
M^{-1}\lambda+\frac{1}{4}\eta m^{-1}R_{i}^{2},$ (106)
$\displaystyle\|J_{h_{i}}(w)\|\geq\gamma_{i}:=1-\eta m^{-1}\lambda,$ (107)

so that

$\displaystyle\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}$
$\displaystyle\leq\frac{-\mathrm{Ent}}{\sum_{i=1}^{m_{b}}p_{i}\log(1/(1-\eta
M^{-1}\lambda+\frac{1}{4}\eta m^{-1}R_{i}^{2}))}$ $\displaystyle\leq\frac{\log
m_{b}}{\log(1/(1-\eta M^{-1}\lambda+\frac{1}{4}\eta m^{-1}R^{2}))}$ (108)
$\displaystyle=\frac{b\log\left(n/b\right)}{\log(1/(1-\eta
M^{-1}\lambda+\frac{1}{4}\eta m^{-1}R^{2}))},$ (109)

where we used (83) in (108). The proof is complete.

∎

###  G.10 Proof of Proposition 10

###### Proof.

Similar as in the proof of Proposition 4, we can compute that

$\displaystyle J_{h_{i}}(w)=\frac{1}{b}\sum_{j\in S_{i}}\left(I-\eta
H^{-1}\lambda_{r}\right)-\eta
H^{-1}a_{j}a_{j}^{T}\rho^{\prime\prime}\left(y_{j}-\langle
w,a_{j}\rangle\right),$ (110)

where $\\{S_{i}\\}_{i=1}^{m_{b}}$ is a partition of $\\{1,2,\dots,n\\}$ with
$|S_{i}|=b$, where $i=1,2,\ldots,m_{b}$ with $m_{b}=n/b$, and $H$ is a
positive-definite matrix with $0\prec mI\preceq H\preceq MI$. For the function
$\rho$, a standard choice is exponential squared loss:
$\rho_{\exp}(t)=1-e^{-|t|^{2}/t_{0}}$, where $t_{0}>0$ is a tuning parameter.
We can compute that
$\|\rho_{\exp}^{\prime\prime}\|_{\infty}=\rho_{\exp}^{\prime\prime}(0)=\frac{2}{t_{0}}$.
Therefore, for $\eta\in(0,\frac{m}{\lambda_{r}+R^{2}(2/t_{0})})$,

$0<1-\eta m^{-1}\lambda_{r}-\eta
m^{-1}R^{2}\frac{2}{t_{0}}\leq\|J_{h_{i}}(w)\|\leq 1-\eta
M^{-1}\lambda_{r}+\eta m^{-1}R^{2}\frac{2}{t_{0}},$ (111)

where $R=\max_{i}\|a_{i}\|$ and we recall that
$R<\sqrt{\lambda_{r}t_{0}m/(2M)}$. We have

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log
m_{b}}{\log(1/(1-\eta M^{-1}\lambda_{r}+\eta
m^{-1}R^{2}\frac{2}{t_{0}}))}=\frac{\log\left(n/b\right)}{\log(1/(1-\eta
M^{-1}\lambda_{r}+\eta m^{-1}R^{2}\frac{2}{t_{0}}))},$ (112)

where we used (83). The proof is complete.

∎

###  G.11 Proof of Proposition 11

###### Proof.

Similar as in the proof of Proposition 7, we can compute that

$J_{h_{i}}(w)=I-\frac{\eta}{b}H^{-1}\sum_{j\in
S_{i}}\nabla^{2}\ell(w,z_{j})=(1-\eta\lambda
H^{-1})I-\frac{\eta}{b}H^{-1}\sum_{j\in
S_{i}}y_{j}^{2}\ell_{\sigma}^{\prime\prime}\left(y_{j}a_{j}^{T}w\right)a_{j}a_{j}^{T},$

where $\\{S_{i}\\}_{i=1}^{m_{b}}$ is a partition of $\\{1,2,\dots,n\\}$ with
$|S_{i}|=b$, where $i=1,2,\ldots,m_{b}$ with $m_{b}=n/b$, and $H$ is a
positive-definite matrix with $0\prec mI\preceq H\preceq MI$, and

$\ell_{\sigma}^{\prime\prime}(z)=\frac{1}{\sigma}\frac{e^{-(1-z)/\sigma}}{(1+e^{-(1-z)/\sigma})^{2}}\geq
0,\quad\|\ell_{\sigma}^{\prime\prime}\|_{\infty}=\ell_{\sigma}^{\prime\prime}(1)=\frac{1}{4\rho}.$

Therefore, if $\eta\in(0,\frac{m}{\lambda+\|R\|^{2}/(4\rho)})$ where
$R:=\max_{i}\|a_{i}\|$, then

$1-\eta m^{-1}\lambda-\eta m^{-1}\frac{1}{4\rho}R^{2}\leq\|J_{h_{i}}(w)\|\leq
1-\eta M^{-1}\lambda.$

This implies that

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log
m_{b}}{\log(1/(1-\eta
M^{-1}\lambda))}=\frac{\log\left(n/b\right)}{\log(1/(1-\eta M^{-1}\lambda))},$
(113)

where we use (83). The proof is complete.

∎

###  G.12 Proof of Proposition 12

###### Proof.

By following the similar derivations as in Proposition 5, we obtain

$\displaystyle J_{h_{i}}(w)=\left(1-\eta\lambda
H^{-1}\right)I-\frac{\eta}{b}H^{-1}\sum_{j\in
S_{i}}\mbox{diag}\left(\\{B_{r}^{(j)}\\}_{r=1}^{m}\right),$ (114)

where $\\{S_{i}\\}_{i=1}^{m_{b}}$ is a partition of $\\{1,2,\dots,n\\}$ with
$|S_{i}|=b$, where $i=1,2,\ldots,m_{b}$, with $m_{b}=n/b$, and $H$ is a
positive-definite matrix and $0\prec mI\preceq H\preceq MI$ for some $m,M>0$,
and $\mbox{diag}(\\{B_{r}^{(i)}\\}_{r=1}^{m})$ denotes a block diagonal matrix
with the matrices $B_{r}^{(i)}$ on the diagonal defined in Proposition 5. As
in Proposition 5, there exists a constant $M_{y}>0$ such that
$\max_{i}\|y_{i}-\hat{y}_{i}\|\leq M_{y}$. Then for
$\eta\in(0,\frac{m}{C+\lambda})$ and $\lambda>\frac{M}{m}C$ where
$C:=M_{y}\|b\|_{\infty}\|\sigma^{\prime\prime}\|R^{2}+\left(\max_{j}\|v_{j}\|_{\infty}\right)^{2}$,
we get

$1-\eta m^{-1}(C+\lambda)\leq\|J_{h_{i}}(w)\|\leq
1-\eta\left(M^{-1}\lambda-m^{-1}C\right).$

This implies that

$\overline{\dim}_{\mathrm{H}}\mu_{W|\mathbf{S}_{n}}\leq\frac{\log
m_{b}}{\log(1/(1-\eta(M^{-1}\lambda-m^{-1}C)))}=\frac{\log\left(n/b\right)}{\log(1/(1-\eta(M^{-1}\lambda-m^{-1}C)))},$
(115)

where we used (83). The proof is complete. ∎