Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization

1 Introduction

• Noisy matrix completion is substantially less understood theoretically than the noiseless problem, despite convex relaxation’s strong practical stability against additive noise.The task estimates a low-rank matrix from a randomly incomplete set of noisy entries.Source: §1 · pp. 2–3

1.1 Convex relaxation: limitations of prior results

• Convex relaxation replaces rank minimization with nuclear-norm regularization, but prior noisy-setting bounds were significantly worse than the oracle lower bound.In the noiseless setting, related convex programs can achieve exact recovery under near-minimal sample complexity.Source: §1.1 · p. 3

1.2 A detour: nonconvex optimization

• The nonconvex Burer–Monteiro approach factors the matrix as Z = XY^⊤ and has appealing noise-robust guarantees, motivating comparison with convex relaxation.When the convex solution has rank r, it coincides with the corresponding factored formulation, although establishing that rank condition is difficult.Source: §1.2 · pp. 3–4

1.3 Empirical evidence: convex and nonconvex solutions are often close

• The convex and nonconvex estimates are typically separated by less than 10^-7 in relative Frobenius distance, far below their respective estimation errors.This numerical proximity suggests that nonconvex statistical guarantees may transfer to convex relaxation, unlike prior theory.Source: §1.3 · p. 4, Figure 1 · p. 5

1.4 Models and main results

• The paper’s main strategy is to rigorously justify convex–nonconvex proximity and propagate the nonconvex scheme’s stability guarantees to the convex program.This route is presented as yielding significantly enhanced statistical guarantees for noisy matrix completion.Source: §1.4 · p. 5

1.4.1 Models and assumptions

• The theory assumes independent random sampling, independent zero-mean sub-Gaussian noise, and an incoherent low-rank matrix with condition number κ.The incoherence condition is presented as crucial for reliable recovery, while alternative spikiness or bounded-ℓ∞ conditions alone may not ensure identifiability.Source: §1.4.1 · pp. 5–6

1.4.2 Theoretical guarantees: when both the rank and the condition number are constants

• When rank r and condition number κ are O(1), the paper claims near-optimal statistical guarantees for practically important noisy matrix-completion settings.The theorem applies under the stated model assumptions, a sufficiently large logarithmic sample-size condition, an appropriate λ proportional to σ√np, and a bounded noise level.Source: §1.4.2 · p. 6

1. Any minimizer Zcvx of (3) obeys

• Under µ = O(1), the method requires sample size above npoly log n, while each-entry noise may substantially exceed the matrix’s maximum entry.The sample complexity is information-theoretically optimal up to logarithmic factors, and the allowed entrywise signal-to-noise ratio can be very small.Source: §1 · p. 6
• Convex optimizers achieve near-optimal Euclidean stability, degrading gracefully with decreasing signal-to-noise ratio and matching the oracle lower bound [CP10].The result improves over the corresponding stability guarantee obtained from [CP10] under the random-noise model.Source: §1 · p. 7
• The convex solution is nearly rank-r, and replacing Zcvx by its best rank-r approximation preserves the stated Frobenius and entrywise error guarantees.Thus rank-r projection incurs no statistical accuracy loss when the true rank is known.Source: §1 · pp. 6–7
• Entrywise control implies implicit spikiness regularization, making the additional constraint ∥Z∥∞≤α unnecessary and yielding results nearly identical to the constrained estimator.The numerical comparison is reported in Figure 3.Source: §1 · p. 7
• Any sufficiently accurate objective-value approximation inherits the optimizer’s error bounds, providing statistical guarantees for iterative methods including SVT, FPC, SOFT–IMPUTE, and FISTA.This applies when g(Z) ≤ g(Zcvx)+ε for sufficiently small ε.Source: §1 · p. 7
• Entrywise and spectral-norm errors are controlled and both scale linearly with the noise level in Figure 2.Figure 2 reports relative errors for n = 1000, r = 5, p = 0.2, λ = 5σ√np, averaged over 20 trials.Source: Figure 2 · p. 8

1.4.3 Theoretical guarantees: extensions to more general settings

