Investigating Variance Definitions for Stochastic Mirror Descent with Relative Smoothness

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 12:04:11

Abstract: Mirror Descent is a popular algorithm, that extends Gradients Descent (GD) beyond the Euclidean geometry. One of its benefits is to enable strong convergence guarantees through smooth-like analyses, even for objectives with exploding or vanishing curvature. This is achieved through the introduction of the notion of relative smoothness, which holds in many of the common use-cases of Mirror descent. While basic deterministic results extend well to the relative setting, most existing stochastic analyses require additional assumptions on the mirror, such as strong convexity (in the usual sense), to ensure bounded variance. In this work, we revisit Stochastic Mirror Descent (SMD) proofs in the (relatively-strongly-) convex and relatively-smooth setting, and introduce a new (less restrictive) definition of variance which can generally be bounded (globally) under mild regularity assumptions. We then investigate this notion in more details, and show that it naturally leads to strong convergence guarantees for stochastic mirror descent. Finally, we leverage this new analysis to obtain convergence guarantees for the Maximum A Posteriori estimator of a Gaussian with unknown mean and variance.

Main paper: 
 introduction: 
 The central problem of this paper is to solve optimization problems of the following form:EQUATIONwhere C is a closed convex subset of R d , and f ξ are differentiable convex functions (stochasticity is on the variable ξ). The problems that we will consider typically arise from machine-learning use-cases, meaning that the dimension d can be very large. Therefore, first-order methods are popular for solving these problems, since they usually scale well with the dimension.In standard machine learning setups, computing a gradient of f is very costly (or even impossible), since it requires computing gradients for all individual examples in the dataset. Yet, gradients of f ξ are relatively cheap, and arbitrarily high precisions are generally not required. This makes Stochastic Gradient Descent (SGD) the method of choice [4] . Using a step-size η > 0, the SGD update from point x ∈ R d can be written as x + SGD = arg min u∈C η∇f ξ (x) ⊤ u + 1 2 ∥u -x∥ 2 .While the standard Euclidean geometry leading to Gradient Descent (GD) fits many use-cases quite well, several applications are better solved with Mirror Descent (MD), a generalization of GD which allows to better capture the geometry of the problem. For instance, the Kullback-Leibler divergence might be better suited to discriminating between probability distributions than the (squared) Euclidean norm, and this is something that one can leverage using MD with entropy as a mirror. As a matter of fact, many standard algorithms can be interpreted as MD, i.e., as generalized first-order methods. This is for instance the case in statistics, where Expectation Minimization and Maximum A Posteriori Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.estimators can be interpreted as running MD with specific mirror and step-sizes [15, 17] . Mirror descent can also be used to solve Poisson inverse problems, which have many applications in astronomy and medicine [3] , to reduce the communication cost of distributed algorithms [24, 12] ,or to solve convex quartic problems [6] . In the online learning community as well, many standard algorithms such as Exponential Weight Updates or Follow-The-Regularized-Leader can be interpreted as running mirror descent [21, 13] . There are still many open questions regarding the convergence guarantees for most of the algorithms mentioned above. Therefore, progress on the understanding of MD can lead to a plethora of results on these applications, and more generally to a more consistent theory for Majorization-Minimization algorithms. This paper is a stepping stone in this direction.Let us now introduce the mirror map, or potential function h, together with the Bregman divergence with respect to h, which is defined for x, y ∈ dom h as D h (x, y) = h(x)-h(y)-∇h(y) ⊤ (x-y). We now introduce the Stochastic Mirror Descent (SMD) update, which can be found in its deterministic form in, e.g., Nemirovskij and Yudin [22] . SMD consists in replacing the squared Euclidean norm from the SGD update by the Bregman divergence with respect to the mirror map h:x + (η, ξ) = arg minEQUATIONNote that since D ∥•∥ 2 (x, y) = ∥x -y∥ 2 , one can recover SGD by taking h = 1 2 ∥ • ∥ 2 . In this sense, SMD can be viewed as standard SGD, but changing the way distances are computed, and so the geometry of the problem. Yet, this change significantly complicates the convergence analysis of the method, since the Bregman divergence, in general: (i) does not satisfy the triangular inequality, (ii) is not symmetric, (iii) is not translation-invariant, (iv) is not convex in its second argument.This means that analyzing mirror descent methods requires quite some care, and that many standard (S)GD results do not extend to the mirror setting. For instance, one can prove that mirror descent cannot be accelerated in general [8] . Similarly, applying techniques such as variance-reduction requires additional assumptions [7] . To ensure that x + (η, ξ) exists and is unique, we first make the following blanket assumption throughout the paper:Assumption 1. Function h : R d → R ∪ {∞} is twice continuously differentiable and strictly convex on C. For every y ∈ R d , the problem min x∈C h(x) -x ⊤ y has a unique solution, which lies in int C, and all f ξ are convex.Note that the regularity assumption on h could be relaxed, as discussed in Section 3, but we choose a rather strong one to make sure all the objects we will manipulate are well-defined. Interestingly, while mirror descent changes the way distances are computed to move away from the Euclidean geometry, standard analyses of mirror descent methods, and in particular in the online learning community, still require strong convexity and Lipschitz continuity with respect to norms [5, Chapter 4] . It is only recently that a relative smoothness assumption was introduced to study mirror descent [2, 20] ,together with the corresponding relative strong convexity.Definition 1. The function f is said to be L-relatively smooth and µ-relatively strongly convex with respect to h if for all x, y ∈ C: µD h (x, y) ≤ D f (x, y) ≤ LD h (x, y). To lighten notation, we will omit the dependence on h and simply write that f is L-rel.-smooth unless clearly specified.Definition 1 extends the standard smooth and strongly convex assumptions that correspond to the case h = 1 2 ∥ • ∥ 2 , so that for all x ∈ C, ∇ 2 h(x) = I the identity matrix. These assumptions allow MD analyses to generalize standard GD analyses, and in particular to obtain similar linear and sublinear rates, with constant step-size and conditions adapted to the relative assumptions.While the basic deterministic setting is now well-understood under relative assumptions, a good understanding of the stochastic setting remains elusive. In particular, as we will see in more details in the related work section, all existing proofs somehow require the mirror h to be globally strongly convex with respect to a norm, or have non-vanishing variance. The only case that can be analyzed tightly is under interpolation (there exists a point that minimizes all stochastic functions), or when using Coordinate Descent instead of SMD [10, 11] . This is a major weakness, as the goal of relative smoothness is precisely to avoid comparisons to norms. Indeed, even when these "absolute" regularity assumptions hold, the smoothness and strong convexity constants are typically very loose, and the theory is not representative of the observed behaviour of the algorithms.However, as hinted at earlier, this was expected: acceleration is notoriously hard to achieve for mirror descent (and even impossible in general [8] ), and variance reduction typically encounters the same problems [7] . For stochastic updates, this comes from the fact that it is impossible to disentangle the stochastic gradient from the effect of the curvature of h at the point at which it is applied.Contribution and outline. The main contribution of this paper is to introduce a new analysis for mirror descent, with a variance notion which is provably bounded under mild regularity assumptions:typically, the same as those required for the deterministic case. We introduce our new variance notion, and compare it with standard ones from the literature in Section 2. This new analysis is both simpler and tighter than existing ones, as shown in Section 3. Finally, we use our results to analyse the convergence of the Maximum Likelihood and Maximum A Posteriori estimators for a Gaussian with unknown mean and variance in Section 4, and show that it is the first generic stochastic mirror descent analysis that obtains meaningful finite-time convergence guarantees in this case.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: We have theorems for all the results we claim to have in the abstract.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 be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
