TY - GEN
T1 - The last-step minimax algorithm
AU - Takimoto, Eiji
AU - Warmuth, Manfred K.
N1 - Funding Information:
Supported by NSF grant CCR-9821087.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
PY - 2000
Y1 - 2000
N2 - We consider on-line density estimation with a parameterized density from an exponential family. In each trial t the learner predicts a parameter θt. Then it receives an instance xt chosen by the adversary and incurs loss -ln p(xt|θt) which is the negative log-likelihood of xt w.r.t. the predicted density of the learner. The performance of the learner is measured by the regret defined as the total loss of the learner minus the total loss of the best parameter chosen off-line. We develop an algorithm called the Last-step Minimax Algorithm that predicts with the minimax optimal parameter assuming that the current trial is the last one. For one-dimensional exponential families, we give an explicit form of the prediction of the Last-step Minimax Algorithm and show that its regret is O(ln T), where T is the number of trials. In particular, for Bernoulli density estimation the Last-step Minimax Algorithm is slightly better than the standard Krichevsky-Trofimov probability estimator.
AB - We consider on-line density estimation with a parameterized density from an exponential family. In each trial t the learner predicts a parameter θt. Then it receives an instance xt chosen by the adversary and incurs loss -ln p(xt|θt) which is the negative log-likelihood of xt w.r.t. the predicted density of the learner. The performance of the learner is measured by the regret defined as the total loss of the learner minus the total loss of the best parameter chosen off-line. We develop an algorithm called the Last-step Minimax Algorithm that predicts with the minimax optimal parameter assuming that the current trial is the last one. For one-dimensional exponential families, we give an explicit form of the prediction of the Last-step Minimax Algorithm and show that its regret is O(ln T), where T is the number of trials. In particular, for Bernoulli density estimation the Last-step Minimax Algorithm is slightly better than the standard Krichevsky-Trofimov probability estimator.
UR - http://www.scopus.com/inward/record.url?scp=84974698795&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84974698795&partnerID=8YFLogxK
U2 - 10.1007/3-540-40992-0_21
DO - 10.1007/3-540-40992-0_21
M3 - Conference contribution
AN - SCOPUS:84974698795
SN - 9783540412373
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 279
EP - 290
BT - Algorithmic Learning Theory - 11th International Conference, ALT 2000, Proceedings
A2 - Arimura, Hiroki
A2 - Jain, Sanjay
A2 - Sharma, Arun
PB - Springer Verlag
T2 - 11th International Conference on Algorithmic Learning Theory, ALT 2000
Y2 - 11 December 2000 through 13 December 2000
ER -