• The theory extends beyond bounded rank and condition number, covering growing r and κ under corresponding sample-size and noise conditions with high probability.Theorem 2 assumes µ-incoherence, λ = Cλσ√np, and a sample requirement scaling with κ, µ, and r.Source: §1.4.3 · p. 8

Rank approximation

• The best rank-r approximation Zcvx,r preserves the error bounds established for the convex solution Zcvx.Thus, the convex estimator is effectively nearly low-rank under the stated guarantees.Source: §1 · p. 9

Noise condition

• The noise condition permits typical noise much larger than the largest entry of M⋆ when p ≫ κ^6µ^3r^3 log n / n; for r, κ = O(1), it recovers Theorem 1’s condition.Incoherence bounds ||M⋆||∞ by κµrσmin/n, enabling this regime.Source: §1 · p. 9

Limitations

• The guarantees require a more stringent sample size than noiseless completion, and their dependence on r and κ is likely suboptimal because the analysis relies on nonconvex optimization.Improving these dependencies is left for future work.Source: §1 · p. 9

Implications

• The convex estimate retains nearly low-rank structure, spreads estimation error across entries, and provides guarantees for approximate minimizers of (3).This reveals implicit regularization against spikiness and extends statistical guarantees to iterative algorithms that approximately minimize the program.Source: §1 · p. 9

2 Strategy and novelty

• The noisy setting is difficult because the convex program lacks a closed-form primal solution, so the proof approximates it using an iterative nonconvex algorithm.In the noiseless case, the ground truth suggests the primal solution directly; random noise makes the corresponding primal-dual pair difficult to identify.Source: §2 · p. 10, §2.1 · p. 10

2.1 Exact duality

• A dual certificate is necessary and almost sufficient for convex optimality and uniqueness, but constructing one in noise requires identifying the unknown primal solution first.In the noiseless case, certificates can be constructed by least squares or golfing schemes [CR09].Source: §2.1 · p. 10

2.2 A candidate primal solution via nonconvex optimization

• Under Condition 1 and tangent-space injectivity, any full-rank critical point of the nonconvex problem yields a unique convex minimizer equal to XY^⊤.The rank-one intuition constructs the dual-certificate condition from the nonconvex first-order condition, while proximity to M⋆ ensures the required norm bound.Source: §2.2 · p. 11

2.3 Approximate nonconvex optimizers

• Near-zero gradients suffice: under strengthened injectivity and factor singular-value conditions, every convex minimizer lies in a neighborhood of XY^⊤ whose radius shrinks with the gradient norm.This approximate result also covers sufficiently accurate objective-value solutions, including iterative methods such as SVT [CCS10], FPC [MGC11], SOFT–IMPUTE [MHT10], and FISTA [BT09].Source: §2.3 · p. 12

2.4 Construction of an approximate nonconvex optimizer

• With high probability, noise concentration makes Condition 1 hold for λ proportional to σ√(np), while a uniform tangent-space bound establishes Condition 2.Gradient descent initialized at the ground truth is an auxiliary construction intended to produce a sufficiently accurate small-gradient iterate; spectral initialization can make it practical [MWCC17] [CLL19].Source: §2.4 · pp. 12–13

2.5 Properties of the nonconvex iterates

• Leave-one-out analysis shows that ground-truth-initialized gradient descent remains close to the true factors in Frobenius, spectral, and ℓ2,∞ norms and contains a small-gradient iterate.The analysis follows Ma et al. [MWCC17] and the rectangular extension of Chen et al. [CLL19]; the step size is η ≍1/(nκ^3σmax) with t0 = n^18 iterations.Source: §2.5 · pp. 13–14

2.6 Proof of Theorem 2

• Selecting the smallest-gradient iterate and applying the approximate-duality lemma shows that the convex and nonconvex estimates are exceedingly close, so convex error is governed mainly by the nonconvex estimate.The argument uses the sample-complexity condition np ≳κ^4µ^2r^2 log^3 n to control the remaining comparison.Source: §2.6 · pp. 14–15

