Generalized majorization-minimization for non-convex optimization

Zhang, H; Zhou, P; Yang, Y; Feng, J

Generalized majorization-minimization for non-convex optimization

Zhang, H Zhou, P Yang, Y

Feng, J

Permalink

Publication Type:: Conference Proceeding
Citation:: IJCAI International Joint Conference on Artificial Intelligence, 2019, 2019-August pp. 4257 - 4263
Issue Date:: 2019-01-01

Recently Added

	Filename	Size
	IJCAI_19_final_OPUS version.pdf	797.9 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is new to OPUS and is not currently available.

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, H	en_US
dc.contributor.author	Zhou, P	en_US
dc.contributor.author	Yang, Y https://orcid.org/0000-0001-5528-0546	en_US
dc.contributor.author	Feng, J	en_US
dc.date.accessioned	2020-06-11T06:51:12Z
dc.date.accessioned	2020-06-11T06:51:13Z
dc.date.available	2020-06-11T06:51:12Z
dc.date.available	2020-06-11T06:51:13Z
dc.date.issued	2019-01-01	en_US
dc.identifier.citation	IJCAI International Joint Conference on Artificial Intelligence, 2019, 2019-August pp. 4257 - 4263	en_US
dc.identifier.isbn	9780999241141	en_US
dc.identifier.issn	1045-0823	en_US
dc.identifier.uri	http://hdl.handle.net/10453/141342
dc.description.abstract	© 2019 International Joint Conferences on Artificial Intelligence. All rights reserved. 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 nonconvex logistic regression and sparse PCA demonstrate the advantageous efficiency of the proposed algorithm and validate our theoretical results.	en_US
dc.relation.ispartof	IJCAI International Joint Conference on Artificial Intelligence	en_US
dc.rights	info:eu-repo/semantics/restrictedAccess
dc.title	Generalized majorization-minimization for non-convex optimization	en_US
dc.type	Conference Proceeding
utslib.citation.volume	2019-August	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
pubs.organisational-group	/University of Technology Sydney/Students
utslib.copyright.status	recently_added	*
pubs.publication-status	Published	en_US
pubs.volume	2019-August	en_US

Abstract:

© 2019 International Joint Conferences on Artificial Intelligence. All rights reserved. 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 nonconvex logistic regression and sparse PCA demonstrate the advantageous efficiency of the proposed algorithm and validate our theoretical results.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/141342