What Can ML Do For Algorithms?

Sergei Vassilvitskii
HALG 2019GoogleTheme
Machine Learning is everywhere…
– Self driving cars
– Speech to speech translation– Search ranking–…

ThemeMachine Learning is everywhere…
– Self driving cars
– Speech to speech translation– Search ranking–…

…but it’s not helping us get better theorems

Motivating Example
Given a sorted array of integers A[1…n], and a query q check if qis in the array.

24711162237

738

4488

8993949596

9798

Motivating Example
Given a sorted array of integers A[1…n], and a query q check if q
is in the array.

24711162237738

448889939495969798

Motivating Example
Given a sorted array of integers A[1…n], and a query q check if q
is in the array.

24711162237

738

448889939495

96

9798

Motivating Example
Given a sorted array of integers A[1…n], and a query q check if q
is in the array.

24711162237

738

448889939495

969798

Motivating Example
Given a sorted array of integers A[1…n], and a query q check if q
is in the array.

24711162237

7– Look up time: O(log n)38448889939495969798

Motivating Example
Given a sorted array of integers A[1…n], and a query q check if q
is in the array.

24711162237

38

4488899394

959697987– Train a predictor h to learn where q should appear. [Kraska et al.’18]– Then proceed via doubling binary searchMotivating Example
Given a sorted array of integers A[1…n], and a query q check if q
is in the array.

2471116223738448889939495969798h

7– Train a predictor h to learn where q should appear. [Kraska et al.’18]– Then proceed via doubling binary searchMotivating Example
Given a sorted array of integers A[1…n], and a query q check if q
is in the array.

2471116223738448889939495969798h

7– Train a predictor h to learn where q should appear. [Kraska et al.’18]– Then proceed via doubling binary searchMotivating Example
Given a sorted array of integers A[1…n], and a query q check if q
is in the array.

2471116223738

448889939495969798

h

7– Train a predictor h to learn where q should appear. [Kraska et al.’18]– Then proceed via doubling binary searchEmpirical Slide [Kraska et al. 2018]– Smaller Index– Faster lookups when error is low, including ML costMotivating Example
Given a sorted array of integers A[1…n], and a query q check if q
is in the array.
h24711162237387448889

9394

95

96

9798

⌘1Analysis:– Let ⌘1 = |h(q)opt(q)| be the absolute error of the predicted position– Running time: O(log ⌘1 )• Can be made practical (must worry about speed & accuracy of predictions)

More on the analysis
Comparing– Classical: O(log n)– Learning augmented: O(log ⌘1 )Results:– Consistent: perfect predictions recover optimal (constant) lookup times.
– Robust: even if predictions are bad, not (much) worse than classicalMore on the analysis
Comparing– Classical: O(log n)– Learning augmented: O(log ⌘1 )Results:– Consistent: perfect predictions recover optimal (constant) lookup times.
– Robust: even if predictions are bad, not (much) worse than classical

Punchline:– Use Machine Learning together with Classical Algorithms to get better results.

Outline
Introduction
Motivating Example
Learning Augmented Algorithms– Overview– Online Algorithms– Streaming Algorithms– Data Structures
Conclusion

Learning Augmented Algorithms
Nascent Area with a number of recent results:– Build better data structures• Indexing: Kraska et al. 2018
• Bloom Filters: Mitzenmacher 2018

– Improve Competitive and Approximation Ratios• Pricing : MedinaV 2017,• Caching: LykourisV 2018
• Scheduling: Kumar et al. 2018, Lattanzi et al. 2019, Mitzenmacher 2019

– Reduce running times• Branch and Bound: Balcan et al. 2018

– Reduce space complexity• Streaming Heavy Hitters: Hsu et al. 2019

Limitations of Machine LearningLimitations of Machine Learning
Limit 1. Machine learning is imperfect.
– Algorithms must be robust to errors

Limitations of Machine Learning
Limit 1. Machine learning is imperfect.
– Algorithms must be robust to errors

Limit 2. ML is best at learning a few things– Generalization is hard, especially with little data
– e.g. predicting the whole instance is unreasonableLimitations of Machine Learning
Limit 1. Machine learning is imperfect.
– Algorithms must be robust to errors

Limit 2. ML is best at learning a few things– Generalization is hard, especially with little data
– e.g. predicting the whole instance is unreasonable

Limit 3. Most ML minimizes a few different functions– Squared loss is most popular– Esoteric loss functions are hard to optimize (e.g. pricing)But.. the power of ML
Machine learning reduces uncertainty– Image recognition : uncertainty of what is in the image– Click prediction: uncertainty about which ad will be clicked–…

