Florent Jacquemard
email: florent.jacquemard@inria.fr

Masahiko Sakai
email: sakai@i.nagoya-u.ac.jp

Yosuke Amagasu
email: amagasu@trs.css.i.nagoya-u.ac.jp

TOKENIZATION OF MIDI SEQUENCES FOR TRANSCRIPTION

There generally exists no simple one-to-one relationship between the events of a MIDI sequence, such as note-on and note-off messages, and the corresponding music notation elements, such as notes, rests, chords, and ornaments. We propose a method for building a formal correspondence between them through a notion of tokens in an input MIDI event sequence and an effective tokenization approach based on a hierarchical representation of music scores. Our tokenization procedure is integrated with an algorithm for music transcription based on parsing wrt a weighted tree grammar. Its effectiveness is shown on examples.

INTRODUCTION

In the context of compiling (lexical analysis) and in Natural Language Processing (NLP), tokenization is the act of dividing a character sequence into elementary subsequences called tokens. The primary purpose of tokenization is to identify, in the early steps of processing, meaningful subsequences of characters in preparation for the next steps. For instance, tokenization consists of finding keywords and identifiers with automata-based pattern-matching techniques in compiling. For NLP based on statistical learning, tokenization aims at building sequential encodings of character sequences into integer vectors, using a dictionary of tokens, for training language models.

In languages based on Latin alphabets (including programming languages), tokens are generally words or subwords. The tokenization into words, in particular, is eased by space separation. The case of written Japanese language is more complicated since there is no space separation (although some punctuation exists). Therefore, some realtime tokenization process is required when reading a text. In the case of hiragana characters (phonetic characters), ambiguity may arise in tokenization, leading to confusion.

Similar ambiguity problems may occur when processing symbolic music data in sequential form, in particular MIDI data, in order to extract more structured information. A MIDI flow (or file) is essentially an unstructured sequence of messages, each one representing an elementary event for the production of music with an electronic instrument. Two common events are the start of a note (note-on), corresponding to a key press, and the end of note (noteoff ), for a key release. On the other hand, higher-level musical elements of Common Western musical notation, such as notes, rests, chords, grace notes, and other ornaments may correspond to several successive MIDI events, and conversely. Therefore, extracting such notational elements from a MIDI flow, in e.g., a task like MIDI-to-score transcription, requires a processing similar to tokenization.

Let us illustrate this point of view with sneak observations on the short MIDI sequence of Figure 1, and some of its possible denotations as a 4/4 measure in a music score. We use a representation similar to a piano-roll, with note pitches on the vertical axis, time on the horizontal axis, and note-on events depicted as black dots and note-off as white dots. Several grouping of these events into tokens are considered in cases (a) to (h) of Figure 1 and correspond to different notations. Note that the piano-roll is the same in all these cases. In each case, the tokens, called T 0 to T n (n depending on the case) are represented with blue boxes. Intuitively, all events in a token T i represent one or several music notation elements occurring at the same time position τ i in a score. The time position τ i associated with the token T i is indicated on the axis under the corresponding blue box. The notation elements represented may be e.g., one note, one chord, some grace notes and one note, etc. In other terms, the groupings defined by the tokens can be seen as a re-alignment of MIDI events, like with a rhythm quantization functionality of a Digital Audio Workstation (DAW), except that the alignment points τ i are not evenly distributed in a grid. One strategy for defining the alignment points τ i according to hierarchical structures is proposed in Section 4.

Going back to Figure 1, in the first tokenization (a), and corresponding notation (a)', the two first note-on events (D4 and A4) belong both to the first token T 0 , and their matching note-off events belong to the next tokens, resp. T 1 and T 2 . This situation corresponds to two notes starting simultaneously on the first beat of the measure (time position τ 0 = 0), and ending on different later beats: beat 2 (time position τ 1 = 1 4 ) for D4, and beat 3 (time position τ 2 = 1 2 ) for A4. It is denoted as an interval tied to a quarter note.

In the tokenization in Figure1(f) however, both the noteon and note-off events of D4 belong to the first token T 0 , aligned at time position τ 0 = 0 (beat 1). It follows that this note is a grace-note located at τ 0 . On the opposite, the A4 has its note-on in T 0 and its note-off in T 1 , aligned at time position τ 1 = 1 2 (beat 3). Hence, this note is a half note, with the D4 as an ornament, see Figure 1(f)'.

The interpretation of the other tokens of Fig. 1 is similar. (g) Tokenization 7

(g)' Score obtained from (g) Note that in case (c), and (g), two pairs of matching noteon and note-off events are embedded in the third token. It follows that the last note D4 has two grace notes E and B . Therefore, we see in Figure 1 many possible denotations of the same MIDI sequence. How were chosen the tokens in this picture, in order to be associated a notation? Which denotation shall be considered the best?

0 1 1 4 1 2 5 8 (h) Tokenization (h)' Score obtained from (h)
In this paper, we propose a formal definition of the notion of token of MIDI events, as an attempt to clarify the correspondence between MIDI events and music notation elements. We characterize in particular what notation can be associated with a token, defining several types of tokens, corresponding to different notations. We focus in particular on notation elements which are not the most studied in the literature on music notation and symbolic music processing in general, namely the rests and the ornaments.

The main motivation for this study is the processing of MIDI data, in particular its transcription into Common Western music notation, a task sometimes referred to as MIDIto-score Automatic Music Transcription (M2S-AMT). We propose an efficient procedure for tokenization and its integration into a M2S-AMT framework. The approach is based on parsing [START_REF] Grune | Parsing Techniques, ser[END_REF], in its usual computational sense: the inferrence of some (hierarchical) structure from unstructured (sequential) data. In these settings, we consider tree structures for defining hierarchically the time boundaries of tokens. A weighted tree grammar generates those trees, and the estimation of the best tree (wrt weight) in the grammar's language is performed by a dynamic programming algorithm. This method is implemented in a framework for MIDI-to-score transcription in development.

Related Work. Compiling (textual) programming languages generally involves steps of lexical analysis and syntactic analysis (parsing) [START_REF] Grune | Parsing Techniques, ser[END_REF]. In some sense, we follow a similar approach in our transcription approach, briefly described above. However, a significant difference is that, in our case, several tokenizations of the MIDI input are possible, and we must explore possibilities to choose the one giving the best notational result.

In the literature on music generation, several works propose sequential encodings of MIDI data in order to train models like the Transformer [START_REF] Zeng | MusicBERT: Symbolic music understanding with large-scale pre-training[END_REF][START_REF] Ren | Popmag: Pop music accompaniment generation[END_REF][START_REF] Hadjeres | The piano inpainting application[END_REF][START_REF] Oore | This time with feeling: Learning expressive musical performance[END_REF][START_REF] Huang | Pop music transformer: Beat-based modeling and generation of expressive pop piano compositions[END_REF][START_REF] Hsiao | Compound word transformer: Learning to compose full-song music over dynamic directed hypergraphs[END_REF][START_REF] Gardner | MT3: Multi-task multitrack music transcription[END_REF][START_REF] Fradet | Byte pair encoding for symbolic music[END_REF][START_REF] Ens | MMM : Exploring conditional multi-track music generation with the transformer[END_REF]. Some of these encodings, often referred to as MIDI tokenization, are implemented in the library MIDItok [START_REF] Fradet | MidiTok: A python package for MIDI file tokenization[END_REF]. Their purpose is to format MIDI data as a sequence of tokens, where, roughly, each token represents one elementary component of a MIDI event (position, duration, pitch value, etc). This notion of elementary token is very different from the one we present here, where every token is made of several MIDI events (considered atomic) and conveys higher-level musical information about the notation. Some strategies for grouping elementary tokens are proposed e.g., in [START_REF] Hsiao | Compound word transformer: Learning to compose full-song music over dynamic directed hypergraphs[END_REF], in order to reduce training sequences. Another critical difference is that the purpose of the above tokenization approaches is the generation of MIDI data by trained model, whereas our purpose is the construction of music notation from MIDI data.

The sequential input and structured output of M2S-AMT are of very different natures, and establishing a relation-ship between input MIDI events and output score elements is not a trivial task, considering the richness of music notation. For instance, many existing M2S transcription tools, including general public ones, like MuseScore, fall short of detecting ornaments and rests. As observed formarly [START_REF] Foscarin | A Parse-based Framework for Coupled Rhythm Quantization and Score Structuring[END_REF] problems often come from mismatches between input and output. Several transcription tools ignore note-off events to cope with the mismatches. In other works, note-on and note-off events are treated in different passes [START_REF] Shibata | Non-local musical statistics as guides for audio-to-score piano transcription[END_REF]. We believe that the notions of tokens and token types proposed here can help in making progress in the production of music notation, such as in M2S-AMT, in particular regarding the treatment of rests and ornaments in preprocessing. However, it should be noted that in the present work, we only consider homophonic input (monophonic voices including chords), whereas [START_REF] Shibata | Non-local musical statistics as guides for audio-to-score piano transcription[END_REF][START_REF] Suzuki | Score transformer: Transcribing quantized midi into comprehensive musical score[END_REF] deal with the transcription piano input, which is a much harder problem.

The main contributions of this paper are the following:

• the definition of tokens as sequences of MIDI events corresponding to notation elements (Section 2),

• the proposition of an efficient procedure using trees for dividing a MIDI sequence into tokens (Section 3),

• a dynamic programming algorithm for parsing a MIDI sequence into structured music notation, joined with the above tokenization procedure (Section 4).

MIDI EVENTS, TOKENS AND SCORE ELEMENTS

In this section, we define a correspondence between music notation elements and sequences of MIDI events called tokens, as described informally in Figure 1. Each token is given a token type, a note, rest, or chord, with or without an ornament, corresponding to the score element. On the other hand, a MIDI event in a token may have an individual role, which we call an event role in the token.

MIDI Events

We consider a typical representation, in the form of socalled timestamped MIDI events, of the note-on and noteoff messages in a MIDI file, often depicted as a piano-roll.

A MIDI event e (or event for short) is made of the following components:

• a real-time value ts(e) ∈ Q, expressed in seconds,

• an integral pitch value pitch(e) ∈ {0, . . . , 128},

• an integral velocity value vel(e) ∈ {0, . . . , 128},

• an attribute flag(e) which is either on when e is a note-on message, or off for a note-off message.

A MIDI sequence E = e 1 , e 2 , . . . , e n is a finite sequence of MIDI events with increasing timestamps, i.e., such that ts(e 1 ) ≤ ts(e 2 ) ≤ • • • ≤ ts(e n ). The length of E is denoted by |E| = n and the concatenation of two sequences E and E is denoted by E E . We use the set-like-notation

e ∈ E to express that the event e belongs to the MIDI sequence E. The subset of note-on (resp. note-off) events in a sequence E of events is denoted by on

