Thank you for your comments.

It 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. First 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". Furthermore, 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.

In 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. In [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.

We 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.

$**The authors claimed that they analyzed Adam throught out the paper, ... I suggest the authors correct this point.**$

• 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. However, we have revised the paper to address this point and clarify the distinction between the two algorithms.

$**In Theorem 4.2, what does$\delta_{j** stand for? ...}

• 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. Regarding 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}$.

$**The authors establied non-asymptotic bound based on various assumption, some of which are quite strong.**$

• As the other assumptions are classical in the literature, we set the focus more on H3 and H4. As discussed after Assumption H3, it is shown to be a minimal requirement for achieving the convergence rate in adaptive SA (see also [20]). Assumption 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. 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. We provided additional comments on the assumptions for instance to Reviewer 1qy9.

$**line 230:$\mathcal{O**\left(n^{-1/4}\right) \rightarrow \mathcal{O}\left(\log n / \sqrt{n} \right)}

• 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)$.

Thank you for your positive and thoughtful review and the opportunity to clarify our contributions.

• 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.
  For instance, denoting as $B_k$ the batch size at iteration $k$, the convergence rate in Theorem 4.2 transforms into the following:

Here, we observe that taking a large $B_k$ leads to a smaller second term in the convergence rate (the reduction of the variance). It 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.

• 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. For 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. In 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. A 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. Furthermore, 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 $||\mathbb{E}[H_{\theta_n}(X_{n+1})\mid\mathcal{F}\_n]-\nabla V(\theta_n)||\leq\tilde b\_{n+1}.$ Compared 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.

Thank you for your positive and thoughtful comments.

There 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.

• 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. 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.

• 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].

• 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.

• 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. Since H3$(i)$ involves 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 $||\mathbb{E}[H_{\theta_n}(X_{n+1})\mid\mathcal{F}\_n]-\nabla V(\theta_n)||\leq\tilde b\_{n+1}.$ 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)$.

Furthermore, we have demonstrated that our framework is applicable to numerous scenarios, including Bilevel Optimization and Conditional Stochastic Optimization, where all these assumptions are verified.

Thank you for your positive and thoughtful comments.

We have changed "adaptive steps" to "adaptive step sizes" in the revised paper.

In 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. It can be challenging to verify this assumption for some other algorithms, such as Stochastic Newton. As discussed after Assumption H4, the truncation method can be used for $A_{n}$ as done in [32]. 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.

Although 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$.

Thank you for your positive and thoughtful review and the opportunity to clarify our contributions.

$\textcolor{blue}{**Link Between IWAE and Bilevel Optimization**}$

We 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. As you noted, there is indeed a connection between IWAE and bilevel optimization. The problem of VAE can be considered a Stochastic Bilevel Optimization problem, given by: $\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))]$ subject to $\phi^*(\theta)\in\arg\min_\phi\mathcal{L}(\theta,\phi).$ Additionally, 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). All 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.

$\textcolor{blue}{**Discussion about the Martingale and Markov Chain Cases**}$

As 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. For 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.

Since 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 $||\mathbb{E}[H_{\theta_n}(X_{n+1})\mid\mathcal{F}\_n]-\nabla V(\theta_n)||\leq\tilde b\_{n+1}.$ Whether $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. Following also the comments of Reviewer ioBT, we provide the form of $\tilde b_n$ for both the i.i.d. and Markov cases.

$**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}[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. In this case, with $\tilde b_{n+1}=||h(\theta_n)-\nabla V(\theta_n)||$, Assumption H3$(i)$ is verified.

$**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 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. 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, 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.

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}(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].

$**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.

$\textcolor{blue}{**The Case with Constant Bias**}$

In 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.

Thank you for the rebuttal which addresses my questions. After reading the other reviews and responses, I do not have any additional concerns.

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)$.

We 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.

Moreover, 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.

• The type of adaptive algorithm (and therefore the form of the matrix $A_n$),
• The application, that is, the gradient of the objective function $\nabla V(\cdot)$ and its empirical counterpart $H_{\theta_{n}} \left( \cdot \right)$,
• The stochasticity of the sequence {$X_{n}, n \in \mathbb{N}$}.

Let 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:

where $(\mathcal{F}\_{n})\_{n\geq 0}$ represents the filtration generated by the random variables $(\theta\_{0}, X_1, ..., X_n)$. Then, we need to verify that

||\mathbb{E}[H_{\theta_{n}}(X_{n+1})\mid\mathcal{F}_{n}]-\nabla V(\theta_{n})||\leq\tilde b_{n+1}.

\min_{\theta \in \mathbb{R}^d} V(\theta) := \mathbb{E}_{x \sim \pi} [f(\theta; x)],