On the generalization of learning algorithms that do not converge
Authors: Nisha Chandramoorthy
Andreas Loukas
Khashayar Gatmiry
Stefanie Jegelka
Venue: NeurIPS 2022 Accept (2022)
Keywords: deep learning theory
generalization
algorithmic stability
statistical learning theory

Abstract: Generalization analyses of deep learning typically assume that the training converges to a fixed point. But, recent results indicate that in practice, the weights of deep neural networks optimized with stochastic gradient descent often oscillate indefinitely. To reduce this discrepancy between theory and practice, this paper focuses on the generalization of neural networks whose training dynamics do not necessarily converge to fixed points.  Our main contribution is to propose a notion of statistical algorithmic stability (SAS) that extends classical algorithmic stability to non-convergent algorithms and to study its connection to generalization. This ergodic-theoretic approach leads to new insights when compared to the traditional optimization and learning theory perspectives. We prove that the stability of the time-asymptotic behavior of a learning algorithm relates to its generalization and empirically demonstrate how loss dynamics can provide clues to generalization performance. Our findings provide evidence that networks that ``train stably generalize better'' even when the training continues indefinitely and the weights do not converge.

On the generalization of learning algorithms that do not converge
Nisha Chandramoorthy
Andreas Loukas Prescient Design Genentech, Roche andreas www.kllookkc..e....oooooo com
Institute for Data, Systems and Society Massachusetts Institute of Technology nishac@mit edu
Khashayar Gatmiry
Stefanie Jegelka
Electrical Engineering and Computer Science Massachusetts Institute of Technology gatmiry@mit.ent edu
Electrical Engineering and Computer Science Massachusetts Institute of Technology stef je0it..... fedmit.edr edu
Abstract
Generalization analyses of deep learning typically assume that the training verges to a fixed point. But, recent results indicate that practice, the weights deep neural networks optimized with stochastic gradient descent often oscillate indefinitely. To reduce this discrepancy between theory and practice, this paper focuses the generalization of neural networks whose training dynamics do not necessarily converge to fixed points. Our main contribution is to propose a notion of statistical algorithmic stability (SAS) that extends classical algorithmic stability to non-convergent algorithms and to study its connection to generalization. This ergodic-theoretic approach leads optimization and learning theory perspectives. We prove that the stability of the time-asymptotic behavior of learning algorithm relates to its generalization and empirically demonstrate how loss dynamics can provide clues to generalization performance. Our findings provide evidence that networks that "train stably gener- alize better" even when the training continues indefinitely and the weights do not converge.
insights when compared to the traditional
Introduction
It is common practice that when the training loss of neural networks converges close to some value, the learning algorihm--typccllly some variant Stochastic Gradient Descent (SGD)-1) is terminated. Perhaps surprisingly, recent works indicate that the network function termination time typically not fixed point of the learning a algorithm: if run longer, the gradient norm does not vanish and the learning algorithm outputs functions with significantly different parameters [Cohen al.) 2021 Zhang et al. 2022 Lobacheva et al. 2021]. This observation stands in contrast to common generalization analyses that assume convergence of the training algorithm fixed point. It also raises the question of when (and why) non-convergent learning algorithms should be expected to generalize.
Standard approaches for obtaining generalization bounds find ways to bound the complexity measure of the function class expressible by neural network in data-inde iata-independent e.g., [Vapnik] [999] Bartlett et al. 2017 Neyshabur et al. 22018 Golowich et al. 2018 Bartlett et al. 2019 Arora et al. 2018] datendependent manner, e.g., [vo Luxburg and Bousquet 2004 Xu and Mannor 2012 Sokolić et al. 2017]. Nevertheless, even with recent technical improvements, by and large these
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

approaches do not explicitly account for the relationship between generalization and the dynamics of the learning algorithm.
different approach to generalization analysis yields algorithn-depenndnt bounds by connecting the generalization performance of the trained network to the stability of the training data perturbations [Bousquet and Elisseefft, 2002 Feldman and Vondrak 2018 Kuzborskij and Lampert [0018] Bousquet al. [020 Zhang et al. 2021b Rakhlin [006]. A key claim of these works has been that networks that are trained last generalize better. This claim, though intuitively meaningful, hinges on the premise of convergent algorithm, which deviates from the observed behavior of deep neural network training. Further work has been done for settings where the algorithm provably converges to a fixed point, such as two-layer overparameterized networks, deep linear networks, certain matrix factorizations, etc. [Frei et al. |
AAleen Zhu et al., [019 [Soudry et al. 2018 Arooa et al. [019b] Gunasekar et al.) more general setting, Hardt et al. (0166) prove algorithmic stability-based generalization bounds that worsen with increasing training time, whereas Loukas et al.)
2018 Haeffele and Vidal [015].
[202T] connect stable training dynamics near convergence under Dropout with good generalization.
For algorithms that do not converge (close) to fixed point, the above analyses result in vacuous bounds.
Contributions. We start with the supposition that robustness of the learning algorithm's fixed points to small changes in the training set is not the mechanism underlying the good generalization properties of deep networks. This is because, as is commonly known and many recent works indirectly
remark upon [Cohen et al.] 202T Ahn et al. 2022 Garipov et al.) 2018 Zhang et al. 2022]. training can be linearly unstable: even if assuming the presence of isolated local minima that the learning algorithm converges to, the weights encountered in training are not robust to small perturbations. Small perturbations can accumulate over time leading to completely different orbits in weight space. Yet, despite unstable dynamics, the generalization properties of two completely different fixed points (e.g., obtained from two different random initializations due to a different order of SGD updates) are typically comparable.
Our first contribution entails proposing a generalization of stability that applies to non- con-convegg algorithms. To achieve this, we depart from the typical optimization perspective of analyzing the generalization properties of minima (Keskar et al.] 2016 Ge et al. 2015 Sagun et al. [016]. Instead, we study the generalization performance of the learning algorithm on average (see section (.2). Adopting statistical viewpoint, in Section 3 we define new notion of statistical algorithmic stability that measures the stability of this average performance to perturbations of the training data, as opposed to stability of individual orbits in the weight space. Section 3 then proves upper bounds for the average generalization error based on our new notion of statistical stability.
We then move on to consider how statistical stability connects to the behavior of the loss function. To this end, in Section we provide conditions such that the spectral gap of Markov operator associated with the dynamics of the loss function is predictive of statistical algorithmic stability and hence of generalization. Empirically, we estimate this spectral gap based on the rate of convergence of ergodic averages of the loss function. We show via experiments that our estimate correlates with generalization for image classification under corruption.
1.1 Related work
Our work builds previous analyses of the stability of learning algorithms that converge [Bousquet and Elissceff] 2002 Feldman and Vondrak 2018 Kuzborskij and Lampert 2018 Bousquet et al. 2020 Zhang et al. 2021b]. Below, we also briefly discuss connections (beyond the literature stability) with previous analyses on the dynamics of learning algorithms.
Convergence and generalization of SGD. Exponential convergence rates to global minima are known for SGD in the smooth and convex setting, with decaying learning rates and small constant learning rates (e.g., [Moulines and Bach 2011 Needell et al. 2014]). In the training of deep neural networks, which is the focus of this paper, the loss function is non-convex and typically not eell-aaproximmted locally by convex functions [Ma et al. 2018). However, in the overparameterized inequality that is automatically satisfied when the loss is smooth and convex can be shown to hold in the non-convex setting well [Liu et al.) 2022 Ma et al. 2018 allowing convergence to a global minimum. In certain non-convex problems, convergence to local
regime, a tolyak-Lojasiewicz-
minima and even global minima has been proved, assuming strict saddle property [Ge et al. 2015

---

2018). Raginsky et al. [017]] show a favorable convergence for slightly different version of SGD by approximating the dynamics with suitable continuous time Langevin diffusion. A number of previous works (Safran and Shamir 2016 Freeman and Bruna 2016 [i and Yuan 2017 Nguyen et al. 2018] have also provided arguments that SGD converges to solution that generalizes given suitable initialization and significant overparameterization. A few works have studied the nonlinear dynamics of training [Kong and Tao, 2020) and provided
or local convexity [Kleinberg et al.
insights into generalization in the overparameterized regime (Dogra and Redman| 2020 Saxx et al.,
2013 Advani et al., 2020]. Another line of work considers the mean field limit SGD dynamics to show generalization [Mei al.) 2019, Gabrié et al. 2018 Chen et al. 2020]. The ergodic theoretic perspective we adopt here deviates from the optimization perspectives but relates to the mean field perspective in that implicitly consider (see section 4
the evolution of probability distributions on
weight space.
Flat minima. In the generalization literature, flat minima correspond to large connected regions with low empirical error weight space. Flat minima have been argued to be related to the complexity of the resulting hypothesis and, hence, can imply good generalization Hochreiter and Schmidhuber [997]. It has also been shown that SGD converges more frequently to flat minima when the batch size is small or the learning rate and the number of iterations are suitably adjusted (Keskar et al.)
2016 Hoffer et al., 2017 Jastrzebski et al.) 2017 Smith and Le| 2018 Zhang et al.) 2018). Some works consider the flat/sharp dichotomy an oversimplification [Dinh et al. 2017 Sagun et al. 2017 He et al. 2019]. e.g., using a reparameterization argument [Sagun et al. 2017J. The eigenvalues of the hessian of the loss affect the local linear stability of optimization orbits. However, given that we picture, we do not explicitly make assumptions on local stability
adopt the time-asye -eee-aatooic/statiisiiiie Hlatness/sharpness/ or the topology of the loss landscape [Montanari and Zhong 2020 Venturi et al.) 2019].
SGD as a Bayesian sampler. The idea of looking at distributions of learners permeates PAC- MAC-Bayesian
analyses of generalization [McAllester] 1999 [ Dziugaite and Roy 2017 Zhou et al. 2019 Pitas 2020). In contrast to Bayesian posteriors of the parameters, we study parameter distributions generated by the learning algorithms. Previous empirical work has suggested that SGD operates almost like a Bayesian sampler [Mingard et al. 2021 but the connection remains to be fully understood.
Local descent algorithms as dynamical systems: a statistical viewpoint
This section lays out the basic definitions and assumptions of our work. We begin Section 2.1 by introducing the learning problem and discussing learning algorithms from dynamical systems perspective. Section 2.2 then puts forth the notions of statistical convergence that give rise to our main results.
2.1 Learning as dynamical system
We consider the supervised learning setup: a learner is given training set S {21 ........ ...,, 2n consisting of n pairs 2, (x 34) of inputs x, E I2 and their corresponding labels y! E y C R. drawn i.i.d. from a distribution D. A class of parametric models or hypotheses h Rd x W - IR on a parameter space W gives possible ioput-to-outuut relationships, h(w.)) Fd + R. The learner is given a risk loss function &: (Rd R. W- + R that describes the error of given hypothesis. Common choices for loss functions are the mean-squared. hinge and cross-ent coos-pyttropy loss. The learner attempts to minimize the population risk (h(,,, w)) ELnDl(Z, w), by minimizing the empirical risk
1 Σ E w)
Rs(h(,, w)) Ls(w)=
(1)
n #
This minimization is achieved using a local descent algorithm given by iterative updates Øs W + W of the form
Wt+1 = dss == we The Lsw(w))
(2)
where N/ is the learning rate step size at time t.
3

