Gamgne Domgue Félicité
email: felice.gamgne@gmail.com

Tsopze Norbert

Ndoundam René

Bruce Watson

Eric Badouel

Eds. Oumar Niang

Multidimensional networks A novel node centrality metric based on common neighborhood

Keywords: Multidimensionnal networks, Centrality measure, Relevance dimension MOTS-CLÉS : Reseaux multidimensionnels, mesure de centralité, Pertinence de dimension

Complex networks have been receiving increasing attention by the scientific community. They can be represented by multidimensional networks in which there is multiple types of connections between nodes. Thanks also to the increasing availability of analytical measures that have been extended in order to describe and analyze properties of entities involved in this kind of multiple relationship representation of networks. These measures focused on quantitative involvement of node through the widely popular and intuitive measure of degree. However, one aspect of such properties have been disregarded so far: entities in such networks are often tied according to the interest they have to their neighbors in the overall dimensions. In this paper, the problem of characterizing multidimensional networks, using a qualitative aspect of the node neighborhood, has been studied, through the new defined node centrality measure, Stability, to describe the connectivity of nodes that incorporates across-dimension topological features in order to identify the relevant dimensions. We assessed our measure on two real-world multidimensional networks, showing its validity, its meaningfulness and its correlation with a dimension connectivity measure.

RÉSUMÉ.

Les réseaux complexes ont reçu beaucoup d'attention de la part de la recherche scientifique. Ils peuvent etre représentés par des réseaux multidimensionnels dans lesquels il existe plusieurs types de relations entre les entités. Plusieurs propriétés decrivant les noeuds et permettant l'extraction de la connaissance sur de tels réseaux, ont été étudiées. La majorité d'entre elles prone l'aspect quantitatif de la connectivité d'un noeud, à l'instar de la centralité de degré. Cependant, un aspect primordial a été omis: celui qualitatif, basé sur le type de voisinage d'un noeud. En effet, dans de tels réseaux, les entités sont généralement connectées selon les mêmes centres d'intérêts qu'ils possèdent. Dans ce travail, le problème de caractérisation des réseaux multidimensionnels moyennant l'utilisation de la notion qualitative du voisinage d'un noeud, a été abordé à travers la définition d'une nouvelle mesure de centralité appelée Stabilité. Cette dernière permet de décrire la connectivité des noeuds basée sur les caractéristiques topologiques, en vu de déterminer les dimensions pertinentes. L'évaluation de cette mesure s'effectue sur deux réseaux multidimensionnels réels, et montre sa validité et sa correlation à une mesure de connectivité de dimensions.

Introduction

Complex network analysis has received a lot of attention by the scientific researchers, because it helps to better understand the intrinsic behavior of relationships between entities. These relationships could be either of one or several types. Unlike a monodimensional network which contains only one type of links between nodes, multidimensional networks contain links which either reflect different kinds of relationship or represent different values of the same kind of relationship among a same set of elementary components. This flexibility allowed to use complex networks to study real-world systems in many fields: sociology, physics, genetics, computer, etc. Such systems can be modeled by multidimensional networks as reported in Figure 1 [START_REF] Berlingerio | Multidimensional networks: foundations of structural analysis[END_REF] where on the left we have different types of links, while on the right we have different values (conferences) for one relationship (for example, co-authorship). Multidisciplinary and extensive research works have been devoted to the extraction of non trivial knowledge from such networks [START_REF] Mucha | Community structure in timedependent, multiscale, and multiplex networks[END_REF]. Some of them focused on the characterization of their properties. More precisely, they studied some centrality measurements based on the quantitative neighborhood also called "weight", of each node [START_REF] Berlingerio | Multidimensional networks: foundations of structural analysis[END_REF][START_REF] Nicosia | Measuring and modeling correlations in multiplex networks[END_REF]. These measures, which are certainly relevant, do not take into account a more recent reality. Indeed, with the advent of the Internet and social networking sites, individuals communicate more easily when the majority of their contacts use the same platforms or means of communication as they do. Thus, the qualitative aspect of this neighborhood is important to be considered. From this aspect, a semantics emerges relating to the retention of the same neighbors of a node over all dimensions, namely Stability. To the best of our knowledge, however, the literature still misses a systematic qualitative measure for weight-based centrality in the context of correlated multidimensional networks, together with a model of extracting relevant dimensions for each node. The aim of this paper is precisely defining a basic and analytical concept of centrality measure, which takes into account the connectivity redundancy of nodes among dimensions. As questioned in [START_REF] Berlingerio | Multidimensional networks: foundations of structural analysis[END_REF], how is it possible to contribute to answering the question To what extent one or more dimensions are more important than others for the connectivity of a node? Contributions: In this work:

-We introduce a novel centrality weighting scheme of nodes called stability, in multidimensional network -We formally define a measure aimed at extracting useful knowledge on relevance dimensions of nodes -We characterize nodes of the multidimensional network according to their stability -we empirically test the meaningfulness of our measure, by means of a case study on two realistic networks.

The rest of the paper is organized as follows. Section 2 overviews related works, Section 3 describes the proposed measures to assess the activity level of a node in a dimension. Section 4 presents experimental evaluation, Section 5 concludes the paper.

Related works

Multidimensional networks have for a long time been proposed as an alternative to better describe interactions within complex systems [START_REF] Berlingerio | Multidimensional networks: foundations of structural analysis[END_REF]. For instance, in social networks, individuals can be connected according to different social ties, such as friendship or family relationship [START_REF] Verbrugge Lois | Multiplexity in Adult Friendships*[END_REF]. The extraction of knowledge and analysis of both the local and global properties of such networks remains of interest to scientists. Indeed, multidimensional networks abound with a large amount of information, particularly concerning the various kinds of relationship between entities. Since an individual may have a particular interest for a certain number of dimensions, he could be influential or important in regard to other nodes in these dimensions: they are then qualified as central. So ignoring centrality in multidimensional structures can lead to different ranking results than what one obtains for multidimensional networks [START_REF] Domenico | Centrality in interconnected multilayer networks[END_REF] .

Centrality, an indicator that quantifies the importance of nodes in a network, comes from the discipline of Social network analysis and has become a fundamental concept in network science with its applications in a range of disciplines. In recent works, many efforts have been devoted to "centrality" measures in order that they are also applicable in multidimensional networks [START_REF] Domenico | Centrality in interconnected multilayer networks[END_REF]. Examples of these various centrality measures include degree centrality, called overlapping degree in [START_REF] Nicosia | Measuring and modeling correlations in multiplex networks[END_REF]. As they help to extract a knowledge and analyze the network properties related to the questioning of "how important a dimension for a node is", these measures are based on both relevance dimension and dimension connectivity, since nodes could exist across all dimensions. A multigraph used to model a multidimensional network is denoted by a triple G = (V, E, L) where: V is a set of nodes; L is a set of dimensions; E is a set of edges, i.e the set of triples (u, v, d) where u, v ∈ V are nodes and d ∈ L is a dimension. Thus, Berlingerio [START_REF] Berlingerio | Multidimensional networks: foundations of structural analysis[END_REF] defined a relevance dimension measure based on the connectivity of dimensions, as described in Equation 1, which computes the fraction of neighbors directly reachable from node v following edges belonging only to the set of dimensions called D with D ⊆ L. Likewise, he defined a measure Node Exclusive Dimension Connectivity (N EDC) computing the ratio of nodes belonging only to a specific dimension d, as described in Equation 2.

DR XOR (v, D) = |N eighbors XOR (v, D)| |N eighbors(v, L)| (1)
N EDC(d) = |u ∈ V |∃v ∈ V : (u, v, d) ∈ E ∧ ∀j ∈ L, j = d : (u, v, j) / ∈ E| |u ∈ V |∃v ∈ V : (u, v, d) ∈ E| (2)
where N eighbors XOR (v, D) is the set of neighbors of v belonging only to dimensions D. Despite their popularity and effectiveness in social network analysis, we believe to our knowledge that these measures mainly take into account the quantitative aspect (i.e. degree) of node properties and links, yet the qualitative aspect, namely the type of neighboring nodes, would have a significant impact on facilitating communication between an individual and his neighborhood. Indeed, these measurements focus only on the degree of nodes regardless of the type of neighborhood, to extract the relevant dimensions. According to them, a relevant dimension for a node is quantified by the density of its neighborhood. Thus, if a node has the same number of neighbors on all dimensions, then all these dimensions will be relevant to it. However, in real life situations relating to human relationships, the communication is more obvious, more easy or cheaper among individuals using the same platform of information exchanges. So, the interest a user has for a platform depends on the subscription of his friends to that platform. Therefore, a dimension(platform) would be more relevant for a node(subscriber) if the node has a conservative behavior of its neighborhood over all dimensions. It is this concept that we implement in the next section.

Multidimensional network analysis

This paragraph presents new defined measures to contribute to knowledge extraction from a multidimensional networks. They concern whether a dimension can be of interest for a node, based on the stability of his neighbors. In the first subsection, the stability centrality is defined, and in the second subsection, we present how to determine the relevant dimensions of a node.

Stability centrality

The weights of the nodes have been the subject of some studies. According to graph theory, this weight corresponds to the sum of the weights of the edges incident to this node. It is a variant of the degree centrality. This measure shows that the importance of a node depends on the number of communications it establishes with its neighborhood. It corresponds to its activity level in a network. Extending this measure in multidimensional networks, Nicosia et al. [START_REF] Nicosia | Measuring and modeling correlations in multiplex networks[END_REF] studied that the activity of a node in a particular dimension is very often correlated with its activity in another dimension. The authors considered the centrality degree as a measure of the node activity in a dimension. However, the number of neighbors seems to be meaningless when studying behavior of entities in a context of correlated dimensions. Then it becomes necessary to maintain the stable behavior of a node in order to make easy information exchange among its community membership. The stability centrality of a node u is then pointed up and computes the proportion of the common neighborhood of this node between two dimensions p and q, through a Jaccard index similarity as defined through Definition 1. It takes into account the structural features across several dimensions.

Definition 1 (The stability centrality of a node in a dimension).

Stability centrality of node u in dimension q measures the common neighborhood of a node between q and the other dimensions. The function Stability : V × D → [0, 1] is defined as:

Stability(u, q) = 1 ndim -1 ndim-1 p=0 | Γ p u ∩ Γ q u | | Γ p u ∪ Γ q u | (3)
whereΓ p u denotes the neighborhood of node u in the dimension p and ndim denotes the number of dimensions. We refer to disassortative stability when its neighborhood is totally different in all dimensions; Stability tends to be null. Otherwise, it is the assortative stability; it tends to its maximal value 1. In this paper, the node with the lowest disassortative stability is unstable and the one with the highest assortative stability is the most stable over the network. As shown in table of Figure 2 above, node 1 possesses a disassortative stability, unlike node 7 which gets an assortative stability.

Relevance dimension

The concept of dimension relevance of a node studied in [START_REF] Boutemine | Mining community structures in multidimensional networks[END_REF] stresses on that dimension in which the node has the most important exclusive degree as defined by Berlingerio [START_REF] Berlingerio | Multidimensional networks: foundations of structural analysis[END_REF] i.e. it computes the fraction of neighbors directly reachable from node u following edges belonging exclusively to a subset of dimensions D l as shown in Equation 1. This way does not seem relevant in some real situations, because if a node has the same degree on all dimensions of the network, then all of them will be relevant. Yet, if we consider only those in which the node has a more stable neighborhood, the relevance of the dimensions would be more semantic. The relevant dimensions RD(u) of a node u refers to those dimensions for which the node has a stability centrality greater than or equal to a certain threshold ε. It is described by the function RD : V → D as:

RD(u) = {q, |Stability(u, q) ≥ ε} (4)
The threshold ε is defined in the Equation 5. When the node u has a stability centrality whose value is higher than ε, it is said that the node u is stable for the subset of dimensions RD(u), or that the dimensions in the subset RD(u) are relevant for the node u.

ε = 1 |D| |D| i=1 Stability(u, i) (5)

Experimental Evaluation

In this section, we assess the proposed metric on two main sights: its correlation with dimension connectivity and the behavior of nodes according to the values of the metric.

Correlation with dimension connectivity

This section reports the results obtained by computing the stability measure on two real-world multidimensional network datasets, namely AUCS [START_REF] Magnani | Combinatorial analysis of multiple networks[END_REF] and DBLP [START_REF] Boden | Mining coherent subgraphs in multi-layer graphs with edge labels[END_REF]. AUCS, an attributed multidimensional network, models relationships between 61 employees of Aarhus University Computer Science department considering five different aspects: coworking, having lunch together, Facebook friendship, offline friendship, and coauthorship. In Figure 3 reports the cumulative distribution of the stability measure. It denotes the average of nodes' stability on 10 intervals. The latter corresponds to the normalization of the number of nodes. Figure 3(a) is a small dataset. Then there is no need to cumulate the stability centrality of the nodes, unlike the figures 3(b) and 3(c) whose size is important, leading to a normalization of their x-axis. Berlingerio in [START_REF] Berlingerio | Multidimensional networks: foundations of structural analysis[END_REF] analyzed the correlation between the DR xor distribution and the Dimension Connectivity values (especially N EDC). The authors deduced that DR xor measure is correlated to the N EDC measure. Following them, we analyze the correlation between the stability distribution and the N EDC measure. What can be seen by looking at the Stability distribution and N EDC values, reported in Tables 123, is that the Stability distributions seem to be correlated to the N EDC measure. This correlation is not surprising since by definition, the two measures are two different perspectives, one local (Node stability) and one global (Dimension Connectivity), of the same aspect: how much a node is important for the connectivity of a network. We note, in fact, that the stability tends to be higher in conjunction with higher N EDC values.

Analyzing node behavior

This section describes node behaviors in the overall dimensions, according to its degree and its stability. Assume that the network in Figure 2 represents an exchange of experiences through a multidimensional network between actors of the agriculture area (e.g. farmers), in which a dimension describes a type of crop (banana, onion, rice, etc.). The idea behind the stability metric is that a stable node/actor is the more important because it favors a success in agricultural business, moreover, the other nodes/actors trust in him. Then, the stability of a farmer's neighborhood demonstrates his competence; therefore, he becomes a more reliable source of information. An individual may not be reliable if he loses his regular relationship. In Figure 2, node 7 is an example of this. If the second and third dimensions are removed, it looses its trusted contacts, but still remains present in the network. On the other hand, according to DR xor measure, that node 7 disappears from the network. As shown in Figure 4, this node has the same value of DR xor across all dimensions, but its value of stability is low in the first dimension. Otherwise, the node 1 has a disassortative behavior. Any dimension is relevant for this node, meaning that it is less important across dimensions.

Conclusion

We proposed a novel centrality measure based on stability of the neighborhood of nodes. Since an active node on one dimension can remain inactive on the rest of the dimensions, it is possible to study the stability of a node in a multidimensional context, according to its center of interest. Therefore we defined the notion of relevance dimension of a node in order to contribute to the question of how important is a dimension for a node. An assessment on the semantic given to the stability centrality compared to degree centrality was carried out. Likewise, we show how correlated the stability to the dimension connectivity NEDC measure. The next study intends to assess the impact of this measure on the communities obtained from a well-defined model.

Figure 1 :

 1 Figure 1: Example of multidimensional networks

Figure 2 :

 2 Figure 2: An example of connected multidimensional network with 3 dimensions on the left, and on the right, the stability node on the top and threshold for relevance dimension extraction below.

  (a) Stability centrality on the network in Fig. 2 illustration (b) Cumulative Stability on AUCS (c) Cumulative Stability on DBLP

Figure 3 :

 3 Figure 3: Stability centrality distribution DBLP, there are 83901 nodes which correspond to authors, tied by 159302 links, and 50 dimensions represent the top-50 Computer Science conferences. Two authors are connected on a dimension if they co-authored at least two papers together in a particular conference. All the experiments were conducted on an Intel Core i5 -8250U CPU @1.60GH z , 8GB of RAM machine, Windows 10 OS 64 bytes.Figure3reports the cumulative distribution of the stability measure. It denotes the average of nodes' stability on 10 intervals. The latter corresponds to the normalization of the number of nodes. Figure3(a) is a small dataset. Then there is no need to cumulate the stability centrality of the nodes, unlike the figures 3(b) and 3(c) whose size is important, leading to a normalization of their x-axis. Berlingerio in[START_REF] Berlingerio | Multidimensional networks: foundations of structural analysis[END_REF] analyzed the correlation between the DR xor distribution and the Dimension Connectivity values (especially N EDC). The authors deduced that DR xor measure is correlated to the N EDC measure. Following them, we analyze the correlation between the stability distribution and the N EDC measure. What can be seen by looking at the Stability distribution and N EDC values, reported in Tables1-3, is that the Stability distributions seem to be correlated to the N EDC measure. This correlation is not surprising since by definition, the two measures are two different perspectives, one local (Node stability) and one global (Dimension Connectivity), of the same aspect: how much a node is important for the connectivity of a network. We note, in fact, that the stability tends to be higher in conjunction with higher N EDC values.

(a) Stability behavior on dimension 1 (

 1 b) Stability behavior on dimension 2 (c) Stability behavior on dimension 3

Figure 4 :

 4 Figure 4: Stability and DR xor assessments on network in Fig. 2

Table 1 :

 1 Node connectivity, Node stability, computed on the illustration network in Fig.2

	Dimension	Stability average NEDC
	Dimension 1 0.63	0.85
	Dimension 2 0.4	0.7
	Dimension 3 0.47	0.7

Table 2 :

 2 Node connectivity, Node stability, computed on AUCS network

	Dimension Stability average NEDC
	Lunch	0.22	0.15
	Facebook	0.10	0.03
	Coauthor	0.11	0.05
	Leisure	0.20	0.11
	Work	0.24	0.25

Table 3 :

 3 Node connectivity, Node stability, computed on DBLP network

	Dimension Stability average NEDC
	VLDB	0.00115	0.75
	SIGMOD	0.0046	0.97
	CIKM	0.15	3.86
	SIGKDD	0.0087	1.38
	ICDM	0.098	2.45
	SDM	0.055	1.44

Proceedings of CARI 2020


Peggy Cénac

Antoine Godichon-Baggioni

Bruno Portier

An efficient Averaged Stochastic Gauss-Newton algorithm for estimating parameters of non linear regressions models

Non linear regression models are a standard tool for modeling real phenomena, with several applications in machine learning, ecology, econometry... Estimating the parameters of the model has garnered a lot of attention during many years. We focus here on a recursive method for estimating parameters of non linear regressions. Indeed, these kinds of methods, whose most famous are probably the stochastic gradient algorithm and its averaged version, enable to deal efficiently with massive data arriving sequentially. Nevertheless, they can be, in practice, very sensitive to the case where the eigenvalues of the Hessian of the functional we would like to minimize are at different scales.

To avoid this problem, we first introduce an online Stochastic Gauss-Newton algorithm. In order to improve the estimates behavior in case of bad initialization, we also introduce a new Averaged Stochastic Gauss-Newton algorithm and prove its asymptotic efficiency.

Introduction

We consider in this paper nonlinear regression model of the form

Y n = f (X n , θ) + ε n , n ∈ N,
where the observations (X n , Y n ) n are independent random vectors in R p × R, (ε n ) n are independent, identically distributed zero-mean non observable random variables. Moreover, f : R p × R q -→ R and θ ∈ R q is the unknown parameter to estimate.

Nonlinear regression models are a standard tool for modeling real phenomena with a complex dynamic. It has a wide range of applications including maching learning [START_REF] Bach | Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression[END_REF]), ecology [START_REF] Komori | An asymmetric logistic regression model for ecological data[END_REF]), econometry [START_REF] Varian | Big data: New tricks for econometrics[END_REF]), pharmacokinetics [START_REF] Bates | Nonlinear regression analysis and its applications[END_REF]), epidemiology [START_REF] Suárez | Applications of Regression Models in Epidemiology[END_REF]) or biology [START_REF] Giurcȃneanu | Clustering time series gene expression data based on sum-of-exponentials fitting[END_REF]).

Most of the time, the parameter θ is estimated using the least squares method, thus it is estimated by

θ n = arg min h∈R q n ∑ j=1 (Y j -f (X j , h)) 2
Many authors have studied the asymptotic behavior of the least squares estimator, under various assumptions with different methods. For example, [START_REF] Jennrich | Asymptotic properties of non-linear least squares estimators[END_REF] consider the case when θ belongs to a compact set, f is a continuous function with a unique extremum. [START_REF] Wu | Asymptotic theory of nonlinear least squares estimation[END_REF] consider similar local assumptions. [START_REF] Lai | Asymptotic properties of nonlinear least squares estimates in stochastic regression models[END_REF]; [START_REF] Skouras | Strong consistency in nonlinear stochastic regression models[END_REF]; van de [START_REF] Van De Geer | Estimating a regression function[END_REF]; [START_REF] Van De Geer | Consistency for the least squares estimator in nonparametric regression[END_REF]; [START_REF] Yao | On least squares estimation for stable nonlinear AR processes[END_REF] generalized the consistency results. Under a stronger assumption about the errors ε, that is, considering that the errors are uniformly subgaussian, van de Geer (1990) obtained sharper stochastic bounds using empirical process methods. Under second moment assumptions on the errors and regularity assumptions (lipschitz conditions) on f , [START_REF] Pollard | Nonlinear least-squares estimation[END_REF] established weak consistency and a central limit theorem. [START_REF] Yang | Sparse nonlinear regression: Parameter estimation under nonconvexity[END_REF] consider a compact set for θ, under strong regularity assumptions and the algorithm allows to reach a stationary point without certainty that it is the one we are looking for. They built hypothesis tests and confidence intervals. Finally, let also mention [START_REF] Yao | On least squares estimation for stable nonlinear AR processes[END_REF] which considers the case of stable nonlinear autoregressive models and establishes the strong consistency of the least squares estimator.

