← Back to all news
Hugging Face Trending Papers

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

The paper investigates how over‑parameterization affects robustness in matrix sensing, a non‑convex problem equivalent to training a two‑layer quadratic neural network. It introduces a rank‑aware robustness theory for the Burer‑Monteiro factorization, showing that robustness depends on both the degree of over‑parameterization and the local geometry of second‑order stationary points. Based on these insights, the authors propose a trajectory‑aware algorithm that steers optimization toward less sensitive solutions, achieving significant reductions in paired sensitivity in experiments without harming reconstruction accuracy.

Related stories

arXiv Machine Learning
Aug 20

Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Lifting

The paper introduces a deterministic Simulated Oracle Direction (SOD) framework that enables escaping spurious local minima in non‑convex low‑rank matrix sensing without explicit tensor lifting. By projecting over‑parameterized escape directions back into the original parameter space, the method guarantees a strict decrease in objective value from existing local minima. Experiments show reliable escape from local minima and convergence to global optima with minimal computational overhead compared to explicit over‑parameterization.

By Tianqi Shen, Jinji Yang, Junze He, Kunhan Gao, Zeyu Zheng, Ziye Ma
More like this →
arXiv Machine Learning
1d ago

Improving the Optimization Landscape of Matrix Completion with $\epsilon$-close Surrogates

The paper proposes a new approach to matrix completion by adding small (ε-level) perturbations to the nullspace of the observation mask, creating noisy surrogates that remain close to the true matrix. These surrogates satisfy a restricted isometry property, enabling the use of tensor methods with theoretical guarantees. The authors provide quantitative recovery guarantees under independent observation assumptions, without requiring explicit sampling rate or incoherence conditions.

By Ziye Ma
More like this →
arXiv Machine Learning
Aug 19

Online Generalized Sparse Regression: How Does Overparametrization Help?

The paper introduces an online generalized-sparsity-constrained regression framework that addresses key challenges in online sparse regression, such as dynamic regularization, memory usage, and real-time computation. It proposes an efficient online hard‑thresholding algorithm that performs closed‑form updates using only summary statistics, achieving global convergence at optimal statistical rates when the projection set is overparameterized. Numerical experiments show the method consistently outperforms existing alternatives in online cardinality‑constrained linear regression and low‑rank matrix sensing.

By Shuoguang Yang, Qiang Sun
efficiencybenchmarks
More like this →