Automatically assigned DDC number: 00631
Manually assigned DDC number: 00631
Number of references: 8
Title: On-line Learning and the Metrical Task System Problem
Author:
Author:
Subject: Avrim Blum,Carl Burch On-line Learning and the Metrical Task System Problem
Description: . The problem of combining expert advice, studied extensively in the Computational Learning Theory literature, and the Metrical Task System (MTS) problem, studied extensively in the area of On-line Algorithms, contain a number of interesting similarities. In this paper we explore the relationship between these problems and show how algorithms designed for each can be used to achieve good bounds and new approaches for solving the other. Specific contributions of this paper include: ffl An analysis of how two recent algorithms for the MTS problem can be applied to the problem of tracking the best expert in the "decision-theoretic" setting, providing good bounds and an approach of a much different flavor from the well-known multiplicative-update algorithms. ffl An analysis showing how the standard randomized Weighted Majority (or Hedge) algorithm can be used for the problem of "combining on-line algorithms on-line", giving much stronger guarantees than the results of Azar et al [1] when...
Contributor: The Pennsylvania State University CiteSeer Archives
Publisher: unknown
Date: 1999-04-27
Pubyear: 1997
Format: ps
Identifier: http://citeseer.ist.psu.edu/167755.html
Source: http://www-cgi.cs.cmu.edu/afs/cs.cmu.edu/user/cburch/www/pub/bb_learning_mts.jv.ps.gz
Language: en
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Relation:
Rights: unrestricted
<?xml version="1.0" encoding="UTF-8"?>
<references_metadata>
<rec ID="/156038.html" Type="inproceedings" CiteSeer_Book="SODA ACMSIAM Symposium on Discrete Algorithms A Conference on Theoretical and Experimental Analysis of Discrete Algorithms" CiteSeer_Volume="" Title="On-line Choice of On-line Algorithms,">
<identifier Org="ISBN:0897917855" Paper_ID="/156038.html" Extracted="0897917855" />
<identifier Org="ISBN:0898713137" Paper_ID="/156038.html" Extracted="0898713137" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.5" />
<identifier Org="ISBN:0898713293" Paper_ID="/156038.html" Extracted="0898713293" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.5" />
<identifier Org="ISBN:1581136617" Paper_ID="/156038.html" Extracted="1581136617" />
</rec>
<rec ID="/375139.html" Type="inproceedings" CiteSeer_Book="IEEE Symposium on Foundations of Computer Science" CiteSeer_Volume="" Title="Probabilistic Approximations of Metric Spaces and Its Algorithmic Applications,">
<identifier Org="ISBN:0818681985" Paper_ID="/375139.html" Extracted="0818681985" />
<identifier Org="ISBN:0897918886" Paper_ID="/375139.html" Extracted="0897918886" />
<identifier Org="ISBN:0898713552" Paper_ID="/375139.html" Extracted="0898713552" DDC="519.4/0285/51" Normalized_DDC="5194028551" Normalized_Weight="0.1" />
<identifier Org="ISBN:0898715385" Paper_ID="/375139.html" Extracted="0898715385" />
<identifier Org="ISBN:0898715857" Paper_ID="/375139.html" Extracted="0898715857" DDC="005.133" Normalized_DDC="005133" Normalized_Weight="0.1" />
<identifier Org="ISBN:0898716055" Paper_ID="/375139.html" Extracted="0898716055" />
<identifier Org="ISBN:1581136749" Paper_ID="/375139.html" Extracted="1581136749" />
<identifier Org="ISBN:1581138741" Paper_ID="/375139.html" Extracted="1581138741" />
<identifier Org="ISBN:1581139608" Paper_ID="/375139.html" Extracted="1581139608" />
<identifier Org="ISBN:1584884657" Paper_ID="/375139.html" Extracted="1584884657" DDC="621.384" Normalized_DDC="621384" Normalized_Weight="0.1" />
<identifier Org="ISBN:1595936319" Paper_ID="/375139.html" Extracted="1595936319" />
<identifier Org="ISBN:3540200649" Paper_ID="/375139.html" Extracted="3540200649" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540212361" Paper_ID="/375139.html" Extracted="3540212361" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540282394" Paper_ID="/375139.html" Extracted="3540282394" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540322124" Paper_ID="/375139.html" Extracted="3540322124" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540323015" Paper_ID="/375139.html" Extracted="3540323015" />
<identifier Org="ISBN:3540699007" Paper_ID="/375139.html" Extracted="3540699007" />
<identifier Org="ISBN:3540709177" Paper_ID="/375139.html" Extracted="3540709177" DDC="004" Normalized_DDC="004" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540755195" Paper_ID="/375139.html" Extracted="3540755195" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.1" />
<identifier Org="ISBN:981270146X" Paper_ID="/375139.html" Extracted="981270146X" DDC="681.2" Normalized_DDC="6812" Normalized_Weight="0.1" />
</rec>
<rec ID="/440364.html" Type="article" CiteSeer_Book="J Algorithms" CiteSeer_Volume="12" Title="Competitive Paging Algorithms,">
<identifier Org="ISBN:0387301623" Paper_ID="/440364.html" Extracted="0387301623" DDC="518.103" Normalized_DDC="518103" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0780331214" Paper_ID="/440364.html" Extracted="0780331214" />
<identifier Org="ISBN:0849326494" Paper_ID="/440364.html" Extracted="0849326494" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0898712718" Paper_ID="/440364.html" Extracted="0898712718" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0898713552" Paper_ID="/440364.html" Extracted="0898713552" DDC="519.4/0285/51" Normalized_DDC="5194028551" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:0898713668" Paper_ID="/440364.html" Extracted="0898713668" />
<identifier Org="ISBN:0898714109" Paper_ID="/440364.html" Extracted="0898714109" />
<identifier Org="ISBN:0898714907" Paper_ID="/440364.html" Extracted="0898714907" />
<identifier Org="ISBN:089871558X" Paper_ID="/440364.html" Extracted="089871558X" />
<identifier Org="ISBN:0898715857" Paper_ID="/440364.html" Extracted="0898715857" DDC="005.133" Normalized_DDC="005133" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540287027" Paper_ID="/440364.html" Extracted="3540287027" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540291180" Paper_ID="/440364.html" Extracted="3540291180" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540412557" Paper_ID="/440364.html" Extracted="3540412557" DDC="001.64" Normalized_DDC="00164" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540424938" Paper_ID="/440364.html" Extracted="3540424938" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540620486" Paper_ID="/440364.html" Extracted="3540620486" DDC="001.64" Normalized_DDC="00164" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540643591" Paper_ID="/440364.html" Extracted="3540643591" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540729135" Paper_ID="/440364.html" Extracted="3540729135" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540755195" Paper_ID="/440364.html" Extracted="3540755195" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />
<identifier Org="ISBN:3540771182" Paper_ID="/440364.html" Extracted="3540771182" />
<identifier Org="ISBN:354077890X" Paper_ID="/440364.html" Extracted="354077890X" />
</rec>
<rec ID="/10394.html" Type="inproceedings" CiteSeer_Book="European Conference on Computational Learning Theory" CiteSeer_Volume="" Title="A decision-theoretic generalization of on-line learning and an application to boosting,">
<identifier Org="ISBN:0262025507" Paper_ID="/10394.html" Extracted="0262025507" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0262194503" Paper_ID="/10394.html" Extracted="0262194503" />
<identifier Org="ISBN:0262511290" Paper_ID="/10394.html" Extracted="0262511290" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0262731444" Paper_ID="/10394.html" Extracted="0262731444" DDC="153.03" Normalized_DDC="15303" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0821841955" Paper_ID="/10394.html" Extracted="0821841955" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1402078676" Paper_ID="/10394.html" Extracted="1402078676" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1581130570" Paper_ID="/10394.html" Extracted="1581130570" />
<identifier Org="ISBN:1852334452" Paper_ID="/10394.html" Extracted="1852334452" DDC="005.3" Normalized_DDC="0053" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540005293" Paper_ID="/10394.html" Extracted="3540005293" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540140409" Paper_ID="/10394.html" Extracted="3540140409" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540211098" Paper_ID="/10394.html" Extracted="3540211098" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540265562" Paper_ID="/10394.html" Extracted="3540265562" />
<identifier Org="ISBN:3540403698" Paper_ID="/10394.html" Extracted="3540403698" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540405046" Paper_ID="/10394.html" Extracted="3540405046" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540407200" Paper_ID="/10394.html" Extracted="3540407200" />
<identifier Org="ISBN:354041066X" Paper_ID="/10394.html" Extracted="354041066X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540421440" Paper_ID="/10394.html" Extracted="3540421440" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540618635" Paper_ID="/10394.html" Extracted="3540618635" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540742719" Paper_ID="/10394.html" Extracted="3540742719" />
<identifier Org="ISBN:3540752242" Paper_ID="/10394.html" Extracted="3540752242" />
</rec>
<rec ID="/9859.html" Type="inproceedings" CiteSeer_Book="International Conference on Machine Learning" CiteSeer_Volume="" Title="Tracking the Best Expert,">
<identifier Org="ISBN:0262195682" Paper_ID="/9859.html" Extracted="0262195682" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1" />
<identifier Org="ISBN:0387001522" Paper_ID="/9859.html" Extracted="0387001522" DDC="519.2/87" Normalized_DDC="519287" Normalized_Weight="0.1" />
<identifier Org="ISBN:0521841089" Paper_ID="/9859.html" Extracted="0521841089" DDC="519.3" Normalized_DDC="5193" Normalized_Weight="0.1" />
<identifier Org="ISBN:0769521258" Paper_ID="/9859.html" Extracted="0769521258" />
<identifier Org="ISBN:0780358589" Paper_ID="/9859.html" Extracted="0780358589" />
<identifier Org="ISBN:0780382552" Paper_ID="/9859.html" Extracted="0780382552" />
<identifier Org="ISBN:0780386086" Paper_ID="/9859.html" Extracted="0780386086" />
<identifier Org="ISBN:0897918886" Paper_ID="/9859.html" Extracted="0897918886" />
<identifier Org="ISBN:0897918916" Paper_ID="/9859.html" Extracted="0897918916" />
<identifier Org="ISBN:1420081918" Paper_ID="/9859.html" Extracted="1420081918" DDC="332.63/2042" Normalized_DDC="332632042" Normalized_Weight="0.1" />
<identifier Org="ISBN:1558603778" Paper_ID="/9859.html" Extracted="1558603778" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.1" />
<identifier Org="ISBN:1558604197" Paper_ID="/9859.html" Extracted="1558604197" />
<identifier Org="ISBN:1581130570" Paper_ID="/9859.html" Extracted="1581130570" />
<identifier Org="ISBN:3540265562" Paper_ID="/9859.html" Extracted="3540265562" />
<identifier Org="ISBN:3540404082" Paper_ID="/9859.html" Extracted="3540404082" DDC="006.3/2" Normalized_DDC="00632" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540413855" Paper_ID="/9859.html" Extracted="3540413855" DDC="510 s" Normalized_DDC="51" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540423435" Paper_ID="/9859.html" Extracted="3540423435" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.1" />
<identifier Org="ISBN:354043836X" Paper_ID="/9859.html" Extracted="354043836X" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.1" />
<identifier Org="ISBN:3540635777" Paper_ID="/9859.html" Extracted="3540635777" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.1" />
</rec>
<rec ID="/21505.html" Type="article" CiteSeer_Book="Theoretical Computer Science" CiteSeer_Volume="194" Title="Randomized algorithms for metrical task systems,">
<identifier Org="ISBN:0387301623" Paper_ID="/21505.html" Extracted="0387301623" DDC="518.103" Normalized_DDC="518103" Normalized_Weight="0.2" />
<identifier Org="ISBN:078033762X" Paper_ID="/21505.html" Extracted="078033762X" />
<identifier Org="ISBN:0897918886" Paper_ID="/21505.html" Extracted="0897918886" />
<identifier Org="ISBN:0897918916" Paper_ID="/21505.html" Extracted="0897918916" />
<identifier Org="ISBN:1581131844" Paper_ID="/21505.html" Extracted="1581131844" />
<identifier Org="ISBN:354034666X" Paper_ID="/21505.html" Extracted="354034666X" DDC="004.6" Normalized_DDC="0046" Normalized_Weight="0.2" />
<identifier Org="ISBN:3540424938" Paper_ID="/21505.html" Extracted="3540424938" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.2" />
<identifier Org="ISBN:3540602208" Paper_ID="/21505.html" Extracted="3540602208" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.2" />
<identifier Org="ISBN:3540679960" Paper_ID="/21505.html" Extracted="3540679960" DDC="004/.01/5114" Normalized_DDC="004015114" Normalized_Weight="0.2" />
</rec>
<rec ID="/42171.html" Type="inproceedings" CiteSeer_Book="IEEE Symposium on Foundations of Computer Science" CiteSeer_Volume="" Title="The Weighted Majority Algorithm,">
<identifier Org="ISBN:0262195348" Paper_ID="/42171.html" Extracted="0262195348" />
<identifier Org="ISBN:0262510952" Paper_ID="/42171.html" Extracted="0262510952" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:0780366573" Paper_ID="/42171.html" Extracted="0780366573" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:0818619821" Paper_ID="/42171.html" Extracted="0818619821" DDC="004" Normalized_DDC="004" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:0849326494" Paper_ID="/42171.html" Extracted="0849326494" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:0897916115" Paper_ID="/42171.html" Extracted="0897916115" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:1558603778" Paper_ID="/42171.html" Extracted="1558603778" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:1581130570" Paper_ID="/42171.html" Extracted="1581130570" />
<identifier Org="ISBN:1878289845" Paper_ID="/42171.html" Extracted="1878289845" DDC="658.4038" Normalized_DDC="6584038" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540221441" Paper_ID="/42171.html" Extracted="3540221441" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540233563" Paper_ID="/42171.html" Extracted="3540233563" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540423435" Paper_ID="/42171.html" Extracted="3540423435" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540437754" Paper_ID="/42171.html" Extracted="3540437754" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540437819" Paper_ID="/42171.html" Extracted="3540437819" DDC="670/.285/63" Normalized_DDC="67028563" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540440666" Paper_ID="/42171.html" Extracted="3540440666" DDC="006.4/2" Normalized_DDC="00642" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540626859" Paper_ID="/42171.html" Extracted="3540626859" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:354065013X" Paper_ID="/42171.html" Extracted="354065013X" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.06666666666666667" />
<identifier Org="ISBN:3540729259" Paper_ID="/42171.html" Extracted="3540729259" />
<identifier Org="ISBN:3540879862" Paper_ID="/42171.html" Extracted="3540879862" />
</rec>
<rec ID="/27078.html" Type="article" CiteSeer_Book="Information and Computation" CiteSeer_Volume="148" Title="Unfair Problems and Randomized Algorithms for Metrical Task Systems,">
<identifier Org="ISBN:078033762X" Paper_ID="/27078.html" Extracted="078033762X" />
<identifier Org="ISBN:0897918886" Paper_ID="/27078.html" Extracted="0897918886" />
<identifier Org="ISBN:0897918916" Paper_ID="/27078.html" Extracted="0897918916" />
<identifier Org="ISBN:1581131844" Paper_ID="/27078.html" Extracted="1581131844" />
<identifier Org="ISBN:3540424938" Paper_ID="/27078.html" Extracted="3540424938" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.5" />
<identifier Org="ISBN:3540679960" Paper_ID="/27078.html" Extracted="3540679960" DDC="004/.01/5114" Normalized_DDC="004015114" Normalized_Weight="0.5" />
</rec>
<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="On-line Learning and the Metrical Task System Problem">
<identifier Org="ISBN:0521841089" Paper_ID="SELF" Extracted="0521841089" DDC="519.3" Normalized_DDC="5193" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:0897918916" Paper_ID="SELF" Extracted="0897918916" />
<identifier Org="ISBN:1558607781" Paper_ID="SELF" Extracted="1558607781" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:1581131844" Paper_ID="SELF" Extracted="1581131844" />
<identifier Org="ISBN:3540407200" Paper_ID="SELF" Extracted="3540407200" />
<identifier Org="ISBN:3540423435" Paper_ID="SELF" Extracted="3540423435" DDC="006.3/1" Normalized_DDC="00631" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:354043836X" Paper_ID="SELF" Extracted="354043836X" DDC="006.31" Normalized_DDC="00631" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:3540673067" Paper_ID="SELF" Extracted="3540673067" DDC="004" Normalized_DDC="004" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:3540679960" Paper_ID="SELF" Extracted="3540679960" DDC="004/.01/5114" Normalized_DDC="004015114" Normalized_Weight="0.16666666666666666" />
<identifier Org="ISBN:8173194904" Paper_ID="SELF" Extracted="8173194904" />
</rec>
</references_metadata>