Under Zipfian frequencies, Count-Min's expected error is Θ(k log(kn/B)/B), Count-Sketch gets its first nearly tight bounds, and learned Count-Sketch achieves Θ(1/B).
Optimal Algorithms for Ski Rental with Soft Machine-Learned Predictions
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We consider a variant of the classic Ski Rental online algorithm with applications to machine learning. In our variant, we allow the skier access to a black-box machine-learning algorithm that provides an estimate of the probability that there will be at most a threshold number of ski-days. We derive a class of optimal randomized algorithms to determine the strategy that minimizes the worst-case expected competitive ratio for the skier given a prediction from the machine learning algorithm,and analyze the performance and robustness of these algorithms.
fields
cs.DS 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
(Learned) Frequency Estimation Algorithms under Zipfian Distribution
Under Zipfian frequencies, Count-Min's expected error is Θ(k log(kn/B)/B), Count-Sketch gets its first nearly tight bounds, and learned Count-Sketch achieves Θ(1/B).