Asymptotic Analysis of Conditioned Stochastic Gradient Descent
Authors: Rémi Leluc
François Portier
Venue: Accepted by TMLR ()

Abstract: In this paper, we investigate a general class of stochastic gradient descent (SGD) algorithms, called $\textit{conditioned}$ SGD, based on a preconditioning of the gradient direction. Using a discrete-time approach with martingale tools, we establish under mild assumptions the weak convergence of the rescaled sequence of iterates for a broad class of conditioning matrices including stochastic first-order and second-order methods. Almost sure convergence results, which may be of independent interest, are also presented. Interestingly, the asymptotic normality result consists in a stochastic equicontinuity property so when the conditioning matrix is an estimate of the inverse Hessian, the algorithm is asymptotically optimal.

Published in Transactions on Machine Learning Research (08/2023)
Asymptotic Analysis of Conditioned Stochastic Gradient Descent
Rémí Lelue
remi.lelue@gmail.comm com
CMAP, École Polgtechnique
Institut Polytechnique de Paris, Palaiseau (France)
François Portier
francois. &omaail com
CREST, ENSAI
École Nationale de la Statistique et de I'Analyse de I'Information, Rennes (Fronce)
Reviewed on OpenReview: https: // openreview. net/ net/forum? id= U4Xg=RjjFF
Abstract
In this paper, we investigate general class of stochastic gradient descent (SGD) algorithms, called conditioned SGD, based on preconditioning of the gradient direction. Using discrete-time approach with martingale tools, we establish under mild assumptions the weak convergence of the rescaled sequence of iterates for a broad class conditioning matrices including stochastic first-order and socond-ordor methods. Almost sure convergence results, which may be of independent interest, are also presented. Interestingly, the asymptotic normality result consists in a stochastic equicontinuity property so when the conditioning matrix is estimate of the inverse Hessian, the algorithm is asymptotically optimal.
1 Introduction
Consider some unconstrained optimization problem of the following form:
min (F (0, GER
where f is loss function and & is random variable. This key methodological problem, known under the name of stochastic programming (Shapiro et al., 2014), includes many flagship machine lcarning applications such as empirical risk minimmization (Bottou et al., 2018), adaptive importance sampling (Delyon & Portier, 2018) and reinforcement learning (Sutton & Barto, 2018). When F is differentiable, common appproach is to rely on first-order methods. However, in many scenarios and particularly in large-scale learning, the gradient of F may be hard to evaluate or even intractable. Instead, random unbiased estimate of the gradient. is available at cheap computing cost and the saate-o-thheart algorithm, slochastic gradient descent (SGD), just moves along this estimate at each iteration. It is an iterative algorithm, simple and computationally fast, but its convergence towards the optimum is generally slow.
Conditioned SGD, which consists in multiplying the gradient estimate by some conditioning matrix at each iteration, can lead better performance as shown several recent studies ranging from natural gradient (Amari, 1998; Kakade, 2002) and stochastic second-order methods with quasi-Newton (Byrd et al., 2016) and (L)-BFGS methods (Liu & Nocedal, 1989) to diagonal scaling methods such as AdaGrad (Duchi et al., 2011), RMSProp (Tieleman et al., 2012), Adam (Kingma & Ba, 2014), AMSGrad (Reddi et al., 2018) and adaptive coordinate sampling (Wangni et al., 2018; Lelue & Portier, 2022). These conditioning techniques are based on different strategies: diagonal scaling rely on feature normalization, stochastic second-order methods are concerned with minimal variance and adaptive coordinate sampling techniques aim at taking advantage of particular data structure. Furthermore, these methods proved to be the current saate-of-tho-arr for training machine learning models (Zhang, 2004; LeCun al., 2012) and are implemented in widely used programming tools (Pedregosa et al., 2011; Abadi et al., 2016).

---

Published in Transactions on Machine Learning Research (08/2023)
Conditioned SGD generalizes standard SGD by adding a conditioning step to refine the descent direction. Starting from 8g E RR,, the algorithm of interest is defined by the following iteration
0x+1 = 02 74+1 Ckg(Oss Ek-1),
k 220,
where g(Ok, Ex+1) is some unbiased gradient valued in RS, Cj E Rddd is called conditioning matriz and (7k)221 is a decreasing learning rate sequence. An important question, which is still open to the best of our knowledge, is to charactorize the asymptotic variance of such algorithms for non-convex objective F and general estimation procedure for the conditioning matrix Ck-
Related work. Seminal works around standard SGD (Cx = La) were initiated by Robbins & Monro (1951) and Kiefer et al. (1952). Since then, a large literature known stochastic approzimation, has developed. The almost sure convergence is studied in Robbins & Siegmund (1971) and Bertsekas & Tsitsiklis (2000); rates of convergence are investigated in Kushner & Huang (1979) and Pelletier (1998a); non-asymptotic bounds are given in Moulines & Bach (2011). The asymptotic normality can be obtained using two different approaches: a iiffusion-based method is employed in Pelletier (1998b) and Benaim (1999) whereas martingale tools are used in Sacks (1958) and Kushner & Clark (1978). We refer to Nevelson & Khas minas'm (1976); Delyon (1996); Benveniste et al. (2012); Duflo (2013) for general textbooks on stochastic approrimation.
The aforementioned results do not apply directly to conditioned SGD because of the presence of the matrix soquence (C&)a20 involving an additional source of randomness in the algorithm. Seminal papers dealing with the weak convergence of conditioned SGD are Venter (1967) and Fabian (1968). Within a restrictive framework (univariate case d d=1 1 and strong assumptions on the function F), their results are encouraging because the limiting variance of the procedure is shown to be smaller than the limiting variance of standard SGD. Venter's and Fabian's results have then been extended to more general situations (Fabian, 1973; Nevelson & Khas minskii, 1976; Wei, 1987). In Wei (1987), the framework is still restrictive not only because the random errors are assumed to be independent and identically distributed but also because the objective F' must satisfy their assumption (4.10) which hardly extends to objectives other than quadratic.
More recently, Bercu et al. (2020) have obtained the asymptotic normality as well as the efficiency of certain conditioned SGD estimates in the particular case of logistic regression. The previous approach has been generalized not long ago in Boyer & Modichon-Baggionn (2022) where the use of the Woodbury matrix identity is promoted to compute the Hessian inverse in the online setting. Several theoretical results, including the weak convergence of conditioned SGD, are obtained for convex objective functions. An alternative to conditioning, called averaging, developed by Polyak (1990) and Polyak & Juditsky (1992), allows to recover the same asymptolic variance as conditioned SGD. When dealing with convex objectives, the theory behind this averaging technique is a well-studied topic (Moulines & Bach, 2011; Gadat & Panloup, 2017; Dieuleveut et al., 2020; Zhu et al., 2021). However, it is inevitably associated with a large bias cansed by poor initialization and requires some parameter luning through the burn-in phase.
Contributions. The main result of this paper deals with the weak convergence of the rescaled sequence of iterates. Interestingly, our asymptotic normality result consists of the following continuity property: whenever the matrix sequence (C&)s20 converges to matrix C' and the iterates (0x)k20 converges to a minimizer 0*, the algorithm behaves in the same way as an oracle version in which C' would be used instead of Cj. We stress that contrary to Boyer & Medichon-Baggion (2022), no convexity assumption is needed on the objective function and no rate of convergence is required on the sequence (Cx))20- This is important because, in most studies, deriving a convergence rate on (Cx)420 requires a specific convergence rate on the itcrates (0x))20 which, in general, is unknown at this stage of the analysis. From a more practical point of view, our main result claims that the impact of the approxination error resulting from the conditioning matrices estimation assumes secondary role. This finding promotes the use of simple and cheap sequential algorithm to estimate the conditioning matrix which encompasses a broad spectrum of conditioned SGD methods, highlighting the applicability and generalizability of the obtained result. Another result of independent. interest dealing with the almost sure convergence of the gradients is also provided.
In addition, for illustration purposes, we apply our results to the popular variational inference problem where one seeks to approximate a target density out of a paramotric family by solving an optimization problem. In this framework, by optimizing the forward Kullback-Liebler divergence (Jerfel et al., 2021) and building
2

---

Published in Transactions on Machine Learning Research (08/2023)
stochastic gradients relying importance sampling schemes (Delyon & Portier, 2018), we show that the approach has some efficiency properties. For the sake of completeness, we present in appendix practical ways to compute the conditioning matrix C₁ and show that the resulting procedure satisfies the high-level conditions of our main Theorem. This yields a fcasible algorithm achieving minimum variance.
To obtain these results, instead of approximating the rescaled sequence of iterates by a continuous diffusion (as for instance in Pelletier (1998b)), we rely on a discrete-time approach where the recursion scheme is directly analyzed (as for instance in Delyon (1996)). More precisely, the sequence of iterates is studied with the help of an auxiliary linear algorithm whose limiting distribution can be deduced from the central limit theorem for martingale increments (Hall & Heyde, 1980). The limiting variance is derived from a discrete time matrix-valued dynamical system algorithm. It corresponds to the solution of a Lyapunov equation involving the matrix C. It allows a special choice for which guarantees an optimal variance. Finally, a particular recursion is identified to examine the remaining part. By studying it on a particular event, this part is shown to be negligible.
Outline. Section 2 introduces the framework of standard SGD with asymptotic results. Section 3 is dedicated to condilioned SGD: it first presents popular optimization methods that fall in the considered framework and then presents our main results, namely the weak convergence and asymptotic optimality. Scction 4 gathers practical implications of the main results for machine learning models in the framework of variational inference and Section concludes the paper with a discussion of avenues for further research. Technical proofs, additional propositions and numerical experiments are available in the appendix.
2 Mathematical background
In this section, the mathematical background of stochastic gradient descent (SGD) methods is presented and illustrated with the help of some examples. Then, to motivate the use of conditioning matrices, we present known result from Pelletier (1998b) about the weak convergence of SGD.
2.1 Problem setup
Consider the problem of finding minimizer 0* Rdd of function F: Rd - TR that is,
0t arg F(0). AERd
In many scenarios and particularly in large scale learning, the gradient of F cannot be fully computed and only a stochastic unbiased version of it is available. The SGD algorithm moves the iterate along this direction. To increase the efficiency, the random generators used to derive the unbiased gradients might evolve during the algorithm, e.g., using the past iterations. To analyse such algorithms, we consider the following probabilistic setting.
Definition 1. stochastic algorithem is a sequence (0x)s20 of random variables defined on a probability space FP) and valued in Rd. Define (Fr) as the natural o o-field associated to the stochastic algorithm (fx),20, i.c., Fx (fo, 01.-.., 0x), k 0. A policy is sequence of random probability measures (Pk (22)s each defined on measurable space () that are adapted to Fs.
Given policy (Pa)a2a and learning rales sequence (Tw)a2 of posilive numbers, the SGD algorithm (Robbins & Monro, 1951) is defined by the update rule
0++1= = - 7 Ex+1) with Ek+1 ~ Pk,
(1)
where g: Rdd x S + Rd is called the gradient generator. The choice of the policy (Px) in SGD is important as it can impact the convergence speed, generalization performance, and efficiency of the optimization algo- rithm. While most classical approaches rely on uniform sampling and mini-batch sampling, may be more efficient to use advanced selection sampling strategy such as stratified sampling or importance sampling (sce Example 1 for details). The policy (Px) used at each iteration to produce random gradients through the function g. Those gradients are assumed to be unbiased.
3

---

