Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation
Authors: Sobihan Surendran
Adeline Fermanian
Antoine Godichon-Baggioni
Sylvain Le Corff
Venue: NeurIPS 2024 poster (2024)
Keywords: Stochastic Optimization
Adaptive Stochastic Approximation
Monte Carlo Methods
Variational Autoenconders
Primary area: optimization

Abstract: Stochastic Gradient Descent (SGD) with adaptive steps is widely used to train deep neural networks and generative models. Most theoretical results assume that it is possible to obtain unbiased gradient estimators, which is not the case in several recent deep learning and reinforcement learning applications that use Monte Carlo methods.
This paper provides a comprehensive non-asymptotic analysis of SGD with biased gradients and adaptive steps for non-convex smooth functions. Our study incorporates time-dependent bias and emphasizes the importance of controlling the bias of the gradient estimator. 
In particular, we establish that Adagrad, RMSProp, and AMSGRAD, an exponential moving average variant of Adam, with biased gradients, converge to critical points for smooth non-convex functions at a rate similar to existing results in the literature for the unbiased case. Finally, we provide experimental results using Variational Autoenconders (VAE) and applications to several learning frameworks that illustrate our convergence results and show how the effect of bias can be reduced by appropriate hyperparameter tuning.

Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation
Sobihan Surendran 1.2 Adeline Fermanian', Antoine Godichon-Baggioni Sylvain Le Corff' Sorbonne Université, CNRS, Laboratoire de Probabilités, Statistique et Modélisation, Paris, France LLOPF, Califrais' Machine Learning Lab, Paris, France
Abstract
Stochastic Gradient Descent (SGD) with adaptive steps is widely used train deep neural networks and generative models. Most theoretical results assume that it is possible to obtain unbiased gradient estimators, which is not the case in several recent deep learning and reinforcement learning applications that use Monte Carlo methods. This paper provides comprehensive non-asymptotic analysis of SGD with biased gradients and adaptive steps for non non-convex smooth functions. Our study incorporates time-dependent bias and emphasizes the importance of control- ling the bias of the gradient estimator. In particular, we establish that Adagrad, RMSProp, and AMSGRAD, an exponential moving average variant of Adam, with biased gradients, converge to critical points for smooth non-convex functions at a rate similar to existing results in the literature for the unbiased case. Finally, we provide experimental results using Variational Autoenconders (VAE) and appli- cations to several learning frameworks that illustrate our convergence results and show how the effect of bias can be reduced by appropriate hyperparameter tuning.
Introduction
Stochastic Gradient Descent (SGD) algorithms standard methods to train statistical models based on deep architectures. Consider a general optimization problem:
0 argmin V(0),
DER
where V is the objective function. Then, Gradient Descent methods produce sequence of parameter estimates follows: 0g E ded and for all N,
0 O, 7n+1 VV
where VV denotes the gradient of and for all n 2 1, 7h > is the learning rate. In many cases, it is not possible to compute the exact gradient of the objective function, hence the introduction of vanilla Stochastic Gradient Descent, defined for all n E N by:
0n+1 On 7++1 VV(e.)
where (V,),, is an estimator of V (e.). For example, in deep learning, stochasticity emerges with the of mini-batchar While these algorithms have been extensively studied, both theoretically and practically, see, e.g., 10), many questions remain open. In particular, most results are based on the case where the estimator VV is unbiased. Although this assumption is valid in the case of vanilla SGD, breaks down in many common applications. For example, zeroth-order methods used
"Corresponding author: sobihan. www..errrrraaaartooommmmeesseeee
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

to optimize black- box functions [6]] in generative adversarial networks [38 16 have access only to noisy biased realizations of the objective functions.
Furthermore, in reinforcement learning algorithms such as Q-learning 442 policy gradient [5] and temporal difference learning 8 122 18, gradient estimators are often obtained using Markov chain
with state-dependent transition probability. These estimators are then biased [69 23 Other examples
of biased gradients can be found the field of generative modeling with Markov Chain Monte Carlo (MCMC) and Sequential Monte Carlo (SMC) 34 [3]. In particular, the Importance Weighted Autoencoder (IWAE) proposed by [12, which is an extension of the standard Variational Autoencoder
(VAE) [4]], yields biased estimators. Finally, this is also the case in Bilevel Optimization 43 36
and Conditional Stochastic Optimization [40 (3].
Moreover, in practical applications, vanilla SGD shows difficulties in calibrating the step sequences. Therefore, modern variants of SGI) employ adaptive steps that past stochastic gradients or Hessians to avoid saddle points and deal with ill-conditioned problems. The idea of adaptive steps was first proposed in the online learning literature by and later adopted in stochastic optimization, with the Adagrad algorithm of (27].
In this paper, we give non-asymptotic convergence guarantees for modern variants of SGD where both the estimators are biased and the steps are adaptive. To our knowledge, existing results consider either
adaptive steps but unbiased estimators [27 77 67 74 19), or biased estimators with -dn-adee steps 770
21.
More precisely, our contributions are summarized as follows.
We provide convergence guarantees for the Biased Adaptive Stochastic Approximation framework, under weak assumptions on the bias. To the best of our knowledge, these are the first convergence results to incorporate adaptive steps in biased Stochastic Approximation.
In particular, we establish that Adagrad, RMSProp. and AMSGRAD, an exponential moving average variant of Adam, with a biased gradient, converge to a critical point for non-convex smooth functions with convergence rate of (log n/ /n + b,), where b, is related to the bias at iteration n. However, we achieve an improved linear convergence rate with the Polyak-Lojasiewicz (PL) condition.
Finally, we show how our theoretical results apply to several applications with biased gradi- ents. In particular, show that our hypotheses hold for Stochastic Bilevel Optimization and Conditional Stochastic Optimization, but also for self-Normalized Importance Sampling estimators Coordinate Sampling. We also propose first non-asymptotic bound on the bias of IWAE, which allows us to illustrate through several experiments the effect of bias the convergence of the optimization, and to show how this effect can be reduced by an appropriate choice of hyperparameters.
Organization of the paper. In Section 2 we introduce the setting of the paper and relevant related works. In Section we present the Adaptive Stochastic Approximation framework and the main assumptions. In Section 4 we present our principal results, i.e., convergence rates for the risk when the PL condition assumed, and on the gradient norm without this hypothesis. We illustrate our All proofs are postponed to the appendix.
results in Section
2 Setting and Related Works
Stochastic Approximation. Stochastic Approximation (SA) methods go far beyond SGD. They consist of sequential algorithms designed to find the zeros a function when only noisy observations available. Indeed, (68] introduced the Stochastic Approximation algorithm iterative recursive algorithm to solve the following integration equation:
h(()) = E,, [Ho(X)) = Ho(r))(z)dz== =0
where h is the mean field function, X is random variable taking values in a measurable space (X, X²), and E, the expectation under the distribution æ. this context, Hg can be any arbitrary function. If Hg (X) ) is an unbiased estimator of the gradient of the objective function, then h(0) VV As

---

result, the minimization problem ( is then equivalent to solving problem 22 and we can note that SGD is specific instance of SA. SA methods are then defined as follows:
pn+1 = 0n - Ho, (Xn+1)
where the term Ho., (x++1) is the n-th stochastic update, also known as the drift term, and is a potentially biased estimator of VV It depends random variable X which takes its values in (X, X). In machine learning, V typically represents the theoretical risk, 0 the model parameters, and X 1+1 the data.
Adaptive Stochastic Gradient Descent. SGD can be traced back to [68], and its averaged counterpart was proposed by (66). The non-asymptotic analysis of SGD in both convex and strong convex cases can be found [59]. [32] prove the convergence of a random iterate of SGD for nonconvex smooth functions, which was already suggested by the results of [9]. They show that SGD with constant or decreasing stepsize "/n = 1/v converges to a stationary point a non-convex smooth function V at rate of ((1/vn) where is the number of iterations.
Most adaptive first-order methods, such as Adam 47 Adadelta 78), RMSProp 72]. and NADA 25] are based on the blueprint provided by the Adagrad family of algorithms. The first known work on adaptive steps for non-convex stochastic optimization, in the asymptotic case, was presented by (50] 774 proved that Adagrad converges to critical point for non-convex objectives at rate of Oloo / /n) when using a scalar adaptive step. addition,
[79] extended this proof to multidimensional settings. More recently, [19] focused the convergence rates for Adagrad and Adam. Furthermore, several modified versions Adam have been proposed, such as AMSGRAD
77 and YOGI (67).
Biased Stochastic Approximation. The asymptotic results of Biased SA have been studied by (7) The non-asymptotic analysis can be found in the reinforcement learning literature, especially in the context of temporal difference (TD) learning, as explored by 8 52 18]. The case of non-convex smooth functions has been studied by [44]. The authors establish convergence results for the mean field function at a rate of Ollog n1/ n1/nn + b), where b corresponds to the bias and n to the number of iterations. For strongly convex functions, the convergence of SGD with biased gradients can be found in [2], specifically addressing the case of Martingale noise with a constant step size.
46 21 introduce a novel assumption, known as "Expected Smoothness", which is the weakest assumption compared the existing literature on biased SGD that we extend to cover the adap- tive case. The authors provide convergence results in the case of non-convex smooth functions. Convergence results with assumptions on the control of bias and MSE can be found in [56 22).
Applications of biased gradients can be found in Bilevel Optimization 43 36 41 and Conditional
Stochastic Optimization [40] 39) Moreover, biased gradients are also used in various other applica-
tions 38 54 6 56). Finally, 3 studied convergence results of biased gradients with Adagrad in the
Markov chain case, focusing on the norm of the gradient the Moreau envelope while assuming boundedness of the objective function.
Our analysis provides non-asymptotic results in a more general setting, for a wide variety of objective functions and adaptive algorithms and treating both the Martingale and Markov chain cases.
3 Adaptive Stochastic Approximation
3.1 Framework
Consider the optimization problem 11) where the objective function V is assumed to be differentiable. In this paper, focus on the following SA algorithm with adaptive steps: Og IRd and for all N,
0x+1 8n He, (Xn+1)
(3)
where 1n+1 > 0 and A, is sequence of symmetric and positive definite matrices. In a context of biased gradient estimates, choosing
A,
5Ta +
12 (
Σ Ho, (Xx+1) (o, (X++1)))
1/2
can be assimilated to the full Adagrad algorithm inverse becomes expensive in high dimensions, so in practice, Adagrad is often used with diagonal
27 However, computing the square root of the
3

---

matrices. This approach has been shown to be particularly effective in sparse optimization settings. Denoting by (A) the matrix formed with the diagonal terms of and setting all other terms Adagrad with diagonal matrices is defined in our context as:
(amn+):00m)))) An = b + (oa -1/2 )
where
Hn (X11111 00:n)
He, (o (Xx+1)"
In RMSProp 72).
Hxx(1nnt3 0o:n) in
is an exponential moving average of the past squared
gradients, defined by:
Σ k=0
p"p - Ho, (Xa+ (X++1)",
where is the moving average parameter. Furthermore, when An is a recursive estimate of the inverse Hessian, it corresponds the Stochastic Newton algorithm
[1]
3.2 Assumptions
Consider the following assumptions.
H1 There exists a constant μ > such that for all IRd,
2μ (V V (0)) IVV(0))
condition, which is weaker than strong convexity and remains satisfied even when the function is non-convex. It ensures uniqueness of the minimizer 0*. The PL condition has been extensively studied theoretically [45] and has been verified empirically in many applications, such as over-parameterizer deep networks (26 and Linear Quadratic Regulator models (2
HI corresponds the
H2 The objective function V is L-smooth. For all (0, E Rd x R. (V - VV (0') < L ||0 - 0'1
This assumption is crucial to obtain our convergence rate and is very common see, e.g., [59 Under this assumption, for all (8, 6') Rdd R.
L 100 0¹11
V (0) < V (0) (VV (0), - 0¹)
(5)
H3 (i) Biased Gradients: There exist two non-increasing positive sequences (An)n21 and (ra)n21 such that for all N,
E (VV (0.) A, (Xn+1))) Xn+1
(IV - - -r+t1)
(ii) Expected Smoothness: there exists a non-increasing non-negative sequence (0 and positive constants ã, ã2 such that for all N,
E [1)
< o + ā (V ( - V(0))
In this assumption, Fa+1 represents an additive bias term, generally of the order of the square of the bias. and An+1 may depend on the minimum eigenvalue of A,, [2]] Theorem 2]. has been demonstrated that this assumption is weaker than the alternatives used in the literature on biased SGD. We have extended these assumptions to the adaptive case. It is important note that the first point of HE depends on the application (objective function V') and on the adaptive algorithm (matrix A,) that we want to use. The purpose of this assumption to provide more general framework that covers all possible applications and adaptive algorithms. In the biased SGD setting, if the bias
term [B[ (Xn+1) Fx] (e.)) is bounded by b,41. we can easily verify the first point of

---

H by considering Xx+1 1/2 and Tn+1 = bn n+1- We show in Section 4.3 that this assumption also verified algorithms such as Adagrad and RMSProp. The second point of is weaker assumption compared to bounding the variance of the noise term. Applications where we can verify these assumptions are discussed in Appendix D
We finally consider an additional assumption on An. Let ||A|| be the spectral norm of a matrix A.
H4 There exists (Bn)n21 such that for all N, || == Amax (A,) S Bu+1
In our setting, since A is assumed to symmetrie matrix, the spectral norm equal to the largest eigenvalue. H4 plays crucial role, as the estimates may diverge when this assumption is not satisfied.
Given a sequence (8n)n21, one way to ensure that H4 is satisfied is to replace the random matrices
A, with
Ån min [A Bn+1) An
(6)
|Aa]]
is then clear that ||An|| S Bn+1. Furthermore, in most cases, especially for Adagrad, RMSProp and Stochastic Newton, control of Amax (An) in H4 satisfied. For example, in Adagrad and RMSProp,
in 4
we have Amax (Ap) S 8-1/2
4
Convergence Results
4.1 Convergence under the PL. condition
In this section, we study the convergence rate of SGD with biased gradients and adaptive steps under the PL condition. We give below a simplified version of the bound we obtain on the risk and refer to Theorem A.2 in the appendix for a formal statement with explicit constants.
Theorem 4.1. Assume that H7 H4 hold. Let On E RRd be the n-th iterate of the recursion
and '/ = C,n 7, Bn = CC An Can with C2 > O, Cp > O, and Cs > Assume that
7, X 2 0 and 7 X Then,
EV (0..) - [] O +24 + TT))
The rate obtained is classical and shows the tradeoff between a term coming from the adaptive steps (with dependence 7, B. >) and a term r, which depends on the control of the bias. To minimize the right hand-side 7 we would like to have = = O. For example, is verified in the case of Adagrad and RMSProp if the gradients are bounded, as will be discussed later.
We stress that Theorem 4.1 applies to any adaptive algorithm of the form (3), with the only assumption being H4 Without any information on these eigenvalues, the choice that B, x n and An x n allows us to remain very general, which can even be seen as worst-case scenario. Finally, note that non-adaptive SGD is a particular case of Theorem 4.1. Thus, our theorem gives new results also in the non-adaptive case with generic step sizes and biased gradients with decreasing bias.
4.2 Convergence without the PL condition
In the non-convex smooth case, theoretical results are generally based on a randomized version of SA, as described in [60 32 Instead of considering the final parameter On. we introduce random variable R, which takes its values in [1..... n). and the quantity of interest becomes On- Note that this procedure is technical tool, in practical applications we use classical SA. The following theorem provides a bound in expectation on the gradient of the objective function V. which is the best we can have given that no assumption is made about the existence of global minimum of V.
Theorem 4.2, Assume that H2 A (0z L,R4 For any n Z
H4 hold. Assume also that for all k e N, we have Yk+1 S Tet R {O....,n) be discrete random variable such that:
W1+17++12441
P(R k) ΣØ 111+1754 Aj+1
where Wk+1 = [ + و25,) - with 6, = 13/33//2. Then,
Va + + + 022
E VVV (0n)][²] 5 L W5+17]+1
5

---

where
01,
wk+1 Wx+17h+12e4777tt 22,n
1 and V = E[V(()) - v(0)))
km0
If 02 = O. Theorem 4.2 recovers the asymptotic convergence rate obtained by 44 with respect to the hyperparameters 7, j5, and X, and to the bias. We observe that if y S X + 233 the condition (7k k21 can be met simply by tuning Cg- In particular, A, = Ia. the requirement on the step sizes can be expressed 7 S L))
We give below the convergence rates obtained from Theorem 4.2 under the same assumptions on Y Sn. and An as in Theorem[4.]
Corollary 4.3. Assume that H2 H4 hold. Let In
C,n 7, An Can An = Can with
C. O, Co > O, and Cx > O. Assume that 7: 1,3,2 2,,22 and 7 + < 1. Then, if 02 we have:
O (n 7+2++8 + bn)
if 3 < 1/2.
E VV (OR))
0 n bm)
if
1/2,
intt>-llog bm)
if 1/2.
where the bias term bn can be constant or decreasing. In the latter case, writing In = C,n we have:
0 (n
i i 1, -
b
(1)
(n logn)
In practice, the value of r is known in advance while the other parameters can be tuned achieve the optimal rate of convergence. In any scenario, we can never achieve a bound of O(1 /n n + bu). reach is Olog n/ /n n bn)) when
and the best rate all eigenvalues of A, must be bounded from both below and above. Note that we could also have obtained such a rate by taking A, = n 1/2 and Sn = 1/2 while keeping "/n constant. However, the assumption that Bn = n 1/22 is too strong (fast decay of the eigenvalues A.), hence our choice of 3n = Cznº. Finally, for decreasing bias, if 2 1/2, the bias term contributes the convergence rate of the algorithm. Otherwise, the other term is the leading term of the upper bound. In both cases, the best achievable bound is Ollog n/ vTi if 1/2.
1/2, = 0, and X = 0. In this case,
Bounded Gradient Case. Now, we analyze the convergence of Randomized Adaptive Stochastic Approximation when the stochastic updates are bounded, as given by the following assumption.
H5 There exists M 2 0 such that for all N. Ho, (X.+1) < M.
Boundedness of the stochastic gradient of the objective function a classical assumption in adaptive stochastic optimization [67] 74
19 73..
Corollary 4.4. Assume that H2
Con An CCn with C. > 0, Cs > 0, and Cs > O. Assume that 3, X 2 O and 7 + X < 1. For any n 2 1, let
HS
hold. Let "in C,n=7,8,
R E (0, - n be uniformly distributed random variable. Then,
V a',n La2a
E (OR)))
Vn
where on,n Σn k= Th+1 Me+1A4+1T441 22 =
Ek- k=
3 and V (V) V(O*)).
Importantly, in Corollary 4.4 there are no assumptions on the step sizes, and we obtain a better bound than in Theorem 4.2
4.3 Application to Adagrad and RMSProp
We give a convergence analysis of Adagrad and RMSProp with biased gradient estimator. First, note that, under HS for all eigenvalues X of An, the adaptive matrix in Adagrad or RMSProp. it holds
that (M² 8) 172 X 8-2/ i.c., H4 is satisfied with À 0 and / = 0.

