On the time-varying distributions of online stochastic optimization

Xuanyu Cao, Junshan Zhang, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

This paper 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, as opposed to the static optimal point used in stochastic optimization with fixed distributions. Stochastic optimization with time-varying distributions is 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 variations of the optimal solutions due to the varying 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. Finally, numerical results are presented to corroborate the efficacy of the proposed algorithm and the derived analytical results.

Original languageEnglish (US)
Title of host publication2019 American Control Conference, ACC 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1494-1500
Number of pages7
ISBN (Electronic)9781538679265
DOIs
StatePublished - Jul 2019
Event2019 American Control Conference, ACC 2019 - Philadelphia, United States
Duration: Jul 10 2019Jul 12 2019

Publication series

NameProceedings of the American Control Conference
Volume2019-July
ISSN (Print)0743-1619

Conference

Conference2019 American Control Conference, ACC 2019
CountryUnited States
CityPhiladelphia
Period7/10/197/12/19

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Keywords

  • Dynamic benchmark
  • Online learning
  • Online optimization
  • Stochastic optimization
  • Time-varying distributions

Fingerprint Dive into the research topics of 'On the time-varying distributions of online stochastic optimization'. Together they form a unique fingerprint.

  • Cite this

    Cao, X., Zhang, J., & Poor, H. V. (2019). On the time-varying distributions of online stochastic optimization. In 2019 American Control Conference, ACC 2019 (pp. 1494-1500). [8814889] (Proceedings of the American Control Conference; Vol. 2019-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.23919/acc.2019.8814889