Generalized Majorization-Minimization for Non-Convex Optimization

Generalized Majorization-Minimization for Non-Convex Optimization

Hu Zhang, Pan Zhou, Yi Yang, Jiashi Feng

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 4257-4263. https://doi.org/10.24963/ijcai.2019/591

Majorization-Minimization (MM) algorithms optimize an objective function by iteratively minimizing its majorizing surrogate and offer attractively fast convergence rate for convex problems. However, their convergence behaviors for non-convex problems remain unclear. In this paper, we propose a novel MM surrogate function from strictly upper bounding the objective to bounding the objective in expectation. With this generalized surrogate conception, we develop a new optimization algorithm, termed SPI-MM, that leverages the recent proposed SPIDER for more efficient non-convex optimization. We prove that for finite-sum problems, the SPI-MM algorithm converges to an stationary point within deterministic and lower stochastic gradient complexity. To our best knowledge, this work gives the first non-asymptotic convergence analysis for MM-alike algorithms in general non-convex optimization. Extensive empirical studies on non-convex logistic regression and sparse PCA demonstrate the advantageous efficiency of the proposed algorithm and validate our theoretical results.
Keywords:
Machine Learning: Data Mining
Computer Vision: Big Data and Large Scale Methods