Implicit Regularization in Matrix Sensing via Mirror Descent
Year: 2021

Abstract:
We study discrete-time mirror descent applied to the unregularized empirical risk in matrix sensing. In both the general case of rectangular matrices and the particular case of positive semidefinite matrices, a simple potential-based analysis in terms of the Bregman divergence allows us to establish convergence of mirror descent—with different choices of the mirror maps—to a matrix that, among all global minimizers of the empirical risk, minimizes a quantity explicitly related to the nuclear norm, the Frobenius norm, and the von Neumann entropy. In both cases, this characterization implies that mirror descent, a first-order algorithm minimizing the unregularized empirical risk, recovers low-rank matrices under the same set of assumptions that are sufficient to guarantee recovery for nuclear-norm minimization. When the sensing matrices are symmetric and commute, we show that gradient descent with full-rank factorized parametrization is a first-order approximation to mirror descent, in which case we obtain an explicit characterization of the implicit bias of gradient flow as a by-product.

heading: 1 Introduction
text: Matrix sensing represents a paradigm in modern statistics [8, 26, 27], with applications ranging from image compression [2] to collaborative filtering [18] and dimensionality reduction [34], for instance. The goal is to recover a rank-r matrix X? ∈ Rn×n′ from a set of linear measurements yi = 〈Ai,X?〉, i = 1, . . . ,m, where the sensing matrices Ai ∈ Rn×n ′ are observed. This formulation includes the problem of matrix completion, where a subset of the entries of the matrix X? is observed.
Most of the literature on matrix sensing is based on some form of explicit regularization or rank constraint to encourage or enforce low-rankness of the estimated matrix. A popular approach is based on minimizing the nuclear norm or on using explicit regularization techniques based on the nuclear norm, e.g. [5, 15, 17, 23, 26, 27, 30]. Another popular approach is based on non-convex optimization and the low-rank factorization X = UV> with matrices U ∈ Rn×r, V ∈ Rn′×r, where the factorization itself enforces the low-rankness of X, e.g. [7, 8, 16, 21, 22, 29, 31, 39].
The literature on implicit regularization for matrix sensing is more recent and less well developed. When X? is assumed to be a positive semidefinite matrix, it was first empirically observed in [14] that mininizing the unregularized empirical risk using vanilla gradient descent with parametrization X = UU> and random full-rank initialization close to zero yields a low nuclear norm solution, even when U ∈ Rn×n, i.e. when no constraint on the rank of X is enforced. It was later proved that, with this parametrization, gradient descent minimizes the nuclear norm under the assumption that the sensing matrices Ai’s commute [14], or when the sensing matrices satisfy a restricted isometry property [19]. Gradient descent with low-rank initialization within a specific “capture neighborhood” has been studied in [9], which ensures that the iterates of the algorithm stay low-rank. When X? is a general rectangular matrix, implicit regularization in matrix sensing has been studied through
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
the lenses of deep matrix factorization in [3, 12, 20, 25], and empirical and theoretical evidence is provided which suggests that a notion of rank-minimization is involved in the implicit bias of gradient descent. However, these works do not establish an explicit characterization of the limiting point of the optimization algorithm, e.g. in the form of a quantity that is minimized among all minimizers of the empirical risk. In the special case of full-observation matrix sensing, gradient flow has been shown to learn solutions with gradually increasing rank [11].
Most theoretical results on implicit regularization in matrix sensing consider the continuous-time dynamics (i.e. gradient flow), e.g. [3, 9, 12, 14, 20, 25], or assume an infinitesimally small initialization, e.g. [14, 20]. Notable exceptions are [11], which makes a commutativity assumption on the data matrices in discrete time, and [19], which assumes a restricted isometry property that leads to a suboptimal sample complexity when the sensing matrices belong to a general class of random matrices [27]. In the context of linear neural networks, the dependence of the implicit bias of gradient descent on the initialization has been studied in [4, 24, 35, 38]. For instance, linear diagonal networks with shared weights were considered in [35], where it was shown that gradient descent minimizes a quantity which corresponds to the `1-norm in the limit α → 0 and to the (weighted) `2-norm in the limit α→∞, where α denotes the initialization size. This result was later generalized in [38] using a tensor formulation, which allows for architectures including linear diagonal networks and linear full-length convolutional networks. However, these results focus on vector-based notions of norm-like functions that do not capture matrix-based quantities typically of interest in matrix sensing.