• Nuclear norm minimization [CR09] can exactly recover rank-r matrices from about nr samples in the noiseless setting [Gro11,Rec11,Che15].Gross’s golfing scheme became an influential dual-construction technique.Source: §3 · p. 15
• For noisy completion, convex-programming analyses [CP10] provide stability or estimation bounds but not optimal guarantees under the paper’s model when r = O(1).Source: §3 · p. 15
• Nonconvex matrix-completion methods offer computational advantages, with convergence established for manifold, alternating-minimization, gradient, and projected-gradient algorithms under suitable initialization.Vanilla gradient descent requires O(nr3) samples and O(log 1/ε) iterations without extra regularization [MWCC17], while [CLL19] improves the sample complexity to O(nr2).Source: §3 · pp. 15–16
• Generic low-rank SDP guarantees motivating Burer–Monteiro optimization [BVB16] are conservative for matrix completion and do not imply that all SDP solutions are approximately low-rank.In the noiseless case, they give rank at most O(n2p), which can greatly exceed the true rank, such as n2p ≫√n ≫r.Source: §3 · p. 16
• Connections between convex and nonconvex optimization have also been studied in line spectral estimation, but that setting differs substantially from matrix completion.Source: §3 · p. 16

4 Discussion

• The paper improves statistical analysis for the natural convex program without an additional spikiness constraint and reveals a connection to nonconvex optimization.The connection may apply beyond matrix completion.Source: §4 · p. 16
• The theory is optimal for constant rank r and condition number κ, but its dependencies loosen as either grows; improving them may require new tools.In the noiseless setting, convex relaxation has sample complexity O(nr), independent of κ, while nonconvex factorization theory is typically also suboptimal in r and κ [KMO10a] [CW15] [MWCC17] [CLL19].Source: §4 · p. 16
• Extending the theory from exactly low-rank matrices to approximately low-rank matrices remains open because the tightness of the nonconvex proxy is unclear.The nonconvex landscape for approximate low rank [CL17] may provide guidance.Source: §4 · p. 16
• The current leave-one-out analysis relies on i.i.d. sub-Gaussian noise, motivating extension to deterministic noise with bounded magnitudes.Such an extension would broaden the applicability of convex relaxation.Source: §4 · p. 16
• The framework may extend to structured matrix completion, where additional structure can reduce sample complexity and help address pessimistic Hankel stability guarantees [CC14].For low-rank Hankel matrices, sample complexity can be O(n) times smaller than in the generic low-rank case.Source: §4 · p. 16
• The paper’s insights may yield tighter statistical guarantees for robust PCA, blind deconvolution, and blind demixing, whose convex-relaxation stability analyses are often suboptimal.These problems and related analyses are cited as, [LS15], [JKS17], and.Source: §4 · p. 16
• The convex–nonconvex link enables statistically optimal inference and uncertainty quantification for noisy matrix completion, including optimal confidence intervals for missing entries [CFMY19].The companion paper [CFMY19] provides in-depth discussion.Source: §4 · p. 17

A Preliminaries

• The preliminaries gather notation and preliminary facts used throughout the proofs, including incoherence-based bounds and conventions for asymptotic inequalities and notation.These preliminaries support the subsequent proof development.Source: A Preliminaries · p. 23

B Exact duality analysis

• The convex program has a unique minimizer when a suitable dual certificate exists and P_Ω is injective on the tangent space.The proof shows strict objective increase for every nonzero feasible perturbation.Source: B Exact duality analysis · pp. 23–24
• The uniqueness argument first shows that any two minimizers agree on observed entries, so their difference satisfies P_Ω(H) = 0.Strict convexity of the data-fit term along differing observations yields the contradiction.Source: B Exact duality analysis · pp. 23–24
• The dual-certificate proof compares every alternative minimizer Z + H against Z, using nuclear-norm subgradients and strictness when the orthogonal perturbation is nonzero.If the orthogonal component vanishes, tangent-space injectivity forces H = 0.Source: B Exact duality analysis · pp. 23–24

C.1 Proof of Lemma 1

• Any stationary factorization (X, Y) has balanced scale, enabling its product XY^⊤ to yield the tangent-space and singular-vector structure needed for dual certification.The analysis reduces Lemma 1 to proving that the orthogonal residual W satisfies ∥W∥<1.Source: §C.1 · pp. 24–25