(E) = {e ∈ E | flag(e) = on} (resp. off(E) = {e ∈ E | flag(e) = off}).
The event matching e in a sequence E, denoted by e -1 is the first note-off after e with the same pitch when e is a note-on, and the note-on event d such that d -1 = e when e is a note-off. Formally, for all event e,

• pitch(e -1 ) = pitch(e) and flag(e -1 ) = flag(e),

• if flag(e) = on, then ts(e) < ts(e -1 ) and for all e such that ts(e) < ts(e ) < ts(e -1 ), it holds that pitch(e ) = pitch(e), and

• if flag(e) = off, then e -1 = d such that d -1 = e.
The matching operator is idempotent: (e -1 ) -1 = e. We shall consider below only well-formed MIDI sequences E, such that e -1 exists in E for all e ∈ E.

Example 1. Figure 2 presents the events e 1 , . . . , e 10 of the MIDI sequence in Figure 1. This sequence is well-formed, and e 1 -1 = e 3 , e 2 -1 = e 4 , e 3 -1 = e 1 , e 4 -1 = e 2 , e 5

-1 = e 8 , . . . , e 10 -1 = e 7 .

Tokens

In order to be converted into music notation, the MIDI events of an input sequence can be aligned to some salient time points, like the grid points in DAWs or in earlier rhythm quantization algorithms [START_REF] Agon | Kant: a critique of pure quantification[END_REF][START_REF] Cemgil | Rhythm quantization for transcription[END_REF]. It may happen that several events, neighbours in a MIDI sequence E are aligned to the same time point. The notion of token aims at capturing the subsequences of events of E made simultaneous after alignment. More precisely, a token of E is a non-empty subsequence T = e i , . . . , e j of E with 1 ≤ i ≤ j ≤ n, that is moreover closed wrt time equality: every e ∈ E such that ts(e) = ts(e k ) for some i ≤ k ≤ j must be in T . We shall use below the number ns E (T ) of notes sounding just after the timestamp of the last event of a token T . Formally, it is defined as the following cardinality:

ns E (T ) = e ∈ E | flag(e) = on, ts(e) ≤ < ts(e -1 )
where = ts(e) for the last event e ∈ T i.e., for all e ∈ T , ts(e ) ≤ ts(e).

Intuitively, a token aims at containing some MIDI events representing simultaneous score elements, i.e., elements occurring at the same musical date (beat) in the score. This can be the case of several notes involved in a chord, or of one note with one or several grace notes, or another specific ornament (mordent, gruppetto, trill...). Note that we are talking here about the theoretical simultaneity of notes in the score, not of simultaneity in a performance. In the score, all the notes of an ornament occur at the same theoretical date, in beats, as the note they decorate. However, during a performance, they will occur shortly before or after the decorated note.

Event Role in a Token

Only some combinations of MIDI events will appropriately fit into one case, corresponding to a notation, like in Figure 1. Having too many events in a token may make no sense. In order to capture tokens that can be considered valid, i.e., that can be transcribed into simultaneous notation elements, we introduce the notion of role of a MIDI event e in a token T . It is defined according to the flag of e (on or off-note) and to the presence or not in T of the matching event e -1 , as presented in Figure 3.

Intuitively, the role grace note corresponds to notes with a theoretical duration of 0 in a score. It can be an appogiatura, an accaciatura, or a part of another ornament, which expresses the fact that both the start (note-on e) and the end (note-off e -1 ) of the corresponding note belong to the same token T . On the opposite, an event of role note corresponds to a note starting in a token T (e ∈ on(T )), but ending in a subsequent token (e -1 / ∈ T ). A note-off event matching an event in the token will have role goff. Otherwise, it shall have role noff. The event role goff is important in the context of MIDI processing. Indeed, events with this role correspond to micro-rests that may occur e.g., when a key of a MIDI keyboard is released before the key for the next note is pressed (i.e., the play is not enough legato). In general, one does not want such artifacts to be transcribed literally, and in several transcription procedures, micro-rests are discarded in a pre-processing step relying on parameters to be set, like the maximal duration of a micro-rest. In our approach, micro-rests are detected as a special case of event role noff or goff in a token, and may be discarded at will.

Token Types and Validity

We consider a finite set K of type names that can be assigned a token T in a MIDI sequence E as follows, according to the respective roles of the events in T :

T has type chord with n (> 0) notes and an ornament of size p (≥ 0), denoted by ch n,p , if and only if it contains n events of role note, it contains p events of role grace-note, each grace note occurs before any note in T , and ns E (T ) = n (the n notes sound after the token).

T has type rest denoted by r, if and only if T = off(T )( = ∅) and ns E (T ) = 0, T has type partial continuation, denoted by pc, if and only if T = off(T )( = ∅), and ns E (T ) > 0.

The cases of a single note or an interval correspond respectively to the types chord with 1 note and chord with 2 notes. We use the name chord for these types of abuse in order to shorten the definition of token types. As explained above, an ornament of size p corresponds to a sequence of events occurring at the same musical date (beat) in a score.

In this description, we use, for simplicity, the generic term of "ornament of size p", but we could distinguish between different kinds of ornaments, such as mordent, gruppetto or trill, or also a tremolo (or roll in the case of drums), by analyzing the respective MIDI pitch values of the events involved.

A rest corresponds to the case where some note ends during the token T (a note-off e ∈ T ). No other note or grace note shall start in the same token (the condition T = off(T ) implies that on(T ) = ∅), and every note started before ends in T (condition ns E (T ) = 0). Moreover, T contains no grace note (another consequence of on(T ) = ∅), since in CW music notation, no grace notes or ornaments may be attached to rests. The latter case may, however, correspond to a note played very shortly, and wrongly interpreted as a grace note. In our framework, we consider an option where such a grace note is transcribed into a note with an articulation staccato or staccatissimo. A continuation represents the prolongation of an event (either a note or a chord), with a tie or a dot. A continuation is partial when some but not all chord notes are prolongated. Remark that no token exists with type (full) continuation because we defined an empty set, which corresponds to a continuation, is not a token.

Token Validity

Tokens of the above types will be considered valid or not for transcription, according to the case of input considered.

Monophonic case

When the input is considered as strictly monophonic, at most one note shall sound at a time. Hence, a token considered valid in this case is a note, i.e., a chord with 1 note, with an ornament of size p ≥ 0 or a rest. This case is appropriate e.g., for the M2S transcription of a single voice, of a monophonic instrument like winds or one piano voice in strict counterpoint.

Homophonic case

This case generalizes the previous one by allowing some chords in a monophonic voice. Then, tokens of all three above types are considered valid, and the others are not valid (discarded in the transcription procedure). This case is appropriate for the M2S transcription of monophonic instruments like strings (where some chords may occur) or one voice of the piano.

Case of Drums

In the case of MIDI files recorded with electronic drumkits, see e.g., [START_REF] Jacquemard | Symbolic weighted language models, quantitative parsing and automated music transcription[END_REF][START_REF] Digard | Automated transcription of electronic drumkits[END_REF], the MIDI pitches encode the drumkit parts (snare drum, kick, toms, hi-hat, and different kinds of cymbals) and the play mode (e.g., on the head or rim of snare drum or toms, on the ride, edge, or bow of cymbals, and so on) Moreover, in such input, the note-off events are not significant (for instance, they are added at a fixed duration, e.g., 20ms, after the matching note-on event) and can be safely ignored. Concretely, for this case, we change the definition of event role such that every e ∈ off(T ) has an extra role ignored, which excludes the rests from the transcription output. Actually, in a post-processing step, some rests are re-introduced by conversion of some continuations, when appropriate for the readability of the score (see [START_REF] Digard | Automated transcription of electronic drumkits[END_REF] for details).

The definition of token validity follows additional constraints for drums. First, only ornaments of size 1, called flams, are allowed, and only for some parts of the drumkit. Second, chords are allowed (the drum is a polyphonic instrument) but with some restrictions: sticks cannot play more than two notes, and two notes played by pedals involved in the same chord. Finally, some particular effects like cross-stick, rim-shot or buzz-roll (see descriptions in [START_REF] Digard | Automated transcription of electronic drumkits[END_REF]) require a particular processing of tokens. Some possible errors of capitation by MIDI sensors also need to be handled. We leave the details about these particular cases out of the scope of this paper.

Polyphonic case

This paper does not cover the polyphonic case, which requires a step of voice separation. To directly cope with polyphonic MIDI sequences, tokens are not just a partition of the input sequence. In fact, multiple tokens shall correspond to interleaved events in a MIDI-sequence, which is a complex extension to handle. We call tokenizer a procedure that takes in input a MIDI sequence E and returns a sequence of valid tokens T 1 , . . . , T k that form a partition of E.

TREE-BASED TOKENIZATION PROCEDURE

In this section, we propose a tokenizer based on a tree structure. Intuitively, the idea is that the salient time points defining the tokens (by alignment of MIDI events) are characterized by a recursive subdivision of time intervals to reflect a metric organization of musical events [START_REF] Yust | Organized Time[END_REF]. This point of view is more involved (and more realistic) than considering regular space points in a grid (e.g., one point every 16th note). It corresponds to a tree-based representation of music notation.

Real and Musical Time Scales

Here, we consider input MIDI sequences corresponding to performances. Their MIDI events are timestamped in a real time scale, whose units are seconds. By contrast, the durations in a music score are expressed in a musical time scale, whose units are beats or bars (given a time signature). The correspondence between these two time-scales is ensured by a tempo function, converting real-time values to musical-time ones. For the sake of presentation, we assume here a coincidence of these two-time scales, or equivalently, a constant tempo. We especially use a bar as a unit of musical time. The extension of the approach presented here to varying tempo functions is out of the scope of this paper.

Time Intervals

A time interval I = [τ 0 , τ 1 ) is defined by a pair of time points τ 0 ∈ Q and τ 1 ∈ Q ∪ {+∞}: I starts at time τ 0 and ends just before τ 1 , i.e., [τ 0 , τ 1 ) = {τ | τ 0 ≤ τ < τ 1 }. In the sequel, we use the notation start(I) for τ 0 and end (I) for τ 1 . The interval div n (I, i), for 1 ≤ i ≤ n, is the ith sub-interval obtained by splitting I into n parts of equal

duration ∆ = τ 1 -τ 0 n when I = [τ 0 , τ 1 ), div n (I, i) = [τ 0 + (i -1) • ∆, τ 0 + i • ∆).
If end (I) = +∞, then div n (I, i) is undefined. Moreover, for I = [τ 0 , τ 1 ) with τ 1 > τ 0 + 1 (including the case τ 1 = +∞), we define unit(I) as the subinterval [τ 0 , τ 0 +1) of duration one bar, and rem(I) for the remaining interval [τ 0 + 1, τ 1 ), i.e., rem(I) = I \ unit(I). The latter is undefined when τ 1 < τ 0 + 1.

Trees

