Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR07-088 | 27th November 2007 00:00

Adaptive Algorithms for Online Optimization

RSS-Feed




Revision #1
Authors: Elad Hazan, C. Seshadhri
Accepted on: 27th November 2007 00:00
Downloads: 3961
Keywords: 


Abstract:

We study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions. We propose a new performance metric, strengthening the standard metric of regret, to capture convergence to locally optimal solutions. We then describe a series of reductions which transform algorithms for minimizing (standard) regret into adaptive algorithms albeit incurring only poly-logarithmic computational overhead.

We describe applications of this technique to various well studied online problems, such as portfolio management, online routing and the tree update problem. In all cases we explain how previous algorithms perform suboptimally and how the reduction technique gives adaptive algorithms.

Our reductions combine techniques from data streaming algorithms, composition of learning algorithms and a novel use of unbiased gradient estimates.


Paper:

TR07-088 | 7th September 2007 00:00

Adaptive Algorithms for Online Decision Problems





TR07-088
Authors: Elad Hazan, C. Seshadhri
Publication: 14th September 2007 05:52
Downloads: 4067
Keywords: 


Abstract:

We study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions. We propose a new performance metric, strengthening the standard metric of regret, to capture convergence to locally optimal solutions, and propose efficient algorithms which provably converge at the optimal rate.

One application is the portfolio management problem, for which we show that all previous algorithms behave suboptimally under dynamic market conditions. Another application is online routing, for which our adaptive algorithm exploits local congestion patterns and runs in near-linear time. We also give an algorithm for the tree update problem that is statically optimal for every sufficiently long contiguous subsequence of accesses.

Our algorithm combines techniques from data streaming algorithms, composition of learning algorithms, and a twist on the standard experts framework.



ISSN 1433-8092 | Imprint