Minimization by Incremental Stochastic Surrogate Optimization for Large Scale Nonconvex Problems

Belhal Karimi, Hoi-To Wai, Eric Moulines, Ping Li
Proceedings of The 33rd International Conference on Algorithmic Learning Theory, PMLR 167:606-637, 2022.

Abstract

Many constrained, nonconvex and nonsmooth optimization problems can be tackled using the majorization-minimization (MM) method which alternates between constructing a surrogate func- tion which upper bounds the objective function, and then minimizing this surrogate. For problems which minimize a finite sum of functions, a stochastic version of the MM method selects a batch of functions at random at each iteration and optimizes the accumulated surrogate. However, in many cases of interest such as variational inference for latent variable models, the surrogate functions are expressed as an expectation. In this contribution, we propose a doubly stochastic MM method based on Monte Carlo approximation of these stochastic surrogates. We establish asymptotic and non-asymptotic convergence of our scheme in a constrained, nonconvex, nonsmooth optimization setting. We apply our new framework for inference of logistic regression model with missing data and for variational inference of Bayesian variants of LeNet-5 and Resnet-18 on benchmark datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v167-karimi22a, title = {Minimization by Incremental Stochastic Surrogate Optimization for Large Scale Nonconvex Problems}, author = {Karimi, Belhal and Wai, Hoi-To and Moulines, Eric and Li, Ping}, booktitle = {Proceedings of The 33rd International Conference on Algorithmic Learning Theory}, pages = {606--637}, year = {2022}, editor = {Dasgupta, Sanjoy and Haghtalab, Nika}, volume = {167}, series = {Proceedings of Machine Learning Research}, month = {29 Mar--01 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v167/karimi22a/karimi22a.pdf}, url = {https://proceedings.mlr.press/v167/karimi22a.html}, abstract = {Many constrained, nonconvex and nonsmooth optimization problems can be tackled using the majorization-minimization (MM) method which alternates between constructing a surrogate func- tion which upper bounds the objective function, and then minimizing this surrogate. For problems which minimize a finite sum of functions, a stochastic version of the MM method selects a batch of functions at random at each iteration and optimizes the accumulated surrogate. However, in many cases of interest such as variational inference for latent variable models, the surrogate functions are expressed as an expectation. In this contribution, we propose a doubly stochastic MM method based on Monte Carlo approximation of these stochastic surrogates. We establish asymptotic and non-asymptotic convergence of our scheme in a constrained, nonconvex, nonsmooth optimization setting. We apply our new framework for inference of logistic regression model with missing data and for variational inference of Bayesian variants of LeNet-5 and Resnet-18 on benchmark datasets.} }
Endnote
%0 Conference Paper %T Minimization by Incremental Stochastic Surrogate Optimization for Large Scale Nonconvex Problems %A Belhal Karimi %A Hoi-To Wai %A Eric Moulines %A Ping Li %B Proceedings of The 33rd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Sanjoy Dasgupta %E Nika Haghtalab %F pmlr-v167-karimi22a %I PMLR %P 606--637 %U https://proceedings.mlr.press/v167/karimi22a.html %V 167 %X Many constrained, nonconvex and nonsmooth optimization problems can be tackled using the majorization-minimization (MM) method which alternates between constructing a surrogate func- tion which upper bounds the objective function, and then minimizing this surrogate. For problems which minimize a finite sum of functions, a stochastic version of the MM method selects a batch of functions at random at each iteration and optimizes the accumulated surrogate. However, in many cases of interest such as variational inference for latent variable models, the surrogate functions are expressed as an expectation. In this contribution, we propose a doubly stochastic MM method based on Monte Carlo approximation of these stochastic surrogates. We establish asymptotic and non-asymptotic convergence of our scheme in a constrained, nonconvex, nonsmooth optimization setting. We apply our new framework for inference of logistic regression model with missing data and for variational inference of Bayesian variants of LeNet-5 and Resnet-18 on benchmark datasets.
APA
Karimi, B., Wai, H., Moulines, E. & Li, P.. (2022). Minimization by Incremental Stochastic Surrogate Optimization for Large Scale Nonconvex Problems. Proceedings of The 33rd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 167:606-637 Available from https://proceedings.mlr.press/v167/karimi22a.html.

Related Material