heading: 1.1 Our contributions
text: We study the implicit bias of discrete-time mirror descent in matrix sensing in both the general case of rectangular matrices and the particular case of positive semidefinite matrices. Under the only assumption on the sensing matrices Ai’s that there exists a matrix achieving zero training error, we characterize the limiting point as the matrix that minimizes a quantity which interpolates between the nuclear norm and Frobenius norm, parametrized by the mirror map parameter, in the rectangular case; and which is a linear combination of the nuclear norm and the negative von Neumann entropy, parametrized by the initialization size, in the positive semidefinite case. Compared to results on implicit regularization for gradient descent, our framework for mirror descent is simple, and the same analysis yields results for both the case of general rectangular and positive semidefinite matrices.
In the general case of rectangular matrices, we show that mirror descent, initialized at zero and equipped with the spectral hypentropy mirror map [10] parametrized by β > 0, among all global minimizers of the empirical risk, converges to a matrix that minimizes a quantity interpolating between the nuclear norm in the limit β → 0 and the Frobenius norm in the limit β → ∞. As a consequence, our result implies that, for β → 0, mirror descent can recover a rank-r matrix X? under the same set of assumptions that is sufficient for nuclear norm minimization to be successful, namely when the sensing matrices Ai’s satisfy the restricted isometry property with restricted isometry constant smaller than some absolute constant [27], or if X? satisfies an incoherence condition and r(n + n′) (modulo constants and logarithmic term) random entries of X? are observed [26]. To the best of our knowledge, this is the first recovery guarantee for an implicit regularization-based algorithm that does not explicitly enforce low-rankness in general rectangular matrix sensing.
In the particular case of positive semidefinite matrices, we can alternatively consider the spectral entropy mirror map and show that mirror descent, initialized at αI for any α > 0, converges to a positive semidefinite matrix that minimizes a linear combination of the nuclear norm and the negative von Neumann entropy, where the relative weights are controlled by the initialization size α. While the limit α→ 0 corresponds to minimizing the nuclear norm as in the case of rectangular matrices, the limit α → ∞ corresponds to maximizing the nuclear norm. This also translates into guaranteed recovery of a low-rank matrix X? for α → 0 under the same assumptions that are sufficient for nuclear norm minimization [26, 27]. A comparable result for gradient descent with full-rank factorized parametrization has been established in [19] under a stronger assumption on the restricted isometry constant, which is assumed to be smaller than a quantity depending on both the rank and the condition number of the matrix X? and translates into a sub-optimal sample complexity.
We establish our results using a potential-based analysis for mirror descent in terms of the Bregman divergence, which provides an alternative proof technique to characterize the limiting point of mirror descent compared to the analysis based on KKT optimality conditions used in [13]. As a by-product, our proof of Theorem 1 yields an alternative proof of Theorem 1 in [13]. The advantage of our
approach is that convergence of mirror descent does not need to be assumed a-priori and can instead be established using convexity of the empirical risk. The analysis in terms of the Bregman divergence is not limited to convex settings and has been applied to non-convex problems, e.g. [36, 37, 40], and hence can be of more general interest to investigate the phenomenon of implicit bias.
In the case of square matrices, we show, assuming that the sensing matrices Ai’s are symmetric and commute, that gradient descent with full-rank parametrization X = UU> −VV>, U,V ∈ Rn×n, is a first-order approximation to mirror descent equipped with the spectral hypentropy, where the initialization size corresponds to the mirror map parameter β. A similar connection between mirror descent and reparametrized gradient descent has been established in the vector-case [1, 10, 33, 36]. Similarly, we show that gradient descent with full-rank parametrization X = UU>, U ∈ Rn×n, is a first-order approximation to mirror descent equipped with the spectral entropy when the sensing matrices are symmetric and commute, thus recovering a generalization of Theorem 1 in [14] which holds for any positive initialization size α > 0 (rather than in the limit α→ 0). We present numerical simulations which suggest that, in some regimes, our results on the dependence on the initialization size α for mirror descent might be indicative for the behavior of gradient descent, even when the sensing matrices Ai’s do not commute. More precisely, the final estimates of gradient descent and mirror descent closely track each other when the number of measurements is sufficiently large for nuclear norm minimization to recover a planted low-rank matrix, while gradient descent seems to put more emphasis on lowering the effective rank [28] at the expense of a higher nuclear norm when fewer measurements are available, which supports the empirical observations in [3, 20].

