### Abstract

Linear optimization is many times algorithmically simpler than non-linear convex optimization. Linear optimization over matroid polytopes, matching polytopes and path polytopes are example of problems for which we have efficient combinatorial algorithms, but whose non-linear convex counterpart is harder and admit significantly less efficient algorithms. This motivates the computational model of online decision making and optimization using a linear optimization oracle. In this computational model we give the first efficient decision making algorithm with optimal regret guarantees, answering an open question of [1], [2], in case the decision set is a polytope. We also give an extension of the algorithm for the partial information setting, i.e. the "bandit" model. Our method is based on a novel variant of the conditional gradient method, or Frank-Wolfe algorithm, that reduces the task of minimizing a smooth convex function over a domain to that of minimizing a linear objective. Whereas previous variants of this method give rise to approximation algorithms, we give such algorithm that converges exponentially faster and thus runs in polynomial-time for a large class of convex optimization problems over polyhedral sets, a result of independent interest.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 |

Pages | 420-428 |

Number of pages | 9 |

DOIs | |

State | Published - Dec 1 2013 |

Externally published | Yes |

Event | 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 - Berkeley, CA, United States Duration: Oct 27 2013 → Oct 29 2013 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

ISSN (Print) | 0272-5428 |

### Other

Other | 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013 |
---|---|

Country | United States |

City | Berkeley, CA |

Period | 10/27/13 → 10/29/13 |

### All Science Journal Classification (ASJC) codes

- Computer Science(all)

### Keywords

- Convex optimization
- Online algorithms
- Regret minimization

## Fingerprint Dive into the research topics of 'Playing non-linear games with linear oracles'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013*(pp. 420-428). [6686178] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2013.52