Skip to content
conftrace_
2023 COLT COLT 2023

A Second-Order Method for Stochastic Bandit Convex Optimisation

Abstract

We introduce a simple and efficient algorithm for unconstrained zeroth-order stochastic convex bandits and prove its regret is at most (1 + r/d)[d^1.5 sqrt(n) + d^3] polylog(n, d, r) where n is the horizon, d the dimension and r is the radius of a known ball containing the minimiser of the loss.

🌉 Interdisciplinary Bridge - Artificial Intelligence and Mathematics & Optimization
🐣 Hot Topic Early Bird - zeroth-order optimization

Authors

Tor Lattimore, András György

Topics

Machine Learning > Optimization & Theory > Optimization Mathematics & Optimization > Optimization > Stochastic Methods Mathematics & Optimization > Optimization > Online Algorithms Machine Learning > Learning Types > Multi-Armed Bandits Machine Learning > Optimization & Theory > Convex Optimization

Keywords

convex optimization stochastic convex optimization regret bound bandit convex optimization zeroth-order optimization stochastic bandit second-order method
Download PDF

More from COLT 2023

All COLT 2023 papers →
Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence
Exploring Local Norms in Exp-concave Statistical Learning
Learning Hidden Markov Models Using Conditional Samples
A Lower Bound for Linear and Kernel Regression with Adaptive Covariates
Provable Benefits of Representational Transfer in Reinforcement Learning
Geodesically convex M-estimation in metric spaces