Jérôme Bolte

Edouard Pauwels

Rodolfo Ríos-Zertuche

Long term dynamics of the subgradient method for Lipschitz path differentiable functions

We consider the long-term dynamics of the vanishing stepsize subgradient method in the case when the objective function is neither smooth nor convex. We assume that this function is locally Lipschitz and path differentiable, i.e., admits a chain rule. Our study departs from other works in the sense that we focus on the behavior of the oscillations, and to do this we use closed measures, a concept that complements the technique of asymptotic pseudotrajectories developed in this setting by Benaïm-Hofbauer-Sorin. We recover known convergence results, establish new ones, and show a local principle of oscillation compensation for the velocities. Roughly speaking, the time average of gradients around one limit point vanishes. Various cases are discussed providing new insight into the oscillation and the stabilization phenomena.

Introduction

The predominance of huge scale complex nonsmooth nonconvex problems in the development of certain artificial intelligence methods, has brought back rudimentary, numerically cheap, robust methods, such as subgradient algorithms, to the forefront of contemporary numerics, see e.g., [START_REF] Barakat | Convergence analysis of a momentum algorithm with adaptive step size for non convex optimization[END_REF][START_REF] Bianchi | Convergence of constant step stochastic gradient descent for non-smooth non-convex functions[END_REF][START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF][START_REF] Higham | Deep learning: An introduction for applied mathematicians[END_REF][START_REF] Diederik | Adam: A method for stochastic optimization[END_REF]. We investigate here some of the properties of the archetypical algorithm within this class, namely, the vanishing stepsize subgradient method of Shor. Given f : R n → R locally Lipschitz, it reads

x i+1 ∈ x i -ε i ∂ c f (x i ), x 0 ∈ R n ,
where ∂ c f is the Clarke subgradient, ε i → 0, and ∞ i=0 ε i = ∞. This dynamics, illustrated in Figure 1, has its roots in Cauchy's gradient method and seems to originate in Shor's thesis [START_REF] Zuselevich | On the structure of algorithms for numerical solution of problems of optimal planning and design[END_REF]. The idea is natural at first sight: one accumulates small subgradient steps to make good progress on average while hoping that oscillations will be tempered by the vanishing steps. For the convex case, the theory was developed by Ermol'ev [START_REF] Yu | Methods for solving nonlinearextremal problems[END_REF], Poljak [START_REF] Poljak | A general method of solving extremum problems[END_REF], Ermol'ev-Shor [START_REF] Yu | On the minimization of nondifferentiable functions[END_REF]. It is a quite mature theory, see e.g. [START_REF] Nemirovskii | Complexity of problems and efficiency of optimization methods[END_REF][START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF], which still has a considerable success through the famous mirror descent of Nemirovskii-Yudin [START_REF] Beck | Mirror descent and nonlinear projected subgradient methods for convex optimization[END_REF][START_REF] Nemirovskii | Complexity of problems and efficiency of optimization methods[END_REF] and its numerous variants. In the nonconvex case, developments of more sophisticated methods were made, see e.g. [START_REF] Hare | A redistributed proximal bundle method for nonconvex optimization[END_REF][START_REF] Krzysztof | Convergence and efficiency of subgradient methods for quasiconvex minimization[END_REF][START_REF] Noll | Bundle method for non-convex minimization with inexact subgradients and function values[END_REF]], yet little was known for the raw method until recently.

