Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize

Introduction

We consider the constrained stochastic optimization problem,

A classical analysis of mirror descent and first-order methods often relies on smoothness with respect to some norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$. The norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$ 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-euclidean 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 et 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 attention. We contribute to the literature of SMD with new constant-stepsize results under relative smoothness and new adaptive-stepsize results under smoothness, both of which use weak assumptions on the noise.

The key contributions of this work are as follows:

Technical assumptions on the noise. 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 or bounded variance assumptions. Instead we use the finite optimal objective difference, introduced by Loizou et al. (2021), for our adaptive smooth setting and introduce a new constrained version for the relative smooth setting. More precisely, Loizou et al. (2021) assume

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 online to batch reduction (Cesa-Bianchi et al., 2004; 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 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 $\sigma^{2}$, and $\sigma_{\mathcal{X}}^{2}$, 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.

Related Work

SMD is often analyzed as a 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 a $O(\nicefrac{{1}}{{\sqrt{T}}})$ convergence rate (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 $O(\nicefrac{{1}}{{T}})$ convergence rate (Hazan & Kale, 2014; Ghadimi & Lan, 2012; Iouditski & Nesterov, 2014). Under smoothness, similar improvements can be made (Dekel et al., 2012; Bubeck, 2015). All of these results use bounded variance or bounded gradient assumptions.Lei & Tang (2018) derive results for non-smooth and strongly convex functions without bounded subgradients but assume a weak growth condition. 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 $\mathcal{X}$ is unbounded, therefore it is common to assume $\mathcal{X}$ is compact.

In relative smooth optimization Hanzely & Richtarik (2021) 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 conditions have mostly been studied with SGD in unconstrained settings (Gower et al., 2019; Vaswani et al., 2019a) or with SMD and conditions that do not incorporate constraints Hanzely & Richtarik (2021). Consequently, these conditions can yield large or unbounded neighborhoods of convergence in constrained optimization. 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 optimum. In comparison, our constraint-aware condition $\sigma_{\mathcal{X}}^{2}$ can hold without interpolation and does not require variance to be zero at the optimum.

Adaptive stepsizes for mirror descent have a long history. Accumulating past gradients or subgradients to set a stepsize, $\eta_{t}\propto\nicefrac{{1}}{{\sqrt{\sum_{s=1}^{t}\left\lvert\left\lvert g_{s}\right\rvert\right\rvert^{2}_{\ast}}}}$ , can be traced back to online learning (Auer et al., 2002; Streeter & McMahan, 2010). Recently, similar coordinate-wise stepsizes such as ADAGRAD (McMahan & 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 & Pál (2018) prove a $\Omega(T)$ worst case lower bound for the regret.Convergence results may still be possible without online to batch reductions; for example, in the case of unconstrained SGD see Li & Orabona (2019). 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 weak assumption on the noise. Another line of related work includes adaptive stepsizes for mirror descent with non-smooth functional constraints (Bayandina, 2017; Bayandina et al., 2018; Stonyakin et al., 2019).

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., 2003; Davis et al., 2018; Hazan & Kakade, 2019). More recently, variations of the Polyak stepsize have been proposed for stochastic optimization (Loizou et al., 2021; Prazeres & Oberman, 2021; Berrada et al., 2020; Gower et al., 2021). The adaptive stepsizes proposed herein are a generalization of SPS proposed and analyzed by Loizou et al. (2021) (see Section 4.2) to the constrained case and for mirror descent.

Background

For a differentiable function $\psi$, we define the difference between $\psi(x)$ and the first order approximation of it at $y$ as the Bregman divergence $B_{\psi}(x;y)$.

A differentiable function $f$ is convex on a convex set $\mathcal{X}$ if $B_{f}(x;y)\geq 0$ for any $x,y\in\mathcal{X}$. Similarly, a function $f$ is $L$-smooth with respect to a norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$ if $B_{f}(x;y)\leq\frac{L}{2}\left\lvert\left\lvert x-y\right\rvert\right\rvert^{2}$, and is $\mu$-strongly convex with respect to the norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$ if $\frac{\mu}{2}\left\lvert\left\lvert x-y\right\rvert\right\rvert^{2}\leq B_{f}(x;y)$.

We will also refer to the generalization of smoothness and strong convexity — relative smoothness and relative strong convexity defined below.

A function $f$ is $L$-smooth relative to $\psi$ on $\mathcal{X}$ if for all $(x,y)\in\mathcal{X}\times(\mathcal{X}\cap\operatorname{int}\mathcal{D})\,$ it holds that: $B_{f}(x;y)\leq LB_{\psi}(x;y).$

A function $f$ is $\mu$-strongly convex relative to $\psi$ on $\mathcal{X}$ if for all $(x,y)\in\mathcal{X}\times(\mathcal{X}\cap\operatorname{int}\mathcal{D})\,$ it holds that: $\mu B_{\psi}(x;y)\leq B_{f}(x;y).$

To solve problem (1) we consider the general stochastic mirror descent update

Where $\xi_{t}$ is a realization of $\xi$ that is i.i.d.. In the non-smooth or deterministic setting $\nabla f_{\xi_{t}}(x_{t})$ may be replaced by a subgradient or the full gradient respectively. To make the updates well defined, all we require is that $x_{t+1}\in\operatorname{int}\mathcal{D}$ in update (4), otherwise $B_{\psi}(\cdot,x_{t+1})$ will be undefined at the next step.

Let $\mathcal{X}\subseteq\mathcal{D}$, then for any $g$, and any stepsize $\eta_{t}>0$, $x_{t+1}=\arg\min_{x\in\mathcal{X}}\,\langle g,x\rangle+\frac{1}{\eta_{t}}B_{\psi}(x;x_{t})\in\operatorname{int}\mathcal{D}$.

For example the following assumption by Orabona (2019) would be sufficient.

The first requirement from Orabona (2019) amounts to assuming $\psi$ is a Legendre function (i.e., essentially smooth and strictly convex), which implies that $x_{t+1}\in\operatorname{int}\mathcal{D}$ (Cesa-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 $x_{t+1}\in\operatorname{int}\mathcal{D}$; for more examples see Bauschke et al. (2003).

Another common assumption is to assume $\psi$ is strongly convex over $\mathcal{X}$, which will be important for our adaptive stepsize in Section 6, however, it it is not needed for the constant step size results of Section 5.

The following is a 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.

Furthermore if $\psi$ is $\mu_{\psi}$-strongly convex over $\mathcal{X}$ then

The SMD update (4) recovers both SGD and SPGD if $\psi$ is taken to be $\frac{1}{2}\left\lvert\left\lvert\cdot\right\rvert\right\rvert{}^{2}_{2}$. Some other interesting examples include the case where $\psi(x)=\frac{1}{2}\left\lvert\left\lvert x\right\rvert\right\rvert_{p}^{2}$ for $1<p\leq 2$ (Grove et al., 2001; Gentile, 2003). If we instead use $\psi(x)=\frac{1}{2}\langle x,Mx\rangle=\frac{1}{2}\left\lvert\left\lvert x\right\rvert\right\rvert^{2}_{M}$ for a positive definite matrix $M$ then we recover the scaled projected gradient algorithm, $x_{t+1}=\arg\min_{x\in\mathcal{X}}\left\lvert\left\lvert x_{t}-\eta_{t}M^{-1}g_{t}-x\right\rvert\right\rvert_{M}^{2}$ (Bertsekas & Tsitsiklis, 2003). Another common setup is when $\psi$ is taken to be the negative entropy with a constraint set $\mathcal{X}=\Delta^{d}=\{x_{i}\geq 0|\sum_{i=1}^{d}x_{i}=1\}$. In this case $\psi$ is $1$-strongly convex with respect to $\left\lvert\left\lvert\cdot\right\rvert\right\rvert_{1}$ and the update rule corresponds to the exponentiated gradient algorithm (Littlestone & Warmuth, 1994; Kivinen & Warmuth, 1997; Beck & Teboulle, 2003; Cesa-Bianchi & Lugosi, 2006).

2 Overparameterization, interpolation, and constrained interpolation

Modern machine learning models are expressive and often over-parametrized, i.e., they can fit or interpolate the training dataset (Zhang et al., 2021). For example when problem (1) 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 $f_{i}$ attains its minimum at $x_{\ast}$. That is the following interpolation condition is satisfied.

Xiao et al. (2022) describe an interpolation-like condition within constraint optimization, however, this condition requires the stochastic gradient to have zero variance at the optimum, which need not hold generally despite all $f_{\xi}$ sharing a common minimum (see for example Figure 1). Therefore, we also make use of the following constrained interpolation condition:

We say that the interpolation condition holds with respect to the constraint $\mathcal{X}$ if there exists $x_{\ast}\in\cal{X}_{\ast}$ such that $f_{\xi}(x_{\ast})=\inf_{x\in\mathcal{X}}f_{\xi}(x)$ almost surely.

Similar to Definition 4 we have interpolation with respect to $\mathcal{X}$ holds when $\sigma^{2}_{\mathcal{X}}=0$. In the finite-sum setting, constrained interpolation reduces to $f_{i}(x_{\ast})=\inf_{x\in\mathcal{X}}f_{i}(x)$ for all $i\in\{1,\cdots,n\}$.

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 of the classic Polyak stepsize and SPS for mirror descent.

When a function is $L$-smooth with respect to the Euclidean norm, a common stepsize for gradient descent is $\eta=\nicefrac{{1}}{{L}}$, allowing for convergence in many settings (Bubeck, 2015). Similarly for an $L$-relatively smooth function with respect to $\psi$, the prescibed stepsize for mirror descent using $\psi$ is $\eta=\nicefrac{{1}}{{L}}$ (Birnbaum et al., 2011; Lu et al., 2018). In the stochastic and relatively smooth case, Hanzely & Richtarik (2021) use $\eta=\nicefrac{{1}}{{L}}$ as well as different stepsize schedules. In Section 5, we provide new convergence guarantees (under weaker assumptions) for SMD with $\eta=\nicefrac{{1}}{{L}}$.

2 Polyak Stepsize

An alternative method to selecting a stepsize, as suggested by Polyak (Polyak, 1987), is to take $\eta_{t}$ by minimizing an upper bound on $\left\lvert\left\lvert x_{t+1}-x_{\ast}\right\rvert\right\rvert_{2}^{2}$. From Lemma 1, if we take $\psi=\frac{1}{2}\left\lvert\left\lvert\cdot\right\rvert\right\rvert^{2}_{2}$ and assume $g_{t}\in\partial f(x_{t})$ is a subgradient at $x_{t}$ for $f$ then we recover a well known inequality for projected subgradient descentAfter using the fact that $g_{t}$ is a subgradient, $f(x_{t})-f(x_{\ast})\leq\langle g_{t},x_{t}-x_{\ast}\rangle$.

Minimizing the right hand size with respect to $\eta_{t}$ yields Polyak’s stepsize, $\eta_{t}=\nicefrac{{(f(x_{t})-f(x_{\ast}))}}{{\left\lvert\left\lvert g_{t}\right\rvert\right\rvert^{2}_{2}}}$ (Polyak, 1987; Beck, 2017). Following in a similar fashion, we propose a generalization of Polyak’s stepsize for mirror descent. If $\psi$ is $\mu_{\psi}$-strongly convexWithout loss of generality we could assume $\psi$ to be 1-strongly convex and scale $\psi$ by $\nicefrac{{1}}{{\mu_{\psi}}}$. The stepsize would remain the same, scaling of $\psi$ inversely scales the stepsize. with respect to the norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$ then we can minimize the right hand side of equation (6) to arrive at the mirror Polyak stepsize

Despite the well-known connection between projected subgradient descent and mirror descent (Beck & Teboulle, 2003), this generalization of Polyak’s stepsize is absent from the literature. For completeness, we include analysis of the non-smooth case in Section C of the appendix, including both a $O(\nicefrac{{1}}{{\sqrt{t}}})$ convergence and a last iterate convergence result. As expected, mirror descent with the mirror Polyak stepsize maintains the benefits of mirror descent — it permits a mild dependence on the dimension of the space. However, it inherits the impractical issues with the Polyak stepsize — knowledge of $f(x_{\ast})$ and an exact gradient or subgradient.

In the stochastic setting Loizou et al. (2021) propose the more practical stochastic Polyak stepsize (SPS), $\eta_{t}=\nicefrac{{(f_{\xi_{t}}(x_{t})-f_{\xi_{t}}^{\ast})}}{{c\left\lvert\left\lvert\nabla f_{\xi_{t}}(x_{t})\right\rvert\right\rvert^{2}_{2}}}$, and the bounded variant SPSmax, $\eta_{t}=\min\{\nicefrac{{(f_{\xi_{t}}(x_{t})-f_{\xi_{t}}^{\ast})}}{{c\left\lvert\left\lvert\nabla f_{\xi_{t}}(x_{t})\right\rvert\right\rvert^{2}_{2}}},\eta_{b}\}$. Where $f_{\xi_{t}}^{\ast}$ is known in many machine learning applications, and $c$ is a scaling parameter that depends on the class of functions being optimized (Loizou et al., 2021).

Similar to our generalization of Polyak’s stepsize (7), we propose a generalization of SPS and SPSmax for mirror descent, the mirror stochastic Polyak stepsize (mSPS) and the bounded variant mSPSmax,

An important property of SPS and mSPS is its self-bounding property for when $f_{\xi_{t}}$ is $L$-smooth and $\mu$-strongly convex with respect to a norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$,

We extensively use the lower bound, also known as the self-bounding property of smooth functions (Srebro et al., 2010), and we provide a complete proof in the appendix (Section D). A proof of the upper bound can be found in Orabona (2019)[Corollary 7.6].

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 of Lemma 2 in Collins et al. (2008), where the exponentiated gradient algorithm is studied under the relative smoothness assumption.

Suppose $f$ is $L$-smooth relative to $\psi$. Then if $\eta\leq\frac{1}{L}$ we have

For an appropriately selected stepsize, we have that SMD enjoys a linear rate of convergence to a neighborhood of the minimum $x_{\ast}$.

Assume $\psi$ satisfies assumption 1. Furthermore assume $f$ to be $\mu$-strongly convex relative to $\psi$ over $\mathcal{X}$, and $f_{\xi}$ to be $L$-smooth relative to $\psi$ over $\mathcal{X}$ almost surely. Then SMD with stepsize $\eta\leq\frac{1}{L}$ guarantees

In the case of interpolation, we have that $B_{\psi}(x_{\ast};x_{t+1})\to 0$ almost surely. If $\psi$ is strictly convex then $x_{t}\to x_{\ast}$ almost surely.

Under the same assumptions as Theorem 1, if $\sigma^{2}_{\mathcal{X}}=0$ then $B_{\psi}(x_{\ast};x_{t+1})\to 0$ almost surely.

2 Relative smoothness without convexity

Similar to Theorem 1 we show convergence of a quantity to a neighborhood, only assuming $f_{\xi}$ to be $L$-smooth relative to $\psi$, where $f$ or $f_{\xi}$ need not be convex.

Assume $\psi$ satisfies assumption 1. Furthermore assume $f_{\xi}$ to be $L$-smooth relative to $\psi$ over $\mathcal{X}$ almost surely. Then SMD with stepsize $\eta\leq\frac{1}{L}$ guarantees

Similar to Theorem 1, an almost surely convergence result follows from Theorem 3 under interpolation.

Under the assumptions of Theorem 3, if $f$ is convex and $\sigma^{2}_{\mathcal{X}}=0$ then $B_{f}(x_{\ast};x_{t})\to 0$ almost surely.

More formally, solving a constrained linear system amounts to to finding $x_{\ast}$ such that

Problem (11) can be reformulated as a constrained finite sum problem with $f_{i}(x)=\frac{1}{2}(\langle A_{i:},x\rangle-b_{i})^{2}$, where $A_{i:}$ and $b_{i}$ denote the $i^{th}$ row and component of $A$ and $b$ respectively. Note that $x_{\ast}$ interpolates all $f_{i}$ since $f_{i}(x_{\ast})=0$ by construction, with $\nabla f_{i}(x_{\ast})=0$ and $\sigma^{2}_{\mathcal{X}}=0$. Since the divergence $B_{f_{i}}$ is symmetricSee Proposition 1 in the appendix for a proof. and $B_{f}$ is simply the average over $B_{f_{i}}$ it holds that

Where the third equality follows from the fact that $\nabla f_{i}(x_{\ast})=0$.

2.2 EG for finding stationary distributions of Markov chains

Problem (12) is ubiquitous in science and machine learning, for example in online learning many algorithms require computing a stationary distribution of a Markov chain at each iteration(Greenwald et al., 2006; Blum & Mansour, 2007).

Where $\odot$ and $\exp$ are component wise multiplication and component wise exponentiation respectively.

We highlight that no other existing works show convergence without a neighborhood under interpolation for the EG algorithm. Additionally, problem (12) also exhibits a natural occurence where $f_{i}^{\ast}$ is known and equal to , rendering mSPS (8) computable. In Section 6, we demonstrate similar guarantees with mSPS.

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 neighborhoods. We provide an in-depth comparison as well as demonstrate via an example where convergence to the solution is not guaranteed by previous works but is possible by Theorem 1.

In comparison to Hanzely & Richtarik (2021), their results apply with a neighborhood of convergence equal to $\approx 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.

Convergence of mirror SPS

In this section we present our convergence results for SMD with mSPSmax when $f_{i}$ are $L_{i}$-smooth and with varying assumptions. First, we consider the case when $f$ is strongly convex relative to $\psi$, a common assumption when analysing mirror descent under strong convexity Hazan & Kale (2014). Then we present rates under convexity and smoothness but without relatively strong convexity. Afterwards, we discuss the results under interpolation and provide examples.

With strong convexity of $\psi$ and $f$ being relatively strongly convex with respect to $\psi$ we can show a linear rate of convergence to a neighborhood.

Assume $f_{\xi}$ is convex and $L$-smooth almost surely with respect to the norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$. Furthermore, assume that $f$ is $\mu$-strongly convex relative to $\psi$ over $\mathcal{X}$, where $\psi$ is $\mu_{\psi}$-strongly convex over $\mathcal{X}$ with respect to the norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$ and assumption 1 holds. Then SMD with mSPSmax and $c\geq\frac{1}{2}$ guarantees

Where $\alpha\coloneqq\min\{\nicefrac{{\mu_{\psi}}}{{2cL}},\eta_{b}\}$.

Since $\psi$ is strongly convex we get a guarantee on expected distance to the minimum, as $\frac{\mu_{\psi}}{2}\left\lvert\left\lvert x_{\ast}-x_{t+1}\right\rvert\right\rvert^{2}\leq B_{\psi}(x_{\ast};x_{t+1})$. Also, if each $f_{i}$ is a strongly convex function or if it satisfies the Polyak-Łojasiewicz (PL) condition (Assumption 2) then mSPS is upper bounded by equation (10) and equivalent to mSPSmax with $\eta_{b}=\nicefrac{{\mu_{\psi}}}{{2c\mu}}$. Therefore, SMD with mSPS converges by Theorem 5.

A similar result was shown for SGD with SPSmax Loizou et al. (2021)[Theorem 3.1]. Indeed, Theorem 5 generalizes their results; by taking $\psi(x)=\frac{1}{2}\left\lvert\left\lvert x\right\rvert\right\rvert^{2}_{2}$ we recover a result which is true for both SGD and SPGD.

In Loizou et al. (2021) constant stepsize results are derived as a special case of SPSmax, similarly if in mSPSmax $\eta_{b}$ is selected such that $\eta_{b}\leq\nicefrac{{\mu_{\psi}}}{{2cL_{\max}}}$ then $\eta_{t}$ is a constant and we can derive new constant stepsize results for SMD. However, using Theorem 5 and mSPSmax to analyze constant stepsize SMD yields weaker results than Theorem 1. The assumptions made in Theorem 5 are stronger. For example, Theorem 5 requires $\psi$ to be both strongly convex and smooth on $\mathcal{X}$ with respect to a norm which would not be possible if $\psi$ is Legendre over $\mathcal{X}$ and $\mathcal{X}$ is bounded. This limitation, however, does not apply for Theorem 1 and the next result for smooth convex losses since we do not enforce a smoothness condition on $\psi$.

2 Smooth and convex

Without $f$ being relatively strongly convex we can attain convergence results on the average function value.

If $f_{\xi}$ is convex and $L$-smooth with respect to a norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$ almost surely, assumption 1 holds, and $\psi$ is $\mu_{\psi}$-strongly convex over $\mathcal{X}$ with respect to $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$. Then mirror descent with mSPSmax and $c\geq 1$ guarantees

Where $\alpha\coloneqq\min\{\nicefrac{{\mu_{\psi}}}{{2cL}},\eta_{b}\}$.

Similarly to Theorem 5 we can derive constant stepsize results, except we require $\eta_{b}\leq\nicefrac{{\psi}}{{2L_{\max}}}$ (with $c=1$), see Section F.2.1 for details. Unlike Theorem 5, however, this result does not require $\psi$ to be smooth over $\mathcal{X}$.

3 Exact convergence with adaptive stepsizes and interpolation

As a consequence of the previous results, we have several convergence guarantees under interpolation ($\sigma^{2}=0$). In fact, when $\sigma^{2}=0$ the upper bound $\eta_{b}$ is not needed, the unbounded variant mSPS will enjoy the same convergence rates as mSPSmax. 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.

4 Mirror descent examples

To demonstrate the generality of our results we consider two cases of Theorem 7. 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 $\left\lvert\left\lvert\cdot\right\rvert\right\rvert{}_{1}$.

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 $c=1$. In theory the bounded stepsize mSPSmax 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. (2021) by selecting $c=0.2$ and a smoothing procedure to set a moving upper bound for mSPSmax.This technique is a moving upperbound. More precisely we run mSPSmax with an upper bound at time $t$ given by $\eta_{b}^{t}=\tau^{b/n}\eta_{t-1}$ where $b$ and $n$ are the batchsize and number of examples respectively, which amounts to $\tau^{b/n}\approx 1$ in our experiments, with $\eta_{b}^{t}\approx\eta_{t-1}$. To compare against a constant stepsize we sweep over $\{10^{-5},10^{-4},10^{-3},10^{-2},10^{-1},1,10^{1},10^{2},10^{3},10^{4},10^{5}\}$.

We consider a convex binary-classification problems using radial basis function (RBF) kernels. We experiment on the ijcnn dataset obtained from LIBSVM (Chang & Lin, 2011) which does not satisfy interpolation.In the appendix we include results on the mushroom dataset where interpolation is satisfied. ijcnn has 22 dimensions, 39,992 training examples, and 9998 test examples. We selected the kernel bandwidth 0.05 following Vaswani et al. (2019b). For these experiments we compare across $p$ $\in\{1.2,1.4,1.6,1.8\}$ 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 observations: (i) mSPS performs reasonably well across different values of $p$ and outperforms most stepsizes of SMD. (ii) mSPS performs well on ijcnn even though it is not separable in the kernel space (i.e. there is 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.

2 Projected gradient descent

In this setup we consider optimizing the logistic loss with a non-negative constraint on the parameters. We run our optimizers on two real-datasets ijcnn and rcv1. rcv1 has 47,236 dimensions, 16194 training examples and 4048 test examples. Following Vaswani et al. (2019b) we selected the RBF kernel on rcv1 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 generate a 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.

3 Exponentiated gradient

For these experiments we test our optimizers on rcv1 and ijcnn and the two synthetic 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 $c$ is kept at 1 and in some cases outperforms the best tuned SMD. Note that the constant stepsizes that don’t appear in the plots have diverged.

4 p𝑝p-norm for optimizing deep networks

For mutliclass-classification with deep networks, we considered the $p$-norm algorithms for the CIFAR10 dataset. CIFAR10 has 10 classes and we used the standard training set consisting of 50k examples and a test set of 10k. As in the kernel experiments, we evaluated the optimizers using the softmax loss for different values of $p$. We used the experimental setup proposed in Loizou et al. (2021) and used a batch-size of 128 for all methods and datasets. We used the standard image-classification 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.

From Figure 3, we observe that: (i) mSPS with $c=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$.

Conclusions and future work

Stochastic mirror descent (SMD) is a powerful generalization of stochastic projected gradient descent to solve problems without a Euclidean structure. We provide new convergence analysis for SMD with constant stepsize in relatively smooth optimization and with the new adaptive stepsizes mSPS, mSPSmax, 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 no tuning but is nonetheless competitive or better than 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 mSPSmax in Theorem 5 requires $\psi$ to be smooth over $\mathcal{X}$, an assumption not required for our constant stepsize results in Section 5, it would be interesting to unify the results by developing a variant of mSPSmax for the more general relatively smooth problem.

References

Appendix A Appendix

The appendices include omitted proofs, other results, and additional experiments. The material is organized as follows: standard mirror descent results are presented in Section B; non-smooth analysis of mirror descent with the mirror Polyak stepsize is given in Section C; the lower bound proof of mSPS is included in Section D; the proofs for the results in Section 5 are presented in Section E, including Theorem 1 and Theorem 3; proofs for Section 6 are given in Section F, including a non-convex result for preconditioned SGD in Section F.3; experiment details are given in Section G.

Appendix B Mirror descent lemmas

Furthermore if $\psi$ is $\mu_{\psi}$ strongly convex over $\mathcal{X}$ then

The proof follows closely to the one presented in Orabona (2019)[Lemma 6.7]. First observe that $x_{t+1}$ statisfies the first order optimality condition

since $\nabla_{x}B_{\psi}(x;x_{t})=\nabla\psi(x)-\nabla\psi(x_{t})$.

We start by examining the inner product $\langle\eta_{t}g_{t},x_{t}-x_{\ast}\rangle$ and adding subtracting quantities to make the first order optimality condition appear.

Rearranging gives the first result. Note at this point we only require $\psi$ to be convex and $\psi$ to be differentiable at $x_{t}$ and $x_{t+1}$, which is guaranteed by assumption 1. To obtain the second result, observe

Appendix C 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.

Assume $f$ is convex with bounded subgradients, $\left\lvert\left\lvert\partial f(x_{t})\right\rvert\right\rvert_{\ast}\leq G$. Let $\psi$ be $\mu_{\psi}$ strongly convex with respect to the norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$, and assume that Assumption 1 holds. Then mirror descent with stepsize $\eta_{t}=\frac{\mu_{\psi}\left(f(x_{t})-f(x_{\ast})\right)}{\left\lvert\left\lvert\partial f(x_{t})\right\rvert\right\rvert^{2}_{\ast}}$ satisfies,

where $\bar{x}_{t}=\frac{1}{t}\sum_{s=1}^{t}x_{s}$. The same result holds for the best iterate $f(x_{t}^{\ast})=\min_{s}\{f(x_{s})\}_{1\leq s\leq t}$. Moreover, we have $\lim_{t\to\infty}f(x_{t})=f(x_{\ast})$.

Let $g_{t}$ be a subgradient of $f$ at $x_{t}$ used to compute $\eta_{t}$. Then by Lemma 1 we have

Rearranging and summing across time we have

Applying the upper bound $\left\lvert\left\lvert g_{s}\right\rvert\right\rvert_{\ast}\leq G$ and taking the square root gives,

The result then follows by the convexity of $f$ and concavity of the square root function,

To obtain the best iterate result notice that $f(x_{t}^{\ast})-f(x_{\ast}))\leq\frac{1}{t}\sum_{s=1}^{t}(f(x_{s})-f(x_{\ast}))$.

To attain the limiting result observe that 16 implies

Giving the result $\lim_{t\to\infty}f(x_{t})=f(x_{\ast})$. ∎

Under the same assumptions as Theorem 10 we have that mirror descent converges to a point. First we provide a useful lemma applicable to mirror descent with a stronly convex mirror map $\psi$.

Suppose $\psi$ is strongly convex, then if the sequece $\{x_{t}\}_{t\geq 1}$ is Bregman monotone with respect to a set $\mathcal{X}$, that is for any $x\in\mathcal{S}$ we have

then $x_{t}\to x_{\ast}\in S$ if and only if all the sequential cluster points of $\{x_{t}\}_{t\geq 1}$ are contained in $\mathcal{S}$.

If the sequence is $\{x_{t}\}_{t\geq 1}$ is Bregman monotone then by strong convexity

Under the same assumptions as Theorem 10, mirror descent converges to a solution,

for some $x_{\ast}\in\mathcal{X}_{\ast}$.

From Theorem 10 we have the following inequality,

Therefore by Lemma 2 it remains to show that all limit points of $x_{t}$ are contained within $\mathcal{X}_{\ast}$.

By Theorem 10 we have that $f(x_{t})\to f(x_{\ast})$. For any limit point $x_{l}$ we have a subsequence $x_{b_{t}}$ such that $x_{b_{t}}\to x_{l}$ and by continuity of $f$ $x_{l}$ must be a solution,

Appendix D Proof of mSPS lower bound in section 4

The lower bound of mSPS (10) when $f_{\xi}$ is L smooth, restated below, is vital to our analysis,

Notice the above inequality is equivalent to

The first inequality is attained by multiplying both sides by $\nicefrac{{\mu_{\psi}}}{{c}}$. We provide a detailed proof below.

Therefore we have the following upper bound on $\inf_{y}f(y)$.

Simplifying and rearranging gives the result. ∎

Appendix E Proofs for section 5

Suppose $f$ is $L$ smooth relative to $\psi$. Then if $\eta\leq\frac{1}{L}$ we have

Since $f$ is $L$ smooth relative to $\psi$ it is also $\frac{1}{\eta}$ smooth relative to $\psi$ (because $L\leq\frac{1}{\eta}$ and $\psi$ is convex). Therefore,

Now we examine the inner product $\eta\langle\nabla f(x_{t}),x_{t}-x_{t+1}\rangle$,

E.2 Proof of Theorem 1

Assume $\psi$ satisfies assumption 1. Furthermore assume $f$ to be $\mu$-strongly convex relative to $\psi$ over $\mathcal{X}$, and $f_{\xi}$ to be $L$-smooth relative to $\psi$ over $\mathcal{X}$ almost surely. Then SMD with stepsize $\eta\leq\frac{1}{L}$ guarantees

From Lemma 1 (before applying strong convexity but assuming convexity of $\psi$) we have

By taking an expectation conditioning on $(\xi_{1},\cdots,\xi_{t})$ we obtain,

Now by the tower property of expectations and applying the definition of $\sigma_{\mathcal{X}}^{2}$,

Where the last inequality follows by $\sum_{s=0}^{t-1}(1-\mu\eta)^{s}\leq\sum_{s=0}^{\infty}(1-\mu\eta)^{s}=\nicefrac{{1}}{{\mu\eta}}$. ∎

Under the same assumptions at Theorem 1, if $\sigma^{2}_{\mathcal{X}}=0$ then $B_{\psi}(x_{\ast};x_{t+1})\to 0$ almost surely.

By Theorem 1 the following inequality holds:

The result then follows by Franci & Grammatico (2022)[Lemma 4.7]. ∎

E.3 Proof of Theorem 3

Assume $\psi$ satisfies assumption 1. Furthermore assume $f_{\xi}$ to be $L$-smooth relative to $\psi$ over $\mathcal{X}$ almost surely. Then SMD with stepsize $\eta\leq\frac{1}{L}$ guarantees

Note that in the proof of Theorem 1 relative strong convexity is not used to attain the inequality (17). Therefore we have,

After applying the tower property, definition of $\sigma^{2}$, and rearranging, we have

Summing across time and dividing by $\eta t$ gives the result. ∎

Under the assumptions of Theorem 3, if $f$ is convex and $\sigma^{2}_{\mathcal{X}}=0$ then $B_{f}(x_{\ast};x_{t})\to 0$ almost surely.

Since $f$ is convex $B_{f}(x_{\ast};x_{t})\geq 0$, therefore, by the Robbins-Siegmun Lemma (e.g. (Franci & Grammatico, 2022)[Lemma 4.1]) $B_{f}(x_{\ast};x_{t})\to 0$ almost surely.

Let $f(x)=\frac{1}{2}\left(\langle g,x\rangle-b\right)^{2}$ then $B_{f}(x;y)=B_{f}(y;x)$.

Note that $\nabla f(x)=\left(\langle g,x\rangle-b\right)g$. Therefore,

Appendix F Proofs for section 6

Notice that by definition of mSPSmax we have the following upper bound

Muliplying both sides of the inequality with $\nicefrac{{\eta_{t}\left\lvert\left\lvert\nabla f_{i}(x_{t})\right\rvert\right\rvert^{2}_{\ast}}}{{\mu_{\psi}}}$ gives the following useful inequality,

The inequality holds with equality for mSPS.

Assume $f_{\xi}$ is convex and $L$-smooth almost surely with respect to the norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$. Furthermore, assume that $f$ is $\mu$-strongly convex relative to $\psi$ over $\mathcal{X}$, where $\psi$ is $\mu_{\psi}$-strongly convex over $\mathcal{X}$ with respect to the norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$ and assumption 1 holds. Then SMD with mSPSmax and $c\geq\frac{1}{2}$ guarantees

Where $\alpha\coloneqq\min\{\nicefrac{{\mu_{\psi}}}{{2cL}},\eta_{b}\}$.

Taking an expectation over $i$ condition on $x_{t}$ gives

Now by the tower property of expectations and applying the definition of $\sigma^{2}$,

Where the last inequality follows by $\sum_{s=0}^{t-1}(1-\mu\alpha)^{s}\leq\sum_{s=0}^{\infty}(1-\mu\alpha)^{s}=\nicefrac{{1}}{{\mu\alpha}}$. ∎

F.2 Proof of Theorem 7

If $f_{\xi}$ is convex and $L$-smooth with respect to a norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$ almost surely, assumption 1 holds, and $\psi$ is $\mu_{\psi}$-strongly convex over $\mathcal{X}$ with respect to $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$. Then mirror descent with mSPSmax and $c\geq 1$ guarantees

Where $\alpha\coloneqq\min\{\nicefrac{{\mu_{\psi}}}{{2cL}},\eta_{b}\}$.

Taking an expectation on both sides, dividing by $\alpha$, and applying the definition of $\sigma^{2}$ yields

Summing across time, applying convexity of $f$, and dividing by $t$ gives

In this section we present the constant stepsize corollary for Theorem 7. If $\eta_{b}\leq\nicefrac{{\mu_{\psi}}}{{2L}}$ then mSPSmax with $c=1$ is a constant stepsize because of the lower bound (10), $\eta_{t}=\eta_{b}$, and we have that $\eta_{b}=\alpha$. Therefore plugging in these values into Theorem 7 gives the following corollary.

Assume $f_{\xi}$ is convex and $L$ smooth with respect to a norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$ almost surely, assumption 1 holds, and $\psi$ is $\mu_{\psi}$ strongly convex over $\mathcal{X}$ with respect to the norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert$. Then stochastic mirror descent with $\eta\leq\nicefrac{{\mu_{\psi}}}{{2L}}$ guarantees

F.3 SGD with preconditioning

In this section we extend the result of mSPSmax 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 preconditioned SGD. Note that in this case we have $\psi(x)=\frac{1}{2}\langle x,Mx\rangle$ is ($\mu_{\psi}=1$)-stronlgy convex with respect to the norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert_{M}$ and $B_{\psi}(x;y)=\frac{1}{2}\left\lvert\left\lvert x-y\right\rvert\right\rvert^{2}_{M}$.

Assume that $f$ and $f_{\xi}$ are $L$ smooth with respect to the norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert_{M}$ almost surely, where $M$ is a positive definite matrix. Furthermore, assume that $f$ satisfies the PL condition (26) with respect to the norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert_{M^{-1}}$, then unconstrained stochastic mirror descent with $\psi(x)=\frac{1}{2}\left\lvert\left\lvert x\right\rvert\right\rvert_{M}^{2}$ and stepsizes

with $c>\frac{L_{\max}}{4\mu}$ and $\eta_{b}<\max\left\{\nicefrac{{1}}{{\left(\frac{1}{\alpha}-2\mu+\frac{L_{\max}}{2c}\right)}},\frac{1}{2cL_{\max}}\right\}$, guarantees

where $\alpha=\min\{\frac{1}{2cL_{\max}},\eta_{b}\}$ and $\nu=\eta_{b}(\frac{1}{\alpha}-2\mu+\frac{L_{\max}}{2c})\in(0,1)$.

We have that the algorithm performs updates of the form

We first apply the $L$ smoothness upper bound on $f$,

We proceed by taking an expectation over $\xi_{t}$ condition on knowing $x_{t}$.

Let $\alpha=\min\{\frac{\mu_{\psi}}{2cL_{\max}},\eta_{b}\}$.

Therefore we have the following sequence of inequalities,

By the tower property of expectations and multiplying both sides by $\eta_{b}$ we have

If $\nu\in(0,1)$ then iterating the inequality and summing the geometric series gives the result,

Therefore, it remains to show that $0<\nu<1$. For the lower bound notice that $\alpha\leq\frac{1}{2cL_{\max}}$,

Following similar arguments made in Loizou et al. (2021)[Theorem 3.6], we can show $\nu<1$ by considering two cases. Recall from our assumptions we have $c>\frac{L_{\max}}{4\mu}$ and $\eta_{b}<\max\left\{\nicefrac{{1}}{{\left(\frac{1}{\alpha}-2\mu+\frac{L_{\max}}{2c}\right)}},\frac{1}{2cL_{\max}}\right\}$, therefore we consider the two following cases:

For the first case (27) we have $\alpha=\eta_{b}$ and

For the second case (28) we have $\alpha=\frac{1}{2cL_{\max}}$ and by the upper bound we have

However, we also have $\alpha=\frac{1}{2cL_{\max}}\leq\eta_{b}$, to avoid a contradiction we need

Which holds by assumption since $c>\frac{L_{\max}}{4\mu}$. ∎

Appendix G Experiment details

In this section we provide details for our experiments including the updates for different mirror descent algorithms. Note that in all our experiments we have $f_{i}^{\ast}=0$.

We ran around a thousand experiments using an internal cluster, where each experiment uses a 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.

G.2 Mirror descent across p-norms

G.3 Projected gradient descent with positive constrains

We consider the case of supervised learning with constraint set $\mathcal{X}=\{x:\left\lvert\left\lvert x\right\rvert\right\rvert_{1}\leq\lambda\}$. To consider the exponentiated gradient algorithm we equivalently write the set $\mathcal{X}$ as a convex hull of its corners, $\mathcal{X}=\{\Lambda x:x\in\Delta_{2d}\}$ where $\Delta_{2d}$ is the $(2d-1)$-dimensional probability simplex and $\Lambda$ is a matrix with $2d$ columns and $d$ rows,

Therefore we can use the exponentiated algorithm with constraint set $\Delta_{2d}$ by selecting $\psi(x)=\sum_{i=1}^{2d}x_{i}\log(x_{i})$. In this case $\psi$ is $\mu_{\psi}=1$ strongly convex on $\Delta_{2d}$ with respect to the norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert_{1}$. Since the dual norm $\left\lvert\left\lvert\cdot\right\rvert\right\rvert_{\ast}=\left\lvert\left\lvert\cdot\right\rvert\right\rvert_{\infty}$ we have that mSPSmax with $c=1$ is

The mirror descent update then can be written in two steps (Bubeck, 2015),

Where $\odot$ and $\exp$ are component wise multiplication and component wise exponentiation respectively.

G.5 Additional Results across p-norms

We observe in Figure 4 that mSPS outperforms 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.

For the non-convex multi-class classification problem in Figure 5 we use MNIST. MNIST has a training set consisting of 60k examples and a test set of 10k examples. We use a 1 hidden-layer multi-layer perceptron (MLP) of width 1000. We also observe that mSPS is either competitive or better than most constant stepsizes across various values of $p$.