Investigating Variance Definitions for Stochastic Mirror Descent with Relative Smoothness

Thank you for your review, we discuss your two main points below.

Diminishing step-sizes: One would have to characterize some kind of average variance indeed. Yet, when $\sigma^2_\eta$ converges for small $\eta$ (Proposition 2.6), one can expect to obtain bounds of the form $\sigma^2_\eta \leq R^2$ for $\eta \leq \eta_0$, with $R^2_0 >0$ only dependent on $\eta_0$. This is for instance the case in our application. Therefore, while case-by-case bounds on the average variance are required, there are strong reasons to believe that these will generally hold.

As a complement, diminishing step-size results are direct adaptations of the results in Section 3. The result in Section 4 actually relies on using diminishing step-sizes. In particular, the equivalent of Theorem 3.1 would write:

$

\eta_t \left[ \mathbb{E} f_{\eta_t}(x^{(t)}) - f_{\eta_t}^*\right] +\mathbb{E} D_h(x_\star, x^{(t+1)}) \leq \prod_{k=0}^t(1 - \eta_k \mu) D_h(x_\star, x^{(0)}) + \sum_{k=0}^t \eta_k^2  \prod_{\ell=k}^t (1 - \eta_\ell \mu) \sigma_{\star, \eta_\ell}^2. 

$

The convex result (adaptation of Theorem 3.3) would write:

$

\frac{1}{T+1}\sum_{k=0}^t \eta_k \mathbb{E}\left[f_{\eta_k}(x) - f_{\eta_k}^* + D_f(x_\star, x^{(k)})\right] \leq \frac{D_h(x_\star, x^{(0)})}{T+1} + \frac{1}{T+1}\sum_{k=0}^t \eta_k^2 \sigma^2_{\star, \eta_k}. 

$

Generalization to multivariate Gaussian distributions: Thank you for bringing out this point. We did not initially tackle the multivariate case since the unidimensional one already contained all the complexity of handling stochasticity with mirror descent. Yet, the multivariate can also be tackled with our approach by replacing quantities with their natural multidimensional equivalents (and in particualr $\log$ by $\log {\rm det}$).

More precisely, the log-partition function writes up to constants:

$

A(\theta) = - \frac{1}{2}\log{\rm det}(\Sigma^{-1}) + \frac{1}{2} m^\top \Sigma^{-1} m = - \frac{1}{2}\log\det(- 2\theta_2) - \frac{\theta_1^\top \theta_2^{-1} \theta_1}{4},

$

where $\theta_1 = \Sigma^{-1} m$, and $\theta_2 = - \Sigma^{-1} /2$. From there, performing similar derivations, function $f_\eta$ writes:

$

f_\eta(\theta) = \frac{d}{2\eta}(\eta + \log(1 - \eta)) + \frac{1}{2\eta} \mathbb{E} \log \det \left(I + \eta \Sigma^{-1} (m - x)(m - x)^\top\right) - \frac{1}{2}\log \det (\Sigma^{-1}),

$

which is a direct transcription of what we had in the unidimensional case. From here, differentiating the above objective implies that the minimizer is $m_\eta = m_\star$ (as in the unidimensional case), and

$

\frac{1}{\eta} \mathbb{E}\left[\left(\Sigma_\eta + \eta (m_\star - x)(m_\star - x)^\top\right)^{-1} \Sigma_\eta - I \right] + I = 0.

$

Writing $X = \Sigma_\eta^{-1/2} (x - m_\star) \sim \mathcal{N}(0, \Sigma_\eta^{-1} \Sigma_\star)$, the previous expression writes:

$

\mathbb{E}\left[ (I + \eta XX^\top)^{-1} XX^\top \right] = I,

$

so in particular since $XX^\top$ is a rank-1 matrix, we can write:

$

\mathbb{E}\left[ \frac{XX^\top}{1 + \eta \|X\|^2} \right] = I.

$

This implies that the covariance of $X$ is isotropic, so $\Sigma_\eta^{-1} \Sigma_\star = \alpha I$ for some $\alpha > 0$.

Taking the trace of this expression, we obtain

$

