Testing Tail Weight of a Distribution Via Hazard Rate

For many computational problems, the distribution of data affects the algorithms we choose to solve them. One important attribute of a distribution is the shape of its "tail", that is, the behavior of the distribution as it moves away from the mean. In some distributions, the frequencies of elements far from the mean drop very quickly ("light-tailed"), while in others, the frequencies of large elements drop more slowly ("heavy-tailed"); consequently, in such "heavy-tailed" distributions, more samples are needed to see important elements. For example, Harchol-Balter in [HB99] has shown that the performances of policies for scheduling computing jobs vary dramatically depending on whether the distribution of the job workloads are heavy-tailed or light-tailed. The shape of the distribution has influenced the design and analysis of learning algorithms - three recent examples include the classification algorithm of [WRH17], the generalization bound of [Fel20] and the frequency estimation result of [HIKV18] (where the latter two are for long-tailed and Zipfian distributions respectively, both subclasses of heavy-tailed distributions).