Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems

Introduction

This paper considers the following minimax optimization problem

In this paper, we focus on a more general case of (1), where $f({\bf{x}},{\bf{y}})$ is $\mu$-strongly-concave in ${\bf{y}}$ but possibly nonconvex in ${\bf{x}}$. This case is referred to as stochastic nonconvex-strongly-concave minimax problems, and it is equivalent to the following problem

Formulation (2) contains several interesting examples in machine learning such as robust optimization and adversarial training .

One insight of SGDA is that the algorithm selects an appropriate ratio of learning rates for ${\bf{x}}$ and ${\bf{y}}$. Concretely, the learning rate for updating ${\bf{y}}$ is ${\mathcal{O}}(\kappa^{2})$ times that of ${\bf{x}}$. Using this idea, it can be shown that the nested loop of SGDmax is unnecessary, and SGDA eliminates the logarithmic term in the complexity result. In addition, Rafique et al. presented some nested-loop algorithms that also achieved ${\mathcal{O}}\left(\kappa^{3}{\varepsilon}^{-4}\right)$ complexity. Recently, Yan et al. proposed Epoch-GDA which considered constraints on both two variables.

Lin et al. proposed a deterministic algorithm called minimax proximal point algorithm (Minimax PPA) to solve nonconvex-strongly-concave minimax problem whose complexity has square root dependence on $\kappa$. Thekumparampil et al. , Barazandeh and Razaviyayn , Ostrovskii et al. also studied the non-convex-concave minimax problems, however, these methods do not cover the stochastic setting in this paper and only work for a special case of problem (2) when the stochastic variable ${\bm{\xi}}$ is finitely sampled from $\{{\bm{\xi}}_{1},\dots,{\bm{\xi}}_{n}\}$ (a.k.a. finite-sum case). That is,

In this paper, we propose a novel algorithm called Stochastic Recursive gradiEnt Descent Ascent (SREDA) for stochastic nonconvex-strongly-concave minimax problems. Unlike SGDmax and SGDA, which only iterate with current stochastic gradients, our SREDA updates the estimator recursively and reduces its variance.

The variance reduction techniques have been widely used in convex and nonconvex minimization problems and convex-concave saddle point problems . However, the nonconvex-strongly-concave minimax problems have two variables ${\bf{x}}$ and ${\bf{y}}$ and their roles in the objective function are quite different. To apply the technique of variance reduction, SREDA employs a concave maximizer with multi-step iteration on ${\bf{y}}$ to simultaneously balance the learning rates, gradient batch sizes and iteration numbers of the two variables. We prove SREDA reduces the number of stochastic gradient evaluations to ${\mathcal{O}}(\kappa^{3}{\varepsilon}^{-3})$, which is the best known upper bound complexity. The result gives optimal dependency on ${\varepsilon}$ since the lower bound of stochastic first order algorithms for general nonconvex optimization is ${\mathcal{O}}({\varepsilon}^{-3})$ . For finite-sum cases, the gradient cost of SREDA is ${\mathcal{O}}\left(n\log(\kappa/{\varepsilon})+\kappa^{2}n^{1/2}{\varepsilon}^{-2}\right)$ when $n\geq\kappa^{2}$, and ${\mathcal{O}}\left((\kappa^{2}+\kappa n){\varepsilon}^{-2}\right)$ when $n\leq\kappa^{2}$. This result is sharper than Minimax PPA in the case of $n$ is larger than $\kappa^{2}$. We summarize the comparison of all algorithms in Table 1.

The paper is organized as follows. In Section 2, we present notations and preliminaries. In Section 3, we review the existing work for stochastic nonconvex-strongly-concave optimization and related techniques. In Section 4, we present the SREDA algorithm and the main theoretical result. In Section 5, we give a brief overview of our convergence analysis. In Section 6, we demonstrate the effectiveness of our methods on robust optimization problem. We conclude this work in Section 7.

Notation and Preliminaries

We first introduce the notations and preliminaries used in this paper. For a differentiable function $f({\bf{x}},{\bf{y}})$, we denote the partial gradient of $f$ with respect to ${\bf{x}}$ and ${\bf{y}}$ at $({\bf{x}},{\bf{y}})$ as $\nabla_{\bf{x}}f({\bf{x}},{\bf{y}})$ and $\nabla_{\bf{y}}f({\bf{x}},{\bf{y}})$ respectively. We use $\left\|\cdot\right\|_{2}$ to denote the Euclidean norm of vectors. For a finite set ${\mathcal{S}}$, we denote its cardinality as $|{\mathcal{S}}|$. We assume that the minimax problem (2) satisfies the following assumptions.