heading: 2 Background
text: We begin by introducing some notation used throughout this paper. We use boldface uppercase letters to denote matrices and boldface lowercase letters to denote vectors. We write ‖ · ‖∗, ‖ · ‖F and ‖ · ‖2 for the nuclear, Frobenius and spectral norm, respectively, and denote by 〈X,Y〉 = tr(X>Y) the standard Frobenius inner product. We write Sn,Sn+ ⊆ Rn×n for the set of symmetric and positive semidefinite matrices, respectively. Without loss of generality, we will always assume n ≤ n′. We first give a brief overview of unconstrained mirror descent (with matrix arguments).
Let D ⊆ Rn×n′ be an open convex set. We say that Φ : D → R is a mirror map if it is strictly convex, differentiable, and its gradient takes all possible values, i.e. {∇Φ(X) : X ∈ D} = Rn×n′ . Given a mirror map Φ, the associated Bregman divergence is defined as
DΦ(X,Y) = Φ(X)− Φ(Y)− 〈∇Φ(Y),X−Y〉. (1) Then, the mirror descent algorithm to minimize a function f : D → R is defined by the update
∇Φ(Xt+1) = ∇Φ(Xt)− ηt∇f(Xt), (2) where ηt > 0 is a sequence of step sizes. We approach the problem of matrix sensing, where we are given measurements {Ai, yi}mi=1, by minimizing the unregularized empirical risk
f(X) = 1
2m m∑ i=1 ( 〈Ai,X〉 − yi )2 (3)
using mirror descent equipped with the spectral hypentropy mirror map, which is defined as [10]
Φβ(X) = n∑ i=1 σi arcsinh ( σi β ) − √ σ2i + β 2, (4)
for some β > 0, where {σi}ni=1 denote the singular values of X. We provide expressions for the gradient∇Φβ and discuss the per-iteration computational cost of the corresponding mirror descent algorithm in Appendix A.
If the optimization is restricted to positive semidefinite matrices X ∈ Rn×n, we can replace Rn×n′ with Sn in above definitions and consider the spectral entropy (using the convention 0 log 0 = 0) Φ(X) = tr(X log X−X), (5)
which is well-defined on the set of positive semidefinite matrices Sn+.