variance assumptions: 
 We now focus on the various variance assumptions under which Stochastic Mirror Descent is analyzed.Some manipulations require technical lemmas, such as the duality property of the Bregman divergence or the Bregman co-coercivity lemma, which can be found in Appendix A.We start by introducing our variance definition, prove a few good properties for it, and then compare it with the existing ones to highlight their shortcomings. The two key properties we would like to ensure (and which are not satisfied by other definitions) are: (i) boundedness without strong convexity of h or restricting the SMD iterates, and (ii) finiteness for η → 0 (with the appropriate scaling).Let η > 0, and recall that x + (η, ξ) is the result of a SMD step from x using function f ξ with step-size η (Equation ( 2)). From now on, when clear from the context, we will simply denote this point x + .Yet, although the dependence is now implicit, do keep in mind that x + is a stochastic quantity that is not independent from ξ nor η, as this is critical in most results. Under Assumption 1, x + writes:EQUATIONSimilarly, we denote by x + the deterministic Mirror Descent update, which is such that ∇h(x + ) = ∇h(x) -η∇f (x). We also introduce h * : y → arg max x∈C x ⊤ y -h(x) the convex conjugate of h, which verifies ∇h * (∇h(x)) = x. Let us now define the key functionEQUATIONDefinition 2. We define the variance of the stochastic mirror descent iterates given by (2) asσ 2 ⋆,η = 1 η sup x∈C (f (x ⋆ ) -f η (x)) = f ⋆ -f ⋆ η η, where f ⋆ and f ⋆ η are respectively the inf. of f and f η .We now state various bounds on σ 2 ⋆,η , to help understand its behaviour. We start by positivity, which is an essential property that justifies the square in the definition.Proposition 2.1 (Positivity). For all η > 0, σ ⋆,η ≥ 0.This result follows from f η (x) ≤ f (x), since D h (x, x + ) ≥ 0 for all x ∈ C by convexity of h.Stochastic functions after a step. We first upper bound σ 2 ⋆,η directly in terms of f ξ .Proposition 2.2. If f ξ is L-rel.-smooth and η ≤ 1/L, then σ 2 ⋆,η ≤ 1 η (f (x ⋆ ) -min x∈C E [f ξ (x + )]). Proof. Since D h (x, x + ) = ⟨∇h(x + ) -∇h(x), x + -x⟩ -D h (x + , x), then D h (x, x + ) = -η∇f ξ (x) ⊤ (x + -x) -D h (x + , x) = η D f ξ (x + , x) -f ξ (x + ) + f ξ (x) -D h (x + , x).The relative smoothness of f ξ and the step-size condition imply that ηD f ξ (x + , x) ≤ D h (x + , x), leading to1 η D h (x, x + ) ≤ f ξ (x) -f ξ (x +), and the result follows.This bound offers a new point of view on the variance, which can be bounded as the difference between the optimum of f , and the optimum of a related function, in which we make one mirror descent step before evaluating each f ξ .Finiteness. Proposition 2.2 implies the following:all η ≤ 1/L, σ 2 ⋆,η ≤ f (x⋆)-E[f ξ (x ξ ⋆ )] η . In particular, σ 2 ⋆,η is finite.This result directly comes from the fact thatmin x∈C E [f ξ (x + )] ≥ E [min x∈C f ξ (x + )] ≥ E f ξ (x ξ ⋆ ). It shows that the standard regularity assumptions for the convergence of stochastic mirror descent guarantee that the variance as introduced in Definition 2 remains bounded. This is a strong result, that justifies the supremum in the variance definition. Indeed, most other variance definitions require additional assumptions for the variance to remain bounded after the supremum. Instead, we globalize the variance definition, by taking the supremum over the right quantity to ensure that it remains bounded over the whole domain without having to explicitly assume it.Note that the bound from Corollary 2.3 has already been investigating in other settings for stochastic optimization [19] , as discussed in Section 2.2. While useful to show boundedness, this bound has a major drawback, which is that it explodes when the step-size η vanishes. This does not reflect what happens in practice, which is why we investigate finer bounds on σ 2 ⋆,η .Gradient norm at optimum. A usual way of formulating variance is to express it as the norm of the difference between stochastic gradients and the deterministic gradients. While the previous bounds highlight dependencies on the gradient steps (through evaluations at x + ), none of them really corresponds to "the size of the stochastic gradients at optimum". The key subtlety is that when using mirror descent, it is important to also specify the point at which these gradients are applied, and the following proposition gives a bound of this flavor on σ 2 ⋆,η . In this section, x η denotes the minimizer of f η when it exists and is in int C. Otherwise, unless explicitly stated, results involving x η can be replaced by a limit for x → x η .Proposition 2.4. If f is L-rel.-smooth, η ≤ 1/L and x ⋆ ∈ int C, σ 2 ⋆,η ≤ 1 η 2 E D h x + η , x + η .This can be considered as the Mirror Descent equivalent of E ∥∇f ξ (x ⋆ )∥ 2 . Yet, a key difference is that stochastic gradients are evaluated at point x η instead of x ⋆ , and ∇f (x η ) ̸ = 0 in general.Proof. For all x, applying the duality property of the Bregman divergence leads to:E D h (x, x + ) = E D h * (∇h(x + ), ∇h(x)) = E [D h * (∇h(x) -η∇f ξ (x), ∇h(x))] = E [D h * (∇h(x) -η∇f (x), ∇h(x))] + E [D h * (∇h(x) -η∇f ξ (x), ∇h(x) -η∇f (x))] = E [D h * (∇h(x) -η [∇f (x) -∇f (x ⋆ )] , ∇h(x))] + E D h x + , x + ,where the last equality comes from the Bregman bias-variance decomposition Lemma [23] .We then use the Bregman cocoercivity Lemma [7] to obtain:E [D h (x, x + )] ≤ ηD f (x, x ⋆ ) + E D h x + , x +. All these technical results can be found in Appendix A. In the end,f η (x) ≥ f (x ⋆ ) -1 η E D h (x + , x +) , and this is in particular true for x = x η .Limit behaviour. A first observation is that both the D h (x, x + ) term in the definition of f η and our variance definition are scaled by η -1 . Yet, they remain finite when η → 0. While this is clear in the Euclidean setting, this property holds more generally, as shown in the two following results.Proposition 2.5. Let x ∈ C and η 0 > 0 s.t. ED h (x, x + (η 0 , ξ)) < ∞. Then, f η (x) η→0 ---→ f (x).Note that uniform convergence of f η to f would require that there exists η > 0 such that sup x∈C D h (x, x + ) is finite, which we cannot guarantee in general (it does not hold for f = g = 1 2 ∥ • ∥ 2 defined on R d for instance). Denote ∥x∥ 2 A = x ⊤ Ax, then:Proposition 2.6 (Small step-sizes limit). If f ξ are L-rel.-smooth and f has a unique minimizer x ⋆ and for some η 0 > 0, x η = arg min f η (x) exists and is in int C for η ≤ η 0 ,EQUATION)This variance is actually the best we can hope for in the Bregman setting, which indicates the relevance of Definition 2. Indeed, this term exactly correspond to the variance one would obtain when making infinitesimal SMD steps from x ⋆ , i.e., the norm of the stochastic gradients at optimum in the geometry given by ∇ 2 h(x ⋆ ) -1 .We now compare Definition 2 with several variance assumptions from the literature. Note that they typically "only" require the bounds to hold for all iterates over the trajectory. However, in the absence of proof that the iterates stay in certain regions of the space, suprema over the whole domain are required for all variance definitions.Euclidean case. Let us now take a step back and look at the Euclidean case, h = variance assumption by assuming the smoothness of all f ξ [9] , which writesσ 2 ⋆,η ≤ E ∥∇f ξ (x ⋆ )∥ 2 .This result is obtained by writing that Divergence between stochastic and deterministic gradients. An early variance definition for SMD in the relative setting comes from Hanzely and Richtárik [10] , who define σ 2 sym as:∥∇f ξ (x)∥ 2 ≤ 2∥∇f ξ (x) -∇f ξ (x ⋆ )∥ 2 + 2∥∇f ξ (x ⋆ )∥ 2 ,σ 2 sym = 1 η sup x∈C E ∇f (x) -∇f ξ (x), x + -x + = 1 η 2 sup x∈C E D h x + , x + + D h x + , x + ,where we recall that x + is such that ∇h(x + ) = ∇h(x) -η∇f (x). We remark two main things when comparing σ 2 sym with Proposition 2.4: (i) σ 2 ⋆,η is not symmetrized, and contains only one of the two terms, and (ii) the bound only needs to hold at x η instead of for all x ∈ C. As a result, we directly obtain that σ 2 ⋆,η ≤ σ 2 sym , and σ 2 sym is actually infinite in most cases, whereas σ 2 ⋆,η is usually finite, as seen above.Stochastic gradients at optimum. Dragomir et al. [7] define the variance as:σ 2 DEH = sup x∈C 1 2η 2 E [D h * (∇h(x) -2η∇f ξ (x ⋆ ), ∇h(x))] = sup x∈C E ∥∇f ξ (x ⋆ )∥ 2 ∇ 2 h * (z(x)) ,where z(x) ∈ [∇h(x), ∇h(x) -η∇f ξ (x ⋆ )] The main interest of this definition is that stochastic gradients are only taken at x ⋆ . In particular, this variance is 0 in case there is interpolation (all stochastic functions share a common minimum). However, this quantity can blow up if h is not strongly convex, since in this case ∇ 2 h * is not upper bounded (indeed, smoothness of the conjugate is ensured by strong convexity of the primal function [14] ). Following similar derivations, but after the supremum has been taken, we arrive at:Proposition 2.7. If f is L-relatively-smooth w.r.t. h, then for η < 1/(2L) and some z η ∈ [∇h(x η ), ∇h(x η ) -η∇f ξ (x ⋆ )], the variance can be bounded as σ 2 ⋆,η ≤ E ∥∇f ξ (x ⋆ )∥ 2 ∇ 2 h * (zη) .In particular, we obtain a finite bound without having to restrict the space.Functions variance. Another variance definition that appears in the SGD literature is of the formf (x ⋆ ) -E f ξ (x ξ ⋆ ), using the optima of the stochastic functions [19] . Unfortunately, the results derived with this definition do not obtain a vanishing variance term when η → 0, unlike most other variance definitions, and contrary to what is observed in practice, that smaller step-sizes reduce the variance. The vanishing variance term can be obtained by rescaling by 1/η (so consideringf (x ⋆ ) -E f ξ (x ξ ⋆ ) /η instead), but this variance definition would explode for η → 0. This is because using such a definition would come down to performing the supremum step within the expectation from Proposition 2.2, using that f ξ (x + ) ≥ f ξ (x ξ ⋆ ), which is a very crude bound. Instead, Corolary 2.3 directly shows that our variance definition is tighter than this one, and in particular (i) it is bounded for all η > 0, (ii) it remains finite as η → 0 even with the proper rescaling (Proposition 2.6).Relation to c-transform. Mirror descent can be viewed as an alternate minimization method on transforms of f [18] . This point of view subsumes many methods, including the Newton Method or Mirror Descent. Central to their analysis is the notion of c-transform f c (y) = sup x∈C f (x) -c(x, y), a standard quantity from optimal transport [25] . It turns out that for η ≤ 1/L, f η is actually linked to the c-transform as f η (x) = E f c ξ (x + ) , where we use the cost c(x, y) = 1 η D h (x, y).Since f (x ⋆ ) = f c (x ⋆ ) = arg min x∈C f (x + ), denoting T c (g) = g c (∇h * (∇h(x) -η∇g(x))), we have that σ 2 ⋆,η = 1 η (min x∈C T c (E [f ξ ])(x)-min x∈C E [T c (f ξ )] (x)).We recognize the structure of a variance, as the difference between an operator applied to the expectation of a random variable, and the expectation of the operator applied to the random variable. Yet, compared to standard (Euclidean)analyses of SGD, it does not simply corresponds to the variance of the stochastic gradients (at optimum), and bears a more complex form.In this section, we have highlighted the connections with other definitions, and argued that f η (and its minimum) is a relevant quantity. In particular, Definition 2 is the only definition that allows boundedness of the variance notion both after a supremum step over the iterates (and without strong convexity of h) and in the η → 0 limit with the proper rescaling.Question: Does the paper discuss the limitations of the work performed by the authors? Guidelines:• The answer NA means that the paper has no 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 the 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 a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
convergence analysis: 
 Now that we have (extensively) investigated σ 2 ⋆,η , and the various interpretations that come from different bounds, we are ready to state the convergence results. Some proofs in this section are just sketched, but complete derivations can be found in Appendix C.Recall thatf ⋆ η = inf x∈C f η (x).Starting from an arbitrary x (0) , the sequence (x (k) ) k≥0 is built asEQUATIONNote that the (relatively) strongly-convex theorem has a standard form, and recovers usual MD resultsif we remove the variance, and standard SGD results if we take h= 1 2 ∥ • ∥ 2 .Proof of Theorem 3.1. We start from a variation of Dragomir et al. [7, Lemma 4 ]:EQUATIONEQUATIONUsing thatD f (x ⋆ , x) ≥ µD h (x ⋆ , x), and remarking that f (x ⋆ ) -f ⋆ η = ησ 2 ⋆,η, we obtain:EQUATIONAt this point, we can neglect the η f η (x) -f ⋆ η ≥ 0 terms and chain the inequalities for x = x (t) for t from 0 to T to obtain the result.This proof is quite simple, and naturally follows from Lemma C.1. One can also note that relative smoothness of f is not required to obtain Theorem 3.1, which has no condition on the step-size. This is not a typo, but reflects the fact that step-size conditions are needed to obtain a bounded variance.Indeed, the variance as defined here entangles aspects tied with the error due to discretization (which is usually dealt with using smoothness), and the error due to stochasticity. This is natural, as the stochastic noise vanishes in the continuous limit (η → 0). Besides, the magnitude of the updates depends both on where the stochastic gradient is applied and on the step-size. Yet, the simplicity of the proof is partly due to this entanglement, meaning that we have deferred some of the complexity to the bounding of the variance term.Also note that Theorem 3.1 uses constant step-sizes, but Equation ( 10) can be used with time-varying step-sizes, as is done for instance in the proof of Theorem 4.3. A variant of Theorem 3.1 in which the discretization error is partly removed from the notion of variance writes:Corollary 3.2. Let f be µ-strongly-convex and L-relatively-smooth with respect to h, andf ⋆ + = inf x∈C E [f ξ (x + )]. If η ≤ 1/L, the SMD iterates (Equation (3)) with constant step-size η verify η E f ξ ((x (T ) ) + ) -f ⋆ + +E D h (x ⋆ , x (T +1) ) ≤ (1-ηµ) T +1 D h (x ⋆ , x (0) )+ η µ f (x ⋆ ) -f ⋆ + η .This alternate version is obtained using thatf η (x) ≥ E [f ξ (x + )],a key step from the proof of Proposition 2.2 (see ( 8)). In the deterministic case, f ⋆ + = f (x ⋆ ), and we recover standard results.Let us now consider the convex case, meaning that µ = 0.Theorem 3.3. If f is convex, the iterates obtained by SMD using a constant step-size η > 0 verifyEQUATIONThis theorem is obtained by summing Equation ( 9) for x = x (k) for all k ∈ {1, . . . , T } and rearranging the terms. Note that varying step-size results can be obtained in the same way.This case differs from standard convex analyses, in that we obtain a control onf η (x (k) ) -f ⋆ η + D f (x ⋆ , x (k) ) instead of the usual f (x (k) ) -f (x ⋆ ).One of the main consequences is that we cannot get a control on the average iterate since Bregman divergences are in general not convex in their second argument, and f η is not necessarily convex. This non-standard result is a direct consequence of our choice of variance definition, but it is actually a quantity that naturally arises in the analysis.Note that a variant involving f ⋆ + can be obtained in the same lines as Corollary 3.2.Controlling f η . The results in this section do not directly control the function gap f (x) -f * , but rather the transformed one f η (x) -f ⋆ η . Yet, the continuity result (in η) from Proposition 2.5 shows that the bounds we provide can still be interpreted as relevant function values for small η.Controlling D f (x ⋆ , x (k) ). An interesting property of D f (x ⋆ , x (k)) is that it can be linked with the size of the gradients of f , as shown by the following result.Proposition 3.4. If ∇f (x ⋆ ) = 0 and f is L-relatively smooth with respect to h then for all x ̸ = x ⋆ , D f (x ⋆ , x) ≥ LD h * ∇h(x ⋆ )+ ∇f (x) L , ∇h(x ⋆ ) > 0.This is a Bregman equivalent of controlling the gradient squared norm, with the additional benefit that the reference point at which we apply the gradient is the optimum x ⋆ . Besides, Proposition 3.4shows that D f (x ⋆ , x) > 0 for x ̸ = x ⋆ without requiring f to be strictly convex (only h).Minimal assumptions on h. Note that the theorems in this section do not actually require h to satisfy Assumption 1, but only that iterations can be written in the form of Equation 3 (which is guaranteed by Assumption 1). While Assumption 1 allows for instance to use the Bregman cocoercivity lemma with any points, or ensures that ∇ 2 h is well-defined, which we leverage extensively in Section 2, our theorems are much more general than this, and include applications such as proximal gradient mirror descent (next remark) or the MAP for Gaussian Parameters Estimation (next section).Stochastic Mirror Descent with a Proximal term. Note that our results can be directly extended to handle a proximal term (similarly to the Euclidean proximal gradient algorithm), to handle composite objectives of the form f + g (and in particular projections, for cases in which g is the indicator of a convex set). More details can be found in Appendix E.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Answer: [NA] Justification: No experimental results.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/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "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 run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) 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. If only a 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) is recommended, but including URLs to data and code is permitted. 
