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

DOI10.1287/OPRE.2019.1843zbMATH Open1455.90113arXiv1708.03020OpenAlexW2976415674MaRDI QIDQ5129221FDOQ5129221

Authors:

Publication date: 26 October 2020

Published in: Operations Research (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

minimax regretbandit convex optimizationnonstationary stochastic optimizationvariation budget constraints

Mathematics Subject Classification ID

Stochastic programming (90C15)

Cites Work

• Title not available (Why is that?)
• Elements of Information Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Introduction to nonparametric estimation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Logarithmic regret algorithms for online convex optimization
• Online convex optimization in the bandit setting: gradient descent without a gradient
• Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization
• Dynamic Pricing and Learning with Finite Inventories
• Chasing demand: learning and earning in a changing environment
• Minimax Bounds for Active Learning
• A survey of algorithms and analysis for adaptive online learning
• Stochastic convex optimization with bandit feedback
• Kernel-based methods for bandit convex optimization
• Non-stationary stochastic optimization
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point 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)