Stochastic convex optimization with bandit feedback

DOI10.1137/110850827zbMATH Open1270.90107arXiv1107.1744OpenAlexW2567882221MaRDI QIDQ5300524FDOQ5300524

Authors: Alekh Agarwal, Dean P. Foster, Daniel Hsu, Sham M. Kakade, Alexander Rakhlin 

Publication date: 27 June 2013

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: This paper addresses the problem of minimizing a convex, Lipschitz function $f$ over a convex, compact set $xset$ under a stochastic bandit feedback model. In this model, the algorithm is allowed to observe noisy realizations of the function value $f(x)$ at any query point $xinxset$. The quantity of interest is the regret of the algorithm, which is the sum of the function values at algorithm's query points minus the optimal function value. We demonstrate a generalization of the ellipsoid algorithm that incurs $otil(poly(d)sqrtT)$ regret. Since any algorithm has regret at least $Omega(sqrtT)$ on this problem, our algorithm is optimal in terms of the scaling with $T$.

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

Recommendations

• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Online convex optimization in the bandit setting: gradient descent without a gradient
• Kernel-based Methods for Bandit Convex Optimization
• Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case
• Kernel-based methods for bandit convex optimization

zbMATH Keywords

derivative-free optimizationellipsoid methodbandit optimization

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Convex programming (90C25) Derivative-free methods and methods using generalized derivatives (90C56)

Cited In (24)

• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Interior-Point Methods for Full-Information and Bandit Online Learning
• Kernel-based Methods for Bandit Convex Optimization
• Online bandit convex optimisation with stochastic constraints via two-point feedback
• Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case
• 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
• An accelerated method for derivative-free smooth stochastic convex optimization
• Robust randomized optimization with \(k\) nearest neighbors
• Improved regret for zeroth-order adversarial bandit convex optimisation
• Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
• Optimal policy for dynamic assortment planning under multinomial logit models
• Exploratory distributions for convex functions
• Random gradient-free minimization of convex functions
• Non-stationary stochastic optimization
• Algorithmic connections between active learning and stochastic convex optimization
• A new one-point residual-feedback oracle for black-box learning and control
• Operations research applications of dichotomous search
• Technical note: Nonstationary stochastic optimization under \(L_{p,q} \)-variation measures
• Title not available (Why is that?)
• An Efficient Algorithm for Learning with Semi-bandit Feedback
• Kernel-based methods for bandit convex optimization
• Zeroth-order feedback optimization for cooperative multi-agent systems
• Derivative-free optimization methods
• Stochastic continuum-armed bandits with additive models: minimax regrets and adaptive algorithm

This page was built for publication: Stochastic convex optimization with bandit feedback

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