Generalized majorization-minimization for non-convex optimization

• Main Authors: ZHANG, Hu, ZHOU, Pan, YANG, Yi, FENG, Jiashi
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Machine Learning: Data Mining; Computer Vision: Big Data and Large Scale Methods; Graphics and Human Computer Interfaces
• Online Access: https://ink.library.smu.edu.sg/sis_research/9006; https://ink.library.smu.edu.sg/context/sis_research/article/10009/viewcontent/2019_IJCAI_MM.pdf
• Institution: Singapore Management University

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.