---

Corollary 4.5. Assume that H2 and HS hold. Let = =nn and A, denote the adaptive matrix in Adagrad or RMSProp. For any 2 let R {O....,n] n.) be uniformly distributed random variable. Suppose that for any n 2 1, there exist positive constants and Ca such that:
|| (Hg, (Xn+1) VV (0n)ll S Can
(8)
Then,
E IVV (OR)ll) = log n vn
+ bn
where the bias bn is explicidly given Appendix A..5
In the case of an unbiased gradient, we obtain the same bound of (logn// vn) in 74 79 19
under the same assumptions. If the bias is of the order O(n O(n-1/4), the algorithm achieves the same convergence rate as in the case of an unbiased gradient.
4.4 AMSGRAD with Biased Gradients
Finally, we show the convergence of AMS- GRAD [67] with a biased gradient esti- mator. At each iteration, AMSGRAD uses an exponential moving average of past gradients instead of the current gradi- ent as in Equation (3), which is detailed in Algorithm [ The key difference be- tween Adam and AMSGRAD lies in their handling of the second moment estimate. Specifically, AMSGRAD uses the updated term V/= = max - Diag(V<)) instead of directly using Ve, with the maximum taken coordinate-wiss wise. This approach is erucial, it ensures that the eigenvalues of A, decrease at each iteration. The fol- lowing theorem provides a bound in pectation on the gradient of the objective
Algorithm 1 AMSGRAD with Biased Gradients
Input: Initial point 6., maximum number of itera-
tions n, step sizes f7A Fx21, momentum parameters
Pl, P2 E [0, 1) and regularization parameter 5 2 0.
Set mg 0, Vo 0 and V. 0
for k = 0 to n do
Compute the stochastic update Ho, (X++1)
mR = Pım + (1 pi) Ho. (Xx+1)
1 VR = DoVi-1+(11 p2) Ho, (Xx+1) (Xx+1)
V2 max Diag (vw)
A₁ [ôld + V/] 11/2
0k+1 B₁ 7 Agme
end for Output: (0*)osksn
function V using randomized iterations with AMSGRAD.
Theorem 4.6. Assume that H2
H3 (i), and H5 hold. Let Yn c.n 1/2 A, denote the adaptive
matrix of AMSGRAD in Algorithm 7 and p1, E 1). For any 2 1, let R E (0...., n be uniformly distributed random variable. Then,
E VVV (0m))= = logn nn
bm
where b, corresponds to the bias which comes from Iu in H3 i). Choosing In C,n we get:
O T)))
ifr 1/2, ifr > 1/2,
bn
O n 1/2)
0 n 11/2
1/2
logn)
ifr = 1/2.
If the bias is of the order O(n O(n-1/4), we achieve convergence rate of Ollog vT). which is the same as that of an unbiased gradient [19] and similar to that of Adagrad and RMSProp. It is worth noting that our results are also applicable to SGD momentum by taking An Ia in Algorithm [
4.5 Convergence Results in i.i.d. and Markov Chain cases
For illustrative purposes, in this subsection we give the form of the bias of the gradient estimator, denoted by ba in two simple scenarios, i.e., when (Xn,n E N) is either an i.i.d. sequence or Markov chain. For Adagrad, RMSProp, and AMSGRAD, bounding the bias of the gradient estimator a sufficient condition for verifying H3 i), which turn enables us derive convergence results in each scenario.

---

