We study the gradient Expectation-Maximization (EM) algorithm for Gaussian
Mixture Models (GMM) in the over-parameterized setting, where a general GMM
with $n>1$ components learns from data that are generated by a single ground
truth Gaussian distribution. While results for the special case of 2-Gaussian
mixtures are well-known, a general global convergence analysis for arbitrary
$n$ remains unresolved and faces several new technical barriers since the
convergence becomes sub-linear and non-monotonic. To address these challenges,
we construct a novel likelihood-based convergence analysis framework and
rigorously prove that gradient EM converges globally with a sublinear rate
$O(1/\sqrt{t})$. This is the first global convergence result for Gaussian
mixtures with more than $2$ components. The sublinear convergence rate is due
to the algorithmic nature of learning over-parameterized GMM with gradient EM.
We also identify a new emerging technical challenge for learning general
over-parameterized GMM: the existence of bad local regions that can trap
gradient EM for an exponential number of steps.

在过参数化的设置中，我们研究了高斯混合模型（GMM）的梯度期望最大化（EM）算法，通过单个真实高斯分布生成的数据来学习具有 n > 1 个分量的一般 GMM。通过构建一个新的基于似然度的收敛性分析框架，我们严格证明了梯度 EM 以 sublinear 速率 O (1/√t) 具有全局收敛性，这是关于具有多于 2 个分量的高斯混合模型的首个全局收敛结果。子线性收敛速率是由于学习过参数化 GMM 的算法性质所导致的。我们还确定了学习一般过参数化 GMM 的新技术挑战：存在能够在指数步数内困住梯度 EM 的不良局部区域。

面向超参数化高斯混合模型梯度 EM 算法的全球收敛

Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian  Mixture Models

We propose a new stochastic optimization framework for empirical risk
minimization problems such as those that arise in machine learning. The
traditional approaches, such as (mini-batch) stochastic gradient descent (SGD),
utilize an unbiased gradient estimator of the empirical average loss. In
contrast, we develop a computationally efficient method to construct a gradient
estimator that is purposely biased toward those observations with higher
current losses. On the theory side, we show that the proposed method minimizes
a new ordered modification of the empirical average loss, and is guaranteed to
converge at a sublinear rate to a global optimum for convex loss and to a
critical point for weakly convex (non-convex) loss. Furthermore, we prove a new
generalization bound for the proposed algorithm. On the empirical side, the
numerical experiments show that our proposed method consistently improves the
test errors compared with the standard mini-batch SGD in various models
including SVM, logistic regression, and deep learning problems.

论文提出了一种新的随机优化方法，它有针对性地偏向于高损失值的观测结果，并证明该算法对于凸损失具有亚线性收敛率，对于弱凸损失（非凸）具有关键点，同时在 SVM、逻辑回归和深度学习等模型中获得了更好的测试误差。

有序 SGD: 一种新的经验风险最小化随机优化框架

Ordered SGD: A New Stochastic Optimization Framework for Empirical Risk  Minimization

In this paper, we study and analyze the mini-batch version of StochAstic
Recursive grAdient algoritHm (SARAH), a method employing the stochastic
recursive gradient, for solving empirical loss minimization for the case of
nonconvex losses. We provide a sublinear convergence rate (to stationary
points) for general nonconvex functions and a linear convergence rate for
gradient dominated functions, both of which have some advantages compared to
other modern stochastic gradient algorithms for nonconvex losses.

本文研究分析了随机递归梯度算法 (StochAstic Recursive grAdient algoritHm, SARAH) 的 mini-batch 版本，用于解决非凸损失函数的经验损失最小化问题。我们提出了一种子线性收敛率 (对于一般非凸函数) 和一种线性收敛率 (对于梯度主导函数)，这两种方法相比其他现代非凸损失随机梯度算法具有一些优势。