Generalization as Dynamical Robustness--The Role of Riemannian Contraction in Supervised Learning
Authors: Leo Kozachkov
Patrick Wensing
Jean-Jacques Slotine
Venue: Accepted by TMLR ()

Abstract: A key property of successful learning algorithms is generalization. In classical supervised learning, generalization can be achieved by ensuring that the empirical error converges to the expected error as the number of training samples goes to infinity. Within this classical setting, we analyze the generalization properties of iterative optimizers such as stochastic gradient descent and natural gradient flow through the lens of dynamical systems and control theory. Specifically, we use contraction analysis to show that generalization and dynamical robustness are intimately related through the notion of algorithmic stability. 

In particular, we prove that Riemannian contraction in a supervised learning setting implies generalization. We show that if a learning algorithm is contracting in some Riemannian metric with rate $\lambda > 0$, it is uniformly algorithmically stable with rate $\mathcal{O}(1/\lambda n)$, where $n$ is the number of examples in the training set. The results hold for stochastic and deterministic optimization, in both continuous and discrete-time, for convex and non-convex loss surfaces. 

The associated generalization bounds reduce to well-known results in the particular case of gradient descent over convex or strongly convex loss surfaces. They can be shown to be optimal in  certain linear settings, such as kernel ridge regression under gradient flow. Finally, we demonstrate that the well-known Polyak-Lojasiewicz condition is intimately related to the contraction of a model's outputs as they evolve under gradient descent. This correspondence allows us to derive uniform algorithmic stability bounds for nonlinear function classes such as wide neural networks.

Published in Transactions on Machine Learning Research (04/2023)
Generalization as Dynamical Robustness- The Role of Riemannian Contraction in Supervised Learning
Leo Kozachkov
leokoz8@miis edu
Deportment of Brain and Cognitive Sciences Lisa Yong Integrative Computational Neuroscience (ICoN) Center
Massachusetts Institute of Technology
Patrick M. Wensing
pwensing edu
Department of Aerospace and Mechanical Engineering University of Notre Dame
Jean-Jacques Slotine
jjs@mit. edu
Department of Mechanical Engineering Department of Brain and Cognitive Sciences Massachusetts Institute of Technology
Reviewed on OpenReview: https: openreview. net/ forum? id= 5mccff
Abstract
A key property of successful learning algorithms is generalization. In classical supervised learning, generalization can be achieved by ensuring that the empirical error converges to the expected error as the number of training samples goes to infinity. Within this classical setting, we analyze the generalization properties of iterative optimizers such as stochastic gradient descent and natural gradient flow through the lens of dynamical systems and control theory. Specifically, we use contraction analysis to show that generalization and dynamical robustness are intimately related through the notion of algorithmic stability.
In particular, we prove that Riemannian contraction in supervised learning setting implies generalization. We show that if learning algorithm contracting in some Riemannian metric with rate À > 0, it is uniformly algorithmically stable with rate (11AAu), where is the number of examples in the training set. The results hold for stochastic and deterministic optimization, in both continuous and discrete-time, for convex and non-convex loss surfaces.
The associated generalization bounds reduce to well-known results in the particular case of gradient descent over convex or strongly convex loss surfaces. They can be shown to be optimal in certain linear settings, such as kernel ridge regression under gradient flow. Finally, we demonstrate that the well-known contraction of model's oulpuls as they evolve under gradient descent. This correspondence allows to derive uniform algorithmic stability bounds for nonlinear function classes such as wide neural networks.
condition is intimately related to the
1 Introduction
Since the seminal work of Bousquet & Elissceff (2002). the concept of algorithmic stability has been used to analyze the generalization properties of learning algorithms (Mukherjee et al.) 2006 Shalev-Shwartz et al. 2009 2010; Hardt et al. 2016). Roughly speaking, algorithmic stability refers to the notion that small changes to the training set will lead to small changes in the output of the learning process.
In this work, we focus on iterative optimizers within supervised learning setting, where we are given access to number of labelled training points drawn from some underlying common distribution, well loss

---