heading: 3 Algorithmic regularization of mirror descent
text: In this section, we show that mirror descent, equipped with the spectral hypentropy mirror map (4) in the rectangular case and the spectral entropy mirror map (5) in the positive semidefinite case, converges to a global minimizer of the empirical risk f that minimizes a quantity which interpolates between the nuclear norm and the Frobenius norm in the rectangular case, and is a linear combination of the nuclear norm and the negative von Neumann entropy tr(X log X) = ∑n i=1 λi log λi in the positive semidefinite case, where {λi}ni=1 denote the eigenvalues of the matrix X ∈ Sn+. The following Theorem applies to matrix sensing in the case of general rectangular matrices.
Theorem 1 (Rectangular case). Consider the mirror descent algorithm (2) with mirror map (4) with parameter β > 0 and initialization X0 = 0. Suppose that the step sizes satisfy ηt ≡ η ≤ c, where c > 0 is a constant depending on the sensing matrices Ai’s, observations yi’s and parameter β, and that there exists a matrix X′ satisfying f(X′) = 0. Then, mirror descent converges to a matrix X∞ = limt→∞Xt which, among all global minimizers of f , minimizes
n∑ i=1 σi log 1 β + σi log ( σi + √ σ2i + β 2 ) − √ σ2i + β 2, (6)
where {σi}ni=1 denote the singular values of X∞. We have, for any t ≥ 0,
f(Xt) ≤ DΦβ (X∞,X0)
ηt . (7)
Proof sketch. The following identity is key to our proof and characterizes how the Bregman divergence between any reference point X′ and the mirror descent iterates Xt evolves:
DΦβ (X ′,Xt+1)−DΦβ (X′,Xt) = −η〈∇f(Xt),Xt −X′〉+DΦβ (Xt,Xt+1), (8)
which follows from the definition of the Bregman divergence (1) and the mirror descent update (2). Letting X′ be any global minimizer of f , we can compute 〈∇f(Xt),Xt −X′〉 = 2f(Xt), where we used the assumption that there exists a matrix X′ achieving zero training error f(X′) = 0. Using the strong convexity of the spectral hypentropy mirror map, we can bound DΦ(Xt,Xt+1) to show
DΦβ (X ′,Xt+1)−DΦβ (X′,Xt) ≤ −ηf(Xt),
for any global minimizer X′ of f . Since the Bregman divergence DΦβ (X ′,Xt) is bounded from below by zero, this means that the empirical risk f(Xt) must converge to zero, which in turn implies that Xt converges to a global minimizer of f .
To see which global minimizer mirror descent converges to, observe that the difference in (8) does not depend on the reference point X′, as long as X′ is a global minimizer of f . This means that the Bregman divergence DΦβ (X
′,Xt) is decreased by the same amount for all global minimizers X′, which then implies that Xt must converge to the global minimizer which is closest to X0 in terms of the Bregman divergence. From this observation it follows that X∞ = limt→∞Xt minimizes the quantity in (6) among all global minimizers of f .
The bound (7) on the empirical risk of the last iterate f(Xt) can be shown using the smoothness of the empirical risk f and the strong convexity of the spectral hypentropy mirror map. A detailed proof of Theorem 1 can be found in Appendix B.1.
We remark that the step size η can be chosen independently from the parameter β if β is chosen from some interval bounded away from infinity, e.g. β ∈ (0, 1). An analogous result holds for mirror descent equipped with the spectral entropy mirror map (5) when optimizing over positive semidefinite matrices.
Theorem 2 (Positive semidefinite case). Consider the mirror descent algorithm (2) with mirror map (5) and initialization X0 = αI for some α > 0. Suppose that the step sizes satisfy ηt ≡ η ≤ c, where c > 0 is a constant depending on the sensing matrices Ai’s and observations yi’s, and that there
exists a positive semidefinite matrix X′ satisfying f(X′) = 0. Then, mirror descent converges to a positive semidefinite matrix X∞ = limt→∞Xt which, among all global minimizers of f , minimizes
n∑ i=1 ( log 1 α − 1 ) λi + λi log λi, (9)
where {λi}ni=1 denote the eigenvalues of X∞. We have, for any t ≥ 0,
f(Xt) ≤ DΦ(X∞,X0)
ηt . (10)
Theorem 2 can be proved the same way as Theorem 1, see Appendix B.2. Neither Theorem requires any assumptions on the sensing matrices Ai’s beyond the existence of a matrix X′ achieving zero training error f(X′) = 0, which, for instance, is satisfied when {Ai}mi=1 are linearly independent and m ≤ nn′ in the rectangular case or m ≤ n(n+ 1)/2 in the positive semidefinite case. On the implicit bias of mirror descent. The implicit bias of mirror descent in linear models has previously been studied using KKT optimality conditions in [13]. Once we have established convergence of mirror descent towards a global minimizer of f , we could have alternatively invoked Theorem 1 of [13] to characterize the limiting point of mirror descent. Instead, our analysis of the Bregman divergence DΦβ (X
′,Xt) reveals that each iteration of the mirror descent algorithm (2) decreases DΦβ (X ′,Xt) by the same amount for all global minmimizers X′ of f , provided that
〈∇f(Xt),Xt −X′〉 = 〈∇f(Xt),Xt −X′′〉
for any two global minimizers X′ and X′′ of f . From this observation it immediately follows that mirror descent converges to the global minimizer of f that minimizes the quantity DΦβ (X
′,X0) among all global minimizers of f . Since this equality is satisfied under the assumptions of Theorem 1 in [13], our analysis presents an alternative proof technique for Theorem 1 in [13] that does not use KKT optimality conditions and hence does not need to assume convergence of mirror descent.
On the mirror map parameter and initialization size. In the rectangular case, minimizing the quantity in (6) is equivalent to minimizing the nuclear norm in the limit β → 0, and equivalent to minimizing the Frobenius norm in the limit β →∞, see Appendix B.6 for further details. This can be seen as a matrix analogue of the result in [35], which shows for linear diagonal networks with shared weights that gradient descent minimizes a quantity interpolating between the `1 and (weighted) `2 norms. For a network with two layers, this architecture corresponds to the parametrization x = u u− v v, where denotes the elementwise Hadamard product and with which gradient descent has been shown to be a first-order approximation to mirror descent equipped with the hypentropy mirror map in the vector-case, see e.g. [33, 36]. In the positive semidefinite case, minimizing the quantity in (9) also corresponds to minimizing the nuclear norm in the limit α→ 0, while in the limit α→∞ the coefficient log(1/α)− 1 tends to minus infinity, and minimizing the quantity in (9) is equivalent to maximizing the nuclear norm.