However, in practice, the calculation of the least square estimator is not explicit in most cases and therefore requires the implementation of a deterministic approximation algorithm. The second order Gauss-Newton algorithm is generally used (or sometimes Gauss-Marquard algorithm to avoid inversion problems (see for example [START_REF] Bates | Nonlinear regression analysis and its applications[END_REF]).

These algorithms are therefore not adapted to the case where the data are acquired sequentially and at high frequencies. In such a situation, stochastic algorithms offer an interesting alternative. One example is the stochastic gradient algorithm, defined by

θ n = θ n-1 -γ n ∇ θ f (X n , θ n-1 ) (Y n -f (X n , θ n-1 )) ,
where (γ n ) is a sequence of positive real numbers decreasing towards 0. Thanks to its recursive nature, this algorithm does not require to store all the data and can be updated automatically when the data sequentially arrive.

It is thus adapted to very large datasets of data arriving at high speed. We refer to [START_REF] Robbins | A stochastic approximation method[END_REF] and to its averaged version [START_REF] Polyak | Acceleration of stochastic approximation[END_REF] [START_REF] Ruppert | Efficient estimations from a slowly convergent robbins-monro process[END_REF]. However, even if it is often used in practice as in the case of neural networks, the use of stochastic gradient algorithms can lead to non satistying results. Indeed, for such models, it amounts to take the same step sequence for each coordinates. Nevertheless, as explained in [START_REF] Bercu | An efficient stochastic newton algorithm for parameter estimation in logistic regressions[END_REF], if the Hessian of the function we would like to minimize has eigenvalues at different scales, this kind of "uniform" step sequences is not adapted.

In this paper, we propose an alternative strategy to stochastic gradient algorithms, in the spirit of the Gauss-Newton algorithm. It is defined by :

φ n = ∇ θ f (X n , θ n ) S -1 n = S -1 n-1 -(1 + φ T n S -1 n φ n ) -1 S -1 n-1 φ n φ T n S -1 n-1 θ n = θ n-1 + S -1 n φ n (Y n -f (X n , θ n-1 ))
where the initial value θ 0 can be arbitrarily chosen and S 0 is a positive definite deterministic matrix, typically S 0 = I q where I q denotes the identity matrix of order q. Remark that thanks to Riccati's formula (see (Duflo, 1997, p. 96), also called Sherman Morrison's formula [START_REF] Sherman | Adjustment of an inverse matrix corresponding to a change in one element of a given matrix[END_REF]), S -1 n is the inverse of the matrix S n defined by

S n = S 0 + n ∑ j=1 φ j φ T j .
When the function f is linear of the form f (x, θ) = θ T x, algorithm (1)-( 3) rewrites as the standard recursive least-squares estimators (see [START_REF] Duflo | of Applications of Mathematics[END_REF]) defined by:

S -1 n = S -1 n-1 -(1 + X T n S -1 n-1 X n ) -1 S -1 n-1 X n X T n S -1 n-1 θ n = θ n-1 + S -1 n X n Y n -θ T n-1 X n
This algorithm can be considered as a Newton stochastic algorithm since the matrix n -1 S n is an estimate of the Hessian matrix of the least squares criterion.

To the best of our knowledge and apart from the least squares estimate mentioned above, second order stochastic algorithms are hardly ever used and studied since they often require the inversion of a matrix at each step, which can be very expensive in term of time calculation. To overcome this problem some authors (see for instance [START_REF] Mokhtari | Res: Regularized stochastic bfgs algorithm[END_REF]; [START_REF] Lucchi | A variance reduced stochastic newton method[END_REF]; [START_REF] Byrd | A stochastic quasi-newton method for large-scale optimization[END_REF]) use the BFGS (for Broyden-Fletcher-Goldfarb-Shanno) algorithm which is based on the recursive estimation of a matrix whose behavior is closed to the one of the inverse of the Hessian matrix. Nevertheless, this last estimate need a regularization of the objective function, leading to unsatisfactory estimation of the unknown parameter. In a recent paper dedicated to estimation of parameters in logistic regression models [START_REF] Bercu | An efficient stochastic newton algorithm for parameter estimation in logistic regressions[END_REF], the authors propose a truncated Stochastic Newton algorithm. This truncation opens the way for online stochastic Newton algorithm without necessity to penalize the objective function.

In the same spirit of this work, and to relax assumption on the function f , we consider in fact a modified version of the stochastic Gauss-Newton algorithm defined by (3), that enables us to obtain the asymptotic efficiency of the estimates in a larger area of assumptions.

In addition, we introduce the following new Averaged Stochastic Gauss-Newton algorithm (ASN for short) defined by

φ n = ∇ h f (X n , θ n-1 ) S -1 n = S -1 n-1 -(1 + φ T n S -1 n-1 φ n ) -1 S -1 n-1 φ n φ T n S -1 n-1 θ n = θ n-1 + n β S -1 n φ n (Y n -f (X n , θ n-1 )) θ n = θ n-1 + 1 n θ n -θ n-1
where β ∈ (0, 1/2), θ 0 = 0. The introduction of the term n β before the term S -1 n in (6) allows the algorithm to move quickly which enables to reduce the sensibility to a bad initialization. The averaging step allows to maintain an optimal asymptotic behavior. Indeed, under assumptions, we first give the rate of convergence of the estimates, before proving their asymptotic efficiency.

The paper is organized as follows. Framework and algorithms are introduced in Section 2. In Section 3, we give the almost sure rates of convergence of the estimates and establish their asymptotic normality. A simulation study illustrating the interest of averaging is presented in Section 4. Proofs are postponed in Section 5 while some general results used in the proofs on almost sure rates of convergence for martingales are given in Section 6.

Framework

The model

Let us consider the non linear regression model of the form

Y n = f (X n , θ) + n
where (X n , Y n , n ) n≥1 is a sequence of independent and identically distributed random vectors in R p × R × R. Furthermore, for all n, n is independent from X n and is a zero-mean random variable. In addition, the function f is assumed to be almost surely twice differentiable with respect to the second variable. Under certain assumptions, θ is a local minimizer of the functional G : R q -→ R + defined for all h ∈ R q by

G(h) = 1 2 E (Y -f (X, h)) 2 =: 1 2 E [g(X, Y, h)] ,
where (X, Y, ) has the same distribution as (X 1 , Y 1 , 1 ). Suppose from now that the following assumptions are fulfilled:

(H1a) There is a positive constant C such that for all h ∈ R q , E ∇ h g (X, Y, h) 2 ≤ C, (H1b) There is a positive constant C such that for all h ∈ R q , E ∇ h f (X, h) 4 ≤ C (H1c) The matrix L(h) defined for all h ∈ R q by L(h) = E ∇ h f (X, h)∇ h f (X, h) T is positive at θ.
Assumption (H1a) ensures ifrst that the functional G is Frechet differentiable for all h ∈ R q . Moreover, since is independent from X and zero-mean,

∇G(h) = E [( f (X, h) -f (X, θ)) ∇ h f (X, h)] .
Then, ∇G(θ) = 0. Assumption (H1b) will be crucial to control the possible divergence of estimates of L(θ) as well as to give their rate of convergence. Finally, remark that thanks to assumption (H1c), L(θ) is invertible.

Construction of the Stochastic Gauss-Newton algorithm

In order to estimate θ, we propose in this work a new approach. Instead of using straight a Stochastic Newton algorithm based on the estimate of the Hessian of the functionnal G, we will substitute this estimate by an estimate of L(θ), imitating thereby the Gauss-Newton algorithm. This leads to an algorithm of the form

θ n+1 = θ n + 1 n + 1 L -1 n (Y n+1 -f (X n+1 , θ n )) ∇ h f (X n+1 , θ n ) ,
where

L n := 1 n n ∑ i=1 ∇ h f (X i , θ i-1 ) ∇ h f (X i , θ i-1 ) T
is a natural recursive estimate of L(θ). Remark that supposing the functional G is twice differentiable leads to

∇ 2 G(h) = E ∇ h f (X, h) ∇ h f (X, h) T -E ( f (X, θ) -f (X, h)) ∇ 2 h f (X, h) ,
and in particular, H = ∇ 2 G(θ) = L(θ). Then, L n is also an estimate of H. The proposed algorithm can so be considered as a Stochastic Newton algorithm, but does not require an explicit formula for the Hessian of G. Furthermore, the interest of considering L n as an estimate of H is that we can update recursively the inverse of L n thanks to the Riccati's formula. To obtain the convergence of such an algorithm, it should be possible to state the following assumption:

(H*) There is a positive constant c such that for all h ∈ R q , λ min (L(h)) ≥ c.

Nevertheless, this assumption consequently limits the family of functions f we can consider.

The algorithms

In order to free ourselves from the restrictive previous assumption (H*), we propose to estimate θ with the following Gauss-Newton algorithm.

Definition 2.1 (Stochastic Gauss-Newton algorithm). Let (Z n ) n≥1 be a sequence of random vectors, independent and for all n ≥ 1, Z n ∼ N (0, I q ). The Gauss-Newton algorithm is defined recursively for all n ≥ 0 by

Φ n+1 = ∇ h f X n+1 , θ n θ n+1 = θ n + H -1 n Φ n+1 Y n+1 -f X n+1 , θ n (8) H -1 n+ 1 2 = H -1 n -1 + c β (n + 1) β Z T n+1 H -1 n Z n+1 -1 c β (n + 1) β H -1 n Z n+1 Z T n+1 H -1 n H -1 n+1 = H -1 n+ 1 2 -1 + Φ T n+1 H -1 n+ 1 2 Φn+1 -1 H -1 n+ 1 2 Φ n+1 Φ T n+1 H -1 n+ 1 2 ,
with θ 0 bounded, H -1 0 symmetric and positive, c β ≥ 0 and β ∈ (0, 1/2). Note that compared with the algorithm (2.2), matrix (n + 1)L n has been replaced by matrix H n defined by:

H n = H 0 + n ∑ i=1 Φ i Φ T i + n ∑ i=1 c β i β Z i Z T i .
Matrix H -1 n is iteratively computed thanks to Riccati's inversion formula (see (Duflo, 1997, p.96)) which is applied twice: first recursively inverse matrix

H n+ 1 2 = H n + c β (n+1) β Z n+1 Z T n+1 , then matrix H n+1 = H n+ 1 2 + Φ n+1 Φ T n+1 .
In fact, introducing this additional term enables to ensure, taking c β > 0 that (see the proof of Theorem 3.1)

λ max H -1 n = O n 1-β a.s.
Therefore, it enables to control the possible divergence of the estimates of the inverse of the Hessian and to obtain convergence results without assuming (H*). Anyway, if assumption (H*) is verified, one can take c β = 0 and Theorem 3.4 remains true. Remark that considering the Gauss-Newton algorithm amounts to take a step sequence of the form 1 n . Nevertheless, in the case of stochastic gradient descents, it is well known in practice that this can lead to non sufficient results with a bad initialization. In order to overcome this problem, we propose an Averaged Stochastic Gauss-Newton algorithm, which consists in modifying equation ( 8) by introducing a term n 1-α (with α ∈ (1/2, 1)), leading step sequence of the form 1 n α . Finally, in order to ensure the asymptotic efficiency, we add an averaging step.

Definition 2.2 (Averaged Stochastic Gauss-Newton algorithm). The Averaged Stochastic Gauss Newton algorithm is recursively defined for all n ≥ 0 by

Φ n+1 = ∇ h f X n+1 , θ n θ n+1 = θ n + γ n+1 S -1 n (Y n+1 -f (X n+1 , θ n )) ∇ h f (X n+1 , θ n ) (9) θ n+1 = n + 1 n + 2 θ n + 1 n + 2 θ n+1 (10)
S -1

n+ 1 2 = S -1 n -1 + c β (n + 1) β Z T n+1 S -1 n Z n+1 -1 c β (n + 1) β S -1 n Z n+1 Z T n+1 S -1 n S -1 n+1 = S -1 n -1 + Φ T n+1 S -1 n Φ n+1 -1 S -1 n Φ n+1 Φ T n+1 S -1 n .
where θ 0 = θ 0 is bounded, S 0 is symmetric and positive,