The trees defined in this section represent hierarchies of nested time intervals, defining salient points for alignment in tokens. Intuitively, the higher the points are in the hierarchy (in the tree), the strongest the corresponding beat is, from a meter point of view. The trees are labeled with two kinds of symbols: • every inner node is labeled with a function symbol from a fixed finite set F,

• every leaf is a node labeled with the empty symbol ε or a token type in K, as defined in Section 2.4.

Every function symbol of F is associated with an operation on time intervals. We consider here two kinds of such operations:

div n , for n > 0, divides an interval I into n sub-intervals div n (I, 1), . . . , div n (I, n) of the same duration;

bar (bar split), divides an interval I in two parts: unit(I) and rem(I).

Here, trees are in the form of Figure 5. Each left child of bar represents the content of one measure. We restrict the second argument of the bottom bar to ε for termination. The set of trees labeled with symbols of F and K is denoted by T (F, K). We denote by yield (t) the sequence of token type names of K labelling the leaves of a tree t ∈ T (F, K). Note that yield (t) does not contain an empty leaf symbol ε.

Example 3. Figure 6 depicts the trees corresponding to the scores in cases (a) to (d) of Figure 1. Each tree, rooted with bar, represents one measure whose content is the left subtree.

Tree-based Tokenizer

Let t ∈ T (F, K) and let I be a time interval associated with the root node of t. We can associate a sub-interval of I to every other node of t, following the above interpretation of the symbols of F.

bar div 2 div 2 ch 2,0 pc div 2 ch 2,1 r ε [0, ∞) [0, 1) [0, 1 2 ) [0, 1 4 ) [ 1 4 , 1 2 ) [ 1 2 , 1) [ 1 2 , 3 4 ) [ 3 4 , 1) [1, ∞) 0 1 1 4 1 2 3 4
(a) Tree t 1 for Figure 1(a)

bar div2 div2 ch2,0 div2 pc div2 r ch1,0 div2 ch2,0 r ε [0, ∞) [0, 1) [0, 1 2 ) [0, 1 4 ) [ 1 4 , 1 2 ) [ 1 4 , 3 8 ) [ 3 8 , 1 2 ) [ 3 8 , 7 16
) [ 7 16 , 1 2 ) [ 1 2 , 1) [ 1 2 , 3 4 ) [ 3 4 , 1)
[1, ∞) 0 1

[0, ∞) [0, 1) [0, 1 2 ) [0, 1 4 ) [ 1 4 , 1 2 ) [ 1 2 , 1) [1, ∞) [1, 2) [2, ∞) 0 1 1 4 1 2 (c) Tree t 3 for Figure 1(c) bar div 2 div 2 div 2 ch 2,0 pc ε div 2 ch 2,1 r ε [0, ∞) [0, 1) [0, 1 2 ) [0, 1 4 ) [0, 1 8 ) [ 1 8 , 1 4 ) [ 1 4 , 1 2 ) [ 1 2 , 1) [ 1 2 , 3 4 ) [ 3 4 , 1)
[1, ∞) 0 1

Tree Grammar and Cost of Readability

A weighted tree grammar is a tuple G = N , A 0 , F, K, R where N is a finite set of non-terminal symbols, A 0 ∈ N is the initial non-terminal, F and K are as in Section 3.3, and R is a finite set of weighted production rules. Every production rule of R has one of the following forms:

A w -→ f (A 1 , . . . , A n ) where A, A 1 , . . . , A n ∈ N , f ∈ F, and w ∈ Q, A w -→ θ | ε where A ∈ N , θ ∈ K and w ∈ Q.
For each rule ρ of one of the two above kinds, w ∈ Q is called the weight of ρ, denoted by weight(ρ) = w. It is used to compute a value of tree complexity (called cost of readability). With the rules of the second kind, a readability cost value w is associated with every θ ∈ K and non terminal A. Let us extend T (F, K ∪ {ε}) to T (F, K ∪ {ε} ∪ N ), the set of trees whose leaves can be labeled with type names of K or non-terminals of N . A derivation D of G is a sequence of the form:

A 0 ρ1 -→ t 1 ρ2 -→ . . . t k-1 ρ k -→ t k ,
where, for all 0 < i ≤ k, t i-1 , t i ∈ T (F, K ∪ {ε} ∪ N ), ρ i = A i → u i ∈ R, the leftmost innermost occurence of a non-terminal in t i-1 is A i and t i is obtained from t i-1 by replacing this occurence of A i by u i . We also write A 0 D -→ t k and abbreviate D = ρ 1 , . . . , ρ k . The above derivation is called complete if t k ∈ T (F, K ∪ {ε}) (i.e., is contains no more non-terminals).

The weight of D is defined by:

weight(D) = k i=1 weight(ρ i ).
The weight of a tree t ∈ T (F, K) wrt G, also called cost of readability of t is:

cr G (t) = min A0 D -→t weight(D).
The grammar G might be omitted when clear from the context. The purpose of tree grammars is to define a restricted prior language of trees that are an acceptable output of transcription.

Cost of Alignment

We assume that a cost alignment function ca(θ, T, τ, τ prev ) is associated to a token T , a token type θ ∈ K, and two time points τ and τ prev such that τ prev < τ or τ prev =⊥ with a undefined symbol ⊥. This value is a summation of the time shifts induced by aligning all the MIDI events in the token T to the time point τ , if the token type is θ. Here, τ prev is the time value to which the former token of T is aligned. If the type of T is not θ, then ca(θ, T, τ, τ prev ) = +∞. See Appenix A for the concrete defintion of a cost alignment function.

Let us consider a tree t ∈ T (F, K), a time interval I, and the associated sequence of leaves yield (t) = θ 0 , . . . , θ p and sequence of pairs of token and time point tokenize(t, I) = (T 0 , τ 0 ), . . . , (T p , τ p ) . The cost of alignment of E to the tree t and the interval I, denoted by ca E (t, I), is defined as the sum of the ca(θ i , T i , τ i , τ i ) for 0 ≤ i ≤ p where τ i =⊥ if i = 0; otherwise τ i = τ i-1 .

Transcription Objective

The problem of transcription can be defined using the above notions, by minimizing a combination of the two cost measures defined above: the cost of alignment and the cost of readability. More precisely, given an input MIDI sequence E and a grammar G, we call transcription of E wrt G, a tree t ∈ T (F, K) minimizing the measure:

ca E t, [0, +∞) + cr G (t) (1)
We present in Section B an algorithm for solving the problem of computing such a tree.

The trees of Section 3.3 are abstract descriptions of music scores. The elementary score elements (symbols) correspond to the names of token types (notes, rests, chords etc in K) labelling leaves. The MIDI pitch of every note can be extracted from the input MIDI sequence using the definition of tokens in Section 3.4. A pitch-spelling algorithm [START_REF] Meredith | The PS13 pitch spelling algorithm[END_REF] is then necessary to cast these MIDI key values to note names. Moreover, the durations are encoded in t by the symbols of F labeling inner nodes. Additionally to the operations on time intervals, some info about the output score can be attached to the symbols of F. For instance, we can express in a symbol div n whether we want the notes below this symbol to be beamed or not.

Algorithm and Implementation

We designed and implemented an algorithm for the parsing problem defined in Section 4 based on ordinary tabulation technique, where we used the cost alignment function described in Appendix A.

Given in input a MIDI sequence E and a weighted tree grammar, it returns a tree t minimizing (1) in Section 4.3. Figure 8 presents the parsing algorithm designed based on ordinary Dynamic Programming. It assumes that the input midi-sequence E is played with a constant tempo and converted to musical time so that one bar is identical to one second.

The algorithm deals with a set of tabulated items, which is kept by the variable C, as candidates of a parsing result. each item contains 1. a current parse tree t (or a sequence of parse trees), 2. the weight w = ca E (t, I) + cr G (t) of the parse tree t and its allignment cost (or the weight sum of the parse trees and their allignment costs), 3. the set E| snd(I) of unprocessed events in the interval I of the parse tree(s), and 4. the assigned time τ prev of the last token in the parse tree(s).

See appendix B for the detail.

The source code of this implementation is found in URL1 , and produces the command line utilities monopase for parsing monophonic/homophonic input in branch mono2 and drumparse for drums in branch beta. The current implementation recognizes the token type of partial continuation as an ordinary continuation.

Example

In addition to former examples of monophonic2 and drum3 transcription, we present an example of homophonic transcription in Figure 7. It is difficult to say that the result Figure 7(c) is a success, but it gives us valuable hints for future work.

1. There exist unnecessary printed accidentals.

2. The generation of scores in musicXML format has a bug that improperly transforms the continuations of chords. The following notes seem strange: the 2nd note in the 4th bar, the 2nd and 4th note in the 7th bar, and the 2nd note in the last bar.

CONCLUDING REMARKS

We have proposed an approach for the tokenization of MIDI sequences which supports score elements such as rests and ornaments. Implemented as a Dynamic Programming algorithm, it is integrated into a framework of transcription by parsing. The identification of grace-chords, as well as arpeggiated chords, shall be added to the cases of Section 2.4. Another future objective is the processing of polyphonic input, like piano MIDI files. When all voices are mixed into the same MIDI file, the application of a voice separation procedure is required. An important question is then whether voice separation should be performed before, after, or jointly to the parsing described in Section 4. Note that in the first case, voice separation would have to deal with unquantized MIDI input, and with quantized rhythms in the two latter cases.

Figure 1 :

 1 Figure 1: Examples of MIDI tokenizations and transcriptions.

Figure 2 :Figure 3 :

 23 Figure 2: MIDI event sequence for Figure 1. e -1 ∈ T e -1 / ∈ T e ∈ on(T ) grace-note note e ∈ off(T ) goff noff Figure 3: Role of event e in token T .

Example 2 .

 2 The roles of events in the tokens represented in (a) and (b) of Figure1are displayed in Figure4.

Figure 1 Figure 4 :

 14 Figure 1(a) Figure 1(b) event e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 role n n no no gn n n go no no n n no no n n n no no no token T0 T0 T1 T2 T2 T2 T2 T2 T3 T3 T0 T0 T1 T2 T3 T4 T4 T4 T5 T5 Figure 4: Event roles in some tokens of Figure 1.

Figure 5 :

 5 Figure 5: The form of trees

  Tree t 4 for Figure1(d)

Figure 6 :

 6 Figure 6: Rhythm Trees for Figure 1

( a )

 a Score: Sonate für Klavier Nr.11 A dur K.331 Mov.1 (b) The piano-roll of a human piano performance (c) A transcription by our implementation (d) A transcription by Logic

Figure 7 :

 7 Figure 7: A transcription example

  Here, MIDI pitches are presented by note name and octave; D4 = 62, E4 = 64, A4 = 69, and B 4 = 70.

		e1	e2	e3	e4	e5	e6	e7	e8	e9	e10
	ts	0.03 0.05 0.15 0.38 0.44 0.50 0.53 0.57 0.70 0.77
	flag	on	on	off	off	on	on	on	off	off	off
	pitch	D4	A4	D4	A4	E4	B 4	D4	E4	B 4	D4
	vel	110	100	0	0	45	90	110	0	0	0