Lid. case, Assume that {X,.n E N) are i..d. random variables. If the mean field function (0,, E H (Xx+1) Fx] aligns with the true gradient, then the estimator is unbiased. Other-
wise, the bias of the gradient estimator is
bp+ [lh(0n)) VV(O.))l
Markov Chain case. Assume now that (Xn, 7. N is Markov Chain. The bias consists of two parts: the difference between the mean field function and the true gradient, and term due to the Markov chain dynamics. For all T 2 O, we define the stochastic update as follows:
Ho, (X++1)
Σ Ho. (x
T
where x represents the i-th sample generated iteration 1. This multi-sample estimator is commonly used in applications such as Reinforcement Learning, Markov Chain Monte Carlo, and Sequential Monte Carlo methods, effectively reducing the variance of the gradient estimator. The mixing time Tmix of a Markov chain with stationary distribution and transition kernel P is characterized as:
s Tmix == inf { sup Drv (Pp 11
where DTv denotes the total variation distance. For an ergodic Markov chain with stationary distribution the bias of this gradient estimator when using T samples per step is
J = [k(0,) (V.)))l + M TTmxx/T
where (0)) f He (z))))(dz) the general optimization problem reduces the following stochastic optimization problem with Markov noise, as considered in most of the literature (28 24 7]:
min ((0) := Ex- (f;; x)]. PERd
where - x0) ) a loss function, and क is some stationary data distribution of the Markov Chain and Ho, (x(1) 24
k41 (O,; x-( k41), then b M /mixs/ similar to SGD with Markov Noise
Applications and Experiments
5.1 Bilevel and Conditional Stochastic Optimization
We can now apply our theoretical results in various settings where biased gradients are involved. In particular, they apply to the fields of Stochastic Bilevel Optimization and Conditional Stochastic Optimization. Stochastic Bilevel Optimization consists of minimizing an objective function V with respect 0, where V is itself function of o² (0) and ø' (0) is obtained by solving another minimization problem. Conditional Stochastic Optimization focuses on optimizing the expected value of a function that contains nested conditional expectation on random variable 77. We provide in Table [ summary of the assumptions satisfied in these settings, which allow to apply the results of Section and to obtain (log n/ /n + b,) convergence rate in both cases, and explicit forms for b,. To our knowledge, these are the first convergence rates obtained in these settings.
We refer Appendix for other examples in which the bias of the estimator can be controlled, in particular Self-Normalized Importance Sampling (Appendix D.II. Sequential Monte Carlo Methods (Appendix D.2) Policy Gradient (Appendix D.3), Zeroth-Order Gradient (Appendix D.4 and Coordinate Sampling (Appendix D.5
5.2 Experiments with IWAE and BR-IWAE
In this section, we illustrate theoretical results in the context of deep VAE. The experiments were conducted using Py Torch 65 and the source code can be found here? In generative models,

---

Table Bilevel and Conditional Stochastic Optimization with our Biased Adaptive SA framework.
Applications
Stochastic Bilevel Optimization
Conditional Stochastic Optimization
Problem
PER s.t. x (0)
min Eg [f(0, o' (0);
min Eg de
[fs (Enl (0,(0,))))
E argmin Eg [9(0, ()
6ER
Lipchitz Constant
H2
Lemma C.2
Lemma C.6
Bias Control H3
Lemma
Lemma
Gradient H5
Lemma
Lemma
Convergence
Theorem
Theorem
the objective is to maximize the marginal likelihood log po (z), which the marginalization of (z. 2) + po (z, 2), where represents the observations and 2 is the latent variable. Under some simple technical assumptions, by Fisher's identity, we have:
o log po()) = / Vo log po (zr, 2)po(= r)dz.
However, in most cases, the conditional density + pa(z x) is intractable and can only be sampled. Variational Autoencoders introduce an additional parameter e and a family variational distributions qa(2 æ)) to approximate the true posterior distribution. Parameters are estimated by maximizing the Evidence Lower Bound (ELBO):
log (xr) gxt(-1z) log (a( Z) go (Z [x)]
LO, o;)).
The Importance Weighted Autoencoder (IWAE) [I2] is a variant of the VAE that incorporates importance weighting to obtain tighter ELBO. The IWAE objective can be written follows:
pa(æ, 2
CRWAE () = E, B (-1x) log
t=1 9o [Z(1) xx)
where & corresponds to the number of samples drawn from the variational posterior distribution. The estimator of the gradient of ELBO in IWAE is biased estimator of Vo log po In Theorem B.1 we establish that the bias of this estimator is order O(1/k), thereby allowing us to derive a one of
convergence rate for IWAE. Since bias has impact convergence rates, propose the bias reduction techniques, the Biased Reduced Importance Weighted Autoencoder (BR-IWAE) [14. which is detailed in Appendix B
conduct our experiments on the CIFAR-10 dataset 51 and use a Convolutional Neural Network (CNN) architecture with the Rectified Linear Unit (ReLU) activation function for both the encoder and the decoder. The latent space dimension is set to 100. We estimate the ligelioel using VAE, IWAE, and BR-IWAE models, all of which are trained for 100 epochs.
Dataset and Model.
Training is conducted using Adagrad, RM- SProp, and Adam with a decaying learning rate. Although AMSGRAD is analyzed our theoretical results, we use Adam for experiments due to widespread use in practice. Additional details are provided in Appendix
(Aclagr ad)
HWME IAdagradd
1.95
(Adagred)
(RMSProp)
Test loss (x10s))
1.95
IWAE (RMSProp)
L925
BR-WAE (RM55Prop
(Adam)
1.
IWAE (Adam)
BR INAE (Adom)
First, we set & = 5 samples in both IWAE and BR-IWAE. The losses are pre- sented in Figure [ We show the negative log-lik likeeiilloood on the test dataset for VAE, IWAE, and BR-IWAE with Adagrad, RM- SProp, and Adam. As expected, we ob- serve that IWAE outperforms VAE, while BR-IWAE outperforms IWAE by reducing bias in all cases.
1.755
1.55
1325
Epochs
Figure 1: Negative Log-Likelihood on the test set for Different Generative Models with Adagrad, RMSProp. and Adam on CIFAR-10. 10. Bold lines represent the mean over 5 independent runs.

---

Then, we illustrate empirically the convergence rates obtained in Corollary 4.5 and Theorem 4.6
IWAE. Since the bias of the estimator of the gradient in IWAE is of the order O(1/k), choosing bias of order ((n=a) is equivalent to using ni" samples at iteration n to estimate the gradient. We plot Figure the gradient squared norm (O,)))) and the Negative Log-I oog-Liielihood is given in
Appendix E.2 Note that all figures are with respect to epochs, whereas here, represents the number of updates of the gradient. The dashed curves correspond to the expected convergence rate Onn-1/4) 1/4) for a 1/8 and (log n/ /n) for a 1/4 and a 1/2.
1/8
16"
1/2
LB (Adant)
(adam
10'
Epochs
Figure 2: Value of [0,]] in IWAE with Adagrad (on the left), RMSProp, and Adam (on the right). Bold lines represent the mean over 5 independent runs. Figures are plotted on a logarithmic scale for better visualization. Both figures have the same scale, so we have not shown dashed theoretical curves on the right for better clarity.
We observe that the algorithms converge at the expected theoretical rates, and even faster. In Appendix we have included an additional experiment on the FashionMNIST dataset [76), which shows similar behavior, but the convergence is closer the expected rates, suggesting that upper bounds may be tight. We see similar convergence rates for Adagrad, RMSProp, and Adam, although, as expected, Adam performs slightly better. Moreover, it is clear that convergence is faster with larger but beyond a certain threshold for a the rate of convergence does not change significantly. Since choosing larger induces an additional computational cost, it is crucial to choose an appropriate value that achieves fast convergence without being too computationally expensive. Choosing an optimal number of samples at each iteration remains an open problem depending the chosen generative model.
Discussion
This paper provides non-asymptotic analysis of Biased Adaptive Stochastic Approximation with and without the PL condition in the non-convex smooth setting. We derive a convergence rate of Ologn/ / + 6,)) for non-convex smooth functions, where bn corresponds the time-dependent decreasing bias, and an improved linear convergence rate with the We also establish that Adagrad, RMSProp, and AMSGRAD with biased gradients converge critical points for non-convex smooth functions. Our results provide insights on hyper-parameterr tuning to achieve fast convergence and reduce computational time. A natural extension of this work the analysis of the assumptions, the bias and convergence rates for specific deep learning architectures. theoretical analysis of the Monte Carlo effort required at each iteration to obtain an optimal convergence rate is another interesting perspective.
(PL) condition.
Acknowledgements
The Ph.D. of Sobihan Surendran was funded by the Paris Region PhD Fellowship Program of Région Ile-de-France. We would like to thank SCAI (Sorbonne Center for Artificial Intelligence) for providing the computing clusters. We also express our gratitude to the reviewers for their insightful comments and suggestions, which have helped improve this paper.
10

---

References
[1] Sergios Agapiou, Omiros Papaspiliopoulos, Daniel Sanz-Alonso, and Andrew Stuart. Impor- tance sampling: Intrinsic dimension and computational cost. Statistical Science, pages 405-431, 2017.
[2] Ahmad Ajalloeian and Sebastian Stich. On the Convergence of SGD with Biased Gradients. arXiv preprini 00,0,
[3] Ahmet Alacaoglu and Hanbaek Lyu. Convergence of first-order methods for constrained nonconvex optimization with dependent data. International Conference on Machine Learning, pages 458-489 PMLR, 2023.
[4] Peter Auer, Nicolo Cesa-Bianchi, and Claudio Gentile. Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48-775 10448,--57 2002.
[5] Jonathan Baxter and Peter Bartlett. Artificial Intelligence Research, 15:319-350, 2001.
policy-gradient estimation. Journal of
[6] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. Journal of Machine Learning Research, 24(276):1-50. 2023.
[7] Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. First order methods with markovian noise: from acceleration variational inequalities. In Advances in Neural Information Processing Systems, volume 36, 2024.
[8] Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference On Learning Theory, pages 1691- 1692. PMLR, 2018.
[9] Léon Bottou. Une approche théorique de I' l'apprentissage connexioniste; applications à la reconnaissance de la parole. PhD thesis, Paris 11, 1991.
[10] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
[11] Claire Boyer and Antoine Godichon-Bagginn stochastic newton algorithms and their weighted averaged versions. Computational Optimization and Applications, 84(3):921-99) 992, 2023.
On the asymptotic rate of convergence of
[12] Yuri Burda, Roger Grosse, and Ruslan Salakhutdinov. Importance weighted autocncoders, In International Conference on Learning Representations, 2016.
[13] Gabriel Cardoso, Yazid Janati Idrissi, Sylvain Le Corff, Eric Moulines, and Jimmy Olsson. State and parameter learning with PaRIS particle Gibbs. In International Conference on Machine Learning, pages 3625-3675. PMLR, 2023.
[14] Gabriel Cardoso, Sergey Samsonov, Achille Thin, Eric Moulines, and Jimmy Olsson. BR- SNIS: bias reduced self-normalized importance sampling. In Advances in Neural Information Processing Systems, volume 35, pages 716-729, 2022.
[15] Congliang Chen, Li Shen, Fangyu Zou, and Wei Liu. Towards practical adam: Non-convexity, convergence theory, and mini-batch acceleration. Journal of Machine Learning Research, 23(229):1-47, 2022.
[16] Pin-Ye Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security pages 15-26, 2017.
[17] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances Neural Information Processing Systems, volume 34, pages 25294-25300 2021.

---

[18] Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for td (0) with function approximation. In Proceedings of the AAAI Conference on Artificial Intelligence. pages 6144-6160, 2018.
[19] Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of Adam and Adagrad. arXiv preprint arXiv:2003.022. 02395, 2020.
[20] Pierre Del Moral, Arnaud Doucet, and Sumeetpal S Singh. A backward particle interpretation of Feynman-Kac formulae. ESAIM: Mathematical Modelling and Numerical Analysis, 44(5):947- 975, 2010.
[21] Yury Demidovich, Grigory Malinovsky, Igor Sokolov, and Peter Richtárik. A guide through the zoo of biased sgd. In Advances in Neural Information Processing Systems, volume 36, 2024.
[22] Aymeric Dieuleveut, Gersende Fort, Eric Moulines, and Hoi-To Wai. Stochastic approximation beyond gradient for signal processing and machine learning. IEEE Transactions on Signal Processing, 2023.
[23] Thinh T' Doan, Lam M Nguyen, Nhan H Pham, and Justin Romberg. Finite-time analysis of stochastic gradient descent under markov randomness. arXiv preprint 2.ti::2003.1977, 2020.
[24] Ron Dorfman and Kfir Yehuda Levy. Adapting to mixing time in stochastic optimization with markovian data. In International Conference Machine Learning, pages 1429-5446. PMLR, 2022.
[25] Timothy Dozat. Incorporating Nesterov momentum into Adam. In ICLR Workshop track, 2016.
[26] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685. PMLR, 2019.
[27] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7), 2011.
[28] John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael I Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 22(4):1549-1578 2012.
[29] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International Conference Machine Learning, pages 1467-1476. PMLR, 2018
[30] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In International Conference on Machine Learning, pages 1126-1135 PMLR, 2017.
[31] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. International Conference Machine Learning, pages 1568-1577. PMLR, 2018.
[32] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):234,-2368, 2013.
[33] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv: 10Xiv:8002.022 02..6.22666. 2018
[34] Pierre Gloaguen, Sylvain Le Corff, and Jimmy Olsson. A Carlo online smoothing algorithm. Bernoulli, 28(4):2606-666 -2000, 2022.
sequential Monte
[35] Antoine Godichon- Codichon-Baggioni and Pierre Tarrago. Non asymptotic analysis of adaptive stochastic gradient algorithms and applications. arXiv preprint arXiv:2303.01370. 2023.
[36] Riccardo Grazzi, Massimiliano Pontil, and Saverio Salzo. Bilevel optimization with a lower- level contraction: Optimal sample complexity without warm-start, Journal of Machine Learning Research, 24(167):1-37, 2023.
12

---

[37] Mingyi Hong, Hoi-To Wai, Zhaoran Wang. and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor- critic. SIAM Journal Optimization, 33(1):147-180, 2023.
[38] Bin Hu, Peter Seiler, and Laurent Lessard. Analysis of biased stochastic gradient descent using sequential semidefinite programs. Mathematical programming. 187:383 408, 2021.
[39] Yifan Hu, Xin Chen, and Niao He. On the bias- varssarainceoosstt tradeoff of stochastic optimization. In Advances in Neural Information Processing Systems, volume 34, pages 221 19-22131, 2021.
[40] Yifan Hu, Siqi Zhang, Xin Chen, and Niao He. Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning. Advances Neural Information Processing Systems, volume 33, pages 27700, 2020.
[41] Feihu Huang, Junyi Li, and Shangqian Gao. Biadam: Fast adaptive bilevel optimization methods. arXiv preprini arXiv:2 106. 1396, 2021.
[42] Tommi Jaakkola, Michael Jordan, and Satinder Singh. Convergence of stochastic iterative dynamic programming algorithms. In Advances in Neural Information Processing Systems, volume 6, 1993.
[43] Kaiyi Ji, Junjie Yang. and Yinghin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892 PMLR, 2021.
[44] Belhal Karimi, Blazej Miasojedow, Eric Moulines, and Hoi-To Wai. Non-asymptotic analysis of biased stochastic approximation scheme. In Conference on Learning Theory, pages 1944-1974. PMLR, 2019.
[45] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the tolyak-tojasiewicz condition. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pages 795-811, Springer, 2016.
[46] Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint arXiv:2002.03322, 2020.
[47] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations, 2015.
[48] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Representations, 2014.
[49] Vijaymohan Konda and Vivek Borkar. Actor-critic-type learning algorithms for markov decision processes. SIAM Journal on control and Oplimization, 38(1 (8(1))94-1 1999.
[50] Milena Kresoja, Zorana Lužanin, and Irena Stojkovska. Adaptive stochastic approximation algorithm. Numerical Algorithms, 76(4):917-977, 2017.
[51] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical Report, 2009.
[52] Chandrashekar Lakshminarayanan and Csaba Szepesvari. Linear stochastic approximation: How far does constant step-size and iterate averaging go? International Conference on Artificial Intelligence and Statistics, pages 1347-1355. PMLR, 2018.
[53] Rémi Lelue and François Portier. Sgd with coordinate sampling: Theory and practice. The Journal of Machine Learning Research, 2340):1540 2022.
[54] Qiang Li and Hoi-To Wai. State dependent performative prediction with stochastic approxima- tion. In International Conference on Artificial Intelligence and Statistics, pages 3164-3186. PMLR, 2022.
[55] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019.
13

---

[56] Yin Liu and Sam Davanloo Tajbakhsh. sta with biased oracles. arXiv preprint arXiv:2306.078/1 2023.
stochastic optimization algorithms for problems
[57] Don McLeish. A general method for debiasing a Monte Carlo estimator, Monte Carlo methods and applications, 17(4):301-315, 2011.
[58] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Univer- sal adversarial perturbations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1765-1773, 2017.
[59] Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algo- rithms for machine learning. Advances Neural Information Processing Systems, volume 24, 2011.
[60] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574- 1609, 2009.
[61] Yurii Nesterov and Vladimir Spokoiny, Random gradient-free minimization of convex functions. Foundations of Computational Muthematics, 17:527-566, 2017.
[62] Sebastian Nowozin. Debiasing evidence approximations: On importance- weighted autoencoders and jackknife variational inference. In International Conference on Learning Representations, 2018.
[63] Julie Nutini, Mark Schmidt, Issam Laradji, Michael Friedlander, and Hoyt Koepke. Coordinate descent converges faster with the gauss-southwell rule than random selection. In International Conference on Machine Learning, pages 1642-1641. PMLR, 2015.
[64] Jimmy Olsson and Johan Westerborn. Efficient particle-based online smoothing general hidden Markov models: the PaRIS algorithm. Bernoulli, 23(3):15511196, 2017.
[65] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary De Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS Autodiff Workshop, 2017.
[66] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4))838-855, 1992.
[67] Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
[68] Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400-407, 1951.
[69] Tao Sun, Yuejiao Sun, and Wotao Yin. On Markov chain gradient descent. In Advances in Neural Information Processing Systems, volume 31, 2018
[70] Vladislav B Tadić and Arnaud Doucet. Asymptotic bias of stochastic gradient search. In 2011 I 50th IEEE Conference on Decision and Control and European Control Conference, pages 722-727. IEEF, 2011.
[71] Yee Teh, David Newman, and Max Welling. A collapsed variational bayesian inference algorithm for latent dirichlet allocation. Advances in Neural Information Processing Systems, volume 19, 2006.
[72] Tijmen Tieleman, Geoffrey Hinton, al. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 4(2):26-31, 2012.
[73] Qianqian Tong, Guannan Liang, and Jinbo Bi. Calibrating the adaptive learning rate to improve convergence of adam. Neurocomputing, 48 481:333-356, 2022.
[74] Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. The Journal of Machine Learning Research, 21(1):9047-907, 2020.
14

---

[75] Xidong Wu, Jianhui Sun. Zhengmian Hu, Junyi Li, Aidong Zhang, and Heng Huang. Federated conditional stochastic optimization. In Advances in Neural Information Processing Systems, volume 36, 2024.
[76] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint 1rxXiv1708..774:::: 2017.
[77] Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in neural information processing systems, volume 31, 2018.
[78] Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint 1200, 2012.
[79] Fangyu Zou, Li Shen, Zequn Jie, Ju Sun, and Wei Liu. Weighted adagrad with unified momentum. arXiv preprint arXiv: 03408, 2018.
15

---

Supplementary Material for "Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation"
Table of Contents
Convergence Proofs
17
A.1
Proof of Theorem
17
Proof Theorem
Proof Corollary
A.4
Proof Corol lary
19
A.5
Proof of Corollary 4.5
20
A.6
Proof of Theorem 4.6
22
A.7
The Impact of regularization parameter 0 in Adam
25
B
IWAE/BR-WAA
26
Importance Weighted Autoencoder (IWAE)
26
BR-IWAE
28
B.3 Some Other Techniques for Reducing Bias
29
C Application of Our Theorem to Bilevel and Conditional Stochastic Optimization
30
C.I Stochastic Bilevel Optimization
30
Conditional Stochastic Optimization
32
D
Some Other Examples of Biased Gradients with Control on Bias
34
D.1
Self-Normalized Importance Sampling
34
D.2
Sequential Monte Carlo Methods
34
D.3
Policy Gradient for Average Reward over Infimite Horizon
35
D.4
Zeroth-Order Gradient
35
D.5
Compressed Stochastic Approximation: Coordinate Sampling
36
Experiment details and supplementary results
E.
Experiment with a Synthetic Time Dependent Bias
37
E.2
Additional Experiments of IWAE
37
16

---

A Convergence Proofs
A.1 Proof of Theorem 4.1
We first establish a technical lemma which is essential for the proof.
Lemma A.1. Let (8m)n20 (1m))21 (fh))21 and (vn)a21 be some positive sequences satisfying the following assumptions.
The sequence 8n follows the recursive relation:
on S (1 - Yn + To) 8n-1 + Un
with 60 2 0 and > O.
Let inf (n 2 1: 1/ S w), then for all n 2 no + 1, we assume that win S 1.
Then, for all n E N,
12
ón exp exp
Σ k=n/2 /
Y
exp
2 2 7x
66 + 2
max 2k Isksn Tl
+
max
Uk.
w
n/25kgn
The proof is given in [35 Proposition 6.1]
Theorem A.2. Assume that H1
H4 hold. Let 0n E Id be the n-th iterate of the recursion
Then,
EV (0,)) - v(0)
E (0o) - +(0')}
E
2
max IskSn
AR+1UK
exp (- Σ
1
A6+17k+1
Pk+1 7k41
2
k=n/2
2 max Uk
x exp 2 Σ
Ch (
1 n/ n/2SkSn
where
ã= T2L 2
x
Lo Pk+1
C2 max 0,
4,8
and 2p rk+1 +
2 A1+1
Yk+1
with the convention C₁ if 52 = 0.
Proof. Since V is L-smooth (Assumption H2 and using the recursion
B of Adaptive SA, we obtain:
L
V (0n+z2) < V (0.. + (VV (0,) Bnt1 Onn) + 110nt1
0nl1
InZ
SV (0.) 7 (VV (0.), A, Ho, (Xn+1))+
| || (Xn+1)ll².
2
Writing Vn V (0,) V(0)). we get
Vn+1 S Vn m (VV (0m), Ho. (Xn+1)) + 1utt 11,,, (11+1)12.
2
2
Then, using H3
L 2 82
E [V++1] < [V]
1 (VV (0w) Ho, (Xn+1))
2
+ L
2 mn 1 [, (0, +1011++++22E)111
TzL.
T I
< 1
32 14tr1
EV, - Mnt1
In
E E/ (0.))1
2
La2 2 1
#1+11 7 +
2
17

---

Given the smoothness condition
with 0' = 8, and 0, - 1 VV (6n), we derive:
1 7 IIV (0.)1l² + 2T.
(0.)
IVV (0.)Il²,
IVV (0.))l 2 2LV,
Using the above inequality and the Polyak-Lojasiewiez condition
HI we obtain:
Ø2L +ē,
E [n+1l]
(1- 11-uu+17m+ 7n
3
EE [v]]
Lo 1nt1
7n+12n+1Int1
By choosing In+1 1n+1 we get:
B [[]++1] (1 unn+1
r2L (o2)
+ ō 12²)
IE [Vn]
n
Lo
82
pn+1
In+1In41 +
1n 1n+1
2
An+1
In order to satisfy the assumptions of Lemma A.
consider
72L
C = max
ã 4,32 m+1
with
5 =
+ 5 ēIL2 2
Then, since On 2 o, we have:
[[ S (1 u
Cn n+1
Lo $2
X
nn
E [v.]
74417441
2 Ant1
7 76+1
Now, using lemma A. by choosing:
Cn
/
Lo 32
6, = E [V..
x
7+1.
w
2' rn+1 +
2 Ant1
we have:
E (0,) - v(0') (Bo)
(0u) - v(0))+
max iskšn
32
7k+1
exp (- Σ
1
2
Tot1)
A kmn/2
x exp 2 n C Thet (i...)
2
max {uk).
1 n/25k$n
which concludes the proof by taking 7n+1 = An+1 An+17/+t1-
A.2
Proof of Theorem
By H2 using 5
obtain:
L V (0x+1) (V,) + (VV (0x), 0x11 0x) + 2222 110.11 - 0x
which, using the recursion of Adaptive SA and H4 yields:
(0++1) S V (0x) - 74+1 (VV (0x) Ho, (X++1)) + 8k+1 |o, (X++2)11, with dR+1
Using Assumption
H3
we have:
EV((++1) - E(V(
- 74+ E(
+ 74114411141 + 84t107 V (0&) - V (0*))).
+ 5k+1
18

---

Therefore,
Loj
1k+1 AR+1 2
7o f |[ [
1 (1 + 020k+1) (R IV (0x) - V (0*)) [R (0x+1)) V (
+ 7k+114+17k++ 56+10
Let us now consider the sequence of weights we defined by wp = 1 and w/ IT (1 + x26;)
Then,
Lō 7k+1 82 18 VVV (0+))
wk+1 7k+1 (At+1
I wk ( (0x)] - V (8*)) wk+1 (E (0s+1)] - V
+ 1k+116+111 16+111+ + 20k+10x+106
In the sequel, let us denote Vn2 = -V.)
(0*), so that
n
WK+178+126+1
1
E VIVV n
2Ax+1
1
B [V]]
Wn+1
1v
wk 11
2
k=
0=
Then, given that 7k+1 S (T
we have
E
WK417841241 VV (0x)]
< Wil [Vo wn+1 I [V
164178+1 +
Σ
W2410+4108
k=0
Consequently, by definition of the discrete random variable R,
E
VV (On)l
Wk++ TK+ AR+1
E [IV (0.))1)
k= 11
E Vol wn+1
[n+11
Ek=o Wi+11 + Ek=o W6-1064107 W W3+1
which concludes the proof by noting that V(On+1) V (0*).
A.3
Proof of Corollary 4.3
The proof is direct consequence of the fact that for a sufficiently large n:
O nn
++1)
1, if 1, if
if
O
(1)
(logn)
A.4 Proof of Corollary 4.4
By
H2 using 55) we obtain:
V (0k+1) < V (0n) + (0.). 00+1 -0x) + L 110 - 0x.12
< V (8x) - 7h+1 (VV (Xx+1)) + IYZ+1
||AA 1l Ho (Xx+1)112,
19

---

which, using H4 and H3 yields:
L
V (0x+1) S (0x) 7 (VV (0x) He (Xx+1)) + 2 3
Using H3
LM
S ((0)) - 7R+I + (V))) 16412411
M2 1824
2
Therefore.
LM
76+1 (0x) & V E (V [F + 1641 +
2
2
and
No+ Ax- 1B VIV (OWII² $ IV (0o) - V (0n+1)) + Σ
Yk+1 74+1A4+7KH7
0=
k=
LM n
3
1k+1
Consequently, by definition of the discrete random variable R.
E
VV (0R)1?
E VV (0=)
Ak+11
VV (0w))*)
k=
Vo,n + Ek= Mh AR+ + LM
Ek
12
Vn
where Vo, (() V(0++1)), which conclude the proof by noting that V(0++1) 2 V(0*).
A.5 Proof of Corollary 4.5
Here, we consider the case where the regularization is non-increasing, i.e., where ó = 3.7 The constant case strictly analogous. To verify H4 we demonstrate that the control of the maximum and minimum eigenvalues is satisfied for Adagrad and RMSProp.
Adagrad
Lower bound for the smallest eigenvalue of A By assumption H5
we have:
Ho, (X++1) Ho, (Xx+1)
SM².
n+ k=D
This implies that:
Hos (X (Xot1) )) -1/2 Σ
Amin (An) Amaax 3 la + Diag
n n+1
k=
2 (8 + 2
Upper bound for the largest eigenvalue of A,.
-1/2
Aenax )nn)(AAn)) Amin 1 + Diag
n n Σ Ho, (X (Xer1))
$ But1
20

---

Therefore, by setting An+1 - (8/² + _M2)-1/2 and 3n = Can we have À = 0 and one can arbitrarily choose 3 (one can take for the constant regularization case).
RMSProp
Lower bound for the smallest eigenvalue of An. By assumption H5 we have:
||Vall s (1 P)
Ho (X++1)ll < 22 - p) Σ M²
where we used the fact that Ex= pm ( (1- (1-p)-1 This implies that:
Amin (An) Amax (077244 Diag (Vw.) 1/2 2 (3T² 2 + 22
Upper bound for the largest eigenvalue of An. Note that
Amax Amax(App (An) Amia (3 Ia + Diag (V.)) - 1/2
I Bnt1
Therefore, under H2
H3
and
H5
we can conclude that
log n V1
VV (0=)ll)
=
bn
where b, corresponds the bias which comes from Tn in H3 i). Choosing in C,n get:
O (n
if 1/2,
bn
0 n 1112) 1/2)
if 1/2,
n2 1/2 logn)
if 1/2.
Now, we show that under the control of bias, i.e.,
|IB [H, (Xn+1) VV (0x)l S Can
we can verify i) with similar bound on the bias, where 2a. This yields the bias term b, as follows:
n 0 O0 1/2)
if 1/4, if > 1/4,
logn)
if = 1/4.
Verifying Assumption H3 (i) for Adagrad. Using the tower property, have:
(VV (0,), A, Ho. (Xn+1))) (VV A, Ho., (Xx+1)) [Fu]l=
where (Fn)no represents the filtration generated by the random variables (0u. (Xalksn): Let An be an adaptive F, measurable matrix. Then,
E BVVV (0,) Ho (Xn+1)) [Fa]= VV (0.) A,E Ho, (Xn+1) [Fn))
as
Arain (A..)
R VVV (.)). (4, A, (X [F,
Control error between A.. and A.,
We only verify Assumption H3 for Adagrad algorithm since it is analogous to RMSProp. Consider A, given by:
-1/2
An diag
3ati la n
Ho, (X++1) Ho, (Xer1)))
First, writing
1 n-
Ho, (X++1) Ho, (Xa+1)) ))
-1/2
A, diag
8-2 I1
n 1
k=
21

