基于集成重要性采样的随机梯度下降算法

Stochastic gradient descent algorithm based on ensemble importance sampling

许多机器学习和深度学习问题都可以使用随机梯度优化算法求解,目前流行的算法大多通过均匀采样从样本集中抽取样本计算梯度估计。然而,随机采样的梯度估计会带来较大的方差,这个方差会随着优化的进行而累积,降低算法收敛速度。为缓解这一现象,可以为每个样本赋予不同的采样概率。该文基于集成学习的思想,提出了一种新的选取非均匀采样分布的算法。算法的主要目的是选取一个采样器权重,使梯度估计的方差尽可能小。所提算法由多个简单采样器组成,采样权重为每个简单采样器分配贡献权重,从而得到最终的采样分布。集成重要性采样算法可以和以往的随机梯度优化方法任意结合,该文给出了使用集成重要性采样的随机梯度下降算法。在试验中,可以直观地看到算法起效的原因。在真实数据集中,展示了所提算法减小方差的效果,与其他算法相比具有一定优势。

Many machine learning and deep learning problems can be solved using stochastic gradient optimization algorithms.Most of the popular algorithms currently use uniform sampling to extract samples from a dataset to calculate gradient estimates.However,randomly sampled gradient estimates will result in a high variance,which will accumulate as the optimization proceeds,reducing the convergence speed of the algorithm.To address this issue,different sampling probabilities can be assigned to each sample.This paper proposes a new algorithm for selecting non-uniform sampling distributions based on the idea of ensemble learning.The primary goal of the algorithm is to select a sampler weight such that the variance of the gradient estimate is minimized.The proposed algorithm consists of multiple simple samplers,and the sampling weight assigns a contribution weight to each simple sampler to obtain the final sampling distribution.The ensemble importance sampling algorithm can be combined with previous stochastic gradient optimization methods.This paper presents a stochastic gradient descent algorithm using ensemble importance sampling.In the experiments,the effectiveness of the algorithm is demonstrated.The proposed algorithm reduces the variance in real datasets which has certain advantages compared to other algorithms.