The component function $F$ is concave in ${\bf{y}}$. That is, for any ${\bf{x}}$, ${\bf{y}}$, ${\bf{y}}^{\prime}$ and random vector ${\bm{\xi}}$, we have $F({\bf{x}},{\bf{y}};{\bm{\xi}})\leq F({\bf{x}},{\bf{y}}^{\prime};{\bm{\xi}})+\langle\nabla_{\bf{y}}F({\bf{x}},{\bf{y}}^{\prime};{\bm{\xi}}),{\bf{y}}-{\bf{y}}^{\prime}\rangle$.

The function $f({\bf{x}},{\bf{y}})$ is $\mu$-strongly-concave in ${\bf{y}}$. That is, there exists a constant $\mu>0$ such that for any ${\bf{x}}$, ${\bf{y}}$ and ${\bf{y}}^{\prime}$, we have $f({\bf{x}},{\bf{y}})\leq f({\bf{x}},{\bf{y}}^{\prime})+\langle\nabla_{\bf{y}}f({\bf{x}},{\bf{y}}^{\prime}),{\bf{y}}-{\bf{y}}^{\prime}\rangle-\frac{\mu}{2}\left\|{\bf{y}}-{\bf{y}}^{\prime}\right\|_{2}^{2}$.

Under the assumptions of Lipschitz-gradient and strongly-concavity on $f$, we can show that $\Phi(\cdot)$ also has Lipschitz-gradient.

Since $\Phi$ is differentiable, we may define ${\varepsilon}$-stationary point based on its gradient. The goal of this paper is to establish a stochastic gradient algorithm that output an ${\mathcal{O}}({\varepsilon})$-stationary point in expectation.

We call ${\bf{x}}$ an ${\mathcal{O}}({\varepsilon})$-stationary point of $\Phi$ if $\left\|\nabla\Phi({\bf{x}})\right\|_{2}\leq{\mathcal{O}}({\varepsilon})$.

We also need the notations of projection and gradient mapping to address the constraint on ${\mathcal{Y}}$.

We define the projection of ${\bf{y}}$ on to convex set ${\mathcal{Y}}$ by $\Pi_{\mathcal{Y}}({\bf{y}})=\operatorname*{arg\,min}_{{\bf{z}}\in{\mathcal{Y}}}\left\|{\bf{z}}-{\bf{y}}\right\|_{2}$.

We define the gradient mapping of $f$ at $({\bf{x}}^{\prime},{\bf{y}}^{\prime})$ with respect to ${\bf{y}}$ as follows

Related Work

In this section, we review recent works for solving stochastic nonconvex-strongly-convex minimax problem (2) and introduce variance reduction techniques in stochastic optimization.

2 Variance Reduction Techniques

Variance reduction techniques has been widely used in stochastic optimization . One scheme of this type of methods is StochAstic Recursive grAdient algoritHm (SARAH) . Nguyen et al. first proposed it for convex minimization and established a convergence result. For nonconvex optimization, a closely related method is Stochastic Path-Integrated Differential EstimatoR (SPIDER) . The algorithm estimates the gradient recursively together with a normalization rule, which guarantees the approximation error of the gradient is ${\mathcal{O}}({\varepsilon}^{2})$ at each step. As a result, it can find ${\mathcal{O}}({\varepsilon})$-stationary point of the nonconvex objective in ${\mathcal{O}}({\varepsilon}^{-3})$ complexity, which matches the lower bound . This idea can also be extended to nonsmooth cases .

It is also possible to employ variance reduction to solve minimax problems. Most of the existing works focused on the convex-concave case. For example, Palaniappan and Bach , Chavdarova et al. , extend SVRG and SAGA to solving strongly-convex-strongly-concave minimax problem in the finite-sum case, and established a linear convergence. One may also use the Catalyst framework and proximal point iteration to further accelerate when the problem is ill-conditioned. Du et al. , Du and Hu pointed out that for some special cases, the strongly-convex and strongly-concave assumptions of linear convergence for minimax problem may not be necessary. Additionally, Zhang and Xiao solved multi-level composite optimization problems by variance reduction, but the oracles in their algorithms are different from our settings.

Algorithms and Main Results

