We study online convex optimization in the random order model, recently proposed by \citet{garber2020online}, where the loss functions may be chosen by an adversary, but are then presented to the online algorithm in a uniformly random order. Focusing on the scenario where the cumulative loss function is (strongly) convex, yet individual loss functions are smooth but might be non-convex, we give algorithms that achieve the optimal bounds and significantly outperform the results of \citet{garber2020online}, completely removing the dimension dependence and improving their scaling with respect to the strong convexity parameter. Our analysis relies on novel connections between algorithmic stability and generalization for sampling without-replacement analogous to those studied in the with-replacement i.i.d.~setting, as well as on a refined average stability analysis of stochastic gradient descent.
翻译:我们研究的是随机顺序模型中的在线 convex优化, 最近由\ citet{garber2020online} 提议, 损失函数可由对手选择, 但随后以统一的随机顺序呈现给在线算法 。 我们的分析依赖于累积损失函数( 强力) 的假设情景, 但单个损失函数是平滑的, 但可能是非cavex 的, 我们给出的算法可以达到最佳的界限, 大大超过\ citet{garber202020online} 的结果, 完全消除尺寸依赖性, 并改进它们相对于强力凝固参数的缩放。 我们的分析依赖于算法稳定性和不替换抽样的概括性之间的新联系, 类似于在替换时所研究的 i. d. ~ 设置, 以及精细的随机梯度梯度下位平均稳定性分析 。