Technical Note—Nonstationary Stochastic Optimization Under L p,q -Variation Measures

Xi Chen (), Yining Wang () and Yu-Xiang Wang ()
Additional contact information
Xi Chen: Department of Technology, Operations, and Statistics, Stern School of Business, New York University, New York, New York 10012
Yining Wang: Machine Learning Department, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Yu-Xiang Wang: Computer Science Department, College of Engineering, University of California, Santa Barbara, Santa Barbara, California 93106

Operations Research, 2019, vol. 67, issue 6, 1752-1765

Abstract: We consider a nonstationary sequential stochastic optimization problem in which the underlying cost functions change over time under a variation budget constraint. We propose an L p,q -variation functional to quantify the change, which yields less variation for dynamic function sequences whose changes are constrained to short time periods or small subsets of input domain. Under the L p,q -variation constraint, we derive both upper and matching lower regret bounds for smooth and strongly convex function sequences, which generalize previously published results [ Besbes O, Gur Y, Zeevi A (2015) Non-stationary stochastic optimization. Oper. Res . 63(5):1227–1244]. Furthermore, we provide an upper bound for general convex function sequences with noisy gradient feedback, which matches the optimal rate as p → ∞. Our results reveal some interesting phenomena under this general variation functional, such as the curse of dimensionality of the function domain. The key technical novelties in our analysis include affinity lemmas that characterize the distance of the minimizers of two convex functions with bounded L p difference and a cubic spline–based construction that attains matching lower bounds.

Keywords: nonstationary stochastic optimization; bandit convex optimization; variation budget constraints; minimax regret (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1843 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:67:y:2019:i:6:p:1752-1765

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().