# Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates

arXiv: https://arxiv.org/abs/2201.01652 · HTML: https://mlsanity.com/paper/2201.01652/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 62 references that are in the map.
- First posted on arXiv 5 Jan 2022.

## Builds on (most cited first, 16 of 16)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization](https://mlsanity.com/paper/1306.4650/) (2013)
- [A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation](https://mlsanity.com/paper/1610.05275/) (2016)
- [Stochastic Gradients for Large-Scale Tensor Decomposition](https://mlsanity.com/paper/1906.01687/) (2019)
- [Online matrix factorization for Markovian data and applications to Network Dictionary Learning](https://mlsanity.com/paper/1911.01931/) (2019)
- [On the Convergence of (Stochastic) Gradient Descent with Extrapolation for Non-Convex Optimization](https://mlsanity.com/paper/1901.10682/) (2019)
- [Stochastic Subsampling for Factorizing Huge Matrices](https://mlsanity.com/paper/1701.05363/) (2017)
- [Markov Chain Block Coordinate Descent](https://mlsanity.com/paper/1811.08990/) (2018)
- [Online nonnegative CP-dictionary learning for Markovian data](https://mlsanity.com/paper/2009.07612/) (2020)
- [Online Nonnegative Matrix Factorization with General Divergences](https://mlsanity.com/paper/1608.00075/) (2016)

## Built on by (most cited first, 2 of 2)

- [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024)
- [Revisiting Incremental Stochastic Majorization-Minimization Algorithms with Applications to Mixture of Experts](https://mlsanity.com/paper/2601.19811/) (2026)

## Abstract (arXiv)

Stochastic majorization-minimization (SMM) is a class of stochastic optimization algorithms that proceed by sampling new data points and minimizing a recursive average of surrogate functions of an objective function. The surrogates are required to be strongly convex and convergence rate analysis for the general non-convex setting was not available. In this paper, we propose an extension of SMM where surrogates are allowed to be only weakly convex or block multi-convex, and the averaged surrogates are approximately minimized with proximal regularization or block-minimized within diminishing radii, respectively. For the general nonconvex constrained setting with non-i.i.d. data samples, we show that the first-order optimality gap of the proposed algorithm decays at the rate O((log n)1+ε/n1/2) for the empirical loss and O((log n)1+ε/n1/4) for the expected loss, where n denotes the number of data samples processed. Under some additional assumption, the latter convergence rate can be improved to O((log n)1+ε/n1/2). As a corollary, we obtain the first convergence rate bounds for various optimization methods under general nonconvex dependent data setting: Double-averaging projected gradient descent and its generalizations, proximal point empirical risk minimization, and online matrix/tensor decomposition algorithms. We also provide experimental validation of our results.