γ n = c α n -α with c α > 0, c β ≥ 0, α ∈ (1/2, 1), β ∈ (0, α -1/2) and S -1 n = (n + 1)S -1 n .
Let us note that despite the modification of the algorithm, Riccati's formula always hold.

Finally, remark that if assumption (H*) is satisfied, one can take c β = 0 and Theorem 3.1 in Section 3 remains true.

Additional assumptions

We now suppose that these additional assumptions are fulfilled:

(H2) The functional G is twice Frechet differentiable in R q and there is a positive constant C such that for all h ∈ R q , ∇ 2 G(h) ≤ C .

Note that this is an usual assumption in stochastic convex optimization (see for instance [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF]), and especially for studying the convergence of stochastic algorithms [START_REF] Bach | Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression[END_REF][START_REF] Godichon-Baggioni | Lp and almost sure rates of convergence of averaged stochastic gradient algorithms: locally strongly convex objective[END_REF][START_REF] Gadat | Optimal non-asymptotic bound of the ruppert-polyak averaging without strong convexity[END_REF].

(H3)

The function L is continuous at θ.

Assumption (H3) is used for the consistency of the estimates of L(θ), which enables to give the almost sure rates of convergence of stochastic Gauss-Newton estimates and their averaged version.

Let us now make some additional assumptions on the Hessian of the function we would like to minimize:

(H4a) The functional h -→ ∇ 2 G(h) is continuous on a neighborhood of θ. (H4b) The functional h -→ ∇ 2 G(h) is C G -Lipschitz on a neighborhood of θ.
Assumption (H4a) is useful for establishing the rate of convergence of stochastic Gauss-Newton algorithms given by ( 8) and ( 9) while assumption (H4b) enables to give the rate of convergence of the averaged estimates. Clearly (H4b) implies (H4a). Note that as in the case of assumption (H2), these last ones are crucial to obtain almost sure rates of convergence of stochastic gradient estimates (see for instance [START_REF] Pelletier | On the almost sure asymptotic behaviour of stochastic algorithms[END_REF][START_REF] Godichon-Baggioni | Lp and almost sure rates of convergence of averaged stochastic gradient algorithms: locally strongly convex objective[END_REF]).

Convergence results

We focus here on the convergence of the Averaged Stochastic Gauss-Newton algorithms since the proofs are more unusual than the ones for the non averaged version. Indeed, these last ones are quite closed to the proofs in [START_REF] Bercu | An efficient stochastic newton algorithm for parameter estimation in logistic regressions[END_REF].

Convergence results on the averaged estimates

The first theorem deals with the almost sure convergence of a subsequence of ∇G (θ n ).

Theorem 3.1. Under assumptions (H1) and (H2) with c β > 0, G (θ n ) converges almost surely to a finite random variable and there is a subsequence

(θ ϕ n ) such that ∇G θ ϕ n a.s ----→ n→+∞ 0
Remark that if the functional G is convex or if we project the algorithm on a convex subspace where G is convex, previous theorem leads to the almost sure convergence of the estimates. In order to stay as general as possible, let us now introduce the event

Γ θ = ω ∈ Ω, θ n (ω) ----→ n→+∞ θ .
It is not unusual to introduce this kind of events for studying convergence of stochastic algorithms without loss of generality: see for instance [START_REF] Pelletier | On the almost sure asymptotic behaviour of stochastic algorithms[END_REF][START_REF] Pelletier | Asymptotic almost sure efficiency of averaged stochastic algorithms[END_REF]. Many criteria can ensure that P [Γ θ ] = 1, i.e that θ n converges almost surely to θ (see [START_REF] Duflo | of Applications of Mathematics[END_REF], [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF] for stochastic gradient descents and [START_REF] Bercu | An efficient stochastic newton algorithm for parameter estimation in logistic regressions[END_REF] for an example of stochastic Newton algorithm). The following corollary gives the almost sure convergence of the estimates of L(θ).

Corollary 3.1. Under assumptions (H1) to (H3), on Γ θ , the following almost sure convergences hold:

S n a.s ----→ n→+∞ H and S -1 n a.s ----→ n→+∞ H -1 .
In order to get the rates of convergence of the estimates (θ n ), let us first introduce a new assumption:

(H5) There are positive constants η, C η such that η > 1 α -1 and for all h ∈ R q , E ∇ h g (X, Y, h) 2η+2 ≤ C η .
Theorem 3.2. Assume assumptions (H1) to (H4a) and (H5) hold. Then, on Γ θ ,

θ n -θ 2 = O ln n n α a.s. (11)
Besides, adding assumption (H4b), assuming that the function L is C f -Lipschitz on a neighborhood of θ, and that the function h

-→ E ∇ h g (X, Y, h) ∇ h g (X, Y, h) T is C g -Lipschitz on a neighbor- hood of θ, then on Γ θ , n α c α (θ n -θ) L ----→ n→+∞ N 0, σ 2 2 L(θ) -1 (12)
These are quite usual results for a step sequence of order n -α . Indeed, as expected, we have a "loss" on the rate of convergence of (θ n ), but the averaged step enables to get an asymptotically optimal behaviour, which is given by the following theorem.

Theorem 3.3. Assuming (H1) to (H4a) together with (H5), on Γ θ ,

θ n -θ 2 = O ln n n a.s. Moreover, suppose that the function h -→ E ∇ h g (X, Y, h) ∇ h g (X, Y, h) T is continuous at θ, then on Γ θ , √ n θ n -θ L ----→ n→+∞ N 0, σ 2 L(θ) -1 .
Corollary 3.2. Assuming (H1) to (H5) and assuming that the functional L is C f -Lipschitz on a neighborhood of θ, then on Γ θ , for all δ > 0,

S n -H 2 F = O max c 2 β n 2β , (ln n) 1+δ n a.s, S -1 n -H -1 2 F = O max c 2 β n 2β , (ln n) 1+δ n a.s.
Recall here that if (H*) holds, then one can take c β = 0 leading to a rate of convergence of order 1 n (up to a log term).

Convergence results on the Stochastic Gauss-Newton algorithm

Theorem 3.4. Assume assumptions (H1) to (H5) hold. Then, on

Γ θ := ω ∈ Ω, θ n (ω) a.s ----→ n→+∞ θ , θn -θ 2 = O ln n n a.s. Moreover, suppose that the functional h -→ E ∇ h g (X, Y, h) ∇ h g (X, Y, h) T is continuous at θ, then on Γ θ , √ n θ n -θ L ----→ n→+∞ N 0, σ 2 L(θ) -1 .

Estimating the variance σ 2

We now focus on the estimation of the variance σ 2 of the errors. First, consider the sequence of predictors Ŷn n≥1 of Y defined for all n ≥ 1 by

Ŷn = f X n , θ n-1 .
Then, one can estimate σ 2 by the recursive estimate σn defined for all n ≥ 1 by

σn = 1 n n ∑ k=1 Ŷk -Y k 2 .
Corollary 3.3. Assume assumptions (H1) to (H5) hold and that admits a 4-th order moment. Then, on Γ θ ,

σ2 n -σ 2 = O ln n n a.s., and √ n σ2 n -σ 2 L ----→ n→+∞ N 0, V 2 .

Simulation study

In this section, we present a short simulation study to illustrate convergence results given in Section 3. Simulations were carried out using the statistical software .

The model

Consider the following model

Y = θ 1 (1 -exp(-θ 2 X)) + , with θ = (θ 1 , θ 2 ) T = (21, 12) T , X ∼ U ([0, 1]
), and ∼ N (0, 1). For sure, this model is very simple. However, it allows us to explore the behaviour of the different algorithms presented in this paper by comparing our methods with the stochastic gradient algorithm and its averaged version and by looking at the influence of the step sequence on the estimates. In that special case, matrix L(θ) = ∇ 2 G(θ) is equal to:

L(θ) = E (1 -exp (-θ 2 X)) 2 θ 1 X (1 -exp (-θ 2 X)) exp (-θ 2 X) θ 1 X (1 -exp (-θ 2 X)) exp (-θ 2 X) θ 2 1 X 2 exp (-2θ 2 X)
.

Then, taking θ = (21, 12) T , we obtain L(21, 12) 0.875 0.109 0.109 0.063 and in particular, the eigenvalues are about equal (in decreasing order) to 0.889 and 0.049.

Comparison with stochastic gradient algorithm and influence of the stepsequence

To avoid some computational problems, we consider projected versions of the different algorithms: more precisely, each algorithm is projected on the ball of center (21, 12) T and of radius 12.

For each algorithm, we calculate the mean squared error based on 100 independent samples of size n = 10 000, with initialization θ 0 = θ + 10U, where U follows an uniform law on the unit sphere of R 2 .

We can see in Tables 1 and2 that Gauss-Newton methods perform globally better than gradient descents. This is certainly due to the fact that the eigenvalues of L(θ) are at quite different scales, so that the step sequence in gradient descent is less adapted to each direction. Remark that we could have been less fair play, considering an example where the eigenvalues of L(θ) would have been at most sensitively different scales. Nevertheless, without surprise, the estimates seem to be quite sensitive to the choices of the parameters c α and α. and its averaged version (on the right) for different parameters α and c α , for n = 10 000.

To complete this study, let us now examine the behaviour of the mean squared error in function of the sample size for the standard Stochastic Gauss-Newton algorithm ("SN"), and its averaged version ("ASN"), for the Stochastic Gauss-Newton algorithm defined by (9) ("ND") and for the stochastic gradient algorithm ("SGD") as well as its averaged version ("ASGD"). The stochastic Gauss-Newton algorithms, has been computed with c β = 0 and S 0 = I 2 . For the averaged stochastic Newton algorithm a step sequence of the form c α n -α with c α = 1 and α = 0.66 has been chosen, while we have taken c α = 5 and α = 0.66 for the stochastic gradient algorithm and its averaged version. Finally, we have considered three different initializations: θ 0 = θ + r 0 Z, where Z follows an uniform law on the unit sphere of R 2 and r 0 = 1, 5, 12. One can see in Figure 1 that stochastic Gauss-Newton algorithms perform better than gradient descents and their averaged version for quite good initialization. As explained before, this is due to the fact that stochastic Gauss-Newton methods enable to adapt the step sequence to each direction. Furthermore, one can see that when we have a quite good initialization, Stochastic Gauss-Newton and the averaged version give similar results. Nevertheless, when we deal with a bad initialization, to take a step sequence of the form c α n -α enables the estimates to move faster, so that the averaged Gauss Newton estimates have better results compare to the non averaged version. Finally, on Figure 2, one can see that Gauss-Newton methods globally perform better than gradient methods, but there are some bad trajectories due to bad initialization.

q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q ND SN ASN SG ASG 0 20 40 60 80 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q ND SN ASN SG ASG 0.00 0.04 0.08

Figure 2: Mean squared errors for the different methods for n = 10 000 and r 0 = 12.

Influence of β n

We now focus on the influence of β n on the behaviour of the estimates. All the results are calculated from 100 independent samples of size n. In table 3, we have chosen c α = 0.66 and c = 1, and initialize the algorithms taking θ 0 = θ + 5U. Choosing small c β leads to goods results, which, without surprise, suggests that the use of the term

