Technical Note-Nonstationary Stochastic Optimization Under Lp,a-Variation Measures

• 成果类型: Article
• 署名作者: Chen, Xi; Wang, Yining; Wang, Yu-Xiang
• 署名单位: New York University; Carnegie Mellon University; University of California System; University of California Santa Barbara
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1843
• 发表日期: 2019
• 页码: 1752-1765
• 关键词: convex; algorithms

摘要

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,L-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,L-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) Nonstationary 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 -> infinity. 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.