Decentralized Matrix Sensing: Statistical Guarantees and Fast Convergence
Authors: Marie Maros
Gesualdo Scutari
Venue: NeurIPS 2023 poster (2023)
Keywords: Distributed non-convex optimization
Low-rank matrix recovery
TL;DR: We provide, for the first time, fast computational guarantees on distributed (non-covex) low-rank matrix recovery.

Abstract: We explore the matrix sensing problem from near-isotropic linear measurements, distributed across a network of agents modeled as an undirected graph, with no centralized node. We provide the first study of statistical, computational/communication guarantees for a decentralized gradient algorithm that solves the (nonconvex) Burer-Monteiro type decomposition associated to the low-rank matrix estimation. With small random initialization, the algorithm displays an approximate two-phase convergence: (i) a spectral phase that aligns the iterates' column space with the underlying low-rank matrix, mimicking centralized spectral initialization (not directly implementable over networks); and (ii) a local refinement phase that diverts the iterates from certain degenerate saddle points, while ensuring swift convergence to the underlying low-rank matrix. Central to our analysis is a novel "in-network" Restricted Isometry Property which accommodates for the decentralized nature of the optimization, revealing an intriguing interplay between sample complexity and network connectivity, topology, and communication complexity.

Decentralized Matrix Sensing: Statistical Guarantees and Fast Convergence
Marie Maros
Gesualdo Scutari
School of Industrial Engineering
School of Industrial Engineering
Purdue University mmaros@purdue.. edu
Purdue University Recutari@purdee edu
Abstract
We explore the matrix sensing problem from near-isotropic linear measurements, distributed across a network of agents modeled as an undirected graph, with no server. We provide the first study of statistical, computaional/coommiicttioo guarantees for a decentralized gradient algorithm that solves the (nonconvex) Burer-Monteiro type decomposition associated to the low-rank matrix estimation. With small random initialization, the algorithm displays an approximate two-phase convergence: (i) spectral phase that aligns the iterates' column space with the underlying low-rank matrix, mimicking centralized spectral initialization (not directly implementable over networks); and (ii) local refinement phase that diverts the iterates from certain degenerate saddle points, while ensuring swift convergence the underlying low-rank matrix. Central to our analysis a novel "in-net network" Restricted Isometry Property which accommodates for the decentralized nature of the optimization, revealing an intriguing interplay between sample complexity, network connectivity & topology, and communication complexity.
Introduction
Matrix sensing-the estimation of a low-rank matrix from set of linear measuremeent-finds applica-
tions in diverse fields such as image reconstruction (c.g., 48 ) object detection (c.g., [33 (2))
and array processing (e.g., (2I)), to name a few. It also serves benchmark for determining the statistical and computational guarantees achievable deep learning theory, since retains many of the key phenomena in deep learning while being simpler analyze. Despite significant progress in understanding the convergence and generalization properties of various solution methods for training such learning models, a majority of these advances focus data at a central location with vast computing resources- good tutorials on the topic include 7 4. This centralized approach, however, is increasingly unsuitable for modern applications due bottlenecks, inefficient communication, and power usage. Therefore, the development of statistical learning methods for massively decentralized networks without servers is timely and crucial.
centralized paradigm, aggregating
This paper tackles the matrix sensing problem from data distributed over networks. We contemplate network of agents modeled as undirected graph with no servers, where agents communicate with their immediate neighbors- objective is to estimate ground- truth matrix Z* R based N y1..... yn. equally split into n-sized, disjoint datasets D1, De...., Dm Each agent's 's signal model thus given by
architectures are also known as mesh networks. The collective
total observations
y; (A,,7*) 7*) trace(A, Z*), for D,
(1)
Here, A, ddxd with D,, the known symmetric measurement matrices agent 2" is assumed symmetric, positive semidefinite, and low-rank, i.e., r* rank (2*) << d.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

