%0 Conference Paper %1 HPGySz16:BCO %A Hu, X. %A Prashanth L.A., %A György, A. %A Szepesvári, Cs. %B AISTATS %D 2016 %K bandits, convex learning, noisy online optimization optimization, order zeroth %P 819--828 %T (Bandit) Convex Optimization with Biased Noisy Gradient Oracles %X Algorithms for bandit convex optimization and online learning often rely on constructing noisy gradient estimates, which are then used in appropriately adjusted first-order algorithms, replacing actual gradients. Depending on the properties of the function to be optimized and the nature of ``noise'' in the bandit feedback, the bias and variance of gradient estimates exhibit various tradeoffs. In this paper we propose a novel framework that replaces the specific gradient estimation methods with an abstract oracle. With the help of the new framework we unify previous works, reproducing their results in a clean and concise fashion, while, perhaps more importantly, the framework also allows us to formally show that to achieve the optimal root-n rate either the algorithms that use existing gradient estimators, or the proof techniques used to analyze them have to go beyond what exists today.

@inproceedings{HPGySz16:BCO, abstract = {Algorithms for bandit convex optimization and online learning often rely on constructing noisy gradient estimates, which are then used in appropriately adjusted first-order algorithms, replacing actual gradients. Depending on the properties of the function to be optimized and the nature of ``noise'' in the bandit feedback, the bias and variance of gradient estimates exhibit various tradeoffs. In this paper we propose a novel framework that replaces the specific gradient estimation methods with an abstract oracle. With the help of the new framework we unify previous works, reproducing their results in a clean and concise fashion, while, perhaps more importantly, the framework also allows us to formally show that to achieve the optimal root-n rate either the algorithms that use existing gradient estimators, or the proof techniques used to analyze them have to go beyond what exists today.}, added-at = {2020-03-17T03:03:01.000+0100}, author = {Hu, X. and {Prashanth L.A.} and Gy{\"o}rgy, A. and {Sz}epesv{\'a}ri, {Cs}.}, biburl = {https://www.bibsonomy.org/bibtex/2fc616df28b83832d7e50188e85d16d8e/csaba}, booktitle = {AISTATS}, date-added = {2016-05-09 08:49:52 +0000}, date-modified = {2016-08-01 15:25:05 +0000}, interhash = {d52e49ef03c87d774f1eb7054be92eea}, intrahash = {fc616df28b83832d7e50188e85d16d8e}, keywords = {bandits, convex learning, noisy online optimization optimization, order zeroth}, pages = {819--828}, pdf = {papers/AISTAT16-BGO.pdf}, timestamp = {2020-03-17T03:03:01.000+0100}, title = {(Bandit) Convex Optimization with Biased Noisy Gradient Oracles}, year = 2016 }