Abstract:We study gradient descent for rank-1 matrix factorization through a certificate-based viewpoint. The central object is a parameterized quadratic certificate $I(\delta;\,\cdot)$ whose level sets shrink along the dynamics, thereby inducing a monotone state parameter $\delta_t$. In the certified regime, this mechanism yields convergence to a global minimizer; in the post-critical regime, it forces trajectories toward a terminal balanced manifold.
To explain the origin of these certificates, we formulate a state-dependent Lyapunov framework based on structural axioms. Within this framework, the scalar certificate is uniquely determined, and the same local Lagrange analysis constrains the signal and noise blocks of rank-1 extensions. Thus, the certificates arise from the monotonicity structure of the dynamics, rather than from ad hoc algebraic constructions.
We also provide numerical evidence beyond the proved cases. For the 2-dimensional rank-1 approximation problem $X=\mathrm{diag}(1,\sigma)$ with $\sigma\in(0,1)$, the experiments are consistent with the existence of a $C^1$ admissible certificate branch. For the quartic-augmented scalar loss $\frac12(ab-1)^2+\mu(ab-1)^4$, the same scalar certificate remains predictive for several values of $\mu$ after choosing an empirical threshold. These experiments suggest that the state-dependent Lyapunov method may extend beyond the settings proved in this paper.
| Subjects: | Numerical Analysis (math.NA); Machine Learning (cs.LG); Optimization and Control (math.OC) |
| Cite as: | arXiv:2604.26993 [math.NA] |
| (or arXiv:2604.26993v1 [math.NA] for this version) | |
| https://doi.org/10.48550/arXiv.2604.26993 arXiv-issued DOI via DataCite (pending registration) |
From: Jaehong Moon [view email]
[v1]
Tue, 28 Apr 2026 22:43:16 UTC (3,689 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。