Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing
Authors: Kangkang Deng
Jiachen Jin
Jiang Hu
Hongxia Wang
Venue: NeurIPS 2025 poster ()
Keywords: ADMM
manifold optimization
iteration complexity
adaptivity
Primary area: optimization

Abstract: We study the problem of minimizing the sum of a smooth function and a nonsmooth convex regularizer over a compact Riemannian submanifold embedded in Euclidean space. By introducing an auxiliary splitting variable, we propose an adaptive Riemannian alternating direction method of multipliers (ARADMM), which, for the first time, achieves convergence without requiring smoothing of the nonsmooth term. In contrast to conventional Riemannian ADMM methods that require exactly solving a nested subproblem at each iteration, our approach involves only one Riemannian gradient evaluation and one proximal update per iteration. Through careful and adaptive coordination of the stepsizes and penalty parameters, we establish an optimal iteration complexity of order $\mathcal{O}(\epsilon^{-3})$ for finding an $\epsilon$-approximate KKT point, matching the complexity of existing smoothing technique-based Riemannian ADMM methods. Extensive numerical experiments on sparse PCA and robust subspace recovery demonstrate that our  ARADMM consistently outperforms state-of-the-art  Riemannian ADMM variants in convergence speed and solution quality.

Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing
Kangkang Deng"
Jiachen Jin
College of Science
College of Science
National University of Defense Technology Changsha, CHINA
National University of Defense Technology
Changsha, CHINA
Ereedengg208@@miil.com
jinjiachen@nudt. edw.eudddedd.... edu.
Jiang Hu
Yau Mathematical Sciences Center
Tsinghua University
Beijing, CHINA mujiangopt@@maii com
Hongxia Wang
College of Science
National University of Defense Technology
Changsha, CHINA eew.eautttuuud..... wanghongxiadnuut. edu. cn
Abstract
We study the problem of minimizing the sum of a smooth function and nonsmooth convex regularizer over compact Riemannian submanifold embedded in Euclidean space. By introducing an auxiliary splitting variable, we propose an adaptive Riemannian alternating direction method of multipliers (ARADMM), which, for the first time, achieves convergence without requiring smoothing of the nonsmooth term. Our approach involves only one Riemannian gradient evaluation and one proximal update per iteration. Through careful and adaptive coordination of the stepsizes and penalty parameters, we establish an optimal iteration complexity of order (c-33) for finding an c-approximate KKT point, matching the complexity of existing smoothing technique-bart based Riemannian ADMM methods. Extensive numerical experiments on sparse PCA and robust subspace recovery demonstrate that our ARADMM consistently outperforms state-of-the-art Riemannian ADMM variants in convergence speed and solution quality.
1 Introduction
Optimization Riemannian manifolds has garnered significant interest due to its wide-ranging applications machine learning, statistics, signal processing, and beyond. While the theory and algorithms for smooth manifold optimization have been extensively developed (see [ [ 22 recent years have witnessed a growing need to address nonsmooth objectives, which arise naturally and semidefinite programming
in tasks such as sparse PCA (28 nonnegative PCA
50 27
45
Equual contribution. Correspnnding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Formally, we consider the nonsmooth optimization problem on Riemannian manifold
min f(x) + h(Ar).
(I)
#EM
where M is a Riemannian submanifold embedded in TR.", f: IR - IR. a continuously differentiable function, A _n + IR'e is linear mappings, h _ + (-30, +oo| is proper closed convex function. Hence, the objective function of (T) can be nonconvex and nonsmooth. By introducing an auxiliary variable y Az, one obtains the linear constrained problem
min f(x + h(y), s.t. Ar = y, x E M.
(2)
To tackle such constrained nonsmooth problems, a natural candidate the alternating direction method of multipliers (ADMM), which has emerged as a powerful framework for solving large-scall
structured optimization problems. One of the carliest attempts to extend ADMM to (2) is the manifold
ADMM (MADMM) proposed in (T,, which adopts the following iteration scheme:
Tk+1 = arg min (x) (Ak Ax yk) + P A1 Uk
#EM
2
yk++ arg min h(y) (AR.AAH+: v) + A y11?
A = d > p(Ar++1 1/+1))
where À denotes the Lagrange multiplier and p 0 is penalty parameter. In MADMM, the subproblem is a smooth Riemannian optimization task that can be solved by using any gradient- based Riemannian algorithm. while the y-subproblem admits closed-fome solution via proximal operator of h. Although this algorithm constitutes a direct generalization of the classical Fuclidean ADMM, its convergence has remained elusive due to the inherent nonconvexity of Riemannian manifolds. More recently, Li et al. (35) introduced a smoothing technique to reformulate the original nonsmooth problem into smooth approximation
min (xx + (Axx), #EM
where h₂ denotes the smooth approximation of h and is a smoothing parameter. They proposed a smoothed ADMM scheme for solving the surrogate problem (4) and established an ((1/e)) complexity bound. Building upon this idea, 49) further incorporated adaptive smoothing strategies, resulting in an improved algorithm. However, all these methods are designed specifically for smoothed formulations, which rely critically on smoothing parameters, rather than directly addressing the original nonsmooth problem.
In this work, fundamental question arises:
interested in the convergence analysis of original Riemannian ADMM A
Can we establish convergence of Riemannian ADMM for the original nonsmooth problem without relying on smoothing?
This question motivates our study. Our contributions can be summarized as follows:
We propose a novel adaptive RADMM (ARADMM) for nonsmooth optimization over compact Riemannian submanifolds. Unlike existing smoothing- based Riemannian ADMM methods, our approach achieves convergence without smoothing the nonsmooth regularizer. Moreover, our adaptive strategy dynamically updates the stepsize and penalty parameter during the iterations, avoiding the expensive exact subproblem solutions required by con- ventional Riemannian ADMM variants. Consequently, each iteration only requires one Riemannian gradient evaluation and one proximal computation, significantly reducing the per-iteration cost. Numerical experiments demonstrate the superior empirical performance of our ARADMM over existing ones.
Through careful and adaptive coordination of the stepsize and penalty parameter, we es- tablish an optimal iteration complexity of order O(c-3) for finding an c-approximate KKT point. This matches the best-known complexity achieved by smoothing- based Euclidean and Riemannian ADMM methods, while entirely avoiding the need for smoothing. A key technical innovation is the adaptive selection of dual step sizes and penalty parameters, which explicitly bounds the differences between multipliers by the norms of the correspond- ing primal iterate differences- an essential property for establishing convergence without requiring exact subproblem solutions.

---

Table I: Comparison of the oracle complexity results of several methods in the literature to our
method to produce an e-stationary point
Algorithms
Manifold
Iteration
Without smoothing
Single-loop
MADMM 31
compact
Yes
No
RADMM 35
compact
O
No
Yes
OADMM 49
Stiefel
No
Yes
this paper
compact
O
Yes
Yes
1.1 Related works
Most existing works focus on simplified instances of problem ( These works can be broadly categorized into three classes. First, subgradient and proximal point methods for geodesically convex problems have been studied in [2] 16 14, [0] 13]. 'hese algorithms typically require stronger assumptions-Suu
as geodesic convexity and often suffer from slower convergence in practice compared to other approaches. Second, proximal gradient-type methods, such as those in (9 225 26). apply in the special case where A I. Each iteration of these methods involves solving subproblem that lacks a closed-form solution, which is typically handled using semismooth Newton techniques. Third, primal-dual methods based on the augmented Lagrangian framework have been developed. including operator splitting algorithms [2], manifold-bard based augmented Lagrangian methods [12 [55] [1] [47 [48), and Riemannian ADMM variants [I] [35 49 [33] Among these, ADMM is particularly attractive due the separable structure of the objective and constraint in problem T which enables efficient and scalable updates.
In the case when the manifold M is specified by equality constraints c(x:) = O, e.g. the Stiefel manifold. Problem ( can be regarded as a constrained optimization problem with a nonsmooth and nonconvex objective function. Given that M is often nonconvex, we only list the related works case of that the constraint functions are nonconvex. Papers By 42)
propose and study the iteration complexity of augmented Lagrangian methods for solving nonlinearly constrained nonconvex composite optimization problems. The iteration complexity results they achieve for an e-stationary point are both Ó( ") More specifically, [42] uses the accelerated gradient method of 17 to obtain the approximate stationary point. On the other hand, the authors in 37 obtain such an approximate stationary point by applying an inner accelerated proximal method as in 8 30), whose generated subproblems
convex. It is worth mentioning that both of these papers make strong assumption about how the feasibility of an iterate is related to its stationarity. Lin et al. [38 propose an inexact proximal-point penalty method by solving a sequence of penalty subproblems. Under non-singularity condition, they show complexity result of Ō(e-)). More recently, some works 19 13. 20 apply ADMM algorithmic framework by penalizing the nonlinear constraint. However, those approaches do not exploit the underlying manifold geometry and essentially reduces to baselty-based methods.
In Table summarize complexity results and several existing Riemannian ADMM methods to produce an c-stationary point. We do not list the algorithm in (53) since the subproblem difficult and requires strong assumption the problem: the last block variable cannot appear in the nonsmooth objective. It can easily be shown that our algorithms achieve better oracle complexity results.
1.2 Notation
Let (-,-) and ||- be the Euclidean product and induced Euclidean norm. Given a matrix A, we use ||Al|] denote the Frobenius norm, ||A]]] := Eij |Aiy to denote the norm. For vector æ, we use ||æ||| and ||>||] to denote Euclidean norm and e, norm, respectively. The distance from z is denoted by dist(r, C) == minyec || wll- We use Vf(x) and gradf(a to denote the Euclidean gradient and Riemannian gradient of respectively. ||Al|oo olp denotes the operator norm of linear
operator A.
3

---

2 Preliminary
2.1 Riemannian optimization
An n--imenniioal smooth manifold M is an n-dimensional topological manifold equipped with smooth structure, where each point has a neighborhood that is diffeomorphism to the n-dimensional Euclidean space. The tangent space of a manifold M is denoted by T.M. In this paper, we consider the case that M is Riemannian submanifold of an Euclidean space E, the inner product defined as the Euclidean inner product: (M.. (2) tr Ez). The Riemannian gradient is given by gradf(u (z) M V fz)). where ff(x) is the Euclidean gradient, Pr,MM is the projection operator onto the tangent space T.M. The retraction operator is one of the most important ingredients for manifold optimization, which turns an element of M into point in M
manifold M is smooth mapping R. TM - M with the following properties. Let Rz T.M + M be the restriction of R. at x. It satisfies
Definition 2.1 (Retraction, []. A retraction
R2 (0x)) x, where 02 the zero element TMM,
(D,((0.)) = idr, M. where idr,M M is the identity mapping on T.MM
We also give the following definition of vector transport.
Definition 2.2 (Vector transport, D.. Given Riemannian manifold M, the vector transport Ty is operator that transports a tangent vector v E T.M to the tangent space T M, i.e. (T( E My In this paper, we assume _ isometric.
We have the following Lipschitz-type inequalities the retraction the compact submanifold. Proposition 2.1 (66, Appendix BJ). Let R. be retraction operator compact submanifold M. Then, there exist two positive constants ar, 3 such that for all x E M and all u E T,M, we have
|R x|| S allull,
[[R[(u) - x ull S @|]
(5)
2.2 Stationary point and proximal operator
Next we give the definition of e-stationary point for problem ( Let us first introduce the Lagrangian function .M E _" R of (T):
1(x, y. A) = f(x + h(y) - Ax - y)
(6)
where is the corresponding Lagrangian multiplier. Based on the KKT condition, we give the definition of e-stationary point for (T:
Definition 2.3. We say x M an e-stationary point of ① there exists y, z E R such that
PP.M (Vf(x) A² Sc,
dist (oat(-A, x- Oh(y)) Se,
| yll Se.
In other words. (z, A) is an e-KTT point pair of Note that setting e = 0 gives the KKT condition problem ①
The following lemma gives the definition of proximal operator for convex function, and the related property.
Lemma 2.1. [ Lemma 3.3] Let be convex function. The proximal operator of with parameter is given by
prox,xx (v) arg min SERm
[(()) 1 || v112?
(8)
211
Moreover, if is l Lipschiit continuous, it holds that
|| prox (x))) S pén
(9)

---

3 Riemannian ADMM
Throughout this paper, we make the following assumptions.
Assumption 3.1. The following assumptions hold:
(i) The manifold M is a compact Riemannian submanifold embedded in R f(z) and h(x) are both lower bounded, and let inf, f(x) -00 and h, inf h(x) > oc.
(ii) The function f is L--iischiitz coninuous and E on M. The finntionn h is convex and Lippiihciitz continuous.
(iii) The linear mapping A satisfies || 5.
Assumption 3. (i) includes many common manifolds, such as sphere, Stiefel manifold and Oblique manifold, etc. This implies M a bounded and closed set, i.e., there exists a finite constant 'D such that D = ma I| yll. Assumption 3.1 (i) implies that for any E M, it holds that
[V - Vf(ii) & vll-
(10)
3.1 Challenges in bounding dual updates Riemannian ADMM
The convergence analysis of ADMM algorithms for nonconvex problems typically relies on estab- lishing a sufficient descent property of the augmented Lagrangian (AL) function, which serves as potential function. However, since ADMM belongs the class of primal-dual algorithms, the update of the dual variables introduces an ascent term, commonly expressed as || Aull. Controlling this ascent term critical for ensuring convergence.
In the Euclidean setting, this term is usually bounded via the optimality condition of the subproblem associated with the primal variable, see, for example, 446 [8 4. Consider the iterative scheme in (3. When the manifold M = IR", the optimality condition for the z-subproblem at iteration & reads
(((x=1) + pA" (Arx+1 yk) A Ax = 0.
Taking differences of the optimality conditions at iterations and [|A++1 Aæl by the difference of corresponding primal iterates using the Lipschitz continuity of f.. However, in the Riemannian setting, the corresponding optimality condition involves projections onto tangent spaces:
one can derive bound on
P Prenii M (Vf(x++1) PA" (AT Vh) A²)x)) 0.
Due to the nonlinear geometry of the manifold, the tangent space changes at each iteration, making it impossible to directly apply the difference technique used in the Euclidean case. This leads to significant challenges in bounding the difference between dual variables, as the projection operators prevent the necessary aligmment of optimality conditions across itcrations.
A common workaround is to smooth the nonsmooth term associated with the y-variable. By replacing the nonsmooth regularizer h with a smooth approximation hus one can leverage the Lipschitz continuity of the gradient Vh, to bound the difference of multipliers. Specifically, the optimality condition for the smoothed y-subproblem becomes
0 (hy((++1) + p(Ar= Mb++1) - A
Thus the desired bound on the multipliers be obtained by the Lipschitz continuity of Vhy- Please refer to [35 49 for more details. However, this approach fundamentally changes the problem structure from nonsmooth optimization smooth optimization, and various gradient-bases based methods can used instead of ADMM. For instance, 41 developed a Riemannian homotopy smoothing algorithm based this idea.
In contrast, our approach works directly with the original, nonsmoothed ADMM framework, without introducing any smoothing to the problem. To overcome the challenge posed by the changing tangent spaces and nonsmooth regularizer, we introduce an adaptive strategy for selecting the dual stepsizes and penalty parameters. Specifically, we introduce adaptive penalty parameter Pk and replace the
5

---

Leveraging the properties of the Algorithm Adaptive Riemannian ADMM for solving TT.
Input: initial point To, yo, Ao. Po. Yo. parameters Cps Cyy
1: for k = 0....
do
2: Update auxiliary variable Vk+1 via
Uk+1 = arg min Cp, (Iks, U, As)- yeRu
(14)
3: Denote (x)x) == Ppe (2, M1+1 Ax) and obtain T&+11 by single gradient step:
#k+1 = Res. (=7ggradd
(15)
4: Update the dual step size 7 via
(1
7o Arro yol log
7k+1 min
[|Ar4+1 - yk++ (1: + 1)2 log(h: + 2) 1/3 log (k: + +1)
(16)
5: Update the dual variable Ak+1 via
A6+1 dx 7k- (Ar++1 - yk+1).
(17)
6: end for
Output: (Z yk: Ak).
original dual stepsize with 7 in original Riemannian ADMM Moreau envelope, we then obtain
Ax+11 Ak 7k+ (ATK+1
11++1)
A
As Pl:
Au )
Au
7
A
proxn/0s
A
+ 1 Fx.
-
Pk: The first term can be bounded using properties of the proximal operator and the Moreau envelope, shown in (9. To further control [A we design the dual stepsize *k+1 adaptively, ensuring that the multiplier difference bounded by the primal iterate difference. More details are referred to Algorithm and Lemma 3.1
Pk:
3.2 Adaptive Riemannian ADMM
We construct the corresponding augmented Lagrangian function:
(x = f(x) h(y) Ar y) + + I1
y/1
(11)
Algorithm D details the iterative process. For the update rule of the dual variable A8+1. we use different sequence {mk} to replace original sequence }, and result in the following update:
Ak+1 A 7h+ (Arx+1 4k++1)
(12)
Here, we refer to 74+1 as the dual step size, which is updated by the following form:
7++1 = min [|Ax++1 | + 1)a log(k 2) k1/3 log 2 )
70 Amo - soll log22
(13)
Our algorithm alternately updates the variables in the order of (y, x, A), which follows from 223 The increasing sequence of penalty parameters Pk and the dual update are responsible for continuously enforcing the constraints. The particular choice of dual step sizes "ik in Algorithm ensures that the difference between the dual variables Å and A remains bounded, which is crucial for the convergence analysis.
Thanks to the careful choice of the penalty parameter and step size, we establish the following key lemma, which ensures that the difference between successive dual variables, || >xel. can be effectively controlled.

---

Lemma 3.1.
Let Assumptions 3.1 hold. Suppose the sequence {ak, du A is generated by the
Algorithm 7
The following inequality holds
70 ||A woll
| S
Amax-
(18)
Moreover we have that
1 - ARll S
Th+1 (fa + Amax) + 74+10A xxll-
(19)
Pk
Proof of Lemma 3.1
We first show that d bounded. By step in Algorithm I we have
k++
|A++1ll
S
All - yell S
ul allAArr - vel
(20)
1 (1 + 1)2 log(1 + +
T ||A20 yoll Amax
S rollAAoo voll log22
n² where the last inequality utilize that log(1 2) for 2 1 and Ei=1 (L+1)2 Again using one can bounds the difference between A and Ap:
step 5 in Algorithm [
|| Axll = 71 11++IlAAR4+ MK+1ll
AR Yo+1 A1lAllolllppptt x&ll +-++11 Pa
d
- 1k++1
Pk
d
prox (Axx An )I1 714110111 xxll + 7h+
Ak
S Yh+ (AAr
1ll
ph
Pk
S Th+1 (Cn + Amax) + 1k+10A||TKet - -xll,
Pk
(21)
where the first inequality uses |Alllop σ from Assumption 3.1 and the update rule of y in [4 the second inequality follows from and (00). The proof is completed.
Now we provide the main convergence result of our algorithm ARADMM. In particular, we show that under certain assumptions, the ARADMM can achieve a oracle complexity of O(c-3).
Theorem 3.1. Suppose that Assumptions 3./ hold. Let the sequence {IK,, Uk, AR AR) be generated by
Algorithm 7
Let us denote A
Ax-1 Pk- (Ax yk), Ph 1/3 and Ty. C, 1-/3, where
Cr, Cp satisfy
1 1
c, 5 min
}. Cp 1
(22)
O' M 16c,
where C C= (alp + Q) + aelss 0)), M = a² (Los + 02) + 2G3, and G.o. 3 are given in 5 and Lemma A.2 I are defined in Lemma A.I there exists & E [ K] such that
Then for any given positive integer K >
8Vg
IPr...((-A A" A'd) + grad
(K + 1)
Ve,
dist( Se.. ah(y))) < AowwVG
(K + 1113/ V
| -ell S S CK - 22/ + 2(Er + Amax)
(K - 2) -1/3
Cp
(23)
where G is constant given in the proof.
Theorem 3.1
establishes that, given > O. our algorithm achieves an iteration complexity of O -3).
Since Algonthm is single-loop method that requires only one gradient evaluation of f. one
7

---

100
500
10
500
5000
50C
WADWW
1MKDMM
NARAMI
14ADMM
RACMM
TVACMAAA
RADKM
ATTABMM
AFADME
CADKIE
102
SCV
160
520
102
50C
14439114
1447780
ARATRUM CACMM
DALVMM
Donake
(a) 400, p 50
(b) 400, p 100
800, 50
(d) 800, p 100
Figure 1: Comparison with ADMM-type methods for solving (24) with different (n. p), m = n and J 0.01.
computation of the proximal operator and retraction operator per iteration both of which are computationally inexpensive-iie overall operation complexity is of the same order as its iteration complexity.
We would like to clarify that this condition in (2) is not essential. For example, since Tk 11/3, the condition on C, is essentially imposed to ensure that Tı satisfies the required bound. This condition can always be satisfied after sufficiently large number of iterations without requiring c,. That is, for any Cr, there exists an integer ko > such that for all h >
1/3
ko, Tk satisfies the condition.
4 Applications and Numerical Experiments
In this section, we investigate the numerical performance of the proposed algorithm and report comparative results with existing methods. All experiments performed in MATLAB R2023b 64-bit laptop equipped with Intel 19-1999-0000 13900HX CPU and 32.0 GB RAM. We denote the final objective values "obj"" and report the CPU time in seconds. All the results averaged across 10 repeated experiments with random initializations.
4.1 Sparse Principal Component Analysis
Sparse principal component analysis 28 29 is cornerstone technique for high-dimensional data analysis, identifying principal components with sparse loadings. Given data matrix A E mx the problem of recovering the top p (p < min (m, n)) sparse loading vectors is formulated as:
min F(X) = Tr A AX) + x|X(,, X St(n,,),
(24)
where > 0 is regularization parameter, Tr(X) denotes the trace of matrix X and St(n. p) (X E R.xp, T X = ) is the Stiefel manifold.
We evaluate our proposed Algorithm to solve (24) and compare it with four ADMM-type methods: SOC [33], MADMM [31], RADMM [35] and OADMM [49]. For ARADMM, we set Yoo = C. = 50, Po = C, = and C, 0.2. For OADMM, we set & 0.1 and other parameters are the same as their originals. For the other three algorithms, we follow the same settings as [35), where the parameters optimized through grid searches. All algorithms use identical random initializations and terminate when [F(x+11) F(Xx)] < 10-8 or after 500 iterations. The data matrix A E IR mxx is generated randomly and the entries follow the standard Gaussian distribution. Figure I shows the objective value versus iterations and CPU time, where f the minimum value across all methods. ARADMM achieves significantly lower objective values and converges faster than other ADMM.
We also compare ARADMM with the Riemannian subgradient method (RSG)
36 and the
accelcrated manifold proximal gradient method (AManPG) (24.. We set the step size 7 0.005

---

Table 2: Comparison with RSG and AManPG for solving (4)
with μr 0.01.
Settings
RSG
AManPG
ARADMM
(n, m, p)
Obj
CPU
Obj
CPU
Obj
CPU
(300, 20, 8)
-3,9517
0.7970
-4.2671
0.8555
-4.4071
0.4264
(400, 30, 10)
-5.5595
1.1105
-5.8129
1.0796
-6.0378
0.5383
(500, 40, 12)
-7.1168
1.9584
-7.3048
1.3820
-7.6569
0.6888
(600, 50, 14)
-7.2259
2.5911
-7.4608
1.7482
-7.9029
0,8701
Table 3: Comparison with ALM-type methods for solving 24). Here "Spa" denotes the sparsity level,
defined as the proportion of entries with magnitude less than 10
Settings
ALMSSN
ALMSRTR
ARADMM
(n, m,P.
Obj
CPU
Spa
Obj
CPU
Spa
Obj
CPU
Spa
(1500, 20, 8, 0.5)
6,0212
1.6349
93.10
4.0169
1.2679
98.38
3,9552
0.9417
99.93
(2000, 40, 10, 0.6)
8,9390
2.7063
94.03
5.9553
1.9281
99.85
5,9190
1.3272
99.95
(2500, 60, 12, 0.8)
9,4527
2.9387
99.61
9.5296
3.6644
99.95
9.4747
1.8394
99.96
(3000, 80, 15,
15.7085
4.7114
94.65
14.8418
4,4791
99.96
14.8470
2.2669
99.97
for RSG, while the code of AManPG is provided by [25]. For ARADMM, we set 70 = = = 10
Po = 100, Cp = and C, 10-4 The termination rules are the KKT conditions with an accuracy tolerance of 10- Table 2 shows that ARADMM consistently achieves lower objective values at significantly faster rate than RSG and AManPG, demonstrating both efficiency and solution quality.
Finally, we compare with two ALM-type algorithms: ALMSSN 55 and ALMSRTR [51] which use a semismooth Newton method and a Riemannian trust region method, respectively, to solve the augmented Lagrangian subproblem manifolds. The codes for these algorithms obtained from related work. The parameters for ARADMM and the termination rules follow the same settings as in above experiments. From Table we can see that ARADMM generates sparse solutions faster than ALMSSN and ALMSRTR, especially when is large.
4.2 Regularized Linear Classifier Over Sphere Manifold
Consider classification task involving training pairs (a;, by) where a, Rh and b; E (-1,1) for all i E [N]. The objective is to estimate a linear classifier parameter x on the sphere manifold
Sm-1 = {xr E I r rTr
1} that minimizes smooth nonconvex loss
52
with t1-
regularization:
Σ 1(1-T+eppl exp( da T Ta;)
min 2ES
+ /||/r|11,
(25)
For data generation, the true parameter x sampled from (0, Im). and projected onto 1 The features J.V are sampled independently and the labels b, are set to if x a, + E, >> 0, where noise ~ N (0, 2²), and -1, otherwise. All algorithms use the identical random initialization and terminate when [x++)1) F(Xx)] < 10-8 or after 500 iterations, with μ 0.2 fixed in (25).
We set 2o = Pu C, = 100, cp = and C₂ = 0.05 for ARADMM, and use the same settings as in the SPCA experiments for OADMM. For the other methods, step size 7 = 0.01. From T we can see that ARADMM and MADMM quickly decrease the objective value, whereas both ARADMM and SOC achieve lower objective value of the outputs. Moreover, ARADMM is more advantageous than existing methods in more challenging scenarios. In short, ARADMM is more efficient in terms of the CPU time and objective value for test instances.
penalty parameter p 150 and
4.3 Robust Subspace Recovery and Dual Principal Component Pursuit
Robust subspace recovery (RSR) 34 40 addresses the challenge of fitting a linear subspace to data corrupted by outliers. Given data set Y OJ E (p)+ where columns of X e Raxp. span a d-dimensional inlier subspace S, columns of O E pp represent outliers without linear

---

Table 4: Comparison with ADMM-type methods for solving 25
Setrings
SOC
MADMM
RADMM
OADMM
ARADMM
mm n²)
Obj
CPU
Obj
CPU
Obj
CPU
Obj
CPU
Obj
CPU
(200, 1000,
0.70044
1.1009
0.7340
0.0729
0.7340
0.0876
0.7282
0.1024
0.7370
0.0507
5000.
0.6877
2.2876
0.8267
0.1701
0.8267
0.1864
0.7288
0.2799
0.6875
0.1073
(600, 10000. 10)
0.6469
7.8231
0.9216
0.6692
0,9216
0.7153
0.6665
1.0664
0.6464
0.4197
(800, 20000, 50)
0.6606
30.7367
1.0398
2.2673
1.0396
2.7062
0.6871
2.7062
0.6602
1.4167
Table 5: Comparison with ADMM-type methods for solving 27
Settings
SOC
MADMM
RADMM
ARADMM
(ra, Pl: P2)
obj
CPU
obj
CPU
obj
CPU
obj
CPU
(30, 100, 500)
286.5284
1.4835
286.4820
0.7677
286.4599
0.0486
286.3336
0.0057
(40, 125, 750)
363.2060
2.6384
363.1336
1.4823
363.0977
0.0136
362.8826
0.0119
(50, 150, 1000)
423.6242
2.7054
423.5769
2.3196
423.5352
0.0378
423.2783
0.0136
6
(30. 100, 500)
431.2076
2.4063
431.1518
1,4842
431.1275
0.0160
431.0405
0.0089
(40, 125, 750)
542.7145
2.8961
542.6425
0.7155
542.5957
0,0540
542.4900
0,0112
(50, 150, 1000)
637.8058
2.6239
637.7484
0.7584
637.6906
0.0972
637.3598
0.0176
structure, and T E R( +pp) an unknown permutation matrix, the goal is to recover S or cluster the points into inliers and outliers. Dual principal component pursuit (DPCP) [44 is recently proposed approach to RSR that seeks a hyperplane containing all inliers via the nonconvex nonsmooth optimization:
min Y x 111,, s.t. ||>|| = 1.
(26)
Here Y E Rnxp is given matrix. In 44 56 it is shown that solving (26) yields vector orthogonal to S, provided that outliers p2 is at most of the order of O(p)). For known d, one can recover S as d orthogonal hyperplanes containing X, which amounts to solve the
the intersection of the p following matrix optimization problem:
min XER*XP
F(X) == ||Y |||TXl XII1, s.t. X
(27)
We focus on the DPCP formulation (7 of the RSR problem, and compare our ARADMM with
SOC [33), MADMM (31] and RADMM [35]. For ARADMM, we set Cp = 1, To 700, Pu
G. 10-2 and C, 0.6. The codes of other methods provided by (35), where we set the stepsize 10-5, All methods terminate when [F((++1) F(Xx)l < 10-6 after 5000 iterations. Table S shows that, for all cases, ARADMM consistently achieves lower objective values and very shorter computation times than SOC, MADMM and RADMM. This efficiency is due to: ARADMM has a cheap per-iteration complexity, where all steps have closed-fome solutions; the adaptive penalty parameter P and the dual step size 7 dynamically balance the enforcement of constraints with the convergence of the algorithm in an effective manner. More numerical results see Appendix
Conclusion
Our work introduces an adaptive Riemannian ADMM (ARADMM) that, for the first time, solves composite optimization on compact manifolds with nonsmooth regularizer without any smoothing, while requiring only one Riemannian gradient evaluation and one proximal update per iteration. By dynamically tuning both stepsizes and penalty parameters- and carefully relating dual increments to primal changes- prove that ARADMM attains the optimal O iteration complexity for finding an e-approximate KKT point, matching the best-known guarantees smoothing- based methods at a far lower per-iteration cost. Extensive experiments sparse PCA and robust subspace recovery confirm that our adaptive scheme converges faster and yields higher- higher-quality solutions than existing Riemannian ADMM variants.
Limitations: While ARADMM demonstrates strong theoretical guarantees and practical performance, our current analysis is limited to general nonconvex nonsmooth setting without leveraging specific structural properties such as the Kurdyka-E.ojasiewie. (KI.) inequality, which could potentially yield sharper convergence rates.
10

---

Acknowledgments
We sincerely thank four anonymous reviewers for their valuable and constructive feedback, which has greatly improved our work. This work was supported by the following grants: the National Key Research and Development Program of China (No. (020YFA0713504) the National Natural Science Foundation of China (Grant No. 12471401, 12401419).
References
[1] P.-A. Absil, Mahony, and R. Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton, NJ, 2008.
[2] Glaydston Bento, Orizon P Ferreira, and Jefferson Melo. Iteration-complextty gradient, subgradient and proximal point methods on Riemannian manifolds. Journal of Optimization Theory and Applications, 173(2):548-5622 2017.
[3] Axel Böhm and Stephen J Wright. Variable smoothing for weakly convex composite functions. Journal of Optimization Theory and Applications, 188(3):628 649, 2021.
[4] Radu Ioan Bot and Dang- Khoa Nguyen. The proximal alternating direction method of multi- pliers in the nonconvex setting: convergence analysis and rates. Mathematics of Operations Research, 45(2):682-712, 2020.
[5] Nicolas Boumal. An introduction to optimization on smooth manifolds. Cambridge University Press, Cambridge, England, 2023.
[6] Nicolas Boumal, P-A Absil, and Coralia Cartis. Global rates of convergence for nonconvex optimization on manifolds. IMA Journal of Numerical Analysis, 39(1):1-33, 2019.
[7] Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95(2):329-357, 2003.
[8] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 28(2): 2018.
[9] Shixiang Chen, Shiqian Ma, Anthony Man-Cho So, and Tong Zhang. Proximal gradient method for nonsmooth optimization over the Stiefel manifold. SIAM Journal on Optimization, 30(1):210-239, 2020.
[10] Glaydston de Carvalho Bento, João Xavier da Cruz Neto, and Paulo Roberto Oliveira. A new approach to the proximal point method: convergence on general Riemannian manifolds. Journal of Optimization Theory and Applications, 168(3):743-77) -55, 2016.
[11] Kangkang Deng, Jiang Hu, Jiayuan Wu, and Zaiwen Wen. Oracle complexities of augmented lagrangian methods for nonsmooth manifold optimization. arXiv preprint arX5v:2404.05/21, 2024.
[12] Kangkang Deng and Zheng Peng. A manifold inexact augmented lagrangian method for nonsmooth optimization on riemannian submanifolds in euclidean space. IMA Journal of Numerical Analysis, 1368)11653-1684 2023.
[13] Lahcen El Bourkhissi, Ion Necoara, and Panagiotis Patrinos. Lincarized admm for nonsmooth nonconvex optimization with nonlinear equality constraints. In 2023 62nd IEEE Conference on Decision and Control (CDC), pages 7312-7311 IEEE, 2023.
[14] OP Ferreira and PR Oliveira. Subgradient algorithm on Riemannian manifolds. Journal of Optimization Theory and Applications, 97(1):93-104, 1998.
[15] OP Ferreira and PR Oliveira. Proximal point algorithm on Riemannian manifolds. Optimization, 51(2):257-270, 2002.

---

[16] Orizon P Ferreira, Mauricio Silva Louzeiro, and Leandro F Prudente. Iterationcommleextty of the subgradient method on riemannian manifolds with lower bounded curvature. Optimization, 68(4))713-729, 2019.
[17] Saeed Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Progrumming. 156(1-2):59 99, 2016.
[18] Ke Guo, DR Han, and Ting-Ting Wu. Convergence of alternating direction method for minimiz- ing sum of two nonconvex functions with linear constraints. International Journal of Computer Mathematics, 14(8))6653-166) 2017.
[19] Le Thi Khanh Hien and Dimitri Papadimitriou. An inertial admm for class of nonconvex composite optimization with nonlinear coupling constraints. Journal of Global Optimization. 89(4):927-948 2024.
[20] Le Thi Khanh Hien and Dimitri Papadimitriou. Multiblock admm for nonsmooth nonconvex optimization with nonlinear coupling constraints. Optimization, pages 1-26, 2024.
[21] Le Thi Khanh Hien, Duy Nhat Phan, and Nicolas Gillis, Inertial alternating direction method of multipliers for non-convex non-smooth optimization. Computational Optimization and Applications, 83(())247-285, 2022.
[22] Jiang Hu, Xin Liu, Zai-Wen Wen, and Ya-Xiang Yuan. A brief introduction to manifold optimization. Journal of the Operations Research Society of China, 8(2): 248, 2020.
[23] Feihu Huang, Songcan Chen, and Heng Huang. Faster stochastic alternating direction method of multipliers for nonconvex optimization. In International conference on machine learning. pages 2839-28445 PMLR, 2019.
[24] Wen Huang and Ke Wei. An extension of fast iterative shrinkage-threshollding algorithm to riemannian optimization for sparse principal component analysis. Numerical Linear Algebra with Applications, 29(1 (9229994 2022.
[25] Wen Huang and Ke Wei. Riemannian proximal gradient methods. Mathematical Programming, 194(1)331--413, 2022.
[26] Wen Huang and Ke Wei. An inexact Riemannian proximal gradient method. Computational Optimization and Applications, 85(1): 2023.
[27] Bo Jiang, Xiang Meng, Zaiwen Wen, and Xiaojun Chen. An exact penalty approach for optimiza- tion with nonnegative orthogonality constraints. Mathematical Programming, 198(1):855-897, 2023.
[28] Ian T Jolliffe, Nickolay T Trendafilov, and Mudassir Uddin. A modified principal component technique based on the LASSO. Journal of computational and Graphical Statistics, 12(3):531- 547, 2003.
[29] Michel Journée, Yurii Nesterov, Peter Richtárik, and Rodolphe Sepulchre. Generalized power method for sparse principal component analysis. Journal of Machine Learning Research, 11())5177-533, 2010.
[30] Weiwei Kong, Jefferson G Melo, and Renato DC Monteiro. Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. SIAM Journal on Optimization, 29(4):2566-259) 2019.
[31] Artiom Kovnatsky, Klaus Glashoff, and Michael M Bronstein. Madmm: generic algorithm for non-smooth optimization on manifolds. In Computer Vision-ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part V 14, pages 680-696. Springer, 2016.
[32] Rongjie Lai and Stanley Osher. A splitting method for orthogonality constrained problems. Journal of Scientific Computing, 58(2):331444,, 2014.
12

---

[33] Rongjie Lai, Zaiwen Wen, Wotao Yin, Xianfeng Gu, and Lok Ming Lui. Folding-fre free global conformal mapping for genus-0 surfaces by harmonic energy minimization. Journal of Scientific Computing, 58(3):705-725, 2014.
[34] Gilad Lerman, Michael B McCoy, Joel A Tropp, and Teng Zhang. Robust computation of linear models by convex relaxation. Foundations of Computational Mathematics, 15(2):363 410, 2015.
[35] Jiaxiang Li, Shiqian Ma, and Tejes Srivastava. A Riemannian alternating direction method of multipliers. Mathematics of Operations Research, 0(0): 2024.
[36] Xiao Li, Shixiang Chen, Zengde Deng, Qing Qu, Zhihui Zhu, and Anthony Man-Cho So. Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods. SIAM Journal on Optimization, 31(3)1605- 2021.
[37] Zichong Li, Pin-Yu Yu Chen, Sijia Liu, Songtao Lu, and Yangyang Xu. Rate-improved inexact augmented Lagrangian method for constrained nonconvex optimization. In International Conference on Artificial Intelligence and Statistics, pages 2170-2178. PMIR, 2021.
[38] Qihang Lin, Runchao Ma, and Yangyang Xu. Inexact ppoint penalty methods for constrained non-convex optimization. arXiv preprint arXiv: 1908. / 1/518, 2019.
[39] Zhaosong Lu, Sanyou Mei, and Yifeng Xiao. Variance-reducel first-order methods for deter- ministically constrained stochastic nonconvex optimization with strong convergence guarantees. arXiv preprint arXiv:24099 099009906, 2024.
[40] Tyler Maunu, Teng Zhang. and Gilad Lerman. A well-tempered landscape for non-convex robust subspace recovery. Journal of Machine Learning Research, 20(1):1348-140) 2019.
[41] Zheng Peng, Weihe Wu, Jiang Hu, and Kangkang Deng. Riemannian smoothing gradient type algorithms for nonsmooth optimization problem on compact Riemannian submanifold embedded in Fuclidean space. Applied Mathematics & Optimization, 88(3):1332, 2023.
[42] Mehmet Fatih Sahin, Armin Eftekhari, Ahmet Alacaoglu, Fabian Latorre Gómez, and Volkan Cevher. An inexact augmented Lagrangian framework for nonconvex optimization with nonlin- ear constraints. Proceedings of NeurlPS 2019, pages 13966-13978, 2019.
[43] Hiroyuki Sato. Riemannian optimization and its applications. Springer Cham, Cham, 2021.
[44] Manolis C. Tsakiris and René Vidal. Dual principal component pursuit. Journal of Machine Learning Research, (9(1)6644732, 2018.
[45] Yifei Wang, Kangkang Deng, Haoyang Liu, and Zaiwen Wen. A decomposition augmented Lagrangian method for low-rank semidefinite programming. SIAM Journal on Optimization, 33(3): 2023.
[46] Yu Wang, Wotao Yin, and Jinshan Zeng. Global convergence of ADMM in nonconvex nons- mooth optimization. Journal of Scientific Computing, 78(1):29-63, 2019.
[47] Meng Xu, Bo Jiang, Ya-Feng Liu, and Anthony Man-Cho So. A Riemannian alternating descent ascent algorithmic framework for nonconvex-linear minimax problems on Riemannian manifolds. arXiv preprint arXiv:2409.188 19588, 2024.
[48] Meng Xu, Bo Jiang, Ya-Feng Liu, and Anthony Man-Cho So. On the oracle complexity of a Riemannian inexact augmented Lagrangian method for nonsmooth composite problems over riemannian submanifolds. Optimization Letters, pages 1-19, 2025.
[49] Ganzhao Yuan. Admm for nonsmooth composite optimization under orthogonality constraints. arXiv preprinl 2405,, 2024.
[50] Ron Zass and Amnon Shashua. Nonnegative sparse PCA. Advances in Neural Information Processing Systems, pages 1561-1568, 2006.
[51] Chenyu Zhang, Rufeng Xiao, Wen Huang, and Rujun Jiang. Riemannian trust region methods for sc 1 minimization. Journal of Scientific Computing, 101(2)::2, 2024.
13

---

[52] Dewei Zhang and Sam Davanloo Tajbakhsh. Riemannian stochastic variance-reduced cubic regularized newton method for submanifold optimization. Journal of Optimization Theory and Applications, 196(1):324-3111 2023.
[53] Junyu Zhang, Shiqian Ma, and Shuzhong Zhang. Primal-dual optimization algorithms over rie- mannian manifolds: an iteration complexity analysis. Mathematical Programming, 184(1):445- 490, 2020.
[54] Lei Zhao, Musa Mammadov, and John Yearwood. From convex to nonconvex: a loss function analysis for binary classification. In 2010 IEEE international conference data mining workshops, pages 1-21-1 IEEE, 2010.
[55] Yuhao Zhou, Chenglong Bao, Chao Ding, and Jun Zhu. A semismooth newton based aug- mented lagrangian method for nonsmooth optimization matrix manifolds. Mathematical Programming, 201(1):1-61, 2023.
[56] Zhihui Zhu, Yifan Wang, Daniel Robinson, Daniel Naiman, Rene Vidal, and Manolis Tsakiris. Dual principal component pursuit: Improved analysis and efficient algorithms. Advances in Neural Information Processing Systems, pages 2175-21828 2018.
A Useful lemmas
The following lemma shows that the Lipschitz continuity of (() can be deduced by the Lipschitz continuity of V (x)).
Lemma A.1. Suppose that M a compact submanifold embedded in the Euclidean space, given
I E M and u T.M, the vector transport 'T is defined as T (u) == ( where y = Rx(E). Denote ( := maxpecom(M) |DDRR(()]] and G == m M [V)() Let Lp be the Lipschitz conslunt of PT,M over E EM in sense that for any x. M, IR"
[PI..MEE) -r), -pllE|||== vll.
(28)
For a function f with Lipschitz continuous gradient with constant L, i.e. [V vf(y)) 1
T| yIl, then we have that
[gradf(x)) Ty" (gradf(w))) S (laL, + + + aL)|Ell.
(29)
Next, provide the definition of retraction smoothness. This concept plays crucial role in the convergence analysis of the algorithm proposed in the following section.
Definition A.1. 16 Retraction smooth] A function f : -M- + IR is said to be retraction smooth (short to retr-smooth) with constant and a retraction R, if for v x. M it holds that
f(v) S f(x) + (gradf(x) n) + 2 |nnl
(30)
where n E T,M and = RT(
We next demonstrate that &u (x) is retr-smooth with some constant La by Definition A.1 The Euclidean gradient V (x) has the following form:
<d fz)) + Pr.A((Ar - uk+1 - An/pu).
(31)
The following lemma provides the essential insight.
Lemma A.2. Suppose that Assumption 3.7 holds. of L, there exists finite M such that 4 is retr-smooth in the sense that
Mp 2
(2) S T (x) (n. grad
||nl
(32)
for all 1) E T.M, where M = a² (lv, + 2 + 2G,3
Proof. By Assumption 3.1 one can easily shows that V is Lipschitz continuous with constant E + 3 Since V is continuous on the compact manifold M. there exists G > 0 such that [x)]l S G for all æ M and any l: > 0. Then the proof is completed by combining 5 with Lemma 2.7 in (6).
14

---

B Proof of Section 3.2
We now give the following descent lemma in term of augmented Lagrangian function.
Lemma B.1. Suppose that Assumptions
3.1 hold. Let the sequence {Ik, Uk. Ae k== be generated by
Algorithm 7 Let Pk c,k2/8 and Th C, 1/3, where or satisfies
1
C S M C 21
(33)
where M is defined in Lemma 3.1 and G, a. B are defined in Lemma A.2 Then
Cps+1 (Ik+1: Yk- 26+1) Ppz (Ixx yk: Ak)
1
+
3
11 dall
Tk graddppo. (0k, yk-1, 2x) 2x) 11?
(34)
Yk+1
Proof. By the step 2 in Algorithm I we have
Pp (Tk Mk+1, 2&) S Cpp (oks, yk: AR).
(35)
It follows from 15 and Lemma A.2 that
M Mp
2x - 2 (xx) + ((*x) 7ggadd (xx)) + I tb (xx)
(
2
(36)
Th
2
where the second inequality uses T I Mrr This is due to the fact that Ps cakkk/ and e, satisfies Therefore, we have from the definition Φy Algorithm| Ithat
pp (IK+1, Uk+1, )x) Pp (IK,, Uk+1, AE) 2
Ilgrad (0K, UK+1, (37)
For the dual variable, it follows from 12 that
pp (IR41, 11 AR+1) Lpx (3 24 An)
|| Aull
(38)
Yk+1
Combining 35 37 and (38), we have
fpet1 (#k+1, yk+ ) pp (Ik; yk: Aa)
Sp (IK+1, 194+1,94+1: AR+1) f.p (IK+1; 11-11: AK+1) Lo (xu+1: yk-1 dut1) Lon (I yku 2k)
Pk PK+1
||A0411 11+1 + Y641
|| - -xal12 211=_
Tk
Iggrad... Spu (0k, Bk+1, At) 11?
2
2
Mk+ Pk
||
-
11 +
||++11
Ax11
Tk Ilgrad A6t
272+1
7k+1
(39)
where the last inequality uses (12). Now we bound the first term. Consider p(x) x 1/3 it follows from the first order characterization that p(x + 1) I p(x) + p''(2) = 1/3 + t/= 2/3 Then we have that
ct
Pk+1 - Ps ((k + 1)1/3 k113) ) < Cpk 2/3
3
3 pk
Plugging this into 39
completes the proof.
Lemma B.2, Suppose that Assumptions 3.1 hold. Let the sequence {xK, yks de jK be generated by
Algorithm] 1 Let us denote X > Pk (Arx - yk). Ph: 1/3 and T = c, 1/3, where
-1/3,
C, and cp satisfies
C, S mint O M
c, 1.
(40)
where C' is defined in the proof and M is given in Lemma A.2 Then
(Pr,,Mt (M-MMMAAA AA Ax) + grad (xx)) < 2 gradC (I 1, yk (x-1) ||, dist( - Ax. Th(
(41)
< a
pr agaalgradCCp.... (0k yke dx-1) ll,
(42)
En + Amax
|| Ar - ykll s
+ -0 (xk-1, Uk. )g 1) ||. (43)
Pk-1
15

---

Proof of Lemma B.2 It follows from the formulas of d and Ppe-1 (Ik: Uss AR-1) that
Ak-1)
grad (ok, yk. 1x-1) = MM Vf(xx) + PK-1A" yk
Ph-1
(44)
=T (Vf(xa) - A
Since that VgLon (Ix. Uk 1 is Lipscitz continuous with constant bv + 30 it follows from Lemma A.1 that grad, pp (# Ms, Ak-1) is Lipschitz continuous with
4 (aLp + G) + alls, + Pk- 10 S Cpk-1,
where C = (aL, + () + alv 02), which is due Pk-1 21
PT M (Vf(Tn) - A A&) || I|grad (Ix. Mks Ax-1)
T grad 1I 1, Uk 1 + Lpa- (Øks yks 7k-1) The grad, Sp--1 (#k- Uky A |I Ellgrad, (I 1 y/h, 1 Cpk- 1 igrad (IK-11 1, yk 1x-1)
22llgrad (I Vk. > l|.
where the second inequality follows from Lemma A.1 and the fact that T is isometric, the last inequality uses Tk-1 S Ope-1 by the condition for cy. It follows from (14) that
0 AR-1 Pk- (AAE-1 yn) + Oh(y))
By the definition of dx. have that
dist( -k. Oh.())))
= 1k-100 -
-oaaPt-I7t--llera I Sp (x Uk: 1
Tk
S Aalallgrad_ (ok-1, yk. 11-1) ll.
where the first inequality uses (5), the second inequality follows 1/L 1/pk, which is implied by 36). For (43). follows that
1
A - Ukel
a| Ax-1ll
7
2n + Amax
toAl12x IR-1ll
Pk-1
En + Amax
+0ga7a-1lgradd (IX-1, yk. Ax-1) ll.
Ph-1
where the first inequality uses
19 the second inequality follows (5. The proof is completed.
Theorem B.1. Suppose that Assumptions 3.1 hold. Let the sequence (æk. yks dx K be generated by Algorithm 1 Let pk = c,k and Tk c, 1/3 where Cr Cp satisfy
c S minf
O' M 16c, } cp 21
(45)
where G, B are defined in Lemma
A.2 There exists an constant G such that
K
Th
Igradppi (zk, Uk+1, N+) SG
16

---

Proof. Combining with Lemmas
3.1 and B. yields
The gggadd Spx (Ikr Mk+1, )x)) 11?
pp++1 (#K+1, + Ak+1) pp (#k, yk: AR) S
1
3
21 (2 (Cn Amax)
2 1 - xx/1?)
Yk+1
1
$
Tk
Igrad fm (Ix: U Ax.) 113 +
27k+1
+
- 0) (Cn + +mmax)² (27 +
2c
20202
||00011 - xxll
2
Pk
3pk
P7
s Tk
Igrad (I M 2x) 112
20g
2 k k-1// + )max)
Cp klog (I: +
3cp
+ 4nk+1 Tha
2 o Aalgradd_oo. (I Mh+11, Xx) 11?
S
Tk
4 Igrad (It: Mk+1, Ax) 11?
20y
2 k 1/-1/3)(l + Amau))
Cp k log (k 2)
3cp
where the third inequality follows from and step in Algorithm
1 and
27x+1
2c
0
2c
3cp k k4/3
P
3
C ls loo (k (k+2 2
the last inequality follows Th S C, S
Summing over k = 1 to K:
Toc, Q
K
gradC (0R, 3k- Ax) 1 (211 M1 - Cpx+i (0K+1, UK+1, AK+1)
+ (en + >mmax)2
K
1
2(th + Amax) 2
+
--43 4/3
k
k log (1: + 2)
3cp
Now we bound a, b, c, respectively. For a, let us denote Φx = Cpe (Ixx Mke Ax), then we have
ΦF f(xx) h(yx) (Au, Ar - yk) + 2
Pk
|AAxx - yxl1
(Tx) h(n)) || 1AA - 2/a1l
(46)
En + Amax + A xk-
2 f. ho Amax
Pk-1
2 ʃ. + 11 - Amax (Cn + Amax + ODD).
We let Ci f. + h,
Amax (Cp, Amax + OAD), and obtain a S Φ1 C1. For b, following 42
there exists a constant C2 such that
20
Sz.
(47)
k log 2 (k +
For c, since 4/3 > 1, the sequence Σx h 4/3 is convergence, there exists a constant C3 such that I Cz. Combining with those terms, one concludes that
K
Tk
gr pe (oes 1k+1, As) 12 c +
20 + Cc, + Amax)
(48)
Cp
3cp
1=1
Let us denote = Ci + ( Ca + 30, Ca) + Amax)² )_ The proof is completed.
Proof of Theorem 3.1
It follows from Theorem B.l that
K
min 1k/2
IgradC
(ox Bk. d 11
Σ
Th
k=
[K/2
(49)
K
TallgradC.... pa-1 (ox-11 Dk, Dky Ap-1) 12 <g,
k= K/2
17

---

which implies that
49
min [K/2 SK
gradC (Ik-1: Dks 1k-1) 11? 2
Lk=
k [K/2] Fk
(50)
Now we bound Σk= decreasing, one has that
Since To = crk 1/3 and the function x -133 is monotonically
[= Tke
K
K
k+1
Σ
2 CT
2 1/3 dx
1=
K/21
k= [K/2]
K
Σ
3
(h: 1))/33 - -1213]
C
2
k= [K/2
(51)
3
(K + (K+1)
1K1/3 (K/2+ + 1)3/3
2
3c,
2
(K 1)-1)))((A + + -)(/))))--1)))) + 1))
2
2
3
C K(K 1)-2/3 4 (K 1)2/3.
where the second inequality uses concavity of 2/3, Together with 49 there exists E [[K/2], K]
such that
16g
IgradLp. (Ix- 1 Uk. A 1) 112
(K + 11- 2/3
(52)
6
Using 52) and Lemma
B.2 it is easily shown that
8v
1 Xw) + grads S
(K + 1)-1/3
V
(53)
A G
dist( (se, (h(()))
(K + 1) 1/3
11/3
Vcr
which proves the first two term
23 For the last term, we have that
+ la + Amax
||Axx Vnl s - g pa-, (Ix-1, Mhe A
Px-1
1/3 1 2(lx + >mmax) 2) (54)
G - 2// + +1)
Cp
2/3 + 2(hh + >max) < & 2)-
(K () 2
Cp
where we use Tx c,(x - 1) 11/3 c (22) 1/3 < 2c, (K - 2 1/3 and Px-1 (1((6-100001 11/1/3 cpl 2 (K-))113 2 ( K - 2/3/3. Combining with (53) completes the proof.
18

---

20
9C0
ARADNIM
15ADMM
ARADWWI
NRADMM
MALMIM FACTUM ARADIM
MAGMM
NALDMM RACTMM ARADMM
MADKM
RACKIN ARAENBA
RAZKRI
ARADWM
AM
(a) 30,
(b) 30.
60,
(d) 60,
Figure 2: Comparison with ADMM-type methods for solving 27 with different (n, p) and (p1, (p1,2)) (150, 1000).
C More numerical results
This section emphasizes that the condition in 22 is not essential. Here, we consider the condition Cp 2 and focus on the DPCP formulation (27 comparing our ARADMM method with SOC B3
MADMM [I] and RADMM [35]. For ARADMM, we reset " = 103 = 0.6 and retain Po. Cr Cy.
The parameter settings for the baseline algorithms follow [55. We report the average results
10 trials with random initializations in Tables Tables[[]and]] 7 The function values for the sequence on the
manifold versus CPU time (in seconds) and iteration number recorded in Figures 2 and 3 It is
shown that the results remain consistent with those reported using = 1 in subsection 4.3
From theoretical point of view, the condition appears initially in Lemma A.2 where it was used to simplify the expression the following inequality:
(n) - (x) + (n, gr)d + a (L o + 2GB |n
Assuming cp 2 implics Pk 1, which simplifies the bound to:
(f + + + 2G3 s (a² + 03) 2G3)pk
However, this assumption not strictly necessary. In fact, we can relax by identifying a threshold index > 0, such that for & 2 k, we have Pk 2 1. This does not affect the final convergence guarantees- the same convergence rate still holds. This type of strategy has been employed in prior work (e.g.. (39) to mitigate the reliance on precise problem constants. This is why Cp = 0.6 also works well empirically here. In fact, the condition for other parameters also be eliminated by this strategy.
Table 6: Numerical results ADMM-type methods for solving 27 with different (n, p) and (PI, P2) (150, 1000).
Settings
SOC
MADMM
RADMM
ARADMM
(n, p)
Obj
CPU
Obj
CPU
Obj
CPU
Obj
CPU
(30, 4)
568.61 16
6.8864
568.4316
18,0771
569.3725
0.7801
568.3537
0.0244
(30, 6)
852.8768
2.0746
852.8180
9.3013
852.8157
0.4351
852.8125
0.0191
(60, 4)
366.1360
2,6194
365.8585
16.2287
365.9267
0.8130
365.6622
0.0245
(60, 6)
553.5725
3.6961
553.5749
43.4826
554.0265
1.0868
553.5650
0.1541
19

---

SCD ARADNMM
ARADMM
ARADNBI
ARADMM
MALMIM RACTU ARADIA
M60MM RACKIM ARAENBA
NALDMM RACTM ARADMM
MADKM RAZKRI ARADNM
bonaka
(a) P1 100, P2 600
(b) p1 100, 1600
(c)
200, P2
600
p1 200, P2 1600
Figure 3: Comparison with ADMM-type methods for solving
27 with different (p1.22) and
(n, (45, 5).
Table 7: Numerical results of ADMM-type methods for solving 27 (n. p) (45,5). 5).
with different (pi, P2) and
Settings
SOC
MADMM
RADMM
ARADMM
(21)
obj
CPU
obj
CPU
obj
CPU
obj
CPU
(100, 600)
317.0240
1.9779
316.9943
29.2210
317.3680
0.8800
316.8880
0.0238
(100, 1600)
859.3896
3.5202
859.3150
26.3167
859.3417
0.2115
859.0431
0.0206
(200, 600)
356.6751
2.5096
356.5580
30.6229
357.4611
0.8100
356.4748
0.0273
(200, 1600)
908.4715
5.2544
12.7438
909.4992
0.7122
907.8516
0.1086
20

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
i Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please refer Sec. conclusion
Guidelines:
21

---

The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texs system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
ii Theory assumptions and proof's
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
iv Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
22

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
We will release the code after the review process.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
haapi//guuudde//ooeSuuiisssssss oos for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7/
gwwps CCodeSoodieeeeeee ssi mollicyy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
vi Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
23

---

Answer: [Yes]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
vii Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
viii Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
ix Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics attpss:/neurips.ccm http://uuruuppppplpiereeeeeeeeee int.eiieeeeeiicccccdeeeeeeeee
Answer: [Yes]
Guidelines:
24

---

The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there is a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairesss considerations (e.g., deploomeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
xi Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
xii Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
25

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpppppppsseeeee thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- eepakkaged both the original license and the license of the derived asset (if has changed) should be provided. this information is not available online, the authors are encouraged to reach out to the asset's s creators.
xiii New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
xiv
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Guidelines:
26

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
xvi Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (bttps://neur http::///eeerrgs.cooooffofrrrrrr http://pp...pco.ooeeeeee//////// for what should or should be described.
27


Reviews:
[{"review_id": "c6UWDs0xbp", "reviewer": "Reviewer_prAa", "summary": "The authors study nonsmooth nonconvex optimization over Riemannian Submanifolds. Canonical examples of such a problem include sparse and/or nonnegative PCA. An adaptive ADMM algorithm is proposed which notably does not necessitate smoothing the nonsmooth term. By carefully adapting the dual step size, ARADMM controls the bound on the dual variables and the difference between successive dual variables. This yields an optimal oracle / iteration complexity of O(e-3) (under certain flexible assumptions e.g. Lipschitzness and smoothness of the smooth term and convexity and Lipschitzness of the nonsmooth term). Compared to existing ADMM-based frameworks for nonsmooth optimization over Riemannian Manifolds (e.g. MADMM), the proposed method only requires a single projection (via the retraction defined on M) and avoids nested iterative procedures or complicated subroutines (in addition to not modifying the original problem, e.g. by smoothing). \n\nNumerically, the authors compare RADMM to four ADMM-based methods and two first-order nonsmooth manifold optimization algorithms. On Sparse PCA, RADMM achieves a marked improvement over other methods in terms of solution quality and empirical convergence rate. On a robust subspace recovery task formulated via dual principal component pursuit, RADMM also outperforms relevant ADMM-based methods and a recently proposed energy minimization scheme.", "questions": "See weaknesses. I would like some contextualization of your framework with respect to some existing relevant missing references and more experimental results if possible.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths** This is a well-written paper that contributes a new practically designed and provably convergent ADMM-based algorithm for nonsmooth nonconvex optimization on smooth manifolds. The derived method notably does not necessitate smoothing the nonsmooth terms in the objective while maintaining numerical efficacy.\n\nNumerically, the method shines over relevant ADMM and first-order methods for optimization over smooth manifolds in terms of simplicity of implementation, solution quality, iteration complexity, and runtime. \n\n\n**Weaknesses** I am admittedly not up to date with the literature, but it seems that the author is missing some key references, including Wang, Yin, Zheng Global Convergence of ADMM in Nonconvex Nonsmooth Optimization, which also addresses nonsmooth nonconvex optimization of an ADMM-based method. It would be good to contextualize the work the authors have done with this important paper. Similarly, only two applications are discussed. It would strengthen the paper to include more experiments - e.g. nonnegative PCA as discussed in the introduction, or problems on manifolds other than the Stiefel manifold.", "was_revised": true, "final_justification": "The authors response to my rebuttal is comprehensive and detailed. I increase my confidence in acceptance.", "rebuttal": "We sincerely thank the reviewer for the positive feedback on the clarity of the writing and the contributions of our work. We are glad that the theoretical and practical aspects of the proposed ADMM-based algorithm were found valuable. We have addressed each concern carefully and made corresponding revisions where appropriate, as detailed below.\n* Our current version mainly focuses on summarizing existing Riemannian ADMM approaches. In the revised version, we will include a more comprehensive discussion of Euclidean-space ADMM methods for nonsmooth nonconvex problems.  We will discuss how our method differs from  Euclidean ADMM in the following two aspects:\n\n  - On one hand, when the manifold reduces to $\\mathbb{R}^n$, several ADMM variants with convergence guarantees have been developed (e.g., [1, 2, 3] and the mentioned reference). These methods typically rely on using the optimality condition of the $x$-subproblem and the smoothness of $f$ to derive a bound on $\\\\|\\lambda_{k+1} - \\lambda_k\\\\|$. However, this strategy fails to generalize to the manifold setting due to the presence of projection operators, see Section 3.1 for details. This also explains why the original Riemannian ADMM (e.g., RADMM) lacks convergence guarantees.\n\n  - On the other hand, for general nonlinear constraints (including manifold constraints), some prior works [4,5,6] apply ADMM by penalizing the constraint. However, this approach does not exploit the underlying manifold geometry and essentially reduces to penalty-based methods, which are generally less efficient than manifold-aware algorithms (e.g., Riemannian gradient and retraction).\n\n* We appreciate the suggestion of adding an experiment on nonnegative PCA. However, we would like to clarify that the nonsmooth term in nonnegative PCA is an indicator function of the nonnegative orthant, which is not Lipschitz continuous. This violates Assumption 3.1 in our paper, which requires the nonsmooth component $h$ to be Lipschitz. For this reason, our algorithm and theoretical analysis do not directly apply to this setting, and we are unable to include it as a valid benchmark in our experiments.\n\n* To further demonstrate the applicability of our algorithm to broader settings, we have added a new experiment: Regularized Linear Classification over the Sphere \\[7,8]. Consider a classification problem with $N$ training examples $\\{a_i,b_i\\}_{i=1}^N$ where $a_i \\in \\mathbb{R}^{m \\times 1}$ and $b_i \\in \\\\{-1,1\\\\}$ for all $i \\in [N]$. The goal is to estimate a linear classifier parameter on the sphere manifold, $x \\in \\mathbb{S}^{m-1} := \\{x \\in \\mathbb{R}^m : x^\\top x = 1\\}$, that minimizes a smooth nonconvex loss function with an $\\ell_1$-regularization:\n\n$$\n\\tag{1}\n\\min_{x \\in \\mathbb{S}^{m-1}} \\sum_{i=1}^{N} \\left(1 - \\frac{1}{1 + \\exp(-b_i x^\\top a_i)} \\right)^2 + \\mu \\\\|x\\\\|_1.\n$$\n\nFor data generation, the true parameter $x$ is sampled from $\\mathcal{N}(0, I_m)$ and projected onto $\\mathbb{S}^{m-1}$. The features $\\\\{a_i\\\\}\\_{i=1}^N$ are sampled independently, and the labels $b_i$ are set to 1 if $x^\\top a_i + \\epsilon_i > 0$, where noise $\\epsilon_i \\sim \\mathcal{N}(0, \\sigma^2)$, and -1 otherwise. All algorithms use the identical random initialization and terminate when $|F(X_{k+1}) - F(X_k)| \\leq 10^{-8}$ or after 500 iterations, with $\\mu = 0.2$ fixed in (1).\n\nFor the three fixed methods, we set the penalty parameter $\\rho = 150$ and the step size $\\eta = 0.01$ for SOC, MADMM, and RADMM. For the two adaptive methods, we set $\\beta_0 = \\rho_0 = c_\\beta = 100$, $c_\\rho = 1$, and $c_\\tau = 0.05$ for ARADMM, and use the same settings as in our SPCA experiment for OADMM. Here, the choices of parameters for all the algorithms in the experiment are consistent with the corresponding theories. Before presenting the numerical comparisons, we remind the reader that there is no convergence guarantee for SOC and MADMM.\n\nTable 1 reports the function value (denoted by “Obj”) and CPU time (in seconds), where the results are averaged over 10 repeated experiments with random initializations. From Table 1, we can see that ARADMM and MADMM quickly decrease the objective value, whereas both ARADMM and SOC achieve a lower objective value for the outputs. Moreover, ARADMM is more advantageous than existing methods in more challenging scenarios. In short, ARADMM is more efficient in terms of CPU time and objective value for test instances.\n\n---\n\n**Table 1: Comparison of the ADMM-type methods for solving problem (1) with different settings. The best and second-best results are marked in bold and italics, respectively.**\n\n| Settings $(m,n,\\sigma^2)$ | SOC Obj    | SOC CPU | MADMM Obj | MADMM CPU | RADMM Obj | RADMM CPU | OADMM Obj | OADMM CPU | ARADMM Obj | ARADMM CPU |\n| ------------------------- | ---------- | ------- | --------- | --------- | --------- | --------- | --------- | --------- | ---------- | ---------- |\n| (200, 1000, 1)            | **0.7004** | 1.1009  | 0.7340    | *0.0729*  | 0.7340    | 0.0876    | 0.7282    | 0.1024    | *0.7370*   | **0.0507** |\n| (400, 5000, 5)            | *0.6877*   | 2.2876  | 0.8267    | *0.1701*  | 0.8267    | 0.1864    | 0.7288    | 0.2799    | **0.6875** | **0.1073** |\n| (600, 10000, 10)          | *0.6469*   | 7.8231  | 0.9216    | *0.6692*  | 0.9216    | 0.7153    | 0.6665    | 1.0664    | **0.6464** | **0.4197** |\n| (800, 20000, 50)          | *0.6606*   | 30.7367 | 1.0398    | *2.2673*  | 1.0396    | 2.7062    | 0.6871    | 2.7062    | **0.6602** | **1.4167** |\n\n\n\n[1] Boţ, R. I., \\& Nguyen, D. K. (2020). The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates. Mathematics of Operations Research, 45(2), 682-712. \n\n[2] Guo, K., Han, D. R., \\& Wu, T. T. (2017). Convergence of alternating direction method for minimizing the sum of two nonconvex functions with linear constraints. International Journal of Computer Mathematics, 94(8), 1653-1669.\n\n[3] Hien, L. T. K., Phan, D. N., \\& Gillis, N. (2022). Inertial alternating direction method of multipliers for non-convex non-smooth optimization. Computational Optimization and Applications, 83(1), 247-285.\n\n[4] Hien, L. T. K., & Papadimitriou, D. (2024). An inertial ADMM for a class of nonconvex composite optimization with nonlinear coupling constraints. Journal of Global Optimization, 89(4), 927-948.\n\n[5] El Bourkhissi, L., Necoara, I., & Patrinos, P. (2023, December). Linearized ADMM for nonsmooth nonconvex optimization with nonlinear equality constraints. In 2023 62nd IEEE Conference on Decision and Control (CDC) (pp. 7312-7317). IEEE.\n\n[6] Hien, L. T. K., & Papadimitriou, D. (2024). Multiblock ADMM for nonsmooth nonconvex optimization with nonlinear coupling constraints. Optimization, 1-26.\n\n[7] Zhao, L.; Mammadov, M.; and Yearwood, J. 2010. From convex to nonconvex: a loss function analysis for binary classification. In 2010 IEEE international conference on data mining workshops, 1281–1288. IEEE\n\n[8] Zhang, D.; and Davanloo Tajbakhsh, S. 2023. Riemannian stochastic variance-reduced cubic regularized Newton method for submanifold optimization. Journal of Optimization Theory and Applications, 196(1): 324–361."}, {"review_id": "CGmcFUb1oM", "reviewer": "Reviewer_dLzV", "summary": "This work proposes a Riemannian ADMM algorithm for optimizing the sum of a smooth function and the composition of a non smooth function with a linear operator, all of that restricted to be in a Riemannian manifold embedded in R^n. Access to the gradient of the former function and the proximal operator of the latter is assumed. Author show that their algorithm achieves a KKT point up to an \\epsilon in O(\\epsilon^{-3}). Experients are provided.", "questions": "What are the main differences and new techniques of this work with respect to its Euclidean counterpart?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This work is generally well written and the result seems interesting, but I missed an explanation comparing the analysis of this paper and the one of the Euclidean approach that this work is based on. There are a couple of minor problems / typos in the analysis:\n\nThe way the statement of Theorem 3.1 is phrased is inaccurate, since if the actual guarantee you prove is what you state, then the minimum of each of the three objectives could happen at different indices k, and it could be that for no single index the three terms are small at the same time. However, taking a look at your proof you can fix it and claim that you have a k such that the sum of all three terms is small.\n\nThere is an index problem in the proof of Theorem B.1. At the beginning of the proof, a property is shown for $\\mathcal{L}$ with rho having an index a unit less than the indices of x, y, \\lambda. However, between line 430 and 431 the indices for all of those variables become the same. This should be fixed.\n\nOne thing to note is that the method is claimed to be adaptive but the algorithm requires access to most problem constants like the smoothness of f, the operator norm of the linear map. The adaptivity refers to how the dual step size can adapt depending on the previous iterates but still depends on these constants.", "was_revised": true, "final_justification": "After the author's response, some points were clarified and I keep my evaluation unchanged. This paper falls into the borderline accept category.", "rebuttal": "Thank you for the positive feedback and for recognizing the core innovation of our work. We have addressed each concern carefully and made corresponding revisions where appropriate, as detailed below.\n\n**1.Regarding the Comparison to the Euclidean Counterpart**:\n\nWe thank the reviewer for this insightful question.  We discuss that our method differs from  Euclidean ADMM in the following two aspects:\n\n- On one hand, when the manifold reduces to $\\mathbb{R}^n$, several ADMM variants with convergence guarantees have been developed (e.g., [1, 2, 3]). These methods typically rely on using the optimality condition of the $x$-subproblem and the smoothness of $f$ to derive a bound on $\\\\|\\lambda_{k+1} - \\lambda_k\\\\|$. However, this strategy fails to generalize to the manifold setting due to the presence of projection operators, see Section 3.1 for details. This also explains why the original Riemannian ADMM (e.g., RADMM) lacks convergence guarantees.\n\n- On the other hand, for general nonlinear constraints (including manifold constraints), some prior works [4,5,6] apply ADMM by penalizing the constraint. However, this approach does not exploit the underlying manifold geometry and essentially reduces to penalty-based methods, which are generally less efficient than manifold-aware algorithms.\n\n- In contrast, our method adopts a **fundamentally different strategy** from Euclidean ADMM to control the difference $\\\\|\\lambda_{k+1} - \\lambda_k\\\\|$. We achieve this through **careful design of the penalty parameter and dual step size updates**, which is of independent interest. Notably, our analysis does **not rely on the smoothness of $f$** to control $\\\\|\\lambda_{k+1} - \\lambda_k\\\\|$, which opens up a potential future direction: developing ADMM-type methods for problems where **both terms in the objective are nonsmooth**.\n\nWe will clarify this comparison more explicitly in the revised manuscript. \n\n\n**2.Regarding the statement of Theorem 3.1**\n\nWe thank the reviewer for pointing out this important issue. We agree that, as originally stated, the theorem could imply that the minimum of each of the three terms occurs at a different index $k$, which would not guarantee a single iterate where all terms are simultaneously small. \n\nIt follows from (46) that:\n$$\n\\sum\\_{k=1}\\^{K}\\frac{\\tau_k}{4}\\left\\\\| \\text{grad} \\mathcal{L}\\_{\\rho_k}\\left(x_\\{k}, y_\\{k+1}, \\lambda_k\\right) \\right\\\\|^2 \\leq \\mathcal{G}.\n$$\nLet us denote\n$$\nR_k = \\left\\\\| \\mathcal{P}\\_{T\\_{x_k}\\mathcal{M}} \\left( -\\mathcal{A}^* \\bar{\\lambda}_k \\right) + \\text{grad}f(x_k) \\right\\\\|^2 + \\text{dist}^2\\left(-\\bar{\\lambda}_k , \\partial h(y_k)\\right) + \\left\\\\| \\mathcal{A}x_k - y_k \\right\\\\|^2.\n$$\nNow we can use Lemma B.2 to bound $R_k$. Then we multiply $\\tau_k$ into both sides and sum it up from $k=1$ to $K$.  \nFollowing the proof of Theorem B.1, we can obtain the following result:\n$$\n\\min\\_{1 \\leq k \\leq K} R_k \\leq \\frac{\\Gamma}{\\sum\\_{k=1}\\^{K} \\tau_k},\n$$\nwith some constant $\\Gamma$. Note that $\\tau_k = c\\_{\\tau}k^{-1/3}$ and\n$$\n\\sum\\_{k=1}\\^{K} k^{-1/3} \\geq \\sum\\_{k=1}^{K} \\int_k^{k+1} x^{-1 / 3} \\mathrm{~d}x \\geq \\frac{1}{2} (K+1)^{2/3}.\n$$\nThen we have that\n$$\n\\min\\_{1 \\leq k \\leq K} R_k \\leq \\mathcal{O}(K\\^{-2/3}).\n$$\nThis guarantees the existence of a single iterate $k$ at which the sum of all three quantities is small, and thus the desired convergence rate holds at that point. We will update the theorem and corresponding discussion in the revised manuscript.\n\n**3.Regarding the proof of Theorem B.1**\n\nWe thank the reviewer for carefully identifying the indexing inconsistency in the proof. At the beginning of the proof, the augmented Lagrangian should be written as:\n\n$$\n\\mathcal{L}\\_{\\rho\\_{k+1}}\\left(x\\_{k+1}, y\\_{k+1}, \\lambda\\_{k+1}\\right) - \\mathcal{L}\\_{\\rho\\_{k}}\\left(x_k, y_k, \\lambda_k\\right),\n$$\n\nwith $\\rho$ taking indices consistent with the corresponding variables. This correction does not affect the validity of the proof or the final result.\n\n**4.Regarding the claim that our method is adaptive**\n\nThank you for your comment. We agree that although our algorithm is described as *adaptive*, it still relies on certain problem-dependent constants.\n\nHowever, we would like to clarify that this dependence is **not essential**. Specifically, the algorithm involves three hyperparameters—$c\\_\\tau$, $c\\_\\rho$, and $c\\_\\beta$—which determine the sequences $\\tau_k = c\\_\\tau k^{-1/3}$, $\\rho_k = c\\_\\rho k^{1/3}$, and $\\frac{c\\_{\\beta}}{k^{1/3} \\log^2(k+1)}$, respectively.  For example, since $\\tau_k = c\\_\\tau k^{-1/3}$, the condition on $c_\\tau$ is essentially imposed to ensure that $\\tau_k$ satisfies the required bound, i.e.,  $\\tau_k < \\min\\\\{  \\frac{1}{C}, \\frac{1}{M}, \\frac{1}{16 c\\_{\\beta}\\alpha^2 \\sigma_A^2}\\\\}$ (Theorem 3.1).  This condition can always be satisfied after a sufficiently large number of iterations without requiring $c_\\tau$. That is, for any $c_\\tau$, there exists an integer $k_0 > 0$ such that for all $k > k_0$,  $\\tau_k$ satisfies the condition. A similar argument applies to the other parameters. Importantly, this does not affect the final convergence guarantees—the same convergence rate still holds. This type of strategy has been employed in prior work (e.g., [7]) to mitigate the reliance on precise problem constants. \n\nTherefore, our use of the term *adaptive* was meant to emphasize that both the penalty parameter and the dual step size evolve with the iteration count $k$, rather than being fixed. A more accurate description might be that these parameters are *dynamic*, rather than *fully adaptive* in the traditional sense. We will clarify this point in the revised manuscript.\n\n**Reference**\n\n[1] Boţ, R. I., & Nguyen, D. K. (2020). The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates. Mathematics of Operations Research, 45(2), 682-712.\n\n[2] Guo, K., Han, D. R., & Wu, T. T. (2017). Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints. International Journal of Computer Mathematics, 94(8), 1653-1669.\n\n[3] Hien, L. T. K., Phan, D. N., & Gillis, N. (2022). Inertial alternating direction method of multipliers for non-convex non-smooth optimization. Computational Optimization and Applications, 83(1), 247-285.\n\n[4] Hien, L. T. K., & Papadimitriou, D. (2024). An inertial ADMM for a class of nonconvex composite optimization with nonlinear coupling constraints. Journal of Global Optimization, 89(4), 927-948.\n\n[5] El Bourkhissi, L., Necoara, I., & Patrinos, P. (2023, December). Linearized ADMM for nonsmooth nonconvex optimization with nonlinear equality constraints. In 2023 62nd IEEE Conference on Decision and Control (CDC) (pp. 7312-7317). IEEE.\n\n[6] Hien, L. T. K., & Papadimitriou, D. (2024). Multiblock ADMM for nonsmooth nonconvex optimization with nonlinear coupling constraints. Optimization, 1-26.\n\n[7] Lu, Z., Mei, S., & Xiao, Y. (2024). Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees. arXiv preprint arXiv:2409.09906."}, {"review_id": "Sxb9lKVR2x", "reviewer": "Reviewer_xPLN", "summary": "This paper proposes an adaptive Riemannian alternating direction method of multipliers to solve the problem of minimizing the sum of a smooth function and a non-smooth convex regularizer over a compact Riemannian submanifold embedded in Euclidean space. Unlike smoothed ADMM, the proposed method directly addresses the original nonsmooth problem. Through adaptive coordination of the step size and penalty parameters, ensuring the Lagrangian multiplier difference is bounded by the primal iterate difference, then establish an optimal iteration complexity of order $O(\\epsilon^{-3})$ for finding an $\\epsilon$-approximate KKT point. Numerical experiments on sparse PCA and robust subspace recovery demonstrate that ARADMM consistently outperforms state-of-the-art Riemannian ADMM variants in convergence speed and solution quality.", "questions": "*) In line 6, RADMM proposed by Jiaxiang Li et al. in [28] also involves only one Riemannian gradient evaluation and one proximal update per iteration.\n\n*) In Section 1.2, the indicator function mentioned is not used in this paper and is recommended to be removed.\n\n*) Vector transport is an important concept in manifold optimization, which is used in this paper. Its definition should be explained in Section 2.1.\n\n*) Why does the inequality below Line 172 hold? Since the Lambda is a vector, does the inequality mean for entrywise inequality?\n*) Why does the second equation in (30) hold?\n\n*) Lemma A.1 is missing a proof or reference. Does the vector transport used in Lemma 1 need to be isometry, and if not, can the requirement of isometry in line 419 be relaxed to \\|\\mathcal{T}_{x}^{y}(u)\\| \\leq L \\|u\\|, where there L is some constant?\n\n*)  Lemma B.1., B.2., and Theorem B.1. and 3.1. all require c_\\rho\\geq 1, but the parameter c_\\rho is set to 0.6 in the numerical experiments for robust subspace recovery. Moreover, line 408 and line 420 both require c_\\rho\\leq 1, but line 418 needs \\rho_{k-1} = c_{\\rho}(k-1)^{1/3}>1 . I think the parameter c_{\\rho} was chosen incorrectly and needs to be adjusted. \n\n*)  During the proof of Theorem B1, there were several writing errors, which made reading difficult. Such as in the first inequality of the proof, \\rho_{k}->\\rho_{k+1}, \\rho_{k-1}->\\rho_{k}, (\\ell_h+\\lambda_{max})^2 is lost in the proof, and so on.\n\n*)  Some symbols do not indicate their meaning before they are used. In Definition 2.1, the meaning of the symbol T\\mathcal{M} is not specified. In inequality (44), the meanings of symbols f_* , h_* and \\mathcal{D} are not specified. Moreover, the symbol \\mathcal{D} also appears in line 142, but their meanings are different.\n\n*)  There are many typos in this paper; for example, in line 114. It is suggested to check again.", "limitations": "This paper already states its limitation, i.e., its current analysis does not exploit structural properties like the Kurdyka–Łojasiewicz (KL) inequality, which could lead to improved convergence rates.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The idea presented in this paper is great. The innovation lies in adaptively selecting dual step sizes and penalty parameters, explicitly bounding multiplier differences by the norms of corresponding primal iterate differences. This is crucial for ensuring convergence. But there are still some details missing in the writing, mainly in the theoretical proof part. The major concern also lies in the theoretical proofs of the main result.", "was_revised": true, "final_justification": "I will keep my score and my questions are all answered.", "rebuttal": "Thank you for the positive feedback and for recognizing the core innovation of our work. We have addressed each concern carefully and made corresponding revisions where appropriate, as detailed below. \n\n**Reply to Questions**\n*  Thank you for the comment. To avoid confusion, we will revise the sentence to: “Our approach involves only one Riemannian gradient evaluation and one proximal update per iteration.”\n* We have removed the sentence about the indicator function.\n* We have added its definition in Section 2.1 in the revised version.\n> **Vector Transport.**\n> Given a Riemannian manifold $\\mathcal{M}$, the *vector transport* $\\mathcal{T}_x^y$ is an operator that transports a tangent vector $v \\in T_x \\mathcal{M}$ to the tangent space $T_y \\mathcal{M}$, i.e., $\\mathcal{T}_x^y(v) \\in T_y \\mathcal{M}$. In this paper, we assume $\\mathcal{T}_x^y$ is isometric.\n* Thank you for pointing this out. The inequality was missing a norm, which may have led to confusion. It should be written as:\n$$\n\\begin{aligned}\n\\\\|\\lambda\\_{k+1} - \\lambda_k\\\\| &= \\left\\\\| \\beta\\_{k+1} (\\mathcal{A} x\\_{k+1} - y\\_{k+1}) \\right\\\\| \\leq \\beta\\_{k+1} \\left\\\\| \\mathcal{A} x_k - y\\_{k+1} - \\frac{\\lambda_k}{\\rho_k} \\right\\\\| + \\beta\\_{k+1} \\\\| \\mathcal{A}(x\\_{k+1} - x_k) \\\\| + \\beta\\_{k+1} \\frac{\\\\|\\lambda_k\\\\|}{\\rho_k} \\\\\\\\\n& \\leq \\beta\\_{k+1} \\left\\\\| \\mathcal{A} x_k - \\frac{\\lambda_k}{\\rho_k} - \\mathrm{prox}\\_{h/\\rho_k} \\left( \\mathcal{A} x_k - \\frac{\\lambda_k}{\\rho_k} \\right) \\right\\\\| + \\beta\\_{k+1} \\\\|\\mathcal{A}\\\\|\\_{op} \\\\|x\\_{k+1} - x_k\\\\| + \\beta\\_{k+1} \\frac{\\\\|\\lambda_k\\\\|}{\\rho_k}.\n\\end{aligned}\n$$\nWe will correct this in the revised version of the paper. Thank you again for carefully catching this issue.\n* The second equation in (30) should use \"$\\leq$\" instead of equality. The correct derivation is as follows:\n$$\n\\begin{aligned}\n\\\\|\\beta\\_{k+1} (\\mathcal{A} x\\_{k+1} - y\\_{k+1})\\\\| &= \\beta\\_{k+1} \\left\\\\| \\mathcal{A} x_k - y\\_{k+1} - \\frac{\\lambda_k}{\\rho_k} + \\mathcal{A}(x\\_{k+1} - x_k) + \\frac{\\lambda_k}{\\rho_k} \\right\\\\|  \\\\\\\\\n& \\leq \\beta\\_{k+1} \\left\\\\| \\mathcal{A} x_k - y\\_{k+1} - \\frac{\\lambda_k}{\\rho_k} \\right\\\\| + \\beta\\_{k+1} \\\\| \\mathcal{A}(x\\_{k+1} - x_k) \\\\| + \\beta\\_{k+1} \\frac{\\\\|\\lambda_k\\\\|}{\\rho_k}.\n\\end{aligned}\n$$\nWe will correct this in the revised version. Thank you again for carefully catching this oversight.\n* We thank the reviewer for the careful reading. We have added the appropriate reference for Lemma A.1, which cites Lemma 1 from \\[10]. Regarding the vector transport: it is not required to be an isometry for the result in Lemma A.1 to hold. In fact, Line 419 can be relaxed to the more general condition\n$$\n\\\\|\\mathcal{T}\\_{x}^{y}(u)\\\\| \\leq L \\\\|u\\\\|,\\quad \\text{for some constant } L > 0.\n$$\nIn our analysis, we assumed an isometric vector transport to simplify the notation and presentation. We will clarify this assumption and the rationale for it in the revised manuscript.\n* Consistency of Assumptions on $c_\\rho$. \n   - Regrading the choice of $c\\_{\\rho}$ in robust subspace recovery,  we have re-run the experiments with $c\\_{\\rho} = 1$. For ARADMM, we reset $c_\\rho = 1$ and $\\beta_0 = 700$, and retain the original values for $\\rho_0$, $c_\\tau$, and $c_\\beta$.\nThe implementations of other methods follow the code provided by [28] in the manuscript, where we set the ADMM stepsize $\\eta = 10^{-5}$. All methods terminate when $|F(X_{k+1}) - F(X_k)| \\leq 10^{-6}$ or the number of iterations exceeds 5000.\nThe results in **Table 1** are averaged over 10 runs with random initialization. It is shown that the results remain consistent with those reported using $c\\_{\\rho} = 0.6$. \n  - We want to emphasize that the condition $c_\\rho \\geq 1$ is **not essential**.  The condition appears initially in Lemma A.2, where it was used to simplify the expression in the following inequality:\n$$\n\\Phi_k(\\mathcal{R}\\_{x}(\\eta)) \\leq \\Phi_k(x) + \\langle \\eta, \\nabla \\Phi_k(x) \\rangle + \\frac{\\alpha^2 (\\ell\\_{\\nabla f} + \\rho_k \\sigma_A^2 ) + 2 G \\beta }{2} \\\\|\\eta\\\\|^2.\n$$\nAssuming $c\\_\\rho \\geq 1$ implies $\\rho_k \\geq 1$, which simplifies the bound to:\n$$\n\\alpha^2 (\\ell\\_{\\nabla f} + \\rho\\_k \\sigma_A^2 ) + 2 G \\beta \\leq \\left(\\alpha^2 (\\ell\\_{\\nabla f} + \\sigma_A^2 ) + 2 G \\beta\\right)\\rho_k = M\\rho_k.\n$$\nHowever, this assumption is not strictly necessary. In fact, we can relax it by identifying a threshold index $\\tilde{k} > 0$, such that for all $k > \\tilde{k}$, we have $\\rho_k \\geq 1$. This does not affect the final convergence guarantees—the same convergence rate still holds. This type of strategy has been employed in prior work (e.g., [1]) to mitigate the reliance on precise problem constants. This is why $c\\_{\\rho} = 0.6$ also works well empirically.  In fact, the condition for other parameters can also be eliminated by this strategy, such as $\\tau_k = c_\\tau k^{-1/3}$. \n  - Regarding lines 408 and 420, our intention was to derive the desired bounds using conditions on $c_\\tau$, but we overlooked the existence of $c_\\rho$ in $\\rho_k$. We will revise Equation (20) to explicitly include this dependence, i.e., \n$$\n c\\_{\\tau} \\leq \\frac{1}{c_{\\rho}} \\min\\\\{  \\frac{1}{C}, \\frac{1}{M}, \\frac{1}{16 c\\_{\\beta}\\alpha^2 \\sigma_A^2}\\\\}.\n$$\n With this correction, it is sufficient to assume $c_\\rho \\geq 1$ throughout the analysis. In addition, for line 418,  inequality should read $\\rho_{k-1} = c_\\rho (k-1)^{1/3} \\geq 1$, not $> 1$. We will correct this in the revision.\n\nWe will revise the theoretical discussion accordingly and clarify how the convergence still holds under more general parameter settings.\n\n--- \n\n### **Table 1: Comparison of SOC, MADMM, RADMM and ARADMM for solving the robust subspace recovery problem**\n\n| p | (n, p₁, p₂)   | SOC obj  | SOC CPU | MADMM obj | MADMM CPU | RADMM obj | RADMM CPU | ARADMM obj   | ARADMM CPU |\n| - | ------------- | -------- | ------- | --------- | --------- | --------- | --------- | ------------ | ---------- |\n| 4 | (30,100,500)  | 286.5284 | 1.4835  | 286.4820  | 0.7677    | 286.4599  | 0.0486    | **286.3336** | **0.0057** |\n|   | (40,125,750)  | 363.2060 | 2.6384  | 363.1336  | 1.4823    | 363.0977  | 0.0136    | **362.8826** | **0.0119** |\n|   | (50,150,1000) | 423.6242 | 2.7054  | 423.5769  | 2.3196    | 423.5352  | 0.0378    | **423.2783** | **0.0136** |\n| 6 | (30,100,500)  | 431.2076 | 2.4063  | 431.1518  | 1.4842    | 431.1275  | 0.0160    | **431.0405** | **0.0089** |\n|   | (40,125,750)  | 542.7145 | 2.8961  | 542.6425  | 0.7155    | 542.5957  | 0.0540    | **542.4900** | **0.0112** |\n|   | (50,150,1000) | 637.8058 | 2.6239  | 637.7484  | 0.7584    | 637.6906  | 0.0972    | **637.3598** | **0.0176** |\n\n\n\n* We thank the reviewer for pointing out the typos and missing terms in the proof of Theorem B.1. We have corrected the subscript inconsistencies (e.g., $\\rho_k \\to \\rho\\_{k+1}$, $\\rho\\_{k-1} \\to \\rho_k$) and added the missing constant term $(\\ell_h + \\lambda\\_{\\max})^2$, which was inadvertently omitted in the derivation. Since this term is independent of the iteration index $k$, its omission does not affect the final complexity result. We have carefully reviewed the entire proof and corrected all related issues to improve clarity and correctness in the revised manuscript.\n* Thank you for the helpful suggestions. We have addressed the symbol-related issues as follows:\n\n  - We have now added the definition of $T\\mathcal{M}$ (the tangent bundle of the manifold $\\mathcal{M}$) before its first use in Definition 2.1.\n\n  - In inequality (44), the symbols $f_*$ and $h_*$ were previously undefined. We have clarified them explicitly in Assumption 3.1 as: $\n  f_* = \\inf_x f(x) > -\\infty, \\quad h_* = \\inf_x h(x) > -\\infty. $\n  - Regarding the symbol $\\mathcal{D}$, it is intended to denote the same quantity throughout the paper, specifically:\n  $\n  \\mathcal{D} = \\max_{x, y \\in \\mathcal{M}} \\\\|x - y\\\\|,\n  $\n  as introduced in line 142. We will explicitly reference this definition when $\\mathcal{D}$ appears in inequality (44) to ensure consistency and avoid confusion.\n* We have carefully proofread the entire manuscript and corrected all identified typos and formatting issues to improve the overall clarity and presentation. We appreciate the reviewer’s suggestion and will ensure that the revised version meets a high standard of writing quality.\n\n**Reply to Limitations**\n\nThank you for pointing this out. We acknowledge this limitation, as also noted in the paper. Our current focus is on establishing convergence without smoothing and analyzing the iteration complexity in the nonconvex, nonsmooth setting. Incorporating structural properties such as the KL inequality is indeed a promising direction and could lead to sharper rates, which we leave for future work.\n\n**Reply to Paper Formatting Concerns**\n\nWe will move the assumptions to appear before the convergence analysis section. Additionally, we will add an organization paragraph to improve the clarity and guide the reader through the structure of the paper.\n\n\n[1] Lu, Z., Mei, S., & Xiao, Y. (2024). Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees. arXiv preprint arXiv:2409.09906."}, {"review_id": "ek4ZsQ0wte", "reviewer": "Reviewer_LuUY", "summary": "This paper addresses the problem of minimizing the sum of a smooth function and a non-smooth convex regularizer over a compact Riemannian submanifold embedded in Euclidean space. The authors propose an adaptive Riemannian alternating direction method of multipliers (ARADMM), which achieves convergence for the first time without requiring the smoothing of the non-smooth term. In contrast to conventional Riemannian ADMM methods that require solving a subproblem exactly at each iteration, the proposed approach involves only one Riemannian gradient evaluation and one proximal update per iteration. A sophisticated dual step size design ensures the convergence of the algorithm. Finally, extensive numerical experiments demonstrate the superiority of ARADMM in terms of both convergence speed and solution quality.", "questions": "- Regarding the dual step size $\\beta_k$, could you clarify the inspiration behind this choice? Is there any similar approach discussed in previous literature? Is there a similar step size design in the Euclidean case? Additionally, what is the role of the constant $\\log^2 2$ in $\\beta_k$? It seems that its critical function is not evident in the proof. A clearer explanation of this would help highlight the originality and significance of your work.\n- The choice of $c_\\tau$ appears to be a delicate adjustment in practice, especially since the Lipschitz constant of the function may not be easily known. In your experiments, did you test different values of $c_\\tau$? How do the results vary with different selections of $c_\\tau$? Clarifying this aspect would further demonstrate the practical applicability of your algorithm.\n- I noticed that in the Sparse PCA experiments, you compared your method with ManPG. As far as I know, the method AManPG in reference [19] achieves faster and better results for Sparse PCA. Why was this method not included in your comparison? Additionally, it seems that comparisons with ALM-based algorithms could also be relevant, such as those in [41] and [Zhang, C. et al.]$^1$. Furthermore, the experimental dimensions appear to be limited to less than 1000. Have you conducted experiments with larger dimensions? Providing an explanation for the exclusion of these comparisons, or additional experiments, would help us better understand the advantages of your proposed algorithm.\n- In the proof section, is there a complete proof or a reference for Lemma A.1? Also, the condition $c_\\rho \\geq 1$ seems to be incorrect and should be $c_\\rho \\leq 1$, which matches the value used in your experiments. Please carefully review the corresponding locations and the relationship between $\\tau_k$ and $\\rho_k$. Furthermore, equation (29) seems to be missing a $\\lambda_0$, and the summation symbol in the second inequality should have the index $l=0$ instead of $l=1$. In line 421, the first equation should be an inequality, and in line 418, $\\ell_k$ should be replaced with $\\ell_{k-1}$.\n\nReference\n1. Zhang, C., Xiao, R., Huang, W., & Jiang, R. (2024). Riemannian Trust Region Methods for SC 1 Minimization. Journal of Scientific Computing, 101(2), 32.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\nThe structure of the paper is well-organized, and the logical flow is clear and coherent. The authors present, for the first time, an algorithm that achieves the convergence complexity of smoothing-based methods without the need for smoothing techniques. The numerical experiments demonstrate impressive results, further validating the proposed method. Additionally, the clever dual step size design provides a guarantee for controlling the boundedness of the Lagrangian multipliers, which seems to be an innovative contribution.\n\n### Weaknesses\nWhile the overall logic of the paper is clear, there are some areas that could be improved:\n- Some equation numbers, such as those in equations (11) and (13), appear to be unnecessary. These redundant labels impact readability.\n- In line 60, the discussion on “the best-known complexity achieved by smoothing-based Euclidean and Riemannian ADMM methods” could benefit from the addition of references to support the claim.\n- The usage of $\\tilde{\\mathcal{O}}$ should be explained for readers who are less familiar with complexity notation.\n- In line 172, the formula should be $\\lambda_k - \\lambda_{k+1}$, and the final inequality should be an equality.\n- The equality in equation (18) should be defined by the symbol used in the paper.\n- In line 405, the definitions of various parameters should reference their initial definitions, and in line 431, the symbol $D$ should refer back to its previous definition for clarity.\n- The paper would benefit from reducing typographical errors. There are some typographical errors:\n    - In equations (1) and (3), the periods should be replaced with commas.\n    - In line 24, \"a linear mappings\" should be corrected to \"a linear mapping.\"\n    - In Proposition 2.1, the second inequality has an extra space.\n    - In line 430, $Q$ should be $\\alpha$.\n    - In line 439, \"Corollary\" should be changed to \"Theorem.\"", "was_revised": true, "final_justification": "The authors have addressed the raised concerns and obtained solid results; the additional experiments provided make me feel confident about the practical feasibility of the proposed algorithm. Therefore, I am willing to raise my score by one point.", "rebuttal": "Thank you for your positive feedback on the structure and clarity of the paper. \n\n**Reply to Weakness**\n* In the revised version, we will remove such redundant labels to improve readability and streamline the presentation. \n* The mention of “Euclidean” in line 60 was a typo — we intended to refer only to smoothing-based Riemannian ADMM methods. We have corrected this in the revised manuscript and added the reference [38]. \n* We will include a brief explanation of the $\\tilde{\\mathcal{O}}$ notation in the revised manuscript. Specifically, we will clarify that $\\tilde{\\mathcal{O}}(\\cdot)$ hides logarithmic factors in the standard $\\mathcal{O}(\\cdot)$ notation.\n* We have revised the formula in line 172 to correctly reflect the expression $\\lambda_k - \\lambda\\_{k+1}$, and changed the final inequality to an equality as appropriate.\n* We have revised the equation to explicitly define the symbol used in the paper:\n$$\n\\\\quad \\\\quad \\\\|\\lambda\\_{k+1}\\\\| \\leq  \\lambda\\_{\\max},\n$$\nwhere $\\lambda\\_{\\max}: = \\frac{\\beta_0 \\pi^2 }{6} \\\\|\\mathcal{A}x_0 - y_0\\\\|$.\n* In the revised manuscript, we have clarified the definitions of all relevant parameters:\nThe parameter $M$ is defined in Theorem 3.1. The parameters $\\alpha$ and $\\beta$ are defined in Equation (5).  The constant $G$ is defined in Lemma A.2. The symbol $\\mathcal{D}$ in line 431 now explicitly refers back to its definition in line 142, where we define $\n  \\mathcal{D} = \\max\\_{x, y \\in \\mathcal{M}} \\\\|x - y\\\\|.\n  $\nWe have revised the manuscript to ensure that all such symbols are clearly defined and consistently referenced.\n* We have corrected all of them in the revised manuscript. We have also thoroughly proofread the entire manuscript to eliminate other potential typographical errors. \n\n**Reply to Questions**\n* **Regrading the parameter $\\beta_k$.** We thank the reviewer for the thoughtful question about the design of the dual step size $\\beta_k$. The choice of $\\beta_k$ is composed of two parts:\n\n   - **The first part** follows a design in \\[10] (refer to manuscript). Its original purpose is to ensure that the dual variable in the augmented Lagrangian method remains bounded, i.e., $\\\\|\\lambda_k\\\\|$ is uniformly controlled. We incorporate this term, along with the penalty parameter and the dual stepsize, to derive a sharp bound on $\\\\|\\lambda_{k+1} - \\lambda_k\\\\|$, as shown in Lemma 3.1. The constant $\\log^2 2$ included in this part does not play a critical role in the analysis—it is included solely to maintain consistency with the $\\log(k+1)$ term in the denominator.\n\n   - **The second part** is introduced to achieve optimal iteration complexity. This term arises from the analysis in the proof of Theorem 3.1, where it is chosen to balance the convergence terms optimally. In particular, the denominator $\\log^2(k)$ is introduced to **avoid the appearance of a $\\log K$** factor in the final convergence rate — as reflected in Equation (45) of our paper.\nWe will provide a more detailed explanation of the motivation and design of $\\beta_k$ in the revised manuscript to clarify both its theoretical and practical implications.\n* **Regarding the parameter $c_\\{\\tau}$** \n  - We acknowledge that the choice of $c_\\{\\tau}$ may depend on certain problem-specific constants, such as the Lipschitz constant. However, we would like to clarify that this dependence is **not essential**. Since $\\tau_k = c\\_\\tau k^{-1/3}$, the condition on $c_\\tau$ is essentially imposed to ensure that $\\tau_k$ satisfies the required bound, i.e.,  $\\tau_k < \\min\\\\{  \\frac{1}{C}, \\frac{1}{M}, \\frac{1}{16 c\\_{\\beta}\\alpha^2 \\sigma_A^2}\\\\}$ (Theorem 3.1). This condition can always be satisfied after a sufficiently large number of iterations without requiring $c_\\tau$. That is, for any $c_\\tau$, there exists an integer $k_0 > 0$ such that for all $k > k_0$,  $\\tau_k$ satisfies the condition.  Importantly, this does not affect the final convergence guarantees—the same convergence rate still holds. \n  - In our experiments, we tested several different values of $c_\\{\\tau}$ and selected the one that yielded the best performance. While the results do exhibit some variation across different choices of $c_\\{\\tau}$, we observed that the algorithm is not particularly sensitive to this parameter. We will clarify this point after the main theorem and provide additional details in the experimental section.\n* **Regarding the experiments**.  \nWhile preparing additional experiments as suggested, we identified an implementation error in one of the experiments reported in Table 2 (comparison with ManPG in our manuscript): due to an inadvertent use of an output from another method as input to our algorithm, the reported runtime was significantly underestimated. We emphasize that this issue occurred only in this particular experiment; all other experiments were correctly implemented and remain unaffected.\nWe have corrected the implementation and re-run this specific experiment (see **Table 1** below). As suggested by the reviewer, we have replaced ManPG with a stronger baseline, AManPG, in this experiment. The updated results still confirm the competitive performance of our method, and our main findings remain unchanged. All other experiments and theoretical results are unaffected by this issue. \nWe sincerely apologize for the oversight and appreciate the reviewer’s comments, which helped us catch and resolve this error promptly. \n  - **Comparison with AmanPG**. We compare ARADMM with the Riemannian subgradient method (RSG) and the accelerated manifold proximal gradient method (AManPG) \\[1]. ARADMM uses the same settings as in our original experiment. We set the step size $\\eta_k \\equiv 10^{-2}$ for RSG, while the code of AManPG is provided by [1]. **Table 1** reports the averaged results across 10 repeated experiments with random initializations. The termination rules are the KKT conditions with an accuracy tolerance of $10^{-8}$.\n\n  - **Comparison with ALM-based methods**. We compare two ALM-based algorithms: ALMSSN \\[2] and ALMSRTR \\[3], which use a semismooth Newton method and a Riemannian trust region method, respectively, to solve the augmented Lagrangian subproblem on manifolds. The codes for these algorithms are obtained from related work.  **Table 2** reports the function value (denoted by “Obj”), CPU time (in seconds), and the percentage of zero entries in the output (denoted by “Spa”), where the sparsity level is defined as the proportion of entries with a magnitude less than $10^{-4}$, and the results are averaged across 10 repeated experiments with random initializations. ARADMM uses the same settings as in our SPCA experiment. The termination rules are the KKT conditions with an accuracy tolerance of $10^{-8}$.\n\n* **Regrading the choice of $c\\_{\\rho}$**\n  -  We have re-run the experiments with $c\\_{\\rho} = 1$. The result is shown in **Table 1** (See reply to 3rd Reviewer **xPLN** due to word limit). It is shown that the results remain consistent with those reported using $c\\_{\\rho} = 0.6$. \n  - In our response to 3nd Reviewer **xPLN**, we realized that the condition on $c_\\tau$ was missing its dependence on $c_\\rho$. We have now corrected it to:\n$$\nc\\_{\\tau} \\leq \\frac{1}{c_{\\rho}} \\min\\\\{  \\frac{1}{C}, \\frac{1}{M}, \\frac{1}{16 c\\_{\\beta}\\alpha^2 \\sigma_A^2}\\\\}.\n$$\n   - We have carefully addressed and corrected all the typographical errors. We sincerely thank the reviewer for the detailed and thoughtful comments, which have significantly improved the clarity and accuracy of our manuscript.\n\n---\n\n **Table 1: Comparison of RSG, AManPG, and ARADMM for solving the SPCA problem with $\\mu = 0.01$**\n\n| Settings $(n,m,p)$ | RSG Obj | RSG CPU | AManPG Obj | AManPG CPU | ARADMM Obj  | ARADMM CPU |\n| ------------------ | ------- | ------- | ---------- | ---------- | ----------- | ---------- |\n| (300, 20, 8)       | -3.9517 | 0.7970  | -4.2671    | 0.8555     | **-4.4071** | **0.4264** |\n| (400, 30, 10)      | -5.5595 | 1.1105  | -5.8129    | 1.0796     | **-6.0378** | **0.5383** |\n| (500, 40, 12)      | -7.1168 | 1.9584  | -7.3048    | 1.3820     | **-7.6569** | **0.6888** |\n| (600, 50, 14)      | -7.2259 | 2.5911  | -7.4608    | 1.7482     | **-7.9029** | **0.8701** |\n\n---\n\n**Table 2: Comparison of the ALM-type methods for solving the SPCA problem with different settings**\n\n| Settings $(n,m,p,\\mu)$ | Obj (ALMSSN) | CPU (ALMSSN) | Spa (ALMSSN) | Obj (ALMSRTR) | CPU (ALMSRTR) | Spa (ALMSRTR) | Obj (ARADMM) | CPU (ARADMM) | Spa (ARADMM) |\n| ---------------------- | ------------ | ------------ | ------------ | ------------- | ------------- | ------------- | ------------ | ------------ | ------------ |\n| (1500, 20, 8, 0.5)     | 6.0212       | 1.6349       | 93.10        | 4.0169        | 1.2679        | 98.38         | **3.9552**   | **0.9417**   | **99.93**    |\n| (2000, 40, 10, 0.6)    | 8.9390       | 2.7063       | 94.03        | 5.9553        | 1.9281        | 99.85         | **5.9190**   | **1.3272**   | **99.95**    |\n| (2500, 60, 12, 0.8)    | **9.4527**   | 2.9387       | 99.61        | 9.5296        | 3.6644        | 99.95         | 9.4747       | **1.8394**   | **99.96**    |\n| (3000, 80, 15, 1)      | 15.7085      | 4.7114       | 94.65        | **14.8418**   | 4.4791        | 99.96         | 14.8470      | **2.2669**   | **99.97**    |\n\n\n**Reference** （We have cited all those papers in our revised manuscript）\n\n\n\n[1] Huang, W., & Wei, K. (2023). An inexact Riemannian proximal gradient method. Computational Optimization and Applications, 85(1), 1-32.\n\n[2] Zhou, Y., Bao, C., Ding, C., & Zhu, J. (2023). A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds. Mathematical Programming, 201(1), 1-61.\n\n[3] Zhang, C., Xiao, R., Huang, W., & Jiang, R. (2024). Riemannian Trust Region Methods for SC 1 Minimization. Journal of Scientific Computing, 101(2), 32."}]

Author rebuttal:

Meta-review: This paper studies the problem of minimizing the sum of a smooth function and a nonsmooth convex regularizer over a compact Riemannian submanifold embedded in Euclidean space. The authors proposed an adaptive Riemannian ADMM that requires only one gradient evaluation and one proximal update per iteration, attaining optimal iteration complexity. All reviewers give positive scores and highlight both the novelty and practical relevance of the work. I recommend acceptance.
Decision: Accept (poster)