---

and denoting by Ali] the i-th element of the diagonal of matrix A, we have
Anli Anli] =u 1/2
(1//²² -u/²² Un 1/2
2 0
where
n Σ
1 n-
Un 1ut1 n + k=0
(Ho, (X++1) [t]) and Un = Pat2 +
Σ
(Ho, (X++1) [i)
n2 + 1
k=0
Then, since Un 2 On:
An An
Un Up
2
(Ho, (Xn+1) [0]) 2u," 3/2
Un Un (vin Un + vvn)
n n+
gn+1
(Ho, (Xn+1) [01)
2
n n+ 1
Since the bias of Ho,, (Xn+1) is bounded by bn = Ca
R [VV (0n), An Ho,, (X [Fn]
VVV (0,) A, (Ho.. (Xx+1) (Fa)) + [(VV (0n). (An - Ho. (Xntz)) [Fn]
2 Amin (A,) VV (0,)ll Amax (An) VVV (0m) bn
VIV (0m)ll Pa+l E |1o, (X (X,+1)I)
+ As Hg, 1X and the gradient of V are uniformly bounded by M, Amin (An) 2 23T2+ 1/2-1/22 so that
VV (0.))l Bu+1 Mr M 89
E (VV (0.), A,, Ho, (Xn+1)) [F,] 2
V0 + M
n
and Assumption H3 is satisfied with Ant1 = (0T2 + 22)-112 and rn+1 1M B2 /na11 M 83
(n + 1).
A.6 Proof of Theorem 4.6
The proof of this theorem is inspired by 67 and 773. considering biased gradient estimators and decreasing step sizes. We define the operation max(D;; D2) for diagonal matrices D1 and D2 the matrix formed by taking the maximum between the diagonal elements of D, and D2. We say that the sequence (An),21 of diagonal matrices is decreasing if all diagonal terms are decreasing, in other words, if all eigenvalues are decreasing.
Let 0++1 = 0k+1 + 1 (0x+1 0s). for & > 1, K E 1) and my Pim + (1 - -Pi)a with gk Ho. (X++1). Using the recursion of AMSGRAD, we have:
0ut1 0x. = (1 x)++00 (1 + 0x) + kθL- = (1 + x) (0x41 9x) - K (0x- 1
-1 + x)T AbTE + AN 1 1
Choosing H = p1/(1 p1), we can rewrite it as:
0 - 0r k (n Ax) m 7k+1
By Assumption H2 V is L-smooth, using the recursion of AMSGRAD together with a Taylor expansion with Oz. we obtain:
((@k+1) S v 0x)
VV
0k 0zt1 0z)
L
0 - 0bl?
2
$ V (%)) -K+11 VV (1)) A4.9k) ) + K VVV (Bk) AT - Ak) mk-1)
+ L7
||Arghll 112 + Lxd [1 Mh+1 At) m 112
< V (x)
Ti,s + T2 + Ta + T4,
22

---

where
T = 7 (VV (0x), Asgk) + +12+t1 A
72,6 = -K+1 VV (0s) VV (0k), ALgg) (
Ta,6 = K (VV (8s) (M - 1 As) mm-11
Ta,k- = Lx 11(Tx=A 16+1 Ac) ma-111
Note first that
E [7
1k+1 E KVV (0x), ALDUN + L Σ
tht1 B || 12]
h=1
k=
S Cx
M+I |IV (0w)1p) + Cx Σ
M44174+1 + L Σ
Re [1Anoxli]
k= where Cx (ō + M2)-1/2
R=1
A=1
For the second term, using the inequality ry S /2 + y² /2 for all x, y, and the smoothness of V. we get:
n
Σ E [22
E
(6))
VV (0s), 7h+ Asgrs)
E
VV
VV (0x)
EE 11
k=1
1
E
0x
eall"
+
Σ
7k+1
E
[|ARga11
2 k=1
2
A=
k22 1,2
n
11
E 110 - 0k 12-111
+
7k+1
E
[|| ||A.geRl 13
2
2
k=1
x2 L n
a
E ||As-
[2]
7h+
E
2
k=1
For the third term, using the boundedness of the gradient of V and the fact that || S M by we have:
Lemma A.3
E
E
VV (8x):
(1 (6)
k=1
d
n
S 2
E 1 An [6] -x++1A
d
S x
Σ E I Aol0] - 1m+14 S KM2
where in the second inequality, we used the fact that 7k and A are decreasing since we use V = max(VV-1 Vi)). For the last term, using the boundedness of the gradient of V yields:
E [Ta, = Lxd Σ E [1(T Ax-1 Ax) m [12)
$ Lk 2
E (r Yk+1 Ac(1))
im
km
m
< LK 2
E (n [1]) 199--o0 A
1=1
< Lx M22
23

---

where we used the inequality (z (z x²~ v² when x 2 in the second last inequality. Combining all these terms, we finally obtain:
16
Cx
7kt1
VV (Bx)
7 7k+ 1++1 + L.
7 1 E [|AR9a) a
Σ 2 ||Argall]
V
Cx
K 2
|| 1 [P] RMM + LK M2
2
k=1
where V (B,) v(+)) 2 E(V())) V(On+1)) Choosing ?n n 1/2 112 and using Lemma
A.3 and
15
Lemma 24] yields
E |I (1 p1) pi)dC log 1+ n.2
2 Tk+1
E [1Aemal]] (1 pı) Σ
2 7h+
0 (d n)).
Therefore, by dividing both sides by CAn 112, we obtain
n
|VV (0x))²) = O
dlog
+ bn
Vn
vn
which concludes the proof.
Lemma A.3. Let 7h-1 S Ti for all & N, and let Au be the adaptive matrix defined in Algorithm Assume that p E [0, 1). Then, for all k E N:
m M and Σ M B
p1) S S(1 |lmmall
Σ
||Angu!?
k=1
Proof. For the first inequality, we have:
1 11-1-00 pl) k ge S - p1)
&
|mell -
Σ 8=1
A Il S M(1 - pi) Σ S
220
where we used the fact that Σ Erso pf 1/(1 p1). For the second inequality, using the fact that Yk and Aş decreasing (in the sense that all eigenvalues of A are decreasing), since we Vi max(Vv-1 Vi), we write:
k gi
224 ||
Σ k=1
Tk+1
As P1)
Σ
Pi
k
1=
1=1
12
(1 p1)²
1k+1
2
p1
k-t
Aegel 1
$ (1 p1)
k-t 2
224 ||
72
$ (1 p1) 2
2241 ||Acgel2
which concludes the proof.
24

---

