Non asymptotic analysis of Adaptive stochastic gradient algorithms and applications
Authors: Antoine Godichon-Baggioni
Pierre Tarrago
Venue: Accepted by TMLR ()

Abstract: In stochastic optimization, a widely used approach for handling large samples sequentially is the stochastic gradient algorithm (SGD). However, a key limitation of SGD is that its step size sequence remains uniform across all gradient directions, which can lead to poor performance in practice, particularly for ill-conditioned problems. To address this issue, adaptive gradient algorithms, such as Adagrad and stochastic Newton methods, have been developed. These algorithms adapt the step size to each gradient direction, providing significant advantages in such challenging settings. This paper focuses on the non-asymptotic analysis of these adaptive gradient algorithms for strongly convex objective functions. The theoretical results are further applied to practical examples, including linear regression and regularized generalized linear models, using both Adagrad and stochastic Newton algorithms.

Published in Transactions on Machine Learning Research (06/2025)
Non asymptotic analysis of Adaptive stochastic gradient al- gorithms and applications
Antoine Godichon-Baggion
intoine.godichon_.. htgpdddwn...giioooooooooooeeeeee
Laboratoire de Probabilités, Statistique et Modélisation Sorbonne Université
Picrre Tarrago
Laboratoire de Probabilités, Stalistique et Modélisation Sorbonne Université
Reviewed on OpenReview: https: openreveww. net/ per//formm? id= byfbbydkkt
Abstract
In stochastic optimization, a widely used approach for handling large samples sequentially is the stochastic gradient algorithm (SGD). However, a key limitation of SGD is that its step size sequence remains uniform across all gradient directions, which can lead to poor perfor- mance in practice, particularly for ill-conditioned problems. To address this issue, adaptive gradient algorithms, such as Adagrad and stochastic, Newton methods, have been developed. These algorithms adapt the step size to each gradient direction, providing significant ad- vantages in such challenging settings. This paper focuses on the non-asymptolic analysis of these adaptive gradient algorithms for strongly convex objective functions. The theoretical results are further applied to practical examples, including linear regression and regularized generalized linear models, using both Adagrad and stochastic Newton algorithms.
Non asymptotic analysis; Online estimation; Adaptive gradient algorithm; Adagrad; Stochastic Newton algorithm.
Keywords:
1 Introduction
A usual problem in stochastic optimization is estimate the minimizer 0 of a convex functional G Rd -> R of the form
G(h) = E [xX,
where g X' x d - R, and X is X-valued random variable. This framework encompasses numerous classical problems, such as lincar and logistic regression (Bach 2014), or the estimation of geometric medians and quantiles (Cardot et al. 2013 2015 Madlichon-Baggiinn 2016) to name a www.oorius methods have been developed to solve this optimization problem, generally categorized into iterative and recursive approaches. Iterative methods involve approximating the minimizer of an empirical function derived from the sample using convex optimization techniques (Boyd & Vandenberghe, (204),, or more advanced refinements like mini-batch algorithms (Konečný al., 2015). While effective, these methods face scalability issues with large datasets and are unsuitable for sequential data. In contrast, recursive methods adapt naturally to sequential data and are computationally efficient.
Among recursive methods, the stochastic gradient algorithm (SGD) [Rbbinn & Monro 1951 and its aver- aged version Ruppprt 1988: Polyak & Juditsky 1992 are particularly well-known. Given sequential data XI...., Xn, Kn+h.... the stochastic gradient algorithm (0,)n20 and its averaged version (0m)n20 are defined recursively for all n 0 by
0x+1 On, - 7o+1 Vng (Xn+1500),
O = On n1 n (On+1 - 0

---

Published in Transactions on Machine Learning Research (06/2025)
where (%x) is positive step sequence converging to 0. These algorithms have been extensively studied, with asymptotic results in works like (Pelletier) 1998 2000) and non-asymptotic results focusing on quadratic mean convergence (Bach & Moulines 2013 Gadat & Panloup 2017 Gower et al. 2019 Averaged estimates are particularly appealing as they achieve asymptotic efficiency under regularity conditions, often attaining the Cramer-Rao bound (up to negligible terms).
Despite these advantages, significant limitation of SGD lies in its step size sequence (7n); which cannot adapt to varying gradient directions, leading to suboptimal performance in ill-conditioned problems. This issue has motivated the development of adaptive stochastic gradient algorithms. These methods take the form:
Oa+1 = 0 7n+1 An Ngg 1,)),
where (A,)) is a sequence of (random) matrices which enables the descent step be adapted in each coordi- nate. Prominent examples include Adagrad (Duchi al.) (01I), which effectively standardizes the gradient, and stochastie Newton algorithms that use estimates of the inverse Hessian (Bercu et al. 2020 Boyer & Codichon-Baggion 2020). These methods are particularly advantageous when the Hessian has eigenvalues of different magnitudes.
While asymptolic properties of adaptive methods are well-studied (e.g., Leluc & Portier 2020 Gadal
& Gavra 2020)), non-asymptotic results remain less explored. Notable exceptions include gigh-probabiiity bounds for Kalman recursions logistic regression (De Vilmarest Wintenberger 2021) and I,2 convergence rates for Adagrad and Adam (Délossez al., 2020). Furthermore, [Brrcu et al. (2021) obtain the rate of convergence in quadratic mean of stochastic Gauss-Newton algorithms for optimal transport. However, these results often assume uniformly bounded gradients, condition violated in cases such linear regression.
This paper addresses these gaps by focusing on non-asymptotic convergence rates for strongly convex func- tions with unbounded gradients. Our contributions include: (i) establishing convergence rates for adaptive methods when An may diverge, with a controlled divergence bound, (ii) deriving standard convergence rates under the additional assumption that A, has uniformly bounded fourth-order moments, (iii) provid- ing a general framework for analyzing the convergence of stochastic Newton and Adagrad algorithms, with applications to linear regression and ridgo-regularized generalized lincar models.
The paper is organized as follows: Section introduces the general framework. Section 3 presents the algorithms and theoretical convergence results. Applications to linear regression and generalized linear models are detailed in Sections and 5 respoctively. Proofs are provided Section 7 and the Appendix.
2
Framework
In what follows, we consider a random variable X taking values in a measurable space and fix d 2 2. Wo locus on the estimation of the minimizer of strongly convex function G RRd - IR defined for all h E Rd by
G(h) E lg (X,))]
with g: X x Rdd - RR. Let us suppose from now on that the following assumptions are fulfilled:
(A1) For almost every x E X' with respect to the distribution of X, the functional g(x;-) is differentiable on Rd. Morcover, there exist p 2 2 and non-ncgative constants c(O), cl such that for all E IR,
|iag (x.N)) < c( + c(( | 2
(A2) The functional G is twice continuously differentiable.
(A3) The Hossian of G is uniformly bounded Rd i.c there is positive constant Log such that for all h e Rd
>< S LVG
where I1-llop is the usual spectral norm for matrices.
2

---

Published in Transactions on Machine Learning Research (06/2025)
(A4) There exists μ such that the functional G is p-strongly convex for all h, h' E R
4 | -hl?? -(h) 2 VG(h)" h)
Let us now discuss these assumptions. First, note that Assumption (A1), for p= 1, ensures that the second- order moment of the gradient bounded by a constant and a torm that, at worst, grows quadratically-ai assumption already present in the literature (Bach Moulines, 2013). When combined with Assumption (A3), this can be linked to the expected smoothness condition (Gower al., 2019). Remark that we require higher order of boundedness in Assumption (A1), compared for example (Bach & Moulines 2013), because of the presence of the random preconditioning Ag. Assumption (A2) justifies the use of gradient-based algorithms, while twice differentiability is crucial for Newton-lype methods.
which only concern the convergence of G(O,), remain valid even without assuming strong convexity or the convexity of the function G, provided that G satisfics the Polyak Lojasiewicz condition (see Guo et 2025
It is worth noting that Theorems 3.1 and 3.2
Gower et al. (2021) Karimi et al. (2016). among others).
That is, if the following condition holds:
(A4') There is μ > 0 such that for all h Rd |VG( 2 2p (G(h) - G(0)).
Theorem 3.3 however needs strong convexity in order translate the convergence of G(O,) into convergence of 8n In the case where the convergence of A, only requires the one of G(On), (A4) can be replaced by (A4") for Theorem 3.3 to hold with 0, replaced by G(O,).
3 Adaptive stochastic gradient algorithms
3.1
The algorithms
Let X,,..., X,, Nnti,... be an i.i.d sequence of random variables with the same distribution as X. Then, an adaptive stochastic gradient algorithm defined recursively for all n 2 0 by
0n11 = On 7n An Vng (X++1, 0n).
where 0 arbitrarily chosen, 7n cn, with ey 0, y (0,1) and A, is sequence of symmetric and positive matrices such that there is filtration (Fu)nzo satisfying:
For all 2 0, An is F.-measurable.
X is independent of Fn.
oo...,, .,. and consider the filtration Typically, one can consider An only depending on Considering A, diagonal with (An),, = generated by the sample, ic Fn = a (X))...
-1/2
(IFI (a D Vng (Xi, ((110)-))).)) where An is a recursive estimate the inverse of the Hessian corresponds then to the stochastic New- ton algorithm (Bercu et al. 2020 Boyer & Godichon- Godichon-Baggion]] (202)), while the case where A,
leads to Adagrad algorithm Duchi et al. 2011p. The case
A En Vag (X,, 02-1) Vag (X,, 0(,00-1)"))
corresponds to the stochastic Gauss-Newion algo-
n+I
rithm
Cénac el al. 2020
Bercu el. al. 2021
3.2
Convergence results
3.2.1
A first convergence result
In order obtain first rate of convergence of the estimates, let us now introduce some assumptions on the sequence of random matrices (Am).2pi
3

---

Published in Transactions on Machine Learning Research (06/2025)
HH1) ) One control the smallest and largest eigenvalues of An:
(Hla) There exist (Un)n2a, Ao and 8, 2 0 such that
P mmmn (A,) S Aod S untit + 1)
for <1S1, with (M + 1)-9)n2 decreasing. y I 1/2, one also assumes the stronger hypothesis of the existence of X, Ny(n 1)-x with
X/ > X < such that for all 2 0,
Amin (An) 2 Xp.
(H1b) There exists sequence Bn can for 2 with cæ 2 0 and 0 B if S 1/2
0 << B 1/2 1/2 such that for all n 2 0,
| op Bn+1.
Remark that the case = 0 is allowed in (H1a) and that one can always choose / in the allowed range of (H1b). In most cases and especially for Adagrad and stochastic Newton algorithm, (Hla) is easily verified. The presence the decreasing term v, in (H1a) takes into account a general phenomenon (usually implied by Rosenthal inequality) that error contributions from higher moments of X, albeit dominant for small n, fade as n goes infinity. Concerning (H1b), some counter-examples showing that the estimates possibly diverge in the case where this last assumption is not fulfilled given in Appendix F] meaning that this assumption is unfortunately crucial. Up to our knowledge, it is still an open problem to know whether such assumption can be lifted in the specific case of the linear or logistic regression. However, it is apparent in the proofs and counterexamples that the failing of the convergence in quadratic mean is due to the exponential explosion the algorithm on an event of negligible probability. It is then still possible to deduce good quadratic bounds on the convergence of 0, even without Assumption (HIb), see for example Corollary 4.1 for such result for the linear regression.
Anyway, easy way to enforce Assumption (H1b) is to replace the random matrices A, by
min || llop S34z1
A,
An
|4n lop
and one can directly check that | S Sut1. Similar adjustment can be used to ensure (Hla) in the case ? 1/2. It is worth noting that when the matrix A, not diagonal, computing the operator norm can be too costly. In this case, we instead consider the Frobenius norm. This does not affect the results, and the proofs remain strictly analogous.
Let us consider the case of Newton's method, and especially the case where the estimates of the Hes- sian are of the form Hn n*I (Ho + Σ 0g +z) and which can be so recursively invert with the help of Riccati/ Riccati/Shermant /her//Shhran--- Aateermann-Morisonn'' formula (see Bercuu et al. (2020); Boyer & Godichon- Godichon-Baggioni (2020): Godichon- Godichon-Baggioni et al.] (2022)), Assumption (H1b) can also be enforeed by considcring the following version of the estimate of the Hessian
1
n
C
H. Hn n
e
k
where eg is the k-th (modulo d) canonical vector (sec Bereu et al.
2021
Godichon-Baan Balichon-Baggion et al. (2022)
Regardless, these assumptions remain less restrictive than the standard ones in the literature, For instance, in the literature on stochastic Newton algorithms (see Byrd et al. (2016); Ye al. (2017): Agarwal et al. (2017), among others), it often assumed that Hessian estimators are uniformly bounded from above and below, implying that. their inverses are also uniformly bounded.
4

---

Published in Transactions on Machine Learning Research (06/2025)
Similarly, in the literature Adagrad, a penalty term is introduced to upper bound the largest eigenvalue of A, This corresponds in our framework to setting this would amounts to choose the strictest hypothesis 3 = 0 in Assumption (H1b). Likewise, it is generally assumed that gradients are bounded in order to ensure a uniform lower bound on A, (see Défossez et al. (2020) and Duchi et al. (2011). for example) this would then amounts to choose on=1 in Assumption (Hla). It worth noting that in Guo al. (2025), gradients are not assumed to be bounded, yet the 'regularization" term still present.
17(n+ p(n+1] 1) (see equation 2 where vj is the penalty
Finally, one examine the proofs of Theorems can be verified in practice.
and 5.2 to understand how these assumptions
We can now oblain a first rate of convergence of the estimales. For the sake of simplicity, let us now denote
the risk error by Vn == G (0,) - G(O). Note that since is μ strongly convex, one has ||0, - 01 I 2 Vn.
Theorem 3.1. Suppose Assumptions (A1) to (A4) and (H1) hold. Then, for all 2 and for ony A < min {- 23, >
E Vil S exp (-cr ((4t)))) e(n))) (x(u) + K
2/12286/2-119214
max 1shSn+1
Vuk
K2 (1 K3 L (6+g2)/2
with e(n) = d(1 given in equation 19 and K( ( K!!", k constants respectively given in equation 20
and equation
In the particular case where 8/2 2 2/ (which happens as soon as 8 2 1), one can simply set X = 0 in the above formula we will see that is the case for the generalized linear model with the stochastic Newton algorithm. However, for Adagrad algorithms, one can not avoid using first À > 0, since A, depends on Vg((,-) rather than V²g(X,-) (while the expectation of the latter is bounded on R4, the one of the former is generally unbounded). To get rid of this weaker statement, will need the following equivalent of Theorem 3.1 for higher moments.
Proposition 3.1. Suppose that Assumptions (A1) with p 2, (A2) to (A3) and (H1) hold. Then for any 2 p p and any X < minfy- - 23,1 7),
Vpa I exp (-c,woont-atti1--- (1- ((i)) (x(") + -K11)
p-pL 2- (8+a)) Up
max 1gkša+1
+ K2 ((1)) n- -p x)
R-d Kg
[n//2]
(n 1)
2 2 (5+gA)
with e'(n),
K (1') k K(l and K.
constants respectively given in equation 67
equation
68 and equa-
tion 77
3.2.2 Convergence when A, has bounded moments
In order to get a better rate of convergence, let us now introduce some new assumptions on the sequence of random matrices (An):
(H2a) The random matrices A, admit uniformly bounded second order moments. There exists Cs > 0 such that for all n 2 0:
|m S C
(H2b) The random matrices An admit uniformly bounded fourth order moments. There exists Cs > 0 (which can be taken equal the one of (H2a), up to increasing the latter) such that for all 2 0:
| 11 < C
5

---

Published in Transactions on Machine Learning Research (06/2025)
For simpler statement, assume here and in the next paragraph that q >>> 0 in (H1a), although similar bound would hold in full generality.
Theorem 3.2. Suppose Assumplions (A1) to (A4) for some > 2, (H1) and (H2a) hold with 6 > 0. Then, for all n 2 0,
E [V]] S exp (-c, 1 (0---(111))) (k(3) K
2-1
p
max 1gksnt1
1
-k? n/2 T2
12) +
()-1)
Kg n
(2)
where enn) o11) is given in equalion 24
and K1a) KTP K2 K3 are constants respeclively given in
equation 25 equation 20 and equation 27
Tt is worth noting that, using calculations analogous to ours and those in Bach & Moulines (2013). a bound in the case of the online stochastic gradient algorithm would take the form
E [V.l S Kge kopmn Knn
Thus, we obtain similar bounds, but with the additional presence of the term Ao the exponent, which arises from the smallest eigenvalue of the conditioning matrix, as well as the term Uny which controls the exlent to which our conditioning matrix cannot be smaller than this value.
Similar to the gradient method, we obtaín bound with two phases: (i) an exponential decay for the initialization error, followed by (ii) convergence rate of order n once the algorithm has stabilized. One might be tempted to choose 7 = 1, but this would result. in the loss of exponential decay (or an increase in variance). Thus, finding an optimal trade-off for the choice of y is challenging. In any case, a common approach to accelerate convergence to introducc an averaging step (soe Ruppert 19888. Polyak & Juditsky 1992 Boyer & Godichon-Bageee Baggion (2020), among herrs)).
Finally, in order to get the rate of convergence in quadratic mean of stochastic Newton estimates, now give the L rate of convergence of G (0.) when > 1/2.
Proposition 3.2. Suppose Assumptions (A1) to (A4) for some > 2, (H1) and (H2b) hold with > 1/2,6 > 0 and 3 < 7 - 1/2. Then
V? S exp
- \opm! (x12) + (2))
(-3
3
UK k 2- 26
p-2
max
Iskšat1
n 27 +
,,(2),(0-211 2//p 2(pp2))/p 1/ =: Mn. [n/22]
with k(?), ( k!?), k222) constants respectively given in equation 73
equation
74 and equation 75
In other words, one has M, 0 min (2y, (0r3)) Hence, for large enough (namely 8
p- 7), the
main contribution comes from the second term of the latter bound, ie we obtain the good rate of convergence O(n"7)
3.2.3 Convergence results for stochastic Newton algorithms
Let us now focus on the rate of convergence of stochastic Newton algorithm. To this end, let us set H := V²G(0) and suppose from now that the following assumptions are also fulfilled:
(A1') There exists Lvg > such that for all à E Rd
E
(X,h) Vng (X, [0] < Lvg 11 0
(1)
(A5) There is a non negative constant Ls such that for all h Rd,
|VG()) (2G(0) (0 b)l < Las ||/- 0

---

Published in Transactions on Machine Learning Research (06/2025)
(H3) The estimate An converges to H there is decreasing positive sequence (UA,n) such that for al 2 0,
| - H 1 S VAA.-
Observe that assumplion (A1') is often called expected smoothness in the literature (Bach & Moulines 2013 and is satisfied in most of examples such as linear and logistic regressions (Bach & Moulines 2013 Bach, 2014) or the estimation of geometric quantiles and medians (Cardot et al. 2013) among others. Concerning (A5), under (A3), it satisfied as soon as the Hessian is Lipschitz on a neighborhood of 8. For instance,
in the case of the linear regression, La = Finally, Assumption (H3) satisfied having a first rate of
convergence of the estimates of 0 (thanks Theorem 3.2 or Proposition 3.2 for instance) leads to first rate
of convergence of A., which is often verified in practice (see Boyer & Godichon-Bagge Baggioni (0220) for instance, see also Lemma 7.9 in the specific case of the linear regression).
Theorem 3.3. Suppose Assumplions (A1'), (A1) to (A5), and (H1) to (H3) hold with 7 > 1/2, 5 and 3 < 7 1/2. Then,
E [10
011²] S se-tan""> ((() + K
max (k +
1)
OSksn
K2 (3)
22t7 Tr (H-ISH-)
K
(3)
UA,/2
U
+ d(n/2]
n
where E is the covariance matrix of X, K(3), i 1, 2, are defined in equation
28
equation
29 and
equation 30 and dg only depending M2 and VAA is given in equalion 29
Recall that Mg is given by Proposition 3.2. Remark from equation that dj S C(VA.& + Ms) for some constant C 0. The latter results can further simplified if we also assume a sufficiently large exponent in (H1a).
Corollary 3.1. Suppose Assumptions (A1'), (A1) to (A5), and (H1) to (H3) hold with y 1/2, ò
2xp p-2
and B 1/2. Then,
K. (3)
E |10, 011] ~n TI
kr(3)
K v /A,n/2
UAnn2
kK(3) - 2onnt
with K(3), 1..22" given in equation 31 and equation
32
Then, if vA,. converges to 0, we obtain the usual rate of convergence nt sumptions, a bound for the online stochastic gradient algorithm would take the form (Bach & Moulines 2013):
+ Indeed, under analogous as-
E [00. 011]] s Koc Koe- lerant- 4c, C( n
However, we can observe two interesting differences compared to standard gradient algorithms: (i) the smallest cigenvalue no longer influences the exponential decay of the first term, and (ii) the variance term is modified. Observation (i) is one of the main advantages mot mvtiiiging the use of stochastic Newton algorithm.
3.2.4 Convergence results for adaptive gradient (Adagrad)
Recall that the Adagrad algorithm amounts to specify d initial parameters a,,..., R4 and choose A, diagonal with
1
(2)
ak + Di-1 n ( Ving(X(+1,00))
n+I
The original Adagrad algorithm would then amount to take 7 1/2. To guarantee non-degeneracy of the matrices assume some minimal fluctuation of the gradient at the minimizer 0.

---

Published in Transactions on Machine Learning Research (06/2025)
(A6) There is a >> 0 such that for all isi5 d,
E (Vng(XX,)) 0)) a.
(3)
(A6") There is a > 0 such that for all h E Rd and 1 s i sism d,
E (Vno(X, (X, 1))
(4)
Remark that (A6') is much stronger as (A6). However, the former often satisfied, as it is the case for the linear regression with noise. Then, we consider the following modification of An (An)ks (An)ar for k * k and
min {can', (A if 1/2
(An)s
(5)
max min {egn?, (An)kt) N6n x3
if S 1/2
for 1 1 k S d, where Br cgnd with B min min (x/2, 1/4] and X < (where X and og 0 are chosen
arbitrarily).
We then have the following convergence result for the mean quadratic distance. We only state the result for S 1/2, but a similar statement holds for 1/2 S 7 < 1 with different constants.
Theorem 3.4. Suppose Assumptions (A1'), (A1) to (A4) and (A6) are satisfied for y S 1/2 and B <
(1-2)>²p 8 8-4+22m(11>) 1/4). Then, with (An)a21 given in equation
min
E [10,- -B113] s k(() exp - (1- + K2 log(n + 1) p=1 (p-1) 1) min
2:1-92761
2032
Kg 7
with E(n) given in equation 34 On =0 log(n + 1), with vo, C3S and do given in equation and equalion 84 with p' satisfied, the same conclusion holds for B < 1/4 with Cs given in equation 87 taking p'
85
equation
86
p. In addition, k(", k!')) and K(t) are given in equalion
35
If (A6') is
p.
In the special case where 7 = 1/2, which corresponds to the usual Adagrad algorithm, we get
E ||00, - 0| < K(D exp (-C,AAoo' (1 - E(n)))
(4) log(n + 1)2 (1-0))0-11 + 1r (
and we so achieve the usual rate of convergence V as soon 1/2 (1-ما)(0-1) 0, i.e soon as p 4
Remark that the advantage of using Adagrad algorithm compared to a standard stochastic gradient algorithm does not appear in the bounds of Theorem 3.4 Since Adagrad algorithm amounts a rogularization of the gradient descent by diagonal matrix, not much can be deduced in full generality. However, one expects better bounds to hold in the case where the Hessian matrix at the minimizer is also diagonal. For example in practico, the parameter 8 should be tuned in such a way that cand >> (H) at the time n of interest, where Amiu (H) is the smallest eigenvalue of the Hessian at the minimizer the influence of such choice of the parameter 3 would appear in the first term of the bound of Theorem 3.4 in the case of a diagonal Hessian at the minimizer.
4 Application to linear model
Let us now consider the linear model = X + where X E Rd and is a centered random real variable independent from X. We suppose from now on that E [XX' X is positive. Then, 0 is the unique minimizer
of the functional G : Rd - E defined for all h E Rd by
G(h) = 2 E (Y
- x x))
8

---

Published in Transactions on Machine Learning Research (06/2025)
If X admits second order moment, the function G is twice continuously differentiable with VG(h) - E [(V h) x] and Gh) = I [XXT].
4.1
Stochastic Newton algorithm
The stochastic Newton algorithm is defined recursively for all n 2 0 by (Boyer & Moddicon--aaggion)
2020
Ox+1 = On + 7 S (Yn+1 X 1n) Xn+1
(6)
oz (mSo Σi= x,x?) with So positive, 2 and (ax)20 a deterministic modulating where Sn atm sequence satisfying, for some 0 a- a4 and O,
a an I a+, and an, 1 n' n20. 0.
The parameter m 2 reflects the expected quality of the initial approximation of the Hessian at the minimizer by Sg. The usual stochastic Newton algorithm corresponds to the choice m 1, a, = 1. Build then a regularized version by setting
min (1|5/= op Bu+1
S
S-1
| 11op
with 3n can.. Remark that S7t1 can be easily updated with only O Morrison (or Ricatti's) formula. More precisely, considering S. = (n + 1)5m: one has
(dº) operations using Sherman
= S - (1 + XT ST X.)) ",.' "T,)) X.+1 X
Then, one can easily update 5n and 3n We call regularized stochastic Newton algorithm the algorithm equation 6 with S, replaced by Sn.
In order to avoid singularities in the estimation of the Hessian, we will assume in the sequel that the distribution of X is non-degenerate on Ied Formally, this amounts to suppose the existence of a constant LMK > 0 such that for any h E 3d /E[AXXTA S LMKE ([x" We can now rewrite Theorem 3.3 for the regularized algorithm as follows:
Theorem 4.1. [Regularized Stochastic Newton/ Suppose that there is p > such that X and respectively admit a moment of order 4p and 2p. Suppose also that there positive constant LMK such that for any h E S TE [ LMK [|xTh]] Then, for any 1/2 < < 1, the regularized algorithm (0n)n20 satisfies the mean quadratic error
I 110, 012] S -e-tamn
(3) 1,1m + (3) max dx(k: (k: + 1)71
OSkSn
K (3)
c. 23+7
23+
Tr (H +
2,86
+ K: HH,n2 + n noddnng d(n/2)
n
n²
(3) where Ka,ün, K23) Rin Rew 1,85 1. lin dn are given by equation 44 while un is defoned in equalion 43
((3)
Observe that n nddn- O max max
and UH O (n- and since p 4, these terms are both
negligible. Using this theorem, it is possible to prove non-asymptotic quadratic concentration bound for the convergence of the original stochastic Newton algorithm, at the cost of imposing a sub-gaussian decay on the tail of X. Namely, following (Vershynin 2018 Soc. 2.5), we say that X sub-gaussian if there exists such that
P|| < 2 exp( -2/c)
for all f. > O, and we then define the sub-gaussian norm
| | of X as
|| inf (1 0, [exp(I] /r}] 2)

---

Published in Transactions on Machine Learning Research (06/2025)
Remark that any gaussian distributed bounded random variable is sub-gaussian. Under sub- sub-gaussian hypothesis for X, we then have the following concentration bound.
Corollary 4.1 (Original stochastic Newton). Suppose that X is sub-goussian with sub-gaussian norm || > 0 and e admits moments of order 2p, p > 2. Suppose also that there is a positive constant LMK such that for any h E S / S LMKE [|xTh]]. Then, for any 1/2 < Y < 1, we have for all ō > O and n 2 co, with co only depending on So; d, and the second moment of X
(6) (r( +C, (et(ee" E|V #) + C2n C2n
P (110,, - 01l > 8) 82 n 72 c.
with e, C1 C2 depending on the parameters of the algorithm, LMK, the first 4p moments of X and || ll and the first 2p moments of c.
In view of the central limit theorem proven in Boyer & Godichon-Bagee Baggioni 2020). this non-asymptotic bound is optimal in the fluctuation regime up to the numerical constant 2 and the error terms.
4.2 Adagrad algorithm
For linear model, we define Adagrad algorithm for all n 2 0 by
aa+1 On + M (Yn41 xm_1 Xut1,
with Dn diagonal with, for y S 1/2.
1V (Xsni)e) (X+1))) ndt
(Dn)Es = min max
n
+
S
C3
X
where 0 < < (7 X)/2 for some un > 0 and if y > 1/2,
(Dx) max
n=
1
n-1
(Y41-X74,1) (X(+1)x)²)
ax
C3
n
for some < 5 1/22. The usual Adagrad algorithm is done with y = 1/2, which yields for (Y xT+11nn (Xn+1)s
(On+1)== = (0n)x
min max
n-8+1/2 Gg
Vox + Ei ((Y++ XT, (Xi+1)k)²
N
%
Note that first convergence analysis yields that almost surcly there exists no 2 0 such that for n 2 no.
(Y - X (Xn+1)&
(on+1)k (0x)) az Σm= ((Y+1 1 01) (X44))))²
which is the usual Adagrad algorithm. We can then rewrite Theorem 3.4 as follows (remark that we only state the result for I 1/2, but a similar statement holds for 1/2 < < with different constants).
Theorem 4.2. Suppose that there p > such that X and e admit a moment of order 2p. Then, for 7 & 1/2 and B 1/4, have
E 00, ] < Kodo exp (- A
ada 1 (1 (1-endo sado 0,tin
+ -add log(n + 1) 2 (x=1) mine 201 iinl 1011
+
Reada m7
3,16n
no
where sada
nin o(1) is given in equation 51 and K Kada
1,imn Kod
Kodo 3,Kn are given by equation 52
equation
53 and
equation 54
Observe that in the case where 7 1/2, the J. rate of convergence is achieved soon (p 1) 011143)/3 43)/3 1/2, ie soon p 2(1-55)
5-48
10

---

Published in Transactions on Machine Learning Research (06/2025)
5 Application to generalized linear models
The framework of the lincar regression can be casily generalized to the more general setting of finite dimen- sional linear models. Let : x y + R be a cost function on some domain y C IR. The general learning problem to solve the minimization problem
arg argmin E f(x)),
JEF
with (X, Y) and F is a given class of mcasurable functions from X' to D, where X a mcasurable space. In the case of finite dimensional linear models, y = R and J {h) h E Rm), with c X R known design function (remark that the setting can be easily generalized to the case Y = R2 and $ X' - IR and h e Mm..p (IR)). Then, assuming that l is convex and adding a regularization term on 0, the minimization problem turns into the framework of this paper with
G(h) = E g (2,
with 2 = (Y, ((X)) = (Y, X) and for all E (R), h) ((Y, In what follows, let us suppose from now that the cost function l twice differentiable for the second variable and that there is a positive constant Lvi such that for all h Rd
(7) where ().. is the second order derivative with respect to the second variable. Remark that such a bound is generally assumed if we require that ||DG(())lop S Lva < too for all h E Rd. This is for example satisfied when f(y.v') = fly - 3/) with sup, [f"()) < +00. For example, in the simplest case of the logistic regression, we consider a couple of random variables (X,Y) lying in Rd x f-1,1}, + Ia and v(y,8/) log(1 + exp(-vu')) and we indeed have for all h and Y (-1,1
(RE s Lvi,
<=(,,(") 1 Xx) 1 exp(- 1
There are then two main cases to deal with the convexity of the mininization problem either assume strong convexity regularization. The first consists in assuming that the functional - E. [e (Y 1TT X)] is strongly convex, which is in particular verified when there exists >> 0 such that
inf Vil(,,8)) > a.
(8)
VER
and E [XX*] is positive. This case is called the elliptic case in the sequel and the results are very analogous the ones for the linear regression and are thus not repeated. We will then focus on the regularized case. Without uniform lower bound on Vil(yyv') one needs regularization term, yielding the following regularized minimization problem
arg min E [&(Y, (0, XX)] + 101
(9)
PERm
for some > 0. In what follows, suppose that the minimizer exists and we denote it by 0..
5.1 Stochastic Newton algorithm
The stochastic Newton algorithm is defined recursively for all 2 by
0.+1 = On - 1 (Vnl (Xn+1, 0%, Xn- X + o0m),
where, using the trick introduced in Bercu al. 22021 and developed in Rodichon-Baggioni et al. (2022 5, is the natural recursive estimate of the Hessian given by
1 a-1
ad Σ 1
Σ 3, n +1 1=0
(0 (H) +
(10)
11

---

Published in Transactions on Machine Learning Research (06/2025)
with i[d] denoting i modulo d. Remark that easily update the inverse using the Riccati's formula used twice, i. considering S. (n 1)5,, and
ST1 n+ = S Vijl(n+1, X0,, x (1 Vie(Yn+1, (0n. (nti)) n+1 S Xn+1) " S, X
Sa+1 = 5 ad (1 ode (1- S-1 (0+1))++1) -1
/ (a
one has 5,t1 = (n + 2) In what follows, let us suppose that the following assumptions hold:
(GLM1) There is L 0 such that the function h + E (Y, XXT] is Tyag--ispchitz with respect to the spectral norm.
(GLM2) There is p 2 such that X admits a moment of order 2p and such that there is positive constant Io satisfying for all 0 f a S 2p
VnL x - 00.11% s Lgg
Remark that Assumption (GLM1) is verified when for all y. -i is Lipschitz and X admits third order moment, which can be easily verified for the logistic regression for instance. Assumption (GLM2) is verified when the random variable v (Y, xT0a) X admits moment of order 2p.
Theorem 5.1. Suppose Assumptions (GLM1) and (GLM2) hold. Then,
|10, - 8011²] S s -dann
k((3) KY.LLM + k(()
V,GLL max (l: + 1yd,,, osksn
K (3)
+ n
Tr TH 2oH
2LG
+ (3)
GL/ + n² nd [Idnjj..N
n"
where Hg E Vi. (Y, Xx" +old, Eg E =
(V (T.) x (V (Y, X =0.)²
k KiCLLM
K p. GLAG K()) (3)
(3)
GLGM K GLM dn, GLM defined in equations equation
60
equation
61 and equa-
GLM
tion 62 and U1,n is defined in Proposition 7.3
Remark that n² 11d1//2 = On min(y,1 (7))))))))) see Section 5
5.2 Adagrad algorithm
For generalized linear model, Adagrad algorithm defined for all n 2 0 by
ant1 = On - "n+1D (Yut1, 8 Xn+1) X,+1,
where D, is diagonal and for 7 1/2,
n-8
n-1
(Dn)ks = max
Gk +
Σ
(V(+,, X++1) (X++1) + a(8))cc)
C3
n n+
1=0
for some 0<B 8 < < 1/2, and for 7 I 1/2,
(Dn)at min
maxx
n
1
+
(nnl Of (Xi+1) (0:))a))
nx
C3
n
+
where 0 < (y X)/2 and as > 0. The usual Adagrad algorithm is done with = 1/2, which yields for
us
VAl (Yn+1, 0 Xm+1) (Xu+1)s + a(0m)
(0n+1)* (8m)
min
max
n 8-1/2
En- (V (V 00 X (X+11) + (0.))))
n 41/2
ca
12

---

Published in Transactions on Machine Learning Research (06/2025)
Like the linear regression, the general linear model needs minimal randomness to ensure the expected rate of convergence of Adagrad. Indeed, in the extreme case of a deterministic sequence (Xn; Yn)220 Ada- grad algorithm may diverge in the unfortunate situation where V& (Y4+1, 0 X (X4+1) vanishes or remains very small. Such behavior can be averted by requiring at the minimizer 6g a minimal variance for Vn, (Y,05 (X)x for all < k d.
(GLM3) There is positive constant 0, such that for all s
Var VR (X)x a..
Remark that
Var (Y, (X)a = E Vil (Y, X 0,) (X)x + +(0.)a
(11)
that (GLM3) can be a mirror assumption (GLM2). We should stress that the existence of such Og is almost automatic when minimal randomness between X and Y is assumed. Indeed, having Vnl (Y, o7 X) Xg deterministic would imply an analytic relation between Y and X. The main computational issue is to estimate concrete value of ag. An example dealing with the logistic regression is given in Section
When (GLM3) is assumed, one can show using Theorem 5.2 that there exists almost surely no 2 a such that for 2 no.
(On+1)a (fn)s + Vhl (Yn+1, 1, 0 Xn+1) (x+1)s + ((0))
ax + Ei= (V (Y,+1, Of X,+1) (X++1)a + (0,)))
SO that we recover the usual Adagrad algorithm for large n. We can then rewrite Theorem 3.4 as follows (remark that we only state the result. for y S 1/2, but a similar statement. holds for 1/2 S < with different constants).
Thcorem 5.2. Suppose Assumptions (GLM1), (GLM2) and (GLM3) hold. Then, assuming that y S 1/2
and 3 min ( (8-1)t2p(111) 1/4), we have
(1 (1-7)r²p
E [10nn 00113
< Kide
KI,GLMeN exp
E(n))
Kada 2,GLM log(n + 1) P-1 x n
(0-1) min 20 20-77107---1 111-))2--29222 2212 1]
Kada +
3,GLMg
77
where =(n) = o(1,, K Kada model.
Kada (ILM 2,L and Kada 3,0LM have explicit formulas depending on the parometers of the
We do not specify the exact value of the constants here, since they can easily be obtained along the lines of previous results. Once again, when y = 1/2, the I rate of convergence achieved as soon as p > 21-43)
5-19
In
6 Simulation study
In this simulation study, we consider the following scenarios:
Stochastic Newton Algorithm: We set c, = 1 and initialize A, 1 Ia stabilize the algorithm during the first. iterations. Additionally, and again for stabilization purposes, as suggested in Boyer & Godichon- Baggioni (2020), we use modified step size, taking Yn [a+2007 We consider:
The choice of 7: y 0.66 7 0.75.
The of truncation not, with eæ 1 and B = 1/2, while employing the Frobenius norm.
13

---

Published in Transactions on Machine Learning Research (06/2025)
Adagrad: We set G = and initialize A. Ia- For stabilization purposes, suggested in Boyer & Ex We consider:
Godichon-Bagginn (2020) use modified step size, taking 7n (x+20)7
The choice of 7: 0.5 or 0.75.
The use of truncation or not, with cg 1, X/ = =, 3 = 0.25 (resp. 0.125) and X = 0.385 (resp. 0.25) 7 = 0.75 (resp. if 7 = 0.5).
6.1 Linear model
We consider the linear model:
== x==00+e +e, where X ~ N N (0, diag(I,...., and e e~ 10,
The parameter A set as f = (-d/2, -0d (d - 1). d/2).. In the following experiments, we set d = 10 and generate 50 datasets of size n 10 Moreover, we consider random initializations 0g = + U, where U N (0, Ia). In Figures and 2 we analyze the evolution of the quadratic mean error of the estimates
1e+02
Quadratic mean error
y= 0.6666 y= 0.66, truncated
1e+00
7= 0.75
y= 0.75, truncated
0.68
1e-02
0.75
1e+01
1e+03
1a+05
n
Figure 1: Evolution of the mean squared error of the estimators obtained using the stochastic Newton algorithm in the linear model as function of the sample size n, for 0.66 or = 0.75, with or without truncation.
function of the sample size Unsurprisingly, we observe that the estimators achieve the expected convergence rates. Although it is possible to construct counterexamples where truncation is essential, we see here that it has little to no impact the quality of the estimators. This is not surprising, considered Corollary 4.1 obtained for the linear regression the possible failing of the convergence in quadratic mean would be due to an event of exponentially small probability, and such an event would only appear with reasonable probability on a very large sample of datasets.
6.2 Logistic regression
We now consider the logistic regression case:
Y ~ B (T (B x)), where N~ diag(I..... d))
and π(Φ) 1 ex
It well known that 0 is the minimizer of the functional G Rdd IR defined for all h Rd by
G(h) E [log (1 exp (xTh)) y
However, this function is not strongly convex. To address this, consider Ridge logistic regression, where aim to estimate the minimizer of the penalized function G2 .d - IR defined for all h E Rd by
G, (h) = Blog (1 + exp (x (xTh)) YX hl + 1
14

---

Published in Transactions on Machine Learning Research (06/2025)
1e+01
Quadratic mean error
y= 0.5
1e+00
Y= 0.5, truncated
y 0.75
1e-01
0=7.75 truncated
0.5
1e-02
0.75
1e-03
16+01
16+03
1e+05
Figure 2: Evolution of the quadratic mean error of the estimates obtained using the Adagrad algorithm in the linear model function of the sample size n, for 7 0.5 7 0.75, with without truncation.
In the sequel, the parameter 0 is set 0= (-d/2, (d
d/2). In addition, set 0.1 and denote by 8 the minimizer of G. (in practice, we generate sample of size 10" and approximate the minimizer using the R function glmnet). Moreover, we generate 50 datasets of size = 10 and we consider random initializations 8 Hr + U, where U N (o, Ia). In Figures and we analyze the evolution the
1e+01
Quadratic mean error
10+00
0.6666
y= 0.66, truncated
1e-01
y= y=0.75 0.75
y= 0.75, truncated
1e
0.88
< n -0.75
1e-03
10+01
1e+03
19+05
Figure 3: Evolution of the mean squared error of the estimators obtained using the stochastic Newton algorithm in the ridge logistic model as a function of the sample size n, for = 0.66 or 7 0.75, with or without truncation.
quadratic mean error of the estimates function of the sample size n. Unsurprisingly, we observe that the estimators achieve the expected convergence rales. Contrary to the linear case, we can here that there is little impact of the truncation the behaviour of the estimates, especially for Adagrad algorithm with 0.5. Indeed, the truncation seems to have little impact on the rate of convergence.
Conclusion
In this paper, we have proposed a relatively simplified framework in which we can establish the conver- gence rates of adaptive algorithms. More specifically, the relaxation assumptions primarily concerns the conditions imposed on adaptive step sizes to achieve the desired convergence results.
However, now necessary complement these relaxed assumptions on step sizes with a similar relaxation of assumptions the studied functions, particularly by providing theoretical guarantees in the non-convex
15

---

Published in Transactions on Machine Learning Research (06/2025)
1e+01
Quadratio mean error
1e+00
Y-0.5
y= 0.5, truncated
1e-01
0=0.5
0=7.5, truncated n
1e-02
n -0.75
10-03
16+01
1e+03
16+05
Figure Evolution of the quadratic mean error of the estimates obtained using the Adagrad algorithm in the ridge logistic model function of the sample size n, for 7 0.5 y 0.75, with without truncation.
setting. This is espocially important since, most machine learning applications, and particularly in doep learning, the function to be minimized is typically non-convex (lypically, for neural networks).
7 Proofs
Throughout our proofs, to alleviate notations, we will denote by the same way ||-|| the Fuclidean norm of Rd and the spectral norm for square matrices. Moreover, since always assume Assumption (A1), we denote by C₁, C2 C2, C22 constants such that for all E Rd
E
[X s Ci + C2 II4 0
E (XV SC + C. l| 0
(12)
7.1
Sketch of the proofs and useful proposition
7.1.1 Proofs of the results of Section 3
The proofs of Theorem 3.1 and Theorem rely on the following Taylor's decomposition of the function G.
Denoting Vn G (0.) G()) and go+1 vg (Xn+1, 0x),
Vn+1 S Vn Tn+1 (0.)" Angh+1 + LVG 2 m ||A |19h41 112.
Then, taking the conditional expectation, comes
E [ < V mi+1 (e,) A. (G,)) + LvG 2 ||Am.11 [| 1|" |FF
2
Furthermore, since Assumption (A4) implies that G(h) G(O) S 2nd |VG(1)] for h E Rd,, and thanks to Assumption (A1), it comes
E [Va+1] < (1 11-2 (Aa) C2l.vG
G.vo
||
E EVV.
+
2241 ||
P
2
Then, the goal of the proofs of both theorems to control the cigenvalues of A, the latter incquality and then to deduce general bound on E [V.] by using Proposition 7.1
the stochastic bound on Amin (A,) from Assumption (Hla) and the deterministic bound on ||A.||
from Assumption (H1b) yield first. bound given in Theorem 3.1
16

---

Published in Transactions on Machine Learning Research (06/2025)
2. further assuming bound on the first moments of ||A,]] (see Assumption (H2a-H2b)) yields
refined bound in Theorem 3.2 The exact same pattern of proof also yields a bound on E [V]] in
Proposition 3.2
To prove Theorem 3.3 we use the defining recursion relation of On
0a+1 =0,- 7h+11 An Vng (Xn+1; 0x);
and, with the aim of using Assumption (H3), we write A, H-1 + (An H-1) and take the square of the
latter relation to get
|10 - 011 - 110n - 0112 2/++1 (gn+1. H (0n - 0)) -2 ((An - H 11 In+1, On - 0)
+ 2 | 9n+1 1²
2 ||An - H 11 ||
The last three error terms can be controlled by Assumptions (A1') and (A3) and by the crude bound on E [V2] obtained from Proposition 3.2 remark that the penultimate term is the main contribution to the constant in front of the n>> term in the final bound of Theorem 3.3 The second crror term is the one contributing to the exponential term in the final bound. The crucial point that, after taking conditional expectation on Fn, this second term simplifies into
E [2m+1 (9h41, H (0,, 0)) [F,] =2 H (0,, -0)
=2 (H (H - 0) + (10 011)) 0, - 0)
2 |00, - 0|1 (1 + (10,, - 01))),
where o(110, 0]] is error term controlled by Assumption (A5) and Proposition
3.2
The proof of Thcorem 3.4 consists in checking the hypothesis of Thcorem 3.2 The only delicate part is the
proof of Assumption (H2a-H2b)- in order to get bounds on the moments of the preconditioner A, in the case of Adagrad, one needs to first use a convergence of 0n towards by using Theorem 3.1 and the strong
convexity of G (see Lemma 7.4 and Lemma 7.5
7.1.2 Proofs of the results of Section 4 and Section
The proof of the results of Section 4 and Section 5 mainly consist in checking all necessary hypotheses to apply Theorem 3.3 and Theorem 3.4 Most computations are straightforward, except when considering the Stochastic Newlon algorithm, for which checking Assumption (H2a-H2b) in the case of the linear regression and Assumption (H3) in the generalized linear case are slightly more delicate.
In the case of the stochastic Newton algorithm for the lincar regression, needs to have lower bound Omin ( + - x,X²") in order to get bounds on the moments of A, (see Proposition 7.3 Since the bound on the moments has to be independent of n, we use a general result from random matrix theory, see Koltchinskii & Mendelson (0015). This only holds for random vectors X; having certain non-degeneracy condition which is described by the constant LMK appearing in the statement of Theorem
In the case of the generalized linear regression, Assumption (H2a-H2b) is directly implied by the regularizing term. However, Assumption (H3) is not straightforward, since A, depends on (04) (which was not the case for the linear regression). In order to prove this assumption, one first applies Theorem 3.2 and the strong convexity to get a first convergence result of 6, towards 0. This then allow us to prove Assumption (H3) in Proposition 7.7
7.2 A useful inequality
The last step all the proofs of the main results consists in applying the following technical result from Goodichon- Baggiooi et al., 2021 Proposition A.5) adequate sequences.
Proposition 7.1. Let (11)211, (10421, and (21)221 some positive and decreasing sequences and let (6))
salisfying the following:
17

---

Published in Transactions on Machine Learning Research (06/2025)
The sequence & follows the recursive relation:
8, S (1 - 2wy m)7)) 6c-1 M17
(13)
with 6p and 0.
Let "t and nt converge to O.
Let lo inf (1 2 1 S wh, and let suppose that for all 1 2 to + one has win S 1.
Then, for all E N, we have the upper bound:
de exp
-w Σ 71
exp
2
7/7
6o
2 max
Vi T}:
+- Pe-
t/25ist
j=t/2
with the convention that E 0 if t/2 < to.
7.3 Proof of Theorem 3.1
Remark that thanks to Taylor's expansion of the gradient, denoting Vn G G(0) and Int1 Vag (Xn+1,0,) On),
14 S Vn - m+1 (O,) Anguti + Loa 2 || 11 11?
2
S Vn - 7 VG (0n)² Angut + LvG Bat
1 15-111
(14)
where we used Hypothosis (H1b) on the last line. Then, taking the conditional expectation, thanks to assumption (A1), and since |00, Ø|I < 2
Vn.
C2LvG 82 E V (1+
1 Bntt Vn - (G- VG + CivGG 2 1
Furthermore, since Assumption (A4) implies that G(h) G(0) < 2n [G(()]] for h E IRd, it comes
(O,)))" A, A.VG(( 2 Amin (A,) VG (0,))l
2 2nnuVn Ammin (A,,, )2>
2\,uVnn - 1 Ammin (An)<d, 2Am
(15)
with An Ao 1)a with 0 5 05A<1-7 Applying Cauchy-Schward yields
E (G,)))" A. V.V
22e [V,] 2A BlV Dmmio (An) An)
22 [Vn] - 2An /P Dmmin (An) < Anls
with 22 2 sup. E[[] calculated later. Then, Assumption (H1a) gives P Pmmin (An) < Aa1 S en +
d Ün. so that
E [n+z1] x 01- 21-2uu 1) " +
C2TNG 32 s
E [Va]
P
C. 2
+ 2No(n + 1)-
2 1
18

---

Published in Transactions on Machine Learning Research (06/2025)
In order to apply Proposition 7.1 let denote
22-20 2-20-A Cм max C2Lvo (mAo)
Cy
(16)
the last upper bound being added so that the terms of equation Proposition 7.1 Set 7n c,n -(n))) and remark that
17
below satisfy the third condition of
B [[ S (1- (1-2ppe 2 Cm(n + m
1 B [[] 2No Vun
C Liv
+ 2
(n + 11 fht1-
(17)
Then, since 2
- 23 -1 1 + 1, with the help of Proposition
7.1 and an integral test for convergence to get
E k29 27 11 [2y-28-1] and Ei=[n/2] 6- 1-2
y(1+20-22)* 2-)+
2 n'-7 for y E (0,1),
[Vn] exp -G,dAon (1+31) exp 20Mc, (1 1+
127 -11 ))
n111-88-21)
A
CLLVERyCy
CiLva n 8 2n/22 + 2V V
[V[o] +
CM
max 15k5n
Vok 2-
Cm
21-
(18)
where we recall that ün un+1(n + 1) 11-88-01 2 Dminn (An) An). Remark that
2 Vok /uk+i 1)7 20 (ks 1) (6+44)/22 = /vuk+i (k -/
so that maxosken 1)3-29-A Vox maxiskEn41 KT 23-22-5/2-12 11-222882-0222-1-111 Vok. Hence, we get
127 - 23 - )1)
n(1422-21)1
))
E [ S exp (-cyHAdn' exp 20mc, 1+
[ + 4 AoHUV
12-29 29 29-2222-22212 (/22211))) V + CLLvac
max 15kgn+1
CM
Cm
GLTGGE 2342-y
21+(++))/22 10/2/ (6+aA)/2 27-288
nbo
where V is defined in Lemma 7.1 Hence, long 7 X (1 + - 2 < 1 .wiich is satisfied since
X < min (-- 28, 1 7), we have
E Vn S exp --tt)) - (1e(i))
(KT)) + +K(I
47-23-6/2-(q/2+11) /uk
max
1gkš++1
+ K2 - (7- 28- + k(
(1)
(8-
/Uln/2jn1 (0+021/2
with
e'(n) 20 -+A++
n2 ((1429-27)
1+
(19)
μdo
127 - 2,3 -1
K(L') -4 = Aopv
k(O) [Vo] +
(20)
CM
Cm
where CM is given in equation 16 and V in Lemnma
7.1
and
C
K(O' = 27
K( = 26
(21)
Mdo
19

---

Published in Transactions on Machine Learning Research (06/2025)
Lemma 7.1. Suppose Assumption (A1) for p 2 2 and (H1b) hold. Then, for all n 2 0, if 1/2 then
E [
I e
2
max
{1, [v]]] == V
and if S 1/2 then
1 7-2タ-2²
22.122 7-28-X
1 Sog
Grogap pp
1
E B & exp
- 1
2 GoGap
1+
V
1 7 X
1 27 + 23
with 02 given in equation 79 and ap is given by equation
78 for
2.
The proof of this Lemma is given in Section
7.4 Proof of Theorem 3.2
Remark that thanks to Assumption (H1b), one has
|m 1 + C2Lva |A Vn SC + -hat1
C2I.VG Vn,
|| || 3|
|
I Ci
Moreover, with the help of Assumption (H2a),
C2 Vn
E
|| 2 1
S C.Css + Bat1
leading as in the proof of Theorem 3.1
E [Vn+1l] S (1- (1-2 11-2p00 + C2Lva 82 2
1
pntiln+t)
[V,]]] + 2 intipB mE [IAmalAAn) Vnl
CILval3 2 + 2 7n+1.
Using Hölder incquality with yiclds then
[ MAnn Vn] s (P (A,) ]) x E 1/ S in p-1
Vp
with on = (n+ 1) and Vp given in Lemma
7.1
Considering CAs defined by
2--29 2- C2LvaeBe (udD) G
Cm max
(22)
1
one has
E Vn+1 S (11 1p4 + Cmr(n (n 1128
mm+1)
E [.] + 2No Vp
Cive
7n41
Then, applying Proposition 7.1 and with the help of integral tests for convergence, it comes
12y - 23 n(1+29-21)+
E Val I exp (-c,udont exp 20MM 1 127
-11)
E [V)] + \ maxicken ke -
28 Ut
CLIvOC
p-1 2V
Cm
Cm
n1/2
+ 27 CITvOC, -7
(23)
20

---

Published in Transactions on Machine Learning Research (06/2025)
Concluding as in the proof of Theorem 3.1 we get
[Vr]] exp (-c,udon" - 1- (1 =())))
(k13) +K
uk y-1
kT-28- 222
max
15/5#+1
p + K2
5 K3 11 7
|n/22" "
with
2n 147
n (1+22--21)
<(n)
1
(24)
127 23 - 1
where Cm is defined by equation 22 and
k!3) [[[o]
CLLVOC,'')
K
4 A0pue22
(25)
Cm
Cm
k((² 22+85 Vip
(26)
CILVGC,
KS² 27-1
(27)
7.5 Proofs of Theorem 3.3 and Corollary 3.1
Proof of Theorem 3.3 Remark that one can rewrite
ont1 - 0 = On - 0 7n+ 11
11ll--1 9utz - 7n+1 (An 11 11 In+1
leading, since H is symmetric, to
||0 - 011 < ||0, - -012 2/n+1 ( H1 (0n - -0) 2/n+1 ((An - 1) Su+1, On - 0)
+ 2 || gh+t 2 + 2 ||An- - H 111 ||attl1?
First, thanks to Assumption (A3) and by Mauchy-Schwarz incquality,
= E [2m+1 ((An - 1 In Bn - -0) [F = 2n (An--H-)) 1) VG (0n), ,0, -6)
< 2L ||A,, H 110, 011
Then, using Assumption (A1'), one has
(**) = E 2 H 1 11211,1, [Fn] < 4n Tr (H (H-1 + 47 ||--1|1 Lv, 110, 011
Finally, one has
(* * = - (Sh+1, H (0n (0n-6) [F,] < 2 10,, 0 + 2 H 11| |,, 10, 011
with, using Assumption (A5), || := VC (0.) H (0.. 0)1 S Ls 100,, 0112 Hence,
(* x) < - |00, - -0112 + r || | L8 0 011
which yields, using that ||0, - 0 < 20 0 1 + 110, 011 with || 1 Ls.
(***) < - 7o+1 110, - 0ll M+ || L3 110, 01
Furthermore,
(****) = E 2 [2x))) An,
.. 112 9 112 |F
< 2 A| 112 Ci + 2 C2 || -H-1 |00, -011
< 2 m+ || -11 C₁ + C2
11 011 + C2 ||A, 1- 11
21

---

Published in Transactions on Machine Learning Research (06/2025)
As conclusion, one has (after using Cauchy-Schwarrd inequality on (+)),
B B1110==1 - 011]]
(1
7n+1 + +.4 1| 2 Tv, E
[10. 013] + 4n Tr (H-
+ n++1 (1|41-11 L3 + C2) 18 110₂ - 011| C22 1B |||An H1 21199
+ 20 20 1 E ||4,
- H 11 2 1 |10 110n-811 011]| E -1 - -1-1112
leading, using Proposition 3.2 with the fact that E [110n 011 S b/ [V.] by (A2), and (H2b) and (H3).
to
E 11
0]1]] = 1 M+ +4 + Pat1 Lvg)
E |10, -01²]
+ + Tr (H~IIH-1
+ m+1 2| L3 C2s
Mn
+
+0 23
1
112
LVG VMnUAn
+ 2017n UAn + 2nn+11
(1 7n+1 + 4 H-| r LFg)
|100, - -01²]
1.3
4M,
+ Yat1"
4 Tr (H-1SH +
+ C2
112
112
+ C2 23 (cs
11
+ +2017+11AA +
LvG
VMauAn
#
Finally, let us denote CA = Cy max {1 11
Tvg 3
11
Then, with the help of Proposition
7.1
one has
E 110 0/1] se topal-
2 21
1100 011
8Tr (H- t.y
16C2 (n 4 + Cgg)
4C1VA.
E
CA
CA
CA
- - 2015 -
max (k: + 1)7
L.g -2 + +C2 Mk-1
CAp / MM-IIAAK-1
LoG
Iskšn
I,CAA
2 c. Tr (H-IEH-1)
8
Li
+ C2
Ma,2+ + 8LVG
/ MMn/20Am/2
117
n2
1
21-21 C2cy (1-1+ + 03) 2
22+ getCceeUAm1
n2t
n
Finally;
E
[10, 0013] S e jo
(x(3) + ((9))
max dx + 1)²*) oskšn
+n 23 Ir (1I (1-1 + K
+ k UA.a/2
+ dd1n/21-
nt
with
xx33 =c
20 IN-T
2 27
E 1100 [ +
8Tr (H-1H-111
+
160s (M- + C33) +C')
+
4CTUA,0
(28)
CA
CA
CA
Liu 2+ C2
119)
20
2 27
Ii,
dn -L / M.UA,, +
Mn.
(29)
CA
112
where we recall that CA = c. max {+| [4|11-112 L = and
11
x(00 21+2 (1-1 C3) Eg.
K - 2
(30)
22

---

Published in Transactions on Machine Learning Research (06/2025)
Proof of Corollary 3.1 Remark that as long as 6 p 27, by Proposition 3.2 and the following discussion,
(K: + 1)7 MMUAA 1
C2
max dk + 1)7 0sksn
max osksn
MR
1²
SLVGVEA. 0
Lzf
C2
V /wo (27) +8
w (7).
12
Likewise,
2 Woc Wo (27)
Ma/2
22
Hence, plugging these inequalities into Theorem 3.3 yields
(3)
E 10. - 011] Sn 2 (H-
K2
K:1a
UA.a22 + K22)
+
n² +
VUAu/2
+ k1 e =2
with
k(3)
k(0) (3) + K|3))
(8IvaVUA,
V /0o (27) + 8 12211 2 + C2 woo (c)(()))
(31)
Gy
112
K3(3) K2² +2 13 -2 + C2 22% Woo (27),
KL/ (3) k(3)) -22+" LonL wwo (2)).
(32)
22
7.6 Proof of Theorem 3.4
3.2 We first need to check that (An M2)n2 satisfies Assumptions (Hia), (H1b) and (H2). Assumption (H1b) is given by construction (see equation while (H1a) is given by the following lemma:
To prove this theorem, we will apply Theorem
Lemma 7.2. Assume (A1) is satisfied for some p > 2. Then, for all 0 <t<,,
PP [(Amin (An) < cal) S S., 22
with
Un c ( Σ
P
V
Cfl
ak
71
μP
The proof is given in Appendix B Remark that IE [V/]= < too by Lemmaa 7.1 with (A1). Assume from now
that p 2 and let p' 2(1-7) and X = (1 101-)(0 7) 2.3). Remark that X 7, X < 7 2,3 and p' < p. Hence, applying Proposition 3.1 with Ao = Cg, 0, q 2p,
VP s sexp (appp-ooont-att11-eee (1- E'(n))
k + ((!)) max 2 1-228-2-((p22)) 2(p 2('--')> 22
1sksat1
(1') vdd
+ K ) 1'1-111-2-1))) + Kg
(n + 1) 1)
2(p-p'11
Uno
with e((n), k(L), K(l),, k. and KS²² respectively given in equation 67 equation do cg. By the choice of X,p' one has
68 and equation 70 with
p'(7 - 23 - A) = 2(1 7) 7)
2 ~ 7(7 - 2:3) = 2(p p))),
23

---

Published in Transactions on Machine Learning Research (06/2025)
that
E VP n
S Kı
exp -101 =1 + K2(n + 1)
20 2/167 200 p = Cp
(33)
with
K = 10
K2 K2 + K33
(1 20
By strong convexity, can obtain first rate of convergence of the estimates, The following lemma enables to ensure that (Hla) is satisfied, but with a possibly better rate than with Lemma 7.2 Lemma 7.3. Assume (A1) satisfied for some p > Then,
P[Amin (An) < Ao} S vp log(n 1
20 20)
(n +
with Ao
201-2) p
(C 2-7
+1]
+
and vo is given in equation 85 with p' 2(1-2) 2-7 p.
The proof is given in Appendix (A6) holds.
B We can also deduce from equation 33 a bound on IE [[]AAx]] [1
in case only
Lemma 7.4. Assume Assumptions (A1)-(A6) and (A1') hold for some p 2. Then, for B
(1-2)2(-2222 28)8 1/4], the sequence of random matrices (An) defined by equation. verifies 4(2-))
min
E |m| s C3.
with C3 given in equation 86
The proof is given in Appendix B If the stronger hypothesis (A6') holds, an improved and simpler bound on E [[| [1] can be reached, as next lemma shows.
Lemma 7.5. Assume Assumptions (A1)-(A6') and (A1') hold for some p 2. Then, for 3 < min 1/4}, the sequence of random matrices (An) defined by equation 2 verifies
E [1| < C3,
with C3 given in equation
87
The proof is given Appendix Theorem 3.4
then a consequence of Theorem 3.2 whose hypotheses are
satisfied thanks to Lemma 7.2 and 7.4 (or 7.5). We then have
E [V] S exp -o (1 =(n)))
k((2) + K(
k² 29
2-16
max 15inn1
UK
2 (n-1) min 201-))1(h2887 (2) v |1/21"
K.
K3 (2)
n
with (2) k k and (2) respectively given in equation
25 equation 26 and equation 27 with
min 201 2(1-))<7 28)p Ao given in equation 84 Up = un log + 1) with vo given in equation and Cs
2-y
given equation
86 or equation 87 depending on whether (A6) or (A6') holds. By strong convexity
0, || < K exp (-cyuunn' E(n)) + k:(4) (up log(n + 1)) = (--1) mine 2u 20-322 2010 11
2-y
(4)
3
with do defined in equation
84
20 -40-)---00--0--001111
(11420-2))*
E(n)
(1 12 - 2/ 1
(34)
uāo
with
2k (4)
2K (4)
K(C0
2
KK + k.
00
k((0)
K
(35)
P
where 0g is given in equation
85
24

---

Published in Transactions on Machine Learning Research (06/2025)
7.7 Proofs of Theorem 4.1 Corollary 4.1 and Theorem 4.2
The proof relies on the verification of each assumption needed in Theorem 3.3
Verifying Assumptions (A1), (A1') to (A6). First, remark that
\V (X,Y, A>Il - Ix - X"O c) x S | |X| + ||]] | 011
Then, if X and respectively admit moments of order 4p and 2p, since and X independent,
E IV Ng (X,Y, 11
(2p) C(2p) || 01)
with (()) "1e4 and Cas = 2 || In particular case, if 2 2, Assumption
(A1) is verified. Furthermore, since for all h, G(h) E [Xx]] is positive, (A2) to (A4) hold with
/ Amin [E [XX]]) Amins Lvg Amax (B [xx]] Amax and (A5) holds with L8 0. Finally Assumption (A1') is verified since
E (X,, Vng (X, X,0)1
=E || (h 0)x
< ||I||*] || 01I
We now prove Theorem 4.1
Proof of Theorem Verifying Assumption (H1) for stochastic Newton algorithm. Let us first an check Assumption (H1) for Sn = n+m [mSo + Σi=1 X,X
Lemma 7.6. Suppose that X admits 4p-moments, with 2. Then, for do x we have
Dunin (5p²)
20 6n
with
2P-1
Ün E (|
(IZ)) 1/2 (E (1111)) + m² |S611" n-
where X 1
[|] and Ci(p), C2(p) are numerical constants given in Rosenthal inequality, see
Pinelis 1994)
If moreover X is subgaussian with subgaussian norm || and m
nB 1 S
then set
Un 2exp
X 1
with numeric.
The proof is given in Section
| To deal with 3n min(n S
S., one first needs the following control on
the behavior of Amm (S,). Set H E [Xx].
Proposition 7.2 (See Koltchinskii & Mendelson (0115). Theorem 1.5 and Theorem 3.3). Suppose that 0 Lain H E Xx' I Amaxta and that there erists LMK > 0 such that E [)] < LMRE [MRE[1(Xtt [|(X,))] for all 1d-1 Then, for eıd,
1 Σ i=1
p Amin
X
S C2
< 2eep (-c3n),
with C₁
2 (
X
C2
Amtn 8V2L
and C3
128L4
MM
25

---

Published in Transactions on Machine Learning Research (06/2025)
Remark that the constant C1 C2 and C3 are fairly explicit in terms of Lak and Xmin- For the latter result and Lemma 7.6 and Proposition 7.2 we deduce Hypothesis (Hn) for Sn. We will need several times the threshold
1/8 c2 (3 1+ (
Sol
max cıd,
(36)
EE X
Lemma 7.7. Suppose that X satisfies hypothesis of Proposition Them, for Ào= 2a, Bl XTT we have
7.2 and admits 4p-moments, with > 2.
P
< 20} S Unti(n + +1) 1)- (xmin (
with p/2, Un+1 = (n + 1)00 for n S no and, for n2 > n1.
Un 2exp( C 2P-1 (C2(p) |21111/2 + C( - mp || n pp/2
(37)
where C1 C2: C3 are given in Proposition 7.2 (p) and C2(p) are numerical constants depending on p and Z 2 E |||
In the case X is subgaussian with subgaussian norm || Il for 2 no, one has instead
( (_n((B]IXX(P))
)
En = exp( (xpp + exp
nP/2
(38)
X 1/22
with c > same as in Lemma 7.6
The proof is given in Section C In particular, in the subgaussian case and for 2
Un 0 (exp(-c1))
(39)
for some constant only dopending on ||x|| and || As a particular case, Assumption (Hla) is verified with a rate p/2 when 7 >> 1/2.
Verifying Assumption (H2) for stochastic Newton algorithm. A straightforward doduction of the above lemma is the following.
Lemma 7.8.
Suppose that hypothesis of Proposition 7.2 holds and that X admils moment of order 4p
with > 2. Then, for all k > 0, we have
< 2 exp(-cap) + (2-c2/2) E |1IS MM
for n 2 cid.V and
E || < [d 1
K
a
for n S e m, with Cı, 02 C3 given in Proposition 7.2
The proof given in Section Finally, the following proposition gives a precise bound for Assumption (H2).
Proposition 7.3. Suppose that hypothesis of Proposition 7.2 hold and that X admits moment of order 4p
with > 2. Then
2,9
[c +2
|| |1]}
12) < c
E 1- 11] < max
203
+ (a_ 02/2)-
eC3
26

---

Published in Transactions on Machine Learning Research (06/2025)
and
4
c1d+2
E [[|
max 20g
+ (a_c2/2)
||5o
s <Cs
ec3
for all 2 0, with Cs max
203
48
28
+ (a (2/22-²/)
2
cid+2 a-
|50'11 1s5
1/4
EDS
The proof is given in Section
Remark that Cs = O(d).
A first convergence result. Since in the case of the lincar model, one as C1 0(2): C/ (4); C2 C(2), C222 = C(s), LvG = Amax. / Amin+ do [=||I 8 = p/2, Proposition now be written as follows:
Proposition 7.4. Suppose that there p > such that X,E respectively admit moments of orders 4p and 2p. Suppose also that there is a positive constant LMK such that for any h E VEI1XX1 I L [|] Then, denoting Amin and Amax the smallest and largest eigenvalues of [xx],
)
( (A122, 1,fin + K
[ I exp
Amin n2tr)
max ISkS++
T Uk
2-2
R-2
4I
X
K2 (2')
2,
27
+
k22) (p-2)//p (p-2)/2 = Cn,
3,1mn
[n/2]]
with Un given in equation 37 in the general case and in equation
38 in the subgaussian case, and
K (22)) = e 20 in 2222
20
E [v.]]
201,unc
K (22))
20 in 27
4Amin V2
p.tin
1,86
e
aM
aM Nn B
|
21+27 a1
Rin c
||111
21/2+1
(2')
V-2
2,1m
3
3,16n
3
p.lin
where, recalling the notations (()) = 2B |c|" E |X1|
and C(1) = 2 ||
2n 2.
2 2AmaaC12
212
3
2-28
OMMiin == max
(4C() + GuncEe))
c Ge
Crty
Amii
X2
min
41
||x1|
1G1
max oay 1|
20% [[|x)11
with Cs given by Proposition 7.3 a1 = CgS X2
Tayc 2
+
and
max
x
min
Amtn
E [V S E Sp 2n
2 27 29
max [V,")
Vp
where
Up,un :-
C(2)
+
(2)
+ 2 2p-2(p
1)p2
(203 ((1) +
4C(a)
+
20
4C(22)
Amin
2
Amin
+ 22 2p- 1)pdp
22-22
2p-2
((2p) +
X2 min
+ 2 p-2
2
(2p)
X2
2p
2
1
+
/Crp )) (40)
Remark that putting logether the above expressions yields that, in the subgaussian case and for n 2 2no for no defined in equation 36
Cn.lin O (exp(-Cn-~>) E [ + (+(66-1)6--2)/28)))
p.lin) + -22
27
V2 pllin exp
p (-P-2 c' )
(41)
2p
Verifying Assumption (H3) for stochastic Newton algorithm. Hypothesis (H3) is then a straight- forward combination of the convergence of S, towards H, together with Hypothesis (H2).
27

---

Published in Transactions on Machine Learning Research (06/2025)
Lemma 7.9. Suppose that X admits moments of order 2p with p 4, and let suppose well that the distribution of X salisfies hypothesis of Proposition 7.2
Then, for 2 no (with no defined in equation 36),
16a+ (1sSoll (E [1X] 2/D
2 11
2E
X
E n1 -
E
-calp-2)n) 2)n/2
(42)
(Amin 3mn)
(n m) O 02/22²
2|1mS H1?
2C.
Q (115011 E 12) =: UHH
(43)
(n + m)? ac2/2
n
For no, we simply bound
17-119 max
2
E
S
H
X2
min
20 UH,00
UHH
Remark that UH = O (+) uniformly on m 2 1. By Lemma
7.7 (H1a) is satisfied with 8 = p/2.. Applying
Theorem 3.3 with the constants computed in the previous lemmas and proposition, we get finally,
100- -11] S --amm
(K(3)) 1,lin
+
k(3)
1r,inn
max da + 1)7 oSksn
K-(3)
n
23 c [e2] Tr 1H-
2,
+
K2
2
(3)
Jin 1/,n/ + d(n/2j
with UH,a defined by equation 43 recalling that Amin and Amax the smallest and largest eigenvalues of
E [x"], and since for the linear case one has CA = 4c, X
2 4c,,
2 A
2 2 Tr (H-1)
(3) 1,1iu
cq
I
E 10 -113]
+ 40(2) (A + C3}) + (2
Cy
Cy
2|13119
C(2)
k-(3)
1ln
4cy
e
2
dn = 8dmax v Cn, UHn +
X
Cn.lin
k-(3)
=22222 Ci2)e (Amin + C3S) cg. k 22)
21+22
(44)
and Gnlin and C3 respectively defined in Propositions 7.4 and 7.3
From the asymptotic behavior of uHHn and Cn, (see equation 41 and the bound Vp,tin in terms of E [V?"] given in Proposition 7.4 we deduce that, for n 2 2no:
dn = of Texpp(CCn (B [V]]] + m + 1)62 2) 100-1)1222/10000
(V
+ E [V8]
2/n exp
PPP2 1 n
dn
(45)
2p
We can deduce Corollary 4.1 from Theorem 4.1
Remark first that we have the following rough bound on
E [22] for the usual stochastic Newton algorithm with adaptive matrix An = 5-1 with an = 1, m m= 1.
Lemma 7.10. Let V, = G(On) for the stochastic Newton algorithmm with An = 5-1, Then,
E B S exp 1)- + Ctm,,1 27 )
13-24
1 Clin (p+ - -py
n(x+1)-p1
[V7],
with Ctin,1 and Ctin, given in equation 97
28

---

Published in Transactions on Machine Learning Research (06/2025)
Proof of Corollary 4.1 Set ma [Rlog(n)] + with R > 0 to tune later, and let (0x)n20 be the sequence induced by the stochastic Newton algorithm with m = Ot = 1 for n 2 1, initial estimated Hessian matrix So and starting point Po- Set 8o- = m and set 0n for the n-step of the regularized stochastic Newton algorithm with respect to the sequence random variables (Xmo+ks cmo+x) paramcters m = ma + 1, (x+1)*
initial estimator of the Hessian So 1 (So + 1 XxxX),, On (m+1+ and B 0, cB 22²" (with
2g given in Proposition 7.2 Then, remark that the event Bm (o 2 e, 0}, On 0 mo indeed on this event, by the choice of the previous parameters and simple recursion,
On+1 = + an An V
Emp Emo+k+1),
Mo+
))
=motn + + n +m
So +
Σ XxXX k=1
Vng((X cmo-n+1), ( mo)
mg + n2 +
-0mo+nt1-
Hence, for n 2 mo 1, by Markov's inequality
P 0| A|| > c) =P (flle, - > c} n Bmol + [ 01 > c) n B
PP [{ 00 n-mo - 011 > }} Bmo]] IP [Bmo]
00 0|]3]
+ P B
(46)
2
Suppose that n 2 2 max(ni, mo), with no given in equation 36 for m = mg. By Theorem 4.1 and the fact that n 2 2mo,
E 01 n-
0|] -(n mo)
2 Tr (H-1)
0 (o- (B[])0 - 0113| dn-m(n (17) -
dl d(n/2l)
(47)
Set V/- G(0)) G(0) and let bound dn/2 and da-ma- By Lemma 7.10 and the fact that Vo Vmo with V. G(0mg) G(f), and mo R log n,
B[V," = e ( = O (exp (C' log(n))3322 B((3")).
(48)
for some constant C, C' > Hence, by equation
45
dn = ( exx (-On' 2/
for constant C >
only depending the first moments of X and the parameters of the algorithm.
Therefore, using the strong convexity and Lemma 7.10 to bound E|l66 0| in equation 48 get, for n 2 2 max max mo),
finally
o e (m-mo)) 1 (I[110 0|]3| + dn-m(n (n 1)?) + 1 + d/m/21
n
0 e Jen 1-7
(E11812/0)+
+
(49)
71
with с > 0 only depending on the first moments of X and the parameters of the algorithm. Finally, by Proposition 7.2 and choosing R = 2x yields
1
IP
mo
<
P
Amin
Xix?
S
<2 Σ exp (-03n)
12.
1=1
n2ma
2
C exp( exp(-camo)
(50)
1 cxp( -Ca)
29

---

Published in Transactions on Machine Learning Research (06/2025)
for some C O. Putting equation 50 and equation 47 together with equation 49 2 2 max ma),
in equation 46
yields, for
(0 ( ( E[V0 n !
P 0 e|| 6) 22
Tr (H-1) +0
+ Onn
Finally, since mo = log n + Twith 21 and no max(cid, Cmo) for some constant on the second moment of X, d and So (sce equation 36), we deduce that n Z max(ng, mo) as long n 2 co, where co is a threshold only depending on y, So and the second moment of X.
depending
Proof of Theorem 4.2 Let us first prove that Assumption (A6') is fulfilled. For all h,
Vg (X, (x (X,Y,
=E (Y - x² xX"
E E + E
xx_]
and (A6') is satisfied with a = E [e2] Amin. Hence, we have by equation 87
4V
4d (1+ 0(1) O(1) + C(4)
X
E [1
C Sodda
E [ min
with V/2 given by Lemma 7.1 for = 2. Then, applying Theorem
E [
0|
i,linn exp (-c Amin A 0,lin - (1
add
En,lin)
p=1 (p-1) min 2(1 2(1-1))(1 2(1-n)1(1-28pp
2, (vode, log(n + 1))
Kado
2-2
with 00tin
4(1-2) 2-7
C (201111)
+ +
4p11
and, recalling that Amin and Amax are the smallest and
largest eigenvalues of [XX]]
aad Mflin n 1+(1 (1(1)))(2 8047
14 (1428--21
ada nntin
(51)
Amin Xada 0,tin
127 2---5 23
2
Caty (m)
Sadaa
Aada Voda 4dmin
0,ton p.lin
1,lin
Amiin
[Vo]
E
Cadda M.lin
Crada
(52)
Mikin
2p/2+3/2 3/2
vado p.lin
(53)
Amii
2d Amax (2) C2 S,ada
Kadl
(54)
X2 aada min
0,tia
2:1-m)
201 22 d2 2-
201 7)
o ((1))))
+2 2-
((1-)) 2-7
p.ada
where 00 dM((3) +
miin
2l
2-
Codo
M.lin = max
C(3) Xmax Ezcy
(Amin
adaa
2x 22 Cj
7-20
Amin
and
In x 7-28-27
1:2
2702 ada
oz ade
pit PAmin
n fine
PAmin Xg
pdmmm Yob
1+
1--
1+
27
VB
Piada = e
30

---

Published in Transactions on Machine Learning Research (06/2025)
where
adda pilin
= ( (22)
(2)
+ +2 20- 11m max
(11) +
(4)
+
20)
(2
Amin
min
/4
min
cy 63 2 222 ((2p) + (²((2))
2p
((2p) )))
+ 2p
1)p
max
X
c
?
p-2
(2p)
+
X
2
+
V
(55)
and
(0
4
8X
(2))
812
C(4)
ado 2,
012) +
Amin
+
Amin
(2) +
max
2 min
+ 21
max
C3) +
2.2
max
10222
(56)
7.8 Proof of Theorem 5.1
The proof relies on the verification of each Assumption in Theorem 3.3
Verifying Assumptions (A1), (A1') to (A6). First, remark that taking for all 0 S S 2p, one has
E V (Y, X + =oll""]
< 2 E
V (Y, x 0,) x + =0.11")
+ 2 E
1 (Y, x X - Vne (Y, X + (h --)11"
s 2 L7 2 E [L |X +0)* || 0-
(57)
=:0
and Assumption (A1) so verified. In a same way,
E I (X Vag (x.0,))1² E [T +0)²] |1/ - 0a11² s <c(l I| 0zl1
and (A1') is verified. Remark that (A2) and (A4) are satisfied by hypothosis. For (A3), one has
|| X²)) xxx rldهll S Tii [|]]]] + CCLM-
(58)
Observe that Assumption (A5) given by (GLM1) while for Assumption (A6), (GLM3) together equa- tion 11 which yields
(vng(X,8.)) =E (Y, Xx + a(0))al > a
for all 1 < k < d.
Verifying Assumption (H1). The following lemma ensures that Assumption (H1) is fulfilled.
Lemma 7.11. Assume first equation 7 and that X admits a moment of order 2p for some p > 2. In the
regularized case defined by equation g denoting No 21.,E[1|x]]]] we have
P Xmiin
(5," < do] s (1
with
2-
(n+
(n+ 1)p/2
||S.11" + Ci(
E [[TT]]
Un+1
[1x|]]
+ +0)"
np
np-1
n1 n
P/2
(B (1(111))02
1/2
+ Cz(p)
Lzi where T= Lov (1 E [[xx1]] (Ixxi)) + a (1212-1) and Z being a stondard d-dimensional random variable
independent of X. In addition, Ci (p) and (2()) given in Pinelis (194))
31

---

Published in Transactions on Machine Learning Research (06/2025)
The proof is given in Appendix D
Verifying Assumption (H2). The following proposition ensures that (H2) is fulfilled.
Proposition 7.5. Considering from the regularized problem given by equalion one has for all n 2 0,
| S 2d max { (0-155'1] Cs.o
Remark 7.1. Remark that if equation hypothesis of Proposition 7.2 for all n
holds for some constant 0 and E [XX'] is positive, under 0 and for
0, one has
|| 11
$ a²
1
max
20
2/
2
+ c 2 ((cd + (c] 1)) S CS
EC3
1
23
43
[ n
11
max
20g
+ + (lad 1) 1)² 5 C5.0
a²
EC3
28
with C, oe max
20
+
022
((od + 1) +||||sT]
EEg
A first result
Remark that one can rewrite Proposition 3.2 as follows:
Proposition 7.6. Suppose there crists p 2 such that X admits a 2p-th order moment and that there is
Lo verifying
Val (Y, (T,) [ ( + 000 s L.P
(59)
Then,
E V2
<exp
(-
3eg ACGLMM
((22) (2) nt-r)
I,, 11M
K
UK k 2
p-2
1skšn+1
(2')
2,GLM
27
3,GLM
(2')
(p-2)/P
n/2
n
(p- 2)/2 =: Un, GLM:
with Un defined in Lemma and equation 57
7.11 Cs. defined in Lemma
7.5 COLM and ((a)
GLM defined in equations equation 58
GAIA 3
4LA
01,GLM S.0 COLM
+ Lc
4CCLMCOLL GLM
2CoIS 0²
(8C GLM + 8C & c.3...
30 (CGLM
2
dM,GLM max
C
(222)
20 27
27
E [Vo]
201 GLMC
KiGGM = exp
27-11
@M.GLM
(2(2)
27
4o 4oV2
P.GLM
1100LM exp
2aM GLM.
27
aM.GLMCGLM
(2') 221+1
01, Dv,GLMCGLLN
2,GLM =
30
22+1p-2)12 2)/2
k(2')
22
3,GLM
G.GLM
with VP
P.G CLCLL C2 2 " max [1,E( where
(c)
123 + 2pp-2(p 1)p &2 8L4 +
(2)(() (4)
GEA
412
(C((2
GLLM
Gp.OLM
2--2(p 1)p0 - (200-1 1,2
(((n)
(2n) GLu r²
+ t -
(220-2
2p
+ 1/2
p-
32

---

Published in Transactions on Machine Learning Research (06/2025)
Remark that for p >>3 2, Un, O(n - min((.
Verifying Assumption (H3). We prove here that (H3) holds for general linear models. We now denote
H. = ( 62) XX"] + old.
Proposition 7.7. Suppose Assumptions (GLM1) and (GLM2) hold, then for all n 2 0,
E || - H- -
40
L
|XX|1
+
L Σ
U,
- -|10 H (0.) 112
16d Ve,n
n²
1=0
with Us GLM defined in Proposition
7.0
We can now finish the proof of Theorem 5.1
In this aim, let us first remark that for all h, h',
E Vl (v, xTh) X +oh Vn (x)x
-h''l]]] 2 (L [Ix]p] + +o²) 110 16'1
Then, with the help of Theorem 3.3 one has
E 10 00113] se 1am (<(3)
1,GLM + K (3) max (k + de
1'GLLM oSk5R
+ n
20t7 (H. "
2,G
GL. M,./2 + d1n/2),GLM.
n
with E. = E (vrl (y, x + (0oo (V (v.)) ) X + o0.)" )"1 and since c.r Cai
CAGLM =2 4c,
(3)
1,GLM =
GLM 24
E [11100- - 0/12²] +
2Ir (H HoH + 800 (o-+ + C.,o)) +
2L3
(60)
Cy
(())
K'GGLM
4c,
1
(2)
GLM
27-11
dn,GLM SCGLM +
13 0 2222((21
a²
2C
GLM
GLM
(61)
K-
2,GLM
(3)
-23+2
C
(o C3.
22.GIM 23+ L
(62)
The proof follows exactly the same pattern as the proof of Thcorem 4.2 using As- sumption (A6) logether with Lemma 7.4 to compute the constant Cs such that (H2) is satisfied. 0
Proof of Theorem 5.2
A Proofs of technical proposition
A.1 Proof of Proposition 3.1
Let recall that
Vn+1 Vn -nn1 (ghtz)² An L' (G + (0n+1 - 0m)) dt
Remark that for 2 2 and x, h E IR such that 2 0 and + h 2 0, we have by Taylor's expansion
(x + h)a S xa + ax h + 2 20 a(a 1)(2-~2111 +
(63)
This yields for a = x Vn and Un4i and after conditioning on F,
E
yp'
ve' + p V - E [Un+ [Fn]
+ 2 2 (p' - 1) E |Un+al
2 || VT' -2 + E [ (F()))))))
(64)
33

---

Published in Transactions on Machine Learning Research (06/2025)
Since G is convex and VG is Lipschitz,
Un+ 1/2' |5 < 7n+1 (sh+1)² An / VG (0n) VP'-1
E Yntt ( T An ( (VG(),) VG +1 +6n+1 Bn))) dt Fr
V
1 ~hh+ (0x) VG V/' + LVG 2
i+
E | 12 |Fn] || Vx
2
S S- (O.
2
92
LvG
Ci GiV2'-
2C2 vp
n+1
2
By strong convexity, we have
(O,)" (Z, Amin (An) V (0,)ll Vz'-1
2 2A 1
2AnuV 21 AA)) An
where An = >annn + 1)A with 0 S A < m
28, 1 - -7)- Applying Hölder incquality yields then
(0,) An (G)) 22An
VP
22nuVz (P(Amin(A)) < Anl) Pdd 22nnE(V3]p'1 /p (TP) (Amin (An) < Xnl) xn +
22nn
VD
with V/ 2 su B[V given by Lemma 7.1 Then, Assumption (Hla) gives P Pmmnn (An) < An) S un+1(n+
1) 11-6-91 Un so that finally
E Un+i1H -
p-rl < - 2 An | + 2An mn on
+ 1 2
LvG
Ci Vg' -1]
20 E [/p"
(65)
Furthermore, since VG is Tvc-Lipschitz, has
11 VG(0,, + +00+11 - onn) dt
( (110, 011 + t110n_1 - 0, dt
S LVG
jo
I LvG |10, - 011 + 2 7n+ ||A |
(66)
Hence, using (H1b) and the strong convexity of G yields
E Un- 12' [Fn]
< o |Alll
the E.
[|lahtill* (20' 110, - 0110 2- 2-22//n
m+ Al |10h+111")) [Fn]
Lta v' <
22 (Qpp 2 12 vgl12 12/11
Chpp /2) 22' 2P' Vp
2 m+ 1++1
w 12
100 (c(p)
cdpl) 2 Vp
wo 1)
+
Specializing the latter inequality with p' yields then (recalling inequalities equation 12
E
Un+il Fr
2
12 2
22 (a(
2V,
2V22
1 (a + C2 1V2
) V2'-2
1
82
+
C2
+ +22
2
p2
112
34

---

Published in Transactions on Machine Learning Research (06/2025)
that
E
|Unt2l
1p
[Fa]
+E E
[Un+2] 2 Fr V
25 12 1
G c(v112)
2 LGa
32p +
4c
1 30
a+1 V +
2 32
VF' -1
2
11t1
PPl12
1++1
1n+1 n+1 n2
L
228' -
C2 (2)
2 -1 - (n')
1n+181
1
18
V2'-2 2 + Vp
1 n+1
32p' 1n+1 n+1
2
10
2
C2L2
2C x²
82 in+
4²
Using the latter inequality with equation
65
in equation
64
yields then
E Vat n+1
<B
Vi
2p' 17++1A,
+ +2p' An Mn p on d
+B [P ( Vn)]
with p(x,,) Aboe Ap1220 / p2 12 + Ap- -1 Ap 2 yp 2 + Ap where
250' 12- 3 pppp' - 1
Ao= 20' 2p'-3pp 'p'p'' 1)1k ((p') App/2
Ap- p' LVG 220' -2 pplp 1)
Ap- 20' 3p''33''p 'p''p' 11ppp111-0 L))
and
DLL0002 Av
+p'(p' -1)
223'' L C2
c
22 2-2
c
22p' 23''-31m
120
v' (l0
22/
22/2// 20/-2
Eg
11
W
22n' C21
2 - 2,03
12
12
Applying now Young's inequality, which implies a'bo' for any 1>0 0 and i E (1,2,p'/2)
in
for 0 0<0<i<pp and a, b 2 0, yields
p.
A. x
iA x0'
(p/ - in)tdn
Ap-sat ypr
(t)
(1)
p'
so that using the latter inequality with t= for i {1,2, 212), and using that
2p' 82p' In
(2 F) (mat1dn)ey
2 p' 2p' -
Cg Xo
(n + 1) 1
(20-132 7+2p 7+2p'0+
5 ((mmtdn)))
2 v/ 23' X/
- //
(n 1)-101-20--)
gives
E 11 vn)] I
I'M An 7n+1
(n 1a+1)--/( (1+1)-((1-20-N) (in + Ag ((n+18442))) E V.
with
2p' -1 2p'
Ag
3c,
2(p' 1))2" 20'
N0 Ap
Ap
2c
2p'
Ab
12/2
+
ci
2p' C
xp
I A
Ag
4p
p
p y
3(pp 3(p"=2] -2]
3
35

---

Published in Transactions on Machine Learning Research (06/2025)
Putting together the previous inequalities and taking the expectation yield then
C
E
VP n+
1
plunn +
(n + 1
mtt1dn
E V
Ao
Lp'D
+ 2p' WVp Un
(n + 1) 1 1)-1(11-0--1)
1n+1
2
Then, recalling that on Un+1(n 1) 1)-8-10 - as and using Proposition yields
VP
exxp
(-coP/uu
n² 1- (-(22)) - <(m)) [ + K(
max 1gksa+1
k--28- A- p- 2 Us
2-d
2
+ Kb (10)) n 21(7-29--) N1 + Ks
eln/2| (n + 1) - --- (6+42)
with
4C 11 ue' Ao
n(1+23-21))
<(n)
1+
(67)
12y - 23 118-11
and
p'ul.) Chus
K(L 4p'nVz'
K(t)
E Vol
(68)
Thu
where
Apr
2--211 7+ズ
ク-28-ル
CM = max
Cy
(69)
Ao
8
and
k(') 2 (1- (7-28-11 -) L, K2 (<1')
22+² -- yF'
(70)
where V,, is given in Lemma
A.2 Proof of Proposition 3.2
Remark that with the help of a Taylor's expansion of G, one has
Vn41 Vn (0n+1 0n)²² J' (G,
dl
Vn - 7 (Dutz)² An L' VG + +1 - 0n.) dt.
Then, using equation 66 one has
22 n+1 < V-2 - 2 Vn (dh+z)) An / VG (0,, + +0n+1 - bn) dt
+ 12a A 11 7
2 21 - 0112 + =
2 in+1 A 1| 1 !l
==()))
36

---

Published in Transactions on Machine Learning Research (06/2025)
We now bound (+) and (**). First, thanks to Assumption (H1) and since ||0, 001 - 3 Vn, has
4L C1
E [ S
1nt1 ||An|1?V,
Vn +
||
V?
122
1
1 Cinti ||
2
C2
nn+1 |l ||.ll V?
4
2
1²
09
0
|| + judo0
V22 +
||An]|
2o
m+t1
2
1n+1
2
+ 112
(4C2 + (2+ 2
72
Then, taking the expectation with Assumption (H2b),
E [++)]] I
3
C$
+
7
E
+ [
2
2
2 G
+
(4C2 + C2c,C))
1 [V.]]
Moreover, since VG is Lig-Lisschit, one can check that
116' VG (0, + - 0,)) - VG (0,,) dt
ILvo J. tdt || [
LvG
|| 1ottall.
Mnt1
2
Then, one has
E [(+))[+)) 2 2 (O,)) VG. Vn - LVG 1 [1lsnt1 (otuta/ 112 FFn Vn
(7++1VG((0.) An VG (0,) LOo ||A CiV, 2Lvo
||Aml1 V2
n++1
VG (., Vn CLLEG
211o0 Int1 ||A
ud00++1 V2
2Lva
Tn+1 82 V2
2
/4
Furtermore, with the help of incquality equation 15 it comes
Nn+1 VG (9.)" (9.) V. 220p 220 AA,
Then, with the help of Holder's inequality, coupled with (H1a) for t L, one has
E [[{+)] 2 2 Aop 1 V/2 4A0/% (in-2)/m22 GL 3
2LvaC2 22,
2pd0 n++1 Cg
22
Bh.1 [
1
with VP defined in Lemma 7.1 and i == un is the upper bound from (Hla) on P Pmmmio (An) S Ao]- Let
am max (2Ixaa
2To (4C2 C22(3)
(3d0m)
21-28
+
Cy
(71)
P
12
2
one has
E [22 < (1 3N0177411 + 2xm28-7
7n+1)
E EVV.)
40017 2/p-2)//p
Cia,
C7
+ C3LL0
1++1
(72)
1do
2
2μ1i0
=101
37

---

Published in Transactions on Machine Learning Research (06/2025)
Applying Proposition 7.1
it comes (with analogous calculus to the ones in the proof of Theorem 3.1
E [ S exp
3 Sy SyJomm
1-7
exp
2a 2 2-3
2y 2 2
B [Vo]
20
SAnpeyy V2 V
uk" " 1-- 1m
R=3
2 aa
+ 27
4 2/220022/
aM
aM
max IskSn+1
3dU
n
3 p [n/2]
where Vig is given by Lemma
7.1 and [L/22] I 1n/22 (n + 1)-6. Sctting
k(2)) exp
2aaM
27 23 -
27 - 2,3
E Vo? +
2a 22
(73)
aM
(2) exp
2a
27 23 33-1 1)
27 - 2,3
(74)
aM
with am given in equation 71 given in equation
72 and Vi given in Lemma
and
22
22 2)8/p
K(0)
V2 p
(75)
320/1
we finally get
E [[ Sexp
(
( Cy Aopmn
(2)) k(2))
Uk k 22 2
p-2
max 1skgnt1
+ { n- 22 + (2')
1 (ip-2)/1
-5p00155ppp000 5(p- 2)/v Mn.
n/2]
Then, for any 0 0 $ min {2y, 6(p-2) } P
g. only depending on Un and y, we have
Woo (7)) sup Mnn to0. n21
(76)
Jo. min {2r, 5(0-2) }] + R can be computed numerically, but in any case note that
The function Woo
Woo (7' I k222 sup:21 Ey exp (-2 [))t k(2") + k=(2), so that function analysis yields, for 7 e
00 min 22y, 5(p-2)
Wo0 woo k(l2)
2 Aopee( - 7)
K=L2) (2))
(77)
We will see in most applications that under suitable assumptions, Y can be equal to 2y (namely when
8 2p 2-))).
B Proofs of technical lemmas
B.1 Proof of Lemma 7.
Observe that since the proofs are analogous, we only make the proof for p 2, and for the case where p 2, if there some differences in the proof, it will be indicated with the help of remarks.
With the help of a Taylor expansion of the functional G, one has
Va41 Vn -n+1 ( An L' VG + +t(0n+1 - 0n)) dt.
38

---

Published in Transactions on Machine Learning Research (06/2025)
Then, applying the inequality
(a + h)p S a" + pa--aa h+ p(p - 1)h²
1 (a= + 11)p-
2
sa + pa" h + p(p 1)2 22 (2 + (a'02+11|0-3)
for a, +220 a = Vn and h 7+ (1x+1) _ An An VG (0n, + t (0n+1 0n)) dt, one has
V n+1 S V - pnn+11 (oh+1)² An I VG (0n + (0n+1 - 0x)) diV.
+ 2p-32(p 1) 7n+1 (ch+11) An / VG (0n + +1(0++ - 0n)) de
VP-2
+ 2 "pp 1) MMI (1ht1)² An ( VG (On + (0n+1 0n)) dl
Remark B.1. Observe that in the case where p = 2, one has
(a + h)² a2 2ah + 122 = n + 2h2 + p(p 1)20-3),211p-2
the last term on the right hand-side of previous inequality can be considered equal to Recalling that since VG is Lvc-Lipschizz, one has
11'0 VG (0, (0n+1 - -On) di s Loo (110, Oll 7o+1 || |1 II),
which implies
n+1 S VIP pma+1 (1h+1)² An / VG (On + (0n+1 0n,) dtv 1 =: (+)
+ 2" 2(p 2 1n+1
vut1 ||
|| (11e, - -012 + +utz || 11 1|9h42 11²) v=-2] 2] }= (**) 11" (110, ||
+ 2" 2p(pppp-pp o |
||4,,11'
011" + + || 11 || [1')] (***)
Furthermore, one has
(*) = - ( An [' VG (0,, +1 0n)) diV
-hh+1 (gu+1)² T' An (G Vp-1
Plat1 (Dn+1) T An L' (VG (0,, + +0n+1 -0,)) VC dv
Since An is positive and since VG is Lvc-lipschizz, taking the conditional expectation, it comes, since for all a, b 2 0, ab < tap + p-1np/(e-1) and with the help of Assumption (Hla),
[(()FF))) < -1++ (O,) A, (G VT-1
2 n A| E ||lhh41 1|2 [F V/-1
P_2
S - (A,) V (0,) 2 v.-1+ P
+
P33
2
(C, + C2 110, - -112) V22
n
2
1n+1
PC2
PC1
S -pphh+1Amin (An) VpP +
32
2
Pu
nr VP-1
pC2
Ci(p - 1)
C
Butt in+1 1++17++11
22
V +
32 1ut1
p
2
39

---

Published in Transactions on Machine Learning Research (06/2025)
with N/2 Xnn-X'_ convexity, |0,, - -012 - 2 Vn ts (0n)ll on the third inequality. For the same reasons, one has
-x" We also used Assumptions (A1) the first incquality and the fact that, by pestrong
E [*( s $2 2p-2pp1 - 1)L2G
2P0 (p - (Iiti
C + V22
11² v/
+
18+18
20
Vn
+ 4C2 v2 vx) V
112
1
20 + (p))) + 4p0²
V
11²
(20 +
(2(p-1)C) [2pp - 1)
+ 4pC2
+ + - 1
Vp
1
112
In same way, thanks Assumptions (A1") and (H1), one has
2
[ * +)] < 20-32(p 1 1 c(p)
20
+
Vp
1ep
V Taking the expectation on E [()) + (**) [. + [[( Fn), applying the latter inequalities, comes
+ 2 plp 2
Cdlp) I
+
2
(
2
E [ max E [7 13 p 1, 1y51/2 + a 1
with
==
C2
Ci +
+
2p 1)gLio
( C
4C² 112
+
201
4C2
1
2
1
n2
+
22-2 20-2
((p) ( 2%C(
+ c.
2
p-2
c(p)
+
2p
1
+ v
c
(pp)
)) (78)
112
2
n2
2
Remark B.2. Observe that in the case where p = 2, one has
2C2
AT2 C1
&T C2
81. C2 2
02 =
+
+ C22
(79)
p p
22
112
I > 1/2, by summation,
28-28 max [1,] Vp.
E [V?] S e
If S 1/2, let no be the smallest integer such that 22 1+ > Pn
Recording that X,
(n(n 1)-x we have no
(
(creap 5-28-x Puu
Then,
E [ A exp
Σ
puXo 7n+1 + ag + max (1 [V,')
n==
1---x¹
1-2y428
Sexp
1
1
crcsap Paud
7-20-
+ CE
14
+
Pu1
7-
Vp.
X
1
27 + 2,8
B.2 Proof of Lemma 7.2
Recall
that
(An)ay
max min {cene, (An) ) Non 1 1,11/23 with An Ai
E22
Since Amin (An) 2 Amin (An) on the event {Amnn (An) < cg), we
D+1 (aut n-
40

---

Published in Transactions on Machine Learning Research (06/2025)
have for 0 < t
IP| Amin (An) < tco] SP Amin (An) < [cs]
12
<P
max Isksd n
ak +
Vang (x:+))1))))
+1
Then, Markov inequality for > 2 and Jensen inequality yields
1
R-1
1
P
max Isked
Ok
+
Vng (Xi+1, 02)x)²
n n+1
cst
n-1
S 8 2
ax Σ
Vvg (Xi+1, 0,)
max
IsKidd + 1
S <c 200
V (Xe+1. 0,01
n1 n+1
S 2 20
ak
+
Ving (X(+1. 0:)1 01)1
n+l
Then, using Assumption (A1) and then (A2) we get
n-1
P
max Iskdd
+
(1,
n2
+
Cst
1=0
S
Cg
20
1
Σ ak
+ nCT
+ C
E [10: 01130)
n+1 1
i=0
1
2D 2 Cr n-
S
3
2p
n+1 1
Σ
ak
+ nC"
+
1p
[V:]]
By the bound E [V < VP from Lemma 7.1
we finally get
IP
max I<kSd
1
0g +
Vag (X, 1x,-1,
1 cst
I t2p
n+ 1
1=0
with
Un c
2p
((:
Σ
0k
p
+ C +
V
(80)
n
up
B.3 Proof of Lemma 7.3
Set Eg E Vng (x
0) and 0gg(h) EE [V Then, by Jensen's inequality for p' 2,
p'
(An)as
-2p'
< 20' -1
8gg Vag 0,3 -0 (0:)
+ 2
Kg
n1
1=0
41

---

Published in Transactions on Machine Learning Research (06/2025)
Hence, for any
IP (An) kal < =P
1 (An)
-2p'
22
IP
hh (X++1, 0:)
0ig (0:)
x226
+
2
+P
ag
1
n
(g((0))
10"
2020
(81)
n1 + 1
n
2
Set Mo 0 and for n 2
M Σ Vng(X,+1, -
Then, (Ma)x20 is martingale, and thus by Burkholder's inequality, see Hall & Heyde 2.10) there exists an explicit constant Cp such that
2014
Theorem
1212
E |M S B.
Σ (M, M1-1)
SC Scyne 12-1
E M.M. M
SCyrl /2-1
Vng (X,+1, 0:) -28-0-0-0 (0:) []]
E
where we used Jensen's inequality on the second inequality. By Assumption (A1); the strong convexity of G and Lemma 7.1
E (vno (X,+1,0))
0.)2 12g (0.)) )7 < 2 EE (Vig (Xe1,, 0:)a
0gg
<2" E
V hg (X,+1, 0,) ||a0
<2D (1')
2D che'r |R
|10 01120'
V
<20'c/')
$2" (p')
2 22 c
(p')
Hence,
CkP') 29' c(z')
yp 1077
R-1
E
Vig (X411, 0:) -hh (0,)
= E
M
$ 2p
(82)
n + 1
n + 1
n
(n + 1)0'12
which yields for x > 0
2d c(p') 22' 1/2// c(a') Vp' T2P
IP
Vng (X++1, 0g (0.)
<
20
(83)
22
(n + 1)
Next, by Jensen incquality,
a2
Σ Rog (0.))
laul"
Σ
n
n
n + 1
1=0
Using Assumption (A1) and then strong convexity yiclds
2d c(r) Vi
[gg (0.))*
sc(i")
wo
42

---

Published in Transactions on Machine Learning Research (06/2025)
that
ak
+
1
(ogg (0:))
1
+
lagl" 12 2 c/
+
m+1 ++
Vp
n +
+
1
n n+1
w
2=
22d 2p'
> chri
Hence, for
x²p
2 Cxlo')
x 2²p'
PP
1
o (O:)
ITP
1
|aa|
+
V.pp
n2 +
20'
+
1
1000
2dd
1=0
1=0
2 clas
E
ag
1
+
Zi=0
n-1
V.8
71.
+
C(P))
2
7216/ 2212
By equation
33
and
the fact
that
n+1 Σi= (i
1)
a+1
log(n+1 1)
and denoting I
1
1ol 2010 11 (2-10
(n+1)
11 2322
201 200
2-9
2019
2(1 311-3)77
2812 y1 20
it comes
2 Olp's app D
2 C(P')
Ei VD
E
lax
+
VP
+ 1
n ++1 1
==
2d' ((p')
2r' C(pp)) 10 (n 1)
K₂T
log n2 +
1 1 |ax] P + Ki Σ
exp (oa_Adii-(Att)pp - -c((i)
1100
211-9116-2202 Al
(n + 1)
1=0
log(12 (z + 1)
(3
7//63 2012
11)
2-7
with for n 2
2 C(pp) M(3)=
+oc
K2i + 1 + 1ax + K₁
Σ
exp
--c.udont--att (ee-eee())) e((1))
w
n=0
Choosing
2 (C(p') + +1]
+
Ao
(84)
yiclds then
P
Ok
(g (0))
Am -2p
M(8) log(n + 1) 201 21-1210-26111
n1 +
n
2
(n +
1=0
Putting the latter incquality with equation
81 and equation
83 gives then
P [dmiu
(An) < Ao] S
(An) kk
Aol
d2p ((t2)) + 20' pir''
VV p
dM log (n + +1
20 11111111-20)) Al
(C(P") + 11m2//2 /2
(n 1)
vo log(n + 1)
7)1(0-29)2 2918 Al
(n 1)
43

---

Published in Transactions on Machine Learning Research (06/2025)
with
d2 (cl)) + +2 ca(c
v0 = dM( +
(85)
c +1
Since P [mAmi (An) < Aul I Amin (An) < Ao) the result is deduced.
B.4 Proof of Lemma 7.4
Set Eg = E Va 0) and (gg(h) = EE (x(X))))] Then
a-1
E
An kk
2
Ek
<20'-1E EE
Vng (X1+1,
02g (0:)
12 +
1=0
0K Fxc
R-1
2 -LE
(0)g(0.) -Ea)
11
k=0
By equation 82
c(Pi) 2 (p')) Vp¹
E
hng (Xi+1, 0z)
0gg (0:)
(0:)
S 2
(n + 1)0'12 1877
n
Next, by Jensen inequality,
p' (ogg (0:) Ex)
Es
1
Σ E [0L0(0.) - Exl EaI"1)
E
S
n+1
(ax - Exy'
n
Using Cauchy-Schwand incquality, Assumption (A1') and then Assumption (A1) yiclds
|0gg (0.) Exl²] | (0g (0,, (0g 10, ["]
E V ng (0,, X)₁ Vng (0. (vng (0,, X) + Vng (n, x)x 10
(vng n9 (0,, x)2 Vng x) )² 10. 12/2
(Vig (0,, + (0, 10,100111 10.00/
E
<20 12- 2Z//2
|10: 110--0'' 0
+ C 1/ 110, 0| }]
28 1/ 0P/12
23p' 12 C25¹ /2 LL'/22
[
E V."
E
12/2 12
1r
2t Lg of /2
23r/ /2 Cy 1
L
V
Ca.
w
w
where o; is given in equation
33
Putting all the latter bounds together yields, using that Es < Ci,
E
0g
F
(gg (0.) Ex)
n1
1
23d 12 105
LL
n
+
1
2F'
(a
C
Σ
12
11
Ci
44

---

Published in Transactions on Machine Learning Research (06/2025)
Hence, noting that V/2 by Assumption (A1') and Lemma 7.1 A -
- Ex
2 c(P) + 2 Cho' V2 ne
2F -1
n-1
2 L C2'01122
2 12-1 C2 /2
2 (ak +
09
+
Σ
Va
nu + 1
1¹'12
UP
==0
1m6n
with, by equation 33 Cn = 0 ( 201y x1]
[
Since by (A6) we have Ex 2 a, we deduce by
Markov's inequality that
20'
2" Gx
P An)) S va/2
= (An) (An) ke I 0/22
S
am E
An))
Ek
S
a
Hence, we have
E
(An)
=
1 An
2 (Am) lik
+ (An)an nn <V= (An)ia
22
<I
b2 2V c2
+E
(A(A) <V2 (An) 1kk
An
2 cgn Cn
S 2
(An) -1 - va/2
4
a²
ao
a²
Since e. = 0 log(m)n" -
aa - 29 A1
for B
(1-1)7(1-201)
A I we have
(1-7)1(1261)
280p
A
-43 >
0
4(2 4(2-7)
2-7
and thus
w(3)
sup n +00, n²1
and finally
E
Am
<
E
(An
S SC
k=1
with
2 c3w(33)
C3 d
(86)
a2d
α²
B.5 Proof of Lemma 7.5
First, we have by (A6')
E ((An)a)))
E
Vag Xx41,
Vng (Xe+1, 0z) a.
Then, as in the proof of Lemma
7.4
4v? C
C
E
Vag 0.)²
E
Vng (Xi+1, 0:)2
<
n
1=0
1=0
Hence, by Markov inequality,
2
a²
P (((AA))))) -2 S sa/2 SP
Vng (X 0,)
(X 0.)3
>
n1
4
1
C
+ C2 4V2 n²²
2
45

---

Published in Transactions on Machine Learning Research (06/2025)
We deduce in Lemma 74 that
4
((c + C2
E [AA))a]] scgn (AA)) kk S va/2
4 a
1/2
4
+
S
n
48 a²
a²
When 3 1/4,, we finally gel
d
E |1
E [(An) ) S C3
k=1
with
4d 1 04 + C22 +ト
C3
(87)
a²
C
Proof of technical Lemma and Propositions for linear regression
C.1 Proof of Lemma 7.6
Remark that
a+ + m
m ||o||| + Σ
||xx,
s a-
m || + Σ 11x:11 IIxIIP)
x=1
2=1
Hence, for A > 0,
m ||So|| + Σ |xxi|2 > 2x-]
P [Amiin (5m²) < A| =
|لt10 1/2
< P
a+
n
Taking Ao = E 111
yields then
P Amiin
(5,11)
Ao
S P
||5 + Σ (I|x,112 - E [[XX1P)
> E [[X]|p]]
Taking the p-power, applying Markov inequality and then Rosenthal inequality yields that
E [[x11]] > [[XIT]]
P
m ||S|/| +
Σ (Ixx11 - E (11x11111)
<
P
||Soo|| +
(E [[XI!))
n
Σ (11x:112 E ((1I1P1) 07 n
(IE [I| 112)
E
np
m
||So|| +
2P-1
(Ci())n' [1 C2(p) 2/2 (L (12 p/2 + m ||Sol1 n n-
<
(EE (19))
with Z = X E [1]
If X is a subgaussian with subgaussian norm || 1l a similar reasoning yields
PP] Ammin (3 < Ao]
<P
m
||Sa||
+
|x,1 Ao
<P
(11x,1122 - x1111 > n² //4 X - m ||Sall
(_ c ((n(Aa''/a -(1xx())) m 1|5611)
<2exp
n/ xl|xX|v22
46

---

Published in Transactions on Machine Learning Research (06/2025)
with 0 absolute constant, where used the generalized Hocffding incquality for sub-Gaussian random
variables and the fact that centering alters the sub-Gaussian norm by a universal constant, see (Vershyning Lemma 2.6.8). Taking λo = (2a+ E [[] and assumiin
2018 Theorem 2.6.2) and (Vershynin 2018
that m S Soll
x yields then
P Amin (3x²) < 2o} - 2xxp
(- ||
for some numeric с 0.
C.2 Proof of Lemma 7.7
By definition of Sn Sn = Sn the event Tn {Amin
(5n)
can= }. Hence, for the same Ap in Lemma
7.6
P [Amin (5 < Ao!
=P Tn n Amin
(Tx² < Ao
P
$ P Amin
[--1
20
+P [TT]
(88)
By Lemma
P Amin (
< 20
S
on.
(89)
with Un given in Lemma 7.6 Then, for n 2 no, where ng is defined in equation 36 we have n 2
-1/3
atm)
and thus na-
u+m 02 canz. In particular, the event {dmin Ei 02), we
cac2a
have
a m.So Σ x,X?' ))
Amin (nn Mmn
an
n2 + m
2 na
Amiu
X,X7
no
C2
n + m
n2 + m
Cyn
Hence, for n 2 no. {mmin t Σ X,X7) 2 02) C Tn and thus by Proposition
7.2 and the fact that 2 eıd,
P TH
P Amin Σ X
< S <cxp(-can)
(90)
Using equation 89 and equation 90 in equation
yields then
Amin
Ao
S 8n + 2 exp((ccnn)
for 2 ng. The statement of the lemma is then rewriting of the latter inequality.
C.3
Proof of Lemma 7.8
Since we have
| = min 1115 11, min
mmnn
Bn+t1 j
Amin {5x)
for C1, 02 03 given in Proposition
7.2 n 2 cid m and x. > 0,
1
+ ( n
E
[||
<33%
Amiin
X,X?7
S C2
12 mm
i=1
22,3 exp (cn)) + (a- 02/ 2) -M
Since 3, = atm (mSo + "" レ
X, X and Σ X,X > 0, an > a_, we have 3, > x+m So and thus
ma
|| < ||Š--11 < [m+m] || 1| for 2 1. Hence, for < c m, || || < (ci+2) || and we finally get the result.
47

---

Published in Transactions on Machine Learning Research (06/2025)
C.4 Proof of Proposition 7.3
Recall that Bn can..
Since,for > 0, the map g 1 + (cal") exp(-cal) is bounded from above by
8x
we get
8x
sup E [|1 & 2cB n2oid
+ (a_c2/2))
eC3
Taking into account the case C1d V m yiclds then
23 CC3
2/
cdd + || 121
Cid
sup E [11
S max 203
(a_c2/2))
m21
a
and
[5
40
c cdd+2 1150 ||| }
sup n21
||| s max
20d
+ (a_c2/2)
EC3
a
C.5
Proof of Lemma 7.9
First notice that
11 = 3 (H 3,) < 3 I 3-|1|111111
Under hypothesis of Proposition
7.2
P Amin (5n) a 02/22/22 02/2] 2exp (-c3n)
for 2 eid' V m. Since || < 1 ||, Amin (Sn) 2 Amiu (Sn) and thus also have
P Dminn (5x) S c2/ < exp (-c3m)
for n 2 eid m. Hence, for 2 no:
E
5 n
=E
Amiia
02/2
3 H-1
E
1
Amiu (3n) 02/2
3 1 - -H -H-1
E (Amin
1 Aumin (3,) 02/2 | H11²]
E
[115, H1]²]
a c2/2)
where we used on the last equality that for n 2 no: Sn = Sn on the event {Amin (Sn > a C2_02/2 (222222), as
the proof of Lemma 7.7 The first summand can be bounded using Hölder inequality with 1 1 and
q' = p/2 as
E
(3.)5a
c2/2 1|s,
HT|2]
1/5 1/E E ||| H SP [Amin (Sm) c2/2
2q 1/4
<2exp( 1acp(-call-00 2) 2) / ||5, H [1r]
2/v
Using the upper bound on H and the convexity inequality (a + 6)" < 20 + b²) yields the rough bound
E |3 H1]r)
2/r
2/v E [| [[H1)))]
<2 2/p E 3,,1l" XPrax
2/p
max Pimaxos E |||Sm|
Since X admits moments of order 2p, we get
17 1/1 )
E 3 [|]]
1/P < a m + m
S
+
a + m
1
Σ
|x
$ a + +a+ (E [[ax 1/p
n i=l
48

---

Published in Transactions on Machine Learning Research (06/2025)
We hence get
E I [''Amo (B.) #11²] & Sexp - 2)n/p) max ( 20x+ (1SS) + (E [[I ( 2/2) (1)1)) }
16a4 exp (-cs(p 2)m/p) (116011 + (E [||X] (1)))
For the second summand, using the relation between Frobenius norm and operator norm yields
E [|, H 11]] I an 112 B (n m))
ImSo +
X 1
+ 2E
1 m
mSo + Σ
XxxX - H
k=1
k=1
= R1 + R2.
By hypothesis, Ian 1 Co so that by Jensen incquality the first term is bounded by
2Ca (1S0 +111x)11)
R1 S n
and the second term is bounded by
(n (n+m) m]² lan - 11 +
2
2
E
Σ (XxX) -B(X=]
(n mm²
2
|| - H 11
2
E
XX
E
Xx
(n + m]²
n m 2
|mSo - H1
E
[
(n m)2
n m
Putting all the above bounds together yields the bound of the statement.
C.6 Proof of Lemma 7.10
Remark first that as in the proof of Lemma 7.1 one has
Va11 I Vn 7nt1 (gn+1)² An /'' VG (0n + - 0n)) dt.
Then,
1// VG (0,, +1(0++1 0n)) dt s LoG (110, - A|| +n+1 ||A |1 (164111)) II),
which implics that
Vn+1 S Vn + Th 1n+1llAnl| (lls'+1ll 110,, - 01 + 7141/An 115
Using the fact that sht1 = (e + X (0 0m)) X yields then
Va+1 SVn + 7ot || |n LVG (11X++ 1 | - 01 + lell 01l 2 || l (1) 1 - +e))
-012+
<Vn 1+ 2(n + 1) LvG
|5 (2 + || + 4(n 1)2 2
in+1 1 |S 1 "11lx11
/ + 2/e LoG (7 1) (n + 1)31|5+211)
49

---

Published in Transactions on Machine Learning Research (06/2025)
where we used the strong convexity of G and bounded A, by (n + 1) ||- Hence, taking the square in the above inequality and taking the expectation conditioned on Fn gives, for 2 1,
2(n + 1) ti ||5 (2 E | 1| 18)1
B ++1 22 <20''E[V?]
1+
4(n + 1) LVG || [1IX 11 1/2 P
#
+ 2 E [||| LbG (in+1 (n + 1)115/11 || + n (n + 1)11)5+311)
<B|V?] exp ((-- 1) l0g + Ciin (n + 172-27) C 1)
with
Cism,1 2pc |ST (2+ R [1] [|] n 111] +
2pc LVG
||5p |
(91)
11
Cisn,2 2B [|c DgG (c>1157 + 11155
We deduce that
n² 22
) (1+ Ctin, (p+11 1)-1-
12(+1)-m
B < exp (p (p-1) log(())) + Cui,,1
3 3-27% 27
E [V
Proof of technical Lemma and Propositions for generalized linear model
D.1 Proof of Lemma 7.11
With the help of inequality equation it comes
1 | S n + S + Lvi
| ad Σ 1z
n
with Zi
e//d+1-
Then, a similar proof as the one of Lemma 7.7 yields that for Ao
(2LV
[|x|1]]
+ 20 +20
PP
Amin
(5m))
Xo]
< TP
So
L
|X 2
E [IxI²])
Σ
(1Zl)² (1z11-1) T +
i=1
i=1
Then, by Markov inequality for p 2 1, we then get
E
1 |
+ Σ L77
|x,,|1 - -X [[x]]]] + (12.12-1))
Amin
( < Ao
5
(L [|| + o)
2
(n 1Soll (C +C(l)) p/2 (E 11)
LvpiE
||x1|] +
with T Loi 2|
2 [|| + a (11]12- - 1).
D.2 Proof of Proposition 7.5
One directly has for all n 2 2d
|n/do σ
n
n
Amin
(Sn) 2
2
2 0,
(n + 1)
d(n 1)
2d
50

---

Published in Transactions on Machine Learning Research (06/2025)
and 3,, 2 2d So for S 2d 1, that
sup n21
|
- 2d max
1 [
||1551|
D.3 Proof of Proposition 7.7
Let us denote
H (0.) = E V XXX]
and
H
1
So +
(Y, x x
++1
1=0
One can decompose H 11 (0o) as
1
Ha H (0o)
Vil (Y++1, (0,, X,+1)) X +
So H (0.)
n+
X141 (Y,41, (x+ - (0.)
71
Σ (0. n+1
- H (0.))
n (S. (0.)).
Let give rate of convergence of cach term on the right-hand side of previous equality. Set M, EL (Vee Of Xi+1) X X - HO:)). Since E V (Y,+1, Of Xi+1) X H (0:), where (F) is the o-algebra generated by the sample, ie F, = ((X1, V))... (X,,)...XX,,X)))) Then, (Mn)n2 is a martingale and thus
E
|
E Ma
<
Σ 1=0
E (IVVE, X.+) X H(O)))
nn 1)2
(n
+ 1)2
It then remains to handle
Eee (H((:) H (0,)). With the help of Assumption (GLM1), one has *+1
n-1
-H (0+))
Σ
[1((0))) - (0.))
71
2 n-1
12 n-1
|10, - 00113 I
on Σ
U.GLM
with 4,GLM defined in Proposition 7.66 Then, since
do 2
- old = do
do
n
n
1
1
(d
+
n d
σ Ip
i=
and
doo
Σ
< n2
do2
n
71 [
Σ
1| <
d=o
n2
n12
R dl S
it comes
B, H₂
4
LE
[IX]]]]
+ 12
G.GLM +
1 - 11 (0o) 13)
+ n
16d
1=0
51

---

Published in Transactions on Machine Learning Research (06/2025)
Now, notice as in Lemma 7.9 that
H
3
(H.
3,)H,
$ 3 H. 3.ll ||
which yields, thanks to Proposition
7.5
E
5
H
2
||3
Holla]
r²
i. one has
S H
11]
403
+
1 +-1S n
H (0+)
16d 3.0
(92)
2
n²
E
How to verify (GLM3) for the logistic regression
Remark that 0g is the unique solution to |, (r, + o0,] 0, that
X + (00)) |] Var [ (Y,X 8.) Xx E Vnl (Y,
For the logistic regression, we have Y E (-1,1) and Vnl (Y, 0²) = -Yexp(-Yo and thus we need 1+exp(-Yo
to get a lower bound on the variance of -YXx exx( for all 1 s k S d. To guarantee Assumptions (GLM3), we impose minimal randomness on (X, given by the existence of Te M > 1 and for all 1 < &s < d an event A& E (x) with IP [A n (M-1 [&al s <M] n such that on Aş we have
1+exp(- -YagX)
Σ iA
Xi(Oo); < aa >e and P Σ X((O,), > by, >c KE
In particular, since +
a cxp(-Yu) 1+3 exp(-uu) is C¹ and monotonic for all a, 3 > 0 and E {-1,1}, for M small enough, there exist constants c ct explicitly depending on M, (0, ), a, such that on Bg = A (M-1 < [&l S M),
exp( -Y > ct Yr Xx >6
P
(xpe-xppoi YO
and
Y exp(- -Y00
P
<c cT 2E
1 exp YO5
We deduce that the event B₁ have
YX -xx
Y,X, 26 cc_ -
Ver
1 11expp-Y007)
Hence,
Y exxexp(-X0
-Y
ct - c
Var
1 1 11exp(-Y0?X
2 E Iaaar
1xepp(-Yoo
Y,Xx
m/e
and we can choose
ct c
0g = mp
2
52

---

Published in Transactions on Machine Learning Research (06/2025)
F Counter-example for the quadratic convergence of the stochastic Newton algorithm without regularization
We show here that even in the simplest case d 1, stochastic Newton algorithm may not converge quadratic mean. Suppose that we define here the naive Newton adaptive matrix An
n-1
Vio ( 8.) T
An
Id +
Σ 1=0
n+1
1
Recall that known (Boyer & Godichon- Codichon-Baggionj 2020 Oy at speed n>> for 7 E (1/
that 0n converges almost-surely to the minimizer
Counter-example with Vg almost everywhere defined
Set g((, y), (x0)² + y 0|0 and let (X,Y) Y) be random vector with independent coordinates such that X ~ (er(1 and P|Y 1] P[ -1] 1/2. Then, G(0) E [xa] 02 + E[Y] 62/2 and we have Lebesgue almost surcly Vng(( v), h) = 22 + y/h and h))
Let 2 1. Then, PP [ O,.... Xn = Y1 -
l..... Yn -1] 2-2n and on the event (X, 0,..., X 0, Y1 = -,..., Yn -,,, as long as 02 & N for all k 2 0 (which will be temporarily assumed),
h-1
A
1
1 + Σ
2x2+1
1 k
k
i=0
Hence, A₃ = and (0s) is defined recursively by
= - Ax 10=-- 1 V4 0x-1 1
If Th k for some 1, we then have ky = kl-a, and thus for 0g > 1
02 2 (1 + 1s -- 12)0
We deduce that 0, 2 IT (1 k2-0/2) 2 (n!) 1n! n In particular,
E [10 0 > 2 3m (n!) n n-000
when 6% & N for all & 2 0. Since for each A: 1, 02 & N for almost every Oo (1,2), the latter hypothesis
holds for Lebesgue almost every choice of fg 2),
Coumter-example with Vg continuous
Let f be such that f" 12+1- and set g((x, v), 0) +yf((). Let (X,Y) be random vector with independent coordinates satisfying X Ber(1/2) and Y u([-2, 2)). Then, G(0) E [X,] 0² [()] 8² /2 and Vng((z,v), 20 + (0). Then, Ao 1,
Ar¹ k ++1 (A + 2x + fd (00x))))
for 2 and
On 0a- An 1/ Vng(((X, (Xn, On), = 0 An-17)(2X20, Y.
Set 0p 33/2 and 7% k- for k 1, and consider (X,, Vilosion satisfying the following conditions:
= for all 5 i n, which yields P P[X; O..... X, 2 and for all k 2
0: ap- A Yk.l (0x-1)
53

---

Published in Transactions on Machine Learning Research (06/2025)
8k-1 being known, Y 7h 1f ((2+)1/3,2/3) - 0x-1) -1] Tl (remark that Tp will be shown to be non-empty).
Lemma F.1. The following facts hold for l 2 1.
0/ 2 1,
An 1,,
3. with l denoting the Lebesgue measure,
- -1 2 1/6.
((
Proof. We will prove those three facts by induction on k 2 1. For k 1, we have Ao 71 and f'(3/2) 1 that 01 = 3/2 Y1. Since
T 1 (Zz))//32/33 -20_))112--111133------331311111
(0))
-|-776,--1U1-22-111
((Ti) 2 1/3. On the other hand, for Y1 E Tı, 01 2/2
Let us show the induction. Set à 2 2 and suppose the result is true for / s k - 1. Then 0 E Z + [1/3, 2/3) for all 1 < k, which implies that A = k - 1. Hence,
0. 0 + b2t Tas (+
By induction, 0k-1 k, and since f(( 2 0 for 2
Tg = ((b + oZ + 201/3.2/300(222-1
with a = ((T)) 2 1/3 1/2 = 1/6. Finally, for Y2 E A we have Vv2 S -1 so that
E : s and b - We deduce by pigeonhole principle that
02 2 k + 2- 2 k + 1.
By the previous result,
P P X,, 0,Y1 E Ti....,, Y, E T 66_ 12-
Moreover, from what showed previously, on this event have for < S
02 = 02-1 A (0x-)) 2 0 12-2 0z- 1k2 1227/2 1/2
We deduce that 0, 0 - 1)1 1313 2 (n!)2-2/22) In particular,
1100, - 001191 2 (n1)2-1/24" oc.
Remark that the latter result. be easily adapted to get counter-example with g as smooth desired.
54

---

Published in Transactions on Machine Learning Research (06/2025)
References
Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimization for machine learning in linear time. Journal of Machine Learning Reseorch, 18(116):1 40, 2017.
Francis Bach. Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic re- gression. The Journal of Machine Learning Research, 15(1):595-60) 627, 2014.
Francis Bach and Eric Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate O (1/n). In Advances in neural information processing systems, pp. 773-781, 2013.
Bernard Bercu, Antoine Godichon, and Bruno Portier. An efficient stochastic newton algorithm for paramcter estimation in logistic regressions. SIAM Journal on Control and Optimization, 58(1):3488338 367, 2020.
Bernard Bercu, Jérémie Bigot, Sébastien Gadat, and Emilia Siviero. A stochastic gauss-newton algorithm for regularized semi-discrete optimal transport. arXic preprint orXin:2107.05291 2021.
Stephen Boyd and Lieven Vandenberghe. Conver optimization. Cambridge university press, 2004.
Claire Boyer and Antoine Godichon- Baaichon-Baggioni. On the asymptotic rate of convergence of stochastic newton algorithms and their weighted averaged versions. arXiv preprint urXiv:2011.09706 2020.
Richard H Byrd, Samantha L Hansen, Jorge Nocedal, and Yoram Singer. A stochastic quasi-newton method for large-scale optimization. STAM Journal on Oplimization, 26(2):1008-1031, 2016.
Hervé Cardot, Peggy Cénac, and Pierre- André Zitt. Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradiont algorithm. Bernoulli, 19(1):18-43 13,18843,-11 2013.
Hervé Cardot, Poggy Cénac, and Antoine Rodichon-Baggjae Online cstimation of the geometric modian in Hilbert spaces: non asymptotic confidence balls. Technical report, arXiv:1501.06930, 2015.
Peggy Cénac, Antoine Godichon-Bagee Baggioni, and Bruno Portier. An efficient averaged stochastic Gauss-Newtor algorithm for estimating parameters of non linear regressions models. arXiv preprint orXiv:2006. 12920, 2020.
Joseph De Vilmarest and Olivier Wintenberger. Stochastic online optimization using kalman recursion. J. Mach. Learn. Res., 22:223 1, 2021.
Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of adam and adagrad. arXiv preprint Nrx::20003.000 02395, 2020.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Sébastien Gadat and Toana Gavra. Asymptotic study of stochastic adaptive algorithm in non-convex land- scape. arXiv preprint arXi::2012.056400 2020.
Sébastien Gadat and Fabien Panloup. Optimal non-asymptotic bound of the ruppert-polyak averaging without strong convexity. arXiv preprint arXiv: 709.0334, 2017.
Antoine Godichon-Baggion Estimating the geometric median in hilbert spaces with stochastic gradient algorithms: L.p and almost sure rates of convergence. Journal of Mullivariale Analysis, 146:209-229 2016.
Antoine Godichon- Baggioni, Nicklas Werge, and Olivier Wintenberger. Non AsymAsympootic Analysis of Stochas- tic Approximation Algorithms for Streaming Data. working paper or preprint, September 2021. URL
Antoine Godichon- Baggionn, Bruno Portier, and Wei Lu. Recursive ridge regression using second-order stochastic algorithms. 2022.
55

---

Published in Transactions on Machine Learning Research (06/2025)
Robert Gower, Othmane Sebbouh, and Nicolas Loizou. SGD for structured nonconvex functions: Learning rates, minibatching and interpolation. In International Conference Arlificial Intelligence and Stalistics. pp. 1315 1323. PMLR, 2021.
Robert Mansel Gower, Nicolas Loizon, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International Conference on Machine Learning, pp. 5200- 5209. PMLR, 2019.
Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, and Tianbao Yang. Unified convergence analysis for adaptive optimization with moving average estimator. Machine Learning, 114(4):1-51, 2025.
Peter Hall and Christopher Heyde. Martingale limit theory and its applicalion. Academic press, 2014.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradiemt methods under the polyak-lojasiewic. condition. In Joint European conference on machine learning and knowledge discovery in databases, pp. 795 811. Springer, 2016.
Vladimir Koltchinskii and Shahar Mendelson. Bounding the smallest singular value of random matrix without concentration. International Mathematics Rescarch Notices, 2019(23):2991111300, 2015.
Jakub Konečný, Jie Liu, Peter Richtárik, and Martin Takáč. Mini-batel semi-stochastic gradient descent in the proximal setting. IEEE Journal of Selected Topics in Signal Processing, 10(2):242 255, 2015.
Rémi Lelue and François Portier. Asymptotic Optimality of Conditioned Stochastic Gradient Descent. arXiv preprinl Xiv:220006.00 02745, 2020.
Mariane Pelletier. On the almost sure asymptotic behaviour of stochastic algorithms. Stochastic processes and their applications, 78(2):217-24) 1998.
Mariane Pelletier. Asymptotic almost sure efficiency of averaged stochastic algorithms. STAM J. Control Optim., 39 (1):49 72, 2000. ISSN 0363-0129. doi: 10.113775003300129980333 org/ 10. 00011317//033001999331111
URL http://dx. doi.
Tosif Pinelis. Optimum bounds for the distributions of martingales in Banach spaces. The Annals of Probo- bilily, 22:1679 1706, 1994.
Boris Polyak and Anatoli Juditsky. Acceleration of stochastic approximation. SIAM J. Control and Opti- mization, 30:838-855 8558-855,111 1992.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
David Ruppert. Efficient estimations from a slowly convergent robbins-monro process. Technical report, Cornell University Operations Research and Industrial Engineering, 1988.
Roman Vershynin. High- donh-dimmesional probability: An introduction with applications in data science, vol- ume 47. Cambridge university press, 2018.
Haishan Ye, Luo Tuo, and Zhihua Zhang. Approximate newton methods and their local convergence. Tn International Conference on Machine Learning, pp. 3931 3939. PMLR, 2017.
56


Reviews:
[{"review_id": "NbxT5KDrGo", "reviewer": "Reviewer_atrp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nProvide analysis of AdaGrad and Newton algorithms without bounded gradient assumptions. Applied the results to linear regression and regularized generalized linear models. \n\nWeakness:\n1. The analysis only applies for strongly-convex cases. It would be beneficial to generalize the analysis to convex and non-convex regime, or discuss the challenges to do so. \n\n2. What is the theoretically optimal choice of $\\gamma$. Although both $\\gamma\\in(0, 1/2]$ and $\\gamma\\in[1/2, 1)$ have been analyzed, it seems unclear about what should be the choice of $\\gamma$ to derive the best optimal convergence results. For example, according to Proposition 3.2, is it correct to claim that a larger $\\gamma$, as long as $\\gamma < 1$, is always better?\n\n3. The following paper covered the Adabound algorithm without bounded gradient assumption, discussed in the Remark under Assumption 2. Please check:\nguo et. al, On stochastic moving-average estimators for non-convex optimization (https://arxiv.org/pdf/2104.14840).\n\n4. The obtained convergence rates $O(n^{-\\gamma})$ seem to be slower than known results under bounded gradient assumptions since $\\gamma < 1$.  \n\n5. There is a lack of experiments to demonstrate the analysis. For example, it would be helpful to include experiments where bounded gradient assumption does not hold and then analyze whether the behavior of the optimization process is consistent with the theoretical analysis. Also, it would helpful to include some ablation studies to investigate the role of $\\gamma$.  \n\nMinor: \nLine 6 under Introduction \"nam a few\" --> \"name a few\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission studies theoretical non-asymptotic convergence about adaptive optimization methods including AdaGrad and stochastic Newton algorithms. Particularly, if focus on strongly convex problems without bounded gradient assumptions. The analysis depend on assumptions of bounded higher-order moments of gradients (A1), twice continuously differentiable (A2), bounded Hessian (A3), and strong convexity (A4). Analysis has been applied to practical examples, including linear regression and regularized generalized linear models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "NA.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dLBEP1yDqP", "reviewer": "Reviewer_xi3x", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I think this paper makes good contributions. \n\nWhile the theoretical insights are valuable, there are a few areas that could be improved:\n\n1. **Empirical Validation**: The paper emphasizes theoretical results, which would be strengthened by empirical validation. The derived convergence rates are persuasive in theory, but including experiments would enhance the paper’s impact and provide practical insights.\n\n2. **Clarification of Assumptions**: The paper discusses a variety of assumptions, which could benefit from clearer organization. When talking about related work, a table summarizing the assumptions used in each method, along with the corresponding convergence results, would provide a more straightforward comparison and enhance the clarity of the discussion.\n\n3. **Extension to Non-Convex Problems**: The authors could explore the potential for extending the non-asymptotic analysis to a broader class of functions, beyond strongly convex ones. Such an extension would be particularly valuable for practitioners dealing with non-convex problems, which are prevalent in fields like deep learning and machine learning applications.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper offers a comprehensive non-asymptotic analysis of adaptive stochastic gradient algorithms, with a particular focus on their convergence properties in strongly convex optimization problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the Weakness part.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Wdkxyfj23m", "reviewer": "Reviewer_rYhH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n\n1. **Technical novelty**: The paper addresses a significant gap in the existing literature by providing non-asymptotic convergence rates for adaptive stochastic gradient methods without requiring uniformly bounded gradients, a condition often violated in practice.\n2. **Comprehensive theoretical framework**: The analysis covers multiple adaptive algorithms (Adagrad, stochastic Newton) within a unified framework, enabling direct comparison of their convergence properties.\n3. **Practical relevance**: The theoretical results are directly applied to common machine learning models including linear regression and generalized linear models, demonstrating real-world applicability.\n4. **Mathematical rigor**: The paper includes detailed proofs and careful handling of technical conditions, providing a solid theoretical foundation for the results.\n5. **Treatment of edge cases**: The authors explicitly address potential divergence scenarios and provide practical modifications to ensure convergence.\n6. **Clear and well-structured writing**: The paper presents complex mathematical concepts and proofs in a clear, organized manner, making the technical content accessible despite its sophistication.\n### Weaknesses:\n1. **Absence of experimental validation**: \n   The paper lacks numerical experiments to validate the tightness of the theoretical bounds or illustrate their practical implications. While the focus is theoretical, empirical validation would strengthen the paper considerably by showing whether the derived rates match practical performance.\n2. **Restrictive assumptions**:\n   Some of the technical assumptions, particularly (H1b) regarding the spectral norm of the adaptation matrix, are acknowledged by the authors as potentially restrictive. The provided workarounds (modifications to the algorithms) might alter their practical performance in ways not thoroughly analyzed.\n3. **Limited scope to strongly convex objectives**:\n   The analysis is restricted to strongly convex objective functions, which limits applicability to many modern machine learning problems involving non-convex optimization.\n4. **Insufficient comparison with existing bounds**:\n   While the paper mentions some previous work, it would benefit from a more thorough comparison of the derived bounds with existing results in the literature, highlighting specific improvements.\n5. **Insufficient intuition for technical results**:\n   The mathematical development, while rigorous, could be better complemented with intuitive explanations of key results and their practical significance, especially for practitioners.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a non-asymptotic analysis of adaptive stochastic gradient algorithms for strongly convex objective functions. The main contributions are:\n\n1. Establishing convergence rates for adaptive methods when the adaptation matrix may diverge (with controlled divergence bounds)\n2. Deriving standard convergence rates under the additional assumption that the adaptation matrix has uniformly bounded fourth-order moments\n3. Providing a general framework for analyzing both stochastic Newton and Adagrad algorithms\n4. Applying the theoretical results to practical examples including linear regression and ridge-regularized generalized linear models\n5. Handling the technically challenging case of unbounded gradients, which many previous analyses avoid\n\nThe authors evaluate their theoretical framework on two important application domains: linear models and generalized linear models (including logistic regression), demonstrating both the versatility and applicability of their approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Recommendations for Enhancement\n1. **Consider including numerical experiments**: The theoretical contribution would be strengthened by empirical validation demonstrating the tightness of the derived bounds. Comparisons between standard implementations and the proposed modifications on benchmark datasets would illustrate the practical implications of the theoretical results.\n2. **Enhancing with intuitive interpretations**: The paper would benefit from additional intuitive explanations of key technical results and assumptions, particularly highlighting their practical implications for algorithm design and implementation. This would make the sophisticated mathematical content more accessible to practitioners.\n3. **Further comparison with existing literature**: The valuable theoretical contribution could be highlighted more effectively through a comprehensive comparison with existing bounds in the literature. Clarifying how these new results improve upon previous work (particularly Défossez et al. (2020) and  Gower et al., (2019)) would contextualize the advances made.\n4. **Guidance on assumption verification**: Practitioners would benefit from additional guidance on verifying the technical assumptions in practice, especially (H1a) and (H1b). A discussion of scenarios where these assumptions might be violated would provide valuable practical insight.\n5. **Exploration of relaxed assumptions**: Considering possibilities for relaxing the strong convexity assumption, at least for special cases, would broaden the impact of this work. A discussion of how the results might extend to weakly convex or non-convex settings would be valuable for many modern machine learning applications.\n6. **Discussion of computational considerations**: Adding insights on the computational overhead introduced by the proposed modifications would provide helpful guidance for practitioners implementing these methods. This practical perspective would complement the strong theoretical foundation already established.\n7. **Standardize capitalization in references**: The bibliography would benefit from consistent capitalization, particularly for mathematical notation and acronyms. For instance, the asymptotic notation \"o (1/n)\" should be capitalized to \"O (1/n)\" in the Bach and Moulines reference, and \"Sgd\" should be standardized to \"SGD\" in the Gower et al. reference.", "broader_impact_concerns": "This paper is primarily theoretical in nature, with limited direct societal implications. The improved understanding of adaptive optimization methods could lead to more efficient and effective machine learning algorithms, indirectly benefiting applications across various domains.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper focuses on the non-asymptotic analysis of adaptive gradient algorithm, under the assumption that the loss is strongly convex. They also assume the full batch loss is smooth, and the stochastic gradients satisfy a rather general bound on the expected norm of gradient bound. The theory is very general, and applies to a large class of stochastic preconditioned methods so long as the stochastic proeconditioner satisfies some high probability bounds (And deterministic spectral bound). The several of generality is impressive, but as a consequence of being generalm the results are also loose as compared to SGD with no preconditioner. 

To show case their general theory, the develop tighter instantiations of their theory for stochastic Newton and Adagrad. In particular I'm not aware of the work that analysis stochastic Newton in this generality, so it could be of interest to the stochastic second order community.

Because most reviewers were not able to verify the proofs, I ask that the authors take one more pass now, making the proofs as legible as possible, and removing the commented red text. I will then take one final pass over the paper, before having it published in TMLR.
Decision: Accept (poster)