ERA

Download the full-sized PDF of On Local RegretDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3930NW06

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

On Local Regret Open Access

Descriptions

Author or creator
Bowling, Michael
Zinkevich, Martin
Additional contributors
Subject/Keyword
Machine Learning
Regret minimization
Online learning
Artificial Intelligence
Type of item
Computing Science Technical Report
Computing science technical report ID
TR12-04
Language
English
Place
Time
Description
Online learning aims to perform nearly as well as the best hypothesis in hindsight. For some hypothesis classes, though, even finding the best hypothesis offline is challenging. In such offline cases, local search techniques are often employed and only local optimality guaranteed. For online decision-making with such hypothesis classes, we introduce local regret, a generalization of regret that aims to perform nearly as well as only nearby hypotheses. We then present a general algorithm to minimize local regret with arbitrary locality graphs. We also show how the graph structure can be exploited to drastically speed learning. These algorithms are then demonstrated on a diverse set of online problems: online disjunct learning, online Max-SAT, and online decision tree learning. This is the longer version of the same-titled paper appearing in the Proceedings of the Twenty-Ninth International Conference on Machine Learning (ICML), 2012.
Date created
2012
DOI
doi:10.7939/R3930NW06
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-24T23:38:26.804+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 482442
Last modified: 2015:10:12 20:53:47-06:00
Filename: TR12-04.pdf
Original checksum: 3081f94b23a48eea6652e13da339bdd2
Well formed: true
Valid: false
Status message: Invalid page tree node offset=131353
Activity of users you follow
User Activity Date