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

Strict-Saddle Landscapes and Multi-Rank Geometry in Low-Tubal-Rank Tensor Sensing
Sep 29, 2026Eugene Agyei-Kodie, Longxiu Huang, Shuang Li +1Nonconvex Optimization Optimization Convergence Analysis
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.
Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics
Jun 30, 2026Yudong Wei, Liang Zhang, Bingcong Li +1Low-Rank Matrix Decomposition Nonconvex Optimization
Department of Mathematics, ETH Zurich, Zurich, Switzerland · Department of Computer Science, ETH Zurich, Zurich, Switzerland
Near-Optimal Nonconvex Matrix Completion
Sep 15, 2026Jian-Feng Cai, Xiliang Lu, Juntao YouRiemannian Optimization Nonconvex Optimization
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.

Sep 29, 2026J/K move · Enter open · S save

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

Eugene Agyei-Kodie, Longxiu Huang, Shuang Li, Xiao Liang

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

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

Near-Optimal Nonconvex Matrix Completion