Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness

Runze Shi; Ziye Ma

cs.LGOct 13, 2026

Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness

Authors: Runze Shi, Ziye Ma

Organizations: City University of Hong Kong

Abstract

Over-parameterization is ubiquitous in modern machine learning, yet its effect on robustness remains poorly understood. We study this question in matrix sensing, a canonical non-convex problem that can also be viewed, under an appropriate parameterization, as training a two-layer quadratic neural network. We develop a rank-aware robustness theory for the Burer-Monteiro factorization when the search rank k may exceed the target rank r_star, thereby capturing over-parameterization. Our analysis shows that robustness depends jointly on the degree of over-parameterization and the local geometry of the attained second-order stationary point: increasing k generally worsens sensitivity, but stationary points with the same search rank can exhibit substantially different robustness. Motivated by this observation, we propose a trajectory-aware algorithm that uses spectral balancing and randomized sketching to steer optimization toward less sensitive solutions. In matrix-sensing experiments, the method reduces paired sensitivity by 18-29 percent for isotropic operators and 87-89 percent for weak-tail operators, without degrading reconstruction accuracy. These results demonstrate that parameter count alone does not determine robustness and identify solution geometry and the optimization trajectory as important levers for improving it.

Figures & tables

g_{t}=2G_{t}X_{t}+\alpha_{0}c_{t}g_{{\rm inv},t}+\beta_{0}c_{t}g_{-,t}.

Algorithm 1 Decayed Anchor-Free Balanced Guidance

Protocol	Operator	Ratio	$\Delta_{\mathsf{R}}$	$\mathsf{E}_{\rm rel}$	Joint
E2E	Gauss.	0.788	21.2%	0.887	23/25
E2E	Radem.	0.785	21.5%	0.863	25/25
E2E	Weak-tail	0.180	82.0%	0.625	25/25
Shared	Gauss.	0.781	21.9%	0.887	23/25
Shared	Radem.	0.771	22.9%	0.863	25/25
Shared	Weak-tail	0.117	88.3%	0.625	25/25

Table 1: Algorithm 1 relative to Plain. Ratio is the median instancewise response ratio

\mathsf{Q}_{p,s}

, and

\Delta_{\mathsf{R}}=1-\operatorname{median}_{s}\mathsf{Q}_{p,s}

. Joint counts instances in which both response and reconstruction improve. Each row contains

25

configuration–seed instances.

Figure 1: Distributions of the Algorithm 1/Plain Paired Sensitivity Ratio (left) and reconstruction-error ratios (right) under E2E (top) and Shared (bottom) initialization. Smaller values favor Algorithm 1; the dashed lines mark

20\%

response improvement and reconstruction parity. The right panels coincide because both protocols use the same noisy-data runs.

Figure 2: Conditional Shared comparison relative to Plain. Each point is one configuration–seed instance. The horizontal line marks a

20\%

reduction in paired sensitivity, and the vertical line marks reconstruction parity; the lower-left region improves both metrics.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Parameter	Value
Measurements	$m=6nk$
Formal seeds	$15,66,102,999,1325$
Native iterations	at most $220$
Algorithm 1/Plain learning rate	$0.035$
Relative perturbation norm	$0.08$
Paired perturbations	$3$

Appendix

Table 2: Common settings for the formal matrix-sensing experiments.

Operator	$(n,r_{\star},k)$	$\mathsf{Q}_{\rm E2E}$	$\mathsf{Q}_{\rm Shared}$	$\mathsf{E}_{\rm rel}$
Gauss.	$(50,2,5)$	.8323	.8161	.9375
Gauss.	$(75,3,6)$	.8269	.8123	.9162
Gauss.	$(100,3,8)$	.7883	.7780	.8874
Gauss.	$(125,4,10)$	.7651	.7516	.8864
Gauss.	$(150,5,12)$	.7483	.7378	.8739
Radem.	$(50,2,5)$	.8031	.7991	.9322

Appendix

Table 3: Configuration-level medians for Algorithm 1 relative to Plain. Each row aggregates five seeds. Values below one favor Algorithm 1 .

