(Bandit) Convex Optimization with Biased Noisy Gradient Oracles
File(s)OPT2015_paper_50(1).pdf (266.96 KB)
Published version
Author(s)
Hu, X
Prashanth, LA
Gyorgy, A
Szepesvari, C
Type
Conference Paper
Abstract
For bandit convex optimization we propose a model, where a gradient estimation oracle acts as an
intermediary between a noisy function evaluation oracle and the algorithms. The algorithms can
control the bias-variance tradeoff in the gradient estimates. We prove lower and upper bounds for
the minimax error of algorithms that interact with the objective function by controlling this oracle.
The upper bounds replicate many existing results (capturing the essence of existing proofs) while the
lower bounds put a limit on the achievable performance in this setup. In particular, our results imply
that no algorithm can achieve the optimal minimax error rate in stochastic bandit smooth convex
optimization.
intermediary between a noisy function evaluation oracle and the algorithms. The algorithms can
control the bias-variance tradeoff in the gradient estimates. We prove lower and upper bounds for
the minimax error of algorithms that interact with the objective function by controlling this oracle.
The upper bounds replicate many existing results (capturing the essence of existing proofs) while the
lower bounds put a limit on the achievable performance in this setup. In particular, our results imply
that no algorithm can achieve the optimal minimax error rate in stochastic bandit smooth convex
optimization.
Date Issued
2015-12-11
Date Acceptance
2015-11-02
Citation
2015
Identifier
http://opt-ml.org/oldopt/opt15/papers.html
Source
8th NIPS Workshop on Optimization for Machine Learning
Publication Status
Published
Start Date
2015-12-11
Finish Date
2015-12-11
Coverage Spatial
Montreal, Quebec, Canada