To minimize communication overhead and avoid the need for d x d matrix transmission, we employ the hurer-Monteiro-typp decomposition of the estimate Z of 2", that is, Z = UÜ with U E gax; and seek to minimize the squared loss F(U), defined as
min F(U) = dER
UU 10--(A, (A,
JED:
(0))
where fi(0) is the loss function of agent i. Ideally, the number r of columns of U should be set to r*. However, r* might not be known in advance. In this study, consider the so-called over-parumeterized regime where r2r".
The formulation 2 poses multiple challenges. Firstly, F is nonconvex, lacks global smoothness
(i.e., global Lipschitz continuity of VF), and is not entirely known to the agents. Secondly, the
over-parameterized regime may intuitively suggest a risk of overfitting. However, recent studies (e.g..
34 (0] ) have compellingly revealed that when centralized Gradient Descent (GD) is applied to 2 with small random initialization, it induces implicit bias towards simpler solutions with favorable
generalization properties. This bias-often referred to as the simplicity bias or the incremental learning behavior of GD(/Stochastic Gradient Descent)- assists in the exact approximate recovery of the ground truth n Interestingly. this phenomenon serves as a hidden mechanism in various other (deep) learning tasks that mitigates overfitting in highly over- wver-parameterized models (e.g.. [ 30 31). However, the direct implementation of GD in mesh networks is not feasible due to the lack of access to F by the agents or of server collecting agents' gradients fi--
The goal of this paper is to uncover the possible simplicity bias of a decentralized instance of GD, solving the matrix sensing problem 2 over mesh networks. To the best of our knowledge, this study is unique in the realm of decentralized optimization, establishing the first sample, convergence rate, and generalization guarantees of a decentralized gradient- gradient-based algorithm tailored for matrix sensing over mesh networks. We delve into the relevant existing literature in the subsequent section.
1.1 Related works
The literature offers numerous decentralized algorithms which could in principle be used to tackle the matrix sensing problem, directly or indirectly. However, the accompanying statistical and computational guarantees fall short, being either non-existent or inadequate, we elaborate next.
Off-the-shelf decentralized algorithms for nonconvex problems: The matrix sensing problem ( naturally invites the application of decentralized algorithms specifically designed for nonconvex losses in the form F- (1/m) Σ St (summation of agent functions). Noteworthy examples of such algorithms include (i) decentralizations of the GD that merge local gradient updates with (push-sum)
consensus algorithms 37 2 37,, (ii) decentralized first-order methods employing gradient tracking strategies R 32
and (iif) decentralized algorithms grounded on primal-dual decomposition or penalization of lifted reformulations incorporating explicitly consensus constraints [T5] 14 50).
However, despite their initial appeal, when applied to 2 these algorithms either lack of any convergence guarantee- the requirement that globally smooth 47 37
and has a (uniformly) bounded gradient 47 or they converge at sublinear rate to some critical points of F (which may not be the global minimizers), whose generalization properties remain unexplored and obscure [7..
42 is not met by the matrix sensing loss in
Ad-hoc decentralized algorithms for some matrix recovery problems: This line of works comprises decentralized schemes designed specifically for the structured matrix-related optimization problem under consideration. Relevant examples are briefly highligthed next.
(i) Dictionary learning & matrix factorization problems IS. 51 49]: In [5]. convergence of
decentralized gradient tracking method for certain dictionary learning problems is established; similar problem class is further investigated in [51]. where generalization properties of penalized consensus algorithm are studied, albeit without convergence rate analysis. Despite their differences. these studies share common premise of a full observation model, leading to a loss in the form of F(UVT)= = ||Y - UVTI² I2 Here, Y = 7 + N is the data matrix with N denoting noise. This full observation model contrasts with the matrix sensing model in 2 which is based on purtial (noiseless) measurements. Lastly, 3y proposes a distributed Frank- Wolfe algorithm to address a
low-rank matrix factorization problem, formulated as a trace (nuclear) norm convex minimization

---

problem (the nonconvex rank constraint is substituted by a nuclear norm constraint).
(ii) Distributed spectral methods 45 10
12
IC 44 43]: Spectral methods have been
established as effective strategies for obtaining reliable estimates of leading eigenvectors of a specified data matrix, as well as for providing a promising "warm start" for numerous iterative nonconvex
matrix factorization algorithms 4 7 Recent developments [9] 12 10 44 [ extended spectral achieving linear convergence rates, communications per iteration on the order of (dr)). and precise recovery up to a desired accuracy. A good tutorial on this subject can be found in [45] These methods, in principle, can tackle the decentralized matrix sensing problem formulated in this work through the estimation of the leading eigenspace of the surrogate matrix Y = >i= ΣjED, U) where EjED, Vj Ag is held by agent i. In fact, under suitable RIP on the linear mapping associated with Y, one has (1/N) E EEED, Uj R Z* A4 While such approach can yield valuable insights about the ground truth Z*, exact recovery of Z to arbitrary precision cannot be guaranteed [88. This limitation starkly contrasts with the robust guarantees attainable by the gradient algorithm applied to the centralized matrix sensing problem with small random initialization (e.g.,
have successfully principal component analysis-to to decentralized contexts,
perthoss-aariiclann
20
Generic saddle-sscaping decentralized algorithms: Under sufficiently small RIP constant of the linear mapping associated with the signal model ( the matrix sensing loss in 2 is shown to have no spurious local minima and all strict saddle points (1.2). Consequently, the task becomes escaping strict saddle points and computing second-order critical points. the distributed optimization context, recent works studied the escape properties of several decentralized algorithms. Early works showed that certain decentralized schemes the deterministic DGD
66 181, the subgradient- flow [36), gradient- tracking algorithms [6). and primal-dual based methods [6 24 with random initialization, converge asymptotically towards second-order critical point of a smooth function (subject to mild regularity conditions), with high probability. However, this near-certain convergence does not necessarily imply fast convergence. There exist non-pathological functions for which randomly initialized GD requires exponential time (in the ambient dimension) to escape saddle points [9. It remains uncertain whether the inherent structure of the matrix sensing problem could yield superior convergence guarantees. Subsequent research has investigated the impact of decaying, additive noise perturbation agents' gradients of (stochastic) DGD in the Adapt-then-Combee convergence approximately second-order stationary points is assured within a polynomial number of iterations, the prerequisite that the loss has globally Lipschitz gradient and Hessian matrix is not met by the matrix sensing loss in This leaves decentralized saddle-escaping methods bereft of convergence rate and generalization guarantees when applied to (2).
the (ATC) form [40 39 41 While
1.2 Major contributions
We establish the first convergence rate and generalization guarantees of decentralized gradient algorithm solving the matrix sensing problem via 2 over mesh networks. We borrow the following decentralized gradient descent 25
46 : for each agent i = 1, .......7. m,
0 Σ wey U
1 and 0,t1/2 Σ U.JUU a
Σ Wis
Here, U. is an estimate at iteration t of the optimization, common matrix Ū in 2 held by agent i; a E (0, 1] is the stepsize; and Wiy" 's are appropriately chosen nonnegative weights. We have Wh > 0, 10;=1. 1,.... 1........,. m, and Wsj > 0 agents and j. i j. can communicate; otherwise Wij 0. The algorithm employs two communication steps/iteration, aiming to enforce an agreement on both iterates U and local gradients Vf. One could reduce the communication steps to one per iteration via a suitable variable change, resulting in the DGD-ATC form 46). However, for the sake of clarity and ease of analysis, opt keep the form in without any loss of generality.
Guarantees: Our study presents thorough statistical and convergence analysis of (3). yielding the following key insights. (i) Convergence to low-rank solutions: We demonstrate that, regardless the degree of overparametrization r. the iterates generated by 3 from a small random initialization converge towards low-rank solutions. We also provide an estimate of the worst-case iteration complexity. Improving results of the GD centralized setting (e.g.. [4]), ), we specify an entire interval for algorithm termination, within which the generalization error is guaranteed to remain below the desired accuracy. This interval expands as the initialization becomes smaller. (ii) Two- phase convergence: Our analysis reveals two-phase convergence behavior of (3). The initial
3

---

"spectral" phase sees the iterates mimic a theoretical centralized power method with full data access, while the subsequent "refinement" phase steers the trajectory towards the ground truth solution. To the best of our knowledge, this provides the first evidence of a simplicity bias in a decentralized algorithm, aligning with the observed behavior of centralized GD 34 (iii) Generalization error and communication complexity: The generalization error is shown to scale polynomially with the initialization size while the communication complexity scales logarithmically. Consequently, one can achieve arbitrarily small estimation errors with only modest increase in communication and computation cost. (iv) RIP and network connectivity: Our findings hold under the conditions that the centralized measurement operator satisfies the standard RIP, and that network connectivity is sufficiently small. The former condition implies that our algorithm operates under the same sample complexity requested in the centralized setting. The latter is distinctive of the decentralized settings and shown to be unavoidable. (v) Almosl performance invariance with the network size: We demonstrate that with increase in the network size, the generalization error maintains its consisteney whereas the communication cost grows logarithmically. Thus, the algorithm ensures effective error control with marginal increase in communication overhead the network expands.
Convergence analysis: Although our analysis draws some insights from employed diverge from those used therein. The decentralized nature of our setting introduces additional error terms, thereby making the analysis substantially more complex. Our methodology hinges on newly introduced concept of RIP, termed in-network RIP. This concept harnesses the RIP of the measurement operator, much like the centralized GD, and intertwines it with the network's s connectivity to derive favorable attributes of the new, overarching network-wide measurement operator. Furthermore, it reveals the interplay between sample complexity, network connectivity & topology, and communication complexity towards achieving statistical and computational guarantees over networks. Although we have defined the in-network RIP in the context of our specific algorithm dynamics, we posit that possesses independent significance and could potentially pave the way for performance analysis of other distributed schemes.
R the proof techniques
2
Preliminaries
In this section, we first list the notations used in the paper, and then provide details of our theoretical setup and necessary preliminary results.
2.1 Notations
For any positive integer m, define [m] é {1...., mm; 1m is the m-dimensional vector of all ones; La is the d x identity matrix; @ denotes the Kronecker product; and ra) (resp. rank M)) denotes the range space (resp. rank) of the matrix M. When considering a matrix M E Rend med partitioned into blocks of size d x d, we will denote the block at the i-th row and j-th column as [M]a,. for i,j E [m]] Here, i and j indices increment by d, reflecting the size of the blocks.
We use ||-I| to denote the Euclidean norm. When applied to matrices, ||:|| is the operator norm induced by II- and ||= denotes the Frobenius norm of the argument matrix. We order the eigenvalues of any symmetric matrix M E R in nonincreasing fashion, i.e., X (M) 2 ... 2 >a(M). The singular values of (a rectangular) matrix M of rank r are denoted as 01 (M) 2 (2(M) 2 ... (M) > O.
Truncated SVD: For any given matrix M E Rd xd2, with rank r* > O, we write the truncated SVD M AM M where VM E Rdix" and Qi E RRdxx"" satisfy V Id, and QMQM Iدا. and A E RRr xr" is a diagonal matrix.
Augmented matrices: It is convenient to introduce the following "augmented" matrices suitable to rewrite the decentralized algorithm 5 in concise block form:
W: W 2 la: J= (1/m)mmm @ La-
where We Rmxm is the matrix of the gossip weights in B.. defined [W]e Wiy-
2.2 Basic definitions and assumptions
We develop our theoretical analysis under the following standard assumptions on the matrix sensing problem, algorithm parameters, and network connectivity.

---

On the matrix sensing problem: Given the signal model ① we decompose the ground matrix as - = X.X,, for some X E Rdxr' (recall, r" is the rank of 2*).
Definition 1 (condition number). We define the condition number of X Rdxx" as K. a.- (x)
||
We associate to the signal model (1) the measurement linear operator Rddd 3 2 + A(2) E RN and its adjoint I 3 w + A (w) E Rdxd defined as
A( 1 VN (AA,2) sE] (En, and A A')
Wi WzAj.
(5)
==1 JED.
A standard assumption in the matrix sensing literature is requiring the RIP for the operator A.
Definition (RIP). The measurement operator Á : Rdddd + E satisfies the (6, RRIP condition if
(1 6) < 11 < (1 + 1| for all matrices Z Bddd with rank(2) r.
(6)
The RIP condition is the key to ensure the ground truth 2 to be recoverable with partial observations. In fact, an important consequence of RIP is that A A'A((2) = (1/N) Σ =i=1 EjED, (Aj, Z) ~ Z, for all Z low-rank (see, e-g-. with distribution (00, 1) on the off-diagonal entries and distribution (N0, 1/v2) on the diagonal, the (6, RRPP holds with high probability, if the number of observations N = [ /52) (e.g., B.).
Notice that when all entries of the matrices A₁ are drawn i.i.d.
Network setup and gossip matrices: Agents are embedded in a communication network, modelled as an undirected graph g EV, where the vertices V = [ma] & (1..... m) correspond to the agents and & is the set of edges of the graph; (i, E & if and only if there is a communication link between agents and j. We study the decentralized algorithm (3) using gossip weight matrices satisfying the following standard assumption in the literature of distributed optimization.
Assumption 1. W = [w]s][}= satisfies: (i) Waj > 0, if (i,j) E E; otherwise Waj = 0: furthermore, Wis > for all i E [m]; (ii) W = W and W1 = 1 (stochastic): (iii) W is positive semidefinite; and (iv) there holds p A || 1m1m/m/l < 1.
Assumption D is standard in the literature of distributed algorithms and is satisfied by several weight matrices; see, c.g., [26] Note that p < 1 holds true by construction for connected graphs. Roughly speaking. P measures how fast the network mixes information; the smaller p. the faster the mixing.
2.3 Augmented mapping and in-network RIP
Fundamental to our analysis is a novel RIP-like property associated with an augmented linear mapping tied to the decentralized algorithm This new property effectively captures the admissible "degree of distortion" on the signal information Z+, taking into account both the partial observability of 7* as postulated in (1) (through the measurement operator A defined in (5) and the intricacies of the in-network optimization process (regulated by the network operator W. as defined in )
We begin rewriting the decentralized algorithm 3 in compact form. To do so, define the following quantities (i) the stacked block matrices Ut gmndrr and Z* E Rmnxmmd
U²= (U))) and Z == 1m I & 7*
(7)
respectively; (ii) the augmented mapping A [Rmdxmd - N and its adjoint A': RR gmmdomd
N
[A(Z)], A 1
Vmn (m (wvre)(bio) @ Ar, Z).
(g)
Σ
qe (murro) @ Ag, (8)
mm
E=1
where V(e): : , V returns the index such that E D,, E E [N]. Note that these operators depend on both data measures (via A) and the network (via W.. Using the definitions in and (8, is not difficult to check that G can be rewritten equivalently as:
U++ = (w2 + a AAA - -((0)))
(9)
5

---

For the convergence of 4 towards low-rank matrices with strong generalization properties, we anticipate certain conditions be imposed on the operator A. The algorithmic mapping structure in ( provides some insights in this regard. Since W = I (due to Assumption I (i)), the linear network operator w effectively functions as the identity map on matrices E Rdm edmxdm with
range(Z)) C range(T). This is in particular true for (d x d block) consensual matrices Z = -JZJ, including the (augmented) ground-truth Z*, as defined in 7. This implies that to accomplish precise reconstructions of Z", the operator A ought to exhibit some RIP-like regularity. Postponing to Sec. 3.T a more rigorous and comprehensive argument, we claim that the following property suffices.
Definition 3 (In-network RIP). The operator A Rmddmmd + RN defined in (8) satisfies the in-network (6, r) RIP property with tolerance A 2
0, if
(L - 8) (35) ZJ P A|IZ JZJIE S (1A(Z)
S (1 8) + A JZJ (10)
for any matrix Z E IR mdddd such that each of its d x d blocks [Z],, and its block-average 2
[ are of rank most
The condition 10 reads as "exact" RIP property of A along (block) consensual directions, allowing for some "perturbation" in the form of consensus errors Z| - -JZJJ 1 I The following result shows that the tolerance error can be controlled by the network connectivity P (see Assumption (emipttioo[i))) Iiv). Lemma 1. Suppose A satisfies the (82r,2r) -RIP and the gossip matrix W is chosen according to Assumption ! Then, the augmented operator A satisfies the in-network (282r.7)-RI) with tolerance
A = p² 4m + 202r) (1+ + 62r)
(11)
62r
Clearly, the smaller p. the smaller A, revealing an unexplored interplay between (potential) generaliza- tion properties and network characteristics. Since small p can be enforced also by employing multiple rounds of communications per iteration (see Sec. 3 for details), the communication complexity enters the tradeoff equation. Our theory in the next section will quantify this interplay, reveal- ing conditions and tuning recommendations to achieve fast convergence and strong generalization properties.
3 Main Results
We are ready to state the convergence results of Algorithm 3 Here we consider the overparametrized case 2r* while the other ranges of are discussed in the supplementary material.
Theorem 1. Consider the matrix sensing problem 4 with augmented ground-truth Z", under
r Z 2r", and the measurement operator A satisfying the (4(r" + +)) RIP, with 8 3 K "(r")- -1/2,
Let {U"), be the (augmented) sequence generated by Algorithm (. under the following tuning: (i)
the stepsize a Z x= -=|11 (ii) the gossip matrix W is chosen to satisfy Assumption / with
8²
p I
(12)
mo xxtp=
and (iil) the initialization U is chosen as U μU, where U E Rundxr has i.i.d. N(O, /m/r) distributed entries, and p. satisfies
-96x²
Vrm
Vr
1:2 2 min
n: "²
(13)
dv dvd
Then, after
+ + Or
r*
|X
is (X)
In x² \²//"/
+ In
max
1,
(14)
11
iterations, there holds
(U 1
21/16)
((--)))((()))))/))))
n 21/11
21/16
(15)
112*|
with probability at least 1 - o2r, where Ci, 02 O are universal constants.