map for gaussian parameters estimation.: 
 So far, we have proposed new variance definitions for the analysis of stochastic mirror descent, and we have shown that they compare favorably to existing ones, while leading to simple convergence proofs. In this section, we investigate the open problem formulated by Le Priol et al. [17] , which is to find non-asymptotic convergence guarantees for the KL-divergence of the Maximum A Posteriori (MAP) estimator. In particular, this example highlights the relevance of the infimum step on f η , since it gives the first generic analysis that obtains meaningful finite time convergence rates. (µ) = max θ ′ ∈Θ ⟨µ, θ ′ ⟩ -A(θ ′ ).Parameter µ is called the mean parameter, and the standard MAP estimator can be derived for n 0 ∈ N,µ 0 ∈ R as µ (n) MAP = n0µ (0) + n i=1 T (Xi) n0+n. The Maximum Likelihood Estimator (MLE) corresponds to taking n 0 = 0. An interesting observation is that µ(n)MAP can be obtained recursively for n > 0, asµ (0) MAP = µ (0) , η n = (n+n 0 ) -1 , µ (n+1) MAP = µ (n) MAP -η n ∇g Xn (µ (n) MAP ), with ∇g Xn (µ) = µ-T (X n ).In terms of primal variable θ (n) = ∇A * (µ (n) MAP ), the MAP writes:EQUATIONwheref Xn (θ) = A(θ) -⟨θ, T (X n )⟩, so that f (θ) = A(θ) -⟨θ, µ ⋆ ⟩.We recognize stochastic mirror descent iterations, with mirror A and stochastic gradients ∇f X . Similar results on the MLE can be obtained by taking n 0 = 0. This key observation implies that convergence guarantees on the MAP and the MLE can be deduced from stochastic mirror descent convergence guarantees.While this appears as an appealing way to obtain convergence guarantees for the MAP, Le Priol et al. [17] observe that none of the existing SMD results obtain meaningful rates for the convergence of the MAP for general exponential families. In particular, none of them recover the O(1/n) asymptotic convergence rate for estimating a Gaussian with unknown mean and covariance. This is due to the variance definitions used in the existing analyses, that all have issues (not uniformly bounded over the domain, not decreasing with the step-size...) as discussed in Section 2. Our analysis fixes this problem, and thus yields finite-time guarantees for the MAP estimator for the estimation of a Gaussian with unknown mean and covariance. This shows the relevance of Assumption 2.The main problem studied in Le Priol et al. [17] is that of the one-dimensional full-Gaussian case, where the goal is to estimate the mean and covariance of a Gaussian from i.i.d. samplesX 1 , . . . , X n ∼ N (m ⋆ , Σ ⋆ ), with Σ ⋆ > 0.Note that although notation Σ is usually reserved for the covariance matrix of a multivariate Gaussian, we use it for a scalar value here to highlight the distinction with σ 2 ⋆,η , the variance from stochastic mirror descent. In this case, the sufficient statistics write T (X) = (X, X 2 ), and the log-partition and entropy functions are, up to constants,A(θ) = θ 2 1 -4θ2 -1 2 log(-θ 2 ), A * (µ) = -1 2 log(µ 2 -µ 2 1 ), for θ ∈ Θ = R × R * -and µ ∈ {(u, v), u 2 < v}.The goal is to estimate D A (θ, θ ⋆ ), for which Le Priol et al. [17] show that only partial solutions exist: results are either asymptotic, or rely on the objective being (approximately) quadratic. Note that there is a relationship between natural parameters, mean parameters, and (m, Σ 2 ), the mean and covariance of the Gaussian we would like to estimate. In the following, we will often abuse notations, and write for instance D A ( θ, θ) in terms of (m, Σ 2 ) and ( m, Σ2 ) rather than θ and θ. We now state a few results, for which detailed derivations can be found in Appendix F. More specifically:D A ( θ, θ) = - 1 2 log Σ 2 Σ2 - Σ2 -Σ 2 2 Σ2 + ( m -m) 2 2 Σ2 .The update formulas for the parameters are given by:m + = (1 -η)m + ηX, (Σ 2 ) + = (1 -η) Σ 2 + η(m -X) 2 .(13) Therefore, MAP iterations are well-defined although A does not verify Assumption 1.Proposition 4.1. The iterations (12) are well-defined for η < 1 in the sense that if θ(n) ∈ Θ = R×R * -, then ∇A(θ (n) ) -η∇f Xn (θ (n) ) ∈ Range(∇A)almost surely, so that θ (n+1) ∈ Θ is well-defined almost surely. Besides, f ξ is 1-relatively-smooth and 1-relatively-strongly-convex with respect to A.This result is a direct consequence of the fact that D f ξ = D f = D A for all ξ, and the fact that∇A(θ) -η∇f Xn (θ) = (1 -η)∇A(θ) + ηT (X n ) ∈ {(u, v), u 2 < v} if ∇A(θ) ∈ {(u, v), u 2 < v}.Proposition 4.1 means that we can apply Theorem 3.1, so the next step is to bound the variance σ 2 ⋆,η .EQUATION)We now use this expression to to lower bound f ⋆ η and so upper boundσ 2 ⋆,η . Lemma 4.2. Let (m η , Σ 2 η ) be the minimizer of f η . Then, for η < 1/3, m η = m ⋆ , Σ 2 ⋆ ≥ Σ 2 η ≥ (1 -3η) Σ 2 ⋆ . In particular, the variance σ 2 ⋆,η verifies σ 2 ⋆,η ≤ -1 2η log (1 -3η). For 1/3 < η ≤ 1 -ε, σ 2 ⋆,η ≤ c ε, where c ε is a numerical constant that only depends on ε.Note that we show in this example that Σ 2 η is arbitrarily close to Σ 2 ⋆ as η → 0, which is expected.Theorem 4.3. Let Γ ≥ 0 be a numerical constant and Γ = 0 if n 0 > 3. The MAP estimator satisfies:E D A (θ ⋆ , θ (n) ) ≤ n 0 D A (θ ⋆ , θ (0) ) + 3 2 log(1 + n+1 n0 ) + Γ n + n 0 .Numerical constants are not optimized. Theorem 4.3 gives an anytime result on the convergence of the MAP estimator for all n ≥ 0, n 0 ≥ 1 directly from the general SMD convergence theorem. Yet, the open problem from Le Priol et al. [17] is not completely solved still, as discussed below.Reverse KL bound. We obtain a bound onD A (θ ⋆ , θ (n) ), instead of D A (θ (n) , θ ⋆ ) = f (θ) -f (θ ⋆ ).D A (θ (n) , θ ⋆ ) can be controlled asymptotically thanks to the bound on f η (θ (n) )-f η (θ η ), and f η → f when η = 1/n → 0, but we might also be able to exploit this control over the course of the iterations.Asymptotic convergence. Theorem 4.3 leads to a O(log n/n) asymptotic convergence rate instead of the expected O(1/n) [17] . This indicates that the f ηn (θ (n) ) -f ⋆ ηn terms should not be neglected.Indeed, θ (n) actually has a lot of structure in this example, since ∇A(θ(n) ) = 1 n n k=1 T (X k ).The SMD analysis is oblivious to this structure, hence the gap. Note that we can get rid of the log n factor and recover the right O(1/n) rate from the same analysis by using a slightly different estimator than the MAP (or MLE). This is done by setting the step-size as η n = 2 n+1 for n > 1, and the analysis of this variant follows Lacoste-Julien et al. [16] , as detailed in Appendix F.3.The special case of the MLE. The MLE corresponds to n 0 = 0, which is not handled in our analysis since the first step corresponds to η = 1, which necessarily results in θ(1) 2 = -∞ (which corresponds to Σ 2 = 0, as can be seen from ( 13)). If we consider that mirror descent is run from θ (1) , then we obtain E D A (θ ⋆ , θ (1) ) = ∞ in general, where the expectation is over the value of the first sample drawn. Therefore, we need to start the SMD analysis at θ (2) to fit the MLE into this framework, and in particular we need to be able to evaluate E D A (θ ⋆ , θ (2) ) . This is further discussed in Appendix F.4. 
