Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize
Authors: Ryan D'Orazio
Nicolas Loizou
Issam H. Laradji
Ioannis Mitliagkas
Venue: Accepted by TMLR ()

Abstract: We investigate the convergence of stochastic mirror descent (SMD) under interpolation in relatively smooth and smooth convex optimization. In relatively smooth convex optimization we provide new convergence guarantees for SMD with a constant stepsize. For smooth convex optimization we propose a new adaptive stepsize scheme --- the mirror stochastic Polyak stepsize (mSPS). Notably, our convergence results in both settings do not make bounded gradient assumptions or bounded variance assumptions, and we show convergence to a neighborhood that vanishes under interpolation. Consequently, these results correspond to the first convergence guarantees under interpolation for the exponentiated gradient algorithm for fixed or adaptive stepsizes. mSPS generalizes the recently proposed stochastic Polyak stepsize (SPS) (Loizou et al. 2021) to mirror descent and remains both practical and efficient for modern machine learning applications while inheriting the benefits of mirror descent. We complement our results with experiments across various supervised learning tasks and different instances of SMD, demonstrating the effectiveness of mSPS.

Published in Transactions on Machine Learning Research (11/2023)
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Step- size
Ryan D'Orazio
ryon.doruzio @rriia quebec
Mila, Université de Montréal
Nicolas Loizou
aloizou&tjhe edu
Johns Hopkins University
Issam Laradji
issam Saaam.aarddjj@@mmi...co
ServiceNow Research
Ioannis Mitliagkas
tounnis &iroo www.rnnnaaarr..rurrrrraaaaaaa www.ntrallccccco.mmmm
Mila, Unéversité de Montréal
Canada CIFAR Al Chair
Reviewed OpenReview: https: /tttps://openreviaau
openreview. net/ forum? id= 286Q1PWwlll
Abstract
We investigate the convergence of stochastic mirror descent (SMD) under interpolation in relatively smooth and smooth convex optimization. In relatively smooth convex optimiza- tion we provide new convergence guarantees for SMD with constant stepsize. For smooth convex optimization we propose a new adaptive stepsize scheme - the mirror stochastic Polyak stepsize (mSPS). Notably, our convergence results in both settings do not make bounded gradient assumptions or bounded variance assumptions, and we show convergence to neighborhood that vanishos under interpolation. Consequently, these results correspond to the first convergence guarantees under interpolation for the exponentiated gradient al- gorithm for fixed or adaptive stepsizes. mSPS generalizes the recently proposed stochastic Polyak stepsize (SPS) (Loizou et al.) 2021 to mirror descent and remains both practical and efficient for modern machine learning applications while inheriting the benefits mirror descent. We complement our results with experiments across various supervised learning tasks and different instances of SMD, demonstrating the effectiveness of mSPS.
1 Introduction
We consider the constrained stochastic optimization problem,
min
f(x) Te [fe(x)) ZE
(1)
where X' C Rdd is non-empty closed convex set that is possibly unbounded, and & a random vector supported on set such that Eg [x]] is always well defined. We assume that is possible generate sequence of independent and identically distributed (i.i.d.) realizations of &, and that for each A Eg [V]{(x)] = (z)). We use X. C X to denote the set of minimizers of ① and assume that X. is not empty.
A special case of interest the finite-sum optimization problem where E = (1....,,, m) and Eg [fe(z)] = Σ f(x)) Finite-sum optimization problems often used in machine learning tasks where vector æ

---

Published in Transactions on Machine Learning Research (11/2023)
denotes the model parameters, fi()) represents the loss on the training point i and the goal is to minimize the average loss f() across the training points while satisfying the problem constraints (expressed as x E 2).
A common iterative approach to solve 1 when X' = IR is stochastic gradient descent (SGD) Robbins & Monro 1951 Gower et al. 2019), iterates are updated the negative direction of a gradient computed from a single realization g. When the problem is constrained, X' C IRd, one may employ projected methods such as stochastic projected gradient descent (SPGD). However, the convergence guarantees of both SGD and SPGD depend values measured by the Euclidean norm. If the Euclidean structure is not naturally suited to the problem, then SGD and PGD can suffer worse dependence the dimension d. A powerful generalization of SGD and SPGD is stochastic mirror descent (SMD), permitting better convergence guarantees by matching the geometry of the problem (Nemirovski & Yudin 1983 Beck & Teboulle (200)). For example in some cases, SMD can improve SGD's vd dependence to v /log(d) (Ben-Tall et al. 2001 Beck & Teeooulle 2003).
Furthermore, mirror descent. leverages non-Euclidean projections, allowing for different choices projections that are perhaps better suited to the constraint set. For example, in sequential games particular instances of mirror descent. have been designed to allow for efficient projections on the stralegy spaces of players (Hoda)
et al.
2010 Kroer et al. 2020).
A classical analysis of mirror descent and first-order methods often relies on smoothness with respect to some norm |-||- The norm ||-I| is often used in selecting the appropriate instance of mirror descent (Dekel
et al. 2012 Bubeck 2015). However, a recent trend is to study non euclidenn methods like mirror descent
with the more general assumption of relative smoothness (Birnbaum et al.] 2011; Bauschke et al.) 2017 Lu et al. 2018). Several applications of interest are not smooth but relatively smooth, e.g., algorithmic game theory (Birnbaum al. 2011); Poisson inverse problems (Bertero et al., 2009;; and more (Lu et al. 2018
In contrast to deterministic methods, stochastic methods under relative smoothness have received less alten- tion. We contribute to the literature of SMD with new constant-stepsize results under relative smoothness and new adaptive-seepsize results under smoothness, both of which use weak assumptions on the noise.
1.1 Main Contributions
The key contributions of this work are as follows:
Technical assumptions on the noisc. Unlike most of the SMD literature, all our convergence results, with relative smoothness or smoothness, and for fixed and adaptive stepsizes, do not make bounded gradient bounded variance assumptions. Instead we use the finite optimal objective
difference, introduced by Loizou et al. (022I), for our adaptive smooth setting and introduce new constrained version for the relative smooth sctting. More preciscly, Loizou et al. 2021 assume
= f(.)) - EE [Jē] < <0,
(2)
where f(x,) = min f(x), ft = inf fe(x). In the finite-sum case, E |f E 5. For our relative smooth results we introduce the construined finile optimal objective difference, a refinement that depends on the constraint X,
= Be [2)) 00,
n where f (x) infzex fi(x)) and in the finite-sum case E [ (2)) >m infaex fi(e). From definition we have that the constrained version is a weaker assumption than its unconstrained counterpart since 22 o²
Novel adaptive SMD. We propose the mirror stochastic Polyak stepsize (mSPS) as an adaptive stepsize for SMD. Contrary to most adaptive mirror descent methods for stochastic optimization we do not use an ouline to batch reduction (Cesa-Bianchi et al., 20044; Littlestone) 1989.. Hence, we avoid common assumptions like bounded constraints and provide efficient convergence results like linear convergence under strong convexity and smoothness.
Exact convergence with interpolation. In modern machine learning, overparametrized models capable of driving training error to zero have increasingly become important. in both theory and
2

---

