{"id":"ba16c67d-a08b-4a9a-9984-945f69b3ce7b","arxiv_id":"2502.00463","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"An alternating preconditioned gradient algorithm removes the damping term and achieves linear convergence to near-optimal error for noisy over-parameterized matrix sensing and related low-rank problems.","lead":"This paper introduces APGD, an alternating preconditioned gradient descent method that recovers low-rank matrices from noisy linear measurements even when the assumed rank is larger than the true rank. It removes the damping parameter used by earlier preconditioned solvers and claims linear convergence to near-optimal error, with experiments on matrix sensing and several related low-rank problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4's noise concentration ∥∑ s_i A_i∥² ≤ C ν² n log n / m is off by a factor of m under the stated model; the true scale is Θ(ν² n), so Theorem 2's claimed E_opt = O(ν² r n log n / m) is unsupported.","rationale":"The reader's weakest_assumption is the imported spectral-initialization bound, which affects the regime of validity but not the core statistical rate. The more load-bearing defect is the noise-scaling in Lemma 4: the claimed E_opt is smaller than the actual gradient-noise floor by a factor of m. This is not a stylistic or presentational issue; it directly invalidates the central quantitative claim that APGD achieves near-optimal error O(ν² r n log n / m) under the stated noise model. The proof's submultiplicative steps are fine, but the final concentration inequality contradicts standard results for sums of independent Gaussian matrices. A simple numerical experiment would settle the matter. If the concern lands, the main theorem as printed is false, although the algorithm may still converge linearly to a noise floor of order ν² r n (or, equivalently, the model could be rescaled so that the noise has variance ν²/m). The reader's CONDITIONAL verdict is too lenient for the stated theorem; I recommend REJECT of the current version, with the caveat that a corrected normalization might restore a meaningful near-optimal guarantee.","tokens_in":28118,"tokens_out":30806,"duration_ms":258306,"concrete_test":"Run a numerical check of Lemma 4's concentration bound. Fix n = 100, m = 1000, ν = 1. Draw A_i ∈ R^{n×n} with iid N(0,1/m) entries and s_i ~ N(0,1) for i = 1,...,m. Compute M = ∑ s_i A_i and record ∥M∥_2². Repeat 100 times. Lemma 4 predicts ∥M∥_2² ≤ C n log n / m ≈ 0.5 C (with log n ≈ 4.6), while the correct iid-Gaussian-matrix bound gives ∥M∥_2² ≈ 4n = 400. If the observed values cluster near 400 and not near 0.5, the bound in Lemma 4 is false under the paper's stated distributions, and Theorem 2's E_opt must be revised upward by a factor of m.","verdict_should_be":"REJECT","load_bearing_attack":"Theorem 2's central claim is that APGD reaches a near-optimal error E_opt = C_e ν² r n log n / m. The proof depends on Lemma 4, which asserts ∥A*(s) R_t∥²_{P*_{R_t}} ≤ E_opt. The key step is the inequality ∥∑_{i=1}^m s_i A_i∥_2² ≤ C_e ν² n log n / m, cited to Lemma 16 of [16]. Under the model stated in Theorem 2 (A_i entries iid N(0,1/m); s_i independent sub-Gaussian with variance proxy ν²), the matrix M = ∑ s_i A_i has, conditional on s, iid Gaussian entries with variance (∑ s_i²)/m ≈ ν². Standard spectral-norm concentration for iid sub-Gaussian matrices gives ∥M∥_2² = Θ(ν² n) with high probability, not O(ν² n log n / m). For the typical scaling m ≍ r n, this is a factor of m smaller than the truth. Consequently the gradient-noise floor in the APGD analysis is actually Θ(ν² r n), and the paper's claim of a near-optimal error O(ν² r n log n / m) is false as stated. The reader's noted issues (strict step size, Lemma 7 misstatement) are repairable; this noise-scaling error changes the statistical guarantee itself.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Alternating Preconditioned Gradient Descent (APGD) for noisy, over-parameterized, asymmetric matrix sensing. Unlike prior preconditioned methods such as PrecGD and NoisyPrecGD, APGD removes the damping parameter from the right preconditioners by alternating the L- and R-updates. The main theoretical result, Theorem 2, claims that APGD converges linearly to a near-optimal error floor E_opt = O(ν² r n log n / m) under RIP, sub-Gaussian noise, spectral initialization, and a step-size condition η ≤ 1/(1+δ). The paper also gives a general contraction result, Theorem 3, for rank-2r restricted smooth and strongly convex losses, and reports experiments on noisy matrix sensing, weighted PCA, 1-bit matrix completion, and matrix completion.","tokens_in":28346,"tokens_out":10726,"duration_ms":109981,"significance":"The damping-free alternating preconditioning idea is attractive and is a genuine departure from the λ-dependent preconditioners in prior work. If the main guarantee were correct, APGD would be the first damping-free preconditioned method with a linear-rate guarantee for noisy asymmetric over-parameterized matrix sensing; the experiments also cover a broad range of low-rank estimation tasks and the code is publicly available. However, the advertised near-optimal statistical error rests on a concentration step that has the wrong scaling under the stated measurement model, and the general contraction claimed for Lg/μ ≤ 9801 is not supported by the algebra in Lemma 9. The algorithmic framework remains potentially valuable, but the central statistical claim is not established as stated.","major_comments":[{"comment":"The concentration inequality used to control the noise term is not valid under the model stated in Theorem 2. Conditional on the noise vector s, the matrix M = ∑_{i=1}^m s_i A_i has iid entries with variance (∑_i s_i²)/m ≈ ν², so the standard spectral-norm bound for iid sub-Gaussian matrices gives ‖M‖₂² = Θ(ν² n) with high probability, not O(ν² n log n / m). The step marked (b) in the proof of Lemma 4 is the only source of the claimed floor E_opt = C_e ν² r n log n / m, so Theorem 2's near-optimal error bound is unsupported; with the usual scaling m ≍ r n, the asserted bound is smaller by a factor of m than the natural concentration scale of the noise term. Please state the precise version of Lemma 16 of [16] being invoked, including its normalization assumptions, or correct the noise model and the theorem accordingly.","section":"Appendix A, Lemma 4; Theorem 2"},{"comment":"The claimed range Lg/μ ≤ 9801 does not follow from the displayed formulas. For ρ = 0.1, Cρ = sqrt((1−3ρ²)/(1−ρ²)) = sqrt(0.97/0.99) < 1, so ζ = ((Cρ−1)Lg + (Cρ+1)μ)/√(2Lg) becomes negative as soon as Lg/μ > (1+Cρ)/(1−Cρ) ≈ 197.99. A negative ζ cannot be used as the lower-bound constant in Lemma 9; the subsequent derivation of Qg = (1 − 0.198 μ/Lg)² for Lg/μ ≤ 9801 is therefore invalid. This affects Theorem 3, the comparison in Table II, and the claim in Remark 4; the condition needs to be corrected or a different argument is required.","section":"Appendix E, Lemma 9 and Eq. (7)"}],"minor_comments":[{"comment":"The step-size condition in Theorem 2 is written as η ≤ 1/(1+δ_{2r+1}), but at the endpoint η = 1/(1+δ_{2r+1}) the coefficient C2 = η − (η/3)(1 + 2η(1+δ_{2r+1})) equals zero, so no contraction is obtained. The theorem should state the strict inequality η < 1/(1+δ_{2r+1}), matching the discussion in the text.","section":"Section III-B, Theorem 2"},{"comment":"In the expression for Z2, the first line writes ∇_L f(L_{t+1}, R_t), but the subsequent computation uses ∇_L f(L_t, R_t); the notation should be made consistent.","section":"Appendix B, proof of Lemma 2"},{"comment":"The final RIP step writes the lower bound in terms of f_c(L_{t+1}, R_t), while f_c(L_t, R_t) appears to be intended. The inequality is repairable, but as written it is confusing.","section":"Appendix C, proof of Lemma 3"},{"comment":"The equality ∥R_t(R_t^T R_t)^{†/2}∥_F² = r holds only when R_t has rank r; for a rank-deficient iterate the right-hand side should be rank(R_t) ≤ r. This is harmless for the proof but should be stated.","section":"Appendix A, Lemma 4 proof"}],"recommendation":"major_revision","confidential_remarks":"The noise-scaling issue in Lemma 4 is the most serious problem: it changes the advertised statistical guarantee, not just a proof detail. The algebraic error in Lemma 9/Theorem 3 is also load-bearing. I nevertheless do not view the algorithmic contribution as unsalvageable, since the damping-free alternating preconditioning scheme and the proof structure could support a corrected statement; hence major revision rather than reject."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the algorithm is genuinely interesting — alternating preconditioned updates remove the damping parameter and the experiments show it is fast and step-size robust. That part is worth paying attention to. But the main statistical guarantee in Theorem 2 is wrong by a factor of m, and Theorem 3 has an arithmetic failure. The paper needs serious revision before its theory is usable.\n\nThe proof skeleton is recognizable: a Lipschitz-like bound under RIP, a gradient lower bound via subspace angles, then a four-case noise analysis. In the noiseless case, the local convergence argument looks plausible. The extension to general RSC/RSM losses is a real ambition, and the paper honestly cites Jia et al. for the underlying alternating ScaledGD idea.\n\nThe soft spots are not cosmetic. Lemma 4 asserts ∥∑ s_i A_i∥₂² ≤ C ν² n log n / m for A_i with entries N(0,1/m) and s_i sub-Gaussian with proxy ν². But under exactly that model, M = ∑ s_i A_i has entries with variance ν², so its squared spectral norm is Θ(ν² n). The paper's bound is smaller by a factor m. Since E_opt = O(ν² r n log n / m) is built on this, the claimed near-optimal error is not supported — the true noise floor in the analysis is Θ(ν² r n). This is a load-bearing error, not a tuning issue.\n\nTheorem 3's displayed contraction (7) also fails as stated. With ρ = 0.1 and Lg/µ = 9801, the coefficient ζ in Lemma 9 is negative because the (Cρ−1)Lg term dominates once Lg/µ ≳ 197, so the claimed rate does not follow. The stated condition Lg/µ ≤ 9801 is simply wrong. The quoted subspace lemma (Lemma 7) looks misstated as well.\n\nCredit: the experiments are consistent, the code is released, and the paper does not oversell its novelty relative to [30]. But the experiments are small-scale, lack error bars, and omit the asymmetric PrecGD baseline [22]. I would not rely on the stated guarantees. For a referee, the paper is worth engaging with — the algorithm is plausible and the analysis errors are identifiable. As is, I would not accept; I would ask for a corrected statistical rate and a rework of the general theorem.","headline":"APGD is a nice damping-free alternating preconditioned method, but Theorem 2's noise floor is off by a factor of m and Theorem 3's algebra fails, so the theory needs major revision.","tokens_in":28976,"tokens_out":9617,"would_cite":false,"duration_ms":87310,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"By alternating updates of the two factor matrices, APGD removes the damping parameter from preconditioned gradient descent and reaches near-optimal error at a linear rate in noisy over-parameterized matrix sensing.","keywords":["matrix sensing","over-parameterization","preconditioned gradient descent","alternating minimization","low-rank matrix recovery","noisy measurements","linear convergence","restricted isometry property"],"falsifier":"On a Gaussian matrix sensing instance with $n_1=n_2=50$, true rank $r_\\star=5$, estimated rank $r=10$, $m=10nr$ measurements, condition number $\\kappa=100$, and noise variance chosen so that $E_{\\mathrm{opt}}$ is well below the initialization error, run APGD with the spectral initialization and step size $\\eta=0.99/(1+\\delta_{2r+1})$. If the relative error does not decrease linearly toward $O(\\nu^2 r n \\log n/m)$ within roughly 100 iterations, Theorem 2's guarantee fails on the regime it claims to cover.","tokens_in":27823,"feed_emoji":"📉","tokens_out":11871,"duration_ms":93755,"temperature":0.7,"pith_summary":"The paper tackles noisy matrix sensing in the over-parameterized regime, where the estimated rank exceeds the true rank and the target is recovered through an asymmetric factorization $X = LR^\\top$. It claims that updating $L$ and $R$ alternately, each with a Moore-Penrose preconditioner $(R^\\top R)^\\dagger$ or $(L^\\top L)^\\dagger$, eliminates the damping parameter $\\lambda$ that all previous preconditioned methods needed, while still converging linearly to near-optimal error $O(\\nu^2 r n \\log n / m)$. If correct, this removes the need for careful $\\lambda$-tuning in ill-conditioned, over-parameterized low-rank recovery and allows step sizes up to $1/(1+\\delta_{2r+1})$, independent of the condition number. The same alternating template is shown to give linear convergence for any loss that is rank-$2r$ restricted smooth and strongly convex, covering weighted PCA, 1-bit matrix completion, and matrix completion.","feed_headline":"Damping-free APGD converges linearly in noisy matrix sensing","feed_subtitle":"Updating L and R alternately removes λ-tuning and still reaches near-optimal error fast.","key_machinery":"The object carrying the argument is the alternating preconditioned update: $L_{t+1} = L_t - \\eta \\nabla_L f(L_t,R_t)(R_t^\\top R_t)^\\dagger$, followed by $R_{t+1} = R_t - \\eta \\nabla_R f(L_{t+1}, R_t)(L_{t+1}^\\top L_{t+1})^\\dagger$. The key step is Lemma 1: for the noiseless case, because the second factor is frozen during each subproblem, the per-subproblem Lipschitz constant is $1+\\delta_{2r+1}$ rather than an expression depending on a damping parameter $\\lambda$; the $DD^\\top$ term that made the Lipschitz constant blow up in simultaneous updates is avoided. The proof then works in the local norms induced by $P_{R_t}=R_t^\\top R_t$ and $P_{L_t}=L_t^\\top L_t$ (that is, $\\|A\\|_{R_t} = \\|A P_{R_t}^{1/2}\\|_F$ and its dual), uses an angle lower bound between the error matrix and the current factor's column space to get a Polyak-\\L{}ojasiewicz-type gradient lower bound (Lemma 3), and splits the noisy dynamics into cases where the gradient dominates the noise (linear contraction) and where the noise dominates (error already near the floor $E_{\\mathrm{opt}}$).","core_discovery":"The central result is Theorem 2: under Gaussian measurements, RIP constant $\\delta_{2r+1} \\le \\rho/(8\\kappa\\sqrt{r_\\star+r})$ with $\\rho \\le 1/2$, sample complexity $m \\gtrsim \\nu^2 r n \\log n / (\\sigma_{r_\\star}(X_\\star)\\rho^2\\delta_{2r+1}^2)$, and step size $\\eta \\le 1/(1+\\delta_{2r+1})$, APGD initialized by spectral initialization satisfies $\\|L_t R_t^\\top - X_\\star\\|_F^2 \\le \\max\\{C_\\delta Q_f^{2t}\\|L_0 R_0^\\top - X_\\star\\|_F^2, C_3 E_{\\mathrm{opt}}\\}$ with high probability, where $E_{\\mathrm{opt}} = C_e \\nu^2 r n \\log n / m$ and $Q_f<1$ is an explicit contraction factor. That is, the iterates converge linearly until they reach a near-optimal statistical error floor, and the error floor is independent of the condition number. The mechanism is the alternating update: because each factor is updated while the other is held fixed, the problematic quadratic term in the gradient that forced the damping parameter in ScaledGD($\\lambda$), PrecGD, and NoisyPrecGD simply disappears. The paper also establishes a general template (Theorem 3) in which any loss satisfying rank-$2r$ restricted smoothness and strong convexity inherits linear convergence under APGD.","pith_inferences":["If the damping-free property is really due to the alternating structure, the same idea should transfer to other bilinear factorizations (for instance, tensor or coupled-matrix decompositions) where simultaneous preconditioned updates also suffer from quadratic gradient terms; testing this would separate the principle from the specific low-rank sensing setting.","The linear-rate guarantee currently needs spectral initialization that improves with the condition number through $\\delta_{2r+1} \\le \\rho/(8\\kappa\\sqrt{r_\\star+r})$. A testable extension is to replace that initialization by, say, a few iterations of vanilla GD or a non-spectral warm start and check whether the contraction still holds numerically, which would widen the regime the theorem covers.","In the matrix completion experiments the paper initializes APGD randomly even though the theory assumes spectral initialization; quantifying the basin of linear convergence for random starts would turn a practical convenience into a provable property."],"forward_implications":["Noisy over-parameterized matrix sensing can be solved at a linear rate with no damping parameter to tune, removing the main practical obstacle in ScaledGD($\\lambda$), PrecGD, and NoisyPrecGD.","The allowed step size $\\eta \\le 1/(1+\\delta_{2r+1})$ is bounded only by the RIP constant, so APGD can take large steps even for ill-conditioned targets, where vanilla GD and small-initialization GD require steps of order $1/(\\kappa^2 \\sigma_1)$.","The recovery error $O(\\nu^2 r n \\log n / m)$ does not grow with the condition number, unlike the $\\kappa^2$ factor in small-initialization GD.","Because the factorization is asymmetric and no PSD constraint is imposed, the method applies to general rectangular low-rank matrices, not only symmetric positive semidefinite ones.","Any low-rank estimation task whose loss is rank-$2r$ restricted smooth and strongly convex inherits linear convergence under the same alternating-preconditioning template, including weighted PCA, matrix completion, and 1-bit matrix completion."],"supporting_citations":[{"why":"Introduces PrecGD for over-parameterized matrix sensing; its Proposition 23 supplies the spectral-initialization closeness used in Lemma 4 and its Lemma 13 gives the angle bounds that power Lemma 6.","marker":"[16]"},{"why":"Introduces ScaledGD and the restricted smoothness/strong convexity framework; Lemma 24 provides the factorization-norm comparison used to control the column-space angles.","marker":"[20]"},{"why":"NoisyPrecGD, the directly competing preconditioned method for noisy measurements; its need for a tuned damping parameter is the gap APGD closes, and it serves as the main theoretical and experimental benchmark.","marker":"[23]"},{"why":"Establishes the RIP for Gaussian measurement maps and the near-minimax noise floor $\\nu^2 r n \\log n/m$ that $E_{\\mathrm{opt}}$ matches.","marker":"[7]"},{"why":"Shows vanilla gradient descent in over-parameterized matrix sensing converges sublinearly; this is the baseline whose linear-rate improvement motivates the preconditioned approach.","marker":"[13]"},{"why":"Proves alternating ScaledGD attains global convergence without needing small step sizes; it is the direct inspiration for the damping-free alternating update.","marker":"[30]"},{"why":"Develops PrecGD for over-parameterized Burer-Monteiro factorization and supplies Lemma 15 used in the proof of the general Theorem 3.","marker":"[17]"}],"fun_headline_variants":["APGD ditches damping, converges linearly in matrix sensing","Alternating preconditioning accelerates noisy matrix recovery","Damping-free APGD: linear rate, larger steps, no λ tuning","Over-parameterized matrix sensing: APGD removes λ, faster convergence","APGD: alternating updates yield linear convergence without damping"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole convergence proof rests on the spectral initialization getting within distance $\\|X_0 - X_\\star\\|_F \\le \\rho\\,\\sigma_{r_\\star}(X_\\star)$ with $\\rho \\le 1/2$, and guaranteeing that closeness forces the number of measurements to grow with the square of the condition number; if the initialization is not that close, the linear rate is not established.","fun_headline_variants_meta":{"raw":{"variants":["APGD ditches damping, converges linearly in matrix sensing","Alternating preconditioning accelerates noisy matrix recovery","Damping-free APGD: linear rate, larger steps, no λ tuning","Over-parameterized matrix sensing: APGD removes λ, faster convergence","APGD: alternating updates yield linear convergence without damping"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000263,"raw_usage":{"total_tokens":1753,"prompt_tokens":1250,"completion_tokens":503,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":866,"completion_tokens_details":{"reasoning_tokens":419}},"tokens_in":866,"tokens_out":503,"duration_ms":5251,"temperature":1.0,"reasoning_tokens":419,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T18:54:44.742334+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a Gaussian matrix sensing instance with $n_1=n_2=50$, true rank $r_\\star=5$, estimated rank $r=10$, $m=10nr$ measurements, condition number $\\kappa=100$, and noise variance chosen so that $E_{\\mathrm{opt}}$ is well below the initialization error, run APGD with the spectral initialization and step size $\\eta=0.99/(1+\\delta_{2r+1})$. If the relative error does not decrease linearly toward $O(\\nu^2 r n \\log n/m)$ within roughly 100 iterations, Theorem 2's guarantee fails on the regime it claims to cover.","supporting_citations":[{"cited_title":"Preconditioned gradient descent for over-parameterized nonconvex matrix factorization,","cited_arxiv_id":null,"evidence_quote":"Introduces PrecGD for over-parameterized matrix sensing; its Proposition 23 supplies the spectral-initialization closeness used in Lemma 4 and its Lemma 13 gives the angle bounds that power Lemma 6."},{"cited_title":"Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent,","cited_arxiv_id":null,"evidence_quote":"Introduces ScaledGD and the restricted smoothness/strong convexity framework; Lemma 24 provides the factorization-norm comparison used to control the column-space angles."},{"cited_title":"Fast and accurate estimation of low-rank matrices from noisy measurements via preconditioned non- convex gradient descent,","cited_arxiv_id":null,"evidence_quote":"NoisyPrecGD, the directly competing preconditioned method for noisy measurements; its need for a tuned damping parameter is the gap APGD closes, and it serves as the main theoretical and experimental benchmark."},{"cited_title":"Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements,","cited_arxiv_id":null,"evidence_quote":"Establishes the RIP for Gaussian measurement maps and the near-minimax noise floor $\\nu^2 r n \\log n/m$ that $E_{\\mathrm{opt}}$ matches."},{"cited_title":"On the computational and statistical complexity of over-parameterized matrix sensing,","cited_arxiv_id":null,"evidence_quote":"Shows vanilla gradient descent in over-parameterized matrix sensing converges sublinearly; this is the baseline whose linear-rate improvement motivates the preconditioned approach."},{"cited_title":"Preconditioning matters: Fast global convergence of non-convex matrix factorization via scaled gradient descent,","cited_arxiv_id":null,"evidence_quote":"Proves alternating ScaledGD attains global convergence without needing small step sizes; it is the direct inspiration for the damping-free alternating update."},{"cited_title":"Preconditioned gradient descent for overparameterized nonconvex burer–monteiro factorization with global optimality certification,","cited_arxiv_id":null,"evidence_quote":"Develops PrecGD for over-parameterized Burer-Monteiro factorization and supplies Lemma 15 used in the proof of the general Theorem 3."}],"review_version":1}