Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms
Authors: Alexander Camuto
George Deligiannidis
Murat A Erdogdu
Mert Gurbuzbalaban
Umut Simsekli
Lingjiong Zhu
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: generalization
stochastic gradient descent
deep learning
fractals

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 \emph{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 \emph{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. Then, by 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. 

Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms
Alexander Camuto', George Deligiannidis', Murat Erdogdu', Mert Gürbüzzalaaann Umut Şimşekli Lingjiong Zhu
1: University of Oxford & Alan Turing Institute 2: University of Toronto Vector Institute
Rutgers Business School 4: INRIA & École Normale Supérieure PSL Research University 5: Florida State University
The authors are in alphabetical order. 5:: Corresponding authors
Abstract
Understanding generalization in deep learning has been one of the major chal- lenges 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 perfor- mance. In this study, we approach this problem from a dynamical systems theory perspective and represent stochastic optimization algorithms 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 be bounded based on the 'complexity' of the fractal structure that underlies its invariant measure. Then, by 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-layeren 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.
Introduction
In statistical learning, many problems can be naturally formulated as a risk minimization problem
minwerd RR(w) [e-=(((w, })}}
where z E Z denotes a data sample coming from an unknown distribution म, and é Rd x Z + R. is the composition of loss and function from the hypothesis class parameterized by Rdd. Since the distribution я is unknown, one needs to rely on empirical risk minimization as a surrogate to (1),
min (W,, S.)) (1/n) E Elw, 2x)
where S,, {21, ... zn) denotes a training set of n points that are independently and identically distributed (i.i.d)) and sampled from æ. and model training often amounts to using an optimization algorithm to solve the above problem.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Statistical learning theory is mainly interested in understanding the behavior of the generalization error, i.e., R(w, S,,) - 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, NBMS17J. 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* L 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:
ukk 1 - R where VR+(w)= == VR (w) == (1/b) Σ ign, Vl(w, 24).
Here, k represents the iteration counter, 17 > is the step-size (also called the learning-rate), VR2 is the stochastic gradient, b is the batch-size, and 9g C (1, n is a random subset drawn with or without replacement with cardinality [S2g] for all k.
Constant step-size SGD forms a Markov chain with a stationary distribution W ~ j4, 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 Rww) over this limit distribution μ.. In particular, the Markov chain defined by the SGD recursion can be written by using random functions hag at each SGD iteration k; i.e.,
Wk hog (wx-1), with hag (w) = w ())
(3)
Here, the randomness in hn, is due to the selection of the subset 92k In fact, such formulation not specific to SGD; it can cover many other stochastic optimization algorithms if the random function fn, 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 1 I-dimensional quadratic problem with n = 2 and f(w, 21) = w² 2 and (() = w² w²/2- w. We run SGD with constant step-size 7) to minimize the resulting empirical risk. We simply choose Q4 C {1,2) 2) uniformly random with batch-size b = 1, and we plot the histograms of stationary distributions for different step-size choices 17 E {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.
Stationary distribution of SGD
9 1/100
1/3
7 2/3
2
0.0
Figure I: Middle-third Cantor set as the
This behavior is not surprising, at least for this toy example. 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 17 = 2/3 is the famous 'middle-thir -hird Cantor set' [FW09], which coincides with the support of the stationary distribution of the SGD.
support of the stationary distribution of con- stant step-size SGD for l(w, =1) w²/2 and E(w, 22) = w² u.
As another example, we 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. to Ro yi, where for i = 1,..., 5, y: and each coordinate of a; are drawn uniformly random from the interval [-1, 1]. Figure 2 shows the heatmap of the resulting stationary distributions for different step-size choices ranging from 0.1 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.

---

log(1/C) Fractals are complex patterns and the level of this com- plexity is typically measured by the Hausdorff dimen- sion of the fractal, which is notion of dimension that can take fractional values!, 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) ISGN+ 19, $SG19, NeGR 19, ŞZTG20), 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 di- mension that appears in classical learning theory bounds is replaced with the Hausdorff dimension.
(a) = 0.3
(b) 0.5
The fractal geometric approach presented in [$SDE20] can capture the 'low dimensional structure' of frac- tal sets and provides an alternative perspective to the compression-based approaches that aim to understand why overparametrized networks do not overfit [AGNZI8, SAN20, SAM* 20, HJTW21J. However, SDE approxima- tions for SGD often serve as mere heuristics, and guaran- teeing good approximation typically requires unrealis- tically small step-sizes [LTE199] For more realistic step- sizes, theoretical concerns have been raised about the validity of conventional SDE approximations for SGD [LMA21, G$Z21, Yai19]. Another drawback 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.
(c) 1 0.7
(d) 1 = 0.9
Figure 2: The stationary distribution of constant step-size SGD for linear regres- sion, where we have n data points and w E IR?.
We address these issues and present direct, discrete-time analysis by exploiting the connections between IFSs and stochastic optimization algorithms. Our contributions are summarized as follows:
We extend [SSDE20] and show that the generalization error can be linked to the Hausdorff dimension of invariant measures (rather than the Hausdorff dimension of sets as [SSDE20]). More precisely, under appropriate conditions, we establish a generalization bound for the stationary distribution of IFS w ~ fu. That is, with probability least 1 122,
(w:o: S.)) - R(w.RWooo R(wx)) dimny (n) +
(4)
n
for large enough, where dimg the (upper) Hausdorff dimension of the measure p.
By leveraging results from IFS theory, we further link dimn// to (i) the form of the recursion (e.g.. hn, in (3)), (ii) algorithm hyperparameters (e.g., 7), b), and (iii) problem geometry (e.g., Hessian of R&), through single term, which encapsulates all these components and their interaction.
We establish bounds dimun 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, explicitly link the generalization performance of the model to the hyperparameters 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.
Notation and preliminaries. (x, C Rd denotes the closed ball centered around x E R with radius r. A function f Rdd - d2 is said to be (Fréchet) differentiable at æ e Rd if there cxists a dj x de matrix (x) dd + d2 such that lim ff (I f(x) - (z)) |/|l = 0. The matrix Jy (x) is called the differential of f, also known as the Jacobian matrix at and determinant of (x) called the Jacobian determinant [HS74]. For vallev functions f.g, we define f(m) (g(()) if lim (f())//(()) = For a set A, |A] denotes its cardinality. For ecalar-valuce function f R + R. we define Il max,ER [f(r)
'The Hausdorff dimension of the middle-thin Cantor set in Figure I is loga (2) z 0.63 whereas the ambient dimension is 1 [Fa104, Example 2.3].
3

---

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, AGZ2IJ. The inherent "complexity" of a fractal set often plays an important role and 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 [Fa104]) is defined follows. Let F Rd be set and for ò O, let N& (&FF) denote collection of sets that contains the smallest number of closed balls of diameter at most which cover F. Then the upper-Minkowe dimension of F is defined as follows:
dimm F == lim sup log [F(()) / log(1/5)
(5)
To visualize the grid and count how many boxes required cover the set. The upper-Minkowski dimension measures how this number changes as the grid is made finer using a box-counting algorithm.
dimension a set F, consider the set F lying on an evenly spaced
Hausdorff dimension of set. An alternative to the purely geometric Minkowski dimension, the Hausdorff dimension [Hau18] a measure theoretical notion of fractal dimension. It is based on the Hausdorff measure, which generalizes the traditional notions of area and volume non- integer dimensions [Rog98]. More precisely, for 8 2 0, let F C Rd and > O, and denote (F) inf >i=
i= diam(A,) (A,)*, where the infimum is taken over all the 8-coverings {A,}: }: of F, that is, F C U,A, with diam (A.) < å for every The s-dimensional Hausdorff measure of F is defined the monotone limit (*) == lims-0 Hz)(F. When E N, H" is the s 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 C Rd is then defined as follows:
dimn F == sup (8 > 0: (F) > 0}- = inf {s > 0: 74' (P) < oo).
In other words, the Hausdorff dimension of F is the 'moment' 8 when (F) drops from co to O, that is, H((F)= = 0 for all r > dimm and H" (F) = oo for r < dima
We always have 0 < dimH F < d, and when F' is bounded, we always have 0 S dima F < FimyF < d [Fal04]. Furthermore, the Hausdorff dimension of IRd equals d, and the Haus- dorff dimension of smooth Riemannian manifolds correspond their intrinsic dimension, e.g. dimn gd-1 = d - 1, where Sd-1 is the unit sphere in Rdd
Hausdorff dimension of 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, JRO8], 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 dimny of Borel probability measure f on Rd, which is defined as follows: dimuj == inf (dima A {(A) 1}. In other words, dimnj 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 stochastic optimization algorithm. We consider a standard supervised learning setting, where Z = X' x V, where X' the space of features and y is the space of labels, and π is the unknown data distribution on Z.
For mathematical convenience, order to construct the training set with n elements, we first consider an infinite sequence of i.idd data samples from the data distribution म. then we take the first n elements from this infinite sequence. More precisely, we consider the (countable) product measure 00 (TT 2 X ...) defined on the cylindrical sigma-algebra. Then, we consider the infinite i.i.d. itd data sequence as ~ 00, i.e., = 22 with 2j ~ x for all j = 1, 2.... Finally, we define the training set Sn : (Z1,..., 2n), i.c., we take the first elements of 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 S... we represent the training algorithm as an IFS, which is based on the following recursion: we hn, (w)= where the mini-batch 94 is i.i.d. sampled according to some distribution (e.g., sampling without-replacement uniformly among all possible mini-batchess This compact representation enables us to cover 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 hi, (w:SA, S,,) = w (w) - RR (10) where H*(w) is an estimate of the Hessian of RR. 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 S2 can take. For example, in the case of without- replacement bati-batch sampling with batch-size b, there are in total my m, many subsets of 21. ) with cardinality b. Alternatively, another setup would be to divide the dataset into my mi we can randomly choose one of the batches. In both examples we can enumerate as Si, S2. Sm..
wo-replacemeett := (%)
bucch :- n/bb batches with each batch having b elements, and at each iteration k,
If the probability of sampling the mini-batch Ωz S; pr for every then, with a slight abuse of notation, we can rewrite the IFS recursion as:
(6) where Us is a random variable taking values in {1, 21, m. and pt == PPU = -). If the mini- batch sampling is uniform (i.e., the default option in practice), we have p3 = 1/m,; however, we are not restricted to this option, the sampling scheme is allowed to be more general. We finally call the triple (IR4, (+: S,)) {p:)_ an iterated function system (IFS).
Wk: = hug (w
Given a dataset Sn, we are interested in the limiting behavior of the training algorithm (6). We characterize this behavior by considering the invariant measure jwis,, of the IFS (also called stationary distribution), that is a Borel probability measure on Rd, such that Woo ~ jw To be able to work in this context, we first need to ensure that the recursion (6) admits invariant measure, iee, IsW,s. is.. exists. Accordingly, we require the following mild conditions on the IFS (6). Let U be a random variable with the same distribution as UR. If the recursion (6) is Lipschitz average, i.e.,
Iho (1; S by by S,
BL [Sm] < 00,
with Lu = sup Z.yERd
x y/
and is contractive on average, i.e., if
E [log(Lu)] [.
mm , log(L.) < with Ps > 0, for any i 1,..., ma.
>
then it can be shown that the process is ergodic and admits unique invariant measure where the limit := lim (1/kk) log hu,,, ... he, || exists almost surely and is a constant [EIt90], where p is called the Lyapunov exponent. Furthermore, under further technical assumptions, it can be shown that (6) is geometrically ergodic [DF99]. We note that this condition for the existence of the invariant measure is only applicable stochastic optimization algorithms with constant stepsize in which case the random map by is not time-varying. If decaying stepsize is used instead, then the limit may degenerate to be a singleton. For example, in the toy example illustrated in Figure I with quadratics in dimension one, if we use SGD with decaying stepsize πソ- = c/k where the positive constant c is small enough, then the limit of the iterates will be singleton as the iterates will converge to the global minimum of the optimization objective (see e.g. [GOP21, GOP19]).
Our goal will be to relate the generalization error to dimn/w Js... To achieve this goal, at first sight, it might seem tempting to extract full-measure set A by using the definition of P sw.... such that Mw (A) and dimy A z dimg//wss., and then directly invoke the results from [SSDE20], which would link the generalization error to dima A, hence, also to dimu/ is..- However, since [$SDE20] does not consider an IFS framework, the conditions they require (c.g.. boundedness of A, dimm A = dimu A) are not suited to IFSs, and hence prevent us from directly using their results.
As remedy, we make detour and show that we can find almost full-measure sets A, such that FW s. (A) R 1 and dimm A x dimmpwis, (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.
5

---

H 1. For Th almost all S and all n. E N+, the recursion (6) satisfies (7) and (8) and the limit lo logg/ Pwis, (Ba(w, r)) logr] exists for pwis.. -almost every w.
This is common condition [Pes08] and is satisfied for large class of measures. For instance, "sufficiently regular' measures with the property that Cir² S (u( r)) I C2r for some constant >> O and positive constants C1, C2 will satisfy this assumption. Such measures are called Ahlfors- regular (cf. I$SDE20, Assumption H4] for a related condition), and it is known that IFSs that satisty certain 'open set conditions' lead to Ahlfors regular invariant measures (see IMT10, Section 8.3]). Yet, our assumption is more general and does not immediately require Aeluars-re
Under HI, we now formalize our key observation, which serves as the basis for our bounds. Proposition 1. Assume that Hi holds. Then for every E > N4, and " -almostt every S, there exists 6 == ö(E, S,) E (0, [0 and a bounded measurable set As C IR, such that
MW S.. (As.. .) 2 1 8, and Ai dinnnuwis. +
and S,, 0 ass E -
Thanks to this result, we can now leverage the proof technique presented in IŞSDE20, Theorem 21, and link the generalization error to dimn/wwss. through SimmAAs,... We shall emphasize that, mainly due to the sets As,,. 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 'topological sta- bility' condition, and is adapted from I$SDE20, Assumption H5J. Formally, consider the (countably infinite) collection of closed balls of radius 8, whose centers are on the fixed grid and for a set A C. Rd, define NA( :=
No = {{ 2/d ..... (2a++110)
(21
2vd :i E Z,i= L..., .d.
{o E N3. Ba(x, 3) A 0), which the collection of the centers of the balls that intersect A.
22 Let T == x 2 x ...) denote the countable product endowed with the product topology and let B be the Borel a-algebra generated by n For a Borel set A C RRd, let B. G be the sub-o- algebras of B generated by the collections of random variables given by [R(w, Sa): w.w. E IRd 2 1} and { {w E &)) PWis.. (A)..s)) dimmpwis. : :8, E Q w E N3, 2 1). where As..& is given in Proposition J. There exists constant M such that for any F S. G G, have TP (F GG) S MP (F)T(G))
H2 simply ensures that the dependence between the training error and the topological properties of the support of pw]ss, can be controlled via M. Hence, it can be seen as form of algorithmic stability [BE02], where M measures the level of stability of the topology of pWWs,, a small M indicates that the geometrical structure of jWWss, does not heavily depend on the particular value of S,. The constant M is also related to the mutual information [XR17, AAVI8, 18, H$KM21J, but may be better behaved than the mutual information as it relies on very specific functions of the random variables. Similar to mutual information, a-priori there is no reason to expect M to be finite for general algorithms; intuitively, however, the more stochasticity an algorithm incorporates the more we expect the set As..5 and the loss landscape to decouple. For example, for purely random algorithm (which ignores S,)) the two objects will be independent. In the other extreme, where the algorithm is deterministic given the sample may fail to be finite. Since are controlling the generalization error on the support, which is itself a random set depending on the sample, we require H2 to be able to make progress.
We require one final assumption, which states that the loss É sub-exponential.
H 3. É is T.-Lipschitz continuous in w, and when nT, for all w. ((w, 2) is (v, sbbbx-eepppoo that is, for all XX| < 1/H, we have log Egzz [exp (> (E(w) 2) R (())))) S 2 X2//RR
Armed with these assumptions, we can now present our main result.
Theorem 1. Assume that HI to hold and dimnjuwis. = w(og log(m)/ log(n)), T0 almost--uurll. Then, the following bound holds for sufficiently large n.:
dim is, log 2 (nL2)
log(13M/S)
(Ř(W,S,) -R(W) /
(10)
n
n

---

with probability at least 1 2Ç over the joint distribution of ~ T W AW|S..
This theorem shows that the Hausdorff dimension of the invariant measure acts as '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 the generalization performance. On the other hand, the condition dimn/ww]s. = wlog log(n))/ogge) (l)((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. We shall mention that Theorem 1 has an asymptotic nature as do not have an explicit control should be. This is due to the fact that the notions of Minkowski and Hausdorff dimensions are essentially asymptotic, which unfortunately prevents us from obtaining any truly non-asymptotic result. However, obtaining nonasymptotic results might be possible with further assumptions on the fractal dimension of the invariant measures and their supports.
how large
Theorem 1 enables us to access the rich theory of IFSs, where bounds on the Hausdorff dimension readily available, and connect them to statistical learning theory. The following result is direct corollary to Theorem I and [Ram06, Theorem 2. I] (see Theorem S2 in the supplementary document).
Corollary 1. Assume that the conditions of Theorem I hold. Furthermore, consider the recursion (6) and assume that ha are confinuously differentiable with derivatives Jn, that are a- o-Höller continuous for some O. Then, there exists constant M > 1 such that for sufficiently large n.:
8 log (n12
(1M(13
(R(W, - R(()) V | Pe Iga (og(ll),,w))l)dd (w)l)ddwwss. (w))
(1I)
with probability 1 2C over S T², W Pw]s.. where & == E. Pa log(p.) denotes the negative entropy of the mini-bater sampling scheme, || denotes the operator norm (with the E--norm being the underlying norm), and Jh, is the Jacobian of h2 defined in the notation section.
Note that the Hölder condition is mainly used to ensure that the invariant measure exists and the constant a does not directly interact with the bound. However, it might affect the rate of convergence to the invariant measure.
By this result, discover an interesting quantity, Em Ps Sae log( Jh, (w) () is. (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| [w]] enumeration of the mini-batches. Then, the overall quantity becomes
|| - s, and [S:) denotes the
Eu.w [log | - - Rs. (W).I)))
(12)
where the expectation is taken over the mini- index U E (1...., m2) with IPU =) 1) = ps. and W ~ HW We clearly observe that this term depends on (i) the algorithm choice through the form of h;, (ii) step-size y, (iii) batch-size through ma. (iv) problem geometry through V²R, and (v) data distribution through (wiss. We believe that such 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 applies to number of stochastic optimization algorithms that can be represented with an IFS and to a large class of losses that can be non-convex convex. It is controlled by the Hausdorff dimension of the invariant measure μwis,, which needs to be estimated. In the numerical experiments section, we will discuss how this quantity can be estimated from the dataset S,, 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(] Jn, (w)ll) with respect to the invariant measure Ww|s,,
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 Ja, [w)] which leads to analytical upper bounds on dimg
Note that thanks to [Ram06], we can allow state-dependent p.- p.(w); yet, we do not consider this option its application is not immediately clear.
7

---

As illustrative examples; in the following, we will consider the setting where we divide S, into m, mi mpalchh = nn/b batches with each batch having elements, and then we discuss how analytical estimates on the (upper) Hausdorff dimension dimm/wwss can be obtained for some particular problems including least squares, regularized logistic regression, and one hidden-layer networks. In the supplementary document, 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 2; (at, y:) and loss
E(w, z;) = (af to - yi)² /2 N1ww|
(13)
where À > 0 is regularization parameter.
Proposition 2 (Least squares). Consider the least squares problem (13). Assume the step-size r7 E (0, T where :: max, ||a:]| finite. Then, we have the following upper bound:
log (n/b)
dima/wwis. S log(1/(1 171))
(14)
Note that here l is only pseudo-Lipschitz [e(w, z.) I(w', 2i) S Li + |||| +|w''|)|| w'll for some L; > O, rather than globally Lipschitz. However, the conditions in Proposition 2 ensure that w will stay in a bounded region, in which case 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 dimn/w is decreasing both in 7j and 6. This behavior is not surprising: large 77 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 O. However, the decrement due to b does not automatically grant good generalization performance: since the algorithm becomes deterministic, the stability constant M in H2 can get arbitrarily large, hence the bound in Theorem 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 logarithmically increasing with n, which is compensated by the factor 1/n in Theorem 1. Nevertheless. we can take the batch-size in proportion with n (i.e., setting my to a constant value), in order avoid this logarithmic growth. We also note that the input dimension d potentially affects the term R, which forms the bound for the input data, and hence the input dimension will indirectly affect the generalization bound. 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.
v:), consider regularized logistic Regularized logistic regression. Given the data points 2; (a), regression with the loss:
(w, x) log (1 + exp (-vaa [-)a + ||
(15)
where À > 0 is regularization parameter. We have the following result.
Proposition 3 (Regularized logistic regression). Consider the regularized logistic regression (15). Assume the step-size n < 1/X and the input data is bounded, i.e. R max; ||a:l| < 2v X. We have:
log (n/b)
dimn/w s.. log(1/(1 n 1)(2)))
(16)
Next, we consider a non-convex formulation for robust regression (see e.g. [MBMI8]), with 21 (at, y:) and the loss
(ww, x4) == (y: (w, a:)) + A/| 1//
(17)
where À > 0 is a regularization parameter and p is non-convex function, assumed to be twice continously differentiable, where a standard choice is Tukey's 's bisquare loss defined as Prukey (t) =
1 - (1 - (z) for [t] S to. and PTakey (t) = for |t| 2 to (see e.g. [MBM18]), and exponential squared loss: Pexp (t) = 1 e -itf /oo where to 0 is tuning parameter (see e,g. [WJHZ13))
8

---

Proposition 4 (Non-convex formulation for robust regression). Consider the nnnt-convexfommulaaiin for robust regression (17). Assume the step-size 1) < X+ R2(2/ta) where R = max; ||a:|| < \tto/2 Then, we have the following upper bound for the Hausdorff dimension:
log (n/b)
dimguw S... log(11(1 nn + RR² ))
(18)
One hidden-layer neural network. Given the data points 24 = (a;, 4/). Let dg E Rd be the input and y4 Rn be the corresponding output, and let w, IR be the weights of the r-th hidden neuron of one hidden-layer network, and b, E IR is the output weight of hidden unit r. For simplicity of the presentation, following [ZMG199, DZPS19], we only optimize the weights of the hidden layer, i.e. w = [w][ w/ Wm! is the decision variable with the regularized squared loss:
f(w, 2)) = || 0:1 + 1|| 0: :-
E,_ m b, (w as).
(19)
where the non-line non-linearity a : R + R is smooth and X > 0 a regularization parameter.
Proposition 5 (One hidden-layer network). Consider the one hidden-laye -laeer network (19). Assume Then, we have the following upper bound for the Hausdorff dimension:
1. the step-size 1) < 2x
log (n//b)
dimHHWIs. log(1/(1 71A C)))
(20)
where C' = My M,Ilb|lo + (max, 110)1lo02 X, where R == max; ||ss]|, My == max; || Dill. and 02 [bio' (wf a.)a, b20' a.)a, ... bm ayma;)) )a:""
In Proposition 4, we assumed that C' uniformly bounded and X >> C for mathematical convenience. However, in general, C by its definition might increase in m and n that we do not expect that we can choose small À for large data sets and wide networks.
5 Experiments
Our aim now is to empirically investigate whether the bound Corollary is informative, in that is predictive of a neural network's generalization error. As the second term of this bound cannot be evaluated, we will assume that negligible and 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 neural network's 's generalization error. Note however that for complex models, such as modern neural networks, analytically bounding (()), 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 Jn, (w) = / 7/ 2 for simplicity we denote the inverse of (12) as the 'complexity": : R = 1/ mas ps fg log (1) Jh, (w)ll duwws, (w)]
To approximate the expectations, we propose the following simple Monte Carlo strategy:
R- R [1/(NwNoo)
Nw Nu log (IJJhe, (W))),
(21)
i=1 1==
where U, denotes i..dd random mini-batch indices that drawn without-rrellcemment from (I....,n) and W. ~ pwls- Assuming (8) is ergodic [DF99], we treat the iterates wi i.i.d. samples from pw s. for large k. hence, log([]Jnu (W+)Il) can be computed on these iterates, and (21) can be computed accordingly. Our implementation for computing [|Jhr, (Wa)ll for neural net- works with millions of parameters detailed in the supplementary document. Though the size of Jn, is very large in our experiments (>= 20M x 20M on average), our algorithm can efficiently compute the norms without constructing Jhu, (W+), by extending the approach presented in [YGKM20]. Our im- plementation is available at https: /ttp///ittttt/tt com/ wwuusuuuuuss.eeeeeee.uuoouuuuuuu www.iiiseskiiiee www.sseffaaaaall../.m/maaaaaaaae htte//aaaaaalggeeaaliiiiiie www.gaeeeeeaaiiiie.eaa
NNote that the first term of the bound in Corollary 1 suggests computing / R rather than R; however, both choices yield very similar results with high statistical significance.

---

te1
ReP FCN
CIFAR1O FCN
165
CIFAR10 CONV
SIGAN COMV
SVHN CONV
2 layer
0.98
Bibyer
Blbyer
16 layer
Complecty (N)
0.98
0.54
Binyer
0.12
7-leyer
100
2.0
0.500 0.525 Generaliztioo
Generalization error
Generakcation
Genennization enrOr
Generalicaiion
Figure 3: Estimates of R plotted against the generalization error ([training loss test loss)) for VGG11 and FCNs trained on CIFARIO, 10, SVHN and BHP with varying 17, b. The linear regression of best fit is plotted in red, where shading corresponds 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, significantly less than 0.001, indicating that highly likely that R and the generalization enror are positively correlated.
In Figure 3 we plot the estimates of R for a variety convolutional (CONV) and fully connected network (FCN) architectures trained on CIFARIO 10, SVHN and Boston House Prices (BHP). For the full details of the models, the hardware used, their run-time, and the
1e1
BHP FCN
25
2-aaer
2.0
Complexity (R)
1.5
convergence criterion used, see Section S7 in the supplement. The
plot demonstrates that R and generalization error are positively correlated and that this correlation is significant (p-value < 0.001)
for all model architectures. This provides evidence that the bound on the generalization error in Corollary is informative.
0.0
1e-2
To support our findings in Section 4 that the bound for the Hausdorff dimension dimg/Wwss, is monotonically decreasing in the step-size 7) we plot R against 17 in Figure for the networks trained on BHP in Figure 3. R decreases with increasing 17, 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 negative or positive correlation. Future work will further study this lack of correlation, particular to classification models.
Figure 4: Estimated R plot- ted against 17 for 2 layer FCN trained on BHP.
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 efficient methodology 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 SGD and its preconditioned variants, which unveil new links between generalization, algorithm parameters and the Hessian of the loss.
Our study does not have direct socictal impact it is largely theoretical. The limitation of our study is its asymptotic nature due to operating on invariant measures. Future work will address (i) obtaining nonasymptotic bounds in terms of the number of iterations k (ii) including the term of (12) as a regularizer to the optimization problem, which would be an alternative to the methods that aim to "decrease the intrinsic dimension" [ZQH* 18, BLG221].
Acknowledgements. MAE partially funded by CIFAR AI Chairs program, and CIFAR AI Catalyst grant, NSERC Grant [2019-0616 167]. MG's research is supported in part by the grants Office of Naval Research Award Number N00014-21-1-22 NSF DMS-2053485, NSF DMS-1723082 US's research is supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements l'avenir" program, reference from NSF ANR-19-P 19-P31A-0000 (PRAIRIE 31A Institute). LZ is grateful to the partial support and a Simons Foundation Collaboration Grant.
National Science Foundation (NSF) CCF-18 SCF-1814888,
10

---

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. (Cited on page 6.)
[AB09] Martin Anthony and Peter L Bartlett. Neural Network Learning: Theoretical Founda- tions. Cambridge University Press, 2009. (Cited on page 2.)
[AGNZ18] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. Proceedings of the 35th Interna- tional Conference Machine Learning, volume 80, pages 254 263..66..22 PMLR, 10-15 Jul 2018. (Cited on page 3.)
[AGZ21] Naman Agarwal, Surbhi Goel, and Cyril Zhang. Acceleration via fractal learning rate schedules. In International Conference Machine Learning, 2021. (Cited page 4.)
[Anc16] Andreas Anckar. Dimension bounds for invariant measures of bi-Lipschitz iterated function systems. Journal of Mathematical Analysis and Applications, 440(2):853-86) 2016. (Cited on pages 12 and 15.)
[BE02] Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2(Mar):499-527 2002. (Cited on page 6.)
[BLGŞ21] Tolga Birdal, Aaron Lou, Leonidas Guibas, and Umut Şimşekli. Intrinsic dimension, persistent homology and generalization in neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2021. (Cited on page 10.)
[Bog07] Vladimir Bogachev. Measure Theory, volume 1. Springer, 2007. (Cited on page 2.)
(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. (Cited on page 2.)
[DF99] Persi Diaconis and David Freedman. Iterated random functions. SIAM Review, 41(1):45-
76, 1999. (Cited on pages 5, and 9.)
[DR17] Gintare Karolina Dziugaite and Daniel Roy. Computing nonvaeuous generalization bounds for deep (stochastic) neural networks with many more parameters than train- ing data. Proceedings of the Thirty-Thite Conference on Uncertainty Artificial Intelligence (UAI), 2017. (Cited on page 2.)
[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. (Cited on page 4.)
[DZPS19] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parane paramereeateee neural networks. International Conference on Learning Representations, 2019. (Cited on page 9.)
[Elt90] John H Elton. A multiplicative ergodic theorem for Lipschitz maps. Stochastic Processes and their Applications, 34(1):39 47, 1990. (Cited on page 5.)
[EM15] Murat Erdogdu and Andrea Montanari. Convergence rates of sub-sampled Newton methods. Advances in Neural Information Processing Systems, 28:3052-3060, 2015. (Cited page 5.)
[Fa197] Kenneth J. Falconer. Techniques in Fractal Geometry. Wiley, 1997. (Cited on page 2.)
[Fa104] Kenneth Falconer. Fractal Geometry: Mathematical Foundations and Applications. Wiley, 2004. (Cited on pages 2, 3, and 4.)
[FST06] Ai Hua Fan, Károly Simon, and Hajnal R. Tóth. Contracting average random IFS with repelling fixed point. Journal of Statistical Physics, 122: 199.9, 2006. (Cited on page 4.)
11

---

[FW09] De-Jun Feng and Yang Wang. On the structures of generating iterated function systems of Cantor sets. Advances Mathematics, (2((6):164-1188) 2009, (Cited on page 2.)
[GOP19] Mert Gürbüüzalaban, Asuman Ozdaglar, and Pablo A Parrilo. Convergence rate of incremental gradient and incremental Newton methods. SIAM Journal on Optimization, 29(4):2542-2555 2565, 2019. (Cited on page 5.)
[GOP21] Mert Gürbüzbalaban, Asu Ozdaglar, and Pablo A Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming. 186(1):49 84, 2021. (Cited on page 5.)
[G$Z21] Mert Gürbüzbalaban, Umut Şimşekli, and Lingjiong Zhu. The heavy-tail phenomenon SGD. In International Conference on Machine Learning, 2021. (Cited on page 3.)
[Hau18] Felix Hausdorff. Dimension und äusseres Mass. Mathematische Annalen, 79(1-2):157- 179, 1918. (Cited on page 4.)
[HJTW21] Daniel Hsu, Ziwei Ji, Matus Telgarsky, and Lan Wang- Generalization bounds via distillation. In International Conference on Learning Representations, 2021. (Cited on page 3.)
[HS74] Morris W. Hirsch and Stephen Smale. Differential Equations, Dynamical Systems, and Linear Algebra. Academic Press, 1974. (Cited on page 3.)
[HŞKM21] Liam Hodgkinson, Umut Şimşekli, Rajiv Khanna, and Michael W Mahoney. Gen- cralization properties of stochastic optimizers via trajectory analysis. arXiv preprint arXiv:2108.00% 00781, 2021. (Cited on page 6.)
[HSS12] Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Overview of mini-batch gradient descent. Neural Networks for Machine Learning, 575, 2012. (Cited on page 5.)
[JR08] Joanna Jaroszewska and Michat Rams. On the Hausdorff dimension of invariant measures of weakly contracting average measurable IFS. Journal of Statistical Physics, 132:907, 2008. (Cited on page 4.)
[KB15] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015. (Cited on page 5.)
[Li17] Xi-Lin Li. Preconditioned stochastic gradient descent. IEEE Transactions Neural Networks and Learning Systems, 29(5):145-11666 2017. (Cited on page 2.)
[LMA21] Zhiyuan Li, Sadhika Malladi, and Sanjeev Arora. On the validity of modeling SGD with stochastic differential equations (SDEs). arXiv preprint 1xXi:22022.12477 2021. (Cited page
[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 2019. (Cited on page 3.)
[MBM18] Song Mei, Yu Bai, and Andrea Montanari. The landscape of empirical risk for nonconvex losses. Annals of Statistics, 46(6A))2747-27774 2018. (Cited on page 8.)
[MS02] Józef Myjak and Tomasz Szarek. On Hausdorff dimension invariant measures arising from non coneortatttivve iterated function systems, Annali di Matematica Pura ed Applicata, 181:223-237, 2002. (Cited on page 4.)
[MSS19] Eran Malach and Shai Advances Neural Information Processing Systems (NeurIPS), volume 32, 2019. (Cited page 4.)
Is deeper better only when shallow is good?
[MT10] John Mackay and Jeremy Tyson. Conformal Dimension: Theory and Application, volume 54. American Mathematical Society, 2010. (Cited page 6.)
12

---

[NBMS17]
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Ex- ploring generalization deep learning. In Advances Neural Information Processing Systems (NIPS), pages 5947-5956, 2017. (Cited on page 2.)
[NcGR19] Thanh Huy Nguyen, Umut Şimşekli, Mert Gürbüzzalaban, and Gaël Richard. First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise. In Advances in Neural Information Processing Systems, pages 273-283, 2019. (Cited on page 3.)
[NSB02] Matthew Nicol, Nikita Sidorov, and David Broomhead. On the fine structure of stationary measures in systems which cntract-on-averagee Journal of Theoretical Probability, 15:715-730, 2002. (Cited on page 4.)
[Pes08] Yakov B Pesin. Dimension Theory in Dynamical Systems: Contemporary Views and Applications. University of Chicago Press, 2008. (Cited on pages 6, 1, and 2.)
[Qia99] Ning Qian. On the momentum term in gradient descent learning algorithms. Neural Networks, 12(1):145-11, 1999. (Cited page 5.)
[Ram06] Michal Rams. Dimension estimates for invariant measures of contracting-on-avere iterated function systems. arXiv preprint math/0606420, 2006. (Cited on pages and 2.)
[RKM16]
Farbod Goossa-Khooasani and Michael W Mahoney. sab-sa Newton methods II: Local convergence rates. arXiv preprint 1601.0400..443 2016. (Cited page 4.)
[Rog98] Claude Ambrose Rogers. Hausdorff Measures. Cambridge University Press, 1998. (Cited on page 4.)
[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 generalization error. In International Joint Conference on Artificial Intelligence, pages 2839-2844444 2846, 2020. (Cited on page 3.)
[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.
(Cited page 3.)
[Saz00] Tomasz Sazarek. The dimension of self-similar measures. Bulletin of the Polish Academy of Sciences. Mathematics, 48:293-202, 2000. (Cited on page 4.)
[$GN+19 19] Umut Şimşekli, Mert Gürbüzbalaban, Thanh Huy Nguyen, Gaël Richard, and Levent Sagun. On the heavy-tailed theory of stochastic gradient descent for deep neural networks. arXiv preprint arXiv: 3ett::/912.001111 2019. (Cited on page 3.)
[SHTY13] Mahito Sugiyama, Eiju Hirowatari, Hideki Tsuiki, and Akihiro Yamamoto. Learning figures with the Hausdorff metric by fractals-towardk computable binary classification. Machine Learning, 90(1):91-126, 2013. (Cited page 4.)
[SSBD14] Shai Shalev-Shwart and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. (Cited on page 2.)
[SSDE20] 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. (Cited on pages 3, and 8.)
[$SG19] Umut Şimşekli, Levent Sagun, and Mert Gürbüzbalaban. A tail-index analysis of stochastic gradient noise deep neural networks. In International Conference on Machine Learning, pages 5827-5837 2019. (Cited page
[$ZTG20] Umut Şimşekli, Lingjiong Zhu, Yee Whye Teh, and Mert Gürbüizbalaban. Fractional underdamped Langevin dynamics: Retargeting SGD with momentum under heavy-tailed gradient noise. arXiv preprint arXiv:20022.55685, 2020. (Cited page 3.)
13

---

[Ver18] Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science, volume 47. Cambridge university press, 2018. (Cited on page 5.)
[Wai19] Martin Wainwright. Hiigh-Dimensiona Statistics: Non-Asymptotic Viewpoint, volume 48. Cambridge University Press, 2019, (Cited page 10.)
[WJHZ13] Xueqin Wang, Yunlu Jiang, Mian Huang, and Heping Zhang. Robust variable selec- tion with exponential squared loss. Journal of the American Statistical Association, 108(502):632-66 643, 2013. (Cited page 8.)
[XR17] Aolin Xu and Maxim Raginsky. information-theorette analysis of generalization capa- bility of learning algorithms. In Advances in Neural Information Processing Systems (NIPS), pages 2524-2533, 2017. (Cited on page 6.)
[Yai19] Sho Yaida. Fluctuation disisppptioisiiiiiinnnnn relations for stochastic gradient descent. In Interna- tional Conference on Learning Representations, 2019. (Cited on page 3.)
[YBVE20] Lu Yu, Krishnakumar Balasubramaniaan, 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. 200.000000007944 2020. (Cited on page 2.)
[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. (Cited on pages 9 and 5.)
[ZBH* 17] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Under- standing deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017. (Cited on page 2.)
[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. (Cited on pages 9 and 3.)
[ZQH+ 18] Wei Zhu, Qiang Qiu, Jiaji Huang, Robert Calderbank, Guillermo Sapiro, and Ingrid Daubechies. LDMNet: Low dimensional manifold regularized neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2743-2751, 2018. (Cited on page 10.)
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the Least Squares part of Section 4, the end of the Section 5 (Experiments), and Conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Conclusion.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See supplemen- tary material.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section S7 in the Supplementary Document
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] See Section S7 in the Supplementary Document
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] The PyHessian paper, with the only external codebase we used, is cited.
(b) Did you mention the license of the assets? [N/A] All code used was released in an open-source manner using an MIT license.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "mFmQaPhOF6", "reviewer": "Reviewer_PfjU", "summary": "{\\bf Summary:} The authors study generalization bounds for stochastic gradient algorithms by studying the invariant distribution of the algorithm. The bounds involve the Hausdorff dimension of the invariant measure, which the authors proceed to bound in several applications in terms of hyperparameters of the algorithm (step-size, batch-size, batch-selection mechanism), parameters of the application (Hessian of risk function, data distribution) and an {\\em integral} quantity of the invariant distribution, which can be estimated more easily.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "{\\bf General assessment:} The article is well-written and the topic is interesting. It bridges topics in fractal geometry and stochastic optimization and generally does both fields justice. While it is on the theoretical side, the results are interesting enough that I believe they merit inclusion in NeurIPS21. I am not quite familiar enough with the surrounding literature to assess the novelty of the results perfectly, but my impression is that the progress made in this paper is sufficient to be included. \n\nMy biggest concern is that the authors obtain an error bound which cannot be evaluated and is as such not useful in practice at this point. The invariant which the authors study is positively correlated with generalization behavior, but only explains the first order correction to an error bound, not the leading order term. Furthermore, the invariant measure is only relevant asymptotically, and the authors do not obtain rates (which they claim as a subject of future work).\n\nNevertheless, I believe that the analysis is quite interesting and sheds light on the properties of stochastic optimization algorithms, which may open the door for further advances.\n \n\n{\\bf Specific comments:}\nThere are a few aspects of the article that should be improved before publication, in particular in Corollary 1 and Proposition 5. I am not entirely convinced by the numerical results, but might be missing something. If the authors can make such improvements, I would be in favor of publication.\n\n* l 147: The supremum should be taken for $s\\geq 0$ to allow Hausdorff dimension zero without having to discuss the supremum of the empty set.\n\n* l 180: SGD or Newton's method have no 'memory' and are Markov processes, as is clear from the IFS representation formula. SGD with momentum, ADAM etc.\\ have a memory of previous states, unless they are viewed on a higher-dimensional phase space. Could the authors briefly comment on how their results extend to this case, since even the appendix avoids this case.\n* l 185: I am not sure this is a more realistic set-up -- typically, we shuffle the data set between epochs, so that the probability of getting the exact same batch twice is pretty low, and the probability of seeing the same batch in consecutive time-steps would be zero in practice (except between epochs).\n* l 187: I believe the authors are introducing the new notation $p_i$ here, not making a condition on whether or not the iteration step can be re-written in a certain way.\n* l 190: Again, this is not the realistic setting, since the probability of seeing a batch would depend on whether this batch has  already been used during the epoch. Uniform sampling is not the default option in practice, since we do not repeat the same batch twice in a row. In Corollary 1, the implication is that $p_i$ is constant in time.\n* l 239: Is $n$ needed in the definition of $\\mathfrak G$?\n* l 240: I assume that $\\mathbb P = \\mu_{W|S_n}$ here and supposed to hold uniformly over $S$ and $n\\in\\mathbb N $, at least almost surely? This is not clear at first reading, please explain.\n* l 241: This condition looks like a quantitative bound on the independence of the sigma algebras $\\mathfrak F, \\mathfrak G$. I understand that space is limited and that references are given, but a few more words on the intuition would be appreciated.\n* l 251: Any quantitative estimate on how large $n$ has to be?\n* l 258: The decay of $\\log(\\log n) / \\log n$ cannot be considered as 'very rapid'. The condition is rather similar to a lower bound on the upper Hausdorff dimension of $\\mu_{W|S_n}$. Do the authors have an idea under which conditions, $\\overline{dim}_H (\\mu|_{W|S_n})\\to 0$? This seems to be the case in e.g. strongly convex problems or problems with a PL property and a unique minimizer (with small enough learning rate and noise which vanishes at the minimum), but unrealistic in the context of deep learning, where the set of minimizers is high-dimensional.\n* l 262: It is unclear how $\\alpha$ and the Hölder constant enter in the result. I suspect the constant $M$, but if this could be mentioned (or even quantified), I would be grateful. This seems to be important in the discussion in l 305 as well.\n* l 263: $h_i' = J_{h_i}$, I believe. (Also Theorem S.2 in the appendix)\n* eq (11): Ent looks like an operator, not a variable. The upright typesetting of a three letter name is confusing here and should be changed.\n* eq (11): Does the condition (8) guarantee that the first term under the square root is positive? Otherwise, the expression under the square root is negative for large $n$ (once $\\log n$ is large enough). Can the authors comment on this more explicitly, and whether (8) has geometric implications for the objective functions in an SGD algorithm.\n* eq (11): It seems that if $h_i$ is almost constant or very rough (so that $\\log\\|J_{h_i}\\|$ is very large), then the first term drops out of the bound. I assume this is compensated for by the constant $M$? Even with a global Hölder bound, I do not see why the first term couldn't be made arbitrarily small. Is this reflected in the geometry of the invariant measure somehow?\n* l 266 (or notation section): The operator norm depends on the norm of the underlying spaces. I assume this is the Euclidean norm everywhere in the article, but this might be worth noting (also for eq (7) and condition H3). \n* Section 4: All loss functionals seem to be considered with an additional regularizer. Could the authors discuss\n\\begin{itemize}\n* How their estimates relate to the estimates that would be obtained directly from regularization for minimizers (or e.g.\\ low loss functions)\n* How the regularization is incorporated in the time-stepping algorithm (e.g.\\ in every batch, or as its own 'batch' which may be chosen stochastically, ...)\n\\end{itemize}\n* l 299: $\\ell(w)$ is not defined, strictly speaking. It may be advisable to denote $\\nabla_w \\ell(w,z_i)$ to be particularly clear.\n* l 302: The bound is decreasing in $\\eta$, but \n\\[\n\\lim_{\\eta\\to 0^+} \\frac{\\log(n/b)} {\\log\\left(\\frac1{1-\\eta \\lambda}\\right)} = \\frac{\\log (n/b)}{\\lim_{z\\to 1^+} \\log (z)} = +\\infty.\n\\]\nAlso in the gradient flow limit, the algorithm becomes deterministic. Why do the authors expect this kind of behavior/a continuous invariant measure, rather than a single point and such different behavior compared to $n=b$? This seems to be in line with Figure 1, but not Figure 2. Is the scale the same in all plots in Figure 2? The 'continuous' behavior seems to still result from fairly large step size. Would the authors expect a double descent-like phenomenon?\n* l 311: If $m_b$ is taken to be constant over large data sets, the benefits of SGD in terms of performance decrease. Since the dependence on $n/b$ is only logarithmic, it seems that a tradeoff with moderately large/moderately growing $m_b$ would be reasonable.\n* l 318: better: 'that $\\eta<1/\\lambda$ and that the data...'\n* l 319: Unlike logistic regression, this loss seems to force $y_i = \\langle w, a_i\\rangle$ instead of having the correct sign and allowing variability in magnitude between data points. This seems more in line with a least squares regression than logistic regression. Could the authors comment on why they dub this a 'nonconvex formulation of logistic regression' or give a reference?\n* l 322: Should this be $|t|^2/t_0^2$ in $\\rho_{exp}$?\n* eq (17) and Proposition 4: Why was $\\lambda$ changed to $\\lambda_r$ comparing to previous notation?\n* l 331: 'smooth' is a very imprecise term here. How smooth, and are quantitative global bounds required? It seems that $\\sigma \\in W^{2,\\infty}$ or $\\sigma'' \\in L^\\infty$ might be natural?\n* Proposition 5: $v_i$ seems to be a matrix, which is very confusing notation. Commas between the columns would make the expression easier to read. What norm do the authors use here -- is this the element-wise $\\ell^\\infty$-norm or an operator norm? If $v_i$ is meant to be a (very long) vector, please be more explicit in the description.\n* Proposition 5: This seems to be written up backwards, with multiple 'where ...' explanations following each other. Can this be rewritten in a more intuitive way? If necessary, the precise statement could be postponed to the supplementary material.\n* Proposition 5: $\\hat y_i$ is the output of the neural network. $v_i$ depends on the weights of the network. How are $M_y$ and $\\|v_i\\|$ controlled during the iteration/is it sufficient to consider bounds at initialization/are there a priori estimates for the invariant measure/...?\n* Proposition 5: Since $\\lambda$ has to be lower bounded, can the authors discuss the dependence of $C$ on $m$ and $n$? Can we e.g.\\ choose small $\\lambda$ for large data sets and wide networks?\n* l 334: Which norm of $\\sigma''$ is taken here?\n\n* l 343: The claim that a numerical method is developed is very generous, as the authors essentially do the natural thing and do not provide error estimates. The non-trivial idea seems to be in how to find the operator norm of a large matrix, which is barely discussed in the article and the supplementary material. However, I would question whether 200 {\\em consecutive} iterates of SGD can be considered as iid samples from the invariant distribution. This seems like a too short time window (or too little time between the individual iterates). I would encourage the authors to rerun the simulations or discuss why this approach is valid.\n* l 345: $R$ was used in a different way above. Please stay consistent in notation and don't switch like this.\n* l 345: The error bound depends on $\\sqrt{R}$, which is only approximately linear if the second term in the error bound is fairly large compared to $R$, which seems to be true in all except the first plot (the total generalization error is much large than the variability within the graph). I assume that this is why the authors chose to consider $R$ instead of $\\sqrt R$. \n\nHowever, this may suggest that the authors closely investigate a term which is not the main contributor to the generalization error, much like estimating the first order term of a Taylor series, but not the term of zeroth order. Could the authors explain why their results are informative for consideration in practice? \n\nUsing a Taylor approximation of the square root $\\sqrt{Q+\\eps} \\approx \\sqrt Q + \\frac1{2\\sqrt{Q}}\\eps$, can the explicit error bound be fit quantitatively with reasonable accuracy, where $\\eps$ is the dimension of the invariant measure (centered at average) and $Q$ is the generalization error in the middle of the domain?\n* l 362: The authors claim the bound of Corollary 1 to be informative, but argue in l 338 that the bound cannot be evaluated, which makes it not informative. They furthermore design their method to only evaluate part of the bound, which contributes less to the overall error. While I find the bound interesting, I do not believe it to be useful in practice for this very reason (without further improvements), and I find the formulation here misleading.\n* l 363: In convex models where a unique minimizer exists, the Hausdorff dimension of the invariant measure should be zero if the time-step size is below $2/L$, where $L$ is the Lipschitz-constant of the gradient of the objective function. In unregularized overparametrized models, there should be a manifold of dimension $m-n$ on which the empirical loss vanishes exactly, and any measure which is supported on this manifold is invariant under SGD dynamics since the data labels are matched exactly. As outlined above, I do not quite see why the complexity should decrease with $\\eta$ (at least below a certain threshold), and I believe a more thorough discussion is required here, which might not be possible within the framework of this article. Is there some intuition the authors can provide for the continuous time limit or small step sizes? The simplified picture presented here does not seem to do the complexity of the situation justice, as the authors acknowledge.\n\n\n\n\n* l 599: The authors did not introduce SOSC or ROSC. Does the result involve $\\alpha$ in any quantitative way?\n* l 622: The authors suggest here that $H$ is fixed, but consider $H$ related to the Jacobian below. I am not sure which Jacobian is considered here: The gradient of the objective function (which would make $H$ rank one) or its Hessian (the Jacobian of the gradient). In either case, the ideas are only compatible for quadratic objective functions.\n* Algorithm 1: Gradient of $f$? and $g_\\theta = g_w$.\n\n\n* l 729: The proof seems to be correct, as far as I can tell, but it is challenging to read. It would be helpful if it could be broken up into a series of steps, and/or if the authors could provide an outline and heuristic before the technical details. \n\nMy understanding is that the key argument is a concentration inequality/tail bound, and that the Hausdorff dimension appears due to a logarithm of the covering numbers. The major technical complications seem to stem from the randomness in $S$. Am I missing something central with this interpretation?\n\n* l 737: I believe that a countable subsequence in $\\delta$ must be selected. This can potentially be avoided here due to monotonicity, but should be discussed.\n* l 745: It would be helpful if the authors could say a little more about the distribution $\\mathbb P$ and argue why the sets they consider are measurable under this distribution. As the choice of $A_{S_n,k}$ is highly non-unique over $S$, it would surprise me if there weren't selections for which the probabilities are not well-defined (but I do imagine that a measurable selection can be found -- Chapter 14 in {\\em Infinite dimensional analysis} by Aliprantis and Border is probably a good place to look)\n* eq (S39): Is this used below? EDIT: I found it in l 763, significantly later. Please refer back to (S39) for the definition or make the definition closer to where the set is needed.\n\n* l 782: Norms missing in the equation above\n* eqs (S59), (S60): I think the determination which term is larger can be made explicitly due to the choice of $\\eta$. $\\gamma_i>0$ since it is the minimum of positive terms... The condition $\\eta < \\frac{1}{R^2+\\lambda}$ was already made.\n* l 783: Do you need to divide by $\\|w\\|$ in the equation above?\n* l 785: There is  $\\binom{n}{b}$ instead $n/b$, which is used in (S63). This should be cleared up. The confusion seems to be a consequence of being able to select either {\\em any} subset of size $b$ or only disjoint batches.\nThe estimates for the two types of batched SGD are very different. Is it reasonable to expect that they would be so different?\n* l 812: The output is {\\em only} bounded a priori since the final layer is fixed at initialization. This needs to be pointed out.\n* l 814: Missing space.\n\nI only skim read results in the supplementary material and not in the main text.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "the authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "jCGpfB8TumQ", "reviewer": "Reviewer_5gBo", "summary": "The authors study the generalization error of iterative stochastic optimization algorithms whose iterates form an ergodic Markov chain. Particular examples include SGD and stochastic Newton methods for a large class of loss functions and models. The generalization error of these algorithms is upper-bounded by the Hausdorff of the invariant measure of the associated Markov chain. Bounds on this dimension are then given for some common example models and loss functions. Statistical correlation between the generalization error of deep neural networks and a quantity in the derived bounds is established numerically, but is only proven for a single layer model.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and relatively easy to follow, although the notation is a bit heavy for a paper of this length. The results are interesting and I appreciate the various examples given as they provide intuition for what the bounds looks like when actually implemented in practice. I would like to have seen at least one of the examples where an explicit bound is given implemented numerically so the theory can be verified. It would also give an idea of how tight the bounds are since no lower bounds are proven. A major component missing from this work, however, is a discussion about the ramification of these bounds for various model/algorithms/data distributions. The authors say that their bound is able to capture specifics of the model, the algorithm, and the problem geometry (eq 11) however they never discuss this information specifically. How do two different models compare under a fixed data, loss function, and algorithm? How do two different loss functions compare under fixed data, model, and algorithm? How do two different algorithms compare under fixed data, loss function, and model? Etc.? Furthermore what do these bounds suggest for improving current optimization algorithms or developing new ones? Do they suggest any ways of tuning hyperparamters for optimal generalization? I think, at least partial answers to some of these questions should be given in discussion. Otherwise the paper feels as if it simply does math for its own, which is fine, but is not necessarily to NeurIPS.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe there are no potential negative societal impacts of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "MdCLsTZCjgl", "reviewer": "Reviewer_iGxg", "summary": "The paper gives novel generalization bounds for models trained with SGD (or variants of SGD) based on the Hausdorff dimension. The main contribution is Theorem 1 which shows, under certain assumptions, that for a general class of models, their generalization bound after training with SGD can be bounded by a term that depends on the Hausdorff dimension of the stationary distribution which the stochastic process converges to. Next, several interpretations of this bound are given for simple models like least squares, and 2-layer NN. Finally, an experiment shows on several datasets that there is a correlation between the generalization capacity of NN and a certain term in the given bound.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper provides a novel view on generalization of models trained by stochastic algorithms, specifically SGD and its variants. This perspective is very interesting and I think this is a good contribution. In Section 4 the authors give more concrete examples of how these bounds are translated for standard models such as regularized linear models with square loss and two-layer neural networks (where only the first layer is trained). Finally, the experiments in Section 5 give a good motivation for why this generalization bound is tighter than known bounds. \n\nClassical generalization bounds on neural networks are exponential in the network’s depth, and the bounds presented here have the potential of being dependant on other parameters (e.g. a bound on the Jacobian’s norm) which may not be necessarily exponential in the depth. I think this makes the bound important for our understanding of how neural networks really generalize.\n\nThere are a couple of minor issues which I would be happy to see the author’s response:\n\n1) In the least-squares and logistic regression bounds, there seems to be no dependence on the input dimension (assuming that the inputs are bounded). This is a bit weird, to have the same bound for all input dimensions, I think the authors should explain this in more detail.\n\n2) Suppose that SGD converges to some minimum over the dataset (either local or global), wouldn’t the distribution \\mu_W be constant? Since the gradient w.r.t, all the data points in the train set are zero? In what cases this distribution is non-constant, or am I missing something?\n\n3) Under what conditions can we ensure that the distribution \\mu_W converges for standard models such as linear predictors or neural networks? i.e. what are the conditions on the model and data such that Eq. (7) and (8) are satisfied? I think elaborating on this would give a better understanding of what is required from the data/model in order for the stochastic process to converge to some distribution.\n\n4) Does \\alpha play a role in Corollary 1? Does the corollary hold even when \\alpha is extremely small?\n\nTo conclude, I think the contribution of this paper is interesting and novel. I recommend acceptance.\n\n--------Post rebuttal comment--------\n\nI read the author's response and decided to maintain my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "47mtbb_F-9L", "reviewer": "Reviewer_gFd8", "summary": "The authors give a general generalization bound for stochastic optimization algorithms, depending on the Hausdorff dimension of the invariant measure. This bound takes into account the dataset and training algorithm, and draws on theory on fractal dimensions and random iterated function systems in dynamical systems. The authors link this bound to quantities that can be estimated from running the algorithm in question - namely an expected logarithm of norm of Jacobian. They specialize the theory for least squares (SGD & stochastic Newton), logistic regression, SVMs, and 1-hidden-layer neural networks. They present experiments showing that this quantity does in fact correlate with with generalization performance for fully-connected and convolutional neural networks trained on CIFAR10 and SVHN.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Generalization in modern machine learning (with overparameterized deep nets) remains a mystery, and this paper provides some new ideas to tackle the problem. The generalization bound given in the paper is applicable to a wide range of stochastic optimization algorithms, and this is illustrated with corollaries of the main theorem. Moreover, experiments suggest that the proxy quantity they defined does indeed correlation with generalization performance in practice for neural networks. I am enthusiastic about the introduction of dynamical systems methods (which are not well-known in ML); this seems to be a promising technique to better understanding generalization.\n\nThe closest work is [ŞSDE20] which needs to assume that the trajectory is well-approximated by a SDE and instead control generalization error with the Hausdorff dimension of trajectories; this work instead considers the discrete-time process instead and bounds generalization error based on Hausdorff dimension of invariant measures, and potentially works in more general circumstances.\n\nHowever, I am concerned about some technical issues.\n\n(1) The definition of $\\mathfrak G$ in H2 does not make sense to me. As defined, $1\\{w\\in N_\\beta(A)\\}$ is a deterministic value, not a random variable depending on $S\\in \\mathcal Z^\\infty$. Also, why is $\\{\\alpha(S,n)\\in J_m(\\rho)\\}$ in $\\mathfrak G$?\n\nCan the authors elaborate on the definition and dependence on M? Assumption H2 is technical and I don't understand what it means intuitively, or the connection to algorithmic stability. Why is this a reasonable assumption, and what kind of bound does one expect to be able to obtain for M? Importantly, why is M finite for reasonable algorithms? Intuitively, how would M vary as we change the amount of \"stochasticity\" (through step size, batch size) in the algorithm? As the authors explain, as the algorithm becomes deterministic, M can blow up, so wouldn't R (the complexity metric) be a poor metric for generalization in the regime of low noise?\n\n(2) In the propositions, the Hausdorff dimension is bounded in terms of $\\log(n/b)$. However, examining the proof, the bound is in terms of $\\log(m_b)$ where $m_b=\\binom nb$, so this gives a bound of $b\\log n$. Such linear dependence on batch size would seem to be a serious shortcoming.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a strong paper, in which the authors prove generalization bounds for iterative stochastic algorithms based on the Hausdorff dimension of the invariant measure. The bounds are specialized for several applications like least squares (SGD & stochastic Newton), logistic regression, SVMs, and 1-hidden-layer neural networks. Some supporting empirical verification is also included. The proofs use tools from dynamical systems which are not so common in this are and seem like a promising lens on generalization.





Decision: Accept (Spotlight)