In this section, we propose a novel algorithm for solving problem (2), which we call Stochastic Recursive gradiEnt Descent Ascent (SREDA). We show that the algorithm finds an ${\mathcal{O}}({\varepsilon})$-stationary point with a complexity of ${\mathcal{O}}(\kappa^{3}{\varepsilon}^{-3})$ stochastic gradient evaluations, and this result may be extended to the finite-sum case (3).

SREDA uses variance reduction to track the gradient estimator recursively. Because there are two variables ${\bf{x}}$ and ${\bf{y}}$ in our problem (2), it is not efficient to combine SGDA with SPIDER or (inexact) SARAH directly. The algorithm should approximate the gradient of $f({\bf{x}}_{k},{\bf{y}}_{k})$ with small error, and keep the value of $f({\bf{x}}_{k},{\bf{y}}_{k})$ sufficiently close to $\Phi({\bf{x}}_{k})$. To achieve this, in the proposed method SREDA, we employ a concave maximizer with stochastic variance reduced gradient ascent on ${\bf{y}}$. The details of SREDA and the concave maximizer are presented in Algorithm 3 and Algorithm 4 respectively. In the rest of this section, we show SREDA can find an ${\mathcal{O}}({\varepsilon})$-stationary point in ${\mathcal{O}}(\kappa^{3}{\varepsilon}^{-3})$ stochastic gradient evaluations.

SREDA estimates the gradient of $f({\bf{x}}_{k},{\bf{y}}_{k})$ by $({\bf{v}}_{k},{\bf{u}}_{k})\approx\left(\nabla_{\bf{x}}f({\bf{x}}_{k},{\bf{y}}_{k}),\nabla_{\bf{y}}f({\bf{x}}_{k},{\bf{y}}_{k})\right)$. As illustrated in Algorithm 4, we evaluate the gradient of $f$ with a large batch size $S_{1}={\mathcal{O}}(\kappa^{2}{\varepsilon}^{-2})$ at the beginning of each period, and update the gradient estimate recursively in concave maximizer with a smaller batch size $S_{2}={\mathcal{O}}(\kappa{\varepsilon}^{-1})$.

For variable ${\bf{x}}_{k}$, we adopt a normalized stochastic gradient descent with a learning rate for theoretical analysis:

With this step size, the change of ${\bf{x}}_{k}$ is not dramatic at each iteration, which leads to accurate gradient estimates. To simplify implementations of the algorithm, we can also use a fixed learning rate in practical.

2 Complexity Analysis

As shown in Algorithm 3, SREDA updates variables with a large batch size per $q$ iterations. We choose $q={\mathcal{O}}({\varepsilon}^{-1})$ as a balance between the number of large batch evaluations with $S_{1}={\mathcal{O}}(\kappa^{2}{\varepsilon}^{-2})$ samples and the concave maximizer with ${\mathcal{O}}(\kappa)$ iterations and $S_{2}={\mathcal{O}}(\kappa{\varepsilon}^{-1})$ samples.

Under Assumptions 1-5 with the following parameter choices:

We should point out the complexity shown in Theorem 1 gives optimal dependency on ${\varepsilon}$. We consider the special case of minimax problem whose objective function has the form

where $g$ is possibly nonconvex and $h$ is strongly-concave, which leads to minimizing on ${\bf{x}}$ and maximizing on ${\bf{y}}$ are independent.

Consequently, finding ${\mathcal{O}}({\varepsilon})$-stationary point of the corresponding $\Phi({\bf{x}})$ can be reduced to finding ${\mathcal{O}}({\varepsilon})$-stationary point of nonconvex function $g({\bf{x}})$, which is based on the stochastic first order-oracle $\nabla_{\bf{x}}F({\bf{x}},{\bf{y}};\xi)=\nabla g({\bf{x}};\xi)$ (this equality holds for any ${\bf{y}}$ since ${\bf{x}}$ and ${\bf{y}}$ are independent). Hence, the analysis of stochastic nonconvex minimization problem based on $\nabla g({\bf{x}};\xi)$ can directly lead to the ${\mathcal{O}}({\varepsilon}^{-3})$ lower bound for our minimax problem. We can prove it by constructing the separate function as $f({\bf{x}},{\bf{y}})=g({\bf{x}})+h({\bf{y}})$ where $g$ is the nonconvex function in Arjevani et al.’s lower bound analysis of stochastic nonconvex minimization, and $h$ is an arbitrary smooth, $\mu$-strongly concave function. It is obvious that the lower bound complexity of finding an ${\mathcal{O}}({\varepsilon})$-stationary point of $\Phi$ is no smaller than that of finding an ${\mathcal{O}}({\varepsilon})$-stationary point of $g$, which requires at least ${\mathcal{O}}({\varepsilon}^{-3})$ stochastic gradient evaluations .