The work of Davis et al. [START_REF] Davis | Stochastic Subgradient Method Converges on Tame Functions[END_REF], see also [START_REF] Bianchi | Constant step stochastic approximations involving differential inclusions: Stability, long-run convergence and applications[END_REF], revolving around the fundamental paper of Benaïm-Hofbauer-Sorin [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF], brought the first breakthroughs. It relies on a classical idea of Euler: small-step discrete dynamics resemble their continuous counterparts. As established by Ljung [START_REF] Ljung | Analysis of recursive stochastic algorithms[END_REF], this observation can be made rigorous for large times in the presence of good Lyapunov functions. Benaïm-Hofbauer-Sorin [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF] showed further that the transfer of asymptotic properties from continuous differential inclusions to small-step discrete methods is valid under rather weak compactness and dissipativity assumptions. This general result, combined with features specific to the subgradient case, allowed to establish several optimization results such as the convergence to the set of critical points, the convergence in value, convergence in the long run in the presence of noise [START_REF] Bianchi | Convergence of constant step stochastic gradient descent for non-smooth non-convex functions[END_REF][START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning[END_REF][START_REF] Davis | Stochastic Subgradient Method Converges on Tame Functions[END_REF][START_REF] Salim | Random monotone operators and application to stochastic optimization[END_REF].

Usual properties expected from an algorithm are diverse: convergence of iterates, convergence in values, rates, quality of optimality, complexity, or prevalence of minimizers. Although in our setting some aspects seem hopeless without strong assumptions, most of them remain largely unexplored. Numerical successes suggest however that the apparently erratic process of subgradient dynamics has appealing stability properties beyond the already delicate subsequential convergence to critical points.

In order to address some of these issues, this paper avoids the use of the theory of [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF] and focuses on the delicate question of oscillations, 1 which is illustrated on Figures 1 and2.

In general, as long as the sequence {x i } i remains bounded and satisfies x i+1 -x i = ε i v i for some vectors v i and positive scalars ε i satisfying ∞ i=0 ε i = +∞, we always have

N i=0 ε i v i N i=0 ε i = x N -x 0 N i=0 ε i → 0 as i → +∞. ( 1
)
This fact, that could be called "global oscillation compensation," does not prevent the trajectory to oscillate fast around a limit cycle, as illustrated in [START_REF] Daniilidis | Pathological subgradient dynamics[END_REF], and is therefore unsatisfying from the stabilization perspective of minimization. The phenomenon (1) remains true even when {x i } i is not a gradient sequence, as in the case of discrete game theoretical dynamical systems [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF]. On the left, the contour plot of a convex polyhedral function with three strata, where the gradient is constant. A subgradient sequence starts at (0.3, -0.7) and converges to the origin with an apparent erratic behavior. On the right, we discover that the behavior is not completely erratic. The oscillation compensation phenomenon contributes some structure: the proportions λ i of time spent in each region where the function has constant gradient g i , i = 1, 2, 3, converge so that we have precisely λ 1 g 1 + λ 2 g 2 + λ 3 g 3 = 0.

In this work, we adapt the theory of closed measures, which was originally developed in the calculus of variations (see for example [START_REF] Bangert | Minimal measures and minimizing closed normal one-currents[END_REF][START_REF] Bernard | Young measures, superposition and transport[END_REF]), to the study of discrete dynamics. Using it, we establish several local oscillation compensation results for path differentiable functions. Morally, our results in this direction say that for limit points x we have " lim

δ 0 N →+∞ 0 i N x-x i δ ε i v i 0 i N x-x i δ ε i = 0 " (2)
See Theorems 4 and 5 for precise statements, and a discussion in Section 3.3. While this does not imply the convergence of {x i } i , it does mean that the drift emanating from the average velocity of the sequence vanishes as time elapses. This is made more explicit in the parts of those theorems that show that, given two distinct limit points x and y of the sequence {x i } i , the time it takes for the sequence to flow from a small ball around x to a small ball around y must eventually grow infinitely long, so that the overall average speed of the sequence as it traverses the accumulation set becomes extremely slow.

With these types of results, we evidence new phenomena:

-while the sequence may not converge, it will spend most of the time oscillating near the critical set of the objective function, and it appears that there are persistent accumulation points whose importance is predominant;

-under weak Sard assumptions, we recover the convergence results of [START_REF] Davis | Stochastic Subgradient Method Converges on Tame Functions[END_REF] and improve them by oscillation compensations results, -oscillation structures itself orthogonally to the limit set, so that the incremental drift along this set is negligible with respect to the time increment ε i .

These results are made possible by the use of closed measures. These measures capture the accumulation behavior of the sequence {x i } i along with the "velocities" {v i } i . The simple idea of not throwing away the information of the vectors v i allows one to recover a lot of structure in the limit, that can be interpreted as a portrait of the long-term behavior of the sequence. The theory that we develop in Section 4.1 should apply to the analysis of the more general case of small-step algorithms. Along the way, for example, we are able to establish a new connection between the discrete and continuous gradient flows (Proposition 18) that complements the point of view of [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF].

Notations and organization of the paper. Let n be a positive integer, and R n denote ndimensional Euclidean space. The space R n × R n of couples (x, v) is seen as the phase space consisting of positions x ∈ R n and velocities v ∈ R n . For two vectors u

= (u 1 , . . . , u n ) and v = (v 1 , . . . , v n ), we let u • v = n i=1 u i v i . The norm v = √ v • v induces the distance dist(x, y) = x -y , and similarly on R n × R n .
An open ball of center x and radius r is denoted B(x, r). The Euclidean gradient of f is denoted by ∇f (x). The set N contains all the nonnegative integers.

In Section 2 we give the definitions necessary to state our results, which we do in Section 3. The proofs of our results will be given in Section 5. Before we broach those arguments, we need to develop some preliminaries regarding our main tool, the so-called closed measures; we do this in Section 4.

Algorithm and framework

The vanishing step subgradient method

Consider a locally Lipschitz functions f : R n → R, denote by Reg f the set of its differentiability points which is dense by Rademacher's theorem (see for example [START_REF] Evans | Measure theory and fine properties of functions[END_REF]Theorem 3.2]). The Clarke subdifferential of f is defined by

∂ c f (x) = conv v ∈ R n : there is a sequence {y k } k ⊂ Reg f with y k → x and ∇f (y k ) → v
where conv S denotes the closed convex envelope of a set S ⊂ R n ; see [START_REF] Frank | Optimization and nonsmooth analysis[END_REF]

. A point x such that 0 ∈ ∂ c f (x), is called critical. The critical set is crit f = {x ∈ R n : 0 ∈ ∂ c f (x)}.
It contains local minima and maxima. The algorithm of interest in this work is: Definition 1 (Small step subgradient method). Let f : R n → R be locally Lipschitz and {ε i } i∈N be a sequence of positive step sizes such that

∞ i=0 ε i = +∞ and ε i 0. (3)
Given x 0 ∈ R n , consider the recursion, for i 0,

x i+1 = x i -ε i v i , v i ∈ ∂ c f (x i ).
Here, v i is chosen freely among

∂ c f (x i ). The sequence {x i } i∈N is called a subgradient sequence.
In what follows the sequence ε i is interpreted as a sequence of time increments, and it naturally defines a time counter through the formula:

t i = i j=0 ε j so that t i → ∞ as i → ∞. Given a sequence {x i } i and a subset U ⊆ R n , we set t i (U ) = x j ∈U, j i ε j ,
which corresponds to the time spent by the sequence in U between times 0 and t i .

When f has a locally Lipschitz continuous gradient, bounded sequences are eventually descent sequences, i.e. f (x i ) is nonincreasing and they approach the critical set, see e.g. [START_REF] Absil | Convergence of the iterates of descent methods for analytic cost functions[END_REF] and references therein. When f is nonsmooth, the descent property does not hold anymore and oscillations appear both in values f (x i ) and in space x i . The objective of this article is precisely to study these oscillations.

Recall that the accumulation set acc{x i } i of the sequence {x i } i is the set of points x ∈ R n such that, for every neighborhood U of x, the intersection U ∩ {x i } i is an infinite set. Its elements are known as limit points.

If the sequence {x i } i is bounded and comes from the subgradient method as in Definition 1, then x i -x i+1 → 0 because ε i → 0 and ∂ c f is locally bounded by local Lipschitz continuity of f , so acc{x i } i is compact and connected, see e.g., [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF].

Accumulation points are the manifestation of recurrent behaviors of the sequence but the frequency of the recurrence is ignored. In the presence of a time counter, here {t i } i , this persistence phenomenon may be measured through presence duration in the neighborhood of a recurrent point. This idea is formalized in the following definition: Definition 2 (Essential accumulation set). Given a step size sequence {ε i } i ⊂ R 0 and a subgradient sequence {x i } i ⊂ R n as in Definition 1, the essential accumulation set ess acc{x i } i is the set of points x ∈ R n such that, for every neighborhood U ⊆ R n of x,

lim sup N →+∞ 1 i N x i ∈U ε i 1 i N ε i > 0, that is, lim sup N →+∞ t N (U ) t N > 0.
Analogously, considering the increments {v i } i ⊂ R n , we say that the point (x, w) is in the essential accumulation set ess acc{(x i , v i )} i if for every neighborhood U ⊂ R n × R n of (x, w) satisfies lim sup

N →+∞ 1 i N (x i ,v i )∈U ε i 1 i N ε i > 0.
As explained previously, the set ess acc{x i } i encodes significantly recurrent behavior; it ignores sporadic escapades of the sequence {x i } i . Essential accumulation points are accumulation points but the converse is not true. If the sequence {x i } i is bounded, ess acc{x i } i is nonempty and compact, but not necessarily connected.

Regularity assumptions on the objective function

Lipchitz continuity and pathologies. Recall that, given a locally Lipschitz function f : R n → R, a subgradient curve is an absolutely continuous curve satisfying, γ (t) ∈ -∂ c f (γ(t)), a.e. on (0, +∞) and γ(0) = x 0 . By general results these curves exist, see e.g., [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF] and references therein. In our context they embody the ideal behavior we could hope from subgradient sequences.

First let us recall that pathological Lipschitz functions are generic in the Baire sense, as established in [START_REF] Borwein | Generalized subdifferentials: a Baire categorical approach[END_REF][START_REF] Xianfu | Fine and Pathological Properties of Subdifferentials[END_REF]. In particular, generic 1-Lipschitz functions f : R → R satisfy ∂ c f ≡ [-1, 1] everywhere on R. This means that any absolutely continuous curve γ : R → R with γ 1 is a subgradient curve of these functions, regardless of their specifics. Note that this implies that a curve may constantly remain away from the critical set.

The examples by Danillidis-Drusvyatskiy [START_REF] Daniilidis | Pathological subgradient dynamics[END_REF] make this erratic behaviour even more concrete. For instance, they provide a Lipschitz function f : R2 → R and a bounded subgradient curve γ having the "absurd" roller coaster property

(f • γ)(t) = sin t, t ∈ R.
Although not directly matching our framework, these examples show that we cannot hope for satisfying convergence results under the spineless general assumption of Lipschitz continuity.

Path differentiability. We are thus led to consider functions avoiding pathologies. We choose to pertain to the fonctions saines 2 of Valadier [START_REF] Valadier | Entrainement unilateral, lignes de descente, fonctions lipschitziennes non pathologiques[END_REF] (1989), rediscovered in several works, see e.g. [START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning[END_REF][START_REF] Borwein | A chain rule for essentially smooth Lipschitz functions[END_REF][START_REF] Davis | Stochastic Subgradient Method Converges on Tame Functions[END_REF]. We use the terminology of [START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning[END_REF]; note however that the equivalent definition proposed in [START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning[END_REF] (see [START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning[END_REF]Corollary 2]) is not limited to chain rules involving the Clarke subgradient.

Definition 3 (Path differentiable functions). A locally Lipschitz function f : R n → R is path differentiable if, for each Lipschitz curve γ : R → R n , for almost every t ∈ R, the composition f • γ is differentiable at t and the derivative is given by

(f • γ) (t) = v • γ (t) for all v ∈ ∂ c f (γ(t)).
In other words, all vectors in ∂ c f (γ(t)) share the same projection onto the subspace generated by γ (t).

Note that the definition of path differentiable functions proposed in [START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning[END_REF] is slightly different but turns out to be equivalent. There, the condition in the definition is required to be satisfied by all absolutely continuous curves γ; here, instead, we restrict to Lipschitz curves γ. The equivalence follows from the fact that absolutely continuous curves can be parameterized by arc-length -hence becoming Lipschitz curves-without affecting their role in the definition.

The class of path differentiable functions is very large and includes many cases of interest functions that are semi-algebraic, tame (definable in an o-minimal structure, see [START_REF] Davis | Stochastic Subgradient Method Converges on Tame Functions[END_REF] and references therein. Tame functions encompass most models and loss functions used in machine learning, such as, for example, those occurring in neural network training with all the activation functions that have been considered in the literature, see e.g., [START_REF] Castera | An inertial newton algorithm for deep learning[END_REF][START_REF] Davis | Stochastic Subgradient Method Converges on Tame Functions[END_REF]. Note that convex, concave, or semi-convex functions (such as lower or upper C k functions) are path differentiable; adapt the proof of [START_REF] Brézis | Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert[END_REF]Lemme 3.3] or see [START_REF] Davis | Stochastic Subgradient Method Converges on Tame Functions[END_REF].

3 Main results: accumulation, convergence, oscillation compensation

We present our main results: first we only assume path differentiability (Section 3.1)), in a second time this assumption is reinforced by a Sard's like property (Section 3.2). Our results complement those of [START_REF] Davis | Stochastic Subgradient Method Converges on Tame Functions[END_REF] and [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF]. The significance of the results is discussed in Section 3.3. The proofs are presented in Section 5.

The vanishing subgradient method for path differentiable functions

Theorem 4 (Large-time regime for path differentiable functions). Assume that f : R n → R is locally Lipschitz path differentiable, and that {x i } i is a bounded subgradient sequence. Then we have:

i. (Slow evolution regime) Let x and y be two distinct points in

acc{x i } i such that f (x) f (y). Let {x i k } k be a subsequence such that x i k → x as k → +∞, and for each k choose i k > i k such that x i k → y. Then Tk = i k p=i k ε p → +∞.
ii. (Oscillation compensation) Let ψ : R n → [0, 1] be a continuous function. Then, for every integer sequence

N j → +∞, lim inf j→+∞ N j i=0 ε i ψ(x i ) N j i=0 ε i > 0 =⇒ lim j→+∞ N j i=0 ε i v i ψ(x i ) N j i=0 ε i ψ(x i ) = 0.
iii. (Criticality). Each essential accumulation point is critical, ess acc{x i } i∈N ⊆ crit f .

The vanishing subgradient method for path differentiable functions with a weak Sard property

We now assume in addition that f is constant on the connected components of its critical set. A Sardtype property which is automatically valid for some important cases, as for instance, semialgebraic or tame functions [START_REF] Bolte | Clarke Subgradients of Stratifiable Functions[END_REF] or lower or upper-C k functions [START_REF] Barbet | Sard theorems for Lipschitz functions and applications in optimization[END_REF] (for k sufficiently large).

Theorem 5 (Large-time regime for path differentiable functions: weak Sard case). In the setting of Theorem 4, and if additionally f is constant on the connected components of its critical set, then:

i. (Slow evolution regime 2) Let x and y be two distinct points in acc{x i } i , x = y, and take δ > 0 small enough that the balls B δ (x) and B δ (y) are at a positive distance from each other, that is,

x -y > 2δ. Consider the successive time duration the sequence needs to go from the ball B δ (x) to the ball B δ (y), namely,

T j = inf{ p=i ε p : j i < , x i ∈ B δ (x), x ∈ B δ (y)}.
Then T j → +∞ as j → +∞.

ii. (Long intervals) Let U, V be open neighborhoods of some accumulation point of {x i } i , such that U ⊂ V . Consider the sequences of indices {i k } k ⊂ N and {j k } k ⊂ N ∪ {+∞} such that (refer to Figure 3):

• i k < j k < i k+1 , • x i ∈ V for i ∈ I k := [i k , j k ] ∩ N, • x i k -1 and x j k +1 are not in V , and
• there is some j ∈ I k such that x j ∈ U .

Then either there is some k for which j k = +∞, i.e., I k is unbounded, or

lim k→+∞ |I k | = lim k→+∞ i∈I k ε i = +∞.
Figure 3: The intervals I k in the statement of item (ii) correspond to fragments of the sequence contained in V and meeting U displayed here in blue.

iii. (Oscillation compensation version 2) Let U ⊂ V be two open sets as in item (ii), and A = i I i be the corresponding union of maximal intervals. Then

lim N →+∞ 0 i N i∈A ε i v i 0 i N i∈A ε i = 0. iv. (Criticality) Each accumulation point is critical, acc{x i } i ⊆ crit f .

v. (Convergence of the values)

The values sequence f (x i ) converge to a Clarke critical value as i → +∞.

Remark 6. Items (iv) and (v) of Theorem 5 can also be deduced from [9, Proposition 3.27] using a different approach. The Sard-like assumption on f in [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF] is that f (crit f ) has empty interior, which is equivalent, once f is locally Lipschitz, to f being constant on the connected components of crit f ; see the proof of Lemma 23. Up to our knowledge, items (i)-(iii) of Theorem 5 as well as Theorem 4 do not have counterparts in the optimization literature.

Remark 7 (Oscillations and V -shaped valleys). Consider a path differentiable function f : R n → R that is C ∞ both when restricted to a smooth submanifold S ⊂ R n with dim S < n and when restricted to its complement R n \ S, and assume the gradient of f is bounded away from zero on R n \ S.

Thus, near S, f forms a V-shaped valley. In this case, we can provide more insight into the oscillation compensation phenomenon: roughly speaking, the "bouncing" (jumps between to strata adjacent to S) of {x i } i gets more and more orthogonal to S around x, suggesting that the drift of the whole sequence should be parallel to S.

Lemma 8 (Normal bouncing in a V -shaped valley). Consider a function f : R n → R as in the previous paragraph, and a bounded subgradient sequence {x i } i . Assume that there is a subsequence

x i j → x with lim sup j→+∞ v i j > 0 (actual bouncing).
Then x is a critical point contained in the submanifold S with

acc{v i j } j ⊂ N S (x) (normal bouncing)
where N S (x) = T ⊥ S (x) is the normal set to S. Proof. Let K be a compact set that contains {x i } i in its interior. By the Morse-Sard theorem applied independently on the submanifold S, f (crit f ) is a compact set of measure zero. Thus, it must be a totally-separated subset of R. It follows that f is constant on each connected component of crit f . In other words, we are in the setting of Theorem 5. From item (iv) of Theorem 5 we know that x ∈ acc{x i } i ⊂ crit f , and the additional condition we have on x tells us that ∂ c f (x) = {0}, so x cannot be a smooth point of f , whence x ∈ S. Let (x, v) = lim j→+∞ (x i j , v i j ) be an accumulation point of the sequence (x i , v i ), and let α : R → R n be a smooth curve with α(0) = x, α(t) ∈ S for all t, and α (0) = w. The path differentiability of f means that the choice of element of

∂ c f (α(0)) is immaterial when we compute (f • α) (0). So we have lim j→+∞ w • v i j = v • w = v • α (0) = (f • α) (0) = 0.
This geometrical setting is reminiscent of the partial smoothness assumptions of Lewis [START_REF] Lewis | Active sets, nonsmoothness, and sensitivity[END_REF] (a smooth manifold lies in between the slopes of a sharp valley). While proximal-like methods end up in a finite time on the smooth locus [34, Theorem 4.1], our result suggests that the explicit subgradient method keeps on bouncing, approaching the smooth part without actually attaining it. This confirms the intuition that finite identification does not occur, although oscillations eventually provide some information on active sets by delineating progressively their normal sets. The observation above can be extended to the semialgebraic or definable setting using Whitney stratifications.

Further discussion

Theorems 4 and 5 describe the long-term dynamics of the algorithm. While Theorem 4 only describes what happens close to ess acc{x i } i focusing on persistent behavior, Theorem 5 covers all of acc{x i } i that is all recurrent behaviors.

The paper [START_REF] Rios-Zertuche | Examples of pathological dynamics of the subgradient method for Lipschitz path-differentiable functions[END_REF] explores the ways in which the results presented above are sharp in the context of the class of locally-Lipschitz, path-differentiable objective functions f . The paper gives examples of functions f with corresponding non-converging subgradient sequences {x i } i , also with non-convergent {f (x i )} i , lack of oscillation compensation outside of ess acc{x i } i , and other interesting properties.

Oscillation compensation. While the high-frequency oscillations will, in many cases, be considerable, they almost cancel out. This is what we refer to as oscillation compensation. The intuitive picture the reader should have in mind is a statement that the oscillations cancel out locally, as in [START_REF] William | On the first variation of a varifold[END_REF]. Yet, because of small technical minutia, we do not have exactly (2) and obtain instead very good approximations. Let us provide some explanations.

Letting, in item (ii) of Theorem 4, ψ = ψ δ,η : R n → [0, 1] be a continuous cutoff function equal to 1 on a ball B η (x) of radius η > 0 around a point x ∈ ess acc{x i } i and vanishing outside the ball B δ (x) for δ > η, then we get, for appropriate subsequences {N j } j ⊂ N,

lim δ 0 lim η δ lim j→+∞ N j i=0 ε i v i ψ δ,η (x i ) N j i=0 ε i ψ δ,η (x i ) = 0,
which is indeed a very good approximation of (2).

Similarly, setting, in item (iii) of Theorem 5, U = B η (x) and V = B δ (x) the balls centered at x with radius 0 < η < δ, we obtain this local version of the oscillation cancellation phenomenon: in the setting of Theorem 5 if

x ∈ acc{x i } i and if A η,δ ⊂ N is the union of maximal intervals I ⊂ N such that {x i } i∈I ∈ B δ (x) and {x i } i∈I ∩ B η (x) = ∅, then lim δ 0 lim η δ lim N →+∞ 0 i N i∈A η,δ ε i v i 0 i N i∈A η,δ ε i = 0.
Note that as we take the limit η δ, we cover almost all x i in the ball B δ (x), so we again get a statement very close to (2).

Convergence. While Theorem 5 tells us that f (x i ) converges, we conjecture that this is no longer true in the context of Theorem 4, which is a matter for future research. Similarly, in the setting of path differentiable functions, the question of determining whether all limit points of bounded sequences are critical remains open.

In all cases, including the smooth case, the sequence {x i } i may not converge. A well-known example of such a situation was provided for the case of smooth f by Palis-de Melo [START_REF] Palis | Geometric theory of dynamical systems[END_REF]. However, our results show that the drift that causes the divergence of {x i } i is very slow in comparison with the local oscillations. This slowness can be immediately appreciated in the statement of item (i) of Theorem 4 and items (i) and (ii) of Theorem 5. In substance, these results express that even if the sequence diverges, it takes longer and longer to connect disjoint neighborhoods of different limit points.

A closed measure theoretical approach

Given a nonempty open subset of U of R n , denote by C 0 (U ) the set of continuous real-valued functions on U while C p (U ) is the set of p ∈ [1, ∞] continuously differentiable real-valued functions on U . The set LipCurv(U ) denotes the space of Lipschitz curves γ : R → U . When U is bounded, LipCurv(U ) is endowed with the supremum norm γ ∞ = sup t∈R γ(t) .

A compendium on closed measures

Elementary facts and density. Given a measure ξ on some set X = ∅ and a measurable map g : X → Y , where Y = ∅ is another set, the pushfoward g * ξ is defined to be the measure on Y such that, for

A ⊂ Y measurable, g * ξ(A) = ξ(g -1 (A)).
Recall that the support supp µ of a positive Radon measure µ on R m , m 0, is the set of points x ∈ R m such that µ(U ) > 0 for every neighborhood U of x. It is a closed set.

The origin of the concept of closed measures, sometimes also called holonomic measures or Young measures, can be traced back to the work of L.C. Young [START_REF] Chisholm | Generalized curves and the existence of an attained absolute minimum in the calculus of variations[END_REF][START_REF] Chisholm | Lectures on the calculus of variations and optimal control theory[END_REF] in the context of the calculus of variations. It has developed in parallel to the closely related normal currents [START_REF] Federer | Geometric measure theory. Die Grundlehren der mathematischen Wissenschaften[END_REF][START_REF] Federer | Real flat chains, cochains and variational problems[END_REF] and varifolds [START_REF] William | On the first variation of a varifold[END_REF][START_REF] Almgren | Plateau's problem: An invitation to varifold geometry[END_REF], and has found applications in several areas of mathematics, especially Lagrangian and Hamiltonian dynamics [START_REF] Contreras | Global minimizers of autonomous Lagrangians. 22 o Colóquio Brasileiro de Matemática[END_REF][START_REF] Mañé | Ergebnisse der Mathematik und ihrer Grenzgebiete[END_REF][START_REF] Mather | Action minimizing invariant measures for positive definite Lagrangian systems[END_REF][START_REF] Sorrentino | Action-minimizing Methods in Hamiltonian Dynamics (MN-50): An Introduction to Aubry-Mather Theory[END_REF], the calculus of variations [4, Section 4.3] and also optimal transport [START_REF] Bernard | Young measures, superposition and transport[END_REF][START_REF] Bernard | Optimal mass transportation and Mather theory[END_REF].

The definition of closed measures is inspired from the following observations. Given a Lipschitz curve γ : [a, b] → R n , its position-velocity information can be encoded by a measure µ γ on R n ×R n that is the pushforward of the Lebesgue measure on the interval [a, b] into R n × R n through the mapping t → (γ(t), γ (t)), that is,

µ γ = 1 b -a (γ, γ ) * Leb [a,b] .
This notation extends readily to the case of curves defined on an arbitrary measurable set J in the domain of γ:

µ γ| J = 1 |J| (γ, γ ) * Leb J .
If φ : R n × R n → R is a measurable function, then the integral with respect to µ γ is given by

R n ×R n φ(x, v) dµ γ (x, v) = 1 b -a b a φ(γ(t), γ (t)) dt.
With this definition of µ γ , it follows that γ is a closed loop, that is, γ(a) = γ(b) if, and only if, for all smooth g : R n → R, we have

R n ×R n ∇g(x) • v dµ γ (x, v) = 1 b -a b a ∇g(γ(t)) • γ (t) dt = 1 b -a b a (g • γ) (t)dt = g • γ(b) -g • γ(a) b -a = 0.
In other words, the integral of ∇g(x) • v with respect to µ γ is the circulation of the gradient vector field ∇f along the curve γ, and so it vanishes when γ is a closed loop. This generalizes into:

Definition 9 (Closed measure). A compactly-supported, positive, Radon measure µ on R n × R n is closed if, for all functions g ∈ C ∞ (R n ), R n ×R n ∇g(x) • v dµ(x, v) = 0.
Let π : R n × R n → R n be the projection π(x, v) = x. To a measure µ on R n × R n we can associate its projected measure π * µ. As an immediate consequence we have that supp π * µ = π(supp µ) ⊆ R n .

The disintegration theorem [START_REF] Dellacherie | Probabilities and potential[END_REF] implies that there are probability measures µ

x , x ∈ R n , on R n such that, if φ : R n × R n → R is measurable, we have R n ×R n φ dµ = R n R n φ(x, v) dµ x (v) d(π * µ)(x). (4)
We shall refer to the couple (π * µ, π x ) as to the desintegration of µ. Thus

µ = R n µ x d(π * µ)(x).
Definition 10 (Centroid field). Let µ be a positive, compactly-supported, Radon measure on R n ×R n desintegrated according to (4). The centroid field vx of µ is

vx = R n v dµ x (v), x ∈ R n .
The centroid field gives an average velocity at each point; it plays a significant role in our work. As a consequence of the disintegration theorem [START_REF] Dellacherie | Probabilities and potential[END_REF], x → vx is measurable, and for every measurable φ : R n × R n → R linear in the second variable, we have

R n ×R n φ(x, v) dµ(x, v) = R n φ(x, vx ) d(π * µ)(x). (5)
Given the measure µ with centroid field vx , we may define its centroidal measure μ on R × R given by

R×R φ dμ = R φ(x, vx ) dπ * µ(x),
for measurable functions φ : R n × R n → R. With this definition, µ is closed if, and only if μ is closed. Thus the closedness property only depends on the centroid field rather than on the whole constellation of velocities in the support of µ. Observe that, if a positive Radon measure µ has a centroid field vx that vanishes π * µ-almost everywhere, then µ is closed because μ is obviously closed.

Young superposition principle. The following result, known as the Young superposition principle [START_REF] Bernard | Young measures, superposition and transport[END_REF][START_REF] Chisholm | Lectures on the calculus of variations and optimal control theory[END_REF] or as the Smirnov solenoidal representation [START_REF] Bangert | Minimal measures and minimizing closed normal one-currents[END_REF][START_REF] Konstantinovich | Decomposition of solenoidal vector charges into elementary solenoids, and the structure of normal one-dimensional flows[END_REF], see also [START_REF] Ríos-Zertuche | Characterization of minimizable Lagrangian action functionals and a dual Mather theorem[END_REF]Example 6]. What this result tells us is basically that, not only can closed measures be approximated by measures induced by curves, but actually the centroidal measure μ can be decomposed into a combination of measures induced by Lipschitz curves. This decomposition is very useful theoretically, as there are no limits involved.

Let U be a nonempty bounded open subset of R n and set LipCurv(U ) = LipCurv. For t ∈ R, let τ t : LipCurv → LipCurv be the time-translation τ t (γ)(s) = γ(s + t).

Theorem 11 (Young superposition principle or Smirnov solenoidal representation). For every closed probability measure µ supported in U × R n with centroid field vx , there is a Borel probability measure ν on the space LipCurv that is invariant under τ t for all t ∈ R and such that

R n φ(x, vx ) d(π * µ)(x) = LipCurv φ(γ(0), γ (0)) dν(γ) (6)
for any measurable φ : R n × R n → R.

For details on how to obtain Theorem 11 from [START_REF] Bernard | Young measures, superposition and transport[END_REF], please see [START_REF] Bianchi | A closed-measure approach to stochastic approximation[END_REF]. Curves lying in supp ν have an appealing property:

Corollary 12 (Centroidal representation of supp ν). With the notation of the previous theorem, we have for ν almost all γ in LipCurv:

γ (t) = vγ(t)
for almost all t ∈ R.

Proof. Take indeed φ 0 vanishing only on the measurable set consisting of points of the form (x, vx ),

x ∈ R n . Then both sides of (6) must vanish, which means that for ν-almost all γ, the point (γ(0), γ (0)) must be of the form (x, vx ). The conclusion follows from the τ t -invariance of the measure ν.

As an example, take the case in which µ is the closed measure

µ = 1 2π (β, β ) * Leb [0,2π) on R 2 × R 2 for β(t) = (cos t, sin t).
In this simple example, the centroid coincides with the derivative, vβ(t) = β (t). Each time-translate τ t (β) is still a parameterization of the circle, and the probability measure ν we obtain in Theorem 11 is

ν = 1 2π 2π 0 δ τt(β) dt,
where δ γ is the Dirac delta function whose mass is concentrated at the curve γ in the space LipCurv.

As a general fact, the measure ν in Theorem 11 can be understood as a decomposition of the closed measure µ into a convex superposition of measures induced by Lipschitz curves. Although at first sight each γ on the right-hand side of ( 6) only participates at t = 0, the τ t -invariance of ν means that in fact the entire curve γ is involved in the integral through its time translates τ t γ. Observe that another consequence of the τ t -invariance is that the integral in the right-hand side of (6) actually writes, for all t ∈ R,

LipCurv φ(γ(0), γ (0)) dν(γ) = LipCurv φ(γ(t), γ (t)) dν(γ) = 1 |I| I LipCurv φ(γ(t), γ (t)) dν(γ) dt (7) = 1 |I| LipCurv I φ(γ(t), γ (t)) dt dν(γ).
where I is any nontrivial, bounded interval . Thus (6) has the more explicit lamination or superposition form :

R n φ(x, vx ) d(π * µ)(x) = 1 |I| LipCurv I φ(γ(t), γ (t)) dt dν(γ) (8) = LipCurv R n ×R n φ(x, v) dµ γ| I (x, v) dν(γ) (9)
for any bounded interval I with nonempty interior.

Although the left-hand side of (6) does not involve the full measure µ, it will turn out to be similar enough: if the integrand φ : R n × R n → R is linear in the second variable v, we still have ( 5) and this will be enough for the applications we have in mind.

We remark that the measure ν in Theorem 11 is not unique in general. For example, if γ is a closed curve intersecting itself once so as to form the figure 8, then, just as the figure 8 can be drawn in several ways -on a single stroke without lifting the pencil from the paper, or by drawing two circles separately-, so also the possibilities of different measures ν decomposing µ = µ γ reflect this diversity; ν can be taken to be supported on all the τ t -translates of γ itself, or it could be taken to be supported on the curves traversing each of the loops of the 8.

Preliminaries on set-valued vector fields and circulation for a subdifferential field

In the following, we consider set-valued maps Z : R n ⇒ R n with the following standing assumption:

Assumption 13. For every x ∈ R n , the set Z(x) ⊆ R n is nonempty, convex and locally bounded (meaning that for every compact subset K ⊆ R n there is a constant N > 0 such that y N for all y ∈ Z(x) and all x ∈ K), and such that the graph of Z, defined by

graph Z = {(x, p) ∈ R n × R n : p ∈ Z(x)}, is a closed subset of R n × R n .
Note that if µ is a closed measure with desintegration (π * µ, µ x ) and centroid field vx , we obviously have

a ∈ R, x ∈ R n and a supp µ x ⊂ Z(x) ⇒ av x ∈ Z(x). (10)
A major example of a set-valued mapping satisfying the above assumption is given by the Clarke subgradient ∂ c f of a locally Lipschitz continuous mapping as defined in Section 2.1. Path-differentiability of a function ensures that the circulation of its subdifferential along any loop vanishes. This generalizes into: Proposition 14 (Circulation of subdifferential for path differentiable functions). If g : R n → R is a path differentiable function and µ is a closed probability measure, then for each open set U ⊂ R n and each measurable function σ : U → R n with σ(x) ∈ ∂ c g(x) for x ∈ U , the integral

U ×R n σ(x) • v dµ(x, v)
is well defined, and its value is independent of the choice of σ. We define the symbol

U ×R n ∂ c g(x) • v dµ(x, v) to be equal to this value. If π(supp µ) ⊂ U , U ×R n ∂ c g(x) • v dµ(x, v) = 0.
Proof. Denote by χ U : R n → {0, 1} the indicator function for the open set U ⊂ R n that is equal to χ U (x) = 1 for x ∈ U and vanishes elsewhere. Let σ 1 , σ 2 : R n → R n be two measurable functions such that σ i (x) ∈ ∂ c g(x) for each x ∈ U , i = 1, 2. From Theorem 11 we get a τ t -invariant, Borel probability measure ν on the space LipCurv of Lipschitz curves. Then, using (8) for any interval I ⊂ R,

U ×R n σ 1 (x) • v dµ(x, v) - U ×R n σ 2 (x) • v dµ(x, v) = R n ×R n χ U (x)(σ 1 (x) -σ 2 (x)) • v dµ(x, v) = LipCurv 1 |I| I χ U (γ(t))(σ 1 (γ(t)) -σ 2 (γ(t))) • γ (t) dt dν(γ).
Since g is path differentiable, for each γ ∈ LipCurv and for almost every t ∈ R with γ(t) ∈ U ,

σ 1 (γ(t)) • γ (t) = σ 2 (γ(t)) • γ (t).
From the τ t -invariance of ν it follows then that the integrand above vanishes ν-almost everywhere.

Let us now analyze the case when π(supp µ) ⊂ U . Let ψ : R n → R be a mollifier, that is, a compactly-supported, nonnegative, rotationally-invariant, C ∞ function such that R n ψ = 1, and let ψ r (x) = r -n ψ(x/r) for r > 0, so that ψ r tends to the Dirac delta at 0 as r → 0. Denote by ψ r * g the convolution of ψ r and g. Observe that if β ∈ LipCurv and a < b, then b a

(g • β) (t) dt = g • β(b) -g • β(a) = lim r 0 [(ψ r * g) • β(b) -(ψ r * g) • β(a)] = lim r 0 b a ((ψ r * g) • β) (t) dt.
This observation, together with (8), justifies the following calculation: for any bounded interval

I ⊂ R, R n ×R n ∂ c g(x).v dµ(x, v) = LipCurv 1 |I| I (g • β) (t) dt dν(β) = = lim r 0 LipCurv 1 |I| I ((ψ r * g) • β) (t) dt dν(β) = lim r 0 LipCurv 1 |I| I ∇(ψ r * g)(β(t)) • β (t) dt dν(β) = lim r 0 R n ×R n ∇(ψ r * g)(x) • v dµ(x, v),
which vanishes because µ is closed and ψ r * g is C ∞ .

Interpolant curves and their limit measures

Given a set-valued map Z satisfying Assumption 13, we shall consider sequences {x i } i satisfying

x i+1 -x i ∈ ε i Z(x i ). ( 11
)
Thus, for example, if Z = ∂ c f , the sequence {x i } i is a subgradient sequence (Definition 1).

In order to analyze the asymptotics of sequences generated by dynamical systems of the form (11), we shall use the following definition. Definition 15 (Interpolant curves). Given a sequence {x i } i∈N ⊆ R n satisfying x i+1 = x i -ε i v i for some uniformly bounded vectors v i ∈ R n and some scalars ε i > 0 that satisfy i ε i = +∞, its interpolating curve is the continuous piecewise affine curve γ : R 0 → R n with γ(t i ) = x i for t i = i j=0 ε i and γ (t) = v i for t i < t < t i+1 .

Interpolant curves correspond to continuous-time piecewise-affine interpolation of sequences {x i } i , as the ones produced by the dynamical system [START_REF] Bernard | Optimal mass transportation and Mather theory[END_REF]. They are extremely useful to study the asymptotic behavior of these sequences.

For a bounded measurable set B ⊂ R 0 , we define a measure on R n × R n by

µ γ| B = 1 |B| (γ, γ ) * Leb B ,
where |B| = B 1 dt is the length of B, and Leb B is the Lebesgue measure on B.

If φ : R n × R n → R is measurable, then R n ×R n φ dµ γ| B = 1 |B| B φ(γ(t), γ (t)) dt.
Lemma 16 (Limiting closed measures associated to bounded sequences). Let γ be the interpolating curve of a bounded sequence {x i } i as in Definition 15. Let A = {I i } i∈N be a collection of intervals

I i ⊂ R, with disjoint interior, such that |I i | → +∞ as i → +∞. Set B N = ∪ N i=0 I i .
Then the set of weak* limit points of the sequence {µ γ| B N } N is nonempty, and its elements are closed probability measures.

Proof. Let φ ∈ C 0 (R n × R n ). For i ∈ N, write I i = [t i 1 , t i 2 ] and d i = γ(t i 1 ) -γ(t i 2 )
, and let

α i : [0, d i ] → R n be the segment joining γ(t i
2 ) to γ(t i 1 ) with unit speed. Also, let

ν i = (α i , α i ) * Leb [0,d i ]
be the measure on R n × R n encoding α i . Let K ⊂ R n × R n be a convex, compact set that contains the image of (γ, γ ) and (α i , α i ) for all i, so that

d i diam K. Estimate N i=0 R n ×R n φ dν i |B N | = N i=0 d i 0 φ(α i (t), α i (t)) dt N i=0 |I i | N (diam K) sup (x,v)∈K |φ(x, v)| N i=0 |I i | → 0 since |I i | → +∞.
Thus the measures in the accumulation sets of the sequences {µ γ| B N } N and

µ γ| B N + N i=0 ν i |B N | N ( 12
)
coincide. The measures in the latter sequence are all closed since, for all ϕ ∈ C ∞ (R n ), we have, by the fundamental theorem of calculus,

t i 2 t i 1 ∇ϕ(γ(t))•γ (t) dt + d i 0 ∇ϕ(α(t)) • α (t) dt = t i 2 t i 1 (ϕ • γ) (t) dt + d i 0 (ϕ • α) (t) dt = [ϕ(γ(t i 2 )) -ϕ(γ(t i 1 ))] + [ϕ(α(d i )) -ϕ(α i (0))] = [ϕ(γ(t i 2 )) -ϕ(γ(t i 1 ))] + [ϕ(γ(t i 1 )) -ϕ(γ(t i 2
))] = 0, and the measures in the sequence [START_REF] Bianchi | Constant step stochastic approximations involving differential inclusions: Stability, long-run convergence and applications[END_REF] are sums of multiples of these. By Prokhorov's theorem [START_REF] Vasilyevich | Convergence of random processes and limit theorems in probability theory[END_REF], the set of probability measures on K is compact, so the set of limit points is nonempty. The set of closed measures is itself closed, as it is defined by a weak* closed condition.

Thus the limit points must also be closed measures.

Note that two bounded sequences {x i } i and {y i } i having similar asymptotic behavior may give rise to the same set of limiting closed measures through their interpolanting curves; this is the case for example when we start the subgradient method (Definition 1) for the function f (x) = |x|, x ∈ R, at two different initial positions x 0 = y 0 , as in this case the only possible limiting measures are δ (0,0) and 1 2 δ (0,-1) + 1 2 δ (0,1) . The coincidence of limiting measures is a manifestation of the concentration phenomenon discussed in [START_REF] Attouch | Variational analysis in Sobolev and BV spaces: applications to PDEs and optimization[END_REF]Section 4.3].

Lemma 17 (Limit points and limiting measure supports). Let γ be the interpolating curve as in Definition 15. Consider the set acc{µ γ| [0,N ] } N of limit points of the sequence {µ γ| [0,N ] } N in the weak* topology. We have

π(supp µ) : µ ∈ acc{µ γ| [0,N ] }} N = ess acc{x i } i .
Proof. Assume x ∈ ess acc{x i } i and let B ⊂ R n be a closed ball whose interior contains x. Let C > 0 be a uniform bound of v i = x i+1 -x i /ε i C, i ∈ N, which exists by Definition 15. Let ψ : R n → R 0 be a continuous function with supp ψ ⊆ B. Since ψ is uniformly continuous on B, given ε > 0, there is n 0 > 0 such that i > n 0 , x, y ∈ B, and x -y ε i C imply |ψ(x) -ψ(y)| ε. We hence have |ψ(x i ) -ψ(γ(t))| ε for t i t t i+1 and i > n 0 . Thus, for S > n 0 , S i=n 0

ε i ψ(x i ) - t S tn 0 ψ(γ(t)) dt ε(t S -t n 0 ). Since x ∈ ess acc{x i } i ⊂ B, there is δ > 0, such that for all n 1 > n 0 there is S > n 1 with 1 i S ε i ψ(x i ) S i=0 ε i > δ.
Then, taking ε = δ/2,

R n ×R n ψ(x) dµ γ| [0,t S ] (x, v) 1 t S t S tn 0 ψ(γ(t)) dt S i=n 0 ε i ψ(x i ) S i=0 ε i -ε t S -t n 0 t S > δ -ε = δ/2 > 0.
It follows that there is an infinite number of integers S satisfying the previous inequality so that there is some

µ ∈ acc{µ γ| [0,N ] } N with π(supp µ) ∩ supp ψ = ∅.
Observe that we can take the support of ψ to be contained inside any neighborhood of x, so the argument above proves that there are measures in acc{µ γ| [0,N ] } N whose supports are arbitrarily close to x. This proves the first inclusion.

Conversely, assume that x ∈ µ∈acc{µ γ| [0,N ] } N π(supp µ). For a nonnegative continuous function ψ

with x ∈ supp ψ, there is µ ∈ acc{µ γ| [0,N ] } N with ψ dµ > 0.
There is a subsequence of {µ γ| [0,N ] } N converging to µ, hence such that 1 i S ε i ψ(x i )/ S i=0 ε i converges to a positive quantity, so that x ∈ ess acc{x i } i , and we obtain the opposite inclusion.

The following proposition gives some connection between the discrete and the continuous dynamics of the differential inclusion associated to the map -Z.

Proposition 18 (Limiting dynamics). Take Z a field satisfying Assumption 13 together with a sequence {x i } i as in [START_REF] Bernard | Optimal mass transportation and Mather theory[END_REF]. Let {I i } i be a sequence of disjoint, bounded intervals in R with lim i→+∞ |I i | = +∞ and write

G k = I 1 ∪ I 2 ∪ • • • ∪ I k .
Suppose that for some sequence {k i } i ⊂ N, the limit

lim i→+∞ µ γ| G k i
exists, so that, by Lemma 16, it is a closed probability measure µ. Let then ν be a Borel probability measure on the space LipCurv of Lipschitz curves that is invariant under the time-translation τ t and satisfies [START_REF] Barakat | Convergence analysis of a momentum algorithm with adaptive step size for non convex optimization[END_REF]. Then ν-almost every curve β satisfies

-β (t) ∈ Z(β(t)) for almost every t ∈ R. Moreover µ(graph[-Z]) = 1 and the centroid field vx satisfies -v x ∈ Z(x) for π * µ-almost every x ∈ R n , that is μ(graph[-Z]) = 1.
Proof. The existence of ν follows from Theorem 11. By Corollary 12, we know that ν-almost every curve β ∈ LipCurv satisfies, β (t) = vβ(t) for almost every t. So we just need to prove that -v x ∈ Z(x)

for π * µ-almost every x ∈ R n . Recall that graph[-Z] = {(x, v) ∈ R n × R n : -v ∈ Z(x)}.
Let K ⊂ R n be a closed ball that contains the sequence {x i } i as well as π(supp µ), and let N > 0 be such that, for all x ∈ K and v ∈ Z(x), v N . Let t i t < t i+1 , using the triangle inequality, the fact that -γ (t) is constant equal to v i in the interval t ∈ [t i , t i+1 ] and belongs to Z(γ(t i )), we have

dist((γ(t), γ (t)), graph[-Z]) (γ(t), γ (t)) -(γ(t i ), -v i ) + dist((γ(t i ), -v i ), graph[-Z]) = (γ(t), -v i ) -(γ(t i ), -v i ) + 0 = γ(t) -γ(t i ) Lip(γ)ε i N ε i . Now R n ×R n dist((x, v), graph[-Z]) dµ γ| G k i (x, v) = 1 k i j=1 |I j | k i j=1 I j dist (γ(t), γ (t)), graph[-Z] dt N k i j=1 |I j | max t ∈I j ε k i j=1 |I j | . This implies that lim i→+∞ R n ×R n dist((x, v), graph[-Z]) dµ γ| G k i (x, v) = 0
by the Stolz-Cesàro theorem using the fact that, for k large enough, k j=1 |I j | ck for a positive constant c, and the fact that ε i converges to 0 as i → +∞. This, in turn, implies that

R n ×R n dist((x, v), graph[-Z]) dµ(x, v) = 0
because the convergence of measures occurs in the weak* topology and the integrand is continuous. Since graph[-Z] is a closed set, the support of µ must be contained in it. From 10 with a = -1, we know that -v x ∈ Z(x), which is what we wanted to prove.

Theorem 19 (Subgradient-like closed measures are trivial). Assume that g : R n → R is a path differentiable function. Let µ be a closed probability measure on

R n × R n such that µ(graph[-∂ c g]) = 1.
Then the centroid field vx of µ vanishes for π * µ-almost every x.

Proof. The condition on µ implies, by Remark 10 with a = -1, that -v x ∈ ∂ c g(x) for π * µ-almost every x. By Proposition 14 we may choose σ(x) = -v x to compute

R n ×R n ∂ c g(x).v dµ(x, v) = R n ×R n σ(x) • v dµ(x, v) = R n σ(x) • R n v dµ x d(π * µ)(x) = R n σ(x) • vx d(π * µ)(x) = - R n vx • vx d(π * µ)(x).
Proposition 14 also implies that the left-hand side vanishes because µ is closed.

In our proofs below, Theorem 19 will be applied in conjunction with Proposition 18 with Z = ∂ c f . Observe that Theorem 19 could as well have been presented just after Proposition 14, as not much more is needed for its proof.

Proofs of main results

Our proofs use two basic techniques: sometimes we use Theorem 19 to deal with long subsequences of {x i } i , and sometimes we use shorter subsequences and instead use Lemmas 21 and 22, which exploit the Arzelà-Ascoli theorem to obtain curves that describe the asymptotic flow.

The structure of the proofs is described in Figure 4. In contrast, in the paper [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF], item (v) of Theorem 5 is proven first, and item (iv) is deduced from it. Remark 20. An alternative route to the proof of items (iv) and (v) of Theorem 5, closer to the one already given in [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF], is to use Lemma 23 to prove (v) and deduce (iv). Item (v) also follows from [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF]Proposition 3.27].

