Multiplicative Update Methods for Incremental Quantile Estimation
提出一种轻量级增量分位数估计器，仅需调节一个参数，采用确定性乘法更新，适用于时变分布系统，收敛性由随机学习理论保证，实验表明优于现有方法。
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.