C.2 Proof of Lemma 2

• For a convex minimizer Z_cvx, the difference ∆ = Z_cvx − XY^⊤ lies primarily in the tangent space, connects sampling error to the gradient, and is controlled by injectivity.Combining these steps yields the advertised upper bound on ∥∆∥_F under small-gradient and singular-value assumptions.Source: §C.2 · pp. 26–27

2. Continue the upper bound in (55) to obtain

• 32 ∥∆∥^2_F ≤ 1/(2p) ∥P_Ω(∆)∥^2_F ≤ 72κ/√σ_min ∥∇f(X, Y)∥_F ∥∆∥_F.This final inequality combines the sampling lower bound with the gradient-based upper bound.Source: §2 · pp. 27–28
• The continuation bounds the orthogonal component of ∆ through the tangent component, then lower-bounds ∥P_Ω(∆)∥_F using injectivity.These estimates hold when c is sufficiently small and complete the error-control argument.Source: §2 · pp. 27–28

C.2.1 Proof of Claim 2

• Claim 3 yields an invertible Q such that X = UΣ^1/2Q and Y = VΣ^1/2Q^-⊤ under Lemma 2’s assumptions.This factorization connects the factors X,Y to the SVD UΣV⊤ of XY⊤.Source: §C.2.1 · p. 28
• The tangent-space bound follows from representing the relevant terms through matrices B1 and B2 whose Frobenius norms are controlled by ∥∇f(X,Y)∥F.The assumptions imply max{∥B1∥F, ∥B2∥F} ≤ √p∥∇f(X,Y)∥F.Source: §C.2.1 · p. 28
• The proof of Claim 2 decomposes the residual R into tangent-space and orthogonal-complement components and bounds both separately.The tangent-space analysis uses the projection definition, Claim 3, and bounds controlled by the gradient norm.Source: §C.2.1 · p. 28
• The Claim 2 bounds hold when the constant c is sufficiently small, using cinj ≤ 1/p and κ ≥ 1.The proof repeatedly invokes this smallness condition when controlling Q and completing the projection estimates.Source: §C.2.1 · pp. 29–30
• For the orthogonal-complement component, debiasing identities and the factorization of X,Y reduce the task to bounding ∥P_T⊥(R̃)∥.The reduction uses that UV⊤, XY⊤, UΣV⊤, and UΣ^1/2QQ⊤Σ^-1/2V⊤ lie in the tangent space.Source: §C.2.1 · pp. 29–30
• Weyl’s inequality and rank(M⋆)=r control the singular directions beyond the first r, whose relevant singular values are no larger than λ/2.These directions cannot simultaneously lie in the column space of U and the row space of V⊤.Source: §C.2.1 · p. 30

C.2.2 Proof of Claim 3

• The proof of Claim 3 derives the same invertible-Q factorization from the identities for X,Y and the bounds ∥X∥,∥Y∥ ≤ √2σmax.The singular values of Q are then used with assumptions (49), (78), and (23) to complete the claim.Source: §C.2.2 · p. 31

C.3 Proof of Lemma 4

• Lemma 7 proves uniform injectivity of PΩ(·) over tangent spaces near (X⋆, Y⋆) when n^2p ≥ Cµrn log n, with probability exceeding 1 − O(n^−10).This uniformity extends beyond fixed tangent spaces and handles tangent spaces statistically dependent on Ω.Source: §C.3 · p. 31
• Unlike prior fixed-tangent-space analyses [CR09], Lemma 7 establishes injectivity uniformly over a large set of tangent spaces.This is the key structural feature enabling dependence between the tangent space and the sampling pattern.Source: §C.3 · p. 31
• The companion result shows PΩ(XY⊤ − M⋆) is uniformly close to p(XY⊤ − M⋆) for all nearby factors under condition (26) and λ = Cλσ√(n/p).The statement holds with probability exceeding 1 − O(n^−10).Source: §C.3 · p. 32

C.3.1 Proof of Lemma 7

