Majorization-minimization algorithms consist of successively minimizing a
sequence of upper bounds of the objective function. These upper bounds are
tight at the current estimate, and each iteration monotonically drives the
objective function downhill. Such a simple principle is widely applicable and
has been very popular in various scientific fields, especially in signal
processing and statistics. In this paper, we propose an incremental
majorization-minimization scheme for minimizing a large sum of continuous
functions, a problem of utmost importance in machine learning. We present
convergence guarantees for non-convex and convex optimization when the upper
bounds approximate the objective up to a smooth error; we call such upper
bounds "first-order surrogate functions". More precisely, we study asymptotic
stationary point guarantees for non-convex problems, and for convex ones, we
provide convergence rates for the expected objective function value. We apply
our scheme to composite optimization and obtain a new incremental proximal
gradient algorithm with linear convergence rate for strongly convex functions.
In our experiments, we show that our method is competitive with the state of
the art for solving machine learning problems such as logistic regression when
the number of training samples is large enough, and we demonstrate its
usefulness for sparse estimation with non-convex penalties.

提出了一种增量主化极小化算法，用于最小化连续函数的大量和，研究给出了非凸优化的渐近稳定点保证，并针对凸优化提供了期望目标函数值的收敛速度，在实验中展示了该方法在解决机器学习问题方面的竞争力以及处理非凸性惩罚稀疏估计的实用性。

增量主次优化在大规模机器学习中的应用

Incremental Majorization-Minimization Optimization with Application to  Large-Scale Machine Learning

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 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 of
$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 develop several efficient algorithms based on our framework. First, we
propose a new stochastic proximal gradient method, which experimentally matches
state-of-the-art solvers for large-scale $\ell_1$-logistic regression. Second,
we develop an online DC programming algorithm for non-convex sparse estimation.
Finally, we demonstrate the effectiveness of our approach for solving
large-scale structured matrix factorization problems.

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