• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Statistics and computing >Fast incremental expectation maximization for finite-sum optimization: nonasymptotic convergence
【24h】

Fast incremental expectation maximization for finite-sum optimization: nonasymptotic convergence

机译：有限和优化的快速增量期望最大化：非血换收敛

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Fast incremental expectation maximization (FIEM) is a version of the EM framework for large datasets. In this paper, we first recast FIEM and other incremental EM type algorithms in the Stochastic Approximation within EM framework. Then, we provide nonasymptotic bounds for the convergence in expectation as a function of the number of examples n and of the maximal number of iterations K-max. We propose two strategies for achieving an epsilon-approximate stationary point, respectively with K-max = O(n(2/3)/epsilon) and K-max = O(root n/epsilon(3/2)), both strategies relying on a random termination rule before K-max and on a constant step size in the Stochastic Approximation step. Our bounds provide some improvements on the literature. First, they allow K-max to scale as root n which is better than n(2/3) which was the best rate obtained so far; it is at the cost of a larger dependence upon the tolerance epsilon, thus making this control relevant for small to medium accuracy with respect to the number of examples n. Second, for the n(2/3)-rate, the numerical illustrations show that thanks to an optimized choice of the step size and of the bounds in terms of quantities characterizing the optimization problem at hand, our results design a less conservative choice of the step size and provide a better control of the convergence in expectation.
机译：快速增量期望最大化（FIEM）是大型数据集的EM框架的版本。在本文中，我们在EM框架内的随机近似下重铸FIEM和其他增量EM型算法。然后，我们为期望的收敛提供非因素的界限，作为示例n的数量N和最大迭代次数的迭代次数的函数。我们提出了两种策略，用于分别与K-MAX = O（n（2/3）/ epsilon）和K-MAX = O（根N / EPSILON（3/2））分别进行epsilon - 近似静止点的策略，这两个策略在K-MAX之前依赖于随机终止规则以及随机近似步骤中的恒定步长。我们的界限对文献提供了一些改进。首先，它们允许K-MAX以根部N缩放，这比N（2/3）更好，这是到目前为止所获得的最优惠速率;它是对普遍耐受性依赖性的更大依赖性的成本，从而使得该控制与相对于示例N的数量相对于较小的中等精度。其次，对于n（2/3） - rate，数字插图表明，由于在表征优化问题的数量方面的阶梯大小和界限的优化选择，我们的结果设计了更保守的保守选择步长并提供更好地控制期望的收敛性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号