• The proof of Lemma 7 selects a specific solution to the underdetermined linear system and derives the needed bounds through a Lagrangian argument.The construction satisfies the property used in the subsequent analysis.Source: §C.3.1 · p. 32
• The upper bound in Lemma 7 follows by controlling max{∥X∥, ∥Y∥} from the proximity assumption and applying elementary inequalities and the triangle inequality.The argument uses ∥Y∥ ≤ 2√σmax before substitution into the target bound.Source: §C.3.1 · p. 33

2. We now move on to the lower bound (84). To this end, one first decomposes

• The lower bound decomposes the target expression into terms α1 and α2, then bounds γ1 through γ5 using incoherence, auxiliary lemmas, and smallness conditions.The proof invokes [CR09, Section 4.2], Lemma 19, Lemma 21, [KMO10a, Lemma 3.2], and [ZL16, Lemma 9].Source: §2 · pp. 33–35

C.3.2 Proof of Lemma 8

• Lemma 8 controls the relevant fluctuation terms by combining triangle inequalities, [CL17, Lemma 4.5], incoherence, the choice of λ, and the condition n^2p ≫ κ^4µ^2r^2n log n.The final bound also uses p ≪ 1/κ and the entrywise upper bound implied by (34).Source: §C.3.2 · p. 36

D Analysis of the nonconvex gradient descent algorithm

• Leave-one-out sequences remove samples associated with each row or column, preserving iterate proximity while enabling statistical independence to control rowwise errors.The construction applies to both row and column indices and underpins the inductive proof of Lemma 5.Source: D Analysis of the nonconvex gradient… · p. 37
• The induction runs through t0 = n^18 iterations with step size η ≍ 1/(nκ^3σmax), establishing Frobenius, spectral, leave-one-out, ℓ2/ℓ∞, balancedness, and descent properties.The resulting lemmas also support the small-gradient conclusion for the nonconvex iterates.Source: D Analysis of the nonconvex gradient… · pp. 38–39

D.1 Preliminaries and notations

• The augmented loss adds a balancing penalty ∥X^⊤X−Y^⊤Y∥_F^2/8 for proof convenience, while Algorithm 1 still optimizes the original loss.This penalty simplifies the geometric analysis without changing the algorithm being analyzed.Source: §D.1 · p. 40
• The augmented loss has local curvature at least (1/10)σmin in the factorized direction under sufficient sampling and bounded noise.Lemma 17 supplies the local geometry used later to control gradient and error terms.Source: §D.1 · p. 40

2. Suppose that the noise satisfies

• The noise-dependent induction consequences include aligned factor control and leave-one-out relations needed to propagate the iterate bounds.These consequences are collected from the induction hypotheses before the proofs of the individual lemmas.Source: §D.1 · p. 41, §2 · p. 41

D.2 Proof of Lemma 9

• A telescoping decrease in function values, combined with the initialization at (X⋆,Y⋆) and Hessian control, yields the small-gradient bound at t0.The argument uses rotational invariance, incoherence, λ ≍ σ√(np), and η ≍ 1/(nκ^3σmax).Source: §D.2 · pp. 41–42

D.3 Proof of Lemma 10

• Lemma 10 decomposes the next Frobenius error into gradient, balancing, and curvature terms, then bounds them using the augmented-loss geometry and induction hypotheses.The proof controls α3 through balanced initialization, α2 through factor norms and balancedness, and α1 through the fundamental theorem of calculus.Source: §D.3 · pp. 42–43
• The Lemma 10 conclusion follows when η ≤ 1/(1000κσmax) and CF is sufficiently large, completing the Frobenius-error induction step.The three α-term bounds are combined after controlling the Hessian along the segment between the current and target factors.Source: §D.3 · pp. 43–44

D.4 Proof of Lemma 11

