Online Learning and Regret Minimization

Outline

• Decision Theory Review
• Regret Minimization
• The Online Learning Setting
• Discrete Case: Prediction with Expert Advice
  • Realizable Case
  • Nonrealizable Case
    
  • Application: The Mind Reading Machine
    
• Model Combination and Hedge

Motivation

• Often, forecasting is not a single unique event, but a process that must be repeated over and over
• Forecasts must be updated in light of new data, and business decisions made on an ongoing basis
• May even need to choose a procedure in which process is entirely automated
• Example use cases
  • Web services: may need to update page every day or even every visitor
  • Large retail operation: need to predict inventories for each outlet each day
• Want a procedure which is both automated and robust
  • Not enough time for practitioner to apply judgment each time model must be changed
  • If something goes wrong, might not be able to intervene immediately
• These goals motivate online learning methods
  • A class of algorithms for making a sequence of repeated forecasting decisions
  • A distinct mode of decision theoretic analysis focused on minimizing worst-case regret

Decision Theory: Review

• Choose a forecasting rule
  • \(f_{t}:\otimes_{s=1}^{t}\mathrm{Y}\to\mathrm{Y}\)
• Observe sequence of data
  • \(\mathcal{Y}_t=\{y_s\}_{s=1}^{t}\in \otimes_{s=1}^{t} \mathrm{Y}\)
• Apply forecasting rule to obtain predicted value
  • \(\widehat{y}_{t+1}=f_{t}(\mathcal{Y}_{t})\)
• Observe realized value \(y_{t+1}\)
• Evaluate by loss function
  • \(\ell(.,.): \mathrm{Y}\times\mathrm{Y}\to\mathbb{R}^+\)
• Loss is \(\ell(y_{t+1},\widehat{y}_{t+1})\)
• Sequential setup is exactly this, but repeated for \(t=0\ldots T\)
  • Need to compare losses across periods to compare \(T\) period sequence of decisions

Sequential Loss Evaluation

• Simplest approach: use total loss \(\sum_{t=1}^{T}\ell(y_{t+1},\widehat{y}_{t+1})\) (or, equivalently, average loss \(\frac{1}{T}\sum_{t=1}^{T}\ell(y_{t+1},\widehat{y}_{t+1})\))
• Sometimes also work with weighted average loss \(\sum_{t=1}^{T}w_t\ell(y_{t+1},\widehat{y}_{t+1})\)
  • If \(w_t=\beta^t\), \(\beta\in(0,1)\), called exponential discounting: future profits discounted at interest rate if maximizing present value
• This is on top of existing issue of needing to compare performance across many sequences \(\mathcal{Y}_t\)
• Previous approaches: \(\mathcal{Y}_t\) comes from a distribution \(p(\mathcal{Y}_t)\), possibly in a family \(\mathcal{P}:=\{p(\mathcal{Y}_t,\theta),\theta\in\Theta\}\)
• Probability approach allows handling fact that multiple outcomes are possible by focusing on average case loss
  • Risk \(R_t(f)=E_{p}[\ell(y_{t+1},f_{t}(\mathcal{Y}_t))]\)
  • Statistical approach looked for low risk for every \(p\in\mathcal{P}\)
  • Bayesian approach looked for low risk on average over \(p\in{P}\), where average is with respect to prior \(\pi(\theta)\)
• These approaches work fine if probability model good description of possible sequences we are likely to face
  • Work best under stationarity or at least good model of changes over time
  • Analyst judgment and intuition can and should be used to build model or method
    
• Extend to sequential setting by considering average risk \(=\) expected average loss
  • \(\frac{1}{T}\sum_{t=1}^{T}E_{p}[\ell(y_{t+1},\widehat{y}_{t+1})]=E_{p}[\frac{1}{T}\sum_{t=1}^{T}\ell(y_{t+1},\widehat{y}_{t+1})]\)

Worst Case Analysis and No Free Lunch Theorems

• It would be even better if we had a method that can do well over all relevant sequences \(\underset{\mathcal{Y}_T}{\max}\sum_{t=1}^{T}\ell(y_{t+1},\widehat{y}_{t+1})\)
• Without additional restrictions, impossible to get nontrivial performance bounds over all sequences
• Consider case where \(\mathrm{Y}=\{0,1\}\) and \(\ell(y_{t+1},\widehat{y}_{t+1})=1\{y_{t+1}\neq \widehat{y}_{t+1}\}\). Total loss is number \(M\) of mistakes made.
• Given sequence \(\widehat{y}_{t+1}=f_{t}(\mathcal{Y}_t)\in\{0,1\}\), consider sequence \(y_{t+1}=(1-f_t(\mathcal{Y}_t))\)
  • Worst case total loss \(M=T\) for any method
