Year: 2020

Abstract:
In the paper, we study a class of useful non-convex minimax optimization problems on Riemanian manifolds and propose a class of Riemanian gradient descent ascent algorithms to solve these minimax problems. Specifically, we propose a new Riemannian gradient descent ascent (RGDA) algorithm for the deterministic minimax optimization. Moreover, we prove that the RGDA has a sample complexity of O(κ −2) for finding an -stationary point of the nonconvex stronglyconcave minimax problems, where κ denotes the condition number. At the same time, we introduce a Riemannian stochastic gradient descent ascent (RSGDA) algorithm for the stochastic minimax optimization. In the theoretical analysis, we prove that the RSGDA can achieve a sample complexity of O(κ −4). To further reduce the sample complexity, we propose a novel momentum variance-reduced Riemannian stochastic gradient descent ascent (MVR-RSGDA) algorithm based on a new momentum variance-reduced technique of STORM. We prove that the MVR-RSGDA algorithm achieves a lower sample complexity of Õ(κ −3) without large batches, which reaches near the best known sample complexity for its Euclidean counterparts. Extensive experimental results on the robust deep neural networks training over Stiefel manifold demonstrate the efficiency of our proposed algorithms.

heading: 1 INTRODUCTION
text: In the paper, we study a class of useful non-convex minimax (a.k.a. min-max) problems on the Riemannian manifoldM with the definition as:
min x∈M max y∈Y f(x, y), (1)
where the function f(x, y) is µ-strongly concave in y but possibly nonconvex in x. Here Y ⊆ Rd is a convex and closed set. f(·, y) : M → R for all y ∈ Y is a smooth but possibly nonconvex real-valued function on manifoldM, and f(x, ·) : Y → R for all x ∈ M a smooth and (strongly)concave real-valued function. In this paper, we mainly focus on the stochastic minimax optimization problem f(x, y) := Eξ∼D[f(x, y; ξ)], where ξ is a random variable that follows an unknown distribution D. In fact, the problem (1) is associated to many existing machine learning applications: 1). Robust Training DNNs over Riemannian manifold. Deep Neural Networks (DNNs) recently have been demonstrating exceptional performance on many machine learning applications. However, they are vulnerable to the adversarial example attacks, which show that a small perturbation in the data input can significantly change the output of DNNs. Thus, the security properties of DNNs have been widely studied. One of secured DNN research topics is to enhance the robustness of DNNs under the adversarial example attacks. To be more specific, given training data D := {ξi = (ai, bi)}ni=1, where ai ∈ Rd and bi ∈ R represent the features and label of sample ξi respectively. Each data sample ai can be corrupted by a universal small perturbation vector y to generate an adversarial attack sample ai + y, as in (Moosavi-Dezfooli et al., 2017; Chaubey et al., 2020). To make DNNs robust against adversarial attacks, one popular approach is to solve the following robust training problem:
min x max y∈Y
1
n n∑ i=1 `(h(ai + y;x), bi) , (2)
where y ∈ Rd denotes a universal perturbation, and x is the weight of the neural network; h(·;x) is the the deep neural network parameterized by x; and `(·) is the loss function. Here the constraint Y = {y : ‖y‖ ≤ ε} indicates that the poisoned samples should not be too different from the original ones.
Recently, the orthonormality on weights of DNNs has gained much interest and has been found to be useful across different tasks such as person re-identification (Sun et al., 2017) and image classification (Xie et al., 2017). In fact, the orthonormality constraints improve the performances of DNNs (Li et al., 2020; Bansal et al., 2018), and reduce overfitting to improve generalization (Cogswell et al., 2015). At the same time, the orthonormality can stabilize the distribution of activations over layers within DNNs (Huang et al., 2018). Thus, we consider the following robust training problem over the Stiefel manifoldM:
min x∈M max y∈Y
1
n n∑ i=1 `(h(ai + y;x), bi). (3)
When data are continuously coming, we can rewrite the problem (3) as follows:
min x∈M max y∈Y
Eξ[f(x, y; ξ)], (4)
where f(x, y; ξ) = `(h(a+ y;x), b) with ξ = (a, b).
2). Distributionally Robust Optimization over Riemannian manifold. Distributionally robust optimization (DRO) (Chen et al., 2017; Rahimian & Mehrotra, 2019) is an effective method to deal with the noisy data, adversarial data, and imbalanced data. At the same time, the DRO in the Riemannian manifold setting is also widely applied in machine learning problems such as robust principal component analysis (PCA). To be more specific, given a set of data samples {ξi}ni=1, the DRO over Riemannian manifoldM can be written as the following minimax problem:
min x∈M max p∈S { n∑ i=1 pi`(x; ξi)− ‖p− 1 n ‖2 } , (5)
where p = (p1, · · · , pn), S = {p ∈ Rn : ∑n i=1 pi = 1, pi ≥ 0}. Here `(x; ξi) denotes the loss function over Riemannian manifold M, which applies to many machine learning problems such as PCA (Han & Gao, 2020a), dictionary learning (Sun et al., 2016), DNNs (Huang et al., 2018), structured low-rank matrix learning (Jawanpuria & Mishra, 2018), among others. For example, the task of PCA can be cast on a Grassmann manifold.
To the best of our knowledge, the existing explicitly minimax optimization methods such as gradient descent ascent method only focus on the minimax problems in Euclidean space. To fill this gap, in the paper, we propose a class of efficient Riemannian gradient descent ascent algorithms to solve the problem (1) via using general retraction and vector transport. When the problem (1) is deterministic, we propose a new deterministic Riemannian gradient descent ascent algorithm. When the problem (1) is stochastic, we propose two efficient stochastic Riemannian gradient descent ascent algorithms. Our main contributions can be summarized as follows:
1) We propose a novel Riemannian gradient descent ascent (RGDA) algorithm for the deterministic minimax optimization problem (1). We prove that the RGDA has a sample complexity of O(κ2 −2) for finding an -stationary point.
2) We also propose a new Riemannian stochastic gradient descent ascent (RSGDA) algorithm for the stochastic minimax optimization. In the theoretical analysis, we prove that the SRGDA has a sample complexity of O(κ4 −4).
3) To further reduce the sample complexity, we introduce a novel momentum variancereduced Riemannian stochastic gradient descent ascent (MVR-RSGDA) algorithm based on a new momentum variance-reduced technique of STORM (Cutkosky & Orabona, 2019). We prove the MVR-RSGDA achieves a lower sample complexity of Õ(κ4 −3) (please see Table 1), which reaches near the best known sample complexity for its Euclidean counterparts.
4) Extensive experimental results on the robust DNN training over Stiefel manifold demonstrate the efficiency of our proposed algorithms.

heading: 2 RELATED WORKS
text: In this section, we briefly review the minimax optimization and Riemannian manifold optimization research works.

heading: 2.1 MINIMAX OPTIMIZATION
text: Minimax optimization recently has been widely applied in many machine learning problems such as adversarial training (Goodfellow et al., 2014; Liu et al., 2019), reinforcement learning (Zhang et al., 2019; 2020), and distribution learning (Razaviyayn et al., 2020). At the same time, many efficient min-max methods (Rafique et al., 2018; Lin et al., 2019; Nouiehed et al., 2019; Thekumparampil et al., 2019; Lin et al., 2020; Yang et al., 2020; Ostrovskii et al., 2020; Yan et al., 2020; Xu et al., 2020a; Luo et al., 2020; Xu et al., 2020b; Boţ & Böhm, 2020; Huang et al., 2020) have been proposed for solving these minimax optimization problems. For example, Thekumparampil et al. (2019) have proposed a class of efficient dual implicit accelerated gradient algorithms to solve smooth min-max optimization. Lin et al. (2019) have proposed a class of efficient gradient decent ascent methods for non-convex minimax optimization. Subsequently, accelerated first-order algorithms Lin et al. (2020) have been proposed for minimax optimization. Xu et al. (2020b) have proposed a unified singleloop alternating gradient projection algorithm for (non)convex-(non)concave minimax problems. Ostrovskii et al. (2020) have proposed an efficient algorithm for finding first-order Nash equilibria in nonconvex concave minimax problems. Xu et al. (2020a); Luo et al. (2020) have proposed a class of fast stochastic variance-reduced GDA algorithms to solve the stochastic minimax problems. More recently, Huang et al. (2020) have presented a class of new momentum-based first-order and zeroth-order descent ascent method for the nonconvex strongly concave minimax problems.