---

48
0.90
23-
0.80
-33
230 0.70
0.65
1B3 0.60
cumulbiive average
wise
-40
2000 5000
Figure Although the training of neural networks depends on the initialization and does not necessarily converge in the weight space, certain functionals of the learned hypothesis can converge distribution independently of initial conditions. Left: The orbits of the 2nd layer weights of four different VGG16 models trained
CIFARIO 10 dataset using SGD with step size 0.01. We embed the orbits the plane by performing PCA onto 40 dimensions followed by t-SNE. Colors indicate epoch. Right: Corresponding test accuracy and cumulative average values function of epoch.
In the gradient descent (GD) algorithm, VLs(w) = (Ls(w) the gradient w.r.t. w, and the iterates of Φs represent deterministic dynamical system. The critical points (including saddle points, local and global minima) of Ls are fixed points of Φs (i.e., points w such that Φsw = w). For stochastic gradient descent (SGD), Ls (w) is a random variable given by the sample mean of gradients Vi(,, w) over a batch of samples S. In this case, Øs is a random dynamical system and critical points of Ls are not necessarily fixed points of Φs.
To unify the definition of és for both GD and SGD, we introduce the random variable E that indicates the choice of batch. Suppose the batch size m is fixed: m < n for SGD and m = n for GD. Denote by [n] the set 21,2, ... ]n and let E, be collection of elements from [n] chosen uniformly random. Then, we may write Φs as
W++1 = (w()) wt LL
Vi(z, w.),
(3)
m
with E, being the set [nx] at all for GD.
In our investigation, we opt for simplicity and consider fixed learning rate v) 17. More generally, our analysis can be extended to learning rates that asymptotically converge to 17. A rapidly vanish- ing learning rate obscure the learning dynamics by enforcing convergence to arbitrary points irrespective of the points' losses. In contrast, learning rates that do not decay to zero can induce interesting transitions between neighborhoods of critical points and the iterates wA generally more exploratory the loss landscape.
2.2 Statistical convergence of the learning algorithm
In deep learning, any specific choice of wr, at some time is arbitrary as the loss landscape is generally non-convex and stochastic learning algorithms are the norm. Hence, rather than focusing on single hypothesis,
attractive to consider the average generalization error induced by the stochastic dynamical system Φs. We adopt this statistical perspective, rather than focus on a single orbit of Øs. Thus, the setting below applies to any asymptotic behavior of orbits of the (typically nonlinear) dynamics Φs including fixed points, periodic, quasiperiodic and chaotic orbits.
To analyze the generalization performance without making assumptions on the global stability properties of individual orbits, we make an assumption about the ergodic properties of ás that reasonably matches empirical evidence. To describe the assumption, give a short primer on the relevant concepts from ergodic theory of dynamical systems.
Invariant measures. Denote the Borel sigma algebra on W by B(W). A probability measure as is called invariant for ds if j.s( (A) = lu o5 1 (A) for all Borel sets A E B(W). Intuitively, for any subset of the weight space, the probability that the dynamical system occupies it does not change. See Liverani (2004) for an introduction to invariant measures.

---

If Ós is a deterministic continuous function on the set W and W is compact, classical ergodic theorems (see e-g., Theorem 4.1.1 Ka and Hasselblati (1997) give the existence of at least one invariant, ergodic measure for rs. Ergodic measures are a pertinent class of invariant measures in practice, that allow us to understand the statistical properties of system through evolution of individual orbits. For ergodic measure, sets that are invariant under the dynamics Φs (such as set of periodic points, quasiperiodic or chaotic attractors) are trivial: they have measure 0 or
When Øs is an SGD update, Dieuleveut et al. [2200] show the existence of invariant distributions for convex loss functions, whereas Fort and Pagès [1999 and Mattingly al. (2002] show the existence of invariant distributions in more general settings under mild assumptions on the gradient noise
(in the estimate A L.s) Several works have analyzed the asymptotic properties of such invariant distributions, e.g.. Chee that is a critical point, as a phase separate from the transient phase of convergence to this invariant distribution. Kong and Tao [2020) study the effect of large learning rates (see also [Wang et al. 2021] for matrix factorization problems) and multiscale loss functions to show the existence of Gibbs invariant measures GD.
Chee and Toulis (2018) analyze the oscillation of the iterates wi about a mean
Ergodicity. When an invariant measure μs is ergodic for Øs, time averages converge to ensemble averages according to ps. That is, for ps--lmost every initial state wo, and for all continuous scalar functions l::
h(we) + Euwnss
and the dependence on initial conditions wo is forgotten.
Unfortunately, we cannot generally expect the dynamics of the learning algorithm have a unique ergodic invariant measure on W. Instead, øg-invariant sets could be smaller subsets of W with different ergodic invariant measures supported on them. As result, starting from two different points chosen Lebesgue almost everywhere (or sampled from any probability density on W), we do not expect time averages to converge to the same limit. Indeed, as shown in Figure [ the weights visited by os depend on the initial conditions and can vary significantly across different runs. In other words, the limit of infinite time averages described in ( does depend on Wy-
Dynamics of the hypothesis. To circumvent the above issues, rather than focusing on the weights, we consider the dynamics of the learned hypothesis h(, wt). Specifically, suppose that the infinite-time averages of the learned hypothesis are ergodic: that is, the time averages of h(2, wy) converge to the same function irrespective of the initial function 1(2,, un). Then, functionals that depend only on h and not explicitly on the weights are also ergodic. This is one such scenario that leads to our main assumption: the time averages of loss functions are ergodic.
Assumption 1. Given any S ~ DD' there exists map - (Ps) such that for Lebesgue-a.e. Wo and every E Rd x R. the following holds:
lim T-000
((z,w)) = (ez)s ERT,
(5)
T
t=o
where (w, (w: is an orbit of ds-.
As an intuitive justification for Assumption I symmetries may result in several sets of parameters (weights and biases) that represent the same network function h. Hence, assuming that there exists a unique probability on the space of neural network functions that is ergodic is less restrictive and closer to reality than assuming a unique ergodic measure the parameter space. Furthermore, ergodicity of the network functions is a stronger condition than our Assumption I and serves to illustrate one possible sufficient condition for our assumption to hold.
Figure I provides evidence that Assumption T can hold in practice. It shows two observables calculated along 4 different orbits of a VGG16 model trained using SGD with momentum (batches of size 128, learning rate of 0.01, momentum of 0.9). On the left, we can see a low-dimensional projection of the second layer weights obtained by projecting the weights onto 40 dimensions using PCA and then employing 1-SNE [Van der Maaten and Hinton 2008). whereas the observable on the right is the test accuracy, which is functional of the hypothesis function. Here, the test accuracy can
5

---

be seen to converge to a distribution independent of the initial conditions, whilst the weight orbits vary significantly across different initializations. This experiment corroborates our hypothesis that time averages of functionals on the loss space converge to distributions independent of the initial condition, even time averages of generic observable on the weight space do not. See Remark on the idea that larger learning rate induces ergodicity and Appendix A which illustrates the idea with a toy example.
Statistical stability implies generalization
In Section 3.1
we generalize algorithmic stability beyond algorithms that converge to fixed points.
Section 3.2 then proceeds to examine the implications of our definition to generalization error.
3.1 Statistical algorithmic stability
Classically, the derivations of algorithmic stability- based generalization (see e.g., Hardt al. (2016). Chapter 14 Mohri et al. [2018). J. Bousquet et al. [2020] utilize an input perturbation of one element in 8 by replacing with different element from the input distribution D:
Consider the weights w's and w'y obtained by running the learning algorithm on two training sets S sampled from D that differ by exactly one sample. We say that the learning algorithmm is algorithmically stable (AS) with a stability coefficient 3 2 0 if
Defnition (Algorithmic stability, adapted from [Bousquet and Elisseefi 2002
sup {10(2, wg) - (2), E TRd x RR.
(6)
We refer to this type of perturbation as a stochastic perturbation. Algorithmic stability does not directly apply to learning algorithms that do not converge to fixed point. Hence, next, we extend algorithmic stability to loss statistics. The resulting notion of statistical algorithmic stability (SAS) extends algorithmic stability to algorithms whose loss statisties converge prescribed by Assumption I even if the weights do not converge.
Defnition 2 (Statistical algorithmic stability). We say that a learning algorithm with loss statistics denoted by (Ex)s is statistically algorithmically stable (SAS) with stability coefficient B 2 0 if
B sup -
- (f2)s:
Rd x xR),
where S, St differ in exactly one element.
In the above definition, (Lz)s) refers the ergodic average of f(2, observed along almost every orbit of Φs A higher value of 33 indicates a lower SAS algorithm. The definition of SAS differs from Definition as we do not assume convergence of the learning algorithm. Nevertheless, when every orbit of és converges to a fixed point w for almost every S, then Definition (7) reduces to the standard notion of algorithmic stability since ergodic averages along almost every orbit converge to ((2, wg)..
Crucially, and in line with the observations in Figure the loss function and not the loss function at an ensemble mean or at any one point the weight space W. In other words, the definition of SAS does not use or provide information about the algorithmic stability of Ewery" w for any invariant measure jas-
quantify stability based on the statistics of
3.2 Learning theoretic implications
It is well-known that Definition Ileads to generalization bounds (see (Hardt et al. 2016 Bousquet et al. 2020) and references therein). Next, we show that the more general statistical algorithmic stability from Definition also can imply notion of generalization.
To obtain generalization bounds, we first redefine the empirical and population risk to use the loss statistics rather than loss values at fixed points:
Rg = E(.)) and Rs = (EsD(
(8)
SES

---

Although the definitions above appear deceivingly similar to the standard ones introduced in Sec- tion 2.. the two notions of risk are defined on different spaces, with the standard ones being maps from the hypothesis space H to scalar values and (8) being maps from the space of learning algo- rithms. That is, the latter risks only depend on algorithmic parameters and are not functions of H. Using these definitions, the following generalization bound holds:
Theorem 1. Given a 3-statistically algorithmically stable algorithm Φs (see Definition P. any 5 E (0, 1), with probability greater than 6,
(2/5)
Rg S Rs + 3 + 2 L)
2n
where L = sup, ww [8( w) is an upper bound on the loss.
The proof can be found in Appendix B and is based applying Mcdiarmid's inequality to the generalization gap. Like Bousquet and Elisseeff [2002]'s bound, the SAS coefficient 3 has to decay least fast as O Vn) for the generalization bound be non-vacuous. Note that our proof is also naturally coupled with [Bousquet et al. 2020 Feldman and Vondrak 2018 s improved technique,
which provides tighter bounds when 3 ~ O1/ nn). (see Appendix
4 Dynamical systems interpretation of SAS
How can we distinguish between two algorithms with different SAS? Can the algorithm dynamics provide clues to its SAS? These questions are of practical importance because a more (statistically) stable algorithm generalizes better (via Theorem [.. Since the SAS coefficient /3 is defined as a supremum over infinite pairs of training sets and inputs, a numerical estimation of it using its definition only gives a rough lower bound and obtaining this lower bound is also computationally expensive (see Figure 3 and section 5). Moreover, a numerical lower bound on B does not give us a mechanistic understanding of statistical stability, which we seek here.
Here we develop an operator-theoretic explanation for what makes an algorithm statistically stable. We also derive a rough heuristic - albeit not a definitive predictor of generalization - that relates a given training dynamics its SAS coefficient 3.
4.1 Bounding the SAS coefficient
Before we present our bound, we discuss why we must deviate from the trajectory-based approach that is commonly employed study algorithmic stability. We recall that Hardt et al.) [2016) base their proofs of classical algorithmic stability (Theorems 3.7 and 3.8 in Hardt et al. (2016]) on the accumulating differences between two orbits corresponding to S and S', whenever the different element is chosen in the mini-batch. The greater the difference in the weights, the greater the difference in the (upper bound on the) loss functions those weights, in the case of Lipschitz loss. Thus, Hardt et al. (016) argue that training faster (or stopping earlier) will lead to stabler algorithms. Since SAS is about robustness of loss statistics or infinitely long time averages, the analysis la Hardt ct al. (0166) generically leads to vacuous bounds for the SAS coefficient.
Our analysis is based on the realization that an algorithm can be SAS even if two orbits corresponding to S and S' diverge from each other (within W), but lead to similar loss statistics. Thus, to bound the SAS coefficient, perturbation analysis of transition operators (global information), rather than finite-time perturbation analysis of an orbit (local information), is needed. Since SAS only demands robustness on loss space, we consider Markov transition operators on the loss space (S [0, L), as opposed to on the weight space (W) In general, at any z and wi, the loss process, {f(z, wx) J is not Markovian. But, family of Markov operators can be associated with the family of loss functions.
Lemma 1. (Markov operators) Let μs be an ergodic, invariant measure for Øs. Assume that loss function :(z,,): : WW + 12= C [0, L) is such that the pushforward, vi :B[{)) )) + lR+,, of us on the loss space is well-defined. Here, B(I.) is the Borel sigma algebra on Ig and Vi = f(z, .)sss, where & refers to the pushforward operation. Then, there exists a uniformly ergodic Markov operator Pis on the space of probability measures on Iz, with its invariant measure being v/..
This lemma (see Appendix C for proof) parallels Chekroun et al. 2014)'s 's Theorem A, but in a quite different setting, without using existence of unique physical measure on the phase space (W).
7

---

defined by Lemma Combined with Assumption 1 perturbation results on the Markov operators, P just Ilead us to SAS. Since P is uniformly ergodic, there exist Ag E (0, 1) and C > such that for all & E I in the Wasserstein norm (l) Ilw),
| us - -33lvl S CX.-
(10)
Let A == sup, A₂ be the rate of mixing associated with the family of operators P perturbation theory of Markov operators to study the effect of stochastic perturbations on vğ. and subsequently, SAS. To see the connection with SAS, we recall that, by Assumption [T for any choice of pss we have that (fz)s = Egnuz5. S. Thus, given any pair of us and us' we have (see Appendix C for details)
We leverage the
((2)s (c)) [Eg Bg-ug El lIv V llw
(11)
Thus, a uniform upper bound on 11/3 - V llw gives an upper bound for the SAS coefficient, 3. Such bound is obtained from the straightforward use of an appropriate perturbation result on uniformly ergodic Markov chains.
Theorem 2. Given a uniformly ergodic Markov operator as constructed Lemmal 7 and that the Lipschitz constant of E((-, w) on R is bounded above by LD for all w E W, ds is SAS with stability coefficient
B 8=0 (- LD 1
where x = sup, X2 is the supremum over of the mixing rates of Pi
Proof. (Sketch) The proof relics on the perturbation bounds of Rudolf and Schweizer (2018). Corol-
lary 3.2. Note that when (TO) is satisfied, and if stochastic perturbation S' introduces change 5p to Pe the perturbation bound from [Rudolf and Schweizer 2018 gives Ps
Mg*
|| - v lww S C1 //(11 X2),
(12)
where |18P us
is the operator norm of öp: induced by Wasserstein norm. From II
( - 1 S C 11/(1 X²). -x).-
(13)
Since this holds for all z, the right hand side of 113 is an upper bound for the stability coefficient / in Definition 2 by taking the supremum over An upper bound on | can be derived when
the Lipschitz constant of Ve(,,w) is uniformly (in w) bounded on Rd, as shown in Appendix
Theorem 2 implies that an algorithm that exhibits fuster convergence to the stationary measure on the loss space generalizes better. The bound in Theorem 2 implies that smaller À (faster convergence of the loss to the ergodic invariant measure) yields smaller upper bounds on 3 (more statistically stable algorithm) and better generalization.
Strictly speaking, to determine Ay we must consider finite-dimensional approximations of the operator P (as done in the setting of chaotic systems in e.g., [Crimmins and Froyland 2020 Chekroun et al. (2144) and compute its spectral decomposition. However, in our setting, it is diffiuut in practice to generate samples in the loss space that obey the Markov process defined in Lemmal Instead, we argue for using the readily available non-Markovian loss process to estimate convergence to the equilibrium distribution. In particular, we hypothesize below that the auto-correlation function of the test loss can separate algorithms based on their SAS.
Dropping the superscripts z, we define the auto-correlation Ce(T) in a loss function & (see also Remark 3 in Appendix Ch by
Ce(T)
lim T-000
E - IST
(14)
That is, Ce(T) gives the correlation between the random variables ((w:)/ (E) and ((we+r)/(() where the randomness comes from the batch selection E, and the initialization of weights SGD, and only from the latter in GD.
8

---

0.06
noisa
0.05
1.2
17 1 nolse
0.05
25 54 noisa
1.0
0.00
30 16 nolee
0.04
0.3
0.2
0.02
0.11
200
4200
Time
600
802
2000
15 363ta
30
200
A30
1irr
200
1020
Figure 2: SAS computed from the VGG16 model. Left: The change in cumulative time averages of the test loss upon stochastic perturbation of the CIFARIO dataset. Center: Lower bound on the statistical stability coefficient 3 (Definition 2 computed using the test loss. Right: Test error timeseries.
1.
0.04
10 ndia
0.03
17 noie
mosk
0.5
12
So
0.02
0.3
0.03
000
200
1000
-020 420
020
0.0
200
420
1020
lime
1ime
Hime
Figure 3: Predictors of generalization gaps data with corrupted labels computed on the ResNet18 model. Left: Time series of the test loss. Center: Normalized auto-correlation of the test loss timeseries the left. The magnitude of the auto-correlation in the test loss is suggestive of the generalization gap (right). For large percentage of noise, the gap decreases because the neural network cannot fit the training data well.
Suppose that the loss process is Markov, i.e., f(we+1) conditioned on ((w)) is independent of {((w)) :t' < 1). Setting = O after sufficiently long runup time, the function Ce(T) in (14) is the auto-correlation function of stationary Markov chain, which typically decays exponentially with This decay rate is lower (slower correlation decay/longer correlation times) when À is closer to 1. Qualitatively, comparing two different stationary Markov chains, the one with higher values of Ce has longer correlation times and hence, larger X.
In general, however, the loss process (f(w)) 2 0} is non-Markovian. Thus, we do not expect Ce(T) to decay with т. This is because the correlation function C2 encodes both the Markovian and non-Markovian components component of the loss dynamics (see Remark in Appendix C Zwanzig Kondrashov et al. 2013).. Hence, we expect the correlation times in the loss process to not be equal that of a Markov process generated according to Pus.- For the purpose of qualitatively comparing the SAS coefficients of two algorithms, however, the loss process can be considered heuristic for a Markov process generated according to Prg. Then, higher values of C2 computed from the loss process indicate larger X, and hence less statistical stability.
2001KKondaahhor
5 Numerical results
We numerically validate the main ideas of section and Jn VGG16 and ResNet18 models trained on the CIFAR10 dataset (see Appendix[]for further numerical results, (Chandramoorthy and Loukas 2023) for the code). For our experiments, ós is an SGD update with momentum 0.9, fixed learning rate 0.01 and batch size of 128. In all figures, "time" indicates number of epochs. We generate different versions of the training set Sp by corrupting CIFAR10' 10's labels with probability p, with So being the original CIFAR10 10 dataset. Figures and 3 show results corresponding to p = 0, 0.1, 0.17, 0.25 and 0.5. Each line in Figure 3 is a sample mean over 10 random initializations.
In Figure we numerically estimate a lower bound on the SAS coefficient 3 using its definition (see Definition 2). On the left, we plot the difference test loss time-averages between between random orbits of Φe, and Φs;, with Sy, being stochastic perturbation of Sp. The mean over 45 pairs of orbits is shown as dots and the error bars indicate the standard error in mean. The cumulative time

---

average along orbits of length 1200 epochs are used as estimators for statistics. With these estimators for statistics, in
we compute an estimate of the stability coefficient as the difference of the (estimated) test loss statistics at different values of This is hence an estimate on the lower bound of 83 and clearly increases with p. This illustrates that cases with worse generalization errors (Figure 2 (right)) have larger lower bounds on 39.
In Figure (left), we show the test loss timeseries obtained with the ResNet18 model. Again, greater the noise corruption p, the larger is the generalization error (estimated by test error), consistent with previous studies Zhang al. [2021a] Loukas al. [202T] ). On the other hand, the generalization gap difference between training and test error is bigger for intermediate levels of noise and decreases when p = 0.5, as shown in Figure (centerr) The gap does not always increase with p because, when
the labels are close to random, the network cannot fit the training data and thus the training error is also large.
In Figure (right), we plot C²(T) (Section 4) where & taken as the test loss. The test loss statistic (e) is estimated time average over 1200 epochs. At each p, we show the sample average of the auto-correlations over 10 independent runs. We see that the magnitude of the test loss auto- correlations preserves the same order (across p's as the generalization gap (absolute difference in test and training losses) shown in Figure 3 center). Hence, we empirically observe that the loss process codifies the phenomenological explanation for SAS that is expressed in Theorem
Discussion and conclusion
Predicting generalization is an active area of research and has implications for more reliable use of machine learning. In this work, we introduce statistical algorithmic stability (SAS) and show how implies generalization bounds. Here, we add few important remarks.
Statistical stability only requires robustness of statistics on loss space. central challenge in the analyses of non-come non-convergent algorithms is the fact that there may be multiple, very different invariant measures Jls. For this reason, our stability criterion focuses on statistics of the loss function. This way, an algorithm can be stable even if the measures jas and uu are not close in the total variation norm. In fact, an algorithm can be stable even if μuy and ps are mutually singular, if the loss functions have similar statistics. Since our SAS analysis hinges on ergodic properties of the algorithm, we believe is broadly applicable.
reasonable yet nonrestrictive assumption
Algorithms that converge are special cases of the above analysis. In Appendix we show that the proposed relationship (section 4 between statistical stability and convergence rates to stationary measures can also be observed in the Neural Tangent Kernel (NTK) regime [Jacot et al. 20188. In this case, the training dynamics, és, can be approximated by a linear function of the weights, which converges to a fixed point. Thus, this provides an alternative, ergodic theoretic, interpretation of generalization in the NTK regime [Arora et al. 2019b Montanari and Zhong 2020 2021].
Bartlett et al.
Broader view: While our focus is on algorithmic stability-based generalization, this work gathers more evidence to support the broader view [Wojtowylsch) 2021 Zhang et al.] 2022] that exploiting theoretically and empirically available dynamical information about the training algorithm is a fruitful complement to understanding generalization from the optimization landscape and learning theory perspectives.
Funding: This work was partially funded by the NSF AI Institute TILOS, NSF award 2134108, and ONR grant N00014-20-15 1-22--1--023 (MURI ML-SCOPE).
Acknolwedgmentss: N.C. would like thank Nandhini Chandramoorthy and Derek Lim for helping with the experimental setup and Sven Wang. Benjamin Zhang. Matt Li and Youssef Marzouk for valuable discussions. The authors also thank the reviewers for their constructive suggestions.
10

---

References
M. S. Advani, A. M. Saxe, and H. Sompolinsky. High-dimensional dynamics of generalization error in neural networks. Neural Networks, 132:428 446, 2020. ISSN 0893-6080. doi: hitps:
022. URL ott.tt/t///////ooooooooooooooooo com/science/
atticle//p1/$99996600000111
K. Ahn, J. Zhang, and S. Sra. Understanding the unstable convergence of gradient descent, 2022.
URL /tappp://arxivv. org/ abaa awwpa/04......... 01050
Z. Allen-Zhu, Y. Li, and Y. Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL htttts::/pppoeeeeeeesseee pptp:////noce.ess.../.... neur cc cctppappeee119//ieeeee 622a662776d2225542277222222
hewpiiinnnnneuuuispeeeee. Paper pdf
H. Arbabi and I. Mezic. Ergodic theory, dynamic mode decomposition, and computation of spectral properties of the koopman operator. SIAM Journal on Applied Dynamical Systems, 16(4):2096- 2126, 2017.
J. L. Aron and I. B. Schwartz. Seasonality and period-doubling bifurcations in an epidemic model. Journal of theoretical biology, 110(4):665-679, 1984.
S. Arora, R. Ge, B. Neyshabur, and Y. Zhang. Stronger generalization bounds for deep nets via compression approach. In International Conference on Machine Learning, pages 254-263. PMLR, 2018.
S. Arora, S. Du, W. Hu, Z. Li, and R. Wang. Fine- Fine-grained analysis of optimization and generaliza- tion for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019a.
S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019b. URL httt::::/proceedings. mwt.rips..c//ppee///1////L dbc4d84bfcfe22880 1 beef b853a8c4 Sasper.pd:
P. L. Bartlett, D. J. Foster, and M. Telgarsky. Spectrally-normaizzed margin bounds for neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 0241-6250 2017.
L. Bartlett, N. Harvey, C. Liaw, and A. Mchrabian. Nearly-tighh vc-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1-17, 2019. URL TtLLhttp://// http://jmlr org.ogg///aa.. wrggpapprs/vv//////o// 100000176112 html
L. Bartlett, A. Montanari, and A. Rakhlin. Deep learning: a statistical viewpoint. Acta numerica. 30:87-201, 2021.
O. Bousquet and A. Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499- 526, 2002.
O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Abernethy and S. Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 610-626. PMLR, 09-12 Jul 2020. httt:tttt///ooeeee
mlr ppwsssvv25/bbaee /ttpppree///////uuuuueu22200
M. BudiKié, R. Mohr, and Mezić. Applied koopmanism. Chaos: An Interdisciplinary Journal of Nonlinear Science, 22(4):047510, 2012. doi: 10.1063/1.4772195.
N. Chandramoorthy and Loukas. ni-sha-c/astability:: Paper, Jan. 2023. URI. U
10. www.58122endd..55220 7525770

---

J. Chee and P. Toulis. Convergence diagnostics for stochastic gradient descent with constant learning rate. In A. Storkey and Perez-Crus Cruz, editors, Proceedings of the Twenty-Fiie First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1476-144 1485. PMIR, 09-11 Apr 2018.
M. D. Chekroun, J. D. Neelin, D. Kondrashov, J. C. McWilliams, and M. Ghil. Rough parameter dependence climate models and the role ruelle-pollicott resonances. Proceedings of the National Academy of Sciences, 1 111(5):1684-166) 2014.
7. Chen, Cao, Q. Gu, and T. Zhang. Mean-field analysis of two-layer neural networks: Non- asymptotic rates and generalization bounds. arXiv preprint arXiv:2002.04Mm 040266 2020.
M. Cohen, Kaur, Li, Z. Kolter, and Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability, 2021. httt::tts:://ar/iit httpppps//aaxi..ooo/aaaaaaa///// 2a0b../210....m 00065
H. Crimmins and G. Froyland. Fourier approximation of the statistical properties of anosov maps on tori. Nonlinearity, (6611))62244, 2020.
M. Dellnitz, G. Froyland, and S. Sertl. On the isolated spectrum the perron-frobenius operator. Nonlinearity, 13(4):1171, 2000.
A. Dieuleveut, A. Durmus, and F. Bach. Bridging the gap between constant step size stochastic gradient descent and Markov chains. The Annals of Statistics, 48(3):1348 1382, 2020. doi: 14.2114/9-AOS1850 URL https:
1214/12 - A0S1850
L. Dinh, R. Pascanu, S. Bengio, and Y. Bengio. Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pages 1019-1028. PMLR, 2017.
A. S. Dogra and W. Redman. Optimizing neural networks via koopman operator theory. Advances in Neural Information Processing Systems, 33:2087-2097, 2020.
G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data, arXiv preprint arXiv: 1703. 10088, 2017.
V. Feldman and Vondrak. Generalization bounds for uniformly stable algorithms. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi. and R. Gar- nett, editors, Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: h cetissenuripp.. www..ps..cppappeeeeeeeee wwtppppppe///e///eeeee.e 005021666e62273886666eeeaa-----2
ppf]]
J.-C. Fort and G. Pagès. Asymptotic behavior of a markovian stochastic algorithm with constant step. SIAM Journal on Control and Optimization, 37(5): 115111426.44 1999.
C. D. Freeman and J. Bruna, Topology and geometry of half-rectified network optimization. arXiv preprint arXiv: 161.05400 2016.
S. Frei, Y. Cao, and Q Gu. Algorithm-depenndntt generalization bounds for overparameterized deep residual networks. In H. Wallach, Larochelle, A. Beygelzimer, F. d'Alché-But Buc, E. Fox, and R. Gameet,, editors, Advances in Neural Information Processing Systems, volume 32, Cur- ran Associates, Inc., 2019. URL httpp::/pproceeeeeeeeee httpr/ddwwnnnnrurppsss///a/////p wttpiips.ccpppppppe wwtpppppppppp1//iiii.... 1e229000111111133324466ccbbbbb
pdf
M. Gabrié, A. Manoel, C. Luneau, N. Macris, F. Krzakala, L. Zdeborová, al. Entropy and mutual information in models of deep neural networks. Advances in Neural Information Processing Systems, 31, 2018
T. Garipov, P. Izmailov, D. Podoprikhin, D. P. Vetrov, and A. G. Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biarde Bianch,, and R. Garnett, editors, Advances in Neural Information Processiny Systems, volume 31, Curran Associates, Inc., 2018. / neurips 2018 2ugffiiiiaacdiirree00000CCCeeeee
neurips.cc/paperr cc/paper/
12

---

R. Ge, F. Huang, C. Jin, and Y. Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. Conference on learning theory, pages 797-842. PMLR, 2015.
N. Golowich, A. Rakhlin, and O. Shamir. Sizs-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR, 2018.
S. Gunasekar, J. D. Lee, D. Soudry, and N. Srebro. Implicit bias of gradient descent on linear convolutional networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garett, editors, Advances in Newral Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018 URL http:p////ppoddddnnnnoooo......p (eB Paper pdf
B. D. Haeffele and R. Vidal. Global optimality in tensor factorization, deep learning, and beyond, 2015. URL /nttps://aaraett org/ abs/1506.0754)
M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In M. F. Balcan and K. Q. Weinberger, editors, Proceedings The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1225-1234, New York, New York, USA, 20-22 Jun 2016. PMLR. BRRth:t:://proeeeee mlr. wwwpp/eeesseeee preess/488/arddt6..ntt htt//harrt1.tttt
H. He, G. Huang, and Y. Yuan. Asymmetric valleys: Beyond sharp and flat local minima. arXiv preprint 4rXiv:1902.00044, 2019.
S. Hochreiter and J. Schmidhuber. Flat Minima. Neural Computationn 9(1):1-42, 01 1997. ISSN 0899- 7667. doi: (tt./////cco.999.9...
/tt/pptt:///00..rr//// wwt.:/111cnceecee 199..9.1.11. 9.11
E. Hoffer, I. Hubara, and D. Soudry. Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In NIPS, 2017.
A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kerne:: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018. URL https: http:////ppoodeeeoeooe.o....eeee wwweiinggn.nnuuuunee nww. pet.rppp.cccpppppr////////1/ BaabefffsJee2bBBBebbb11222222222 Papeeerraaaaparr......earrrree.e .pff
/
S. Jastrzebski, Z. Kenton, D. Arpit, N. Ballas, A. Fischer, Y. Bengio, and A. Storkey. Three factors influencing minima in sgd. arXiv preprint 1711v:/711.04622.0 2017.
T. Kato. Perturbation theory for linear operators, volume 132. Springer Science & Business Media, 2013.
A. Katok and B. Hasselblatt. Introduction to the modern theory of dynamical systems. Number 54. Cambridge university press. 1997.
G. Keller and C. Liverani. Stability of the spectrum for transfer operators. Annali della Scuola Normale Superiore di Pisa-Classe di Scienze, 28(1):141-152, 1999.
N. S. Keskar, D. Mudigere, Nocedal, M. Smelyanskiy, and P. Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint 1wX.::16,9.04866, 2016.
B. Kleinberg, Y. Li, and Y. Yuan. An alternative view: When does SGD escape local minima? In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2698-2707, PMLR, 10-15 Jul 2018. URL httl:ttts/////ceeeeiii
mlr. wwwppp/esssweeeeee htt.rr/////eeeeeeeerreeee html
D. Kondrashov, M. D. Chekroun, and M. Ghil. Data-driven non-markovian closure models. Physicu D: Nonlineur Phenomena, 297:33-55, 2015. ISSN 0167-2789. doi: https://doi.org/ 10. ph1.: 12.000. URI.https: h/ttttsss//wwwtt./ http://wwwwcceeeeerreettttc cometttcocccceeeeeeeeeeeee http:///sssecttcccoo///cc//ceeae 151/801667278914002413
13

---

L. Kong and M. Tao. Stochasticity of deterministic gradient descent: Large learning rate for multiscale objective function. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 2625 2638. Curran Associates, Inc., 2020. URL JRRpttpss: 1195806666674433443222222222 htttpps:/ppooceddnggss httprrppss.c/aappe/////////eeee Paper pdf
B. O. Koopman. Hamiltonian systems and transformation in hilbert space. Proceedings of the national academy of sciences of the united states of america, 17(5):315, 1931.
M. Korda and I. Mezić. On convergence of extended dynamic mode decomposition to the koopman operator. Journal of Nonlinear Science, 28(2):687-710, 2018.
I. Kuzborskij and C. Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pages 2815-2824. 2824. PMLR, 2018.
A. Lasota and M. C. Mackey. Chaos, fractals, and noise: stochastic aspects of dynamics, volume 97. Springer Science Business Media, 1998. doi: 10. 1-1779977----412-2288--1--
Y. Li and Y. Yuan. Convergence analysis of two-layer neural networks with relu activation. Advances in neural information processing systems, 30, 2017.
K. K. Lin and F. Lu. Data-driven model reduction, wiener projections, and the koopman-mori- zwanzig formalism. Journal of Computational Physics, 424: 109864, 2021. ISSN 0021-9991. doi: https://doi.org/1000 2ttp:///rrr/........../......... 109864. URL
com/
C. Liu, L. Zhu, and M. Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Hurmonic Analysis, 2022.
C. Liverani. Invariant measures and their properties. a functional analytic point of view. Dynamical systems. Part II, pages 288-237, 2004.
E. Lobacheva, M. Kodryan, N. Chirkova, A. Malinin, and D. P. Vetrov. On the periodic behavior of neural network training with batch normalization and weight decay. Advances in Neural Information Processing Systems, 34, 2021.
A. Loukas, M. Poiitis, and S. Jegelka. What training reveals about neural network complexity. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https::/ http://wwnnnttoorrmreeeeoo/////
S. Ma. R. Bassily, and M. Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern wer-parametrriee learning. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 Proceedings of Machine Learning Research, pages mlr. www.pressvveee v80/ ma18a.1.1mmmmmmmmmmmmmmmmmm html
PMLR, 10-15 Jul 2018. URL http::ttp:::/ttt htttps://proceedingg
J. Mattingly, A. Stuart, and D. Higham. Ergodicity for sdes and approximations: locally lipschitz vector fields and degenerate noise. Stochastic Processes and their Applications,, 101(2):155-232. 2002. ISSN 0304-4149, doi:
URL https
//www
D. A. McAllester. Some pac-bayesian theorems. Machine Learning, 37(3):355-363, 1999.
S. Mei, T. Misiakiewicz, and A. Montanari. Mean-fiel theory of two-layers neural networks: dimension-free frre bounds and kernel limit. In Conference Learning Theory, pages 2388-2464. PMLR, 2019.
C. Mingard, G. Valle-Pérez, J. Skalse, and A. A. Louis. Is sgd a bayesian sampler? well, almost. Journal of Machine Learning Research, 22, 2021.
M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of machine learning. MIT press, 2018.
A. Montanari and Y. Zhong. The interpolation phase transition in neural networks: Memorization and generalization under lazy training. arXiv preprint 200.:iv:0077.2206 2020.
14

---

E. Moulines and F. Bach. Non- Non-asymphnn as--ammmmttiic analysis of stochastic approximation algorithms for machine learning. In J. Shawe-Taylor, Zemel, P. Bartlett, F. Pereira, and K. Wein- berger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011. URL. https: httpp:://proeeedinss new.. pttparpppps.ccppppp///////////
pdf
D. Needell, R. Ward, and N. Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In Z. Ghahramani. M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Cur- ran Associates, Inc., 2014. URL
nwuripe. cearripp.ccc/pppe///1/////1
pdf
Y. Nesterov. Introductory lectures on convex optimization: basic course, volume 87. Springer Science & Business Media, 2003.
B. Neyshabur, S. Bhojanapalli,, and N. Srebro. A pac-bayesian approach to ppectrallynormmalize margin bounds for neural networks. International Conference on Learning Representations, 2018.
Q. Nguyen, M. C. Mukkamala, and M. Hein. On the loss landscape of a class of deep neural networks with no bad local valleys. In International Conference on Learning Representations, 2018.
K. Pitas. Dissecting non- vacuous generalization bounds based on the mean-field approximation. In International Conference Machine Learning, pages 7739-7749. PMLR, 2020.
T. Quail, A. Shrier, and L. Glass. Predicting the onset period-doubling bifurcations in noisy car- diac systems. Proceedings of the National Academy of Sciences, 112(30):9358-99)) 9363, 2015. doi: 10. 1..1077/pnas.142422111 142430011..
URL https:://satt pnas. org htt////iibbsso.oo 1073/ 1073/pnas pnas
1424520112
M. Raginsky, A. Rakhlin, and M. Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a monasymptotic analysis. In Conference on Learning Theory, pages 1674-1703. PMLR, 2017.
A. Rakhlin. Applications of empirical processes in learning theory: algorithmic stability and generalization bounds. PhD thesis, Massachusetts Institute of Technology, 2006.
D. Rudolf and N. Schweizer. Perturbation theory for Markov chains via Wasserstein distance. Bernoulli, 24(4A):2610 -2639, 2018. doi: 10.3150/17-BEJ933 URL /ttps:////// 1150/17--BJJ93
I. Safran and O. Shamir. On the quality of the initial basin in overspecified neural networks. In International Conference on Machine Learning, pages 774-782, PMLR, 2016.
L. Sagun, L. Bottou, and LeCun. Eigenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint
2016.
L. Sagun, U. Evci, V. U. Guney, Dauphin, and L. Bottou. Empirical analysis of the hessian of over-parametrized neural networks. arXiv preprint arXiv:1706.04453 04454, 2017.
A. M. Saxe, J. I. McClelland, and S. Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, 2013. URL httph::tts/s:ttt www.aaawww..oorrraaaararerrraaae 11///1112.26111
J. Sirignano and K. Spiliopoulos. Mean field analysis of deep neural networks. Mathematics of Operations Research, 4701):120-152, 2022.
S. L. Smith and Q Le. A bayesian perspective generalization and stochastic gradient descent. In International Conference on Learning Representations, 2018.
J. Sokolić, R. Giryes, G. Sapiro, and M. R. Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65(16):4265 4280, 2017.
D. Soudry, F. Hoffer, M. S. Nacson, S. Gunasekar, and Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1):82222877.. 2018.
15

---

L. Van der Maaten and G. Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
V. N. Vapnik. An overview of statistical learning theory. IEEE transactions on newral networks, 10 (5):988 9998 1999.
L. Venturi, Bandeira, and J. Bruna. Spurious valleys in one-hidden-layer neural network optimization landscapes. Journal of Machine Learning Research, 20:133, 2019.
U. von Luxburg and O. Bousquet. Distance-based classification with lipschitz functions. J. Mach. Learn. Res., 5:669-695, 2004.
Y. Wang, M. Chen, T. Zhao, and M. Tao. Large learning rate tames homogeneity: Convergence and balaneing effect. 2021. doi: 00-4550/ARXXI2211000:::11
httth::tt/:tsiiiie abs/
A. Wilkinson. What are дyарыnov exponents, and why are they interesting? Bulletin of the American Mathematical Society, 54(1):79-105, 2017.
M. O. Williams, C. W. Rowley and I. G. Kevrekidis. A based approach to data-driven koopman spectral analysis. arXiv preprint arXiv:1411.2200 2014.
S. Wojtowytsch. Stochastic gradient descent with noise of machine learning type. part Discrete time analysis, 2021. URL
01650
H. Xu and S. Mannor. Robustness and generalization. Machine learning, 86(3):391-423, 2012.
C. Zhang, Q. Liao, A. Rakhlin, B. Miranda, N. Golowich, and T. Poggio. Theory of deep learning iib: Optimization properties of sgd. arXiv preprint arXiv 2018.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021a.
J. Zhang, H. Li, S. Sra, and A. Jadbabaie. Neural network weights do not converge to stationary points: An invariant measure perspective. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings Machine Learning Research, pages 17-23 Jul 2022. Utthhtts:://prott http:////pceeeen......e mlr prwss/vevvvvve ht/p//v1222//2 /62222hag2222 hhtmmlllmm..mll html
PMLR.
Y. Zhang, W. Zhang, S. Bald, V. Pingali, C. Chen, and M. Goswami. Stability of sgd: Tightness analysis and improved bounds. arXiv preprint arXiv:2102.05274, 2021b.
L. Zhao, Tang, F. Lin, and Zhao. Observation of period-doubling bifurcations in a femtosecond fiber soliton laser with dispersion management cavity. Optics express, 12(19):4573 4578, 2004.
W. Zhou, V. Veitch, M. Austern, R. Adams, and P. Orbanz. Non-vacuous generalization bounds at the imagenet scale: a PAC-bayesian compression approach. In International Conference on Learning Representations, 2019. URL httptttss////pteeeeee/ wtt.:/wwwwweeeeomo/////deggooooe
R. Zwanzig. Nonequilibrium statistical mechanics. Oxford university press, 2001.
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]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
16

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof' of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material URL.)? [Yes] In the supplementary material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] see section 5 and Appendix [
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See section 5 and Appendix D
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(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]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, 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]
17


Reviews:
[{"review_id": "gyIOydOw8q0", "reviewer": "Reviewer_HJ1k", "summary": "This paper, entitled \"On the generalization of learning algorithms that do not converge\", extends the notion of algorithmic stability to algorithms that do not converge in the traditional sense of reaching a fixed point in weight space. Because it is increasingly becoming clear that many commonly used algorithms often do not converge, this covers a broad range of algorithms. By using ergodic theory, the authors define statistical algorithmic stability and develop bounds for their metric. These bounds identify that algorithms \"that exhibit faster convergence to the stationary measure on the loss space generalize better.\" Finally, the authors validate their theory on VGG-16 and ResNet-18 models.", "questions": "I have no additional questions for the authors.", "limitations": "The authors should make a little more clear what possible limitations the use of the auto-correlation and the non-Markovian nature of samples from the loss space introduces into their numerical experiments. ", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS:\n\n1. This paper is very well written. It was easy to read and get the main points from. \n\n2. This paper effectively motivates the problem by identifying a gap in the current theory developed for studying algorithmic stability and illustrating why many commonly used algorithms fall into this gap. TA large body of literature was cited and it was clear where overlap between this paper's contributions and other work in the field was. \n\n3. The authors' new definition of statistical algorithmic stability is general, intuitive, and theoretically backed. This last point, being grounded in theory, makes it especially appealing as an extension for algorithmic stability.  I believe that it will be prove useful for studying algorithmic stability, and will open up new discussion in the field.  Additionally, the authors should be applauded for their treatment of dynamical systems and ergodic theory, which was clear and well laid out.\n\n4. The result that \"that exhibit faster convergence to the stationary measure on the loss space generalize better\" is very interesting. If anything, I think the authors should emphasize this point more throughout the paper, as I imagine it will be of interest to the community. \n\nWEAKNESSES:\n\n1. The discussion surrounding the use of the auto-correlation and the non-Markovian nature of samples from the loss space felt cramped. I understand page that there are page constraints, but it felt a little difficult to connect the experimental results with the theory that had been laid out earlier. Additionally, I would emphasize the last (punchline) sentence of Sec. 4 (lines 324-326) more. \n\n2. The generalization gap for the 50% noise being nearly the same (if not lower) than the generalization gap of the 0% noise confuses me (Figure 2). Is this because the ResNet is performing \"at chance\"? Adding a sentence or two to clarify this would be helpful for interpreting this result. \n\n3. There are two points in Sec. 5 where I believe the conclusions from the results are overstated. First, Figure 3 (right) shows the lower bounds of $\\beta$. Therefore, the claim \"illustrating that cases with worse generalization error have larger $\\beta$\" (lines 344-345), is not quite right because it has not been shown how tight the lower bound is. However, I do think it is interesting and telling that the lower bound increases with worse generalization. Making this point more accurately does not, in my mind, diminish the finding. And second, \"the magnitude of the test loss autocorrelation correlates with with the generalization gap\" (lines 353-354). Looking at Figure 2 (center), it appears that the generalization gap between 10%, 17%, and 25% noise, at the end of the 1000 epochs, is pretty minimal. However, there is a very clear difference in the magnitude of the test loss autocorrelation between 10% and 17%/25% (Figure 2 (right)). Similarly, there is a large difference in magnitude between 0% and 50%, whereas there is not a major difference between the generalization gap of those two. I think the authors would do better to report the results as is. The theory they develop is very convincing (at least to me), and improvements on the bounds and ways to compute $\\lambda$ will lead to stronger numerical results. For now, it is sufficient (again, to me) to just show the current state of numerical results, even if they aren't 100% convincing. \n\n3. The abstract mentions the work \"provides clues to overfitting\" (line 12), but overfitting is not explicitly mentioned. I would either discuss this in Sec. 6 or remove from the abstract.\n\nMINOR POINTS:\n\n1. Figure 3 (left) should have lines instead of dots to reduce the thickness of the curves. \n\n2. That Figure 2 and Figure 3 are tested on different models should be made more clear in the text (not just the figure captions). \n\n3. It should be noted after Eq. 7 that a smaller value of $\\beta$ implies better generalization. This is of course obvious from the equation, but \"stability coefficient\" may make readers think bigger is more stable. \n\n4. \"two notions of risk defined...\" (lines 250-252) is an interesting point and should be made a little more clear. What precisely is \"the space of learning algorithms\"? Why does Eq. 8 lie in the space?\n\n5. There are a few typos:\n\ni. Lines 94 and 99 have mis-formatted citations. \n\nii. Line 355 should say Eq. 12 or (12).\n\niii. Should it say \"Figure 3 (left)\" on line 345?\n\n6. There are a few places where things should be defined before they are used:\n\ni. $m$ being the batch size in line 133. \n\nii. $|| \\cdot ||_{TV}$ in Eq. 10. \n\niii. The # symbol in line 274.\n\n7. The literature was in general very well cited, but I think adding some references when discussing dynamical systems theory and ergodic theory in ML would be helpful. Eg: Saxe et al. 2013; Li et al. 2018; Dietrich et al. 2020; Dogra and Redman, 2020. \n\nOVERALL:\n\nI believe this paper is strong and fills an important need in the field. Given that generalization is a major problem in machine learning, and that current approaches based in algorithmic stability have limitations (namely, they require that the algorithmic converge in weight space, which many commonly used algorithms do not do). Additionally, I believe that the ergodic theory, and dynamical systems theoretic more generally, perspective the authors take is a very fruitful direction for the general field of ML to move in. \n\nFor all these reasons, I am giving the paper a 7. That being said, I do believe the points I discuss above in the weakness section (which I believe can be addressed in a straightforward manner) need to be addressed for this score to remain this high. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_Z7pOa-qwEL", "reviewer": "Reviewer_mM1Z", "summary": "This paper lays the theoretical groundwork for studying the behavior (generalization, dynamics) of stochastic learning algorithms: here, the appropriate notion is not deterministic convergence to a fixed-point, but rather various notions of stochastic convergence. Specifically, the paper posits (Assumption 1) that the dynamics of the hypothesis (input-output function) are ergodic. Thus, functionals of the hypothesis may converge over the SGD trajectory, while the parameters themselves may not converge. The paper also discusses relations to existing notions of stability and convergence, and provides a toy analysis for when SGD learning is \"stochastically stable.\"\n", "questions": "See above.", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is very well-motivated and well-written: it correctly points out limitations of prior (deterministic) approaches to analyzing learning dynamics, and it clearly outlines a formalism for studying stochastic dynamics of SGD. The mathematical exposition is clear. \n\nWeaknesses:\nAssumption 1 is very strong, and is not tested with proper experiments. For example: Assumption 1 (and the definition of SAS) involves a supremum over all inputs z, and all test functions \\ell. However, the experiments in Figure 1 only measure several observables, and make no effort to take the supremum over z.\nThis limitation should be discussed in the paper: do the authors claim that Assumption 1 is realistic, or is it merely meant to be theoretically-suggestive, while being too strong to hold in practice?\n\nI am also curious whether Assumption 1 is consistent with the \"Disagreement Property\" in the literature (introduced by [1][https://arxiv.org/abs/2009.08092] and followed-up by [2][https://arxiv.org/abs/2106.13799]).\nThe Disagreement Property in [2] shows that two models trained with different seeds, on the same train dataset, *do not* converge to the same hypothesis function. Rather, the two hypotheses \"disagree\" in their predictions, at a rate roughly equal to the test error.\nThis property seems at-odds with the convergence that's claimed in the present paper, and I'd be curious to hear the author's thoughts on this.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9--HIyEIGMk", "reviewer": "Reviewer_3UBZ", "summary": "The standard notion o stability assumes learning algorithms to be convergent to a fixed point w.r.t. the weights. But, in practice, the weights of deep neural networks optimized with stochastic gradient descent do not satisfy such a condition and they often oscillate indefinitely. Motivated by this fact, the authors propose a notion of statistical algorithmic stability (SAS) that extends classical algorithmic stability to algorithms in which the weights only converge in distribution. The authors also show particular conditions under which such stability condition is satisfied and they discuss the learning algorithms from a dynamical systems perspective. Finally, they confirm their theoretical findings by computational experiments.", "questions": "In my opinion, the relation between the standard notion of stability and the SAS stability is not well investigated in the paper. Which is the relation between them? What about the generalization property of the two? ", "limitations": "I do not see any negative societal impact.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem addressed by the authors is for sure an interesting question. On the other hand, I think that the results could be presented in a clearer way, adding some examples and more discussion would make the paper for sure more readable by the community. For instance, adding specific examples of SAS algorithms would be very useful. Also the presentations of the theoretical results could be better addressed and the reader could be better guided in the meaning of the paper. For instance, giving a sketch of the proof of Thm.1 would be very meaningful. Otherwise, the paper remains quite abstract.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-_c-6_lPO5", "reviewer": "Reviewer_jP3X", "summary": "Traditional generalization analysis assume that a given algorithm converges to a fixed point. This paper studies the generalization of algorithms when the weights converge in distribution. In particular, the authors propose statistical algorithmic stability (SAS), through which they give upper bounds for the generalization bound. Then this paper gives a sufficient condition for an algorithm that satisfies the SAS.\nFinally, this paper provides numerical results to find the SAS coefficient.", "questions": "- My main concern lies on the difference between the traditional algorithm stability and SAS in this paper. \nThe Definition 1 in this paper is based on a deterministic algorithm. However,  [1] gives a uniform stability definition with exception over the randomness of a random algorithm. That is to say, traditional algorithm stability can also handles the situations when learning algorithms that do not converge to a fixed point. I think it would be better if the authors could give more discussions on the comparison between the uniform stability in [1] and SAS. \n\n- The generalization bound in Theorem 1 seems to be dominated by $\\beta$. It would be more convincing if the authors could include numerical results on the order of $\\beta$ when varying the sample size (on clean dataset rather than corrupted dataset)\n \n\n\n\n[1] Hardt, Moritz, Ben Recht, and Yoram Singer. \"Train faster, generalize better: Stability of stochastic gradient descent.\" International conference on machine learning. PMLR, 2016.", "limitations": "It seems that there is no potential negative societal impact of this work.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper is well organized and easy to follow.\n- The idea of analyzing the generalization of algorithms that converge in distribution is interesting.\n- Provides the code.\n\n\nWeaknesses:\n- The significance of SAS is not clearly stated when comparing with traditional algorithm stability.  By taking the expectation over the randomness of an algorithm, traditional algorithm stability can also analyzes the generalization when an algorithm does not converge to a fixed point. See the Questions part for details. \n\n\nMinor issue:\n- The references in the PDF cannot be retrieved. Maybe because the hyperref package is missing.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept