Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization

Introduction

Although the class of smooth nonconvex problems can be effectively solved by the above provably optimal algorithms, it does not include many important modern machine learning applications, e.g., distributionally robust optimization (DRO) (jin2021non, ) and language model learning (zhang2019gradient, ), etc. Specifically, for the problems involved in these applications, they are not globally smooth but have been shown to satisfy certain generalized-smooth conditions, in which the smoothness parameters scale with the gradient norm in various ways (see the formal definitions in Section 2). To solve these generalized-smooth-type nonconvex problems, the existing works have developed various gradient-based algorithms, but only with sub-optimal complexity results for stochastic optimization. Therefore, we are motivated to systematically build a comprehensive understanding of generalized-smooth functions and develop algorithms with improved complexities.

To achieve this overarching goal, we need to address several fundamental challenges. First, the existing generalized-smooth conditions are proposed for specific application examples. Therefore, they define relatively restricted classes of functions that do not cover many popular ones such as high-order polynomials and exponential functions. Thus, we are motivated to consider the following question.

Q1: How to extend the existing notion of generalized-smoothness to cover a broad range of functions used in machine learning practice? What are the fundamental properties of the functions in this class?

Second, for such an extended class of generalized-smooth problems, it is expected that first-order algorithms may generally suffer from higher computation complexity (as compared to solving smooth problems). On the other hand, it is unclear how to design first-order algorithms that can efficiently solve these more challenging problems. Therefore, we aim to answer the following question.

Q2: Can first-order algorithms solve generalized-smooth nonconvex problems as efficiently as solving smooth nonconvex problems? In particular, what algorithms can achieve the optimal complexities?

In this paper, we provide comprehensive and affirmative answers to the aforementioned fundamental questions. Our contributions are summarized as follows.

We propose a class of $\alpha$-symmetric generalized-smooth functions, denoted by $\mathbf{\mathcal{L}}_{\text{sym}}^{*}(\alpha)$, which we show strictly contains the popular class of $L$-smooth functions (i.e., functions with Lipschitz continuous gradient), the class of asymmetric generalized-smooth functions (levy2020large, ; jin2021non, ) and the class of Hessian-based generalized-smooth functions (zhang2019gradient, ) (see the definitions in Section 2). In particular, we show that our proposed function class $\mathbf{\mathcal{L}}_{\text{sym}}^{*}(\alpha)$ includes a wide range of popular machine learning problems and functions used in practice, including distributionally robust optimization (levy2020large, ; jin2021non, ), objective function of language models (zhang2019gradient, ), high-order polynomials and exponential functions.

We study the fundamental properties of functions in the class $\mathbf{\mathcal{L}}_{\text{sym}}^{*}(\alpha)$ and establish new decent lemmas for functions in $\mathbf{\mathcal{L}}_{\text{sym}}^{*}(\alpha)$ with different values of $\alpha$ (See Proposition 3.2). These technical tools play an important role later in designing new gradient-based algorithms and developing their corresponding convergence analysis.

In summary, our work reveals that generalized-smooth nonconvex (stochastic) optimization is as efficient as smooth nonconvex (stochastic) optimization, and the optimal complexities can be achieved by $\beta$-GD (for deterministic case) and SPIDER (for stochastic case), respectively.

2 Related Work

Hessian-based Generalized-smooth Functions $\mathcal{L}_{\text{H}}^{*}$: (zhang2019gradient, ) extended the $L$-smooth function class to a Hessian-based generalized-smooth function class $\mathcal{L}_{\text{H}}^{*}$ which allows the Lipschitz constant to linearly increase with the gradient norm (see Definition 2.2) and thus includes higher-order polynomials and many language models that are not $L$-smooth. For objective function on $\mathcal{L}_{\text{H}}^{*}$, (zhang2019gradient, ) also proposed clipped GD and normalized GD which keep the optimal iteration complexity $\mathcal{O}(\epsilon^{-2})$, and proposed clipped SGD which also achieves sample complexity $\mathcal{O}(\epsilon^{-4})$. (zhang2020improved, ) proposed a general framework for clipped GD/SGD with momentum acceleration and obtained the same complexities for both deterministic and stochastic optimization. (zhao2021convergence, ) obtained sample complexity $\mathcal{O}(\epsilon^{-4})$ for normalized SGD with both small constant stepsize and diminishing stepsize. A contemporary work (reisizadeh2023variance, ) reduced the sample complexity to $\mathcal{O}(\epsilon^{-3})$ by combining SPIDER variance reduction technique with gradient clipping.

Asymmetric Generalized-Smooth Functions $\mathbf{\mathcal{L}}_{\text{asym}}^{*}$: Variants of clipped/normalized GD and SGD have been proposed on the asymmetric generalized-smooth function class $\mathbf{\mathcal{L}}_{\text{asym}}^{*}$, which looks like a first-order variant of $\mathcal{L}_{\text{H}}^{*}$ (see Definition 2.1). For example, (jin2021non, ) applied mini-batch normalized SGD with momentum proposed by (cutkosky2020momentum, ) to distributionally robust optimization problem which has been proved equivalent to minimizing a function in $\mathbf{\mathcal{L}}_{\text{asym}}^{*}$ (levy2020large, ; jin2021non, ), and also obtained sample complexity $\mathcal{O}(\epsilon^{-4})$. (yang2022normalized, ) made normalized and clipped SGD differentially private by adding Gaussian noise. (crawshawrobustness2022, ) proposed generalized signSGD with ADAM-type normalization and obtained sample complexity $\mathcal{O}(\epsilon^{-4})$ on a smaller coordinate-wise version of $\mathbf{\mathcal{L}}_{\text{asym}}^{*}$.

Existing Notions of Generalized-Smoothness

The class of $L$-smooth functions, which we denote as $\mathcal{L}$, includes all continuously differentiable functions with Lipschitz continuous gradient. Specifically, for any $f\in\mathcal{L}$, there exists $L_{0}>0$ such that

Many useful functions fall into this class, e.g., quadratic functions, logistic functions, etc. Nevertheless, $\mathcal{L}$ is a restricted function class that cannot efficiently model a broad class of functions, including higher-order polynomials, exponential functions, etc. For example, consider the one-dimensional polynomial function $f(x)=x^{4}$ in the range $x\in$. According to (1), its smoothness parameter $L_{0}$ can be as large as $1200$, leading to an ill-conditioned problem that hinders optimization.

To address this issue and provide a better model for optimization, previous works have introduced various notions of generalized-smoothness, which cover a broader class of functions that are used in machine learning applications. For example, distributionally robust optimization (DRO) is an important machine learning problem, and recently it has been proved that DRO can be reformulated as another problem whose objective function belongs to the following asymmetric generalized-smooth function class ($\mathbf{\mathcal{L}}_{\text{asym}}^{*}$) (levy2020large, ; jin2021non, ).

To elaborate, we name the above function class asymmetric generalized-smooth as the definition in (2) takes an asymmetric form. In particular, the smoothness parameter of the functions in $\mathcal{L}_{\text{asym}}^{*}$ scales with the gradient norm $\|\nabla f(w^{\prime})\|$. This implies that the nonconvex problem can be ill-conditioned in the initial optimization stage when the gradient is relatively large.

On the other hand, (zhang2019gradient, ) showed that high-order polynomials and many language models belong to the following Hessian-based generalized-smooth function class $\mathbf{\mathcal{L}}_{\text{H}}^{*}$.

In addition to the above notions of generalized-smoothness, many other works have developed optimization algorithms for minimizing the class of higher-order smooth functions, i.e., functions with Lipschitz continuous higher-order gradients (Nesterov2006, ; carmon2020lower, ; carmon2021lower, ). However, the resulting algorithms usually require either computing higher-order gradients or solving higher-order subproblems, which are not suitable for machine learning applications with big data. In the following subsection, we propose a so-called $\alpha$-symmetric generalized-smooth function class, which we show substantially generalizes the existing generalized-smooth function classes and covers a wide range of functions used in many important machine learning applications.

The α𝛼\alpha-Symmetric Generalized-Smooth Function Class

We propose the following class of $\alpha$-symmetric generalized-smooth functions $\mathbf{\mathcal{L}}_{\text{sym}}^{*}(\alpha)$, which we show later covers the aforementioned generalized-smooth function classes and includes many important machine learning problems. Throughout the whole paper, we define $0^{0}=1$.

where $w_{\theta}(w,w^{\prime}):=\theta w^{\prime}+(1-\theta)w$.

Remark: we use $w_{\theta}(w,w^{\prime})$ to emphasize its dependence on $w,w^{\prime}$. Later whenever $w,w^{\prime}$ is given, we will use the abbreviation $w_{\theta}$.

It can be seen that the above function class $\mathbf{\mathcal{L}}_{\text{sym}}^{*}(\alpha)$ covers the aforementioned function classes $\mathcal{L}$ (corresponds to $L_{1}=0$) and $\mathbf{\mathcal{L}}_{\text{asym}}^{*}$ (with $L_{1}>0,\alpha=1$ and $\max_{\theta\in}\|\nabla f(w_{\theta}(w,w^{\prime}))\|$ being replaced with the smaller term $\|\nabla f(w)\|$). In particular, compared to the asymmetric generalized-smooth function class $\mathbf{\mathcal{L}}_{\text{asym}}^{*}$, our proposed function class $\mathbf{\mathcal{L}}_{\text{sym}}^{*}(\alpha)$ generalizes it in two aspects. First, $\mathbf{\mathcal{L}}_{\text{sym}}^{*}(\alpha)$ defines generalized-smoothness in a symmetric way with regard to the points $w$ and $w^{\prime}$ since it considers the maximum gradient norm over the line segment $\{w_{\theta}:\theta\in\}$. As a comparison, $\mathbf{\mathcal{L}}_{\text{asym}}^{*}$ defines generalized-smoothness in an asymmetric way. Second, $\mathbf{\mathcal{L}}_{\text{sym}}^{*}(\alpha)$ covers the functions whose smoothness parameter can scale polynomially as $\max_{\theta\in}\|\nabla f(w_{\theta})\|^{\alpha}$, whereas $\mathbf{\mathcal{L}}_{\text{asym}}^{*}$ only considers the special case $\alpha=1$.

Next, we show connections among all these generalized-smooth function classes, and prove that our proposed function class $\mathbf{\mathcal{L}}_{\text{sym}}^{*}(\alpha)$ is substantially bigger than others.

The generalized-smooth function classes $\mathbf{\mathcal{L}}_{\text{asym}}^{*}$, $\mathbf{\mathcal{L}}_{\textsc{H}}^{*}$ and $\mathbf{\mathcal{L}}_{\text{sym}}^{*}(\alpha)$ satisfy the following properties.

$\mathcal{L}_{\text{asym}}^{*}\subset\mathcal{L}_{\text{sym}}^{*}(1)$;

$\mathbf{\mathcal{L}}_{\textsc{H}}^{*}\subset\mathbf{\mathcal{L}}_{\text{sym}}^{*}(1)$. Moreover, they are equivalent when restricted to the set of twice-differentiable functions;

To elaborate, items 1 & 2 show that a special case of our proposed $\alpha$-symmetric generalized-smooth function class $\mathcal{L}_{\text{sym}}^{*}(1)$ includes the other existing generalized-smooth function classes $\mathcal{L}_{\text{asym}}^{*},\mathcal{L}_{\text{H}}^{*}$. In particular, when $f$ is restricted to be twice-differentiable, the class $\mathcal{L}_{\text{H}}^{*}$ is equivalent to $\mathcal{L}_{\text{sym}}^{*}(1)$. Moreover, items 3 & 4 show that our proposed generalized-smooth function class $\mathcal{L}_{\text{sym}}^{*}(\alpha)$ includes a wide range of ‘fast-growing’ functions, including high-order polynomials and even exponential functions, which are not included in $\mathcal{L}_{\text{asym}}^{*}$. In summary, our proposed $\alpha$-symmetric generalized-smooth function class $\mathcal{L}_{\text{sym}}^{*}(\alpha)$ extends the existing boundary of smooth functions in nonconvex optimization.

Next, for the functions in $\mathcal{L}_{\text{sym}}^{*}(\alpha)$, we establish various important technical tools that are leveraged later to develop efficient algorithms and their convergence analysis.

The function class $\mathcal{L}_{\text{sym}}^{*}(\alpha)$ can be equivalently defined as follows.

where K_{0}:=L_{0}\big{(}2^{\frac{\alpha^{2}}{1-\alpha}}+1\big{)}, $K_{1}:=L_{1}\cdot 2^{\frac{\alpha^{2}}{1-\alpha}}\cdot 3^{\alpha}$, $K_{2}:=L_{1}^{\frac{1}{1-\alpha}}\cdot 2^{\frac{\alpha^{2}}{1-\alpha}}\cdot 3^{\alpha}(1-\alpha)^{\frac{\alpha}{1-\alpha}}$.

Consequently, the following descent lemmas hold.

Please refer to (25) in Lemma A.1 in Appendix A for the details. To prove this, we uniformly divide the line segment between $w$ and $w^{\prime}$ into $n$ pieces with the end points $\{w_{\theta}:\theta=\frac{k}{n}\}_{k=0}^{n}$. Then, we obtain the following bound.

where $w_{k/n}$ and $w_{(k+1)/n}$ denote $w_{\theta}$ with $\theta=k/n$ and $\theta=(k+1)/n$ respectively, and $h(\theta):=L_{0}+L_{1}\|\nabla f(w_{\theta})\|^{\alpha}$. As $n\to+\infty$, the summation in the above inequality converges to the desired integral $\int_{0}^{1}h(\theta)d\theta$. Second, to prove sufficiency, i.e., (9) implies (5) & (6), we derive and solve an ordinary differential equation (ODE) of the function $H(\theta):=\int_{0}^{\theta}h(\theta^{\prime})d\theta^{\prime}$. This ODE is obtained by substituting $w^{\prime}=w_{\theta}$ into the above equivalent definition (9). Then, to prove necessity, i.e., (5) & (6) imply (9), we use a similar dividing technique so that averaging the terms $K_{0}+K_{1}\|\nabla f(w_{k/n})\|^{\alpha}$ and $L_{0}+L_{1}\|\nabla f(w_{k/n})\|$ over $k=0,1,\ldots,n-1$ yields the desired integral as $n\to+\infty$, while at the same time the other terms vanish as $\|w_{(k+1)/n}-w_{k/n}\|^{\frac{\alpha}{1-\alpha}}\to 0$ and \exp\big{(}L_{1}\|w_{(k+1)/n}-w_{k/n}\|\big{)}\to 1.

Next, we present some nonconvex machine learning examples that belong to the proposed function class $\mathcal{L}_{\text{sym}}^{*}(\alpha)$.

The above nonconvex objective function is a high-order polynomial in the high-dimensional space. Therefore, it does not belong to the $L$-smooth function class $\mathcal{L}$. In the following result, we formally prove that the above phase retrieval problem can be effectively modeled by our proposed function class $\mathcal{L}_{\text{sym}}^{*}(\alpha)$.

The nonconvex phase retrieval objective function $f(z)$ in (10) belongs to $\mathcal{L}_{\text{sym}}^{*}(\frac{2}{3})$.

Example 2: Distributionally Robust Optimization. In many practical machine learning applications, there is usually a gap between training data distribution and test data distribution. Therefore, it is much desired to train a model that is robust to distribution shift. Distributionally robust optimization (DRO) is such a popular optimization framework for training robust models. Specifically, DRO aims to solve the following problem

where $\psi^{*}$ denotes the convex conjugate function of $\psi$. In particular, the objective function $L(x,\eta)$ in the above equivalent form has been shown to belong to the function class $\mathcal{L}_{\text{asym}}^{*}$ (jin2021non, ). Therefore, by item 1 of Theorem 1, we can make the following conclusion.

Regarding the equivalent form (12) of the DRO problem (11), its objective function $L$ belongs to the function class $\mathcal{L}_{\text{sym}}^{*}(1)$.

In this section, we develop an efficient and optimal deterministic gradient-based algorithm for minimizing nonconvex functions in $\mathcal{L}_{\text{sym}}^{*}(\alpha)$ and analyze its iteration complexity.

The challenge for optimizing the functions in $\mathcal{L}_{\text{sym}}^{*}(\alpha)$ is that the generalized-smoothness parameter scales with $\max_{\theta\in}\|\nabla f(w_{\theta})\|^{\alpha}$. To address this issue, we need to use a specialized gradient normalization technique, and this motivates us to consider the $\beta$-normalized gradient descent ($\beta$-GD) algorithm as shown in Algorithm 1. To elaborate, $\beta$-GD simply normalizes the gradient update by the gradient norm term $\|\nabla f(w_{t})\|^{\beta}$ for some $\beta\geq 0$. Such a normalized update is closely related to some existing gradient-type algorithms, including the clipped GD algorithm that uses the normalization term $\max\{\|\nabla f(w_{t})\|,C\}$ and the normalized GD that uses the normalization term $\|\nabla f(w_{t})\|+C$ (zhang2019gradient, ), where $C>0$ is a certain constant.

We obtain the following convergence result of $\beta$-GD on minimizing functions in $\mathcal{L}_{\text{sym}}^{*}(\alpha)$.

Apply the $\beta$-GD algorithm to minimize any function $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$ with $\beta\in[\alpha,1]$. Choose $\gamma=\frac{\epsilon^{\beta}}{12(K_{0}+K_{1}+2K_{2})+1}$See the definition of $K_{0},K_{1},K_{2}$ in Proposition 3.2. if $\alpha\in(0,1)$ and $\gamma=\frac{\epsilon^{\beta}}{4L_{0}+1}$ if $\alpha=1$ ($\epsilon$ is the target accuracy). Then, the following convergence rate result holds.

Theorem 2 shows that $\beta$-GD achieves the iteration complexity $\mathcal{O}(\epsilon^{-2})$ when minimizing functions in $\mathcal{L}_{\text{sym}}^{*}(\alpha)$. Such a complexity result matches the iteration complexity lower bound for deterministic smooth nonconvex optimization and hence is optimal. In particular, Theorem 2 shows that to minimize any function $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$, it suffices to apply $\beta$-GD with any $\beta\in[\alpha,1]$ and a proper learning rate $\gamma=\mathcal{O}(\epsilon^{\beta})$. Intuitively, with a larger $\alpha$, the gradient norm of function $f$ in the class $\mathcal{L}_{\text{sym}}^{*}(\alpha)$ increases faster as $\|w\|\to+\infty$, and therefore we need to use a larger normalization parameter $\beta$ and a smaller learning rate $\mathcal{O}(\epsilon^{\beta})$ to alleviate gradient explosion. Interestingly, the convergence and iteration complexity of $\beta$-GD remain the same as long as $\beta\geq\alpha$ is used, i.e., over-normalization does not affect the complexity order. In practice, when $\alpha$ is unknown a priori for the function class $\mathcal{L}_{\text{sym}}^{*}(\alpha)$, one can simply use the conservative choice $\beta=1$ and is guaranteed to converge.

Technical Novelty. In the proof of Theorem 2, a major challenge is that due to the $\beta$-normalization term in Algorithm 1, the generalized-smoothness of functions in the class $\mathcal{L}_{\text{sym}}^{*}(\alpha)$ introduces additional higher-order terms to the Taylor expansion upper bounds, as can be seen from the descent lemmas shown in (7) (for $\alpha\in(0,1)$) and (8) (for $\alpha=1$). In the convergence proof, these terms contribute to certain fast-increasing terms that reduce the overall optimization progress. For example, when $\alpha\in(0,1)$, substituting $w=w_{t}$ and $w^{\prime}=w_{t+1}$ into (7) yields that See (i) of (E) in Appendix E for the full expression of $\mathcal{O}$ in eq. (14).

The above key inequality bounds the optimization progress $f(w_{t+1})-f(w_{t})$ using gradient norm terms with very different exponents. This makes it challenging to achieve the desired level of optimization progress, as compared with the analysis of minimizing other (generalized) smooth functions in $\mathcal{L}$, $\mathcal{L}_{\text{asym}}^{*}$ and $\mathcal{L}_{\text{H}}^{*}$ (zhang2019gradient, ; jin2021non, ). To address this issue and homogenize the diverse exponents, we develop a technical tool in Lemma E.1 in Appendix A to bridge polynomials with different exponents. With this technique, we further obtain the following optimization progress bound

which leads to the desired result with proper telescoping.

We also obtain the following complementary result to Theorem 2, which shows that $\beta$-GD may diverge in general with under-normalization.

(Divergence of $\beta$-GD) For the $\beta$-GD algorithm with $\beta\in[0,\alpha)$, there always exists a convex function $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$ with a unique minimizer such that for any learning rate $\gamma>0$, $\beta$-GD diverges for all initialization $\|w_{0}\|>C$ for some constant $C>0$.

Expected α𝛼\alpha-Symmetric Generalized-Smooth Functions in Stochastic Optimization

In this section, we propose a class of expected $\alpha$-symmetric generalized-smooth functions and study their properties in stochastic optimization. Specifically, we consider the following nonconvex stochastic optimization problem

where $w_{\theta}:=\theta w^{\prime}+(1-\theta)w$.

Under Assumption 1, the following statements hold.

where $\overline{K}_{0}=2^{\frac{2-\alpha}{1-\alpha}}L_{0}$, $\overline{K}_{1}=2^{\frac{2-\alpha}{1-\alpha}}L_{1}$, $\overline{K}_{2}=(5L_{1})^{\frac{1}{1-\alpha}}$;

We first compare deterministic algorithms with fine-tuned learning rate $\gamma$ over 500 iterations. This includes the basic GD with $\gamma=8\times 10^{-4}$, clipped GD (zhang2019gradient, ) with $\gamma=0.9$ and normalization term $\max(\|\nabla f(x_{t})\|,100)$, and our $\beta$-GD with $\beta=\frac{1}{3},\frac{2}{3},1$ and $\gamma=0.03,0.1,0.2$, respectively. Figure 1 (top left) plots the comparison result on objective function value v.s. iteration. It can be seen that our proposed $\beta$-GD with $\beta=\frac{1}{3},\frac{2}{3}$ converges faster than the existing GD, normalized GD ($1$-GD) and clipped GD algorithms, which shows the advantage of using a proper normalization parameter $\beta$.

We further compare stochastic algorithms with fine-tuned learning rate $\gamma$ and fixed batch size $b=50$ over 500 iterations. This includes the basic SGD with $\gamma=2\times 10^{-4}$, normalized SGD with $\gamma=2\times 10^{-3}$, normalized SGD with momentum (jin2021non, ) with $\gamma=3\times 10^{-3}$ and momentum coefficient $10^{-4}$, clipped SGD (zhang2019gradient, ) with $\gamma=0.3$ and normalization term $\max(\|\nabla f(z_{t})\|,10^{3})$, and SPIDER with $\gamma=0.01$, epoch size $q=5$ and batchsizes $B=3000,B^{\prime}=50$. We generate the initialization by running $\frac{2}{3}$-GD with $\gamma=0.1$ for 100 iterations from $z_{0}$. Figure 1 (top right) plots the comparison result on objective function value v.s. sample complexity. It can be seen that SPIDER uses slightly more samples at the beginning but converges to a much better solution than the other SGD-type algorithms. This demonstrates the advantage of applying both variance reduction and proper normalization to solve generalized-smooth nonconvex stochastic problems.

2 Application to DRO

We further compare stochastic algorithms with fine-tuned learning rate $\gamma$ and fixed minibatch size $b=50$ over 5000 iterations. This includes the basic SGD with $\gamma=2\times 10^{-4}$, normalized SGD with $\gamma=8\times 10^{-3}$, normalized SGD with momentum with $\gamma=8\times 10^{-3}$ and momentum coefficient $10^{-4}$, clipped SGD with $\gamma=0.05$ and normalization term $\max(\|\nabla L(x_{t},\eta_{t})\|,100)$, and SPIDER with $\gamma=4\times 10^{-3}$, epoch size $q=20$ and batchsizes $B=2000,B^{\prime}=50$. We generate the initialization by running normalized GD with $\gamma=0.2$ for 30 iterations from $w_{0},\eta_{0}$. Figure 1 (bottom right) plots the comparison result on objective function value $\Psi(x_{t})$ v.s. sample complexity. It can be seen that SPIDER takes slightly more samples at the beginning but converges to a better solution than the other SGD-type algorithms. This demonstrates the advantage of applying both variance reduction and proper normalization to solve generalized-smooth nonconvex stochastic problems.

Conclusion

In this work, we proposed a new class of generalized-smooth functions that extends the existing ones. We developed both deterministic and stochastic gradient-based algorithms for solving problems in this class and obtained the optimal complexities. Our results extend the existing boundary of first-order nonconvex optimization and may inspire new developments in this direction. In the future, it is interesting to explore if other popular variance reduction algorithms such as STORM and SpiderBoost can be normalized to solve generalized-smooth nonconvex stochastic problems.

Acknowledgement

The work of Ziyi and Yi Zhou was supported in part by U.S. National Science Foundation under the grants CCF-2106216, DMS-2134223 and CAREER-2237830.

The work of Yingbin was supported in part by the U.S. National Science Foundation under the grants CCF-1900145 and CCF-1909291.

The work of Zhaosong was supported in part by U.S. National Science Foundation under the grant IIS-2211491.

References

Part Appendix

where $w_{\theta}:=\theta w^{\prime}+(1-\theta)w$.

Lemma A.1 provides an equivalent definition of $f\in\mathcal{L}_{\text{asym}}^{*}(1)$ which is sometimes more convenient to use than Definition 3.1, for example, in the proof in Section B.2.

Eq. (25) directly implies eq. (4) (i.e., $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$) since

where (i) uses eq. (4) with $w,w^{\prime}$ replaced by $w_{k/n},w_{(k+1)/n}$ respectively ($w_{k/n}$ and $w_{(k+1)/n}$ denote $w_{\theta}$ with $\theta=k/n$ and $\theta=(k+1)/n$ respectively) and (ii) denotes $h(\theta):=L_{0}+L_{1}\|\nabla f(w_{\theta})\|^{\alpha}$. Since $h(\cdot)$ is continuous, letting $n\to+\infty$ in the above inequality proves eq. (25) as follows.

where $w_{\theta}:=\theta w^{\prime}+(1-\theta)w$.

It sufficies to prove the equivalence between eqs. (26) & (19).

where (i) applies Jensen’ inequality to the convex function $\|\cdot\|^{2}$, (ii) uses eq. (19), and (iii) denotes h(u):=\big{(}L_{0}+L_{1}\|\nabla f_{\xi}(w_{\theta u})\|^{\alpha}\big{)}^{2}. Since $h$ is a continuous function, letting $n\to+\infty$ in the above inequality yields that

Substituting $\theta=1$ into the above inequality proves eq. (26). ∎

Under Assumption 1, the stochastic gradient $\nabla f_{\xi}(w)$ and true gradient $\nabla f(w)$ satisfy the following inequalities for any $\tau\in$,

First, when $\tau=2$, Assumption 1 implies eq. (28) as follows.

where (i) applies Jensen’s inequality to the concave function $g(s)=s^{\tau/2}$, (ii) uses eq. (29), and (iii) uses the inequality that $(a+b)^{\tau/2}\leq a^{\tau/2}+b^{\tau/2}$ for any $a,b\geq 0$ and $\tau/2\in$. ∎

Note that the only randomness of Algorithm 2 comes from $S_{t}$, so we can consider the filtration $\mathcal{F}(S_{1:t}):=\mathcal{F}(S_{1},\ldots,S_{t})$ which monotonically increases with larger $t$. Then, it can be easily seen from Algorithm 2 that

Appendix B Proof of Theorem 1

B.2 Proof of Item 2

Note that if a function is not twice-differentiable, it cannot belong to $\mathcal{L}_{\text{H}}^{*}$ but may still belong to $\mathcal{L}_{\text{sym}}^{*}(1)$. For example, for the function $f(w)=w|w|$ whose derivative $f^{\prime}(w)=2|w|$ is not differentiable (so $f\notin\mathcal{L}_{\text{H}}^{*}$), we have $f\in\mathcal{L}\subset\mathcal{L}_{\text{sym}}^{*}(1)$ since |f^{\prime}(w^{\prime})-f^{\prime}(w)|\leq 2\big{|}|w^{\prime}|-|w|\big{|}\leq 2|w^{\prime}-w|.

Therefore, it remains to prove for twice-differentiable functions $f$ the equivalence between eq. (31) below (definition of $\mathcal{L}_{\text{H}}^{*}$) and eq. (25) with $\alpha=1$ (equivalent definition of $\mathcal{L}_{\text{sym}}^{*}(1)$).

Eq. (31) implies eq. (25) as proved below.

where (i) uses eq. (31). Finally, it remains prove eq. (31) given eq. (25).

Note that of the symmetric Hessian matrix $\nabla^{2}f(w)$ has eigenvalue $\|\nabla^{2}f(w)\|$ or $-\|\nabla^{2}f(w)\|$. Denote $s$ as the corresponding eigenvector with $\|s\|=1$, i.e., $\nabla^{2}f(w)s=\pm\|\nabla^{2}f(w)\|s$. In eq. (25) , we adopt $w^{\prime}:=w+\theta^{\prime}s$ ($\theta^{\prime}\in(0,1)$), so $w_{\theta}:=\theta w^{\prime}+(1-\theta)w=\theta(w+\theta^{\prime}s)+(1-\theta)w=w+\theta\theta^{\prime}s$ and thus eq. (25) becomes

The left side of eq. (32) can be rewritten as follows.

where (i) uses change of variables $u=\theta^{\prime}\theta$. The right side of eq. (32) can be rewritten as follows.

where (i) also uses change of variables $u=\theta^{\prime}\theta$. Substituting eqs. (33) & (34) into eq. (32) and multiplying both sides by $1/\theta^{\prime}>0$, we obtain that

Letting $\theta^{\prime}\to+0$ in the above inequality, we obtain eq. (31) as follows.

B.3 Proof of Item 3

where $w_{\theta}:=\theta w^{\prime}+(1-\theta)w$. This verifies eq. (4) and thus proves that $f\in\mathcal{L}_{\text{sym}}(\alpha)$.

As $|w|\to+\infty$, the left side of the above inequality is $\mathcal{O}(|w|^{\frac{1}{1-\alpha}})$ whereas the right side has strictly smaller order $\mathcal{O}(|w|^{\frac{1-\alpha+\widetilde{\alpha}}{1-\alpha}})$. Hence, the above inequality cannot hold for sufficiently large $|w|$, which means the assumption that $f\in\mathcal{L}_{\text{sym}}^{*}(\widetilde{\alpha})$ does not hold.

which implies that |w^{\prime}|\leq\big{(}\frac{L_{0}(1-\alpha)}{2-\alpha}\big{)}^{\frac{1-\alpha}{\alpha}}<+\infty. Hence, the above inequality cannot for all sufficiently large $|w^{\prime}|$, which means the assumption that $f\in\mathcal{L}_{\text{asym}}^{*}$ does not hold.

B.4 Proof of Item 4

When $|w|\leq 1$, $|f^{\prime\prime}(w)|\leq e+e^{-1}<4$; When $|w|>1$, $|f^{\prime}(w)|+4=e^{|w|}+e^{-|w|}-2e^{-|w|}+4>|f^{\prime\prime}(w)|-2e^{-1}+4>|f^{\prime\prime}(w)|$. Combining the two cases yields that $|f^{\prime\prime}(w)|<|f^{\prime}(w)|+4$, which implies that $f\in\mathcal{L}_{\text{sym}}^{*}$. Since $f$ is twice-differentiable, we have $f\in\mathcal{L}_{\text{sym}}^{*}(1)$ based on item 2 of Theorem 1.

where $w_{\theta}:=\theta w^{\prime}+(1-\theta)w$. Substituting $w^{\prime}=0$ into the above inequality, we obtain the following inequality.

As $|w|\to+\infty$, the left side of the above inequality goes to $+\infty$ while the right sides converges to $L_{1}<+\infty$. Hence, the above inequality cannot hold for sufficiently large $|w|$, which means the assumption that $f\in\mathcal{L}_{\text{sym}}^{*}(\widetilde{\alpha})$ does not hold.

As $|w|\to+\infty$, the left side of the above inequality goes to $+\infty$, so the above inequality cannot for all sufficiently large $|w^{\prime}|$, which means the assumption that $f\in\mathcal{L}_{\text{asym}}^{*}$ does not hold.

Appendix C Proof of Proposition 3.2

where (i) denotes $H(\theta^{\prime}):=L_{0}\theta^{\prime}+L_{1}\int_{0}^{1}\|\nabla f(w_{\theta^{\prime}\theta})\|^{\alpha}\theta^{\prime}d\theta=L_{0}\theta^{\prime}+L_{1}\int_{0}^{\theta^{\prime}}\|\nabla f(w_{u})\|^{\alpha}du$. Then its derivative $H^{\prime}(\theta)$ can be bounded as follows,

where (i) uses eq. (36) and (ii) applies Jensen’s inequality to the concave function $g(x)=x^{\alpha}$. Rearranging the above inequality yields that

Integrating the above inequality over $\theta^{\prime}\in[0,\theta]$ yields that

where (i) uses $H(0)=0$ and applies Jensen’s inequality to the concave function $g(x)=x^{1-\alpha}$. Therefore,

Substituting the above inequality into eq. (36), we obtain that

Then, substituting the above inequality into eq. (4), we obtain that

where (i) uses the inequality that $(a+b+c)^{\alpha}\leq a^{\alpha}+b^{\alpha}+c^{\alpha}$ for any $a,b,c\geq 0$ and $\alpha\in$, and (ii) denotes that K_{0}:=L_{0}\big{(}2^{\frac{\alpha^{2}}{1-\alpha}}+1\big{)}, $K_{1}:=L_{1}\cdot 2^{\frac{\alpha^{2}}{1-\alpha}}\cdot 3^{\alpha}$, $K_{2}:=L_{1}^{\frac{1}{1-\alpha}}\cdot 2^{\frac{\alpha^{2}}{1-\alpha}}\cdot 3^{\alpha}(1-\alpha)^{\frac{\alpha}{1-\alpha}}$.

where (i) denotes $w_{\theta}:=\theta w^{\prime}+(1-\theta)w$, (ii) uses eq. (5) with $w,w^{\prime}$ replaced by $w_{k/n},w_{(k+1)/n}$ respectively and (iii) denotes $h(\theta):=K_{0}+K_{1}\|\nabla f(w_{\theta})\|^{\alpha}$. Since $h(\cdot)$ is continuous, letting $n\to+\infty$ in the above inequality proves eq. (25) as follows, which implies $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$ by Lemma A.1.

C.2 Proof of Item 2

Note that eq. (37) holds for any function $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$ with $\alpha\in$. Substituting $\alpha=1$ into eq. (37), we obtain that

where $H(\theta^{\prime}):=L_{0}\theta^{\prime}+L_{1}\int_{0}^{\theta^{\prime}}\|\nabla f(w_{u})\|du$. Rearranging the above inequality yields that

Integrating the above inequality over $\theta^{\prime}\in[0,\theta]$ yields that (note that $H(0)=0$)

Substituting the above inequality and $\alpha=1$ into eq. (36), we obtain that

Then, substituting the above inequality and $\alpha=1$ into eq. (4), we prove eq. (6) as follows.

where (i) denotes $w_{\theta}:=\theta w^{\prime}+(1-\theta)w$, (ii) uses eq. (6) with $w,w^{\prime}$ replaced by $w_{k/n},w_{(k+1)/n}$ respectively and (iii) denotes $h(\theta):=L_{0}+L_{1}\|\nabla f(w_{\theta})\|$. Since $h(\cdot)$ is continuous, letting $n\to+\infty$ in the above inequality proves eq. (25) with $\alpha=1$ as follows, which implies $f\in\mathcal{L}_{\text{sym}}^{*}(1)$ by Lemma A.1.

C.3 Proof of Item 3

where (i) uses eq. (5) with $w^{\prime}$ replaced by $w_{\theta}:=\theta w^{\prime}+(1-\theta)w$.

C.4 Proof of Item 4

where (i) uses eq. (6) with $w^{\prime}$ replaced by $w_{\theta}:=\theta w^{\prime}+(1-\theta)w$.

Appendix D Proof of Proposition 3.3 and Proposition 5.2

where (i) uses trianagular inequality, $\|a_{\xi}a_{\xi}^{\top}\|=\|a_{\xi}\|^{2}$, $|y_{\xi}|\leq 1$ and the following inequality, (ii) uses $(|a_{\xi}^{\top}z^{\prime}|+|a_{\xi}^{\top}z|)^{2}\leq 2|a_{\xi}^{\top}z^{\prime}|^{2}+2|a_{\xi}^{\top}z|^{2}$, (iii) uses eq. (38) and denotes that $y_{\max}:=\max_{1\leq r\leq m}|y_{r}|$ and that $a_{\max}:=\max_{1\leq r\leq m}\|a_{r}\|$.

D.2 Proof for DRO Problem

We adopt the following assumptions from (jin2021non, ):

$\psi$ is a non-negative convex function with $\psi(1)=0$ and $\psi(t)=+\infty$ for all $t<0$, and $\psi^{*}$ is $M$-smooth.

The gradient \nabla L_{\xi}=\big{[}\nabla_{x}L_{\xi};\frac{\partial}{\partial\eta}L_{\xi}\big{]} can be computed as follows.

Therefore, we can prove that $L_{\xi}\in\mathcal{L}_{\text{sym}}^{*}(1)$ as follows.

Appendix E Proof of Theorem 2

We will first prove the following lemma which will be used in the proof of Theorem 2.

For any $x\geq 0$, $C\in$, $\Delta>0$ and $0\leq\omega\leq\omega^{\prime}$ such that $\Delta\geq\omega^{\prime}-\omega$, the following inequality holds

We consider three cases: $\omega=0$, $\omega^{\prime}=\omega>0$ and $\omega^{\prime}>\omega>0$.

(Case I) When $\omega=0$, $\Delta\geq\omega^{\prime}$ and $\Delta>0$ imply that $\frac{\omega^{\prime}}{\Delta}\in$, so $Cx^{\omega}=C\leq C^{\frac{\omega^{\prime}}{\Delta}}$, which implies eq. (44).

(Case II) When $\omega^{\prime}=\omega>0$, $Cx^{\omega}\leq x^{\omega}=x^{\omega^{\prime}}$, which implies eq. (44).

(Case III) When $\omega^{\prime}>\omega>0$, by applying Young’s inequality with $p=\frac{\omega^{\prime}}{\omega}>1$ and $q=\frac{\omega^{\prime}}{\omega^{\prime}-\omega}>1$ which satisfy $\frac{1}{p}+\frac{1}{q}=1$, we prove eq. (44) as follows.

Now we will prove Theorem 2. We omit the well-known case of $\beta=\alpha=0$ where GD is applied to $L$-smooth function $f\in\mathcal{L}$. Hence, we focus on the case of $\beta>0$. We first bound $f(w_{t+1})-f(w_{t})$ in two cases: $\alpha\in(0,1)$ and $\alpha=1$.

(Case I) When $\alpha\in(0,1)$, eq. (7) holds for $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$. Hence, we have

where (i) uses the update rule $w_{t+1}=w_{t}-\gamma\frac{\nabla f(w_{t})}{\|\nabla f(w_{t})\|^{\beta}}$ of Algorithm 1 ($\beta$-GD), (ii) uses $\gamma^{\frac{1}{1-\alpha}}\leq 1$ and applies Lemma E.1 three times respectively with $x=\|\nabla f(w_{t})\|$, $C=3K_{0}\gamma,3K_{1}\gamma,6K_{2}\gamma$ ($C\in$ since $\gamma=\frac{\epsilon^{\beta}}{12(K_{0}+K_{1}+2K_{2})+1}$ and $\epsilon\in(0,1)$), $\Delta=\beta$, $\omega=2-2\beta,2+\alpha-2\beta,\frac{(2-\alpha)(1-\beta)}{1-\alpha}$, $\omega^{\prime}=2-\beta$, (iii) uses the inequality that $a^{\tau}+b^{\tau}+c^{\tau}\leq(a+b+c)^{\tau}$ for $\tau=\frac{2}{\beta}-1>1$ and any $a,b,c\geq 0$, and (iv) uses $\gamma=\frac{\epsilon^{\beta}}{12(K_{0}+K_{1}+2K_{2})+1}$.

(Case II) When $\alpha=1$, we have $\beta=1$ and eq. (8) holds for $f\in\mathcal{L}_{\text{sym}}^{*}(1)$. Hence, we have

where (i) uses the update rule $w_{t+1}=w_{t}-\gamma\frac{\nabla f(w_{t})}{\|\nabla f(w_{t})\|}$ of Algorithm 1 ($\beta$-GD with $\beta=1$) and (ii) and (iii) use $\gamma=\frac{\epsilon}{4L_{0}+1}\leq\frac{1}{2L_{1}}$. Note that eq. (E) holds in both cases. Therefore, by telescoping eq. (E) and rearranging it, we obtain that

where (i) uses $(a+b)^{\tau}\leq a^{\tau}+b^{\tau}$ for $\tau=\frac{1}{2-\beta}\in$ and any $a,b\geq 0$.

Appendix F Proof of Theorem 3

(Case I) When $\alpha\in(0,1)$, consider the convex function $f(w):=|w|^{\frac{2-\alpha}{1-\alpha}}$ with unique minimizer $w=0$ and derivative $f^{\prime}(w)=\frac{2-\alpha}{1-\alpha}|w|^{\frac{1}{1-\alpha}}\text{sgn}(w)$. Based on item 3 of Proposition 1, $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$. Applying $\beta$-GD to this function yields that

Note that $0\leq\beta<\alpha<1$. Hence, if $|w_{t}|>C$ with constant C:=\Big{(}\frac{3(1-\alpha)}{\gamma(2-\alpha)}\Big{)}^{\frac{1-\alpha}{\alpha-\beta}}>0, we have $\gamma\frac{2-\alpha}{1-\alpha}|w_{t}|^{\frac{1-\beta}{1-\alpha}}>3|w_{t}|$ and thus $|w_{t+1}|>2|w_{t}|$. Therefore, if $|w_{0}|>C$, by induction we obtain that $|w_{t}|>2^{t}C$ for any $t$, and thus $|f^{\prime}(w_{t})|>2^{\frac{t}{1-\alpha}}C^{\frac{1}{1-\alpha}}$, $f(w_{t})>2^{\frac{t(2-\alpha)}{1-\alpha}}C^{\frac{2-\alpha}{1-\alpha}}$, which means $\beta$-GD diverges.

(Case II) When $\alpha=1$, consider the convex function $f(w):=e^{w}+e^{-w}$ with unique minimizer $w=0$ and derivative $f^{\prime}(w):=e^{w}-e^{-w}=(e^{|w|}-e^{-|w|})\text{sgn}(w)$. Based on item 4 of Proposition 1, $f\in\mathcal{L}_{\text{sym}}^{*}(1)$. Applying $\beta$-GD to this function yields that

Since $\beta<\alpha=1$, |w_{t}|^{-1}\big{(}e^{|w_{t}|}-e^{-|w_{t}|}\big{)}^{1-\beta}\to+\infty as $|w_{t}|\to+\infty$. Hence, there exists a constant $C>1$ such that \big{(}e^{|w_{t}|}-e^{-|w_{t}|}\big{)}^{1-\beta}>3|w_{t}| for $|w_{t}|>C$. Therefore, $|w_{t+1}|>2|w_{t}|$. Therefore, if $|w_{0}|>C$, by induction we obtain that $|w_{t}|>2^{t}C$ for any $t$, and thus $f(w_{t})>|f^{\prime}(w_{t})|=e^{|w_{t}|}-e^{-|w_{t}|}\geq\frac{1}{2}e^{|w_{t}|}>\frac{1}{2}\exp(2^{t}C)$, which means $\beta$-GD diverges.

Appendix G Proof of Proposition 5.3

Integrating the above inequality over $\theta\in$ yields that

where (i) applies Jensen’s inequality to the concave function $x^{1-\alpha}$. Rearranging the above inequality yields that

Substituting the above inequality into eq. (47), we obtain that

where (i) uses eq. (50) and denotes that $\overline{K}_{0}^{2}:=2^{\frac{4-2\alpha}{1-\alpha}}L_{0}^{2}\geq 2L_{0}^{2}(2^{\frac{1}{1-\alpha}}+1)$, $\overline{K}_{1}^{2}:=2^{\frac{4-2\alpha}{1-\alpha}}L_{1}^{2}\geq 2L_{1}^{2}(2^{\frac{1}{1-\alpha}}+2)$, $\overline{K}_{2}^{2}:=(25L_{1}^{2})^{\frac{1}{1-\alpha}}\geq 4L_{1}^{2}(24L_{1}^{2})^{\frac{\alpha}{1-\alpha}}$, and (ii) uses the inequality that $a^{2}+b^{2}+c^{2}\leq(a+b+c)^{2}$ for any $a,b,c\geq 0$. This proves eq. (20).

where (i) applies Jensen’ inequality to the convex function $\|\cdot\|^{2}$ and (ii) uses eq. (20). For any $\epsilon>0$, there exists $n_{0}>0$ such that $\overline{K}_{2}n^{-\frac{\alpha}{1-\alpha}}\|w^{\prime}-w\|^{\frac{\alpha}{1-\alpha}}<\epsilon$ for any $n\geq n_{0}$. Therefore, taking limit superior of both sides of the above inequality, we obtain that

G.2 Proof of Item 2

Integrating the above inequality over $\theta\in$, we obtain that

Hence, we have $BG(\theta)\leq BG(1)\leq A(e^{3B}-1)$. Substituting this inequality into eq. (47), we obtain that

where (i) uses eq. (53). This proves eq. (21).

where (i) applies Jensen’ inequality to the convex function $\|\cdot\|^{2}$ and (ii) uses eq. (21). For any $\epsilon>0$, there exists $n_{0}>0$ such that $\exp(12n^{-2}L_{1}^{2}\|w^{\prime}-w\|^{2})<1+\epsilon$ for any $n\geq n_{0}$. Therefore, letting $n\to+\infty$ in the above inequality, we obtain that

G.3 Proof of Item 3

(Case I) When $\alpha\in(0,1)$, eq. (20) holds, so we have

where (i) uses Lemma A.3. The above inequality implies that $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$ based on item 1 of Proposition 3.2.

(Case II) When $\alpha=1$, eq. (21) holds, so we have

where (i) uses Lemma A.3, (ii) uses the inequality that $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any $a,b\geq 0$. The above inequality implies that $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$ based on item 2 of Proposition 3.2.

Appendix H Proof of Theorem 4

We will first prove the following lemmas which will be used in the proof of Theorem 4.

Apply SPIDER algorithm (Algorithm 2) to $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$ with stepsize $\gamma\leq\frac{\epsilon}{2\overline{K}_{0}+2\overline{K}_{2}+2\overline{K}_{1}(\Lambda^{\alpha}+\Gamma^{\alpha}+1)+1}$ (when $\alpha\in(0,1)$) or $\gamma\leq\frac{\epsilon}{3L_{1}\sqrt{\Gamma^{2}+1}+3\sqrt{L_{0}^{2}+2L_{1}^{2}\Lambda^{2}}}$ (when $\alpha=1$) ($\epsilon\in(0,1)$ is the target accuracy). Then we have,

Given $S_{1:t}$, $w_{t},w_{t+1}$ are non-random based on eq. (30). Hence, eq. (20) or (21) holds respectively when $\alpha\in(0,1)$ or $\alpha=1$.

If $\alpha\in(0,1)$, eq. (55) can be proved as follows

where (i) uses eq. (20), (ii) uses eq. (28) and $\|w_{t+1}-w_{t}\|=\gamma\leq 1$ based on Algorithm 2, (iii) uses the inequality that $(a+b)^{2}\leq 2a^{2}+2b^{2}$ for any $a,b\geq 0$, (iv) uses \gamma\leq\frac{\epsilon}{2\overline{K}_{0}+2\overline{K}_{2}+2\overline{K}_{1}(\Lambda^{\alpha}+\Gamma^{\alpha}+1)}\leq\frac{\epsilon}{2}\big{(}(\overline{K}_{0}+\overline{K}_{2}+\overline{K}_{1}\Lambda^{\alpha})^{2}+\overline{K}_{1}^{2}(\Gamma^{\alpha}+1)^{2}\big{)}^{-\frac{1}{2}}.

If $\alpha=1$, eq. (55) can be proved as follows

where (i) uses eq. (21), (ii) uses eq. (28) and $\|w_{t+1}-w_{t}\|=\gamma\leq 1$ based on Algorithm 2, (iii) uses \gamma\leq\frac{\epsilon}{3L_{1}\sqrt{\Gamma^{2}+1}+3\sqrt{L_{0}^{2}+2L_{1}^{2}\Lambda^{2}}}\leq\min\big{(}\frac{1}{3L_{1}},\frac{\epsilon}{3L_{1}\sqrt{\Gamma^{2}+1}+3\sqrt{L_{0}^{2}+2L_{1}^{2}\Lambda^{2}}}\big{)}. ∎

Apply SPIDER algorithm (Algorithm 2) to $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$ with stepsize $\gamma$ given by Lemma H.1 batchsize $|S_{t}|=B$ when $t\mod q=0$ and $|S_{t}|=B^{\prime}$ otherwise. Then the approximation error $\delta_{t}:=v_{t}-\nabla f(w_{t})$ has the following properties conditional on minibatches $S_{1:t}:=\{S_{1},\ldots,S_{t}\}$.

where (i) uses eq. (30). Then eq. (58) can be proved as follows.

We prove eq. (60) via backward induction on $s^{\prime}=s,s-1,\ldots,1,0$. Note that eq. (60) holds trivially for $s^{\prime}=s$. Then, assume that eq. (60) holds for a certain value of $s^{\prime}\in[1,s]$ and we prove eq. (60) for $s^{\prime}-1$ as follows.

where (i) uses eq. (60) for $s^{\prime}$, (ii) applies Jensen’s inequality to the concave function $\sqrt{\cdot}$, (iii) uses eq. (58), and (iv) uses the inequality that $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any $a,b\geq 0$. Substituting $s^{\prime}=0$ into eq. (60), we prove eq. (59) as follows.

where (i) uses the inequality that $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any $a,b\geq 0$ and then applies Lyapunov inequality, and (ii) uses eq. (57) and then uses $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ for any $a,b\geq 0$. ∎

Apply SPIDER algorithm (Algorithm 2) to $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$ with batchsize $|S_{t}|=B$ when $t\mod q=0$ and $|S_{t}|=B^{\prime}$ otherwise, and stepsize stepsize $\gamma\leq\frac{\epsilon}{2(\overline{K}_{0}+\overline{K}_{1}+2\overline{K}_{2})+1}$ (when $\alpha\in(0,1)$) or $\gamma\leq\frac{\epsilon}{5L_{1}+8L_{0}}$ (when $\alpha=1$) ($\epsilon\in(0,1)$ is the target accuracy). Then the decrease of the function $f$ has the following bound.

We consider two cases: $\alpha\in(0,1)$ and $\alpha=1$.

(Case I) When $\alpha\in(0,1)$, eq. (7) holds for $f\in\mathcal{L}_{\text{sym}}^{*}(\alpha)$. Hence,

where (i) uses $\|\nabla f(w_{t})\|^{\alpha}\leq\|\nabla f(w_{t})\|^{2}+1$ and $\gamma\leq 1$, (ii) uses Cauchy-Schwartz inequality, $\|v_{t}\|\geq\|\nabla f(w_{t})\|-\|v_{t}-\nabla f(w_{t})\|$ and $\gamma\leq\frac{\epsilon}{2(\overline{K}_{0}+\overline{K}_{1}+2\overline{K}_{2})}$, (iii) uses $\epsilon\leq 1$.

(Case II) When $\alpha=1$, we have $\beta=1$ and eq. (8) holds for $f\in\mathcal{L}_{\text{sym}}^{*}(1)$. Hence,

where (i) uses $\gamma\leq\frac{1}{5L_{1}}$, (ii) uses Cauchy-Schwartz inequality, $\|v_{t}\|\geq\|\nabla f(w_{t})\|-\|v_{t}-\nabla f(w_{t})\|$ and $\gamma\leq\frac{\epsilon}{8L_{0}}$. ∎

Now we will prove Theorem 4. First, it can be easily verified that the choice of stepsize $\gamma$ and batchsize $|S_{t}|$ satisfies the requirements of Lemmas H.2 & H.3. Therefore, eq. (61) in Lemma H.3 holds. Taking expectation of eq. (61) and telescoping over $t=0,1,\ldots,T-1$ where $T=qK$, we obtain that

where (i) uses eq. (59) and (ii) uses the following condition satisfied by the hyperparamter choices $B\geq\max(576\Lambda^{2}\epsilon^{-2},2304\Gamma^{2}q^{2}),B^{\prime}\geq\max(576q,2304q^{2}\epsilon^{2})$.