heading: 2.2 RIEMANNIAN MANIFOLD OPTIMIZATION
text: Riemannian manifold optimization methods have been widely applied in machine learning problems including dictionary learning (Sun et al., 2016), matrix factorization (Vandereycken, 2013), and DNNs (Huang et al., 2018). Many Riemannian optimization methods were recently proposed. E.g. Zhang & Sra (2016); Liu et al. (2017) have proposed some efficient first-order gradient methods for geodesically convex functions. Subsequently, Zhang et al. (2016) have presented fast stochastic variance-reduced methods to Riemannian manifold optimization. More recently, Sato et al. (2019) have proposed fast first-order gradient algorithms for Riemannian manifold optimization by using general retraction and vector transport. Subsequently, based on these retraction and vector transport, some fast Riemannian gradient-based methods (Zhang et al., 2018; Kasai et al., 2018; Zhou et al., 2019; Han & Gao, 2020a) have been proposed for non-convex optimization. Riemannian Adam-type algorithms (Kasai et al., 2019) were introduced for matrix manifold optimization. In addition, some algorithms (Ferreira et al., 2005; Li et al., 2009; Wang et al., 2010) have been studied for variational inequalities on Riemannian manifolds, which are the implicit min-max problems on Riemannian manifolds.
Notations: ‖ · ‖ denotes the `2 norm for vectors and spectral norm for matrices. 〈x, y〉 denotes the inner product of two vectors x and y. For function f(x, y), f(x, ·) denotes function w.r.t. the second variable with fixing x, and f(·, y) denotes function w.r.t. the first variable with fixing y. Given a convex closed set Y , we define a projection operation on the set Y as PY(y0) = arg miny∈Y 12‖y − y0‖2. We denote a = O(b) if a ≤ Cb for some constant C > 0, and the notation Õ(·) hides logarithmic terms. Id denotes the identity matrix with d dimension. The operation ⊕ denotes the
Whitney sum. Given Bt = {ξit}Bi=1 for any t ≥ 1, let ∇fBt(x, y) = 1B ∑B i=1∇f(x, y; ξit).

heading: 3 PRELIMINARIES
text: In this section, we first re-visit some basic information on the Riemannian manifoldM. In general, the manifoldM is endowed with a smooth inner product 〈·, ·〉x : TxM× TxM → R on tangent space TxM for every x ∈ M. The induced norm ‖ · ‖x of a tangent vector in TxM is associated with the Riemannian metric. We first define a retraction Rx : TxM →M mapping tangent space TxM onto M with a local rigidity condition that preserves the gradients at x ∈ M (please see Fig.1 (a)). The retraction Rx satisfies all of the following: 1) Rx(0) = x, where 0 ∈ TxM; 2) 〈∇Rx(0), u〉x = u for u ∈ TxM. In fact, exponential mapping Expx is a special case of retraction Rx that locally approximates the exponential mapping Expx to the first order on the manifold.
Next, we define a vector transport T : TM ⊕ TM → TM (please see Fig.1 (b)) that satisfies all of the following 1) T has an associated retraction R, i.e., for x ∈ M and w, u ∈ TxM, Tuw is a tangent vector at Rx(w); 2) T0v = v; 3) Tu(av + bw) = aTuv + bTuw for all a, b ∈ R a u, v, w ∈ TM. Vector transport T yx v or equivalently Tuv with y = Rx(u) transports v ∈ TxM along the retraction curve defined by direction u. Here we focus on the isometric vector transport T yx , which satisfies 〈u, v〉x = 〈T yx u, T yx v〉y for all u, v ∈ TxM. Let ∇f(x, y) = (∇xf(x, y),∇yf(x, y)) denote the gradient over the Euclidean space, and let gradf(x, y) = (gradxf(x, y), gradyf(x, y)) = ProjTxM(∇f(x, y)) denote the Riemannian gradient over tangent space TxM, where ProjX (z) = arg minx∈X ‖x−z‖ is a projection operator. Based on the above definitions, we provide some standard assumptions about the problem (1). Although the problem (1) is non-convex, following (Von Neumann & Morgenstern, 2007), there exists a local solution or stationary point (x∗, y∗) satisfies the Nash Equilibrium, i.e.,
f(x∗, y) ≤ f(x∗, y∗) ≤ f(x, y∗), where x∗ ∈ X and y∗ ∈ Y . Here X ⊂M is a neighbourhood around an optimal point x∗. Assumption 1. X is compact. Each component function f(x, y) is twice continuously differentiable in both x ∈ X and y ∈ Y , and there exist constants L11, L12, L21 and L22, such that for every x, x1, x2 ∈ X and y, y1, y2 ∈ Y , we have
‖gradxf(x1, y; ξ)− T x1x2 gradxf(x2, y; ξ)‖ ≤ L11‖u‖, ‖gradxf(x, y1; ξ)− gradxf(x, y2; ξ)‖ ≤ L12‖y1 − y2‖, ‖∇yf(x1, y; ξ)−∇yf(x2, y; ξ)‖ ≤ L21‖u‖, ‖∇yf(x, y1; ξ)−∇yf(x, y2; ξ)‖ ≤ L22‖y1 − y2‖,
where u ∈ Tx1M and x2 = Rx1(u).
Assumption 1 is commonly used in Riemannian optimization (Sato et al., 2019; Han & Gao, 2020a), and min-max optimization (Lin et al., 2019; Luo et al., 2020; Xu et al., 2020b). Here, the terms L11, L12 and L21 implicitly contain the curvature information as in (Sato et al., 2019; Han & Gao, 2020a). Specifically, Assumption 1 implies the partial Riemannian gradient gradxf(·, y; ξ) for all y ∈ Y is retraction L11-Lipschitz continuous as in (Han & Gao, 2020a) and the partial gradient ∇yf(x, ·; ξ) for all x ∈ X is L22-Lipschitz continuous as in (Lin et al., 2019). Since ‖gradxf(x, y1; ξ) − gradxf(x, y2; ξ)‖ = ‖ProjTxM ( ∇xf(x, y1; ξ) ) −
ProjTxM ( ∇xf(x, y2; ξ) ) ‖ ≤ ‖∇xf(x, y1; ξ) − ∇xf(x, y2; ξ)‖ ≤ L12‖y1 − y2‖, we can obtain ‖gradxf(x, y1; ξ) − gradxf(x, y2; ξ)‖ ≤ L12‖y1 − y2‖ by the L12-Lipschitz continuous of ∇xf(x, ·; ξ) for all x ∈ X . Let the partial Riemannian gradient gradyf(·, y; ξ) for all y ∈ Y be retraction L̃21-Lipschitz, i.e., ‖gradyf(x1, y; ξ) − T x1x2 gradyf(x2, y; ξ)‖ ≤ L̃21‖u‖. Since ‖gradyf(x1, y; ξ) − T x1x2 gradyf(x2, y; ξ)‖ = ‖ProjTxM ( ∇yf(x1, y; ξ) ) −
T x1x2 ProjTxM ( ∇yf(x2, y; ξ) ) ‖ ≤ ‖∇yf(x1, y; ξ)−∇yf(x2, y; ξ)‖ ≤ L21‖u‖, we have L21 ≥ L̃21.
For the deterministic problem, let f(x, y) instead of f(x, y; ξ) in Assumption 1. Since f(x, y) is strongly concave in y ∈ Y , there exists a unique solution to the problem maxy∈Y f(x, y) for any x. We define the function Φ(x) = maxy∈Y f(x, y) and y∗(x) = arg maxy∈Y f(x, y). Assumption 2. The function Φ(x) is retraction L-smooth. There exists a constant L > 0, for all x ∈ X , z = Rx(u) with u ∈ TxM, such that
Φ(z) ≤ Φ(x) + 〈gradΦ(x), u〉+ L 2 ‖u‖2. (6)
Assumption 3. The objective function f(x, y) is µ-strongly concave w.r.t y, i.e., for any x ∈M
f(x, y1) ≤ f(x, y2) + 〈∇yf(x, y2), y1 − y2〉 − µ
2 ‖y1 − y2‖2, ∀y1, y2 ∈ Y. (7)
Assumption 4. The function Φ(x) is bounded from below inM, i.e., Φ∗ = infx∈M Φ(x). Assumption 5. The variance of stochastic gradient is bounded, i.e., there exists a constant σ1 > 0 such that for all x, it follows Eξ‖gradxf(x, y; ξ) − gradxf(x, y)‖2 ≤ σ21; There exists a constant σ2 > 0 such that for all y, it follows Eξ‖∇yf(x, y; ξ) − ∇yf(x, y)‖2 ≤ σ22 . We also define σ = max{σ1, σ2}.
Assumption 2 imposes the retraction smooth of function Φ(x), as in Sato et al. (2019); Han & Gao (2020b;a). Assumption 3 imposes the strongly concave of f(x, y) on variable y, as in (Lin et al., 2019; Luo et al., 2020). Assumption 4 guarantees the feasibility of the nonconvex-strongly-concave problems, as in (Lin et al., 2019; Luo et al., 2020). Assumption 5 imposes the bounded variance of stochastic (Riemannian) gradients, which is commonly used in the stochastic optimization (Han & Gao, 2020b; Lin et al., 2019; Luo et al., 2020).

heading: 4 RIEMANIAN GRADIENT DESCENT ASCENT
text: In the section, we propose a class of Riemannian gradient descent ascent algorithm to solve the deterministic and stochastic minimax optimization problem (1), respectively.

heading: 4.1 RGDA AND RSGDA ALGORITHMS
text: In this subsection, we propose an efficient Riemannian gradient descent ascent (RGDA) algorithm to solve the deterministic min-max problem (1). At the same time, we propose a standard Riemannian stochastic gradient descent ascent (RSGDA) algorithm to solve the stochastic min-max problem (1). Algorithm 1 summarizes the algorithmic framework of our RGDA and RSGDA algorithms.
At the step 5 of Algorithm 1, we apply the retraction operator to ensure the variable xt for all t ≥ 1 in the manifoldM. At the step 6 of Algorithm 1, we use 0 < ηt ≤ 1 to ensure the variable yt for all t ≥ 1 in the convex constraint Y . Here we define a reasonable metric to measure the convergence:
Ht = ‖gradΦ(xt)‖+ L̃‖yt − y∗(xt)‖, (10)
where L̃ = max(1, L11, L12, L21, L22), and the first term of Ht measures convergence of the iteration solutions {xt}Tt=1, and the last term measures convergence of the iteration solutions {yt}Tt=1. Since the function f(x, y) is strongly concave in y ∈ Y , there exists a unique solution y∗(x) to the problem maxy∈Y f(x, y) for any x ∈ M. Thus, we apply the standard metric ‖yt − y∗(xt)‖ to measure convergence of the parameter y. Given y = y∗(xt), we use the standard metric ‖gradΦ(xt)‖ = ‖gradxf(xt, y∗(xt))‖ to measure convergence of the parameter x. Note that we use the coefficient L̃ to balance the scale of metrics of the variable x and the variable y.
Algorithm 1 RGDA and RSGDA Algorithms for Min-Max Optimization
1: Input: T , parameters {γ, λ, ηt}Tt=1, mini-batch size B, and initial input x1 ∈M, y1 ∈ Y; 2: for t = 1, 2, . . . , T do 3: (RGDA) Compute deterministic gradients
vt = gradxf(xt, yt), wt = ∇yf(xt, yt); (8)
4: (RSGDA) Draw B i.i.d. samples {ξit}Bi=1, then compute stochastic gradients
vt = 1
B B∑ i=1 gradxf(xt, yt; ξ i t), wt = 1 B B∑ i=1 ∇yf(xt, yt; ξit); (9)
5: Update: xt+1 = Rxt(−γηtvt); 6: Update: ỹt+1 = PY(yt + λwt) and yt+1 = yt + ηt(ỹt+1 − yt); 7: end for 8: Output: xζ and yζ chosen uniformly random from {xt, yt}Tt=1.
Algorithm 2 MVR-RSGDA Algorithm for Min-Max Optimization 1: Input: T , parameters {γ, λ, b,m, c1, c2} and initial input x1 ∈M and y1 ∈ Y; 2: Draw B i.i.d. samples B1 = {ξi1}Bi=1, then compute v1 = gradxfB1(x1, y1) and w1 = ∇yfB1(x1, y1);
3: for t = 1, 2, . . . , T do 4: Compute ηt = b(m+t)1/3 ; 5: Update: xt+1 = Rxt(−γηtvt); 6: Update: ỹt+1 = PY(yt + λwt) and yt+1 = yt + ηt(ỹt+1 − yt); 7: Compute αt+1 = c1η2t and βt+1 = c2η 2 t ; 8: Draw B i.i.d. samples Bt+1 = {ξit+1}Bi=1, then compute
vt+1 = gradxfBt+1(xt+1, yt+1) + (1− αt+1)T xt+1xt [ vt − gradxfBt+1(xt, yt) ] , (12)
wt+1 = ∇yfBt+1(xt+1, yt+1) + (1− βt+1) [ wt −∇yfBt+1(xt, yt) ] ; (13)
9: end for 10: Output: xζ and yζ chosen uniformly random from {xt, yt}Tt=1.

heading: 4.2 MVR-RSGDA ALGORITHM
text: In this subsection, we propose a novel momentum variance-reduced stochastic Riemannian gradient descent ascent (MVR-RSGDA) algorithm to solve the stochastic min-max problem (1), which builds on the momentum-based variance reduction technique of STORM (Cutkosky & Orabona, 2019). Algorithm 2 describes the algorithmic framework of MVR-RSGDA method.
In Algorithm 2, we use the momentum-based variance-reduced technique of STORM to update stochastic Riemannian gradient vt:
vt+1 = αt+1 gradxfBt+1(xt+1, yt+1)︸ ︷︷ ︸ SGD
+ (1− αt+1) ( gradxfBt+1(xt+1, yt+1)− T xt+1xt ( gradxfBt+1(xt, yt)− vt ))︸ ︷︷ ︸ SPIDER
= gradxfBt+1(xt+1, yt+1) + (1− αt+1)T xt+1xt ( vt − gradxfBt+1(xt, yt) ) , (11)
where αt+1 ∈ (0, 1]. When αt+1 = 1, vt will degenerate a vanilla stochastic Riemannian gradient; When αt+1 = 0, vt will degenerate a stochastic Riemannian gradient based on variance-reduced technique of SPIDER (Nguyen et al., 2017; Fang et al., 2018). Similarly, we use this momentumbased variance-reduced technique to estimate the stochastic gradient wt.

heading: 5 CONVERGENCE ANALYSIS
text: In this section, we study the convergence properties of our RGDA, RSGDA, and MVR-RSGDA algorithms under some mild conditions. For notational simplicity, let L̃ = max(1, L11, L12, L21, L22) and κ = L21/µ denote the number condition of function f(x, y). We first give a useful lemma. Lemma 1. Under the assumptions in §3, the gradient of function Φ(x) = maxy∈Y f(x, y) is retraction G-Lipschitz, and the mapping or function y∗(x) = arg maxy∈Y f(x, y) is retraction κLipschitz. Given any x1, x2 = Rx1(u) ∈ X ⊂M and u ∈ Tx1M, we have:
‖gradΦ(x1)− T x1x2 gradΦ(x2)‖ ≤ G‖u‖, ‖y ∗(x1)− y∗(x2)‖ ≤ κ‖u‖, (14)
where G = κL12 + L11 and κ = L21/µ.

heading: 5.1 CONVERGENCE ANALYSIS OF BOTH THE RGDA AND RSGDA ALGORITHMS
text: In the subsection, we study the convergence properties of deterministic RGDA and stochastic RSGDA algorithms. The related proofs of RGDA and RSGDA are provided in Appendix A.1. Theorem 1. Suppose the sequence {xt, yt}Tt=1 is generated from Algorithm 1 by using deterministic gradients. Given η = ηt for all t ≥ 1, 0 < η ≤ min(1, 12γL ), 0 < λ ≤ 1 6L̃ and 0 < γ ≤ µλ 10L̃κ
, we have
1
T T∑ t=1 [ ‖gradΦ(xt)‖+ L̃‖yt − y∗(xt)‖ ] ≤
2 √
Φ(x1)− Φ∗√ γηT . (15)
Remark 1. Since 0 < η ≤ min(1, 12γL ) and 0 < γ ≤ µλ 10L̃κ , we have 0 < ηγ ≤ min( µλ 10L̃κ , 12L ). Let ηγ = min( µλ 10L̃κ , 12L ), we have ηγ = O( 1 κ2 ). The RGDA algorithm has convergence rate of
O (
κ T 1/2
) . By κ
T 1/2 ≤ , i.e., E[Hζ ] ≤ , we choose T ≥ κ2 −2. In the deterministic RGDA
Algorithm, we need one sample to estimate the gradients vt and wt at each iteration, and need T iterations. Thus, the RGDA reaches a sample complexity of T = O(κ2 −2) for finding an - stationary point. Theorem 2. Suppose the sequence {xt, yt}Tt=1 is generated from Algorithm 1 by using stochastic gradients. Given η = ηt for all t ≥ 1, 0 < η ≤ min(1, 12γL ), 0 < λ ≤ 1 6L̃ and 0 < γ ≤ µλ 10L̃κ
, we have
1
T T∑ t=1 E [ ‖gradΦ(xt)‖+ L̃‖yt − y∗(xt)‖ ] ≤
2 √
Φ(x1)− Φ∗√ γηT + √ 2σ√ B + 5 √ 2L̃σ√ Bµ . (16)
Remark 2. Since 0 < η ≤ min(1, 12γL ) and 0 < γ ≤ µλ 10L̃κ , we have 0 < ηγ ≤ min( µλ 10L̃κ , 12L ). Let ηγ = min( µλ 10L̃κ , 12L ), we have ηγ = O( 1 κ2 ). Let B = T , the RSGDA algorithm has convergence
rate of O (
κ T 1/2
) . By κ
T 1/2 ≤ , i.e., E[Hζ ] ≤ , we choose T ≥ κ2 −2. In the stochastic RSGDA
Algorithm, we need B samples to estimate the gradients vt and wt at each iteration, and need T iterations. Thus, the RSGDA reaches a sample complexity of BT = O(κ4 −4) for finding an -stationary point.

heading: 5.2 CONVERGENCE ANALYSIS OF THE MVR-RSGDA ALGORITHM
text: In the subsection, we provide the convergence properties of the MVR-RSGDA algorithm. The related proofs of MVR-RSGDA are provided in Appendix A.2. Theorem 3. Suppose the sequence {xt, yt}Tt=1 is generated from Algorithm 2. Given y1 = y∗(x1), c1 ≥ 23b3 + 2λµ, c2 ≥ 2 3b3 + 50λL̃2 µ , b > 0, m ≥ max ( 2, (c̃b)3 ) , 0 < γ ≤ µλ 2κL̃ √ 25+4µλ and 0 < λ ≤ 1 6L̃ , we have
1
T T∑ t=1 E [ ‖gradΦ(xt)‖+ L̃‖yt − y∗(xt)‖ ] ≤ √ 2M ′m1/6 T 1/2 + √ 2M ′ T 1/3 , (17)
where c̃ = max(1, c1, c2, 2γL) and M ′ = 2(Φ(x1)−Φ∗) γb + 2σ2 Bλµη0b + 2(c21+c 2 2)σ 2b2 Bλµ ln(m+ T ).
Remark 3. Let c1 = 23b3 + 2λµ, c2 = 2 3b3 + 50λL̃2 µ , λ = 1 6L̃ , γ = µλ 2κL̃ √ 25+4µλ and η0 = bm1/3 . It is easy verified that γ = O( 1κ2 ), λ = O(1), λµ = O( 1 κ ), c1 = O(1), c2 = O(κ), m = O(κ
3) and η0 = O( 1 κ ). Without loss of generality, let T ≥ m = O(κ 3), we haveM ′ = O ( κ2+ κ 2 B + κ3 B ln(T ) ) .
When B = κ, we have M ′ = O ( κ2 ln(T ) ) . Thus, the MVR-RSGDA algorithm has a convergence
rate of Õ (
κ T 1/3
) . By κ
T 1/3 ≤ , i.e., E[Hζ ] ≤ , we choose T ≥ κ3 −3. In Algorithm 2, we require
B samples to estimate the stochastic gradients vt and wt at each iteration, and need T iterations. Thus, the MVR-RSGDA has a sample complexity of BT = Õ ( κ4 −3 ) for finding an -stationary point of the problem (1). Similarly, when B = 1, the MVR-RSGDA algorithm has a convergence rate of Õ ( κ3/2
T 1/3
) , and has a sample complexity of BT = Õ ( κ9/2 −3 ) for finding an -stationary
point.
Remark 4. In the about theoretical analysis, we only assume the convexity of constraint set Y , while Lin et al. (2019) not only assume the convexity of set Y , but also assume and use its bounded (Please see Assumption 4.2 in (Lin et al., 2019)). Clearly, our assumption is milder than (Lin et al., 2019). When there does not exist a constraint set on parameter y, i.e.,Y = Rd, our algorithms and theoretical results still work, while Lin et al. (2019) can‘t work.

heading: 6 EXPERIMENTS
text: In this section, we conduct the deep neural network (DNN) robust training over the Stiefel manifold St(r, d) = {W ∈ Rd×r : WTW = Ir} to evaluate the performance of our algorithms. In the experiment, we use MNIST, CIFAR-10, and CIFAR-100 datasets to train the model ( More experimental results on SVHN, STL10, and FashionMNIST datasets are provided in the Appendix B ). Considering the sample size is large in these datasets, we only compare the proposed stochastic algorithms (RSGDA and MVR-RSGDA) in the experiments. Here, we use the SGDA algorithm (Lin et al., 2019) as a baseline, which does not apply the orthogonal regularization in the DNN robust training.

heading: 6.1 EXPERIMENTAL SETTING
text: Given a deep neural network h(·;x) parameterized by x as shown in the above problem (2), the weights of l-th layer is xi ∈ St(nlin, nlout), where St(nlin, nlout) is the Stiefel manifold of l-th layer.
For both RSGDA and MVR-RSGDA algorithms, we set {γ, λ} to {1.0, 0.1}. We further set {b, m, c1, c2} to 0.5, 8, 512, 512 for MVR-RSGDA. η in RSGDA is set to 0.01. For both algorithms, the mini-batch size is set to 512. We set for y as 0.05 and 0.03 for the MNIST dataset and CIFAR10/100 datasets. The above settings are the same for all datasets. An 8-layer (5 convolution layers and 3 dense layers) deep neural network is used in all experiments. All codes are implemented with McTorch (Meghwanshi et al., 2018) which is based on PyTorch (Paszke et al., 2019).

heading: 6.2 EXPERIMENTAL RESULTS
text: The training loss plots of the robust training problem in the above Eq. (2) are shown in Fig. 2. From the figure, we can see that MVR-RSGDA enjoys a faster convergence speed compared to the baseline RSGDA. It’s also clear that when the dataset becomes complicate (from MNIST to CIFAR-10/100), the advantage of MVR-RSGDA becomes larger.
When it comes to robust training, the training loss is not enough to identify which algorithm is better. We also use a variant of uniform perturbation to attack the model trained by our algorithms. We follow the design of uniform attack in previous works (Moosavi-Dezfooli et al., 2017; Chaubey et al., 2020), and the detail uniform attack objective is shown below:
min y∈Y
1
n n∑ i=1 max ( hbi(y + ai)−max j 6=bi hj(y + ai), 0 ) , s.t. Y = {‖y‖∞ ≤ ε}
where hj is the j-th logit of the output from the deep neural network, and y here is a uniform permutation added for all inputs. In practice, we sample a mini-batch with 512 samples at each iteration. The optimization of the uniform permutation lasts for 1000 iterations for all settings. The attack loss is presented in Fig 3. The attack loss for the model trained by MVR-RSGDA is higher compared to both RSGDA and SGDA, which indicates the model trained by MVR-RSGDA is harder to attack and thus more robust. The test accuracy with natural image and uniform attack is shown in Tab. 2, which also suggests the advantage of MVR-RSGDA. More results are provided in Appendix B.

heading: 7 CONCLUSION
text: In the paper, we investigated a class of useful min-max optimization problems on the Riemanian manifold. We proposed a class of novel efficient Riemanian gradient descent ascent algorithms to solve these minimax problems, and studied the convergence properties of the proposed algorithms. For example, we proved that our new MVR-RSGDA algorithm achieves a sample complexity of Õ(κ4 −3) without large batches, which reaches near the best known sample complexity for its Euclidean counterparts.

heading: A APPENDIX
text: In this section, we provide the detailed convergence analysis of our algorithms. We first review some useful lemmas.
Lemma 2. (Nesterov, 2018) Assume that f(x) is a differentiable convex function and X is a convex set. x∗ ∈ X is the solution of the constrained problem minx∈X f(x), if
〈∇f(x∗), x− x∗〉 ≥ 0, x ∈ X . (18)
Lemma 3. (Nesterov, 2018) Assume the function f(x) is L-smooth, i.e., ‖∇f(x) − ∇f(y)‖ ≤ L‖x− y‖, and then the following inequality holds
|f(y)− f(x)−∇f(x)T (y − x)| ≤ L 2 ‖x− y‖2. (19)
Next, based on the above assumptions and Lemmas, we gives some useful lemmas:
Lemma 4. The gradient of function Φ(x) = maxy∈Y f(x, y) is retraction G-Lipschitz, and the mapping or function y∗(x) = arg maxy∈Y f(x, y) is retraction κ-Lipschitz. Given any x1, x2 = Rx1(u) ∈ X ⊂M and u ∈ Tx1M, we have
‖gradΦ(x1)− T x1x2 gradΦ(x2)‖ ≤ G‖u‖, ‖y∗(x1)− y∗(x2)‖ ≤ κ‖u‖,
where G = κL12 + L11 and κ = L21/µ, and vector transport T x1x2 transport the tangent space of x1 to that of x2.
Proof. Given any x1, x2 = Rx1(u) ∈ X and u ∈ Tx1M, define y∗(x1) = arg maxy∈Y f(x1, y) and y∗(x2) = arg maxy∈Y f(x2, y), by the above Lemma 2, we have
(y − y∗(x1))T∇yf(x1, y∗(x1)) ≤ 0, ∀y ∈ Y (20) (y − y∗(x2))T∇yf(x2, y∗(x2)) ≤ 0, ∀y ∈ Y. (21)
Let y = y∗(x2) in the inequality (20) and y = y∗(x1) in the inequality (21), then summing these inequalities, we have
(y∗(x2)− y∗(x1))T ( ∇yf(x1, y∗(x1))−∇yf(x2, y∗(x2)) ) ≤ 0. (22)
Since the function f(x1, ·) is µ-strongly concave, we have
f(x1, y ∗(x1)) ≤ f(x1, y∗(x2)) + (∇yf(x1, y∗(x2)))T (y∗(x1)− y∗(x2))−
µ 2 ‖y∗(x1)− y∗(x2)‖2,
(23)
f(x1, y ∗(x2)) ≤ f(x1, y∗(x1)) + (∇yf(x1, y∗(x1)))T (y∗(x2)− y∗(x1))−
µ 2 ‖y∗(x1)− y∗(x2)‖2.
(24)
Combining the inequalities (23) with (24), we obtain (y∗(x2)− y∗(x1))T ( ∇yf(x1, y∗(x2))−∇yf(x1, y∗(x1)) ) + µ‖y∗(x1)− y∗(x2)‖2 ≤ 0. (25)
By plugging the inequalities (22) into (25), we have µ‖y∗(x1)− y∗(x2)‖2 ≤ (y∗(x2)− y∗(x1))T ( ∇yf(x2, y∗(x2))−∇yf(x1, y∗(x2)) ) ≤ ‖y∗(x2)− y∗(x1)‖‖∇yf(x2, y∗(x2))−∇yf(x1, y∗(x2))‖ ≤ L21‖u‖‖y∗(x2)− y∗(x1)‖, (26)
where the last inequality is due to Assumption 1. Thus, we have
‖y∗(x1)− y∗(x2)‖ ≤ κ‖u‖, (27)
where κ = L21/µ and x2 = Rx1(u), u ∈ Tx1M.
Since Φ(x) = f(x, y∗(x)), we have gradΦ(x) = gradxf(x, y ∗(x)). Then we have
‖gradΦ(x1)−T x1x2 gradΦ(x2)‖ = ‖gradxf(x1, y∗(x1))− T x1x2 gradxf(x2, y
∗(x2))‖ ≤ ‖gradxf(x1, y∗(x1))−gradxf(x1, y∗(x2))‖+‖gradxf(x1, y∗(x2))−T x1x2 gradxf(x2, y
∗(x2))‖ ≤ L12‖y∗(x1)− y∗(x2)‖+ L11‖u‖ ≤ (κL12 + L11)‖u‖, (28)
where u ∈ Tx1M.
Lemma 5. Suppose the sequence {xt, yt}Tt=1 is generated from Algorithm 1 or 2. Given 0 < ηt ≤ 1 2γL , we have
Φ(xt+1) ≤ Φ(xt) + γL12ηt‖y∗(xt)− yt‖2 + γηt‖gradxf(xt, yt)− vt‖2 − γηt 2 ‖gradΦ(xt)‖2
− γηt 4 ‖vt‖2. (29)
Proof. According to Assumption 2, i.e., the function Φ(x) is retraction L-smooth, we have
Φ(xt+1) ≤ Φ(xt)− γηt〈gradΦ(xt), vt〉+ γ2η2tL
2 ‖vt‖2 (30)
= Φ(xt) + γηt 2 ‖gradΦ(xt)− vt‖2 − γηt 2 ‖gradΦ(xt)‖2 + (
γ2η2tL
2 − γηt 2 )‖vt‖2
= Φ(xt) + γηt 2 ‖gradΦ(xt)− gradxf(xt, yt) + gradxf(xt, yt)− vt‖2 − γηt 2 ‖gradΦ(xt)‖2
+ ( γ2η2tL 2 − γηt 2 )‖vt‖2
≤ Φ(xt) + γηt‖gradΦ(xt)− gradxf(xt, yt)‖2 + γηt‖gradxf(xt, yt)− vt‖2 − γηt 2 ‖gradΦ(xt)‖2
+ ( Lγ2η2t 2 − γηt 2 )‖vt‖2
≤ Φ(xt) + γηt‖gradΦ(xt)− gradxf(xt, yt)‖2 + γηt‖gradxf(xt, yt)− vt‖2 − γηt 2 ‖gradΦ(xt)‖2
− γηt 4 ‖vt‖2,
where the last inequality is due to 0 < ηt ≤ 12γL .
Consider an upper bound of ‖gradΦ(xt)− gradxf(xt, yt)‖2, we have ‖gradΦ(xt)− gradxf(xt, yt)‖2 = ‖gradxf(xt, y∗(xt))− gradxf(xt, yt)‖2 ≤ L12‖y∗(xt)− yt‖2. (31) Then we have
Φ(xt+1) ≤ Φ(xt) + γηtL12‖y∗(xt)− yt‖2 + γηt‖gradxf(xt, yt)− vt‖2 − γηt 2 ‖gradΦ(xt)‖2
− γηt 4 ‖vt‖2. (32)
Lemma 6. Suppose the sequence {xt, yt}Tt=1 is generated from Algorithm 1 or 2. Under the above assumptions, and set 0 < ηt ≤ 1 and 0 < λ ≤ 16L̃ , we have
‖yt+1 − y∗(xt+1)‖2 ≤ (1− ηtµλ
4 )‖yt − y∗(xt)‖2 − 3ηt 4 ‖ỹt+1 − yt‖2
+ 25ηtλ
6µ ‖∇yf(xt, yt)− wt‖2 + 25γ2κ2ηt 6µλ ‖vt‖2, (33)
where κ = L21/µ.
Proof. According to the assumption 3, i.e., the function f(x, y) is µ-strongly concave w.r.t y, we have
f(xt, y) ≤ f(xt, yt) + 〈∇yf(xt, yt), y − yt〉 − µ
2 ‖y − yt‖2
= f(xt, yt) + 〈wt, y − ỹt+1〉+ 〈∇yf(xt, yt)− wt, y − ỹt+1〉
+ 〈∇yf(xt, yt), ỹt+1 − yt〉 − µ
2 ‖y − yt‖2. (34)
According to the assumption 1, i.e., the function f(x, y) is L22-smooth w.r.t y, and L̃ ≥ L22, we have
f(xt, ỹt+1)− f(xt, yt)− 〈∇yf(xt, yt), ỹt+1 − yt〉 ≥ − L22 2 ‖ỹt+1 − yt‖2
≥ − L̃ 2 ‖ỹt+1 − yt‖2. (35)
Combining the inequalities (34) with (35), we have
f(xt, y) ≤ f(xt, ỹt+1) + 〈wt, y − ỹt+1〉+ 〈∇yf(xt, yt)− wt, y − ỹt+1〉
− µ 2 ‖y − yt‖2 + L̃ 2 ‖ỹt+1 − yt‖2. (36)
According to the step 6 of Algorithm 1 or 2, we have ỹt+1 = PY(yt + λwt) = arg miny∈Y 12‖y − yt − λwt‖2. Since Y is a convex set and the function 12‖y − yt − λwt‖
2 is convex, according to Lemma 2, we have
〈ỹt+1 − yt − λwt, y − ỹt+1〉 ≥ 0, y ∈ Y. (37) Then we obtain
〈wt, y − ỹt+1〉 ≤ 1
λ 〈ỹt+1 − yt, y − ỹt+1〉
= 1
λ 〈ỹt+1 − yt, yt − ỹt+1〉+
1 λ 〈ỹt+1 − yt, y − yt〉
= − 1 λ ‖ỹt+1 − yt‖2 + 1 λ 〈ỹt+1 − yt, y − yt〉. (38)
Combining the inequalities (36) with (38), we have
f(xt, y) ≤ f(xt, ỹt+1) + 1
λ 〈ỹt+1 − yt, y − yt〉+ 〈∇yf(xt, yt)− wt, y − ỹt+1〉
− 1 λ ‖ỹt+1 − yt‖2 − µ 2 ‖y − yt‖2 + L̃ 2 ‖ỹt+1 − yt‖2. (39)
Let y = y∗(xt) and we obtain
f(xt, y ∗(xt)) ≤ f(xt, ỹt+1) +
1 λ 〈ỹt+1 − yt, y∗(xt)− yt〉+ 〈∇yf(xt, yt)− wt, y∗(xt)− ỹt+1〉
− 1 λ ‖ỹt+1 − yt‖2 − µ 2 ‖y∗(xt)− yt‖2 + L̃ 2 ‖ỹt+1 − yt‖2. (40)
Due to the concavity of f(·, y) and y∗(xt) = arg maxy∈Y f(xt, y), we have f(xt, y∗(xt)) ≥ f(xt, ỹt+1). Thus, we obtain
0 ≤ 1 λ 〈ỹt+1 − yt, y∗(xt)− yt〉+ 〈∇yf(xt, yt)− wt, y∗(xt)− ỹt+1〉
− ( 1 λ − L̃ 2 )‖ỹt+1 − yt‖2 − µ 2 ‖y∗(xt)− yt‖2. (41)
By yt+1 = yt + ηt(ỹt+1 − yt), we have
‖yt+1 − y∗(xt)‖2 = ‖yt + ηt(ỹt+1 − yt)− y∗(xt)‖2
= ‖yt − y∗(xt)‖2 + 2ηt〈ỹt+1 − yt, yt − y∗(xt)〉+ η2t ‖ỹt+1 − yt‖2. (42)
Then we obtain
〈ỹt+1 − yt, y∗(xt)− yt〉 ≤ 1
2ηt ‖yt − y∗(xt)‖2 + ηt 2 ‖ỹt+1 − yt‖2 − 1 2ηt ‖yt+1 − y∗(xt)‖2. (43)
Consider the upper bound of the term 〈∇yf(xt, yt)− wt, y∗(xt)− ỹt+1〉, we have
〈∇yf(xt, yt)− wt, y∗(xt)− ỹt+1〉 = 〈∇yf(xt, yt)− wt, y∗(xt)− yt〉+ 〈∇yf(xt, yt)− wt, yt − ỹt+1〉
≤ 1 µ ‖∇yf(xt, yt)− wt‖2 + µ 4 ‖y∗(xt)− yt‖2 + 1 µ ‖∇yf(xt, yt)− wt‖2 + µ 4 ‖yt − ỹt+1‖2
= 2
µ ‖∇yf(xt, yt)− wt‖2 +
µ 4 ‖y∗(xt)− yt‖2 + µ 4 ‖yt − ỹt+1‖2. (44)
By plugging the inequalities (41), (43) to (44), we have
1
2ηtλ ‖yt+1 − y∗(xt)‖2 ≤ (
1 2ηtλ − µ 4 )‖yt − y∗(xt)‖2 + ( ηt 2λ + µ 4 + L̃ 2 − 1 λ )‖ỹt+1 − yt‖2
+ 2
µ ‖∇yf(xt, yt)− wt‖2
≤ ( 1 2ηtλ − µ 4 )‖yt − y∗(xt)‖2 + ( 3L̃ 4 − 1 2λ )‖ỹt+1 − yt‖2 + 2 µ ‖∇yf(xt, yt)− wt‖2
= ( 1 2ηtλ − µ 4 )‖yt − y∗(xt)‖2 − ( 3 8λ + 1 8λ − 3L̃ 4 ) ‖ỹt+1 − yt‖2
+ 2
µ ‖∇yf(xt, yt)− wt‖2
≤ ( 1 2ηtλ − µ 4 )‖yt − y∗(xt)‖2 − 3 8λ ‖ỹt+1 − yt‖2 + 2 µ ‖∇yf(xt, yt)− wt‖2,
(45)
where the second inequality holds by L̃ ≥ L22 ≥ µ and 0 < ηt ≤ 1, and the last inequality is due to 0 < λ ≤ 1
6L̃ . It implies that
‖yt+1 − y∗(xt)‖2 ≤ (1− ηtµλ
2 )‖yt − y∗(xt)‖2 − 3ηt 4 ‖ỹt+1 − yt‖2 + 4ηtλ µ ‖∇yf(xt, yt)− wt‖2.
(46)
Next, we decompose the term ‖yt+1 − y∗(xt+1)‖2 as follows:
‖yt+1 − y∗(xt+1)‖2 = ‖yt+1 − y∗(xt) + y∗(xt)− y∗(xt+1)‖2
= ‖yt+1 − y∗(xt)‖2 + 2〈yt+1 − y∗(xt), y∗(xt)− y∗(xt+1)〉+ ‖y∗(xt)− y∗(xt+1)‖2
≤ (1 + ηtµλ 4 )‖yt+1 − y∗(xt)‖2 + (1 + 4 ηtµλ )‖y∗(xt)− y∗(xt+1)‖2
≤ (1 + ηtµλ 4 )‖yt+1 − y∗(xt)‖2 + (1 + 4 ηtµλ )η2t γ 2κ2‖vt‖2, (47)
where the first inequality holds by the Cauchy-Schwarz inequality and Young’s inequality, and the last equality is due to Lemma 4.
By combining the above inequalities (46) and (47), we have
‖yt+1 − y∗(xt+1)‖2 ≤ (1 + ηtµλ 4 )(1− ηtµλ 2 )‖yt − y∗(xt)‖2 − (1 + ηtµλ 4 ) 3ηt 4 ‖ỹt+1 − yt‖2
+ (1 + ηtµλ 4 ) 4ηtλ µ ‖∇yf(xt, yt)− wt‖2 + (1 + 4 ηtµλ )η2t γ 2κ2‖vt‖2.
(48)
Since 0 < ηt ≤ 1, 0 < λ ≤ 16L̃ and L̃ ≥ L22 ≥ µ, we have λ ≤ 1 6L̃ ≤ 16µ and ηt ≤ 1 ≤ 1 6µλ . Then we obtain
(1 + ηtµλ 4 )(1− ηtµλ 2 ) = 1− ηtµλ 2 + ηtµλ 4 − η
2 t µ 2λ2
8 ≤ 1− ηtµλ 4 ,
−(1 + ηtµλ 4 ) 3ηt 4 ≤ −3ηt 4 ,
(1 + ηtµλ 4 ) 4ηtλ µ ≤ (1 + 1 24 ) 4ηtλ µ = 25ηtλ 6µ ,
(1 + 4
ηtµλ )γ2κ2η2t = γ 2κ2η2t + 4γ2κ2ηt µλ ≤ γ 2κ2ηt 6µλ + 4γ2κ2ηt µλ = 25γ2κ2ηt 6µλ . (49)
Thus we have
‖yt+1 − y∗(xt+1)‖2 ≤ (1− ηtµλ
4 )‖yt − y∗(xt)‖2 − 3ηt 4 ‖ỹt+1 − yt‖2
+ 25ηtλ
6µ ‖∇yf(xt, yt)− wt‖2 + 25γ2κ2ηt 6µλ ‖vt‖2. (50)
A.1 CONVERGENCE ANALYSIS OF RGDA AND RSGDA ALGORITHMS
In the subsection, we study the convergence properties of deterministic RGDA and stochastic RSGDA algorithms, respectively. For notational simplicity, let L̃ = max(1, L11, L12, L21, L22). Theorem 4. Suppose the sequence {xt, yt}Tt=1 is generated from Algorithm 1 by using deterministic gradients. Given η = ηt for all t ≥ 1, 0 < η ≤ min(1, 12γL ), 0 < λ ≤ 1 6L̃ and 0 < γ ≤ µλ 10L̃κ
, we have
1
T T∑ t=1 [ L̃‖yt − y∗(xt)‖+ ‖gradΦ(xt)‖ ] ≤
2 √
Φ(x1)− Φ∗√ γηT . (51)
Proof. According to Lemma 6, we have
‖yt+1 − y∗(xt+1)‖2 ≤ (1− ηtµλ
4 )‖yt − y∗(xt)‖2 − 3ηt 4 ‖ỹt+1 − yt‖2 + 25ηtλ 6µ ‖∇yf(xt, yt)− wt‖2
+ 25γ2κ2ηt
6µλ ‖vt‖2. (52)
We first define a Lyapunov function Λt, for any t ≥ 1
Λt = Φ(xt) + 6γL̃2
λµ ‖yt − y∗(xt)‖2. (53)
According to Lemma 5, we have
Λt+1 − Λt = Φ(xt+1)− Φ(xt) + 6γL̃2
λµ
( ‖yt+1 − y∗(xt+1)‖2 − ‖yt − y∗(xt)‖2 ) ≤ γηtL12‖yt − y∗(xt)‖2 + γηt‖gradxf(xt, yt)− vt‖2 −
γηt 2 ‖gradΦ(xt)‖2 − γηt 4 ‖vt‖2
+ 6γL̃2
λµ
( − µληt
4 ‖yt − y∗(xt)‖2 − 3ηt 4 ‖ỹt+1 − yt‖2 + 25ληt 6µ ‖∇yf(xt, yt)− wt‖2
+ 25γ2κ2ηt
6µλ ‖vt‖2 ) ≤ − L̃
2γηt 2 ‖yt − y∗(xt)‖2 − γηt 2 ‖gradΦ(xt)‖2 − 9γL̃2ηt 2λµ ‖ỹt+1 − yt‖2
− (1
4 − 25κ
2L̃2γ2 µ2λ2 ) γηt‖vt‖2
≤ − L̃ 2γηt 2 ‖yt − y∗(xt)‖2 − γηt 2 ‖gradΦ(xt)‖2, (54)
where the first inequality holds by the inequality (52); the second last inequality is due to L̃ = max(1, L11, L12, L21, L22) and vt = gradxf(xt, yt), wt = ∇yf(xt, yt), and the last inequality is due to 0 < γ ≤ µλ
10L̃κ . Thus, we obtain
L̃2γηt 2 ‖yt − y∗(xt)‖2 + γηt 2 ‖gradΦ(xt)‖2 ≤ Λt − Λt+1. (55)
Since the initial solution satisfies y1 = y∗(x1) = arg maxy∈Y f(x1, y), we have
Λ1 = Φ(x1) + 6γL̃2
λµ ‖y1 − y∗(x1)‖2 = Φ(x1). (56)
Taking average over t = 1, 2, · · · , T on both sides of the inequality (55), we have
1
T T∑ t=1 [ L̃2ηt 2 ‖yt − y∗(xt)‖2 + ηt 2 ‖gradΦ(xt)‖2 ] ≤ Λ1 − ΛT+1 γT ≤ Φ(x1)− Φ ∗ γT , (57)
where the last equality is due to the above equality (56) and Assumption 4. Let η = η1 = · · · = ηT , we have
1
T T∑ t=1 [ L̃2‖yt − y∗(xt)‖2 + ‖gradΦ(xt)‖2 ] ≤ 2(Φ(x1)− Φ ∗) γηT . (58)
According to Jensen’s inequality, we have
1
T T∑ t=1 [ L̃‖yt − y∗(xt)‖+ ‖gradΦ(xt)‖ ] ≤ ( 2 T T∑ t=1 [ L̃2‖yt − y∗(xt)‖2 + ‖gradΦ(xt)‖2 )1/2 ≤ (
4(Φ(x1)− Φ∗) γηT
)1/2 = 2 √
Φ(x1)− Φ∗√ γηT . (59)
Theorem 5. Suppose the sequence {xt, yt}Tt=1 is generated from Algorithm 1 by using stochastic gradients. Given η = ηt for all t ≥ 1, 0 < η ≤ min(1, 12γL ), 0 < λ ≤ 1 6L̃ and 0 < γ ≤ µλ 10L̃κ
, we have
1
T T∑ t=1 E [ L̃‖yt − y∗(xt)‖+ ‖gradΦ(xt)‖ ] ≤
2 √
Φ(x1)− Φ∗√ γηT + √ 2σ√ B + 5 √ 2L̃σ√ Bµ . (60)
Proof. According to Lemma 6, we have
‖yt+1 − y∗(xt+1)‖2 ≤ (1− ηtµλ
4 )‖yt − y∗(xt)‖2 − 3ηt 4 ‖ỹt+1 − yt‖2 + 25ηtλ 6µ ‖∇yf(xt, yt)− wt‖2
+ 25γ2κ2ηt
6µλ ‖vt‖2. (61)
We first define a Lyapunov function Θt, for any t ≥ 1
Θt = E [ Φ(xt) + 6γL̃2
λµ ‖yt − y∗(xt)‖2
] . (62)
By Assumption 5, we have
E‖gradxf(xt, yt)− vt‖2 = E‖gradxf(xt, yt)− 1
B B∑ i=1 gradxf(xt, yt; ξ i t)‖2 ≤ σ2 B , (63)
E‖∇yf(xt, yt)− wt‖2 = E‖∇yf(xt, yt)− 1
B B∑ i=1 ∇yf(xt, yt; ξit)‖2 ≤ σ2 B . (64)
According to Lemma 5, we have
Θt+1 −Θt = E[Φ(xt+1)]− E[Φ(xt)] + 6γL̃2
λµ
( E‖yt+1 − y∗(xt+1)‖2 − E‖yt − y∗(xt)‖2 ) ≤ γηtL12E‖yt − y∗(xt)‖2 + γηtE‖gradxf(xt, yt)− vt‖2 −
γηt 2 E‖gradΦ(xt)‖2 − γηt 4 ‖vt‖2
+ 6γL̃2
λµ
( − µληt
4 E‖yt − y∗(xt)‖2 − 3ηt 4 E‖ỹt+1 − yt‖2 + 25ληt 6µ E‖∇yf(xt, yt)− wt‖2
+ 25γ2κ2ηt
6µλ ‖vt‖2 ) ≤ − L̃
2γηt 2 E‖yt − y∗(xt)‖2 − γηt 2 E‖gradΦ(xt)‖2 − 9γL̃2ηt 2λµ E‖ỹt+1 − yt‖2
− (1
4 − 25κ
2L̃2γ2 µ2λ2 ) γηt‖vt‖2 + γηtE‖gradxf(xt, yt)− vt‖2 + 25L̃2γηt µ2 E‖∇yf(xt, yt)− wt‖2
≤ − L̃ 2γηt 2 E‖yt − y∗(xt)‖2 − γηt 2 E‖gradΦ(xt)‖2 + γηtσ 2 B + 25L̃2γηtσ 2 Bµ2 , (65)
where the first inequality holds by the inequality (61); the second last inequality is due to L̃ = max(1, L11, L12, L21, L22), and the last inequality is due to 0 < γ ≤ µλ10L̃κ and Assumption 5. Thus, we obtain
L̃2γηt 2 E‖yt − y∗(xt)‖2 + γηt 2 E‖gradΦ(xt)‖2 ≤ Θt −Θt+1 + γηtσ 2 B + 25L̃2γηtσ 2 Bµ2 . (66)
Since the initial solution satisfies y1 = y∗(x1) = arg maxy∈Y f(x1, y), we have
Θ1 = Φ(x1) + 6γL̃2
λµ ‖y1 − y∗(x1)‖2 = Φ(x1). (67)
Taking average over t = 1, 2, · · · , T on both sides of the inequality (66), we have
1
T T∑ t=1 E [ L̃2ηt 2 ‖yt − y∗(xt)‖2 + ηt 2 ‖gradΦ(xt)‖2 ] ≤ Θt −Θt+1 γT + 1 T T∑ t=1 ηtσ 2 B + 1 T T∑ t=1 25L̃2ηtσ 2 Bµ2
= Φ(x1)− Φ∗
γT +
1
T T∑ t=1 ηtσ 2 B + 1 T T∑ t=1 25L̃2ηtσ 2 Bµ2 ,
(68)
where the last equality is due to the above equality (67). Let η = η1 = · · · = ηT , we have
1
T T∑ t=1 E [ L̃2‖yt − y∗(xt)‖2 + ‖gradΦ(xt)‖2 ] ≤ 2(Φ(x1)− Φ ∗) γηT + σ2 B + 25L̃2σ2 Bµ2 . (69)
According to Jensen’s inequality, we have
1
T T∑ t=1 E [ L̃‖yt − y∗(xt)‖+ ‖gradΦ(xt)‖ ] ≤ ( 2 T T∑ t=1 E [ L̃2‖yt − y∗(xt)‖2 + ‖gradΦ(xt)‖2 )1/2 ≤ 4(Φ(x1)− Φ ∗)
γηT +
2σ2
B +
50L̃2σ2 Bµ2 )1/2
≤ 2 √
Φ(x1)− Φ∗√ γηT + √ 2σ√ B + 5 √ 2L̃σ√ Bµ , (70)
where the last inequality is due to (a1 + a2 + a3)1/2 ≤ a1/21 + a 1/2 2 + a 1/2 3 for all a1, a2, a3 > 0.
A.2 CONVERGENCE ANALYSIS OF THE MVR-RSGDA ALGORITHM
In the subsection, we study the convergence properties of the MVR-RSGDA algorithm. For notational simplicity, let L̃ = max(L11, L12, L21, L22, 1).
Lemma 7. Suppose the stochastic gradients vt and wt is generated from Algorithm 2, given 0 < αt+1 ≤ 1 and 0 < βt+1 ≤ 1, we have
E‖gradxf(xt+1, yt+1)− vt+1‖2 ≤ (1− αt+1)2E‖gradxf(xt, yt)− vt‖2 + 4(1− αt+1)2L211γ2η2t ‖vt‖2
+ 4(1− αt+1)2L212η2t ‖ỹt+1 − yt‖2 + 2α2t+1σ 2
B . (71)
E‖∇yf(xt+1, yt+1)− wt+1‖2 ≤ (1− βt+1)2E‖∇yf(xt, yt)− wt‖2 + 4(1− βt+1)2L221γ2η2t ‖vt‖2
+ 4(1− βt+1)2L222η2t ‖ỹt+1 − yt‖2 + 2β2t+1σ 2
B . (72)
Proof. We first prove the inequality (71). According to the definition of vt in Algorithm 2, we have
vt+1 − T xt+1xt vt = −αt+1T xt+1 xt vt + (1− αt+1) ( gradxfBt+1(xt+1, yt+1)− T xt+1xt gradxfBt+1(xt, yt) ) + αt+1gradxfBt+1(xt+1, yt+1). (73)
Then we have
E‖gradxf(xt+1, yt+1)− vt+1‖2 (74) = E‖gradxf(xt+1, yt+1)− T xt+1xt vt − (vt+1 − T xt+1 xt vt)‖ 2
= E‖gradxf(xt+1, yt+1)− T xt+1xt vt + αt+1T xt+1 xt vt − αt+1gradxfBt+1(xt+1, yt+1) − (1− αt+1) ( gradxfBt+1(xt+1, yt+1)− T xt+1xt gradxfBt+1(xt, yt) ) ‖2
= E‖(1− αt+1)T xt+1xt (gradxf(xt, yt)− vt) + (1− αt+1) ( gradxf(xt+1, yt+1)− T xt+1xt gradxf(xt, yt)
− gradxfBt+1(xt+1, yt+1) + T xt+1xt gradxfBt+1(xt, yt) )
+ αt+1 ( gradxf(xt+1, yt+1)− gradxfBt+1(xt+1, yt+1) ) ‖2
= (1− αt+1)2E‖gradxf(xt, yt)− vt‖2 + α2t+1E‖gradxf(xt+1, yt+1)− gradxfBt+1(xt+1, yt+1)‖2
+ (1− αt+1)2E‖gradxf(xt+1, yt+1)− T xt+1xt gradxf(xt, yt)− gradxfBt+1(xt+1, yt+1) + T xt+1xt gradxfBt+1(xt, yt)‖ 2 + 2αt+1(1− αt+1) 〈 gradxf(xt+1, yt+1)− T xt+1xt gradxf(xt, yt)
− gradxfBt+1(xt+1, yt+1) + T xt+1xt gradxfBt+1(xt, yt), gradxf(xt+1, yt+1)− gradxfBt+1(xt+1, yt+1) 〉
≤ (1− αt+1)2E‖gradxf(xt, yt)− vt‖2 + 2α2t+1E‖gradxf(xt+1, yt+1)− gradxfBt+1(xt+1, yt+1)‖2
+ 2(1− αt+1)2E‖gradxf(xt+1, yt+1)− T xt+1xt gradxf(xt, yt)− gradxfBt+1(xt+1, yt+1) + T xt+1xt gradxfBt+1(xt, yt)‖ 2
≤ (1− αt+1)2E‖gradxf(xt, yt)− vt‖2 + 2α2t+1σ 2
B
+ 2(1− αt+1)2 E‖gradxfBt+1(xt+1, yt+1)− T xt+1xt gradxfBt+1(xt, yt)‖ 2︸ ︷︷ ︸
=T1
,
where the fourth equality follows by E[gradxfBt+1(xt+1, yt+1)] = gradxf(xt+1, yt+1) and E[gradxfBt+1(xt+1, yt+1) − gradxfBt+1(xt, yt)] = gradxf(xt+1, yt+1) − gradxf(xt, yt); the first inequality holds by Young’s inequality; the last inequality is due to the equality E‖ζ − E[ζ]‖2 = E‖ζ‖2 − ‖E[ζ]‖2 and Assumption 5.
Next, we consider an upper bound of the above term T1 as follows: T1 = E ∥∥gradxfBt+1(xt+1, yt+1)− T xt+1xt gradxfBt+1(xt, yt)∥∥2 (75)
= E ∥∥gradxfBt+1(xt+1, yt+1)− T xt+1xt gradxf(xt, yt+1; ξt+1) + T xt+1xt gradxf(xt, yt+1; ξt+1) − T xt+1xt gradxfBt+1(xt, yt)
∥∥2 ≤ 2E
∥∥gradxfBt+1(xt+1, yt+1)− T xt+1xt gradxf(xt, yt+1; ξt+1)‖2 + 2E‖gradxf(xt, yt+1; ξt+1)− gradxfBt+1(xt, yt)
∥∥2 ≤ 2L211γ2η2t ‖vt‖2 + 2L212‖yt+1 − yt‖2
= 2L211γ 2η2t ‖vt‖2 + 2L212η2t ‖ỹt+1 − yt‖2, (76)
where the last inequality is due to Assumption 1. Thus, we have
E‖gradxf(xt+1, yt+1)− vt+1‖2 ≤ (1− αt+1)2E‖gradxf(xt, yt)− vt‖2 + 4(1− αt+1)2L211γ2η2t ‖vt‖2
+ 4(1− αt+1)2L212η2t ‖ỹt+1 − yt‖2 + 2α2t+1σ 2
B . (77)
We apply a similar analysis to prove the above inequality (72). We obtain
E‖∇yf(xt+1, yt+1)− wt+1‖2 ≤ (1− βt+1)2E‖∇yf(xt, yt)− wt‖2 + 4(1− βt+1)2L221γ2η2t ‖vt‖2
+ 4(1− βt+1)2L222η2t ‖ỹt+1 − yt‖2 + 2β2t+1σ 2
B . (78)
Theorem 6. Suppose the sequence {xt, yt}Tt=1 is generated from Algorithm 2. Given y1 = y∗(x1), c1 ≥ 23b3 + 2λµ, c2 ≥ 2 3b3 + 50λL̃2 µ , b > 0, m ≥ max ( 2, (c̃b)3 ) , 0 < γ ≤ µλ 2κL̃ √ 25+4µλ and 0 < λ ≤ 1 6L̃ , we have
1
T T∑ t=1 E [ ‖gradΦ(xt)‖+ L̃‖yt − y∗(xt)‖ ] ≤ √ 2M ′m1/6 T 1/2 + √ 2M ′ T 1/3 , (79)
where c̃ = max(2γL, c1, c2, 1) and M ′ = 2(Φ(x1)−Φ∗) γb + 2σ2 λµη0bB + 2(c21+c 2 2)σ 2b2 λµB ln(m+ T ).
Proof. Since ηt is decreasing and m ≥ b3, we have ηt ≤ η0 = bm1/3 ≤ 1. Similarly, due to m ≥ (2γLb)3, we have ηt ≤ η0 = bm1/3 ≤ 1 2γL . Due to 0 < ηt ≤ 1 andm ≥ max ( (c1b) 3, (c2b) 3 ) , we have αt+1 = c1η2t ≤ c1ηt ≤ c1bm1/3 ≤ 1 and βt+1 = c2η 2 t ≤ c2ηt ≤ c2bm1/3 ≤ 1. According to Lemma 7, we have 1 ηt E‖gradxf(xt+1, yt+1)− vt+1‖2 − 1 ηt−1 E‖gradxf(xt, yt)− vt‖2 (80)
≤ ( (1− αt+1)2
ηt − 1 ηt−1
) E‖gradxf(xt, yt)− vt‖2 + 4(1− αt+1)2L211γ2ηt‖vt‖2
+ 4(1− αt+1)2L212ηt‖ỹt+1 − yt‖2 + 2α2t+1σ 2
ηtB ≤ (1− αt+1
ηt − 1 ηt−1
) E‖gradxf(xt, yt)− vt‖2 + 4L211γ2ηt‖vt‖2 + 4L212ηt‖ỹt+1 − yt‖2 + 2α2t+1σ 2
ηtB = ( 1 ηt − 1 ηt−1 − c1ηt ) E‖gradxf(xt, yt)− vt‖2 + 4L211γ2ηt‖vt‖2 + 4L212ηt‖ỹt+1 − yt‖2 + 2α2t+1σ 2 ηtB ,
where the second inequality is due to 0 < αt+1 ≤ 1. By a similar way, we also obtain 1 ηt E‖∇yf(xt+1, yt+1)− wt+1‖2 − 1 ηt−1 E‖∇yf(xt, yt)− wt‖2 (81)
≤ ( 1 ηt − 1 ηt−1 − c2ηt ) E‖∇yf(xt, yt)− wt‖2 + 4L221γ2ηt‖vt‖2 + 4L222ηt‖ỹt+1 − yt‖2 + 2β2t+1σ 2 ηtB .
By ηt = b(m+t)1/3 , we have
1 ηt − 1 ηt−1 = 1 b
( (m+ t) 1 3 − (m+ t− 1) 13 ) ≤ 1
3b(m+ t− 1)2/3 ≤ 1 3b ( m/2 + t )2/3 ≤ 2 2/3
3b(m+ t)2/3 =
22/3 3b3 b2 (m/2 + t)2/3 = 22/3 3b3 η2t ≤ 2 3b3 ηt, (82)
where the first inequality holds by the concavity of function f(x) = x1/3, i.e., (x + y)1/3 ≤ x1/3 + y
3x2/3 ; the second inequality is due to m ≥ 2, and the last inequality is due to 0 < ηt ≤ 1.
Let c1 ≥ 23b3 + 2λµ, we have
1 ηt E‖gradxf(xt+1, yt+1)− vt+1‖2 − 1 ηt−1 E‖gradxf(xt, yt)− vt‖2 (83)
≤ −2λµηtE‖gradxf(xt, yt)− vt‖2 + 4L211γ2ηt‖vt‖2 + 4L212ηt‖ỹt+1 − yt‖2 + 2α2t+1σ 2
ηtB .
Let c2 ≥ 23b3 + 50λL̃2 µ , we have
1 ηt E‖∇yf(xt+1, yt+1)− wt+1‖2 − 1 ηt−1 E‖∇yf(xt, yt)− wt‖2 (84)
≤ −50λL̃ 2
µ ηtE‖∇yf(xt, yt)− wt‖2 + 4L221γ2ηt‖vt‖2 + 4L222ηt‖ỹt+1 − yt‖2 +
2β2t+1σ 2
ηtB .
According to Lemma 6, we have
‖yt+1 − y∗(xt+1)‖2 − ‖yt − y∗(xt)‖2 ≤ − ηtµλ
4 ‖yt − y∗(xt)‖2 − 3ηt 4 ‖ỹt+1 − yt‖2
+ 25ληt
6µ ‖∇yf(xt, yt)− wt‖2 + 25γ2κ2ηt 6µλ ‖vt‖2.
(85)
Next, we define a Lyapunov function Ωt, for any t ≥ 1
Ωt = E [ Φ(xt) ] + γ
2λµ ( 1 ηt−1 E‖gradxf(xt, yt)− vt‖2 + 1 ηt−1 E‖∇yf(xt, yt)− wt‖2 ) + 6γL̃2
λµ E‖yt − y∗(xt)‖2. (86)
Then we have
Ωt+1 − Ωt = E[Φ(xt+1)]− E[Φ(xt)] + 6γL̃2
λµ
( E‖yt+1 − y∗(xt+1)‖2 − E‖yt − y∗(xt)‖2 ) + γ
2λµ ( 1 ηt E‖gradxf(xt+1, yt+1)− vt+1‖2 − 1 ηt−1 E‖gradxf(xt, yt)− vt‖2
+ 1
ηt E‖∇yf(xt+1, yt+1)− wt+1‖2 −
1
ηt−1 E‖∇yf(xt, yt)− wt‖2 ) ≤ L12γηtE‖yt − y∗(xt)‖2 + γηtE‖gradxf(xt, yt)− vt‖2 −
γηt 2 E‖gradΦ(xt)‖2 − γηt 4 ‖vt‖2
+ 6γL̃2
λµ
( − µληt
4 E‖yt − y∗(xt)‖2 − 3ηt 4 E‖ỹt+1 − yt‖2 + 25ληt 6µ E‖∇yf(xt, yt)− wt‖2 + 25γ2κ2ηt 6µλ
‖vt‖2 )
+ γ
2λµ
( − 2λµηtE‖gradxf(xt, yt)− vt‖2 + 4L211γ2ηt‖vt‖2 + 4L212ηtE‖ỹt+1 − yt‖2 + 2α2t+1σ 2
ηtB
− 50λL̃ 2
µ ηtE‖∇yf(xt, yt)− wt‖2 + 4L221γ2ηt‖vt‖2 + 4L222ηtE‖ỹt+1 − yt‖2 +
2β2t+1σ 2
ηtB ) ≤ −γL̃
2ηt 2 E‖yt − y∗(xt)‖2 − γηt 2 E‖gradΦ(xt)‖2 − γL̃2ηt 2λµ
E‖ỹt+1 − yt‖2 − (γ
4 − 25γ
3κ2L̃2
µ2λ2 − 4γ
3L̃2
µλ
) ηt‖vt‖2
+ γα2t+1σ 2 λµηtB + γβ2t+1σ 2 λµηtB
≤ −γL̃ 2ηt 2 E‖yt − y∗(xt)‖2 − γηt 2 E‖gradΦ(xt)‖2 + γα2t+1σ 2 λµηtB + γβ2t+1σ 2 λµηtB , (87)
where the first inequality holds by Lemmas 5 and the above inequalities (83), (84) and (85); the second inequality is due to L̃ = max(1, L11, L12, L21, L22); the last inequality is due to 0 ≤ γ ≤
µλ
2κL̃ √ 25+4µλ and κ ≥ 1.
According to the above inequality (87), we have
γηt 2
( E‖gradΦ(xt)‖2 + L̃2E‖yt − y∗(xt)‖2 ) ≤ Ωt − Ωt+1 + γα2t+1σ 2
λµηtB + γβ2t+1σ 2 λµηtB . (88)
Taking average over t = 1, 2, · · · , T on both sides of the inequality (88), we have
1
T T∑ t=1 Eηt ( ‖gradΦ(xt)‖2 + L̃2‖yt − y∗(xt)‖2 ) ≤ T∑ t=1 2(Ωt − Ωt+1) γT + 1 T T∑ t=1 (2α2t+1σ2 λµηtB + 2β2t+1σ 2 λµηtB ) .
Since the initial solution satisfies y1 = y∗(x1) = arg maxy∈Y f(x1, y), we have
Ω1 = Φ(x1) + 6γL̃2
λµ ‖y1 − y∗(x1)‖2 +
γ
2λµ ( 1 η0 ‖gradxf(x1, y1)− v1‖2 + 1 η0 ‖∇yf(x1, y1)− w1‖2 ) = Φ(x1) + γ
2λµ ( 1 η0 ‖gradxf(x1, y1)− gradxfB1(x1, y1)‖2 + 1 η0 ‖∇yf(x1, y1)−∇yfB1(x1, y1)‖2 ) ≤ Φ(x1) + γσ2
λµη0B , (89)
where the last inequality holds by Assumption 5.
Table 3: Benchmark Datasets Used in Experiments
datasets #samples #dimension #classes MNIST 60,000 28×28 10
CIFAR-10 50,000 32×32×3 10 CIFAR-100 50,000 32×32×3 100
SVHN 73,257 32×32×3 10 Fashion-MNIST 60,000 28×28 10
STL-10 5,000 32×32×3 10 Consider ηt is decreasing, i.e., η−1T ≥ η −1 t for any 0 ≤ t ≤ T , we have
1
T T∑ t=1 E ( ‖gradΦ(xt)‖2 + L̃2‖yt − y∗(xt)‖2 ) (90)
≤ T∑ t=1 2(Ωt − Ωt+1) TγηT + 1 TηT T∑ t=1 (2α2t+1σ2 λµηtB + 2β2t+1σ 2 λµηtB ) ≤ 1 TηT (2Φ(x1) γ + 2σ2 λµη0B − 2Φ ∗ γ ) + 1 TηT T∑ t=1 (2α2t+1σ2 λµηtB + 2β2t+1σ 2 λµηtB
) =
2(Φ(x1)− Φ∗) TγηT + 2σ2 Tλµη0ηTB + 2(c21 + c 2 2)σ 2 TηTλµB T∑ t=1 η3t
≤ 2(Φ(x1)− Φ ∗)
TγηT +
2σ2
Tλµη0ηTB +
2(c21 + c 2 2)σ 2
TηTλµB ∫ T 1 b3 m+ t dt
≤ 2(Φ(x1)− Φ ∗)
TγηT +
2σ2
Tλµη0ηTB +
2(c21 + c 2 2)σ 2b3
TηTλµB ln(m+ T )
= 2(Φ(x1)− Φ∗)
Tγb (m+ T )1/3 +
2σ2
Tλµη0bB (m+ T )1/3 +
2(c21 + c 2 2)σ 2b2
TλµB ln(m+ T )(m+ T )1/3,
where the third inequality holds by ∑T t=1 η 3 t ≤ ∫ T 1 η3t dt. Let M ′ = 2(Φ(x1)−Φ ∗) γb + 2σ2 λµη0bB + 2(c21+c 2 2)σ 2b2
λµB ln(m+ T ), we rewrite the above inequality as follows:
1
T T∑ t=1 E ( ‖gradΦ(xt)‖2 + L̃2‖yt − y∗(xt)‖2 ) ≤ M ′ T (m+ T )1/3. (91)
According to Jensen’s inequality, we have
1
T T∑ t=1 E ( ‖gradΦ(xt)‖+ L̃‖yt − y∗(xt)‖ ) ≤ ( 2 T T∑ t=1 E ( ‖gradΦ(xt)‖2 + L̃2‖yt − y∗(xt)‖2 ))1/2 ≤ √ 2M ′
T 1/2 (m+ T )1/6 ≤
√ 2M ′m1/6
T 1/2 +
√ 2M ′
T 1/3 ,
(92)
where the last inequality is due to (a1 + a2)1/6 ≤ a1/61 + a 1/6 2 for all a1, a2 > 0.

heading: B ADDITIONAL EXPERIMENTAL RESULTS
text: In this section, we provide additional experimental results on SVHN, FashionMNIST and STL-10 datasets, given in Table 3. The training loss and attack loss under uniform attack is shown in Fig 4. The test accuracy with natural images and uniform attack is shown in Tab. 4. From these results, our methods are robust to the uniform attack in training DNNs.

Review summaries:
In this paper, the authors present and analyze a class of gradient-descent algorithms for solving min-max problems when the first (minimization) variable is constrained to live on a Riemaniann manifold. In the case when i) a retraction and an isometric transport are available on the manifold; and ii) the objective is strongly convex and smooth in the second variable, the authors show convergence rates. Experiments are performed with the setting of minimizing losses of neural nets whose weights are constrained to live in the Stiefeld manifold while an attacker of small norm perturbs the input.