d = \mathbb{E}\left[ \frac{\alpha Z}{1 + \eta \alpha Z}\right],

$

where $Z$ is a chi-squared distribution with parameter $d$. Since $x \mapsto x / (1 + \eta x)$ is a concave function, we can apply Jensen inequality and obtain:

$

d \leq \frac{\alpha d}{1 + \eta \alpha d}.

$

In particular, this leads to

$

\Sigma_\eta \geq (1 - \eta d) \Sigma_\star.

$

Note that this is actually tighter than our 1d bound, which we can also improve in a similar way by just using Jensen on the same function in Equation (81) (instead of the other bound).

Now that we have a bound on $\Sigma_\eta$, we can (similarly to the 1d case) substitute it into

$

f_\eta(\theta_\eta) - f(\theta_\star) = \frac{1}{2} \log \det \left( \Sigma_\star^{-1} \Sigma_\eta\right) + \frac{1}{2\eta} \mathbb{E} \log \det \left((1 - \eta)\Sigma_\eta^{-1} \left[\Sigma_\eta + \eta (m_\eta - X)(m_\eta - X)^\top \right]\right).

$

At this point, we use that $\log \det (A) \geq {\rm Tr}(I - A^{-1})$, so $\log \det (I + B) \geq Tr(I - (I + B)^{-1}) = Tr((I + B)^{-1} B)$, which is the multidimensional version of the $\log(1 + x) \geq x / (1 + x)$ that we use to obtain (89). Following similar derivations, we also obtain that the expectation of the log term is greater than 0, and we are left with:

$

\sigma_{\star, \eta}^2 \leq - \frac{1}{2\eta} \log \det \left( \Sigma_\star^{-1} \Sigma_\eta\right) \geq - \frac{d}{\eta} \log (1 - \eta d). 

$

In the end, plugging everything, we obtain a $\tilde{O}\left(\frac{d^2}{n}\right)$ convergence result for the map with $n_0 > d$ independent samples (or actually anything that makes the prior full rank, and the condition $\eta \leq 1/d$). This is consistent with Appendix A.3 [17]. We write the result with a $\tilde{O}$ notation (that includes log factors) but they are non-asymptotic, similarly to the 1d case.

In short, while the result are presented in the 1d case, no additional conceptual steps are required to tackle the d-dimensional one. We presented the main differences with the 1d proof in this rebuttal, and will make sure to add the full d-dimensional results to a revision of the paper.

Another main application of our bounds are Poisson inverse problems: $D_{KL}(b, Ax)$, which are often solved using (stochastic) mirror descent and for which theoretical results are limited.

We hope that we answered your question in a satisfying way, and are open to any further discussions.

Thank you for your review.

We agree with you that the minima are not the same, and this is actually a crucial point in the paper, otherwise we would directly obtain that $\sigma^2_\eta = \frac{1}{\eta}^2 \mathbb{E}D_h(x_\star, x_\star^+)$, which is not true. Yet, this holds asymptotically, as we show in Proposition 2.6.

We are not sure which Proposition 2 you are referring to, but we never use the identity that you mention at the end of your summary in our proofs. In Proposition 2.2, we simply bound $f_\eta$ in terms of another function, but everything remains within the $\min$. We would be glad to detail any result you might be wondering about.

We hope that you will reconsider your score in light of this answer, and would otherwise be happy to answer any other concern you might have.

Thank you for your review and careful comments, we will make sure to fix all points you raised in the next revision.

Before we start the point-by-point answer, we kindly ask you whether you could provide references for non-asymptotic rates on $D_f(\theta_\star, \theta)$ (since they probably do not exist for $f_\eta(\theta^{(n)})$, as we introduce this quantity). As a matter of fact, we do not only give non-asymptotic results on $D_f(\theta_\star, \theta^{(n)})$, but anytime results (for all $n$ such that it is finite). These results can then be converted on results for $D_f(\theta^{(n)}, \theta_\star)$ for $n$ large enough using similar arguments than in Le Priol et. al. (2021) (essentially, that Bregman divergences are close to quadratics when their arguments are close enough). Although we do not bound $f(\theta) - f(\theta_\star)$, we are not aware of equivalent results in the literature. However, we are not experts in Gaussian MAP estimation and would gladly compare to any reference you may provide.