Online Algorithms with ML Advice
Augment online algorithms with some information about thefuture.
Goals:– If the ML prediction is good : algorithm should perform well
• Ideally: perfect predictions lead to competitive ratio of 1

– If the ML prediction is bad : revert back to the non augmented optimum• Then trusting the prediction is “free”– Isolate the role of the prediction as a plug and play mechanism.
• Allow to plug in richer ML models.
• Ensure that better predictions lead to better algorithm performance.

Online Algorithms with ML Advice
Augment online algorithms with some information about thefuture.
Not a new idea:– Advice Model : minimize the number of bits of perfect advice to recover OPT– Noisy Advice: minimize the number of bits of imperfect advice to recover OPT

What is new:
– Look at quality of natural prediction tasks rather than measuring # of bits.

OutlineIntroduction
Motivating Example
Learning Augmented Algorithms– Overview– Online Algorithms: Paging– Streaming Algorithms: Heavy Hitters– Data Structures: Bloom FiltersConclusion

Caching (aka Paging)
Caching problem:
Have a cache of size k.
Elements arrive one a time.
– If arriving element is in the cache: cache hit, cost 0.
– If arriving element is not in the cache. Cache miss. Pay cost of 1.
• Evict one element from the cache, and place the arriving element in its slot

State of the Art (in theory)
Bad News:– Any deterministic algorithm is k-competitive– There exist randomized algorithms that are log k competitive– But no better competitive ratio is possible

A bit unsatisfying:– Would like a constant competitive algorithm– Would like to use theory to guide us in selection of a good algorithm

ML Advice
What kind of ML predictions would be helpful?

ML Advice
What kind of ML predictions would be helpful?
Generally:– The richer the prediction space, the harder it is to learn– Lots of learning theory results quantifying this exactly– Intuition: need enough examples for every possible outcome.

ML Advice
What kind of ML predictions would be helpful?
Generally:– The richer the prediction space, the harder it is to learn– Lots of learning theory results quantifying this exactly– Intuition: need enough examples for every possible outcome

What to predict for caching?

Offline Optimum
What is the offline optimum solution?

Offline Optimum
What is the offline optimum solution?
Simple greedy scheme (Belady’s rule)– Evict element that reappears furthest in the future– Intuition: greedy stays ahead (makes fewest evictions) as compared to any
other strategy.

What to Predict?
What do we need to implement Belady’s rule?
Predict: the next appearance time of each element upon arrival.

Notes:– One prediction at every time step
– No need to worry about consistency of predictions from one time step to thenext

Measuring Error
Tempting:– Use the performance of the predictor, h, in the caching algorithm

Better:– Use a standard error function– For example squared loss, absolute loss, etc.

Why Better?
– Most ML methods are used to optimize squared loss
– Want the training to be independent of how the predictor is used
– Decomposes the problem into (i) find a good prediction and (ii) use thisprediction effectively

A bit more formal
Optimum Algorithm:– Always evict element that appears furthest in the future.

Prediction:– Every time an element arrives, predict when it will appear next
– Today consider absolute loss:⌘=Xi|h(i)t(i)|
Actual Arrival Time (integral)

Predicted Arrival TimeUsing the predictions
Now have a prediction. What’s next?

Blindly Following the Oracle
Algorithm:– Evict element that is predicted to appear furthest in the future

Blindly Following the Oracle
Elements

Predictions of next arrival– x in position 2r– For x : always correct– y in position 2r+1

– For y : always correct– c at position 1,T– For c : 1

c x y x y x y x y x y x y x y x y …

cEvict Element Predicted Furthest in the Future

Blindly Following the Oracle
Elements

Predictions of next arrival– x in position 2r– For x : always correct– y in position 2r+1

– For y : always correct– c at position 1,T– For c : 1

c x y x y x y x y x y x y x y x y …

cAlgorithm :– [t = 2] Initial Cache: [c,x]Evict Element Predicted Furthest in the Future

Blindly Following the Oracle
Elements

Predictions of next arrival– x in position 2r– For x : always correct– y in position 2r+1

– For y : always correct– c at position 1,T– For c : 1c x y x y x y x y x y x y x y x y …

cAlgorithm :– [t = 2] Initial Cache: [c,x]– [t = 3] Evict x, place y: [c,y]Evict Element Predicted Furthest in the Future

Blindly Following the Oracle
Elements

Predictions of next arrival– x in position 2r– For x : always correct– y in position 2r+1

– For y : always correct– c at position 1,T– For c : 1c x y x y x y x y x y x y x y x y …