∑ n k=1 β k Z k Z T k is only theoretical, but

Asymptotic efficiency

We now illustrate the asymptotic normality of the estimates. In order to consider all the components of parameter θ, we shall in fact examine the two following central limit theorem.

C n := θ n -θ T H n θ n -θ L ----→ n→+∞ χ 2 2 and C n := θ n -θ T S n θ n -θ L ----→ n→+∞ χ 2 2 .
These two results are straightforward applications of Theorems 3.3 and 3.4, taking σ 2 = 1.

From 1000 independent samples of size n, and using the kernel method, we estimate the probability density function (pdf for short) of C n and C n that we compare to the pdf of a chi-squared with 2 degrees of freedom (df). Estimates θ n and θ n are computed taking

θ 0 = θ + U, c α = 1 and α = 0.66.
One can observe in Figure 3 that the estimated densities are quite similar to the chisquared pdf. Remark that a Kolmogorov-Smirnov test leads to p-values equal to 0.1259 for C n and 0.33 for C n . Therefore, the gaussian approximation provided by the TLC given by 3.3 and 3.4 is pretty good, and so, even for quite moderate sample sizes.

λ max S -1 n = O n β-1 a.s and λ max (S n ) = O(n) a.s.
Proof of Lemma 5.1. First, note that

λ min (S n ) ≥ λ min n ∑ i=1 c β i β Z i Z T i ,
and one can check that 1

∑ n i=1 c β i β n ∑ i=1 c β i β Z i Z T i a.s ----→ n→+∞ I q . Since n ∑ i=1 c β i β ∼ c β 1 -β n 1-β , it comes λ max S -1 n = O n β-1 a.s.
Let us now give a bound of λ max (S n ). First, remark that S n can be written as

S n = S 0 + n ∑ i=1 E Φ i Φ T i |F i-1 + ∑ i=1 Ξ i + n ∑ i=1 c β i β Z i Z T i ,
where

Ξ i := Φ i Φ T i -E Φ i Φ T i |F i-1 and (F i )
is the σ-algebra generated by the sample, i.e F i := σ ((X 1 , Y 1 ) , . . . , (X i , Y i )). Thanks to assumption (H1b),

E Φ i Φ T i 2 F |F i-1 ≤ C ,
and applying Theorem 6.2, it comes for all positive constant δ > 0,

n ∑ i=1 Ξ i 2 F = o n(ln n) 1+δ a.s,
where . F is the Frobenius norm. Then,

S n F = O max S 0 F , C n, n(ln n) 1+δ , n 1-β a.s,
which concludes the proof.

Proof of Theorem 3.1. With the help of a Taylor's decomposition, it comes

G (θ n+1 ) = G (θ n ) + ∇G (θ n ) T (θ n+1 -θ n ) + 1 2 (θ n+1 -θ n ) T 1 0 ∇ 2 G (θ n+1 + t (θ n+1 -θ n )) dt (θ n+1 -θ n ) .
Then, assumption (H2) yields

G (θ n+1 ) ≤ G (θ n ) + ∇G (θ n ) T (θ n+1 -θ n ) + C 2 θ n+1 -θ n 2 .
Replacing θ n+1 ,

G (θ n+1 ) ≤ G (θ n ) -γ n+1 ∇G (θ n ) T S -1 n ∇ h g (X n+1 , Y n+1 , θ n ) + C 2 γ 2 n+1 S -1 n ∇ h g (X n+1 , Y n+1 , θ n ) 2 ≤ G (θ n ) -γ n+1 ∇G (θ n ) T S -1 n ∇ h g (X n+1 , Y n+1 , θ n ) + C 2 γ 2 n+1 λ max S -1 n 2 ∇ h g (X n+1 , Y n+1 , θ n ) 2 .
Assumption (H1a) leads to

E [G (θ n+1 ) |F n ] ≤ G (θ n ) -γ n+1 ∇G (θ n ) T S -1 n ∇G (θ n ) + CC 2 γ 2 n+1 λ max S -1 n 2 ≤ G (θ n ) -γ n+1 λ min S -1 n ∇G (θ n ) 2 + CC 2 γ 2 n+1 λ max S -1 n 2 .
Thanks to Lemma 5.1, and since

β < α -1/2, ∑ n≥1 γ 2 n+1 λ max S -1 n 2 < +∞ a.s,
so that, applying Robbins-Siegmund Theorem (see [START_REF] Duflo | of Applications of Mathematics[END_REF] for instance), G (θ n ) con- verges almost surely to a finite random variable and

∑ n≥1 γ n+1 λ min S -1 n ∇G (θ n ) 2 = ∑ n≥1 γ n+1 λ max S n -1 ∇G (θ n ) 2 < +∞ a.s.
Lemma 5.1 implies ∑ n≥1 γ n+1 λ max S n -1 = +∞ almost surely, so that there is alsmot surely a subsequence θ ϕ n such that ∇G θ ϕ n 2 converges to 0.

Proof of Corollary 3.1. Let us give the convergence of each term in decomposition (5.1). Since β > 0 and applying (5.1), it comes

1 n n ∑ i=1 Ξ i F a.s ----→ n→+∞ 0 a.s and 1 n n ∑ i=1 c β i β Z i Z T i F a.s ----→ n→+∞ 0 a.s.
Finally, since θ n converges almost surely to θ, assumption (H3) together with Toeplitz lemma

yield 1 n n ∑ i=1 E Φ i Φ T i |F i-1 a.s ----→ n→+∞ E ∇ h f (X, θ) ∇ h f (X, θ) T = L(θ).

Proof of Theorem 3.2

First, θ n+1 can be written as

θ n+1 -θ = θ n -θ -γ n+1 S -1 n ∇G (θ n ) + γ n+1 S -1 n ξ n+1 , (13)
with ξ n+1 := ∇G (θ n ) -∇ h g (X n+1 , Y n+1 , θ n ). Remark that (ξ n ) is a sequence of martingale differences adapted to the filtration (F n ). Moreover, linearizing the gradient and noting H = ∇ 2 G(θ), it comes

θ n+1 -θ = θ n -θ -γ n+1 S -1 n H (θ n -θ) + γ n+1 S -1 n ξ n+1 -γ n+1 S -1 n δ n = (1 -γ n+1 ) (θ n -θ) + γ n+1 H -1 -S -1 n H (θ n -θ) + γ n+1 S -1 n ξ n+1 -γ n+1 S -1 n δ n , ( 14
)
where

δ n = ∇G (θ n ) -H (θ n -θ)
is the remainder term in the Taylor's decomposition of the gradient. By induction, one can check that for all n ≥ 1,

θ n -θ = β n,0 (θ 0 -θ) + n-1 ∑ k=0 β n,k+1 γ k+1 H -1 -S -1 k H (θ k -θ) - n-1 ∑ k=0 β n,k+1 γ k+1 S -1 k δ k + n-1 ∑ k=0 β n,k+1 γ k+1 S -1 k ξ k+1 ,
with, for all k, n ≥ 0 and k ≤ n,

β n,k = n ∏ j=k+1 1 -γ j and β n,n = 1.
Applying Theorem 6.1,

n-1 ∑ k=0 β n,k+1 γ k+1 S -1 k ξ k+1 2 = O ln n n α a.s. (15)
We can now prove Theorem 3.2.

Proof of equation 11. The aim is to give the rate of convergence of each term of decomposition (5.2). The rate of the martingale term is given by equation ( 15). Remark that there is a rank n α such that for all n ≥ n α , we have γ n ≤ 1, so that, for all n ≥ n α ,

β n,0 (θ 0 -θ) ≤ θ 0 -θ n α -1 ∏ i=1 |1 -γ i+1 | ∏ i=n α (1 -γ i+1 ) ≤ θ 0 -θ n α -1 ∏ i=1 |1 -γ i+1 | exp - n ∑ i=n α γ i+1 .
Since α < 1, this term converges at an exponential rate, and more precisely

β n,0 (θ 0 -θ) = O exp - c α 1 -α n 1-α a.s.
Let us denote

∆ n := n-1 ∑ k=0 β n,k+1 γ k+1 H -1 -S -1 k H (θ k -θ) - n ∑ k=0 β n,k+1 γ k+1 S -1 k δ k .
The aim is so to prove that this term is negligible. First, remark that the Taylor's decomposition of the gradient yields

δ n = 1 0 ∇ 2 G (θ + t (θ n -θ)) -H (θ n -θ) dt,
and thanks to assumption (H4a), since θ n converges almost surely to θ and by dominated convergence,

δ n ≤ θ n -θ 1 0 ∇ 2 G (θ + t (θ n -θ)) -H op dt = o ( θ n -θ ) a.s
In a similar way, since S -1

n converges almost surely to H -1 , H -1 -S -1 n H (θ n -θ) = o ( θ n -θ ) a.s.
Moreover, since

∆ n+1 = (1 -γ n+1 ) ∆ n + γ n+1 H -1 -S -1 n H (θ n -θ) -γ n+1 S -1 n δ n ,
we have,

∆ n+1 ≤ |1 -γ n+1 | ∆ n + o n -α θ n -θ a.s ≤ |1 -γ n+1 | ∆ n + o n -α ∆ n + n-1 ∑ k=0 β n,k+1 γ k+1 S -1 k ξ k+1 + β n,0 (θ 0 -θ) a.s.
Then, since β n,0 (θ 0θ) converges at an exponential rate to 0 and thanks to equation ( 15),

∆ n+1 ≤ (1 -γ n+1 ) ∆ n + o γ n+1 ln n n α + γ n+1 ∆ n a.s,
and applying a stabilization Lemma (see [START_REF] Duflo | of Applications of Mathematics[END_REF] for instance),

∆ n = O ln n n α a.s
which concludes the proof.

Proof of equation ( 12). In order to get the asymptotic normality, we will apply the Central Limit Theorem in [START_REF] Jakubowski | Tightness criteria for random measures with application to the principle of conditioning in Hilbert spaces[END_REF] to the martingale term in decomposition (5.2) and prove that other terms of this decomposition are negligible. The rate of convergence of the first term on the right-hand side of equality (5.2) is given by equality (5.2). Moreover, applying Theorem 3.2 and Remark 5.1 as well as Lemma E.2 in [START_REF] Cardot | Fast estimation of the median covariation matrix with application to online robust principal components analysis[END_REF], one can check that for all δ > 0,

n-1 ∑ k=0 β n,k+1 γ k+1 H -1 -S -1 k H (θ k -θ) 2 = o (ln n) 1+δ n α+β a.s,
and this term is so negligible. In the same way,

n-1 ∑ k=0 β n,k+1 γ k+1 S -1 k δ k 2 = o (ln n) 2+δ n 2α a.s.
Note that the martingale term can be written as

n-1 ∑ k=0 β n,k+1 γ k+1 S -1 k ξ k+1 = n-1 ∑ k=0 β n,k+1 c α γ k+1 S -1 k -H -1 ξ k+1 + n-1 ∑ k=0 β n,k+1 γ k+1 H -1 ξ k+1 .
Applying Theorem 6.1 and Remark 5.1,

n ∑ k=0 β n+1,k+1 γ k+1 S -1 k -H -1 ξ k+1 2 = O ln n n α+2β a.s.
Finally, let us now prove that the martingale term verifies assumption in [START_REF] Jakubowski | Tightness criteria for random measures with application to the principle of conditioning in Hilbert spaces[END_REF],