Published in Transactions on Machine Learning Research (08/2023)
Assumption 1 (Unbiased gradient). The gradient generator g IR S - R² is such that for all 0 E R
g(0,,) is measurable, and we have: wk 2 0, TE ([g((n: V F(O)).
We emphasize three important examples covered by the developed approach. In each case, explicit ways to gencrate the stochastic gradient are provided.
Example 1. (Empirical Risk Minimizalion) Given some observed data E1..... Fn E Rp and a differentiable loss function L: I x Rp + R. the objective function F' approximates the true expected risk E, [e[( z)] using its empirical counterpart F(0) = n "m= E(0,22 zi). Classically, the gradient estimates at 8& are given by the policy
g(0k, Ex+1) = Vol(ORs Ex+1) with EK+1
óz,/n. nn.
1=1
Another one, more subtle, referred to as mini-batching (Gower al., 2019), consists in generating uniformly set of n, samples (Z1...., 2nx) and computing the gradient as the average nk _j=1 Vol(On. 22). Note that interestingly, we allow changes of the minibatch size throughout the algorithm. Our framework also includes adaptive non-uniform sampling (Papa et al., 2015) and survey sampling (Clémengon et al., 2019), which use Ps- - Ei= w//h) 82, with F& Fa-adapted weights satisfying Σ (*) for each k 0.
Example 2. (Adaptive importance sampling for variational inference) Given target density function f. which for instance might. result. from the posterior distribution of some observed data, and a parametric family of samplers {go 0 E θ), the aim is to find a good approximation of f out of the family of samplers. A standard choice (Jerfel et al., 2021) for the objective function is the so called forward Kullback- Kullback-Leibler Leibler divergence given by F(0) = - f Log(ge (v)/
f(y) ( Then in the spirit of adaptive importance sampling schemes (Delyon Portier, 2018), gradient estimates are given by
f(xx+1) qo, (Ex+1)' Ek+1 9o.-
Ex+1) - Vo (Eg(9),(Ex+1))
Other losses such as a-divergence (Daudel et al., 2021) or generalized method of moment (Delyon & Portier, 2018) may also be considered depending on the problem of interest. Some applications of conditioned SGD algorithm to this particular framework are considered with more details in Section 4.
Example 3. (Policy-grudient methods) In reinforcement learning (Sutton & Barto, 2018), the goal of the agent is to find the best action-seloction policy to maximize the expected reward. Policy-gradient methods (Baxter & Bartlett, 2001; Williams, 1992) use a parameterized policy { : E @} to optimize an expected reward function F given by F(0)= = E [R(E)] where & is a trajectory including nature states and selected actions. Using the policy gradient theorem, REINFORCE algorithm (Williams, 1992) given by
has F(O) = ER [R log (o))), leading to the
g(Ox,Eu+1) = R(Ex+1)( log no (Ex+1), Ex-1 ~ no
2.2 Weak convergence of SGD
This section is related to the weak convergence property of the normalized sequence of iterates (0x-0-)/ // The working assumptions include the almost sure convergence of the sequence of iterates (0z) towards a stationary point 0*. Note that, given Assumptions and 2, there exist many criteria on the objective function that give such almost sure convergence. For these results, we refer to Bertsckas & Tsitsiklis (2000); Benveniste et al. (2012); Duflo (2013). In addition to this high-level assumption of almost sure convergence, we require the following classical assumptions. Let S denote the space of real symmetric positive definite matrices and define for all A 2 0,
Wh+1 = FF(02) - 9000 E641), F E (Wktiw/411
The learning rates sequence (74)221 should decay to eventually anneal the noise but not too fast so that the iterates (Ox )220 can reach interesting places in finite time.
4

---

Published in Transactions on Machine Learning Research (08/2023)
Assumption 2 (Learning rates). The sequence of step-size is 7k = ak with B E (1/2,
This classical form of the step-size ensures theoretical convergence guarantee through the Gobbins-Monn condition: Σx 7kk = xo, Ex rh < 20. However, note that in practice, the choice of learning rate is often determined through experimentation and fine-tuning to achieve the best performance on the given task.
Assumption 3 (Hessian). The Hessian matriz at stationary point is positive definite, i.e,, H = F2F(6") S (R) and the mapping - F()) is continuous al 0
The positive definiteness of the Hessian matrix provides stability and robustness guarantees in the optimiza- tion process. ensures that small perturbations or noise in the objective function or the training data do not siguificantly affect the convergence behavior. The positive curvature helps in confining the optimization trajectory near the minimum and prevents it from getting trapped in flat regions saddle points.
The noise sequence (ux)k21 defines sequence of conditional covariance matrices (Tk)k21 that is assumed to converge that one can identify the limiting covariance I (l)(()))))(("
.E) ']
Assumption 4 (Covariance matrix). There erists T S (R)) such that F& A r a.s.
Finally, in order to derive central limit theorem for the itcrates of the algorithm, there is extra need for stability which is synonymous with uniform bound on the noise around the minimizer. Assumption 5 (Lyapunov bound). There ezist 6, such that:
sup B[[[w]-11e 2+ 1 110 0o a.s.
#20
Note that all these assumptions are stated in the spirit of Pelletier (1998b) making them mild and general. In particular, Assumptions 4 and 5 similar to (A1.2) in Pelletier (1998b). More precisely, Assumption 4 is needed to identify the limiting distribution while Assumption 5 is stability condition often referred to as the Lyapunov condition. This last condition is technical but not that strong as it is similar to the Lindeberg's condition which is necessary (Hall & Heyde, 1980) for tightness. The following result can be either derived from (Pelletier, 1998b, Theorem 1) or as a direct corollary of our main result, Theorem 2, given Section 3.2.
Theorem 1 (Weak convergence of SGD). Let (0x)220 be oblained by the SGD rule (1). Suppose that Assumptions 1, 2, 3, 4, 5 are fulfilled and that Og - Hr almost surely. If moreover, (H - CT) is positive definite with Ç = 1/=11/2a, holds that
(On - (0000))~((02))
as k +
TTk
where E satisfies the Lyapunov equation: (H (Ta) (Ia)" IT.
Several remarks are to be explored. Since and (H (1) are positive definite matrices, there exists a - given by Σ = So p4000 expl-t(H- [Ta]] cxpl-t(H- - (Ia) Second, the previous result can be expressed as k.9/ l*) ~s NOO., oE). Hence, the fastest rate of convergence is obtained when 3 for which we recover the classical 1/ VT-rate of a Monte Carlo estimate. In this case, the coefficient should be chosen large enough to ensure the convergence through the condition H - (a > 0, but also such that the covariance matrix aΣ is small. The choice of a is discussed in the next section and should be replaced with a matrix gain.
unique solution Σ to the Lyapunov equation (H - +
3 The asymptotics of conditioned stochastic gradient descent
This Section first presents practical optimization schemes that fall in the framework conditioned SGD, Then it contains our main results, namely the weak convergence and asymptotic optimality. Another result of independent interest dealing with the almost sure convergence of the gradients and the iterates is also provided.
5

---

Published in Transactions on Machine Learning Research (08/2023)
3.1 Framework and Examples
We introduce the general framework of condilioned SGD as extension of the slandard SGD presented in Section 2. It is defined by the following update rule, for k 2 0,
Ok+1 = 02 - -k+ C Ex+1);
(2)
where the conditioning matriz C& E S (R) is Fi-mcasurable real symmetric positive definite matrix so that the search direction always points to a descent direction. In convex optinization, inverse of the Hessian is a popular choice but (1) it may be hard to compute, (2) it is not always positive definite and (3) it may increase the noise of SGD especially when the Hessian ill-conditioned.
Quasi-Newton. These methods build approximations of the Hessian C2 (2)()))~ with gradient-only information, and are applicable for convex and nonconvex problems. For scalability issue, variants with limited memory are the most used in practice (Liu & Nocedal, 1989). Following Newton's method idea with the secant equation, the update rule is based on pairs (sk, Uk) tracking the differences of iterates and stochastic gradients, i.C., 8k = 0x+1 - 0g and yk = g(0x+1,, Ex+1) g(Ok, Ex+1)- Let Pk = 1/ yk) then the Hessian updates are
Ck+1 = (I- PKyNS T - + PASKST
In the deterministic setting, the BFGS update formula above is well-defined as long as 8 > 0. Such con- dition preserves positive definite approximations and may be obtained in the stochastic setting by replacing the Hessian matrix with a Gauss-Newton approximation and using regularization.
Adaptive methods and Diagonal scalings. These methods adapt locally to the structure of the opti- mization problem by setting Cg as function of past stochastic gradients. General adaptive methods differ in the construction of the conditioning matrix and whether or not they add momentum term. Using different representations such as dense or sparse conditioners also modify the properties of the underlying algorithm. For instance, the optimizers Adam and RMSProp maintain an exponential moving average of past stochastic gradients with a factor т E (0, 1) but fail to guarantee Ck+1 A Cg. Such behaviour can lead to large fluctuations and prevent convergence of the iterates. Instead, AdaGrad and AMSGrad ensure the monotonicity Ck+1 3 Cz.
Optimizer Gradient matrix Gk+1
AdaFull
Gş + 9kd
AdaNorm
G: + || 1
0
AdaDiag
G + diag(g
RMSProp
rG₁ + (1 - ((1-))diagel T)diag(gkg()
Adam
[TG₁ + (1 T)diag (g:9) )1/(1 7²)
AMSGrad
[G2 + (1 T)diag((da))) (gagk )1/(1 7*) m
Table 1: Adaptive Gradient Methods.
Denote by 9z g 14+1) and E [0,1) momentum paramcter. General adaptive gradient methods are defined by: 0x+1 = 0₂ 7kt1Ckku år mrg-1 (1 m)9x. Different optimizers summarized in Table above. They all rely on gradient matrix Gk which accumulates the information of stochastic gradients. The conditioning matrix equal to Ci G-1/2 except for AMSGrad which uses C2 max (Cx Starting from Go 51 with 8 > O, G&+1 is updated either in a dense sparse (diagonal) manner or using exponential moving average. Note that conditioned SGD methods also include schemes with general estimation of the matrix C₁ such as Hessian sketching (Gower et al., 2016) or Jacobian sketching (Gower et al., 2021).
A common assumption made in the literature of adaptive methods is that conditioning matrices are well- behaved in the sense that their cigenvalues are bounded in a fixed interval. This property is easy to check for diagonal matrices and can always be implemented in practice using projection.

---

Published in Transactions on Machine Learning Research (08/2023)
3.2
Main result
Similarly to standard SGD, it is interesting to search for an appropriate rescaled process to obtain some convergence rate and asymptotic normality results. In fact the only additional assumption needed, compared to SGD, is the almost sure convergence of the sequence (Cx)a20- This makes Theorem a particular case of the following Theorem which the main result the paper (the proof is given in Appendix A.1).
Theorem 2 (Weak convergence of Conditioned SGD). Let (0x)k20 be obtained by conditioned SGD (2). Suppose that Assumptions 1, 2, 3, 4, 5 are fulfilled and that 0x + 0 almost surely. If moreover, Cs + C St (R) almost surely and all the eigenvalues of (CH- -(I are positive with Ç = 1 (a=1) 2a, it holds that
103 0²) ~ (0,
as k - x0,
Vik
where De satisfies: (CH - (la) Ec + Ec (CH - (ld) = CTCT.
Sketch of the proof. The idea of the proof is to rely the following bias-variance decomposition. Remark that the difference A₂ = 0g 0* is subjected to the iteration:
A = AK T C&FFL)) + M641CRWE41,
A: 2 0.
In a similar spirit as in Delyon (1996), we use the Taylor approximation VF(0k) V)(()) + H(0, 0*) + o(0, - -*) ~ (0, 0*) to define the following auxiliary linear stochastic algorithm which carries the same variance as the main algorithm,
Â = A -K+IKK 16+11 CR
2 1,
where K = CH. As a first step we establish the weak convergence of Âx+1 using discrete martingale tools. Note that the analysis is made possible because the matrix K is fixed along this algorithm. As second step, we prove that the difference (Ax - -A),, which represents some bias term, is negligible.
Comparison with previous works. Theorem 2 stated above is comparable to Theorem 1 given in Pelletier (1998b). However, our result on the weak convergence cannot be recovered from the one Pelletier (1998b) due to their Assumption (A1.2) about convergence rates. Indeed, this assumption would require that the sequence (Cz)a20 converges towards C' faster than VTk- This condition is either hardly meet practice or difficult to check. Unlike this prior work, our result, only requires the almost convergence of the sequence (Cx)s20- In more restrictive setting of convex objective and online learning framework, f.e. in which data becomes available in a sequential order, another way to obtaín the weak convergence of the rescaled sequence of iterates (0x-0))/ VT is to rely on the results of Boyer & Godichon- Boagioon-Baggiooi (2022). However, once again, their work rely on a particular convergence rate for the matrix sequence (Ck) This implics the derivation of an additional result on the almost sure convergence rate of the iterates. To overcome all these issues, we show in Appendix that our conditions on the matrices Cg are easily satisfied in common situations.
3.3 Asymptotic optimality of Conditioned SGD
The best conditioning matrix C that could be chosen regarding the asymptotic variance is specified in the next proposition whose proof is given in the supplementary material (Appendix C.3).
Proposition 1 (Optimal choice). The choice C* H-1 is optimal in the sense that Ec- I Ec for all C' E CH. Moreover, we have Σc. = --
Another remarkable result, which directly follows from the Theorem 2 is now stated as corollary.
Corollary (Asymptotic optimality). Under the assumptions of Theorem 2, if 7h 1/k and C H-1 then
Vh(0e 0*) NoO, H "HH as

---

Published in Transactions on Machine Learning Research (08/2023)
Moreover, let (Zi...., Za) (( Id) and (Ak))=l.....d be the eigenvalues of the matrix H H-1/3TH 1/2 have the convergence in distrivulion:
((F(0k)-F() F(O)))
~ Σ Nq Zh.
as k 00.
This result shows the success of the proposed approach as the asymptotic variance is the optimal one. It provides the user practical choice for the sequence of rate, 7 -== 1/k and also removes the assumption that 2aHl la which is usually needed in SGD (see Theorem 1). Concerning the almost sure convergence of the conditioning matrices, we provide in Appendix B an explicit way to ensure that C2 - HH!
The above statement also provides insights about the convergence speed. It claims that the convergence rate of F(Os) towards the optimum F(0"), in 1/k, is faster than the convergence rate of the iterates, in 1/vk. Another important feature, which is a consequence of Proposition 1, is that the cigenvalues (A+)k=1,....d that appear in the limiting distribution are the smallest ones among all the other possible version of conditioned SGD (defined by the matrix C*).
3.4 Convergence of the iterates (0x) of Conditioned SGD
To apply both Theorem 2 and Corollary 1, it remains to check the almost sure convergence of the iterates. In a non-convex setting, the iterates of stochastic first-order methods can only reach local optima, i.e. the iterates are expected to converge to the following set S = {0 E g VF(0) = 0}. Going in this direction, we first prove the almost sure convergence of the gradients towards zero for general conditioned SGD methods under mild assumptions. This theoretical result may be of independent interest. Under a condition on S, one may uniquely identify limit point 4* and consider the event (0x 6*) which is needed for the weak convergence results. The next analysis is based on classical assumptions which are used in the literature to obtain the convergence of standard SGD.
Assumption (L-smooth). EL > 0 V0,NE [VF(() - VF S LI10 n/12.
Assumption 7 (Lower bound). =F E VRR:VORR,FT F < F(0).
To handle the noise of the stochastic estimates, we consider a weak growth condition, related to the notion of expected smoothness as introduced in Gower et al. (2019) (see also Gazagnadou et al. (2019); Gower el al. (2021)). In particular, we extend the condition of Gower et al. (2019) to our general context in which the sampling distributions are allowed to change along the algorithm.
Assumption 8 (Growth condition). With probability 1, there erist 0 s L, < such that for all e e k E N, E [llo(0, & [113 < 2C(F(0) - F²) + o2.
This almost-sure bound on the stochastic noise E [0 [x) is key in the analysis of the conditioned SGD algorithm. This weak growth condition on the stochastic noise is general and can be achieved in practice with general Lemma. available in the supplement (Appendix C.4). Note that Assumption 8, often referred to as a growth condition, is mild since it allows the noise to be large when the iterate is far away from the optimal point. In that aspect, it contrasts with uniform bounds of the form E [00, 1B S o² for some deterministic o² (see Nemirovski et al. (2009); Nemirovski & Yudin (1983): Observe that such uniform bound is recovered by taking L = 0 Assumption but cannot hold when the objective function F strongly convex (Nguyen et al., 2018). Besides, fast convergence rates have been derived in Schmidt & Roux (2013) under the strong-grouthh condition: [[]lg(0, 118 I F()) for some M O. Similarly to our growth condition, Bertsekas & Tsitsiklis (2000) and Bottou et al. (2018) performed an analysis under the condition B(llg(f. [F) S (I)VF(() + o² 2 for M, > 0. Under Assumptions 6 and 7, we have (|))) < (F F(O*)) (Gower et al., 2019, Propasition A.1) so our growth condition less restrictive. If F satisfies the Lojyak-Lojasiewizz condition (Karimi et al., 2016), then our growth condition bocomes a bit stronger. Another weak growth condition has been used for a non-asymptotic study in Moulines & Bach (2011). The success of conditioned SGD relies on the following extended Robbins- Monro condition which ensures control on the eigenvalues of the conditioning matrices.
et al. (2011)).
8

---

Published in Transactions on Machine Learning Research (08/2023)
Assumption 9 (Eigenvalues). Let (uu)x21 and (uk)a21 be positive sequences such that: 4k 2 1, 3 CR-1 3 Uk ld; Σx Tk = +00; [x(nu)) < +oo; lim sups Vt/ pa < 0o 0.8.
The last condition deals with the ratio (v) which may be as conditioned number and ensures that the matrices Cg are well-conditioned. The following Theorem reveals that all these assumptions are sulficient to ensure the almost sure convergence of the gradients Lowards zero.
Theorem 3 (Almost sure convergence). Suppose that Assumptions 6, 7, 8, 9 are fulfilled. Then (0=) obtoined by conditioned SGD (2) satisfies ((,))) - 0 as k + oo 0.8.
Other convergence results concerning the sequence of iterates towards global minimizers may be obtained by considering stronger assumptions such as convexity or that F is coercive and the level sets of stationary point n {0, F(0) = y} are locally finite for every y E R (see Gadat et al. (2018)). In our analysis, the proof of Theorem 3 reveals that 0k+1 0% 0 I and almost surely. Thus, as soon as the stationary points are isolated, the sequence of iterates will converge towards unique stationary point 0" E Rd. This result is stated in the next Corollary.
Corollary (Almost sure convergence). Under the assumptions of Theorem 3, assume that F is coercive and let (0x) be the sequence of iterates obtained by the conditioned SGD (2), then d(fk, - 0 as k 00. In porticular, if S is finile sel, (0x) converges to some 0" E.
4 Asymptotic optimality in Adaptive importance sampling
The aim of this section is to demonstrate that statistical efficiency be ensured in variational inference problems through the combination of adaptive importance sampling and conditioned SGD. While well- known results regarding the asymptotic optimality of maximum likelihood estimates (MLE) obtained from conditioned SGD (see for instance Amari (1998) or Bercu et al. (2020)) are initially revisited, attention is subsequently shifted towards the variational inference topic relying on adaptive sampling schemes methods. A novel result is then presented, assorting that even within this challenging framcwork, conditioned SGD allows for the recovery of certain statistical efficiency.
4.1 Maximum likelihood estimation
Assume that (Xe)221 an independent sequence of random variables with distribution g". Consider a parametric family {ge 0 θ} from which we aim obtain an estimate of q*. We further assume that the model is well-specified, f.e. 9² qa- for some 4" Q. The MLE is given by
O, E arg max
Σ log(ao
BEE
Under suitable condition (van der Vaart, 1998), is well known that é,, is efficient, meaning asymptot- ically unbiased and has the smallest. achievable variance. The Cramer-Rao bound is given by the inverse of the Fisher information matrix, denoted by I-1 and defined as
/ Vo (ogg(go))) log(go-) T do
Unfortunately, the estimate O, is often unknown in closed-form, requiring the use of a sequential procedure for approximation. This raises the further question of whether the estimate obtained through the sequential procedure achieves the officiency bound. When using standard SGD without conditioning, the update rule is fx+1 = 0₁ M log(ge, (X++1)). However, the optimal variance bound not achieved this case. To recover efficiency, one can rely on conditioned SGD, incorporating a conditioning matrix that estimates the inverse of the Hessian. In light of the definition of the Fisher information matrix, the conditioning matrix can be estimated iteratively using at each step new sample X follows
I++1 (1 I + 7k41 v log(go, V log(go, (Xx))
9

---

Published in Transactions on Machine Learning Research (08/2023)
and then relying the CSGD algorithm with update rule 0x+1 0k - - log(10, (Xx+1)). As consequence of Theorem 2, under stipulated assumptions, one can recover the optimal bound I-1 as the asymptotic variance of vk(0, - 0*).
4.2 Adaptive importance sampling
Consider the variational inference problem where the aim is to approximate a target distribution q" qo based on family of density f9o : : e Unlike the previous statistical framework, one does not have access random variables distributed according to q². Instead, one can usually evaluate the largel. function q*- More background about this type of problem might be found in Zhang et al. (2018). In the following, we show that conditioned SGD methods allow to achieve the same variance as the optimal variance described in the previous statistical setting. To the best of our knowledge, this result is novel and has potential implications in variational inference problems using forward KT. (or a-divergence) as described in Jerfel et al. (2021) and Section 5.2 in Zhang et al. (2018). Consider the objective function defined as the Kullback- Liebler divergence between a sampler qo and the target distribution q², i.e.,
F(0) = f log(ge/d")g"ddl dX.
Under regularity conditions, the gradient and Hessian are respectively written VgF(0) = - log(4o) and (0) = E,, V log(go)]. Stochastic gradients can be defined using adaptive importance sampling- based estimate as in Delyon & Portier (2018). Given the current iterate fg. one needs to generate X from 99, and compute the (unbiasod) stochastic gradient Ik+1 = U VA+1 where uk+1 = q (X 1/+1)/gpp /// (Xx+1) and Vk+1 = Ve log(ge, (Xx+1)). Based on our almost sure convergence result, one can obtain that 0g + 8" and then deduce
/ Vo log(gg, log(go.)
lim B[0x+19T lim 1+000
)T
dA=I.
1=+00
q0
where the value I for the limit comes from replacing qa, by its limit qø- =q" The choice of the conditioning matrix Ck may be done using an auxiliary algorithm of the following form
Ck+1 = (1 C + 7+110k+1 V
It can be shown that the sequence of conditioning matrices (C²) converges to I. Thus, Theorem 2 implies that conditioned SGD is efficient in this framework as it matches the lower bound of the previous less restrictive statistical framework in which qk = q². Similar computations, left for future work, may be performed to investigate if the same optimal variance can be achieved with more general similarity measures such as a-divergences (Daudel et al., 2021).
5 Conclusion and Discussion
We derived an asymptotic theory for Conditioned SGD methods in a general non-convex setting, Compared to standard SGD methods, the only additional assumption required to obtain the weak convergence is the almost sure convergence of the conditioning matrices. The use of appropriate conditioning matrices with the help of Hessian estimates is the key to achieve asymptotic optimality. While our study focuses on the weak convergence of the rescaled sequence of iterates an appropriate tool to deal with efficiency issues since algorithms can be casily compared through their asymptotic variances it would be interesting to complement our asymptotic results with concentration inequalities. This research direction, left for future work, may be done at the cost of extra assumptions, e.g., strong convexity of the objective function combined with bounded gradients. Furthermore, by using some recent results on the behavior of adaptive gradient methods in non-convex settings (Daneshmand et al., 2018; Staib et al., 2019; Antonakopoulos et al., 2022), another research direction would be to extend the current weak convergence analysis to edge cases where the objective function possesses saddle points.
From a practical standpoint, the approach proposed in Appendix may not be computationally optimal as it requires cigenvalue docomposition. However, conditioned SGD methods and espocially stochastic second- order methods do not actually require the full computation of matrix decomposition but rely on matrix- vector products which may be performed in (d2) operations. Futhermore, using low-rank approximation
10

---

Published in Transactions on Machine Learning Research (08/2023)
with BFGS algorithm (Broyden, 1970; Fletcher, 1970; Goldfarb, 1970; Shanno, 1970) and its variant L-BFGS
(Liu & Nocedal, 1989), those algorithms approximately invert Hessian matrices in O(d) operations. More recently, this technique was extended to the online learning framework (Schraudolph et al., 2007) and purely stochastic sctting (Moritz et al., 2016). Similarly, the different adaptive optimizers presented in Section 3.1 are concerned with both fast computations and high precision. Designing an efficient. conditioned SGD algorithm involves careful trade-off between the low-memory storage of the scaling matrix representation Ck and the quality of its approximation of either the inverse Hessian V²F(0+)- or the information brought in by the underlying geometry of the problem.
Acknowledgments
The authors are grateful to the Associate Editor and three anonymous Reviewers for their many valuable comments and interesting suggestions.
References
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: A system for large-scale machine learning. In 12th {USENIX} symposium on operating systems design and implementation (1 (SDD))) 16), pp. 265 283, 2016.
Shun-Ichi Amari Natural gradient works efficiently in learning. Neural computation, 10(2):251-22) 1998.
Kimon Antonakopoulos, Panayotis Mertikopoulos, Georgios Piliouras, and Xiao Wang. Adagrad avoids saddle points. In International Conference on Machine Learning, pp. 731-771. PMLR, 2022.
Jonathan Baxter and Peter L Bartlett. Infinite-horizon volicy-gradiens estimation. Journal of Artificial Intelligence Research, 15:319 350, 2001.
Michel Benaïm. Dynamics of stochastic approximation algorithms. In Seminaire de probabilites XXXIII, pp. 1-68. Springer, 1999.
Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic approzimations, volume 22. Springer Science & Business Media, 2012.
Bernard Bercu, Antoine Godichon, and Bruno Portier. An efficient stochastic newton algorithm for parameter estimation in logistic regressions. SIAM Journal on Control and Optimization, 38483334,,3 2020.
Dimitri P Bertsekas and John N Tsitsiklis. Gradient convergence in gradient methods with errors. SIAM
Journal on Optimization, 10(3):627-642 2000.
M Émile Borel. Les probabilités dénombrables et leurs applications arithmétiques. Rendiconti del Circolo Matematico di Palermo (1884-1940). 27(1):247-271, 1909.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-31) 221223111111113 2018.
Claire Boyer and Antoine Godichon- Madichon-Baggioni. On the asymptotic rate of convergence of stochastic newton algorithms and their weighted averaged versions. Computational Optimization and Applications, pp. 1-52, 2022.
Charles George Broyden. The convergence of class of double-rank minimization algorithms 1. general considerations. IMA Journal of Applied Mathematics, 6(1):76 90, 1970.
Richard H Byrd, Samantha L Hansen, Jorge Nocedal, and Yoram Singer. A stochastic quasi-newton method for large-scale optimization. STAM Journal on Optimization, 26(2):1008-100) 2016.
11

---

Published in Transactions on Machine Learning Research (08/2023)
Stephan Clémençon, Patrice Bertail, Emilic Chautru, and Guillaume Papa. Optimal survey schemes for stochastic gradient descent with applications to m-estimation. ESATM: Probabilily and Stalistics, 23: 310 307, 2019.
Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. In International Conference on Machine Learning, pp. 1155 1164. PMLR, 2018.
Kamélia Daudel, Randal Douc, and François Portier. Infinite-dimensional gradient-basod descent for alpha- divergence minimisation. The Annals of Statistics, 49(4):2250 2270, 2021. doi: 10.1214/20A0520035
URL pettps:/ddoi.rgge
A0S2035.
Bernard Delyon. General results on the convergence of stochastic algorithms. IEEE Trunsactions on Aulo- matic Control, (1(9):1245-12)) 1996.
Bernard Delyon and François Portier. Asymplotic optimality of adaplive importance sampling. In Pro- ceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 3138 3148. Curran Associates Inc., 2018.
Bernard Delyon and François Portier. Safe adaptive importance sampling: A mixture approach. The Annals of Statistics, 49(2):885 917, 2021.
Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and markov chains. Annals of Statistics, 48(3):1348 1382, 2020.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http: ics, uci edu/ ml.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, (2(Jul):2121 2159,, 2011.
Marie Duflo. Random iterative models, volume 34. Springer Science & Business Media, 1st edition, 2013.
Vaclav Fabian. On asymptotic normality in stochastic approximation. The Annals of Mothematical Statistics, 39(4):1327-1333) 1968.
Vaclav Fabian. Asymptotically efficient stochastic approximation; the rm case. The Annals of Statistics, 1 (3):486 495, 1973.
Roger Fletcher. A new approach to variable metric algorithms. The computer journal, 13(3):317-322 1970.
Sébastien Gadat and Fabien Panloup. Optimal non-asymptotic bound of the ruppert-polyak averaging without strong convexity. arXiv preprint 1xXiv:17090033/ 2017.
Sébastien Gadat, Fabien Panloup, Sofiane Saadane, al. Stochastic heavy ball. Electronic Journal of Statistics, 12(1):461-52) 2018.
Nidham Gazagnadou, Robert Gower, and Joseph Salmon. Optimal mini-batch and step sizes for saga. In International conference on machine learning, pp. 2142-2150. PMLR, 2019.
Donald Goldfarb. A family of variable-metric methods derived by variational means. Mathematics of com- putation, 24(109):23-22) 26, 1970.
Robert Gower, Donald Goldfarb, and Peter Richtárik. Stochastic block bigs: Squeezing more curvature out of data. In International Conference on Machine Learning, pp. 1869-1878. PMLR, 2016.
Robert M Gower, Peter Richtárik, and Francis Bach. Stochastic quasi-gradient methods: Variance reduction via jacobian sketching. Mathematical Programming, 188(1):135-192, 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.
12

---

Published in Transactions on Machine Learning Research (08/2023)
P. Hall and C.C. Heyde. Martingale Limit Theory and Its Application. Probability and mathematical statistics. Academic Press, 1980. ISBN 9781483240244, URL https://books. google fr/books?ic wdLajgEACAAJ.
David Harrison Jr and Daniel L Rubinfeld. Hedonic housing prices and the demand for clean air. Journal of environmental economics and manogement, 5(1):81-102, 1978.
Ghassen Jerfel, Serena Wang, Clara dan. Variational refinement. for importance sampling using the forward kullback-leibler divergence. Tn Uncertainty in Artificial Intelligence, pp. 1819 1829, PMLR, 2021.
Katherine A Heller, Yian Ma, and Michael Jor-
Sham M Kakade. natural policy gradient. In Advances in neural information processing systems, pp. 1531-1538, 2002.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradions methods under the polyak-lojasiewizz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795-811. Springer, 2016.
Hassan K Khalil. Nonlinear systems; 3rd ed. Prentico-Hall, Upper Saddle River, NJ, 2002. URL https:
//cds. cern. ch/..ecord//117334....
Jack Kiefer, Jacob Wolfowitz, et al. Stochastic estimation of the maximum of regression function. The Annals of Mathematical Statisties, 23(3):462-44) 466, 1952.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv:1412. 6980, 2014.
ar preprint
Harold J Kushner and Hai Huang. Rates of convergence for stochastic approximation type algorithms. SIAM Journal on Control and Optimization, 17(5):607 617, 1979.
Harold Joseph Kushner and Dean S Clark. Stochastic approximation methods for constrained and uncon- strained systems. 1978.
Yann LeCun, Léon Bottou, Genevieve Orr, and Hobus- Müller. Efficient backprop. In Newral networks: Tricks of the trade, pp. 9-48. Springer, 2012.
Rémi Lehic and François Portier. Sgd with coordinate sampling: Theory and practice. Journal of Machine Learning Research, 23(422): 47, 2022. URL http://jmmr... http://jal..oog/paapessss ort//appers//2///11124 html.
Dong C Liu and Jorge Nocedal. On the limited memory blgs method for large scale optimization. Mothe- matical programming, 45(1):503-55) 528, 1989.
Philipp Moritz, Robert Nishihara, and Michael Jordan. A linearly-convergent stochastic I-bfgs algorithm. In Artificial Intelligence and Statistics, pp. 249-258. PMLR, 2016.
Eric Moulines and Francis R Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Newral Information Processing Systems, pp. 451-459, 2011.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approxima- tion approach to stochastic programming. STAM Journal on oplimization, 19(4):1574-1600 2009.
Arkadi Semenovich Nemirovski and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov. Introductory lectures on conver optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Mikhail Borisovich Nevelson and Rafail Zalmanovich Khas'minskif. Stochastic opprorimation and recursive estimation, volume 47. American Mathematical Soc., 1976.
13

---

Published in Transactions on Machine Learning Research (08/2023)
Lam Nguyen, Phuong Ha Nguyen, Marten Dijk, Peter Richtárik, Katya Scheinberg, and Martin Takác. Sgd and hogwild! convergence without the bounded gradients assumption. In International Conference Machine Learning, pp. 3750 3758. PMLR, 2018.
Guillaume Papa, Pascal Bianchi, and Stéphan Clémençon. Adaptive sampling for incremental optimization using stochastic gradient descent. In International Conference on Algorithmic Learning Theory, pp. 317- 331. Springer, 2015.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
Mariane Pelletier. On the almost sure asymptotic behaviour of stochastic algorithms. Stochastic processes and their applications, 78(2):217-244, 1998a.
Mariane Pelletier. Weak convergence rates for stochastic approximation with application multiple targets and simulated anncaling. Annals of Applied Probebility, pp. 10-44, 1998b.
Boris Polyak. A new method of stochastic approximation type. Automatika telemekhanika, (7):98-107, 1990.
Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838 855, 1992.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400 407, 1951.
Herbert Robbins and David Siegmund. A convergence theorem for non negative almost supermartingales and some applications. In Optimizing methods in statistics, pp. 233-20-300000 233-257. Elsevier, 1971.
Jerome Sacks, Asymptotic distribution stochastic approximation procedures. The Annals of Mathematical Statisties, 29(2):373 405, 1958.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under strong growth condition. Xrxiv preprint arXiv:1308.631 6370, 2013.
Nicol N Schraudolph, Jin Yu, and Simon Günter. A stochastic quasi-newton method for online convex optimization. In Artificial intelligence and statistics, pp. 136-443. PMLR, 2007.
Shai Shalev-Shwarzz, Yoram Singer, Nathan Srebro, and Andrew Cotter. Pegasos: Primal estimated sub- gradient solver for svm Mathematical programming, 127(1):3-30) 2011.
David F Shanno. Conditioning of quasi-newton methods for function minimization. Mathematics of compu- tation, 24(111):647-656, 1970.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyússi. Lectures on stochastic programming: modeling and theory. STAM, 2014.
Matthew Staib, Sashank Reddi, Satyen Kale, Sanjiv Kumar, and Suvrit. Sra. Escaping saddle points with adaptive gradient methods. In International Conference Machine Learning, pp. 5956 5965. PMLR, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Tijmen Tieleman, Geoffrey Hinton, al. Locture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26 31, 2012.
14

---

Published in Transactions on Machine Learning Research (08/2023)
A. W. van der Vaart. Asymptotic statistics, volume 3 of Cambridge Series in Statistical and Probabilistic Mathemalics. Cambridge University Press, Cambridge, 1998.
J. H. Venter. An extension of the robbins-monro procedure. The Annals of Mathematical Statistics, 38(1): 181-190, 1967.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication--ficienn distributed optimization. In Advances in Newral Information Processing Systems, pp. 1299 1309, 2018.
CZ Wei. Multivariate adaptive stochastic approximation. The Annals of Statistics, 15(3):1115-131 1987.
Ronald Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229 256, 1992.
Mishael Zedek. Continuity and location of zeros of linear combinations of polynomials. Proceedings of the American Mathematical Society, 16(1):78 84, 1965.
Cheng Zhang, Judith Bütepage, Hedvig Kjellström, and Stephan Mandt. Advances in variational inference, IEEE transactions on pattern analysis and machine intelligence, 41(8):2008-2000 2018.
Tong Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In Proceedings of the twenty-fin cortt-firsttt international conference Machine learning, pp. 116, 2004.
Wanrong Zhu, Xi Chen, and Wei Biao Wu. Online covariance matrix estimation in stochastic gradient descent. Journal of the American Statisticnl Association, pp. 1-12, 2021.
15

---

Published in Transactions on Machine Learning Research (08/2023)
Appendix: Asymptotic Analysis of Conditioned Stochastic Gradient Descent
Appendix A contains the mathematical proofs of the main results while Appendix dedicated practical procedure and numerical experiments for illustration purposes. Appendix C gathers some technical auxiliary results and additional propositions.
A Proofs of main results
16
A.1 Proof of the weak convergence (Theorem 2)
16
A.2 Proof of the almost sure convergence (Theorem 3)
26
A.3 Proof of Corollary
B Practical procedure
28
B.1 Construction of the conditioning matrix Ck
................................
28
B.2 Numerical illustration
29
C Auxiliary results
32
C.1 Robbins-Siegmund Theorem
32
C.2 Auxiliary lemmas
32
C.3 Additional propositions
C.4 Auxiliary results on expected smoothness
36
A Proofs of main results
A.1 Proof of the weak convergence (Theorem 2)
For any matrix A E Rdxd, we denote by ||||| = |ul ||ul|2 the operator norm associated to the Euclidian norm and by p(A) the spectral radius of A, i.e., p(A) = the eigenvalues of A. We also introduce Amin = min([Arl...... .....,,,,,. Note that when is symmetric ||||| p(A) and recall that the spectral radius is a (submultiplicative) norm on the real linear space of symmetrie matrices.
Dal where A An are
Structure of the proof.
In virtue of Assumption 5, there exist 8, such that almost surely
sup k20
[||lw+1112 12+ [Fa] -0 lage) 00.
(3)
An important event in the following
A = [10 - 0 S e, |[a]]l C|], |[&|| 2
By assumption, this event has probability going Introduce the difference
4 02 - 0"
and remark that A subjected to the iteration:
An 0, 0*
Ak+1 A 7K+1 CVV(OL) + mh+ 1 CALLCHH
16

---

Published in Transactions on Machine Learning Research (08/2023)
with Wk+1 (F((k)) g(0k: (k+1). We have by assumption that C C almost surely and we define K = limg-to C&H = CH. The proof relies on the introduction of an auxiliary stochastic algorithm which
follows the iteration:
Å 0o lr
Δ = As Yh+t KÅp + Yo4 CR A
k 2 0
The previous algorithm is a linear approximation of the algorithm that defines As the sense that VF(0;) VF(0") H0x 0*) + o00x 0*) H0s 0*) has been linearly expanded around 0*. Writing
A Ax + (Ax AR),
and invoking the Shutsky lemma, the proof will be complete as soon as we obtain that
7kk AS ~ .O
(4)
(A: Σx) = (31
(5)
Denote by VH the positive square root of the real symmetric positive definite matrix H and consider the transformation θ₂ = v which satisfies
Og v HH
*+11 = O₂ - TKt + *K+1 WC
k 2 1,
where K = VHCVH St (R) is a real symmetric positive definite matrix. The sequence (9t) is casier study than Â bocause contrary K, the matrix K CH not symmetric in general unless and H commute. In view of Assumption 3, the eigenvalues of K are real and positive. Denote by Am (resp. AM) the smallest (resp. the largest) eigenvalue of K, i.e.,
Am Amin (K), AM = Amaxx (K).
Because CHH similar to K, they share the same cigenvalues. Since by assumption, the cigenvalues of (CH - (Ta) are positive, we have 20dm [(==1}- For all k 2 1, introduce the real symmetric matrix
A = I K. Observe that all these matrices commute, i.., for any i,j 0, have A,A, Aj For any k n 2 0, denote the matrices product
{ Dn, An.... Act1 if n
11 = Ia if 2 n, = II,,0
Since the matrices Aş commute, we have n IIn. is also real symmetric.
Step Proof of Equation (4).
The random process (Ox)zzo follows the recursion equation
θ₂ A40x-1 + +7e---7-VVHCC HHVCCC-
We have by induction
+, = 11 + Σ
IT 1
k=
and the rescaled process is equal to
I Oo
HHCH- L
n.k
mm
Tn
Tn
k=
iriitial error Y,
sampling error M..
17

---

Published in Transactions on Machine Learning Research (08/2023)
Bound the initial error.
Define Ek=1 7 the partial sum of the learning rates. Since The is symmetrio, we have (TT,, S 0(ll=))@ool2- In view of Lemma 5, since + 0, there exists j 2 1 such that
P(TI.) S p(TI;) expp(Amml -Ty)).
Therefore, the initial error is bounded by
p(Yx)) S p(II,) exp 11ool exp(d,) with =m log(v Vn.)
Using Lemma 6, treat the two cases B < 1 and [ = 1. On the one hand, if B < 1 then we always have dn + -c0. On the other hand, if B = 1, we have d,, (7 7mm) log(n) and the condition 2adm 1 > 0 ensures dn + -c. In both cases we get exp(d,) - 0 and the imitial error vanishes to 0.
Weak convergence of the sampling error. Consider the random process
Mn
1/2 Vn
Σ km
VCC
Note that O2. As and Cg are Fa-measurabl.. As a consequence, M, is a sum of martingale increments and we may rely on the following central limit theorem for martingale arrays.
Theorem 4. (Hall & Heyde, 1980, Corollary 3.1) Let (W (Wna)isesm be triangular array of random vectors such that
BiWa. Fi-1l= =0, for all 1 sisn.
(6)
B BiW,,WWW n.a Fi-1] + V 2 0, in probability,
(7)
( |sst [i-i]] in probability, Σ BillW, n, [
(8)
then, Σ Wny ~ NN V*), as n 00
We start by verifying (7). Let D2 = is given by
E Sa(R). The quadratic variation of Mn.
1 En 1
2 Dxll,
First we can check that 2n is bounded. Using the triangle inequality and since the operator norm is submultiplicative, have
| S mm
D $ mm
DAI 1I = 2m
D&llolll
where we use in the last equality that 11, is real symmetric so ||l,, |I = p(U,,,)) On the event Aç-1, the matrices Ck-1 and T are bounded as ||Ca-1| < 2|[C|| and ||Tx-il| || S 2|[ leading to the following bound for the matrix Dr,
||D||| = IV
< 8||8||||| -UD. < |/ 11
18

---

Published in Transactions on Machine Learning Research (08/2023)
It follows that
E S Un
Σ
The
1=1
In view of Lemma 5, we shall split the summation from k I..... and h: = I,... as
f
7n
TkP
kI,,,k)
Yn
TEP
(IIn,k
In
TEP (In,,)) )²
kmj+1
$ 7n
T&P (IIm,)) +m
7kk
(1 mm
kmj+1
imk+1
On
For the first term an, we have for all I....
(lnn S p(Iing) -
II
11-Amm) S expl->A((Tx - Tg)),
(=++1
which implies since (7k) is decreasing with V1 that
Σ de (I (I,,))² S aryy
Tz))..
Therefore, similarly to the initial error term, get
ary exp(2Am exp(dn) with d, = - 22 Tn - log((n);
and the condition 20.Am. > ensures dn + -o so that 0n goes to and is almost surely bounded by U,.
For the second term bR, we can apply Lemma 3 and need to distinguish between the two cases:
(B = 1) If 7n a/n, since 2adm > we can apply Lemma 3 (p 1, m À Ama, 2, 0, = a2)
and obtain
a²
bn
Ub.
2aAm
(B 1) If Yn = 7/n2, deduce the before because Am > 0.
Finally in both cases, we get
E. UD (Ua + Ub).
(9)
We now derive the limit En We shall use a recursion equation to recover a stochastic approximation scheme. Note that
In En
Σ
Y 2I D.II
(10)
2/2 Dn + An
IT, IT 1 Dr AT
(11)
and recognize
2n =,,DD, + 1
19

---

Published in Transactions on Machine Learning Research (08/2023)
Replacing the symmetric matrix A, I YnK, get (because En is bounded almost surely)
In - D, in-1 (T In Em Yn K) = = + nn-1 En-1 In In 7n K -
Divide by Tn to obtain
On = In Dn + Mn-1
En- 7n mn (n + (k)
7a
and we recognize stochastic approximation scheme
En = En-1 - [Kn-1 1 + En-1 Dn + mn - Ya In- + O(7n-17n + hm-1- - 7nl)
Recall that when 8 < 1 we have
1 + 0, i.e.
nn-1 1a = o(Ti)).
7n
7n-1
Yn
(B=1) If In = a/n we get
1 -
En 1n-1
Km En-iK
-m-1--Da Dn
+ +0
71
a
I
En En-1
K
En + En-1
K
Dn
+O 3).
n
2a
20
(B 1) 1f in Tn a/nz we get
En En-1 -/n KKE-1 + En-ik -Dn] + +(()))
Recall that (= 1 (8=1)/(2a) and define Ke -T, so that in both cases, the recursion equation becomes
Σn = En In KeEn-1 + En-IKf - Dn + o(7)).
We can vectorize this equation. The vectorization of an m matrix (ar.s), denoted vec(A), is the mn 1 column vector obtained by stacking the columns of the matrix A top of one another:
vec(A) [ai,), am..1 1 01,2 2m, 01
am,n
Applying this operator to our stochastic approximation scheme gives
vec(Zin) vec(2n-1) In vec (Keino1 En- Inn1 vec(D + +((m))
Denote by @ the Kronecker product, we have the following properly
vec (KςEn-1 Em-1KF) = (Ia @ Kg + KJ 8 Ia) vec ven(En-1). Define D as the almost sure limit of D i.e.
D lim Dn VHCTCVH.
Introduce o, voc(En)) and Q [I, 8 K2 + K2 @ la). We have almost surely
Un Un-1 7/ (Qun-1 voc( 7n voc D) + o(%)) 1n-1 7n (Qun-1 vec(D)) En
20

---

Published in Transactions on Machine Learning Research (08/2023)
where En - 0 almost surely. This is stochastic approximation scheme with the affine function h(v) Qo vec(D) for u E Rd Let e* be the solution of h(v) 0 which is well defined since Q = [Ia @ K2 + K2 @ Is) is invertible. Indeed, the eigenvalues of Q are μ4 + Maj S i,j I d, where the Pi: i 1,..., are the eigenvalues of K Equivalently, the eigenvalues of Q are of the form (A: () + (A3 () where the A g d are the eigenvalues of K. Because Am > C, we have that Q 0. As consequence
(Un- v²) = (Un-1 - 2²) I/ (h(en-1) h(v²)) + En
(Un-1 - u*) 2n (Un-1 v²) + En
Bn (Vn-1 - e²) + 7mn
with Bn (I1= - Qn By induction, we obtain
-0n (Bn ... (vD u²) + Σ 7h (Bn... ... Bk+1) Eks
Define λq = (Q) > and remark that
Bn ... Butill S II
| = II (1 - 73)2))
j=k+1
j=k+1
It follows that
|10 0²112 S |B,... ... Billl/eo -2"ll2 + Σ
Tkl
ll Bu..... ... BB+1
km
< II (1 7-00)11101000 - 22 + ==1
Σ Th II (1 (1 73 j=k+1
k=
Applying Lemma we obtain that the right-hand side term goes to The left-hand side term goes under the effect of the product by definition of (14)221. We therefore conclude that in + e* almost surely. From easy manipulation involving vee(.) and &, this is equivalent to E,, - E, where E is the solution of the Lyapunov equation
Now we turn our attention to (8). We need show that almost surely,
nh E VHCH Irallla WHC. F +0
We have
Biy, 1
[I HC 1 111121 (Tull HC MaCCa-1wullaee 1/2 Fx-1l
< " 1/2 1/2-//
11,, 11 la 2 FR-1]]
7/
< E 8 (m/ 1/2 IIn, V 2 11 12- Fx-1).
Let (ww sup421 [|[| wk 122 2+0 Fa-I]1AN which almost surely finite by Assumption We get
Eh IT
[T HCC--iw&ll (TullIT... v HCC, ne v0xl22en Fe Au-1
S - (2]1H]111C1) U(w)(T 1/2 1/2 P(I((n)) 2+8
21

---

Published in Transactions on Machine Learning Research (08/2023)
Hence by showing that
(mn 1/2 (I)()),)))) - 0,
we will obtain (8). The previous convergence can be deduced from Lemma 3 with p = 1+ 6/2, m = 22+0 8,
6/2 checking that (2+ 6)adm 1 + 8/2. 6 = 7
Step 2. Proof of Equation (5).
A preliminary step to the derivation of Equation (5) is to obtain that As 0 almost surely. For any 0 and
77 in Rd, we have
||0| 2 = ||>l|2 + 227 Tn 17) 110 n/1²
implying that for all 22 0
B 1| 1|0 2xx+ Ko + [[] CRWM+1 AA 1[FF).
Since (w)) is a martingale increment and because on Ax. p(C)) S 2p(C', we get
B CRu++ 1 11 K ||Fv| + BEII W LA Fb X Ox| 2 + p(C,)² WK| 1A 11 [Fu]
s x 0x12 + 4p(C)² B|IlW++1 1A [12]
Injecting this bound in the previous equality yields
B[|@ < (1 + the1 Ais) - 2 O₂ kO, + 4p(C)) Ell 11 AA
Since, using (3),
22 B[] 1
< sup Supp[[wekt PP k20
2 7k+1
< oc,
N200
1200
we are in position to apply the Robbins Sibbind-Siegmund Theorem and we obtain the almost sure convergence of Ee 7 KO2 and ||Oxlž + Vx.. Because K is positive definite, il gives that, with probability 1, Ekz0 1
+o,, from which, we deduce lim inf, ||0,|2 Therefore one can extract subsequence O₁ such that ||Ox]] + O. Using the above second condition yields Vx2 = and we conclude that A H 1 +.
Define the difference
E = A. Ag.
Since 0 + F(O is continous at f", we can apply a coordinato wise mean value theorem. Indeed, for any 0 E Rd, we have (F) (0, F(O)..... (z)( where for all j = =, d, the partial derivatives functions 0, F: Rdd +R R are Lipschitz continuous. Denote by ((a,F): Rdd + Rd the gradient of the partial derivative O,F, i.e., ((0,F)(0) = (0),... F()). For any 0, 17 E 3(0*,)), there exists E E Rd such that
F(F 0,F ((8 n))
We construct Hessian matrix by rows H({) ((E....... where the j-th row is equal to V(O,F)(E,)
(0P, F(,)...., F(E,))
F()) ((aF(E))
H(S)
02 Fg,F(L PzaF(Ea)
22

---

Published in Transactions on Machine Learning Research (08/2023)
and we can write
- H(E)(O - -1)-
There exists &N (6%)) ())) with -000 10 Ex, 0u] and Ek ((11 (4 with (x 10+ + Ex, 0-] such that
VF(0" + E&) VF(O2) (E(E) VF + E&) = Exk
(12)
(13)
Let 7) > 0 such that 20 (1- 37) > 1. This choice will come clear the end of the reasoning. On the one hand, have C2 -. C. On the other hand, using Lemma 4, the spectrum of C&H is real and positive. Hence, we have the convergence of the eigenvalues of C2 H towards the eigenvalues of K = CH. This follows from the definition of eigenvalues as roots of the characteristic polynomial and the fact that the roots of any polynomial P E C[X] are continuous functions of the coefficients (Zedck, 1965). Consequently, there exists ni (w) such that for all 2 ni (w),
(1 7m Amin(CHHH) (C S + 1))M-
(14)
We can define n2 (w) such that for all k 2 nz(w)
As is realized.
(15)
Since | Tall + 0 as - 20, there is n3(w) and ny(w) such that for all le 2 ng(w)
T Am
I Tall 1+ Am
(16)
and for all 2 ng(w),
I WH- HHE 1-1 1
(17)
Since ihk + 0, there is ny such that for all ns
21/2m
7k+1 S
(18)
(1 + 22
To use the previous local properties, define no (w) = ni (w) V nz(w) V va(()) Vna(w) V ns and introduce the set E, along with its complement Ey, defined by
E, = (w j 2 no (w))
Let > 0 and take j 2 large enough such that P(89) < 8. Invoking the Markov inequality, we have for all
a
PP 1/2 1x > a)
P( - 1/2 E | > E2) P(i 1/2 | a, Ej) |
$ P(y 1/2 Ex > E,) +
1/2 -E E 1 & + 5
$ 7
Because 8 is arbitrary, we only need to show that for any value of j 2
ek E|| = a 1/2).
To prove this fact, we shall recognize stochastic algorithm for the sequence ex
Let k 2 j and assume further that E, is realized. We have, because of (15),
Ex+1 A - - 7h+1 MMF1CCVF(00 + 7 Kāx
23

---

Published in Transactions on Machine Learning Research (08/2023)
Introducing Eg EK, we find
E-1= - ( + 7K+1V
and using (12), it comes that
Ex+1 = Ex - 7R+1 TCHIVHC&VE(0 + + - 7K+1 TK-I THCHHHCH + TK+1 + HKĀ.
TR Ex) 7h+ VH(K C
Using Minkowski inequality, we have
1 I |E 1 + EG)l + In-IVA (
We shall now focus the first term. Still on the set Ej. we have
Ex Yk41 SHHIVHON VFCO - -1)l1
|x 2 (Ex. VFC&VF + E&)) + VVC Ex)1
(19)
We have on the one hand using (13)
(E,, VHCCVFFO +x)) (EA, VHC.H(E))
(É., VHC,HE)) + (Ex, (HCL(H(()) H)Ex))
Due to (14), the first term satisfies
(Éx, VHC.HE,) = (ER, WHC.HHCCHEE HE,)
2 Amin Amx 12212
2 (1 - Am Exl?
The second term satisfies
(Fx, (HCL(H((E) H)Fa) = (Fx, TIN la)
2 2 2.. V Ex)
Using inequality, the submultiplicativity of the norm, (14) and (16), we have
(Éx, VF -1))EE
INTHGNEIINIEEHHHHEVEV Lall 12
< nm |
Finally, it follows that
(Ex, VHOVVF(O +b)) 2 (1 Am) Eull
(20)
On the other hand using (13), (14) and (17),
IHCC + 2 IIVHC&H(E)EEM
= INNGW/HIEFFFNNG
< Amax (FTN
< (1 + 21
(21)
24

---

Published in Transactions on Machine Learning Research (08/2023)
Putting together (19), (20), (21) and using (18) gives that, E,,
|| Ex 7h+ MAoiIHHC&FFOC + Ex)l1
< Ex 27k+1 1 (1 -21) + xkt1 (1 + +1)) 2z3))
- E1 - -31))mm)
By the Minkowski inoquality and the fact that (1 1/2 S x/2, on E,, it holds
| - [[ - 1 (1 )m) ) + 7 (K CxH((E)))aNl
< |x 7k+1 Am) + Mo+1 || H [K CCH((E)))NI)
Hence, we have shown that for any &s J,
| [1s S E (1 - 74+1 (1 - -37))mm + Th 7 It follows that, for any 2 J.
ck+1 S cx(1 1++1(1 - Am) 7k+ B[
with Un (K & Because with probability 1, |R is bounded, apply the Lebesgue dominated convergence theorem to obtain that Ey U + 0. From the Cauchy-Schwarz inequality, we get
E|| S VERV E
On the other hand, we have already shown in (9) that p(Ex) | & UD (U, + Ub). Since A. VH-TO, VH-T Vre + Mx), we have
E S 2(7m/Mm) EIII Mr 12),,
where the last term is the loading term and satisfics
B [21] B[(+(E+)] S dE(p(Ex)]
Therefore, we have
E| 1 nnA
for some A > 0. Consequently, for all k 2 j,
ex+1 S ex (1 7h- 1 - (1- + 7
3/2 A'll HHIE 1/2
The condition 2aAm -n)) ensures that we can apply Lemma with (md > p), m = 1,p = 1/2,1 a(1 - -m we finally get
lim limssp(ee//it 1/2)= 0.
As consequence, E₁ Tk),,, which concludes the proof.
Since TN 1/2 VHA, (O0, E), we have T6 -1/2 5) where E= VH-ISVHH-I Recall that Σ
satisfics the Lyapunov equation
-A
Multiplying on the left and right sides by V we get
where we recognize the following Lyapunov equation
(CH + 5(CH -CCC.
25

---

Published in Transactions on Machine Learning Research (08/2023)
A.2 Proof of the almost sure convergence (Theorem 3)
The idea behind the proof of the almost sure convergence is to apply the Robbins-Siegmunt Theorem (Theorem 6) (which can be found in Appendix C) in combination with the following key deterministic result.
Lemma 1 (Deterministic result). Let F Rd + R be L-smooth function and (0x) random sequence obtoined by the SGD update rule 0,+1 = 0, - -++1 Cige where (7)121 a positive sequence of learning rates and
C--1 3 vela are such that E, 704 = 00. Let w E Q such that the following limits exist:
(i)
7+11++11
oo
(i) Σ
-
< 00
220
21
then (F((((W)) + 0 as 00
Proof. The proof (and in particular the reasoning by contradiction) is inspired from the proof of Proposition in Bertsekas & Tsitsiklis (2000). For ease of notation we omit the w in the proof. Note that condition (i) along with Ee 7t4 = oo implie that lim inf, [[V) = 0. Now, by contradiction, let & > and assume that
sup |[ >
We have that there infinitely many such that ||,F < E/2 and also infinitely many such that [[,)) > E. It follows that there is infinitely many crossings between the sets {t E N || < E/2]
and (t N: [VF(()))] > E). A crossing collection of indexes = (Tu, La +1 1,.., Un -11 1) with L S Uk
(I 0 when Lx Un) such that for all t IR,
(F(0L--1)| < (VF()) S <<< / [/
Define the following partial Cauchy sequence Rs Einry ( V=(00-1)) and note that condition (ii) implies that Rş - as lo co. For all k 2 1,
e/2 < (F(B - [F
< VF (F(L
< L L 112-
where we use that VF I-Lipschitz. Then using the update rule 0, 0 - we have by sum
Un
U Σ
8/2
< L||
Σ
0.
---0, 02-1112 10-112=11 = =bl
7
t=L:
t=
Uh
U
< L||
Σ
MCC11 VF Lll
Σ
7.Cr-1 VF(O--)))l
t=
Ui
7e44 T
Since in the previous equation (VF(0,1))ll > e/2, we get
U, Σ
(6/2)² <
nul n VF(0
[
t=
But since Σ120 (1442)44/[V((B)) is finite and lim; R 0, the previous upper bound goes and implics contradiction.
26

---

Published in Transactions on Machine Learning Research (08/2023)
It remains to show that points (i) and (ii) in Lemma 1 are valid with probability one. Since 0 + F(0) is I-smooth, we have the quadratic bound (see Nesterov (2013))
T || 012.
v8, E RR F S F(O) (VF(O). 8) 2
Using the update rule 0k+1 On 7k+1Ck Ek+1); we get
F(0x+1) & F(O)) + (VF(O)), - 0x) + プ -100++1 0x112
= F(t)) 7*+ (V (0)); Cup(Oks Ex- 1)) + - マ rh+1
- (CC Ex+1
The last term can be upper bounded using the matrix norm and Assumption as [[C=g(O,.Ct11)) Sc+1) < || Ex+1 1 - (
and we have the inequality
F(0x+1) S F(Ox) 7k+1 (VF(On), C,g(Ok,Cx+1)) + (14414e+)))ll(00
Introduce up 7H44 and vk TKPk: we have ESS1 Uk too and Σxअ1 u < too a.s. in virtue of Assumption 9. The random variables F(Ox), Cs are Fe-mcasurable and the gradient estimate is unbiased with respect to Fs. Taking the conditional expectation denoted by Ex leads to
L 2 E& (l1((0..(++1)1)) Es [F(Ok+1)] -F(b)) S + FF(O),, Ex [Cag(Ok, [x+1)])
L 2 Es (00(0):E4+21333
7 VF (p) T C.VF((L)) + 2
On the one hand for the first term, using Assumption
VF(OA) C&VF(()) 2 Amin (C&) VZF()11 2 px+1 [F()))
On the other hand, using Assumption there exist 0 0 02 < such that almost surely vk E N, Es (l - 2C (F(Os) F*) +
Inject these bounds in the previons incquality and substract F(8*) on both sides to have
- Ex [F(0k+1) - F*] S +1+ LLuR 1) F*) - uk+1 (F + (T.2))
Introduce V& ((Ox) F", Wv ux4 VVF ag LLu and by = (L/2) 0², These four random
sequences are non-negative Feamaaauee sequences with Es ak 0o and Σx bb co almost surely. Moreover we have
E [ S (1 + ax) - We + bR.
We can apply Robbins- Sibbbin--Sigmundd Theorem 6 to have
(a) Σ Wx < 00 a.s. A20
(b) Vx 0.2 Vos E [ool < <0. x0.
(c) sup E [V4] < 0o.
k20
Therefore we have the almost sure convergence of the series Σ U IV= which, given that lim sup; Me/pk exists, implies that Σ Su+1l/VF((), is finite. Hence obtain (i) in Lemma 1. We now show that (ii) in Lemma 1 is also valid. The term of interest is sum of martingale increments. The quadratic variation is given by
Σ PB (((0-(44))
S
$ B2
121
27

---

Published in Transactions on Machine Learning Research (08/2023)
Now we use that V& F(0x) F (which was deduced from Robbins- Sibbinn-Siegmund Theorem) to obtain that the previous series converges. Invoking Theorem 2.17 in Hall & Heyde (1980), we obtain (ii) in Lemma 1. Furthermore we can prove that ok+1 02 + 0 almost surely and in L2 Indeed, we have
E [110x+1 1 E Ckg Ex+1l uh (2C (F(O)) - F²) +
In virtue of the almost sure convergence of V& F(2z) F the last term in parenthesis is upper bounded by constant that in view of the convergence of Σ u uk+1' we have the convergence of the series Σ [[0x+1 1x12 We then deduce that E [|0x+1 0x 0x1 0 and Σ | - 0x112 < too almost surely. In particular, 0k+1 Oz 0 in 1,2 and almost surely. The last point follows from the fact. that, for
every 8 > 0,
lim P sup |0x+1 Oull 0ull 20) 100000
lim Σ E [10x+1 k2n
0x112] 0.
42n
A.3 Proof of Corollary 2
First observe that since F coercive, the convergence of (F(O;)) obtained by Robbins-Siegmund theorem implies that the sequence of iterates (04)220 remains in a compact subset K. C Rd. Let ε 0. Since o + S) is continuous, the set D()) = {0 B S) <} is closed and the set K({)) K D(s) is compact. On this set, the map A + VF 2l is stricly positive and there exists 17 >> 0 such that: O K({E) [[))(2) > Te Thus, P(0 E K(e)) < P(IVF((0)l2 > ne) and this last quantity goes to zero which proves the convergence in probability d(O,, S) + 0. Actually the almost sure convergence V + 0 implies the convergence of the distances. Define As(E) = {ww (x(w) E K(E)) and Bx(e) = {w : [VF(O(())]] > ne}. We have (e) C (e( then Un21 Nezn Ae(e) c Un21 Ou2n (x))). Conclude by using the almost sure convergence P(Un21 Ouzn (E)
for each E > If S finite, it in particular a compact set so the distance is atlained for every & 2 0, S) min.es d(Ox, 8) O. Since 0x+1 Oz - 0, the sequence of iterates can only converge to single point of S.
B Practical procedure
For the sake of completeness, the aim of this Section is to derive a feasible procedure that achieves the optimal asymptotic variance described in Corollary 1. First, we present a practical way to compute the conditioning matrix Cj and then we show that the resulting algorithm satisfies the high-level conditions of Theorem This method considered in a numerical illustration along with a novel variant of AdaGrad.
B.1 Construction of the conditioning matrix Ck
Similarly to the unavailability of gradients, one may not have access to values of the Hessian matrix but only stochastic versions of it (sce details in numerical experiments below). As consoquence, we consider the following framework which involves random Hessian matrices. As for gradients, policy (P)) is used at each iteration to produce random Hessians through (0,, (x+1) with Ex+1 P--
Assumption 10 (Unbiased and bounded Hessians). The Hessian generator H x Raxd uniformly bounded around the minimizer and is such that for all 0 Rdd, ((,,.) is measurable and we have: vk 2 0, E (0,, FFFF] ((a())).
An estimate of the Hessian matrix H = V2F(0*) is now introduced as the weighted average
S D Wj (,
with Σ 11 1=0
(22)
The previous estimate has two advantages. First, thanks to averaging, the noise associated to each evaluation H(,,, (/411) will eventually vanished due to the sum of martingale increments. Second, the weights Wj, may help to give more importance most recent iterates. In the idea that fg lies near 0* eventually, might be helpful to reduce the bias when estimating H V²F(())
28

---

Published in Transactions on Machine Learning Research (08/2023)
Proposition 2. Let (#x)k20 be obtained by (22). Suppose that Assumptions 3 and 10 are fulfilled and that 0:: 0r a.s. If suPosisk 4j.A O(/k)) then we have 4 - H F(') a.s.
A natural choice is to take equal weights wj,A = 1k+ However, since the last iterates are more likely to bring more relevant information through their Hessian estimates, we advocate the use of adaptive weights of the form Wi.k & exp(-n|10,_ -88112) with a parameter 1) 2 0 that recovers equal weights with fj = 0. These two weights sequences satisfy the assumption of Proposition 2. They are considered in the numerical illustration of the next Section. While inverting @ would produce a. simple estimate of H such an approach might result in certain instability in practice caused by large jumps towards wrong directions (large eigenvalues) too restrictive visit along other components (vanishing eigenvalues). To overcome this issue, rely on the following filter which clamps the cigenvalues of symmetric matrix. For any symmetric matrix $ and two positive numbers < < b, denote by Sla, bj the associated matrix where all the eigenvalues are clamped to [a, b). Le,, any eigenvalue À of S is modified as X x max (a, min(X.b)
Let (mm) )x21 and (A )x21) be two sequence of positive numbers such that ((m)) I (M for all k 2 1. Define the matrices
(A)) vk E, C2 = =0=(01l(A//))) ( (A
(m)) ((mT))-1))
(28)
Such a definition guarantees two properties. First, C E St (R) with ((m) Ld 3 Ck 3 X Second, in virtue of Proposition t H a.s. so that, soon (A(m))ss k221 and (A )221 go to and tos respectively, the matrix Ck converges almost surely to H-1 (as recommended by Corollary 1). Therefore, obtain feasible procedure leading to asymptotic optimality.
)
Theorem 5 (Asymptotic optimality of the iterates). Let (Ow)s20 be obtained by conditioned SGD (2) with .kk = 1/k; 4x defined by (22), x(m) + 0, 2 (M) - +00 and Ck given by (23). Suppose that Assumptions to 9 are fulfilled and suposisk Wii = O(1kk). We have
Vi(O 6*) ((OHHTTHH"),
k oc.
This algorithm is theoretically asymptotically optimal. However in practice, adaptive gradient methods described in Table 1 have become the workhorse for training deep learning models as they take advantage of low rank-approximations and diagonal scalings. Interestingly, the conditioned matrices involved in these methods are linked to gradient estimates and thus to covariance matrices I'ss (see Assumption 4) rather than the Hessian H. Indeed, since 8* E S, we have for the limiting covariance r Eglg(0 (0)(0*, (0)( T. Consider variant of AdaGrad which accumulates the average gradients G2 ô1 + (1/k) Σ 9:9 and Cs G Averaging allows to anneal the stochastic noise of the gradient estimate. By the law of large numbers, the limiting matrix in our Theorem 2 will be C = (T + 57)-1/2_
B.2 Numerical illustration
Consider the empirical risk minimization framework applied to Generalized Linear Models. Given data matrix X = (5.,s) E Raxd with labels y E R" and a regularization parameter > O, we are interested in solving mingers F(A) with
F(0) = n1 -
((O), A((0) L(x, C(x,0.1)) A0(0).
C.RR--RR is smooth loss function and Ω Rd - R4 is smooth convex regularizer chosen Tikhonov regularization R(0)= 11011/. The gradient and Hessian of each component Si are given for all i = l,..., by
VS((0) = C' + 00 V4 (z, 1. x. Ala.
29

---

Published in Transactions on Machine Learning Research (08/2023)
where -.)) and (.--) are the first and second derivative of [(.,-) with respect to the first argument. Consider two well-known losses, namely least-squares and logistic. These losses are respectively associated to the Ridge regression problem with E 1" and the binary classication task with y E {-1,+13" The regularization parameter is set to the classical value X = 1/n. Denote by o(z) = cxp-- the sigmoid function, we have the following closed-form equations
(Ridge Regression)
(Logistic Regression)
C(x.0.9) C' 6x
[y: x)
C(x 0,
log(1 exp(- y:u0 0))
2, 0
V/
L' (x. =o(x, 0) y/
L" (x: 0,
=
(x; (x3)
= =0(x, 0) - (z. 0))
As stated in Example of Section 2, stochastic versions of both the gradient and the Hessian of the objective F can be easily computed using only a batch B C (I,...,n] of data and - EieB V |B (resp. V F(0)= = Eies ((0)/ for the gradient (resp. Hessian) estimate. Note that these random generators meet Assumptions and 10 as they produce unbiased estimates of the gradient and the Hessian matrix respectively.
For the sake of completeness and illustrative purposes, we compare the performance of classical stochastic gradient descent (sgd) and the conditionmed variant (csgd) presented in Appendix B where the matrix 4y is an averaging of past Hessian estimates as given in Equation (22). We shall compare equal weights Wy.k = (k + 1) and adaptive weights wy.k x exp(-n)l0, - 0% (lll) with v > 0 to give more importance to Hessian estimates associated itcrates which are closod to the current point. Furthermore, for computational reason, we consider a novel adaptive stochastic first-order method which is a variant of Adagrad.
Starting from the null vector 0g (O....,,) 0) Rd, we use optimal learning rate of the form * = a/(k + Ko) (Bottou et al., 2018) and set ((m) = 0, (MM = AVT in the experiments where y, ko and are tuned using a grid search. The means of the optimality ratio + [F(0x) - ((0())/(F(Ob) F(0*)), obtained over 100 independent runs, are presented in Figures below.
Methods in competition. The different methods in the experiments are:
sgd: standard stochastic gradient descent.
sgd_an avg: Polyak-avcraging stochastic gradicnt descent, with a burn-in period (ng = 15 for d === 20 and ni = 30 for = 100) to avoid the poor performance of bad initialization.
csgd(ı) = 0) and csgd(n) > 0): conditioned stochastic gradient descent methods with equal and adaptive weights where the matrix 42 is an averaging of past Hessian estimates as given in Equation (22).
adafullaag:: The variant of Adagrad presented in Appendix B where the gradient matrix G₁ is updated an average G2 81 + (1/k) E 9.9 and C2 CT.//2 instead of the cumulative sum provided in the literature of Adagrad. Note that averaging here allows to anneal the stochastic noise whereas classical versions of Adagrad often rely on true gradients and may use cumulative sums. The parameter å is also tuned using a grid search.
We focus on Ridge regression on simulated data with n = 10, 000 samples in dimensions E (20; 100). Stochastic gradient methods are known to greatly benefit from mini-batch instcad of picking a single random sample when computing the gradient. estimate. We use batch-size equal |B] 16. In Figure 1, we can see that conditioned SGD outperforms standard SGD. Furthermore, adaptive weights (n >> 0) improve the convergence speed of conditioned SGD methods. Interestingly, the novel approach adafull avg offers great performance at a cheap computing cost. Indeed, the update of C++1 relies on the inverse of an average. This operation can be carried out in an efficient way thanks to Woodbury matrix identity.
Real-world data. We now turn our attention to real-world data and consider again the Ridge regression problem on the following datasets: Boston Housing dataset (Harrison Jr & Rubinfeld, 1978) (n 506; 14) and Diabeles dalaset (Dua & Graff, 2017) (n 442; d 10)-
30

---

Published in Transactions on Machine Learning Research (08/2023)
100
sgd
100
sgd
sgd avg
sgd avg
10
csgd(n=0)
10
csgd(n=0)
Optimally Ratio
10-2
csgd(n>0)
adafull avg
Optimaliy Ratio
10
csgd(n>0)
adafull_ave
10-3
10
10
10
10-5
10-5
10-6
10-6
20
40
60
80
100
0
50
100 150 200 250 300 Iterations
Iterations
(a) Ridge 20
(b) Ridge d 100
Figure 1: Optimality ratio k [F(0z) - =(0)))F((0)((((0)) F((*)] for Ridge regression in dimension d E
{20; 100).
Boston Housing dataset (Harrison Jr & Rubinfeld, 1978): This dataset contains information collected by the U.S Census Service concerning housing in the area of Boston Mass. It contains 506 samples in dimension d = 14.
Diabetes dataset (Dua & Graff, 2017): Ten baseline variables, age, sex, body mass index, average blood pressure, and six blood serum measurements were obtained for each of 442 diabeles patients, as well as the response of interest, a quantitative measure of disease progression one year after bascline.
The means of the optimality ratio k - (( F(O")) obtained over 100 independent runs, are presented in Figure 2. Once again, the conditioned SGD methods offer better performance than plain SGD. For these datasets, the conditioning matrix with adaptive weights as given in Equation (22) which presents the best results.
100
sgd
sgd
10
sgd_avy _vg
sgd_avg
csgd(n=0)
csgd(n=0)
Optimaliy Ratio
10-1
adafull_av avg
csgd(m>00)
Optimaliy Ratio
10 1
adafull_avg
csgd(r>0)
10-2
1
10-3
10-3
50
100 150 200
250
300
100
200
300
400
500
Iterations
Iterations
(a) Boston Dataset.
(b) Diabetes Dataset
Figure 2: Optimality ratio + [F(0z) F(8*)]/(F(()) - F(O*)] for Ridge regression on datasets Boston and
Diabetes.
31

---

Published in Transactions on Machine Learning Research (08/2023)
C Auxiliary results
C.1 Bobbins-Siegmunn Theorem
Theorem 6. (Robbins & Siegmund (1971)) Consider a filtration (Fa) and four sequences of random variables(V.)) (200 ( (Wn)n2o (an)nzo and (ba)nz0 that are adapled and non-negative. Assume that almost surely Σx ax < oo and Σx by < 30. Assume moreover that E [Vo] < co and for all n NEN, B[V S (1 +. Wn + bn- Then it holds
(a) Σ We < oc a.s.
(b) V 8.a. Vo0, B < x0.
sup [V,] < 00. (c)
n20
k
C.2 Auxiliary lemmas
Lemma 2. Let (un) (22))21, (Un)221 and (Nn)a21 be non--egatiee sequences such that 7/n - and Σn 7n = t00. Assume that there crists a real number m 2 and j 2 1 such that for all 2 j. un I (1 -nn) un 7n Un. Then it holds that lim sup un lim sunsu Un-
++0
R--00
Proof. Denote 24 max(æ, 0). One has (x + y)+ I x+ + y+. Set E and lim,up, on + Then there exists integer N 2 1 such that (1 -nn S 7n) and on u, i.e., (Va +)+ = 0 for 2 N. We have
for large enough 2 N V.
Un - S (1 mn)(n- v) 7n - v),
and taking the positive part gives
(un u) S (1-7w (1-7))mm-- - o)+ + In u)+ = (1 (n - v)+
Since En Pn = +00, this inequality implies that (u, - +)+ tends to zero, but this is true for all & > 0 so v is arbitrarily close to limsup, un and the result follows.
Lemma 3. Let (7m)21 be non-negative sequence converging to zero, and X, m and p three real numbers with À > 0, 2 1,p 2 0. Consider two non-negative sequences (xn), (En) and an integer j 2 such that
Vn 2 J. In = (1 20n " Fn-1 + pPt Ens
n
ie.,
In II 10
II (1 x²)) Ek. k=++1
(=)
k=j
The following holds if In = n -3 8 (1/2, 1), then for any p
lim sup n 4-00000 T
En
lim sums
mA n
Th 1/nn, then for any p < mX
lim limsup sup En <
lim Sn.
+-+000 7 md p n
In porticular, when + 0 with j = and Fo = 0,
n lim
Th
II (1
Xy)) "x =0,
+00
1+1
(md > 1) lim
7k
II \7)
=
7n
i=++1
32

---

Published in Transactions on Machine Learning Research (08/2023)
Before proving this result, note that if consider Yn2 z/n2 then we write
Zn (1 A7n) In- xn-1 + n ratte, En (1 pm + (n
and apply the result with X = yd and Ên gpt
Proof. We apply Lemma 2 to the sequence Un = z.
We have for all n 2 j,
7a
1
Un
((1
+
nn sm
mm
7n-1
Xmnn)
nn
exp
plog
Yn-1
m log(11 )mma) un-1 InEn.
I'
Define
7n (1 (1- 11-exp) exp
(plog
plog Im-1
+ m log(1 - xrn)) )
An
so we get the recursion equation
Vn 2 un = (1 An un- + An En An
if Th = P E 11/2,1)
then 1/7n- 1/7n-1 + O and the ratio Yn- 7n-1/7o tends to 1 with
7n-1
7n -1) (1 (1+)(1)) 7n-1 ( 7n 7n-1
(---1)
log
(1 + o(1) = 0(7x).
I'm
You
Bosides, mog((1 -Nya) -mdy + o(7)) when and get
An
11 (- + o(%)))),
7n
which implies that Aa converges to md. We conclude with Lemma 2. 7h = 1/n then the ratio 7n11/7 tends to I with
7n-1
= log (1 - + o(7))
log
We still have m log(1 \tr) = -ndnn + o(7a) when + too and therefore
An = Yn [1- - exp - (A)-))) + o(%)))),
which implics X, converges to (md - p) and we conclude in the same way.
Lemma 4. Let A.B E S (R) then the eigenvalues of AB are real and positive with Sp(AB) Dminn (A))min (B); Amax (A) Maxx (B)).
Proof. Denote by /B the unique positive square root of B. The matrix AB is similar to the real symmetric positive definite matrix VBAVB. B. Therefore its eigenvalues are real and positive. Since A + Amax is sub-multiplicative matrix norm on (TR), (AB) & Xmaxx(A (A))x(A which gives Amax ((AB) -1] S
Amax(A (A-) Amaas B- BB1), i.e., Amin (AB)- < (Ani(A) Amii (B)-1, and finally Amiu Amin(A) (A) (B) S Amin (AB).
33

---

Published in Transactions on Machine Learning Research (08/2023)
Lemma 5. Let S S (R) be real symmetric positive definite matrix. Let (rk))22 be positive decreasing sequence. converging to 0 such that Σx +00. Denole by Am the smallest eigenvalue of S. It. holds that there erists 2 1 such that for any & >> j. all the eigenvalues of the real symmetric matrix A = I - are positive and we have
p(lI,) p(....... n 000 0,
Wk > J. p(II,,)) p(An...AAt1)
πI 1m-mm 1mR+1
Proof. For any & E N, the cigenvalues the real symmetric matrix Aş S are given by Sp(At) {(1 (1,) X Sp(S)). Since " + there exists 2 such that nm < for all &o j. Therefore for any k> J, we have Sp(As) R4 and the largest eigenvalue is p(Ac) = 7m Since P is sub-multiplicative norm for real symmetric matrices, we get p(II,.) < II==1 p(Ar) = Ilk= p(Ax) II p(As). The second product can be upper bounded with the convexity of exponential,
II (
II (1 - 7m < k=j+1
exp (-)mm) = exp (-Am - -Ty)) t=0 0. k=
II
k=j+1
Similarly we have for all & > j. pL IT ((A)) IT km)m)-
Lemma 6. Let 7n
an with (1/2, 1] then it holds
(B < 1)
whn
n1
(B =0=1] 1) Σ a llg(n)). 1-8
B 1- 3
k=1
Proof. By series- integral comprison, JT pn+1 8 dt S k s 51 dt.
Theorem 7. (Delyon & Portier, 2021, Theorem (Freeddmn inequality) Let (Xy)ısisn be random vari- ables such that 1[x1 for all 1 j n then, for all 2 0 and v, m > 0,
62/2
P
Xj Σ j=l
24
max
1X S m,
E [
FJ-1] Su < 2exp
(-
1 1m/3
Lemma 7. Let A Raxn be a symmetric positive semi-definite matria. Then for any B E Rmxx, the
matria BAB T E &mmmm is symmetric positive semi-definite.
Proof. First note that -BB)AAB = BAB bocause is symmetric. Then for any vector I R, we have x (BAB )x = (B (T
A(B x) since is positive semi-definite.
Proposition 3. (Khalil, 2002, Theorem 4.6) Let H be a positive definite matria and I a symmetric positive definite malria of same dimension. Then there exists symmetric posilive defirite matris Σ, unique solution of the Lyapunov equation HE + Σ =T, which is given by Σ = S e- dt.
The results remains true the matrix I' is only symmetric positive semi-definite: in that case the matrix Σ is also symmetric positive semi-definite and is the solution the Lyapunov equation.
C.3 Additional propositions
This section gathers the proofs of Proposition about the optimal choice for the conditioning matrix and of Proposition 2 about the almost sure convergence of the conditioning matrices.
Proposition The choice C* H11 optimal in the sense that Ec. 1 Ec, VC E Ch. Moreover, Σc- = -1
34

---

Published in Transactions on Machine Learning Research (08/2023)
Proof. Define Ac = Ec - -H and check that Ac satisfies
(CH Ac + Ac (CH Ia/2) - -CC-
Because is symmetric positive semi-definite, we have using Lemma 7 that the term on the right side is symmetric positive semi-definite Therefore, in view of Proposition 3, we get that Ac symmetric positive semi-definite Ac which implies Ee = -----1--- for all C E Cn. The equality reached for C H-1 with Ac Ec. H-
Proposition 2. Let (Pn)x20 be oblained by (22). Suppose that Assumptions and 10 are fulfilled and that 0% 8t almost surely. If suposiss O(1kk) then we have 4x H. F(0) almost surely.
Proof. We the docomposition
Φ2 - H = Σ Wi. (V²F(0,)) H) + Σ wAA (0,) - -22 3=0
==
The continuity of V 8* and the fact that 8, rr a.s. implic that ||(2 H - a.s. Since suPoSisA WijA = (1//k, there exists a 0 such that
Σ WiS (V2F(0,)- H) S
V2F(0,) H||
f=0
which goes to 0 in virtue of Cesaro's Lemma, therefore lim Ej 2-=00 j F(2) H) =0. The second
term is a sum of martingale increments and shall be treated with Freedman inequality and Borel-Cantell Lemma. Introduce the martingale increments
0A S S k X5+1A= -
For fixed k we have X,+1, the Hessian generator unbiased, we have for all coordinates
(i.))
where we remove the index io for the sake of clarity. Because
Isi.sd
E
= for all 0 Siisk
By definition of the Hessian generator and using that (V=F(0,)) is bounded, get that (11) v2F(0))|| O(1) for all j 0. For any b > 0, consider the following event.
(1.0) 541 =bj.
2
sup max (I: 1) k20J=0,...
and note that since wij& O(/k)) we have P(Ln) + 1 b + xc. On this event, the martingale increments and the variance term are bounded as
(R.)) a Æj+1 S b(k+
Σ
Fr < (k
max j
Using Freedman incquality (Theorem 7): we have for all coordinates i, 1....,d,
(2 + 26(6 + x)
P
Σ
(1.0 J+1
> E, Sb
< 2xxp
The last term the general term of a convergent series. Apply Borel-Cantelli Lemma (Borel, 1909) to finally get almost surely Q2 that limg- Σ (i.))
0. Since b > 0 is arbitrary and P(Q,) when
35

---

Published in Transactions on Machine Learning Research (08/2023)
(1.1) b- oo, we have almost surely limg- Z==0 2f j+1 0. This is true for all the coordinates of the martingale
increments and therefore
Σ Wjsk (H(0), ( V2F(0))) a.s. 80000
lim
C.4 Auxiliary results expected smoothness
The following Lemma gives sufficient conditions to meet the weak growth condition on the stochastic noise as stated in Assumption 8.
Lemma Suppose that for all k 2 1,0 E RR,F(O (x) Fx-1] with &K ~ Pk-1- Assume that for all Ek- Pk-1, the function B +> f(0,Ex) L-smooth almost surely and there evists m E R such that for all Rdd 5(00 2 m. Then gradient eslimate is given by g(0, E) vS(0,)) and the growth condition of Assumplion is satisfied with o² =2 m) and
4O YE
s (F(( - F*) + 0
Proof. For all Ex Pk-1, Lipschitz continuity of the gradient 0 + ff(, implics (scc Nesterov (2013))
fx) & f(0, Ex) + (Vf(0,E)) y - 0) + (L/2) - -0112-
Plug y = - (1/T///V// and use the lower bound f'y. {x) 2 m to obtain
2T. (1(0,E)) < ((0,Es) f(y, S 5(0, Ex) - m
which gives,
19(0, Ex)11 < 2L (f(8 f(0 (x)) + 2L (f(0", m)
and conclude by taking the conditional expectation with respect to FR-1-
The next Lemma links our weak growth condition with the notion of expected smoothness as introduced Gower et al. (2019). In particular, this notion can be extended to our general context where the sampling distribution can evolve through the stochastic algorithm.
Lemma 9. (Expected smoothness) Assume that with probabilily one,
E 119(0, Ex) g(00, [() < oo and sup (1((0==)))BB)=1] < oc.
sup sup 1 x//="
F(0)= - F
121
Then there erist 0 5 C, o² < 0 such that
V DORR
< (F( E [11000,6@)1]]]=--]
202.
Proof. For all 0 Rd and all & E N, we have
(lg(0, & llg(0, {x) g00" {x) + Ex) < 211g Ex) - g(0" Ex) + 2l 1x)
Using the expected smoothness, with probability one, there exists 0 S L < ca such that E [1lg(0, Ex) g 11) < -FF())FF))
Since the noise at optimal point is almost surely finite there exists S o² < oo such that
13 s0²
which allows to conclude by taking the conditional expectation.
36


Reviews:
[{"review_id": "tRw4nzOVNL", "reviewer": "Reviewer_bN52", "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": "### Strength:\n\n- Overall the paper is well-written with clear presentation. The results are corroborated with numerical experiments.\n\n- The analysis does not impose additional assumptions on the convergence rate of the preconditioners $\\\\{C_k\\\\}_\\{k\\ge0\\}$, and shows that the algorithm would behave in the same way as an oracle version where $\\lim_\\{k\\to\\infty\\}C_k$ is used instead. This technical novelty allows one to apply the analysis in a more general way and can be of independent interest.\n\n### Weakness:\n\n- In section 3.4, the authors provide some additional convergence results that are helpful in applying the main results, which require the convergence of the iterates in the first place. The discussion is limited to the stationary points, while the main results also require certain conditions involving the final Hessian matrix $H$. Since a number of existing literature has investigated how SGD algorithms escape from saddle points, it would be helpful if the authors can provide a more detailed discussion on dealing with $H$ in a non-convex setting.\n\n- Assumption 9 introduces a set of extended Robbins-Monro conditions on the preconditioners $\\\\{C_k\\\\}_\\{k\\\\ge0\\}$, and essentially requires $\\\\lim_\\{k\\\\to\\\\infty\\} C_k = 0$ (if I am not mistaken), which is not compatible with the conditions in Theorem 2. If this is the case, please make it clear in the discussion.\n\n========\n\nThe authors' response has addressed my concerns and I recommend for accept.", "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 work investigates the asymptotic behavior of a general class of preconditioned stochastic gradient descent methods. Under certain technical conditions, the authors characterize the asymptotic normality of the iterates under certain technical conditions, and show that using the inverse of Hessian as the conditioner leads to optimal variance. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Strengths And Weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tMqNY13TQU", "reviewer": "Reviewer_3EKA", "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": "General remarks: The paper is cleanly written and reads well -- with interesting content. I also found the part related to the review and summary of existing methods well written. I found the overall contributions slightly limited.", "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 an asymptotic analysis of SGD, in terms of central limit theorems, for the case where the SGD is preconditioned. The result is novel.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am not sure about the paper's contributions' significance, I have the following questions/suggestions and open to discussion:\n\n1- I think the authors can make it clearer in their case policy P_k has an explicit link to sampling patterns of data in Example 1. More generally, the \"policy\" seems to be sampling distribution that computes the stochastic gradients. It is a bit of a different terminology -- but would be good to clarify this.\n\n2- For A2-A5: I would appreciate some detailed explanation for the intuition in the assumptions, optimally in the form of remarks.\n\nFor example, A2 is standard learning rate decay but known to fail to work in practice.\n\nWhy A3 is important and what does it \"intuitively\" bring?\n\nSame for A5, a thorough explanation of the assumption would be useful. This is assuming that the MSE (more correctly 2+\\delta power of the error in the gradient) of the stochastic gradients are bounded \"around the stationary point\". Is it a mild assumption or a strong assumption? How does it compare to usual bounded variance (or MSE) assumption in SGD?\n\nAlso a discussion about how these relates to standard assumptions for SGD (namely, \\mu-strong convexity + L-smooth gradients) should be discussed. Are these weaker or stronger?\n\n3- I found sketch of the proof a bit unhelpful -- not clarifying a lot the general idea. Also it would be good to cite here the exact section in Appendix where the proof can be found.\n\n4- About Prop. 1 and Corollary 1: I think the results here could be made a bit more specific given the setting. While the optimal choice of the preconditioning matrix is the Hessian, this is often approximated in practice. What kind of approximation errors can be accounted for theory in this paper to hold? Is there a structure to this error? If the preconditioned matrix is the perturbed version (an approximation) of the Hessian, can theory say anything approximate here? I think this would be useful direction to enhance this paper and demonstrate the utility of the introduced result.\n\n5- The last part of the paper seems to proceed under stronger assumptions (A6 onwards) to prove almost sure convergence. As I said above, it is also important to contrast these with the A2-A5 on what/how they differ and compare.", "broader_impact_concerns": "theory work, no broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "D3yWarvpAI", "reviewer": "Reviewer_bWM3", "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": "Strength: All the prooves are clear to understand and easy to follow. \n\nWeakness: The practical implication of the provided analysis for the machine learning community is not discussed enough. The numerical evaluations are just for the convex settings. Also, assumption 5 may not hold for all the stationary points of a non-convex objective function. ", "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 considers the conditioned stochastic gradient descent and provides the weak convergence for this method for the non-convex objective functions. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please bring up the practical implication of this analysis to the main part of the paper and add more examples about where CSGD can be utilized for ML models along side showing that the assumptions of the paper hold for those models. ", "broader_impact_concerns": "No broader impact concerns. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers have recommended acceptance, and the authors have already updated their paper addressing the points made by the reviewers.
Decision: Accept (poster)