cAlgorithm :Error :– [t = 2] Initial Cache: [c,x]– Constant on average– [t = 3] Evict x, place y: [c,y]– [t = 4] Evict y, place x: [c,y]–…

Evict Element Predicted Furthest in the Future

Using the Prediction
Blindly following the oracle:– Not a good idea
– Constant average error can lead to super-constant competitive ratio

Algorithms to the rescue!Using the Prediction
Marker Algorithm:– In beginning of a phase all elements unmarked– When an element arrives, mark it.
– When need to evict, pick a random unmarked element– When all elements are marked, start a new phase, and unmark all elements– Theorem: 2 log k - competitive [Fiat+’91].

Predictive Marker [LykourisV’18]
Marker Algorithm:– In beginning of a phase all elements unmarked– When an element arrives, mark it.
– When need to evict, pick a random unmarked element predicted to appear
furthest in the future– When all elements are marked, start a new phase, and unmark all elements

Predictive Marker [LykourisV’18]
Marker Algorithm:– In beginning of a phase all elements unmarked– When an element arrives, mark it.
– When need to evict, pick a random unmarked element predicted to appear
furthest in the future– When all elements are marked, start a new phase, and unmark all elements

Notes:– If predictions are perfect, almost follows Belady’s rule. Recover a 2competitive algorithm.
– When predictions are terrible, algorithm is k-competitive, small tweaks canensure log k competitiveness in the worst case.

Proof Intuition
What causes cache misses?
– Elements appearing that have not been seen for a long time
• OPT has to pay for these as well

– Recent elements being evicted• Tried to minimize this (subject to predictions)• Charge these to error of the predictor• Phases defined by marker cap the maximum impact of errors

Analysis
Main claim:– Suppose the absolute error of predictor during the phase is ⌘ . Then number
pof misses due to mispredictions is at most O( ⌘).
– Intuition: loss on two length t sequences: a,b,c,…,t and t,…,c,b,a is ⌦(t2 ) .

Altogether:– Given a predictor with total error ⌘ , predictive marker has competitive ratio ofpO(1 + 1 + 4⌘/OP T )– Can tune to recover worst case bounds: min(O(p⌘/OP T), (2 + ✏) log k)✏Empirical Slide
Algorithm

Britekite
Competitive ratio

Citi Bike
Competitive ratio

BlindOracle

2.049

2.023

LRU

1.280

1.859

Marker

1.310

1.869

Predictive Marker

1.266

1.810

Discussion:– Blind Oracle is too sensitive to errors in the data– LRU tends to outperform Marker (latter is too pessimistic)– Predictive marker consistently outperforms LRU.

Online Algorithms
Other algorithms analyzed in this setting:– Ski Rental– Non clairvoyant job scheduling– Online scheduling with restricted assignment– Online matching– Online pricing

Many open problems:– Clustering– Submodular Maximization– k-server–…

Outline
Introduction
Motivating Example
Learning Augmented Algorithms– Overview– Online Algorithms– Streaming Algorithms– Data Structures
Conclusion

Streaming Algorithms
See a never ending stream of elements, only allowed to use
small (typically logarithmic) amount of memory.

xyxzarytwzw

rarmxtCanonical question:– Frequency estimation: compute the frequency of every element in the stream– If elements are drawn from U trivial to do in O(|U|) space– How to use less space?

Frequency Estimation: Count Min Sketch
CountMin:– Prepare k hash functions to use B/k buckets each.
– Keep a histogram on frequency of each hash function– Return the minimum hashed value for any elementxyxzarytw

zw

hash1

hash20010

1000

k=2
B=8rarmxt

Frequency Estimation: Count Min Sketch
CountMin:– Prepare k hash functions to use B/k buckets each.
– Keep a histogram on frequency of each hash function– Return the minimum hashed value for any element
xyxzaryt

wzw

hash1

hash200201

100

k=2
B=8rarmxt

Frequency Estimation: Count Min Sketch
CountMin:– Prepare k hash functions to use B/k buckets each.
– Keep a histogram on frequency of each hash function– Return the minimum hashed value for any element
xyxzarytwzw

hash1

hash200

302

100

k=2
B=8rarmxt

Frequency Estimation: Count Min Sketch
CountMin:– Prepare k hash functions to use B/k buckets each.
– Keep a histogram on frequency of each hash function– Return the minimum hashed value for any element
xyxz

arytw

zw

hash1
44

5

4

4

7

4

2

hash2Count(x) = min (4,5)=

4rar

mxt

