arXiv:2602.05887cs.LGmath.OC2026-02被引 1

提出可证明逃离局部最优的确定性方法,无需复杂升维计算。

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

  • 设计模拟升维方向的投影机制,直接在原空间逃逸局部极小。
  • 理论保证从任意局部极小值严格下降目标函数,收敛到全局最优。
  • 适合研究非凸优化、低秩恢复的学者,尤其关注可证明性能者。

低秩矩阵感知是基础但极具挑战性的非凸问题,其优化景观常包含大量虚假局部极小值,导致基于梯度的优化器难以收敛至全局最优。近期研究表明,通过张量升维实现过参数化,可将这些局部极小值转化为严格鞍点,这一发现也部分解释了现代机器学习中大规模模型提升泛化与性能的原因。受此启发,我们提出模拟预言方向(SOD)逃逸机制,不实际进行问题升维(因其计算不可行),而是模拟过参数空间的景观与逃逸方向。本质上,该方法将过参数化空间中的逃逸方向投影回原始参数空间,确保从现有局部极小值出发能严格降低目标函数值。据我们所知,这是首个可证明逃逸虚假局部极小的确定性框架,且无需随机扰动或启发式估计。数值实验表明,该框架可靠地逃离局部极小,并促进收敛至全局最优,同时计算开销远低于显式张量过参数化。我们认为该框架对矩阵感知之外的非凸优化具有重要意义,展示了模拟过参数化如何用于驯服复杂优化景观。

原文摘要 · Abstract (English)

Low-rank matrix sensing is a fundamental yet challenging nonconvex problem whose optimization landscape typically contains numerous spurious local minima, making it difficult for gradient-based optimizers to converge to the global optimum. Recent work has shown that over-parameterization via tensor lifting can convert such local minima into strict saddle points, an insight that also partially explains why massive scaling can improve generalization and performance in modern machine learning. Motivated by this observation, we propose a Simulated Oracle Direction (SOD) escape mechanism that simulates the landscape and escape direction of the over-parametrized space, without resorting to actually lifting the problem, since that would be computationally intractable. In essence, we designed a mathematical framework to project over-parametrized escape directions onto the original parameter space to guarantee a strict decrease of objective value from existing local minima. To the best of our knowledge, this represents the first deterministic framework that could escape spurious local minima with guarantee, especially without using random perturbations or heuristic estimates. Numerical experiments demonstrate that our framework reliably escapes local minima and facilitates convergence to global optima, while incurring minimal computational cost when compared to explicit tensor over-parameterization. We believe this framework has non-trivial implications for nonconvex optimization beyond matrix sensing, by showcasing how simulated over-parameterization can be leveraged to tame challenging optimization landscapes.

非凸优化矩阵感知全局收敛

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。