• Claim 4 shows that the auxiliary iterate ˜F_t+1 is aligned with F⋆, so I_r is its best rotation under condition (113).The proof verifies that F⋆⊤˜F_t+1 is symmetric positive semidefinite.Source: §D.4 · pp. 45, 47
• Lemma 11 applies Lemma 22 to F⋆, ˜F_t+1, and F_t+1H_t after checking the required conditioning and gradient-update conditions.The relevant assignments are F0 = F⋆, F1 = ˜F_t+1, and F2 = F_t+1H_t.Source: §D.4 · pp. 45–47
• Lemma 11 concludes after combining bounds, provided C_op ≫ 1 and n^2p ≫ κ^4µ^2r^2n log n.The proof also requires λ ≍ σ√np and σ/σ_min ≪ 1/κ.Source: §D.4 · pp. 45, 47

D.5 Proof of Lemma 12

• D.5 bounds the rowwise remainder terms A1, A2, and A3 using gradient-update identities, rotational invariance, induction hypotheses, and Lemma 15.The argument treats A1 and A2 by derivations parallel to those for α1 and α2, then handles A3 through auxiliary claims.Source: §D.5 · p. 48, §2 · pp. 48–49

2. Next, we turn attention to A2, which clearly obeys

• The A3 analysis combines the bounds on A1 and A2 to obtain the claimed result when C3 is sufficiently large and n^2p ≫ κ^4µ^2r^2n log n.The final step explicitly invokes induction hypothesis (93c).Source: §2 · pp. 49–50
• Claims 5–7 control the auxiliary rowwise terms using conditional independence and matrix Bernstein inequalities, with failure probability at most O(n^-100) under sampling conditions.The stated requirements include np ≫ log^2 n and, for some bounds, np ≫ log n.Source: §2 · pp. 50–51
• The concentration arguments additionally use incoherence and iterate-size controls, including ∥F⋆∥2,∞ ≤ µ√(rσ_max/n) and ∥Y⋆∥F ≤ √(rσ_max).They also require σ/σ_min to be sufficiently small for the relevant Lemma 18 bounds.Source: §2 · pp. 50–52

D.6 Proof of Lemma 13

• D.6 proves Lemma 13 by decomposing (F_t+1,(l)H_t+1,(l) − F⋆)_{l,·} and separately bounding the r-dimensional vectors a1 and a2.The argument assumes 1 ≤ l ≤ n and uses the triangle inequality after introducing Δ_t,(l).Source: §D.6 · p. 52
• D.6 transfers Lemma 18’s control into the a1 and a2 bounds, relying on the induction hypothesis and additional sufficiently large-constant conditions.The stated requirements include n ≫ κµ, a noise constraint involving σ and σ_min, and C_op ≫ 1.Source: §D.6 · p. 53
• D.6 combines the component bounds to obtain Lemma 13 for an absolute constant ˜C, provided n p ≪ 1/κ and η ≪ 1/(κ^2√rσ_max).These conditions are stated at the conclusion of the collective bounds on ∥a1∥2 and ∥a2∥2.Source: §D.6 · p. 53
• D.6 establishes Claim 8 by introducing an auxiliary point ˜F_t+1 and identifying I_r as the best rotation aligning ˜F_t+1,(l) with F⋆.The alignment claim enables an application of Lemma 23 and reduces the analysis to controlling ∥F_t+1,(l)H_t,(l) − ˜F_t+1,(l)∥.Source: §D.6 · p. 54
• The analysis bounds B1 using Lemma 8, addresses B2, and bounds B3 via Lemma 3, then combines the three bounds with Lemma 18 after invoking Lemma 15.Source: §D.6 · pp. 54–55
• D.6 concludes the proof by combining relations (126)–(128), using (123), and substituting the resulting estimates into (125).The final step also requires C_op to be sufficiently large.Source: §D.6 · p. 55

D.7 Proof of Lemma 14

• D.7 proves Lemma 14 by applying the triangle inequality together with Lemmas 13, 18, and 12 to the (t + 1)th iterates, uniformly for 1 ≤ l ≤ 2n.The proof completes when C_∞ ≥ 5C_3 + C_4.Source: §D.7 · pp. 55–56

D.8 Proof of Lemma 15

