Gradient Descent Ascent for Min-Max Problems on Riemannian Manifolds
Authors: Feihu Huang
Shangqian Gao
Heng Huang
Venue:  (2021)
Keywords: Min-Max Optimization
Riemannian Manifold
Robust Training

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(\kappa^2\epsilon^{-2})$ for finding an $\epsilon$-stationary point of the nonconvex strongly-concave minimax problems, where $\kappa$ 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(\kappa^4\epsilon^{-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 $\tilde{O}(\kappa^{4}\epsilon^{-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.

Under review as a conference paper at ICLR 2021
GRADIENT DESCENT ASCENT FOR MIN-MAX PROB- LEMS ON RIEMANNIAN MANIFOLDS
Anonymous authors Paper under double-blind review
ABSTRACT
In the paper, we study a class of useful non-convex minimax optimization prob- lems 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 com- plexity of O(k2E=3 for finding e-stationary point of the nonconvex strongly- concave minimax problems, where и denotes the condition number. At the same time, introduce Riemannian stochastic gradient descent ascent (RSGDA) al- gorithm for the stochastic minimax optimization. In the theoretical analysis, we prove that the RSGDA can achieve sample complexity of O(k*E=4). To further reduce the sample complexity, we propose a novel momentum variance-reduced Riemannian stochastic gradient descent ascent IMVR-RSGDA algorithm based a new momentum variance-reduced technique of STORM. We prove that the MVR-RSGDA algorithm achieves a lower sample complexity of ((Kte=)) with- out 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.
INTRODUCTION
In the paper, we study a class of useful non-convex minimax (akka. min-max) problems on the Riemannian manifold M with the definition as:
min max f(z y), #EM yEY
where the function [(x u) is j-strrogly concave in but possibly nonconvex in x. Here y C Rd convex and closed set. f(:,y) -M- + lK for all y ) is smooth but possibly nonconvex real-valued function on manifold M, and f(z.-) y + E for all x E .M smooth and (strongly)- concave real-valued function. this paper, we mainly focus on the stochastic minimax optimization problem far y) := BgwDif (x. y: E)). where is a random variable that follows an unknown distri- bution D. In fact, the problem I 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. How- ever, 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 robust- ness of DNNs under the adversarial example attacks. To be more specific, given training data R represent the features and label of sam-
D {E (a,, b,)) where a; E IRd and ple & respectively. Each data sample a; can be corrupted by universal small perturbation vector y generate an adversarial attack sample a; + y, in "Moosavi-Dezfood
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 max BEY E(h(a, + v),)

---

Under review as a conference paper at ICLR 2021
where y E I denotes universal perturbation, and x: is the weight of the neural network; h(::z:) the the deep neural network parameterized by 2; and f(-) is the loss function. Here the constraint D' = {y |yl| S }} indicates that the poisoned samples should not be too different from the original ones.
Recently, the orthonormality weights of DNNs has gained much interest and has been found to be useful across different tasks such as person re-identificattion (Sun et al.) (017) and image classifi- cation (Xie et al., 2017). In fact, the orthonormality constraints improve the performances of DNNs (Li et al., 2020, Bansal et al. (0018), and reduce overfitting to improve generalization (Cogswell 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 manifold M:
min max #EM yEy T
E(h(a; + v,,
(3)
When data are continuously coming, can rewrite the problem 3 follows:
min max [e[f(xr REM vEy
(4)
where f(x, = + y; b) with (a,
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 also widely applied in machine learning problems such as robust principal component analysis (PCA). To be more specific, given set of data samples (5:) the DRO over Riemannian manifold M can be written as the following minimax problem:
Th Σ
min max #EM PES
prl(x:
|lp
1 72
(5)
where p (PI.... Pn). S S= {p E R" Σー L. 0}. Here (x); 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. (016)). DNNs (Huang et al., 2018), structured low-rank matrix learning (Jawanpuria & Mishra 2018). among others. For example, the task of PCA can be cast Grassmann manifold.
.P))
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 (T) via using general retraction and vector transport. When the problem (T) is deterministic, we propose a new deterministic Riemannian gradient descent ascent algorithm. When the problem (T) is stochastic, we propose two efficient stochastic Riemannian gradient descent ascent algorithms. Our main contributions can be summarized as follows:
1) We propose novel Riemannian gradient descent ascent (RGDA) algorithm for the de- terministic minimax optimization problem (T). We prove that the RGDA has a sample complexity of O -2 for finding e-stationary point.
2) We also propose new Riemannian stochastic gradient descent ascent (RSGDA) algorithm for the stochastic minimax optimization. In the theoretical analysis, we prove that the SRGDA has sample complexity of O(Nae-1)
3) To further reduce the sample complexity, we introduce a novel momentum variance- reduced Riemannian stochastic gradient descent ascent on new momentum variance-reducet technique of STORM (Cutkosky & Orabona 2019). We prove the MVR-RSGDA achieves lower sample complexity of (k'²,-3) (please see Table Dp. which reaches near the best known sample complexity for its Euclidean counter- parts.
algorithm based
4) Extensive experimental results on the robust DNN training over Stiefel manifold demon- strate the efficiency of our proposed algorithms.
2

---

Under review as a conference paper at ICLR 2021
Table 1:
Convergence properties comparison of our algorithms for obtaining an e-stationary point
of the min-max optimization problem denotes the condition number of function f(z,
Problem
Algorithm
Learning Rate
Batch Size
Complexity 7(
Deterministic
RGDA
Constant
RSGDA
Constant
a(
Stochastic
MVR-RSGIA
Decrease
0(1)
((19/26-3)
MVR-RSGDA
Decrease
((k)
3(k-c=3)
2
RELATED WORKS
In this section, we briefly review the minimax optimization and Riemannian manifold optimization research works.
2.1
MINIMAX OPTIMIZATION
Minimax optimization recently has been widely applied in many machine learning problems such as adversarial training (Goodfellow et al. 2014 [iu al. (019), reinforcement learning (Zhang al.)
2019 2020), and distribution learning (Razaviyayn et al., 2020). At the same time, many efficient
min-max methods (Rafique et al., 20118 88] Lin et al., 2019; Nouiched et al. 2019; Thekumparampil
et al. 2019: Lin al.] 2020 Yang al. 2020 Ostrovski al. 2020 Y Yan et al. 2020 Xu al.,
2020a Luo et al. 2020) et 2020b] Bot & Böhm|[2020) Huang et al. 2020) have been proposed
for solving these minimax optimization problems. For example, "Thekumparampi et al. (2019) have proposed a class of efficient dual implicit accelerated gradient algorithms to solve smooth min-max optimization. [in et al. (2019) have proposed 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 al.] (2020b) have proposed a unified single- loop alternating gradient projection algorithm for (non)convex--non) (noo))ccavee 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 al. (2020) have proposed class of fast stochastic variance-reduced GDA algorithms to solve the stochastic minimax problems. More recently, |Huang et al. (2020) have presented class of new momentum based first-order and zeroth-orde descent ascent method for the nonconvex strongly concave minimax problems.
2.2 RIEMANNIAN MANIFOLD OPTIMIZATION
Riemannian manifold optimization methods have been widely applied in machine learning problems including dictionary learning (Sun 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-roduced methods to Ricmannian 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 al. 2018 Kasai et al. 2018 Zhou al.)
2019 Han & Gao. 2020a) have been proposed for non-convex optimization. Riemannian Adam-type algorithms (Ksai 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 & norm for vectors and spectral norm for matrices. (a, y) denotes the inner product of two vectors x and For function f(x. v). f(r, -) denotes function w.e.t the second variable with fixing x, and f(- y) denotes function w.r.f. the first variable with fixing y. Given convex closed set ) we define projection operation the set 3 as Py(vo)
arg minyey 1 lly (b)) if < Cb for some constant C >> O, and the notation Ô(-) hides
voll2. We denote logarithmic terms. I denotes the identity matrix with d dimension. The operation ④ denotes the
Whitney sum. Given B, [ for any I. 2 1, let V SB, (x. v) = Σ (f yr (1)
3

---

Under review as a conference paper at ICLR 2021
u
u
x
L
TV V
Rx (u)
x
M
M
(a) Retraction Rg
(b) Vector Transport T
Figure I: Illustration of manifold operations.(a) A vector u in T2 M is mapped to Rz(u) in M: (b) A vector in T.M is transported to M.MM by Tho (or Twt), where y Rz(u) and E T.M.
PRELIMINARIES
In this section, we first re-visit some basic information on the Riemannian manifold M. In general, the manifold M is endowed with a smooth inner product (:: ) T.M x TrM + R on tangent space T.M for every with the Riemannian metric. We first define a retraction Rs T.M + M mapping tangent space T,M onto M with local rigidity condition that preserves the gradients at æ M (please see Fig.1 (a)). The retraction Rg satisfies all of the following: 1) R.
M. The induced norm || || of tangent vector in T.M is associated
x, where E T.M;; 2) (V), 2)2 = u for T.M. In fact, exponential mapping Exp., is a special case of retraction R2 that locally approximates the exponential mapping Exp,, to the first order on the manifold.
Next, we define a vector transport T : TM TMOTM + TM (please see Fig.1 (b)) that satisfies all of the following 1) T has an associated retraction R. ie., for E M and w, u E M,M, Taw tangent vector at (w)); 2) Tou = v; 3) Ta + bw) u, v, w E TMM. Vector transport T20 or equivalently Tuv with along the retraction curve defined by direction u. Here we focus on the isometric vector transport TH, which satisfies (u, u)2 (TFu, Tyu), for all u, e E T.M.
T + bTaw for all a, b E (u) transports E T.M
Let Vf(z,)) v) = fx, 8). (x,(x,)) denote the gradient over the Euclidean space, and let gradf (z. y) = fIr y). (z. v))
(rojr,,((Vf.. v)) denote the Riemannian gradi- ent over tangent space T,M, where Projx (z) arg min x || | is projection operator. Based on the above definitions, we provide some standard assumptions about the problem (I). Although the problem (1) is non-convex, following (Von Neumann & Morgenstern) 2007). there exists local solution or stationary point (x* .y") satisfies the Nash Equilibrium, i.e.,
f(x" v) I f(x" ,y") S f(x,y"),
where x" X and y" E... Here X C M a neighbourhood around an optimal point x". Assumption 1. X is compact. Each component function f(x,y) y) is twice continuously differentiable in both I E X and y E y, and there exist constants L1n, T1z. Lz and Lozz, such that for every 21, E X and y, 21, 92 Y, we have
Igrad=f((x (I1,3:E) - T ff y: E)1l & Lnllulll
W (1 - grad y2i I| < Liellea 92ll.
vyf(22, V: Ell < L21 [e]l
IV (x. 811 V V y2i e S Lgg ll - -2ll.
where u E Tay M and R., (u).
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. the terms L11. L12 and Len implicitly contain the curvature information as in (Sato et al. 2019 Han & Gao, 2020a). Specifically, Assumption implies the partial Riemannian gradi- ent grad (. for all y E y is retraction L continuous as in (Han & Gao. 2020a) and the partial gradient Vyf(x, &) for all x E X is Lez-Lipschitz continuous as in (Lin al. 2019). Since [|grad, f g) frr, U2; Ell ||rojj, (x,,))
Assumption
2020b). Here.
4

---

Under review as a conference paper at ICLR 2021
Projt..M (w..(VVV.. (Vef(z, Σ (2.((2,)13)
(=f(z.32:)) L12l131 y2ll. we ob- grad__(aa U2: E)Il I Lıllyy - y2ll by the Iız-I.ipschitz continu- ous of vef(z,)E) for all x E X. Let the partial Riemannian gradient g for all y y be retraction L21 Lipschitz, i.e., of (21, T grad, v: S L21 ||ll- Since llgrad ( 9: 2 grad, (I2. v: = ||Projr, (Z), v: T2 Projy, (V (V, v: I) S (2 ys x) - v ys E)ll - L2i ||u||, we have L21 L21.
tain
For the deterministic problem, let f(z, y) instead of f(z, g) in Assumption 1. Since f(,, v) is strongly concave in E V, there exists a unique solution to the problem maxyey ((x,)) for any x. We define the function (x)) maxyey [zz y) and v² (x) arg maxyey [(I, y).
Assumption 2. The function (x) is retraction L-smooth. There exists a constant L > 0, for all X2 (u) with u T M,M, such that
L
(z) S (xx) + (grad(()), u) + [ullp.
(6)
Assumption 3. The objective function f1r, v) is p-strongly concave w.r.t y, i.e., any M
M |1 - y2ll? Vy y2 E y.
f(x v1) S f(x, (2) + ( y2). y1 y2)
2
Assumption 4. The function (xx) is bounded from below in .M, i.e., :0 = inf ((x)
Assumption 5. The variance of stochastic gradient is bounded, i.c., there exists constant > 0 such that for all æ, it follows Egllgrad, (z. y: E) (x. S of: There exists a constant such that for all y. follows EEg ff, vyf(z, S oz. We also define 22 max(01,02]
(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 al.) (020)) Assumption guarantees the feasibility of the
Assumption imposes the retraction smooth function ((x), as in Sato
problems, in (Lin et al. [2119] Luo et al. (2220). 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).
4
RIEMANIAN GRADIENT DESCENT ASCENT
In the section, we propose class of Riemannian gradient descent ascent algorithm to solve the deterministic and stochastic minimax optimization problem (L). respectively.
4.1 RGDA AND RSGDA ALGORITHMS
In this subsection, we propose an efficient Riemannian gradient descent ascent (RGDA) algorithm to solve the deterministic min-max problem T the same time, we propose a standard Riemannian stochastic gradient descent ascent (RSGDA) algorithm solve the stochastic min-max problem (.. Algorithm summarizes the algorithmic framework of our RGDA and RSGDA algorithms.
At the step 5 of Algorithm D apply the retraction operator to ensure the variable for all t > in the manifold M. At the step 6 of Algorithm I we use < n S to ensure the variable ye for all t 2 in the convex constraint y
Here we define reasonable metric to measure the convergence:
H4 (x=)) + Dllv, y" (x:)]l,
(10)
where I max(1, L11, L12, L21, L22), and the first term of He measures convergence of the iter- ation solutions {xx |T and the last term measures convergence of the iteration solutions {v, )
Since the function f(x, y) is strongly concave in y E V, there exists a unique solution y (x) to the problem max fxx,)) for any
M.. Thus, we apply the standard metric ||v: y (x,)) to measure convergence of the parameter y. Given y = y² (xz), we use the standard metric (xx, = Ilgrad, y (xx))]l to measure convergence of the parameter æ. Note that we use the coefficient f. to balance the scale of metrics of the variable and the variable
5

---

Under review as a conference paper at ICLR 2021
Algorithm RGDA and RSGDA Algorithms for Min-Max Optimization
Input: T, parameters {7, n mini-batch size B, and initial input #1 M. y E\:
2: for 1= 1,2...., 7 do
3: (RGDA) Compute deterministic gradients
Vt grad (It (fre We), Wi VyJ (1):))))))
4:
(RSGDA) Draw i.i.d. samples { then compute stochastic gradients
1
1
grad o (I)),
V ( Ve: El
(9)
B
B
5: Update: 2x+1 Rz, (-)))
6: Update: Dt+1 = Py(ye + Xure) and Vt+1 = Yt + (e ye):
7: end for
8: Output: and V/ chosen uniformly random from { Vo 1
Algorithm MVR-RSGDA Algorithm for Min-Max Optimization
1: Input: T. parameters {7, X, b, m, c1, 02) and initial input æı E M and y1 E Y;
2: Draw B i.idd samples B1 [() then compute ti grad, (I1,91) and w1
Vyfe, (Z1, V1);
3: for to
.......7 1,,,..., do
4: Compute 17 = (1)7333
5: Update: 1 Rz, U))
6: Update: Me+1 Py + Awa) and ytt! = Y1 + 7e(01+1 ve);
7: Compute 0:-1 cuTf and Br+1 c27
8:
Draw B i..d samples Bi-1 = (5+11ee then compute
U grad (Ie+1, Me+1 + 0141) [or gBad (ot v:)]
(12)
W++1 VyfBr4 (Iez1, M1+1) + (1 B(+1)( Vyt (F (e):
(13)
9:
end for
10: Output: and y/ chosen uniformly random from fae, TT
4.2
MVR-RSGDA ALGORITHM
this subsection, we propose novel momentum variance-reduced stochastic Riemannian gradient descent ascent (MVR-RSGDA algorithm to solve the stochastic min-max problem (T). which builds on the momentum based variance reduction technique STORM (Cutkosky & Orabona 2019).
Algorithm describes the algorithmic framework of MVR-RSGDA method.
In Algorithm 2
we use the momentum-bass variance-reduced technique of STORM to update stochastic Riemannian gradient t4:
U++1 0141 grad, S8, (FI-1, M(+1)
SGD
+ (1 04+1) (grad,, BB. (0441.9641) - T (grad,, (Ie, (t) Uz)
SPIDER
grad.SB... (Iras Mc+1)
0444 ) (v= grad g (8 (Ire, vc)),
(11)
where a++1 E (0, 1). When a++1 = 1, 82 will degenerate a vanilla stochastic Riemannian gradient;
When a++1 0. 2 will degenerate stochastic Riemannian gradient based reduced
technique of SPIDER (Nguyen et al.) 2017; Fang et al., 2018). Similarly, we use this momentum- based variance-reduced technique to estimate the stochastic gradient wt.

---

Under review as a conference paper at ICLR 2021
5 CONVERGENCE ANALYSIS
In this section, we study the convergence properties of our RGDA, RSGDA, and MVR-RSGEE al- gorithms under some mild conditions. For notational simplicity, let L = max(1, L11, L12, L21 Lzz and K = L21/u 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 4(x) = maxyEy f(z y) is re- traction G-Lipschitz, and the mapping or function y (x) arg maxyey (x, V) retraction k- Lipschitz. Given any T2, I2 = Rz (u) E X C M and u E M, we have:
(1g) -T2 gradd (x2)) S Gl|u||,
[1v)(x1) y (12))) S k||u|||
(14)
where G = = T1 and L21/1-
5.1 CONVERGENCE ANALYSIS OF BOTH THE RGDA AND RSGDA ALGORIHTM
In the subsection, we study the convergence properties of deterministic RGDA and stochastic RS- GDA algorithms. The related proofs of RGDA and RSGDA are provided Appendix A..] Theorem 1. Suppose the sequence {æ,, Ve VT is generated from Algorithm 7 by using deterministic
gradients. Given 1) Th for all 2 1, 0 < n < min(1, 24L). 0 X have
A and 0 Y
_ud.
6l
10LK'
1
glgadd [x)) + Lllye 8² (x:)]] S 2 1/11)11) x-
ΣV t=1
(15)
T
VMiT
Remark 1. Since 0 n S min(1, 27L and 0 <
10hn" have 0 m min( pd
nd
10Lx" 21
10L ) we have 177 ( The RGDA algorithm has convergence rate of (T7))) By Ti/z S e, i.e., [[Hcc] S e, we choose T 2 -2. In the deterministic RGDA Algorithm, need one sample to estimate the gradients Vt and Wi at each iteration, and need iterations. Thus, the RGDA reaches a sample complexity of T = O(k2c22) for finding an c- stationary point.
Let 177 = min( pd
Theorem 2. Suppose the sequence {Ie, Vt " is generated from Algorithm by using stochastic gradients. Given 1)- = for all t 2 1, 0 < n min(1, 21 0 X and 0 < <7S 10Lx' have
nd
we
T E [llgradd (x))) + Elyee (x+) < 1=1
2 201((11) - $
V20
5/2Lo
B +
(16)
T
VnnTT
VBμ
Remark 2. Since 0 < S min(1, 24L
1 and 0 <9S
10L.* we have 0 < my S min( nd
nd
10L." 21 Let
7y min( =Ad 10Lx ). we have = ( Let B = T. the RSGDA algorithm has convergence rate of O (z By T4 S,, i... E[H[]] S e, we choose T 2 =²2 In the stochastic RSGDA Algorithm, we need B samples to estimate the gradients and w: at each iteration, and need iterations. Thus, the RSGDA reaches a sample complexity of BT O(K²c-1) for finding an c-stationary point.
5.2 CONVERGENCE ANALYSIS OF THE MVR-RSGDA ALGORITHM
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 (It, yt )T is generated from Algorithm 2
Given = y (x1))
C 2 3/ + 2d C2 3 + 50Xi2 b O, 2 max (eb))). <7
nd and 2kIL
P
0 X 6L. we have
V2M'
Σ B[llgradd(::)1 i.llve - 3 (xx))l
(17)
T1/2
T1/3
where ē max(1, 02, T-) and M 2(0((z))) 76
20a B
2(c slee+c3)o03
In(m + T).
BA

---

Under review as a conference paper at ICLR 2021
RSGDA
RSGOA MVN-RSCDA
R5G04 MVR ASGDA
Miv RSGAA
Epochs
Epochs
Epochs
(a)
MNIST
(b) CIFAR-10
(c) CIFAR-100
Figure 2: Training loss of robust training DNNs with orthogonality regularization weights.
RSGDA MVVIRSSDAA
RSGDA
SGDR
SGDA
Loos
Attack
Rerations
Iterations
Iteration
(a) MNIST
(b) CIFAR-10
(c) CIFAR-100
Figure 3: Attack loss when using uniform attack on DNNs trained by SGDA, RSGDA and MVR- RSGDA.
Remark 3. Let ~o 2Aμ, 02 2. +
50AE?
A= 1 7= 2xt. 2xt. and 77 mi/5- Ir
0d
b
P
67.
is easy verified that 0 0 =p= 0 0(1) (K), O and
Noo = -..)). Without loss of generality, let m = O(x3), we have M' 0 have M' = (1²2 (T). Thus, the MVR-RSGDA algorithm has convergence & rate of ( ). By Tiys S, i.e. [[Hc]] S e, we choose T k3 3. In Algorithm 2 we require B samples estimate the stochastic gradients and we at each iteration, and need iterations.
B In))))
When B ==6
Thus, the MVR-RSGDA has sample complexity of BT ((K²E-3) for finding e-stationary point of the problem (7). Similarly, when B = the MVR-RSGDA algorithm has convergence rate of ( ((777)) and has a sample complexity of BT = (1:1122- for finding an e-stationary point.
Remark 4. the about theoretical analysis, we only assume the convexity of constraint set Y, while Lin 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 constraint set on parameter y, i.e..) Rd, our algorithms and theoretical results still work, while Lin et al, (2019 can't work.
EXPERIMENTS
In this section, we conduct the deep neural network (DNN) robust training over the Stiefel manifold St(r, {W E Radrr W W I,) evaluate the performance of our algorithms. In the experiment, we use MNIST, CIFAR-10, and CIFAR-100 datasets to train the model ( More exper- imental results on SVHN, STL10, and FashionMNIST datasets are provided the Appendix [ Considering the sample size is large in these datasets, we only compare the proposed stochastic al- gorithms (RSGDA and MVR-RSGDA) in the experiments. Here, we use the SGDA algorithm (Lin) al. 2019) baseline, which does not apply the orthogonal regularization in the DNN robust training.
6.1 EXPERIMENTAL SETTING
Given a deep neural network h(=;z) parameterized by x as shown in the above problem (2) the weights of 1-th layer is i, St(ni/n bo where St(ni mou)) is the Stiefel manifold of 1-th layer.
8

---

Under review as a conference paper at ICLR 2021
Table Test accuracy against nature images and uniform attack for MNIST, CIFAR-IO, and CIFAR- 100 datasets.
Methods
Eval. Against
MNIST
CIFAR-10
CITAR-100
Nat. Images 98.92%
62.87%
29.92%
RSGDA
Uniform Attack
98.58%
61.45%
31.14%
Nat. Images 99.15%
67.45%
32.92%
MVR-RSGDA
Uniform Attack
99.03%
68.56%
34.69%
Nat. Images 98.96%
76.75%
43.41 %
SGDA
Uniform Attack
98.59%
55.68%
27.81%
For the weights in dense layers, n/ Yut the number of inputs and outputs neurons. For the weights in convolution layers, ni, is the number of input channels, no is the product of the number of output channels and kernel sizes. Note that the trainable parameters from other components (e.g. batchnorm) are not in Stiefel manifold.
For both RSGDA and MVR-RSGDA algorithms, we set {7, }} to {1.0, 0.1}. We further set (b, m, CI, ) 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 0.05 and 0.03 for the MNIST dataset and CIFAR- 10/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 al. 2018) which is based on PyTorch (Paszke et 2019.
6.2 EXPERIMENTAL RESULTS
The training loss plots of the robust training problem in the above Eq. are shown in Fig. From the figure, we can see that AVRRRRSGDA enjoys a faster convergence speed compared to the baseline RSGDA. It's also clear that when the dataset becomes complicate (from MNIST to CIFAR- 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- Moossvv--Dezoooli et al. 2017 Chaubey et al.
2020), and the detail uniform attack objective is shown below:
T
min DEy TI
max (Nv,, + a.) - max (5 + a)), s.t. y {11yllo 5e} jzb,
where h, 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, sample mini-bate batch with 512 samples at each iteration. The optimization of the uniform permutation lasts for 1000 iterations for all settings. The attack loss 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 harder 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
CONCLUSION
In the paper, investigated class of useful min-max optimization problems 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 Ō(kte=3) without large batches, which reaches near the best known sample complexity for its Eu- clidean counterparts.
REFERENCES
Nitin Bansal, Xiaohan Chen, and Zhangyang Wang. Can gain more from orthogonality regular- izations in training deep networks? In Advances in Neural Information Processing Systems, pp. 4261-4274 2018.

---

Under review as a conference paper at ICLR 2021
Radu Ioan Bot and Axel Böhm. Alteraating proximal-gradient steps for (stochastic) nonconvex- concave minimax problems. arXiv preprint arXiv:2007.13605, 2020.
Ashutosh Chaubey, Nikhil Agrawal, Kavya Barnwal, Keerat K Guliani, and Pramod Mehta. Uni- versal adversarial perturbations: A survey. arXiv preprint arXiv:2005.0800 2020.
Robert S Chen, Brendan Lucier, Yaron Singer, and Vasilis Syrgkanis. Robust optimization for convex objectives. In Advances in Neural Information Processing Systems, pp. 4705-4714, 2017.
Michael Cogswell, Faruk Ahmed, Ross Girshick, Larry Zitnick, and Dhruv Batra. Reducing overfit- ting in deep networks by decorrelating representations. arXiv preprint arXiv:1511.000 160668 2015.
Ashok Cutkosky and Francesco Orabona. Momentum-baase variance reduction in non-convex sgd. In Advances in Neural Information Processing Systems, pp. 15210-15219, 2019.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex op-
timization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pp. 689-699, 2018.
Orizon Pereira Ferreira, LR Lucambio Pérez, and Sandor Z Németh. Singularities of monotone vector fields and an extragradient- algorithm. Journal of Global Optimization, 31(1):133- 151, 2005.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014.
Andi Han and Junbin Gao. Riemannian stochastic recursive momentum method for non-convex optimization. arXiv preprint arXiv:2008.0455 2020a.
Andi Han and Junbin Gao. Variance reduction for riemannian non-convex optimization with batch size adaptation. arXiv preprint 1ixXi::0077001944, 2020b.
Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-order momentum methods from mini minimax optimization. arXiv preprint arXiv:2008.081 081700 2020.
Lei Huang, Xianglong Liu, Bo Lang, Adams Wei Yu, Yongliang Wang, and Bo Li. Orthogonal weight normalization: Solution to optimization over multiple dependent stiefel manifolds in deep neural networks. In 32nd AAAI Conference on Artificial Intelligence, AAA/ 2018, pp. 3271-3278. AAAI Press, 2018
Pratik Jawanpuria and Bamdev Mishra. A unified framework for structured low-rank matrix learn- ing. In International Conference on Machine Learning, pp. 2254-2263, 2018.
Hiroyuki Kasai, Hiroyuki Sato, and Bamdev Mishra. Riemannian stochastic recursive gradient algorithm. In International Conference Machine Learning, pp. 2516-2524, 2018.
Hiroyuki Kasai, Pratik Jawanpuria, and Bamdev Mishra. Riemannian adaptive stochastic gradient algorithms on matrix manifolds. arXiv preprint 1rX1v:1902.01144. 2019.
Chong Li, Genaro López, and Victoria Martín Martun-Márquez. Monotone vector fields and the proximal point algorithm on hadamard manifolds. Journal of the London Mathematical Society, 79(3): 663-683, 2009.
Jun Li, Li Fuxin, and Sinisa Todorovic. Efficient riemannian optimization on the stiefel manifold via the cayley transform. arXiv preprint arXiv:2002.01133 2020.
Tianyi Lin, Chi Jin, and Michael I Jordan. On gradient descent ascent for nonconvex-comce minimax problems. arXiv preprint (rXiv:1906.0033/ 2019.
Tianyi Lin, Chi Jin, Michael Jordan, et al. Near-optimal algorithms for minimax optimization. arXiv preprint arXiv:2002.0244 02 2020.
10

---

Under review as a conference paper at ICLR 2021
Mingrui Liu, Youssef Mrouch, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. arXiv preprint arXiv: 1tt.19....1994., 2019.
Yuanyuan Liu, Fanhua Shang, James Cheng, Hong Cheng, and Licheng Jiao. Accelerated first-order methods for geodesically convex optimization on riemannian manifolds. In Advances in Neural Information Processing Systems, pp. 4868-4877, 2017.
Luo Luo, Haishan Ye, and Tong Zhang. Stochastic recursive gradient descent ascent for stochastic nonconmee--sronnyy-cooaav minimax problems. arXiv preprint arXiv:2001.03724, 2020.
Mayank Meghwanshi, Pratik Jawanpuria, Anoop Kunchukuttan, Hiroyuki Kasai, and Bamdev Mishra. Mctorch, manifold optimization library for deep learning. arXiv preprint
arXiv:1810.018811 2018.
Seyed-Mohsen Moosavi-Dezzooli Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1773-1773, 2017.
Yurii Nesterov. Lectures convex optimization, volume 137. Springer, 2018
Lam Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pp. 2613-2621, 2017.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam R Solving class non-convex min-max games using iterative first order methods. In Advances in Neural Information Processing Systems, pp. 14934-14942, 2019.
Dmitri M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria in nonconvex-concav smooth min-max problems. arXiv preprint arXiv:2002.07919, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances neural information processing systems, pp- 8026-8037, 2019.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:1810.0200 2018.
Hamed Rahimian and Sanjay Mchrotra. Distributionally robust optimization: A review. arXiv
preprint arXiv:1908.0560 0065999...6...... 2019.
Meisam Razaviyayn. Tianjian Huang, Songtao Lu, Maher Nouiched, Maziar Sanjabi, and Mingyi Hong. Nonconvex min-max optimization: Applications, challenges, and recent theoretical ad- vances. IEEE Signal Processing Magazine, 37(5):55-66, 2020.
Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra. Riemannian stochastic variance reduced gra- dient algorithm with retraction and vector transport. SIAM Journal Optimization, 29(2): 1444 1472, 2019.
Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere ii: Recovery by riemannian trust-region method. IEEE Transactions on Information Theory, 63(2):885-914, 2016.
Yifan Sun, Liang Zheng, Weijian Deng. and Shengjin Wang. Svdnet for pedestrian retrieval. In Proceedings of the IEEE International Conference on Computer Vision, pp. 3800-3808, 2017.
Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. In Advances in Neural Information Processing Systems, pp- 12680-12691, 2019.
11

---

Under review as a conference paper at ICLR 2021
Bart Vandereycken. Low-rank matrix completion by riemannian optimization. SIAM Journal Optimization, 23(2):121--126,, 2013.
John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior (commemo- rative edition). Princeton university press, 2007.
JH Wang, G López, Victoria Martin-Märquez, and Chong Li. Monotone and accretive vector fields on riemannian manifolds. Journal of optimization theory and applications, 146(3):691-708, 2010.
Di Xie, Jiang Xiong, and Shiliang Pu. All you need beyond a good init: Exploring better solution for training extremely deep convolutional neural networks with orthonormality and modulation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6176- 6185, 2017.
Tengyu Xu, Zhe Wang, Yingbin Liang, and H Vincent Poor. Enhanced first and zeroth order variance reduced algorithms for min-max optimization. arXiv preprint arXiv:2006. 09361, 2020a.
Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems. arXiv preprint arXiv:2006.0203:: 2020b.
Yan Yan, Yi Xu. Qihang Lin, Wei Liu, and Tianbao Yang. Sharp analysis of epoch stochastic
gradient descent ascent methods for min-max optimization. arXiv preprint arXiv:2002.05309, 2020.
Junchi Yang. Negar Kiyavash, and Niao He. Global convergence and variance-reduuced optimization for a class of nonconvex nonconcave minimax problems. arXiv preprint arXiv:2002.09621, 2020.
mnnconvvx-nonconccve
Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Con- ference on Learning Theory, pp. 1617-1638, 2016.
Hongyi Zhang, Sashank J Reddi, and Suvrit Sra. Riemannian svrg: Fast stochastic optimization on riemannian manifolds. In Advances in Neural Information Processing Systems, pp. 4592-4600, 2016.
Jingzhao Zhang, Hongyi Zhang, and Suvrit Sra. R-spider: A fast riemannian stochastic optimization algorithm with curvature independent rate. arXiv preprint arXiv: 2018.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint 1rXiv:1911.10633 2019.
Kaiqing Zhang, Sham M Kakade, Tamer Başar, and Lin F Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. arXiv preprint arXiv:2007.0746) 2020.
Pan Zhou, Xiaotong Yuan, Shuicheng Yan, and Jiashi Feng. Faster first-order methods for stochastic non-convex optimization on riemannian manifolds. JEEE transactions on pattern analysis and machine intelligence, 2019.
12

---

Under review as a conference paper at ICLR 2021
A APPENDIX
In this section, we provide the detailed convergence analysis of our algorithms. We first review some useful lemmas.
Lemma 2. (Nestervv 2018) Assume that f(x) is a differentiable convex function and X is a convex set. x² E X is the solution of the constrained problem min f (x),, if
N((x"),=->2 2 O, x E X.
(18)
Lemma 3. (Nesterov 2018 Assume the function f(x) is L-smooth, i.e., IVf(x)
Vf(w)
L| - yll, and then the following inequality holds
L - yl1
If(w) f() Vf(x)" - x)1
(19)
Next, based on the above assumptions and Lemmas, gives some useful lemmas:
Lemma 4. The gradient of function ((x) = maxyey (x, is retraction G-Lipschitz, and the
mapping or fanction y² (a) arg maxyey [(x,,) y) is retraction k-Lipschitz Given any 3i, D2 Rx, (u) E X C. M and E M, we have
Iggrad (x1) T (x2)) S G||u]], (x1) - y2 (x=2) S k klll
where G = KL12 + Li1 and x = L21/ us, and vector transport T transport the tangent space of T1 to that of xz-
Proof. Given any 31, 22 = R2, (w) X and u E TT,MM M. define y²(x1) = arg maxyey [(11 y)
and y" (x2) = arg maxyey (22 y). by the above Lemma 2 we have
(y - リ" (x) "
S 0, Vy
(20)
(y 10 (xz) (22, (x2)) - 0,
Vy V.
(21)
Let yety-y'e y" (x²) in the inequality inequalities, we have
20 and y = y (x1) in the inequality 21 then summing these
(v'(22) y² (V
y (I2))) $o.
(22)
Since the function f(11,)) is u-strongly concave, we have
((21.5" < f(x,, (x2)) + vV,f((1,, ( (v'(x1) 1/ (x2)) - - 1ly (x1) - 3² (x2))1
-2
(23)
( S [(,, + (V (( ( (x)))) - 1/ (x1)) - マ/ 11y" (x)) - 3/ (x22)1
(24)
Combining the inequalities with 24). we obtain
(v"(2)) y" (x1))) (V,f(mi.v' (xz)) V v + (xl)"(>))) --" (x2))) < 0. (25)
By plugging the inequalities
into 25 we have
"lly" "/ (222)
< (y (x2) - v" (vm)
(x2)) - v,s(2r, (x2)))
< (x2) -
V. (anl))-VVfff,,,.... v
s L ||lll//lllll//////
(x1)l.
(26)
where the last inequality is due Assumption 1. Thus, we have
(x1) y" (122) s k||u/],
(27)
where T22//1 and D2 Rz, (u), M.
13

---

Under review as a conference paper at ICLR 2021
Since ((x) fxx y (I)), we have (x) = grad,, (z)). Then we have
(gradd(2))) gradd)
=Iggrad_ [g The grad
grad_ ff (x2)))
(z)))
(x2))) (+ Ig (x1 y (az)))-Tr, grad y (x2))
1 (21) - Iutl
& (kI112 + In]]:
(28)
where a E M.
Lemma 5. Suppose the sequence {1,, yerrm is generated from Algorithm 1 oor Given 0 <
24 we have
((1+11) s ((x)) + +LI1mmllle (xx) voll mm of vell 2- M
Igrad (2)))())))) [x)) 1|
2
Mt 10.1.
(29)
Proof. According to Assumption 2, i.e., the function (xx) is retraction L-smooth, we have
((1(41) S (xx))) Thh (grad vz) ?n
(30)
2
[g:rad(xx))1 + 321
= ( +
7i
gradø (x:) - well 7h
M
) |1t
2
2
2 2 7h
(xx)) + Th
grad (x,) - grad (x,, Mn) + grad (( Uc) U1 12
(x;))
2
2
72112
Me
2
< (wx) +m/ll am ((gggadd grad, vi)l grggddddd v1) uvll
7 -
2
Ln
Me
]leell
2
< (2,)) YTe myellgradd gr (1r, 3t)l + mm g..dd ( M1) v2ll 7 (x,))
7Th ||:.1
where the last inequality is due to 0 S 25L.
1
Consider an upper bound of [|grad grad, f frr, (g:) grad, ( 112 = ||grad_ (vt, yd (xx)) grad [ 30ll
1211 we have
< I12lly" (xx) - yell?
(31)
Then we have
(x++1) s (xx:) + mmeLe2ll - y +md avellgrad, vel1 1|1 Me
[grad
2
Mi
(32)
4
Lemma 6. Suppose the sequence (2r, is generated from Algorithm 7 oor Under the above assumptions, and set 0 < ne Σ and 0 < <
6f.' we have
1 y" (21+1))1 <1 n.ddA
31/t
l1 y² y0xx1)112-
1 30l12
4
257, +
25 ||
V
ve.
well2
(33)
6/z
where K. T22/11
14

---

Under review as a conference paper at ICLR 2021
According to the assumption 3. i... the function f(x, y) is p-strongly concave w.I. y, have
Proof.
f(z s f(z,, vr) + (f ve). yr) P 11y yell2
2
[sr, + (wi, 1 ve+1) Vyy[uus De) We, y D(+1)
+ +VyJ 06); 0t+1 ve) 2 vell?
(34)
According to the assumption i.e. the function f(x, y) Lz2-smooth w.r.t y, and L 2 L2z, we
have
L22
f(r, Det1) - far, un) (V yf 21).
ve) 2
l0t+1 - yell"
L
2 2 1it+1 well?.
(35)
Combining the inequalities with (35, we have
[Fr, v) S (1t, De+1) ) + (we, De+1) + VVDl(T, M1) wr.y -D++1)
I
M vell2 + 2
11 -vel?
(36)
2
1 or 2 have Jc+1 Py(Bt Aw,) arg ey 2 lly 3/: Aw 2 Since is convex set and the function $lly Y/ Awr 2 is convex, according to Lemma we have
According to the step 6 of Algorithm
(We+1 V1- -.w, H1+1) 2 0, y y.
(37)
Then we obtain
(we. - - Dc+1)= 5 X (Je+1 yt. - 11++1
(Je+1 - Ue: V1 - m(+1) + (Jt+1 - yc y - ve)
1
1l++ Me 112 I (De+1 1/. m²)
(38)
Combining the inequalities (36 with (8). we have
((1,,) S [ D(+1) + (We+1 - yr. - - + (V We: y Wo+1)
11 1 libtt vell2 1/1 l1y 2ell2 I1ūe+1 - 30ll2
L
(39)
Lety y" (xt) and we obtain
1 (ie+1 ye, ve. (xxz) ve) + (V we, w1,)"(xe)) Dc+1)
f(x,,1" (xx)) S [( 0c+1)
1 * |1 voll - " (Ile((a)) (e)) vell2 + 2
i _ Elie+1 - vill?.
(40)
2
Due to the concavity of f(,,)) and y² (at) arg m f( we have f y (x+)) f(r,, I.) Thus, we obtain
0 5 (0c+1 Vc. (x.)"(xe -v) + (Vyf yı) we, v" vxx)) v(tz)
vi)
_ [ )1l - 32112 ト/~ |1 (αx) 11.112
(41)
2
By M6+1 = yt + nc(i++1 - ve). we have
|| v² (xx))1 = 11 + nT We) - 4¹ (xx) 1|
Ilve y² (xxa)12 217 (5t+1 ve, V4 4² (xx)) + 11b11111 - -a (42)
15

---

Under review as a conference paper at ICLR 2021
Then obtain
1
+ 7h |1 vell? 1 -luo+1 (xx))) (43)
(We+1 Me, (o.y((x))) (1z)) - v1) S 2mj.
-lyee y² (xxx))1
2
21/-
Consider the upper bound of the term (V (V 1/.) we: (xxe) - 1); we have
(V (x vo) we. 1² (xz) - i(+1)
(V ue) - We.
-e V (z1) y1) + (f 31)
We, Yt Di+1)
S 1 (yJ( We) -w; + 4 (x+) vell +
4
1
V [ we) - will2 + 11
4 11 sr+1l1
1
2
IV (32. u. 1011 4 Ilv" (xx) vell + |1 ūttill
#
(44)
μ
By plugging the inequalities
41
to (44) we have
1
116+1 - 3/ (1())]11 1
")lle= y² (xx:)l
+
+
i
)1 well
2mp
2m x
2X
4
2
+ /
v (x2,,)) - 1
$ 2nd
1
4 *
Ilve y² (xx))12 +
31 1
I|ūb+1 yoll2
2
2 V v.) well?
2X
1
")1l91 y- (xx))1
3
1
3
)lle+11
yell?
2nd
82
4
2
+ 1
V w1) - w2
(x1,811)
$ 2nd
" "1le y² (xx)))1
3
|lut1 -o0l2
+
2
V vvf(ze well?
82
p
(45)
where the second inequality holds by i. 2 T.22 2 a and 0 < 1/t S 1, and the last inequality is due
0 < A S 1 It implies that
67.
MPd 2
37l
4nt 1 Br) - w, 12
[lue41 - y" (x, s (1
11yee - 1/" (xx))1
11++1 - 32112 +
|
4
11
(46)
Next, we decompose the term || - y² (Iz+ 212 as follows:
Ilve+1 - y² (12+1)l = |lıe41 - (xx) + y² (1x) - 1/ (1++1)l²
= || y" (xx))1 + 2( 11" (xx)), y (x+) - y² (x++1)) + (1x) - v (x++1))1
- (1 + Deped
4 || - (x,))1 + (1 + veuu )x,)((x))))))))))))))))))) - 22" (1(+1))1
4
< (1 +
)lbee1 (xx))l + (1+
Map 2 10e11
(47)
4
where the first inequality holds by the Cauchy-Schwerd inequality and Young's 's inequality, and the last equality is due Lemma
By combining the above inequalities (46 and
47
we have
Ilve - (xx))1 (1+ Mdddd 31/t
|| (2(4++1)1 < (1+
)
|1 - 2ell
4
2
4 4
Madd
4m
A
4
+ (1
Vy vk) well2 + + Maiud
4
(48)
16

---

Under review as a conference paper at ICLR 2021
Since 0 T/ E 1, v G7
and L 2 Leg μ, we have
1
S
1
and
m
S
1
1 6μλ
Then
obtain
(1 + MAd
TeMA + 7HHA
2 1 nudr
][1
2
(1 11/11
31/²
31/²
4
(1 + Mud
1
AmA 25mA
< (1 +
4
1
24
1
6μ
4
472k2111
n222m
472k211
25-2k²m
(1
>n²
= x222
I
(49)
MA
6pd
MA
6ud
Thus we have
37tt
1lb+11 (21+1))1
)lBe - y yxx))]1
lūt+1
yell
4
4
25m A
257 x²
+
V ve)
well
11
(50)
6p
6Fd
A.1 CONVERGENCE ANALYSIS OF RGDA AND RSGDA ALGORITHMS
In the subsection, we study the convergence properties of deterministic RGDA and stochastic RS- GDA algorithms, respectively, For notational simplicity, let L = max(1, 41, L12, L2 422). Theorem 4. Suppose the sequence {I,, yr Y is generated from Algorithm [ by using deterministic
gradients. Given 1] Th for all 2 < v S min(1, 2イz 0 < X have
67. and 0 < 7 S 10LK'
add we
1 T
Σ
[Lvee - (x+)) + (x; 5
2 ((x)) x
(51)
Vnrlt
Proof. According to Lemma 6 have
MPd Iluee - y² (xx))11 4
31t
25
Ilue41 - y" (2++1))1 s (1
11:c11
31 31
1 1 (x(. Vo)
- -wel
6/
2122 112.112.
(52)
We first define a Lyapunov function Ae, for any 2 1
A, = ((x)) + G,L²
1Ive - 1² (xx))1
(53)
Ay
According to Lemma
we have
Ac+1- A. ((I++1) (xx)) +
Au (11v4+1 y² (fe++))) - y²(xx) )12)
S mh y² (x:+) + + + lgrlllrrdd_rr (_ Vt) - -vell2
7
|grad -
||e|
2
4
1.2 (- pudule uud 11ye -- 1 (x:))) 3re 11 vill2
25
V
y Me) w/l1
Ap1
6μ
25-2
(1
6td
9 nm
11
V (xxx)12
Me gr:dd(x:))1
11++1 - 8/
2
2
2Aμ
1
25n2 {222
25n:
12222
11 y²(xz) 112
Mi
Igrad((2;))
(54)
17

---

Under review as a conference paper at ICLR 2021
where the first inequality holds by the inequality (52) the second last inequality is due L max(1, L11, L12, L22 L22) and 2 = grad,f( yc), we Vyf(z,, yo), and the last inequality is due to 0 < 7 S
jad
Thus, we obtain
10Lx"
1 L' 1i - 1/ (xx)]] + Mh
2 grad S A. A
(55)
2
Since the initial solution satisfies y1 = y (x1) = arg max f f21, y), we have
A1 = (21) + 67 y y
(z1).
(56)
Apr
Taking average over t 2, on both sides of the inequality (55 have
2 n:
Tht y² (2x)))
( A1 Ar+1
( o+
1/
(57)
T
2
77
where the last equality is due to the above equality (56 and Assumption 4. Let 1/1 = have
qr,
2(0(21)- - x*)
Σ
P' y 02(x)))1²=
[grad(()))1 <
(58)
7T/L"
According to Jensen's 's inequality, we have
T
T
1/2
Elvee - y (xx:)l + (grad((x))))))))
-
Σ
[?7 - (xx))1 + Igrad (xt)
T
T
1=1
4(((21) (5))
1/2
2 (()))) x
(59)
mi
VnnT
Theorem 5. Suppose the sequence (Ii, Dt 12 is generated from Algorithml 7 by using stochastic
gradients. Given 17 = T/s for all 2 1, 0 < 1 min(1, 241. ). 0 < X < and 0 < 7 S ad we 10
huve
2 ( :h
V20 +
5v2Lo
B[Lll y" (2x))l + (graa
(60)
V
VB B
VBp
Proof.
According to Lemma G we have
nepd Ilvee 1/" (xx)))1
37t M1
25nx
llve41 - y² (11+1)112 s
ve 112
1 W
(
-
6/
25 x22 ||ux|1?
(61)
We first define a Lyapunov function Or, for any t 2
1,
θ = E (xx) +
Ilve - y (x:)))
(62)
Ap
By Assumption 5, we have
B
d²
E Bgagradd [gggrddd// (1x. vell = El|grad [ggadd_[(s,, we)
Σ
grad_/' ( yri 21l
(63)
B
B
1
B
o²
E V Vyf((u, -w,l B y (x v1)
V y ( <
(64)
B
B
18

---

Under review as a conference paper at ICLR 2021
According to Lemma we have
GyL² (Bl yy (1(41) 2l Ellye - v" (1x))1?)
141 O. -E (1+ (1(((1++1)
B[+(),)) +
Ay1
S 11/T11181 ve of (x+) )1 1. grad f2 m1) -rell2 Yi
B grgadd 7
||
2
4
E Ellu+1 - well? + 6,,12 (- Hu Ellye (xx))) 3rd
25
V V (x): - well
Ap
6p
25
1|
6Pd
L'
9yL2m 11
7 Blllte - -x
E (x)))
B1 - -Bell 11
2
2
2Aμ
1 25k 23m²i???
) + Bng _ Mr) - 1re12 + 25I.2
E| (2,,
-wel"
1²22
112
L L' Bl gt (xx)
Th (2.)) mho² 25L
(65)
2
B₁²
where the first inequality holds by the inequality 61 the second last inequality is due i. max L1,, L12, L21, L22), and the last inequality due to 0 < 7 S Thus, we obtain
ad and Assumption 5.
10Lx
L E Elye - y² (xx))
7h (zggrad < 0. - 0 + 1ho²
25
(66)
2
2
B
Bu²
Since the initial solution satisfies y1 = (x1) = arg max f(1 v), we have
1. 1ly1 y" (x1))1 ((11)
θ p(11) +
(67)
Ap
Taking average over I. = 1,2, ... on both sides of the inequality
(66
we have
T
E2
1.2m
30 (x:))
7)
(rrad(())))13)))
O,
0,+1
+
T
2
T
25i.2mp.
T
2
2
7T
T
B
T
By²
D(x1) - -
1
T
Σ
T
1
7T
T
B
T
Bμ²
(68)
where the last equality is due to the above equality 67 1. Let 17 = 171 ... frr we have
2($(x:)
xh))
+ 0² +
25
B Mr - (x+)) + (x;)
(69)
B
Bp²
According to Jensen's 's inequality, we have
T
T
E Llue - y² (#+1l + (2x))l
<
( Σ
E [[2
yy (x))1 + (x:)))
T 1
T 1=1
4( - x8)
20
50
1/2
mT/I
B
Bμ²
2 1 (xx1) +t
-20
5/2Lo
+
+
(70)
VnrT
VB
VBu
where the last inequality is due to (a) + 02 + 2/2 < aj
+ 0g
1/2
+ ag
1/2
for all a1 02 03 > 0.
19

---

Under review as a conference paper at ICLR 2021
A.2 CONVERGENCE ANALYSIS OF THE AVR-RSGDA ALGORITHM
In the subsection, we study the convergence properties of the MVR-RSGIA algorithm. For nota- tional simplicity, let L = mnxx(L11 L12, Ln, Lyg, 1).
Lemma 7. Suppose the stochastic gradients ut and wy is generated from Algorithm given 0 < ac+1 S 1 and 0 < 34+1 1, we have
B Bllgrad, (f Bo+1) Dit1l' 112 2 -0411 ( (1-a vo) - -vell + 4(11 -
2441)
2a,
+ 4(1 a 110-1 vell
(71)
B
V w (1 Bu+1) 2 f w.ll
+ 4(1 (0-1))22277
||,,
20/+10²
4(1 B 2 L3 11ue41
3ell
(72)
B
Proof. We first prove the inequality 71 According to the definition of U2 in Algorithm 2 we have
Ut+1 T u.u, = -0++1 T 12 U + (1 ac+1) (grad, (I M(+1) Tet ggradd fB (0 Vt))
+ 1 (11+1,
(73)
Then we have
E| El|grad
f of
M4+1) 1/+1/12
(74)
grlg Mt+1) - Teit1 (V++1 - -T (eHtiv))] 12)
21
Ellggad, ( U(+1) T 0++1 Thi+1 gradd (#441,
- (1 a++1) gf.t (1++1:30+1) - T (r--ggrad,BB... (z,, 112
[1 02++1) T [g Ur) - v2) + (1 (1-a4+1) (grad (E++1, - Tel grad Mt)
grad, (Ie+1, 11)) + t grad,fB.4. (21, 31))
au+1 (grad, (x1+11 9(+1) grad,ff..... (II-1. M(+1)) ||2
(1 oz+1 ) ggaad (#x, m1) 12 + a ggrad (xe+1, 1141) grad (1241, 91441,,844111
(1 ar+ * (I++1,
T grad (x m.) grad, (11+11
1 (It, )12 + 20 - ()) grad f ( Mo+1) - T ff yt)
grad. (1 11) + Tz grad (x,, v=), grad s (1 - grad (1441,
< (1 o++1) ) gradd ( v1) w2l2 + 20 B grlggrdd (I - grad, (11+1, v++1)
2( a1+1 2 grad f M1+1) T grad f fIr, vi) - grad.ff.4. (#++1, 1141)
T frad (Ie, 11
< (1 - 04+11 2BIad (Ir, vi) - vol12 2a
B
+ 21 04+1)* 1 Ellgrad, (#141,8141) - Tre+t grad fBr. (It, v:ll
=ni
where the fourth equality follows by Elgrad, (I141, v1+1)l grad ( M141) and - Elgrad, (0441.96111 fB.., (It, ye)l = grad,, ( V1+1) - grad, (ar, y:): the first
inequality holds by Young's inequality; the last inequality due to the equality E||ç - E[]]1 = E||c||2 [| and Assumption 5.
20

---

Under review as a conference paper at ICLR 2021
Next, we consider an upper bound of the above term T1 as follows:
Ti E grad (#++1, M6+11) - + fBe (Ie, Be)l"
(75)
E gradd_fB,, (#1+1, Mt+1) + grad ( M++1iE++1) Tei grad, yet1i
To grad,, (2',, (x), w)
< 2B grad (Te+1 11++ T gradd_/(a Vetii
+ 2|bl|grad_ f (2t, 1h+1: ((+1) - grad,fB... B.. (Te, Mt) |
2 1 || 22 + 22 11 -v
> ||: 2 + 22 lūt+1 yell?
(76)
where the last inequality is due to Assumption 1. Thus, we have
E f (1+1)) 1 112 s (1 0x+1) 2 ggrad (1r, M1)
+ +4(11 22+1) ||ell
20
4(1 a++1 2 |1
yell
(77)
B
We apply a similar analysis to prove the above inequality
72p. We obtain
E|| V v (Z M1+1) we++ 11 (1 B2+1) (I yc) w. 11 + 4(1 -3--
L22
2
+ 4(1 - 3u+1) 12211 l1 - well? +
(78)
B
Theorem 6. Suppose the sequence (ait, yt I is generated from Algorithm 2
Given y1
y (x1),
C1
2
30
2 + 2d1,, C2 2
35
2
+
50x
P > O, m 2 max (2, ((b)
<
2xLv26+4ux
nd
and
0
< A
1 we have
6L'
T Σ
22M'm 1/6
V2M'
([(grra(((xa)l + i.l. - 3 (x+)]]
(79)
T
T1/2
T1/3
where ė max c1, 02 1) and M' 2(0(()))))) 76
20²
2 20) AuB
In(m + T).
AunabB
Proof. Since "n is decreasing and m 2 63, we have T/2 S 1/0 m3 S 1. Similarly, due to
m 2 L we have 77, S no m I 1. Due to 0 < 17t S and m 2 max ((c/b)3, ((czb)".(eb)) (c)b)3),
have 0+++1 cn? cine I
b mi/a and B 02 c2n miro S 1. According to
Lemma 7 we have
1
1
E grad, (IT+1 - Ue+1 2
EE Ellgradd (2 311) 12
(80)
1h-1
(1 a²
1
E
grad f ye) -vll2
2e|12 1(1 1111-111))
Ntc
Th-1
202
+ 4(1 ax+1)
2 11++1 12
BBB
a1+1
1
grad If (xv vi) - ve122 + 2 112 + 4L ll0441
yel12
2a 0z
1)t Th-1
nBB
1
1
20 20
cin) glgaad ( 11) - 11 + -4111> 2 12 4L llū++1 - vell +
1/
T--
BBB
where the second inequality is due to
< a++1 S 1. By similar way, we also obtain
1
1
El V Tyf(2441, 21+1l22
E f (z,, vt) w2,12
(81)
n
m--1
1 1
2
3 ff v6) w, 2 4LL 2 1 + 4L32nd 10+1 - 3e112
11
Tp-1
nBB
21

---

Under review as a conference paper at ICLR 2021
By ni (m++)173 we have
(m + 1)3 - (m + 1--1--101 1133)
?/-
1
S
36(m +t 1)2/33
3b m 3b(m/
+1) 1)2/3
22/3
2
22/3
3b3 1h 1
(82)
3b(m + 1)2/3
3b3
(m/2 + 1)2/3
3b
where the first inequality holds by the concavity of function ((x = x2/3 i.e. (x + y) <
r//3 + 30378: the second inequality is due to m 2 2, and the last inequality is due to 0 < 1/2 1.
Let Ci 36
2 + 2Aj,, we have
1 EE ggad ( 12+1ll2- 1/-1
1
glllgrad g f Ve) - well
(83)
1/
grrad 12 > || 4132m1ll00e yel12 + 2a o²
1/. B
Let 02 2
36
2
+
50x
we have
1 V (I - of - -well
(84)
77-11
50AI2
2,3 o² nBB
TE
V ffr,,
w 4LL11 7 2 /1/11 + 4L32 1e 11:0+111111111 31112
4
According to Lemma
we have
T.pted 11y: (xx))1 31J:
Ilue+1 y² ( -1y1- -1111-11 (x:))
|1 vell
25
25-22 ||
+
V v1)
w: 2
6p
65dr
(85)
Next, we define a Lyapunov function 24, for any 2 1
Ω2 [[((x]] + 7 1
1
El Ellgrad_ we) 22
E (xe, wc) -wal²²)
2d
1
M--1
1.2
Elye y (2.)
(86)
d
22

---

Under review as a conference paper at ICLR 2021
Then we have
Gy
Pe+1 - S4 =
-B( -B0(o]] +
(Bell y (x++1)]1 - Elyy - y² (xxe)1
Ape
+ 2Aμ 1/
(
1 El Ellgrad f(1+1, 31-1)) - u1+1 11?
1
E Elgrrd_ f 36) - well?
M6-1
1
E of ( M(+1) wo+1
E V off (Fe.
woll²)
7/
7/-1
L1 yt (x:))
) 1| + 1. _ (2 vv) -ell2
Y E gllgdad (rx))l - 7 ||eell
6r,12 (-
Jud Bllye (xx)))
3/f
25
V y (Tt 11) wwel? + 25 11
E Ellūt++ - well +
| 112)
Ap
4
6p
20
+ Y
( 2 f( Me) - 2 2 + +477 > v1l1
12
11l12 +
2Aμ
50xi.
2
V f
w/ll + +1221 7m 1/l111111 4
wel1
P
niB
Me E Igrad (a:))12 7..2
25
4-
B
Ut 15" (xx))1
Felli++1 - 2
mell
2
1²
DA
70
3/2+102
Apm B A
IL2mm
E. (x))) + 7a2+102 Apnr B
Mi Elyr y (x+)
(87)
2
2
Apar, B
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, L1, L2,, L21, L22); the last inequality is due to 0 7
HA
and K 2
According to the above inequality 87 we have
7a24102 Apme
18
?he 2
(E] (x:)) i' 1y+ y" (xt)11) s Ω
2441 +
+ Apmp
(88)
Taking average over f = 1, 2, T on both sides of the inequality 88
we have
T
2(S4
P441)
T
20 0²
En (Igrad
L 3² (2:))1 <
T
7I'
T
ApMil
Apm
1=1
Since the initial solution satisfies yı = y=²((x) arg max (x1, v), have
0 =(x1)= +
i
11
---"(x11)1
2xμ | v1) - 11112
7
1
| (x(,))11) - w (/)1
Apr
170
= =x(1))= + 2 170
(=
1
grad_Ss, (11,
- - VyJis (x1, un 113)
-
170
< <011)) + B
(89)
where the last inequality holds by Assumption 5.
23

---

Under review as a conference paper at ICLR 2021
Table 3: Benchmark Datasets Used in Experiments
datasets
#samples
#dimension
#classes
MNIST
60,000
28 x 28
I0
CIFAR-10
50,000
32 x3
10
CIFAR-I00
50,000
32x32 x3
100
SVHN
73,257
32 x3
10
Fashion-MNIST
60,000
28
10
STL-I0
5,000
32 x22 x3
10
Consider Q) is decreasing, i.e., 1/" 1b
for any 0 stst, T, we have
E (x;))(
L3 - y (x=))
(90)
T 2(52, 1441)
1
Σ
2a 20 02
+ TmT
TyTT
AuniB B
A
1 (x1)
20
24
202 0²
2 18 0² Awan B
+
+ Twr
TyI
7
APTI B
AumB B
2(0(z1) - -
20²
2(c + +2)0
Σ
3
m
THIT
TAUMOOT B
TIT AuB
t=1
2(F((1)) $5))
202
2(c o2)0²
13
dt
TYTT
TApoour B
TunABB
111 +
2((((11) xb))
202
2(c
+ TAAmOOTT B
In(m + T)
THUT
TuBBBB
2()(x11) (b))
20²
2(c + 22)
(m + 1// +
(m + TT
In(m Tm + 1/3
Tyb
TApmobB
T\uB
where the third inequality holds by ET T S S dt. Let M' 2(0(m))) -*)
2o
+
76
2(0 + In(m + T), we rewrite the above inequality as follows: ApB
T Σ (())radd((x:)) + E (x:))13)
M'
< T (m + 1/1133
(91)
According to Jensen's 's inequality, we have
T
2 T
(Ilgrad (I:)]l² (IIgrad((x:)]1 + -2llyv 1 ((x))))))
( gra Lll - (x+)l) <
E
T
T
t=1
/2M'
V2M'm
V2M
(m T)
112
71/2
T1/3
(92)
where the last inequality is due (a, + 1/6 < a + a 1/6
for all a1, ag >
B ADDITIONAL EXPERIMENTAL RESULTS
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 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 training DNNs.
24

---

Under review as a conference paper at ICLR 2021
Table 4: Test accuracy against nature images and uniform attack for FashionMNIST, SVHN and
STL- 10 datasets.
Method
Eval. Against
FashionMNIST
SVHN
STL-10
Nat. Images
84.96%
75.72%
52.34%
RSGDA
Uniform Attack
82.54 %
43.19%
47.28%
Nat. Images
88.49%
76.05%
54.92%
MVR-RSGDA
Uniform Attack
76.75%
45.06%
48.89% %
Nat. Images
88.57 %
91.96%
56.10%
SGDA
Uniform Attack
50.90%
45.97
45.27%
RY3DA
RSG3A
SVV MUR-RSSON R5GOA
NVR RSCDA
MVR RSGDA
Trxin
Train
Epochs
Epocht
Epochs
FashionMNIST
(b) SVHN
STL.-10
RSSDA
RSODA
RSGOA
MVIL-USIIAA
MUR-ASCDA
Atteck
23
Eerations
Berations
(d) FashionMNIST
(e) SVHN
(I) STL-10
Figure 4: Additional results for robust training (a-c) and uniform attack (d-f) with SGDA, RSGDA and MVR-RSGDD algorithms.
25


Reviews:
[{"review_id": "sF0jCQ7ifA9", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes Riemannian algorithms for min-max problems where the min problem is over a manifold and the max problem is a strongly convex problem. It presents a rigorous convergence analysis of the algorithms proposed. Finally, experiments show the good performance of the algorithms for robust training of DNNs over manifolds. \n\nThe paper is nicely written and overall easy to follow. The work is relevant for practitioners who use similar min-max problems as it provides necessary theoretical backing to the use of such constraints in DNNs. \n\nComments\nAssumptions on the manifold are missing, compactness is required? What are other restrictions?\n\nSince the max problem is strongly convex, one can in principle directly work the formulation min_{x in M} Phi(x). The Euclidean gradient of Phi(x) can be easily computed (Danskin’s theorem). (One work in a similar spirit is [1]). Of course, I assume that the max problem is solvable with an iterative solver which is easy to implement in many cases. This may be easier to analyze, no? If that is so, then why go for explicit updates of the max variable y? A discussion on this is missing. \n\nThe main contributions are theoretical, and to that end, the experiments suffice. However, it can be broadened by including other baselines. This will strengthen the paper.\n\nThere are some issues with how to use \\citet and \\citep while citing papers, especially in Section 2.2. For example, in “More recently, Sato et al. (2019) has proposed…,” it should either be \\citep or has ---> have. Please look into other such issues in the paper.\n\n[1] Jawanpuria, P. and Mishra, B., 2018, July. A unified framework for structured low-rank matrix learning. In International Conference on Machine Learning (pp. 2254-2263).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "PNgS_C8KaML", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1.Summarize what the paper claims to do/contribute. Be positive and generous.\n\nThis paper considers solving the minimax saddle point of the form \\min_{x\\in X}\\max_{y\\in Y} f(x,y), where X is a Riemannian manifold and Y is a closed convex set. The objective function f is nonconvex in x and is strongly-concave in y. To the best of the reviewer’s knowledge, this min-max problem with Riemannian manifold constraint has not been considered in the literature. To solve such a problem, a two-time-scale manifold gradient descent ascent (MGDA) approach is then proposed to solve the problem in the deterministic case. An iteration complexity of O(\\kappa^2\\epsilon^{-2}) has been derived for the MGDA approach, where $\\kappa$ is the condition number of the problem. When $f$ is in the form of an expectation or a finite-sum of a large number of component functions, the author proposes a manifold stochastic gradient descent ascent (MSGDA) approach and a variant of MSGDA with the gradient estimator constructed with a momentum-style SARAH/SPIDER technique. Sample complexities of O(\\kappa^4\\epsilon^{-4}) and \\tilde O(\\kappa^3\\epsilon^{-3}) have been derived for the MSGDA and MVR-MSGDA methods respectively. The adversarial training of DNN and a specific instance of the DRO problem are proposed as the motivating example of this work. \n\n2. Clearly state your decision (accept or reject) with one or two key reasons for this choice.\n\nThis paper should be rejected.\n\n3. Provide supporting arguments for the reasons for the decision. \n\n(i). The results for RGDA are largely from section 4 of (Tianyi Lin et al., 2020). Though the authors consider the Riemannian constraint on x, from the author’s experience in Riemannian optimization, it does not make much difference as long as the retraction operator is available. \n\n(ii). The RSGDA analysis also shares the same novelty concern as stated in (i). Moreover, the sample complexity of (Tianyi Lin et al., 2020) is only O(\\kappa^3\\epsilon^{-4}), which is much better than the O(\\kappa^4\\epsilon^{-4}). The reviewer believes that following the proof of (Tianyi Lin et al., 2020) step by step while replacing the gradient step by gradient-retraction step, O(\\kappa^3\\epsilon^{-4}) will be achievable for RSGDA. \n\n(iii). Technically, there are many non-rigorous arguments. E.g., the authors frequently use \n\\|x_{t+1} – x_t\\|^2 \\leq \\gamma^2\\eta_t^2\\|v_t\\|^2. However, this is wrong on manifold. The authors seems to believe \\|R_x(u) - x\\| = \\|R_x(u) – R_x(0)\\| \\leq \\|u\\|, but this is not true. The rigorous statement should be: Exist d,c>0 s.t. for any x\\in X, for any u\\inT_xX with \\|u\\|\\leq d, we have \\|R_x(u) - x\\| \\leq c\\|u\\|. These parameters should present in the final complexity result. They represent the property of the manifold itself. \n\n(iv). Although the result for momentum SARAH/SPIDER variance reduction seems new in this setting, merely this part is not enough contribution.\n\n4. Provide additional feedback with the aim to improve the paper. Make it clear that these points are here to help, and not necessarily part of your decision assessment.\n\n(I) The authors should carefully describe the relation of their result and that of (Tianyi Lin et al., 2020). Specifically, clearly state the differences and additional difficulties when generalizing the result of (Tianyi Lin et al., 2020).\n\n(II) The reviewer suspect that the result of RSGDA can be improved to O(\\kappa^3\\epsilon^{-4}) by following the procedure of (Tianyi Lin et al., 2020) more carefully. If this can be done, it will be better fill this gap. If this cannot be done, the authors should state the difficulty. \n\n(III) Since this work generalizes (Tianyi Lin et al., 2020), and the Riemannian manifold does not add much difficulty. So it might be better to include the nonconvex-concave case in (Tianyi Lin et al., 2020), this will make the result more complete. \n\n(IV) The authors should carefully review their statements w.r.t. Riemannian manifold so that the mistakes pointed out before does not happen. Though, generalizing from Euclidean optimization to Riemannian optimization is conceptually simple. But there are also some subtly in the arguments. \n\n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "OVlAShd1Gi", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\n\nThis work is one of the first I see tackling explicitly min-max optimization over a Riemannian manifold. The presented techniques are interseting and seem to have some applications. However, the presentation and writing of the make it quite hard to follow and, in my opinion, not ready for publication at that stage.\n\n\n* The introduction is rather well written and nice to read.\n\n* Then, there is an imprecision that has been bothering me throughout the paper: the authors seem to actually define the nabla_x f(x,y) directly as the Riemannian gradient, not the usual gradient. This is done directly without mentioning it in the bottom of page 3 (otherwise, all the gradient transportations do not make sense). Considering how the functions are defined in eg. (3,4), nabla_x f could stand for the full gradient naturally and then, grad_x f = proj T_x (nabla_x  f ) could be the Riemannian gradient. I think this can be easily fixed but presently it can cause a lot of confusion. \n- In addition, in Assuùmption 1, I do not get the inequality with L21. nabla_y lives in R^n so the transport is identity?...\n\n\n* The authors state that \"this is the first study of minmax optimization over the Riemannian manifold\" however, there seem to be some works on finding stable points of variational inequalities (by extragradient and the like) on Manifolds, eg. \n- (see Sec. 5.2 ) Li, Chong, Genaro López, and Victoria Martín-Márquez. \"Monotone vector fields and the proximal point algorithm on Hadamard manifolds.\" Journal of the London Mathematical Society 79.3 (2009): 663-683.\n- Wang, J. H., et al. \"Monotone and accretive vector fields on Riemannian manifolds.\" Journal of optimization theory and applications 146.3 (2010): 691-708.\n- Ferreira, Orizon Pereira, LR Lucambio Pérez, and Sandor Z. Németh. \"Singularities of monotone vector fields and an extragradient-type algorithm.\" Journal of Global Optimization 31.1 (2005): 133-151.\n\n* In assumption 1, the terms L11 and L12 seem to implicitly contain curvature information on the manifold. Could the authors comment on that? I guess that Assumptions 2 may also imply some \"hidden\" conditions on Y.\n\n* Theorem 1: In the case of deterministic gradients ( ie (8) ), I do not get over what the expectation is. Either it is related to the gradient and hence not need. Or, it is related to the random output (line 10) in which  case the sum seems not needed (as in E[H_\\zeta] below). \n\n* In Table 2, How are the algorithms stopped, is it after 1000 iterations?\n\n* I do not get how the authors obtain the first line after \"By plugging the inequalities (22) into (25), we have\" in Appendix A\n\n\nMinor Comments/Typos:\n* Abstract: \"on the Riemannian manifold\" -> \"on Riemannian manifolds\"\n* Preliminairies: several typos \"We define a retraction R maps tangent space\" \"Exp mapping is a special case of retraction that approximate the Exp mapping up the first order\" (!)\n* Theorem 1: \"Suppose the sequence () be generated\"\n* In Remark 2, the setting B=T seems quite unrealistic.\n* Figure 3: \"Iteratons\"->\"Iterations\" in the 3 subfigures.\n* between (22) and (23) \"By the function f is strongly concave\" \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5x4nL43YEH_", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the convergence of min-max optimization algorithms when the minimizer takes values in a manifold and the maximizer in a subset of R^d. The authors proposed three algorithms and analyzed the convergence rates to stationary points. Some experiments are provided to evaluate the proposed algorithms.\n\nThere are two major issues with the paper:\n\n1) There is essentially no novelty in the theory. Specifically, under the very strong assumptions 1-5 and that the maxmization is strongly concave, one can simply pretend that the retraction is a gradient step and then the analysis for gradient descent-ascent would hold almost verbatim for the proof provided by the authors. In other words, as the difficulty of analyzing Riemannian algorithms is already \"assumed away\" by the assumptions, there is virtually zero element of Riemannian geometry in the proofs. As a result, I found the theory to be incremental at best.\n\n\n2) The empirical evaluation is rather incomplete and disconnected from the theory:\n\n2a) First, the only algorithms presented are the ones proposed in this paper. Where are the baselines? What is the retraction used and what about its computational efficiency?\n\n2b) The main motivation (and the only considered applications) of the paper is robust training. However, the robust training problem is more commonly formulated as min-\\sum-max instead of min-max-\\sum, and there is a significant difference in optimizing these two objectives. The authors did not provide any justification as why they could switch the order of \\sum and max at will.\n\n\nBased on the above, I recommend rejection.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors provide a Riemannian version of gradient descent/ascent for min-max problems on manifolds. Assuming a tractable retraction mapping for the descent/ascent step, the authors provide a complexity analysis for finding a (local) saddle point in the spirit of Lin et al. (2020).

The paper received three negative recommendations and one positive, with all reviewers indicating high to expert confidence. After my own reading of the paper, I concur with the majority view that the paper does not clear the (admittedly high) bar for ICLR. After discussing the paper with the reviewers, the concerns that led to this recommendation are as follows:
1. On the proposed examples: it is not clear what exactly is the motivation for the DNN training example with orthonormality constraints on the weights. In the paper, $x$ is the vector of DNN weights, so it lives in some real space $R^d$. The authors subsequently assume it is constrained to live on some Stiefel manifold, but which one? The Stiefel manifold is the set of all orthonormal $r$-frames on $R^d$, and the formulation in Section 6 doesn't clarify things. Moreover, the papers cited by the authors either concern the initialization of the DNN or a regularization by an orthonormality/orthogonality penalty. This is quite different since DNN training typically involves at least some neurons with very large weights (which is of course disallowed if the weights are constrained to live on some "norm 1" subspace).
2. The presentation is often lacking in mathematical rigor: in a Riemannian setting, it is crucial to distinguish between the Riemannian distance function and the Riemannian norm. However, the two were used interchangeably at several points, and the authors' revision wasn't satisfactory in this regard - even the basepoint for the norm is missing in cases where it is not made clear from the context on which point the norm is considered.
3. The cost of applying retraction-based methods in DNNs is also unclear. On a Stiefel manifold, the only known retractions involve SVD, so they have a superlinear computational cost relative to the size of the input matrix. If the dimensionality of the input matrix is that of the parameter space of the DNN, the efficiency of the method seems somewhat limited.

The above concerns regarding DNN training are perhaps less important if we view this as a primarily theoretical paper. In that regard however, the novelty of this paper over that of Lin et al. (and other Riemannian minimization papers) is not clear, so I am forced to recommend rejection at this stage. That being said, I believe that a thoroughly revised version of this paper could ultimately be publishable at one of the top venues of the field, and I would strongly encourage the authors to pursue this.
Decision: Reject