https://gitlab.inria.fr/qparse/qparselib

https://qparse.gitlabpages.inria.fr/docs/examples

https://gitlab.inria.fr/transcription/gmdscores

Acknowledgments

This research was supported by JSPS Kaken 20H04302.

Example 4. In Figure 6, the time intervals associated with each node of trees are represented in red. They are computed from the interval assigned to the root node by recursive application of the operators labeling the nodes.

Formally, the interval assignment is defined as follows, where itv (t, I) is the sequence of the intervals labelling the leaves of t. itv div n (t 1 , . . . , t n ), I = itv (t 1 , div n (I, 1)) . . .

It can be observed that, when it is defined, itv (t, I) forms a partition of I. It is always defined when I = [τ 0 , +∞) and t has the form of a right combination. The sequence of time points induced by the partition itv (t, I) is called the grid of t of carrier I, denoted by grid (t, I). Formally, if itv (t, I) is a partition of the form [τ 0 , τ 1 ), [τ 1 , τ 2 ), . . . , [τ k-1 , τ k ) with τ 0 = start(I) and τ k = end (I), for some k ≥ 0 (τ k might be +∞), then:

To every time point τ i in the grid, we can associate a set T i of events in E containing the MIDI events closer to τ i than to its neighbours τ i-1 and τ i+1 in the grid. For a formal definition, we introduce a notation cp(τ 1 , τ 2 ) to the present center point of τ 1 and τ 2 :

Based on grid (t, I) and the above sequence T 0 , . . . , T k-1 , we define

where

In the sequel, we use a renumbered tokenized sequence as tokenize(t, I) = (T 0 , τ 0 ), . . . , (T p , τ p ) .

Example 5. For the trees of Figure 6 it holds that:

where T 0 , T 1 , . . . are the displayed tokens from left to right in the corresponding figures.

TREE LANGUAGES, PARSING AND M2S-TRANSCRIPTION

In this section, we propose to use weighted tree grammar in order to define languages of trees of Section 3.3. Then we reduce M2S-AMT into the problem of parsing an input MIDI sequence wrt such a grammar.

A. COST ALIGHNMENT FUNCTION

Let E be an input MIDI sequence. For a token type θ ∈ K and a token T of E, let θ(T ) be defined by: θ(T ) = 1 if T has type θ and θ is valid in the case of input considered (see Section 2.5), θ(T ) = +∞ otherwise, The cost alignment function used in the implementation is as follows:

where ∆(τ prev , τ ) = τ -τ prev if τ prev =⊥; otherwise a fixed constant value. σ is the sign of ts(e), τ and α + and α -associate appropriate constants to the role r(e, T ) of e in T . Typically, α offL > α offR because note-off often occurs earlier than expected.

Input: Midi-sequence E, tree grammar G = N , A0, F, K, R .

Output: The tree t obtained from (t, w) := parse([0, ∞), ∅, ⊥).

Functions:

fst(I) (resp. snd (I)) denotes div 2(I , 1) (resp. div 2(I , 2)). E|I = {e ∈ E | ts(e) ∈ I)} is the subsequence of events in an interval I.

parse(I, F, τ ): For

For i = 1, . . . , k, do

Ci := min t1, . . . , ti-1 , wi-1, Fi-1, τi-1 ∈ Ci-1 ti, wi, Fi, τi ∈ parseRec(div k (I, i), Ai, Fi-1, τi-1) t1, . . . , ti , wi-1 + wi, Fi, τi

The set of S, w, F, τ ∈ C having minimum w for each F, τ . parse: Assuming the following arguments:

• an interval I of midi-sequence E to be parsed,

• a set F of events in prior to start(I), and • the time point τ aligned the last parsed token before start(I), it returns a pair of the best weighted tree t and its weight w for midi-sequence F ∪ E with alligning all events in F to start(I).

parseRec: calculates possible best trees within one bar. Assuming the following arguments:

• an interval I of midi-sequence E to be parsed,

• a non-terminal symbol A of the grammar,

• a set F of events in prior to start(I), and

• the time point τ aligned the last parsed token.

it returns a set of tuples t, w, F , τ consisting of the tree t with weight w and root nonterminal symbol A for each possble pair of F and τ determined in the calculation.


Edouard Pauwels

Fréchet Generic

Stationarity

Generic Fréchet stationarity in constrained optimization

Keywords: Constrained optimization, nonconvex optimization, optimality conditions, stationarity, semi-algebraic optimization, genericity, projected gradient algorithm

Introduction

We consider the problem

min x∈C f (x) (1)
where f : R p → R is C 1 and C ⊂ R p is closed. A point x ∈ C is called Fréchet stationary for f on C if f (y) -f (x) ≥ o(∥y -x∥) for y ∈ C and a vector v is called a regular normal vector to C at x whenever x is Fréchet stationary for the linear form x → -⟨v, x⟩ on C. The notion of regular normal vector lacks basic continuity properties, and in particular limits of regular normals may not correspond to regular normals. The broader notion of criticality aims at recovering a form of continuity, see Section 2.1. But the price is the variational meaning of Fréchet stationarity which may be lost due to lack of regularity (see Example 1). The purpose of this work is to formaly show that despite the widespread use of the notion of criticality in non convex optimization, the vast majority of cases encountered relate to the stronger notion Fréchet stationarity, aligning formal guaranties with practical observations.

We first show that if f and C are assumed to be semi-algebraic, then considering the functions {f v : x → f (x)+⟨v, x⟩}, generically in v, all critical points of f v on C are Fréchet stationary. This result illustrates the fact that the existence of critical points which are not Fréchet stationary is the consequence of a bad alignment of the objective function f and the constraint set C, which

The consequences of lack of regularity on optimality conditions, and optimality measures, was further studied in [START_REF] Levin | Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy[END_REF] for low rank matrices under the name "apocalypses" with a very similar flavor as [START_REF] Beck | Sparsity constrained nonlinear optimization: Optimality conditions and algorithms[END_REF] for sparsity constraints. This constitutes further motivations to develop algorithmic schemes for low rank matrix optimization which avoid this pathology and are attracted by stationary points in [START_REF] Levin | Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy[END_REF] followed by [START_REF] Hou | Asymptotic escape of spurious critical points on the low-rank matrix manifold[END_REF][START_REF] Olikier | An apocalypse-free first-order lowrank optimization algorithm[END_REF][START_REF] Olikier | An apocalypse-free first-order low-rank optimization algorithm with at most one rank reduction attempt per iteration[END_REF][START_REF] Olikier | First-order optimization on stratified sets[END_REF]. As mentioned in [START_REF] Olikier | Gauss-southwell type descent methods for low-rank matrix optimization[END_REF], the absence of regularity only has rare consequences in practice and our main motivation is to provide formal guaranties for this observation in the form of genericity results on problem data and convergence guaranties for the projected gradient algorithm.

