Inertial Block Proximal Methods for Non-Convex Non-Smooth Optimization

Hien Le, Nicolas Gillis, Panagiotis Patrinos
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:5671-5681, 2020.

Abstract

We propose inertial versions of block coordinate descent methods for solving non-convex non-smooth composite optimization problems. Our methods possess three main advantages compared to current state-of-the-art accelerated first-order methods: (1) they allow using two different extrapolation points to evaluate the gradients and to add the inertial force (we will empirically show that it is more efficient than using a single extrapolation point), (2) they allow to randomly select the block of variables to update, and (3) they do not require a restarting step. We prove the subsequential convergence of the generated sequence under mild assumptions, prove the global convergence under some additional assumptions, and provide convergence rates. We deploy the proposed methods to solve non-negative matrix factorization (NMF) and show that they compete favorably with the state-of-the-art NMF algorithms. Additional experiments on non-negative approximate canonical polyadic decomposition, also known as nonnegative tensor factorization, are also provided.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-le20a, title = {Inertial Block Proximal Methods for Non-Convex Non-Smooth Optimization}, author = {Le, Hien and Gillis, Nicolas and Patrinos, Panagiotis}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {5671--5681}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/le20a/le20a.pdf}, url = {https://proceedings.mlr.press/v119/le20a.html}, abstract = {We propose inertial versions of block coordinate descent methods for solving non-convex non-smooth composite optimization problems. Our methods possess three main advantages compared to current state-of-the-art accelerated first-order methods: (1) they allow using two different extrapolation points to evaluate the gradients and to add the inertial force (we will empirically show that it is more efficient than using a single extrapolation point), (2) they allow to randomly select the block of variables to update, and (3) they do not require a restarting step. We prove the subsequential convergence of the generated sequence under mild assumptions, prove the global convergence under some additional assumptions, and provide convergence rates. We deploy the proposed methods to solve non-negative matrix factorization (NMF) and show that they compete favorably with the state-of-the-art NMF algorithms. Additional experiments on non-negative approximate canonical polyadic decomposition, also known as nonnegative tensor factorization, are also provided.} }
Endnote
%0 Conference Paper %T Inertial Block Proximal Methods for Non-Convex Non-Smooth Optimization %A Hien Le %A Nicolas Gillis %A Panagiotis Patrinos %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-le20a %I PMLR %P 5671--5681 %U https://proceedings.mlr.press/v119/le20a.html %V 119 %X We propose inertial versions of block coordinate descent methods for solving non-convex non-smooth composite optimization problems. Our methods possess three main advantages compared to current state-of-the-art accelerated first-order methods: (1) they allow using two different extrapolation points to evaluate the gradients and to add the inertial force (we will empirically show that it is more efficient than using a single extrapolation point), (2) they allow to randomly select the block of variables to update, and (3) they do not require a restarting step. We prove the subsequential convergence of the generated sequence under mild assumptions, prove the global convergence under some additional assumptions, and provide convergence rates. We deploy the proposed methods to solve non-negative matrix factorization (NMF) and show that they compete favorably with the state-of-the-art NMF algorithms. Additional experiments on non-negative approximate canonical polyadic decomposition, also known as nonnegative tensor factorization, are also provided.
APA
Le, H., Gillis, N. & Patrinos, P.. (2020). Inertial Block Proximal Methods for Non-Convex Non-Smooth Optimization. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:5671-5681 Available from https://proceedings.mlr.press/v119/le20a.html.

Related Material