Calibrating Sales Forecast in a Pandemic: Random-Design Online Isotonic Regression

Motivated by our collaboration with a consumer packaged goods (CPG) company, we consider the problem of calibrating sales forecast under the coronavirus disease 2019 (COVID‑19) pandemic. We study the \emph{random-design} online isotonic regression setting, where a decision-maker iteratively predicts the adversarially chosen labels of a sequence of covariates sampled from a given distribution. The goal is to attain small \emph{regret} bound against the loss-minimized (under some suitable metric) isotonic/monotone function in the hindsight. For this setting, we propose a novel and computationally-efficient Sampling Exponential Weights (\texttt{SEW}) policy that incorporates a random sampling scheme (for the future covariates) into the exponential weights algorithm. Different than many traditional online learning algorithms, which only use historical information to make predictions, the \sew~additionally depends on the sampled future covariates. It is thus unclear how one can apply existing regret anallysis techniques to establish a regret bound for the \sew. Nevertheless, we show that the \sew~can achieve the minimax-optimal regret bound by leveraging the relaxation framework derived from the sequential complexity theory and the zero-sum sequential game re-formulation for general online learning problems. Finally, we demonstrate the superior performances of our algorithm on both the synthetic and the CPG company's datasets.