Genericity in tame optimization: Our first main result, Theorem 1, relates to semialgebraicity or tameness of the considered objective function f and the constraint set C. Studying nonconvex optimization and first order methods under such rigidity assumptions have a long history in optimization. Indeed, semi-algebraicity has numerous structural consequences on the optimization losses [START_REF] Bolte | The lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF][START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF][START_REF] Bolte | Tame functions are semismooth[END_REF][START_REF] Ioffe | An invitation to tame optimization[END_REF]. Furthermore, virtually all losses met in an optimization context are covered by tameness assumptions, see the numerous examples in [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the kurdyka-lojasiewicz inequality[END_REF][START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF], and the connection with deep learning in [START_REF] Bolte | A mathematical model for automatic differentiation in machine learning[END_REF][START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning[END_REF]. One can take advantage of these properties, for which semi-algebraicity is a mild sufficient condition, to analyse optimization algorithms and optimization landscapes. Examples include sequential convergence of deterministic optimization algorithms [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF][START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the kurdyka-lojasiewicz inequality[END_REF][START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF][START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF][START_REF] Bolte | Majorization-minimization procedures and convergence of sqp methods for semi-algebraic and tame programs[END_REF][START_REF] Pauwels | The value function approach to convergence analysis in composite optimization[END_REF], as well as the analysis of stochastic first order methods [START_REF] Davis | Stochastic subgradient method converges on tame functions[END_REF][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] Bolte | A mathematical model for automatic differentiation in machine learning[END_REF][START_REF] Bolte | Nonsmooth automatic differentiation: a cheap gradient principle and other complexity results[END_REF].

Genericity is a notion that is used to express the fact that a certain behavior is typical. It is most often expressed in measure theoretic terms (Lebesgue almost everywhere), or topological terms (residual sets are countable intersections of sets with dense interior). In general, the two notions do not coincide (see for example [START_REF] Oxtoby | Measure and category[END_REF]Theorem 1.6]), but in the semi-algebraic setting they coincide and sometimes correspond to a stronger notion: being the complement of the union of finitely many lower dimensional embedded smooth manifolds. This is essentially due to the stratification property [53, 4.8]. Genericity results in an optimization context relate to the typical structure of the data of optimization problems [START_REF] Daniilidis | Generic identifiability and second-order sufficiency in tame convex optimization[END_REF][START_REF] Bolte | Generic optimality conditions for semialgebraic convex programs[END_REF][START_REF] Daniilidis | Continuity and differentiability of set-valued maps revisited in the light of tame geometry[END_REF][START_REF] Pham | Genericity in polynomial optimization[END_REF][START_REF] Drusvyatskiy | Generic minimizing behavior in semialgebraic optimization[END_REF][START_REF] Bolte | Qualification conditions in semi-algebraic programming[END_REF][START_REF] Lee | Generic properties for semialgebraic programs[END_REF] and generic desirable properties of optimization methods [START_REF] Nie | Optimality conditions and finite convergence of lasserre's hierarchy[END_REF][START_REF] Bianchi | Stochastic subgradient descent escapes active strict saddles on weakly convex functions[END_REF][START_REF] Davis | Proximal methods avoid active strict saddles of weakly convex functions[END_REF][START_REF] Davis | A nearly linearly convergent first-order method for nonsmooth functions with quadratic growth[END_REF]. Our first main result falls in this category, we show that for a generic semi-algebraic f and a fixed semi-algebraic set C, there is no critical point which is not Fréchet stationary for the resulting constrained minimization problem. A consequence of this result is that for a generic smooth semi-algebraic function f and a fixed closed set C, the "apocalypses" described in [START_REF] Levin | Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy[END_REF] do not exist.

Projected gradient algorithm: Our second main result, Theorem 2, concerns the projected gradient algorithm proposed independently by Glodstein [START_REF] Goldstein | Convex programming in hilbert space[END_REF] and Levitin Polyak [START_REF] Levitin | Constrained minimization methods[END_REF] for convex optimization with subsequent contributions in the convex setting [START_REF] Bertsekas | On the goldstein-levitin-polyak gradient projection method[END_REF][START_REF] Calamai | Projected gradient methods for linearly constrained problems[END_REF][START_REF] Dunn | Global and asymptotic convergence rate estimates for a class of projected gradient processes[END_REF][START_REF] Dunn | On the convergence of projected gradient processes to singular critical points[END_REF]. Our analysis is a consequence of a detailed analysis of the proximal gradient algorithm, the proximal mapping generalizing the projection. Convergence of the proximal point algorithms in a non-convex setting was considered in [START_REF] Spingarn | Submonotone mappings and the proximal point algorithm[END_REF][START_REF] Kaplan | Proximal point methods and nonconvex optimization[END_REF][START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF], convergence of the proximal gradient algorithms under semi-algebraic assumptions was given in [START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF]. In the nonconvex setting, existing convergence guaranties are related to a notion of criticallity, weaker than Fréchet stationarity and we show that the analysis can be extended to obtain a quantitative version of Fréchet stationarity. This can be seen as an extension of the L-stationarity result obtained in [START_REF] Beck | Sparsity constrained nonlinear optimization: Optimality conditions and algorithms[END_REF] for the projected gradient algorithm under sparsity constraints to general sets, and constitutes an element of answer regarding the convergence guaranties of the projected gradient algorithm related to the concerns raised in [START_REF] Levin | Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy[END_REF].

Notations

Throughout the paper, the ambiant space is R p . We denote by ⟨•, •⟩ and ∥ • ∥, the Euclidean scalar product and Euclidean norm. We denote a set valued map F , from R p to subsets of R p with the notation F : R p ⇒ R p . For a subset C ⊂ R p , we denote by T C , NC , N C the tangent, regular normal and normal cones respectively which are seen as set valued maps R p ⇒ R p with empty values outside C. Relevant definitions are introduced along the paper.

Main results

We introduce the required elements of variational geometry in Section 2.1 and state our two main results in Section 2.2 and Section 2.3.

Notions of stationarity

We use the notations and denominations of [START_REF] Rockafellar | Variational analysis[END_REF]. First recall the definitions of the objects of interest.

Definition 1 (Tangent and Normal Cones). For x ∈ C, w ∈ R p is an element of the tangent cone of C at x, written w ∈ T C (x) if

x k -x τ k → w for some sequence (x k ) k∈N ,
∈ N C (x) if ∃(x k ) k∈N , (v k ) k∈N , x k ∈ C, v k ∈ NC (x k ), k ∈ N, x k → x, v k → w, k → ∞.
T C , NC and N C can be seen as set valued maps R p ⇒ R p by assigning empty values for x ̸ ∈ C.

We gather known facts about these cones, the following is taken from Theorem 6.21 and 6.28 [START_REF] Rockafellar | Variational analysis[END_REF].

Proposition 1. Let C ⊂ R p be closed, then for all x ∈ C, T C (x) is a closed cone and NC (x) is the polar of T C (x): NC (x) = {v ∈ R p , ⟨v, w⟩ ≤ 0, ∀w ∈ T C (x)}.
Let f : R p → R be C 1 . Suppose that x ∈ C is a local minimum of f restricted to C, then the two equivalent conditions hold:

-∇f (x) ∈ NC (x) proj T C (x) (-∇f (x)) = 0.
(2)

A point x ∈ C which satisfy (2) is called Fréchet stationary for f on C, in which case, f (y) -f (x) ≥ o(∥y -x∥). (3)
This implies the stronger condition -∇f (x) ∈ N C (x), an x ∈ C satisfying this condition is called critical for f on C.

Proposition 1 suggests to use (2) as an optimality condition for constrained optimization, however the proposed quantity lacks basic continuity in general, which is troublesome for many applications. This motivates the introduction of the normal cone to C, N C which is the graph closure of the regular normal cone to C, recovering some form of continuity and the possibility to pass to limits. Typical optimization results fall in this scope and provide guaranties in terms of criticality, -∇f (x) ∈ N C (x), in the context of (1) which is necessary but not sufficient for [START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the kurdyka-lojasiewicz inequality[END_REF]. While this constitutes a bona fide optimality condition, in the sense that if it is not satisfied, x is not a local extremum, it may result in meaningless notion of criticality contrary to the interpretation of Fréchet stationarity in [START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF].

Example 1. Let C ⊂ R 2 be the set of 1-sparse vector, then N C (0, 0) = T C (0, 0) = C while NC (0, 0) = {0}. Set f : (x, y) → (x -1) 2 + y 2 , then (0, 0
) is critical for f on C but this does not have much variational meaning since f has directional derivative 2 in the y direction which is in T C (0, 0) and is actually admissible with respect to the constraint induced by C.

To ellaborate on this remark and illustrate the relevance of the normal cone in comparison to the regular normal cone, we quote Rockafellar and Wets [START_REF] Rockafellar | Variational analysis[END_REF] regarding the phenomenon presented in Example 1:

This possibility causes some linguistic discomfort over 'normality', but the cone of such limiting normal vectors comes to dominate technically in formulas and proofs, [. . .] Many key results would fail if we tried to make do with regular normal vectors alone.

This absence of regularity is related to the main motivations in [START_REF] Levin | Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy[END_REF] to propose algorithms which do not suffer from it.

Genericity of Fréchet stationarity

We start by introducing the necessary tools from semi-algebraic geometry. An introduction to semi-algerbaic and tame geometry is found in [START_REF] Coste | Istituti editoriali e poligrafici internazionali Pisa[END_REF][START_REF] Coste | An introduction to semialgebraic geometry[END_REF] and a comprehensive overview is given in [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF], see also [START_REF] Van Den Dries | Tame topology and o-minimal structures[END_REF]. We recall all the required concepts with necessary bibliographic pointers.

Semi-algebraic geometry

Let us first introduce the required definitions.

Definition 2. Let p, q ∈ N be arbitrary.

A basic semi-algebraic set S ⊂ R p is the solution set of a polynomial system of inequalities.

S = {x ∈ R p , P (x) = 0, Q 1 (x) > 0, . . . Q m (x) > 0} (4)
where P, Q 1 , . . . , Q m are polynomials of p variables and m ∈ N.

A semi-algebraic set is the finite union of basic semi-algebraic sets.

A function

f : R p → R q is semi-algebraic if its graph {(x, z) ∈ R p+q , z = f (x)} is semi-algebraic. A set-valued map F : R p ⇒ R q is semi-algebraic if its graph {(x, z) ∈ R p+q , z ∈ F (x)} is semi-algebraic.
Example 2 (semi-algebraic functions). Euclidean norm, square root, quotients, rational powers, matrix rank are semi-algebraic functions. Semi-algebraic functions are closed under composition.

Semi-algebraic objects are closed under many relevant operations: intersection, unions, complementation and Cartesian product [START_REF] Coste | Istituti editoriali e poligrafici internazionali Pisa[END_REF]. The Tarski-Seidenberg principle [21, Theorem 2.3] allows to characterize semi-algebraic sets as the smallest o-minimal structure [20, Exercise 1.17]. Therefore the general tools of o-minimal geometry apply to the semi-algebraic setting. Furthermore, many results for semi-algebraic sets naturaly extend to the o-minimal setting. In this spirit, we gather below properties which will be useful in order to prove our genericity result.

Proposition 2. Let p, m ∈ N be arbitrary and C ⊂ R p and F : R p ⇒ R m be semi-algebraic.

1. The projection of C onto a subspace is semi-algebraic . 4. If F is a differentiable function (single valued), then its Jacobian is a semi-algebraic function.

5. The image of C by F , F (C) ⊂ R m is semi-algebraic.

6. C can be partitioned into a finite union of disjoint semi-algebraic smooth embedded submanifolds .

Proof of Proposition 2: These are well known and can be found in [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF][START_REF] Coste | An introduction to semialgebraic geometry[END_REF][START_REF] Coste | Istituti editoriali e poligrafici internazionali Pisa[END_REF], we provide proof arguments and detailed pointers for completeness.

1. This is Tarski-Seidenberg Theorem, up to a rotation, see [START_REF] Coste | An introduction to semialgebraic geometry[END_REF]Theorem 2.3]. An equivalent formulation of this result is [START_REF] Coste | An introduction to semialgebraic geometry[END_REF]Theorem 2.6] states that every first order formula (quantification on variables), involving semi-algebraic sets or functions, polynomials, inequalities, equalities and the logical negation, conjunction and disjunction, describes a semi-algebraic object. In the following, we describe each set of interest with such a first order formula, which implies that they are semi-algebraic (see [21, Section 2.1.2] and [20, Theorem 1.13]).

2.

z ∈ T C (x) ⇔ ∀ϵ > 0, ∃y ∈ C, y ̸ = x, ∥y -x∥ ≤ ϵ, y -x ∥y -x∥ - z ∥z∥ ≤ ϵ z ∈ NC (x) ⇔ ∀w ∈ T C (x), ⟨z, w⟩ ≤ 0 z ∈ N C (x) ⇔ ∀ϵ > 0, ∃y ∈ C, ∃v ∈ NC (y), ∥x -y∥ ≤ ϵ, ∥v -z∥ ≤ ϵ.
3.

x ∈ int C ⇔ ∃ϵ > 0, ∀y ∈ R p , ∥x -y∥ > ϵ or y ∈ C x ∈ cl C ⇔ ∀ϵ > 0, ∃y ∈ C, ∥y -x∥ ≤ ϵ.
4.

M = J F (x) ⇔ M ∈ R m×p , ∀ϵ > 0, ∃δ > 0, ∀y ̸ = x, ∥y -x∥ > δ or ∥F (y) -F (x) -M (y -x)∥ ∥y -x∥ ≤ ϵ 5. z ∈ F (C) ⇔ ∃x ∈ C, z ∈ F (x).
6. This is the geometric notion of stratification, see for example in [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]Claim 4.8].

□

Semi-algebraic sets come with a notion of integral dimension, denoted by dim C for a semialgebraic set C, which agrees with the classical notion of dimension for affine sets or embedded manifolds. The following facts can be found in [20, Proposition 3.17, Theorem 3.22] and will be useful to prove our genericity result.

Proposition 3. Let p, m ∈ N be arbitrary.

1. If B ⊂ A ⊂ R p are semi-algebraic, then dimB ≤ dimA. 2. If A, B ⊂ R p are semi-algebraic, then dim A ∪ B = max{dim A, dim B}.

For any

A ⊂ R p semi-algebraic, dim cl A = dim A, dim cl A \ A < dim A.
4. For f : R p → R m and A ⊂ R p , both semi-algebraic, dim f (A) ≤ dim A.

Main result