3 Extension to Finite-sum Case

SREDA also works for nonconvex-strongly-concave minimax optimization in the finite-sum case (3) with little modification of Algorithm 3. We just need to replace line 5-7 of Algorithm 3 with the full gradients, and use projected SARAH (PSARAH)PSARAH extends SARAH to constrained case, which requires ${\mathcal{O}}\left((n+\kappa)\log(\kappa/{\varepsilon})\right)$ stochastic gradient evaluation to achieve sufficient accuracy for our initialization. Please see Appendix E.1 for details to initialization. We present the details in Algorithm 5. The algorithm is more efficient than Minimax PPA when $n\geq\kappa^{2}$. We state the result formally in Theorem 2.

Suppose Assumption 1-4 hold. In the finite-sum case with $n\geq\kappa^{2}$, we set the parameters

In the case of $n\leq\kappa^{2}$, we set the parameters

Sketch of Proofs

We present the briefly overview of the proof of Theorem 1. The details are shown in appendix. Different from Lin et al.’s analysis of SGDA which directly considered the value of $\Phi({\bf{x}}_{k})$ and the distance $\left\|{\bf{y}}_{k}-{\bf{y}}^{*}({\bf{x}}_{k})\right\|_{2}$, our proof mainly depends on $f({\bf{x}}_{k},{\bf{y}}_{k})$ and its gradient. We split the change of objective functions after one iteration on $({\bf{x}}_{k},{\bf{y}}_{k})$ into $A_{k}$ and $B_{k}$ as follows

Numerical Experiments

$l_{i}({\bf{x}})=\log(1+\exp(-b_{i}{\bf{a}}_{i}^{\top}{\bf{x}}))$, $g$ is the nonconvex regularizer :

We evaluate compared the performance of SREDA with baseline algorithms GDAmax, GDA, SGDA and Minimax PPA on six real-world data sets “a9a”, “w8a”, “gisette”, “mushrooms”, “sido0” and “rcv1”, whose details are listed in Table 2. The dataset “sido0” comes from Causality Workbenchhttps://www.causality.inf.ethz.ch/challenge.php?page=datasets and the others can be downloaded from LIBSVM repositoryhttps://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/. Our experiments are conducted on a workstation with Intel Xeon Gold 5120 CPU and 256GB memory. We use MATLAB 2018a to run the code and the operating system is Ubuntu 18.04.4 LTS.

The parameters of the algorithms are chosen as follows: The stepsizes of all algorithms are tuned from $\{10^{-3},10^{-2},10^{-1},1\}$ and we keep the stepsize ratio is $\{10,10^{2},10^{3}\}$. For stochastic algorithms SGDA and SREDA, the mini-batch size is set with $\{10,100,200\}$. For SREDA, we use the finite-sum version (Algorithm 5 with the first case of Theorem 2) and let $q=m=\lceil n/S_{2}\rceil$ heuristically. The initialization of SREDA is based on PSARAH with $K_{0}=5$, $b=1$ and $m=20$. For Minimax PPA, we tune the proximal parameter from $\{1,10,100\}$ and momentum parameter from $\{0.2,0.5,0.7\}$. Each inner loop of Minimax PPA has five times Maximin-AG2 which contains five AGD iterations. The results are shown in Figure 1. It is clear that SREDA converges faster than the baseline algorithms.

Conclusion

In this paper, we studied stochastic nonconvex-strongly-concave minimax problems. We proposed a novel algorithm called Stochastic Recursive gradiEnt Descent Ascent (SREDA). The algorithm employs variance reduction to solve minimax problems. Based on the appropriate choice of the parameters, we prove SREDA finds an ${\mathcal{O}}({\varepsilon})$-stationary point of $\Phi$ with a stochastic gradient complexity of ${\mathcal{O}}(\kappa^{3}\varepsilon^{-3})$. This result is better than state-of-the-art algorithms and optimal in its dependency on ${\varepsilon}$. We can also apply SREDA to the finite-sum case, and show that it performs well when $n$ is larger than $\kappa^{2}$.

