Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

The 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.

However, I am concerned about some technical issues.

(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$?

Can 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?

(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.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.
limitations_and_societal_impact: I believe there are no potential negative societal impacts of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

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. 

My 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).

Nevertheless, 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.
 

{\bf Specific comments:}
There 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.

* 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.

* 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.
* 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).
* 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.
* 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.
* l 239: Is $n$ needed in the definition of $\mathfrak G$?
* 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.
* 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.
* l 251: Any quantitative estimate on how large $n$ has to be?
* 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.
* 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.
* l 263: $h_i' = J_{h_i}$, I believe. (Also Theorem S.2 in the appendix)
* 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.
* 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.
* 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?
* 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). 
* Section 4: All loss functionals seem to be considered with an additional regularizer. Could the authors discuss
\begin{itemize}
* How their estimates relate to the estimates that would be obtained directly from regularization for minimizers (or e.g.\ low loss functions)
* 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, ...)
\end{itemize}
* 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.
* l 302: The bound is decreasing in $\eta$, but 
\[
\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.
\]
Also 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?
* 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.
* l 318: better: 'that $\eta<1/\lambda$ and that the data...'
* 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?
* l 322: Should this be $|t|^2/t_0^2$ in $\rho_{exp}$?
* eq (17) and Proposition 4: Why was $\lambda$ changed to $\lambda_r$ comparing to previous notation?
* 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?
* 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.
* 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.
* 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/...?
* 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?
* l 334: Which norm of $\sigma''$ is taken here?

* 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.
* l 345: $R$ was used in a different way above. Please stay consistent in notation and don't switch like this.
* 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$. 

However, 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? 

Using 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?
* 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.
* 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.




* l 599: The authors did not introduce SOSC or ROSC. Does the result involve $\alpha$ in any quantitative way?
* 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.
* Algorithm 1: Gradient of $f$? and $g_\theta = g_w$.


* 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. 

My 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?

* 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.
* 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)
* 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.

* l 782: Norms missing in the equation above
* 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.
* l 783: Do you need to divide by $\|w\|$ in the equation above?
* 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.
The estimates for the two types of batched SGD are very different. Is it reasonable to expect that they would be so different?
* l 812: The output is {\em only} bounded a priori since the final layer is fixed at initialization. This needs to be pointed out.
* l 814: Missing space.

I only skim read results in the supplementary material and not in the main text.

limitations_and_societal_impact: the authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 

Classical 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.

There are a couple of minor issues which I would be happy to see the author’s response:

1) 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.

2) 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?

3) 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.

4) Does \alpha play a role in Corollary 1? Does the corollary hold even when \alpha is extremely small?

To conclude, I think the contribution of this paper is interesting and novel. I recommend acceptance.

--------Post rebuttal comment--------

I read the author's response and decided to maintain my score.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

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)