A perceptron-like online algorithm for tracking the median
Tom Bylander, Bruce E. Rosen · Proceedings of International Conference on Neural Networks (ICNN'97) · 2002
We present an online algorithm for tracking the median of a series of values. The algorithm updates its current estimate of the median by incrementing or decrementing a fixed value, which is analogous to perceptron updating. The median value of a sequence minimizes the absolute loss, i.e., the sum of absolute deviations. The analysis shows that the worst-case absolute loss of our algorithm is comparable to the absolute loss of any sequence of target medians, given restrictions on how much the target can change per trial.