Lemmas on the convergence of curve segments for general multivalued dynamics

In this section, we consider a set-valued map Z : R n ⇒ R n satisfying Assumption 13 and x i a corresponding sequence as in [START_REF] Bernard | Optimal mass transportation and Mather theory[END_REF].

Lemma 21 (Approximate solutions of differential inclusions). For each i ∈ N, let T i > 0 and assume that T i → T for some T > 0. Let, for each i ∈ N, γ i : [0, T i ] → R n be a Lipschitz curve. Assume that the sequence {γ i } i converges to some bounded, Lipschitz curve γ : [0, T ] → R, γ i → γ, in the sense that sup t∈[0,min(T i ,T )] γ(t) -γ i (t) → 0 and

lim i→+∞ T i 0 dist((γ i (t), γ i (t)), graph[-Z]) dt = 0. ( 13
)
Then -γ (t) ∈ Z(γ(t)) for almost all t ∈ [0, T ].

Proof. We follow classical arguments; see for example [START_REF] Benaïm | Stochastic approximations and differential inclusions[END_REF]Theorem 4.2]. Let 0 < T < T . For i large enough, T i > T because T i → T . In particular, we eventually have uniform convergence of γ i on [0, T ] to the restriction of γ to [0, T ]. For each i, the derivative

γ i is an element of L ∞ = L ∞ ([0, T ]; R d ),
and being uniformly bounded with compact domain, belong to L 2 = L 2 ([0, T ]; R d ) as well. Recall that, since L 2 is reflexive, the weak and weak* topologies coincide in L 2 . So by the Banach-Alaoglu compactness theorem, by passing to a subsequence we may assume that γ j converge weakly in L 2 and weak* in L ∞ to some u ∈ L 2 ∩ L ∞ . Since γ j converges to γ uniformly, γ j → γ also in L 2 . Hence γ j tends to γ in the sense of distributions on [0, T ]; indeed, for all C ∞ functions g : [0, T ] → R with compact support in (0, T ), we have It follows from Mazur's lemma [28, p. 6] that there is a function N : N → N and, for each p k N (p), a number a(p, k) 0 such that N (p) k=p a(p, k) = 1, and such that the convex combinations