There are still some open problems left. The complexity of SREDA is optimal with respect to ${\varepsilon}$, but weather it is optimal with respect to $\kappa$ is unknown. It is also possible to employ SREDA to reduce the complexity of stochastic nonconvex-concave minimax problems without the strongly-concave assumption.

Broader Impact

This paper studied the theory of stochastic minimax optimization. The proposed method SREDA is the first stochastic algorithm which attains the optimal dependency on ${\varepsilon}$. This observation help us to understand the minimax optimization without convex-concave assumption. It is interesting to apply SREDA to more machine learning applications in future.

Acknowledgments and Disclosure of Funding

The authors would like to thank Min Tao and Jiahao Xie to point out that the first version of this paper on arXiv has a mistake in the original proof of Theorem 1. This work is supported by GRF 16201320 and the project of Shenzhen Research Institute of Big Data (named “Automated Machine Learning”).

References

Supplementary Materials

This supplementary materials are organized as follows. Appendix A provide several technique lemmas for later analysis. Appendix B give some properties for our concave maximizer. Then, Appendix C proposes projected inexact SARAH (PiSARAH), which generalizes SARAH to constrained optimization and we use it for the initialization of SREDA. Appendix D presents the proof of our main results Theorem 1 and we extend it to prove finite-sum case Theorem 2 in Appendix E.

Appendix A Technical Tools

We first present some useful inequalities in convex optimization, martingale variance bound and gradient mapping.

Let ${\mathcal{V}}_{k}$ be estimator of ${\mathcal{B}}({\bf{z}}_{k})$ as

where ${\mathcal{B}}_{{\mathcal{S}}_{*}}=\frac{1}{|{\mathcal{S}}_{*}|}\sum_{{\mathcal{B}}_{i}\in{\mathcal{S}}_{*}}{\mathcal{B}}_{i}$ satisfies

and ${\mathcal{B}}_{i}$ is $L$-Lipschitz continuous for any ${\mathcal{B}}_{i}\in{\mathcal{S}}_{*}$. Then for all $k=1,\dots,K$, we have

Under assumptions of Lemma 5, we have $\frac{\mu}{2}\left\|{\bf{w}}-{\bf{w}}^{*}\right\|_{2}\leq\left\|{\mathcal{G}}_{\gamma}({\bf{w}})\right\|_{2}$.

where the first inequality use Lemma 5 and the last one is based on Cauchy-Schwarz inequality. Then we obtain the desired result. ∎

Appendix B Some Results of Concave Maximizer

In this section, we present some results of concave maximizer Algorithm 4. The analysis of SREDA is based on the following two auxiliary quantities:

The main target is to prove both $\Delta_{k}$ and $\delta_{k}$ can be bounded by ${\mathcal{O}}(\kappa^{-2}{\varepsilon}^{2})$.

where ${\varepsilon}_{\bf{x}}^{2}$ is defined as $\frac{1}{25}\kappa^{-2}{\varepsilon}^{2}$. We also denote the gradient mapping with respect to ${\bf{y}}$ as

We first introduce some lemmas for our iteration and gradient mapping.

Let ${\bf{y}}^{+}:=\Pi_{{\mathcal{Y}}}({\bf{y}}-\lambda{\bf{u}})$, then for all ${\bf{z}}$, we have

Let ${\bf{y}}^{+}:=\Pi_{{\mathcal{Y}}}({\bf{y}}-\lambda{\bf{u}})$ and \overline{{\bf{y}}_{k,t}}:=\Pi_{{\mathcal{Y}}}\big{(}{\bf{y}}-\lambda\nabla g_{k}({\bf{y}})\big{)}, then we have $\langle\nabla g_{k}({\bf{y}})-{\bf{u}},{\bf{y}}^{+}-\overline{{\bf{y}}_{k,t}}\rangle\leq\lambda\left\|\nabla g_{k}({\bf{y}})-{\bf{u}}\right\|_{2}^{2}$.

Using Lemma 4 and smoothness of $f$, we have

Let $Q({\bf{z}})=f({\bf{y}})+\langle{\bf{u}},{\bf{z}}-{\bf{y}}\rangle+\frac{1}{2\lambda}\left\|{\bf{z}}-{\bf{y}}\right\|_{2}^{2}+r({\bf{z}})$. We have ${\bf{y}}^{+}=\operatorname*{arg\,min}_{\bf{z}}Q({\bf{z}})$ and