Published in Transactions on Machine Learning Research (11/2023)
in practice (Ma et al. 2018 Zhang et al. 2021]. Under these conditions (see Definition 4 it has been shown that SGD enjoys favourable guarantees with exact convergence (Ma et al. 2018) Our analysis with o², and ox, shows that SMD inherits similar guarantees with fast and exact convergence under interpolation. We are unaware of other similar results for SMD with adaptive stepsizes. Moreover, our results provide the first convergence guarantees under interpolation for the exponentiated gradient algorithm under both the relative smoothness and the classic smoothness settings.
Extensive numerical experiments for adaptive SMD. We demonstrate the adaptive capability of our proposed adaptive stepsize across a wide variety of domains and mirror descent algorithms for both constrained and unconstrained problems.
2 Related Work
Stochastic Mirror Descent. SMD is often analyzed stochastic method for optimizing non-smooth
Lipschitz continuous convex functions (Nemirovski et al. 2009 Bubeck 2015 Beck 2017). These results can
be derived from online to batch reductions yielding O(IvT) convergence rale "Cesa-Bianchi et al. 2004
Duchi et al. 2010 Orabona 2019). In the case of non-smooth and strongly convex, several works improve the results following from online regret bounds with a 0(!/r) convergence rate (Hazan & Kale 2014 Ghadimi
& Lan 2012
Juditsky Nesterov. 2010). Under smoothness, similar improvements can be made (Dekel
et al. 2012 Bubeck| 2015). All of these results use bounded variance or bounded gradient assumptions These assumptions can be difficult to verify, and may impose further restrictions. For example, one cannot in general assume a bounded gradient with strong convexity if X' is unbounded, thercfore it is common to assume X' is compact.
In relative smooth optimization Hanzely& & Richtarik (021) make an assumption similar to bounded variance. More recently, Dragomir et al. (2021) avoid making bounded variance or bounded gradient assumptions under relative smoothness but make larger restrictions on the class of problems and mirror descent methods. We make an in-depth comparison with these works in Section 5 We also add that there are several works related
to randomized coordinate descent methods (Hanzely & Richtarik] 2021: Gao et al. 2020 Hendrikx et al.
2020), and with variance reduction (Hendrikx et al. 2020 Dragomir et al. 2021
Interpolation in constrained optimization. SGD in unconstrained settings (Gower et al. 2019 Vaswani et al., 2019al or with SMD and conditions that do not incorporate constraints Hanzely & Richtarik (2021). Consequently, these conditions can yield large
Interpolation conditions have mostly been studied with
unbounded neighborhoods of convergence in constrained iolimizatiion. Xiao et al. (2022) addresses some of these shortcomings by introducing the variance based weak growth condition to model interpolation under stochastic constrained optimization. However, the condition only holds under interpolation and requires the variance to be zero at the optinuum. In comparison, our constraint-aware condition o% can hold without interpolation and does not require variance to be zero at the optimum.
Adaptive stepsizes. Adaptive stepsizes for mirror descent have a long history. Accumulating, past gradi- ents or subgradients to set a stepsize, NJ x 1/v 1l., can be traced back online learning (Auer al,
2002 Streeter & McMahan 2010 Recently, similar coordinate-wise stepsizes such as ADAGRAD (MeMa- han & Streeter 2010 Duchi et al. 2011 have been proposed. The convergence guarantees for these methods in convex optimization use online regret bounds, requiring sublinear regret. Unfortunately, all mirror descent methods with the aforementioned stepsizes require a bounded constraint; when the problem is unconstrained
Orabona & Pal (2018) prove a I(()) worst case lower bound for the regret. ? Furthermore, in the stochastic case, bounded gradient and variance assumptions are made when using the online to batch reduction (Duchi
2018 Orabona
2019 In contrast our methods employ a completely different stepsize and we make a very
Lci & Tang (018 derive results for non-smooth and strongly convex functions without bounded subgradients but assume
weak growth condition.
2 CConvergence results may still possible without online to batch reductions; for example, the case of unconstrained SGD
see Ti & Orabona (0019).
3

---

Published in Transactions on Machine Learning Research (11/2023)
weak assumption the noise. Another line of related work includes adaptive stepsizes for mirror descent Bayandina et al. 2018 Stonyakin et al. 2019).
with non-smooth functional constraints [Bayandina] 2017
Polyak stepsize. Our adaptive stepsizes are in the spirit of Polyak's stepsize originally proposed for deterministic projected subgradient descent. (Polyak) 1987). In the deterministic setting Polyak's results have been been successfully extended and used for solving weakly convex and smooth problems (Boyd et al, Davis et al. 2018 Hazan & Kakade 2019). More recently, variations of the Polyak stepsize have
2003
been
proposed for stochastic optimization (Loizou et al., 2021 Prazeres & Oberman, 2021 Berrada et al.
2020
Gower ct al. 2021). The adaptive stepsizes proposed hercin are a generalization of SPS proposed and
anal snaly by Loizou et al. 2021
(see Section
4.2 to the constrained case and for mirror descent.
3
Background
We denote vectors within the feasible set as E X' C Rd, where R is the set of real numbers. We use the subscript to denote time, after time steps the average of the iterates 21.-. 3t is Ht 1/2 Ee_ 2g. With slight abuse of notation subscript refers to time or the coordinate is clear from context. We denote ||-1|p the Euclidean norm and |1-11 as any arbitrary norm with corresponding dual norm ||~||, = sup, (z, y) |Blll S 1}.
may also refer to the ith coordinate of
2i, x (æ1, za). Whether the
For a differentiable function e we define the difference between vb(x) and the first order approximation of it at y as the Bregman divergence (x v).
Definition 1 (Bregman divergence). Lel 1b D - IR be differentiable on int D. Then the Bregman divergence with respect to sb is By : D x int - I, defined as
Bx (xx) - (b()) x
A diffcrentiable function f is convex on a convex set X' if (2; v) 2 0 for any x, E X. Similarly, function
f is I-smooth with respect to norm ||+II if By 1/2 yl and is p-strongly convex with respect to the norm ||-I1 if || - y/1 < (y
We will also refer to the generalization of smoothness and strong convexity - relative smoothness and relative strong convexity defined below.
Definition 2. A function I is L-smooth relative to vp on X if for all (z, v) E Xx int D) il holds that: (y(x; S LB
Definition 3. A function f is u-strongly conver relative to on X if for all (I,z) E X x (X int D) it holds that: (B v) I (x(x;)).
3.1 Mirror descent
To solve problem [ we consider the general stochastic mirror descent update with a convex function & and domain D
1 (o( nt
It+1 arg min mig (z), + zEX
(4)
Where & a realization of g that is i.i.d. In the non-smooth or deterministic setting V.g, (2:) may be replaced by subgradient the full gradient respectively. To make the updates well defined, all require is that 3141 int D in update 4 otherwise 2x(+24441 will be undefined al the next step.
Assumption 1. Let zi be convex with domain D, differentiable over int D, and C D. For any g, and ony stepsize 1/. 0, Z++1 = arg minzex x),x) By(x; x.) E int D.
For example the following assumption by Orabona (019) would be sufficient..
4

---

Published in Transactions on Machine Learning Research (11/2023)
Assumption (Section 6.4 Orabona 2019 ). Let vp : D + R de strictly convez function such that X' C D, we require either one of the following to hold: limz-ax [[b())] +oo or X int DD
The first requirement from Orabona 2019) amounts to assuming vb is Legendre function (i.e., essentially smooth and strictly convex), which implics that I++1 E int D (Cosa-Bianchi & Lugosi 2006). Otherwise, if the second condition holds then the update is also well defined. Furthermore, we note that other assumptions can be made to guarantee ž(+1 E int D; for more examples see Bauschke et al. (2003).
Another common assumption is to assume & is strongly convex over X, which will be important for our adaplive stepsize in Section however, is not needed for the constant step size results of Section
The following is standard one step mirror descent lemma and will be used often (Beck 2017 Bubeck 2015
Orabona 2019 Duchi, 2018), this particular statement and proof is taken from Lemma 6.7 by Orabona (2019) and we include the full proof in the appendix for completeness. All other omitted proofs are deferred to the appendix.
Lemma 1. Let By be the Bregman divergence with respect to conver function v6 D - R and assume assumption 7 holds. Let I++1 = arg miggex (g. x) + nh (x; Then for any Is E X
Be(xa:3411) (B)(I))))) n (gt, It x.) (2(244133))) + m (gt, It T141).
(5)
Furthermore if a/ is py--trongly conver over X' then
(2( (Bo(Fr)))) - (9 xx.) + 24
mi
|1 11:
(6)
The SMD update
44) recovers both SGD and SPGD if ab is taken to be 1/ 11:113. Some other interesting
examples include the case where (xxx = 2 ||= for < $
2 Grrve et al. 2001 Gentile 2003). If we instead
use (xx) 1/2 (a. Mr) || 1/2 for positive definite matrix M then we recover the scaled projected gradicnt algorithm, 1z+1 arg min || - 7MM 9t =I1a, (Bertsekas & Tsitsiklis 2003). Another common setup
is when vi is taken to be the negative entropy with constraint set X' = A {z; 0 인; 1}. In this case & is 1-strongly convex with respect to ||-1], and the update rule corresponds to the exponentiated
gradient algorithm [Littlestone & Warmuth 1994 Kivinen & Warmuth 1997 Beck & Teboulle
2003 Cesa-
Bianchi & Lugosi 2006).
3.2 Overparameteriiation, interpolation, and constrained interpolation
Modern machine learning models are expressive and often over- pee-pparamtrized, i.e., they can fit or interpolate the training dataset (Zhang et al.] 2021). For example when problem 11] is the training problem of an over- parametrized model such as a deep neural network (Ma et al. 2018 or involves solving a consistent linear system [Loizou & Richtárik, 2020b a) or problems such as deep matrix factorization (Rolinek & Martius 2018 Vaswani et al.] 2019b), each individual loss function fa attains its minimum x.. That is the following interpolation condition is satisfied.
Definition 4 (Interpolation). We say that the interpolation condition holds when there exists x, E X, such that fe(x.) inf fe(x:) almost surely.
In the finite-sum setting this condition amounts fe(xx) = inf fe( for all (1,--. ,n). Note that when the interpolation condition is satisfied, it follows that 0² = 0 (see (2)
The use of interpolation in the literature has mostly been discussed within the context of unconstrained optimization. Despite Definition 4 being designed to study SGD for unconstrained optimization, we show that constrained optimization with minror descent enjoys similar convergence benefits if o² = 0. However, the standard definition of interpolation, as given by Definition 4 does not adequately describe interpolation with respect to the constraint X. For example, consider the case where f((x) f(x) for all x E X but do not
3yX denotes the boundary of X.
5

---

Published in Transactions on Machine Learning Research (11/2023)
agree outside the constraint X. In this case, it is possible to have o² arbitrarily large, meanwhile, there is no variance in the stochastic gradient E [) ( = 0 rendering the problem non-stochastic.
Xiao et al. (0022) describe an interpolation-lice condition within constraint optimization, however, this condition requires the stochastic gradient to have zero variance the optimum, which need not hold generally despite all f& sharing a common minimum (see for example Figure 1 Therefore, we also make of the following constrained interpolation condition:
Definition 5 (Contrained Interpolation). We say that the interpolation condition holds with respect the constraint. X if there erisls x, E X. such that. fe(x.)) infzex fe(*) almost surely.
Similar to Definition 4 we have interpolation with respect to X' holds when d3 = =0. In the finite-sum setting, constrained interpolation reduces to fa(x.) infzex fi(x)) for all E ,n,...,,.
4
Constant and Polyak stepsize for mirror descent
In this section we provide background on constant stepsize selection for mirror descent. For non-constant setpsize, we introduce our natural extensions the classic Polyak stepsize and SPS for mirror descent.
4.1 Constant Stepsize
When function is L-smooth with respect to the Euclidean norm, common stepsize for gradient descent is 7 1/2, allowing for convergence in many settings (Bubeck 2015). Similarly for L-relatively smooth function with respect to v) the prescibed stepsize for mirror descent using vb is 17 1/z. (Birnbaum et al. 2011
Lu et al. 2018). In the stochastic and relatively smooth case, Hanzely & Richtarik (2021) use 1) = 1/2 as well as different stepsize schedules. In Section 5. we provide new convergence guarantees (under weaker assumptions) for SMD with rj = 1/r.
4.2 Polyak Stepsize
An alternative method to selecting stepsize, suggested by Polyak (Polyak 1987). is to take The by minimizing an upper bound on || 1.112- From Lemma 1 if take t II: 2 and assume It. (x)))
is subgradient at 24 for f then recover well known inequality for projected subgradient descen
|/ ||.. 1+t1l12 S ||=-- sell2 (e([(x)) - f(x.))
11 12.
Minimizing the right hand size with respect to t, yields Polyak's stepsize, = f(x))-((x.))) (Polyak
1987 Beck 2017). Following in a similar fashion, we propose a generalization of Polyak's stepsize for mirror
descent. ih is Me-strongly convex with respect to the norm ||-|| then we can minimize the right hand side
of equation G to arrive at the mirror Polyak stepsize
= (x(e)) f(x.))
(7)
119.112
Despite the well-known connection between projected subgradient descent and mirror descent (Beck Teboulle, 2203),, this generalization of Polyak's stepsize is absent from the literature. For completeness, include analysis of the non-smooth case in Section of the appendix, including both O(Ivit) conver- gence and last iterate convergence result. As expected, mirror descent with the mirror Polyak stepsize maintains the benefits of mirror descent - it permits mild dependence on the dimension of the space.
4 After using the fact that ga subgradient, f(x) f(x)) (gt, x-). Without loss of generality could assume v he 1-strongly convex and scale 1 by 1/pg- The stepsize would remain the
same, scaling inversely scales the stepsize.

---

Published in Transactions on Machine Learning Research (11/2023)
However, it inherits the impractical issues with the Polyak stepsize knowledge of f(x)) and exact gradient or subgradient.
In the stochastic setting Loizou et al. (2021) propose the more practical stochastic Polyak stepsize (SPS), M = f/ellll (=))le and the bounded variant SPSmax T = (x.)) (u.)) no). Where f.. known many machine learning applications, and scaling parameter that depends on the class of functions being optimized (Loizou et al. 2021).
Similar to generalization of Polyak's stepsize
propose a generalization of SPS and SPSmax for mirror descent, the mirror stochastic Polyak stepsize (mSPS) and the bounded variant mSPSmax.
[o (Z.)
mSPS np
(8)
c cllVfe. (x+))1
Moo (o (2:1) - 136)
mSPS 1/ min
(9)
c|lV fe, (sr:))
4.2.1 Self-bounding property of mSPS
An important properly of SPS and mSPS is its self-bounding property for when Se. is L-smooth and strongly convex with respect to a norm ||-11,
(f.. (2t) fā.) I
Pv 2cL S 1)
Hs 2cp
(10)
We extensively use the lower bound, also known the self-bounding property of smooth functions (Srebro et al. 2010), and provide complete proof in the appendix (Section Eb. A proof of the upper bound can be found in Orabona (2019)[ [Corollary 7.6].
5 Convergence with constant stepsize in relatively smooth optimization
In this section we provide new convergence results for SMD with constant stepsize under relative smoothness. We provide the following lemma which allows us to bound the last two terms in (5) This result can be seen as a generalization Lemma 2 in Collins et al. (2008), where the exponentiated gradient algorithm is studied under the relative snoothness assumption.
Lemma Suppose f is L-smooth relative vh Then if 1 we have
-B f()) - s n(f(x)) f(441)).
5.1 Relative smoothness and strong convexity
For appropriately selected stepsize, have that SMD enjoys linear rate of convergence to neighbor- hood of the minimum I..
Theorem 1. Assume vb satisfies assumption D Furthermore assume f to be p-strongly conver relative to &o over X, and fe to be L-smooth relative to vp over X almost surely. Then SMD with stepsize S 1 guarantees
ox
E [Bo < (1 -1- By
Importantly, we do not assume f& to be convex and under interpolation with respect X we have ox = 0 implying SMD will converge the true solution if & is strictly convex. strongly convex then Theorem provides linear rate on the expected distance || 2= for some norm ||-||- For example Collins al. (2008) show that a particular loss Se appearing in the dual problem of fitting regularized linllinear
7

---

Published in Transactions on Machine Learning Research (11/2023)
models is both smooth and strongly convex relative to the negative entropy function. In this case, results provide linear rate on E || - x.- [l] for the stochastic exponentiated gradient algorithm since & (negative entropy) is strongly convex with respect to the norm ||-111-
In the case of interpolation, we have that (2(2))1441) + 0 almost surely. If t is strictly convex then
2t - v, almost surely.
Corollary 2. Under the same assumptions as Theorem 1 if xx then Belxa) 0 almost surely.
5.2 Relative smoothness without convexity
Similar to Theorem we show convergence of a quantity to a neighborhood, only assuming fe to be L-smooth relative to V) where or fe need not be convex.
Theorem 3. Assumne &b sotisfies assumption 7 Purthermore assume fe to be L-smooth relative to tb over X' almost surely. Then SMD with slepsize n guaranlees
By(csiz))
Bol + oxx <
E
np
The above guarantee also implics a result for the "best" iterate if f is convex, [minigast ()(2=:;))), to neighborhood. II f is strictly convex then this implies least one iterate I, converges to neighborhood of Is in expectation. If is strictly convex and 1-coercive then its conjugate function f is also strictly convex (Hiriart-Urruts & Lemarécha] 2004) [Corollary 4.1.3] and we have (x,55 = (V
[Bauschke et al.) 1997]] Theoremn 3.7,, implying that the average gra- dients E s=1 Vf(x.) at least one of Vf(x,) converges to neighborhood of Vf(x). If happens to be convex and L-smooth with respect to norm ||-I1 then z f fz(.))) s Bz(2,;; 22, (Nesterov 2018) [Theorem 2.1.5], providing a similar convergence guarantee on the distance of gradients to Vf(x)).
(,)
Similar to Theorem D almost surely convergence result follows from Theorem under interpolation.
Corollary 4. Under the assumplions of Theorem if f is convex and 0x 0 then By(x.; 0 almost surely.
5.2.1 Application of Theorem 3 solving linear systems
Theorem 3 provides convergence for the unconventional quantity By(x.; however, this quantity is some- times equal to f(x)) - fxx)), as in the case of solving linear systems. In this case Theorem 3 aallmaticaaly gives result for the quantity E [f - [xx)] if f is convex.
More formally, solving a constrained lincar system amounts to to finding x, such that
Ar. b, and v. X.
(11)
Problem 11 can be reformulated as constrained finite sum problem with fi(x) ((A,, b,)² where Ae and 6; denote the tt row and component of A and b respectively. Note that interpolates all ft since f((x.) 0 by construction, with ff. = O and ox = 0. Since the divergence B,, is symmetrid and Bj is simply the average over By. it holds that
By(1.11))= Σ BB((..5))) n
f((x)) Si(xa) f(x.) - f(xx).
Where the third equality follows from the fact that Vf((F.) = 0.
Theorem therefore gives a convergence result for the gap E [f - f (xx)), and Corollary guarantees f(x)) + f(x), provided each f. is relatively smooth. Relative smoothness of holds if ab is strongly convex
CA function 1-cocrcive if lim|jall-+oo /(*\/||a|| +00. 7ee Proposition in the appendix for a proof.
8

---

Published in Transactions on Machine Learning Research (11/2023)
since for any norm ||-| there exists a constant Lg for which fa is L,-smooth with respect to |1-11. Therefore, taking I. = max; 14 gives
2 x - y/1² Tup
(x: S
|| - y/1 (x(x;))-
2p
5.2.2 EG for finding stationary distributions of Markov chains
An important example of problem [1] for which I, exists and X' o Rd is the problem of finding a stationary distribution of a Markov chain with transition matrix P. That is, to find v. such that
- 0, and I. E A..
(12)
Problem 12 is ubiquitous in science and machine learning, for example in online learning many algorithmss
require computing a stationary distribution of a Markov chain at each ileration aaaaiion/Greewaldd et al. 2006; Blum
& Mansour 2007
From the above discussion we can formulate the problem 12 as a finito-sum problem with constraint X' = Am. A natural choice for the simplex constraint is the stochastic EG algorithm (SMD with d taken to be negative entropy). Denoting the 9i (PT - 1)x we have that f((x) (g., x)),, and is 1-smooth with respect to 11-111- Since negative entropy is 1-strongly convex with respect to I|-112 we have that fi is also 1-smooth relative to vb Therefore, Theorem 3 and Corollary 4 guaranttee E [f(T) f(x))] and f(x)) - f(x,)
converge to zero, respectively, for the following stochastic update: sample E (1, ... ,n] uniformly at random and
V1+1
Zg
exp (- fz())) F++1 119--1li
V6+1
(13)
Where and exp are component wise multiplication and component wise exponentiation respoctively,
We highlight that other existing works show convergence without a neighborhood under interpolation for the EG algorithm. Additionally, problem [2 also exhibits natural occurence where f is known and equal to 0, rendering mSPS (8] computable. In Section we demonstrate similar guarantees with mSPS.
5.3 Comparison with related works
In the constant stepsize and relatively smooth regime, Hanzely & Richtarik (2021) and Dragomir et al. (2021) provide convergence guarantees for SMD under different assumptions and to different noighborhoods. Wo provide an in-depth comparison as well as demonstrate via an example where convergence to the solution is not guaranteed by previous works but possible by Theorem
Hanzely & Richtarik 2022 make /. I o², where ž441 is the mirror descent iterate using the true gradient Vf(x).. In the case of relative smoothness and relative strong convexity they show linear rate of conver- gence to neighborhood for E [f(ž.) - fxx)]] (Theorem 5.3), where I; is a particular weighted average of the iterates (#1,.... ....,,,)))) 22). Without relative strong convexity, a similar result is shown for the uniform average 7, with a rate of O(1/)) using a particular schedule of stepsizes (Corollary 5.5).
assumption akin to bounded variance, they assume
Our results more closely resemble the work of Dragomir et al. (2021) giving the same rates and exact convergence with interpolation (Theorem 1 and Theorem 3), however, there several important differences. Firstly, our results apply to wider range of problems and mirror descent methods. Dragomir et al. (2021) do not decouple the domain D of the function t and the constraint set X' they assume that Zz+1 E int X where Ve((=++1) = Vv((x;) - тΙ. Se, (Ix). Therefore their definition of mirror descent precludes the famous exponentiated gradient algorithm or projected gradient descent no projection steps are allowed in their definition. Furthermore, our analysis allows x, to be anywhere A' while Dragomir et al.) (202T) require ff(2.) 0 and exclude the case when I. is on the boundary of X. Secondly, our neighborhoods of convergence different, they show convergence to different neighborhood 1/2/vu (nn² in the smooth case).
9

---

Published in Transactions on Machine Learning Research (11/2023)
Example with 03 m2-00
Fuclidean Divergence to Solution
Synvex /
mean trajectory
conceve
8x) 3,,," 19.33
50
10-1
40
20
10
X
10a
-10
10.1]
50
150
175
200
Iterations
Finite-sum example of Theorem with SPGD and &b 1/211-112 (left) f(x) is strongly convex and is a sum of smooth fi that are either non-convex strongly convex functions. (right) As predicted by Theorem linear convergence is observed for the mean trajectory of SPGD over 10,000 runs.
Figure 1:
where o² is such that E [IV/e(=>)] S 2 Unlike our results, their neighborhood can be controlled
with a smaller stepsize if interpolation does not hold. Thirdly, our results hold for s 1/2 while they require n S 1/2r. Finally, when strongly convex relative to sb they require fs to be convex while we allow fe be non-convex.
5.3.1 An example of Theorem
To demonstrate the differences with previous works we consider a finite-sum example with SPGD and & = 1/2 where each fi
R + ax²² + bąæ + o is quadratic, and the constraint the closed interval X' [0, 1). As demonstrated in Figure 1 f is the average of both non-convex and strongly convex quadratics, and f is strongly convex relative to V. Additionally, each fi is max, 2/ay/osmooth relative to th More importantly, as depicted in Figure holds with f(0) = (X) for all i.
we consider the case where ox 0, interpolation relative to X
In comparison to Hanzoly & Richtarik 2021 , their results apply with a neighborhood of convergence equal to R 168. We note that their neighborhood depends on the choice of stepsize and we report the smallest neighborhood guaranteed by their results by using their perscribed stepsize.
In comparison to Dragomir et al. (2021), their results do not apply for several reasons: SPGD is not included in their analysis (only SGD in the Euclidean case is allowed). f: is not always convex, and Vf(x.) * 0. Nevertheless, their variance term in the Euclidean case corresponds to E [==))) the expected squared norm the optimum, which has a value of 520 in this constrained finite-sum example.
6 Convergence of mirror SPS
In this section we present our convergence results for SMD with mSPS when fr are L,-smooth and with varying assumptions. First, we consider the case when is strongly convex relative v a common assumption when analysing mirror descent. under strong convexity Hazan & Kale (014). Then we present
Note that Dragomir al. 2021 assume be twice differentiable and strictly convex and the conjugate function of ih. ze is some point within the line segment, between Vi((z)) fi(r)(((..) and V.l(z))
10

---

Published in Transactions on Machine Learning Research (11/2023)
rates under convexity and smoothness but without relatively strong convexity. Afterwards, discuss the results under interpolation and provide examples.
6.1 Smooth and strongly convex
With strong convexity of and f being relatively strongly convex with respect to db show linear rate of convergence to neighborhood.
Theorem 5. Assume f& is convez and L-smooth almost surely with respect to the norm ||-1- Furthermore, assume that f is ju-strongly convez relative to & over X, where vb is pe-strongly conver over X with respect to the norm ||-I] and assumption holds. Then SMD with mSPSmar and c 2 2 guarantees
E (2 S (1 pa) (2( + T60²
au
Where a min((m/fff (no/2at, 96
Since v is strongly convex we get a guarantec on expected distance to the minimum, as Me || - x 1| < (2, 1t+1). Also, each Ji a strongly convex function or it satisfies the Polyak-Lojasiewicz (PL) condition (Assumption 2) then mSPS is upper bounded by equation [10 and equivalent mSPS with
1h = Pe/2cp. Therefore, SMD with mSPS converges by Theorem
A similar result was shown for SGD with SPS Loizou el al. 2202
Theorem 3.1]. Indeed, Theorem 5
gencralizes their results; by taking (xxx) 1 ||=1| recover result which is true for both SGD and SPGD.
Corollary 6. Assume f& is convex and L-smooth with respect to the norm I1-1lp almost surely and that f is u-strongly conver with respect to 11-112 over X. Then SPGD (SGD if X R2)) with SPSmon guaranlees
E
2 111.-- 11 < <1 - (1-p))''
3 ||,.. 21112 ap
mo?
For the case of preconditioned SGD, (x)) 1 and X = RRd, we can go further and extend non-convex
result similar to Theorem 3.6 in Loizou et al. (0021) We include the result and proof in section G.3
In Loizon et al. (2021) constant stepsize results are derived as a special case SPSmax. similarly if in mSPSmax 17b is selected such that т) S #s/2et.uua then T)t a constant and we can derive new constant stepsize results for SMD. However, using Theorem 5 and mSPS to analyze constant stepsize SMD yields weaker results than Theorem [ The assumptions made in Theorem 5 are stronger. For example, Theorem 5 requires & be both strongly convex and smooth on X' with respect if & is Legendre over X' and X' is bounded. This limitation, however, does not apply for Theorem and the next result for smooth convex losses since we do not enforce a smoothness condition on vb.
norm which would not be possible
6.2 Smooth and convex
Without f being relatively strongly convex we can attain convergence results on the average function value.
Theorem 7. If Je is conver and L-smooth with respect to norm |1-Il almost surely, assumplion holds, and vb is pe-stan utr-stongly convex over X with respect to ||-I1. Then mirror descent with mSPSmes and 2 1 guarantees
E [[(x)) [(x)) 2B (x.izi)
2mpa
at
Where a min(us/2eee }.
Similarly to Theorem we can derive constant stepsize results, except we require 1/ I 4/2t.mm. (with c= 1), see Section G.2.1 for details. Unlike Thcorem however, this result does not require & to be smooth over X.
Comparison with SPS. Unlike the analysis of SPS our results and stepsize depend on the choice of the mirror map sb. This dependence, observed historically, is important motivation for mirror descent.
11

---

Published in Transactions on Machine Learning Research (11/2023)
allowing for tighter bounds and better dependence the dimension d. For example, suppose X = Aa and fo is I. smooth with respect to Il-111 and for simplicity
(V/,.... :/4a,, 1, and Th is selected large enough such that a = ps/20lmax. Then the bound in Theorem (7) for EG gives E [f(ā)) f(=))] S 42 log + Mcanwhile, under SPGD the bound is sdL/e- + 4dLmo since f& is smooth with respect to 11-112 if L dL. Note that unlike SPGD the neighborhood of convergence for EG is independent of Moreover, under interpolation EG converges at rate that scales logarithmically in d, which is otherwise not possible with SGD. Therefore, selecting the appropriate and stepsize allows for better dependence on d with a smaller neighborhood of convergence.
6.3 Exact convergence with adaptive stepsizes and interpolation
As consequence of the previous results, we have several convergence guarantees under interpolation (o² 0). In fact, when x² = 0 the upper bound t is not needed, the unbounded variant mSPS will enjoy the same convergence rates as mSPS Additionally, similar to Section 5 we can attain almost sure convergence results analogous to Corollary 2 and Corollary 4 To the best of our knowledge, all existing results are with constant stepsize (Section 5 Dragomir et al. 2021 Azizan & Hassibi, 2019) or with conditions on the initialization of parameters Azizan et al. (2019). In contrast, with mSPS we have provided exact global
convergence guarantees with an adaptive stepsize.
6.4 Mirror descent examples
To demonstrate the generality of our results we consider two cases of Theorem We examine the so called p- norm algorithms, and preconditioned SGD. Similar results can also be derived with the exponential gradient algorithm and the norm I--II
Corollary 8 (p-norm). Suppose the assumptions of Theorem 7 hold with ||-I1 = 11-11p for 1 < <<p <ps S 2 and
==11. guarantees E [f. fxx))] (x.().))) 2mho²
Let q be such that 1 p ((x) = |all:
-
Then SMD with stepsizes ne min (p (0-1)(f5((21)) (2))) 76
V. (m1))];
at
Another interesting case is SGD with preconditioning T++1 = (i(a), for some positive definite matrix M. In other words, vo is taken to be v(x) = 1 || with (x ||x vIl and X= = Corollary 9 (Preconditioned SGD). Suppose X = Rd and the assumptions of Theorem ? hold with IHII I1-Ilar: for positive definite matriz M. Then SMD with v(x) 1/ ||=|| and stepsizes n
min { (1)) (10,,, .m0.. guarantees [ff())) - f(z.)) N
l|x. -ıll- 2mp"
at
7 Experiments
We test the performance of mSPS on different supervised learning domains and with different instances of SMD. We use mSPS in our convex experiments with e= 1. In theory the bounded stepsize mSPS is required in absence of interpolation, however, in practice we observe mSPS converges, likely due to the problems being close to interpolation. For our non-convex deep learning experiments we follow Loizou et al.) (2021h by selecting c = 0.2 and smoothing procedure to set a moving upper bound for mSPS max To com- pare against a constant stepsize we sweep over (10-5, 10-1, 10-2 10-1,1111 1, 10 102, 103 10 10 Code for our experiments and implerenntaton available at: https://githi:: com/
We consider series of experiments. First, we consider unconstrained convex problems with mSPS and different p-norm algorithms, (xxx) ||-=| Second, we evaluate the performance of mSPS with SPGD and positive constraints. Third, solve convex problem with a &1 constraint using mSPS and the exponentiated gradient algorithm (EG). Finally, Section 7.4 demonstrates that our method shows competitive performance over highly tuned stepsizes for deep learning without any tuning of the eyper-parameters.
mSPSmax with an upper bound at time given oig = - where b and are the batchsize and number examples respectively, which amounts p/n our experiments, with of 7--1-
"This technique is moving upperbound. More preciscly
12

---

Published in Transactions on Machine Learning Research (11/2023)
iionn p=122
iinnn p=1.4
iicnn p=1.6
iicnn p=1.8
10a
10
10'
Tain llng)
10'
10-4
109
10"
10
500.0
20-3
10-4
1.00
250
200
100
150
200
100 Epech
150
200
50
100
150
200
Esoch
Esoch
Epech
Jcnn NN
10"
rcv1 NN
10a
synthetic (0.01) NN
10'
synthetic (0.05) NN
2.041
Tran loxe (log]
20-2-
Mymu
20-4
10-2
10-4
10-3
10
50
1000
150
200
10
50
100
10-
Epach
Epoch
Epoch
Epoch
(jcnn
rcv1 h
synthedic (0.01)
synthetic (0.05) A
102.
20'
309
Train (mgg)
10-
10a
207
10a
10a
2.0
10+
102
300
10a
10
10-1
50
100
150
200
50
100
150
260
50
100 Epoch
150
200
50
100
150
200
Epoch
Epoch
Epoch
Figure 2: Comparison between mSPS with and constant stepsizes on convex binary-clasiffcation problem with no constraints (rowl), with non-negative (NN) constraints (row2), and with & constraints (row3).
cifar10
cifar10 p-1.4
cifar10 p-1.6
cifar10 p-1.8
Step Siee (log)
10a
Train loss (log)
10
10
0.1
10
10
10
10-1
15.1
10003
10
10
10
10
10
50
100 Epoch
150
200
100
200
100
200
100 Epoch
200
Epoch
Epoch
Figure 3: Comparison between mSPS and constant stepsizes on non-conver multiclass classification with deep networks. The leftmost plot shows the stepsize evolution of mSPS with smoothing and c = 0.2 for different p values.
7.1 Mirror descent across p-norms.
We consider a convex Smaary-classfficatin problems using radial basis function (RBF) kernels. We experi- ment the ijenn dataset obtained from LIBSVM (Chang & Lin 2011) which does not satisfy interpolation 10 ijenn has 22 dimensions, 39,992 training examples, and 9998 test examples. We selected the kernel band- compare across p E (1.2, 1.4, 1.8)
width 0.05 following Vaswani et al. (2019b). For these experiments between mSPS and the standard constant stepsize. The first row of Figure 2 shows the training loss for the different optimizers with a softmax loss. We make the following obscrvations: (i) mSPS performs reason- ably well across different values p and outperforms most stepsizes of SMD. (ii) mSPS performs well on ijenn even though it not separable in the kernel space (i.e. there no interpolation). This demonstrates some robustness to violations of the interpolation condition and to different values of the p. Note that each optimizer was ran with five different random seeds to demonstrate their robustness.
10 the appendix include results the mushroom dataset where interpolation satisfied.
13

---

Published in Transactions on Machine Learning Research (11/2023)
7.2 Projected gradient descent
In this setup consider optimizing the logistic loss with non-negative constraint the parameters. We run our optimizers on two real-datasets ijenn and rcv1. rev1 has 47,236 dimensions, 16194 training examples and 4048 test examples. Following Vaswani et al. (2019b) we selected the RBF kernel on revl with bandwidth 0.25.
We also ran the optimizers on two synthetic datasets for binary classification that are linearly separable datasets with margins 0.01 and 0.05 respectively. Linear separability ensures the interpolation condition will hold. For each margin, we generale dataset with 10k examples with d 20 features and binary targets.
We observe in the second row of Figure 2 that mSPS outperforms the best tuned constant stepsize in most cases, and in the rest of the cases is competitive. The result underlines the importance of adaptive stepsizes.
7.3 Exponentiated gradient
7.2 with logitistic regression where parameters constrained to the & ball, X' fx ||ا||| I X}- To solve this problem with EG, employ the common trick of reducing & ball constraint to simplex constraint with dimension (2d 1) 1) (Schuurmans & Zinkevich 2016
To test the effectiveness of mSPS with EG we consider the datasets in Section
For these experiments we test our optimizers on revl and ijenn and the two syuthetic datasets mentioned in Section 7.2 and report their results in row 3 of Figure 2 Like in the previous experiments, mSPS is significantly faster than most constant stepsizes even though e is kept at and in some cases outperforms the best tuned SMD. Note that the constant stepsizes that don't appear in the plots have diverged.
7.4 p-norm for optimizing deep networks
with deep networks, we considered the p-norm algorithms for the CIFAR10 dataset. CIFARIO has 10 classes and we used the standard training set consisting of 50k examples and a test set of 10k. As the kernel experiments, we evaluated the optimizers using the softmax loss for different values of p. We used the experimental sctup proposed in Loizou et al. (2021) and used batch-size of 128 for all methods and datasets. We used the standard image-clasiiliattion architecture ResNet-34 (He et al, 2016). As in the other experiments, each optimizer was run with five different random seeds in the final experiment. The optimizers were run until the performance of most methods saturated; 200 epochs for the models on the CIFAR10 dataset.
For
From Figure 3 we observe that: (i) mSPS with e = 0.2 and smoothing constantly converges to a good solution much faster when compared to most constant stepsizes. (ii) The gap between the performance of mSPS and constant stepsize increases as p decreases suggesting that, like in the convex setting, our method is robust to different. values of p.
8 Conclusions and future work
Stochastic mirror descent (SMD) is a powerful generalization of stochasiiic projected gradient descent to solve problems without a Euclidean structure. We provide new convergence analysis for SMD with constant step- size in relatively smooth optimization and with the new adaptive stepsizes mSPS, mSPS in the smooth case. Consequently, we achieve the first interpolation results for the EG algorithm under interpolation.
A main novelty of our results is the use of the finite optimal objective difference assumption (Loizou et al. 2021] with mirror descent, allowing for convergence without bounded gradient or variance assumptions and achieving exact convergence under interpolation. In relative smooth optimization we refine the finite optimal objective difference assumption to better capture interpolation with constraints and achieve convergence in cases not guaranteed by existing works.
In smooth optimization we experimentally validate mSPS in several supervised learning domains and across various instances of mirror descent. mSPS requires tuning but is nonetheless competitive better than
14

---

Published in Transactions on Machine Learning Research (11/2023)
extensively hand-tuned step sizes. This adaptivity is important for tackling different problem domains with
different versions of mirror descent.
Beyond the scope of this paper there are several interesting directions for future work. For example, we critically rely on the relative smoothness or smoothness, however, it would be interesting to attain rates of convergence with the finite optimal objective difference assumption without smoothness. Additionally, our convergence result of mSPSmma in Theorem 5
requires & to be smooth over X, an assumption not required for our constant stepsize results in Section 5 it would be interesting to unify the results by developing variant of mSPSSmax for the more general relatively smooth problem.
References
Peter Auer, Nicolò Cesa-Bianchi, and Claudio Gentile. Adaptive and self-confident on-line learning algo- rithms. Journal of Computer and System Sciences, 64(1):48 75, 2002. ISSN 0022-0000.
Navid Azizan and Babak Hassibi. Stochastic gradient descent: Minimax optimality and implicit regularization. In International Conference on Learning Representations, 2019.
Navid Azizan, Sahin Lale, and Babak Hassibi. Stochastic mirror descent on overparametterized nonlinear models: Convergence, implicit regularization, and gencralization. arXiv preprint orXiv:1906.03890 2019.
Heinz H Bauschke, Jonathan M Borwein, et al. Legendre functions and the method of random bregman projections. Journal of convez analysis, 4(1):27-67, 1997.
Heinz H Bauschke, Jonathan M Borwein, and Patrick L Combettes. Bregman monotone optimization algorithms. STAM Journal control and oplimization, 42(2):596 636, 2003.
Heinz H Bauschke, Jérôme Bolte, and Mare Teboulle. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42(2):330-33) 2017.
Anastasia Bayandina. Adaptive stochastic mirror descent for constrained optimization. In 2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V.F. Demyanov) (CNSA), pp. 144, 2017.
Anastasia Bayandina, Pavel Dvurechensky, Alexander Gasnikov, Fedor Stonyakin, and Alexander Titov. Mirror Descent and Conver Optimization Problems with Non-smooth Inequality Constraints, pp. 181-213.
Springer International Publishing, Cham, 2018. ISBN 978-3-319-97478-1.
Amir Beck. Pirst-Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadel- phia, PA, 2017.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167 175, 2003. ISSN 0167-6377.
Aharon Ben-Tal, Tamar Margalit, and Arkadi Nemirovski. The ordered subsets mirror descent optimization method with applications to tomography. SIAM Journal on Optimization, 12(1):79-108, 2001.
Leonard Berrada, Andrew Zisserman, and M Pawan Kumar. Training neural networks for and by interpo- lation. In International Conference on Machine Learning, pp. 799-809. PMLR, 2020.
Mario Bertero, Patrizia Boccacci, Gabriele Desiderå, and Giuseppe Vicidomini. Image deblurring with poisson data: from cells to galaxies. Inverse Problems, 25(12): 2009.
Dimitri P Bertsekas and John N Tsitsiklis. Parallel and distributed computation: numerical methods. 2003.
Benjamin Birnbaum, Nikhil R Devanur, and Lin Xiao. Distributed algorithms via gradient descent for fisher markets. In Proceedings of the 12th ACM conference on Electronic commerce, pp. 127-136, 2011.
Avrim Blum and Yishay Mansour. From external internal regret. Journal of Machine Learning Research, 8(6), 2007.
15

---

Published in Transactions on Machine Learning Research (11/2023)
Stephen Boyd, Lin Xiao, and Almir Mutapcie. Subgradient methods. lecture notes of EE392o, Stanford Universily, Aulumn Quarter, 2004:2004-22 2005,, 2003.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends& in Machine Learning, 8(3-4):231 357, 2015.
Nicolo Biancii and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Nicolo Cesa- Desa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions Information Theory, 50(9):2050-200) -057, 2004.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transac- tions on Intelligent Systems and Technology, 2011. Software available at http::/www.cc. csie. ntu. edu. tw/
-ajlin/libsvm
Gong Chen and Marc Teboulle. Convergence analysis of proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3):538 543, 1993.
Michael Collins, Amir Globerson, Terry Koo, Xavier Carreras Pérez, and Peter Bartlett. Exponentiated gradient algorithms for conditional random fields and max-margin markov networks. Journal of Machine Learning Research, 9:1775 1822, 2008.
Damek Davis, Dmitriy Drusvyatskiy, Kellie MacPhee, and Courtney Paquette. Subgradient methods for sharp weakly convex functions. Journal of Oplimization Theory and Applications, 179(3):962 982, 2018.
Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13:165-202, 2012.
Radu Alexandru Dragomir, Mathieu Even, and Hadrien Hendrikx. Fast stochastic bregman gradient meth- ods: Sharp analysís and variance reduction. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 2815 2825. PMLR, 18 24 Jul 2021.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121 21591, 2011.
John C Duchi. Introductory lectures on stochastic optimization. The mathematics of data, 25:99, 2018
John C Duchi, Shai Shalev-Shward Yoram Singer, and Ambuj Tewari. Composite objective mirror descent. In 23rd Conference on Learning Theory, COLT 2010, pp. 14-26, 2010.
Barbara Franci and Sergio Grammatico. Convergence of sequences: A survey. Annual Reviews in Control, 2022.
Tianxiang Gao, Songtao Lu, Jia Liu, and Chris Chu. Randomized bregman coordinate descent methods for non-lipschitz optimization. arXiv preprint arXiv:2001.05202 2020.
Claudio Gentile. The robustness of the p-norm algorithms. Machine Learning, 53(3):265 299, 2003.
Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochas- tic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22(4): 1469-1499 2012.
Robert Gower, Othmane Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. In International Conference Artificial Intelligence and Statistics, pp. 1315-1323. PMLR, 2021.
Robert Mansel Gower, Nicolas Loizon, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International Conference on Machine Learning, pp. 5200- 5209. PMLR, 2019.
16

---

Published in Transactions on Machine Learning Research (11/2023)
Amy Greenwald, Zheng Li, and Casey Marks. Bounds for regret-matching algorithms. In AI6M, 2006.
Adamn J Grove, Nick Littlestone, and Dale Schuurmans. General convergence results for linear discriminant updates. Machine Learning, 43(3):173-21) 2001.
Filip Hanzely and Peter Richtarik. Fastest rates for stochastic mirror descent methods. Computational Optimization and Applications, 79(3):717-766, 2021.
Elad Hazan and Sham Kakade. Revisiting the polyak step size. arXiv preprint 4rXiv 2019.
Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. The Journal of Machine Learning Research, 15(1))2489-225) 2512, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
Hadrien Hendrikx, Francis Bach, and Laurent Massoulié. Dual-free stochastic decentralized optimization with variance reduction. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 19455- 19466. Curran Associates, Inc., 2020.
Jean- Cran-Baptiste Hiriart- Urruty and Claude Lemaréchal. Fundamentals of convex analysis. Springer Science & Business Media, 2004.
Samid Hoda, Andrew Gilpin, Javier Pena, and Tuomas Sandholm. Smoothing techniques for computing nash equilibria of sequential games. Mathematics of Operations Research, 35(2):494 512, 2010.
Anatoli Juditsky and Yuri Nesterov. Primal-dual subgradient methods for minimizing uniformly convex functions. Technical Report, 2010.
Jyrki Kivinen and Manfred K. Warmuth. Exponentiated gradient versus gradient descent for linear predic- tors. Information and Computation, 132(1):1 63, 1997. ISSN 0890-5401.
Christian Krocr, Kevin Waugh, Fatma Kirma-Karzan, and Tuomas Sandholm. Faster algorithms for extensive-form game solving via improved smoothing functions. Mathematical Programming. 179(1):385- 417, 2020.
Yunwen Lei and Ke Tang. Stochastic composite mirror descent: Optimal bounds with high probabilities. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive step- sizes. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the Twenty-Sezon Second Interna- tional Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 983 992. PMLR, 16-18 18 Apr 2019.
Nick Littlestone. From on-line to batch learning. In Proceedings of the second annual workshop on Compu- tational learning theory, pp. 269 284, 1989.
Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-2) 1994.
Nicolas Loizou and Peter Richtárik. Convergence analysis of inexact randomized iterative methods. SIAM Journal on Scientific Computing, A3(67 A4016, 2020a.
Nicolas Loizou and Peter Richtárik. Momentum and stochastic momentum for stochastic gradient, newton, proximal point and subspace descent methods. Computational Optimization and Applications, 77(3):653- 710, 2020b.
17

---

Published in Transactions on Machine Learning Research (11/2023)
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien. Stochastic polyak step- size for sgd: An adaptive learning rate for fast convergence. In International Conference on Artificial Intelligence and Statistics, pp. 1306 1314. PMLR, 2021.
Stanislaw Lojasiewicz. Une propriété topologique des sous-ensembles analytiques réels, 1963.
Haihao Lu, Robert M Freund, and Yurii Nesterov. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal Optimization, 28(1):333-335 3543,,33,, 2018.
Siyuan Ma, Racf Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3325-3334 PMLR, 2018.
H. Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. COLT, 2010.
Arkadi Nemirovski and David Borisovich Yudin. Problem Complexity and Melhod Efficiency in Oplimization. A Wiley-Interscience publication. Wiley, 1983. ISBN 9780471103455.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approxima- tion approach to stochastic programming. SIAM Journal on oplimization, 19(4):1574 1609, 2009.
Yurii Nesterov. Lectures on conver oplimization,, volume 137. Springer, 2018.
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXi::1912.19213 2019.
Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716:50-69,
2018. ISSN 0304-3975. Special Issue on ALT 2015.
Boris Polyak.
Introduction to optimization. New York : Optimization Software, Publications Division, 1987.
Boris T Polyak. Gradient methods for solving equations and inequalities. USSR Computational Mathematics and Mathematical Physics, 4(6):17-33 32, 1964.
Mariana Prazeres and Adam M Oberman. Stochastic gradient descent with polyak's learning rate. Journal of Scientific Compuling, 89(1):1 16, 2021.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400 407, 1951
Michal Rolinek and Georg Martius. L4: Practical loss based stepsize adaptation for deep learning. Advances in Neural Information Processing Systems, 2018.
Dale Schuurmans and Martin A Zinkevich. Deep learning games. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
Samuel Sokota, Ryan D'Orazio, J Zico Kolter, Nicolas Loizou, Marc Lanctot, loannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning. quantal response equilibria, and bwo-player zero-sum games. In The Eleventh International Conference on Learning Represenlations, 2023. URL httpss://pperreviee wttpeeeiwwwweeeeeeeeeee wwt.:eee//toooo wwwp://www..eetotuneeeeeeeeeee stee//oorumm.ccppeSUU00022
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with smooth loss. arXiv preprint arXii:1009.3899 2010.
Fedor Sergeevich Stonyakin, M Alkousa, Alcksci Nikolaevich Stepanov, and Alcksandr Aleksandrovich Titov. Adaptive mirror descent algorithms for convex and strongly convex optimization problems with functional constraints. Journal of Applied and Industrial Mathematics, 13(3):557-55) 574, 2019.
18

---

Published in Transactions on Machine Learning Research (11/2023)
Matthew Streeter and H Brendan McMahan. Less regret via online conditioning. arXiv preprint arXiv:1022.4400 2010.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for pver-parameterized models and an accelerated perceptron. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the Twenty-Secone International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 1195-1204. PMLR, 16-18 Apr 2019a. URL https://
proceedings mlr. wwtpsss/vv/vvawaaana 19a.. html
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien, Interpolation, line-search, and convergence rates. In Advances in Neural Information Processing Systems, pp. 3727-3740, 2019b.
Painless stochastic gradient:
Sharan Vaswani, Olivier Bachem, Simone Totaro, Robert Müller, Shivam Garg, Matthicu Gcist, Marlos C. Machado, Pablo Samuel Castro, and Nicolas Le Roux. A general class of surrogale functions for stable and efficient reinforcement learning. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 8619 8649. PMLR, 28 30 Mar 2022. URL https: //proceedings. mlr http://........p..s.r.eeeme wtt..pee//11////aaaaaait
html
Tesi Xiao, Krishnakumar Balasubramanian, and Saced Ghadimi. Improved complexities for stochas- tic conditional gradient mot under interpolation-like condit ions. Operations Research Lelters, 50
(2):184 189, 2022. ISSN 0167-6377. doi: https: /ttp:::///oooorg////// http:///.....100....20.000000000
URL https:
//www.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commun. ACM, 64(3):107 115, 2021.
A Appendix
The appendices include omitted proofs, other results, and additional experiments. The material is organized as follows: equivalent definitions of relative smoothness are given in Section B standard mirror descent results are presented in Section C non-smooth analysis of mirror descent with the mirror Polyak stepsize is given in Section D the lower bound proof of mSPS is included in Section E. the proofs for the results
Section 5 are presented in Section F including Theorem [ and Theorem proofs for Section G are given in Section G including non-convex result. for preconditioned SGD in Section G.3 experiment details are
given in Section
H
B Relative Smoothness
Relative smoothness is a generalization of smoothness in first order optimization that includes non-Lipschitz gradients. A function is L-smooth with respect to a norm ||-11 if
[[v Vf(i)l.. s ||
With Lipschitz gradient the error in the first order approximation of f grows at most quadratically
- (VS(), v)) = By(r;)) < || vll².
Relative smoothness replaces the quadratic upper bound with divergence relative convex function v. By(x;)) S LB,(
If db is strongly convex then smoothness with respect to a norm implies relative smoothness with respect to tb. However, a relative smooth function may not admit a Lipchitz gradient, as was first remarked by Birnbaum et al. (2011) and later rediscovered by Lu et al. (2018) and Bauschke al. (2017). Similar traditional smoothness, equivalent definitions of relative smoothness exist in the literature. For example, Lu et al. (2018) prove that the following conditions equivalent:
19

---

Published in Transactions on Machine Learning Research (11/2023)
1. is L smooth relative to
2. Li f is convex
3. under twice differentiability V = LV
4. (Vf(x) Vf(v), v\ S (z) Vv(y), -))
Similar conditions can also stated for relative strong convexity.
Defining curvature and smoothness relative a function & allows for a wider application of first order methods via mirror descent. Recently, such assumptions have been used to establish both new results and algorithms in machine learning. In reinforcement learning, Vaswani et al. (022) relative smoothness and mirror descent to provide
perspective policy optimization in reinforcement learning, In algorithmic game theory, Sokota et al. (2023) use relative strong convexity to establish fast convergence to quantal- response equilibria in extensive-form games.
C Mirror descent lemmas
Lemma (Three Point Property (Chen & Teboulle 1993)). ) Let By be the Bregman divergence with respect t D R. Then for any three points 2,y E int and E D, the following holds
Ba(z;z) + (x Bo(x:)) (Vv(y) Vv((x), =x).
C.1 Proof of Lemma
Lemma 1. Let By be the Bregman divergence with respect to conver function v/ D - R. and assume assumption holds, Let Te+1 arg min (gt, x) (x; Then for any X
B (2( S (I Ti (9 It x.) - B (x(1++1) + mo (gt, 21 r(+1).
(14)
Furthermore if tb is py strongly conver over X then
m/²
Bo(sajZet1) S (p(x:: mngg, v.)
|| 19
(15)
2/r
Proof. The proof follows closcly to the one presented in Orabona 2019 Lemma 6.7]. First obscrve that
2+41 statisfies the first order optimality condition
(n.g. + Veb(++1) - Ve(I)) 2(41) 2 0,
since V (2 = VV(x))
We start by examining the inner product (nigt, xt x.) and adding subtracting quantitics to make the first order optimality condition appear.
- (1h9,, Te - x.) (n:g + (+((++)) - VV(1z), - x.) (Ve((T+++) Velar), xe+1) + (Thge, 24 - Ie+1)
(Vb(z441) Vv(a,),, x++1) (n.g Ht - x(+1) (first order optimality) Bo(x.:04) (x(x.:0141) - (2( (n.t, 24 xt+1) (three point property).
Rearranging gives the first result. Note this point only require v to be convex and i be differentiable at Ie and 21+1, which is guaranteed by assumption [
To obtain the second result, observe
(1 Ze xx) & Bx(x.)))) B (x.:2444)) ( 25) + (mii 2, re+1) (from above)
14 || =rll + (nigr, Te 2+41) (strong convexity) < Bo(x,),,) By (2::244))
m
< (x (o. +
||g:l12 (Fenchel- Jrinche--Young inequality).
24
Rearranging gives the second result..
20

---

Published in Transactions on Machine Learning Research (11/2023)
D Non-smooth analysis of mirror SPS for Lipschitz functions
As we have already mentioned in the main paper, the Polyak step-size is used extensively in the literature of projected subgradient descent for solving non-smooth optimization problems. However to the best of our knowledge there is no efficient generalization of this step-size for the more general mirror descent update.
Theorem 10 (Non-smooth deterministic). Assume f is conver with bounded subgradients, [10f(z))l, S G. Let s be p&g strongly convex with respect to the norm II-1|; and assume that Assumption holds. Then mirror descent with stepsize Tp. (o(f(x))-f(x.)) satisfies,
[[a((=))11
(x Pe
2
f f(x.) S GV
where He -x=1 Lz.. The same result holds for the best iterate f(x)) min,(f(e)))seee. Moreover, have lim [(xe) f(x.).
Proof. Let Ir be subgradient of I at x, used to compute ne.
Then by Lemma 1 we have
(1411 & (x(xx;2)) n(g0 xz - xz) + |19c11
2p
< (o(x)))s) - (f((x))) f(x+)) +
llgell? (by convexity)
2p0
Pi (f(z)) (xxa))
u& (f(ar) f(x.))
(by definition of mt)
1
2 2|19:l1
Mg (f(xx)) {(xa))²
2 2|
Rearranging and summing across time we have
Me (f(rr)) - [(xa))² Bo(x.:11) (2.3544411) & Bx(x.;2)).
(16)
2 2119a11.
Applying the upper bound ||9.|1. < G' and taking the square root gives,
2B (x+;
Σ ((((.)) ((x))) s G
The result then follows by the convexity of f and concavily of the square root function,
< { 1=1
Σ
- (((x)))((x)))
+ Σ (f(x.) - f(x)))²
(xx)
< G
To obtain the best iterate result notice that f(x)) - f(x.)) (f=r))) f(x)))
To allain the limiting result observe that 16 implies
Σ po (f(xz) - f(x))) G2 Be < t00.
Giving the result lime-soo f(x)) (xxa).
21

---

