Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method
This addresses optimization challenges in sparse matrix recovery for applications like machine learning and signal processing, offering an incremental improvement in convergence guarantees for momentum-based methods.
The paper tackles non-convex, non-smooth optimization with rank regularization by proposing a proximal gradient descent method accelerated with a novel support set projection on singular values, achieving an O(1/t^2) convergence rate matching Nesterov's optimal rate for smooth convex problems and ensuring strict sparsity with monotonically shrinking support sets.
We study a class of non-convex and non-smooth problems with \textit{rank} regularization to promote sparsity in optimal solution. We propose to apply the proximal gradient descent method to solve the problem and accelerate the process with a novel support set projection operation on the singular values of the intermediate update. We show that our algorithms are able to achieve a convergence rate of $O(\frac{1}{t^2})$, which is exactly same as Nesterov's optimal convergence rate for first-order methods on smooth and convex problems. Strict sparsity can be expected and the support set of singular values during each update is monotonically shrinking, which to our best knowledge, is novel in momentum-based algorithms.