Optimization objectives in the form of a sum of intractable expectations are
rising in importance (e.g., diffusion models, variational autoencoders, and
many more), a setting also known as "finite sum with infinite data." For these
problems, a popular strategy is to employ SGD with doubly stochastic gradients
(doubly SGD): the expectations are estimated using the gradient estimator of
each component, while the sum is estimated by subsampling over these
estimators. Despite its popularity, little is known about the convergence
properties of doubly SGD, except under strong assumptions such as bounded
variance. In this work, we establish the convergence of doubly SGD with
independent minibatching and random reshuffling under general conditions, which
encompasses dependent component gradient estimators. In particular, for
dependent estimators, our analysis allows fined-grained analysis of the effect
correlations. As a result, under a per-iteration computational budget of $b
\times m$, where $b$ is the minibatch size and $m$ is the number of Monte Carlo
samples, our analysis suggests where one should invest most of the budget in
general. Furthermore, we prove that random reshuffling (RR) improves the
complexity dependence on the subsampling noise.

对于以不可解期望的求和形式作为优化目标的问题，除了有界方差等强假设条件外，很少了解双重随机梯度下降（doubly SGD）的收敛性质。本研究在一般条件下，建立了具有独立小批量和随机重排的双重随机梯度下降的收敛性，并允许对依赖的分量梯度估计进行详细分析，推荐在每次迭代的计算预算中如何进行合理分配，同时证明随机重排（RR）可以改善子采样噪声的复杂度依赖关系。