Please find the answers to your questions below:

1 - The set C is not necessarily compact. The minimum should thus be an infimum and can potentially be $-\infty$ at this point if the $f_\xi$ are not lower bounded (Corollary 2.3 ensures finiteness). Yet, the assumptions of Corollary 2.3 are not necessary to ensure finiteness.

2 - $x_\star$ is the solution to Problem (1), defined in Def 2 as the point such that $f(x_\star) = f^*$, where $f^*$ is the infimum of $f$, but we will define it more explicitly. We did not want to make its existence a blanket assumption since $\sigma_{\star, \eta}^2$ does not require $x_\star$ to exist, and neither do Theorems 3.1 and 3.3 (where the $D_h(x_\star, y)$ terms can be replaced by $\lim_{n\rightarrow \infty} D_h(u_n, y)$ for any sequence $u_n$ such that $f(u_n) \rightarrow f^\star$), since we do not use any property of $x_\star$ other than the fact that it's involved in defining $\sigma_{\star, \eta}$, which actually just involves $f^\star$. We used $x_\star$ here to facilitate reading.

Yet, other works we compare to [7, 19] assume it exists, so we make this assumption to have comparable results in terms of interpretation. Similarly, when $x_\star$ exists, our variance definition has a nice interpretation in terms of ``gradients at optimum'' (Proposition 2.6). Similarly, assuming existence of $x_\star$ (and that it belongs to ${\rm int} C$) allows for a natural interpretation of $D_f(x_\star, x)$ in terms of 'gradient norm' (Proposition 3.4). To avoid any confusion, we will make existence of $x_\star$ a blanket assumption for convenience, and discuss case-by-case where it can be relaxed.

3 - Thank you for spotting this indexing issue.

4 - Regarding your update: We respectfully disagree with your statement on several aspects:

• relative strong convexity is not stronger that strong convexity. For instance if $h(x) = -\log x$, $f(x) = h(x) + g(x)$ where $g(x) = a x$ for instance for some $a >0$ (but could also be another convex function), then $f$ is strongly convex relatively to $h$ but not strongly convex in the usual sense.
• The fact that the control is not on $f(x^{(k)}) - f^\star$ is explicitly and clearly mentioned right after Theorem 3.3.
• The results of Theorem 3.3 are meaningful, they are simply not function value results (see Proposition 3.4 and Proposition 2.5). It is an open question to know whether $f(x^{(k)}) - f(x_\star)$ can actually be bounded when using stochastic mirror descent without strong(er) assumptions on the variance (such as the ones we compare to in Section 2 or in Appendix D). The fact that we obtain convergence in terms of $f(x)$ in the deterministic case can be considered as an artifact of the deterministic setting, and we can recover it with our analysis: it corresponds to proving a result analog to Corollary 3.2 but for the convex setting, and in this case $E[f_\xi((x^{(k)})^+)] = f(x^{(k+1)})$. In the stochastic setting this simplification does not happen, and so we are 'stuck' with bounding either $f_\eta(x^{(k)})$ or $E[f_\xi((x^{(k)})^+)]$. Finally, note that Dragomir et. al. (2021) obtain even weaker results in the convex setting, since they do not bound $f_\eta(x^{(k)})$, and Hanzely and Richtarik (2021) use a definition that is comparably strong to the one discussed in Appendix D.

In the end, we fully agree with you that convergence of function values directly would be appreciated. Unfortunately, it simply does not seem to be achievable in our setting.

5 - Is it possible to consider other non-Gaussian/non-conjugate models? Non-Gaussian models can be considered, as in this case Proposition 4.1 still applies for exponential families (as highlighted by Reviewer 35cP). However, several properties of the Gaussian distribution are used when bounding the variance, and so this work would have to be done again on a distribution-specific basis.

For non-conjugate models, it would first be necessary to express the updates as resulting from stochastic mirror descent steps, which might be done in a case-by-case basis but maybe not in full generality.