Figure 3: Terminal spectral diagnostics for Algorithm 1 relative to Plain. The panels show

\rho_{\rm A1}^{-}/\rho_{\rm Plain}^{-}

and

\lambda_{k}^{\rm A1}/\lambda_{k}^{\rm Plain}

, respectively. Each operator pools

25

matched instances. Smaller values favor Algorithm 1 for

\rho^{-}

, whereas larger values favor it for

\lambda_{k}

. E2E and Shared use the same primary noisy-data runs, so these diagnostics coincide and are shown only once.

Figure 4: L1-SubGM relative to Plain under E2E (top) and Shared (bottom). From upper left to lower right, the panels show

\mathsf{Q}

\mathsf{E}_{\rm rel}

, the

\rho^{-}

ratio, and the

\lambda_{k}

ratio. The dashed references are

\mathsf{Q}=0.8

and one for the other metrics. The

\rho^{-}

panel uses a logarithmic scale because of the weak-tail range.

Figure 5: ScaledSM relative to Plain under E2E (top) and Shared (bottom), using the same four diagnostics and reference lines as Figure 4 . Each operator contains

25

matched configuration–seed instances.

Figure 6: GNMR relative to Plain under E2E (top) and Shared (bottom), using the same four diagnostics and reference lines as Figure 4 . Each operator contains

25

matched configuration–seed instances.

$n$	Operator	$\mathsf{Q}_{\rm E2E}$	$\Delta_{\rm E2E}$	$\mathsf{Q}_{\rm Sh}$	$\Delta_{\rm Sh}$	$\mathsf{E}_{\rm rel}$	$\rho^{-}_{\rm Plain}$	$\rho^{-}_{\rm A1}$	Joint
250	Gauss.	0.715	28.5%	0.710	29.0%	0.821	0.2624	0.4093	5/5
250	Radem.	0.712	28.8%	0.706	29.4%	0.824	0.2543	0.3954	5/5
250	Weak-tail	0.307	69.3%	0.125	87.5%	0.668	0.0077	0.0084	5/5
500	Gauss.	0.713	28.7%	0.703	29.7%	0.823	0.1826	0.2850	5/5
500	Radem.	0.722	27.8%	0.702	29.8%	0.834	0.1951	0.3058	5/5
500	Weak-tail	0.385	61.5%	0.120	88.0%	0.586	0.0029	0.0061	5/5

Appendix

Table 4: Formal large-scale comparison of Algorithm 1 with Plain over five seeds per

(n,\mathrm{operator})

cell. The quantities

\mathsf{Q}_{\rm E2E}

and

\mathsf{Q}_{\rm Sh}

are the median instancewise relative paired critical-point sensitivities under E2E and Shared observed-spectral initialization. The corresponding sensitivity reductions are

\Delta_{\rm E2E}=100(1-\mathsf{Q}_{\rm E2E})

and

\Delta_{\rm Sh}=100(1-\mathsf{Q}_{\rm Sh})

. The reconstruction ratio is common to both protocols because their main noisy-data runs are identical. The two

\rho^{-}

columns report the median terminal normal-curvature ratios of Plain and Algorithm 1; these values are likewise common to the two protocols up to numerical precision. Joint counts seeds for which both

\mathsf{Q}<1

and

\mathsf{E}_{\rm rel}<1

; all cells have

5/5

under both protocols.

Figure 7: Formal large-scale comparison of Algorithm 1 with Plain. Each row contains the five seeds for one fixed

(n,\mathrm{operator})

cell. The quantities

\mathsf{Q}_{\rm E2E}

and

\mathsf{Q}_{\rm Sh}

are the median instancewise relative paired critical-point sensitivities under E2E and Shared observed-spectral initialization. Their corresponding sensitivity reductions are

\Delta_{\rm E2E}=100(1-\mathsf{Q}_{\rm E2E})

and

\Delta_{\rm Sh}=100(1-\mathsf{Q}_{\rm Sh})

. The reconstruction ratio

\mathsf{E}_{\rm rel}

and the terminal

\rho^{-}_{\rm Plain}

and

\rho^{-}_{\rm A1}

values are common to both protocols because their main noisy-data runs are identical. Joint counts seeds for which both

