For obtaining optimal first-order convergence guarantee for stochastic optimization, it is necessary to use a recurrent data sampling algorithm that samples every data point with sufficient frequency. Most commonly used data sampling algorithms (e.g., i.i.d., MCMC, random reshuffling) are indeed recurrent under mild assumptions. In this work, we show that for a particular class of stochastic optimization algorithms, we do not need any other property (e.g., independence, exponential mixing, and reshuffling) than recurrence in data sampling algorithms to guarantee the optimal rate of first-order convergence. Namely, using regularized versions of Minimization by Incremental Surrogate Optimization (MISO), we show that for non-convex and possibly non-smooth objective functions, the expected optimality gap converges at an optimal rate $O(n^{-1/2})$ under general recurrent sampling schemes. Furthermore, the implied constant depends explicitly on the `speed of recurrence', measured by the expected amount of time to visit a given data point either averaged (`target time') or supremized (`hitting time') over the current location. We demonstrate theoretically and empirically that convergence can be accelerated by selecting sampling algorithms that cover the data set most effectively. We discuss applications of our general framework to decentralized optimization and distributed non-negative matrix factorization.

使用定期化的最小化增量替代优化算法 (MISO)，基于常规的重复采样方案，在非凸、可能非光滑的目标函数上，期望的最优性差随着数据点数量的增加以最佳速率 O(n^{-1/2}) 收敛。更进一步，暗示常数明确取决于“重复速度”，通过对预期访问给定数据点的时间进行平均（“目标时间”）或最大化（“击中时间”）测量。我们的研究理论上和实证上证明，通过选择最有效地覆盖数据集的采样算法，可以加速收敛速度。我们还讨论了该通用框架在分散优化和分布式非负矩阵分解方面的应用。

任意循环数据抽样的随机优化