• Motivates randomizing: data fixed, but choices random
  • Eg. flip a coin every period and guess 1 for Heads, 0 for Tails
  • Then no matter what sequence is, expected total loss (with respect to own choices) is \(\frac{T}{2}\)
• No Free Lunch theorems give converse relationship
  • Any algorithm producing a \(\{0,1\}\) sequence has loss \(\frac{T}{2}\) on average over all sequences
  • Corresponds to data playing the same coinflip strategy
• Implication: without some assumptions on set of data faced, only trivial results possible
  • Doing better against some sequences must mean doing worse against others
  • With a little extra info, can focus on sequences that are relevant

Regret Analysis

• Intermediate between worst and average case analysis, may single out set of sequences which matter more
• Assess relative loss in comparison to some baseline
• Let \(\mathcal{F}_t=\{f_{t,\theta}(): \otimes_{s=1}^{t}\mathrm{Y}\to\mathrm{Y}:\ \theta\in\Theta\}\) be a set of “baseline” predictors against which we want to perform well
• Let \(\mathcal{A}\) be a strategy or algorithm: sequence of decision rules \(\{f_t(\mathcal{Y}_t)\}_{t=1}^{T}\) which may depend on the observations
• The maximum total regret of strategy \(\mathcal{A}\) with respect to comparison class \(\mathcal{\Theta}\) is
  • \(reg_{T}(\mathcal{A})=\underset{\{y_{t+1}\}_{t=1}^{T}\in\otimes_{t=1}^{T}\mathrm{Y}}{\max}\left\{\sum_{t=1}^{T}\ell(y_{t+1},f_t(.))-\underset{\theta\in\Theta}{\min}\sum_{t=1}^{T}\ell(y_{t+1},f_{\theta,t}(.))\right\}\)
• Average Regret is \(\frac{1}{T}reg_{T}(\mathcal{A})\)
• Because regret is defined over all sequences, no probability distribution needed over sequences
  • But, it can be helpful to randomize to compete with possibly adversarial sequences
• A randomized algorithm/strategy \(\mathcal{A}=\{f_t(\mathcal{Y}_t,\omega_t)\}_{t=1}^{T}\) depends on auxiliary random variables \(\omega_t\sim q_t\)
• If adversary can condition on strategy but not on realizations of randomness, measure of loss is expected regret
  • \(\underset{\{y_{t+1}\}_{t=1}^{T}\in\otimes_{t=1}^{T}\mathrm{Y}}{\max}\mathbf{E}\left\{\sum_{t=1}^{T}\ell(y_{t+1},f_t(.,\omega_t))-\underset{\theta\in\Theta}{\min}\sum_{t=1}^{T}\ell(y_{t+1},f_{\theta,t}(.))\right\}\)
  • Here, expectation is only over randomness in own decisions

Interpretation of Regret

• An algorithm with low regret performs nearly as well as the best rule in the baseline set in hindsight, after the sequence was seen, for any possible sequence
• Per no free lunch result, total loss on some sequences may be (indeed, has to be) terrible
• But if regret is low, this means that best rule in comparison class also did terribly on that sequence
  • Conversely, whenever some rule does well on a sequence, a low regret strategy also does well
• Low expected regret methods perform well relative to the best baseline rule on average, for any possible sequence
  • Different draws of randomization may do better or worse
• Regret captures situations where evaluation is against a benchmark
  • Either explicitly as it is for hedge fund managers
  • Or implicitly if you are competing with a group, and you can blame others for your mistakes
• “Worldly wisdom teaches that it is better for reputation to fail conventionally than to succeed unconventionally.” Keynes (1936)
• Less cynically, useful if you care more about accuracy in some sequences than others
  • Different from probability, which captures this by “weights” these sequences
  • May care about them more either because they are more likely or because performance in that case is important

Example 1: Prediction with Expert Advice

• Want to predict sequence of binary outcomes \(y_{t+1}\in\{0,1\}\) with 0-1 loss
  • User will click/not click on ad, Product will sell or not sell, Recession this quarter or no