Learned CountMin [Hsu+’19]
Idea:– Train a classifier to predict whether an item is a heavy hitter– For those predicted to be frequent elements, keep their counts exactly– For the rest, use a CountMin sketch

Frequency Estimation: Count Min Sketch
Learned CountMin:– Predict whether an element is frequent– If so, keep its count exactly– Otherwise, use CountMin
xyx

frequent?

zar

ytw

zxr

10000000w

r

yes

k=2
B=6

ar

mxt

Frequency Estimation: Count Min Sketch
Learned CountMin:– Predict whether an element is frequent– If so, keep its count exactly– Otherwise, use CountMin
xyxzarytw

xr

10w

r

hash1

frequent?
noz001

100y

k=2
B=6

hash2armxt

Frequency Estimation: Count Min Sketch
Learned CountMin:– Predict whether an element is frequent– If so, keep its count exactly– Otherwise, use CountMin
xyxz

yes

ar

ytw

zxr

20001

100w

r

frequent?

k=2
B=6ar

mxt

Analysis
Main question:– Space vs. Accuracy trade-off.
– Fix space of B buckets. Measure accuracyError Function:– “Expected” error– Given true counts fi and estimated counts fˆi .

X
1Err(f, fˆ) =|fi
N ifˆi | · fi

Analysis of Learned CountMin
For Zipf Distributions:– Vanilla Count Min:OO

– Perfect Predictions:– Noisy Predictions:k ln n ln( knB )B
2 nln BB

2Oln2!

!

2 n
B + ln B

B!

Analysis of Learned CountMin
For Zipf Distributions:– Vanilla Count Min:OO

– Perfect Predictions:– Noisy Predictions:

Whenk ln n ln( knB )B
2 nln BB

2Oln2!

O!

2 n
B + ln BBB = ⇥(n)
✓ln nn◆✓ ◆1On!

O✓ 22ln nn◆

Empirical SlideOutline
Introduction
Motivating Example
Online Algorithms
Streaming Algorithms
Data Structures
Conclusion

Outline
Already saw “learned indexes” [Kraska+’18, LykourisV’18]– Predict offset rather than doing binary search
New idea:– Learned Bloom Filters.

Bloom Filters Review
Bloom Filter– Data Structure to test set membership– Never returns a false negative (elements in the set always
returned as in the set)
– Sometimes returns a false positive (elements not in the set
are claimed to be in the set)
Trade-off between space & false positive probability.
xx 62 Z

noBloom Filter for Z

yesx2̃Z

Learned Bloom Filters [Mitzenmacher ’18]
Train a predictor on whether an element is in the set.
– Prediction has both false positive & false negative rates

˜Z
x62

noLearned
Membershipyesx2̃Z

Learned Bloom Filters
Train a predictor on whether an element is in the set.
– Prediction has both false positive & false negative rates

˜Zx62

noLearned
Membershipyesx2̃Zx– Combine the two:

LearnedMembershipyesx2̃Znox 62 Z

noBloom Filter for Z

yesx2̃Z

Learned Bloom Filters
Do a step better:xx 62 Z

noBloom Filter for Z

yes
LearnedMembershipyesx2̃Znox 62 Z

noBloom Filter for Z

yesx2̃Z

Learned Bloom Filters
Do a step better:

Filter out easy negatives
to make learning easierxx 62 Z

noBloom Filter for Z

yesLearnedMembershipyesx2̃Znox 62 Z

noBloom Filter for Z

yesx2̃Z

Learned Bloom Filters
Do a step better:

Filter out easy negatives
to make learning easierxx 62 Z

noBloom Filter for Z

yes
LearnedMembershipyesx2̃Znox 62 Z

noBloom Filter for Z

yesx2̃Z
Back up filter to deal
with prediction errors

Learned Bloom Filter Analysis
Trade-off between error rates and false positive / negative rates.
Main takeaways:– The forward bloom filter makes the learning robust (if, for instance, examples
are from a different distribution)– The backup bloom filter does not grow with input size (it depends more on thequality of the learner)

Conclusion

Overall Question
How to incorporate (noisy, non-uniform) ML predictions toimprove performance (time, space, approximation/competitiveratios) of classical algorithms.

Two Subproblems
Decide on what to predict.
– Predictions should be concise & compact– Should use traditional loss functions

Incorporate predictions into algorithms.
– Full power of algorithm design and analysis– Typically need a “trust but verify” approach

Final Thought
Another way to go beyond worst case analysis.
– Parametrize difficulty of the problem by the quality of the prediction– Formally cast heuristics (e.g. LRU) as learning problems and evaluate theirquality

Thank You