i.e that we have ∀ν > 0, lim

n→+∞ P sup 0≤k≤n n α c α β n+1,k+1 c α (k + 1) -α H -1 ξ k+1 > ν = 0. n α c α n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 H -1 ξ k+1 ξ T k+1 H -1 a.s ----→ n→+∞ 1 2 σ 2 H -1 .
Proof of equation ( 5.2): Thanks to assumption (H5), one can check that for all n ≥ 1,

E ξ n+1 2+2η |F k ≤ 2 2+2η C η
Then, applying Markov's inequality,

P sup 0≤k≤n n α c α β n+1,k+1 γ k+1 H -1 ξ k+1 > ν ≤ n ∑ k=0 P n α c α β n+1,k+1 γ k+1 H -1 ξ k+1 > ν ≤ n ∑ k=0 P ξ k+1 > √ c α ν n α/2 |β n+1,k+1 | γ k+1 H -1 op ≤ c 1+η α H -1 2+2η op ν 2+2η 2 2+2η C η n α(1+η) n ∑ k=0 |β n+1,k+1 | 2+2η k -2α(1+η) .
Moreover, note that there is a rank n α such that for all j ≥ n α we have c α j -α ≤ 1. For the sake of readibility of the proof (in other way, one can split the sum into two parts as in the proof of Lemma 3.1 in Cardot et al. ( 2017)), we consider from now on that n α = 1. Then

|β n+1,k+1 | = n+1 ∏ i=k+2 1 -c α i -α ≤ exp -c α n+1 ∑ i=k+2 i -α .
Applying Lemma E.2 in [START_REF] Cardot | Fast estimation of the median covariation matrix with application to online robust principal components analysis[END_REF], it comes

n ∑ k=0 |β n+1,k+1 | 2+2η k -2α(1+η) = O n -α-2αη ,
and so

lim n→+∞ c 1+η α H -1 2+2η op ν 2+2η 2 2+2η C η n α(1+η) n ∑ k=0 |β n+1,k+1 | k -2α(1+η) = 0.
Proof of equation (5.2): First, note that

n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 H -1 ξ k+1 ξ T k+1 H -1 = n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 H -1 E ξ k+1 ξ T k+1 |F k H -1 + n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 H -1 Ξ k+1 H -1 , with Ξ k+1 = ξ k+1 ξ T k+1 -E ξ k+1 ξ T k+1 |F k . (Ξ k
) is a sequence of martingale differences adapted to the filtration (F k ). Applying Theorem 6.1, it comes

n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 H -1 Ξ k+1 H -1 2 = O ln n n 3α a.s. Moreover, note that n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 H -1 E ξ k+1 ξ T k+1 |F k H -1 = - n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 H -1 ∇G (θ k ) ∇G (θ k ) T H -1 + n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 H -1 E ∇ h g (X k+1 , Y k+1 , θ k ) ∇ h g (X k+1 , Y k+1 , θ k ) T |F k H -1 .
Applying Theorem 3.2, equality (5.2) and Lemma E.2 in [START_REF] Cardot | Fast estimation of the median covariation matrix with application to online robust principal components analysis[END_REF], since the gradient of G is Lipschitz, one can check that for all δ > 0,

n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 H -1 ∇G (θ k ) ∇G (θ k ) T H -1 2 F = o (ln n) 1+δ n 2α a.s.
Moreover, noting

R k = E ∇ h g (X k+1 , Y k+1 , θ k ) ∇ h g (X k+1 , Y k+1 , θ k ) T |F k -E ∇ h g (X k+1 , Y k+1 , θ) ∇ h g (X k+1 , Y k+1 , θ) T |F k , n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 H -1 E ∇ h g (X k+1 , Y k+1 , θ k ) ∇ h g (X k+1 , Y k+1 , θ k ) T |F k H -1 = n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 H -1 R k H -1 + n ∑ k=1 β 2 n+1,k+1 γ 2 k+1 H -1 E ∇ h g (X k+1 , Y k+1 , θ) ∇ h g (X k+1 , Y k+1 , θ) T |F k H -1
Moreover, applying Theorem 3.2, Lemma E.2 in [START_REF] Cardot | Fast estimation of the median covariation matrix with application to online robust principal components analysis[END_REF], one chan check that for all δ > 0,

n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 H -1 R k H -1 F = o (ln n) 1+δ n 2α a.s. Furthermore, since E ∇ h g (X k+1 , Y k+1 , θ) ∇ h g (X k+1 , Y k+1 , θ) T |F k = σ 2 H, applying Lemma A.1 in Godichon-Baggioni (2019), lim n→∞ H -1 n α c α n ∑ k=0 β 2 n+1,k+1 γ 2 k+1 E ∇ h g (X k+1 , Y k+1 , θ) ∇ h g (X k+1 , Y k+1 , θ) T |F k - 1 2 σ 2 H H -1 F = 0,
which concludes the proof.

Proof of Theorem 3.3

Let us first give some decompositions of the averaged estimates. First, note that

θ n = 1 n + 1 n ∑ k=0 θ k .
Second, one can write decomposition (5.2) as

θ n -θ = H -1 S n (θ n -θ) -(θ n+1 -θ) γ n+1 + H -1 ξ n+1 -H -1 δ n .
Then, summing these equalities and dividing by n + 1, it comes

θ n -θ = H -1 1 n + 1 n ∑ k=0 S k (θ k -θ) -(θ k+1 -θ) γ k+1 + H -1 1 n + 1 n ∑ k=0 ξ k+1 -H -1 1 n + 1 n ∑ k=0 δ k .
Proof of Theorem 3.3. Let us give the rate of convergence of each term on the right-hand side of equality (5.3). First, in order to apply a Law of Large Numbers and a Central Limit Theorem for martingales, let us calculate

lim n→∞ 1 n + 1 n ∑ k=0 E ξ k+1 ξ T k+1 |F k .
By definition of (ξ n ), it comes

1 n + 1 n ∑ k=0 E ξ k+1 ξ T k+1 |F k = 1 n + 1 n ∑ k=0 E ∇ h g (X k+1 , Y k+1 , θ k ) ∇ h g (X k+1 , Y k+1 , θ k ) T |F k - 1 n + 1 n ∑ k=0 ∇G (θ k ) ∇G (θ k ) T .
By continuity and since θ k converges amost surely to θ, Toeplitz lemma implies

1 n + 1 n ∑ k=0 E ξ k+1 ξ T k+1 |F k a.s ----→ n→+∞ E ∇ h g (X, Y, θ) ∇ h g (X, Y, θ) T .
Furthermore,

E ∇ h g (X, Y, θ) ∇ h g (X, Y, θ) T = E 2 ∇ h f (X, Y, θ) ∇ h f (X, Y, θ) T = σ 2 H.
Finally, since E ξ n+1 2+2η |F n ≤ 2 2+2η C η , applying a Law of Large Numbers for martingales (see [START_REF] Duflo | of Applications of Mathematics[END_REF]),

1 (n + 1) 2 H -1 n ∑ k=0 ξ k+1 2 = O ln n n a.s.
Moreover, applying a Central Limit Theorem for martingales (see [START_REF] Duflo | of Applications of Mathematics[END_REF]),

1 √ n H -1 n ∑ k=0 ξ k+1 L ----→ n→+∞ N 0, σ 2 H -1 .
Let us now prove that other terms on the right-hand side of equality (5.3) are negligible.

Thanks to assumption (H4b) and since θ n converges almost surely to θ,

δ n ≤ θ n -θ 1 0 ∇ 2 G (θ + t (θ n -θ)) -H op dt = O θ n -θ 2 a.s
Then applying Theorem 3.2, for all δ > 0,

1 n + 1 H -1 n ∑ k=0 δ k ≤ H -1 op n + 1 n ∑ k=1 δ k = o (ln n) 1+δ n α a.s
and since α > 1/2, this term is negligible. Finally, as in [START_REF] Pelletier | Asymptotic almost sure efficiency of averaged stochastic algorithms[END_REF], using an Abel's transform,

1 n + 1 n ∑ k=0 S k (θ k -θ) -(θ k+1 -θ) c α (k + 1) -α = - S n+1 (θ n+1 -θ) (n + 1)γ n+2 + S 0 (θ 0 -θ) (n + 1)γ 1 - 1 n + 1 n+1 ∑ k=1 γ -1 k S k-1 -γ -1 k+1 S k (θ k -θ) .
Let us now give the rates of convergence of each term on the right-hand side of equality (5.3). First, applying Theorem 3.2 and since S n converges almost surely to H,

S n+1 (θ n+1 -θ) γ n+2 (n + 1) 2 = O ln n n 2-α a.s and S 0 (θ 0 -θ) (n + 1)γ 1 2 = O 1 n 2 a.s
and these terms are negligible since α < 1. Furthermore, since

S k = S k-1 - 1 k S k-1 + 1 k Φ k Φ T k + c β k β Z k Z T k , it comes ( * ) : = 1 n + 1 n+1 ∑ k=1 γ k S k-1 -γ k+1 S k (θ k -θ) = 1 n + 1 n+1 ∑ k=1 γ -1 k -γ -1 k+1 S k-1 (θ k -θ) - 1 n + 1 n+1 ∑ k=1 γ -1 k+1 k S k-1 (θ k -θ) + 1 n + 1 n+1 ∑ k=1 γ -1 k+1 k Φ k Φ T k + c β k β Z k Z T k (θ k -θ) :=( * * )
.

For the first term on the right-hand side of previous equality, since

γ -1 k -γ -1 k+1 ≤ αc -1 α k α-1
and since S k-1 converges almost surely to H, applying Theorem 3.2, for all δ > 0,

1 (n + 1) 2 n+1 ∑ k=1 γ -1 k -γ -1 k+1 S k-1 (θ k -θ) 2 = o (ln n) 1+δ n 2-α a.s
which is negligible since α < 1. Furthermore, since S k-1 converges almost surely to H, one can check that

1 (n + 1) 2 n ∑ k=1 γ -1 k+1 k S k-1 (θ k -θ) 2 = o (ln n) 1+δ n 2-α a.s.
Let us now give the rate of convergence of ( * * ). In this aim, let us consider δ > 0 and introduce the events

Ω k = θ k -θ ≤ (ln k) 1/2+δ k α/2
. Since δ > 0, and thanks to Theorem 3.2,

θ n -θ 2 n α (ln n) 1+δ converges almost surely to 0, so that 1 Ω C k converges almost surely to 0. Further- more, ( * * ) = 1 n + 1 n+1 ∑ k=1 γ -1 k+1 k Φ k Φ T k + c β k β Z k Z T k (θ k -θ) 1 Ω k :=( * * * ) + 1 n + 1 n+1 ∑ k=1 γ -1 k+1 k Φ k Φ T k + c β k β Z k Z T k (θ k -θ) 1 Ω C k Since 1 Ω C k converges almost surely to 0, ∑ k≥1 γ -1 k+1 k Φ k Φ T k + c β k β Z k Z T k θ k -θ op 1 Ω C k < +∞ a.s so that 1 n + 1 n+1 ∑ k=1 γ -1 k+1 k Φ k Φ T k + c β k β Z k Z T k (θ k -θ) 1 Ω C k = O 1 n a.s.
Moreover,