The following is our first main result. It is stated in the semi-algebraic setting, but it can be extended to functions and sets which are definable in the same o-minimal structure as the arguments rely on the elements described in Proposition 2 and Proposition 3 which hold for definable functions and sets [START_REF] Coste | Istituti editoriali e poligrafici internazionali Pisa[END_REF][START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF].

Theorem 1. Let f : R p → R be continuously differentiable and C ⊂ R p be closed, both semialgebraic. Then there is V ⊂ R p , which is a finite union of semi-algebraic embedded manifolds of dimension at most p -1, such that for all v ̸ ∈ V , all critical point of f v : x → f (x) + ⟨v, x⟩ on C are Fréchet stationary.

Proof of Theorem 1: By Proposition 2 item 2, NC and N C are semi-algebraic.

We work with NC : C ⇒ R p . It follows from Definition 1 that for any S ⊂ C, we have for all x ∈ S, NC (x) ⊂ NS (x). We may consider a partition of C into M 1 , . . . , M m embedded smooth manifolds by Proposition 2 item 6. For each i = 1, . . . , m, we have M i ⊂ C and therefore NC (x) ⊂ NM i (x). But NM i (x) is simply the normal space of M i at x as described by differential geometry. Therefore the graph of NC restricted to M i is contained in the normal bundle of M i which can be seen as an embedded submanifold of R 2p of dimension p, see for example [START_REF] Lee | Introduction to Smooth Manifolds[END_REF]Theorem 6.23]. Therefore, the graph of the restriction of NC to M i is of dimension at most p by Proposition 3 item 1. The graph of NC is the union of its restriction to M i , i = 1, . . . , m and it is therefore of dimension at most p by Proposition 3 item 2.

Set G the closure of graph NC in R 2p , it is semi-algebraic by Proposition 2 item 3. We have that (x, z) ∈ G if and only if there is a sequence

x k → x and z k → z such that z k ∈ NC (x k )
v ∈ R p ∃x ∈ C, -∇f (x) -v ∈ N C (x) \ NC (x) ⇔ ∃x ∈ C, v ∈ R(x) so that v ∈ R p , ∃x ∈ C, -∇f (x) -v ∈ N C (x) \ NC (x) = proj v graph R.
where proj v (x, z) = z for any x, z ∈ R p . Setting V = proj v graph R, we have that dimV ≤ p -1 by Proposition 3 item 4. By Proposition 2 item 6, V is a finite union of semi-algebraic embedded submanifolds of dimension p -1 at most by Proposition 3 item 2. □ Remark 1. The result of Theorem 1 holds generically in v, as understood in both measure theoretic terms (almost everywhere), or topological terms (residual). We perturb f using a linear form, but one could consider a peturbation of the form x → ϵ∥x -c∥ 2 for small ϵ > 0, and the same result would hold generically in c ∈ R p . It is easy to see that the critical point example in Example 1 would not persist under generic perturbation and Theorem 1 provides a general ground for this observation.

Projected gradient is attracted by Fréchet stationary points

Given a non-empty closed set C ⊂ R p , the projection of x ∈ R p on C, denoted by proj C (x) is given by the non-empty set proj C (x) = arg min z∈C ∥x -z∥.

Given an initial point x 0 ∈ C and a step-size parameter, γ > 0, the projected gradient algorithm iterates.

x k+1 ∈ proj C (x k -γ∇f (x k )). ( 5
)
The following is our second main result. It is a consequence of the analysis of the proximal gradient algorithm proposed in Section 3.2

Theorem 2. Let f : R p → R be C 1 with L-Lipschitz gradient and C ⊂ R p be non-empty and closed. Then for any step size γ < 1/L, any accumulation point of the projected gradient algorithm, x, is Fréchet stationary such that

f (y) ≥ f (x) - 1 γ ∥y -x∥ 2 , ∀y ∈ C, (6) proj
C (x -s∇f (x)) = {x}, ∀0 < s < γ. Furthermore proj T C (x k ) (-∇f (x k )) → 0 as k → ∞.
Proof : From [50, Exercise 8.14]: ∂δ C (x) = NC (x), where δ C is the indicator function of C with value 0 on C an +∞ outside. Note that δ C satisfies the hypotheses of Lemma 3 for any δ > 0.

We have for any that f = γf has Lγ < 1 Lipschitz gradient and the proximal gradient algorithm with unit step on f and g = δ C in ( 7) is equivalent to the projected gradient algorithm on f with step size γ so that Theorem 4 applies. We obtain that all accumulation points x are Fréchet stationary such that x ∈ proj C (x -γ∇f (x)) from Theorem 4, which means that dist(x -γ∇f (x)) = γ∥∇f (x)∥. The quantitative statement on Fréchet stationarity follows from Theorem 4 applied to f = γf .

Let us prove unicity of the projection fix 0 < s < γ. The case ∇f (x) = 0 is obvious so let us eliminate it. Denote by B 1 the ball of center x -γ∇f (x) and radius γ∥∇f (x)∥ and B 2 the ball of center x -s∇f (x) and radius s∥∇f (x)∥. Let us show that for any x ∈ B 2 , x ̸ = x, we have

∥x -x + γ∇f (x)∥ = ∥x -x + s∇f (x) + (γ -s)∇f (x)∥ < s∥∇f (x)∥ + (γ -s)∥∇f (x)∥ = γ∥∇f (x)∥
where the strict inequality is from the triangle inequality. Indeed, either the triangle inequality is strict, or x-x+s∇f (x) = α(γ -s)∇f (x) for some α ≥ 0. In this second case, since x ∈ B 2 , by taking the norm, we obtain s ≥ α(γ -s), so that x = x -t∇f (x) where t = s -α(γ -s) ≥ 0 and t ≤ s. The case t = 0 is excluded because we assumed that x ̸ = x and we have 0 < t ≤ s < γ, so that

∥x -x + γ∇f (x)∥ = ∥(γ -t)∇f (x)∥ = |γ -t| ∥∇f (x)∥ < γ∥∇f (x)∥
We have shown that any x ∈ B 2 different from x is actually in intB 1 and therefore at positive distance from C, otherwise this would contradict dist(x -γ∇f (x)) = ∥∇f (x)∥. Since x ∈ C, it is the unique element in B 2 ∩ C which proves unicity of the projection.

We conclude regarding the last statement proj T C (x k ) (-∇f (x k )) → 0 by combining the fact that dist( NC (x k ), -∇f (x k )) → 0 from Theorem 4 and Lemma 1. □ Lemma 1. Let T ⊂ R p be a closed cone, not necessarily convex and N be its polar, N = {v ∈ R p , ⟨w, v⟩ ≤ 0, ∀w ∈ T }, then for any x ∈ R p , ∥proj T (x)∥ ≤ dist(x, N ).

Proof : Set z = proj T (x), if ∥z∥ = 0, then there is nothing to prove. Assume that ∥z∥ > 0. Set T = {λz, λ ≥ 0} and Ñ its polar, we have

T ⊂ T, Ñ ⊃ N, proj T (x) = z.
Both Ñ and T are convex cones and by Moreau's identity [START_REF] Moreau | Proximité et dualité dans un espace hilbertien[END_REF]Section 4.b], we have x = proj T (x) + proj Ñ (x) so that

∥proj T (x)∥ = ∥x -proj Ñ (x)∥ = dist(x, Ñ ) ≤ dist(x, N ).
□ Remark 2 (Comments on Theorem 2). It was identified in [START_REF] Beck | Sparsity constrained nonlinear optimization: Optimality conditions and algorithms[END_REF] that for sparsity constraints, local minimizers need to be fixed point of the projected gradient algorithm (a condition termed L stationarity) and the projection has to be univalued. Theorem 2 shows that for general sets, the projected gradient algorithm will be attracted by such points, generalizing the result of [START_REF] Beck | Sparsity constrained nonlinear optimization: Optimality conditions and algorithms[END_REF] for the Iterative Hard Thresholding algorithm, as illustrated in Figure 1. This result is related to the notion of proximal normals [50, Exemple 6.16], the sequences are actually attracted by the set of points x ∈ C such that -∇f (x) is a proximal normal of C at x. The last assertion in Theorem 2 ensures that the so called "serendipity" phenomenon described in [37, Definition 2.8] does not affect the projected gradient algorithm. If we assume in addition that f and C are semi-algebraic, then the sequence actually converges, as shown in [START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF]. Finally if f is convex one can add a factor 1 2 in front of the quadratic term in (6).

Numerical illustration

We illustrate the relevance of the result of Theorem 2, first with the avoidance of a critical point which is not Fréchet stationary as in Example 1, and second with the avoidance of bad local minima on a grid. These are illustrative toy examples, and in both cases the observed behavior could be justified with elementary dedicated arguments. Exploring consequences of Theorem 2 in practical application will be a matter of future research.

Sparsity constraints

We consider as in Example 1 the set C of 1-sparse vectors in R 2 and a loss function is f : (x, y) → (x -1) 2 + y 2 whose global minimum on the constraint set is x = 1, y = 0. We depict in Figure 1 the sequence generated by the projected gradient algorithm in (5) for various step sizes and initializations, representing both the gradient and the projection steps explicitly. The point (0, 0) is critical but not Fréchet stationary, none of the three sequences converges to this point. Instead, they all converge to the global minimum, illustrating the result of Theorem 2.

Nonlinear optimization on a grid We consider the problem of minimizing a convex quadratic function, where the constraint set is a regular grid in R 2 . In this setting, all feasible points are local minimizers, hence Fréchet critical. Yet Theorem 2 predicts that not all of them are attractors of the projected gradient algorithm. We illustrate this with several projected gradient sequences in Figure 1 displaying explicitely the points which do not satisfy the quantitative estimate (5) (with factor 1 2 for convex functions, see Remark 2). The sequences stop when they reach these stationary points as predicted by Theorem 2. 6) (with an additional factor 1 2 from Remark 2). We display several projected gradient sequences which all stop at the points satisfying these estimates.

The proximal gradient algorithm

In this section we provide a general result for the proximal gradient algorithm, from which Theorem 2 follows. We first recall the necessary notations and concepts. This section can be seen of independent interest.

Technical results from nonmooth analysis

The following extends the notion of gradient in a natural way.

Definition 3 (Regular subdifferential). Let f : R p → R ∪ {+∞} and consider x ∈ R p such that f (x) < +∞. Then v ∈ ∂f (x) if f (y) ≥ f (x) + ⟨v, y -x⟩ + o(∥y -x∥).
This notation means that lim inf y→x f (y)-f (x)-⟨v,y-x⟩ ∥y-x∥ ≥ 0.

We obtain an optimality condition as a consequence of the definition in [START_REF] Rockafellar | Variational analysis[END_REF]Theorem 10.1].

Theorem 3 (Fermat Rule). If x ∈ R p is a local minimizer of a lower semicontinuous function f : R p → R ∪ {+∞}, then 0 ∈ ∂f (x).

