### Abstract

Prediction from expert advice is a fundamental problem in machine learning. A major pillar of the field is the existence of learning algorithms whose average loss approaches that of the best expert in hindsight (in other words, whose average regret approaches zero). Traditionally the regret of online algorithms was bounded in terms of the number of prediction rounds. Cesa-Bianchi, Mansour and Stoltz [4] posed the question whether it is be possible to bound the regret of an online algorithm by the variation of the observed costs. In this paper we resolve this question, and prove such bounds in the fully adversarial setting, in two important online learning scenarios: prediction from expert advice, and online linear optimization.

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

Pages | 57-67 |

Number of pages | 11 |

State | Published - Dec 1 2008 |

Externally published | Yes |

Event | 21st Annual Conference on Learning Theory, COLT 2008 - Helsinki, Finland Duration: Jul 9 2008 → Jul 12 2008 |

### Other

Other | 21st Annual Conference on Learning Theory, COLT 2008 |
---|---|

Country | Finland |

City | Helsinki |

Period | 7/9/08 → 7/12/08 |

### All Science Journal Classification (ASJC) codes

- Education

## Fingerprint Dive into the research topics of 'Extracting certainty from uncertainty: Regret bounded by variation in costs'. Together they form a unique fingerprint.

## Cite this

*Extracting certainty from uncertainty: Regret bounded by variation in costs*. 57-67. Paper presented at 21st Annual Conference on Learning Theory, COLT 2008, Helsinki, Finland.