( * * * ) ≤ 1 n + 1 n+1 ∑ k=1 γ -1 k+1 k Φ k Φ T k + c β k β Z k Z T k op (ln k) 1/2+δ k α/2 .
One can consider the sequence of martigales differences (Ξ k ) adapted to the filtration (F k ) and defined for all k ≥ 1 by

Ξ k = Φ k Φ T k + c β k β Z k Z T k op -E Φ k Φ T k + c β k β Z k Z T k op |F k-1 .
Then,

( * * * ) ≤ 1 n + 1 n+1 ∑ k=1 γ k+1 (ln k) 1/2+δ k α/2+1 E Φ k Φ T k + c β k β Z k Z T k op |F k-1 + 1 n + 1 n+1 ∑ k=1 γ k+1 (ln k) 1/2+δ k α/2+1 Ξ k .
Then, thanks to Assumption (H1b) and Toeplitz lemma,

1 n + 1 n+1 ∑ k=1 γ k+1 (ln k) 1/2+δ k α/2+1 E Φ k Φ T k + c β k β Z k Z T k op |F k-1 = o (ln n) 1/2+δ n 1-α/2 a.s.
Furthermore, since α < 1, with assumption (H1b), Theorem 6.2 leads to

1 n + 1 n+1 ∑ k=1 γ k+1 (ln k) 1/2+δ k α/2+1 Ξ k 2 = O 1 n 2 a.s.

Proof of Corollary 3.2

Proof. The aim is to give the rate of convergence of each term of decomposition (5.1). Note that the rate of the martingale term is given by (5.1), while, thanks to equation (5.1), we

have 1 n 2 n ∑ k=1 c β k β Z k+1 Z T k+1 2 F = O 1 n 2β a.s.
Finally, since the functional h -→ E ∇ h f (X, h) ∇ h f (X, h) T is C f -Lipschitz on a neighborhood of θ and since θ n converges almost surely to θ, applying Theorem 3.3 as well as Toeplitz lemma, for all δ > 0,

1 n 2 n ∑ k=1 E Φ k+1 Φ T k+1 |F k -H 2 F = O   C 2 f n 2 n ∑ k=1 θ k -θ 2   a.s = o (ln n) 1+δ n a.s,
which concludes the proof.

Remark 5.1. Note that to prove equality (12) without knowing the rate of convergence of θ n , it is necessary to have a first rate of convergence of S n . For that purpose, we study the asymptotic behaviour of

1 n 2 n ∑ k=1 E Φ k+1 Φ T k+1 |F k -H 2 F .
Equality (11) yields for all δ > 0,

θ n -θ ≤ 1 n + 1 n ∑ k=0 θ k -θ = O (ln n) 1/2+δ/2 n α/2 , so that, since the functional h -→ E ∇ h f (X, h) ∇ h f (X, h) T is C f -Lipschitz on a neighborhood of θ, 1 n 2 n ∑ k=1 E Φ k+1 Φ T k+1 |F k -H 2 F = O   C 2 f n 2 n ∑ k=1 θ k -θ 2   a.s = o (ln n) 1+δ n α a.s,
and then, since

β < α -1/2, S n -H F = O max c β n β , (ln n) 1+δ n α a.s

Proof of Theorem 3.4

Only the main lines of the proof are given since it is a mix between the proof of Theorem 3.3 and the ones in [START_REF] Bercu | An efficient stochastic newton algorithm for parameter estimation in logistic regressions[END_REF].

Proof of THeorem 3.4. Let us denote

H -1 n = (n + 1) H -1 n .
First, remark that as in the proof of Corollary 3.2, one can check that that on Γ θ ,

H n a.s ----→ n→+∞ H and H -1 n a.s ----→ n→+∞ H -1 .
Furthermore, decomposition (13) can be rewritten as

θ n+1 = θ n -θ - 1 n + 1 S -1 n ∇G θ n + 1 n + 1 H -1 n ξ n+1 ,
where ξ n+1 := ∇G θ n -∇ h g X n+1 , Y n+1 , θ n . Then, ξ n is a sequence of martingale differences adapted to the filtration (F n ). Linearizing the gradient, decomposition ( 14) can be rewritten as

θ n+1 -θ = n n + 1 θ n -θ + 1 n + 1 H -1 -H -1 n H θ n -θ + 1 n + 1 H -1 n ξ n+1 - 1 n + 1 H -1 n δ n
where δ n = ∇G θ n -H θ nθ is the reminder term in the Taylor's decomposition of the gradient. Then, by induction, it comes

θ n -θ = 1 n θ 0 -θ + 1 n n-1 ∑ k=0 H -1 -H -1 k H θ k -θ - 1 n n-1 ∑ k=0 H -1 k δ k + 1 n n-1 ∑ k=0 H -1 k ξ k+1 . ( 16
) Since H -1 k converges almost surely to H -1 , on Γ θ , one can check that 1 n n-1 ∑ k=0 H -1 k ξ k+1 ξ T k+1 H -1 k a.s ----→ n→+∞ σ 2 H -1 .
Thanks to assumption (H5), applying a law of large numbers for martingales, one can check

that 1 n n-1 ∑ k=0 H -1 k ξ k+1 2 = O ln n n a.s (17)
In the same way, applying a central limit theorem, it comes

1 √ n n-1 ∑ k=0 H -1 k ξ k+1 L ----→ n→+∞ N 0, σ 2 H -1 .
Let us now prove that the other terms in decomposition ( 16) are negligible. First, clearly

1 n θ 0 -θ = O 1 n a.s. (18)
Furthermore, let us denote

∆ n = 1 n n-1 ∑ k=0 H -1 -H -1 k H θ k -θ - 1 n n-1 ∑ k=0 H -1 k δ k .
Furthermore, as in the proof of Theorem 3.2, one can verify

H -1 -H -1 n H θ n -θ = o θ n -θ a.s δ n = o θ n -θ a.s Then, ∆ n+1 = n n + 1 ∆ n + o θ n -θ a.s.
As in the proof of Theorem 6.2 in [START_REF] Bercu | An efficient stochastic newton algorithm for parameter estimation in logistic regressions[END_REF] (see equations (6.24) to (6.32)), it comes

∆ n 2 = O ln n n a.s. (19)
Then, thanks to equalities (17),( 18) and ( 19), it comes

θ n -θ 2 = O ln n n a.s. (20)
In order to get the asymptotic normality of θ n , let us now give the rate of convergence of each term on the right-hand side of decomposition (16). First, since

δ n = O θ n -θ 2 a.s,
and since H -1

n converges almost surely to H -1 , thanks to equality (20), for all δ > 0

1 n n-1 ∑ k=0 H -1 k δ k = o (ln n) 2+δ n a.s
which is so negligible. Furthermore, as in the proof of Corollary 3.2, one can check that for all δ > 0,

H -1 n -H -1 2 = O max c 2 β n 2β , (ln n) 1+δ n a.s.
Then, for all δ > 0,

1 n n ∑ k=1 H -1 k -H -1 H θ k -θ = o max c β (ln n) 1/2+δ n β+1/2 , (ln n) 2+δ n a.s
and this term is no negligible.

Proof of Corollary 3.3

First, note that

Ŷk -Y k 2 -σ 2 = f X k , θ k-1 -f (X k , θ) 2 -2 k f X k , θ k-1 -f (X k , θ) + 2 k -σ 2 .
Thanks to a Taylor's decomposition, there are U 0 , . . . , U n-1 ∈ R q such that R

1 := 1 n n ∑ k=1 f X k , θ k-1 -f (X k , θ) 2 ≤ 1 n n ∑ k=1 ∇ h f (X k , U k-1 ) 2 θ k-1 -θ 2
Let us consider the filtration F

(1) n defined by F

(1) n

= σ ((X k , k-1 ) , k = 1, . . . , n). Then, considering ξ k = E ∇ h f (X k , U k-1 ) 2 |F (1) k-1 -∇ h f (X k , U k-1 ) 2 , it comes thanks to as- sumption (H1b), R 1 ≤ 1 n n ∑ k=1 √ C θ k-1 -θ 2 - 1 n n ∑ k=1 ξ k θ k-1 -θ 2
Then, applying Toeplitz Lemma and Theorem 3.3 to the term on the left hand-side of previous inequality, one can check that for all δ > 0,

1 n n ∑ k=1 √ C θ k-1 -θ 2 = o (ln n) 2+δ n a.s.
Furthermore, since ξ n is a sequence of martingale differences with bounded squared moments, with the help of Theorems 3.3 and 6.2, it comes

1 n n ∑ k=1 ξ k θ k-1 -θ 2 = O 1 n a.s so that R 1 = o (ln n) 2+δ n a.s.
Furthermore, let us consider

R 2 = 1 n n ∑ k=1 k f X k , θ k-1 -f (X k , θ) .
We have a sum of martingale differences, and thanks to Theorems 3.3 and 6.2, one can check that

R 2 2 = o (ln n) 2+δ n 2 a.s. Then, considering that 2 n -σ 2 = 2 n -E 2 n |F (1) n-1
one can apply a Central Limit Theorem for martingale to get the asymptotic normality, and a strong law of large numbers for martingales to get the almost sure rate of convergence.

6 Useful results on martingales 6.1 A useful theorem for stochastic algorithms with step sequence (n -α ) n Theorem 6.1. Let H be a separable Hilbert space and let us consider

M n+1 = n ∑ k=1 β n,k γ k R k ξ k+1 ,
where

• (ξ n ) is a H-valued martingale differences sequence adapted to a filtration (F n ) such that E ξ n+1 2 |F n ≤ C + R 2,n a.s, ∑ n≥1 γ n E ξ n+1 2 1 1 { ξ n+1 2 ≥γ -1 n (ln n) -1 } |F n < +∞ a.s, (21)
where C ≥ 0 and (R 2,n ) n converges almost surely to 0;

• γ n = cn -α with c > 0 and α ∈ (1/2, 1);

• (R n ) is a sequence of operators on H such that, for a deterministic sequence (v n ), R n op = o (v n ) a.s and v n = (ln n) a n b .
with a, b ≥ 0;

• For all n ≥ 1 and 1 ≤ k ≤ n,

β n,k = n ∏ j=k+1 (I H -γ k Γ) and β n,n = I H ,
where Γ is a symmetric operator on H such that 0 < λ min (Γ) ≤ λ max (Γ) < +∞.

≥ n R , R n op ≤ C R v n .
Proof. Let us now consider the events

A n = {R n > v n or R 2,n > C} B n+1 = {R n ≤ v n , R 2,n ≤ C, ξ n+1 ≤ δ n } C n+1 = {R n ≤ v n , R 2,n ≤ C, ξ n+1 > δ n } with δ n = γ -1/2 n (ln n) -1/2 . One can remark that A c n = B n+1 C n+1 . Then, one can write M n+1 as M n+1 = n ∑ k=1 β n,k γ k R k ξ k+1 1 1 {A k } + n ∑ k=1 β n,k γ k R k ξ k+1 1 1 {A c k } = n ∑ k=1 β n,k γ k R k ξ k+1 1 1 {A k } + n ∑ k=1 β n,k γ k R k ξ k+1 1 1 {B k+1 } -E ξ k+1 1 1 {B k+1 } |F k + n ∑ k=1 β n,k γ k R k ξ k+1 1 1 {C k+1 } -E ξ k+1 1 1 {C k+1 } |F k .
Let us now give the rates of convergence of these three terms.