N (p) k=p a(p, k)γ k → γ (14)
strongly in L 2 as p → +∞ (and also in the weak* sense in L ∞ ). Since the set Z(x) is convex at each x, the function

g(x, v) = dist(-v, Z(x))
is convex in its second argument for fixed x ∈ R n . Using the fact that the convergence [START_REF] Bianchi | A closed-measure approach to stochastic approximation[END_REF]

+ g(γ k (t), γ k (t))] dt = lim inf p→+∞ T 0 N (p) k=p a(p, k)[dist(γ(t), γ k (t)) + g(γ k (t), γ k (t))] dt
where we have used the triangle inequality. Now, using a uniform bound on the integral, we have 0

T 0 g(γ(t), γ (t)) dt lim inf p→+∞ N (p) k=p a(p, k) T sup t∈[0,T ] [dist(γ(t), γ k (t))] + T 0 g(γ k (t), γ k (t)) lim inf p→+∞ sup p k N (p) T sup t∈[0,T ] [dist(γ(t), γ k (t))] + T 0 g(γ k (t), γ k (t)) lim sup k→+∞ T sup t∈[0,T ] [dist(γ(t), γ k (t))] + T 0 g(γ k (t), γ k (t)) = 0,
where we used the fact that

N (p)
k=p a(p, k) = 1, the fact that γ k → γ uniformly and the hypothesis in [START_REF] Bianchi | Convergence of constant step stochastic gradient descent for non-smooth non-convex functions[END_REF]. Hence we have -γ (t) ∈ Z(γ(t)) for almost all t ∈ [0, T ], and this proves the lemma since T was taken arbitrary in (0, T ).

