Optimal Online Prediction in Adversarial Environments Peter Bartlett EECS and Statistics UC Berkeley http://www.cs.berkeley.edu/∼bartlett Online Prediction (cid:73) Probabilistic Model (cid:73) Batch: independentrandomdata. (cid:73) Aimforsmallexpectedlosssubsequently. (cid:73) Adversarial Model (cid:73) Online: Sequenceofinteractionswithanadversary. (cid:73) Aimforsmallcumulativelossthroughout. Online Learning: Motivations 1. Adversarial model is appropriate for (cid:73) Computer security. (cid:73) Computational finance. WebSpamChallenge(www.iw3c2.org) ACM Online Learning: Motivations 2. Understanding statistical prediction methods. (cid:73) Many statistical methods, based on probabilistic assumptions, can be effective in an adversarial setting. (cid:73) Analyzing their performance in adversarial settings provides perspective on their robustness. (cid:73) We would like violations of the probabilistic assumptions to have a limited impact. Online Learning: Motivations 3. Online algorithms are also effective in probabilistic settings. (cid:73) Easy to convert an online algorithm to a batch algorithm. (cid:73) Easy to show that good online performance implies good i.i.d. performance, for example. Prediction in Probabilistic Settings (cid:73) i.i.d. (X,Y),(X ,Y ),...,(X ,Y ) from X ×Y. 1 1 n n (cid:73) Use data (X ,Y ),...,(X ,Y ) to choose f : X → A with 1 1 n n n small risk, R(f ) = E(cid:96)(Y,f (X)). n n