Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems
Authors: Atara Kaplan
Dan Garber
Venue: NeurIPS 2021 Poster (2021)
Keywords: convex optimization
low-rank matrix recovery
low-rank matrix optimization

Abstract: Low-rank and nonsmooth matrix optimization problems capture many fundamental tasks in statistics and machine learning. While significant progress has been made in recent years in developing efficient methods for \textit{smooth} low-rank optimization problems that avoid maintaining high-rank matrices and computing expensive high-rank SVDs, advances for nonsmooth problems have been slow paced. 

In this paper we consider standard convex relaxations for such problems. Mainly, we prove that under a natural \textit{generalized strict complementarity} condition and under the relatively mild assumption that the nonsmooth objective can be written as a maximum of smooth functions, the \textit{extragradient method}, when initialized with a "warm-start'' point, converges to an optimal solution with rate $O(1/t)$ while requiring only two \textit{low-rank} SVDs per iteration. We give a precise trade-off between the rank of the SVDs required and the radius of the ball in which we need to initialize the method. We support our theoretical results with empirical experiments on several nonsmooth low-rank matrix recovery tasks, demonstrating that using simple initializations, the extragradient method produces exactly the same iterates when full-rank SVDs are replaced with SVDs of rank that matches the rank of the (low-rank) ground-truth matrix to be recovered.

Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems
Dan Garber
Atara Kaplan
Technion Israel Institute of Technology Haifa, Israel 3200003
Technion Israel Institute of Technology
Haifa, Israel 3200003
dangar&technie il
ataragold@ccmpus. techni ac. il
Abstract
Low-rank and nonsmooth matrix optimization problems capture many fundamental tasks in statisties and machine learning. While significant progress has been made in recent years in developing efficient methods for smooth low-rank optimization problems that avoid maintaining high-rank matrices and computing expensive high-rank SVDs, advances for nonsmooth problems have been slow paced.
In this paper we consider standard convex relaxations for such problems. Mainly, we prove that under a natural generalized strict complementarity condition and under the relatively mild assumption that the nonsmooth objective can be written as maximum of smooth functions, the extragradient method, when initialized with "warm-start" point, converges requiring only two low-rank SVDs per iteration. We give a precise trade-off between the rank of the SVDs required and the radius of the ball in which we need to initialize the method. We support our theoretical results with empirical experiments several nonsmooth low-rank matrix recovery tasks, demonstrating that using simple initializations, the extragradient method produces exactly the same iterates when full-rank SVDs replaced with SVDs of rank that matches the rank of the (low-rank) ground-truth matrix to be recovered.
optimal solution with rate (11/t) while
Introduction
Low-rank and nonsmooth matrix optimization problems have many important applications in statistics, machine learning, and related fields, such as sparse PCA (21 34), robust PCA [28] 33 2 9 38).
phase synchronization 41 6 29], community detection and stochastic block models I low-rank 22 and more. For many
and sparse covariance matrix recovery
robust matrix completion
of these problems, convex relaxations, in which one replaces the nonconvex low-rank constraint with a trace-norm constraint, have been demonstrated in numerous papers to be highly effective both in theory (under suitable assumptions) and empirically (see references above). These convex relaxations can be formulated as the following general nonsmooth optimization problem:
min g g(X), XES,
where g nDD R is convex nonsmooth, and S,, = (X E S" Tr(X) = 1, > spectrahedron in S S" being the space of n x n real symmetric matrices.
0} is the
Problem ①I despite being convex, is notoriously difficult solve in large scale. The simplest and most general approach applicable to it is the projected subgradient method 3.77, 7 which requires on
in 41 6 29 and [ the authors consider SDPs with linear objective function and affine constraints of the form A = b. By incorporating the linear constraints into the objective function via a &z penalty term of the form (AX) bllz. À 0, obtain nonsmooth objective function.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

each iteration to compute a Euclidean projection onto the spectrahedron Sn, which in worst case amounts O (n²) runtime per iteration. In many applications g(X) follows a composite model, i... g(X) = h(X) + wo (X), where h(-)) is convex and smooth and w(+) is convex and nonsmooth but admits a simple structure (e.g., nonsmooth regularizer). For such composite objectives, without the spectrahedron constraint, proximal methods such as FISTA 4 or splitting methods such as ADMM [32 are often very effective. However, with the spectrahderon constraint, all such methods require on each iteration to apply subprocedure (e.g., computing the proximal mapping) which in worst case amounts to at least (Tr²) runtime. A third type of off-the-shelf methods include those which are based on the conditional gradient method and adapted to nonsmooth problems, see for instance 31 19 36 26]. The advantage of such methods is that no expensive high-rank SVD computations needed. Instead, only single leading eigenvector computation (i.c., rank-one SVD) per iteration is required. However, whenever the number of iterations is not small, these methods still require to store high-rank matrices in memory, even when the optimal solution is low-rank. Thus, conclude, standard first-order methods for Problem ( require in worst case 22()²) runtime per iteration and/or to store high-rank matrices in memory.
In the recent works [17 18 it was established that for smooth objective functions, the high-rank SVD computations required for Euclidean projections onto the spectrahedron in standard gradient methods, can be replaced with low-rank SVDs in the close proximity of a low-rank optimal solution. This is significant since the runtime to compute rank-r SVD of given x n matrix using efficient iterative methods typically scales with rn² (and further improves when the matrix is sparse), instead of n² for full-rank SVD. These results depend the existence of eigen-gaps in the gradient of the optimal solution, which we refer to as a generalized strict complementarity condition. These results also hinge on unique property of the Euclidean projection onto the spectrahedron. The projection onto -
the spectrahedron of a matrix X E S", which admits an eigen-decomposition X- given by
Li A.V.V, is
1
1s. X
Σ
maxf0, 00, A A/V.V.
where À E IR is the unique scalar satisfying En= 00 -) = 1. This operation thus truncates all eigenvalues that smaller than X, while leaving the eigenvectors unchanged, thereby returning matrix with rank equal to the number of cigenvalues greater than X. Importantly, when the projection of X onto S, of rank r. only the first components in the igen-decomposition of X are required to compute it in the first place, and thus, only a rank-r SVD of X is required. In other words and simplifying, [1] 18 show that under strict complementary, at the proximity of an optimal solution of rank r, the exact Euclidean projection equals the rank-r truncated projection given by:
Σ AoverT
î X = IIs
(3)
Extending the results of [17]18] to the nonsmooth setting is difficult since the smoothness assumption is critical to the analysis. Moreover, while [17 [8) rely on certain eigen-gaps in the gradients at optimal points, for nonsmooth problems, since the subdifferential set is often not singleton, it is not likely that a similar eigen-gap property holds for all subgradients of an optimal solution.
In this paper we show that under the mild assumption that Problem IT) can be formulated as smooth poidle-point problem, i.e., the nonsmooth term can be written as a maximum over convex-conenn number of) smooth convex functions, we can obtain results in the spirit of [7 [8] (possibly infinite Concretely, we show that a generalized strict complementarity (GSC) assumption holds for a low-rank optimal solution (see Assumption T in the sequel), the extragradient method for smooth convex-concave saddlc-point problems [23 30 (see Algorithm [bllow), ), when initialized in the proximity of the optimal solution, converges with its original convergence rate of O(L/t), while requiring only two low-rank SVDs per itcration It is important to recall that while the extragradient method requires two SVDs per iteration, it has the benefit of fast O convergence rate, while simpler saddle-poin point methods such
based only achieve O(1/VB) rate 77].
Our contributions can be summarized as follows:
2 note that the extradgradient method computes two crojected-gradient steps on each iteration, and thus two SVDs are needed per iteration.
2

---

We prove that even under (standard) strict complementarity the projected subgradient method, when initialized with "warm-start", may produce iterates with rank higher than that of the optimal solution. This phenomena further motivates our saddle-poing approach. See Lemma 5
We suggest a generalized strict complementarity (GSC) condition for saddle-point problems and prove that when g(-) the objective function in Problem ([), admits a highly popular muddle-point structure (one which captures all applications we mentioned GSC w.r.t. optimal solution to Problem ( implies GSC (with the same parameters) w.r.t. a corresponding optimal solution of the equivalent saddle point problem (the other direction always holds). See Section 3
this paper),
Main result: we prove that for smooth cenee-cconcve saddle-poing problem and an optimal solution which satisfies GSC, the extragradient method, when initialized with a "warm-start", converges with its original rate of ((1/t) while requiring only two low-rank SVDs per iteration. Moreover, we prove GSC facilitates a precise and powerful tradeoff: increasing the rank of SVD computations (beyond the rank of the optimal solution) can significantly increase the radius of the ball in which the method needs to be initialized. See Theorem I
We present extensive numerical evidence that demonstrate both the plausibility of the GSC assumption in various tasks, and more importantly, demonstrate that indeed the extragradient method with simple initialization converges correctly (i.e., produces exactly the same sequences of iterates) when the rank of the SVDs used to compute the (truncated) projections matches the rank of the (low-rank) ground-truth matrix to be recovered, instead of naively using full-rank SVDs (as suggested by (2)). See Section 5
1.1
Additional related work
Since, as in the works 17 [8] mentioned before which deal with smooth objectives, strict com- plementarity plays a key role in our analysis, we refer the interested reader to the recent works
16 39 13 20 which also exploit this property for efficient smooth and convex optimization over the spectrahedron. Strict complementarity has also played instrumental role in recent and very influential works which used it to prove linear convergence rates for proximal gradient methods
42
Besides convex relaxations such as Problem I considerable advances have been made in the past several yeas in developing efficient nonconvex methods with global convergence guarantees for low-rank matrix problems. In [37] the authors consider semidefinite programs and prove that under smooth manifold assumption on the constraints, such methods converge the optimal global solution. In [24] the authors prove global convergence of factorized nonconvex gradient descent from "warm-start" initialization point for non-linear smooth minimization the positive semidefinite cone. Very recently, [ has established, under statistical conditions, fast convergence results from "warm-start" initialization of nonconvex first-order methods, when applied nonsmooth nonconvex matrix recovery problems which are based on the explicit factorization of the low-rank matrix. A result of similar flavor concerning nonsmooth and nonconvex formulation of robust recovery of low- rank matrices from random linear measurements was presented in [25] Finally, several recent works have considered nonconvex low-rank regularizers which result in nonconvex nonsmooth optimization problems, but guarantee convergence only to stationary point [27 40
2 Strict complementarity for nonsmooth optimization and difficulty of applying low-rank projected subgradient steps
Our analysis of the nonsmooth Problem ① naturally depends on certain subgradients of an optimal solution which, in many aspects, behave like the gradients of smooth functions. The existence of such a subgradient is guaranteed from the first-order optimality condition for constrained convex minimization problems:
Lemma 1 (first-order optimality condition, see (3). Let Sr - R be convex function. Then X E Sn minimizes g over Sn if and only if there exists a subgradient G* E Og(X*)) such that X X', G²)")) 2 for all X E S..
3

---

For some G E Og(X") which satisfies the first-order optimality condition for an optimal solution X", if the multiplicity of the smallest eigenvalue equals r" rank(X*) then it can be shown that the optimal solution satisfies a strict complementarity assumption. The equivalence between a standard strict complementarity assumption on some low-rank optimal solution of a smooth optimization problem over the spectrahedron and an eigen-gap in the gradient of the optimal solution was established in [39]. We generalize this equivalence to also include nonsmooth problems. The proof follows similar arguments and is given in Appendix A.I
Definition 1 (strict complementarity). An optimal solution X E Snn of rank r" for Problem ①I satisfies the strict complementarity assumption with parameter 5 > 0, if there exists an optimal
solution of the dual problem (Z (+) E S" x R such that rank (Z*) = n - r", and An-r- (Z)) 2 8.
Lemma 2. Let X E ES, be rank-r" optimal solution to Problem ①]. X* satisfies the (standard)
strict complementarit assumption with parameter 8 >> 0 if and only if there exists a subgradient GO E xx) such that (X- - XX, G*) 2 0 for all X E S, and An-r" (G') (n') 2 8.
Throughout this paper we assume weaker and more general assumption than strict complementarity. namely generalized strict complementarity (GSC), which we present now.
Assumption 1 (generalized strict complementarity). We say optimal solution X to Problem ! satisfies the generalized strict complementarity assumption with parameters r, 6, if there exists a subgradient G (g((X)) such that (X -X* -X, G*) z for all X E S, and (G X, (G')
In 17 the author presents several characteristic properties of the gradient of the optimal solution in optimization problems over the spectrahedron. Using the existence of subgradients which satisfy the extend these properties also to the nonsmooth setting. The following lemma shows that GSC with parameters (r, 7) for some > 0 (Assumption I is a sufficient condition for the optimal solution be of rank at most r. The proof follows immediately from the proof of the analogous Lemma 7 in [17, by replacing the gradient of the optimal solution with subgradient for which the first-order optimality condition holds.
condition in Lemma]] [
Lemma 3. Let X* be an optimal solution to Problem ① and write its eigen-decomposition as X -i A.v.v?" Then, any subgradient G (x") which satisfies iX- Xx, "G) 2 for all X E Sm, admits an eigen-decomposition such that the set of vectors {vi] a set of leading eigenvectors of (-G*) which corresponds to the eigenvalue (-(- -xx (G*). Furthermore, there exists at least one such subgradient.
One motivation for assuming (standard) strict complementarity (Assumption 1 with parameters r = ran and 5 > 0) that it guarantees a certain notion of robustness of the problem to small perturbations in the parameters. It is well known (see for instance 3 that a projected subgradient step from X* with respect to a subgradient G E 0g(X)) for which the first-order optimality condition holds, returns the optimal solution X itself. This implies that rank (Ils,, XX* -/G")) = rank (X*) ) (here 1j is the step-size). Without (standard) strict complementarity however, a small change in the parameters could result in a higher rank matrix. This is captured in the following lemma which is analogous to Lemma 3 in [88,, where again the proof is straightforward from the proof in [18] by replacing the gradient of the optimal solution with subgradient for which the first-order optimality condition holds.
Let X* be an optimal solution of rank r to Problem ( Let G* E 0g(X')) be subgradient at X* such that (X- - X", G*) 2 for all X E Sn. Then, An-r- (G') (G)) if and only for any arbitrarily small Ç >> O it holds that rank (X' 1 > 0, (1 + S)S, [(1 X E S,,), and Il(++)s.. I-] denotes the Euclidean projection onto the set (1 + S)...
Lemma
> r", where
2.1 The challenge of applying low-rank projected subgradient steps
We now demonstrate the difficulty of replacing the full-rank SVD computations required in projected subgradient steps over the spectrahedron, with their low-rank SVD counterparts when attempting to solve Problem ( We prove that a projected subgradient step from a point arbitrarily close to a
DDnotte (Z, s) minxes" (9 + s(1 - Tr(X)) (Z, X)). The dual problem of Problem | written as: max *ER) (o(Z, (Z, s) E do
can be

---

low-rank optimal solution - even one that satisfies strict complementarity (Definition T may result in higher rank matrix. The problem on which we demonstrate this phenomena well known convex formulation of the sparse PCA problem [12]. The proof is given in Appendix A..2]
Lemma (failure of low-rank subgradient descent on sparse PCA), Consider the problem minxes.. (g(X) : - + z1 21 X) + 26 IX[]), where & = (1/VE..... 1/V/,,,....... supported on the first i entries, Z1 =
0.1/vn-k..... ............... 1/v/ - k) is supported on the last n -k k entries, and h S n//4. Then, zz' is a rank-one optimal solution for which strict complemen- tarity holds. However, for any 17 < and any IR. such that ||v|] = support(v) C suppor((2),
and (z.v) = 2 vV zz 2 2k2. holds that rank (Iss, lvv vv) > 1, where GvvT = -2Z Z 2 + कें sign(vv
@g(vv")
Note that the subgradient of the & norm which we choose for the projected subgradient step simply corresponds to the sign function, which is arguably the most natural choice.
3 From nonsmooth to saddle-point problems
To circumvent the difficulty demonstrated in Lemma 5 in incorporating low-rank SVDs into standard subgradient methods for solving Problem (T) we propose tackling the nonsmooth problem with saddle-point methods.
We assume the nonsmooth Problem 1 can be written as a maximum of smooth functions, i.e., gXX) = maxyex/ y(,,y), where K. C Y is some compact and convex subset of the finite linear space over the reals Y onto which it efficient to compute Euclidean projections. We assume f(; y) is convex for all y E IC and f(X.-) -) is concave for all X E S,.. That is, we rewrite Problem ① as the following equivalent saddle-point problem:
min max f(X,y). XES YEK.
(4)
Finding an optimal solution to problem (4) is equivalent to finding a saddle-point y*) E Sn x K. such that for all X E Sn and y E K, f(X*,y) S f(X','' S y").
We make a standard assumption that f(::-) -) is smooth with respect to all components. That is, we assume there exist 8x, By 8xy, Byx x 2 0 such that for any X, X S,, and y, E K. the following four inequalities hold: f (x, y 222 I By lly - y 812,, Vxf (X, Vxf(X, y) I 8xxlly 812, (y,(X,y)
(xf S xx X|FF, f
(X, 22 S Byx X X|| r, where Vx
8f 0f and Vyy= ōy.
We denote by |8 the full Lipschitz parameter of the gradient, that is for any X, X E Sn and y, y E K.
(X. - Vy.((X,)) - (Vx/(X,))) - (y,(X, S B (X, Y) (X,5)1.
where || || denotes the Euclidean norm over the product space S, x Y. The relationship between the full Lipschitz parameter 3 and its components 3x, By 3xv. Syx can be written as B = /2 max
(v
& + 8xx,
8 + Bx,, }. See proof in Appendix B
The following lemma highlights a connection between the gradient of a saddle-point of 44 and subgradients of an optimal solution to (I) for which the first order optimality condition holds. One of the connections we will be interested in, is that GSC for Problem ① implies GSC (with the same parameters) for Problem ( However, to prove this specific connection we require an additional structural assumption on the objective function g(-). We note that this assumption holds for all applications mentioned in this paper.
Assumption 2. g(X) is of the form g(X) h(X) m y (A(X)- bb), where h(-)) smooth and convex, and A is a linear map.
Lemma 6. If(X yy* is a saddle-point of Problem (4) then X* is an optimal solution to Problem
I. Vxf(",, ) E Og(X*), and for all X E Sn it holds that (X - X*, fxf(X" ,y*)) > 0.
Conversely, under Assumption 2 X is an optimal solution to Problem M. and G E xX
which satisfies (X- -x* S*, 0 for all X E Sn then there exists y E arg maxyek s(X",,) ,y)
such that (X' yy) is saddle- saddle-point of Problem and V fx (X",)"") G
5

---

The proof is given in Appendix C.1 the saddle-point problem and subgradient of a corresponding optimal solution in the equivalent nonsmooth problem established in Lemma 6 naturally leads to the formulation of the following generalized strict complementarity assumption for saddle-point problems.
The connection between the gradient of an optimal solution to
Assumption (generalized strict complementarity for saddle-points). We say a saddle-point yX" E Sn x K of Problem 4 with rank(XX) = satisfies the generalized strict complementar- ity assumption with parameters 2 r" 8 0, if (xx' .y*) >a (VVxf(X'.'") y")) 8.
Remark 1. Note that under Assumption 2 due Lemma 6 GSC with parameters r, ô for some optimal solution X to Problem (1) implies GSC with parameters r, å to a corresponding saddle-point ,X*)") of Problem (4. Nevertheless, Assumption 2 not necessary for proving our convergence results for Problem which are directly stated in terms of Assumption 3
4 Projected extragradient method with low-rank projections
In this section we formally state and prove our main result: the projected extragradient method for the saddle-point Problem (4), when initialized in the proximity of a saddle-poing point which satisfies GSC (Assumption B). converges with its original O(1/t) rate while requiring only two low-rank SVD computations per iteration.
Algorithm 1 Projected extragradient method for saddle-point problems (see also
23 30
Input: sequence of step-sizes {nt)22 Initialization: (1) E S,, x K. for 1. = 1, 2.... do
Z,+1 IIs,, X, T/ ViVxJC XXXx, Yc)
Wo+1 1kxly; + 7h Vy, ye)
X,+1 Ils,, [X, T/e f w(+1)l
Yt+1 = 1kx y: + T1 Vy Wi+1l
end for
Theorem 1 (main theorem). Fix an optimal solution (X", E S, K. to Problem 4 Let i
denote the multiplicity of Xn (Vx (xx,(""y yy")) and any r 2 i define 5(T) = (Vxf y*)
Xn (xx y²). Let {(x,, Yr) h22 and {Zi, w2))222 be the sequences of iterates generated by Algorithm| with fixed step-size 11 = min the initialization (X) satisfies (1 (X', xx"'y") (o()), where
Assume
2 13 f.x
/ 3x 3x+ BytByx
Viö(r -
8(r)
(o(r) (1+ (2+ (2+ 2) max (Bx, Bxy})
7
2
(1+1/v7)
Then, for all t 2 1. the projections Is, [X, - x ve)l and Iss. [X, - 1/ Xff We+1)l
can be replaced with their rank-r truncated counterparts (see (3) without changing the sequences (Xe, and [Zz, we)hez2. and for any T 2 0 it holds that
1
max f (Z yEK
min f(X, W(+1) XES.
T
D2 max V 83 82
82 + Rxy 2 (Bx + (xx); + Bbx))
xxx /
T
where D = SUP((x))) xK (X, -Z, w)ll
Remark 2. Note that Theorem implies that if standard striet complementarity holds for Problem (4) that is Assumption 3 holds with r -- rank(X") and some 5 > O, then only rank-r" SVDs are required so that Algorihhm| 7 converges with the guaranteed convergence rate of (1/t),, when initialized with a "warm-sturt". Furthermore, by using SVDs of rank >> r", with moderately higher values of r, we can increase the radius of the ball in which Algorithm 7 needs to be initialized quite significantly.

---

The complete proof of Theorem 1 is given in Appendix D Below we give short sketch of the proof.
Proof sketch for Theorem 7 The convergence rate of Algorithm T well known in the literature (see Appendix [J for completeness). Thus, we focus on the novel part of the low-rank projections. A. From (2) can be deduced that for any P E S" holds
For simplicity consider the case
that rank([Ts., (P)) S f if and only the condition Σ (P) 2 + (P) holds. Denote
p= X =X="
V/X [X',X y") From Lemma and Lemma 3 follows that
Vi < rank (X'): APP) = (x - nAw (Vxf(X,, ,y));
Vi rank (X*): {;(P") -
,y)).
Using this and the fact that An- (X >n ,")) for all i S F we have,
mnn(X')
(PPP = Σ Ax(*)) - Σ An (xx = TT(X - Tf Vx y*))
= =1 =
+
FAF++( ()F
(5)
not only satisfies the condition that ensures its projection onto Sn of rank at most F, but it satisfies it with a positive slack of nfF Also, for any (X. y) sufficiently close to (X', Thus, by applying perturbation bounds for the eigenvalues of symmetric matrices to Eq. (5) and using the fact that the positive slack mf8((F) in the RHS of (5) allows to absorb sufficiently small errors, we can establish that for such points (X, y) it holds that rank PP) < F. A similar argument shows that the second primal step in Algorithm [ X,+1
Thus, P p==X- X -X'''XX
using the smoothness of f. we have that P = X V (X, y) is close to P
ITs,, [ 1) VX [Zz+1, Wx+1 )}, also results in matrices of rank at most F when Z,, W, are also in the proximity of X" x",". Finally, we prove a complementary argument, that when initialized in the proximity of (x*, .y" ). the iterates of Algorithm stay in the proximity of (X*,y") throughout all iterations.
y".
Remark 3. Note that when applying Algorithm 7 towards minimizing a nonsmooth objective of the form oXX maxyek y) (as discussed in Section 3 a guarantee of the form
T Eim maxyek ((i+1l T Ei= minxes, f(X, Woi1) S C, for some c >> 0, which is what we get from Theorem implies particular that mintetry -(x:)-9(() S where X* is minimizer of g(-) over Sn,
Remark 4. A downside of considering the saddle-point formulation 44 when attempting to solve Problem (T that arises from Theorem 7 is that not only do we need a "warm-start" initialization for the original primal matrix variable X, in the saddle-point formulation we need a "warmmstart" for the primal-duse pair (X.y) Nevertheless,
demonstrate extensively in Section 5 it seems that very simple initialization schemes work very well in practice.
4.1
Effieiently-computabee certificates for correctness of low-rank projections
Since Theorem - Jonly applies in some neighborhood of an optimal solution, it is of interest to have a procedure for verifying if the rank-r truncated projection of given point indeed equals the exact Euclidean projection. In particular, from a practical point of view, it does not matter whether the conditions of Theorem I hold. In practice, long as the truncated projection (see (3)) equals the exact projection (see (2). we are guaranteed that [
correctly with rate (1/tt), without needing to verify any other condition. Luckily, the expression (2) which characterizes the structure of the Euclidean projection onto the spectrahedron, yields exactly such a verification procedure. As already noted in [17, for any X E S", we have Niç XX] Ils., [X] if only if the condition Σe= >x(X) 2 1 + Art1 (X) holds. Note that verifying this condition simply requires increasing the rank of the SVD computation by one, i.e., computing a rank-(r + 1) SVD of the matrix
to project rather than rank-r SVD.
5 Empirical evidence
The goal of this section to bring empirical evidence support of our theoretical approach. We consider various tasks that take the form of minimizing a composite objective, i.c., the sum of
7

---

smooth convex function and a nonsmooth convex function, where the nonsmoothness comes from either an é nooor or l norm regularizer penalty term, over a r-scaled spectrahedron. In all cases the nonsmooth objective can be written as a saddle-point with function y(X,y) which is linear in and in particular satisfies Assumption 2
The tasks considered include 1. sparse PCA, 2. robust PCA. 3. low-rank and sparse recovery, 4. low-rank estimation, under variety of parameters. Due to lack of space many of the results are deferred to Appendix
phase synchronization, and 5. dinearly-constraine
For all tasks considered we generate random instances, and examine the sequences of iterates generated by A (c) procedures. Out of both sequences generated, we choose candidate for the optimal solution to be the iterate for which the dual-gap, which is a certificate for optimality, is smallest. See Appendix
(Zz, We) when initialized with simple initialization
In all tasks considered the goal is to recover a ground-truth low-rank matrix Mo S" from some noisy observation of it M M, + N, where N E S" is noise matrix. We measure In all experiments we measure the relative | [|
the signal-to-noise ratio (SNR) as |
initialization eπrоr by
Tr(Ma X1
Mo
Mo and similarly we measure the relative re- |Ma
Note that in some of the experiments we take < Tr(Ma) to prevent the method from overfitting the noise. In addition, we measure the (stan- dard) strict complementarity parameter which corresponds to the eigen-gap gap( (opf(xxX'' y")) :=
covery error by Tr(Ma) X - M
An (Vxf(X",y")) An (Vxf(X*, y")),,)) r = rank
In all experiments we use SVDs of rank rank (Mo) to compute the projections in Algorithm T according to the truncated projection given in 33 To certify the correctness of these low-rank projections (that is, that they equal the exact Euclidean projection) we confirm that the inequality
E (P 2 T + r (P,) always holds for P1 = X2 XX,, Y,) and P = X, V (Z We+1) (see also Section 4.1) Indeed, we can now already state our main observation from the experiments:
In all tasks considered and all random instances generated, throughout all iterations of Algorithm
7 when initialized with simple "warm-starl" strategy and when computing only rank-r truncated projections, = rank(Mo), the truncated projections of P1 Xx V/
1XX,Y Y,) x and P =
Sg-vVV xf (Zi+1. W++1) equal their exact full-rank counterparts. That is, Algorithm 7 using only rank-r SVDs, computed exactly the same sequences of iterates it would have computed if using full-rank SVDs.
Aside from the above observation, in the sequel we demonstrate that all models considered indeed satisfy that: 1. the returned solution, denoted (X*, y"",")), ), is of the same rank as the ground-truth matrix and satisfies the strict complementarity condition with non-negligible parameter (measured by the eigengap (Vx y")) An Ln(Vx(XX' "y"))))) 2. the recovery error of the returned solution indeed improves significantly over the error of the initialization point.
Sparse PCA:
We consider the sparse PCA problem in a well known convex formulation taken from 12 and its equivalent saddle-point formulation:
min X MM) + +||X|| = min Tn - X=0
max (X, -M) + A(X, Y)),
X II X
where M = zz + +
is a noisy observation of a rank-one matrix zz T, with z being sparse unit vector. Each entry 2, is chosen to be 0 with probability 0.9 and U1,.... 10) with probability 0.1, and then we normalize z to be of unit norm. We test the results obtained when adding different magnitudes of Gaussian or uniform noise, We set the signal-to toll--ttoooieeee ratio (SNR) to be constant. Thus, we set the noise level to c = SNR IF for our choice of SNR. We initialize the
+ NT)
2
X variable with the rank-one approximation of M. That is, we take X, = u u where u, is the top eigenvector of M. For the Y variable we initialize it with Y, sign(X,) which is subgradient of ||X||| |1. We set the step-size to 1) = 1/(2)) and we set the number of iterations to = 1000 and for any set of parameters average the measurements over 10 i.i.d. runs.
8

---

Table Numerical results for the sparse PCA problem. Niy U|0 1], SNR 0.05.
dimension (n)
100
200
400
600
À
0.04
0.02
0.01
0.0067
initialization error
1.7456
1.7494
1.7566
1.7625
recovery error
0.0425
0.0244
0.0149
0.0100
dual gap
2.0 x 10-9
5.8 10
4.5 X 10
0.0018
gap V y"))
0.7092
0.7854
0.8340
0.8622
Robust PCA: We consider the robust PCA problem [28] in the following formulation:
min T()) X=-
J M
min Tr K)=,
max
- (X-M, Y),),
|1
X=u
where M rZoZo + (N is sparsely-corupted observation of some rank-r matrix ZoZo. We choose Zo E Ruxr to be random unit Frobenius norm matrix. For N E R=x" we choose each entry be with probability
1/VVi and otherwise 1 -1 with equal probability. We initialize the X variable with the projection X, [[(nx)=r,, X=03 [M], and the Y variable with Y1 = sign(X; M). We vary the rank of Zo. which in turn determines the step-size 1/. We set the trace bound = 0.95 Zo ), and the number iterations = 30, 000. For every set of parameters we average the measurements over 10 i.i.d. runs.
Table 2: Numerical results for the robust PCA problem. rank (Zo
10, step-size 17
dimension (n)
100
200
400
600
SNR initialization error
0.0229
0.0077
0.0026
0.0014
1.5729
1.6485
1.6317
1.5949
recovery error
0.0079
0.0081
0.0073
0.0065
dual gap
0.0139
0.0338
0.1533
0.3561
gap( V (X" yy))
1.7945
16.9890
48.9799
82.2727
Linearly-constrained low-rank estimation:
Consider the following penalized formulation:
min (X, -M) + AIIA(X) -bll2 = min max (X, -M) + A(A(X) - b, Tx(X==1, X
X)LL, X
where M = 2azy + (N + T is a noisy observation of some rank-one matrix Zozy (0, We take A(X) X with matrices A ,,, Am S" of the form A; v,v, such that V. (). We take b E R such that rank-one approximation of M. That is, we take X; u,uTT where is the top eigenvector of M. The y variable initialized with y1 = (A(X,) b)/l[{((,,) bl12- We set the number of constraints to the number of iterations in each experiment to 2000 and for each value n we average the measurements over 10 i.i.d. runs.
such that ||zo||2 1 and the noise matrix is chosen ((A,, X)...., (Am,
(A,, Zozz ). We initialize the X variable with the
the penalty parameter to À 2, and the step-size to 7 1/(2X). We set
Low-rank and sparse matrix recovery: low-rank and sparse covariance matrix optimization problem:
We consider the problem recovering simultancously which can be written as the following maddle-point
35
min Th
X MI X|XX||
min
X S1
max
MI X(X, Y),
=1,
Tr()
0
X
where M = Zo + SNN + is a noisy observation of some low-rank and sparse covariance
matrix Zo T
We choose Zo gaxr to be sparse matrix where each entry Zoi,j is chosen to be

---

Table Numerical results for the linearly-constraie low-rank matrix estimation problem.
dimension (n)
100
200
400
600
SNR initialization error
0.15
0.075
0.04
0.027
0.1219
0.1324
0.1242
0.1228
recovery error
0.0437
0.0617
0.0685
0.0735
dual gap
5.3 10-11
5.0 x 10
8.5 x 10
2.3 x 10
gap V x fX" y")) |AAX 2
0.2941
0.3409
0.4690
0.5069
0.0080
0.0082
0.0079
0.0073
O with probability 0.9 and Ul,,..., 10} with probability 0.1, and then we normalize Zp to be of unit
Frobenius norm. We choose N II). We test the model with rank = 5, 10. We set
2| Z, l|
the signal-to-noiss to-se ratio (SNR) to be a constant and set the noise level to e SNR- N for our choice of SNR. We initialize the X variable with the rank-r approximation of M. That is, we take X1 U,diag aMa,, [diag( A,)]] U, where U,A,UU, is the rank-r eigen-decomposition of M and A., {z R"
0, Σ -= 2; = } is the simplex of radius in RR.. For the Y variable we initialize it with Y1 = sign x1) which is subgradient of |X||11 We set the step-size to 1 = 1, r = 0.7 Tr ), and the number iterations in each experiment to = 2000. For each value of r and average the measurements 10 i..dd runs.
Table Numerical results for the low-rank and sparse matrix recovery problem.
dimension (n)
100
200
400
600
4 r rank Z,
= 5, SNR 2.4
A initialization error
0.0012
0.0006
0.0003
0.0002
0.2132
0.2103
0.1983
0.1907
recovery error dual gap gap( (xx
0.0641
0.0478
0.0349
0.0274
9.0 x 10
4.3 x 10
1.4 x 10
7.3 x 10-5
0.0148
0.0200
0.0257
0.0277
4
rank rank 2g)
= 10, SNR = 4.8
0.0007
0.0004
0.0002
0.0001
initialization error
0.1855
0.1661
0.1527
0.1473
recovery error dual gap
0.0702
0.0403
0.0268
0.0356
4.9 x 10
6.6 x 10
4.2 x 10
3.4 x 10-5
gap( Vx (X'''"y))
0.0072
0.0142
0.0187
0.0160
6
Discussion
This work expands upon a line of research that aims harness the ability of convex relaxations to produce low-rank and high-quality solutions to important low-rank matrix optimization problems, while insisting on methods that, least locally, store and manipulate only low-rank matrices. Focusing on the challenging case of nonsmooth objective functions and following our evidence for the difficulties of obtaining such result for subgradient methods (Lemma (5). we consider tackling nonsmooth objectives via saddle- point formulations. We prove that indeed under a generalized strict complementarity condition, a state-of-the-art method for convex-concave saddle-point problems converges locally while storing and manipulating only low-rank matrices. Extensive experiments over several tasks demonstrate that our conceptual approach of utilizing low-rank projections for more efficient optimization is not only of theoretical merit, but indeed seems work well in practice.
10

---

Acknowledgements
This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No. 1108/18).
References
[1] Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):64466653 -5341, 2017.
[2] Praneeth Netrapalli, UN Niranjan, Sujay Sanghavi, Animashree Anandkumar and Prateek Jain. Non-convex robust pea. Advances in Neural Information Processing Systems, page 1107-1115, 2014.
[3] Amir Beck. First-order methods in optimization. SIAM, 2017.
[4] Amir Beck and Mare Teboulle. A fast iterative bbrinkage-threshlldde algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-2000 202, 2009.
[5] Dimitri Bertsekas. Nonlinear programming. Athena Scientific, 1999.
[6] Afonso S. Bandeira, Nicolas Boumal, and Amit Singer. Tightness of the maximum likelihood semidefinite relaxation for angular synchronization. Mathematical Programming, 163(1-2):145- 167, 2017.
[7] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-357) 2015.
[8] Vasileios Charisopoulos, Yudong Chen, Damek Davis, Mateo Díaz, Lijun Ding, and Dmitriy Drusvyatskiy. Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence. Foundations of Computational Mathematics, pages 1-89, 2021.
[9] PXinyang Yi, Dohyung Park, Yudong Chen and Constantine Caramanis. Fast algorithms for robust pca via gradient descent. Advances in Neural Information Processing Systems, page 4152-4160, 2016.
[10] Yudong Chen, Huan Xu, Constantine Caramanis, and Sujay Sanghavi. Robust matrix completion and corrupted columns. In Proceedings of the 28th International Conference on Machine Learning (ICML-I1), pages 873-880. Citeseer, 2011.
[11] Frank H. Clarke. Optimization and Nonsmooth Analysis. SIAM, 1990.
[12] Alexandre d' Aspremont, Laurent Ghaoui, Michael I Jordan, and Gert RG Lanckriet. A direct formulation for sparse pca using semidefinite programming. SIAM review, 49(3):434-448, 2007.
[13] Lijun Ding, Jicong Fan, and Madelcine Udell. kfw: frank-wolfe style algorithm with stronger subproblem oracles, 2020.
[14] Dmitriy Drusvyatskiy and Adrian S Lewis. Error bounds, quadratic growth, and linear conver- gence of proximal methods. Mathematics of Operations Research, 43(3):919-948, 2018.
[15] Francisco Facchinei and Jong-Shi Pang. Complementarity Problems, volume II. Springer-Verlag New York, 2003.
Variational Inequalities and
[16] Dan Garber. Linear convergence frank-wolfe for rank-one matrix recovery without strong convexity, arXiv preprint arXiv:1912.01467, 2019.
[17] Dan Garber. On the convergence of projected-gradee methods with low-rank projections for smooth convex minimization over trace-norm balls and related problems. SIAM Journal on Optimization, 2019.
[18] Dan Garber. On the convergence of stochastic gradient descent with low-rank projections for convex low-rank matrix problems. Conference on Learning Theory, COLT, 125:1666-1681, 2020.
11

---

[19] Dan Garber and Atara Kaplan. Fast stochastic algorithms for low-rank and nonsmooth matrix problems. The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS, 89:286-294, 2019.
[20] Dan Garber and Atara Kaplan. On the efficient implementation of the matrix exponentiated gradient algorithm for low-rank matrix optimization. arXiv preprint arXiv:2012. 10469, 2020.
[21] Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. Journal of Computational and Graphical Statistics, 15:2006, 2004.
[22] Olga Klopp, Karim Lounici, and Alexandre B Tsybakov. Robust matrix completion. Probability Theory and Related Fields, 169(1):523-55)) 564, 2017.
[23] G.M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
[24] Srinadh Bhojanapalli, Anastasios Kyrillidis, and Sujay Sanghavi. Dropping convexity for faster semi-definite optimization. In 29th Annual Conference Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 530-582, 2016.
[25] Xiao Li, Zhihui Zhu, Anthony Man-Cho So, and Rene Vidal. Nonconvex robust low-rank matrix recovery. SIAM Journal on Optimization, 30(1);660- 6666666666666666 2020.
[26] Francesco Locatello, Alp Yurtsevert, Olivier Fercoq, and Volkan Cevhert. Stochastic frank- wolfe for composite convex minimization. Advances in Neural Information Processing Systems, 32, 2019.
[27] Canyi Lu, Jinhui Tang, Shuicheng Yan, and Zhouchen Lin. Generalized nonconvex nonsmooth low-rank minimization. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4130 2014.
[28] Emmanuel J. Candès, Xiaodong Li, Yi Ma and John Wright. Robust principal component analysis? Journal of the ACM, 58, 2009.
[29] Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenaee Phase transitions in semidef- inite relaxations. Proceedings of the National Academy of Sciences, (13(16):E2218EE222 2016.
[30] Arkadi Nemirovski. Prox-method with rate of convergence o o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. on Optimization, 15(1):229-251 251,, 2005.
[31] Gergely Odor, Yen-Huan Li, Alp Yurtsever, Ya-Ping Hsieh, Quoe Tran-Dinh, Marwa El Halabi, and Volkan Cevher. Frank-wolfe works for non-lipschitz continuous gradient objectives: scalable poisson phase retrieval. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages
leee, 2016.
[32] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1):1-122, 2011.
[33] John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng and Yi Ma. Robust principal compo- nent analysis: Exact recovery of corrupted low-rank matrices via convex optimization. Advances in Neural Information Processing Systems 22, pages 2080-2088, 2009.
[34] Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro. Online learning for matrix factorization and sparse coding. Journal of Machine Learning Research, 11:19-60, 2010.
[35] Emile Richard, Pierre-Andr'e Savalle and Nicolas Vayatis. Estimation of simultaneously sparse and low rank matrices. Proceedings of the 29th International Conference on Machine Learning, 2012.
12

---

[36] Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Projection efficient subgradient method and optimal nonsmooth frank-wolfe method. In Advances in Neural Information Processing Systems, volume 33, pages 12211-12224 Curran Associates, Inc., 2020.
[37] Nicolas Boumal, Vladislav Voroninski, and Afonso S. Bandcira. Deterministic guarantees for factorizations of smooth semidefinite programs. Communications Pure and Applied Mathematics, 73(3):581 608, 2020.
[38] Cun Mu, Yuqian Zhang, John Wright and Donald Goldfarb. Scalable robust matrix recovery: Frank-wolfe meets proximal methods. SIAM Journal on Scientific Computing, A825): 2016.
[39] Lijun Ding, Yingjie Fei, Qiantong Xu and Chengrun Yang. Spectral frank-wolfe algorithm: Striet complementarity and linear convergence. ICML, 2020.
[40] Quanming Yao, James T Kwok, Taifeng Wang, and Tie- Yan Liu. Large-scale low-rank matrix learning with nonconvex regularizers. IEEE transactions pattern analysis and machine intelligence, 41( (1(11):2228-2643 2018.
[41] Yiqiao Zhong and Nicolas Boumal. Near-optimal bounds for phase synchronization. SIAM Journal Optimization, 28(2):989-100) 2018.
[42] Zirui Zhou and Anthony Man-Cho So. A unified approach to emror bounds for structured convex optimization problems. Mathematical Programming, 165(():689-722, 2017.
13


Reviews:
[{"review_id": "tHR7k2QL_4e", "reviewer": "Reviewer_M6vn", "summary": "This paper studies the problem of minimizing a convex, non-smooth objective function of matrices with low-rank constraints. For the smooth counterpart of the same problem, it has been previously shown that SVDs computed during the iterations of algorithms such as projected sub-gradient descent can be replaced by low-rank SVDs, thus improving the computational complexity. This paper studies the conditions under which such a replacement can be used for non-smooth objective functions. \n\nThe main result of the paper consists of describing the class of non-smooth functions for which low-rank SVDs can be used. The paper proves theoretically and empirically that for non-smooth functions that have a saddle point structure (can be written as a sum of a smooth function and a point-wise maximum of affine functions), and when the initialization is within a certain radius w.r.t the ground truth, low0rank SVDs lead to the same solution as full SVDs and a O(1/t) convergence can be achieved. \n\nFurther, the paper also shows empirically that using low-rank SVDs on non-smooth objectives leads to the same solution as using full SVDs. ", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The paper addresses a clear gap in the literature and provides an elegant solution. The main result of the paper is novel and interesting to the community. \n\nQuality: The presented results are insightful and the quality of the presentation is very good. The paper makes strong technical contributions and the proofs seems to be correct. \n\nClarity: The paper is very clearly written and provides an excellent coverage of existing literature. The authors also do a very good job of describing how their work relates to existing literature and the paper is self-contained in this sense. \n\nSignificance: The presented results are definitely relevant to the community. \n\nSome suggestions:\n\nIt would be very useful if the authors provided some interpretation of the main results. In particular, the radius constraint on the initialization is hard to visualize and any insight into how restrictive this is (at least theoretically) will help the reader to better appreciate the results. Maybe the authors could use specific examples to characterize the radius.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors address some limitations of the assumptions made such as the saddle-point structure and the requirements on the warm-start.\n\nThere are no negative societal impacts of this work. ", "review_text": "", "extra_scores": {"ethical_concerns": "None. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "hNBOU2n9gSe", "reviewer": "Reviewer_3rGU", "summary": "The paper considers a class of nonsmooth and low-rank matrix optimization problems. Major contributions include: (1) Discuss strict complementarity for nonsmooth problems and challenges of low-rank projected subgradient steps. (2) Under certain assumptions, a special type of nonsmooth problems can be reformulated as maximum of smooth ones and thereby a minimax form, and develop a projected extragradient method with low-rank projections. (3) Use the proposed method to solve several classical low-rank approximation problems in applications. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers a special type of nonsmooth matrix problems which can be expressed as a minimax form and then design a projected extragradient type of algorithm, which shows incremental novelty and improvement. The title could be improved to avoid repetition of \"low-rank\". Presentation and English could be substantially improved. There are some confusing statements throughout the paper, e.g., lines 4-5, the term \"correct convergence\" in lines 15, 92-93, \"Very recently\" -> \"More recently\" in line 106. In line 123, which type of \"multiplicity\" does it refer to? References about strict complementarity in Definition 1 could be added. In line 184, \"From nonsmooth ... \" -> \"From nonsmooth to smooth ...\"? In line 256, \"RHS\" was not defined or explained. In the equation between lines 315-316, is $X$ required to be symmetric in this setting? Similarly, does the constraint $X\\in \\mathcal{S}_n$ need to appear in the linearly-constrained low-rank estimation problem so that Alg.1 can be applied?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The three assumptions about the nonsmooth matrix problem of interest may not be satisfied simultaneously in application. Possible issues and feasibility of the proposed algorithm could be discussed. Furthermore, it may be difficult to distinguish between high-rank and low-rank SVDs, the corresponding wordings could be made more precise. Some specific examples would be helpful for the illustration purpose. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "-_mODkGkF1D", "reviewer": "Reviewer_Ahfq", "summary": "In this paper, motivated by a new efficient method in solving smooth low-rank matrix optimization problems, the authors propose to extend the method to nonsmooth problems. However, direct generalization is not possible, as is shown for a specific failure case. Thus, the authors propose to introduce some auxiliary parameters and transform the original nonsmooth problem to a smooth saddle-point problem. The authors then extend to the method of this new problem and derive a new algorithm that is suitable for\nthe saddle-point problem. Theoretically, the authors proved the convergence of their proposed method. And empirical results verify the correctness of their proposed method.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In my opinion, the idea of extending methods on the smooth low-rank matrix optimization problem that only needs low-rank SVD to the nonsmooth case is interesting. \nHowever, the theoretical analysis is a bit confusing and needs more clarification. And the empirical results are definitely not sufficient enough.  Therefore, the work is not ready for NeurIPS 2021 in the current version. \n\n- The presentation of the theoretical part is a bit confusing in the current version. It is hard to see how the theoretical results are derived and which assumption is necessary for the result. \n\n- Moreover, some assumptions in theoretical analysis lacks enough\njustification. It is not clear how these assumptions are satisfied in real-world problems. \n\n- Empirical results are not sufficient enough either. Specifically, no other baseline methods are compared in experiments, which makes it hard to evaluate the improvements of the proposed method. \n\n=== Main concerns ===\n- What is the relation between these assumptions? I suppose Assumption 3 is actually equivalent to Assumption 1 (except in a different form), is this correct? If so, Assumption 3 is not needed and should be derived based on Assumption 1 for the objective $g(\\mX)$,  and the proof for Theorem 1 may also need some changes, since it is directly based on Assumption 3. \n\n- Assumption 2 for the objective $g(\\mX)$ is also a bit confusing.  In Section 3, Line 189, the authors first claim that $g(\\mX)$ can be written as $g(\\mX)=\\max_{\\vy} f(\\mX, \\vy)$, and introduce some assumptions on the new function $f$. However, in Assumption 2, the authors restrict the objective to be the form of $g(\\mX) = h(\\mX) + \\max_{\\vy} \\vy^{\\top}(\\gA(\\mX)-\\vb)$.  It will be better if the authors can change the assumption on $f(\\mX, \\vy)$ to $h(\\mX)$. \n\n- Based on the previous concern, it will also be better if the authors can show that how the application considers in the paper satisfy this assumption.\n\n- Empirical results are far from sufficient. Although the authors have demonstrated the correctness of the proposed method in many applications, there are no other baseline methods compared in experiments. This makes it difficult to compare the proposed method with existing methods.\n\n- In addition, while the authors argue that their method has a better convergence speed, the running time analysis is not present in experiments. Therefore, these theoretical analyses lack empirical support. \n\n=== Minor concerns ===\n- The authors seem to assume that the rank of the optimal solution is known in advance. However, this may not always be the case. It will be better if the authors can provide some analysis on the influence of the rank $r$ that counts as a hyper-parameter for the proposed method. \n\n- What does Remark 1 mean? Specifically, in Line 224-225, the authors write that ``Assumption 2 is not necessary for proving our convergence results''. However, in Theorem 1, I suppose the convergence rate depends on the Lipschitz parameters (i.e. the $\\beta$'s), thus assumptions on the objective are still needed? \nThis needs some clarification. \n\n- Also, in Line 271-272, the authors write that ``from a practical point of view, it does not matter whether the conditions of Theorem 1 hold''. \nHowever, I suppose Theorem 1 is the main theoretical result in this paper. Are you claiming that this result is actually useless? This is very confusing. \n\n- Some typos: in Line 56-57, the authors write that ``In other words and simplifying ...''. This is a bit confusing. Is this a typo?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the main reviews above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies an important class of non-smooth low rank matrix optimization problems.  Recent work established that for corresponding smooth problem, high rank SVD computations could be replaced with low rank SVDs in the proximity of an optimal solution.  This work establishes a corresponding result in the challenging non-smooth case, under appropriate assumptions.  The authors use empirical observations to justify the reasonability of these assumptions.   This work provides a significant theoretical extension and fills an important hole in the literature by providing theoretical justification for techniques that are used to efficiently solve a broad class of non-smooth low rank matrix optimization problems.  

Decision: Accept (Poster)