2025/05/01 by Ouyang, Wenqing, Pong, Ting Kei, Yue, Man-Chung · 1 citation
#FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2505.00349
This paper studies the relationship between the nuclear norm-regularized minimization problem, which minimizes the sum of a C2 function h and a positive multiple of the nuclear norm, and its factorized problem obtained by the Burer-Monteiro technique. We first prove that every second-order stationary point of the factorized problem corresponds to an approximate stationary point of its non-factorized counterpart, and those rank-deficient ones correspond to global minimizers of the latter problem when h is additionally convex, conforming with the observations in [2, 15]. Next, discarding the rank condition on the second-order stationary points but assuming the convexity and Lipschitz differentiability of h, we characterize, with respect to some natural problem parameters, when every second-order stationary point of the factorized problem is a global minimizer of the corresponding nuclear norm-regularized problem. More precisely, we subdivide the class of Lipschitz differentiable convex C2 functions into subclasses according to those natural parameters and characterize when each subclass consists solely of functions h such that every second-order stationary point of the associated factorized model is a global minimizer of the nuclear norm regularized model. In particular, explicit counterexamples are established when the characterizing condition on the said parameters is violated.