heading: 4 The estimation problem
text: In this section, we consider the estimation problem of reconstructing a rank-r matrix X? from a set of linear measurements yi = 〈Ai,X?〉, i = 1, . . . ,m. Theorem 1 and Theorem 2 imply that mirror descent, equipped with the spectral hypentropy mirror map (4) or spectral entropy mirror map (5), approximately minimizes the nuclear norm for a small mirror map parameter β or a small initialization size α. Hence, mirror descent, a first-order algorithm minimizing the unregularized empirical risk, can recover a low-rank matrix X? under the same set of assumptions which is sufficient for nuclear norm minimization to be successful.

heading: 4.1 Matrix sensing with restricted isometry property
text: The following restricted isometry property has been shown to be sufficient to guarantee recovery of low-rank matrices using nuclear norm minimization [27], and has also been used in [19] to show that gradient descent with full-rank factorized parametrization recovers X?.
Definition 1 (Restricted isometry property [27]). A set of matrices A1, . . . ,Am ∈ Rn×n ′
satisfies (r, δ)-restricted isometry property (RIP) if for any matrix X ∈ Rn×n′ with rank at most r, we have
(1− δ)‖X‖F ≤ ( 1
m m∑ i=1 〈Ai,X〉2 )1/2 ≤ (1 + δ)‖X‖F .
With this definition, we have the following recovery guarantee for mirror descent.
Theorem 3. Assume that the set of measurement matrices {Ai}mi=1 satisfies (5r, δ)-restricted isometry property with δ ≤ 0.1. Then, the mirror descent algorithm described in Theorem 1 with parameter β < ‖X
?‖∗ 1.05en converges to a matrix X∞ = limt→∞Xt that satisfies
‖X∞ −X?‖F ≤ ∆β‖X?‖∗ + (1 + ∆β) nβ log ‖X?‖∗ β −1
Cδ √ 3r , (11)
where Cδ = 12 (1− √ 2 3 − δ(1 + √ 2 3 )) and ∆β = ( log(‖X?‖∗/β)−1 log(1.05n) − 1) −1.
If, additionally, n = n′ and X? is positive semidefinite, then the mirror descent algorithm described in Theorem 2 with α < ‖X
?‖∗ en converges to a positive semidefinite matrix X∞ that satisfies
‖X∞ −X?‖F ≤ ∆α‖X?‖∗ Cδ √ 3r , (12)
where ∆α = ( log(‖X?‖∗/α)−1 logn − 1) −1.
Among the existing results on implicit regularization in matrix sensing, the result that is perhaps most closely related to Theorem 3 is Theorem 1.1 in [19], which considers the positive semidefinite case of matrix sensing with full-rank parametrization X = UU>, U ∈ Rn×n, and shows that gradient descent recovers X? under the assumption of restricted isometry with constant δ ≤ c/(κ3 √ r log2 n), where κ is the condition number of X? and c > 0 is an absolute constant.
The analysis that leads to Theorem 3 differs significantly from the proof of Theorem 1.1 in [19]. The proof of Theorem 1.1 in [19] involves an analysis of the trajectory of gradient descent, relating it to the population dynamics defined by the population risk E(Ai)kl∼N (0,1)[f(UtU>t )] = ‖UtU>t −X?‖2F , and identifying adaptive rank-r subspaces to which the iterates Ut are approximately confined. On the other hand, Theorem 3 follows from Theorem 1 and Theorem 2, which rely on a simple analysis of the evolution of the Bregman divergence, and employs arguments similar to the ones used in [27] to prove that RIP is sufficient to guarantee that nuclear norm minimization recovers X?. Further, our analysis applies both to the case of rectangular and positive semidefinite matrices, while the results in [19] only hold for the full-rank parametrization X = UU>, U ∈ Rn×n, for which an extension to general rectangular matrices does not seem to be trivial, see e.g. [16, 21, 29, 31, 39].
Sample complexity and condition number. The restricted isometry property assumption in Theorem 1.1 in [19] requires a restricted isometry constant δ ≤ c/(κ3 √ r log2 n) for an absolute constant c > 0, which leads to a sample complexity of O(κ6nr2 log5 n) if the sensing matrices Ai’s belong to a general class of random matrices [27]. It is conjectured in [19] that the dependence of δ on the rank r and condition number κ is not tight, and that δ only needs to be smaller than some absolute constant. On the other hand, Theorem 3 only requires δ ≤ 0.1, which is the same assumption that is sufficient to guarantee that nuclear norm minimization recovers low-rank matrices [27] and leads to a sample complexity of O((n+ n′)r log(nn′)) . To the best of our knowledge, our result for mirror descent is the first recovery guarantee for an implicit regularization-based algorithm for (rectangular) matrix sensing that only requires the same assumptions as nuclear norm minimization [27].
Convergence speed and dependence on intialization size. The analysis along the trajectory of gradient descent in [19] allows to establish convergence speed guarantees and a polynomial dependence of the estimation error ‖UtU>t −X?‖F on the initialization size α. On the other hand, we have no convergence speed guarantees for mirror descent (beyond the bounds on the empirical risk (7) and (10)), and the final estimation error ‖X∞−X?‖F depends logarithmically on the parameters α and β, which can lead to an unpractically small value for α and β being required to reach some
desired accuracy ε. Nonetheless, our result guarantees exact recovery of X? in the limit α, β → 0, which is a setting often considered in the literature, e.g. [14, 20, 35].
We remark that, beyond the aforementioned result on implicit regularization in matrix sensing [19], similar recovery results that include convergence speed guarantees and a polynomial dependence on the initialization size have also been established for implicit regularization-based algorithms in the context of sparse linear regression [32] and sparse phase retrieval [36, 37]. However, these results all require a sample complexity that scales quadratically in the respective notions of sparsity, and we leave it to future work to investigate whether it is possible to establish convergence guarantees that include a convergence speed analysis and depend polynomially on α and β when a sample complexity that scales only linearly in the rank r of X? is assumed.