for any ${\bf{y}}^{*}\in{\mathcal{Y}}$. Then

We can now present the key lemma for the concave maximizer, which upper bounds the magnitude of gradient mapping after one epoch iterations on ${\bf{y}}$.

Sum over inequalities (7) and (8), we have

where the second inequality uses Young’s inequality as follows

and the last inequality holds due to Lemma 7. Take the expectation on above result, we have

where the second inequality is based on Lemma 3. Summing over (9) with $t$ from $1$ to $m$ and relax the upper bound of $i$ to $m$, we obtain

where the first inequality is based on Lemma 9 and the second one is due to assumption $S_{2}\geq m$. ∎

Using the notations of Algorithm 4, we define $g_{k,t}({\bf{y}})=-\frac{1}{S_{2}}\sum_{i=1}^{S_{2}}\nabla_{\bf{y}}F({\bf{x}}_{k+1},{\bf{y}};{\bm{\xi}}_{t,i})$. Then, we have

The fact $\left\|{\bf{a}}+{\bf{b}}+{\bf{c}}\right\|_{2}^{2}\leq 3\left(\left\|{\bf{a}}\right\|_{2}^{2}+\left\|{\bf{b}}\right\|_{2}^{2}+\left\|{\bf{c}}\right\|_{2}^{2}\right)$ means

We use Lemma 4 and Lemma 8 to bound the first and the second term respectively, that is

The third term is $\left\|{\mathcal{G}}_{\lambda,{\bf{y}}}({\bf{x}}_{k},{\bf{y}}_{k})\right\|_{2}^{2}=\delta_{k}$ because of the definition. Hence, we have

Then we can establish the recursive relationship of $\Delta_{k}$ and $\delta_{k}$.

where the first inequality comes from Lemma 3 by letting ${\mathcal{B}}(\cdot)=\nabla f(\cdot)$ and ${\mathcal{V}}_{k}=({\bf{v}}_{k},{\bf{u}}_{k})$.

where the first inequality is due to Lemma 3; the second inequality comes from Lemma 11 and the third one is due to basic property of geometric sequence.

Combining above results and Lemma 12, we have

Summing over the above inequality from $k_{0}$ to $k$, we can prove the first part of this theorem as follows

where the first inequality is according to Lemma 10, the second inequality is based on Young’s inequality and Lemma 12, the third inequality is due to Lemma 8 and the other steps are based on definitions. ∎

Now we can provide the upper bound of $\Delta_{k}$ and $\delta_{k}$.

Then we have $\Delta_{k}\leq\frac{19}{1125}\kappa^{-2}{\varepsilon}^{2}$ and $\delta_{k}\leq\kappa^{-2}{\varepsilon}^{2}$ for all $k\geq 0$.

Firstly, we let $k_{0}$ be the number of round satisfies ${\rm mod}(k_{0},q)=0$ in Algorithm 3 and $\alpha$ be the one defined in Lemma 10, such that

for all $k_{0}$. Then we prove the statement by induction.

The choice of $S_{1}$ and Assumption 5 means

Combing the assumptions of $\delta_{0}$, we obtain the induction base.

Induction step:

For any $k\geq 1$, we suppose $\Delta_{k^{\prime}}\leq\frac{19}{1125}\kappa^{-2}{\varepsilon}^{2}$ and $\delta_{k^{\prime}}\leq\kappa^{-2}{\varepsilon}^{2}$ holds for all $k^{\prime}<k$. Let $k^{\prime}_{0}$ be the largest integer such that ${\rm mod}(k^{\prime}_{0},q)=0$ and $k^{\prime}_{0}\leq k$. Using Lemma 10, and inequalities (11) and (12), we have

Appendix C Initialization via Projected Inexact SARAH

The initialization of SREDA (line 2 of Algorithm 3) can be regarded as solving a stochastic constrained convex minimization (concave maximization) problem. Hence, we consider the following formulation

The component function $G$ is convex. That is, for any ${\bf{w}}$, ${\bf{w}}^{\prime}$ and random vector ${\bm{\xi}}$, we have

The function $g({\bf{w}})$ is $\mu$-strongly-convex. That is, there exists a constant $\mu>0$ such that for any ${\bf{w}}$ and ${\bf{w}}^{\prime}$, we have

The gradient of each component function $G({\bf{w}};{\bm{\xi}})$ has bounded variance. That is, there exists a constant $\sigma>0$ such that for and ${\bf{w}}$ and random vector ${\bm{\xi}}$, we have