Conversely, a point x ∈ R p with f (x) finite satisfying 0 ∈ ∂f (x) has non-negative first order variations around x, in the sense that f (y) -f (x) ≥ o(∥y -x∥). Such a point is called Fréchet critical. While calculus is in general out of scope for this type of object, it is possible to obtain sum rules when combined with a C 1 function.

Lemma 2 (Smooth sum rule). Let g : R p → R ∪ {+∞} be lower semicontinuous and consider x ∈ R p such that g(x) < +∞. Let f : R p → R be C 1 , then ∂(f + g)(x) = ∂g(x) + ∇f (x).

Proof : From [50, Corollary 10.9] we have ∂(f +g)(x) ⊃ ∂g(x)+∇f (x). Let us prove the reverse inclusion. Choose v ∈ ∂(f + g)(x), we have by Definition 3 and continuous differentiability.

lim inf y→x f (y) + g(y) -f (x) -g(x) -⟨v, y -x⟩ ∥y -x∥ ≥ 0 lim y→x f (y) -f (x) -⟨∇f (x), y -x⟩ ∥y -x∥ = 0.
We deduce by a substraction that lim inf y→x g(y) -g(x) -⟨v -∇f (x), y -x⟩ ∥y -x∥ ≥ 0, which shows that v -∇f (x) ∈ ∂g(x) which is the desired result. □

The proximal gradient algorithm and Fréchet stationarity

Given a lower-semi continuous function g : R p → R ∪ {+∞}, the proximity operator of g is defined as the possibly empty valued mapping

prox g (x) = arg min y∈R p g(y) + 1 2 ∥y -x∥ 2 .
The following Lemma provides a sufficient condition for prox g to be well behaved. This is [50, Theorem 1.25], we provide a short proof for completeness.

Lemma 3. Let g : R p → R ∪ {+∞} be lower semicontinuous, finite at least at one point, such that g + 1+δ 2 ∥ • ∥ 2 is bounded below for some δ > 0. Then prox g : R p ⇒ R p has non-empty values, is locally bounded and upper semi-continuous, in the sense that for any converging sequences y k ∈ prox g (x k ), k ∈ N, x k → x, y k → y, we have y ∈ prox g (x).

Proof : By assumption, there is no escape at infinity, the prox operation is compact valued and locally bounded. Let (x k ) k∈N and (y k ) k∈N be sequences such that y k ∈ prox g (x k ) for all k ∈ N, and x k → x, y k → y as k → ∞. For any z ∈ R p , and any k ∈ N, we have

g(z) + 1 2 ∥z -x k ∥ 2 ≥ g(y k ) + 1 2 ∥y k -x k ∥ 2 .
Hence for any z ∈ R p , we have by lower semi-continuity

g(z) + 1 2 ∥z -x k ∥ 2 ≥ lim inf k→∞ g(y k ) + 1 2 ∥y k -x k ∥ 2 ≥ g(y) + 1 2 ∥y -x∥ 2
which is what we wanted to prove. □

We now state the main result of this section.

Theorem 4. Let f : R p → R be C 1 with 1 -δ Lipschitz gradient for some δ ∈ (0, 1) and g be as in Lemma 3. Fix x 0 ∈ R p ; and consider the recursion

x k+1 = prox g (x k -∇f (x k )). (7)
Any accumulation point x of (x k ) k∈N are Fréchet critical for f + g such that

x ∈ prox g (x -∇f (x)) ( 8)

f (y) + g(y) ≥ f (x) + g(x) -∥y -x∥ 2 , ∀y ∈ R p .
Furthermore, dist(-∇f (x k+1 ), ∂g(x k+1 )) → 0 as k → ∞.

Proof : One can check that x k+1 ∈ arg min y f (x k ) + ⟨∇f (x k ), y -x k ⟩ + 1 2 ∥y -x k ∥ 2 + g(y) by completing the square.

Combining with the descent lemma for Lipschitz gradient functions[41, Lemma 1.2.3], we have

f (x k ) + g(x k ) ≥ f (x k ) + ⟨∇f (x k ), x k+1 -x k ⟩ + 1 2 ∥x k+1 -x k ∥ 2 + g(x k+1 ) = f (x k ) + ⟨∇f (x k ), x k+1 -x k ⟩ + 1 -δ 2 ∥x k+1 -x k ∥ 2 + g(x k+1 ) + δ 2 ∥x k+1 -x k ∥ 2 ≥ f (x k+1 ) + g(x k+1 ) + δ 2 ∥x k+1 -x k ∥ 2 .
Now suppose that the sequence (x k ) k∈N has an accumulation point x. In this case f (x k ) + g(x k ) is decreasing, and it converges to a finite value. Therefore the increments x k+1 -x k tend to 0 and prox g (x k -∇f (x k )) also tends to x. Using Lemma 3, we have that x ∈ prox g (x -∇f (x)) so that, using Fermat rule in Theorem 3 and Lemma 2

x ∈ arg min For the last point, using Fermat rule in Theorem 3 for the prox operator leads to

x k+1 -x k + ∇f (x k ) = x k+1 -x k + ∇f (x k ) -∇f (x k+1 ) + ∇f (x k+1 ) ∈ -∂g(x k+1 ) so that dist(-∇f (x k+1 ), ∂g(x k+1 )) ≤ ∥x k+1 -x k ∥ + ∥∇f (x k ) -∇f (x k+1 )∥ → k→∞ 0, which is the second result. □ Remark 3 (Comments on Theorem 4). If in addition, the function f and the set C are assumed to be semi-algebraic, then the sequence actually converges [START_REF] Attouch | Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized gauss-seidel methods[END_REF]. The quadratic lower bound provides a quantitative estimate of Fréchet stationarity. Furthermore, if f is convex, then one can add a factor 1 2 in front of the quadratic term in (8), since the inequality (10) can be tightened.

Conclusion

Our main results in Theorem 1 and Theorem 2 ensure that the lack of Clarke regularity has minimal effect on the optimality conditions in nonconvex constrained optimization, and that it does not affect the projected gradient algorithm. A by product of the analysis is a global quantitative estimate for Fréchet stationarity of accumulation points of the projected gradient algorithm with a strong variational interpretation and a natural connection to the convex setting where the negative quadratic term vanishes. This generalizes the analysis of Iterative Hard Thresholding in [START_REF] Beck | Sparsity constrained nonlinear optimization: Optimality conditions and algorithms[END_REF] and illustrates the fact that the projected gradient algorithms constitutes a strong baseline in light of the observations made in [START_REF] Levin | Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy[END_REF]. Future work will be dedicated to the exploration of the consequences of this observation. Finally it is a natural to ask if this type of favorable property would extend to different proximal decomposition algorithms in a nonconvex setting, such as alternating methods or momentum methods.

2 .

 2 T C , NC and N C are semi-algebraic set valued maps. . 3. The interior and closure of C are semi-algebraic .

  for all k ∈ N. In other words, we have G = graph N C . By Proposition 3 item 3, the semi-algebraic set H = cl(graph NC ) \ graph NC ⊂ R 2p has dimension at most p -1. The set H can be understood as the graph of the possibly empty-valued map S : x ⇒ N C (x) \ NC (x). Now consider the set valued map R : x ⇒ S(x) + ∇f (x). Using Proposition 3 item 4 the dimension of graph R is at most p -1 because it is the image of H, by the map (x, z) → (x, z + ∇f (x)) which is semi-algebraic by Proposition 2 item 4. Now we have the following equivalence, for any

Figure 1 :

 1 Figure 1: Left: Illustration of the avoidance of the non Clarke regular point of Example 1, the constraint set is depicted by the thick black lines and the thiner lines display several projected gradient sequences with different step-sizes. Right: Avoidance of bad local minima. The feasible set is a grid and the contour of the convex quadratic objective is displayed. Every feasible point is a local minimum and the shape of the point indicate those which satisfies the quantitative estimate (6) (with an additional factor1 2 from Remark 2). We display several projected gradient sequences which all stop at the points satisfying these estimates.

2 ∥y -x∥ 2 f

 22 x + ∇f (x)∥ 2 (9) 0 ∈ ∂ g(y) + 1 2 ∥y -x + ∇f (x)∥ 2 y=x = ∂g(x) + ∇f (x)which is the Fréchet stationarity. This actually ensures that -∇f (x) is a proximal subgradient of g, and using [50, Proposition 8.46] and the descent Lemma, for all y ∈ R p ,g(y) ≥ g(x) + ⟨-∇f (x), y -x⟩ -1 (y) ≥ f (x) + ⟨∇f (x), y -x⟩ -1 2 ∥y -x∥ 2(10)f (y) + g(y) ≥ f (x) + g(x) -∥y -x∥ 2 .

  in C and (τ k ) k∈N in R + decreasing to 0. Furthermore, v ∈ R p is an element of the regular normal cone of C at x, written w ∈ NC (x) if Finally, v ∈ R p is an element of the normal cone of C at x, written w

	⟨v, y -x⟩ ≤ o(∥y -x∥),	y ∈ C,
	where the inequality is understood as lim sup y→x	⟨v,y-x⟩ ∥y-x∥ ≤ 0.

Acknowledgements

The authors acknowledge the support of the AI Interdisciplinary Institute ANITI funding, through the French "Investments for the Future -PIA3" program under the grant agreement ANR-19-PI3A0004, Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant numbers FA8655-22-1-7012, ANR Chess (ANR-17-EURE-0010), ANR Regulia and ANR Bonsai.


Hervé Pennec

João Manuel

Ramos

Susinyos Palace

Pennec

Nova -Maryam Gorgora

Gemb

THE RESEARCH OF GONDARINE HERITAGE REPORT -MAY, 15 TH , 2005

Introduction:

The 1972 UNESCO Convention for the Safeguard of Cultural and Natural Heritage has led to the expansion of a worldwide preservation programme that, in the case of cultural heritage, favoured the protection of architectural sites. Unfortunately, during the three following decades, the local implementation of such preservation programme has rarely considered the relevance of their organic relation to the historical and anthropological aspects of that heritage.

In various meetings of international experts and in the 1989 Chicago Declaration for the Safekeeping of Cultural Heritage, the UNESCO member states have progressively recognized that the limitations of such perspective hindered the development of a coherent and systematic protection of cultural values. To overcome this situation, the UNESCO General Assembly has approved, in October 26, 2003, the Convention for the Safeguard of Intangible Cultural Heritage. This new Convention is expected to become an essential legal and programmatic instrument to safeguard the endangered cultural heritage of many local communities and generally to protect cultural diversity as a fundamental means to sustainable world development. Presumably, it will also help redress the perversions that arose from the application of the 1972 Convention, in the case of the classified World Heritage Sites (WHS).