Published in Transactions on Machine Learning Research (04/2023)
function which quantifies performance. Within this setting, show that algorithmic stability is intimately related to notions of robustness from the dynamical systems and control literature. In particular, we make connection between algorithmic stability and contractive stability (Lohmiller & Slotine, 1998p. Loosely, a dynamical system is contracting if it forgets its initial conditions exponentially quickly.
Contraction analysis has found wide application nonlinear control theory Manchester Slotine 2017
robotics (Chung Slotine, 2009), and synchronization (Pham & Slotine 2007
However, it has only recently
been applied to machine learning (Boffi et al. 2020 Revay & Manchester 2020
Jafarpour et al., 2021 Burghi
et al. 2022 We show that if an optimizer is contructing (Lohmiller & Slotine 1998) in some Riemannian
metric (in precise sense defined below) then it is algorithmically stable. Due to the generality of contraction analysis and the flexibility afforded us by the choice of metric, our theory applies to wide variety of common optimizers for example gradient flows and stochastic minibatch gradient descent descent-operatinnn operating over both convex and non-convex loss surfaces (see Figures and
Figure 1: Example loss surfaces for which our results apply. Left panel: strongly convex and convex loss surfaces (sections 3.1 and 4.2.1). Middle panel: isolated local minima surrounded by basins of contraction (see Theorem Right panel: valley of path-connected global minima (see section
1.1 Related Work
A key early result in analyzing generalization in iterative optimization came from (ardd et al. 2016 which established algorithmic stability for stochastic gradient methods. Later (Mou et al. 2018)) proved similar results for stochastic gradient. Langevin dynamics. Shortly thereafter (Charles & Papailiopoulos 2018) showed that for loss functions satisfying certain geometrical constraints (e.g., the Solyak-Lojasiewice inequality (Polyak] 1963)). ) any optimizer that converges lo global minimum also algorithmicallly stable. Since then, several follow-up works have analyzed the algorithmic stability of accelerated gradient methods, and the tradeoffs between optimization accuracy and algorithmic stability (Chen et al. 2018 Ho et al.
2020 Attia & Koren, 2021). The present work is similar in spirit to Charles & Papailiopoulos (2018), in the sense that we use an assumed stability property (in our case, contraction of optimizer trajectories) to derive generalization bounds for wide class of optimizers. The following section introduces our supervised learning sctting, which is the same setting as in Hardt et al. (2016). and provides necessary background on algorithmic stability.
1.2 Algorithmic Stability Background
We consider a generic supervised learning setting where we have access to n labelled examples, assumed be drawn i.id from an unknown distribution D (Vapnik 1999). We collect these examples into a training set 5 = (21,...,,,,) 2,). The population risk with respect to loss function & is defined as
R EZ-D ((0
where E ITM describes model. We assume that do not know the population risk, use the empirical risk as a proxy
Rs n ((0,z))
The difference between the population and empirical risk denoted as the generalization error of model
A gen
( R[0] Rs [0]
2

---

Published in Transactions on Machine Learning Research (04/2023)
We now define the stability of an algorithm, and relate it to this generalization error. Consider algorithm A that takes in S and outputs model (e-g., parameter vector 0).
Definition 1 (Uniform Algorithmic Stability). An algorithm A is e-uniformly stable if for all data sets S, S such that S and S' diffrr in at most one example, we have
sup supEA(((A(()) E(A(S") se
(1)
where the expectation is taken over the randomness of A, if any.
A key result in learning theory states that uniform stability leads to generalization in expectation (Bousquet
& Elisseeff 2002] Shalev-Shwartz et al., 2010 Hardt et al. 2016). In particular, we use Theorem 2.2 of Hardt et al. (2016)
Theorem 1. Let A e-uniform stable and let Es.A denote an expectation taken over the samples and the randomness of A. Then, EEs.A gen (A(S)) c.
If the output of A is some parameter vector 0 and we assume that loss function is L-Lipshitz for every example 2j with respect to some norm || Il, then the difference between two trajectorics of an optimizer trained on set S and 5" can be used to bound the generalization error, because
Eall((Og,2) E(0g, 2) - L A 0g
(2)
Rather than only considering the Euclidean distance ||0g - 0s 1. in this paper we consider the geodesic distance (0s, 0s+) computed on a Riemannian manifold MM (RE", .M) (Figure Here M(0,)) E Rm is the positive definite metric associated to M. There are many optimization settings for which the geodesic distance between two points opposed to the Euclidean norm is the
natural distance measure to consider (Amari, 1998 Wensing & Slotine 2020). The main takeaway of this paper is that Riemannian contraction implies generalization in supervised learning. The details about this generalization (e.g., its dependence on the number of samples n and the training time 7) depend on the dynamical equations of the optimizer, as well as the geometry of the loss landscape, as we will see. We now provide background on nonlinear contraction analysis before stating our results.
1.3 Nonlinear Contraction Theory Background
Consider a state vector R", evolving according to the contimuoss time dynamics
0 = f(0,t)
(3)
where it assumed that all quantitics are real and smooth, so any required derivative or partial derivative exists and is continuous. Then we have the following definition
Definition 2 (Contracting Dynamical System). Denote the Jacobian of 3 by (0, If there exists
symmetric positive-definite metric M(0,t) IR" x R + pm and scalar À > 0 such that the following differential Lyapunov matrix equation is uniformly satisfied in space and time
M+ MJ J < -2MM
(4)
then the geodesic distance defined with respect to M between any two trajectories of converges to zero exponentially, with rate X, and 3 is said to be contracting. Discreto-time contraction can be defined similarly (Lohmiller Slotine, 1998). One may consider more generally in (4) a. (uniformly positive definite)
instantaneous contraction rare X(t).
1.3.1 Robustness of Contracting Systems
Contracting systems are robust to disturbances, in the following sense. Assume that 33 is contracting in metric M T(0, ((B, with rate X. Now consider the same dynamics as perturbed with some disturbance
0, = f(Op: 1) + d(Op.))
(5)
3

---

Published in Transactions on Machine Learning Research (04/2023)
0s
S
Time
Figure 2: The geodesic distance between optimizer trajectories 0s and 0s- If the optimizer is contracting with rate A, this distance, denoted by the dashed line in the figure and (0s Ogt) in the text, shrinks until the two trajectories are within a ball of radius (
The geodesic distance dm 0p) satisfies the differential inequality
d dd 0p) + Ad, 0,) [T(O,)))(0))) t)l
(6)
Assuming there exists finite constant D such that [d t)ll - D uniformly,
6 implics
R(t) S XR(0)e M Dx A
(7)
where R(t) = [I0(t)= - (()l and X denotes an upper-bound on the condition number of T. Likewise for the discrete-time dynamics contracting in some metric with rate 0 p < 1
θ f++1=((0.,t)
the analogous result is
DX
R(I) XR(O)R' + (1-#)
For proofs of these statements refer the reader to Lohmiller & Slotine 1998 (section 3.7, vii) as well Del Vecchio & Slotine 2012) and Proposition 1 in the appendix of Zhang et al. (0021)
If we interpret 3 as an algorithm, then the only source of indeterminacy in this algorithm is the initial
condition 0(0). Therefore if (3 is always initialized within a ball of radius C/2 of some reference point, then may be stated in expectation
Ex(R()) S ExlxR(0)e-* D XCe SxCe- DX
(9)
where we have used the linearity of the expectation value operator, well as the assumption [A(R()) < C. Let us also state a new robustness result using instantaneous contraction rates, which will be useful later. Theorem 2. If the instantaneous contraction rale X(1) > of system tends towards a finále limil X with À 0, then R(t) tends to the bound 0 < R(t) A
xD
Proof. By analogy with (lotine & Coetsee
1986 define Rs R sat(R/o) where Φ
One has x(e
xD
d Ra 2 S 2R
dt
As + +o0, the rinht-hand side of the above incquality tends to zero, which in turn implies (from the lllowal lemma) that RA tends to zero, i.e., that R tends to the bound R < doo X
L
4

---

Published in Transactions on Machine Learning Research (04/2023)
1.3.2 Geodesics and Bounded Distortions
To ensure that our results are coordinate-free, we show that the "distortion factor' between the geodesic dis- lances computed along two different manifolds Mi and M2 is uniformly bounded. The practical implication is that geodesic distances as measured in two different metrics can differ by no more than a constant factor, which precludes any situation where a system is stable in metric (gcodesic distances between trajectories shrink to zero) and not stable in another metric (geodesic distances do not shrink to zero). Theorem 3. Consider beo Riemanmian metrics M1,0,) and M2(0,1) salisfying
an I 3 ( t) 3 8
(10)
02 I h (2 = 13T
(11)
with a4, > 0. Then the corresponding geodesic distances evaluated between two points, 0 and y, satisfy the bound
S d.M (0, V B2 dd,(0.y)
B1 a2
S
Note that the lower bound the metric follows from the requirement that to define a proper metric, the matrix M(O,t) must be uniformly positive definite for all 0 and t. The upper bound can be ensured when c.g., the norm of the metric is Lipshitz with respect to the state, and the state remains within finite set (as is the case with contracting optimizers, as we will see).
2
Main Results
2.1
Contracting Optimizers are Algorithmically Stable
In this section we prove our main result. for continuous-time optimizers using the entire training batch. We start with this case because it is the simplest. Later on, we provide the same result for stochastic, discrete- time optimizers such as mini-batch stochastic gradient descent. We assume that parameter update is sum-separable with respect to training set S
1 = n 1=1
Øs = G(Os,
Σ
g 21)
(12)
In this case the output of algorithm A(S) is the vector 0s obtained by simulating 12) for time t. We also assume that ||g]| S &, for some constant &. we interpret g as the gradient of some loss e, then this corre- sponds to assuming that is f-Lipschitz. Finally, we assume that the optimizer always initialized perhhaps randomly- within ball of radius C/2 around some reference point. Now consider the same parameter update with respect to training set 5", which differs from S in one example
0g: G(Os,, 8")
(13)
We can now state our first main result.
Theorem 4. [Contraction Implies Algorithmic Stability] If the dynamics M M= t) ((O,))) E) with rate X, then A is uniformly e-stable, with
12 are contracting in metric
x MC MC 2xLE
(14)
Xn
where denotes uniform upper-bound on the condition number of T(0,t), t). Going forward we refer to Catab = 2x14
Proof. We shall write 13 as perturbed version of 12 and then apply the robustness property of con- tracting systems to yield the result. Letting & denote the index of the replacod element in S', we can write gg as
gg
g (
23)
[g(0s.22) 2x) - g(0s,++))
1=1
5

---

Published in Transactions on Machine Learning Research (04/2023)
where we have just subtracted out the term involving 2n from the sum, and added in the replacement term -k- This may be viewed as a perturbed version of 122 with disturbance
O 2h, t m)]l 11 (g( (0 2x) g(0s, 2(10 - 2 D
(15)
Plugging D into 9 multiplying through by L because of 2 and taking the expectation EA to produce R(O) yields the result.
Remark 1 (Leave-One-Out Stability). As pointed out in [Bousquet et al. 2020 for interpolation algo-
rilhms (such as, e-g,, the highly overporomelerized searches common in deep learning) is more meaningful to analyze leave-one-out, stability, rather than replace-one stability as we just did. The some dynamical ro- bustness argument applies immediately to this case, with D and therefore Estob reduced by factor of two, 15 is replaced by
- g(0s 2t)1 5
||d(0s,, 2k, 2/ n)ll
Remark (Generalization with High Probability). woell-known limitation of using algorithmic stability to derive generalization bounds is that the bounds only hold in expectation. However, one con use Chebyshev' 's inequality to derive generalization bounds that hold with high probubilily Bousquel& & Elisseef] 2002 Elissee ct ol. 2005; Feldman & Vondrak, 2019; Bousquet et al. 2020). It is well known that these bounds tight in the case when algorithmic stability scales with 1/n,, see e.g,, Theorem 12 and Remark 13 in (Bousquet & Elisseefj (2002). Theorem / shows that (after exponentially decaying transients) deterministic contracting optámizers generalize with rate 1/n. In Section 2.2 Theorem 5 will show that this 1/n scaling also holds for the stochastic optimization case.
Remark 3 (Scaling Dynamics Does not Change Generalization Rate). Note that if we 'speed up" the dy- namics in 12 by some factor k >
G(Os, - RGG(Os,S)
one might intuitively expect the contraction rate to be scaled by k as well (A + KA), which would allow an arbitrary increase of the rate of genernlization
(14 by simply incrensing K. Note however that this is prevented by the presence of & in q14p, which is also scaled by K. The terms in the numerator and denominator therefore eancel out, leaving Estah unchanged. The exponentially decaying term in 14 however,
decays with new rate kλ.
Remark 4 (Tipschitz Assumption). As pointed out in Hardt et al. 2016), there cases where L as defined in 2 may not erist. For example, strongly conver functions have unbounded gradients on R. In this case we will overload the symbol L to be
I supsup VE(0,2))l: BEn z
where Ω denoles a compact set where the ilerales of the oplimizer are known to remain when initiillzzd in a given compact region. For contracting optimizers and f-smooth loss functions (V26 I (T), L, is always finite. In particular, if we have some compact set of initial conditions and our optimizer contracting (in a uniformly pnsitive-definttt metric), then the trajectories of the optimizer from any of those initial conditions will remain bounded. Indeed, any one trajectory will connerge to fired point, and all the others muust remain in tube around its iterates [Lhhmäller & Slotine, 1998). With this construction, we have direct bound the diameler of the set that the ilerales of the oplimizer must remain within which we denole diameter(S)). In this case we have L < 3 diameter(S)).
2.2 Stochastic, Contracting Optimizers are Algorithmically Stable
In this section we show that a variant of Theorem holds for stochastic, discrete-time optimizers (for example stochastic gradient descent). Consider the iterative optimizer
b Σ
05 b
$ 24)
(16)
1=1
6

---

Published in Transactions on Machine Learning Research (04/2023)
Trajectory
Trajectory
800
Global Minimizer
700
600
(6'00
300
200
100
Figure 3: Left subplot) Two trajectories of a contracting optimizer, seeded from two different initial conditions, evolving over non-convex loss surface (Rosenbrock function, f(z, y) 100(2² y)² (x 1) Both exponentially converge the global minimizer of the function. Trajectories superimposed over a contour plot of the loss surface. Right subplot) A different view of the same optimization process, more clearly displaying the non-convexily of the loss surface.
where 1 < b S n is the size of the mini-batch and z; are samples drawn randomly from set S. As before we assume that g smooth and bounded as |lg/l S &. Since (16) defines a discrete-time, random dynamical system (Tabareau & Slotine, 2013) we have define what we mean by 'contraction'. In particular we will rely on an assumption of "contraction in expectation', by which we mean the following. Consider two instantiations of the same discrete-time, random dynamical system
0111 = f(0,,t,)
Yt+1 f(y,,t, t,
with potentially different On and yo, and where I' denotes a particular realization of stochastic process which the same for both O and y. In our casc, this stochasticity stems from the random sampling of training set datapoints to form a mini-batch. We will say that this system is contracting in expectation if for sequence of metrics Mo...., M, we have
EAldM (f(0,,t,)) f(y,, t, ())] S (O..
where 0 μ < and each metric is bounded M.ni. A M, = Mmaz.. We state the following theorem
Theorem 5. [Contraction Implics Algorithmic Stability (Stochastic, Discrete]] Assume 16 is contracting in expectation, as defined above. In this case A is uniformly e-stable with bound
2xLE
c
E LXCRt (1 pm
(17)
Proof. See appendix section A.1
Remark Note that [7] does not depend on the batch size, b. Intuitively, this is because the resampled dalapoint z will oppear given batch with probabilily b/n, but the magnilude the disturbance this causes the opttmizer dynamics scales with 1/b. These two terms interact multiplicatively, that the b terms cancel, leaving only the 1/n scaling.
3 Examples of Metrics
3.1 Preconditioned Gradient Descent On Strongly Convex Loss Functions
In this example we show that our theory reproduces known stability bounds for gradient descent on strongly convex losses. To illustrate the role the contraction metric, we consider preconditioned gradient descent. Consider this descent over an empirical loss function which 7-strongly convex with respect a parameter vector
-PP--V

---

Published in Transactions on Machine Learning Research (04/2023)
where P is positive-definite and symmetric matrix. Denote the largest and smallest eigenvalues of P Pmar and Pmin; respectively. The Jacobian of this system is
00
-
00
Picking the metric M = P, we see that
27 P
PJ PJ+J'P=22V' -2 S
Pmaz
and thus the system is contracting in metric P with rate 7/ Our algorithmic stability bound is therefore
pd 2L
Estab
Prain 7n
Where L is given by 4 Note that in the case of regular gradient descent, without preconditioning (i.e.,
P = I) the above analysis shows that À y and 1. Plugging these numbers into equation [14] yields the following
2L
Ssabb 7/2
which is precisely the result of Theorem 3.9 in (Hardt et al. 2016
Remark 6 (Natural Gradient Geodesically Strongly Convex Losses). Natural gradients popular way to incorporate geometric information about the loss surface into gradient-based optimization technáques (Amari, 1998 Zhang el al. 2019). An equivalence between g-Strong Converily and global contraction of natural gradient flows was given in (Theorem 1, (Wensing & Slotine 2020)). That is, the optimizer dynamics
θ (
are globally contracting in the metric M if and only if C(0) is geodesically strongly conver over M. this case Theorem 4 of the present work applies immediately, precisely the same fashion as the preceding subsection.
3.2 The Choice of Metric is Critical
We now consider simple two-dimensionall, analytical example where failing to include metric leads to inconclusive stability and generalization bounds. Consider minimizing the classical nonconvex Rosenbrock function (Figure
4, = ( 02)² + (01 1)²
where 0 = [e 82]² and is a bounded random variable whose expected value is 100. The mean loss over training samples is
4 = (a) 02)² + (01 - 1)2
n
where (a) denotes the empirical average
(a)
a
We consider the large n limit, where (a) ~ 100. It was shown in Wensing & Slotine (0220) that when 100, the natural gradient descent dynamics
d 0 = -0-
dt
8

---

Published in Transactions on Machine Learning Research (04/2023)
is contracting with rate > 0 in metric
40 + -200 01
-000
M(
100
this implies generalization rate of order 1 1/na. We can now ask what happens if we use the identity metric in the stability analysís, instead of M()). It can be shown that the Jacobian of the natural gradient descent dynamics above
By Theorem 4
00 J
0 -1
-
= 2
00
01
without the metric, the contraction condition are uniformly negative definite. Howover, it readily shown these eigenvalucs are
4 requires that the eigenvalues of the symmetric part of J
A1 oP 0 20 - 5 -2
Because A is always positive, the natural gradient descent dynamics are not contracting in the identity metric, and thus one would not be able to derive generalization bounds in this case.
3.3 Identity Metric is Optimal for Ridge Regression
In section 3.2 we demonstrated that the choice of metric can be critical for establishing stability and generalization bounds. For certain nonlinear optimization problems, this metric will naturally be state- dependent (such as in natural gradient descent). However, for other optimization problems, in particular linear ones, a constant metric to be expected. this setting, one can ask there exists an optimal metrie in terms of providing the best generalization bounds. In the case of ridge regression, we prove that the answer yes, and that this metric is in fact the identity metric. This is sharply contrasted with nonlinear optimization problems, where the identity metric can fail to produce stability and generalization bounds (see section 3.2
For constant metrics, our stability bound estab X depends on the condition number of the contraction metric (specifically its square root) to the contraction rate measured in that metric. Different metrics yield different Cstab, so is natural to ask whether an 'optimal' metric M Moptimat exists, such that
Estab Estab (Moptimal) S (M)
While finding such metric is in general not easy to do, show that it is possible in the case of gradient descent for kernel ridge regression Shhae-Tayloo et al. 2004). Kernel methods (which are inherently linear) can be used to derive insights into nonlinear systems such deep neural networks (Jacot et al. 2018 Lee et al. 2019 Fort et al., 2020: Canatar et al. 2021). Without loss gencrality, we assume an element-wise feature map such that for a matrix E Raxx the matrix oxX) E Rax= satisfies ((X);; = (X.;). The squared-loss
for kernel ridge-regression is
L 2n Σ (o(x)) - v2)² a
2 [w]
where the dxx;)) are feature row vectors, R the linear model parameters to be learned, and the
yi E IR are target labels. The parameter > 0 is the regularization parameter. Under gradient descent
w = - VL the Jacobian of the optimizer dynamics is
Ow dw
(-
where G L [xx)) and X E Rxd symmetric, constant, and negative-definite. Thus, the optimizer contracting in the identity metric with rate \ Xmmin (G) a, where Amin() (:) denotes the smallest eigenvalue. We prove the following
x is constant matrix with x; as the 1th row. The Jacobian is
Theorem 6. For kernel ridge regression, the algorithmic slabilily bound stab is minsmized for M M

---

Published in Transactions on Machine Learning Research (04/2023)
Proof. Recall that for an arbitrary, constant metric we are looking for positive-defniite symmetric Q such that
MJ - JM = - < -2M
Ignoring for a moment, we can ask: out of the set of all possible metrics, there a metric that yields the largest contraction rate X? An interesting result from linear dynamical systems theory is that the answer is fact yes. While there can be many metrics for linear syslems that give the largest possible X, one can always be found from setting Q = I and solving for M (see, e.g., section 3.5.5 in (Slotine Li 1991)). Since J is symmetric, in case this metric corresponds to the diagonalizing metric
[ J-J -:::2200 ( +
Miargest
The contraction rate Atargest corresponding to this metric
Atargest
2 Amar (Maargest) Amin (G) + a
which is precisely the same contraction rate measured in the identity metric. Thus X Aargest- Now simply use the fact that X1 = S XM for any metric. Since M = I corresponds to the largest possible À and the smallest possible x 1, the ratio of x to À is minimal over all possible M when M M=I. Thus
Estab (I) S Estab(M)
60
M =
M =
40
20
0
1
2 3
4
0.10
0.15
X
A
Figure 4: For fixed G E R3x3 randomly generate and solve for M. We then calculate the ratio a/ (the only metrie-dependent terms in our algorithmic stability bound). We repeat this procedure 4000 times. Left subplot) The ratio X/ plotted against X. Right subplot) The ratio X/AM bound plotted against AM- Details are in the main text. These plots illustrate our theoretical result that the identity metric gives the optimal (i.e smallest) algorithmic stability bound. They also illustrate the reason: the identity metric simultancously obtains the smallest condition number and the largest contraction rate, thus minimizing the ratio of the former the latter.
This result is illustrated Figure To create this plot we generated random 3R333 Then we generated random Q and solved the Lyapunov equation for M using an implementation of the Bartels- Stewart algorithm in SciPy (Bartels & Stewart 1972 Virtanen et al.) 2020). In addition to these random Q, we also set Q I to obtain the M corresponding to the largest. X. For each of these Q and M pairs, XM is given by Am Amaz(M) SciPy) and then performed a singular value decomposition to obtain X. One interpretation of this result there is no 'better' coordinate system. That is, there no coordinate transformation we could perform on the state vector w which would give us tighter algorithmic stability bounds. This is because a constant metric M TTT corresponds to the coordinate change Tw.
Ami...Q) (Slotine & Li 1991). We computed T via Cholesky decomposition (also using
10

---

Published in Transactions on Machine Learning Research (04/2023)
3.4 Immersions and Embeddings
Early concepts in machine learning, such as support vector machines (Vapnik) 1999 and kernel meth- ods Sahawe-Taylor et al. (004). build on the idea that immersing data points into a higher dimensional space can often simplify learning. Using the same intuition, we explore the potential to simplify the con- traction analysis of an optimizer through the use of a gigher-dimensional immersion. Contraction properties of immersions in higher-dimensional spaces can be easily translated in terms of metrics the original low dimensional space, as pointed out in (Yi Manchester 2021) in the special case of linear Koopman embed- of compressed representations and lower
dings. Conversely, modern machine learning makes extensive dimensional embeddings of the original space [Goodfellow et al. 2016), e-g. through the use of autoencoders. We show how contraction properties in the compressed (or latent) space can be related to contraction prop- erties of the original space. In both cases, the generalization bounds derived in this paper can be readily applied.
Immmersions Consider immersing a lower dimensional state 0 E R into higher dimensional onc E R with d 2
2 (0)
(18)
where (0) is continuously differentiable, 80 has full column rank, and the vector fields à and are com- patible (i.e., for each 0, 2 at (0) agrees with Assume that the higher dimensional system is contracting in some metric M(z, t)
de 0 al 0).
30
8z 8z'M(z, t)oz S -2X 0z"MM2z. t)oz
(19)
dt
with 8z a differential displacement (Lohmiller Slotine 1998
and a strictly positive constant. Since
abb
8z 00
60
equation 19 can be equivalently written
d 60 Mo S -2X 50 Mo(0,
dt
with
Os
(o, do M(v(0), t)
d0
This shows that the original system is also contracting, in metric Mg with the same contraction rate X. More generally, one can consider differential immersion of the form
8z 000=T(0.000 T(0,0)50
with T(0, of full column rank, and assuming as before that dóz and & 450 are compatible. Note that such an immersion does not require the above equation be integrable, i.e., an explicit z to exist in 188 It corresponds to immersing the vector field for O into one defined in some higher dimensional Riemannian manifold rather than Euclidean space. By the same argument above, contraction of the higher-dimensional system in the metric (()( t) implies contraction of the lower dimensional system at the same rate in the metric
(e, = (0, M()(O),t) T(0,t)
This result may simplify the contraction analysis of the lower dimensional one. In particular, if the higher dimensional system is contracting in a constant metric M, so that M = o in 4 then we can immedi- ately conclude that the lower dimensional system is contracting in the time-varying, state-dependent metric Mo () = (0, M T(0,1) without having to deal explicitly with the time-derivative that metrie.
In the gencralization bound of Theorem 4 both the contraction rate À and the 1/n scaling remain un- changed. In addition, decomposing M())(0), as M()((). t) B"
(1))).) x is now replaced by x = XTXB where Xr and X denote upper bounds on the condition numbers of T(0, 1) and B(b((0), t).
11

---

Published in Transactions on Machine Learning Research (04/2023)
Embeddings The same logic can in fact be applied to embeddings in lower-dimensional spaces. Assume for instance that there exists high-quality auloencoder for the original state 0 E IR. In other words, there exists an encoder E' and a decoder D such that z = E(0) E IR' and (ideally) D(z) = 0, with d I m. Assume the compressed (latent) z dynamics are contracting with rate À a metric of a specific form,
d oz' (2, 1)ó2 < 22 oz (2,12)) di
OD T Mz ()
0D dn
with
M(z, () dz
then the original 0 dynamics are contracting in metric M(E(0).t) with the same rate X. This follows directly from substituting above the identity 80 dz generalization bounds in the latent space or the original space.
a2 óz and using z E(0). One may choose to compute
4 Weaker Notions of Stability
Contraction imposes a strong condition on trajectories: they must converge toward one another exponentially. Such convergence can be expected for parameter trajectories around isolated local or global minima, as discussed above. However, in modern machine learning, one often observes parameter trajectories which converge towards common basin of low/zero loss, where minima may lic among a low-dimensional manifold Garipov et al. 2018 Draxler et al. 2018: Fort al.) 2020 Liu et al.) 2021). To accommodate these cases, now discuss several weaker notions of innttraction-spccfffeen
local contraction, semi-contraction, partial contraction, and output contraction which also yield 'well-behaved" algorithmic stability bounds.
4.1 Loss Surfaces with Many Local Minima
A contraction region (i.e., a forward invariant region of state space that satisfies Definition 2 for au- tonomous system contains at most one equilibrium point (Lohmiller & Slotine 1998). From this it follows that gradient descent over a loss surface with many local equilibria cannot be globally contracting. For- tunately, Definition 2 holds within a subset of state-space, and additionally the system can be shown to remain that subset for all time (i.e., the subset is forward invariant), then that system locally contracting. This motivates the following general result, as well as an optimization-specif remark.
Theorem 7. Consider the system (3) initiaaized inside an inner Euclidean ball of radius b, which is fully contained within an outer contraction. region (which we also assume without loss of generality to be a Eu- clidean ball) of radius B > b. Assume that (3) stays within the inner ball for all time. Now consider the perturbed dynamics (5) If B 2 b(x+1) xD then 5 slays within the ouler contraction region for all lime,
and the robustness result 7 holds.
Proof. By 1, the perturbed trajectory will at most distance xb + X from the unperturbed trajectory. Since the unperturbed trajectory is always contained within a ball of radius b, this implies the perturbed trajectory is also contained in ball of radius b + xb X assuming stays in a contraction region. To
ensure that it does in fact stay within a contraction region, we must have that B 2 b(x + 1) +)++3 xD
Remark 7. In the case of continuous-tim optimizer equilibrium point 0 enclosed by the contraction region
12
we have that Og converges exponentially to the
0 0sll S xe
Arb
Since 032 is a particular trajectory of the optimizer dynamics, by robustness we also have
2xE
|10 - 0s $ xe xx6
An
by the triangle inequality
2xE
0 0s- S 2xe
2xe->xp
An
this puls the following lower bound on the size of the contraction region B
2xE
B> 2bx +
An
12

---

Published in Transactions on Machine Learning Research (04/2023)
4.2 Semi-Contractin Optimizers
If the oplimizer is not strictly contracting (A > 0), but instead is semt-conlracting (i.e., X 2 0) then our algorithmic stability bound Estab is not independent of the training time. This is because the geodesic distance d0, 02) between unperturbed and perturbed trajectorics evolves according to
(0.00 Adm 8p) S ()
If the only information we have about À is that it is non-negative, then we only bound the distance between trajectories
dm(0, 02) & t)d +)
Considering the disturbance bound |ld(0p. t)ll I 28 leads to the algorithmic stability bound
2x T R(O)
< T
(20)
This bound holds generally for contracttt systems. However, without additional information about the optimizer dynamics, this bound gets worse as + oc. If we know additional information about the dynamics-for example, that they are modulated by decaying learning rate-much tighter bounds can be obtained. We show this with the following example.
4.2.1 Example: Gradient Flows on Convex Losses
Here we show how the above analysis reproduces a well-known result from Hardt et al. 2016) regarding the algorithmic stability of SGD on convex (but not strongly convex) losses.
Assume that the Hessian of the loss function is positive semi-definite
V2L 0
and consider the gradient flow with learning rate scheduler (Goodfellow et al. 2016
= -
where att) 2 0. This optimizer is semi-contracting the identity metric, since
à0 =
00
In this case the disturbance term in Theorem is the same as before, only with an additional a(t) factored in. To facilitate comparison with Hardt et al. (2016), we assume as they do that the optimizer is always initialized at the origin (i.e., R(O) = 0). The Euclidean distance between the optimizer trajectories on training sets and S' evolves according
where D = 2L/n. Integrating this incquality and setting R(0) = 0 yields the algorithmic stability bound
212 c n J1=0 a(t)dt
which is the result of Hardt et al. (2016), Theorem 3.8. We remind the reader that the extra factor of L is picked up from
This result helps explain why a decaying learning rate is a useful strategy in deep learning if the learning rate decays quickly enough (e.g., exponentially). the above integral converges, so that n and T do not compete with each other, as they do (20).
Remark The equivalence between semi-contraction of natural gradient flows the natural metric and geodesic converity was recently prouen in Wensing Slotine (2020). Thus the above algorithmic stability bound exlends immediately to this case.
13

---

Published in Transactions on Machine Learning Research (04/2023)
4.3 Output Contractions, Neural Tangent Kernels, and Polyak-Lojasiewvn
The same robustness arguments developed above can be applied to oulpuls of nonlinear models, through the concept of Neural Tangent Kernel (NTK) (Jacot et al. 2018). While so far we have been using contraction of the model parameters 0 to derive generalization bounds, for this section will use the contraction of the model outputs to derive generalization bounds. NTK training may be viewed as contraction on a Hilbert space, a special case of Riemannian manifold, allowing a straight application of the robust arguments developed above. As we will show, contraction of the model outputs is a consequence of using gradient descent /fscent/floww together with mean-squared loss, and does not require any additional assumptions, such convexity of the loss with respect to the model parameters.
Consider the following nonlinear model Fø, parameterized by a set of weights 0 E R". For each input vector X; the model produces a p-dimensional output. We denote this output y.- We will also find it useful to define a vector y obtained by stacking these vectors
Y1
y, == = F(x,) E R
and y
E RD
(21)
yn_
We will assume that Fo(x;) is Lipschitz with respect to the weights 0, namely that there exists some バ 2 0 such that
[V>F(x)ll2 x
We will also assume that the model is sufficiently overparameterizel Liu et al. 2021 Arora et al. 2019 Nguyen et al. 2021) so that the NTK, H E Rupxup, is positive definite
1 Vo. Voy - Ao with Ao > 0
With these assumptions in hand, the main result of this section is as follows.
Theorem 8. Using gradient flow together with mean-squared loss, the overparameterized model defined in 21 is algoritlemicully slable with rale
Estab O Aov'n
where do > a uniform lower bound on the smallest eigenvalue of the Neural Tangent Kernel.
Proof. As in the previous sections, we will consider training this model on two datasets S and S' which differ at single datapoint at index We will focus on the case where the parameters 0 of the model defined in (21) the notation yi and Os when referring to the model learned by training dataset S, and the notation y' and Os when referring to the model learned by training on dataset S'. Similarly, to refer to the replaced datapoint we will use the notation x to denote the input and y's to denote the desired output. To begin, we note that ( is agnostic with respect to what we define as the outputs of the optimization algorithm A. this section, we consider the outputs the trained model defined in (21) as the outputs of the optimization procedure. That is
trained using gradient flow. To distinguish between the two different models,
will use
yt + oo) A(S)
as in we will assume that the loss function is Lipschitz with respect to the model outputs
Vi EAlle(y,, - <y', =)]] < L, FAlly; yíll
(22)
The goal of this section is to show that the number of training samples + co, the distance lly: y'll shrinks to zero, which implies a vanishing generalization gap via ( With this notation in hand, consider the time evolution of the output y:
J. F(x.
-
0s
1 n
V F(x,) (ee
(23)
14

---

Published in Transactions on Machine Learning Research (04/2023)
Using the same idea in the proof of Theorem dynamics of yi.
we view the dynamics of y' as perturbed version of the
J. Veg. F(x))"
0s
1 =
Σ j=1
Ve F(x:) Fox +.(()
(24)
di
where the disturbance term d:(t) is given by
(t) = Vog F(xs) (e (yy.
with & being the index of the replaced element in S As in previous sections, the effect of this disturbance term is to "subtract out" the gradient corresponding to index k in dataset S, and to "add in" the gradient corresponding to index k in dataset S'. The norm of the disturbance term is upper-bounded simply as
2xL
|d <
(25)
Note that this disturbance term applies to each model output separately, whereas the NTK perspective emerges when considering all model outputs jointly and using the mcan squared loss function. To obtaín the final generalization bound using (25). we also have to consider all the outputs jointly and use the mean squared loss function. The time evolution of the stacked vector y 21 is obtained by taking the time
derivative and substituting in 23
d = H(t) (y ya) with H(t) 0gg Vo,y 0
Y
y
(26)
dt
where Ya is the stacked vector of desired model outputs, defined analogously to y. The matrix H(t) the NTK time The vector y' follows perturbed evolution
5' -H ( -Fa) + a(t) with -(11=- V 20
with d(() is obtained by stacking the disturbance terms d(((), analogously to and Ya- Recent works have
shown that for certain sufficiently overparameterized neural networks, H(t) remains strictly positive definite
throughout the training process (Du et al. 2018 Arora et al.) 2019 Huang & Yau 2020 Liu et al. 2021
That is, there exists a strictly positive constant A > 0 such that
H(t) > Ao
(27)
Because the dynamics y are contracting with rate Ag, and y = ya a particular trajectory the dynamics (since in that case d 0), we can conclude that y will converge towards Ya exponentially. Similarly, y will converge to a ball of radius D centered around Ya, where ||||| s D. We can determine as follows
4,2 n²
2kI.
||||
| <
=
= D Vn
where the first incquality was obtained by substituting in transients of rate λo, we have that sup, Ily: yill Ily y'l
25
This analysis shows that, after exponential
2xL
vo
Remark 9. The generalization bounds achieved above using output contraction scale 1/ /n, while the generalization bounds achieved using parameter contraction (Theorem 4 scale as 1/n. Intuâtively, this is becouse the oulpul veclors (21] interact with each other through equation (26). While resampling produces a disturbance of norm 1/n for each individual output vector, these disturbances can be amplified through coupling via 226 In particular, each individual disturbonce term has squared norm on the order of 1/n². Adding these squared norms together, one finds that the total disturbance has squared norm of the order of n/n² 1/n. Thus, the lotal disturbance has norm the order of 1/ Vn.
15

---

Published in Transactions on Machine Learning Research (04/2023)
Equivalence of Polyak-Lojjasiewiez and Output Contraction in the NTK Limit Here we relate the well-known Polyak-T.ojasieviczz (PI.) condition to contraction of the model outputs in the NTK setting, Specifically, we consider the notion of μ-PL* introduced in (Liu et al., 2021 A loss landscape satisfies the μ-PL* condition with μ > if
|| 2 μu
(28)
uniformly. It was shown in Liu et al. (2021) Theorem 1, that uniform positive definiteness the Neural Tangent Kernel sufficient for the mean-squared loss landscape to satisfy the μ-PI.* condition with μ Ao.
where A uniform lower bound on the smallest eigenvalue of Neural Tangent Kernel (27
VoCIl (J v.) H() Va) 2 Aol Fall AgC
(29)
Equation 29 shows that if the loss landscape L satisfics μ-P uniformly, then the neural tangent kernel H(
is uniformly positive definite, which in lurn implies oulpul contraction, i.e., contraction of the y dynamics (26)
in the section above. This is true for any nonlinear model, and does not require an infinite width assumption.
We now show in the wide network regime, where the Neural Tangent Kernel becomes constant during training, contraction of the model outputs equivalent to the positive definiteness of the Neural Tangent Kernel. Thus, contraction of the model outputs implics the p-PL* condition. Indeed, the dynamics of the model outputs in the nede-network regime may be written
d dt Val H Fa)
where H H now constant. Because this a linear time-invariant dynamical system, and H is symmetric, it contracting if and only if H is positive definite for linear systems, global asymptotic stability, global contraction, and cigenvalues with strictly negative real part are all equivalent conditions. Thus, in the wide network limit, where H is constant and symmetric, uniform positive definiteness of the Neural Tangent Kernel is equivalent to contraction of the model outputs.
A Generalized Polyak-Lojasiewicz Condition with Metric The preceding paragraph establishes a connection between PL and output contraction. Given the prevalence of the metric in contraction analysis, this suggests generalizing the p-PL* condition include explicit metric terms.
Assume for instance that the parameter vector 0 is being updated according to natural gradient flow
θ = - V0
where M-)(0) 2 aT a symmetric positive definite matrix. The generalized PI. condition
VoL Q(0)o uL
where 0 < Q(0) = 31 bounded and symmetric, guarantees that the loss L converges exponentially to zero with rate op/B,
dt C= -
Vo
ap 3
4.4 Partial Contraction and Virtual Systems
In some cases, 'pure' contraction analysis may be hard to do. For example, when an optimizer has an adaptive learning rate, this can significantly complicate the calculation of the Jacobian. To deal with these difficulties, we make use of a generalization of contraction known as partial contraction, introduced Wang & Slotine (2005) and further discussed Jouffroy Sloting (2004).
Definition 3 (Partially Contracting Dynamical System). Consider the system ing) and an auxiliary, virtual system of the form
3 (not necessarily contract-
y g(y,0,1)) 0,
Assume that this virtual system is contracting (with respect to y) metric M with rate X, and also that g( 0,t) f(0.t) t). We then say that (3) partially contracting. If one particular trajectory y(t) of the virtual system is known, then all trajectories of (3) converge exponentially towards y().
16

---

Published in Transactions on Machine Learning Research (04/2023)
Robustness properties of virtual contracting system lead directly robustness properties for the original system (Del Vecchio & Slotine 2012), which need not be contracting itself. This result provides a direct bridge for using virtual systems analysis to study generalization.
4.4.1 Adaptive Learning Rates
The results of the previous sections can be extended to include the presence of stale-dependent, time-
varying, learning rate [Zeiler 2012 Kingma & Baj 2014] Goodfellow et al. 2016 Liu et al. 2019). In particular consider the learning dynamics with learning rate scheduler p(0,t)
0g p(0s,
where Pmow 2 p(0,t) 2 Pmin > Now consider the virtual system
0 pp- ()G(
If the 0y system is contracting in M with rate Pminn, then we have, by the same arguments in Theorem that A(S) is asymptotically (after exponential transients of rate Pmiin) uniformly e-stable with
Pmaz XL
estab
Pmin
Note that the factor Pmax/ Pmmnn Pmin 1 plays similar role to the condition number upper bound X 1. I may be viewed the "cost" of using virtual system, similarly to that of switching to metric. This step is necessary because naive application of contraction analysis rates may be inconclusive. Using a virtual system provides a simple route toward obtaining the desired 1/n generalization bounds.
optimizer with adaptive learning
4.4.2 Sharpness Aware Minimization
Let us apply simple partial contraction analysis to the recently introduced Sharpness Aware Minimization algorithm (SAM) (Foret et al. 2020). In cistinuous-time SAM may be written
VoL
0 = -= |
(30)
where p > 0. Assume first, slightly generalizing [Bartlett et al. 2022 that L is convex quadratic loss of the form
C 1 0--0-P(000
with P(() symmetric uniformly positive definite matrix, i.e., P(() ż p(() 2 Pmin I > where p(() and Pmni are scalars. Substituting in this loss function, the SAM optimizer dynamics may be written
θ ( P(t) (P(() + [PP())] [I(()))
(²) 0 ) 0
where A(0) uniformly positive definite. It is readily shown that this optimizer is partially contracting in the identity metric, by using the virtual system
8, = A
which has 0y= 0 and Og 0 particular solutions. Thus 0 - 0 exponentially with rate of al least X Pmin 0, which implies that SAM achieves generalization rate on the order of 1/2n for this loss function.
Consider now the case an arbitrary (time-invariant) strongly convex loss, and modify the SAM dynamics 30p slightly for improved regularity to
-- 0+
VoL
=
Vo
(31)
17

---

Published in Transactions on Machine Learning Research (04/2023)
with >> small constant. Defining
VoC |
then have
V - vo((0)+ 1 so) Vo[(0) pHe
where H is the average Hessian over the line element, which is positive definite via strong convexity. This implics that -VoL( + pe) is descent direction for the loss,
- Voo = -VL(())
(+ (1+ (1 Vol(O) & -1VVe
This in turn implies that the modified SAM dynamics [3 converges to the unknown global optimizer 0". Similarly to the previous example, consider now the virtual system
HO
Og ((0)VoL((,) with A(O) I+ ( +e
(32)
This virtual system has 0y = 0 and Oy = 0" as particular solutions. Furthermore, considering for this
system the metric M(0) = A (0) (which is purely time-dependent to the virtual system), and denoting
fy = 0g
Of, (0y) 00,
Hly (0,) M(O) M(O) -2V3 A A-
O(
00,
Letting B Amin 2 [( Amin| [ the above implics
M( Of, (0,) 0 00,
Of, (0,)² M(0) M(0) < -23 A A- (() A()) A (0)
As (() approaches the global optimum 0", H(O) reaches some limit and (oC(()) goes to zero, so that À (0) goes to zero. Let hini and Mina be the minimum and maximum eigenvalue of the Hessian 7gg at d". The virtual system becomes contracting with rate hman (1 + p /min//e) so that including the conditioning term X and the disturbance term D s A yields by Theorem (2 the generalization bound
2x(1 +
+ p h Minax
2(1 + L2
hina
3/2
2L2 hmin
A
Aiin
h (1 + P h mann /e)n
h hmin
n2
where we have approximated the expression for small c. Aside from a constant prefactor of (hiax 3/2
this is the same generalization bound and desirable 1/n scaling as standard gradient descent. Note that this result, as far as we awarc, provides the first global convergence analysis and generalization bound for SAM in distribution-free general convex setting. The empirical observation that SAM generalizes better than gradient descent (Foret et al. 2020) suggests that this bound may be further tightened.
5 Concluding Remarks
Is Contraction the Correct Approach to Studying Generalization? In deep learning, models are trained using gradient descent non-convex loss functions. Despite the non-convexity of the loss, these models achieve low lest. error. However, most theoretical analyses of generalization are only applied to convex loss landscapes. This disconnect suggests the need for more general nonlinear analysis tools which can provide tighter gencralization bounds for non-convex landscapes (Foret et al., 2020 Bartlett et al. 2022
We demonstrate that. raction analysis is one such tool, although course it may only provide part the picture. Contraction analysis can be applied either directly to optimizer dynamics (as Theorem 4 or the outputs of a model being trained with gradient flow (as in the Neural Tangent Kernel examples). In both
1 Since hoth PC. and symmetric positive definite, 4 (ZL(0,) 2 Amin (V (((()) = 1/Amin (A(0)) AA BA-1(0)
18

---

Published in Transactions on Machine Learning Research (04/2023)
cases, contraction yields generalization certificates that improve as the number of training samples increases. Although overparameterived optimizers cannot be globally contracting (because overparameterization implies many possible optima), it is expected that the outputs of an overparameterized model will be contracting as the loss converges to zero. Contraction is also consistent with training curves that do not look like pure exponential decay. This is because contraction analysis yields upper bounds on the contract ion rale; training curves are free to be arbitrarily complicated as long as they are upper-bounded by an exponential decay function.
Why Metries are Critical Metrics play a crucial role in our analysis. It is natural to wonder whether changing the metric (or contraction rate) could improve optimization but harm gencralization (Chen et al. 2018). However, since metrics are an analysis tool (i.e., they do not influence the optimization process, only how analyzed), their use in analyzing generalization has no bearing on the performance of the optimizer. That said, as scction shows, "bad" choice of metric can significantly alter the stability and generalization bounds for a given oplimizer. Indeed, the dependence of stability measurement on coordinate systems is precisely why metries are necessary. Contraction analysis considers differential coordinate transforms, which provide a more flexible set of tools than other stability analyses that only consider explicit coordinate transforms [Lohmiller & Slotine 1998).
Comparison to Related Work Our results are similar in spirit to Charles & Papailiopoulos (2018) in the sense that we also use optimizer's intrinsic dynamical stability to provide generalization error bounds. In certain cases-for for example gradient flow on strongly convex losses-our our results allow us to derive tighter bounds, because we do not assume the existence of a global minimizer 0" and go through the triangle inequality to bound the distance between 0g and 0z..
Future Directions Contracting systems are robust to noise (Pham & Slotine 2013 and therefore it seems likely that the results presented here can straightfowardly be extended to stochastic gradient flows- along the lines of Mandt et al. (2015) or Bolli & Slotine (2020). This may be applicable to settings where gradient training may be seen as Wasserstein gradient flow (Bouvric & Slotine, 2019 Mei et al. 2019 Chizat 2022). Our work also suggests a potential connection to the double descent phenomenon (Nakkiran et al. 2021). In particular (14) implies that the generalization error can overshoot by a factor of Lx. which gives room for the generalization to increase transiently from its initial value before it eventually decreases. It has recently been shown that gradient training of deep lincar networks is related to Riemannian gradient flow (Cohen et al. 2022),, another potential application of our results relating contraction to generalization. Similarly, it has been shown in [Bernacchia et al. (2018) that training deep linear networks with natural gradient descont lcads to contraction (in the identity metric) of the network weights towards their optimal value. Theorem is immediately applicable to this setting. Additionally, it has been shown that the self- attention mechanism of Transformers may be interpreted as a primal-dual algorithm (Nguyen et al. 2023). Given the correspondence between primal-dual algorithms and contraction (Nguyen et al. 2018), and in particular between pre-conditioned primal-dual algorithms and Riemannian contraction [Wensing & Slotine 2020 Section 3.2). it could be interesting to also analyze Transformers through contraction lens.
Finally, recent extensions of Riemannian contraction to general Banach spaces (Srinivasan & Slotine 2023 may allow further insights in this broad context.
We conclude with some speculations on the potential connection between our results and biology, specifically neuroscience. The role of non-Euclidean geometry in the objective-based functions of the brain remains an open question (Surace et al. 2020). Many local synaptic rules can be viewed as implementing optimization over loss function, such as Hebbian plasticity minimizing Principal Component Loss in certain settings Oja 1992). It seems plausible that our results can be used to quantify the generalization behavior of such rules. Additionally, we did not explore the combination properties of contracting systems, which can be combined in various hierarchical and feedback forms that automatically preserve contraction [Lohmiller & Slotine 1998 Slotine & Lohmiller 2001] Kozachkov et al.) 2021). Our results suggest that combinations of contracting optimizers automatically generalize well, a property that evolution would likely preserve in a system like the brain.
19

---

Published in Transactions on Machine Learning Research (04/2023)
6 Acknowledgments
This work benefited from stimulating discussions with John Tauber (Neuroscience Statistics Lab at MIT), Akshay Rangaman, Andrzej Banburski-Pahey (Center for Brains, Minds and Machines at MIT), as well as members of the Fiete Lab at MIT. We also thank reviewers for suggestions that strengthened the paper.
References
Shun-Ichi Amari. Natural gradient works efficiently in learning. Newral compulation, 10(2):251-277) 1998.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learnäng, pp. 322-332. PMLR, 2019.
Amit Attia and Tomer Koren. Algorithmic instabilities of accelerated gradient descent. Advances in Neural Information Processing Systems, 34, 2021.
R. H. Bartels and G. W. Stewart. Solution of the matrix equation ax xb c [f4]. Commun. ACM, (9):820 (00,220-26,, sep 1972. ISSN 0001-0782. doi: 10.1145/361578..6111 361188.. URL hnttps://ooi http:////o...r//.....1 1145//
Peter Bartlett, Philip M Long, and Olivier Bousquet. The dynamics of sharpness-awan aware minimization: Bouncing across ravines and drifting towards wide minima. arXiv preprint 2rXiv:2210.01513, 2022.
Alberto Bernacchia, Máté Lengyel, and Guillaume Hennequin. Exact natural gradient in deep linear networks and its application to the nonlinear case. Advances in Newral Information Processing Systems, 31, 2018.
Nicholas M Boffi and Jean-Jacques E Slotine. A continuous-time analysis of distributed stochastic gradient. Newral computation, 32(1):36-96, 2020.
Nicholas M Boffi, Stephen Tu, Nikolai Matni, Jean-Jacques Slotine, and Vikas Sindhwani. Learning stability certificates from data. CoRL, 2020.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pp. 620. PMLR, 2020.
Jake Bouvrie and Jean-Jacques Slotine. Wasserstein contraction of stochastic nonlinear systems. ar preprint XrX:::1902.0883 2019.
Thiago B Burghi, Timothy O'Leary, and Rodolphe Sepulchre. Distributed online estimation of biophysical neural networks. ar preprint arXiv:2204 20X,:22244001772, 2022.
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and Lask-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature communications,, 12(():
1 12, 2021.
Zachary Charles and Dimitris Papailioponlos. Stability and generalization of learning algorithms that con- verge to global optima. International Conference on Machine Learning, pp. 745 754. PMLR, 2018
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence tradc-off of iterative optimization algorithms. arXiv preprinl ar Xix:::180. 10111104.1100 01619, 2018.
Lénaïc Chizat. Mcan-field langevin dynamics: Exponential convergence and anncaling. ar preprint arXiv:2202.0111 01009, 2022.
Soon-Jo Chung and Jean-Jacques E Slotine. Cooperative robot control and concurrent synchronization of lagrangian systems. IEFE transactions on Robotics, 25(3):686-777 -700, 2009.
20

---

Published in Transactions on Machine Learning Research (04/2023)
Nadav Cohen, Govind Menon, and Zsolt Veraszto. Deep linear networks for matrix completion-al infinite depth limit. arXiv preprint or Xri:22200. 12497, 2022.
Domitilla Del Vecchio and Jean-Jacques E Slotine. A contraction theory approach to singularly perturbed systems. TEEE Transactions on Automatic Control, 58(3):752-755) 757, 2012.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht. Essentially no barriers in neural network energy landscape. In International conference on machine learning, pp. 1309-1318. PMLR, 2018.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parametcrized neural networks. arXiv preprint 1Tfi::81000222
2018.
Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing, Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(1), 2005.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference Learning Theory, pp. 1270-1279. PMLR, 2019.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-awarr minimization for efficiently improving generalization. arXiv preprint 010:2200000111,,, 2020.
Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy, and Surya Ganguli. Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel. arXiv preprint xrxiv:2010. 1510000..11111111111 10, 2020.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry Vetrov, and Andrew Gordon Wilson. Loss sur- faces, mode connectivity, and fast ensembling of dnns. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 8803 8812, 2018.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent, 2016.
Nhat Ho, Koulik Khamaru, Raaz Dwivedi, Martin J Wainwright, Michael Jordan, and Bin Yu. Instability, computational efficiency and statistical accuracy. arXiv preprint ar arXiv:2005.14411, 2020.
Jiaoyang Huang and Horng- Tzer Yau. Dynamics of deep neural networks and neural tangent hierarchy. In International conference on machine learning, pp. 4542-4551. PMLR, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv
2018
Saber Jafarpour, Alexander Davydov, Anton Proskurnikov, and Francesco Bullo. Robust. implicit networks via non-euclidean contractions. Advances in Neural Information Processing Systems, 34:9857-968 99668, 2021.
JoufTroy and J-JE Slotine. Methodological remarks on contraction theory. In 2004 43rd IEEE Conference on Decision and Control (IEF) Cat. No. O4CH97601), volume 3, pp. 2537-2543. TEEE, 2004.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv:1412.6960 2014.
arXio preprinl
Leo Kozachkov, Michaela Ennis, and Jean-Jacques Slotine. Recursive construction of stable assemblies of recurrent neural networks. arXiv preprint arXim:2106.0890 2021.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as lincar models under gradient descent. Advances in neural information processing systems, 32:8572 2583, 2019.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in per-parameterizee non- linear systems and neural networks, 2021.
21

---

Published in Transactions on Machine Learning Research (04/2023)
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. arxiv preprint orXie: 03263, 2019.
Winfried Lohmiller and Jean-Jacques E Slotine. On contraction analysis for non-linear systems. Aulomation, 34(6))683 696, 1998.
lan R Manchester and Jean-Jacques E Slotine. Control contraction metrics: Convex and intrinsic criteria for nonlincar foedback design. IEEE Transactions on Automatic Control, (00))3046-3053, 2017.
Stephan Mandt, Matthow D Hoffman, David M Blei, et al. Contimuous-time limit of stochastic gradient descent revisited. In OPT workshop, NIPS, 2015.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mcan-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory, pp. 2388 2464. PMLR, 2019.
Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng, Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints. In Conference on Learning Theory, 605-638. PMLR, 2018.
Sayan Mukherjee, Partha Niyogi, Tomaso Poggio, and Ryan Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Advances in Computational Mathematics, 25(1):161 193, 2006.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Lya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statislical Mechanics: Theory and Erperiment, 2021 2021.
Hung D Nguyen, Thanh Long Vu, Konstantin Turitsyn, and Jean-Jacques Slotine, Contraction and robust- ness of continnous time primal-dual dynamics. IEEE control systems letters, 2(4):755-760, 2018.
Quynh Nguyen, Marco Mondelli, and Guido F Montufar. Tight bounds the smallest eigenvalue of the neural tangent kernel for deep relu networks. In International Conference on Machine Learning, pp. 8119 8129. PMLR, 2021.
Tan M Nguyen, Tam Nguyen, Nhat Ho, Andrea Bertozzi, Richard Baraniuk, and Stanley Osher. Aprimal-dual framework for transformers and neural networks. In International Conference on Learning Representations, 2023.
Erkki Oja. Principal components, minor components, and linear neural networks. Neural networks, 5(6): 927 935, 1992.
Quang-Cuong Pham and Jean-Jacques Slotine. Stable concurrent synchronization in dynamic system net- works. Neural networks, 20(1):62-77, 2007.
Quang- Cuong Pham and Jean-Jacques Slotine. Stochastic contraction in riemannian metries. arXiv preprint arXiv:1304.0344 2013.
Boris Polyak. Gradient methods for the minimisation of functionals. Ussr Computational Mathematics and Mathematical Physics, 3:864-878, 1963.
Max Revay and Tan Manchester. Contracting implicit recurrent neural networks: Stable models with im- proved trainability. In Learning for Dynamics and Control, pp. 393 403. PMLR, 2020.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT, volume 2, pp. 5, 2009.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2618 2010.
John Thylor, Nello Cristianini, al. Kernel methods for pattern analysis. Cambridge university press, 2004.
22

---

and global convergence of Published in Transactions on Machine Learning Research (04/2023)
J-JE Slotine and JA Coetsec. Adaptive sliding controller synthesis for non-linear systems. International Journal of Control, 43(6):16311165)) 1986.
J.J.EE Slotine and W. Lohmiller. Modularity, evolution, and the binding problem: a view from stability the- ory. Neural Networks, 14(2):137-145, 2001. ISSN 0893-6080. doi:
(00000))0))))))
00089-7. URL http:///ww....eoocccc....o..oooa
Jean-Jacques Slotine and Weiping Li. Applied nonlinear control, volume 199. Prentice hall Englewood Cliffs, NJ, 1991.
Anand Srinivasan and Jean-Jacques Slotine. Contracting differential equations in weighted banach spaces. Journal of Differential Equations, 344:203 229, 2023.
Simone Carlo Surace, Jean-Pascal Pfister, Wulfram Gerstner, and Johanni Brea. On the choice of metric in gradient- based theories of brain function. PLoS computational biology, 16(4))e1007640, 2020.
Nicolas Tabareau and Jean-Jacques Slotine. Contraction analysis of nonlinear random dynamical systems. arXiv preprint 1309.5530.33 2013.
Vladimir Vapnik. An overview of statistical learning theory. IEEE transactions on neural networks, (5):988-990) 999, 1999.
Pauli Virtanen, Ralf Gommers, Travis F. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Ev- geni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Tan Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272 2020. doi: 10.1038/s41592- 019-0686-2.
Wei Wang and Jean-Jacques E Slotine. On partial contraction analysis for coupled nonlincar oscillators. Biologicul cybernetics, 92(1):38 53, 2005.
Patrick M Wensing and Jean-Jacques Slotine. Beyond
gradient descent. Plos one, 15()):e0236661, 2020.
Bowen Yi and Ian R Manchester. On the equivalence of contraction and koopman approaches for nonlinear stability and control. In 2021 60th IEEE Conference on Decision and Control (CDC), pp. 4609 4614. IEEE, 2021.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5700 2012.
Guodong Zhang, James Martens, and Roger Grosse. Fast convergence of natural gradient descent. for parameterized neural networks. arXiv preprint arXiv:1905.1000 10961, 2019.
Thomas TCK Zhang, Stephen Tu, Nicholas M Boffi, Jcan-Jacques E Slotine, and Nikolai Matni. Adversarially robust stability certificates can be sample-efficient. arXiv preprint arXiv:2112. 10690, 2021.
A Appendix
A.1 Proof of
Proof. For every time we randomly sample b indices i,, in. Using these indices we select datapoints "..-.. 25 from S and S' to update 0 and 0 respectively. At every time there are two possibilities. Fither do not draw the replaced element. z we do. Denote these events A and B, respectively (Figure
23

---

Published in Transactions on Machine Learning Research (04/2023)
5 We have P(A) = and P(B) If event A occurs, then by assumption expect the geodesic
distance to shrink
M (0 111) - yEAldm. 00 [AA]
(33)
where B|-[A] denotes the conditional expectation given event However, if the replaced element is drawn (i.e., event B occurs) then we have
b Σ
0
g ; G(0,)
b 1=1
0 = G( d
where d(0,5) (g( - )). As in Theorem we have written the update for 0 "perturbed' version of the updale for 0= We will now derive an analogous robustness result, and then use the linearity of expectation to bound the overall geodesic distance. Note that
G(e dM ( (1 0²r1) = d (G(O,) ( + d(o,)))
s d (G())) G()))) + d (G(O)) ((0()) a((,))
s d (G )(0))) + Mmaz 2
where the first incquality comes from the triangle incquality and the second comes from the boundedness of d(())) and the metric distortion bound in Theorem 3 Now applying the assumption of contraction in expectation we get
2
EaldMes (0 of S EAldMini (G(O,), G(0," B)B + V Mmaa
(34)
2
S LRAAldM. ( 0. ) + Maax
We can now use the linearity of the expectation operator to bound the geodesic distance, and then use the metric distortion result to bound the Euclidean distance
EAld (0 0111 EEAld (0 0 [A)P(A) + EAldM,,, (0 (0 (BBP))))(BB)
s WEAldM 0. [[1 b) + (DEAldM, (0, 0]')] / VMaax 25 b
n
25
mEEAdd '0,,00 000)) + V Mmaax
Using the metric distortion bounds and unraveling the recursion yields
2xE
Ex 00 x +
(1 - u)n
Where x V
Moaz has again come from the metric distortion bound. Multiplying through by L, we have Mmsnn
that
2LXE Estab nl1 (4)
which is the same result as the continuous-time case, except that À + (1 n).
24

---

Published in Transactions on Machine Learning Research (04/2023)
Event A
Event B
(Replaced Element Not Drawn)
(Replaced Element Drawn)
O5 t mini-batch
21
zb
Z 1
bb
o mini-batch
Zb
21
Zb
Figure 5: Illustration of the two cases for updating with mini-batches. At each time t, we randomly sample b indices between 1 and n. Then we draw the corresponding datapoints from sets S and S' to form the mini-batches used to update 0 and 05 respectively. In Event A (left column), the index of the replaced element is not selected, and therefore the datapoints used to update o and 0 are the same. In Event B, the index of the replaced element is selected, and so the datapoints used to perform the update are different.
25


Reviews:
[{"review_id": "0o5AB0oD95", "reviewer": "Reviewer_yqhG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Leveraging different metrics for better generalization guarantees is a useful direction in the context of algorithmic stability, and may help design better algorithms. The present work provides a new perspective on this based on Riemannian contractions, and is thus of interest for the community. The paper is also well written, and the presentation is clear.\n\nNevertheless, the current manuscript does not highlight cases where using a non-trivial Riemannian metric is actually helpful for improving generalization bounds, which seems like an important weakness. In particular, the examples in Section 3.1 and 3.2 seem to suggest that the best bounds are achieved when using the trivial metric (M = I) or preconditioner (P = I). It seems important to discuss an example where a non-trivial metric may help with generalization, perhaps with additional assumptions (see, e.g., [this paper](https://arxiv.org/abs/2006.10732) for an example where preconditioning may help, though with different analyses). If this is difficult in the current framework, it would be great to identify why.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies generalization guarantees for optimization algorithms based on algorithmic stability, with a focus on algorithms that contract trajectories in some Riemannian metric. After providing background on Riemannian contractions, the authors present new algorithmic stability bounds for deterministic and stochastic contracting optimizers, which leverage such Riemannian metrics. They then provide several examples to illustrate the theory, as well as extensions to settings where contractions may only hold in a weaker sense.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The main change I'd like to request is described above, i.e. finding examples where the proposed bounds can actually improve over trivial metrics. This seems critical.\n\nAnother important aspect to discuss is regarding the trade-offs between stability and optimization, following related works such as Chen et al, 2018: are there cases where changing the metric or contraction rate may improve optimization but hurt stability, or vice versa, and how may such trade-offs be addressed in this context?\n\nSome additional minor comments/typos:\n- \"Definition 1.1\": the numbering seems different between Definitions and other results (e.g. Theorem 1)\n- Remark 3: dynamics *in* equation..\n- Theorem 4: please add comments: how does this bound compare to the full-batch case? how does the mini-batch size affect the involved quantities, such as $\\mu$?\n- Remark 5: do you have any specific examples where improved stability bounds can be obtained by leveraging the varying metric?\n- section 4.2.1: \"and setting $R(0) = 0$\"\n- section 4.3.1: again the stability bound seems worse when the learning rate is non-contant (due to $\\rho_{max} / \\rho_{\\min} \\geq 1$), which suggests the proposed theory does not explain any benefits of adaptive learning rates, so perhaps this section is not very useful here?", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FByeS5nf5Z", "reviewer": "Reviewer_8Jkf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n-----------\n* The paper analyzes a rather classical question (algorithmic generalization) with a somewhat unique perspective. The insights are reasonably deep and provide a good glimpse into several common optimization problems.\n* The derivations are concise, easy to follow, and are (at least to my current calculation) correct.\n* The results seem reasonably strong. In particular, the remarks on page 5 and 6 help contextualize the work. In particular, the derived bounds provide good insight into general algorithmic stability open problems.\n* The use-cases showcase a broad applicability to several classical problems.\n\nWeaknesses\n--------------\n* I found it rather hard to follow the notation. One notable example is that \"x\" and \"$\\theta$\" are both used to describe points on the underlying space, a pretty hard to follow overloading. I would recommend the authors generally revise to increase clarity.\n* In Theorem 2, the condition on the metrics imply that the metrics do not vanish or explode at infinity. I wonder how realistic this is; does it hold, for example, for the metrics defined in the experiments?\n* A similar question should be asked for Theorem 4. In this case, one should also be careful with how the metrics evolve with time, so a comment about it here would also be nice.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proves the algorithmic stability of certain flow-like optimization algorithms (in particular SGD and Natural Gradient). This is done by rewriting the (Euclidean) problem in the lens of a dynamical system with a new Riemannian metric and showing contraction under this new metric. Results are shown on a variety of learning problems. Furthermore, the paper then expands the notion of \"contractiveness\" to be more inclusive, allowing for some analysis on other optimization problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Mostly, could you address my questions in \"weaknesses\".", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5PhgX3Nf9v", "reviewer": "Reviewer_7zJi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n\nThe results are correct and easily verifiable. The idea of the paper is somewhat obvious in hindsight, but I believe the consequences are significant as it significantly improves the limitations of the Hardt et al. results in the strong convex loss setting. \n\nWeaknesses \n\nIntuitively speaking, the extension to the Riemannian manifold setting is unsurprising - contraction on any metric space will yield uniform stability bounds. Therefore I personally do not believe this is a particularly strong technical contribution. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper extended the framework of Hardt et al. [1] to the Riemannian manifold setting. In the Euclidean setting, this framework provides a generalization bound via uniform stability. In particular, if the loss is strongly convex and has Lipschitz gradients, one can achieve a bound only dependent on the condition number of the loss and number of samples. The analysis of stability is essentially due to contraction - the algorithm cannot change too much to begin with, and therefore it cannot change much more after swapping out a single data point. The authors then proceeds to analyze several examples that fits into this framework but do not fit into the Euclidean setting. \n\nReferences \n1. Hardt, Moritz, Ben Recht, and Yoram Singer. \"Train faster, generalize better: Stability of stochastic gradient descent.\" In International conference on machine learning, pp. 1225-1234. PMLR, 2016.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Aesthetically, there is definitely a question of whether or not this is the \"correct approach\" to studying generalization. While I believe this is of a lesser concern for TMLR, I believe the authors should at least add a discussion towards this direction for readers who are unfamiliar with the meta concerns of this approach. \n\nIs contraction really the reason why gradient descent type algorithms generalize? The main criticism of Hardt et al.'s approach is that in practice we often run gradient based algorithms in nonconvex settings, which do not yield contractions in the first place. This is in sharp contrast with the empirical observations that generalization does still happen without contraction - at least the training curves typically do not look like exponential decay. I hope the authors can provide some discussion, not necessarily a rebuttal, but at least to help put this paper's contribution in appropriate context. \n\nAt the same time, I was hoping the authors consider some other interesting examples of manifolds in their paper, which I believe will significantly strengthen the contributions: \n1. Neural tangent kernel training is contracting on a Hilbert space, a special case of Riemannian manifold, and the contraction rate depends on the minimum eigenvalue of the Gram matrix. \n2. Gradient training of deep linear networks is Riemannian gradient flow, the contraction depends on the strong convexity of the loss function e.g. least squares [2]. \n3. Gradient training of two layer mean field networks is Wasserstein gradient flow [3], although contraction is an open problem, see [4] for some progress towards this direction. \n\nI would strongly recommend adding at least some discussion towards these connections and ideally the first two examples. \n\nReferences \n2. Cohen, Nadav, Govind Menon, and Zsolt Veraszto. \"Deep Linear Networks for Matrix Completion--An Infinite Depth Limit.\" arXiv preprint arXiv:2210.12497 (2022).\n3. Mei, Song, Theodor Misiakiewicz, and Andrea Montanari. \"Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit.\" In Conference on Learning Theory, pp. 2388-2464. PMLR, 2019.\n4. Chizat, Lénaïc. \"Mean-field langevin dynamics: Exponential convergence and annealing.\" arXiv preprint arXiv:2202.01009 (2022).", "broader_impact_concerns": "N/A ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies generalisation bounds for supervised learning based on the algorithmic stability framework of Bousquet & Elisef , using contraction properties of the algorithm (e.g a gradient flow) in appropriate riemanninan metrics. 

Reviewers  agreed that this is submission puts forward an interesting and clear extension of the notion of algorithmic stability. Despite the relative lack of novel technical contributions, overall they found this to be a valuable contribution. 
Decision: Accept (poster)