Tuesday, 16:15 - 16:40 h, Room: H 3503


Alexander Rakhlin
Regret minimization with zeroth order information

Coauthors: Alekh Agarwal, Dean Foster, Daniel Hsu, Sham Kakade


The problem of stochastic convex optimization with the noisy zeroth order oracle can be seen as a generalization of the classical multi-armed bandit problem, if the goal is to minimize regret rather than the final value of the objective. Regret is defined as the average of the function values along the optimization path, and not all convex optimization methods have low regret. In this talk we present a regret-minimization algorithm that is based on the zeroth order algorithm of Nemirovskii and Yudin from the 70's. We also briefly discuss regret minimization in a more difficult scenario of online linear optimization, where the linear cost functions are changing adversarially at every step. While we only have one shot at getting any information about the cost function per step, a randomized method which explores according to the Dikin ellipsoid is shown to enjoy a near-optimal regret bound.


Talk 3 of the invited session Tue.3.H 3503
"Novel approaches in derivative-free optimization" [...]
Cluster 6
"Derivative-free & simulation-based optimization" [...]


  Most online loan lenders allow getting New Jersey Payday Loans without visiting a bank, straight to your bank account. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cheap Cialis was obtained in Europe, Australia, New Zealand.