Lemma 22 (Limiting dynamics for discrete sequences). Let γ be the interpolant curve of the bounded sequence {x i } i , and {I j } j a collection of pairwise-disjoint intervals of R 0 of length 1/C |I j | C for some C > 1. Then, there is a subsequence {j k } k ⊂ N such that the restrictions γ|

I j k converge uniformly to a Lipschitz curve γ : [a, b] → R that satisfies -γ (t) ∈ Z(γ(t)) for almost every t ∈ [a, b].
If we additionally assume that the sequence {x i } i is generated by the subgradient method, so that -v i ∈ ∂ c f (x i ) for some locally Lipschitz, path differentiable function f , then the curve γ satisfies

- b a γ (t) 2 dt = f • γ(b) -f • γ(a).
b a γ (t) 2 dt = b a ∂ c f (γ(t)) • γ (t)dt = b a (f • γ) (t) dt = f • γ(b) -f • γ(a).

Proof of Theorem 4

Item (i)

Let γ be the interpolant curve of the sequence {x i } i , and consider the intervals I k = [t i k , t i k ], so that the endpoints of the restriction γ| I k are precisely γ(t i k ) = x i k and γ(t i k ) = x i k . Aiming for a contradiction, assume that the numbers Tk = t i k -t i k remain bounded. Apply Lemma 22 to obtain a curve γ : [a, b] → R n joining γ(a) = lim k x i k = x and γ(b) = lim k x i k = y. We have that the arc length of γ must be positive because x = y, while γ also satisfies, as part of the conclusion of Lemma 22,

