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" [...]


  The majority of financial loan companies provide the service of getting North Carolina Loans Online for U.S. citizens. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Levitra, but also as part of its analogs.