Online Stochastic Optimization with Time-Varying Distributions

Xuanyu Cao, Junshan Zhang, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Article number9097905
Pages (from-to)1840-1847
Number of pages8
JournalIEEE Transactions on Automatic Control
Volume66
Issue number4
DOIs
StatePublished - Apr 2021

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Keywords

  • Dynamic benchmark
  • online learning
  • online optimization
  • stochastic optimization
  • time-varying distributions

Fingerprint Dive into the research topics of 'Online Stochastic Optimization with Time-Varying Distributions'. Together they form a unique fingerprint.

Cite this