conclusion: 
 This paper introduces a new notion of variance for the analysis of stochastic mirror descent. This notion, based on the fact that a certain function f η admits a minimum, is less restrictive than existing ones, has the right asymptotic scaling with the step-size and is bounded regardless of the trajectory of the iterates without further assumptions.We strongly believe that our analysis of SMD opens up new perspectives. As an example, we use our SMD results to show convergence of the MAP for estimating a Gaussian with unknown mean and covariance. As evidenced in Le Priol et al. [17] , all existing generic analyses of stochastic mirror descent failed to obtain such results. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA] Justification: No experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a 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, or as supplemental material. 
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: [NA] Justification: No experimental results.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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is 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 a 96% CI, if the hypothesis of Normality of errors is 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 are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or 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 in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a theoretical work on an optimization algorithm, it has no foreseeable societal impact bey 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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or 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 out 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 as 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 or unintentional) misuse of the technology.• If 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). 
safeguards: 
 Question: 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)?Answer: [NA] Justification: No model release.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] Justification: Not using existing assets.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 a URL.• 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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: As for the rest of this paper, Assumption 1 is assumed throughout this section. However, some of these results hold even with less regularity, and in particular do not require second order continuous differentiability.Lemma A.1 (Duality). For all x, y ∈ C, it holds that:EQUATIONSee, e.g. Bauschke et al. [1, Theorem 3.7] for the proof.Lemma A.2 (Symmetrized Bregman). For all x, y ∈ C, it holds that:EQUATIONThe proof immediately follows from the definition of the Bregman divergence. EQUATION)Denoting x +y = ∇h * (∇h(x) -η [∇f (x) -∇f (y)]), a tighter result actually writes:EQUATION)The proof of the tighter version is simply obtained by not using that D f (x +y , y) ≥ 0 in the original proof. While we don't directly use it in this paper, it is sometimes useful. We now introduce the generalized bias-variance decomposition Lemma [23, Theorem 0.1].Lemma A.4. If X is a random variable, then for all u ∈ C,EQUATIONWe start this section by proving the following lemma, which in particular ensures that D h (x, x + )/η increases with η (and so decreases as η → 0).Lemma B.1. Let ϕ ξ : η → 1 η D h (x, x + (η, ξ)). Then, ∇ϕ ξ (η) = 1 η 2 D h (x + (η, ξ), x) ≥ 0.Proof. First remark that since ∇h(x + ) = ∇h(x) -η∇f ξ (x), we can write∇ η D h (x, x + ) = ∇ η h(x) -h(x + ) -∇h(x + ) ⊤ (x -x + ) = -∇h(x + ) ⊤ ∇ η x + + ∇f ξ (x) ⊤ (x -x + ) + ∇h(x + ) ⊤ ∇ η x + = ∇f ξ (x) ⊤ (x -x + ) = 1 η ∇h(x) -∇h(x + ) ⊤ (x -x + ) = D h (x, x + ) + D h (x + , x) η .Then, the expression follows fromEQUATION)Proof of Proposition 2.5. We now prove that f η → f when η → 0. To show this, we note that for any fixed x ∈ int C:• For any fixed ξ, 1 η D h (x, x + ) = η 2 ||∇f ξ (x)|| 2 ∇ 2 h * (z) for z ∈ [∇h(x), ∇h(x) -η∇f ξ (x)]. Therefore, 1 η D h (x, x + ) → 0 for η → 0 since ∇ 2 h * (∇h(x)) = (∇ 2 h(x)) -1 < ∞ by strict convexity of h. • Let η ≤ η 0 . Then, for all ξ, 1 η D h (x, x + (η, ξ)) ≤ 1 η0 D h (x, x + (η 0 , ξ)) since the function η → 1 η D h (x, x + (η, ξ)) is an increasing function (positive gradient using Lemma B.1).• 1 η0 E [D h (x, x + (η 0 , ξ))] is finite.Then, using the dominated convergence theorem, we obtain that we can invert the integral (expectation) and the limit, so thatlim η→0 E 1 η D h (x, x + ) = E lim η→0 1 η D h (x, x + ) = 0.Proof of Proposition 2.6. We prove this result by successively upper bounding and lower bounding σ 2 ⋆,η , and making η → 0.1 -Upper bound on σ 2 ⋆,η . One side is direct, by writing that f (x η ) ≥ f (x ⋆ ):EQUATIONFrom the proof of Proposition 2.5 we have pointwise convergence of f η to f . Since f is convex and has a unique minimizer x ⋆ , then x η → x ⋆ for η → 0, which leads to the result.2 -Lower bound on σ 2 ⋆,η . By definition of x η as the minimizer of f η , we have f η (x η ) ≤ f η (x ⋆ ), and so:EQUATIONLet us now prove the following proposition, which follows the proof from Dragomir et al. [7] .Proof of Proposition 2.7. Let us prove thatσ 2 ⋆,η ≤ E ∥∇f ξ (x ⋆ )∥ 2 ∇ 2 h * (zη). We start byEQUATIONEQUATION)Using the convexity of D h * in its first argument and then the Bregman cocoercivity lemma, we obtain for η ≤ 1/2L:EQUATIONEQUATIONEQUATIONUsing that E D f ξ (x, x ⋆ ) = D f (x, x ⋆ ) and applying this to x = x η , we obtainσ 2 ⋆,η = f (x ⋆ ) -f η (x η ) η = E D h (x η , x + η ) + ηf (x ⋆ ) -ηf (x η ) η 2 ≤ 1 2η 2 E [D h * (∇h(x η ) -2η∇f ξ (x ⋆ ), ∇h(x η ))] + D f (x η , x ⋆ ) + f (x ⋆ ) -f (x η ) η = 1 2η 2 E [D h * (∇h(x η ) -2η∇f ξ (x ⋆ ), ∇h(x η ))] = 1 2η 2 × E 1 2 ∥2η∇f ξ (x ⋆ )∥ 2 ∇ 2 h * (zη) ,and the result follows. The last inequality comes from the fact that if x ⋆ = arg min x∈C f (x), then-∇f (x ⋆ ) is normal to C so -∇f (x ⋆ ) ⊤ (x η -x ⋆ ) ≤ 0. .In this section, we detail the proofs of the various convergence theorems that were only sketched in the main text. We start by proving the first identity, which is a variation of e.g., Dragomir et al. [7, Lemma 4], which we detail here for the sake of completeness.Lemma C.1. Let x + ∈ C be such that ∇h(x + ) = ∇h(x)-η∇f ξ (x), with f ξ a random differentiable function such that E [f ξ ] = f . Then, for all points y ∈ C,EQUATIONIn particular, we can apply the result to y = x ⋆ .Proof. We give a slightly different proof than Dragomir et al. [7] , and in particular this version of the identity is slightly more direct (though maybe less insightful) and does not require ∇f (y) = 0. We write:E D h (y, x + ) = E h(y) -h(x + ) -∇h(x + ) ⊤ (y -x + ) = E h(y) -h(x + ) -∇h(x + ) ⊤ (y -x) -∇h(x + ) ⊤ (x -x + ) = E h(y) -h(x) -∇h(x) ⊤ (y -x) + η∇f ξ (x) ⊤ (y -x) ∇h(x + ) ⊤ (x -x + ) + h(x) -h(x + ) = D h (y, x) + η∇f (x) ⊤ (y -x) + E D h (x, x + ) = D h (y, x) -ηD f (y, x) + η [f (y) -f (x)] + E D h (x, x + ) .Proof of Corollary 3.2. We start back from Equation ( 8), and write, using thatf η (x) ≥ E [f ξ (x + )](proof of Proposition 2.2):EQUATIONEQUATIONThe result follows naturally from using the relative strong convexity of f , leading to:EQUATIONThen, we chain iterations as done for Theorem 3.1Proof of Theorem 3.3. We also start from the same result as above, and write it for x = x (k) , so thatEQUATIONMoving the f η terms to the left, and summing this for k = 0 to T leads to:η T k=0 f η (x (k) ) -f η (x η ) + D f (x ⋆ , x (k) ) ≤ D h (x ⋆ , x (0) )-E D h (x ⋆ , x (k+1) ) +T η 2 σ 2 ⋆,η . (36)The final result is obtained by dividing by ηT , and the fact that E D h (x ⋆ , x (k+1) ) ≥ 0.Proof of Proposition 3.4. We use Bregman cocoercivity (Lemma A.3) with η = 1 L between x ⋆ and x (instead of x and x ⋆ as it had been done previously), which directly leads to:EQUATIONThe first part of the proposition follows from the fact that ∇f (x ⋆ ) = 0. For the rest proof, we start with Inequality (32), which gives:0 = D h * (∇h(x ⋆ ) - 1 L ∇f (x), ∇h(x ⋆ )) = D h x ⋆ , ∇h * ∇h(x ⋆ ) - 1 L ∇f (x) .At this point, strict convexity of h leads to ∇h * ∇h(x ⋆ ) -1 L ∇f (x) = x ⋆ , so that ∇f (x) = 0 by applying ∇h on both sides.In this section, we quickly illustrate that the result we obtain is tightly linked to the notion of variance that we define. As an example, a variation of Theorem 3.3 can be obtained with a control on f (x) -f (x ⋆ ), but this requires a different notion of variance:Theorem D.1. If f is convex, the iterates obtained by SMD using a constant step-sizes η > 0 verifyEQUATIONwhereEQUATIONNote that this alternative variance definition can be unbounded even when σ 2 ⋆,η is bounded, as is the case for instance in the Gaussian MAP example. Besides, it does not inherit from most of the good properties of σ 2 ⋆,η presented in Section 2, and cannot be compared to the other standard variance notions. The main case in which this alternative definition makes sense is the Euclidean case, in which σ2 ⋆,η can be bounded using cocoercivity.Proof of Theorem D.1. This proof directly starts from Lemma C.1:EQUATIONSumming this for k = 0 to T , and dividing by ηT we obtain:EQUATIONThe result on the average iterate then follows from convexity of f and taking expectation on x (k) .We are interested in this section in a variation of the original problem, where we would like to solve the following problem:EQUATION)where g is a convex proper lower semi-continuous function (but not necessarily differentiable). This problem can be solved using the following stochastic proximal mirror descent algorithm:EQUATION)This is a "proximal" version, which for instance corresponds to projected stochastic mirror descent if g is the indicator of a convex set. Under Assumption 1, the iterations write:EQUATIONwhere ω ∈ ∂g(x + ), the subgradient of g at point x + . Equation (47) can be rewritten asEQUATIONfor any ω x ∈ ∂g(x). In particular, (47) can be interpreted as a Stochastic mirror descent step with objective f ξ + g and mirror h + ηg. While the mirror does not satisfy Assumption 1 (and in particular twice differentiability in case g is the indicator of a set), the iterations can still be written in the form of Equation ( 3). In particular, the theorems from Section 3 still apply, with the adapted variance definition involving function f + g and mirror h + ηg. Similarly, f + g is 1/η relatively-smooth with respect to h + ηg as long as f is L-relatively-smooth with respect to h and η ≤ 1/L.We now prove an equivalent for Lemma C.1.Lemma E.1. Let x + ∈ C be such that ∇h(x + ) = ∇h(x) -η [∇f ξ (x) + ω], with f ξ a random differentiable function such that E [f ξ ] = f and ω ∈ ∂g(x + )where g is a convex proper lower semi-continuous function. Then, for all y ∈ C ∩ domg,E D h (y, x + ) = D h (y, x) -ηD f (y, x) -η[f (x) -f (y)] + E D h (x, x +f ) -D h (x + , x +f ) + ηω ⊤ (y -x + ),where x +f is the point such that ∇h(x +f ) = ∇h(x) -η∇f ξ (x).Proof. We write:D h (y, x + ) = h(y) -h(x + ) -∇h(x + ) ⊤ (y -x + ) = h(y) -h(x +f ) -∇h(x +f ) ⊤ (y -x + ) + ηω ⊤ (y -x + ) -h(x + ) + h(x +f ) = D h (y, x +f ) -∇h(x +f ) ⊤ (x +f -x + ) + ηω ⊤ (y -x + ) -h(x + ) + h(x +f ) = D h (y, x +f ) -D h (x + , x +f ) + ηω ⊤ (y -x + )The result follows from applying Lemma C.1 to D h (y, x +f ).Note that by abuse of notation, if we denote D g (y, x + ) = g(y) -g(x + ) -ω ⊤ (y -x + ), andD g (y, x) = g(y) -g(x) -ω ⊤x (y -x) for any ω x ∈ ∂g(x), then with a few lines of computations, andnoting in particular that D h (x, x +f ) -D h (x + , x +f ) = D h (x, x + ) -∇h(x +f ) -∇h(x + ) ⊤ (x -x + ) we obtain:E D h+ηg (y, x + ) = D h (y, x) -ηD f (y, x) -η[f (x) -f (y)] + E D h (x, x + ) -ηE ω ⊤ (x -x + ) + ηE g(y) -g(x + ) = D h+ηg (y, x) -ηD g (y, x) -ηD f (y, x) -η[f (x) -f (y)] + E D h+ηg (x, x + ) + η [g(y) -g(x)]In particular, we exactly recover the result of Lemma C.1 applied to the iterations in which we take (sub)-gradients of f + g with mirror h + ηg, i.e.,E D h+ηg (y, x + ) = D h+ηg (y, x) -ηD f +g (y, x) -η[(f + g)(x) -(f + g)(y)] + ED h+g (x, x + ).Therefore, using the same sequence of derivations, Theorems 3.1 and 3.3 can be transposed directly to the composite (f + g) setting by simply defining generalized Bregman divergences where the gradient parts are replaced by the subgradients picked in the actual SMD steps.While h + ηg does not necessarily satisfy Assumption 1, the key point is that iterations can be written in the form of Equation ( 47), which is the case for instance if g is the indicator of a convex set.Note that Corollary 3.2 also holds in the same way, since relative smoothness is only needed to obtain that ηD f ξ +g (x, x + ) ≤ D h+ηg (x, x + ), which is equivalent to ηD f ξ (x, x + ) ≤ D h (x, x + ), which holds by L-relative smoothness of f with respect to h for η ≤ 1/L.In this section, we prove the various results for Gaussian estimation with unknown mean and covariance. For the sake of brevity, we only prove the propositions, and refer the interested reader to, e.g., Le Priol et al. [17] for standard results about the setting.We first write what the various divergences are in our setting, together with the mirror updates and finally the form of f η . Following Le Priol et al. [17, Section 4 .2], we write that:EQUATION)This allows us to express A(θ) in terms of (m, Σ 2 ):EQUATIONProposition F.1. The Bregman divergence with respect to θ, θ writes:EQUATION)Proof. We know that ∇A(θ) = µ = (m, m 2 + Σ 2 ). Therefore,EQUATION)Using Equation (50), we obtain:D A ( θ, θ) = A( θ) -A(θ) -∇A(θ) ⊤ ( θ -θ) = 1 2 log(2 Σ2 ) - 1 2 log(2Σ 2 ) + Σ 2 -Σ2 2 Σ2 + (m -m) 2 2 Σ2 ,which finishes the proof.In the Gaussian with unknown covariance, the sufficient statistics are:EQUATIONwhere x ∈ R is an observation drawn from N (m ⋆ , Σ ⋆ ).Let us now prove the form on the updates, which corresponds to (13):Proposition F.2. In (m, Σ 2 ) parameters, the updates write:EQUATIONEQUATION)Proof. Since the (stochastic) gradients write g(µ) = µ -T (X), the iterations are defined by:EQUATION)Since (µ 1 , µ 2 ) = (m, m 2 + Σ 2 ), the update on m is immediate. For the update on Σ 2 , we write:(Σ 2 ) + = µ + 2 -(m + ) 2 = (1 -η)µ 2 + ηX 2 -((1 -η)m + ηX) 2 = (1 -η)Σ 2 + (1 -η)m 2 + ηX 2 -(1 -η) 2 m 2 -2η(1 -η)Xm -η 2 X 2 = (1 -η)Σ 2 + η(1 -η)(m -X) 2 .We now use this to show that updates are well-defined.Proof of Proposition 4.1. If θ 2 < 0 then Σ 2 > 0 so for η < 1, (Σ 2 ) + > 0 almost surely so thatθ + 2 < 0 and |θ + 1 | < ∞. In particular, θ + ∈ R × R *-so the update is well-defined. The rest of the proposition comes from the fact that∇ 2 f ξ = ∇ 2 f = ∇ 2 A.We can now proceed to proving the form of f η . We first start by writing that:EQUATIONTherefore,EQUATIONIn particular,EQUATIONNote that, as expected, this corresponds to D A (θ, θ ⋆ ), that we can also compute through Proposition F.1. We now write:EQUATIONTherefore,EQUATIONFinally, E (m -X) 2 = (m -m ⋆ ) 2 + Σ 2 ⋆ , and so:EQUATIONwhich precisely corresponds to Equation (14) . We now proceed to proving bounds on θ η for η < 1.F.2 Bounding the stochastic mirror descent variance σ 2 ⋆,η .Now that we have an explicit form for f η , we can characterize its minimizer θ η , and use this to prove results on f η (θ η ), which will in turn lead to bounds on σ 2 ⋆,η . This is the core of Lemma 4.2.Proof. Proof of Lemma 4.2. The proof will proceed in three different stages:• Differentiating f η with respect to m and Σ 2 .• Using these expressions to obtain bounds on the (m η , Σ 2 η ) for which ∇f η is 0.• Plugging these bounds into the expression of f η to bound Σ 2 η .1 -Differentiating f η . Before differentiating, we rewrite:f η (θ) -f (θ ⋆ ) = 1 2 log Σ 2 + 1 2η E log 1 + η (m -X) 2 Σ 2 - 1 2 log Σ 2 ⋆ + 1 2η log(1 -η) (72) = - 1 -η 2η log Σ 2 + 1 2η E log Σ 2 + η(m -X) 2 - 1 2 log Σ 2 ⋆ + 1 2η log(1 -η).(73) Indeed, the two terms on the right are constant and so do not matter. If we differentiate in m, we obtain:EQUATIONNow, differentiating in Σ 2 yields:EQUATION2 -Obtaining bounds on (m η , Σ 2 η ). The solution to ∇ m f η (θ) = 0 is m = m ⋆ . Indeed, it is direct to verify that in this case, E X Σ 2 +η X2 = 0 since X = m ⋆ -X is symmetric (with respect to 0). For m > m ⋆ , E X Σ 2 +η X2 > 0 since we integrate the same values as the previous case, but now more mass is put on the positive values (and similarly for m < m ⋆ ). Note that this is the case regardless ofΣ 2 η .We are now interested in Σ 2 η . Note that we will not get such a clean expression as for m η , but only bounds. From its expression, we deduce that ∇ Σ 2 f η (θ η ) = 0 can be reformulated as:EQUATIONFor the upper bound, we simply write that:EQUATIONfrom which we deduce that Σ 2 η ≤ Σ 2 ⋆ . Let us now introduce some α > 0. We have that:EQUATIONWe now use that for u ≥ -1, 1 1+u ≥ 1 -u, and so:EQUATIONEQUATIONRearranging terms, we obtain:EQUATIONWe see that α = Σ 2 ⋆ maximizes the right term, and we obtain the desired result, i.e.:EQUATIONUnfortunately, we see that this bound is only informative for 3η < 1. For the rest of the cases, we will use the Markov inequality instead, which writes for all a > 0:EQUATIONYet,P (m η -X) 2 Σ 2 η + η(m η -X) 2 ≥ a = P (m η -X) 2 Σ 2 ⋆ ≥ a 1 -ηa Σ 2 η Σ 2 ⋆ = 2P X -m ⋆ Σ ⋆ ≥ a 1 -ηa Σ η Σ ⋆ .(85) Therefore, denoting Φ the cumulative distribution function of the standard Gaussian, we have:EQUATIONand since Φ -1 is an increasing function, this leads to:EQUATIONso that:EQUATIONOne can check that Φ -1 1 -1 2a / √ a < 1 for all a, which is consistent with the fact that Σ 2 η ≤ Σ 2 ⋆ .Also note that for η = 1, a non-trivial bound would require a < 1, but then Φ -1 1 -1 2a ≤ 0 so (as expected), we cannot get better than Σ 2 η ≥ 0. However, the previous bounding (Equation ( 83)) is more precise for small η since Φ -1 1 -1 2a / √ a < 1 -c with c > 0 a constant regardless of a. In particular, for any ε, by using any 1 < a < 1/(1 -ε), we obtain that Σ 2 η ≥ α ε Σ 2 ⋆ for some constant α ε that only depends on the a that we choose. In particular, we can handle the cases η = 1/2 and η = 1/3 that gave trivial results Σ 2 η ≥ 0 with the previous bounds.The last part consists in proving thatf η (θ η ) -f (θ ⋆ ) ≥ 1 2 log Σ 2 η Σ 2 ⋆ .To do so, we start back fromf η (θ) -f (θ ⋆ ) = 1 2 log Σ 2 Σ 2 ⋆ + 1 2η E log (1 -η) 1 + η (m -X) 2 Σ 2 ,and show that E log (1-η) 1 + η (mη-X) 2 Σ 2 η ≥ 0.We start by the inequality log(1+x) ≥ x 1+x , leading to:EQUATIONRecall that the optimality conditions for (m η , Σ 2 η ) write:EQUATIONso thatEQUATIONCombining these, we obtain thatE log (1 -η) 1 + η (m η -X) 2 Σ 2 η ≥ ηE (1 -η)(m η -X) 2 -Σ 2 η (1 -η) Σ 2 η + η(m η -X) 2 = η E (m η -X) 2 Σ 2 η + η(m η -X) 2 - 1 1 -η E Σ 2 η Σ 2 η + η(m η -X) 2 = 0,which is the desired result.The final result is obtained by plugging the lower bounds for Σ 2 η into this bound, leading to either σ 2 ⋆,η ≤ -1 2η log(1 -3η) for η < 1/3 or σ 2 ⋆,η ≤ -1 2η log α ε for η < 1 -ε.EQUATIONwhere the right term is replaced by c ε (where c ϵ = -1 2 log α ε ) for k ≤ 3. Taking η = 1/k for k > 1 and multiplying by k leads for k > 3 to:EQUATIONTherefore, a telescopic sum leads to, for n 0 > 0:EQUATIONand so, sinceEQUATIONwhere Γ = 2c 1/2 and we actually have Γ = 0 for n 0 > 3.F.3.2 O(1/n) convergence result.We now consider a different estimator (from the MAP and the MLE), which we construct in the following way:• Choose n 0 ≥ 6 and initial parameter θ(n0) .• Obtain θ(n) by performing n -n 0 stochastic mirror descent steps from θ(n0) with step-sizesη k = 2/(k + 1) for k ∈ {n 0 , ..., n}.This estimator is a modified version of the MAP, where n 0 controls how much weight we would like to put on the prior, and θ(n0) would typically be the same starting parameter as for the MAP estimator.This estimator is built so that we can use the convergence analysis from Lacoste-Julien et al. [16] and obtain a O(1/n) convergence rate. Note that we make the n 0 ≥ 6 restriction for simplicity to ensure that σ 2 ⋆,η ≤ 3/2, but the result can be easily adapted to n 0 ≥ 2.Proposition F.3. After n -n 0 steps, this modified estimator θ(n) verifies:EQUATIONProof. Let us note D k = E D h (θ ⋆ , θ(k) ) . In this case, using that σ 2 ⋆,η ≤ 3/2, Theorem 3.1 writes (since µ = 1):EQUATION)At this point, we can multiply by k(k + 1) on both sides, and takeη k = 2 k+1 for k ≥ n 0 . Remarking that 1 -η k = 1 -2 k+1 = k-1 k+1, we obtain that:EQUATIONUnrolling this recursion from k = n 0 to k = n -1 (since (k + 1)kD k+1 = L k+1 , where L k = k(k -1)D k ), we obtain:EQUATIONand the result follows by dividing by n(n -1), and using that (n -n 0 )/(n -1) ≤ 1.For the MLE estimator, directly applying the mirror descent approach would require using η 0 = 1, starting from an arbitrary θ (0) (that would not affect the results anyway). The problem in this case is that D h (θ ⋆ , θ (1) ) is infinite since Σ (2) = 0. This also means that we cannot start the stochastic mirror descent algorithm from θ (1) , since the recursion would still involve the infinite D h (θ ⋆ , θ (1) ).Therefore, in the case of the MLE, considering that the first two samples are X (1) and X (2) , then the first two points are:m (1) = X (1) , Σ (1) = 0 and mEQUATIONMore generally, a direct recursion for the MLE leads to:EQUATION)From this, we derive that:EQUATIONwhere (107) comes from the fact that X (n) and m (n-1) are independent with mean m ⋆ . Plugging this into the expression of D h (θ ⋆ , θ) for the MLE after n steps, we obtain:EQUATIONUnfortunately, there is no closed-form for this expression for arbitrary n, hence the need for a more involved analysis, for instance through the mirror descent framework. For the case n = 2 however (which is the one we are interested in), we obtain thatEQUATIONwhere Y = X (1) -X (2) √ 2Σ⋆∼ N (0, 1). Therefore, this can simply be treated as a constant that we can precisely evaluate numerically (for instance remarking that Y 2 is gamma distributed and using results on logarithmic expectations of gamma distributions).For n > 2, it is tempting to use the convexity of -log to use a similar reasoning, but this only leads to a constant bound on D h (θ ⋆ , θ (n) ).NeurIPS Paper ChecklistJustification: Only theoretical results for the convergence of an optimization algorithm, with no foreseeable societal impact.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 


