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 7.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 = rank(X*) 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) : -m==== + 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)
Wi+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) = (Vx 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+ (1+ (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/ XVf 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',XX y") From Lemma and Lemma 3 follows that
Vi < rank (X'): APP) = (x - nAw (Vxf(X,, ,y));
Vi rank (X*): {;(P") -n
,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- Xx -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, Woi)) 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-11 (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/ x 1XX,Y Y,) 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 paxr 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 In). We test the model with rank = 5, 10. We set
2| Z, l|
the signal-to-noiss to-so 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 |X1|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-thresolldde 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(2):689-722, 2017.
13


Reviews:
[{"review_id": "yvHcCvlBhg", "reviewer": "Reviewer_zvmw", "summary": "This paper develops an algorithm for nonsmooth convex objectives with a trace norm ball constraint. It produces an algorithm using the extragradient method and shows the method enjoys lower iteration complexity due to strict complementarity.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "I think this is a good paper and it solves a class of nonsmooth problems that are interesting. I have a few questions that would like to hear the author's comment on them. \n\n1. Theoretically, the algorithm needs a warm start. Even though I think warm starting the matrix variable X is easy. It is not clear to me how to initialize the vector variable y. Can the author comment on why the y is initialized in the way in Section 5? Is there any rule being used for initializing y in section 5? \n\n2. Is there any particular reason to use the extragradient method?  Is it because simpler methods that use only one matrix variable and one vector variable, and one gradient update in each iteration, cannot have the same convergence guarantees as the extragradient method in general? \n\n3. Does the 1/t rate appears in the examples in section 5? Or do you observe an even faster convergence?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not see the author mentioned any limitation of the current work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "u5hyrsrIMtb", "reviewer": "Reviewer_u8Jo", "summary": "This paper develops an extragradient method for low-rank and nonsmooth matrix optimization problems. Under certain conditions, the proposed method converges to an optimal solution with rate O(1/t). Numerical experiments are provided to support the theoretical results.", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "1. I think authors should use more space to the assumptions imposed on the objective function and the optimal solution. The current version is not straightforward to see if the assumptions are stringent or easy to hold. For example, it would make paper more motived to show some applications in the introduction where the assumptions do hold.\n2. It would be better to discuss the initialization condition in Theorem 1. Is this initialization requirement easy to meet?\n3. In the numerical experiment, there is no comparison with the state-of-the-art algorithms. Therefore, it is unknown if the proposed algorithm improves over the prior work. As far as I know, there exist more efficient algorithms (converges faster than O(1/t)) to solve the applications in the numerical experiment.\n\nAs a result, I tend to vote for rejection.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "u2ErS80klii", "reviewer": "Reviewer_MxNL", "summary": "This paper considers low-rank and nonsmooth optimization problems and proposes the extragradient method to solve it. ", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n\nThe extragradient method is proved to converge with rate $O(1/t)$ and low computational cost. \n\nWeakness:\n\n1. There seems no discussion on how restrictive the generalized strict complementarity condition (Assumption 1) in the paper. It would be much better if more explanations and intuitions about this condition are given.\n\n2.  It's said that an advantage of the extragradient method over previous standard methods is low per iteration computational cost. How faster is this method than others quantitatively?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical paper, and I think there is no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "EhdjUPDWCJ8", "reviewer": "Reviewer_xRc5", "summary": "This paper considers the problem of minimizing a non-smooth matrix function  $f(X)$ over the spectrahedron $S_n$, i.e., positive semidefinite matrices with trace equal to 1. Such optimization problems often arise as the convex relaxation of various low-rank matrix recovery problems. In general solving these problems with projected subgradient descent requires a projection onto the spectraherdon at every iteration, which is expensive because of the need to compute a full SVD at every step.\n\nUnder the assumption that the non-smooth objective function $f(X)$ can be written as the pointwise maximum of a family of smooth functions,  the authors reformulate the original optimization problem as a saddle point problem which can be solved via the projected extragradient method. The key contribution is that under a “generalized strict complementarity” condition and when close to the ground truth, the projection onto $S_n$ can be replaced by a low-rank projection. Therefore, the overall algorithm can be significantly more efficient, because only a low-rank SVD is needed.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1.\tPrior work by Garber 2019 [16,17] consider only smooth functions, which has relatively limited practical applications for machine learning. This paper expands the scope by considering nonsmooth functions and gives examples like robust PCA and sparse PCA, which are of interest for the ML community. \n2.\tGives an interesting counterexample where previous guarantee for projected gradient descent does indeed fail for projected subgradient descent. This justifies the use of the extragradient method proposed in this paper.\n3.\tThe saddle-point view has further applications in the context of two-player zero sum games, and other minimax type problems in ML.\n4.\tThis paper also establishes an interesting tradeoff between the rank of the SVD and the radius of the neighborhood around the ground truth in which the extragradient method converges.\n\nCons:\n1. The setting of this paper is fairly restrictive. The main result of this paper only applies to functions of the form $g(X) = h(X)+\\max_y y^T(\\mathcal{A}(x)-b)$, where $h(X)$ is a smooth convex function and $\\mathcal{A}$ is a linear map.\n\n2. The proof techniques seem incremental in view of the previous work of [16] and [17]. It is not clear how these techniques can be further extended to more general non-smooth functions.\n\n3. The authors do not investigate how a good initial point might be found that satisfy the assumptions of their theoretical results. Also it seems difficult to verify a priori whether the strict complementarity condition actually holds for a given problem, without already having solved it.\n\n4. Moreover, the numerical experiments in section 5 do not demonstrate the advantage of the extragradient method. They do not show the convergence rate of the method. It would be nice if we can see a more straightforward comparison between the convergence rates and computational costs of the extragradient method and projected subgradient descent.\n\nMinor comments:\n1. I suggest that the authors define the generalized strict complementarity condition and the standard complementarity condition more clearly in the introduction. Right now both terms are used in the introduction without a clear definition, which is a bit confusing. There are numerous places where strict complementarity is referred to, and it is not clear which one is being talked about.\n2. I also feel that section 2 needs a bit more motivation. It is not clear from this section why the strict complementarity condition is important and what Lemma 3 and 4 are used for.\n\n\n----- Update after rebuttal -----\nI have read the response of the authors. As before, my main concern is that the proposed algorithm does not have strong guarantees of success. Therefore I choose to keep my original score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Thank you for your submission to NeurIPS. Overall, all reviewers found the work interesting and valuable, but could not agree on whether it was ready for publication. This was a difficult decision -- while the paper provides an interesting theoretical analysis, the reviewers found the setting to be quite restrictive, and the exposition of the assumptions to be unclear. One reviewer who reviewed the proof in detail expressed some concern in the amount of overlap with prior work. The reviewers also noted that the experimental results did not build a strong case for the proposed algorithm. 
Decision: Accept (Poster)