heading: 4.2 Matrix completion
text: In matrix completion, a subset of the entries of the matrix X? is observed, and the corresponding sensing matrices Ai’s do not satisfy the restricted isometry property. Instead, an incoherence condition together with a sufficient number of randomly observed entries have been used to guarantee recovery for nuclear norm minimization [26] and gradient descent [22], for instance.
Definition 2 (Coherence [6]). Let U ⊆ Rn be a linear subspace of dimension r and PU the orthogonal projection onto U . The coherence of U is defined as ({ei}ni=1 denotes the canonical basis)
µ(U) = n
r max 1≤i≤n ‖PUei‖22.
We have the following recovery guarantee for mirror descent under the same assumptions as in [26].
Theorem 4. Let X? ∈ Rn×n′ be a rank-r matrix with (compact) singular value decomposition X? = UΣV>, where U ∈ Rn×r, V ∈ Rn′×r and Σ ∈ Rr×r. Assume that: A1 The row and column spaces of X? have coherences bounded by µ0 > 0. A2 The matrix UV> has maximum entry bounded by µ1 √ r/nn′ in absolute value for some µ1 > 0.
Suppose that we observe m entries of X? with locations sampled uniformly at random. Then, if m ≥ 32cmax{µ20, µ1}r(n+ n′) log
2(2n′) for some c > 1, the mirror descent algorithm described in Theorem 1 with β < ‖X
?‖∗ 1.05en converges to a matrix X∞ = limt→∞Xt that satisfies
‖X∞ −X?‖F ≤ 6 ( ∆β‖X?‖∗ + (1 + ∆β) nβ
log ‖X ?‖∗ β − 1
)( 1 + ( 128cnn′ log2 n′
9m
) 1 2 ) , (13)
with probability at least 1−6 log(n′)(n+n′)2−2c−(n′)2−2 √ c, where ∆β = ( log(‖X?‖∗/β)−1 log(1.05n) −1) −1.
If, additionally, n = n′ and X? is positive semidefinite, then the mirror descent algorithm described in Theorem 2 with α < ‖X
?‖∗ en converges to a positive semidefinite matrix X∞ that satisfies
‖X∞ −X?‖F ≤ 6∆α‖X?‖∗ ( 1 + ( 128cn2 log2 n
9m
) 1 2 ) , (14)
where ∆α = ( log(‖X?‖∗/α)−1 logn − 1) −1.
To the best of our knowledge, there are no recovery guarantees in matrix completion for an unregularized empirical risk minimization-based algorithm that does not explicitly enforce the low-rank constraint. For instance, when X? ∈ Rn×n is positive semidefinite, Theorem 2 in [22] establishes a recovery guarantee for gradient descent with low-rank parametrization X = UU>, where U ∈ Rn×r, applied to the unregularized empirical risk with a sample requirement of order r3n log3 n.