Decision: This was a difficult decision. I think this is an incredibly important problem due to its implications about basic estimation ("statistics has no clothes"). So I was excited to see work on the topic but the result is ultimately not quite what we want. I do think the paper has some great insights and should be published, but the reviewers (a couple of which know the topic very well) felt that the paper was unclear on many points.

If this were a journal, I would be sending it back for a major revision. In the conference system, it is less clear what to do. I think the paper will benefit from a lot by a re-write, with the authors thinking carefully about what points the reviewers understood and including the additional examples brought up in the reviewer discussion. I ultimately fell on the side of recommending reject when considering that many other accepted papers have already gone through the process of making the contribution as clear as possible.

Nevertheless, I am looking forward to reading the revision.

Reviews: review: paper_summary: paper_summary: This submission studies stochastic mirror descent (SMD) under quite mild conditions on the mirror map and objective function. More specifically, there are a variety of SMD analysis in the literature, but virtually all of them require strong conditions on the mirror map (such as strong convexity) that do not hold in cases where we only have relative smoothness (and/or relative strong convexity) of the objective function with respect to the mirror map. The authors propose a definition of variance of SMD that is better behaved under minimal assumptions. They show how this new variance can be used to obtain general convergence results for SMD. Finally, they show how the new variance definition for SMD can show some kind of non-asymptotic convergence rates for MLE and MAP of Gaussian parameter estimation with unknown mean and covariance, making partial progress on a conjecture posed by Le Priol et at.
strength_weakness: strength_weakness: In its current form, I have one main concern with the paper:
- Despite what is written at the beginning of the paper, **Assumption 1** is NOT a blanket assumption used throughout the paper. In fact, it appears only section 2 uses assumption 1. The rest of the paper uses a weaker assumption that is never clearly stated, which makes it hard to understand when the results hold or not. 
This is likely to be a problem with presentation, but in its current form it is often not clear what are the assumption required at each point. Since the main point of the paper is to use a minimal number of assumptions, it is very important for those to be clearly stated. 