\mathsf{Q}<1

and

\mathsf{E}_{\rm rel}<1

; every row has

5/5

under both protocols. Pooling the three dimensions gives

15/15

joint improvements for each operator and

45/45

per protocol.

Figure 8: Formal large-scale comparison under Shared observed-spectral initialization. Only the paired-sensitivity panel changes relative to Figure 7 ; reconstruction and terminal spectral diagnostics coincide because the two protocols use the same main noisy-data solutions.

Figure 9: Robust validation performance under fixed unit-

\ell_{2}

logit-objective perturbations. Panel (a) reports noisy validation accuracy for plain and scaled-active LoRA. Panel (b) reports the paired scaled-active-minus-plain accuracy difference. Each point is the mean over three training seeds, after first averaging three fixed perturbation directions within each seed. Error bars denote sample standard deviations across training seeds.

Explore similar work

Sep 29, 2026

Strict-Saddle Landscapes and Multi-Rank Geometry in Low-Tubal-Rank Tensor Sensing

We study the optimization landscape of low-tubal-rank tensor sensing through a balanced factorization. Under a tubal restricted isometry condition, we establish a quantitative strict-saddle landscape with no spurious local minima for arbitrary Fourier multi-rank profiles. We further show that the local geometry depends on the Fourier-slice ranks rather than the tubal rank alone. Uniform ranks yield quadratic growth transverse to the solution orbit, whereas nonuniform ranks produce quartically flat directions through hidden frequency-wise overparameterization, even when the factor width equals the exact tubal rank. Numerical experiments illustrate the global optimization behavior and the contrasting local geometries.

Eugene Agyei-Kodie, Longxiu Huang, Shuang Li +1

Department of Mathematics, Michigan State University, 619 Red Cedar, East Lansing, 48824, MI, USA. · Department of Computational Mathematics, Science and Engineering, Michigan State University, 428 S Shaw Ln, East Lansing, 48824, MI, USA. · Department of Electrical and Computer Engineering, Iowa State University, 2520 Osborn Dr, Ames, 50011, IA, USA.

Nonconvex Optimization Optimization Convergence Analysis Tensor Decomposition

Ask PDF

Jun 30, 2026

Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics

Low-rank matrix optimization is often carried out via the Burer-Monteiro (BM) formulation, but choosing the factorization rank

r

is delicate and can substantially slow optimization. We propose a unified framework, termed direction-magnitude decomposition (DMD), that decomposes the optimization variable to improve optimization efficiency even when the target rank is unknown. We develop two DMD-based approaches and establish their theoretical advantages on the canonical problem of matrix factorization. The first, overparameterized DMD, uses a rank

r

larger than necessary and enjoys faster convergence as

r

increases. The second, recursive DMD, is motivated by the incremental eigenpair learning, or saddle-to-saddle, behavior of overparameterized DMD. It achieves lower memory and computational costs, complementing overparameterized DMD. Both approaches are exponentially faster than gradient descent applied to the BM formulation. Numerical experiments on matrix factorization, sensing, and completion corroborate our theoretical findings and demonstrate the practical effectiveness of DMD.

Yudong Wei, Liang Zhang, Bingcong Li +1

Department of Mathematics, ETH Zurich, Zurich, Switzerland · Department of Computer Science, ETH Zurich, Zurich, Switzerland

Low-Rank Matrix Decomposition Nonconvex Optimization Matrix Optimization Matrix Factorization Gradient Descent Dynamics

Ask PDF

Sep 15, 2026

Near-Optimal Nonconvex Matrix Completion

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an

n\times n

matrix of rank

r

with incoherence parameter

μ

and condition number

κ

, the two methods achieve exact recovery with high probability from

O(μnr\log n\log(nκ))

and

O(μnr\log n\log(2μrκ))

observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.

Jian-Feng Cai, Xiliang Lu, Juntao You

Department of Mathematics, Hong Kong University of Science and Technology. · School of Mathematics and Statistics, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China. · School of Artificial Intelligence, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China.

Riemannian Optimization Nonconvex Optimization Matrix Completion

Ask PDF