A.7 The Impact of regularization parameter ő in Adam
In our case, we have dependence on 8 in the logarithm, which is common for adaptive algorithms. The regularization parameter 6, originally introduced to avoid the zero denominator issue when Vi approaches often overlooked. However, has been empirically observed that the performance of adaptive methods can be sensitive to the choice of this parameter, especially when a very small 6 is used, which has resulted in performance issues in some applications.
In practice, 5 is typically chosen as 10 In our convergence rate analysis, even though the logarithm of 88-1111 is small, it still impacts the convergence rate. A larger å will lead better convergence rate, while a smaller d will preserve stronger adaptívity. We need to find better compromise between the convergence rate and the adaptivity choose 6. In [77 67 7
shown that by choosing between 10 3 and 10 better results were obtained in some applications of deep learning.
Furthermore, several modified versions of Adam have been proposed, such AMSGRAD 777 and YOGI [67] with the discussion of the regularization parameter 8. The authors of 731 proposed new modified version of Adam called SADAM to represent the calibrated ADAM using the softplus function. this algorithm, they define V2 softplus (VVs) while other terms remain unchanged. Since we have:
V = softplus (VVss - log 1 + eVVr =
b log (elvVi) = VVk.
where b is the parameter to control for achieving better convergence rate. In this case, we have Amax (Ax) < 6/ log 2. which is similar to 8 1/2 Adagrad and Adam. Additionally, they demonstrate that 6 RJ 50 appears to be good choice based on the empirical observations.
25

---

B IWAE/ BR-IWAE
B.1 Importance Weighted Autoencoder (IWAE)
In this section, we elahorate on the IWAE procedure within our framework to illustrate its convergence rate. The IWAE objective function is defined as:
pa(x, 2 t=1 4o [Z(1) xx)
IIAA x;)) E (-1x)) log
where corresponds to the number of samples drawn from the encoder's approximate posterior distribution. Denoting V the objective function, i.e., V(0) log (o the gradient of V and the estimator of the gradient of the ELBO of the IWAE objective are given by:
VoV(0) = V log po (a: poll) [V log po (2r, z)]
w((
(10)
VOLTWAR (2;x)
Ve log (x, 20),
2t=1 w(
where ( = (a, 2 (01 / (2 (z)))z) the unnormalized importance weights. Theorem B.1 provides an upper bound for the bias of this estimator.
Theorem B.1. Let X C Rd and Z C Rd denote the data space and the latent space, respectively. Assume that there exists M such that for all A θ Rd. X and E Z, I/ log po z)ll s (x). Then, there exists a constant C > O such that for all E O 0 E and x E X,
C
where (0) and CO o;x)) x) are defined in 10
Proof. The proof is adapted from II Theorem 2.1]. By definition,
VOLLWAE (0,6;z) VoV(0)= Ee ((() ( log (2, =00) - Bpa(- Vo po(r, z)])
Σk wll)
Writing (1x z(0) V log po (I,22(0) 20) (xp((1)) [V log po (z, 2)], yields
Vock CIWAE (0, xx (0V Ek= w(t) (xx
Σk wl()
Since Egg [WH(2 (z, 2)] = 0, we have:
v WOL -VV()) & Ek wit) Ax, 200)
Byy (w(((,
4 t== w(l) (
As Ek= (1) (I, (0)) /k is an unbiased estimator of Byg
Bgg VoLLAA (0, (;;x))
-v [
= =Eqs
Σ
w fxx,
Ens [u(((,,)))
I D w(e)
Egg [w)]
T
t=1
so that
Egg VoL..AB x;;)) -vvV)) VoV(
b Ek mn(0) Hr, 2(0) - Eggo Hr 2)
Egga [w] E wl(e)
Egg
Ego [w]
1 k Eh (()
26

---

Therefore,
By. (ock 00) -
- A - A2.
where
A Egg [ (VoCHWAEEO (0, vor(o)) 1 { with Egg 100
Egg ( (Voc (0,0:z) VoV(0)) L E2 wn vs Ri (w))
A2 =
Note that
k
k (0)
( (x)) - Egg (x. 2)]
A1
Egg
Ego
[m]
Ens [w]
k 1=1
1=1
2
Egg
w
(0) (x, 200) - BBg /wfi( z)
w
Egg [w]]
Eggo [w]] 2
K
t=1
t=1
272
2
<
Egg
Σ
w
(x, 2(0) - Egg [H, 2)
Egg
[w]] 2
k
8=1
27 1/2
x Egg
2)(
Eg [w]]
8=1
where we used Cauchy- Schwarz inequality in the last inequality. On the other hand,
k Σ
Egs [10] )
27
5 Eg 222
Egg
(1)
Σ
(()
k
K
k
E=1
1=1
and
Bgg
w (1) H(x, (1))
w wH((I, -Bys
Egg
t=1
( H ((,,)(00)
- 4d.22 Eg [w2
TTr
V
Finally, we deduce that
A
<
2
Bas
[w]]
2v d.M
Eng
[w
1/2
Eyg [22] Egg
4 dM
Egg
[w]]
2
VT.
[w]] k
Using the assumption on the boundedness of Ve log po 2)]l and the Markov incquality, obtain:
&
A2 S 2MP
2
( < Eggo [w]
t=1
1 *
< 2MP
2
(e)
Eya [w]
< -- Egg [wo]
7m1
E nv
[w]]
EF
Iw2 27
8.M
< 2MP
w
Egg [w0]
go
1R
[w]]
k
which concludes the proof.
27

---

Algorithm 2 Adaptive Stochastic Approximation for IWAE
Input: Initial point 8, maximum number of iterations n, step sizes (12 and a hyperparameter 2 0 to control the bias and MSF. for k = 0 to
1 do
Compute the stochastic update Vo oo C.WAB the Xk+1) using ko samples from the varia- tional posterior distribution and adaptive steps Ak-
Set 0k+1 02 7 As VoL (Ox, Φk; Xx+1).
Set 0x+1 = ON 74+ V L.W (Ok: dn; Xe+1).
end for
Output: (0*)osk<h
B.2 BR-IWAE
In this section, we provide additional details on the Biased Reduced Importance Weighted Autoen- coder (BR-IWAF). IWAF, instead of estimating the gradient of the ELBB with respect via the Monte Carlo method, we estimate the gradient of the true objective function p [V log (a z)] using the BR-SNIS estimator [14]. This estimator aims to reduce the bias of self-normalized impor- tance sampling estimators without increasing the variance.
Algorithm 3 BR-IWAE Gradient Estimator
Input: Maximum number of iterations /max for MCMC and number of samples & from the variational distribution q-(- 12).
Initialization: Draw 2o from the variational distribution 4s(- z)) for t to mmxx do
J441 Draw 4+1 fl.....k: k) uniformly at random and set 2,+1
Draw zt+1 1:b(()+4) independently from the variational distribution qa(- x)). Compute the unnormalized importance weights:
Po (2, 2141)
Wl kl.
g 24(1 x))
Normalize importance weights:
(8) We+
vl E Al.
Wi+1
Σ
++
Select žn-1 from the set 1ikk by choosing #(41 with probability w end for Output: (z]-k) 1815 and (w]-*) ise5tm
The BR-SNIS estimator of Epoc m) Vo log Po (z, 2)] is given by:
v log po (z,
1:k 2tgstam
( (' (zg
max
to
where lo corresponds to burn-in period. By 14 Theorem 4] the bias of this estimator decreases exponentially with lo- The BR-IWAE algorithm proceeds in two steps, which are repeated during optimization:
Update the parameter Φ as in the IWAE algorithm, that is, for all 2 1:
Φut1 on 7n+1 An V L /IWAB (On, On; X
Update the parameter by estimating 9 using SNIS as detailed in Algorithm
1ikk Ønt1 On An V log pe (Xn+1, 2
28

---

B.3 Some Other Techniques for Reducing Bias
In the previous section, we discussed one technique for reducing bias, BR-IWAE. Here, we provide an overview of some other bias reduction techniques within our context. First, the jackknife bias- corrected estimator [62] is defined as:
Clackknite (0, x;;); R
(0,0; (k ()).
which achieves reduced bias of O This can also be generalized to have bias of order O(h"") for some m 2 by considering:
Clackknife m
c(k, m, J) [ Σ 1=0
where the coefficients c(k, m) given
c(k, m. (-1)3 (k - j)m
(m j}!ز
The Delta method Variational Inference (DVI) is defined by:
DDVI E g (-1x))
log w
2k
t=1
where
w po(x, (=(2()) 1x)²
Wk
1
and
(w wx)²
The Monte Carlo estimator of the Delta method Variational Inference objective achieves reduced bias of ((k Some other techniques for reducing bias include the iterated bootstrap for bias correction, the debiasing lemma (57]. and Multi-Level Monte Carlo and its variants (3)
29

---

C Application of Our Theorem to Bilevel and Conditional Stochastic Optimization
C.1
Stochastic Bilevel Optimization
We consider the Stochastic Bilevel Optimization problem given by: min (0) = EEg [f 6 (0); (upper-level) DER!
(11)
subject to
o (0) E Eggminn&g [g(0,, () (lower-level)
dER'
where the upper and inner level functions f and are both jointly continuously differentiable and and Ç are random variables. The goal of equation (TT) is minimize the objective function with respect to 0, where 6 (0) is obtained by solving the lower-level minimization problem. This bilevel problem involves many machine learning problems with a hierarchical structure, which include hyper-parameter optimization [I), metalearning [0), policy optimization [37] and neural network architecture search [53 The gradient of the objective function given by:
VV (0) (0, o" (0))
(eog(0,"((0))
where v is the solution of the following linear system: Vāg(0, ( (0))o
(0,
Instead of computing v", the solution of the linear system above, 43 17 proposes a method to estimate v² This estimation introduces bias in the gradient of the objective function.
Consider the following assumptions.
H6 For all 0 E Rd, g( Φ) is strongly convex with respect to ø with parameter > 0.
H7 (Regularity Lipschitz condition) Assume that f. V,, Vg. Väg are respectively Lipschitz continuous with Lipschitz constants f,o, fI11, gg and Eg2.
Assumptions and H7 are the same assumptions used in [17] to obtain the convergence results with SGD. Furthermore, these two assumptions ensure that the first- and second-order derivatives of f and g. as well as the solution mapping o² (f), are well-behaved.
Proposition C.1. (77 Lemma 2.2]) Under Assumption 6 we have:
VV of (0, 6" (0)) - Vigg (0,6" (0)) (0, (0)) v.f (0)
(12)
Due to the dependence of the minimizer of the lower-level problem d" (0), obtaining an unbiased estimate of VV (0) is challenging. To address this, replace o²(0) in the gradient with o and define
vef(e, Φ) = Vof(e, Φ) Vosg(A, Φ) Vāg () Vof(O,))
Furthermore, by estimating Vāg((,
define the stochastic update H3 11 follows:
Hx Vef (02, (b+11Ex)))))))))))))))))))))).) Visa (Bx.
(: (( GVof (Ok, dx+1iE))
(13)
where G E I II 6,11 Vág (Be, oxt1: ((:) with N' is drawn from [1....,N] N} uni-
formly at random and (ca),..., (N7) are i.dd samples.
In Algorithm 4 we perform T steps of SGD on the lower-level variable de before updating the upper-level variable 0z using adaptive methods such as Adagrad, RMSProp, or AMSGRAD.
Lemma C.2. (33 Lemma 2.2]) Under Assumptions /16 and 117 for all (0,0") E Rdd Rd.
VVV (0) VV VV (0')ll Toy 1 0'11
with the constant Ly is given by
Lv = =v11 lg.1 (Cy,1 Lz)
CrD (g fg.1
+
Mg
My
and Lgg is defined as L, 1,1
+ too By
(l.2 + Lask
30

---

Algorithm 4 Stochastic Bilevel Optimization
Input: Initial points 0o, do. maximum number of iterations for the upper-level and for the
lower-level T, step sizes {Th, J2, momentum parameters Pt, P2 E [0, 1) and regularization
parameter 6 2 0.
Set mg = 0, Vo- 0 and V = 0
for to n 1 do
Set ΦR,0 Ok.
for t = 0 to T 1 do
14,++1 Wutt io+1 V (Ox, ou,ti Sx,))
end for
Set oR+1 UR.T. Compute the stochastic update H5 using Φk+1.
my -1 + (1 H
V/2 P2VA-1 + (1 H
V max (Vi-1, Diag(V)))
As سölي Vn] 1/2
0x+1 O2 7k+1 Asme
end for Output: (0x, db dssssknn
Lemma C.3. Under Assumptions H6 and H7 the following inequalities hold:
IV (0x) EH Full s 213 |1 -6" (0x))l + 25g
(1) s t,o + f9lel.0
1ig
where Lg = 2f.1 + fustes + feo
(6,2 + Su.fe22 and by = lo
1 (1 Mx
Mu N Eg.1
Px
M4
Proof. For the bias term, since VV (0k) (0k. o" (0x)), we have:
VV (0x) - [HH Fxll
| (0x, d' (0z) f (Ox, 0 + V (Ox, ox+1)) - E[Hls [Fl]ll
< 2 V f (0k, 6² (0k)) ff (0x, o + + V (0x, ox+1) E [H FFll
< 213 || 6² (02) + 26}
where we used
[33 Lemma 2.2] for the first term and 37 Lemma 11] for the second term. For the second inequality, we have:
Vof(B, Φ) Vof(H.0) Viso(A, Φ) [ m)] (o.( (va(((,e)))vvvv((o)) /l x) + V0s w) | x)] -1 [v,(0,))
f9111.00
$ +
Pg
Theorem C.4. Assume that H6 and H7 hold. Let On E Id be the n-th iterate of Algorithm In = c.n 1/2 and &nn = cn 1-2 /T. For any 2 1, let E (o, be a uniformly distributed random variable. Assume the boundedness of the variance of the estimators of Vf. Vg. and V2 Then,
E IVV (0R))1? = =0 llogn
(1
+ bn
31

---

Proof. By using Lemma
C33
V is smooth and Lemma C.3 the bias and the gradient of V are
bounded. Using our Corollary
4.5
we obtain:
E IVV (0n))l) =0 (Ow)))
(
log n + bn
Vn
where
Ei= 7k+16p b + Ek= Met1 1 0² (0x))1
v
Then, with
33 Lemma 2.3] and 17 Lemma 3], we derive:
on o
VT
We achieve classical convergence rate of O (logn/ vT) for Stochastic Bilevel Optimization prob- lems. Two types of bias emerge in this context: firstly, the challenge directly computing $ (0), and secondly, the necessity of estimating [))(0,0)]
Our results extend those of 17 to the adaptive case, particularly Adagrad, RMSProp, and AMS- GRAD. This provides convergence guarantees for the Alternating Stochastic Gradient Descent (ALSET) method. We can apply our convergence analysis to Stochastic Min-Max and Compositional Problems, as well as the Actor-Critic method with linear value function approximation 49 which can be viewed as a special case of the Stochastic Bilevel algorithm.
C.2 Conditional Stochastic Optimization
We now consider a class of Conditional Stochastic Optimization:
min
V(0) E&g [fe (Eeyle (0,))))
(14)
BERd
where fe(-) R R depends the random vector & and (y(+, Rd - R2 is a vector- vector-valued function dependent on both random vectors & and 17. The inner expectation taken with respect to the conditional distribution of ") given Ç. Given certain conditions the regularity of these functions, the gradient of V as defined 14) can be expressed as:
(V Eg (EE, 90, E))) VSe (Eyyle La (0,())
(15)
Constructing an unbiased stochastic estimator of this gradient can be both costly and, in some cases, impractical. Instead, opt for biased estimator of VV(O), using just one sample & and i.i.d. samples (7/ ) from the conditional distribution of given E:
( =
Σ
m7
V
1 m
m
In,
(0,E)
(16)
m
j=1
j=1
H8 For all & and y, assume that (c).). Vie(.), (n( (), and Vg {) are respectively Lipschitz continuous with Lipschitz constants f.D. f,I, lg.0 and gg.
H9 For all 0 and &. we assume that Eyyle (0.) E [,, (0.))]]]] S oz
Lemma C.5. 40 Lemma 2.2]) Under Assumptions H8 and
H9
the following holds:
(V: (n -V(
E
m
Lemma C.6. Under Assumption H8
we have:
-V (enier + l. 110 0'l
[VV( < f.
32

---

Proof. Denoting Gg = Ee (0, and VGa Enyle (V (0, [)), we establish the smoothness of V and Boundness of VV.
Smoothness of V:
[[V VV
Ei VG Ve V.e (Ga) E& VG V.fe (Ga)) }]]
| VG V (Ga) - E. VG (Ga)
+ | VG f (Ga)] E3 VVG fe (Ga) |||
E (VGo VG (Vf (Ga)
+ || V (V/s V (G
E& [IVGG VG [[] | (Ga)]]
+ Be Vl [ (Gg) - -V (Go) )I]
S 1g.18 0 - 0'1 + 9,06,, Eg [l Ga |I]
< f 0' + 3.0 ln 10 1l1.
Boundness of VV:
[VV E& (G
< | V/ (Go) S fg,0lf0
Theorem C.7. Assume that in AMSGRAD and P1, P2 E random variable. Then,
H8
and H9 hold. Let In -1/21/2, An denote the adaptive matrix U, For any n 2 1, let E mo. be a uniformly distributed
(
log n
IIV (0+)) =0
bn
Vn
where by is defined by writing mg as the number of conditional samples iteration k:
Ek vk
bn 0
n
Proof. This is an immediate implication of Theorem 4.6 using Lemmas C.5 and C.6
These results can also be extended to the Federated Conditional Stochastic Optimization problem 75 which is defined by:
1 Σ Eg, [5 (E (0,, (8. (+.))))
min V(Ø) BERd
R is the outer-layer function on the ε-th device with the randomness &e- R R99 is the inner-layer function the f-th device with respect to the conditional distribution of vi given &c. If the functions f (-) and of (-) for all L devices verify Assumptions|HHS H8 and H9 obtain the same convergence rate.
where E (+) : 1R9 +
and ( (c.t)
The following Table provides a comprehensive summary of the key points, including the verification of our assumptions and the convergence results obtained in both Stochastic Bilevel Optimization and Conditional Stochastic Optimization.
33

---

Table 2: Bilevel and Conditional Stochastic Optimization with our biased adaptive SA framework.
Applications
Stochneric Rilevel Optimization
Conditional Stochastic Optimization
Probiem
min Fg [s(e, (#): E)
Be (Enis (0. el]]
Rexd
6 (0) argmin Ee (o(o, de C)
Gradicut
Vel (0)00)0)))) (0)) Voguto, (0))
3g (Bule (V,, s0l)
vie (Bois lo (0.)0.))))
f411 fo.1 (4
5ro (6.2 Su.1f
Lipchitz Constan 42
2 7.20
E Ma faid
1 po
8g00 10
Gadiiet Bound
HS
fy.0 log hn
Convergence
log n + 6m))
D Some Other Examples of Biased Gradients with Control on Bias
In this section, we explore examples of applications using biased gradient estimators while having control over the bias.
D.1 Self-Normalized Importance Sampling
Let i be a probability measure on a measurable space (X, X).. The objective is to estimate ((f) = Eg [f]]] for a measurable function f X - IR such that (((f)) < oc. Assume that T(zz) oc w(z) A(dz), where is positive weight function and À is proposal probability distribution, and that A(w) = w(r))(dx) < co. For function f : X - Rd such that ((ff)) co, the identity
X(wf)
(ff)
(17)
X(w)
leads to the Self-Normalized Importance Sampling (SNIS) estimator:
N
w (X))
IN (xI:))
Σ wki (x*), wh
Σ w (Xe)
where X1:N (X1 XN) are independent draws from À and the w/y are called the normalized weights. 1 shows that the bias of the SNIS estimator can be expressed as:
E [ / (x1:N) π < S 1 (w²)
N X(w)²
This particular type of estimator can be found in the domain of Monte Carlo methods, particularly in the context of Bayesian inference and Sequential Monte Carlo methods.
D.2 Sequential Monte Carlo Methods
We focus here in the task of estimating the parameters, denoted as in Hidden Markov Models. In this context, the hidden Markov chain denoted by (Xx)e2o. The distribution of X, has density X with respect to the Lebesgue measure Jr and for all 2 O, the conditional distribution X given Xo.: has density mX,,,,,)). It is assumed that this state is partially observed through an observation process (YG)osETT. The observations You, are assumed to be independent conditionally on Xoxt and, for all 0 S t < T. the distribution of given Xo.: depends on X, only and has density ge (Xe,.) with respect to the Lebesgue measure. The joint distribution of hidden states and observations is given by
T-1
Po( Bo.r) x( (x0. yo)
II
ma Fe- (go 1144),
Our objective is to maximize the likelihood of the model:
Po (o(oor)) = f po (Zorr, Borr) dzorr.
34

---

To use gradient- based method for this maximization problem, we need to compute the gradient of the objective function. Under simple technical assumptions, by Fisher's identity.
Vo log (o(or))) = Vo log po (Noer, your ( (oorr d
Vo log po (Norr, yo:r
T
Σ
80,0 Ft+1)
where $1,0 (2, Vo Img az)) go (x,, ye+1)) for & 0 and by convention $0,0 (I, Vo log go (z, vo). Given that the gradient of the log-likelihone represents the smoothed expectation of additive functional, one may opt for Online Smoothing algorithms to mitigate computational costs. The estimation of the gradient V log (3(O)))) is given by:
Ha (yo:T) =
727
T,O
where { 1 are particle approximations obtained using particles ((tt, ) targeting the
filtering distribution cT, i.e. the conditional distribution of æt given y0:7. In the Forward-only implementation of FFBSm [20), the particle approximations (T+,0)i=1 are computed using the following formula, with initialization of TO for all i E [1,
T.1.8 E J=1 E 11t1) (7. s1 (i14) LEN.
The estimator of the gradient Hp (yo:r) computed by the Forward-only implementation of FFBSm is
biased. The bias and MSE of this estimator are of order O (1/N) [20]. where corresponds to the number of particles used to estimate it. Using alternative recursion methods compute { 1 N
results in different algorithms, such the particle-based rapid incremental smoother (PARIS) [64]
and its ascudo-margina extension [34] and Parisian particle Gibbs (PPG) [3]. In such cases, one
can also control the bias and MSE of the estimator.
D.3 Policy Gradient for Average Reward over Infinite Horizon
Consider finite Markov Decision Process (MDP) denoted as (S,A, R, P), where represents the state space, A denotes the action space, R S x A + [0, Rmax] is reward function, and P is the transition model. The agent's decision-making process characterized by a parametric family of policies {TO JeER, employing the soft-max parameterization. The reward function is given by:
V(#) == (ss.))=m [R(S, A)]
Σ
vs ())
(s.0)ESxA
where Ue represents the unique stationary distribution of the state-action Markov Chain sequence (s)))))) generated by the policy wa. Let X E (0, be discount factor and T be sufficiently large, the estimator of the gradient of the objective function V is given by:
Ho (81.T,AAT)) = R (Sr, AT) Σ N'v log ne (AT-;
where (Si:r, A1T)) (1,, AI.... ..... Sr, Ar) is realization of state-action sequence generated by the policy Tg. It's important to note that this gradient estimator is biased, and the bias is of order O(1
44
D.4 Zeroth-Order Gradient
Consider the problem minimizing the objective function V. The zeroth-order gradient method is particularly valuable in scenarios where direct access to the gradient of the objective function is
35

---

challenging or computationally expensive. The zeroth-order gradient oracle obtained by Gaussian smoothing [6] is given by:
Ha (X) V1O +X0+ V
X
(18)
7
where T >> is a smoothing parameter and X NO Ia) random Gaussian vector. 66 Lemma 3]
provide the bias of this estimator:
| Ho (X)) VV (0) S
2 T(d+
(19)
The application of these zeroth-order gradient methods can be found in generative adversarial networks 58 [6]
D.5
Compressed Stochastic Approximation: Coordinate Sampling
The coordinate descent method is based on the iteration:
0u+1 = 0n - 'n+1 Ho, (Xu+1) Ejn
where {ei,...,ea) is the canonical basis of id and He. (Xn+1); is the j-th coordinate of the gradient. The randomized coordinate selection rule chooses in uniformly from the set ( 2..,, .d.. Alternatively, the Gauss-Southwell selection rule [63] uses:
ja+1 argmax He, (Xn+1)şl.
jE(1....dd
This corresponds to a greedy selection procedure since each iteration we choose the coordinate with the largest directional derivative. Another approach to choosing jn. is Coordinate Sampling (53), variant of the stochastic gradient descent algorithm that incorporates selection step by sampling to perform random coordinate descent. The distribution of (n+1. which selects the coordinate, is characterized by the probability weights vector (wh wh.)) defined as:
(f) = P(Gu+1 = jlFa), j jE (1......] w n
This distribution of 10+1 is referred to as the coordinate sampling policy. The Stochastic Coordinate Gradient Descent algorithm is defined by:
p-- = 0, - 7n+1 1 D( (Xn+1).
where D(k) ekez Raxd has its entries equal to 0 except for the (k, k) entry, which is 1. Observe that the distribution of the random matrix D(G++1) fully characterized by the matrix
D, = E[D(((+1))FFnl where the diagonal terms characterize the probability weights for sampling each coordinate. These weights typically depend on preceding iterations and even on current gradients. In this case, we always have 8,-1 and control the minimum eigenvalue, we only require lower bound on the probability weights. This method can be easily extended to incorporate biased gradients and adaptive steps by introducing A, D2 An, where A,, represents the adaptive matrix as before, and D, the matrix of probability weights.
Diag(w?) (1) wn. (d)) In this context, A, represents a diagonal matrix D, .....
36

---

E Experiment details and supplementary results
E.1 Experiment with Synthetic Time-Dependent Bias
To illustrate Theorem 4.1 and the impact of bias, we consider in Figure simple least squares objective function (d) ||A0|| /2 in dimension d = 10. We artificially add to every gradient a zero-mean Gaussian noise with variance o² 0.01 and bias term 7n C,n at each iteration We use Adagrad with a learning rate = 1/2, 3 and = 0. Then, the bound of Theorem 4.
of the form (n 1/2 + n n)
100- 190--9871
258
Spoths
Figure 3: Value of V(0,)) V(0*) (on the left) and (0,) (on the right) with Adagrad for different values of nn n= and learning rate "n2 = n expected convergence rate Onn 1/1) for r = 1/4 and (nn1111))))) for 2 1/2.
1/2, 1/1 The dashed curve corresponds to the
We explore different values of r, E {1, 1/4 1/2 (L,,-114,,211//2
n- 00. where r, corresponds to constant bias, In = 0 for an unbiased gradient, and the others exhibit decreasing bias. First, note that the impact constant bias term (rn 1) on the risk and the norm of gradients never vanishes. From rn
rn n -1/2, the effect of the bias decreases until threshold is reached where there is no significant improvement. The convergence rate in the case Tn = n 1/2 is then the same as in the case without bias, illustrating the fact that in this case the dominating term comes from the learning rate.
E.2 Additional Experiments of IWAE
In this section, we provide detailed information about the experiments on CIFAR-10. We also conduct additional experiments on the FashionMNIST dataset. For all experiments, we use Adagrad, RMSProp, and Adam with a learning rate decay given by % = C./Vn. ni, where C, 0.01 for Adagrad and C.2- = 0.001 for RMSProp and Adam. The momentum parameters are set to P1 = 0.9 and P2 0.999, and the regularization parameter is fixed at 5 10-2 The impact of this regularization parameter will be illustrated later.
datasets: FashionMNIST (76 and CIFAR-10. The FashionMNIST dataset is a variant of MNIST and consists of 28x28 pixel images of various fashion items, with 60,000 images in the training set and 10,000 images the test CIFAR-10 consists of 32x32 pixel images categorized into 10 different classes. The dataset is divided into 60,000 images in the training set and 10,000 images in the test set.
Datasets. We conduct experiments
Models. For FaShionMNIST. we use a fully connected neural network with a single hidden layer consisting of 400 hidden units and ReLU activation functions for both the encoder and the decoder. The latent space dimension is set to 20. We use 256 images per iteration (235 iterations per epoch). Convolutional Neural Network (CNN) architecture with
For CIFAR-10 10 and CIFAR- 1000, we Convolutional layers and 2 fully connected layers with ReLU activation functions. The latent space dimension set to 100. For both datasets, use 256 images per iteration (196 iterations per epoch).
We estimate the log-likelihood using the VAE, IWAE, and BR-IWAE models, all which are trained for 100 epochs. Training is conducted using the SGD, SGD with momentum, Adagrad, RMSProp.
37

---

and Adam algorithms with decaying learning rate, mentioned before. For SGD, we employ the clipping method clip the gradients to prevent excessively large steps.
For this experiment, we set = samples in both IWAE and BR-IWAF, while restricting the maximum iteration of the MCMC algorithm to 5 and the burn-in period to 2 for BR-IWAE. For comparison, we estimate the Negative Log-Likelihood using these three models with SGD, SGD with momentum, Adagrad, RMSProp, and Adam, and the results are presented Table 3 case of CIFAR-IC 10, we observe that IWAE outperforms VAE, while BR-IWAE outperforms IWAE by reducing bias in all cases. The adaptive methods surpass SGD, and momentum further improves their performances. Consequently, Adam excels among all algorithms due to its adaptive steps and momentum.
Similar the
Table 3: Comparison Negative Log-Likelihood on the FashionMNIST Test Set (Lower is Better).
Algorithm
VAE
IWAE
BR-IWAE
SGD
247.2
244.9
244.0
SGD with momentum
244.6
240.2
238.4
Adagrad
245.8
241.4
240.5
RMSProp
242.6
239.3
237.8
Adam
240.3
237.8
236.
Similarly, as we did the case of CIFAR-10, we incorporate a time-dependent bias that decreases by choosing bias of order Onnaa) at iteration We vary the value of a for both MNSSi and CIFAR- 1000
1/4
275
== 1/
19/00/2
16"
245
28
2.5
24
23
Epecto
Figure 4: IWAE on the FashionMNIST Dataset with Adagrad for different values of a. Bold lines represent the mean 5 independent runs.
1/8
- 1/8
1/2
1/2
povz6.0 0
20--
100
25
66
100
Epochs
Epochs
Figure 5: IWAE on the FaSH Dataset with RMSProp for different values of a. Bold lines represent the mean over independent runs.
38

---

7.6
304
d- 1/2
2.7-
d- 1/2
Jovee.
2.3
244
100
25
80
300
Epochs
Epochs
Figure 6: IWAE on the FashionMNIST Dataset with Adam for different values of a. Bold lines represent the mean 5 independent runs.
All figures are plotted on a logarithmic scale for better visualization and with respect the number of epochs. The dashed curve corresponds the expected convergence rate Onn-1/4 for 1/8. and Ollog n/ vn) for a = 1 1/4, as well as for a = 1/2, just as the case CIFAR-10. We can clearly observe that for all cases, convergence is achieved when is sufficiently large. In the case of the FashionMNIST dataset, the bound seems tight, and the convergence rate of (/21 does not seem to be possible to reach, in contrast to the case of CIFAR-10 where the curves corresponding to = 1/4 and a = 1/2 approach O(n -1/2) convergence rate. For all figures, with a larger a, the convergence in both the squared gradient norm and negative log-likelihood occurs more rapidly.
Additional Experiments on CIFAR-10 Dataset.
a 1/8 (Adagrad)
1/4 (Adagrad)
1.975
a 1/2 (Adagrad)
a 1/8 (RMSProp)
Test loss (x10e3)
1.95
α 1/4 (RMSProp)
α 1/2 (RMSProp)
α 1/8 (Adam)
1.9
a 1/4 (Adam)
1/2 (Adam)
1.875
1.85
1.825
20
40
60
80
100
Epochs
Figure 7: Negative Log-Likelihoon on the test set on the CIFAR-10 10 Dataset for IWAE with Adagrad, RMSProp, and Adam. Bold lines represent the mean over independent runs.
The effect of C.,
Figure X iillustrates the convergence in both the squared gradient norm and the negative log- likelihood for C, 0,001 and C, = 0.01 in Adagrad. In the case of the squared gradient norm, we have only plotted the results for C., 0.001 for better visualization, and the plot for C,2 = 0.01 was already presented in Figure It is clear that when C, is set to 0.001, the convergence of the negative log-lite loglliillhood is slower. Similarly, the convergence the squared gradient norm for C, = 0.001 achieves convergence, but it is slower compared to the case of C2 0.01.
39

---

1/4
2-14 22000
--18,C--000
1-43
e=12 2,0202
5225
16
1.43
Epoore
Epecte
Figure 8: IWAE on the CIFAR-10 Dataset with Adagrad for different values of a and C.. Bold lines 5 independent runs.
represent the mean
The Impact of regularization parameter 8.
In Section A.7
discussed the impact of the regularization parameter 5 in Adam. It has been empirically observed that the performance of adaptive methods can be sensitive to the choice of this parameter. Here, illustrate the impact of this regularization parameter in IWAE, To achieve this, we plot the test loss for different sets of values for E {10 1,10 Figure 9
s, 10 10 -2 2,5 x 10 2 1011
2015
6 1e-08
146
8 1e-05
0.001
1.55
8 0.01
6 0.1
1.84
145
1.32
Figure 9: IWAE on the CIFAR-10 Dataset with Adam for different values of Lines represent the mean over independent runs.
Our experimental results align with prior work 77 Notably, we find that employing 6 5 x 10-2 yields improved performance in IWAE.
67 73 affirming the consistent impact of
The Impact of Bias over Time.
Our experiments illustrate the negative log- bog-likelihood with respect to epochs, and we observed that higher value of leads to faster convergence. The key point consider when tuming is that while convergence may be faster in terms of iterations, it may lead to higher computational costs. To illustrate this, set fixed time limit of 1000 seconds and tested different values of a, plotting the test loss as a function of time in Figure 10 It is clear that with a = 1/8, the convergence always slower, whereas choosing a 1/4 achieves faster convergence than a 1/2. While the difference may seem small here, with more complex models, the disparity becomes significant. Therefore, is essential tune the value of to attain fast convergence and reduce computational time.
In this paper, all simulations were conducted using the Nvidia Tesla T4 GPU. The total computing hours required for the results presented in this paper are estimated to be around 100 to 200 hours of GPU usage.
40

---

1.2
d-
1.44
d- 1/2
2075
d- 1/2
2.22
1.9
2.8
2475
288
1.5
200 600 663 800
1000
203
660
600
820
1300
Figure 10: Negative Log-Likelihood on the test set of the CIFAR-10 Dataset for IWAE with Adagrad (on the left) RMSProp (on the right) for Different Values of over time (in seconds). Bold lines represent the mean over 5 independent runs.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The paper's contributions are mentioned the abstract and clearly detailed in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: In our paper, we discuss the limitations our results. Furthermore, for each assumption, we also discuss where it can be verified and provide the limitations of these assumptions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution
41

---

is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faireess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The paper provides comprehensive set of assumptions with discussions, along with complete proofs for each theoretical result in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our work is primarily theoretical, and the experiments are conducted to illustrate our results. The paper provides detailed descriptions of the experimental setup, parameters, and methodologies, ensuring that the main results can be reproduced and verified.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (c.g., in the case
42

---

of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e-g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code supporting our experiments is available on GitHub, as referenced in the Experiments section. All data used in our study is publicly accessible (CIFAR dataset).
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
Sublic/guides httaa//ggiide//oeeeuiii..se
CoodeSuuuissioooolooio for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurIPS code and data submission guidelines (https www.oooaaummmssssoooooloooo
/ //nips.co ccc httee//ubllegggguieee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper provides comprehensive details the experimental setup, including hyperparameters, all optimizer algorithms, and other relevant algorithms with pseudo code, ensuring the reproducibility of the results.
Guidelines:
43

---

The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All algorithms used to illustrate the results are run times, and the mean and significance of all results are plotted, ensuring an appropriate representation of statistical significance.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
The paper provides detailed information on the computer resources required for all experiments, including the type of compute workers (CPU or GPU), and approximate time of execution.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
44

---

Question:
Does the research conducted in the paper conform, in every respect. with the
NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper aligns with the NeurlPS Code of Ethies, ensuring adherence to ethical guidelines throughout the study.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Given that the paper is primarily theoretical and the experiments are conducted solely for illustrative purposes, the work does not involve significant broader societal impacts to discuss. The focus of the paper is on theoretical contributions rather than practical applications with societal implications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper is theoretical and does not involve the release of data models that have high risk for misuse. Therefore, safeguards were necessary.
Guidelines:
The answer NA means that the paper poses such risks.
45

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
The paper does not use existing assets; therefore, no creators or original owners need to be credited, and no license terms of use need to be mentioned or respected.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not introduce new assets; therefore, there is no documentation provided alongside any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
46

---

The paper does not involve crowdsourcing experiments or research with human subjects, so there are no instructions provided participants or details about compensation.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does involve research with human subjects; thus, there are no potential risks, disclosure of risks, or IRB approvals to describe.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
47


Reviews:
[{"review_id": "n5clIjC2Zt", "reviewer": "Reviewer_ioBT", "summary": "The authors provide convergence guarantees for the biased adaptive stochastic approximation framework and establishes convergence to a critical point for non-convex setting of Adagrad type methods. The authors illustrate their results in the setting of IWAE.", "questions": "See the weakness section.", "limitations": "The authors should discuss in more details the types of considered data stream $(X_n)$ and its relations with H3.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Stated results for the rates of convergence of biased SA under Polyak-Łojasiewic condition are novel, yet the obtained rates are classical in the literature.", "weaknesses": "Checking assumption H3 in its current form is not obvious for different types of noise, since it involves taking expectation w.r.t. dynamics of the process $\\{\\theta_n\\}$ itself. With this assumption the proof of the main results is rather classical, following standard techniques in non-convex optimization. At the same time, it is not clear how H3 can be checked even for independent sequence $\\{X_n\\}$. Checking the same assumption for $\\{X_n\\}$ being a Markov chain is even more tricky due to correlations between $X_n$ and $\\theta_n$. It is typical that previous papers on the subject (see e.g. [Karimi et al, 2019]) state the assumptions, that do not involve expectations over $\\theta_n$. I suggest the authors to clarify H3 for independent/martingale/Markov noise separately and to clarify respective assumption (when $X_n$ is a Markov chain - probably in terms of mixing time of this sequence). Provided that my concerns regarding H3 are resolved, I will be happy to increase my score.\n\nAlso the bibliography can be complemented by the paper [Dorfman and Levy, 2022], where the authors consider adaptivity of Adagrad-type algorithms to mixing time. \n\nReferences:\n[Dorfman and Levy, 2022] Dorfman, R. and Levy, K.Y. Adapting to mixing time in stochastic optimization with markovian data. In International Conference on Machine Learning 2022, pp. 5429-5446. PMLR.\n[Karimi et al, 2019] Karimi, B., Miasojedow, B., Moulines, E. and Wai, H.T. Non-asymptotic analysis of biased stochastic approximation scheme. In Conference on Learning Theory, 2019, pp. 1944-1974.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback, we give below some clarifications concerning H3. The purpose of Assumption H3 is to provide a very general framework that covers all possible applications and adaptive algorithms. Since H3 $(ii)$ is a well-known assumption [20], we understand that your question concerns Assumption H3 $(i)$. \n\nWe would like to first stress that, with this assumption, the proofs of the main results (Theorems 4.1 and 4.2) still differ from that of biased SGD in the way in which we control the preconditioning matrix $A_n$. Furthermore, the application of these results to Adagrad and RMSProp, as well as the extension to Adam, are significantly different from the proof of biased SGD.\n\nMoreover, it is actually possible to verify Assumption H3 $(i)$ in many settings. It is important to keep in mind that this assumption is very general and depends on three quantities.\n\n- The type of adaptive algorithm (and therefore the form of the matrix $A_n$),\n- The application, that is, the gradient of the objective function $\\nabla V(\\cdot)$ and its empirical counterpart $H_{\\theta_{n}} \\left( \\cdot \\right)$,\n- The stochasticity of the sequence {$X_{n}, n \\in \\mathbb{N}$}.\n\nLet us first discuss the last point, which concerns the stochasticity of $X_{n}$. It is actually possible to avoid computing ``an expectation with respect to the dynamics of the process itself'', as mentioned in the review. Indeed, using the tower property, we have:\n$$\n\\mathbb{E}\\left[\\left\\langle\\nabla V\\left(\\theta_{n}\\right),A_{n}H_{\\theta_{n}}\\left(X_{n+1}\\right)\\right\\rangle\\right]=\\mathbb{E}\\left[ \\mathbb{E}\\left[\\left\\langle\\nabla V\\left(\\theta\\_{n}\\right),A\\_{n}H_{\\theta\\_{n}}\\left(X\\_{n+1}\\right)\\right\\rangle |\\mathcal{F}\\_{n}\\right]\\right],\n$$\nwhere $(\\mathcal{F}\\_{n})\\_{n\\geq 0}$ represents the filtration generated by the random variables $(\\theta\\_{0}, X_1, ..., X_n)$.\nThen, we need to verify that \n$$\n\\mathbb{E}\\left[\\left\\langle\\nabla V\\left(\\theta_{n}\\right),A_{n}H_{\\theta_{n}}\\left(X_{n+1}\\right)\\right\\rangle |\\mathcal{F}\\_{n}\\right]\\geq \\lambda_{n+1}\\left(||\\nabla V(\\theta_{n})||^{2}-r_{n+1}\\right).$$\nHere, the stochasticity depends only on $X_{n+1}$, and not on the dynamics of the process {$\\theta_{k}$}$_{k \\leq n}$.\n\nMoreover, we have shown that for Adagrad, Adam, and RMSProp (Corollary 4.5), a sufficient condition to verify H3$(i)$ is to bound the bias of the gradient, that is, to show that there exists $\\tilde b_{n+1}$ such that \n$$\n||\\mathbb{E}[H_{\\theta_{n}}(X_{n+1})\\mid\\mathcal{F}\\_{n}]-\\nabla V(\\theta_{n})||\\leq\\tilde b\\_{n+1}.\n$$\n\nThen, whatever the assumptions on stochasticity, that is, whether $X_n$ is i.i.d. (the noise as a Martingale difference) or a Markov Chain, the goal is simply to find $\\tilde b_n$. We have used this approach to verify H3$(i)$ for several applications such as Stochastic Bilevel Optimization and Conditional Stochastic Optimization (in which case, the sequence  {$X_{n}, n \\in \\mathbb{N}$} is arbitrary) or  Sequential Monte Carlo Methods, which corresponds to a Markov Chain case. This is discussed in Section 5.1 of the main paper and in Appendix C and D. \n\nHowever, we agree that this was not clear enough in the first version. We will use the extra page to clarify this point. To help the reader, we will give more details on the form of $\\tilde b_n$ in the i.i.d. and Markov cases, as detailed below.\n\n#### $\\textbf{I.I.D case}$\nLet us assume that {$X_{n}, n \\in \\mathbb{N}$}  is an i.i.d. sequence. If the mean field function (the conditional expectation of the gradient $h(\\theta_{n}) = \\mathbb{E}\\left[H_{\\theta_{n}}\\left(X_{n+1}\\right) \\mid \\mathcal{F}\\_{n}\\right]$) matches the gradient of the objective function, then there is no bias. Any bias arises from the difference between the mean field function and the true gradient of the objective function. \nIn this case, with $ \\tilde b_{n+1} = ||h(\\theta_n) - \\nabla V(\\theta_n)|| $, Assumption H3$(i)$ is verified.\n\n#### $\\textbf{Markov Chain case}$\nWe now assume that {$X_{n}, n \\in \\mathbb{N}$} is a Markov Chain. In this case, even if $h(\\theta) = \\nabla V(\\theta)$, there is an additional bias introduced by the Markov Chain's properties. Specifically, the total bias consists of two components: one due to the difference between the mean field function and the true gradient of the objective function, and the other due to the Markov Chain’s characteristics.\n\nWe define the stochastic update as:\n$$H_{\\theta_{k}}\\left(X_{k+1}\\right) = \\frac{1}{T} \\sum_{i=1}^{T} H_{\\theta_{k}}\\left(X_{k+1}^{(i)}\\right). $$\n\nWhen using $T$ samples per step to compute the gradient, if {$X_{n}, n \\in \\mathbb{N}$} is an ergodic Markov chain with stationary distribution $\\pi$ and $||h(\\theta_n) - \\nabla V(\\theta_n)||$ is bounded, Assumption H3$(i)$ is verified with $\\tilde b_{n+1} = ||h(\\theta_n) - \\nabla V(\\theta_n)|| + M \\sqrt{\\tau_{\\text{mix}}/T}$, where $h(\\theta) = \\int H_{\\theta}(x) \\pi(dx)$ and $\\tau_{\\text{mix}}$ is the mixing time defined in [78].\n    \nIf the general optimization problem reduces to the following stochastic optimization problem with Markov noise, as considered in most of the literature [77, 78, 79]:\n$$\n\\min_{\\theta \\in \\mathbb{R}^d} V(\\theta) := \\mathbb{E}\\_{x \\sim \\pi} [f(\\theta; x)], \n$$\nwhere $\\theta \\mapsto f(\\theta; x)$ is a loss function, and $\\pi$ is some stationary data distribution of the Markov Chain and $H_{\\theta_{k}}\\left(X_{k+1}^{(i)}\\right)=\\nabla f(\\theta_{k}; X_{k+1}^{(i)})$, then  $\\tilde b_{n+1}=M\\sqrt{\\tau_{\\text{mix}}/T}$, similar to SGD with Markov Noise [78].\n\n### $\\textbf{Convergence Results in Both Cases}$\nOnce we have the form of the bias of the gradient $\\tilde b_n$, we can determine the convergence rate for our theorems. For instance, the convergence rate in Theorem 4.1 becomes $\\mathcal{O}(n^{-\\gamma+2\\beta+\\lambda} + ||h(\\theta_n) - \\nabla V(\\theta_n)||^{2})$ for i.i.d case and $\\mathcal{O}(n^{-\\gamma+2\\beta+\\lambda} + ||h(\\theta_n) - \\nabla V(\\theta_n)||^{2} + M^2 \\tau_{\\text{mix}}/T)$ for Markov Chain case.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "EmT84g7wdt", "reviewer": "Reviewer_BcqM", "summary": "Stochastic and adaptive optimization algorithms are commonly used in advanced machine learning techniques. However, the analysis of non-convex optimization with biased gradients is lacking in the literature. This work considers the general scenario of optimizing machine learning objectives with practical optimizers given biased gradient estimators. Convergence bounds for different optimizers are proved with or without the Polyak-Łojasiewicz condition, and developed under an adaptive (preconditioning) matrix, which indicates the possibility of achieving the same convergence speed as with unbiased estimators by proper hyperparameter tuning.\n\nThe results are theoretically applied to bi-level optimization and others, empirically applied to importance weighted variational-autoencoder (IWAE) optimization. It is shown that the proved bounds apply to several applications. The experiments on Cifar-10 and FasionMNIST conclude that controlling the bias is beneficial to the convergence speed when the bias term dominates the optimizer term and the benefits become marginal after a certain threshold.", "questions": "The variational distribution q may also affect the convergence. In the experiments, is q fixed or trained? I think the analysis applies to fixed q, but would like to learn about assumptions and implementation details here.\n\nThe introduction also talked about Markov chain based optimization schemes, but the analysis later in the paper seems to be far from it. How is assumption H3 achieved in such case? How are the theorems connected to the Martingale and Markov chain cases?\n\nThe main analysis in the paper is limited to optimization with vanishing bias, which does not directly apply to some practical methods (e.g. relaxation with Gumbel-softmax/concrete distribution, variational sequential Monte Carlo that drops part of the gradient). Can you provide a useful bound when r_n is a (or only bounded by a) constant from Theorem 4.2?", "limitations": "I do not see a limitation section and it would be beneficial to sketch future works by discussing limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "My overall judgement of the work is quite positive from its logic flow. However, I am not able to check all the details of the proofs.\n\nThe paper performs theoretical analysis of a common issue that covers a wide range of settings. Early in the paper, the background and application of adaptive stochastic approximation are established, which includes commonly used optimizers like SGD, Adagrad, RMSProp and Adam. The theoretical part is thorough with hyperparameters and different assumption groups, which is quite general. The most important assumption in the paper bounds the bias of the gradient, which also seems reasonable. \n\nThe settings of the IWAE experiment are not realistic, since an increasing number of samples are assumed during optimization. However, it can be viewed as a verification instead of an application of the bounds. As commented by the authors, the experiments with FasionMNIST indicate that the proved bound may be tight. The combination of theoretical and empirical evidences makes the paper strong.", "weaknesses": "Despite having wide applications, the experiments only include one case that verifies the proved bounds. The paper spent some efforts in bi-level optimization, but did not provide empirical analysis. IWAE has a remote connection to bi-level optimization when q is flexible enough, which could be utilized with a different optimization scheduling. \n\nminor: line 135, there seems to be a redundant factor of 1/2 for $r_{n+1}$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive and thoughtful review and the opportunity to clarify our contributions.\n\n$\\textcolor{blue}{\\textbf{Link Between IWAE and Bilevel Optimization}}$\n\nWe agree that assuming an increasing number of samples during optimization in IWAE is unrealistic; it is used merely to illustrate our convergence results. In our experiments, we have illustrated our results in the PL case using an artificial example (see Appendix E.1). To avoid oversimplification, we also train the variational distribution $q$ rather than keeping it fixed. In this context, we are also in a biased gradient case, which is more aligned with Stochastic Bilevel Optimization.\nAs you noted, there is indeed a connection between IWAE and bilevel optimization.\nThe problem of VAE can be considered a Stochastic Bilevel Optimization problem, given by:\n$$\\min_\\theta V(\\theta)=\\mathbb{E}\\_\\pi[\\log p_\\theta(x)]=\\mathcal{L}(\\theta,\\phi^*(\\theta)) + \\mathbb{E}\\_\\pi[\\text{D}\\_{KL}(q\\_{\\phi^*(\\theta)}(z|x)||p\\_\\theta(z|x))]$$\nsubject to\n$$\\phi^*(\\theta)\\in\\arg\\min_\\phi\\mathcal{L}(\\theta,\\phi).$$\nAdditionally, the IWAE problem can also be interpreted as Conditional Stochastic Optimization by setting $f$ to correspond to the identity function and $g_z((\\theta,\\phi),x)=\\log p_\\theta(x,z)/q_\\phi(z|x)$ in Eq (14).\nAll discussions on the link between IWAE and Stochastic Bilevel Optimization, as well as Conditional Stochastic Optimization IWAE, will be added in the experiments section. Additional details on the model configuration will be included in Appendix E in the revised paper.\n\n$\\textcolor{blue}{\\textbf{Discussion about the Martingale and Markov Chain Cases}}$\n\nAs you mentioned in your comments, the purpose of Assumption H3 is to provide a very general framework that covers all possible applications and adaptive algorithms. In many cases, $X_n$ is i.i.d. (noise as a Martingale difference) or forms a Markov Chain.\nFor IWAE, this applies to the Martingale case, but we also provide examples of applications involving the Markov Chain case, such as Sequential Monte Carlo Methods discussed in Appendix D.2.\n\nSince H3$(i)$ involves both the preconditioning matrix and the objective function, providing a necessary and sufficient condition in a general setting is challenging. However, we have shown that for Adagrad, Adam, and RMSProp (Corollary 4.5), a sufficient condition to verify H3$(i)$ is to bound the bias of the gradient, that is, to show that there exists $\\tilde b_{n+1}$ such that \n$$||\\mathbb{E}[H_{\\theta_n}(X_{n+1})\\mid\\mathcal{F}\\_n]-\\nabla V(\\theta_n)||\\leq\\tilde b\\_{n+1}.$$\nWhether $X_n$ is i.i.d. or a Markov Chain, the goal is simply to find $\\tilde b_n$. We have used this approach to verify H3$(i)$ for several applications, such as Stochastic Bilevel Optimization and Conditional Stochastic Optimization, which are discussed in Section 5.1 and Appendix C.\nFollowing also the comments of Reviewer ioBT, we provide the form of $\\tilde b_n$ for both the i.i.d. and Markov cases.\n\n### $\\textbf{I.I.D case}$\nLet us assume that {$X_{n}, n \\in \\mathbb{N}$}  is an i.i.d. sequence. If the mean field function (the conditional expectation of the gradient $h(\\theta_n)=\\mathbb{E}[H_{\\theta_n}(X_{n+1})\\mid\\mathcal{F}\\_n]$) matches the gradient of the objective function, then there is no bias. Any bias arises from the difference between the mean field function and the true gradient of the objective function. \nIn this case, with $\\tilde b_{n+1}=||h(\\theta_n)-\\nabla V(\\theta_n)||$, Assumption H3$(i)$ is verified.\n\n### $\\textbf{Markov Chain case}$\nWe now assume that {$X_{n}, n \\in \\mathbb{N}$} is a Markov Chain. In this case, even if $h(\\theta) = \\nabla V(\\theta)$, there is an additional bias introduced by the Markov Chain's properties. Specifically, the total bias consists of two components: one due to the difference between the mean field function and the true gradient of the objective function, and the other due to the Markov Chain’s characteristics.\nWe define the stochastic update as:\n$$H_{\\theta_{k}}\\left(X_{k+1}\\right)=\\frac{1}{T}\\sum_{i=1}^{T}H_{\\theta_k}\\left(X_{k+1}^{(i)}\\right).$$\nWhen using $T$ samples per step to compute the gradient, if {$X_{n}, n \\in \\mathbb{N}$} is an ergodic Markov chain with stationary distribution $\\pi$ and $||h(\\theta_n)-\\nabla V(\\theta_n)||$ is bounded, Assumption H3$(i)$ is verified with $\\tilde b_{n+1}=||h(\\theta_n)-\\nabla V(\\theta_n)||+M\\sqrt{\\tau_\\text{mix}/T}$, where $h(\\theta)=\\int H_{\\theta}(x)\\pi(dx)$ and $\\tau_\\text{mix}$ is the mixing time.\n    \nIf the general optimization problem reduces to the following stochastic optimization problem with Markov noise, as considered in most of the literature [77, 78, 79]:\n$$\\min_{\\theta\\in\\mathbb{R}^d}V(\\theta):=\\mathbb{E}\\_{x\\sim\\pi}[f(\\theta;x)], $$\nwhere $\\theta\\mapsto f(\\theta;x)$ is a loss function, and $\\pi$ is some stationary data distribution of the Markov Chain and $H_{\\theta_k}(X_{k+1}^{(i)})=\\nabla f(\\theta_k;X_{k+1}^{(i)})$, then $\\tilde b_{n+1}=M\\sqrt{\\tau_\\text{mix}/T}$, similar to SGD with Markov Noise [78].\n\n### $\\textbf{Convergence Results in Both Cases}$\nOnce we have the form of the bias of the gradient $\\tilde b_n$, we can determine the convergence rate for our theorems. For instance, the convergence rate in Theorem 4.1 becomes $\\mathcal{O}(n^{-\\gamma+2\\beta+\\lambda}+||h(\\theta_n)-\\nabla V(\\theta_n)||^{2})$ for i.i.d case and $\\mathcal{O}(n^{-\\gamma+2\\beta+\\lambda}+||h(\\theta_n)-\\nabla V(\\theta_n)||^{2}+M^2\\tau_{\\text{mix}}/T)$ for Markov Chain case.\n\n$\\textcolor{blue}{\\textbf{The Case with Constant Bias}}$\n\nIn fact, our analysis also applies to scenarios with a constant bias. For example, if the additive bias term $r_n$ is bounded by a constant $a$, the convergence rate becomes $\\mathcal{O}(\\log n/\\sqrt{n}+a)$. To ensure that $\\mathbb{E}\\left[||\\nabla V(\\theta_{n})||^{2}\\right]\\leq\\varepsilon$ for some $\\varepsilon > 0$, the constant $a$ must be less than $\\varepsilon$. Otherwise, this constant bias will adversely affect the convergence.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "uytZycC2fs", "reviewer": "Reviewer_aKkE", "summary": "This paper studies the non-asymptotic convergence guarantees of SGD with adaptive step sizes and (time-dependent) biased gradient estimators for nonconvex smooth functions. Applications to AdaGrad, RMSProp and Adam are developed. Numerical experiments on bilevel and conditional stochastic optimization, as well as deep VAE are used to illustrate the established theoretical results.", "questions": "Sometimes “adaptive step sizes” is referred to as “adaptive steps” in the paper. I guess using “adaptive step sizes” for all instances will avoid possible confusion. Can you also address the above point in weaknesses?", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work considers the biased gradient setting, which is away from the standard unbiased gradient setting like most standard results in the literature. This work also considers a more recently relaxed assumption on the gradient variance called “expected smoothness”, which makes the analysis even more general.", "weaknesses": "The bounded spectrum assumption of $A_n$ might not hold for every optimizer considered, and it remains to see how to relax it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive and thoughtful comments.\n\nWe have changed \"adaptive steps\" to \"adaptive step sizes\" in the revised paper.\n\nIn Theorems 4.1 and 4.2, since the exact form of $A_n$ is unknown (as we aim to cover all adaptive algorithms), we must assume certain properties about the preconditioning matrix, specifically the bound on its eigenvalues (H4). However, when applied to algorithms such as Adagrad, RMSProp, and Adam, we have shown that this assumption holds.\nIt can be challenging to verify this assumption for some other algorithms, such as Stochastic Newton.\nAs discussed after Assumption H4, the truncation method can be used for $A_{n}$ as done in [32]. \nThe truncation method involves replacing the random matrices $\\tilde{A}\\_n = \\min${$||A\\_n||,\\beta\\_{n+1}$}$A\\_n/||A\\_n||$). It is also stated that truncation is only used with very low probability, which means that the estimators $A_{n}$ are minimally affected by these truncations [32]. Since we choose $\\beta_{n+1}$, we have control over the convergence rate. \n\nAlthough controlling the minimal eigenvalue is not strictly necessary, ensuring the boundedness of the gradient is generally sufficient to control this quantity in algorithms such as Adagrad, RMSProp, and Adam. Further details on controlling the minimum and maximum eigenvalues are provided in line 566 for Adagrad and line 572 for RMSProp. For Adam, the control is the same as for RMSProp since both use the same preconditioning matrix $A_n$.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "H2irXYQ2VS", "reviewer": "Reviewer_1qy9", "summary": "This paper proposes non-asymptotic convergence guarantuees on several gradient-based optimization methods, ranging from the SGD to AdaGrad-like methods, when the estimation of the gradients is biased. More specifically, the convergence results include a theorem with the Polyak-Lojasiewicz condition and another one without the PL condition, both in a non-convex smooth setting.", "questions": "How limitating are hypotheses H1-5? It is difficult to check when the proposed models fulfill them.", "limitations": "-", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "# Originality\n\nThis paper studies a problem that is not yet broadly dealt with. \n\n# Clarity\n\nThis paper is easy to read and the statements are clear.\n\n# Significance\n\nThe setup of the provided convergence results include non-convex smooth settings, which are very common in ML.\n\n# Quality\n\nOverall, the theoretical results are sound and the proofs are easy to read (and seem to involve only classical techniques).\n\nThe experimental section provides examples where the estimation is naturally biased, which helps to evaluate the significance of the results.", "weaknesses": "# Signifiance\n\nHow limitating are hypotheses H1-5? It is difficult to check when the proposed models fulfill them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive and thoughtful comments.\n\nThere are three types of hypotheses discussed: those concerning only the adaptive algorithm, those concerning only the application (objective function), and those concerning both. These assumptions are discussed in the paper, but we will provide more detailed comments in the revised version.\n\n-  Assumption H4 [10, 32] relates only to the adaptive algorithm. We have shown that it can be verified in Adagrad, RMSprop, and Adam. For other algorithms where verification is difficult, we can use the truncation method described after this assumption.\n    The truncation method involves replacing the random matrices $\\tilde{A}\\_n = \\min${$||A\\_n||,\\beta\\_{n+1}$}$A\\_n/||A\\_n||$). It is also stated that truncation is only used with very low probability, which means that the estimators $A_{n}$ are minimally affected by these truncations [32]. Since we choose $\\beta_{n+1}$, we have control over the convergence rate. \n\n- Assumption H1 relates to the Polyak-Łojasiewicz (PL) condition. We provide convergence rates with and without this condition.  This assumption is weaker than strong convexity and remains satisfied even when the function is non-convex. Note that it has been studied theoretically [42] and has been verified empirically in many applications, such as in deep networks [24] and for Linear Quadratic Regulator [26].\n\n- Assumption H2 is crucial for obtaining the convergence rate [9, 56]. This assumption can be restricted to the generalized smoothness condition [80]. Since we assume the boundedness of gradients (H4), the smoothness and generalized smoothness are equivalent. Assumption H4 is standard in adaptive algorithms [18, 64, 70, 71] and, in practice, can be satisfied by clipping the gradient.\n\n- Assumption H3 is the only assumption that relates to both the adaptive algorithm and the objective function. H3$(ii)$ is a relaxed assumption on the gradient variance, referred to as “expected smoothness” [20], as mentioned in our paper and noted by reviewer aKkE.\n    Since H3$(i)$ involves the preconditioning matrix and the objective function, providing a necessary and sufficient condition in a general setting is challenging.\n    However, we have shown that for Adagrad, Adam, and RMSProp (Corollary 4.5), a sufficient condition to verify H3$(i)$ is to bound the bias of the gradient, that is, to show that there exists $\\tilde b_{n+1}$ such that \n$$||\\mathbb{E}[H_{\\theta_n}(X_{n+1})\\mid\\mathcal{F}\\_n]-\\nabla V(\\theta_n)||\\leq\\tilde b\\_{n+1}.$$\n    Applications, where this sufficient condition can be verified, are listed in Appendices C and D. We also refer reviewer ioBT to see how to verify H3$(i)$.\n\nFurthermore, we have demonstrated that our framework is applicable to numerous scenarios, including Bilevel Optimization and Conditional Stochastic Optimization, where all these assumptions are verified.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "DwRxH9vAs1", "reviewer": "Reviewer_3iVV", "summary": "This paper aims to analyze SGD with biased gradients in a non-asymptotic manner, where the steps  are also adaptive. In particular, under certain assumptions and conditions, it provides convergence guarantees and establishes convergence rates for a critical point of non-convex smooth functions for various adaptive methods.  \n\nOverall, I think the theoretical results of this paper are interesting and insightful.", "questions": "- Please see the weaknesses part.\n\n- In addition, although I understand that the settings considered in this paper are novel, there are already a lot of works in closely related topics. Does there exist any technical difficulty that cannot be solved by techniques from previous works? If it does, what are the technical difficulties compared to previous works?", "limitations": "The authors have adequately addressed the limitations in the main part of the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper is well-organized and clearly written. In particular, it well demonstrates the motivation of the study in the introduction and accurately compares its contributions with previous related works. All the theorems and the corresponding set of assumptions are concretely presented. In addition, the structures of proofs in the Appendix are also clear and easy to follow.\n\n- The proposed methods are general in the sense that it not only covers the adaptive step sizes (e.g., Adam) but also applies to the biased gradient, making it a comprehensive and interesting work in the direction of analyzing non-asymptotic convergence guarantees for variants of SGD. \n\n- The numerical experiments for IWAE and BR-IWAE are comprehensive and well support the theoretical claims.", "weaknesses": "One thing unclear to me is the role of parameters that are related to sampling noise (e.g. batch size) in the theorems. These parameters are supposed to be crucial since they are actually closely related to the training process and generalization. How do theorems in this paper characterize the effects of such parameters (other than some simple bounds from the assumptions)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive and thoughtful review and the opportunity to clarify our contributions.\n\n- In our framework, the gradient is computed using a single sample, as is common in many theoretical results. However, this can easily be extended to account for batch size. In such a case, instead of having $\\sigma^2$ (variance noise), $\\sigma^2$ would be scaled by the batch size.  \nFor instance, denoting as $B_k$ the batch size at iteration $k$, the convergence rate in Theorem 4.2 transforms into the following:\n$$\n\\mathbb{E}\\left[\\left\\| \\nabla V\\left(\\theta_{R}\\right)\\right\\|^{2}\\right] \\leq 2\\frac{\\mathbb{E}[V(\\theta_{0}) - V(\\theta^{*})] + \\sum_{k=0}^{n} w_{k+1} \\delta_{k+1} \\sigma_{k}^2 / B_{k}  + \\sum_{k=0}^{n} w_{k+1} \\gamma_{k+1} \\lambda_{k+1} r_{k+1} }{\\sum_{j=0}^{n} w_{j+1} \\gamma_{j+1} \\lambda_{j+1}}. \n$$\nHere, we observe that taking a large $B_k$ leads to a smaller second term in the convergence rate (the reduction of the variance). \nIt is well-known that increasing the batch size leads to faster convergence but also increases computation time. Therefore, a balance must be struck between batch size and computational efficiency. These comments will be added in the revised version of the paper.\n\n\n- Most of the existing literature on biased SA focuses on SGD with biased gradients, assuming a constant bias throughout the iterations. Only a few studies address biased gradients with adaptive steps, and these typically focus on the scalar version of Adagrad with strong assumptions.\nFor instance, [3] studied convergence results for biased gradients with Adagrad in the Markov chain case, focusing on the norm of the gradient of the Moreau envelope while assuming the boundedness of the objective function.\nIn contrast, our work provides convergence rates in a broader and more general setting that encompasses various applications and adaptive algorithms. One of the key challenges addressed in our work is the need to manage the preconditioning matrix effectively.\nA significant technical difficulty in this context arises from the term $\\mathbb{E} \\left[ \\left\\langle \\nabla V \\left( \\theta_{n} \\right), A_{n}H_{\\theta_{n}} \\left( X_{n+1} \\right) \\right\\rangle \\mid \\mathcal{F}\\_{n} \\right]$, where the stochasticity depends on $X_{n+1}$, which is part of the biased gradient estimator $H_{\\theta_{n}} \\left( X_{n+1} \\right)$, as well as the preconditioning matrix $A_n$. To address this challenge, Assumption H3$(i)$ was introduced.\nFurthermore, we have shown that for Adagrad, Adam, and RMSProp (Corollary 4.5), a sufficient condition to verify H3$(i)$ is to bound the bias of the gradient, that is, to show that there exists $\\tilde b_{n+1}$ such that \n$$||\\mathbb{E}[H_{\\theta_n}(X_{n+1})\\mid\\mathcal{F}\\_n]-\\nabla V(\\theta_n)||\\leq\\tilde b\\_{n+1}.$$\nCompared to existing convergence rates for Adagrad with biased gradients, our approach is notable for its weaker assumptions and its coverage of both the scalar and diagonal versions of Adagrad. Additionally, it introduces novel results for other algorithms, such as RMSProp and Adam.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "N0VdOBGDNA", "reviewer": "Reviewer_nF8X", "summary": "This paper studied convergence rate of general adaptive stochastic approximation with biased gradient. This is an important field since only biased gradient is accessible in many practical machine learning problem. The authors establied non-asymptotic bound based on various assumption, some of which are quite strong.", "questions": "In Theorem 4.2, what does $\\delta_j$ stand for? Does it correspond to $\\delta$ in eq (4)? What is the dependence of $\\delta$ in the final convergence rate of Adagrad and other algorithms?", "limitations": "The limitations are pointed out in the weakness part.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The authors provided convergence analysis of general biasd adaptive optimization method, and applied their results to popular adaptive algorithms including Adagrad, RMSProp and AMSGrad. They also mentioned various practical machine learning problems suffering from biased gradient. Extensive numerical experiments were conducted to verify the theoretical rate.", "weaknesses": "1. The techinque is not novel compared with existing works on biased SGD, e.g. [1]. The authors directly impose an upper and lower bound of preconditioning matrix in H3, in which case the analysis is not very different from that of SGD. A better way is to establish the boundedness of preconditioning matrix along the tracjectory as in e.g., [2], instead of taking it as prior assumption.\n\n2. The authors claimed that they analyzed Adam throught out the paper, but in fact they only did AMSGRAD. This is misleading since they are two totally different algorithms with distinct practical performance. I suggest the authors correct this point.\n\n### Typos:\n\nline 230: $\\mathcal{O}(n^{-1/4})$->$\\mathcal{O}(\\log n/n^{1/2})$\n\n[1] Liu, Yin, and Sam Davanloo Tajbakhsh. \"Adaptive stochastic optimization algorithms for problems with biased oracles.\" arXiv preprint arXiv:2306.07810 (2023).\n\n[2] Li, Haochuan, Alexander Rakhlin, and Ali Jadbabaie. \"Convergence of adam under relaxed assumptions.\" Advances in Neural Information Processing Systems 36 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments.\n\nIt is true that the stochastic optimization literature is very rich and is the focus of a great deal of research activity.  For instance, the work proposed in [81] focuses on the theoretical analysis of stochastic optimization problems with biased gradients.\nFirst of all, the proof for adaptive biased SA differs from that of biased SGD in how we control the preconditioning matrix. The adaptivity mentioned in [81] refers to how the authors update the gradient, not to the adaptive steps used in Adagrad, RMSProp, and Adam. The title was even changed since the first submission by removing \"Adaptive\". \nFurthermore, our results for Adagrad and RMSProp in Section 4.3, as well as the extension to Adam in Section 4.4, provide new theoretical bounds for adaptive optimization algorithms widely used in machine leaning. Their proofs are significantly different from the sketch proof of biased SGD. \n\nIn Theorems 4.1 and 4.2, since the exact form of $A_n$ is unknown (as we aim to encompass all adaptive algorithms), we must assume certain properties about the preconditioning matrix, specifically the bound of its eigenvalues (H4). However, when applied to algorithms such as Adagrad, RMSProp, and Adam (AMSGRAD), we have demonstrated that this assumption holds.\nIn [82], they only consider the convergence results of Adam in an unbiased setting, which means they do not need to make assumptions about the preconditioning matrix. The assumption on the preconditioning matrix in our case is only for the general case. The convergence results for AMSGRAD with biased gradients do not take the boundedness of the preconditioning matrix into account.\n\nWe believe that the originality of the contribution of the paper is that we cover adaptive step sizes applied to the biased gradient setting with relaxed assumptions (for instance expected smoothness) as supported for instance by Reviewer aKkE and Reviewer 3iVV.\n\n$\\textbf{The authors claimed that they analyzed Adam throught out the paper, ... I suggest the authors correct this point.}$\n\n- Since AMSGRAD is a minor modification of Adam and is not as well known as Adam, we believed it makes more sense to refer to Adam. Even in packages like PyTorch and TensorFlow, Adam has an option \"AMSGRAD\" to use this algorithm. The difference between these two algorithms is already mentioned in lines 221-225 of Section 4.4 of the paper. Furthermore, [64] highlights the convergence difficulties of Adam while proposing AMSGRAD. \nHowever, we have revised the paper to address this point and clarify the distinction between the two algorithms.\n\n$\\textbf{In Theorem 4.2, what does $\\delta_{j}$ stand for? ...}$\n\n- In Theorem 4.2, $\\delta_{j}$ is defined as $\\delta_{j} = L\\gamma_{j}^{2}\\beta_{j}^{2} /2$. This notation is introduced to simplify the terms in the convergence rate analysis, and $\\delta$ represents the regularization parameter.\nRegarding the final convergence rate, there is a term $\\log \\left( 1 + \\frac{nM^2}{\\delta}\\right) / \\sqrt{n}$, which is asymptotically similar to $\\log n / \\sqrt{n}$. \n\n$\\textbf{The authors establied non-asymptotic bound based on various assumption, some of which are quite strong.}$\n \n- As the other assumptions are classical in the literature, we set the focus more on H3 and H4.\nAs discussed after Assumption H3, it is shown to be a minimal requirement for achieving the convergence rate in adaptive SA (see also [20]).\nAssumption H4 [10, 32] relates to the adaptive algorithm. We have shown that it can be verified in Adagrad, RMSprop, and Adam. For other algorithms where verification is difficult, we can use the truncation method described after this assumption.\nThe truncation method involves replacing the random matrices $\\tilde{A}\\_n = \\min${$||A\\_n||,\\beta\\_{n+1}$}$A\\_n/||A\\_n||$). It is also stated that truncation is only used with very low probability, which means that the estimators $A_{n}$ are minimally affected by these truncations [32]. Since we choose $\\beta_{n+1}$, we have control over the convergence rate. \nWe provided additional comments on the assumptions for instance to Reviewer 1qy9.\n\n$\\textbf{line 230: $\\mathcal{O}\\left(n^{-1/4}\\right) \\rightarrow \\mathcal{O}\\left(\\log n / \\sqrt{n} \\right)$}$\n\n- If the additive bias $b_n$ in the convergence rate is of order $\\mathcal{O}\\left(\\log n / \\sqrt{n} \\right)$, we achieve a convergence rate of $\\mathcal{O}\\left(\\log n / \\sqrt{n} \\right)$. However, in line 230, we want to state that if the bias of the gradient estimator is of order $\\mathcal{O}\\left(n^{-1/4}\\right)$ (since $r_{n+1}$ represents an additive bias term, generally of the order of the square of the bias of the gradient estimator, as mentioned after H3), then we achieve a convergence rate of $\\mathcal{O}\\left(\\log n / \\sqrt{n} \\right)$.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to express our gratitude to the reviewers for their helpful reviews and constructive feedback, which have helped us further improve our paper. Below, we provide a common response to comments made by several reviewers, followed by our point-by-point responses addressing all the specific concerns. Please note that all reference numbers correspond to those in the original paper, with any new references listed below.

Here are some comments on our results in the Martingale and Markov Chain cases, as requested by some reviewers. We provide below the convergence results for both the Martingale and Markov Chain cases. First, we want to highlight that our framework is more general and encompasses all possible applications and adaptive algorithms. In many cases, the data $X_n$ is i.i.d. (with noise as a Martingale difference) or forms a Markov Chain.

### $\textbf{Obtaining the form of the bias}$

We provide the bound $\tilde b_n$ of the gradient estimator $|| \mathbb{E}[H_{\theta_{n}}(X_{n+1}) \mid \mathcal{F}\_{n} ] - \nabla V(\theta_{n}) ||$ for both the i.i.d. and Markov cases.

#### $\textbf{I.I.D case}$
Let us assume that {$X_{n}, n \in \mathbb{N}$}  is an i.i.d. sequence. If the mean field function (the conditional expectation of the gradient $h(\theta_{n}) = \mathbb{E}\left[H_{\theta_{n}}\left(X_{n+1}\right) \mid \mathcal{F}\_{n}\right]$) matches the gradient of the objective function, then there is no bias. Any bias arises from the difference between the mean field function and the true gradient of the objective function. 
In this case, $ \tilde b_{n+1} = ||h(\theta_n) - \nabla V(\theta_n)|| $.

#### $\textbf{Markov Chain case}$
We now assume that {$X_{n}, n \in \mathbb{N}$} is a Markov Chain. In this case, even if $h(\theta) = \nabla V(\theta)$, there is an additional bias introduced by the properties of the Markov Chain. Specifically, the total bias consists of two components: one due to the difference between the mean field function and the true gradient of the objective function, and the other due to the characteristics of the Markov Chain.

We define the stochastic update as:
$$H_{\theta_{k}}\left(X_{k+1}\right) = \frac{1}{T} \sum_{i=1}^{T} H_{\theta_{k}}\left(X_{k+1}^{(i)}\right). $$

When using $T$ samples per step to compute the gradient, if {$X_{n}, n \in \mathbb{N}$} is an ergodic Markov chain with stationary distribution $\pi$ and $||h(\theta_n) - \nabla V(\theta_n)||$ is bounded, then $\tilde b_{n+1} = ||h(\theta_n) - \nabla V(\theta_n)|| + M \sqrt{\tau_{\text{mix}}/T}$, where $h(\theta) = \int H_{\theta}(x) \pi(dx)$ and $\tau_{\text{mix}}$ is the mixing time defined below..
    
If the general optimization problem reduces to the following stochastic optimization problem with Markov noise, as considered in most of the literature [77, 78, 79]:
$$
\min_{\theta \in \mathbb{R}^d} V(\theta) := \mathbb{E}\_{x \sim \pi} [f(\theta; x)], 
$$
where $\theta \mapsto f(\theta; x)$ is a loss function, and $\pi$ is some stationary data distribution of the Markov Chain and $H_{\theta_{k}}\left(X_{k+1}^{(i)}\right)=\nabla f(\theta_{k}; X_{k+1}^{(i)})$, then  $\tilde b_{n+1}=M\sqrt{\tau_{\text{mix}}/T}$, similar to SGD with Markov Noise [78].

### $\textbf{Convergence Results in Both Cases}$
Once we have the form of the bias of the gradient $\tilde b_n$, we can determine the convergence rate for our theorems. For instance, the convergence rate in Theorem 4.1 becomes $\mathcal{O}(n^{-\gamma+2\beta+\lambda} + ||h(\theta_n) - \nabla V(\theta_n)||^{2})$ for i.i.d case and $\mathcal{O}(n^{-\gamma+2\beta+\lambda} + ||h(\theta_n) - \nabla V(\theta_n)||^{2} + M^2 \tau_{\text{mix}}/T)$ for Markov Chain case.

- The mixing time $\tau_{\text{mix}}$ of a Markov chain with stationary distribution $\pi$ and transition kernel $P$ is defined as
$
\tau_{\text{mix}} := \inf $ { $t : \sup_{x} D_{\text{TV}}(P^t(x, \cdot), \pi) \leq \frac{1}{4}$},
where $D\_{\text{TV}}$ denotes the total variation distance.

[77] John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael I Jordan. Ergodic mirror descent. SIAM Journal on Optimization, 22(4):1549–1578, 2012.

[78] Ron Dorfman and Kfir Yehuda Levy. Adapting to mixing time in stochastic optimization with markovian data.
In International Conference on Machine Learning, pages 5429–5446. PMLR, 2022.

[79] Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric
Moulines. First order methods with markovian noise: from acceleration to variational inequalities. In Advances
in Neural Information Processing Systems, volume 36, 2024.

[80] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: a theoretical justification for adaptivity. In International Conference on Learning Representations, 2020. 

[81] Yin Liu and Sam Davanloo Tajbakhsh. Adaptive stochastic optimization algorithms for problems with biased
oracles. arXiv preprint arXiv:2306.07810, 2023.

[82] Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of adam under relaxed assumptions. Advances
in Neural Information Processing Systems, 36, 2024.

Meta-review: This paper studies the convergence rate for a set of biased adaptive stochastic estimations (e.g., Adagrad, RmsProp), which is different from the prior works on the unbiased estimations. Most reviewers acknowledge the theoretical contributions of this paper and suggest acceptance. The authors should take the reviewers' comments (especially Reviewer nF8X) into consideration in the revision.
Decision: Accept (poster)