Approximate Convex Optimization by Online Game Playing

Elad Hazan

Lagrangian relaxation and approximate optimization algorithms have received much attention in the last two decades. Typically, the running time of these methods to obtain a $\epsilon$ app…