Majorization-minimization algorithms consist of iteratively minimizing a majorizing surrogate of an objective function. Because of its simplicity and its wide applicability, this principle has been very popular in statistics and in signal processing. In this paper, we intend to make this principle scalable. We introduce and study a stochastic majorization-minimization scheme, which is able to deal with large-scale or possibly infinite data sets. When applied to convex optimization problems under suitable assumptions, we show that it achieves an expected convergence rate of O(1/\sqrt{n}) after n iterations, and O(1/n) for strongly convex functions. Equally important, our scheme almost surely converges to stationary points for a large class of non-convex problems. We derive from our framework several efficient algorithms. First, we propose a new stochastic proximal gradient method, which experimentally matches state-of-the-art solvers for large-scale l1-logistic regression. Second, we develop an online DC programming algorithm for non-convex sparse estimation. Finally, we demonstrate the effectiveness of our technique for solving large-scale structured matrix factorization problems.

本文提出了一种可扩展的随机主化最小化方案，能够应对大规模或可能无限的数据集，解决凸优化问题，并开发了几种基于此框架的有效算法，包括一个新的随机近端梯度方法，用于大规模l1逻辑回归的非凸稀疏估计的在线DC编程算法和解决大规模结构矩阵分解问题的有效性。

大规模优化的随机主支配-最小化算法