We propose projected inexact SARAH (PiSARAH) to solve problem (15), whose detailed procedure is presented in Algorithm 6.

We are interested in the convergence behavior of the gradient mapping, that is

The remain of this section provide the convergence analysis of PiSARAH.

Note that each epoch of PiSARAH can be regarded as using ConcaveMaximizer (Algorithm 4) on $-g(\cdot)$. Hence, we can follow the analysis of Lemma 10 to achieve the result as follows.

Using Lemma 10 in the view of $g_{k}(\cdot)=g(\cdot)$, we have

We finish the proof by combining (16) and (17). ∎

Then we provide the main result in this section to show the convergence of the gradient mapping.

Using Corollary 3 with $m=\left\lceil 256\kappa\right\rceil$ and $b_{1}=\left\lceil 34\sigma^{2}\zeta^{-1}\right\rceil$ we have

The result of Corollary 3 indicate that we hope the PiSARAH as initialization to make the gradient mapping is no larger than ${\mathcal{O}}(\kappa^{-2}{\varepsilon}^{2})$. The following statement shows we can implement it within ${\mathcal{O}}(\kappa^{2}{\varepsilon}^{-2}\log(\kappa/{\varepsilon}))$ stochastic gradient evaluations.

Appendix D The Proof of Theorem 1

Our proof mainly depends on $f({\bf{x}}_{k},{\bf{y}}_{k})$ and its gradient mapping with respect to ${\bf{y}}$, which is different from Lin et al.’s analysis that directly considered the value of $\Phi({\bf{x}}_{k})$ and the distance $\left\|{\bf{y}}_{k}-{\bf{y}}^{*}({\bf{x}}_{k})\right\|_{2}$. We split the change of objective functions after one iteration on $({\bf{x}}_{k},{\bf{y}}_{k})$ into $A_{k}$ and $B_{k}$ as follows

We provide two lemmas for preparing the proof of our main results, Theorem 1. The first lemma is to upper bound $B_{k}$.

where the inequalities are based on Young’s inequality and Lemma 8.

where the second inequality is based on Lemma 12 and the third inequality is due to Corollary 3.

We bound the second term of (18) as follows:

where the first inequality is based on Lemma 3 and the last one is due to Corollary 3.

By connecting inequalities (18), (19) and (20), we have

Then we show the estimate error of approximating $\nabla\Phi({\bf{x}}_{k})$ by ${\bf{v}}_{k}$.

Consider that we have defined ${\bf{y}}^{*}({\bf{x}})=\operatorname*{arg\,max}_{{\bf{y}}\in{\mathcal{Y}}}f({\bf{x}},{\bf{y}})$, then we have

where the first equality is based on Lemma 1, the second inequality comes from Corollary 1 and the last inequality is due to Lemma 10.

Similarly, we can use Jensen’s inequality and Lemma 10 to prove

By combining the inequalities (21) and (22), we obtain

Now we can present the proof of Theorem 1.

Based on the update of ${\bf{x}}_{k}$ in Algorithm 3, we have

where the first inequality is due to the average smoothness of $f$, and second comes from the Cauchy-Schwartz inequality.

The choice of step size $\eta_{k}$ implies that

where the first inequality is based on $\kappa\geq 1$ and the definition of $\eta_{k}$; the second one uses the fact that $\min(|x|,\frac{x^{2}}{2})\geq|x|-2$ holds for all $x$.

The definition of $\Phi^{*}$ and Assumption 1 implies

By combining inequalities (25), (26), Lemma 14 and Corollary 3; and taking the average over $k=0,\dots,K-1$, we obtain

where the second inequality uses Corollary 3 to bound $\Delta_{k}$.

Appendix E The proof of Theorem 2

In the finite-sum case, we use the full gradient to replace the large batch sample size in stochastic case. Similar to previous section, we extend SARAH to constrained case as the initialization of ${\bf{y}}_{0}$. We can prove Theorem 2 with minor modifications on the analysis of Theorem 1.

We present the detailed procedure of projected SARAH (PSARAH) in Algorithm 7, which is used to initialize ${\bf{y}}_{0}$ in SREDA for problem (3) (line 2 of Algorithm 5). The algorithm considers the following convex optimization problem

Similar to stochastic case, we directly obtain the following result.

The total complexity of stochastic gradient evaluation is