First-order Optimization Methods with Generalized Smoothness for Low-rank Matrix Factorization
Abstract
This paper studies several first-order methods for low-rank matrix minimization in the Burer--Monteiro form, where the target matrix is represented as the product of a nonnegative factor matrix and its transpose. Such a factorization destroys convexity of the objective function and global Lipschitz continuity of the gradient. We prove that for a quadratic objective function that is strongly convex only on the subspace of symmetric matrices, the Burer-Monteiro factorized objective possesses generalized smoothness with a fractional exponent 2/3. For a quadratic objective, the generalized smoothness property requires positive definiteness of the operator A only on the subspace of symmetric matrices, which relaxes the assumptions of Dragomir et al. On this basis, three methods are proposed: an adaptive gradient descent method with Armijo backtracking; an unconstrained SafeAdam method combining the Adam direction with a descent-angle certificate and a fallback to the normalized gradient; and a certified projected version for the nonnegativity constraint. Global convergence and explicit convergence rates for the proposed methods have been proved. The obtained convergence rate is better than the convergence rate of ordinary unaccelerated gradient descent in the case of a sufficiently large gradient. In the small-gradient regime, the convergence guarantee is of square-root type, and the corresponding complexity scales as the inverse square of the desired accuracy. In the large-gradient regime, the convergence guarantee is of three-quarters type, and the corresponding complexity is proportional to the inverse of the accuracy raised to the power of 4/3. Experiments on SymNMF using the TDT2, Reuters and CBCL datasets, which are standard benchmarks for document and image clustering, show that the methods match or outperform Dyn-NoLips without tuning the relative-smoothness kernel parameters.
Related
- Gibbs Sampling for Bayesian Generalized Poisson Matrix Factorization
- Localize, Restart, Accelerate: Stochastic Optimization under Generalized Smoothness
- Efficient Convex Optimization Methods for State-Space Heartbeat Dynamics Models with Gamma Generalized Linear Models
- Optimal Parameter-Free Second-order Acceleration with Inexact Hessians under Generalized Smoothness
- Acceleration Survives Heavy Tails and Generalized Smoothness
BibTeX
@misc{bidanets2026firstorder,
title = {{First-order Optimization Methods with Generalized Smoothness for Low-rank Matrix Factorization}},
author = {A. V. Bidanets and F. S. Stonyakin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19059},
eprint = {2610.19059},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19059},
}
RIS
TY - UNPB
TI - First-order Optimization Methods with Generalized Smoothness for Low-rank Matrix Factorization
AU - A. V. Bidanets
AU - F. S. Stonyakin
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.19059
UR - https://arxiv.org/abs/2610.19059
AB - This paper studies several first-order methods for low-rank matrix minimization in the Burer--Monteiro form, where the target matrix is represented as the product of a nonnegative factor matrix and its transpose. Such a factorization destroys convexity of the objective function and global Lipschitz continuity of the gradient. We prove that for a quadratic objective function that is strongly convex only on the subspace of symmetric matrices, the Burer-Monteiro factorized objective possesses generalized smoothness with a fractional exponent 2/3. For a quadratic objective, the generalized smoothness property requires positive definiteness of the operator A only on the subspace of symmetric matrices, which relaxes the assumptions of Dragomir et al. On this basis, three methods are proposed: an adaptive gradient descent method with Armijo backtracking; an unconstrained SafeAdam method combining the Adam direction with a descent-angle certificate and a fallback to the normalized gradient; and a certified projected version for the nonnegativity constraint. Global convergence and explicit convergence rates for the proposed methods have been proved. The obtained convergence rate is better than the convergence rate of ordinary unaccelerated gradient descent in the case of a sufficiently large gradient. In the small-gradient regime, the convergence guarantee is of square-root type, and the corresponding complexity scales as the inverse square of the desired accuracy. In the large-gradient regime, the convergence guarantee is of three-quarters type, and the corresponding complexity is proportional to the inverse of the accuracy raised to the power of 4/3. Experiments on SymNMF using the TDT2, Reuters and CBCL datasets, which are standard benchmarks for document and image clustering, show that the methods match or outperform Dyn-NoLips without tuning the relative-smoothness kernel parameters.
ER -