---

Statistical guarantees: 15 demonstrates that, in the setting above, the iterates U U'")"" converge to an estimate of the low-rank solution Z" within a precision that can be made arbitrarily small by reducing the size js of the random initialization. The test error's dependence on f is polynomial,
whereas the worst-case convergence time only increases logarithmically with μ (see (4 ), indicating that significant test error reductions can be achieved with moderate increases in communication and
local computations. These guarantees are established under the RIP of the measurement operator A, and thus operate under the same sample complexity the centralized setting. For instance, for Gaussian measurement matrices, N i d(r")²x*. While the dependence on is optimal, the scaling on (r*)² and R is less favorable compared to convex approaches based on nuclear norm minimization
B However, decentralized methods solving such formulations directly (e.g.. (23)) would entail a communication cost of (dd²), which is significantly less favorable than the (rdd) of Algorithm S
On the number of iterations: Interestingly, the worst-case iteration complexity aligns with what observed for the GD in the centralized setting, following thus the same interpretation [4)) The first term in (14) represents the duration of the spectral alignment phase: beginning from a small initialization, the iterates U*(UT) progressively align with the r* leading eigenvectors of the mapping W + a /mmAAAA" A(Z*). Under the in-network RIP (Lemma I}. which requires the RIP of A and a sufficiently small p. we establish that this operator approximates the mapping of the power method applied to Z" (see the sketch of the proof in Sec. B.I. The remaining two terms in (14 represent the duration of the subsequent refinement phase. This phase steers the iterates away from certain degenerate saddle points while ensuring convergence towards the low-rank matrix Z*
In line with the findings for centralized GD 34 the test accuracy achieved at time i might not persist for larger iterations. The corollary below refines these results by establishing a nonempty time interval within which the estimation error is guaranteed to stay within the desired accuracy.
Corollary 1. Under the conditions of Theorem 7 it holds
T - 11
1/8
23 (r--r")//(r)) 1/8 1
1
21/11
x:
(16)
1
r
for any t E TT with
d
T T-
(1202 and o= (
(17)
where C3 > 0 is an universal constant.
The corollary ensures that the test error remains proportional to /// throughout the interval T f. Notably, the duration of this interval increases as μ approaches zero. This result is quite desirable, especially in distributed settings where coordinating termination at specific time may be challenging.
On the condition (2) on p and network scalability: The stipulation on P signifies the need of a well-connected network- the larger the network size m or the condition number k of the ground truth, the smaller p. This through the tolerance A, thus ensuring an adequate in-network RIP for the algorithm operator A. When coupled with the RIP of the measurement operator A, it suffices for a sufficient alignment of the iterates U (U*)T with the signal subspace from the early stages of the algorithm. Our numerical experiments (see Sec. 4 indeed demonstrate that maintaining such a constraint on p is indispensable for securing convergence and favorable estimation errors. When the network graph is predetermined (with given W), one can meet the condition (2) (if not a-priori satisfied) by employing at each agent's iss side multiple rounds of communications per gradient evaluation. This is common practice [27] that in our case results in a communication overhead that is only logarithmic in m and k.
non-negotiable condition essential for managing consensus errors
Notice that the generalization error (see 15) and 16 is independent of p or m. This demonstrates that the algorithm's 's performance scales favorably with m. As m increases, the generalization error remains unchanged, whereas the communication cost grows only modestly (logarithmically with m).
3.1 Sketch of the proof of Theorem
i
This section provides some insights on the proof of the theorem, highlighting the challenges and the differences with existing centralized and decentralized techniques.
7

---

The goal is to establish that ('(TT) 2 Zt as the algorithm progresses. Following G4 we decompose the iterates as
U' -'=''Q(Q"' (Q
(18)
Ssignal
nnoise
where Q' E R*x," contains the right singular vectors of U² ie., 12.0=V''A' and Qt-- E (r(rr-r") is the orthonormal complement of Q' By construction, span(Q") (a(("""sssaa(+)) IR", allowing for the decomposition (18) Further, notice that the noise term is orthogonal to the signal space, i.c. V= = O, which implies that once U* is projected onto the signal space, the only relevant term left is V Vzz U'Q(")))) hence the name "signal".
Based on 18 and under the assumptions of the theorem, we establish that: (i QQ)) is full rank and the signal-term grows as the algorithm progresses. (ii) The noise-term grows slower than the signal and remains sufficiently small. (ii) The error can be bounded by a polynomial proportional to the initialization size. Similar to 34], the analysis is organized in two phases.
Phase I (power-like method): The goal of this phase is to establish that after sufficiently long time t. since the initialization (f = 0), U
> cllU*~Q* ""= and and that (1(2).) ) Vor. Qu
is small, which means that the iterates are better aligned with the signal space than the noise space.
Therefore, we are to identify in y a mechanism that allows Venge to become aligned with Vz..
Given the initialization U = ,ll at iteration t = 1, we have
U (w2
ar m
A''AAA(A" A(21)) UO + Ar yoO.
(19)
m
Consequently, if is sufficiently small, for the first few iterations t, one can write
U²* (w2 + a =A'A(2))) U + +0 0~²
(20)
Under the assumption that A fulfills the 8, RIP, we can establish using the in-network RIP that if p S O W2 Z*W2, implying that W2 and 2 share the same eigenspace. Also, (,W2)) = 1, for all
AZ²) Z E, with ||||| < 0 | Further, by construction
mi mm/m 7/m
i ,,..,,,,,. d. Consequently Ae (w2 + a ) I+ + 11')))) for I,...,d. d. Therefore, we can further approximate (00) as
U²Z (W
0 + (
(1210
(21)
where we have disregarded for simplicity of exposition. Leveraging perturbation theory arguments, in the proof we demonstrate that E can be properly controlled. Using the above arguments, we have
V2. V2. = Vz (I+
a m
A2.)
VT. U + V2 ViJo (We)* Vz. (v+) Uo + O (1210%)100111)
(22)
VZ ~ V (W2) To 01
(23)
where the first term in the RHS of 22 corresponds to the power method the matrix ZT. Further, we see that the mentioned term grows faster than any other. Consequently, at the time t, at which we exit phase I, t is sufficiently aligned with the signal space as compared to the noise space.
this phase we establish that, given mmin (1-) 2 co (U--Q----11 and U Q'+)) grows and stabilizes away from zero (ii) the error |U='Q==- grows slower than the alignment || [U' and, (iii) the error || ||V Vu-qr remains sufficiently small. A careful study and balance of these quantities yield the final convergence.
Phase II (refinement):
IIV=)) T Vyr.qr. S Ci : (i) the alignment miin UV..U
Challenges with respect to the centralized case: The main challenge with respect to analyses of the GD (e.g., (34) comes from the distributed nature of the algorithm generating extra error terms (e.g., consensus errors), which significantly complicate the analysis. Our analysis builds newly introduced notion of RIP for the algorithm operator A. This is substantially different from the 3E] which lack of the network gossip matrix W2
classical RIP GD mapping
Challenges with respect to existing distributed optimization approaches: The standard approach in the distributed optimization literature typically takes the route of splitting the algorithm dynamics
8

---

in its average and consensus error. We deviated from such decomposition, because controlling such errors on (UT) would result in bounds of the type
JU' JI 5 (DIIU'(U)) 7*1))
(24)
which are insufficient to understand for example the dynamics of II(V))) Ve I|- Furthermore, the split into signal and noise subspaces allows us to invoke the in-network RIP with r", which would not be the case if splitting the iterates along consensus and non-consensus spaces.
Specifically regarding to phase of the scheme, another mode classical approach would be "centering" the dynamies around the centralized trajectory of the power method, i.e.,
U = (J+ a -JA A(Z)5)) U -12 =2= A" A'AUUU D m a ((") JA' m
(25)
m
+ (W2 - JTU +
(26)
which, using the in-network RIP and the fact that 2r² and t are sufficiently small, would yield
U² ~ J
a (J++AAAZZTT) U 120 (1111111"1) + O (p2110)))
(27)
Here, the degree of freedom control the error terms (second and third) are p and μ. This however would enforce the undesirable condition & S O(u), which couples the network connectivity with the size of the initialization.
4 Numerical experiments
We discuss some preliminary experiments validating our theoretical findings. All simulations performed on a Apple M2 Pro @ 3.5 GHz computer, using 32 GB RAM running macOS Ventura 13.3.1. We generate a random matrix X Rdxr", with d 50 and r* 2, which we use through all experiments. The symmetric measurement matrices are generated as A, (1/ + S,). where S, E Bdddd have i.i.d. standard Gaussian elements. The communication networks are generated as Erdös-Rényi graphs, with link activation probability p = 0.05. and different sizes m (specified in each experiment below). For any generated graph, we set W according to Metropolis weights [28]. and then let W W with the integer K chosen meet the condition (12) on p. resulting in K
communication rounds per agent/iteration. Finally, we choose a 1/4 and d
ii Validating Theorem I This experiment shows that under the conditions of Theorem I the test error behaves predictably y as that of the centralized GD (up to constant factors). Furthermore, the invariance of such an error with the network size m also confirmed, (as requested in ( In the experiments, the total sample size is N = 1000, split equally among agents m {5, 100, 500, 1000). Fig plots the normalized test error; Fig Ib shows || [[ ( VV which measures the missalignment of U with the power method matrix; and and Fig Ic displays the o,- (U*)/o,- (X) which combined with Fig [b us to claim that the signal U' is well aligned with Vz and full ranked. The curves show that the behavior of the decentralized algorithm close to that of the centralized GD (blue lines). As predicted, the error decays quickly after the correct subspace has been identified. Furthermore, convergence rate and generalization error are almost invariant to network-size scaling, as long as p S Om.-)).
long as p S O(1/m²)
(ii) Validating condition 12) on pt We showcase the necessity of decreasing p while increasing m. Given a connected base graph with associated W. for the sequence of graphs generated with increasing m = {10. 50, 100, 500}. we let W = WT, with T such that p ss 0.85, for all m. This eventually violates 122. Fig.2) (resp. Fig. 2b) plots the normalized generalization error versus the iterations, for m 1. m = 10 and m 50 (resp. m = 100 and m = 500, where the two curves are only up to the iterations scaling down with m increasing. In fact, both the rate and achievable estimation errors degrade (and eventually break down) as the network size increases while keeping p fixed. We claim that this the in-network RIP does
70 and 17, respectively). The figures demonstrate the necessity of
stems from the fact that if the network is not sufficiently not hold with sufficiently small tolerance, yielding to a failure of the power method early stage and consequently producing unrecoverable missalignment with the signal subspace.

---

2000
Beraioos
Derations
(a)
(b)
(c)
Figure I: Performance of Algorithm for different network size m, with = O(m
Centraizaal
Ieeration 1
Iterations
(a)
(b)
Figure 2: Performance of Algorithm for different network size m, and fixed p 0.85.
Acknowledgments and Disclosure of Funding
Funding in direct support of this work: ONR Grant # N00014-21-1-267.
References
[1] S. Bhojanapalli, B. Neyshabur, and N. Srebro. Global optimality of local search for low rank matrix recovery. In Adv. Neural Inf. Process. Syst., pages 3873-33 1373-3881, 2016.
[2] Bianchi and J. Jakubowicz. Convergence of multi-agent projected stochastic gradient algorithm for non-convex optimization. ICEE Trans. on Automatic Control, 58(2):391-445, Feb. 2013.
[3] Emmanuel J Candès and Yaniv Plan. Tight oracle inequalities for low-rank matrix recovery from minimal number of noisy random measurements. IEEE Transactions on information theory,
2011.
[4] Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing, 67(20):5239 2019.
[5] A. Daneshmand, Ying Sun, G. Scutari, F. Facchinei, and B. Sadler. Decentralized dictionary learning over time-varying digraphs. on Machine Learning Research, (139):1-62, 2019.
[6] Amir Daneshmand, Gesualdo Scutari, and Vyacheslav Kungurtsev. Second-order guarantees of distributed gradient algorithms. SIAM Journal Optimization, 30(4):3029-3068, 2020.
[7] M. A. Davenport and Romberg. An overview of low-rank matrix recovery from incomplete observations. IEEE Journal Selected Topics in Signal Processing, 10(4):608-66) 6622, 2016.
[8] Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization. IEEE Trans. on Signal and Information Processing over Networks, (22):20-1366 June 2016.
10

---

[9] Simon S Du, Chi Jin, Jason D Lee, Michael Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time escape saddle points. Advances in Neural Information Processing Systems, 30, 2017.
[10] Arpita Gang and Waheed U Bajwa. Fast-pea: A fast and exact algorithm for distributed principal component analysis. IEEE Transactions on Signal Processing, 70:6080-6095, 2022.
[11] Arpita Gang and Waheed U. Bajwa. A linearly convergent algorithm for distributed principal component analysis. Signal Processing, 193:108408, 2022.
[12] Arpita Gang, Bingqing Xiang, and Waheed U. Bajwa. Distributed principal subspace analysis for partitioned big data: Algorithms, analysis, and implementation. IEEE Transactions on Signal and Information Processing over Networks, 7:699-715, 2021.
[13] G. Gidel, F. Bach, and S. Lacoste-Julien. Implicit regularization of discrete gradient dynamics linear neural networks. In Advances Neural Information Processing Systems, volume 32, pages 3202-3211 1, 2019.
[14] D. Hajinezhad and M. Hong. Perturbed proximal primal-dual algorithm for nonconvex nons- mooth optimization. Math. Program., Ser. B, 176:207-245, 2019.
[15] M Hong, D. Hajinezhad, and M. Zhao, Prox-PDA: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks. In Proc. of the 34th International Conference on Machine Learning (ICML 2017), volume 70, pages 1529-1538, 2017.
[16] M. Hong, J. D. Lee, and M. Razaviyayn. Gradient primal-dual algorithm converges to second- order stationary solution for nonconvex distributed optimization over networks. In International Conference Machine Learning, pages
2018.
[17] M. Hong, Zeng, Zhang, and H. Sun. On the divergence of decentralized nonconvex optimization. SIAM Journal on Optimization, 32(4):2879-23)) 29099, 2022.
[18] Charikleia lakovidou and Ermin Wei. On the convergence of near-dgd for nonconvex optimiza- tion with second order guarantees. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 259-264, 2021.
[19] Yuchen Jiao and Yuantao Gu. Communication--ffiicenn decentralized subspace estimation. IEEE Journal of Selected Topics in Signal Processing, 16(3):516-531) 2022.
[20] Jikai Jin, Zhiyuan Li, Kaifeng Lyu, Simon Du, and Jason Lee. Understanding incremen- tal learning of gradient descent: A fine-grained analysis of matrix sensing. arXiv prepring, arXiv:2301. 15000 2023.
[21] D. S. Kalogerias and A. P. Petropulu. Matrix completion in colocated mimo radar: Recoverabil- ity, bounds and theoretical guarantees. IEEE Transactions Signal Processing, 62(2)3309-321, 2013.
[22] Q. Li, 7. Zhu, and G. Tang. The non-convex geometry of low-rank matrix optimization. Inf. Inferecee 8(1):51-96, 2019.
[23] Weijian Li, Xianlin Zeng, Yiguang Hong, and Haibo Ji. Distributed design for nuclear norm minimization of linear matrix equations with constraints. IEEE Transactions on Automatic Control, 66(2):745-752) 2020.
[24] Songtao Lu, Jason D. Lee, Meisam Razaviyayn, and Mingyi Hong. Linearized admm converges to second-order stationary points for non-convex problems. IEEE Transactions on Signal Processing, (9:4859-4874 2021.
[25] Marie Maros and Gesualdo Scutari. Dgd'2: A linearly convergent distributed algorithm for high-dimensional statistical recovery. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances Neural Information Processing Systems, volume 35, pages 3475-3487. Curran Associates, Inc., 2022.

---

[26] A. Nedić, A. Olshevsky, and M. G. Rabbat. Network topology and ceapmuuiiiatooncompppree tradeoff's in decentralized optimization. Proceedings of the IEEE, 106:953-9766 2018.
[27] Angelia Nedić, Alex Olshevsky, and Michael Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings the IEEE, 106(5):553-99) 2018.
[28] Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-2633, 2017.
[29] Y. Peng. Suo, Q. Dai, and W. Xu. Reweighted low-rank matrix recovery and its application in image restoration. IEEE Transactions Cybermetics, 44(12)24418-2333 2014.
[30] N. Razin, A. Maman, and N. Cohen. Implicit regularization in tensor factorization. In Interna- tional Conference on Machine Learning, pages 8913-8924, 2021.
[31] N. Razin, A. Maman, and N. Cohen. Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks. arXiv preprint. arXiv:2201.11729, 2022, 2022.
[32] G. Scutari and Y. Sun. Distributed nonconvex constrained optimization over time-varying digraphs. Mathematical Programming. 176:497-544, 2019.
[33] X. Shen and Y. Wu. A unified approach to salient object detection via low rank matrix recovery.
In IEEE Conference on Computer Vision and Puttern Recognition, pages 853-860, 2012.
[34] Dominik Stöger and Mahdi Soltanolkotabi. Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction. Advances in Neural Information Processing Systems, 34:23831-23843, 2021.
[35] Dominik Stöger and Mahdi Soltanolkotabi. Small random initialization is akin spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction, 2022.
[36] Brian Swenson, Ryan Murray, H. Vincent Poor, and Soummya Kar. Distributed gradient flow: Nonsmoothnesss nonconvexity, and saddle point evasion. IEEE Transactions on Automatic Control, (7(8):3949-3964 2022.
[37] Tatiana Tatarenko and Behrouz Touri. Non-convex distributed optimization. IEEE Trans. on Autom. Control, 62(8):377443777 -757,, 2017.
[38] Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank solutions of linear matrix equations via procrustes flow. In International Conference on Machine Learning, pages 964-973, PMLR. 2016.
[39] Stefan Vlaski and Ali Sayed. Distributed learning in non-convex environments- part Polynomial escape from saddle-points. IEEE Transactions on Signal Processing, 69: 19:1257-1270, 2021.
[40] Stefan Vlaski and Ali H. Sayed. Distributed learning in non-convex environments part i: Agreement linear rate. IEEE Transactions Signal Processing, 69: 19:1222-1256 2021.
[41] Stefan Vlaski and Ali H. Sayed. Second-order guarantees of stochastic gradient descent in nonconvex optimization. IEEE Transactions on Automatic Control, (7(12):6499-6500 2022.
[42] H.T. Wai, J. Lafond, A. Scaglione, and E. Moulines. Decentralized frank-wolfe algorithm for convex and non-convex problems. IEEE Transactions on Automatic Control, 62(1 1):5522-5537, 2017.
[43] Lei Wang and Xin Liu. Smoothing gradient tracking for decentralized optimization over the stiefel manifold with non-smooth regularizers. arXiv preprint arXiv:2303. / 2023.
[44] Xiaolu Wang, Yuchen Jiao, Hoi-To Wai, and Yuantao Gu. Incremental aggregated riemannian gradient method for distributed pea. In International Conference on Artificial Intelligence and Statistics, pages 7492-7510 10. PMLR, 2023.
12

---

[45] Sissi Xiaoxiao Wu, Hoi-To Wai, Lin Li, and Anna Scaglione. A review of distributed algorithms for principal component analysis. Proceedings of the IEEE, 106(8):1321-1340 2018.
[46] Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Decentlam: Decentralized momentum sgd for large-batch deep training. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 3029-3033 October 2021.
[47] J. Zeng and W. Yin. On nonconvex decentralized gradient descent. IEEE Transactions on Signal Processing, 66(1 1):2844-2848, June 2018.
[48] B. Zhao, J. P. Haldar, C. Brinegar, and Z.-P. Liang. Low rank matrix recovery for real-time cardiac mri. In 2010 IEEE International Symposium on Biomedical Imaging, pages 996-999, 2010.
[49] Wenjie Zheng, Aurélien Bellet, and Patrick Gallinari. A distributed foank-wolfe framework for learning low-rank matrices with the trace norm. Machine Learning. 107:1457-1475, 2018.
[50] M. Zhu and S. Mart'ine 'nez. An approximate dual subgradient algorithm for multi-agent non- 2013.
convex optimization. IEEE Transactions Automatic Control,
[51] Zhihui Zhu, Qiuwei Li, Xinshuo Yang, Gongguo Tang, and Michael B Wakin. Distributed low- rank matrix factorization with exact consensus. In H. Wallach, H. Larochelle, A. Beygelzimer, d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[52] W. Zou, K. Kpalma, Z. Liu, and J. Ronsin. Segmentation driven low-rank matrix recovery for saliency detection. In the 24th British machine vision conference (BMVC), pages 1-13, 2013.
13


Reviews:
[{"review_id": "80mfS1VckH", "reviewer": "Reviewer_qpo5", "summary": "This paper studies the problem of decentralized low-rank matrix sensing.  The paper presents novel theoretical results on the convergence and generalization of a standard decentralized learning algorithm. In particular, they provide convergence and generalization guarantees for  decentralized gradient descent algorithm over mesh networks without any central server. To do so, the authors define a new \"in-network\" RIP, which serves as an equivalent quantity to the standard RIP used to establish similar results in the fully centralized setting. This quantity is shown to capture both the network connectivity and the measurement operator characteristics. Using this quantity, they establish an upper bound on the number of communication iterations and the resulting estimation error. The paper also provides simulation results that demonstrate the recoverability of the ground truth matrices using the algorithm. ", "questions": "Please see the weaknesses section. ", "limitations": "N/A. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The paper is very well-written and is easy to follow despite being dense. \n\n2. The formulation of the in-network RIP is interesting and captures the complexity of the problem well. \n\n3. The paper makes solid technical contributions to an interesting problem. \n\n4. The interpretation of the theoretical results is much appreciated and helps the readability of the paper. ", "weaknesses": "1. The figures in the experimental section could be improved in terms of presentation. Particularly, please enlarge the figure font sizes.\n\n2. The authors could provide a refinement of equation 15 in terms of the sample complexity required to achieve epsilon relative error. The current error bound makes it hard to get a sense of how many measurements are required to get a desired error, when all other parameters are fixed. \n\n3. In lines 95-98, the authors mention that distributed spectral methods cannot guaranty exact recovery and seem to indicate that the current algorithm can. However, it is not clear from the theory or the experiments if exact recovery is possible in the noiseless case even when the required RIP properties are obeyed. Can the authors provide further clarification on this? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their insightful comments and the overall positive assessment of our work. We are happy the Reviewer liked it. We answer the Reviewer's concerns in order.\n\n-$\\textbf{1.}$  We will enlarge the font of the text in the figures and re scale them for visibility. We can change the color choices/grid choices to increase the figure visibility.\n\n-$\\textbf{2:}$  We agree that the result can be alternatively stated in terms of iterations towards an $\\varepsilon>0$ accuracy. We opted for the format of presentation of the convergence of the same type as in [34] to facilitate the comparison, showing that our distributed algorithm  achieves centralized statistical guarantees.  Addressing the Reviewer's question, an $\\varepsilon>0$ solution,   $$ \\frac{ \\||U^{\\hat{t}}(U^{\\hat{t}})^\\top-Z^{\\star}\\||_F}{\\||Z^{\\star}\\||}\\leq \\varepsilon,$$ is achieved by  choosing the size of the initialization $\\mu$ as\n\n$$\\mu^2 \\precsim \\min \\left\\\\{\\frac{\\varepsilon^2 r^2}{\\kappa^4 d^2 (r - r^{\\star})^2(r^{\\star})^{4/21}} \\\\|\\bar{X}\\\\|^2, \\frac{\\sqrt{rm}}{d \\sqrt{d}\\kappa^9} , \\frac{\\sqrt{r}}{d \\sqrt{d}}\\left(\\kappa^2 \\sqrt{\\frac{d}{r}} \\right)^{-96\\kappa^2} \\right\\\\} \\quad \\text{(A)}$$\n\nNotice that this result holds for **any** sample size  $N \\geq c_1 d (r^{\\star})\\kappa^8$, which is **independent** on $\\varepsilon$, This condition is required to guarantee the RIP condition (with   $\\delta \\precsim \\kappa^{-4}(r^{\\star})^{-1/2}$). \n\nTo summarize, the condition on the sample size $N$ does not depend on the precision of the estimates the algorithm can achieve, which   instead is controlled via the initialization size $\\mu$ (affecting thus the convergence rate). \n\n-$\\textbf{3: }$ Contrary to our algorithm that achieves arbitrarily small  $\\varepsilon>0$ precision, under the $\\delta$-RIP, for **any**   $\\delta \\precsim \\kappa^{-4}(r^{\\star})^{-1/2}$ (resulting in a **fixed**  $N \\geq C_1 d (r^{\\star})\\kappa^8$ for **any** $\\varepsilon>0$),  this is not the case if spectral methods are employed to solve the matrix sensing problem.  Such methods  would provably estimate  the eigenvalues and eigenvectors of the matrix $\\mathcal{J}\\mathcal{A}^*\\mathcal{A}(Z^{\\star})\\mathcal{J}$ with arbitrary precision, which however do not match the eigenvalues and eigenvectors  of $Z^{\\star}$ with arbitrarily precision, unless $\\delta$  becomes arbitrarily small (which cannot be for fixed $N$). More precisely, assuming the centralized mapping $\\bar{\\mathcal{A}}$ fulfills the $\\delta$-RIP, with fixed $\\delta\\neq 0$ (thus fixed, proper $N$), the estimate  $Y$ produced by such procedures  satisfies  [Chi, Lu, Chen 2019]\n$$\\\\|Y-\\bar{Z}^{\\star}\\\\| \\leq \t\\delta \\sqrt{r^{\\star}}\\\\|\\bar{Z}^{\\star}\\\\|.$$ Clearly, for a given  $\\delta\\neq 0$, the right hand side cannot be made arbitrarily small. As discussed in the comment 2 above, this is not the case for our algorithm.  \n\nPlease let us know if further clarification are needed. We will update the paper to point out the above aspects. "}, {"review_id": "9sWgxJ4muE", "reviewer": "Reviewer_1WwW", "summary": "This paper proposes a decentralized gradient algorithm for the matrix sensing problem via Burer-Monteiro type decomposition. A new concept of RIP termed in-network RIP is introduced for the proposed algorithm, which harnesses the RIP of the measurement operator and intertwines it with the network's connectivity. The paper demonstrates the effectiveness of the proposed algorithm by providing numerical simulations.", "questions": "Please explain the concept \"generalization error\". As far as I know, generalization error is a concept in machine learning that measures the performance of a trained model on new, unseen data. What does it mean in this paper?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper provides a new decentralized gradient algorithm that solves the low-rank matrix sensing problem via Burer-Monteiro type decomposition. The study covers various aspects of the algorithm, including statistical guarantees, communication complexity, and sample complexity.\n\n- The paper introduces a new concept of in-network RIP, which harnesses the RIP of the measurement operator and intertwines it with the network's connectivity to derive favorable attributes of the new, overarching network-wide measurement operator. This concept provides a new perspective on the analysis of decentralized matrix sensing.\n\n", "weaknesses": "- Lack of decentralized applications. The paper only provides some applications for centralized matrix sensing problems and presents the shortcomings of common centralized applications. It would be helpful to list some practical applications for decentralized matrix sensing problems to motivate the proposed algorithms.\n\n- The article is innovative but not too big. The algorithm is a simple combination of [25] and [45], but it's not straightforward to extend the analysis in [34] from the centralized case to the decentralized case. In-network RIP is proposed to close the gap.\n \n- The condition of $\\rho$ in (12) seems too strict. How many communication rounds per iteration are needed to satisfy (12)?  It would be helpful to present the number of communication rounds per iteration in numerical experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their insightful comments  and the overall positive assessment of our work. Our response to her/his comments/questions follows, starting from those listed under the `Weaknesses'. \n\n-$\\textbf{1.}$ Solving problems in a decentralized fashion is essential in situations in which high dimensionality data is gathered in multiple locations. In these situations gathering all data in a single machine can be prohibitive. However, with only partial access to the data the problem may not be solvable. A feasible approach in this circumstance is to opt for a master-client architecture (star topology with a server node connected to all the clients). However, this introduces a single point of failure and the server can easily become a communication bottleneck. Thus, in circumstances in which high-dimensional data is gathered in multiple/many locations, in terms of robustness and efficiency, decentralized computation over mesh networks is the preferred option, which has become a popular choice in several ML applications and computational architectures. Concrete matrix factorization/sensing applications in which high dimensional data is gathered in multiple locations naturally include the Netflix problem [Koren, Bell, Volinski 2019], for which schemes working on the master-client architecture have been proposed [Teflioudi, Makari, Gemulla, 2012] , and Seismic data interpolation [Aravkin, Kumar, Mansour, et. al. 2014].  Observe that in these applications data is both high dimensional and gathered in a decentralized fashion.\n\n\n\n-$\\textbf{2.}$ We agree with the Reviewer that the proposed scheme builds on [25]. However, it is important to remark that the algorithm [25]  has been designed to deal with **convex** problem. A direct application of the same approach here would have suggested the algorithm in [25] applied to a  **convex formulation** of the matrix sensing problem  over the network (e.g., minimizing the nuclear norm subject to  linear constraint, e.g.,  [3]). However, by doing so, the resulting distributed algorithm would have incurred in the unaffordable communication cost of  $\\mathcal{O}(d^2)$ elements per iteration. This motivates the application of a double-mixing based  decentralized algorithm to the distributed **non-convex** problem in the form  (2), for which there was no study in the literature. We refer the Reviewer to the reply to Reviewer XCka for  details also on the *technical* novelties of our convergence analysis. \n\nReferring to [45], the authors therein established that for unconstrained problems the algorithm in [25] and a variant of decentralized gradient descent are equivalent. Because the matrix sensing problem is indeed unconstrained, our proposed scheme can be cast into a variant of decentralized gradient descent (up to a change of variable), which we mentioned in our manuscript. However, since the analysis in [45] does not help to  establish  convergence guarantees in our setting, we believe that the aforementioned change of variable is not convenient for our purposed. \n\nMore generally, we believe that for the matrix sensing  problem proposed algorithm is most suitable among other distributed algorithms in the literature applicable to nonconvex problems. This is for two reasons, (i) contrary to the problems handled in [25] and [45] $\\bar{Z}^{\\star}$ is a solution to the global problem and to each individual problem, which removes the need of more involved updates, like incorporating correction mechanisms of the local gradients (such as gradient tracking mechanisms), even if arbitrarily close to 0 precision guarantees are requested; (ii) gradient tracking or other correction mechanisms would complicate the analysis further, and as argued, to no benefit. \n\n-$\\textbf{3.}$\nIn order to obtain the number of communication rounds required to satisfy (12) with a mixing matrix/graph with a given connectivity $\\bar{\\rho}$ we require $K$ communication rounds where $K$ is such that\n$$\n    \\bar{\\rho}^K \\leq C \\frac{\\delta}{m^6 \\kappa^4 r^{\\star}} \n$$\nwhich is fulfilled by setting for some universal constant $c_0 > 0$\n$$\n    K = \\left\\lceil \\frac{c_0 \\log\\left( m \\kappa r^{\\star}/\\delta \\right)}{1-\\bar{\\rho}} \\right\\rceil.\n$$\nObserve that the dependence on the number of communication rounds is logarithmic with respect to $m$ $\\kappa$ and $r^{\\star},$ and consequently, scales beneficially with quantities that are moderate in size and is independent of potentially large quantities such as $d.$\n\n$\\textbf{Questions:}$ We agree with the reviewer that the terminology 'generalization error' is typically used in the ML community to evaluate the performance of a trained model (typically trained on the empirical risk) $U^t$ in terms of the population risk value at $U^t$. We referred to the quantity in Theorem 1 as generalization error because when particularized to the data model discussed in lines 193-197 the quantity on the RHS of (15) corresponds to the population risk value for the distributed problem. \n\nWe understand that this terminology can be misleading and we will change it in the final version of the paper. \n\nPlease let us know if further clarifications are needed. \n"}, {"review_id": "NorVXUdNzx", "reviewer": "Reviewer_XCka", "summary": "In this work, the authors proved the convergence of the distributed GD method on the over-parameterized matrix sensing problem. The convergence is based on the proposed in-network RIP condition. Numerical experiments are conducted to verify the theoretical findings.", "questions": "(1) Equation (1): I think it should be trace(A_j * Z^*) instead of trace(A_j, Z^*) in the right term.\n\n(2) Line 124: I think w_{ij} > 0 if and only if i and j can communicate?\n\n(3) \n\n(3) Theorem 1 and Remark on Line 333: it would be better if the authors could elaborate on the technical difficulty in proving the theorem, besides introducing the in-network RIP condition and modifying the proofs in [34].\n\n(4) Corollary 1: the denominator in the left-hand side should be \\|Z^*\\| instead of \\|Z^*\\|^2?\n\n(5) Line 355: A_i = (1/2) (S_i + S_i^T).", "limitations": "Please see my questions in the previous section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and easy to follow. In my opinion, the results are novel and should be interesting to audiences in optimization and machine learning fields. ", "weaknesses": "Although I believe that the paper is theoretically sound, I feel that the proof techniques are mostly the same as [34], except the concept of in-network RIP condition. This may weaken the theoretical contribution of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We acknowledge the query about the novelty of our convergence analysis relative to [34], providing an opportunity to highlight the unique features of our approach. While both methods share a two-phase structure, our proof contains technical details that substantially diverge from [34], a distinction recognized by the other Reviewers and elaborated below.\n- **Different algorithms and consequences**:  [34] employs the standard gradient algorithm, \n$$ \\bar{U}^{t+1} = \\Big(I + \\alpha \\bar{\\mathcal{A}}^*\\bar{\\mathcal{A}}(\\bar{Z}^* - \\bar{U}^t(\\bar U^t)^{\\top})\\Big)\\bar{U}^t, \\qquad (1)$$\nwhile the proposed scheme performs a *double* mixing update that intermingles iterates and local gradients:\n$$U^{t+1} = \\Big(\\mathcal{W}^2 + \\frac{\\alpha}{m}\\mathcal{A}^*\\mathcal{A}(Z^{\\star} - U^t(U^t)\\Big)U^t.\t\\qquad (2)$$\nThe difference in the updates (despite the lifting of variables), in particular the dissimilarity of the maps  $\\mathcal{A}$ and $\\bar{\\mathcal{A}}$,  has the following consequences on the analysis \n\n    -(i) *Lack of RIP*:  The proofs in [34] heavily rely on the RIP of $\\bar{\\mathcal{A}}$.   **Notably,  $\\mathcal{A}$  does not in general fulfill the RIP**, except under an undesirable stringent condition on the agents' local sample size, which would break the *centralized* sample complexity achievable by our scheme following our analysis. This difference renders some steps of the proofs in [34] inapplicable to our algorithm and complicate the translation of analyses between the centralized and distributed contexts. \n\n    -(ii) *Which power-like  method in Phase I for (2)?*  Using the RIP of $\\bar{\\mathcal{A}}$, Phase I in [34] demonstrates that,  for small $t$,  $\\bar{U}^{t+1}$ in (1) remains sufficiently close to the power method iterate $\\bar{\\mathcal{M}}^t U^0$, (i.e.,  $\\||\\bar{U}^{t+1}-\\bar{\\mathcal{M}}^t U^0\\||=\\mathcal O(\\mu^3)$), which can be proved to be  'well-aligned' to the ground truth $\\bar{Z}^\\star$, where  $$\\bar{\\mathcal{M}}:={I} + \\alpha \\bar{\\mathcal{A}}^*\\bar{\\mathcal{A}}(\\bar{Z}^{\\star}) \\qquad (3)$$ and $\\mu$ is the size of the initialization.   \n\n    While the choice of  $\\bar{\\mathcal{M}}$ is straightforward for the gradient algorithm (1),  **the counterpart of  $\\bar{\\mathcal{M}}$ for the iterates (2)** (denoted hereafter by $\\mathcal M$) **remains unclear**. An observation under the RIP of $\\bar{\\mathcal{A}}^*\\bar{\\mathcal{A}}(\\bar{Z}^{\\star})$ is that $\\mathcal{J}\\mathcal{A}^*\\mathcal{A}(Z^{\\star})\\mathcal{J}$ fulfills the RIP as well. Consequently,  a potential choice of   $\\mathcal M$  in line  with (3) that allows us to closely emulate the proof in [34] could be   $$\\mathcal M=\\mathcal{J} + \\frac{\\alpha}{m}\\mathcal{J}\\mathcal{A}^*\\mathcal{A}(Z^{\\star})\\mathcal{J} \\quad \\text{or}\\quad \\mathcal M=\\mathcal{W}^2 + \\frac{\\alpha}{m}\\mathcal{J}\\mathcal{A}^*\\mathcal{A}(Z^{\\star})\\mathcal{J}, \\quad (4) $$ enabling reliance on the RIP of the mappings appearing in such  $\\mathcal M$'s. \n\n    Following the steps of [34] with either of these choices leads to an unsatisfactory outcome: the discrepancy of the trajectories,  $\\||{U}^{t+1}-{\\mathcal{M}}^t U^0\\||$, becomes uncontrollable by the initialization size $\\mu$ only (as instead in [34]), due to the network dependency of the mapping  $\\mathcal{A}$. This breaks the condition in [34] to exit Phase I.   \n\n    Therefore,  if one aims to avoid imposing a local RIP (thus a local sample size) condition, the proofs of [34] are not directly applicable. To circumvent this challenge, our key innovation lies in identifying the 'right' mapping $\\mathcal M$,  expressed as $$\\mathcal M=\\mathcal{W}^2 + \\frac{\\alpha}{m}\\mathcal{A}^*\\mathcal{A}(Z^{\\star}),\\qquad (5)$$ which in conjunction with the *new concept*  of in-network RIP,  enables us to demonstrate that   $\\||{U}^{t+1}-{\\mathcal{M}}^t U^0\\||$ is controllable solely by the initialization size  $\\mu$    without necessitating the RIP of $\\mathcal{A}^*\\mathcal{A}(Z^{\\star})$ in $\\mathcal M$ (thereby avoiding constraints on the local sample size). In essence, the new RIP serves as the linchpin to manage the distortion that the mapping  $\\mathcal M$ in (5) induces on  the eigenvectors and eigenvalues of $Z^\\star$ via a condition on the network connectivity $\\rho$ while  maintaining a decoupling from the size $\\mu$ of the initialization. This subtle yet powerful modification illuminates a path forward, distinct from  [34], that captures the  decentralized nature of the algorithm.\n\n    -(iii) *Phase II: handling  extra error terms:* The aforementioned difference of the mappings,  along with the distributed nature of our algorithm, introduce additional complexity into the analysis of Phase II, due to extra error terms (such as those stemming from consensus errors) that are absent in [34]. These error components necessitate careful control and management, adding an additional layer of intricacy to our analysis\n- **In-network RIP**:We feel  that the new concept of in-network RIP holds more than mere technical significance; it represents an essential bridge between centralized and distributed worlds. It provides a tool for analyzing decentralized algorithms under *centralized* sample complexity, marking a considerable departure from [34]. Far from a minor contribution, it may pave the way for broader applications and insights in distributed computation\n- **On the final stage of convergence:** Our new analysis offers convergence assurances within a specific time **window** post a defined point in time. This is an enhancement over [34], whose proofs only ensure convergence at a particular instance and not all subsequent iterations. This expansion of the convergence window (consequence of our proof)  is sensitive in distributed settings, where synchronizing termination at a singular moment is not easily enforceable.\n \t \nPlease let us know if our assessment of the technical novelty is satisfactory. Happy to provide more details\n\nWe will also fix the typos raised in your questions. Thanks"}]

Author rebuttal:
We thank the Reviewers for their careful reading and insightful comments. We are glad that there is a consensus that the paper is well written and contains novel results that are of interest   to audiences in optimization and machine learning. Our reply to their specific questions and key comments follow.  In our replies we use the same notation as in the paper. 


Meta-review: This paper offers a first analysis for solving low-rank matrix sensing in a decentralized network, providing a comprehensive statistical, computational and communication complexity analysis. In particular, it bypasses several challenges, including but not limited to how to characterize the algorithm dynamics from small random initializations.
Decision: Accept (poster)