Stochastic Optimization under Distributional Drift
Stochastic Optimization under Distributional Drift
复制标题
DOI：
--
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Joshua Cutler;D. Drusvyatskiy;Zaïd Harchaoui
中科院分区：
文献类型：
--
作者：
Joshua Cutler;D. Drusvyatskiy;Zaïd Harchaoui
我们考虑最小化凸函数的问题，凸函数是根据未知的和可能的随机动态，这可能取决于共同的时间和决策变量本身。这样的问题在机器学习和信号处理文献中比比皆是，以概念漂移，随机跟踪和表演预测的名义。我们提供了新的非渐近收敛保证随机算法的平均，专注于有效的期望和高概率的界限。我们获得的效率估计清楚地解耦了优化误差、梯度噪声和时间漂移的贡献。值得注意的是，我们确定了一个低漂移噪声制度，其中的近端随机梯度方法的跟踪效率显着受益于一个步骤衰减时间表。数值实验说明了我们的结果。
We consider the problem of minimizing a convex function that is evolving according to unknown and possibly stochastic dynamics, which may depend jointly on time and on the decision variable itself. Such problems abound in the machine learning and signal processing literature, under the names of concept drift, stochastic tracking, and performative prediction. We provide novel non-asymptotic convergence guarantees for stochastic algorithms with iterate averaging, focusing on bounds valid both in expectation and with high probability. The efficiency estimates we obtain clearly decouple the contributions of optimization error, gradient noise, and time drift. Notably, we identify a low drift-to-noise regime in which the tracking efficiency of the proximal stochastic gradient method benefits significantly from a step decay schedule. Numerical experiments illustrate our results.