• We have access to a set of \(N\) “experts” \(\Theta=\{i\in 1\ldots N\}\) who each round give us their prediction \(f_{\theta,t}=\widehat{y}_{i,t+1}\in \{0,1\}\) of \(y_{t+1}\)
  • Experts may be real human forecasters, like those surveyed by the Survey of Professional Forecasters or the Wall Street Journal Economic Survey
  • Or they may be algorithms: eg. logistic regression, some bespoke Bayesian model, or some state-of-the-art machine learning thing
  • Or just simple rules: Always 0, Always 1, Alternate, 1 on primes, etc
• Goal is to use all this info to make a forecast, recognizing that some experts may be more accurate than others
• Experts are “black boxes”: often impossible or too difficult to figure out where forecast comes from or why
  • Only use history of past performance to evaluate
• Best expert makes \(M^*=\underset{i\in1\ldots N}{min}\sum_{t=1}^{T}1\{y_{t+1}\neq \widehat{y}_{i,t+1}\}\) mistakes
• Expected regret of an online learning procedure \(\mathcal{A}\) is \(\mathbf{E}\sum_{t=1}^{T}1\{y_{t+1}\neq \widehat{y}_{t+1}\}-M^*\)
• Goal is to make not many more mistakes than best expert

Example 2: Online Regression

• Let \(y_{t}\in\mathrm{Y}\) and \(\ell(.,.):\ \mathrm{Y}\times\mathrm{Y}\to B\subset\mathbb{R}\), \(B\) a bounded set
• Boundedness may come from \(\mathbf{Y}\) bounded, as in outcomes known to take limited range
• Needed for regret analysis, because if unbounded, worst case may achieve unbounded regret
  • Worst case regret analysis useful if bad outcome is “customer doesn’t click the ad this time”
  • Less so if worst outcome is “humanity perishes in nuclear war”
  • Even though early theory came from David Blackwell at the RAND corporation, which supported early game and decision theory research for purpose of Cold War nuclear strategic planning
• Set \(\Theta=\{\beta\in\mathbb{R}^d: \left\Vert\beta\right\Vert\leq C \}\) and \(\mathcal{F}_t=\{z_t^{\prime}\beta, \beta\in\Theta\}\)
  • \(z_t\) may be external predictors, lagged values, etc
• Regret of a procedure \(\mathcal{A}\) given by \(\underset{\{y_{t+1}\}_{t=1}^{T}\in\otimes_{t=1}^{T}\mathrm{Y}}{\max}\mathbf{E}\left\{\sum_{t=1}^{T}\ell(y_{t+1},f_t(.))-\underset{\theta\in\Theta}{\min}\sum_{t=1}^{T}\ell(y_{t+1},z_t^\prime\beta)\right\}\)
• Goal is to perform as well as best regression model in hindsight

Algorithms

• What kind of algorithms will produce a low regret in a particular problem?
• Ideally, we would find method that solves minimax regret problem \(\underset{\mathcal{A}}{\min}Reg_{T}(\mathcal{A})\)
• Minimizes over all possible sequences of prediction rules the maximum over all sequences the loss relative to the best sequence-specific benchmark
  • This is insanely hard computationally and nobody ever does it
• Instead, introduce some popular simple methods and show that they perform reasonably
• Method may be proper: choosing an element of the comparison set \(f_t\in\mathcal{F}_t\) each time
  • E.g. prediction must be same as that of a particular expert, or must be linear
  • If randomized, may choose a random element of \(\mathcal{F}_t\)
• Or it may be improper: \(f_t\notin\mathcal{F}_t\)
  • Using advice of all experts, combine in some way which is not the same as any particular expert
  • Use possibly nonlinear function, and compare to best linear function
• Will explore examples of both types
  • Improper setting, which is less restricted, often yields stronger results, but properness sometimes a genuine restriction

Realizable Case

• Some especially simple problems are realizable: the best possible predictor is in the comparison set \(\mathcal{F}_t\)
  • \(\underset{\theta\in\Theta}{\min}\sum_{t=1}^{T}\ell(y_{t+1},f_{t,\theta})=0\)
  • Regret minimization then equivalent to minimax case
• Not realistic outside of settings where goal is to ascertain some unambiguous matter of fact
  • But useful to show how analysis works
• In expert advice setting, corresponds to \(M^*=0\): at least one expert knows the true sequence
  • Goal is to find this expert as quickly with as few mistakes as possible
