Online Stochastic Optimization With Time-Varying Distributions
Online Stochastic Optimization With Time-Varying Distributions
复制标题
DOI：
10.1109/tac.2020.2996178
复制
发表时间：
2021-04
影响因子：
6.8
通讯作者：
Xuanyu Cao;Junshan Zhang;H. Vincent Poor
中科院分区：
文献类型：
--
作者：
Xuanyu Cao;Junshan Zhang;H. Vincent Poor
本文研究了随机参数服从时变分布的在线随机优化问题。在每个时隙中，在确定控制变量之后，从当前分布中提取的样本被显示为反馈信息。这种形式的随机优化在在线学习和信号处理中有着广泛的应用，其中潜在的地面真实数据本质上是时变的，例如跟踪运动目标。与固定分布随机优化中的静态最优点不同，采用动态最优点作为性能基准来定义算法的遗憾。首先研究了具有时变分布的无约束随机优化问题，提出了一种投影随机梯度下降算法。关于动态最优的漂移，建立了关于其后悔的上界，该上界测量了潜在分布的时间变化。特别是，只要最优解的漂移是次线性的，即分布变化不太大，算法就会有次线性遗憾。在此基础上，针对具有时变分布的约束随机优化问题，提出了一种只需迭代闭式计算的随机鞍点算法。对于最优解的漂移，给出了其后悔和违反约束的上界。类似地，如果最优解的漂移是次线性的，则可以保证次线性的后悔和次线性的约束违反。最后，给出了数值结果，验证了所提算法和分析结果的有效性。
This article studies online stochastic optimization, where the random parameters follow time-varying distributions. In each time slot, after a control variable is determined, a sample drawn from the current distribution is revealed as feedback information. This form of stochastic optimization has broad applications in online learning and signal processing, where the underlying ground-truth is inherently time-varying, e.g., tracking a moving target. Dynamic optimal points are adopted as the performance benchmark to define the regret of algorithms, as opposed to the static optimal point used in stochastic optimization with fixed distributions. Unconstrained stochastic optimization with time-varying distributions is first examined and a projected stochastic gradient descent algorithm is presented. An upper bound on its regret is established with respect to the drift of the dynamic optima, which measures the temporal variations of the underlying distributions. In particular, the algorithm possesses sublinear regret as long as the drift of the optima is sublinear, i.e., the distributions do not vary too drastically. Further, a stochastic saddle point method involving only iterative closed-form computation is proposed for constrained stochastic optimization with time-varying distributions. Upper bounds on its regret and constraint violation are developed with respect to the drift of the optima. Analogously, sublinear regret and sublinear constraint violation can be ensured provided that the drift of the optima is sublinear. Finally, numerical results are presented to corroborate the efficacy of the proposed algorithms and the derived analytical results.