heading: 5 Connection with gradient descent
text: In the vector-case, it has been established that gradient descent with parametrization x = u u−v v is a first-order approximation to mirror descent equipped with the hypentropy mirror map [10, 33, 36],
and a general framework connecting mirror descent and reparametrized gradient descent was studied in [1]. A natural question is whether such a connection also extends to the matrix-case.
In the following, we consider matrix sensing with square symmetric sensing matrices Ai ∈ Rn×n, i = 1, . . . ,m. Consider the following exponentiated gradient algorithm given by
Xt = Ut −Vt
Ut+1 = Ute −η∇f(Xt) + e−η∇f(Xt)Ut 2 , Vt+1 = Vte η∇f(Xt) + eη∇f(Xt)Vt 2 . (15)
When considering the full-rank parametrization X = UU> −VV>, where U,V ∈ Rn×n, gradient descent on the variables (U,V) is a first-order approximation to the exponentiated gradient algorithm defined in (15), with the step size rescaled by a constant factor and the approximation being exact in the limit η → 0, see Appendix B.6 for details. The gradient descent algorithm considered in [3, 14, 19, 20] can be obtained by initializing V0 = 0.
Proposition 5. Assume that the sensing matrices Ai’s are symmetric and commute. Then: 1. Mirror descent equipped with the spectral entropy mirror map (5) and any positive definite
initialization X0 which commutes with all Ai’s (e.g. X0 = αI for some α > 0) is equivalent to the exponentiated gradient algorithm defined in (15) with initialization U0 = X0 and V0 = 0.
2. Mirror descent equipped with the spectral hypentropy mirror map (4) with parameter β > 0 and initialization X0 = 0 is equivalent to the exponentiated gradient algorithm defined in (15) with initialization U0 = V0 = 12βI.
As a Corollary, we obtain a generalization of Theorem 1 in [14]. Let f̃(U) = f(UU>).
Corollary 6. Assume that the sensing matrices Ai’s are symmetric and commute, and that there exists a X′ ∈ Sn+ satisfying f(X′) = 0. Then, the gradient flow defined by dUtdt = −∇f̃(Ut) and any initialization satisfying U0U>0 = αI converges to a matrix U∞ minimizing
n∑ i=1 ( log 1 α − 1 ) λi + λi log λi
among all global minimizers of f̃ , where {λi}ni=1 denote the eigenvalues of the matrix U∞U>∞.
This result generalizes Theorem 1 in [14] in two ways: first, we obtain a precise characterization of the quantity that is minimized for any initialization size α > 0, which indeed coincides with the nuclear norm in the limit α→ 0. Second, convergence to a global minimizer is assumed in Theorem 1 in [14], which is non-trivial a-priori, since the optimization problem in Ut is non-convex. On the other hand, we show convergence of mirror descent in Theorem 2, which then carries over to gradient flow on the non-convex objective f̃ via Proposition 5 (when the Ai’s are symmetric and commute).

heading: 6 Numerical simulations
text: In this section, we present numerical simulations examining the dependence of the final estimates of mirror descent equipped with the spectral entropy (5) and of gradient descent with full-rank parametrization X = UU>, U ∈ Rn×n, on the initialization size for random Gaussian sensing matrices A1, . . . ,Am. We evaluate the nuclear norm ‖X‖∗, the reconstruction error ‖X−X?‖F , and the effective rank [28] effrank(X) = exp(− ∑n i=1 pi log pi), where pi = σi/‖X‖∗, i = 1, . . . , n, denote the normalized singular values of X. Numerical simulations for matrix completion are provided in Appendix C and yield similar results as for random Gaussian sensing matrices.
Our experimental setup is as follows. We generate a rank-r positive semidefinite matrix by sampling a random matrix U? ∈ Rn×r with i.i.d. N (0, 1) entries, setting X? = U?(U?)> and normalizing ‖X?‖∗ = 1. We generate m symmetric sensing matrices Ai = 12 (Bi + B > i ), where the entries of Bi are i.i.d. N (0, 1). We run mirror descent and gradient descent with initialization X0 = αI and constant step sizes µ = 1 and µ = 0.25, respectively, for T = 5000 iterations, and vary the initialization size α from 10−1 to 10−10. For reference, we also include the ground truth X? and the estimate obtained from minimizing the nuclear norm, argmin{‖X‖∗ : X 0, f(X) = 0}, using the
cvxopt package. The experiments for Figure 1 were implemented in Python 3.9 and took around 10 minutes on a machine with 1.1-GHz Intel Core i5 CPU and 8 GB of RAM.
With m = 3nr measurements (Figure 1, top row), nuclear norm minimization coincides with X?. In this case, our simulations show that the estimate of gradient descent closely tracks the estimate of mirror descent for all initialization sizes in terms of nuclear norm, effective rank [28] and reconstruction error, even though the sensing matrices do not commute. When we have m = nr measurements (Figure 1, bottom row), nuclear norm minimization does not recover the planted matrix X?, and our simulations show that gradient descent puts more emphasis on lowering the effective rank at the expense of a higher nuclear norm for initialization sizes smaller than 10−3. Since Theorem 2 guarantees that mirror descent minimizes the nuclear norm in the limit α→ 0, regardless of the number of measurements, this is in line with the observations in [3, 20], which suggest that a notion of rank-minimization is involved in the implicit bias of gradient descent.