0 > - b a γ (t) 2 dt = f • γ(b) -f • γ(a) = f (y) -f (x) 0.
Whence we get the contradiction we were aiming at.

Item (ii)

Let B ⊂ R n be a closed ball containing the sequence {x i } i . By convexity, B contains also the image of the interpolating curve γ.

Fix ε > 0. By uniform continuity of ψ over B, there exists n 0 > 0 such that i > n 0 , x, y ∈ B and |x -y| ε i Lip(f ) imply |ψ(x) -ψ(y)| ε and ε i 1. We hence have |ψ(x i ) -ψ(γ(t))| ε for t i t t i+1 and i > n 0 . Thus

N j i=n 0 ε i v i ψ(x i ) - t N j tn 0 γ (t)ψ(γ(t))dt ε Lip(f )(t N j -t n 0 ) and 1 N j i=0 ε i N j i=0 ε i v i ψ(x i ) - t N j 0 γ (t)ψ(γ(t))dt 1 N j i=0 ε i n 0 -1 i=0 ε i v i ψ(x i ) - tn 0 0 γ (t)ψ(γ(t))dt + ε Lip(f )(t N j -t n 0 ) .
Since ∞ i=0 ε i = +∞ and ε > 0 was arbitrary, it follows that the latter becomes arbitrarily small as N j grows. Whence the quotient in the limit in the statement of item (ii) is very close, for large j, to

