Non-Stationary Stochastic Optimization

By Omar Besbes, Yonatan Gur, Assaf J. Zeevi. 2013

507 citations recorded by the source corpus.

We consider a non-stationary variant of a sequential stochastic optimization problem, in which the underlying cost functions may change along the horizon. We propose a measure, termed variation budget , that controls the extent of said change, and study how restrictions on this budget impact achievable performance. We identify sharp conditions under which it is possible to achieve long-run average optimality and more refined performance measures such as rate optimality that fully characterize the complexity of such problems. In doing so, we also establish a strong connection between two rather disparate strands of literature: (1) adversarial online convex optimization and (2) the more traditional stochastic approximation paradigm (couched in a non-stationary setting). This connection is the key to deriving well-performing policies in the latter, by leveraging structure of optimal policies in the former. Finally, tight bounds on the minimax regret allow us to quantify the “price of non-stationarity,” which mathematically captures the added complexity embedded in a temporally changing environment versus a stationary one.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Adaptive Online Planning for Continual Lifelong Learning (2019, neutral): “In contrast to previous notions of regret [1, 5, 41], we consider a notion of regret that focuses on how well the agent can learn in the future as a consequence of near short-term actions.”
Online Meta-Learning (2019, neutral): “In the dynamic regret setting (Herbster & Warmuth, 1995; Yang et al., 2016; Besbes et al., 2015), the performance of the online learner’s model sequence is compared against the sequence of optimal solutions corresponding to each loss function in the sequence.”
Understand Dynamic Regret with Switching Cost for Online Decision Making (2019, background): “Many other previous researches investigate the regret under dierent denitions of dynamics such as parameter variation [19, 34, 44, 47], functional variation [7, 25, 46], gradient variation [17], and the mixed regularity [16, 24].”
Dynamic Pricing and Learning: Historical Origins, Current Research, and New Directions (2013, unknown): “3, is related to the non-stationary multiarmed bandit problem [304,305].”
Tracking Moving Agents via Inexact Online Gradient Descent Algorithm (2017, methodology): “Recent year have witnessed the development of theoretical guarantees in form of dynamic regret, where the performance of the learner is measured against that of an adaptive and time-varying adversary [11], [17], [18].”
Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient (2016, methodology): “hen φt(w) = w. There has been a different notion to measure the point-wise changes in the sequence of loss functions that measure the changesoftwo consecutivefunctionsat anyfeasiblepoints. Forexample,Besbes et al. (2013) consideredthefunctional variation deﬁned as V f T = TX−1 t=1 max w∈Ω |ft(w) −ft”
Markov Decision Processes with Time-varying Transition Probabilities and Rewards (2019, background): “Part i) is common in literature when the problem considered does not have a Markov processe structure, e.g. (Besbes et al., 2014; 2015).”
Improved Dynamic Regret for Non-degenerate Functions (2016, background): “There are also some regularities deﬁned in terms of the function sequence, such as the functional variation (Besbes et al., 2015) or the gradient variation (Chiang et al., 2012) Under the condition that F T is given beforehand, a restarted online gradient descent is developed in (Besbes et al.,…”
Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound (2021, background): “Other regularities including the functional variation [5], [32]–[34], the gradient variation [35], and the mixed regularity [28], [36], [37] have been investigated to bound the dynamic regret.”
Adaptive Online Learning in Dynamic Environments (2018, background): “Under the assumption that an upper bound VT ≥ FT is known beforehand, Besbes et al. [2015] develop a restarted online gradient descent, and prove its dynamic regret is upper bounded by O(T (VT + 1)) and O(log T √ T (VT + 1)) for convex functions and strongly convex functions, respectively.”
Dynamic Regret of Strongly Adaptive Methods (2017, methodology): “Furthermore, according to the minimax dynamic regret of strongly convex functions (Besbes et al., 2015), our upper bound is minimax optimal, up to a polylogarithmic factor.”
Competing with Automata-based Expert Sequences (2018, background): “One perspective has been the design of algorithms that maintain a guarantee against sequences that do not vary too much [Mokhtari et al., 2016, Shahrampour and Jadbabaie, 2016, Jadbabaie et al., 2015, Besbes et al., 2015].”
Distributed Online Optimization in Dynamic Environments Using Mirror Descent (2016, background): “In parallel to studies of centralized online optimization [14], [15], [26], the hardness of the problem should be characterized via a complexity measure that captures the variation in the minimizer sequence {x t }t=1 .”
Tracking the Best Expert in Non-stationary Stochastic Environments (2017, background): “This regret upper bound is unimprovable in general even in the full-information setting, as a matching lower bound was shown in [4].”
Optimization in Dynamic Environments : Improved Regret Rates for Strongly Convex Problems (2016, unknown): “The work in [9] evaluates the performance of OGD for the case when a noisy estimate of the gradient is available and an upper bound on VT is assumed as prior knowledge.”
Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards (2014, background): “In particular, as in [24], it is seen that optimal policy in the adversarial setting may be suitably calibrated to perform near-optimally in the non-stationary stochastic setting.”
Online Learning for Markov Decision Processes in Nonstationary Environments: A Dynamic Regret Analysis (2019, methodology): “Similar impossibility results have been established for online learning without an MDP structure in literature [20] [21].”