• A possible algorithm to use here, with good properties, is Majority Vote
  • Give each expert an initial weight \(w_{i,1}=1\), then at each t, do as follows:
  • Choose 1 if \(\sum_{i=1}^{n}w_{i,t}1\{\widehat{y}_{i,t+1}=1\}>\sum_{i=1}^{n}w_{i,t}1\{\widehat{y}_{i,t+1}=0\}\), 0 otherwise
    • Vote with majority of experts
  • After \(y_{t+1}\) realized, set weight of any expert \(i\) which made a mistake to 0
• If we know best rule is exact, can ignore any rule as soon as it makes a mistake

Analysis of Majority Vote

• Let \(W_t=\sum_{i=1}^{n}w_{i,t}\) be the number of remaining experts after \(t\) steps
• If in period \(t\) a mistake is made, more than half of experts must have been wrong, so \(W_{t+1}\leq\frac{W_t}{2}\)
• If \(M\) is total number of mistakes over \(T\) rounds then \(W_{T+1}\leq n 2^{-M}\)
• Further \(W_{T+1}\geq 1\), since by realizability, at least one expert doesn’t make mistakes
• Rearranging \(n 2^{-M}\geq 1\), \(M\leq \log_{2}n\)
  • Regret satisfies bound \(reg_{T}(\mathcal{A})\leq\log_{2}n\)
• Average regret \(\leq\frac{\log_{2}n}{T}\) goes to 0 as long as \(n\) not exponential in \(T\)
  • Can deal with very large number of wrong predictors and still make few mistakes
• In general, and certainly for a proper algorithm, vanishing average regret is best that can be hoped for
  
• Compare method with minority vote: among those that haven’t made a mistake, choose smallest group
  • Could remove as few as 1 expert per mistake, leading to up to \(n-1\) mistakes in worst case

Non-realizable Case

• Outside of realizable case, problem much harder
• Suppose expert set contains i,j s.t. \(f_{i,t}=0\) \(\forall t\) and \(f_{j,t}=1\) \(\forall t\)
• Take any algorithm depending only on past data to pick outcome \(\widehat{y}_{t+1}\)
  • Then sequence which always picks \(y_{t+1}=1-\widehat{y}_{t+1}\) is possible, giving \(T\) mistakes
• Further, this sequence either has \(\leq\frac{1}{2}\) 1s or \(\leq\frac{1}{2}\) 0s
  • So either \(i\) or \(j\) has loss \(\leq\frac{T}{2}\), respectively
• Regret is \(\geq T-\frac{T}{2}=\frac{T}{2}\): allowing comparators does not make the worst case that much better
• But, randomized algorithms can do fine in terms of expected regret
  • Let \(p_{i,t}\) be probability of choosing expert \(i\) in round \(t\)
  • Then Expected regret is \(\sum_{t=1}^{T}\sum_{i=1}^{n}p_{i,t}|y_{t+1}-\widehat{y}_{i,t+1}|-\underset{i}{\min}\sum_{t=1}^{T}|y_{t+1}-\widehat{y}_{i,t+1}|\)

Randomized Weighted Majority

• Simple changes to Majority Vote lead to low expected regret in non-realizable case
• Sample with probability proportional to weight
  • \(p_{i,t}=\frac{w_{i,t}}{\sum_{i=1}^{n}w_{i,t}}\)
• Since even best expert may make mistakes, don’t discard completely
  • Instead, if expert \(i\) makes mistake, set \(w_{i,t+1}=(1-\epsilon)w_{i,t}\)
• Analysis (cf Hazan 2015) similar to majority vote: let \(M(i)\) be # of mistakes of expert \(i\)
  • \(W_T=\sum_{i=1}^{n}w_{i,T}\) has lower bound of \((1-\epsilon)^{M(i)}\)
  • Can show upper bound of \(n\exp(-\epsilon\mathbf{E}M)\) in terms of total mistakes
• Results imply regret \(\mathbf{E}M-\underset{i}{\min}M(i)\leq \epsilon T +\frac{\log n}{\epsilon}\)
• Choosing \(\epsilon=\sqrt{\frac{\log n}{T}}\), upper bound is \(2\sqrt{T\log n}\)
• Method has average expected regret \(\leq \frac{2\sqrt{\log N}}{\sqrt{T}}\)
  • Goes to 0 with \(T\), and depends only weakly on number of experts

Claude Shannon’s Mind-Reading Machine

• A simple example of online binary prediction: a machine that predicts user’s next choice, left or right
  • If machine guesses right, it gets a point, if wrong, user gets a point
  • Goal is to build machine that can win every time