• D.8 derives an identity for the factor-Gram difference under the gradient descent updates, introducing auxiliary terms B_t and C_t to organize the bound.The proof defines A_t and A_{t+1}, then expresses the update through B_t and C_t before applying the triangle inequality.Source: §D.8 · p. 56
• Under λη/p < 1, the remaining term is controlled by Claim 10, assuming n^2p ≫ κ^2µ^2r^2n log n and the stated noise condition.The proof reduces the argument to bounding ∥Y_t^⊤D_t^⊤D_tY_t − X_t^⊤D_tD_t^⊤X_t∥_F.Source: §D.8 · p. 57
• D.8 combines bounds on three components of D_t with incoherence, induction, and np ≫ κ^2µ^2r^2 to obtain the claimed upper bound.The leave-one-out sequence bounds are stated to follow similarly but are omitted.Source: §D.8 · pp. 57–58

D.9 Proof of Lemma 16

• D.9 exploits f(FR)=f(F) and ∇f(FR)=∇f(F)R for orthogonal R to analyze the update between F_tH_t and F_tH_t−η∇f(F_tH_t).The argument uses an intermediate point between the current iterate and its gradient step.Source: §D.9 · p. 58
• A Hessian bound ∥∇^2f( F̃ )∥≤10σ_max, together with η ≤ 1/(10σ_max), controls the gradient change along the update path.The proof invokes Lemma 17 and the fundamental theorem of calculus after establishing one of the required conditions from Lemma 9.Source: §D.9 · pp. 58–59
• The second condition in D.9 follows from the induction hypothesis when λ ≍ σ√(np)/(σ/σ_min), np ≪ 1/√r, and η ≪ 1/(κnσ_max).These restrictions complete the control needed for Lemma 16.Source: §D.9 · p. 59

D.10 Proof of Lemma 17

• D.10 bounds the noisy Hessian by comparing the augmented loss with a noise-free loss and combining the resulting inequalities under the stated noise scaling.The proof sets λ = 0 and removes E in the clean loss, then uses prior bounds, Lemma 3, the nuclear-norm fact, and the triangle inequality to establish Lemma 17’s claims.Source: §D.10 · pp. 59–60

D.11 Proof of Lemma 18

• D.11 derives the first and second sets of Lemma 18 consequences from induction hypotheses, unitary invariance, triangle inequalities, and auxiliary comparisons between iterates.The bounds require conditions such as n ≫ µr log n and noise-to-signal restrictions involving σ, σ_min, κ, and log n; further consequences follow by analogous arguments.Source: §D.11 · p. 60
• D.11 connects F_tH_t−F_t,(l)H_t,(l) to F_tH_t−F_t,(l)R_t,(l) using Lemma 22 and bounds on the reference factors’ norms.The argument uses F_0 = F⋆, F_1 = F_tH_t, and F_2 = F_t,(l)R_t,(l), together with incoherence- and condition-number-dependent assumptions.Source: §D.11 · p. 61

D.12 Proof of the inequalities (31)

• D.12 proves the inequalities (31) by decomposing X_tY_t⊤−M⋆ and applying Lemma 18, triangle inequalities, incoherence, and norm relations.The proof singles out the entrywise norm, while stating that the Frobenius and corresponding norm bounds follow by the same argument.Source: §D.12 · pp. 61–62

E Technical lemmas

• Technical Lemma 19 provides a uniform high-probability bound for all A, B ∈ R^{n×r} when n^2p ≥ Cn log n.Its proof combines [ZL16, Lemma 9] with algebra and the triangle inequality.Source: E Technical lemmas · p. 62
• Technical Lemma 20 characterizes factors of a rank-r matrix through an invertible Q and shows that balanced-scale factors force Q to be a rotation matrix.The same lemma establishes a perturbation bound using the SVD of Q and identifies σ_min(B) with σ_min(Σ).Source: E Technical lemmas · pp. 62–63
• Technical Lemmas 21–23 supply auxiliary norm, orthogonal-alignment, and matrix-sign inequalities, with proofs tied to [CL17, Lemma 4.4] and [MWCC17, Lemmas 36–37].Lemma 22 compares optimal orthogonal alignments for three matrices, while Lemma 23 controls the matrix-sign perturbation when ∥K∥ ≤ σ_min(S).Source: E Technical lemmas · pp. 63–64