Multiplicative Update Methods for Incremental Quantile Estimation

Abstract

We present a novel lightweight incremental quantile estimator which possesses far less complexity than the Tierney's estimator and its extensions. Notably, our algorithm relies only on tuning one single parameter which is a plausible property which we could only find in the discretized quantile estimator Frugal. This makes our algorithm easy to tune for better performance. Furthermore, our algorithm is multiplicative which makes it highly suitable to handle quantile estimation in systems in which the underlying distribution varies with time. Unlike Frugal and our legacy work which are randomized algorithms, we suggest deterministic updates where the step size is adjusted in a subtle manner to ensure the convergence. The deterministic algorithm is more efficient since the estimate is updated at every iteration. The convergence of the proposed estimator is proven using the theory of stochastic learning. Extensive experimental results show that our estimator clearly outperforms legacy works.