• In principle, user could guarantee \(\frac{T}{2}\) points and a tie just by random guessing
• In practice, humans are really bad at randomness without tools like coins, dice, computers
• With online algorithm, can build machine that usually wins, as Claude Shannon did at Bell labs in 1950s

Photo: Poundstone (2014)

Hedge

• Binary case can be generalized to experts making any kind of prediction, with arbitrary non-negative loss function
  • Any output: discrete, scalar, vector, etc, all permitted
  • Sufficient that \(\ell^2(.,.)\leq B\): bounded loss, eg due to bounded outcomes
• Hedge algorithm takes in \(n\) experts, with initial weights \(w_{i,0}=1\)
• Predict \(y_{t+1}\) using expert \(i\) forecast \(\widehat{y}_{i,t+1}\) with probability \(p_{i,t}=\frac{w_{i,t}}{\sum_{i=1}^nw_{i,t}}\)
• Observe losses \(\ell_{i,t}=\ell(y_{t+1},\widehat{y}_{i,t+1})\) for each expert
• Update weights to \(w_{i,t+1}=w_{i,t}\exp(-\epsilon\ell_{i,t})\) and repeat for next forecast
• Analysis shows expected regret bounded by \(\epsilon\sum_{t=1}^{T}\sum_{i=1}^{n}p_{i,t}\ell^2_{i,t} +\frac{\log n}{\epsilon}\)
• Choosing \(\epsilon=\sqrt{\frac{\log n}{BT}}\), upper bound is \(2\sqrt{B T\log n}\)
• Regret grows sublinearly in \(T\), depends weakly on number of experts

Hedge: Applications

• Hedge provides alternative approach to model selection
• Can use for hyperparameter choice like AIC/BIC/Cross-validation etc
• Allows combining input of large set of models of diverse types
  • Choice depends on past performance only, not model structure
  • Inputs can be simple or complicated, or even based on human judgment
  • Can’t use AIC to compare VAR, random forest, and a CNBC pundit
• Does not require stationarity or correct specification or existence of a probability distribution over outcomes
  • Does require boundedness: useful for outcomes with known range
• Guarantees performance near best in class on realized outcomes
  • Contrast oracle guarantees: performance near best in class for risk
• Rapidly (exponentially fast) downweights bad models, maintains weights on those with good performance
• Essentially random near start of run: good performance coming from middle-to-end
  • This is typical feature of online algorithms
  • Choice of update speed \(\epsilon\) depends on horizon \(T\)

General Purpose Methods: Online Convex Optimization

• Can we move beyond case of finite comparison class of “experts” to methods that apply to more general variable structures and comparison classes?
• One large class of problems where this is feasible are online convex optimization problems
• If realized loss functions \(\ell(y_{t+1},.)\) are convex in \(f_t(.)\), there are general purpose methods with strong regret guarantees
• Convexity means \(\ell(y_{t+1},ax+(1-a)z)\leq a\ell(y_{t+1},x)+(1-a)\ell(y_{t+1},z)\) for any \(a\in[0,1]\)
  • Bowl shaped functions
  • Contains quadratic loss, absolute value loss, linear loss, etc
  • Does not contain discrete case: randomization needed to make loss linear
• Hedge and online regression with convex \(\ell\) are special cases of this setup
  
• Next class: general algorithms and conditions
  • Preview: Look a lot like (regularized) ERM

Conclusions

• Online learning methods provide principled way to evaluate and implement stream of iteratively updated predictions
• Regret based analyses ensure robustness against arbitrary sequences, relative to a set of comparison models
  • An algorithm that produces low total expected regret over time can be trusted to have adequate performance regardless of what kind of new data comes in
• For finite model sets, a useful class of procedures puts weights on the models based on past performance, then chooses randomly based on weights
  • Hedge algorithm takes many models or experts as inputs, outputs low expected regret sequence of predictions
  • Randomization critical, as without it worst case regret is linear in \(T\)

References

• Elad Hazan Introduction to Online Convex Optimization Foundations and Trends in Optimization, vol. 2, no. 3-4 (2015) 157–325.
  • Textbook on online learning, from an optimization theory perspective
• John Maynard Keynes The General Theory of Employment, Interest, and Money (1936)
  • Aside from introducing whole framework of 20th century macroeconomics, insightful chapters on investor psychology
• Shai Shalev-Shwartz Online Learning and Online Convex Optimization Foundations and Trends in Machine Learning Vol. 4, No. 2 (2011) 107–194
  • Shorter intro to online learning