Online Stochastic Optimization With Time-Varying Distributions

• 成果类型: Article
• 署名作者: Cao, Xuanyu; Zhang, Junshan; Poor, H. Vincent
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; Arizona State University; Arizona State University-Tempe; Princeton University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.2996178
• 发表日期: 2021
• 页码: 1840-1847
• 关键词: Optimization; Heuristic algorithms; Stochastic processes; Signal processing algorithms; programming; Benchmark testing; Power system dynamics; Dynamic benchmark; online learning; online optimization; stochastic optimization; time-varying distributions

摘要

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.