Non-stationary stochastic optimization
From MaRDI portal
Abstract: 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: adversarial online convex optimization; and 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.
Recommendations
- Technical note: Nonstationary stochastic optimization under \(L_{p,q} \)-variation measures
- Better algorithms for benign bandits
- scientific article; zbMATH DE number 6253908
- Optimal exploration-exploitation in a multi-armed bandit problem with non-stationary rewards
- Second-order non-stationary online learning for regression
Cites work
- A nonparametric asymptotic analysis of inventory planning with censored demand
- A Stochastic Approximation Method
- An analog of the minimax theorem for vector payoffs
- Dynamic pricing under a general parametric choice model
- Dynamic Pricing with an Unknown Demand Model: Asymptotically Optimal Semi-Myopic Policies
- Efficient algorithms for online decision problems.
- scientific article; zbMATH DE number 3128728 (Why is no real title available?)
- scientific article; zbMATH DE number 4043678 (Why is no real title available?)
- Learning Theory
- Logarithmic Regret Algorithms for Online Convex Optimization
- On the minimax complexity of pricing in a changing environment
- Online convex optimization in the bandit setting: gradient descent without a gradient
- Optimal Experimentation in a Changing Environment
- Regret and Convergence Bounds for a Class of Continuum-Armed Bandit Problems
- Robust convex optimization
- Stochastic approximation
- Stochastic convex optimization with bandit feedback
- Stochastic Estimation of the Maximum of a Regression Function
- Theory and applications of robust optimization
Cited in
(44)- Bounds for the tracking error of first-order online optimization methods
- Handling concept drift via model reuse
- Decentralized online convex optimization based on signs of relative states
- Reinforcement with fading memories
- Dynamic Pricing and Learning with Finite Inventories
- Random feature-based online multi-kernel learning in environments with unknown dynamics
- Technical note: Perishable inventory systems: convexity results for base-stock policies and learning algorithms under censored demand
- Bandit convex optimization in non-stationary environments
- A simplex method for countably infinite linear programs
- Tracking and Regret Bounds for Online Zeroth-Order Euclidean and Riemannian Optimization
- Data-driven pricing for a new product
- Learning in structured MDPs with convex cost functions: improved regret bounds for inventory management
- Optimal exploration-exploitation in a multi-armed bandit problem with non-stationary rewards
- Technical note: Nonstationary stochastic optimization under \(L_{p,q} \)-variation measures
- Nonstationary bandits with habituation and recovery dynamics
- Adaptive online distributed optimization in dynamic environments
- Stochastic approximation with nondecaying gain: Error bound and data‐driven gain‐tuning
- Technical note: <scp>Finite‐time</scp> regret analysis of <scp>Kiefer‐Wolfowitz</scp> stochastic approximation algorithm and nonparametric <scp>multi‐product</scp> dynamic pricing with unknown demand
- A relaxation-based probabilistic approach for PDE-constrained optimization under uncertainty with pointwise state constraints
- Online decision making for trading wind energy
- Decentralized online convex optimization with compressed communications
- Nonstationary online convex optimization with multiple predictions
- Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
- The optimal dynamic regret for smoothed online convex optimization with squared \(l_2\) norm switching costs
- Dynamic regret of adaptive gradient methods for strongly convex problems
- Concept drift adaptation with continuous kernel learning
- Online composite optimization with time-varying regularizers
- Nonlinear optimization filters for stochastic time-varying convex optimization
- Distributed constrained online convex optimization with adaptive quantization
- Optimality and duality for nonconvex fuzzy optimization using granular differentiability method
- Online distributed nonconvex optimization with stochastic objective functions: high probability bound analysis of dynamic regrets
- Distributed online constrained convex optimization with event-triggered communication
- Distributed online stochastic gradient tracking
- Tracking nonstationary streaming data via exponentially weighted moving average stochastic gradient descent
- Continual learning as computationally constrained reinforcement learning
- Online distributed optimization with clipped stochastic gradients: high probability bound of regrets
- Distributed mirror descent for online bandit saddle point problem
- Stochastic approach for price optimization problems with decision-dependent uncertainty
- Nonparametric multi-product dynamic pricing with demand learning via simultaneous price perturbation
- Combinatorial multi-armed bandits with fairness constraints: an online convex optimization perspective
- Dynamic regret for decentralized online bandit gradient descent with local steps
- Last round convergence and no-dynamic regret in asymmetric repeated games
- Value-oriented forecast reconciliation for renewables in electricity markets
- On the performance of stochastic gradient methods with momentum in time-varying regimes
This page was built for publication: Non-stationary stochastic optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2795881)