A minor weakness is the lack of an example besides MAP/MLE. I could not easily think of a concrete example where I could apply the convergence results in sec 3 or 4. If the authors have an example besides MLE or MAP (even if a bit artificial), it would be great. For example, some example with a mirror map such as $- \log x$ would be interesting, but this is a minor suggestion, since it would be nice to see a concrete example of the use of the results in Sec 2 (the results in Sec 4 require a specialized bound on the variance) 

Summary of weaknesses:
- Unclear requires assumptions for many of the results
- (Minor weakness) Lack of a concrete (even artificial) example of application of any of the theorems in Sec 3 beyond MAP/MLE (and the latter require specialized bounds on the variance).
questions: questions: Currently I'm leaning towards accepting this paper (although borderline), but I'd expect the authors to address some of my concerns regarding assumptions (which, ultimately, are concerns about the correctness of the paper). 
If the authors successfully address my concerns, I'll most likely increase my score. At this point I believe there should be mistakes with the assumptions, but my confidence if no high due to the lack of clarity regarding assumptions. I will be forced to decrease my score if another review or myself find a hard inconsistency in the proofs and the assumptions needed. 

#### Questions about assumptions
- *$h$ should be of Legendre type?*: At some points the authors say they do not need assumption 1, but instead only need eq. (3) to hold for all iterates. One issue is that this is an assumption on the iterates, not on $h$, and leaves the conditions on $h$ way too open. In fact,  for many of the properties the authors seem to use in the appendix (Bregman divergence duality, for example), we usually require $h$ to **at least** be of Legendre type. Without this assumption it is unclear whether many of the derivations hold (I haven't checked the appendix carefully, but $h$ being of Legendre type is close to the minimal assumption for mirror descent to be well-defined). It is not clear that (3) implies a condition on $h$, and trying to prove something like this seems unecessary. The authors should either explain why they do not assume $h$ is of Legendre type (and show that all the properties they use actually hold even without assumption 1), or clearly state this assumption.
- *Formal statement of the assumption used?*: Ideally the authors would have the two different assumptions clearly stated, and then clearly mention either in each section or in the statement of each result which results depend on the assumptions. Also, eq. (3) seems to not be well-defined in general for general $h$ of Legendre type (for example, if $h = - \ln x$ the right-hand side might be negative if $x$ is large, regardless of $\eta$, which is a problem). Moreover, it would be interesting if the authors showed that the assumption on the iterates holds for a broad class of problems, such as general MAP for exponential families. This is because if $f_z(x) = h(x) - \langle x,z \rangle$ with $z \in \mathrm{cl}(\mathrm{dom} \nabla h)$ (here $z$ would be the sufficient statistics of one of the data points), then $\nabla h(x) - \eta \nabla f_z(h) = (1 - \eta)\nabla h(x) + \eta\nabla f_z(h)$, which is in the interior of the domain of $\nabla h$ for $\eta < 1$, showing that eq. (12) is indeed valid for exponential families. It is likely that the authors were aware of this already, but I believe clearly stating that this is true for general exponental families since Prop. 4.1 only covers the Gaussian case.
- *Assumption 1 is required for a result in sec 3, and this should be clearly mentioned*: Not a question, but related to the previous point: the authors say that the theorems in section 3 do not use assumption 1. While this seems to be true if read literally (not carefully checked), this might be read as all the *results* in section 3 not requiring Assumption 1, which is false: Proposition 3.4 uses Bregman co-coercivity, which in turn requires Assumption 1 to be true in general if I am not mistaken. The problem is that now the reader is left unsure what requires assumption 1 or not, putting into question whether the results in Sec 4 (which uses Sec 3) are correct or not.
- *Projected Gradient Descent*: The authors mention the 2-norm case a couple of times, but one should be careful regarding the set $C$ in this case. For $C \neq \mathbb{R}^d$  convex (say, the $\ell_2$-ball), assumption 1 fails to hold for $h = \frac{1}{2}\lVert\cdot \rVert_2^2$ since, in this case, the minimization problem may be attained at the boundary of $C$. This is an issue since (3) stops to be equivalent to (projected) gradient descent (either it becomes unprojected gradient descent or, if you add the indicator of $C$ to $h$, then $h$ may not be differentiable at the iterates $x$). In this case $h$ is not Legendre in $C$ (thus, having the assumption on $h$ would help prevent this case), and one might be able to handle this case by carefully handling the projections. I don't think it is interesting to try to do so, but this is a point that can bring even more doubts about the correctness of the paper. 

#### Minor points 
- 196-197: Not clear what "after the supremum has been taken" refers to exactly.
- 202-203: "Variance term" does not mean "variance", right? I think I understand what you meant on this lines, but this is a quite confusing passage and I had to re-read it a couple of times
- 232: The notation $\{0,T\}$ refers to a set with 2 elements, you did not mean that. 
- 237: What are the assumptions of Lemma 4 of Dragomir? Maybe state it on the appendix, since it is very important for this result to not depend on Assumption 1, right? I'll check the lemma in detail later to verify.
- 278-283: This should definitely be mentioned earlier in the section, not at the end. Also, this should be formalized if possible.
- 318: Assumption 2 -> Definition 2 (Also, why assumptions/defs are numbered differently from theorems/propositions/lemmas?)
- 338: Not exactly clear what $\xi$  is here, use $X_n$ notation?
- This might be personal choice, but $\overline{x^{+}}$ is very big and stretches a lot of the lines you use this notation. $\overline{x}^+$  seems to be slightly better (although a bit cluttered). Don't feel like you need to change this if you disagree.

#### Post-discussion summary
Ultimately, this discussion on assumptions is more on the organization of the text and on the writing, not on the contributions of this submission. This is a very hard theoretical problem (which one can gauge by the amount of previous work with only partial results or restrictive assumptions). The partial solution to the conjecture on non-asymptotic convergence of MAP showcases the potential usefulness of these ideas for future work. Thus, I vouch for acceptance of this paper, since I believe it is of interest for the ML optimization community and can clearly be of inspiration for future work.
limitations: limitations: Although the authors are not explicit about some of the limitations of the results on sec 3, they do discuss how to interpret some of the results and limitations from their convergence rates.
paper_summary: paper_summary: This paper introduces a new variance assumption for the analysis of stochastic mirror descent (SMD) to handle cases where standard bounded variance assumption does not hold. The authors show this new assumption can be shown to hold under some regularity assumptions. The authors use the new results to show some convergence guarantees for MLE and MAP of a Gaussian with unknown mean and variance using the connection between this problem and SMD convergence guarantees.
strength_weakness: strength_weakness: I find the motivation of the paper and its application to MAP bounds interesting, however I have some concerns about writing and the strength of the derived results in the context of the application in Section 4. It seems necessary for the latter point to be clarified.

- Authors write after Theorem 4.3 that the open problem from [17] is not completely resolved because  the convergence is not shown for the desired quantity. In particular, the authors describe that the guarantee is for $D_A(\theta_*, \theta^{(n)})$ instead of $D_A(\theta^{(n)}, \theta_*) = f(\theta) - f(\theta_*)$. The authors then write that two quantities can be related asymptotically but they state: "but we might also be able to exploit this control over the course of the iterations". Can you make this point more precise? It is not clear to me what this last part is trying to describe. Is it meant to be understood as an open question or is it possible for the authors to derive the stronger result? Since the paper mentions at many places that showing convergence guarantees for MAP is an important contribution of the paper, it is important to justify the convergence metric used in the results for justifying the contribution of the paper fully.

- It might be better to replace MLE in the abstract to MAP since Section 4 is mostly about MAP.

- Abstract states a couple of times "strong convergence", I suggest to remove this since "strong convergence" has a precise meaning in infinite-dimensional optimization and usage in the abstract is confusing because of this. Clearly this is not how the authors are using this term, but it seems authors are using this as a subjective adjective, which is not necessary. By subjective, I mean that: how can one decide what convergence result is strong and what is not?

- Assumption 1 requires all $f_\xi$ are convex. This is rather strong since the standard assumption is $\mathbb{E} f_\xi$ to be convex. Can you discuss this more? According to Prop 4.1, this holds for the main application of the paper, but it might be worth discussing why componentwise convexity is needed.
questions: questions: Please see the questions in the "Weaknesses" section.

- Can you describe more clearly "additional assumptions on the mirror, such as strong convexity (in the usual sense), to ensure bounded variance"?

- Line 179, 180: can you provide the proof for getting $\sigma_{\star, \eta}^2 \leq \mathbb{E} \| \nabla f_{\xi}(x_\star)\|^2$? I could not find this in Appendix B, can you let me know if I missed this?

- Corollary 2.3: Why does it follow that $\sigma_{\star, \eta}^2$ is finite? There is no lower bound on $\eta$, why can't one make this infinite for arbitrarily small $\eta$? The explanation in line 132-136 is also not clear. Can you provide clearer references and explanations for the claim you give in bold in this passage? To add to the confusion here, Line 206 mentions that the quantity that appears in this corollary can explode for $\eta \to 0$ by citing [19]. Can you first provide the precise pointer to [19] for this variance bound and then also explain the difference of this with Corollary 2.3?

- line 137: should change to "has already been investigated"

- Line 262-267: The authors say that the result is "non-standard" but they do not explain how meaningful it is, since the convergence is not shown for standard quantities. Can you please clarify?

- Bregman methods are used often with compact domains (especially simplex). It might be good to also mention this in the paper to say that some interesting applications may satisfy the bounded variance assumption but other interesting appllications do not. It might also help to provide more examples where we have unbounded domains and we use SMD.

- Section 4.2: Where did you define $R_{-}^*$?
limitations: limitations: The limitations are discussed clearly. The authors provided explanations after Theorem 3.3 and Theorem 4.3 to describe the limitations of their result.
paper_summary: paper_summary: The paper proposes a new analysis of SMD using a newly introduced generalized variance notion. The benefit of the new analysis is demonstrated in the application to maximum a posteriori estimation of Gaussian parameters.
strength_weakness: strength_weakness: Major:

As explained after theorem 4.3, the guarantees are derived for a reverse KL and may not imply anything on the desired quantity $f(\theta) - f(\theta_*)$. This of course, limits the contribution in this application significantly as non-asymptotic rates were known before. 

Minor problems that I hope the authors can fix in the next revision. 

1. Is the set C compact? If not, why the minimum exists in Proposition 2.2?

2. Cannot find where $x_*$ is defined. Why does it exist? 

3. There is a small issue with indicies in equation (12) and in paragraph before. $\eta_{n} = \frac{1}{n_0+n+1}$, and the stochastic gradient should depend on the new sample $X_{n+1}$.

Update: meaningful results are obtained only for relatively strongly convex case (which is a stronger assumption than even strong convexity). In the convex case, a different (much stronger) definition is used. This becomes clear only after reading Appendix D. This limitation should be clarified in section 3.2, where convergence on some surrogate loss is shown. I will update my evalutation.
questions: questions: Is it possible to consider other, non-Gaussian/non-conjugate, models?
limitations: limitations: n/a
paper_summary: paper_summary: This work revisits Stochastic Mirror Descent (SMD) proofs in the (relatively-strongly-) convex and relatively-smooth setting, and introduces a new (less restrictive) definition  of variance which can generally be bounded (globally) under mild regularity assumptions. Then this paper investigates this notion in more details, and show that it  naturally leads to strong convergence guarantees for stochastic mirror descent. Finally, this paper leverage this new analysis to obtain convergence guarantees for the Maximum Likelihood Estimator of a Gaussian with unknown mean and variance.

Problem:
In proof of Proposition 2, by the definition of $\sigma_{*,\eta}^2$, we can obtain that
$ \sigma_{*,\eta}^2 = \frac{\min_x f(x) - \min_x f_\eta(x)}{\eta}  $. 
However,  $x_* =\argmin_x f(x)$ does not equal to $x_*' = \argmin_x f_{\eta}(x)$.
This will lead to $\sigma_{*,\eta}^2 \neq \frac{1}{\eta^2} D_h(x^*, x^+）$.
strength_weakness: strength_weakness: No.
questions: questions: In the proof of Proposition 2, by the definition of $\sigma_{*,\eta}^2$, we can obtain that
$ \sigma_{*,\eta}^2 = \frac{\min_x f(x) - \min_x f_\eta(x)}{\eta}  $. 
However,  $x_* =\argmin_x f(x)$ does not equal to $x_*' = \argmin_x f_{\eta}(x)$.
This will lead to $\sigma_{*,\eta}^2 \neq \frac{1}{\eta^2} D_h(x^*, x^+）$.
limitations: limitations: No
paper_summary: paper_summary: This paper investigates a new definition for the stochastic gradient variance in mirror descent.
Most existing analyses for stochastic mirror descent require a strongly convex distance generating function to bound the gradient variance.
This limits the their applications especially when this assumption fails.
In particular, Le Priol et al. (2021) have shown that the none of the existing convergence rates applies to Gaussian maximum likelihood.

This paper aims to fix this issue by proposing a new definition of gradient variance.
They show that the new definition is strictly stronger (more likely to hold in practice) than existing definitions, and derive convergence rates in convex setting.
The authors demonstrate an application of the new variance definition bounding the estimation error of MAP for one-dimensional Gaussian distributions.
strength_weakness: strength_weakness: While developing the new gradient variance definition is certainly interesting, I have the following concerns.

- The authors have shown that their gradient variance \\(\sigma_{\star, \eta}^2\\) is finite for every fixed step size \\(\eta\\).
The convergence rates in the convex setting are proved using constant step sizes, and thus the optimality gap does not vanish.
To make the optimality gap vanish, diminishing step sizes are often required, which is not covered in this paper.
Proving convergence with diminishing step sizes probably requires characterizing the average variance \\(\frac1T \sum_{t=1}^{T} \sigma_{\star, \eta_t}^2\\), which I think can be done only on a case-by-case manner depending on the specific application.

- The only case so far where this new definition shines while all other definitions fail is maximum likelihood estimation for one-dimensional Gaussian distributions.
This is very restrictive.
Is it possible to generalize this result to multivariate Gaussian distributions?
In addition, it would be great if the authors could provide other applications to further justify the necessity of this new definition.

Minor:
- Line 192: Add a period.
- Bad notation in Section 4.2: It might be confusing to use $\Sigma$ to denote the standard deviation.
Consider using a different letter like $s$ or $\tau$.
questions: questions: See the questions in the weaknesses.
limitations: limitations: NA.

Comments: title: Comment about assumptions and increase in score
Asymptotic results and relative strong convexity
Answers to rephrased Questions 1 and 2.
Rephrasing questions 1 and 2
comment: 1 - We agree that convergence in function values would be more suitable, unfortunately the assumptions from Hanzely and Richtarik [10] are too strong to be applied in this setting, which was one of the reasons for this work in the first place. 

4 - The Poisson inverse problem is to the best of our knowledge not relatively strongly convex in general (the Hessian of the mirror can blow up if one $x_j$ goes to 0, whereas the Hessian of the objective remains bounded as long as $A_i^\top x$ remains bounded away from 0). 

Regarding our optimality criteria in the plain convex case, we would like to emphasize the following point (shared answer with that to Reviewer HwBA): our results are non-standard **with respect to standard Gradient Descent results**, not mirror descent ones. As a matter of fact: 
- Dragomir et. al. (2021) only control $D_h(x_\star, x)$ in the relatively strongly convex setting and $D_f(x_\star, x)$ in the convex one. We additionally control $f_\eta(x) - f_\eta^\star$ in both settings, under a weaker variance assumption. 
- Loizou et. al. (2021) do not consider a mirror descent setting (besides the "vanishing variance" issue, which we tackle below).
- Hanzely and Richtarik (2021) make a very strong variance assumption, under which we have that $f_\eta(x) + \eta \sigma^2_{\rm sym} \geq \mathbb{E}f(x^+)$ (proof at the end of this comment), and so the control on $f_\eta$ gives a non-asymptotic control on $f$ in this case. Note that a similar control can be obtained from the variance Assumption from Appendix D. 

In particular, all other existing stochastic mirror descent analyses provide **weaker** results in terms of optimality metrics. We can recover control on function values either asymptotically or through stronger variance assumptions. To us, this is similar to the fact that standard relatively strongly convex Mirror Descent results only control $D_h(x_\star, x)$, but not $D_h(x, x_\star)$. 

Regarding the main application of the paper, we are in a similar position: as far as we know, existing results obtain bounds that hold either asymptotically or for $n$ large enough. This is because they bound other objectives, and then transfer their control to the right objective. Instead, we obtain anytime bounds, though on the reverse objective (and we are not aware of such bounds in other works). 

We have tried to obtain proper lower bounds to strengthen these claims on optimality criteria, but these are unfortunately very hard to come by as they would combine the difficulties of both the stochastic setting and the relative mirror descent setting (see, e.g, [1] for impossibility of acceleration in the mirror setting, which remained open for a significant time). 

We unfortunately do not have time to provide convincing numerical experiments in this rebuttal. One reason why we think that convergence in function values is not achievable without stronger assumptions is that our convex result is basically an equality (up to the removal of the $D_h(x_\star, x^{(k+1)})$ after the telescopic sum), so there is few room for improvement. Another is the one we gave you in the previous comment: the deterministic result follows the same scheme, but a simplification happens that allows to bound function values. This simplification does not happen in the stochastic case.
We would like to thank you for the fruitful discussions and your positive post-discussion summary. 

We will make the blanket assumption that $h$ is Legendre as you suggest, as we agree with you that it cleans up many corner cases without strong drawbacks.
**Regarding non-standard guarantees.** Your reasoning is correct and non-asymptotic guarantees on $f_\eta$ do not allow to obtain guarantees on $f$ a priori without further assumptions. Yet, we would like to emphasize that this non-standardness is **with respect to standard Gradient Descent results**, not mirror descent ones. As a matter of fact: 
- Dragomir et. al. (2021) only control $D_h(x_\star, x)$ in the relatively strongly convex setting and $D_f(x_\star, x)$ in the convex one. We additionally control $f_\eta(x) - f_\eta^\star$ in both settings, under a weaker variance assumption. 
- Loizou et. al. (2021) do not consider a mirror descent setting (besides the "vanishing variance" issue, which we tackle below).
- Hanzely and Richtarik (2021) make a very strong variance assumption, under which we have that $f_\eta(x) + \eta \sigma^2_{\rm sym} \geq \mathbb{E}f(x^+)$ (proof at the end of this comment), and so the control on $f_\eta$ gives a non-asymptotic control on $f$ in this case. Note that a similar control can be obtained from the variance Assumption from Appendix D. 

In particular, all other existing stochastic mirror descent analyses provide **weaker** results in terms of optimality metrics. We can recover control on function values either asymptotically or through stronger variance assumptions. To us, this is similar to the fact that standard relatively strongly convex Mirror Descent results only control $D_h(x_\star, x)$, but not $D_h(x, x_\star)$. 

Regarding the main application of the paper, we are in a similar position: as far as we know, existing results obtain bounds that hold either asymptotically or for $n$ large enough. This is because they bound other objectives, and then transfer their control to the right objective. Instead, we obtain anytime bounds, though on the reverse objective (which no other people obtain). 

We have tried to obtain proper lower bounds to strengthen these claims on optimality criteria, but these are unfortunately very hard to come by as they would combine the difficulties of both the stochastic setting and the relative mirror descent setting (see, e.g, [1] for impossibility of acceleration in the mirror setting, which remained open for a significant time).


**Comparison to other variance definition.** The "variance term" refers to the $\sigma^2$ term of the RHS of their Theorem 3.1, which is equal to $f(x_\star) - E\left[f_\xi(x_\star^\xi)\right]$, which does not go to 0 when $\eta \rightarrow 0$. This does not describe the actual behaviour of SGD, which is that the 'variance term' (as opposed to the term that depends on the initial conditions) vanishes when the step-size is small, allowing to obtain $f(x^{(t)}) - f(x_\star)$ (or other optimality criteria) arbitrarily close to 0 (with enough iterations and small enough step-size). We would obtain the same behaviour in our analysis if we were to use their variance definition. 

Instead, in our analysis, we replace $f(x_\star) - E\left[f_\xi(x_\star^\xi)\right]$ by $f(x_\star) - f_\eta^\star$, which goes to $0$ for $\eta \rightarrow 0$ (since the $1/\eta$ rescaled version has a finite limit as shown in Proposition 2.6). In this case, the optimality criterion can go arbitrarily close to 0 given enough iterations and small enough step-size.

 
**Final comment.** We agree that presentation and clarity are extremely important, and thus thank you for helping us improve them for our paper. We hope these points are now clearer to you, and that you are now in a more comfortable position to recommend acceptance for our paper.

**Proof of the claim.** We have that  $- \frac{1}{\eta} D_h(x, x^+) = \nabla f_\xi(x)^\top(x^+ - x) + \frac{1}{\eta} D_h(x^+, x) = \left(\nabla f_\xi(x) - \nabla f(x)\right)^\top (x^+ - x) + \frac{1}{\eta} D_h(x^+, x) + \nabla f(x)^\top (x^+ - x) $
and so 

$- \frac{1}{\eta} D_h(x, x^+) = f(x^+) - f(x) + \left(\nabla f_\xi(x) - \nabla f(x)\right)^\top (x^+ - x) + \frac{1}{\eta} D_h(x^+, x) - D_f(x^+, x).$

Taking expectations on both sides, we obtain using the relative smoothness of $f$ that:
$f_\eta(x) \geq \mathbb{E} f(x^+)  - \eta \sigma^2_{\rm sym}$, leading to the desired result. 

[1] Dragomir, R. A., Taylor, A. B., d’Aspremont, A., & Bolte, J. (2022). Optimal complexity and certification of Bregman first-order methods. Mathematical Programming, 1-43.
Thank you for the explanations. Even though I see the potential value of the paper, I have still some questions and concerns.

Question: You mention in the answer to me and Reviewer H5hK that the guarantee on $f_\eta$ is meaningful because $f_\eta \to f$. But I am not sure that this is an enough justification. This is especially because the paper wants to get non-asymptotic guarantees, whereas justifications such as $f_\eta \to f$ are only asymptotic. In particular, it seems you cannot convert nonasymptotic guarantee on $f_\eta$ to nonasymptotic guarantee on $f$, is this correct? If so, then I think one needs another way to justify that a nonasymptotic guarantee on $f_\eta$ is meaningful. I think a clearer connection is necessary here for different optimality metrics. Please let me know if I am missing something here.

Concerns: The discussions where you are comparing variance definitions are quite confusing, at least to me. And this is perhaps one of the most important parts of the paper so the reader can understand the contributions. This was the case when I was writing the review and it is still the case even with the rebuttal. This needs to be really improved, in my opinion. For example, the discussion on lines 201-210 is quite confusing. You say "The vanishing variance term can be obtained by rescaling by $1/\eta$" which I am sure is very clear to the authors but not to the readers. Can you clearly describe what you mean by "vanishing variance term". It is confusing because earlier you talk about step size reducing the variance. But when you scale $f(x_*) - E[f_\xi(x_*^\xi)]$ by $1/\eta$, of course smaller $\eta$ makes this quantity larger. I guess what you call the "variance term" is different. But please be more explicit. 

Lastly, I want to emphasize that presentation is also extremely important since at the end we, as reviewers, and the authors want to make sure that the paper will be received well by our community. Especially given the volume of papers that appear in our conferences, I believe making papers as clear as possible and as readable as possible is extremely important to make sure that the community can read and understand the developments.

If the authors can justify the non-standard guarantees (not on objective value) for the main application of the paper and promise to improve the presentation, I can push my recommendation to a "5" which is an accept rating, but my reasons are outlined above for why I am not comfortable raising the score more than that.
I would like to thank the authors for carefully addressing my concerns.

I would still suggest/insist the authors make the blanket assumption that $h$ is of Legendre type (note that $h$ does not need to be of Legendre type on $C$ but on maybe a larger set as long as you add the Bregman projection in the algorithm). The reason for that is two-fold:
- A mirror map of Legendre type is close to being a minimal set of assumptions on $h$ for mirror descent to be well-defined (which might even then not be enough, as discussed by Bubeck in "Introduction to Online Optimization", Sec. 5). I agree that Assumption 1 cleanly handles many of the examples covered in Sec 3, but when the authors try to change assumption 1 to only hold on the iterates, this makes it unclear what are the assumptions on $h$. I don't think assuming $h$ is Legendre will rule out any applications the authors consider and will make other researchers that worked on mirror descent like myself less worried about corner cases. For example, mirror maps of Legendre type allow the use of Bregman duality more cleanly (Lemma 5.1 of Bubeck in "Introduction to Online Optimization"). Without this assumption the gradient map stops being a bijection and one might be able to cook up weird corner cases;
- Mirror map being of Legendre type was used when relative smoothness was first introduced by Bauschke, Bolte, Teboulle, as well as in the by most classical texts covering mirror descent. For this work I can't see exactly the advantage of letting go of such a "classical" assumption. The disadvantage is that it makes readers acquainted with mirror descent worried about correctness of the paper. This is not a journal submission, so I am not verifying all the proofs, but from the rebuttals it seems like the authors essentially only look at functions of Legendre type, so you might as well say it explicitly to not make readers worry.
---

**Post-discussion summary:** Ultimately, this discussion on assumptions is more on the organization of the text and on the writing, not on the contributions of this submission. This is a very hard theoretical problem (which one can gauge by the amount of previous work with only partial results or restrictive assumptions). The partial solution to the conjecture on non-asymptotic convergence of MAP showcases the potential usefulness of these ideas for future work. Thus, I vouch for acceptance of this paper, since I believe it is of interest for the ML optimization community and can clearly be of inspiration for future work.
1. It was a typo, I meant "asymptotic" results were already known before, e.g., discussed in Section 5 of Le Priol et al. [17]. My concern here is that whether the bound on the reverse KL is meaningful in this problem, because it seems to say nothing about $f(\theta) - f(\theta_*)$. The convergence in function value as in Hanzely and Richtárik [10] would be more suitable. 

2. You're right, relative strong convexity is weaker than strong convexity only if h is strongly convex, which you don't assume here.  

3. I am not entirely convinced about this statement "it simply does not seem to be achievable in our setting." Just because the proof doesn't go through easily in function value, does not mean the function value convergence is not achievable. Why the authors think it is not possible? If the authors can provide a convincing numerical experiment or a counter-example to show that the function value might not converge under these assumptions, I will be happy to increase my evaluation.

4. I believe the lack of convergence in function value in convex case is really important to clarify because it limits the applications of the results a lot. RE another application, Poisson inverse problems, suggested by the authors in the general response is also unclear if it is relatively strongly convex or not in general (even for a positive definite matrix).
I acknowledge that I have read the rebuttal. I am satisfied provided that the authors add the extension to multivariate Gaussians.
Thank you for your quick reply, for engaging in the discussion, and for giving us time to respond. We greatly appreciate it. 

**Question 1.** We replace the Legendre-type assumption by Assumption 1, where twice continuous differentiability, strict convexity and well-definition of the the conjugacy problems (within the interior of $C$) ensure all the good properties we need for the derivations (since the gradient map is injective and so can be inverted on its image). We use this version of the Assumption following Dragomir et. al. (2021), to be able to write the 'Hessian formulation' of Bregman divergences, which we believe is often easier to interpret.

If we do not want to assume that $h$ is twice continuously differentiable, then we would need to assume that it is Legendre on $C$ as you suggest, in order to be able to write duality for instance as you point out. We could also just assume Legendre and second-order differentiability when we would like to write out Hessians.  

Note that the L2 norm case is already cleanly handled with Assumption 1, since it imposes that the solution of the 'duality problem' is unique and lies within the interior of $C$ (which is essentially usually guaranteed by the Legendre assumption), which would not be the case if $h$ included a projection term. 

**Question 2.** We will remove the mention about relaxing assumptions right after Assumption 1, and replace it by the fact that Assumption 1 can be replaced by assuming that $h$ is Legendre if one does not have second-order continuous differentiability. 

Then, we will explicitly state in Section 2 that we give sufficient (but not necessary) conditions for several good properties of the variance to hold. 

Finally, we will give Assumption 2, a minimal assumption for Theorems 3.1 and 3.3 to hold, which are essentially well-definition of the iterates in the form of (3), and existence (in the sense of finiteness) of all the manipulated quantities. We will highlight that although these can be obtained using results in Section 2 (and the corresponding assumptions), they can also be obtained case-by-case for specific problems (as in Section 4). 

Thank you again for giving us the opportunity to clear up our answers, we are still available for further clarifications. We are fully aware that there is only so much time you can spend on a review, and we appreciate that you took the time to rephrase your questions so we can hopefully better address them. Regarding the appendix, we recommend first the proof of Lemma C.1, which is just a few lines without advanced arguments. Appendix E is longer and harder to read (introduces a few notations).
Thanks a lot for the authors for the detailed reply! I think the main point of my first two questions was not addressed, in part because I don't think I have properly written them. I will try to rephrase the questions, trying to be brief and clear. I do not expect a long answer either, but question 1 is something I am confused about and question 2 is asking for precise statement of the assumptions used.

**Question 1: Do you need $h$ to be of Legendre type?** Assuming the mirror map is of Legendre type is a classical assumption to ensure everything works out in mirror descent. So it is not clear to me whether the authors need to go beyond Legendre type (which I do not think is the case) or if it is actually necessary for it to be of Legendre type. If so, it should be stated clearly the domain and everything (this would, for example, clear up the L2 norm case). I will take a look at appendix E later just in case.

**Question 2: What are the formal statements of the assumptions used?**. Assumption 1 is a formal statement of the assumption used in Sec 3. But in Sec 4 the authors quickly mention that the assumption needs only to hold for the iterates... but then it is not clear what assumptions are needed on $h$. So there should be some sort of "Assumption 2" that clearly states all the assumptions on $h$ and/or the iterates. Then, at the beginning of each section the authors should explicitly say which assumption is being used (or mention on the theorems which assumption is used). Currently which were the assumptions necessary at each point was the part that confused me. Like I mentioned before, I think the authors should still explicitly assume that $h$ if Legendre (so that many of the properties of Bregman divergences work, for example) and formally state the assumptions mentioned in Sec 4. 

If I have the time I will also look at Lemma C.1. I just wanted to write a reply early in the discussion period to allow for the authors to write a reply without any rush. Again, I don't expect long answers, but these are my main points of confusion, that is why I am trying to rephrase the questions.