heading: 7 Conclusion
text: In this paper, we analyzed discrete-time mirror descent for matrix sensing, equipped with the spectral hypentropy mirror map in the case of general rectangular matrices and equipped with the spectral entropy mirror map in the particular case of positive semidefinite matrices. We showed that mirror descent minimizes a quantity that interpolates between the nuclear norm and Frobenius norm in the rectangular case, and is a linear combination of the nuclear norm and the negative von Neumann entropy in the positive semidefinite case. We used this result to show that mirror descent, a first-order algorithm minimizing the unregularized empirical risk that does not explicitly enforce low-rankness of its iterates, can recover a low-rank matrix X? under the same set of assumptions which is sufficient for nuclear norm minimization to recover X? [26, 27].
A downside of mirror descent compared to gradient descent with full-rank factorized parametrization, which is an alternative implicit regularization-based algorithm for matrix sensing, is its computational cost: the spectral hypentropy requires a singular value decomposition in each iteration, while the spectral entropy requires computing a matrix exponential in each iteration, see Appendix A. For general sensing matrices, the computational cost of mirror descent is of the same order as that of gradient descent, since a singular value decomposition takes O(n2n′) operations and matrix exponentials can be computed in O(n3) operations, while evaluating the gradient ∇f(X) = 1m ∑m i=1(〈Ai,X〉 − yi)Ai requires O(mnn′) operations, and m > n is typically required to recover X?. However, the inner product 〈Ai,X〉 can be computed in O(1) operations in matrix completion, in which case the computational cost of gradient descent with full-rank factorized parametrization is dominated by the multiplication of two n × n matrices. When r min{n, n′}, neither implicit regularizationbased approach achieves the computational efficiency of gradient descent with low-rank factorized parametrization X = UV>, where U ∈ Rn×r, V ∈ Rn′×r, see e.g. [8, 22]. Previous results on implicit regularization-based algorithms in matrix sensing [19], sparse linear regression [32] and sparse phase retrieval [36, 37] establish convergence speed guarantees and a poly-
nomial dependence on the initialization size α, while a sample complexity that scales quadratically in the respective notions of sparsity is required. On the other hand, our results for mirror descent in matrix sensing require a sample complexity that scales linearly in the rank r of X?, but do not establish any convergence speed guarantees, and the bound on the estimation error depends logarithmically on α and β. We leave bridging this gap, i.e. establishing convergence speed guarantees with a polynomial dependence on α and β while only assuming a linear sample complexity, to future work.
Acknowledgments and Disclosure of Funding
Fan Wu is supported by the EPSRC and MRC through the OxWaSP CDT programme (EP/L016710/1). Patrick Rebeschini was supported in part by the Alan Turing Institute under the EPSRC grant EP/N510129/1.

Review summaries:
In this manuscript, the authors study the trajectory of mirror descent to optimize the unregularized empirical risk functional to solve low-rank matrix estimation problems. They characterize the trajectory of mirror descent with different mirror maps and showcase an implicit bias towards certain structures in solutions. In particular, when equipped with either the spectral hypentropy map or spectral entropy map, they show that mirror descent converges to a global minimizer that minimizes a particular quantity depending on the singular values of the resulting matrix. This quantity interpolates between the nuclear norm and Frobenius norm for the spectral hypentropy map and is a linear combination of the nuclear norm and von Neumann entropy for the spectral entropy map. They also show algorithmic guarantees for mirror descent to solve matrix sensing and matrix completion problems that operate with sample complexities on par with traditional nuclear norm minimization approaches, without explicit regularization. Finally, a connection between gradient descent over the parameterization $UU^T - VV^T$ and mirror descent is shown and toy experiments show mirror descent and gradient descent behave similarly.

The paper provides the convergence analysis of mirror descent for matrix sensing to particular minimum norm solutions. The updates that are studied are induced by the hypentropy and von Neumann divergences. The authors analyze multiple interesting cases including matrix completion and the case where the instances satisfy the RIP. They also provide some experimental evaluations to validate their findings.