Bounding M 1,n+1 := ∑ n k=1 β n,k γ k R k ξ k+1 1 1 {A k } . Remark that there is a rank n 0 such that for all n ≥ n 0 , I H -γ n Γ op ≤ (1 -λ min γ n ). Furthermore, M 1,n+1 = (I H -γ n Γ) M 1,n + γ n R n ξ n+1 1 1 {A n } . Then, for all n ≥ n 0 , E M 1,n+1 2 |F n ≤ (1 -λ min γ n ) 2 M 1,n 2 + γ 2 n R n 2 op (C + R 2,n ) 1 1 {A n } .
Considering V n+1 = ∏ n k=1 (1 + λ min γ k )2 M 1,n+1 2 , it comes (1 + λ min γ k ) -2 a.s and converges exponentially fast.

E [V n+1 |F n ] ≤ 1 -λ 2 min γ 2 n 2 V n + n ∏ k=1 (1 + λ min γ k ) 2 γ 2 n R n
Bounding M 2,n+1 := ∑ n k=1 β n,k γ k R k ξ k+1 1 1 {B k+1 } -E ξ k+1 1 1 {B k+1 } |F k . Let us denote Ξ k+1 = R k ξ k+1 1 1 {B k+1 } -E ξ k+1 1 1 {B k+1 } |F k .
Remark that (Ξ n ) is a sequence of martin- gale differences adapted to the filtration (F n ). As in Pinelis (1994) (proofs of Theorems 3.1 and 3.2), let λ > 0 and consider for all t ∈ [0, 1] and j ≤ n,

ϕ(t) = E cosh λ j-1 ∑ k=1 β n,k γ k Ξ k+1 + tβ n,j γ j Ξ j+1 F j .
One can check that ϕ (0) = 0 and (see Pinellis for more details) ϕ (t) ≤ λ 2 E β n,j γ j Ξ j+1 2 e λt β n,j γ j Ξ j+1 cosh λ with e j,n = E e λ β n,j γ j Ξ j+1 -1λ β n,j γ j Ξ j+1 |F j , which is well defined since Ξ j+1 is a.s. finite. Moreover, considering Then, recalling that δ n = γ -1/2 n (ln n) -1/2 , and since for all k ≥ 2,

G n+1 = cosh (λ ∑ n k=1 β n,k γ k Ξ k+1 ) ∏ n j=1 1 + e j,
E j+1 k |F j ≤ 2 k-2 δ k-2 j E ξ j+1 2 1 1 {B j } |F j ≤ 2 k-1 Cδ k-2 j , e j,n = ∞ ∑ k=2 λ k β n,j k op γ k j E Ξ j+1 k |F j ≤ ∞ ∑ k=2 λ k β n,j k op γ k j v k j E j+1 k |F k ≤ ∞ ∑ k=2 λ k β n,j k op γ k j v k j 2 k-1 Cδ k-2 j ≤ 2Cλ 2 β n,j 2 op γ 2 j v 2 j ∞ ∑ k=2 (2λ) k-2 β n,j k-2 op γ k-2 2 j v k-2 j ln j -k-2 2 = 2Cλ 2 β n,j 2
op γ 2 j v 2 j exp 2λ β n,j op γ j v j β n,j 2 op γ 2 j v 2 j exp 2λ β n,j op v j γ j ln j .

Take λ = γ -1/2 n v -1 n √ ln n. Let C 0 = β n 0 ,0 op and remark that for n ≥ 2n 0 (i.e such that γ n/2 λ max (Γ) ≤ 1), and for all j ≤ n/2, β n,j op ≤ C 0 exp -cλ min (n/2) 1-α , so that for all j ≤ n/2, λ β n,j op γ j v j ≤ C 0 exp -λ min (n/2) 1-α √ n 2b+α ln n a.s ----→ n→+∞ 0.

Furthermore, for all n ≥ 2n 0 , and for all j ≥ n/2, λ β n,j op

√ γ j v j ln j ≤ C 0 2 2b+α+1 .
Then, there is a positive constant C such that for all n ≥ 1 and j ≤ n,

exp
E M 3,n+1 2 |F n ≤ (1 -λ min γ n ) M 3,n 2 + γ 2 n v 2 n E n+1 2 |F n ≤ (1 -λ min γ n ) M 3,n 2 + γ 2 n v 2 n E ξ n+1 2 1 1 { ξ n+1 2 ≥γ -1 n } |F n Let V n = 1 γ n v 2 n M 3,n 2 .
There are a rank n 1 and a positive constant c such that for all n ≥ n 1

E [V n+1 |F n ] ≤ (1 -cγ n ) V n + O γ n E ξ n+1 2 1 1 { ξ n+1 2 ≥γ -1 n } |F n a.s.
Applying Robbins-Siegmund Theorem as well as equation ( 21), it comes M 3,n+1 2 = O γ n v 2 n a.s.

A useful theorem for averaged stochastic algorithms

Theorem 6.2. Let H be a separable Hilbert space and let

M n = 1 n n ∑ k=1 R k ξ k+1 ,
where

• (ξ n ) is a H-valued martingale differences sequence adapted to a filtration (F n ) verifying

E ξ n+1 2 |F n ≤ C + R 2,n
where (R 2,n ) n converges almost surely to 0.

Figure 1 :

 1 Figure 1: Evolution of the mean squared error in relation with the sample size with, from the left to the right, r 0 = 1, 5, 12.

Table 3 :

 3 Mean squared errors (.10 -2 ) of, from left to right, Stochastic Newton estimates with c α n -α defined by (9), its averaged version defined by (10) and Stochastic Newton estimates definded by (8) for different values of β and c β .

Figure 3 :

 3 Figure 3: Density function of a Chi squared with 2 df (in black) and kernel-based density estimates of C n (in green) and C n (in red) for n = 5000.

0 ( 1

 01 k γ k Ξ k+1 |F j = ϕ(1) = ϕ(0) + 1 t)ϕ (t)dt ≤ 1 + e j,n cosh λ j-1 ∑ k=1 β n,k γ k Ξ k+1

Table 1 :

 1

	H c α H H 0.1 0.0241 0.3873 2.1115 9.1682 H H α 0.55 0.66 0.75 0.9	H H c α	H 0.1 0.3280 1.3746 4.1304 13.5156 H α 0.55 0.66 0.75 0.9 H
	0.5 0.1229 0.0130 0.0057 0.0171			0.5 0.1393 0.0078 0.0135	0.0928
	1 0.0732 0.0257 0.0113 0.0030			1 0.0068 0.0049 0.0085	0.0440
	2 0.1203 0.0503 0.0213 0.0073			2 0.0104 0.0058 0.0052	0.0082
	5 0.4029 0.1647 0.0762 0.0168			5 0.2076 0.0260 0.0067	0.0027
	H c α H H 0.1 15.40 24.69 35.32 40.42 H H α 0.55 0.66 0.75 0.9	H c α H	H H α H 0.1 19.78 28.03 38.49 43.01 0.55 0.66 0.75 0.9
	0.5	1.30	8.36 15.90 22.80			0.5	4.49 12.48 18.79 24.20
	1	0.24	2.66	9.76 28.52			1	1.16	7.28 13.68 30.84
	2	0.29	0.06	3.02 22.64			2	0.41	1.75	7.46 26.90
	5	0.26	0.02	0.01	3.89			5	0.27	0.02	0.18	7.45

Mean squared errors of Stochastic Newton estimates defined by (9) (on the left) and its averaged version defined by (10) (on the right) for different parameters α and c α , for n = 10 000.

Table 2 :

 2 Mean squared errors of Stochastic Gradient estimates with step c α n -α (on the left)

  has no use in practice.

	H c β H H H β 10 -10	0.01 2.59	0.08 3.12 2.84 2.66 0.2 0.5	H c β H H H β 10 -10	0.01 0.24	0.08 0.22 0.30 0.17 0.2 0.5	H c β H H β H 10 -10	0.01 0.22	0.08 0.21	0.2 0.27 0.19 0.5
	10 -5	2.59	2.90 2.42 1.88	10 -5	0.29	0.26 0.20 0.23	10 -5	0.27	0.24	0.19 0.21
	10 -2	2.11	2.32 2.23 1.83	10 -2	0.22	0.26 0.23 0.32	10 -2	0.25	0.23	0.22 0.28
	10 -1	0.69	1.09 1.98 2.64	10 -1	0.25	0.24 0.21 0.27	10 -1	11.77	3.89	0.85 0.26
	1	4.04	0.61 0.66 2.06	1 26.37 11.19 1.46 0.30	1 444.61 409.27 184.09 9.77

  Previous theorem remains true considering a sequence (R n ) satisfying that there are a positive constant C R and a rank n R such that for all n

	Then,
	M n+1	2 = O γ n v 2 n ln n	a.s.
	Remark 6.1. Note equation (21) holds since there are η > 1 α -1 and a positive constant C 2 such
	that
	E ξ n+1	2+2η |F n ≤ C 2 + R η,n
	with R η,n converging to 0.
	Remark 6.2.

  Moreover, 1 1 {A n } converges almost surely to 0 so that R 2,n ) 1 1 {A n } < +∞ a.s and applying Robbins-Siegmund Theorem, V n converges almost surely to a finite random

	∑ n≥1 op (C + variable, i.e n ∏ k=1 (1 + λ min γ k ) 2 γ 2 n R n 2
	M 1,n+1	2 = O

n ∏ k=1

  n and G 0 = 1 and since E [G n+1 |F n ] = G n , it comes E [G n+1 ] = 1. For all r > 0, P [ M 2,n+1 ≥ r] = P G n+1 ≥ Furthermore, let j+1 = ξ j+1 1 1 {B j } -E ξ j+1 1 1 {B j } |F j and remark that E

	cosh(λr) ∏ n j=1 1 + e j,n	≤ P 2G n+1 ≥	e λr j=1 1 + e jn ∏ n	.

j+1 2 |F j ≤ 2C.

  λ β n,j op γ j v j ≤ C Finally, one can easily check that (see Lemma E.2 in Cardot and Godichon-Baggioni (2015))There is a positive constant C such thatP [ M 2,n+1 ≥ r] ≤ exp -rv -1 n γ -1/2Then , taking r = (2 + C ) v n γ n ln n, it comesP M 2,n+1 ≥ 2 + C v n γ n ln n ≤ exp (-2 ln n) = 1 n 2and applying Borell Cantelli's lemma,M 2,n+1 = O v n γ n ln n a.s. Bounding M 3,n+1 := ∑ n k=1 β n,k γ k R n ξ k+1 1 1 {C k+1 } -E ξ k+1 1 1 {C k+1 } |F k . Let us denote k+1 = ξ k+1 1 1 {C k+1 } -E ξ k+1 1 1 {C k+1 }|F k and remark that for n ≥ n 0 ,

	n ∑ j=1	β n,j	2 op γ 2 j	(ln j) 2a j 2b = O	(ln n) 2a n 2b+α	.

n √ ln n + C ln n

op (C + R 2,n ) 1 1 {A n }

• (R n ) is a sequence of operators on H such that for a deterministic sequence (v n ),

with (a n ) converging to 0.

Then, for all δ > 0,

We have

Then,

and applying Robbins-Siegmund Theorem,

Let us consider a ≤ 1 and

a.s

Applying Robbins-Siegmund theorem,

• If c < 1/2, one can take a = 1 and