We hope that we have answered your concerns with the desired clarifications and that you will go back to your more positive evaluation. We are available for further discussion if this is not the case.

Thank your for your careful review and suggestions. We will change MLE to MAP in the abstract and remove the 'strong' adjective, which refered to the fact that we obtain similar guarantees for SMD as what we have in the `usual' setting for SGD, and was not specifically aimed at the statistical setting indeed.

Control over the course of iterations: The sentence `we might be able to exploit this control over the course of iterations' refers to the fact that the convergence result in Section 4 completely discards the fact that we not only bound $D_A(\theta_\star, \theta^{(n)})$ but also $f_{\eta_n}(\theta^{(n)}) - f_{\eta_n}(\theta_{\eta_n})$. It might be possible to exploit the bound on $f_{\eta_n}(\theta^{(n)}) - f_{\eta_n}(\theta_{\eta_n})$ to obtain one on $D_A(\theta^{(n)}, \theta_\star)$, instead of wanting to obtain it from $D_A(\theta_\star, \theta^{(n)})$ for $\theta^{(n)} \approx \theta_\star$. Yet, we have not been able to leverage this control in a satisfying way, and so this sentence is more to be understood as an open question (and the fact that we control another metric related to the desired one). We will make this clearer to avoid confusions.

Component-wise convexity: This assumption is mostly used in Proposition 2.7 to use Bregman cocoercivity with the $f_\xi$ to compare with the results of Dragomir et. al., which require it (so we require it as well to compare to their definition). Our other results do not require convexity of $f_\xi$ directly, but we do use the fact that each $D_{f_\xi}$ is relatively smooth. We will discuss this more clearly.

Questions:

1. This sentence refers to the variance expression of Line 191-192, which can be infinite in general, but is finite if $h$ is strongly convex (in the usual, not relative sense), since in this case the eigenvalues of $\nabla^2 h^*(u)$ are bounded uniformly in $u$.

2. The proof is not in Appendix B indeed, sorry for this. As sketched in the main text, we write that in this case, $\sigma^2_{\star, \eta} \leq \frac{f(x_\star) - f(x) + \frac{\eta}{2} \mathbb{E}\|\nabla f_\xi(x)\|^2}{\eta}$. Then, we use that $\frac{1}{2}\|\nabla f_\xi(x)\|^2 \leq \| \nabla f_\xi(x) - \nabla f_\xi(x_\star)\|^2 + \|\nabla f_\xi(x_\star)\|^2 \leq 2L D_{f_\xi}(x, x_\star) + \|\nabla f_\xi(x_\star)\|^2$, using cocoercivity of $f_\xi$ (which requires individual convexity of the $f_\xi$). Then, applying expectations, we have $\mathbb{E} \left[2\eta L D_{f_\xi}(x, x_\star)\right] = 2 \eta L D_f(x, x_\star) = 2\eta L \left[ f(x) - f(x_\star)\right]$, so that $\sigma^2_{\star, \eta} \leq \frac{(2\eta L - 1)}{\eta}\left[f(x) - f(x_\star)\right] + \mathbb{E}{\|\nabla f_\xi(x_\star)\|^2}$, leading to the desired result. This requires $\eta \leq 1/(2L)$, similarly to the Euclidean proof that uses this definition.

3. Finiteness is to be understood for a fixed $\eta$, which is already non-trivial due to the supremum on $x$. The precise reference in [19] is Assumption 2.1, and the difference is that this does not include the $1/\eta$ factor. As a result, the RHS of their Theorem 3.1 does not go to 0 as $\eta \rightarrow 0$. They study an adaptive step-size setting, but they would still get a non-vanishing RHS with constant step-size (making it go to 0) or vanishing step-sizes. Instead, $\eta \sigma^2_{\star, \eta}$ vanishes for $\eta \rightarrow 0$, ensuring that $D_h(x_\star, x^{(t)})$ can be arbitrarily close to 0 with enough steps and small enough step-sizes (which is not the case in [19]).