Published in Transactions on Machine Learning Research (11/2023)
D.1 Last-iterate convergence to solution
Under the same assumptions Theorem we have that mirror descent converges to point. First we provide a useful lemma applicable to mirror descent with strongly convex mirror map vh.
Lemma 4. Suppose de strongly conver, then if the sequece faet121 is Bregman monotone with respect to set S, that is for any E S we have
By(x;1411) S Bo(z;z)).
then It 7x E if and only if all the sequential cluster points of {2t)12 are contained in
Proof. If the sequence is ( is Bregman monotone then by strong convexity
Pe || 1---a r++1l1 s (x;
hence the sequence is bounded. Therefore, the sequence has a limit point æι such that there exists subse- quence Tb. - Ir. Assume æ E and consider the sequence {yr- = Bg (2); (1))11 Since ze is monotonically decreasing and bounded below Yt - L for some L R. However, the subesequence (Zn converges to zero, therefore have that lim, Bx( 0, implying that lim It 3i by strong convexity of d.
Corollary 11. Under the same assumptions as Theorem 10 mirror descent converges to a solution,
lim Txs
for some a. X..
Proof. From Theorem 10 we have the following inequality,
Bolx:gz41) Bx(xx, ps (f(x)) f((x)
f(x)))
2 211
Therefore by Lemma it remains to show that all limit points of 24 are contained within X..
By Theorem 10 we have that f(xx)) - f(x.). For any limit point æs we have a subsequence Tb, such that Tb. + Ii and by contimuity of f, æ must be solution,
f(x.) lim f(x)) lim f(xo,) f(lim lim 2b,)) f(x)).
t-000
The result then follows by Lemma 4
E Proof of mSPS lower bound in section 4
The lower bound of mSPS 10 when fe is L. smooth, restated below, is vital to our analysis,
ue (x(( - f2)
Pv 2cL
< m7
cl[Vf(zx))1
Notice the above inequality is equivalent to
1 (fe( - f2)
2L
|V
The first inequality is attained by multiplying both sides by mo/c. We provide detailed proof below.
22

---

Published in Transactions on Machine Learning Research (11/2023)
Lemma 5. If f R= - R is L-smooth with respect to norm |I-I1 then
|V
I f(z)
inf fly). yER
2L
Rearranging and defining f inf yeRr fly) gives
f(z) - f [V
2L
Proof. Since f is T-smooth we have
x) + T. 2 1|x 811 Vx,y E ER"
f(0) S +())+ (Vf(r),
Therefore we have the following upper bound inf, f
inf f(y) s min { [(x)+ (V.())) + || - y11
min
,² ||=11
+20.||=||s1
2
L
< min
r20.||=||s1
(r(Vf(()) 2)} + T, |1
f(x)
min
min
2
f(x)
min
((V[(x), -2)] + 2 n, ||
max
L
f(x) min
by the definition of ||-11.
2
(r=1\V(()) L/L) f(x)
[V[()]]
|V
2L
Simplifying and rearranging gives the result.
F Proofs for section 5
In this section we provide proofs of our main results in the relative smooth setting, For convenience we denote the expectation conditional upon (E1,E,,... ,.) as E, [t]. All statements hold almost surely.
F.1 Proof of Lemma
Lemma 2. Suppose f is smooth relative to vb. Then if 1 we have
- -B + n f(z)) - < ((f(xz)) f(
2+41)
Proof. Since f smooth relative to it is also Y smooth relative to & (because L S 1 and & is convex). Therefore,
1
(y < Bp( 1)
-Bo(2411 + nB (x 5 0.
23

---

Published in Transactions on Machine Learning Research (11/2023)
Now we examine the inner product 17( (V))) 21 -
(Vf(2=), I(t1) = 17 (f(+++) - f(()) (Vf(zz), 2411 -x)) + f(zs) - f(((+1))
= 17 B (T(+1: + f(x)) - -f f(x2+1))
Therefore, we have the following
-Bo(2141;)))) + (VV(((V -x41) (1 + +nBg(re41;))) + ([((x)) f(x+t1)
S {n(((r)) [(x+11).
F.2 Proof of Theorem
Theorem 1. Assume v satisfies assumption | Furthermore assume f to be p-strongly conver relative to ab over X, and fe to be L-smooth relative to vp over X' almost surely. Then SMD with stepsize S 1 guarantees
E [B s (1 (1) B (xx: + ox
Proof. From Lemma
(before applying strong convexity but assuming convexity of th) we have
B3(2,;0(41) < Bo(x.; - 7 fV, (z+) 22 z.) (x( + (V. (2z), Z(t1)
< By(x.iz)) - 7 (V (2+), Jz- - x.) + nff,, (xt) - fe. (f(+1)) (by Lemma 2
< Be(zsizz) 7 (V,, (2i), Tz z.) n(fe, (2t) f2. (X)) (by definition of fū, (X)) -p((x fc (2+), Ft =.) + nffs (xt) - (xx)) + ((f.( f2 (X)).
By taking expectation conditioning on (f1, , we obtain,
E, (B.(z.) < (x(x.)z)) -n v>(f(=)), - x.) nff( - f(x.)) + +ff(xx)) -E, By(s.)))) (f(x.) f(x)) (VI())), -x,))) +n((())))))))) E, [52 (X))
[fā (x)]
(17)
$ Ba( (n)) -n((xx)) E. [5 (2)]) (by relative strongly convexity of f)-
Now by the tower property of expectations and applying the definition of ox
E ( < (z.: (1 pm) + no
Iterating the inequality gives,
E BB S Ba(xs:m))(1 (11)) Σ x (1 jm7)
< Ba(x, pm7) ax
Where the last inequality follows by Et=d(1 (m < 1. - pm) 1/wn-
Corollary 2. Under the some assumptions at Theorem 1 if 03 = 0 then B (2.12++1)) + almost surely.
Proof. By Theorem the following inequality holds:
E, [Bp(k.: s (x:) - pn).
(18)
The result then follows by Franci & Grammatico 2022 Lemma 4.7].
24

---

Published in Transactions on Machine Learning Research (11/2023)
F.3 Proof of Theorem
Theorem 3. Assume & solisfies assumplion 7
Purthermore assume Ie to be L-smooth relative to th over X' almost surely. Then SMD with stepsize I guarantees
By(caizte)
B Bol ox
E
S
ny
Proof. Note that in the proof of Theorem 17 Therefore we have,
1 relative strong convexity is not used to attain the inequality
Eg By (2,122441)) & (2()))z) (By( + (((())))))))))))))))))())))))))) E. [(((())]
After applying the tower property, definition of o², and rearranging, we have
1 (B) < E BB [x)) - E (Ba((a) + na
Summing across time and dividing by ryt gives the result.
Corollary 4. Under the assumptions of Theorem if f is conver and o = 0 then By + 0 almost
surely.
Proof. Under interpolation f(x.) Es [( 0. From Theorem the following inequality holds:
E, (20: & Bo(x,:))) - (x.
(19)
Since f convex (x 2 therefore, by the Robbins-Siegmun Lemma (e.g. (Franci & Grammatico 2022 [Lemma 4.1)) (x.))))))) almost surely.
Proposition 1. Let f(z) (19,2) b)² then (x; 2)
Proof. Note that vf(x)= ((g, x) b) g. Therefore,
2 (gg, 2) b)² 1 (gg v) b)2 ((9.)) b) (g, x y)
By(x,
(20)
1
1
2 (10, x²)² x))²
(g + b² ((9 y))² + v)b - 6² - ((g. v) b) (g, 3)
(21)
2
2 (1a, x)) 2. - ((.,2)) + (g. ((g - b) (g, - v)
(22)
5 x))² b) 2 (2 (g.
m) + b(g, () b(g.v)
(23)
(),,))) ((g. (g. v) (g,
(24)
It follows that B, is symmetric.
G Proofs for section 6
In this section we provide proofs of our main results in the smooth setting. For convenience we denote the expectation conditional upon "Ei,,,,".,, as E, [+]. All statements hold almost surely.
Notice that by definition of mSPSmax we have the following upper bound
nt 1 ns (f,, (It) - ft.)
V Se. (xx))1
25

---

Published in Transactions on Machine Learning Research (11/2023)
Muliplying both sides of the inequality with m m.l (2vlli/us gives the following useful inequality,
m
V (zx)
(x)) - fEi)
(25)
Mv
c
The inequality holds with equality for mSPS.
G.1 Proof of Theorem 5
Theorem 5. Assume Je is conver and L-smooth almost surely with respect to the norm II-I1- Furthermore, assume that f is p-sttronly convez relative to sb over X, where tb is pug-sronnly conver over X with respect to the norm ||-||| and assumption holds. Then SMD with mSPSmar and c 2 2 guarantees
E (xa s pux)* By (x:;;1) + 1602
au
Where a = min(2w/2el, no
Proof.
(s s (V - xx.++ +
2pp
(Fe. (2+) fE.)
(2. - 1/: f. (zz)), 22 xz) +
2c
(c21/2)
By (o( n: ( ( - x.) + no (S, (xx) -{(
= By(xx: - (V. (x+), -x)) + (ee,, (xit) - (x.( + (xx) ) -(2)
(x( 22.) 77 (x..) (x(( (Vie, (3t),, mzi) + (f,, (2.)) -Ea)
20
B& (1) min { My 2CT." mh
(xe. (x:) (V (b(e))))( -SE)
Taking an expectation over i condition on I, gives
E, [B x1+1 S (x(xa))) - min {
(2eL' 1h (f(x.) - f(x)) (Vf(x.), - -xa) + EE [(fe, (x.) - St,)]
< Ba(1aa))) (1 (1- / min
. a1)) MolLE (x.) - ff (by relative strong convexity of f)
2cL
Bo(1, (1 uai + B. [ffG f())
Now by the tower property of expectations and applying the definition of a²
E [B( E (By pa) + noo
Iterating the inequality gives,
[B < Bo(xa::1((1- pa)* Σ n00 (1 p2a)
1
< Bo( paa
aj
Where the last inequality follows by E1=d(1 ua0 < E uai)* 1/10.
26

---

Published in Transactions on Machine Learning Research (11/2023)
G.2 Proof of Theorem 7
Theorem 7. If f& is conver and L-smooth with respect to norm I1-Il almost surely, assumption | holds, and do is Heg-ttoogly comvex over X' with respect to |1-11- Then märror descent with mSPSmer and 2 1 guarantees
2B (z.(2))11)
2mo
E (f(a)) -
5
at
Where a min(20/ n63.
Proof. We begin with Lemma] 1
( & (x( - (V(V.,, It - xx) -x.) +
V (x:)
2/10
n?
s Bp(xxiz)) - no (fE. (x1) - fe.((1)) (x+)) + || fV. fc.
)1 by convexity
2/14
(1) 7/6 (wx) fe. (2.)) (T))) - -E.)
(221)
2 Be(rai0s)) - 11 (Se, (5tt) - (x.))))) + me(fs, (Jie) -fE.
2
Belxa11)) no (J5. SE. + Sz. fe,(2x))) + MeeSe (ITe) fE. 1
(o( - "tt (1-2) (Js. (Is,( - -sã) + +m1 "n((ee(a..) - -SE.)
Bo((x)))) 1)t (fc,(1)) - -Et) (me(fe((x.) -1t.
20
a
(ze, - -st.) + (,(e -
2
= (Z.)2a)
a
(fe, (x)) - ft. (x+))
a
(fe, (x+) ftt) + (x)) - ff.)
2
2
- (2.)))))
(fe, (2x) - (x.)) + (x.))((x)) - -fE)
2
Recall from
10 that we have
Pv
?b } S 11t S 1/b.
min
2cL_max
By a simple rearrangement we have
(z). - f2.) s (z(z.))) (L( + (o(f.( -(ā).
Taking an expectation on both sides, dividing by a, and applying the definition of 0² yields
E [f(x)) - [(x)] < (E (x.; mx) - E (msss)))))) + 21h 0²
Summing across time, applying convexity of S; and dividing by L gives
E [f(:)) - f(xx)) 1 Σ B(f(e.) f(x+)) 2 2B((x.)11)
2np
at
27

---

Published in Transactions on Machine Learning Research (11/2023)
G.2.1 Constant stepsize corollary
In this section we present the constant stepsize corollary for Theorem If mh S Po/22 then mSPS with a constant stepsize because of the lower bound 10), 7)t = 1),, and we have that y = a. Therefore plugging in these values into Theorem gives the following corollary.
Corollary 8. Assume Ie is conner and I smooth with respect to norm ||-Il almost surely, assumplion 1 holds, and to is pep strongly conver over X' with respect to the norm I1-I1- Then stochastic mirror descent with S uo/21 guarantees
E - (x.ii)))
+ 20²
ntt
G.3 SGD with preconditioning
In this section we extend the result of mSPS to the non-convex setting when f is smooth and satisfies the PL condition. The result generalizes Theorem 3.6 in Loizou et al. (2021) by replacing SGD with precon- ditioned SGD. Note that in this case we have (bxx)= = 2 az, Mx) is (po 1) Jstronlgy convex with respect to the norm |1-1|am and Bx(x;))
| y
Assumption 2 (Polyak (1964): Lojasiewicz 1963 Assume that f. R" - R satisfies the PL condition with respect to the norm II. if there evists P such that for all x E R
I 2 2-()
(26)
Theorem 9. Assume that f and Je are L smooth with respect to the norm I1-IMM almost surely, where M is positive definite matria. Furthermore, assume that f satisfies the PI, condition (26) with respect to the norm I1-1| then unconstrained stochastic mårror descent with (1(x)) ||=|1 and stepsizes
fe. fz.
7/ min {
1lb
ccIVVe, (x:) 11 M-1
with
Lmax and np max 1/(2 - -mpn) ) 2ctimax 4u
2n+
guarantees
Lod
E Bff(z(+1) - f(x.)( (((()))) +
2(1 - v)c'
where a = min{ 2cTrwas mo} and v = m - 241 + Lmax) E (0.
Proof.
We have that the algorithm performs updates of the form
E++1 = Tt - T/. M Se. (xx).
We first apply the smoothness upper bound on f,
f(r++1) f(x))
12) +
|4411 21
Lib || V...
f(ax) - M fz.
(xx) 'V
Luf
f((x) - 7 S. (x1)
+
(x)))
Lm
-(x)) - (z.
2
f(1+11) f(x))
Lm
S +
||V fe, (11))
1/1
2
L (fe. (z:) -f²)
( +
2c
L
Se, (2r)) + L
- + (Je
(xx)
-
(Je, -(
2c
2c
28

---

Published in Transactions on Machine Learning Research (11/2023)
We proceed by taking expectation over condition on knowing zz-
f(x++1) f(x))
(Vf(z)), M M + L (f(zs) f(xx))())))))))))))))))) -
L
E2
Eu
(z.) f:)1
2
||V + (f(x)) - f(x))) + _
2c
2c
-2p(f(x)) f(x,)) + 4 (f(zz) f(x.)) 4 0²
2c
2c
Let = min| My
f(x+41) ((x.)
f(xx) - -(x))
L
E2
$ B2
-p((((r)) [(x,)) _ (J(ax) - [(xx)) +
002
1/8
1/8
2c
2c
(f(zz) - -s(x.)) 21((((0)) - -(x.)) + (f(z) - -(x.)) +
L
L
0²
2c
2c
1
L
(f(x)) f(xx)) + _
24 +
2c
2c
1 24 + Tmmax
) (f(ze) f(x,)) + 02
2c
2c
Therefore we have the following sequence of inequalities,
f(0141) f(x+)
[((++1)= - f(xx))
(= 22-2u= 24 +
Lmax
(f(xz) - f(xx)) + _o
Eg
< E2
I
1/b
1/:
2c
2c
By the Lower property of expectations and multiplying both sides by th we have
(2
I Imax
7bb 0²
E [[((4)) f(xx)] s T6
2 +
[(f(a)) - -(x))))((x)))+++
a
2c
2c
If v (0,1) then iterating the incquality and summing the goometric scries gives the result,
Blf(041) (f((z) -f(x)) + Σ MoL 2c
0²
Lo
S (f(1)) - f(xx) +
2(1 - v(1v'cc'
Therefore, it remains to show that 0 < v < 1. For the lower bound notice that S 2ehma
1
Lmax 2c
1
2p +
Linax
2 1/
2cLmax
22 +
2c
((2
1 (2c+
1hb
Lmax 2/1 > 0.
2c
Following similar arguments made in Loizou et al.
2021
Theorem 3.6], we can show < 1 by considering
two cases. Recall from our assumptions we have c
Lmaxx 4p
and 1/b < max 1/(( 2p+ Zehmax
therefore
29

---

Published in Transactions on Machine Learning Research (11/2023)
consider the two following cases:
766 2cLmax
(27)
1/6
1
24 + Leyua
(28)
For the first case 27 we have a = T/ and
1
mmx
17b
241 +
1/b
2
Limax
1
21///1 +
2c
(n> Xmax
1 2put + 2p17/b = 1.
For the second
(28 we have 20Lmax
and by the upper bound we have
1
Lina
= 1/b a
241 +
2c
However, we also have a Zchmax S TJb to avoid a contradiction we need
2cLmaxx
1
2/
Lmax 2c
2cTmmax
2p +
Lmnax 20
Which holds by assumption since
Lunax 4y
H Experiment details
In this section provide details for experiments including the updates for different mirror descent algorithms. Note that in all our experiments we have f = 0.
H.1 Compute resources
We ran around thousand experiments using internal cluster, where each experiment uses single NVIDIA Tesla P100 GPU, 40GB of RAM, and 4 CPUs. Some experiments like the synthetic ones took only few minutes to complete, while the deep learning experiments like CIFAR10 took about 12 hours.
H.2 Mirror descent across p-norms
We select (xx) ||=| and X Rd for < S 2. We have in this case that 1b is ue (v 1) strongly convex with respect to the norm I1-11p with dual norm ||-I1, where is such that 1/p + 1/4 = (Orabona 2019). Therefore, as defined in Corollary g mSPS with c = is
(p 1)(f(xx)) f() |A(T))?
Tr min
and similarly for mSPS.
The closed form update for mirror descent this case is given by the following coordinate wise up- dates (Duchi 2018): let d², I2d + Rd with component functions (x(x) = (2= sign(x;) 11,1-1, then the mirror descent update with stepsize n
S++1 (6) (()) m/. (((x)))
30

---

Published in Transactions on Machine Learning Research (11/2023)
H.3 Projected gradient descent with positive constrains
We select ((xa) 1 | to recover projected gradient descent, in this case & is μ4 1 strongly convex with respect to the Euclidean norm and ||-I.. 11-112- Since X' R the non-negative orthant, the projection step amounts to clipping negative values (sctting them to zero).
H.4 Exponentiated gradient with & constraint
We consider the case of supervised learning with constraint set X = fx ||ا|| S A}. In our experiments we consider the exponentiated gradient algorithun we equivalently write the set X as a
set A = 10, 000 convex hull of its corners, X {Az E A2a) where Azd the (2d 1) dimennesial probability simplex and A matrix with 2d columns and d rows,
A
0
0
0
0
0
-
0
A
0
0
Therefore use the exponentiated algorithm with constraint set A2d by selecting v(x) Edd ze log(x;). In this case is ph = strongly convex on A2d with respect to the norm ||-||,- Since the dual norm |I-II. = I1-11oo we have that mSPSmax with 1 is
1) min (f((z)) -()
[V 17
and similarly for mSPS.
The mirror descent update then can be written in two steps Bubeck 2015).
Vt+1 Iz exp(-m f(()))
V++1
Ft+1
Where @ and exp are component wise multiplication and component wise exponentiation respectively.
H.5 Additional Results across p-norms
We observe in Figure 4 that mSPS oulperforms a large grid of step-sizes for most values of p. Note that we used the mushrooms dataset with the kernel bandwidth selected in Vaswani et al. (2019b) which satisfies interpolation.
mushrooms p=1.2
mushrooms p=1.4
mushroams p=1.6
mushrooms p=
Train loss (log)
10-2
13011
10-1
5.1
10-3
10-4
10-2
10
10-1
S00CE
10
10-3
150
100
200
150
100
200
Epoch
Epoch
Epoch
Comparison between mSPS with 1 and constant step-sizes convex binary-clasiffcattion problem on the mushroom datasct.
Figure 4:
For the non-convex multi-class classification problem Figure 5 we use MNIST. MNIST has a training set consisting of 60k examples and a test set 10k examples. We use 1 hidden-layer multi-layer perceptron (MLP) of width 1000. We also observe that mSPS either competitive or better than most constant stepsizes across various values of p.
31

---

Published in Transactions on Machine Learning Research (11/2023)
mnist p=1.2
mnit p=14
mnist p=1.6
mnist p=1.8
10a
10a
10r
Train less (log)
10:
10.
10a
10.1
10
10"
10-2
10-3
10
25
50 Epoch
75
100
23
50 Epoch
75
100
0
25
50 Epech
75
100
25
50
75
100
Epoch
Figure 5: Comparison between mSPS with c and constant step-sizes on MNIST across different values of p.
cifar10 pnorm=1.4 1.4
cifar10 pnom=116
cifar10 pnorm=1.8 1.8
constant
c- 1.0
10a
109
smooth ite
c=0.2
smooth, Iter
c=1.0
(log)
10a
10-1
10-1
10
10-2
10-3
0
50
100
150
200
50
100
150
200
50
100
150
200
Epoch
Epech
Epoch
Figure 6: Comparison between mSPS with and without smoothing on non-convex multiclass classification with deep networks across different values of p.
32


Reviews:
[{"review_id": "efp2Sxwf88", "reviewer": "Reviewer_eT7G", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-structured and provides a comprehensive analysis of the SMD under different conditions. The introduction of Polyak as an adaptive stepsize for SMD seems to be an interesting contribution, and the authors' approach to not using an online to batch reduction is noteworthy. The paper also stands out for its extensive numerical experiments for adaptive SMD across a wide variety of domains and mirror descent algorithms for both constrained and unconstrained problems.\n\n\nIn terms of technical aspects, the analysis of relative smoothness and Polyak step size appears to be fairly standard, and the convergence results are as expected. Additionally, it's unclear to me what the standard for TMLR is, but in my view, this paper may not meet the high standards set by conferences such as ICML or NeurIPS.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates the convergence of stochastic mirror descent (SMD) under interpolation in relatively smooth and smooth convex optimization. The authors provide new convergence guarantees for SMD with a constant stepsize in relatively smooth convex optimization. They also propose a new adaptive stepsize scheme, the mirror stochastic Polyak stepsize (mSPS), for smooth convex optimization. Notably, their convergence results do not make bounded gradient assumptions or bounded variance assumptions, and they show convergence to a neighborhood that vanishes under interpolation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "The use of Polyak'stepsize seems to be of limited use. Maybe I missed something, is it possible to use the adaptive stepsize when the optimal value is unknown? can you provide a discussion?", "broader_impact_concerns": "In my opinion, there don't appear to be any specific concerns regarding Broader Impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CGSjhuM9Ef", "reviewer": "Reviewer_Uiqa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\n- Mirror descent is a powerful extension of gradient descent which covers many instantiations of existing algorithms, e.g., exponentiated gradient, gradient descent. The paper studies convergence rate of stochastic mirror descent. The proposed results are general.\n\n- The existing results often require a bounded sub-gradient assumption or a bounded variance assumption. The paper gives convergence rates without these assumptions.\n\n- The existing analysis on Polyak step size is conducted for SGD. The paper gives the first analysis on Polyak step size for stochastic mirror descent. The analysis seems to be rigorous.\n\n- There are various experimental results.\n\n**Weakness**\n\n- While mirror descent is more general, the framework of studying the convergence of mirror descent has already been established in the literature. The analysis presented in the paper seems to be standard in the mirror descent literature. For example, all the analysis is based on Lemma 1, which has already been developed in the literature.\n\n- Within the recent progress in optimization, people have already known how to handle the unbounded gradient assumption. For example, it is now becoming standard to remove the bounded gradient assumption by using the smoothness assumption of the loss function. Therefore, it is not surprising to remove the bounded gradient assumption in the paper.\n\n- The analysis of Polyak step sizes has already been done for SGD. The paper extends it to SMD. While this extension is definitely useful, it seems that the extension follows standard techniques.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers stochastic mirror descent with both constant step sizes and Polyak stepsizes. For the constant step sizes, the paper presents convergence in a neighborhood for strongly convex problems, and convergence in terms of Bregman distance of $f$ for smooth problems. For the Polyak step sizes, the paper presents convergence in a neighborhood for strongly convex problems, and convergence in function values for smooth and convex problems. Experimental results are presented to show the effectiveness of the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper is very well written and the results are solid. My only concern is the novelty of the analysis. Both the analysis and the results are a bit standard. I would like to see more discussions on the novelty of the paper in the revision, e.g., what are the technical challenges of the extension and technical contributions of the analysis?\n\nMinor comments:\nSection 3.1: \"it it\" should be \"it\"\nSection 5.3.1: \"is a quadratic\" should be \"is quadratic\"\nSection C.1: \"stronly\" should be \"strongly\"", "broader_impact_concerns": "I have no impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HkBDaphuBt", "reviewer": "Reviewer_qw5m", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nAdaptive learning rates such as the Polyak step size have drawn interest in the recent years because of their favourable performance for problems with (almost) interpolation and their improved sensitivity to learning rate tuning. \nThis paper studies the important question how we can make use of these techniques for mirror descent methods where specific variable constraints or domains motivate the use of a different proximal term. \n\nEven though the results of section 5 and 6 seem somewhat unrelated at first sight, the paper has a clear structure and the contributions of these two sections are linked through their relation to the interpolation constant. The paper gives a thorough literature review and relates their results nicely within the context of previous work which makes the paper an enjoyable read.\n\n\nWeaknesses: \n\n* I think that the result of section 5 (e.g. Theorem 1) is useful mainly in the cases where the interpolation constant is reasonably small. A major difference to the works compared in the paper is that one can not force the constant term small by making the step size small (even though the other terms are large). For the result of e.g. Dragomir et al 2021 this is different - the constant term in their work multiplies with the step size. Hence, if the interpolation constant is not very small, the constant term in Thm. 1 is not in control of the user. While this is in general fine for me, I think that it needs to be pointed out and explained clearer as it limits the applicability of the convergence result to problems with zero or reasonably small interpolation constant. \n\n* Regarding the point above, I think that the example in 5.3.1 is insightful to showcase the advantage of your results but also slightly one-sided. You could give a second example where the interpolation constant is large to show what happens in such a case (I would not see it as a weakness if your result is less useful for such settings).\n\n* The same remark applies to Theorem 5 and subsequent results: if $\\eta_b$ is set small then at some point $\\alpha=\\eta_b$ and it will cancel out in the constant term. Hence, the constant term can not be made small by reducing the parameter $\\eta_b$.\n\n* The theoretical results (except for Thm 9 using PL condition) are mainly in the convex setting. From the current paper it is unclear to me if the presented results could be extended to more general nonconvex settings.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the mirror descent method for stochastic optimization. The main contributions are two-fold: on the one hand it proves new theory for constant step-size mirror descent based on an interpolation constant. On the other hand, it proposes a new method which is reminiscent of Polyak's step size adapted to the setting of mirror descent (mSPS). For this new method, theoretical results (mainly for the convex case) are established; experiments show that mSPS achieves good convergence with less tuning due to an adaptive step size.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some of the below are questions which I had while reading - it might be sufficient to clarify them during the discussion period without changing the paper. \n\nOn the theoretical part:\n\n* Do you assume that $\\mathcal{X} \\subset \\mathcal{D}$? This seems to be somewhat implictly assumed in Def. 2 as $B_{\\psi}$ is defined via $\\mathcal{D}$, but I couldn't find it in the paper.\n\n* I think you need to assume that $B_{\\psi}$ is non-negative (e.g. for Corollary 2) i.e. $\\psi$ is convex. I couldn't find this assumption in the paper, but maybe I just skipped it. Can you clarify?\n\n* Page 3: what do you mean with \"bounded constraint\"?\n\n* For the theory of section 6, you use the interpolation constant $\\sigma^2$ and not $\\sigma^2_{\\mathcal{X}}$. I think this comes from the lower bound of $\\eta_t$, but it seemed a bit hidden to me why this is the case - I guess that one would prefer to have $\\sigma^2_{\\mathcal{X}}$ if it was possible. Maybe you could explain this phenomenon in a short sentence/paragraph.\n\n\nOn the experiments:\n\n* For some experiments, it looks like the biggest step size is still the best one for mirror descent e.g. first row or cifar10, p=1.4. I would have expected that the largest one is always too large so that we can be sure that the best step size is among the ones that were run. But maybe its just misleading because there are lines missing from diverged runs? If not, I think you should extend the step size range in order to make sure that the (approximately) best step size is among the ones that were run.\n\n* The runs for ijcnn and rcv1 for the l1-constrained problem look a bit strange: it looks to me like mirror descent would need a smaller step size as the ones that are displayed are already quite unstable. Also the scale of the loss there (in the orders of 10^6) looks uncommonly high to me. Related to this I did not find the value of $\\lambda$ you chose. Further, in section G.4 in the mirror descent update I can't see any influence of $\\lambda$ - but it should have. I think the result from Bubeck, 2015 is only valid if the domain is the simplex, but in your case we have an additional $\\Lambda$?\n\n* I understand that you use the smoothing of $\\eta_b$ and the values of $c$ for mSPS based on the Loizou et al 2021 paper. However, we should be careful as this introduces additional tuning for mSPS which has to be accounted for - in the sense that some hyperparameters are varied per experiment which is not done for Mirror Descent. It is unclear to me when $c=1$ or when $c=0.2$ should be used - is it only depending on convexity and what's the intuition for this? For completeness, it would be nice to see - for example - also the results for the choice $c=1$ in the experiments where $c=0.2$ is used.\n\nMinor remarks:\n\n* In several spots, you write $f_i$ instead of $f_\\xi$ (e.g. page 2, end of first bullet or several times in Appendix F).\n\n* You cite an Assumption right below Assum. 1, from the book of Orabona. As this book has lots of content, it would be nice to be more specific where that assumption can be found in the book. The same applies to the result of Hanzely & Richtarik 2021 and Dragomir et al 2021 in section 5.3. Please state explicitly which theorem you compare to as it makes it easier for the reader. ", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In consensus with the reviewers, I find this paper to have enough novelty and significance to warrant publication, so I am happy to recommend publication.  It's well-written and pushes existing results forward in a few new directions.


Please make a few small changes, e.g., some of the authors in the bibliography have abbreviated first names (A. Nemirovski...) while most others don't; please update references to journal versions when possible; and I'd change the "Anatoli Iouditski" and Nesterov paper to the "Juditsky" transliteration (as he himself uses on his PDF copy, https://arxiv.org/pdf/1401.1792.pdf ).

Lemma 3, the three point property, was proven by Chen and Teboulle, "Convergence analysis of a proximal-like minimization algorithm using Bregman functions", 1993, so I would cite that instead of Bubeck '15/Orabona '19.

One reviewer requested a link to an open source implementation of the experiments, if you have that.

Reviewer qw5m had requested that the case c=1 to be run for the non-convex experiments (in Fig. 3). If this doesn't fit in well with the main paper, it would be OK to put it in the appendix.

Finally, to make the paper more accessible to a general audience, I would add a small section on relative smoothness to the appendix, since it's a new concept (from Lu, Freund & Nesterov '16)
Decision: Accept (poster)