N j i=0 ε i N j i=0 ε i ψ(x i ) R n ×R n vψ(x)dµ γ| [0,t N j +1 ] (x, v).
We now prove that the above quantity converges to 0 as j → +∞. Taking a subsequence so that µ γ| [0,t N j +1 ] converges to some probability measure µ, the quotient on the left converges to 1 ψ(x) dπ * µ(x), and our hypothesis on the subsequence {N j } j thus guarantees that ψ(x) dπ * µ(x) > 0. Thus, it suffices to show that, for every limit point µ of the sequence {µ γ| [0,t N +1 ] } N satisfying ψ(x) dπ * µ(x) > 0, we have

R n ×R n v ψ(x) dµ(x, v) = R n vx ψ(x) d(π * µ)(x) = 0, ( 15
)
where vx is the centroid field of µ. By Lemma 16 we know that µ is closed so that Proposition 18 and Theorem 19 apply and give vx = 0 for π * µ-almost every x. This immediately implies (15).

Item (iii)

To prove item (iii), consider the interpolation curve constructed in Section 4.3. Consider a limit point µ of the sequence {µ γ| [0,N ] } N . By Lemma 16, µ is closed. By Proposition 18 and Theorem 19, the centroid field vx of µ vanishes for π * µ-almost every x, so from [START_REF] Bernard | Young measures, superposition and transport[END_REF] we know that 0 = -v x ∈ ∂ c f (x), and hence x ∈ crit f for a dense subset of π(supp µ). Since this is true for all limit points µ, by Lemma 17 we know that it is true throughout ess acc{x i } i .

5.3 Proof of Theorem 5

The function is constant on the accumulation set

Lemma 23 (f is constant on its limit set). Assume that the path differentiable function f : R n → R is constant on each connected component of its critical set, and let {x i } i be a bounded sequence produced by the subgradient method. Then f is constant on the set acc{x i } i of limit points of {x i } i .

Proof. Assume instead that f takes two values J 1 < J 2 within acc{x i } i .

Let K be a compact set that contains the closure {x i } i in its interior. Since f is constant on the connected components of crit f and since f is Lipschitz, the set f (K ∩ crit f ) has measure zero because, given ε > 0, the connected components C i of K ∩ crit f of positive measure |C i | > 0 -of which there are only countably many-can be covered with open sets

f -1 ((f (C i ) -ε/2 i+1 , f (C i ) + ε/2 i+1 ))
with image under f of length ε/2 i ; the rest of K ∩ crit J has measure zero, so it is mapped to another set of measure zero. The set f (K ∩ crit f ) is also compact, so we conclude that it is not dense on any open interval of R.