4. Clarifying non-standard: How meaningful this is very much depends on the applications. The guarantee on $f_\eta$ is meaningful in the sense that $f_\eta \rightarrow f$ for $\eta \rightarrow 0$ (Proposition 2.5). The result on $D_f(x_\star, x)$ can be seen on a control on the gradients of $f$, for instance through Proposition 3.4. Finally, $D_f(x_\star, x) \approx D_f(x, x_\star)$ if $x \approx x_\star$. Please note that existing results with relaxed variance assumptions (such as Dragomir et. al. (2021)), also only obtain convergence on $D_f(x_\star, x)$ in the convex case. The 'non-standard' aspect is with respect to usual results on gradient descent.

5. Thank you for your suggestion, we will add a remark on this aspect in the paper.

6. $R^*_- = \{ u \in R, u < 0 \}$.

Thank you again for your many suggestions and comments, we hope that our results are clearer to you now and that you are willing to increase your score. We will gladly discuss any further question more in details.

We would like to thank you for your detailed review, understand your concerns, and clarify these points below.

Questions 1 and 2: From what we understand from your review, most concerns come from the `minimal assumptions on $h$' remark from lines 278-283. We realize that this remark can be confusing indeed as to the assumptions on $h$ that are necessary.

Our intention was to emphasize the fact that Theorem 3.1 and Theorem 3.3 (and only these two results, as you point out) are mainly algebraic manipulations that explicit convergence in terms of relevant quantities. In particular, they only require assumptions on the iterates (in the form of Eq. (3)) because their goal is to express how quantities evolve from one iteration to the other. In fact, you can notice that the only inequality used in the proof of Theorem 3.1 is relative strong convexity. We also note that chaining (10) to obtain (6) requires $1 - \eta \mu \geq 0$, and so the condition $\eta \leq 1/\mu$, which we will make sure to add to Theorem 3.1 (we initially presented the theorems with the one-step versions (Eq 10) and then changed to (6)). Similarly, Theorem 3.3 requires $D_h(x_\star, y)$ to be positive for all $y$, and would otherwise include a $D_h(x_\star, x_{t})$ term.

However, the fact that such minimal assumptions are required to write the derivations leading to Theorem 3.1 does not imply non-trivial results on $D_h(x_\star, x^{(t)})$. In particular several quantities involved in Theorem 3.1 can potentially be infinite. (6) still holds, but potentially with $f_\eta^\star = -\infty$ or $D_h(x_\star, x^{(0)}) = +\infty$. Finiteness can be obtained in different ways, such as using the general results given in Section 2, or using problem-specific bounds when these do not apply, as is done in Section 4.

We understand that this can introduce confusion and we will highlight it very clearly. You are right that Assumption 1 is needed in general for some results in Section 3 (not the theorems though, but we agree that it can easily be read as `all results', which was not intended), which is why we present it as a blanket assumption.

The `minimal assumption on $h$' was more intended to encourage readers to adapt inequalities such as (10) even for problems that do not satisfy the blanket assumption, if bounds on the various terms can be ensured in other ways. This is what we do for instance in Section 4 (in which just Eq. (10) is used, and $f_\eta^\star$ is bounded directly). We will rephrase it in that way and make sure to make this point extremely clear.

Note that most of the Appendix is actually devoted to deriving results in Section 2 and Section 4. For Theorem 3.1. for instance we only prove Lemma C.1 with a very direct (and we believe verifiable) proof, which we encourage you to take a look at.

Question 3: Thank you for your suggestion of writing Proposition 4.1 for exponential families more genrerally, we will make sure to add this to the paper.

Question 4: Thank you for your remark, the L2 norm examples are more intended to give readers elements of comparison with more familiar expressions, we will add "unconstrained" explcitly in Line 175 since this is indeed the setting we had in mind. The (mirror) constrained case in which a projection term is added to (3) is discussed in Appendix E, though not tackled in full details.

We thank you again for your feedback and are open to suggestions in order to better convey our message from the remark that the inequality holds under very mild assumptions, but results such as the ones derived in Section 2 are necessary to make the result meaningful in general.

We hope we have lifted your doubts about correctness of the paper, and otherwise encourage you to take a look at the proof of Lemma C.1, or ask us to clarify any other concern you might have.