Technical note: Nonstationary stochastic optimization under L_p,q -variation measures

DOI10.1287/OPRE.2019.1843MaRDI QIDQ5129221zbMATH OpenOpenAlexFDO

Authors

Publication date 26 October 2020

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.03020

zbMATH Keywords

minimax regretbandit convex optimizationnonstationary stochastic optimizationvariation budget constraints

Mathematics Subject Classification ID

Stochastic programming (90C15)

Abstract: We consider a non-stationary 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 previous results in Besbes et al. (2015). Furthermore, we provide an upper bound for general convex function sequences with noisy gradient feedback, which matches the optimal rate as $poinfty$. Our results reveal some surprising 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 Lp difference, and a cubic spline based construction that attains matching lower bounds.

Recommendations

• Non-stationary stochastic optimization
• Regret bounded by gradual variation for online convex optimization
• Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case
• Online sequential optimization with biased gradients: theory and applications to censored demand
• Better algorithms for benign bandits

Cites work

• scientific article; zbMATH DE number 3733065 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 1064667 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• A survey of algorithms and analysis for adaptive online learning
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization
• Chasing demand: learning and earning in a changing environment
• Dynamic Pricing and Learning with Finite Inventories
• Elements of Information Theory
• Introduction to nonparametric estimation
• Kernel-based methods for bandit convex optimization
• Logarithmic regret algorithms for online convex optimization
• Minimax Bounds for Active Learning
• Non-stationary stochastic optimization
• Online convex optimization in the bandit setting: gradient descent without a gradient
• Stochastic convex optimization with bandit feedback

Cited in

(2)

• Online sequential optimization with biased gradients: theory and applications to censored demand
• Non-stationary stochastic optimization

This page was built for publication: Technical note: Nonstationary stochastic optimization under \(L_{p,q} \)-variation measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5129221)