We may thus assume, without loss of generality, that the values J 1 and J 2 are such that there are no critical values of f | K between them.

Pick

c 1 , c 2 ∈ R such that J 1 < c 1 < c 2 < J 2 .
Let W 1 = f -1 (-∞, c 1 ) and W 2 = f -1 (c 2 , +∞). Clearly W j ∩ acc{x i } i = ∅ because the value J j is attained in acc{x i } i , j = 1, 2. Consider the curve γ : R 0 → K ⊂ R n interpolating the sequence {x i } i . Let A be the set of intervals A = {[t 1 , t 2 ] ⊂ R : t 1 < t 2 , γ(t 1 ) ∈ ∂W 1 , γ(t 2 ) ∈ ∂W 2 , γ(t) / ∈ W 1 ∪ W 2 for t ∈ (t 1 , t 2 )} Write A = {I j } j∈N for maximal, disjoint intervals I j . Observe that if I j = [t j 1 , t j 2 ], then we have, by the path differentiability of f , that

t j 2 t j 1 ∂ c f (γ(t)) • γ (t) dt = t j 2 t j 1 (f • γ) (t) dt = f • γ(t j 2 ) -f • γ(t j 1 ) = c 2 -c 1 . (16)
Let µ be a probability measure that is a limit point of the sequence {µ γ| ∪ N i=0 I i

} N .
Now, since f is Lipschitz and W 1 and W 2 are compact, |I i | is bounded from below, let us say

|I i | > α.
It is also bounded from above, because if not then there is a subset {I i j } j of A consisting of intervals with length |I i j | → +∞, and we can apply Lemma 16, Proposition 18, and Theorem 19 to get closed measures μ with supp π * μ ⊂ crit f . Since the support of each such π * μ is contained in K \ (W 1 ∪ W 2 ), this would mean the existence of a critical value between c 1 and c 2 , which contradicts our choice of J 1 and J 2 . We conclude that the size of the intervals in A is also bounded from above, say, We also know that γ interpolates a gradient sequence, so we may use the path differentiability of f and the second part of Lemma 22 to see that this integral must be nonpositive, a contradiction that proves that statement of the lemma.

|I i | < β.

Proof of item (i)

For j ∈ N, let I j = [t i j , t i j+1 ] ⊂ R be the interval closest to 0 with t j t i j < t i j+1 , γ(t i j ) ∈ B δ (x), and γ(t i j+1 ) ∈ B δ (y), so that T j = t i j+1 -t i j . Let γ| I j be the restriction of the interpolant curve γ. Since the two balls B δ (x) and B δ (y) are at positive distance from each other, and since the velocity is bounded uniformly γ Lip(f ), we know that the numbers T j = |I j | are uniformly bounded from below by a positive number.

Assume, looking for a contradiction, that there is a subsequence of {T j } j that remains bounded from above. Apply Lemma 22 to obtain a curve γ : [a, b] → R such that γ(a) ∈ B δ (x) ∩ acc{x i } i and γ(b) ∈ B δ (y) ∩ acc{x i } i , while also satisfying

- b a γ (t) 2 dt = f • γ(b) -f • γ(a) = 0 (17)
by Lemma 23. This contradicts the fact that the distance between the balls B δ (x) and B δ (y) -and hence also the arc length of γ-is positive.

Proof of item (ii)

Aiming at a contradiction, we assume instead that there is some x ∈ U ∩acc{x i } i and some subsequence {i j } j such that dist(x, γ(I i j )) → 0 and |I i j | C for some C > 0 and all j ∈ N. We may thus apply Lemma 22 to get a curve γ : [a, b] → R n whose endpoints γ(a) and γ(b) are contained in acc{x i } i \ V , and γ passes through x ∈ U , so it has positive arc length. However, it is also a conclusion of Lemma 22, together with Lemma 23, that γ satisfies [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF], which makes it impossible for its arc length to be positive, so we have arrived at the contradiction we were looking for.

Proof of item (iii)

Let U , V , and A be as in the statement of item (iii). Let B = i∈A [t i , t i+1 ). The statement of item (iii) is equivalent to the statement that lim

N →+∞ v dµ γ| B∩[0,N ] = 0. ( 18
)
It follows from item (ii) that the maximal intervals I i ⊂ N comprising A = i I i satisfy |I i | → +∞ as do the lengths j∈I i ε j of the intervals j∈I i [t j , t j+1 ) ⊂ B. Hence, from Lemma 16 we know that any limit point µ of the sequence {µ γ| B∩[0,N ] } N is closed. This implies [START_REF] Borwein | A chain rule for essentially smooth Lipschitz functions[END_REF] because each coordinate v k of the integrand v = (v 1 , . . . , v n ) is a gradient: v k = ∇p k • v for p k (x) = x k , so each entry of the integral (18) vanishes.

Proof of item (iv)

Let x ∈ acc{x i } i . For any neighborhood U of x, we can take a slightly larger neighborhood V and repeat the construction described in the proof of item (iii) (Section 5.3.4) of a closed measure µ whose support intersects U , and whose centroid field vanishes π * µ-almost everywhere. By Remark 10 we know that the centroid field satisfies -v x ∈ ∂ c f (x). In sum, we have that in every neighborhood U of x, there is a point y ∈ U with 0 ∈ ∂ c f (y), which implies that 0 ∈ ∂ c f (x) because the graph of ∂ c f is closed in R n × R n .

Proof of item (v)

Recall that acc{x i } i is connected. We know from item (iv) that acc{x i } i ⊆ crit f . So it is contained in a single connected component of crit f . Hence f must be constant on acc{x i } i , and {f (x i )} i converges.

Figure 1 :Figure 2 :

 12 Figure 1: Contour plot of a Lipschitz function with a subgradient sequence. The color reflects the iteration count. The sequence converges to the unique global minimum, but is constantly oscillating.

Figure 4 :

 4 Figure 4: Arrows indicate results that are used in the proofs of the statements they point to.

T 0 γ

 0 j (t)g(t) dt = -T 0 γ j (t)g (t) dt → -T 0 γ(t)g (t) dt = T 0 γ (t)g(t) dt since we have convergence in L 2 . By uniqueness of the limit, u = γ almost everywhere on [0, T ].

Proof.

  By passing to a subsequence, we may assume that the lengths |I j | converge to a positive number. By the Lipschitz version of the Arzelà-Ascoli theorem, we may pass to a subsequence such that γ| I j k converges uniformly to a curve γ on an interval [a, b] of length lim j→+∞ |I j | > 0. Condition (13) holds if we let γ i be the appropriate translate of γ| I i , so by Lemma 21, -γ (t) ∈ Z(γ(t)) for almost every t ∈ [a, b].

-

1 ∂

 1 Apply the first part of Lemma 22 to obtain a subsequence {j k } k such that {γ|I j k } k converges uniformly to a Lipschitz curve γ : [a, b] → R n joining γ(a) ∈ W 1 with γ(b) ∈ W 2 . By (16), we have b a ∂ c f (γ(t)) • γ (t) dt = lim c f (γ(t)) • γ (t) dt c 2 -c 1 > 0.

  happens pointwise almost everywhere, we have, by continuity of g and by the fact that countable union of zero measure sets has zero measure, for almost all t ∈ [0, T ] step follows from Jensen's inequality and convexity of g in its second argument. Since g is non negative, integrating on [0, T ], we have using Fatou's Lemma,

	where the last 0	T	g(γ(t), γ (t)) dt
	0
				T	N (p)
	lim inf p→+∞	0	k=p	a(p, k)g(γ(t), γ k (t)) dt
				T	N (p)
	lim inf p→+∞	0	k=p	a(p, k)[dist((γ(t), γ k (t)), (γ k (t), γ k (t)))
		g(γ(t), γ (t)) = g(γ(t), lim p→+∞	N (p) k=p a(p, k)γ k (t))
					= lim p→+∞	g(γ(t),	N (p) k=p a(p, k)γ k (t))
					N (p)
					lim inf p→+∞	k=p	a(p, k)g(γ(t), γ k (t)),

In Figure1, we see the sequence descending along a ridge. The jumps xi+1 -xi can be decomposed into two components, one that is parallel to the "ridge" and another one that is perpendicular to it; we will informally refer to these components, respectively, as the drift and the bouncing, without attempting to define these concepts formally, (see however the discussion before Lemma 8). Similarly we shall often use the term oscillations to evoke notable and persistent variations of the directional term xi+1 -xi/ xi+1 -xi over time.

Literally from the French, "healthy functions", as opposed to pathological.

Acknowledgements. The authors acknowledge the support of ANR-3IA Artificial and Natural Intelligence Toulouse Institute. JB and EP also thank Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant numbers FA9550-19-1-7026, FA9550-18-1-0226, and ANR MasDol. JB acknowledges the support of ANR Chess, grant ANR-17-EURE-0010, TSE-P and ANR OMS.