Considering the specific situation of the Gondar region, in Ethiopia, which is home to one WHS -the Fasil Gemb, in Gondar town -the preservation projects have focused, almost exclusively, on the preservation and restoration of the buildings situated within the castle compound and of the so-called Fasil's Bath. If the latter has, to this day, an important ceremonial and symbolic function, that was not certainly caused by the preservation programme but by the importance that the local Christian population accords it, during the annual festival of the Timkat (Orthodox Epiphany).

As to the former, it is an empty, clueless, space, detached from the town's and the region's cultural life, little else than an unkempt tourist attraction.

Present state of the research

The reason for the situation described above lies mainly in the fact that the historical site of Fasil Gemb, in Gondar, has been almost exclusively considered as a monumental emblem of Abyssinian royal power, and no integrative view was developed to understand it as part of the complex and dynamic cultural history of the Gondar region. Although the site itself, as well as the Fasil's Bath and the Qwesqwam compound, have been thoroughly surveyed and classified, by the Italian occupiers, by UNESCO experts, and by the local Culture Department, little research has been carried out in a number of important areas, which are essential to understand and give meaning to Gondar's architectural heritage. In particular, a artificial conception was developed in which a radical chronological cleavage served, and serves, to distinguish a supposed pre-Gondarine period (early 16 th century to circa 1640's) from the Gondarine times, which ideally start with the foundation of Fasiladas' castle (1634).

Oral and written historical sources and archaeological evidence should nevertheless help review this unsubstantiated idea. Analysis of historical documentation and site surveys carried out in the Lake Tana area by archaeologists Francis Anfray and Guy Annequin (1970Annequin ( 's to 1980's)'s), and later by the present team of researchers (from 1998 to today -see "research team -surveys", below), clearly show that this view is unfounded, since the Ethiopian kings have, throughout most of the so-called Gondarine period, extensively used, as courtly centres, the royal katamas built during the 16 th and early 17 th century. Consequently, it is fundamental to reconsider the notion of "royal site", within a broader and more dynamic perspective that may extend the scope of research and preservation programmes of Gondarine historical and architectural heritage to include such sites as Qoga, Guzara (and Debsan), Denkaz, Gorgora Nova (Maryam Gemb), as well as a number of Gojjami locations (Sarka, Yebabay Gemb, Giorghis Gemb, Mertula Maryam, etc.). Furthermore, there are other presumably relevant sites, recorded in the historical documentation relative to Gondarine royalty, which are yet to be identified.

Prospective research

For a deeper understanding of the historical foundation and development of Gondar (a step that seems essential for the proper interpretation of the architectural heritage of the Fasil Gemb and other sites in and around Gondar), a more cohesive methodology must be implemented, that permits the development of coordinated archaeological, historical and anthropological studies. The present team has been carrying out research in Gondar and in the Lake Tana area to try to understand the complex and insoluble relations between written sources (both indigenous and foreign), oral traditions and artistic expressions that frame Gondarine culture and history.

The oral stories that the team has been collecting, in and around Gondar, have already provided important hints about the history of the foundation of the capital and about the important transformations which occurred there, during the better part of the 17 th century. The continuation of this urgent task will undoubtedly help us elucidate many obscure anthropological aspects of the architectural sites and of their symbolical function as centres of the royal institution. The same must be said about the archaeological research. Diggings executed in the royal camp of Baeda Maryam (Menz) in 1999, by the Authority of Research and Conservation of Cultural Heritage, together with the French Centre of Ethiopian Studies, offer an important window to understand the organization of the katamas of Lake Tana, including that of Gondar.

Further research that brings together historical documentation, oral sources and archaeological evidence seems the only way to bring the ancient cultural heritage of Gondar out of the shadows of its neglected history. In this respect, a word must be said about the rich and extensive documentation in Portuguese, Latin and even Ge'ez, authored by Portuguese travellers and Jesuit missionaries, from the early 16 th century to the late 17 th century. This documentation has been used by historians that have little or no knowledge of Portuguese and Latin, and with general disregard of their literary, ideological and cultural constraints. The present team has been dedicating attention to these sources, in more substantial and global terms, but much of their richness is still to unearth.

The provisional results obtained by the research team confirm the need to expand the traditional view, repeatedly presented in historical publications about Gondarnamely:

the double question of the continuity and transformation of the Ethiopian royal institution, in its symbolic and functional relation to society and religion, from the late medieval period (Wolo) to the later occupation of the territory surrounding Lake Tana;

the need to enrich the study of the history of the Gondarine political system by considering the bi-univocal relation between royal central power and the largely autonomic regions of Gojjam, Tigray, Lasta, Shawa, Begemder, Wolo and Simien;

the reconsideration of the value of oral sources in the understanding of Gondarine civilization -both within and beyond the capital proper -, especially in order to provide a coherent view of the symbolic system that characterized the royal institution, and its relation with religion, magic, the judicial system, etc., and which instilled meaning to the architectonic spaces and the urban divisions (the Christian, Muslim, Kayla and Kemant quarters); -the reanalysis of the position of the royal compound within the capital, understood as part of a web of politico-religious authority, in which the numerous churches have always played a particularly relevant, and largely misunderstood, role;

the study of the often-conflicting relation between the Gondarine kingship system, the monastic orders and theological doctrines (Tehawedo, K'ebat, Karra, Catholicism);

a compared analysis with other regional and national contexts, in order to better comprehend the nature of the various institutions that shaped the social, cultural and artistic life of Gondar and the surrounding regionparticularly, by drawing attention to other East African kingdoms, to Arabian sultanates and to Indian states. In this respect, a revision of the international relations of the Gondarine royalty with neighbouring countries, with India (and specially with Portuguese possessions and trading places), and with Southern Europe (the Vatican, the Iberian Peninsula, in particular) is of utmost importance.

Problems of Conservation

Detailed survey of the sites executed during the years of 1998, 1999, 2001 and 2005, as well as various discussions with archaeologists, architects and art historians specialized in both Ethiopian and Indo-Portuguese heritage (see "provisional results", below), have led the research team to suspect that all preservation programmes which do not incorporate previous careful archaeological research, may lead to unrepairable damage to Ethiopian history: regrettably, this may have already happened, in the case of the consolidation of the castle of Guzara, which some popular traditions declare having been built by king Sarsa Dengel (1563-1597) but, according to such specialists as Prof. Merid Wolde Aregay, was probably subjected to a radical reconstruction during the late 17 th century -the fact that no systematic archaeological survey has taken place hampers a correct dating of the building and of the overlaying stages of occupation of the royal site. Other examples where human and/or natural action have also had shattering consequences for the archaeological study of the Gondarine heritage are two precious sites built during the reign of King Susinyos (1607-1632): Gorgora Nova (a church and castle compound of great architectural significance) and Azazo Ganata Iyesus (certainly, the model for the construction of the "Fasil's Bath", in Gondar).

The present team has identified strong signs of imminent decay in other surviving sites, the destruction of which will mean the loss of fundamental elements for the comprehension of the genesis and function of the Gondar WHS: this is clearly the case of Denkaz (both Susiunyos castle and the Catholic cathedral are at great risk), of Debsan (the walls of the "Casa do Patriarca", of great historical and architectural importance, risk collapse), of Mertula Maryam (the Catholic church, with its delicate Indo-Portuguese decorations, is on the verge of collapse), and other sites like Yebabay Gemb, Gemb Giorghis, Gemb Maryam (south of Bahir Dar), Sarka, Qoma Fasiladas and Qwalala. Attention should also be directed to infrastructures like bridges, such as the ones over Garno (Enfraz), over the Abbay (Eastern Gojjam), and over the Angareb (Gondar). The situation of the cistern of the royal palace of Dankaz, the only surviving of the series of arched cisterns built next to the royal compounds (including that of the Fasil Gemb, in Gondar) is a disheartening example of the dire need of resolute and coordinated action (at the local, regional and national level, and with the support of other interested parties -national and international organisations, both public and private): the installation of a corrugated iron roof, that would prevent its further erosion in the coming rainy season, would cost little more than one thousand birrs (one hundred euros), but the local community, which has shown obvious interest in the preservation of the site (namely by constructing a surrounding wall and regularly cleaning it of grass and bush), does not have the means or the knowledge to install it adequately.

In respect to the inventory and classification of historical sources, an overwhelming amount of work has yet to be executed. Not only is oral history in great danger by the fact that the holders of that type of information are dying out, without being able to transmit their knowledge to the younger generations, but the continuous plunder of church archives and libraries has led to the disappearance of important documental sources, to the scattering of information and to an attitude of ingrained suspicion and defensiveness on the part of local church authorities. Each church, in each locality of Lake Tana, preserves an original perspective regarding the region's history, which is kept both in writing and in oral stories (afatarik).

Still regarding conservation problems, one further word must be said: traditionally in Ethiopia, and clearly in Gondar, the popular idea of conservation has little to do with Western notions; to conserve an icon is to repaint it when its colours fade -its substance as a reproduction of an original image of the divine or of the saint being much more important that its original style, paint and material support. In some way, the same must be said about popular ideas on architectural preservation: a church is considered in its entire history, since the consecration of its tabot, irrespective of the fact that the original building might have crumbled and that another one was later reerected in the same place. This is the case of most churches in Gondar (the noted exception being that of Debra Berhane Selassie). When proceeding to preservation projects, one should be sensitive to the importance of such cultural notions -the Fasil's Bath being one case in point.

Recommendations

-

  coordination of the research programmes dedicated to the understanding of Gondarine heritage, by promoting continuous dialogue between national and international specialists, who have been dedicating their professional attention to this subject (though seminars, conferences, and linking via the internet); -creation of a Cultural and Studies Centre (in Ras Mikael Sehul's palace, for instance), with both a physical and a virtual (internet) interface, that may permit raising interest about Gondarine civilization among the local community, among the substantial Gondarine diaspora, among international scholars and among the general public interested in knowing more about Gondar (namely, prospective visitors and tourists); -establishment of physical and virtual databases, based on extensive and progressive inventories on Gondarine history, ethnography, geography, architecture, archaeology, prosopography (of local figures, of churches, monasteries, etc.) and art history, easily accessible to people interested in Gondarine studies -including manuscript and published material, oral and videographic records, digital reconstruction of architectural monuments, use of Geographic Information Systems, etc.; -logistical and financial support to research programmes on the abovementioned areas, with creation of an international scientific commission: -establishment of an urgent programme of consolidation of architectural sites in imminent danger, and creation of a coordinated effort to proceed to the further study and restoration of architectural and cultural heritage; -creation of a publishing programme, including Amharic and English versions of local historical sources, studies, facsimile of important yet unpublished documentation (namely that kept in Western archives and libraries); -support of local associations dedicated to the study and preservation of Gondarine heritage.

Provisional results

Surveys:

-1998: one month mission by Hervé Pennec in the Gondar and Gojjam regions (photographic survey, measurements and plans of monuments, and interviews to local people)

Contacts:

Hervé