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

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.